PostDominators.h revision f0d24f1f597a84b1a164019ab81831ccd7aea47f
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 bool dominates(DomTreeNode* A, DomTreeNode* B) const { 53 return DT->dominates(A, B); 54 } 55 56 inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { 57 return DT->dominates(A, B); 58 } 59 60 inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { 61 return DT->properlyDominates(A, B); 62 } 63 64 inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { 65 return DT->properlyDominates(A, B); 66 } 67 68 virtual void releaseMemory() { 69 DT->releaseMemory(); 70 } 71 72 virtual void print(raw_ostream &OS, const Module*) const; 73}; 74 75FunctionPass* createPostDomTree(); 76 77template <> struct GraphTraits<PostDominatorTree*> 78 : public GraphTraits<DomTreeNode*> { 79 static NodeType *getEntryNode(PostDominatorTree *DT) { 80 return DT->getRootNode(); 81 } 82 83 static nodes_iterator nodes_begin(PostDominatorTree *N) { 84 return df_begin(getEntryNode(N)); 85 } 86 87 static nodes_iterator nodes_end(PostDominatorTree *N) { 88 return df_end(getEntryNode(N)); 89 } 90}; 91 92/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 93/// used to compute the a post-dominance frontier. 94/// 95struct PostDominanceFrontier : public DominanceFrontierBase { 96 static char ID; 97 PostDominanceFrontier() 98 : DominanceFrontierBase(&ID, true) {} 99 100 virtual bool runOnFunction(Function &) { 101 Frontiers.clear(); 102 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 103 Roots = DT.getRoots(); 104 if (const DomTreeNode *Root = DT.getRootNode()) 105 calculate(DT, Root); 106 return false; 107 } 108 109 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 110 AU.setPreservesAll(); 111 AU.addRequired<PostDominatorTree>(); 112 } 113 114private: 115 const DomSetType &calculate(const PostDominatorTree &DT, 116 const DomTreeNode *Node); 117}; 118 119FunctionPass* createPostDomFrontier(); 120 121} // End llvm namespace 122 123#endif 124