Machine verifier failure because of register-coalescer - involving sub-registers

[petar-avramovic]

When register-coalescer merges small registers into big, some sub-registers end up being undefined in some paths.
short.mir.txt
short.ll.txt

llc -march=amdgcn -mcpu=gfx1010 -verify-machineinstrs short.ll -o -
llc -march=amdgcn -mcpu=gfx1010 -run-pass=register-coalescer -start-before=register-coalescer -verify-machineinstrs short.mir -o -

llc -march=amdgcn -mcpu=gfx1010 -run-pass=register-coalescer -debug short.mir -o -

      bb.0:
        successors: %bb.2(0x50000000), %bb.1(0x30000000)
        liveins: $sgpr0_sgpr1_sgpr2_sgpr3, $sgpr4

        %0:sgpr_128 = COPY $sgpr0_sgpr1_sgpr2_sgpr3
        %1:sreg_32 = COPY $sgpr4
        S_CMP_EQ_U32 killed %1, 0, implicit-def $scc
        S_CBRANCH_SCC0 %bb.2, implicit killed $scc

      bb.1:
        successors: %bb.3(0x80000000)

        %2:vgpr_32 = IMPLICIT_DEF
        %3:vgpr_32 = IMPLICIT_DEF
        %4:vgpr_32 = IMPLICIT_DEF
        %5:vgpr_32 = IMPLICIT_DEF
        S_BRANCH %bb.3

      bb.2:
        successors: %bb.3(0x80000000)

        %6:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
        %7:vreg_128 = BUFFER_LOAD_FORMAT_XYZW_IDXEN killed %6, killed %0, 0, 0, 0, 0, implicit $exec :: (dereferenceable load (<4 x s32>), align 1, addrspace 8)
        %2:vgpr_32 = COPY %7.sub0
        %3:vgpr_32 = COPY %7.sub1
        %4:vgpr_32 = COPY %7.sub2
        %5:vgpr_32 = COPY killed %7.sub3

      bb.3:
        EXP_DONE 0, killed %2, killed %3, killed %4, killed %5, -1, 0, 15, implicit $exec
        S_ENDPGM 0

$ llc -march=amdgcn -mcpu=gfx1010 -o - short.mir -run-pass=register-coalescer -debug

In short.mir Register Coalescer tries to combine registers %2:vgpr_32, %3:vgpr_32, %4:vgpr_32, %5:vgpr_32 with %7:vreg_128.
In bb.1, instructions:

%2:vgpr_32 = IMPLICIT_DEF
%3:vgpr_32 = IMPLICIT_DEF
%4:vgpr_32 = IMPLICIT_DEF
%5:vgpr_32 = IMPLICIT_DEF

are converted to only one instruction. %2 in %7:sub0 are merged and first instruction is updated to:

undef %7.sub0:vreg_128 = IMPLICIT_DEF

but after others get merged their IMPLICIT_DEFs get deleted.

      bb.0:
        successors: %bb.2(0x50000000), %bb.1(0x30000000)
        liveins: $sgpr0_sgpr1_sgpr2_sgpr3, $sgpr4
      
        %0:sgpr_128 = COPY $sgpr0_sgpr1_sgpr2_sgpr3
        %1:sreg_32 = COPY $sgpr4
        S_CMP_EQ_U32 %1, 0, implicit-def $scc
        S_CBRANCH_SCC0 %bb.2, implicit killed $scc
      
      bb.1:
        successors: %bb.3(0x80000000)
      
        undef %7.sub0:vreg_128 = IMPLICIT_DEF
        S_BRANCH %bb.3
      
      bb.2:
        successors: %bb.3(0x80000000)
      
        %6:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
        %7:vreg_128 = BUFFER_LOAD_FORMAT_XYZW_IDXEN %6, %0, 0, 0, 0, 0, implicit $exec :: (dereferenceable load (<4 x s32>), align 1, addrspace 8)
      
      bb.3:
        EXP_DONE 0, %7.sub0, %7.sub1, %7.sub2, %7.sub3, -1, 0, 15, implicit $exec
        S_ENDPGM 0

