using namespace llvm;
bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
+ // The isScheduleHigh flag allows nodes with wraparound dependencies that
+ // cannot easily be modeled as edges with latencies to be scheduled as
+ // soon as possible in a top-down schedule.
+ if (LHS->isScheduleHigh && !RHS->isScheduleHigh)
+ return false;
+ if (!LHS->isScheduleHigh && RHS->isScheduleHigh)
+ return true;
+
unsigned LHSNum = LHS->NodeNum;
unsigned RHSNum = RHS->NodeNum;
}
-/// CalcNodePriority - Calculate the maximal path from the node to the exit.
-///
-int LatencyPriorityQueue::CalcLatency(const SUnit &SU) {
- int &Latency = Latencies[SU.NodeNum];
- if (Latency != -1)
- return Latency;
-
- std::vector<const SUnit*> WorkList;
- WorkList.push_back(&SU);
- while (!WorkList.empty()) {
- const SUnit *Cur = WorkList.back();
- unsigned CurLatency = Cur->Latency;
- bool AllDone = true;
- unsigned 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 {
- // This assumes that there's no delay for reusing registers.
- unsigned NewLatency =
- SuccLatency + ((I->isCtrl && I->Reg != 0) ? 1 : CurLatency);
- MaxSuccLatency = std::max(MaxSuccLatency, NewLatency);
- }
- }
- if (AllDone) {
- Latencies[Cur->NodeNum] = MaxSuccLatency;
- 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 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.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.
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->Dep;
+ SUnit &Pred = *I->getSUnit();
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.
// this node is the sole unscheduled node for.
unsigned NumNodesBlocking = 0;
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I)
- if (getSingleUnscheduledPred(I->Dep) == SU)
+ I != E; ++I) {
+ if (getSingleUnscheduledPred(I->getSUnit()) == SU)
++NumNodesBlocking;
+ }
NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
Queue.push(SU);
// the node available.
void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I)
- AdjustPriorityOfUnscheduledPreds(I->Dep);
+ I != E; ++I) {
+ AdjustPriorityOfUnscheduledPreds(I->getSUnit());
+ }
}
/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just