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