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