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() : DominatorSetBase(false) {}
 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() : DominatorSetBase(true) {}
 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() : ImmediateDominatorsBase(false) {}
 178
 179   virtual const char *getPassName() const {
 180     return "Immediate Dominators Construction";
 181   }
 182
 183   virtual bool runOnFunction(Function &F) {
 184     IDoms.clear();     // Reset from the last time we were run...
 185     DominatorSet &DS = getAnalysis<DominatorSet>();
 186     Root = DS.getRoot();
 187     calcIDoms(DS);
 188     return false;
 189   }
 190
 191   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 192     AU.setPreservesAll();
 193     AU.addProvided(ID);
 194     AU.addRequired(DominatorSet::ID);
 195   }
 196 };
 197
 198
 199 //===-------------------------------------
 200 // ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
 201 // that is used to compute the immediate post-dominators.
 202 //
 203 struct ImmediatePostDominators : public ImmediateDominatorsBase {
 204   static AnalysisID ID;         // Build immediate postdominators
 205
 206   ImmediatePostDominators() : ImmediateDominatorsBase(true) {}
 207
 208   virtual const char *getPassName() const {
 209     return "Immediate Post-Dominators Construction";
 210   }
 211
 212   virtual bool runOnFunction(Function &F) {
 213     IDoms.clear();     // Reset from the last time we were run...
 214     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 215     Root = DS.getRoot();
 216     calcIDoms(DS);
 217     return false;
 218   }
 219
 220   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 221     AU.setPreservesAll();
 222     AU.addRequired(PostDominatorSet::ID);
 223     AU.addProvided(ID);
 224   }
 225 };
 226
 227
 228
 229 //===----------------------------------------------------------------------===//
 230 //
 231 // DominatorTree - Calculate the immediate dominator tree for a function.
 232 //
 233 class DominatorTreeBase : public DominatorBase {
 234 protected:
 235   class Node2;
 236 public:
 237   typedef Node2 Node;
 238 protected:
 239   std::map<BasicBlock*, Node*> Nodes;
 240   void reset();
 241   typedef std::map<BasicBlock*, Node*> NodeMapType;
 242 public:
 243   class Node2 : public std::vector<Node*> {
 244     friend class DominatorTree;
 245     friend class PostDominatorTree;
 246     BasicBlock *TheNode;
 247     Node2 *IDom;
 248   public:
 249     inline BasicBlock *getNode() const { return TheNode; }
 250     inline Node2 *getIDom() const { return IDom; }
 251     inline const std::vector<Node*> &getChildren() const { return *this; }
 252
 253     // dominates - Returns true iff this dominates N.  Note that this is not a
 254     // constant time operation!
 255     inline bool dominates(const Node2 *N) const {
 256       const Node2 *IDom;
 257       while ((IDom = N->getIDom()) != 0 && IDom != this)
 258         N = IDom;   // Walk up the tree
 259       return IDom != 0;
 260     }
 261
 262   private:
 263     inline Node2(BasicBlock *node, Node *iDom)
 264       : TheNode(node), IDom(iDom) {}
 265     inline Node2 *addChild(Node *C) { push_back(C); return C; }
 266   };
 267
 268 public:
 269   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 270   ~DominatorTreeBase() { reset(); }
 271
 272   virtual void releaseMemory() { reset(); }
 273
 274   inline Node *operator[](BasicBlock *BB) const {
 275     NodeMapType::const_iterator i = Nodes.find(BB);
 276     return (i != Nodes.end()) ? i->second : 0;
 277   }
 278 };
 279
 280
 281 //===-------------------------------------
 282 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 283 // compute a normal dominator tree.
 284 //
 285 struct DominatorTree : public DominatorTreeBase {
 286   static AnalysisID ID;         // Build dominator tree
 287
 288   DominatorTree() : DominatorTreeBase(false) {}
 289
 290   virtual const char *getPassName() const {
 291     return "Dominator Tree Construction";
 292   }
 293
 294   virtual bool runOnFunction(Function &F) {
 295     reset();     // Reset from the last time we were run...
 296     DominatorSet &DS = getAnalysis<DominatorSet>();
 297     Root = DS.getRoot();
 298     calculate(DS);
 299     return false;
 300   }
 301
 302   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 303     AU.setPreservesAll();
 304     AU.addProvided(ID);
 305     AU.addRequired(DominatorSet::ID);
 306   }
 307 private:
 308   void calculate(const DominatorSet &DS);
 309 };
 310
 311
 312 //===-------------------------------------
 313 // PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 314 // compute the a post-dominator tree.
 315 //
 316 struct PostDominatorTree : public DominatorTreeBase {
 317   static AnalysisID ID;         // Build immediate postdominators
 318
 319   PostDominatorTree() : DominatorTreeBase(true) {}
 320
 321   virtual const char *getPassName() const {
 322     return "Post-Dominator Tree Construction";
 323   }
 324
 325   virtual bool runOnFunction(Function &F) {
 326     reset();     // Reset from the last time we were run...
 327     PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
 328     Root = DS.getRoot();
 329     calculate(DS);
 330     return false;
 331   }
 332
 333   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 334     AU.setPreservesAll();
 335     AU.addRequired(PostDominatorSet::ID);
 336     AU.addProvided(ID);
 337   }
 338 private:
 339   void calculate(const PostDominatorSet &DS);
 340 };
 341
 342
 343 //===----------------------------------------------------------------------===//
 344 //
 345 // DominanceFrontier - Calculate the dominance frontiers for a function.
 346 //
 347 class DominanceFrontierBase : public DominatorBase {
 348 public:
 349   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 350   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 351 protected:
 352   DomSetMapType Frontiers;
 353 public:
 354   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 355
 356   virtual void releaseMemory() { Frontiers.clear(); }
 357
 358   // Accessor interface:
 359   typedef DomSetMapType::const_iterator const_iterator;
 360   inline const_iterator begin() const { return Frontiers.begin(); }
 361   inline const_iterator end()   const { return Frontiers.end(); }
 362   inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); }
 363 };
 364
 365
 366 //===-------------------------------------
 367 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 368 // compute a normal dominator tree.
 369 //
 370 struct DominanceFrontier : public DominanceFrontierBase {
 371   static AnalysisID ID;         // Build dominance frontier
 372
 373   DominanceFrontier() : DominanceFrontierBase(false) {}
 374
 375   virtual const char *getPassName() const {
 376     return "Dominance Frontier Construction";
 377   }
 378
 379   virtual bool runOnFunction(Function &) {
 380     Frontiers.clear();
 381     DominatorTree &DT = getAnalysis<DominatorTree>();
 382     Root = DT.getRoot();
 383     calculate(DT, DT[Root]);
 384     return false;
 385   }
 386
 387   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 388     AU.setPreservesAll();
 389     AU.addProvided(ID);
 390     AU.addRequired(DominatorTree::ID);
 391   }
 392 private:
 393   const DomSetType &calculate(const DominatorTree &DT,
 394                               const DominatorTree::Node *Node);
 395 };
 396
 397
 398 //===-------------------------------------
 399
 400 // PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
 401 // used to compute the a post-dominance frontier.
 402 //
 403 struct PostDominanceFrontier : public DominanceFrontierBase {
 404   static AnalysisID ID;         // Build post dominance frontier
 405
 406   PostDominanceFrontier() : DominanceFrontierBase(true) {}
 407
 408   virtual const char *getPassName() const {
 409     return "Post-Dominance Frontier Construction";
 410   }
 411
 412   virtual bool runOnFunction(Function &) {
 413     Frontiers.clear();
 414     PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
 415     Root = DT.getRoot();
 416     calculate(DT, DT[Root]);
 417     return false;
 418   }
 419
 420   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 421     AU.setPreservesAll();
 422     AU.addRequired(PostDominatorTree::ID);
 423     AU.addProvided(ID);
 424   }
 425 private:
 426   const DomSetType &calculate(const PostDominatorTree &DT,
 427                               const DominatorTree::Node *Node);
 428 };
 429
 430 #endif