Optimize SelectionDAG's AssignTopologicalOrder even further.
authorDan Gohman <gohman@apple.com>
Tue, 30 Sep 2008 18:30:35 +0000 (18:30 +0000)
committerDan Gohman <gohman@apple.com>
Tue, 30 Sep 2008 18:30:35 +0000 (18:30 +0000)
commitf06c835f769aa1cf67801ed1f6bd366a447c18b1
tree9f4baa2f4853b5d60994462327e73b21edb66763
parent21420dfae18bff11434775e8bdad15496908f17f
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
include/llvm/CodeGen/DAGISelHeader.h
include/llvm/CodeGen/SelectionDAG.h
include/llvm/CodeGen/SelectionDAGISel.h
lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
lib/CodeGen/SelectionDAG/SelectionDAG.cpp
lib/Target/X86/X86ISelDAGToDAG.cpp