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_ANALYSIS_DOMINATORS_H
  19 #define LLVM_ANALYSIS_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
  71   /// getDominators - Return the set of basic blocks that dominate the specified
  72   /// block.
  73   ///
  74   inline const DomSetType &getDominators(BasicBlock *BB) const {
  75     const_iterator I = find(BB);
  76     assert(I != end() && "BB not in function!");
  77     return I->second;
  78   }
  79
  80   /// dominates - Return true if A dominates B.
  81   ///
  82   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
  83     return getDominators(B).count(A) != 0;
  84   }
  85
  86   /// properlyDominates - Return true if A dominates B and A != B.
  87   ///
  88   bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
  89     return dominates(A, B) && A != B;
  90   }
  91
  92   /// print - Convert to human readable form
  93   virtual void print(std::ostream &OS) const;
  94
  95   /// dominates - Return true if A dominates B.  This performs the special
  96   /// checks neccesary if A and B are in the same basic block.
  97   ///
  98   bool dominates(Instruction *A, Instruction *B) const;
  99
 100   //===--------------------------------------------------------------------===//
 101   // API to update (Post)DominatorSet information based on modifications to
 102   // the CFG...
 103
 104   /// addBasicBlock - Call to update the dominator set with information about a
 105   /// new block that was inserted into the function.
 106   void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
 107     assert(find(BB) == end() && "Block already in DominatorSet!");
 108     Doms.insert(std::make_pair(BB, Dominators));
 109   }
 110
 111   // addDominator - If a new block is inserted into the CFG, then method may be
 112   // called to notify the blocks it dominates that it is in their set.
 113   //
 114   void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
 115     iterator I = find(BB);
 116     assert(I != end() && "BB is not in DominatorSet!");
 117     I->second.insert(NewDominator);
 118   }
 119 };
 120
 121
 122 //===-------------------------------------
 123 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
 124 // compute a normal dominator set.
 125 //
 126 struct DominatorSet : public DominatorSetBase {
 127   DominatorSet() : DominatorSetBase(false) {}
 128
 129   virtual bool runOnFunction(Function &F);
 130
 131   // getAnalysisUsage - This simply provides a dominator set
 132   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 133     AU.setPreservesAll();
 134   }
 135 private:
 136   void calculateDominatorsFromBlock(BasicBlock *BB);
 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     return get(BB);
 166   }
 167
 168   // get() - Synonym for operator[].
 169   inline BasicBlock *get(BasicBlock *BB) const {
 170     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
 171     return I != IDoms.end() ? I->second : 0;
 172   }
 173
 174   //===--------------------------------------------------------------------===//
 175   // API to update Immediate(Post)Dominators information based on modifications
 176   // to the CFG...
 177
 178   /// addNewBlock - Add a new block to the CFG, with the specified immediate
 179   /// dominator.
 180   ///
 181   void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
 182     assert(get(BB) == 0 && "BasicBlock already in idom info!");
 183     IDoms[BB] = IDom;
 184   }
 185
 186   /// setImmediateDominator - Update the immediate dominator information to
 187   /// change the current immediate dominator for the specified block to another
 188   /// block.  This method requires that BB already have an IDom, otherwise just
 189   /// use addNewBlock.
 190   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
 191     assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
 192     IDoms[BB] = NewIDom;
 193   }
 194
 195   // print - Convert to human readable form
 196   virtual void print(std::ostream &OS) const;
 197 };
 198
 199 //===-------------------------------------
 200 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
 201 // is used to compute a normal immediate dominator set.
 202 //
 203 struct ImmediateDominators : public ImmediateDominatorsBase {
 204   ImmediateDominators() : ImmediateDominatorsBase(false) {}
 205
 206   virtual bool runOnFunction(Function &F) {
 207     IDoms.clear();     // Reset from the last time we were run...
 208     DominatorSet &DS = getAnalysis<DominatorSet>();
 209     Root = DS.getRoot();
 210     calcIDoms(DS);
 211     return false;
 212   }
 213
 214   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 215     AU.setPreservesAll();
 216     AU.addRequired<DominatorSet>();
 217   }
 218 };
 219
 220
 221 //===----------------------------------------------------------------------===//
 222 //
 223 // DominatorTree - Calculate the immediate dominator tree for a function.
 224 //
 225 class DominatorTreeBase : public DominatorBase {
 226 protected:
 227   class Node2;
 228 public:
 229   typedef Node2 Node;
 230 protected:
 231   std::map<BasicBlock*, Node*> Nodes;
 232   void reset();
 233   typedef std::map<BasicBlock*, Node*> NodeMapType;
 234 public:
 235   class Node2 {
 236     friend class DominatorTree;
 237     friend class PostDominatorTree;
 238     friend class DominatorTreeBase;
 239     BasicBlock *TheNode;
 240     Node2 *IDom;
 241     std::vector<Node*> Children;
 242   public:
 243     typedef std::vector<Node*>::iterator iterator;
 244     typedef std::vector<Node*>::const_iterator const_iterator;
 245
 246     iterator begin()             { return Children.begin(); }
 247     iterator end()               { return Children.end(); }
 248     const_iterator begin() const { return Children.begin(); }
 249     const_iterator end()   const { return Children.end(); }
 250
 251     inline BasicBlock *getNode() const { return TheNode; }
 252     inline Node2 *getIDom() const { return IDom; }
 253     inline const std::vector<Node*> &getChildren() const { return Children; }
 254
 255     // dominates - Returns true iff this dominates N.  Note that this is not a
 256     // constant time operation!
 257     inline bool dominates(const Node2 *N) const {
 258       const Node2 *IDom;
 259       while ((IDom = N->getIDom()) != 0 && IDom != this)
 260         N = IDom;   // Walk up the tree
 261       return IDom != 0;
 262     }
 263
 264   private:
 265     inline Node2(BasicBlock *node, Node *iDom)
 266       : TheNode(node), IDom(iDom) {}
 267     inline Node2 *addChild(Node *C) { Children.push_back(C); return C; }
 268
 269     void setIDom(Node2 *NewIDom);
 270   };
 271
 272 public:
 273   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 274   ~DominatorTreeBase() { reset(); }
 275
 276   virtual void releaseMemory() { reset(); }
 277
 278   /// getNode - return the (Post)DominatorTree node for the specified basic
 279   /// block.  This is the same as using operator[] on this class.
 280   ///
 281   inline Node *getNode(BasicBlock *BB) const {
 282     NodeMapType::const_iterator i = Nodes.find(BB);
 283     return (i != Nodes.end()) ? i->second : 0;
 284   }
 285
 286   inline Node *operator[](BasicBlock *BB) const {
 287     return getNode(BB);
 288   }
 289
 290   //===--------------------------------------------------------------------===//  // API to update (Post)DominatorTree information based on modifications to
 291   // the CFG...
 292
 293   /// createNewNode - Add a new node to the dominator tree information.  This
 294   /// creates a new node as a child of IDomNode, linking it into the children
 295   /// list of the immediate dominator.
 296   ///
 297   Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
 298     assert(getNode(BB) == 0 && "Block already in dominator tree!");
 299     Node *New = Nodes[BB] = new Node(BB, IDomNode);
 300     if (IDomNode) IDomNode->addChild(New);
 301     return New;
 302   }
 303
 304   /// changeImmediateDominator - This method is used to update the dominator
 305   /// tree information when a node's immediate dominator changes.
 306   ///
 307   void changeImmediateDominator(Node *Node, Node *NewIDom) {
 308     assert(Node && NewIDom && "Cannot change null node pointers!");
 309     Node->setIDom(NewIDom);
 310   }
 311
 312   /// print - Convert to human readable form
 313   virtual void print(std::ostream &OS) const;
 314 };
 315
 316
 317 //===-------------------------------------
 318 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 319 // compute a normal dominator tree.
 320 //
 321 struct DominatorTree : public DominatorTreeBase {
 322   DominatorTree() : DominatorTreeBase(false) {}
 323
 324   virtual bool runOnFunction(Function &F) {
 325     reset();     // Reset from the last time we were run...
 326     DominatorSet &DS = getAnalysis<DominatorSet>();
 327     Root = DS.getRoot();
 328     calculate(DS);
 329     return false;
 330   }
 331
 332   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 333     AU.setPreservesAll();
 334     AU.addRequired<DominatorSet>();
 335   }
 336 private:
 337   void calculate(const DominatorSet &DS);
 338 };
 339
 340
 341 //===----------------------------------------------------------------------===//
 342 //
 343 // DominanceFrontier - Calculate the dominance frontiers for a function.
 344 //
 345 class DominanceFrontierBase : public DominatorBase {
 346 public:
 347   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 348   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 349 protected:
 350   DomSetMapType Frontiers;
 351 public:
 352   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 353
 354   virtual void releaseMemory() { Frontiers.clear(); }
 355
 356   // Accessor interface:
 357   typedef DomSetMapType::const_iterator const_iterator;
 358   inline const_iterator begin() const { return Frontiers.begin(); }
 359   inline const_iterator end()   const { return Frontiers.end(); }
 360   inline const_iterator find(BasicBlock* B) const { return Frontiers.find(B); }
 361
 362   // print - Convert to human readable form
 363   virtual void print(std::ostream &OS) const;
 364 };
 365
 366
 367 //===-------------------------------------
 368 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 369 // compute a normal dominator tree.
 370 //
 371 struct DominanceFrontier : public DominanceFrontierBase {
 372   DominanceFrontier() : DominanceFrontierBase(false) {}
 373
 374   virtual bool runOnFunction(Function &) {
 375     Frontiers.clear();
 376     DominatorTree &DT = getAnalysis<DominatorTree>();
 377     Root = DT.getRoot();
 378     calculate(DT, DT[Root]);
 379     return false;
 380   }
 381
 382   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 383     AU.setPreservesAll();
 384     AU.addRequired<DominatorTree>();
 385   }
 386 private:
 387   const DomSetType &calculate(const DominatorTree &DT,
 388                               const DominatorTree::Node *Node);
 389 };
 390
 391 #endif