1//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This class is to be used as a base class for operations that want to zero in
10// on a subset of the input which still causes the bug we are tracking.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
15#define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H
16
17#include "llvm/Support/Error.h"
18#include "llvm/Support/raw_ostream.h"
19#include <algorithm>
20#include <cstdlib>
21#include <random>
22#include <vector>
23
24namespace llvm {
25
26extern bool BugpointIsInterrupted;
27
28template <typename ElTy> struct ListReducer {
29 enum TestResult {
30 NoFailure, // No failure of the predicate was detected
31 KeepSuffix, // The suffix alone satisfies the predicate
32 KeepPrefix // The prefix alone satisfies the predicate
33 };
34
35 virtual ~ListReducer() {}
36
37 /// This virtual function should be overriden by subclasses to implement the
38 /// test desired. The testcase is only required to test to see if the Kept
39 /// list still satisfies the property, but if it is going to check the prefix
40 /// anyway, it can.
41 virtual Expected<TestResult> doTest(std::vector<ElTy> &Prefix,
42 std::vector<ElTy> &Kept) = 0;
43
44 /// This function attempts to reduce the length of the specified list while
45 /// still maintaining the "test" property. This is the core of the "work"
46 /// that bugpoint does.
47 Expected<bool> reduceList(std::vector<ElTy> &TheList) {
48 std::vector<ElTy> empty;
49 std::mt19937 randomness(0x6e5ea738); // Seed the random number generator
50 Expected<TestResult> Result = doTest(Prefix&: TheList, Kept&: empty);
51 if (Error E = Result.takeError())
52 return std::move(E);
53 switch (*Result) {
54 case KeepPrefix:
55 if (TheList.size() == 1) // we are done, it's the base case and it fails
56 return true;
57 else
58 break; // there's definitely an error, but we need to narrow it down
59
60 case KeepSuffix:
61 // cannot be reached!
62 llvm_unreachable("bugpoint ListReducer internal error: "
63 "selected empty set.");
64
65 case NoFailure:
66 return false; // there is no failure with the full set of passes/funcs!
67 }
68
69 // Maximal number of allowed splitting iterations,
70 // before the elements are randomly shuffled.
71 const unsigned MaxIterationsWithoutProgress = 3;
72
73 // Maximal number of allowed single-element trim iterations. We add a
74 // threshold here as single-element reductions may otherwise take a
75 // very long time to complete.
76 const unsigned MaxTrimIterationsWithoutBackJump = 3;
77 bool ShufflingEnabled = true;
78
79 Backjump:
80 unsigned MidTop = TheList.size();
81 unsigned MaxIterations = MaxIterationsWithoutProgress;
82 unsigned NumOfIterationsWithoutProgress = 0;
83 while (MidTop > 1) { // Binary split reduction loop
84 // Halt if the user presses ctrl-c.
85 if (BugpointIsInterrupted) {
86 errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
87 return true;
88 }
89
90 // If the loop doesn't make satisfying progress, try shuffling.
91 // The purpose of shuffling is to avoid the heavy tails of the
92 // distribution (improving the speed of convergence).
93 if (ShufflingEnabled && NumOfIterationsWithoutProgress > MaxIterations) {
94 std::vector<ElTy> ShuffledList(TheList);
95 llvm::shuffle(ShuffledList.begin(), ShuffledList.end(), randomness);
96 errs() << "\n\n*** Testing shuffled set...\n\n";
97 // Check that random shuffle doesn't lose the bug
98 Expected<TestResult> Result = doTest(Prefix&: ShuffledList, Kept&: empty);
99 // TODO: Previously, this error was ignored and we treated it as if
100 // shuffling hid the bug. This should really either be consumeError if
101 // that behaviour was sensible, or we should propagate the error.
102 assert(!Result.takeError() && "Shuffling caused internal error?");
103
104 if (*Result == KeepPrefix) {
105 // If the bug is still here, use the shuffled list.
106 TheList.swap(ShuffledList);
107 MidTop = TheList.size();
108 // Must increase the shuffling treshold to avoid the small
109 // probability of infinite looping without making progress.
110 MaxIterations += 2;
111 errs() << "\n\n*** Shuffling does not hide the bug...\n\n";
112 } else {
113 ShufflingEnabled = false; // Disable shuffling further on
114 errs() << "\n\n*** Shuffling hides the bug...\n\n";
115 }
116 NumOfIterationsWithoutProgress = 0;
117 }
118
119 unsigned Mid = MidTop / 2;
120 std::vector<ElTy> Prefix(TheList.begin(), TheList.begin() + Mid);
121 std::vector<ElTy> Suffix(TheList.begin() + Mid, TheList.end());
122
123 Expected<TestResult> Result = doTest(Prefix, Kept&: Suffix);
124 if (Error E = Result.takeError())
125 return std::move(E);
126 switch (*Result) {
127 case KeepSuffix:
128 // The property still holds. We can just drop the prefix elements, and
129 // shorten the list to the "kept" elements.
130 TheList.swap(Suffix);
131 MidTop = TheList.size();
132 // Reset progress treshold and progress counter
133 MaxIterations = MaxIterationsWithoutProgress;
134 NumOfIterationsWithoutProgress = 0;
135 break;
136 case KeepPrefix:
137 // The predicate still holds, shorten the list to the prefix elements.
138 TheList.swap(Prefix);
139 MidTop = TheList.size();
140 // Reset progress treshold and progress counter
141 MaxIterations = MaxIterationsWithoutProgress;
142 NumOfIterationsWithoutProgress = 0;
143 break;
144 case NoFailure:
145 // Otherwise the property doesn't hold. Some of the elements we removed
146 // must be necessary to maintain the property.
147 MidTop = Mid;
148 NumOfIterationsWithoutProgress++;
149 break;
150 }
151 }
152
153 // Probability of backjumping from the trimming loop back to the binary
154 // split reduction loop.
155 const int BackjumpProbability = 10;
156
157 // Okay, we trimmed as much off the top and the bottom of the list as we
158 // could. If there is more than two elements in the list, try deleting
159 // interior elements and testing that.
160 //
161 if (TheList.size() > 2) {
162 bool Changed = true;
163 std::vector<ElTy> EmptyList;
164 unsigned TrimIterations = 0;
165 while (Changed) { // Trimming loop.
166 Changed = false;
167
168 // If the binary split reduction loop made an unfortunate sequence of
169 // splits, the trimming loop might be left off with a huge number of
170 // remaining elements (large search space). Backjumping out of that
171 // search space and attempting a different split can significantly
172 // improve the convergence speed.
173 if (std::rand() % 100 < BackjumpProbability)
174 goto Backjump;
175
176 for (unsigned i = 1; i < TheList.size() - 1; ++i) {
177 // Check interior elts
178 if (BugpointIsInterrupted) {
179 errs() << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
180 return true;
181 }
182
183 std::vector<ElTy> TestList(TheList);
184 TestList.erase(TestList.begin() + i);
185
186 Expected<TestResult> Result = doTest(Prefix&: EmptyList, Kept&: TestList);
187 if (Error E = Result.takeError())
188 return std::move(E);
189 if (*Result == KeepSuffix) {
190 // We can trim down the list!
191 TheList.swap(TestList);
192 --i; // Don't skip an element of the list
193 Changed = true;
194 }
195 }
196 if (TrimIterations >= MaxTrimIterationsWithoutBackJump)
197 break;
198 TrimIterations++;
199 }
200 }
201
202 return true; // there are some failure and we've narrowed them down
203 }
204};
205
206} // End llvm namespace
207
208#endif
209