Bisect tool: Pass/Transformation level bisection for bad item

This patch provides pass and transformation level bisection support for
existing bisection tool.

Usage: When `--pass_bisect=script_path` is set, pass/transformation
level bisection will be turned on. It only works when prune is set to
False. Orignial bisection will end with the first bad item it find. This
patch then will rebuild and bisect the bad item using bad compiler with
pass/transformation level bisect limit. It will end up with the bad pass
name/index and bad transformation index for that pass.

Notice that this patch still need support from LLVM with this review:
https://reviews.llvm.org/D50031, which allows debugcounter to print info
we need.

The patch eventally add a new binary search process, and two build
function to saparately build with pass and transformation level limit.
A new BinarySearcherForPass is also introduced for pass level bisect.

The workflow is:
    1) get bad item and command to build it with existing bisection.
    2) rebuild bad item with pass level limit to -1 to get total pass
       count.
    3) binary search pass index until we got bad pass.
    4) rebuild bad item with pass limit we get and also set
       transformation level limit to -1 to get total number of
       transforamtion.
    5) binary search transformation index until we got bad
       transformation.

BUG=chromium:878954
TEST=Ran test successfully with Android compiler wrapper. Will add
unittests once new patch in LLVM applied.

Change-Id: I08f376f15d12eea232da5887981c44184ffb9568
Reviewed-on: https://chromium-review.googlesource.com/1208855
Commit-Ready: Zhizhou Yang <zhizhouy@google.com>
Tested-by: Zhizhou Yang <zhizhouy@google.com>
Reviewed-by: Caroline Tice <cmtice@chromium.org>

6 files changed, 397 insertions, 57 deletions

diff --git a/binary_search_tool/android/generate_cmd.sh b/binary_search_tool/android/generate_cmd.sh
index eaae738b..7db3e7e0 100755
--- a/binary_search_tool/android/generate_cmd.sh
+++ b/binary_search_tool/android/generate_cmd.sh
@@ -38,4 +38,15 @@ output+=${result}
 
 echo -e "${output}" > android/cmd_script.sh
 
+chmod u+x android/cmd_script.sh
+
 echo 'Script created as android/cmd_script.sh'
+
+# Check if compiler is LLVM.
+if grep -q "clang" android/cmd_script.sh
+then
+    exit 0
+else
+    echo 'Pass/transformation level bisection only works for LLVM compiler.'
+    exit 1
+fi
\ No newline at end of file
diff --git a/binary_search_tool/binary_search_perforce.py b/binary_search_tool/binary_search_perforce.py
index aaa09eef..a4f8c1c6 100755
--- a/binary_search_tool/binary_search_perforce.py
+++ b/binary_search_tool/binary_search_perforce.py
@@ -1,4 +1,8 @@
 #!/usr/bin/env python2
+
+# Copyright 2018 The Chromium OS Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
 """Module of binary serch for perforce."""
 from __future__ import print_function
 
@@ -63,6 +67,66 @@ class BinarySearchPoint(object):
     self.tag = tag
 
 
+class BinarySearcherForPass(object):
+  """Class of pass level binary searcher."""
+
+  def __init__(self, logger_to_set=None):
+    self.current = 0
+    self.lo = 0
+    self.hi = 0
+    self.total = 0
+    if logger_to_set is not None:
+      self.logger = logger_to_set
+    else:
+      self.logger = logger.GetLogger()
+
+  def GetNext(self):
+    # For the first run, update self.hi with total pass/transformation count
+    if self.hi == 0:
+      self.hi = self.total
+    self.current = (self.hi + self.lo) / 2
+    message = ('Bisecting between: (%d, %d)' % (self.lo, self.hi))
+    self.logger.LogOutput(message, print_to_console=verbose)
+    message = ('Current limit number: %d' % self.current)
+    self.logger.LogOutput(message, print_to_console=verbose)
+    return self.current
+
+  def SetStatus(self, status):
+    """Set lo/hi status based on test script result
+
+    If status == 0, it means that runtime error is not introduced until current
+    pass/transformation, so we need to increase lower bound for binary search.
+
+    If status == 1, it means that runtime error still happens with current pass/
+    transformation, so we need to decrease upper bound for binary search.
+
+    Return:
+      True if we find the bad pass/transformation, or cannot find bad one after
+      decreasing to the first pass/transformation. Otherwise False.
+    """
+    assert status == 0 or status == 1 or status == 125
+
+    if self.current == 0:
+      message = ('Runtime error occurs before first pass/transformation. '
+                 'Stop binary searching.')
+      self.logger.LogOutput(message, print_to_console=verbose)
+      return True
+
+    if status == 0:
+      message = ('Runtime error is not reproduced, increasing lower bound.')
+      self.logger.LogOutput(message, print_to_console=verbose)
+      self.lo = self.current + 1
+    elif status == 1:
+      message = ('Runtime error is reproduced, decreasing upper bound..')
+      self.logger.LogOutput(message, print_to_console=verbose)
+      self.hi = self.current
+
+    if self.lo >= self.hi:
+      return True
+
+    return False
+
+
 class BinarySearcher(object):
   """Class of binary searcher."""
 
