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 LLVM_TOOLS_BUGPOINT_LISTREDUCER_H 16 #define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H 17 18 #include "llvm/Support/ErrorHandling.h" 19 #include "llvm/Support/raw_ostream.h" 20 #include <algorithm> 21 #include <cstdlib> 22 #include <vector> 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 79 // Maximal number of allowed single-element trim iterations. We add a 80 // threshhold here as single-element reductions may otherwise take a 81 // very long time to complete. 82 const unsigned MaxTrimIterationsWithoutBackJump = 3; 83 bool ShufflingEnabled = true; 84 85 Backjump: 86 unsigned MidTop = TheList.size(); 87 unsigned MaxIterations = MaxIterationsWithoutProgress; 88 unsigned NumOfIterationsWithoutProgress = 0; 89 while (MidTop > 1) { // Binary split reduction loop 90 // Halt if the user presses ctrl-c. 91 if (BugpointIsInterrupted) { 92 errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; 93 return true; 94 } 95 96 // If the loop doesn't make satisfying progress, try shuffling. 97 // The purpose of shuffling is to avoid the heavy tails of the 98 // distribution (improving the speed of convergence). 99 if (ShufflingEnabled && 100 NumOfIterationsWithoutProgress > MaxIterations) { 101 std::vector<ElTy> ShuffledList(TheList); 102 std::random_shuffle(ShuffledList.begin(), ShuffledList.end()); 103 errs() << "\n\n*** Testing shuffled set...\n\n"; 104 // Check that random shuffle doesn't loose the bug 105 if (doTest(ShuffledList, empty, Error) == KeepPrefix) { 106 // If the bug is still here, use the shuffled list. 107 TheList.swap(ShuffledList); 108 MidTop = TheList.size(); 109 // Must increase the shuffling treshold to avoid the small 110 // probability of inifinite looping without making progress. 111 MaxIterations += 2; 112 errs() << "\n\n*** Shuffling does not hide the bug...\n\n"; 113 } else { 114 ShufflingEnabled = false; // Disable shuffling further on 115 errs() << "\n\n*** Shuffling hides the bug...\n\n"; 116 } 117 NumOfIterationsWithoutProgress = 0; 118 } 119 120 unsigned Mid = MidTop / 2; 121 std::vector<ElTy> Prefix(TheList.begin(), TheList.begin()+Mid); 122 std::vector<ElTy> Suffix(TheList.begin()+Mid, TheList.end()); 123 124 switch (doTest(Prefix, Suffix, Error)) { 125 case KeepSuffix: 126 // The property still holds. We can just drop the prefix elements, and 127 // shorten the list to the "kept" elements. 128 TheList.swap(Suffix); 129 MidTop = TheList.size(); 130 // Reset progress treshold and progress counter 131 MaxIterations = MaxIterationsWithoutProgress; 132 NumOfIterationsWithoutProgress = 0; 133 break; 134 case KeepPrefix: 135 // The predicate still holds, shorten the list to the prefix elements. 136 TheList.swap(Prefix); 137 MidTop = TheList.size(); 138 // Reset progress treshold and progress counter 139 MaxIterations = MaxIterationsWithoutProgress; 140 NumOfIterationsWithoutProgress = 0; 141 break; 142 case NoFailure: 143 // Otherwise the property doesn't hold. Some of the elements we removed 144 // must be necessary to maintain the property. 145 MidTop = Mid; 146 NumOfIterationsWithoutProgress++; 147 break; 148 case InternalError: 149 return true; // Error was set by doTest. 150 } 151 assert(Error.empty() && "doTest did not return InternalError for error"); 152 } 153 154 // Probability of backjumping from the trimming loop back to the binary 155 // split reduction loop. 156 const int BackjumpProbability = 10; 157 158 // Okay, we trimmed as much off the top and the bottom of the list as we 159 // could. If there is more than two elements in the list, try deleting 160 // interior elements and testing that. 161 // 162 if (TheList.size() > 2) { 163 bool Changed = true; 164 std::vector<ElTy> EmptyList; 165 unsigned TrimIterations = 0; 166 while (Changed) { // Trimming loop. 167 Changed = false; 168 169 // If the binary split reduction loop made an unfortunate sequence of 170 // splits, the trimming loop might be left off with a huge number of 171 // remaining elements (large search space). Backjumping out of that 172 // search space and attempting a different split can significantly 173 // improve the convergence speed. 174 if (std::rand() % 100 < BackjumpProbability) 175 goto Backjump; 176 177 for (unsigned i = 1; i < TheList.size()-1; ++i) { // 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 if (doTest(EmptyList, TestList, Error) == KeepSuffix) { 187 // We can trim down the list! 188 TheList.swap(TestList); 189 --i; // Don't skip an element of the list 190 Changed = true; 191 } 192 if (!Error.empty()) 193 return true; 194 } 195 if (TrimIterations >= MaxTrimIterationsWithoutBackJump) 196 break; 197 TrimIterations++; 198 } 199 } 200 201 return true; // there are some failure and we've narrowed them down 202 } 203 }; 204 205 } // End llvm namespace 206 207 #endif 208
