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