LLVM  7.0.0svn
Dominators.cpp
Go to the documentation of this file.
1 //===- Dominators.cpp - Dominator Calculation -----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements simple dominator construction algorithms for finding
11 // forward dominators. Postdominators are available in libanalysis, but are not
12 // included in libvmcore, because it's not needed. Forward dominators are
13 // needed to support the Verifier pass.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/IR/Dominators.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/Config/llvm-config.h"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/PassManager.h"
26 #include "llvm/Support/Debug.h"
29 #include <algorithm>
30 using namespace llvm;
31 
32 bool llvm::VerifyDomInfo = false;
35  cl::desc("Verify dominator info (time consuming)"));
36 
37 #ifdef EXPENSIVE_CHECKS
38 static constexpr bool ExpensiveChecksEnabled = true;
39 #else
40 static constexpr bool ExpensiveChecksEnabled = false;
41 #endif
42 
44  const TerminatorInst *TI = Start->getTerminator();
45  unsigned NumEdgesToEnd = 0;
46  for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
47  if (TI->getSuccessor(i) == End)
48  ++NumEdgesToEnd;
49  if (NumEdgesToEnd >= 2)
50  return false;
51  }
52  assert(NumEdgesToEnd == 1);
53  return true;
54 }
55 
56 //===----------------------------------------------------------------------===//
57 // DominatorTree Implementation
58 //===----------------------------------------------------------------------===//
59 //
60 // Provide public access to DominatorTree information. Implementation details
61 // can be found in Dominators.h, GenericDomTree.h, and
62 // GenericDomTreeConstruction.h.
63 //
64 //===----------------------------------------------------------------------===//
65 
67 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
68 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
69 
71 
72 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
74 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
76 
77 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
79 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
81 
82 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
84 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
86 
87 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
89 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
91 
92 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
93  const DomTreeBuilder::BBDomTree &DT,
95 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
98 
101  // Check whether the analysis, all analyses on functions, or the function's
102  // CFG have been preserved.
103  auto PAC = PA.getChecker<DominatorTreeAnalysis>();
104  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
105  PAC.preservedSet<CFGAnalyses>());
106 }
107 
108 // dominates - Return true if Def dominates a use in User. This performs
109 // the special checks necessary if Def and User are in the same basic block.
110 // Note that Def doesn't dominate a use in Def itself!
112  const Instruction *User) const {
113  const BasicBlock *UseBB = User->getParent();
114  const BasicBlock *DefBB = Def->getParent();
115 
116  // Any unreachable use is dominated, even if Def == User.
117  if (!isReachableFromEntry(UseBB))
118  return true;
119 
120  // Unreachable definitions don't dominate anything.
121  if (!isReachableFromEntry(DefBB))
122  return false;
123 
124  // An instruction doesn't dominate a use in itself.
125  if (Def == User)
126  return false;
127 
128  // The value defined by an invoke dominates an instruction only if it
129  // dominates every instruction in UseBB.
130  // A PHI is dominated only if the instruction dominates every possible use in
131  // the UseBB.
132  if (isa<InvokeInst>(Def) || isa<PHINode>(User))
133  return dominates(Def, UseBB);
134 
135  if (DefBB != UseBB)
136  return dominates(DefBB, UseBB);
137 
138  // Loop through the basic block until we find Def or User.
140  for (; &*I != Def && &*I != User; ++I)
141  /*empty*/;
142 
143  return &*I == Def;
144 }
145 
146 // true if Def would dominate a use in any instruction in UseBB.
147 // note that dominates(Def, Def->getParent()) is false.
149  const BasicBlock *UseBB) const {
150  const BasicBlock *DefBB = Def->getParent();
151 
152  // Any unreachable use is dominated, even if DefBB == UseBB.
153  if (!isReachableFromEntry(UseBB))
154  return true;
155 
156  // Unreachable definitions don't dominate anything.
157  if (!isReachableFromEntry(DefBB))
158  return false;
159 
160  if (DefBB == UseBB)
161  return false;
162 
163  // Invoke results are only usable in the normal destination, not in the
164  // exceptional destination.
165  if (const auto *II = dyn_cast<InvokeInst>(Def)) {
166  BasicBlock *NormalDest = II->getNormalDest();
167  BasicBlockEdge E(DefBB, NormalDest);
168  return dominates(E, UseBB);
169  }
170 
171  return dominates(DefBB, UseBB);
172 }
173 
175  const BasicBlock *UseBB) const {
176  // If the BB the edge ends in doesn't dominate the use BB, then the
177  // edge also doesn't.
178  const BasicBlock *Start = BBE.getStart();
179  const BasicBlock *End = BBE.getEnd();
180  if (!dominates(End, UseBB))
181  return false;
182 
183  // Simple case: if the end BB has a single predecessor, the fact that it
184  // dominates the use block implies that the edge also does.
185  if (End->getSinglePredecessor())
186  return true;
187 
188  // The normal edge from the invoke is critical. Conceptually, what we would
189  // like to do is split it and check if the new block dominates the use.
190  // With X being the new block, the graph would look like:
191  //
192  // DefBB
193  // /\ . .
194  // / \ . .
195  // / \ . .
196  // / \ | |
197  // A X B C
198  // | \ | /
199  // . \|/
200  // . NormalDest
201  // .
202  //
203  // Given the definition of dominance, NormalDest is dominated by X iff X
204  // dominates all of NormalDest's predecessors (X, B, C in the example). X
205  // trivially dominates itself, so we only have to find if it dominates the
206  // other predecessors. Since the only way out of X is via NormalDest, X can
207  // only properly dominate a node if NormalDest dominates that node too.
208  int IsDuplicateEdge = 0;
209  for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
210  PI != E; ++PI) {
211  const BasicBlock *BB = *PI;
212  if (BB == Start) {
213  // If there are multiple edges between Start and End, by definition they
214  // can't dominate anything.
215  if (IsDuplicateEdge++)
216  return false;
217  continue;
218  }
219 
220  if (!dominates(End, BB))
221  return false;
222  }
223  return true;
224 }
225 
226 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
227  Instruction *UserInst = cast<Instruction>(U.getUser());
228  // A PHI in the end of the edge is dominated by it.
229  PHINode *PN = dyn_cast<PHINode>(UserInst);
230  if (PN && PN->getParent() == BBE.getEnd() &&
231  PN->getIncomingBlock(U) == BBE.getStart())
232  return true;
233 
234  // Otherwise use the edge-dominates-block query, which
235  // handles the crazy critical edge cases properly.
236  const BasicBlock *UseBB;
237  if (PN)
238  UseBB = PN->getIncomingBlock(U);
239  else
240  UseBB = UserInst->getParent();
241  return dominates(BBE, UseBB);
242 }
243 
244 bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
245  Instruction *UserInst = cast<Instruction>(U.getUser());
246  const BasicBlock *DefBB = Def->getParent();
247 
248  // Determine the block in which the use happens. PHI nodes use
249  // their operands on edges; simulate this by thinking of the use
250  // happening at the end of the predecessor block.
251  const BasicBlock *UseBB;
252  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
253  UseBB = PN->getIncomingBlock(U);
254  else
255  UseBB = UserInst->getParent();
256 
257  // Any unreachable use is dominated, even if Def == User.
258  if (!isReachableFromEntry(UseBB))
259  return true;
260 
261  // Unreachable definitions don't dominate anything.
262  if (!isReachableFromEntry(DefBB))
263  return false;
264 
265  // Invoke instructions define their return values on the edges to their normal
266  // successors, so we have to handle them specially.
267  // Among other things, this means they don't dominate anything in
268  // their own block, except possibly a phi, so we don't need to
269  // walk the block in any case.
270  if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
271  BasicBlock *NormalDest = II->getNormalDest();
272  BasicBlockEdge E(DefBB, NormalDest);
273  return dominates(E, U);
274  }
275 
276  // If the def and use are in different blocks, do a simple CFG dominator
277  // tree query.
278  if (DefBB != UseBB)
279  return dominates(DefBB, UseBB);
280 
281  // Ok, def and use are in the same block. If the def is an invoke, it
282  // doesn't dominate anything in the block. If it's a PHI, it dominates
283  // everything in the block.
284  if (isa<PHINode>(UserInst))
285  return true;
286 
287  // Otherwise, just loop through the basic block until we find Def or User.
288  BasicBlock::const_iterator I = DefBB->begin();
289  for (; &*I != Def && &*I != UserInst; ++I)
290  /*empty*/;
291 
292  return &*I != UserInst;
293 }
294 
297 
298  // ConstantExprs aren't really reachable from the entry block, but they
299  // don't need to be treated like unreachable code either.
300  if (!I) return true;
301 
302  // PHI nodes use their operands on their incoming edges.
303  if (PHINode *PN = dyn_cast<PHINode>(I))
304  return isReachableFromEntry(PN->getIncomingBlock(U));
305 
306  // Everything else uses their operands in their own block.
307  return isReachableFromEntry(I->getParent());
308 }
309 
310 //===----------------------------------------------------------------------===//
311 // DominatorTreeAnalysis and related pass implementations
312 //===----------------------------------------------------------------------===//
313 //
314 // This implements the DominatorTreeAnalysis which is used with the new pass
315 // manager. It also implements some methods from utility passes.
316 //
317 //===----------------------------------------------------------------------===//
318 
321  DominatorTree DT;
322  DT.recalculate(F);
323  return DT;
324 }
325 
326 AnalysisKey DominatorTreeAnalysis::Key;
327 
329 
332  OS << "DominatorTree for function: " << F.getName() << "\n";
334 
335  return PreservedAnalyses::all();
336 }
337 
340  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
341  assert(DT.verify());
342  (void)DT;
343  return PreservedAnalyses::all();
344 }
345 
346 //===----------------------------------------------------------------------===//
347 // DominatorTreeWrapperPass Implementation
348 //===----------------------------------------------------------------------===//
349 //
350 // The implementation details of the wrapper pass that holds a DominatorTree
351 // suitable for use with the legacy pass manager.
352 //
353 //===----------------------------------------------------------------------===//
354 
357  "Dominator Tree Construction", true, true)
358 
360  DT.recalculate(F);
361  return false;
362 }
363 
365  if (VerifyDomInfo)
367  else if (ExpensiveChecksEnabled)
369 }
370 
372  DT.print(OS);
373 }
374 
375 //===----------------------------------------------------------------------===//
376 // DeferredDominance Implementation
377 //===----------------------------------------------------------------------===//
378 //
379 // The implementation details of the DeferredDominance class which allows
380 // one to queue updates to a DominatorTree.
381 //
382 //===----------------------------------------------------------------------===//
383 
384 /// Queues multiple updates and discards duplicates.
388  for (auto U : Updates)
389  // Avoid duplicates to applyUpdate() to save on analysis.
390  if (std::none_of(Seen.begin(), Seen.end(),
391  [U](DominatorTree::UpdateType S) { return S == U; })) {
392  Seen.push_back(U);
393  applyUpdate(U.getKind(), U.getFrom(), U.getTo());
394  }
395 }
396 
397 /// Helper method for a single edge insertion. It's almost always better
398 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
399 /// This is best used when there is only a single insertion needed to update
400 /// Dominators.
402  applyUpdate(DominatorTree::Insert, From, To);
403 }
404 
405 /// Helper method for a single edge deletion. It's almost always better
406 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
407 /// This is best used when there is only a single deletion needed to update
408 /// Dominators.
410  applyUpdate(DominatorTree::Delete, From, To);
411 }
412 
413 /// Delays the deletion of a basic block until a flush() event.
415  assert(DelBB && "Invalid push_back of nullptr DelBB.");
416  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
417  // DelBB is unreachable and all its instructions are dead.
418  while (!DelBB->empty()) {
419  Instruction &I = DelBB->back();
420  // Replace used instructions with an arbitrary value (undef).
421  if (!I.use_empty())
423  DelBB->getInstList().pop_back();
424  }
425  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
426  // Child of Function F it must contain valid IR.
427  new UnreachableInst(DelBB->getContext(), DelBB);
428  DeletedBBs.insert(DelBB);
429 }
430 
431 /// Returns true if DelBB is awaiting deletion at a flush() event.
433  if (DeletedBBs.empty())
434  return false;
435  return DeletedBBs.count(DelBB) != 0;
436 }
437 
438 /// Returns true if pending DT updates are queued for a flush() event.
439 bool DeferredDominance::pending() { return !PendUpdates.empty(); }
440 
441 /// Flushes all pending updates and block deletions. Returns a
442 /// correct DominatorTree reference to be used by the caller for analysis.
444  // Updates to DT must happen before blocks are deleted below. Otherwise the
445  // DT traversal will encounter badref blocks and assert.
446  if (!PendUpdates.empty()) {
447  DT.applyUpdates(PendUpdates);
448  PendUpdates.clear();
449  }
450  flushDelBB();
451  return DT;
452 }
453 
454 /// Drops all internal state and forces a (slow) recalculation of the
455 /// DominatorTree based on the current state of the LLVM IR in F. This should
456 /// only be used in corner cases such as the Entry block of F being deleted.
458  // flushDelBB must be flushed before the recalculation. The state of the IR
459  // must be consistent before the DT traversal algorithm determines the
460  // actual DT.
461  if (flushDelBB() || !PendUpdates.empty()) {
462  DT.recalculate(F);
463  PendUpdates.clear();
464  }
465 }
466 
467 /// Debug method to help view the state of pending updates.
468 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
470  raw_ostream &OS = llvm::dbgs();
471  OS << "PendUpdates:\n";
472  int I = 0;
473  for (auto U : PendUpdates) {
474  OS << " " << I << " : ";
475  ++I;
476  if (U.getKind() == DominatorTree::Insert)
477  OS << "Insert, ";
478  else
479  OS << "Delete, ";
480  BasicBlock *From = U.getFrom();
481  if (From) {
482  auto S = From->getName();
483  if (!From->hasName())
484  S = "(no name)";
485  OS << S << "(" << From << "), ";
486  } else {
487  OS << "(badref), ";
488  }
489  BasicBlock *To = U.getTo();
490  if (To) {
491  auto S = To->getName();
492  if (!To->hasName())
493  S = "(no_name)";
494  OS << S << "(" << To << ")\n";
495  } else {
496  OS << "(badref)\n";
497  }
498  }
499  OS << "DeletedBBs:\n";
500  I = 0;
501  for (auto BB : DeletedBBs) {
502  OS << " " << I << " : ";
503  ++I;
504  if (BB->hasName())
505  OS << BB->getName() << "(";
506  else
507  OS << "(no_name)(";
508  OS << BB << ")\n";
509  }
510 }
511 #endif
512 
513 /// Apply an update (Kind, From, To) to the internal queued updates. The
514 /// update is only added when determined to be necessary. Checks for
515 /// self-domination, unnecessary updates, duplicate requests, and balanced
516 /// pairs of requests are all performed. Returns true if the update is
517 /// queued and false if it is discarded.
518 bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
519  BasicBlock *From, BasicBlock *To) {
520  if (From == To)
521  return false; // Cannot dominate self; discard update.
522 
523  // Discard updates by inspecting the current state of successors of From.
524  // Since applyUpdate() must be called *after* the Terminator of From is
525  // altered we can determine if the update is unnecessary.
526  bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
527  [To](BasicBlock *B) { return B == To; });
528  if (Kind == DominatorTree::Insert && !HasEdge)
529  return false; // Unnecessary Insert: edge does not exist in IR.
530  if (Kind == DominatorTree::Delete && HasEdge)
531  return false; // Unnecessary Delete: edge still exists in IR.
532 
533  // Analyze pending updates to determine if the update is unnecessary.
534  DominatorTree::UpdateType Update = {Kind, From, To};
538  From, To};
539  for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
540  if (Update == *I)
541  return false; // Discard duplicate updates.
542  if (Invert == *I) {
543  // Update and Invert are both valid (equivalent to a no-op). Remove
544  // Invert from PendUpdates and discard the Update.
545  PendUpdates.erase(I);
546  return false;
547  }
548  }
549  PendUpdates.push_back(Update); // Save the valid update.
550  return true;
551 }
552 
553 /// Performs all pending basic block deletions. We have to defer the deletion
554 /// of these blocks until after the DominatorTree updates are applied. The
555 /// internal workings of the DominatorTree code expect every update's From
556 /// and To blocks to exist and to be a member of the same Function.
557 bool DeferredDominance::flushDelBB() {
558  if (DeletedBBs.empty())
559  return false;
560  for (auto *BB : DeletedBBs)
561  BB->eraseFromParent();
562  DeletedBBs.clear();
563  return true;
564 }
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:452
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
BasicBlock * getSuccessor(unsigned idx) const
Return the specified successor.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
static constexpr bool ExpensiveChecksEnabled
Definition: Dominators.cpp:40
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:225
F(f)
const BasicBlock * getEnd() const
Definition: Dominators.h:92
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:295
void insertEdge(BasicBlock *From, BasicBlock *To)
Helper method for a single edge insertion.
Definition: Dominators.cpp:401
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
bool isSingleEdge() const
Check if this is the only edge between Start and End.
Definition: Dominators.cpp:43
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: Dominators.cpp:364
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
bool pendingDeletedBB(BasicBlock *DelBB)
Returns true if DelBB is awaiting deletion at a flush() event.
Definition: Dominators.cpp:432
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:922
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
bool empty() const
Definition: BasicBlock.h:275
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
LLVM_DUMP_METHOD void dump() const
Debug method to help view the state of pending updates.
Definition: Dominators.cpp:469
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
void deleteBB(BasicBlock *DelBB)
Delays the deletion of a basic block until a flush() event.
Definition: Dominators.cpp:414
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
DominatorTreePrinterPass(raw_ostream &OS)
Definition: Dominators.cpp:328
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
DominatorTree & flush()
Flushes all pending updates and block deletions.
Definition: Dominators.cpp:443
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Queues multiple updates and discards duplicates.
Definition: Dominators.cpp:385
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
static bool runOnFunction(Function &F, bool PostInlining)
void deleteEdge(BasicBlock *From, BasicBlock *To)
Helper method for a single edge deletion.
Definition: Dominators.cpp:409
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:235
bool hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
DominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a dominator tree.
Definition: Dominators.cpp:319
This function has undefined behavior.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:117
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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
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:915
const Instruction & back() const
Definition: BasicBlock.h:278
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:32
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:107
INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", "Dominator Tree Construction", true, true) bool DominatorTreeWrapperPass
Definition: Dominators.cpp:356
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
ArrayRef< Update< BasicBlock * > > BBUpdates
Definition: Dominators.h:46
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:329
Iterator for intrusive lists based on ilist_node.
Generic dominator tree construction - This file provides routines to construct immediate dominator in...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:861
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:244
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
static cl::opt< bool, true > VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), cl::Hidden, cl::desc("Verify dominator info (time consuming)"))
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition: Dominators.cpp:371
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: Dominators.cpp:99
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:121
void clear()
Definition: ilist.h:309
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:115
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
bool pending()
Returns true if pending DT updates are queued for a flush() event.
Definition: Dominators.cpp:439
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
void recalculate(Function &F)
Drops all internal state and forces a (slow) recalculation of the DominatorTree based on the current ...
Definition: Dominators.cpp:457
const unsigned Kind
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
const BasicBlock * getStart() const
Definition: Dominators.h:88
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:330
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
Invoke instruction.
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:254
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
This header defines various interfaces for pass management in LLVM.
void pop_back()
Definition: ilist.h:318
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
bool use_empty() const
Definition: Value.h:322
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:426
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:338
const BasicBlock * getParent() const
Definition: Instruction.h:67