LLVM API Documentation

PostDominators.h

Go to the documentation of this file.
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 private:
00132   const DomSetType &calculate(const PostDominatorTree &DT,
00133                               const DominatorTree::Node *Node);
00134 };
00135 
00136 } // End llvm namespace
00137 
00138 // Make sure that any clients of this file link in PostDominators.cpp
00139 FORCE_DEFINING_FILE_TO_BE_LINKED(PostDominanceFrontier)
00140 
00141 #endif