RegAlloc: Fix "SubRange for this mask not found" unreachable in SplitKit

[arsenm]

Summary

In this testcase, %2 has some full defs and some subregister defs and
initially has two subranges for the low lane, and the rest of the full
register. The subregister def is not live out of the block where it
is defined.

After %2 is split, refineSubRanges ends up splitting the subrange
masks into a different set of masks than in the original parent
interval. This would then fail to find it and hit the unreachable.

I'm suspicious of how simple this patch is, and not sure why this
special phi handling is needed given that refineSubRanges was already
called Suspiciously, only one SystemZ test fails if I remove this
entire loop for subrange handling.

[qcolombet]

I'm suspicious of how simple this patch is, and not sure why this special phi handling is needed given that refineSubRanges was already called

No sure. I am actually thinking that the new version is missing to update the ranges properly when the match is inexact (i.e., aren't we missing some updates?). Previously we had an expectation that the match was exact so the code was correct w.r.t. that simplification. Now, I am not so sure, but maybe like you said this job was actually already done in refineSubRanges.

@kparzysz what do you think?

[arsenm]

ping @kparzysz

[arsenm]

ping @kparzysz

[kparzysz]

Sorry, the emails that I'm getting from the @-mentions look exactly the same as any other email from phabricator to llvm-commits, and with hundreds of these per day I only look at a few...

The special handling of PHIs (with the exact mask) was added in D88020. It used to be finding a match that covered the given mask, but that commit made it look for an exact cover. It appears that it's essentially incompatible with the call to refineSubRanges.

Testcases for the more complex scenarios are accumulated as bug reproducers. There is no comprehensive coverage of all possible situations, so only one test failing with the removal of some piece of code is still pretty good (better than nothing).

[foad]

In D105065#2920370, @kparzysz wrote:

The special handling of PHIs (with the exact mask) was added in D88020. It used to be finding a match that covered the given mask, but that commit made it look for an exact cover. It appears that it's essentially incompatible with the call to refineSubRanges.

That's not quite true. Before D88020 getSubRangeForMask was always "exact". D88020 split it into getSubRangeForMaskExact and getSubRangeForMask (which is the inexact version). So it should have been NFC in extendPHIRange and extendPHIKillRanges.

[kparzysz]

Ah, you're right, I didn't look closely enough.

In any case, seems like the problem originates with the refineSubRanges actually doing something non-trivial, as it would generally create subranges without direct matches in the PHI values. Maybe it has never worked for such cases. Frankly, I'm not sure what to do here, since the thing that comes to mind is to update the PHI nodes, but it would require function-wide refinement of the PHIs.

[arsenm]

Superseded by D107829

llvm/lib/CodeGen/SplitKit.h

private:
   /// getLICalc - Return the LICalc to use for RegIdx.  In spill mode, the
   /// complement interval can overlap the other intervals, so it gets its own
   /// LICalc instance.  When not in spill mode, all intervals can share one.
   LiveIntervalCalc &getLICalc(unsigned RegIdx) {
     return LICalc[SpillMode != SM_Partition && RegIdx != 0];
   }
 
   /// Find a subrange corresponding to the exact lane mask @p LM in the live
-  /// interval @p LI. The interval @p LI is assumed to contain such a subrange.
-  /// This function is used to find corresponding subranges between the
-  /// original interval and the new intervals.
-  LiveInterval::SubRange &getSubRangeForMaskExact(LaneBitmask LM,
+  /// interval @p LI. If the interval @p LI does not contain contain such a
+  /// subrange, returns nullptr. This function is used to find corresponding
+  /// subranges between the original interval and the new intervals.
+  LiveInterval::SubRange *getSubRangeForMaskExact(LaneBitmask LM,
                                                   LiveInterval &LI);
 
   /// Find a subrange corresponding to the lane mask @p LM, or a superset of it,
   /// in the live interval @p LI. The interval @p LI is assumed to contain such
   /// a subrange.  This function is used to find corresponding subranges between
   /// the original interval and the new intervals.
   LiveInterval::SubRange &getSubRangeForMask(LaneBitmask LM, LiveInterval &LI);
 

llvm/lib/CodeGen/SplitKit.cpp

LLVM_DUMP_METHOD void SplitEditor::dump() const {
   }
 
   for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
     dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
   dbgs() << '\n';
 }
 #endif
 
-LiveInterval::SubRange &SplitEditor::getSubRangeForMaskExact(LaneBitmask LM,
+LiveInterval::SubRange *SplitEditor::getSubRangeForMaskExact(LaneBitmask LM,
                                                              LiveInterval &LI) {
-  for (LiveInterval::SubRange &S : LI.subranges())
+  for (LiveInterval::SubRange &S : LI.subranges()) {
     if (S.LaneMask == LM)
-      return S;
-  llvm_unreachable("SubRange for this mask not found");
+      return &S;
+  }
+
+  return nullptr;
 }
 
 LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
                                                         LiveInterval &LI) {
   for (LiveInterval::SubRange &S : LI.subranges())
     if ((S.LaneMask & LM) == LM)
       return S;
   llvm_unreachable("SubRange for this mask not found");
void SplitEditor::extendPHIRange(MachineBasicBlock &B, LiveIntervalCalc &LIC,
   for (MachineBasicBlock *P : B.predecessors()) {
     SlotIndex End = LIS.getMBBEndIdx(P);
     SlotIndex LastUse = End.getPrevSlot();
     // The predecessor may not have a live-out value. That is OK, like an
     // undef PHI operand.
     LiveInterval &PLI = Edit->getParent();
     // Need the cast because the inputs to ?: would otherwise be deemed
     // "incompatible": SubRange vs LiveInterval.
-    LiveRange &PSR = !LM.all() ? getSubRangeForMaskExact(LM, PLI)
+    LiveRange &PSR = !LM.all() ? *getSubRangeForMaskExact(LM, PLI)
                                : static_cast<LiveRange &>(PLI);
     if (PSR.liveAt(LastUse))
       LIC.extend(LR, End, /*PhysReg=*/0, Undefs);
   }
 }
 
 void SplitEditor::extendPHIKillRanges() {
   // Extend live ranges to be live-out for successor PHI values.
void SplitEditor::extendPHIKillRanges() {
   LiveIntervalCalc SubLIC;
 
   for (LiveInterval::SubRange &PS : ParentLI.subranges()) {
     for (const VNInfo *V : PS.valnos) {
       if (V->isUnused() || !V->isPHIDef())
         continue;
       unsigned RegIdx = RegAssign.lookup(V->def);
       LiveInterval &LI = LIS.getInterval(Edit->get(RegIdx));
-      LiveInterval::SubRange &S = getSubRangeForMaskExact(PS.LaneMask, LI);
-      if (removeDeadSegment(V->def, S))
+
+      LiveInterval::SubRange *S = getSubRangeForMaskExact(PS.LaneMask, LI);
+      if (!S || removeDeadSegment(V->def, *S))
         continue;
 
       MachineBasicBlock &B = *LIS.getMBBFromIndex(V->def);
       SubLIC.reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
                    &LIS.getVNInfoAllocator());
       Undefs.clear();
       LI.computeSubRangeUndefs(Undefs, PS.LaneMask, MRI, *LIS.getSlotIndexes());
-      extendPHIRange(B, SubLIC, S, PS.LaneMask, Undefs);
+      extendPHIRange(B, SubLIC, *S, PS.LaneMask, Undefs);
     }
   }
 }
 
 /// rewriteAssigned - Rewrite all uses of Edit->getReg().
 void SplitEditor::rewriteAssigned(bool ExtendRanges) {
   struct ExtPoint {
     ExtPoint(const MachineOperand &O, unsigned R, SlotIndex N)

llvm/test/CodeGen/AMDGPU/extend-phi-subrange-not-in-parent.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx90a -verify-regalloc -run-pass=greedy -o - %s | FileCheck %s
+
+# Initially %2 starts out with 2 subranges (one for sub0, and one for
+# the rest of the lanes). After %2 is split, after refineSubRanges the
+# newly created register has a different set of lane masks since the
+# copy bundle uses 2 different defs to cover the register.
+
+---
+name: subrange_for_this_mask_not_found
+tracksRegLiveness: true
+machineFunctionInfo:
+  scratchRSrcReg:  '$sgpr0_sgpr1_sgpr2_sgpr3'
+  stackPtrOffsetReg: '$sgpr32'
+  occupancy:       7
+body:             |
+  ; CHECK-LABEL: name: subrange_for_this_mask_not_found
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   [[DEF:%[0-9]+]]:vgpr_32 = IMPLICIT_DEF
+  ; CHECK:   [[DEF1:%[0-9]+]]:vreg_1024_align2 = IMPLICIT_DEF
+  ; CHECK:   SI_SPILL_V1024_SAVE [[DEF1]], %stack.0, $sgpr32, 0, implicit $exec :: (store 128 into %stack.0, align 4, addrspace 5)
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
+  ; CHECK:   S_NOP 0, implicit [[DEF1]]
+  ; CHECK:   S_NOP 0, implicit [[DEF1]]
+  ; CHECK:   [[DEF2:%[0-9]+]]:vreg_1024_align2 = IMPLICIT_DEF
+  ; CHECK:   S_CBRANCH_VCCNZ %bb.1, implicit undef $vcc
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x80000000)
+  ; CHECK:   [[SI_SPILL_V1024_RESTORE:%[0-9]+]]:vreg_1024_align2 = SI_SPILL_V1024_RESTORE %stack.0, $sgpr32, 0, implicit $exec :: (load 128 from %stack.0, align 4, addrspace 5)
+  ; CHECK:   undef %5.sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16:vreg_1024_align2 = COPY [[SI_SPILL_V1024_RESTORE]].sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16 {
+  ; CHECK:     internal %5.sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30_sub31:vreg_1024_align2 = COPY [[SI_SPILL_V1024_RESTORE]].sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30_sub31
+  ; CHECK:   }
+  ; CHECK:   %5.sub0:vreg_1024_align2 = IMPLICIT_DEF
+  ; CHECK:   S_NOP 0, implicit %5.sub0
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.4(0x80000000)
+  ; CHECK:   S_NOP 0, implicit %5
+  ; CHECK: bb.4:
+  ; CHECK:   successors: %bb.3(0x40000000), %bb.5(0x40000000)
+  ; CHECK:   [[DEF2:%[0-9]+]]:vreg_1024_align2 = IMPLICIT_DEF
+  ; CHECK:   S_CBRANCH_VCCNZ %bb.3, implicit undef $vcc
+  ; CHECK: bb.5:
+  ; CHECK:   undef %3.sub0:vreg_1024_align2 = COPY [[DEF]]
+  ; CHECK:   S_NOP 0, implicit %3
+  bb.0:
+    %0:vgpr_32 = IMPLICIT_DEF
+    %1:vreg_1024_align2 = IMPLICIT_DEF
+    %2:vreg_1024_align2 = COPY %1
+
+  bb.1:
+    S_NOP 0, implicit %1
+    S_NOP 0, implicit %1
+    %1:vreg_1024_align2 = IMPLICIT_DEF
+    S_CBRANCH_VCCNZ %bb.1, implicit undef $vcc
+
+  bb.3:
+    %2.sub0:vreg_1024_align2 = IMPLICIT_DEF
+    S_NOP 0, implicit %2.sub0
+
+  bb.4:
+    S_NOP 0, implicit %2
+
+  bb.5:
+    %2:vreg_1024_align2 = IMPLICIT_DEF
+    S_CBRANCH_VCCNZ %bb.4, implicit undef $vcc
+
+  bb.6:
+    undef %4.sub0:vreg_1024_align2 = COPY %0
+    S_NOP 0, implicit %4
+...