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

#include "llvm/CodeGen/MachineDominators.h"

Inheritance diagram for llvm::MachineDominatorTree:

Public Types
using	Base = DomTreeBase< MachineBasicBlock >

Public Types inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
enum class	VerificationLevel { Fast , Basic , Full }

using	NodeTrait = DomTreeNodeTraits< NodeT >

using	NodeType = typename NodeTrait::NodeType

using	NodePtr = typename NodeTrait::NodePtr

using	ParentPtr = typename NodeTrait::ParentPtr

using	ParentType = std::remove_pointer_t< ParentPtr >

using	UpdateType = cfg::Update< NodePtr >

using	UpdateKind = cfg::UpdateKind

using	root_iterator = typename SmallVectorImpl< NodeT * >::iterator
	Iteration over roots.

using	const_root_iterator = typename SmallVectorImpl< NodeT * >::const_iterator

Public Member Functions
	MachineDominatorTree ()=default

	MachineDominatorTree (MachineFunction &MF)

bool	invalidate (MachineFunction &, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &)
	Handle invalidation explicitly.

MachineDominatorTree &	getBase ()

MachineBasicBlock *	getRoot () const

MachineDomTreeNode *	getRootNode () const

void	calculate (MachineFunction &F)

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

void	getDescendants (MachineBasicBlock A, SmallVectorImpl< MachineBasicBlock > &Result)

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

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

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

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

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

MachineDomTreeNode *	operator[] (MachineBasicBlock *BB) const

MachineDomTreeNode *	getNode (MachineBasicBlock *BB) const
	getNode - return the (Post)DominatorTree node for the specified basic block.

MachineDomTreeNode *	addNewBlock (MachineBasicBlock BB, MachineBasicBlock DomBB)
	addNewBlock - Add a new node to the dominator tree information.

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

void	changeImmediateDominator (MachineDomTreeNode N, MachineDomTreeNode NewIDom)

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

void	splitBlock (MachineBasicBlock *NewBB)
	splitBlock - BB is split and now it has one successor.

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

void	recordSplitCriticalEdge (MachineBasicBlock FromBB, MachineBasicBlock ToBB, MachineBasicBlock *NewBB)
	Record that the critical edge (FromBB, ToBB) has been split with NewBB.

Public Member Functions inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
	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< NodeT > *	getNode (const NodeT *BB) const
	getNode - return the (Post)DominatorTree node for the specified basic block.

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

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

const DomTreeNodeBase< NodeT > *	getRootNode () const

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

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

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.

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.

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

NodeT *	getRoot () const

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

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.

void	applyUpdates (ArrayRef< UpdateType > Updates, ArrayRef< UpdateType > PostViewUpdates)

void	insertEdge (NodeT From, NodeT To)
	Inform the dominator tree about a CFG edge insertion and update the tree.

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

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

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

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.

void	changeImmediateDominator (NodeT BB, NodeT NewBB)

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

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

template<typename T = NodeT>
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< NodeT, IsPostDom >
static constexpr bool	IsPostDominator = IsPostDom

static constexpr UpdateKind	Insert = UpdateKind::Insert

static constexpr UpdateKind	Delete = UpdateKind::Delete

Protected Types inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
using	DomTreeNodeStorageTy = SmallVector< std::unique_ptr< DomTreeNodeBase< NodeT > > >

Protected Member Functions inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
void	addRoot (NodeT *BB)

DomTreeNodeBase< NodeT > *	createNode (NodeT BB, DomTreeNodeBase< NodeT > IDom=nullptr)

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

void	addRoot (MachineBasicBlock *MBB)

Protected Attributes inherited from llvm::DominatorTreeBase< NodeT, IsPostDom >
SmallVector< NodeT *, IsPostDom ? 4 :1 >	Roots

DomTreeNodeStorageTy	DomTreeNodes

std::conditional_t<!GraphHasNodeNumbers< NodeT * >, DenseMap< const NodeT *, unsigned >, std::tuple<> >	NodeNumberMap

DomTreeNodeBase< NodeT > *	RootNode = nullptr

ParentPtr	Parent = nullptr

bool	DFSInfoValid = false

unsigned int	SlowQueries = 0

unsigned	BlockNumberEpoch = 0

