include/llvm/Analysis/Dominators.h

   1 //===- llvm/Analysis/DominatorSet.h - Dominator Set Calculation --*- C++ -*--=//
   2 //
   3 // This file defines the following classes:
   4 //  1. DominatorSet: Calculates the [reverse] dominator set for a method
   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 //     method.
  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 <set>
  22 #include <map>
  23 #include <vector>
  24 class Method;
  25 class BasicBlock;
  26
  27 namespace cfg {
  28
  29 //===----------------------------------------------------------------------===//
  30 //
  31 // DominatorBase - Base class that other, more interesting dominator analyses
  32 // inherit from.
  33 //
  34 class DominatorBase {
  35 protected:
  36   const BasicBlock *Root;
  37   inline DominatorBase(const BasicBlock *root = 0) : Root(root) {}
  38 public:
  39   inline const BasicBlock *getRoot() const { return Root; }
  40   bool isPostDominator() const;  // Returns true if analysis based of postdoms
  41 };
  42
  43 //===----------------------------------------------------------------------===//
  44 //
  45 // DominatorSet - Maintain a set<const BasicBlock*> for every basic block in a
  46 // method, that represents the blocks that dominate the block.
  47 //
  48 class DominatorSet : public DominatorBase {
  49 public:
  50   typedef std::set<const BasicBlock*>         DomSetType;    // Dom set for a bb
  51   // Map of dom sets
  52   typedef std::map<const BasicBlock*, DomSetType> DomSetMapType;
  53 private:
  54   DomSetMapType Doms;
  55
  56   void calcForwardDominatorSet(const Method *M);
  57 public:
  58   // DominatorSet ctor - Build either the dominator set or the post-dominator
  59   // set for a method... Building the postdominator set may require the analysis
  60   // routine to modify the method so that there is only a single return in the
  61   // method.
  62   //
  63   DominatorSet(const Method *M);
  64   DominatorSet(      Method *M, bool PostDomSet);
  65
  66   // Accessor interface:
  67   typedef DomSetMapType::const_iterator const_iterator;
  68   inline const_iterator begin() const { return Doms.begin(); }
  69   inline const_iterator end()   const { return Doms.end(); }
  70   inline const_iterator find(const BasicBlock* B) const { return Doms.find(B); }
  71
  72   // getDominators - Return the set of basic blocks that dominate the specified
  73   // block.
  74   //
  75   inline const DomSetType &getDominators(const BasicBlock *BB) const {
  76     const_iterator I = find(BB);
  77     assert(I != end() && "BB not in method!");
  78     return I->second;
  79   }
  80
  81   // dominates - Return true if A dominates B.
  82   //
  83   inline bool dominates(const BasicBlock *A, const BasicBlock *B) const {
  84     return getDominators(B).count(A) != 0;
  85   }
  86 };
  87
  88
  89 //===----------------------------------------------------------------------===//
  90 //
  91 // ImmediateDominators - Calculate the immediate dominator for each node in a
  92 // method.
  93 //
  94 class ImmediateDominators : public DominatorBase {
  95   std::map<const BasicBlock*, const BasicBlock*> IDoms;
  96   void calcIDoms(const DominatorSet &DS);
  97 public:
  98
  99   // ImmediateDominators ctor - Calculate the idom mapping, for a method, or
 100   // from a dominator set calculated for something else...
 101   //
 102   inline ImmediateDominators(const DominatorSet &DS)
 103     : DominatorBase(DS.getRoot()) {
 104     calcIDoms(DS);                         // Can be used to make rev-idoms
 105   }
 106
 107   // Accessor interface:
 108   typedef std::map<const BasicBlock*, const BasicBlock*> IDomMapType;
 109   typedef IDomMapType::const_iterator const_iterator;
 110   inline const_iterator begin() const { return IDoms.begin(); }
 111   inline const_iterator end()   const { return IDoms.end(); }
 112   inline const_iterator find(const BasicBlock* B) const { return IDoms.find(B);}
 113
 114   // operator[] - Return the idom for the specified basic block.  The start
 115   // node returns null, because it does not have an immediate dominator.
 116   //
 117   inline const BasicBlock *operator[](const BasicBlock *BB) const {
 118     std::map<const BasicBlock*, const BasicBlock*>::const_iterator I =
 119       IDoms.find(BB);
 120     return I != IDoms.end() ? I->second : 0;
 121   }
 122 };
 123
 124
 125 //===----------------------------------------------------------------------===//
 126 //
 127 // DominatorTree - Calculate the immediate dominator tree for a method.
 128 //
 129 class DominatorTree : public DominatorBase {
 130   class Node2;
 131 public:
 132   typedef Node2 Node;
 133 private:
 134   std::map<const BasicBlock*, Node*> Nodes;
 135   void calculate(const DominatorSet &DS);
 136   typedef std::map<const BasicBlock*, Node*> NodeMapType;
 137 public:
 138   class Node2 : public std::vector<Node*> {
 139     friend class DominatorTree;
 140     const BasicBlock *TheNode;
 141     Node2 * const IDom;
 142   public:
 143     inline const BasicBlock *getNode() const { return TheNode; }
 144     inline Node2 *getIDom() const { return IDom; }
 145     inline const std::vector<Node*> &getChildren() const { return *this; }
 146
 147     // dominates - Returns true iff this dominates N.  Note that this is not a
 148     // constant time operation!
 149     inline bool dominates(const Node2 *N) const {
 150       const Node2 *IDom;
 151       while ((IDom = N->getIDom()) != 0 && IDom != this)
 152         N = IDom;   // Walk up the tree
 153       return IDom != 0;
 154     }
 155
 156   private:
 157     inline Node2(const BasicBlock *node, Node *iDom)
 158       : TheNode(node), IDom(iDom) {}
 159     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 160   };
 161
 162 public:
 163   // DominatorTree ctors - Compute a dominator tree, given various amounts of
 164   // previous knowledge...
 165   inline DominatorTree(const DominatorSet &DS) : DominatorBase(DS.getRoot()) {
 166     calculate(DS);
 167   }
 168
 169   DominatorTree(const ImmediateDominators &IDoms);
 170   ~DominatorTree();
 171
 172   inline const Node *operator[](const BasicBlock *BB) const {
 173     NodeMapType::const_iterator i = Nodes.find(BB);
 174     return (i != Nodes.end()) ? i->second : 0;
 175   }
 176 };
 177
 178
 179 //===----------------------------------------------------------------------===//
 180 //
 181 // DominanceFrontier - Calculate the dominance frontiers for a method.
 182 //
 183 class DominanceFrontier : public DominatorBase {
 184 public:
 185   typedef std::set<const BasicBlock*>         DomSetType;    // Dom set for a bb
 186   typedef std::map<const BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 187 private:
 188   DomSetMapType Frontiers;
 189   const DomSetType &calcDomFrontier(const DominatorTree &DT,
 190                                     const DominatorTree::Node *Node);
 191   const DomSetType &calcPostDomFrontier(const DominatorTree &DT,
 192                                         const DominatorTree::Node *Node);
 193 public:
 194   DominanceFrontier(const DominatorSet &DS) : DominatorBase(DS.getRoot()) {
 195     const DominatorTree DT(DS);
 196     if (isPostDominator())
 197       calcPostDomFrontier(DT, DT[Root]);
 198     else
 199       calcDomFrontier(DT, DT[Root]);
 200   }
 201   DominanceFrontier(const ImmediateDominators &ID)
 202     : DominatorBase(ID.getRoot()) {
 203     const DominatorTree DT(ID);
 204     if (isPostDominator())
 205       calcPostDomFrontier(DT, DT[Root]);
 206     else
 207       calcDomFrontier(DT, DT[Root]);
 208   }
 209   DominanceFrontier(const DominatorTree &DT) : DominatorBase(DT.getRoot()) {
 210     if (isPostDominator())
 211       calcPostDomFrontier(DT, DT[Root]);
 212     else
 213       calcDomFrontier(DT, DT[Root]);
 214   }
 215
 216   // Accessor interface:
 217   typedef DomSetMapType::const_iterator const_iterator;
 218   inline const_iterator begin() const { return Frontiers.begin(); }
 219   inline const_iterator end()   const { return Frontiers.end(); }
 220   inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B);}
 221 };
 222
 223 } // End namespace cfg
 224
 225 #endif