AMDGPU: Fix LiveVariables error after lowering SI_END_CF

[arsenm]

Summary

This wasn't accounting for the block change in updating LiveVariables.

[arsenm]

Drop leftover test

[foad]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

516

Would it make sense to move this code into splitAt, i.e. have it update LV just like it updates LIS?

522

This is a shame. isPHIJoin hasn't been used since rGfac770b865f59cbe615241dad153ad20d5138b9e 9 years ago and I was hoping to remove it.

526

Why do you only need to do this for phi join regs? Couldn't any random register have its last use in SplitBB?

[arsenm]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

516

Probably

522

Well we were hoping to remove LiveVariables completely, so I'm not worried about using a specific piece of it.

526

I derived this based on the phi representation described in the comment for VarInfo. Other registers should have the block already in AliveBlocks

[foad]

Why do you only need to do this for phi join regs? Couldn't any random register have its last use in SplitBB?

I was thinking of a case like this:

---
name:            phi_visit_order
tracksRegLiveness: true
body:             |
  bb.0:
    successors: %bb.3(0x40000000), %bb.1(0x40000000)
    liveins: $vgpr0
  
    %0:vgpr_32 = COPY killed $vgpr0
    %1:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, killed %0, implicit $exec
    %3:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
    S_BRANCH %bb.3
  
  bb.1:
    successors: %bb.2(0x80000000)
  
    %4:sreg_64_xexec = PHI %5, %bb.3, %3, %bb.0
    %6:vgpr_32 = PHI %7, %bb.3, %1, %bb.0
    S_BRANCH %bb.2
  
  bb.2:
    successors: %bb.3(0x80000000)
  
    %8:sreg_64_xexec = COPY %4
    SI_END_CF killed %8, implicit-def $exec, implicit-def dead $scc, implicit $exec
    %9:vgpr_32 = nsw V_ADD_U32_e32 1, killed %6, implicit $exec
  
  bb.3:
    successors: %bb.3(0x40000000), %bb.1(0x40000000)
  
    %10:vgpr_32 = PHI %9, %bb.2, %7, %bb.3, %1, %bb.0
    GLOBAL_STORE_DWORD undef %11:vreg_64, %10, 0, 0, implicit $exec :: (volatile store (s32), addrspace 1)
    %7:vgpr_32 = COPY killed %10
    %5:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
    S_BRANCH %bb.3

...

Here %4 which is not a phi join reg has its last use in bb.2. When bb.2 is split into MBB/SplitBB, %4 will be live through MBB. Rather than testing for phi join regs I think you want to do it for any register that is live into MBB.

[ruiling]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

60–87

Could you show me the .ll and the llc command to reproduce the issue? the test has irreducible control flow, something must be wrong in early pass.

[arsenm]

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

60–87

You hit this failure by adding -global-isel to test/CodeGen/AMDGPU/salu-to-valu.ll. GlobalISel avoids some extra copies the DAG happens to emit, which (correctly) allows for tail duplicating the SI_IF. We can't rely on reducible control flow or specific instruction+control flow patterns being preserved

[arsenm]

Fix Jay's testcase. We need to avoid adding registers to the block that are only live in one block

[ruiling]

I would hope we can move the block split logic into a separate pass that can be scheduled before we constructing liveness information, like during addPreRegAlloc(). It is expensive to update either LiveVariables or LiveIntervals. Sounds good?

[arsenm]

In D117796#3274452, @ruiling wrote:

I would hope we can move the block split logic into a separate pass that can be scheduled before we constructing liveness information, like during addPreRegAlloc(). It is expensive to update either LiveVariables or LiveIntervals. Sounds good?

The whole reason this pass is here is because it needs to be done after phi elimination, so you can't really move it anywhere else. LiveVariables we should also just be pushing to eliminate entirely

[ruiling]

In D117796#3274453, @arsenm wrote:

In D117796#3274452, @ruiling wrote:

I would hope we can move the block split logic into a separate pass that can be scheduled before we constructing liveness information, like during addPreRegAlloc(). It is expensive to update either LiveVariables or LiveIntervals. Sounds good?

The whole reason this pass is here is because it needs to be done after phi elimination, so you can't really move it anywhere else. LiveVariables we should also just be pushing to eliminate entirely

I think block split itself could be done before phi elimination. If you detect the source operand of SI_END_CF defined in the same block, you can split the block. That works just like what we are doing now. Did I miss something? Even you deprecate LiveVariables, you still need to update LiveIntervals, it still need to searching against all virtual registers to see whose LiveInterval need updated.

[ruiling]

