Remove ImmediateDominator analysis. The same information can be obtained from DomTree. A lot of code for

constructing ImmediateDominator is now folded into DomTree construction.

This is part of the ongoing work for PR217.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@36063 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 88 insertions, 186 deletions

diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index 24399405fc..7351ed7a6a 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -19,13 +19,13 @@
 using namespace llvm;
 
 //===----------------------------------------------------------------------===//
-//  ImmediatePostDominators Implementation
+//  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
-static RegisterPass<ImmediatePostDominators>
-D("postidom", "Immediate Post-Dominators Construction", true);
+static RegisterPass<PostDominatorTree>
+F("postdomtree", "Post-Dominator Tree Construction", true);
 
-unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
+unsigned PostDominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
                                           unsigned N) {
   std::vector<std::pair<BasicBlock *, InfoRec *> > workStack;
   std::set<BasicBlock *> visited;
@@ -73,7 +73,7 @@ unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
   return N;
 }
 
-void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
+void PostDominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) {
   BasicBlock *VAncestor = VInfo.Ancestor;
   InfoRec &VAInfo = Info[VAncestor];
   if (VAInfo.Ancestor == 0)
@@ -89,7 +89,7 @@ void ImmediatePostDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
   VInfo.Ancestor = VAInfo.Ancestor;
 }
 
-BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) {
+BasicBlock *PostDominatorTree::Eval(BasicBlock *V) {
   InfoRec &VInfo = Info[V];
 
   // Higher-complexity but faster implementation
@@ -99,16 +99,13 @@ BasicBlock *ImmediatePostDominators::Eval(BasicBlock *V) {
   return VInfo.Label;
 }
 
-void ImmediatePostDominators::Link(BasicBlock *V, BasicBlock *W, 
+void PostDominatorTree::Link(BasicBlock *V, BasicBlock *W, 
                                    InfoRec &WInfo) {
   // Higher-complexity but faster implementation
   WInfo.Ancestor = V;
 }
 
-bool ImmediatePostDominators::runOnFunction(Function &F) {
-  IDoms.clear();     // Reset from the last time we were run...
-  Roots.clear();
-
+void PostDominatorTree::calculate(Function &F) {
   // Step #0: Scan the function looking for the root nodes of the post-dominance
   // relationships.  These blocks, which have no successors, end with return and
   // unwind instructions.
@@ -159,35 +156,6 @@ bool ImmediatePostDominators::runOnFunction(Function &F) {
       WIDom = IDoms[WIDom];
   }
   
-  // Free temporary memory used to construct idom's
-  Info.clear();
-  std::vector<BasicBlock*>().swap(Vertex);
-  
-  return false;
-}
-
-//===----------------------------------------------------------------------===//
-//  PostDominatorTree Implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<PostDominatorTree>
-F("postdomtree", "Post-Dominator Tree Construction", true);
-
-DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
-  Node *&BBNode = Nodes[BB];
-  if (BBNode) return BBNode;
-  
-  // Haven't calculated this node yet?  Get or calculate the node for the
-  // immediate postdominator.
-  BasicBlock *IPDom = getAnalysis<ImmediatePostDominators>()[BB];
-  Node *IPDomNode = getNodeForBlock(IPDom);
-  
-  // Add a new tree node for this BasicBlock, and link it as a child of
-  // IDomNode
-  return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode));
-}
-
-void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) {
   if (Roots.empty()) return;
 
   // Add a node for the root.  This node might be the actual root, if there is
@@ -196,10 +164,9 @@ void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) {
   BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0;
   Nodes[Root] = RootNode = new Node(Root, 0);
   
-  Function *F = Roots[0]->getParent();
   // Loop over all of the reachable blocks in the function...
-  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
-    if (BasicBlock *ImmPostDom = IPD.get(I)) {  // Reachable block.
+  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+    if (BasicBlock *ImmPostDom = getIDom(I)) {  // Reachable block.
       Node *&BBNode = Nodes[I];
       if (!BBNode) {  // Haven't calculated this node yet?
                       // Get or calculate the node for the immediate dominator
@@ -210,6 +177,26 @@ void PostDominatorTree::calculate(const ImmediatePostDominators &IPD) {
         BBNode = IPDomNode->addChild(new Node(I, IPDomNode));
       }
     }
+
+  // Free temporary memory used to construct idom's
+  IDoms.clear();
+  Info.clear();
+  std::vector<BasicBlock*>().swap(Vertex);
+}
+
+
+DominatorTreeBase::Node *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
+  Node *&BBNode = Nodes[BB];
+  if (BBNode) return BBNode;
+  
+  // Haven't calculated this node yet?  Get or calculate the node for the
+  // immediate postdominator.
+  BasicBlock *IPDom = getIDom(BB);
+  Node *IPDomNode = getNodeForBlock(IPDom);
+  
+  // Add a new tree node for this BasicBlock, and link it as a child of
+  // IDomNode
+  return BBNode = IPDomNode->addChild(new Node(BB, IPDomNode));
 }
 
 //===----------------------------------------------------------------------===//
@@ -225,13 +212,15 @@ ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) {
 
   // Haven't calculated this node yet?  Get or calculate the node for the
   // immediate dominator.
-  BasicBlock *IDom = getAnalysis<ImmediatePostDominators>()[BB];
+  PostDominatorTree::Node *node = getAnalysis<PostDominatorTree>().getNode(BB);
 
   // If we are unreachable, we may not have an immediate dominator.
-  if (!IDom)
+  if (!node)
+		return 0;
+	else if (!node->getIDom())
     return BBNode = new ETNode(BB);
   else {
-    ETNode *IDomNode = getNodeForBlock(IDom);
+    ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock());
     
     // Add a new tree node for this BasicBlock, and link it as a child of
     // IDomNode
@@ -241,7 +230,7 @@ ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) {
   }
 }
 
