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. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
  12 //     and their immediate dominator.
  13 //  2. DominatorSet: Calculates the [reverse] dominator set for a function
  14 //  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
  15 //     structure.
  16 //  4. ETForest: Efficient data structure for dominance comparisons and
  17 //     nearest-common-ancestor queries.
  18 //  5. DominanceFrontier: Calculate and hold the dominance frontier for a
  19 //     function.
  20 //
  21 //  These data structures are listed in increasing order of complexity.  It
  22 //  takes longer to calculate the dominator frontier, for example, than the
  23 //  ImmediateDominator mapping.
  24 //
  25 //===----------------------------------------------------------------------===//
  26
  27 #ifndef LLVM_ANALYSIS_DOMINATORS_H
  28 #define LLVM_ANALYSIS_DOMINATORS_H
  29
  30 #include "llvm/Analysis/ET-Forest.h"
  31 #include "llvm/Pass.h"
  32 #include <set>
  33
  34 namespace llvm {
  35
  36 class Instruction;
  37
  38 template <typename GraphType> struct GraphTraits;
  39
  40 //===----------------------------------------------------------------------===//
  41 /// DominatorBase - Base class that other, more interesting dominator analyses
  42 /// inherit from.
  43 ///
  44 class DominatorBase : public FunctionPass {
  45 protected:
  46   std::vector<BasicBlock*> Roots;
  47   const bool IsPostDominators;
  48
  49   inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {}
  50 public:
  51   /// getRoots -  Return the root blocks of the current CFG.  This may include
  52   /// multiple blocks if we are computing post dominators.  For forward
  53   /// dominators, this will always be a single block (the entry node).
  54   ///
  55   inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
  56
  57   /// isPostDominator - Returns true if analysis based of postdoms
  58   ///
  59   bool isPostDominator() const { return IsPostDominators; }
  60 };
  61
  62
  63 //===----------------------------------------------------------------------===//
  64 /// ImmediateDominators - Calculate the immediate dominator for each node in a
  65 /// function.
  66 ///
  67 class ImmediateDominatorsBase : public DominatorBase {
  68 protected:
  69   struct InfoRec {
  70     unsigned Semi;
  71     unsigned Size;
  72     BasicBlock *Label, *Parent, *Child, *Ancestor;
  73
  74     std::vector<BasicBlock*> Bucket;
  75
  76     InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
  77   };
  78
  79   std::map<BasicBlock*, BasicBlock*> IDoms;
  80
  81   // Vertex - Map the DFS number to the BasicBlock*
  82   std::vector<BasicBlock*> Vertex;
  83
  84   // Info - Collection of information used during the computation of idoms.
  85   std::map<BasicBlock*, InfoRec> Info;
  86 public:
  87   ImmediateDominatorsBase(bool isPostDom) : DominatorBase(isPostDom) {}
  88
  89   virtual void releaseMemory() { IDoms.clear(); }
  90
  91   // Accessor interface:
  92   typedef std::map<BasicBlock*, BasicBlock*> IDomMapType;
  93   typedef IDomMapType::const_iterator const_iterator;
  94   inline const_iterator begin() const { return IDoms.begin(); }
  95   inline const_iterator end()   const { return IDoms.end(); }
  96   inline const_iterator find(BasicBlock* B) const { return IDoms.find(B);}
  97
  98   /// operator[] - Return the idom for the specified basic block.  The start
  99   /// node returns null, because it does not have an immediate dominator.
 100   ///
 101   inline BasicBlock *operator[](BasicBlock *BB) const {
 102     return get(BB);
 103   }
 104
 105   /// dominates - Return true if A dominates B.
 106   ///
 107   bool dominates(BasicBlock *A, BasicBlock *B) const;
 108
 109   /// properlyDominates - Return true if A dominates B and A != B.
 110   ///
 111   bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
 112     return A != B || properlyDominates(A, B);
 113   }
 114
 115   /// get() - Synonym for operator[].
 116   ///
 117   inline BasicBlock *get(BasicBlock *BB) const {
 118     std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
 119     return I != IDoms.end() ? I->second : 0;
 120   }
 121
 122   //===--------------------------------------------------------------------===//
 123   // API to update Immediate(Post)Dominators information based on modifications
 124   // to the CFG...
 125
 126   /// addNewBlock - Add a new block to the CFG, with the specified immediate
 127   /// dominator.
 128   ///
 129   void addNewBlock(BasicBlock *BB, BasicBlock *IDom) {
 130     assert(get(BB) == 0 && "BasicBlock already in idom info!");
 131     IDoms[BB] = IDom;
 132   }
 133
 134   /// setImmediateDominator - Update the immediate dominator information to
 135   /// change the current immediate dominator for the specified block to another
 136   /// block.  This method requires that BB already have an IDom, otherwise just
 137   /// use addNewBlock.
 138   ///
 139   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom) {
 140     assert(IDoms.find(BB) != IDoms.end() && "BB doesn't have idom yet!");
 141     IDoms[BB] = NewIDom;
 142   }
 143
 144   /// print - Convert to human readable form
 145   ///
 146   virtual void print(std::ostream &OS, const Module* = 0) const;
 147   void print(std::ostream *OS, const Module* M = 0) const {
 148     if (OS) print(*OS, M);
 149   }
 150 };
 151
 152 //===-------------------------------------
 153 /// ImmediateDominators Class - Concrete subclass of ImmediateDominatorsBase
 154 /// that is used to compute a normal immediate dominator set.
 155 ///
 156 class ImmediateDominators : public ImmediateDominatorsBase {
 157 public:
 158   ImmediateDominators() : ImmediateDominatorsBase(false) {}
 159
 160   BasicBlock *getRoot() const {
 161     assert(Roots.size() == 1 && "Should always have entry node!");
 162     return Roots[0];
 163   }
 164
 165   virtual bool runOnFunction(Function &F);
 166
 167   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 168     AU.setPreservesAll();
 169   }
 170
 171 private:
 172   unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
 173   void Compress(BasicBlock *V, InfoRec &VInfo);
 174   BasicBlock *Eval(BasicBlock *v);
 175   void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
 176 };
 177
 178
 179
 180 //===----------------------------------------------------------------------===//
 181 /// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
 182 /// function, that represents the blocks that dominate the block.  If the block
 183 /// is unreachable in this function, the set will be empty.  This cannot happen
 184 /// for reachable code, because every block dominates at least itself.
 185 ///
 186 class DominatorSetBase : public DominatorBase {
 187 public:
 188   typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
 189   // Map of dom sets
 190   typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
 191 protected:
 192   DomSetMapType Doms;
 193 public:
 194   DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
 195
 196   virtual void releaseMemory() { Doms.clear(); }
 197
 198   // Accessor interface:
 199   typedef DomSetMapType::const_iterator const_iterator;
 200   typedef DomSetMapType::iterator iterator;
 201   inline const_iterator begin() const { return Doms.begin(); }
 202   inline       iterator begin()       { return Doms.begin(); }
 203   inline const_iterator end()   const { return Doms.end(); }
 204   inline       iterator end()         { return Doms.end(); }
 205   inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
 206   inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
 207
 208
 209   /// getDominators - Return the set of basic blocks that dominate the specified
 210   /// block.
 211   ///
 212   inline const DomSetType &getDominators(BasicBlock *BB) const {
 213     const_iterator I = find(BB);
 214     assert(I != end() && "BB not in function!");
 215     return I->second;
 216   }
 217
 218   /// isReachable - Return true if the specified basicblock is reachable.  If
 219   /// the block is reachable, we have dominator set information for it.
 220   ///
 221   bool isReachable(BasicBlock *BB) const {
 222     return !getDominators(BB).empty();
 223   }
 224
 225   /// dominates - Return true if A dominates B.
 226   ///
 227   inline bool dominates(BasicBlock *A, BasicBlock *B) const {
 228     return getDominators(B).count(A) != 0;
 229   }
 230
 231   /// properlyDominates - Return true if A dominates B and A != B.
 232   ///
 233   bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
 234     return dominates(A, B) && A != B;
 235   }
 236
 237   /// print - Convert to human readable form
 238   ///
 239   virtual void print(std::ostream &OS, const Module* = 0) const;
 240   void print(std::ostream *OS, const Module* M = 0) const {
 241     if (OS) print(*OS, M);
 242   }
 243
 244   /// dominates - Return true if A dominates B.  This performs the special
 245   /// checks necessary if A and B are in the same basic block.
 246   ///
 247   bool dominates(Instruction *A, Instruction *B) const;
 248
 249   //===--------------------------------------------------------------------===//
 250   // API to update (Post)DominatorSet information based on modifications to
 251   // the CFG...
 252
 253   /// addBasicBlock - Call to update the dominator set with information about a
 254   /// new block that was inserted into the function.
 255   ///
 256   void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
 257     assert(find(BB) == end() && "Block already in DominatorSet!");
 258     Doms.insert(std::make_pair(BB, Dominators));
 259   }
 260
 261   /// addDominator - If a new block is inserted into the CFG, then method may be
 262   /// called to notify the blocks it dominates that it is in their set.
 263   ///
 264   void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
 265     iterator I = find(BB);
 266     assert(I != end() && "BB is not in DominatorSet!");
 267     I->second.insert(NewDominator);
 268   }
 269 };
 270
 271
 272 //===-------------------------------------
 273 /// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
 274 /// compute a normal dominator set.
 275 ///
 276 class DominatorSet : public DominatorSetBase {
 277 public:
 278   DominatorSet() : DominatorSetBase(false) {}
 279
 280   virtual bool runOnFunction(Function &F);
 281
 282   BasicBlock *getRoot() const {
 283     assert(Roots.size() == 1 && "Should always have entry node!");
 284     return Roots[0];
 285   }
 286
 287   /// getAnalysisUsage - This simply provides a dominator set
 288   ///
 289   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 290     AU.addRequired<ImmediateDominators>();
 291     AU.setPreservesAll();
 292   }
 293
 294   // stub - dummy function, just ignore it
 295   static int stub;
 296 };
 297
 298
 299 //===----------------------------------------------------------------------===//
 300 /// DominatorTree - Calculate the immediate dominator tree for a function.
 301 ///
 302 class DominatorTreeBase : public DominatorBase {
 303 public:
 304   class Node;
 305 protected:
 306   std::map<BasicBlock*, Node*> Nodes;
 307   void reset();
 308   typedef std::map<BasicBlock*, Node*> NodeMapType;
 309
 310   Node *RootNode;
 311 public:
 312   class Node {
 313     friend class DominatorTree;
 314     friend struct PostDominatorTree;
 315     friend class DominatorTreeBase;
 316     BasicBlock *TheBB;
 317     Node *IDom;
 318     std::vector<Node*> Children;
 319   public:
 320     typedef std::vector<Node*>::iterator iterator;
 321     typedef std::vector<Node*>::const_iterator const_iterator;
 322
 323     iterator begin()             { return Children.begin(); }
 324     iterator end()               { return Children.end(); }
 325     const_iterator begin() const { return Children.begin(); }
 326     const_iterator end()   const { return Children.end(); }
 327
 328     inline BasicBlock *getBlock() const { return TheBB; }
 329     inline Node *getIDom() const { return IDom; }
 330     inline const std::vector<Node*> &getChildren() const { return Children; }
 331
 332     /// properlyDominates - Returns true iff this dominates N and this != N.
 333     /// Note that this is not a constant time operation!
 334     ///
 335     bool properlyDominates(const Node *N) const {
 336       const Node *IDom;
 337       if (this == 0 || N == 0) return false;
 338       while ((IDom = N->getIDom()) != 0 && IDom != this)
 339         N = IDom;   // Walk up the tree
 340       return IDom != 0;
 341     }
 342
 343     /// dominates - Returns true iff this dominates N.  Note that this is not a
 344     /// constant time operation!
 345     ///
 346     inline bool dominates(const Node *N) const {
 347       if (N == this) return true;  // A node trivially dominates itself.
 348       return properlyDominates(N);
 349     }
 350
 351   private:
 352     inline Node(BasicBlock *BB, Node *iDom) : TheBB(BB), IDom(iDom) {}
 353     inline Node *addChild(Node *C) { Children.push_back(C); return C; }
 354
 355     void setIDom(Node *NewIDom);
 356   };
 357
 358 public:
 359   DominatorTreeBase(bool isPostDom) : DominatorBase(isPostDom) {}
 360   ~DominatorTreeBase() { reset(); }
 361
 362   virtual void releaseMemory() { reset(); }
 363
 364   /// getNode - return the (Post)DominatorTree node for the specified basic
 365   /// block.  This is the same as using operator[] on this class.
 366   ///
 367   inline Node *getNode(BasicBlock *BB) const {
 368     NodeMapType::const_iterator i = Nodes.find(BB);
 369     return (i != Nodes.end()) ? i->second : 0;
 370   }
 371
 372   inline Node *operator[](BasicBlock *BB) const {
 373     return getNode(BB);
 374   }
 375
 376   /// getRootNode - This returns the entry node for the CFG of the function.  If
 377   /// this tree represents the post-dominance relations for a function, however,
 378   /// this root may be a node with the block == NULL.  This is the case when
 379   /// there are multiple exit nodes from a particular function.  Consumers of
 380   /// post-dominance information must be capable of dealing with this
 381   /// possibility.
 382   ///
 383   Node *getRootNode() { return RootNode; }
 384   const Node *getRootNode() const { return RootNode; }
 385
 386   //===--------------------------------------------------------------------===//
 387   // API to update (Post)DominatorTree information based on modifications to
 388   // the CFG...
 389
 390   /// createNewNode - Add a new node to the dominator tree information.  This
 391   /// creates a new node as a child of IDomNode, linking it into the children
 392   /// list of the immediate dominator.
 393   ///
 394   Node *createNewNode(BasicBlock *BB, Node *IDomNode) {
 395     assert(getNode(BB) == 0 && "Block already in dominator tree!");
 396     assert(IDomNode && "Not immediate dominator specified for block!");
 397     return Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
 398   }
 399
 400   /// changeImmediateDominator - This method is used to update the dominator
 401   /// tree information when a node's immediate dominator changes.
 402   ///
 403   void changeImmediateDominator(Node *N, Node *NewIDom) {
 404     assert(N && NewIDom && "Cannot change null node pointers!");
 405     N->setIDom(NewIDom);
 406   }
 407
 408   /// removeNode - Removes a node from the dominator tree.  Block must not
 409   /// dominate any other blocks.  Invalidates any node pointing to removed
 410   /// block.
 411   void removeNode(BasicBlock *BB) {
 412     assert(getNode(BB) && "Removing node that isn't in dominator tree.");
 413     Nodes.erase(BB);
 414   }
 415
 416   /// print - Convert to human readable form
 417   ///
 418   virtual void print(std::ostream &OS, const Module* = 0) const;
 419   void print(std::ostream *OS, const Module* M = 0) const {
 420     if (OS) print(*OS, M);
 421   }
 422 };
 423
 424 //===-------------------------------------
 425 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 426 /// compute a normal dominator tree.
 427 ///
 428 class DominatorTree : public DominatorTreeBase {
 429 public:
 430   DominatorTree() : DominatorTreeBase(false) {}
 431
 432   BasicBlock *getRoot() const {
 433     assert(Roots.size() == 1 && "Should always have entry node!");
 434     return Roots[0];
 435   }
 436
 437   virtual bool runOnFunction(Function &F) {
 438     reset();     // Reset from the last time we were run...
 439     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
 440     Roots = ID.getRoots();
 441     calculate(ID);
 442     return false;
 443   }
 444
 445   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 446     AU.setPreservesAll();
 447     AU.addRequired<ImmediateDominators>();
 448   }
 449 private:
 450   void calculate(const ImmediateDominators &ID);
 451   Node *getNodeForBlock(BasicBlock *BB);
 452 };
 453
 454 //===-------------------------------------
 455 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 456 /// iterable by generic graph iterators.
 457 ///
 458 template <> struct GraphTraits<DominatorTree::Node*> {
 459   typedef DominatorTree::Node NodeType;
 460   typedef NodeType::iterator  ChildIteratorType;
 461
 462   static NodeType *getEntryNode(NodeType *N) {
 463     return N;
 464   }
 465   static inline ChildIteratorType child_begin(NodeType* N) {
 466     return N->begin();
 467   }
 468   static inline ChildIteratorType child_end(NodeType* N) {
 469     return N->end();
 470   }
 471 };
 472
 473 template <> struct GraphTraits<DominatorTree*>
 474   : public GraphTraits<DominatorTree::Node*> {
 475   static NodeType *getEntryNode(DominatorTree *DT) {
 476     return DT->getRootNode();
 477   }
 478 };
 479
 480
 481 //===-------------------------------------
 482 /// ET-Forest Class - Class used to construct forwards and backwards
 483 /// ET-Forests
 484 ///
 485 class ETForestBase : public DominatorBase {
 486 public:
 487   ETForestBase(bool isPostDom) : DominatorBase(isPostDom), Nodes(),
 488                                  DFSInfoValid(false), SlowQueries(0) {}
 489
 490   virtual void releaseMemory() { reset(); }
 491
 492   typedef std::map<BasicBlock*, ETNode*> ETMapType;
 493
 494   void updateDFSNumbers();
 495
 496   /// dominates - Return true if A dominates B.
 497   ///
 498   inline bool dominates(BasicBlock *A, BasicBlock *B) {
 499     if (A == B)
 500       return true;
 501
 502     ETNode *NodeA = getNode(A);
 503     ETNode *NodeB = getNode(B);
 504
 505     if (DFSInfoValid)
 506       return NodeB->DominatedBy(NodeA);
 507     else {
 508       // If we end up with too many slow queries, just update the
 509       // DFS numbers on the theory that we are going to keep querying.
 510       SlowQueries++;
 511       if (SlowQueries > 32) {
 512         updateDFSNumbers();
 513         return NodeB->DominatedBy(NodeA);
 514       }
 515       return NodeB->DominatedBySlow(NodeA);
 516     }
 517   }
 518
 519   // dominates - Return true if A dominates B. THis performs the
 520   // special checks necessary if A and B are in the same basic block.
 521   bool dominates(Instruction *A, Instruction *B);
 522
 523   /// properlyDominates - Return true if A dominates B and A != B.
 524   ///
 525   bool properlyDominates(BasicBlock *A, BasicBlock *B) {
 526     return dominates(A, B) && A != B;
 527   }
 528
 529   /// Return the nearest common dominator of A and B.
 530   BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const  {
 531     ETNode *NodeA = getNode(A);
 532     ETNode *NodeB = getNode(B);
 533
 534     ETNode *Common = NodeA->NCA(NodeB);
 535     if (!Common)
 536       return NULL;
 537     return Common->getData<BasicBlock>();
 538   }
 539
 540   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 541     AU.setPreservesAll();
 542     AU.addRequired<ImmediateDominators>();
 543   }
 544   //===--------------------------------------------------------------------===//
 545   // API to update Forest information based on modifications
 546   // to the CFG...
 547
 548   /// addNewBlock - Add a new block to the CFG, with the specified immediate
 549   /// dominator.
 550   ///
 551   void addNewBlock(BasicBlock *BB, BasicBlock *IDom);
 552
 553   /// setImmediateDominator - Update the immediate dominator information to
 554   /// change the current immediate dominator for the specified block
 555   /// to another block.  This method requires that BB for NewIDom
 556   /// already have an ETNode, otherwise just use addNewBlock.
 557   ///
 558   void setImmediateDominator(BasicBlock *BB, BasicBlock *NewIDom);
 559   /// print - Convert to human readable form
 560   ///
 561   virtual void print(std::ostream &OS, const Module* = 0) const;
 562   void print(std::ostream *OS, const Module* M = 0) const {
 563     if (OS) print(*OS, M);
 564   }
 565 protected:
 566   /// getNode - return the (Post)DominatorTree node for the specified basic
 567   /// block.  This is the same as using operator[] on this class.
 568   ///
 569   inline ETNode *getNode(BasicBlock *BB) const {
 570     ETMapType::const_iterator i = Nodes.find(BB);
 571     return (i != Nodes.end()) ? i->second : 0;
 572   }
 573
 574   inline ETNode *operator[](BasicBlock *BB) const {
 575     return getNode(BB);
 576   }
 577
 578   void reset();
 579   ETMapType Nodes;
 580   bool DFSInfoValid;
 581   unsigned int SlowQueries;
 582
 583 };
 584
 585 //==-------------------------------------
 586 /// ETForest Class - Concrete subclass of ETForestBase that is used to
 587 /// compute a forwards ET-Forest.
 588
 589 class ETForest : public ETForestBase {
 590 public:
 591   ETForest() : ETForestBase(false) {}
 592
 593   BasicBlock *getRoot() const {
 594     assert(Roots.size() == 1 && "Should always have entry node!");
 595     return Roots[0];
 596   }
 597
 598   virtual bool runOnFunction(Function &F) {
 599     reset();     // Reset from the last time we were run...
 600     ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
 601     Roots = ID.getRoots();
 602     calculate(ID);
 603     return false;
 604   }
 605
 606   void calculate(const ImmediateDominators &ID);
 607   ETNode *getNodeForBlock(BasicBlock *BB);
 608 };
 609
 610 //===----------------------------------------------------------------------===//
 611 /// DominanceFrontierBase - Common base class for computing forward and inverse
 612 /// dominance frontiers for a function.
 613 ///
 614 class DominanceFrontierBase : public DominatorBase {
 615 public:
 616   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 617   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 618 protected:
 619   DomSetMapType Frontiers;
 620 public:
 621   DominanceFrontierBase(bool isPostDom) : DominatorBase(isPostDom) {}
 622
 623   virtual void releaseMemory() { Frontiers.clear(); }
 624
 625   // Accessor interface:
 626   typedef DomSetMapType::iterator iterator;
 627   typedef DomSetMapType::const_iterator const_iterator;
 628   iterator       begin()       { return Frontiers.begin(); }
 629   const_iterator begin() const { return Frontiers.begin(); }
 630   iterator       end()         { return Frontiers.end(); }
 631   const_iterator end()   const { return Frontiers.end(); }
 632   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
 633   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
 634
 635   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
 636     assert(find(BB) == end() && "Block already in DominanceFrontier!");
 637     Frontiers.insert(std::make_pair(BB, frontier));
 638   }
 639
 640   void addToFrontier(iterator I, BasicBlock *Node) {
 641     assert(I != end() && "BB is not in DominanceFrontier!");
 642     I->second.insert(Node);
 643   }
 644
 645   void removeFromFrontier(iterator I, BasicBlock *Node) {
 646     assert(I != end() && "BB is not in DominanceFrontier!");
 647     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
 648     I->second.erase(Node);
 649   }
 650
 651   /// print - Convert to human readable form
 652   ///
 653   virtual void print(std::ostream &OS, const Module* = 0) const;
 654   void print(std::ostream *OS, const Module* M = 0) const {
 655     if (OS) print(*OS, M);
 656   }
 657 };
 658
 659
 660 //===-------------------------------------
 661 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
 662 /// used to compute a forward dominator frontiers.
 663 ///
 664 class DominanceFrontier : public DominanceFrontierBase {
 665 public:
 666   DominanceFrontier() : DominanceFrontierBase(false) {}
 667
 668   BasicBlock *getRoot() const {
 669     assert(Roots.size() == 1 && "Should always have entry node!");
 670     return Roots[0];
 671   }
 672
 673   virtual bool runOnFunction(Function &) {
 674     Frontiers.clear();
 675     DominatorTree &DT = getAnalysis<DominatorTree>();
 676     Roots = DT.getRoots();
 677     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
 678     calculate(DT, DT[Roots[0]]);
 679     return false;
 680   }
 681
 682   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 683     AU.setPreservesAll();
 684     AU.addRequired<DominatorTree>();
 685   }
 686 private:
 687   const DomSetType &calculate(const DominatorTree &DT,
 688                               const DominatorTree::Node *Node);
 689 };
 690
 691
 692 } // End llvm namespace
 693
 694 // Make sure that any clients of this file link in Dominators.cpp
 695 FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet)
 696
 697 #endif