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