tools/bugpoint/ListReducer.h

   1 //===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This class is to be used as a base class for operations that want to zero in
  10 // on a subset of the input which still causes the bug we are tracking.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
  15 #define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
  16
  17 #include "llvm/Support/Error.h"
  18 #include "llvm/Support/raw_ostream.h"
  19 #include <algorithm>
  20 #include <cstdlib>
  21 #include <random>
  22 #include <vector>
  23
  24 namespace llvm {
  25
  26 extern bool BugpointIsInterrupted;
  27
  28 template <typename ElTy> struct ListReducer {
  29   enum TestResult {
  30     NoFailure,  // No failure of the predicate was detected
  31     KeepSuffix, // The suffix alone satisfies the predicate
  32     KeepPrefix  // The prefix alone satisfies the predicate
  33   };
  34
  35   virtual ~ListReducer() {}
  36
  37   /// This virtual function should be overriden by subclasses to implement the
  38   /// test desired.  The testcase is only required to test to see if the Kept
  39   /// list still satisfies the property, but if it is going to check the prefix
  40   /// anyway, it can.
  41   virtual Expected<TestResult> doTest(std::vector<ElTy> &Prefix,
  42                                       std::vector<ElTy> &Kept) = 0;
  43
  44   /// This function attempts to reduce the length of the specified list while
  45   /// still maintaining the "test" property.  This is the core of the "work"
  46   /// that bugpoint does.
  47   Expected<bool> reduceList(std::vector<ElTy> &TheList) {
  48     std::vector<ElTy> empty;
  49     std::mt19937 randomness(0x6e5ea738);  // Seed the random number generator
  50     Expected<TestResult> Result = doTest(TheList, empty);
  51     if (Error E = Result.takeError())
  52       return std::move(E);
  53     switch (*Result) {
  54     case KeepPrefix:
  55       if (TheList.size() == 1) // we are done, it's the base case and it fails
  56         return true;
  57       else
  58         break; // there's definitely an error, but we need to narrow it down
  59
  60     case KeepSuffix:
  61       // cannot be reached!
  62       llvm_unreachable("bugpoint ListReducer internal error: "
  63                        "selected empty set.");
  64
  65     case NoFailure:
  66       return false; // there is no failure with the full set of passes/funcs!
  67     }
  68
  69     // Maximal number of allowed splitting iterations,
  70     // before the elements are randomly shuffled.
  71     const unsigned MaxIterationsWithoutProgress = 3;
  72
  73     // Maximal number of allowed single-element trim iterations. We add a
  74     // threshold here as single-element reductions may otherwise take a
  75     // very long time to complete.
  76     const unsigned MaxTrimIterationsWithoutBackJump = 3;
  77     bool ShufflingEnabled = true;
  78
  79   Backjump:
  80     unsigned MidTop = TheList.size();
  81     unsigned MaxIterations = MaxIterationsWithoutProgress;
  82     unsigned NumOfIterationsWithoutProgress = 0;
  83     while (MidTop > 1) { // Binary split reduction loop
  84       // Halt if the user presses ctrl-c.
  85       if (BugpointIsInterrupted) {
  86         errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
  87         return true;
  88       }
  89
  90       // If the loop doesn't make satisfying progress, try shuffling.
  91       // The purpose of shuffling is to avoid the heavy tails of the
  92       // distribution (improving the speed of convergence).
  93       if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) {
  94         std::vector<ElTy> ShuffledList(TheList);
  95         std::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
  96         errs() << "\n\n*** Testing shuffled set...\n\n";
  97         // Check that random shuffle doesn't lose the bug
  98         Expected<TestResult> Result = doTest(ShuffledList, empty);
  99         // TODO: Previously, this error was ignored and we treated it as if
 100         // shuffling hid the bug. This should really either be consumeError if
 101         // that behaviour was sensible, or we should propagate the error.
 102         assert(!Result.takeError() && "Shuffling caused internal error?");
 103
 104         if (*Result == KeepPrefix) {
 105           // If the bug is still here, use the shuffled list.
 106           TheList.swap(ShuffledList);
 107           MidTop = TheList.size();
 108           // Must increase the shuffling treshold to avoid the small
 109           // probability of infinite looping without making progress.
 110           MaxIterations += 2;
 111           errs() << "\n\n*** Shuffling does not hide the bug...\n\n";
 112         } else {
 113           ShufflingEnabled = false; // Disable shuffling further on
 114           errs() << "\n\n*** Shuffling hides the bug...\n\n";
 115         }
 116         NumOfIterationsWithoutProgress = 0;
 117       }
 118
 119       unsigned Mid = MidTop / 2;
 120       std::vector<ElTy> Prefix(TheList.begin(), TheList.begin() + Mid);
 121       std::vector<ElTy> Suffix(TheList.begin() + Mid, TheList.end());
 122
 123       Expected<TestResult> Result = doTest(Prefix, Suffix);
 124       if (Error E = Result.takeError())
 125         return std::move(E);
 126       switch (*Result) {
 127       case KeepSuffix:
 128         // The property still holds.  We can just drop the prefix elements, and
 129         // shorten the list to the "kept" elements.
 130         TheList.swap(Suffix);
 131         MidTop = TheList.size();
 132         // Reset progress treshold and progress counter
 133         MaxIterations = MaxIterationsWithoutProgress;
 134         NumOfIterationsWithoutProgress = 0;
 135         break;
 136       case KeepPrefix:
 137         // The predicate still holds, shorten the list to the prefix elements.
 138         TheList.swap(Prefix);
 139         MidTop = TheList.size();
 140         // Reset progress treshold and progress counter
 141         MaxIterations = MaxIterationsWithoutProgress;
 142         NumOfIterationsWithoutProgress = 0;
 143         break;
 144       case NoFailure:
 145         // Otherwise the property doesn't hold.  Some of the elements we removed
 146         // must be necessary to maintain the property.
 147         MidTop = Mid;
 148         NumOfIterationsWithoutProgress++;
 149         break;
 150       }
 151     }
 152
 153     // Probability of backjumping from the trimming loop back to the binary
 154     // split reduction loop.
 155     const int BackjumpProbability = 10;
 156
 157     // Okay, we trimmed as much off the top and the bottom of the list as we
 158     // could.  If there is more than two elements in the list, try deleting
 159     // interior elements and testing that.
 160     //
 161     if (TheList.size() > 2) {
 162       bool Changed = true;
 163       std::vector<ElTy> EmptyList;
 164       unsigned TrimIterations = 0;
 165       while (Changed) { // Trimming loop.
 166         Changed = false;
 167
 168         // If the binary split reduction loop made an unfortunate sequence of
 169         // splits, the trimming loop might be left off with a huge number of
 170         // remaining elements (large search space). Backjumping out of that
 171         // search space and attempting a different split can significantly
 172         // improve the convergence speed.
 173         if (std::rand() % 100 < BackjumpProbability)
 174           goto Backjump;
 175
 176         for (unsigned i = 1; i < TheList.size() - 1; ++i) {
 177           // Check interior elts
 178           if (BugpointIsInterrupted) {
 179             errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
 180             return true;
 181           }
 182
 183           std::vector<ElTy> TestList(TheList);
 184           TestList.erase(TestList.begin() + i);
 185
 186           Expected<TestResult> Result = doTest(EmptyList, TestList);
 187           if (Error E = Result.takeError())
 188             return std::move(E);
 189           if (*Result == KeepSuffix) {
 190             // We can trim down the list!
 191             TheList.swap(TestList);
 192             --i; // Don't skip an element of the list
 193             Changed = true;
 194           }
 195         }
 196         if (TrimIterations >= MaxTrimIterationsWithoutBackJump)
 197           break;
 198         TrimIterations++;
 199       }
 200     }
 201
 202     return true; // there are some failure and we've narrowed them down
 203   }
 204 };
 205
 206 } // End llvm namespace
 207
 208 #endif