[AMDGPU] Add test

[piotr]

Summary

Add test checking that the redundant immediate MOV instruction
(by-product of handling phi nodes) is not found in the generated code.

[piotr]

Related to D63709.

[arsenm]

lib/CodeGen/MachineCSE.cpp

482–490

I'm not sure the phis only part is needed. It would make sense to me to check the successor blocks if it's trivial (i.e. the successor only has the one predecessor here)

test/CodeGen/AMDGPU/cse-phi-incoming-val.ll

14

There should probably be additional MIR tests for this. I wouldn't trust that the control flow block layout we emit know will remain constant

[piotr]

V2: Removing condition that BB has to contain phis only. Added a MIR test.

[piotr]

lib/CodeGen/MachineCSE.cpp

482–490

Good point, I removed the condition that BB has to contain phis only. I am checking that the BB has only one successor. However, that successor might have more than one predecessor, as the pattern I am matching here is a block containing phi nodes, and such blocks typically have more than one predecessor.

test/CodeGen/AMDGPU/cse-phi-incoming-val.ll

14

Added a MIR test.

[piotr]

V3: Updating commit message.

[anton-afanasyev]

Hi @piotr, have you tried regression benchmarking with this patch? For instance, test suite.

[piotr]

In D63860#1572882, @anton-afanasyev wrote:

Hi @piotr, have you tried regression benchmarking with this patch? For instance, test suite.

Hi Anton, Yes, I have just run regression testing on the test-suite and the tests pass ("Expected Passes : 917").

[arsenm]

lib/CodeGen/MachineCSE.cpp

482–490

I'm not sure if this should include the phi check or not. More sample cases stressing the different numbers of successors and other instructions would be good?

test/CodeGen/AMDGPU/cse-phi-incoming-val.mir

42–51

Can you trim some of these instructions?

[anton-afanasyev]

In D63860#1574717, @piotr wrote:

In D63860#1572882, @anton-afanasyev wrote:

Hi @piotr, have you tried regression benchmarking with this patch? For instance, test suite.

Hi Anton, Yes, I have just run regression testing on the test-suite and the tests pass ("Expected Passes : 917").

Hmm, I'm talking about performance benchmarking, from llvm Test Suite: https://llvm.org/docs/TestingGuide.html#test-suite.

[piotr]

In D63860#1576545, @anton-afanasyev wrote:

In D63860#1574717, @piotr wrote:

In D63860#1572882, @anton-afanasyev wrote:

Hi @piotr, have you tried regression benchmarking with this patch? For instance, test suite.

Hi Anton, Yes, I have just run regression testing on the test-suite and the tests pass ("Expected Passes : 917").

Hmm, I'm talking about performance benchmarking, from llvm Test Suite: https://llvm.org/docs/TestingGuide.html#test-suite.

Sorry, I referred to the entire test-suite. For MicroBenchmarks only (llvm-lit -v -j 1 -o patch.json MicroBenchmarks) I get the following detailed results:

$python3 ../../test-suite/utils/compare.py --filter-short orig.json patch.json
Warning: 'test-suite :: MicroBenchmarks/XRay/FDRMode/fdrmode-bench.test' has No metrics!
Warning: 'test-suite :: MicroBenchmarks/XRay/ReturnReference/retref-bench.test' has No metrics!
Warning: 'test-suite :: MicroBenchmarks/XRay/FDRMode/fdrmode-bench.test' has No metrics!
Warning: 'test-suite :: MicroBenchmarks/XRay/ReturnReference/retref-bench.test' has No metrics!
Tests: 248
Metric: exec_time

