LLVM  9.0.0svn
DomTreeUpdater.cpp
Go to the documentation of this file.
1 //===- DomTreeUpdater.cpp - DomTree/Post DomTree Updater --------*- 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 //
9 // This file implements the DomTreeUpdater class, which provides a uniform way
10 // to update dominator tree related data structures.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/IR/Dominators.h"
19 #include <algorithm>
20 #include <functional>
21 #include <utility>
22 
23 namespace llvm {
24 
25 bool DomTreeUpdater::isUpdateValid(
26  const DominatorTree::UpdateType Update) const {
27  const auto *From = Update.getFrom();
28  const auto *To = Update.getTo();
29  const auto Kind = Update.getKind();
30 
31  // Discard updates by inspecting the current state of successors of From.
32  // Since isUpdateValid() must be called *after* the Terminator of From is
33  // altered we can determine if the update is unnecessary for batch updates
34  // or invalid for a single update.
35  const bool HasEdge = llvm::any_of(
36  successors(From), [To](const BasicBlock *B) { return B == To; });
37 
38  // If the IR does not match the update,
39  // 1. In batch updates, this update is unnecessary.
40  // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
41  // Edge does not exist in IR.
42  if (Kind == DominatorTree::Insert && !HasEdge)
43  return false;
44 
45  // Edge exists in IR.
46  if (Kind == DominatorTree::Delete && HasEdge)
47  return false;
48 
49  return true;
50 }
51 
52 bool DomTreeUpdater::isSelfDominance(
53  const DominatorTree::UpdateType Update) const {
54  // Won't affect DomTree and PostDomTree.
55  return Update.getFrom() == Update.getTo();
56 }
57 
58 void DomTreeUpdater::applyDomTreeUpdates() {
59  // No pending DomTreeUpdates.
60  if (Strategy != UpdateStrategy::Lazy || !DT)
61  return;
62 
63  // Only apply updates not are applied by DomTree.
65  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
66  const auto E = PendUpdates.end();
67  assert(I < E && "Iterator range invalid; there should be DomTree updates.");
68  DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
69  PendDTUpdateIndex = PendUpdates.size();
70  }
71 }
72 
74  applyDomTreeUpdates();
75  applyPostDomTreeUpdates();
76  dropOutOfDateUpdates();
77 }
78 
79 void DomTreeUpdater::applyPostDomTreeUpdates() {
80  // No pending PostDomTreeUpdates.
81  if (Strategy != UpdateStrategy::Lazy || !PDT)
82  return;
83 
84  // Only apply updates not are applied by PostDomTree.
86  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
87  const auto E = PendUpdates.end();
88  assert(I < E &&
89  "Iterator range invalid; there should be PostDomTree updates.");
91  PendPDTUpdateIndex = PendUpdates.size();
92  }
93 }
94 
95 void DomTreeUpdater::tryFlushDeletedBB() {
96  if (!hasPendingUpdates())
97  forceFlushDeletedBB();
98 }
99 
100 bool DomTreeUpdater::forceFlushDeletedBB() {
101  if (DeletedBBs.empty())
102  return false;
103 
104  for (auto *BB : DeletedBBs) {
105  // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
106  // validateDeleteBB() removes all instructions of DelBB and adds an
107  // UnreachableInst as its terminator. So we check whether the BasicBlock to
108  // delete only has an UnreachableInst inside.
109  assert(BB->getInstList().size() == 1 &&
110  isa<UnreachableInst>(BB->getTerminator()) &&
111  "DelBB has been modified while awaiting deletion.");
112  BB->removeFromParent();
113  eraseDelBBNode(BB);
114  delete BB;
115  }
116  DeletedBBs.clear();
117  Callbacks.clear();
118  return true;
119 }
120 
122 
123  if (Strategy == UpdateStrategy::Eager) {
124  if (DT)
125  DT->recalculate(F);
126  if (PDT)
127  PDT->recalculate(F);
128  return;
129  }
130 
131  // There is little performance gain if we pend the recalculation under
132  // Lazy UpdateStrategy so we recalculate available trees immediately.
133 
134  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
135  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
136 
137  // Because all trees are going to be up-to-date after recalculation,
138  // flush awaiting deleted BasicBlocks.
139  forceFlushDeletedBB();
140  if (DT)
141  DT->recalculate(F);
142  if (PDT)
143  PDT->recalculate(F);
144 
145  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
146  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
147  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
148  dropOutOfDateUpdates();
149 }
150 
153 }
154 
156  if (!DT)
157  return false;
158  return PendUpdates.size() != PendDTUpdateIndex;
159 }
160 
162  if (!PDT)
163  return false;
164  return PendUpdates.size() != PendPDTUpdateIndex;
165 }
166 
168  if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
169  return false;
170  return DeletedBBs.count(DelBB) != 0;
171 }
172 
173 // The DT and PDT require the nodes related to updates
174 // are not deleted when update functions are called.
175 // So BasicBlock deletions must be pended when the
176 // UpdateStrategy is Lazy. When the UpdateStrategy is
177 // Eager, the BasicBlock will be deleted immediately.
179  validateDeleteBB(DelBB);
180  if (Strategy == UpdateStrategy::Lazy) {
181  DeletedBBs.insert(DelBB);
182  return;
183  }
184 
185  DelBB->removeFromParent();
186  eraseDelBBNode(DelBB);
187  delete DelBB;
188 }
189 
191  BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
192  validateDeleteBB(DelBB);
193  if (Strategy == UpdateStrategy::Lazy) {
194  Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
195  DeletedBBs.insert(DelBB);
196  return;
197  }
198 
199  DelBB->removeFromParent();
200  eraseDelBBNode(DelBB);
201  Callback(DelBB);
202  delete DelBB;
203 }
204 
205 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
206  if (DT && !IsRecalculatingDomTree)
207  if (DT->getNode(DelBB))
208  DT->eraseNode(DelBB);
209 
210  if (PDT && !IsRecalculatingPostDomTree)
211  if (PDT->getNode(DelBB))
212  PDT->eraseNode(DelBB);
213 }
214 
215 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
216  assert(DelBB && "Invalid push_back of nullptr DelBB.");
217  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
218  // DelBB is unreachable and all its instructions are dead.
219  while (!DelBB->empty()) {
220  Instruction &I = DelBB->back();
221  // Replace used instructions with an arbitrary value (undef).
222  if (!I.use_empty())
224  DelBB->getInstList().pop_back();
225  }
226  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
227  // Child of Function F it must contain valid IR.
228  new UnreachableInst(DelBB->getContext(), DelBB);
229 }
230 
232  if (!DT && !PDT)
233  return;
234 
235  if (Strategy == UpdateStrategy::Lazy) {
236  for (const auto U : Updates)
237  if (!isSelfDominance(U))
238  PendUpdates.push_back(U);
239 
240  return;
241  }
242 
243  if (DT)
244  DT->applyUpdates(Updates);
245  if (PDT)
246  PDT->applyUpdates(Updates);
247 }
248 
251  if (!DT && !PDT)
252  return;
253 
255  SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
256  for (const auto U : Updates) {
257  auto Edge = std::make_pair(U.getFrom(), U.getTo());
258  // Because it is illegal to submit updates that have already been applied
259  // and updates to an edge need to be strictly ordered,
260  // it is safe to infer the existence of an edge from the first update
261  // to this edge.
262  // If the first update to an edge is "Delete", it means that the edge
263  // existed before. If the first update to an edge is "Insert", it means
264  // that the edge didn't exist before.
265  //
266  // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
267  // because
268  // 1. it is illegal to submit updates that have already been applied,
269  // i.e., user cannot delete an nonexistent edge,
270  // 2. updates to an edge need to be strictly ordered,
271  // So, initially edge A -> B existed.
272  // We can then safely ignore future updates to this edge and directly
273  // inspect the current CFG:
274  // a. If the edge still exists, because the user cannot insert an existent
275  // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
276  // resulted in a no-op. DTU won't submit any update in this case.
277  // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
278  // actually happened but {Insert, A, B} was an invalid update which never
279  // happened. DTU will submit {Delete, A, B} in this case.
280  if (!isSelfDominance(U) && Seen.count(Edge) == 0) {
281  Seen.insert(Edge);
282  // If the update doesn't appear in the CFG, it means that
283  // either the change isn't made or relevant operations
284  // result in a no-op.
285  if (isUpdateValid(U)) {
286  if (isLazy())
287  PendUpdates.push_back(U);
288  else
289  DeduplicatedUpdates.push_back(U);
290  }
291  }
292  }
293 
294  if (Strategy == UpdateStrategy::Lazy)
295  return;
296 
297  if (DT)
298  DT->applyUpdates(DeduplicatedUpdates);
299  if (PDT)
300  PDT->applyUpdates(DeduplicatedUpdates);
301 }
302 
304  assert(DT && "Invalid acquisition of a null DomTree");
305  applyDomTreeUpdates();
306  dropOutOfDateUpdates();
307  return *DT;
308 }
309 
311  assert(PDT && "Invalid acquisition of a null PostDomTree");
312  applyPostDomTreeUpdates();
313  dropOutOfDateUpdates();
314  return *PDT;
315 }
316 
317 void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
318 
319 #ifndef NDEBUG
320  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
321  "Inserted edge does not appear in the CFG");
322 #endif
323 
324  if (!DT && !PDT)
325  return;
326 
327  // Won't affect DomTree and PostDomTree; discard update.
328  if (From == To)
329  return;
330 
331  if (Strategy == UpdateStrategy::Eager) {
332  if (DT)
333  DT->insertEdge(From, To);
334  if (PDT)
335  PDT->insertEdge(From, To);
336  return;
337  }
338 
339  PendUpdates.push_back({DominatorTree::Insert, From, To});
340 }
341 
342 void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
343  if (From == To)
344  return;
345 
346  if (!DT && !PDT)
347  return;
348 
349  if (!isUpdateValid({DominatorTree::Insert, From, To}))
350  return;
351 
352  if (Strategy == UpdateStrategy::Eager) {
353  if (DT)
354  DT->insertEdge(From, To);
355  if (PDT)
356  PDT->insertEdge(From, To);
357  return;
358  }
359 
360  PendUpdates.push_back({DominatorTree::Insert, From, To});
361 }
362 
363 void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
364 
365 #ifndef NDEBUG
366  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
367  "Deleted edge still exists in the CFG!");
368 #endif
369 
370  if (!DT && !PDT)
371  return;
372 
373  // Won't affect DomTree and PostDomTree; discard update.
374  if (From == To)
375  return;
376 
377  if (Strategy == UpdateStrategy::Eager) {
378  if (DT)
379  DT->deleteEdge(From, To);
380  if (PDT)
381  PDT->deleteEdge(From, To);
382  return;
383  }
384 
385  PendUpdates.push_back({DominatorTree::Delete, From, To});
386 }
387 
388 void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
389  if (From == To)
390  return;
391 
392  if (!DT && !PDT)
393  return;
394 
395  if (!isUpdateValid({DominatorTree::Delete, From, To}))
396  return;
397 
398  if (Strategy == UpdateStrategy::Eager) {
399  if (DT)
400  DT->deleteEdge(From, To);
401  if (PDT)
402  PDT->deleteEdge(From, To);
403  return;
404  }
405 
406  PendUpdates.push_back({DominatorTree::Delete, From, To});
407 }
408 
409 void DomTreeUpdater::dropOutOfDateUpdates() {
411  return;
412 
413  tryFlushDeletedBB();
414 
415  // Drop all updates applied by both trees.
416  if (!DT)
417  PendDTUpdateIndex = PendUpdates.size();
418  if (!PDT)
419  PendPDTUpdateIndex = PendUpdates.size();
420 
421  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
422  const auto B = PendUpdates.begin();
423  const auto E = PendUpdates.begin() + dropIndex;
424  assert(B <= E && "Iterator out of range.");
425  PendUpdates.erase(B, E);
426  // Calculate current index.
427  PendDTUpdateIndex -= dropIndex;
428  PendPDTUpdateIndex -= dropIndex;
429 }
430 
431 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
433  raw_ostream &OS = llvm::dbgs();
434 
435  OS << "Available Trees: ";
436  if (DT || PDT) {
437  if (DT)
438  OS << "DomTree ";
439  if (PDT)
440  OS << "PostDomTree ";
441  OS << "\n";
442  } else
443  OS << "None\n";
444 
445  OS << "UpdateStrategy: ";
446  if (Strategy == UpdateStrategy::Eager) {
447  OS << "Eager\n";
448  return;
449  } else
450  OS << "Lazy\n";
451  int Index = 0;
452 
453  auto printUpdates =
456  if (begin == end)
457  OS << " None\n";
458  Index = 0;
459  for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
460  auto U = *It;
461  OS << " " << Index << " : ";
462  ++Index;
463  if (U.getKind() == DominatorTree::Insert)
464  OS << "Insert, ";
465  else
466  OS << "Delete, ";
467  BasicBlock *From = U.getFrom();
468  if (From) {
469  auto S = From->getName();
470  if (!From->hasName())
471  S = "(no name)";
472  OS << S << "(" << From << "), ";
473  } else {
474  OS << "(badref), ";
475  }
476  BasicBlock *To = U.getTo();
477  if (To) {
478  auto S = To->getName();
479  if (!To->hasName())
480  S = "(no_name)";
481  OS << S << "(" << To << ")\n";
482  } else {
483  OS << "(badref)\n";
484  }
485  }
486  };
487 
488  if (DT) {
489  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
490  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
491  "Iterator out of range.");
492  OS << "Applied but not cleared DomTreeUpdates:\n";
493  printUpdates(PendUpdates.begin(), I);
494  OS << "Pending DomTreeUpdates:\n";
495  printUpdates(I, PendUpdates.end());
496  }
497 
498  if (PDT) {
499  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
500  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
501  "Iterator out of range.");
502  OS << "Applied but not cleared PostDomTreeUpdates:\n";
503  printUpdates(PendUpdates.begin(), I);
504  OS << "Pending PostDomTreeUpdates:\n";
505  printUpdates(I, PendUpdates.end());
506  }
507 
508  OS << "Pending DeletedBBs:\n";
509  Index = 0;
510  for (auto BB : DeletedBBs) {
511  OS << " " << Index << " : ";
512  ++Index;
513  if (BB->hasName())
514  OS << BB->getName() << "(";
515  else
516  OS << "(no_name)(";
517  OS << BB << ")\n";
518  }
519 
520  OS << "Pending Callbacks:\n";
521  Index = 0;
522  for (auto BB : Callbacks) {
523  OS << " " << Index << " : ";
524  ++Index;
525  if (BB->hasName())
526  OS << BB->getName() << "(";
527  else
528  OS << "(no_name)(";
529  OS << BB << ")\n";
530  }
531 }
532 #endif
533 } // namespace llvm
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
Various leaf nodes.
Definition: ISDOpcodes.h:59
void push_back(const T &Elt)
Definition: SmallVector.h:211
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
F(f)
bool isLazy() const
Returns true if the current strategy is Lazy.
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
bool empty() const
Definition: BasicBlock.h:279
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool hasName() const
Definition: Value.h:250
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
This function has undefined behavior.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
const Instruction & back() const
Definition: BasicBlock.h:282
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:116
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
iterator erase(const_iterator CI)
Definition: SmallVector.h:438
size_t size() const
Definition: SmallVector.h:52
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
void removeFromParent()
Unlink &#39;this&#39; from the containing function, but do not delete it.
Definition: BasicBlock.cpp:110
BlockVerifier::State From
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
bool hasPendingDomTreeUpdates() const
Returns true if there are DominatorTree updates queued.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
#define I(x, y, z)
Definition: MD5.cpp:58
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDominatorTree updates queued.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
succ_range successors(Instruction *I)
Definition: CFG.h:259
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
print Print MemDeps of function
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
void pop_back()
Definition: ilist.h:316
bool use_empty() const
Definition: Value.h:322
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164