@@ -167,9 +231,8 @@ class BinarySearcher(object):
       self.GetNextFlakyBinary()
 
     # TODO: Add an estimated time remaining as well.
-    message = ('Estimated tries: min: %d max: %d\n' %
-               (1 + math.log(self.hi - self.lo, 2),
-                self.hi - self.lo - len(self.skipped_indices)))
+    message = ('Estimated tries: min: %d max: %d\n' % (1 + math.log(
+        self.hi - self.lo, 2), self.hi - self.lo - len(self.skipped_indices)))
     self.logger.LogOutput(message, print_to_console=verbose)
     message = ('lo: %d hi: %d current: %d version: %s\n' %
                (self.lo, self.hi, self.current, self.sorted_list[self.current]))
@@ -186,8 +249,8 @@ class BinarySearcher(object):
   def GetAllPoints(self):
     to_return = ''
     for i in range(len(self.sorted_list)):
-      to_return += ('%d %d %s\n' % (self.points[i].status, i,
-                                    self.points[i].revision))
+      to_return += (
+          '%d %d %s\n' % (self.points[i].status, i, self.points[i].revision))
 
     return to_return
 
@@ -276,8 +339,9 @@ class P4BinarySearcher(VCSBinarySearcher):
     command = 'cd %s && g4 changes ...' % self.checkout_dir
     _, out, _ = self.ce.RunCommandWOutput(command)
     self.changes = re.findall(r'Change (\d+)', out)
-    change_infos = re.findall(r'Change (\d+) on ([\d/]+) by '
-                              r"([^\s]+) ('[^']*')", out)
+    change_infos = re.findall(
+        r'Change (\d+) on ([\d/]+) by '
+        r"([^\s]+) ('[^']*')", out)
     for change_info in change_infos:
       ri = RevisionInfo(change_info[1], change_info[2], change_info[3])
       self.rim[change_info[0]] = ri
@@ -330,9 +394,8 @@ class P4BinarySearcher(VCSBinarySearcher):
       else:
         to_return += ('%s\t%d\t%s\t%s\t%s\t%s\t%s\t%s\n' %
                       (change, ri.status, ri.date, ri.client, ri.description,
-                       self.job_log_root + change + '.cmd',
-                       self.job_log_root + change + '.out',
-                       self.job_log_root + change + '.err'))
+                       self.job_log_root + change + '.cmd', self.job_log_root +
+                       change + '.out', self.job_log_root + change + '.err'))
     return to_return
 
 
@@ -367,9 +430,9 @@ class P4GCCBinarySearcher(P4BinarySearcher):
 
     self.CleanupCLs()
     # Change the revision of only the gcc part of the toolchain.
-    command = ('cd %s/gcctools/google_vendor_src_branch/gcc '
-               '&& g4 revert ...; g4 sync @%s' % (self.checkout_dir,
-                                                  current_revision))
+    command = (
+        'cd %s/gcctools/google_vendor_src_branch/gcc '
+        '&& g4 revert ...; g4 sync @%s' % (self.checkout_dir, current_revision))
     self.current_ce.RunCommand(command)
 
     self.HandleBrokenCLs(current_revision)
@@ -427,8 +490,8 @@ def Main(argv):
       ce = command_executer.GetCommandExecuter()
       command = '%s %s' % (script, p4gccbs.checkout_dir)
       status = ce.RunCommand(command)
