[MCA] Support carry-over instructions for in-order processors

[asavonic]

Summary

Instructions that have more uops than the processor's IssueWidth are
issued in multiple cycles.

The patch fixes PR49712.

[andreadb]

LGTM modulo a few nits (see comments below).

llvm/lib/MCA/Stages/InOrderIssueStage.cpp

266–268

This check is not needed if ShouldCarryOver is true. It can be safely moved inside the the above else block (at like 261).

333–356

Please move this to a separate function. Something like updateCarriedOverInstruction() (or a similar name..).

335–337

The first assert (i.e. assert(Bandwidth > 0)) can be safely removed. IssueWidth is supposed to always be bigger than 0. You would see other problems otherwise.

The second assert (i.e. assert(CarryOver > 0)) can also be removed because, by construction, it is an impossible situation if we take that if-stmt.

You can live the third assert, but please add a string comment to it.

339–340

Nit: The [E] notation should only be used for real events.

I noticed this in previous patches too, but I didn't say anything because it was not so important. Also, those debug comments are very useful in general.

However, it would be nicer if we could use a different prefix for these new remarks; messages like this one are not strictly related to hardware events. It would be nicer if we consistently use a different char for it (maybe N - as in "Note", or R for "Remark"?) instead of E, which is supposed to be used as prefix for event-related debug messages.

352–353

Same.

[asavonic]

• Refactored code, added updateCarriedOver function
• Used a different prefix for non-event debugging messages

[asavonic]

Thanks for the review Andrea!

llvm/lib/MCA/Stages/InOrderIssueStage.cpp

339–340

"N" as in Note sounds good.
I'll update other log messages in a separate NFC patch.

[andreadb]

llvm/lib/MCA/Stages/InOrderIssueStage.cpp

339–340

Sounds good! Thanks!

The patch LGTM

llvm/include/llvm/MCA/Stages/InOrderIssueStage.h

class InOrderIssueStage final : public Stage {
   /// Number of instructions issued in the current cycle.
   unsigned NumIssued;
 
   /// If an instruction cannot execute due to an unmet register or resource
   /// dependency, the it is stalled for StallCyclesLeft.
   InstRef StalledInst;
   unsigned StallCyclesLeft;
 
+  /// Instruction that is issued in more than 1 cycle.
+  InstRef CarriedOver;
+  /// Number of CarriedOver uops left to issue.
+  unsigned CarryOver;
+
   /// Number of instructions that can be issued in the current cycle.
   unsigned Bandwidth;
 
   /// Number of cycles (counted from the current cycle) until the last write is
   /// committed. This is taken into account to ensure that writes commit in the
   /// program order.
   unsigned LastWriteBackCycle;
 

llvm/lib/MCA/Stages/InOrderIssueStage.cpp

 
 #include <algorithm>
 
 #define DEBUG_TYPE "llvm-mca"
 namespace llvm {
 namespace mca {
 
 bool InOrderIssueStage::hasWorkToComplete() const {
-  return !IssuedInst.empty() || StalledInst;
+  return !IssuedInst.empty() || StalledInst || CarriedOver;
 }
 
