Improve machine schedulers for in-order processors

[javed.absar]

Summary

This patch enables schedulers for in-order processors to specify instructions that
cannot be issued with any other instructions.

Schedulers for such sub-targets can now attach ‘let SingleIssue = 1; // single issue ‘
to any general sched class or individual instruction. The scheduler then does not
allow those instructions to be issued in same cycle with any other instruction.
In this way, the scheduler models more accurately the real pipeline behavior.
Some partial out-of-order processors may also benefit from this.

[MatzeB]

Can't you already get this effect with BufferSize = 0 in a ProcResource?

[javed.absar]

Hi Matthias:

The single-issue restriction is on the instruction and not a limitation of the ProcResource e.g. for some processor, a load using load/store unit may be allowed dual-issue, but VLDx using the same load/store unit may not be allowed to dual-issue.

[atrick]

I think what Matthias was getting at is that you can add a new ProcResource to model issue constraints. If you have a dual issue machine then any instruction that can't be grouped would simply consume both issue resources. Another option might be to use the begin/end group flags.

A SingleIssue flag seems like special casing a problem that needs a general solution.

[atrick]

That said, if there are multiple target maintainers who think adding a special SingleIssue case would be much better than the alternatives, then it may be worth adding.

[MatzeB]

The single-issue restriction is on the instruction and not a limitation of the ProcResource e.g. for some processor, a load using load/store unit may be allowed dual-issue, but VLDx using the same load/store unit may not be allowed to dual-issue.

I guess this could still be modeled by making the instruction occupy every processor resource. So I was wondering whether we need the extension of the scheduling model.

In D30744#696124, @atrick wrote:

That said, if there are multiple target maintainers who think adding a special SingleIssue case would be much better than the alternatives, then it may be worth adding.

We could also make the SingleIssue flag syntactic sugar so tablegen adds all available proc resources to the instruction.

[javed.absar]

In D30744#696106, @atrick wrote:

I think what Matthias was getting at is that you can add a new ProcResource to model issue constraints. If you have a dual issue machine then any instruction that can't be grouped would simply consume both issue resources. Another option might be to use the begin/end group flags.

A SingleIssue flag seems like special casing a problem that needs a general solution.

For those of us quite familiar with the scheduler, using your suggested approach would indeed be a workaround. However, for those not so familiar, but wanting to use machine-scheduler to model their sub-target, the natural way to see ProcResource is as a resource (to do something e.g. perform an add). Using resource to impose restriction on instructions is bit counter-intuitive, and would not occur naturally at first. The sad consequence is - this aspect of the pipeline would not be properly or at all modeled.

In D30744#696136, @MatzeB wrote:

I guess this could still be modeled by making the instruction occupy every processor resource. So I was wondering whether we need the extension of the scheduling model.

Good idea. Unfortunately a syntatic-sugar that adds 'every processor resource' would not work. For example, if div is not-pipelined and is in execution; then an instruction X that does not need UniDiv but is single issue cannot be issued and has to wait for div to finish.
Besides, workarounds destroy simplicity/elegance and having a straightforward bit 'isSingleIssue' that is simple to interpret for anyone and does exactly what it says, would possibly be better.

[atrick]

Separate processor resources should be defined to model issue resources rather than trying to work around it by consuming functional units. The processor resources were always intended to be used for both issue resources and functional units. It just isn't well documented or easily discoverable. It might makes sense to have either a single issue flag or a separate list of issue resources in the tablegen machine model. My argument is that the scheduler itself already supports this functionality.

There at three ways this feature is already generally supported by the scheduler's machine model:

1. Begin/EndGroup.

This feature was added to model issue constraints that were too awkward to model with resources. It's the most straightforward way to model single issue. Adding syntactic sugar to tablegen's machine model should be trivial.

2. Issue resources

Define a new type of processor resource with N units. A single-issue instructions takes N unit to issue. This was an intended use of the machine model. The scheduler will model it with the issue counter.

3. Hardware ports.

x86 models "issue" ports this way.
e.g. def IssueSlots : ProcResGroup<[Slot0, Slot1]>

It was designed to handle micro-ops, so it's slightly misleading. A single-issue instruction on a dual issue machine would simply use both issue slots. Other instructions would use the IssueSlots group. The scheduler models this with a bit for each port.

[javed.absar]

In D30744#696730, @atrick wrote:

This feature was added to model issue constraints that were too awkward to model with resources. It's the most straightforward way to model single issue. Adding syntactic sugar to tablegen's machine model should be trivial.

Can you please elaborate on this a bit so I can try to develop a patch to add this. Thanks.

[javed.absar]

