include/llvm/Analysis/PostDominators.h

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