Detailed Description

DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Definition at line 75 of file MachineDominators.h.

Member Typedef Documentation

◆ Base

using llvm::MachineDominatorTree::Base = DomTreeBase<MachineBasicBlock>

Definition at line 106 of file MachineDominators.h.

Constructor & Destructor Documentation

◆ MachineDominatorTree() [1/2]

llvm::MachineDominatorTree::MachineDominatorTree ( )

default

◆ MachineDominatorTree() [2/2]

llvm::MachineDominatorTree::MachineDominatorTree ( MachineFunction & MF )

inlineexplicit

Definition at line 109 of file MachineDominators.h.

Member Function Documentation

◆ addNewBlock()

MachineDomTreeNode * llvm::MachineDominatorTree::addNewBlock	(	MachineBasicBlock *	BB,
		MachineBasicBlock *	DomBB
	)

inline

addNewBlock - 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.

Definition at line 204 of file MachineDominators.h.

Referenced by loadMBUFScalarOperandsFromVGPR().

◆ calculate()

void MachineDominatorTree::calculate ( MachineFunction & F )

Definition at line 98 of file MachineDominators.cpp.

References llvm::SmallVectorImpl< T >::clear(), F, and llvm::DominatorTreeBase< NodeT, IsPostDom >::recalculate().

◆ changeImmediateDominator() [1/2]

void llvm::MachineDominatorTree::changeImmediateDominator	(	MachineBasicBlock *	N,
		MachineBasicBlock *	NewIDom
	)

inline

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

Definition at line 213 of file MachineDominators.h.

References N.

Referenced by loadMBUFScalarOperandsFromVGPR().

◆ changeImmediateDominator() [2/2]

void llvm::MachineDominatorTree::changeImmediateDominator	(	MachineDomTreeNode *	N,
		MachineDomTreeNode *	NewIDom
	)

inline

Definition at line 219 of file MachineDominators.h.

References N.

◆ dominates() [1/3]

bool llvm::MachineDominatorTree::dominates	(	const MachineBasicBlock *	A,
		const MachineBasicBlock *	B
	)		const

inline

Definition at line 147 of file MachineDominators.h.

References A, and B.

◆ dominates() [2/3]

bool llvm::MachineDominatorTree::dominates	(	const MachineDomTreeNode *	A,
		const MachineDomTreeNode *	B
	)		const

inline

Definition at line 135 of file MachineDominators.h.

References A, and B.

Referenced by llvm::CombinerHelper::dominates(), dominatesAllUsesOf(), hoistAndMergeSGPRInits(), INITIALIZE_PASS(), isReachable(), isReachableAmongDominated(), oneUseDominatesOtherUses(), replaceDominatedUses(), and sortBlocks().

◆ dominates() [3/3]

bool llvm::MachineDominatorTree::dominates	(	const MachineInstr *	A,
		const MachineInstr *	B
	)		const

inline

Definition at line 154 of file MachineDominators.h.

References A, B, llvm::MachineBasicBlock::begin(), and I.

◆ eraseNode()

