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

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