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:

Collaboration diagram for llvm::DominatorTree:

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 = typename std::remove_pointer< ParentPtr >::type
using	UpdateType = cfg::Update< NodePtr >
using	UpdateKind = cfg::UpdateKind

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 Instruction *Def, const Use &U) const
	Return true if Def dominates a use in User. More...
bool	dominates (const Instruction *Def, const Instruction *User) const
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	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
const SmallVectorImpl< BasicBlock *> &	getRoots () const
	getRoots - Return the root blocks of the current CFG. More...
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...
void	releaseMemory ()
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
	findNearestCommonDominator - 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	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...

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)
void	reset ()
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 144 of file Dominators.h.

Member Typedef Documentation

Base

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

Definition at line 146 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 149 of file Dominators.h.

DominatorTree() [3/3]

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

inlineexplicit

Definition at line 150 of file Dominators.h.

References llvm::tgtok::Def, F(), Name, and llvm::DominatorTreeBase< NodeT, IsPostDom >::Parent.

Member Function Documentation

dominates() [1/5]

bool DominatorTree::dominates	(	const Instruction *	Def,
		const Use &	U
	)		const

Return true if Def dominates a use in User.

This performs the special checks necessary if Def and User are in the same basic block. Note that Def doesn't dominate a use in Def itself!

Definition at line 248 of file Dominators.cpp.

References E, llvm::Instruction::getParent(), llvm::Use::getUser(), and I.

Referenced by llvm::LoopSafetyInfo::allLoopPathsLeadToBlock(), AllUsesDominatedByBlock(), llvm::MemorySSAUpdater::applyInsertUpdates(), AreSequentialAccesses(), llvm::LoopAccessInfo::blockNeedsPredication(), BrPHIToSelect(), calculateUnswitchCostMultiplier(), checkBasicSSA(), checkHoistValue(), CompareSCEVComplexity(), containsUnconditionalCallSafepoint(), llvm::createSeparateConstOffsetFromGEPPass(), doesStoreDominatesAllLatches(), llvm::OrderedInstructions::dominates(), enableCallSafepoints(), ensurePromotedGV(), findBasePointers(), findBBsToSinkInto(), findCallsAtConstantOffset(), llvm::ScalarEvolution::forgetValue(), llvm::formLCSSAForInstructions(), LoopFuser::fuseLoops(), llvm::ScalarEvolution::getBlockDisposition(), llvm::InnerLoopVectorizer::getBroadcastInstrs(), getFirstNonAllocaInTheEntryBlock(), getInsertPointForUses(), llvm::MemoryDependenceResults::getInvariantGroupPointerDependency(), llvm::ScalarEvolution::getLoopDisposition(), getMemSetPatternValue(), getReductionValue(), getSignature(), llvm::SCEVExpander::hoistIVInc(), llvm::hoistRegion(), hoistValue(), llvm::DivergenceAnalysis::inRegion(), insertParsePoints(), IsAcceptableTarget(), IsAvailableOnEntry(), IsBackEdge(), llvm::RecurrenceDescriptor::isFirstOrderRecurrence(), isFullDominator(), llvm::HardwareLoopInfo::isHardwareLoopCandidate(), isKnownNonNullFromDominatingCondition(), llvm::isOverflowIntrinsicNoWrap(), llvm::isPotentiallyReachableFromMany(), isSafeToSpeculatePHIUsers(), isSupportedGuardInstruction(), llvm::isValidAssumeForContext(), IVUseShouldUsePostIncValue(), moveSpillUsesAfterCoroBegin(), moveUp(), mustExecuteUBIfPoisonOnPathTo(), nearest_common_dominatee(), FusionCandidateCompare::operator()(), optimizeDivRem(), partitionOuterLoopBlocks(), PickMostRelevantLoop(), llvm::promoteLoopAccessesToScalars(), llvm::GVNHoist::rank(), RemoveInstInputs(), llvm::replaceDominatedUsesWith(), ReplaceUsesOfWith(), reportMayClobberedLoad(), rewriteDebugUsers(), rewriteSingleStoreAlloca(), separateNestedLoop(), shouldConvert(), llvm::CaptureTracker::shouldExplore(), simplifyCommonValuePhi(), llvm::sinkRegion(), unswitchNontrivialInvariants(), and valueDominatesPHI().

dominates() [2/5]

bool DominatorTree::dominates	(	const Instruction *	Def,
		const Instruction *	User
	)		const

Definition at line 115 of file Dominators.cpp.

References llvm::BasicBlock::begin(), llvm::tgtok::Def, llvm::Instruction::getParent(), and I.

dominates() [3/5]

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

Definition at line 152 of file Dominators.cpp.

References E, and llvm::Instruction::getParent().

dominates() [4/5]

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

References llvm::dyn_cast(), llvm::BasicBlockEdge::getEnd(), llvm::Instruction::getParent(), llvm::BasicBlockEdge::getStart(), and llvm::Use::getUser().

dominates() [5/5]

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

Definition at line 178 of file Dominators.cpp.

References E, llvm::BasicBlockEdge::getEnd(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlockEdge::getStart(), llvm::pred_begin(), and llvm::pred_end().

invalidate()

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

Handle invalidation explicitly.

Definition at line 103 of file Dominators.cpp.

References llvm::PreservedAnalyses::getChecker().

isReachableFromEntry()

bool DominatorTree::isReachableFromEntry

(

const Use &

U

)

const

Provide an overload for a Use.

Definition at line 299 of file Dominators.cpp.

References llvm::dyn_cast(), llvm::Instruction::getParent(), llvm::Use::getUser(), and I.

Referenced by buildExtractionBlockSet(), CreatePrologue(), deleteDeadBlocksFromLoop(), deleteDeadClonedBlocks(), eliminateDeadStores(), findBestInsertionSet(), findUnconditionalPreds(), foldUnusualPatterns(), getInnermostLoopFor(), getInsertPointForUses(), hasUndefContents(), llvm::SSAUpdaterBulk::HasValueForBlock(), insertParsePoints(), isBlockInLCSSAForm(), llvm::isPotentiallyReachable(), llvm::isPotentiallyReachableFromMany(), isSupportedGuardInstruction(), llvm::PHITransAddr::PHITranslateValue(), ProcessBlock(), llvm::TruncInstCombine::run(), llvm::RewriteStatepointsForGC::runOnFunction(), llvm::CaptureTracker::shouldExplore(), sink(), SortNonLocalDepInfoCache(), and UpdateAnalysisInformation().

viewGraph() [1/2]

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

Definition at line 82 of file DomPrinter.cpp.

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

viewGraph() [2/2]

void DominatorTree::viewGraph

(

)

Definition at line 90 of file DomPrinter.cpp.

References llvm::errs(), llvm::DominatorTreeWrapperPass::getDomTree(), llvm::PassRegistry::getPassRegistry(), llvm::PostDominatorTreeWrapperPass::getPostDomTree(), INITIALIZE_PASS(), llvm::initializeDomOnlyViewerPass(), llvm::initializeDomViewerPass(), llvm::initializePostDomOnlyViewerPass(), and llvm::initializePostDomViewerPass().

---

The documentation for this class was generated from the following files:

• include/llvm/IR/Dominators.h
• lib/Analysis/DomPrinter.cpp
• lib/IR/Dominators.cpp