LLVM API Documentation

Dominators.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the following classes:
00011 //  1. DominatorTree: Represent dominators as an explicit tree structure.
00012 //  2. DominanceFrontier: Calculate and hold the dominance frontier for a
00013 //     function.
00014 //
00015 //  These data structures are listed in increasing order of complexity.  It
00016 //  takes longer to calculate the dominator frontier, for example, than the
00017 //  DominatorTree mapping.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #ifndef LLVM_ANALYSIS_DOMINATORS_H
00022 #define LLVM_ANALYSIS_DOMINATORS_H
00023 
00024 #include "llvm/Pass.h"
00025 #include "llvm/BasicBlock.h"
00026 #include "llvm/Function.h"
00027 #include "llvm/Instructions.h"
00028 #include "llvm/ADT/DenseMap.h"
00029 #include "llvm/ADT/GraphTraits.h"
00030 #include "llvm/ADT/SmallPtrSet.h"
00031 #include "llvm/ADT/SmallVector.h"
00032 #include "llvm/Assembly/Writer.h"
00033 #include "llvm/Support/CFG.h"
00034 #include "llvm/Support/Compiler.h"
00035 #include <algorithm>
00036 #include <map>
00037 #include <set>
00038 
00039 namespace llvm {
00040 
00041 //===----------------------------------------------------------------------===//
00042 /// DominatorBase - Base class that other, more interesting dominator analyses
00043 /// inherit from.
00044 ///
00045 template <class NodeT>
00046 class DominatorBase {
00047 protected:
00048   std::vector<NodeT*> Roots;
00049   const bool IsPostDominators;
00050   inline explicit DominatorBase(bool isPostDom) :
00051     Roots(), IsPostDominators(isPostDom) {}
00052 public:
00053 
00054   /// getRoots -  Return the root blocks of the current CFG.  This may include
00055   /// multiple blocks if we are computing post dominators.  For forward
00056   /// dominators, this will always be a single block (the entry node).
00057   ///
00058   inline const std::vector<NodeT*> &getRoots() const { return Roots; }
00059 
00060   /// isPostDominator - Returns true if analysis based of postdoms
00061   ///
00062   bool isPostDominator() const { return IsPostDominators; }
00063 };
00064 
00065 
00066 //===----------------------------------------------------------------------===//
00067 // DomTreeNode - Dominator Tree Node
00068 template<class NodeT> class DominatorTreeBase;
00069 struct PostDominatorTree;
00070 class MachineBasicBlock;
00071 
00072 template <class NodeT>
00073 class DomTreeNodeBase {
00074   NodeT *TheBB;
00075   DomTreeNodeBase<NodeT> *IDom;
00076   std::vector<DomTreeNodeBase<NodeT> *> Children;
00077   int DFSNumIn, DFSNumOut;
00078 
00079   template<class N> friend class DominatorTreeBase;
00080   friend struct PostDominatorTree;
00081 public:
00082   typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
00083   typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
00084                    const_iterator;
00085   
00086   iterator begin()             { return Children.begin(); }
00087   iterator end()               { return Children.end(); }
00088   const_iterator begin() const { return Children.begin(); }
00089   const_iterator end()   const { return Children.end(); }
00090   
00091   NodeT *getBlock() const { return TheBB; }
00092   DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
00093   const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
00094     return Children;
00095   }
00096 
00097   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
00098     : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
00099   
00100   DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
00101     Children.push_back(C);
00102     return C;
00103   }
00104 
00105   size_t getNumChildren() const {
00106     return Children.size();
00107   }
00108 
00109   void clearAllChildren() {
00110     Children.clear();
00111   }
00112   
00113   bool compare(DomTreeNodeBase<NodeT> *Other) {
00114     if (getNumChildren() != Other->getNumChildren())
00115       return true;
00116 
00117     SmallPtrSet<NodeT *, 4> OtherChildren;
00118     for(iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
00119       NodeT *Nd = (*I)->getBlock();
00120       OtherChildren.insert(Nd);
00121     }
00122 
00123     for(iterator I = begin(), E = end(); I != E; ++I) {
00124       NodeT *N = (*I)->getBlock();
00125       if (OtherChildren.count(N) == 0)
00126         return true;
00127     }
00128     return false;
00129   }
00130 
00131   void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
00132     assert(IDom && "No immediate dominator?");
00133     if (IDom != NewIDom) {
00134       typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
00135                   std::find(IDom->Children.begin(), IDom->Children.end(), this);
00136       assert(I != IDom->Children.end() &&
00137              "Not in immediate dominator children set!");
00138       // I am no longer your child...
00139       IDom->Children.erase(I);
00140 
00141       // Switch to new dominator
00142       IDom = NewIDom;
00143       IDom->Children.push_back(this);
00144     }
00145   }
00146   
00147   /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
00148   /// not call them.
00149   unsigned getDFSNumIn() const { return DFSNumIn; }
00150   unsigned getDFSNumOut() const { return DFSNumOut; }
00151 private:
00152   // Return true if this node is dominated by other. Use this only if DFS info
00153   // is valid.
00154   bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
00155     return this->DFSNumIn >= other->DFSNumIn &&
00156       this->DFSNumOut <= other->DFSNumOut;
00157   }
00158 };
00159 
00160 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
00161 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
00162 
00163 template<class NodeT>
00164 static std::ostream &operator<<(std::ostream &o,
00165                                 const DomTreeNodeBase<NodeT> *Node) {
00166   if (Node->getBlock())
00167     WriteAsOperand(o, Node->getBlock(), false);
00168   else
00169     o << " <<exit node>>";
00170   
00171   o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
00172   
00173   return o << "\n";
00174 }
00175 
00176 template<class NodeT>
00177 static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o,
00178                          unsigned Lev) {
00179   o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
00180   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
00181        E = N->end(); I != E; ++I)
00182     PrintDomTree<NodeT>(*I, o, Lev+1);
00183 }
00184 
00185 typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
00186 
00187 //===----------------------------------------------------------------------===//
00188 /// DominatorTree - Calculate the immediate dominator tree for a function.
00189 ///
00190 
00191 template<class FuncT, class N>
00192 void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
00193                FuncT& F);
00194 
00195 template<class NodeT>
00196 class DominatorTreeBase : public DominatorBase<NodeT> {
00197 protected:
00198   typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
00199   DomTreeNodeMapType DomTreeNodes;
00200   DomTreeNodeBase<NodeT> *RootNode;
00201 
00202   bool DFSInfoValid;
00203   unsigned int SlowQueries;
00204   // Information record used during immediate dominators computation.
00205   struct InfoRec {
00206     unsigned DFSNum;
00207     unsigned Semi;
00208     unsigned Size;
00209     NodeT *Label, *Child;
00210     unsigned Parent, Ancestor;
00211 
00212     std::vector<NodeT*> Bucket;
00213 
00214     InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0),
00215                 Ancestor(0) {}
00216   };
00217 
00218   DenseMap<NodeT*, NodeT*> IDoms;
00219 
00220   // Vertex - Map the DFS number to the BasicBlock*
00221   std::vector<NodeT*> Vertex;
00222 
00223   // Info - Collection of information used during the computation of idoms.
00224   DenseMap<NodeT*, InfoRec> Info;
00225 
00226   void reset() {
00227     for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), 
00228            E = DomTreeNodes.end(); I != E; ++I)
00229       delete I->second;
00230     DomTreeNodes.clear();
00231     IDoms.clear();
00232     this->Roots.clear();
00233     Vertex.clear();
00234     RootNode = 0;
00235   }
00236   
00237   // NewBB is split and now it has one successor. Update dominator tree to
00238   // reflect this change.
00239   template<class N, class GraphT>
00240   void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
00241              typename GraphT::NodeType* NewBB) {
00242     assert(std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1
00243            && "NewBB should have a single successor!");
00244     typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB);
00245 
00246     std::vector<typename GraphT::NodeType*> PredBlocks;
00247     for (typename GraphTraits<Inverse<N> >::ChildIteratorType PI =
00248          GraphTraits<Inverse<N> >::child_begin(NewBB),
00249          PE = GraphTraits<Inverse<N> >::child_end(NewBB); PI != PE; ++PI)
00250       PredBlocks.push_back(*PI);  
00251 
00252     assert(!PredBlocks.empty() && "No predblocks??");
00253 
00254     bool NewBBDominatesNewBBSucc = true;
00255     for (typename GraphTraits<Inverse<N> >::ChildIteratorType PI =
00256          GraphTraits<Inverse<N> >::child_begin(NewBBSucc),
00257          E = GraphTraits<Inverse<N> >::child_end(NewBBSucc); PI != E; ++PI)
00258       if (*PI != NewBB && !DT.dominates(NewBBSucc, *PI) &&
00259           DT.isReachableFromEntry(*PI)) {
00260         NewBBDominatesNewBBSucc = false;
00261         break;
00262       }
00263 
00264     // Find NewBB's immediate dominator and create new dominator tree node for
00265     // NewBB.
00266     NodeT *NewBBIDom = 0;
00267     unsigned i = 0;
00268     for (i = 0; i < PredBlocks.size(); ++i)
00269       if (DT.isReachableFromEntry(PredBlocks[i])) {
00270         NewBBIDom = PredBlocks[i];
00271         break;
00272       }
00273 
00274     // It's possible that none of the predecessors of NewBB are reachable;
00275     // in that case, NewBB itself is unreachable, so nothing needs to be
00276     // changed.
00277     if (!NewBBIDom)
00278       return;
00279 
00280     for (i = i + 1; i < PredBlocks.size(); ++i) {
00281       if (DT.isReachableFromEntry(PredBlocks[i]))
00282         NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
00283     }
00284 
00285     // Create the new dominator tree node... and set the idom of NewBB.
00286     DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
00287 
00288     // If NewBB strictly dominates other blocks, then it is now the immediate
00289     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
00290     if (NewBBDominatesNewBBSucc) {
00291       DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
00292       DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
00293     }
00294   }
00295 
00296 public:
00297   explicit DominatorTreeBase(bool isPostDom)
00298     : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
00299   virtual ~DominatorTreeBase() { reset(); }
00300 
00301   // FIXME: Should remove this
00302   virtual bool runOnFunction(Function &F) { return false; }
00303 
00304   /// compare - Return false if the other dominator tree base matches this
00305   /// dominator tree base. Otherwise return true.
00306   bool compare(DominatorTreeBase &Other) const {
00307 
00308     const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
00309     if (DomTreeNodes.size() != OtherDomTreeNodes.size())
00310       return true;
00311 
00312     SmallPtrSet<const NodeT *,4> MyBBs;
00313     for (typename DomTreeNodeMapType::const_iterator 
00314            I = this->DomTreeNodes.begin(),
00315            E = this->DomTreeNodes.end(); I != E; ++I) {
00316       NodeT *BB = I->first;
00317       typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB);
00318       if (OI == OtherDomTreeNodes.end())
00319         return true;
00320 
00321       DomTreeNodeBase<NodeT>* MyNd = I->second;
00322       DomTreeNodeBase<NodeT>* OtherNd = OI->second;
00323       
00324       if (MyNd->compare(OtherNd))
00325         return true;
00326     }
00327 
00328     return false;
00329   }
00330 
00331   virtual void releaseMemory() { reset(); }
00332 
00333   /// getNode - return the (Post)DominatorTree node for the specified basic
00334   /// block.  This is the same as using operator[] on this class.
00335   ///
00336   inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
00337     typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
00338     return I != DomTreeNodes.end() ? I->second : 0;
00339   }
00340 
00341   /// getRootNode - This returns the entry node for the CFG of the function.  If
00342   /// this tree represents the post-dominance relations for a function, however,
00343   /// this root may be a node with the block == NULL.  This is the case when
00344   /// there are multiple exit nodes from a particular function.  Consumers of
00345   /// post-dominance information must be capable of dealing with this
00346   /// possibility.
00347   ///
00348   DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
00349   const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
00350 
00351   /// properlyDominates - Returns true iff this dominates N and this != N.
00352   /// Note that this is not a constant time operation!
00353   ///
00354   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
00355                          DomTreeNodeBase<NodeT> *B) const {
00356     if (A == 0 || B == 0) return false;
00357     return dominatedBySlowTreeWalk(A, B);
00358   }
00359 
00360   inline bool properlyDominates(NodeT *A, NodeT *B) {
00361     return properlyDominates(getNode(A), getNode(B));
00362   }
00363 
00364   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, 
00365                                const DomTreeNodeBase<NodeT> *B) const {
00366     const DomTreeNodeBase<NodeT> *IDom;
00367     if (A == 0 || B == 0) return false;
00368     while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
00369       B = IDom;   // Walk up the tree
00370     return IDom != 0;
00371   }
00372 
00373 
00374   /// isReachableFromEntry - Return true if A is dominated by the entry
00375   /// block of the function containing it.
00376   bool isReachableFromEntry(NodeT* A) {
00377     assert (!this->isPostDominator() 
00378             && "This is not implemented for post dominators");
00379     return dominates(&A->getParent()->front(), A);
00380   }
00381   
00382   /// dominates - Returns true iff A dominates B.  Note that this is not a
00383   /// constant time operation!
00384   ///
00385   inline bool dominates(const DomTreeNodeBase<NodeT> *A,
00386                         DomTreeNodeBase<NodeT> *B) {
00387     if (B == A) 
00388       return true;  // A node trivially dominates itself.
00389 
00390     if (A == 0 || B == 0)
00391       return false;
00392 
00393     if (DFSInfoValid)
00394       return B->DominatedBy(A);
00395 
00396     // If we end up with too many slow queries, just update the
00397     // DFS numbers on the theory that we are going to keep querying.
00398     SlowQueries++;
00399     if (SlowQueries > 32) {
00400       updateDFSNumbers();
00401       return B->DominatedBy(A);
00402     }
00403 
00404     return dominatedBySlowTreeWalk(A, B);
00405   }
00406 
00407   inline bool dominates(NodeT *A, NodeT *B) {
00408     if (A == B) 
00409       return true;
00410     
00411     return dominates(getNode(A), getNode(B));
00412   }
00413   
00414   NodeT *getRoot() const {
00415     assert(this->Roots.size() == 1 && "Should always have entry node!");
00416     return this->Roots[0];
00417   }
00418 
00419   /// findNearestCommonDominator - Find nearest common dominator basic block
00420   /// for basic block A and B. If there is no such block then return NULL.
00421   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
00422 
00423     assert (!this->isPostDominator() 
00424             && "This is not implemented for post dominators");
00425     assert (A->getParent() == B->getParent() 
00426             && "Two blocks are not in same function");
00427 
00428     // If either A or B is a entry block then it is nearest common dominator.
00429     NodeT &Entry  = A->getParent()->front();
00430     if (A == &Entry || B == &Entry)
00431       return &Entry;
00432 
00433     // If B dominates A then B is nearest common dominator.
00434     if (dominates(B, A))
00435       return B;
00436 
00437     // If A dominates B then A is nearest common dominator.
00438     if (dominates(A, B))
00439       return A;
00440 
00441     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
00442     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
00443 
00444     // Collect NodeA dominators set.
00445     SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
00446     NodeADoms.insert(NodeA);
00447     DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
00448     while (IDomA) {
00449       NodeADoms.insert(IDomA);
00450       IDomA = IDomA->getIDom();
00451     }
00452 
00453     // Walk NodeB immediate dominators chain and find common dominator node.
00454     DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
00455     while(IDomB) {
00456       if (NodeADoms.count(IDomB) != 0)
00457         return IDomB->getBlock();
00458 
00459       IDomB = IDomB->getIDom();
00460     }
00461 
00462     return NULL;
00463   }
00464 
00465   //===--------------------------------------------------------------------===//
00466   // API to update (Post)DominatorTree information based on modifications to
00467   // the CFG...
00468 
00469   /// addNewBlock - Add a new node to the dominator tree information.  This
00470   /// creates a new node as a child of DomBB dominator node,linking it into 
00471   /// the children list of the immediate dominator.
00472   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
00473     assert(getNode(BB) == 0 && "Block already in dominator tree!");
00474     DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
00475     assert(IDomNode && "Not immediate dominator specified for block!");
00476     DFSInfoValid = false;
00477     return DomTreeNodes[BB] = 
00478       IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode));
00479   }
00480 
00481   /// changeImmediateDominator - This method is used to update the dominator
00482   /// tree information when a node's immediate dominator changes.
00483   ///
00484   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
00485                                 DomTreeNodeBase<NodeT> *NewIDom) {
00486     assert(N && NewIDom && "Cannot change null node pointers!");
00487     DFSInfoValid = false;
00488     N->setIDom(NewIDom);
00489   }
00490 
00491   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
00492     changeImmediateDominator(getNode(BB), getNode(NewBB));
00493   }
00494 
00495   /// eraseNode - Removes a node from  the dominator tree. Block must not
00496   /// domiante any other blocks. Removes node from its immediate dominator's
00497   /// children list. Deletes dominator node associated with basic block BB.
00498   void eraseNode(NodeT *BB) {
00499     DomTreeNodeBase<NodeT> *Node = getNode(BB);
00500     assert (Node && "Removing node that isn't in dominator tree.");
00501     assert (Node->getChildren().empty() && "Node is not a leaf node.");
00502 
00503       // Remove node from immediate dominator's children list.
00504     DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
00505     if (IDom) {
00506       typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
00507         std::find(IDom->Children.begin(), IDom->Children.end(), Node);
00508       assert(I != IDom->Children.end() &&
00509              "Not in immediate dominator children set!");
00510       // I am no longer your child...
00511       IDom->Children.erase(I);
00512     }
00513 
00514     DomTreeNodes.erase(BB);
00515     delete Node;
00516   }
00517 
00518   /// removeNode - Removes a node from the dominator tree.  Block must not
00519   /// dominate any other blocks.  Invalidates any node pointing to removed
00520   /// block.
00521   void removeNode(NodeT *BB) {
00522     assert(getNode(BB) && "Removing node that isn't in dominator tree.");
00523     DomTreeNodes.erase(BB);
00524   }
00525   
00526   /// splitBlock - BB is split and now it has one successor. Update dominator
00527   /// tree to reflect this change.
00528   void splitBlock(NodeT* NewBB) {
00529     if (this->IsPostDominators)
00530       this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
00531     else
00532       this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB);
00533   }
00534 
00535   /// print - Convert to human readable form
00536   ///
00537   virtual void print(std::ostream &o, const Module* ) const {
00538     o << "=============================--------------------------------\n";
00539     if (this->isPostDominator())
00540       o << "Inorder PostDominator Tree: ";
00541     else
00542       o << "Inorder Dominator Tree: ";
00543     if (this->DFSInfoValid)
00544       o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
00545     o << "\n";
00546 
00547     PrintDomTree<NodeT>(getRootNode(), o, 1);
00548   }
00549   
00550   void print(std::ostream *OS, const Module* M = 0) const {
00551     if (OS) print(*OS, M);
00552   }
00553   
00554   virtual void dump() {
00555     print(llvm::cerr);
00556   }
00557   
00558 protected:
00559   template<class GraphT>
00560   friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
00561                        typename GraphT::NodeType* VIn);
00562 
00563   template<class GraphT>
00564   friend typename GraphT::NodeType* Eval(
00565                                DominatorTreeBase<typename GraphT::NodeType>& DT,
00566                                          typename GraphT::NodeType* V);
00567 
00568   template<class GraphT>
00569   friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
00570                    unsigned DFSNumV, typename GraphT::NodeType* W,
00571          typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
00572   
00573   template<class GraphT>
00574   friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
00575                           typename GraphT::NodeType* V,
00576                           unsigned N);
00577   
00578   template<class FuncT, class N>
00579   friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
00580                         FuncT& F);
00581   
00582   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
00583   /// dominator tree in dfs order.
00584   void updateDFSNumbers() {
00585     unsigned DFSNum = 0;
00586 
00587     SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
00588                 typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
00589 
00590     for (unsigned i = 0, e = (unsigned)this->Roots.size(); i != e; ++i) {
00591       DomTreeNodeBase<NodeT> *ThisRoot = getNode(this->Roots[i]);
00592       WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
00593       ThisRoot->DFSNumIn = DFSNum++;
00594 
00595       while (!WorkStack.empty()) {
00596         DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
00597         typename DomTreeNodeBase<NodeT>::iterator ChildIt =
00598                                                         WorkStack.back().second;
00599 
00600         // If we visited all of the children of this node, "recurse" back up the
00601         // stack setting the DFOutNum.
00602         if (ChildIt == Node->end()) {
00603           Node->DFSNumOut = DFSNum++;
00604           WorkStack.pop_back();
00605         } else {
00606           // Otherwise, recursively visit this child.
00607           DomTreeNodeBase<NodeT> *Child = *ChildIt;
00608           ++WorkStack.back().second;
00609           
00610           WorkStack.push_back(std::make_pair(Child, Child->begin()));
00611           Child->DFSNumIn = DFSNum++;
00612         }
00613       }
00614     }
00615     
00616     SlowQueries = 0;
00617     DFSInfoValid = true;
00618   }
00619   
00620   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
00621     typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB);
00622     if (I != this->DomTreeNodes.end() && I->second)
00623       return I->second;
00624 
00625     // Haven't calculated this node yet?  Get or calculate the node for the
00626     // immediate dominator.
00627     NodeT *IDom = getIDom(BB);
00628 
00629     assert(IDom || this->DomTreeNodes[NULL]);
00630     DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
00631 
00632     // Add a new tree node for this BasicBlock, and link it as a child of
00633     // IDomNode
00634     DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
00635     return this->DomTreeNodes[BB] = IDomNode->addChild(C);
00636   }
00637   
00638   inline NodeT *getIDom(NodeT *BB) const {
00639     typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
00640     return I != IDoms.end() ? I->second : 0;
00641   }
00642   
00643   inline void addRoot(NodeT* BB) {
00644     this->Roots.push_back(BB);
00645   }
00646   
00647 public:
00648   /// recalculate - compute a dominator tree for the given function
00649   template<class FT>
00650   void recalculate(FT& F) {
00651     if (!this->IsPostDominators) {
00652       reset();
00653       
00654       // Initialize roots
00655       this->Roots.push_back(&F.front());
00656       this->IDoms[&F.front()] = 0;
00657       this->DomTreeNodes[&F.front()] = 0;
00658       this->Vertex.push_back(0);
00659       
00660       Calculate<FT, NodeT*>(*this, F);
00661       
00662       updateDFSNumbers();
00663     } else {
00664       reset();     // Reset from the last time we were run...
00665 
00666       // Initialize the roots list
00667       for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
00668         if (std::distance(GraphTraits<FT*>::child_begin(I),
00669                           GraphTraits<FT*>::child_end(I)) == 0)
00670           addRoot(I);
00671 
00672         // Prepopulate maps so that we don't get iterator invalidation issues later.
00673         this->IDoms[I] = 0;
00674         this->DomTreeNodes[I] = 0;
00675       }
00676 
00677       this->Vertex.push_back(0);
00678       
00679       Calculate<FT, Inverse<NodeT*> >(*this, F);
00680     }
00681   }
00682 };
00683 
00684 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
00685 
00686 //===-------------------------------------
00687 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
00688 /// compute a normal dominator tree.
00689 ///
00690 class DominatorTree : public FunctionPass {
00691 public:
00692   static char ID; // Pass ID, replacement for typeid
00693   DominatorTreeBase<BasicBlock>* DT;
00694   
00695   DominatorTree() : FunctionPass(&ID) {
00696     DT = new DominatorTreeBase<BasicBlock>(false);
00697   }
00698   
00699   ~DominatorTree() {
00700     DT->releaseMemory();
00701     delete DT;
00702   }
00703   
00704   DominatorTreeBase<BasicBlock>& getBase() { return *DT; }
00705   
00706   /// getRoots -  Return the root blocks of the current CFG.  This may include
00707   /// multiple blocks if we are computing post dominators.  For forward
00708   /// dominators, this will always be a single block (the entry node).
00709   ///
00710   inline const std::vector<BasicBlock*> &getRoots() const {
00711     return DT->getRoots();
00712   }
00713   
00714   inline BasicBlock *getRoot() const {
00715     return DT->getRoot();
00716   }
00717   
00718   inline DomTreeNode *getRootNode() const {
00719     return DT->getRootNode();
00720   }
00721 
00722   /// compare - Return false if the other dominator tree matches this
00723   /// dominator tree. Otherwise return true.
00724   inline bool compare(DominatorTree &Other) const {
00725     DomTreeNode *R = getRootNode();
00726     DomTreeNode *OtherR = Other.getRootNode();
00727     
00728     if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
00729       return true;
00730     
00731     if (DT->compare(Other.getBase()))
00732       return true;
00733 
00734     return false;
00735   }
00736 
00737   virtual bool runOnFunction(Function &F);
00738   
00739   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00740     AU.setPreservesAll();
00741   }
00742   
00743   inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
00744     return DT->dominates(A, B);
00745   }
00746   
00747   inline bool dominates(BasicBlock* A, BasicBlock* B) const {
00748     return DT->dominates(A, B);
00749   }
00750   
00751   // dominates - Return true if A dominates B. This performs the
00752   // special checks necessary if A and B are in the same basic block.
00753   bool dominates(Instruction *A, Instruction *B) const {
00754     BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
00755     if (BBA != BBB) return DT->dominates(BBA, BBB);
00756 
00757     // It is not possible to determine dominance between two PHI nodes 
00758     // based on their ordering.
00759     if (isa<PHINode>(A) && isa<PHINode>(B)) 
00760       return false;
00761 
00762     // Loop through the basic block until we find A or B.
00763     BasicBlock::iterator I = BBA->begin();
00764     for (; &*I != A && &*I != B; ++I) /*empty*/;
00765 
00766     //if(!DT.IsPostDominators) {
00767       // A dominates B if it is found first in the basic block.
00768       return &*I == A;
00769     //} else {
00770     //  // A post-dominates B if B is found first in the basic block.
00771     //  return &*I == B;
00772     //}
00773   }
00774   
00775   inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const {
00776     return DT->properlyDominates(A, B);
00777   }
00778   
00779   inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const {
00780     return DT->properlyDominates(A, B);
00781   }
00782   
00783   /// findNearestCommonDominator - Find nearest common dominator basic block
00784   /// for basic block A and B. If there is no such block then return NULL.
00785   inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
00786     return DT->findNearestCommonDominator(A, B);
00787   }
00788   
00789   inline DomTreeNode *operator[](BasicBlock *BB) const {
00790     return DT->getNode(BB);
00791   }
00792   
00793   /// getNode - return the (Post)DominatorTree node for the specified basic
00794   /// block.  This is the same as using operator[] on this class.
00795   ///
00796   inline DomTreeNode *getNode(BasicBlock *BB) const {
00797     return DT->getNode(BB);
00798   }
00799   
00800   /// addNewBlock - Add a new node to the dominator tree information.  This
00801   /// creates a new node as a child of DomBB dominator node,linking it into 
00802   /// the children list of the immediate dominator.
00803   inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
00804     return DT->addNewBlock(BB, DomBB);
00805   }
00806   
00807   /// changeImmediateDominator - This method is used to update the dominator
00808   /// tree information when a node's immediate dominator changes.
00809   ///
00810   inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) {
00811     DT->changeImmediateDominator(N, NewIDom);
00812   }
00813   
00814   inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) {
00815     DT->changeImmediateDominator(N, NewIDom);
00816   }
00817   
00818   /// eraseNode - Removes a node from  the dominator tree. Block must not
00819   /// domiante any other blocks. Removes node from its immediate dominator's
00820   /// children list. Deletes dominator node associated with basic block BB.
00821   inline void eraseNode(BasicBlock *BB) {
00822     DT->eraseNode(BB);
00823   }
00824   
00825   /// splitBlock - BB is split and now it has one successor. Update dominator
00826   /// tree to reflect this change.
00827   inline void splitBlock(BasicBlock* NewBB) {
00828     DT->splitBlock(NewBB);
00829   }
00830   
00831   bool isReachableFromEntry(BasicBlock* A) {
00832     return DT->isReachableFromEntry(A);
00833   }
00834   
00835   
00836   virtual void releaseMemory() { 
00837     DT->releaseMemory();
00838   }
00839   
00840   virtual void print(std::ostream &OS, const Module* M= 0) const {
00841     DT->print(OS, M);
00842   }
00843 };
00844 
00845 //===-------------------------------------
00846 /// DominatorTree GraphTraits specialization so the DominatorTree can be
00847 /// iterable by generic graph iterators.
00848 ///
00849 template <> struct GraphTraits<DomTreeNode *> {
00850   typedef DomTreeNode NodeType;
00851   typedef NodeType::iterator  ChildIteratorType;
00852   
00853   static NodeType *getEntryNode(NodeType *N) {
00854     return N;
00855   }
00856   static inline ChildIteratorType child_begin(NodeType* N) {
00857     return N->begin();
00858   }
00859   static inline ChildIteratorType child_end(NodeType* N) {
00860     return N->end();
00861   }
00862 };
00863 
00864 template <> struct GraphTraits<DominatorTree*>
00865   : public GraphTraits<DomTreeNode *> {
00866   static NodeType *getEntryNode(DominatorTree *DT) {
00867     return DT->getRootNode();
00868   }
00869 };
00870 
00871 
00872 //===----------------------------------------------------------------------===//
00873 /// DominanceFrontierBase - Common base class for computing forward and inverse
00874 /// dominance frontiers for a function.
00875 ///
00876 class DominanceFrontierBase : public FunctionPass {
00877 public:
00878   typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
00879   typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
00880 protected:
00881   DomSetMapType Frontiers;
00882   std::vector<BasicBlock*> Roots;
00883   const bool IsPostDominators;
00884   
00885 public:
00886   DominanceFrontierBase(void *ID, bool isPostDom) 
00887     : FunctionPass(ID), IsPostDominators(isPostDom) {}
00888 
00889   /// getRoots -  Return the root blocks of the current CFG.  This may include
00890   /// multiple blocks if we are computing post dominators.  For forward
00891   /// dominators, this will always be a single block (the entry node).
00892   ///
00893   inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
00894   
00895   /// isPostDominator - Returns true if analysis based of postdoms
00896   ///
00897   bool isPostDominator() const { return IsPostDominators; }
00898 
00899   virtual void releaseMemory() { Frontiers.clear(); }
00900 
00901   // Accessor interface:
00902   typedef DomSetMapType::iterator iterator;
00903   typedef DomSetMapType::const_iterator const_iterator;
00904   iterator       begin()       { return Frontiers.begin(); }
00905   const_iterator begin() const { return Frontiers.begin(); }
00906   iterator       end()         { return Frontiers.end(); }
00907   const_iterator end()   const { return Frontiers.end(); }
00908   iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
00909   const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
00910 
00911   void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
00912     assert(find(BB) == end() && "Block already in DominanceFrontier!");
00913     Frontiers.insert(std::make_pair(BB, frontier));
00914   }
00915 
00916   /// removeBlock - Remove basic block BB's frontier.
00917   void removeBlock(BasicBlock *BB) {
00918     assert(find(BB) != end() && "Block is not in DominanceFrontier!");
00919     for (iterator I = begin(), E = end(); I != E; ++I)
00920       I->second.erase(BB);
00921     Frontiers.erase(BB);
00922   }
00923 
00924   void addToFrontier(iterator I, BasicBlock *Node) {
00925     assert(I != end() && "BB is not in DominanceFrontier!");
00926     I->second.insert(Node);
00927   }
00928 
00929   void removeFromFrontier(iterator I, BasicBlock *Node) {
00930     assert(I != end() && "BB is not in DominanceFrontier!");
00931     assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
00932     I->second.erase(Node);
00933   }
00934 
00935   /// compareDomSet - Return false if two domsets match. Otherwise
00936   /// return true;
00937   bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
00938     std::set<BasicBlock *> tmpSet;
00939     for (DomSetType::const_iterator I = DS2.begin(),
00940            E = DS2.end(); I != E; ++I) 
00941       tmpSet.insert(*I);
00942 
00943     for (DomSetType::const_iterator I = DS1.begin(),
00944            E = DS1.end(); I != E; ) {
00945       BasicBlock *Node = *I++;
00946 
00947       if (tmpSet.erase(Node) == 0)
00948         // Node is in DS1 but not in DS2.
00949         return true;
00950     }
00951 
00952     if(!tmpSet.empty())
00953       // There are nodes that are in DS2 but not in DS1.
00954       return true;
00955 
00956     // DS1 and DS2 matches.
00957     return false;
00958   }
00959 
00960   /// compare - Return true if the other dominance frontier base matches
00961   /// this dominance frontier base. Otherwise return false.
00962   bool compare(DominanceFrontierBase &Other) const {
00963     DomSetMapType tmpFrontiers;
00964     for (DomSetMapType::const_iterator I = Other.begin(),
00965            E = Other.end(); I != E; ++I) 
00966       tmpFrontiers.insert(std::make_pair(I->first, I->second));
00967 
00968     for (DomSetMapType::iterator I = tmpFrontiers.begin(),
00969            E = tmpFrontiers.end(); I != E; ) {
00970       BasicBlock *Node = I->first;
00971       const_iterator DFI = find(Node);
00972       if (DFI == end()) 
00973         return true;
00974 
00975       if (compareDomSet(I->second, DFI->second))
00976         return true;
00977 
00978       ++I;
00979       tmpFrontiers.erase(Node);
00980     }
00981 
00982     if (!tmpFrontiers.empty())
00983       return true;
00984 
00985     return false;
00986   }
00987 
00988   /// print - Convert to human readable form
00989   ///
00990   virtual void print(std::ostream &OS, const Module* = 0) const;
00991   void print(std::ostream *OS, const Module* M = 0) const {
00992     if (OS) print(*OS, M);
00993   }
00994   virtual void dump();
00995 };
00996 
00997 
00998 //===-------------------------------------
00999 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
01000 /// used to compute a forward dominator frontiers.
01001 ///
01002 class DominanceFrontier : public DominanceFrontierBase {
01003 public:
01004   static char ID; // Pass ID, replacement for typeid
01005   DominanceFrontier() : 
01006     DominanceFrontierBase(&ID, false) {}
01007 
01008   BasicBlock *getRoot() const {
01009     assert(Roots.size() == 1 && "Should always have entry node!");
01010     return Roots[0];
01011   }
01012 
01013   virtual bool runOnFunction(Function &) {
01014     Frontiers.clear();
01015     DominatorTree &DT = getAnalysis<DominatorTree>();
01016     Roots = DT.getRoots();
01017     assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
01018     calculate(DT, DT[Roots[0]]);
01019     return false;
01020   }
01021 
01022   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
01023     AU.setPreservesAll();
01024     AU.addRequired<DominatorTree>();
01025   }
01026 
01027   /// splitBlock - BB is split and now it has one successor. Update dominance
01028   /// frontier to reflect this change.
01029   void splitBlock(BasicBlock *BB);
01030 
01031   /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
01032   /// to reflect this change.
01033   void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
01034                                 DominatorTree *DT) {
01035     // NewBB is now  dominating BB. Which means BB's dominance
01036     // frontier is now part of NewBB's dominance frontier. However, BB
01037     // itself is not member of NewBB's dominance frontier.
01038     DominanceFrontier::iterator NewDFI = find(NewBB);
01039     DominanceFrontier::iterator DFI = find(BB);
01040     // If BB was an entry block then its frontier is empty.
01041     if (DFI == end())
01042       return;
01043     DominanceFrontier::DomSetType BBSet = DFI->second;
01044     for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
01045            BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
01046       BasicBlock *DFMember = *BBSetI;
01047       // Insert only if NewBB dominates DFMember.
01048       if (!DT->dominates(NewBB, DFMember))
01049         NewDFI->second.insert(DFMember);
01050     }
01051     NewDFI->second.erase(BB);
01052   }
01053 
01054   const DomSetType &calculate(const DominatorTree &DT,
01055                               const DomTreeNode *Node);
01056 };
01057 
01058 
01059 } // End llvm namespace
01060 
01061 #endif