In D117796#3274477, @ruiling wrote:

In D117796#3274453, @arsenm wrote:

In D117796#3274452, @ruiling wrote:

I would hope we can move the block split logic into a separate pass that can be scheduled before we constructing liveness information, like during addPreRegAlloc(). It is expensive to update either LiveVariables or LiveIntervals. Sounds good?

The whole reason this pass is here is because it needs to be done after phi elimination, so you can't really move it anywhere else. LiveVariables we should also just be pushing to eliminate entirely

I think block split itself could be done before phi elimination. If you detect the source operand of SI_END_CF defined in the same block, you can split the block. That works just like what we are doing now. Did I miss something? Even you deprecate LiveVariables, you still need to update LiveIntervals, it still need to searching against all virtual registers to see whose LiveInterval need updated.

Sounds like LiveIntervals does not need expensive update?

[ruiling]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

531

Is it possible that a value defined in MBB (and kept in MBB after split) and killed in successor block, now becomes alive in SplitBB?

[arsenm]

In D117796#3274477, @ruiling wrote:

In D117796#3274453, @arsenm wrote:

In D117796#3274452, @ruiling wrote:

I would hope we can move the block split logic into a separate pass that can be scheduled before we constructing liveness information, like during addPreRegAlloc(). It is expensive to update either LiveVariables or LiveIntervals. Sounds good?

The whole reason this pass is here is because it needs to be done after phi elimination, so you can't really move it anywhere else. LiveVariables we should also just be pushing to eliminate entirely

I think block split itself could be done before phi elimination. If you detect the source operand of SI_END_CF defined in the same block, you can split the block. That works just like what we are doing now. Did I miss something?

The reason we are splitting the block is so we can place the exec modification before the copies for lowered phis. We cannot split the block as needed while the phis still exist since phis need to be the first instructions in the block

[arsenm]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

531

That's covered by updating the Killed set, replaceKillInstruction

[ruiling]

The reason we are splitting the block is so we can place the exec modification before the copies for lowered phis. We cannot split the block as needed while the phis still exist since phis need to be the first instructions in the block

I don't understand, we are moving out instructions after SI_END_CF into a new block, all the PHIs and SI_END_CF will still be in the old block. Why are we breaking the phis?
To make it clear, I am not strongly asking for this now. I am fine with fixing the LiveVariable update issue.

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

531

It is something like below after split:

MBB:
  %a = PHI ... // this will be lowered into COPY after phi-elim
 ...
SplitBB:
  ...
Succ:
  use(%a)

%a is not the source of SI_END_CF, here we need to insert SplitBB into AliveBlocks of %a.

[arsenm]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

531

The lowered SI_END_CF is not inserted at its original position in the block. It is moved to the top of the block, moving it before the phis which were lowered

[ruiling]

LGTM

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

531

I missed the trick we have already reordered the instructions during phi elimination. The only COPY comes before SI_END_CF is the one that generate source of SI_END_CF.

[arsenm]

6071c92768a43b838a2eda3c5ee8d0e6b1b0d748

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

if (NeedBlockSplit) {
     Opcode = OrTermrOpc;
     InsPt = MI;
   }
 
   MachineInstr *NewMI =
     BuildMI(MBB, InsPt, DL, TII->get(Opcode), Exec)
     .addReg(Exec)
     .add(MI.getOperand(0));
-  if (LV)
-    LV->replaceKillInstruction(MI.getOperand(0).getReg(), MI, *NewMI);
+  if (LV) {
+    LV->replaceKillInstruction(DataReg, MI, *NewMI);
+
+    if (SplitBB != &MBB) {
+      for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+        Register Reg = Register::index2VirtReg(i);
+        LiveVariables::VarInfo &VI = LV->getVarInfo(Reg);
+
+        if (VI.AliveBlocks.test(MBB.getNumber()))
+          VI.AliveBlocks.set(SplitBB->getNumber());
+        else if (LV->isPHIJoin(Reg)) {
+          // Pass through live phis
+          for (MachineInstr *Kill : VI.Kills)
+            if (Kill->getParent() == SplitBB)
+              VI.AliveBlocks.set(MBB.getNumber());
+        }
+      }
+    }
+  }
 
   LoweredEndCf.insert(NewMI);
 
   if (LIS)
     LIS->ReplaceMachineInstrInMaps(MI, *NewMI);
 
   MI.eraseFromParent();
 
   if (LIS)

