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. DominatorTree: Represent dominators as an explicit tree structure.
  12 //  2. DominanceFrontier: Calculate and hold the dominance frontier for a
  13 //     function.
  14 //
  15 //  These data structures are listed in increasing order of complexity.  It
  16 //  takes longer to calculate the dominator frontier, for example, than the
  17 //  DominatorTree mapping.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_ANALYSIS_DOMINATORS_H
  22 #define LLVM_ANALYSIS_DOMINATORS_H
  23
  24 #include "llvm/Pass.h"
  25 #include "llvm/Instruction.h"
  26 #include "llvm/Instructions.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/ADT/SmallVector.h"
  30 #include "llvm/Assembly/Writer.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include <algorithm>
  33 #include <set>
  34
  35 namespace llvm {
  36
  37 template <typename GraphType> struct GraphTraits;
  38
  39 //===----------------------------------------------------------------------===//
  40 /// DominatorBase - Base class that other, more interesting dominator analyses
  41 /// inherit from.
  42 ///
  43 template <class NodeT>
  44 class DominatorBase : public FunctionPass {
  45 protected:
  46   std::vector<NodeT*> Roots;
  47   const bool IsPostDominators;
  48   inline DominatorBase(intptr_t ID, bool isPostDom) :
  49     FunctionPass(ID), Roots(), IsPostDominators(isPostDom) {}
  50 public:
  51
  52   /// getRoots -  Return the root blocks of the current CFG.  This may include
  53   /// multiple blocks if we are computing post dominators.  For forward
  54   /// dominators, this will always be a single block (the entry node).
  55   ///
  56   inline const std::vector<NodeT*> &getRoots() const { return Roots; }
  57
  58   /// isPostDominator - Returns true if analysis based of postdoms
  59   ///
  60   bool isPostDominator() const { return IsPostDominators; }
  61 };
  62
  63
  64 //===----------------------------------------------------------------------===//
  65 // DomTreeNode - Dominator Tree Node
  66 template<class NodeT> class DominatorTreeBase;
  67 class PostDominatorTree;
  68 class MachineBasicBlock;
  69
  70 template <class NodeT>
  71 class DomTreeNodeBase {
  72   NodeT *TheBB;
  73   DomTreeNodeBase<NodeT> *IDom;
  74   std::vector<DomTreeNodeBase<NodeT> *> Children;
  75   int DFSNumIn, DFSNumOut;
  76
  77   template<class N> friend class DominatorTreeBase;
  78   friend class PostDominatorTree;
  79 public:
  80   typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
  81   typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
  82                    const_iterator;
  83
  84   iterator begin()             { return Children.begin(); }
  85   iterator end()               { return Children.end(); }
  86   const_iterator begin() const { return Children.begin(); }
  87   const_iterator end()   const { return Children.end(); }
  88
  89   NodeT *getBlock() const { return TheBB; }
  90   DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
  91   const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
  92     return Children;
  93   }
  94
  95   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
  96     : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
  97
  98   DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
  99     Children.push_back(C);
 100     return C;
 101   }
 102
 103   void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
 104     assert(IDom && "No immediate dominator?");
 105     if (IDom != NewIDom) {
 106       std::vector<DomTreeNodeBase<BasicBlock>*>::iterator I =
 107                   std::find(IDom->Children.begin(), IDom->Children.end(), this);
 108       assert(I != IDom->Children.end() &&
 109              "Not in immediate dominator children set!");
 110       // I am no longer your child...
 111       IDom->Children.erase(I);
 112
 113       // Switch to new dominator
 114       IDom = NewIDom;
 115       IDom->Children.push_back(this);
 116     }
 117   }
 118
 119   /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
 120   /// not call them.
 121   unsigned getDFSNumIn() const { return DFSNumIn; }
 122   unsigned getDFSNumOut() const { return DFSNumOut; }
 123 private:
 124   // Return true if this node is dominated by other. Use this only if DFS info
 125   // is valid.
 126   bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
 127     return this->DFSNumIn >= other->DFSNumIn &&
 128       this->DFSNumOut <= other->DFSNumOut;
 129   }
 130 };
 131
 132 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
 133
 134 template<class NodeT>
 135 static std::ostream &operator<<(std::ostream &o,
 136                                 const DomTreeNodeBase<NodeT> *Node) {
 137   if (Node->getBlock())
 138     WriteAsOperand(o, Node->getBlock(), false);
 139   else
 140     o << " <<exit node>>";
 141
 142   o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
 143
 144   return o << "\n";
 145 }
 146
 147 template<class NodeT>
 148 static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o,
 149                          unsigned Lev) {
 150   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
 151   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
 152        E = N->end(); I != E; ++I)
 153     PrintDomTree<NodeT>(*I, o, Lev+1);
 154 }
 155
 156 typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
 157 typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
 158
 159 //===----------------------------------------------------------------------===//
 160 /// DominatorTree - Calculate the immediate dominator tree for a function.
 161 ///
 162
 163 template<class N, class GraphT>
 164 void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
 165            typename GraphT::NodeType* NewBB);
 166
 167 template<class NodeT>
 168 class DominatorTreeBase : public DominatorBase<NodeT> {
 169 protected:
 170   typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
 171   DomTreeNodeMapType DomTreeNodes;
 172   DomTreeNodeBase<NodeT> *RootNode;
 173
 174   bool DFSInfoValid;
 175   unsigned int SlowQueries;
 176   // Information record used during immediate dominators computation.
 177   struct InfoRec {
 178     unsigned Semi;
 179     unsigned Size;
 180     NodeT *Label, *Parent, *Child, *Ancestor;
 181
 182     std::vector<NodeT*> Bucket;
 183
 184     InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0) {}
 185   };
 186
 187   DenseMap<NodeT*, NodeT*> IDoms;
 188
 189   // Vertex - Map the DFS number to the BasicBlock*
 190   std::vector<NodeT*> Vertex;
 191
 192   // Info - Collection of information used during the computation of idoms.
 193   DenseMap<NodeT*, InfoRec> Info;
 194
 195   void reset() {
 196     for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
 197            E = DomTreeNodes.end(); I != E; ++I)
 198       delete I->second;
 199     DomTreeNodes.clear();
 200     IDoms.clear();
 201     this->Roots.clear();
 202     Vertex.clear();
 203     RootNode = 0;
 204   }
 205
 206 public:
 207   DominatorTreeBase(intptr_t ID, bool isPostDom)
 208     : DominatorBase<NodeT>(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
 209   ~DominatorTreeBase() { reset(); }
 210
 211   virtual void releaseMemory() { reset(); }
 212
 213   /// getNode - return the (Post)DominatorTree node for the specified basic
 214   /// block.  This is the same as using operator[] on this class.
 215   ///
 216   inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
 217     typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
 218     return I != DomTreeNodes.end() ? I->second : 0;
 219   }
 220
 221   inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const {
 222     return getNode(BB);
 223   }
 224
 225   /// getRootNode - This returns the entry node for the CFG of the function.  If
 226   /// this tree represents the post-dominance relations for a function, however,
 227   /// this root may be a node with the block == NULL.  This is the case when
 228   /// there are multiple exit nodes from a particular function.  Consumers of
 229   /// post-dominance information must be capable of dealing with this
 230   /// possibility.
 231   ///
 232   DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
 233   const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
 234
 235   /// properlyDominates - Returns true iff this dominates N and this != N.
 236   /// Note that this is not a constant time operation!
 237   ///
 238   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
 239                          DomTreeNodeBase<NodeT> *B) const {
 240     if (A == 0 || B == 0) return false;
 241     return dominatedBySlowTreeWalk(A, B);
 242   }
 243
 244   inline bool properlyDominates(NodeT *A, NodeT *B) {
 245     return properlyDominates(getNode(A), getNode(B));
 246   }
 247
 248   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
 249                                const DomTreeNodeBase<NodeT> *B) const {
 250     const DomTreeNodeBase<NodeT> *IDom;
 251     if (A == 0 || B == 0) return false;
 252     while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
 253       B = IDom;   // Walk up the tree
 254     return IDom != 0;
 255   }
 256
 257
 258   /// isReachableFromEntry - Return true if A is dominated by the entry
 259   /// block of the function containing it.
 260   const bool isReachableFromEntry(NodeT* A) {
 261     assert (!this->isPostDominator()
 262             && "This is not implemented for post dominators");
 263     return dominates(&A->getParent()->getEntryBlock(), A);
 264   }
 265
 266   /// dominates - Returns true iff A dominates B.  Note that this is not a
 267   /// constant time operation!
 268   ///
 269   inline bool dominates(const DomTreeNodeBase<NodeT> *A,
 270                         DomTreeNodeBase<NodeT> *B) {
 271     if (B == A)
 272       return true;  // A node trivially dominates itself.
 273
 274     if (A == 0 || B == 0)
 275       return false;
 276
 277     if (DFSInfoValid)
 278       return B->DominatedBy(A);
 279
 280     // If we end up with too many slow queries, just update the
 281     // DFS numbers on the theory that we are going to keep querying.
 282     SlowQueries++;
 283     if (SlowQueries > 32) {
 284       updateDFSNumbers();
 285       return B->DominatedBy(A);
 286     }
 287
 288     return dominatedBySlowTreeWalk(A, B);
 289   }
 290
 291   inline bool dominates(NodeT *A, NodeT *B) {
 292     if (A == B)
 293       return true;
 294
 295     return dominates(getNode(A), getNode(B));
 296   }
 297
 298   /// findNearestCommonDominator - Find nearest common dominator basic block
 299   /// for basic block A and B. If there is no such block then return NULL.
 300   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
 301
 302     assert (!this->isPostDominator()
 303             && "This is not implemented for post dominators");
 304     assert (A->getParent() == B->getParent()
 305             && "Two blocks are not in same function");
 306
 307     // If either A or B is a entry block then it is nearest common dominator.
 308     NodeT &Entry  = A->getParent()->getEntryBlock();
 309     if (A == &Entry || B == &Entry)
 310       return &Entry;
 311
 312     // If B dominates A then B is nearest common dominator.
 313     if (dominates(B, A))
 314       return B;
 315
 316     // If A dominates B then A is nearest common dominator.
 317     if (dominates(A, B))
 318       return A;
 319
 320     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
 321     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
 322
 323     // Collect NodeA dominators set.
 324     SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
 325     NodeADoms.insert(NodeA);
 326     DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
 327     while (IDomA) {
 328       NodeADoms.insert(IDomA);
 329       IDomA = IDomA->getIDom();
 330     }
 331
 332     // Walk NodeB immediate dominators chain and find common dominator node.
 333     DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
 334     while(IDomB) {
 335       if (NodeADoms.count(IDomB) != 0)
 336         return IDomB->getBlock();
 337
 338       IDomB = IDomB->getIDom();
 339     }
 340
 341     return NULL;
 342   }
 343
 344   // dominates - Return true if A dominates B. This performs the
 345   // special checks necessary if A and B are in the same basic block.
 346   bool dominates(Instruction *A, Instruction *B) {
 347     NodeT *BBA = A->getParent(), *BBB = B->getParent();
 348     if (BBA != BBB) return this->dominates(BBA, BBB);
 349
 350     // It is not possible to determine dominance between two PHI nodes
 351     // based on their ordering.
 352     if (isa<PHINode>(A) && isa<PHINode>(B))
 353       return false;
 354
 355     // Loop through the basic block until we find A or B.
 356     typename NodeT::iterator I = BBA->begin();
 357     for (; &*I != A && &*I != B; ++I) /*empty*/;
 358
 359     if(!this->IsPostDominators) {
 360       // A dominates B if it is found first in the basic block.
 361       return &*I == A;
 362     } else {
 363       // A post-dominates B if B is found first in the basic block.
 364       return &*I == B;
 365     }
 366   }
 367
 368   //===--------------------------------------------------------------------===//
 369   // API to update (Post)DominatorTree information based on modifications to
 370   // the CFG...
 371
 372   /// addNewBlock - Add a new node to the dominator tree information.  This
 373   /// creates a new node as a child of DomBB dominator node,linking it into
 374   /// the children list of the immediate dominator.
 375   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
 376     assert(getNode(BB) == 0 && "Block already in dominator tree!");
 377     DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
 378     assert(IDomNode && "Not immediate dominator specified for block!");
 379     DFSInfoValid = false;
 380     return DomTreeNodes[BB] =
 381       IDomNode->addChild(new DomTreeNode(BB, IDomNode));
 382   }
 383
 384   /// changeImmediateDominator - This method is used to update the dominator
 385   /// tree information when a node's immediate dominator changes.
 386   ///
 387   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
 388                                 DomTreeNodeBase<NodeT> *NewIDom) {
 389     assert(N && NewIDom && "Cannot change null node pointers!");
 390     DFSInfoValid = false;
 391     N->setIDom(NewIDom);
 392   }
 393
 394   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
 395     changeImmediateDominator(getNode(BB), getNode(NewBB));
 396   }
 397
 398   /// eraseNode - Removes a node from  the dominator tree. Block must not
 399   /// domiante any other blocks. Removes node from its immediate dominator's
 400   /// children list. Deletes dominator node associated with basic block BB.
 401   void eraseNode(NodeT *BB) {
 402     DomTreeNodeBase<NodeT> *Node = getNode(BB);
 403     assert (Node && "Removing node that isn't in dominator tree.");
 404     assert (Node->getChildren().empty() && "Node is not a leaf node.");
 405
 406       // Remove node from immediate dominator's children list.
 407     DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
 408     if (IDom) {
 409       typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
 410         std::find(IDom->Children.begin(), IDom->Children.end(), Node);
 411       assert(I != IDom->Children.end() &&
 412              "Not in immediate dominator children set!");
 413       // I am no longer your child...
 414       IDom->Children.erase(I);
 415     }
 416
 417     DomTreeNodes.erase(BB);
 418     delete Node;
 419   }
 420
 421   /// removeNode - Removes a node from the dominator tree.  Block must not
 422   /// dominate any other blocks.  Invalidates any node pointing to removed
 423   /// block.
 424   void removeNode(NodeT *BB) {
 425     assert(getNode(BB) && "Removing node that isn't in dominator tree.");
 426     DomTreeNodes.erase(BB);
 427   }
 428
 429   /// print - Convert to human readable form
 430   ///
 431   virtual void print(std::ostream &o, const Module* ) const {
 432     o << "=============================--------------------------------\n";
 433     o << "Inorder Dominator Tree: ";
 434     if (this->DFSInfoValid)
 435       o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
 436     o << "\n";
 437
 438     PrintDomTree<NodeT>(getRootNode(), o, 1);
 439   }
 440
 441   void print(std::ostream *OS, const Module* M = 0) const {
 442     if (OS) print(*OS, M);
 443   }
 444
 445   virtual void dump() {
 446     print(llvm::cerr);
 447   }
 448
 449 protected:
 450   template<class GraphT>
 451   friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
 452                        typename GraphT::NodeType* VIn);
 453
 454   template<class GraphT>
 455   friend typename GraphT::NodeType* Eval(
 456                                DominatorTreeBase<typename GraphT::NodeType>& DT,
 457                                          typename GraphT::NodeType* V);
 458
 459   template<class GraphT>
 460   friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
 461                    typename GraphT::NodeType* V,
 462                    typename GraphT::NodeType* W,
 463          typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
 464
 465   template<class GraphT>
 466   friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
 467                           typename GraphT::NodeType* V,
 468                           unsigned N);
 469
 470   template<class N, class GraphT>
 471   friend void Calculate(DominatorTreeBase<typename GraphT::NodeType>& DT,
 472                         Function& F);
 473
 474   template<class N, class GraphT>
 475   friend void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
 476                     typename GraphT::NodeType* NewBB);
 477
 478 public:
 479   /// splitBlock - BB is split and now it has one successor. Update dominator
 480   /// tree to reflect this change.
 481   void splitBlock(NodeT* NewBB) {
 482     if (this->IsPostDominators)
 483       Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
 484     else
 485       Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB);
 486   }
 487
 488 protected:
 489   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
 490   /// dominator tree in dfs order.
 491   void updateDFSNumbers() {
 492     unsigned DFSNum = 0;
 493
 494     SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
 495                 typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
 496
 497     for (unsigned i = 0, e = this->Roots.size(); i != e; ++i) {
 498       DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]);
 499       WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
 500       ThisRoot->DFSNumIn = DFSNum++;
 501
 502       while (!WorkStack.empty()) {
 503         DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
 504         typename DomTreeNodeBase<NodeT>::iterator ChildIt =
 505                                                         WorkStack.back().second;
 506
 507         // If we visited all of the children of this node, "recurse" back up the
 508         // stack setting the DFOutNum.
 509         if (ChildIt == Node->end()) {
 510           Node->DFSNumOut = DFSNum++;
 511           WorkStack.pop_back();
 512         } else {
 513           // Otherwise, recursively visit this child.
 514           DomTreeNodeBase<NodeT> *Child = *ChildIt;
 515           ++WorkStack.back().second;
 516
 517           WorkStack.push_back(std::make_pair(Child, Child->begin()));
 518           Child->DFSNumIn = DFSNum++;
 519         }
 520       }
 521     }
 522
 523     SlowQueries = 0;
 524     DFSInfoValid = true;
 525   }
 526
 527   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
 528     if (DomTreeNodeBase<NodeT> *BBNode = this->DomTreeNodes[BB])
 529       return BBNode;
 530
 531     // Haven't calculated this node yet?  Get or calculate the node for the
 532     // immediate dominator.
 533     NodeT *IDom = getIDom(BB);
 534     DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
 535
 536     // Add a new tree node for this BasicBlock, and link it as a child of
 537     // IDomNode
 538     DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
 539     return this->DomTreeNodes[BB] = IDomNode->addChild(C);
 540   }
 541
 542   inline NodeT *getIDom(NodeT *BB) const {
 543     typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
 544     return I != IDoms.end() ? I->second : 0;
 545   }
 546 };
 547
 548 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
 549
 550 //===-------------------------------------
 551 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 552 /// compute a normal dominator tree.
 553 ///
 554 class DominatorTree : public DominatorTreeBase<BasicBlock> {
 555 public:
 556   static char ID; // Pass ID, replacement for typeid
 557   DominatorTree() : DominatorTreeBase<BasicBlock>(intptr_t(&ID), false) {}
 558
 559   BasicBlock *getRoot() const {
 560     assert(Roots.size() == 1 && "Should always have entry node!");
 561     return Roots[0];
 562   }
 563
 564   virtual bool runOnFunction(Function &F);
 565
 566   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 567     AU.setPreservesAll();
 568   }
 569 };
 570
 571 //===-------------------------------------
 572 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 573 /// iterable by generic graph iterators.
 574 ///
 575 template <> struct GraphTraits<DomTreeNode *> {
 576   typedef DomTreeNode NodeType;
 577   typedef NodeType::iterator  ChildIteratorType;
 578
 579   static NodeType *getEntryNode(NodeType *N) {
 580     return N;
 581   }
 582   static inline ChildIteratorType child_begin(NodeType* N) {
 583     return N->begin();
 584   }
 585   static inline ChildIteratorType child_end(NodeType* N) {
 586     return N->end();
 587   }
 588 };
 589
 590 template <> struct GraphTraits<DominatorTree*>
 591   : public GraphTraits<DomTreeNode *> {
 592   static NodeType *getEntryNode(DominatorTree *DT) {
 593     return DT->getRootNode();
 594   }
 595 };
 596
 597
 598 //===----------------------------------------------------------------------===//
 599 /// DominanceFrontierBase - Common base class for computing forward and inverse
 600 /// dominance frontiers for a function.
 601 ///
 602 class DominanceFrontierBase : public DominatorBase<BasicBlock> {
 603 public:
 604   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 605   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 606 protected:
 607   DomSetMapType Frontiers;
 608 public:
 609   DominanceFrontierBase(intptr_t ID, bool isPostDom)
 610     : DominatorBase<BasicBlock>(ID, isPostDom) {}
 611
 612   virtual void releaseMemory() { Frontiers.clear(); }
 613
 614   // Accessor interface:
 615   typedef DomSetMapType::iterator iterator;
 616   typedef DomSetMapType::const_iterator const_iterator;
 617   iterator       begin()       { return Frontiers.begin(); }
 618   const_iterator begin() const { return Frontiers.begin(); }
 619   iterator       end()         { return Frontiers.end(); }
 620   const_iterator end()   const { return Frontiers.end(); }
 621   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
 622   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
 623
 624   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
 625     assert(find(BB) == end() && "Block already in DominanceFrontier!");
 626     Frontiers.insert(std::make_pair(BB, frontier));
 627   }
 628
 629   /// removeBlock - Remove basic block BB's frontier.
 630   void removeBlock(BasicBlock *BB) {
 631     assert(find(BB) != end() && "Block is not in DominanceFrontier!");
 632     for (iterator I = begin(), E = end(); I != E; ++I)
 633       I->second.erase(BB);
 634     Frontiers.erase(BB);
 635   }
 636
 637   void addToFrontier(iterator I, BasicBlock *Node) {
 638     assert(I != end() && "BB is not in DominanceFrontier!");
 639     I->second.insert(Node);
 640   }
 641
 642   void removeFromFrontier(iterator I, BasicBlock *Node) {
 643     assert(I != end() && "BB is not in DominanceFrontier!");
 644     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
 645     I->second.erase(Node);
 646   }
 647
 648   /// print - Convert to human readable form
 649   ///
 650   virtual void print(std::ostream &OS, const Module* = 0) const;
 651   void print(std::ostream *OS, const Module* M = 0) const {
 652     if (OS) print(*OS, M);
 653   }
 654   virtual void dump();
 655 };
 656
 657
 658 //===-------------------------------------
 659 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
 660 /// used to compute a forward dominator frontiers.
 661 ///
 662 class DominanceFrontier : public DominanceFrontierBase {
 663 public:
 664   static char ID; // Pass ID, replacement for typeid
 665   DominanceFrontier() :
 666     DominanceFrontierBase(intptr_t(&ID), 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
 687   /// splitBlock - BB is split and now it has one successor. Update dominance
 688   /// frontier to reflect this change.
 689   void splitBlock(BasicBlock *BB);
 690
 691   /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
 692   /// to reflect this change.
 693   void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
 694                                 DominatorTree *DT) {
 695     // NewBB is now  dominating BB. Which means BB's dominance
 696     // frontier is now part of NewBB's dominance frontier. However, BB
 697     // itself is not member of NewBB's dominance frontier.
 698     DominanceFrontier::iterator NewDFI = find(NewBB);
 699     DominanceFrontier::iterator DFI = find(BB);
 700     DominanceFrontier::DomSetType BBSet = DFI->second;
 701     for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
 702            BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
 703       BasicBlock *DFMember = *BBSetI;
 704       // Insert only if NewBB dominates DFMember.
 705       if (!DT->dominates(NewBB, DFMember))
 706         NewDFI->second.insert(DFMember);
 707     }
 708     NewDFI->second.erase(BB);
 709   }
 710
 711 private:
 712   const DomSetType &calculate(const DominatorTree &DT,
 713                               const DomTreeNode *Node);
 714 };
 715
 716
 717 } // End llvm namespace
 718
 719 #endif