Program orig patch diff
test-suite...mbda.test:BM_PIC_2D_LAMBDA/171 3.18 0.88 -72.2%
test-suite...alsCRaw.test:BM_PIC_2D_RAW/171 1.77 0.89 -49.8%
test-suite...Raw.test:BM_MAT_X_MAT_RAW/5001 4520.23 6770.15 49.8%
test-suite...aw.test:BM_MULADDSUB_RAW/44217 47.74 69.22 45.0%
test-suite...lsBRaw.test:BM_INIT3_RAW/44217 33.57 47.99 42.9%
test-suite...ambda.test:BM_EOS_LAMBDA/44217 46.45 58.30 25.5%
test-suite...ENCHMARK_BILATERAL_FILTER/16/2 22.35 27.97 25.2%
test-suite...ENCHMARK_BILATERAL_FILTER/16/4 68.97 85.68 24.2%
test-suite...ENCHMARK_BILATERAL_FILTER/32/2 103.48 127.84 23.5%
test-suite...ENCHMARK_BILATERAL_FILTER/32/4 381.09 468.47 22.9%
test-suite...mbda.test:BM_ICCG_LAMBDA/44217 32.80 39.22 19.6%
test-suite...st:BM_INT_PREDICT_LAMBDA/44217 366.07 434.41 18.7%
test-suite...est:BM_INT_PREDICT_LAMBDA/5001 14.69 16.82 14.5%
test-suite...BRaw.test:BM_IF_QUAD_RAW/44217 148.05 168.47 13.8%
test-suite....test:BENCHMARK_HARRIS/256/256 389.53 346.90 -10.9%
Geomean difference nan%
orig patch diff
count 232.000000 232.000000 232.000000
mean 2081.547998 2091.565842 0.007603
std 11692.576779 11651.097661 0.091756
min 0.030994 0.030717 -0.722465
25% 3.198364 2.967566 -0.012795
50% 36.165086 39.408759 -0.000642
75% 318.340952 318.455341 0.009107
max 115341.083667 113080.746500 0.497745

[piotr]

lib/CodeGen/MachineCSE.cpp

482–490

My feeling is that without the phi check this heuristic would be too generic and will cause regressions, but can double check. The aim of this change is to target phi nodes re-using the same arguments.
As for the second part, do you mean to add more tests?

test/CodeGen/AMDGPU/cse-phi-incoming-val.mir

42–51

Will do.

[piotr]

V4: Simplified the condition and test.

[arsenm]

lib/CodeGen/MachineCSE.cpp

482–484

I'm having a bit too much trouble following the heuristic with the two loops. Can you split the first loop into a function to return a possible alternative block? The second loop would then remain as-is, except checking UseMI.getParent() == OrigParent || == AlternativeParent

484–489

Can you re-flow this loop into separate BBUses and !BBUses case?

[piotr]

V5: Refactored code.

[piotr]

Ping

[arsenm]

Mostly LGTM, except for the empty block case I'm worried about

lib/CodeGen/MachineCSE.cpp

422

Extra empty line

test/CodeGen/AMDGPU/cse-phi-incoming-val.mir

74

Can you add another test with a totally empty successor block? I think those should also be ignored

[arsenm]

Any update on this?

[piotr]

Thank you for bearing with me, I have been away.

Now, when I re-checked the original case from D63709 this morning (cse-phi-incoming-val.ll) I noticed that the extra mov is not present, even without my patch. It turns out that D63198 (which was pushed recently) made the original issue go away. I guess, the fact that the issue was in the structurizer kind of explains the observation that other targets seemed to not suffer from similar problems.

Anyway, I intend to just push cse-phi-incoming-val.ll as part of the current review.

[piotr]

Reverting the patch and leaving the test only as it passes without the change in code.

[arsenm]

LGTM

lib/CodeGen/MachineCSE.cpp

bool MachineCSE::isCSECandidate(MachineInstr *MI) {
   return true;
 }
 
 /// isProfitableToCSE - Return true if it's profitable to eliminate MI with a
 /// common expression that defines Reg. CSBB is basic block where CSReg is
 /// defined.
 bool MachineCSE::isProfitableToCSE(unsigned CSReg, unsigned Reg,
                                    MachineBasicBlock *CSBB, MachineInstr *MI) {
   // FIXME: Heuristics that works around the lack the live range splitting.
 
   // If CSReg is used at all uses of Reg, CSE should not increase register
   // pressure of CSReg.
   bool MayIncreasePressure = true;
   if (TargetRegisterInfo::isVirtualRegister(CSReg) &&
       TargetRegisterInfo::isVirtualRegister(Reg)) {
     MayIncreasePressure = false;
     SmallPtrSet<MachineInstr*, 8> CSUses;
for (MachineInstr &MI : MRI->use_nodbg_instructions(Reg)) {
         break;
       }
     }
     if (!HasNonCopyUse)
       return false;
   }
 
   // Heuristics #3: If the common subexpression is used by PHIs, do not reuse
-  // it unless the defined value is already used in the BB of the new use.
+  // it unless:
+  // a) the defined value is already used in the BB of the new use or
+  // b) all uses of the defined value are phi nodes placed in a BB,
+  //    whose only successor contains the new use
+
+  // First find the BB containing all uses, as defined in point b) above
+  MachineBasicBlock *BBUses = nullptr;
+  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(Reg)) {
+    if (!UseMI.isPHI() || (BBUses && BBUses != UseMI.getParent())) {
+      BBUses = nullptr;
+      break;
+    }
+    if (!BBUses)
+      BBUses = UseMI.getParent();
+  }
+
+  MachineBasicBlock *BBOnlySucc = nullptr;
+  if (BBUses && BBUses->succ_size() == 1)
+    BBOnlySucc = *BBUses->succ_begin();
+
   bool HasPHI = false;