-      message = ('Revision: %s produced: %d status\n' % (current_revision,
-                                                         status))
+      message = (
+          'Revision: %s produced: %d status\n' % (current_revision, status))
       logger.GetLogger().LogOutput(message, print_to_console=verbose)
       terminated = p4gccbs.SetStatus(status)
       num_tries -= 1
diff --git a/binary_search_tool/binary_search_state.py b/binary_search_tool/binary_search_state.py
index 645e613c..0d5810c3 100755
--- a/binary_search_tool/binary_search_state.py
+++ b/binary_search_tool/binary_search_state.py
@@ -3,7 +3,6 @@
 # Copyright 2018 The Chromium OS Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
-
 """The binary search wrapper."""
 
 from __future__ import print_function
@@ -14,6 +13,7 @@ import errno
 import math
 import os
 import pickle
+import re
 import sys
 import tempfile
 import time
@@ -26,6 +26,7 @@ from cros_utils import command_executer
 from cros_utils import logger
 
 import binary_search_perforce
+import pass_mapping
 
 GOOD_SET_VAR = 'BISECT_GOOD_SET'
 BAD_SET_VAR = 'BISECT_BAD_SET'
@@ -93,6 +94,8 @@ class BinarySearchState(object):
     self.search_cycles = 0
     self.binary_search = None
     self.all_items = None
+    self.cmd_script = None
+    self.mode = None
     self.PopulateItemsUsingCommand(self.get_initial_items)
     self.currently_good_items = set([])
     self.currently_bad_items = set([])
@@ -188,6 +191,17 @@ class BinarySearchState(object):
     ret, _, _ = self.ce.RunCommandWExceptionCleanup(command)
     return ret
 
