MachineSink: Fix sinking VGPR def out of a divergent loop

[arsenm]

Summary

This fixes sinking a VGPR def out of a loop past the reconvergence
point at the SI_END_CF. There was a prior fix which introduced
blockPrologueInterferes (D121277) to fix the same basic problem for
the post RA sink. This also had the special case isIgnorableUse case
which was incorrect, because in some contexts the exec use is not
ignorable.

I'm thinking of a new way to represent this which will avoid needing
hasIgnorableUse and isBasicBlockPrologue.

Fixes: SWDEV-407790

[nickdesaulniers]

Not sure what to make of that Fixes tag. The change to isInlineAsmBrIndirectTarget LGTM; unsure about the rest.

llvm/lib/CodeGen/MachineSink.cpp

1024

consider using const auto here.

[critson]

LGTM - but should probably have more eyes on it.

[rampitec]

LGTM

[arsenm]

3f8ef57bede94445b1a1042c987cc914a886e7ff

[ruiling]

llvm/test/CodeGen/AMDGPU/machine-sink-loop-var-out-of-divergent-loop-swdev407790.mir

54

Sorry I don't see why we are not allowed to sink such kind of loop-invariant v_add out of the loop. For this specific case, the result vgpr should be the same with and without the change, right?

[arsenm]

llvm/test/CodeGen/AMDGPU/machine-sink-loop-var-out-of-divergent-loop-swdev407790.mir

54

Maybe we could sink it if we introduced a new block before the reconvergence at si_end_cf.

This testcase has 2 loops, nested with unrelated conditions. By sinking here, it's sinking from the body of the first loop into the second loop. It now executes for lanes which would not have taken the inner loop

[ruiling]

llvm/test/CodeGen/AMDGPU/machine-sink-loop-var-out-of-divergent-loop-swdev407790.mir

54

I am not sure whether I read the CFG correctly. The bb.4 here is inside the inner loop, and the bb.5 is the reconvergence point for the inner loop. So all the lanes that are active after the SI_END_CF in bb.5 (restore the exec as before entering inner loop) should have been active in the inner loop (bb4).

[ruiling]

I think a more accurate description of the real problem is: sinking vgpr def which has a loop-variant sgpr source out of divergent loop is wrong for AMDGPU. For other cases, it is still legal to move out of loop. The problem is not specific to nested loops, it also applies to single loop. The test case has been over-simplified and does not show original problem (both .ll and .mir test). We can keep the code as now, but I still think it's better to update the tests to show the real problem to make it easy to revisit the issue.

[arsenm]

In D155343#4517032, @ruiling wrote:

I think a more accurate description of the real problem is: sinking vgpr def which has a loop-variant sgpr source out of divergent loop is wrong for AMDGPU. For other cases, it is still legal to move out of loop. The problem is not specific to nested loops, it also applies to single loop. The test case has been over-simplified and does not show original problem (both .ll and .mir test). We can keep the code as now, but I still think it's better to update the tests to show the real problem to make it easy to revisit the issue.

What do you suggest? I think we need to come up with a way to properly model this

[arsenm]

In D155343#4520753, @arsenm wrote:

In D155343#4517032, @ruiling wrote:

I think a more accurate description of the real problem is: sinking vgpr def which has a loop-variant sgpr source out of divergent loop is wrong for AMDGPU. For other cases, it is still legal to move out of loop. The problem is not specific to nested loops, it also applies to single loop. The test case has been over-simplified and does not show original problem (both .ll and .mir test). We can keep the code as now, but I still think it's better to update the tests to show the real problem to make it easy to revisit the issue.

What do you suggest? I think we need to come up with a way to properly model this

I was thinking about something along the lines of marking basic block edges as read or write convergent, and then adding some notion of read/write convergence that approximately means VALU, VALU cross lane, scalar or divergent control flow

llvm/lib/CodeGen/MachineSink.cpp

if (!TII->isBasicBlockPrologue(*PI))
       continue;
     for (auto &MO : MI.operands()) {
       if (!MO.isReg())
         continue;
       Register Reg = MO.getReg();
       if (!Reg)
         continue;
       if (MO.isUse()) {
-        if (Reg.isPhysical() &&
-            (TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(Reg))))
+        if (Reg.isPhysical() && MRI && MRI->isConstantPhysReg(Reg))
           continue;
         if (PI->modifiesRegister(Reg, TRI))
           return true;
       } else {
         if (PI->readsRegister(Reg, TRI))
           return true;
         // Check for interference with non-dead defs
         auto *DefOp = PI->findRegisterDefOperand(Reg, false, true, TRI);
for (const MachineOperand &MO : MI.operands()) {
     }
   }
 
   // It is not possible to sink an instruction into its own block.  This can
   // happen with cycles.
   if (MBB == SuccToSinkTo)
     return nullptr;
 
+  if (!SuccToSinkTo)
+    return nullptr;
+
   // It's not safe to sink instructions to EH landing pad. Control flow into
   // landing pad is implicitly defined.
