[Scheduling] Create the missing dependency edges for store cluster

[steven.zhang]

Summary

If it is load cluster, we don't need to create the dependency edges(SUb->reg) from SUb to SUa as they both depend on the base register "reg"

     +-------+
+---->  reg  |
|    +---+---+
|        ^
|        |
|        |
|        |
|    +---+---+
|    |  SUa  |  Load 0(reg)
|    +---+---+
|        ^
|        |
|        |
|    +---+---+
+----+  SUb  |  Load 4(reg)
     +-------+

But if it is store cluster, we need to create it as follow shows to avoid the instruction store depend on scheduled in-between SUb and SUa. Notice that, AMDGPU several cases break due to this change and I examine them one by one, no obvious issue found from scheduling aspect. However, need double confirm. And one case show some deg in the final code sequence, which seems to be an issue of the later pass I think.

     +-------+
+---->  reg  |
|    +---+---+
|        ^
|        |         Missing       +-------+
|        | +-------------------->+   y   |
|        | |                     +---+---+
|    +---+-+-+                       ^
|    |  SUa  |  Store x 0(reg)       |
|    +---+---+                       |
|        ^                           |
|        |  +------------------------+
|        |  |
|    +---+--++
+----+  SUb  |  Store y 4(reg)
     +-------+

[steven.zhang]

llvm/test/CodeGen/AMDGPU/byval-frame-setup.ll

339 ↗

