//===-- GCNSchedStrategy.cpp - GCN Scheduler Strategy ---------------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

/// \file

/// This contains a MachineSchedStrategy implementation for maximizing wave

/// occupancy on GCN hardware.

///

/// This pass will apply multiple scheduling stages to the same function.

/// Regions are first recorded in GCNScheduleDAGMILive::schedule. The actual

/// entry point for the scheduling of those regions is

/// GCNScheduleDAGMILive::runSchedStages.

/// Generally, the reason for having multiple scheduling stages is to account

/// for the kernel-wide effect of register usage on occupancy.  Usually, only a

/// few scheduling regions will have register pressure high enough to limit

/// occupancy for the kernel, so constraints can be relaxed to improve ILP in

/// other regions.

///

//===----------------------------------------------------------------------===//

#include "GCNSchedStrategy.h"

#include "AMDGPUIGroupLP.h"

#include "SIMachineFunctionInfo.h"

#include "llvm/CodeGen/RegisterClassInfo.h"

#define DEBUG_TYPE "machine-scheduler"

using namespace llvm;

static cl::opt<bool> DisableUnclusterHighRP(

    "amdgpu-disable-unclustered-high-rp-reschedule", cl::Hidden,

    cl::desc("Disable unclustered high register pressure "

             "reduction scheduling stage."),

    cl::init(false));

static cl::opt<bool> DisableClusteredLowOccupancy(

    "amdgpu-disable-clustered-low-occupancy-reschedule", cl::Hidden,

    cl::desc("Disable clustered low occupancy "

             "rescheduling for ILP scheduling stage."),

    cl::init(false));

static cl::opt<unsigned> ScheduleMetricBias(

    "amdgpu-schedule-metric-bias", cl::Hidden,

    cl::desc(

        "Sets the bias which adds weight to occupancy vs latency. Set it to "

        "100 to chase the occupancy only."),

    cl::init(10));

static cl::opt<bool>

    RelaxedOcc("amdgpu-schedule-relaxed-occupancy", cl::Hidden,

               cl::desc("Relax occupancy targets for kernels which are memory "

                        "bound (amdgpu-membound-threshold), or "

                        "Wave Limited (amdgpu-limit-wave-threshold)."),

               cl::init(false));

const unsigned ScheduleMetrics::ScaleFactor = 100;

GCNSchedStrategy::GCNSchedStrategy(const MachineSchedContext *C)

    : GenericScheduler(C), TargetOccupancy(0), MF(nullptr),

      HasHighPressure(false) {}

void GCNSchedStrategy::initialize(ScheduleDAGMI *DAG) {

  GenericScheduler::initialize(DAG);

  MF = &DAG->MF;

  const GCNSubtarget &ST = MF->getSubtarget<GCNSubtarget>();

  SGPRExcessLimit =

      Context->RegClassInfo->getNumAllocatableRegs(&AMDGPU::SGPR_32RegClass);

  VGPRExcessLimit =

      Context->RegClassInfo->getNumAllocatableRegs(&AMDGPU::VGPR_32RegClass);

  SIMachineFunctionInfo &MFI = *MF->getInfo<SIMachineFunctionInfo>();

  // Set the initial TargetOccupnacy to the maximum occupancy that we can

  // achieve for this function. This effectively sets a lower bound on the

  // 'Critical' register limits in the scheduler.

  // Allow for lower occupancy targets if kernel is wave limited or memory

  // bound, and using the relaxed occupancy feature.

  TargetOccupancy =

      RelaxedOcc ? MFI.getMinAllowedOccupancy() : MFI.getOccupancy();

  SGPRCriticalLimit =

      std::min(ST.getMaxNumSGPRs(TargetOccupancy, true), SGPRExcessLimit);

  if (!KnownExcessRP) {

    VGPRCriticalLimit =

        std::min(ST.getMaxNumVGPRs(TargetOccupancy), VGPRExcessLimit);

  } else {

    // This is similar to ST.getMaxNumVGPRs(TargetOccupancy) result except

    // returns a reasonably small number for targets with lots of VGPRs, such

    // as GFX10 and GFX11.

    LLVM_DEBUG(dbgs() << "Region is known to spill, use alternative "

                         "VGPRCriticalLimit calculation method.\n");

    unsigned Granule = AMDGPU::IsaInfo::getVGPRAllocGranule(&ST);

    unsigned Addressable = AMDGPU::IsaInfo::getAddressableNumVGPRs(&ST);

    unsigned VGPRBudget = alignDown(Addressable / TargetOccupancy, Granule);

    VGPRBudget = std::max(VGPRBudget, Granule);

    VGPRCriticalLimit = std::min(VGPRBudget, VGPRExcessLimit);

  }

  // Subtract error margin and bias from register limits and avoid overflow.

  SGPRCriticalLimit -= std::min(SGPRLimitBias + ErrorMargin, SGPRCriticalLimit);

  VGPRCriticalLimit -= std::min(VGPRLimitBias + ErrorMargin, VGPRCriticalLimit);

  SGPRExcessLimit -= std::min(SGPRLimitBias + ErrorMargin, SGPRExcessLimit);

  VGPRExcessLimit -= std::min(VGPRLimitBias + ErrorMargin, VGPRExcessLimit);

  LLVM_DEBUG(dbgs() << "VGPRCriticalLimit = " << VGPRCriticalLimit

                    << ", VGPRExcessLimit = " << VGPRExcessLimit

                    << ", SGPRCriticalLimit = " << SGPRCriticalLimit

                    << ", SGPRExcessLimit = " << SGPRExcessLimit << "\n\n");

}

