Fix a bug in non-local memdep that was causing an infinite loop on 175.vpr.

[oota-llvm.git] / lib / Analysis / PostDominators.cpp

diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index c4d42e9f3c38650bad755c52a55c9b55c1aaf0ab..1188cff0303644ebcb953eca24921a72c54e87c9 100644 (file)
--- 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<PostDominatorTree>
 F("postdomtree", "Post-Dominator Tree Construction", true);
 
@@ -113,8 +112,12 @@ void PostDominatorTree::calculate(Function &F) {
   // relationships.  These blocks, which have no successors, end with return and
   // unwind instructions.
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
-    if (succ_begin(I) == succ_end(I))
-      Roots.push_back(I);
+    if (succ_begin(I) == succ_end(I)) {
+      Instruction *Insn = I->getTerminator();
+      // Unreachable block is not a root node.
+      if (!isa<UnreachableInst>(Insn))
+        Roots.push_back(I);
+    }
   
   Vertex.push_back(0);
   
@@ -165,9 +168,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 +180,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 +196,8 @@ void PostDominatorTree::calculate(Function &F) {
   for (unsigned i = 0, e = Roots.size(); i != e; ++i)
     for (idf_iterator<BasicBlock*> 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,79 +214,11 @@ 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<PostETForest>
-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<PostDominatorTree>().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<BasicBlock*> 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<BasicBlock*> 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
 //===----------------------------------------------------------------------===//