(On Diff #235692)

This case has some deg as it generates more instructions. But the output of the scheduler is as expected. An issue of the later pass ?

[fhahn]

llvm/test/CodeGen/AArch64/macro-fusion.ll

22 ↗

(On Diff #235692)

This should probably go into a different file, as it’s load/store clustering and not macro fusion

[steven.zhang]

Address comments about the test case.

[steven.zhang]

Ping ...

[fhahn]

This adds new dependencies, hence I think it would be good to gather code size/perf numbers with this change for some impacted targets (e.g. AArch64) to be reasonably sure that there are no unexpected knock-on effects.

llvm/lib/CodeGen/MachineScheduler.cpp

1613

I may be missing something, but IIRC stores could have other memory operations as successors, e.g. because to enforce an ordering between aliasing memory operations.

[steven.zhang]

llvm/lib/CodeGen/MachineScheduler.cpp

1613

It they have memory dependency, they won't be put into the same group.

[fhahn]

llvm/lib/CodeGen/MachineScheduler.cpp

1613

Ah right. The wording in the comment comment seems a bit general though, maybe it would be possible to mention that this is a constraint for the clustering. It might be good to add it as assert as well :)

[steven.zhang]

llvm/lib/CodeGen/MachineScheduler.cpp

1613

ok. I will update the comments and the assertion if it is easy ... Thank you for the comments!

[steven.zhang]

In D72031#1807588, @fhahn wrote:

This adds new dependencies, hence I think it would be good to gather code size/perf numbers with this change for some impacted targets (e.g. AArch64) to be reasonably sure that there are no unexpected knock-on effects.

I can do the code size part with spec 2017 for AArch64 and other affected targets, but I cannot evaluate the perf numbers as I didn't have the env. Can someone help me get that data ? Thank you in advance!

[steven.zhang]

Address the comments. And all the case changes disappear with the patch https://reviews.llvm.org/D72706 landed. So, I didn't see the negative impact from this patch any more. And from the design, it is doing the right thing, without increasing the compiling time.

[merge_guards_bot]

Unit tests: pass. 61882 tests passed, 0 failed and 782 were skipped.

clang-tidy: unknown.

clang-format: pass.

Build artifacts: diff.json, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

[steven.zhang]

Rebase the patch and update the test change for AMDGPU.

[rampitec]

Tests change looks neutral to me now, and the logic seems plausible. How comes that only AMDGPU tests affected?

[steven.zhang]

In D72031#1880128, @rampitec wrote:

Tests change looks neutral to me now, and the logic seems plausible. How comes that only AMDGPU tests affected?

For now, only AMDGPU and AArch64 supports the mem cluster in LLVM. AArch64 only supports the back-2-back load/store cluster while AMDGPU supports 6 load/store at most to be cluster. So, it is more easy to expose this change.

[rampitec]

LGTM, but please wait for other responses.

[evandro]

Would it be possible to add a test case for AArch64?

[steven.zhang]

In D72031#1880821, @evandro wrote:

Would it be possible to add a test case for AArch64?

That would not be easy, but I could cook a case for AArch64 to indicate that, the internal dependency graph has been changed.

[steven.zhang]

Add one test for AArch64 and rebase the patch.

[steven.zhang]

Gentle ping

[steven.zhang]

Ping ...

[steven.zhang]

Rebase the patch.

[foad]

Seems reasonable to me. It's just a heuristic and shouldn't affect correctness, right?

[steven.zhang]

In D72031#2162539, @foad wrote:

Seems reasonable to me. It's just a heuristic and shouldn't affect correctness, right?

Yes.

[evandro]

The AMDGPU test change likely means nothing, but it'd be good if someone who maintains or work that target would ok it. I suggest giving it another week or so. Otherwise, it LGTM.

[steven.zhang]

I see three extra AMDGPU tests changed when rebase the patch. @evandro Would you please help me verify if there is no deg for those changes ? Thank you.

LLVM :: CodeGen/AMDGPU/call-argument-types.ll
LLVM :: CodeGen/AMDGPU/callee-special-input-vgprs.ll
LLVM :: CodeGen/AMDGPU/stack-realign.ll

[evandro]

I'm not familiar with the AMDGPU target, but the changes in these new tests seem harmless, except in CodeGen/AMDGPU/stack-realign.ll, where an instruction disappeared. Again, I'd defer to someone who works in this backend, perhaps @arsenm, to chime in.

[arsenm]

llvm/test/CodeGen/AMDGPU/stack-realign.ll

164–171

Looks like an irrelevant change; no problem. I don't see anything missing?

[evandro]

llvm/test/CodeGen/AMDGPU/stack-realign.ll

164–171

My bad.

[steven.zhang]

Thank you for all the information!

llvm/lib/CodeGen/MachineScheduler.cpp

if (!TII->shouldClusterMemOps(MemOpa.BaseOps, MemOpb.BaseOps, ClusterLength,
       // Current mem ops pair could not be clustered, reset cluster length, and
       // go to next pair
       ClusterLength = 1;
       CurrentClusterBytes = MemOpb.Width;
       continue;
     }
 
     SUnit *SUa = MemOpa.SU;
     SUnit *SUb = MemOpb.SU;
     if (SUa->NodeNum > SUb->NodeNum)
       std::swap(SUa, SUb);
 
     // FIXME: Is this check really required?
     if (!DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) {
       ClusterLength = 1;
       CurrentClusterBytes = MemOpb.Width;
       continue;
     }
 
     LLVM_DEBUG(dbgs() << "Cluster ld/st SU(" << SUa->NodeNum << ") - SU("
                       << SUb->NodeNum << ")\n");
 
+    if (IsLoad) {
       // Copy successor edges from SUa to SUb. Interleaving computation
       // dependent on SUa can prevent load combining due to register reuse.
       // Predecessor edges do not need to be copied from SUb to SUa since
       // nearby loads should have effectively the same inputs.
       for (const SDep &Succ : SUa->Succs) {
         if (Succ.getSUnit() == SUb)
           continue;
         LLVM_DEBUG(dbgs() << "  Copy Succ SU(" << Succ.getSUnit()->NodeNum
                           << ")\n");
         DAG->addEdge(Succ.getSUnit(), SDep(SUb, SDep::Artificial));
       }
+    } else {
+      // Copy predecessor edges from SUb to SUa to avoid the SUnits that
+      // SUb dependent on scheduled in-between SUb and SUa. Successor edges
+      // do not need to be copied from SUa to SUb since no one will depend
+      // on stores.
+      // Notice that, we don't need to care about the memory dependency as
+      // we won't try to cluster them if they have any memory dependency.
+      for (const SDep &Pred : SUb->Preds) {
+        if (Pred.getSUnit() == SUa)
+          continue;
+        LLVM_DEBUG(dbgs() << "  Copy Pred SU(" << Pred.getSUnit()->NodeNum
+                          << ")\n");
+        DAG->addEdge(SUa, SDep(Pred.getSUnit(), SDep::Artificial));
+      }
+    }
 
     LLVM_DEBUG(dbgs() << "  Curr cluster length: " << ClusterLength
                       << ", Curr cluster bytes: " << CurrentClusterBytes
                       << "\n");
   }
 }
 
 /// Callback from DAG postProcessing to create cluster edges for loads.

