AMDGPU: Partial ILP scheduler port from SelectionDAG to SchedulingDAG (experimental)

[vpykhtin]

Summary

This is a partial port in that register pressure lowering checks aren't yet done because it isn't really straitforward to port them from the old place

There're some comments left copypasted from the old place, it may be outdated/irrelevant.

[rampitec]

Can you add some tests just to show it does not crash? Maybe add run-lines to schedule-regpressure-limit.ll, schedule-regpressure-limit2.ll

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

224

Can we use ld/st clustering mutations and MacroFusion to it?

[rampitec]

lib/Target/AMDGPU/GCNILPSched.cpp

244

Can queue be empty?

284

spaces around ==.

[vpykhtin]

fixed per review issues.

[rampitec]

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

224

i think we need MacroFusion as well.

[vpykhtin]

Added test. It turns out getOccupancyWithLocalMemSize function doesn't account for amdgpu-waves-per-eu attribute so I added call to getWavesPerEU (which does).

[rampitec]

LGTM

lib/Target/AMDGPU/GCNIterativeScheduler.cpp

569

Looks like this call is missing in the GCNSchedStrategy as well, so needs to be added there as well.

[vpykhtin]

lib/Target/AMDGPU/GCNIterativeScheduler.cpp

569

Right, but I wonder if this should be added into getOccupancyWithLocalMemSize itself? It uses getMaxWavesPerEU which probably should be changed to getWavesPerEU.

[rampitec]

lib/Target/AMDGPU/GCNIterativeScheduler.cpp

569

It probably should, though I believe it should go as a separate change.

[arsenm]

test/CodeGen/AMDGPU/schedule-ilp.ll

3 ↗