+  def GenerateBadCommandScript(self, bad_items):
+    """Generate command line script for building bad item."""
+    assert not self.prune, 'Prune must be false if pass_bisect is set.'
+    assert len(bad_items) == 1, 'Pruning is off, but number of bad ' \
+                                       'items found was not 1.'
+    item = list(bad_items)[0]
+    command = '%s %s' % (self.pass_bisect, item)
+    ret, _, _ = self.ce.RunCommandWExceptionCleanup(
+        command, print_to_console=self.verbose)
+    return ret
+
   def DoVerify(self):
     """Verify correctness of test environment.
 
@@ -222,14 +236,14 @@ class BinarySearchState(object):
         status = self.TestScript()
       assert status == 1, 'When reset_to_bad, status should be 1.'
 
-  def DoSearch(self):
+  def DoSearchBadItems(self):
     """Perform full search for bad items.
 
     Perform full search until prune_iterations number of bad items are found.
     """
     while (True and len(self.all_items) > 1 and
            self.prune_cycles < self.prune_iterations):
-      terminated = self.DoBinarySearch()
+      terminated = self.DoBinarySearchBadItems()
       self.prune_cycles += 1
       if not terminated:
         break
@@ -240,6 +254,7 @@ class BinarySearchState(object):
       if prune_index == len(self.all_items) - 1:
         self.l.LogOutput('First bad item is the last item. Breaking.')
         self.l.LogOutput('Bad items are: %s' % self.all_items[-1])
+        self.found_items.add(self.all_items[-1])
         break
 
       # If already seen item we have no new bad items to find, finish up
@@ -279,24 +294,15 @@ class BinarySearchState(object):
     # If pass level bisecting is set, generate a script which contains command
     # line options to rebuild bad item.
     if self.pass_bisect:
-      assert not self.prune, 'Prune must be false if pass_bisect is set.'
       status = self.GenerateBadCommandScript(self.found_items)
       if status == 0:
-        self.l.LogOutput('Command script generated.')
+        self.cmd_script = os.path.join(
+            os.path.dirname(self.pass_bisect), 'cmd_script.sh')
+        self.l.LogOutput('Command script generated at %s.' % self.cmd_script)
       else:
         raise RuntimeError('Error while generating command script.')
 
-  def GenerateBadCommandScript(self, bad_items):
-    assert len(bad_items) == 1, 'Pruning is off, but number of bad items' \
-                                'found was not 1.'
-    item = list(bad_items)[0]
-
-    command = '%s %s' % (self.pass_bisect, item)
-    ret, _, _ = self.ce.RunCommandWExceptionCleanup(command,
-                  print_to_console=self.verbose)
-    return ret
-
-  def DoBinarySearch(self):
+  def DoBinarySearchBadItems(self):
     """Perform single iteration of binary search."""
     # If in resume mode don't reset search_cycles
     if not self.resumed:
@@ -307,7 +313,7 @@ class BinarySearchState(object):
     terminated = False
     while self.search_cycles < self.iterations and not terminated:
       self.SaveState()
-      self.OutputIterationProgress()
+      self.OutputIterationProgressBadItem()
 
       self.search_cycles += 1
       [bad_items, good_items] = self.GetNextItems()
@@ -328,6 +334,199 @@ class BinarySearchState(object):
     self.l.LogOutput(str(self), print_to_console=self.verbose)
     return terminated
 
+  def CollectPassName(self, pass_info):
+    """Mapping opt-bisect output of pass info to debugcounter name."""
+    self.l.LogOutput('Pass info: %s' % pass_info, print_to_console=self.verbose)
+
+    for desc in pass_mapping.pass_name:
+      if desc in pass_info:
+        return pass_mapping.pass_name[desc]
+
+    # If pass not found, return None
+    return None
+
+  def BuildWithPassLimit(self, limit):
+    """ Rebuild bad item with pass level bisect limit
+
+    Run command line script generated by GenerateBadCommandScript(), with
+    pass level limit flags.
+
+    Return:
+      pass_num: current number of the pass, or total number of passes if
+                limit set to -1.
+      pass_name: The debugcounter name of current limit pass.
+    """
+    os.environ['LIMIT_FLAGS'] = '-mllvm -opt-bisect-limit=' + str(limit)
+    self.l.LogOutput(
+        'Limit flags: %s' % os.environ['LIMIT_FLAGS'],
+        print_to_console=self.verbose)
+    command = self.cmd_script
+    _, _, msg = self.ce.RunCommandWOutput(command, print_to_console=False)
+
+    # Massages we get will be like this:
+    #   BISECT: running pass (9) <Pass Description> on <function> (<file>)
+    #   BISECT: running pass (10) <Pass Description> on <module> (<file>)
+    #   BISECT: NOT running pass (11) <Pass Description> on <SCG> (<file>)
+    #   BISECT: NOT running pass (12) <Pass Description> on <SCG> (<file>)
+    # We want to get the pass description of last running pass, to have
+    # transformation level bisect on it.
+    if 'BISECT: ' not in msg:
+      raise RuntimeError('No bisect info printed, OptBisect may not be '
+                         'supported by the compiler.')
+
+    lines = msg.split('\n')
+    pass_num = 0
+    last_pass = ''
+    for l in lines:
+      if 'running pass' in l:
+        # For situation of limit==-1, we want the total number of passes
+        if limit != -1 and 'BISECT: NOT ' in l:
+          break
+        pass_num += 1
+        last_pass = l
+    if limit != -1 and pass_num != limit:
+      raise ValueError('[Error] While building, limit number does not match.')
+    return pass_num, self.CollectPassName(last_pass)
+
+  def BuildWithTransformLimit(self, limit, pass_name=None, pass_limit=-1):
+    """ Rebuild bad item with transformation level bisect limit
+
+    Run command line script generated by GenerateBadCommandScript(), with
+    pass level limit flags and transformation level limit flags.
+
+    Args:
+      limit: transformation level limit for bad item
+      pass_name: name of bad pass debugcounter from pass level bisect result
+      pass_limit: pass level limit from pass level bisect result
+    Return: Total number of transformations if limit set to -1, else return 0.
+    """
+    counter_name = pass_name
+
+    os.environ['LIMIT_FLAGS'] = '-mllvm -opt-bisect-limit=' + \
+                                str(pass_limit) + \
+                                ' -mllvm -debug-counter=' + counter_name + \
+                                '-count=' + str(limit) + \
+                                ' -mllvm -print-debug-counter'
+    self.l.LogOutput(
+        'Limit flags: %s' % os.environ['LIMIT_FLAGS'],
+        print_to_console=self.verbose)
+    command = self.cmd_script
+    _, _, msg = self.ce.RunCommandWOutput(command, print_to_console=False)
+
+    if 'Counters and values:' not in msg:
+      raise RuntimeError('No bisect info printed, DebugCounter may not be '
+                         'supported by the compiler.')
+
+    # With debugcounter enabled, there will be DebugCounter counting info in
+    # the output.
+    lines = msg.split('\n')
+    for l in lines:
+      if pass_name in l:
+        # Output of debugcounter will be like:
+        #   instcombine-visit: {10, 0, 20}
+        #   dce-transform: {1, 0, -1}
+        # which indicates {Count, Skip, StopAfter}.
+        # The last number should be the limit we set.
+        # We want the first number as the total transformation count.
+        # Split each line by ,|{|} and we can get l_list as:
+        #   ['instcombine: ', '10', '0', '20', '']
+        # and we will need the second item in it.
+        l_list = re.split(',|{|}', l)
+        count = int(l_list[1])
+        if limit == -1:
+          return count
+    # The returned value is only useful when limit == -1, which shows total
+    # transformation count.
+    return 0
+
+  def DoSearchBadPass(self):
+    """Perform full search for bad pass of bad item."""
+    logger.GetLogger().LogOutput('Starting to bisect bad pass for bad item.')
+
+    # Pass level bisection
+    self.mode = 'pass'
+    self.binary_search = binary_search_perforce.BinarySearcherForPass(
+        logger_to_set=self.l)
+    self.binary_search.total, _ = self.BuildWithPassLimit(-1)
+    logger.GetLogger().LogOutput(
+        'Total %s number: %d' % (self.mode, self.binary_search.total))
+
+    pass_index, pass_name = self.DoBinarySearchBadPass()
+
+    if (not pass_name and pass_index == 0):
+      raise ValueError('Bisecting passes cannot reproduce good result.')
+    logger.GetLogger().LogOutput('Bad pass found: %s.' % pass_name)
+
+    # Transformation level bisection.
+    logger.GetLogger().LogOutput('Starting to bisect at transformation level.')
+
+    self.mode = 'transform'
+    self.binary_search = binary_search_perforce.BinarySearcherForPass(
+        logger_to_set=self.l)
+    self.binary_search.total = self.BuildWithTransformLimit(
+        -1, pass_name, pass_index)
+    logger.GetLogger().LogOutput(
+        'Total %s number: %d' % (self.mode, self.binary_search.total))
+
+    trans_index, _ = self.DoBinarySearchBadPass(pass_index, pass_name)
+    if (trans_index == 0):
+      raise ValueError('Bisecting %s cannot reproduce good result.' % pass_name)
+    logger.GetLogger().LogOutput(
+        'Bisection result for bad item %s:\n'
+        'Bad pass: %s at number %d\n'
+        'Bad transformation number: %d' % (self.found_items, pass_name,
+                                           pass_index, trans_index))
+
+  def DoBinarySearchBadPass(self, pass_index=-1, pass_name=None):
+    """Perform single iteration of binary search at pass level
+
+    Args:
+      pass_index: Works for transformation level bisection, indicates the limit
+        number of pass from pass level bisecting result.
+      pass_name: Works for transformation level bisection, indicates
+        DebugCounter name of the bad pass from pass level bisecting result.
+    Return:
+      index: Index of problematic pass/transformation.
+      pass_name: Works for pass level bisection, returns DebugCounter name for
+        bad pass.
+    """
+    # If in resume mode don't reset search_cycles
+    if not self.resumed:
+      self.search_cycles = 0
+    else:
+      self.resumed = False
+
+    terminated = False
+    index = 0
+    while self.search_cycles < self.iterations and not terminated:
+      self.SaveState()
+      self.OutputIterationProgressBadPass()
+
+      self.search_cycles += 1
+      current = self.binary_search.GetNext()
+
+      if self.mode == 'pass':
+        index, pass_name = self.BuildWithPassLimit(current)
+      else:
+        self.BuildWithTransformLimit(current, pass_name, pass_index)
+        index = current
+
+      # TODO: Newly generated object should not directly replace original
+      # one, need to put it somewhere and symbol link original one to it.
+      # Will update cmd_script to do it.
+
+      status = self.TestSetupScript()
+      assert status == 0, 'Test setup should succeed.'
+      status = self.TestScript()
+      terminated = self.binary_search.SetStatus(status)
+
+      if terminated:
+        self.l.LogOutput('Terminated!', print_to_console=self.verbose)
+    if not terminated:
+      self.l.LogOutput('Ran out of iterations searching...')
+    self.l.LogOutput(str(self), print_to_console=self.verbose)
+    return index, pass_name
+
   def PopulateItemsUsingCommand(self, command):
     """Update all_items and binary search logic from executable.
 
