RegisterCoalescer: Fix verifier error when merging copy of undef

[arsenm]

Summary

There's no real read of the register, so the copy introduced a new
live value. Make sure we introduce a replacement implicit_def instead
of just erasing the copy.

Found from llvm-reduce since it tries to set undef on everything.

[arsenm]

Fix missing test update (which I guess is a minor regression)

[arsenm]

ping

[MatzeB]

I am not sure I understand this change... Wasn't the intention of the existing that code that when you have something like:

%2 = COPY undef %1
  USE %2

that you merge the regs to remove the copy and add an undef to the use operands? =>

USE undef %1

Why are we starting to use IMPLICIT_DEFs here? Is this related to subregs?

[arsenm]

In D127516#3613027, @MatzeB wrote:

I am not sure I understand this change... Wasn't the intention of the existing that code that when you have something like:

%2 = COPY undef %1
  USE %2

that you merge the regs to remove the copy and add an undef to the use operands? =>

USE undef %1

Yes, but in this situation the output register was a phi def so we need to keep a phi def in the same block in the coalesced register

Why are we starting to use IMPLICIT_DEFs here? Is this related to subregs?

Because it's a live out value, so you need a phi def in the block. It's not related to subregs. This is analagous to the case where ProcessImplicitDefs won't delete IMPLICIT_DEFs that feed phi uses.

[MatzeB]

For background: My understanding of IMPLICIT_DEF is that it was a bit of a workaround/hack necessary because for a given VReg on a control flow join you can have different "undef"/"not undef" merge. Unfortunately being out of SSA form we can't just attach an undef flag to the respective PHI operand as there is no PHI anymore. I always felt a bit uneasy with IMPLICIT_DEF getting used in other situations where they are not at the end of a block just for joining with a different definition/live value in the next block...

Though I have a feeling restricting IMPLICIT_DEFs just to this particular use case may be a loosing battle now since I think I've seen them pop-up in other situations... Also I don't remember fully, but I think we also trouble with undef flags being unable to express partially defined registers when subreg liveness is enabled.

[MatzeB]

llvm/test/CodeGen/AMDGPU/undef-subreg-use-after-coalesce.mir

35–37

This isn't a case of a live-out value though? Shouldn't it continue to use an undef flag over an IMPLICIT_DEF?

[MatzeB]

llvm/lib/CodeGen/RegisterCoalescer.cpp

1648

• This DstLI.liveAt(Idx) can only really be true if we assign to a subregister, can't it? (Otherwise the fact that we are about to (re-)assign the register means that it wouldn't be alive immediately before the copy (except for degenerate cases where the source and destination register of the COPY is the same)...

• Can SrcLI.liveAt(Idx) ever be true? Don't we filter for that above in lines 1624-1636?

[arsenm]

llvm/lib/CodeGen/RegisterCoalescer.cpp

1648

In this case there are subranges in the destination register, but not the source.

You're right, this works with the SrcLI.liveAt check removed

llvm/test/CodeGen/AMDGPU/undef-subreg-use-after-coalesce.mir

35–37

This is the minor regression I mentioned

[arsenm]

Remove unnecessary check

[arsenm]

llvm/test/CodeGen/AMDGPU/undef-subreg-use-after-coalesce.mir

35–37

On second inspection, I think this is arguably better. %0.sub1 is dead in the original MIR. Previously, the use on the S_ENDPGM was made undead by the coalescing. The implicit_def keeps %0.sub1 dead and defs a separate register for the undef use

[arsenm]

ping

[arsenm]

ping

[arsenm]

ping

[arsenm]

ping

[MatzeB]

I still feel like I don't fully understand why the change in undef-subreg-use-after-coalesce.mir makes things better, but either way the code changes seem reasonable and in the interest of not blocking this any further, go ahead! LGTM

[qcolombet]

I think it makes sense to insert an implicit_def here.

[arsenm]

d00b0aab31405432fad7bbaebccc0ae0956d6d39

llvm/lib/CodeGen/RegisterCoalescer.cpp

if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
     return nullptr;
 
   // If the undef copy defines a live-out value (i.e. an input to a PHI def),
   // then replace it with an IMPLICIT_DEF.
   LiveInterval &DstLI = LIS->getInterval(DstReg);
   SlotIndex RegIndex = Idx.getRegSlot();
   LiveRange::Segment *Seg = DstLI.getSegmentContaining(RegIndex);
   assert(Seg != nullptr && "No segment for defining instruction");
