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