1193323Sed//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This class is to be used as a base class for operations that want to zero in 11193323Sed// on a subset of the input which still causes the bug we are tracking. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#ifndef BUGPOINT_LIST_REDUCER_H 16193323Sed#define BUGPOINT_LIST_REDUCER_H 17193323Sed 18249423Sdim#include "llvm/Support/ErrorHandling.h" 19198090Srdivacky#include "llvm/Support/raw_ostream.h" 20249423Sdim#include <algorithm> 21249423Sdim#include <cstdlib> 22193323Sed#include <vector> 23193323Sed 24193323Sednamespace llvm { 25193323Sed 26193323Sed extern bool BugpointIsInterrupted; 27193323Sed 28193323Sedtemplate<typename ElTy> 29193323Sedstruct ListReducer { 30193323Sed enum TestResult { 31193323Sed NoFailure, // No failure of the predicate was detected 32193323Sed KeepSuffix, // The suffix alone satisfies the predicate 33207618Srdivacky KeepPrefix, // The prefix alone satisfies the predicate 34207618Srdivacky InternalError // Encountered an error trying to run the predicate 35193323Sed }; 36193323Sed 37193323Sed virtual ~ListReducer() {} 38193323Sed 39193323Sed // doTest - This virtual function should be overriden by subclasses to 40193323Sed // implement the test desired. The testcase is only required to test to see 41193323Sed // if the Kept list still satisfies the property, but if it is going to check 42193323Sed // the prefix anyway, it can. 43193323Sed // 44193323Sed virtual TestResult doTest(std::vector<ElTy> &Prefix, 45207618Srdivacky std::vector<ElTy> &Kept, 46207618Srdivacky std::string &Error) = 0; 47193323Sed 48193323Sed // reduceList - This function attempts to reduce the length of the specified 49193323Sed // list while still maintaining the "test" property. This is the core of the 50193323Sed // "work" that bugpoint does. 51193323Sed // 52207618Srdivacky bool reduceList(std::vector<ElTy> &TheList, std::string &Error) { 53193323Sed std::vector<ElTy> empty; 54193323Sed std::srand(0x6e5ea738); // Seed the random number generator 55207618Srdivacky switch (doTest(TheList, empty, Error)) { 56193323Sed case KeepPrefix: 57193323Sed if (TheList.size() == 1) // we are done, it's the base case and it fails 58193323Sed return true; 59193323Sed else 60193323Sed break; // there's definitely an error, but we need to narrow it down 61193323Sed 62193323Sed case KeepSuffix: 63193323Sed // cannot be reached! 64207618Srdivacky llvm_unreachable("bugpoint ListReducer internal error: " 65207618Srdivacky "selected empty set."); 66193323Sed 67193323Sed case NoFailure: 68193323Sed return false; // there is no failure with the full set of passes/funcs! 69207618Srdivacky 70207618Srdivacky case InternalError: 71207618Srdivacky assert(!Error.empty()); 72207618Srdivacky return true; 73193323Sed } 74193323Sed 75193323Sed // Maximal number of allowed splitting iterations, 76193323Sed // before the elements are randomly shuffled. 77193323Sed const unsigned MaxIterationsWithoutProgress = 3; 78193323Sed bool ShufflingEnabled = true; 79193323Sed 80193323SedBackjump: 81193323Sed unsigned MidTop = TheList.size(); 82193323Sed unsigned MaxIterations = MaxIterationsWithoutProgress; 83193323Sed unsigned NumOfIterationsWithoutProgress = 0; 84193323Sed while (MidTop > 1) { // Binary split reduction loop 85193323Sed // Halt if the user presses ctrl-c. 86193323Sed if (BugpointIsInterrupted) { 87198090Srdivacky errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; 88193323Sed return true; 89193323Sed } 90193323Sed 91193323Sed // If the loop doesn't make satisfying progress, try shuffling. 92193323Sed // The purpose of shuffling is to avoid the heavy tails of the 93193323Sed // distribution (improving the speed of convergence). 94193323Sed if (ShufflingEnabled && 95193323Sed NumOfIterationsWithoutProgress > MaxIterations) { 96193323Sed std::vector<ElTy> ShuffledList(TheList); 97193323Sed std::random_shuffle(ShuffledList.begin(), ShuffledList.end()); 98198090Srdivacky errs() << "\n\n*** Testing shuffled set...\n\n"; 99193323Sed // Check that random shuffle doesn't loose the bug 100207618Srdivacky if (doTest(ShuffledList, empty, Error) == KeepPrefix) { 101193323Sed // If the bug is still here, use the shuffled list. 102193323Sed TheList.swap(ShuffledList); 103193323Sed MidTop = TheList.size(); 104193323Sed // Must increase the shuffling treshold to avoid the small 105193323Sed // probability of inifinite looping without making progress. 106193323Sed MaxIterations += 2; 107198090Srdivacky errs() << "\n\n*** Shuffling does not hide the bug...\n\n"; 108193323Sed } else { 109193323Sed ShufflingEnabled = false; // Disable shuffling further on 110198090Srdivacky errs() << "\n\n*** Shuffling hides the bug...\n\n"; 111193323Sed } 112193323Sed NumOfIterationsWithoutProgress = 0; 113193323Sed } 114193323Sed 115193323Sed unsigned Mid = MidTop / 2; 116193323Sed std::vector<ElTy> Prefix(TheList.begin(), TheList.begin()+Mid); 117193323Sed std::vector<ElTy> Suffix(TheList.begin()+Mid, TheList.end()); 118193323Sed 119207618Srdivacky switch (doTest(Prefix, Suffix, Error)) { 120193323Sed case KeepSuffix: 121193323Sed // The property still holds. We can just drop the prefix elements, and 122193323Sed // shorten the list to the "kept" elements. 123193323Sed TheList.swap(Suffix); 124193323Sed MidTop = TheList.size(); 125193323Sed // Reset progress treshold and progress counter 126193323Sed MaxIterations = MaxIterationsWithoutProgress; 127193323Sed NumOfIterationsWithoutProgress = 0; 128193323Sed break; 129193323Sed case KeepPrefix: 130193323Sed // The predicate still holds, shorten the list to the prefix elements. 131193323Sed TheList.swap(Prefix); 132193323Sed MidTop = TheList.size(); 133193323Sed // Reset progress treshold and progress counter 134193323Sed MaxIterations = MaxIterationsWithoutProgress; 135193323Sed NumOfIterationsWithoutProgress = 0; 136193323Sed break; 137193323Sed case NoFailure: 138193323Sed // Otherwise the property doesn't hold. Some of the elements we removed 139193323Sed // must be necessary to maintain the property. 140193323Sed MidTop = Mid; 141193323Sed NumOfIterationsWithoutProgress++; 142193323Sed break; 143207618Srdivacky case InternalError: 144207618Srdivacky return true; // Error was set by doTest. 145193323Sed } 146207618Srdivacky assert(Error.empty() && "doTest did not return InternalError for error"); 147193323Sed } 148193323Sed 149193323Sed // Probability of backjumping from the trimming loop back to the binary 150193323Sed // split reduction loop. 151193323Sed const int BackjumpProbability = 10; 152193323Sed 153193323Sed // Okay, we trimmed as much off the top and the bottom of the list as we 154193323Sed // could. If there is more than two elements in the list, try deleting 155193323Sed // interior elements and testing that. 156193323Sed // 157193323Sed if (TheList.size() > 2) { 158193323Sed bool Changed = true; 159193323Sed std::vector<ElTy> EmptyList; 160193323Sed while (Changed) { // Trimming loop. 161193323Sed Changed = false; 162193323Sed 163193323Sed // If the binary split reduction loop made an unfortunate sequence of 164193323Sed // splits, the trimming loop might be left off with a huge number of 165193323Sed // remaining elements (large search space). Backjumping out of that 166193323Sed // search space and attempting a different split can significantly 167193323Sed // improve the convergence speed. 168193323Sed if (std::rand() % 100 < BackjumpProbability) 169193323Sed goto Backjump; 170193323Sed 171193323Sed for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts 172193323Sed if (BugpointIsInterrupted) { 173198090Srdivacky errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; 174193323Sed return true; 175193323Sed } 176193323Sed 177193323Sed std::vector<ElTy> TestList(TheList); 178193323Sed TestList.erase(TestList.begin()+i); 179193323Sed 180207618Srdivacky if (doTest(EmptyList, TestList, Error) == KeepSuffix) { 181193323Sed // We can trim down the list! 182193323Sed TheList.swap(TestList); 183193323Sed --i; // Don't skip an element of the list 184193323Sed Changed = true; 185193323Sed } 186210006Srdivacky if (!Error.empty()) 187210006Srdivacky return true; 188193323Sed } 189193323Sed // This can take a long time if left uncontrolled. For now, don't 190193323Sed // iterate. 191193323Sed break; 192193323Sed } 193193323Sed } 194193323Sed 195193323Sed return true; // there are some failure and we've narrowed them down 196193323Sed } 197193323Sed}; 198193323Sed 199193323Sed} // End llvm namespace 200193323Sed 201193323Sed#endif 202