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