-  for (MachineInstr &UseMI : MRI->use_nodbg_instructions(CSReg)) {
-    HasPHI |= UseMI.isPHI();
-    if (UseMI.getParent() == MI->getParent())
+  for (MachineInstr &UseCSMI : MRI->use_nodbg_instructions(CSReg)) {
+    HasPHI |= UseCSMI.isPHI();
+    // a) the defined value is already used in the BB of the new use
+    if (UseCSMI.getParent() == MI->getParent())
+      return true;
+    // b) the BB's only successor contains the new use
+    if (UseCSMI.getParent() == BBOnlySucc)
       return true;
   }
 
   return !HasPHI;
 }
 
 void MachineCSE::EnterScope(MachineBasicBlock *MBB) {
   LLVM_DEBUG(dbgs() << "Entering: " << MBB->getName() << '\n');

test/CodeGen/AMDGPU/cse-phi-incoming-val.ll

+; RUN: llc < %s -mtriple=amdgcn--amdpal -mcpu=gfx900 -verify-machineinstrs | FileCheck %s
+
+; Check that the redundant immediate MOV instruction
+; (by-product of handling phi nodes) is not found
+; in the generated code due to CSE heuristic.
+
+; CHECK-LABEL: {{^}}mov_opt:
+; CHECK: v_mov_b32_e32 {{v[0-9]+}}, 1.0
+; CHECK: %bb.1:
+; CHECK-NOT: v_mov_b32_e32 {{v[0-9]+}}, 1.0
+; CHECK: BB0_2:
+
+define amdgpu_ps void @mov_opt(i32 %arg, i32 inreg %arg1, i32 inreg %arg2) local_unnamed_addr #0 {
+bb:
+  %tmp = icmp eq i32 %arg1, 0
+  br i1 %tmp, label %bb3, label %bb10
+
+bb3:                                              ; preds = %bb
+  %tmp4 = icmp eq i32 %arg2, 0
+  br i1 %tmp4, label %bb5, label %bb10
+
+bb5:                                              ; preds = %bb3
+  %tmp6 = getelementptr <{ [4294967295 x i32] }>, <{ [4294967295 x i32] }> addrspace(6)* null, i32 0, i32 0, i32 %arg
+  %tmp7 = load i32, i32 addrspace(6)* %tmp6
+  %tmp8 = icmp eq i32 %tmp7, 1
+  br i1 %tmp8, label %bb10, label %bb9
+
+bb9:                                              ; preds = %bb5
+  br label %bb10
+
+bb10:                                             ; preds = %bb9, %bb5, %bb3, %bb
+  %tmp11 = phi float [ 1.000000e+00, %bb3 ], [ 0.000000e+00, %bb9 ], [ 1.000000e+00, %bb ], [ undef, %bb5 ]
+  call void @llvm.amdgcn.exp.f32(i32 immarg 40, i32 immarg 15, float %tmp11, float undef, float undef, float undef, i1 immarg false, i1 immarg false) #0
+  ret void
+}
+
+; Function Attrs: inaccessiblememonly nounwind
+declare void @llvm.amdgcn.exp.f32(i32 immarg, i32 immarg, float, float, float, float, i1 immarg, i1 immarg) #1
+
+attributes #0 = { nounwind }
+attributes #1 = { inaccessiblememonly nounwind }

test/CodeGen/AMDGPU/cse-phi-incoming-val.mir

