X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=310239823cf1a36a2e78c745ecd3a94218856ade;hb=64925c55c65f9345a69fb67db07aa62cfb723577;hp=b405f5b71ed7c23c570a7cce8bdea73b730f882d;hpb=15002a2b528e04a5edcfccbec392f5d6b19f7f6a;p=oota-llvm.git diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index b405f5b71ed..310239823cf 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -7,14 +7,8 @@ // //===----------------------------------------------------------------------===// // -// This file defines the following classes: -// 1. DominatorTree: Represent dominators as an explicit tree structure. -// 2. DominanceFrontier: Calculate and hold the dominance frontier for a -// function. -// -// These data structures are listed in increasing order of complexity. It -// takes longer to calculate the dominator frontier, for example, than the -// DominatorTree mapping. +// This file defines the DominatorTree class, which provides fast and efficient +// dominance queries. // //===----------------------------------------------------------------------===// @@ -22,19 +16,16 @@ #define LLVM_ANALYSIS_DOMINATORS_H #include "llvm/Pass.h" -#include "llvm/BasicBlock.h" #include "llvm/Function.h" -#include "llvm/Instructions.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Assembly/Writer.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/raw_ostream.h" #include -#include -#include namespace llvm { @@ -51,7 +42,7 @@ protected: Roots(), IsPostDominators(isPostDom) {} public: - /// getRoots - Return the root blocks of the current CFG. This may include + /// getRoots - Return the root blocks of the current CFG. This may include /// multiple blocks if we are computing post dominators. For forward /// dominators, this will always be a single block (the entry node). /// @@ -82,12 +73,12 @@ public: typedef typename std::vector *>::iterator iterator; typedef typename std::vector *>::const_iterator const_iterator; - + iterator begin() { return Children.begin(); } iterator end() { return Children.end(); } const_iterator begin() const { return Children.begin(); } const_iterator end() const { return Children.end(); } - + NodeT *getBlock() const { return TheBB; } DomTreeNodeBase *getIDom() const { return IDom; } const std::vector*> &getChildren() const { @@ -96,7 +87,7 @@ public: DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } - + DomTreeNodeBase *addChild(DomTreeNodeBase *C) { Children.push_back(C); return C; @@ -109,18 +100,18 @@ public: void clearAllChildren() { Children.clear(); } - + bool compare(DomTreeNodeBase *Other) { if (getNumChildren() != Other->getNumChildren()) return true; SmallPtrSet OtherChildren; - for(iterator I = Other->begin(), E = Other->end(); I != E; ++I) { + for (iterator I = Other->begin(), E = Other->end(); I != E; ++I) { NodeT *Nd = (*I)->getBlock(); OtherChildren.insert(Nd); } - for(iterator I = begin(), E = end(); I != E; ++I) { + for (iterator I = begin(), E = end(); I != E; ++I) { NodeT *N = (*I)->getBlock(); if (OtherChildren.count(N) == 0) return true; @@ -143,7 +134,7 @@ public: IDom->Children.push_back(this); } } - + /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do /// not call them. unsigned getDFSNumIn() const { return DFSNumIn; } @@ -161,22 +152,22 @@ EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); template -static std::ostream &operator<<(std::ostream &o, - const DomTreeNodeBase *Node) { +static raw_ostream &operator<<(raw_ostream &o, + const DomTreeNodeBase *Node) { if (Node->getBlock()) WriteAsOperand(o, Node->getBlock(), false); else o << " <>"; - + o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; - + return o << "\n"; } template -static void PrintDomTree(const DomTreeNodeBase *N, std::ostream &o, +static void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &o, unsigned Lev) { - o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; + o.indent(2*Lev) << "[" << Lev << "] " << N; for (typename DomTreeNodeBase::const_iterator I = N->begin(), E = N->end(); I != E; ++I) PrintDomTree(*I, o, Lev+1); @@ -204,15 +195,11 @@ protected: // Information record used during immediate dominators computation. struct InfoRec { unsigned DFSNum; + unsigned Parent; unsigned Semi; - unsigned Size; - NodeT *Label, *Child; - unsigned Parent, Ancestor; + NodeT *Label; - std::vector Bucket; - - InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0), - Ancestor(0) {} + InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {} }; DenseMap IDoms; @@ -224,7 +211,7 @@ protected: DenseMap Info; void reset() { - for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), + for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), E = DomTreeNodes.end(); I != E; ++I) delete I->second; DomTreeNodes.clear(); @@ -233,33 +220,37 @@ protected: Vertex.clear(); RootNode = 0; } - + // NewBB is split and now it has one successor. Update dominator tree to // reflect this change. template void Split(DominatorTreeBase& DT, typename GraphT::NodeType* NewBB) { - assert(std::distance(GraphT::child_begin(NewBB), GraphT::child_end(NewBB)) == 1 - && "NewBB should have a single successor!"); + assert(std::distance(GraphT::child_begin(NewBB), + GraphT::child_end(NewBB)) == 1 && + "NewBB should have a single successor!"); typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB); std::vector PredBlocks; - for (typename GraphTraits >::ChildIteratorType PI = - GraphTraits >::child_begin(NewBB), - PE = GraphTraits >::child_end(NewBB); PI != PE; ++PI) - PredBlocks.push_back(*PI); + typedef GraphTraits > InvTraits; + for (typename InvTraits::ChildIteratorType PI = + InvTraits::child_begin(NewBB), + PE = InvTraits::child_end(NewBB); PI != PE; ++PI) + PredBlocks.push_back(*PI); - assert(!PredBlocks.empty() && "No predblocks??"); + assert(!PredBlocks.empty() && "No predblocks?"); bool NewBBDominatesNewBBSucc = true; - for (typename GraphTraits >::ChildIteratorType PI = - GraphTraits >::child_begin(NewBBSucc), - E = GraphTraits >::child_end(NewBBSucc); PI != E; ++PI) - if (*PI != NewBB && !DT.dominates(NewBBSucc, *PI) && - DT.isReachableFromEntry(*PI)) { + for (typename InvTraits::ChildIteratorType PI = + InvTraits::child_begin(NewBBSucc), + E = InvTraits::child_end(NewBBSucc); PI != E; ++PI) { + typename InvTraits::NodeType *ND = *PI; + if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && + DT.isReachableFromEntry(ND)) { NewBBDominatesNewBBSucc = false; break; } + } // Find NewBB's immediate dominator and create new dominator tree node for // NewBB. @@ -270,12 +261,17 @@ protected: NewBBIDom = PredBlocks[i]; break; } - assert(i != PredBlocks.size() && "No reachable preds?"); + + // It's possible that none of the predecessors of NewBB are reachable; + // in that case, NewBB itself is unreachable, so nothing needs to be + // changed. + if (!NewBBIDom) + return; + for (i = i + 1; i < PredBlocks.size(); ++i) { if (DT.isReachableFromEntry(PredBlocks[i])) NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); } - assert(NewBBIDom && "No immediate dominator found??"); // Create the new dominator tree node... and set the idom of NewBB. DomTreeNodeBase *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); @@ -293,9 +289,6 @@ public: : DominatorBase(isPostDom), DFSInfoValid(false), SlowQueries(0) {} virtual ~DominatorTreeBase() { reset(); } - // FIXME: Should remove this - virtual bool runOnFunction(Function &F) { return false; } - /// compare - Return false if the other dominator tree base matches this /// dominator tree base. Otherwise return true. bool compare(DominatorTreeBase &Other) const { @@ -304,8 +297,7 @@ public: if (DomTreeNodes.size() != OtherDomTreeNodes.size()) return true; - SmallPtrSet MyBBs; - for (typename DomTreeNodeMapType::const_iterator + for (typename DomTreeNodeMapType::const_iterator I = this->DomTreeNodes.begin(), E = this->DomTreeNodes.end(); I != E; ++I) { NodeT *BB = I->first; @@ -315,7 +307,7 @@ public: DomTreeNodeBase* MyNd = I->second; DomTreeNodeBase* OtherNd = OI->second; - + if (MyNd->compare(OtherNd)) return true; } @@ -329,8 +321,7 @@ public: /// block. This is the same as using operator[] on this class. /// inline DomTreeNodeBase *getNode(NodeT *BB) const { - typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB); - return I != DomTreeNodes.end() ? I->second : 0; + return DomTreeNodes.lookup(BB); } /// getRootNode - This returns the entry node for the CFG of the function. If @@ -347,16 +338,23 @@ public: /// Note that this is not a constant time operation! /// bool properlyDominates(const DomTreeNodeBase *A, - DomTreeNodeBase *B) const { + const DomTreeNodeBase *B) const { if (A == 0 || B == 0) return false; return dominatedBySlowTreeWalk(A, B); } - inline bool properlyDominates(NodeT *A, NodeT *B) { - return properlyDominates(getNode(A), getNode(B)); + inline bool properlyDominates(const NodeT *A, const NodeT *B) { + if (A == B) + return false; + + // Cast away the const qualifiers here. This is ok since + // this function doesn't actually return the values returned + // from getNode. + return properlyDominates(getNode(const_cast(A)), + getNode(const_cast(B))); } - bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, + bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, const DomTreeNodeBase *B) const { const DomTreeNodeBase *IDom; if (A == 0 || B == 0) return false; @@ -368,23 +366,31 @@ public: /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. - bool isReachableFromEntry(NodeT* A) { - assert (!this->isPostDominator() - && "This is not implemented for post dominators"); + bool isReachableFromEntry(const NodeT* A) { + assert(!this->isPostDominator() && + "This is not implemented for post dominators"); return dominates(&A->getParent()->front(), A); } - + /// dominates - Returns true iff A dominates B. Note that this is not a /// constant time operation! /// inline bool dominates(const DomTreeNodeBase *A, - DomTreeNodeBase *B) { - if (B == A) + const DomTreeNodeBase *B) { + if (B == A) return true; // A node trivially dominates itself. if (A == 0 || B == 0) return false; + // Compare the result of the tree walk and the dfs numbers, if expensive + // checks are enabled. +#ifdef XDEBUG + assert((!DFSInfoValid || + (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && + "Tree walk disagrees with dfs numbers!"); +#endif + if (DFSInfoValid) return B->DominatedBy(A); @@ -399,13 +405,17 @@ public: return dominatedBySlowTreeWalk(A, B); } - inline bool dominates(NodeT *A, NodeT *B) { - if (A == B) + inline bool dominates(const NodeT *A, const NodeT *B) { + if (A == B) return true; - - return dominates(getNode(A), getNode(B)); + + // Cast away the const qualifiers here. This is ok since + // this function doesn't actually return the values returned + // from getNode. + return dominates(getNode(const_cast(A)), + getNode(const_cast(B))); } - + NodeT *getRoot() const { assert(this->Roots.size() == 1 && "Should always have entry node!"); return this->Roots[0]; @@ -414,16 +424,16 @@ public: /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { - - assert (!this->isPostDominator() - && "This is not implemented for post dominators"); - assert (A->getParent() == B->getParent() - && "Two blocks are not in same function"); - - // If either A or B is a entry block then it is nearest common dominator. - NodeT &Entry = A->getParent()->front(); - if (A == &Entry || B == &Entry) - return &Entry; + assert(A->getParent() == B->getParent() && + "Two blocks are not in same function"); + + // If either A or B is a entry block then it is nearest common dominator + // (for forward-dominators). + if (!this->isPostDominator()) { + NodeT &Entry = A->getParent()->front(); + if (A == &Entry || B == &Entry) + return &Entry; + } // If B dominates A then B is nearest common dominator. if (dominates(B, A)) @@ -447,7 +457,7 @@ public: // Walk NodeB immediate dominators chain and find common dominator node. DomTreeNodeBase *IDomB = NodeB->getIDom(); - while(IDomB) { + while (IDomB) { if (NodeADoms.count(IDomB) != 0) return IDomB->getBlock(); @@ -457,19 +467,26 @@ public: return NULL; } + const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { + // Cast away the const qualifiers here. This is ok since + // const is re-introduced on the return type. + return findNearestCommonDominator(const_cast(A), + const_cast(B)); + } + //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to // the CFG... /// addNewBlock - Add a new node to the dominator tree information. This - /// creates a new node as a child of DomBB dominator node,linking it into + /// creates a new node as a child of DomBB dominator node,linking it into /// the children list of the immediate dominator. DomTreeNodeBase *addNewBlock(NodeT *BB, NodeT *DomBB) { assert(getNode(BB) == 0 && "Block already in dominator tree!"); DomTreeNodeBase *IDomNode = getNode(DomBB); assert(IDomNode && "Not immediate dominator specified for block!"); DFSInfoValid = false; - return DomTreeNodes[BB] = + return DomTreeNodes[BB] = IDomNode->addChild(new DomTreeNodeBase(BB, IDomNode)); } @@ -487,13 +504,13 @@ public: changeImmediateDominator(getNode(BB), getNode(NewBB)); } - /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + /// eraseNode - Removes a node from the dominator tree. Block must not + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. void eraseNode(NodeT *BB) { DomTreeNodeBase *Node = getNode(BB); - assert (Node && "Removing node that isn't in dominator tree."); - assert (Node->getChildren().empty() && "Node is not a leaf node."); + assert(Node && "Removing node that isn't in dominator tree."); + assert(Node->getChildren().empty() && "Node is not a leaf node."); // Remove node from immediate dominator's children list. DomTreeNodeBase *IDom = Node->getIDom(); @@ -517,7 +534,7 @@ public: assert(getNode(BB) && "Removing node that isn't in dominator tree."); DomTreeNodes.erase(BB); } - + /// splitBlock - BB is split and now it has one successor. Update dominator /// tree to reflect this change. void splitBlock(NodeT* NewBB) { @@ -529,51 +546,37 @@ public: /// print - Convert to human readable form /// - virtual void print(std::ostream &o, const Module* ) const { + void print(raw_ostream &o) const { o << "=============================--------------------------------\n"; if (this->isPostDominator()) o << "Inorder PostDominator Tree: "; else o << "Inorder Dominator Tree: "; - if (this->DFSInfoValid) + if (!this->DFSInfoValid) o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; o << "\n"; - PrintDomTree(getRootNode(), o, 1); + // The postdom tree can have a null root if there are no returns. + if (getRootNode()) + PrintDomTree(getRootNode(), o, 1); } - - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } - - virtual void dump() { - print(llvm::cerr); - } - -protected: - template - friend void Compress(DominatorTreeBase& DT, - typename GraphT::NodeType* VIn); +protected: template friend typename GraphT::NodeType* Eval( DominatorTreeBase& DT, - typename GraphT::NodeType* V); + typename GraphT::NodeType* V, + unsigned LastLinked); - template - friend void Link(DominatorTreeBase& DT, - unsigned DFSNumV, typename GraphT::NodeType* W, - typename DominatorTreeBase::InfoRec &WInfo); - template friend unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V, unsigned N); - + template friend void Calculate(DominatorTreeBase::NodeType>& DT, FuncT& F); - + /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking /// dominator tree in dfs order. void updateDFSNumbers() { @@ -582,39 +585,45 @@ protected: SmallVector*, typename DomTreeNodeBase::iterator>, 32> WorkStack; - for (unsigned i = 0, e = (unsigned)this->Roots.size(); i != e; ++i) { - DomTreeNodeBase *ThisRoot = getNode(this->Roots[i]); - WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); - ThisRoot->DFSNumIn = DFSNum++; - - while (!WorkStack.empty()) { - DomTreeNodeBase *Node = WorkStack.back().first; - typename DomTreeNodeBase::iterator ChildIt = - WorkStack.back().second; - - // If we visited all of the children of this node, "recurse" back up the - // stack setting the DFOutNum. - if (ChildIt == Node->end()) { - Node->DFSNumOut = DFSNum++; - WorkStack.pop_back(); - } else { - // Otherwise, recursively visit this child. - DomTreeNodeBase *Child = *ChildIt; - ++WorkStack.back().second; - - WorkStack.push_back(std::make_pair(Child, Child->begin())); - Child->DFSNumIn = DFSNum++; - } + DomTreeNodeBase *ThisRoot = getRootNode(); + + if (!ThisRoot) + return; + + // Even in the case of multiple exits that form the post dominator root + // nodes, do not iterate over all exits, but start from the virtual root + // node. Otherwise bbs, that are not post dominated by any exit but by the + // virtual root node, will never be assigned a DFS number. + WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); + ThisRoot->DFSNumIn = DFSNum++; + + while (!WorkStack.empty()) { + DomTreeNodeBase *Node = WorkStack.back().first; + typename DomTreeNodeBase::iterator ChildIt = + WorkStack.back().second; + + // If we visited all of the children of this node, "recurse" back up the + // stack setting the DFOutNum. + if (ChildIt == Node->end()) { + Node->DFSNumOut = DFSNum++; + WorkStack.pop_back(); + } else { + // Otherwise, recursively visit this child. + DomTreeNodeBase *Child = *ChildIt; + ++WorkStack.back().second; + + WorkStack.push_back(std::make_pair(Child, Child->begin())); + Child->DFSNumIn = DFSNum++; } } - + SlowQueries = 0; DFSInfoValid = true; } - + DomTreeNodeBase *getNodeForBlock(NodeT *BB) { - if (DomTreeNodeBase *BBNode = this->DomTreeNodes[BB]) - return BBNode; + if (DomTreeNodeBase *Node = getNode(BB)) + return Node; // Haven't calculated this node yet? Get or calculate the node for the // immediate dominator. @@ -628,39 +637,37 @@ protected: DomTreeNodeBase *C = new DomTreeNodeBase(BB, IDomNode); return this->DomTreeNodes[BB] = IDomNode->addChild(C); } - + inline NodeT *getIDom(NodeT *BB) const { - typename DenseMap::const_iterator I = IDoms.find(BB); - return I != IDoms.end() ? I->second : 0; + return IDoms.lookup(BB); } - + inline void addRoot(NodeT* BB) { this->Roots.push_back(BB); } - + public: /// recalculate - compute a dominator tree for the given function template void recalculate(FT& F) { + typedef GraphTraits TraitsTy; + reset(); + this->Vertex.push_back(0); + if (!this->IsPostDominators) { - reset(); - - // Initialize roots - this->Roots.push_back(&F.front()); - this->IDoms[&F.front()] = 0; - this->DomTreeNodes[&F.front()] = 0; - this->Vertex.push_back(0); - + // Initialize root + NodeT *entry = TraitsTy::getEntryNode(&F); + this->Roots.push_back(entry); + this->IDoms[entry] = 0; + this->DomTreeNodes[entry] = 0; + Calculate(*this, F); - - updateDFSNumbers(); } else { - reset(); // Reset from the last time we were run... - // Initialize the roots list - for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) { - if (std::distance(GraphTraits::child_begin(I), - GraphTraits::child_end(I)) == 0) + for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), + E = TraitsTy::nodes_end(&F); I != E; ++I) { + if (std::distance(TraitsTy::child_begin(I), + TraitsTy::child_end(I)) == 0) addRoot(I); // Prepopulate maps so that we don't get iterator invalidation issues later. @@ -668,8 +675,6 @@ public: this->DomTreeNodes[I] = 0; } - this->Vertex.push_back(0); - Calculate >(*this, F); } } @@ -685,30 +690,30 @@ class DominatorTree : public FunctionPass { public: static char ID; // Pass ID, replacement for typeid DominatorTreeBase* DT; - - DominatorTree() : FunctionPass(&ID) { + + DominatorTree() : FunctionPass(ID) { + initializeDominatorTreePass(*PassRegistry::getPassRegistry()); DT = new DominatorTreeBase(false); } - + ~DominatorTree() { - DT->releaseMemory(); delete DT; } - + DominatorTreeBase& getBase() { return *DT; } - - /// getRoots - Return the root blocks of the current CFG. This may include + + /// getRoots - Return the root blocks of the current CFG. This may include /// multiple blocks if we are computing post dominators. For forward /// dominators, this will always be a single block (the entry node). /// inline const std::vector &getRoots() const { return DT->getRoots(); } - + inline BasicBlock *getRoot() const { return DT->getRoot(); } - + inline DomTreeNode *getRootNode() const { return DT->getRootNode(); } @@ -718,10 +723,10 @@ public: inline bool compare(DominatorTree &Other) const { DomTreeNode *R = getRootNode(); DomTreeNode *OtherR = Other.getRootNode(); - + if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) return true; - + if (DT->compare(Other.getBase())) return true; @@ -729,324 +734,140 @@ public: } virtual bool runOnFunction(Function &F); - + + virtual void verifyAnalysis() const; + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } - - inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { + + inline bool dominates(const DomTreeNode* A, const DomTreeNode* B) const { return DT->dominates(A, B); } - - inline bool dominates(BasicBlock* A, BasicBlock* B) const { + + inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { return DT->dominates(A, B); } - + // dominates - Return true if A dominates B. This performs the // special checks necessary if A and B are in the same basic block. - bool dominates(Instruction *A, Instruction *B) const { - BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); - if (BBA != BBB) return DT->dominates(BBA, BBB); - - // It is not possible to determine dominance between two PHI nodes - // based on their ordering. - if (isa(A) && isa(B)) - return false; + bool dominates(const Instruction *A, const Instruction *B) const; - // Loop through the basic block until we find A or B. - BasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; - - //if(!DT.IsPostDominators) { - // A dominates B if it is found first in the basic block. - return &*I == A; - //} else { - // // A post-dominates B if B is found first in the basic block. - // return &*I == B; - //} - } - - inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { + bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const { return DT->properlyDominates(A, B); } - - inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { + + bool properlyDominates(const BasicBlock *A, const BasicBlock *B) const { return DT->properlyDominates(A, B); } - + /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { return DT->findNearestCommonDominator(A, B); } - + + inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A, + const BasicBlock *B) { + return DT->findNearestCommonDominator(A, B); + } + inline DomTreeNode *operator[](BasicBlock *BB) const { return DT->getNode(BB); } - + /// getNode - return the (Post)DominatorTree node for the specified basic /// block. This is the same as using operator[] on this class. /// inline DomTreeNode *getNode(BasicBlock *BB) const { return DT->getNode(BB); } - + /// addNewBlock - Add a new node to the dominator tree information. This - /// creates a new node as a child of DomBB dominator node,linking it into + /// creates a new node as a child of DomBB dominator node,linking it into /// the children list of the immediate dominator. inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) { return DT->addNewBlock(BB, DomBB); } - + /// changeImmediateDominator - This method is used to update the dominator /// tree information when a node's immediate dominator changes. /// inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - + inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - - /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + + /// eraseNode - Removes a node from the dominator tree. Block must not + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. inline void eraseNode(BasicBlock *BB) { DT->eraseNode(BB); } - + /// splitBlock - BB is split and now it has one successor. Update dominator /// tree to reflect this change. inline void splitBlock(BasicBlock* NewBB) { DT->splitBlock(NewBB); } - - bool isReachableFromEntry(BasicBlock* A) { + + bool isReachableFromEntry(const BasicBlock* A) { return DT->isReachableFromEntry(A); } - - - virtual void releaseMemory() { + + + virtual void releaseMemory() { DT->releaseMemory(); } - - virtual void print(std::ostream &OS, const Module* M= 0) const { - DT->print(OS, M); - } + + virtual void print(raw_ostream &OS, const Module* M= 0) const; }; //===------------------------------------- /// DominatorTree GraphTraits specialization so the DominatorTree can be /// iterable by generic graph iterators. /// -template <> struct GraphTraits { +template <> struct GraphTraits { typedef DomTreeNode NodeType; typedef NodeType::iterator ChildIteratorType; - + static NodeType *getEntryNode(NodeType *N) { return N; } - static inline ChildIteratorType child_begin(NodeType* N) { + static inline ChildIteratorType child_begin(NodeType *N) { return N->begin(); } - static inline ChildIteratorType child_end(NodeType* N) { + static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } -}; - -template <> struct GraphTraits - : public GraphTraits { - static NodeType *getEntryNode(DominatorTree *DT) { - return DT->getRootNode(); - } -}; - - -//===----------------------------------------------------------------------===// -/// DominanceFrontierBase - Common base class for computing forward and inverse -/// dominance frontiers for a function. -/// -class DominanceFrontierBase : public FunctionPass { -public: - typedef std::set DomSetType; // Dom set for a bb - typedef std::map DomSetMapType; // Dom set map -protected: - DomSetMapType Frontiers; - std::vector Roots; - const bool IsPostDominators; - -public: - DominanceFrontierBase(void *ID, bool isPostDom) - : FunctionPass(ID), IsPostDominators(isPostDom) {} - - /// getRoots - Return the root blocks of the current CFG. This may include - /// multiple blocks if we are computing post dominators. For forward - /// dominators, this will always be a single block (the entry node). - /// - inline const std::vector &getRoots() const { return Roots; } - - /// isPostDominator - Returns true if analysis based of postdoms - /// - bool isPostDominator() const { return IsPostDominators; } - - virtual void releaseMemory() { Frontiers.clear(); } - - // Accessor interface: - typedef DomSetMapType::iterator iterator; - typedef DomSetMapType::const_iterator const_iterator; - iterator begin() { return Frontiers.begin(); } - const_iterator begin() const { return Frontiers.begin(); } - iterator end() { return Frontiers.end(); } - const_iterator end() const { return Frontiers.end(); } - iterator find(BasicBlock *B) { return Frontiers.find(B); } - const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } - - void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { - assert(find(BB) == end() && "Block already in DominanceFrontier!"); - Frontiers.insert(std::make_pair(BB, frontier)); - } - /// removeBlock - Remove basic block BB's frontier. - void removeBlock(BasicBlock *BB) { - assert(find(BB) != end() && "Block is not in DominanceFrontier!"); - for (iterator I = begin(), E = end(); I != E; ++I) - I->second.erase(BB); - Frontiers.erase(BB); - } + typedef df_iterator nodes_iterator; - void addToFrontier(iterator I, BasicBlock *Node) { - assert(I != end() && "BB is not in DominanceFrontier!"); - I->second.insert(Node); + static nodes_iterator nodes_begin(DomTreeNode *N) { + return df_begin(getEntryNode(N)); } - void removeFromFrontier(iterator I, BasicBlock *Node) { - assert(I != end() && "BB is not in DominanceFrontier!"); - assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); - I->second.erase(Node); + static nodes_iterator nodes_end(DomTreeNode *N) { + return df_end(getEntryNode(N)); } - - /// compareDomSet - Return false if two domsets match. Otherwise - /// return true; - bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { - std::set tmpSet; - for (DomSetType::const_iterator I = DS2.begin(), - E = DS2.end(); I != E; ++I) - tmpSet.insert(*I); - - for (DomSetType::const_iterator I = DS1.begin(), - E = DS1.end(); I != E; ) { - BasicBlock *Node = *I++; - - if (tmpSet.erase(Node) == 0) - // Node is in DS1 but not in DS2. - return true; - } - - if(!tmpSet.empty()) - // There are nodes that are in DS2 but not in DS1. - return true; - - // DS1 and DS2 matches. - return false; - } - - /// compare - Return true if the other dominance frontier base matches - /// this dominance frontier base. Otherwise return false. - bool compare(DominanceFrontierBase &Other) const { - DomSetMapType tmpFrontiers; - for (DomSetMapType::const_iterator I = Other.begin(), - E = Other.end(); I != E; ++I) - tmpFrontiers.insert(std::make_pair(I->first, I->second)); - - for (DomSetMapType::iterator I = tmpFrontiers.begin(), - E = tmpFrontiers.end(); I != E; ) { - BasicBlock *Node = I->first; - const_iterator DFI = find(Node); - if (DFI == end()) - return true; - - if (compareDomSet(I->second, DFI->second)) - return true; - - ++I; - tmpFrontiers.erase(Node); - } - - if (!tmpFrontiers.empty()) - return true; - - return false; - } - - /// print - Convert to human readable form - /// - virtual void print(std::ostream &OS, const Module* = 0) const; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } - virtual void dump(); }; - -//===------------------------------------- -/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is -/// used to compute a forward dominator frontiers. -/// -class DominanceFrontier : public DominanceFrontierBase { -public: - static char ID; // Pass ID, replacement for typeid - DominanceFrontier() : - DominanceFrontierBase(&ID, false) {} - - BasicBlock *getRoot() const { - assert(Roots.size() == 1 && "Should always have entry node!"); - return Roots[0]; - } - - virtual bool runOnFunction(Function &) { - Frontiers.clear(); - DominatorTree &DT = getAnalysis(); - Roots = DT.getRoots(); - assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); - calculate(DT, DT[Roots[0]]); - return false; +template <> struct GraphTraits + : public GraphTraits { + static NodeType *getEntryNode(DominatorTree *DT) { + return DT->getRootNode(); } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); + static nodes_iterator nodes_begin(DominatorTree *N) { + return df_begin(getEntryNode(N)); } - /// splitBlock - BB is split and now it has one successor. Update dominance - /// frontier to reflect this change. - void splitBlock(BasicBlock *BB); - - /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier - /// to reflect this change. - void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB, - DominatorTree *DT) { - // NewBB is now dominating BB. Which means BB's dominance - // frontier is now part of NewBB's dominance frontier. However, BB - // itself is not member of NewBB's dominance frontier. - DominanceFrontier::iterator NewDFI = find(NewBB); - DominanceFrontier::iterator DFI = find(BB); - // If BB was an entry block then its frontier is empty. - if (DFI == end()) - return; - DominanceFrontier::DomSetType BBSet = DFI->second; - for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(), - BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) { - BasicBlock *DFMember = *BBSetI; - // Insert only if NewBB dominates DFMember. - if (!DT->dominates(NewBB, DFMember)) - NewDFI->second.insert(DFMember); - } - NewDFI->second.erase(BB); + static nodes_iterator nodes_end(DominatorTree *N) { + return df_end(getEntryNode(N)); } - - const DomSetType &calculate(const DominatorTree &DT, - const DomTreeNode *Node); };