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