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