#include <GenericDomTree.h>
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 *, 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 181 of file GenericDomTree.h.
Member Typedef Documentation
typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> llvm::DominatorTreeBase< NodeT >::DomTreeNodeMapType [protected] |
Definition at line 195 of file GenericDomTree.h.
Constructor & Destructor Documentation
| llvm::DominatorTreeBase< NodeT >::DominatorTreeBase | ( | bool | isPostDom | ) | [inline, explicit] |
Definition at line 294 of file GenericDomTree.h.
| virtual llvm::DominatorTreeBase< NodeT >::~DominatorTreeBase | ( | ) | [inline, virtual] |
Definition at line 296 of file GenericDomTree.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 510 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::Split(), llvm::SplitBlock(), and llvm::SplitBlockAndInsertIfThen().
| void llvm::DominatorTreeBase< MachineBasicBlock >::addRoot | ( | MachineBasicBlock * | MBB | ) | [inline, protected] |
Definition at line 28 of file MachineDominators.h.
| void llvm::DominatorTreeBase< NodeT >::addRoot | ( | NodeT * | BB | ) | [inline, protected] |
Definition at line 671 of file GenericDomTree.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 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().
| void llvm::DominatorTreeBase< NodeT >::changeImmediateDominator | ( | NodeT * | BB, |
| NodeT * | NewBB | ||
| ) | [inline] |
Definition at line 529 of file GenericDomTree.h.
| 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.
| bool llvm::DominatorTreeBase< NodeT >::dominates | ( | const DomTreeNodeBase< NodeT > * | A, |
| const DomTreeNodeBase< NodeT > * | B | ||
| ) | const [inline] |
dominates - Returns true iff A dominates B. Note that this is not a constant time operation!
Definition at line 392 of file GenericDomTree.h.
Referenced by llvm::LoopInfoBase< BlockT, LoopT >::Analyze(), llvm::MachinePostDominatorTree::dominates(), llvm::PostDominatorTree::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 | ||
| ) | const |
Definition at line 711 of file GenericDomTree.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 536 of file GenericDomTree.h.
Referenced by llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), and simplifyOneLoop().
| 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().
| const NodeT* llvm::DominatorTreeBase< NodeT >::findNearestCommonDominator | ( | const NodeT * | A, |
| const NodeT * | B | ||
| ) | [inline] |
Definition at line 496 of file GenericDomTree.h.
| 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().
| NodeT* llvm::DominatorTreeBase< NodeT >::getIDom | ( | NodeT * | BB | ) | const [inline, protected] |
Definition at line 667 of file GenericDomTree.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 329 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::addNewBlock(), blockDominatesAnExit(), llvm::DominatorTreeBase< MachineBasicBlock >::changeImmediateDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::eraseNode(), llvm::DominatorTreeBase< MachineBasicBlock >::findNearestCommonDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::getDescendants(), llvm::MachinePostDominatorTree::getNode(), llvm::PostDominatorTree::getNode(), llvm::DominatorTreeBase< MachineBasicBlock >::getNodeForBlock(), llvm::DominatorTreeBase< MachineBasicBlock >::isReachableFromEntry(), isSimplifiedLoopNest(), llvm::MergeBasicBlockIntoOnlyPred(), llvm::MergeBlockIntoPredecessor(), llvm::MachinePostDominatorTree::operator[](), llvm::PostDominatorTree::operator[](), llvm::DominatorTreeBase< MachineBasicBlock >::operator[](), processInstruction(), llvm::DominatorTreeBase< MachineBasicBlock >::removeNode(), simplifyOneLoop(), llvm::DominatorTreeBase< MachineBasicBlock >::Split(), llvm::SplitBlock(), and llvm::SplitBlockAndInsertIfThen().
| DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getNodeForBlock | ( | NodeT * | BB | ) | [inline, protected] |
Definition at line 650 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::getNodeForBlock().
| NodeT* llvm::DominatorTreeBase< NodeT >::getRoot | ( | ) | const [inline] |
Definition at line 430 of file GenericDomTree.h.
| 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().
| const DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::getRootNode | ( | ) | const [inline] |
Definition at line 345 of file GenericDomTree.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 379 of file GenericDomTree.h.
Referenced by llvm::LoopInfoBase< BlockT, LoopT >::Analyze(), llvm::discoverAndMapSubloop(), llvm::DominatorTreeBase< MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< MachineBasicBlock >::isReachableFromEntry(), and llvm::DominatorTreeBase< MachineBasicBlock >::Split().
| bool llvm::DominatorTreeBase< NodeT >::isReachableFromEntry | ( | const DomTreeNodeBase< NodeT > * | A | ) | const [inline] |
Definition at line 385 of file GenericDomTree.h.
| DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::operator[] | ( | NodeT * | BB | ) | const [inline] |
Definition at line 333 of file GenericDomTree.h.
| void llvm::DominatorTreeBase< NodeT >::print | ( | raw_ostream & | o | ) | const [inline] |
print - Convert to human readable form
Definition at line 575 of file GenericDomTree.h.
Referenced by llvm::MachinePostDominatorTree::print(), llvm::PostDominatorTree::print(), llvm::DominatorTreeWrapperPass::print(), llvm::MachineDominatorTree::print(), and llvm::DominatorTree::verifyDomTree().
| 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().
| bool llvm::DominatorTreeBase< NodeT >::properlyDominates | ( | const NodeT * | A, |
| const NodeT * | B | ||
| ) | const |
Definition at line 723 of file GenericDomTree.h.
| void llvm::DominatorTreeBase< NodeT >::recalculate | ( | FT & | F | ) | [inline] |
recalculate - compute a dominator tree for the given function
Definition at line 678 of file GenericDomTree.h.
Referenced by AddAliasScopeMetadata(), llvm::MachinePostDominatorTree::runOnMachineFunction(), llvm::MachineDominatorTree::runOnMachineFunction(), llvm::UnrollLoop(), and llvm::DominatorTree::verifyDomTree().
| virtual void llvm::DominatorTreeBase< NodeT >::releaseMemory | ( | ) | [inline, virtual] |
Definition at line 324 of file GenericDomTree.h.
Referenced by llvm::PostDominatorTree::releaseMemory(), llvm::DominatorTreeWrapperPass::releaseMemory(), and llvm::MachineDominatorTree::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 559 of file GenericDomTree.h.
| void llvm::DominatorTreeBase< NodeT >::reset | ( | ) | [inline, protected] |
Definition at line 219 of file GenericDomTree.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 233 of file GenericDomTree.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 566 of file GenericDomTree.h.
Referenced by insertUniqueBackedgeBlock().
| 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
| 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 GenericDomTreeConstruction.h.
| 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
bool llvm::DominatorTreeBase< NodeT >::DFSInfoValid [mutable, protected] |
Definition at line 199 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::addNewBlock(), llvm::DominatorTreeBase< MachineBasicBlock >::changeImmediateDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::dominates(), llvm::DominatorTreeBase< MachineBasicBlock >::findNearestCommonDominator(), llvm::DominatorTreeBase< MachineBasicBlock >::print(), and llvm::DominatorTreeBase< MachineBasicBlock >::updateDFSNumbers().
DomTreeNodeMapType llvm::DominatorTreeBase< NodeT >::DomTreeNodes [protected] |
Definition at line 196 of file GenericDomTree.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 211 of file GenericDomTree.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 217 of file GenericDomTree.h.
Referenced by llvm::DFSPass(), and llvm::Eval().
DomTreeNodeBase<NodeT>* llvm::DominatorTreeBase< NodeT >::RootNode [protected] |
Definition at line 197 of file GenericDomTree.h.
Referenced by llvm::DominatorTreeBase< MachineBasicBlock >::getRootNode(), and llvm::DominatorTreeBase< MachineBasicBlock >::reset().
unsigned int llvm::DominatorTreeBase< NodeT >::SlowQueries [mutable, protected] |
Definition at line 200 of file GenericDomTree.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 214 of file GenericDomTree.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.6.1