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
|
//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===//
//
// 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 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 <vector>
#include <iostream>
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
};
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) = 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::vector<ElTy> empty;
switch (doTest(TheList, empty)) {
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!
std::cerr << "bugpoint ListReducer internal error: selected empty set.\n";
abort();
case NoFailure:
return false; // there is no failure with the full set of passes/funcs!
}
unsigned MidTop = TheList.size();
while (MidTop > 1) {
// Halt if the user presses ctrl-c.
if (BugpointIsInterrupted) {
std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
return true;
}
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)) {
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();
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 necessary 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
if (BugpointIsInterrupted) {
std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
return true;
}
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;
}
}
// 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
|
