Unbundle KILL bundles in VirtRegRewriter

[rampitec]

Summary

SplitKit forms invalid COPY subreg bundles without a leading
BUNDLE instruction. That manifests itself in post-RA scheduler
counting instruction and asserting on "Instruction count mismatch".

The bundle shall be undone by VirtRegRewriter::expandCopyBundle(),
but it does not because VirtRegRewriter::handleIdentityCopy() can
turn COPY bundle into a KILL bundle.

Process KILLs as well.

[foad]

SplitKit forms invalid COPY subreg bundles without a leading BUNDLE instruction.

From reading through @MatzeB's D30438, it looks like this was done intentionally and they were all supposed to be unbundled again by VirtRegRewriter::expandCopyBundle, i.e. before the post RA scheduler runs.

[rampitec]

For the context, there is also D85456 which just fixes instruction counting in the scheduler, although consensus was a bundle without BOUNDLE instruction is illegal.

[foad]

consensus was a bundle without BOUNDLE instruction is illegal.

I don't disagree with that, but I wonder why it isn't working the way D30438 was designed. Is there some reason why expandCopyBundle is not unbundling all the BUNDLE-less bundles?

[rampitec]

In D85484#2203273, @foad wrote:

consensus was a bundle without BOUNDLE instruction is illegal.

I don't disagree with that, but I wonder why it isn't working the way D30438 was designed. Is there some reason why expandCopyBundle is not unbundling all the BUNDLE-less bundles?

I do not think that is a good idea to unbundle just everything. Ideally this code shall only expand what was created by the SplitKit and do not touch what was bundled by an user code for any other reason.
Then do you think forming of an invalid bundle is a good idea to distinguish?
I am now playing with the change which will unboundle COPY and KILL bundles, not just COPY.

[rampitec]

Handle KILLs when unbundling.

[rampitec]

There is probably a question do we need to insert BUNDLE header or just unpack KILLs as well? Having a bundle without a header is not legal, but having a header can mess with target code. I believe D30438 did not have a perfect solution.

[rampitec]

After all these changes I now believe these are two separate problems and two separate patches. Handling of KILLs is what solves the problem and what needs to be done anyway. A question of proper formation and marking of transient bundles is a separate issue.

Changed to only handle KILLs. I believe it should make the patch not controversial.

[foad]

Looks good to me, thanks.

llvm/lib/CodeGen/SplitKit.cpp

SlotIndex SplitEditor::buildCopy(unsigned FromReg, unsigned ToReg,
   }
 
   // Abort if we cannot possibly implement the COPY with the given indexes.
   if (BestIdx == 0)
     report_fatal_error("Impossible to implement partial COPY");
 
   SlotIndex Def = buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore,
                                         BestIdx, DestLI, Late, SlotIndex());
