Have PostDomTree use the newly templated DFSPass.

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

6 files changed, 9 insertions, 58 deletions

diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
index 66ac2b7..cfd2d74 100644
--- a/include/llvm/Analysis/DominatorInternals.h
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -21,7 +21,8 @@
 namespace llvm {
 
 template<class GraphT>
-unsigned DFSPass(DominatorTree& DT, typename GraphT::NodeType* V, unsigned N) {
+unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V,
+                 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
   // documentation purposes.
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index e8ed92c..b14e619 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -280,6 +280,10 @@ protected:
   friend void Link(DominatorTreeBase& DT, BasicBlock *V,
                    BasicBlock *W, InfoRec &WInfo);
   
+  template<class GraphT> friend unsigned DFSPass(DominatorTreeBase& DT,
+                                                 typename GraphT::NodeType* V,
+                                                 unsigned N);
+  
   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
   /// dominator tree in dfs order.
   void updateDFSNumbers();
@@ -319,9 +323,6 @@ public:
 
 private:
   friend void DTcalculate(DominatorTree& DT, Function& F);
-  
-  template<class GraphT> friend
-  unsigned DFSPass(DominatorTree& DT, typename GraphT::NodeType* V, unsigned N);
 };
 
 //===-------------------------------------
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
index b2a37ff..d87f604 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -37,10 +37,7 @@ struct PostDominatorTree : public DominatorTreeBase {
     AU.setPreservesAll();
   }
 private:
-  unsigned DFSPass(BasicBlock *V, unsigned N);
   friend void PDTcalculate(PostDominatorTree& PDT, Function &F);
-  friend void PDTLink(PostDominatorTree& PDT,BasicBlock *V,
-                      BasicBlock *W, InfoRec &WInfo);
 };
 
 
diff --git a/lib/Analysis/PostDominatorCalculation.h b/lib/Analysis/PostDominatorCalculation.h
index 550422d..5e2b3c8 100644
--- a/lib/Analysis/PostDominatorCalculation.h
+++ b/lib/Analysis/PostDominatorCalculation.h
@@ -13,7 +13,9 @@
 #ifndef LLVM_ANALYSIS_POST_DOMINATOR_CALCULATION_H
 #define LLVM_ANALYSIS_POST_DOMINATOR_CALCULATION_H
 
+#include "llvm/Analysis/Dominators.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/DominatorInternals.h"
 
 namespace llvm {
 
@@ -40,7 +42,7 @@ void PDTcalculate(PostDominatorTree& PDT, Function &F) {
   // in later stages of the algorithm.
   unsigned N = 0;
   for (unsigned i = 0, e = PDT.Roots.size(); i != e; ++i)
-    N = PDT.DFSPass(PDT.Roots[i], N);
+    N = DFSPass<GraphTraits<Inverse<BasicBlock*> > >(PDT, PDT.Roots[i], N);
   
   for (unsigned i = N; i >= 2; --i) {
     BasicBlock *W = PDT.Vertex[i];
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index b8d833e..cd29749 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -28,51 +28,6 @@ char PostDominanceFrontier::ID = 0;
 static RegisterPass<PostDominatorTree>
 F("postdomtree", "Post-Dominator Tree Construction", true);
 
-unsigned PostDominatorTree::DFSPass(BasicBlock *V, unsigned N) {
-  std::vector<BasicBlock *> workStack;
-  SmallPtrSet<BasicBlock *, 32> Visited;
-  workStack.push_back(V);
-
-  do {
-    BasicBlock *currentBB = workStack.back();
-    InfoRec &CurVInfo = Info[currentBB];
-
-    // Visit each block only once.
-    if (Visited.insert(currentBB)) {
-      CurVInfo.Semi = ++N;
-      CurVInfo.Label = currentBB;
-      
-      Vertex.push_back(currentBB);  // Vertex[n] = current;
-      // Info[currentBB].Ancestor = 0;     
-      // Ancestor[n] = 0
-      // Child[currentBB] = 0;
-      CurVInfo.Size = 1;       // Size[currentBB] = 1
-    }
-
-    // Visit children
-    bool visitChild = false;
-    for (pred_iterator PI = pred_begin(currentBB), PE = pred_end(currentBB); 
-         PI != PE && !visitChild; ++PI) {
-      InfoRec &SuccVInfo = Info[*PI];
-      if (SuccVInfo.Semi == 0) {
-        SuccVInfo.Parent = currentBB;
-        if (!Visited.count(*PI)) {
-          workStack.push_back(*PI);   
-          visitChild = true;
-        }
-      }
-    }
-
-    // If all children are visited or if this block has no child then pop this
-    // block out of workStack.
-    if (!visitChild)
-      workStack.pop_back();
-
-  } while (!workStack.empty());
-
-  return N;
-}
-
 //===----------------------------------------------------------------------===//
 //  PostDominanceFrontier Implementation
 //===----------------------------------------------------------------------===//
diff --git a/lib/VMCore/DominatorInternals.cpp b/lib/VMCore/DominatorInternals.cpp
index fbbac9f..abb87cd 100644
--- a/lib/VMCore/DominatorInternals.cpp
+++ b/lib/VMCore/DominatorInternals.cpp
@@ -7,9 +7,6 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LIB_LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
-#define LIB_LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
-
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
@@ -141,5 +138,3 @@ void Link(DominatorTreeBase& DT, BasicBlock *V, BasicBlock *W,
 }
 
 }
-
-#endif