ListReducer.h revision 54e4c02d8e7ca49b89a1f39824a7617920dd43f0 
1//===- ListReducer.h - Trim down list while retaining property --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source 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
21namespace llvm {
22
23  extern bool BugpointIsInterrupted;
24
25template<typename ElTy>
26struct ListReducer {
27  enum TestResult {
28    NoFailure,         // No failure of the predicate was detected
29    KeepSuffix,        // The suffix alone satisfies the predicate
30    KeepPrefix         // The prefix alone satisfies the predicate
31  };
32
33  virtual ~ListReducer() {}
34
35  // doTest - This virtual function should be overriden by subclasses to
36  // implement the test desired.  The testcase is only required to test to see
37  // if the Kept list still satisfies the property, but if it is going to check
38  // the prefix anyway, it can.
39  //
40  virtual TestResult doTest(std::vector<ElTy> &Prefix,
41                            std::vector<ElTy> &Kept) = 0;
42
43  // reduceList - This function attempts to reduce the length of the specified
44  // list while still maintaining the "test" property.  This is the core of the
45  // "work" that bugpoint does.
46  //
47  bool reduceList(std::vector<ElTy> &TheList) {
48    std::vector<ElTy> empty;
49    switch (doTest(TheList, empty)) {
50    case KeepPrefix:
51      if (TheList.size() == 1) // we are done, it's the base case and it fails
52        return true;
53      else
54        break; // there's definitely an error, but we need to narrow it down
55
56    case KeepSuffix:
57      // cannot be reached!
58      std::cerr << "bugpoint ListReducer internal error: selected empty set.\n";
59      abort();
60
61    case NoFailure:
62      return false; // there is no failure with the full set of passes/funcs!
63    }
64
65    unsigned MidTop = TheList.size();
66    while (MidTop > 1) {
67      // Halt if the user presses ctrl-c.
68      if (BugpointIsInterrupted) {
69        std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
70        return true;
71      }
72
73      unsigned Mid = MidTop / 2;
74      std::vector<ElTy> Prefix(TheList.begin(), TheList.begin()+Mid);
75      std::vector<ElTy> Suffix(TheList.begin()+Mid, TheList.end());
76
77      switch (doTest(Prefix, Suffix)) {
78      case KeepSuffix:
79        // The property still holds.  We can just drop the prefix elements, and
80        // shorten the list to the "kept" elements.
81        TheList.swap(Suffix);
82        MidTop = TheList.size();
83        break;
84      case KeepPrefix:
85        // The predicate still holds, shorten the list to the prefix elements.
86        TheList.swap(Prefix);
87        MidTop = TheList.size();
88        break;
89      case NoFailure:
90        // Otherwise the property doesn't hold.  Some of the elements we removed
91        // must be necessary to maintain the property.
92        MidTop = Mid;
93        break;
94      }
95    }
96
97    // Okay, we trimmed as much off the top and the bottom of the list as we
98    // could.  If there is more than two elements in the list, try deleting
99    // interior elements and testing that.
100    //
101    if (TheList.size() > 2) {
102      bool Changed = true;
103      std::vector<ElTy> EmptyList;
104      while (Changed) {
105        Changed = false;
106        for (unsigned i = 1; i < TheList.size()-1; ++i) { // Check interior elts
107          if (BugpointIsInterrupted) {
108            std::cerr << "\n\n*** Reduction Interrupted, cleaning up...\n\n";
109            return true;
110          }
111
112          std::vector<ElTy> TestList(TheList);
113          TestList.erase(TestList.begin()+i);
114
115          if (doTest(EmptyList, TestList) == KeepSuffix) {
116            // We can trim down the list!
117            TheList.swap(TestList);
118            --i;  // Don't skip an element of the list
119            Changed = true;
120          }
121        }
122        // This can take a long time if left uncontrolled.  For now, don't
123        // iterate.
124        break;
125      }
126    }
127
128    return true; // there are some failure and we've narrowed them down
129  }
130};
131
132} // End llvm namespace
133
134#endif
135