From 4d42dea25397f2f822a93edfe9930b36ea85a7e7 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Tue, 12 Jun 2007 00:54:38 +0000 Subject: Break DominatorTree from ETNode. Remove unused PostETForest. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37551 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/Dominators.h | 34 ++------------ include/llvm/Analysis/PostDominators.h | 24 ---------- lib/Analysis/PostDominators.cpp | 83 ++-------------------------------- lib/VMCore/Dominators.cpp | 22 ++------- 4 files changed, 12 insertions(+), 151 deletions(-) diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index f2d6da5..34d027d 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -63,7 +63,6 @@ public: class DomTreeNode { BasicBlock *TheBB; DomTreeNode *IDom; - ETNode *ETN; std::vector Children; int DFSNumIn, DFSNumOut; @@ -78,14 +77,10 @@ public: inline BasicBlock *getBlock() const { return TheBB; } inline DomTreeNode *getIDom() const { return IDom; } - inline ETNode *getETNode() const { return ETN; } inline const std::vector &getChildren() const { return Children; } - inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom, ETNode *E) - : TheBB(BB), IDom(iDom), ETN(E), DFSNumIn(-1), DFSNumOut(-1) { - if (IDom) - ETN->setFather(IDom->getETNode()); - } + inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom) + : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; } void setIDom(DomTreeNode *NewIDom); @@ -111,9 +106,6 @@ protected: DomTreeNodeMapType DomTreeNodes; DomTreeNode *RootNode; - typedef std::map ETMapType; - ETMapType ETNodes; - bool DFSInfoValid; unsigned int SlowQueries; // Information record used during immediate dominators computation. @@ -197,17 +189,6 @@ protected: void updateDFSNumbers(); - /// Return the nearest common dominator of A and B. - BasicBlock *nearestCommonDominator(BasicBlock *A, BasicBlock *B) const { - ETNode *NodeA = getNode(A)->getETNode(); - ETNode *NodeB = getNode(B)->getETNode(); - - ETNode *Common = NodeA->NCA(NodeB); - if (!Common) - return NULL; - return Common->getData(); - } - /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. const bool isReachableFromEntry(BasicBlock* A); @@ -222,12 +203,8 @@ protected: if (A == 0 || B == 0) return false; - ETNode *NodeA = A->getETNode(); - ETNode *NodeB = B->getETNode(); - if (DFSInfoValid) return B->DominatedBy(A); - //return NodeB->DominatedBy(NodeA); // If we end up with too many slow queries, just update the // DFS numbers on the theory that we are going to keep querying. @@ -235,9 +212,8 @@ protected: if (SlowQueries > 32) { updateDFSNumbers(); return B->DominatedBy(A); - //return NodeB->DominatedBy(NodeA); } - //return NodeB->DominatedBySlow(NodeA); + return dominatedBySlowTreeWalk(A, B); } @@ -268,10 +244,8 @@ protected: DomTreeNode *IDomNode = getNode(DomBB); assert(IDomNode && "Not immediate dominator specified for block!"); DFSInfoValid = false; - ETNode *E = new ETNode(BB); - ETNodes[BB] = E; return DomTreeNodes[BB] = - IDomNode->addChild(new DomTreeNode(BB, IDomNode, E)); + IDomNode->addChild(new DomTreeNode(BB, IDomNode)); } /// changeImmediateDominator - This method is used to update the dominator diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 6d29c40..091925e 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -51,30 +51,6 @@ private: }; -/// PostETForest Class - Concrete subclass of ETForestBase that is used to -/// compute a forwards post-dominator ET-Forest. -struct PostETForest : public ETForestBase { - static char ID; - PostETForest() : ETForestBase((intptr_t)&ID, true) {} - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); - } - - virtual bool runOnFunction(Function &F) { - reset(); // Reset from the last time we were run... - PostDominatorTree &DT = getAnalysis(); - Roots = DT.getRoots(); - calculate(DT); - return false; - } - - void calculate(const PostDominatorTree &DT); - ETNode *getNodeForBlock(BasicBlock *BB); -}; - - /// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is /// used to compute the a post-dominance frontier. /// diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index c4d42e9..48f7b30 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -24,7 +24,6 @@ using namespace llvm; char PostDominatorTree::ID = 0; char PostDominanceFrontier::ID = 0; -char PostETForest::ID = 0; static RegisterPass F("postdomtree", "Post-Dominator Tree Construction", true); @@ -165,9 +164,7 @@ void PostDominatorTree::calculate(Function &F) { // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) // which postdominates all real exits if there are multiple exit blocks. BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0; - ETNode *ERoot = new ETNode(Root); - ETNodes[Root] = ERoot; - DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0, ERoot); + DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); // Loop over all of the reachable blocks in the function... for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) @@ -179,9 +176,7 @@ void PostDominatorTree::calculate(Function &F) { // Add a new tree node for this BasicBlock, and link it as a child of // IDomNode - ETNode *ET = new ETNode(I); - ETNodes[I] = ET; - DomTreeNode *C = new DomTreeNode(I, IPDomNode, ET); + DomTreeNode *C = new DomTreeNode(I, IPDomNode); DomTreeNodes[I] = C; BBNode = IPDomNode->addChild(C); } @@ -197,8 +192,8 @@ void PostDominatorTree::calculate(Function &F) { for (unsigned i = 0, e = Roots.size(); i != e; ++i) for (idf_iterator I = idf_begin(Roots[i]), E = idf_end(Roots[i]); I != E; ++I) { - if (!getNodeForBlock(*I)->getETNode()->hasFather()) - getNodeForBlock(*I)->getETNode()->assignDFSNumber(dfsnum); + if (!getNodeForBlock(*I)->getIDom()) + getNodeForBlock(*I)->assignDFSNumber(dfsnum); } DFSInfoValid = true; } @@ -215,80 +210,12 @@ DomTreeNode *PostDominatorTree::getNodeForBlock(BasicBlock *BB) { // Add a new tree node for this BasicBlock, and link it as a child of // IDomNode - ETNode *ET = new ETNode(BB); - ETNodes[BB] = ET; - DomTreeNode *C = new DomTreeNode(BB, IPDomNode, ET); + DomTreeNode *C = new DomTreeNode(BB, IPDomNode); DomTreeNodes[BB] = C; return BBNode = IPDomNode->addChild(C); } //===----------------------------------------------------------------------===// -// PostETForest Implementation -//===----------------------------------------------------------------------===// - -static RegisterPass -G("postetforest", "Post-ET-Forest Construction", true); - -ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) { - ETNode *&BBNode = Nodes[BB]; - if (BBNode) return BBNode; - - // Haven't calculated this node yet? Get or calculate the node for the - // immediate dominator. - DomTreeNode *node = getAnalysis().getNode(BB); - - // If we are unreachable, we may not have an immediate dominator. - if (!node) - return 0; - else if (!node->getIDom()) - return BBNode = new ETNode(BB); - else { - ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock()); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - BBNode = new ETNode(BB); - BBNode->setFather(IDomNode); - return BBNode; - } -} - -void PostETForest::calculate(const PostDominatorTree &DT) { - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root - - // Iterate over all nodes in inverse depth first order. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - for (idf_iterator I = idf_begin(Roots[i]), - E = idf_end(Roots[i]); I != E; ++I) { - BasicBlock *BB = *I; - ETNode *&BBNode = Nodes[BB]; - if (!BBNode) { - ETNode *IDomNode = NULL; - DomTreeNode *node = DT.getNode(BB); - if (node && node->getIDom()) - IDomNode = getNodeForBlock(node->getIDom()->getBlock()); - - // Add a new ETNode for this BasicBlock, and set it's parent - // to it's immediate dominator. - BBNode = new ETNode(BB); - if (IDomNode) - BBNode->setFather(IDomNode); - } - } - - int dfsnum = 0; - // Iterate over all nodes in depth first order... - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - for (idf_iterator I = idf_begin(Roots[i]), - E = idf_end(Roots[i]); I != E; ++I) { - if (!getNodeForBlock(*I)->hasFather()) - getNodeForBlock(*I)->assignDFSNumber(dfsnum); - } - DFSInfoValid = true; -} - -//===----------------------------------------------------------------------===// // PostDominanceFrontier Implementation //===----------------------------------------------------------------------===// diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index e6e1ffa..4d125fb 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -235,9 +235,7 @@ void DominatorTree::calculate(Function& F) { BasicBlock* Root = Roots[0]; // Add a node for the root... - ETNode *ERoot = new ETNode(Root); - ETNodes[Root] = ERoot; - DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0, ERoot); + DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); Vertex.push_back(0); @@ -292,9 +290,7 @@ void DominatorTree::calculate(Function& F) { // Add a new tree node for this BasicBlock, and link it as a child of // IDomNode - ETNode *ET = new ETNode(I); - ETNodes[I] = ET; - DomTreeNode *C = new DomTreeNode(I, IDomNode, ET); + DomTreeNode *C = new DomTreeNode(I, IDomNode); DomTreeNodes[I] = C; BBNode = IDomNode->addChild(C); } @@ -320,9 +316,6 @@ void DominatorTreeBase::updateDFSNumbers() if (BBNode) { if (!BBNode->getIDom()) BBNode->assignDFSNumber(dfsnum); - //ETNode *ETN = BBNode->getETNode(); - //if (ETN && !ETN->hasFather()) - // ETN->assignDFSNumber(dfsnum); } } SlowQueries = 0; @@ -472,13 +465,6 @@ void DomTreeNode::setIDom(DomTreeNode *NewIDom) { // Switch to new dominator IDom = NewIDom; IDom->Children.push_back(this); - - if (!ETN->hasFather()) - ETN->setFather(IDom->getETNode()); - else if (ETN->getFather()->getData() != IDom->getBlock()) { - ETN->Split(); - ETN->setFather(IDom->getETNode()); - } } } @@ -493,9 +479,7 @@ DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) { // Add a new tree node for this BasicBlock, and link it as a child of // IDomNode - ETNode *ET = new ETNode(BB); - ETNodes[BB] = ET; - DomTreeNode *C = new DomTreeNode(BB, IDomNode, ET); + DomTreeNode *C = new DomTreeNode(BB, IDomNode); DomTreeNodes[BB] = C; return BBNode = IDomNode->addChild(C); } -- cgit v1.1