From e6f35d8a5cc92d776cf460200e2b815e8c301b14 Mon Sep 17 00:00:00 2001
From: Evan Cheng <evan.cheng@apple.com>
Date: Tue, 1 Aug 2006 08:20:41 +0000
Subject: [PATCH] Added AssignTopologicalOrder() to assign each node an unique
 id based on their topological order.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29431 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/CodeGen/SelectionDAG.h       |  9 +++++--
 lib/CodeGen/SelectionDAG/SelectionDAG.cpp | 40 +++++++++++++++++++++++++++++--
 2 files changed, 45 insertions(+), 4 deletions(-)

diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index 91d2800cc42..b7dda01a0a1 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -422,10 +422,15 @@ public:
   /// have no referrers.
   void DeleteNode(SDNode *N);
 
-  /// AssignNodeIds - Assign a unique node id for each node in the DAG. It
-  /// returns the maximum id.
+  /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
+  /// their allnodes order. It returns the maximum id.
   unsigned AssignNodeIds();
 
+  /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
+  /// based on their topological order. It returns a vector of the SDNodes* in
+  /// assigned order.
+  std::vector<SDNode*> AssignTopologicalOrder();
+
   void dump() const;
 
   /// InsertISelMapEntry - A helper function to insert a key / element pair
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 8c40a72bec1..943a9501852 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -28,6 +28,7 @@
 #include <set>
 #include <cmath>
 #include <algorithm>
+#include <deque>
 using namespace llvm;
 
 static bool isCommutativeBinOp(unsigned Opcode) {
@@ -2698,8 +2699,8 @@ void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
 }
 
 
-/// AssignNodeIds - Assign a unique node id for each node in the DAG. It returns
-/// the maximum id.
+/// AssignNodeIds - Assign a unique node id for each node in the DAG based on
+/// their allnodes order. It returns the maximum id.
 unsigned SelectionDAG::AssignNodeIds() {
   unsigned Id = 0;
   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
@@ -2709,6 +2710,41 @@ unsigned SelectionDAG::AssignNodeIds() {
   return Id;
 }
 
+/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
+/// based on their topological order. It returns a vector of the SDNodes* in
+/// assigned order.
+std::vector<SDNode*> SelectionDAG::AssignTopologicalOrder() {
+  unsigned DAGSize = AllNodes.size();
+  std::vector<SDNode*> TopOrder;
+  std::map<SDNode*, unsigned> InDegree;
+  std::deque<SDNode*> Sources;
+  for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
+    SDNode *N = I;
+    unsigned Degree = N->use_size();
+    InDegree[N] = Degree;
+    if (Degree == 0)
+      Sources.push_back(I);
+  }
+
+  int Id = 0;
+  while (!Sources.empty()) {
+    SDNode *N = Sources.front();
+    Sources.pop_front();
+    TopOrder.push_back(N);
+    N->setNodeId(Id++);
+    for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
+      SDNode *P = I->Val;
+      unsigned Degree = InDegree[P] - 1;
+      if (Degree == 0)
+        Sources.push_back(P);
+      InDegree[P] = Degree;
+    }
+  }
+
+  return TopOrder;
+}
+
+
 
 //===----------------------------------------------------------------------===//
 //                              SDNode Class
-- 
2.11.0