[LiveRange] Reset the VNIs when splitting subranges

[qcolombet]

Summary

When splitting a subrange we end up with two different subranges covering
two different, non overlapping, lanes.
As part of this splitting the VNIs of the original live-range need
to be dispatched to the subranges according to which lanes they are
actually defining.

Prior to this patch we were assuming that all values were defining
all lanes. This was wrong as demonstrated by llvm.org/PR40835.

[qcolombet]

Fix seg fault with PHIs

[arsenm]

LGTM

include/llvm/CodeGen/LiveInterval.h

public:
     /// until \p LaneMask can be matched exactly. \p Mod is executed on the
     /// matching subranges.
     ///
     /// Example:
     ///    Given an interval with subranges with lanemasks L0F00, L00F0 and
     ///    L000F, refining for mask L0018. Will split the L00F0 lane into
     ///    L00E0 and L0010 and the L000F lane into L0007 and L0008. The Mod
     ///    function will be applied to the L0010 and L0008 subranges.
+    ///
+    /// \p Indexes and \p TRI are required to clean up the VNIs that
+    /// don't defne the related lane masks after they get shrunk. E.g.,
+    /// when L000F gets split into L0007 and L0008 maybe only a subset
+    /// of the VNIs that defined L000F defines L0007.
     void refineSubRanges(BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
-                         std::function<void(LiveInterval::SubRange&)> Apply);
+                         std::function<void(LiveInterval::SubRange &)> Apply,
+                         const SlotIndexes &Indexes,
+                         const TargetRegisterInfo &TRI);
 
     bool operator<(const LiveInterval& other) const {
       const SlotIndex &thisIndex = beginIndex();
       const SlotIndex &otherIndex = other.beginIndex();
       return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg);
     }
 
     void print(raw_ostream &OS) const;

lib/CodeGen/LiveInterval.cpp

 void LiveInterval::clearSubRanges() {
   for (SubRange *I = SubRanges, *Next; I != nullptr; I = Next) {
     Next = I->Next;
     freeSubRange(I);
   }
   SubRanges = nullptr;
 }
 
-void LiveInterval::refineSubRanges(BumpPtrAllocator &Allocator,
-    LaneBitmask LaneMask, std::function<void(LiveInterval::SubRange&)> Apply) {
+/// For each VNI in \p SR, check whether or not that value defines part
+/// of the mask describe by \p LaneMask and if not, remove that value
+/// from \p SR.
+static void stripValuesNotDefiningMask(unsigned Reg, LiveInterval::SubRange &SR,
+                                       LaneBitmask LaneMask,
+                                       const SlotIndexes &Indexes,
+                                       const TargetRegisterInfo &TRI) {
+  // Phys reg should not be tracked at subreg level.
+  // Same for noreg (Reg == 0).
+  if (!TargetRegisterInfo::isVirtualRegister(Reg) || !Reg)
+    return;
+  // Remove the values that don't define those lanes.
+  SmallVector<VNInfo *, 8> ToBeRemoved;
+  for (VNInfo *VNI : SR.valnos) {
+    if (VNI->isUnused())
+      continue;
+    const MachineInstr *MI = Indexes.getInstructionFromIndex(VNI->def);
+    bool hasDef = false;
+    for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); ++MOI) {
+      if (!MOI->isReg() || !MOI->isDef())
+        continue;
+      if (MOI->getReg() != Reg)
+        continue;
+      if ((TRI.getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
+        continue;
+      hasDef = true;
+      break;
+    }
+
+    if (!hasDef)
+      ToBeRemoved.push_back(VNI);
+  }
+  for (VNInfo *VNI : ToBeRemoved)
+    SR.removeValNo(VNI);
+
+  assert(!SR.empty() && "At least one value should be defined by this mask");
+}
+
+void LiveInterval::refineSubRanges(
+    BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
+    std::function<void(LiveInterval::SubRange &)> Apply,
+    const SlotIndexes &Indexes, const TargetRegisterInfo &TRI) {
   LaneBitmask ToApply = LaneMask;
   for (SubRange &SR : subranges()) {
     LaneBitmask SRMask = SR.LaneMask;
     LaneBitmask Matching = SRMask & LaneMask;
     if (Matching.none())
       continue;
 
     SubRange *MatchingRange;
     if (SRMask == Matching) {
       // The subrange fits (it does not cover bits outside \p LaneMask).
       MatchingRange = &SR;
     } else {
       // We have to split the subrange into a matching and non-matching part.
       // Reduce lanemask of existing lane to non-matching part.
       SR.LaneMask = SRMask & ~Matching;
       // Create a new subrange for the matching part
       MatchingRange = createSubRangeFrom(Allocator, Matching, SR);
+      // Now that the subrange is split in half, make sure we
+      // only keep in the subranges the VNIs that touch the related half.
+      stripValuesNotDefiningMask(reg, *MatchingRange, Matching, Indexes, TRI);
+      stripValuesNotDefiningMask(reg, SR, SR.LaneMask, Indexes, TRI);
     }
     Apply(*MatchingRange);
     ToApply &= ~Matching;
   }
   // Create a new subrange if there are uncovered bits left.
   if (ToApply.any()) {
     SubRange *NewRange = createSubRange(Allocator, ToApply);
     Apply(*NewRange);

lib/CodeGen/LiveRangeCalc.cpp

if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
       // If this is the first time we see a subregister def, initialize
       // subranges by creating a copy of the main range.
       if (!LI.hasSubRanges() && !LI.empty()) {
         LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
         LI.createSubRangeFrom(*Alloc, ClassMask, LI);
       }
 
       LI.refineSubRanges(*Alloc, SubMask,
                          [&MO, this](LiveInterval::SubRange &SR) {
                            if (MO.isDef())
                              createDeadDef(*Indexes, *Alloc, SR, MO);
-      });
+                         },
+                         *Indexes, TRI);
     }
 
     // Create the def in the main liverange. We do not have to do this if
     // subranges are tracked as we recreate the main range later in this case.
     if (MO.isDef() && !LI.hasSubRanges())
       createDeadDef(*Indexes, *Alloc, LI, MO);
   }
 

