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 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
14 #include "GCNIterativeScheduler.h"
15 #include "GCNSchedStrategy.h"
16 #include "SIMachineFunctionInfo.h"
20 #define DEBUG_TYPE "machine-scheduler"
23 std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
24 const ScheduleDAG &DAG);
27 // shim accessors for different order containers
28 static inline MachineInstr *getMachineInstr(MachineInstr *MI) {
31 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
32 return SU->getInstr();
34 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
38 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
40 static void printRegion(raw_ostream &OS,
41 MachineBasicBlock::iterator Begin,
42 MachineBasicBlock::iterator End,
43 const LiveIntervals *LIS,
45 std::numeric_limits<unsigned>::max()) {
46 auto BB = Begin->getParent();
47 OS << BB->getParent()->getName() << ":BB#" << BB->getNumber()
48 << ' ' << BB->getName() << ":\n";
50 MaxInstNum = std::max(MaxInstNum, 1u);
51 for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
52 if (!I->isDebugValue() && LIS)
53 OS << LIS->getInstructionIndex(*I);
59 if (!I->isDebugValue() && LIS)
60 OS << LIS->getInstructionIndex(*I);
63 if (End != BB->end()) { // print boundary inst if present
65 if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
71 static void printLivenessInfo(raw_ostream &OS,
72 MachineBasicBlock::iterator Begin,
73 MachineBasicBlock::iterator End,
74 const LiveIntervals *LIS) {
75 const auto BB = Begin->getParent();
76 const auto &MRI = BB->getParent()->getRegInfo();
78 const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
80 getRegPressure(MRI, LiveIns).print(OS);
82 const auto BottomMI = End == BB->end() ? std::prev(End) : End;
83 const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
85 getRegPressure(MRI, LiveOuts).print(OS);
89 void GCNIterativeScheduler::printRegions(raw_ostream &OS) const {
90 const auto &ST = MF.getSubtarget<SISubtarget>();
91 for (const auto R : Regions) {
92 OS << "Region to schedule ";
93 printRegion(OS, R->Begin, R->End, LIS, 1);
94 printLivenessInfo(OS, R->Begin, R->End, LIS);
96 R->MaxPressure.print(OS, &ST);
101 void GCNIterativeScheduler::printSchedResult(raw_ostream &OS,
103 const GCNRegPressure &RP) const {
104 OS << "\nAfter scheduling ";
105 printRegion(OS, R->Begin, R->End, LIS);
106 printSchedRP(OS, R->MaxPressure, RP);
111 void GCNIterativeScheduler::printSchedRP(raw_ostream &OS,
112 const GCNRegPressure &Before,
113 const GCNRegPressure &After) const {
114 const auto &ST = MF.getSubtarget<SISubtarget>();
116 Before.print(OS, &ST);
118 After.print(OS, &ST);
123 // DAG builder helper
124 class GCNIterativeScheduler::BuildDAG {
125 GCNIterativeScheduler &Sch;
126 SmallVector<SUnit*, 8> TopRoots;
128 BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
130 auto BB = R.Begin->getParent();
131 Sch.BaseClass::startBlock(BB);
132 Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
134 Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
135 /*TrackLaneMask*/true);
136 Sch.Topo.InitDAGTopologicalSorting();
138 SmallVector<SUnit*, 8> BotRoots;
139 Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
142 Sch.BaseClass::exitRegion();
143 Sch.BaseClass::finishBlock();
145 ArrayRef<const SUnit*> getTopRoots() const {
150 class GCNIterativeScheduler::OverrideLegacyStrategy {
151 GCNIterativeScheduler &Sch;
153 std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
154 GCNRegPressure SaveMaxRP;
156 OverrideLegacyStrategy(Region &R,
157 MachineSchedStrategy &OverrideStrategy,
158 GCNIterativeScheduler &_Sch)
161 , SaveSchedImpl(std::move(_Sch.SchedImpl))
162 , SaveMaxRP(R.MaxPressure) {
163 Sch.SchedImpl.reset(&OverrideStrategy);
164 auto BB = R.Begin->getParent();
165 Sch.BaseClass::startBlock(BB);
166 Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
168 ~OverrideLegacyStrategy() {
169 Sch.BaseClass::exitRegion();
170 Sch.BaseClass::finishBlock();
171 Sch.SchedImpl.release();
172 Sch.SchedImpl = std::move(SaveSchedImpl);
175 assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
176 DEBUG(dbgs() << "\nScheduling ";
177 printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
178 Sch.BaseClass::schedule();
180 // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
181 Sch.RegionEnd = Rgn.End;
182 //assert(Rgn.End == Sch.RegionEnd);
183 Rgn.Begin = Sch.RegionBegin;
184 Rgn.MaxPressure.clear();
186 void restoreOrder() {
187 assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
188 // DAG SUnits are stored using original region's order
189 // so just use SUnits as the restoring schedule
190 Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
195 // just a stub to make base class happy
196 class SchedStrategyStub : public MachineSchedStrategy {
198 bool shouldTrackPressure() const override { return false; }
199 bool shouldTrackLaneMasks() const override { return false; }
200 void initialize(ScheduleDAGMI *DAG) override {}
201 SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
202 void schedNode(SUnit *SU, bool IsTopNode) override {}
203 void releaseTopNode(SUnit *SU) override {}
204 void releaseBottomNode(SUnit *SU) override {}
208 GCNIterativeScheduler::GCNIterativeScheduler(MachineSchedContext *C,
210 : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
216 // returns max pressure for a region
218 GCNIterativeScheduler::getRegionPressure(MachineBasicBlock::iterator Begin,
219 MachineBasicBlock::iterator End)
221 // For the purpose of pressure tracking bottom inst of the region should
222 // be also processed. End is either BB end, BB terminator inst or sched
224 auto const BBEnd = Begin->getParent()->end();
225 auto const BottomMI = End == BBEnd ? std::prev(End) : End;
227 // scheduleRegions walks bottom to top, so its likely we just get next
228 // instruction to track
229 auto AfterBottomMI = std::next(BottomMI);
230 if (AfterBottomMI == BBEnd ||
231 &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
232 UPTracker.reset(*BottomMI);
234 assert(UPTracker.isValid());
237 for (auto I = BottomMI; I != Begin; --I)
238 UPTracker.recede(*I);
240 UPTracker.recede(*Begin);
242 assert(UPTracker.isValid() ||
243 (dbgs() << "Tracked region ",
244 printRegion(dbgs(), Begin, End, LIS), false));
245 return UPTracker.moveMaxPressure();
248 // returns max pressure for a tentative schedule
249 template <typename Range> GCNRegPressure
250 GCNIterativeScheduler::getSchedulePressure(const Region &R,
251 Range &&Schedule) const {
252 auto const BBEnd = R.Begin->getParent()->end();
253 GCNUpwardRPTracker RPTracker(*LIS);
254 if (R.End != BBEnd) {
255 // R.End points to the boundary instruction but the
256 // schedule doesn't include it
257 RPTracker.reset(*R.End);
258 RPTracker.recede(*R.End);
260 // R.End doesn't point to the boundary instruction
261 RPTracker.reset(*std::prev(BBEnd));
263 for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
264 RPTracker.recede(*getMachineInstr(*--I));
266 return RPTracker.moveMaxPressure();
269 void GCNIterativeScheduler::enterRegion(MachineBasicBlock *BB, // overriden
270 MachineBasicBlock::iterator Begin,
271 MachineBasicBlock::iterator End,
272 unsigned NumRegionInstrs) {
273 BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
274 if (NumRegionInstrs > 2) {
276 new (Alloc.Allocate())
277 Region { Begin, End, NumRegionInstrs,
278 getRegionPressure(Begin, End), nullptr });
282 void GCNIterativeScheduler::schedule() { // overriden
285 printLivenessInfo(dbgs(), RegionBegin, RegionEnd, LIS);
286 if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
287 dbgs() << "Max RP: ";
288 Regions.back()->MaxPressure.print(dbgs(), &MF.getSubtarget<SISubtarget>());
294 void GCNIterativeScheduler::finalizeSchedule() { // overriden
298 case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
299 case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
300 case SCHEDULE_LEGACYMAXOCCUPANCY: scheduleLegacyMaxOccupancy(); break;
304 // Detach schedule from SUnits and interleave it with debug values.
305 // Returned schedule becomes independent of DAG state.
306 std::vector<MachineInstr*>
307 GCNIterativeScheduler::detachSchedule(ScheduleRef Schedule) const {
308 std::vector<MachineInstr*> Res;
309 Res.reserve(Schedule.size() * 2);
312 Res.push_back(FirstDbgValue);
314 const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
315 for (auto SU : Schedule) {
316 Res.push_back(SU->getInstr());
317 const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
318 return P.second == SU->getInstr();
321 Res.push_back(D->first);
326 void GCNIterativeScheduler::setBestSchedule(Region &R,
327 ScheduleRef Schedule,
328 const GCNRegPressure &MaxRP) {
329 R.BestSchedule.reset(
330 new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
333 void GCNIterativeScheduler::scheduleBest(Region &R) {
334 assert(R.BestSchedule.get() && "No schedule specified");
335 scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
336 R.BestSchedule.reset();
339 // minimal required region scheduler, works for ranges of SUnits*,
340 // SUnits or MachineIntrs*
341 template <typename Range>
342 void GCNIterativeScheduler::scheduleRegion(Region &R, Range &&Schedule,
343 const GCNRegPressure &MaxRP) {
344 assert(RegionBegin == R.Begin && RegionEnd == R.End);
345 assert(LIS != nullptr);
347 const auto SchedMaxRP = getSchedulePressure(R, Schedule);
349 auto BB = R.Begin->getParent();
351 for (const auto &I : Schedule) {
352 auto MI = getMachineInstr(I);
356 if (!MI->isDebugValue())
357 LIS->handleMove(*MI, true);
359 if (!MI->isDebugValue()) {
360 // Reset read - undef flags and update them later.
361 for (auto &Op : MI->operands())
362 if (Op.isReg() && Op.isDef())
363 Op.setIsUndef(false);
365 RegisterOperands RegOpers;
366 RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
367 /*IgnoreDead*/false);
368 // Adjust liveness and add missing dead+read-undef flags.
369 auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
370 RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
372 Top = std::next(MI->getIterator());
374 RegionBegin = getMachineInstr(Schedule.front());
376 // Schedule consisting of MachineInstr* is considered 'detached'
377 // and already interleaved with debug values
378 if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
380 // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
381 //assert(R.End == RegionEnd);
385 R.Begin = RegionBegin;
386 R.MaxPressure = MaxRP;
389 const auto RegionMaxRP = getRegionPressure(R);
390 const auto &ST = MF.getSubtarget<SISubtarget>();
392 assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
393 || (dbgs() << "Max RP mismatch!!!\n"
394 "RP for schedule (calculated): ",
395 SchedMaxRP.print(dbgs(), &ST),
396 dbgs() << "RP for schedule (reported): ",
397 MaxRP.print(dbgs(), &ST),
398 dbgs() << "RP after scheduling: ",
399 RegionMaxRP.print(dbgs(), &ST),
403 // Sort recorded regions by pressure - highest at the front
404 void GCNIterativeScheduler::sortRegionsByPressure(unsigned TargetOcc) {
405 const auto &ST = MF.getSubtarget<SISubtarget>();
406 std::sort(Regions.begin(), Regions.end(),
407 [&ST, TargetOcc](const Region *R1, const Region *R2) {
408 return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
412 ///////////////////////////////////////////////////////////////////////////////
413 // Legacy MaxOccupancy Strategy
415 // Tries to increase occupancy applying minreg scheduler for a sequence of
416 // most demanding regions. Obtained schedules are saved as BestSchedule for a
418 // TargetOcc is the best achievable occupancy for a kernel.
419 // Returns better occupancy on success or current occupancy on fail.
420 // BestSchedules aren't deleted on fail.
421 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
422 // TODO: assert Regions are sorted descending by pressure
423 const auto &ST = MF.getSubtarget<SISubtarget>();
424 const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
425 DEBUG(dbgs() << "Trying to to improve occupancy, target = " << TargetOcc
426 << ", current = " << Occ << '\n');
428 auto NewOcc = TargetOcc;
429 for (auto R : Regions) {
430 if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
433 DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
434 printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
436 BuildDAG DAG(*R, *this);
437 const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
438 const auto MaxRP = getSchedulePressure(*R, MinSchedule);
439 DEBUG(dbgs() << "Occupancy improvement attempt:\n";
440 printSchedRP(dbgs(), R->MaxPressure, MaxRP));
442 NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
446 setBestSchedule(*R, MinSchedule, MaxRP);
448 DEBUG(dbgs() << "New occupancy = " << NewOcc
449 << ", prev occupancy = " << Occ << '\n');
450 return std::max(NewOcc, Occ);
453 void GCNIterativeScheduler::scheduleLegacyMaxOccupancy(
454 bool TryMaximizeOccupancy) {
455 const auto &ST = MF.getSubtarget<SISubtarget>();
456 auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
458 sortRegionsByPressure(TgtOcc);
459 auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
461 if (TryMaximizeOccupancy && Occ < TgtOcc)
462 Occ = tryMaximizeOccupancy(TgtOcc);
464 // This is really weird but for some magic scheduling regions twice
465 // gives performance improvement
466 const int NumPasses = Occ < TgtOcc ? 2 : 1;
468 TgtOcc = std::min(Occ, TgtOcc);
469 DEBUG(dbgs() << "Scheduling using default scheduler, "
470 "target occupancy = " << TgtOcc << '\n');
471 GCNMaxOccupancySchedStrategy LStrgy(Context);
473 for (int I = 0; I < NumPasses; ++I) {
474 // running first pass with TargetOccupancy = 0 mimics previous scheduling
475 // approach and is a performance magic
476 LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
477 for (auto R : Regions) {
478 OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
481 const auto RP = getRegionPressure(*R);
482 DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
484 if (RP.getOccupancy(ST) < TgtOcc) {
485 DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
486 if (R->BestSchedule.get() &&
487 R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
488 DEBUG(dbgs() << ", scheduling minimal register\n");
491 DEBUG(dbgs() << ", restoring\n");
493 assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
500 ///////////////////////////////////////////////////////////////////////////////
501 // Minimal Register Strategy
503 void GCNIterativeScheduler::scheduleMinReg(bool force) {
504 const auto &ST = MF.getSubtarget<SISubtarget>();
505 const auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
506 sortRegionsByPressure(TgtOcc);
508 auto MaxPressure = Regions.front()->MaxPressure;
509 for (auto R : Regions) {
510 if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
513 BuildDAG DAG(*R, *this);
514 const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
516 const auto RP = getSchedulePressure(*R, MinSchedule);
517 DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
518 dbgs() << "\nWarning: Pressure becomes worse after minreg!";
519 printSchedRP(dbgs(), R->MaxPressure, RP);
522 if (!force && MaxPressure.less(ST, RP, TgtOcc))
525 scheduleRegion(*R, MinSchedule, RP);
526 DEBUG(printSchedResult(dbgs(), R, RP));