void GCNSchedStrategy::initCandidate(SchedCandidate &Cand, SUnit *SU,

                                     bool AtTop,

                                     const RegPressureTracker &RPTracker,

                                     const SIRegisterInfo *SRI,

                                     unsigned SGPRPressure,

                                     unsigned VGPRPressure) {

  Cand.SU = SU;

  Cand.AtTop = AtTop;

  if (!DAG->isTrackingPressure())

    return;

  // getDownwardPressure() and getUpwardPressure() make temporary changes to

  // the tracker, so we need to pass those function a non-const copy.

  RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);

  Pressure.clear();

  MaxPressure.clear();

  if (AtTop)

    TempTracker.getDownwardPressure(SU->getInstr(), Pressure, MaxPressure);

  else {

    // FIXME: I think for bottom up scheduling, the register pressure is cached

    // and can be retrieved by DAG->getPressureDif(SU).

    TempTracker.getUpwardPressure(SU->getInstr(), Pressure, MaxPressure);

  }

  unsigned NewSGPRPressure = Pressure[AMDGPU::RegisterPressureSets::SReg_32];

  unsigned NewVGPRPressure = Pressure[AMDGPU::RegisterPressureSets::VGPR_32];

  // If two instructions increase the pressure of different register sets

  // by the same amount, the generic scheduler will prefer to schedule the

  // instruction that increases the set with the least amount of registers,

  // which in our case would be SGPRs.  This is rarely what we want, so

  // when we report excess/critical register pressure, we do it either

  // only for VGPRs or only for SGPRs.

  // FIXME: Better heuristics to determine whether to prefer SGPRs or VGPRs.

  const unsigned MaxVGPRPressureInc = 16;

  bool ShouldTrackVGPRs = VGPRPressure + MaxVGPRPressureInc >= VGPRExcessLimit;

  bool ShouldTrackSGPRs = !ShouldTrackVGPRs && SGPRPressure >= SGPRExcessLimit;

  // FIXME: We have to enter REG-EXCESS before we reach the actual threshold

  // to increase the likelihood we don't go over the limits.  We should improve

  // the analysis to look through dependencies to find the path with the least

  // register pressure.

  // We only need to update the RPDelta for instructions that increase register

  // pressure. Instructions that decrease or keep reg pressure the same will be

  // marked as RegExcess in tryCandidate() when they are compared with

  // instructions that increase the register pressure.

  if (ShouldTrackVGPRs && NewVGPRPressure >= VGPRExcessLimit) {

    HasHighPressure = true;

    Cand.RPDelta.Excess = PressureChange(AMDGPU::RegisterPressureSets::VGPR_32);

    Cand.RPDelta.Excess.setUnitInc(NewVGPRPressure - VGPRExcessLimit);

  }

  if (ShouldTrackSGPRs && NewSGPRPressure >= SGPRExcessLimit) {

    HasHighPressure = true;

    Cand.RPDelta.Excess = PressureChange(AMDGPU::RegisterPressureSets::SReg_32);

    Cand.RPDelta.Excess.setUnitInc(NewSGPRPressure - SGPRExcessLimit);

  }

  // Register pressure is considered 'CRITICAL' if it is approaching a value

  // that would reduce the wave occupancy for the execution unit.  When

  // register pressure is 'CRITICAL', increasing SGPR and VGPR pressure both

  // has the same cost, so we don't need to prefer one over the other.

  int SGPRDelta = NewSGPRPressure - SGPRCriticalLimit;

  int VGPRDelta = NewVGPRPressure - VGPRCriticalLimit;

  if (SGPRDelta >= 0 || VGPRDelta >= 0) {

    HasHighPressure = true;

    if (SGPRDelta > VGPRDelta) {

      Cand.RPDelta.CriticalMax =

        PressureChange(AMDGPU::RegisterPressureSets::SReg_32);

      Cand.RPDelta.CriticalMax.setUnitInc(SGPRDelta);

    } else {

      Cand.RPDelta.CriticalMax =

        PressureChange(AMDGPU::RegisterPressureSets::VGPR_32);

      Cand.RPDelta.CriticalMax.setUnitInc(VGPRDelta);

    }

  }

}

