LLVM API Documentation
00001 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file exposes interfaces to post dominance information. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ANALYSIS_POST_DOMINATORS_H 00015 #define LLVM_ANALYSIS_POST_DOMINATORS_H 00016 00017 #include "llvm/Analysis/Dominators.h" 00018 00019 namespace llvm { 00020 00021 //===------------------------------------- 00022 /// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase 00023 /// that is used to compute a normal immediate dominator set. 00024 /// 00025 struct ImmediatePostDominators : public ImmediateDominatorsBase { 00026 ImmediatePostDominators() : ImmediateDominatorsBase(false) {} 00027 00028 virtual bool runOnFunction(Function &F); 00029 00030 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00031 AU.setPreservesAll(); 00032 } 00033 00034 private: 00035 unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N); 00036 void Compress(BasicBlock *V, InfoRec &VInfo); 00037 BasicBlock *Eval(BasicBlock *v); 00038 void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); 00039 }; 00040 00041 /// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used 00042 /// to compute the post-dominator set. Because there can be multiple exit nodes 00043 /// in an LLVM function, we calculate post dominators with a special null block 00044 /// which is the virtual exit node that the real exit nodes all virtually branch 00045 /// to. Clients should be prepared to see an entry in the dominator sets with a 00046 /// null BasicBlock*. 00047 /// 00048 struct PostDominatorSet : public DominatorSetBase { 00049 PostDominatorSet() : DominatorSetBase(true) {} 00050 00051 virtual bool runOnFunction(Function &F); 00052 00053 /// getAnalysisUsage - This simply provides a dominator set 00054 /// 00055 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00056 AU.addRequired<ImmediatePostDominators>(); 00057 AU.setPreservesAll(); 00058 } 00059 00060 // stub - dummy function, just ignore it 00061 static void stub(); 00062 }; 00063 00064 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to 00065 /// compute the a post-dominator tree. 00066 /// 00067 struct PostDominatorTree : public DominatorTreeBase { 00068 PostDominatorTree() : DominatorTreeBase(true) {} 00069 00070 virtual bool runOnFunction(Function &F) { 00071 reset(); // Reset from the last time we were run... 00072 ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>(); 00073 Roots = IPD.getRoots(); 00074 calculate(IPD); 00075 return false; 00076 } 00077 00078 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00079 AU.setPreservesAll(); 00080 AU.addRequired<ImmediatePostDominators>(); 00081 } 00082 private: 00083 void calculate(const ImmediatePostDominators &IPD); 00084 Node *getNodeForBlock(BasicBlock *BB); 00085 }; 00086 00087 00088 /// PostETForest Class - Concrete subclass of ETForestBase that is used to 00089 /// compute a forwards post-dominator ET-Forest. 00090 struct PostETForest : public ETForestBase { 00091 PostETForest() : ETForestBase(true) {} 00092 00093 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00094 AU.setPreservesAll(); 00095 AU.addRequired<ImmediatePostDominators>(); 00096 } 00097 00098 virtual bool runOnFunction(Function &F) { 00099 reset(); // Reset from the last time we were run... 00100 ImmediatePostDominators &ID = getAnalysis<ImmediatePostDominators>(); 00101 Roots = ID.getRoots(); 00102 calculate(ID); 00103 return false; 00104 } 00105 00106 void calculate(const ImmediatePostDominators &ID); 00107 ETNode *getNodeForBlock(BasicBlock *BB); 00108 }; 00109 00110 00111 /// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is 00112 /// used to compute the a post-dominance frontier. 00113 /// 00114 struct PostDominanceFrontier : public DominanceFrontierBase { 00115 PostDominanceFrontier() : DominanceFrontierBase(true) {} 00116 00117 virtual bool runOnFunction(Function &) { 00118 Frontiers.clear(); 00119 PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); 00120 Roots = DT.getRoots(); 00121 if (const DominatorTree::Node *Root = DT.getRootNode()) 00122 calculate(DT, Root); 00123 return false; 00124 } 00125 00126 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00127 AU.setPreservesAll(); 00128 AU.addRequired<PostDominatorTree>(); 00129 } 00130 00131 // stub - dummy function, just ignore it 00132 static void stub(); 00133 00134 private: 00135 const DomSetType &calculate(const PostDominatorTree &DT, 00136 const DominatorTree::Node *Node); 00137 }; 00138 00139 // Make sure that any clients of this file link in PostDominators.cpp 00140 static IncludeFile 00141 POST_DOMINATOR_INCLUDE_FILE((void*)&PostDominanceFrontier::stub); 00142 00143 } // End llvm namespace 00144 00145 #endif