LLVM
12.0.0git
|
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 > |
![]() | |
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 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 () |
![]() | |
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 () |
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.
Definition at line 153 of file Dominators.h.
|
default |
|
inlineexplicit |
Definition at line 156 of file Dominators.h.
References F().
|
inlineexplicit |
Definition at line 157 of file Dominators.h.
References llvm::DominatorTreeBase< NodeT, IsPostDom >::Parent.
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:
Definition at line 260 of file Dominators.cpp.
References assert(), llvm::tgtok::Def, E, llvm::Instruction::getParent(), llvm::Use::getUser(), and isReachableFromEntry().
Referenced by llvm::LoopSafetyInfo::allLoopPathsLeadToBlock(), llvm::LoopAccessInfo::blockNeedsPredication(), BrPHIToSelect(), CalculateUnswitchCostMultiplier(), checkBasicSSA(), checkHoistValue(), CompareSCEVComplexity(), containsUnconditionalCallSafepoint(), doesStoreDominatesAllLatches(), dominates(), llvm::MemorySSA::dominates(), llvm::EpilogueVectorizerEpilogueLoop::emitMinimumVectorEpilogueIterCountCheck(), findBasePointers(), findBBsToSinkInto(), findCallsAtConstantOffset(), foldGuardedFunnelShift(), llvm::formLCSSAForInstructions(), llvm::ScalarEvolution::getAddExpr(), llvm::ScalarEvolution::getAddRecExpr(), llvm::InnerLoopVectorizer::getBroadcastInstrs(), getInsertPointForUses(), llvm::MemoryDependenceResults::getInvariantGroupPointerDependency(), getMinAnalyzeableBackedgeTakenCount(), getReductionValue(), llvm::hoistRegion(), hoistValue(), insertParsePoints(), insertSpills(), 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::isSafeToMoveBefore(), isSafeToSpeculatePHIUsers(), llvm::isValidAssumeForContext(), IVUseShouldUsePostIncValue(), mustExecuteUBIfPoisonOnPathTo(), nearest_common_dominatee(), optimizeDivRem(), partitionLoopBlocks(), PickMostRelevantLoop(), llvm::promoteLoopAccessesToScalars(), llvm::replaceDominatedUsesWith(), reportMayClobberedLoad(), rewriteDebugUsers(), rewriteSingleStoreAlloca(), separateNestedLoop(), simplifyCommonValuePhi(), SimplifyUsingControlFlow(), SinkInstruction(), sinkLifetimeStartMarkers(), sinkSpillUsesAfterCoroBegin(), unswitchNontrivialInvariants(), valueDominatesPHI(), WidenIV::widenWithVariantUse(), and llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner().
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 118 of file Dominators.cpp.
References assert(), llvm::tgtok::Def, dominates(), and isReachableFromEntry().
bool DominatorTree::dominates | ( | const Instruction * | Def, |
const BasicBlock * | BB | ||
) | const |
Definition at line 157 of file Dominators.cpp.
References llvm::tgtok::Def, dominates(), E, and isReachableFromEntry().
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 242 of file Dominators.cpp.
References dominates(), llvm::BasicBlockEdge::getEnd(), llvm::Instruction::getParent(), llvm::BasicBlockEdge::getStart(), and llvm::Use::getUser().
bool DominatorTree::dominates | ( | const BasicBlockEdge & | BBE, |
const BasicBlock * | BB | ||
) | const |
Definition at line 190 of file Dominators.cpp.
bool DominatorTree::dominates | ( | const BasicBlockEdge & | BBE1, |
const BasicBlockEdge & | BBE2 | ||
) | const |
Returns true if edge BBE1
dominates edge BBE2
.
Definition at line 336 of file Dominators.cpp.
References dominates(), llvm::BasicBlockEdge::getEnd(), and llvm::BasicBlockEdge::getStart().
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().
Provide an overload for a Use.
Definition at line 320 of file Dominators.cpp.
References llvm::Use::getUser(), and I.
Referenced by buildExtractionBlockSet(), deleteDeadBlocksFromLoop(), deleteDeadClonedBlocks(), llvm::deleteDeadLoop(), dominates(), eliminateDeadStores(), findUnconditionalPreds(), foldUnusualPatterns(), getInsertPointForUses(), insertParsePoints(), isBlockInLCSSAForm(), llvm::ScalarEvolution::isLoopBackedgeGuardedByCond(), llvm::isPotentiallyReachable(), llvm::isPotentiallyReachableFromMany(), makeReducible(), llvm::PHITransAddr::PHITranslateValue(), ProcessBlock(), llvm::TruncInstCombine::run(), runImpl(), llvm::RewriteStatepointsForGC::runOnFunction(), SimplifyUsingControlFlow(), sink(), SinkInstruction(), and UpdateAnalysisInformation().
Definition at line 83 of file DomPrinter.cpp.
References llvm::errs(), and ViewGraph().
void DominatorTree::viewGraph | ( | ) |
Definition at line 91 of file DomPrinter.cpp.
References llvm::errs().