// This function is mostly cut and pasted from

// GenericScheduler::pickNodeFromQueue()

void GCNSchedStrategy::pickNodeFromQueue(SchedBoundary &Zone,

                                         const CandPolicy &ZonePolicy,

                                         const RegPressureTracker &RPTracker,

                                         SchedCandidate &Cand) {

  const SIRegisterInfo *SRI = static_cast<const SIRegisterInfo*>(TRI);

  ArrayRef<unsigned> Pressure = RPTracker.getRegSetPressureAtPos();

  unsigned SGPRPressure = 0;

  unsigned VGPRPressure = 0;

  if (DAG->isTrackingPressure()) {

    SGPRPressure = Pressure[AMDGPU::RegisterPressureSets::SReg_32];

    VGPRPressure = Pressure[AMDGPU::RegisterPressureSets::VGPR_32];

  }

  ReadyQueue &Q = Zone.Available;

  for (SUnit *SU : Q) {

    SchedCandidate TryCand(ZonePolicy);

    initCandidate(TryCand, SU, Zone.isTop(), RPTracker, SRI,

                  SGPRPressure, VGPRPressure);

    // Pass SchedBoundary only when comparing nodes from the same boundary.

    SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;

    tryCandidate(Cand, TryCand, ZoneArg);

    if (TryCand.Reason != NoCand) {

      // Initialize resource delta if needed in case future heuristics query it.

      if (TryCand.ResDelta == SchedResourceDelta())

        TryCand.initResourceDelta(Zone.DAG, SchedModel);

      Cand.setBest(TryCand);

      LLVM_DEBUG(traceCandidate(Cand));

    }

  }

}

// This function is mostly cut and pasted from

// GenericScheduler::pickNodeBidirectional()

SUnit *GCNSchedStrategy::pickNodeBidirectional(bool &IsTopNode) {

  // Schedule as far as possible in the direction of no choice. This is most

  // efficient, but also provides the best heuristics for CriticalPSets.

  if (SUnit *SU = Bot.pickOnlyChoice()) {

    IsTopNode = false;

    return SU;

  }

  if (SUnit *SU = Top.pickOnlyChoice()) {

    IsTopNode = true;

    return SU;

  }

  // Set the bottom-up policy based on the state of the current bottom zone and

  // the instructions outside the zone, including the top zone.

  CandPolicy BotPolicy;

  setPolicy(BotPolicy, /*IsPostRA=*/false, Bot, &Top);

  // Set the top-down policy based on the state of the current top zone and

  // the instructions outside the zone, including the bottom zone.

  CandPolicy TopPolicy;

  setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot);

  // See if BotCand is still valid (because we previously scheduled from Top).

  LLVM_DEBUG(dbgs() << "Picking from Bot:\n");

  if (!BotCand.isValid() || BotCand.SU->isScheduled ||

      BotCand.Policy != BotPolicy) {

    BotCand.reset(CandPolicy());

    pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);

    assert(BotCand.Reason != NoCand && "failed to find the first candidate");

  } else {

    LLVM_DEBUG(traceCandidate(BotCand));

#ifndef NDEBUG

    if (VerifyScheduling) {

      SchedCandidate TCand;

      TCand.reset(CandPolicy());

      pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);

      assert(TCand.SU == BotCand.SU &&

             "Last pick result should correspond to re-picking right now");

    }

#endif

  }

  // Check if the top Q has a better candidate.

  LLVM_DEBUG(dbgs() << "Picking from Top:\n");

  if (!TopCand.isValid() || TopCand.SU->isScheduled ||

      TopCand.Policy != TopPolicy) {

    TopCand.reset(CandPolicy());

    pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);

    assert(TopCand.Reason != NoCand && "failed to find the first candidate");

  } else {

    LLVM_DEBUG(traceCandidate(TopCand));

#ifndef NDEBUG

    if (VerifyScheduling) {

      SchedCandidate TCand;

      TCand.reset(CandPolicy());

      pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);

      assert(TCand.SU == TopCand.SU &&

           "Last pick result should correspond to re-picking right now");

    }

#endif

  }

  // Pick best from BotCand and TopCand.

  LLVM_DEBUG(dbgs() << "Top Cand: "; traceCandidate(TopCand);

             dbgs() << "Bot Cand: "; traceCandidate(BotCand););

  SchedCandidate Cand = BotCand;

  TopCand.Reason = NoCand;

  tryCandidate(Cand, TopCand, nullptr);

  if (TopCand.Reason != NoCand) {

    Cand.setBest(TopCand);

  }

  LLVM_DEBUG(dbgs() << "Picking: "; traceCandidate(Cand););

  IsTopNode = Cand.AtTop;

  return Cand.SU;

}

