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