LLVM  14.0.0git
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 } // namespace
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 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
it
into xmm2 addss xmm2 xmm1 xmm3 addss xmm3 movaps xmm0 unpcklps xmm0 ret seems silly when it could just be one addps Expand libm rounding functions main should enable SSE DAZ mode and other fast SSE modes Think about doing i64 math in SSE regs on x86 This testcase should have no SSE instructions in it
Definition: README-SSE.txt:81
DeltaAlgorithm.h
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::DAGDeltaAlgorithm
DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing directed acyclic graphs u...
Definition: DAGDeltaAlgorithm.h:38
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
Format.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::cl::Required
@ Required
Definition: CommandLine.h:121
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::DAGDeltaAlgorithm::UpdatedSearchState
virtual void UpdatedSearchState(const changeset_ty &Changes, const changesetlist_ty &Sets, const changeset_ty &Required)
UpdatedSearchState - Callback used when the search state changes.
Definition: DAGDeltaAlgorithm.h:68
DAGDeltaAlgorithm.h
llvm::DAGDeltaAlgorithm::ExecuteOneTest
virtual bool ExecuteOneTest(const changeset_ty &S)=0
ExecuteOneTest - Execute a single test predicate on the change set S.
llvm::DAGDeltaAlgorithm::edge_ty
std::pair< change_ty, change_ty > edge_ty
Definition: DAGDeltaAlgorithm.h:43
llvm::DAGDeltaAlgorithm::Run
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.
Definition: DAGDeltaAlgorithm.cpp:358
llvm::succ_begin
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:99
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::format
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::DAGDeltaAlgorithm::changesetlist_ty
std::vector< changeset_ty > changesetlist_ty
Definition: DAGDeltaAlgorithm.h:47
llvm::DAGDeltaAlgorithm::changeset_ty
std::set< change_ty > changeset_ty
Definition: DAGDeltaAlgorithm.h:46
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::pred_begin
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:109
llvm::DAGDeltaAlgorithm::change_ty
unsigned change_ty
Definition: DAGDeltaAlgorithm.h:42
raw_ostream.h
Debug.h
llvm::DeltaAlgorithm
DeltaAlgorithm - Implements the delta debugging algorithm (A.
Definition: DeltaAlgorithm.h:35