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