LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

llvm::DominatorTreeBase< NodeT > Class Template Reference

#include <Dominators.h>

Inheritance diagram for llvm::DominatorTreeBase< NodeT >:

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

Collaboration graph
[legend]
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

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)

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

Member Typedef Documentation

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

Definition at line 199 of file Dominators.h.

Constructor & Destructor Documentation

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

Definition at line 326 of file Dominators.h.

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

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

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

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

Definition at line 671 of file Dominators.h.

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

Definition at line 520 of file Dominators.h.

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

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

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

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

Definition at line 436 of file Dominators.h.

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

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

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

Definition at line 583 of file Dominators.h.

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

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

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

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

Definition at line 666 of file Dominators.h.

Referenced by llvm::Calculate().

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

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

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

Definition at line 649 of file Dominators.h.

Referenced by llvm::Calculate().

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

Definition at line 443 of file Dominators.h.

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

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

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

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

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

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

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

Definition at line 389 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 383 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 678 of file Dominators.h.

Referenced by llvm::PostDominatorTree::runOnFunction(), llvm::DominatorTree::runOnFunction(), and llvm::PMDataManager::verifyDomInfo().

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

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

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

Definition at line 227 of file Dominators.h.

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

Definition at line 331 of file Dominators.h.

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 241 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 557 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 613 of file Dominators.h.

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>
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>
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 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]
 

Definition at line 181 of file DominatorInternals.h.

Member Data Documentation

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

Definition at line 203 of file Dominators.h.

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

Definition at line 200 of file Dominators.h.

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

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

Definition at line 219 of file Dominators.h.

Referenced by llvm::Calculate().

template<class NodeT>
DenseMap<NodeT*, InfoRec> llvm::DominatorTreeBase< NodeT >::Info [protected]
 

Definition at line 225 of file Dominators.h.

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

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

Definition at line 201 of file Dominators.h.

Referenced by llvm::Calculate().

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

Definition at line 204 of file Dominators.h.

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

Definition at line 222 of file Dominators.h.

Referenced by llvm::Calculate(), llvm::Compress(), and llvm::DFSPass().

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

Generated on Fri Aug 29 02:50:34 2008 for LLVM by Doxygen1.3.9.1
Copyright © 2003-2007 University of Illinois at Urbana-Champaign. All Rights Reserved.

This web site is hosted by the Computer Science Department at the University of Illinois at Urbana-Champaign.