include/llvm/Analysis/Dominators.h

   1 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation ---*- C++ -*--=//
   2 //
   3 // This file defines the following classes:
   4 //  1. DominatorSet: Calculates the [reverse] dominator set for a function
   5 //  2. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
   6 //     and their immediate dominator.
   7 //  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
   8 //     structure.
   9 //  4. DominanceFrontier: Calculate and hold the dominance frontier for a
  10 //     function.
  11 //
  12 //  These data structures are listed in increasing order of complexity.  It
  13 //  takes longer to calculate the dominator frontier, for example, than the
  14 //  ImmediateDominator mapping.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_DOMINATORS_H
  19 #define LLVM_DOMINATORS_H
  20
  21 #include "llvm/Pass.h"
  22 #include <set>
  23
  24 namespace cfg {
  25
  26 //===----------------------------------------------------------------------===//
  27 //
  28 // DominatorBase - Base class that other, more interesting dominator analyses
  29 // inherit from.
  30 //
  31 class DominatorBase : public FunctionPass {
  32 protected:
  33   BasicBlock *Root;
  34   const bool IsPostDominators;
  35
  36   inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {}
  37 public:
  38   inline const BasicBlock *getRoot() const { return Root; }
  39   inline       BasicBlock *getRoot()       { return Root; }
  40
  41   // Returns true if analysis based of postdoms
  42   bool isPostDominator() const { return IsPostDominators; }
  43 };
  44
  45 //===----------------------------------------------------------------------===//
  46 //
  47 // DominatorSet - Maintain a set<const BasicBlock*> for every basic block in a
  48 // function, that represents the blocks that dominate the block.
  49 //
  50 class DominatorSet : public DominatorBase {
  51 public:
  52   typedef std::set<const BasicBlock*>         DomSetType;    // Dom set for a bb
  53   // Map of dom sets
  54   typedef std::map<const BasicBlock*, DomSetType> DomSetMapType;
  55 private:
  56   DomSetMapType Doms;
  57
  58   void calcForwardDominatorSet(Function *F);
  59   void calcPostDominatorSet(Function *F);
  60 public:
  61   // DominatorSet ctor - Build either the dominator set or the post-dominator
  62   // set for a function...
  63   //
  64   static AnalysisID ID;            // Build dominator set
  65   static AnalysisID PostDomID;     // Build postdominator set
  66
  67   DominatorSet(AnalysisID id) : DominatorBase(id == PostDomID) {}
  68
  69   virtual bool runOnFunction(Function *F);
  70
  71   // Accessor interface:
  72   typedef DomSetMapType::const_iterator const_iterator;
  73   typedef DomSetMapType::iterator iterator;
  74   inline const_iterator begin() const { return Doms.begin(); }
  75   inline       iterator begin()       { return Doms.begin(); }
  76   inline const_iterator end()   const { return Doms.end(); }
  77   inline       iterator end()         { return Doms.end(); }
  78   inline const_iterator find(const BasicBlock* B) const { return Doms.find(B); }
  79   inline       iterator find(      BasicBlock* B)       { return Doms.find(B); }
  80
  81   // getDominators - Return the set of basic blocks that dominate the specified
  82   // block.
  83   //
  84   inline const DomSetType &getDominators(const BasicBlock *BB) const {
  85     const_iterator I = find(BB);
  86     assert(I != end() && "BB not in function!");
  87     return I->second;
  88   }
  89
  90   // dominates - Return true if A dominates B.
  91   //
  92   inline bool dominates(const BasicBlock *A, const BasicBlock *B) const {
  93     return getDominators(B).count(A) != 0;
  94   }
  95
  96   // getAnalysisUsage - This obviously provides a dominator set, but it also
  97   // uses the UnifyFunctionExitNode pass if building post-dominators
  98   //
  99   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 100 };
 101
 102
 103 //===----------------------------------------------------------------------===//
 104 //
 105 // ImmediateDominators - Calculate the immediate dominator for each node in a
 106 // function.
 107 //
 108 class ImmediateDominators : public DominatorBase {
 109   std::map<const BasicBlock*, const BasicBlock*> IDoms;
 110   void calcIDoms(const DominatorSet &DS);
 111 public:
 112
 113   // ImmediateDominators ctor - Calculate the idom or post-idom mapping,
 114   // for a function...
 115   //
 116   static AnalysisID ID;         // Build immediate dominators
 117   static AnalysisID PostDomID;  // Build immediate postdominators
 118
 119   ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {}
 120
 121   virtual bool runOnFunction(Function *F) {
 122     IDoms.clear();     // Reset from the last time we were run...
 123     DominatorSet *DS;
 124     if (isPostDominator())
 125       DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
 126     else
 127       DS = &getAnalysis<DominatorSet>();
 128
 129     Root = DS->getRoot();
 130     calcIDoms(*DS);                         // Can be used to make rev-idoms
 131     return false;
 132   }
 133
 134   // Accessor interface:
 135   typedef std::map<const BasicBlock*, const BasicBlock*> IDomMapType;
 136   typedef IDomMapType::const_iterator const_iterator;
 137   inline const_iterator begin() const { return IDoms.begin(); }
 138   inline const_iterator end()   const { return IDoms.end(); }
 139   inline const_iterator find(const BasicBlock* B) const { return IDoms.find(B);}
 140
 141   // operator[] - Return the idom for the specified basic block.  The start
 142   // node returns null, because it does not have an immediate dominator.
 143   //
 144   inline const BasicBlock *operator[](const BasicBlock *BB) const {
 145     std::map<const BasicBlock*, const BasicBlock*>::const_iterator I =
 146       IDoms.find(BB);
 147     return I != IDoms.end() ? I->second : 0;
 148   }
 149
 150   // getAnalysisUsage - This obviously provides a dominator tree, but it
 151   // can only do so with the input of dominator sets
 152   //
 153   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 154     AU.setPreservesAll();
 155     if (isPostDominator()) {
 156       AU.addRequired(DominatorSet::PostDomID);
 157       AU.addProvided(PostDomID);
 158     } else {
 159       AU.addRequired(DominatorSet::ID);
 160       AU.addProvided(ID);
 161     }
 162   }
 163 };
 164
 165
 166 //===----------------------------------------------------------------------===//
 167 //
 168 // DominatorTree - Calculate the immediate dominator tree for a function.
 169 //
 170 class DominatorTree : public DominatorBase {
 171   class Node2;
 172 public:
 173   typedef Node2 Node;
 174 private:
 175   std::map<const BasicBlock*, Node*> Nodes;
 176   void calculate(const DominatorSet &DS);
 177   void reset();
 178   typedef std::map<const BasicBlock*, Node*> NodeMapType;
 179 public:
 180   class Node2 : public std::vector<Node*> {
 181     friend class DominatorTree;
 182     const BasicBlock *TheNode;
 183     Node2 * const IDom;
 184   public:
 185     inline const BasicBlock *getNode() const { return TheNode; }
 186     inline Node2 *getIDom() const { return IDom; }
 187     inline const std::vector<Node*> &getChildren() const { return *this; }
 188
 189     // dominates - Returns true iff this dominates N.  Note that this is not a
 190     // constant time operation!
 191     inline bool dominates(const Node2 *N) const {
 192       const Node2 *IDom;
 193       while ((IDom = N->getIDom()) != 0 && IDom != this)
 194         N = IDom;   // Walk up the tree
 195       return IDom != 0;
 196     }
 197
 198   private:
 199     inline Node2(const BasicBlock *node, Node *iDom)
 200       : TheNode(node), IDom(iDom) {}
 201     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 202   };
 203
 204 public:
 205   // DominatorTree ctor - Compute a dominator tree, given various amounts of
 206   // previous knowledge...
 207   static AnalysisID ID;         // Build dominator tree
 208   static AnalysisID PostDomID;  // Build postdominator tree
 209
 210   DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {}
 211   ~DominatorTree() { reset(); }
 212
 213   virtual bool runOnFunction(Function *F) {
 214     reset();
 215     DominatorSet *DS;
 216     if (isPostDominator())
 217       DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
 218     else
 219       DS = &getAnalysis<DominatorSet>();
 220     Root = DS->getRoot();
 221     calculate(*DS);                         // Can be used to make rev-idoms
 222     return false;
 223   }
 224
 225   inline const Node *operator[](const BasicBlock *BB) const {
 226     NodeMapType::const_iterator i = Nodes.find(BB);
 227     return (i != Nodes.end()) ? i->second : 0;
 228   }
 229
 230   // getAnalysisUsage - This obviously provides a dominator tree, but it
 231   // uses dominator sets
 232   //
 233   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 234     AU.setPreservesAll();
 235     if (isPostDominator()) {
 236       AU.addRequired(DominatorSet::PostDomID);
 237       AU.addProvided(PostDomID);
 238     } else {
 239       AU.addRequired(DominatorSet::ID);
 240       AU.addProvided(ID);
 241     }
 242   }
 243 };
 244
 245
 246 //===----------------------------------------------------------------------===//
 247 //
 248 // DominanceFrontier - Calculate the dominance frontiers for a function.
 249 //
 250 class DominanceFrontier : public DominatorBase {
 251 public:
 252   typedef std::set<const BasicBlock*>         DomSetType;    // Dom set for a bb
 253   typedef std::map<const BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 254 private:
 255   DomSetMapType Frontiers;
 256   const DomSetType &calcDomFrontier(const DominatorTree &DT,
 257                                     const DominatorTree::Node *Node);
 258   const DomSetType &calcPostDomFrontier(const DominatorTree &DT,
 259                                         const DominatorTree::Node *Node);
 260 public:
 261
 262   // DominatorFrontier ctor - Compute dominator frontiers for a function
 263   //
 264   static AnalysisID ID;         // Build dominator frontier
 265   static AnalysisID PostDomID;  // Build postdominator frontier
 266
 267   DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {}
 268
 269   virtual bool runOnFunction(Function *) {
 270     Frontiers.clear();
 271     DominatorTree *DT;
 272     if (isPostDominator())
 273       DT = &getAnalysis<DominatorTree>(DominatorTree::PostDomID);
 274     else
 275       DT = &getAnalysis<DominatorTree>();
 276     Root = DT->getRoot();
 277
 278     if (isPostDominator())
 279       calcPostDomFrontier(*DT, (*DT)[Root]);
 280     else
 281       calcDomFrontier(*DT, (*DT)[Root]);
 282     return false;
 283   }
 284
 285   // Accessor interface:
 286   typedef DomSetMapType::const_iterator const_iterator;
 287   inline const_iterator begin() const { return Frontiers.begin(); }
 288   inline const_iterator end()   const { return Frontiers.end(); }
 289   inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B); }
 290
 291   // getAnalysisUsage - This obviously provides the dominance frontier, but it
 292   // uses dominator sets
 293   //
 294   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 295     AU.setPreservesAll();
 296     if (isPostDominator()) {
 297       AU.addRequired(DominatorTree::PostDomID);
 298       AU.addProvided(PostDomID);
 299     } else {
 300       AU.addRequired(DominatorTree::ID);
 301       AU.addProvided(ID);
 302     }
 303   }
 304 };
 305
 306 } // End namespace cfg
 307
 308 #endif