X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAGList.cpp;h=067407b1eb84e5f27bf13eb1cb69066df6b20c22;hb=ef5b199905cee0b78eb30cd44836e5b6ca5cbd09;hp=369b05c5e9cb7211871a9c552b6a951165e90b51;hpb=74d2fd8dd847e0ebccef30e2c5907ff09495d518;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index 369b05c5e9c..067407b1eb8 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Evan Cheng and is distributed under the -// University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -22,23 +22,22 @@ #include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/SelectionDAGISel.h" -#include "llvm/CodeGen/SSARegMap.h" -#include "llvm/Target/MRegisterInfo.h" +#include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetData.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Compiler.h" +#include "llvm/ADT/PriorityQueue.h" #include "llvm/ADT/Statistic.h" #include -#include using namespace llvm; STATISTIC(NumNoops , "Number of noops inserted"); STATISTIC(NumStalls, "Number of pipeline stalls"); static RegisterScheduler - tdListDAGScheduler("list-td", " Top-down list scheduler", + tdListDAGScheduler("list-td", "Top-down list scheduler", createTDListDAGScheduler); namespace { @@ -95,18 +94,11 @@ void ScheduleDAGList::Schedule() { // Build scheduling units. BuildSchedUnits(); - AvailableQueue->initNodes(SUnitMap, SUnits); + AvailableQueue->initNodes(SUnits); ListScheduleTopDown(); AvailableQueue->releaseState(); - - DOUT << "*** Final schedule ***\n"; - DEBUG(dumpSchedule()); - DOUT << "\n"; - - // Emit in scheduled order - EmitSchedule(); } //===----------------------------------------------------------------------===// @@ -165,24 +157,20 @@ void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { /// schedulers. void ScheduleDAGList::ListScheduleTopDown() { unsigned CurCycle = 0; - SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front(); // All leaves to Available queue. for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { // It is available if it has no predecessors. - if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) { + if (SUnits[i].Preds.empty()) { AvailableQueue->push(&SUnits[i]); SUnits[i].isAvailable = SUnits[i].isPending = true; } } - // Emit the entry node first. - ScheduleNodeTopDown(Entry, CurCycle); - HazardRec->EmitInstruction(Entry->Node); - // While Available queue is not empty, grab the node with the highest // priority. If it is not ready put it back. Schedule the node. std::vector NotReady; + Sequence.reserve(SUnits.size()); while (!AvailableQueue->empty() || !PendingQueue.empty()) { // Check to see if any of the pending instructions are ready to issue. If // so, add them to the available queue. @@ -218,7 +206,7 @@ void ScheduleDAGList::ListScheduleTopDown() { // If this is a pseudo op, like copyfromreg, look to see if there is a // real target node flagged to it. If so, use the target node. for (unsigned i = 0, e = CurSUnit->FlaggedNodes.size(); - FoundNode->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i) + !FoundNode->isMachineOpcode() && i != e; ++i) FoundNode = CurSUnit->FlaggedNodes[i]; HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode); @@ -320,13 +308,12 @@ namespace { /// mobility. std::vector NumNodesSolelyBlocking; - std::priority_queue, latency_sort> Queue; + PriorityQueue, latency_sort> Queue; public: LatencyPriorityQueue() : Queue(latency_sort(this)) { } - void initNodes(DenseMap > &sumap, - std::vector &sunits) { + void initNodes(std::vector &sunits) { SUnits = &sunits; // Calculate node priorities. CalculatePriorities(); @@ -379,25 +366,9 @@ public: return V; } - /// remove - This is a really inefficient way to remove a node from a - /// priority queue. We should roll our own heap to make this better or - /// something. void remove(SUnit *SU) { - std::vector Temp; - assert(!Queue.empty() && "Not in queue!"); - while (Queue.top() != SU) { - Temp.push_back(Queue.top()); - Queue.pop(); - assert(!Queue.empty() && "Not in queue!"); - } - - // Remove the node from the PQ. - Queue.pop(); - - // Add all the other nodes back. - for (unsigned i = 0, e = Temp.size(); i != e; ++i) - Queue.push(Temp[i]); + Queue.erase_one(SU); } // ScheduledNode - As nodes are scheduled, we look to see if there are any @@ -443,22 +414,57 @@ int LatencyPriorityQueue::CalcLatency(const SUnit &SU) { int &Latency = Latencies[SU.NodeNum]; if (Latency != -1) return Latency; - - int MaxSuccLatency = 0; - for (SUnit::const_succ_iterator I = SU.Succs.begin(), E = SU.Succs.end(); - I != E; ++I) - MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(*I->Dep)); - return Latency = MaxSuccLatency + SU.Latency; + std::vector WorkList; + WorkList.push_back(&SU); + while (!WorkList.empty()) { + const SUnit *Cur = WorkList.back(); + bool AllDone = true; + int MaxSuccLatency = 0; + for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end(); + I != E; ++I) { + int SuccLatency = Latencies[I->Dep->NodeNum]; + if (SuccLatency == -1) { + AllDone = false; + WorkList.push_back(I->Dep); + } else { + MaxSuccLatency = std::max(MaxSuccLatency, SuccLatency); + } + } + if (AllDone) { + Latencies[Cur->NodeNum] = MaxSuccLatency + Cur->Latency; + WorkList.pop_back(); + } + } + + return Latency; } /// CalculatePriorities - Calculate priorities of all scheduling units. void LatencyPriorityQueue::CalculatePriorities() { Latencies.assign(SUnits->size(), -1); NumNodesSolelyBlocking.assign(SUnits->size(), 0); - - for (unsigned i = 0, e = SUnits->size(); i != e; ++i) - CalcLatency((*SUnits)[i]); + + // For each node, calculate the maximal path from the node to the exit. + std::vector > WorkList; + for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { + const SUnit *SU = &(*SUnits)[i]; + if (SU->Succs.empty()) + WorkList.push_back(std::make_pair(SU, 0U)); + } + + while (!WorkList.empty()) { + const SUnit *SU = WorkList.back().first; + unsigned SuccLat = WorkList.back().second; + WorkList.pop_back(); + int &Latency = Latencies[SU->NodeNum]; + if (Latency == -1 || (SU->Latency + SuccLat) > (unsigned)Latency) { + Latency = SU->Latency + SuccLat; + for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end(); + I != E; ++I) + WorkList.push_back(std::make_pair(I->Dep, Latency)); + } + } } /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor @@ -535,7 +541,7 @@ void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { /// recognizer and deletes it when done. ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB) { + MachineBasicBlock *BB, bool Fast) { return new ScheduleDAGList(*DAG, BB, DAG->getTarget(), new LatencyPriorityQueue(), IS->CreateTargetHazardRecognizer());