Hi Andrew/Matthias:
Would having a "SingleIssue" bit flag, as this patch proposes, be a good user option, even though I agree other workarounds can achieve same effect.
Thanks.

[atrick]

I think a SingleIssue flag would be a good user option. Representing such a flag in the tables generated by the machine model (MCSchedClassDesc) would be redundant. Either begin/endgroup already does the same thing, or it's a bug that should be fixed.

[atrick]

I just looked at the MachineScheduler implementation. I see this TODO:
/// TODO: Also check whether the SU must start a new group.

So, I think your patch is necessary except:

• The SubtargetEmitter can simply set the begin/end group flags for SingleIssue

• Instead of adding an isSingleIssue() API to TargetSchedule, you should add mustBeginGroup() and mustEndGroup() that checks the existing bits in MCSchedClassDesc.

• In the scheduler, mustBeginGroup() is a hazard if CurMOps > 0 when isTop() is true. Similarly, mustEndGroup() is the same hazard for !isTop().

• Your patch needs to handle isTop() && mustEndGroup(); likewise, !isTop() && mustBeginGroup() by calling bumpCycle(++NextCycle). Do this just after setting CurrMOps at CurrMOps += IncMOps, and just before checking the MOps hazard at while (CurrMOps >= SchedModel->getIssueWidth()). That obviously needs to be commented: "Bump the cycle count for issue group constraints. This must be done after NextCycle has been adjust for all other stalls. Calling bumpCycle(X) with reduces CurrMOps by one issue group and sets currCycle to X."

Your current implementation of isSingleIssue is actually only half the solution. Implementing the begin/end group bits will make it complete.

[javed.absar]

Hi Andrew:
Thanks for the help. I have made the changes as you suggested (unless I misunderstood some parts). Please have a look.
Thanks a lot.
Javed

[javed.absar]

Ping.

[atrick]

Thanks.

I don't think you need the SingleIssue flag in MCSchedule.h any more.

Also, I don't see the hazard checker logic yet. I think you still need to so this:

• In the scheduler, mustBeginGroup() is a hazard if CurMOps > 0 when isTop() is true. Similarly, mustEndGroup() is the same hazard for !isTop().

It looks like only half the logic is there now--the part where you bump the cycle when finishing a group. Maybe you need a better test case to exercise the hazard checking logic?

[javed.absar]

Hi Andrew:

You are right, I had missed out the hazard part. Have fixed things now. Please have a look if it is ok now.
Thanks
Javed

[atrick]

That looks good. But this version of the patch no longer has the SingleIssue flag support in the SubtargetEmitter. I thought you wanted that so the feature was more self-documenting. Your previous implementation looked ok to me. I just don't think you need any flag in the implementation of the model (MCSchedule.h).

[javed.absar]

Thanks Andrew. OK, I have added back 'SingleIssue' as syntactic sugar, but not in model, as recommended (if I got you right).
Best Regards, Javed.

[atrick]

LGTM. I think you should comment in TargetSchedule.td that SingleIssue is an alias for Begin/EndGroup.

llvm/trunk/include/llvm/CodeGen/TargetSchedule.h

public:
   }
 
   /// \brief Identify the processor corresponding to the current subtarget.
   unsigned getProcessorID() const { return SchedModel.getProcessorID(); }
 
   /// \brief Maximum number of micro-ops that may be scheduled per cycle.
   unsigned getIssueWidth() const { return SchedModel.IssueWidth; }
 
+  /// \brief Return true if new group must begin.
+  bool mustBeginGroup(const MachineInstr *MI,
+                          const MCSchedClassDesc *SC = nullptr) const;
+  /// \brief Return true if current group must end.
+  bool mustEndGroup(const MachineInstr *MI,
+                          const MCSchedClassDesc *SC = nullptr) const;
+
   /// \brief Return the number of issue slots required for this MI.
   unsigned getNumMicroOps(const MachineInstr *MI,
                           const MCSchedClassDesc *SC = nullptr) const;
 
   /// \brief Get the number of kinds of resources for this target.
   unsigned getNumProcResourceKinds() const {
     return SchedModel.getNumProcResourceKinds();
   }
#endif
   /// If UseDefaultDefLatency is false and no new machine sched model is
   /// present this method falls back to TII->getInstrLatency with an empty
   /// instruction itinerary (this is so we preserve the previous behavior of the
   /// if converter after moving it to TargetSchedModel).
   unsigned computeInstrLatency(const MachineInstr *MI,
                                bool UseDefaultDefLatency = true) const;
   unsigned computeInstrLatency(unsigned Opcode) const;
 
