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 private:
  63   void calcIDoms(const DominatorSetBase &DS);
  64 };
  65
  66
  67 //===-------------------------------------
  68 // PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
  69 // compute the a post-dominator tree.
  70 //
  71 struct PostDominatorTree : public DominatorTreeBase {
  72   PostDominatorTree() : DominatorTreeBase(true) {}
  73
  74   virtual bool runOnFunction(Function &F) {
  75     reset();     // Reset from the last time we were run...
  76     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
  77     Roots = DS.getRoots();
  78     calculate(DS);
  79     return false;
  80   }
  81
  82   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  83     AU.setPreservesAll();
  84     AU.addRequired<PostDominatorSet>();
  85   }
  86 private:
  87   void calculate(const PostDominatorSet &DS);
  88 };
  89
  90
  91 //===-------------------------------------
  92 // PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
  93 // used to compute the a post-dominance frontier.
  94 //
  95 struct PostDominanceFrontier : public DominanceFrontierBase {
  96   PostDominanceFrontier() : DominanceFrontierBase(true) {}
  97
  98   virtual bool runOnFunction(Function &) {
  99     Frontiers.clear();
 100     PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
 101     Roots = DT.getRoots();
 102     if (const DominatorTree::Node *Root = DT.getRootNode())
 103       calculate(DT, Root);
 104     return false;
 105   }
 106
 107   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 108     AU.setPreservesAll();
 109     AU.addRequired<PostDominatorTree>();
 110   }
 111
 112   // stub - dummy function, just ignore it
 113   static void stub();
 114
 115 private:
 116   const DomSetType &calculate(const PostDominatorTree &DT,
 117                               const DominatorTree::Node *Node);
 118 };
 119
 120 // Make sure that any clients of this file link in PostDominators.cpp
 121 static IncludeFile
 122 POST_DOMINATOR_INCLUDE_FILE((void*)&PostDominanceFrontier::stub);
 123
 124 } // End llvm namespace
 125
 126 #endif