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 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 "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 MethodPass {
  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 // method, 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(Method *M);
  59   void calcPostDominatorSet(Method *M);
  60 public:
  61   // DominatorSet ctor - Build either the dominator set or the post-dominator
  62   // set for a method...
  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 runOnMethod(Method *M);
  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 method!");
  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   // getAnalysisUsageInfo - This obviously provides a dominator set, but it also
  97   // uses the UnifyMethodExitNode pass if building post-dominators
  98   //
  99   virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
 100                                     Pass::AnalysisSet &Destroyed,
 101                                     Pass::AnalysisSet &Provided);
 102 };
 103
 104
 105 //===----------------------------------------------------------------------===//
 106 //
 107 // ImmediateDominators - Calculate the immediate dominator for each node in a
 108 // method.
 109 //
 110 class ImmediateDominators : public DominatorBase {
 111   std::map<const BasicBlock*, const BasicBlock*> IDoms;
 112   void calcIDoms(const DominatorSet &DS);
 113 public:
 114
 115   // ImmediateDominators ctor - Calculate the idom or post-idom mapping,
 116   // for a method...
 117   //
 118   static AnalysisID ID;         // Build immediate dominators
 119   static AnalysisID PostDomID;  // Build immediate postdominators
 120
 121   ImmediateDominators(AnalysisID id) : DominatorBase(id == PostDomID) {}
 122
 123   virtual bool runOnMethod(Method *M) {
 124     IDoms.clear();     // Reset from the last time we were run...
 125     DominatorSet *DS;
 126     if (isPostDominator())
 127       DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
 128     else
 129       DS = &getAnalysis<DominatorSet>();
 130
 131     Root = DS->getRoot();
 132     calcIDoms(*DS);                         // Can be used to make rev-idoms
 133     return false;
 134   }
 135
 136   // Accessor interface:
 137   typedef std::map<const BasicBlock*, const BasicBlock*> IDomMapType;
 138   typedef IDomMapType::const_iterator const_iterator;
 139   inline const_iterator begin() const { return IDoms.begin(); }
 140   inline const_iterator end()   const { return IDoms.end(); }
 141   inline const_iterator find(const BasicBlock* B) const { return IDoms.find(B);}
 142
 143   // operator[] - Return the idom for the specified basic block.  The start
 144   // node returns null, because it does not have an immediate dominator.
 145   //
 146   inline const BasicBlock *operator[](const BasicBlock *BB) const {
 147     std::map<const BasicBlock*, const BasicBlock*>::const_iterator I =
 148       IDoms.find(BB);
 149     return I != IDoms.end() ? I->second : 0;
 150   }
 151
 152   // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
 153   // can only do so with the input of dominator sets
 154   //
 155   virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
 156                                     Pass::AnalysisSet &Destroyed,
 157                                     Pass::AnalysisSet &Provided) {
 158     if (isPostDominator()) {
 159       Requires.push_back(DominatorSet::PostDomID);
 160       Provided.push_back(PostDomID);
 161     } else {
 162       Requires.push_back(DominatorSet::ID);
 163       Provided.push_back(ID);
 164     }
 165   }
 166 };
 167
 168
 169 //===----------------------------------------------------------------------===//
 170 //
 171 // DominatorTree - Calculate the immediate dominator tree for a method.
 172 //
 173 class DominatorTree : public DominatorBase {
 174   class Node2;
 175 public:
 176   typedef Node2 Node;
 177 private:
 178   std::map<const BasicBlock*, Node*> Nodes;
 179   void calculate(const DominatorSet &DS);
 180   void reset();
 181   typedef std::map<const BasicBlock*, Node*> NodeMapType;
 182 public:
 183   class Node2 : public std::vector<Node*> {
 184     friend class DominatorTree;
 185     const BasicBlock *TheNode;
 186     Node2 * const IDom;
 187   public:
 188     inline const BasicBlock *getNode() const { return TheNode; }
 189     inline Node2 *getIDom() const { return IDom; }
 190     inline const std::vector<Node*> &getChildren() const { return *this; }
 191
 192     // dominates - Returns true iff this dominates N.  Note that this is not a
 193     // constant time operation!
 194     inline bool dominates(const Node2 *N) const {
 195       const Node2 *IDom;
 196       while ((IDom = N->getIDom()) != 0 && IDom != this)
 197         N = IDom;   // Walk up the tree
 198       return IDom != 0;
 199     }
 200
 201   private:
 202     inline Node2(const BasicBlock *node, Node *iDom)
 203       : TheNode(node), IDom(iDom) {}
 204     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 205   };
 206
 207 public:
 208   // DominatorTree ctor - Compute a dominator tree, given various amounts of
 209   // previous knowledge...
 210   static AnalysisID ID;         // Build dominator tree
 211   static AnalysisID PostDomID;  // Build postdominator tree
 212
 213   DominatorTree(AnalysisID id) : DominatorBase(id == PostDomID) {}
 214   ~DominatorTree() { reset(); }
 215
 216   virtual bool runOnMethod(Method *M) {
 217     reset();
 218     DominatorSet *DS;
 219     if (isPostDominator())
 220       DS = &getAnalysis<DominatorSet>(DominatorSet::PostDomID);
 221     else
 222       DS = &getAnalysis<DominatorSet>();
 223     Root = DS->getRoot();
 224     calculate(*DS);                         // Can be used to make rev-idoms
 225     return false;
 226   }
 227
 228   inline const Node *operator[](const BasicBlock *BB) const {
 229     NodeMapType::const_iterator i = Nodes.find(BB);
 230     return (i != Nodes.end()) ? i->second : 0;
 231   }
 232
 233   // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
 234   // uses dominator sets
 235   //
 236   virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
 237                                     Pass::AnalysisSet &Destroyed,
 238                                     Pass::AnalysisSet &Provided) {
 239     if (isPostDominator()) {
 240       Requires.push_back(DominatorSet::PostDomID);
 241       Provided.push_back(PostDomID);
 242     } else {
 243       Requires.push_back(DominatorSet::ID);
 244       Provided.push_back(ID);
 245     }
 246   }
 247 };
 248
 249
 250 //===----------------------------------------------------------------------===//
 251 //
 252 // DominanceFrontier - Calculate the dominance frontiers for a method.
 253 //
 254 class DominanceFrontier : public DominatorBase {
 255 public:
 256   typedef std::set<const BasicBlock*>         DomSetType;    // Dom set for a bb
 257   typedef std::map<const BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 258 private:
 259   DomSetMapType Frontiers;
 260   const DomSetType &calcDomFrontier(const DominatorTree &DT,
 261                                     const DominatorTree::Node *Node);
 262   const DomSetType &calcPostDomFrontier(const DominatorTree &DT,
 263                                         const DominatorTree::Node *Node);
 264 public:
 265
 266   // DominatorFrontier ctor - Compute dominator frontiers for a method
 267   //
 268   static AnalysisID ID;         // Build dominator frontier
 269   static AnalysisID PostDomID;  // Build postdominator frontier
 270
 271   DominanceFrontier(AnalysisID id) : DominatorBase(id == PostDomID) {}
 272
 273   virtual bool runOnMethod(Method *M) {
 274     Frontiers.clear();
 275     DominatorTree *DT;
 276     if (isPostDominator())
 277       DT = &getAnalysis<DominatorTree>(DominatorTree::PostDomID);
 278     else
 279       DT = &getAnalysis<DominatorTree>();
 280     Root = DT->getRoot();
 281
 282     if (isPostDominator())
 283       calcPostDomFrontier(*DT, (*DT)[Root]);
 284     else
 285       calcDomFrontier(*DT, (*DT)[Root]);
 286     return false;
 287   }
 288
 289   // Accessor interface:
 290   typedef DomSetMapType::const_iterator const_iterator;
 291   inline const_iterator begin() const { return Frontiers.begin(); }
 292   inline const_iterator end()   const { return Frontiers.end(); }
 293   inline const_iterator find(const BasicBlock* B) const { return Frontiers.find(B); }
 294
 295   // getAnalysisUsageInfo - This obviously provides a dominator tree, but it
 296   // uses dominator sets
 297   //
 298   virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires,
 299                                     Pass::AnalysisSet &Destroyed,
 300                                     Pass::AnalysisSet &Provided) {
 301     if (isPostDominator()) {
 302       Requires.push_back(DominatorTree::PostDomID);
 303       Provided.push_back(PostDomID);
 304     } else {
 305       Requires.push_back(DominatorTree::ID);
 306       Provided.push_back(ID);
 307     }
 308   }
 309 };
 310
 311 } // End namespace cfg
 312
 313 #endif