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 class Instruction;
  24
  25 //===----------------------------------------------------------------------===//
  26 //
  27 // DominatorBase - Base class that other, more interesting dominator analyses
  28 // inherit from.
  29 //
  30 class DominatorBase : public FunctionPass {
  31 protected:
  32   BasicBlock *Root;
  33   const bool IsPostDominators;
  34
  35   inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {}
  36 public:
  37   inline BasicBlock *getRoot() const { return Root; }
  38
  39   // Returns true if analysis based of postdoms
  40   bool isPostDominator() const { return IsPostDominators; }
  41 };
  42
  43 //===----------------------------------------------------------------------===//
  44 //
  45 // DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
  46 // function, that represents the blocks that dominate the block.
  47 //
  48 class DominatorSetBase : public DominatorBase {
  49 public:
  50   typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
  51   // Map of dom sets
  52   typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
  53 protected:
  54   DomSetMapType Doms;
  55 public:
  56   DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
  57
  58   virtual void releaseMemory() { Doms.clear(); }
  59
  60   // Accessor interface:
  61   typedef DomSetMapType::const_iterator const_iterator;
  62   typedef DomSetMapType::iterator iterator;
  63   inline const_iterator begin() const { return Doms.begin(); }
  64   inline       iterator begin()       { return Doms.begin(); }
  65   inline const_iterator end()   const { return Doms.end(); }
  66   inline       iterator end()         { return Doms.end(); }
  67   inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
  68   inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
  69
  70   // getDominators - Return the set of basic blocks that dominate the specified
  71   // block.
  72   //
  73   inline const DomSetType &getDominators(BasicBlock *BB) const {
  74     const_iterator I = find(BB);
  75     assert(I != end() && "BB not in function!");
  76     return I->second;
  77   }
  78
  79   // dominates - Return true if A dominates B.
  80   //
  81   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
  82     return getDominators(B).count(A) != 0;
  83   }
  84
  85   // print - Convert to human readable form
  86   virtual void print(std::ostream &OS) const;
  87
  88   // dominates - Return true if A dominates B.  This performs the special checks
  89   // neccesary if A and B are in the same basic block.
  90   //
  91   bool dominates(Instruction *A, Instruction *B) const;
  92 };
  93
  94
  95 //===-------------------------------------
  96 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
  97 // compute a normal dominator set.
  98 //
  99 struct DominatorSet : public DominatorSetBase {
 100   DominatorSet() : DominatorSetBase(false) {}
 101
 102   virtual bool runOnFunction(Function &F);
 103
 104   // getAnalysisUsage - This simply provides a dominator set
 105   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 106     AU.setPreservesAll();
 107   }
 108 };
 109
 110
 111 //===-------------------------------------
 112 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
 113 // compute the post-dominator set.
 114 //
 115 struct PostDominatorSet : public DominatorSetBase {
 116   PostDominatorSet() : DominatorSetBase(true) {}
 117
 118   virtual bool runOnFunction(Function &F);
 119
 120   // getAnalysisUsage - This obviously provides a dominator set, but it also
 121   // uses the UnifyFunctionExitNode pass if building post-dominators
 122   //
 123   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 124 };
 125
 126
 127
 128
 129
 130 //===----------------------------------------------------------------------===//
 131 //
 132 // ImmediateDominators - Calculate the immediate dominator for each node in a
 133 // function.
 134 //
 135 class ImmediateDominatorsBase : public DominatorBase {
 136 protected:
 137   std::map<BasicBlock*, BasicBlock*> IDoms;
 138   void calcIDoms(const DominatorSetBase &DS);
 139 public:
 140   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
 141
 142   virtual void releaseMemory() { IDoms.clear(); }
 143
 144   // Accessor interface:
 145   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
 146   typedef IDomMapType::const_iterator const_iterator;
 147   inline const_iterator begin() const { return IDoms.begin(); }
 148   inline const_iterator end()   const { return IDoms.end(); }
 149   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
 150
 151   // operator[] - Return the idom for the specified basic block.  The start
 152   // node returns null, because it does not have an immediate dominator.
 153   //
 154   inline BasicBlock *operator[](BasicBlock *BB) const {
 155     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
 156     return I != IDoms.end() ? I->second : 0;
 157   }
 158
 159   // print - Convert to human readable form
 160   virtual void print(std::ostream &OS) const;
 161 };
 162
 163 //===-------------------------------------
 164 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
 165 // is used to compute a normal immediate dominator set.
 166 //
 167 struct ImmediateDominators : public ImmediateDominatorsBase {
 168   ImmediateDominators() : ImmediateDominatorsBase(false) {}
 169
 170   virtual bool runOnFunction(Function &F) {
 171     IDoms.clear();     // Reset from the last time we were run...
 172     DominatorSet &DS = getAnalysis<DominatorSet>();
 173     Root = DS.getRoot();
 174     calcIDoms(DS);
 175     return false;
 176   }
 177
 178   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 179     AU.setPreservesAll();
 180     AU.addRequired<DominatorSet>();
 181   }
 182 };
 183
 184
 185 //===-------------------------------------
 186 // ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
 187 // that is used to compute the immediate post-dominators.
 188 //
 189 struct ImmediatePostDominators : public ImmediateDominatorsBase {
 190   ImmediatePostDominators() : ImmediateDominatorsBase(true) {}
 191
 192   virtual bool runOnFunction(Function &F) {
 193     IDoms.clear();     // Reset from the last time we were run...
 194     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 195     Root = DS.getRoot();
 196     calcIDoms(DS);
 197     return false;
 198   }
 199
 200   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 201     AU.setPreservesAll();
 202     AU.addRequired<PostDominatorSet>();
 203   }
 204 };
 205
 206
 207
 208 //===----------------------------------------------------------------------===//
 209 //
 210 // DominatorTree - Calculate the immediate dominator tree for a function.
 211 //
 212 class DominatorTreeBase : public DominatorBase {
 213 protected:
 214   class Node2;
 215 public:
 216   typedef Node2 Node;
 217 protected:
 218   std::map<BasicBlock*, Node*> Nodes;
 219   void reset();
 220   typedef std::map<BasicBlock*, Node*> NodeMapType;
 221 public:
 222   class Node2 : public std::vector<Node*> {
 223     friend class DominatorTree;
 224     friend class PostDominatorTree;
 225     BasicBlock *TheNode;
 226     Node2 *IDom;
 227   public:
 228     inline BasicBlock *getNode() const { return TheNode; }
 229     inline Node2 *getIDom() const { return IDom; }
 230     inline const std::vector<Node*> &getChildren() const { return *this; }
 231
 232     // dominates - Returns true iff this dominates N.  Note that this is not a
 233     // constant time operation!
 234     inline bool dominates(const Node2 *N) const {
 235       const Node2 *IDom;
 236       while ((IDom = N->getIDom()) != 0 && IDom != this)
 237         N = IDom;   // Walk up the tree
 238       return IDom != 0;
 239     }
 240
 241   private:
 242     inline Node2(BasicBlock *node, Node *iDom)
 243       : TheNode(node), IDom(iDom) {}
 244     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 245   };
 246
 247 public:
 248   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 249   ~DominatorTreeBase() { reset(); }
 250
 251   virtual void releaseMemory() { reset(); }
 252
 253   inline Node *operator[](BasicBlock *BB) const {
 254     NodeMapType::const_iterator i = Nodes.find(BB);
 255     return (i != Nodes.end()) ? i->second : 0;
 256   }
 257
 258   // print - Convert to human readable form
 259   virtual void print(std::ostream &OS) const;
 260 };
 261
 262
 263 //===-------------------------------------
 264 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 265 // compute a normal dominator tree.
 266 //
 267 struct DominatorTree : public DominatorTreeBase {
 268   DominatorTree() : DominatorTreeBase(false) {}
 269
 270   virtual bool runOnFunction(Function &F) {
 271     reset();     // Reset from the last time we were run...
 272     DominatorSet &DS = getAnalysis<DominatorSet>();
 273     Root = DS.getRoot();
 274     calculate(DS);
 275     return false;
 276   }
 277
 278   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 279     AU.setPreservesAll();
 280     AU.addRequired<DominatorSet>();
 281   }
 282 private:
 283   void calculate(const DominatorSet &DS);
 284 };
 285
 286
 287 //===-------------------------------------
 288 // PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 289 // compute the a post-dominator tree.
 290 //
 291 struct PostDominatorTree : public DominatorTreeBase {
 292   PostDominatorTree() : DominatorTreeBase(true) {}
 293
 294   virtual bool runOnFunction(Function &F) {
 295     reset();     // Reset from the last time we were run...
 296     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 297     Root = DS.getRoot();
 298     calculate(DS);
 299     return false;
 300   }
 301
 302   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 303     AU.setPreservesAll();
 304     AU.addRequired<PostDominatorSet>();
 305   }
 306 private:
 307   void calculate(const PostDominatorSet &DS);
 308 };
 309
 310
 311 //===----------------------------------------------------------------------===//
 312 //
 313 // DominanceFrontier - Calculate the dominance frontiers for a function.
 314 //
 315 class DominanceFrontierBase : public DominatorBase {
 316 public:
 317   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 318   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 319 protected:
 320   DomSetMapType Frontiers;
 321 public:
 322   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 323
 324   virtual void releaseMemory() { Frontiers.clear(); }
 325
 326   // Accessor interface:
 327   typedef DomSetMapType::const_iterator const_iterator;
 328   inline const_iterator begin() const { return Frontiers.begin(); }
 329   inline const_iterator end()   const { return Frontiers.end(); }
 330   inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); }
 331
 332   // print - Convert to human readable form
 333   virtual void print(std::ostream &OS) const;
 334 };
 335
 336
 337 //===-------------------------------------
 338 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 339 // compute a normal dominator tree.
 340 //
 341 struct DominanceFrontier : public DominanceFrontierBase {
 342   DominanceFrontier() : DominanceFrontierBase(false) {}
 343
 344   virtual bool runOnFunction(Function &) {
 345     Frontiers.clear();
 346     DominatorTree &DT = getAnalysis<DominatorTree>();
 347     Root = DT.getRoot();
 348     calculate(DT, DT[Root]);
 349     return false;
 350   }
 351
 352   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 353     AU.setPreservesAll();
 354     AU.addRequired<DominatorTree>();
 355   }
 356 private:
 357   const DomSetType &calculate(const DominatorTree &DT,
 358                               const DominatorTree::Node *Node);
 359 };
 360
 361
 362 //===-------------------------------------
 363
 364 // PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
 365 // used to compute the a post-dominance frontier.
 366 //
 367 struct PostDominanceFrontier : public DominanceFrontierBase {
 368   PostDominanceFrontier() : DominanceFrontierBase(true) {}
 369
 370   virtual bool runOnFunction(Function &) {
 371     Frontiers.clear();
 372     PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
 373     Root = DT.getRoot();
 374     calculate(DT, DT[Root]);
 375     return false;
 376   }
 377
 378   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 379     AU.setPreservesAll();
 380     AU.addRequired<PostDominatorTree>();
 381   }
 382 private:
 383   const DomSetType &calculate(const PostDominatorTree &DT,
 384                               const DominatorTree::Node *Node);
 385 };
 386
 387 #endif