lib/CodeGen/RegisterCoalescer.cpp

if (!IntA.hasSubRanges()) {
       LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg);
       IntA.createSubRangeFrom(Allocator, Mask, IntA);
     } else if (!IntB.hasSubRanges()) {
       LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntB.reg);
       IntB.createSubRangeFrom(Allocator, Mask, IntB);
     }
     SlotIndex AIdx = CopyIdx.getRegSlot(true);
     LaneBitmask MaskA;
+    const SlotIndexes &Indexes = *LIS->getSlotIndexes();
     for (LiveInterval::SubRange &SA : IntA.subranges()) {
       VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
       assert(ASubValNo != nullptr);
       MaskA |= SA.LaneMask;
 
-      IntB.refineSubRanges(Allocator, SA.LaneMask,
-          [&Allocator,&SA,CopyIdx,ASubValNo,&ShrinkB]
-            (LiveInterval::SubRange &SR) {
-        VNInfo *BSubValNo = SR.empty()
-          ? SR.getNextValue(CopyIdx, Allocator)
+      IntB.refineSubRanges(
+          Allocator, SA.LaneMask,
+          [&Allocator, &SA, CopyIdx, ASubValNo,
+           &ShrinkB](LiveInterval::SubRange &SR) {
+            VNInfo *BSubValNo = SR.empty() ? SR.getNextValue(CopyIdx, Allocator)
                                            : SR.getVNInfoAt(CopyIdx);
             assert(BSubValNo != nullptr);
             auto P = addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);
             ShrinkB |= P.second;
             if (P.first)
               BSubValNo->def = ASubValNo->def;
-      });
+          },
+          Indexes, *TRI);
     }
     // Go over all subranges of IntB that have not been covered by IntA,
     // and delete the segments starting at CopyIdx. This can happen if
     // IntA has undef lanes that are defined in IntB.
     for (LiveInterval::SubRange &SB : IntB.subranges()) {
       if ((SB.LaneMask & MaskA).any())
         continue;
       if (LiveRange::Segment *S = SB.getSegmentContaining(CopyIdx))
void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
   LIS->extendToIndices(LRange, EndPoints);
 }
 
 void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
                                           const LiveRange &ToMerge,
                                           LaneBitmask LaneMask,
                                           CoalescerPair &CP) {
   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
-  LI.refineSubRanges(Allocator, LaneMask,
-      [this,&Allocator,&ToMerge,&CP](LiveInterval::SubRange &SR) {
+  LI.refineSubRanges(
+      Allocator, LaneMask,
+      [this, &Allocator, &ToMerge, &CP](LiveInterval::SubRange &SR) {
         if (SR.empty()) {
           SR.assign(ToMerge, Allocator);
         } else {
           // joinSubRegRange() destroys the merged range, so we need a copy.
           LiveRange RangeCopy(ToMerge, Allocator);
           joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
         }
-  });
+      },
+      *LIS->getSlotIndexes(), *TRI);
 }
 
 bool RegisterCoalescer::isHighCostLiveInterval(LiveInterval &LI) {
   if (LI.valnos.size() < LargeIntervalSizeThreshold)
     return false;
   auto &Counter = LargeLIVisitCounter[LI.reg];
   if (Counter < LargeIntervalFreqThreshold) {
     Counter++;

lib/CodeGen/SplitKit.cpp

SlotIndex SplitEditor::buildSingleSubRegCopy(unsigned FromReg, unsigned ToReg,
   const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
   bool FirstCopy = !Def.isValid();
   MachineInstr *CopyMI = BuildMI(MBB, InsertBefore, DebugLoc(), Desc)
       .addReg(ToReg, RegState::Define | getUndefRegState(FirstCopy)
               | getInternalReadRegState(!FirstCopy), SubIdx)
       .addReg(FromReg, 0, SubIdx);
 
   BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
-  if (FirstCopy) {
-    SlotIndexes &Indexes = *LIS.getSlotIndexes();
+  if (FirstCopy) {
     Def = Indexes.insertMachineInstrInMaps(*CopyMI, Late).getRegSlot();
   } else {
     CopyMI->bundleWithPred();
   }
   LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubIdx);
   DestLI.refineSubRanges(Allocator, LaneMask,
-                         [Def, &Allocator](LiveInterval::SubRange& SR) {
+                         [Def, &Allocator](LiveInterval::SubRange &SR) {
                            SR.createDeadDef(Def, Allocator);
-  });
+                         },
+                         Indexes, TRI);
   return Def;
 }
 
 SlotIndex SplitEditor::buildCopy(unsigned FromReg, unsigned ToReg,
     LaneBitmask LaneMask, MachineBasicBlock &MBB,
     MachineBasicBlock::iterator InsertBefore, bool Late, unsigned RegIdx) {
   const MCInstrDesc &Desc = TII.get(TargetOpcode::COPY);
   if (LaneMask.all() || LaneMask == MRI.getMaxLaneMaskForVReg(FromReg)) {

test/CodeGen/SystemZ/regcoal-subranges-update.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple s390x-ibm-linux -mcpu=z13 -systemz-subreg-liveness -verify-machineinstrs -start-before simple-register-coalescing -stop-after greedy -o - %s | FileCheck %s
+
+# Check that when we split the live-range with several active lanes
+# as part of the live-range update, we correctly eliminate the VNI from
+# the relevant part.
+#
+# In this specific test, the register coalescer will:
+# 1. Merge %0 with %1, creating a live-range for the full value subreg_l32 + subreg_h32
+#    (actually %0 gets merge with %1 via rematerialization, and technically %0 and %1
+#     remain two different live-ranges.)
+# 2. Merge %2 with %1 triggering a split into the subreg_l32 + subreg_h32 ranges, since
+#    %2 only touches subreg_l32. As part of the split the subrange covering subreg_h32
+#    must contain only the VNI for the high part (i.e., the one tied with the remaaat of %0).
+# This used to be broken and trigger a machine verifier error, because we were not
+# clearing the dead value w.r.t. lanes when doing the splitting. I.e., we were ending
+# with a subrange referring a value that did not define that lane.
+#
+# PR40835
+---
+name:            main
+tracksRegLiveness: true
+body:             |
+  bb.0:
+
+    ; CHECK-LABEL: name: main
+    ; CHECK: [[LGHI:%[0-9]+]]:gr64bit = LGHI 43
+    ; CHECK: [[LGHI1:%[0-9]+]]:gr64bit = LGHI 43
+    ; CHECK: [[LGHI1]].subreg_l32:gr64bit = MSR [[LGHI1]].subreg_l32, [[LGHI1]].subreg_l32
+    ; CHECK: [[LGHI1]].subreg_l32:gr64bit = AHIMux [[LGHI1]].subreg_l32, 9, implicit-def dead $cc
+    ; CHECK: undef %3.subreg_l64:gr128bit = LGFI -245143785, implicit [[LGHI1]].subreg_l32
+    ; CHECK: [[DLGR:%[0-9]+]]:gr128bit = DLGR [[DLGR]], [[LGHI]]
+    ; CHECK: Return implicit [[DLGR]]
+    %0:gr64bit = LGHI 43
+    %1:gr32bit = COPY %0.subreg_l32
+    %1:gr32bit = MSR %1, %1
+    %2:gr32bit = COPY killed %1
+    %2:gr32bit = AHIMux killed %2, 9, implicit-def dead $cc
+    undef %3.subreg_l64:gr128bit = LGFI -245143785, implicit killed %2
+    %3:gr128bit = DLGR %3:gr128bit, killed %0
+    Return implicit killed %3
+
+...