contrib/llvm/lib/Target/AMDGPU/GCNSchedStrategy.cpp

   1 //===-- GCNSchedStrategy.cpp - GCN Scheduler Strategy ---------------------===//
   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 /// \file
  11 /// This contains a MachineSchedStrategy implementation for maximizing wave
  12 /// occupancy on GCN hardware.
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "GCNSchedStrategy.h"
  16 #include "AMDGPUSubtarget.h"
  17 #include "SIInstrInfo.h"
  18 #include "SIMachineFunctionInfo.h"
  19 #include "SIRegisterInfo.h"
  20 #include "llvm/CodeGen/RegisterClassInfo.h"
  21 #include "llvm/Support/MathExtras.h"
  22
  23 #define DEBUG_TYPE "machine-scheduler"
  24
  25 using namespace llvm;
  26
  27 GCNMaxOccupancySchedStrategy::GCNMaxOccupancySchedStrategy(
  28     const MachineSchedContext *C) :
  29     GenericScheduler(C), TargetOccupancy(0), MF(nullptr) { }
  30
  31 static unsigned getMaxWaves(unsigned SGPRs, unsigned VGPRs,
  32                             const MachineFunction &MF) {
  33
  34   const SISubtarget &ST = MF.getSubtarget<SISubtarget>();
  35   const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
  36   unsigned MinRegOccupancy = std::min(ST.getOccupancyWithNumSGPRs(SGPRs),
  37                                       ST.getOccupancyWithNumVGPRs(VGPRs));
  38   return std::min(MinRegOccupancy,
  39                   ST.getOccupancyWithLocalMemSize(MFI->getLDSSize(),
  40                                                   MF.getFunction()));
  41 }
  42
  43 void GCNMaxOccupancySchedStrategy::initialize(ScheduleDAGMI *DAG) {
  44   GenericScheduler::initialize(DAG);
  45
  46   const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo*>(TRI);
  47
  48   MF = &DAG->MF;
  49
  50   const SISubtarget &ST = MF->getSubtarget<SISubtarget>();
  51
  52   // FIXME: This is also necessary, because some passes that run after
  53   // scheduling and before regalloc increase register pressure.
  54   const int ErrorMargin = 3;
  55
  56   SGPRExcessLimit = Context->RegClassInfo
  57     ->getNumAllocatableRegs(&AMDGPU::SGPR_32RegClass) - ErrorMargin;
  58   VGPRExcessLimit = Context->RegClassInfo
  59     ->getNumAllocatableRegs(&AMDGPU::VGPR_32RegClass) - ErrorMargin;
  60   if (TargetOccupancy) {
  61     SGPRCriticalLimit = ST.getMaxNumSGPRs(TargetOccupancy, true);
  62     VGPRCriticalLimit = ST.getMaxNumVGPRs(TargetOccupancy);
  63   } else {
  64     SGPRCriticalLimit = SRI->getRegPressureSetLimit(DAG->MF,
  65                                                     SRI->getSGPRPressureSet());
  66     VGPRCriticalLimit = SRI->getRegPressureSetLimit(DAG->MF,
  67                                                     SRI->getVGPRPressureSet());
  68   }
  69
  70   SGPRCriticalLimit -= ErrorMargin;
  71   VGPRCriticalLimit -= ErrorMargin;
  72 }
  73
  74 void GCNMaxOccupancySchedStrategy::initCandidate(SchedCandidate &Cand, SUnit *SU,
  75                                      bool AtTop, const RegPressureTracker &RPTracker,
  76                                      const SIRegisterInfo *SRI,
  77                                      unsigned SGPRPressure,
  78                                      unsigned VGPRPressure) {
  79
  80   Cand.SU = SU;
  81   Cand.AtTop = AtTop;
  82
  83   // getDownwardPressure() and getUpwardPressure() make temporary changes to
  84   // the the tracker, so we need to pass those function a non-const copy.
  85   RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
  86
  87   std::vector<unsigned> Pressure;
  88   std::vector<unsigned> MaxPressure;
  89
  90   if (AtTop)
  91     TempTracker.getDownwardPressure(SU->getInstr(), Pressure, MaxPressure);
  92   else {
  93     // FIXME: I think for bottom up scheduling, the register pressure is cached
  94     // and can be retrieved by DAG->getPressureDif(SU).
  95     TempTracker.getUpwardPressure(SU->getInstr(), Pressure, MaxPressure);
  96   }
  97
  98   unsigned NewSGPRPressure = Pressure[SRI->getSGPRPressureSet()];
  99   unsigned NewVGPRPressure = Pressure[SRI->getVGPRPressureSet()];
 100
 101   // If two instructions increase the pressure of different register sets
 102   // by the same amount, the generic scheduler will prefer to schedule the
 103   // instruction that increases the set with the least amount of registers,
 104   // which in our case would be SGPRs.  This is rarely what we want, so
 105   // when we report excess/critical register pressure, we do it either
 106   // only for VGPRs or only for SGPRs.
 107
 108   // FIXME: Better heuristics to determine whether to prefer SGPRs or VGPRs.
 109   const unsigned MaxVGPRPressureInc = 16;
 110   bool ShouldTrackVGPRs = VGPRPressure + MaxVGPRPressureInc >= VGPRExcessLimit;
 111   bool ShouldTrackSGPRs = !ShouldTrackVGPRs && SGPRPressure >= SGPRExcessLimit;
 112
 113
 114   // FIXME: We have to enter REG-EXCESS before we reach the actual threshold
 115   // to increase the likelihood we don't go over the limits.  We should improve
 116   // the analysis to look through dependencies to find the path with the least
 117   // register pressure.
 118
 119   // We only need to update the RPDelata for instructions that increase
 120   // register pressure.  Instructions that decrease or keep reg pressure
 121   // the same will be marked as RegExcess in tryCandidate() when they
 122   // are compared with instructions that increase the register pressure.
 123   if (ShouldTrackVGPRs && NewVGPRPressure >= VGPRExcessLimit) {
 124     Cand.RPDelta.Excess = PressureChange(SRI->getVGPRPressureSet());
 125     Cand.RPDelta.Excess.setUnitInc(NewVGPRPressure - VGPRExcessLimit);
 126   }
 127
 128   if (ShouldTrackSGPRs && NewSGPRPressure >= SGPRExcessLimit) {
 129     Cand.RPDelta.Excess = PressureChange(SRI->getSGPRPressureSet());
 130     Cand.RPDelta.Excess.setUnitInc(NewSGPRPressure - SGPRExcessLimit);
 131   }
 132
 133   // Register pressure is considered 'CRITICAL' if it is approaching a value
 134   // that would reduce the wave occupancy for the execution unit.  When
 135   // register pressure is 'CRITICAL', increading SGPR and VGPR pressure both
 136   // has the same cost, so we don't need to prefer one over the other.
 137
 138   int SGPRDelta = NewSGPRPressure - SGPRCriticalLimit;
 139   int VGPRDelta = NewVGPRPressure - VGPRCriticalLimit;
 140
 141   if (SGPRDelta >= 0 || VGPRDelta >= 0) {
 142     if (SGPRDelta > VGPRDelta) {
 143       Cand.RPDelta.CriticalMax = PressureChange(SRI->getSGPRPressureSet());
 144       Cand.RPDelta.CriticalMax.setUnitInc(SGPRDelta);
 145     } else {
 146       Cand.RPDelta.CriticalMax = PressureChange(SRI->getVGPRPressureSet());
 147       Cand.RPDelta.CriticalMax.setUnitInc(VGPRDelta);
 148     }
 149   }
 150 }
 151
 152 // This function is mostly cut and pasted from
 153 // GenericScheduler::pickNodeFromQueue()
 154 void GCNMaxOccupancySchedStrategy::pickNodeFromQueue(SchedBoundary &Zone,
 155                                          const CandPolicy &ZonePolicy,
 156                                          const RegPressureTracker &RPTracker,
 157                                          SchedCandidate &Cand) {
 158   const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo*>(TRI);
 159   ArrayRef<unsigned> Pressure = RPTracker.getRegSetPressureAtPos();
 160   unsigned SGPRPressure = Pressure[SRI->getSGPRPressureSet()];
 161   unsigned VGPRPressure = Pressure[SRI->getVGPRPressureSet()];
 162   ReadyQueue &Q = Zone.Available;
 163   for (SUnit *SU : Q) {
 164
 165     SchedCandidate TryCand(ZonePolicy);
 166     initCandidate(TryCand, SU, Zone.isTop(), RPTracker, SRI,
 167                   SGPRPressure, VGPRPressure);
 168     // Pass SchedBoundary only when comparing nodes from the same boundary.
 169     SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
 170     GenericScheduler::tryCandidate(Cand, TryCand, ZoneArg);
 171     if (TryCand.Reason != NoCand) {
 172       // Initialize resource delta if needed in case future heuristics query it.
 173       if (TryCand.ResDelta == SchedResourceDelta())
 174         TryCand.initResourceDelta(Zone.DAG, SchedModel);
 175       Cand.setBest(TryCand);
 176     }
 177   }
 178 }
 179
 180 // This function is mostly cut and pasted from
 181 // GenericScheduler::pickNodeBidirectional()
 182 SUnit *GCNMaxOccupancySchedStrategy::pickNodeBidirectional(bool &IsTopNode) {
 183   // Schedule as far as possible in the direction of no choice. This is most
 184   // efficient, but also provides the best heuristics for CriticalPSets.
 185   if (SUnit *SU = Bot.pickOnlyChoice()) {
 186     IsTopNode = false;
 187     return SU;
 188   }
 189   if (SUnit *SU = Top.pickOnlyChoice()) {
 190     IsTopNode = true;
 191     return SU;
 192   }
 193   // Set the bottom-up policy based on the state of the current bottom zone and
 194   // the instructions outside the zone, including the top zone.
 195   CandPolicy BotPolicy;
 196   setPolicy(BotPolicy, /*IsPostRA=*/false, Bot, &Top);
 197   // Set the top-down policy based on the state of the current top zone and
 198   // the instructions outside the zone, including the bottom zone.
 199   CandPolicy TopPolicy;
 200   setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot);
 201
 202   // See if BotCand is still valid (because we previously scheduled from Top).
 203   DEBUG(dbgs() << "Picking from Bot:\n");
 204   if (!BotCand.isValid() || BotCand.SU->isScheduled ||
 205       BotCand.Policy != BotPolicy) {
 206     BotCand.reset(CandPolicy());
 207     pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);
 208     assert(BotCand.Reason != NoCand && "failed to find the first candidate");
 209   } else {
 210     DEBUG(traceCandidate(BotCand));
 211   }
 212
 213   // Check if the top Q has a better candidate.
 214   DEBUG(dbgs() << "Picking from Top:\n");
 215   if (!TopCand.isValid() || TopCand.SU->isScheduled ||
 216       TopCand.Policy != TopPolicy) {
 217     TopCand.reset(CandPolicy());
 218     pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);
 219     assert(TopCand.Reason != NoCand && "failed to find the first candidate");
 220   } else {
 221     DEBUG(traceCandidate(TopCand));
 222   }
 223
 224   // Pick best from BotCand and TopCand.
 225   DEBUG(
 226     dbgs() << "Top Cand: ";
 227     traceCandidate(TopCand);
 228     dbgs() << "Bot Cand: ";
 229     traceCandidate(BotCand);
 230   );
 231   SchedCandidate Cand;
 232   if (TopCand.Reason == BotCand.Reason) {
 233     Cand = BotCand;
 234     GenericSchedulerBase::CandReason TopReason = TopCand.Reason;
 235     TopCand.Reason = NoCand;
 236     GenericScheduler::tryCandidate(Cand, TopCand, nullptr);
 237     if (TopCand.Reason != NoCand) {
 238       Cand.setBest(TopCand);
 239     } else {
 240       TopCand.Reason = TopReason;
 241     }
 242   } else {
 243     if (TopCand.Reason == RegExcess && TopCand.RPDelta.Excess.getUnitInc() <= 0) {
 244       Cand = TopCand;
 245     } else if (BotCand.Reason == RegExcess && BotCand.RPDelta.Excess.getUnitInc() <= 0) {
 246       Cand = BotCand;
 247     } else if (TopCand.Reason == RegCritical && TopCand.RPDelta.CriticalMax.getUnitInc() <= 0) {
 248       Cand = TopCand;
 249     } else if (BotCand.Reason == RegCritical && BotCand.RPDelta.CriticalMax.getUnitInc() <= 0) {
 250       Cand = BotCand;
 251     } else {
 252       if (BotCand.Reason > TopCand.Reason) {
 253         Cand = TopCand;
 254       } else {
 255         Cand = BotCand;
 256       }
 257     }
 258   }
 259   DEBUG(
 260     dbgs() << "Picking: ";
 261     traceCandidate(Cand);
 262   );
 263
 264   IsTopNode = Cand.AtTop;
 265   return Cand.SU;
 266 }
 267
 268 // This function is mostly cut and pasted from
 269 // GenericScheduler::pickNode()
 270 SUnit *GCNMaxOccupancySchedStrategy::pickNode(bool &IsTopNode) {
 271   if (DAG->top() == DAG->bottom()) {
 272     assert(Top.Available.empty() && Top.Pending.empty() &&
 273            Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
 274     return nullptr;
 275   }
 276   SUnit *SU;
 277   do {
 278     if (RegionPolicy.OnlyTopDown) {
 279       SU = Top.pickOnlyChoice();
 280       if (!SU) {
 281         CandPolicy NoPolicy;
 282         TopCand.reset(NoPolicy);
 283         pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);
 284         assert(TopCand.Reason != NoCand && "failed to find a candidate");
 285         SU = TopCand.SU;
 286       }
 287       IsTopNode = true;
 288     } else if (RegionPolicy.OnlyBottomUp) {
 289       SU = Bot.pickOnlyChoice();
 290       if (!SU) {
 291         CandPolicy NoPolicy;
 292         BotCand.reset(NoPolicy);
 293         pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);
 294         assert(BotCand.Reason != NoCand && "failed to find a candidate");
 295         SU = BotCand.SU;
 296       }
 297       IsTopNode = false;
 298     } else {
 299       SU = pickNodeBidirectional(IsTopNode);
 300     }
 301   } while (SU->isScheduled);
 302
 303   if (SU->isTopReady())
 304     Top.removeReady(SU);
 305   if (SU->isBottomReady())
 306     Bot.removeReady(SU);
 307
 308   DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr());
 309   return SU;
 310 }
 311
 312 GCNScheduleDAGMILive::GCNScheduleDAGMILive(MachineSchedContext *C,
 313                         std::unique_ptr<MachineSchedStrategy> S) :
 314   ScheduleDAGMILive(C, std::move(S)),
 315   ST(MF.getSubtarget<SISubtarget>()),
 316   MFI(*MF.getInfo<SIMachineFunctionInfo>()),
 317   StartingOccupancy(ST.getOccupancyWithLocalMemSize(MFI.getLDSSize(),
 318                                                     MF.getFunction())),
 319   MinOccupancy(StartingOccupancy), Stage(0), RegionIdx(0) {
 320
 321   DEBUG(dbgs() << "Starting occupancy is " << StartingOccupancy << ".\n");
 322 }
 323
 324 void GCNScheduleDAGMILive::schedule() {
 325   if (Stage == 0) {
 326     // Just record regions at the first pass.
 327     Regions.push_back(std::make_pair(RegionBegin, RegionEnd));
 328     return;
 329   }
 330
 331   std::vector<MachineInstr*> Unsched;
 332   Unsched.reserve(NumRegionInstrs);
 333   for (auto &I : *this) {
 334     Unsched.push_back(&I);
 335   }
 336
 337   GCNRegPressure PressureBefore;
 338   if (LIS) {
 339     PressureBefore = Pressure[RegionIdx];
 340
 341     DEBUG(dbgs() << "Pressure before scheduling:\nRegion live-ins:";
 342           GCNRPTracker::printLiveRegs(dbgs(), LiveIns[RegionIdx], MRI);
 343           dbgs() << "Region live-in pressure:  ";
 344           llvm::getRegPressure(MRI, LiveIns[RegionIdx]).print(dbgs());
 345           dbgs() << "Region register pressure: ";
 346           PressureBefore.print(dbgs()));
 347   }
 348
 349   ScheduleDAGMILive::schedule();
 350   Regions[RegionIdx] = std::make_pair(RegionBegin, RegionEnd);
 351
 352   if (!LIS)
 353     return;
 354
 355   // Check the results of scheduling.
 356   GCNMaxOccupancySchedStrategy &S = (GCNMaxOccupancySchedStrategy&)*SchedImpl;
 357   auto PressureAfter = getRealRegPressure();
 358
 359   DEBUG(dbgs() << "Pressure after scheduling: "; PressureAfter.print(dbgs()));
 360
 361   if (PressureAfter.getSGPRNum() <= S.SGPRCriticalLimit &&
 362       PressureAfter.getVGPRNum() <= S.VGPRCriticalLimit) {
 363     Pressure[RegionIdx] = PressureAfter;
 364     DEBUG(dbgs() << "Pressure in desired limits, done.\n");
 365     return;
 366   }
 367   unsigned WavesAfter = getMaxWaves(PressureAfter.getSGPRNum(),
 368                                     PressureAfter.getVGPRNum(), MF);
 369   unsigned WavesBefore = getMaxWaves(PressureBefore.getSGPRNum(),
 370                                      PressureBefore.getVGPRNum(), MF);
 371   DEBUG(dbgs() << "Occupancy before scheduling: " << WavesBefore <<
 372                   ", after " << WavesAfter << ".\n");
 373
 374   // We could not keep current target occupancy because of the just scheduled
 375   // region. Record new occupancy for next scheduling cycle.
 376   unsigned NewOccupancy = std::max(WavesAfter, WavesBefore);
 377   if (NewOccupancy < MinOccupancy) {
 378     MinOccupancy = NewOccupancy;
 379     DEBUG(dbgs() << "Occupancy lowered for the function to "
 380                  << MinOccupancy << ".\n");
 381   }
 382
 383   if (WavesAfter >= WavesBefore) {
 384     Pressure[RegionIdx] = PressureAfter;
 385     return;
 386   }
 387
 388   DEBUG(dbgs() << "Attempting to revert scheduling.\n");
 389   RegionEnd = RegionBegin;
 390   for (MachineInstr *MI : Unsched) {
 391     if (MI->isDebugValue())
 392       continue;
 393
 394     if (MI->getIterator() != RegionEnd) {
 395       BB->remove(MI);
 396       BB->insert(RegionEnd, MI);
 397       if (!MI->isDebugValue())
 398         LIS->handleMove(*MI, true);
 399     }
 400     // Reset read-undef flags and update them later.
 401     for (auto &Op : MI->operands())
 402       if (Op.isReg() && Op.isDef())
 403         Op.setIsUndef(false);
 404     RegisterOperands RegOpers;
 405     RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);
 406     if (!MI->isDebugValue()) {
 407       if (ShouldTrackLaneMasks) {
 408         // Adjust liveness and add missing dead+read-undef flags.
 409         SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
 410         RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
 411       } else {
 412         // Adjust for missing dead-def flags.
 413         RegOpers.detectDeadDefs(*MI, *LIS);
 414       }
 415     }
 416     RegionEnd = MI->getIterator();
 417     ++RegionEnd;
 418     DEBUG(dbgs() << "Scheduling " << *MI);
 419   }
 420   RegionBegin = Unsched.front()->getIterator();
 421   Regions[RegionIdx] = std::make_pair(RegionBegin, RegionEnd);
 422
 423   placeDebugValues();
 424 }
 425
 426 GCNRegPressure GCNScheduleDAGMILive::getRealRegPressure() const {
 427   GCNDownwardRPTracker RPTracker(*LIS);
 428   RPTracker.advance(begin(), end(), &LiveIns[RegionIdx]);
 429   return RPTracker.moveMaxPressure();
 430 }
 431
 432 void GCNScheduleDAGMILive::computeBlockPressure(const MachineBasicBlock *MBB) {
 433   GCNDownwardRPTracker RPTracker(*LIS);
 434
 435   // If the block has the only successor then live-ins of that successor are
 436   // live-outs of the current block. We can reuse calculated live set if the
 437   // successor will be sent to scheduling past current block.
 438   const MachineBasicBlock *OnlySucc = nullptr;
 439   if (MBB->succ_size() == 1 && !(*MBB->succ_begin())->empty()) {
 440     SlotIndexes *Ind = LIS->getSlotIndexes();
 441     if (Ind->getMBBStartIdx(MBB) < Ind->getMBBStartIdx(*MBB->succ_begin()))
 442       OnlySucc = *MBB->succ_begin();
 443   }
 444
 445   // Scheduler sends regions from the end of the block upwards.
 446   size_t CurRegion = RegionIdx;
 447   for (size_t E = Regions.size(); CurRegion != E; ++CurRegion)
 448     if (Regions[CurRegion].first->getParent() != MBB)
 449       break;
 450   --CurRegion;
 451
 452   auto I = MBB->begin();
 453   auto LiveInIt = MBBLiveIns.find(MBB);
 454   if (LiveInIt != MBBLiveIns.end()) {
 455     auto LiveIn = std::move(LiveInIt->second);
 456     RPTracker.reset(*MBB->begin(), &LiveIn);
 457     MBBLiveIns.erase(LiveInIt);
 458   } else {
 459     I = Regions[CurRegion].first;
 460     RPTracker.reset(*I);
 461   }
 462
 463   for ( ; ; ) {
 464     I = RPTracker.getNext();
 465
 466     if (Regions[CurRegion].first == I) {
 467       LiveIns[CurRegion] = RPTracker.getLiveRegs();
 468       RPTracker.clearMaxPressure();
 469     }
 470
 471     if (Regions[CurRegion].second == I) {
 472       Pressure[CurRegion] = RPTracker.moveMaxPressure();
 473       if (CurRegion-- == RegionIdx)
 474         break;
 475     }
 476     RPTracker.advanceToNext();
 477     RPTracker.advanceBeforeNext();
 478   }
 479
 480   if (OnlySucc) {
 481     if (I != MBB->end()) {
 482       RPTracker.advanceToNext();
 483       RPTracker.advance(MBB->end());
 484     }
 485     RPTracker.reset(*OnlySucc->begin(), &RPTracker.getLiveRegs());
 486     RPTracker.advanceBeforeNext();
 487     MBBLiveIns[OnlySucc] = RPTracker.moveLiveRegs();
 488   }
 489 }
 490
 491 void GCNScheduleDAGMILive::finalizeSchedule() {
 492   GCNMaxOccupancySchedStrategy &S = (GCNMaxOccupancySchedStrategy&)*SchedImpl;
 493   DEBUG(dbgs() << "All regions recorded, starting actual scheduling.\n");
 494
 495   LiveIns.resize(Regions.size());
 496   Pressure.resize(Regions.size());
 497
 498   do {
 499     Stage++;
 500     RegionIdx = 0;
 501     MachineBasicBlock *MBB = nullptr;
 502
 503     if (Stage > 1) {
 504       // Retry function scheduling if we found resulting occupancy and it is
 505       // lower than used for first pass scheduling. This will give more freedom
 506       // to schedule low register pressure blocks.
 507       // Code is partially copied from MachineSchedulerBase::scheduleRegions().
 508
 509       if (!LIS || StartingOccupancy <= MinOccupancy)
 510         break;
 511
 512       DEBUG(dbgs()
 513               << "Retrying function scheduling with lowest recorded occupancy "
 514               << MinOccupancy << ".\n");
 515
 516       S.setTargetOccupancy(MinOccupancy);
 517     }
 518
 519     for (auto Region : Regions) {
 520       RegionBegin = Region.first;
 521       RegionEnd = Region.second;
 522
 523       if (RegionBegin->getParent() != MBB) {
 524         if (MBB) finishBlock();
 525         MBB = RegionBegin->getParent();
 526         startBlock(MBB);
 527         if (Stage == 1)
 528           computeBlockPressure(MBB);
 529       }
 530
 531       unsigned NumRegionInstrs = std::distance(begin(), end());
 532       enterRegion(MBB, begin(), end(), NumRegionInstrs);
 533
 534       // Skip empty scheduling regions (0 or 1 schedulable instructions).
 535       if (begin() == end() || begin() == std::prev(end())) {
 536         exitRegion();
 537         continue;
 538       }
 539
 540       DEBUG(dbgs() << "********** MI Scheduling **********\n");
 541       DEBUG(dbgs() << MF.getName() << ":" << printMBBReference(*MBB) << " "
 542                    << MBB->getName() << "\n  From: " << *begin() << "    To: ";
 543             if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;
 544             else dbgs() << "End";
 545             dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n');
 546
 547       schedule();
 548
 549       exitRegion();
 550       ++RegionIdx;
 551     }
 552     finishBlock();
 553
 554   } while (Stage < 2);
 555 }