void llvm::MachineDominatorTree::eraseNode ( MachineBasicBlock * 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 228 of file MachineDominators.h.

◆ findNearestCommonDominator()

MachineBasicBlock * llvm::MachineDominatorTree::findNearestCommonDominator	(	MachineBasicBlock *	A,
		MachineBasicBlock *	B
	)

inline

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

If there is no such block then return NULL.

Definition at line 182 of file MachineDominators.h.

References A, and B.

Referenced by hoistAndMergeSGPRInits().

◆ getBase()

MachineDominatorTree & llvm::MachineDominatorTree::getBase ( )

inline

Definition at line 118 of file MachineDominators.h.

Referenced by llvm::MachineLoopInfo::calculate(), llvm::AsmPrinter::emitFunctionBody(), llvm::PhiLoweringHelper::lowerPhis(), llvm::AMDGPURegBankSelect::runOnMachineFunction(), and splitBlock().

◆ getDescendants()

void llvm::MachineDominatorTree::getDescendants	(	MachineBasicBlock *	A,
		SmallVectorImpl< MachineBasicBlock * > &	Result
	)

inline

Definition at line 141 of file MachineDominators.h.

References A.

◆ getNode()

MachineDomTreeNode * llvm::MachineDominatorTree::getNode ( MachineBasicBlock * BB ) const

inline

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

This is the same as using operator[] on this class.

Definition at line 196 of file MachineDominators.h.

Referenced by llvm::rdf::Liveness::getNearestAliasedRef(), and llvm::PhiLoweringHelper::lowerPhis().

◆ getRoot()

MachineBasicBlock * llvm::MachineDominatorTree::getRoot ( ) const

inline

Definition at line 123 of file MachineDominators.h.

◆ getRootNode()

MachineDomTreeNode * llvm::MachineDominatorTree::getRootNode ( ) const

inline

Definition at line 128 of file MachineDominators.h.

Referenced by llvm::GraphTraits< MachineDominatorTree * >::getEntryNode().

◆ invalidate()

bool MachineDominatorTree::invalidate	(	MachineFunction &	,
		const PreservedAnalyses &	PA,
		MachineFunctionAnalysisManager::Invalidator &
	)

Handle invalidation explicitly.

Definition at line 60 of file MachineDominators.cpp.

References llvm::PreservedAnalyses::getChecker().

◆ isReachableFromEntry()

bool llvm::MachineDominatorTree::isReachableFromEntry ( const MachineBasicBlock * A )

inline

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

Definition at line 242 of file MachineDominators.h.

References A.

◆ operator[]()

MachineDomTreeNode * llvm::MachineDominatorTree::operator[] ( MachineBasicBlock * BB ) const

inline

Definition at line 188 of file MachineDominators.h.

◆ properlyDominates() [1/2]

bool llvm::MachineDominatorTree::properlyDominates	(	const MachineBasicBlock *	A,
		const MachineBasicBlock *	B
	)		const

inline

Definition at line 174 of file MachineDominators.h.

References A, and B.

◆ properlyDominates() [2/2]

bool llvm::MachineDominatorTree::properlyDominates	(	const MachineDomTreeNode *	A,
		const MachineDomTreeNode *	B
	)		const

inline

Definition at line 168 of file MachineDominators.h.

References A, and B.

Referenced by llvm::rdf::Liveness::getAllReachingDefs(), hoistAndMergeSGPRInits(), and loadMBUFScalarOperandsFromVGPR().

◆ recordSplitCriticalEdge()

void llvm::MachineDominatorTree::recordSplitCriticalEdge	(	MachineBasicBlock *	FromBB,
		MachineBasicBlock *	ToBB,
		MachineBasicBlock *	NewBB
	)

inline

Record that the critical edge (FromBB, ToBB) has been split with NewBB.

This is best to use this method instead of directly update the underlying information, because this helps mitigating the number of time the DT information is invalidated.

Note: Do not use this method with regular edges.; To benefit from the compile time improvement incurred by this method, the users of this method have to limit the queries to the DT interface between two edges splitting. In other words, they have to pack the splitting of critical edges as much as possible.

Definition at line 259 of file MachineDominators.h.

References assert(), llvm::SmallSet< T, N, C >::insert(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

◆ splitBlock()

void llvm::MachineDominatorTree::splitBlock ( MachineBasicBlock * NewBB )

inline

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

Update dominator tree to reflect this change.

Definition at line 235 of file MachineDominators.h.

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

include/llvm/CodeGen/MachineDominators.h
lib/CodeGen/MachineDominators.cpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

Constructor & Destructor Documentation

◆ MachineDominatorTree() [1/2]

◆ MachineDominatorTree() [2/2]

Member Function Documentation

◆ addNewBlock()

◆ calculate()

◆ changeImmediateDominator() [1/2]

◆ changeImmediateDominator() [2/2]

◆ dominates() [1/3]

◆ dominates() [2/3]

◆ dominates() [3/3]

◆ eraseNode()

◆ findNearestCommonDominator()

◆ getBase()

◆ getDescendants()

◆ getNode()

◆ getRoot()

◆ getRootNode()

◆ invalidate()

◆ isReachableFromEntry()

◆ operator[]()

◆ properlyDominates() [1/2]

◆ properlyDominates() [2/2]

◆ recordSplitCriticalEdge()

◆ splitBlock()