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>

1 files changed, 32 insertions, 0 deletions

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',
+}