1//===-- GCNSchedStrategy.cpp - GCN Scheduler 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/// This contains a MachineSchedStrategy implementation for maximizing wave
11/// occupancy on GCN hardware.
12///
13/// This pass will apply multiple scheduling stages to the same function.
14/// Regions are first recorded in GCNScheduleDAGMILive::schedule. The actual
15/// entry point for the scheduling of those regions is
16/// GCNScheduleDAGMILive::runSchedStages.
17
18/// Generally, the reason for having multiple scheduling stages is to account
19/// for the kernel-wide effect of register usage on occupancy. Usually, only a
20/// few scheduling regions will have register pressure high enough to limit
21/// occupancy for the kernel, so constraints can be relaxed to improve ILP in
22/// other regions.
23///
24//===----------------------------------------------------------------------===//
25
26#include "GCNSchedStrategy.h"
27#include "AMDGPUIGroupLP.h"
28#include "GCNHazardRecognizer.h"
29#include "GCNRegPressure.h"
30#include "SIMachineFunctionInfo.h"
31#include "Utils/AMDGPUBaseInfo.h"
32#include "llvm/ADT/BitVector.h"
33#include "llvm/ADT/STLExtras.h"
34#include "llvm/CodeGen/CalcSpillWeights.h"
35#include "llvm/CodeGen/MachineBasicBlock.h"
36#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
37#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
38#include "llvm/CodeGen/MachineCycleAnalysis.h"
39#include "llvm/CodeGen/MachineOperand.h"
40#include "llvm/CodeGen/Rematerializer.h"
41#include "llvm/MC/LaneBitmask.h"
42#include "llvm/MC/MCSchedule.h"
43#include "llvm/MC/TargetRegistry.h"
44#include "llvm/Support/ErrorHandling.h"
45
46#define DEBUG_TYPE "machine-scheduler"
47
48using namespace llvm;
49
50static cl::opt<bool> DisableUnclusterHighRP(
51 "amdgpu-disable-unclustered-high-rp-reschedule", cl::Hidden,
52 cl::desc("Disable unclustered high register pressure "
53 "reduction scheduling stage."),
54 cl::init(Val: false));
55
56static cl::opt<bool> DisableClusteredLowOccupancy(
57 "amdgpu-disable-clustered-low-occupancy-reschedule", cl::Hidden,
58 cl::desc("Disable clustered low occupancy "
59 "rescheduling for ILP scheduling stage."),
60 cl::init(Val: false));
61
62static cl::opt<unsigned> ScheduleMetricBias(
63 "amdgpu-schedule-metric-bias", cl::Hidden,
64 cl::desc(
65 "Sets the bias which adds weight to occupancy vs latency. Set it to "
66 "100 to chase the occupancy only."),
67 cl::init(Val: 10));
68
69static cl::opt<bool>
70 RelaxedOcc("amdgpu-schedule-relaxed-occupancy", cl::Hidden,
71 cl::desc("Relax occupancy targets for kernels which are memory "
72 "bound (amdgpu-membound-threshold), or "
73 "Wave Limited (amdgpu-limit-wave-threshold)."),
74 cl::init(Val: false));
75
76static cl::opt<bool> GCNTrackers(
77 "amdgpu-use-amdgpu-trackers", cl::Hidden,
78 cl::desc("Use the AMDGPU specific RPTrackers during scheduling"),
79 cl::init(Val: false));
80
81static cl::opt<unsigned> PendingQueueLimit(
82 "amdgpu-scheduler-pending-queue-limit", cl::Hidden,
83 cl::desc(
84 "Max (Available+Pending) size to inspect pending queue (0 disables)"),
85 cl::init(Val: 256));
86
87#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
88#define DUMP_MAX_REG_PRESSURE
89static cl::opt<bool> PrintMaxRPRegUsageBeforeScheduler(
90 "amdgpu-print-max-reg-pressure-regusage-before-scheduler", cl::Hidden,
91 cl::desc("Print a list of live registers along with their def/uses at the "
92 "point of maximum register pressure before scheduling."),
93 cl::init(false));
94
95static cl::opt<bool> PrintMaxRPRegUsageAfterScheduler(
96 "amdgpu-print-max-reg-pressure-regusage-after-scheduler", cl::Hidden,
97 cl::desc("Print a list of live registers along with their def/uses at the "
98 "point of maximum register pressure after scheduling."),
99 cl::init(false));
100#endif
101
102static cl::opt<bool> DisableRewriteMFMAFormSchedStage(
103 "amdgpu-disable-rewrite-mfma-form-sched-stage", cl::Hidden,
104 cl::desc("Disable rewrite mfma rewrite scheduling stage"), cl::init(Val: true));
105
106namespace {
107
108struct VGPRThresholdParser : public cl::parser<unsigned> {
109 VGPRThresholdParser(cl::Option &O) : cl::parser<unsigned>(O) {}
110
111 bool parse(cl::Option &O, StringRef ArgName, StringRef Arg, unsigned &Value) {
112 if (Arg.getAsInteger(Radix: 0, Result&: Value))
113 return O.error(Message: "'" + Arg + "' value invalid for uint argument!");
114
115 if (Value > 100)
116 return O.error(Message: "'" + Arg + "' value must be in the range [0, 100]!");
117
118 return false;
119 }
120};
121
122} // end anonymous namespace
123
124static cl::opt<unsigned, false, VGPRThresholdParser> VGPRThresholdPercentOpt(
125 "amdgpu-vgpr-threshold-percent", cl::Hidden,
126 cl::desc("Percent of VGPR limits that we should use as RP threshold "
127 "during scheduling. We have two limits relevant to scheduling: "
128 "Critical (avoid decreasing occupancy), Excess (avoid spilling). "
129 "This flag scales both limits back by an equal percent: (0 = use "
130 " default calculation, 1-100 = use percentage), default: 0"),
131 cl::init(Val: 0));
132
133const unsigned ScheduleMetrics::ScaleFactor = 100;
134
135GCNSchedStrategy::GCNSchedStrategy(const MachineSchedContext *C)
136 : GenericScheduler(C), TargetOccupancy(0), MF(nullptr),
137 DownwardTracker(*C->LIS), UpwardTracker(*C->LIS), HasHighPressure(false) {
138 if (GCNTrackers.getNumOccurrences() > 0)
139 GCNTrackersOverride = GCNTrackers;
140}
141
142void GCNSchedStrategy::initialize(ScheduleDAGMI *DAG) {
143 GenericScheduler::initialize(dag: DAG);
144
145 MF = &DAG->MF;
146
147 const GCNSubtarget &ST = MF->getSubtarget<GCNSubtarget>();
148
149 SGPRExcessLimit =
150 Context->RegClassInfo->getNumAllocatableRegs(RC: &AMDGPU::SGPR_32RegClass);
151 VGPRExcessLimit =
152 Context->RegClassInfo->getNumAllocatableRegs(RC: &AMDGPU::VGPR_32RegClass);
153 AGPRExcessLimit =
154 Context->RegClassInfo->getNumAllocatableRegs(RC: &AMDGPU::AGPR_32RegClass);
155
156 SIMachineFunctionInfo &MFI = *MF->getInfo<SIMachineFunctionInfo>();
157 // Set the initial TargetOccupnacy to the maximum occupancy that we can
158 // achieve for this function. This effectively sets a lower bound on the
159 // 'Critical' register limits in the scheduler.
160 // Allow for lower occupancy targets if kernel is wave limited or memory
161 // bound, and using the relaxed occupancy feature.
162 TargetOccupancy =
163 RelaxedOcc ? MFI.getMinAllowedOccupancy() : MFI.getOccupancy();
164 SGPRCriticalLimit =
165 std::min(a: ST.getMaxNumSGPRs(WavesPerEU: TargetOccupancy, Addressable: true), b: SGPRExcessLimit);
166
167 if (!KnownExcessRP) {
168 VGPRCriticalLimit = std::min(
169 a: ST.getMaxNumVGPRs(WavesPerEU: TargetOccupancy, DynamicVGPRBlockSize: MFI.getDynamicVGPRBlockSize()),
170 b: VGPRExcessLimit);
171 } else {
172 // This is similar to ST.getMaxNumVGPRs(TargetOccupancy) result except
173 // returns a reasonably small number for targets with lots of VGPRs, such
174 // as GFX10 and GFX11.
175 LLVM_DEBUG(dbgs() << "Region is known to spill, use alternative "
176 "VGPRCriticalLimit calculation method.\n");
177 unsigned DynamicVGPRBlockSize = MFI.getDynamicVGPRBlockSize();
178 unsigned Granule =
179 AMDGPU::IsaInfo::getVGPRAllocGranule(STI: ST, DynamicVGPRBlockSize);
180 unsigned Addressable =
181 AMDGPU::IsaInfo::getAddressableNumVGPRs(STI: ST, DynamicVGPRBlockSize);
182 unsigned VGPRBudget = alignDown(Value: Addressable / TargetOccupancy, Align: Granule);
183 VGPRBudget = std::max(a: VGPRBudget, b: Granule);
184 VGPRCriticalLimit = std::min(a: VGPRBudget, b: VGPRExcessLimit);
185 }
186
187 // Reuse VGPR critical limit
188 AGPRCriticalLimit = std::min(a: VGPRCriticalLimit, b: AGPRExcessLimit);
189
190 // Apply VGPR excess threshold percentage if specified.
191 if (VGPRThresholdPercentOpt > 0) {
192 [[maybe_unused]] unsigned OriginalVGPRExcessLimit = VGPRExcessLimit;
193 [[maybe_unused]] unsigned OriginalVGPRCriticalLimit = VGPRCriticalLimit;
194 VGPRExcessLimit = (VGPRThresholdPercentOpt * VGPRExcessLimit + 99) / 100;
195 VGPRCriticalLimit =
196 (VGPRThresholdPercentOpt * VGPRCriticalLimit + 99) / 100;
197 LLVM_DEBUG(dbgs() << "Applied VGPR excess threshold "
198 << VGPRThresholdPercentOpt << "%, VGPRExcessLimit: "
199 << OriginalVGPRExcessLimit << " -> " << VGPRExcessLimit
200 << ". VGPRCriticalLimit: " << OriginalVGPRCriticalLimit
201 << " -> " << VGPRCriticalLimit << '\n');
202 } else {
203 VGPRExcessLimit -= std::min(a: VGPRLimitBias + ErrorMargin, b: VGPRExcessLimit);
204 VGPRCriticalLimit -=
205 std::min(a: VGPRLimitBias + ErrorMargin, b: VGPRCriticalLimit);
206 }
207
208 // Subtract error margin and bias from register limits and avoid overflow.
209 SGPRCriticalLimit -= std::min(a: SGPRLimitBias + ErrorMargin, b: SGPRCriticalLimit);
210 SGPRExcessLimit -= std::min(a: SGPRLimitBias + ErrorMargin, b: SGPRExcessLimit);
211
212 AGPRExcessLimit -= std::min(a: VGPRLimitBias + ErrorMargin, b: AGPRExcessLimit);
213 AGPRCriticalLimit -= std::min(a: VGPRLimitBias + ErrorMargin, b: AGPRCriticalLimit);
214
215 LLVM_DEBUG(dbgs() << "VGPRCriticalLimit = " << VGPRCriticalLimit
216 << ", VGPRExcessLimit = " << VGPRExcessLimit
217 << ", AGPRCriticalLimit = " << AGPRCriticalLimit
218 << ", AGPRExcessLimit = " << AGPRExcessLimit
219 << ", SGPRCriticalLimit = " << SGPRCriticalLimit
220 << ", SGPRExcessLimit = " << SGPRExcessLimit << "\n\n");
221}
222
223/// Checks whether \p SU can use the cached DAG pressure diffs to compute the
224/// current register pressure.
225///
226/// This works for the common case, but it has a few exceptions that have been
227/// observed through trial and error:
228/// - Explicit physical register operands
229/// - Subregister definitions
230///
231/// In both of those cases, PressureDiff doesn't represent the actual pressure,
232/// and querying LiveIntervals through the RegPressureTracker is needed to get
233/// an accurate value.
234///
235/// We should eventually only use PressureDiff for maximum performance, but this
236/// already allows 80% of SUs to take the fast path without changing scheduling
237/// at all. Further changes would either change scheduling, or require a lot
238/// more logic to recover an accurate pressure estimate from the PressureDiffs.
239static bool canUsePressureDiffs(const SUnit &SU) {
240 if (!SU.isInstr())
241 return false;
242
243 // Cannot use pressure diffs for subregister defs or with physregs, it's
244 // imprecise in both cases.
245 for (const auto &Op : SU.getInstr()->operands()) {
246 if (!Op.isReg() || Op.isImplicit())
247 continue;
248 if (Op.getReg().isPhysical() ||
249 (Op.isDef() && Op.getSubReg() != AMDGPU::NoSubRegister))
250 return false;
251 }
252 return true;
253}
254
255void GCNSchedStrategy::getRegisterPressures(
256 bool AtTop, const RegPressureTracker &RPTracker, SUnit *SU,
257 std::vector<unsigned> &Pressure, std::vector<unsigned> &MaxPressure,
258 GCNDownwardRPTracker &DownwardTracker, GCNUpwardRPTracker &UpwardTracker,
259 ScheduleDAGMI *DAG, const SIRegisterInfo *SRI) {
260 // getDownwardPressure() and getUpwardPressure() make temporary changes to
261 // the tracker, so we need to pass those function a non-const copy.
262 RegPressureTracker &TempTracker = const_cast<RegPressureTracker &>(RPTracker);
263 if (!useGCNTrackers()) {
264 AtTop
265 ? TempTracker.getDownwardPressure(MI: SU->getInstr(), PressureResult&: Pressure, MaxPressureResult&: MaxPressure)
266 : TempTracker.getUpwardPressure(MI: SU->getInstr(), PressureResult&: Pressure, MaxPressureResult&: MaxPressure);
267
268 return;
269 }
270
271 // GCNTrackers
272 Pressure.resize(new_size: 4, x: 0);
273 MachineInstr *MI = SU->getInstr();
274 GCNRegPressure NewPressure;
275 if (AtTop) {
276 GCNDownwardRPTracker TempDownwardTracker(DownwardTracker);
277 NewPressure = TempDownwardTracker.bumpDownwardPressure(MI, TRI: SRI);
278 } else {
279 GCNUpwardRPTracker TempUpwardTracker(UpwardTracker);
280 TempUpwardTracker.recede(MI: *MI);
281 NewPressure = TempUpwardTracker.getPressure();
282 }
283 Pressure[AMDGPU::RegisterPressureSets::SReg_32] = NewPressure.getSGPRNum();
284 Pressure[AMDGPU::RegisterPressureSets::VGPR_32] =
285 NewPressure.getArchVGPRNum();
286 Pressure[AMDGPU::RegisterPressureSets::AGPR_32] = NewPressure.getAGPRNum();
287}
288
289void GCNSchedStrategy::initCandidate(SchedCandidate &Cand, SUnit *SU,
290 bool AtTop,
291 const RegPressureTracker &RPTracker,
292 const SIRegisterInfo *SRI,
293 unsigned SGPRPressure,
294 unsigned VGPRPressure,
295 unsigned AGPRPressure, bool IsBottomUp) {
296 Cand.SU = SU;
297 Cand.AtTop = AtTop;
298
299 if (!DAG->isTrackingPressure())
300 return;
301
302 Pressure.clear();
303 MaxPressure.clear();
304
305 // We try to use the cached PressureDiffs in the ScheduleDAG whenever
306 // possible over querying the RegPressureTracker.
307 //
308 // RegPressureTracker will make a lot of LIS queries which are very
309 // expensive, it is considered a slow function in this context.
310 //
311 // PressureDiffs are precomputed and cached, and getPressureDiff is just a
312 // trivial lookup into an array. It is pretty much free.
313 //
314 // In EXPENSIVE_CHECKS, we always query RPTracker to verify the results of
315 // PressureDiffs.
316 if (AtTop || !canUsePressureDiffs(SU: *SU) || useGCNTrackers()) {
317 getRegisterPressures(AtTop, RPTracker, SU, Pressure, MaxPressure,
318 DownwardTracker, UpwardTracker, DAG, SRI);
319 } else {
320 // Reserve 4 slots.
321 Pressure.resize(new_size: 4, x: 0);
322 Pressure[AMDGPU::RegisterPressureSets::SReg_32] = SGPRPressure;
323 Pressure[AMDGPU::RegisterPressureSets::VGPR_32] = VGPRPressure;
324 Pressure[AMDGPU::RegisterPressureSets::AGPR_32] = AGPRPressure;
325
326 for (const auto &Diff : DAG->getPressureDiff(SU)) {
327 if (!Diff.isValid())
328 continue;
329 // PressureDiffs is always bottom-up so if we're working top-down we need
330 // to invert its sign.
331 Pressure[Diff.getPSet()] +=
332 (IsBottomUp ? Diff.getUnitInc() : -Diff.getUnitInc());
333 }
334
335#ifdef EXPENSIVE_CHECKS
336 std::vector<unsigned> CheckPressure, CheckMaxPressure;
337 getRegisterPressures(AtTop, RPTracker, SU, CheckPressure, CheckMaxPressure,
338 DownwardTracker, UpwardTracker, DAG, SRI);
339 if (Pressure[AMDGPU::RegisterPressureSets::SReg_32] !=
340 CheckPressure[AMDGPU::RegisterPressureSets::SReg_32] ||
341 Pressure[AMDGPU::RegisterPressureSets::VGPR_32] !=
342 CheckPressure[AMDGPU::RegisterPressureSets::VGPR_32] ||
343 Pressure[AMDGPU::RegisterPressureSets::AGPR_32] !=
344 CheckPressure[AMDGPU::RegisterPressureSets::AGPR_32]) {
345 errs() << "Register Pressure is inaccurate when calculated through "
346 "PressureDiff\n"
347 << "SGPR got " << Pressure[AMDGPU::RegisterPressureSets::SReg_32]
348 << ", expected "
349 << CheckPressure[AMDGPU::RegisterPressureSets::SReg_32] << "\n"
350 << "VGPR got " << Pressure[AMDGPU::RegisterPressureSets::VGPR_32]
351 << ", expected "
352 << CheckPressure[AMDGPU::RegisterPressureSets::VGPR_32] << "\n"
353 << "AGPR got " << Pressure[AMDGPU::RegisterPressureSets::AGPR_32]
354 << ", expected "
355 << CheckPressure[AMDGPU::RegisterPressureSets::AGPR_32] << "\n";
356 report_fatal_error("inaccurate register pressure calculation");
357 }
358#endif
359 }
360
361 unsigned NewAGPRPressure = Pressure[AMDGPU::RegisterPressureSets::AGPR_32];
362 unsigned NewSGPRPressure = Pressure[AMDGPU::RegisterPressureSets::SReg_32];
363 unsigned NewVGPRPressure = Pressure[AMDGPU::RegisterPressureSets::VGPR_32];
364
365 // If two instructions increase the pressure of different register sets
366 // by the same amount, the generic scheduler will prefer to schedule the
367 // instruction that increases the set with the least amount of registers,
368 // which in our case would be SGPRs. This is rarely what we want, so
369 // when we report excess/critical register pressure, we do it either
370 // only for VGPRs, AGPRs or SGPRs. Priority: VGPR > AGPR > SGPR.
371
372 // FIXME: Better heuristics to determine whether to prefer SGPRs or VGPRs.
373 const unsigned MaxVGPRPressureInc = 16;
374 bool ShouldTrackVGPRs = VGPRPressure + MaxVGPRPressureInc >= VGPRExcessLimit;
375 bool ShouldTrackAGPRs = AGPRExcessLimit > 0 && !ShouldTrackVGPRs &&
376 AGPRPressure + MaxVGPRPressureInc >= AGPRExcessLimit;
377 bool ShouldTrackSGPRs =
378 !ShouldTrackVGPRs && !ShouldTrackAGPRs && SGPRPressure >= SGPRExcessLimit;
379 // FIXME: We have to enter REG-EXCESS before we reach the actual threshold
380 // to increase the likelihood we don't go over the limits. We should improve
381 // the analysis to look through dependencies to find the path with the least
382 // register pressure.
383 // We only need to update the RPDelta for instructions that increase register
384 // pressure. Instructions that decrease or keep reg pressure the same will be
385 // marked as RegExcess in tryCandidate() when they are compared with
386 // instructions that increase the register pressure.
387 if (ShouldTrackVGPRs && NewVGPRPressure >= VGPRExcessLimit) {
388 HasHighPressure = true;
389 Cand.RPDelta.Excess = PressureChange(AMDGPU::RegisterPressureSets::VGPR_32);
390 Cand.RPDelta.Excess.setUnitInc(NewVGPRPressure - VGPRExcessLimit);
391 }
392
393 if (ShouldTrackAGPRs && NewAGPRPressure >= AGPRExcessLimit) {
394 HasHighPressure = true;
395 Cand.RPDelta.Excess = PressureChange(AMDGPU::RegisterPressureSets::AGPR_32);
396 Cand.RPDelta.Excess.setUnitInc(NewAGPRPressure - AGPRExcessLimit);
397 }
398
399 if (ShouldTrackSGPRs && NewSGPRPressure >= SGPRExcessLimit) {
400 HasHighPressure = true;
401 Cand.RPDelta.Excess = PressureChange(AMDGPU::RegisterPressureSets::SReg_32);
402 Cand.RPDelta.Excess.setUnitInc(NewSGPRPressure - SGPRExcessLimit);
403 }
404
405 // Register pressure is considered 'CRITICAL' if it is approaching a value
406 // that would reduce the wave occupancy for the execution unit. When
407 // register pressure is 'CRITICAL', increasing SGPR, VGPR, and AGPR
408 // pressure all has the same cost, so we pick the most critical type.
409
410 int SGPRDelta = NewSGPRPressure - SGPRCriticalLimit;
411 int VGPRDelta = NewVGPRPressure - VGPRCriticalLimit;
412 int AGPRDelta = AGPRExcessLimit > 0 ? NewAGPRPressure - AGPRCriticalLimit
413 : std::numeric_limits<int>::min();
414
415 if (SGPRDelta >= 0 || VGPRDelta >= 0 || AGPRDelta >= 0) {
416 HasHighPressure = true;
417 // Pick the most critical type.
418 if (VGPRDelta >= SGPRDelta && VGPRDelta >= AGPRDelta) {
419 Cand.RPDelta.CriticalMax =
420 PressureChange(AMDGPU::RegisterPressureSets::VGPR_32);
421 Cand.RPDelta.CriticalMax.setUnitInc(VGPRDelta);
422 } else if (AGPRDelta >= SGPRDelta) {
423 Cand.RPDelta.CriticalMax =
424 PressureChange(AMDGPU::RegisterPressureSets::AGPR_32);
425 Cand.RPDelta.CriticalMax.setUnitInc(AGPRDelta);
426 } else {
427 Cand.RPDelta.CriticalMax =
428 PressureChange(AMDGPU::RegisterPressureSets::SReg_32);
429 Cand.RPDelta.CriticalMax.setUnitInc(SGPRDelta);
430 }
431 }
432}
433
434static bool shouldCheckPending(SchedBoundary &Zone,
435 const TargetSchedModel *SchedModel) {
436 bool HasBufferedModel =
437 SchedModel->hasInstrSchedModel() && SchedModel->getMicroOpBufferSize();
438 unsigned Combined = Zone.Available.size() + Zone.Pending.size();
439 return Combined <= PendingQueueLimit && HasBufferedModel;
440}
441
442static SUnit *pickOnlyChoice(SchedBoundary &Zone,
443 const TargetSchedModel *SchedModel) {
444 // pickOnlyChoice() releases pending instructions and checks for new hazards.
445 SUnit *OnlyChoice = Zone.pickOnlyChoice();
446 if (!shouldCheckPending(Zone, SchedModel) || Zone.Pending.empty())
447 return OnlyChoice;
448
449 return nullptr;
450}
451
452void GCNSchedStrategy::printCandidateDecision(const SchedCandidate &Current,
453 const SchedCandidate &Preferred) {
454 LLVM_DEBUG({
455 dbgs() << "Prefer:\t\t";
456 DAG->dumpNode(*Preferred.SU);
457
458 if (Current.SU) {
459 dbgs() << "Not:\t";
460 DAG->dumpNode(*Current.SU);
461 }
462
463 dbgs() << "Reason:\t\t";
464 traceCandidate(Preferred);
465 });
466}
467
468// This function is mostly cut and pasted from
469// GenericScheduler::pickNodeFromQueue()
470void GCNSchedStrategy::pickNodeFromQueue(SchedBoundary &Zone,
471 const CandPolicy &ZonePolicy,
472 const RegPressureTracker &RPTracker,
473 SchedCandidate &Cand, bool &IsPending,
474 bool IsBottomUp) {
475 const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo *>(TRI);
476 ArrayRef<unsigned> Pressure = RPTracker.getRegSetPressureAtPos();
477 unsigned SGPRPressure = 0;
478 unsigned VGPRPressure = 0;
479 unsigned AGPRPressure = 0;
480 IsPending = false;
481 if (DAG->isTrackingPressure()) {
482 if (!useGCNTrackers()) {
483 SGPRPressure = Pressure[AMDGPU::RegisterPressureSets::SReg_32];
484 VGPRPressure = Pressure[AMDGPU::RegisterPressureSets::VGPR_32];
485 AGPRPressure = Pressure[AMDGPU::RegisterPressureSets::AGPR_32];
486 } else {
487 GCNRPTracker *T = IsBottomUp
488 ? static_cast<GCNRPTracker *>(&UpwardTracker)
489 : static_cast<GCNRPTracker *>(&DownwardTracker);
490 SGPRPressure = T->getPressure().getSGPRNum();
491 VGPRPressure = T->getPressure().getArchVGPRNum();
492 AGPRPressure = T->getPressure().getAGPRNum();
493 }
494 }
495 LLVM_DEBUG(dbgs() << "Available Q:\n");
496 ReadyQueue &AQ = Zone.Available;
497 for (SUnit *SU : AQ) {
498
499 SchedCandidate TryCand(ZonePolicy);
500 initCandidate(Cand&: TryCand, SU, AtTop: Zone.isTop(), RPTracker, SRI, SGPRPressure,
501 VGPRPressure, AGPRPressure, IsBottomUp);
502 // Pass SchedBoundary only when comparing nodes from the same boundary.
503 SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
504 tryCandidate(Cand, TryCand, Zone: ZoneArg);
505 if (TryCand.Reason != NoCand) {
506 // Initialize resource delta if needed in case future heuristics query it.
507 if (TryCand.ResDelta == SchedResourceDelta())
508 TryCand.initResourceDelta(DAG: Zone.DAG, SchedModel);
509 LLVM_DEBUG(printCandidateDecision(Cand, TryCand));
510 Cand.setBest(TryCand);
511 } else {
512 printCandidateDecision(Current: TryCand, Preferred: Cand);
513 }
514 }
515
516 if (!shouldCheckPending(Zone, SchedModel))
517 return;
518
519 LLVM_DEBUG(dbgs() << "Pending Q:\n");
520 ReadyQueue &PQ = Zone.Pending;
521 for (SUnit *SU : PQ) {
522
523 SchedCandidate TryCand(ZonePolicy);
524 initCandidate(Cand&: TryCand, SU, AtTop: Zone.isTop(), RPTracker, SRI, SGPRPressure,
525 VGPRPressure, AGPRPressure, IsBottomUp);
526 // Pass SchedBoundary only when comparing nodes from the same boundary.
527 SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
528 tryPendingCandidate(Cand, TryCand, Zone: ZoneArg);
529 if (TryCand.Reason != NoCand) {
530 // Initialize resource delta if needed in case future heuristics query it.
531 if (TryCand.ResDelta == SchedResourceDelta())
532 TryCand.initResourceDelta(DAG: Zone.DAG, SchedModel);
533 LLVM_DEBUG(printCandidateDecision(Cand, TryCand));
534 IsPending = true;
535 Cand.setBest(TryCand);
536 } else {
537 printCandidateDecision(Current: TryCand, Preferred: Cand);
538 }
539 }
540}
541
542// This function is mostly cut and pasted from
543// GenericScheduler::pickNodeBidirectional()
544SUnit *GCNSchedStrategy::pickNodeBidirectional(bool &IsTopNode,
545 bool &PickedPending) {
546 // Schedule as far as possible in the direction of no choice. This is most
547 // efficient, but also provides the best heuristics for CriticalPSets.
548 if (SUnit *SU = pickOnlyChoice(Zone&: Bot, SchedModel)) {
549 IsTopNode = false;
550 return SU;
551 }
552 if (SUnit *SU = pickOnlyChoice(Zone&: Top, SchedModel)) {
553 IsTopNode = true;
554 return SU;
555 }
556 // Set the bottom-up policy based on the state of the current bottom zone
557 // and the instructions outside the zone, including the top zone.
558 CandPolicy BotPolicy;
559 setPolicy(Policy&: BotPolicy, /*IsPostRA=*/false, CurrZone&: Bot, OtherZone: &Top);
560 // Set the top-down policy based on the state of the current top zone and
561 // the instructions outside the zone, including the bottom zone.
562 CandPolicy TopPolicy;
563 setPolicy(Policy&: TopPolicy, /*IsPostRA=*/false, CurrZone&: Top, OtherZone: &Bot);
564
565 bool BotPending = false;
566 // See if BotCand is still valid (because we previously scheduled from Top).
567 LLVM_DEBUG(dbgs() << "Picking from Bot:\n");
568 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
569 BotCand.Policy != BotPolicy) {
570 BotCand.reset(NewPolicy: CandPolicy());
571 pickNodeFromQueue(Zone&: Bot, ZonePolicy: BotPolicy, RPTracker: DAG->getBotRPTracker(), Cand&: BotCand,
572 IsPending&: BotPending,
573 /*IsBottomUp=*/true);
574 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
575 } else {
576 LLVM_DEBUG(traceCandidate(BotCand));
577#ifndef NDEBUG
578 if (VerifyScheduling) {
579 SchedCandidate TCand;
580 TCand.reset(CandPolicy());
581 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand,
582 BotPending,
583 /*IsBottomUp=*/true);
584 assert(TCand.SU == BotCand.SU &&
585 "Last pick result should correspond to re-picking right now");
586 }
587#endif
588 }
589
590 bool TopPending = false;
591 // Check if the top Q has a better candidate.
592 LLVM_DEBUG(dbgs() << "Picking from Top:\n");
593 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
594 TopCand.Policy != TopPolicy) {
595 TopCand.reset(NewPolicy: CandPolicy());
596 pickNodeFromQueue(Zone&: Top, ZonePolicy: TopPolicy, RPTracker: DAG->getTopRPTracker(), Cand&: TopCand,
597 IsPending&: TopPending,
598 /*IsBottomUp=*/false);
599 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
600 } else {
601 LLVM_DEBUG(traceCandidate(TopCand));
602#ifndef NDEBUG
603 if (VerifyScheduling) {
604 SchedCandidate TCand;
605 TCand.reset(CandPolicy());
606 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand,
607 TopPending,
608 /*IsBottomUp=*/false);
609 assert(TCand.SU == TopCand.SU &&
610 "Last pick result should correspond to re-picking right now");
611 }
612#endif
613 }
614
615 // Pick best from BotCand and TopCand.
616 LLVM_DEBUG(dbgs() << "Top Cand: "; traceCandidate(TopCand);
617 dbgs() << "Bot Cand: "; traceCandidate(BotCand););
618 SchedCandidate Cand = BotPending ? TopCand : BotCand;
619 SchedCandidate TryCand = BotPending ? BotCand : TopCand;
620 PickedPending = BotPending && TopPending;
621
622 TryCand.Reason = NoCand;
623 if (BotPending || TopPending) {
624 PickedPending |= tryPendingCandidate(Cand, TryCand&: TopCand, Zone: nullptr);
625 } else {
626 tryCandidate(Cand, TryCand, Zone: nullptr);
627 }
628
629 if (TryCand.Reason != NoCand) {
630 Cand.setBest(TryCand);
631 }
632
633 LLVM_DEBUG(dbgs() << "Picking: "; traceCandidate(Cand););
634
635 IsTopNode = Cand.AtTop;
636 return Cand.SU;
637}
638
639// This function is mostly cut and pasted from
640// GenericScheduler::pickNode()
641SUnit *GCNSchedStrategy::pickNode(bool &IsTopNode) {
642 if (DAG->top() == DAG->bottom()) {
643 assert(Top.Available.empty() && Top.Pending.empty() &&
644 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
645 return nullptr;
646 }
647 bool PickedPending;
648 SUnit *SU;
649 do {
650 PickedPending = false;
651 if (RegionPolicy.OnlyTopDown) {
652 SU = pickOnlyChoice(Zone&: Top, SchedModel);
653 if (!SU) {
654 CandPolicy NoPolicy;
655 TopCand.reset(NewPolicy: NoPolicy);
656 pickNodeFromQueue(Zone&: Top, ZonePolicy: NoPolicy, RPTracker: DAG->getTopRPTracker(), Cand&: TopCand,
657 IsPending&: PickedPending,
658 /*IsBottomUp=*/false);
659 assert(TopCand.Reason != NoCand && "failed to find a candidate");
660 SU = TopCand.SU;
661 }
662 IsTopNode = true;
663 } else if (RegionPolicy.OnlyBottomUp) {
664 SU = pickOnlyChoice(Zone&: Bot, SchedModel);
665 if (!SU) {
666 CandPolicy NoPolicy;
667 BotCand.reset(NewPolicy: NoPolicy);
668 pickNodeFromQueue(Zone&: Bot, ZonePolicy: NoPolicy, RPTracker: DAG->getBotRPTracker(), Cand&: BotCand,
669 IsPending&: PickedPending,
670 /*IsBottomUp=*/true);
671 assert(BotCand.Reason != NoCand && "failed to find a candidate");
672 SU = BotCand.SU;
673 }
674 IsTopNode = false;
675 } else {
676 SU = pickNodeBidirectional(IsTopNode, PickedPending);
677 }
678 } while (SU->isScheduled);
679
680 if (PickedPending) {
681 unsigned ReadyCycle = IsTopNode ? SU->TopReadyCycle : SU->BotReadyCycle;
682 SchedBoundary &Zone = IsTopNode ? Top : Bot;
683 unsigned CurrentCycle = Zone.getCurrCycle();
684 if (ReadyCycle > CurrentCycle)
685 Zone.bumpCycle(NextCycle: ReadyCycle);
686
687 // FIXME: checkHazard() doesn't give information about which cycle the
688 // hazard will resolve so just keep bumping the cycle by 1. This could be
689 // made more efficient if checkHazard() returned more details.
690 while (Zone.checkHazard(SU))
691 Zone.bumpCycle(NextCycle: Zone.getCurrCycle() + 1);
692
693 Zone.releasePending();
694 }
695
696 if (SU->isTopReady())
697 Top.removeReady(SU);
698 if (SU->isBottomReady())
699 Bot.removeReady(SU);
700
701 LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "
702 << *SU->getInstr());
703 return SU;
704}
705
706void GCNSchedStrategy::schedNode(SUnit *SU, bool IsTopNode) {
707 if (useGCNTrackers()) {
708 MachineInstr *MI = SU->getInstr();
709 IsTopNode ? (void)DownwardTracker.advance(MI, UseInternalIterator: false)
710 : UpwardTracker.recede(MI: *MI);
711 }
712
713 return GenericScheduler::schedNode(SU, IsTopNode);
714}
715
716GCNSchedStageID GCNSchedStrategy::getCurrentStage() {
717 assert(CurrentStage && CurrentStage != SchedStages.end());
718 return *CurrentStage;
719}
720
721bool GCNSchedStrategy::advanceStage() {
722 assert(CurrentStage != SchedStages.end());
723 if (!CurrentStage)
724 CurrentStage = SchedStages.begin();
725 else
726 CurrentStage++;
727
728 return CurrentStage != SchedStages.end();
729}
730
731bool GCNSchedStrategy::hasNextStage() const {
732 assert(CurrentStage);
733 return std::next(x: CurrentStage) != SchedStages.end();
734}
735
736GCNSchedStageID GCNSchedStrategy::getNextStage() const {
737 assert(CurrentStage && std::next(CurrentStage) != SchedStages.end());
738 return *std::next(x: CurrentStage);
739}
740
741bool GCNSchedStrategy::tryPendingCandidate(SchedCandidate &Cand,
742 SchedCandidate &TryCand,
743 SchedBoundary *Zone) const {
744 // Initialize the candidate if needed.
745 if (!Cand.isValid()) {
746 TryCand.Reason = NodeOrder;
747 return true;
748 }
749
750 // Bias PhysReg Defs and copies to their uses and defined respectively.
751 if (tryGreater(TryVal: biasPhysReg(SU: TryCand.SU, isTop: TryCand.AtTop),
752 CandVal: biasPhysReg(SU: Cand.SU, isTop: Cand.AtTop), TryCand, Cand, Reason: PhysReg))
753 return TryCand.Reason != NoCand;
754
755 // Avoid exceeding the target's limit.
756 if (DAG->isTrackingPressure() &&
757 tryPressure(TryP: TryCand.RPDelta.Excess, CandP: Cand.RPDelta.Excess, TryCand, Cand,
758 Reason: RegExcess, TRI, MF: DAG->MF))
759 return TryCand.Reason != NoCand;
760
761 // Avoid increasing the max critical pressure in the scheduled region.
762 if (DAG->isTrackingPressure() &&
763 tryPressure(TryP: TryCand.RPDelta.CriticalMax, CandP: Cand.RPDelta.CriticalMax,
764 TryCand, Cand, Reason: RegCritical, TRI, MF: DAG->MF))
765 return TryCand.Reason != NoCand;
766
767 bool SameBoundary = Zone != nullptr;
768 if (SameBoundary) {
769 TryCand.initResourceDelta(DAG, SchedModel);
770 if (tryLess(TryVal: TryCand.ResDelta.CritResources, CandVal: Cand.ResDelta.CritResources,
771 TryCand, Cand, Reason: ResourceReduce))
772 return TryCand.Reason != NoCand;
773 if (tryGreater(TryVal: TryCand.ResDelta.DemandedResources,
774 CandVal: Cand.ResDelta.DemandedResources, TryCand, Cand,
775 Reason: ResourceDemand))
776 return TryCand.Reason != NoCand;
777 }
778
779 return false;
780}
781
782GCNMaxOccupancySchedStrategy::GCNMaxOccupancySchedStrategy(
783 const MachineSchedContext *C, bool IsLegacyScheduler)
784 : GCNSchedStrategy(C) {
785 SchedStages.push_back(Elt: GCNSchedStageID::OccInitialSchedule);
786 if (!DisableRewriteMFMAFormSchedStage)
787 SchedStages.push_back(Elt: GCNSchedStageID::RewriteMFMAForm);
788 SchedStages.push_back(Elt: GCNSchedStageID::UnclusteredHighRPReschedule);
789 SchedStages.push_back(Elt: GCNSchedStageID::ClusteredLowOccupancyReschedule);
790 SchedStages.push_back(Elt: GCNSchedStageID::PreRARematerialize);
791 if (IsLegacyScheduler)
792 GCNTrackersOverride = std::nullopt;
793}
794
795GCNMaxILPSchedStrategy::GCNMaxILPSchedStrategy(const MachineSchedContext *C)
796 : GCNSchedStrategy(C) {
797 SchedStages.push_back(Elt: GCNSchedStageID::ILPInitialSchedule);
798}
799
800bool GCNMaxILPSchedStrategy::tryCandidate(SchedCandidate &Cand,
801 SchedCandidate &TryCand,
802 SchedBoundary *Zone) const {
803 // Initialize the candidate if needed.
804 if (!Cand.isValid()) {
805 TryCand.Reason = NodeOrder;
806 return true;
807 }
808
809 // Avoid spilling by exceeding the register limit.
810 if (DAG->isTrackingPressure() &&
811 tryPressure(TryP: TryCand.RPDelta.Excess, CandP: Cand.RPDelta.Excess, TryCand, Cand,
812 Reason: RegExcess, TRI, MF: DAG->MF))
813 return TryCand.Reason != NoCand;
814
815 // Bias PhysReg Defs and copies to their uses and defined respectively.
816 if (tryGreater(TryVal: biasPhysReg(SU: TryCand.SU, isTop: TryCand.AtTop),
817 CandVal: biasPhysReg(SU: Cand.SU, isTop: Cand.AtTop), TryCand, Cand, Reason: PhysReg))
818 return TryCand.Reason != NoCand;
819
820 bool SameBoundary = Zone != nullptr;
821 if (SameBoundary) {
822 // Prioritize instructions that read unbuffered resources by stall cycles.
823 if (tryLess(TryVal: Zone->getLatencyStallCycles(SU: TryCand.SU),
824 CandVal: Zone->getLatencyStallCycles(SU: Cand.SU), TryCand, Cand, Reason: Stall))
825 return TryCand.Reason != NoCand;
826
827 // Avoid critical resource consumption and balance the schedule.
828 TryCand.initResourceDelta(DAG, SchedModel);
829 if (tryLess(TryVal: TryCand.ResDelta.CritResources, CandVal: Cand.ResDelta.CritResources,
830 TryCand, Cand, Reason: ResourceReduce))
831 return TryCand.Reason != NoCand;
832 if (tryGreater(TryVal: TryCand.ResDelta.DemandedResources,
833 CandVal: Cand.ResDelta.DemandedResources, TryCand, Cand,
834 Reason: ResourceDemand))
835 return TryCand.Reason != NoCand;
836
837 // Unconditionally try to reduce latency.
838 if (tryLatency(TryCand, Cand, Zone&: *Zone))
839 return TryCand.Reason != NoCand;
840
841 // Weak edges are for clustering and other constraints.
842 if (tryLess(TryVal: getWeakLeft(SU: TryCand.SU, isTop: TryCand.AtTop),
843 CandVal: getWeakLeft(SU: Cand.SU, isTop: Cand.AtTop), TryCand, Cand, Reason: Weak))
844 return TryCand.Reason != NoCand;
845 }
846
847 // Keep clustered nodes together to encourage downstream peephole
848 // optimizations which may reduce resource requirements.
849 //
850 // This is a best effort to set things up for a post-RA pass. Optimizations
851 // like generating loads of multiple registers should ideally be done within
852 // the scheduler pass by combining the loads during DAG postprocessing.
853 unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
854 unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
855 bool CandIsClusterSucc =
856 isTheSameCluster(A: CandZoneCluster, B: Cand.SU->ParentClusterIdx);
857 bool TryCandIsClusterSucc =
858 isTheSameCluster(A: TryCandZoneCluster, B: TryCand.SU->ParentClusterIdx);
859 if (tryGreater(TryVal: TryCandIsClusterSucc, CandVal: CandIsClusterSucc, TryCand, Cand,
860 Reason: Cluster))
861 return TryCand.Reason != NoCand;
862
863 // Avoid increasing the max critical pressure in the scheduled region.
864 if (DAG->isTrackingPressure() &&
865 tryPressure(TryP: TryCand.RPDelta.CriticalMax, CandP: Cand.RPDelta.CriticalMax,
866 TryCand, Cand, Reason: RegCritical, TRI, MF: DAG->MF))
867 return TryCand.Reason != NoCand;
868
869 // Avoid increasing the max pressure of the entire region.
870 if (DAG->isTrackingPressure() &&
871 tryPressure(TryP: TryCand.RPDelta.CurrentMax, CandP: Cand.RPDelta.CurrentMax, TryCand,
872 Cand, Reason: RegMax, TRI, MF: DAG->MF))
873 return TryCand.Reason != NoCand;
874
875 if (SameBoundary) {
876 // Fall through to original instruction order.
877 if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) ||
878 (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
879 TryCand.Reason = NodeOrder;
880 return true;
881 }
882 }
883 return false;
884}
885
886GCNMaxMemoryClauseSchedStrategy::GCNMaxMemoryClauseSchedStrategy(
887 const MachineSchedContext *C)
888 : GCNSchedStrategy(C) {
889 SchedStages.push_back(Elt: GCNSchedStageID::MemoryClauseInitialSchedule);
890}
891
892/// GCNMaxMemoryClauseSchedStrategy tries best to clause memory instructions as
893/// much as possible. This is achieved by:
894// 1. Prioritize clustered operations before stall latency heuristic.
895// 2. Prioritize long-latency-load before stall latency heuristic.
896///
897/// \param Cand provides the policy and current best candidate.
898/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
899/// \param Zone describes the scheduled zone that we are extending, or nullptr
900/// if Cand is from a different zone than TryCand.
901/// \return \c true if TryCand is better than Cand (Reason is NOT NoCand)
902bool GCNMaxMemoryClauseSchedStrategy::tryCandidate(SchedCandidate &Cand,
903 SchedCandidate &TryCand,
904 SchedBoundary *Zone) const {
905 // Initialize the candidate if needed.
906 if (!Cand.isValid()) {
907 TryCand.Reason = NodeOrder;
908 return true;
909 }
910
911 // Bias PhysReg Defs and copies to their uses and defined respectively.
912 if (tryGreater(TryVal: biasPhysReg(SU: TryCand.SU, isTop: TryCand.AtTop),
913 CandVal: biasPhysReg(SU: Cand.SU, isTop: Cand.AtTop), TryCand, Cand, Reason: PhysReg))
914 return TryCand.Reason != NoCand;
915
916 if (DAG->isTrackingPressure()) {
917 // Avoid exceeding the target's limit.
918 if (tryPressure(TryP: TryCand.RPDelta.Excess, CandP: Cand.RPDelta.Excess, TryCand, Cand,
919 Reason: RegExcess, TRI, MF: DAG->MF))
920 return TryCand.Reason != NoCand;
921
922 // Avoid increasing the max critical pressure in the scheduled region.
923 if (tryPressure(TryP: TryCand.RPDelta.CriticalMax, CandP: Cand.RPDelta.CriticalMax,
924 TryCand, Cand, Reason: RegCritical, TRI, MF: DAG->MF))
925 return TryCand.Reason != NoCand;
926 }
927
928 // MaxMemoryClause-specific: We prioritize clustered instructions as we would
929 // get more benefit from clausing these memory instructions.
930 unsigned CandZoneCluster = Cand.AtTop ? TopClusterID : BotClusterID;
931 unsigned TryCandZoneCluster = TryCand.AtTop ? TopClusterID : BotClusterID;
932 bool CandIsClusterSucc =
933 isTheSameCluster(A: CandZoneCluster, B: Cand.SU->ParentClusterIdx);
934 bool TryCandIsClusterSucc =
935 isTheSameCluster(A: TryCandZoneCluster, B: TryCand.SU->ParentClusterIdx);
936 if (tryGreater(TryVal: TryCandIsClusterSucc, CandVal: CandIsClusterSucc, TryCand, Cand,
937 Reason: Cluster))
938 return TryCand.Reason != NoCand;
939
940 // We only compare a subset of features when comparing nodes between
941 // Top and Bottom boundary. Some properties are simply incomparable, in many
942 // other instances we should only override the other boundary if something
943 // is a clear good pick on one boundary. Skip heuristics that are more
944 // "tie-breaking" in nature.
945 bool SameBoundary = Zone != nullptr;
946 if (SameBoundary) {
947 // For loops that are acyclic path limited, aggressively schedule for
948 // latency. Within an single cycle, whenever CurrMOps > 0, allow normal
949 // heuristics to take precedence.
950 if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() &&
951 tryLatency(TryCand, Cand, Zone&: *Zone))
952 return TryCand.Reason != NoCand;
953
954 // MaxMemoryClause-specific: Prioritize long latency memory load
955 // instructions in top-bottom order to hide more latency. The mayLoad check
956 // is used to exclude store-like instructions, which we do not want to
957 // scheduler them too early.
958 bool TryMayLoad =
959 TryCand.SU->isInstr() && TryCand.SU->getInstr()->mayLoad();
960 bool CandMayLoad = Cand.SU->isInstr() && Cand.SU->getInstr()->mayLoad();
961
962 if (TryMayLoad || CandMayLoad) {
963 bool TryLongLatency =
964 TryCand.SU->Latency > 10 * Cand.SU->Latency && TryMayLoad;
965 bool CandLongLatency =
966 10 * TryCand.SU->Latency < Cand.SU->Latency && CandMayLoad;
967
968 if (tryGreater(TryVal: Zone->isTop() ? TryLongLatency : CandLongLatency,
969 CandVal: Zone->isTop() ? CandLongLatency : TryLongLatency, TryCand,
970 Cand, Reason: Stall))
971 return TryCand.Reason != NoCand;
972 }
973 // Prioritize instructions that read unbuffered resources by stall cycles.
974 if (tryLess(TryVal: Zone->getLatencyStallCycles(SU: TryCand.SU),
975 CandVal: Zone->getLatencyStallCycles(SU: Cand.SU), TryCand, Cand, Reason: Stall))
976 return TryCand.Reason != NoCand;
977 }
978
979 if (SameBoundary) {
980 // Weak edges are for clustering and other constraints.
981 if (tryLess(TryVal: getWeakLeft(SU: TryCand.SU, isTop: TryCand.AtTop),
982 CandVal: getWeakLeft(SU: Cand.SU, isTop: Cand.AtTop), TryCand, Cand, Reason: Weak))
983 return TryCand.Reason != NoCand;
984 }
985
986 // Avoid increasing the max pressure of the entire region.
987 if (DAG->isTrackingPressure() &&
988 tryPressure(TryP: TryCand.RPDelta.CurrentMax, CandP: Cand.RPDelta.CurrentMax, TryCand,
989 Cand, Reason: RegMax, TRI, MF: DAG->MF))
990 return TryCand.Reason != NoCand;
991
992 if (SameBoundary) {
993 // Avoid critical resource consumption and balance the schedule.
994 TryCand.initResourceDelta(DAG, SchedModel);
995 if (tryLess(TryVal: TryCand.ResDelta.CritResources, CandVal: Cand.ResDelta.CritResources,
996 TryCand, Cand, Reason: ResourceReduce))
997 return TryCand.Reason != NoCand;
998 if (tryGreater(TryVal: TryCand.ResDelta.DemandedResources,
999 CandVal: Cand.ResDelta.DemandedResources, TryCand, Cand,
1000 Reason: ResourceDemand))
1001 return TryCand.Reason != NoCand;
1002
1003 // Avoid serializing long latency dependence chains.
1004 // For acyclic path limited loops, latency was already checked above.
1005 if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&
1006 !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, Zone&: *Zone))
1007 return TryCand.Reason != NoCand;
1008
1009 // Fall through to original instruction order.
1010 if (Zone->isTop() == (TryCand.SU->NodeNum < Cand.SU->NodeNum)) {
1011 assert(TryCand.SU->NodeNum != Cand.SU->NodeNum);
1012 TryCand.Reason = NodeOrder;
1013 return true;
1014 }
1015 }
1016
1017 return false;
1018}
1019
1020GCNScheduleDAGMILive::GCNScheduleDAGMILive(
1021 MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S)
1022 : ScheduleDAGMILive(C, std::move(S)), ST(MF.getSubtarget<GCNSubtarget>()),
1023 MFI(*MF.getInfo<SIMachineFunctionInfo>()),
1024 StartingOccupancy(MFI.getOccupancy()), MinOccupancy(StartingOccupancy),
1025 RegionLiveOuts(this, /*IsLiveOut=*/true) {
1026
1027 // We want regions with a single MI to be scheduled so that we can reason
1028 // about them correctly during scheduling stages that move MIs between regions
1029 // (e.g., rematerialization).
1030 ScheduleSingleMIRegions = true;
1031 LLVM_DEBUG(dbgs() << "Starting occupancy is " << StartingOccupancy << ".\n");
1032 if (RelaxedOcc) {
1033 MinOccupancy = std::min(a: MFI.getMinAllowedOccupancy(), b: StartingOccupancy);
1034 if (MinOccupancy != StartingOccupancy)
1035 LLVM_DEBUG(dbgs() << "Allowing Occupancy drops to " << MinOccupancy
1036 << ".\n");
1037 }
1038}
1039
1040std::unique_ptr<GCNSchedStage>
1041GCNScheduleDAGMILive::createSchedStage(GCNSchedStageID SchedStageID) {
1042 switch (SchedStageID) {
1043 case GCNSchedStageID::OccInitialSchedule:
1044 return std::make_unique<OccInitialScheduleStage>(args&: SchedStageID, args&: *this);
1045 case GCNSchedStageID::RewriteMFMAForm:
1046 return std::make_unique<RewriteMFMAFormStage>(args&: SchedStageID, args&: *this);
1047 case GCNSchedStageID::UnclusteredHighRPReschedule:
1048 return std::make_unique<UnclusteredHighRPStage>(args&: SchedStageID, args&: *this);
1049 case GCNSchedStageID::ClusteredLowOccupancyReschedule:
1050 return std::make_unique<ClusteredLowOccStage>(args&: SchedStageID, args&: *this);
1051 case GCNSchedStageID::PreRARematerialize:
1052 return std::make_unique<PreRARematStage>(args&: SchedStageID, args&: *this);
1053 case GCNSchedStageID::ILPInitialSchedule:
1054 return std::make_unique<ILPInitialScheduleStage>(args&: SchedStageID, args&: *this);
1055 case GCNSchedStageID::MemoryClauseInitialSchedule:
1056 return std::make_unique<MemoryClauseInitialScheduleStage>(args&: SchedStageID,
1057 args&: *this);
1058 }
1059
1060 llvm_unreachable("Unknown SchedStageID.");
1061}
1062
1063void GCNScheduleDAGMILive::schedule() {
1064 // Collect all scheduling regions. The actual scheduling is performed in
1065 // GCNScheduleDAGMILive::finalizeSchedule.
1066 Regions.push_back(Elt: std::pair(RegionBegin, RegionEnd));
1067}
1068
1069GCNRegPressure
1070GCNScheduleDAGMILive::getRealRegPressure(unsigned RegionIdx) const {
1071 if (Regions[RegionIdx].first == Regions[RegionIdx].second)
1072 return llvm::getRegPressure(MRI, LiveRegs: LiveIns[RegionIdx]);
1073 GCNDownwardRPTracker RPTracker(*LIS);
1074 RPTracker.advance(Begin: Regions[RegionIdx].first, End: Regions[RegionIdx].second,
1075 LiveRegsCopy: &LiveIns[RegionIdx]);
1076 return RPTracker.moveMaxPressure();
1077}
1078
1079static MachineInstr *getLastMIForRegion(MachineBasicBlock::iterator RegionBegin,
1080 MachineBasicBlock::iterator RegionEnd) {
1081 assert(RegionBegin != RegionEnd && "Region must not be empty");
1082 return &*skipDebugInstructionsBackward(It: std::prev(x: RegionEnd), Begin: RegionBegin);
1083}
1084
1085void GCNScheduleDAGMILive::computeBlockPressure(unsigned RegionIdx,
1086 const MachineBasicBlock *MBB) {
1087 GCNDownwardRPTracker RPTracker(*LIS);
1088
1089 // If the block has the only successor then live-ins of that successor are
1090 // live-outs of the current block. We can reuse calculated live set if the
1091 // successor will be sent to scheduling past current block.
1092
1093 // However, due to the bug in LiveInterval analysis it may happen that two
1094 // predecessors of the same successor block have different lane bitmasks for
1095 // a live-out register. Workaround that by sticking to one-to-one relationship
1096 // i.e. one predecessor with one successor block.
1097 const MachineBasicBlock *OnlySucc = nullptr;
1098 if (MBB->succ_size() == 1) {
1099 auto *Candidate = *MBB->succ_begin();
1100 if (!Candidate->empty() && Candidate->pred_size() == 1) {
1101 SlotIndexes *Ind = LIS->getSlotIndexes();
1102 if (Ind->getMBBStartIdx(mbb: MBB) < Ind->getMBBStartIdx(mbb: Candidate))
1103 OnlySucc = Candidate;
1104 }
1105 }
1106
1107 // Scheduler sends regions from the end of the block upwards.
1108 size_t CurRegion = RegionIdx;
1109 for (size_t E = Regions.size(); CurRegion != E; ++CurRegion)
1110 if (Regions[CurRegion].first->getParent() != MBB)
1111 break;
1112 --CurRegion;
1113
1114 auto I = MBB->begin();
1115 auto LiveInIt = MBBLiveIns.find(Val: MBB);
1116 auto &Rgn = Regions[CurRegion];
1117 auto *NonDbgMI = &*skipDebugInstructionsForward(It: Rgn.first, End: Rgn.second);
1118 if (LiveInIt != MBBLiveIns.end()) {
1119 auto LiveIn = std::move(LiveInIt->second);
1120 RPTracker.reset(MI: *MBB->begin(), End: MBB->end(), LiveRegs: &LiveIn);
1121 MBBLiveIns.erase(I: LiveInIt);
1122 } else {
1123 I = Rgn.first;
1124 auto LRS = BBLiveInMap.lookup(Val: NonDbgMI);
1125#ifdef EXPENSIVE_CHECKS
1126 assert(isEqual(getLiveRegsBefore(*NonDbgMI, *LIS), LRS));
1127#endif
1128 RPTracker.reset(MI: *I, End: I->getParent()->end(), LiveRegs: &LRS);
1129 }
1130
1131 for (;;) {
1132 I = RPTracker.getNext();
1133
1134 if (Regions[CurRegion].first == I || NonDbgMI == I) {
1135 LiveIns[CurRegion] = RPTracker.getLiveRegs();
1136 RPTracker.clearMaxPressure();
1137 }
1138
1139 if (Regions[CurRegion].second == I) {
1140 Pressure[CurRegion] = RPTracker.moveMaxPressure();
1141 if (CurRegion-- == RegionIdx)
1142 break;
1143 auto &Rgn = Regions[CurRegion];
1144 NonDbgMI = &*skipDebugInstructionsForward(It: Rgn.first, End: Rgn.second);
1145 }
1146 RPTracker.advanceBeforeNext();
1147 RPTracker.advanceToNext();
1148 }
1149
1150 if (OnlySucc) {
1151 if (I != MBB->end()) {
1152 RPTracker.advanceBeforeNext();
1153 RPTracker.advanceToNext();
1154 RPTracker.advance(End: MBB->end());
1155 }
1156 MBBLiveIns[OnlySucc] = RPTracker.moveLiveRegs();
1157 }
1158}
1159
1160DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet>
1161GCNScheduleDAGMILive::getRegionLiveInMap() const {
1162 assert(!Regions.empty());
1163 std::vector<MachineInstr *> RegionFirstMIs;
1164 RegionFirstMIs.reserve(n: Regions.size());
1165 for (auto &[RegionBegin, RegionEnd] : reverse(C: Regions))
1166 RegionFirstMIs.push_back(
1167 x: &*skipDebugInstructionsForward(It: RegionBegin, End: RegionEnd));
1168
1169 return getLiveRegMap(R&: RegionFirstMIs, /*After=*/false, LIS&: *LIS);
1170}
1171
1172DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet>
1173GCNScheduleDAGMILive::getRegionLiveOutMap() const {
1174 assert(!Regions.empty());
1175 std::vector<MachineInstr *> RegionLastMIs;
1176 RegionLastMIs.reserve(n: Regions.size());
1177 for (auto &[RegionBegin, RegionEnd] : reverse(C: Regions)) {
1178 // Skip empty regions.
1179 if (RegionBegin == RegionEnd)
1180 continue;
1181 RegionLastMIs.push_back(x: getLastMIForRegion(RegionBegin, RegionEnd));
1182 }
1183 return getLiveRegMap(R&: RegionLastMIs, /*After=*/true, LIS&: *LIS);
1184}
1185
1186void RegionPressureMap::buildLiveRegMap() {
1187 IdxToInstruction.clear();
1188
1189 RegionLiveRegMap =
1190 IsLiveOut ? DAG->getRegionLiveOutMap() : DAG->getRegionLiveInMap();
1191 for (unsigned I = 0; I < DAG->Regions.size(); I++) {
1192 auto &[RegionBegin, RegionEnd] = DAG->Regions[I];
1193 // Skip empty regions.
1194 if (RegionBegin == RegionEnd)
1195 continue;
1196 MachineInstr *RegionKey =
1197 IsLiveOut ? getLastMIForRegion(RegionBegin, RegionEnd) : &*RegionBegin;
1198 IdxToInstruction[I] = RegionKey;
1199 }
1200}
1201
1202void GCNScheduleDAGMILive::finalizeSchedule() {
1203 // Start actual scheduling here. This function is called by the base
1204 // MachineScheduler after all regions have been recorded by
1205 // GCNScheduleDAGMILive::schedule().
1206 LiveIns.resize(N: Regions.size());
1207 Pressure.resize(N: Regions.size());
1208 RegionsWithHighRP.resize(N: Regions.size());
1209 RegionsWithExcessRP.resize(N: Regions.size());
1210 RegionsWithIGLPInstrs.resize(N: Regions.size());
1211 RegionsWithHighRP.reset();
1212 RegionsWithExcessRP.reset();
1213 RegionsWithIGLPInstrs.reset();
1214
1215 runSchedStages();
1216}
1217
1218void GCNScheduleDAGMILive::runSchedStages() {
1219 LLVM_DEBUG(dbgs() << "All regions recorded, starting actual scheduling.\n");
1220
1221 GCNSchedStrategy &S = static_cast<GCNSchedStrategy &>(*SchedImpl);
1222 if (!Regions.empty()) {
1223 BBLiveInMap = getRegionLiveInMap();
1224 if (S.useGCNTrackers())
1225 RegionLiveOuts.buildLiveRegMap();
1226 }
1227
1228#ifdef DUMP_MAX_REG_PRESSURE
1229 if (PrintMaxRPRegUsageBeforeScheduler) {
1230 dumpMaxRegPressure(MF, GCNRegPressure::VGPR, *LIS, MLI);
1231 dumpMaxRegPressure(MF, GCNRegPressure::SGPR, *LIS, MLI);
1232 LIS->dump();
1233 }
1234#endif
1235
1236 while (S.advanceStage()) {
1237 auto Stage = createSchedStage(SchedStageID: S.getCurrentStage());
1238 if (!Stage->initGCNSchedStage())
1239 continue;
1240
1241 for (auto Region : Regions) {
1242 RegionBegin = Region.first;
1243 RegionEnd = Region.second;
1244 // Setup for scheduling the region and check whether it should be skipped.
1245 if (!Stage->initGCNRegion()) {
1246 Stage->advanceRegion();
1247 exitRegion();
1248 continue;
1249 }
1250
1251 if (S.useGCNTrackers()) {
1252 const unsigned RegionIdx = Stage->getRegionIdx();
1253 S.getDownwardTracker()->reset(MRI, LiveRegs: LiveIns[RegionIdx]);
1254 S.getUpwardTracker()->reset(
1255 MRI, LiveRegs: RegionLiveOuts.getLiveRegsForRegionIdx(RegionIdx));
1256 }
1257
1258 ScheduleDAGMILive::schedule();
1259 Stage->finalizeGCNRegion();
1260 Stage->advanceRegion();
1261 exitRegion();
1262 }
1263
1264 Stage->finalizeGCNSchedStage();
1265 }
1266
1267#ifdef DUMP_MAX_REG_PRESSURE
1268 if (PrintMaxRPRegUsageAfterScheduler) {
1269 dumpMaxRegPressure(MF, GCNRegPressure::VGPR, *LIS, MLI);
1270 dumpMaxRegPressure(MF, GCNRegPressure::SGPR, *LIS, MLI);
1271 LIS->dump();
1272 }
1273#endif
1274}
1275
1276#ifndef NDEBUG
1277raw_ostream &llvm::operator<<(raw_ostream &OS, const GCNSchedStageID &StageID) {
1278 switch (StageID) {
1279 case GCNSchedStageID::OccInitialSchedule:
1280 OS << "Max Occupancy Initial Schedule";
1281 break;
1282 case GCNSchedStageID::RewriteMFMAForm:
1283 OS << "Instruction Rewriting Reschedule";
1284 break;
1285 case GCNSchedStageID::UnclusteredHighRPReschedule:
1286 OS << "Unclustered High Register Pressure Reschedule";
1287 break;
1288 case GCNSchedStageID::ClusteredLowOccupancyReschedule:
1289 OS << "Clustered Low Occupancy Reschedule";
1290 break;
1291 case GCNSchedStageID::PreRARematerialize:
1292 OS << "Pre-RA Rematerialize";
1293 break;
1294 case GCNSchedStageID::ILPInitialSchedule:
1295 OS << "Max ILP Initial Schedule";
1296 break;
1297 case GCNSchedStageID::MemoryClauseInitialSchedule:
1298 OS << "Max memory clause Initial Schedule";
1299 break;
1300 }
1301
1302 return OS;
1303}
1304#endif
1305
1306GCNSchedStage::GCNSchedStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
1307 : DAG(DAG), S(static_cast<GCNSchedStrategy &>(*DAG.SchedImpl)), MF(DAG.MF),
1308 MFI(DAG.MFI), ST(DAG.ST), StageID(StageID) {}
1309
1310bool GCNSchedStage::initGCNSchedStage() {
1311 if (!DAG.LIS)
1312 return false;
1313
1314 LLVM_DEBUG(dbgs() << "Starting scheduling stage: " << StageID << "\n");
1315 return true;
1316}
1317
1318void RewriteMFMAFormStage::findReachingDefs(
1319 MachineOperand &UseMO, LiveIntervals *LIS,
1320 SmallVectorImpl<SlotIndex> &DefIdxs) {
1321 MachineInstr *UseMI = UseMO.getParent();
1322 LiveInterval &UseLI = LIS->getInterval(Reg: UseMO.getReg());
1323 VNInfo *VNI = UseLI.getVNInfoAt(Idx: LIS->getInstructionIndex(Instr: *UseMI));
1324
1325 // If the def is not a PHI, then it must be the only reaching def.
1326 if (!VNI->isPHIDef()) {
1327 DefIdxs.push_back(Elt: VNI->def);
1328 return;
1329 }
1330
1331 SmallPtrSet<MachineBasicBlock *, 8> Visited = {UseMI->getParent()};
1332 SmallVector<MachineBasicBlock *, 8> Worklist;
1333
1334 // Mark the predecessor blocks for traversal
1335 for (MachineBasicBlock *PredMBB : UseMI->getParent()->predecessors()) {
1336 Worklist.push_back(Elt: PredMBB);
1337 Visited.insert(Ptr: PredMBB);
1338 }
1339
1340 while (!Worklist.empty()) {
1341 MachineBasicBlock *CurrMBB = Worklist.pop_back_val();
1342
1343 SlotIndex CurrMBBEnd = LIS->getMBBEndIdx(mbb: CurrMBB);
1344 VNInfo *VNI = UseLI.getVNInfoAt(Idx: CurrMBBEnd.getPrevSlot());
1345
1346 MachineBasicBlock *DefMBB = LIS->getMBBFromIndex(index: VNI->def);
1347
1348 // If there is a def in this block, then add it to the list. This is the
1349 // reaching def of this path.
1350 if (!VNI->isPHIDef()) {
1351 DefIdxs.push_back(Elt: VNI->def);
1352 continue;
1353 }
1354
1355 for (MachineBasicBlock *PredMBB : DefMBB->predecessors()) {
1356 if (Visited.insert(Ptr: PredMBB).second)
1357 Worklist.push_back(Elt: PredMBB);
1358 }
1359 }
1360}
1361
1362void RewriteMFMAFormStage::findReachingUses(
1363 const MachineInstr *DefMI, LiveIntervals *LIS,
1364 SmallVectorImpl<MachineOperand *> &ReachingUses) {
1365 SlotIndex DefIdx = LIS->getInstructionIndex(Instr: *DefMI);
1366 for (MachineOperand &UseMO :
1367 DAG.MRI.use_nodbg_operands(Reg: DefMI->getOperand(i: 0).getReg())) {
1368 SmallVector<SlotIndex, 8> ReachingDefIndexes;
1369 findReachingDefs(UseMO, LIS, DefIdxs&: ReachingDefIndexes);
1370
1371 // If we find a use that contains this DefMI in its reachingDefs, then it is
1372 // a reaching use.
1373 if (any_of(Range&: ReachingDefIndexes, P: [DefIdx](SlotIndex RDIdx) {
1374 return SlotIndex::isSameInstr(A: RDIdx, B: DefIdx);
1375 }))
1376 ReachingUses.push_back(Elt: &UseMO);
1377 }
1378}
1379
1380bool RewriteMFMAFormStage::initGCNSchedStage() {
1381 // We only need to run this pass if the architecture supports AGPRs.
1382 // Additionally, we don't use AGPRs at occupancy levels above 1 so there
1383 // is no need for this pass in that case, either.
1384 const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
1385 if (!ST.hasGFX90AInsts() || MFI.getMinWavesPerEU() > 1)
1386 return false;
1387
1388 RegionsWithExcessArchVGPR.resize(N: DAG.Regions.size());
1389 RegionsWithExcessArchVGPR.reset();
1390 for (unsigned Region = 0; Region < DAG.Regions.size(); Region++) {
1391 GCNRegPressure PressureBefore = DAG.Pressure[Region];
1392 if (PressureBefore.getArchVGPRNum() > ST.getAddressableNumArchVGPRs())
1393 RegionsWithExcessArchVGPR[Region] = true;
1394 }
1395
1396 if (RegionsWithExcessArchVGPR.none())
1397 return false;
1398
1399 TII = ST.getInstrInfo();
1400 SRI = ST.getRegisterInfo();
1401
1402 std::vector<std::pair<MachineInstr *, unsigned>> RewriteCands;
1403 DenseMap<MachineBasicBlock *, std::set<Register>> CopyForUse;
1404 SmallPtrSet<MachineInstr *, 8> CopyForDef;
1405
1406 if (!initHeuristics(RewriteCands, CopyForUse, CopyForDef))
1407 return false;
1408
1409 int64_t Cost = getRewriteCost(RewriteCands, CopyForUse, CopyForDef);
1410
1411 // If we haven't found the beneficial conditions, prefer the VGPR form which
1412 // may result in less cross RC copies.
1413 if (Cost > 0)
1414 return false;
1415
1416 return rewrite(RewriteCands);
1417}
1418
1419bool UnclusteredHighRPStage::initGCNSchedStage() {
1420 if (DisableUnclusterHighRP)
1421 return false;
1422
1423 if (!GCNSchedStage::initGCNSchedStage())
1424 return false;
1425
1426 if (DAG.RegionsWithHighRP.none() && DAG.RegionsWithExcessRP.none())
1427 return false;
1428
1429 SavedMutations.swap(x&: DAG.Mutations);
1430 DAG.addMutation(
1431 Mutation: createIGroupLPDAGMutation(Phase: AMDGPU::SchedulingPhase::PreRAReentry));
1432
1433 InitialOccupancy = DAG.MinOccupancy;
1434 // Aggressively try to reduce register pressure in the unclustered high RP
1435 // stage. Temporarily increase occupancy target in the region.
1436 TempTargetOccupancy = MFI.getMaxWavesPerEU() > DAG.MinOccupancy
1437 ? InitialOccupancy + 1
1438 : InitialOccupancy;
1439 IsAnyRegionScheduled = false;
1440 S.SGPRLimitBias = S.HighRPSGPRBias;
1441 S.VGPRLimitBias = S.HighRPVGPRBias;
1442
1443 LLVM_DEBUG(
1444 dbgs()
1445 << "Retrying function scheduling without clustering. "
1446 "Aggressively try to reduce register pressure to achieve occupancy "
1447 << TempTargetOccupancy << ".\n");
1448
1449 return true;
1450}
1451
1452bool ClusteredLowOccStage::initGCNSchedStage() {
1453 if (DisableClusteredLowOccupancy)
1454 return false;
1455
1456 if (!GCNSchedStage::initGCNSchedStage())
1457 return false;
1458
1459 // Don't bother trying to improve ILP in lower RP regions if occupancy has not
1460 // been dropped. All regions will have already been scheduled with the ideal
1461 // occupancy targets.
1462 if (DAG.StartingOccupancy <= DAG.MinOccupancy)
1463 return false;
1464
1465 LLVM_DEBUG(
1466 dbgs() << "Retrying function scheduling with lowest recorded occupancy "
1467 << DAG.MinOccupancy << ".\n");
1468 return true;
1469}
1470
1471/// Allows to easily filter for this stage's debug output.
1472#define REMAT_PREFIX "[PreRARemat] "
1473#define REMAT_DEBUG(X) LLVM_DEBUG(dbgs() << REMAT_PREFIX; X;)
1474
1475#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1476Printable PreRARematStage::ScoredRemat::print() const {
1477 return Printable([&](raw_ostream &OS) {
1478 OS << '(' << MaxFreq << ", " << FreqDiff << ", " << RegionImpact << ')';
1479 });
1480}
1481#endif
1482
1483bool PreRARematStage::initGCNSchedStage() {
1484 // FIXME: This pass will invalidate cached BBLiveInMap and MBBLiveIns for
1485 // regions inbetween the defs and region we sinked the def to. Will need to be
1486 // fixed if there is another pass after this pass.
1487 assert(!S.hasNextStage());
1488
1489 if (!GCNSchedStage::initGCNSchedStage() || DAG.Regions.size() <= 1)
1490 return false;
1491
1492#ifndef NDEBUG
1493 auto PrintTargetRegions = [&]() -> void {
1494 if (TargetRegions.none()) {
1495 dbgs() << REMAT_PREFIX << "No target regions\n";
1496 return;
1497 }
1498 dbgs() << REMAT_PREFIX << "Target regions:\n";
1499 for (unsigned I : TargetRegions.set_bits())
1500 dbgs() << REMAT_PREFIX << " [" << I << "] " << RPTargets[I] << '\n';
1501 };
1502#endif
1503
1504 // Set an objective for the stage based on current RP in each region.
1505 REMAT_DEBUG({
1506 dbgs() << "Analyzing ";
1507 MF.getFunction().printAsOperand(dbgs(), false);
1508 dbgs() << ": ";
1509 });
1510 if (!setObjective()) {
1511 LLVM_DEBUG(dbgs() << "no objective to achieve, occupancy is maximal at "
1512 << MFI.getMaxWavesPerEU() << '\n');
1513 return false;
1514 }
1515 LLVM_DEBUG({
1516 if (TargetOcc) {
1517 dbgs() << "increase occupancy from " << *TargetOcc - 1 << '\n';
1518 } else {
1519 dbgs() << "reduce spilling (minimum target occupancy is "
1520 << MFI.getMinWavesPerEU() << ")\n";
1521 }
1522 PrintTargetRegions();
1523 });
1524
1525 // We need up-to-date live-out info. to query live-out register masks in
1526 // regions containing rematerializable instructions.
1527 DAG.RegionLiveOuts.buildLiveRegMap();
1528
1529 if (!Remater.analyze()) {
1530 REMAT_DEBUG(dbgs() << "No rematerializable registers\n");
1531 return false;
1532 }
1533 const ScoredRemat::FreqInfo FreqInfo(MF, DAG);
1534
1535 // Set of registers already marked for potential remterialization; used to
1536 // avoid rematerialization chains.
1537 SmallSet<Register, 4> MarkedRegs;
1538
1539 // Collect candidates. We have more restrictions on what we can track here
1540 // compared to the rematerializer.
1541 SmallVector<ScoredRemat, 8> Candidates;
1542 // Map registers to candidate indices. Use ~0u as null value
1543 // since 0 is a valid index.
1544 IndexedMap<unsigned, VirtReg2IndexFunctor> DefRegToCandIdx(~0u);
1545 DefRegToCandIdx.resize(S: DAG.MRI.getNumVirtRegs());
1546 const unsigned NumRegions = DAG.Regions.size();
1547
1548 for (unsigned RegIdx = 0, E = Remater.getNumRegs(); RegIdx < E; ++RegIdx) {
1549 const Rematerializer::Reg &CandReg = Remater.getReg(RegIdx);
1550
1551 // All users must be in a single region.
1552 if (CandReg.Uses.size() != 1)
1553 continue;
1554 const auto [UseRegion, Users] = *CandReg.Uses.begin();
1555
1556 // Rematerialization moves the defining instruction into the region of its
1557 // use, which may sit under different control dependencies (e.g., across a
1558 // change of EXEC). Convergent operations must not be made control-dependent
1559 // on additional values, so they cannot be safely relocated this way. This
1560 // mirrors the check MachineSink performs before sinking an instruction.
1561 if (any_of(Range: CandReg.Defs,
1562 P: [](const MachineInstr *DefMI) { return DefMI->isConvergent(); }))
1563 continue;
1564
1565 // We further filter the registers that we can rematerialize based on our
1566 // current tracking capabilities in the stage. Users cannot themselves be
1567 // marked rematerializable, and no register operand of the defining MI can
1568 // be marked rematerializable. We also do not rematerialize an instruction
1569 // if it uses registers that aren't available at its use. This ensures that
1570 // we are not extending any live range while rematerializing.
1571 if (llvm::any_of(Range: Users, P: [&MarkedRegs](const MachineInstr *UserMI) {
1572 assert(UserMI->getNumOperands() > 0 &&
1573 "user must have at least one operand");
1574 const MachineOperand &UseMO = UserMI->getOperand(i: 0);
1575 return UseMO.isReg() && MarkedRegs.contains(V: UseMO.getReg());
1576 }))
1577 continue;
1578 MachineInstr *FirstUseMI =
1579 CandReg.getRegionUseBounds(UseRegion, LIS: *DAG.LIS).first;
1580 assert(FirstUseMI && "there must be a user in the region");
1581 SlotIndex FirstUseIdx =
1582 DAG.LIS->getInstructionIndex(Instr: *FirstUseMI).getRegSlot(EC: true);
1583 SlotIndex RefIdx =
1584 DAG.LIS->getInstructionIndex(Instr: *CandReg.getLastDef()).getRegSlot(EC: true);
1585 if (llvm::any_of(Range: CandReg.Dependencies, P: [&](RegisterIdx DepRegIdx) {
1586 const Rematerializer::Reg &DepReg = Remater.getReg(RegIdx: DepRegIdx);
1587 Register DepDefReg = DepReg.getDefReg();
1588 return MarkedRegs.contains(V: DepDefReg) ||
1589 !Remater.isRegIdenticalAtUses(Reg: DepDefReg, Mask: DepReg.Mask, RefSlot: RefIdx,
1590 Uses: {FirstUseIdx});
1591 }))
1592 continue;
1593 if (llvm::any_of(Range: Remater.getUnrematableDeps(RegIdx),
1594 P: [&](const std::pair<Register, LaneBitmask> &RegAndMask) {
1595 const auto &[Reg, Mask] = RegAndMask;
1596 return !Remater.isRegIdenticalAtUses(Reg, Mask, RefSlot: RefIdx,
1597 Uses: {FirstUseIdx});
1598 }))
1599 continue;
1600
1601 Register DefReg = CandReg.getDefReg();
1602 MarkedRegs.insert(V: DefReg);
1603 DefRegToCandIdx[DefReg] = Candidates.size();
1604 Candidates.emplace_back(Args&: RegIdx, Args: NumRegions);
1605 }
1606
1607 // Initialize the LiveIn and LiveOut sets of all candidates.
1608 // Iterating all regions and their live regs once is considerably
1609 // more efficient than querying those structures for each candidate
1610 // separately in ScoredRemat::init.
1611 for (unsigned I = 0; I < NumRegions; ++I) {
1612 for (const auto &[Reg, Mask] : DAG.LiveIns[I]) {
1613 if (!Register::isVirtualRegister(Reg))
1614 continue;
1615 unsigned CandIdx = DefRegToCandIdx[Reg];
1616 if (CandIdx != ~0u)
1617 Candidates[CandIdx].LiveIn.set(I);
1618 }
1619 for (const auto &[Reg, Mask] :
1620 DAG.RegionLiveOuts.getLiveRegsForRegionIdx(RegionIdx: I)) {
1621 if (!Register::isVirtualRegister(Reg))
1622 continue;
1623 unsigned CandIdx = DefRegToCandIdx[Reg];
1624 if (CandIdx != ~0u)
1625 Candidates[CandIdx].LiveOut.set(I);
1626 }
1627 }
1628
1629 // Finish initializing candidates.
1630 SmallVector<unsigned> CandidateOrder;
1631 for (auto [CandIdx, Cand] : enumerate(First&: Candidates)) {
1632 Cand.init(Freq: FreqInfo, Remater, DAG);
1633 Cand.update(TargetRegions, RPTargets, Freq: FreqInfo, ReduceSpill: !TargetOcc);
1634 if (!Cand.hasNullScore())
1635 CandidateOrder.push_back(Elt: CandIdx);
1636 }
1637
1638 if (TargetOcc) {
1639 // Every rematerialization we do here is likely to move the instruction
1640 // into a higher frequency region, increasing the total sum latency of the
1641 // instruction itself. This is acceptable if we are eliminating a spill in
1642 // the process, but when the goal is increasing occupancy we get nothing
1643 // out of rematerialization if occupancy is not increased in the end; in
1644 // such cases we want to roll back the rematerialization.
1645 Rollback = std::make_unique<RollbackSupport>(args&: Remater);
1646 }
1647
1648 // Rematerialize registers in successive rounds until all RP targets are
1649 // satisifed or until we run out of rematerialization candidates.
1650 BitVector RecomputeRP(DAG.Regions.size());
1651 for (;;) {
1652 RecomputeRP.reset();
1653
1654 // Sort candidates in increasing score order.
1655 sort(C&: CandidateOrder, Comp: [&](unsigned LHSIndex, unsigned RHSIndex) {
1656 return Candidates[LHSIndex] < Candidates[RHSIndex];
1657 });
1658
1659 REMAT_DEBUG({
1660 dbgs() << "==== NEW REMAT ROUND ====\n"
1661 << REMAT_PREFIX
1662 << "Candidates with non-null score, in rematerialization order:\n";
1663 for (const ScoredRemat &Cand : reverse(Candidates)) {
1664 dbgs() << REMAT_PREFIX << " " << Cand.print() << " | "
1665 << Remater.printRematReg(Cand.RegIdx) << '\n';
1666 }
1667 PrintTargetRegions();
1668 });
1669
1670 // Rematerialize registers in decreasing score order until we estimate
1671 // that all RP targets are satisfied or until rematerialization candidates
1672 // are no longer useful to decrease RP.
1673 while (!CandidateOrder.empty()) {
1674 const ScoredRemat &Cand = Candidates[CandidateOrder.back()];
1675 const Rematerializer::Reg &Reg = Remater.getReg(RegIdx: Cand.RegIdx);
1676
1677 // When previous rematerializations in this round have already satisfied
1678 // RP targets in all regions this rematerialization can impact, we have a
1679 // good indication that our scores have diverged significantly from
1680 // reality, in which case we interrupt this round and re-score. This also
1681 // ensures that every rematerialization we perform is possibly impactful
1682 // in at least one target region.
1683 if (!Cand.maybeBeneficial(TargetRegions, RPTargets)) {
1684 REMAT_DEBUG(dbgs() << "Interrupt round on stale score for "
1685 << Cand.print() << " | "
1686 << Remater.printRematReg(Cand.RegIdx));
1687 break;
1688 }
1689 CandidateOrder.pop_back();
1690
1691#ifdef EXPENSIVE_CHECKS
1692 // All uses are known to be available / live at the remat point. Thus,
1693 // the uses should already be live in to the using region.
1694 for (const MachineInstr *DefMI : Reg.Defs) {
1695 for (const MachineOperand &MO : DefMI->operands()) {
1696 // Exclude the defined register. We are rematerializing all
1697 // instructions defining it so we don't care that its value is
1698 // available at the remat point.
1699 if (!MO.isReg() || !MO.getReg() || !MO.readsReg() || MO.isDef())
1700 continue;
1701
1702 Register UseReg = MO.getReg();
1703 if (!UseReg.isVirtual())
1704 continue;
1705
1706 LiveInterval &LI = DAG.LIS->getInterval(UseReg);
1707 LaneBitmask LM = DAG.MRI.getMaxLaneMaskForVReg(MO.getReg());
1708 if (LI.hasSubRanges() && MO.getSubReg())
1709 LM = DAG.TRI->getSubRegIndexLaneMask(MO.getSubReg());
1710
1711 const unsigned UseRegion = Reg.Uses.begin()->first;
1712 LaneBitmask LiveInMask = DAG.LiveIns[UseRegion].at(UseReg);
1713 LaneBitmask UncoveredLanes = LM & ~(LiveInMask & LM);
1714 // If this register has lanes not covered by the LiveIns, be sure they
1715 // do not map to any subrange. ref:
1716 // machine-scheduler-sink-trivial-remats.mir::omitted_subrange
1717 if (UncoveredLanes.any()) {
1718 assert(LI.hasSubRanges());
1719 for (LiveInterval::SubRange &SR : LI.subranges())
1720 assert((SR.LaneMask & UncoveredLanes).none());
1721 }
1722 }
1723 }
1724#endif
1725
1726 // Remove the register from all regions where it is a live-in or live-out,
1727 // then rematerialize the register.
1728 REMAT_DEBUG(dbgs() << "** REMAT " << Remater.printRematReg(Cand.RegIdx)
1729 << '\n');
1730 removeFromLiveMaps(Reg: Reg.getDefReg(), LiveIn: Cand.LiveIn, LiveOut: Cand.LiveOut);
1731 if (Rollback) {
1732 Rollback->LiveMapUpdates.emplace_back(Args: Cand.RegIdx, Args: Cand.LiveIn,
1733 Args: Cand.LiveOut);
1734 }
1735 Cand.rematerialize(Remater);
1736
1737 // Adjust RP targets. The save is guaranteed in regions in which the
1738 // register is live-through and unused but optimistic in all other regions
1739 // where the register is live.
1740 updateRPTargets(Regions: Cand.Live, RPSave: Cand.RPSave);
1741 RecomputeRP |= Cand.UnpredictableRPSave;
1742 RescheduleRegions |= Cand.Live;
1743 if (!TargetRegions.any()) {
1744 REMAT_DEBUG(dbgs() << "All targets cleared, verifying...\n");
1745 break;
1746 }
1747 }
1748
1749 if (!updateAndVerifyRPTargets(Regions: RecomputeRP) && !TargetRegions.any()) {
1750 REMAT_DEBUG(dbgs() << "Objectives achieved!\n");
1751 break;
1752 }
1753
1754 // Update the score of remaining candidates and filter out those that have
1755 // become useless from the vector. Candidates never become useful after
1756 // having been useless for a round, so we can freely drop them without
1757 // losing any future rematerialization opportunity.
1758 unsigned NumUsefulCandidates = 0;
1759 for (unsigned CandIdx : CandidateOrder) {
1760 ScoredRemat &Candidate = Candidates[CandIdx];
1761 Candidate.update(TargetRegions, RPTargets, Freq: FreqInfo, ReduceSpill: !TargetOcc);
1762 if (!Candidate.hasNullScore())
1763 CandidateOrder[NumUsefulCandidates++] = CandIdx;
1764 }
1765 if (NumUsefulCandidates == 0) {
1766 REMAT_DEBUG(dbgs() << "Stop on exhausted rematerialization candidates\n");
1767 break;
1768 }
1769 CandidateOrder.truncate(N: NumUsefulCandidates);
1770 }
1771
1772 if (RescheduleRegions.none())
1773 return false;
1774
1775 // Commit all pressure changes to the DAG and compute minimum achieved
1776 // occupancy in impacted regions.
1777 REMAT_DEBUG(dbgs() << "==== REMAT RESULTS ====\n");
1778 unsigned DynamicVGPRBlockSize = MFI.getDynamicVGPRBlockSize();
1779 for (unsigned I : RescheduleRegions.set_bits()) {
1780 DAG.Pressure[I] = RPTargets[I].getCurrentRP();
1781 REMAT_DEBUG(dbgs() << '[' << I << "] Achieved occupancy "
1782 << DAG.Pressure[I].getOccupancy(ST, DynamicVGPRBlockSize)
1783 << " (" << RPTargets[I] << ")\n");
1784 }
1785 AchievedOcc = MFI.getMaxWavesPerEU();
1786 for (const GCNRegPressure &RP : DAG.Pressure) {
1787 AchievedOcc =
1788 std::min(a: AchievedOcc, b: RP.getOccupancy(ST, DynamicVGPRBlockSize));
1789 }
1790
1791 REMAT_DEBUG({
1792 dbgs() << "Retrying function scheduling with new min. occupancy of "
1793 << AchievedOcc << " from rematerializing (original was "
1794 << DAG.MinOccupancy;
1795 if (TargetOcc)
1796 dbgs() << ", target was " << *TargetOcc;
1797 dbgs() << ")\n";
1798 });
1799
1800 DAG.setTargetOccupancy(getStageTargetOccupancy());
1801 return true;
1802}
1803
1804void GCNSchedStage::finalizeGCNSchedStage() {
1805 DAG.finishBlock();
1806 LLVM_DEBUG(dbgs() << "Ending scheduling stage: " << StageID << "\n");
1807}
1808
1809void UnclusteredHighRPStage::finalizeGCNSchedStage() {
1810 SavedMutations.swap(x&: DAG.Mutations);
1811 S.SGPRLimitBias = S.VGPRLimitBias = 0;
1812 if (DAG.MinOccupancy > InitialOccupancy) {
1813 assert(IsAnyRegionScheduled);
1814 LLVM_DEBUG(dbgs() << StageID
1815 << " stage successfully increased occupancy to "
1816 << DAG.MinOccupancy << '\n');
1817 } else if (!IsAnyRegionScheduled) {
1818 assert(DAG.MinOccupancy == InitialOccupancy);
1819 LLVM_DEBUG(dbgs() << StageID
1820 << ": No regions scheduled, min occupancy stays at "
1821 << DAG.MinOccupancy << ", MFI occupancy stays at "
1822 << MFI.getOccupancy() << ".\n");
1823 }
1824
1825 GCNSchedStage::finalizeGCNSchedStage();
1826}
1827
1828bool GCNSchedStage::initGCNRegion() {
1829 // Skip empty scheduling region.
1830 if (DAG.begin() == DAG.end())
1831 return false;
1832
1833 // Check whether this new region is also a new block.
1834 if (DAG.RegionBegin->getParent() != CurrentMBB)
1835 setupNewBlock();
1836
1837 unsigned NumRegionInstrs = std::distance(first: DAG.begin(), last: DAG.end());
1838 DAG.enterRegion(bb: CurrentMBB, begin: DAG.begin(), end: DAG.end(), regioninstrs: NumRegionInstrs);
1839
1840 // Skip regions with 1 schedulable instruction.
1841 if (DAG.begin() == std::prev(x: DAG.end()))
1842 return false;
1843
1844 LLVM_DEBUG(dbgs() << "********** MI Scheduling **********\n");
1845 LLVM_DEBUG(dbgs() << MF.getName() << ":" << printMBBReference(*CurrentMBB)
1846 << " " << CurrentMBB->getName()
1847 << "\n From: " << *DAG.begin() << " To: ";
1848 if (DAG.RegionEnd != CurrentMBB->end()) dbgs() << *DAG.RegionEnd;
1849 else dbgs() << "End";
1850 dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n');
1851
1852 // Save original instruction order before scheduling for possible revert.
1853 Unsched.clear();
1854 Unsched.reserve(n: DAG.NumRegionInstrs);
1855 if (StageID == GCNSchedStageID::OccInitialSchedule ||
1856 StageID == GCNSchedStageID::ILPInitialSchedule) {
1857 const SIInstrInfo *SII = static_cast<const SIInstrInfo *>(DAG.TII);
1858 for (auto &I : DAG) {
1859 Unsched.push_back(x: &I);
1860 if (SII->isIGLPMutationOnly(Opcode: I.getOpcode()))
1861 DAG.RegionsWithIGLPInstrs[RegionIdx] = true;
1862 }
1863 } else {
1864 for (auto &I : DAG)
1865 Unsched.push_back(x: &I);
1866 }
1867
1868 PressureBefore = DAG.Pressure[RegionIdx];
1869
1870 LLVM_DEBUG(
1871 dbgs() << "Pressure before scheduling:\nRegion live-ins:"
1872 << print(DAG.LiveIns[RegionIdx], DAG.MRI)
1873 << "Region live-in pressure: "
1874 << print(llvm::getRegPressure(DAG.MRI, DAG.LiveIns[RegionIdx]))
1875 << "Region register pressure: " << print(PressureBefore));
1876
1877 S.HasHighPressure = false;
1878 S.KnownExcessRP = isRegionWithExcessRP();
1879
1880 if (DAG.RegionsWithIGLPInstrs[RegionIdx] &&
1881 StageID != GCNSchedStageID::UnclusteredHighRPReschedule) {
1882 SavedMutations.clear();
1883 SavedMutations.swap(x&: DAG.Mutations);
1884 bool IsInitialStage = StageID == GCNSchedStageID::OccInitialSchedule ||
1885 StageID == GCNSchedStageID::ILPInitialSchedule;
1886 DAG.addMutation(Mutation: createIGroupLPDAGMutation(
1887 Phase: IsInitialStage ? AMDGPU::SchedulingPhase::Initial
1888 : AMDGPU::SchedulingPhase::PreRAReentry));
1889 }
1890
1891 return true;
1892}
1893
1894bool UnclusteredHighRPStage::initGCNRegion() {
1895 // Only reschedule regions that have excess register pressure (i.e. spilling)
1896 // or had minimum occupancy at the beginning of the stage (as long as
1897 // rescheduling of previous regions did not make occupancy drop back down to
1898 // the initial minimum).
1899 unsigned DynamicVGPRBlockSize = DAG.MFI.getDynamicVGPRBlockSize();
1900 // If no region has been scheduled yet, the DAG has not yet been updated with
1901 // the occupancy target. So retrieve it from the temporary.
1902 unsigned CurrentTargetOccupancy =
1903 IsAnyRegionScheduled ? DAG.MinOccupancy : TempTargetOccupancy;
1904 if (!DAG.RegionsWithExcessRP[RegionIdx] &&
1905 (CurrentTargetOccupancy <= InitialOccupancy ||
1906 DAG.Pressure[RegionIdx].getOccupancy(ST, DynamicVGPRBlockSize) !=
1907 InitialOccupancy))
1908 return false;
1909
1910 bool IsSchedulingThisRegion = GCNSchedStage::initGCNRegion();
1911 // If this is the first region scheduled during this stage, make the target
1912 // occupancy changes in the DAG and MFI.
1913 if (!IsAnyRegionScheduled && IsSchedulingThisRegion) {
1914 IsAnyRegionScheduled = true;
1915 if (MFI.getMaxWavesPerEU() > DAG.MinOccupancy)
1916 DAG.setTargetOccupancy(TempTargetOccupancy);
1917 }
1918 return IsSchedulingThisRegion;
1919}
1920
1921bool ClusteredLowOccStage::initGCNRegion() {
1922 // We may need to reschedule this region if it wasn't rescheduled in the last
1923 // stage, or if we found it was testing critical register pressure limits in
1924 // the unclustered reschedule stage. The later is because we may not have been
1925 // able to raise the min occupancy in the previous stage so the region may be
1926 // overly constrained even if it was already rescheduled.
1927 if (!DAG.RegionsWithHighRP[RegionIdx])
1928 return false;
1929
1930 return GCNSchedStage::initGCNRegion();
1931}
1932
1933bool PreRARematStage::initGCNRegion() {
1934 return !RevertAllRegions && RescheduleRegions[RegionIdx] &&
1935 GCNSchedStage::initGCNRegion();
1936}
1937
1938void GCNSchedStage::setupNewBlock() {
1939 if (CurrentMBB)
1940 DAG.finishBlock();
1941
1942 CurrentMBB = DAG.RegionBegin->getParent();
1943 DAG.startBlock(bb: CurrentMBB);
1944 // Get real RP for the region if it hasn't be calculated before. After the
1945 // initial schedule stage real RP will be collected after scheduling.
1946 if (StageID == GCNSchedStageID::OccInitialSchedule ||
1947 StageID == GCNSchedStageID::ILPInitialSchedule ||
1948 StageID == GCNSchedStageID::MemoryClauseInitialSchedule)
1949 DAG.computeBlockPressure(RegionIdx, MBB: CurrentMBB);
1950}
1951
1952void GCNSchedStage::finalizeGCNRegion() {
1953 DAG.Regions[RegionIdx] = std::pair(DAG.RegionBegin, DAG.RegionEnd);
1954 if (S.HasHighPressure)
1955 DAG.RegionsWithHighRP[RegionIdx] = true;
1956
1957 // Revert scheduling if we have dropped occupancy or there is some other
1958 // reason that the original schedule is better.
1959 checkScheduling();
1960
1961 if (DAG.RegionsWithIGLPInstrs[RegionIdx] &&
1962 StageID != GCNSchedStageID::UnclusteredHighRPReschedule)
1963 SavedMutations.swap(x&: DAG.Mutations);
1964}
1965
1966void PreRARematStage::finalizeGCNRegion() {
1967 GCNSchedStage::finalizeGCNRegion();
1968 // When the goal is to increase occupancy, all regions must reach the target
1969 // occupancy for rematerializations to be possibly useful, otherwise we will
1970 // just hurt latency for no benefit. If minimum occupancy drops below the
1971 // target there is no point in trying to re-schedule further regions.
1972 if (!TargetOcc)
1973 return;
1974 RegionReverts.emplace_back(Args&: RegionIdx, Args&: Unsched, Args&: PressureBefore);
1975 if (DAG.MinOccupancy < *TargetOcc) {
1976 REMAT_DEBUG(dbgs() << "Region " << RegionIdx
1977 << " cannot meet occupancy target, interrupting "
1978 "re-scheduling in all regions\n");
1979 RevertAllRegions = true;
1980 }
1981}
1982
1983void GCNSchedStage::checkScheduling() {
1984 // Check the results of scheduling.
1985 PressureAfter = DAG.getRealRegPressure(RegionIdx);
1986
1987 LLVM_DEBUG(dbgs() << "Pressure after scheduling: " << print(PressureAfter));
1988 LLVM_DEBUG(dbgs() << "Region: " << RegionIdx << ".\n");
1989
1990 unsigned DynamicVGPRBlockSize = DAG.MFI.getDynamicVGPRBlockSize();
1991
1992 if (PressureAfter.getSGPRNum() <= S.SGPRCriticalLimit &&
1993 PressureAfter.getVGPRNum(UnifiedVGPRFile: ST.hasGFX90AInsts()) <= S.VGPRCriticalLimit) {
1994 DAG.Pressure[RegionIdx] = PressureAfter;
1995
1996 // Early out if we have achieved the occupancy target.
1997 LLVM_DEBUG(dbgs() << "Pressure in desired limits, done.\n");
1998 return;
1999 }
2000
2001 unsigned TargetOccupancy = std::min(
2002 a: S.getTargetOccupancy(), b: ST.getOccupancyWithWorkGroupSizes(MF).second);
2003 unsigned WavesAfter = std::min(
2004 a: TargetOccupancy, b: PressureAfter.getOccupancy(ST, DynamicVGPRBlockSize));
2005 unsigned WavesBefore = std::min(
2006 a: TargetOccupancy, b: PressureBefore.getOccupancy(ST, DynamicVGPRBlockSize));
2007 LLVM_DEBUG(dbgs() << "Occupancy before scheduling: " << WavesBefore
2008 << ", after " << WavesAfter << ".\n");
2009
2010 // We may not be able to keep the current target occupancy because of the just
2011 // scheduled region. We might still be able to revert scheduling if the
2012 // occupancy before was higher, or if the current schedule has register
2013 // pressure higher than the excess limits which could lead to more spilling.
2014 unsigned NewOccupancy = std::max(a: WavesAfter, b: WavesBefore);
2015
2016 // Allow memory bound functions to drop to 4 waves if not limited by an
2017 // attribute.
2018 if (WavesAfter < WavesBefore && WavesAfter < DAG.MinOccupancy &&
2019 WavesAfter >= MFI.getMinAllowedOccupancy()) {
2020 LLVM_DEBUG(dbgs() << "Function is memory bound, allow occupancy drop up to "
2021 << MFI.getMinAllowedOccupancy() << " waves\n");
2022 NewOccupancy = WavesAfter;
2023 }
2024
2025 if (NewOccupancy < DAG.MinOccupancy) {
2026 DAG.MinOccupancy = NewOccupancy;
2027 MFI.limitOccupancy(Limit: DAG.MinOccupancy);
2028 LLVM_DEBUG(dbgs() << "Occupancy lowered for the function to "
2029 << DAG.MinOccupancy << ".\n");
2030 }
2031 // The maximum number of arch VGPR on non-unified register file, or the
2032 // maximum VGPR + AGPR in the unified register file case.
2033 unsigned MaxVGPRs = ST.getMaxNumVGPRs(MF);
2034 // The maximum number of arch VGPR for both unified and non-unified register
2035 // file.
2036 unsigned MaxArchVGPRs = std::min(a: MaxVGPRs, b: ST.getAddressableNumArchVGPRs());
2037 unsigned MaxSGPRs = ST.getMaxNumSGPRs(MF);
2038
2039 if (PressureAfter.getVGPRNum(UnifiedVGPRFile: ST.hasGFX90AInsts()) > MaxVGPRs ||
2040 PressureAfter.getArchVGPRNum() > MaxArchVGPRs ||
2041 PressureAfter.getAGPRNum() > MaxArchVGPRs ||
2042 PressureAfter.getSGPRNum() > MaxSGPRs) {
2043 DAG.RegionsWithHighRP[RegionIdx] = true;
2044 DAG.RegionsWithExcessRP[RegionIdx] = true;
2045 }
2046
2047 // Revert if this region's schedule would cause a drop in occupancy or
2048 // spilling.
2049 if (shouldRevertScheduling(WavesAfter)) {
2050 modifyRegionSchedule(RegionIdx, MIOrder: Unsched);
2051 std::tie(args&: DAG.RegionBegin, args&: DAG.RegionEnd) = DAG.Regions[RegionIdx];
2052 } else {
2053 DAG.Pressure[RegionIdx] = PressureAfter;
2054 }
2055}
2056
2057unsigned
2058GCNSchedStage::computeSUnitReadyCycle(const SUnit &SU, unsigned CurrCycle,
2059 DenseMap<unsigned, unsigned> &ReadyCycles,
2060 const TargetSchedModel &SM) {
2061 unsigned ReadyCycle = CurrCycle;
2062 for (auto &D : SU.Preds) {
2063 if (D.isAssignedRegDep()) {
2064 MachineInstr *DefMI = D.getSUnit()->getInstr();
2065 unsigned Latency = SM.computeInstrLatency(MI: DefMI);
2066 unsigned DefReady = ReadyCycles[DAG.getSUnit(MI: DefMI)->NodeNum];
2067 ReadyCycle = std::max(a: ReadyCycle, b: DefReady + Latency);
2068 }
2069 }
2070 ReadyCycles[SU.NodeNum] = ReadyCycle;
2071 return ReadyCycle;
2072}
2073
2074#ifndef NDEBUG
2075struct EarlierIssuingCycle {
2076 bool operator()(std::pair<MachineInstr *, unsigned> A,
2077 std::pair<MachineInstr *, unsigned> B) const {
2078 return A.second < B.second;
2079 }
2080};
2081
2082static void printScheduleModel(std::set<std::pair<MachineInstr *, unsigned>,
2083 EarlierIssuingCycle> &ReadyCycles) {
2084 if (ReadyCycles.empty())
2085 return;
2086 unsigned BBNum = ReadyCycles.begin()->first->getParent()->getNumber();
2087 dbgs() << "\n################## Schedule time ReadyCycles for MBB : " << BBNum
2088 << " ##################\n# Cycle #\t\t\tInstruction "
2089 " "
2090 " \n";
2091 unsigned IPrev = 1;
2092 for (auto &I : ReadyCycles) {
2093 if (I.second > IPrev + 1)
2094 dbgs() << "****************************** BUBBLE OF " << I.second - IPrev
2095 << " CYCLES DETECTED ******************************\n\n";
2096 dbgs() << "[ " << I.second << " ] : " << *I.first << "\n";
2097 IPrev = I.second;
2098 }
2099}
2100#endif
2101
2102ScheduleMetrics
2103GCNSchedStage::getScheduleMetrics(const std::vector<SUnit> &InputSchedule) {
2104#ifndef NDEBUG
2105 std::set<std::pair<MachineInstr *, unsigned>, EarlierIssuingCycle>
2106 ReadyCyclesSorted;
2107#endif
2108 const TargetSchedModel &SM = ST.getInstrInfo()->getSchedModel();
2109 unsigned SumBubbles = 0;
2110 DenseMap<unsigned, unsigned> ReadyCycles;
2111 unsigned CurrCycle = 0;
2112 for (auto &SU : InputSchedule) {
2113 unsigned ReadyCycle =
2114 computeSUnitReadyCycle(SU, CurrCycle, ReadyCycles, SM);
2115 SumBubbles += ReadyCycle - CurrCycle;
2116#ifndef NDEBUG
2117 ReadyCyclesSorted.insert(std::make_pair(SU.getInstr(), ReadyCycle));
2118#endif
2119 CurrCycle = ++ReadyCycle;
2120 }
2121#ifndef NDEBUG
2122 LLVM_DEBUG(
2123 printScheduleModel(ReadyCyclesSorted);
2124 dbgs() << "\n\t"
2125 << "Metric: "
2126 << (SumBubbles
2127 ? (SumBubbles * ScheduleMetrics::ScaleFactor) / CurrCycle
2128 : 1)
2129 << "\n\n");
2130#endif
2131
2132 return ScheduleMetrics(CurrCycle, SumBubbles);
2133}
2134
2135ScheduleMetrics
2136GCNSchedStage::getScheduleMetrics(const GCNScheduleDAGMILive &DAG) {
2137#ifndef NDEBUG
2138 std::set<std::pair<MachineInstr *, unsigned>, EarlierIssuingCycle>
2139 ReadyCyclesSorted;
2140#endif
2141 const TargetSchedModel &SM = ST.getInstrInfo()->getSchedModel();
2142 unsigned SumBubbles = 0;
2143 DenseMap<unsigned, unsigned> ReadyCycles;
2144 unsigned CurrCycle = 0;
2145 for (auto &MI : DAG) {
2146 SUnit *SU = DAG.getSUnit(MI: &MI);
2147 if (!SU)
2148 continue;
2149 unsigned ReadyCycle =
2150 computeSUnitReadyCycle(SU: *SU, CurrCycle, ReadyCycles, SM);
2151 SumBubbles += ReadyCycle - CurrCycle;
2152#ifndef NDEBUG
2153 ReadyCyclesSorted.insert(std::make_pair(SU->getInstr(), ReadyCycle));
2154#endif
2155 CurrCycle = ++ReadyCycle;
2156 }
2157#ifndef NDEBUG
2158 LLVM_DEBUG(
2159 printScheduleModel(ReadyCyclesSorted);
2160 dbgs() << "\n\t"
2161 << "Metric: "
2162 << (SumBubbles
2163 ? (SumBubbles * ScheduleMetrics::ScaleFactor) / CurrCycle
2164 : 1)
2165 << "\n\n");
2166#endif
2167
2168 return ScheduleMetrics(CurrCycle, SumBubbles);
2169}
2170
2171bool GCNSchedStage::shouldRevertScheduling(unsigned WavesAfter) {
2172 if (WavesAfter < DAG.MinOccupancy)
2173 return true;
2174
2175 // For dynamic VGPR mode, we don't want to waste any VGPR blocks.
2176 if (DAG.MFI.isDynamicVGPREnabled()) {
2177 unsigned BlocksBefore = AMDGPU::IsaInfo::getAllocatedNumVGPRBlocks(
2178 STI: ST, NumVGPRs: PressureBefore.getVGPRNum(UnifiedVGPRFile: false),
2179 DynamicVGPRBlockSize: DAG.MFI.getDynamicVGPRBlockSize());
2180 unsigned BlocksAfter = AMDGPU::IsaInfo::getAllocatedNumVGPRBlocks(
2181 STI: ST, NumVGPRs: PressureAfter.getVGPRNum(UnifiedVGPRFile: false), DynamicVGPRBlockSize: DAG.MFI.getDynamicVGPRBlockSize());
2182 if (BlocksAfter > BlocksBefore)
2183 return true;
2184 }
2185
2186 return false;
2187}
2188
2189bool OccInitialScheduleStage::shouldRevertScheduling(unsigned WavesAfter) {
2190 if (PressureAfter == PressureBefore)
2191 return false;
2192
2193 if (GCNSchedStage::shouldRevertScheduling(WavesAfter))
2194 return true;
2195
2196 if (mayCauseSpilling(WavesAfter))
2197 return true;
2198
2199 return false;
2200}
2201
2202bool UnclusteredHighRPStage::shouldRevertScheduling(unsigned WavesAfter) {
2203 // If RP is not reduced in the unclustered reschedule stage, revert to the
2204 // old schedule.
2205 if ((WavesAfter <=
2206 PressureBefore.getOccupancy(ST, DynamicVGPRBlockSize: DAG.MFI.getDynamicVGPRBlockSize()) &&
2207 mayCauseSpilling(WavesAfter)) ||
2208 GCNSchedStage::shouldRevertScheduling(WavesAfter)) {
2209 LLVM_DEBUG(dbgs() << "Unclustered reschedule did not help.\n");
2210 return true;
2211 }
2212
2213 // Do not attempt to relax schedule even more if we are already spilling.
2214 if (isRegionWithExcessRP())
2215 return false;
2216
2217 LLVM_DEBUG(
2218 dbgs()
2219 << "\n\t *** In shouldRevertScheduling ***\n"
2220 << " *********** BEFORE UnclusteredHighRPStage ***********\n");
2221 ScheduleMetrics MBefore = getScheduleMetrics(InputSchedule: DAG.SUnits);
2222 LLVM_DEBUG(
2223 dbgs()
2224 << "\n *********** AFTER UnclusteredHighRPStage ***********\n");
2225 ScheduleMetrics MAfter = getScheduleMetrics(DAG);
2226 unsigned OldMetric = MBefore.getMetric();
2227 unsigned NewMetric = MAfter.getMetric();
2228 unsigned WavesBefore = std::min(
2229 a: S.getTargetOccupancy(),
2230 b: PressureBefore.getOccupancy(ST, DynamicVGPRBlockSize: DAG.MFI.getDynamicVGPRBlockSize()));
2231 unsigned Profit =
2232 ((WavesAfter * ScheduleMetrics::ScaleFactor) / WavesBefore *
2233 ((OldMetric + ScheduleMetricBias) * ScheduleMetrics::ScaleFactor) /
2234 NewMetric) /
2235 ScheduleMetrics::ScaleFactor;
2236 LLVM_DEBUG(dbgs() << "\tMetric before " << MBefore << "\tMetric after "
2237 << MAfter << "Profit: " << Profit << "\n");
2238 return Profit < ScheduleMetrics::ScaleFactor;
2239}
2240
2241bool ClusteredLowOccStage::shouldRevertScheduling(unsigned WavesAfter) {
2242 if (PressureAfter == PressureBefore)
2243 return false;
2244
2245 if (GCNSchedStage::shouldRevertScheduling(WavesAfter))
2246 return true;
2247
2248 if (mayCauseSpilling(WavesAfter))
2249 return true;
2250
2251 return false;
2252}
2253
2254bool PreRARematStage::shouldRevertScheduling(unsigned WavesAfter) {
2255 // When trying to increase occupancy (TargetOcc == true) the stage manages
2256 // region reverts globally (all or none), so we always return false here.
2257 return !TargetOcc && mayCauseSpilling(WavesAfter);
2258}
2259
2260bool ILPInitialScheduleStage::shouldRevertScheduling(unsigned WavesAfter) {
2261 if (mayCauseSpilling(WavesAfter))
2262 return true;
2263
2264 return false;
2265}
2266
2267bool MemoryClauseInitialScheduleStage::shouldRevertScheduling(
2268 unsigned WavesAfter) {
2269 return mayCauseSpilling(WavesAfter);
2270}
2271
2272bool GCNSchedStage::mayCauseSpilling(unsigned WavesAfter) {
2273 if (WavesAfter <= MFI.getMinWavesPerEU() && isRegionWithExcessRP() &&
2274 !PressureAfter.less(MF, O: PressureBefore)) {
2275 LLVM_DEBUG(dbgs() << "New pressure will result in more spilling.\n");
2276 return true;
2277 }
2278
2279 return false;
2280}
2281
2282void GCNSchedStage::modifyRegionSchedule(unsigned RegionIdx,
2283 ArrayRef<MachineInstr *> MIOrder) {
2284 assert(static_cast<size_t>(std::distance(DAG.Regions[RegionIdx].first,
2285 DAG.Regions[RegionIdx].second)) ==
2286 MIOrder.size() &&
2287 "instruction number mismatch");
2288 if (MIOrder.empty())
2289 return;
2290
2291 LLVM_DEBUG(dbgs() << "Reverting scheduling for region " << RegionIdx << '\n');
2292
2293 // Reconstruct MI sequence by moving instructions in desired order before
2294 // the current region's start.
2295 MachineBasicBlock::iterator RegionEnd = DAG.Regions[RegionIdx].first;
2296 MachineBasicBlock *MBB = MIOrder.front()->getParent();
2297 for (MachineInstr *MI : MIOrder) {
2298 // Either move the next MI in order before the end of the region or move the
2299 // region end past the MI if it is at the correct position.
2300 MachineBasicBlock::iterator MII = MI->getIterator();
2301 if (MII != RegionEnd) {
2302 // Will subsequent splice move MI up past a non-debug instruction?
2303 bool NonDebugReordered =
2304 !MI->isDebugInstr() &&
2305 skipDebugInstructionsForward(It: RegionEnd, End: MII) != MII;
2306 MBB->splice(Where: RegionEnd, Other: MBB, From: MI);
2307 // Only update LiveIntervals information if non-debug instructions are
2308 // reordered. Otherwise debug instructions could cause code generation to
2309 // change.
2310 if (NonDebugReordered)
2311 DAG.LIS->handleMove(MI&: *MI, UpdateFlags: true);
2312 } else {
2313 // MI is already at the expected position. However, earlier splices in
2314 // this loop may have changed neighboring slot indices, so this MI's
2315 // slot index can become non-monotonic w.r.t. the physical MBB order.
2316 // Only re-seat when monotonicity is actually violated to avoid
2317 // unnecessary LiveInterval changes that could perturb scheduling.
2318 if (!MI->isDebugInstr()) {
2319 SlotIndex MIIdx = DAG.LIS->getInstructionIndex(Instr: *MI);
2320 SlotIndex PrevIdx = DAG.LIS->getSlotIndexes()->getIndexBefore(MI: *MI);
2321 if (PrevIdx >= MIIdx)
2322 DAG.LIS->handleMove(MI&: *MI, UpdateFlags: true);
2323 }
2324 ++RegionEnd;
2325 }
2326 if (MI->isDebugInstr()) {
2327 LLVM_DEBUG(dbgs() << "Scheduling " << *MI);
2328 continue;
2329 }
2330
2331 // Reset read-undef flags and update them later.
2332 for (MachineOperand &Op : MI->all_defs())
2333 Op.setIsUndef(false);
2334 RegisterOperands RegOpers;
2335 RegOpers.collect(MI: *MI, TRI: *DAG.TRI, MRI: DAG.MRI, TrackLaneMasks: DAG.ShouldTrackLaneMasks, IgnoreDead: false);
2336 if (DAG.ShouldTrackLaneMasks) {
2337 // Adjust liveness and add missing dead+read-undef flags.
2338 RegOpers.adjustLaneLiveness(LIS: *DAG.LIS, MRI: DAG.MRI, MI&: *MI);
2339 } else {
2340 // Adjust for missing dead-def flags.
2341 RegOpers.detectDeadDefs(MI: *MI, LIS: *DAG.LIS, MRI: DAG.MRI);
2342 }
2343 LLVM_DEBUG(dbgs() << "Scheduling " << *MI);
2344 }
2345
2346 // The region end doesn't change throughout scheduling since it itself is
2347 // outside the region (whether that is a MBB end or a terminator MI).
2348 assert(RegionEnd == DAG.Regions[RegionIdx].second && "region end mismatch");
2349 DAG.Regions[RegionIdx].first = MIOrder.front();
2350}
2351
2352/// Returns true if reaching def \p RD will be in AGPR form after the rewrite
2353/// and so needs no bridge copy: a candidate MFMA in \p RewriteSet, an
2354/// AV_MOV_*_IMM_PSEUDO, or a copy from a candidate src2 reg in \p CandSrc2Regs.
2355/// A non-candidate MFMA stays in VGPR form and still needs a bridge.
2356static bool isReachingDefAGPRForm(
2357 MachineInstr *RD, const SmallPtrSetImpl<MachineInstr *> &RewriteSet,
2358 const DenseSet<Register> &CandSrc2Regs, const SIInstrInfo &TII) {
2359 if (TII.isMAI(MI: *RD))
2360 return RewriteSet.contains(Ptr: RD);
2361 if (RD->getOpcode() == AMDGPU::AV_MOV_B32_IMM_PSEUDO ||
2362 RD->getOpcode() == AMDGPU::AV_MOV_B64_IMM_PSEUDO)
2363 return true;
2364 if (RD->isCopy() && CandSrc2Regs.contains(V: RD->getOperand(i: 1).getReg()))
2365 return true;
2366 return false;
2367}
2368
2369bool RewriteMFMAFormStage::hasUseRequiringVGPR(
2370 ArrayRef<SlotIndex> Src2ReachingDefs,
2371 const SmallPtrSetImpl<MachineInstr *> &RewriteSet) {
2372 for (SlotIndex RDIdx : Src2ReachingDefs) {
2373 const MachineInstr *RD = DAG.LIS->getInstructionFromIndex(index: RDIdx);
2374 SmallVector<MachineOperand *, 8> ReachingUses;
2375 findReachingUses(DefMI: RD, LIS: DAG.LIS, ReachingUses);
2376 for (const MachineOperand *UseMO : ReachingUses) {
2377 const MachineInstr *UseMI = UseMO->getParent();
2378 if (UseMI->isCopy())
2379 continue;
2380 if (TII->isMAI(MI: *UseMI) && RewriteSet.contains(Ptr: UseMI))
2381 continue;
2382 return true;
2383 }
2384 }
2385 return false;
2386}
2387
2388void RewriteMFMAFormStage::resetRewriteCandsToVGPR(
2389 ArrayRef<std::pair<MachineInstr *, unsigned>> RewriteCands) {
2390 for (auto [MI, OriginalOpcode] : RewriteCands) {
2391 assert(TII->isMAI(*MI));
2392 const TargetRegisterClass *ADefRC =
2393 DAG.MRI.getRegClass(Reg: MI->getOperand(i: 0).getReg());
2394 const TargetRegisterClass *VDefRC = SRI->getEquivalentVGPRClass(SRC: ADefRC);
2395 DAG.MRI.setRegClass(Reg: MI->getOperand(i: 0).getReg(), RC: VDefRC);
2396 MI->setDesc(TII->get(Opcode: OriginalOpcode));
2397
2398 MachineOperand *Src2 = TII->getNamedOperand(MI&: *MI, OperandName: AMDGPU::OpName::src2);
2399 if (!Src2->isReg())
2400 continue;
2401
2402 // Have to get src types separately since subregs may cause C and D
2403 // registers to be different types even though the actual operand is
2404 // the same size.
2405 const TargetRegisterClass *AUseRC = DAG.MRI.getRegClass(Reg: Src2->getReg());
2406 const TargetRegisterClass *VUseRC = SRI->getEquivalentVGPRClass(SRC: AUseRC);
2407 DAG.MRI.setRegClass(Reg: Src2->getReg(), RC: VUseRC);
2408 }
2409}
2410
2411bool RewriteMFMAFormStage::isRewriteCandidate(MachineInstr *MI) const {
2412 if (!static_cast<const SIInstrInfo *>(DAG.TII)->isMAI(MI: *MI))
2413 return false;
2414 if (AMDGPU::getAGPRFormOp(Opcode: MI->getOpcode()) == -1)
2415 return false;
2416 // Reject candidates whose users force an unavoidable bridge copy.
2417 Register DstReg = MI->getOperand(i: 0).getReg();
2418 for (const MachineInstr &UseMI : DAG.MRI.use_nodbg_instructions(Reg: DstReg)) {
2419 if (!TII->isMAI(MI: UseMI) && !UseMI.isCopy())
2420 return false;
2421 }
2422 return true;
2423}
2424
2425bool RewriteMFMAFormStage::initHeuristics(
2426 std::vector<std::pair<MachineInstr *, unsigned>> &RewriteCands,
2427 DenseMap<MachineBasicBlock *, std::set<Register>> &CopyForUse,
2428 SmallPtrSetImpl<MachineInstr *> &CopyForDef) {
2429 bool Changed = false;
2430
2431 // Collect the candidate group, its members share AGPR-form operands
2432 // post-rewrite, so reaching defs feeding any member don't need bridge copy.
2433 SmallPtrSet<MachineInstr *, 16> RewriteSet;
2434 DenseSet<Register> CandSrc2Regs;
2435 for (MachineBasicBlock &MBB : MF) {
2436 for (MachineInstr &MI : MBB) {
2437 if (!isRewriteCandidate(MI: &MI))
2438 continue;
2439 RewriteSet.insert(Ptr: &MI);
2440 MachineOperand *Src2 = TII->getNamedOperand(MI, OperandName: AMDGPU::OpName::src2);
2441 if (Src2 && Src2->isReg())
2442 CandSrc2Regs.insert(V: Src2->getReg());
2443 }
2444 }
2445
2446 // Prepare for the heuristics
2447 for (MachineBasicBlock &MBB : MF) {
2448 for (MachineInstr &MI : MBB) {
2449 if (!isRewriteCandidate(MI: &MI))
2450 continue;
2451
2452 int ReplacementOp = AMDGPU::getAGPRFormOp(Opcode: MI.getOpcode());
2453 assert(ReplacementOp != -1);
2454
2455 RewriteCands.push_back(x: {&MI, MI.getOpcode()});
2456 MI.setDesc(TII->get(Opcode: ReplacementOp));
2457
2458 MachineOperand *Src2 = TII->getNamedOperand(MI, OperandName: AMDGPU::OpName::src2);
2459 if (Src2->isReg()) {
2460 SmallVector<SlotIndex, 8> Src2ReachingDefs;
2461 findReachingDefs(UseMO&: *Src2, LIS: DAG.LIS, DefIdxs&: Src2ReachingDefs);
2462
2463 // If src2 has a use that must remain VGPR, it cannot be reclassified to
2464 // AGPR.
2465 bool Src2NeedsVGPR = hasUseRequiringVGPR(Src2ReachingDefs, RewriteSet);
2466 Src2NeedsVGPRCache[&MI] = Src2NeedsVGPR;
2467
2468 for (SlotIndex RDIdx : Src2ReachingDefs) {
2469 MachineInstr *RD = DAG.LIS->getInstructionFromIndex(index: RDIdx);
2470 if (!Src2NeedsVGPR &&
2471 isReachingDefAGPRForm(RD, RewriteSet, CandSrc2Regs, TII: *TII))
2472 continue;
2473 CopyForDef.insert(Ptr: RD);
2474 }
2475 }
2476
2477 MachineOperand &Dst = MI.getOperand(i: 0);
2478 SmallVector<MachineOperand *, 8> DstReachingUses;
2479
2480 findReachingUses(DefMI: &MI, LIS: DAG.LIS, ReachingUses&: DstReachingUses);
2481
2482 for (MachineOperand *RUOp : DstReachingUses) {
2483 MachineInstr *UserMI = RUOp->getParent();
2484 // Group members read the AGPR result directly.
2485 if (TII->isMAI(MI: *UserMI) && RewriteSet.contains(Ptr: UserMI))
2486 continue;
2487
2488 // For any user of the result of the MFMA which is not an MFMA, we
2489 // insert a copy. For a given register, we will only insert one copy
2490 // per user block.
2491 CopyForUse[UserMI->getParent()].insert(x: RUOp->getReg());
2492
2493 if (TII->isMAI(MI: *UserMI))
2494 continue;
2495
2496 SmallVector<SlotIndex, 8> DstUsesReachingDefs;
2497 findReachingDefs(UseMO&: *RUOp, LIS: DAG.LIS, DefIdxs&: DstUsesReachingDefs);
2498
2499 for (SlotIndex RDIndex : DstUsesReachingDefs) {
2500 MachineInstr *RD = DAG.LIS->getInstructionFromIndex(index: RDIndex);
2501 if (TII->isMAI(MI: *RD))
2502 continue;
2503
2504 // For any definition of the user of the MFMA which is not an MFMA,
2505 // we insert a copy. We do this to transform all the reaching defs
2506 // of this use to AGPR. By doing this, we can insert a copy from
2507 // AGPR to VGPR at the user rather than after the MFMA.
2508 CopyForDef.insert(Ptr: RD);
2509 }
2510 }
2511
2512 // Do the rewrite to allow for updated RP calculation.
2513 const TargetRegisterClass *VDefRC = DAG.MRI.getRegClass(Reg: Dst.getReg());
2514 const TargetRegisterClass *ADefRC = SRI->getEquivalentAGPRClass(SRC: VDefRC);
2515 DAG.MRI.setRegClass(Reg: Dst.getReg(), RC: ADefRC);
2516 if (Src2->isReg()) {
2517 // Have to get src types separately since subregs may cause C and D
2518 // registers to be different types even though the actual operand is
2519 // the same size.
2520 const TargetRegisterClass *VUseRC = DAG.MRI.getRegClass(Reg: Src2->getReg());
2521 const TargetRegisterClass *AUseRC = SRI->getEquivalentAGPRClass(SRC: VUseRC);
2522 DAG.MRI.setRegClass(Reg: Src2->getReg(), RC: AUseRC);
2523 }
2524 Changed = true;
2525 }
2526 }
2527
2528 return Changed;
2529}
2530
2531int64_t RewriteMFMAFormStage::getRewriteCost(
2532 ArrayRef<std::pair<MachineInstr *, unsigned>> RewriteCands,
2533 const DenseMap<MachineBasicBlock *, std::set<Register>> &CopyForUse,
2534 const SmallPtrSetImpl<MachineInstr *> &CopyForDef) {
2535 MachineBlockFrequencyInfo *MBFI = DAG.MBFI;
2536
2537 int64_t BestSpillCost = 0;
2538 int64_t Cost = 0;
2539 uint64_t EntryFreq = MBFI->getEntryFreq().getFrequency();
2540
2541 std::pair<unsigned, unsigned> MaxVectorRegs =
2542 ST.getMaxNumVectorRegs(F: MF.getFunction());
2543 unsigned ArchVGPRThreshold = MaxVectorRegs.first;
2544 unsigned AGPRThreshold = MaxVectorRegs.second;
2545 unsigned CombinedThreshold = ST.getMaxNumVGPRs(MF);
2546
2547 for (unsigned Region = 0; Region < DAG.Regions.size(); Region++) {
2548 if (!RegionsWithExcessArchVGPR[Region])
2549 continue;
2550
2551 GCNRegPressure &PressureBefore = DAG.Pressure[Region];
2552 unsigned SpillCostBefore = PressureBefore.getVGPRSpills(
2553 MF, ArchVGPRThreshold, AGPRThreshold, CombinedThreshold);
2554
2555 // For the cases we care about (i.e. ArchVGPR usage is greater than the
2556 // addressable limit), rewriting alone should bring pressure to manageable
2557 // level. If we find any such region, then the rewrite is potentially
2558 // beneficial.
2559 GCNRegPressure PressureAfter = DAG.getRealRegPressure(RegionIdx: Region);
2560 unsigned SpillCostAfter = PressureAfter.getVGPRSpills(
2561 MF, ArchVGPRThreshold, AGPRThreshold, CombinedThreshold);
2562
2563 uint64_t BlockFreq =
2564 MBFI->getBlockFreq(MBB: DAG.Regions[Region].first->getParent())
2565 .getFrequency();
2566
2567 bool RelativeFreqIsDenom = EntryFreq > BlockFreq;
2568 uint64_t RelativeFreq = EntryFreq && BlockFreq
2569 ? (RelativeFreqIsDenom ? EntryFreq / BlockFreq
2570 : BlockFreq / EntryFreq)
2571 : 1;
2572
2573 // This assumes perfect spilling / splitting -- using one spill / copy
2574 // instruction and one restoreFrom / copy for each excess register,
2575 int64_t SpillCost = ((int)SpillCostAfter - (int)SpillCostBefore) * 2;
2576
2577 // Also account for the block frequency.
2578 if (RelativeFreqIsDenom)
2579 SpillCost /= (int64_t)RelativeFreq;
2580 else
2581 SpillCost *= (int64_t)RelativeFreq;
2582
2583 // If we have increased spilling in any block, just bail.
2584 if (SpillCost > 0) {
2585 resetRewriteCandsToVGPR(RewriteCands);
2586 return SpillCost;
2587 }
2588
2589 if (SpillCost < BestSpillCost)
2590 BestSpillCost = SpillCost;
2591 }
2592
2593 // Set the cost to the largest decrease in spill cost in order to not double
2594 // count spill reductions.
2595 Cost = BestSpillCost;
2596 assert(Cost <= 0);
2597
2598 unsigned CopyCost = 0;
2599
2600 // For each CopyForDef, increase the cost by the register size while
2601 // accounting for block frequency.
2602 for (MachineInstr *DefMI : CopyForDef) {
2603 Register DefReg = DefMI->getOperand(i: 0).getReg();
2604 uint64_t DefFreq =
2605 EntryFreq
2606 ? MBFI->getBlockFreq(MBB: DefMI->getParent()).getFrequency() / EntryFreq
2607 : 1;
2608
2609 const TargetRegisterClass *RC = DAG.MRI.getRegClass(Reg: DefReg);
2610 CopyCost += RC->getCopyCost() * DefFreq;
2611 }
2612
2613 // Account for CopyForUse copies in each block that the register is used.
2614 for (auto &[UseBlock, UseRegs] : CopyForUse) {
2615 uint64_t UseFreq =
2616 EntryFreq ? MBFI->getBlockFreq(MBB: UseBlock).getFrequency() / EntryFreq : 1;
2617
2618 for (Register UseReg : UseRegs) {
2619 const TargetRegisterClass *RC = DAG.MRI.getRegClass(Reg: UseReg);
2620 CopyCost += RC->getCopyCost() * UseFreq;
2621 }
2622 }
2623
2624 // Reset the classes that were changed to AGPR for better register bank
2625 // analysis. We must do rewriting after copy-insertion, as some defs of the
2626 // register may require VGPR. Additionally, if we bail out and don't perform
2627 // the rewrite then these need to be restored anyway.
2628 resetRewriteCandsToVGPR(RewriteCands);
2629
2630 return Cost + CopyCost;
2631}
2632
2633bool RewriteMFMAFormStage::rewrite(
2634 ArrayRef<std::pair<MachineInstr *, unsigned>> RewriteCands) {
2635 DenseMap<MachineInstr *, unsigned> FirstMIToRegion;
2636 DenseMap<MachineInstr *, unsigned> LastMIToRegion;
2637
2638 for (unsigned Region = 0; Region < DAG.Regions.size(); Region++) {
2639 RegionBoundaries Entry = DAG.Regions[Region];
2640 if (Entry.first == Entry.second)
2641 continue;
2642
2643 FirstMIToRegion[&*Entry.first] = Region;
2644 if (Entry.second != Entry.first->getParent()->end())
2645 LastMIToRegion[&*Entry.second] = Region;
2646 }
2647
2648 // Rewrite the MFMAs to AGPR, and insert any copies as needed.
2649 // The general assumption of the algorithm (and the previous cost calculation)
2650 // is that it is better to insert the copies in the MBB of the def of the src2
2651 // operands, and in the MBB of the user of the dest operands. This is based on
2652 // the assumption that the MFMAs are likely to appear in loop bodies, while
2653 // the src2 and dest operands are live-in / live-out of the loop. Due to this
2654 // design, the algorithm for finding copy insertion points is more
2655 // complicated.
2656 //
2657 // There are three main cases to handle: 1. the reaching defs of the src2
2658 // operands, 2. the reaching uses of the dst operands, and 3. the reaching
2659 // defs of the reaching uses of the dst operand.
2660 //
2661 // In the first case, we simply insert copies after each of the reaching
2662 // definitions. In the second case, we collect all the uses of a given dest
2663 // and organize them by MBB. Then, we insert 1 copy for each MBB before the
2664 // earliest use. Since the use may have multiple reaching defs, and since we
2665 // want to replace the register it is using with the result of the copy, we
2666 // must handle case 3. In the third case, we simply insert a copy after each
2667 // of the reaching defs to connect to the copy of the reaching uses of the dst
2668 // reg. This allows us to avoid inserting copies next to the MFMAs.
2669 //
2670 // While inserting the copies, we maintain a map of operands which will use
2671 // different regs (i.e. the result of the copies). For example, a case 1 src2
2672 // operand will use the register result of the copies after the reaching defs,
2673 // as opposed to the original register. Now that we have completed our copy
2674 // analysis and placement, we can bulk update the registers. We do this
2675 // separately as to avoid complicating the reachingDef and reachingUse
2676 // queries.
2677 //
2678 // While inserting the copies, we also maintain a list or registers which we
2679 // will want to reclassify as AGPR. After doing the copy insertion and the
2680 // register replacement, we can finally do the reclassification. This uses the
2681 // redef map, as the registers we are interested in reclassifying may be
2682 // replaced by the result of a copy. We must do this after the copy analysis
2683 // and placement as we must have an accurate redef map -- otherwise we may end
2684 // up creating illegal instructions.
2685
2686 // The original registers of the MFMA that need to be reclassified as AGPR.
2687 DenseSet<Register> RewriteRegs;
2688 // The map of an original register in the MFMA to a new register (result of a
2689 // copy) that it should be replaced with.
2690 DenseMap<Register, Register> RedefMap;
2691 // The map of the original MFMA registers to the relevant MFMA operands.
2692 DenseMap<Register, DenseSet<MachineOperand *>> ReplaceMap;
2693 // The map of reaching defs for a given register -- to avoid duplicate copies.
2694 DenseMap<Register, SmallPtrSet<MachineInstr *, 8>> ReachingDefCopyMap;
2695 // The map of reaching uses for a given register by basic block -- to avoid
2696 // duplicate copies and to calculate per MBB insert pts.
2697 DenseMap<unsigned, DenseMap<Register, SmallPtrSet<MachineOperand *, 8>>>
2698 ReachingUseTracker;
2699
2700 // Collect the candidate group; its members share AGPR-form operands
2701 // post-rewrite, so reaching defs feeding any member need no bridge copy.
2702 SmallPtrSet<MachineInstr *, 16> RewriteCandsSet;
2703 DenseSet<Register> RewriteSrc2Regs;
2704 for (auto &[MI, OriginalOpcode] : RewriteCands) {
2705 RewriteCandsSet.insert(Ptr: MI);
2706 MachineOperand *Src2 = TII->getNamedOperand(MI&: *MI, OperandName: AMDGPU::OpName::src2);
2707 if (Src2 && Src2->isReg())
2708 RewriteSrc2Regs.insert(V: Src2->getReg());
2709 }
2710
2711 for (auto &[MI, OriginalOpcode] : RewriteCands) {
2712 int ReplacementOp = AMDGPU::getAGPRFormOp(Opcode: MI->getOpcode());
2713 if (ReplacementOp == -1)
2714 continue;
2715 MI->setDesc(TII->get(Opcode: ReplacementOp));
2716
2717 // Case 1: insert copies for the reaching defs of the Src2Reg.
2718 MachineOperand *Src2 = TII->getNamedOperand(MI&: *MI, OperandName: AMDGPU::OpName::src2);
2719 if (Src2->isReg()) {
2720 Register Src2Reg = Src2->getReg();
2721 if (!Src2Reg.isVirtual())
2722 return false;
2723
2724 Register MappedReg = Src2->getReg();
2725 SmallVector<SlotIndex, 8> Src2ReachingDefs;
2726 findReachingDefs(UseMO&: *Src2, LIS: DAG.LIS, DefIdxs&: Src2ReachingDefs);
2727 SmallSetVector<MachineInstr *, 8> Src2DefsReplace;
2728
2729 // If src2 has a use that must remain VGPR, it cannot be reclassified to
2730 // AGPR.
2731 bool Src2NeedsVGPR = Src2NeedsVGPRCache.lookup(Val: MI);
2732
2733 for (SlotIndex RDIndex : Src2ReachingDefs) {
2734 MachineInstr *RD = DAG.LIS->getInstructionFromIndex(index: RDIndex);
2735 if (!Src2NeedsVGPR &&
2736 isReachingDefAGPRForm(RD, RewriteSet: RewriteCandsSet, CandSrc2Regs: RewriteSrc2Regs, TII: *TII))
2737 continue;
2738
2739 Src2DefsReplace.insert(X: RD);
2740 }
2741
2742 if (!Src2DefsReplace.empty()) {
2743 auto RI = RedefMap.find(Val: Src2Reg);
2744 if (RI != RedefMap.end()) {
2745 MappedReg = RI->second;
2746 } else {
2747 assert(!ReachingDefCopyMap.contains(Src2Reg));
2748 const TargetRegisterClass *Src2RC = DAG.MRI.getRegClass(Reg: Src2Reg);
2749 const TargetRegisterClass *VGPRRC =
2750 SRI->getEquivalentVGPRClass(SRC: Src2RC);
2751
2752 // Track the mapping of the original register to the new register.
2753 MappedReg = DAG.MRI.createVirtualRegister(RegClass: VGPRRC);
2754 RedefMap[Src2Reg] = MappedReg;
2755 }
2756
2757 // If none exists, create a copy from this reaching def.
2758 // We may have inserted a copy already in an earlier iteration.
2759 for (MachineInstr *RD : Src2DefsReplace) {
2760 // Do not create redundant copies.
2761 if (ReachingDefCopyMap[Src2Reg].insert(Ptr: RD).second) {
2762 MachineInstrBuilder VGPRCopy =
2763 BuildMI(BB&: *RD->getParent(), I: std::next(x: RD->getIterator()),
2764 MIMD: RD->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::COPY))
2765 .addDef(RegNo: MappedReg, Flags: {}, SubReg: 0)
2766 .addUse(RegNo: Src2Reg, Flags: {}, SubReg: 0);
2767 DAG.LIS->InsertMachineInstrInMaps(MI&: *VGPRCopy);
2768
2769 // If this reaching def was the last MI in the region, update the
2770 // region boundaries.
2771 if (LastMIToRegion.contains(Val: RD)) {
2772 unsigned UpdateRegion = LastMIToRegion[RD];
2773 DAG.Regions[UpdateRegion].second = VGPRCopy;
2774 LastMIToRegion.erase(Val: RD);
2775 }
2776 }
2777 }
2778 }
2779
2780 // Track the register for reclassification
2781 RewriteRegs.insert(V: Src2Reg);
2782
2783 // Always insert the operand for replacement. If this corresponds with a
2784 // chain of tied-def we may not see the VGPR requirement until later.
2785 ReplaceMap[Src2Reg].insert(V: Src2);
2786 }
2787
2788 // Case 2 and Case 3: insert copies before the reaching uses of the dsts,
2789 // and after the reaching defs of the reaching uses of the dsts.
2790
2791 MachineOperand *Dst = &MI->getOperand(i: 0);
2792 Register DstReg = Dst->getReg();
2793 if (!DstReg.isVirtual())
2794 return false;
2795
2796 Register MappedReg = DstReg;
2797 SmallVector<MachineOperand *, 8> DstReachingUses;
2798
2799 SmallVector<MachineOperand *, 8> DstReachingUseCopies;
2800 SmallVector<MachineInstr *, 8> DstUseDefsReplace;
2801
2802 findReachingUses(DefMI: MI, LIS: DAG.LIS, ReachingUses&: DstReachingUses);
2803
2804 for (MachineOperand *RUOp : DstReachingUses) {
2805 MachineInstr *UserMI = RUOp->getParent();
2806 // Group members read the AGPR result directly.
2807 if (TII->isMAI(MI: *UserMI) && RewriteCandsSet.contains(Ptr: UserMI))
2808 continue;
2809
2810 // If there is a non mai reaching use, then we need a copy.
2811 if (find(Range&: DstReachingUseCopies, Val: RUOp) == DstReachingUseCopies.end())
2812 DstReachingUseCopies.push_back(Elt: RUOp);
2813
2814 // Non-rewritten MAI: its defs aren't being reclassified.
2815 if (TII->isMAI(MI: *UserMI))
2816 continue;
2817
2818 SmallVector<SlotIndex, 8> DstUsesReachingDefs;
2819 findReachingDefs(UseMO&: *RUOp, LIS: DAG.LIS, DefIdxs&: DstUsesReachingDefs);
2820
2821 for (SlotIndex RDIndex : DstUsesReachingDefs) {
2822 MachineInstr *RD = DAG.LIS->getInstructionFromIndex(index: RDIndex);
2823 if (TII->isMAI(MI: *RD))
2824 continue;
2825
2826 // If there is a non mai reaching def of this reaching use, then we will
2827 // need a copy.
2828 if (find(Range&: DstUseDefsReplace, Val: RD) == DstUseDefsReplace.end())
2829 DstUseDefsReplace.push_back(Elt: RD);
2830 }
2831 }
2832
2833 if (!DstUseDefsReplace.empty()) {
2834 auto RI = RedefMap.find(Val: DstReg);
2835 if (RI != RedefMap.end()) {
2836 MappedReg = RI->second;
2837 } else {
2838 assert(!ReachingDefCopyMap.contains(DstReg));
2839 const TargetRegisterClass *DstRC = DAG.MRI.getRegClass(Reg: DstReg);
2840 const TargetRegisterClass *VGPRRC = SRI->getEquivalentVGPRClass(SRC: DstRC);
2841
2842 // Track the mapping of the original register to the new register.
2843 MappedReg = DAG.MRI.createVirtualRegister(RegClass: VGPRRC);
2844 RedefMap[DstReg] = MappedReg;
2845 }
2846
2847 // If none exists, create a copy from this reaching def.
2848 // We may have inserted a copy already in an earlier iteration.
2849 for (MachineInstr *RD : DstUseDefsReplace) {
2850 // Do not create reundant copies.
2851 if (ReachingDefCopyMap[DstReg].insert(Ptr: RD).second) {
2852 MachineInstrBuilder VGPRCopy =
2853 BuildMI(BB&: *RD->getParent(), I: std::next(x: RD->getIterator()),
2854 MIMD: RD->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::COPY))
2855 .addDef(RegNo: MappedReg, Flags: {}, SubReg: 0)
2856 .addUse(RegNo: DstReg, Flags: {}, SubReg: 0);
2857 DAG.LIS->InsertMachineInstrInMaps(MI&: *VGPRCopy);
2858
2859 // If this reaching def was the last MI in the region, update the
2860 // region boundaries.
2861 auto LMI = LastMIToRegion.find(Val: RD);
2862 if (LMI != LastMIToRegion.end()) {
2863 unsigned UpdateRegion = LMI->second;
2864 DAG.Regions[UpdateRegion].second = VGPRCopy;
2865 LastMIToRegion.erase(Val: RD);
2866 }
2867 }
2868 }
2869 }
2870
2871 DenseSet<MachineOperand *> &DstRegSet = ReplaceMap[DstReg];
2872 // One AGPR→VGPR copy per dst register, shared by all same-block uses.
2873 Register SameBlockCopyReg;
2874 MachineInstr *EarliestSameBlockUse = nullptr;
2875 for (MachineOperand *RU : DstReachingUseCopies) {
2876 MachineBasicBlock *RUBlock = RU->getParent()->getParent();
2877 // Just keep track of the reaching use of this register by block. After we
2878 // have scanned all the MFMAs we can find optimal insert pts.
2879 if (RUBlock != MI->getParent()) {
2880 ReachingUseTracker[RUBlock->getNumber()][DstReg].insert(Ptr: RU);
2881 continue;
2882 }
2883
2884 // Lazily create the copy register on first same-block use.
2885 if (!SameBlockCopyReg.isValid()) {
2886 const TargetRegisterClass *DstRC = DAG.MRI.getRegClass(Reg: DstReg);
2887 const TargetRegisterClass *VGPRRC = SRI->getEquivalentVGPRClass(SRC: DstRC);
2888 SameBlockCopyReg = DAG.MRI.createVirtualRegister(RegClass: VGPRRC);
2889 }
2890
2891 // Track the earliest use for copy insertion point.
2892 MachineInstr *UseInst = RU->getParent();
2893 if (!EarliestSameBlockUse ||
2894 SlotIndex::isEarlierInstr(
2895 A: DAG.LIS->getInstructionIndex(Instr: *UseInst),
2896 B: DAG.LIS->getInstructionIndex(Instr: *EarliestSameBlockUse)))
2897 EarliestSameBlockUse = UseInst;
2898 RU->setReg(SameBlockCopyReg);
2899 }
2900
2901 // Insert the copy before the earliest same-block use.
2902 if (SameBlockCopyReg.isValid()) {
2903 MachineInstrBuilder VGPRCopy =
2904 BuildMI(BB&: *EarliestSameBlockUse->getParent(),
2905 I: EarliestSameBlockUse->getIterator(), MIMD: DebugLoc(),
2906 MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: SameBlockCopyReg)
2907 .addUse(RegNo: DstReg, Flags: {}, SubReg: 0);
2908 DAG.LIS->InsertMachineInstrInMaps(MI&: *VGPRCopy);
2909 DstRegSet.insert(V: &VGPRCopy->getOperand(i: 1));
2910 }
2911
2912 // Track the register for reclassification
2913 RewriteRegs.insert(V: DstReg);
2914
2915 // Insert the dst operand for replacement. If this dst is in a chain of
2916 // tied-def MFMAs, and the first src2 needs to be replaced with a new reg,
2917 // all the correspond operands need to be replaced.
2918 DstRegSet.insert(V: Dst);
2919 }
2920
2921 // Handle the copies for dst uses.
2922 using RUBType =
2923 std::pair<unsigned, DenseMap<Register, SmallPtrSet<MachineOperand *, 8>>>;
2924 for (RUBType RUBlockEntry : ReachingUseTracker) {
2925 using RUDType = std::pair<Register, SmallPtrSet<MachineOperand *, 8>>;
2926 for (RUDType RUDst : RUBlockEntry.second) {
2927 MachineOperand *OpBegin = *RUDst.second.begin();
2928 SlotIndex InstPt = DAG.LIS->getInstructionIndex(Instr: *OpBegin->getParent());
2929
2930 // Find the earliest use in this block.
2931 for (MachineOperand *User : RUDst.second) {
2932 SlotIndex NewInstPt = DAG.LIS->getInstructionIndex(Instr: *User->getParent());
2933 if (SlotIndex::isEarlierInstr(A: NewInstPt, B: InstPt))
2934 InstPt = NewInstPt;
2935 }
2936
2937 const TargetRegisterClass *DstRC = DAG.MRI.getRegClass(Reg: RUDst.first);
2938 const TargetRegisterClass *VGPRRC = SRI->getEquivalentVGPRClass(SRC: DstRC);
2939 Register NewUseReg = DAG.MRI.createVirtualRegister(RegClass: VGPRRC);
2940 MachineInstr *UseInst = DAG.LIS->getInstructionFromIndex(index: InstPt);
2941
2942 MachineInstrBuilder VGPRCopy =
2943 BuildMI(BB&: *UseInst->getParent(), I: UseInst->getIterator(),
2944 MIMD: UseInst->getDebugLoc(), MCID: TII->get(Opcode: TargetOpcode::COPY))
2945 .addDef(RegNo: NewUseReg, Flags: {}, SubReg: 0)
2946 .addUse(RegNo: RUDst.first, Flags: {}, SubReg: 0);
2947 DAG.LIS->InsertMachineInstrInMaps(MI&: *VGPRCopy);
2948
2949 // If this UseInst was the first MI in the region, update the region
2950 // boundaries.
2951 auto FI = FirstMIToRegion.find(Val: UseInst);
2952 if (FI != FirstMIToRegion.end()) {
2953 unsigned UpdateRegion = FI->second;
2954 DAG.Regions[UpdateRegion].first = VGPRCopy;
2955 FirstMIToRegion.erase(Val: UseInst);
2956 }
2957
2958 // Replace the operand for all users.
2959 for (MachineOperand *User : RUDst.second) {
2960 User->setReg(NewUseReg);
2961 }
2962
2963 // Track the copy source operand for replacement.
2964 ReplaceMap[RUDst.first].insert(V: &VGPRCopy->getOperand(i: 1));
2965 }
2966 }
2967
2968 // We may have needed to insert copies after the reaching defs of the MFMAs.
2969 // Replace the original register with the result of the copy for all relevant
2970 // operands.
2971 for (std::pair<Register, Register> NewDef : RedefMap) {
2972 Register OldReg = NewDef.first;
2973 Register NewReg = NewDef.second;
2974
2975 // Replace the register for any associated operand in the MFMA chain.
2976 for (MachineOperand *ReplaceOp : ReplaceMap[OldReg])
2977 ReplaceOp->setReg(NewReg);
2978 }
2979
2980 // Finally, do the reclassification of the MFMA registers.
2981 for (Register RewriteReg : RewriteRegs) {
2982 Register RegToRewrite = RewriteReg;
2983
2984 // Be sure to update the replacement register and not the original.
2985 auto RI = RedefMap.find(Val: RewriteReg);
2986 if (RI != RedefMap.end())
2987 RegToRewrite = RI->second;
2988
2989 const TargetRegisterClass *CurrRC = DAG.MRI.getRegClass(Reg: RegToRewrite);
2990 const TargetRegisterClass *AGPRRC = SRI->getEquivalentAGPRClass(SRC: CurrRC);
2991
2992 DAG.MRI.setRegClass(Reg: RegToRewrite, RC: AGPRRC);
2993 }
2994
2995 // Bulk update the LIS.
2996 DAG.LIS->reanalyze(MF&: DAG.MF);
2997 // Liveins may have been modified for cross RC copies
2998 RegionPressureMap LiveInUpdater(&DAG, false);
2999 LiveInUpdater.buildLiveRegMap();
3000
3001 for (unsigned Region = 0; Region < DAG.Regions.size(); Region++)
3002 DAG.LiveIns[Region] = LiveInUpdater.getLiveRegsForRegionIdx(RegionIdx: Region);
3003
3004 DAG.Pressure[RegionIdx] = DAG.getRealRegPressure(RegionIdx);
3005
3006 return true;
3007}
3008
3009unsigned PreRARematStage::getStageTargetOccupancy() const {
3010 return TargetOcc ? *TargetOcc : MFI.getMinWavesPerEU();
3011}
3012
3013bool PreRARematStage::setObjective() {
3014 const Function &F = MF.getFunction();
3015
3016 // Set up "spilling targets" for all regions.
3017 unsigned MaxSGPRs = ST.getMaxNumSGPRs(F);
3018 unsigned MaxVGPRs = ST.getMaxNumVGPRs(F);
3019 bool HasVectorRegisterExcess = false;
3020 for (unsigned I = 0, E = DAG.Regions.size(); I != E; ++I) {
3021 const GCNRegPressure &RP = DAG.Pressure[I];
3022 GCNRPTarget &Target = RPTargets.emplace_back(Args&: MaxSGPRs, Args&: MaxVGPRs, Args&: MF, Args: RP);
3023 if (!Target.satisfied())
3024 TargetRegions.set(I);
3025 HasVectorRegisterExcess |= Target.hasVectorRegisterExcess();
3026 }
3027
3028 if (HasVectorRegisterExcess || DAG.MinOccupancy >= MFI.getMaxWavesPerEU()) {
3029 // In addition to register usage being above addressable limits, occupancy
3030 // below the minimum is considered like "spilling" as well.
3031 TargetOcc = std::nullopt;
3032 } else {
3033 // There is no spilling and room to improve occupancy; set up "increased
3034 // occupancy targets" for all regions.
3035 TargetOcc = DAG.MinOccupancy + 1;
3036 const unsigned VGPRBlockSize = MFI.getDynamicVGPRBlockSize();
3037 MaxSGPRs = ST.getMaxNumSGPRs(WavesPerEU: *TargetOcc, Addressable: false);
3038 MaxVGPRs = ST.getMaxNumVGPRs(WavesPerEU: *TargetOcc, DynamicVGPRBlockSize: VGPRBlockSize);
3039 for (auto [I, Target] : enumerate(First&: RPTargets)) {
3040 Target.setTarget(NumSGPRs: MaxSGPRs, NumVGPRs: MaxVGPRs);
3041 if (!Target.satisfied())
3042 TargetRegions.set(I);
3043 }
3044 }
3045
3046 return TargetRegions.any();
3047}
3048
3049bool PreRARematStage::ScoredRemat::maybeBeneficial(
3050 const BitVector &TargetRegions, ArrayRef<GCNRPTarget> RPTargets) const {
3051 for (unsigned I : TargetRegions.set_bits()) {
3052 if (Live[I] && RPTargets[I].isSaveBeneficial(SaveRP: RPSave))
3053 return true;
3054 }
3055 return false;
3056}
3057
3058PreRARematStage::ScoredRemat::FreqInfo::FreqInfo(
3059 MachineFunction &MF, const GCNScheduleDAGMILive &DAG) {
3060 MachineBranchProbabilityInfo MBPI;
3061 MachineCycleInfo MCI;
3062 MCI.compute(F&: MF);
3063 MachineBlockFrequencyInfo MBFI(MF, MBPI, MCI);
3064
3065 const unsigned NumRegions = DAG.Regions.size();
3066 MinFreq = MBFI.getEntryFreq().getFrequency();
3067 MaxFreq = 0;
3068 Regions.reserve(N: NumRegions);
3069 for (unsigned I = 0; I < NumRegions; ++I) {
3070 MachineBasicBlock *MBB = DAG.Regions[I].first->getParent();
3071 uint64_t BlockFreq = MBFI.getBlockFreq(MBB).getFrequency();
3072 Regions.push_back(Elt: BlockFreq);
3073 if (BlockFreq && BlockFreq < MinFreq)
3074 MinFreq = BlockFreq;
3075 else if (BlockFreq > MaxFreq)
3076 MaxFreq = BlockFreq;
3077 }
3078 if (!MinFreq)
3079 return;
3080
3081 // Scale everything down if frequencies are high.
3082 if (MinFreq >= ScaleFactor * ScaleFactor) {
3083 for (uint64_t &Freq : Regions)
3084 Freq /= ScaleFactor;
3085 MinFreq /= ScaleFactor;
3086 MaxFreq /= ScaleFactor;
3087 }
3088}
3089
3090void PreRARematStage::ScoredRemat::init(const FreqInfo &Freq,
3091 const Rematerializer &Remater,
3092 GCNScheduleDAGMILive &DAG) {
3093 const Rematerializer::Reg &Reg = Remater.getReg(RegIdx);
3094 Register DefReg = Reg.getDefReg();
3095 assert(Reg.Uses.size() == 1 && "expected users in single region");
3096 const unsigned UseRegion = Reg.Uses.begin()->first;
3097
3098 Live |= LiveIn;
3099 Live |= LiveOut;
3100
3101 for (unsigned I : Live.set_bits()) {
3102 // If the register is both unused and live-through in the region, the
3103 // latter's RP is guaranteed to decrease.
3104 if (!LiveIn[I] || !LiveOut[I] || I == UseRegion)
3105 UnpredictableRPSave.set(I);
3106 }
3107 RPSave.inc(Reg: DefReg, PrevMask: LaneBitmask::getNone(), NewMask: Reg.Mask, MRI: DAG.MRI);
3108
3109 // Get frequencies of defining and using regions. A rematerialization from the
3110 // least frequent region to the most frequent region will yield the greatest
3111 // in order to penalize rematerializations from or into regions whose
3112 int64_t DefOrMin = std::max(a: Freq.Regions[Reg.DefRegion], b: Freq.MinFreq);
3113 int64_t UseOrMax = Freq.Regions[UseRegion];
3114 if (!UseOrMax)
3115 UseOrMax = Freq.MaxFreq;
3116 FreqDiff = DefOrMin - UseOrMax;
3117}
3118
3119void PreRARematStage::ScoredRemat::update(const BitVector &TargetRegions,
3120 ArrayRef<GCNRPTarget> RPTargets,
3121 const FreqInfo &FreqInfo,
3122 bool ReduceSpill) {
3123 MaxFreq = 0;
3124 RegionImpact = 0;
3125 for (unsigned I : TargetRegions.set_bits()) {
3126 if (!Live[I])
3127 continue;
3128
3129 // The rematerialization must contribute positively in at least one
3130 // register class with usage above the RP target for this region to
3131 // contribute to the score.
3132 const GCNRPTarget &RegionTarget = RPTargets[I];
3133 const unsigned NumRegsBenefit = RegionTarget.getNumRegsBenefit(SaveRP: RPSave);
3134 if (!NumRegsBenefit)
3135 continue;
3136
3137 // Regions in which RP is guaranteed to decrease have more weight.
3138 RegionImpact += (UnpredictableRPSave[I] ? 1 : 2) * NumRegsBenefit;
3139
3140 if (ReduceSpill) {
3141 uint64_t Freq = FreqInfo.Regions[I];
3142 if (UnpredictableRPSave[I]) {
3143 // Apply a frequency penalty in regions in which we are not sure that RP
3144 // will decrease.
3145 Freq /= 2;
3146 }
3147 MaxFreq = std::max(a: MaxFreq, b: Freq);
3148 }
3149 }
3150}
3151
3152void PreRARematStage::ScoredRemat::rematerialize(
3153 Rematerializer &Remater) const {
3154 const Rematerializer::Reg &Reg = Remater.getReg(RegIdx);
3155 Rematerializer::DependencyReuseInfo DRI;
3156 for (RegisterIdx DepRegIdx : Reg.Dependencies)
3157 DRI.reuse(DepIdx: DepRegIdx);
3158 unsigned UseRegion = Reg.Uses.begin()->first;
3159 Remater.rematerializeToRegion(RootIdx: RegIdx, UseRegion, DRI);
3160}
3161
3162void PreRARematStage::updateRPTargets(const BitVector &Regions,
3163 const GCNRegPressure &RPSave) {
3164 for (unsigned I : Regions.set_bits()) {
3165 RPTargets[I].saveRP(SaveRP: RPSave);
3166 if (TargetRegions[I] && RPTargets[I].satisfied()) {
3167 REMAT_DEBUG(dbgs() << " [" << I << "] Target reached!\n");
3168 TargetRegions.reset(Idx: I);
3169 }
3170 }
3171}
3172
3173bool PreRARematStage::updateAndVerifyRPTargets(const BitVector &Regions) {
3174 bool TooOptimistic = false;
3175 for (unsigned I : Regions.set_bits()) {
3176 GCNRPTarget &Target = RPTargets[I];
3177 Target.setRP(DAG.getRealRegPressure(RegionIdx: I));
3178
3179 // Since we were optimistic in assessing RP decreases in these regions, we
3180 // may need to remark the target as a target region if RP didn't decrease
3181 // as expected.
3182 if (!TargetRegions[I] && !Target.satisfied()) {
3183 REMAT_DEBUG(dbgs() << " [" << I << "] Incorrect RP estimation\n");
3184 TooOptimistic = true;
3185 TargetRegions.set(I);
3186 }
3187 }
3188 return TooOptimistic;
3189}
3190
3191void PreRARematStage::removeFromLiveMaps(Register Reg, const BitVector &LiveIn,
3192 const BitVector &LiveOut) {
3193 assert(LiveIn.size() == DAG.Regions.size() &&
3194 LiveOut.size() == DAG.Regions.size() && "region num mismatch");
3195 for (unsigned I : LiveIn.set_bits())
3196 DAG.LiveIns[I].erase(Val: Reg);
3197 for (unsigned I : LiveOut.set_bits())
3198 DAG.RegionLiveOuts.getLiveRegsForRegionIdx(RegionIdx: I).erase(Val: Reg);
3199}
3200
3201void PreRARematStage::addToLiveMaps(Register Reg, LaneBitmask Mask,
3202 const BitVector &LiveIn,
3203 const BitVector &LiveOut) {
3204 assert(LiveIn.size() == DAG.Regions.size() &&
3205 LiveOut.size() == DAG.Regions.size() && "region num mismatch");
3206 std::pair<Register, LaneBitmask> LiveReg(Reg, Mask);
3207 for (unsigned I : LiveIn.set_bits())
3208 DAG.LiveIns[I].insert(KV: LiveReg);
3209 for (unsigned I : LiveOut.set_bits())
3210 DAG.RegionLiveOuts.getLiveRegsForRegionIdx(RegionIdx: I).insert(KV: LiveReg);
3211}
3212
3213void PreRARematStage::finalizeGCNSchedStage() {
3214 // We consider that reducing spilling is always beneficial so we never
3215 // rollback rematerializations or revert scheduling in such cases.
3216 if (!TargetOcc)
3217 return;
3218
3219 // When increasing occupancy, it is possible that re-scheduling is not able to
3220 // achieve the target occupancy in all regions, in which case re-scheduling in
3221 // all regions should be reverted.
3222 if (DAG.MinOccupancy >= *TargetOcc)
3223 return;
3224
3225 // Revert re-scheduling in all affected regions.
3226 for (const auto &[RegionIdx, OrigMIOrder, MaxPressure] : RegionReverts) {
3227 REMAT_DEBUG(dbgs() << "Reverting re-scheduling in region " << RegionIdx
3228 << '\n');
3229 DAG.Pressure[RegionIdx] = MaxPressure;
3230 modifyRegionSchedule(RegionIdx, MIOrder: OrigMIOrder);
3231 }
3232
3233 // It is possible that re-scheduling lowers occupancy over the one achieved
3234 // just through rematerializations, in which case we revert re-scheduling in
3235 // all regions but do not roll back rematerializations.
3236 if (AchievedOcc >= *TargetOcc) {
3237 DAG.setTargetOccupancy(AchievedOcc);
3238 return;
3239 }
3240
3241 // Reset the target occupancy to what it was pre-rematerialization.
3242 DAG.setTargetOccupancy(*TargetOcc - 1);
3243
3244 // Roll back changes made by the stage, then recompute pressure in all
3245 // affected regions.
3246 REMAT_DEBUG(dbgs() << "==== ROLLBACK ====\n");
3247 assert(Rollback && "rollbacker should be defined");
3248 Rollback->Listener.rollback(Remater);
3249 for (const auto &[RegIdx, LiveIn, LiveOut] : Rollback->LiveMapUpdates) {
3250 const Rematerializer::Reg &Reg = Remater.getReg(RegIdx);
3251 addToLiveMaps(Reg: Reg.getDefReg(), Mask: Reg.Mask, LiveIn, LiveOut);
3252 }
3253
3254#ifdef EXPENSIVE_CHECKS
3255 // In particular, we want to check for coherent MI/slot order in regions in
3256 // which reverts and/or rollbacks may have happened.
3257 MF.verify();
3258#endif
3259 for (unsigned I : RescheduleRegions.set_bits())
3260 DAG.Pressure[I] = DAG.getRealRegPressure(RegionIdx: I);
3261
3262 GCNSchedStage::finalizeGCNSchedStage();
3263}
3264
3265void GCNScheduleDAGMILive::setTargetOccupancy(unsigned TargetOccupancy) {
3266 MinOccupancy = TargetOccupancy;
3267 if (MFI.getOccupancy() < TargetOccupancy)
3268 MFI.increaseOccupancy(MF, Limit: MinOccupancy);
3269 else
3270 MFI.limitOccupancy(Limit: MinOccupancy);
3271}
3272
3273static bool hasIGLPInstrs(ScheduleDAGInstrs *DAG) {
3274 const SIInstrInfo *SII = static_cast<const SIInstrInfo *>(DAG->TII);
3275 return any_of(Range&: *DAG, P: [SII](MachineBasicBlock::iterator MI) {
3276 return SII->isIGLPMutationOnly(Opcode: MI->getOpcode());
3277 });
3278}
3279
3280GCNPostScheduleDAGMILive::GCNPostScheduleDAGMILive(
3281 MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
3282 bool RemoveKillFlags)
3283 : ScheduleDAGMI(C, std::move(S), RemoveKillFlags) {}
3284
3285void GCNPostScheduleDAGMILive::schedule() {
3286 HasIGLPInstrs = hasIGLPInstrs(DAG: this);
3287 if (HasIGLPInstrs) {
3288 SavedMutations.clear();
3289 SavedMutations.swap(x&: Mutations);
3290 addMutation(Mutation: createIGroupLPDAGMutation(Phase: AMDGPU::SchedulingPhase::PostRA));
3291 }
3292
3293 ScheduleDAGMI::schedule();
3294}
3295
3296void GCNPostScheduleDAGMILive::finalizeSchedule() {
3297 if (HasIGLPInstrs)
3298 SavedMutations.swap(x&: Mutations);
3299
3300 ScheduleDAGMI::finalizeSchedule();
3301}
3302