in path bb.0 -> bb.1 -> bb.3 %7.sub1, %7.sub2, %7.sub3 are undefined. This does not cause Machine Verifier failure(yet).
Tail Duplication moves EXP_DONE from bb.3 into bb.2 and more importantly bb.1:

    # After Tail Duplication
    # Machine code for function test: NoPHIs, TracksLiveness, NoVRegs, TracksDebugUserValues

    bb.0:
      successors: %bb.2(0x50000000), %bb.1(0x30000000); %bb.2(62.50%), %bb.1(37.50%)
      liveins: $sgpr4, $sgpr0_sgpr1_sgpr2_sgpr3
      S_CMP_EQ_U32 killed renamable $sgpr4, 0, implicit-def $scc
      S_CBRANCH_SCC0 %bb.2, implicit killed $scc

    bb.1:
    ; predecessors: %bb.0

      renamable $vgpr0 = IMPLICIT_DEF
      EXP_DONE 0, killed renamable $vgpr0, renamable $vgpr1, renamable $vgpr2, renamable $vgpr3, -1, 0, 15, implicit $exec
      S_ENDPGM 0

    bb.2:
    ; predecessors: %bb.0
      liveins: $sgpr0_sgpr1_sgpr2_sgpr3
      renamable $vgpr0 = V_MOV_B32_e32 0, implicit $exec
      renamable $vgpr0_vgpr1_vgpr2_vgpr3 = BUFFER_LOAD_FORMAT_XYZW_IDXEN killed renamable $vgpr0, killed renamable $sgpr0_sgpr1_sgpr2_sgpr3, 0, 0, 0, 0, implicit $exec :: (dereferenceable load (<4 x s32>), align 1, addrspace 8)
      EXP_DONE 0, killed renamable $vgpr0, renamable $vgpr1, renamable $vgpr2, renamable $vgpr3, -1, 0, 15, implicit $exec
      S_ENDPGM 0

    # End machine code for function test.

This causes machine verifier to fail for $vgpr1, $vgpr2, $vgpr3

*** Bad machine code: Using an undefined physical register ***

• function: test
• basic block: %bb.1 (0x569b4a93c240)
• instruction: EXP_DONE 0, killed renamable $vgpr0, renamable $vgpr1, renamable $vgpr2, renamable $vgpr3, -1, 0, 15, implicit $exec
• operand 2: renamable $vgpr1an undefined physical register ***

[llvmbot]

@llvm/issue-subscribers-backend-amdgpu

Author: Petar Avramovic (petar-avramovic)

