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