From 8d3ab25335d985665cbf69231811da9e58e27592 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Fri, 22 Sep 2006 01:05:33 +0000
Subject: [PATCH] Use iterative algorith to assign DFS number. This reduces
 call stack depth.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@30575 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Analysis/ET-Forest.h | 11 +-------
 lib/VMCore/Dominators.cpp         | 47 +++++++++++++++++++++++++++++++
 2 files changed, 48 insertions(+), 10 deletions(-)

diff --git a/include/llvm/Analysis/ET-Forest.h b/include/llvm/Analysis/ET-Forest.h
index b05776a9e0f..be9df98e26b 100644
--- a/include/llvm/Analysis/ET-Forest.h
+++ b/include/llvm/Analysis/ET-Forest.h
@@ -250,16 +250,7 @@ public:
     return this->Below(other);
   }
 
-  void assignDFSNumber(int &num) {
-    DFSNumIn = num++;
-    
-    if (Son) {
-      Son->assignDFSNumber(num);
-      for (ETNode *son = Son->Right; son != Son; son = son->Right)
-        son->assignDFSNumber(num);
-    }
-    DFSNumOut = num++;
-  }
+  void assignDFSNumber (int);
   
   bool hasFather() const {
     return Father != NULL;
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 9f7e5d9365d..940653d1ec2 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -809,6 +809,53 @@ ETNode *ETNode::NCA(ETNode *other) {
     return occmin->OccFor;
 }
 
+void ETNode::assignDFSNumber(int num) {
+  std::vector<ETNode *>  workStack;
+  std::set<ETNode *> visitedNodes;
+  
+  workStack.push_back(this);
+  visitedNodes.insert(this);
+  this->DFSNumIn = num++;
+
+  while (!workStack.empty()) {
+    ETNode  *Node = workStack.back();
+    
+    // If this is leaf node then set DFSNumOut and pop the stack
+    if (!Node->Son) {
+      Node->DFSNumOut = num++;
+      workStack.pop_back();
+      continue;
+    }
+    
+    ETNode *son = Node->Son;
+    
+    // Visit Node->Son first
+    if (visitedNodes.count(son) == 0) {
+      son->DFSNumIn = num++;
+      workStack.push_back(son);
+      visitedNodes.insert(son);
+      continue;
+    }
+    
+    bool visitChild = false;
+    // Visit remaining children
+    for (ETNode *s = son->Right;  s != son && !visitChild; s = s->Right) {
+      if (visitedNodes.count(s) == 0) {
+        visitChild = true;
+        s->DFSNumIn = num++;
+        workStack.push_back(s);
+          visitedNodes.insert(s);
+      }
+    }
+    
+    if (!visitChild) {
+      // If we reach here means all children are visited
+      Node->DFSNumOut = num++;
+      workStack.pop_back();
+    }
+  }
+}
+
 //===----------------------------------------------------------------------===//
 // ETForest implementation
 //===----------------------------------------------------------------------===//
-- 
2.34.1