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