-  if (SuccToSinkTo && SuccToSinkTo->isEHPad())
+  if (SuccToSinkTo->isEHPad())
     return nullptr;
 
   // It ought to be okay to sink instructions into an INLINEASM_BR target, but
   // only if we make sure that MI occurs _before_ an INLINEASM_BR instruction in
   // the source block (which this code does not yet do). So for now, forbid
   // doing so.
-  if (SuccToSinkTo && SuccToSinkTo->isInlineAsmBrIndirectTarget())
+  if (SuccToSinkTo->isInlineAsmBrIndirectTarget())
+    return nullptr;
+
+  MachineBasicBlock::const_iterator InsertPos =
+      SuccToSinkTo->SkipPHIsAndLabels(SuccToSinkTo->begin());
+  if (blockPrologueInterferes(SuccToSinkTo, InsertPos, MI, TRI, TII, MRI))
     return nullptr;
 
   return SuccToSinkTo;
 }
 
 /// Return true if MI is likely to be usable as a memory operation by the
 /// implicit null check optimization.
 ///

llvm/test/CodeGen/AMDGPU/machine-sink-loop-var-out-of-divergent-loop-swdev407790.ll

 ; CHECK-NEXT:    v_cmp_eq_u32_e32 vcc_lo, 1, v3
 ; CHECK-NEXT:    s_xor_b32 s6, s4, -1
 ; CHECK-NEXT:    s_inst_prefetch 0x1
 ; CHECK-NEXT:    s_branch .LBB0_3
 ; CHECK-NEXT:    .p2align 6
 ; CHECK-NEXT:  .LBB0_1: ; %Flow
 ; CHECK-NEXT:    ; in Loop: Header=BB0_3 Depth=1
 ; CHECK-NEXT:    s_or_b32 exec_lo, exec_lo, s8
-; CHECK-NEXT:    v_add_nc_u32_e32 v4, -4, v4
 ; CHECK-NEXT:  .LBB0_2: ; %Flow1
 ; CHECK-NEXT:    ; in Loop: Header=BB0_3 Depth=1
 ; CHECK-NEXT:    s_or_b32 exec_lo, exec_lo, s7
 ; CHECK-NEXT:    v_cmp_ne_u32_e64 s4, 0, v3
 ; CHECK-NEXT:    ;;#ASMSTART
 ; CHECK-NEXT:    ; j lastloop entry
 ; CHECK-NEXT:    ;;#ASMEND
 ; CHECK-NEXT:    s_or_b32 s5, s4, s5

 ; CHECK-NEXT:    ; in Loop: Header=BB0_6 Depth=2
 ; CHECK-NEXT:    s_or_b32 exec_lo, exec_lo, s4
 ; CHECK-NEXT:    s_add_i32 s9, s9, 4
 ; CHECK-NEXT:    ;;#ASMSTART
 ; CHECK-NEXT:    ; backedge
 ; CHECK-NEXT:    ;;#ASMEND
 ; CHECK-NEXT:    v_add_nc_u32_e32 v4, s9, v2
 ; CHECK-NEXT:    v_cmp_ge_u32_e64 s4, v4, v0
+; CHECK-NEXT:    v_add_nc_u32_e32 v4, -4, v4
 ; CHECK-NEXT:    s_or_b32 s8, s4, s8
 ; CHECK-NEXT:    s_andn2_b32 exec_lo, exec_lo, s8
 ; CHECK-NEXT:    s_cbranch_execz .LBB0_1
 ; CHECK-NEXT:  .LBB0_6: ; %for.body51
 ; CHECK-NEXT:    ; Parent Loop BB0_3 Depth=1
 ; CHECK-NEXT:    ; => This Inner Loop Header: Depth=2
 ; CHECK-NEXT:    v_mov_b32_e32 v3, 1
 ; CHECK-NEXT:    s_and_saveexec_b32 s4, vcc_lo

llvm/test/CodeGen/AMDGPU/machine-sink-loop-var-out-of-divergent-loop-swdev407790.mir