// This function is mostly cut and pasted from

// GenericScheduler::pickNode()

SUnit *GCNSchedStrategy::pickNode(bool &IsTopNode) {

  if (DAG->top() == DAG->bottom()) {

    assert(Top.Available.empty() && Top.Pending.empty() &&

           Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");

    return nullptr;

  }

  SUnit *SU;

  do {

    if (RegionPolicy.OnlyTopDown) {

      SU = Top.pickOnlyChoice();

      if (!SU) {

        CandPolicy NoPolicy;

        TopCand.reset(NoPolicy);

        pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);

        assert(TopCand.Reason != NoCand && "failed to find a candidate");

        SU = TopCand.SU;

      }

      IsTopNode = true;

    } else if (RegionPolicy.OnlyBottomUp) {

      SU = Bot.pickOnlyChoice();

      if (!SU) {

        CandPolicy NoPolicy;

        BotCand.reset(NoPolicy);

        pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);

        assert(BotCand.Reason != NoCand && "failed to find a candidate");

        SU = BotCand.SU;

      }

      IsTopNode = false;

    } else {

      SU = pickNodeBidirectional(IsTopNode);

    }

  } while (SU->isScheduled);

  if (SU->isTopReady())

    Top.removeReady(SU);

  if (SU->isBottomReady())

    Bot.removeReady(SU);

  LLVM_DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") "

                    << *SU->getInstr());

  return SU;

}

GCNSchedStageID GCNSchedStrategy::getCurrentStage() {

  assert(CurrentStage && CurrentStage != SchedStages.end());

  return *CurrentStage;

}

bool GCNSchedStrategy::advanceStage() {

  assert(CurrentStage != SchedStages.end());

  if (!CurrentStage)

    CurrentStage = SchedStages.begin();

  else

    CurrentStage++;

  return CurrentStage != SchedStages.end();

}

bool GCNSchedStrategy::hasNextStage() const {

  assert(CurrentStage);

  return std::next(CurrentStage) != SchedStages.end();

}

GCNSchedStageID GCNSchedStrategy::getNextStage() const {

  assert(CurrentStage && std::next(CurrentStage) != SchedStages.end());

  return *std::next(CurrentStage);

}

GCNMaxOccupancySchedStrategy::GCNMaxOccupancySchedStrategy(

    const MachineSchedContext *C)

    : GCNSchedStrategy(C) {

  SchedStages.push_back(GCNSchedStageID::OccInitialSchedule);

  SchedStages.push_back(GCNSchedStageID::UnclusteredHighRPReschedule);

  SchedStages.push_back(GCNSchedStageID::ClusteredLowOccupancyReschedule);

  SchedStages.push_back(GCNSchedStageID::PreRARematerialize);

}

GCNMaxILPSchedStrategy::GCNMaxILPSchedStrategy(const MachineSchedContext *C)

    : GCNSchedStrategy(C) {

  SchedStages.push_back(GCNSchedStageID::ILPInitialSchedule);

}

