From 44fd0bcc40e04cf9aaaf0f33744ae4decbb656c3 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Tue, 18 Dec 2012 20:52:56 +0000 Subject: [PATCH] MISched: Heuristics, compare latency more precisely. It matters more for some targets. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@170452 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineScheduler.cpp | 81 +++++++++++++++----------------- 1 file changed, 38 insertions(+), 43 deletions(-) diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index df3bec12f9e..45360597991 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -954,19 +954,25 @@ public: // Number of micro-ops left to schedule. unsigned RemainingMicroOps; - unsigned MaxRemainingCount; - void reset() { CriticalPath = 0; RemainingCounts.clear(); CritResIdx = 0; RemainingMicroOps = 0; - MaxRemainingCount = 0; } SchedRemainder() { reset(); } void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel); + + unsigned getMaxRemainingCount(const TargetSchedModel *SchedModel) const { + if (!SchedModel->hasInstrSchedModel()) + return 0; + + return std::max( + RemainingMicroOps * SchedModel->getMicroOpFactor(), + RemainingCounts[CritResIdx]); + } }; /// Each Scheduling boundary is associated with ready queues. It tracks the @@ -1007,9 +1013,6 @@ public: unsigned ExpectedCount; - // Policy flag: attempt to find ILP until expected latency is covered. - bool ShouldIncreaseILP; - #ifndef NDEBUG // Remember the greatest min operand latency. unsigned MaxMinLatency; @@ -1030,7 +1033,6 @@ public: CritResIdx = 0; IsResourceLimited = false; ExpectedCount = 0; - ShouldIncreaseILP = false; #ifndef NDEBUG MaxMinLatency = 0; #endif @@ -1058,7 +1060,7 @@ public: unsigned getUnscheduledLatency(SUnit *SU) const { if (isTop()) return SU->getHeight(); - return SU->getDepth(); + return SU->getDepth() + SU->Latency; } unsigned getCriticalCount() const { @@ -1067,7 +1069,7 @@ public: bool checkHazard(SUnit *SU); - void checkILPPolicy(); + void setLatencyPolicy(CandPolicy &Policy); void releaseNode(SUnit *SU, unsigned ReadyCycle); @@ -1170,9 +1172,6 @@ init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) { CritResIdx = PIdx; } } - MaxRemainingCount = std::max( - RemainingMicroOps * SchedModel->getMicroOpFactor(), - RemainingCounts[CritResIdx]); } void ConvergingScheduler::SchedBoundary:: @@ -1281,12 +1280,27 @@ bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) { return false; } -/// If expected latency is covered, disable ILP policy. -void ConvergingScheduler::SchedBoundary::checkILPPolicy() { - if (ShouldIncreaseILP - && (IsResourceLimited || ExpectedLatency <= CurrCycle)) { - ShouldIncreaseILP = false; - DEBUG(dbgs() << "Disable ILP: " << Available.getName() << '\n'); +/// Compute the remaining latency to determine whether ILP should be increased. +void ConvergingScheduler::SchedBoundary::setLatencyPolicy(CandPolicy &Policy) { + // FIXME: compile time. In all, we visit four queues here one we should only + // need to visit the one that was last popped if we cache the result. + unsigned RemLatency = 0; + for (ReadyQueue::iterator I = Available.begin(), E = Available.end(); + I != E; ++I) { + unsigned L = getUnscheduledLatency(*I); + if (L > RemLatency) + RemLatency = L; + } + for (ReadyQueue::iterator I = Pending.begin(), E = Pending.end(); + I != E; ++I) { + unsigned L = getUnscheduledLatency(*I); + if (L > RemLatency) + RemLatency = L; + } + if (RemLatency + ExpectedLatency >= Rem->CriticalPath + ILPWindow + && RemLatency > Rem->getMaxRemainingCount(SchedModel)) { + Policy.ReduceLatency = true; + DEBUG(dbgs() << "Increase ILP: " << Available.getName() << '\n'); } } @@ -1305,15 +1319,6 @@ void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU, // Record this node as an immediate dependent of the scheduled node. NextSUs.insert(SU); - - // If CriticalPath has been computed, then check if the unscheduled nodes - // exceed the ILP window. Before registerRoots, CriticalPath==0. - if (Rem->CriticalPath && (ExpectedLatency + getUnscheduledLatency(SU) - > Rem->CriticalPath + ILPWindow)) { - ShouldIncreaseILP = true; - DEBUG(dbgs() << "Increase ILP: " << Available.getName() << " " - << ExpectedLatency << " + " << getUnscheduledLatency(SU) << '\n'); - } } /// Move the boundary of scheduled code by one cycle. @@ -1361,9 +1366,6 @@ void ConvergingScheduler::SchedBoundary::countResource(unsigned PIdx, assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted"); Rem->RemainingCounts[PIdx] -= Count; - // Reset MaxRemainingCount for sanity. - Rem->MaxRemainingCount = 0; - // Check if this resource exceeds the current critical resource by a full // cycle. If so, it becomes the critical resource. if ((int)(ResourceCounts[PIdx] - ResourceCounts[CritResIdx]) @@ -1495,9 +1497,7 @@ SUnit *ConvergingScheduler::SchedBoundary::pickOnlyChoice() { /// resources. /// /// If the CriticalZone is latency limited, don't force a policy for the -/// candidates here. Instead, When releasing each candidate, releaseNode -/// compares the region's critical path to the candidate's height or depth and -/// the scheduled zone's expected latency then sets ShouldIncreaseILP. +/// candidates here. Instead, setLatencyPolicy sets ReduceLatency if needed. void ConvergingScheduler::balanceZones( ConvergingScheduler::SchedBoundary &CriticalZone, ConvergingScheduler::SchedCandidate &CriticalCand, @@ -1506,6 +1506,7 @@ void ConvergingScheduler::balanceZones( if (!CriticalZone.IsResourceLimited) return; + assert(SchedModel->hasInstrSchedModel() && "required schedmodel"); SchedRemainder *Rem = CriticalZone.Rem; @@ -1513,7 +1514,7 @@ void ConvergingScheduler::balanceZones( // remainder, try to reduce it. unsigned RemainingCritCount = Rem->RemainingCounts[CriticalZone.CritResIdx]; - if ((int)(Rem->MaxRemainingCount - RemainingCritCount) + if ((int)(Rem->getMaxRemainingCount(SchedModel) - RemainingCritCount) > (int)SchedModel->getLatencyFactor()) { CriticalCand.Policy.ReduceResIdx = CriticalZone.CritResIdx; DEBUG(dbgs() << "Balance " << CriticalZone.Available.getName() << " reduce " @@ -1539,12 +1540,9 @@ void ConvergingScheduler::checkResourceLimits( ConvergingScheduler::SchedCandidate &TopCand, ConvergingScheduler::SchedCandidate &BotCand) { - Bot.checkILPPolicy(); - Top.checkILPPolicy(); - if (Bot.ShouldIncreaseILP) - BotCand.Policy.ReduceLatency = true; - if (Top.ShouldIncreaseILP) - TopCand.Policy.ReduceLatency = true; + // Set ReduceLatency to true if needed. + Bot.setLatencyPolicy(TopCand.Policy); + Top.setLatencyPolicy(BotCand.Policy); // Handle resource-limited regions. if (Top.IsResourceLimited && Bot.IsResourceLimited @@ -1579,9 +1577,6 @@ void ConvergingScheduler::checkResourceLimits( // The critical resource is different in each zone, so request balancing. // Compute the cost of each zone. - Rem.MaxRemainingCount = std::max( - Rem.RemainingMicroOps * SchedModel->getMicroOpFactor(), - Rem.RemainingCounts[Rem.CritResIdx]); Top.ExpectedCount = std::max(Top.ExpectedLatency, Top.CurrCycle); Top.ExpectedCount = std::max( Top.getCriticalCount(), -- 2.34.1