lib/Target/AMDGPU/GCNIterativeScheduler.cpp

   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 "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"
  27 #include <algorithm>
  28 #include <cassert>
  29 #include <iterator>
  30 #include <limits>
  31 #include <memory>
  32 #include <type_traits>
  33 #include <vector>
  34
  35 using namespace llvm;
  36
  37 #define DEBUG_TYPE "machine-scheduler"
  38
  39 namespace llvm {
  40
  41 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
  42                                               const ScheduleDAG &DAG);
  43
  44   std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
  45     const ScheduleDAG &DAG);
  46 }
  47
  48 // shim accessors for different order containers
  49 static inline MachineInstr *getMachineInstr(MachineInstr *MI) {
  50   return MI;
  51 }
  52 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
  53   return SU->getInstr();
  54 }
  55 static inline MachineInstr *getMachineInstr(const SUnit &SU) {
  56   return SU.getInstr();
  57 }
  58
  59 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  60 LLVM_DUMP_METHOD
  61 static void printRegion(raw_ostream &OS,
  62                         MachineBasicBlock::iterator Begin,
  63                         MachineBasicBlock::iterator End,
  64                         const LiveIntervals *LIS,
  65                         unsigned MaxInstNum =
  66                           std::numeric_limits<unsigned>::max()) {
  67   auto BB = Begin->getParent();
  68   OS << BB->getParent()->getName() << ":" << printMBBReference(*BB) << ' '
  69      << BB->getName() << ":\n";
  70   auto I = Begin;
  71   MaxInstNum = std::max(MaxInstNum, 1u);
  72   for (; I != End && MaxInstNum; ++I, --MaxInstNum) {
  73     if (!I->isDebugInstr() && LIS)
  74       OS << LIS->getInstructionIndex(*I);
  75     OS << '\t' << *I;
  76   }
  77   if (I != End) {
  78     OS << "\t...\n";
  79     I = std::prev(End);
  80     if (!I->isDebugInstr() && LIS)
  81       OS << LIS->getInstructionIndex(*I);
  82     OS << '\t' << *I;
  83   }
  84   if (End != BB->end()) { // print boundary inst if present
  85     OS << "----\n";
  86     if (LIS) OS << LIS->getInstructionIndex(*End) << '\t';
  87     OS << *End;
  88   }
  89 }
  90
  91 LLVM_DUMP_METHOD
  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();
  98
  99   const auto LiveIns = getLiveRegsBefore(*Begin, *LIS);
 100   OS << "LIn RP: ";
 101   getRegPressure(MRI, LiveIns).print(OS);
 102
 103   const auto BottomMI = End == BB->end() ? std::prev(End) : End;
 104   const auto LiveOuts = getLiveRegsAfter(*BottomMI, *LIS);
 105   OS << "LOt RP: ";
 106   getRegPressure(MRI, LiveOuts).print(OS);
 107 }
 108
 109 LLVM_DUMP_METHOD
 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);
 116     OS << "Max RP: ";
 117     R->MaxPressure.print(OS, &ST);
 118   }
 119 }
 120
 121 LLVM_DUMP_METHOD
 122 void GCNIterativeScheduler::printSchedResult(raw_ostream &OS,
 123                                              const Region *R,
 124                                              const GCNRegPressure &RP) const {
 125   OS << "\nAfter scheduling ";
 126   printRegion(OS, R->Begin, R->End, LIS);
 127   printSchedRP(OS, R->MaxPressure, RP);
 128   OS << '\n';
 129 }
 130
 131 LLVM_DUMP_METHOD
 132 void GCNIterativeScheduler::printSchedRP(raw_ostream &OS,
 133                                          const GCNRegPressure &Before,
 134                                          const GCNRegPressure &After) const {
 135   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 136   OS << "RP before: ";
 137   Before.print(OS, &ST);
 138   OS << "RP after:  ";
 139   After.print(OS, &ST);
 140 }
 141 #endif
 142
 143 // DAG builder helper
 144 class GCNIterativeScheduler::BuildDAG {
 145   GCNIterativeScheduler &Sch;
 146   SmallVector<SUnit *, 8> TopRoots;
 147
 148   SmallVector<SUnit*, 8> BotRoots;
 149 public:
 150   BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
 151     : Sch(_Sch) {
 152     auto BB = R.Begin->getParent();
 153     Sch.BaseClass::startBlock(BB);
 154     Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
 155
 156     Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
 157                         /*TrackLaneMask*/true);
 158     Sch.Topo.InitDAGTopologicalSorting();
 159     Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
 160   }
 161
 162   ~BuildDAG() {
 163     Sch.BaseClass::exitRegion();
 164     Sch.BaseClass::finishBlock();
 165   }
 166
 167   ArrayRef<const SUnit *> getTopRoots() const {
 168     return TopRoots;
 169   }
 170   ArrayRef<SUnit*> getBottomRoots() const {
 171     return BotRoots;
 172   }
 173 };
 174
 175 class GCNIterativeScheduler::OverrideLegacyStrategy {
 176   GCNIterativeScheduler &Sch;
 177   Region &Rgn;
 178   std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
 179   GCNRegPressure SaveMaxRP;
 180
 181 public:
 182   OverrideLegacyStrategy(Region &R,
 183                          MachineSchedStrategy &OverrideStrategy,
 184                          GCNIterativeScheduler &_Sch)
 185     : Sch(_Sch)
 186     , Rgn(R)
 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);
 193   }
 194
 195   ~OverrideLegacyStrategy() {
 196     Sch.BaseClass::exitRegion();
 197     Sch.BaseClass::finishBlock();
 198     Sch.SchedImpl.release();
 199     Sch.SchedImpl = std::move(SaveSchedImpl);
 200   }
 201
 202   void schedule() {
 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();
 207
 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();
 213   }
 214
 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);
 220   }
 221 };
 222
 223 namespace {
 224
 225 // just a stub to make base class happy
 226 class SchedStrategyStub : public MachineSchedStrategy {
 227 public:
 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 {}
 235 };
 236
 237 } // end anonymous namespace
 238
 239 GCNIterativeScheduler::GCNIterativeScheduler(MachineSchedContext *C,
 240                                              StrategyKind S)
 241   : BaseClass(C, llvm::make_unique<SchedStrategyStub>())
 242   , Context(C)
 243   , Strategy(S)
 244   , UPTracker(*LIS) {
 245 }
 246
 247 // returns max pressure for a region
 248 GCNRegPressure
 249 GCNIterativeScheduler::getRegionPressure(MachineBasicBlock::iterator Begin,
 250                                          MachineBasicBlock::iterator End)
 251   const {
 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
 254   // boundary inst.
 255   auto const BBEnd = Begin->getParent()->end();
 256   auto const BottomMI = End == BBEnd ? std::prev(End) : End;
 257
 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);
 264   } else {
 265     assert(UPTracker.isValid());
 266   }
 267
 268   for (auto I = BottomMI; I != Begin; --I)
 269     UPTracker.recede(*I);
 270
 271   UPTracker.recede(*Begin);
 272
 273   assert(UPTracker.isValid() ||
 274          (dbgs() << "Tracked region ",
 275           printRegion(dbgs(), Begin, End, LIS), false));
 276   return UPTracker.moveMaxPressure();
 277 }
 278
 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);
 290   } else {
 291     // R.End doesn't point to the boundary instruction
 292     RPTracker.reset(*std::prev(BBEnd));
 293   }
 294   for (auto I = Schedule.end(), B = Schedule.begin(); I != B;) {
 295     RPTracker.recede(*getMachineInstr(*--I));
 296   }
 297   return RPTracker.moveMaxPressure();
 298 }
 299
 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) {
 306     Regions.push_back(
 307       new (Alloc.Allocate())
 308       Region { Begin, End, NumRegionInstrs,
 309                getRegionPressure(Begin, End), nullptr });
 310   }
 311 }
 312
 313 void GCNIterativeScheduler::schedule() { // overriden
 314   // do nothing
 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>());
 320              } dbgs()
 321              << '\n';);
 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<GCNSubtarget>();
 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<GCNSubtarget>();
 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<GCNSubtarget>();
 455   const auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 456   LLVM_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     LLVM_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     LLVM_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   LLVM_DEBUG(dbgs() << "New occupancy = " << NewOcc
 480                     << ", prev occupancy = " << Occ << '\n');
 481   if (NewOcc > Occ) {
 482     SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 483     MFI->increaseOccupancy(MF, NewOcc);
 484   }
 485
 486   return std::max(NewOcc, Occ);
 487 }
 488
 489 void GCNIterativeScheduler::scheduleLegacyMaxOccupancy(
 490   bool TryMaximizeOccupancy) {
 491   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 492   SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 493   auto TgtOcc = MFI->getMinAllowedOccupancy();
 494
 495   sortRegionsByPressure(TgtOcc);
 496   auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 497
 498   if (TryMaximizeOccupancy && Occ < TgtOcc)
 499     Occ = tryMaximizeOccupancy(TgtOcc);
 500
 501   // This is really weird but for some magic scheduling regions twice
 502   // gives performance improvement
 503   const int NumPasses = Occ < TgtOcc ? 2 : 1;
 504
 505   TgtOcc = std::min(Occ, TgtOcc);
 506   LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
 507                        "target occupancy = "
 508                     << TgtOcc << '\n');
 509   GCNMaxOccupancySchedStrategy LStrgy(Context);
 510   unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
 511
 512   for (int I = 0; I < NumPasses; ++I) {
 513     // running first pass with TargetOccupancy = 0 mimics previous scheduling
 514     // approach and is a performance magic
 515     LStrgy.setTargetOccupancy(I == 0 ? 0 : TgtOcc);
 516     for (auto R : Regions) {
 517       OverrideLegacyStrategy Ovr(*R, LStrgy, *this);
 518
 519       Ovr.schedule();
 520       const auto RP = getRegionPressure(*R);
 521       LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
 522
 523       if (RP.getOccupancy(ST) < TgtOcc) {
 524         LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
 525         if (R->BestSchedule.get() &&
 526             R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
 527           LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
 528           scheduleBest(*R);
 529         } else {
 530           LLVM_DEBUG(dbgs() << ", restoring\n");
 531           Ovr.restoreOrder();
 532           assert(R->MaxPressure.getOccupancy(ST) >= TgtOcc);
 533         }
 534       }
 535       FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
 536     }
 537   }
 538   MFI->limitOccupancy(FinalOccupancy);
 539 }
 540
 541 ///////////////////////////////////////////////////////////////////////////////
 542 // Minimal Register Strategy
 543
 544 void GCNIterativeScheduler::scheduleMinReg(bool force) {
 545   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 546   const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 547   const auto TgtOcc = MFI->getOccupancy();
 548   sortRegionsByPressure(TgtOcc);
 549
 550   auto MaxPressure = Regions.front()->MaxPressure;
 551   for (auto R : Regions) {
 552     if (!force && R->MaxPressure.less(ST, MaxPressure, TgtOcc))
 553       break;
 554
 555     BuildDAG DAG(*R, *this);
 556     const auto MinSchedule = makeMinRegSchedule(DAG.getTopRoots(), *this);
 557
 558     const auto RP = getSchedulePressure(*R, MinSchedule);
 559     LLVM_DEBUG(if (R->MaxPressure.less(ST, RP, TgtOcc)) {
 560       dbgs() << "\nWarning: Pressure becomes worse after minreg!";
 561       printSchedRP(dbgs(), R->MaxPressure, RP);
 562     });
 563
 564     if (!force && MaxPressure.less(ST, RP, TgtOcc))
 565       break;
 566
 567     scheduleRegion(*R, MinSchedule, RP);
 568     LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
 569
 570     MaxPressure = RP;
 571   }
 572 }
 573
 574 ///////////////////////////////////////////////////////////////////////////////
 575 // ILP scheduler port
 576
 577 void GCNIterativeScheduler::scheduleILP(
 578   bool TryMaximizeOccupancy) {
 579   const auto &ST = MF.getSubtarget<GCNSubtarget>();
 580   SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 581   auto TgtOcc = MFI->getMinAllowedOccupancy();
 582
 583   sortRegionsByPressure(TgtOcc);
 584   auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
 585
 586   if (TryMaximizeOccupancy && Occ < TgtOcc)
 587     Occ = tryMaximizeOccupancy(TgtOcc);
 588
 589   TgtOcc = std::min(Occ, TgtOcc);
 590   LLVM_DEBUG(dbgs() << "Scheduling using default scheduler, "
 591                        "target occupancy = "
 592                     << TgtOcc << '\n');
 593
 594   unsigned FinalOccupancy = std::min(Occ, MFI->getOccupancy());
 595   for (auto R : Regions) {
 596     BuildDAG DAG(*R, *this);
 597     const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
 598
 599     const auto RP = getSchedulePressure(*R, ILPSchedule);
 600     LLVM_DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
 601
 602     if (RP.getOccupancy(ST) < TgtOcc) {
 603       LLVM_DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
 604       if (R->BestSchedule.get() &&
 605         R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
 606         LLVM_DEBUG(dbgs() << ", scheduling minimal register\n");
 607         scheduleBest(*R);
 608       }
 609     } else {
 610       scheduleRegion(*R, ILPSchedule, RP);
 611       LLVM_DEBUG(printSchedResult(dbgs(), R, RP));
 612       FinalOccupancy = std::min(FinalOccupancy, RP.getOccupancy(ST));
 613     }
 614   }
 615   MFI->limitOccupancy(FinalOccupancy);
 616 }