When register-coalescer merges small registers into big, some sub-registers end up being undefined in some paths. [short.mir.txt](https://github.com/user-attachments/files/16177318/short.mir.txt) [short.ll.txt](https://github.com/user-attachments/files/16177319/short.ll.txt)

llc -march=amdgcn -mcpu=gfx1010 -verify-machineinstrs short.ll -o -
llc -march=amdgcn -mcpu=gfx1010 -run-pass=register-coalescer -start-before=register-coalescer -verify-machineinstrs short.mir -o -

llc -march=amdgcn -mcpu=gfx1010 -run-pass=register-coalescer -debug short.mir -o -

      bb.0:
        successors: %bb.2(0x50000000), %bb.1(0x30000000)
        liveins: $sgpr0_sgpr1_sgpr2_sgpr3, $sgpr4

        %0:sgpr_128 = COPY $sgpr0_sgpr1_sgpr2_sgpr3
        %1:sreg_32 = COPY $sgpr4
        S_CMP_EQ_U32 killed %1, 0, implicit-def $scc
        S_CBRANCH_SCC0 %bb.2, implicit killed $scc

      bb.1:
        successors: %bb.3(0x80000000)

        %2:vgpr_32 = IMPLICIT_DEF
        %3:vgpr_32 = IMPLICIT_DEF
        %4:vgpr_32 = IMPLICIT_DEF
        %5:vgpr_32 = IMPLICIT_DEF
        S_BRANCH %bb.3

      bb.2:
        successors: %bb.3(0x80000000)

        %6:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
        %7:vreg_128 = BUFFER_LOAD_FORMAT_XYZW_IDXEN killed %6, killed %0, 0, 0, 0, 0, implicit $exec :: (dereferenceable load (<4 x s32>), align 1, addrspace 8)
        %2:vgpr_32 = COPY %7.sub0
        %3:vgpr_32 = COPY %7.sub1
        %4:vgpr_32 = COPY %7.sub2
        %5:vgpr_32 = COPY killed %7.sub3

      bb.3:
        EXP_DONE 0, killed %2, killed %3, killed %4, killed %5, -1, 0, 15, implicit $exec
        S_ENDPGM 0

$ llc -march=amdgcn -mcpu=gfx1010 -o - short.mir -run-pass=register-coalescer -debug

In short.mir Register Coalescer tries to combine registers %2:vgpr_32, %3:vgpr_32, %4:vgpr_32, %5:vgpr_32 with %7:vreg_128.
In bb.1, instructions:

%2:vgpr_32 = IMPLICIT_DEF
%3:vgpr_32 = IMPLICIT_DEF
%4:vgpr_32 = IMPLICIT_DEF
%5:vgpr_32 = IMPLICIT_DEF

are converted to only one instruction. %2 in %7:sub0 are merged and first instruction is updated to:

undef %7.sub0:vreg_128 = IMPLICIT_DEF

but after others get merged their IMPLICIT_DEFs get deleted.

      bb.0:
        successors: %bb.2(0x50000000), %bb.1(0x30000000)
        liveins: $sgpr0_sgpr1_sgpr2_sgpr3, $sgpr4
      
        %0:sgpr_128 = COPY $sgpr0_sgpr1_sgpr2_sgpr3
        %1:sreg_32 = COPY $sgpr4
        S_CMP_EQ_U32 %1, 0, implicit-def $scc
        S_CBRANCH_SCC0 %bb.2, implicit killed $scc
      
      bb.1:
        successors: %bb.3(0x80000000)
      
        undef %7.sub0:vreg_128 = IMPLICIT_DEF
        S_BRANCH %bb.3
      
      bb.2:
        successors: %bb.3(0x80000000)
      
        %6:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
        %7:vreg_128 = BUFFER_LOAD_FORMAT_XYZW_IDXEN %6, %0, 0, 0, 0, 0, implicit $exec :: (dereferenceable load (<4 x s32>), align 1, addrspace 8)
      
      bb.3:
        EXP_DONE 0, %7.sub0, %7.sub1, %7.sub2, %7.sub3, -1, 0, 15, implicit $exec
        S_ENDPGM 0

in path bb.0 -> bb.1 -> bb.3 %7.sub1, %7.sub2, %7.sub3 are undefined. This does not cause Machine Verifier failure(yet).
Tail Duplication moves EXP_DONE from bb.3 into bb.2 and more importantly bb.1:

    # After Tail Duplication
    # Machine code for function test: NoPHIs, TracksLiveness, NoVRegs, TracksDebugUserValues

    bb.0:
      successors: %bb.2(0x50000000), %bb.1(0x30000000); %bb.2(62.50%), %bb.1(37.50%)
      liveins: $sgpr4, $sgpr0_sgpr1_sgpr2_sgpr3
      S_CMP_EQ_U32 killed renamable $sgpr4, 0, implicit-def $scc
      S_CBRANCH_SCC0 %bb.2, implicit killed $scc

    bb.1:
    ; predecessors: %bb.0

      renamable $vgpr0 = IMPLICIT_DEF
      EXP_DONE 0, killed renamable $vgpr0, renamable $vgpr1, renamable $vgpr2, renamable $vgpr3, -1, 0, 15, implicit $exec
      S_ENDPGM 0

    bb.2:
    ; predecessors: %bb.0
      liveins: $sgpr0_sgpr1_sgpr2_sgpr3
      renamable $vgpr0 = V_MOV_B32_e32 0, implicit $exec
      renamable $vgpr0_vgpr1_vgpr2_vgpr3 = BUFFER_LOAD_FORMAT_XYZW_IDXEN killed renamable $vgpr0, killed renamable $sgpr0_sgpr1_sgpr2_sgpr3, 0, 0, 0, 0, implicit $exec :: (dereferenceable load (<4 x s32>), align 1, addrspace 8)
      EXP_DONE 0, killed renamable $vgpr0, renamable $vgpr1, renamable $vgpr2, renamable $vgpr3, -1, 0, 15, implicit $exec
      S_ENDPGM 0

    # End machine code for function test.

This causes machine verifier to fail for $vgpr1, $vgpr2, $vgpr3

*** Bad machine code: Using an undefined physical register ***

• function: test
• basic block: %bb.1 (0x569b4a93c240)
• instruction: EXP_DONE 0, killed renamable $vgpr0, renamable $vgpr1, renamable $vgpr2, renamable $vgpr3, -1, 0, 15, implicit $exec
• operand 2: renamable $vgpr1an undefined physical register ***

[arsenm]

Original MIR here passes verifier for me. Last time I looked at this, that was also the case and I re-reduced to new MIR. That test case also no longer reproduces. I do see a different verifier error in the IR test, at a different point

Nevermind. I see the same undefined physical register case, and I think I lost the re-reduced mir

[arsenm]

Further reduced IR:

; RUN: llc -mtriple=amdgcn-amd-amdpal -mcpu=gfx900 -verify-machineinstrs -o - %s

define amdgpu_vs void @test(i32 inreg %cmp, i32 %e0) {
entry:
  %cond = icmp eq i32 %cmp, 0
  br i1 %cond, label %end, label %load

load:
  %data1 = call <2 x i32> @llvm.amdgcn.struct.buffer.load.format.v2i32(<4 x i32> zeroinitializer, i32 0, i32 0, i32 0, i32 0)
  %e1 = extractelement <2 x i32> %data1, i32 0
  %e2 = extractelement <2 x i32> %data1, i32 1
  br label %end

end:
  %out1 = phi i32 [ 0, %entry ], [ %e1, %load ]
  %out2 = phi i32 [ poison, %entry ], [ %e2, %load ]
  call void @llvm.amdgcn.exp.i32(i32 0, i32 0, i32 %e0, i32 %out1, i32 %out2, i32 %e0, i1 false, i1 false)
  ret void
}

More reduced MIR:

# RUN: llc -mtriple=amdgcn-amd-amdpal -mcpu=gfx900 -start-after=register-coalescer -stop-after=tailduplication -verify-machineinstrs -o - %s

---
name:            test
tracksRegLiveness: true
machineFunctionInfo:
  isEntryFunction: true
  scratchRSrcReg:  '$sgpr96_sgpr97_sgpr98_sgpr99'
  stackPtrOffsetReg: '$sgpr32'
body:             |
  bb.0:
    liveins: $sgpr0, $vgpr0

    %0:vgpr_32 = COPY killed $vgpr0
    S_CMP_EQ_U32 killed $sgpr0, 0, implicit-def $scc
    S_CBRANCH_SCC0 %bb.2, implicit killed $scc

  bb.1:
    undef %1.sub0:vreg_64 = V_MOV_B32_e32 0, implicit $exec
    S_BRANCH %bb.3

  bb.2:
    %2:sgpr_128 = IMPLICIT_DEF
    %3:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
    %1:vreg_64 = BUFFER_LOAD_FORMAT_XY_IDXEN killed %3, killed %2, 0, 0, 0, 0, implicit $exec :: (dereferenceable load (s64), addrspace 8)

  bb.3:
    EXP 0, killed %0, killed %1.sub0, killed %1.sub1, killed %0, 0, 0, 0, implicit $exec
    S_ENDPGM 0

...

There are several options for what the bug is here. I would primarily blame tailduplication, which is making no effort to track physical register liveness. The coalescer didn't do anything wrong. The problematic part is the representation in %bb.1 of the partial def of %1. After register allocation / virtregrewriter, the representation of the live out undef phi def is lost.

The problems appear after VirtRegRewriter. undef %1.sub0:vreg_64 = V_MOV_B32_e32 0, implicit $exec is rewritten with no reference to the undef sub1. To maintain the physical register liveness, this would need an implicit-def of the whole register (or at least the undef piece). This however is really ugly, and I think we should avoid adding arbitrary implicit operands to instructions since code is rarely prepared to deal with them.

As another buglet, the livein entry bb.3 is $vgpr1_vgpr2:0x000000000000000F. This fully covers the register. Maybe VirtRegRewriter should not use the livein mask if there is a subregister phi def.

Failing that, TailDuplicator needs to track liveness and mark operands as undef. It currently doesn't bother and assumes everything will work out OK. It would need to add undef flags to the operands in the block where the used operands were never defined

[arsenm]

I have a plausible patch to fix this in VirtRegRewriter. We are missing a verifier check too