+  auto FirstMI = LIS.getInstructionFromIndex(Def)->getIterator();
 
   // Greedy heuristic: Keep iterating keeping the best covering subreg index
   // each time.
   LaneBitmask LanesLeft = LaneMask & ~(TRI.getSubRegIndexLaneMask(BestIdx));
   while (LanesLeft.any()) {
     unsigned BestIdx = 0;
     int BestCover = std::numeric_limits<int>::min();
     for (unsigned Idx : PossibleIndexes) {
while (LanesLeft.any()) {
     if (BestIdx == 0)
       report_fatal_error("Impossible to implement partial COPY");
 
     buildSingleSubRegCopy(FromReg, ToReg, MBB, InsertBefore, BestIdx,
                           DestLI, Late, Def);
     LanesLeft &= ~TRI.getSubRegIndexLaneMask(BestIdx);
   }
 
+  if (FirstMI->isBundledWithSucc()) {
+    finalizeBundle(MBB, FirstMI);
+    auto Bundle = std::prev(FirstMI);
+    assert(Bundle->isBundle());
+    LIS.ReplaceMachineInstrInMaps(*FirstMI, *Bundle);
+  }
+
   return Def;
 }
 
 VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
                                    VNInfo *ParentVNI,
                                    SlotIndex UseIdx,
                                    MachineBasicBlock &MBB,
                                    MachineBasicBlock::iterator I) {

llvm/lib/CodeGen/VirtRegMap.cpp

void VirtRegRewriter::handleIdentityCopy(MachineInstr &MI) const {
   LLVM_DEBUG(dbgs() << "  deleted.\n");
 }
 
 /// The liverange splitting logic sometimes produces bundles of copies when
 /// subregisters are involved. Expand these into a sequence of copy instructions
 /// after processing the last in the bundle. Does not update LiveIntervals
 /// which we shouldn't need for this instruction anymore.
 void VirtRegRewriter::expandCopyBundle(MachineInstr &MI) const {
-  if (!MI.isCopy())
+  if (!MI.isCopy() && !MI.isKill())
     return;
 
   if (MI.isBundledWithPred() && !MI.isBundledWithSucc()) {
     SmallVector<MachineInstr *, 2> MIs({&MI});
 
-    // Only do this when the complete bundle is made out of COPYs.
+    // Only do this when the complete bundle is made out of COPYs and KILLs.
     MachineBasicBlock &MBB = *MI.getParent();
     for (MachineBasicBlock::reverse_instr_iterator I =
          std::next(MI.getReverseIterator()), E = MBB.instr_rend();
          I != E && I->isBundledWithSucc(); ++I) {
-      if (!I->isCopy())
+      if (I->isBundle()) {
+        I->eraseFromBundle();
+        if (Indexes)
+          Indexes->removeSingleMachineInstrFromMaps(*I);
+        break;
+      }
+      if (!I->isCopy() && !I->isKill())
         return;
       MIs.push_back(&*I);
     }
     MachineInstr *FirstMI = MIs.back();
 
     auto anyRegsAlias = [](const MachineInstr *Dst,
                            ArrayRef<MachineInstr *> Srcs,
                            const TargetRegisterInfo *TRI) {

llvm/test/CodeGen/AMDGPU/splitkit-copy-bundle.mir

+# RUN: llc -march=amdgcn -mcpu=gfx900 -run-pass=greedy -o - -verify-machineinstrs %s | FileCheck -check-prefixes=MIR,RA %s
+# RUN: llc -march=amdgcn -mcpu=gfx900 -run-pass=greedy,virtregrewriter,post-RA-sched -o - -verify-machineinstrs %s | FileCheck -check-prefixes=MIR,VR %s
+# RUN: llc -march=amdgcn -mcpu=gfx900 -start-before=greedy -o - -verify-machineinstrs %s | FileCheck -check-prefix=ASM %s
+
+---
+# MIR-LABEL: name: splitkit_copy_bundle
+
+# RA:         BUNDLE implicit-def %4, implicit %5 {
+# RA-NEXT:      undef %4.sub0_sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15:sgpr_1024 = COPY %5.sub0_sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15
+# RA-NEXT:      internal %4.sub12_sub13_sub14_sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27:sgpr_1024 = COPY %5.sub12_sub13_sub14_sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27
+# RA-NEXT:      internal %4.sub28_sub29:sgpr_1024 = COPY %5.sub28_sub29
+# RA-NEXT:    }
+
+# RA:         BUNDLE implicit-def %6, implicit %4 {
+# RA-NEXT:      undef %6.sub0_sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15:sgpr_1024 = COPY %4.sub0_sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15
+# RA-NEXT:      internal %6.sub12_sub13_sub14_sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27:sgpr_1024 = COPY %4.sub12_sub13_sub14_sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27
+# RA-NEXT:      internal %6.sub28_sub29:sgpr_1024 = COPY %4.sub28_sub29
+# RA-NEXT:    }
+
+# RA:         BUNDLE implicit-def %4, implicit %6 {
+# RA-NEXT:      undef %4.sub0_sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15:sgpr_1024 = COPY %6.sub0_sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15
+# RA-NEXT:      internal %4.sub12_sub13_sub14_sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27:sgpr_1024 = COPY %6.sub12_sub13_sub14_sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27
+# RA-NEXT:      internal %4.sub28_sub29:sgpr_1024 = COPY %6.sub28_sub29
+# RA-NEXT:    }
+
+
+
+# VR-NOT:     BUNDLE
+# VR:         renamable $sgpr80_sgpr81_sgpr82_sgpr83_sgpr84_sgpr85_sgpr86_sgpr87_sgpr88_sgpr89_sgpr90_sgpr91_sgpr92_sgpr93_sgpr94_sgpr95 = KILL undef renamable $sgpr80_sgpr81_sgpr82_sgpr83_sgpr84_sgpr85_sgpr86_sgpr87_sgpr88_sgpr89_sgpr90_sgpr91_sgpr92_sgpr93_sgpr94_sgpr95
+# VR-NEXT:    renamable $sgpr96_sgpr97 = KILL undef renamable $sgpr96_sgpr97
+
+# VR-NOT: BUNDLE
+
+# ASM-LABEL: {{^}}splitkit_copy_bundle:
+# ASM:      ; implicit-def: $sgpr34_sgpr35
+# ASM-NEXT: ; implicit-def: $sgpr98_sgpr99
+# ASM-NEXT: ; kill: def $sgpr80_sgpr81_sgpr82_sgpr83_sgpr84_sgpr85_sgpr86_sgpr87_sgpr88_sgpr89_sgpr90_sgpr91_sgpr92_sgpr93_sgpr94_sgpr95 killed $sgpr80_sgpr81_sgpr82_sgpr83_sgpr84_sgpr85_sgpr86_sgpr87_sgpr88_sgpr89_sgpr90_sgpr91_sgpr92_sgpr93_sgpr94_sgpr95
+# ASM-NEXT: ; kill: def $sgpr96_sgpr97 killed $sgpr96_sgpr97
+
+name:            splitkit_copy_bundle
+tracksRegLiveness: true
+machineFunctionInfo:
+  scratchRSrcReg:  '$sgpr0_sgpr1_sgpr2_sgpr3'
+  stackPtrOffsetReg: '$sgpr32'
+body:             |
+  bb.0:
+    %0:sreg_64 = IMPLICIT_DEF
+    %1:sreg_64 = IMPLICIT_DEF
+    undef %2.sub1:sgpr_1024 = S_MOV_B32 -1
+    %2.sub0:sgpr_1024 = S_MOV_B32 -1
+    undef %3.sub0:sgpr_1024 = S_MOV_B32 0
+
+  bb.1:
+    %2.sub2:sgpr_1024 = COPY %2.sub0
+    %2.sub3:sgpr_1024 = COPY %2.sub1
+    %2.sub4:sgpr_1024 = COPY %2.sub0
+    %2.sub5:sgpr_1024 = COPY %2.sub1
+    %2.sub6:sgpr_1024 = COPY %2.sub0
+    %2.sub7:sgpr_1024 = COPY %2.sub1
+    %2.sub8:sgpr_1024 = COPY %2.sub0
+    %2.sub9:sgpr_1024 = COPY %2.sub1
+    %2.sub10:sgpr_1024 = COPY %2.sub0
+    %2.sub11:sgpr_1024 = COPY %2.sub1
+    %2.sub12:sgpr_1024 = COPY %2.sub0
+    %2.sub13:sgpr_1024 = COPY %2.sub1
+    %2.sub14:sgpr_1024 = COPY %2.sub0
+    %2.sub15:sgpr_1024 = COPY %2.sub1
+    %2.sub16:sgpr_1024 = COPY %2.sub0
+    %2.sub17:sgpr_1024 = COPY %2.sub1
+    %2.sub18:sgpr_1024 = COPY %2.sub0
+    %2.sub19:sgpr_1024 = COPY %2.sub1
+    %2.sub20:sgpr_1024 = COPY %2.sub0
+    %2.sub21:sgpr_1024 = COPY %2.sub1
+    %2.sub22:sgpr_1024 = COPY %2.sub0
+    %2.sub23:sgpr_1024 = COPY %2.sub1
+    %2.sub24:sgpr_1024 = COPY %2.sub0
+    %2.sub25:sgpr_1024 = COPY %2.sub1
+    %2.sub26:sgpr_1024 = COPY %2.sub0
+    %2.sub27:sgpr_1024 = COPY %2.sub1
+    %2.sub28:sgpr_1024 = COPY %2.sub0
+    %2.sub29:sgpr_1024 = COPY %2.sub1
+    %3.sub1:sgpr_1024 = COPY %3.sub0
+    %3.sub2:sgpr_1024 = COPY %3.sub0
+    %3.sub3:sgpr_1024 = COPY %3.sub0
+    %3.sub4:sgpr_1024 = COPY %3.sub0
+    %3.sub5:sgpr_1024 = COPY %3.sub0
+    %3.sub6:sgpr_1024 = COPY %3.sub0
+    %3.sub7:sgpr_1024 = COPY %3.sub0
+    %3.sub8:sgpr_1024 = COPY %3.sub0
+    %3.sub9:sgpr_1024 = COPY %3.sub0
+    %3.sub10:sgpr_1024 = COPY %3.sub0
+    %3.sub11:sgpr_1024 = COPY %3.sub0
+    %3.sub12:sgpr_1024 = COPY %3.sub0
+    %3.sub13:sgpr_1024 = COPY %3.sub0
+    %3.sub14:sgpr_1024 = COPY %3.sub0
+    %3.sub15:sgpr_1024 = COPY %3.sub0
+    %3.sub16:sgpr_1024 = COPY %3.sub0
+    %3.sub17:sgpr_1024 = COPY %3.sub0
+    %3.sub18:sgpr_1024 = COPY %3.sub0
+    %3.sub19:sgpr_1024 = COPY %3.sub0
+    %3.sub20:sgpr_1024 = COPY %3.sub0
+    %3.sub21:sgpr_1024 = COPY %3.sub0
+    %3.sub22:sgpr_1024 = COPY %3.sub0
+    %3.sub23:sgpr_1024 = COPY %3.sub0
+    %3.sub24:sgpr_1024 = COPY %3.sub0
+    %3.sub25:sgpr_1024 = COPY %3.sub0
+    %3.sub26:sgpr_1024 = COPY %3.sub0
+    %3.sub27:sgpr_1024 = COPY %3.sub0
+    %3.sub28:sgpr_1024 = COPY %3.sub0
+    %3.sub29:sgpr_1024 = COPY %3.sub0
+    %3.sub30:sgpr_1024 = COPY %3.sub0
+    %3.sub31:sgpr_1024 = COPY %3.sub0
+
+  bb.2:
+    S_NOP 0, implicit %0, implicit %1, csr_amdgpu_highregs
+    S_CBRANCH_VCCNZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.2
+
+...