1 //===-- GCNSchedStrategy.cpp - GCN Scheduler Strategy ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This contains a MachineSchedStrategy implementation for maximizing wave
12 /// occupancy on GCN hardware.
13 //===----------------------------------------------------------------------===//
15 #include "GCNSchedStrategy.h"
16 #include "AMDGPUSubtarget.h"
17 #include "SIInstrInfo.h"
18 #include "SIMachineFunctionInfo.h"
19 #include "SIRegisterInfo.h"
20 #include "llvm/CodeGen/RegisterClassInfo.h"
21 #include "llvm/Support/MathExtras.h"
23 #define DEBUG_TYPE "misched"
27 GCNMaxOccupancySchedStrategy::GCNMaxOccupancySchedStrategy(
28 const MachineSchedContext *C) :
29 GenericScheduler(C), TargetOccupancy(0), MF(nullptr) { }
31 static unsigned getMaxWaves(unsigned SGPRs, unsigned VGPRs,
32 const MachineFunction &MF) {
34 const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
35 const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
36 unsigned MinRegOccupancy = std::min(ST.getOccupancyWithNumSGPRs(SGPRs),
37 ST.getOccupancyWithNumVGPRs(VGPRs));
38 return std::min(MinRegOccupancy,
39 ST.getOccupancyWithLocalMemSize(MFI->getLDSSize(),
43 void GCNMaxOccupancySchedStrategy::initialize(ScheduleDAGMI *DAG) {
44 GenericScheduler::initialize(DAG);
46 const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo*>(TRI);
50 const SISubtarget &ST = MF->getSubtarget<SISubtarget>();
52 // FIXME: This is also necessary, because some passes that run after
53 // scheduling and before regalloc increase register pressure.
54 const int ErrorMargin = 3;
56 SGPRExcessLimit = Context->RegClassInfo
57 ->getNumAllocatableRegs(&AMDGPU::SGPR_32RegClass) - ErrorMargin;
58 VGPRExcessLimit = Context->RegClassInfo
59 ->getNumAllocatableRegs(&AMDGPU::VGPR_32RegClass) - ErrorMargin;
60 if (TargetOccupancy) {
61 SGPRCriticalLimit = ST.getMaxNumSGPRs(TargetOccupancy, true);
62 VGPRCriticalLimit = ST.getMaxNumVGPRs(TargetOccupancy);
64 SGPRCriticalLimit = SRI->getRegPressureSetLimit(DAG->MF,
65 SRI->getSGPRPressureSet());
66 VGPRCriticalLimit = SRI->getRegPressureSetLimit(DAG->MF,
67 SRI->getVGPRPressureSet());
70 SGPRCriticalLimit -= ErrorMargin;
71 VGPRCriticalLimit -= ErrorMargin;
74 void GCNMaxOccupancySchedStrategy::initCandidate(SchedCandidate &Cand, SUnit *SU,
75 bool AtTop, const RegPressureTracker &RPTracker,
76 const SIRegisterInfo *SRI,
77 unsigned SGPRPressure,
78 unsigned VGPRPressure) {
83 // getDownwardPressure() and getUpwardPressure() make temporary changes to
84 // the the tracker, so we need to pass those function a non-const copy.
85 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
87 std::vector<unsigned> Pressure;
88 std::vector<unsigned> MaxPressure;
91 TempTracker.getDownwardPressure(SU->getInstr(), Pressure, MaxPressure);
93 // FIXME: I think for bottom up scheduling, the register pressure is cached
94 // and can be retrieved by DAG->getPressureDif(SU).
95 TempTracker.getUpwardPressure(SU->getInstr(), Pressure, MaxPressure);
98 unsigned NewSGPRPressure = Pressure[SRI->getSGPRPressureSet()];
99 unsigned NewVGPRPressure = Pressure[SRI->getVGPRPressureSet()];
101 // If two instructions increase the pressure of different register sets
102 // by the same amount, the generic scheduler will prefer to schedule the
103 // instruction that increases the set with the least amount of registers,
104 // which in our case would be SGPRs. This is rarely what we want, so
105 // when we report excess/critical register pressure, we do it either
106 // only for VGPRs or only for SGPRs.
108 // FIXME: Better heuristics to determine whether to prefer SGPRs or VGPRs.
109 const unsigned MaxVGPRPressureInc = 16;
110 bool ShouldTrackVGPRs = VGPRPressure + MaxVGPRPressureInc >= VGPRExcessLimit;
111 bool ShouldTrackSGPRs = !ShouldTrackVGPRs && SGPRPressure >= SGPRExcessLimit;
114 // FIXME: We have to enter REG-EXCESS before we reach the actual threshold
115 // to increase the likelihood we don't go over the limits. We should improve
116 // the analysis to look through dependencies to find the path with the least
117 // register pressure.
119 // We only need to update the RPDelata for instructions that increase
120 // register pressure. Instructions that decrease or keep reg pressure
121 // the same will be marked as RegExcess in tryCandidate() when they
122 // are compared with instructions that increase the register pressure.
123 if (ShouldTrackVGPRs && NewVGPRPressure >= VGPRExcessLimit) {
124 Cand.RPDelta.Excess = PressureChange(SRI->getVGPRPressureSet());
125 Cand.RPDelta.Excess.setUnitInc(NewVGPRPressure - VGPRExcessLimit);
128 if (ShouldTrackSGPRs && NewSGPRPressure >= SGPRExcessLimit) {
129 Cand.RPDelta.Excess = PressureChange(SRI->getSGPRPressureSet());
130 Cand.RPDelta.Excess.setUnitInc(NewSGPRPressure - SGPRExcessLimit);
133 // Register pressure is considered 'CRITICAL' if it is approaching a value
134 // that would reduce the wave occupancy for the execution unit. When
135 // register pressure is 'CRITICAL', increading SGPR and VGPR pressure both
136 // has the same cost, so we don't need to prefer one over the other.
138 int SGPRDelta = NewSGPRPressure - SGPRCriticalLimit;
139 int VGPRDelta = NewVGPRPressure - VGPRCriticalLimit;
141 if (SGPRDelta >= 0 || VGPRDelta >= 0) {
142 if (SGPRDelta > VGPRDelta) {
143 Cand.RPDelta.CriticalMax = PressureChange(SRI->getSGPRPressureSet());
144 Cand.RPDelta.CriticalMax.setUnitInc(SGPRDelta);
146 Cand.RPDelta.CriticalMax = PressureChange(SRI->getVGPRPressureSet());
147 Cand.RPDelta.CriticalMax.setUnitInc(VGPRDelta);
152 // This function is mostly cut and pasted from
153 // GenericScheduler::pickNodeFromQueue()
154 void GCNMaxOccupancySchedStrategy::pickNodeFromQueue(SchedBoundary &Zone,
155 const CandPolicy &ZonePolicy,
156 const RegPressureTracker &RPTracker,
157 SchedCandidate &Cand) {
158 const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo*>(TRI);
159 ArrayRef<unsigned> Pressure = RPTracker.getRegSetPressureAtPos();
160 unsigned SGPRPressure = Pressure[SRI->getSGPRPressureSet()];
161 unsigned VGPRPressure = Pressure[SRI->getVGPRPressureSet()];
162 ReadyQueue &Q = Zone.Available;
163 for (SUnit *SU : Q) {
165 SchedCandidate TryCand(ZonePolicy);
166 initCandidate(TryCand, SU, Zone.isTop(), RPTracker, SRI,
167 SGPRPressure, VGPRPressure);
168 // Pass SchedBoundary only when comparing nodes from the same boundary.
169 SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
170 GenericScheduler::tryCandidate(Cand, TryCand, ZoneArg);
171 if (TryCand.Reason != NoCand) {
172 // Initialize resource delta if needed in case future heuristics query it.
173 if (TryCand.ResDelta == SchedResourceDelta())
174 TryCand.initResourceDelta(Zone.DAG, SchedModel);
175 Cand.setBest(TryCand);
180 // This function is mostly cut and pasted from
181 // GenericScheduler::pickNodeBidirectional()
182 SUnit *GCNMaxOccupancySchedStrategy::pickNodeBidirectional(bool &IsTopNode) {
183 // Schedule as far as possible in the direction of no choice. This is most
184 // efficient, but also provides the best heuristics for CriticalPSets.
185 if (SUnit *SU = Bot.pickOnlyChoice()) {
189 if (SUnit *SU = Top.pickOnlyChoice()) {
193 // Set the bottom-up policy based on the state of the current bottom zone and
194 // the instructions outside the zone, including the top zone.
195 CandPolicy BotPolicy;
196 setPolicy(BotPolicy, /*IsPostRA=*/false, Bot, &Top);
197 // Set the top-down policy based on the state of the current top zone and
198 // the instructions outside the zone, including the bottom zone.
199 CandPolicy TopPolicy;
200 setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot);
202 // See if BotCand is still valid (because we previously scheduled from Top).
203 DEBUG(dbgs() << "Picking from Bot:\n");
204 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
205 BotCand.Policy != BotPolicy) {
206 BotCand.reset(CandPolicy());
207 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);
208 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
210 DEBUG(traceCandidate(BotCand));
213 // Check if the top Q has a better candidate.
214 DEBUG(dbgs() << "Picking from Top:\n");
215 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
216 TopCand.Policy != TopPolicy) {
217 TopCand.reset(CandPolicy());
218 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);
219 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
221 DEBUG(traceCandidate(TopCand));
224 // Pick best from BotCand and TopCand.
226 dbgs() << "Top Cand: ";
227 traceCandidate(TopCand);
228 dbgs() << "Bot Cand: ";
229 traceCandidate(BotCand);
232 if (TopCand.Reason == BotCand.Reason) {
234 GenericSchedulerBase::CandReason TopReason = TopCand.Reason;
235 TopCand.Reason = NoCand;
236 GenericScheduler::tryCandidate(Cand, TopCand, nullptr);
237 if (TopCand.Reason != NoCand) {
238 Cand.setBest(TopCand);
240 TopCand.Reason = TopReason;
243 if (TopCand.Reason == RegExcess && TopCand.RPDelta.Excess.getUnitInc() <= 0) {
245 } else if (BotCand.Reason == RegExcess && BotCand.RPDelta.Excess.getUnitInc() <= 0) {
247 } else if (TopCand.Reason == RegCritical && TopCand.RPDelta.CriticalMax.getUnitInc() <= 0) {
249 } else if (BotCand.Reason == RegCritical && BotCand.RPDelta.CriticalMax.getUnitInc() <= 0) {
252 if (BotCand.Reason > TopCand.Reason) {
260 dbgs() << "Picking: ";
261 traceCandidate(Cand);
264 IsTopNode = Cand.AtTop;
268 // This function is mostly cut and pasted from
269 // GenericScheduler::pickNode()
270 SUnit *GCNMaxOccupancySchedStrategy::pickNode(bool &IsTopNode) {
271 if (DAG->top() == DAG->bottom()) {
272 assert(Top.Available.empty() && Top.Pending.empty() &&
273 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
278 if (RegionPolicy.OnlyTopDown) {
279 SU = Top.pickOnlyChoice();
282 TopCand.reset(NoPolicy);
283 pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);
284 assert(TopCand.Reason != NoCand && "failed to find a candidate");
288 } else if (RegionPolicy.OnlyBottomUp) {
289 SU = Bot.pickOnlyChoice();
292 BotCand.reset(NoPolicy);
293 pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);
294 assert(BotCand.Reason != NoCand && "failed to find a candidate");
299 SU = pickNodeBidirectional(IsTopNode);
301 } while (SU->isScheduled);
303 if (SU->isTopReady())
305 if (SU->isBottomReady())
308 DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr());
312 GCNScheduleDAGMILive::GCNScheduleDAGMILive(MachineSchedContext *C,
313 std::unique_ptr<MachineSchedStrategy> S) :
314 ScheduleDAGMILive(C, std::move(S)),
315 ST(MF.getSubtarget<SISubtarget>()),
316 MFI(*MF.getInfo<SIMachineFunctionInfo>()),
317 StartingOccupancy(ST.getOccupancyWithLocalMemSize(MFI.getLDSSize(),
319 MinOccupancy(StartingOccupancy), Stage(0), RegionIdx(0) {
321 DEBUG(dbgs() << "Starting occupancy is " << StartingOccupancy << ".\n");
324 void GCNScheduleDAGMILive::schedule() {
326 // Just record regions at the first pass.
327 Regions.push_back(std::make_pair(RegionBegin, RegionEnd));
331 std::vector<MachineInstr*> Unsched;
332 Unsched.reserve(NumRegionInstrs);
333 for (auto &I : *this)
334 Unsched.push_back(&I);
336 GCNRegPressure PressureBefore;
338 PressureBefore = Pressure[RegionIdx];
340 DEBUG(dbgs() << "Pressure before scheduling:\nRegion live-ins:";
341 GCNRPTracker::printLiveRegs(dbgs(), LiveIns[RegionIdx], MRI);
342 dbgs() << "Region live-in pressure: ";
343 llvm::getRegPressure(MRI, LiveIns[RegionIdx]).print(dbgs());
344 dbgs() << "Region register pressure: ";
345 PressureBefore.print(dbgs()));
348 ScheduleDAGMILive::schedule();
349 Regions[RegionIdx] = std::make_pair(RegionBegin, RegionEnd);
354 // Check the results of scheduling.
355 GCNMaxOccupancySchedStrategy &S = (GCNMaxOccupancySchedStrategy&)*SchedImpl;
356 auto PressureAfter = getRealRegPressure();
358 DEBUG(dbgs() << "Pressure after scheduling: "; PressureAfter.print(dbgs()));
360 if (PressureAfter.getSGPRNum() <= S.SGPRCriticalLimit &&
361 PressureAfter.getVGPRNum() <= S.VGPRCriticalLimit) {
362 Pressure[RegionIdx] = PressureAfter;
363 DEBUG(dbgs() << "Pressure in desired limits, done.\n");
366 unsigned WavesAfter = getMaxWaves(PressureAfter.getSGPRNum(),
367 PressureAfter.getVGPRNum(), MF);
368 unsigned WavesBefore = getMaxWaves(PressureBefore.getSGPRNum(),
369 PressureBefore.getVGPRNum(), MF);
370 DEBUG(dbgs() << "Occupancy before scheduling: " << WavesBefore <<
371 ", after " << WavesAfter << ".\n");
373 // We could not keep current target occupancy because of the just scheduled
374 // region. Record new occupancy for next scheduling cycle.
375 unsigned NewOccupancy = std::max(WavesAfter, WavesBefore);
376 if (NewOccupancy < MinOccupancy) {
377 MinOccupancy = NewOccupancy;
378 DEBUG(dbgs() << "Occupancy lowered for the function to "
379 << MinOccupancy << ".\n");
382 if (WavesAfter >= WavesBefore) {
383 Pressure[RegionIdx] = PressureAfter;
387 DEBUG(dbgs() << "Attempting to revert scheduling.\n");
388 RegionEnd = RegionBegin;
389 for (MachineInstr *MI : Unsched) {
390 if (MI->getIterator() != RegionEnd) {
392 BB->insert(RegionEnd, MI);
393 LIS->handleMove(*MI, true);
395 // Reset read-undef flags and update them later.
396 for (auto &Op : MI->operands())
397 if (Op.isReg() && Op.isDef())
398 Op.setIsUndef(false);
399 RegisterOperands RegOpers;
400 RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);
401 if (ShouldTrackLaneMasks) {
402 // Adjust liveness and add missing dead+read-undef flags.
403 SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
404 RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
406 // Adjust for missing dead-def flags.
407 RegOpers.detectDeadDefs(*MI, *LIS);
409 RegionEnd = MI->getIterator();
411 DEBUG(dbgs() << "Scheduling " << *MI);
413 RegionBegin = Unsched.front()->getIterator();
414 Regions[RegionIdx] = std::make_pair(RegionBegin, RegionEnd);
419 GCNRegPressure GCNScheduleDAGMILive::getRealRegPressure() const {
420 GCNDownwardRPTracker RPTracker(*LIS);
421 RPTracker.advance(begin(), end(), &LiveIns[RegionIdx]);
422 return RPTracker.moveMaxPressure();
425 void GCNScheduleDAGMILive::computeBlockPressure(const MachineBasicBlock *MBB) {
426 GCNDownwardRPTracker RPTracker(*LIS);
428 // If the block has the only successor then live-ins of that successor are
429 // live-outs of the current block. We can reuse calculated live set if the
430 // successor will be sent to scheduling past current block.
431 const MachineBasicBlock *OnlySucc = nullptr;
432 if (MBB->succ_size() == 1 && !(*MBB->succ_begin())->empty()) {
433 SlotIndexes *Ind = LIS->getSlotIndexes();
434 if (Ind->getMBBStartIdx(MBB) < Ind->getMBBStartIdx(*MBB->succ_begin()))
435 OnlySucc = *MBB->succ_begin();
438 // Scheduler sends regions from the end of the block upwards.
439 size_t CurRegion = RegionIdx;
440 for (size_t E = Regions.size(); CurRegion != E; ++CurRegion)
441 if (Regions[CurRegion].first->getParent() != MBB)
445 auto I = MBB->begin();
446 auto LiveInIt = MBBLiveIns.find(MBB);
447 if (LiveInIt != MBBLiveIns.end()) {
448 auto LiveIn = std::move(LiveInIt->second);
449 RPTracker.reset(*MBB->begin(), &LiveIn);
450 MBBLiveIns.erase(LiveInIt);
452 I = Regions[CurRegion].first;
457 I = RPTracker.getNext();
459 if (Regions[CurRegion].first == I) {
460 LiveIns[CurRegion] = RPTracker.getLiveRegs();
461 RPTracker.clearMaxPressure();
464 if (Regions[CurRegion].second == I) {
465 Pressure[CurRegion] = RPTracker.moveMaxPressure();
466 if (CurRegion-- == RegionIdx)
469 RPTracker.advanceToNext();
470 RPTracker.advanceBeforeNext();
474 if (I != MBB->end()) {
475 RPTracker.advanceToNext();
476 RPTracker.advance(MBB->end());
478 RPTracker.reset(*OnlySucc->begin(), &RPTracker.getLiveRegs());
479 RPTracker.advanceBeforeNext();
480 MBBLiveIns[OnlySucc] = RPTracker.moveLiveRegs();
484 void GCNScheduleDAGMILive::finalizeSchedule() {
485 GCNMaxOccupancySchedStrategy &S = (GCNMaxOccupancySchedStrategy&)*SchedImpl;
486 DEBUG(dbgs() << "All regions recorded, starting actual scheduling.\n");
488 LiveIns.resize(Regions.size());
489 Pressure.resize(Regions.size());
494 MachineBasicBlock *MBB = nullptr;
497 // Retry function scheduling if we found resulting occupancy and it is
498 // lower than used for first pass scheduling. This will give more freedom
499 // to schedule low register pressure blocks.
500 // Code is partially copied from MachineSchedulerBase::scheduleRegions().
502 if (!LIS || StartingOccupancy <= MinOccupancy)
506 << "Retrying function scheduling with lowest recorded occupancy "
507 << MinOccupancy << ".\n");
509 S.setTargetOccupancy(MinOccupancy);
512 for (auto Region : Regions) {
513 RegionBegin = Region.first;
514 RegionEnd = Region.second;
516 if (RegionBegin->getParent() != MBB) {
517 if (MBB) finishBlock();
518 MBB = RegionBegin->getParent();
521 computeBlockPressure(MBB);
524 unsigned NumRegionInstrs = std::distance(begin(), end());
525 enterRegion(MBB, begin(), end(), NumRegionInstrs);
527 // Skip empty scheduling regions (0 or 1 schedulable instructions).
528 if (begin() == end() || begin() == std::prev(end())) {
533 DEBUG(dbgs() << "********** MI Scheduling **********\n");
534 DEBUG(dbgs() << MF.getName()
535 << ":BB#" << MBB->getNumber() << " " << MBB->getName()
536 << "\n From: " << *begin() << " To: ";
537 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;
538 else dbgs() << "End";
539 dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n');