(On Diff #123341)

This isn't a useful check. Is there something more specific to check, like there are no spills or some other improvement over the default?

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

createIterativeGCNMaxOccupancyMachineScheduler(MachineSchedContext *C) {
   return DAG;
 }
 
 static ScheduleDAGInstrs *createMinRegScheduler(MachineSchedContext *C) {
   return new GCNIterativeScheduler(C,
     GCNIterativeScheduler::SCHEDULE_MINREGFORCED);
 }
 
+static ScheduleDAGInstrs *
+createIterativeILPMachineScheduler(MachineSchedContext *C) {
+  auto DAG = new GCNIterativeScheduler(C,
+    GCNIterativeScheduler::SCHEDULE_ILP);
+  DAG->addMutation(createLoadClusterDAGMutation(DAG->TII, DAG->TRI));
+  DAG->addMutation(createStoreClusterDAGMutation(DAG->TII, DAG->TRI));
+  return DAG;
+}
+
 static MachineSchedRegistry
 R600SchedRegistry("r600", "Run R600's custom scheduler",
                    createR600MachineScheduler);
 
 static MachineSchedRegistry
 SISchedRegistry("si", "Run SI's custom scheduler",
                 createSIMachineScheduler);
 
 static MachineSchedRegistry
 GCNMaxOccupancySchedRegistry("gcn-max-occupancy",
                              "Run GCN scheduler to maximize occupancy",
                              createGCNMaxOccupancyMachineScheduler);
 
 static MachineSchedRegistry
 IterativeGCNMaxOccupancySchedRegistry("gcn-max-occupancy-experimental",
   "Run GCN scheduler to maximize occupancy (experimental)",
   createIterativeGCNMaxOccupancyMachineScheduler);
 
 static MachineSchedRegistry
 GCNMinRegSchedRegistry("gcn-minreg",
   "Run GCN iterative scheduler for minimal register usage (experimental)",
   createMinRegScheduler);
 
+static MachineSchedRegistry
+GCNILPSchedRegistry("gcn-ilp",
+  "Run GCN iterative scheduler for ILP scheduling (experimental)",
+  createIterativeILPMachineScheduler);
+
 static StringRef computeDataLayout(const Triple &TT) {
   if (TT.getArch() == Triple::r600) {
     // 32-bit pointers.
     if (TT.getEnvironmentName() == "amdgiz" ||
         TT.getEnvironmentName() == "amdgizcl")
       return "e-p:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128"
              "-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-A5";
     return "e-p:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128"

lib/Target/AMDGPU/CMakeLists.txt

add_llvm_target(AMDGPUCodeGen
   SIMachineScheduler.cpp
   SIMemoryLegalizer.cpp
   SIOptimizeExecMasking.cpp
   SIOptimizeExecMaskingPreRA.cpp
   SIPeepholeSDWA.cpp
   SIRegisterInfo.cpp
   SIShrinkInstructions.cpp
   SIWholeQuadMode.cpp
+  GCNILPSched.cpp
   )
 
 add_subdirectory(AsmParser)
 add_subdirectory(InstPrinter)
 add_subdirectory(Disassembler)
 add_subdirectory(TargetInfo)
 add_subdirectory(MCTargetDesc)
 add_subdirectory(Utils)

lib/Target/AMDGPU/GCNILPSched.cpp

+//===---------------------------- GCNILPSched.cpp - -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/ScheduleDAG.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "machine-scheduler"
+
+namespace {
+
+class GCNILPScheduler {
+  struct Candidate : ilist_node<Candidate> {
+    SUnit *SU;
+
+    Candidate(SUnit *SU_)
+      : SU(SU_) {}
+  };
+
+  SpecificBumpPtrAllocator<Candidate> Alloc;
+  typedef simple_ilist<Candidate> Queue;
+  Queue PendingQueue;
+  Queue AvailQueue;
+  unsigned CurQueueId = 0;
+
+  std::vector<unsigned> SUNumbers;
+
+  /// CurCycle - The current scheduler state corresponds to this cycle.
+  unsigned CurCycle = 0;
+
+  unsigned getNodePriority(const SUnit *SU) const;
+
+  const SUnit *pickBest(const SUnit *left, const SUnit *right);
+  Candidate* pickCandidate();
+
+  void releasePending();
+  void advanceToCycle(unsigned NextCycle);
+  void releasePredecessors(const SUnit* SU);
+
+public:
+  std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots,
+                                     const ScheduleDAG &DAG);
+};
+} // namespace
+
+/// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
+/// Smaller number is the higher priority.
+static unsigned
+CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
+  unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
+  if (SethiUllmanNumber != 0)
+    return SethiUllmanNumber;
+
+  unsigned Extra = 0;
+  for (const SDep &Pred : SU->Preds) {
+    if (Pred.isCtrl()) continue;  // ignore chain preds
+    SUnit *PredSU = Pred.getSUnit();
+    unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
+    if (PredSethiUllman > SethiUllmanNumber) {
+      SethiUllmanNumber = PredSethiUllman;
+      Extra = 0;
+    }
+    else if (PredSethiUllman == SethiUllmanNumber)
+      ++Extra;
+  }
+
+  SethiUllmanNumber += Extra;
+
+  if (SethiUllmanNumber == 0)
+    SethiUllmanNumber = 1;
+
+  return SethiUllmanNumber;
+}
+
+// Lower priority means schedule further down. For bottom-up scheduling, lower
+// priority SUs are scheduled before higher priority SUs.
+unsigned GCNILPScheduler::getNodePriority(const SUnit *SU) const {
+  assert(SU->NodeNum < SUNumbers.size());
+  if (SU->NumSuccs == 0 && SU->NumPreds != 0)
+    // If SU does not have a register use, i.e. it doesn't produce a value
+    // that would be consumed (e.g. store), then it terminates a chain of
+    // computation.  Give it a large SethiUllman number so it will be
+    // scheduled right before its predecessors that it doesn't lengthen
+    // their live ranges.
+    return 0xffff;
+
+  if (SU->NumPreds == 0 && SU->NumSuccs != 0)
+    // If SU does not have a register def, schedule it close to its uses
+    // because it does not lengthen any live ranges.
+    return 0;
+
+  return SUNumbers[SU->NodeNum];
+}
+
+/// closestSucc - Returns the scheduled cycle of the successor which is
+/// closest to the current cycle.
+static unsigned closestSucc(const SUnit *SU) {
+  unsigned MaxHeight = 0;
+  for (const SDep &Succ : SU->Succs) {
+    if (Succ.isCtrl()) continue;  // ignore chain succs
+    unsigned Height = Succ.getSUnit()->getHeight();
+    // If there are bunch of CopyToRegs stacked up, they should be considered
+    // to be at the same position.
+    if (Height > MaxHeight)
+      MaxHeight = Height;
+  }
+  return MaxHeight;
+}
+
+/// calcMaxScratches - Returns an cost estimate of the worse case requirement
+/// for scratch registers, i.e. number of data dependencies.
+static unsigned calcMaxScratches(const SUnit *SU) {
+  unsigned Scratches = 0;
+  for (const SDep &Pred : SU->Preds) {
+    if (Pred.isCtrl()) continue;  // ignore chain preds
+    Scratches++;
+  }
+  return Scratches;
+}
+
+// Return -1 if left has higher priority, 1 if right has higher priority.
+// Return 0 if latency-based priority is equivalent.
+static int BUCompareLatency(const SUnit *left, const SUnit *right) {
+  // Scheduling an instruction that uses a VReg whose postincrement has not yet
+  // been scheduled will induce a copy. Model this as an extra cycle of latency.
+  int LHeight = (int)left->getHeight();
+  int RHeight = (int)right->getHeight();
+
+  // If either node is scheduling for latency, sort them by height/depth
+  // and latency.
+
+  // If neither instruction stalls (!LStall && !RStall) and HazardRecognizer
+  // is enabled, grouping instructions by cycle, then its height is already
+  // covered so only its depth matters. We also reach this point if both stall
+  // but have the same height.
+  if (LHeight != RHeight)
+    return LHeight > RHeight ? 1 : -1;
+
+  int LDepth = left->getDepth();
+  int RDepth = right->getDepth();
+  if (LDepth != RDepth) {
+    DEBUG(dbgs() << "  Comparing latency of SU (" << left->NodeNum
+      << ") depth " << LDepth << " vs SU (" << right->NodeNum
+      << ") depth " << RDepth << "\n");
+    return LDepth < RDepth ? 1 : -1;
+  }
+  if (left->Latency != right->Latency)
+    return left->Latency > right->Latency ? 1 : -1;
+
+  return 0;
+}
+
+const SUnit *GCNILPScheduler::pickBest(const SUnit *left, const SUnit *right)
+{
+  // TODO: add register pressure lowering checks
+
+  bool const DisableSchedCriticalPath = false;
+  int MaxReorderWindow = 6;
+  if (!DisableSchedCriticalPath) {
+    int spread = (int)left->getDepth() - (int)right->getDepth();
+    if (std::abs(spread) > MaxReorderWindow) {
+      DEBUG(dbgs() << "Depth of SU(" << left->NodeNum << "): "
+        << left->getDepth() << " != SU(" << right->NodeNum << "): "
+        << right->getDepth() << "\n");
+      return left->getDepth() < right->getDepth() ? right : left;
+    }
+  }
+
+  bool const DisableSchedHeight = false;
+  if (!DisableSchedHeight && left->getHeight() != right->getHeight()) {
+    int spread = (int)left->getHeight() - (int)right->getHeight();
+    if (std::abs(spread) > MaxReorderWindow)
+      return left->getHeight() > right->getHeight() ? right : left;
+  }
+
+  // Prioritize by Sethi-Ulmann number and push CopyToReg nodes down.
+  unsigned LPriority = getNodePriority(left);
+  unsigned RPriority = getNodePriority(right);
+
+  if (LPriority != RPriority)
+    return LPriority > RPriority ? right : left;
+
+  // Try schedule def + use closer when Sethi-Ullman numbers are the same.
+  // e.g.
+  // t1 = op t2, c1
+  // t3 = op t4, c2
+  //
+  // and the following instructions are both ready.
+  // t2 = op c3
+  // t4 = op c4
+  //
+  // Then schedule t2 = op first.
+  // i.e.
+  // t4 = op c4
+  // t2 = op c3
+  // t1 = op t2, c1
+  // t3 = op t4, c2
+  //
+  // This creates more short live intervals.
+  unsigned LDist = closestSucc(left);
+  unsigned RDist = closestSucc(right);
+  if (LDist != RDist)
+    return LDist < RDist ? right : left;
+
+  // How many registers becomes live when the node is scheduled.
+  unsigned LScratch = calcMaxScratches(left);
+  unsigned RScratch = calcMaxScratches(right);
+  if (LScratch != RScratch)
+    return LScratch > RScratch ? right : left;
+
+  bool const DisableSchedCycles = false;
+  if (!DisableSchedCycles) {
+    int result = BUCompareLatency(left, right);
+    if (result != 0)
+      return result > 0 ? right : left;
+    return left;
+  }
+  else {
+    if (left->getHeight() != right->getHeight())
+      return (left->getHeight() > right->getHeight()) ? right : left;
+
+    if (left->getDepth() != right->getDepth())
+      return (left->getDepth() < right->getDepth()) ? right : left;
+  }
+
+  assert(left->NodeQueueId && right->NodeQueueId &&
+        "NodeQueueId cannot be zero");
+  return (left->NodeQueueId > right->NodeQueueId) ? right : left;
+}
+
+GCNILPScheduler::Candidate* GCNILPScheduler::pickCandidate() {
+  if (AvailQueue.empty())
+    return nullptr;
+  auto Best = AvailQueue.begin();
+  for (auto I = std::next(AvailQueue.begin()), E = AvailQueue.end(); I != E; ++I) {
+    auto NewBestSU = pickBest(Best->SU, I->SU);
+    if (NewBestSU != Best->SU) {
+      assert(NewBestSU == I->SU);
+      Best = I;
+    }
+  }
+  return &*Best;
+}
+
+void GCNILPScheduler::releasePending() {
+  // Check to see if any of the pending instructions are ready to issue.  If
+  // so, add them to the available queue.
+  for(auto I = PendingQueue.begin(), E = PendingQueue.end(); I != E;) {
+    auto &C = *I++;
+    if (C.SU->getHeight() <= CurCycle) {
+      PendingQueue.remove(C);
+      AvailQueue.push_back(C);
+      C.SU->NodeQueueId = CurQueueId++;
+    }
+  }
+}
+
+/// Move the scheduler state forward by the specified number of Cycles.
+void GCNILPScheduler::advanceToCycle(unsigned NextCycle) {
+  if (NextCycle <= CurCycle)
+    return;
+  CurCycle = NextCycle;
+  releasePending();
+}
+
+void GCNILPScheduler::releasePredecessors(const SUnit* SU) {
+  for (const auto &PredEdge : SU->Preds) {
+    auto PredSU = PredEdge.getSUnit();
+    if (PredEdge.isWeak())
+      continue;
+    assert(PredSU->isBoundaryNode() || PredSU->NumSuccsLeft > 0);
+
+    PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge.getLatency());
+
+    if (!PredSU->isBoundaryNode() && --PredSU->NumSuccsLeft == 0)
+      PendingQueue.push_front(*new (Alloc.Allocate()) Candidate(PredSU));
+  }
+}
+
+std::vector<const SUnit*>
+GCNILPScheduler::schedule(ArrayRef<const SUnit*> BotRoots,
+                          const ScheduleDAG &DAG) {
+  auto &SUnits = const_cast<ScheduleDAG&>(DAG).SUnits;
+
+  std::vector<SUnit> SUSavedCopy;
+  SUSavedCopy.resize(SUnits.size());
+
+  // we cannot save only those fields we touch: some of them are private
+  // so save units verbatim: this assumes SUnit should have value semantics
+  for (const SUnit &SU : SUnits)
+    SUSavedCopy[SU.NodeNum] = SU;
+
+  SUNumbers.assign(SUnits.size(), 0);
+  for (const SUnit &SU : SUnits)
+    CalcNodeSethiUllmanNumber(&SU, SUNumbers);
+
+  for (auto SU : BotRoots) {
+    AvailQueue.push_back(
+      *new (Alloc.Allocate()) Candidate(const_cast<SUnit*>(SU)));
+  }
+  releasePredecessors(&DAG.ExitSU);
+
+  std::vector<const SUnit*> Schedule;
+  Schedule.reserve(SUnits.size());
+  while (true) {
+    if (AvailQueue.empty() && !PendingQueue.empty()) {
+      auto EarliestSU = std::min_element(
+        PendingQueue.begin(), PendingQueue.end(),
+        [=](const Candidate& C1, const Candidate& C2) {
+        return C1.SU->getHeight() < C2.SU->getHeight();
+      })->SU;
+      advanceToCycle(std::max(CurCycle + 1, EarliestSU->getHeight()));
+    }
+    if (AvailQueue.empty())
+      break;
+
+    DEBUG(
+      dbgs() << "\n=== Picking candidate\n"
+                "Ready queue:";
+      for (auto &C : AvailQueue)
+        dbgs() << ' ' << C.SU->NodeNum;
+      dbgs() << '\n';
+    );
+
+    auto C = pickCandidate();
+    assert(C);
+    AvailQueue.remove(*C);
+    auto SU = C->SU;
+    DEBUG(dbgs() << "Selected "; SU->dump(&DAG));
+
+    advanceToCycle(SU->getHeight());
+
+    releasePredecessors(SU);
+    Schedule.push_back(SU);
+    SU->isScheduled = true;
+  }
+  assert(SUnits.size() == Schedule.size());
+
+  std::reverse(Schedule.begin(), Schedule.end());
+
+  // restore units
+  for (auto &SU : SUnits)
+    SU = SUSavedCopy[SU.NodeNum];
+
+  return Schedule;
+}
+
+namespace llvm {
+std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
+                                              const ScheduleDAG &DAG) {
+  GCNILPScheduler S;
+  return S.schedule(BotRoots, DAG);
+}
+}

