LLVM  6.0.0svn
DeltaAlgorithm.cpp
Go to the documentation of this file.
1 //===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- 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 
10 #include <algorithm>
11 #include <iterator>
12 #include <set>
13 using namespace llvm;
14 
16 }
17 
18 bool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) {
19  if (FailedTestsCache.count(Changes))
20  return false;
21 
22  bool Result = ExecuteOneTest(Changes);
23  if (!Result)
24  FailedTestsCache.insert(Changes);
25 
26  return Result;
27 }
28 
29 void DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) {
30  // FIXME: Allow clients to provide heuristics for improved splitting.
31 
32  // FIXME: This is really slow.
33  changeset_ty LHS, RHS;
34  unsigned idx = 0, N = S.size() / 2;
35  for (changeset_ty::const_iterator it = S.begin(),
36  ie = S.end(); it != ie; ++it, ++idx)
37  ((idx < N) ? LHS : RHS).insert(*it);
38  if (!LHS.empty())
39  Res.push_back(LHS);
40  if (!RHS.empty())
41  Res.push_back(RHS);
42 }
43 
45 DeltaAlgorithm::Delta(const changeset_ty &Changes,
46  const changesetlist_ty &Sets) {
47  // Invariant: union(Res) == Changes
48  UpdatedSearchState(Changes, Sets);
49 
50  // If there is nothing left we can remove, we are done.
51  if (Sets.size() <= 1)
52  return Changes;
53 
54  // Look for a passing subset.
55  changeset_ty Res;
56  if (Search(Changes, Sets, Res))
57  return Res;
58 
59  // Otherwise, partition the sets if possible; if not we are done.
60  changesetlist_ty SplitSets;
61  for (changesetlist_ty::const_iterator it = Sets.begin(),
62  ie = Sets.end(); it != ie; ++it)
63  Split(*it, SplitSets);
64  if (SplitSets.size() == Sets.size())
65  return Changes;
66 
67  return Delta(Changes, SplitSets);
68 }
69 
70 bool DeltaAlgorithm::Search(const changeset_ty &Changes,
71  const changesetlist_ty &Sets,
72  changeset_ty &Res) {
73  // FIXME: Parallelize.
74  for (changesetlist_ty::const_iterator it = Sets.begin(),
75  ie = Sets.end(); it != ie; ++it) {
76  // If the test passes on this subset alone, recurse.
77  if (GetTestResult(*it)) {
78  changesetlist_ty Sets;
79  Split(*it, Sets);
80  Res = Delta(*it, Sets);
81  return true;
82  }
83 
84  // Otherwise, if we have more than two sets, see if test passes on the
85  // complement.
86  if (Sets.size() > 2) {
87  // FIXME: This is really slow.
88  changeset_ty Complement;
90  Changes.begin(), Changes.end(), it->begin(), it->end(),
91  std::insert_iterator<changeset_ty>(Complement, Complement.begin()));
92  if (GetTestResult(Complement)) {
93  changesetlist_ty ComplementSets;
94  ComplementSets.insert(ComplementSets.end(), Sets.begin(), it);
95  ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());
96  Res = Delta(Complement, ComplementSets);
97  return true;
98  }
99  }
100  }
101 
102  return false;
103 }
104 
106  // Check empty set first to quickly find poor test functions.
107  if (GetTestResult(changeset_ty()))
108  return changeset_ty();
109 
110  // Otherwise run the real delta algorithm.
111  changesetlist_ty Sets;
112  Split(Changes, Sets);
113 
114  return Delta(Changes, Sets);
115 }
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
virtual void UpdatedSearchState(const changeset_ty &Changes, const changesetlist_ty &Sets)
UpdatedSearchState - Callback used when the search state changes.
std::set< change_ty > changeset_ty
S1Ty set_difference(const S1Ty &S1, const S2Ty &S2)
set_difference(A, B) - Return A - B
Definition: SetOperations.h:51
changeset_ty Run(const changeset_ty &Changes)
Run - Minimize the set Changes by executing.
std::vector< changeset_ty > changesetlist_ty
virtual bool ExecuteOneTest(const changeset_ty &S)=0
ExecuteOneTest - Execute a single test predicate on the change set S.
#define N