1 //===--- DAGDeltaAlgorithm.cpp - A DAG 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 //
8 // The algorithm we use attempts to exploit the dependency information by
9 // minimizing top-down. We start by constructing an initial root set R, and
10 // then iteratively:
11 //
12 // 1. Minimize the set R using the test predicate:
13 // P'(S) = P(S union pred*(S))
14 //
15 // 2. Extend R to R' = R union pred(R).
16 //
17 // until a fixed point is reached.
18 //
19 // The idea is that we want to quickly prune entire portions of the graph, so we
20 // try to find high-level nodes that can be eliminated with all of their
21 // dependents.
22 //
23 // FIXME: The current algorithm doesn't actually provide a strong guarantee
24 // about the minimality of the result. The problem is that after adding nodes to
25 // the required set, we no longer consider them for elimination. For strictly
26 // well formed predicates, this doesn't happen, but it commonly occurs in
27 // practice when there are unmodelled dependencies. I believe we can resolve
28 // this by allowing the required set to be minimized as well, but need more test
29 // cases first.
30 //
31 //===----------------------------------------------------------------------===//
32
33 #include "llvm/ADT/DAGDeltaAlgorithm.h"
34 #include "llvm/ADT/DeltaAlgorithm.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/Format.h"
37 #include "llvm/Support/raw_ostream.h"
38 #include <algorithm>
39 #include <cassert>
40 #include <iterator>
41 #include <map>
42 using namespace llvm;
43
44 #define DEBUG_TYPE "dag-delta"
45
46 namespace {
47
48 class DAGDeltaAlgorithmImpl {
49 friend class DeltaActiveSetHelper;
50
51 public:
52 typedef DAGDeltaAlgorithm::change_ty change_ty;
53 typedef DAGDeltaAlgorithm::changeset_ty changeset_ty;
54 typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty;
55 typedef DAGDeltaAlgorithm::edge_ty edge_ty;
56
57 private:
58 typedef std::vector<change_ty>::iterator pred_iterator_ty;
59 typedef std::vector<change_ty>::iterator succ_iterator_ty;
60 typedef std::set<change_ty>::iterator pred_closure_iterator_ty;
61 typedef std::set<change_ty>::iterator succ_closure_iterator_ty;
62
63 DAGDeltaAlgorithm &DDA;
64
65 std::vector<change_ty> Roots;
66
67 /// Cache of failed test results. Successful test results are never cached
68 /// since we always reduce following a success. We maintain an independent
69 /// cache from that used by the individual delta passes because we may get
70 /// hits across multiple individual delta invocations.
71 mutable std::set<changeset_ty> FailedTestsCache;
72
73 // FIXME: Gross.
74 std::map<change_ty, std::vector<change_ty> > Predecessors;
75 std::map<change_ty, std::vector<change_ty> > Successors;
76
77 std::map<change_ty, std::set<change_ty> > PredClosure;
78 std::map<change_ty, std::set<change_ty> > SuccClosure;
79
80 private:
pred_begin(change_ty Node)81 pred_iterator_ty pred_begin(change_ty Node) {
82 assert(Predecessors.count(Node) && "Invalid node!");
83 return Predecessors[Node].begin();
84 }
pred_end(change_ty Node)85 pred_iterator_ty pred_end(change_ty Node) {
86 assert(Predecessors.count(Node) && "Invalid node!");
87 return Predecessors[Node].end();
88 }
89
pred_closure_begin(change_ty Node)90 pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
91 assert(PredClosure.count(Node) && "Invalid node!");
92 return PredClosure[Node].begin();
93 }
pred_closure_end(change_ty Node)94 pred_closure_iterator_ty pred_closure_end(change_ty Node) {
95 assert(PredClosure.count(Node) && "Invalid node!");
96 return PredClosure[Node].end();
97 }
98
succ_begin(change_ty Node)99 succ_iterator_ty succ_begin(change_ty Node) {
100 assert(Successors.count(Node) && "Invalid node!");
101 return Successors[Node].begin();
102 }
succ_end(change_ty Node)103 succ_iterator_ty succ_end(change_ty Node) {
104 assert(Successors.count(Node) && "Invalid node!");
105 return Successors[Node].end();
106 }
107
succ_closure_begin(change_ty Node)108 succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
109 assert(SuccClosure.count(Node) && "Invalid node!");
110 return SuccClosure[Node].begin();
111 }
succ_closure_end(change_ty Node)112 succ_closure_iterator_ty succ_closure_end(change_ty Node) {
113 assert(SuccClosure.count(Node) && "Invalid node!");
114 return SuccClosure[Node].end();
115 }
116
UpdatedSearchState(const changeset_ty & Changes,const changesetlist_ty & Sets,const changeset_ty & Required)117 void UpdatedSearchState(const changeset_ty &Changes,
118 const changesetlist_ty &Sets,
119 const changeset_ty &Required) {
120 DDA.UpdatedSearchState(Changes, Sets, Required);
121 }
122
123 /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
ExecuteOneTest(const changeset_ty & S)124 bool ExecuteOneTest(const changeset_ty &S) {
125 // Check dependencies invariant.
126 LLVM_DEBUG({
127 for (changeset_ty::const_iterator it = S.begin(), ie = S.end(); it != ie;
128 ++it)
129 for (succ_iterator_ty it2 = succ_begin(*it), ie2 = succ_end(*it);
130 it2 != ie2; ++it2)
131 assert(S.count(*it2) && "Attempt to run invalid changeset!");
132 });
133
134 return DDA.ExecuteOneTest(S);
135 }
136
137 public:
138 DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
139 const std::vector<edge_ty> &Dependencies);
140
141 changeset_ty Run();
142
143 /// GetTestResult - Get the test result for the active set \p Changes with
144 /// \p Required changes from the cache, executing the test if necessary.
145 ///
146 /// \param Changes - The set of active changes being minimized, which should
147 /// have their pred closure included in the test.
148 /// \param Required - The set of changes which have previously been
149 /// established to be required.
150 /// \return - The test result.
151 bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required);
152 };
153
154 /// Helper object for minimizing an active set of changes.
155 class DeltaActiveSetHelper : public DeltaAlgorithm {
156 DAGDeltaAlgorithmImpl &DDAI;
157
158 const changeset_ty &Required;
159
160 protected:
161 /// UpdatedSearchState - Callback used when the search state changes.
UpdatedSearchState(const changeset_ty & Changes,const changesetlist_ty & Sets)162 void UpdatedSearchState(const changeset_ty &Changes,
163 const changesetlist_ty &Sets) override {
164 DDAI.UpdatedSearchState(Changes, Sets, Required);
165 }
166
ExecuteOneTest(const changeset_ty & S)167 bool ExecuteOneTest(const changeset_ty &S) override {
168 return DDAI.GetTestResult(S, Required);
169 }
170
171 public:
DeltaActiveSetHelper(DAGDeltaAlgorithmImpl & DDAI,const changeset_ty & Required)172 DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI,
173 const changeset_ty &Required)
174 : DDAI(DDAI), Required(Required) {}
175 };
176
177 } // namespace
178
DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm & DDA,const changeset_ty & Changes,const std::vector<edge_ty> & Dependencies)179 DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
180 DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
181 const std::vector<edge_ty> &Dependencies)
182 : DDA(DDA) {
183 for (changeset_ty::const_iterator it = Changes.begin(),
184 ie = Changes.end(); it != ie; ++it) {
185 Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
186 Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
187 }
188 for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
189 ie = Dependencies.end(); it != ie; ++it) {
190 Predecessors[it->second].push_back(it->first);
191 Successors[it->first].push_back(it->second);
192 }
193
194 // Compute the roots.
195 for (changeset_ty::const_iterator it = Changes.begin(),
196 ie = Changes.end(); it != ie; ++it)
197 if (succ_begin(*it) == succ_end(*it))
198 Roots.push_back(*it);
199
200 // Pre-compute the closure of the successor relation.
201 std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
202 while (!Worklist.empty()) {
203 change_ty Change = Worklist.back();
204 Worklist.pop_back();
205
206 std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
207 for (pred_iterator_ty it = pred_begin(Change),
208 ie = pred_end(Change); it != ie; ++it) {
209 SuccClosure[*it].insert(Change);
210 SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
211 Worklist.push_back(*it);
212 }
213 }
214
215 // Invert to form the predecessor closure map.
216 for (changeset_ty::const_iterator it = Changes.begin(),
217 ie = Changes.end(); it != ie; ++it)
218 PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
219 for (changeset_ty::const_iterator it = Changes.begin(),
220 ie = Changes.end(); it != ie; ++it)
221 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
222 ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
223 PredClosure[*it2].insert(*it);
224
225 // Dump useful debug info.
226 LLVM_DEBUG({
227 llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
228 llvm::errs() << "Changes: [";
229 for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
230 it != ie; ++it) {
231 if (it != Changes.begin())
232 llvm::errs() << ", ";
233 llvm::errs() << *it;
234
235 if (succ_begin(*it) != succ_end(*it)) {
236 llvm::errs() << "(";
237 for (succ_iterator_ty it2 = succ_begin(*it), ie2 = succ_end(*it);
238 it2 != ie2; ++it2) {
239 if (it2 != succ_begin(*it))
240 llvm::errs() << ", ";
241 llvm::errs() << "->" << *it2;
242 }
243 llvm::errs() << ")";
244 }
245 }
246 llvm::errs() << "]\n";
247
248 llvm::errs() << "Roots: [";
249 for (std::vector<change_ty>::const_iterator it = Roots.begin(),
250 ie = Roots.end();
251 it != ie; ++it) {
252 if (it != Roots.begin())
253 llvm::errs() << ", ";
254 llvm::errs() << *it;
255 }
256 llvm::errs() << "]\n";
257
258 llvm::errs() << "Predecessor Closure:\n";
259 for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
260 it != ie; ++it) {
261 llvm::errs() << format(" %-4d: [", *it);
262 for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
263 ie2 = pred_closure_end(*it);
264 it2 != ie2; ++it2) {
265 if (it2 != pred_closure_begin(*it))
266 llvm::errs() << ", ";
267 llvm::errs() << *it2;
268 }
269 llvm::errs() << "]\n";
270 }
271
272 llvm::errs() << "Successor Closure:\n";
273 for (changeset_ty::const_iterator it = Changes.begin(), ie = Changes.end();
274 it != ie; ++it) {
275 llvm::errs() << format(" %-4d: [", *it);
276 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
277 ie2 = succ_closure_end(*it);
278 it2 != ie2; ++it2) {
279 if (it2 != succ_closure_begin(*it))
280 llvm::errs() << ", ";
281 llvm::errs() << *it2;
282 }
283 llvm::errs() << "]\n";
284 }
285
286 llvm::errs() << "\n\n";
287 });
288 }
289
GetTestResult(const changeset_ty & Changes,const changeset_ty & Required)290 bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
291 const changeset_ty &Required) {
292 changeset_ty Extended(Required);
293 Extended.insert(Changes.begin(), Changes.end());
294 for (changeset_ty::const_iterator it = Changes.begin(),
295 ie = Changes.end(); it != ie; ++it)
296 Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));
297
298 if (FailedTestsCache.count(Extended))
299 return false;
300
301 bool Result = ExecuteOneTest(Extended);
302 if (!Result)
303 FailedTestsCache.insert(Extended);
304
305 return Result;
306 }
307
308 DAGDeltaAlgorithm::changeset_ty
Run()309 DAGDeltaAlgorithmImpl::Run() {
310 // The current set of changes we are minimizing, starting at the roots.
311 changeset_ty CurrentSet(Roots.begin(), Roots.end());
312
313 // The set of required changes.
314 changeset_ty Required;
315
316 // Iterate until the active set of changes is empty. Convergence is guaranteed
317 // assuming input was a DAG.
318 //
319 // Invariant: CurrentSet intersect Required == {}
320 // Invariant: Required == (Required union succ*(Required))
321 while (!CurrentSet.empty()) {
322 LLVM_DEBUG({
323 llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, "
324 << Required.size() << " required changes\n";
325 });
326
327 // Minimize the current set of changes.
328 DeltaActiveSetHelper Helper(*this, Required);
329 changeset_ty CurrentMinSet = Helper.Run(CurrentSet);
330
331 // Update the set of required changes. Since
332 // CurrentMinSet subset CurrentSet
333 // and after the last iteration,
334 // succ(CurrentSet) subset Required
335 // then
336 // succ(CurrentMinSet) subset Required
337 // and our invariant on Required is maintained.
338 Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());
339
340 // Replace the current set with the predecssors of the minimized set of
341 // active changes.
342 CurrentSet.clear();
343 for (changeset_ty::const_iterator it = CurrentMinSet.begin(),
344 ie = CurrentMinSet.end(); it != ie; ++it)
345 CurrentSet.insert(pred_begin(*it), pred_end(*it));
346
347 // FIXME: We could enforce CurrentSet intersect Required == {} here if we
348 // wanted to protect against cyclic graphs.
349 }
350
351 return Required;
352 }
353
anchor()354 void DAGDeltaAlgorithm::anchor() {
355 }
356
357 DAGDeltaAlgorithm::changeset_ty
Run(const changeset_ty & Changes,const std::vector<edge_ty> & Dependencies)358 DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
359 const std::vector<edge_ty> &Dependencies) {
360 return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
361 }
362