[RegAlloc] Immediately delete dead instructions with live uses

[rampitec]

Summary

When RA eliminated a dead def it can either immediately delete
the instruction itself or replace it with KILL to defer the
actual removal. If this instruction has a virtual register use
killing the register it will shrink the LI of the use. However,
if the LI covers the instruction and extends beyond it the
shrink will not happen. In fact that is impossible to shrink
such use because of the KILL still using it.

If later the LI of the use will be split at the KILL and the
KILL itself is eliminated after that point the new live segment
ends up at an invalid slot index.

This extremely rare condition was hit after D106408 which has
enabled rematerialization of such instructions. The replacement
with KILL is only done for rematerialized defs which became dead
and such rematerialization did not generally happen before.

The patch deletes an instruction immediately if it is a result
of rematerialization and has such use. An alternative would be
to prohibit a split at a KILL instruction, but it looks like it
is better to split a live range rather then keeping a killed
instruction just in case it can be rematerialized further.

Fixes PR51655.

[qcolombet]

llvm/lib/CodeGen/LiveRangeEdit.cpp

369–373

Typo: immedialtely => immediately

llvm/test/CodeGen/X86/pr51655.mir

4 ↗

(On Diff #369562)

Could you set a more descriptive file name like delete-dead-instrs-with-live-uses.mir?

[rampitec]

Fixed comment typo and renamed the test.

llvm/lib/CodeGen/LiveRangeEdit.cpp

if (VRM && MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&
     // The original live-range may have been shrunk to
     // an empty live-range. It happens when it is dead, but
     // we still keep it around to be able to rematerialize
     // other values that depend on it.
     if (OrigVNI)
       isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx);
   }
 
+  bool HasLiveVRegUses = false;
+
   // Check for live intervals that may shrink
   for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
          MOE = MI->operands_end(); MOI != MOE; ++MOI) {
     if (!MOI->isReg())
       continue;
     Register Reg = MOI->getReg();
     if (!Register::isVirtualRegister(Reg)) {
       // Check if MI reads any unreserved physregs.
       if (Reg && MOI->readsReg() && !MRI.isReserved(Reg))
         ReadsPhysRegs = true;
       else if (MOI->isDef())
         LIS.removePhysRegDefAt(Reg.asMCReg(), Idx);
       continue;
     }
     LiveInterval &LI = LIS.getInterval(Reg);
 
     // Shrink read registers, unless it is likely to be expensive and
     // unlikely to change anything. We typically don't want to shrink the
     // PIC base register that has lots of uses everywhere.
     // Always shrink COPY uses that probably come from live range splitting.
     if ((MI->readsVirtualRegister(Reg) && (MI->isCopy() || MOI->isDef())) ||
         (MOI->readsReg() && (MRI.hasOneNonDBGUse(Reg) || useIsKill(LI, *MOI))))
       ToShrink.insert(&LI);
+    else if (MOI->readsReg())
+      HasLiveVRegUses = true;
 
     // Remove defined value.
     if (MOI->isDef()) {
       if (TheDelegate && LI.getVNInfoAt(Idx) != nullptr)
         TheDelegate->LRE_WillShrinkVirtReg(LI.reg());
       LIS.removeVRegDefAt(LI, Idx);
       if (LI.empty())
         RegsToErase.push_back(Reg);
if (ReadsPhysRegs) {
     }
     LLVM_DEBUG(dbgs() << "Converted physregs to:\t" << *MI);
   } else {
     // If the dest of MI is an original reg and MI is reMaterializable,
     // don't delete the inst. Replace the dest with a new reg, and keep
     // the inst for remat of other siblings. The inst is saved in
     // LiveRangeEdit::DeadRemats and will be deleted after all the
     // allocations of the func are done.
-    if (isOrigDef && DeadRemats && TII.isTriviallyReMaterializable(*MI, AA)) {
+    // However, immediately delete instructions which have unshrunk virtual
+    // register uses. That may provoke RA to split an interval at the KILL
+    // and later result in an invalid live segment end.
+    if (isOrigDef && DeadRemats && !HasLiveVRegUses &&
+        TII.isTriviallyReMaterializable(*MI, AA)) {
       LiveInterval &NewLI = createEmptyIntervalFrom(Dest, false);
       VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator());
       NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
       pop_back();
       DeadRemats->insert(MI);
       const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
       MI->substituteRegister(Dest, NewLI.reg(), 0, TRI);
       MI->getOperand(0).setIsDead(true);

llvm/test/CodeGen/X86/delete-dead-instrs-with-live-uses.mir

+# RUN: llc -mtriple=i386-apple-ios9.0.0-simulator --frame-pointer=all -verify-machineinstrs -start-before=greedy -o - %s | FileCheck %s
+
+# The test used to fail with "Live segment doesn't end at a valid instruction"
+# See PR51655.
+
+---
+# CHECK: jne
+# CHECK: andl    $-16, %edx
+# CHECK: xorl    %ebx, %ebx
+# CHECK: movl    %edx, -16(%ebp)
+# CHECK: xorl    %esi, %esi
+
+name:            test
+tracksRegLiveness: true
+fixedStack:
+  - { id: 0, type: default, offset: 4, size: 4, alignment: 4, stack-id: default,
+      isImmutable: true, isAliased: false, callee-saved-restored: true }
+  - { id: 1, type: default, offset: 0, size: 4, alignment: 16, stack-id: default,
+      isImmutable: true, isAliased: false, callee-saved-restored: true }
+body:             |
+  bb.0:
+    successors: %bb.3(0x40000000), %bb.1(0x40000000)
+
+    %0:gr32_nosp = MOV32rm %fixed-stack.1, 1, $noreg, 0, $noreg :: (load (s32) from %fixed-stack.1)
+    %1:gr32_nosp = MOV32rm %fixed-stack.0, 1, $noreg, 0, $noreg :: (load (s32) from %fixed-stack.0, align 16)
+    %2:gr32_abcd = MOV32r0 implicit-def dead $eflags
+    JCC_1 %bb.3, 5, implicit undef $eflags
+    JMP_1 %bb.1
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+
+    %2:gr32_abcd = AND32ri8 %2, -16, implicit-def dead $eflags
+    %3:gr32_abcd = MOV32r0 implicit-def dead $eflags
+    %4:gr32 = LEA32r %0, 1, %1, -49, $noreg
+    %5:gr32_abcd = MOV32r0 implicit-def dead $eflags
+    %6:gr32 = IMPLICIT_DEF
+    JMP_1 %bb.2
+
+  bb.2:
+    successors: %bb.2(0x40000000), %bb.3(0x40000000)
+
+    %7:vr128 = MOVUPSrm %4, 1, %3, 0, $noreg :: (load (s128), align 1)
+    %5:gr32_abcd = nuw ADD32ri8 %5, 64, implicit-def dead $eflags
+    %6:gr32 = ADD32ri8 %6, -4, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit killed $eflags
+    JMP_1 %bb.3
+
+  bb.3:
+    successors: %bb.4(0x80000000)
+
+    %2:gr32_abcd = NEG32r %2, implicit-def dead $eflags
+    %8:gr32 = LEA32r %0, 1, %1, -5, $noreg
+    JMP_1 %bb.4
+
+  bb.4:
+    RET 0
+
+...