Core dominator tree base class. More...

#include "llvm/Analysis/LoopInfo.h"

Inheritance diagram for llvm::DominatorTreeBase< NodeT, IsPostDom >:

[legend]

Collaboration diagram for llvm::DominatorTreeBase< NodeT, IsPostDom >:

[legend]

Public Types
enum	VerificationLevel { VerificationLevel::Fast, VerificationLevel::Basic, VerificationLevel::Full }

using	NodeType = NodeT

using	NodePtr = NodeT *

using	ParentPtr = decltype(std::declval< NodeT * >() ->getParent())

using	ParentType = typename std::remove_pointer< ParentPtr >::type

using	UpdateType = cfg::Update< NodePtr >

using	UpdateKind = cfg::UpdateKind

Public Member Functions
	DominatorTreeBase ()

	DominatorTreeBase (DominatorTreeBase &&Arg)

DominatorTreeBase &	operator= (DominatorTreeBase &&RHS)

	DominatorTreeBase (const DominatorTreeBase &)=delete

DominatorTreeBase &	operator= (const DominatorTreeBase &)=delete

const SmallVectorImpl< NodeT * > &	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< NodeT > *	getNode (const NodeT *BB) const
	getNode - return the (Post)DominatorTree node for the specified basic block. More...

DomTreeNodeBase< NodeT > *	operator[] (const NodeT *BB) const
	See getNode. More...

DomTreeNodeBase< NodeT > *	getRootNode ()
	getRootNode - This returns the entry node for the CFG of the function. More...

const DomTreeNodeBase< NodeT > *	getRootNode () const

void	getDescendants (NodeT R, SmallVectorImpl< NodeT > &Result) const
	Get all nodes dominated by R, including R itself. More...

bool	properlyDominates (const DomTreeNodeBase< NodeT > A, const DomTreeNodeBase< NodeT > B) const
	properlyDominates - Returns true iff A dominates B and A != B. More...

bool	properlyDominates (const NodeT A, const NodeT B) const

bool	isReachableFromEntry (const NodeT *A) const
	isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it. More...

bool	isReachableFromEntry (const DomTreeNodeBase< NodeT > *A) const

bool	dominates (const DomTreeNodeBase< NodeT > A, const DomTreeNodeBase< NodeT > B) const
	dominates - Returns true iff A dominates B. More...

bool	dominates (const NodeT A, const NodeT B) const

NodeT *	getRoot () const

NodeT *	findNearestCommonDominator (NodeT A, NodeT B) const
	findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B. More...

const NodeT *	findNearestCommonDominator (const NodeT A, const NodeT B) const

