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   // dominates - Return true if A dominates B.  This performs the special checks
  86   // neccesary if A and B are in the same basic block.
  87   //
  88   bool dominates(Instruction *A, Instruction *B) const;
  89 };
  90
  91
  92 //===-------------------------------------
  93 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
  94 // compute a normal dominator set.
  95 //
  96 struct DominatorSet : public DominatorSetBase {
  97   static AnalysisID ID;            // Build dominator set
  98
  99   DominatorSet(AnalysisID id) : DominatorSetBase(false) { assert(id == ID); }
 100
 101   virtual const char *getPassName() const {
 102     return "Dominator Set Construction";
 103   }
 104
 105   virtual bool runOnFunction(Function &F);
 106
 107   // getAnalysisUsage - This simply provides a dominator set
 108   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 109     AU.setPreservesAll();
 110     AU.addProvided(ID);
 111   }
 112 };
 113
 114
 115 //===-------------------------------------
 116 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
 117 // compute the post-dominator set.
 118 //
 119 struct PostDominatorSet : public DominatorSetBase {
 120   static AnalysisID ID;            // Build post-dominator set
 121
 122   PostDominatorSet(AnalysisID id) : DominatorSetBase(true) { assert(id == ID); }
 123
 124   virtual const char *getPassName() const {
 125     return "Post-Dominator Set Construction";
 126   }
 127
 128   virtual bool runOnFunction(Function &F);
 129
 130   // getAnalysisUsage - This obviously provides a dominator set, but it also
 131   // uses the UnifyFunctionExitNode pass if building post-dominators
 132   //
 133   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 134 };
 135
 136
 137
 138
 139
 140 //===----------------------------------------------------------------------===//
 141 //
 142 // ImmediateDominators - Calculate the immediate dominator for each node in a
 143 // function.
 144 //
 145 class ImmediateDominatorsBase : public DominatorBase {
 146 protected:
 147   std::map<BasicBlock*, BasicBlock*> IDoms;
 148   void calcIDoms(const DominatorSetBase &DS);
 149 public:
 150   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
 151
 152   virtual void releaseMemory() { IDoms.clear(); }
 153
 154   // Accessor interface:
 155   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
 156   typedef IDomMapType::const_iterator const_iterator;
 157   inline const_iterator begin() const { return IDoms.begin(); }
 158   inline const_iterator end()   const { return IDoms.end(); }
 159   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
 160
 161   // operator[] - Return the idom for the specified basic block.  The start
 162   // node returns null, because it does not have an immediate dominator.
 163   //
 164   inline BasicBlock *operator[](BasicBlock *BB) const {
 165     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
 166     return I != IDoms.end() ? I->second : 0;
 167   }
 168 };
 169
 170 //===-------------------------------------
 171 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
 172 // is used to compute a normal immediate dominator set.
 173 //
 174 struct ImmediateDominators : public ImmediateDominatorsBase {
 175   static AnalysisID ID;         // Build immediate dominators
 176
 177   ImmediateDominators(AnalysisID id) : ImmediateDominatorsBase(false) {
 178     assert(id == ID);
 179   }
 180
 181   virtual const char *getPassName() const {
 182     return "Immediate Dominators Construction";
 183   }
 184
 185   virtual bool runOnFunction(Function &F) {
 186     IDoms.clear();     // Reset from the last time we were run...
 187     DominatorSet &DS = getAnalysis<DominatorSet>();
 188     Root = DS.getRoot();
 189     calcIDoms(DS);
 190     return false;
 191   }
 192
 193   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 194     AU.setPreservesAll();
 195     AU.addProvided(ID);
 196     AU.addRequired(DominatorSet::ID);
 197   }
 198 };
 199
 200
 201 //===-------------------------------------
 202 // ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
 203 // that is used to compute the immediate post-dominators.
 204 //
 205 struct ImmediatePostDominators : public ImmediateDominatorsBase {
 206   static AnalysisID ID;         // Build immediate postdominators
 207
 208   ImmediatePostDominators(AnalysisID id) : ImmediateDominatorsBase(true) {
 209     assert(id == ID);
 210   }
 211
 212   virtual const char *getPassName() const {
 213     return "Immediate Post-Dominators Construction";
 214   }
 215
 216   virtual bool runOnFunction(Function &F) {
 217     IDoms.clear();     // Reset from the last time we were run...
 218     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 219     Root = DS.getRoot();
 220     calcIDoms(DS);
 221     return false;
 222   }
 223
 224   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 225     AU.setPreservesAll();
 226     AU.addRequired(PostDominatorSet::ID);
 227     AU.addProvided(ID);
 228   }
 229 };
 230
 231
 232
 233 //===----------------------------------------------------------------------===//
 234 //
 235 // DominatorTree - Calculate the immediate dominator tree for a function.
 236 //
 237 class DominatorTreeBase : public DominatorBase {
 238 protected:
 239   class Node2;
 240 public:
 241   typedef Node2 Node;
 242 protected:
 243   std::map<BasicBlock*, Node*> Nodes;
 244   void reset();
 245   typedef std::map<BasicBlock*, Node*> NodeMapType;
 246 public:
 247   class Node2 : public std::vector<Node*> {
 248     friend class DominatorTree;
 249     friend class PostDominatorTree;
 250     BasicBlock *TheNode;
 251     Node2 *IDom;
 252   public:
 253     inline BasicBlock *getNode() const { return TheNode; }
 254     inline Node2 *getIDom() const { return IDom; }
 255     inline const std::vector<Node*> &getChildren() const { return *this; }
 256
 257     // dominates - Returns true iff this dominates N.  Note that this is not a
 258     // constant time operation!
 259     inline bool dominates(const Node2 *N) const {
 260       const Node2 *IDom;
 261       while ((IDom = N->getIDom()) != 0 && IDom != this)
 262         N = IDom;   // Walk up the tree
 263       return IDom != 0;
 264     }
 265
 266   private:
 267     inline Node2(BasicBlock *node, Node *iDom)
 268       : TheNode(node), IDom(iDom) {}
 269     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 270   };
 271
 272 public:
 273   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 274   ~DominatorTreeBase() { reset(); }
 275
 276   virtual void releaseMemory() { reset(); }
 277
 278   inline Node *operator[](BasicBlock *BB) const {
 279     NodeMapType::const_iterator i = Nodes.find(BB);
 280     return (i != Nodes.end()) ? i->second : 0;
 281   }
 282 };
 283
 284
 285 //===-------------------------------------
 286 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 287 // compute a normal dominator tree.
 288 //
 289 struct DominatorTree : public DominatorTreeBase {
 290   static AnalysisID ID;         // Build dominator tree
 291
 292   DominatorTree(AnalysisID id) : DominatorTreeBase(false) {
 293     assert(id == ID);
 294   }
 295
 296   virtual const char *getPassName() const {
 297     return "Dominator Tree Construction";
 298   }
 299
 300   virtual bool runOnFunction(Function &F) {
 301     reset();     // Reset from the last time we were run...
 302     DominatorSet &DS = getAnalysis<DominatorSet>();
 303     Root = DS.getRoot();
 304     calculate(DS);
 305     return false;
 306   }
 307
 308   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 309     AU.setPreservesAll();
 310     AU.addProvided(ID);
 311     AU.addRequired(DominatorSet::ID);
 312   }
 313 private:
 314   void calculate(const DominatorSet &DS);
 315 };
 316
 317
 318 //===-------------------------------------
 319 // PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 320 // compute the a post-dominator tree.
 321 //
 322 struct PostDominatorTree : public DominatorTreeBase {
 323   static AnalysisID ID;         // Build immediate postdominators
 324
 325   PostDominatorTree(AnalysisID id) : DominatorTreeBase(true) {
 326     assert(id == ID);
 327   }
 328
 329   virtual const char *getPassName() const {
 330     return "Post-Dominator Tree Construction";
 331   }
 332
 333   virtual bool runOnFunction(Function &F) {
 334     reset();     // Reset from the last time we were run...
 335     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 336     Root = DS.getRoot();
 337     calculate(DS);
 338     return false;
 339   }
 340
 341   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 342     AU.setPreservesAll();
 343     AU.addRequired(PostDominatorSet::ID);
 344     AU.addProvided(ID);
 345   }
 346 private:
 347   void calculate(const PostDominatorSet &DS);
 348 };
 349
 350
 351 //===----------------------------------------------------------------------===//
 352 //
 353 // DominanceFrontier - Calculate the dominance frontiers for a function.
 354 //
 355 class DominanceFrontierBase : public DominatorBase {
 356 public:
 357   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 358   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 359 protected:
 360   DomSetMapType Frontiers;
 361 public:
 362   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 363
 364   virtual void releaseMemory() { Frontiers.clear(); }
 365
 366   // Accessor interface:
 367   typedef DomSetMapType::const_iterator const_iterator;
 368   inline const_iterator begin() const { return Frontiers.begin(); }
 369   inline const_iterator end()   const { return Frontiers.end(); }
 370   inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); }
 371 };
 372
 373
 374 //===-------------------------------------
 375 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 376 // compute a normal dominator tree.
 377 //
 378 struct DominanceFrontier : public DominanceFrontierBase {
 379   static AnalysisID ID;         // Build dominance frontier
 380
 381   DominanceFrontier(AnalysisID id) : DominanceFrontierBase(false) {
 382     assert(id == ID);
 383   }
 384
 385   virtual const char *getPassName() const {
 386     return "Dominance Frontier Construction";
 387   }
 388
 389   virtual bool runOnFunction(Function &) {
 390     Frontiers.clear();
 391     DominatorTree &DT = getAnalysis<DominatorTree>();
 392     Root = DT.getRoot();
 393     calculate(DT, DT[Root]);
 394     return false;
 395   }
 396
 397   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 398     AU.setPreservesAll();
 399     AU.addProvided(ID);
 400     AU.addRequired(DominatorTree::ID);
 401   }
 402 private:
 403   const DomSetType &calculate(const DominatorTree &DT,
 404                               const DominatorTree::Node *Node);
 405 };
 406
 407
 408 //===-------------------------------------
 409
 410 // PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
 411 // used to compute the a post-dominance frontier.
 412 //
 413 struct PostDominanceFrontier : public DominanceFrontierBase {
 414   static AnalysisID ID;         // Build post dominance frontier
 415
 416   PostDominanceFrontier(AnalysisID id) : DominanceFrontierBase(true) {
 417     assert(id == ID);
 418   }
 419
 420   virtual const char *getPassName() const {
 421     return "Post-Dominance Frontier Construction";
 422   }
 423
 424   virtual bool runOnFunction(Function &) {
 425     Frontiers.clear();
 426     PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
 427     Root = DT.getRoot();
 428     calculate(DT, DT[Root]);
 429     return false;
 430   }
 431
 432   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 433     AU.setPreservesAll();
 434     AU.addRequired(PostDominatorTree::ID);
 435     AU.addProvided(ID);
 436   }
 437 private:
 438   const DomSetType &calculate(const PostDominatorTree &DT,
 439                               const DominatorTree::Node *Node);
 440 };
 441
 442 #endif