//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "sched"
+#define DEBUG_TYPE "pre-RA-sched"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/Statistic.h"
#include <climits>
-#include <iostream>
#include <queue>
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",
/// Schedule - Schedule the DAG using list scheduling.
void ScheduleDAGList::Schedule() {
- DEBUG(std::cerr << "********** List Scheduling **********\n");
+ DOUT << "********** List Scheduling **********\n";
// Build scheduling units.
BuildSchedUnits();
- AvailableQueue->initNodes(SUnits);
+ AvailableQueue->initNodes(SUnitMap, SUnits);
ListScheduleTopDown();
AvailableQueue->releaseState();
- DEBUG(std::cerr << "*** Final schedule ***\n");
+ DOUT << "*** Final schedule ***\n";
DEBUG(dumpSchedule());
- DEBUG(std::cerr << "\n");
+ DOUT << "\n";
// Emit in scheduled order
EmitSchedule();
/// 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.
// 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;
/// 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);
// 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];
+ SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front();
// All leaves to Available queue.
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
} 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;
// 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;
// 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;
}
}
LatencyPriorityQueue() : Queue(latency_sort(this)) {
}
- void initNodes(std::vector<SUnit> &sunits) {
+ void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap,
+ std::vector<SUnit> &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();
return NumNodesSolelyBlocking[NodeNum];
}
+ unsigned size() const { return Queue.size(); }
+
bool empty() const { return Queue.empty(); }
virtual void push(SUnit *U) {
return V;
}
- // 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
- // the node available.
- void ScheduledNode(SUnit *Node);
-
-private:
- void CalculatePriorities();
- 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) {
+ /// 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<SUnit*> Temp;
assert(!Queue.empty() && "Not in queue!");
for (unsigned i = 0, e = Temp.size(); i != e; ++i)
Queue.push(Temp[i]);
}
+
+ // 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
+ // the node available.
+ void ScheduledNode(SUnit *Node);
+
+private:
+ void CalculatePriorities();
+ int CalcLatency(const SUnit &SU);
+ void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
+ SUnit *getSingleUnscheduledPred(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<const SUnit*> 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<std::pair<const SUnit*, unsigned> > WorkList;
+ for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
+ const SUnit *SU = &(*SUnits)[i];
+ if (SU->Succs.size() == 0)
+ 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
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.
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;
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
// 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.
projects / oota-llvm.git / blobdiff