llvm::DominatorTreeBase< NodeT > Class Template Reference

#include <Dominators.h>

Inheritance diagram for llvm::DominatorTreeBase< NodeT >:

Collaboration diagram for llvm::DominatorTreeBase< NodeT >:

List of all members.

Public Member Functions

DominatorTreeBase (bool isPostDom)

virtual ~DominatorTreeBase ()

virtual bool runOnFunction (Function &F)

bool compare (DominatorTreeBase &Other) const

virtual void releaseMemory ()

DomTreeNodeBase< NodeT > * getNode (NodeT *BB) const

DomTreeNodeBase< NodeT > * getRootNode ()

const DomTreeNodeBase< NodeT > * getRootNode () const

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

bool properlyDominates (NodeT *A, NodeT *B)

bool dominatedBySlowTreeWalk (const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const

bool isReachableFromEntry (NodeT *A)

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

bool dominates (NodeT *A, NodeT *B)

NodeT * getRoot () const

NodeT * findNearestCommonDominator (NodeT *A, 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)

virtual void print (std::ostream &o, const Module *) const

void print (std::ostream *OS, const Module *M=0) const

virtual void dump ()

template<class FT>

void recalculate (FT &F)

recalculate - compute a dominator tree for the given function

template<>

void addRoot (MachineBasicBlock *MBB)

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)

Protected Attributes

DomTreeNodeMapType DomTreeNodes

DomTreeNodeBase< NodeT > * RootNode

bool DFSInfoValid

unsigned int SlowQueries

DenseMap< NodeT *, NodeT * > IDoms

std::vector< NodeT * > Vertex

DenseMap< NodeT *, InfoRec > Info

Friends

template<class GraphT>

void Compress (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *VIn)

template<class GraphT>

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

template<class GraphT>

void Link (DominatorTreeBase< typename GraphT::NodeType > &DT, unsigned DFSNumV, typename GraphT::NodeType *W, typename DominatorTreeBase< typename GraphT::NodeType >::InfoRec &WInfo)

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)

Classes

struct InfoRec

Detailed Description

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

Definition at line 196 of file Dominators.h.

Member Typedef Documentation

template<class NodeT>

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

Definition at line 198 of file Dominators.h.

Constructor & Destructor Documentation

template<class NodeT>

llvm::DominatorTreeBase< NodeT >::DominatorTreeBase ( bool isPostDom ) [inline, explicit]

Definition at line 325 of file Dominators.h.

template<class NodeT>

virtual llvm::DominatorTreeBase< NodeT >::~DominatorTreeBase ( ) [inline, virtual]

Definition at line 327 of file Dominators.h.

Member Function Documentation

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::reset ( ) [inline, protected]

Definition at line 226 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
	)			`[inline, protected]`

Definition at line 240 of file Dominators.h.

template<class NodeT>

virtual bool llvm::DominatorTreeBase< NodeT >::runOnFunction ( Function & F ) [inline, virtual]

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

template<class NodeT>

virtual void llvm::DominatorTreeBase< NodeT >::releaseMemory ( ) [inline, virtual]

Definition at line 359 of file Dominators.h.

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

Referenced by llvm::LoopInfoBase< llvm::MachineBasicBlock >::Calculate(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::print().

template<class NodeT>

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

Definition at line 377 of file Dominators.h.

template<class NodeT>

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

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

Definition at line 382 of file Dominators.h.

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

template<class NodeT>

bool llvm::DominatorTreeBase< NodeT >::properlyDominates	(	NodeT *	A,
		NodeT *	B
	)			`[inline]`

Definition at line 388 of file Dominators.h.

template<class NodeT>

bool llvm::DominatorTreeBase< NodeT >::dominatedBySlowTreeWalk	(	const DomTreeNodeBase< NodeT > *	A,
		const DomTreeNodeBase< NodeT > *	B
	)			const `[inline]`

Definition at line 392 of file Dominators.h.

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

template<class NodeT>

bool llvm::DominatorTreeBase< NodeT >::isReachableFromEntry ( NodeT * A ) [inline]

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

Definition at line 404 of file Dominators.h.

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

template<class NodeT>

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

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

Definition at line 413 of file Dominators.h.

Referenced by llvm::LoopInfoBase< llvm::MachineBasicBlock >::ConsiderForLoop(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::findNearestCommonDominator(), llvm::DominatorTreeBase< llvm::MachineBasicBlock >::isReachableFromEntry(), and llvm::DominatorTreeBase< llvm::MachineBasicBlock >::Split().

template<class NodeT>

bool llvm::DominatorTreeBase< NodeT >::dominates	(	NodeT *	A,
		NodeT *	B
	)			`[inline]`

Definition at line 435 of file Dominators.h.

template<class NodeT>

NodeT* llvm::DominatorTreeBase< NodeT >::getRoot ( ) const [inline]

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

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

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

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

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 512 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 519 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 domiante any other blocks. Removes node from its immediate dominator's children list. Deletes dominator node associated with basic block BB.

Definition at line 526 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 549 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 556 of file Dominators.h.

template<class NodeT>

virtual void llvm::DominatorTreeBase< NodeT >::print	(	std::ostream &	o,
		const Module *
	)			const `[inline, virtual]`

print - Convert to human readable form

Definition at line 565 of file Dominators.h.

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

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::print	(	std::ostream *	OS,
		const Module *	M = `0`
	)			const `[inline]`

Definition at line 578 of file Dominators.h.

template<class NodeT>

virtual void llvm::DominatorTreeBase< NodeT >::dump ( ) [inline, virtual]

Definition at line 582 of file Dominators.h.

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::updateDFSNumbers ( ) [inline, protected]

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

Definition at line 612 of file Dominators.h.

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

template<class NodeT>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getNodeForBlock ( NodeT * BB ) [inline, protected]

Definition at line 648 of file Dominators.h.

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

template<class NodeT>

NodeT* llvm::DominatorTreeBase< NodeT >::getIDom ( NodeT * BB ) const [inline, protected]

Definition at line 665 of file Dominators.h.

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

template<class NodeT>

void llvm::DominatorTreeBase< NodeT >::addRoot ( NodeT * BB ) [inline, protected]

Definition at line 670 of file Dominators.h.

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

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

template<>

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

Definition at line 27 of file MachineDominators.h.

References llvm::DominatorBase< NodeT >::Roots.

Friends And Related Function Documentation

template<class NodeT>

template<class GraphT>

void Compress	(	DominatorTreeBase< typename GraphT::NodeType > &	DT,
		typename GraphT::NodeType *	VIn
	)			`[friend]`

Definition at line 117 of file DominatorInternals.h.

template<class NodeT>

template<class GraphT>

GraphT::NodeType* Eval	(	DominatorTreeBase< typename GraphT::NodeType > &	DT,
		typename GraphT::NodeType *	V
	)			`[friend]`

Definition at line 155 of file DominatorInternals.h.

template<class NodeT>

template<class GraphT>

void Link	(	DominatorTreeBase< typename GraphT::NodeType > &	DT,
		unsigned	DFSNumV,
		typename GraphT::NodeType *	W,
		typename DominatorTreeBase< typename GraphT::NodeType >::InfoRec &	WInfo
	)			`[friend]`

template<class NodeT>

template<class GraphT>

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

Definition at line 38 of file DominatorInternals.h.

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.

Member Data Documentation

template<class NodeT>

DomTreeNodeMapType llvm::DominatorTreeBase< NodeT >::DomTreeNodes [protected]

Definition at line 199 of file Dominators.h.

template<class NodeT>

DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::RootNode [protected]

Definition at line 200 of file Dominators.h.

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

template<class NodeT>

bool llvm::DominatorTreeBase< NodeT >::DFSInfoValid [protected]

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

unsigned int llvm::DominatorTreeBase< NodeT >::SlowQueries [protected]

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

DenseMap<NodeT*, NodeT*> llvm::DominatorTreeBase< NodeT >::IDoms [protected]

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

std::vector<NodeT*> llvm::DominatorTreeBase< NodeT >::Vertex [protected]

Definition at line 221 of file Dominators.h.

Referenced by llvm::Compress(), llvm::DFSPass(), 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 224 of file Dominators.h.

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

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

Dominators.h


Public Member Functions
	DominatorTreeBase (bool isPostDom)
virtual	~DominatorTreeBase ()
virtual bool	runOnFunction (Function &F)
bool	compare (DominatorTreeBase &Other) const
virtual void	releaseMemory ()
DomTreeNodeBase< NodeT > *	getNode (NodeT *BB) const
DomTreeNodeBase< NodeT > *	getRootNode ()
const DomTreeNodeBase< NodeT > *	getRootNode () const
bool	properlyDominates (const DomTreeNodeBase< NodeT > A, DomTreeNodeBase< NodeT > B) const
bool	properlyDominates (NodeT A, NodeT B)
bool	dominatedBySlowTreeWalk (const DomTreeNodeBase< NodeT > A, const DomTreeNodeBase< NodeT > B) const
bool	isReachableFromEntry (NodeT *A)
bool	dominates (const DomTreeNodeBase< NodeT > A, DomTreeNodeBase< NodeT > B)
bool	dominates (NodeT A, NodeT B)
NodeT *	getRoot () const
NodeT *	findNearestCommonDominator (NodeT A, 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)
virtual void	print (std::ostream &o, const Module *) const
void	print (std::ostream OS, const Module M=0) const
virtual void	dump ()
template<class FT>
void	recalculate (FT &F)
	recalculate - compute a dominator tree for the given function
template<>
void	addRoot (MachineBasicBlock *MBB)
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)
Protected Attributes
DomTreeNodeMapType	DomTreeNodes
DomTreeNodeBase< NodeT > *	RootNode
bool	DFSInfoValid
unsigned int	SlowQueries
DenseMap< NodeT , NodeT >	IDoms
std::vector< NodeT * >	Vertex
DenseMap< NodeT *, InfoRec >	Info
Friends
template<class GraphT>
void	Compress (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *VIn)
template<class GraphT>
GraphT::NodeType *	Eval (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *V)
template<class GraphT>
void	Link (DominatorTreeBase< typename GraphT::NodeType > &DT, unsigned DFSNumV, typename GraphT::NodeType *W, typename DominatorTreeBase< typename GraphT::NodeType >::InfoRec &WInfo)
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)
Classes
struct	InfoRec

llvm::DominatorTreeBase< NodeT > Class Template Reference

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Friends

Classes

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

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