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/IR/CFG.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/PassManager.h"
25 #include "llvm/Support/Debug.h"
28 #include <algorithm>
29 using namespace llvm;
30 
31 bool llvm::VerifyDomInfo = false;
34  cl::desc("Verify dominator info (time consuming)"));
35 
36 #ifdef EXPENSIVE_CHECKS
37 static constexpr bool ExpensiveChecksEnabled = true;
38 #else
39 static constexpr bool ExpensiveChecksEnabled = false;
40 #endif
41 
43  const TerminatorInst *TI = Start->getTerminator();
44  unsigned NumEdgesToEnd = 0;
45  for (unsigned int i = 0, n = TI->getNumSuccessors(); i < n; ++i) {
46  if (TI->getSuccessor(i) == End)
47  ++NumEdgesToEnd;
48  if (NumEdgesToEnd >= 2)
49  return false;
50  }
51  assert(NumEdgesToEnd == 1);
52  return true;
53 }
54 
55 //===----------------------------------------------------------------------===//
56 // DominatorTree Implementation
57 //===----------------------------------------------------------------------===//
58 //
59 // Provide public access to DominatorTree information. Implementation details
60 // can be found in Dominators.h, GenericDomTree.h, and
61 // GenericDomTreeConstruction.h.
62 //
63 //===----------------------------------------------------------------------===//
64 
66 template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase
67 template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase
68 
70 
71 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree>(
73 template void llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree>(
75 
76 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>(
78 template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>(
80 
81 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>(
83 template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>(
85 
86 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBDomTree>(
88 template void llvm::DomTreeBuilder::ApplyUpdates<DomTreeBuilder::BBPostDomTree>(
90 
91 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>(
92  const DomTreeBuilder::BBDomTree &DT,
94 template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>(
97 
100  // Check whether the analysis, all analyses on functions, or the function's
101  // CFG have been preserved.
102  auto PAC = PA.getChecker<DominatorTreeAnalysis>();
103  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
104  PAC.preservedSet<CFGAnalyses>());
105 }
106 
107 // dominates - Return true if Def dominates a use in User. This performs
108 // the special checks necessary if Def and User are in the same basic block.
109 // Note that Def doesn't dominate a use in Def itself!
111  const Instruction *User) const {
112  const BasicBlock *UseBB = User->getParent();
113  const BasicBlock *DefBB = Def->getParent();
114 
115  // Any unreachable use is dominated, even if Def == User.
116  if (!isReachableFromEntry(UseBB))
117  return true;
118 
119  // Unreachable definitions don't dominate anything.
120  if (!isReachableFromEntry(DefBB))
121  return false;
122 
123  // An instruction doesn't dominate a use in itself.
124  if (Def == User)
125  return false;
126 
127  // The value defined by an invoke dominates an instruction only if it
128  // dominates every instruction in UseBB.
129  // A PHI is dominated only if the instruction dominates every possible use in
130  // the UseBB.
131  if (isa<InvokeInst>(Def) || isa<PHINode>(User))
132  return dominates(Def, UseBB);
133 
134  if (DefBB != UseBB)
135  return dominates(DefBB, UseBB);
136 
137  // Loop through the basic block until we find Def or User.
139  for (; &*I != Def && &*I != User; ++I)
140  /*empty*/;
141 
142  return &*I == Def;
143 }
144 
145 // true if Def would dominate a use in any instruction in UseBB.
146 // note that dominates(Def, Def->getParent()) is false.
148  const BasicBlock *UseBB) const {
149  const BasicBlock *DefBB = Def->getParent();
150 
151  // Any unreachable use is dominated, even if DefBB == UseBB.
152  if (!isReachableFromEntry(UseBB))
153  return true;
154 
155  // Unreachable definitions don't dominate anything.
156  if (!isReachableFromEntry(DefBB))
157  return false;
158 
159  if (DefBB == UseBB)
160  return false;
161 
162  // Invoke results are only usable in the normal destination, not in the
163  // exceptional destination.
164  if (const auto *II = dyn_cast<InvokeInst>(Def)) {
165  BasicBlock *NormalDest = II->getNormalDest();
166  BasicBlockEdge E(DefBB, NormalDest);
167  return dominates(E, UseBB);
168  }
169 
170  return dominates(DefBB, UseBB);
171 }
172 
174  const BasicBlock *UseBB) const {
175  // If the BB the edge ends in doesn't dominate the use BB, then the
176  // edge also doesn't.
177  const BasicBlock *Start = BBE.getStart();
178  const BasicBlock *End = BBE.getEnd();
179  if (!dominates(End, UseBB))
180  return false;
181 
182  // Simple case: if the end BB has a single predecessor, the fact that it
183  // dominates the use block implies that the edge also does.
184  if (End->getSinglePredecessor())
185  return true;
186 
187  // The normal edge from the invoke is critical. Conceptually, what we would
188  // like to do is split it and check if the new block dominates the use.
189  // With X being the new block, the graph would look like:
190  //
191  // DefBB
192  // /\ . .
193  // / \ . .
194  // / \ . .
195  // / \ | |
196  // A X B C
197  // | \ | /
198  // . \|/
199  // . NormalDest
200  // .
201  //
202  // Given the definition of dominance, NormalDest is dominated by X iff X
203  // dominates all of NormalDest's predecessors (X, B, C in the example). X
204  // trivially dominates itself, so we only have to find if it dominates the
205  // other predecessors. Since the only way out of X is via NormalDest, X can
206  // only properly dominate a node if NormalDest dominates that node too.
207  int IsDuplicateEdge = 0;
208  for (const_pred_iterator PI = pred_begin(End), E = pred_end(End);
209  PI != E; ++PI) {
210  const BasicBlock *BB = *PI;
211  if (BB == Start) {
212  // If there are multiple edges between Start and End, by definition they
213  // can't dominate anything.
214  if (IsDuplicateEdge++)
215  return false;
216  continue;
217  }
218 
219  if (!dominates(End, BB))
220  return false;
221  }
222  return true;
223 }
224 
225 bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const {
226  Instruction *UserInst = cast<Instruction>(U.getUser());
227  // A PHI in the end of the edge is dominated by it.
228  PHINode *PN = dyn_cast<PHINode>(UserInst);
229  if (PN && PN->getParent() == BBE.getEnd() &&
230  PN->getIncomingBlock(U) == BBE.getStart())
231  return true;
232 
233  // Otherwise use the edge-dominates-block query, which
234  // handles the crazy critical edge cases properly.
235  const BasicBlock *UseBB;
236  if (PN)
237  UseBB = PN->getIncomingBlock(U);
238  else
239  UseBB = UserInst->getParent();
240  return dominates(BBE, UseBB);
241 }
242 
243 bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
244  Instruction *UserInst = cast<Instruction>(U.getUser());
245  const BasicBlock *DefBB = Def->getParent();
246 
247  // Determine the block in which the use happens. PHI nodes use
248  // their operands on edges; simulate this by thinking of the use
249  // happening at the end of the predecessor block.
250  const BasicBlock *UseBB;
251  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
252  UseBB = PN->getIncomingBlock(U);
253  else
254  UseBB = UserInst->getParent();
255 
256  // Any unreachable use is dominated, even if Def == User.
257  if (!isReachableFromEntry(UseBB))
258  return true;
259 
260  // Unreachable definitions don't dominate anything.
261  if (!isReachableFromEntry(DefBB))
262  return false;
263 
264  // Invoke instructions define their return values on the edges to their normal
265  // successors, so we have to handle them specially.
266  // Among other things, this means they don't dominate anything in
267  // their own block, except possibly a phi, so we don't need to
268  // walk the block in any case.
269  if (const InvokeInst *II = dyn_cast<InvokeInst>(Def)) {
270  BasicBlock *NormalDest = II->getNormalDest();
271  BasicBlockEdge E(DefBB, NormalDest);
272  return dominates(E, U);
273  }
274 
275  // If the def and use are in different blocks, do a simple CFG dominator
276  // tree query.
277  if (DefBB != UseBB)
278  return dominates(DefBB, UseBB);
279 
280  // Ok, def and use are in the same block. If the def is an invoke, it
281  // doesn't dominate anything in the block. If it's a PHI, it dominates
282  // everything in the block.
283  if (isa<PHINode>(UserInst))
284  return true;
285 
286  // Otherwise, just loop through the basic block until we find Def or User.
287  BasicBlock::const_iterator I = DefBB->begin();
288  for (; &*I != Def && &*I != UserInst; ++I)
289  /*empty*/;
290 
291  return &*I != UserInst;
292 }
293 
296 
297  // ConstantExprs aren't really reachable from the entry block, but they
298  // don't need to be treated like unreachable code either.
299  if (!I) return true;
300 
301  // PHI nodes use their operands on their incoming edges.
302  if (PHINode *PN = dyn_cast<PHINode>(I))
303  return isReachableFromEntry(PN->getIncomingBlock(U));
304 
305  // Everything else uses their operands in their own block.
306  return isReachableFromEntry(I->getParent());
307 }
308 
309 //===----------------------------------------------------------------------===//
310 // DominatorTreeAnalysis and related pass implementations
311 //===----------------------------------------------------------------------===//
312 //
313 // This implements the DominatorTreeAnalysis which is used with the new pass
314 // manager. It also implements some methods from utility passes.
315 //
316 //===----------------------------------------------------------------------===//
317 
320  DominatorTree DT;
321  DT.recalculate(F);
322  return DT;
323 }
324 
325 AnalysisKey DominatorTreeAnalysis::Key;
326 
328 
331  OS << "DominatorTree for function: " << F.getName() << "\n";
333 
334  return PreservedAnalyses::all();
335 }
336 
339  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
340  assert(DT.verify());
341  (void)DT;
342  return PreservedAnalyses::all();
343 }
344 
345 //===----------------------------------------------------------------------===//
346 // DominatorTreeWrapperPass Implementation
347 //===----------------------------------------------------------------------===//
348 //
349 // The implementation details of the wrapper pass that holds a DominatorTree
350 // suitable for use with the legacy pass manager.
351 //
352 //===----------------------------------------------------------------------===//
353 
356  "Dominator Tree Construction", true, true)
357 
359  DT.recalculate(F);
360  return false;
361 }
362 
364  if (VerifyDomInfo)
366  else if (ExpensiveChecksEnabled)
368 }
369 
371  DT.print(OS);
372 }
373 
374 //===----------------------------------------------------------------------===//
375 // DeferredDominance Implementation
376 //===----------------------------------------------------------------------===//
377 //
378 // The implementation details of the DeferredDominance class which allows
379 // one to queue updates to a DominatorTree.
380 //
381 //===----------------------------------------------------------------------===//
382 
383 /// \brief Queues multiple updates and discards duplicates.
387  for (auto U : Updates)
388  // Avoid duplicates to applyUpdate() to save on analysis.
389  if (std::none_of(Seen.begin(), Seen.end(),
390  [U](DominatorTree::UpdateType S) { return S == U; })) {
391  Seen.push_back(U);
392  applyUpdate(U.getKind(), U.getFrom(), U.getTo());
393  }
394 }
395 
396 /// \brief Helper method for a single edge insertion. It's almost always better
397 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
398 /// This is best used when there is only a single insertion needed to update
399 /// Dominators.
401  applyUpdate(DominatorTree::Insert, From, To);
402 }
403 
404 /// \brief Helper method for a single edge deletion. It's almost always better
405 /// to batch updates and call applyUpdates to quickly remove duplicate edges.
406 /// This is best used when there is only a single deletion needed to update
407 /// Dominators.
409  applyUpdate(DominatorTree::Delete, From, To);
410 }
411 
412 /// \brief Delays the deletion of a basic block until a flush() event.
414  assert(DelBB && "Invalid push_back of nullptr DelBB.");
415  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
416  // DelBB is unreachable and all its instructions are dead.
417  while (!DelBB->empty()) {
418  Instruction &I = DelBB->back();
419  // Replace used instructions with an arbitrary value (undef).
420  if (!I.use_empty())
422  DelBB->getInstList().pop_back();
423  }
424  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
425  // Child of Function F it must contain valid IR.
426  new UnreachableInst(DelBB->getContext(), DelBB);
427  DeletedBBs.insert(DelBB);
428 }
429 
430 /// \brief Returns true if DelBB is awaiting deletion at a flush() event.
432  if (DeletedBBs.empty())
433  return false;
434  return DeletedBBs.count(DelBB) != 0;
435 }
436 
437 /// \brief Returns true if pending DT updates are queued for a flush() event.
438 bool DeferredDominance::pending() { return !PendUpdates.empty(); }
439 
440 /// \brief Flushes all pending updates and block deletions. Returns a
441 /// correct DominatorTree reference to be used by the caller for analysis.
443  // Updates to DT must happen before blocks are deleted below. Otherwise the
444  // DT traversal will encounter badref blocks and assert.
445  if (!PendUpdates.empty()) {
446  DT.applyUpdates(PendUpdates);
447  PendUpdates.clear();
448  }
449  flushDelBB();
450  return DT;
451 }
452 
453 /// \brief Drops all internal state and forces a (slow) recalculation of the
454 /// DominatorTree based on the current state of the LLVM IR in F. This should
455 /// only be used in corner cases such as the Entry block of F being deleted.
457  // flushDelBB must be flushed before the recalculation. The state of the IR
458  // must be consistent before the DT traversal algorithm determines the
459  // actual DT.
460  if (flushDelBB() || !PendUpdates.empty()) {
461  DT.recalculate(F);
462  PendUpdates.clear();
463  }
464 }
465 
466 /// \brief Debug method to help view the state of pending updates.
467 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
469  raw_ostream &OS = llvm::dbgs();
470  OS << "PendUpdates:\n";
471  int I = 0;
472  for (auto U : PendUpdates) {
473  OS << " " << I << " : ";
474  ++I;
475  if (U.getKind() == DominatorTree::Insert)
476  OS << "Insert, ";
477  else
478  OS << "Delete, ";
479  BasicBlock *From = U.getFrom();
480  if (From) {
481  auto S = From->getName();
482  if (!From->hasName())
483  S = "(no name)";
484  OS << S << "(" << From << "), ";
485  } else {
486  OS << "(badref), ";
487  }
488  BasicBlock *To = U.getTo();
489  if (To) {
490  auto S = To->getName();
491  if (!To->hasName())
492  S = "(no_name)";
493  OS << S << "(" << To << ")\n";
494  } else {
495  OS << "(badref)\n";
496  }
497  }
498  OS << "DeletedBBs:\n";
499  I = 0;
500  for (auto BB : DeletedBBs) {
501  OS << " " << I << " : ";
502  ++I;
503  if (BB->hasName())
504  OS << BB->getName() << "(";
505  else
506  OS << "(no_name)(";
507  OS << BB << ")\n";
508  }
509 }
510 #endif
511 
512 /// Apply an update (Kind, From, To) to the internal queued updates. The
513 /// update is only added when determined to be necessary. Checks for
514 /// self-domination, unnecessary updates, duplicate requests, and balanced
515 /// pairs of requests are all performed. Returns true if the update is
516 /// queued and false if it is discarded.
517 bool DeferredDominance::applyUpdate(DominatorTree::UpdateKind Kind,
518  BasicBlock *From, BasicBlock *To) {
519  if (From == To)
520  return false; // Cannot dominate self; discard update.
521 
522  // Discard updates by inspecting the current state of successors of From.
523  // Since applyUpdate() must be called *after* the Terminator of From is
524  // altered we can determine if the update is unnecessary.
525  bool HasEdge = std::any_of(succ_begin(From), succ_end(From),
526  [To](BasicBlock *B) { return B == To; });
527  if (Kind == DominatorTree::Insert && !HasEdge)
528  return false; // Unnecessary Insert: edge does not exist in IR.
529  if (Kind == DominatorTree::Delete && HasEdge)
530  return false; // Unnecessary Delete: edge still exists in IR.
531 
532  // Analyze pending updates to determine if the update is unnecessary.
533  DominatorTree::UpdateType Update = {Kind, From, To};
537  From, To};
538  for (auto I = PendUpdates.begin(), E = PendUpdates.end(); I != E; ++I) {
539  if (Update == *I)
540  return false; // Discard duplicate updates.
541  if (Invert == *I) {
542  // Update and Invert are both valid (equivalent to a no-op). Remove
543  // Invert from PendUpdates and discard the Update.
544  PendUpdates.erase(I);
545  return false;
546  }
547  }
548  PendUpdates.push_back(Update); // Save the valid update.
549  return true;
550 }
551 
552 /// Performs all pending basic block deletions. We have to defer the deletion
553 /// of these blocks until after the DominatorTree updates are applied. The
554 /// internal workings of the DominatorTree code expect every update's From
555 /// and To blocks to exist and to be a member of the same Function.
556 bool DeferredDominance::flushDelBB() {
557  if (DeletedBBs.empty())
558  return false;
559  for (auto *BB : DeletedBBs)
560  BB->eraseFromParent();
561  DeletedBBs.clear();
562  return true;
563 }
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
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:39
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:294
void insertEdge(BasicBlock *From, BasicBlock *To)
Helper method for a single edge insertion.
Definition: Dominators.cpp:400
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:42
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:363
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:431
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:860
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
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:468
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:413
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:327
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:442
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:384
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:408
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:318
This function has undefined behavior.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
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:853
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:31
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:107
INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", "Dominator Tree Construction", true, true) bool DominatorTreeWrapperPass
Definition: Dominators.cpp:355
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1382
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:862
bool dominates(const Instruction *Def, const Use &U) const
Return true if Def dominates a use in User.
Definition: Dominators.cpp:243
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
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:370
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: Dominators.cpp:98
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
void clear()
Definition: ilist.h:322
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:438
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:456
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:329
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
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:331
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:328
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:422
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Dominators.cpp:337
const BasicBlock * getParent() const
Definition: Instruction.h:67