body:             |
   ; CHECK-NEXT:   successors: %bb.4(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   S_NOP 0
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.4:
   ; CHECK-NEXT:   successors: %bb.2(0x40000000), %bb.5(0x40000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */
+  ; CHECK-NEXT:   [[V_ADD_U32_e64_:%[0-9]+]]:vgpr_32 = V_ADD_U32_e64 [[COPY]], [[COPY1]], 0, implicit $exec
   ; CHECK-NEXT:   [[SI_IF_BREAK:%[0-9]+]]:sreg_32 = SI_IF_BREAK killed [[SI_IF1]], [[SI_IF]], implicit-def dead $scc
   ; CHECK-NEXT:   SI_LOOP [[SI_IF_BREAK]], %bb.2, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
   ; CHECK-NEXT:   S_BRANCH %bb.5
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.5:
   ; CHECK-NEXT:   successors: %bb.2(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[PHI:%[0-9]+]]:vgpr_32 = PHI [[COPY]], %bb.4
   ; CHECK-NEXT:   SI_END_CF [[SI_IF_BREAK]], implicit-def dead $exec, implicit-def dead $scc, implicit $exec
-  ; CHECK-NEXT:   [[V_ADD_U32_e64_:%[0-9]+]]:vgpr_32 = V_ADD_U32_e64 [[COPY]], [[COPY1]], 0, implicit $exec
   ; CHECK-NEXT:   INLINEASM &"", 1 /* sideeffect attdialect */, implicit [[V_ADD_U32_e64_]]
   ; CHECK-NEXT:   S_BRANCH %bb.2
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.6:
   ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.7(0x40000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   SI_LOOP [[SI_IF]], %bb.1, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
   ; CHECK-NEXT:   S_BRANCH %bb.7

llvm/test/CodeGen/AMDGPU/sink-after-control-flow.mir

machineFunctionInfo:
   isEntryFunction: true
 body:             |
   ; GFX10-LABEL: name: _amdgpu_hs_main
   ; GFX10: bb.0:
   ; GFX10-NEXT:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT:   [[DEF:%[0-9]+]]:vgpr_32 = IMPLICIT_DEF
   ; GFX10-NEXT:   [[S_MOV_B32_:%[0-9]+]]:sreg_32 = S_MOV_B32 8
+  ; GFX10-NEXT:   [[V_LSHRREV_B32_e64_:%[0-9]+]]:vgpr_32 = V_LSHRREV_B32_e64 [[S_MOV_B32_]], [[DEF]], implicit $exec
   ; GFX10-NEXT:   [[V_BFE_U32_e64_:%[0-9]+]]:vgpr_32 = V_BFE_U32_e64 [[DEF]], 8, 5, implicit $exec
   ; GFX10-NEXT:   [[S_MOV_B32_1:%[0-9]+]]:sreg_32 = S_MOV_B32 5
   ; GFX10-NEXT:   [[V_CMP_NE_U32_e64_:%[0-9]+]]:sreg_32 = V_CMP_NE_U32_e64 [[V_BFE_U32_e64_]], killed [[S_MOV_B32_1]], implicit $exec
   ; GFX10-NEXT:   [[S_XOR_B32_:%[0-9]+]]:sreg_32 = S_XOR_B32 [[V_CMP_NE_U32_e64_]], -1, implicit-def $scc
   ; GFX10-NEXT:   [[S_AND_B32_:%[0-9]+]]:sreg_32 = S_AND_B32 [[S_XOR_B32_]], $exec_lo, implicit-def $scc
   ; GFX10-NEXT:   [[S_XOR_B32_1:%[0-9]+]]:sreg_32 = S_XOR_B32 $exec_lo, [[S_AND_B32_]], implicit-def $scc
   ; GFX10-NEXT:   $exec_lo = S_MOV_B32_term [[S_AND_B32_]]
   ; GFX10-NEXT:   S_CBRANCH_EXECZ %bb.2, implicit $exec
   ; GFX10-NEXT:   S_BRANCH %bb.1
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT: bb.1:
   ; GFX10-NEXT:   successors: %bb.2(0x80000000)
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT:   [[DEF1:%[0-9]+]]:sgpr_32 = IMPLICIT_DEF
   ; GFX10-NEXT:   S_BRANCH %bb.2
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT: bb.2:
   ; GFX10-NEXT:   successors: %bb.3(0x40000000), %bb.4(0x40000000)
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT:   $exec_lo = S_OR_B32 $exec_lo, [[S_XOR_B32_1]], implicit-def $scc
-  ; GFX10-NEXT:   [[V_LSHRREV_B32_e64_:%[0-9]+]]:vgpr_32 = V_LSHRREV_B32_e64 [[S_MOV_B32_]], [[DEF]], implicit $exec
   ; GFX10-NEXT:   [[S_MOV_B32_2:%[0-9]+]]:sreg_32 = S_MOV_B32 31
   ; GFX10-NEXT:   [[V_CMP_NE_U32_e64_1:%[0-9]+]]:sreg_32 = V_CMP_NE_U32_e64 [[V_BFE_U32_e64_]], killed [[S_MOV_B32_2]], implicit $exec
   ; GFX10-NEXT:   [[S_XOR_B32_2:%[0-9]+]]:sreg_32 = S_XOR_B32 [[V_CMP_NE_U32_e64_1]], -1, implicit-def $scc
   ; GFX10-NEXT:   [[S_AND_B32_1:%[0-9]+]]:sreg_32 = S_AND_B32 [[S_XOR_B32_2]], $exec_lo, implicit-def $scc
   ; GFX10-NEXT:   [[S_XOR_B32_3:%[0-9]+]]:sreg_32 = S_XOR_B32 $exec_lo, [[S_AND_B32_1]], implicit-def $scc
   ; GFX10-NEXT:   $exec_lo = S_MOV_B32_term [[S_AND_B32_1]]
   ; GFX10-NEXT:   S_CBRANCH_EXECZ %bb.4, implicit $exec
   ; GFX10-NEXT:   S_BRANCH %bb.3