tools/bisection-search/bisection_search.py

#!/usr/bin/env python3.4
#
# Copyright (C) 2016 The Android Open Source Project
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""Performs bisection bug search on methods and optimizations.

See README.md.

Example usage:
./bisection-search.py -cp classes.dex --expected-output output Test
"""

import argparse
import re
import sys

from common import DeviceTestEnv
from common import FatalError
from common import GetEnvVariableOrError
from common import HostTestEnv

# Passes that are never disabled during search process because disabling them
# would compromise correctness.
MANDATORY_PASSES = ['dex_cache_array_fixups_arm',
                    'dex_cache_array_fixups_mips',
                    'instruction_simplifier$before_codegen',
                    'pc_relative_fixups_x86',
                    'pc_relative_fixups_mips',
                    'x86_memory_operand_generation']

# Passes that show up as optimizations in compiler verbose output but aren't
# driven by run-passes mechanism. They are mandatory and will always run, we
# never pass them to --run-passes.
NON_PASSES = ['builder', 'prepare_for_register_allocation',
              'liveness', 'register']


class Dex2OatWrapperTestable(object):
  """Class representing a testable compilation.

  Accepts filters on compiled methods and optimization passes.
  """

  def __init__(self, base_cmd, test_env, class_name, args,
               expected_output=None, verbose=False):
    """Constructor.

    Args:
      base_cmd: list of strings, base command to run.
      test_env: ITestEnv.
      class_name: string, name of class to run.
      args: list of strings, program arguments to pass.
      expected_output: string, expected output to compare against or None.
      verbose: bool, enable verbose output.
    """
    self._base_cmd = base_cmd
    self._test_env = test_env
    self._class_name = class_name
    self._args = args
    self._expected_output = expected_output
    self._compiled_methods_path = self._test_env.CreateFile('compiled_methods')
    self._passes_to_run_path = self._test_env.CreateFile('run_passes')
    self._verbose = verbose

  def Test(self, compiled_methods, passes_to_run=None):
    """Tests compilation with compiled_methods and run_passes switches active.

    If compiled_methods is None then compiles all methods.
    If passes_to_run is None then runs default passes.

    Args:
      compiled_methods: list of strings representing methods to compile or None.
      passes_to_run: list of strings representing passes to run or None.

    Returns:
      True if test passes with given settings. False otherwise.
    """
    if self._verbose:
      print('Testing methods: {0} passes:{1}.'.format(
          compiled_methods, passes_to_run))
    cmd = self._PrepareCmd(compiled_methods=compiled_methods,
                           passes_to_run=passes_to_run,
                           verbose_compiler=True)
    (output, _, ret_code) = self._test_env.RunCommand(cmd)
    res = ret_code == 0 and (self._expected_output is None
                             or output == self._expected_output)
    if self._verbose:
      print('Test passed: {0}.'.format(res))
    return res

  def GetAllMethods(self):
    """Get methods compiled during the test.

    Returns:
      List of strings representing methods compiled during the test.

    Raises:
      FatalError: An error occurred when retrieving methods list.
    """
    cmd = self._PrepareCmd(verbose_compiler=True)
    (_, err_output, _) = self._test_env.RunCommand(cmd)
    match_methods = re.findall(r'Building ([^\n]+)\n', err_output)
    if not match_methods:
      raise FatalError('Failed to retrieve methods list. '
                       'Not recognized output format.')
    return match_methods

  def GetAllPassesForMethod(self, compiled_method):
    """Get all optimization passes ran for a method during the test.

    Args:
      compiled_method: string representing method to compile.

    Returns:
      List of strings representing passes ran for compiled_method during test.

    Raises:
      FatalError: An error occurred when retrieving passes list.
    """
    cmd = self._PrepareCmd(compiled_methods=[compiled_method],
                           verbose_compiler=True)
    (_, err_output, _) = self._test_env.RunCommand(cmd)
    match_passes = re.findall(r'Starting pass: ([^\n]+)\n', err_output)
    if not match_passes:
      raise FatalError('Failed to retrieve passes list. '
                       'Not recognized output format.')
    return [p for p in match_passes if p not in NON_PASSES]

  def _PrepareCmd(self, compiled_methods=None, passes_to_run=None,
                  verbose_compiler=False):
    """Prepare command to run."""
    cmd = list(self._base_cmd)
    if compiled_methods is not None:
      self._test_env.WriteLines(self._compiled_methods_path, compiled_methods)
      cmd += ['-Xcompiler-option', '--compiled-methods={0}'.format(
          self._compiled_methods_path)]
    if passes_to_run is not None:
      self._test_env.WriteLines(self._passes_to_run_path, passes_to_run)
      cmd += ['-Xcompiler-option', '--run-passes={0}'.format(
          self._passes_to_run_path)]
    if verbose_compiler:
      cmd += ['-Xcompiler-option', '--runtime-arg', '-Xcompiler-option',
              '-verbose:compiler']
    cmd += ['-classpath', self._test_env.classpath, self._class_name]
    cmd += self._args
    return cmd


def BinarySearch(start, end, test):
  """Binary search integers using test function to guide the process."""
  while start < end:
    mid = (start + end) // 2
    if test(mid):
      start = mid + 1
    else:
      end = mid
  return start


def FilterPasses(passes, cutoff_idx):
  """Filters passes list according to cutoff_idx but keeps mandatory passes."""
  return [opt_pass for idx, opt_pass in enumerate(passes)
          if opt_pass in MANDATORY_PASSES or idx < cutoff_idx]


def BugSearch(testable):
  """Find buggy (method, optimization pass) pair for a given testable.

  Args:
    testable: Dex2OatWrapperTestable.

  Returns:
    (string, string) tuple. First element is name of method which when compiled
    exposes test failure. Second element is name of optimization pass such that
    for aforementioned method running all passes up to and excluding the pass
    results in test passing but running all passes up to and including the pass
    results in test failing.

    (None, None) if test passes when compiling all methods.
    (string, None) if a method is found which exposes the failure, but the
      failure happens even when running just mandatory passes.

  Raises:
    FatalError: Testable fails with no methods compiled.
    AssertionError: Method failed for all passes when bisecting methods, but
    passed when bisecting passes. Possible sporadic failure.
  """
  all_methods = testable.GetAllMethods()
  faulty_method_idx = BinarySearch(
      0,
      len(all_methods),
      lambda mid: testable.Test(all_methods[0:mid]))
  if faulty_method_idx == len(all_methods):
    return (None, None)
  if faulty_method_idx == 0:
    raise FatalError('Testable fails with no methods compiled. '
                     'Perhaps issue lies outside of compiler.')
  faulty_method = all_methods[faulty_method_idx - 1]
  all_passes = testable.GetAllPassesForMethod(faulty_method)
  faulty_pass_idx = BinarySearch(
      0,
      len(all_passes),
      lambda mid: testable.Test([faulty_method],
                                FilterPasses(all_passes, mid)))
  if faulty_pass_idx == 0:
    return (faulty_method, None)
  assert faulty_pass_idx != len(all_passes), 'Method must fail for some passes.'
  faulty_pass = all_passes[faulty_pass_idx - 1]
  return (faulty_method, faulty_pass)


def PrepareParser():
  """Prepares argument parser."""
  parser = argparse.ArgumentParser()
  parser.add_argument(
      '-cp', '--classpath', required=True, type=str, help='classpath')
  parser.add_argument('--expected-output', type=str,
                      help='file containing expected output')
  parser.add_argument(
      '--device', action='store_true', default=False, help='run on device')
  parser.add_argument('classname', type=str, help='name of class to run')
  parser.add_argument('--lib', dest='lib', type=str, default='libart.so',
                      help='lib to use, default: libart.so')
  parser.add_argument('--64', dest='x64', action='store_true',
                      default=False, help='x64 mode')
  parser.add_argument('--dalvikvm-option', dest='dalvikvm_opts',
                      metavar='OPTION', nargs='*', default=[],
                      help='additional dalvikvm option')
  parser.add_argument('--arg', dest='test_args', nargs='*', default=[],
                      help='argument to pass to program')
  parser.add_argument('--image', type=str, help='path to image')
  parser.add_argument('--verbose', action='store_true',
                      default=False, help='enable verbose output')
  return parser


def main():
  # Parse arguments
  parser = PrepareParser()
  args = parser.parse_args()

  # Prepare environment
  if args.expected_output is not None:
    with open(args.expected_output, 'r') as f:
      expected_output = f.read()
  else:
    expected_output = None
  if args.device:
    run_cmd = ['dalvikvm64'] if args.x64 else ['dalvikvm32']
    test_env = DeviceTestEnv(args.classpath)
  else:
    run_cmd = ['dalvikvm64'] if args.x64 else ['dalvikvm32']
    run_cmd += ['-XXlib:{0}'.format(args.lib)]
    if not args.image:
      image_path = '{0}/framework/core-optimizing-pic.art'.format(
          GetEnvVariableOrError('ANDROID_HOST_OUT'))
    else:
      image_path = args.image
    run_cmd += ['-Ximage:{0}'.format(image_path)]
    if args.dalvikvm_opts:
      run_cmd += args.dalvikvm_opts
    test_env = HostTestEnv(args.classpath, args.x64)

  # Perform the search
  try:
    testable = Dex2OatWrapperTestable(run_cmd, test_env, args.classname,
                                      args.test_args, expected_output,
                                      args.verbose)
    (method, opt_pass) = BugSearch(testable)
  except Exception as e:
    print('Error. Refer to logfile: {0}'.format(test_env.logfile.name))
    test_env.logfile.write('Exception: {0}\n'.format(e))
    raise

  # Report results
  if method is None:
    print('Couldn\'t find any bugs.')
  elif opt_pass is None:
    print('Faulty method: {0}. Fails with just mandatory passes.'.format(
        method))
  else:
    print('Faulty method and pass: {0}, {1}.'.format(method, opt_pass))
  print('Logfile: {0}'.format(test_env.logfile.name))
  sys.exit(0)


if __name__ == '__main__':
  main()