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

686

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

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

llvm/lib/CodeGen/MachineScheduler.cpp

1974

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

2036

InstanceID unused?

2202

InstanceID only used with DEBUG?

2207

Can we convert the instanceID to a resource name?

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

15

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

[andreadb]

llvm/include/llvm/CodeGen/MachineScheduler.h

686

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

+1.

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

llvm/lib/CodeGen/MachineScheduler.cpp

1930–1933

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().

1979–1980

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

2036

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

15

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

1979–1980

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

[andreadb]

llvm/lib/CodeGen/MachineScheduler.cpp

1979–1980

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> ProcessorResourceList;
+
 #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 InstanceCount,
+                         unsigned Cycles);
 
   bool checkHazard(SUnit *SU);
 
   unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
 
   unsigned getOtherResourceCount(unsigned &OtherCritIdx);
 
   void releaseNode(SUnit *SU, unsigned ReadyCycle);

llvm/include/llvm/CodeGen/TargetSchedule.h

unsigned getNumProcResourceKinds() const {
     return SchedModel.getNumProcResourceKinds();
   }
 
   /// Get a processor resource by ID for convenience.
   const MCProcResourceDesc *getProcResource(unsigned PIdx) const {
     return SchedModel.getProcResource(PIdx);
   }
 
+  /// Get the processor resource table.
+  const MCProcResourceDesc *getProcResourceTable() const {
+    return SchedModel.ProcResourceTable;
+  }
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   const char *getResourceName(unsigned PIdx) const {
     if (!PIdx)
       return "MOps";
     return SchedModel.getProcResource(PIdx)->Name;
   }
 #endif
 

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();
+  ProcessorResourceList.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);
+    const MCProcResourceDesc *Resources = SchedModel->getProcResourceTable();
+    unsigned ResourceCount = SchedModel->getNumProcResourceKinds();
+    ProcessorResourceList.resize(ResourceCount);
+    ExecutedResCounts.resize(ResourceCount);
+    unsigned NumUnits = 0;
+
+    for (unsigned i = 0; i < ResourceCount; ++i) {
+      ProcessorResourceList[i] = NumUnits;
+      NumUnits += (Resources + 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.
+
+/// Compute the next cycle at which the given processor resource unit
+/// can be scheduled.
 unsigned SchedBoundary::
-getNextResourceCycle(unsigned PIdx, unsigned Cycles) {
-  unsigned NextUnreserved = ReservedCycles[PIdx];
+getNextResourceCycleByInstance(unsigned InstanceIndex, unsigned Cycles) {
+  unsigned NextUnreserved = ReservedCycles[InstanceIndex];
   // 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 (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 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) {
+      InstanceID = I;
+      MinNextUnreserved = NextUnreserved;
+    }
+  }
+  return std::make_pair(MinNextUnreserved, InstanceID);
+}
+
 /// 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 ResCount = SchedModel->getProcResource(ResIdx)->NumUnits;
       unsigned Cycles = PE.Cycles;
-      unsigned NRCycle = getNextResourceCycle(ResIdx, Cycles);
+      unsigned NRCycle, InstanceID;
+      std::tie(NRCycle, InstanceID) =
+        getNextResourceCycle(ResIdx, ResCount, Cycles);
       if (NRCycle > CurrCycle) {
 #ifndef NDEBUG
         MaxObservedStall = std::max(Cycles, MaxObservedStall);
 #endif
         LLVM_DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") "
                           << SchedModel->getResourceName(ResIdx) << "="
                           << NRCycle << "c\n");
         return true;
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 ResCount = SchedModel->getProcResource(PIdx)->NumUnits;
+  unsigned NextAvailable, InstanceID;
+  std::tie(NextAvailable, InstanceID) =
+    getNextResourceCycle(PIdx, ResCount, Cycles);
   if (NextAvailable > CurrCycle) {
     LLVM_DEBUG(dbgs() << "  Resource conflict: "
                       << SchedModel->getProcResource(PIdx)->Name
+                      << " instance " << InstanceID
                       << " 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 ResCount = SchedModel->getProcResource(PIdx)->NumUnits;
+          unsigned ReservedUntil, InstanceIndex;
+          std::tie(ReservedUntil, InstanceIndex) =
+            getNextResourceCycle(PIdx, ResCount, 0);
           if (isTop()) {
-            ReservedCycles[PIdx] =
-              std::max(getNextResourceCycle(PIdx, 0), NextCycle + PI->Cycles);
+            ReservedCycles[InstanceIndex] =
+              std::max(ReservedUntil, NextCycle + PI->Cycles);
           }
           else
-            ReservedCycles[PIdx] = NextCycle;
+            ReservedCycles[InstanceIndex] = 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