1 //===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //===----------------------------------------------------------------------===//
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
13 // 1. Minimize the set R using the test predicate:
14 // P'(S) = P(S union pred*(S))
16 // 2. Extend R to R' = R union pred(R).
18 // until a fixed point is reached.
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
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
32 //===----------------------------------------------------------------------===//
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"
45 #define DEBUG_TYPE "dag-delta"
49 class DAGDeltaAlgorithmImpl {
50 friend class DeltaActiveSetHelper;
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;
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;
64 DAGDeltaAlgorithm &DDA;
66 const changeset_ty &Changes;
67 const std::vector<edge_ty> &Dependencies;
69 std::vector<change_ty> Roots;
71 /// Cache of failed test results. Successful test results are never cached
72 /// since we always reduce following a success. We maintain an independent
73 /// cache from that used by the individual delta passes because we may get
74 /// hits across multiple individual delta invocations.
75 mutable std::set<changeset_ty> FailedTestsCache;
78 std::map<change_ty, std::vector<change_ty> > Predecessors;
79 std::map<change_ty, std::vector<change_ty> > Successors;
81 std::map<change_ty, std::set<change_ty> > PredClosure;
82 std::map<change_ty, std::set<change_ty> > SuccClosure;
85 pred_iterator_ty pred_begin(change_ty Node) {
86 assert(Predecessors.count(Node) && "Invalid node!");
87 return Predecessors[Node].begin();
89 pred_iterator_ty pred_end(change_ty Node) {
90 assert(Predecessors.count(Node) && "Invalid node!");
91 return Predecessors[Node].end();
94 pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
95 assert(PredClosure.count(Node) && "Invalid node!");
96 return PredClosure[Node].begin();
98 pred_closure_iterator_ty pred_closure_end(change_ty Node) {
99 assert(PredClosure.count(Node) && "Invalid node!");
100 return PredClosure[Node].end();
103 succ_iterator_ty succ_begin(change_ty Node) {
104 assert(Successors.count(Node) && "Invalid node!");
105 return Successors[Node].begin();
107 succ_iterator_ty succ_end(change_ty Node) {
108 assert(Successors.count(Node) && "Invalid node!");
109 return Successors[Node].end();
112 succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
113 assert(SuccClosure.count(Node) && "Invalid node!");
114 return SuccClosure[Node].begin();
116 succ_closure_iterator_ty succ_closure_end(change_ty Node) {
117 assert(SuccClosure.count(Node) && "Invalid node!");
118 return SuccClosure[Node].end();
121 void UpdatedSearchState(const changeset_ty &Changes,
122 const changesetlist_ty &Sets,
123 const changeset_ty &Required) {
124 DDA.UpdatedSearchState(Changes, Sets, Required);
127 /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
128 bool ExecuteOneTest(const changeset_ty &S) {
129 // Check dependencies invariant.
131 for (changeset_ty::const_iterator it = S.begin(),
132 ie = S.end(); it != ie; ++it)
133 for (succ_iterator_ty it2 = succ_begin(*it),
134 ie2 = succ_end(*it); it2 != ie2; ++it2)
135 assert(S.count(*it2) && "Attempt to run invalid changeset!");
138 return DDA.ExecuteOneTest(S);
142 DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA,
143 const changeset_ty &_Changes,
144 const std::vector<edge_ty> &_Dependencies);
148 /// GetTestResult - Get the test result for the active set \p Changes with
149 /// \p Required changes from the cache, executing the test if necessary.
151 /// \param Changes - The set of active changes being minimized, which should
152 /// have their pred closure included in the test.
153 /// \param Required - The set of changes which have previously been
154 /// established to be required.
155 /// \return - The test result.
156 bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required);
159 /// Helper object for minimizing an active set of changes.
160 class DeltaActiveSetHelper : public DeltaAlgorithm {
161 DAGDeltaAlgorithmImpl &DDAI;
163 const changeset_ty &Required;
166 /// UpdatedSearchState - Callback used when the search state changes.
167 void UpdatedSearchState(const changeset_ty &Changes,
168 const changesetlist_ty &Sets) override {
169 DDAI.UpdatedSearchState(Changes, Sets, Required);
172 bool ExecuteOneTest(const changeset_ty &S) override {
173 return DDAI.GetTestResult(S, Required);
177 DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI,
178 const changeset_ty &_Required)
179 : DDAI(_DDAI), Required(_Required) {}
184 DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA,
185 const changeset_ty &_Changes,
186 const std::vector<edge_ty>
190 Dependencies(_Dependencies)
192 for (changeset_ty::const_iterator it = Changes.begin(),
193 ie = Changes.end(); it != ie; ++it) {
194 Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
195 Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
197 for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
198 ie = Dependencies.end(); it != ie; ++it) {
199 Predecessors[it->second].push_back(it->first);
200 Successors[it->first].push_back(it->second);
203 // Compute the roots.
204 for (changeset_ty::const_iterator it = Changes.begin(),
205 ie = Changes.end(); it != ie; ++it)
206 if (succ_begin(*it) == succ_end(*it))
207 Roots.push_back(*it);
209 // Pre-compute the closure of the successor relation.
210 std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
211 while (!Worklist.empty()) {
212 change_ty Change = Worklist.back();
215 std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
216 for (pred_iterator_ty it = pred_begin(Change),
217 ie = pred_end(Change); it != ie; ++it) {
218 SuccClosure[*it].insert(Change);
219 SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
220 Worklist.push_back(*it);
224 // Invert to form the predecessor closure map.
225 for (changeset_ty::const_iterator it = Changes.begin(),
226 ie = Changes.end(); it != ie; ++it)
227 PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
228 for (changeset_ty::const_iterator it = Changes.begin(),
229 ie = Changes.end(); it != ie; ++it)
230 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
231 ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
232 PredClosure[*it2].insert(*it);
234 // Dump useful debug info.
236 llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
237 llvm::errs() << "Changes: [";
238 for (changeset_ty::const_iterator it = Changes.begin(),
239 ie = Changes.end(); it != ie; ++it) {
240 if (it != Changes.begin()) llvm::errs() << ", ";
243 if (succ_begin(*it) != succ_end(*it)) {
245 for (succ_iterator_ty it2 = succ_begin(*it),
246 ie2 = succ_end(*it); it2 != ie2; ++it2) {
247 if (it2 != succ_begin(*it)) llvm::errs() << ", ";
248 llvm::errs() << "->" << *it2;
253 llvm::errs() << "]\n";
255 llvm::errs() << "Roots: [";
256 for (std::vector<change_ty>::const_iterator it = Roots.begin(),
257 ie = Roots.end(); it != ie; ++it) {
258 if (it != Roots.begin()) llvm::errs() << ", ";
261 llvm::errs() << "]\n";
263 llvm::errs() << "Predecessor Closure:\n";
264 for (changeset_ty::const_iterator it = Changes.begin(),
265 ie = Changes.end(); it != ie; ++it) {
266 llvm::errs() << format(" %-4d: [", *it);
267 for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
268 ie2 = pred_closure_end(*it); it2 != ie2; ++it2) {
269 if (it2 != pred_closure_begin(*it)) llvm::errs() << ", ";
270 llvm::errs() << *it2;
272 llvm::errs() << "]\n";
275 llvm::errs() << "Successor Closure:\n";
276 for (changeset_ty::const_iterator it = Changes.begin(),
277 ie = Changes.end(); it != ie; ++it) {
278 llvm::errs() << format(" %-4d: [", *it);
279 for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
280 ie2 = succ_closure_end(*it); it2 != ie2; ++it2) {
281 if (it2 != succ_closure_begin(*it)) llvm::errs() << ", ";
282 llvm::errs() << *it2;
284 llvm::errs() << "]\n";
287 llvm::errs() << "\n\n";
291 bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
292 const changeset_ty &Required) {
293 changeset_ty Extended(Required);
294 Extended.insert(Changes.begin(), Changes.end());
295 for (changeset_ty::const_iterator it = Changes.begin(),
296 ie = Changes.end(); it != ie; ++it)
297 Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));
299 if (FailedTestsCache.count(Extended))
302 bool Result = ExecuteOneTest(Extended);
304 FailedTestsCache.insert(Extended);
309 DAGDeltaAlgorithm::changeset_ty
310 DAGDeltaAlgorithmImpl::Run() {
311 // The current set of changes we are minimizing, starting at the roots.
312 changeset_ty CurrentSet(Roots.begin(), Roots.end());
314 // The set of required changes.
315 changeset_ty Required;
317 // Iterate until the active set of changes is empty. Convergence is guaranteed
318 // assuming input was a DAG.
320 // Invariant: CurrentSet intersect Required == {}
321 // Invariant: Required == (Required union succ*(Required))
322 while (!CurrentSet.empty()) {
324 llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, "
325 << Required.size() << " required changes\n";
328 // Minimize the current set of changes.
329 DeltaActiveSetHelper Helper(*this, Required);
330 changeset_ty CurrentMinSet = Helper.Run(CurrentSet);
332 // Update the set of required changes. Since
333 // CurrentMinSet subset CurrentSet
334 // and after the last iteration,
335 // succ(CurrentSet) subset Required
337 // succ(CurrentMinSet) subset Required
338 // and our invariant on Required is maintained.
339 Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());
341 // Replace the current set with the predecssors of the minimized set of
344 for (changeset_ty::const_iterator it = CurrentMinSet.begin(),
345 ie = CurrentMinSet.end(); it != ie; ++it)
346 CurrentSet.insert(pred_begin(*it), pred_end(*it));
348 // FIXME: We could enforce CurrentSet intersect Required == {} here if we
349 // wanted to protect against cyclic graphs.
355 void DAGDeltaAlgorithm::anchor() {
358 DAGDeltaAlgorithm::changeset_ty
359 DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
360 const std::vector<edge_ty> &Dependencies) {
361 return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();