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 NodeT>
 164 class DominatorTreeBase : public DominatorBase<NodeT> {
 165 protected:
 166   typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
 167   DomTreeNodeMapType DomTreeNodes;
 168   DomTreeNodeBase<NodeT> *RootNode;
 169
 170   bool DFSInfoValid;
 171   unsigned int SlowQueries;
 172   // Information record used during immediate dominators computation.
 173   struct InfoRec {
 174     unsigned Semi;
 175     unsigned Size;
 176     NodeT *Label, *Parent, *Child, *Ancestor;
 177
 178     std::vector<NodeT*> Bucket;
 179
 180     InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0) {}
 181   };
 182
 183   DenseMap<NodeT*, NodeT*> IDoms;
 184
 185   // Vertex - Map the DFS number to the BasicBlock*
 186   std::vector<NodeT*> Vertex;
 187
 188   // Info - Collection of information used during the computation of idoms.
 189   DenseMap<NodeT*, InfoRec> Info;
 190
 191   void reset() {
 192     for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
 193            E = DomTreeNodes.end(); I != E; ++I)
 194       delete I->second;
 195     DomTreeNodes.clear();
 196     IDoms.clear();
 197     this->Roots.clear();
 198     Vertex.clear();
 199     RootNode = 0;
 200   }
 201
 202 public:
 203   DominatorTreeBase(intptr_t ID, bool isPostDom)
 204     : DominatorBase<NodeT>(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
 205   ~DominatorTreeBase() { reset(); }
 206
 207   virtual void releaseMemory() { reset(); }
 208
 209   /// getNode - return the (Post)DominatorTree node for the specified basic
 210   /// block.  This is the same as using operator[] on this class.
 211   ///
 212   inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
 213     typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
 214     return I != DomTreeNodes.end() ? I->second : 0;
 215   }
 216
 217   inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const {
 218     return getNode(BB);
 219   }
 220
 221   /// getRootNode - This returns the entry node for the CFG of the function.  If
 222   /// this tree represents the post-dominance relations for a function, however,
 223   /// this root may be a node with the block == NULL.  This is the case when
 224   /// there are multiple exit nodes from a particular function.  Consumers of
 225   /// post-dominance information must be capable of dealing with this
 226   /// possibility.
 227   ///
 228   DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
 229   const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
 230
 231   /// properlyDominates - Returns true iff this dominates N and this != N.
 232   /// Note that this is not a constant time operation!
 233   ///
 234   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
 235                          DomTreeNodeBase<NodeT> *B) const {
 236     if (A == 0 || B == 0) return false;
 237     return dominatedBySlowTreeWalk(A, B);
 238   }
 239
 240   inline bool properlyDominates(NodeT *A, NodeT *B) {
 241     return properlyDominates(getNode(A), getNode(B));
 242   }
 243
 244   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
 245                                const DomTreeNodeBase<NodeT> *B) const {
 246     const DomTreeNodeBase<NodeT> *IDom;
 247     if (A == 0 || B == 0) return false;
 248     while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
 249       B = IDom;   // Walk up the tree
 250     return IDom != 0;
 251   }
 252
 253
 254   /// isReachableFromEntry - Return true if A is dominated by the entry
 255   /// block of the function containing it.
 256   const bool isReachableFromEntry(NodeT* A) {
 257     assert (!this->isPostDominator()
 258             && "This is not implemented for post dominators");
 259     return dominates(&A->getParent()->getEntryBlock(), A);
 260   }
 261
 262   /// dominates - Returns true iff A dominates B.  Note that this is not a
 263   /// constant time operation!
 264   ///
 265   inline bool dominates(const DomTreeNodeBase<NodeT> *A,
 266                         DomTreeNodeBase<NodeT> *B) {
 267     if (B == A)
 268       return true;  // A node trivially dominates itself.
 269
 270     if (A == 0 || B == 0)
 271       return false;
 272
 273     if (DFSInfoValid)
 274       return B->DominatedBy(A);
 275
 276     // If we end up with too many slow queries, just update the
 277     // DFS numbers on the theory that we are going to keep querying.
 278     SlowQueries++;
 279     if (SlowQueries > 32) {
 280       updateDFSNumbers();
 281       return B->DominatedBy(A);
 282     }
 283
 284     return dominatedBySlowTreeWalk(A, B);
 285   }
 286
 287   inline bool dominates(NodeT *A, NodeT *B) {
 288     if (A == B)
 289       return true;
 290
 291     return dominates(getNode(A), getNode(B));
 292   }
 293
 294   /// findNearestCommonDominator - Find nearest common dominator basic block
 295   /// for basic block A and B. If there is no such block then return NULL.
 296   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
 297
 298     assert (!this->isPostDominator()
 299             && "This is not implemented for post dominators");
 300     assert (A->getParent() == B->getParent()
 301             && "Two blocks are not in same function");
 302
 303     // If either A or B is a entry block then it is nearest common dominator.
 304     NodeT &Entry  = A->getParent()->getEntryBlock();
 305     if (A == &Entry || B == &Entry)
 306       return &Entry;
 307
 308     // If B dominates A then B is nearest common dominator.
 309     if (dominates(B, A))
 310       return B;
 311
 312     // If A dominates B then A is nearest common dominator.
 313     if (dominates(A, B))
 314       return A;
 315
 316     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
 317     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
 318
 319     // Collect NodeA dominators set.
 320     SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
 321     NodeADoms.insert(NodeA);
 322     DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
 323     while (IDomA) {
 324       NodeADoms.insert(IDomA);
 325       IDomA = IDomA->getIDom();
 326     }
 327
 328     // Walk NodeB immediate dominators chain and find common dominator node.
 329     DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
 330     while(IDomB) {
 331       if (NodeADoms.count(IDomB) != 0)
 332         return IDomB->getBlock();
 333
 334       IDomB = IDomB->getIDom();
 335     }
 336
 337     return NULL;
 338   }
 339
 340   // dominates - Return true if A dominates B. This performs the
 341   // special checks necessary if A and B are in the same basic block.
 342   bool dominates(Instruction *A, Instruction *B) {
 343     NodeT *BBA = A->getParent(), *BBB = B->getParent();
 344     if (BBA != BBB) return this->dominates(BBA, BBB);
 345
 346     // It is not possible to determine dominance between two PHI nodes
 347     // based on their ordering.
 348     if (isa<PHINode>(A) && isa<PHINode>(B))
 349       return false;
 350
 351     // Loop through the basic block until we find A or B.
 352     typename NodeT::iterator I = BBA->begin();
 353     for (; &*I != A && &*I != B; ++I) /*empty*/;
 354
 355     if(!this->IsPostDominators) {
 356       // A dominates B if it is found first in the basic block.
 357       return &*I == A;
 358     } else {
 359       // A post-dominates B if B is found first in the basic block.
 360       return &*I == B;
 361     }
 362   }
 363
 364   //===--------------------------------------------------------------------===//
 365   // API to update (Post)DominatorTree information based on modifications to
 366   // the CFG...
 367
 368   /// addNewBlock - Add a new node to the dominator tree information.  This
 369   /// creates a new node as a child of DomBB dominator node,linking it into
 370   /// the children list of the immediate dominator.
 371   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
 372     assert(getNode(BB) == 0 && "Block already in dominator tree!");
 373     DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
 374     assert(IDomNode && "Not immediate dominator specified for block!");
 375     DFSInfoValid = false;
 376     return DomTreeNodes[BB] =
 377       IDomNode->addChild(new DomTreeNode(BB, IDomNode));
 378   }
 379
 380   /// changeImmediateDominator - This method is used to update the dominator
 381   /// tree information when a node's immediate dominator changes.
 382   ///
 383   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
 384                                 DomTreeNodeBase<NodeT> *NewIDom) {
 385     assert(N && NewIDom && "Cannot change null node pointers!");
 386     DFSInfoValid = false;
 387     N->setIDom(NewIDom);
 388   }
 389
 390   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
 391     changeImmediateDominator(getNode(BB), getNode(NewBB));
 392   }
 393
 394   /// eraseNode - Removes a node from  the dominator tree. Block must not
 395   /// domiante any other blocks. Removes node from its immediate dominator's
 396   /// children list. Deletes dominator node associated with basic block BB.
 397   void eraseNode(NodeT *BB) {
 398     DomTreeNodeBase<NodeT> *Node = getNode(BB);
 399     assert (Node && "Removing node that isn't in dominator tree.");
 400     assert (Node->getChildren().empty() && "Node is not a leaf node.");
 401
 402       // Remove node from immediate dominator's children list.
 403     DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
 404     if (IDom) {
 405       typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
 406         std::find(IDom->Children.begin(), IDom->Children.end(), Node);
 407       assert(I != IDom->Children.end() &&
 408              "Not in immediate dominator children set!");
 409       // I am no longer your child...
 410       IDom->Children.erase(I);
 411     }
 412
 413     DomTreeNodes.erase(BB);
 414     delete Node;
 415   }
 416
 417   /// removeNode - Removes a node from the dominator tree.  Block must not
 418   /// dominate any other blocks.  Invalidates any node pointing to removed
 419   /// block.
 420   void removeNode(NodeT *BB) {
 421     assert(getNode(BB) && "Removing node that isn't in dominator tree.");
 422     DomTreeNodes.erase(BB);
 423   }
 424
 425   /// print - Convert to human readable form
 426   ///
 427   virtual void print(std::ostream &o, const Module* ) const {
 428     o << "=============================--------------------------------\n";
 429     o << "Inorder Dominator Tree: ";
 430     if (this->DFSInfoValid)
 431       o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
 432     o << "\n";
 433
 434     PrintDomTree<NodeT>(getRootNode(), o, 1);
 435   }
 436
 437   void print(std::ostream *OS, const Module* M = 0) const {
 438     if (OS) print(*OS, M);
 439   }
 440
 441   virtual void dump() {
 442     print(llvm::cerr);
 443   }
 444
 445 protected:
 446   template<class GraphT> friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
 447                                               typename GraphT::NodeType* VIn);
 448   template<class GraphT> friend typename GraphT::NodeType* Eval(
 449                                                   DominatorTreeBase<typename GraphT::NodeType>& DT,
 450                                                   typename GraphT::NodeType* V);
 451   template<class GraphT> friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
 452                                           typename GraphT::NodeType* V,
 453                                           typename GraphT::NodeType* W,
 454                                  typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
 455
 456   template<class GraphT> friend unsigned DFSPass(
 457                                                  DominatorTreeBase<typename GraphT::NodeType>& DT,
 458                                                  typename GraphT::NodeType* V,
 459                                                  unsigned N);
 460
 461   template<class N, class GraphT> friend void Calculate(DominatorTreeBase<typename GraphT::NodeType>& DT,
 462                                                    Function& F);
 463
 464   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
 465   /// dominator tree in dfs order.
 466   void updateDFSNumbers() {
 467     unsigned DFSNum = 0;
 468
 469     SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
 470                 typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
 471
 472     for (unsigned i = 0, e = this->Roots.size(); i != e; ++i) {
 473       DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]);
 474       WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
 475       ThisRoot->DFSNumIn = DFSNum++;
 476
 477       while (!WorkStack.empty()) {
 478         DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
 479         typename DomTreeNodeBase<NodeT>::iterator ChildIt =
 480                                                         WorkStack.back().second;
 481
 482         // If we visited all of the children of this node, "recurse" back up the
 483         // stack setting the DFOutNum.
 484         if (ChildIt == Node->end()) {
 485           Node->DFSNumOut = DFSNum++;
 486           WorkStack.pop_back();
 487         } else {
 488           // Otherwise, recursively visit this child.
 489           DomTreeNodeBase<NodeT> *Child = *ChildIt;
 490           ++WorkStack.back().second;
 491
 492           WorkStack.push_back(std::make_pair(Child, Child->begin()));
 493           Child->DFSNumIn = DFSNum++;
 494         }
 495       }
 496     }
 497
 498     SlowQueries = 0;
 499     DFSInfoValid = true;
 500   }
 501
 502   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
 503     if (DomTreeNodeBase<NodeT> *BBNode = this->DomTreeNodes[BB])
 504       return BBNode;
 505
 506     // Haven't calculated this node yet?  Get or calculate the node for the
 507     // immediate dominator.
 508     NodeT *IDom = getIDom(BB);
 509     DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
 510
 511     // Add a new tree node for this BasicBlock, and link it as a child of
 512     // IDomNode
 513     DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
 514     return this->DomTreeNodes[BB] = IDomNode->addChild(C);
 515   }
 516
 517   inline NodeT *getIDom(NodeT *BB) const {
 518     typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
 519     return I != IDoms.end() ? I->second : 0;
 520   }
 521 };
 522
 523 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
 524
 525 //===-------------------------------------
 526 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
 527 /// compute a normal dominator tree.
 528 ///
 529 class DominatorTree : public DominatorTreeBase<BasicBlock> {
 530 public:
 531   static char ID; // Pass ID, replacement for typeid
 532   DominatorTree() : DominatorTreeBase<BasicBlock>(intptr_t(&ID), false) {}
 533
 534   BasicBlock *getRoot() const {
 535     assert(Roots.size() == 1 && "Should always have entry node!");
 536     return Roots[0];
 537   }
 538
 539   virtual bool runOnFunction(Function &F);
 540
 541   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 542     AU.setPreservesAll();
 543   }
 544
 545   /// splitBlock
 546   /// BB is split and now it has one successor. Update dominator tree to
 547   /// reflect this change.
 548   void splitBlock(BasicBlock *BB);
 549 };
 550
 551 //===-------------------------------------
 552 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 553 /// iterable by generic graph iterators.
 554 ///
 555 template <> struct GraphTraits<DomTreeNode *> {
 556   typedef DomTreeNode NodeType;
 557   typedef NodeType::iterator  ChildIteratorType;
 558
 559   static NodeType *getEntryNode(NodeType *N) {
 560     return N;
 561   }
 562   static inline ChildIteratorType child_begin(NodeType* N) {
 563     return N->begin();
 564   }
 565   static inline ChildIteratorType child_end(NodeType* N) {
 566     return N->end();
 567   }
 568 };
 569
 570 template <> struct GraphTraits<DominatorTree*>
 571   : public GraphTraits<DomTreeNode *> {
 572   static NodeType *getEntryNode(DominatorTree *DT) {
 573     return DT->getRootNode();
 574   }
 575 };
 576
 577
 578 //===----------------------------------------------------------------------===//
 579 /// DominanceFrontierBase - Common base class for computing forward and inverse
 580 /// dominance frontiers for a function.
 581 ///
 582 class DominanceFrontierBase : public DominatorBase<BasicBlock> {
 583 public:
 584   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
 585   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
 586 protected:
 587   DomSetMapType Frontiers;
 588 public:
 589   DominanceFrontierBase(intptr_t ID, bool isPostDom)
 590     : DominatorBase<BasicBlock>(ID, isPostDom) {}
 591
 592   virtual void releaseMemory() { Frontiers.clear(); }
 593
 594   // Accessor interface:
 595   typedef DomSetMapType::iterator iterator;
 596   typedef DomSetMapType::const_iterator const_iterator;
 597   iterator       begin()       { return Frontiers.begin(); }
 598   const_iterator begin() const { return Frontiers.begin(); }
 599   iterator       end()         { return Frontiers.end(); }
 600   const_iterator end()   const { return Frontiers.end(); }
 601   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
 602   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
 603
 604   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
 605     assert(find(BB) == end() && "Block already in DominanceFrontier!");
 606     Frontiers.insert(std::make_pair(BB, frontier));
 607   }
 608
 609   /// removeBlock - Remove basic block BB's frontier.
 610   void removeBlock(BasicBlock *BB) {
 611     assert(find(BB) != end() && "Block is not in DominanceFrontier!");
 612     for (iterator I = begin(), E = end(); I != E; ++I)
 613       I->second.erase(BB);
 614     Frontiers.erase(BB);
 615   }
 616
 617   void addToFrontier(iterator I, BasicBlock *Node) {
 618     assert(I != end() && "BB is not in DominanceFrontier!");
 619     I->second.insert(Node);
 620   }
 621
 622   void removeFromFrontier(iterator I, BasicBlock *Node) {
 623     assert(I != end() && "BB is not in DominanceFrontier!");
 624     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
 625     I->second.erase(Node);
 626   }
 627
 628   /// print - Convert to human readable form
 629   ///
 630   virtual void print(std::ostream &OS, const Module* = 0) const;
 631   void print(std::ostream *OS, const Module* M = 0) const {
 632     if (OS) print(*OS, M);
 633   }
 634   virtual void dump();
 635 };
 636
 637
 638 //===-------------------------------------
 639 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
 640 /// used to compute a forward dominator frontiers.
 641 ///
 642 class DominanceFrontier : public DominanceFrontierBase {
 643 public:
 644   static char ID; // Pass ID, replacement for typeid
 645   DominanceFrontier() :
 646     DominanceFrontierBase(intptr_t(&ID), false) {}
 647
 648   BasicBlock *getRoot() const {
 649     assert(Roots.size() == 1 && "Should always have entry node!");
 650     return Roots[0];
 651   }
 652
 653   virtual bool runOnFunction(Function &) {
 654     Frontiers.clear();
 655     DominatorTree &DT = getAnalysis<DominatorTree>();
 656     Roots = DT.getRoots();
 657     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
 658     calculate(DT, DT[Roots[0]]);
 659     return false;
 660   }
 661
 662   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 663     AU.setPreservesAll();
 664     AU.addRequired<DominatorTree>();
 665   }
 666
 667   /// splitBlock - BB is split and now it has one successor. Update dominance
 668   /// frontier to reflect this change.
 669   void splitBlock(BasicBlock *BB);
 670
 671   /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
 672   /// to reflect this change.
 673   void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
 674                                 DominatorTree *DT) {
 675     // NewBB is now  dominating BB. Which means BB's dominance
 676     // frontier is now part of NewBB's dominance frontier. However, BB
 677     // itself is not member of NewBB's dominance frontier.
 678     DominanceFrontier::iterator NewDFI = find(NewBB);
 679     DominanceFrontier::iterator DFI = find(BB);
 680     DominanceFrontier::DomSetType BBSet = DFI->second;
 681     for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
 682            BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
 683       BasicBlock *DFMember = *BBSetI;
 684       // Insert only if NewBB dominates DFMember.
 685       if (!DT->dominates(NewBB, DFMember))
 686         NewDFI->second.insert(DFMember);
 687     }
 688     NewDFI->second.erase(BB);
 689   }
 690
 691 private:
 692   const DomSetType &calculate(const DominatorTree &DT,
 693                               const DomTreeNode *Node);
 694 };
 695
 696
 697 } // End llvm namespace
 698
 699 #endif