LLVM  8.0.0svn
DAGDeltaAlgorithm.cpp
Go to the documentation of this file.
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
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
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/Format.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  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  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  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 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  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
172 public:
173  DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &DDAI,
174  const changeset_ty &Required)
175  : DDAI(DDAI), Required(Required) {}
176 };
177
178 }
179
180 DAGDeltaAlgorithmImpl::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  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 }
290
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));
298
299  if (FailedTestsCache.count(Extended))
300  return false;
301
302  bool Result = ExecuteOneTest(Extended);
303  if (!Result)
304  FailedTestsCache.insert(Extended);
305
306  return Result;
307 }
308
310 DAGDeltaAlgorithmImpl::Run() {
311  // The current set of changes we are minimizing, starting at the roots.
312  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  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  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  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  ie = CurrentMinSet.end(); it != ie; ++it)
346  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  return Required;
353 }
354
355 void DAGDeltaAlgorithm::anchor() {
356 }
357
360  const std::vector<edge_ty> &Dependencies) {
361  return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
362 }
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing directed acyclic graphs u...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
std::set< change_ty > changeset_ty
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:103
std::vector< changeset_ty > changesetlist_ty
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
DeltaAlgorithm - Implements the delta debugging algorithm (A.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
virtual bool ExecuteOneTest(const changeset_ty &S)=0
ExecuteOneTest - Execute a single test predicate on the change set S.
std::pair< change_ty, change_ty > edge_ty
changeset_ty Run(const changeset_ty &Changes, const std::vector< edge_ty > &Dependencies)
Run - Minimize the DAG formed by the Changes vertices and the Dependencies edges by executing...
virtual void UpdatedSearchState(const changeset_ty &Changes, const changesetlist_ty &Sets, const changeset_ty &Required)
UpdatedSearchState - Callback used when the search state changes.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define LLVM_DEBUG(X)
Definition: Debug.h:123