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