Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree. More...
#include "llvm/IR/Dominators.h"
Public Types | |
| using | Base = DominatorTreeBase< BasicBlock, false > |
 Public Types inherited from llvm::DominatorTreeBase< BasicBlock, false > | |
| enum | VerificationLevel |
| using | NodeType = BasicBlock |
| using | NodePtr = BasicBlock * |
| using | ParentPtr = decltype(std::declval< BasicBlock * >() ->getParent()) |
| using | ParentType = std::remove_pointer_t< ParentPtr > |
| using | UpdateType = cfg::Update< NodePtr > |
| using | UpdateKind = cfg::UpdateKind |
| using | root_iterator = typename SmallVectorImpl< BasicBlock * >::iterator |
| Iteration over roots. More... | |
| using | const_root_iterator = typename SmallVectorImpl< BasicBlock * >::const_iterator |
Public Member Functions | |
| DominatorTree ()=default | |
| DominatorTree (Function &F) | |
| DominatorTree (DominatorTree &DT, DomTreeBuilder::BBUpdates U) | |
| bool | invalidate (Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &) |
| Handle invalidation explicitly. More... | |
| bool | dominates (const BasicBlock *BB, const Use &U) const |
| Return true if the (end of the) basic block BB dominates the use U. More... | |
| bool | dominates (const Value *Def, const Use &U) const |
| Return true if value Def dominates use U, in the sense that Def is available at U, and could be substituted as the used value without violating the SSA dominance requirement. More... | |
| bool | dominates (const Value *Def, const Instruction *User) const |
| Return true if value Def dominates all possible uses inside instruction User. More... | |
| bool | dominates (const Instruction *Def, const BasicBlock *BB) const |
| bool | dominates (const BasicBlockEdge &BBE, const Use &U) const |
| Return true if an edge dominates a use. More... | |
| bool | dominates (const BasicBlockEdge &BBE, const BasicBlock *BB) const |
| bool | dominates (const BasicBlockEdge &BBE1, const BasicBlockEdge &BBE2) const |
Returns true if edge BBE1 dominates edge BBE2. More... | |
| bool | isReachableFromEntry (const Use &U) const |
| Provide an overload for a Use. More... | |
| void | viewGraph (const Twine &Name, const Twine &Title) |
| void | viewGraph () |
| Public Member Functions inherited from llvm::DominatorTreeBase< BasicBlock, false > | |
| DominatorTreeBase () | |
| DominatorTreeBase (DominatorTreeBase &&Arg) | |
| DominatorTreeBase (const DominatorTreeBase &)=delete | |
| DominatorTreeBase & | operator= (DominatorTreeBase &&RHS) |
| DominatorTreeBase & | operator= (const DominatorTreeBase &)=delete |
| root_iterator | root_begin () |
| const_root_iterator | root_begin () const |
| root_iterator | root_end () |
| const_root_iterator | root_end () const |
| size_t | root_size () const |
| iterator_range< root_iterator > | roots () |
| iterator_range< const_root_iterator > | roots () const |
| bool | isPostDominator () const |
| isPostDominator - Returns true if analysis based of postdoms More... | |
| bool | compare (const DominatorTreeBase &Other) const |
| compare - Return false if the other dominator tree base matches this dominator tree base. More... | |
| DomTreeNodeBase< BasicBlock > * | getNode (const BasicBlock *BB) const |
| getNode - return the (Post)DominatorTree node for the specified basic block. More... | |
| DomTreeNodeBase< BasicBlock > * | operator[] (const BasicBlock *BB) const |
| See getNode. More... | |
| DomTreeNodeBase< BasicBlock > * | getRootNode () |
| getRootNode - This returns the entry node for the CFG of the function. More... | |
| const DomTreeNodeBase< BasicBlock > * | getRootNode () const |
| void | getDescendants (BasicBlock *R, SmallVectorImpl< BasicBlock * > &Result) const |
| Get all nodes dominated by R, including R itself. More... | |
| bool | properlyDominates (const DomTreeNodeBase< BasicBlock > *A, const DomTreeNodeBase< BasicBlock > *B) const |
| properlyDominates - Returns true iff A dominates B and A != B. More... | |
| bool | properlyDominates (const BasicBlock *A, const BasicBlock *B) const |
| bool | isReachableFromEntry (const BasicBlock *A) const |
| isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it. More... | |
| bool | isReachableFromEntry (const DomTreeNodeBase< BasicBlock > *A) const |
| bool | dominates (const DomTreeNodeBase< BasicBlock > *A, const DomTreeNodeBase< BasicBlock > *B) const |
| dominates - Returns true iff A dominates B. More... | |
| bool | dominates (const BasicBlock *A, const BasicBlock *B) const |
| BasicBlock * | getRoot () const |
| BasicBlock * | findNearestCommonDominator (BasicBlock *A, BasicBlock *B) const |
| Find nearest common dominator basic block for basic block A and B. More... | |
| const BasicBlock * | findNearestCommonDominator (const BasicBlock *A, const BasicBlock *B) const |
| bool | isVirtualRoot (const DomTreeNodeBase< BasicBlock > *A) const |
| void | applyUpdates (ArrayRef< UpdateType > Updates) |
| Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch update on the tree. More... | |
| void | applyUpdates (ArrayRef< UpdateType > Updates, ArrayRef< UpdateType > PostViewUpdates) |
| void | insertEdge (BasicBlock *From, BasicBlock *To) |
| Inform the dominator tree about a CFG edge insertion and update the tree. More... | |
| void | deleteEdge (BasicBlock *From, BasicBlock *To) |
| Inform the dominator tree about a CFG edge deletion and update the tree. More... | |
| DomTreeNodeBase< BasicBlock > * | addNewBlock (BasicBlock *BB, BasicBlock *DomBB) |
| Add a new node to the dominator tree information. More... | |
| DomTreeNodeBase< BasicBlock > * | setNewRoot (BasicBlock *BB) |
| Add a new node to the forward dominator tree and make it a new root. More... | |
| void | changeImmediateDominator (DomTreeNodeBase< BasicBlock > *N, DomTreeNodeBase< BasicBlock > *NewIDom) |
| changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes. More... | |
| void | changeImmediateDominator (BasicBlock *BB, BasicBlock *NewBB) |
| void | eraseNode (BasicBlock *BB) |
| eraseNode - Removes a node from the dominator tree. More... | |
| void | splitBlock (BasicBlock *NewBB) |
| splitBlock - BB is split and now it has one successor. More... | |
| void | print (raw_ostream &O) const |
| print - Convert to human readable form More... | |
| void | updateDFSNumbers () const |
| updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order. More... | |
| void | recalculate (ParentType &Func) |
| recalculate - compute a dominator tree for the given function More... | |
| void | recalculate (ParentType &Func, ArrayRef< UpdateType > Updates) |
| bool | verify (VerificationLevel VL=VerificationLevel::Full) const |
| verify - checks if the tree is correct. More... | |
| void | reset () |
Detailed Description
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: A block is said to be forward statically reachable if there is a path from the entry of the function to the block. A statically reachable block may become statically unreachable during optimization.
A forward unreachable block may appear in the dominator tree, or it may not. If it does, dominance queries will return results as if all reachable blocks dominate it. When asking for a Node corresponding to a potentially unreachable block, calling code must handle the case where the block was unreachable and the result of getNode() is nullptr.
Generally, a block known to be unreachable when the dominator tree is constructed will not be in the tree. One which becomes unreachable after the dominator tree is initially constructed may still exist in the tree, even if the tree is properly updated. Calling code should not rely on the preceding statements; this is stated only to assist human understanding.
Definition at line 151 of file Dominators.h.
Member Typedef Documentation
◆ Base
Definition at line 153 of file Dominators.h.
Constructor & Destructor Documentation
◆ DominatorTree() [1/3]
|
default |
◆ DominatorTree() [2/3]
|
inlineexplicit |
Definition at line 156 of file Dominators.h.
References F.
◆ DominatorTree() [3/3]
|
inlineexplicit |
Definition at line 157 of file Dominators.h.
References llvm::DominatorTreeBase< NodeT, IsPostDom >::Parent.
Member Function Documentation
◆ dominates() [1/7]
| bool DominatorTree::dominates | ( | const BasicBlock * | BB, |
| const Use & | U | ||
| ) | const |
Return true if the (end of the) basic block BB dominates the use U.
Definition at line 115 of file Dominators.cpp.
References BB, llvm::Instruction::getParent(), llvm::Use::getUser(), and llvm::DominatorTreeBase< BasicBlock, false >::properlyDominates().
Referenced by llvm::LoopSafetyInfo::allLoopPathsLeadToBlock(), llvm::ScalarEvolution::applyLoopGuards(), llvm::LoopAccessInfo::blockNeedsPredication(), BrPHIToSelect(), CalculateUnswitchCostMultiplier(), checkBasicSSA(), checkHoistValue(), llvm::SCEVExpanderCleaner::cleanup(), CompareSCEVComplexity(), containsUnconditionalCallSafepoint(), doesStoreDominatesAllLatches(), dominates(), llvm::MemorySSA::dominates(), eliminateConstraints(), llvm::EpilogueVectorizerEpilogueLoop::emitMinimumVectorEpilogueIterCountCheck(), findBasePointers(), findBBsToSinkInto(), findCallsAtConstantOffset(), findCommonDominator(), foldGuardedFunnelShift(), llvm::formLCSSAForInstructions(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::InnerLoopVectorizer::getBroadcastInstrs(), llvm::ScalarEvolution::getConstantMaxTripCountFromArray(), getInsertPointForUses(), getInvariantGroupClobberingInstruction(), llvm::MemoryDependenceResults::getInvariantGroupPointerDependency(), getMinAnalyzeableBackedgeTakenCount(), getReductionValue(), llvm::hoistRegion(), hoistValue(), insertParsePoints(), insertSpills(), llvm::ScalarEvolution::instructionCouldExistWitthOperands(), IsAcceptableTarget(), IsAvailableOnEntry(), IsBackEdge(), llvm::ScalarEvolution::isBasicBlockEntryGuardedByCond(), llvm::isControlFlowEquivalent(), llvm::RecurrenceDescriptor::isFirstOrderRecurrence(), isFullDominator(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isKnownNonNullFromDominatingCondition(), llvm::ScalarEvolution::isKnownViaInduction(), llvm::ScalarEvolution::isLoopBackedgeGuardedByCond(), llvm::isOverflowIntrinsicNoWrap(), llvm::isPotentiallyReachableFromMany(), llvm::isReachedBefore(), llvm::isSafeToMoveBefore(), llvm::isValidAssumeForContext(), llvm::AA::isValidAtPosition(), IVUseShouldUsePostIncValue(), liesBetween(), mustExecuteUBIfPoisonOnPathTo(), nearest_common_dominatee(), optimizeDivRem(), partitionLoopBlocks(), peelToTurnInvariantLoadsDerefencebale(), PickMostRelevantLoop(), llvm::promoteLoopAccessesToScalars(), llvm::replaceDominatedUsesWith(), reportMayClobberedLoad(), rewriteDebugUsers(), rewriteSingleStoreAlloca(), separateNestedLoop(), simplifyCommonValuePhi(), SimplifyUsingControlFlow(), SinkInstruction(), sinkLifetimeStartMarkers(), sinkSpillUsesAfterCoroBegin(), unswitchBestCondition(), unswitchNontrivialInvariants(), and valueDominatesPHI().
◆ dominates() [2/7]
| bool DominatorTree::dominates | ( | const BasicBlockEdge & | BBE, |
| const BasicBlock * | BB | ||
| ) | const |
Definition at line 200 of file Dominators.cpp.
◆ dominates() [3/7]
| bool DominatorTree::dominates | ( | const BasicBlockEdge & | BBE, |
| const Use & | U | ||
| ) | const |
Return true if an edge dominates a use.
If BBE is not a unique edge between start and end of the edge, it can never dominate the use.
Definition at line 250 of file Dominators.cpp.
References dominates(), llvm::BasicBlockEdge::getEnd(), llvm::PHINode::getIncomingBlock(), llvm::Instruction::getParent(), llvm::BasicBlockEdge::getStart(), and llvm::Use::getUser().
◆ dominates() [4/7]
| bool DominatorTree::dominates | ( | const BasicBlockEdge & | BBE1, |
| const BasicBlockEdge & | BBE2 | ||
| ) | const |
Returns true if edge BBE1 dominates edge BBE2.
Definition at line 344 of file Dominators.cpp.
References dominates(), llvm::BasicBlockEdge::getEnd(), and llvm::BasicBlockEdge::getStart().
◆ dominates() [5/7]
| bool DominatorTree::dominates | ( | const Instruction * | Def, |
| const BasicBlock * | BB | ||
| ) | const |
Definition at line 167 of file Dominators.cpp.
References llvm::tgtok::Def, dominates(), E, and isReachableFromEntry().
◆ dominates() [6/7]
| bool DominatorTree::dominates | ( | const Value * | Def, |
| const Instruction * | User | ||
| ) | const |
Return true if value Def dominates all possible uses inside instruction User.
Same comments as for the Use-based API apply.
Definition at line 128 of file Dominators.cpp.
References assert(), llvm::tgtok::Def, dominates(), and isReachableFromEntry().
◆ dominates() [7/7]
Return true if value Def dominates use U, in the sense that Def is available at U, and could be substituted as the used value without violating the SSA dominance requirement.
In particular, it is worth noting that:
- Non-instruction Defs dominate everything.
- Def does not dominate a use in Def itself (outside of degenerate cases like unreachable code or trivial phi cycles).
- Invoke/callbr Defs only dominate uses in their default destination.
Definition at line 268 of file Dominators.cpp.
References assert(), llvm::tgtok::Def, dominates(), E, llvm::Instruction::getParent(), llvm::Use::getUser(), and isReachableFromEntry().
◆ invalidate()
| bool DominatorTree::invalidate | ( | Function & | F, |
| const PreservedAnalyses & | PA, | ||
| FunctionAnalysisManager::Invalidator & | |||
| ) |
Handle invalidation explicitly.
Definition at line 106 of file Dominators.cpp.
References llvm::PreservedAnalyses::getChecker().
◆ isReachableFromEntry()
Provide an overload for a Use.
Definition at line 328 of file Dominators.cpp.
References llvm::Use::getUser(), and I.
Referenced by buildExtractionBlockSet(), deleteDeadBlocksFromLoop(), deleteDeadClonedBlocks(), llvm::deleteDeadLoop(), dominates(), foldUnusualPatterns(), getInsertPointForUses(), insertParsePoints(), isBlockInLCSSAForm(), llvm::ScalarEvolution::isLoopBackedgeGuardedByCond(), llvm::isPotentiallyReachable(), llvm::isPotentiallyReachableFromMany(), makeReducible(), llvm::PHITransAddr::PHITranslateValue(), ProcessBlock(), llvm::TruncInstCombine::run(), runImpl(), llvm::JumpThreadingPass::runImpl(), llvm::RewriteStatepointsForGC::runOnFunction(), SimplifyUsingControlFlow(), sink(), SinkInstruction(), and UpdateAnalysisInformation().
◆ viewGraph() [1/2]
| void DominatorTree::viewGraph | ( | ) |
Definition at line 91 of file DomPrinter.cpp.
References llvm::errs().
◆ viewGraph() [2/2]
Definition at line 83 of file DomPrinter.cpp.
References llvm::errs(), and llvm::ViewGraph().
The documentation for this class was generated from the following files:
- include/llvm/IR/Dominators.h
- lib/Analysis/DomPrinter.cpp
- lib/IR/Dominators.cpp
