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/Error.h" 19 #include "llvm/Support/raw_ostream.h" 20 #include <algorithm> 21 #include <cstdlib> 22 #include <random> 23 #include <vector> 24 25 namespace llvm { 26 27 extern bool BugpointIsInterrupted; 28 29 template <typename ElTy> 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 }; 35 36 virtual ~ListReducer() {} 37 38 /// This virtual function should be overriden by subclasses to implement the 39 /// test desired. The testcase is only required to test to see if the Kept 40 /// list still satisfies the property, but if it is going to check the prefix 41 /// anyway, it can. 42 virtual Expected<TestResult> doTest(std::vector<ElTy> &Prefix, 43 std::vector<ElTy> &Kept) = 0; 44 45 /// This function attempts to reduce the length of the specified list while 46 /// still maintaining the "test" property. This is the core of the "work" 47 /// that bugpoint does. 48 Expected<bool> reduceList(std::vector<ElTy> &TheList) { 49 std::vector<ElTy> empty; 50 std::mt19937 randomness(0x6e5ea738); // Seed the random number generator 51 Expected<TestResult> Result = doTest(TheList, empty); 52 if (Error E = Result.takeError()) 53 return std::move(E); 54 switch (*Result) { 55 case KeepPrefix: 56 if (TheList.size() == 1) // we are done, it's the base case and it fails 57 return true; 58 else 59 break; // there's definitely an error, but we need to narrow it down 60 61 case KeepSuffix: 62 // cannot be reached! 63 llvm_unreachable("bugpoint ListReducer internal error: " 64 "selected empty set."); 65 66 case NoFailure: 67 return false; // there is no failure with the full set of passes/funcs! 68 } 69 70 // Maximal number of allowed splitting iterations, 71 // before the elements are randomly shuffled. 72 const unsigned MaxIterationsWithoutProgress = 3; 73 74 // Maximal number of allowed single-element trim iterations. We add a 75 // threshold here as single-element reductions may otherwise take a 76 // very long time to complete. 77 const unsigned MaxTrimIterationsWithoutBackJump = 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 && NumOfIterationsWithoutProgress > MaxIterations) { 95 std::vector<ElTy> ShuffledList(TheList); 96 std::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness); 97 errs() << "\n\n*** Testing shuffled set...\n\n"; 98 // Check that random shuffle doesn't lose the bug 99 Expected<TestResult> Result = doTest(ShuffledList, empty); 100 // TODO: Previously, this error was ignored and we treated it as if 101 // shuffling hid the bug. This should really either be consumeError if 102 // that behaviour was sensible, or we should propagate the error. 103 assert(!Result.takeError() && "Shuffling caused internal error?"); 104 105 if (*Result == 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 infinite 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 Expected<TestResult> Result = doTest(Prefix, Suffix); 125 if (Error E = Result.takeError()) 126 return std::move(E); 127 switch (*Result) { 128 case KeepSuffix: 129 // The property still holds. We can just drop the prefix elements, and 130 // shorten the list to the "kept" elements. 131 TheList.swap(Suffix); 132 MidTop = TheList.size(); 133 // Reset progress treshold and progress counter 134 MaxIterations = MaxIterationsWithoutProgress; 135 NumOfIterationsWithoutProgress = 0; 136 break; 137 case KeepPrefix: 138 // The predicate still holds, shorten the list to the prefix elements. 139 TheList.swap(Prefix); 140 MidTop = TheList.size(); 141 // Reset progress treshold and progress counter 142 MaxIterations = MaxIterationsWithoutProgress; 143 NumOfIterationsWithoutProgress = 0; 144 break; 145 case NoFailure: 146 // Otherwise the property doesn't hold. Some of the elements we removed 147 // must be necessary to maintain the property. 148 MidTop = Mid; 149 NumOfIterationsWithoutProgress++; 150 break; 151 } 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) { 178 // Check interior elts 179 if (BugpointIsInterrupted) { 180 errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; 181 return true; 182 } 183 184 std::vector<ElTy> TestList(TheList); 185 TestList.erase(TestList.begin() + i); 186 187 Expected<TestResult> Result = doTest(EmptyList, TestList); 188 if (Error E = Result.takeError()) 189 return std::move(E); 190 if (*Result == KeepSuffix) { 191 // We can trim down the list! 192 TheList.swap(TestList); 193 --i; // Don't skip an element of the list 194 Changed = true; 195 } 196 } 197 if (TrimIterations >= MaxTrimIterationsWithoutBackJump) 198 break; 199 TrimIterations++; 200 } 201 } 202 203 return true; // there are some failure and we've narrowed them down 204 } 205 }; 206 207 } // End llvm namespace 208 209 #endif 210
