X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAGList.cpp;h=067407b1eb84e5f27bf13eb1cb69066df6b20c22;hb=b3bc6352defdf1a5c6b1b0770d0c4d603f6524a8;hp=9e4e46f1cc7568c48b6dee9324f1f47d556f5a4f;hpb=e7e7d0d7e39d0c7c659d26b97e8081fce0fcd749;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index 9e4e46f1cc7..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(); } //===----------------------------------------------------------------------===// @@ -116,15 +108,12 @@ 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. @@ -134,9 +123,9 @@ void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) { // 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. - SUnit &Pred = *I->first; + SUnit &Pred = *I->Dep; unsigned PredDoneCycle = Pred.Cycle; - if (!I->second) + if (!I->isCtrl) PredDoneCycle += Pred.Latency; else if (Pred.Latency) PredDoneCycle += 1; @@ -161,31 +150,27 @@ void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { // Bottom up: release successors. for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) - ReleaseSucc(I->first, I->second); + 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. @@ -221,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); @@ -276,7 +261,7 @@ 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) cerr << "*** List scheduling failed! ***\n"; SUnits[i].dump(&DAG); @@ -323,17 +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(DenseMap &sumap, - 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(); @@ -349,6 +345,8 @@ public: return NumNodesSolelyBlocking[NodeNum]; } + unsigned size() const { return Queue.size(); } + bool empty() const { return Queue.empty(); } virtual void push(SUnit *U) { @@ -368,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 @@ -379,27 +382,6 @@ private: int CalcLatency(const SUnit &SU); void AdjustPriorityOfUnscheduledPreds(SUnit *SU); SUnit *getSingleUnscheduledPred(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]); - } }; } @@ -432,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->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 @@ -456,7 +473,7 @@ SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { SUnit *OnlyAvailablePred = 0; for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) { - SUnit &Pred = *I->first; + 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. @@ -475,7 +492,7 @@ void LatencyPriorityQueue::push_impl(SUnit *SU) { unsigned NumNodesBlocking = 0; for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) - if (getSingleUnscheduledPred(I->first) == SU) + if (getSingleUnscheduledPred(I->Dep) == SU) ++NumNodesBlocking; NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; @@ -490,7 +507,7 @@ void LatencyPriorityQueue::push_impl(SUnit *SU) { void LatencyPriorityQueue::ScheduledNode(SUnit *SU) { for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) - AdjustPriorityOfUnscheduledPreds(I->first); + AdjustPriorityOfUnscheduledPreds(I->Dep); } /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just @@ -507,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. @@ -524,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());