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

1 files changed, 4 insertions, 5 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index c3ab3680b2..d6bb142646 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();