-void PostETForest::calculate(const ImmediatePostDominators &ID) {
+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
 
@@ -253,9 +242,9 @@ void PostETForest::calculate(const ImmediatePostDominators &ID) {
     ETNode *&BBNode = Nodes[BB];
     if (!BBNode) {  
       ETNode *IDomNode =  NULL;
-
-      if (ID.get(BB))
-        IDomNode = getNodeForBlock(ID.get(BB));
+			PostDominatorTree::Node *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.
diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 332ddfa488..38cfd91fe1 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -154,7 +154,6 @@ namespace {
       AU.addPreservedID(LoopSimplifyID);
       AU.addPreserved<LoopInfo>();
       AU.addPreserved<ETForest>();
-      AU.addPreserved<ImmediateDominators>();
       AU.addPreserved<DominanceFrontier>();
       AU.addPreserved<DominatorTree>();
 
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 2f91e57590..2cf2ecd3e9 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -38,7 +38,6 @@ namespace {
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.addPreserved<ETForest>();
-      AU.addPreserved<ImmediateDominators>();
       AU.addPreserved<DominatorTree>();
       AU.addPreserved<DominanceFrontier>();
       AU.addPreserved<LoopInfo>();
@@ -196,29 +195,6 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P,
     if (NewBBDominatesDestBB)
       EF->setImmediateDominator(DestBB, NewBB);
   }
-
-  // Should we update ImmediateDominator information?
-  if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) {
-    // Only do this if TIBB is reachable.
-    if (ID->get(TIBB) || &TIBB->getParent()->getEntryBlock() == TIBB) {
-      // TIBB is the new immediate dominator for NewBB.
-      ID->addNewBlock(NewBB, TIBB);
-      
-      // If NewBBDominatesDestBB hasn't been computed yet, do so with ID.
-      if (!OtherPreds.empty()) {
-        while (!OtherPreds.empty() && NewBBDominatesDestBB) {
-          NewBBDominatesDestBB = ID->dominates(DestBB, OtherPreds.back());
-          OtherPreds.pop_back();
-        }
-        OtherPreds.clear();
-      }
-      
-      // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it
-      // doesn't dominate anything.
-      if (NewBBDominatesDestBB)
-        ID->setImmediateDominator(DestBB, NewBB);
-    }
-  }
   
   // Should we update DominatorTree information?
   if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) {
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 75991688b1..7d34b95cba 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -68,7 +68,6 @@ namespace {
       AU.addRequired<ETForest>();
 
       AU.addPreserved<LoopInfo>();
-      AU.addPreserved<ImmediateDominators>();
       AU.addPreserved<ETForest>();
       AU.addPreserved<DominatorTree>();
       AU.addPreserved<DominanceFrontier>();
@@ -749,31 +748,6 @@ void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB,
   }
 
   BasicBlock *NewBBIDom = 0;
-  
-  // Update immediate dominator information if we have it.
-  if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) {
-    unsigned i = 0;
-    for (i = 0; i < PredBlocks.size(); ++i)
-      if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i])) {
-        NewBBIDom = PredBlocks[i];
-        break;
-      }
-    assert(i != PredBlocks.size() && "No reachable preds?");
-    for (i = i + 1; i < PredBlocks.size(); ++i) {
-      if (ETF.dominates(&PredBlocks[i]->getParent()->getEntryBlock(), PredBlocks[i]))
-        NewBBIDom = ETF.nearestCommonDominator(NewBBIDom, PredBlocks[i]);
-    }
-    assert(NewBBIDom && "No immediate dominator found??");
-  
-    // Set the immediate dominator now...
-    ID->addNewBlock(NewBB, NewBBIDom);
-
-    // If NewBB strictly dominates other blocks, we need to update their idom's
-    // now.  The only block that need adjustment is the NewBBSucc block, whose
-    // idom should currently be set to PredBlocks[0].
-    if (NewBBDominatesNewBBSucc)
-      ID->setImmediateDominator(NewBBSucc, NewBB);
-  }
 
   // Update DominatorTree information if it is active.
   if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 0959b07b47..9685ed9efa 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -24,11 +24,24 @@
 #include <algorithm>
 using namespace llvm;
 
