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

why Offset is uninitialized ?

[chill]

lib/CodeGen/MachineScheduler.cpp

1937

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

Where does InvalidCycle come from here?

[chill]

lib/CodeGen/MachineScheduler.cpp

1937

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

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);

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
 

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 = 0;
+  unsigned InstanceID = 0;
+  bool ResourceConsidered = false;
+  unsigned ResourceInstanceStartIndex = ProcessorResourceList[PIdx];
+  unsigned NumberOfInstances = SchedModel->getProcResource(PIdx)->NumUnits;
+
+  for (unsigned Offset; Offset < NumberOfInstances; ++Offset) {
+    unsigned InstanceIndex = ResourceInstanceStartIndex + Offset;
+    unsigned NextUnreserved =
+      getNextResourceCycleByInstance(InstanceIndex,
+                                     Cycles);
+    if (ResourceConsidered) {
+      if (MinNextUnreserved > NextUnreserved) {
+        InstanceID = InstanceIndex;
+        MinNextUnreserved = NextUnreserved;
+      }
+    } else {
+      ResourceConsidered = true;
+      MinNextUnreserved = NextUnreserved;
+      InstanceID = InstanceIndex;
+    }
+  }
+  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) {

test/CodeGen/AArch64/ldst-paired-aliasing.ll

 ; RUN: llc -mcpu cortex-a53 < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-i128:128-n8:16:32:64-S128"
 target triple = "aarch64--linux-gnu"
 
 declare void @f(i8*, i8*)
 declare void @f2(i8*, i8*)
 declare void @_Z5setupv()
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i1) #3
 
 define i32 @main() local_unnamed_addr #1 {
 ; Make sure the stores happen in the correct order (the exact instructions could change).
 ; CHECK-LABEL: main:
 ; CHECK: stp xzr, xzr, [sp, #72]
 ; CHECK: str w9, [sp, #80]
 ; CHECK: str q0, [sp, #48]
-; CHECK: ldr w8, [sp, #48]
 ; CHECK: str q0, [sp, #64]
+; CHECK: ldr w8, [sp, #48]
 
 for.body.lr.ph.i.i.i.i.i.i63:
   %b1 = alloca [10 x i32], align 16
   %x0 = bitcast [10 x i32]* %b1 to i8*
   %b2 = alloca [10 x i32], align 16
   %x1 = bitcast [10 x i32]* %b2 to i8*
   tail call void @_Z5setupv()
   %x2 = getelementptr inbounds [10 x i32], [10 x i32]* %b1, i64 0, i64 6

test/CodeGen/ARM/saxpy10-a9.ll

 ; RUN: llc < %s -mtriple=thumbv7-apple-ios7.0.0 -float-abi=hard -mcpu=cortex-a9 -misched-postra -enable-misched -pre-RA-sched=source -scheditins=false | FileCheck %s
 ;
 ; Test MI-Sched suppory latency based stalls on in in-order pipeline
 ; using the new machine model.
 
 target datalayout = "e-p:32:32:32-i1:8:32-i8:8:32-i16:16:32-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:32:64-v128:32:128-a0:0:32-n32-S32"
 
 ; Don't be too strict with the top of the schedule, but most of it
 ; should be nicely pipelined.
 ;
 ; CHECK: saxpy10:
-; CHECK: vldr
-; CHECK: vldr
-; CHECK: vldr
-; CHECK: vldr
-; CHECK: vldr
+; CHECK: vmov
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vmul
-; CHECK-NEXT: vadd
-; CHECK-NEXT: vadd
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vldr
-; CHECK-NEXT: vadd
-; CHECK-NEXT: vadd
 ; CHECK-NEXT: vmul
 ; CHECK-NEXT: vldr
-; CHECK-NEXT: vadd
+; CHECK-NEXT: vldr
 ; CHECK-NEXT: vadd
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vmul
+; CHECK-NEXT: vadd
 ; CHECK-NEXT: vldr
+; CHECK-NEXT: vmul
 ; CHECK-NEXT: vadd
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vadd
+; CHECK-NEXT: vadd
+; CHECK-NEXT: vldr
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vmul
 ; CHECK-NEXT: vadd
-; CHECK-NEXT: vldr
 ; CHECK-NEXT: vadd
 ; CHECK-NEXT: vldr
+; CHECK-NEXT: vldr
 ; CHECK-NEXT: vmul
 ; CHECK-NEXT: vadd
-; CHECK-NEXT: vldr
 ; CHECK-NEXT: vadd
 ; CHECK-NEXT: vldr
+; CHECK-NEXT: vldr
 ; CHECK-NEXT: vmul
 ; CHECK-NEXT: vadd
+; CHECK-NEXT: vadd
+; CHECK-NEXT: vldr
 ; CHECK-NEXT: vldr
+; CHECK-NEXT: vmul
 ; CHECK-NEXT: vadd
+; CHECK-NEXT: vadd
+; CHECK-NEXT: vldr
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vmul
 ; CHECK-NEXT: vadd
+; CHECK-NEXT: vadd
+; CHECK-NEXT: vldr
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vmul
 ; CHECK-NEXT: vadd
+; CHECK-NEXT: vadd
 ; CHECK-NEXT: vldr
 ; CHECK-NEXT: vadd
 ; CHECK-NEXT: vadd
 ; CHECK-NEXT: vadd
 ; CHECK-NEXT: vmov
 ; CHECK-NEXT: bx
 ;
 ; This accumulates a sum rather than storing each result.