bool	isVirtualRoot (const DomTreeNodeBase< NodeT > *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 (NodeT From, NodeT To)
	Inform the dominator tree about a CFG edge insertion and update the tree. More...

void	deleteEdge (NodeT From, NodeT To)
	Inform the dominator tree about a CFG edge deletion and update the tree. More...

DomTreeNodeBase< NodeT > *	addNewBlock (NodeT BB, NodeT DomBB)
	Add a new node to the dominator tree information. More...

DomTreeNodeBase< NodeT > *	setNewRoot (NodeT *BB)
	Add a new node to the forward dominator tree and make it a new root. More...

void	changeImmediateDominator (DomTreeNodeBase< NodeT > N, DomTreeNodeBase< NodeT > NewIDom)
	changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes. More...

void	changeImmediateDominator (NodeT BB, NodeT NewBB)

void	eraseNode (NodeT *BB)
	eraseNode - Removes a node from the dominator tree. More...

void	splitBlock (NodeT *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...

Static Public Attributes
static constexpr bool	IsPostDominator = IsPostDom

static constexpr UpdateKind	Insert = UpdateKind::Insert

static constexpr UpdateKind	Delete = UpdateKind::Delete

Protected Types
using	DomTreeNodeMapType = DenseMap< NodeT *, std::unique_ptr< DomTreeNodeBase< NodeT > >>

Protected Member Functions
void	addRoot (NodeT *BB)

void	reset ()

template<class N >
void	Split (typename GraphTraits< N >::NodeRef NewBB)

template<>
void	addRoot (MachineBasicBlock *MBB)

Protected Attributes
SmallVector< NodeT *, IsPostDom ? 4 :1 >	Roots

DomTreeNodeMapType	DomTreeNodes

DomTreeNodeBase< NodeT > *	RootNode

ParentPtr	Parent = nullptr

bool	DFSInfoValid = false

unsigned int	SlowQueries = 0

Friends
struct	DomTreeBuilder::SemiNCAInfo< DominatorTreeBase >

Detailed Description

template<typename NodeT, bool IsPostDom>
class llvm::DominatorTreeBase< NodeT, IsPostDom >

Core dominator tree base class.

This class is a generic template over graph nodes. It is instantiated for various graphs in the LLVM IR or in the code generator.

Definition at line 61 of file LoopInfo.h.

Member Typedef Documentation

◆ DomTreeNodeMapType

template<typename NodeT, bool IsPostDom>

using llvm::DominatorTreeBase< NodeT, IsPostDom >::DomTreeNodeMapType = DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT> >>

protected

Definition at line 244 of file GenericDomTree.h.

◆ NodePtr

template<typename NodeT, bool IsPostDom>

using llvm::DominatorTreeBase< NodeT, IsPostDom >::NodePtr = NodeT *

Definition at line 225 of file GenericDomTree.h.

◆ NodeType

template<typename NodeT, bool IsPostDom>

using llvm::DominatorTreeBase< NodeT, IsPostDom >::NodeType = NodeT

Definition at line 224 of file GenericDomTree.h.

◆ ParentPtr

template<typename NodeT, bool IsPostDom>

using llvm::DominatorTreeBase< NodeT, IsPostDom >::ParentPtr = decltype(std::declval<NodeT *>()->getParent())

Definition at line 226 of file GenericDomTree.h.

◆ ParentType

template<typename NodeT, bool IsPostDom>

using llvm::DominatorTreeBase< NodeT, IsPostDom >::ParentType = typename std::remove_pointer<ParentPtr>::type

Definition at line 229 of file GenericDomTree.h.

◆ UpdateKind

template<typename NodeT, bool IsPostDom>

using llvm::DominatorTreeBase< NodeT, IsPostDom >::UpdateKind = cfg::UpdateKind

Definition at line 233 of file GenericDomTree.h.

◆ UpdateType

template<typename NodeT, bool IsPostDom>

using llvm::DominatorTreeBase< NodeT, IsPostDom >::UpdateType = cfg::Update<NodePtr>

Definition at line 232 of file GenericDomTree.h.

Member Enumeration Documentation

◆ VerificationLevel

template<typename NodeT, bool IsPostDom>

enum llvm::DominatorTreeBase::VerificationLevel

strong

Enumerator
Fast
Basic
Full

Definition at line 237 of file GenericDomTree.h.

Constructor & Destructor Documentation

◆ DominatorTreeBase() [1/3]

template<typename NodeT, bool IsPostDom>

llvm::DominatorTreeBase< NodeT, IsPostDom >::DominatorTreeBase ( )

inline

Definition at line 255 of file GenericDomTree.h.

◆ DominatorTreeBase() [2/3]

template<typename NodeT, bool IsPostDom>

llvm::DominatorTreeBase< NodeT, IsPostDom >::DominatorTreeBase ( DominatorTreeBase< NodeT, IsPostDom > && Arg )

inline

Definition at line 257 of file GenericDomTree.h.

◆ DominatorTreeBase() [3/3]

template<typename NodeT, bool IsPostDom>

llvm::DominatorTreeBase< NodeT, IsPostDom >::DominatorTreeBase ( const DominatorTreeBase< NodeT, IsPostDom > & )

delete

Member Function Documentation

◆ addNewBlock()

template<typename NodeT, bool IsPostDom>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock	(	NodeT *	BB,
		NodeT *	DomBB
	)

inline

Add a new node to the dominator tree information.

This creates a new node as a child of DomBB dominator node, linking it into the children list of the immediate dominator.

Parameters

BB	New node in CFG.
DomBB	CFG node that is dominator for BB.

Returns: New dominator tree node that represents new CFG node.

Definition at line 569 of file GenericDomTree.h.

Referenced by CloneLoopBlocks(), cloneLoopBlocks(), llvm::cloneLoopWithPreheader(), CreatePrologue(), llvm::InnerLoopVectorizer::emitMemRuntimeChecks(), llvm::InnerLoopVectorizer::emitMinimumIterationCountCheck(), llvm::InnerLoopVectorizer::emitSCEVChecks(), llvm::VPlan::execute(), llvm::CodeExtractor::findInputsOutputs(), ReplaceUsesOfWith(), llvm::sinkRegion(), llvm::SplitBlock(), llvm::SplitBlockAndInsertIfThen(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), and llvm::InnerLoopVectorizer::updateAnalysis().

◆ addRoot() [1/2]

template<>

void llvm::DominatorTreeBase< MachineBasicBlock, false >::addRoot ( MachineBasicBlock * MBB )

inlineprotected

Definition at line 32 of file MachineDominators.h.

◆ addRoot() [2/2]

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::addRoot ( NodeT * BB )

inlineprotected

Definition at line 761 of file GenericDomTree.h.

◆ applyUpdates()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::applyUpdates ( ArrayRef< UpdateType > Updates )

inline

Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch update on the tree.

This function should be used when there were multiple CFG updates after the last dominator tree update. It takes care of performing the updates in sync with the CFG and optimizes away the redundant operations that cancel each other. The functions expects the sequence of updates to be balanced. Eg.:

{{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because logically it results in a single insertions.
{{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make sense to insert the same edge twice.

What's more, the functions assumes that it's safe to ask every node in the CFG about its children and inverse children. This implies that deletions of CFG edges must not delete the CFG nodes before calling this function.

The applyUpdates function can reorder the updates and remove redundant ones internally. The batch updater is also able to detect sequences of zero and exactly one update – it's optimized to do less work in these cases.

Note that for postdominators it automatically takes care of applying updates on reverse edges internally (so there's no need to swap the From and To pointers when constructing DominatorTree::UpdateType). The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T> with the same template parameter T.

Parameters

Updates An unordered sequence of updates to perform.

Definition at line 521 of file GenericDomTree.h.

Referenced by llvm::DomTreeUpdater::applyUpdates(), CloneLoop(), llvm::DomTreeUpdater::flush(), turnGuardIntoBranch(), llvm::UnrollAndJamLoop(), unswitchNontrivialInvariants(), and unswitchTrivialSwitch().

◆ changeImmediateDominator() [1/2]

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator	(	DomTreeNodeBase< NodeT > *	N,
		DomTreeNodeBase< NodeT > *	NewIDom
	)

inline

changeImmediateDominator - This method is used to update the dominator tree information when a node's immediate dominator changes.

Definition at line 607 of file GenericDomTree.h.

Referenced by cloneLoopBlocks(), llvm::cloneLoopWithPreheader(), ConnectEpilog(), ConnectProlog(), llvm::CodeExtractor::findInputsOutputs(), llvm::foldBlockIntoPredecessor(), llvm::peelLoop(), llvm::sinkRegion(), llvm::SplitBlock(), llvm::SplitBlockAndInsertIfThen(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), llvm::InnerLoopVectorizer::updateAnalysis(), and llvm::LoopVersioning::versionLoop().

◆ changeImmediateDominator() [2/2]

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator	(	NodeT *	BB,
		NodeT *	NewBB
	)

inline

Definition at line 614 of file GenericDomTree.h.

◆ compare()

template<typename NodeT, bool IsPostDom>

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::compare ( const DominatorTreeBase< NodeT, IsPostDom > & Other ) const

inline

compare - Return false if the other dominator tree base matches this dominator tree base.

Otherwise return true.

Definition at line 293 of file GenericDomTree.h.

◆ deleteEdge()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::deleteEdge	(	NodeT *	From,
		NodeT *	To
	)

inline

Inform the dominator tree about a CFG edge deletion and update the tree.

This function has to be called just after making the update on the actual CFG. An internal functions checks if the edge doesn't exist in the CFG in DEBUG mode. There cannot be any other updates that the dominator tree doesn't know about.

Note that for postdominators it automatically takes care of deleting a reverse edge internally (so there's no need to swap the parameters).

Definition at line 552 of file GenericDomTree.h.

Referenced by llvm::DomTreeUpdater::deleteEdge(), llvm::DomTreeUpdater::deleteEdgeRelaxed(), and unswitchTrivialBranch().

◆ dominates() [1/2]

template<typename NodeT, bool IsPostDom>

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

inline

dominates - Returns true iff A dominates B.

Note that this is not a constant time operation!

Definition at line 394 of file GenericDomTree.h.

Referenced by llvm::LoopInfoBase< BasicBlock, Loop >::analyze(), callsiteIsHot(), llvm::MachinePostDominatorTree::dominates(), and isFullPostDominator().

◆ dominates() [2/2]

template<typename NodeT, bool IsPostDom>

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

Definition at line 867 of file GenericDomTree.h.

◆ eraseNode()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::eraseNode ( NodeT * BB )

inline

eraseNode - Removes a node from the dominator tree.

Block must not dominate any other blocks. Removes node from its immediate dominator's children list. Deletes dominator node associated with basic block BB.

Definition at line 621 of file GenericDomTree.h.

Referenced by llvm::DomTreeUpdater::callbackDeleteBB(), and llvm::foldBlockIntoPredecessor().

◆ findNearestCommonDominator() [1/2]

template<typename NodeT, bool IsPostDom>

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

inline

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

If there is no such block then return nullptr.

Definition at line 446 of file GenericDomTree.h.

Referenced by llvm::MemorySSAUpdater::applyInsertUpdates(), llvm::MachinePostDominatorTree::findNearestCommonDominator(), getInsertPointForUses(), isAlwaysFoldable(), mayUsePostIncMode(), nearest_common_dominator(), shouldConvert(), and llvm::UnrollLoop().

◆ findNearestCommonDominator() [2/2]

template<typename NodeT, bool IsPostDom>

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

inline

Definition at line 475 of file GenericDomTree.h.

◆ getDescendants()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::getDescendants	(	NodeT *	R,
		SmallVectorImpl< NodeT *> &	Result
	)		const

inline

Get all nodes dominated by R, including R itself.

Definition at line 352 of file GenericDomTree.h.

◆ getNode()

template<typename NodeT, bool IsPostDom>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode ( const NodeT * BB ) const

inline

getNode - return the (Post)DominatorTree node for the specified basic block.

This is the same as using operator[] on this class. The result may (but is not required to) be null for a forward (backwards) statically unreachable block.

Definition at line 329 of file GenericDomTree.h.

Referenced by llvm::MemorySSAUpdater::applyInsertUpdates(), llvm::DomTreeUpdater::callbackDeleteBB(), checkHoistValue(), CloneLoopBlocks(), cloneLoopBlocks(), llvm::cloneLoopWithPreheader(), computeBlocksDominatingExits(), llvm::DivergencePropagator::computeJoinPoints(), containsUnconditionalCallSafepoint(), llvm::createLICMPass(), deleteDeadBlocksFromLoop(), llvm::OrderedInstructions::dfsBefore(), llvm::CodeExtractor::findInputsOutputs(), llvm::foldBlockIntoPredecessor(), llvm::formLCSSAForInstructions(), llvm::MachinePostDominatorTree::getNode(), llvm::SSAUpdaterBulk::HasValueForBlock(), llvm::hoistRegion(), isProfitableChain(), isSimplifiedLoopNest(), mayUsePostIncMode(), llvm::MachinePostDominatorTree::operator[](), preheader(), llvm::GVNHoist::rank(), llvm::GuardWideningPass::run(), shouldSplitOnPredicatedArgument(), SinkInstruction(), llvm::sinkRegion(), llvm::SplitBlock(), llvm::SplitBlockAndInsertIfThen(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), and llvm::UnrollRuntimeLoopRemainder().

◆ getRoot()

template<typename NodeT, bool IsPostDom>

NodeT* llvm::DominatorTreeBase< NodeT, IsPostDom >::getRoot ( ) const

inline

Definition at line 439 of file GenericDomTree.h.

Referenced by llvm::ForwardDominanceFrontierBase< BasicBlock >::analyze(), llvm::isAllocaPromotable(), and nearest_common_dominatee().

◆ getRootNode() [1/2]

template<typename NodeT, bool IsPostDom>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT, IsPostDom >::getRootNode ( )

inline

getRootNode - This returns the entry node for the CFG of the function.

If this tree represents the post-dominance relations for a function, however, this root may be a node with the block == NULL. This is the case when there are multiple exit nodes from a particular function. Consumers of post-dominance information must be capable of dealing with this possibility.

Definition at line 348 of file GenericDomTree.h.

Referenced by llvm::LoopInfoBase< BasicBlock, Loop >::analyze(), llvm::GraphTraits< PostDominatorTree * >::getEntryNode(), llvm::GraphTraits< DominatorTree * >::getEntryNode(), llvm::MachinePostDominatorTree::getRootNode(), llvm::GuardWideningPass::run(), UpdateAnalysisInformation(), and llvm::MachineDominatorTree::verifyAnalysis().

◆ getRootNode() [2/2]

template<typename NodeT, bool IsPostDom>

const DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT, IsPostDom >::getRootNode ( ) const

inline

Definition at line 349 of file GenericDomTree.h.

◆ getRoots()

template<typename NodeT, bool IsPostDom>

const SmallVectorImpl<NodeT *>& llvm::DominatorTreeBase< NodeT, IsPostDom >::getRoots ( ) const

inline

getRoots - Return the root blocks of the current CFG.

This may include multiple blocks if we are computing post dominators. For forward dominators, this will always be a single block (the entry node).

Definition at line 285 of file GenericDomTree.h.

Referenced by llvm::ForwardDominanceFrontierBase< BasicBlock >::analyze(), and llvm::MachinePostDominatorTree::getRoots().

◆ insertEdge()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::insertEdge	(	NodeT *	From,
		NodeT *	To
	)

inline

Inform the dominator tree about a CFG edge insertion and update the tree.

This function has to be called just before or just after making the update on the actual CFG. There cannot be any other updates that the dominator tree doesn't know about.

Note that for postdominators it automatically takes care of inserting a reverse edge internally (so there's no need to swap the parameters).

Definition at line 534 of file GenericDomTree.h.

Referenced by llvm::DomTreeUpdater::insertEdge(), llvm::DomTreeUpdater::insertEdgeRelaxed(), and unswitchTrivialBranch().

◆ isPostDominator()

template<typename NodeT, bool IsPostDom>

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::isPostDominator ( ) const

inline

isPostDominator - Returns true if analysis based of postdoms

Definition at line 289 of file GenericDomTree.h.

◆ isReachableFromEntry() [1/2]

template<typename NodeT, bool IsPostDom>

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

inline

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

Definition at line 383 of file GenericDomTree.h.

Referenced by llvm::LoopInfoBase< BasicBlock, Loop >::analyze(), and llvm::discoverAndMapSubloop().

◆ isReachableFromEntry() [2/2]

template<typename NodeT, bool IsPostDom>

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

inline

Definition at line 389 of file GenericDomTree.h.

◆ isVirtualRoot()

template<typename NodeT, bool IsPostDom>

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::isVirtualRoot ( const DomTreeNodeBase< NodeT > * A ) const

inline

Definition at line 483 of file GenericDomTree.h.

◆ operator=() [1/2]

template<typename NodeT, bool IsPostDom>

DominatorTreeBase& llvm::DominatorTreeBase< NodeT, IsPostDom >::operator= ( DominatorTreeBase< NodeT, IsPostDom > && RHS )

inline

Definition at line 267 of file GenericDomTree.h.

◆ operator=() [2/2]

template<typename NodeT, bool IsPostDom>

DominatorTreeBase& llvm::DominatorTreeBase< NodeT, IsPostDom >::operator= ( const DominatorTreeBase< NodeT, IsPostDom > & )

delete

◆ operator[]()

template<typename NodeT, bool IsPostDom>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT, IsPostDom >::operator[] ( const NodeT * BB ) const

inline

See getNode.

Definition at line 337 of file GenericDomTree.h.

◆ print()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::print ( raw_ostream & O ) const

inline

print - Convert to human readable form

Definition at line 661 of file GenericDomTree.h.

Referenced by llvm::PostDominatorTreeWrapperPass::print(), llvm::PostDominatorTreeWrapperPass::releaseMemory(), and llvm::MachineDominatorTree::verifyAnalysis().

◆ properlyDominates() [1/2]

template<typename NodeT, bool IsPostDom>

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates	(	const DomTreeNodeBase< NodeT > *	A,
		const DomTreeNodeBase< NodeT > *	B
	)		const

inline

properlyDominates - Returns true iff A dominates B and A != B.

Note that this is not a constant time operation!

Definition at line 370 of file GenericDomTree.h.

Referenced by llvm::ForwardDominanceFrontierBase< BasicBlock >::calculate(), ConstructSSAForLoadSet(), llvm::ScalarEvolution::getBlockDisposition(), isAlwaysFoldable(), isLoadInvariantInLoop(), isLoopInvariant(), llvm::MachinePostDominatorTree::properlyDominates(), llvm::GVNHoist::rank(), llvm::replaceDominatedUsesWith(), and llvm::InnerLoopVectorizer::updateAnalysis().

◆ properlyDominates() [2/2]

template<typename NodeT, bool IsPostDom>

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::properlyDominates	(	const NodeT *	A,
		const NodeT *	B
	)		const

Definition at line 879 of file GenericDomTree.h.

◆ recalculate() [1/2]

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate ( ParentType & Func )

inline

recalculate - compute a dominator tree for the given function

Definition at line 732 of file GenericDomTree.h.

Referenced by AddAliasScopeMetadata(), AddAlignmentAssumptions(), enableCallSafepoints(), GetGlobalTypeString(), getSignature(), hasProfileData(), llvm::OptimizationRemarkEmitter::OptimizationRemarkEmitter(), llvm::PostDominatorTree::PostDominatorTree(), llvm::DomTreeUpdater::recalculate(), llvm::DominatorTreeAnalysis::run(), llvm::PostDominatorTreeWrapperPass::runOnFunction(), and llvm::MachineDominatorTree::verifyAnalysis().

◆ recalculate() [2/2]

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate	(	ParentType &	Func,
		ArrayRef< UpdateType >	Updates
	)

inline

Definition at line 737 of file GenericDomTree.h.

◆ releaseMemory()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::releaseMemory ( )

inline

Definition at line 323 of file GenericDomTree.h.

Referenced by llvm::PostDominatorTreeWrapperPass::releaseMemory(), and llvm::DominatorTreeWrapperPass::releaseMemory().

◆ reset()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::reset ( )

inlineprotected

Definition at line 763 of file GenericDomTree.h.

Referenced by llvm::JumpThreadingPass::run(), and updatePredecessorProfileMetadata().

◆ setNewRoot()

template<typename NodeT, bool IsPostDom>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT, IsPostDom >::setNewRoot ( NodeT * BB )

inline

Add a new node to the forward dominator tree and make it a new root.

Parameters

BB	New node in CFG.

Returns: New dominator tree node that represents new CFG node.

Definition at line 583 of file GenericDomTree.h.

Referenced by UpdateAnalysisInformation().

◆ Split()

template<typename NodeT, bool IsPostDom>

template<class N >

void llvm::DominatorTreeBase< NodeT, IsPostDom >::Split ( typename GraphTraits< N >::NodeRef NewBB )

inlineprotected

Definition at line 775 of file GenericDomTree.h.

◆ splitBlock()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::splitBlock ( NodeT * NewBB )

inline

splitBlock - BB is split and now it has one successor.

Update dominator tree to reflect this change.

Definition at line 652 of file GenericDomTree.h.

Referenced by insertUniqueBackedgeBlock(), and UpdateAnalysisInformation().

◆ updateDFSNumbers()

template<typename NodeT, bool IsPostDom>

void llvm::DominatorTreeBase< NodeT, IsPostDom >::updateDFSNumbers ( ) const

inline

updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.

Definition at line 686 of file GenericDomTree.h.

◆ verify()

template<typename NodeT, bool IsPostDom>

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::verify ( VerificationLevel VL = VerificationLevel::Full ) const

inline

verify - checks if the tree is correct.

There are 3 level of verification:

Full – verifies if the tree is correct by making sure all the properties (including the parent and the sibling property) hold. Takes O(N^3) time.
Basic – checks if the tree is correct, but compares it to a freshly constructed tree instead of checking the sibling property. Takes O(N^2) time.
Fast – checks basic tree structure and compares it with a freshly constructed tree. Takes O(N^2) time worst case, but is faster in practise (same as tree construction).

Definition at line 756 of file GenericDomTree.h.

Referenced by getOnlyLiveSuccessor(), llvm::hoistRegion(), llvm::peelLoop(), llvm::SimpleLoopUnswitchPass::run(), runImpl(), llvm::UnrollAndJamLoop(), llvm::UnrollLoop(), llvm::UnrollRuntimeLoopRemainder(), unswitchNontrivialInvariants(), unswitchTrivialSwitch(), llvm::InnerLoopVectorizer::updateAnalysis(), and llvm::PostDominatorTreeWrapperPass::verifyAnalysis().

Friends And Related Function Documentation

◆ DomTreeBuilder::SemiNCAInfo< DominatorTreeBase >

template<typename NodeT, bool IsPostDom>

friend struct DomTreeBuilder::SemiNCAInfo< DominatorTreeBase >

friend

Definition at line 252 of file GenericDomTree.h.

Member Data Documentation

◆ Delete

template<typename NodeT, bool IsPostDom>

constexpr UpdateKind llvm::DominatorTreeBase< NodeT, IsPostDom >::Delete = UpdateKind::Delete

static

Definition at line 235 of file GenericDomTree.h.

Referenced by unswitchTrivialSwitch().

◆ DFSInfoValid

template<typename NodeT, bool IsPostDom>

bool llvm::DominatorTreeBase< NodeT, IsPostDom >::DFSInfoValid = false

mutableprotected

Definition at line 249 of file GenericDomTree.h.

◆ DomTreeNodes

template<typename NodeT, bool IsPostDom>

DomTreeNodeMapType llvm::DominatorTreeBase< NodeT, IsPostDom >::DomTreeNodes

protected

Definition at line 245 of file GenericDomTree.h.

Referenced by llvm::DominatorTreeBase< BasicBlock, false >::compare().

◆ Insert

template<typename NodeT, bool IsPostDom>

constexpr UpdateKind llvm::DominatorTreeBase< NodeT, IsPostDom >::Insert = UpdateKind::Insert

static

Definition at line 234 of file GenericDomTree.h.

Referenced by llvm::MemorySSAUpdater::applyUpdates(), unswitchTrivialSwitch(), and llvm::MemorySSAUpdater::updateForClonedBlockIntoPred().

◆ IsPostDominator

template<typename NodeT, bool IsPostDom>

constexpr bool llvm::DominatorTreeBase< NodeT, IsPostDom >::IsPostDominator = IsPostDom

static

Definition at line 230 of file GenericDomTree.h.

◆ Parent

template<typename NodeT, bool IsPostDom>

ParentPtr llvm::DominatorTreeBase< NodeT, IsPostDom >::Parent = nullptr

protected

Definition at line 247 of file GenericDomTree.h.

Referenced by llvm::DominatorTreeBase< BasicBlock, false >::compare(), and llvm::DominatorTree::DominatorTree().

◆ RootNode

template<typename NodeT, bool IsPostDom>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT, IsPostDom >::RootNode

protected

Definition at line 246 of file GenericDomTree.h.

◆ Roots

template<typename NodeT, bool IsPostDom>

SmallVector<NodeT *, IsPostDom ? 4 : 1> llvm::DominatorTreeBase< NodeT, IsPostDom >::Roots

protected

Definition at line 241 of file GenericDomTree.h.

Referenced by llvm::DominatorTreeBase< BasicBlock, false >::compare().

◆ SlowQueries

template<typename NodeT, bool IsPostDom>

unsigned int llvm::DominatorTreeBase< NodeT, IsPostDom >::SlowQueries = 0

mutableprotected

Definition at line 250 of file GenericDomTree.h.

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

include/llvm/Analysis/LoopInfo.h
include/llvm/Support/GenericDomTree.h

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Friends

Detailed Description

template<typename NodeT, bool IsPostDom> class llvm::DominatorTreeBase< NodeT, IsPostDom >

Member Typedef Documentation

◆ DomTreeNodeMapType

◆ NodePtr

◆ NodeType

◆ ParentPtr

◆ ParentType

◆ UpdateKind

◆ UpdateType

Member Enumeration Documentation

◆ VerificationLevel

Constructor & Destructor Documentation

◆ DominatorTreeBase() [1/3]

◆ DominatorTreeBase() [2/3]

◆ DominatorTreeBase() [3/3]

Member Function Documentation

◆ addNewBlock()

◆ addRoot() [1/2]

◆ addRoot() [2/2]

◆ applyUpdates()

◆ changeImmediateDominator() [1/2]

◆ changeImmediateDominator() [2/2]

◆ compare()

◆ deleteEdge()

◆ dominates() [1/2]

◆ dominates() [2/2]

◆ eraseNode()

◆ findNearestCommonDominator() [1/2]

◆ findNearestCommonDominator() [2/2]

◆ getDescendants()

◆ getNode()

◆ getRoot()

◆ getRootNode() [1/2]

◆ getRootNode() [2/2]

◆ getRoots()

◆ insertEdge()

◆ isPostDominator()

◆ isReachableFromEntry() [1/2]

◆ isReachableFromEntry() [2/2]

◆ isVirtualRoot()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]()

◆ print()

◆ properlyDominates() [1/2]

◆ properlyDominates() [2/2]

◆ recalculate() [1/2]

◆ recalculate() [2/2]

◆ releaseMemory()

◆ reset()

◆ setNewRoot()

◆ Split()

◆ splitBlock()

◆ updateDFSNumbers()

◆ verify()

Friends And Related Function Documentation

◆ DomTreeBuilder::SemiNCAInfo< DominatorTreeBase >

Member Data Documentation

◆ Delete

◆ DFSInfoValid

◆ DomTreeNodes

◆ Insert

◆ IsPostDominator

◆ Parent

◆ RootNode

◆ Roots

◆ SlowQueries

template<typename NodeT, bool IsPostDom>
class llvm::DominatorTreeBase< NodeT, IsPostDom >