PostDominators.h revision 90c579de5a383cee278acc3f7e7b9d0a656e6a35
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 DT = new DominatorTreeBase<BasicBlock>(true); 30 } 31 32 ~PostDominatorTree(); 33 34 virtual bool runOnFunction(Function &F); 35 36 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 37 AU.setPreservesAll(); 38 } 39 40 inline const std::vector<BasicBlock*> &getRoots() const { 41 return DT->getRoots(); 42 } 43 44 inline DomTreeNode *getRootNode() const { 45 return DT->getRootNode(); 46 } 47 48 inline DomTreeNode *operator[](BasicBlock *BB) const { 49 return DT->getNode(BB); 50 } 51 52 inline DomTreeNode *getNode(BasicBlock *BB) const { 53 return DT->getNode(BB); 54 } 55 56 inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { 57 return DT->dominates(A, B); 58 } 59 60 inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { 61 return DT->dominates(A, B); 62 } 63 64 inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { 65 return DT->properlyDominates(A, B); 66 } 67 68 inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { 69 return DT->properlyDominates(A, B); 70 } 71 72 inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { 73 return DT->findNearestCommonDominator(A, B); 74 } 75 76 virtual void releaseMemory() { 77 DT->releaseMemory(); 78 } 79 80 virtual void print(raw_ostream &OS, const Module*) const; 81}; 82 83FunctionPass* createPostDomTree(); 84 85template <> struct GraphTraits<PostDominatorTree*> 86 : public GraphTraits<DomTreeNode*> { 87 static NodeType *getEntryNode(PostDominatorTree *DT) { 88 return DT->getRootNode(); 89 } 90 91 static nodes_iterator nodes_begin(PostDominatorTree *N) { 92 if (getEntryNode(N)) 93 return df_begin(getEntryNode(N)); 94 else 95 return df_end(getEntryNode(N)); 96 } 97 98 static nodes_iterator nodes_end(PostDominatorTree *N) { 99 return df_end(getEntryNode(N)); 100 } 101}; 102 103/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 104/// used to compute the a post-dominance frontier. 105/// 106struct PostDominanceFrontier : public DominanceFrontierBase { 107 static char ID; 108 PostDominanceFrontier() 109 : DominanceFrontierBase(ID, true) {} 110 111 virtual bool runOnFunction(Function &) { 112 Frontiers.clear(); 113 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 114 Roots = DT.getRoots(); 115 if (const DomTreeNode *Root = DT.getRootNode()) 116 calculate(DT, Root); 117 return false; 118 } 119 120 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 121 AU.setPreservesAll(); 122 AU.addRequired<PostDominatorTree>(); 123 } 124 125private: 126 const DomSetType &calculate(const PostDominatorTree &DT, 127 const DomTreeNode *Node); 128}; 129 130FunctionPass* createPostDomFrontier(); 131 132} // End llvm namespace 133 134#endif 135