lib/Target/AMDGPU/GCNIterativeScheduler.cpp

   1 //===- GCNIterativeScheduler.cpp ------------------------------------------===//
   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 #include "GCNIterativeScheduler.h"
  10 #include "AMDGPUSubtarget.h"
  11 #include "GCNRegPressure.h"
  12 #include "GCNSchedStrategy.h"
  13 #include "SIMachineFunctionInfo.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<GCNSubtarget>();
 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<GCNSubtarget>();
 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     LLVM_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, std::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   LLVM_DEBUG(printLivenessInfo(dbgs(), RegionBegin, RegionEnd, LIS);
 315              if (!Regions.empty() && Regions.back()->Begin == RegionBegin) {
 316                dbgs() << "Max RP: ";
 317                Regions.back()->MaxPressure.print(
 318                    dbgs(), &MF.getSubtarget<GCNSubtarget>());
 319              } dbgs()
 320              << '\n';);
 321 }
 322
 323 void GCNIterativeScheduler::finalizeSchedule() { // overriden
 324   if (Regions.empty())
 325     return;
 326   switch (Strategy) {
 327   case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
 328   case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
 329   case SCHEDULE_LEGACYMAXOCCUPANCY: scheduleLegacyMaxOccupancy(); break;
 330   case SCHEDULE_ILP: scheduleILP(false); break;
 331   }
 332 }
 333
 334 // Detach schedule from SUnits and interleave it with debug values.
 335 // Returned schedule becomes independent of DAG state.
 336 std::vector<MachineInstr*>
 337 GCNIterativeScheduler::detachSchedule(ScheduleRef Schedule) const {
 338   std::vector<MachineInstr*> Res;
 339   Res.reserve(Schedule.size() * 2);
 340
 341   if (FirstDbgValue)
 342     Res.push_back(FirstDbgValue);
 343
 344   const auto DbgB = DbgValues.begin(), DbgE = DbgValues.end();
 345   for (auto SU : Schedule) {
 346     Res.push_back(SU->getInstr());
 347     const auto &D = std::find_if(DbgB, DbgE, [SU](decltype(*DbgB) &P) {
 348       return P.second == SU->getInstr();
 349     });
 350     if (D != DbgE)
 351       Res.push_back(D->first);
 352   }
 353   return Res;
 354 }
 355
 356 void GCNIterativeScheduler::setBestSchedule(Region &R,
 357                                             ScheduleRef Schedule,
 358                                             const GCNRegPressure &MaxRP) {
 359   R.BestSchedule.reset(
 360     new TentativeSchedule{ detachSchedule(Schedule), MaxRP });
 361 }
 362
 363 void GCNIterativeScheduler::scheduleBest(Region &R) {
 364   assert(R.BestSchedule.get() && "No schedule specified");
 365   scheduleRegion(R, R.BestSchedule->Schedule, R.BestSchedule->MaxPressure);
 366   R.BestSchedule.reset();
 367 }
 368
 369 // minimal required region scheduler, works for ranges of SUnits*,
 370 // SUnits or MachineIntrs*
 371 template <typename Range>
 372 void GCNIterativeScheduler::scheduleRegion(Region &R, Range &&Schedule,
 373                                            const GCNRegPressure &MaxRP) {
 374   assert(RegionBegin == R.Begin && RegionEnd == R.End);
 375   assert(LIS != nullptr);
 376 #ifndef NDEBUG
 377   const auto SchedMaxRP = getSchedulePressure(R, Schedule);
 378 #endif
 379   auto BB = R.Begin->getParent();
 380   auto Top = R.Begin;
 381   for (const auto &I : Schedule) {
 382     auto MI = getMachineInstr(I);
 383     if (MI != &*Top) {
 384       BB->remove(MI);
 385       BB->insert(Top, MI);
 386       if (!MI->isDebugInstr())
 387         LIS->handleMove(*MI, true);
 388     }
 389     if (!MI->isDebugInstr()) {
 390       // Reset read - undef flags and update them later.
 391       for (auto &Op : MI->operands())
 392         if (Op.isReg() && Op.isDef())
 393           Op.setIsUndef(false);
 394
 395       RegisterOperands RegOpers;
 396       RegOpers.collect(*MI, *TRI, MRI, /*ShouldTrackLaneMasks*/true,
 397                                        /*IgnoreDead*/false);
 398       // Adjust liveness and add missing dead+read-undef flags.
 399       auto SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
 400       RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
 401     }
 402     Top = std::next(MI->getIterator());
 403   }
 404   RegionBegin = getMachineInstr(Schedule.front());
 405
 406   // Schedule consisting of MachineInstr* is considered 'detached'
 407   // and already interleaved with debug values
 408   if (!std::is_same<decltype(*Schedule.begin()), MachineInstr*>::value) {
 409     placeDebugValues();
 410     // Unfortunatelly placeDebugValues incorrectly modifies RegionEnd, restore
 411     //assert(R.End == RegionEnd);
 412     RegionEnd = R.End;
 413   }
 414
 415   R.Begin = RegionBegin;
 416   R.MaxPressure = MaxRP;
 417
 418 #ifndef NDEBUG
 419   const auto RegionMaxRP = getRegionPressure(R);
 420   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 421 #endif
 422   assert((SchedMaxRP == RegionMaxRP && (MaxRP.empty() || SchedMaxRP == MaxRP))
 423   || (dbgs() << "Max RP mismatch!!!\n"
 424                 "RP for schedule (calculated): ",
 425       SchedMaxRP.print(dbgs(), &ST),
 426       dbgs() << "RP for schedule (reported): ",
 427       MaxRP.print(dbgs(), &ST),
 428       dbgs() << "RP after scheduling: ",
 429       RegionMaxRP.print(dbgs(), &ST),
 430       false));
 431 }
 432
 433 // Sort recorded regions by pressure - highest at the front
 434 void GCNIterativeScheduler::sortRegionsByPressure(unsigned TargetOcc) {
 435   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 436   llvm::sort(Regions, [&ST, TargetOcc](const Region *R1, const Region *R2) {
 437     return R2->MaxPressure.less(ST, R1->MaxPressure, TargetOcc);
 438   });
 439 }
 440
 441 ///////////////////////////////////////////////////////////////////////////////
 442 // Legacy MaxOccupancy Strategy
 443
 444 // Tries to increase occupancy applying minreg scheduler for a sequence of
 445 // most demanding regions. Obtained schedules are saved as BestSchedule for a
 446 // region.
 447 // TargetOcc is the best achievable occupancy for a kernel.
 448 // Returns better occupancy on success or current occupancy on fail.
 449 // BestSchedules aren't deleted on fail.
 450 unsigned GCNIterativeScheduler::tryMaximizeOccupancy(unsigned TargetOcc) {
 451   // TODO: assert Regions are sorted descending by pressure
 452   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 453   const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 454   LLVM_DEBUG(dbgs() << "Trying to improve occupancy, target = " << TargetOcc
 455                     << ", current = " << Occ << '\n');
 456
 457   auto NewOcc = TargetOcc;
 458   for (auto R : Regions) {
 459     if (R->MaxPressure.getOccupancy(ST) >= NewOcc)
 460       break;
 461
 462     LLVM_DEBUG(printRegion(dbgs(), R->Begin, R->End, LIS, 3);
 463                printLivenessInfo(dbgs(), R->Begin, R->End, LIS));
 464
 465     BuildDAG DAG(*R, *this);
 466     const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
 467     const auto MaxRP = getSchedulePressure(*R, MinSchedule);
 468     LLVM_DEBUG(dbgs() << "Occupancy improvement attempt:\n";
 469                printSchedRP(dbgs(), R->MaxPressure, MaxRP));
 470
 471     NewOcc = std::min(NewOcc, MaxRP.getOccupancy(ST));
 472     if (NewOcc <= Occ)
 473       break;
 474
 475     setBestSchedule(*R, MinSchedule, MaxRP);
 476   }
 477   LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
 478                     << ", prev occupancy = " << Occ << '\n');
 479   if (NewOcc > Occ) {
 480     SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 481     MFI->increaseOccupancy(MF, NewOcc);
 482   }
 483
 484   return std::max(NewOcc, Occ);
 485 }
 486
 487 void GCNIterativeScheduler::scheduleLegacyMaxOccupancy(
 488   bool TryMaximizeOccupancy) {
 489   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 490   SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 491   auto TgtOcc = MFI->getMinAllowedOccupancy();
 492
 493   sortRegionsByPressure(TgtOcc);
 494   auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 495
 496   if (TryMaximizeOccupancy && Occ < TgtOcc)
 497     Occ = tryMaximizeOccupancy(TgtOcc);
 498
 499   // This is really weird but for some magic scheduling regions twice
 500   // gives performance improvement
 501   const int NumPasses = Occ < TgtOcc ? 2 : 1;
 502
 503   TgtOcc = std::min(Occ, TgtOcc);
 504   LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
 505                        "target occupancy = "
 506                     << TgtOcc << '\n');
 507   GCNMaxOccupancySchedStrategy LStrgy(Context);
 508   unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
 509
 510   for (int I = 0; I < NumPasses; ++I) {
 511     // running first pass with TargetOccupancy = 0 mimics previous scheduling
 512     // approach and is a performance magic
 513     LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
 514     for (auto R : Regions) {
 515       OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
 516
 517       Ovr.schedule();
 518       const auto RP = getRegionPressure(*R);
 519       LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
 520
 521       if (RP.getOccupancy(ST) < TgtOcc) {
 522         LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
 523         if (R->BestSchedule.get() &&
 524             R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
 525           LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
 526           scheduleBest(*R);
 527         } else {
 528           LLVM_DEBUG(dbgs() << ", restoring\n");
 529           Ovr.restoreOrder();
 530           assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
 531         }
 532       }
 533       FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
 534     }
 535   }
 536   MFI->limitOccupancy(FinalOccupancy);
 537 }
 538
 539 ///////////////////////////////////////////////////////////////////////////////
 540 // Minimal Register Strategy
 541
 542 void GCNIterativeScheduler::scheduleMinReg(bool force) {
 543   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 544   const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 545   const auto TgtOcc = MFI->getOccupancy();
 546   sortRegionsByPressure(TgtOcc);
 547
 548   auto MaxPressure = Regions.front()->MaxPressure;
 549   for (auto R : Regions) {
 550     if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
 551       break;
 552
 553     BuildDAG DAG(*R, *this);
 554     const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
 555
 556     const auto RP = getSchedulePressure(*R, MinSchedule);
 557     LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
 558       dbgs() << "\nWarning: Pressure becomes worse after minreg!";
 559       printSchedRP(dbgs(), R->MaxPressure, RP);
 560     });
 561
 562     if (!force && MaxPressure.less(ST, RP, TgtOcc))
 563       break;
 564
 565     scheduleRegion(*R, MinSchedule, RP);
 566     LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
 567
 568     MaxPressure = RP;
 569   }
 570 }
 571
 572 ///////////////////////////////////////////////////////////////////////////////
 573 // ILP scheduler port
 574
 575 void GCNIterativeScheduler::scheduleILP(
 576   bool TryMaximizeOccupancy) {
 577   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 578   SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 579   auto TgtOcc = MFI->getMinAllowedOccupancy();
 580
 581   sortRegionsByPressure(TgtOcc);
 582   auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 583
 584   if (TryMaximizeOccupancy && Occ < TgtOcc)
 585     Occ = tryMaximizeOccupancy(TgtOcc);
 586
 587   TgtOcc = std::min(Occ, TgtOcc);
 588   LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
 589                        "target occupancy = "
 590                     << TgtOcc << '\n');
 591
 592   unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
 593   for (auto R : Regions) {
 594     BuildDAG DAG(*R, *this);
 595     const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
 596
 597     const auto RP = getSchedulePressure(*R, ILPSchedule);
 598     LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
 599
 600     if (RP.getOccupancy(ST) < TgtOcc) {
 601       LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
 602       if (R->BestSchedule.get() &&
 603         R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
 604         LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
 605         scheduleBest(*R);
 606       }
 607     } else {
 608       scheduleRegion(*R, ILPSchedule, RP);
 609       LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
 610       FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
 611     }
 612   }
 613   MFI->limitOccupancy(FinalOccupancy);
 614 }