-  if (VNInfo *V = DstLI.getVNInfoAt(Seg->end)) {
-    if (V->isPHIDef()) {
-      CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
-      for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) {
-        MachineOperand &MO = CopyMI->getOperand(i-1);
-        if (MO.isReg() && MO.isUse())
-          CopyMI->removeOperand(i-1);
-      }
-      LLVM_DEBUG(dbgs() << "\tReplaced copy of <undef> value with an "
-                           "implicit def\n");
-      return CopyMI;
-    }
-  }
+  VNInfo *V = DstLI.getVNInfoAt(Seg->end);
+
+  // The source interval may also have been on an undef use, in which case the
+  // copy introduced a live value.
+  if ((V && V->isPHIDef()) || (!V && !DstLI.liveAt(Idx) && !SrcLI.liveAt(Idx))) {
 
   // Remove any DstReg segments starting at the instruction.
   LLVM_DEBUG(dbgs() << "\tEliminating copy of <undef> value\n");
 
   // Remove value or merge with previous one in case of a subregister def.
   if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
     VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
     DstLI.MergeValueNumberInto(VNI, PrevVNI);

llvm/test/CodeGen/AMDGPU/coalesce-liveout-undef-copy.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx900 -verify-coalescing -run-pass=simple-register-coalescing -o - %s | FileCheck %s
+
+# %2 has an undef read in %bb.3, and this IR wouldn't be valid if it
+# was a real read. After merging %2 into %0, we need to replace the
+# copy of undef with an implicit_def since the copy introduced a new
+# value.
+
+---
+name: coalesce_into_undef_copy
+tracksRegLiveness: true
+machineFunctionInfo:
+  scratchRSrcReg:  '$sgpr0_sgpr1_sgpr2_sgpr3'
+  stackPtrOffsetReg: '$sgpr32'
+body:             |
+  ; CHECK-LABEL: name: coalesce_into_undef_copy
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:vreg_128_align2 = COPY undef %1:sgpr_128, implicit $exec
+  ; CHECK-NEXT:   S_BRANCH %bb.1
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   dead %2:vreg_128_align2 = IMPLICIT_DEF
+  ; CHECK-NEXT:   [[COPY]].sub0:vreg_128_align2 = IMPLICIT_DEF
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   dead %4:vgpr_32 = V_INDIRECT_REG_READ_GPR_IDX_B32_V4 [[COPY]], undef %5:sgpr_32, 11, implicit-def $m0, implicit $m0, implicit $exec
+  ; CHECK-NEXT:   S_BRANCH %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[DEF:%[0-9]+]]:vreg_128_align2 = IMPLICIT_DEF
+  ; CHECK-NEXT:   S_CBRANCH_EXECNZ %bb.1, implicit $exec
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  bb.0:
+    %0:vreg_128_align2 = COPY undef %1:sgpr_128, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    %2:vreg_128_align2 = IMPLICIT_DEF
+    %3:vreg_128_align2 = COPY killed %0
+    %3.sub0:vreg_128_align2 = IMPLICIT_DEF
+
+  bb.2:
+    dead %5:vgpr_32 = V_INDIRECT_REG_READ_GPR_IDX_B32_V4 %3, undef %6:sgpr_32, 11, implicit-def $m0, implicit $m0, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.3:
+    %0:vreg_128_align2 = COPY undef %2
+    S_CBRANCH_EXECNZ %bb.1, implicit $exec
+
+  bb.4:
+
+...

llvm/test/CodeGen/AMDGPU/undef-subreg-use-after-coalesce.mir

 ---
 name: undef_subreg_use_after_full_copy_coalesce_composed
 tracksRegLiveness: true
 body:             |
   bb.0:
     ; CHECK-LABEL: name: undef_subreg_use_after_full_copy_coalesce_composed
     ; CHECK: undef %0.sub0:vreg_128 = V_MOV_B32_e32 0, implicit $exec
     ; CHECK-NEXT: dead %0.sub1:vreg_128 = V_MOV_B32_e32 0, implicit $exec
-    ; CHECK-NEXT: S_ENDPGM 0, implicit undef %2.sub1:vreg_64
+    ; CHECK-NEXT: [[DEF:%[0-9]+]]:vreg_64 = IMPLICIT_DEF
+    ; CHECK-NEXT: S_ENDPGM 0, implicit [[DEF]].sub1
     undef %0.sub0:vreg_128 = V_MOV_B32_e32 0, implicit $exec
     %0.sub1:vreg_128 = V_MOV_B32_e32 0, implicit $exec
     %1:vreg_128 = COPY killed %0
     %2:vreg_64 = COPY killed %1.sub2_sub3
     S_ENDPGM 0, implicit %2.sub1
 
 ...
 
 # FIXME: Initial computed range is wrong for %0.sub2_sub3 and fails