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