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