209 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This class is to be used as a base class for operations that want to zero in10// on a subset of the input which still causes the bug we are tracking.11//12//===----------------------------------------------------------------------===//13 14#ifndef LLVM_TOOLS_BUGPOINT_LISTREDUCER_H15#define LLVM_TOOLS_BUGPOINT_LISTREDUCER_H16 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 detected31 KeepSuffix, // The suffix alone satisfies the predicate32 KeepPrefix // The prefix alone satisfies the predicate33 };34 35 virtual ~ListReducer() = default;36 37 /// This virtual function should be overriden by subclasses to implement the38 /// test desired. The testcase is only required to test to see if the Kept39 /// list still satisfies the property, but if it is going to check the prefix40 /// 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 while45 /// 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 generator50 Expected<TestResult> Result = doTest(TheList, 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 fails56 return true;57 else58 break; // there's definitely an error, but we need to narrow it down59 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 a74 // threshold here as single-element reductions may otherwise take a75 // 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 loop84 // 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 the92 // 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 bug98 Expected<TestResult> Result = doTest(ShuffledList, empty);99 // TODO: Previously, this error was ignored and we treated it as if100 // shuffling hid the bug. This should really either be consumeError if101 // 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 small109 // 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 on114 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, 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, and129 // shorten the list to the "kept" elements.130 TheList.swap(Suffix);131 MidTop = TheList.size();132 // Reset progress treshold and progress counter133 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 counter141 MaxIterations = MaxIterationsWithoutProgress;142 NumOfIterationsWithoutProgress = 0;143 break;144 case NoFailure:145 // Otherwise the property doesn't hold. Some of the elements we removed146 // 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 binary154 // 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 we158 // could. If there is more than two elements in the list, try deleting159 // 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 of169 // splits, the trimming loop might be left off with a huge number of170 // remaining elements (large search space). Backjumping out of that171 // search space and attempting a different split can significantly172 // 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 elts178 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(EmptyList, 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 list193 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 down203 }204};205 206} // End llvm namespace207 208#endif209