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