From e10e6f7a36f6f60d1889465a4df51ac8cdb34365 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Mon, 18 Jun 2007 21:28:10 +0000
Subject: [PATCH] make ComputeTopDownOrdering significantly faster and use less
 stack space by making it non-recursive

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@37629 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/LegalizeDAG.cpp | 69 +++++++++++++-----------
 1 file changed, 37 insertions(+), 32 deletions(-)

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index 7d57c00c141..eb81d54a9a9 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -302,24 +302,45 @@ SelectionDAGLegalize::SelectionDAGLegalize(SelectionDAG &dag)
          "Too many value types for ValueTypeActions to hold!");
 }
 
-/// ComputeTopDownOrdering - Add the specified node to the Order list if it has
-/// not been visited yet and if all of its operands have already been visited.
-static void ComputeTopDownOrdering(SDNode *N, SmallVector<SDNode*, 64> &Order,
-                                   DenseMap<SDNode*, unsigned> &Visited) {
-  if (++Visited[N] != N->getNumOperands())
-    return;  // Haven't visited all operands yet
-  
-  Order.push_back(N);
+/// ComputeTopDownOrdering - Compute a top-down ordering of the dag, where Order
+/// contains all of a nodes operands before it contains the node.
+static void ComputeTopDownOrdering(SelectionDAG &DAG,
+                                   SmallVector<SDNode*, 64> &Order) {
+
+  DenseMap<SDNode*, unsigned> Visited;
+  std::vector<SDNode*> Worklist;
+  Worklist.reserve(128);
   
-  if (N->hasOneUse()) { // Tail recurse in common case.
-    ComputeTopDownOrdering(*N->use_begin(), Order, Visited);
-    return;
+  // Compute ordering from all of the leaves in the graphs, those (like the
+  // entry node) that have no operands.
+  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
+       E = DAG.allnodes_end(); I != E; ++I) {
+    if (I->getNumOperands() == 0) {
+      Visited[I] = 0 - 1U;
+      Worklist.push_back(I);
+    }
   }
   
-  // Now that we have N in, add anything that uses it if all of their operands
-  // are now done.
-  for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); UI != E;++UI)
-    ComputeTopDownOrdering(*UI, Order, Visited);
+  while (!Worklist.empty()) {
+    SDNode *N = Worklist.back();
+    Worklist.pop_back();
+    
+    if (++Visited[N] != N->getNumOperands())
+      continue;  // Haven't visited all operands yet
+    
+    Order.push_back(N);
+
+    // Now that we have N in, add anything that uses it if all of their operands
+    // are now done.
+    for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
+         UI != E; ++UI)
+      Worklist.push_back(*UI);
+  }
+
+  assert(Order.size() == Visited.size() &&
+         Order.size() == 
+         (unsigned)std::distance(DAG.allnodes_begin(), DAG.allnodes_end()) &&
+         "Error: DAG is cyclic!");
 }
 
 
@@ -333,24 +354,8 @@ void SelectionDAGLegalize::LegalizeDAG() {
   // practice however, this causes us to run out of stack space on large basic
   // blocks.  To avoid this problem, compute an ordering of the nodes where each
   // node is only legalized after all of its operands are legalized.
-  DenseMap<SDNode*, unsigned> Visited;
   SmallVector<SDNode*, 64> Order;
-  
-  // Compute ordering from all of the leaves in the graphs, those (like the
-  // entry node) that have no operands.
-  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
-       E = DAG.allnodes_end(); I != E; ++I) {
-    if (I->getNumOperands() == 0) {
-      Visited[I] = 0 - 1U;
-      ComputeTopDownOrdering(I, Order, Visited);
-    }
-  }
-  
-  assert(Order.size() == Visited.size() &&
-         Order.size() == 
-            (unsigned)std::distance(DAG.allnodes_begin(), DAG.allnodes_end()) &&
-         "Error: DAG is cyclic!");
-  Visited.clear();
+  ComputeTopDownOrdering(DAG, Order);
   
   for (unsigned i = 0, e = Order.size(); i != e; ++i)
     HandleOp(SDOperand(Order[i], 0));
-- 
2.34.1