llvm/test/CodeGen/AMDGPU/lower-control-flow-live-variables-update.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=amdgcn-amd-amdhsa -start-before=livevars -stop-after=twoaddressinstruction -verify-machineinstrs -o - %s | FileCheck %s
+
+# FIXME: update_mir_test_checks tries to incorrectly re-use a variable
+# name used for a copy, so some of the check variable names were
+# manually fixed.
+
+# Check for LiveVariables verifier error after lowering SI_END_CF
+
+---
+name:            phi_visit_order
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: phi_visit_order
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK-NEXT:   liveins: $vgpr0
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:vgpr_32 = COPY killed $vgpr0
+  ; CHECK-NEXT:   [[V_MOV_B32_e32_:%[0-9]+]]:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+  ; CHECK-NEXT:   [[V_CMP_EQ_U32_e64_:%[0-9]+]]:sreg_64_xexec = V_CMP_EQ_U32_e64 0, killed [[COPY]], implicit $exec
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:vgpr_32 = COPY [[V_MOV_B32_e32_]]
+  ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:vgpr_32 = COPY killed [[V_MOV_B32_e32_]]
+  ; CHECK-NEXT:   [[COPY3:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
+  ; CHECK-NEXT:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY3]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
+  ; CHECK-NEXT:   [[S_XOR_B64_:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_]], [[COPY3]], implicit-def dead $scc
+  ; CHECK-NEXT:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
+  ; CHECK-NEXT:   [[S_MOV_B64_term:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[S_XOR_B64_]], implicit $exec
+  ; CHECK-NEXT:   S_CBRANCH_EXECZ %bb.1, implicit $exec
+  ; CHECK-NEXT:   S_BRANCH %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY4:%[0-9]+]]:sreg_64_xexec = COPY killed [[S_MOV_B64_term]]
+  ; CHECK-NEXT:   $exec = S_OR_B64_term $exec, killed [[COPY4]], implicit-def $scc
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY5:%[0-9]+]]:vgpr_32 = COPY killed [[COPY1]]
+  ; CHECK-NEXT:   [[V_ADD_U32_e32_:%[0-9]+]]:vgpr_32 = nsw V_ADD_U32_e32 1, killed [[COPY5]], implicit $exec
+  ; CHECK-NEXT:   [[COPY6:%[0-9]+]]:vgpr_32 = COPY killed [[V_ADD_U32_e32_]]
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY66:%[0-9]+]]:vgpr_32 = COPY killed [[COPY6]]
+  ; CHECK-NEXT:   GLOBAL_STORE_DWORD undef %10:vreg_64, [[COPY66]], 0, 0, implicit $exec :: (volatile store (s32), addrspace 1)
+  ; CHECK-NEXT:   [[COPY7:%[0-9]+]]:vgpr_32 = COPY killed [[COPY66]]
+  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:vgpr_32 = COPY [[COPY7]]
+  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:vgpr_32 = COPY killed [[COPY7]]
+  ; CHECK-NEXT:   [[COPY8:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
+  ; CHECK-NEXT:   [[S_AND_B64_1:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY8]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
+  ; CHECK-NEXT:   [[S_XOR_B64_1:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_1]], [[COPY8]], implicit-def dead $scc
+  ; CHECK-NEXT:   $exec = S_MOV_B64_term killed [[S_AND_B64_1]]
+  ; CHECK-NEXT:   [[S_MOV_B64_term1:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[S_XOR_B64_1]], implicit $exec
+  ; CHECK-NEXT:   S_CBRANCH_EXECZ %bb.1, implicit $exec
+  ; CHECK-NEXT:   S_BRANCH %bb.2
+  bb.0:
+    successors: %bb.2(0x40000000), %bb.1(0x40000000)
+    liveins: $vgpr0
+
+    %0:vgpr_32 = COPY killed $vgpr0
+    %1:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, killed %0, implicit $exec
+    %3:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+
+    %4:sreg_64_xexec = PHI %5, %bb.2, %3, %bb.0
+    %6:vgpr_32 = PHI %7, %bb.2, %1, %bb.0
+    SI_END_CF killed %4, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    %8:vgpr_32 = nsw V_ADD_U32_e32 1, killed %6, implicit $exec
+
+  bb.2:
+    successors: %bb.2(0x40000000), %bb.1(0x40000000)
+
+    %9:vgpr_32 = PHI %8, %bb.1, %7, %bb.2, %1, %bb.0
+    GLOBAL_STORE_DWORD undef %10:vreg_64, %9, 0, 0, implicit $exec :: (volatile store (s32), addrspace 1)
+    %7:vgpr_32 = COPY killed %9
+    %5:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    S_BRANCH %bb.2
+
+...