include/llvm/Analysis/PostDominators.h

   1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source 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
  22 /// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used
  23 /// to compute the post-dominator set.  Because there can be multiple exit nodes
  24 /// in an LLVM function, we calculate post dominators with a special null block
  25 /// which is the virtual exit node that the real exit nodes all virtually branch
  26 /// to.  Clients should be prepared to see an entry in the dominator sets with a
  27 /// null BasicBlock*.
  28 ///
  29 struct PostDominatorSet : public DominatorSetBase {
  30   PostDominatorSet() : DominatorSetBase(true) {}
  31
  32   virtual bool runOnFunction(Function &F);
  33
  34   // getAnalysisUsage - This pass does not modify the function at all.
  35   //
  36   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  37     AU.setPreservesAll();
  38   }
  39 };
  40
  41
  42
  43 //===-------------------------------------
  44 // ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
  45 // that is used to compute the immediate post-dominators.
  46 //
  47 struct ImmediatePostDominators : public ImmediateDominatorsBase {
  48   ImmediatePostDominators() : ImmediateDominatorsBase(true) {}
  49
  50   virtual bool runOnFunction(Function &F) {
  51     IDoms.clear();     // Reset from the last time we were run...
  52     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
  53     Roots = DS.getRoots();
  54     calcIDoms(DS);
  55     return false;
  56   }
  57
  58   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  59     AU.setPreservesAll();
  60     AU.addRequired<PostDominatorSet>();
  61   }
  62 };
  63
  64
  65 //===-------------------------------------
  66 // PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
  67 // compute the a post-dominator tree.
  68 //
  69 struct PostDominatorTree : public DominatorTreeBase {
  70   PostDominatorTree() : DominatorTreeBase(true) {}
  71
  72   virtual bool runOnFunction(Function &F) {
  73     reset();     // Reset from the last time we were run...
  74     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
  75     Roots = DS.getRoots();
  76     calculate(DS);
  77     return false;
  78   }
  79
  80   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  81     AU.setPreservesAll();
  82     AU.addRequired<PostDominatorSet>();
  83   }
  84 private:
  85   void calculate(const PostDominatorSet &DS);
  86 };
  87
  88
  89 //===-------------------------------------
  90 // PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
  91 // used to compute the a post-dominance frontier.
  92 //
  93 struct PostDominanceFrontier : public DominanceFrontierBase {
  94   PostDominanceFrontier() : DominanceFrontierBase(true) {}
  95
  96   virtual bool runOnFunction(Function &) {
  97     Frontiers.clear();
  98     PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
  99     Roots = DT.getRoots();
 100     if (const DominatorTree::Node *Root = DT.getRootNode())
 101       calculate(DT, Root);
 102     return false;
 103   }
 104
 105   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 106     AU.setPreservesAll();
 107     AU.addRequired<PostDominatorTree>();
 108   }
 109
 110   // stub - dummy function, just ignore it
 111   static void stub();
 112
 113 private:
 114   const DomSetType &calculate(const PostDominatorTree &DT,
 115                               const DominatorTree::Node *Node);
 116 };
 117
 118 // Make sure that any clients of this file link in PostDominators.cpp
 119 static IncludeFile
 120 POST_DOMINATOR_INCLUDE_FILE((void*)&PostDominanceFrontier::stub);
 121
 122 } // End llvm namespace
 123
 124 #endif