llvm/test/CodeGen/AArch64/aarch64-stp-cluster.ll

entry:
   %10 = load i64, i64* %arrayidx3.3, align 8
   %mul.3 = mul nsw i64 %10, %9
   %arrayidx5.3 = getelementptr inbounds i64, i64* %a, i64 3
   %11 = load i64, i64* %arrayidx5.3, align 8
   %add6.3 = add nsw i64 %11, %mul.3
   store i64 %add6.3, i64* %arrayidx5.3, align 8
   ret void
 }
+
+; Verify that the SU(2) and SU(4) are the preds of SU(3)
+; CHECK: ********** MI Scheduling **********
+; CHECK-LABEL: stp_missing_preds_edges:%bb.0
+; CHECK:Cluster ld/st SU(3) - SU(5)
+; CHECK: Copy Pred SU(4)
+; CHECK: Copy Pred SU(2)
+; CHECK:SU(2):   %0:gpr64common = COPY $x0
+; CHECK:SU(3):   STRWui %1:gpr32, %0:gpr64common, 0
+; CHECK:SU(4):   %3:gpr32common = nsw ADDWri %2:gpr32common, 5, 0
+; CHECK:SU(5):   STRWui %3:gpr32common, %0:gpr64common, 1
+define void @stp_missing_preds_edges(i32* %p, i32 %m, i32 %n) {
+entry:
+  store i32 %m, i32* %p, align 4
+  %add = add nsw i32 %n, 5
+  %arrayidx1 = getelementptr inbounds i32, i32* %p, i64 1
+  store i32 %add, i32* %arrayidx1, align 4
+  ret void
+}

llvm/test/CodeGen/AMDGPU/call-argument-types.ll

 define amdgpu_kernel void @stack_passed_arg_alignment_v32i32_f64(<32 x i32> %val, double %tmp) #0 {
 entry:
   call void @stack_passed_f64_arg(<32 x i32> %val, double %tmp)
   ret void
 }
 
 ; GCN-LABEL: {{^}}tail_call_byval_align16:
 ; GCN-NOT: s32
-; GCN: buffer_load_dword v32, off, s[0:3], s32 offset:12
-; GCN: buffer_load_dword v33, off, s[0:3], s32 offset:8
+; GCN: buffer_load_dword v32, off, s[0:3], s32 offset:8
+; GCN: buffer_load_dword v33, off, s[0:3], s32 offset:12
 
 ; GCN: s_getpc_b64
 
-; GCN: buffer_store_dword v32, off, s[0:3], s32 offset:4
-; GCN: buffer_store_dword v33, off, s[0:3], s32{{$}}
+; GCN: buffer_store_dword v33, off, s[0:3], s32 offset:4
+; GCN: buffer_store_dword v32, off, s[0:3], s32{{$}}
 ; GCN-NOT: s32
 ; GCN: s_setpc_b64
 define void @tail_call_byval_align16(<32 x i32> %val, double %tmp) #0 {
 entry:
   %alloca = alloca double, align 8, addrspace(5)
   tail call void @byval_align16_f64_arg(<32 x i32> %val, double addrspace(5)* byval align 16 %alloca)
   ret void
 }