lib/Target/AMDGPU/GCNIterativeScheduler.h

 
 class GCNIterativeScheduler : public ScheduleDAGMILive {
   using BaseClass = ScheduleDAGMILive;
 
 public:
   enum StrategyKind {
     SCHEDULE_MINREGONLY,
     SCHEDULE_MINREGFORCED,
-    SCHEDULE_LEGACYMAXOCCUPANCY
+    SCHEDULE_LEGACYMAXOCCUPANCY,
+    SCHEDULE_ILP
   };
 
   GCNIterativeScheduler(MachineSchedContext *C,
                         StrategyKind S);
 
   void schedule() override;
 
   void enterRegion(MachineBasicBlock *BB,
protected:
   void scheduleRegion(Region &R, Range &&Schedule,
                       const GCNRegPressure &MaxRP = GCNRegPressure());
 
   unsigned tryMaximizeOccupancy(unsigned TargetOcc =
                                 std::numeric_limits<unsigned>::max());
 
   void scheduleLegacyMaxOccupancy(bool TryMaximizeOccupancy = true);
   void scheduleMinReg(bool force = false);
+  void scheduleILP(bool TryMaximizeOccupancy = true);
 
   void printRegions(raw_ostream &OS) const;
   void printSchedResult(raw_ostream &OS,
                         const Region *R,
                         const GCNRegPressure &RP) const;
   void printSchedRP(raw_ostream &OS,
                     const GCNRegPressure &Before,
                     const GCNRegPressure &After) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_AMDGPU_GCNITERATIVESCHEDULER_H

lib/Target/AMDGPU/GCNIterativeScheduler.cpp

 
 #define DEBUG_TYPE "machine-scheduler"
 
 namespace llvm {
 
 std::vector<const SUnit *> makeMinRegSchedule(ArrayRef<const SUnit *> TopRoots,
                                               const ScheduleDAG &DAG);
 
-} // end namespace llvm
+  std::vector<const SUnit*> makeGCNILPScheduler(ArrayRef<const SUnit*> BotRoots,
+    const ScheduleDAG &DAG);
+}
 
 // shim accessors for different order containers
 static inline MachineInstr *getMachineInstr(MachineInstr *MI) {
   return MI;
 }
 static inline MachineInstr *getMachineInstr(const SUnit *SU) {
   return SU->getInstr();
 }

 }
 #endif
 
 // DAG builder helper
 class GCNIterativeScheduler::BuildDAG {
   GCNIterativeScheduler &Sch;
   SmallVector<SUnit *, 8> TopRoots;
 
+  SmallVector<SUnit*, 8> BotRoots;
 public:
   BuildDAG(const Region &R, GCNIterativeScheduler &_Sch)
     : Sch(_Sch) {
     auto BB = R.Begin->getParent();
     Sch.BaseClass::startBlock(BB);
     Sch.BaseClass::enterRegion(BB, R.Begin, R.End, R.NumRegionInstrs);
 
     Sch.buildSchedGraph(Sch.AA, nullptr, nullptr, nullptr,
                         /*TrackLaneMask*/true);
     Sch.Topo.InitDAGTopologicalSorting();
-
-    SmallVector<SUnit *, 8> BotRoots;
     Sch.findRootsAndBiasEdges(TopRoots, BotRoots);
   }
 
   ~BuildDAG() {
     Sch.BaseClass::exitRegion();
     Sch.BaseClass::finishBlock();
   }
 
   ArrayRef<const SUnit *> getTopRoots() const {
     return TopRoots;
   }
+  ArrayRef<SUnit*> getBottomRoots() const {
+    return BotRoots;
+  }
 };
 
 class GCNIterativeScheduler::OverrideLegacyStrategy {
   GCNIterativeScheduler &Sch;
   Region &Rgn;
   std::unique_ptr<MachineSchedStrategy> SaveSchedImpl;
   GCNRegPressure SaveMaxRP;
 

 
 void GCNIterativeScheduler::finalizeSchedule() { // overriden
   if (Regions.empty())
     return;
   switch (Strategy) {
   case SCHEDULE_MINREGONLY: scheduleMinReg(); break;
   case SCHEDULE_MINREGFORCED: scheduleMinReg(true); break;
   case SCHEDULE_LEGACYMAXOCCUPANCY: scheduleLegacyMaxOccupancy(); break;
+  case SCHEDULE_ILP: scheduleILP(false); break;
   }
 }
 
 // Detach schedule from SUnits and interleave it with debug values.
 // Returned schedule becomes independent of DAG state.
 std::vector<MachineInstr*>
 GCNIterativeScheduler::detachSchedule(ScheduleRef Schedule) const {
   std::vector<MachineInstr*> Res;
if (!force && MaxPressure.less(ST, RP, TgtOcc))
       break;
 
     scheduleRegion(*R, MinSchedule, RP);
     DEBUG(printSchedResult(dbgs(), R, RP));
 
     MaxPressure = RP;
   }
 }
