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

#include "llvm/IR/Dominators.h"

Inheritance diagram for llvm::DominatorTree:

Public Types
using	Base = DominatorTreeBase<BasicBlock, false>
Public Types inherited from llvm::DominatorTreeBase< BasicBlock, false >
using	NodeTrait
using	NodeType
using	NodePtr
using	ParentPtr
using	ParentType
using	UpdateType
using	UpdateKind
using	root_iterator
	Iteration over roots.
using	const_root_iterator
enum	VerificationLevel

Public Member Functions
	DominatorTree ()=default
	DominatorTree (Function &F)
	DominatorTree (DominatorTree &DT, DomTreeBuilder::BBUpdates U)
LLVM_ABI bool	invalidate (Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
	Handle invalidation explicitly.
LLVM_ABI bool	dominates (const BasicBlock *BB, const Use &U) const
	Return true if the (end of the) basic block BB dominates the use U.
LLVM_ABI 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.
LLVM_ABI bool	dominates (const Value Def, const Instruction User) const
	Return true if value Def dominates all possible uses inside instruction User.
bool	dominates (const Value *Def, BasicBlock::iterator User) const
LLVM_ABI bool	dominates (const Instruction Def, const BasicBlock BB) const
	Returns true if Def would dominate a use in any instruction in BB.
LLVM_ABI bool	dominates (const BasicBlockEdge &BBE, const Use &U) const
	Return true if an edge dominates a use.
LLVM_ABI bool	dominates (const BasicBlockEdge &BBE, const BasicBlock *BB) const
LLVM_ABI bool	dominates (const BasicBlockEdge &BBE1, const BasicBlockEdge &BBE2) const
	Returns true if edge `BBE1` dominates edge `BBE2`.
LLVM_ABI bool	isReachableFromEntry (const Use &U) const
	Provide an overload for a Use.
LLVM_ABI Instruction *	findNearestCommonDominator (Instruction I1, Instruction I2) const
	Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced before I will be available at both I1 and I2.
LLVM_ABI void	viewGraph (const Twine &Name, const Twine &Title)
LLVM_ABI void	viewGraph ()
bool	dominates (const DomTreeNodeBase< BasicBlock > A, const DomTreeNodeBase< BasicBlock > B) const
	dominates - Returns true iff A dominates B.
bool	dominates (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.
bool	isReachableFromEntry (const DomTreeNodeBase< BasicBlock > *A) const
BasicBlock *	findNearestCommonDominator (BasicBlock A, BasicBlock B) const
	Find nearest common dominator basic block for basic block A and B.
const BasicBlock *	findNearestCommonDominator (const BasicBlock A, const BasicBlock B) const
BasicBlock *	findNearestCommonDominator (iterator_range< IteratorTy > Nodes) const
Public Member Functions inherited from llvm::DominatorTreeBase< BasicBlock, false >
	DominatorTreeBase ()=default
	DominatorTreeBase (DominatorTreeBase &&Arg)
DominatorTreeBase &	operator= (DominatorTreeBase &&RHS)
	DominatorTreeBase (const DominatorTreeBase &)=delete
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
bool	compare (const DominatorTreeBase &Other) const
	compare - Return false if the other dominator tree base matches this dominator tree base.
DomTreeNodeBase< BasicBlock > *	getNode (const BasicBlock *BB) const
	getNode - return the (Post)DominatorTree node for the specified basic block.
DomTreeNodeBase< BasicBlock > *	operator[] (const BasicBlock *BB) const
	See getNode.
DomTreeNodeBase< BasicBlock > *	getRootNode ()
	getRootNode - This returns the entry node for the CFG of the function.
const DomTreeNodeBase< BasicBlock > *	getRootNode () const
void	getDescendants (BasicBlock R, SmallVectorImpl< BasicBlock > &Result) const
	Get all nodes dominated by R, including R itself.
bool	properlyDominates (const DomTreeNodeBase< BasicBlock > A, const DomTreeNodeBase< BasicBlock > B) const
	properlyDominates - Returns true iff A dominates B and A != B.
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.
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.
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.
const BasicBlock *	findNearestCommonDominator (const BasicBlock A, const BasicBlock B) const
bool	isVirtualRoot (const DomTreeNodeBase< BasicBlock > *A) const
BasicBlock *	findNearestCommonDominator (iterator_range< IteratorTy > Nodes) 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.
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.
void	deleteEdge (BasicBlock From, BasicBlock To)
	Inform the dominator tree about a CFG edge deletion and update the tree.
DomTreeNodeBase< BasicBlock > *	addNewBlock (BasicBlock BB, BasicBlock DomBB)
	Add a new node to the dominator tree information.
DomTreeNodeBase< BasicBlock > *	setNewRoot (BasicBlock *BB)
	Add a new node to the forward dominator tree and make it a new root.
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.
void	changeImmediateDominator (BasicBlock BB, BasicBlock NewBB)
void	eraseNode (BasicBlock *BB)
	eraseNode - Removes a node from the dominator tree.
void	splitBlock (BasicBlock *NewBB)
	splitBlock - BB is split and now it has one successor.
void	print (raw_ostream &O) const
	print - Convert to human readable form
void	updateDFSNumbers () const
	updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
void	recalculate (ParentType &Func)
	recalculate - compute a dominator tree for the given function
void	recalculate (ParentType &Func, ArrayRef< UpdateType > Updates)
std::enable_if_t< GraphHasNodeNumbers< T * >, void >	updateBlockNumbers ()
	Update dominator tree after renumbering blocks.
bool	verify (VerificationLevel VL=VerificationLevel::Full) const
	verify - checks if the tree is correct.
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	DomTreeNodeStorageTy
Protected Member Functions inherited from llvm::DominatorTreeBase< BasicBlock, false >
void	addRoot (BasicBlock *BB)
DomTreeNodeBase< BasicBlock > *	createNode (BasicBlock BB, DomTreeNodeBase< BasicBlock > IDom=nullptr)
void	Split (typename GraphTraits< N >::NodeRef NewBB)
Protected Attributes inherited from llvm::DominatorTreeBase< BasicBlock, false >
SmallVector< BasicBlock *, IsPostDom ? 4 :1 >	Roots
DomTreeNodeStorageTy	DomTreeNodes
std::conditional_t<!GraphHasNodeNumbers< BasicBlock * >, DenseMap< const BasicBlock *, unsigned >, std::tuple<> >	NodeNumberMap
DomTreeNodeBase< BasicBlock > *	RootNode
ParentPtr	Parent
bool	DFSInfoValid
unsigned int	SlowQueries
unsigned	BlockNumberEpoch

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 165 of file Dominators.h.

Member Typedef Documentation

◆ Base

using llvm::DominatorTree::Base = DominatorTreeBase<BasicBlock, false>

Definition at line 167 of file Dominators.h.

Constructor & Destructor Documentation

◆ DominatorTree() [1/3]

llvm::DominatorTree::DominatorTree ( )

default

Referenced by DominatorTree().

◆ DominatorTree() [2/3]

llvm::DominatorTree::DominatorTree ( Function & F )

inlineexplicit

Definition at line 170 of file Dominators.h.

References F, and llvm::DominatorTreeBase< BasicBlock, false >::recalculate().

◆ DominatorTree() [3/3]

llvm::DominatorTree::DominatorTree	(	DominatorTree &	DT,
		DomTreeBuilder::BBUpdates	U )

inlineexplicit

Definition at line 171 of file Dominators.h.

References DominatorTree(), llvm::DominatorTreeBase< NodeT, IsPostDom >::Parent, and llvm::DominatorTreeBase< BasicBlock, false >::recalculate().

Member Function Documentation

◆ dominates() [1/10]

bool llvm::DominatorTreeBase< BasicBlock, IsPostDom >::dominates	(	const BasicBlock *	A,
		const BasicBlock *	B ) const

◆ dominates() [2/10]

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 135 of file Dominators.cpp.

References llvm::cast(), dominates(), llvm::dyn_cast(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), and llvm::DominatorTreeBase< BasicBlock, false >::properlyDominates().

Referenced by llvm::LoopSafetyInfo::allLoopPathsLeadToBlock(), llvm::LoopAccessInfo::blockNeedsPredication(), BrPHIToSelect(), CalculateUnswitchCostMultiplier(), canProveExitOnFirstIteration(), checkBasicSSA(), checkHoistValue(), CompareSCEVComplexity(), llvm::computeKnownBitsFromContext(), computeKnownFPClassFromContext(), containsUnconditionalCallSafepoint(), doesStoreDominatesAllLatches(), DoFlattenLoopPair(), dominates(), dominates(), dominates(), dominates(), dominates(), dominates(), dominates(), findBasePointers(), findBBsToSinkInto(), findBestNonTrivialUnswitchCandidate(), findCallsAtConstantOffset(), findMayClobberedPtrAccess(), foldConsecutiveLoads(), foldGuardedFunnelShift(), foldIdempotentBinaryIntrinsicRecurrence(), formLCSSAForInstructionsImpl(), forwardHandleAccesses(), generateReproducer(), getFreezeInsertPt(), getInsertPointForUses(), getInvariantGroupClobberingInstruction(), getMinAnalyzeableBackedgeTakenCount(), getReductionInstr(), llvm::coro::getSpillInsertionPt(), llvm::GCNTTIImpl::hoistLaneIntrinsicThroughOperand(), llvm::hoistRegion(), hoistValue(), insertParsePoints(), insertSpills(), IsBackEdge(), llvm::isControlFlowEquivalent(), llvm::RecurrenceDescriptor::isFixedOrderRecurrence(), isFullDominator(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isKnownNonEqualFromContext(), isKnownNonNullFromDominatingCondition(), llvm::isKnownToBeAPowerOfTwo(), llvm::isOverflowIntrinsicNoWrap(), isReachableImpl(), llvm::isReachedBefore(), llvm::isSafeToMoveBefore(), llvm::isValidAssumeForContext(), IVUseShouldUsePostIncValue(), liesBetween(), llvm::mustExecuteUBIfPoisonOnPathTo(), nearest_common_dominatee(), optimizeDivRem(), partitionLoopBlocks(), peelToTurnInvariantLoadsDerefencebale(), PickMostRelevantLoop(), PrintDebugDomInfo(), llvm::promoteLoopAccessesToScalars(), llvm::replaceDominatedUsesWith(), llvm::replaceDominatedUsesWith(), llvm::replaceDominatedUsesWithIf(), llvm::replaceDominatedUsesWithIf(), rewriteDebugUsers(), rewriteSingleStoreAlloca(), llvm::PlaceSafepointsPass::runImpl(), separateNestedLoop(), simplifyCommonValuePhi(), simplifyUsingControlFlow(), SinkInstruction(), sinkLifetimeStartMarkers(), llvm::coro::sinkSpillUsesAfterCoroBegin(), llvm::PHITransAddr::translateValue(), unswitchNontrivialInvariants(), UpdateSSA(), and valueDominatesPHI().

◆ dominates() [3/10]

bool DominatorTree::dominates	(	const BasicBlockEdge &	BBE,
		const BasicBlock *	BB ) const

Definition at line 213 of file Dominators.cpp.

References dominates(), llvm::BasicBlockEdge::getEnd(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlockEdge::getStart(), and llvm::predecessors().

◆ dominates() [4/10]

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 263 of file Dominators.cpp.

References llvm::cast(), dominates(), llvm::dyn_cast(), llvm::BasicBlockEdge::getEnd(), llvm::PHINode::getIncomingBlock(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), and llvm::BasicBlockEdge::getStart().

◆ dominates() [5/10]

bool DominatorTree::dominates	(	const BasicBlockEdge &	BBE1,
		const BasicBlockEdge &	BBE2 ) const

Returns true if edge BBE1 dominates edge BBE2.

Definition at line 350 of file Dominators.cpp.

References dominates(), llvm::BasicBlockEdge::getEnd(), and llvm::BasicBlockEdge::getStart().

◆ dominates() [6/10]

bool llvm::DominatorTreeBase< BasicBlock, IsPostDom >::dominates	(	const DomTreeNodeBase< BasicBlock > *	A,
		const DomTreeNodeBase< BasicBlock > *	B ) const

inline

dominates - Returns true iff A dominates B.

Note that this is not a constant time operation!

Definition at line 467 of file GenericDomTree.h.

◆ dominates() [7/10]

bool DominatorTree::dominates	(	const Instruction *	Def,
		const BasicBlock *	BB ) const

Returns true if Def would dominate a use in any instruction in BB.

If Def is an instruction in BB, then Def does not dominate BB.

Does not accept Value to avoid ambiguity with dominance checks between two basic blocks.

Definition at line 187 of file Dominators.cpp.

References dominates(), llvm::dyn_cast(), E(), II, and isReachableFromEntry().

◆ dominates() [8/10]

bool llvm::DominatorTree::dominates	(	const Value *	Def,
		BasicBlock::iterator	User ) const

inline

Definition at line 199 of file Dominators.h.

References dominates().

◆ dominates() [9/10]

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 148 of file Dominators.cpp.

References assert(), dominates(), llvm::dyn_cast(), llvm::isa(), and isReachableFromEntry().

◆ dominates() [10/10]

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 Defs only dominate uses in their default destination.

Definition at line 281 of file Dominators.cpp.

References assert(), llvm::cast(), dominates(), llvm::dyn_cast(), E(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), II, llvm::isa(), and isReachableFromEntry().

◆ findNearestCommonDominator() [1/4]

BasicBlock * llvm::DominatorTreeBase< BasicBlock, IsPostDom >::findNearestCommonDominator	(	BasicBlock *	A,
		BasicBlock *	B ) const

inline

Find nearest common dominator basic block for basic block A and B.

A and B must have tree nodes.

Definition at line 519 of file GenericDomTree.h.

◆ findNearestCommonDominator() [2/4]

const BasicBlock * llvm::DominatorTreeBase< BasicBlock, IsPostDom >::findNearestCommonDominator	(	const BasicBlock *	A,
		const BasicBlock *	B ) const

inline

Definition at line 549 of file GenericDomTree.h.

◆ findNearestCommonDominator() [3/4]

Instruction * DominatorTree::findNearestCommonDominator	(	Instruction *	I1,
		Instruction *	I2 ) const

Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced before I will be available at both I1 and I2.

Definition at line 357 of file Dominators.cpp.

References findNearestCommonDominator(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getTerminator(), and isReachableFromEntry().

Referenced by Prefetch::addInstruction(), ConnectEpilog(), ConnectProlog(), findCommonDominator(), findNearestCommonDominator(), getInsertPointForUses(), llvm::isControlFlowEquivalent(), nearest_common_dominator(), llvm::nonStrictlyPostDominate(), llvm::peelLoop(), runMoveAutoInit(), SinkInstruction(), llvm::UnrollLoop(), and usersDominator().

◆ findNearestCommonDominator() [4/4]

BasicBlock * llvm::DominatorTreeBase< BasicBlock, IsPostDom >::findNearestCommonDominator ( iterator_range< IteratorTy > Nodes ) const

inline

Definition at line 562 of file GenericDomTree.h.

◆ invalidate()

bool DominatorTree::invalidate	(	Function &	F,
		const PreservedAnalyses &	PA,
		FunctionAnalysisManager::Invalidator &	)

Handle invalidation explicitly.

Definition at line 126 of file Dominators.cpp.

References F, and llvm::PreservedAnalyses::getChecker().

◆ isReachableFromEntry() [1/3]

bool llvm::DominatorTreeBase< BasicBlock, IsPostDom >::isReachableFromEntry ( const BasicBlock * A ) const

inline

isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it.

Definition at line 456 of file GenericDomTree.h.

◆ isReachableFromEntry() [2/3]

bool llvm::DominatorTreeBase< BasicBlock, IsPostDom >::isReachableFromEntry ( const DomTreeNodeBase< BasicBlock > * A ) const

inline

Definition at line 462 of file GenericDomTree.h.

◆ isReachableFromEntry() [3/3]

bool DominatorTree::isReachableFromEntry ( const Use & U ) const

Provide an overload for a Use.

Definition at line 334 of file Dominators.cpp.

References llvm::dyn_cast(), I, and isReachableFromEntry().

Referenced by buildExtractionBlockSet(), checkClobberSanity(), collectUnswitchCandidatesWithInjections(), deleteDeadBlocksFromLoop(), deleteDeadClonedBlocks(), llvm::deleteDeadLoop(), dominates(), dominates(), dominates(), findBestInsertionSet(), findNearestCommonDominator(), foldUnusualPatterns(), formLCSSAForInstructionsImpl(), llvm::FunctionPropertiesInfo::getFunctionPropertiesInfo(), getInsertPointForUses(), insertParsePoints(), isBlockInLCSSAForm(), llvm::isPotentiallyReachable(), isReachableFromEntry(), isReachableImpl(), ProcessBlock(), llvm::coro::BaseCloner::replaceEntryBlock(), llvm::SSAUpdaterBulk::RewriteAllUses(), llvm::JumpThreadingPass::runImpl(), runImpl(), runMoveAutoInit(), llvm::RewriteStatepointsForGC::runOnFunction(), simplifyLoopInst(), simplifyUsingControlFlow(), sink(), SinkInstruction(), llvm::PHITransAddr::translateValue(), and UpdateAnalysisInformation().

◆ viewGraph() [1/2]

void DominatorTree::viewGraph ( )

Definition at line 36 of file DomPrinter.cpp.

References llvm::errs(), and viewGraph().

Referenced by viewGraph().

◆ viewGraph() [2/2]

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

Definition at line 28 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

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

Constructor & Destructor Documentation

◆ DominatorTree() [1/3]

◆ DominatorTree() [2/3]

◆ DominatorTree() [3/3]

Member Function Documentation

◆ dominates() [1/10]

◆ dominates() [2/10]

◆ dominates() [3/10]

◆ dominates() [4/10]

◆ dominates() [5/10]

◆ dominates() [6/10]

◆ dominates() [7/10]

◆ dominates() [8/10]

◆ dominates() [9/10]

◆ dominates() [10/10]

◆ findNearestCommonDominator() [1/4]

◆ findNearestCommonDominator() [2/4]

◆ findNearestCommonDominator() [3/4]

◆ findNearestCommonDominator() [4/4]

◆ invalidate()

◆ isReachableFromEntry() [1/3]

◆ isReachableFromEntry() [2/3]

◆ isReachableFromEntry() [3/3]

◆ viewGraph() [1/2]

◆ viewGraph() [2/2]