llvm/test/CodeGen/AMDGPU/callee-special-input-vgprs.ll

 ; VARABI: buffer_store_dword v0, off, s[0:3], s32 offset:4
 
 ; VARABI: buffer_store_dword [[RELOAD_BYVAL]], off, s[0:3], s32{{$}}
 ; VARABI: v_mov_b32_e32 [[RELOAD_BYVAL]],
 ; VARABI: s_swappc_b64
 
 
 ; FIXEDABI: v_mov_b32_e32 [[K0:v[0-9]+]], 0x3e7
-; FIXEDABI: buffer_store_dword [[K0]], off, s[0:3], 0 offset:4{{$}}
-
 ; FIXEDABI: s_movk_i32 s32, 0x400{{$}}
-
 ; FIXEDABI: v_mov_b32_e32 [[K1:v[0-9]+]], 0x140
+; FIXEDABI: buffer_store_dword [[K0]], off, s[0:3], 0 offset:4{{$}}
+
 ; FIXEDABI: buffer_store_dword [[K1]], off, s[0:3], s32{{$}}
 
 ; FIXME: Why this reload?
 ; FIXEDABI: buffer_load_dword [[RELOAD:v[0-9]+]], off, s[0:3], 0 offset:4{{$}}
 
 ; FIXEDABI-DAG: v_lshlrev_b32_e32 [[TMP1:v[0-9]+]], 10, v1
 ; FIXEDABI-DAG: v_lshlrev_b32_e32 [[TMP0:v[0-9]+]], 20, v2
 ; FIXEDABI-DAG: v_or_b32_e32 [[TMP2:v[0-9]+]], v0, [[TMP1]]

 ; VARABI: buffer_store_dword v0, off, s[0:3], s32 offset:4
 ; VARABI: buffer_store_dword [[RELOAD_BYVAL]], off, s[0:3], s32{{$}}
 ; VARABI: v_mov_b32_e32 [[RELOAD_BYVAL]],
 ; VARABI: s_swappc_b64
 
 
 ; FIXED-ABI-NOT: v31
 ; FIXEDABI: v_mov_b32_e32 [[K0:v[0-9]+]], 0x3e7{{$}}
-; FIXEDABI: buffer_store_dword [[K0]], off, s[0:3], s33{{$}}
-
 ; FIXEDABI: v_mov_b32_e32 [[K1:v[0-9]+]], 0x140{{$}}
+; FIXEDABI: buffer_store_dword [[K0]], off, s[0:3], s33{{$}}
 ; FIXEDABI: buffer_store_dword [[K1]], off, s[0:3], s32{{$}}
 ; FIXEDABI: buffer_load_dword [[RELOAD_BYVAL:v[0-9]+]], off, s[0:3], s33{{$}}
 
 ; FIXED-ABI-NOT: v31
 ; FIXEDABI: buffer_store_dword [[RELOAD_BYVAL]], off, s[0:3], s32 offset:4{{$}}
 ; FIXED-ABI-NOT: v31
 ; FIXEDABI: s_swappc_b64
 define void @func_call_too_many_args_use_workitem_id_x_byval() #1 {

llvm/test/CodeGen/AMDGPU/fshr.ll

 ; GFX9-NEXT:    v_lshl_or_b32 v5, v5, v7, v6
 ; GFX9-NEXT:    v_cmp_eq_u32_e32 vcc, 0, v2
 ; GFX9-NEXT:    v_cndmask_b32_e32 v1, v5, v1, vcc
 ; GFX9-NEXT:    s_waitcnt vmcnt(0)
 ; GFX9-NEXT:    v_lshl_or_b32 v6, v8, v10, v9
 ; GFX9-NEXT:    v_cmp_eq_u32_e32 vcc, 0, v3
 ; GFX9-NEXT:    v_cndmask_b32_e32 v2, v6, v4, vcc
 ; GFX9-NEXT:    v_lshrrev_b32_e32 v3, 8, v2
