]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | ||
1a4d82fc JJ |
15 | #ifndef LLVM_TOOLS_BUGPOINT_LISTREDUCER_H |
16 | #define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H | |
223e47cc | 17 | |
223e47cc | 18 | #include "llvm/Support/ErrorHandling.h" |
970d7e83 | 19 | #include "llvm/Support/raw_ostream.h" |
223e47cc | 20 | #include <algorithm> |
970d7e83 LB |
21 | #include <cstdlib> |
22 | #include <vector> | |
223e47cc LB |
23 | |
24 | namespace llvm { | |
25 | ||
26 | extern bool BugpointIsInterrupted; | |
27 | ||
28 | template<typename ElTy> | |
29 | 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 | InternalError // Encountered an error trying to run the predicate | |
35 | }; | |
36 | ||
37 | virtual ~ListReducer() {} | |
38 | ||
39 | // doTest - This virtual function should be overriden by subclasses to | |
40 | // implement the test desired. The testcase is only required to test to see | |
41 | // if the Kept list still satisfies the property, but if it is going to check | |
42 | // the prefix anyway, it can. | |
43 | // | |
44 | virtual TestResult doTest(std::vector<ElTy> &Prefix, | |
45 | std::vector<ElTy> &Kept, | |
46 | std::string &Error) = 0; | |
47 | ||
48 | // reduceList - This function attempts to reduce the length of the specified | |
49 | // list while still maintaining the "test" property. This is the core of the | |
50 | // "work" that bugpoint does. | |
51 | // | |
52 | bool reduceList(std::vector<ElTy> &TheList, std::string &Error) { | |
53 | std::vector<ElTy> empty; | |
54 | std::srand(0x6e5ea738); // Seed the random number generator | |
55 | switch (doTest(TheList, empty, Error)) { | |
56 | case KeepPrefix: | |
57 | if (TheList.size() == 1) // we are done, it's the base case and it fails | |
58 | return true; | |
59 | else | |
60 | break; // there's definitely an error, but we need to narrow it down | |
61 | ||
62 | case KeepSuffix: | |
63 | // cannot be reached! | |
64 | llvm_unreachable("bugpoint ListReducer internal error: " | |
65 | "selected empty set."); | |
66 | ||
67 | case NoFailure: | |
68 | return false; // there is no failure with the full set of passes/funcs! | |
69 | ||
70 | case InternalError: | |
71 | assert(!Error.empty()); | |
72 | return true; | |
73 | } | |
74 | ||
75 | // Maximal number of allowed splitting iterations, | |
76 | // before the elements are randomly shuffled. | |
77 | const unsigned MaxIterationsWithoutProgress = 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 && | |
95 | NumOfIterationsWithoutProgress > MaxIterations) { | |
96 | std::vector<ElTy> ShuffledList(TheList); | |
97 | std::random_shuffle(ShuffledList.begin(), ShuffledList.end()); | |
98 | errs() << "\n\n*** Testing shuffled set...\n\n"; | |
99 | // Check that random shuffle doesn't loose the bug | |
100 | if (doTest(ShuffledList, empty, Error) == KeepPrefix) { | |
101 | // If the bug is still here, use the shuffled list. | |
102 | TheList.swap(ShuffledList); | |
103 | MidTop = TheList.size(); | |
104 | // Must increase the shuffling treshold to avoid the small | |
105 | // probability of inifinite looping without making progress. | |
106 | MaxIterations += 2; | |
107 | errs() << "\n\n*** Shuffling does not hide the bug...\n\n"; | |
108 | } else { | |
109 | ShufflingEnabled = false; // Disable shuffling further on | |
110 | errs() << "\n\n*** Shuffling hides the bug...\n\n"; | |
111 | } | |
112 | NumOfIterationsWithoutProgress = 0; | |
113 | } | |
114 | ||
115 | unsigned Mid = MidTop / 2; | |
116 | std::vector<ElTy> Prefix(TheList.begin(), TheList.begin()+Mid); | |
117 | std::vector<ElTy> Suffix(TheList.begin()+Mid, TheList.end()); | |
118 | ||
119 | switch (doTest(Prefix, Suffix, Error)) { | |
120 | case KeepSuffix: | |
121 | // The property still holds. We can just drop the prefix elements, and | |
122 | // shorten the list to the "kept" elements. | |
123 | TheList.swap(Suffix); | |
124 | MidTop = TheList.size(); | |
125 | // Reset progress treshold and progress counter | |
126 | MaxIterations = MaxIterationsWithoutProgress; | |
127 | NumOfIterationsWithoutProgress = 0; | |
128 | break; | |
129 | case KeepPrefix: | |
130 | // The predicate still holds, shorten the list to the prefix elements. | |
131 | TheList.swap(Prefix); | |
132 | MidTop = TheList.size(); | |
133 | // Reset progress treshold and progress counter | |
134 | MaxIterations = MaxIterationsWithoutProgress; | |
135 | NumOfIterationsWithoutProgress = 0; | |
136 | break; | |
137 | case NoFailure: | |
138 | // Otherwise the property doesn't hold. Some of the elements we removed | |
139 | // must be necessary to maintain the property. | |
140 | MidTop = Mid; | |
141 | NumOfIterationsWithoutProgress++; | |
142 | break; | |
143 | case InternalError: | |
144 | return true; // Error was set by doTest. | |
145 | } | |
146 | assert(Error.empty() && "doTest did not return InternalError for error"); | |
147 | } | |
148 | ||
149 | // Probability of backjumping from the trimming loop back to the binary | |
150 | // split reduction loop. | |
151 | const int BackjumpProbability = 10; | |
152 | ||
153 | // Okay, we trimmed as much off the top and the bottom of the list as we | |
154 | // could. If there is more than two elements in the list, try deleting | |
155 | // interior elements and testing that. | |
156 | // | |
157 | if (TheList.size() > 2) { | |
158 | bool Changed = true; | |
159 | std::vector<ElTy> EmptyList; | |
160 | while (Changed) { // Trimming loop. | |
161 | Changed = false; | |
162 | ||
163 | // If the binary split reduction loop made an unfortunate sequence of | |
164 | // splits, the trimming loop might be left off with a huge number of | |
165 | // remaining elements (large search space). Backjumping out of that | |
166 | // search space and attempting a different split can significantly | |
167 | // improve the convergence speed. | |
168 | if (std::rand() % 100 < BackjumpProbability) | |
169 | goto Backjump; | |
170 | ||
171 | for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts | |
172 | if (BugpointIsInterrupted) { | |
173 | errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n"; | |
174 | return true; | |
175 | } | |
176 | ||
177 | std::vector<ElTy> TestList(TheList); | |
178 | TestList.erase(TestList.begin()+i); | |
179 | ||
180 | if (doTest(EmptyList, TestList, Error) == KeepSuffix) { | |
181 | // We can trim down the list! | |
182 | TheList.swap(TestList); | |
183 | --i; // Don't skip an element of the list | |
184 | Changed = true; | |
185 | } | |
186 | if (!Error.empty()) | |
187 | return true; | |
188 | } | |
189 | // This can take a long time if left uncontrolled. For now, don't | |
190 | // iterate. | |
191 | break; | |
192 | } | |
193 | } | |
194 | ||
195 | return true; // there are some failure and we've narrowed them down | |
196 | } | |
197 | }; | |
198 | ||
199 | } // End llvm namespace | |
200 | ||
201 | #endif |