Bisection bug search tool
Bisection Bug Search is a tool for finding compiler optimization
bugs. It accepts a program which exposes a bug by producing incorrect
output and expected correct output for the program. The tool will
then attempt to narrow down the issue to a single method and
optimization pass.
Given methods in order M0..Mn finds smallest i such that compiling
Mi and interpreting all other methods produces incorrect output.
Then, given ordered optimization passes P0..Pl, finds smallest j
such that compiling Mi with passes P0..Pj-1 produces expected output
and compiling Mi with passes P0..Pj produces incorrect output.
Prints Mi and Pj.
Test: unit tests ./art/tools/bisection-search/tests.py
Manual testing:
./bisection-search.py -cp classes.dex --expected-output output Test
Change-Id: Ic40a82184975d42c9a403f697995e5c9654b8e52
diff --git a/tools/bisection-search/bisection_search.py b/tools/bisection-search/bisection_search.py
new file mode 100755
index 0000000..d6c1749
--- /dev/null
+++ b/tools/bisection-search/bisection_search.py
@@ -0,0 +1,300 @@
+#!/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()