include/llvm/Analysis/Dominators.h

   1 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the following classes:
  11 //  1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
  12 //     and their immediate dominator.
  13 //  2. DominatorSet: Calculates the [reverse] dominator set for a function
  14 //  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
  15 //     structure.
  16 //  4. DominanceFrontier: Calculate and hold the dominance frontier for a
  17 //     function.
  18 //
  19 //  These data structures are listed in increasing order of complexity.  It
  20 //  takes longer to calculate the dominator frontier, for example, than the
  21 //  ImmediateDominator mapping.
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #ifndef LLVM_ANALYSIS_DOMINATORS_H
  26 #define LLVM_ANALYSIS_DOMINATORS_H
  27
  28 #include "llvm/Pass.h"
  29 #include <set>
  30
  31 namespace llvm {
  32
  33 class Instruction;
  34
  35 template <typename GraphType> struct GraphTraits;
  36
  37 //===----------------------------------------------------------------------===//
  38 //
  39 // DominatorBase - Base class that other, more interesting dominator analyses
  40 // inherit from.
  41 //
  42 class DominatorBase : public FunctionPass {
  43 protected:
  44   std::vector<BasicBlock*> Roots;
  45   const bool IsPostDominators;
  46
  47   inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
  48 public:
  49   // Return the root blocks of the current CFG.  This may include multiple
  50   // blocks if we are computing post dominators.  For forward dominators, this
  51   // will always be a single block (the entry node).
  52   inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
  53
  54   // Returns true if analysis based of postdoms
  55   bool isPostDominator() const { return IsPostDominators; }
  56 };
  57
  58
  59 //===----------------------------------------------------------------------===//
  60 //
  61 // ImmediateDominators - Calculate the immediate dominator for each node in a
  62 // function.
  63 //
  64 class ImmediateDominatorsBase : public DominatorBase {
  65 protected:
  66   std::map<BasicBlock*, BasicBlock*> IDoms;
  67 public:
  68   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
  69
  70   virtual void releaseMemory() { IDoms.clear(); }
  71
  72   // Accessor interface:
  73   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
  74   typedef IDomMapType::const_iterator const_iterator;
  75   inline const_iterator begin() const { return IDoms.begin(); }
  76   inline const_iterator end()   const { return IDoms.end(); }
  77   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
  78
  79   // operator[] - Return the idom for the specified basic block.  The start
  80   // node returns null, because it does not have an immediate dominator.
  81   //
  82   inline BasicBlock *operator[](BasicBlock *BB) const {
  83     return get(BB);
  84   }
  85
  86   // get() - Synonym for operator[].
  87   inline BasicBlock *get(BasicBlock *BB) const {
  88     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
  89     return I != IDoms.end() ? I->second : 0;
  90   }
  91
  92   //===--------------------------------------------------------------------===//
  93   // API to update Immediate(Post)Dominators information based on modifications
  94   // to the CFG...
  95
  96   /// addNewBlock - Add a new block to the CFG, with the specified immediate
  97   /// dominator.
  98   ///
  99   void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
 100     assert(get(BB) == 0 && "BasicBlock already in idom info!");
 101     IDoms[BB] = IDom;
 102   }
 103
 104   /// setImmediateDominator - Update the immediate dominator information to
 105   /// change the current immediate dominator for the specified block to another
 106   /// block.  This method requires that BB already have an IDom, otherwise just
 107   /// use addNewBlock.
 108   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
 109     assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
 110     IDoms[BB] = NewIDom;
 111   }
 112
 113   // print - Convert to human readable form
 114   virtual void print(std::ostream &OS) const;
 115 };
 116
 117 //===-------------------------------------
 118 // ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase that
 119 // is used to compute a normal immediate dominator set.
 120 //
 121 struct ImmediateDominators : public ImmediateDominatorsBase {
 122   ImmediateDominators() : ImmediateDominatorsBase(false) {}
 123
 124   BasicBlock *getRoot() const {
 125     assert(Roots.size() == 1 && "Should always have entry node!");
 126     return Roots[0];
 127   }
 128
 129   virtual bool runOnFunction(Function &F);
 130
 131   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 132     AU.setPreservesAll();
 133   }
 134
 135 private:
 136   struct InfoRec {
 137     unsigned Semi;
 138     unsigned Size;
 139     BasicBlock *Label, *Parent, *Child, *Ancestor;
 140
 141     std::vector<BasicBlock*> Bucket;
 142
 143     InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
 144   };
 145
 146   // Vertex - Map the DFS number to the BasicBlock*
 147   std::vector<BasicBlock*> Vertex;
 148
 149   // Info - Collection of information used during the computation of idoms.
 150   std::map<BasicBlock*, InfoRec> Info;
 151
 152   unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
 153   void Compress(BasicBlock *V, InfoRec &VInfo);
 154   BasicBlock *Eval(BasicBlock *v);
 155   void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
 156 };
 157
 158
 159
 160 //===----------------------------------------------------------------------===//
 161 //
 162 // DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
 163 // function, that represents the blocks that dominate the block.  If the block
 164 // is unreachable in this function, the set will be empty.  This cannot happen
 165 // for reachable code, because every block dominates at least itself.
 166 //
 167 struct DominatorSetBase : public DominatorBase {
 168   typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
 169   // Map of dom sets
 170   typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
 171 protected:
 172   DomSetMapType Doms;
 173 public:
 174   DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
 175
 176   virtual void releaseMemory() { Doms.clear(); }
 177
 178   // Accessor interface:
 179   typedef DomSetMapType::const_iterator const_iterator;
 180   typedef DomSetMapType::iterator iterator;
 181   inline const_iterator begin() const { return Doms.begin(); }
 182   inline       iterator begin()       { return Doms.begin(); }
 183   inline const_iterator end()   const { return Doms.end(); }
 184   inline       iterator end()         { return Doms.end(); }
 185   inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
 186   inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
 187
 188
 189   /// getDominators - Return the set of basic blocks that dominate the specified
 190   /// block.
 191   ///
 192   inline const DomSetType &getDominators(BasicBlock *BB) const {
 193     const_iterator I = find(BB);
 194     assert(I != end() && "BB not in function!");
 195     return I->second;
 196   }
 197
 198   /// isReachable - Return true if the specified basicblock is reachable.  If
 199   /// the block is reachable, we have dominator set information for it.
 200   bool isReachable(BasicBlock *BB) const {
 201     return !getDominators(BB).empty();
 202   }
 203
 204   /// dominates - Return true if A dominates B.
 205   ///
 206   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
 207     return getDominators(B).count(A) != 0;
 208   }
 209
 210   /// properlyDominates - Return true if A dominates B and A != B.
 211   ///
 212   bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
 213     return dominates(A, B) && A != B;
 214   }
 215
 216   /// print - Convert to human readable form
 217   virtual void print(std::ostream &OS) const;
 218
 219   /// dominates - Return true if A dominates B.  This performs the special
 220   /// checks necessary if A and B are in the same basic block.
 221   ///
 222   bool dominates(Instruction *A, Instruction *B) const;
 223
 224   //===--------------------------------------------------------------------===//
 225   // API to update (Post)DominatorSet information based on modifications to
 226   // the CFG...
 227
 228   /// addBasicBlock - Call to update the dominator set with information about a
 229   /// new block that was inserted into the function.
 230   void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
 231     assert(find(BB) == end() && "Block already in DominatorSet!");
 232     Doms.insert(std::make_pair(BB, Dominators));
 233   }
 234
 235   // addDominator - If a new block is inserted into the CFG, then method may be
 236   // called to notify the blocks it dominates that it is in their set.
 237   //
 238   void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
 239     iterator I = find(BB);
 240     assert(I != end() && "BB is not in DominatorSet!");
 241     I->second.insert(NewDominator);
 242   }
 243 };
 244
 245
 246 //===-------------------------------------
 247 // DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
 248 // compute a normal dominator set.
 249 //
 250 struct DominatorSet : public DominatorSetBase {
 251   DominatorSet() : DominatorSetBase(false) {}
 252
 253   virtual bool runOnFunction(Function &F);
 254
 255   BasicBlock *getRoot() const {
 256     assert(Roots.size() == 1 && "Should always have entry node!");
 257     return Roots[0];
 258   }
 259
 260   // getAnalysisUsage - This simply provides a dominator set
 261   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 262     AU.addRequired<ImmediateDominators>();
 263     AU.setPreservesAll();
 264   }
 265 };
 266
 267
 268 //===----------------------------------------------------------------------===//
 269 //
 270 // DominatorTree - Calculate the immediate dominator tree for a function.
 271 //
 272 struct DominatorTreeBase : public DominatorBase {
 273   class Node;
 274 protected:
 275   std::map<BasicBlock*, Node*> Nodes;
 276   void reset();
 277   typedef std::map<BasicBlock*, Node*> NodeMapType;
 278
 279   Node *RootNode;
 280 public:
 281   class Node {
 282     friend class DominatorTree;
 283     friend class PostDominatorTree;
 284     friend class DominatorTreeBase;
 285     BasicBlock *TheBB;
 286     Node *IDom;
 287     std::vector<Node*> Children;
 288   public:
 289     typedef std::vector<Node*>::iterator iterator;
 290     typedef std::vector<Node*>::const_iterator const_iterator;
 291
 292     iterator begin()             { return Children.begin(); }
 293     iterator end()               { return Children.end(); }
 294     const_iterator begin() const { return Children.begin(); }
 295     const_iterator end()   const { return Children.end(); }
 296
 297     inline BasicBlock *getBlock() const { return TheBB; }
 298     inline Node *getIDom() const { return IDom; }
 299     inline const std::vector<Node*> &getChildren() const { return Children; }
 300
 301     // dominates - Returns true iff this dominates N.  Note that this is not a
 302     // constant time operation!
 303     inline bool dominates(const Node *N) const {
 304       const Node *IDom;
 305       while ((IDom = N->getIDom()) != 0 && IDom != this)
 306         N = IDom;   // Walk up the tree
 307       return IDom != 0;
 308     }
 309
 310   private:
 311     inline Node(BasicBlock *BB, Node *iDom)
 312       : TheBB(BB), IDom(iDom) {}
 313     inline Node *addChild(Node *C) { Children.push_back(C); return C; }
 314
 315     void setIDom(Node *NewIDom);
 316   };
 317
 318 public:
 319   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 320   ~DominatorTreeBase() { reset(); }
 321
 322   virtual void releaseMemory() { reset(); }
 323
 324   /// getNode - return the (Post)DominatorTree node for the specified basic
 325   /// block.  This is the same as using operator[] on this class.
 326   ///
 327   inline Node *getNode(BasicBlock *BB) const {
 328     NodeMapType::const_iterator i = Nodes.find(BB);
 329     return (i != Nodes.end()) ? i->second : 0;
 330   }
 331
 332   inline Node *operator[](BasicBlock *BB) const {
 333     return getNode(BB);
 334   }
 335
 336   // getRootNode - This returns the entry node for the CFG of the function.  If
 337   // this tree represents the post-dominance relations for a function, however,
 338   // this root may be a node with the block == NULL.  This is the case when
 339   // there are multiple exit nodes from a particular function.  Consumers of
 340   // post-dominance information must be capable of dealing with this
 341   // possibility.
 342   //
 343   Node *getRootNode() { return RootNode; }
 344   const Node *getRootNode() const { return RootNode; }
 345
 346   //===--------------------------------------------------------------------===//
 347   // API to update (Post)DominatorTree information based on modifications to
 348   // the CFG...
 349
 350   /// createNewNode - Add a new node to the dominator tree information.  This
 351   /// creates a new node as a child of IDomNode, linking it into the children
 352   /// list of the immediate dominator.
 353   ///
 354   Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
 355     assert(getNode(BB) == 0 && "Block already in dominator tree!");
 356     assert(IDomNode && "Not immediate dominator specified for block!");
 357     return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 358   }
 359
 360   /// changeImmediateDominator - This method is used to update the dominator
 361   /// tree information when a node's immediate dominator changes.
 362   ///
 363   void changeImmediateDominator(Node *Node, Node *NewIDom) {
 364     assert(Node && NewIDom && "Cannot change null node pointers!");
 365     Node->setIDom(NewIDom);
 366   }
 367
 368   /// print - Convert to human readable form
 369   virtual void print(std::ostream &OS) const;
 370 };
 371
 372
 373 //===-------------------------------------
 374 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 375 // compute a normal dominator tree.
 376 //
 377 struct DominatorTree : public DominatorTreeBase {
 378   DominatorTree() : DominatorTreeBase(false) {}
 379
 380   BasicBlock *getRoot() const {
 381     assert(Roots.size() == 1 && "Should always have entry node!");
 382     return Roots[0];
 383   }
 384
 385   virtual bool runOnFunction(Function &F) {
 386     reset();     // Reset from the last time we were run...
 387     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
 388     Roots = ID.getRoots();
 389     calculate(ID);
 390     return false;
 391   }
 392
 393   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 394     AU.setPreservesAll();
 395     AU.addRequired<ImmediateDominators>();
 396   }
 397 private:
 398   void calculate(const ImmediateDominators &ID);
 399   Node *getNodeForBlock(BasicBlock *BB);
 400 };
 401
 402 //===-------------------------------------
 403 // DominatorTree GraphTraits specialization so the DominatorTree can be
 404 // iterable by generic graph iterators.
 405
 406 template <> struct GraphTraits<DominatorTree::Node*> {
 407   typedef DominatorTree::Node NodeType;
 408   typedef NodeType::iterator  ChildIteratorType;
 409
 410   static NodeType *getEntryNode(NodeType *N) {
 411     return N;
 412   }
 413   static inline ChildIteratorType child_begin(NodeType* N) {
 414     return N->begin();
 415   }
 416   static inline ChildIteratorType child_end(NodeType* N) {
 417     return N->end();
 418   }
 419 };
 420
 421 template <> struct GraphTraits<DominatorTree*>
 422   : public GraphTraits<DominatorTree::Node*> {
 423   static NodeType *getEntryNode(DominatorTree *DT) {
 424     return DT->getRootNode();
 425   }
 426 };
 427
 428 //===----------------------------------------------------------------------===//
 429 //
 430 // DominanceFrontier - Calculate the dominance frontiers for a function.
 431 //
 432 struct DominanceFrontierBase : public DominatorBase {
 433   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 434   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 435 protected:
 436   DomSetMapType Frontiers;
 437 public:
 438   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 439
 440   virtual void releaseMemory() { Frontiers.clear(); }
 441
 442   // Accessor interface:
 443   typedef DomSetMapType::iterator iterator;
 444   typedef DomSetMapType::const_iterator const_iterator;
 445   iterator       begin()       { return Frontiers.begin(); }
 446   const_iterator begin() const { return Frontiers.begin(); }
 447   iterator       end()         { return Frontiers.end(); }
 448   const_iterator end()   const { return Frontiers.end(); }
 449   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
 450   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
 451
 452   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
 453     assert(find(BB) == end() && "Block already in DominanceFrontier!");
 454     Frontiers.insert(std::make_pair(BB, frontier));
 455   }
 456
 457   void addToFrontier(iterator I, BasicBlock *Node) {
 458     assert(I != end() && "BB is not in DominanceFrontier!");
 459     I->second.insert(Node);
 460   }
 461
 462   void removeFromFrontier(iterator I, BasicBlock *Node) {
 463     assert(I != end() && "BB is not in DominanceFrontier!");
 464     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
 465     I->second.erase(Node);
 466   }
 467
 468   // print - Convert to human readable form
 469   virtual void print(std::ostream &OS) const;
 470 };
 471
 472
 473 //===-------------------------------------
 474 // DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 475 // compute a normal dominator tree.
 476 //
 477 struct DominanceFrontier : public DominanceFrontierBase {
 478   DominanceFrontier() : DominanceFrontierBase(false) {}
 479
 480   BasicBlock *getRoot() const {
 481     assert(Roots.size() == 1 && "Should always have entry node!");
 482     return Roots[0];
 483   }
 484
 485   virtual bool runOnFunction(Function &) {
 486     Frontiers.clear();
 487     DominatorTree &DT = getAnalysis<DominatorTree>();
 488     Roots = DT.getRoots();
 489     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
 490     calculate(DT, DT[Roots[0]]);
 491     return false;
 492   }
 493
 494   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 495     AU.setPreservesAll();
 496     AU.addRequired<DominatorTree>();
 497   }
 498 private:
 499   const DomSetType &calculate(const DominatorTree &DT,
 500                               const DominatorTree::Node *Node);
 501 };
 502
 503 } // End llvm namespace
 504
 505 #endif