+
   /// \brief Output dependency latency of a pair of defs of the same register.
   ///
   /// This is typically one cycle.
   unsigned computeOutputLatency(const MachineInstr *DefMI, unsigned DefIdx,
                                 const MachineInstr *DepMI) const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_TARGETSCHEDULE_H

llvm/trunk/include/llvm/Target/TargetSchedule.td

class ProcWriteResources<list<ProcResourceKind> resources> {
   list<int> ResourceCycles = [];
   int Latency = 1;
   int NumMicroOps = 1;
   bit BeginGroup = 0;
   bit EndGroup = 0;
   // Allow a processor to mark some scheduling classes as unsupported
   // for stronger verification.
   bit Unsupported = 0;
+  // Allow a processor to mark some scheduling classes as single-issue.
+  // SingleIssue is an alias for Begin/End Group.
+  bit SingleIssue = 0;
   SchedMachineModel SchedModel = ?;
 }
 
 // Define the resources and latency of a SchedWrite. This will be used
 // directly by targets that have no itinerary classes. In this case,
 // SchedWrite is defined by the target, while WriteResources is
 // defined by the subtarget, and maps the SchedWrite to processor
 // resources.

llvm/trunk/lib/CodeGen/MachineScheduler.cpp

DEBUG(
     if (EntrySU.getInstr() != nullptr)
       EntrySU.dumpAll(this);
     for (const SUnit &SU : SUnits) {
       SU.dumpAll(this);
       if (ShouldTrackPressure) {
         dbgs() << "  Pressure Diff      : ";
         getPressureDiff(&SU).dump(*TRI);
       }
+      dbgs() << "  Single Issue       : ";
+      if (SchedModel.mustBeginGroup(SU.getInstr()) &&
+         SchedModel.mustEndGroup(SU.getInstr()))
+        dbgs() << "true;";
+      else
+        dbgs() << "false;";
       dbgs() << '\n';
     }
     if (ExitSU.getInstr() != nullptr)
       ExitSU.dumpAll(this);
   );
   if (ViewMISchedDAGs) viewGraph();
 
   // Initialize ready queues now that the DAG and priority data are finalized.

 /// can dispatch per cycle.
 ///
 /// TODO: Also check whether the SU must start a new group.
 bool SchedBoundary::checkHazard(SUnit *SU) {
   if (HazardRec->isEnabled()
       && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) {
     return true;
   }
+
   unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
   if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {
     DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") uops="
           << SchedModel->getNumMicroOps(SU->getInstr()) << '\n');
     return true;
   }
+
+  if (CurrMOps > 0 &&
+      ((isTop() && SchedModel->mustBeginGroup(SU->getInstr())) ||
+       (!isTop() && SchedModel->mustEndGroup(SU->getInstr())))) {
+    DEBUG(dbgs() << "  hazard: SU(" << SU->NodeNum << ") must "
+                 << (isTop()? "begin" : "end") << " group\n");
+    return true;
+  }
+
   if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
     const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
     for (TargetSchedModel::ProcResIter
            PI = SchedModel->getWriteProcResBegin(SC),
            PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
       unsigned NRCycle = getNextResourceCycle(PI->ProcResourceIdx, PI->Cycles);
       if (NRCycle > CurrCycle) {
 #ifndef NDEBUG
IsResourceLimited =
       (int)(getCriticalCount() - (getScheduledLatency() * LFactor))
       > (int)LFactor;
   }
   // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle
   // resets CurrMOps. Loop to handle instructions with more MOps than issue in
   // one cycle.  Since we commonly reach the max MOps here, opportunistically
   // bump the cycle to avoid uselessly checking everything in the readyQ.
   CurrMOps += IncMOps;
+
+  // Bump the cycle count for issue group constraints.
+  // This must be done after NextCycle has been adjust for all other stalls.
+  // Calling bumpCycle(X) will reduce CurrMOps by one issue group and set
+  // currCycle to X.
+  if ((isTop() &&  SchedModel->mustEndGroup(SU->getInstr())) ||
+      (!isTop() && SchedModel->mustBeginGroup(SU->getInstr()))) {
+    DEBUG(dbgs() << "  Bump cycle to "
+                 << (isTop() ? "end" : "begin") << " group\n");
+    bumpCycle(++NextCycle);
+  }
+
   while (CurrMOps >= SchedModel->getIssueWidth()) {
     DEBUG(dbgs() << "  *** Max MOps " << CurrMOps
           << " at cycle " << CurrCycle << '\n');
     bumpCycle(++NextCycle);
   }
   DEBUG(dumpScheduledState());
 }
 

llvm/trunk/lib/CodeGen/TargetSchedule.cpp

