LLVM  13.0.0git
Public Types | Public Member Functions | List of all members
llvm::DominatorTree Class Reference

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree. More...

#include "llvm/IR/Dominators.h"

Inheritance diagram for llvm::DominatorTree:
Inheritance graph
[legend]
Collaboration diagram for llvm::DominatorTree:
Collaboration graph
[legend]

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
 
DominatorTreeBaseoperator= (DominatorTreeBase &&RHS)
 
DominatorTreeBaseoperator= (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_iteratorroots ()
 
iterator_range< const_root_iteratorroots () 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
 
BasicBlockgetRoot () const
 
BasicBlockfindNearestCommonDominator (BasicBlock *A, BasicBlock *B) const
 Find nearest common dominator basic block for basic block A and B. More...
 
const BasicBlockfindNearestCommonDominator (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 ()
 

Additional Inherited Members

- Static Public Attributes inherited from llvm::DominatorTreeBase< BasicBlock, false >
static constexpr bool IsPostDominator
 
static constexpr UpdateKind Insert
 
static constexpr UpdateKind Delete
 
- Protected Types inherited from llvm::DominatorTreeBase< BasicBlock, false >
using DomTreeNodeMapType = DenseMap< BasicBlock *, std::unique_ptr< DomTreeNodeBase< BasicBlock > >>
 
- Protected Member Functions inherited from llvm::DominatorTreeBase< BasicBlock, false >
void addRoot (BasicBlock *BB)
 
void addRoot (MachineBasicBlock *MBB)
 
DomTreeNodeBase< BasicBlock > * createChild (BasicBlock *BB, DomTreeNodeBase< BasicBlock > *IDom)
 
DomTreeNodeBase< BasicBlock > * createNode (BasicBlock *BB)
 
void Split (typename GraphTraits< N >::NodeRef NewBB)
 
- Protected Attributes inherited from llvm::DominatorTreeBase< BasicBlock, false >
SmallVector< BasicBlock *, IsPostDom ? 4 :1 > Roots
 
DomTreeNodeMapType DomTreeNodes
 
DomTreeNodeBase< BasicBlock > * RootNode
 
ParentPtr Parent
 
bool DFSInfoValid
 
unsigned int SlowQueries
 

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]

llvm::DominatorTree::DominatorTree ( )
default

◆ DominatorTree() [2/3]

llvm::DominatorTree::DominatorTree ( Function F)
inlineexplicit

Definition at line 156 of file Dominators.h.

References F.

◆ DominatorTree() [3/3]

llvm::DominatorTree::DominatorTree ( DominatorTree DT,
DomTreeBuilder::BBUpdates  U 
)
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(), 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(), liesBetween(), mustExecuteUBIfPoisonOnPathTo(), nearest_common_dominatee(), optimizeDivRem(), partitionLoopBlocks(), 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]

bool DominatorTree::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.

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()

bool DominatorTree::isReachableFromEntry ( const Use U) const

◆ viewGraph() [1/2]

void DominatorTree::viewGraph ( )

Definition at line 91 of file DomPrinter.cpp.

References llvm::errs().

◆ viewGraph() [2/2]

void DominatorTree::viewGraph ( const Twine Name,
const Twine Title 
)

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: