LLVM API Documentation

Classes | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | Friends
llvm::DominatorTreeBase< NodeT > Class Template Reference

#include <GenericDomTree.h>

Inheritance diagram for llvm::DominatorTreeBase< NodeT >:
Inheritance graph
[legend]
Collaboration diagram for llvm::DominatorTreeBase< NodeT >:
Collaboration graph
[legend]

List of all members.

Classes

struct  InfoRec

Public Member Functions

 DominatorTreeBase (bool isPostDom)
virtual ~DominatorTreeBase ()
bool compare (const DominatorTreeBase &Other) const
virtual void releaseMemory ()
DomTreeNodeBase< NodeT > * getNode (NodeT *BB) const
DomTreeNodeBase< NodeT > * operator[] (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.
bool properlyDominates (const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
bool properlyDominates (const NodeT *A, const NodeT *B) const
bool isReachableFromEntry (const NodeT *A) const
bool isReachableFromEntry (const DomTreeNodeBase< NodeT > *A) const
bool dominates (const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
bool dominates (const NodeT *A, const NodeT *B) const
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

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 () const
DomTreeNodeBase< NodeT > * getNodeForBlock (NodeT *BB)
NodeT * getIDom (NodeT *BB) const
void addRoot (NodeT *BB)
template<>
void addRoot (MachineBasicBlock *MBB)

Protected Attributes

DomTreeNodeMapType DomTreeNodes
DomTreeNodeBase< NodeT > * RootNode
bool DFSInfoValid
unsigned int SlowQueries
DenseMap< NodeT *, NodeT * > IDoms
std::vector< NodeT * > Vertex
DenseMap< NodeT *, InfoRecInfo

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 181 of file GenericDomTree.h.


Member Typedef Documentation

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

Definition at line 195 of file GenericDomTree.h.


Constructor & Destructor Documentation

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

Definition at line 294 of file GenericDomTree.h.

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

Definition at line 296 of file GenericDomTree.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 510 of file GenericDomTree.h.

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

template<>
void llvm::DominatorTreeBase< MachineBasicBlock >::addRoot ( MachineBasicBlock MBB) [inline, protected]

Definition at line 28 of file MachineDominators.h.

template<class NodeT>
void llvm::DominatorTreeBase< NodeT >::addRoot ( NodeT *  BB) [inline, protected]
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 522 of file GenericDomTree.h.

Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::changeImmediateDominator(), llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), simplifyOneLoop(), llvm::DominatorTreeBase< MachineBasicBlock >::Split(), llvm::SplitBlock(), and llvm::SplitBlockAndInsertIfThen().

template<class NodeT>
void llvm::DominatorTreeBase< NodeT >::changeImmediateDominator ( NodeT *  BB,
NodeT *  NewBB 
) [inline]

Definition at line 529 of file GenericDomTree.h.

template<class NodeT>
bool llvm::DominatorTreeBase< NodeT >::compare ( const 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 300 of file GenericDomTree.h.

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

Definition at line 711 of file GenericDomTree.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 536 of file GenericDomTree.h.

Referenced by llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), and simplifyOneLoop().

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 GenericDomTree.h.

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

template<class NodeT>
const NodeT* llvm::DominatorTreeBase< NodeT >::findNearestCommonDominator ( const NodeT *  A,
const NodeT *  B 
) [inline]

Definition at line 496 of file GenericDomTree.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.

Definition at line 348 of file GenericDomTree.h.

Referenced by llvm::PostDominatorTree::getDescendants().

template<class NodeT>
NodeT* llvm::DominatorTreeBase< NodeT >::getIDom ( NodeT *  BB) const [inline, protected]
template<class NodeT>
DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getNode ( NodeT *  BB) const [inline]
template<class NodeT>
DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getNodeForBlock ( NodeT *  BB) [inline, protected]
template<class NodeT>
NodeT* llvm::DominatorTreeBase< NodeT >::getRoot ( ) const [inline]

Definition at line 430 of file GenericDomTree.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 344 of file GenericDomTree.h.

Referenced by llvm::LoopInfoBase< BlockT, LoopT >::Analyze(), llvm::DominatorTree::compare(), llvm::GraphTraits< DominatorTree * >::getEntryNode(), llvm::DOTGraphTraits< DominatorTree * >::getNodeLabel(), llvm::MachinePostDominatorTree::getRootNode(), llvm::PostDominatorTree::getRootNode(), llvm::DominatorTreeBase< MachineBasicBlock >::print(), and llvm::DominatorTreeBase< MachineBasicBlock >::updateDFSNumbers().

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

Definition at line 345 of file GenericDomTree.h.

template<class NodeT>
bool llvm::DominatorTreeBase< NodeT >::isReachableFromEntry ( const NodeT *  A) const [inline]
template<class NodeT>
bool llvm::DominatorTreeBase< NodeT >::isReachableFromEntry ( const DomTreeNodeBase< NodeT > *  A) const [inline]

Definition at line 385 of file GenericDomTree.h.

template<class NodeT>
DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::operator[] ( NodeT *  BB) const [inline]

Definition at line 333 of file GenericDomTree.h.

template<class NodeT>
void llvm::DominatorTreeBase< NodeT >::print ( raw_ostream o) const [inline]
template<class NodeT>
bool llvm::DominatorTreeBase< NodeT >::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 366 of file GenericDomTree.h.

Referenced by llvm::ForwardDominanceFrontierBase< BlockT >::calculate(), isLoopInvariant(), llvm::PostDominatorTree::properlyDominates(), and llvm::MachinePostDominatorTree::properlyDominates().

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

Definition at line 723 of file GenericDomTree.h.

template<class NodeT>
template<class FT >
void llvm::DominatorTreeBase< NodeT >::recalculate ( FT &  F) [inline]
template<class NodeT>
virtual void llvm::DominatorTreeBase< NodeT >::releaseMemory ( ) [inline, virtual]
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 559 of file GenericDomTree.h.

template<class NodeT>
void llvm::DominatorTreeBase< NodeT >::reset ( ) [inline, protected]
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 233 of file GenericDomTree.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 566 of file GenericDomTree.h.

Referenced by insertUniqueBackedgeBlock().

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

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

Definition at line 608 of file GenericDomTree.h.

Referenced by llvm::DominatorTreeBase< 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 GenericDomTreeConstruction.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 GenericDomTreeConstruction.h.


Member Data Documentation

template<class NodeT>
bool llvm::DominatorTreeBase< NodeT >::DFSInfoValid [mutable, protected]
template<class NodeT>
DomTreeNodeMapType llvm::DominatorTreeBase< NodeT >::DomTreeNodes [protected]
template<class NodeT>
DenseMap<NodeT*, NodeT*> llvm::DominatorTreeBase< NodeT >::IDoms [protected]
template<class NodeT>
DenseMap<NodeT*, InfoRec> llvm::DominatorTreeBase< NodeT >::Info [protected]

Definition at line 217 of file GenericDomTree.h.

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

template<class NodeT>
DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::RootNode [protected]
template<class NodeT>
unsigned int llvm::DominatorTreeBase< NodeT >::SlowQueries [mutable, protected]
template<class NodeT>
std::vector<NodeT*> llvm::DominatorTreeBase< NodeT >::Vertex [protected]

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