Home | History | Annotate | Download | only in AMDGPU 
      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 }
    617