@@ -460,15 +659,21 @@ class BinarySearchState(object):
     progress = progress % (self.ElapsedTimeString(), progress_text)
     self.l.LogOutput(progress)
 
-  def OutputIterationProgress(self):
+  def OutputIterationProgressBadItem(self):
     out = ('Search %d of estimated %d.\n'
            'Prune %d of max %d.\n'
            'Current bad items found:\n'
            '%s\n')
     out = out % (self.search_cycles + 1,
-                 math.ceil(math.log(len(self.all_items), 2)),
-                 self.prune_cycles + 1, self.prune_iterations,
-                 ', '.join(self.found_items))
+                 math.ceil(math.log(len(self.all_items), 2)), self.prune_cycles
+                 + 1, self.prune_iterations, ', '.join(self.found_items))
+    self._OutputProgress(out)
+
+  def OutputIterationProgressBadPass(self):
+    out = ('Search %d of estimated %d.\n' 'Current limit: %s\n')
+    out = out % (self.search_cycles + 1,
+                 math.ceil(math.log(self.binary_search.total, 2)),
+                 self.binary_search.current)
     self._OutputProgress(out)
 
   def __str__(self):
@@ -532,30 +737,34 @@ def Run(get_initial_items,
         prune_iterations=100,
         verbose=False,
         resume=False):
