1//===- AMDGPUCoExecSchedStrategy.cpp - CoExec Scheduling Strategy ---------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// Coexecution-focused scheduling strategy for AMDGPU.
11//
12//===----------------------------------------------------------------------===//
13
14#include "AMDGPUCoExecSchedStrategy.h"
15#include "AMDGPUIGroupLP.h"
16#include "GCNHazardRecognizer.h"
17#include "llvm/Support/Debug.h"
18
19using namespace llvm;
20using namespace llvm::AMDGPU;
21
22#define DEBUG_TYPE "machine-scheduler"
23
24namespace {
25
26// Used to disable post-RA scheduling with function level granularity.
27class GCNNoopPostScheduleDAG final : public ScheduleDAGInstrs {
28public:
29 explicit GCNNoopPostScheduleDAG(MachineSchedContext *C)
30 : ScheduleDAGInstrs(*C->MF, C->MLI, /*RemoveKillFlags=*/true) {}
31
32 // Do nothing.
33 void schedule() override {}
34};
35
36} // namespace
37
38static SUnit *pickOnlyChoice(SchedBoundary &Zone) {
39 // pickOnlyChoice() releases pending instructions and checks for new hazards.
40 SUnit *OnlyChoice = Zone.pickOnlyChoice();
41 if (!Zone.Pending.empty())
42 return nullptr;
43
44 return OnlyChoice;
45}
46
47InstructionFlavor llvm::AMDGPU::classifyFlavor(const MachineInstr &MI,
48 const SIInstrInfo &SII) {
49 if (MI.isDebugInstr())
50 return InstructionFlavor::Other;
51
52 unsigned Opc = MI.getOpcode();
53
54 // Check for specific opcodes first.
55 if (Opc == AMDGPU::ATOMIC_FENCE || Opc == AMDGPU::S_WAIT_ASYNCCNT ||
56 Opc == AMDGPU::S_WAIT_TENSORCNT || Opc == AMDGPU::S_BARRIER_WAIT ||
57 Opc == AMDGPU::S_BARRIER_SIGNAL_IMM)
58 return InstructionFlavor::Fence;
59
60 if (SII.isLDSDMA(MI))
61 return InstructionFlavor::DMA;
62
63 if (SII.isMFMAorWMMA(MI))
64 return InstructionFlavor::WMMA;
65
66 if (SII.isTRANS(MI))
67 return InstructionFlavor::TRANS;
68
69 if (SII.isVALU(MI, /*AllowLDSDMA=*/true))
70 return InstructionFlavor::SingleCycleVALU;
71
72 if (SII.isSMRD(MI))
73 return InstructionFlavor::SMEM;
74
75 if (SII.isDS(MI))
76 return InstructionFlavor::DS;
77
78 if (SII.isVMEM(MI))
79 return InstructionFlavor::VMEM;
80
81 if (SII.isSALU(MI))
82 return InstructionFlavor::SALU;
83
84 return InstructionFlavor::Other;
85}
86
87SUnit *HardwareUnitInfo::getNextTargetSU(bool LookDeep) const {
88 for (SUnit *PrioritySU : PrioritySUs) {
89 if (!PrioritySU->isTopReady())
90 return PrioritySU;
91 }
92
93 if (!LookDeep)
94 return nullptr;
95
96 unsigned MinDepth = std::numeric_limits<unsigned int>::max();
97 SUnit *TargetSU = nullptr;
98 for (auto *SU : AllSUs) {
99 if (SU->isScheduled)
100 continue;
101
102 if (SU->isTopReady())
103 continue;
104
105 if (SU->getDepth() < MinDepth) {
106 MinDepth = SU->getDepth();
107 TargetSU = SU;
108 }
109 }
110 return TargetSU;
111}
112
113void HardwareUnitInfo::insert(SUnit *SU, unsigned BlockingCycles) {
114 if (!AllSUs.insert(X: SU))
115 llvm_unreachable("HardwareUnit already contains SU!");
116
117 TotalCycles += BlockingCycles;
118
119 if (PrioritySUs.empty()) {
120 PrioritySUs.insert(X: SU);
121 return;
122 }
123 unsigned SUDepth = SU->getDepth();
124 unsigned CurrDepth = (*PrioritySUs.begin())->getDepth();
125 if (SUDepth > CurrDepth)
126 return;
127
128 if (SUDepth == CurrDepth) {
129 PrioritySUs.insert(X: SU);
130 return;
131 }
132
133 // SU is lower depth and should be prioritized.
134 PrioritySUs.clear();
135 PrioritySUs.insert(X: SU);
136}
137
138void HardwareUnitInfo::markScheduled(SUnit *SU, unsigned BlockingCycles) {
139 // We may want to ignore some HWUIs (e.g. InstructionFlavor::Other). To do so,
140 // we just clear the HWUI. However, we still have instructions which map to
141 // this HWUI. Don't bother managing the state for these HWUI.
142 if (TotalCycles == 0)
143 return;
144
145 ScheduledSUs.push_back(Elt: SU);
146 AllSUs.remove(X: SU);
147 PrioritySUs.remove(X: SU);
148
149 // BufferSize 0 is unlimited, while size 1 has no parallel buffering. In
150 // either case, each SU uses the HardwareUnit for BlockingCycles.
151 if (BufferSize <= 1 || (ScheduledSUs.size() % BufferSize == 0))
152 TotalCycles -= std::min(a: TotalCycles, b: BlockingCycles);
153
154 if (AllSUs.empty())
155 return;
156 if (PrioritySUs.empty()) {
157 for (auto SU : AllSUs) {
158 if (PrioritySUs.empty()) {
159 PrioritySUs.insert(X: SU);
160 continue;
161 }
162 unsigned SUDepth = SU->getDepth();
163 unsigned CurrDepth = (*PrioritySUs.begin())->getDepth();
164 if (SUDepth > CurrDepth)
165 continue;
166
167 if (SUDepth == CurrDepth) {
168 PrioritySUs.insert(X: SU);
169 continue;
170 }
171
172 // SU is lower depth and should be prioritized.
173 PrioritySUs.clear();
174 PrioritySUs.insert(X: SU);
175 }
176 }
177}
178
179void HardwareUnitInfo::finalizeCycles() {
180 if (BufferSize == 0 || AllSUs.empty())
181 return;
182
183 // We estimate the amount of cycles it takes to free up a slot in the buffer
184 // as the average cycles per SU.
185 BufferCycles = TotalCycles / AllSUs.size();
186 // A single-entry buffer does not reduce TotalCycles.
187 if (BufferSize == 1)
188 return;
189
190 // The TotalCycles is normalized against the BufferSize.
191 // This provides an estimate of the TotalCycles which is not always accurate
192 // -- particularly in cases where we have fewer instructions than the
193 // BufferSize. For example, if we have 2 instructions which each take 50
194 // cycles and a BufferSize of 16, then a TotalCycles of 51 cycles would be
195 // somewhat accurate. This normalization calculates TotalCycles as 6. However,
196 // if we have 64 of these instructions, our normalized estimate of 200 is more
197 // reasonable, given the more accurate measure is 264. Having a completely
198 // accurate measure is not very important, since this metric is mainly used to
199 // compare the relative demand per HardwareUnit across the region. The simpler
200 // estimate makes managing the metric incrementally during scheduling much
201 // simpler.
202 TotalCycles /= BufferSize;
203}
204
205HardwareUnitInfo *
206CandidateHeuristics::getHWUIFromFlavor(InstructionFlavor Flavor) {
207 for (HardwareUnitInfo &HWUICand : HWUInfo) {
208 if (HWUICand.getType() == Flavor) {
209 return &HWUICand;
210 }
211 }
212 return nullptr;
213}
214
215unsigned CandidateHeuristics::getHWUICyclesForInst(SUnit *SU) {
216 assert(SchedModel && SchedModel->hasInstrSchedModel());
217 MachineInstr *MI = SU->getInstr();
218 if (SII->isDS(MI: *MI))
219 return SchedModel->computeInstrLatency(MI);
220
221 unsigned ReleaseAtCycle = 0;
222 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
223 for (TargetSchedModel::ProcResIter PI = SchedModel->getWriteProcResBegin(SC),
224 PE = SchedModel->getWriteProcResEnd(SC);
225 PI != PE; ++PI) {
226 ReleaseAtCycle = std::max(a: ReleaseAtCycle, b: (unsigned)PI->ReleaseAtCycle);
227 }
228 return ReleaseAtCycle;
229}
230
231void CandidateHeuristics::updateForScheduling(SUnit *SU) {
232 HardwareUnitInfo *HWUI =
233 getHWUIFromFlavor(Flavor: classifyFlavor(MI: *SU->getInstr(), SII: *SII));
234 assert(HWUI);
235 HWUI->markScheduled(SU, BlockingCycles: getHWUICyclesForInst(SU));
236}
237
238void CandidateHeuristics::initialize(ScheduleDAGMI *SchedDAG,
239 const TargetSchedModel *TargetSchedModel,
240 const TargetRegisterInfo *TRI) {
241 DAG = SchedDAG;
242 SchedModel = TargetSchedModel;
243 assert(SchedModel && SchedModel->hasInstrSchedModel());
244
245 SRI = static_cast<const SIRegisterInfo *>(TRI);
246 SII = static_cast<const SIInstrInfo *>(DAG->TII);
247
248 HWUInfo.resize(N: (int)InstructionFlavor::NUM_FLAVORS);
249
250 for (unsigned I = 0; I < HWUInfo.size(); I++) {
251 HWUInfo[I].reset();
252 HWUInfo[I].setType(I);
253 }
254
255 HWUInfo[(int)InstructionFlavor::WMMA].setProducesCoexecWindow(true);
256 HWUInfo[(int)InstructionFlavor::MultiCycleVALU].setProducesCoexecWindow(true);
257 HWUInfo[(int)InstructionFlavor::TRANS].setProducesCoexecWindow(true);
258 HWUInfo[(int)InstructionFlavor::DS].setBufferSize(DefaultBufferSizes::DS);
259
260 collectHWUIPressure();
261}
262
263void CandidateHeuristics::collectHWUIPressure() {
264 if (!SchedModel || !SchedModel->hasInstrSchedModel())
265 return;
266
267 for (auto &SU : DAG->SUnits) {
268 const InstructionFlavor Flavor = classifyFlavor(MI: *SU.getInstr(), SII: *SII);
269 HWUInfo[(int)(Flavor)].insert(SU: &SU, BlockingCycles: getHWUICyclesForInst(SU: &SU));
270 }
271
272 for (auto &HWUI : HWUInfo)
273 HWUI.finalizeCycles();
274
275 LLVM_DEBUG(dumpRegionSummary());
276}
277
278void CandidateHeuristics::dumpRegionSummary() {
279 MachineBasicBlock *BB = DAG->begin()->getParent();
280 dbgs() << "\n=== Region: " << DAG->MF.getName() << " BB" << BB->getNumber()
281 << " (" << DAG->SUnits.size() << " SUs) ===\n";
282
283 dbgs() << "\nHWUI Resource Pressure:\n";
284 for (auto &HWUI : HWUInfo) {
285 if (HWUI.getTotalCycles() == 0)
286 continue;
287
288 StringRef Name = getFlavorName(F: HWUI.getType());
289 dbgs() << " " << Name << ": " << HWUI.getTotalCycles() << " cycles, "
290 << HWUI.size() << " instrs\n";
291 }
292 dbgs() << "\n";
293}
294
295void CandidateHeuristics::sortHWUIResources() {
296 // Highest priority should be first.
297 llvm::sort(C&: HWUInfo, Comp: [](HardwareUnitInfo &A, HardwareUnitInfo &B) {
298 // Prefer CoexecWindow producers
299 if (A.producesCoexecWindow() != B.producesCoexecWindow())
300 return A.producesCoexecWindow();
301
302 // Prefer more demanded resources
303 if (A.getTotalCycles() != B.getTotalCycles())
304 return A.getTotalCycles() > B.getTotalCycles();
305
306 // In ties -- prefer the resource with more instructions
307 if (A.size() != B.size())
308 return A.size() < B.size();
309
310 // Default to Flavor order
311 return static_cast<unsigned>(A.getType()) <
312 static_cast<unsigned>(B.getType());
313 });
314}
315
316bool CandidateHeuristics::tryCriticalResourceDependency(
317 GenericSchedulerBase::SchedCandidate &TryCand,
318 GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary *Zone) const {
319
320 auto HasPrioritySU = [this, &Cand, &TryCand](unsigned ResourceIdx) {
321 const HardwareUnitInfo &HWUI = HWUInfo[ResourceIdx];
322
323 auto CandFlavor = classifyFlavor(MI: *Cand.SU->getInstr(), SII: *SII);
324 auto TryCandFlavor = classifyFlavor(MI: *TryCand.SU->getInstr(), SII: *SII);
325 bool LookDeep = (CandFlavor == InstructionFlavor::DS ||
326 TryCandFlavor == InstructionFlavor::DS) &&
327 HWUI.getType() == InstructionFlavor::WMMA;
328 auto *TargetSU = HWUI.getNextTargetSU(LookDeep);
329
330 // If we do not have a TargetSU for this resource, then it is not critical.
331 if (!TargetSU)
332 return false;
333
334 return true;
335 };
336
337 auto TryEnablesResource = [&Cand, &TryCand, this](unsigned ResourceIdx) {
338 const HardwareUnitInfo &HWUI = HWUInfo[ResourceIdx];
339 auto CandFlavor = classifyFlavor(MI: *Cand.SU->getInstr(), SII: *SII);
340
341 // We want to ensure our DS order matches WMMA order.
342 bool LookDeep = CandFlavor == InstructionFlavor::DS &&
343 HWUI.getType() == InstructionFlavor::WMMA;
344 auto *TargetSU = HWUI.getNextTargetSU(LookDeep);
345
346 bool CandEnables =
347 TargetSU != Cand.SU && DAG->IsReachable(SU: TargetSU, TargetSU: Cand.SU);
348 bool TryCandEnables =
349 TargetSU != TryCand.SU && DAG->IsReachable(SU: TargetSU, TargetSU: TryCand.SU);
350
351 if (!CandEnables && !TryCandEnables)
352 return false;
353
354 if (CandEnables && !TryCandEnables) {
355 if (Cand.Reason > GenericSchedulerBase::RegCritical)
356 Cand.Reason = GenericSchedulerBase::RegCritical;
357
358 return true;
359 }
360
361 if (!CandEnables && TryCandEnables) {
362 TryCand.Reason = GenericSchedulerBase::RegCritical;
363 return true;
364 }
365
366 // Both enable, prefer the critical path.
367 unsigned CandHeight = Cand.SU->getHeight();
368 unsigned TryCandHeight = TryCand.SU->getHeight();
369
370 if (CandHeight > TryCandHeight) {
371 if (Cand.Reason > GenericSchedulerBase::RegCritical)
372 Cand.Reason = GenericSchedulerBase::RegCritical;
373
374 return true;
375 }
376
377 if (CandHeight < TryCandHeight) {
378 TryCand.Reason = GenericSchedulerBase::RegCritical;
379 return true;
380 }
381
382 // Same critical path, just prefer original candidate.
383 if (Cand.Reason > GenericSchedulerBase::RegCritical)
384 Cand.Reason = GenericSchedulerBase::RegCritical;
385
386 return true;
387 };
388
389 for (unsigned I = 0; I < HWUInfo.size(); I++) {
390 // If we have encountered a resource that is not critical, then neither
391 // candidate enables a critical resource
392 if (!HasPrioritySU(I))
393 continue;
394
395 bool Enabled = TryEnablesResource(I);
396 // If neither has enabled the resource, continue to the next resource
397 if (Enabled)
398 return true;
399 }
400 return false;
401}
402
403bool CandidateHeuristics::tryCriticalResource(
404 GenericSchedulerBase::SchedCandidate &TryCand,
405 GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary *Zone) const {
406 for (unsigned I = 0; I < HWUInfo.size(); I++) {
407 const HardwareUnitInfo &HWUI = HWUInfo[I];
408
409 bool CandUsesCrit = HWUI.contains(SU: Cand.SU);
410 bool TryCandUsesCrit = HWUI.contains(SU: TryCand.SU);
411
412 if (!CandUsesCrit && !TryCandUsesCrit)
413 continue;
414
415 if (CandUsesCrit != TryCandUsesCrit) {
416 if (CandUsesCrit) {
417 if (Cand.Reason > GenericSchedulerBase::RegCritical)
418 Cand.Reason = GenericSchedulerBase::RegCritical;
419 return true;
420 }
421 TryCand.Reason = GenericSchedulerBase::RegCritical;
422 return true;
423 }
424
425 // Otherwise, both use the critical resource
426 // For longer latency InstructionFlavors, we should prioritize first by
427 // their enablement of critical resources
428 if (HWUI.getType() == InstructionFlavor::DS) {
429 if (tryCriticalResourceDependency(TryCand, Cand, Zone))
430 return true;
431 }
432
433 // Prioritize based on HWUI priorities.
434 SUnit *Match = HWUI.getHigherPriority(SU: Cand.SU, Other: TryCand.SU);
435 if (Match) {
436 if (Match == Cand.SU) {
437 if (Cand.Reason > GenericSchedulerBase::RegCritical)
438 Cand.Reason = GenericSchedulerBase::RegCritical;
439 return true;
440 }
441 TryCand.Reason = GenericSchedulerBase::RegCritical;
442 return true;
443 }
444 }
445
446 return false;
447}
448
449AMDGPUCoExecSchedStrategy::AMDGPUCoExecSchedStrategy(
450 const MachineSchedContext *C)
451 : GCNSchedStrategy(C) {
452 SchedStages.push_back(Elt: GCNSchedStageID::ILPInitialSchedule);
453 SchedStages.push_back(Elt: GCNSchedStageID::RewriteMFMAForm);
454 SchedStages.push_back(Elt: GCNSchedStageID::PreRARematerialize);
455 // Use more accurate GCN pressure trackers.
456 UseGCNTrackers = true;
457}
458
459void AMDGPUCoExecSchedStrategy::initPolicy(MachineBasicBlock::iterator Begin,
460 MachineBasicBlock::iterator End,
461 unsigned NumRegionInstrs) {
462 GCNSchedStrategy::initPolicy(Begin, End, NumRegionInstrs);
463 assert((PreRADirection == MISched::Unspecified ||
464 PreRADirection == MISched::TopDown) &&
465 "coexec scheduler only supports top-down scheduling");
466 RegionPolicy.OnlyTopDown = true;
467 RegionPolicy.OnlyBottomUp = false;
468 RegionPolicy.ShouldTrackLaneMasks = true;
469}
470
471void AMDGPUCoExecSchedStrategy::initialize(ScheduleDAGMI *DAG) {
472 // Coexecution scheduling strategy is only done top-down to support new
473 // resource balancing heuristics.
474 RegionPolicy.OnlyTopDown = true;
475 RegionPolicy.OnlyBottomUp = false;
476
477 GCNSchedStrategy::initialize(DAG);
478 Heurs.initialize(SchedDAG: DAG, TargetSchedModel: SchedModel, TRI);
479
480 // Replace the default hazard recognizer with our PreRA one so that pre-RA
481 // scheduling accounts for WMMA co-execution slot constraints. This must
482 // happen after GCNSchedStrategy::initialize() because
483 // GenericScheduler::initialize() calls SchedBoundary::reset(), which deletes
484 // and recreates the hazard recognizer each region.
485 Top.HazardRec = std::make_unique<GCNHazardRecognizer>(
486 args&: DAG->MF, args: GCNHazardRecognizer::OperatingMode::PreRA);
487}
488
489void AMDGPUCoExecSchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
490 Heurs.updateForScheduling(SU);
491 GCNSchedStrategy::schedNode(SU, IsTopNode);
492}
493
494SUnit *AMDGPUCoExecSchedStrategy::pickNode(bool &IsTopNode) {
495 assert(RegionPolicy.OnlyTopDown && !RegionPolicy.OnlyBottomUp &&
496 "coexec scheduler only supports top-down scheduling");
497
498 if (DAG->top() == DAG->bottom()) {
499 assert(Top.Available.empty() && Top.Pending.empty() &&
500 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
501 return nullptr;
502 }
503
504 bool PickedPending = false;
505 SUnit *SU = nullptr;
506#ifndef NDEBUG
507 SchedCandidate *PickedCand = nullptr;
508#endif
509 do {
510 PickedPending = false;
511 SU = pickOnlyChoice(Zone&: Top);
512 if (!SU) {
513 CandPolicy NoPolicy;
514 TopCand.reset(NewPolicy: NoPolicy);
515 pickNodeFromQueue(Zone&: Top, ZonePolicy: NoPolicy, RPTracker: DAG->getTopRPTracker(), Cand&: TopCand,
516 PickedPending, /*IsBottomUp=*/false);
517 assert(TopCand.Reason != NoCand && "failed to find a candidate");
518 SU = TopCand.SU;
519#ifndef NDEBUG
520 PickedCand = &TopCand;
521#endif
522 }
523 IsTopNode = true;
524 } while (SU->isScheduled);
525
526 LLVM_DEBUG(if (PickedCand) dumpPickSummary(SU, IsTopNode, *PickedCand));
527
528 if (PickedPending) {
529 unsigned ReadyCycle = SU->TopReadyCycle;
530 unsigned CurrentCycle = Top.getCurrCycle();
531 if (ReadyCycle > CurrentCycle)
532 Top.bumpCycle(NextCycle: ReadyCycle);
533
534 // checkHazard() does not expose the exact cycle where the hazard clears.
535 while (Top.checkHazard(SU))
536 Top.bumpCycle(NextCycle: Top.getCurrCycle() + 1);
537
538 Top.releasePending();
539 }
540
541 if (SU->isTopReady())
542 Top.removeReady(SU);
543 if (SU->isBottomReady())
544 Bot.removeReady(SU);
545
546 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
547 << *SU->getInstr());
548
549 assert(IsTopNode && "coexec scheduler must only schedule from top boundary");
550 return SU;
551}
552
553void AMDGPUCoExecSchedStrategy::pickNodeFromQueue(
554 SchedBoundary &Zone, const CandPolicy &ZonePolicy,
555 const RegPressureTracker &RPTracker, SchedCandidate &Cand,
556 bool &PickedPending, bool IsBottomUp) {
557 assert(Zone.isTop() && "coexec scheduler only supports top boundary");
558 assert(!IsBottomUp && "coexec scheduler only supports top-down scheduling");
559
560 const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo *>(TRI);
561 ArrayRef<unsigned> Pressure = RPTracker.getRegSetPressureAtPos();
562 unsigned SGPRPressure = 0;
563 unsigned VGPRPressure = 0;
564 PickedPending = false;
565 if (DAG->isTrackingPressure()) {
566 if (!useGCNTrackers()) {
567 SGPRPressure = Pressure[AMDGPU::RegisterPressureSets::SReg_32];
568 VGPRPressure = Pressure[AMDGPU::RegisterPressureSets::VGPR_32];
569 } else {
570 SGPRPressure = DownwardTracker.getPressure().getSGPRNum();
571 VGPRPressure = DownwardTracker.getPressure().getArchVGPRNum();
572 }
573 }
574
575 auto EvaluateQueue = [&](ReadyQueue &Q, bool FromPending) {
576 for (SUnit *SU : Q) {
577 SchedCandidate TryCand(ZonePolicy);
578 initCandidate(Cand&: TryCand, SU, AtTop: Zone.isTop(), RPTracker, SRI, SGPRPressure,
579 VGPRPressure, IsBottomUp);
580 SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
581 tryCandidateCoexec(Cand, TryCand, Zone: ZoneArg);
582 if (TryCand.Reason != NoCand) {
583 if (TryCand.ResDelta == SchedResourceDelta())
584 TryCand.initResourceDelta(DAG: Zone.DAG, SchedModel);
585 LLVM_DEBUG(printCandidateDecision(Cand, TryCand));
586 PickedPending = FromPending;
587 Cand.setBest(TryCand);
588 } else {
589 LLVM_DEBUG(printCandidateDecision(TryCand, Cand));
590 }
591 }
592 };
593
594 LLVM_DEBUG(dbgs() << "Available Q:\n");
595 EvaluateQueue(Zone.Available, /*FromPending=*/false);
596
597 LLVM_DEBUG(dbgs() << "Pending Q:\n");
598 EvaluateQueue(Zone.Pending, /*FromPending=*/true);
599}
600
601#ifndef NDEBUG
602void AMDGPUCoExecSchedStrategy::dumpPickSummary(SUnit *SU, bool IsTopNode,
603 SchedCandidate &Cand) {
604 const SIInstrInfo *SII = static_cast<const SIInstrInfo *>(DAG->TII);
605 unsigned Cycle = IsTopNode ? Top.getCurrCycle() : Bot.getCurrCycle();
606
607 dbgs() << "=== Pick @ Cycle " << Cycle << " ===\n";
608
609 const InstructionFlavor Flavor = classifyFlavor(*SU->getInstr(), *SII);
610 dbgs() << "Picked: SU(" << SU->NodeNum << ") ";
611 SU->getInstr()->print(dbgs(), /*IsStandalone=*/true, /*SkipOpers=*/false,
612 /*SkipDebugLoc=*/true);
613 dbgs() << " [" << getFlavorName(Flavor) << "]\n";
614
615 dbgs() << " Reason: ";
616 if (LastAMDGPUReason != AMDGPUSchedReason::None)
617 dbgs() << getReasonName(LastAMDGPUReason);
618 else if (Cand.Reason != NoCand)
619 dbgs() << GenericSchedulerBase::getReasonStr(Cand.Reason);
620 else
621 dbgs() << "Unknown";
622 dbgs() << "\n\n";
623
624 LastAMDGPUReason = AMDGPUSchedReason::None;
625}
626#endif
627
628bool AMDGPUCoExecSchedStrategy::tryCandidateCoexec(SchedCandidate &Cand,
629 SchedCandidate &TryCand,
630 SchedBoundary *Zone) {
631 // Initialize the candidate if needed.
632 if (!Cand.isValid()) {
633 TryCand.Reason = FirstValid;
634 return true;
635 }
636
637 // Bias PhysReg Defs and copies to their uses and defined respectively.
638 if (tryGreater(TryVal: biasPhysReg(SU: TryCand.SU, isTop: TryCand.AtTop),
639 CandVal: biasPhysReg(SU: Cand.SU, isTop: Cand.AtTop), TryCand, Cand, Reason: PhysReg))
640 return TryCand.Reason != NoCand;
641
642 // Avoid exceeding the target's limit.
643 if (DAG->isTrackingPressure() &&
644 tryPressure(TryP: TryCand.RPDelta.Excess, CandP: Cand.RPDelta.Excess, TryCand, Cand,
645 Reason: RegExcess, TRI, MF: DAG->MF))
646 return TryCand.Reason != NoCand;
647
648 // We only compare a subset of features when comparing nodes between
649 // Top and Bottom boundary. Some properties are simply incomparable, in many
650 // other instances we should only override the other boundary if something
651 // is a clear good pick on one boundary. Skip heuristics that are more
652 // "tie-breaking" in nature.
653 bool SameBoundary = Zone != nullptr;
654 if (SameBoundary) {
655 // Compare candidates by the stall they would introduce if
656 // scheduled in the current cycle.
657 if (tryEffectiveStall(Cand, TryCand, Zone&: *Zone))
658 return TryCand.Reason != NoCand;
659
660 Heurs.sortHWUIResources();
661 if (Heurs.tryCriticalResource(TryCand, Cand, Zone)) {
662 LastAMDGPUReason = AMDGPUSchedReason::CritResourceBalance;
663 return TryCand.Reason != NoCand;
664 }
665
666 if (Heurs.tryCriticalResourceDependency(TryCand, Cand, Zone)) {
667 LastAMDGPUReason = AMDGPUSchedReason::CritResourceDep;
668 return TryCand.Reason != NoCand;
669 }
670 }
671
672 // Keep clustered nodes together to encourage downstream peephole
673 // optimizations which may reduce resource requirements.
674 //
675 // This is a best effort to set things up for a post-RA pass. Optimizations
676 // like generating loads of multiple registers should ideally be done within
677 // the scheduler pass by combining the loads during DAG postprocessing.
678 unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
679 unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
680 bool CandIsClusterSucc =
681 isTheSameCluster(A: CandZoneCluster, B: Cand.SU->ParentClusterIdx);
682 bool TryCandIsClusterSucc =
683 isTheSameCluster(A: TryCandZoneCluster, B: TryCand.SU->ParentClusterIdx);
684
685 if (tryGreater(TryVal: TryCandIsClusterSucc, CandVal: CandIsClusterSucc, TryCand, Cand,
686 Reason: Cluster))
687 return TryCand.Reason != NoCand;
688
689 if (SameBoundary) {
690 // Weak edges are for clustering and other constraints.
691 if (tryLess(TryVal: getWeakLeft(SU: TryCand.SU, isTop: TryCand.AtTop),
692 CandVal: getWeakLeft(SU: Cand.SU, isTop: Cand.AtTop), TryCand, Cand, Reason: Weak))
693 return TryCand.Reason != NoCand;
694 }
695
696 // Avoid increasing the max pressure of the entire region.
697 if (DAG->isTrackingPressure() &&
698 tryPressure(TryP: TryCand.RPDelta.CurrentMax, CandP: Cand.RPDelta.CurrentMax, TryCand,
699 Cand, Reason: RegMax, TRI, MF: DAG->MF))
700 return TryCand.Reason != NoCand;
701
702 if (SameBoundary) {
703 // Avoid serializing long latency dependence chains.
704 // For acyclic path limited loops, latency was already checked above.
705 if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&
706 !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, Zone&: *Zone))
707 return TryCand.Reason != NoCand;
708
709 // Fall through to original instruction order.
710 if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) ||
711 (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
712 TryCand.Reason = NodeOrder;
713 return true;
714 }
715 }
716
717 return false;
718}
719
720bool AMDGPUCoExecSchedStrategy::tryEffectiveStall(SchedCandidate &Cand,
721 SchedCandidate &TryCand,
722 SchedBoundary &Zone) {
723 auto getBufferFullStalls = [this, &Zone](SUnit *SU) -> unsigned {
724 InstructionFlavor Flavor = classifyFlavor(
725 MI: *SU->getInstr(), SII: *static_cast<const SIInstrInfo *>(DAG->TII));
726 HardwareUnitInfo *HWUI = Heurs.getHWUIFromFlavor(Flavor);
727
728 // A BufferSize of 0 is unlimited, so it has no FIFO scheduling cost.
729 if (HWUI->getBufferSize() == 0)
730 return 0;
731
732 // getBufferAvailableCycle assumes top-down scheduling.
733 assert(Zone.isTop());
734 unsigned CurrCycle = Zone.getCurrCycle();
735 unsigned BufferReadyCycle = HWUI->getBufferAvailableCycle(CurrCycle);
736 if (BufferReadyCycle <= CurrCycle)
737 return 0;
738
739 return BufferReadyCycle - CurrCycle;
740 };
741
742 // Treat structural and latency stalls as a single scheduling cost for the
743 // current cycle.
744 struct StallCosts {
745 unsigned Ready = 0;
746 unsigned Structural = 0;
747 unsigned Latency = 0;
748 unsigned Effective = 0;
749 unsigned Buffer = 0;
750 };
751
752 unsigned CurrCycle = Zone.getCurrCycle();
753 auto GetStallCosts = [&](SUnit *SU) {
754 unsigned ReadyCycle = Zone.isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
755 StallCosts Costs;
756 Costs.Ready = ReadyCycle > CurrCycle ? ReadyCycle - CurrCycle : 0;
757 Costs.Structural = getStructuralStallCycles(Zone, SU);
758 Costs.Latency = Zone.getLatencyStallCycles(SU);
759 Costs.Buffer = getBufferFullStalls(SU);
760 Costs.Effective =
761 std::max(l: {Costs.Ready, Costs.Structural, Costs.Latency, Costs.Buffer});
762 return Costs;
763 };
764
765 StallCosts TryCosts = GetStallCosts(TryCand.SU);
766 StallCosts CandCosts = GetStallCosts(Cand.SU);
767
768 LLVM_DEBUG(if (TryCosts.Effective || CandCosts.Effective) {
769 dbgs() << "Effective stalls: try=" << TryCosts.Effective
770 << " (ready=" << TryCosts.Ready << ", struct=" << TryCosts.Structural
771 << ", lat=" << TryCosts.Latency << ", buffer=" << TryCosts.Buffer
772 << ") cand=" << CandCosts.Effective << " (ready=" << CandCosts.Ready
773 << ", struct=" << CandCosts.Structural
774 << ", lat=" << CandCosts.Latency << ", buffer=" << CandCosts.Buffer
775 << ")\n";
776 });
777
778 return tryLess(TryVal: TryCosts.Effective, CandVal: CandCosts.Effective, TryCand, Cand, Reason: Stall);
779}
780
781ScheduleDAGInstrs *
782llvm::createGCNCoExecMachineScheduler(MachineSchedContext *C) {
783 LLVM_DEBUG(dbgs() << "AMDGPU coexec preRA scheduler selected for "
784 << C->MF->getName() << '\n');
785 ScheduleDAGMILive *DAG = new GCNScheduleDAGMILive(
786 C, std::make_unique<AMDGPUCoExecSchedStrategy>(args&: C));
787 DAG->addMutation(Mutation: createIGroupLPDAGMutation(Phase: AMDGPU::SchedulingPhase::Initial));
788 return DAG;
789}
790
791ScheduleDAGInstrs *
792llvm::createGCNNoopPostMachineScheduler(MachineSchedContext *C) {
793 LLVM_DEBUG(dbgs() << "AMDGPU nop postRA scheduler selected for "
794 << C->MF->getName() << '\n');
795 return new GCNNoopPostScheduleDAG(C);
796}
797