Optimize SelectionDAG's topological sort to use one pass instead

of two, and to not need a scratch std::vector. Also, use the
SelectionDAG's topological sort in LegalizeDAG instead of having
a separate implementation.


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

1 files changed, 7 insertions, 12 deletions

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index 71a60fbff7..640fc97dcf 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -4427,40 +4427,35 @@ void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
 /// of the SDNodes* in assigned order by reference.
 unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
   unsigned DAGSize = AllNodes.size();
-  std::vector<unsigned> InDegree(DAGSize);
   std::vector<SDNode*> Sources;
 
-  // Use a two pass approach to avoid using a std::map which is slow.
-  unsigned Id = 0;
   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
     SDNode *N = I;
-    N->setNodeId(Id++);
     unsigned Degree = N->use_size();
-    InDegree[N->getNodeId()] = Degree;
+    // 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();
-      unsigned Degree = --InDegree[P->getNodeId()];
+      unsigned Degree = P->getNodeId();
+      --Degree;
+      P->setNodeId(Degree);
       if (Degree == 0)
         Sources.push_back(P);
     }
   }
 
-  // Second pass, assign the actual topological order as node ids.
-  Id = 0;
-  for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
-       TI != TE; ++TI)
-    (*TI)->setNodeId(Id++);
-
   return Id;
 }