-  """Run binary search tool. Equivalent to running through terminal.
+  """Run binary search tool.
+
+  Equivalent to running through terminal.
 
   Args:
     get_initial_items: Script to enumerate all items being binary searched
     switch_to_good: Script that will take items as input and switch them to good
-                    set
+      set
     switch_to_bad: Script that will take items as input and switch them to bad
-                   set
+      set
     test_script: Script that will determine if the current combination of good
-                 and bad items make a "good" or "bad" result.
+      and bad items make a "good" or "bad" result.
     test_setup_script: Script to do necessary setup (building, compilation,
-                       etc.) for test_script.
+      etc.) for test_script.
     iterations: How many binary search iterations to run before exiting.
     prune: If False the binary search tool will stop when the first bad item is
-           found. Otherwise then binary search tool will continue searching
-           until all bad items are found (or prune_iterations is reached).
-    pass_bisect: Script that takes single bad item from POPULATE_BAD and
-                 returns the compiler command used to generate the bad item.
-                 Requires that 'prune' be set to False.
+      found. Otherwise then binary search tool will continue searching until all
+      bad items are found (or prune_iterations is reached).
+    pass_bisect: Script that takes single bad item from POPULATE_BAD and returns
+      the compiler command used to generate the bad item. This will turn on
+      pass/ transformation level bisection for the bad item. Requires that
+      'prune' be set to False, and needs support of `-opt-bisect-limit`(pass)
+      and `-print-debug-counter`(transformation) from LLVM.
     noincremental: Whether to send "diffs" of good/bad items to switch scripts.
     file_args: If True then arguments to switch scripts will be a file name
-               containing a newline separated list of the items to switch.
-    verify: If True, run tests to ensure initial good/bad sets actually
-            produce a good/bad result.
+      containing a newline separated list of the items to switch.
+    verify: If True, run tests to ensure initial good/bad sets actually produce
+      a good/bad result.
     prune_iterations: Max number of bad items to search for.
     verbose: If True will print extra debug information to user.
     resume: If True will resume using STATE_FILE.
@@ -578,8 +787,8 @@ def Run(get_initial_items,
                                  'ignoring given options and loading saved '
                                  'options instead.')
   else:
-    if not (get_initial_items and switch_to_good and
-            switch_to_bad and test_script):
+    if not (get_initial_items and switch_to_good and switch_to_bad and
+            test_script):
       logger.GetLogger().LogOutput('The following options are required: '
                                    '[-i, -g, -b, -t] | [-r]')
       return 1
