llvm::DominatorTreeBase< NodeT > Class Template Reference

#include <Dominators.h>

Inheritance diagram for llvm::DominatorTreeBase< NodeT >:

Collaboration diagram for llvm::DominatorTreeBase< NodeT >:

Classes
struct	InfoRec

Public Member Functions
	DominatorTreeBase (bool isPostDom)
virtual	~DominatorTreeBase ()
bool	compare (DominatorTreeBase &Other) const
virtual void	releaseMemory ()
DomTreeNodeBase< NodeT > *	getNode (NodeT *BB) const
DomTreeNodeBase< NodeT > *	getRootNode ()
const DomTreeNodeBase< NodeT > *	getRootNode () const
void	getDescendants (NodeT *R, SmallVectorImpl< NodeT * > &Result) const
	Get all nodes dominated by R, including R itself. Return true on success. More...
bool	properlyDominates (const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B)
bool	properlyDominates (const NodeT *A, const NodeT *B)
bool	isReachableFromEntry (const NodeT *A) const
bool	isReachableFromEntry (const DomTreeNodeBase< NodeT > *A) const
bool	dominates (const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B)
bool	dominates (const NodeT *A, const NodeT *B)
NodeT *	getRoot () const
NodeT *	findNearestCommonDominator (NodeT *A, NodeT *B)
const NodeT *	findNearestCommonDominator (const NodeT *A, const NodeT *B)
DomTreeNodeBase< NodeT > *	addNewBlock (NodeT *BB, NodeT *DomBB)
void	changeImmediateDominator (DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
void	changeImmediateDominator (NodeT *BB, NodeT *NewBB)
void	eraseNode (NodeT *BB)
void	removeNode (NodeT *BB)
void	splitBlock (NodeT *NewBB)
void	print (raw_ostream &o) const
template<class FT >
void	recalculate (FT &F)
	recalculate - compute a dominator tree for the given function More...
Public Member Functions inherited from llvm::DominatorBase< NodeT >
const std::vector< NodeT * > &	getRoots () const
bool	isPostDominator () const

Protected Types
typedef DenseMap< NodeT *, DomTreeNodeBase< NodeT > * >	DomTreeNodeMapType

Protected Member Functions
void	reset ()
template<class N , class GraphT >
void	Split (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *NewBB)
void	updateDFSNumbers ()
DomTreeNodeBase< NodeT > *	getNodeForBlock (NodeT *BB)
NodeT *	getIDom (NodeT *BB) const
void	addRoot (NodeT *BB)
template<>
void	addRoot (MachineBasicBlock *MBB)
Protected Member Functions inherited from llvm::DominatorBase< NodeT >
	DominatorBase (bool isPostDom)

Protected Attributes
DomTreeNodeMapType	DomTreeNodes
DomTreeNodeBase< NodeT > *	RootNode
bool	DFSInfoValid
unsigned int	SlowQueries
DenseMap< NodeT *, NodeT * >	IDoms
std::vector< NodeT * >	Vertex
DenseMap< NodeT *, InfoRec >	Info
Protected Attributes inherited from llvm::DominatorBase< NodeT >
std::vector< NodeT * >	Roots
const bool	IsPostDominators

Friends
template<class GraphT >
GraphT::NodeType *	Eval (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *V, unsigned LastLinked)
template<class GraphT >
unsigned	DFSPass (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *V, unsigned N)
template<class FuncT , class N >
void	Calculate (DominatorTreeBase< typename GraphTraits< N >::NodeType > &DT, FuncT &F)

Detailed Description

template<class NodeT>
class llvm::DominatorTreeBase< NodeT >

Definition at line 59 of file Dominators.h.

Member Typedef Documentation

template<class NodeT>

typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> llvm::DominatorTreeBase< NodeT >::DomTreeNodeMapType

protected

Definition at line 201 of file Dominators.h.

Constructor & Destructor Documentation

template<class NodeT>

llvm::DominatorTreeBase< NodeT >::DominatorTreeBase ( bool  isPostDom )

inlineexplicit

Definition at line 300 of file Dominators.h.

template<class NodeT>

virtual llvm::DominatorTreeBase< NodeT >::~DominatorTreeBase ( )

inlinevirtual

Definition at line 302 of file Dominators.h.

Member Function Documentation

template<class NodeT>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::addNewBlock ( NodeT *  BB, NodeT *  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 495 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::Split().

template<>

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

inlineprotected

Definition at line 27 of file MachineDominators.h.

template<class NodeT>

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

inlineprotected

Definition at line 656 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::recalculate().

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::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 507 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::changeImmediateDominator(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::Split().

template<class NodeT>

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

inline

Definition at line 514 of file Dominators.h.

template<class NodeT>

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

inline

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

Definition at line 306 of file Dominators.h.

template<class NodeT>

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

inline

dominates - Returns true iff A dominates B. Note that this is not a constant time operation!

Definition at line 392 of file Dominators.h.

Referenced by llvm::LoopInfoBase< N, M >::Analyze(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::findNearestCommonDominator(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::properlyDominates(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::Split().

template<class NodeT>

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

Definition at line 696 of file Dominators.h.

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::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 521 of file Dominators.h.

template<class NodeT>

NodeT* llvm::DominatorTreeBase< NodeT >::findNearestCommonDominator ( NodeT *  A, NodeT *  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 437 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::findNearestCommonDominator(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::Split().

template<class NodeT>

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

inline

Definition at line 481 of file Dominators.h.

template<class NodeT>

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

inline

Get all nodes dominated by R, including R itself. Return true on success.

Definition at line 350 of file Dominators.h.

template<class NodeT>

NodeT* llvm::DominatorTreeBase< NodeT >::getIDom ( NodeT *  BB ) const

inlineprotected

Definition at line 652 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getNodeForBlock().

template<class NodeT>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getNode ( 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.

Definition at line 335 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::addNewBlock(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::changeImmediateDominator(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::eraseNode(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::findNearestCommonDominator(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getDescendants(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getNodeForBlock(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::isReachableFromEntry(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::removeNode(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::Split().

template<class NodeT>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getNodeForBlock ( NodeT *  BB )

inlineprotected

Definition at line 635 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getNodeForBlock().

template<class NodeT>

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

inline

Definition at line 430 of file Dominators.h.

template<class NodeT>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::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 346 of file Dominators.h.

Referenced by llvm::LoopInfoBase< N, M >::Analyze(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::print(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::updateDFSNumbers().

template<class NodeT>

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

inline

Definition at line 347 of file Dominators.h.

template<class NodeT>

bool llvm::DominatorTreeBase< NodeT >::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 379 of file Dominators.h.

Referenced by llvm::LoopInfoBase< N, M >::Analyze(), llvm::discoverAndMapSubloop(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::isReachableFromEntry(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::Split().

template<class NodeT>

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

inline

Definition at line 385 of file Dominators.h.

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::print ( raw_ostream &  o ) const

inline

print - Convert to human readable form

Definition at line 560 of file Dominators.h.

template<class NodeT>

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

inline

properlyDominates - Returns true iff A dominates B and A != B. Note that this is not a constant time operation!

Definition at line 366 of file Dominators.h.

template<class NodeT>

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

Definition at line 708 of file Dominators.h.

template<class NodeT>

template<class FT >

void llvm::DominatorTreeBase< NodeT >::recalculate ( FT &  F )

inline

recalculate - compute a dominator tree for the given function

Definition at line 663 of file Dominators.h.

template<class NodeT>

virtual void llvm::DominatorTreeBase< NodeT >::releaseMemory ( )

inlinevirtual

Definition at line 330 of file Dominators.h.

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::removeNode ( NodeT *  BB )

inline

removeNode - Removes a node from the dominator tree. Block must not dominate any other blocks. Invalidates any node pointing to removed block.

Definition at line 544 of file Dominators.h.

template<class NodeT>

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

inlineprotected

Definition at line 225 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::recalculate(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::releaseMemory(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::~DominatorTreeBase().

template<class NodeT>

template<class N , class GraphT >

void llvm::DominatorTreeBase< NodeT >::Split ( DominatorTreeBase< typename GraphT::NodeType > &  DT, typename GraphT::NodeType *  NewBB  )

inlineprotected

Definition at line 239 of file Dominators.h.

template<class NodeT>

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

inline

splitBlock - BB is split and now it has one successor. Update dominator tree to reflect this change.

Definition at line 551 of file Dominators.h.

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::updateDFSNumbers ( )

inlineprotected

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

Definition at line 593 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::dominates().

Friends And Related Function Documentation

template<class NodeT>

template<class FuncT , class N >

void Calculate ( DominatorTreeBase< typename GraphTraits< N >::NodeType > &  DT, FuncT &  F  )

friend

DominatorTree - Calculate the immediate dominator tree for a function.

template<class NodeT>

template<class GraphT >

unsigned DFSPass ( DominatorTreeBase< typename GraphT::NodeType > &  DT, typename GraphT::NodeType *  V, unsigned  N  )

friend

Definition at line 34 of file DominatorInternals.h.

template<class NodeT>

template<class GraphT >

GraphT::NodeType* Eval ( DominatorTreeBase< typename GraphT::NodeType > &  DT, typename GraphT::NodeType *  V, unsigned  LastLinked  )

friend

Definition at line 108 of file DominatorInternals.h.

Member Data Documentation

template<class NodeT>

bool llvm::DominatorTreeBase< NodeT >::DFSInfoValid

protected

Definition at line 205 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::addNewBlock(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::changeImmediateDominator(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::print(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::updateDFSNumbers().

template<class NodeT>

DomTreeNodeMapType llvm::DominatorTreeBase< NodeT >::DomTreeNodes

protected

Definition at line 202 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::addNewBlock(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::compare(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::eraseNode(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getNode(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getNodeForBlock(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::recalculate(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::removeNode(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::reset().

template<class NodeT>

DenseMap<NodeT*, NodeT*> llvm::DominatorTreeBase< NodeT >::IDoms

protected

Definition at line 217 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getIDom(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::recalculate(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::reset().

template<class NodeT>

DenseMap<NodeT*, InfoRec> llvm::DominatorTreeBase< NodeT >::Info

protected

Definition at line 223 of file Dominators.h.

Referenced by llvm::DFSPass(), and llvm::Eval().

template<class NodeT>

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

protected

Definition at line 203 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::getRootNode(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::reset().

template<class NodeT>

unsigned int llvm::DominatorTreeBase< NodeT >::SlowQueries

protected

Definition at line 206 of file Dominators.h.

Referenced by llvm::DominatorTreeBase< llvm::MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::print(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::updateDFSNumbers().

template<class NodeT>

std::vector<NodeT*> llvm::DominatorTreeBase< NodeT >::Vertex

protected

Definition at line 220 of file Dominators.h.

Referenced by llvm::DFSPass(), llvm::Eval(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::recalculate(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::reset().

---

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

• Dominators.h