+# RUN: llc -march=amdgcn -mcpu=gfx900 -run-pass machine-cse -verify-machineinstrs %s -o - | FileCheck -check-prefix=GCN %s
+
+# Check that the redundant immediate MOV instruction
+# (by-product of handling phi nodes) is not found
+# in the generated code due to CSE heuristic.
+
+# GCN-LABEL: name: cse_phi_incoming_val
+# GCN: bb.0:
+# GCN: V_MOV_B32_e32 1065353216
+# GCN: bb.1:
+# GCN-NOT: V_MOV_B32_e32 1065353216
+# GCN: bb.2:
+
+---
+name: cse_phi_incoming_val
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.1, %bb.6
+    liveins: $vgpr0, $sgpr0, $sgpr1
+    %5:sgpr_32 = COPY $sgpr1
+    %4:sgpr_32 = COPY $sgpr0
+    %3:vgpr_32 = COPY $vgpr0
+    %7:vgpr_32 = V_MOV_B32_e32 1065353216, implicit $exec
+    %8:sreg_32_xm0 = S_MOV_B32 0
+    S_CMP_LG_U32 %4:sgpr_32, killed %8:sreg_32_xm0, implicit-def $scc
+    S_CBRANCH_SCC1 %bb.6, implicit $scc
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.2, %bb.5
+
+    %9:vgpr_32 = V_MOV_B32_e32 1065353216, implicit $exec
+    %10:sreg_32_xm0 = S_MOV_B32 0
+    S_CMP_LG_U32 %5:sgpr_32, killed %10:sreg_32_xm0, implicit-def $scc
+    S_CBRANCH_SCC1 %bb.5, implicit $scc
+    S_BRANCH %bb.2
+
+  bb.2:
+    successors: %bb.3, %bb.4
+
+    %11:sreg_32_xm0 = S_MOV_B32 2
+    %12:vgpr_32 = V_LSHLREV_B32_e64 killed %11:sreg_32_xm0, %3:vgpr_32, implicit $exec
+    %24:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %23:vreg_64 = REG_SEQUENCE killed %12:vgpr_32, %subreg.sub0, killed %24:vgpr_32, %subreg.sub1
+    %26:sgpr_32 = V_READFIRSTLANE_B32 %23.sub0:vreg_64, implicit $exec
+    %27:sgpr_32 = V_READFIRSTLANE_B32 %23.sub1:vreg_64, implicit $exec
+    %25:sreg_64 = REG_SEQUENCE %26:sgpr_32, %subreg.sub0, %27:sgpr_32, %subreg.sub1
+    %15:sreg_32_xm0_xexec = S_LOAD_DWORD_IMM killed %25:sreg_64, 0, 0, 0 :: (load 4, addrspace 6)
+    %16:sreg_32_xm0 = S_MOV_B32 1
+    %18:vgpr_32 = COPY killed %16:sreg_32_xm0
+    %17:sreg_64 = V_CMP_NE_U32_e64 killed %15:sreg_32_xm0_xexec, %18:vgpr_32, implicit $exec
+    %0:sreg_64 = SI_IF killed %17:sreg_64, %bb.4, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.3
+
+  bb.3:
+    successors: %bb.4
+
+  bb.4:
+    successors: %bb.5
+
+    SI_END_CF %0:sreg_64, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
+    %19:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+
+  bb.5:
+    successors: %bb.6
+
+    %1:vgpr_32 = PHI %9:vgpr_32, %bb.1, %19:vgpr_32, %bb.4
+
+  bb.6:
+
+    %2:vgpr_32 = PHI %7:vgpr_32, %bb.0, %1:vgpr_32, %bb.5
+    %20:vgpr_32 = IMPLICIT_DEF
+    %21:vgpr_32 = IMPLICIT_DEF
+    %22:vgpr_32 = IMPLICIT_DEF
+    EXP 40, %2:vgpr_32, %20:vgpr_32, %21:vgpr_32, %22:vgpr_32, 0, 0, 15, implicit $exec
+    S_ENDPGM 0
+---
+

test/CodeGen/AMDGPU/multilevel-break.ll

 ; GCN: ; %Flow4
 ; GCN:      s_and_b64          [[BREAK:s\[[0-9]+:[0-9]+\]]], exec, [[BREAK]]
 ; GCN:      s_or_b64           [[LEFT]], [[BREAK]], [[OLD_LEFT:s\[[0-9]+:[0-9]+\]]]
 ; GCN:      s_andn2_b64        exec, exec, [[LEFT]]
 ; GCN-NEXT: s_cbranch_execz
 
 ; GCN: [[LOOP:BB[0-9]+_[0-9]+]]: ; %bb1{{$}}
 ; GCN:      s_mov_b64          [[OLD_LEFT]], [[LEFT]]
+; GCN:      s_mov_b64
 
 ; GCN: ; %LeafBlock1
-; GCN:      s_mov_b64
 ; GCN:      s_mov_b64          [[BREAK]], -1{{$}}
 
 ; GCN: ; %case1
 ; GCN:      buffer_load_dword  [[LOAD2:v[0-9]+]],
 ; GCN:      v_cmp_ge_i32_e32   vcc, {{v[0-9]+}}, [[LOAD2]]
 ; GCN:      s_orn2_b64         [[BREAK]], vcc, exec
 
 ; GCN: ; %Flow3