From e5a8dc5cc4647cdfd97c71165d4c8f805b4c78a3 Mon Sep 17 00:00:00 2001
From: Dan Gohman <gohman@apple.com>
Date: Wed, 27 Aug 2008 16:29:48 +0000
Subject: [PATCH] Optimize ScheduleDAGRRList's topological sort to use one pass
 instead of two, and to not need a scratch std::vector. Also, compute the
 ordering immediately in the result array, instead of in another scratch
 std::vector that is copied to the result array.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55421 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 27 ++++++++------------------
 1 file changed, 8 insertions(+), 19 deletions(-)

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index cd29cf15910..338035a4879 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -448,18 +448,19 @@ inline void ScheduleDAGRRList::Allocate(int n, int index) {
 /// immediately after X in Index2Node.
 void ScheduleDAGRRList::InitDAGTopologicalSorting() {
   unsigned DAGSize = SUnits.size();
-  std::vector<unsigned> InDegree(DAGSize);
   std::vector<SUnit*> WorkList;
   WorkList.reserve(DAGSize);
-  std::vector<SUnit*> TopOrder;
-  TopOrder.reserve(DAGSize);
+
+  Index2Node.resize(DAGSize);
+  Node2Index.resize(DAGSize);
 
   // Initialize the data structures.
   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
     SUnit *SU = &SUnits[i];
     int NodeNum = SU->NodeNum;
     unsigned Degree = SU->Succs.size();
-    InDegree[NodeNum] = Degree;
+    // Temporarily use the Node2Index array as scratch space for degree counts.
+    Node2Index[NodeNum] = Degree;
 
     // Is it a node without dependencies?
     if (Degree == 0) {
@@ -469,35 +470,23 @@ void ScheduleDAGRRList::InitDAGTopologicalSorting() {
     }
   }  
 
+  int Id = DAGSize;
   while (!WorkList.empty()) {
     SUnit *SU = WorkList.back();
     WorkList.pop_back();
-    TopOrder.push_back(SU);
+    Allocate(SU->NodeNum, --Id);
     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
          I != E; ++I) {
       SUnit *SU = I->Dep;
-      if (!--InDegree[SU->NodeNum])
+      if (!--Node2Index[SU->NodeNum])
         // If all dependencies of the node are processed already,
         // then the node can be computed now.
         WorkList.push_back(SU);
     }
   }
 
-  // Second pass, assign the actual topological order as node ids.
-  int Id = 0;
-
-  Index2Node.clear();
-  Node2Index.clear();
-  Index2Node.resize(DAGSize);
-  Node2Index.resize(DAGSize);
   Visited.resize(DAGSize);
 
-  for (std::vector<SUnit*>::reverse_iterator TI = TopOrder.rbegin(),
-       TE = TopOrder.rend();TI != TE; ++TI) {
-    Allocate((*TI)->NodeNum, Id);
-    Id++;
-  }
-
 #ifndef NDEBUG
   // Check correctness of the ordering
   for (unsigned i = 0, e = DAGSize; i != e; ++i) {
-- 
2.11.0