bool GCNMaxILPSchedStrategy::tryCandidate(SchedCandidate &Cand,

                                          SchedCandidate &TryCand,

                                          SchedBoundary *Zone) const {

  // Initialize the candidate if needed.

  if (!Cand.isValid()) {

    TryCand.Reason = NodeOrder;

    return true;

  }

  // Avoid spilling by exceeding the register limit.

  if (DAG->isTrackingPressure() &&

      tryPressure(TryCand.RPDelta.Excess, Cand.RPDelta.Excess, TryCand, Cand,

                  RegExcess, TRI, DAG->MF))

    return TryCand.Reason != NoCand;

  // Bias PhysReg Defs and copies to their uses and defined respectively.

  if (tryGreater(biasPhysReg(TryCand.SU, TryCand.AtTop),

                 biasPhysReg(Cand.SU, Cand.AtTop), TryCand, Cand, PhysReg))

    return TryCand.Reason != NoCand;

  bool SameBoundary = Zone != nullptr;

  if (SameBoundary) {

    // Prioritize instructions that read unbuffered resources by stall cycles.

    if (tryLess(Zone->getLatencyStallCycles(TryCand.SU),

                Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))

      return TryCand.Reason != NoCand;

    // Avoid critical resource consumption and balance the schedule.

    TryCand.initResourceDelta(DAG, SchedModel);

    if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,

                TryCand, Cand, ResourceReduce))

      return TryCand.Reason != NoCand;

    if (tryGreater(TryCand.ResDelta.DemandedResources,

                   Cand.ResDelta.DemandedResources, TryCand, Cand,

                   ResourceDemand))

      return TryCand.Reason != NoCand;

    // Unconditionally try to reduce latency.

    if (tryLatency(TryCand, Cand, *Zone))

      return TryCand.Reason != NoCand;

    // Weak edges are for clustering and other constraints.

    if (tryLess(getWeakLeft(TryCand.SU, TryCand.AtTop),

                getWeakLeft(Cand.SU, Cand.AtTop), TryCand, Cand, Weak))

      return TryCand.Reason != NoCand;

  }

  // Keep clustered nodes together to encourage downstream peephole

  // optimizations which may reduce resource requirements.

  //

  // This is a best effort to set things up for a post-RA pass. Optimizations

  // like generating loads of multiple registers should ideally be done within

  // the scheduler pass by combining the loads during DAG postprocessing.

  const SUnit *CandNextClusterSU =

      Cand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();

  const SUnit *TryCandNextClusterSU =

      TryCand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();

  if (tryGreater(TryCand.SU == TryCandNextClusterSU,

                 Cand.SU == CandNextClusterSU, TryCand, Cand, Cluster))

    return TryCand.Reason != NoCand;

  // Avoid increasing the max critical pressure in the scheduled region.

  if (DAG->isTrackingPressure() &&

      tryPressure(TryCand.RPDelta.CriticalMax, Cand.RPDelta.CriticalMax,

                  TryCand, Cand, RegCritical, TRI, DAG->MF))

    return TryCand.Reason != NoCand;

  // Avoid increasing the max pressure of the entire region.

  if (DAG->isTrackingPressure() &&

      tryPressure(TryCand.RPDelta.CurrentMax, Cand.RPDelta.CurrentMax, TryCand,

                  Cand, RegMax, TRI, DAG->MF))

    return TryCand.Reason != NoCand;

  if (SameBoundary) {

    // Fall through to original instruction order.

    if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) ||

        (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {

      TryCand.Reason = NodeOrder;

      return true;

    }

  }

  return false;

}

GCNScheduleDAGMILive::GCNScheduleDAGMILive(

    MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S)

    : ScheduleDAGMILive(C, std::move(S)), ST(MF.getSubtarget<GCNSubtarget>()),

      MFI(*MF.getInfo<SIMachineFunctionInfo>()),

      StartingOccupancy(MFI.getOccupancy()), MinOccupancy(StartingOccupancy) {

  LLVM_DEBUG(dbgs() << "Starting occupancy is " << StartingOccupancy << ".\n");

  if (RelaxedOcc) {

    MinOccupancy = std::min(MFI.getMinAllowedOccupancy(), StartingOccupancy);

    if (MinOccupancy != StartingOccupancy)

      LLVM_DEBUG(dbgs() << "Allowing Occupancy drops to " << MinOccupancy

                        << ".\n");

  }

}

std::unique_ptr<GCNSchedStage>

GCNScheduleDAGMILive::createSchedStage(GCNSchedStageID SchedStageID) {

  switch (SchedStageID) {

  case GCNSchedStageID::OccInitialSchedule:

    return std::make_unique<OccInitialScheduleStage>(SchedStageID, *this);

  case GCNSchedStageID::UnclusteredHighRPReschedule:

    return std::make_unique<UnclusteredHighRPStage>(SchedStageID, *this);

  case GCNSchedStageID::ClusteredLowOccupancyReschedule:

    return std::make_unique<ClusteredLowOccStage>(SchedStageID, *this);

  case GCNSchedStageID::PreRARematerialize:

    return std::make_unique<PreRARematStage>(SchedStageID, *this);

  case GCNSchedStageID::ILPInitialSchedule:

    return std::make_unique<ILPInitialScheduleStage>(SchedStageID, *this);

  }

  llvm_unreachable("Unknown SchedStageID.");

}

void GCNScheduleDAGMILive::schedule() {

  // Collect all scheduling regions. The actual scheduling is performed in

  // GCNScheduleDAGMILive::finalizeSchedule.

  Regions.push_back(std::pair(RegionBegin, RegionEnd));

}

GCNRegPressure

GCNScheduleDAGMILive::getRealRegPressure(unsigned RegionIdx) const {

  GCNDownwardRPTracker RPTracker(*LIS);

  RPTracker.advance(begin(), end(), &LiveIns[RegionIdx]);

  return RPTracker.moveMaxPressure();

}

