1 //===- GCNIterativeScheduler.cpp ------------------------------------------===//
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 //===----------------------------------------------------------------------===//
10 #include "GCNIterativeScheduler.h"
11 #include "AMDGPUSubtarget.h"
12 #include "GCNRegPressure.h"
13 #include "GCNSchedStrategy.h"
14 #include "SIMachineFunctionInfo.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/CodeGen/LiveIntervals.h"
19 #include "llvm/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/RegisterPressure.h"
22 #include "llvm/CodeGen/ScheduleDAG.h"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
32 #include <type_traits>
37 #define DEBUG_TYPE "machine-scheduler"
41 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
42 const ScheduleDAG &DAG);
44 std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
45 const ScheduleDAG &DAG);
48 // shim accessors for different order containers
49 static inline MachineInstr *getMachineInstr(MachineInstr *MI) {
52 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
53 return SU->getInstr();
55 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
59 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
61 static void printRegion(raw_ostream &OS,
62 MachineBasicBlock::iterator Begin,
63 MachineBasicBlock::iterator End,
64 const LiveIntervals *LIS,
66 std::numeric_limits<unsigned>::max()) {
67 auto BB = Begin->getParent();
68 OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
69 << BB->getName() << ":\n";
71 MaxInstNum = std::max(MaxInstNum, 1u);
72 for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
73 if (!I->isDebugInstr() && LIS)
74 OS << LIS->getInstructionIndex(*I);
80 if (!I->isDebugInstr() && LIS)
81 OS << LIS->getInstructionIndex(*I);
84 if (End != BB->end()) { // print boundary inst if present
86 if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
92 static void printLivenessInfo(raw_ostream &OS,
93 MachineBasicBlock::iterator Begin,
94 MachineBasicBlock::iterator End,
95 const LiveIntervals *LIS) {
96 const auto BB = Begin->getParent();
97 const auto &MRI = BB->getParent()->getRegInfo();
99 const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
101 getRegPressure(MRI, LiveIns).print(OS);
103 const auto BottomMI = End == BB->end() ? std::prev(End) : End;
104 const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
106 getRegPressure(MRI, LiveOuts).print(OS);
110 void GCNIterativeScheduler::printRegions(raw_ostream &OS) const {
111 const auto &ST = MF.getSubtarget<GCNSubtarget>();
112 for (const auto R : Regions) {
113 OS << "Region to schedule ";
114 printRegion(OS, R->Begin, R->End, LIS, 1);
115 printLivenessInfo(OS, R->Begin, R->End, LIS);
117 R->MaxPressure.print(OS, &ST);
122 void GCNIterativeScheduler::printSchedResult(raw_ostream &OS,
124 const GCNRegPressure &RP) const {
125 OS << "\nAfter scheduling ";
126 printRegion(OS, R->Begin, R->End, LIS);
127 printSchedRP(OS, R->MaxPressure, RP);
132 void GCNIterativeScheduler::printSchedRP(raw_ostream &OS,
133 const GCNRegPressure &Before,
134 const GCNRegPressure &After) const {
135 const auto &ST = MF.getSubtarget<GCNSubtarget>();
137 Before.print(OS, &ST);
139 After.print(OS, &ST);
143 // DAG builder helper
144 class GCNIterativeScheduler::BuildDAG {
145 GCNIterativeScheduler &Sch;
146 SmallVector<SUnit *, 8> TopRoots;
148 SmallVector<SUnit*, 8> BotRoots;
150 BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
152 auto BB = R.Begin->getParent();
153 Sch.BaseClass::startBlock(BB);
154 Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
156 Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
157 /*TrackLaneMask*/true);
158 Sch.Topo.InitDAGTopologicalSorting();
159 Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
163 Sch.BaseClass::exitRegion();
164 Sch.BaseClass::finishBlock();
167 ArrayRef<const SUnit *> getTopRoots() const {
170 ArrayRef<SUnit*> getBottomRoots() const {
175 class GCNIterativeScheduler::OverrideLegacyStrategy {
176 GCNIterativeScheduler &Sch;
178 std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
179 GCNRegPressure SaveMaxRP;
182 OverrideLegacyStrategy(Region &R,
183 MachineSchedStrategy &OverrideStrategy,
184 GCNIterativeScheduler &_Sch)
187 , SaveSchedImpl(std::move(_Sch.SchedImpl))
188 , SaveMaxRP(R.MaxPressure) {
189 Sch.SchedImpl.reset(&OverrideStrategy);
190 auto BB = R.Begin->getParent();
191 Sch.BaseClass::startBlock(BB);
192 Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
195 ~OverrideLegacyStrategy() {
196 Sch.BaseClass::exitRegion();
197 Sch.BaseClass::finishBlock();
198 Sch.SchedImpl.release();
199 Sch.SchedImpl = std::move(SaveSchedImpl);
203 assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
204 LLVM_DEBUG(dbgs() << "\nScheduling ";
205 printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
206 Sch.BaseClass::schedule();
208 // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
209 Sch.RegionEnd = Rgn.End;
210 //assert(Rgn.End == Sch.RegionEnd);
211 Rgn.Begin = Sch.RegionBegin;
212 Rgn.MaxPressure.clear();
215 void restoreOrder() {
216 assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
217 // DAG SUnits are stored using original region's order
218 // so just use SUnits as the restoring schedule
219 Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
225 // just a stub to make base class happy
226 class SchedStrategyStub : public MachineSchedStrategy {
228 bool shouldTrackPressure() const override { return false; }
229 bool shouldTrackLaneMasks() const override { return false; }
230 void initialize(ScheduleDAGMI *DAG) override {}
231 SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
232 void schedNode(SUnit *SU, bool IsTopNode) override {}
233 void releaseTopNode(SUnit *SU) override {}
234 void releaseBottomNode(SUnit *SU) override {}
237 } // end anonymous namespace
239 GCNIterativeScheduler::GCNIterativeScheduler(MachineSchedContext *C,
241 : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
247 // returns max pressure for a region
249 GCNIterativeScheduler::getRegionPressure(MachineBasicBlock::iterator Begin,
250 MachineBasicBlock::iterator End)
252 // For the purpose of pressure tracking bottom inst of the region should
253 // be also processed. End is either BB end, BB terminator inst or sched
255 auto const BBEnd = Begin->getParent()->end();
256 auto const BottomMI = End == BBEnd ? std::prev(End) : End;
258 // scheduleRegions walks bottom to top, so its likely we just get next
259 // instruction to track
260 auto AfterBottomMI = std::next(BottomMI);
261 if (AfterBottomMI == BBEnd ||
262 &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
263 UPTracker.reset(*BottomMI);
265 assert(UPTracker.isValid());
268 for (auto I = BottomMI; I != Begin; --I)
269 UPTracker.recede(*I);
271 UPTracker.recede(*Begin);
273 assert(UPTracker.isValid() ||
274 (dbgs() << "Tracked region ",
275 printRegion(dbgs(), Begin, End, LIS), false));
276 return UPTracker.moveMaxPressure();
279 // returns max pressure for a tentative schedule
280 template <typename Range> GCNRegPressure
281 GCNIterativeScheduler::getSchedulePressure(const Region &R,
282 Range &&Schedule) const {
283 auto const BBEnd = R.Begin->getParent()->end();
284 GCNUpwardRPTracker RPTracker(*LIS);
285 if (R.End != BBEnd) {
286 // R.End points to the boundary instruction but the
287 // schedule doesn't include it
288 RPTracker.reset(*R.End);
289 RPTracker.recede(*R.End);
291 // R.End doesn't point to the boundary instruction
292 RPTracker.reset(*std::prev(BBEnd));
294 for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
295 RPTracker.recede(*getMachineInstr(*--I));
297 return RPTracker.moveMaxPressure();
300 void GCNIterativeScheduler::enterRegion(MachineBasicBlock *BB, // overriden
301 MachineBasicBlock::iterator Begin,
302 MachineBasicBlock::iterator End,
303 unsigned NumRegionInstrs) {
304 BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
305 if (NumRegionInstrs > 2) {
307 new (Alloc.Allocate())
308 Region { Begin, End, NumRegionInstrs,
309 getRegionPressure(Begin, End), nullptr });
313 void GCNIterativeScheduler::schedule() { // overriden
315 LLVM_DEBUG(printLivenessInfo(dbgs(), RegionBegin, RegionEnd, LIS);
316 if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
317 dbgs() << "Max RP: ";
318 Regions.back()->MaxPressure.print(
319 dbgs(), &MF.getSubtarget<GCNSubtarget>());
324 void GCNIterativeScheduler::finalizeSchedule() { // overriden
328 case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
329 case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
330 case SCHEDULE_LEGACYMAXOCCUPANCY: scheduleLegacyMaxOccupancy(); break;
331 case SCHEDULE_ILP: scheduleILP(false); break;
335 // Detach schedule from SUnits and interleave it with debug values.
336 // Returned schedule becomes independent of DAG state.
337 std::vector<MachineInstr*>
338 GCNIterativeScheduler::detachSchedule(ScheduleRef Schedule) const {
339 std::vector<MachineInstr*> Res;
340 Res.reserve(Schedule.size() * 2);
343 Res.push_back(FirstDbgValue);
345 const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
346 for (auto SU : Schedule) {
347 Res.push_back(SU->getInstr());
348 const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
349 return P.second == SU->getInstr();
352 Res.push_back(D->first);
357 void GCNIterativeScheduler::setBestSchedule(Region &R,
358 ScheduleRef Schedule,
359 const GCNRegPressure &MaxRP) {
360 R.BestSchedule.reset(
361 new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
364 void GCNIterativeScheduler::scheduleBest(Region &R) {
365 assert(R.BestSchedule.get() && "No schedule specified");
366 scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
367 R.BestSchedule.reset();
370 // minimal required region scheduler, works for ranges of SUnits*,
371 // SUnits or MachineIntrs*
372 template <typename Range>
373 void GCNIterativeScheduler::scheduleRegion(Region &R, Range &&Schedule,
374 const GCNRegPressure &MaxRP) {
375 assert(RegionBegin == R.Begin && RegionEnd == R.End);
376 assert(LIS != nullptr);
378 const auto SchedMaxRP = getSchedulePressure(R, Schedule);
380 auto BB = R.Begin->getParent();
382 for (const auto &I : Schedule) {
383 auto MI = getMachineInstr(I);
387 if (!MI->isDebugInstr())
388 LIS->handleMove(*MI, true);
390 if (!MI->isDebugInstr()) {
391 // Reset read - undef flags and update them later.
392 for (auto &Op : MI->operands())
393 if (Op.isReg() && Op.isDef())
394 Op.setIsUndef(false);
396 RegisterOperands RegOpers;
397 RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
398 /*IgnoreDead*/false);
399 // Adjust liveness and add missing dead+read-undef flags.
400 auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
401 RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
403 Top = std::next(MI->getIterator());
405 RegionBegin = getMachineInstr(Schedule.front());
407 // Schedule consisting of MachineInstr* is considered 'detached'
408 // and already interleaved with debug values
409 if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
411 // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
412 //assert(R.End == RegionEnd);
416 R.Begin = RegionBegin;
417 R.MaxPressure = MaxRP;
420 const auto RegionMaxRP = getRegionPressure(R);
421 const auto &ST = MF.getSubtarget<GCNSubtarget>();
423 assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
424 || (dbgs() << "Max RP mismatch!!!\n"
425 "RP for schedule (calculated): ",
426 SchedMaxRP.print(dbgs(), &ST),
427 dbgs() << "RP for schedule (reported): ",
428 MaxRP.print(dbgs(), &ST),
429 dbgs() << "RP after scheduling: ",
430 RegionMaxRP.print(dbgs(), &ST),
434 // Sort recorded regions by pressure - highest at the front
435 void GCNIterativeScheduler::sortRegionsByPressure(unsigned TargetOcc) {
436 const auto &ST = MF.getSubtarget<GCNSubtarget>();
437 llvm::sort(Regions, [&ST, TargetOcc](const Region *R1, const Region *R2) {
438 return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
442 ///////////////////////////////////////////////////////////////////////////////
443 // Legacy MaxOccupancy Strategy
445 // Tries to increase occupancy applying minreg scheduler for a sequence of
446 // most demanding regions. Obtained schedules are saved as BestSchedule for a
448 // TargetOcc is the best achievable occupancy for a kernel.
449 // Returns better occupancy on success or current occupancy on fail.
450 // BestSchedules aren't deleted on fail.
451 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
452 // TODO: assert Regions are sorted descending by pressure
453 const auto &ST = MF.getSubtarget<GCNSubtarget>();
454 const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
455 LLVM_DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
456 << ", current = " << Occ << '\n');
458 auto NewOcc = TargetOcc;
459 for (auto R : Regions) {
460 if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
463 LLVM_DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
464 printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
466 BuildDAG DAG(*R, *this);
467 const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
468 const auto MaxRP = getSchedulePressure(*R, MinSchedule);
469 LLVM_DEBUG(dbgs() << "Occupancy improvement attempt:\n";
470 printSchedRP(dbgs(), R->MaxPressure, MaxRP));
472 NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
476 setBestSchedule(*R, MinSchedule, MaxRP);
478 LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
479 << ", prev occupancy = " << Occ << '\n');
481 SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
482 MFI->increaseOccupancy(MF, NewOcc);
485 return std::max(NewOcc, Occ);
488 void GCNIterativeScheduler::scheduleLegacyMaxOccupancy(
489 bool TryMaximizeOccupancy) {
490 const auto &ST = MF.getSubtarget<GCNSubtarget>();
491 SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
492 auto TgtOcc = MFI->getMinAllowedOccupancy();
494 sortRegionsByPressure(TgtOcc);
495 auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
497 if (TryMaximizeOccupancy && Occ < TgtOcc)
498 Occ = tryMaximizeOccupancy(TgtOcc);
500 // This is really weird but for some magic scheduling regions twice
501 // gives performance improvement
502 const int NumPasses = Occ < TgtOcc ? 2 : 1;
504 TgtOcc = std::min(Occ, TgtOcc);
505 LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
506 "target occupancy = "
508 GCNMaxOccupancySchedStrategy LStrgy(Context);
509 unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
511 for (int I = 0; I < NumPasses; ++I) {
512 // running first pass with TargetOccupancy = 0 mimics previous scheduling
513 // approach and is a performance magic
514 LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
515 for (auto R : Regions) {
516 OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
519 const auto RP = getRegionPressure(*R);
520 LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
522 if (RP.getOccupancy(ST) < TgtOcc) {
523 LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
524 if (R->BestSchedule.get() &&
525 R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
526 LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
529 LLVM_DEBUG(dbgs() << ", restoring\n");
531 assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
534 FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
537 MFI->limitOccupancy(FinalOccupancy);
540 ///////////////////////////////////////////////////////////////////////////////
541 // Minimal Register Strategy
543 void GCNIterativeScheduler::scheduleMinReg(bool force) {
544 const auto &ST = MF.getSubtarget<GCNSubtarget>();
545 const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
546 const auto TgtOcc = MFI->getOccupancy();
547 sortRegionsByPressure(TgtOcc);
549 auto MaxPressure = Regions.front()->MaxPressure;
550 for (auto R : Regions) {
551 if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
554 BuildDAG DAG(*R, *this);
555 const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
557 const auto RP = getSchedulePressure(*R, MinSchedule);
558 LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
559 dbgs() << "\nWarning: Pressure becomes worse after minreg!";
560 printSchedRP(dbgs(), R->MaxPressure, RP);
563 if (!force && MaxPressure.less(ST, RP, TgtOcc))
566 scheduleRegion(*R, MinSchedule, RP);
567 LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
573 ///////////////////////////////////////////////////////////////////////////////
574 // ILP scheduler port
576 void GCNIterativeScheduler::scheduleILP(
577 bool TryMaximizeOccupancy) {
578 const auto &ST = MF.getSubtarget<GCNSubtarget>();
579 SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
580 auto TgtOcc = MFI->getMinAllowedOccupancy();
582 sortRegionsByPressure(TgtOcc);
583 auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
585 if (TryMaximizeOccupancy && Occ < TgtOcc)
586 Occ = tryMaximizeOccupancy(TgtOcc);
588 TgtOcc = std::min(Occ, TgtOcc);
589 LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
590 "target occupancy = "
593 unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
594 for (auto R : Regions) {
595 BuildDAG DAG(*R, *this);
596 const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
598 const auto RP = getSchedulePressure(*R, ILPSchedule);
599 LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
601 if (RP.getOccupancy(ST) < TgtOcc) {
602 LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
603 if (R->BestSchedule.get() &&
604 R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
605 LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
609 scheduleRegion(*R, ILPSchedule, RP);
610 LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
611 FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
614 MFI->limitOccupancy(FinalOccupancy);