Move the ListReducer Class into it's own header file instead of living in Miscompilation.cpp
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5907 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/tools/bugpoint/Miscompilation.cpp b/tools/bugpoint/Miscompilation.cpp
index 4960b82..89854f5 100644
--- a/tools/bugpoint/Miscompilation.cpp
+++ b/tools/bugpoint/Miscompilation.cpp
@@ -6,6 +6,7 @@
#include "BugDriver.h"
#include "SystemUtils.h"
+#include "ListReducer.h"
#include "llvm/Pass.h"
#include "llvm/Module.h"
#include "llvm/Transforms/Utils/Cloning.h"
@@ -26,79 +27,6 @@
"(for miscompilation detection)"));
}
-template<typename ElTy>
-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
- };
-
- // doTest - This virtual function should be overriden by subclasses to
- // implement the test desired. The testcase is only required to test to see
- // if the Kept list still satisfies the property, but if it is going to check
- // the prefix anyway, it can.
- //
- virtual TestResult doTest(const std::vector<ElTy> &Prefix,
- const std::vector<ElTy> &Kept) = 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.
- //
- void reduceList(std::vector<ElTy> &TheList) {
- unsigned MidTop = TheList.size();
- while (MidTop > 1) {
- unsigned Mid = MidTop / 2;
- std::vector<ElTy> Prefix(TheList.begin()+Mid, TheList.end());
- std::vector<ElTy> Kept (TheList.begin(), TheList.begin()+Mid);
-
- switch (doTest(Prefix, Kept)) {
- case KeepSuffix:
- // The property still holds. We can just drop the prefix elements, and
- // shorten the list to the "kept" elements.
- TheList.swap(Kept);
- MidTop = TheList.size();
- break;
- case KeepPrefix:
- // The predicate still holds, shorten the list to the prefix elements.
- TheList.swap(Prefix);
- MidTop = TheList.size();
- break;
- case NoFailure:
- // Otherwise the property doesn't hold. Some of the elements we removed
- // must be neccesary to maintain the property.
- MidTop = Mid;
- break;
- }
- }
-
- // Okay, we trimmed as much off the top and the bottom of the list as we
- // could. If there is more two elements in the list, try deleting interior
- // elements and testing that.
- //
- if (TheList.size() > 2) {
- bool Changed = true;
- std::vector<ElTy> EmptyList;
- while (Changed) {
- Changed = false;
- std::vector<ElTy> TrimmedList;
- for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts
- std::vector<ElTy> TestList(TheList);
- TestList.erase(TestList.begin()+i);
-
- if (doTest(EmptyList, TestList) == KeepSuffix) {
- // We can trim down the list!
- TheList.swap(TestList);
- --i; // Don't skip an element of the list
- Changed = true;
- }
- }
- }
- }
- }
-};
-
class ReduceMiscompilingPasses : public ListReducer<const PassInfo*> {
BugDriver &BD;
public: