diff options
author | Dan Gohman <gohman@apple.com> | 2008-08-27 16:29:48 +0000 |
---|---|---|
committer | Dan Gohman <gohman@apple.com> | 2008-08-27 16:29:48 +0000 |
commit | e5a8dc5cc4647cdfd97c71165d4c8f805b4c78a3 (patch) | |
tree | 4f2686b954104845edb470029c9298e3b36d2fe6 /lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | |
parent | 3a09d891a47c3f887bb1d9fec0355dffdc205b38 (diff) | |
download | llvm-e5a8dc5cc4647cdfd97c71165d4c8f805b4c78a3.tar.gz llvm-e5a8dc5cc4647cdfd97c71165d4c8f805b4c78a3.tar.bz2 llvm-e5a8dc5cc4647cdfd97c71165d4c8f805b4c78a3.tar.xz |
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
Diffstat (limited to 'lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp')
-rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 27 |
1 files changed, 8 insertions, 19 deletions
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp index cd29cf1591..338035a487 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) { |