void TargetSchedModel::init(const MCSchedModel &sm,
   }
   MicroOpFactor = ResourceLCM / SchedModel.IssueWidth;
   for (unsigned Idx = 0; Idx < NumRes; ++Idx) {
     unsigned NumUnits = SchedModel.getProcResource(Idx)->NumUnits;
     ResourceFactors[Idx] = NumUnits ? (ResourceLCM / NumUnits) : 0;
   }
 }
 
+/// Returns true only if instruction is specified as single issue.
+bool TargetSchedModel::mustBeginGroup(const MachineInstr *MI,
+                                     const MCSchedClassDesc *SC) const {
+  if (hasInstrSchedModel()) {
+    if (!SC)
+      SC = resolveSchedClass(MI);
+    if (SC->isValid())
+      return SC->BeginGroup;
+  }
+  return false;
+}
+
+bool TargetSchedModel::mustEndGroup(const MachineInstr *MI,
+                                     const MCSchedClassDesc *SC) const {
+  if (hasInstrSchedModel()) {
+    if (!SC)
+      SC = resolveSchedClass(MI);
+    if (SC->isValid())
+      return SC->EndGroup;
+  }
+  return false;
+}
+
 unsigned TargetSchedModel::getNumMicroOps(const MachineInstr *MI,
                                           const MCSchedClassDesc *SC) const {
   if (hasInstrItineraries()) {
     int UOps = InstrItins.getNumMicroOps(MI->getDesc().getSchedClass());
     return (UOps >= 0) ? UOps : TII->getNumMicroOps(&InstrItins, *MI);
   }
   if (hasInstrSchedModel()) {
     if (!SC)

llvm/trunk/lib/Target/ARM/ARMScheduleR52.td

 def : WriteRes<WriteCMP, [R52UnitALU]> { let Latency = 0; }
 def : WriteRes<WriteCMPsi, [R52UnitALU]> { let Latency = 0; }
 def : WriteRes<WriteCMPsr, [R52UnitALU]> { let Latency = 0; }
 
 // Multiply - aliased to sub-target specific later
 
 // Div - may stall 0-9 cycles depending on input (i.e. WRI+(0-9)/2)
 def : WriteRes<WriteDIV, [R52UnitDiv]> {
-  let Latency = 8; let ResourceCycles = [8]; // not pipelined
+  let Latency = 8; let ResourceCycles = [8]; // non-pipelined
 }
 
 // Branches  - LR written in Late EX2
 def : WriteRes<WriteBr, [R52UnitB]> { let Latency = 0; }
 def : WriteRes<WriteBrL, [R52UnitB]> { let Latency = 0; }
 def : WriteRes<WriteBrTbl, [R52UnitALU]> { let Latency = 0; }
 
 // Misc

 
 // Vector Load/Stores. Can issue only in slot-0. Can dual-issue with
 // another instruction in slot-1, but only in the last issue.
 def R52WriteVLD1Mem  : SchedWriteRes<[R52UnitLd]> { let Latency = 5;}
 def R52WriteVLD2Mem  : SchedWriteRes<[R52UnitLd]> {
   let Latency = 6;
   let NumMicroOps = 3;
   let ResourceCycles = [2];
+  let SingleIssue = 1;
 }
 def R52WriteVLD3Mem  : SchedWriteRes<[R52UnitLd]> {
   let Latency = 7;
   let NumMicroOps = 5;
   let ResourceCycles = [3];
+  let SingleIssue = 1;
 }
 def R52WriteVLD4Mem  : SchedWriteRes<[R52UnitLd]> {
   let Latency = 8;
   let NumMicroOps = 7;
   let ResourceCycles = [4];
+  let SingleIssue = 1;
 }
 def R52WriteVST1Mem  : SchedWriteRes<[R52UnitLd]> {
   let Latency = 5;
   let NumMicroOps = 1;
   let ResourceCycles = [1];
 }
 def R52WriteVST2Mem  : SchedWriteRes<[R52UnitLd]> {
   let Latency = 6;

llvm/trunk/test/CodeGen/ARM/single-issue-r52.mir

+# RUN: llc -o /dev/null %s -mtriple=arm-eabi -mcpu=cortex-r52 -run-pass  machine-scheduler  -enable-misched -debug-only=misched -misched-topdown 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=TOPDOWN
+# RUN: llc -o /dev/null %s -mtriple=arm-eabi -mcpu=cortex-r52 -run-pass  machine-scheduler  -enable-misched -debug-only=misched -misched-bottomup 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=BOTTOMUP
+# REQUIRES: asserts
+--- |
+  ; ModuleID = 'foo.ll'
+  source_filename = "foo.ll"
+  target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+  target triple = "arm---eabi"
+
+  %struct.__neon_int8x8x4_t = type { <8 x i8>, <8 x i8>, <8 x i8>, <8 x i8> }
+  ; Function Attrs: nounwind
+  define <8 x i8> @foo(i8* %A) {
+    %tmp1 = call %struct.__neon_int8x8x4_t @llvm.arm.neon.vld4.v8i8.p0i8(i8* %A, i32 8)
+    %tmp2 = extractvalue %struct.__neon_int8x8x4_t %tmp1, 0
+    %tmp3 = extractvalue %struct.__neon_int8x8x4_t %tmp1, 1
+    %tmp4 = add <8 x i8> %tmp2, %tmp3
+    ret <8 x i8> %tmp4
+  }
+  declare %struct.__neon_int8x8x4_t @llvm.arm.neon.vld4.v8i8.p0i8(i8*, i32)
+
+# CHECK: ********** MI Scheduling **********
+# CHECK: ScheduleDAGMILive::schedule starting
+# CHECK: SU(1):   %vreg1<def> = VLD4d8Pseudo %vreg0, 8, pred:14, pred:%noreg; mem:LD32[%A](align=8) QQPR:%vreg1 GPR:%vreg0
+# CHECK: Latency            : 8
+# CHECK: Single Issue       : true;
+# CHECK: SU(2):   %vreg4<def> = VADDv8i8 %vreg1:dsub_0, %vreg1:dsub_1, pred:14, pred:%noreg; DPR:%vreg4 QQPR:%vreg1
+# CHECK: Latency            : 5
+# CHECK: Single Issue       : false;
+# CHECK: SU(3):   %vreg5<def>, %vreg6<def> = VMOVRRD %vreg4, pred:14, pred:%noreg; GPR:%vreg5,%vreg6 DPR:%vreg4
+# CHECK: Latency            : 4
+# CHECK: Single Issue       : false;
+
+# TOPDOWN: Scheduling SU(1) %vreg1<def> = VLD4d8Pseudo
+# TOPDOWN: Bump cycle to end group
+# TOPDOWN: Scheduling SU(2) %vreg4<def> = VADDv8i8
+
+# BOTTOMUP: Scheduling SU(2) %vreg4<def> = VADDv8i8
+# BOTTOMUP: Scheduling SU(1) %vreg1<def> = VLD4d8Pseudo
+# BOTTOMUP: Bump cycle to begin group
+
+...
+---
+name:            foo
+alignment:       2
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gpr }
+  - { id: 1, class: qqpr }
+  - { id: 2, class: dpr }
+  - { id: 3, class: dpr }
+  - { id: 4, class: dpr }
+  - { id: 5, class: gpr }
+  - { id: 6, class: gpr }
+liveins:
+  - { reg: '%r0', virtual-reg: '%0' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+body:             |
+  bb.0 (%ir-block.0):
+    liveins: %r0
+
+    %0 = COPY %r0
+    %1 = VLD4d8Pseudo %0, 8, 14, _ :: (load 32 from %ir.A, align 8)
+    %4 = VADDv8i8 %1.dsub_0, %1.dsub_1, 14, _
+    %5, %6 = VMOVRRD %4, 14, _
+    %r0 = COPY %5
+    %r1 = COPY %6
+    BX_RET 14, _, implicit %r0, implicit killed %r1
+
+...

llvm/trunk/utils/TableGen/SubtargetEmitter.cpp

for (unsigned W : Writes) {
         if (WriteRes->getValueAsBit("Unsupported")) {
           SCDesc.NumMicroOps = MCSchedClassDesc::InvalidNumMicroOps;
           break;
         }
         WLEntry.Cycles += WriteRes->getValueAsInt("Latency");
         SCDesc.NumMicroOps += WriteRes->getValueAsInt("NumMicroOps");
         SCDesc.BeginGroup |= WriteRes->getValueAsBit("BeginGroup");
         SCDesc.EndGroup |= WriteRes->getValueAsBit("EndGroup");
+        SCDesc.BeginGroup |= WriteRes->getValueAsBit("SingleIssue");
+        SCDesc.EndGroup |= WriteRes->getValueAsBit("SingleIssue");
 
         // Create an entry for each ProcResource listed in WriteRes.
         RecVec PRVec = WriteRes->getValueAsListOfDefs("ProcResources");
         std::vector<int64_t> Cycles =
           WriteRes->getValueAsListOfInts("ResourceCycles");
 
         ExpandProcResources(PRVec, Cycles, ProcModel);