X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=tools%2Fbugpoint%2FListReducer.h;h=a0bb570a5cb28123d1f63745bae32894e0e8da00;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=784c2f8bde471f77891f5afe85d4ff3942962e1b;hpb=54e4c02d8e7ca49b89a1f39824a7617920dd43f0;p=oota-llvm.git diff --git a/tools/bugpoint/ListReducer.h b/tools/bugpoint/ListReducer.h index 784c2f8bde4..a0bb570a5cb 100644 --- a/tools/bugpoint/ListReducer.h +++ b/tools/bugpoint/ListReducer.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -12,11 +12,14 @@ // //===----------------------------------------------------------------------===// -#ifndef BUGPOINT_LIST_REDUCER_H -#define BUGPOINT_LIST_REDUCER_H +#ifndef LLVM_TOOLS_BUGPOINT_LISTREDUCER_H +#define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" +#include +#include #include -#include namespace llvm { @@ -27,7 +30,8 @@ struct ListReducer { enum TestResult { NoFailure, // No failure of the predicate was detected KeepSuffix, // The suffix alone satisfies the predicate - KeepPrefix // The prefix alone satisfies the predicate + KeepPrefix, // The prefix alone satisfies the predicate + InternalError // Encountered an error trying to run the predicate }; virtual ~ListReducer() {} @@ -38,15 +42,17 @@ struct ListReducer { // the prefix anyway, it can. // virtual TestResult doTest(std::vector &Prefix, - std::vector &Kept) = 0; + std::vector &Kept, + std::string &Error) = 0; // reduceList - This function attempts to reduce the length of the specified // list while still maintaining the "test" property. This is the core of the // "work" that bugpoint does. // - bool reduceList(std::vector &TheList) { + bool reduceList(std::vector &TheList, std::string &Error) { std::vector empty; - switch (doTest(TheList, empty)) { + std::srand(0x6e5ea738); // Seed the random number generator + switch (doTest(TheList, empty, Error)) { case KeepPrefix: if (TheList.size() == 1) // we are done, it's the base case and it fails return true; @@ -55,45 +61,95 @@ struct ListReducer { case KeepSuffix: // cannot be reached! - std::cerr << "bugpoint ListReducer internal error: selected empty set.\n"; - abort(); + llvm_unreachable("bugpoint ListReducer internal error: " + "selected empty set."); case NoFailure: return false; // there is no failure with the full set of passes/funcs! + + case InternalError: + assert(!Error.empty()); + return true; } + // Maximal number of allowed splitting iterations, + // before the elements are randomly shuffled. + const unsigned MaxIterationsWithoutProgress = 3; + bool ShufflingEnabled = true; + +Backjump: unsigned MidTop = TheList.size(); - while (MidTop > 1) { + unsigned MaxIterations = MaxIterationsWithoutProgress; + unsigned NumOfIterationsWithoutProgress = 0; + while (MidTop > 1) { // Binary split reduction loop // Halt if the user presses ctrl-c. if (BugpointIsInterrupted) { - std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; + errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; return true; } + + // If the loop doesn't make satisfying progress, try shuffling. + // The purpose of shuffling is to avoid the heavy tails of the + // distribution (improving the speed of convergence). + if (ShufflingEnabled && + NumOfIterationsWithoutProgress > MaxIterations) { + std::vector ShuffledList(TheList); + std::random_shuffle(ShuffledList.begin(), ShuffledList.end()); + errs() << "\n\n*** Testing shuffled set...\n\n"; + // Check that random shuffle doesn't loose the bug + if (doTest(ShuffledList, empty, Error) == KeepPrefix) { + // If the bug is still here, use the shuffled list. + TheList.swap(ShuffledList); + MidTop = TheList.size(); + // Must increase the shuffling treshold to avoid the small + // probability of inifinite looping without making progress. + MaxIterations += 2; + errs() << "\n\n*** Shuffling does not hide the bug...\n\n"; + } else { + ShufflingEnabled = false; // Disable shuffling further on + errs() << "\n\n*** Shuffling hides the bug...\n\n"; + } + NumOfIterationsWithoutProgress = 0; + } unsigned Mid = MidTop / 2; std::vector Prefix(TheList.begin(), TheList.begin()+Mid); std::vector Suffix(TheList.begin()+Mid, TheList.end()); - switch (doTest(Prefix, Suffix)) { + switch (doTest(Prefix, Suffix, Error)) { case KeepSuffix: // The property still holds. We can just drop the prefix elements, and // shorten the list to the "kept" elements. TheList.swap(Suffix); MidTop = TheList.size(); + // Reset progress treshold and progress counter + MaxIterations = MaxIterationsWithoutProgress; + NumOfIterationsWithoutProgress = 0; break; case KeepPrefix: // The predicate still holds, shorten the list to the prefix elements. TheList.swap(Prefix); MidTop = TheList.size(); + // Reset progress treshold and progress counter + MaxIterations = MaxIterationsWithoutProgress; + NumOfIterationsWithoutProgress = 0; break; case NoFailure: // Otherwise the property doesn't hold. Some of the elements we removed // must be necessary to maintain the property. MidTop = Mid; + NumOfIterationsWithoutProgress++; break; + case InternalError: + return true; // Error was set by doTest. } + assert(Error.empty() && "doTest did not return InternalError for error"); } + // Probability of backjumping from the trimming loop back to the binary + // split reduction loop. + const int BackjumpProbability = 10; + // Okay, we trimmed as much off the top and the bottom of the list as we // could. If there is more than two elements in the list, try deleting // interior elements and testing that. @@ -101,23 +157,34 @@ struct ListReducer { if (TheList.size() > 2) { bool Changed = true; std::vector EmptyList; - while (Changed) { + while (Changed) { // Trimming loop. Changed = false; + + // If the binary split reduction loop made an unfortunate sequence of + // splits, the trimming loop might be left off with a huge number of + // remaining elements (large search space). Backjumping out of that + // search space and attempting a different split can significantly + // improve the convergence speed. + if (std::rand() % 100 < BackjumpProbability) + goto Backjump; + for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts if (BugpointIsInterrupted) { - std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; + errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; return true; } std::vector TestList(TheList); TestList.erase(TestList.begin()+i); - if (doTest(EmptyList, TestList) == KeepSuffix) { + if (doTest(EmptyList, TestList, Error) == KeepSuffix) { // We can trim down the list! TheList.swap(TestList); --i; // Don't skip an element of the list Changed = true; } + if (!Error.empty()) + return true; } // This can take a long time if left uncontrolled. For now, don't // iterate.