ListReducer.h revision 126840f49e8d49156a342e836d4b2adca46dc3ba
1//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===// 2// 3// This class is to be used as a base class for operations that want to zero in 4// on a subset of the input which still causes the bug we are tracking. 5// 6//===----------------------------------------------------------------------===// 7 8#ifndef BUGPOINT_LIST_REDUCER_H 9#define BUGPOINT_LIST_REDUCER_H 10 11#include <vector> 12 13template<typename ElTy> 14struct ListReducer { 15 enum TestResult { 16 NoFailure, // No failure of the predicate was detected 17 KeepSuffix, // The suffix alone satisfies the predicate 18 KeepPrefix, // The prefix alone satisfies the predicate 19 }; 20 21 // doTest - This virtual function should be overriden by subclasses to 22 // implement the test desired. The testcase is only required to test to see 23 // if the Kept list still satisfies the property, but if it is going to check 24 // the prefix anyway, it can. 25 // 26 virtual TestResult doTest(const std::vector<ElTy> &Prefix, 27 const std::vector<ElTy> &Kept) = 0; 28 29 // reduceList - This function attempts to reduce the length of the specified 30 // list while still maintaining the "test" property. This is the core of the 31 // "work" that bugpoint does. 32 // 33 void reduceList(std::vector<ElTy> &TheList) { 34 unsigned MidTop = TheList.size(); 35 while (MidTop > 1) { 36 unsigned Mid = MidTop / 2; 37 std::vector<ElTy> Prefix(TheList.begin()+Mid, TheList.end()); 38 std::vector<ElTy> Kept (TheList.begin(), TheList.begin()+Mid); 39 40 switch (doTest(Prefix, Kept)) { 41 case KeepSuffix: 42 // The property still holds. We can just drop the prefix elements, and 43 // shorten the list to the "kept" elements. 44 TheList.swap(Kept); 45 MidTop = TheList.size(); 46 break; 47 case KeepPrefix: 48 // The predicate still holds, shorten the list to the prefix elements. 49 TheList.swap(Prefix); 50 MidTop = TheList.size(); 51 break; 52 case NoFailure: 53 // Otherwise the property doesn't hold. Some of the elements we removed 54 // must be neccesary to maintain the property. 55 MidTop = Mid; 56 break; 57 } 58 } 59 60 // Okay, we trimmed as much off the top and the bottom of the list as we 61 // could. If there is more two elements in the list, try deleting interior 62 // elements and testing that. 63 // 64 if (TheList.size() > 2) { 65 bool Changed = true; 66 std::vector<ElTy> EmptyList; 67 while (Changed) { 68 Changed = false; 69 std::vector<ElTy> TrimmedList; 70 for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts 71 std::vector<ElTy> TestList(TheList); 72 TestList.erase(TestList.begin()+i); 73 74 if (doTest(EmptyList, TestList) == KeepSuffix) { 75 // We can trim down the list! 76 TheList.swap(TestList); 77 --i; // Don't skip an element of the list 78 Changed = true; 79 } 80 } 81 } 82 } 83 } 84}; 85 86#endif 87