+namespace llvm {
+static std::ostream &operator<<(std::ostream &o,
+                                const std::set<BasicBlock*> &BBs) {
+  for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
+       I != E; ++I)
+    if (*I)
+      WriteAsOperand(o, *I, false);
+    else
+      o << " <<exit node>>";
+  return o;
+}
+}
+
 //===----------------------------------------------------------------------===//
-//  ImmediateDominators Implementation
+//  DominatorTree Implementation
 //===----------------------------------------------------------------------===//
 //
-// Immediate Dominators construction - This pass constructs immediate dominator
+// DominatorTree construction - This pass constructs immediate dominator
 // information for a flow-graph based on the algorithm described in this
 // document:
 //
@@ -45,10 +58,10 @@ using namespace llvm;
 //
 //===----------------------------------------------------------------------===//
 
-static RegisterPass<ImmediateDominators>
-C("idom", "Immediate Dominators Construction", true);
+static RegisterPass<DominatorTree>
+E("domtree", "Dominator Tree Construction", true);
 
-unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
+unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo,
                                       unsigned N) {
   // This is more understandable as a recursive algorithm, but we can't use the
   // recursive algorithm due to stack depth issues.  Keep it here for
@@ -110,7 +123,7 @@ unsigned ImmediateDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
   return N;
 }
 
