X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAGList.cpp;h=39aadd5279c65bd2183e4919fd0f21dd741c2349;hb=bf304c20651b80309af4c0fb3a14c0d73eaa984f;hp=ee01370d59bc2b29b7cfa83a902166222ae6d77b;hpb=ed41f1bb1981a98eea63f00c5988cf62bbdd7c59;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index ee01370d59b..39aadd5279c 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. // //===----------------------------------------------------------------------===// // @@ -18,26 +18,28 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "sched" +#define DEBUG_TYPE "pre-RA-sched" #include "llvm/CodeGen/ScheduleDAG.h" -#include "llvm/CodeGen/SSARegMap.h" -#include "llvm/Target/MRegisterInfo.h" +#include "llvm/CodeGen/SchedulerRegistry.h" +#include "llvm/CodeGen/SelectionDAGISel.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/Visibility.h" +#include "llvm/Support/Compiler.h" +#include "llvm/ADT/PriorityQueue.h" #include "llvm/ADT/Statistic.h" #include -#include -#include using namespace llvm; -namespace { - static Statistic<> NumNoops ("scheduler", "Number of noops inserted"); - static Statistic<> NumStalls("scheduler", "Number of pipeline stalls"); -} +STATISTIC(NumNoops , "Number of noops inserted"); +STATISTIC(NumStalls, "Number of pipeline stalls"); +static RegisterScheduler + tdListDAGScheduler("list-td", " Top-down list scheduler", + createTDListDAGScheduler); + namespace { //===----------------------------------------------------------------------===// /// ScheduleDAGList - The actual list scheduler implementation. This supports @@ -87,7 +89,7 @@ HazardRecognizer::~HazardRecognizer() {} /// Schedule - Schedule the DAG using list scheduling. void ScheduleDAGList::Schedule() { - DEBUG(std::cerr << "********** List Scheduling **********\n"); + DOUT << "********** List Scheduling **********\n"; // Build scheduling units. BuildSchedUnits(); @@ -97,13 +99,6 @@ void ScheduleDAGList::Schedule() { ListScheduleTopDown(); AvailableQueue->releaseState(); - - DEBUG(std::cerr << "*** Final schedule ***\n"); - DEBUG(dumpSchedule()); - DEBUG(std::cerr << "\n"); - - // Emit in scheduled order - EmitSchedule(); } //===----------------------------------------------------------------------===// @@ -113,28 +108,26 @@ void ScheduleDAGList::Schedule() { /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to /// the PendingQueue if the count reaches zero. void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) { - if (!isChain) - SuccSU->NumPredsLeft--; - else - SuccSU->NumChainPredsLeft--; + SuccSU->NumPredsLeft--; - assert(SuccSU->NumPredsLeft >= 0 && SuccSU->NumChainPredsLeft >= 0 && + assert(SuccSU->NumPredsLeft >= 0 && "List scheduling internal error"); - if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) { + if (SuccSU->NumPredsLeft == 0) { // Compute how many cycles it will be before this actually becomes // available. This is the max of the start time of all predecessors plus // their latencies. unsigned AvailableCycle = 0; - for (std::set >::iterator I = SuccSU->Preds.begin(), + for (SUnit::pred_iterator I = SuccSU->Preds.begin(), E = SuccSU->Preds.end(); I != E; ++I) { // If this is a token edge, we don't need to wait for the latency of the // preceeding instruction (e.g. a long-latency load) unless there is also // some other data dependence. - unsigned PredDoneCycle = I->first->Cycle; - if (!I->second) - PredDoneCycle += I->first->Latency; - else if (I->first->Latency) + SUnit &Pred = *I->Dep; + unsigned PredDoneCycle = Pred.Cycle; + if (!I->isCtrl) + PredDoneCycle += Pred.Latency; + else if (Pred.Latency) PredDoneCycle += 1; AvailableCycle = std::max(AvailableCycle, PredDoneCycle); @@ -148,40 +141,36 @@ void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) { /// count of its successors. If a successor pending count is zero, add it to /// the Available queue. void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { - DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: "); + DOUT << "*** Scheduling [" << CurCycle << "]: "; DEBUG(SU->dump(&DAG)); Sequence.push_back(SU); SU->Cycle = CurCycle; // Bottom up: release successors. - for (std::set >::iterator I = SU->Succs.begin(), - E = SU->Succs.end(); I != E; ++I) - ReleaseSucc(I->first, I->second); + for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) + ReleaseSucc(I->Dep, I->isCtrl); } /// ListScheduleTopDown - The main loop of list scheduling for top-down /// schedulers. void ScheduleDAGList::ListScheduleTopDown() { unsigned CurCycle = 0; - SUnit *Entry = SUnitMap[DAG.getEntryNode().Val]; // 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. @@ -252,7 +241,7 @@ void ScheduleDAGList::ListScheduleTopDown() { } else if (!HasNoopHazards) { // Otherwise, we have a pipeline stall, but no other problem, just advance // the current cycle and try again. - DEBUG(std::cerr << "*** Advancing cycle, no work to do\n"); + DOUT << "*** Advancing cycle, no work to do\n"; HazardRec->AdvanceCycle(); ++NumStalls; ++CurCycle; @@ -260,7 +249,7 @@ void ScheduleDAGList::ListScheduleTopDown() { // Otherwise, we have no instructions to issue and we have instructions // that will fault if we don't do this right. This is the case for // processors without pipeline interlocks and other cases. - DEBUG(std::cerr << "*** Emitting noop\n"); + DOUT << "*** Emitting noop\n"; HazardRec->EmitNoop(); Sequence.push_back(0); // NULL SUnit* -> noop ++NumNoops; @@ -272,11 +261,11 @@ void ScheduleDAGList::ListScheduleTopDown() { // Verify that all SUnits were scheduled. bool AnyNotSched = false; for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { - if (SUnits[i].NumPredsLeft != 0 || SUnits[i].NumChainPredsLeft != 0) { + if (SUnits[i].NumPredsLeft != 0) { if (!AnyNotSched) - std::cerr << "*** List scheduling failed! ***\n"; + cerr << "*** List scheduling failed! ***\n"; SUnits[i].dump(&DAG); - std::cerr << "has not been scheduled!\n"; + cerr << "has not been scheduled!\n"; AnyNotSched = true; } } @@ -307,7 +296,7 @@ namespace { namespace { class LatencyPriorityQueue : public SchedulingPriorityQueue { // SUnits - The SUnits for the current graph. - const std::vector *SUnits; + std::vector *SUnits; // Latencies - The latency (max of latency from this node to the bb exit) // for each node. @@ -319,16 +308,28 @@ namespace { /// mobility. std::vector NumNodesSolelyBlocking; - std::priority_queue, latency_sort> Queue; + PriorityQueue, latency_sort> Queue; public: LatencyPriorityQueue() : Queue(latency_sort(this)) { } - void initNodes(const std::vector &sunits) { + void initNodes(std::vector &sunits) { SUnits = &sunits; // Calculate node priorities. CalculatePriorities(); } + + void addNode(const SUnit *SU) { + Latencies.resize(SUnits->size(), -1); + NumNodesSolelyBlocking.resize(SUnits->size(), 0); + CalcLatency(*SU); + } + + void updateNode(const SUnit *SU) { + Latencies[SU->NodeNum] = -1; + CalcLatency(*SU); + } + void releaseState() { SUnits = 0; Latencies.clear(); @@ -344,6 +345,8 @@ public: return NumNodesSolelyBlocking[NodeNum]; } + unsigned size() const { return Queue.size(); } + bool empty() const { return Queue.empty(); } virtual void push(SUnit *U) { @@ -363,6 +366,11 @@ public: return V; } + void remove(SUnit *SU) { + assert(!Queue.empty() && "Not in queue!"); + Queue.erase_one(SU); + } + // ScheduledNode - As nodes are scheduled, we look to see if there are any // successor nodes that have a single unscheduled predecessor. If so, that // single predecessor has a higher priority, since scheduling it will make @@ -373,27 +381,7 @@ private: void CalculatePriorities(); int CalcLatency(const SUnit &SU); void AdjustPriorityOfUnscheduledPreds(SUnit *SU); - - /// RemoveFromPriorityQueue - 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 RemoveFromPriorityQueue(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]); - } + SUnit *getSingleUnscheduledPred(SUnit *SU); }; } @@ -426,37 +414,74 @@ int LatencyPriorityQueue::CalcLatency(const SUnit &SU) { int &Latency = Latencies[SU.NodeNum]; if (Latency != -1) return Latency; - - int MaxSuccLatency = 0; - for (std::set >::const_iterator I = SU.Succs.begin(), - E = SU.Succs.end(); I != E; ++I) - MaxSuccLatency = std::max(MaxSuccLatency, CalcLatency(*I->first)); - 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 /// of SU, return it, otherwise return null. -static SUnit *getSingleUnscheduledPred(SUnit *SU) { +SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { SUnit *OnlyAvailablePred = 0; - for (std::set >::const_iterator I = SU->Preds.begin(), - E = SU->Preds.end(); I != E; ++I) - if (!I->first->isScheduled) { + for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); + I != E; ++I) { + SUnit &Pred = *I->Dep; + if (!Pred.isScheduled) { // We found an available, but not scheduled, predecessor. If it's the // only one we have found, keep track of it... otherwise give up. - if (OnlyAvailablePred && OnlyAvailablePred != I->first) + if (OnlyAvailablePred && OnlyAvailablePred != &Pred) return 0; - OnlyAvailablePred = I->first; + OnlyAvailablePred = &Pred; } + } return OnlyAvailablePred; } @@ -465,9 +490,9 @@ void LatencyPriorityQueue::push_impl(SUnit *SU) { // Look at all of the successors of this node. Count the number of nodes that // this node is the sole unscheduled node for. unsigned NumNodesBlocking = 0; - for (std::set >::const_iterator I = SU->Succs.begin(), - E = SU->Succs.end(); I != E; ++I) - if (getSingleUnscheduledPred(I->first) == SU) + for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) + if (getSingleUnscheduledPred(I->Dep) == SU) ++NumNodesBlocking; NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; @@ -480,9 +505,9 @@ void LatencyPriorityQueue::push_impl(SUnit *SU) { // single predecessor has a higher priority, since scheduling it will make // the node available. void LatencyPriorityQueue::ScheduledNode(SUnit *SU) { - for (std::set >::const_iterator I = SU->Succs.begin(), - E = SU->Succs.end(); I != E; ++I) - AdjustPriorityOfUnscheduledPreds(I->first); + for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) + AdjustPriorityOfUnscheduledPreds(I->Dep); } /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just @@ -499,7 +524,7 @@ void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { // Okay, we found a single predecessor that is available, but not scheduled. // Since it is available, it must be in the priority queue. First remove it. - RemoveFromPriorityQueue(OnlyAvailablePred); + remove(OnlyAvailablePred); // Reinsert the node into the priority queue, which recomputes its // NumNodesSolelyBlocking value. @@ -511,12 +536,13 @@ void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { // Public Constructor Functions //===----------------------------------------------------------------------===// -/// createTDListDAGScheduler - This creates a top-down list scheduler with the -/// specified hazard recognizer. -ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAG &DAG, - MachineBasicBlock *BB, - HazardRecognizer *HR) { - return new ScheduleDAGList(DAG, BB, DAG.getTarget(), +/// createTDListDAGScheduler - This creates a top-down list scheduler with a +/// new hazard recognizer. This scheduler takes ownership of the hazard +/// recognizer and deletes it when done. +ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + MachineBasicBlock *BB, bool Fast) { + return new ScheduleDAGList(*DAG, BB, DAG->getTarget(), new LatencyPriorityQueue(), - HR); + IS->CreateTargetHazardRecognizer()); }