 bool InOrderIssueStage::isAvailable(const InstRef &IR) const {
+  if (StalledInst || CarriedOver)
+    return false;
+
   const Instruction &Inst = *IR.getInstruction();
   unsigned NumMicroOps = Inst.getNumMicroOps();
   const InstrDesc &Desc = Inst.getDesc();
 
-  if (Bandwidth < NumMicroOps)
+  bool ShouldCarryOver = NumMicroOps > SM.IssueWidth;
+  if (Bandwidth < NumMicroOps && !ShouldCarryOver)
     return false;
 
   // Instruction with BeginGroup must be the first instruction to be issued in a
   // cycle.
   if (Desc.BeginGroup && NumIssued != 0)
     return false;
 
   return true;
llvm::Error InOrderIssueStage::tryIssue(InstRef &IR, unsigned *StallCycles) {
 
   // Replace resource masks with valid resource processor IDs.
   for (std::pair<ResourceRef, ResourceCycles> &Use : UsedResources) {
     uint64_t Mask = Use.first.first;
     Use.first.first = RM->resolveResourceMask(Mask);
   }
   notifyInstructionIssue(IR, UsedResources, *this);
 
-  if (Desc.EndGroup) {
+  bool ShouldCarryOver = NumMicroOps > Bandwidth;
+  if (ShouldCarryOver) {
+    CarryOver = NumMicroOps - Bandwidth;
+    CarriedOver = IR;
     Bandwidth = 0;
+    NumIssued += Bandwidth;
+    LLVM_DEBUG(dbgs() << "[E] Carry over #" << IR << " \n");
   } else {
-    assert(Bandwidth >= NumMicroOps);
     Bandwidth -= NumMicroOps;
+    NumIssued += NumMicroOps;
   }
 
+  if (Desc.EndGroup)
+    Bandwidth = 0;
+
   IssuedInst.push_back(IR);
-  NumIssued += NumMicroOps;
 
   if (!IR.getInstruction()->getDesc().RetireOOO)
     LastWriteBackCycle = findLastWriteBackCycle(IR);
 
   return llvm::ErrorSuccess();
 }
 
 void InOrderIssueStage::updateIssuedInst() {
llvm::Error InOrderIssueStage::cycleStart() {
   PRF.cycleStart();
 
   // Release consumed resources.
   SmallVector<ResourceRef, 4> Freed;
   RM->cycleEvent(Freed);
 
   updateIssuedInst();
 
+  // Continue to issue the instruction carried over from the previous cycle
+  if (CarriedOver) {
+    assert(Bandwidth > 0);
+    assert(CarryOver > 0);
+    assert(!StalledInst);
+    if (CarryOver <= Bandwidth) {
+      LLVM_DEBUG(dbgs() << "[E] Carry over (complete) #" << CarriedOver
+                        << " \n");
+
+      if (CarriedOver.getInstruction()->getDesc().EndGroup)
+        Bandwidth = 0;
+      else
+        Bandwidth -= CarryOver;
+
+      CarriedOver = InstRef();
+      CarryOver = 0;
+    } else {
+      CarryOver -= Bandwidth;
+      Bandwidth = 0;
+      LLVM_DEBUG(dbgs() << "[E] Carry over (" << CarryOver << "cy left) #"
+                        << CarriedOver << " \n");
+    }
+  }
+
   // Issue instructions scheduled for this cycle
   if (!StallCyclesLeft && StalledInst) {
     if (llvm::Error E = tryIssue(StalledInst, &StallCyclesLeft))
       return E;
   }
 
   if (!StallCyclesLeft) {
     StalledInst.invalidate();

llvm/test/tools/llvm-mca/AArch64/Cortex/A53-carry-over.s

+# NOTE: Assertions have been autogenerated by utils/update_mca_test_checks.py
+# RUN: llvm-mca -mtriple=aarch64 -mcpu=cortex-a53 --timeline --iterations=1 < %s | FileCheck %s
+
+ldp  w3, w5, [x10], #4 // 2uop + 1uop carry over
+add  w10, w11, w12
+add  w13, w14, w15
+ldp  w7, w8, [x11] // 2uop, no carry over
+add  w16, w17, w18
+add  w19, w20, w21
+
+# CHECK:      Iterations:        1
+# CHECK-NEXT: Instructions:      6
+# CHECK-NEXT: Total Cycles:      8
+# CHECK-NEXT: Total uOps:        9
+
+# CHECK:      Dispatch Width:    2
+# CHECK-NEXT: uOps Per Cycle:    1.13
+# CHECK-NEXT: IPC:               0.75
+# CHECK-NEXT: Block RThroughput: 4.5
+
+# CHECK:      Instruction Info:
+# CHECK-NEXT: [1]: #uOps
+# CHECK-NEXT: [2]: Latency
+# CHECK-NEXT: [3]: RThroughput
+# CHECK-NEXT: [4]: MayLoad
+# CHECK-NEXT: [5]: MayStore
+# CHECK-NEXT: [6]: HasSideEffects (U)
+
+# CHECK:      [1]    [2]    [3]    [4]    [5]    [6]    Instructions:
+# CHECK-NEXT:  3      4     2.00    *                   ldp w3, w5, [x10], #4
+# CHECK-NEXT:  1      3     0.50                        add w10, w11, w12
+# CHECK-NEXT:  1      3     0.50                        add w13, w14, w15
+# CHECK-NEXT:  2      4     2.00    *                   ldp w7, w8, [x11]
+# CHECK-NEXT:  1      3     0.50                        add w16, w17, w18
+# CHECK-NEXT:  1      3     0.50                        add w19, w20, w21
+
+# CHECK:      Resources:
+# CHECK-NEXT: [0.0] - A53UnitALU
+# CHECK-NEXT: [0.1] - A53UnitALU
+# CHECK-NEXT: [1]   - A53UnitB
+# CHECK-NEXT: [2]   - A53UnitDiv
+# CHECK-NEXT: [3]   - A53UnitFPALU
+# CHECK-NEXT: [4]   - A53UnitFPMDS
+# CHECK-NEXT: [5]   - A53UnitLdSt
+# CHECK-NEXT: [6]   - A53UnitMAC
+
+# CHECK:      Resource pressure per iteration:
+# CHECK-NEXT: [0.0]  [0.1]  [1]    [2]    [3]    [4]    [5]    [6]
+# CHECK-NEXT: 2.00   2.00    -      -      -      -     4.00    -
+
+# CHECK:      Resource pressure by instruction:
+# CHECK-NEXT: [0.0]  [0.1]  [1]    [2]    [3]    [4]    [5]    [6]    Instructions:
+# CHECK-NEXT:  -      -      -      -      -      -     2.00    -     ldp w3, w5, [x10], #4
+# CHECK-NEXT:  -     1.00    -      -      -      -      -      -     add w10, w11, w12
+# CHECK-NEXT: 1.00    -      -      -      -      -      -      -     add w13, w14, w15
+# CHECK-NEXT:  -      -      -      -      -      -     2.00    -     ldp w7, w8, [x11]
+# CHECK-NEXT:  -     1.00    -      -      -      -      -      -     add w16, w17, w18
+# CHECK-NEXT: 1.00    -      -      -      -      -      -      -     add w19, w20, w21
+
+# CHECK:      Timeline view:
+# CHECK-NEXT: Index     01234567
+
+# CHECK:      [0,0]     DeeeE. .   ldp  w3, w5, [x10], #4
+# CHECK-NEXT: [0,1]     .DeeE. .   add  w10, w11, w12
+# CHECK-NEXT: [0,2]     . DeeE .   add  w13, w14, w15
+# CHECK-NEXT: [0,3]     .  DeeeE   ldp  w7, w8, [x11]
+# CHECK-NEXT: [0,4]     .   DeeE   add  w16, w17, w18
+# CHECK-NEXT: [0,5]     .   DeeE   add  w19, w20, w21
+
+# CHECK:      Average Wait times (based on the timeline view):
+# CHECK-NEXT: [0]: Executions
+# CHECK-NEXT: [1]: Average time spent waiting in a scheduler's queue
+# CHECK-NEXT: [2]: Average time spent waiting in a scheduler's queue while ready
+# CHECK-NEXT: [3]: Average time elapsed from WB until retire stage
+
+# CHECK:            [0]    [1]    [2]    [3]
+# CHECK-NEXT: 0.     1     0.0    0.0    0.0       ldp  w3, w5, [x10], #4
+# CHECK-NEXT: 1.     1     0.0    0.0    0.0       add  w10, w11, w12
+# CHECK-NEXT: 2.     1     0.0    0.0    0.0       add  w13, w14, w15
+# CHECK-NEXT: 3.     1     0.0    0.0    0.0       ldp  w7, w8, [x11]
+# CHECK-NEXT: 4.     1     0.0    0.0    0.0       add  w16, w17, w18
+# CHECK-NEXT: 5.     1     0.0    0.0    0.0       add  w19, w20, w21
+# CHECK-NEXT:        1     0.0    0.0    0.0       <total>

llvm/test/tools/llvm-mca/AMDGPU/gfx10-double.s

 v_min_f64 v[6:7], v[6:7], v[6:7]
 v_max_f64 v[8:9], v[8:9], v[8:9]
 
 v_div_fmas_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 
 v_div_fixup_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 v_ldexp_f64 v[2:3], v[2:3], v0
 
-; FIXME: This instructions sends llvm-mca into an infinite loop
-;v_div_scale_f64 v[0:1], vcc_lo, v[0:1], v[0:1], v[0:1]
+v_div_scale_f64 v[0:1], vcc_lo, v[0:1], v[0:1], v[0:1]
 
 v_trig_preop_f64 v[2:3], v[2:3], v0
 
 v_cmp_eq_f64 v[0:1], v[0:1]
 v_cmp_class_f64 vcc_lo, v[2:3], s0
 
 v_rcp_f64 v[0:1], v[0:1]
 v_rsq_f64 v[2:3], v[2:3]
 v_sqrt_f64 v[4:5], v[4:5]
 
 # CHECK:      Iterations:        1
-# CHECK-NEXT: Instructions:      27
-# CHECK-NEXT: Total Cycles:      204
-# CHECK-NEXT: Total uOps:        27
+# CHECK-NEXT: Instructions:      28
+# CHECK-NEXT: Total Cycles:      224
+# CHECK-NEXT: Total uOps:        29
 
 # CHECK:      Dispatch Width:    1
 # CHECK-NEXT: uOps Per Cycle:    0.13
 # CHECK-NEXT: IPC:               0.13
-# CHECK-NEXT: Block RThroughput: 27.0
+# CHECK-NEXT: Block RThroughput: 29.0
 
 # CHECK:      Instruction Info:
 # CHECK-NEXT: [1]: #uOps
 # CHECK-NEXT: [2]: Latency
 # CHECK-NEXT: [3]: RThroughput
 # CHECK-NEXT: [4]: MayLoad
 # CHECK-NEXT: [5]: MayStore
 # CHECK-NEXT: [6]: HasSideEffects (U)

 # CHECK-NEXT:  1      22    1.00                  U     v_fma_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  1      22    1.00                  U     v_add_f64 v[2:3], v[2:3], v[2:3]
 # CHECK-NEXT:  1      22    1.00                  U     v_mul_f64 v[4:5], v[4:5], v[4:5]
 # CHECK-NEXT:  1      22    1.00                  U     v_min_f64 v[6:7], v[6:7], v[6:7]
 # CHECK-NEXT:  1      22    1.00                  U     v_max_f64 v[8:9], v[8:9], v[8:9]
 # CHECK-NEXT:  1      22    1.00                  U     v_div_fmas_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  1      22    1.00                  U     v_div_fixup_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  1      22    1.00                  U     v_ldexp_f64 v[2:3], v[2:3], v0
+# CHECK-NEXT:  2      22    2.00                  U     v_div_scale_f64 v[0:1], vcc_lo, v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  1      22    1.00                  U     v_trig_preop_f64 v[2:3], v[2:3], v0
 # CHECK-NEXT:  1      22    1.00                  U     v_cmp_eq_f64_e32 vcc_lo, v[0:1], v[0:1]
 # CHECK-NEXT:  1      22    1.00                  U     v_cmp_class_f64_e64 vcc_lo, v[2:3], s0
 # CHECK-NEXT:  1      24    1.00                  U     v_rcp_f64_e32 v[0:1], v[0:1]
 # CHECK-NEXT:  1      24    1.00                  U     v_rsq_f64_e32 v[2:3], v[2:3]
 # CHECK-NEXT:  1      24    1.00                  U     v_sqrt_f64_e32 v[4:5], v[4:5]
 
 # CHECK:      Resources:
 # CHECK-NEXT: [0]   - HWBranch
 # CHECK-NEXT: [1]   - HWExport
 # CHECK-NEXT: [2]   - HWLGKM
 # CHECK-NEXT: [3]   - HWRC
 # CHECK-NEXT: [4]   - HWSALU
 # CHECK-NEXT: [5]   - HWVALU
 # CHECK-NEXT: [6]   - HWVMEM
 
 # CHECK:      Resource pressure per iteration:
 # CHECK-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]
-# CHECK-NEXT:  -      -      -     27.00   -     27.00   -
+# CHECK-NEXT:  -      -      -     29.00  1.00   28.00   -
 
 # CHECK:      Resource pressure by instruction:
 # CHECK-NEXT: [0]    [1]    [2]    [3]    [4]    [5]    [6]    Instructions:
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cvt_i32_f64_e32 v0, v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cvt_f64_i32_e32 v[2:3], v2
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cvt_f32_f64_e32 v4, v[4:5]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cvt_f64_f32_e32 v[6:7], v6
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cvt_u32_f64_e32 v8, v[8:9]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cvt_f64_u32_e32 v[10:11], v10
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_frexp_exp_i32_f64_e32 v0, v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_frexp_mant_f64_e32 v[2:3], v[2:3]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_fract_f64_e32 v[4:5], v[4:5]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_trunc_f64_e32 v[0:1], v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_ceil_f64_e32 v[2:3], v[2:3]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_rndne_f64_e32 v[4:5], v[4:5]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_floor_f64_e32 v[6:7], v[6:7]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_fma_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_add_f64 v[2:3], v[2:3], v[2:3]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_mul_f64 v[4:5], v[4:5], v[4:5]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_min_f64 v[6:7], v[6:7], v[6:7]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_max_f64 v[8:9], v[8:9], v[8:9]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_div_fmas_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_div_fixup_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_ldexp_f64 v[2:3], v[2:3], v0
+# CHECK-NEXT:  -      -      -     2.00   1.00   1.00    -     v_div_scale_f64 v[0:1], vcc_lo, v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_trig_preop_f64 v[2:3], v[2:3], v0
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cmp_eq_f64_e32 vcc_lo, v[0:1], v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_cmp_class_f64_e64 vcc_lo, v[2:3], s0
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_rcp_f64_e32 v[0:1], v[0:1]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_rsq_f64_e32 v[2:3], v[2:3]
 # CHECK-NEXT:  -      -      -     1.00    -     1.00    -     v_sqrt_f64_e32 v[4:5], v[4:5]
 
 # CHECK:      Timeline view:

 # CHECK-NEXT: 13.    1     0.0    0.0    0.0       v_fma_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT: 14.    1     0.0    0.0    0.0       v_add_f64 v[2:3], v[2:3], v[2:3]
 # CHECK-NEXT: 15.    1     0.0    0.0    0.0       v_mul_f64 v[4:5], v[4:5], v[4:5]
 # CHECK-NEXT: 16.    1     0.0    0.0    0.0       v_min_f64 v[6:7], v[6:7], v[6:7]
 # CHECK-NEXT: 17.    1     0.0    0.0    0.0       v_max_f64 v[8:9], v[8:9], v[8:9]
 # CHECK-NEXT: 18.    1     0.0    0.0    0.0       v_div_fmas_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT: 19.    1     0.0    0.0    0.0       v_div_fixup_f64 v[0:1], v[0:1], v[0:1], v[0:1]
 # CHECK-NEXT: 20.    1     0.0    0.0    0.0       v_ldexp_f64 v[2:3], v[2:3], v0
-# CHECK-NEXT: 21.    1     0.0    0.0    0.0       v_trig_preop_f64 v[2:3], v[2:3], v0
-# CHECK-NEXT: 22.    1     0.0    0.0    0.0       v_cmp_eq_f64_e32 vcc_lo, v[0:1], v[0:1]
-# CHECK-NEXT: 23.    1     0.0    0.0    0.0       v_cmp_class_f64_e64 vcc_lo, v[2:3], s0
-# CHECK-NEXT: 24.    1     0.0    0.0    0.0       v_rcp_f64_e32 v[0:1], v[0:1]
-# CHECK-NEXT: 25.    1     0.0    0.0    0.0       v_rsq_f64_e32 v[2:3], v[2:3]
-# CHECK-NEXT: 26.    1     0.0    0.0    0.0       v_sqrt_f64_e32 v[4:5], v[4:5]
+# CHECK-NEXT: 21.    1     0.0    0.0    0.0       v_div_scale_f64 v[0:1], vcc_lo, v[0:1], v[0:1], v[0:1]
+# CHECK-NEXT: 22.    1     0.0    0.0    0.0       v_trig_preop_f64 v[2:3], v[2:3], v0
+# CHECK-NEXT: 23.    1     0.0    0.0    0.0       v_cmp_eq_f64_e32 vcc_lo, v[0:1], v[0:1]
+# CHECK-NEXT: 24.    1     0.0    0.0    0.0       v_cmp_class_f64_e64 vcc_lo, v[2:3], s0
+# CHECK-NEXT: 25.    1     0.0    0.0    0.0       v_rcp_f64_e32 v[0:1], v[0:1]
+# CHECK-NEXT: 26.    1     0.0    0.0    0.0       v_rsq_f64_e32 v[2:3], v[2:3]
+# CHECK-NEXT: 27.    1     0.0    0.0    0.0       v_sqrt_f64_e32 v[4:5], v[4:5]
 # CHECK-NEXT:        1     0.0    0.0    0.0       <total>