-; GFX9-NEXT:    buffer_store_byte_d16_hi v2, v0, s[0:3], 0 offen offset:5
-; GFX9-NEXT:    buffer_store_byte v3, v0, s[0:3], 0 offen offset:4
 ; GFX9-NEXT:    buffer_store_byte v2, v0, s[0:3], 0 offen offset:3
 ; GFX9-NEXT:    buffer_store_byte_d16_hi v1, v0, s[0:3], 0 offen offset:2
 ; GFX9-NEXT:    buffer_store_short v1, v0, s[0:3], 0 offen
+; GFX9-NEXT:    buffer_store_byte_d16_hi v2, v0, s[0:3], 0 offen offset:5
+; GFX9-NEXT:    buffer_store_byte v3, v0, s[0:3], 0 offen offset:4
 ; GFX9-NEXT:    s_waitcnt vmcnt(0)
 ; GFX9-NEXT:    s_setpc_b64 s[30:31]
 ;
 ; R600-LABEL: v_fshr_v2i24:
 ; R600:       ; %bb.0:
 ; R600-NEXT:    CF_END
 ; R600-NEXT:    PAD
   %ret = call <2 x i24> @llvm.fshr.v2i24(<2 x i24> %src0, <2 x i24> %src1, <2 x i24> %src2)
   ret <2 x i24> %ret
 }

llvm/test/CodeGen/AMDGPU/half.ll

 ; GCN: flat_load_dwordx4
 ; GCN: flat_load_dwordx4
 
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
+; SI: v_cvt_f32_f16_e32
 
 ; GCN: flat_store_dwordx4
 
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
 ; SI: v_cvt_f32_f16_e32
-; SI: v_cvt_f32_f16_e32
 
 ; VI: v_cvt_f32_f16_e32
 ; VI: v_cvt_f32_f16_sdwa
 
 
 ; GCN: flat_store_dwordx4
 ; GCN: flat_store_dwordx4
 ; GCN: flat_store_dwordx4

llvm/test/CodeGen/AMDGPU/stack-realign.ll

 ; Should use BP to access the incoming stack arguments.
 ; The BP value is saved/restored with a VGPR spill.
 
 ; GCN-LABEL: func_call_align1024_bp_gets_vgpr_spill:
 ; GCN: buffer_store_dword [[VGPR_REG:v[0-9]+]], off, s[0:3], s32 offset:1028 ; 4-byte Folded Spill
 ; GCN-NEXT: s_mov_b64 exec, s[4:5]
 ; GCN-NEXT: v_writelane_b32 [[VGPR_REG]], s33, 2
 ; GCN-NEXT: v_writelane_b32 [[VGPR_REG]], s34, 3
+; GCN: s_mov_b32 s34, s32
 ; GCN: s_add_u32 [[SCRATCH_REG:s[0-9]+]], s32, 0xffc0
 ; GCN: s_and_b32 s33, [[SCRATCH_REG]], 0xffff0000
-
-; GCN: s_mov_b32 s34, s32
-; GCN-NEXT: v_mov_b32_e32 v32, 0
-
-; GCN: buffer_store_dword v32, off, s[0:3], s33 offset:1024
 ; GCN-NEXT: buffer_load_dword v{{[0-9]+}}, off, s[0:3], s34
 ; GCN-NEXT: s_add_u32 s32, s32, 0x30000
 
+; GCN: v_mov_b32_e32 v33, 0
+
+; GCN: buffer_store_dword v33, off, s[0:3], s33 offset:1024
+
 ; GCN: buffer_store_dword v{{[0-9]+}}, off, s[0:3], s32
 ; GCN-NEXT: s_swappc_b64 s[30:31], s[4:5]
 
 ; GCN: v_readlane_b32 s33, [[VGPR_REG]], 2
 ; GCN-NEXT: s_sub_u32 s32, s32, 0x30000
 ; GCN-NEXT: v_readlane_b32 s34, [[VGPR_REG]], 3
 ; GCN-NEXT: s_or_saveexec_b64 s[6:7], -1
 ; GCN-NEXT: buffer_load_dword [[VGPR_REG]], off, s[0:3], s32 offset:1028 ; 4-byte Folded Reload