void GCNScheduleDAGMILive::computeBlockPressure(unsigned RegionIdx,

                                                const MachineBasicBlock *MBB) {

  GCNDownwardRPTracker RPTracker(*LIS);

  // If the block has the only successor then live-ins of that successor are

  // live-outs of the current block. We can reuse calculated live set if the

  // successor will be sent to scheduling past current block.

  // However, due to the bug in LiveInterval analysis it may happen that two

  // predecessors of the same successor block have different lane bitmasks for

  // a live-out register. Workaround that by sticking to one-to-one relationship

  // i.e. one predecessor with one successor block.

  const MachineBasicBlock *OnlySucc = nullptr;

  if (MBB->succ_size() == 1) {

    auto *Candidate = *MBB->succ_begin();

    if (!Candidate->empty() && Candidate->pred_size() == 1) {

      SlotIndexes *Ind = LIS->getSlotIndexes();

      if (Ind->getMBBStartIdx(MBB) < Ind->getMBBStartIdx(Candidate))

        OnlySucc = Candidate;

    }

  }

  // Scheduler sends regions from the end of the block upwards.

  size_t CurRegion = RegionIdx;

  for (size_t E = Regions.size(); CurRegion != E; ++CurRegion)

    if (Regions[CurRegion].first->getParent() != MBB)

      break;

  --CurRegion;

  auto I = MBB->begin();

  auto LiveInIt = MBBLiveIns.find(MBB);

  auto &Rgn = Regions[CurRegion];

  auto *NonDbgMI = &*skipDebugInstructionsForward(Rgn.first, Rgn.second);

  if (LiveInIt != MBBLiveIns.end()) {

    auto LiveIn = std::move(LiveInIt->second);

    RPTracker.reset(*MBB->begin(), &LiveIn);

    MBBLiveIns.erase(LiveInIt);

  } else {

    I = Rgn.first;

    auto LRS = BBLiveInMap.lookup(NonDbgMI);

#ifdef EXPENSIVE_CHECKS

    assert(isEqual(getLiveRegsBefore(*NonDbgMI, *LIS), LRS));

#endif

    RPTracker.reset(*I, &LRS);

  }

  for (;;) {

    I = RPTracker.getNext();

    if (Regions[CurRegion].first == I || NonDbgMI == I) {

      LiveIns[CurRegion] = RPTracker.getLiveRegs();

      RPTracker.clearMaxPressure();

    }

    if (Regions[CurRegion].second == I) {

      Pressure[CurRegion] = RPTracker.moveMaxPressure();

      if (CurRegion-- == RegionIdx)

        break;

    }

    RPTracker.advanceToNext();

    RPTracker.advanceBeforeNext();

  }

  if (OnlySucc) {

    if (I != MBB->end()) {

      RPTracker.advanceToNext();

      RPTracker.advance(MBB->end());

    }

    RPTracker.advanceBeforeNext();

    MBBLiveIns[OnlySucc] = RPTracker.moveLiveRegs();

  }

}

DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet>

GCNScheduleDAGMILive::getBBLiveInMap() const {

  assert(!Regions.empty());

  std::vector<MachineInstr *> BBStarters;

  BBStarters.reserve(Regions.size());

  auto I = Regions.rbegin(), E = Regions.rend();

  auto *BB = I->first->getParent();

  do {

    auto *MI = &*skipDebugInstructionsForward(I->first, I->second);

    BBStarters.push_back(MI);

    do {

      ++I;

    } while (I != E && I->first->getParent() == BB);

  } while (I != E);

  return getLiveRegMap(BBStarters, false /*After*/, *LIS);

}

void GCNScheduleDAGMILive::finalizeSchedule() {

  // Start actual scheduling here. This function is called by the base

  // MachineScheduler after all regions have been recorded by

  // GCNScheduleDAGMILive::schedule().

  LiveIns.resize(Regions.size());

  Pressure.resize(Regions.size());

  RescheduleRegions.resize(Regions.size());

  RegionsWithHighRP.resize(Regions.size());

  RegionsWithExcessRP.resize(Regions.size());

  RegionsWithMinOcc.resize(Regions.size());

  RegionsWithIGLPInstrs.resize(Regions.size());

  RescheduleRegions.set();

  RegionsWithHighRP.reset();

  RegionsWithExcessRP.reset();

  RegionsWithMinOcc.reset();

  RegionsWithIGLPInstrs.reset();

  runSchedStages();

}

void GCNScheduleDAGMILive::runSchedStages() {

  LLVM_DEBUG(dbgs() << "All regions recorded, starting actual scheduling.\n");

  if (!Regions.empty())

    BBLiveInMap = getBBLiveInMap();

  GCNSchedStrategy &S = static_cast<GCNSchedStrategy &>(*SchedImpl);

  while (S.advanceStage()) {

    auto Stage = createSchedStage(S.getCurrentStage());

    if (!Stage->initGCNSchedStage())

      continue;

    for (auto Region : Regions) {

      RegionBegin = Region.first;

      RegionEnd = Region.second;

      // Setup for scheduling the region and check whether it should be skipped.

      if (!Stage->initGCNRegion()) {

        Stage->advanceRegion();

        exitRegion();

        continue;

      }

      ScheduleDAGMILive::schedule();

      Stage->finalizeGCNRegion();

    }

    Stage->finalizeGCNSchedStage();

  }

}

