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