X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=956ed1a36f116202a8434602def65d4a0d8c62cc;hb=af9ac8f8212a062291e218ea0dea90a2e81dcf66;hp=dfb73bd0d747535dd8643891bee3ab45b5d78c64;hpb=276222a5ae189ed5c6a2afb248d4c8f0335585b4;p=oota-llvm.git diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index dfb73bd0d74..956ed1a36f1 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -22,32 +22,40 @@ #define LLVM_ANALYSIS_DOMINATORS_H #include "llvm/Pass.h" -#include +#include "llvm/BasicBlock.h" +#include "llvm/Function.h" +#include "llvm/Instruction.h" +#include "llvm/Instructions.h" #include "llvm/ADT/DenseMap.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 +#include namespace llvm { -class Instruction; - -template struct GraphTraits; - //===----------------------------------------------------------------------===// /// DominatorBase - Base class that other, more interesting dominator analyses /// inherit from. /// -class DominatorBase : public FunctionPass { +template +class DominatorBase { protected: - std::vector Roots; + std::vector Roots; const bool IsPostDominators; - inline DominatorBase(intptr_t ID, bool isPostDom) : - FunctionPass(ID), Roots(), IsPostDominators(isPostDom) {} + inline DominatorBase(bool isPostDom) : + Roots(), IsPostDominators(isPostDom) {} public: /// 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; } + inline const std::vector &getRoots() const { return Roots; } /// isPostDominator - Returns true if analysis based of postdoms /// @@ -57,34 +65,58 @@ public: //===----------------------------------------------------------------------===// // DomTreeNode - Dominator Tree Node -class DominatorTreeBase; -class PostDominatorTree; -class DomTreeNode { - BasicBlock *TheBB; - DomTreeNode *IDom; - std::vector Children; +template class DominatorTreeBase; +struct PostDominatorTree; +class MachineBasicBlock; + +template +class DomTreeNodeBase { + NodeT *TheBB; + DomTreeNodeBase *IDom; + std::vector *> Children; int DFSNumIn, DFSNumOut; - friend class DominatorTreeBase; - friend class PostDominatorTree; + template friend class DominatorTreeBase; + friend struct PostDominatorTree; public: - typedef std::vector::iterator iterator; - typedef std::vector::const_iterator const_iterator; + 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(); } - BasicBlock *getBlock() const { return TheBB; } - DomTreeNode *getIDom() const { return IDom; } - const std::vector &getChildren() const { return Children; } + NodeT *getBlock() const { return TheBB; } + DomTreeNodeBase *getIDom() const { return IDom; } + const std::vector*> &getChildren() const { + return Children; + } - DomTreeNode(BasicBlock *BB, DomTreeNode *iDom) + DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } - DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; } - void setIDom(DomTreeNode *NewIDom); - + + DomTreeNodeBase *addChild(DomTreeNodeBase *C) { + Children.push_back(C); + return C; + } + + void setIDom(DomTreeNodeBase *NewIDom) { + assert(IDom && "No immediate dominator?"); + if (IDom != NewIDom) { + typename std::vector*>::iterator I = + std::find(IDom->Children.begin(), IDom->Children.end(), this); + assert(I != IDom->Children.end() && + "Not in immediate dominator children set!"); + // I am no longer your child... + IDom->Children.erase(I); + + // Switch to new dominator + IDom = NewIDom; + IDom->Children.push_back(this); + } + } /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do /// not call them. @@ -93,21 +125,53 @@ public: private: // Return true if this node is dominated by other. Use this only if DFS info // is valid. - bool DominatedBy(const DomTreeNode *other) const { + bool DominatedBy(const DomTreeNodeBase *other) const { return this->DFSNumIn >= other->DFSNumIn && this->DFSNumOut <= other->DFSNumOut; } }; +EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); +EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); + +template +static std::ostream &operator<<(std::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, + unsigned Lev) { + o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; + for (typename DomTreeNodeBase::const_iterator I = N->begin(), + E = N->end(); I != E; ++I) + PrintDomTree(*I, o, Lev+1); +} + +typedef DomTreeNodeBase DomTreeNode; + //===----------------------------------------------------------------------===// /// DominatorTree - Calculate the immediate dominator tree for a function. /// -class DominatorTreeBase : public DominatorBase { + +template +void Calculate(DominatorTreeBase::NodeType>& DT, + FuncT& F); + +template +class DominatorTreeBase : public DominatorBase { protected: - void reset(); - typedef DenseMap DomTreeNodeMapType; + typedef DenseMap*> DomTreeNodeMapType; DomTreeNodeMapType DomTreeNodes; - DomTreeNode *RootNode; + DomTreeNodeBase *RootNode; bool DFSInfoValid; unsigned int SlowQueries; @@ -115,40 +179,137 @@ protected: struct InfoRec { unsigned Semi; unsigned Size; - BasicBlock *Label, *Parent, *Child, *Ancestor; + NodeT *Label, *Parent, *Child, *Ancestor; - std::vector Bucket; + std::vector Bucket; InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0) {} }; - DenseMap IDoms; + DenseMap IDoms; // Vertex - Map the DFS number to the BasicBlock* - std::vector Vertex; + std::vector Vertex; // Info - Collection of information used during the computation of idoms. - DenseMap Info; + DenseMap Info; + + void reset() { + for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), + E = DomTreeNodes.end(); I != E; ++I) + delete I->second; + DomTreeNodes.clear(); + IDoms.clear(); + this->Roots.clear(); + 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!"); + 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); + + assert(!PredBlocks.empty() && "No predblocks??"); + + // The newly inserted basic block will dominate existing basic blocks iff the + // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate + // the non-pred blocks, then they all must be the same block! + // + bool NewBBDominatesNewBBSucc = true; + { + typename GraphT::NodeType* OnePred = PredBlocks[0]; + unsigned i = 1, e = PredBlocks.size(); + for (i = 1; !DT.isReachableFromEntry(OnePred); ++i) { + assert(i != e && "Didn't find reachable pred?"); + OnePred = PredBlocks[i]; + } + + for (; i != e; ++i) + if (PredBlocks[i] != OnePred && DT.isReachableFromEntry(OnePred)) { + NewBBDominatesNewBBSucc = false; + break; + } + + if (NewBBDominatesNewBBSucc) + for (typename GraphTraits >::ChildIteratorType PI = + GraphTraits >::child_begin(NewBBSucc), + E = GraphTraits >::child_end(NewBBSucc); PI != E; ++PI) + if (*PI != NewBB && !DT.dominates(NewBBSucc, *PI)) { + NewBBDominatesNewBBSucc = false; + break; + } + } + + // The other scenario where the new block can dominate its successors are when + // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc + // already. + if (!NewBBDominatesNewBBSucc) { + 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)) { + NewBBDominatesNewBBSucc = false; + break; + } + } + + // Find NewBB's immediate dominator and create new dominator tree node for + // NewBB. + NodeT *NewBBIDom = 0; + unsigned i = 0; + for (i = 0; i < PredBlocks.size(); ++i) + if (DT.isReachableFromEntry(PredBlocks[i])) { + NewBBIDom = PredBlocks[i]; + break; + } + assert(i != PredBlocks.size() && "No reachable preds?"); + 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); + + // If NewBB strictly dominates other blocks, then it is now the immediate + // dominator of NewBBSucc. Update the dominator tree as appropriate. + if (NewBBDominatesNewBBSucc) { + DomTreeNodeBase *NewBBSuccNode = DT.getNode(NewBBSucc); + DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); + } + } public: - DominatorTreeBase(intptr_t ID, bool isPostDom) - : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {} - ~DominatorTreeBase() { reset(); } + DominatorTreeBase(bool isPostDom) + : DominatorBase(isPostDom), DFSInfoValid(false), SlowQueries(0) {} + virtual ~DominatorTreeBase() { reset(); } + + // FIXME: Should remove this + virtual bool runOnFunction(Function &F) { return false; } virtual void releaseMemory() { reset(); } /// 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 { - DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB); + inline DomTreeNodeBase *getNode(NodeT *BB) const { + typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB); return I != DomTreeNodes.end() ? I->second : 0; } - inline DomTreeNode *operator[](BasicBlock *BB) const { - return getNode(BB); - } - /// getRootNode - This returns the entry node for the CFG of the function. If /// this tree represents the post-dominance relations for a function, however, /// this root may be a node with the block == NULL. This is the case when @@ -156,24 +317,25 @@ public: /// post-dominance information must be capable of dealing with this /// possibility. /// - DomTreeNode *getRootNode() { return RootNode; } - const DomTreeNode *getRootNode() const { return RootNode; } + DomTreeNodeBase *getRootNode() { return RootNode; } + const DomTreeNodeBase *getRootNode() const { return RootNode; } /// properlyDominates - Returns true iff this dominates N and this != N. /// Note that this is not a constant time operation! /// - bool properlyDominates(const DomTreeNode *A, DomTreeNode *B) const { + bool properlyDominates(const DomTreeNodeBase *A, + DomTreeNodeBase *B) const { if (A == 0 || B == 0) return false; return dominatedBySlowTreeWalk(A, B); } - inline bool properlyDominates(BasicBlock *A, BasicBlock *B) { + inline bool properlyDominates(NodeT *A, NodeT *B) { return properlyDominates(getNode(A), getNode(B)); } - bool dominatedBySlowTreeWalk(const DomTreeNode *A, - const DomTreeNode *B) const { - const DomTreeNode *IDom; + bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, + const DomTreeNodeBase *B) const { + const DomTreeNodeBase *IDom; if (A == 0 || B == 0) return false; while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) B = IDom; // Walk up the tree @@ -183,12 +345,17 @@ public: /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. - const bool isReachableFromEntry(BasicBlock* A); + bool isReachableFromEntry(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 DomTreeNode *A, DomTreeNode *B) { + inline bool dominates(const DomTreeNodeBase *A, + DomTreeNodeBase *B) { if (B == A) return true; // A node trivially dominates itself. @@ -209,20 +376,63 @@ public: return dominatedBySlowTreeWalk(A, B); } - inline bool dominates(BasicBlock *A, BasicBlock *B) { + inline bool dominates(NodeT *A, NodeT *B) { if (A == B) return true; return dominates(getNode(A), getNode(B)); } + + NodeT *getRoot() const { + assert(this->Roots.size() == 1 && "Should always have entry node!"); + return this->Roots[0]; + } /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. - BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B); + 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; + + // If B dominates A then B is nearest common dominator. + if (dominates(B, A)) + return B; + + // If A dominates B then A is nearest common dominator. + if (dominates(A, B)) + return A; + + DomTreeNodeBase *NodeA = getNode(A); + DomTreeNodeBase *NodeB = getNode(B); + + // Collect NodeA dominators set. + SmallPtrSet*, 16> NodeADoms; + NodeADoms.insert(NodeA); + DomTreeNodeBase *IDomA = NodeA->getIDom(); + while (IDomA) { + NodeADoms.insert(IDomA); + IDomA = IDomA->getIDom(); + } - // 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); + // Walk NodeB immediate dominators chain and find common dominator node. + DomTreeNodeBase *IDomB = NodeB->getIDom(); + while(IDomB) { + if (NodeADoms.count(IDomB) != 0) + return IDomB->getBlock(); + + IDomB = IDomB->getIDom(); + } + + return NULL; + } //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to @@ -231,62 +441,251 @@ public: /// 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 /// the children list of the immediate dominator. - DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) { + DomTreeNodeBase *addNewBlock(NodeT *BB, NodeT *DomBB) { assert(getNode(BB) == 0 && "Block already in dominator tree!"); - DomTreeNode *IDomNode = getNode(DomBB); + DomTreeNodeBase *IDomNode = getNode(DomBB); assert(IDomNode && "Not immediate dominator specified for block!"); DFSInfoValid = false; return DomTreeNodes[BB] = - IDomNode->addChild(new DomTreeNode(BB, IDomNode)); + IDomNode->addChild(new DomTreeNodeBase(BB, IDomNode)); } /// changeImmediateDominator - This method is used to update the dominator /// tree information when a node's immediate dominator changes. /// - void changeImmediateDominator(DomTreeNode *N, DomTreeNode *NewIDom) { + void changeImmediateDominator(DomTreeNodeBase *N, + DomTreeNodeBase *NewIDom) { assert(N && NewIDom && "Cannot change null node pointers!"); DFSInfoValid = false; N->setIDom(NewIDom); } - void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB) { + void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { 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 + /// 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."); + + // Remove node from immediate dominator's children list. + DomTreeNodeBase *IDom = Node->getIDom(); + if (IDom) { + typename std::vector*>::iterator I = + std::find(IDom->Children.begin(), IDom->Children.end(), Node); + assert(I != IDom->Children.end() && + "Not in immediate dominator children set!"); + // I am no longer your child... + IDom->Children.erase(I); + } + + DomTreeNodes.erase(BB); + delete Node; + } + /// removeNode - Removes a node from the dominator tree. Block must not /// dominate any other blocks. Invalidates any node pointing to removed /// block. - void removeNode(BasicBlock *BB) { + void removeNode(NodeT *BB) { 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) { + if (this->IsPostDominators) + this->Split, GraphTraits > >(*this, NewBB); + else + this->Split >(*this, NewBB); + } /// print - Convert to human readable form /// - virtual void print(std::ostream &OS, const Module* = 0) const; + virtual void print(std::ostream &o, const Module* ) const { + o << "=============================--------------------------------\n"; + o << "Inorder Dominator Tree: "; + if (this->DFSInfoValid) + o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; + o << "\n"; + + PrintDomTree(getRootNode(), o, 1); + } + void print(std::ostream *OS, const Module* M = 0) const { if (OS) print(*OS, M); } - virtual void dump(); + + virtual void dump() { + print(llvm::cerr); + } protected: + template + friend void Compress(DominatorTreeBase& DT, + typename GraphT::NodeType* VIn); + + template + friend typename GraphT::NodeType* Eval( + DominatorTreeBase& DT, + typename GraphT::NodeType* V); + + template + friend void Link(DominatorTreeBase& DT, + typename GraphT::NodeType* V, + 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(); + void updateDFSNumbers() { + unsigned DFSNum = 0; + + SmallVector*, + typename DomTreeNodeBase::iterator>, 32> WorkStack; + + for (unsigned i = 0, e = 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++; + } + } + } + + SlowQueries = 0; + DFSInfoValid = true; + } + + DomTreeNodeBase *getNodeForBlock(NodeT *BB) { + if (DomTreeNodeBase *BBNode = this->DomTreeNodes[BB]) + return BBNode; + + // Haven't calculated this node yet? Get or calculate the node for the + // immediate dominator. + NodeT *IDom = getIDom(BB); + DomTreeNodeBase *IDomNode = getNodeForBlock(IDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + 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; + } + + inline void addRoot(NodeT* BB) { + // Unreachable block is not a root node. + if (!isa(&BB->back())) + this->Roots.push_back(BB); + } + +public: + /// recalculate - compute a dominator tree for the given function + template + void recalculate(FT& F) { + 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); + + 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) + addRoot(I); + + // Prepopulate maps so that we don't get iterator invalidation issues later. + this->IDoms[I] = 0; + this->DomTreeNodes[I] = 0; + } + + this->Vertex.push_back(0); + + Calculate >(*this, F); + } + } }; +EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase); + //===------------------------------------- /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to /// compute a normal dominator tree. /// -class DominatorTree : public DominatorTreeBase { +class DominatorTree : public FunctionPass { public: static char ID; // Pass ID, replacement for typeid - DominatorTree() : DominatorTreeBase(intptr_t(&ID), false) {} + DominatorTreeBase* DT; - BasicBlock *getRoot() const { - assert(Roots.size() == 1 && "Should always have entry node!"); - return Roots[0]; + DominatorTree() : FunctionPass(intptr_t(&ID)) { + 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 + /// 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(); } virtual bool runOnFunction(Function &F); @@ -294,21 +693,102 @@ public: virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } + + inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { + return DT->dominates(A, B); + } + + inline bool dominates(BasicBlock* A, 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); - /// splitBlock - /// BB is split and now it has one successor. Update dominator tree to - /// reflect this change. - void splitBlock(BasicBlock *BB); -private: - void calculate(Function& F); - DomTreeNode *getNodeForBlock(BasicBlock *BB); - unsigned DFSPass(BasicBlock *V, unsigned N); - void Compress(BasicBlock *V); - BasicBlock *Eval(BasicBlock *v); - void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo); - inline BasicBlock *getIDom(BasicBlock *BB) const { - DenseMap::const_iterator I = IDoms.find(BB); - return I != IDoms.end() ? I->second : 0; + // It is not possible to determine dominance between two PHI nodes + // based on their ordering. + if (isa(A) && isa(B)) + return false; + + // 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 { + return DT->properlyDominates(A, B); + } + + inline bool properlyDominates(BasicBlock* A, 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 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 + /// 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 + /// 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); + } + + + virtual void releaseMemory() { + DT->releaseMemory(); + } + + virtual void print(std::ostream &OS, const Module* M= 0) const { + DT->print(OS, M); } }; @@ -316,7 +796,7 @@ private: /// 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; @@ -332,7 +812,7 @@ template <> struct GraphTraits { }; template <> struct GraphTraits - : public GraphTraits { + : public GraphTraits { static NodeType *getEntryNode(DominatorTree *DT) { return DT->getRootNode(); } @@ -343,15 +823,28 @@ template <> struct GraphTraits /// DominanceFrontierBase - Common base class for computing forward and inverse /// dominance frontiers for a function. /// -class DominanceFrontierBase : public DominatorBase { +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(intptr_t ID, bool isPostDom) - : DominatorBase(ID, 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(); } @@ -370,6 +863,14 @@ public: 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); + } + void addToFrontier(iterator I, BasicBlock *Node) { assert(I != end() && "BB is not in DominanceFrontier!"); I->second.insert(Node); @@ -424,6 +925,26 @@ public: /// 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); + 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); + } + private: const DomSetType &calculate(const DominatorTree &DT, const DomTreeNode *Node);