PostDominators.h revision 2833fac27324b956cfb31be987652d2304d10761
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 if (getEntryNode(N)) 85 return df_begin(getEntryNode(N)); 86 else 87 return df_end(getEntryNode(N)); 88 } 89 90 static nodes_iterator nodes_end(PostDominatorTree *N) { 91 return df_end(getEntryNode(N)); 92 } 93}; 94 95/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 96/// used to compute the a post-dominance frontier. 97/// 98struct PostDominanceFrontier : public DominanceFrontierBase { 99 static char ID; 100 PostDominanceFrontier() 101 : DominanceFrontierBase(&ID, true) {} 102 103 virtual bool runOnFunction(Function &) { 104 Frontiers.clear(); 105 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 106 Roots = DT.getRoots(); 107 if (const DomTreeNode *Root = DT.getRootNode()) 108 calculate(DT, Root); 109 return false; 110 } 111 112 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 113 AU.setPreservesAll(); 114 AU.addRequired<PostDominatorTree>(); 115 } 116 117private: 118 const DomSetType &calculate(const PostDominatorTree &DT, 119 const DomTreeNode *Node); 120}; 121 122FunctionPass* createPostDomFrontier(); 123 124} // End llvm namespace 125 126#endif 127