LLVM  14.0.0git
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 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::DeltaAlgorithm::UpdatedSearchState
virtual void UpdatedSearchState(const changeset_ty &Changes, const changesetlist_ty &Sets)
UpdatedSearchState - Callback used when the search state changes.
Definition: DeltaAlgorithm.h:73
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
DeltaAlgorithm.h
llvm::DeltaAlgorithm::ExecuteOneTest
virtual bool ExecuteOneTest(const changeset_ty &S)=0
ExecuteOneTest - Execute a single test predicate on the change set S.
llvm::DeltaAlgorithm::~DeltaAlgorithm
virtual ~DeltaAlgorithm()
Definition: DeltaAlgorithm.cpp:14
llvm::DeltaAlgorithm::changesetlist_ty
std::vector< changeset_ty > changesetlist_ty
Definition: DeltaAlgorithm.h:40
llvm::DeltaAlgorithm::Run
changeset_ty Run(const changeset_ty &Changes)
Run - Minimize the set Changes by executing.
Definition: DeltaAlgorithm.cpp:104
llvm::DeltaAlgorithm::changeset_ty
std::set< change_ty > changeset_ty
Definition: DeltaAlgorithm.h:39
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::set_difference
S1Ty set_difference(const S1Ty &S1, const S2Ty &S2)
set_difference(A, B) - Return A - B
Definition: SetOperations.h:50
N
#define N