reimplement dfs number computation to be significantly faster. This speeds up

natural loop canonicalization (which does many cfg xforms) by 4.3x, for 
example.  This also fixes a bug in postdom dfnumber computation.


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

1 files changed, 3 insertions, 9 deletions

diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index 4622441e06..69e9cbe26b 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -193,15 +193,9 @@ void PostDominatorTree::calculate(Function &F) {
   Info.clear();
   std::vector<BasicBlock*>().swap(Vertex);
 
-  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)->getIDom())
-        getNodeForBlock(*I)->assignDFSNumber(dfsnum);
-    }
-  DFSInfoValid = true;
+  // Start out with the DFS numbers being invalid.  Let them be computed if
+  // demanded.
+  DFSInfoValid = false;
 }