#ifndef NDEBUG

raw_ostream &llvm::operator<<(raw_ostream &OS, const GCNSchedStageID &StageID) {

  switch (StageID) {

  case GCNSchedStageID::OccInitialSchedule:

    OS << "Max Occupancy Initial Schedule";

    break;

  case GCNSchedStageID::UnclusteredHighRPReschedule:

    OS << "Unclustered High Register Pressure Reschedule";

    break;

  case GCNSchedStageID::ClusteredLowOccupancyReschedule:

    OS << "Clustered Low Occupancy Reschedule";

    break;

  case GCNSchedStageID::PreRARematerialize:

    OS << "Pre-RA Rematerialize";

    break;

  case GCNSchedStageID::ILPInitialSchedule:

    OS << "Max ILP Initial Schedule";

    break;

  }

  return OS;

}

#endif

GCNSchedStage::GCNSchedStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)

    : DAG(DAG), S(static_cast<GCNSchedStrategy &>(*DAG.SchedImpl)), MF(DAG.MF),

      MFI(DAG.MFI), ST(DAG.ST), StageID(StageID) {}

bool GCNSchedStage::initGCNSchedStage() {

  if (!DAG.LIS)

    return false;

  LLVM_DEBUG(dbgs() << "Starting scheduling stage: " << StageID << "\n");

  return true;

}

bool UnclusteredHighRPStage::initGCNSchedStage() {

  if (DisableUnclusterHighRP)

    return false;

  if (!GCNSchedStage::initGCNSchedStage())

    return false;

  if (DAG.RegionsWithHighRP.none() && DAG.RegionsWithExcessRP.none())

    return false;

  SavedMutations.swap(DAG.Mutations);

  DAG.addMutation(createIGroupLPDAGMutation(/*IsPostRA=*/false));

  InitialOccupancy = DAG.MinOccupancy;

  // Aggressivly try to reduce register pressure in the unclustered high RP

  // stage. Temporarily increase occupancy target in the region.

  S.SGPRLimitBias = S.HighRPSGPRBias;

  S.VGPRLimitBias = S.HighRPVGPRBias;

  if (MFI.getMaxWavesPerEU() > DAG.MinOccupancy)

    MFI.increaseOccupancy(MF, ++DAG.MinOccupancy);

  LLVM_DEBUG(

      dbgs()

      << "Retrying function scheduling without clustering. "

         "Aggressivly try to reduce register pressure to achieve occupancy "

      << DAG.MinOccupancy << ".\n");

  return true;

}

bool ClusteredLowOccStage::initGCNSchedStage() {

  if (DisableClusteredLowOccupancy)

    return false;

  if (!GCNSchedStage::initGCNSchedStage())

    return false;

  // Don't bother trying to improve ILP in lower RP regions if occupancy has not

  // been dropped. All regions will have already been scheduled with the ideal

  // occupancy targets.

  if (DAG.StartingOccupancy <= DAG.MinOccupancy)

    return false;

  LLVM_DEBUG(

      dbgs() << "Retrying function scheduling with lowest recorded occupancy "

             << DAG.MinOccupancy << ".\n");

  return true;

}

bool PreRARematStage::initGCNSchedStage() {

  if (!GCNSchedStage::initGCNSchedStage())

    return false;

  if (DAG.RegionsWithMinOcc.none() || DAG.Regions.size() == 1)

    return false;

  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();

  // Check maximum occupancy

  if (ST.computeOccupancy(MF.getFunction(), MFI.getLDSSize()) ==

      DAG.MinOccupancy)

    return false;

  // FIXME: This pass will invalidate cached MBBLiveIns for regions

  // inbetween the defs and region we sinked the def to. Cached pressure

  // for regions where a def is sinked from will also be invalidated. Will

  // need to be fixed if there is another pass after this pass.

  assert(!S.hasNextStage());

  collectRematerializableInstructions();

  if (RematerializableInsts.empty() || !sinkTriviallyRematInsts(ST, TII))

    return false;

  LLVM_DEBUG(

      dbgs() << "Retrying function scheduling with improved occupancy of "

             << DAG.MinOccupancy << " from rematerializing\n");

  return true;

}

void GCNSchedStage::finalizeGCNSchedStage() {

  DAG.finishBlock();

  LLVM_DEBUG(dbgs() << "Ending scheduling stage: " << StageID << "\n");

}

