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 
14 #include "llvm/IR/DomTreeUpdater.h"
16 #include "llvm/IR/Dominators.h"
18 #include <algorithm>
19 #include <functional>
20 
21 namespace llvm {
22 
23 bool DomTreeUpdater::isUpdateValid(
24  const DominatorTree::UpdateType Update) const {
25  const auto *From = Update.getFrom();
26  const auto *To = Update.getTo();
27  const auto Kind = Update.getKind();
28 
29  // Discard updates by inspecting the current state of successors of From.
30  // Since isUpdateValid() must be called *after* the Terminator of From is
31  // altered we can determine if the update is unnecessary for batch updates
32  // or invalid for a single update.
33  const bool HasEdge = llvm::any_of(
34  successors(From), [To](const BasicBlock *B) { return B == To; });
35 
36  // If the IR does not match the update,
37  // 1. In batch updates, this update is unnecessary.
38  // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
39  // Edge does not exist in IR.
40  if (Kind == DominatorTree::Insert && !HasEdge)
41  return false;
42 
43  // Edge exists in IR.
44  if (Kind == DominatorTree::Delete && HasEdge)
45  return false;
46 
47  return true;
48 }
49 
50 bool DomTreeUpdater::isSelfDominance(
51  const DominatorTree::UpdateType Update) const {
52  // Won't affect DomTree and PostDomTree.
53  return Update.getFrom() == Update.getTo();
54 }
55 
56 bool DomTreeUpdater::applyLazyUpdate(DominatorTree::UpdateKind Kind,
57  BasicBlock *From, BasicBlock *To) {
58  assert((DT || PDT) &&
59  "Call applyLazyUpdate() when both DT and PDT are nullptrs.");
61  "Call applyLazyUpdate() with Eager strategy error");
62  // Analyze pending updates to determine if the update is unnecessary.
63  const DominatorTree::UpdateType Update = {Kind, From, To};
64  const DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
67  From, To};
68  // Only check duplicates in updates that are not applied by both trees.
69  auto I =
70  PendUpdates.begin() + std::max(PendDTUpdateIndex, PendPDTUpdateIndex);
71  const auto E = PendUpdates.end();
72 
73  assert(I <= E && "Iterator out of range.");
74 
75  for (; I != E; ++I) {
76  if (Update == *I)
77  return false; // Discard duplicate updates.
78 
79  if (Invert == *I) {
80  // Update and Invert are both valid (equivalent to a no-op). Remove
81  // Invert from PendUpdates and discard the Update.
82  PendUpdates.erase(I);
83  return false;
84  }
85  }
86 
87  PendUpdates.push_back(Update); // Save the valid update.
88  return true;
89 }
90 
91 void DomTreeUpdater::applyDomTreeUpdates() {
92  // No pending DomTreeUpdates.
93  if (Strategy != UpdateStrategy::Lazy || !DT)
94  return;
95 
96  // Only apply updates not are applied by DomTree.
98  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
99  const auto E = PendUpdates.end();
100  assert(I < E && "Iterator range invalid; there should be DomTree updates.");
101  DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
102  PendDTUpdateIndex = PendUpdates.size();
103  }
104 }
105 
107  applyDomTreeUpdates();
108  applyPostDomTreeUpdates();
109  dropOutOfDateUpdates();
110 }
111 
112 void DomTreeUpdater::applyPostDomTreeUpdates() {
113  // No pending PostDomTreeUpdates.
114  if (Strategy != UpdateStrategy::Lazy || !PDT)
115  return;
116 
117  // Only apply updates not are applied by PostDomTree.
119  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
120  const auto E = PendUpdates.end();
121  assert(I < E &&
122  "Iterator range invalid; there should be PostDomTree updates.");
124  PendPDTUpdateIndex = PendUpdates.size();
125  }
126 }
127 
128 void DomTreeUpdater::tryFlushDeletedBB() {
129  if (!hasPendingUpdates())
130  forceFlushDeletedBB();
131 }
132 
133 bool DomTreeUpdater::forceFlushDeletedBB() {
134  if (DeletedBBs.empty())
135  return false;
136 
137  for (auto *BB : DeletedBBs) {
138  // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
139  // validateDeleteBB() removes all instructions of DelBB and adds an
140  // UnreachableInst as its terminator. So we check whether the BasicBlock to
141  // delete only has an UnreachableInst inside.
142  assert(BB->getInstList().size() == 1 &&
143  isa<UnreachableInst>(BB->getTerminator()) &&
144  "DelBB has been modified while awaiting deletion.");
145  BB->removeFromParent();
146  eraseDelBBNode(BB);
147  delete BB;
148  }
149  DeletedBBs.clear();
150  Callbacks.clear();
151  return true;
152 }
153 
155 
156  if (Strategy == UpdateStrategy::Eager) {
157  if (DT)
158  DT->recalculate(F);
159  if (PDT)
160  PDT->recalculate(F);
161  return;
162  }
163 
164  // There is little performance gain if we pend the recalculation under
165  // Lazy UpdateStrategy so we recalculate available trees immediately.
166 
167  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
168  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
169 
170  // Because all trees are going to be up-to-date after recalculation,
171  // flush awaiting deleted BasicBlocks.
172  forceFlushDeletedBB();
173  if (DT)
174  DT->recalculate(F);
175  if (PDT)
176  PDT->recalculate(F);
177 
178  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
179  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
180  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
181  dropOutOfDateUpdates();
182 }
183 
186 }
187 
189  if (!DT)
190  return false;
191  return PendUpdates.size() != PendDTUpdateIndex;
192 }
193 
195  if (!PDT)
196  return false;
197  return PendUpdates.size() != PendPDTUpdateIndex;
198 }
199 
201  if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
202  return false;
203  return DeletedBBs.count(DelBB) != 0;
204 }
205 
206 // The DT and PDT require the nodes related to updates
207 // are not deleted when update functions are called.
208 // So BasicBlock deletions must be pended when the
209 // UpdateStrategy is Lazy. When the UpdateStrategy is
210 // Eager, the BasicBlock will be deleted immediately.
212  validateDeleteBB(DelBB);
213  if (Strategy == UpdateStrategy::Lazy) {
214  DeletedBBs.insert(DelBB);
215  return;
216  }
217 
218  DelBB->removeFromParent();
219  eraseDelBBNode(DelBB);
220  delete DelBB;
221 }
222 
224  BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
225  validateDeleteBB(DelBB);
226  if (Strategy == UpdateStrategy::Lazy) {
227  Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
228  DeletedBBs.insert(DelBB);
229  return;
230  }
231 
232  DelBB->removeFromParent();
233  eraseDelBBNode(DelBB);
234  Callback(DelBB);
235  delete DelBB;
236 }
237 
238 void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
239  if (DT && !IsRecalculatingDomTree)
240  if (DT->getNode(DelBB))
241  DT->eraseNode(DelBB);
242 
243  if (PDT && !IsRecalculatingPostDomTree)
244  if (PDT->getNode(DelBB))
245  PDT->eraseNode(DelBB);
246 }
247 
248 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
249  assert(DelBB && "Invalid push_back of nullptr DelBB.");
250  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
251  // DelBB is unreachable and all its instructions are dead.
252  while (!DelBB->empty()) {
253  Instruction &I = DelBB->back();
254  // Replace used instructions with an arbitrary value (undef).
255  if (!I.use_empty())
257  DelBB->getInstList().pop_back();
258  }
259  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
260  // Child of Function F it must contain valid IR.
261  new UnreachableInst(DelBB->getContext(), DelBB);
262 }
263 
265  bool ForceRemoveDuplicates) {
266  if (!DT && !PDT)
267  return;
268 
269  if (Strategy == UpdateStrategy::Lazy || ForceRemoveDuplicates) {
271  for (const auto U : Updates)
272  // For Lazy UpdateStrategy, avoid duplicates to applyLazyUpdate() to save
273  // on analysis.
274  if (llvm::none_of(
275  Seen,
276  [U](const DominatorTree::UpdateType S) { return S == U; }) &&
277  isUpdateValid(U) && !isSelfDominance(U)) {
278  Seen.push_back(U);
279  if (Strategy == UpdateStrategy::Lazy)
280  applyLazyUpdate(U.getKind(), U.getFrom(), U.getTo());
281  }
282  if (Strategy == UpdateStrategy::Lazy)
283  return;
284 
285  if (DT)
286  DT->applyUpdates(Seen);
287  if (PDT)
288  PDT->applyUpdates(Seen);
289  return;
290  }
291 
292  if (DT)
293  DT->applyUpdates(Updates);
294  if (PDT)
295  PDT->applyUpdates(Updates);
296 }
297 
299  assert(DT && "Invalid acquisition of a null DomTree");
300  applyDomTreeUpdates();
301  dropOutOfDateUpdates();
302  return *DT;
303 }
304 
306  assert(PDT && "Invalid acquisition of a null PostDomTree");
307  applyPostDomTreeUpdates();
308  dropOutOfDateUpdates();
309  return *PDT;
310 }
311 
313 
314 #ifndef NDEBUG
315  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
316  "Inserted edge does not appear in the CFG");
317 #endif
318 
319  if (!DT && !PDT)
320  return;
321 
322  // Won't affect DomTree and PostDomTree; discard update.
323  if (From == To)
324  return;
325 
326  if (Strategy == UpdateStrategy::Eager) {
327  if (DT)
328  DT->insertEdge(From, To);
329  if (PDT)
330  PDT->insertEdge(From, To);
331  return;
332  }
333 
334  applyLazyUpdate(DominatorTree::Insert, From, To);
335 }
336 
338  if (From == To)
339  return;
340 
341  if (!DT && !PDT)
342  return;
343 
344  if (!isUpdateValid({DominatorTree::Insert, From, To}))
345  return;
346 
347  if (Strategy == UpdateStrategy::Eager) {
348  if (DT)
349  DT->insertEdge(From, To);
350  if (PDT)
351  PDT->insertEdge(From, To);
352  return;
353  }
354 
355  applyLazyUpdate(DominatorTree::Insert, From, To);
356 }
357 
359 
360 #ifndef NDEBUG
361  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
362  "Deleted edge still exists in the CFG!");
363 #endif
364 
365  if (!DT && !PDT)
366  return;
367 
368  // Won't affect DomTree and PostDomTree; discard update.
369  if (From == To)
370  return;
371 
372  if (Strategy == UpdateStrategy::Eager) {
373  if (DT)
374  DT->deleteEdge(From, To);
375  if (PDT)
376  PDT->deleteEdge(From, To);
377  return;
378  }
379 
380  applyLazyUpdate(DominatorTree::Delete, From, To);
381 }
382 
384  if (From == To)
385  return;
386 
387  if (!DT && !PDT)
388  return;
389 
390  if (!isUpdateValid({DominatorTree::Delete, From, To}))
391  return;
392 
393  if (Strategy == UpdateStrategy::Eager) {
394  if (DT)
395  DT->deleteEdge(From, To);
396  if (PDT)
397  PDT->deleteEdge(From, To);
398  return;
399  }
400 
401  applyLazyUpdate(DominatorTree::Delete, From, To);
402 }
403 
404 void DomTreeUpdater::dropOutOfDateUpdates() {
406  return;
407 
408  tryFlushDeletedBB();
409 
410  // Drop all updates applied by both trees.
411  if (!DT)
412  PendDTUpdateIndex = PendUpdates.size();
413  if (!PDT)
414  PendPDTUpdateIndex = PendUpdates.size();
415 
416  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
417  const auto B = PendUpdates.begin();
418  const auto E = PendUpdates.begin() + dropIndex;
419  assert(B <= E && "Iterator out of range.");
420  PendUpdates.erase(B, E);
421  // Calculate current index.
422  PendDTUpdateIndex -= dropIndex;
423  PendPDTUpdateIndex -= dropIndex;
424 }
425 
426 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
428  raw_ostream &OS = llvm::dbgs();
429 
430  OS << "Available Trees: ";
431  if (DT || PDT) {
432  if (DT)
433  OS << "DomTree ";
434  if (PDT)
435  OS << "PostDomTree ";
436  OS << "\n";
437  } else
438  OS << "None\n";
439 
440  OS << "UpdateStrategy: ";
441  if (Strategy == UpdateStrategy::Eager) {
442  OS << "Eager\n";
443  return;
444  } else
445  OS << "Lazy\n";
446  int Index = 0;
447 
448  auto printUpdates =
451  if (begin == end)
452  OS << " None\n";
453  Index = 0;
454  for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
455  auto U = *It;
456  OS << " " << Index << " : ";
457  ++Index;
458  if (U.getKind() == DominatorTree::Insert)
459  OS << "Insert, ";
460  else
461  OS << "Delete, ";
462  BasicBlock *From = U.getFrom();
463  if (From) {
464  auto S = From->getName();
465  if (!From->hasName())
466  S = "(no name)";
467  OS << S << "(" << From << "), ";
468  } else {
469  OS << "(badref), ";
470  }
471  BasicBlock *To = U.getTo();
472  if (To) {
473  auto S = To->getName();
474  if (!To->hasName())
475  S = "(no_name)";
476  OS << S << "(" << To << ")\n";
477  } else {
478  OS << "(badref)\n";
479  }
480  }
481  };
482 
483  if (DT) {
484  const auto I = PendUpdates.begin() + PendDTUpdateIndex;
485  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
486  "Iterator out of range.");
487  OS << "Applied but not cleared DomTreeUpdates:\n";
488  printUpdates(PendUpdates.begin(), I);
489  OS << "Pending DomTreeUpdates:\n";
490  printUpdates(I, PendUpdates.end());
491  }
492 
493  if (PDT) {
494  const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
495  assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
496  "Iterator out of range.");
497  OS << "Applied but not cleared PostDomTreeUpdates:\n";
498  printUpdates(PendUpdates.begin(), I);
499  OS << "Pending PostDomTreeUpdates:\n";
500  printUpdates(I, PendUpdates.end());
501  }
502 
503  OS << "Pending DeletedBBs:\n";
504  Index = 0;
505  for (auto BB : DeletedBBs) {
506  OS << " " << Index << " : ";
507  ++Index;
508  if (BB->hasName())
509  OS << BB->getName() << "(";
510  else
511  OS << "(no_name)(";
512  OS << BB << ")\n";
513  }
514 
515  OS << "Pending Callbacks:\n";
516  Index = 0;
517  for (auto BB : Callbacks) {
518  OS << " " << Index << " : ";
519  ++Index;
520  if (BB->hasName())
521  OS << BB->getName() << "(";
522  else
523  OS << "(no_name)(";
524  OS << BB << ")\n";
525  }
526 }
527 #endif
528 } // namespace llvm
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:258
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:249
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:464
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)
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.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1199
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:428
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")
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
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:1414
iterator erase(const_iterator CI)
Definition: SmallVector.h:437
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.
void deleteEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge deletion.
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
void insertEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge insertion.
void removeFromParent()
Unlink &#39;this&#39; from the containing function, but do not delete it.
Definition: BasicBlock.cpp:110
BlockVerifier::State From
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending...
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates, bool ForceRemoveDuplicates=false)
Apply updates on all available trees.
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 deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge deletion.
void recalculate(Function &F)
Recalculate all available trees and flush all BasicBlocks awaiting deletion immediately.
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:213
#define I(x, y, z)
Definition: MD5.cpp:58
void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge insertion.
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.
const unsigned Kind
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:317
bool use_empty() const
Definition: Value.h:322