#include <Dominators.h>
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 |
| 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 | |
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 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 > | |
| 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 187 of file Dominators.h.
Member Typedef Documentation
typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> llvm::DominatorTreeBase< NodeT >::DomTreeNodeMapType [protected] |
Definition at line 201 of file Dominators.h.
Constructor & Destructor Documentation
| llvm::DominatorTreeBase< NodeT >::DominatorTreeBase | ( | bool | isPostDom | ) | [inline, explicit] |
Definition at line 300 of file Dominators.h.
| virtual llvm::DominatorTreeBase< NodeT >::~DominatorTreeBase | ( | ) | [inline, virtual] |
Definition at line 302 of file Dominators.h.
Member Function Documentation
| 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 481 of file Dominators.h.
Referenced by llvm::DominatorTree::addNewBlock(), and llvm::DominatorTreeBase< MachineBasicBlock >::Split().
| void llvm::DominatorTreeBase< MachineBasicBlock >::addRoot | ( | MachineBasicBlock * | MBB | ) | [inline, protected] |
Definition at line 27 of file MachineDominators.h.
| void llvm::DominatorTreeBase< NodeT >::addRoot | ( | NodeT * | BB | ) | [inline, protected] |
Definition at line 642 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::recalculate().
| 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 493 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::changeImmediateDominator(), llvm::DominatorTree::changeImmediateDominator(), and llvm::DominatorTreeBase< MachineBasicBlock >::Split().
| void llvm::DominatorTreeBase< NodeT >::changeImmediateDominator | ( | NodeT * | BB, |
| NodeT * | NewBB | ||
| ) | [inline] |
Definition at line 500 of file Dominators.h.
| 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.
Referenced by llvm::DominatorTree::compare().
| 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 378 of file Dominators.h.
Referenced by llvm::LoopInfoBase< BlockT, LoopT >::Analyze(), llvm::PostDominatorTree::dominates(), llvm::MachinePostDominatorTree::dominates(), llvm::DominatorTree::dominates(), llvm::DominatorTreeBase< MachineBasicBlock >::findNearestCommonDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::properlyDominates(), and llvm::DominatorTreeBase< MachineBasicBlock >::Split().
| bool llvm::DominatorTreeBase< NodeT >::dominates | ( | const NodeT * | A, |
| const NodeT * | B | ||
| ) |
Definition at line 682 of file Dominators.h.
| 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 507 of file Dominators.h.
Referenced by llvm::DominatorTree::eraseNode().
| 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 423 of file Dominators.h.
Referenced by llvm::PostDominatorTree::findNearestCommonDominator(), llvm::MachinePostDominatorTree::findNearestCommonDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::findNearestCommonDominator(), llvm::DominatorTree::findNearestCommonDominator(), and llvm::DominatorTreeBase< MachineBasicBlock >::Split().
| const NodeT* llvm::DominatorTreeBase< NodeT >::findNearestCommonDominator | ( | const NodeT * | A, |
| const NodeT * | B | ||
| ) | [inline] |
Definition at line 467 of file Dominators.h.
| NodeT* llvm::DominatorTreeBase< NodeT >::getIDom | ( | NodeT * | BB | ) | const [inline, protected] |
Definition at line 638 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::getNodeForBlock().
| 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< MachineBasicBlock >::addNewBlock(), llvm::DominatorTreeBase< MachineBasicBlock >::changeImmediateDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::eraseNode(), llvm::DominatorTreeBase< MachineBasicBlock >::findNearestCommonDominator(), llvm::MachinePostDominatorTree::getNode(), llvm::PostDominatorTree::getNode(), llvm::DominatorTree::getNode(), llvm::DominatorTreeBase< MachineBasicBlock >::getNodeForBlock(), llvm::DominatorTreeBase< MachineBasicBlock >::isReachableFromEntry(), llvm::PostDominatorTree::operator[](), llvm::MachinePostDominatorTree::operator[](), llvm::DominatorTree::operator[](), llvm::DominatorTreeBase< MachineBasicBlock >::removeNode(), and llvm::DominatorTreeBase< MachineBasicBlock >::Split().
| DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getNodeForBlock | ( | NodeT * | BB | ) | [inline, protected] |
Definition at line 621 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::getNodeForBlock().
| NodeT* llvm::DominatorTreeBase< NodeT >::getRoot | ( | ) | const [inline] |
Definition at line 416 of file Dominators.h.
Referenced by llvm::DominatorTree::getRoot().
| 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< BlockT, LoopT >::Analyze(), llvm::PostDominatorTree::getRootNode(), llvm::MachinePostDominatorTree::getRootNode(), llvm::DominatorTree::getRootNode(), llvm::DominatorTreeBase< MachineBasicBlock >::print(), and llvm::DominatorTreeBase< MachineBasicBlock >::updateDFSNumbers().
| const DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getRootNode | ( | ) | const [inline] |
Definition at line 347 of file Dominators.h.
| 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 365 of file Dominators.h.
Referenced by llvm::LoopInfoBase< BlockT, LoopT >::Analyze(), llvm::discoverAndMapSubloop(), llvm::DominatorTreeBase< MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< MachineBasicBlock >::isReachableFromEntry(), llvm::DominatorTree::isReachableFromEntry(), and llvm::DominatorTreeBase< MachineBasicBlock >::Split().
| bool llvm::DominatorTreeBase< NodeT >::isReachableFromEntry | ( | const DomTreeNodeBase< NodeT > * | A | ) | const [inline] |
Definition at line 371 of file Dominators.h.
| void llvm::DominatorTreeBase< NodeT >::print | ( | raw_ostream & | o | ) | const [inline] |
print - Convert to human readable form
Definition at line 546 of file Dominators.h.
Referenced by llvm::PostDominatorTree::print(), llvm::MachinePostDominatorTree::print(), llvm::MachineDominatorTree::print(), and llvm::DominatorTree::print().
| 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 352 of file Dominators.h.
Referenced by llvm::PostDominatorTree::properlyDominates(), llvm::MachinePostDominatorTree::properlyDominates(), and llvm::DominatorTree::properlyDominates().
| bool llvm::DominatorTreeBase< NodeT >::properlyDominates | ( | const NodeT * | A, |
| const NodeT * | B | ||
| ) |
Definition at line 694 of file Dominators.h.
| void llvm::DominatorTreeBase< NodeT >::recalculate | ( | FT & | F | ) | [inline] |
recalculate - compute a dominator tree for the given function
Definition at line 649 of file Dominators.h.
Referenced by llvm::MachineDominatorTree::runOnMachineFunction(), llvm::MachinePostDominatorTree::runOnMachineFunction(), and llvm::DominatorTree::verifyAnalysis().
| virtual void llvm::DominatorTreeBase< NodeT >::releaseMemory | ( | ) | [inline, virtual] |
Definition at line 330 of file Dominators.h.
Referenced by llvm::PostDominatorTree::releaseMemory(), llvm::MachineDominatorTree::releaseMemory(), and llvm::DominatorTree::releaseMemory().
| 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 530 of file Dominators.h.
| void llvm::DominatorTreeBase< NodeT >::reset | ( | ) | [inline, protected] |
Definition at line 225 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::recalculate(), llvm::DominatorTreeBase< MachineBasicBlock >::releaseMemory(), and llvm::DominatorTreeBase< MachineBasicBlock >::~DominatorTreeBase().
| void llvm::DominatorTreeBase< NodeT >::Split | ( | DominatorTreeBase< typename GraphT::NodeType > & | DT, |
| typename GraphT::NodeType * | NewBB | ||
| ) | [inline, protected] |
Definition at line 239 of file Dominators.h.
| 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 537 of file Dominators.h.
Referenced by llvm::DominatorTree::splitBlock().
| 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 579 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::dominates().
Friends And Related Function Documentation
| void Calculate | ( | DominatorTreeBase< typename GraphTraits< N >::NodeType > & | DT, |
| FuncT & | F | ||
| ) | [friend] |
DominatorTree - Calculate the immediate dominator tree for a function.
| unsigned DFSPass | ( | DominatorTreeBase< typename GraphT::NodeType > & | DT, |
| typename GraphT::NodeType * | V, | ||
| unsigned | N | ||
| ) | [friend] |
Definition at line 34 of file DominatorInternals.h.
| 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
bool llvm::DominatorTreeBase< NodeT >::DFSInfoValid [protected] |
Definition at line 205 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::addNewBlock(), llvm::DominatorTreeBase< MachineBasicBlock >::changeImmediateDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< MachineBasicBlock >::print(), and llvm::DominatorTreeBase< MachineBasicBlock >::updateDFSNumbers().
DomTreeNodeMapType llvm::DominatorTreeBase< NodeT >::DomTreeNodes [protected] |
Definition at line 202 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::addNewBlock(), llvm::DominatorTreeBase< MachineBasicBlock >::compare(), llvm::DominatorTreeBase< MachineBasicBlock >::eraseNode(), llvm::DominatorTreeBase< MachineBasicBlock >::getNode(), llvm::DominatorTreeBase< MachineBasicBlock >::getNodeForBlock(), llvm::DominatorTreeBase< MachineBasicBlock >::recalculate(), llvm::DominatorTreeBase< MachineBasicBlock >::removeNode(), and llvm::DominatorTreeBase< MachineBasicBlock >::reset().
DenseMap<NodeT*, NodeT*> llvm::DominatorTreeBase< NodeT >::IDoms [protected] |
Definition at line 217 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::getIDom(), llvm::DominatorTreeBase< MachineBasicBlock >::recalculate(), and llvm::DominatorTreeBase< MachineBasicBlock >::reset().
DenseMap<NodeT*, InfoRec> llvm::DominatorTreeBase< NodeT >::Info [protected] |
Definition at line 223 of file Dominators.h.
Referenced by llvm::DFSPass(), and llvm::Eval().
DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::RootNode [protected] |
Definition at line 203 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::getRootNode(), and llvm::DominatorTreeBase< MachineBasicBlock >::reset().
unsigned int llvm::DominatorTreeBase< NodeT >::SlowQueries [protected] |
Definition at line 206 of file Dominators.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< MachineBasicBlock >::print(), and llvm::DominatorTreeBase< MachineBasicBlock >::updateDFSNumbers().
std::vector<NodeT*> llvm::DominatorTreeBase< NodeT >::Vertex [protected] |
Definition at line 220 of file Dominators.h.
Referenced by llvm::DFSPass(), llvm::Eval(), llvm::DominatorTreeBase< MachineBasicBlock >::recalculate(), and llvm::DominatorTreeBase< MachineBasicBlock >::reset().
The documentation for this class was generated from the following file:
1.7.5.1