PostDominators.h revision 081c34b725980f995be9080eaec24cd3dfaaf065
1//=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file exposes interfaces to post dominance information. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_ANALYSIS_POST_DOMINATORS_H 15#define LLVM_ANALYSIS_POST_DOMINATORS_H 16 17#include "llvm/Analysis/Dominators.h" 18 19namespace llvm { 20 21/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 22/// compute the a post-dominator tree. 23/// 24struct PostDominatorTree : public FunctionPass { 25 static char ID; // Pass identification, replacement for typeid 26 DominatorTreeBase<BasicBlock>* DT; 27 28 PostDominatorTree() : FunctionPass(ID) { 29 initializePostDominatorTreePass(*PassRegistry::getPassRegistry()); 30 DT = new DominatorTreeBase<BasicBlock>(true); 31 } 32 33 ~PostDominatorTree(); 34 35 virtual bool runOnFunction(Function &F); 36 37 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 38 AU.setPreservesAll(); 39 } 40 41 inline const std::vector<BasicBlock*> &getRoots() const { 42 return DT->getRoots(); 43 } 44 45 inline DomTreeNode *getRootNode() const { 46 return DT->getRootNode(); 47 } 48 49 inline DomTreeNode *operator[](BasicBlock *BB) const { 50 return DT->getNode(BB); 51 } 52 53 inline DomTreeNode *getNode(BasicBlock *BB) const { 54 return DT->getNode(BB); 55 } 56 57 inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { 58 return DT->dominates(A, B); 59 } 60 61 inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { 62 return DT->dominates(A, B); 63 } 64 65 inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { 66 return DT->properlyDominates(A, B); 67 } 68 69 inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { 70 return DT->properlyDominates(A, B); 71 } 72 73 inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { 74 return DT->findNearestCommonDominator(A, B); 75 } 76 77 virtual void releaseMemory() { 78 DT->releaseMemory(); 79 } 80 81 virtual void print(raw_ostream &OS, const Module*) const; 82}; 83 84FunctionPass* createPostDomTree(); 85 86template <> struct GraphTraits<PostDominatorTree*> 87 : public GraphTraits<DomTreeNode*> { 88 static NodeType *getEntryNode(PostDominatorTree *DT) { 89 return DT->getRootNode(); 90 } 91 92 static nodes_iterator nodes_begin(PostDominatorTree *N) { 93 if (getEntryNode(N)) 94 return df_begin(getEntryNode(N)); 95 else 96 return df_end(getEntryNode(N)); 97 } 98 99 static nodes_iterator nodes_end(PostDominatorTree *N) { 100 return df_end(getEntryNode(N)); 101 } 102}; 103 104/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 105/// used to compute the a post-dominance frontier. 106/// 107struct PostDominanceFrontier : public DominanceFrontierBase { 108 static char ID; 109 PostDominanceFrontier() 110 : DominanceFrontierBase(ID, true) { 111 initializePostDominanceFrontierPass(*PassRegistry::getPassRegistry()); 112 } 113 114 virtual bool runOnFunction(Function &) { 115 Frontiers.clear(); 116 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 117 Roots = DT.getRoots(); 118 if (const DomTreeNode *Root = DT.getRootNode()) 119 calculate(DT, Root); 120 return false; 121 } 122 123 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 124 AU.setPreservesAll(); 125 AU.addRequired<PostDominatorTree>(); 126 } 127 128private: 129 const DomSetType &calculate(const PostDominatorTree &DT, 130 const DomTreeNode *Node); 131}; 132 133FunctionPass* createPostDomFrontier(); 134 135} // End llvm namespace 136 137#endif 138