+
+///////////////////////////////////////////////////////////////////////////////
+// ILP scheduler port
+
+void GCNIterativeScheduler::scheduleILP(
+  bool TryMaximizeOccupancy) {
+  const auto &ST = MF.getSubtarget<SISubtarget>();
+  auto TgtOcc = ST.getOccupancyWithLocalMemSize(MF);
+
+  sortRegionsByPressure(TgtOcc);
+  auto Occ = Regions.front()->MaxPressure.getOccupancy(ST);
+
+  if (TryMaximizeOccupancy && Occ < TgtOcc)
+    Occ = tryMaximizeOccupancy(TgtOcc);
+
+  TgtOcc = std::min(Occ, TgtOcc);
+  DEBUG(dbgs() << "Scheduling using default scheduler, "
+    "target occupancy = " << TgtOcc << '\n');
+
+  for (auto R : Regions) {
+    BuildDAG DAG(*R, *this);
+    const auto ILPSchedule = makeGCNILPScheduler(DAG.getBottomRoots(), *this);
+
+    const auto RP = getSchedulePressure(*R, ILPSchedule);
+    DEBUG(printSchedRP(dbgs(), R->MaxPressure, RP));
+
+    if (RP.getOccupancy(ST) < TgtOcc) {
+      DEBUG(dbgs() << "Didn't fit into target occupancy O" << TgtOcc);
+      if (R->BestSchedule.get() &&
+        R->BestSchedule->MaxPressure.getOccupancy(ST) >= TgtOcc) {
+        DEBUG(dbgs() << ", scheduling minimal register\n");
+        scheduleBest(*R);
+      }
+    } else {
+      scheduleRegion(*R, ILPSchedule, RP);
+      DEBUG(printSchedResult(dbgs(), R, RP));
+    }
+  }
+}