void UnclusteredHighRPStage::finalizeGCNSchedStage() {

  SavedMutations.swap(DAG.Mutations);

  S.SGPRLimitBias = S.VGPRLimitBias = 0;

  if (DAG.MinOccupancy > InitialOccupancy) {

    for (unsigned IDX = 0; IDX < DAG.Pressure.size(); ++IDX)

      DAG.RegionsWithMinOcc[IDX] =

          DAG.Pressure[IDX].getOccupancy(DAG.ST) == DAG.MinOccupancy;

    LLVM_DEBUG(dbgs() << StageID

                      << " stage successfully increased occupancy to "

                      << DAG.MinOccupancy << '\n');

  }

  GCNSchedStage::finalizeGCNSchedStage();

}

bool GCNSchedStage::initGCNRegion() {

  // Check whether this new region is also a new block.

  if (DAG.RegionBegin->getParent() != CurrentMBB)

    setupNewBlock();

  unsigned NumRegionInstrs = std::distance(DAG.begin(), DAG.end());

  DAG.enterRegion(CurrentMBB, DAG.begin(), DAG.end(), NumRegionInstrs);

  // Skip empty scheduling regions (0 or 1 schedulable instructions).

  if (DAG.begin() == DAG.end() || DAG.begin() == std::prev(DAG.end()))

    return false;

  LLVM_DEBUG(dbgs() << "********** MI Scheduling **********\n");

  LLVM_DEBUG(dbgs() << MF.getName() << ":" << printMBBReference(*CurrentMBB)

                    << " " << CurrentMBB->getName()

                    << "\n  From: " << *DAG.begin() << "    To: ";

             if (DAG.RegionEnd != CurrentMBB->end()) dbgs() << *DAG.RegionEnd;

             else dbgs() << "End";

             dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n');

  // Save original instruction order before scheduling for possible revert.

  Unsched.clear();

  Unsched.reserve(DAG.NumRegionInstrs);

  if (StageID == GCNSchedStageID::OccInitialSchedule ||

      StageID == GCNSchedStageID::ILPInitialSchedule) {

    for (auto &I : DAG) {

      Unsched.push_back(&I);

      if (I.getOpcode() == AMDGPU::SCHED_GROUP_BARRIER ||

          I.getOpcode() == AMDGPU::IGLP_OPT)

        DAG.RegionsWithIGLPInstrs[RegionIdx] = true;

    }

  } else {

    for (auto &I : DAG)

      Unsched.push_back(&I);

  }

  PressureBefore = DAG.Pressure[RegionIdx];

  LLVM_DEBUG(

      dbgs() << "Pressure before scheduling:\nRegion live-ins:"

             << print(DAG.LiveIns[RegionIdx], DAG.MRI)

             << "Region live-in pressure:  "

             << print(llvm::getRegPressure(DAG.MRI, DAG.LiveIns[RegionIdx]))

             << "Region register pressure: " << print(PressureBefore));

  S.HasHighPressure = false;

  S.KnownExcessRP = isRegionWithExcessRP();

  if (DAG.RegionsWithIGLPInstrs[RegionIdx] &&

      StageID != GCNSchedStageID::UnclusteredHighRPReschedule) {

    SavedMutations.clear();

    SavedMutations.swap(DAG.Mutations);

    bool IsInitialStage = StageID == GCNSchedStageID::OccInitialSchedule ||

                          StageID == GCNSchedStageID::ILPInitialSchedule;

    DAG.addMutation(createIGroupLPDAGMutation(/*IsReentry=*/!IsInitialStage));

  }

  return true;

}

bool UnclusteredHighRPStage::initGCNRegion() {

  // Only reschedule regions with the minimum occupancy or regions that may have

  // spilling (excess register pressure).

  if ((!DAG.RegionsWithMinOcc[RegionIdx] ||

       DAG.MinOccupancy <= InitialOccupancy) &&

      !DAG.RegionsWithExcessRP[RegionIdx])

    return false;

  return GCNSchedStage::initGCNRegion();

}

bool ClusteredLowOccStage::initGCNRegion() {

  // We may need to reschedule this region if it wasn't rescheduled in the last

  // stage, or if we found it was testing critical register pressure limits in

  // the unclustered reschedule stage. The later is because we may not have been

  // able to raise the min occupancy in the previous stage so the region may be

  // overly constrained even if it was already rescheduled.

  if (!DAG.RegionsWithHighRP[RegionIdx])

    return false;

  return GCNSchedStage::initGCNRegion();

}

bool PreRARematStage::initGCNRegion() {

  if (!DAG.RescheduleRegions[RegionIdx])

    return false;

  return GCNSchedStage::initGCNRegion();

}

void GCNSchedStage::setupNewBlock() {

  if (CurrentMBB)

    DAG.finishBlock();