1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This class is to be used as a base class for operations that want to zero in
// on a subset of the input which still causes the bug we are tracking.
//
//===----------------------------------------------------------------------===//
#ifndef BUGPOINT_LIST_REDUCER_H
#define BUGPOINT_LIST_REDUCER_H
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/ErrorHandling.h"
#include <vector>
#include <cstdlib>
#include <algorithm>
namespace llvm {
extern bool BugpointIsInterrupted;
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
InternalError // Encountered an error trying to run the predicate
};
virtual ~ListReducer() {}
// 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(std::vector<ElTy> &Prefix,
std::vector<ElTy> &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<ElTy> &TheList, std::string &Error) {
std::vector<ElTy> 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;
else
break; // there's definitely an error, but we need to narrow it down
case KeepSuffix:
// cannot be reached!
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();
unsigned MaxIterations = MaxIterationsWithoutProgress;
unsigned NumOfIterationsWithoutProgress = 0;
while (MidTop > 1) { // Binary split reduction loop
// Halt if the user presses ctrl-c.
if (BugpointIsInterrupted) {
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<ElTy> 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<ElTy> Prefix(TheList.begin(), TheList.begin()+Mid);
std::vector<ElTy> Suffix(TheList.begin()+Mid, TheList.end());
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.
//
if (TheList.size() > 2) {
bool Changed = true;
std::vector<ElTy> EmptyList;
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) {
errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
return true;
}
std::vector<ElTy> TestList(TheList);
TestList.erase(TestList.begin()+i);
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.
break;
}
}
return true; // there are some failure and we've narrowed them down
}
};
} // End llvm namespace
#endif
|
