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>
43using namespace llvm;
44
45#define DEBUG_TYPE "dag-delta"
46
47namespace {
48
49class DAGDeltaAlgorithmImpl {
50  friend class DeltaActiveSetHelper;
51
52public:
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
58private:
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
81private:
82  pred_iterator_ty pred_begin(change_ty Node) {
83    assert(Predecessors.count(Node) && "Invalid node!");
84    return Predecessors[Node].begin();
85  }
86  pred_iterator_ty pred_end(change_ty Node) {
87    assert(Predecessors.count(Node) && "Invalid node!");
88    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    return PredClosure[Node].begin();
94  }
95  pred_closure_iterator_ty pred_closure_end(change_ty Node) {
96    assert(PredClosure.count(Node) && "Invalid node!");
97    return PredClosure[Node].end();
98  }
99
100  succ_iterator_ty succ_begin(change_ty Node) {
101    assert(Successors.count(Node) && "Invalid node!");
102    return Successors[Node].begin();
103  }
104  succ_iterator_ty succ_end(change_ty Node) {
105    assert(Successors.count(Node) && "Invalid node!");
106    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    return SuccClosure[Node].begin();
112  }
113  succ_closure_iterator_ty succ_closure_end(change_ty Node) {
114    assert(SuccClosure.count(Node) && "Invalid node!");
115    return SuccClosure[Node].end();
116  }
117
118  void UpdatedSearchState(const changeset_ty &Changes,
119                          const changesetlist_ty &Sets,
120                          const changeset_ty &Required) {
121    DDA.UpdatedSearchState(Changes, Sets, Required);
122  }
123
124  /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
125  bool ExecuteOneTest(const changeset_ty &S) {
126    // Check dependencies invariant.
127    DEBUG({
128        for (changeset_ty::const_iterator it = S.begin(),
129               ie = S.end(); it != ie; ++it)
130          for (succ_iterator_ty it2 = succ_begin(*it),
131                 ie2 = succ_end(*it); it2 != ie2; ++it2)
132            assert(S.count(*it2) && "Attempt to run invalid changeset!");
133      });
134
135    return DDA.ExecuteOneTest(S);
136  }
137
138public:
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.
156class DeltaActiveSetHelper : public DeltaAlgorithm {
157  DAGDeltaAlgorithmImpl &DDAI;
158
159  const changeset_ty &Required;
160
161protected:
162  /// UpdatedSearchState - Callback used when the search state changes.
163  void UpdatedSearchState(const changeset_ty &Changes,
164                                  const changesetlist_ty &Sets) override {
165    DDAI.UpdatedSearchState(Changes, Sets, Required);
166  }
167
168  bool ExecuteOneTest(const changeset_ty &S) override {
169    return DDAI.GetTestResult(S, Required);
170  }
171
172public:
173  DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI,
174                       const changeset_ty &Required)
175      : DDAI(DDAI), Required(Required) {}
176};
177
178}
179
180DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(
181    DAGDeltaAlgorithm &DDA, const changeset_ty &Changes,
182    const std::vector<edge_ty> &Dependencies)
183    : DDA(DDA) {
184  for (changeset_ty::const_iterator it = Changes.begin(),
185         ie = Changes.end(); it != ie; ++it) {
186    Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
187    Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
188  }
189  for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
190         ie = Dependencies.end(); it != ie; ++it) {
191    Predecessors[it->second].push_back(it->first);
192    Successors[it->first].push_back(it->second);
193  }
194
195  // Compute the roots.
196  for (changeset_ty::const_iterator it = Changes.begin(),
197         ie = Changes.end(); it != ie; ++it)
198    if (succ_begin(*it) == succ_end(*it))
199      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  while (!Worklist.empty()) {
204    change_ty Change = Worklist.back();
205    Worklist.pop_back();
206
207    std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
208    for (pred_iterator_ty it = pred_begin(Change),
209           ie = pred_end(Change); it != ie; ++it) {
210      SuccClosure[*it].insert(Change);
211      SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
212      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         ie = Changes.end(); it != ie; ++it)
219    PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
220  for (changeset_ty::const_iterator it = Changes.begin(),
221         ie = Changes.end(); it != ie; ++it)
222    for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
223           ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
224      PredClosure[*it2].insert(*it);
225
226  // Dump useful debug info.
227  DEBUG({
228      llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
229      llvm::errs() << "Changes: [";
230      for (changeset_ty::const_iterator it = Changes.begin(),
231             ie = Changes.end(); it != ie; ++it) {
232        if (it != Changes.begin()) 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),
238                 ie2 = succ_end(*it); it2 != ie2; ++it2) {
239            if (it2 != succ_begin(*it)) llvm::errs() << ", ";
240            llvm::errs() << "->" << *it2;
241          }
242          llvm::errs() << ")";
243        }
244      }
245      llvm::errs() << "]\n";
246
247      llvm::errs() << "Roots: [";
248      for (std::vector<change_ty>::const_iterator it = Roots.begin(),
249             ie = Roots.end(); it != ie; ++it) {
250        if (it != Roots.begin()) llvm::errs() << ", ";
251        llvm::errs() << *it;
252      }
253      llvm::errs() << "]\n";
254
255      llvm::errs() << "Predecessor Closure:\n";
256      for (changeset_ty::const_iterator it = Changes.begin(),
257             ie = Changes.end(); it != ie; ++it) {
258        llvm::errs() << format("  %-4d: [", *it);
259        for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
260               ie2 = pred_closure_end(*it); it2 != ie2; ++it2) {
261          if (it2 != pred_closure_begin(*it)) llvm::errs() << ", ";
262          llvm::errs() << *it2;
263        }
264        llvm::errs() << "]\n";
265      }
266
267      llvm::errs() << "Successor Closure:\n";
268      for (changeset_ty::const_iterator it = Changes.begin(),
269             ie = Changes.end(); it != ie; ++it) {
270        llvm::errs() << format("  %-4d: [", *it);
271        for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
272               ie2 = succ_closure_end(*it); it2 != ie2; ++it2) {
273          if (it2 != succ_closure_begin(*it)) 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(Changes.begin(), Changes.end());
287  for (changeset_ty::const_iterator it = Changes.begin(),
288         ie = Changes.end(); it != ie; ++it)
289    Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));
290
291  if (FailedTestsCache.count(Extended))
292    return false;
293
294  bool Result = ExecuteOneTest(Extended);
295  if (!Result)
296    FailedTestsCache.insert(Extended);
297
298  return Result;
299}
300
301DAGDeltaAlgorithm::changeset_ty
302DAGDeltaAlgorithmImpl::Run() {
303  // The current set of changes we are minimizing, starting at the roots.
304  changeset_ty CurrentSet(Roots.begin(), Roots.end());
305
306  // The set of required changes.
307  changeset_ty Required;
308
309  // Iterate until the active set of changes is empty. Convergence is guaranteed
310  // assuming input was a DAG.
311  //
312  // Invariant:  CurrentSet intersect Required == {}
313  // Invariant:  Required == (Required union succ*(Required))
314  while (!CurrentSet.empty()) {
315    DEBUG({
316        llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, "
317                     << Required.size() << " required changes\n";
318      });
319
320    // Minimize the current set of changes.
321    DeltaActiveSetHelper Helper(*this, Required);
322    changeset_ty CurrentMinSet = Helper.Run(CurrentSet);
323
324    // Update the set of required changes. Since
325    //   CurrentMinSet subset CurrentSet
326    // and after the last iteration,
327    //   succ(CurrentSet) subset Required
328    // then
329    //   succ(CurrentMinSet) subset Required
330    // and our invariant on Required is maintained.
331    Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());
332
333    // Replace the current set with the predecssors of the minimized set of
334    // active changes.
335    CurrentSet.clear();
336    for (changeset_ty::const_iterator it = CurrentMinSet.begin(),
337           ie = CurrentMinSet.end(); it != ie; ++it)
338      CurrentSet.insert(pred_begin(*it), pred_end(*it));
339
340    // FIXME: We could enforce CurrentSet intersect Required == {} here if we
341    // wanted to protect against cyclic graphs.
342  }
343
344  return Required;
345}
346
347void DAGDeltaAlgorithm::anchor() {
348}
349
350DAGDeltaAlgorithm::changeset_ty
351DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
352                       const std::vector<edge_ty> &Dependencies) {
353  return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
354}
355