Adjust MIScheduler to use ProcResource counts

[chill]

Summary

This fix allows the scheduler to take into account the number of
instances of each ProcResource specified. Previously a declaration in a
scheduler of ProcResource<1> would be treated identically to a
declaration of ProcResource<2>. This patch fixes that. Testsuite
fixes are included for schedulers that have changed.

[javed.absar]

Would it be possible to add a test case that highlights the problem you are solving e.g. take a processor that has multiple resources (e.g. two adders) and show that it now can use both resources in same cycle.

lib/CodeGen/MachineScheduler.cpp

1945 ↗

(On Diff #162169)

why Offset is uninitialized ?

[chill]

lib/CodeGen/MachineScheduler.cpp

1937 ↗

(On Diff #162169)

I would write it like:

/// Compute the next cycle at which the given processor resource can be
/// scheduled.  Returns (NextCycle, InstanceIDAssignedTo).
std::pair<unsigned, unsigned> SchedBoundary::
getNextResourceCycle(unsigned PIdx, unsigned ResCount, unsigned Cycles) {
  unsigned MinNextUnreserved = InvalidCycle;
  unsigned InstanceID = 0;
  unsigned StartIndex = ProcessorResourceList[PIdx];
  unsigned NumUnits = SchedModel->getProcResource(PIdx)->NumUnits;

  for (unsigned I = StartIndex, E = StartIndex + NumUnits;  I < E; ++I) {
    unsigned NextUnreserved =  getNextResourceCycleByInstance(I, Cycles);
    if (NextUnreserved < MinNextUnreserved) {
        InstanceID = I;
        MinNextUnreserved = NextUnreserved;
      }
  }
  return std::make_pair(MinNextUnreserved, InstanceID);
}

but YMMV.

[Jackson]

lib/CodeGen/MachineScheduler.cpp

1937 ↗

(On Diff #162169)

Where does InvalidCycle come from here?

[chill]

lib/CodeGen/MachineScheduler.cpp

1937 ↗

(On Diff #162169)

line 1817

[Jackson]

Thanks for the feedback. I have fixed up the getNextResourceCycle function and added a testcase.

[chill]

PIng?

[chill]

Ping?

[javed.absar]

test/CodeGen/ARM/proc_resouces_schedule.ll

1 ↗

(On Diff #163088)

The filename has a typo 'resouces'.
Also, it may be helpful to add a comment at the top of this file on what exactly is being tested.

[chill]

Taking over as Jackson's internship ended in the meantime.

[chill]

Updated regression tests.

[fhahn]

Do you have any benchmark data you could share with this patch? I am curious what the impact is and if there are any regressions.

llvm/include/llvm/CodeGen/MachineScheduler.h

671

This name is too generic I think. this is only relevant to ReservedCycles. Also it is basically a map, right?

llvm/include/llvm/CodeGen/TargetSchedule.h

119 ↗

(On Diff #192220)

Is there a benefit if adding this over just using getProcResource? Leaking the table may make future changes harder.

llvm/lib/CodeGen/MachineScheduler.cpp

1953

ResCount not used here? I think you can remove it, as you get it from the model in the function.

2014–2015

InstanceID unused?

2180

InstanceID only used with DEBUG?

2183

Can we convert the instanceID to a resource name?

llvm/test/CodeGen/ARM/proc-resource-sched.ll

16

The function is quite small, can you check the full schedule?

[andreadb]

llvm/include/llvm/CodeGen/MachineScheduler.h

671

I agree: the name should be improved.
ProcessorResourceList is only used to map processor resource identifiers to ReservedCycles indices. That being said, it is okay to have it as a small vector with size SchedModel->getNumProcResourceKinds().

llvm/include/llvm/CodeGen/TargetSchedule.h

119 ↗

(On Diff #192220)

+1.

I don't think it is really needed (see my other comment below).

llvm/lib/CodeGen/MachineScheduler.cpp

1911–1914

Instead of doing (Resources + i)->NumUnits, you should use
SchedModel->getProcResource(i) to ge the MCProcResourceDesc, and then access field NumUnits.

So, something like:

NumUnits += SchedModel->getProcResource(i)->NumUnits;

That way, you can get rid of the code at line 1924. You also don't need method getProcResourceTable().

1958–1959

We should probably enforce this constraint in the SubtargetEmitter and error out if a processor resource declares zero (or negative) units.

(In practice, none of the models available upstream declares a resource with zero units. Only the 'InvalidUnit' at index 0 defaults to having zero units).

[atrick]

I scanned the code. It seems reasonable to me. Thanks for all the other good review feedback.

[chill]

Thanks for the feedback. Here's an updated diff.

[chill]

In D51160#1442763, @fhahn wrote:

Do you have any benchmark data you could share with this patch? I am curious what the impact is and if there are any regressions.

No, I'm sorry, I don't have publishable benchmark results at the moment.

llvm/lib/CodeGen/MachineScheduler.cpp

2014–2015

Yes, it's unused, here and in one more place we care only for the cycle number.

llvm/test/CodeGen/ARM/proc-resource-sched.ll

16

I'm not sure what do you mean. The test tests the difference in the internal state of the scheduler, which does not necesarily results in different schedule. Perhaps I can make a bigger test case, but I'd rather not do it as it'll have the tendency to break with unrelated scheduler changes.

[chill]

llvm/lib/CodeGen/MachineScheduler.cpp

1958–1959

That would be for a separate patch, wouldn't it ?

[andreadb]

llvm/lib/CodeGen/MachineScheduler.cpp

1958–1959

Yes. That would be a follow-up patch.

You can commit this change since it is good (and it was already approved by @atrick ).

Thanks,
Andrea

llvm/include/llvm/CodeGen/MachineScheduler.h

private:
 
   // Is the scheduled region resource limited vs. latency limited.
   bool IsResourceLimited;
 
   // Record the highest cycle at which each resource has been reserved by a
   // scheduled instruction.
   SmallVector<unsigned, 16> ReservedCycles;
 
+  // For each PIdx, stores first index into ReservedCycles that corresponds to
+  // it.
+  SmallVector<unsigned, 16> ReservedCyclesIndex;
+
 #ifndef NDEBUG
   // Remember the greatest possible stall as an upper bound on the number of
   // times we should retry the pending queue because of a hazard.
   unsigned MaxObservedStall;
 #endif
 
 public:
   /// Pending queues extend the ready queues with the same ID and the
public:
 
   // Is the scheduled region resource limited vs. latency limited.
   bool isResourceLimited() const { return IsResourceLimited; }
 
   /// Get the difference between the given SUnit's ready time and the current
   /// cycle.
   unsigned getLatencyStallCycles(SUnit *SU);
 
-  unsigned getNextResourceCycle(unsigned PIdx, unsigned Cycles);
+  unsigned getNextResourceCycleByInstance(unsigned InstanceIndex,
+                                          unsigned Cycles);
+
+  std::pair<unsigned, unsigned> getNextResourceCycle(unsigned PIdx,
+                                                     unsigned Cycles);
 
   bool checkHazard(SUnit *SU);
 
   unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
 
   unsigned getOtherResourceCount(unsigned &OtherCritIdx);
 
   void releaseNode(SUnit *SU, unsigned ReadyCycle);

llvm/lib/CodeGen/MachineScheduler.cpp

void SchedBoundary::reset() {
   MinReadyCycle = std::numeric_limits<unsigned>::max();
   ExpectedLatency = 0;
   DependentLatency = 0;
   RetiredMOps = 0;
   MaxExecutedResCount = 0;
   ZoneCritResIdx = 0;
   IsResourceLimited = false;
   ReservedCycles.clear();
+  ReservedCyclesIndex.clear();
 #ifndef NDEBUG
   // Track the maximum number of stall cycles that could arise either from the
   // latency of a DAG edge or the number of cycles that a processor resource is
   // reserved (SchedBoundary::ReservedCycles).
   MaxObservedStall = 0;
 #endif
   // Reserve a zero-count for invalid CritResIdx.
   ExecutedResCounts.resize(1);

 
 void SchedBoundary::
 init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
   reset();
   DAG = dag;
   SchedModel = smodel;
   Rem = rem;
   if (SchedModel->hasInstrSchedModel()) {
-    ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds());
-    ReservedCycles.resize(SchedModel->getNumProcResourceKinds(), InvalidCycle);
+    unsigned ResourceCount = SchedModel->getNumProcResourceKinds();
+    ReservedCyclesIndex.resize(ResourceCount);
+    ExecutedResCounts.resize(ResourceCount);
+    unsigned NumUnits = 0;
+
+    for (unsigned i = 0; i < ResourceCount; ++i) {
+      ReservedCyclesIndex[i] = NumUnits;
+      NumUnits += SchedModel->getProcResource(i)->NumUnits;
+    }
+
+    ReservedCycles.resize(NumUnits, InvalidCycle);
   }
 }
 
 /// Compute the stall cycles based on this SUnit's ready time. Heuristics treat
 /// these "soft stalls" differently than the hard stall cycles based on CPU
 /// resources and computed by checkHazard(). A fully in-order model
 /// (MicroOpBufferSize==0) will not make use of this since instructions are not
 /// available for scheduling until they are ready. However, a weaker in-order
 /// model may use this for heuristics. For example, if a processor has in-order
 /// behavior when reading certain resources, this may come into play.
 unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
   if (!SU->isUnbuffered)
     return 0;
 
   unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
   if (ReadyCycle > CurrCycle)
     return ReadyCycle - CurrCycle;
   return 0;
 }
 
-/// Compute the next cycle at which the given processor resource can be
-/// scheduled.
-unsigned SchedBoundary::
-getNextResourceCycle(unsigned PIdx, unsigned Cycles) {
-  unsigned NextUnreserved = ReservedCycles[PIdx];
+/// Compute the next cycle at which the given processor resource unit
+/// can be scheduled.
+unsigned SchedBoundary::getNextResourceCycleByInstance(unsigned InstanceIdx,
+                                                       unsigned Cycles) {
+  unsigned NextUnreserved = ReservedCycles[InstanceIdx];
   // If this resource has never been used, always return cycle zero.
   if (NextUnreserved == InvalidCycle)
     return 0;
   // For bottom-up scheduling add the cycles needed for the current operation.
   if (!isTop())
     NextUnreserved += Cycles;
   return NextUnreserved;
 }
 
+/// Compute the next cycle at which the given processor resource can be
+/// scheduled.  Returns the next cycle and the index of the processor resource
+/// instance in the reserved cycles vector.
+std::pair<unsigned, unsigned>
+SchedBoundary::getNextResourceCycle(unsigned PIdx, unsigned Cycles) {
+  unsigned MinNextUnreserved = InvalidCycle;
+  unsigned InstanceIdx = 0;
+  unsigned StartIndex = ReservedCyclesIndex[PIdx];
+  unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits;
+  assert(NumberOfInstances > 0 &&
+         "Cannot have zero instances of a ProcResource");
+
+  for (unsigned I = StartIndex, End = StartIndex + NumberOfInstances; I < End;
+       ++I) {
+    unsigned NextUnreserved = getNextResourceCycleByInstance(I, Cycles);
+    if (MinNextUnreserved > NextUnreserved) {
+      InstanceIdx = I;
+      MinNextUnreserved = NextUnreserved;
+    }
+  }
+  return std::make_pair(MinNextUnreserved, InstanceIdx);
+}
+
 /// Does this SU have a hazard within the current instruction group.
 ///
 /// The scheduler supports two modes of hazard recognition. The first is the
 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
 /// supports highly complicated in-order reservation tables
 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
 ///
 /// The second is a streamlined mechanism that checks for hazards based on
bool SchedBoundary::checkHazard(SUnit *SU) {
 
   if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
     const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
     for (const MCWriteProcResEntry &PE :
           make_range(SchedModel->getWriteProcResBegin(SC),
                      SchedModel->getWriteProcResEnd(SC))) {
       unsigned ResIdx = PE.ProcResourceIdx;
       unsigned Cycles = PE.Cycles;
-      unsigned NRCycle = getNextResourceCycle(ResIdx, Cycles);
+      unsigned NRCycle, InstanceIdx;
+      std::tie(NRCycle, InstanceIdx) = getNextResourceCycle(ResIdx, Cycles);
       if (NRCycle > CurrCycle) {
 #ifndef NDEBUG
         MaxObservedStall = std::max(Cycles, MaxObservedStall);
 #endif
         LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") "
-                          << SchedModel->getResourceName(ResIdx) << "="
-                          << NRCycle << "c\n");
+                          << SchedModel->getResourceName(ResIdx)
+                          << '[' << InstanceIdx - ReservedCyclesIndex[ResIdx]  << ']'
+                          << "=" << NRCycle << "c\n");
         return true;
       }
     }
   }
   return false;
 }
 
 // Find the unscheduled node in ReadySUs with the highest latency.
countResource(unsigned PIdx, unsigned Cycles, unsigned NextCycle) {
   if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {
     ZoneCritResIdx = PIdx;
     LLVM_DEBUG(dbgs() << "  *** Critical resource "
                       << SchedModel->getResourceName(PIdx) << ": "
                       << getResourceCount(PIdx) / SchedModel->getLatencyFactor()
                       << "c\n");
   }
   // For reserved resources, record the highest cycle using the resource.
-  unsigned NextAvailable = getNextResourceCycle(PIdx, Cycles);
+  unsigned NextAvailable, InstanceIdx;
+  std::tie(NextAvailable, InstanceIdx) = getNextResourceCycle(PIdx, Cycles);
   if (NextAvailable > CurrCycle) {
     LLVM_DEBUG(dbgs() << "  Resource conflict: "
-                      << SchedModel->getProcResource(PIdx)->Name
+                      << SchedModel->getResourceName(PIdx)
+                      << '[' << InstanceIdx - ReservedCyclesIndex[PIdx]  << ']'
                       << " reserved until @" << NextAvailable << "\n");
   }
   return NextAvailable;
 }
 
 /// Move the boundary of scheduled code by one SUnit.
 void SchedBoundary::bumpNode(SUnit *SU) {
   // Update the reservation table.
if (SU->hasReservedResource) {
       // For top-down scheduling, this is the cycle in which we schedule this
       // instruction plus the number of cycles the operations reserves the
       // resource. For bottom-up is it simply the instruction's cycle.
       for (TargetSchedModel::ProcResIter
              PI = SchedModel->getWriteProcResBegin(SC),
              PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
         unsigned PIdx = PI->ProcResourceIdx;
         if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {
+          unsigned ReservedUntil, InstanceIdx;
+          std::tie(ReservedUntil, InstanceIdx) = getNextResourceCycle(PIdx, 0);
           if (isTop()) {
-            ReservedCycles[PIdx] =
-              std::max(getNextResourceCycle(PIdx, 0), NextCycle + PI->Cycles);
-          }
-          else
-            ReservedCycles[PIdx] = NextCycle;
+            ReservedCycles[InstanceIdx] =
+                std::max(ReservedUntil, NextCycle + PI->Cycles);
+          } else
+            ReservedCycles[InstanceIdx] = NextCycle;
         }
       }
     }
   }
   // Update ExpectedLatency and DependentLatency.
   unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
   unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
   if (SU->getDepth() > TopLatency) {

llvm/test/CodeGen/AArch64/misched-fusion-aes.ll

entry:
   %in3 = load <16 x i8>, <16 x i8>* %p3, align 16
   %aesmc2= call <16 x i8> @llvm.aarch64.crypto.aesmc(<16 x i8> %aese2) #2
   %aese3 = call <16 x i8> @llvm.aarch64.crypto.aese(<16 x i8> %aesmc2, <16 x i8> %in3) #2
   store <16 x i8> %aese3, <16 x i8>* %x5, align 16
   ret void
 
 ; CHECK-LABEL: aes_load_store:
 ; CHECK: aese [[VA:v[0-7].16b]], {{v[0-7].16b}}
-; CHECK-NEXT: aesmc [[VA]], [[VA]]
+; aese and aesmc are described to share a unit, hence won't be scheduled on the
+; same cycle and the scheduler can find another instruction to place inbetween
+; CHECK: aesmc [[VA]], [[VA]]
 ; CHECK: aese [[VB:v[0-7].16b]], {{v[0-7].16b}}
 ; CHECK-NEXT: aesmc [[VB]], [[VB]]
 ; CHECK-NOT: aesmc
 }

llvm/test/CodeGen/ARM/proc-resource-sched.ll

+; RUN: llc -mtriple=arm-eabi -mcpu=cortex-r52 -debug-only=machine-scheduler %s -o - 2>&1 | FileCheck %s --check-prefix=CHECK-R52
+; REQUIRES: asserts
+
+; source_filename = "sched-2.c"
+target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+
+define dso_local i32 @f(i32 %a, i32 %b, i32 %c, i32 %d) local_unnamed_addr {
+entry:
+  %add = add nsw i32 %b, %a
+  %add1 = add nsw i32 %d, %c
+  %div = sdiv i32 %add, %add1
+  ret i32 %div
+}
+
+; Cortex-R52 model describes it as dual-issue with two integer ALUs
+; It should be able to issue the two additions in the same cycle.
+; CHECK-R52: MI Scheduling
+; CHECK-R52: Cycle: 14
+; CHECK-R52: Scheduling SU(5) %5:gpr = nsw ADDrr %3:gpr, %2:gpr, 14, $noreg, $noreg
+; CHECK-R52: Scheduling SU(4) %4:gpr = nsw ADDrr %1:gpr, %0:gpr, 14, $noreg, $noreg
+; CHECK-R52: Cycle: 15