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