1 //===- GCNIterativeScheduler.cpp ------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "GCNIterativeScheduler.h"
11 #include "AMDGPUSubtarget.h"
12 #include "GCNRegPressure.h"
13 #include "GCNSchedStrategy.h"
14 #include "llvm/ADT/ArrayRef.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/CodeGen/LiveIntervals.h"
18 #include "llvm/CodeGen/MachineBasicBlock.h"
19 #include "llvm/CodeGen/MachineFunction.h"
20 #include "llvm/CodeGen/RegisterPressure.h"
21 #include "llvm/CodeGen/ScheduleDAG.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include <algorithm>
27 #include <cassert>
28 #include <iterator>
29 #include <limits>
30 #include <memory>
31 #include <type_traits>
32 #include <vector>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "machine-scheduler"
37 
38 namespace llvm {
39 
40 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
41                                               const ScheduleDAG &DAG);
42 
43   std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
44     const ScheduleDAG &DAG);
45 }
46 
47 // shim accessors for different order containers
48 static inline MachineInstr *getMachineInstr(MachineInstr *MI) {
49   return MI;
50 }
51 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
52   return SU->getInstr();
53 }
54 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
55   return SU.getInstr();
56 }
57 
58 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
59 LLVM_DUMP_METHOD
60 static void printRegion(raw_ostream &OS,
61                         MachineBasicBlock::iterator Begin,
62                         MachineBasicBlock::iterator End,
63                         const LiveIntervals *LIS,
64                         unsigned MaxInstNum =
65                           std::numeric_limits<unsigned>::max()) {
66   auto BB = Begin->getParent();
67   OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
68      << BB->getName() << ":\n";
69   auto I = Begin;
70   MaxInstNum = std::max(MaxInstNum, 1u);
71   for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
72     if (!I->isDebugInstr() && LIS)
73       OS << LIS->getInstructionIndex(*I);
74     OS << '\t' << *I;
75   }
76   if (I != End) {
77     OS << "\t...\n";
78     I = std::prev(End);
79     if (!I->isDebugInstr() && LIS)
80       OS << LIS->getInstructionIndex(*I);
81     OS << '\t' << *I;
82   }
83   if (End != BB->end()) { // print boundary inst if present
84     OS << "----\n";
85     if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
86     OS << *End;
87   }
88 }
89 
90 LLVM_DUMP_METHOD
91 static void printLivenessInfo(raw_ostream &OS,
92                               MachineBasicBlock::iterator Begin,
93                               MachineBasicBlock::iterator End,
94                               const LiveIntervals *LIS) {
95   const auto BB = Begin->getParent();
96   const auto &MRI = BB->getParent()->getRegInfo();
97 
98   const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
99   OS << "LIn RP: ";
100   getRegPressure(MRI, LiveIns).print(OS);
101 
102   const auto BottomMI = End == BB->end() ? std::prev(End) : End;
103   const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
104   OS << "LOt RP: ";
105   getRegPressure(MRI, LiveOuts).print(OS);
106 }
107 
108 LLVM_DUMP_METHOD
109 void GCNIterativeScheduler::printRegions(raw_ostream &OS) const {
110   const auto &ST = MF.getSubtarget<SISubtarget>();
111   for (const auto R : Regions) {
112     OS << "Region to schedule ";
113     printRegion(OS, R->Begin, R->End, LIS, 1);
114     printLivenessInfo(OS, R->Begin, R->End, LIS);
115     OS << "Max RP: ";
116     R->MaxPressure.print(OS, &ST);
117   }
118 }
119 
120 LLVM_DUMP_METHOD
121 void GCNIterativeScheduler::printSchedResult(raw_ostream &OS,
122                                              const Region *R,
123                                              const GCNRegPressure &RP) const {
124   OS << "\nAfter scheduling ";
125   printRegion(OS, R->Begin, R->End, LIS);
126   printSchedRP(OS, R->MaxPressure, RP);
127   OS << '\n';
128 }
129 
130 LLVM_DUMP_METHOD
131 void GCNIterativeScheduler::printSchedRP(raw_ostream &OS,
132                                          const GCNRegPressure &Before,
133                                          const GCNRegPressure &After) const {
134   const auto &ST = MF.getSubtarget<SISubtarget>();
135   OS << "RP before: ";
136   Before.print(OS, &ST);
137   OS << "RP after:  ";
138   After.print(OS, &ST);
139 }
140 #endif
141 
142 // DAG builder helper
143 class GCNIterativeScheduler::BuildDAG {
144   GCNIterativeScheduler &Sch;
145   SmallVector<SUnit *, 8> TopRoots;
146 
147   SmallVector<SUnit*, 8> BotRoots;
148 public:
149   BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
150     : Sch(_Sch) {
151     auto BB = R.Begin->getParent();
152     Sch.BaseClass::startBlock(BB);
153     Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
154 
155     Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
156                         /*TrackLaneMask*/true);
157     Sch.Topo.InitDAGTopologicalSorting();
158     Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
159   }
160 
161   ~BuildDAG() {
162     Sch.BaseClass::exitRegion();
163     Sch.BaseClass::finishBlock();
164   }
165 
166   ArrayRef<const SUnit *> getTopRoots() const {
167     return TopRoots;
168   }
169   ArrayRef<SUnit*> getBottomRoots() const {
170     return BotRoots;
171   }
172 };
173 
174 class GCNIterativeScheduler::OverrideLegacyStrategy {
175   GCNIterativeScheduler &Sch;
176   Region &Rgn;
177   std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
178   GCNRegPressure SaveMaxRP;
179 
180 public:
181   OverrideLegacyStrategy(Region &R,
182                          MachineSchedStrategy &OverrideStrategy,
183                          GCNIterativeScheduler &_Sch)
184     : Sch(_Sch)
185     , Rgn(R)
186     , SaveSchedImpl(std::move(_Sch.SchedImpl))
187     , SaveMaxRP(R.MaxPressure) {
188     Sch.SchedImpl.reset(&OverrideStrategy);
189     auto BB = R.Begin->getParent();
190     Sch.BaseClass::startBlock(BB);
191     Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
192   }
193 
194   ~OverrideLegacyStrategy() {
195     Sch.BaseClass::exitRegion();
196     Sch.BaseClass::finishBlock();
197     Sch.SchedImpl.release();
198     Sch.SchedImpl = std::move(SaveSchedImpl);
199   }
200 
201   void schedule() {
202     assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
203     DEBUG(dbgs() << "\nScheduling ";
204       printRegion(dbgs(), Rgn.Begin, Rgn.End, Sch.LIS, 2));
205     Sch.BaseClass::schedule();
206 
207     // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
208     Sch.RegionEnd = Rgn.End;
209     //assert(Rgn.End == Sch.RegionEnd);
210     Rgn.Begin = Sch.RegionBegin;
211     Rgn.MaxPressure.clear();
212   }
213 
214   void restoreOrder() {
215     assert(Sch.RegionBegin == Rgn.Begin && Sch.RegionEnd == Rgn.End);
216     // DAG SUnits are stored using original region's order
217     // so just use SUnits as the restoring schedule
218     Sch.scheduleRegion(Rgn, Sch.SUnits, SaveMaxRP);
219   }
220 };
221 
222 namespace {
223 
224 // just a stub to make base class happy
225 class SchedStrategyStub : public MachineSchedStrategy {
226 public:
227   bool shouldTrackPressure() const override { return false; }
228   bool shouldTrackLaneMasks() const override { return false; }
229   void initialize(ScheduleDAGMI *DAG) override {}
230   SUnit *pickNode(bool &IsTopNode) override { return nullptr; }
231   void schedNode(SUnit *SU, bool IsTopNode) override {}
232   void releaseTopNode(SUnit *SU) override {}
233   void releaseBottomNode(SUnit *SU) override {}
234 };
235 
236 } // end anonymous namespace
237 
238 GCNIterativeScheduler::GCNIterativeScheduler(MachineSchedContext *C,
239                                              StrategyKind S)
240   : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
241   , Context(C)
242   , Strategy(S)
243   , UPTracker(*LIS) {
244 }
245 
246 // returns max pressure for a region
247 GCNRegPressure
248 GCNIterativeScheduler::getRegionPressure(MachineBasicBlock::iterator Begin,
249                                          MachineBasicBlock::iterator End)
250   const {
251   // For the purpose of pressure tracking bottom inst of the region should
252   // be also processed. End is either BB end, BB terminator inst or sched
253   // boundary inst.
254   auto const BBEnd = Begin->getParent()->end();
255   auto const BottomMI = End == BBEnd ? std::prev(End) : End;
256 
257   // scheduleRegions walks bottom to top, so its likely we just get next
258   // instruction to track
259   auto AfterBottomMI = std::next(BottomMI);
260   if (AfterBottomMI == BBEnd ||
261       &*AfterBottomMI != UPTracker.getLastTrackedMI()) {
262     UPTracker.reset(*BottomMI);
263   } else {
264     assert(UPTracker.isValid());
265   }
266 
267   for (auto I = BottomMI; I != Begin; --I)
268     UPTracker.recede(*I);
269 
270   UPTracker.recede(*Begin);
271 
272   assert(UPTracker.isValid() ||
273          (dbgs() << "Tracked region ",
274           printRegion(dbgs(), Begin, End, LIS), false));
275   return UPTracker.moveMaxPressure();
276 }
277 
278 // returns max pressure for a tentative schedule
279 template <typename Range> GCNRegPressure
280 GCNIterativeScheduler::getSchedulePressure(const Region &R,
281                                            Range &&Schedule) const {
282   auto const BBEnd = R.Begin->getParent()->end();
283   GCNUpwardRPTracker RPTracker(*LIS);
284   if (R.End != BBEnd) {
285     // R.End points to the boundary instruction but the
286     // schedule doesn't include it
287     RPTracker.reset(*R.End);
288     RPTracker.recede(*R.End);
289   } else {
290     // R.End doesn't point to the boundary instruction
291     RPTracker.reset(*std::prev(BBEnd));
292   }
293   for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
294     RPTracker.recede(*getMachineInstr(*--I));
295   }
296   return RPTracker.moveMaxPressure();
297 }
298 
299 void GCNIterativeScheduler::enterRegion(MachineBasicBlock *BB, // overriden
300                                         MachineBasicBlock::iterator Begin,
301                                         MachineBasicBlock::iterator End,
302                                         unsigned NumRegionInstrs) {
303   BaseClass::enterRegion(BB, Begin, End, NumRegionInstrs);
304   if (NumRegionInstrs > 2) {
305     Regions.push_back(
306       new (Alloc.Allocate())
307       Region { Begin, End, NumRegionInstrs,
308                getRegionPressure(Begin, End), nullptr });
309   }
310 }
311 
312 void GCNIterativeScheduler::schedule() { // overriden
313   // do nothing
314   DEBUG(
315     printLivenessInfo(dbgs(), RegionBegin, RegionEnd, LIS);
316     if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
317       dbgs() << "Max RP: ";
318       Regions.back()->MaxPressure.print(dbgs(), &MF.getSubtarget<SISubtarget>());
319     }
320     dbgs() << '\n';
321   );
322 }
323 
324 void GCNIterativeScheduler::finalizeSchedule() { // overriden
325   if (Regions.empty())
326     return;
327   switch (Strategy) {
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;
332   }
333 }
334 
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);
341 
342   if (FirstDbgValue)
343     Res.push_back(FirstDbgValue);
344 
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();
350     });
351     if (D != DbgE)
352       Res.push_back(D->first);
353   }
354   return Res;
355 }
356 
357 void GCNIterativeScheduler::setBestSchedule(Region &R,
358                                             ScheduleRef Schedule,
359                                             const GCNRegPressure &MaxRP) {
360   R.BestSchedule.reset(
361     new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
362 }
363 
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();
368 }
369 
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);
377 #ifndef NDEBUG
378   const auto SchedMaxRP = getSchedulePressure(R, Schedule);
379 #endif
380   auto BB = R.Begin->getParent();
381   auto Top = R.Begin;
382   for (const auto &I : Schedule) {
383     auto MI = getMachineInstr(I);
384     if (MI != &*Top) {
385       BB->remove(MI);
386       BB->insert(Top, MI);
387       if (!MI->isDebugInstr())
388         LIS->handleMove(*MI, true);
389     }
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);
395 
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);
402     }
403     Top = std::next(MI->getIterator());
404   }
405   RegionBegin = getMachineInstr(Schedule.front());
406 
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) {
410     placeDebugValues();
411     // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
412     //assert(R.End == RegionEnd);
413     RegionEnd = R.End;
414   }
415 
416   R.Begin = RegionBegin;
417   R.MaxPressure = MaxRP;
418 
419 #ifndef NDEBUG
420   const auto RegionMaxRP = getRegionPressure(R);
421   const auto &ST = MF.getSubtarget<SISubtarget>();
422 #endif
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),
431       false));
432 }
433 
434 // Sort recorded regions by pressure - highest at the front
435 void GCNIterativeScheduler::sortRegionsByPressure(unsigned TargetOcc) {
436   const auto &ST = MF.getSubtarget<SISubtarget>();
437   llvm::sort(Regions.begin(), Regions.end(),
438     [&ST, TargetOcc](const Region *R1, const Region *R2) {
439     return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
440   });
441 }
442 
443 ///////////////////////////////////////////////////////////////////////////////
444 // Legacy MaxOccupancy Strategy
445 
446 // Tries to increase occupancy applying minreg scheduler for a sequence of
447 // most demanding regions. Obtained schedules are saved as BestSchedule for a
448 // region.
449 // TargetOcc is the best achievable occupancy for a kernel.
450 // Returns better occupancy on success or current occupancy on fail.
451 // BestSchedules aren't deleted on fail.
452 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
453   // TODO: assert Regions are sorted descending by pressure
454   const auto &ST = MF.getSubtarget<SISubtarget>();
455   const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
456   DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
457                << ", current = " << Occ << '\n');
458 
459   auto NewOcc = TargetOcc;
460   for (auto R : Regions) {
461     if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
462       break;
463 
464     DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
465           printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
466 
467     BuildDAG DAG(*R, *this);
468     const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
469     const auto MaxRP = getSchedulePressure(*R, MinSchedule);
470     DEBUG(dbgs() << "Occupancy improvement attempt:\n";
471           printSchedRP(dbgs(), R->MaxPressure, MaxRP));
472 
473     NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
474     if (NewOcc <= Occ)
475       break;
476 
477     setBestSchedule(*R, MinSchedule, MaxRP);
478   }
479   DEBUG(dbgs() << "New occupancy = " << NewOcc
480                << ", prev occupancy = " << Occ << '\n');
481   return std::max(NewOcc, Occ);
482 }
483 
484 void GCNIterativeScheduler::scheduleLegacyMaxOccupancy(
485   bool TryMaximizeOccupancy) {
486   const auto &ST = MF.getSubtarget<SISubtarget>();
487   auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
488 
489   sortRegionsByPressure(TgtOcc);
490   auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
491 
492   if (TryMaximizeOccupancy && Occ < TgtOcc)
493     Occ = tryMaximizeOccupancy(TgtOcc);
494 
495   // This is really weird but for some magic scheduling regions twice
496   // gives performance improvement
497   const int NumPasses = Occ < TgtOcc ? 2 : 1;
498 
499   TgtOcc = std::min(Occ, TgtOcc);
500   DEBUG(dbgs() << "Scheduling using default scheduler, "
501                   "target occupancy = " << TgtOcc << '\n');
502   GCNMaxOccupancySchedStrategy LStrgy(Context);
503 
504   for (int I = 0; I < NumPasses; ++I) {
505     // running first pass with TargetOccupancy = 0 mimics previous scheduling
506     // approach and is a performance magic
507     LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
508     for (auto R : Regions) {
509       OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
510 
511       Ovr.schedule();
512       const auto RP = getRegionPressure(*R);
513       DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
514 
515       if (RP.getOccupancy(ST) < TgtOcc) {
516         DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
517         if (R->BestSchedule.get() &&
518             R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
519           DEBUG(dbgs() << ", scheduling minimal register\n");
520           scheduleBest(*R);
521         } else {
522           DEBUG(dbgs() << ", restoring\n");
523           Ovr.restoreOrder();
524           assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
525         }
526       }
527     }
528   }
529 }
530 
531 ///////////////////////////////////////////////////////////////////////////////
532 // Minimal Register Strategy
533 
534 void GCNIterativeScheduler::scheduleMinReg(bool force) {
535   const auto &ST = MF.getSubtarget<SISubtarget>();
536   const auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
537   sortRegionsByPressure(TgtOcc);
538 
539   auto MaxPressure = Regions.front()->MaxPressure;
540   for (auto R : Regions) {
541     if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
542       break;
543 
544     BuildDAG DAG(*R, *this);
545     const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
546 
547     const auto RP = getSchedulePressure(*R, MinSchedule);
548     DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
549       dbgs() << "\nWarning: Pressure becomes worse after minreg!";
550       printSchedRP(dbgs(), R->MaxPressure, RP);
551     });
552 
553     if (!force && MaxPressure.less(ST, RP, TgtOcc))
554       break;
555 
556     scheduleRegion(*R, MinSchedule, RP);
557     DEBUG(printSchedResult(dbgs(), R, RP));
558 
559     MaxPressure = RP;
560   }
561 }
562 
563 ///////////////////////////////////////////////////////////////////////////////
564 // ILP scheduler port
565 
566 void GCNIterativeScheduler::scheduleILP(
567   bool TryMaximizeOccupancy) {
568   const auto &ST = MF.getSubtarget<SISubtarget>();
569   auto TgtOcc = std::min(ST.getOccupancyWithLocalMemSize(MF),
570                          ST.getWavesPerEU(MF.getFunction()).second);
571 
572   sortRegionsByPressure(TgtOcc);
573   auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
574 
575   if (TryMaximizeOccupancy && Occ < TgtOcc)
576     Occ = tryMaximizeOccupancy(TgtOcc);
577 
578   TgtOcc = std::min(Occ, TgtOcc);
579   DEBUG(dbgs() << "Scheduling using default scheduler, "
580     "target occupancy = " << TgtOcc << '\n');
581 
582   for (auto R : Regions) {
583     BuildDAG DAG(*R, *this);
584     const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
585 
586     const auto RP = getSchedulePressure(*R, ILPSchedule);
587     DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
588 
589     if (RP.getOccupancy(ST) < TgtOcc) {
590       DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
591       if (R->BestSchedule.get() &&
592         R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
593         DEBUG(dbgs() << ", scheduling minimal register\n");
594         scheduleBest(*R);
595       }
596     } else {
597       scheduleRegion(*R, ILPSchedule, RP);
598       DEBUG(printSchedResult(dbgs(), R, RP));
599     }
600   }
601 }
602