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