@@ -606,7 +815,9 @@ def Run(get_initial_items,
     bss.DoVerify()
 
   try:
-    bss.DoSearch()
+    bss.DoSearchBadItems()
+    if pass_bisect:
+      bss.DoSearchBadPass()
     bss.RemoveState()
     logger.GetLogger().LogOutput(
         'Total execution time: %s' % bss.ElapsedTimeString())
diff --git a/binary_search_tool/common.py b/binary_search_tool/common.py
index 1d950ced..2850801c 100644
--- a/binary_search_tool/common.py
+++ b/binary_search_tool/common.py
@@ -196,9 +196,12 @@ def _BuildArgsDict(args):
       dest='pass_bisect',
       default=None,
       help='Script to generate another script for pass level bisect, '
-           'which contains command line options to build bad item.'
+           'which contains command line options to build bad item. '
+           'This will also turn on pass/transformation level bisection. '
+           'Needs support of `-opt-bisect-limit`(pass) and '
+           '`-print-debug-counter`(transformation) from LLVM. '
            'For now it only supports one single bad item, so to use it, '
-           'prune must be set to false.')
+           'prune must be set to False.')
   # No input (evals to False),
   # --noincremental (evals to True),
   # --noincremental=False,
diff --git a/binary_search_tool/pass_mapping.py b/binary_search_tool/pass_mapping.py
new file mode 100644
index 00000000..cb80910c
--- /dev/null
+++ b/binary_search_tool/pass_mapping.py
@@ -0,0 +1,32 @@
+# Copyright 2018 The Chromium OS Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+"""Config file for pass level bisection
+
+Provides a mapping from pass info from -opt-bisect result to DebugCounter name.
+"""
+pass_name = {
+    # The list now contains all the passes in LLVM that support DebugCounter at
+    # transformation level.
+    # We will need to keep updating this map after more DebugCounter added to
+    # each pass in LLVM.
+    # For users who make local changes to passes, please add a map from pass
+    # description to newly introduced DebugCounter name for transformation
+    # level bisection purpose.
+    'Hoist/decompose integer division and remainder':
+        'div-rem-pairs-transform',
+    'Early CSE':
+        'early-cse',
+    'Falkor HW Prefetch Fix Late Phase':
+        'falkor-hwpf',
+    'Combine redundant instructions':
+        'instcombine-visit',
+    'Machine Copy Propagation Pass':
+        'machine-cp-fwd',
+    'Global Value Numbering':
+        'newgvn-phi',
+    'PredicateInfo Printer':
+        'predicateinfo-rename',
+    'SI Insert Waitcnts':
+        'si-insert-waitcnts-forceexp',
+}
diff --git a/binary_search_tool/test/binary_search_tool_tester.py b/binary_search_tool/test/binary_search_tool_tester.py
index e733d9c4..923ea112 100755
--- a/binary_search_tool/test/binary_search_tool_tester.py
+++ b/binary_search_tool/test/binary_search_tool_tester.py
@@ -1,6 +1,8 @@
 #!/usr/bin/env python2
 
-# Copyright 2012 Google Inc. All Rights Reserved.
+# Copyright 2018 The Chromium OS Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
 """Tests for bisecting tool."""
 
 from __future__ import print_function
@@ -283,7 +285,7 @@ class BisectingUtilsTest(unittest.TestCase):
         prune=True,
         file_args=True,
         iterations=1)
-    bss.DoSearch()
+    bss.DoSearchBadItems()
     self.assertFalse(bss.found_items)
 
   def test_no_prune(self):
@@ -295,7 +297,25 @@ class BisectingUtilsTest(unittest.TestCase):
         test_setup_script='./test_setup.py',
         prune=False,
         file_args=True)
-    bss.DoSearch()
+    bss.DoSearchBadItems()
+    self.assertEquals(len(bss.found_items), 1)
+
+    bad_objs = common.ReadObjectsFile()
+    found_obj = int(bss.found_items.pop())
+    self.assertEquals(bad_objs[found_obj], 1)
+
+  def test_pass_bisect(self):
+    bss = binary_search_state.MockBinarySearchState(
+        get_initial_items='./gen_init_list.py',
+        switch_to_good='./switch_to_good.py',
+        switch_to_bad='./switch_to_bad.py',
+        pass_bisect='./generate_cmd.py',
+        test_script='./is_good.py',
+        test_setup_script='./test_setup.py',
+        prune=False,
+        file_args=True)
+    # TODO: Need to design unit tests for pass level bisection
+    bss.DoSearchBadItems()
     self.assertEquals(len(bss.found_items), 1)
 
     bad_objs = common.ReadObjectsFile()