From 808823cf77076a4a77937a02b0c51b315f722b7b Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Sat, 7 Jun 2014 01:48:43 +0000 Subject: [PATCH] Fix the MachineScheduler's logic for updating ready times for in-order. Now the scheduler updates a node's ready time as soon as it is scheduled, before releasing dependent nodes. There was a reason I didn't do this initially but it no longer applies. A53 is in-order and was running into an issue where nodes where added to the readyQ too early. That's now fixed. This also makes it easier for custom scheduling strategies to build heuristics based on the actual cycles that the node was scheduled at. The only impact on OOO (sandybridge/cyclone) is that ready times will be slightly more accurate. I didn't measure any significant regressions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210390 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/MachineScheduler.h | 4 +- lib/CodeGen/MachineScheduler.cpp | 57 +++++++++++-------------- 2 files changed, 27 insertions(+), 34 deletions(-) diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index 4429b4a347a..b8a28e877f7 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -624,9 +624,9 @@ private: SmallVector ReservedCycles; #ifndef NDEBUG - // Remember the greatest operand latency as an upper bound on the number of + // Remember the greatest possible stall as an upper bound on the number of // times we should retry the pending queue because of a hazard. - unsigned MaxObservedLatency; + unsigned MaxObservedStall; #endif public: diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index 734aba482b9..cbe937a06f0 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -535,6 +535,11 @@ void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) { llvm_unreachable(nullptr); } #endif + // SU->TopReadyCycle was set to CurrCycle when it was scheduled. However, + // CurrCycle may have advanced since then. + if (SuccSU->TopReadyCycle < SU->TopReadyCycle + SuccEdge->getLatency()) + SuccSU->TopReadyCycle = SU->TopReadyCycle + SuccEdge->getLatency(); + --SuccSU->NumPredsLeft; if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) SchedImpl->releaseTopNode(SuccSU); @@ -569,6 +574,11 @@ void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) { llvm_unreachable(nullptr); } #endif + // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However, + // CurrCycle may have advanced since then. + if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency()) + PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency(); + --PredSU->NumSuccsLeft; if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) SchedImpl->releaseBottomNode(PredSU); @@ -680,10 +690,13 @@ void ScheduleDAGMI::schedule() { CurrentBottom = MI; } } - updateQueues(SU, IsTopNode); - - // Notify the scheduling strategy after updating the DAG. + // Notify the scheduling strategy before updating the DAG. + // This sets the scheduled nodes ReadyCycle to CurrCycle. When updateQueues + // runs, it can then use the accurate ReadyCycle time to determine whether + // newly released nodes can move to the readyQ. SchedImpl->schedNode(SU, IsTopNode); + + updateQueues(SU, IsTopNode); } assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); @@ -1574,7 +1587,7 @@ void SchedBoundary::reset() { // Track the maximum number of stall cycles that could arise either from the // latency of a DAG edge or the number of cycles that a processor resource is // reserved (SchedBoundary::ReservedCycles). - MaxObservedLatency = 0; + MaxObservedStall = 0; #endif // Reserve a zero-count for invalid CritResIdx. ExecutedResCounts.resize(1); @@ -1731,6 +1744,12 @@ getOtherResourceCount(unsigned &OtherCritIdx) { } void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle) { + assert(SU->getInstr() && "Scheduled SUnit must have instr"); + +#ifndef NDEBUG + MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall); +#endif + if (ReadyCycle < MinReadyCycle) MinReadyCycle = ReadyCycle; @@ -1750,18 +1769,6 @@ void SchedBoundary::releaseTopNode(SUnit *SU) { if (SU->isScheduled) return; - for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); - I != E; ++I) { - if (I->isWeak()) - continue; - unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle; - unsigned Latency = I->getLatency(); -#ifndef NDEBUG - MaxObservedLatency = std::max(Latency, MaxObservedLatency); -#endif - if (SU->TopReadyCycle < PredReadyCycle + Latency) - SU->TopReadyCycle = PredReadyCycle + Latency; - } releaseNode(SU, SU->TopReadyCycle); } @@ -1769,20 +1776,6 @@ void SchedBoundary::releaseBottomNode(SUnit *SU) { if (SU->isScheduled) return; - assert(SU->getInstr() && "Scheduled SUnit must have instr"); - - for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) { - if (I->isWeak()) - continue; - unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle; - unsigned Latency = I->getLatency(); -#ifndef NDEBUG - MaxObservedLatency = std::max(Latency, MaxObservedLatency); -#endif - if (SU->BotReadyCycle < SuccReadyCycle + Latency) - SU->BotReadyCycle = SuccReadyCycle + Latency; - } releaseNode(SU, SU->BotReadyCycle); } @@ -1951,7 +1944,7 @@ void SchedBoundary::bumpNode(SUnit *SU) { if (SchedModel->getProcResource(PIdx)->BufferSize == 0) { ReservedCycles[PIdx] = isTop() ? NextCycle + PI->Cycles : NextCycle; #ifndef NDEBUG - MaxObservedLatency = std::max(PI->Cycles, MaxObservedLatency); + MaxObservedStall = std::max(PI->Cycles, MaxObservedStall); #endif } } @@ -2055,7 +2048,7 @@ SUnit *SchedBoundary::pickOnlyChoice() { } } for (unsigned i = 0; Available.empty(); ++i) { - assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedLatency) && + assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) && "permanent hazard"); (void)i; bumpCycle(CurrCycle + 1); releasePending(); -- 2.34.1