Optimize SelectionDAG's AssignTopologicalOrder even further.

Completely eliminate the TopOrder std::vector. Instead, sort
the AllNodes list in place. This also eliminates the need to
call AllNodes.size(), a linear-time operation, before
performing the sort.

Also, eliminate the Sources temporary std::vector, since it
essentially duplicates the sorted result as it is being
built.

This also changes the direction of the topological sort
from bottom-up to top-down. The AllNodes list starts out in
roughly top-down order, so this reduces the amount of
reordering needed. Top-down is also more convenient for
Legalize, and ISel needed only minor adjustments.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56867 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 66 insertions, 31 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index c3ab368..d6bb142 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -280,11 +280,10 @@ 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.
-  std::vector<SDNode *> TopOrder;
-  unsigned N = DAG.AssignTopologicalOrder(TopOrder);
-  for (unsigned i = N; i != 0; --i)
-    HandleOp(SDValue(TopOrder[i-1], 0));
-  TopOrder.clear();
+  DAG.AssignTopologicalOrder();
+  for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
+       E = prior(DAG.allnodes_end()); I != next(E); ++I)
+    HandleOp(SDValue(I, 0));
 
   // Finally, it's possible the root changed.  Get the new root.
   SDValue OldRoot = DAG.getRoot();
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 4c4a90a..004fc4c 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -587,7 +587,7 @@ void SelectionDAG::DeleteNode(SDNode *N) {
 
 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 
-  // Drop all of the operands and decrement used nodes use counts.
+  // Drop all of the operands and decrement used node's use counts.
   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
     I->getVal()->removeUser(std::distance(N->op_begin(), I), N);
   if (N->OperandsNeedDelete)
@@ -4569,38 +4569,74 @@ void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
 /// based on their topological order. It returns the maximum id and a vector
 /// of the SDNodes* in assigned order by reference.
-unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
-  unsigned DAGSize = AllNodes.size();
-  std::vector<SDNode*> Sources;
+unsigned SelectionDAG::AssignTopologicalOrder() {
+
+  unsigned DAGSize = 0;
+
+  // SortedPos tracks the progress of the algorithm. Nodes before it are
+  // sorted, nodes after it are unsorted. When the algorithm completes
+  // it is at the end of the list.
+  allnodes_iterator SortedPos = allnodes_begin();
+
+  // Visit all the nodes. Add nodes with no operands to the TopOrder result
+  // array immediately. Annotate nodes that do have operands with their
+  // operand count. Before we do this, the Node Id fields of the nodes
+  // may contain arbitrary values. After, the Node Id fields for nodes
+  // before SortedPos will contain the topological sort index, and the
+  // Node Id fields for nodes At SortedPos and after will contain the
+  // count of outstanding operands.
+  for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
+    SDNode *N = I++;
+    unsigned Degree = N->getNumOperands();
+    if (Degree == 0) {
+      // A node with no uses, add it to the result array immediately.
+      N->setNodeId(DAGSize++);
+      allnodes_iterator Q = N;
+      if (Q != SortedPos)
+        SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
+      ++SortedPos;
+    } else {
+      // Temporarily use the Node Id as scratch space for the degree count.
+      N->setNodeId(Degree);
+    }
+  }
 
-  for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
+  // Visit all the nodes. As we iterate, moves nodes into sorted order,
+  // such that by the time the end is reached all nodes will be sorted.
+  for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
     SDNode *N = I;
-    unsigned Degree = N->use_size();
-    // Temporarily use the Node Id as scratch space for the degree count.
-    N->setNodeId(Degree);
-    if (Degree == 0)
-      Sources.push_back(N);
-  }
-
-  TopOrder.clear();
-  TopOrder.reserve(DAGSize);
-  int Id = 0;
-  while (!Sources.empty()) {
-    SDNode *N = Sources.back();
-    Sources.pop_back();
-    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->getVal();
+    for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
+         UI != UE; ++UI) {
+      SDNode *P = *UI;
       unsigned Degree = P->getNodeId();
       --Degree;
-      P->setNodeId(Degree);
-      if (Degree == 0)
-        Sources.push_back(P);
+      if (Degree == 0) {
+        // All of P's operands are sorted, so P may sorted now.
+        P->setNodeId(DAGSize++);
+        if (P != SortedPos)
+          SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
+        ++SortedPos;
+      } else {
+        // Update P's outstanding operand count.
+        P->setNodeId(Degree);
+      }
     }
   }
 
-  return Id;
+  assert(SortedPos == AllNodes.end() &&
+         "Topological sort incomplete!");
+  assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
+         "First node in topological sort is not the entry token!");
+  assert(AllNodes.front().getNodeId() == 0 &&
+         "First node in topological sort has non-zero id!");
+  assert(AllNodes.front().getNumOperands() == 0 &&
+         "First node in topological sort has operands!");
+  assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
+         "Last node in topologic sort has unexpected id!");
+  assert(AllNodes.back().use_empty() &&
+         "Last node in topologic sort has users!");
+  assert(DAGSize == allnodes_size() && "TopOrder result count mismatch!");
+  return DAGSize;
 }