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

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 = 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) {

test/CodeGen/ARM/proc_resouces_schedule.ll

+; RUN: llc -mtriple=arm-linux-none-eabi -O3 -mcpu=cortex-r52 --debug 2>&1 < %s | FileCheck %s
+
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+; CHECK: *** Max MOps {{[0-9]}} at cycle {{[0-9]+}}
+
+define dso_local void @test(i32* %res, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %x, i32 %y, i32 %z) #0 {
+entry:
+  %res.addr = alloca i32*, align 4
+  %a.addr = alloca i32, align 4
+  %b.addr = alloca i32, align 4
+  %c.addr = alloca i32, align 4
+  %d.addr = alloca i32, align 4
+  %e.addr = alloca i32, align 4
+  %x.addr = alloca i32, align 4
+  %y.addr = alloca i32, align 4
+  %z.addr = alloca i32, align 4
+  store i32* %res, i32** %res.addr, align 4
+  store i32 %a, i32* %a.addr, align 4
+  store i32 %b, i32* %b.addr, align 4
+  store i32 %c, i32* %c.addr, align 4
+  store i32 %d, i32* %d.addr, align 4
+  store i32 %e, i32* %e.addr, align 4
+  store i32 %x, i32* %x.addr, align 4
+  store i32 %y, i32* %y.addr, align 4
+  store i32 %z, i32* %z.addr, align 4
+  %0 = load i32, i32* %a.addr, align 4
+  %1 = load i32, i32* %b.addr, align 4
+  %add = add nsw i32 %0, %1
+  %2 = load i32, i32* %c.addr, align 4
+  %add1 = add nsw i32 %add, %2
+  %3 = load i32, i32* %x.addr, align 4
+  %add2 = add nsw i32 %add1, %3
+  %4 = load i32, i32* %y.addr, align 4
+  %add3 = add nsw i32 %add2, %4
+  %5 = load i32, i32* %z.addr, align 4
+  %add4 = add nsw i32 %add3, %5
+  %6 = load i32*, i32** %res.addr, align 4
+  %arrayidx = getelementptr inbounds i32, i32* %6, i32 1
+  store i32 %add4, i32* %arrayidx, align 4
+  %7 = load i32, i32* %c.addr, align 4
+  %8 = load i32, i32* %d.addr, align 4
+  %add5 = add nsw i32 %7, %8
+  %9 = load i32, i32* %e.addr, align 4
+  %add6 = add nsw i32 %add5, %9
+  %10 = load i32, i32* %x.addr, align 4
+  %add7 = add nsw i32 %add6, %10
+  %11 = load i32, i32* %y.addr, align 4
+  %add8 = add nsw i32 %add7, %11
+  %12 = load i32, i32* %z.addr, align 4
+  %add9 = add nsw i32 %add8, %12
+  %13 = load i32*, i32** %res.addr, align 4
+  %arrayidx10 = getelementptr inbounds i32, i32* %13, i32 2
+  store i32 %add9, i32* %arrayidx10, align 4
+  ret void
+}
+

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: vldr
+; CHECK-NEXT: vldr
+; CHECK-NEXT: vmul
+; 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: vadd
 ; CHECK-NEXT: vadd