From 3e089ae0b8aa6d9daf0b8ca8f6059422c45936f0 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Wed, 8 Aug 2007 05:51:24 +0000
Subject: [PATCH] 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
---
 include/llvm/Analysis/Dominators.h | 14 +++---
 lib/Analysis/PostDominators.cpp    | 12 ++---
 lib/VMCore/Dominators.cpp          | 73 ++++++++++++++----------------
 3 files changed, 42 insertions(+), 57 deletions(-)

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 7c7c56771ac..a57f17bee1c 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -97,17 +97,12 @@ private:
     return this->DFSNumIn >= other->DFSNumIn &&
       this->DFSNumOut <= other->DFSNumOut;
   }
-
-  /// assignDFSNumber - Assign In and Out numbers while walking dominator tree
-  /// in dfs order.
-  void assignDFSNumber(int num);
 };
 
 //===----------------------------------------------------------------------===//
 /// DominatorTree - Calculate the immediate dominator tree for a function.
 ///
 class DominatorTreeBase : public DominatorBase {
-
 protected:
   void reset();
   typedef DenseMap<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
@@ -135,9 +130,7 @@ protected:
   // Info - Collection of information used during the computation of idoms.
   DenseMap<BasicBlock*, InfoRec> Info;
 
-  void updateDFSNumbers();
-
-  public:
+public:
   DominatorTreeBase(intptr_t ID, bool isPostDom) 
     : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
   ~DominatorTreeBase() { reset(); }
@@ -275,6 +268,11 @@ protected:
     if (OS) print(*OS, M);
   }
   virtual void dump();
+  
+protected:
+  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
+  /// dominator tree in dfs order.
+  void updateDFSNumbers();
 };
 
 //===-------------------------------------
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index 4622441e06b..69e9cbe26b8 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;
 }
 
 
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 95ebca0f5b1..3dc87965873 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -20,6 +20,7 @@
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Instructions.h"
 #include "llvm/Support/Streams.h"
 #include <algorithm>
@@ -383,15 +384,39 @@ void DominatorTree::calculate(Function &F) {
 }
 
 void DominatorTreeBase::updateDFSNumbers() {
-  int dfsnum = 0;
-  // Iterate over all nodes in depth first order.
-  for (unsigned i = 0, e = Roots.size(); i != e; ++i)
-    for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
-           E = df_end(Roots[i]); I != E; ++I) {
-      if (DomTreeNode *BBNode = getNode(*I)) {
-        if (!BBNode->getIDom())
-          BBNode->assignDFSNumber(dfsnum);
+  unsigned DFSNum = 0;
+
+  SmallVector<DomTreeNode *, 32> WorkStack;
+  SmallPtrSet<DomTreeNode *, 32> Visited;
+
+  for (unsigned i = 0, e = Roots.size(); i != e; ++i) {
+    DomTreeNode *ThisRoot = getNode(Roots[i]);
+    WorkStack.push_back(ThisRoot);
+    Visited.insert(ThisRoot);
+    ThisRoot->DFSNumIn = DFSNum++;
+    
+    while (!WorkStack.empty()) {
+      DomTreeNode *Node = WorkStack.back();
+      
+      bool MustVisitAChild = false;
+      for (DomTreeNode::iterator DI = Node->begin(), E = Node->end();
+           DI != E; ++DI) {
+        DomTreeNode *Child = *DI;
+        if (!Visited.insert(Child))
+          continue;
+        
+        MustVisitAChild = true;
+        Child->DFSNumIn = DFSNum++;
+        WorkStack.push_back(Child);
+        break;
       }
+      
+      if (!MustVisitAChild) {
+        // If we reach here means all children are visited
+        Node->DFSNumOut = DFSNum++;
+        WorkStack.pop_back();
+      }
+    }
   }
   SlowQueries = 0;
   DFSInfoValid = true;
@@ -489,38 +514,6 @@ BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A,
   return NULL;
 }
 
-/// assignDFSNumber - Assign In and Out numbers while walking dominator tree
-/// in dfs order.
-void DomTreeNode::assignDFSNumber(int num) {
-  std::vector<DomTreeNode *>  workStack;
-  SmallPtrSet<DomTreeNode *, 32> Visited;
-  
-  workStack.push_back(this);
-  Visited.insert(this);
-  this->DFSNumIn = num++;
-  
-  while (!workStack.empty()) {
-    DomTreeNode  *Node = workStack.back();
-    
-    bool visitChild = false;
-    for (std::vector<DomTreeNode*>::iterator DI = Node->begin(),
-           E = Node->end(); DI != E && !visitChild; ++DI) {
-      DomTreeNode *Child = *DI;
-      if (!Visited.insert(Child))
-        continue;
-      
-      visitChild = true;
-      Child->DFSNumIn = num++;
-      workStack.push_back(Child);
-    }
-    if (!visitChild) {
-      // If we reach here means all children are visited
-      Node->DFSNumOut = num++;
-      workStack.pop_back();
-    }
-  }
-}
-
 void DomTreeNode::setIDom(DomTreeNode *NewIDom) {
   assert(IDom && "No immediate dominator?");
   if (IDom != NewIDom) {
-- 
2.34.1