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 ↗

(On Diff #192220)

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

1974 ↗

(On Diff #192220)

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

2036 ↗

(On Diff #192220)

InstanceID unused?

2202 ↗

(On Diff #192220)

InstanceID only used with DEBUG?

2207 ↗

(On Diff #192220)

Can we convert the instanceID to a resource name?

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

15 ↗

(On Diff #192220)

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

[andreadb]

llvm/include/llvm/CodeGen/MachineScheduler.h

686 ↗

(On Diff #192220)

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

1930–1933 ↗

(On Diff #192220)

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 ↗

(On Diff #192220)

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 ↗

(On Diff #192220)

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 ↗

(On Diff #192220)

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 ↗

(On Diff #192220)

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

[andreadb]

llvm/lib/CodeGen/MachineScheduler.cpp

1979–1980 ↗

(On Diff #192220)

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/trunk/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/trunk/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/trunk/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/trunk/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