-void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
+void DominatorTree::Compress(BasicBlock *V, InfoRec &VInfo) {
   BasicBlock *VAncestor = VInfo.Ancestor;
   InfoRec &VAInfo = Info[VAncestor];
   if (VAInfo.Ancestor == 0)
@@ -126,7 +139,7 @@ void ImmediateDominators::Compress(BasicBlock *V, InfoRec &VInfo) {
   VInfo.Ancestor = VAInfo.Ancestor;
 }
 
-BasicBlock *ImmediateDominators::Eval(BasicBlock *V) {
+BasicBlock *DominatorTree::Eval(BasicBlock *V) {
   InfoRec &VInfo = Info[V];
 #if !BALANCE_IDOM_TREE
   // Higher-complexity but faster implementation
@@ -149,7 +162,7 @@ BasicBlock *ImmediateDominators::Eval(BasicBlock *V) {
 #endif
 }
 
-void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
+void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
 #if !BALANCE_IDOM_TREE
   // Higher-complexity but faster implementation
   WInfo.Ancestor = V;
@@ -196,13 +209,10 @@ void ImmediateDominators::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
 #endif
 }
 
-
-
-bool ImmediateDominators::runOnFunction(Function &F) {
-  IDoms.clear();     // Reset from the last time we were run...
-  BasicBlock *Root = &F.getEntryBlock();
-  Roots.clear();
-  Roots.push_back(Root);
+void DominatorTree::calculate(Function& F) {
+	BasicBlock* Root = Roots[0];
+	
+  Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
 
   Vertex.push_back(0);
 
@@ -247,65 +257,34 @@ bool ImmediateDominators::runOnFunction(Function &F) {
       WIDom = IDoms[WIDom];
   }
 
+  // Loop over all of the reachable blocks in the function...
+  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
+    if (BasicBlock *ImmDom = getIDom(I)) {  // Reachable block.
+			Node *&BBNode = Nodes[I];
+      if (!BBNode) {  // Haven't calculated this node yet?
+        // Get or calculate the node for the immediate dominator
+        Node *IDomNode = getNodeForBlock(ImmDom);
+
+        // Add a new tree node for this BasicBlock, and link it as a child of
+        // IDomNode
+        BBNode = IDomNode->addChild(new Node(I, IDomNode));
+      }
+    }
+
   // Free temporary memory used to construct idom's
   Info.clear();
+	IDoms.clear();
   std::vector<BasicBlock*>().swap(Vertex);
-
-  return false;
 }
 
-/// dominates - Return true if A dominates B.
-///
-bool ImmediateDominatorsBase::dominates(BasicBlock *A, BasicBlock *B) const {
-  assert(A && B && "Null pointers?");
-  
-  // Walk up the dominator tree from B to determine if A dom B.
-  while (A != B && B)
-    B = get(B);
-  return A == B;
-}
-
-void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const {
-  Function *F = getRoots()[0]->getParent();
-  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) {
-    o << "  Immediate Dominator For Basic Block:";
-    WriteAsOperand(o, I, false);
-    o << " is:";
-    if (BasicBlock *ID = get(I))
-      WriteAsOperand(o, ID, false);
-    else
-      o << " <<exit node>>";
-    o << "\n";
-  }
-  o << "\n";
-}
-
-namespace llvm {
-static std::ostream &operator<<(std::ostream &o,
-                                const std::set<BasicBlock*> &BBs) {
-  for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
-       I != E; ++I)
-    if (*I)
-      WriteAsOperand(o, *I, false);
-    else
-      o << " <<exit node>>";
-  return o;
-}
-}
-
-//===----------------------------------------------------------------------===//
-//  DominatorTree Implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<DominatorTree>
-E("domtree", "Dominator Tree Construction", true);
-
 // DominatorTreeBase::reset - Free all of the tree node memory.
 //
 void DominatorTreeBase::reset() {
   for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
     delete I->second;
   Nodes.clear();
+	IDoms.clear();
+	Roots.clear();
   RootNode = 0;
 }
 
@@ -331,7 +310,7 @@ DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) {
 
   // Haven't calculated this node yet?  Get or calculate the node for the
   // immediate dominator.
-  BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
+  BasicBlock *IDom = getIDom(BB);
   Node *IDomNode = getNodeForBlock(IDom);
 
   // Add a new tree node for this BasicBlock, and link it as a child of
@@ -339,27 +318,6 @@ DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) {
   return BBNode = IDomNode->addChild(new Node(BB, IDomNode));
 }
 
-void DominatorTree::calculate(const ImmediateDominators &ID) {
-  assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
-  BasicBlock *Root = Roots[0];
-  Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
-
-  Function *F = Root->getParent();
-  // Loop over all of the reachable blocks in the function...
-  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
-    if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
-      Node *&BBNode = Nodes[I];
-      if (!BBNode) {  // Haven't calculated this node yet?
-        // Get or calculate the node for the immediate dominator
-        Node *IDomNode = getNodeForBlock(ImmDom);
-
-        // Add a new tree node for this BasicBlock, and link it as a child of
-        // IDomNode
-        BBNode = IDomNode->addChild(new Node(I, IDomNode));
-      }
-    }
-}
-
 static std::ostream &operator<<(std::ostream &o,
                                 const DominatorTreeBase::Node *Node) {
   if (Node->getBlock())
@@ -383,6 +341,12 @@ void DominatorTreeBase::print(std::ostream &o, const Module* ) const {
   PrintDomTree(getRootNode(), o, 1);
 }
 
+bool DominatorTree::runOnFunction(Function &F) {
+  reset();     // Reset from the last time we were run...
+	Roots.push_back(&F.getEntryBlock());
+  calculate(F);
+  return false;
+}
 
 //===----------------------------------------------------------------------===//
 //  DominanceFrontier Implementation