[bugpoint] Add ability to reduce to zero elements

[modocache]

Summary

Depends on https://reviews.llvm.org/D55216.

https://reviews.llvm.org/D55216 implemented reducing function attributes
in bugpoint. However, these attributes are only reduced down to a single
element, so even in the case where function attributes were irrelevant
to the crash being reduced, there would still be one arbitrary attribute
left after the program had been reduced. For example, take the following
program, tested with the bugpoint-crashcalls pass:

define i32 @bar() #0 {
  ret i32 12
}

define i32 @foo() #0 {
  %1 = call i32 @bar()
  ret i32 %1
}

attributes #0 = { "one" "two" "three" }

This program would be "reduced" to having just one attribute:

define i32 @bar() #0 {
  ret i32 12
}

define i32 @foo() #0 {
  %1 = call i32 @bar()
  ret i32 %1
}

attributes #0 = { "two" }

However, clearly the attribute is irrelevant, and so a fully reduced
program would have no attributes.

Implememting reduction to zero attributes required changing ListReducer.
It now takes a "reduction limit" parameter in its initializer. When
given a limit of zero, it attempts to reduce down to zero attributes.
This results in a fully reduced program such as the one below (and such
as is tested in this commit's tests):

define i32 @bar() {
  ret i32 12
}

define i32 @foo() {
  %1 = call i32 @bar()
  ret i32 %1
}

[reames]

A question. Why do we need a 1 limit at all? Wouldn't reducing any list to zero when 1 element is required to produce the failure fail to reduce? I'm wondering if what we want is essentially a base case for the reducer that tries removing the last element, and if it fails, backing off to the single element case.

[reames]

Per previous comment (just getting out of review queue)

test/BugPoint/func-attrs-none.ll

+; Test that reducing function attributes on functions with no attributes works.
+; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes
+; REQUIRES: loadable_module
+
+define dso_local i32 @bar() {
+  ret i32 42
+}
+
+define dso_local i32 @foo() {
+  %1 = call i32 @bar()
+  ret i32 %1
+}

test/BugPoint/func-attrs-zero.ll

+; RUN: bugpoint -load %llvmshlibdir/BugpointPasses%shlibext %s -output-prefix %t -bugpoint-crashcalls -silence-passes
+; RUN: llvm-dis %t-reduced-simplified.bc -o - | FileCheck %s
+; REQUIRES: loadable_module
+
+; Check that all function attributes on bar have been eliminated,
+; since they have nothing to do with the crash.
+; CHECK: bar(){{[^#0-9]*$}}
+define dso_local i32 @bar() #0 {
+  ret i32 42
+}
+
+; Same goes for foo: all attributes should be removed.
+; CHECK: foo(){{[^#0-9]*$}}
+define dso_local i32 @foo() #1 {
+  %1 = call i32 @bar()
+  ret i32 %1
+}
+
+; CHECK-NOT: attributes #
+attributes #0 = { uwtable nounwind "no-frame-pointer-elim-non-leaf" "disable-tail-calls"="false" }
+attributes #1 = { optnone noinline "my-custom-attribute" "no-infs-fp-math"="false" }

tools/bugpoint/CrashDebugger.cpp

 class ReduceCrashingFunctionAttributes : public ListReducer<Attribute> {
   BugDriver &BD;
   std::string FnName;
   BugTester TestFn;
 
 public:
   ReduceCrashingFunctionAttributes(BugDriver &bd, const std::string &FnName,
                                    BugTester testFn)
-      : BD(bd), FnName(FnName), TestFn(testFn) {}
+      : ListReducer(Zero), BD(bd), FnName(FnName), TestFn(testFn) {}
 
   Expected<TestResult> doTest(std::vector<Attribute> &Prefix,
                               std::vector<Attribute> &Kept) override {
-    if (!Kept.empty() && TestFuncAttrs(Kept))
+    if (TestFuncAttrs(Kept))
       return KeepSuffix;
-    if (!Prefix.empty() && TestFuncAttrs(Prefix))
+    if (TestFuncAttrs(Prefix))
       return KeepPrefix;
     return NoFailure;
   }
 
   bool TestFuncAttrs(std::vector<Attribute> &Attrs);
 };
 }
 

tools/bugpoint/ListReducer.h

 
 template <typename ElTy> struct ListReducer {
   enum TestResult {
     NoFailure,  // No failure of the predicate was detected
     KeepSuffix, // The suffix alone satisfies the predicate
     KeepPrefix  // The prefix alone satisfies the predicate
   };
 
+  enum ReductionLimit {
+    Zero, // Keep reducing list elements until none are left.
+    One   // Keep reducing list elements until only one is left.
+  };
+  ReductionLimit ReduceLimit;
+
+  ListReducer(ReductionLimit Limit = One) : ReduceLimit(Limit) {}
+
   virtual ~ListReducer() {}
 
   /// This virtual function should be overriden by subclasses to implement the
   /// test desired.  The testcase is only required to test to see if the Kept
   /// list still satisfies the property, but if it is going to check the prefix
   /// anyway, it can.
   virtual Expected<TestResult> doTest(std::vector<ElTy> &Prefix,
                                       std::vector<ElTy> &Kept) = 0;
 
   /// This function attempts to reduce the length of the specified list while
   /// still maintaining the "test" property.  This is the core of the "work"
   /// that bugpoint does.
   Expected<bool> reduceList(std::vector<ElTy> &TheList) {
     std::vector<ElTy> empty;
     std::mt19937 randomness(0x6e5ea738);  // Seed the random number generator
+    unsigned Limit;
+    switch (ReduceLimit) {
+    case One:
+      Limit = 1;
+      break;
+    case Zero:
+      Limit = 0;
+      break;
+    }
+
     Expected<TestResult> Result = doTest(TheList, empty);
     if (Error E = Result.takeError())
       return std::move(E);
     switch (*Result) {
     case KeepPrefix:
-      if (TheList.size() == 1) // we are done, it's the base case and it fails
+      if (TheList.size() == Limit) // we are done, it's the base case and it fails
         return true;
       else
         break; // there's definitely an error, but we need to narrow it down
 
     case KeepSuffix:
-      // cannot be reached!
+      if (Limit > 0)
         llvm_unreachable("bugpoint ListReducer internal error: "
                          "selected empty set.");
+      else {
+        // If we are reducing to zero, then we're happy to select the empty set,
+        // because that means we're done reducing!
+        TheList.swap(empty);
+        return true;
+      }
+
 
     case NoFailure:
       return false; // there is no failure with the full set of passes/funcs!
     }
 
     // Maximal number of allowed splitting iterations,
     // before the elements are randomly shuffled.
     const unsigned MaxIterationsWithoutProgress = 3;
 
     // Maximal number of allowed single-element trim iterations. We add a
     // threshold here as single-element reductions may otherwise take a
     // very long time to complete.
     const unsigned MaxTrimIterationsWithoutBackJump = 3;
     bool ShufflingEnabled = true;
 
   Backjump:
     unsigned MidTop = TheList.size();
     unsigned MaxIterations = MaxIterationsWithoutProgress;
     unsigned NumOfIterationsWithoutProgress = 0;
-    while (MidTop > 1) { // Binary split reduction loop
+    while (MidTop > Limit) { // Binary split reduction loop
       // Halt if the user presses ctrl-c.
       if (BugpointIsInterrupted) {
         errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
         return true;
       }
 
+      if (NumOfIterationsWithoutProgress > MaxIterations)
+        break;
+
       // If the loop doesn't make satisfying progress, try shuffling.
       // The purpose of shuffling is to avoid the heavy tails of the
       // distribution (improving the speed of convergence).
-      if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) {
+      if (ShufflingEnabled && TheList.size() > 1 &&
+          NumOfIterationsWithoutProgress > MaxIterations) {
         std::vector<ElTy> ShuffledList(TheList);
         std::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
         errs() << "\n\n*** Testing shuffled set...\n\n";
         // Check that random shuffle doesn't lose the bug
         Expected<TestResult> Result = doTest(ShuffledList, empty);
         // TODO: Previously, this error was ignored and we treated it as if
         // shuffling hid the bug. This should really either be consumeError if
         // that behaviour was sensible, or we should propagate the error.
while (MidTop > Limit) { // Binary split reduction loop
       std::vector<ElTy> Prefix(TheList.begin(), TheList.begin() + Mid);
       std::vector<ElTy> Suffix(TheList.begin() + Mid, TheList.end());
 
       Expected<TestResult> Result = doTest(Prefix, Suffix);
       if (Error E = Result.takeError())
         return std::move(E);
       switch (*Result) {
       case KeepSuffix:
-        // The property still holds.  We can just drop the prefix elements, and
-        // shorten the list to the "kept" elements.
-        TheList.swap(Suffix);
+        // The property still holds.  We can drop the prefix elements, and
+        // choose the "kept" elements instead. If the number of kept elements
+        // is smaller than our previous number of elements, we've made progress
+        // in reducing the list.
         MidTop = TheList.size();
-        // Reset progress treshold and progress counter
+        if (Suffix.size() < TheList.size()) {
+          TheList.swap(Suffix);
           MaxIterations = MaxIterationsWithoutProgress;
           NumOfIterationsWithoutProgress = 0;
+        } else
+          NumOfIterationsWithoutProgress++;
         break;
       case KeepPrefix:
         // The predicate still holds, shorten the list to the prefix elements.
         TheList.swap(Prefix);
         MidTop = TheList.size();
         // Reset progress treshold and progress counter
         MaxIterations = MaxIterationsWithoutProgress;
         NumOfIterationsWithoutProgress = 0;