*** Bad machine code: Illegal virtual register for instruction *** after early-tailduplication

[mikaelholmen]

LLVM commit: c5dede8
Reproduce with:

llc -verify-machineinstrs -mtriple aarch64-none-linux-gnu -o - bbi-63545-aarch64.mir -run-pass early-tailduplication

Result:

# After Early Tail Duplication
# Machine code for function f: IsSSA, TracksLiveness

bb.0:
  successors: %bb.4(0x80000000); %bb.4(100.00%)

  $x0 = COPY undef $x0, implicit-def %0:gpr32common
  B %bb.4

bb.1:
  successors: %bb.4(0x80000000); %bb.4(100.00%)

  $x0 = COPY undef $x0, implicit-def %1:gpr32common
  B %bb.4

bb.3:

bb.4:
; predecessors: %bb.0, %bb.1
  successors: %bb.5(0x50000000), %bb.6(0x30000000); %bb.5(62.50%), %bb.6(37.50%)

  %3:gpr32sp = PHI %0:gpr32common, %bb.0, %1:gpr32common, %bb.1
  CBNZW %3:gpr32sp, %bb.6

bb.5:
; predecessors: %bb.4


bb.6:
; predecessors: %bb.4


# End machine code for function f.

*** Bad machine code: Illegal virtual register for instruction ***
- function:    f
- basic block: %bb.4  (0x9140f00)
- instruction: CBNZW %3:gpr32sp, %bb.6
- operand 0:   %3:gpr32sp
Expected a GPR32 register, but got a GPR32sp register
LLVM ERROR: Found 1 machine code errors.

So early tail-duplication has changed
CBNZW %1, %bb.6
where %1 is a gpr32 vreg into
CBNZW %3:gpr32sp, %bb.6
but CBNZW requires a vreg of the class gpr32.

bbi-63545-aarch64.mir.gz

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

[bjope]

Short summary of what I think happens here:

1. TailDuplicator::tailDuplicate is collecting a set of UsedByPhi registers.
2. Presence of a register in the UsedByPhi set results in addSSAUpdateEntry calls. Adding mappings between registers in SSAUpdateVals. Since a PHI node can have different register classes for inputs and outputs those mappings could map a register from one register class to a register of a different register class.
3. TailDuplicator::tailDuplicateAndUpdate will do this to inform the MachineSSAUpdater about available values. This is done without considering that the available value might have a register class that isn't fulfilling constraints by the machine operand uses that we want to update:

       // Add the new vregs as available values.
      DenseMap<Register, AvailableValsTy>::iterator LI =
          SSAUpdateVals.find(VReg);
      for (std::pair<MachineBasicBlock *, Register> &J : LI->second) {
        MachineBasicBlock *SrcBB = J.first;
        Register SrcReg = J.second;
        SSAUpdate.AddAvailableValue(SrcBB, SrcReg);
      }

4. SSAUpdate.RewriteUse will find and use an "available value", which might be a register with unexpected register class for the MO being updated.

Some different ideas about how to solve this:

1. Let RewriteUse insert a COPY instruction when needed, to make sure we satisfy any constraints for the using MI.
2. Populate SSAUpdate for each use being updated, but only add registers that have a satisfying class. We could do one scan here to find out if the register class of the register satisfies all uses, and skip adding it as available value to SSAUpdate if not all users constraints are met.
3. Maybe we should be more careful already when populating SSAUpdateVals. This to make sure that we only add registers with satisfying regclass. TailDuplicator::duplicateInstruction is doing checks PreRegAlloc regarding register class constraints (also involving subregister uses), but only for the !MO.isDef() case. For isDef() it is calling addSSAUpdateEntry without checking register classes, given that the register is in the UsedByPhi set.

Here is an updated reproducer with a few more scenarios (all three tests currently result in machine verifier errors):

# RUN: llc -verify-machineinstrs -mtriple aarch64-none-linux-gnu -o - %s -run-pass early-tailduplication

# These tests used to hit verification failure due to register class
# mismatches after tail dupilication (and the SSA form updates).

# In test1 we have a simple case when the COPY:s already are duplicated, but
# TailDuplication will try to eliminate the PHI in bb.2 by adding a new PHI in
# bb.4. The presence of a PHI node in bb.4, which happens to assign to a
# gpr32sp register, was enough to mess up the result. That PHI node was reused
# and the use of %2 in the CBNZW was changed into using %3 instead. But the
# register class of %3 is not correct for CBNZW.
---
name:            test1
tracksRegLiveness: true
body:             |
  bb.0:
    $x0 = COPY undef $x0, implicit-def %0:gpr32
    B %bb.2

  bb.1:
    $x0 = COPY undef $x0, implicit-def %1:gpr32

  bb.2:
    %2:gpr32 = PHI %1, %bb.1, %0, %bb.0
    B %bb.4

  bb.3:
    B %bb.3

  bb.4:
    %3:gpr32sp = PHI %2, %bb.2
    %5:gpr32 = SUBSWri %3, 1, 0, implicit-def dead $nzcv
    CBNZW %2, %bb.5

  bb.5:

...

# In test2 there are two PHI:s already present, one with the wanted register
# class.
# FIXME: Can we pick the best PHI directly instead of getting a COPY from the
#        one with wrong register class? Is that better?
---
name:            test2
tracksRegLiveness: true
body:             |
  bb.0:
    $x0 = COPY undef $x0, implicit-def %0:gpr32
    B %bb.2

  bb.1:
    $x0 = COPY undef $x0, implicit-def %1:gpr32

  bb.2:
    %2:gpr32 = PHI %1, %bb.1, %0, %bb.0
    B %bb.4

  bb.3:
    B %bb.3

  bb.4:
    %3:gpr32sp = PHI %2, %bb.2
    %4:gpr32 = PHI %2, %bb.2
    CBNZW %2, %bb.5

  bb.5:
    %5:gpr32 = SUBSWri %3, 1, 0, implicit-def dead $nzcv
...

# In test3 we have multiple uses, and in multiple BB:s. This test is to show
# that we get one COPY instruction inserted for each BB where there is a use.
---
name:            test3
tracksRegLiveness: true
body:             |
  bb.0:
    $x0 = COPY undef $x0, implicit-def %0:gpr32
    B %bb.2

  bb.1:
    $x0 = COPY undef $x0, implicit-def %1:gpr32

  bb.2:
    %2:gpr32 = PHI %1, %bb.1, %0, %bb.0
    B %bb.4

  bb.3:
    B %bb.3

  bb.4:
    %3:gpr32sp = PHI %2, %bb.2
    %5:gpr32 = SUBSWri %3, 1, 0, implicit-def dead $nzcv

  bb.5:
    CBNZW %2, %bb.6

  bb.6:
    CBNZW %2, %bb.7

  bb.7:
...

[bjope]

Here is an attempt to fix this (by adding extra COPY instructions): #95553

(Not quite sure how to do it using the other ideas I mentioned in the previous comment. I tried the idea of avoiding to populate SSAUpdate with "available values" when the registers had a non-satisfying register class. But could not really get that to work. If removing the SSAUpdate.AddAvailableValue call completely it does however pass. So not quite sure why it didn't help to filter our all regs with a non matching register class.