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