[RegisterCoalescer] Avoid erasing copy that breaks subranges

[tpr]

Summary

I found a case where erasing a copy in coalescing causes a subrange to
be modified incorrectly.

It looks like it would be quite a large change to fix this properly,
such that subranges are updated correctly when a subreg is dead in and
live out of a copy being erased.

A possible alternative would be to recalculate subranges from scratch
for a register that is affected by this problem.

For now, I have just disabled that case of erasing a copy when subranges
are present.

Change-Id: Ib85a4e7e5458ec1b156cb84207c51cab63e92635

[kparzysz]

What exactly is done wrong in the testcase without your change? I see one extra IMPLICIT_DEF in the output, compared to running it with your change.

Updating live ranges should work correctly, disabling erasing copies is not the right thing to do.

Could you run the input through -run-pass=none first? It will produce a slightly better-looking .mir.

[kparzysz]

I missed the comment in the .mir file.

[tpr]

V2: This is a revised fix. Still not the proper fix, but at least it
doesn't stop a copy being erased.

Also tidied the test as suggested.

Here's the new commit message, as I don't think phabricator updates the
summary box:

[RegisterCoalescer] Recalculate subranges in some cases

Summary:
I found a case where erasing a copy in coalescing causes a subrange to
be modified incorrectly.

It looks like it would be quite a large change to fix this properly,
such that subranges are updated correctly when a subreg is dead in and
live out of a copy being erased.

So for now, in the case causing my problem, it now just recalculates
the whole live interval after the coalesce.

[tpr]

To try and diagnose this kind of problem in the future, I added code (not in this change) to always recalculate the live interval if there are subranges, and compare it with the one updated in RegisterCoalescer.cpp. The problem I ran into then is that RegisterCoalescer remembers more information about when subregs are undef and thus considered not live than is available in the MIR after coalescing. I wonder if there is some way of recording undef subregs in a use in MIR such that recalculating a live interval should always give the same result as updating in coalescing, and if it doesn't then you've found a bug.

[kparzysz]

Could you try D41802 and see if it works for you? I works with the testcase and it passes my local tests.

[tpr]

Superseded by D48102 from Krzysztof.

lib/CodeGen/RegisterCoalescer.h

class CoalescerPair {
     /// copy instruction.
     bool Flipped = false;
 
     /// The register class of the coalesced register, or NULL if DstReg
     /// is a physreg. This register class may be a super-register of both
     /// SrcReg and DstReg.
     const TargetRegisterClass *NewRC = nullptr;
 
+    /// Whether subranges need to be recalculated after coalescing.
+    bool NeedRecalcSubRanges = false;
+
   public:
     CoalescerPair(const TargetRegisterInfo &tri) : TRI(tri) {}
 
     /// Create a CoalescerPair representing a virtreg-to-physreg copy.
     /// No need to call setRegisters().
     CoalescerPair(unsigned VirtReg, unsigned PhysReg,
                   const TargetRegisterInfo &tri)
       : TRI(tri), DstReg(PhysReg), SrcReg(VirtReg) {}
public:
     /// Return the subregister index that DstReg will be coalesced into, or 0.
     unsigned getDstIdx() const { return DstIdx; }
 
     /// Return the subregister index that SrcReg will be coalesced into, or 0.
     unsigned getSrcIdx() const { return SrcIdx; }
 
     /// Return the register class of the coalesced register.
     const TargetRegisterClass *getNewRC() const { return NewRC; }
+
+    /// Get whether subranges need to be recalculated after coalescing.
+    bool getNeedRecalcSubRanges() const { return NeedRecalcSubRanges; }
+
+    /// Flag that subranges will need to be recalculated after coalescing.
+    void setNeedRecalcSubRanges() { NeedRecalcSubRanges = true; }
+
   };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_CODEGEN_REGISTERCOALESCER_H

lib/CodeGen/RegisterCoalescer.cpp

bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
 
   // SrcReg is guaranteed to be the register whose live interval that is
   // being merged.
   LIS->removeInterval(CP.getSrcReg());
 
   // Update regalloc hint.
   TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
 
+  if (CP.getNeedRecalcSubRanges()) {
+    // CoalescerPair decided that subranges need to be recalculated.
+    // Recalculate the whole live interval.
+    LIS->removeInterval(CP.getDstReg());
+    LIS->createAndComputeVirtRegInterval(CP.getDstReg());
+  }
+
   DEBUG({
     dbgs() << "\tSuccess: " << printReg(CP.getSrcReg(), TRI, CP.getSrcIdx())
            << " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
     dbgs() << "\tResult = ";
     if (CP.isPhys())
       dbgs() << printReg(CP.getDstReg(), TRI);
     else
       dbgs() << LIS->getInterval(CP.getDstReg());
public:
   /// CR_Replace values in LR. Collect end points for restoring the live range
   /// after joining.
   void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
                    bool changeInstrs);
 
   /// Removes subranges starting at copies that get removed. This sometimes
   /// happens when undefined subranges are copied around. These ranges contain
   /// no useful information and can be removed.
-  void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
+  /// Returns whether subrange recalculation is needed.
+  bool pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
 
   /// Pruning values in subranges can lead to removing segments in these
   /// subranges started by IMPLICIT_DEFs. The corresponding segments in
   /// the main range also need to be removed. This function will mark
   /// the corresponding values in the main range as pruned, so that
   /// eraseInstrs can do the final cleanup.
   /// The parameter @p LI must be the interval whose main range is the
   /// live range LR.
case CR_Merge:
       break;
     case CR_Unresolved:
     case CR_Impossible:
       llvm_unreachable("Unresolved conflicts");
     }
   }
 }
 
-void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
+// Returns whether subrange recalculation is needed.
+bool JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
+  bool NeedRecalcSubRanges = false;
   // Look for values being erased.
   bool DidPrune = false;
   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
     // We should trigger in all cases in which eraseInstrs() does something.
     // match what eraseInstrs() is doing, print a message so
     if (Vals[i].Resolution != CR_Erase &&
         (Vals[i].Resolution != CR_Keep || !Vals[i].ErasableImplicitDef ||
          !Vals[i].Pruned))
       continue;
 
     // Check subranges at the point where the copy will be removed.
     SlotIndex Def = LR.getValNumInfo(i)->def;
     // Print message so mismatches with eraseInstrs() can be diagnosed.
     DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def << '\n');
     for (LiveInterval::SubRange &S : LI.subranges()) {
       LiveQueryResult Q = S.Query(Def);
 
-      // If a subrange starts at the copy then an undefined value has been
-      // copied and we must remove that subrange value as well.
+      // If a subrange starts at the copy then an undefined value has
+      // possibly, but not definitely, been copied. We need to remove the
+      // subrange value, but we need to ask for subrange recalculation too, in
+      // case it wasn't dead.
       VNInfo *ValueOut = Q.valueOutOrDead();
       if (ValueOut != nullptr && Q.valueIn() == nullptr) {
         DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)
                      << " at " << Def << "\n");
         LIS->pruneValue(S, Def, nullptr);
         DidPrune = true;
         // Mark value number as unused.
         ValueOut->markUnused();
+        NeedRecalcSubRanges = true;
         continue;
       }
       // If a subrange ends at the copy, then a value was copied but only
       // partially used later. Shrink the subregister range appropriately.
       if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) {
         DEBUG(dbgs() << "\t\tDead uses at sublane " << PrintLaneMask(S.LaneMask)
                      << " at " << Def << "\n");
         ShrinkMask |= S.LaneMask;
       }
     }
   }
   if (DidPrune)
     LI.removeEmptySubRanges();
+  return NeedRecalcSubRanges;
 }
 
 /// Check if any of the subranges of @p LI contain a definition at @p Def.
 static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def) {
   for (LiveInterval::SubRange &SR : LI.subranges()) {
     if (VNInfo *VNI = SR.Query(Def).valueOutOrDead())
       if (VNI->def == Def)
         return true;
if (!RHS.hasSubRanges()) {
       }
     }
     DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n");
 
     // Pruning implicit defs from subranges may result in the main range
     // having stale segments.
     LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
 
-    LHSVals.pruneSubRegValues(LHS, ShrinkMask);
-    RHSVals.pruneSubRegValues(LHS, ShrinkMask);
+    if (LHSVals.pruneSubRegValues(LHS, ShrinkMask))
+      CP.setNeedRecalcSubRanges();
+    if (RHSVals.pruneSubRegValues(LHS, ShrinkMask))
+      CP.setNeedRecalcSubRanges();
   }
 
   // The merging algorithm in LiveInterval::join() can't handle conflicting
   // value mappings, so we need to remove any live ranges that overlap a
   // CR_Replace resolution. Collect a set of end points that can be used to
   // restore the live range after joining.
   SmallVector<SlotIndex, 8> EndPoints;
   LHSVals.pruneValues(RHSVals, EndPoints, true);

test/CodeGen/AMDGPU/coalescing-with-subregs-in-loop-bug.mir

+# RUN: llc -mtriple=amdgcn--amdpal -mcpu=gfx803 -run-pass=simple-register-coalescing,rename-independent-subregs %s -o - | FileCheck -check-prefix=GCN %s
+
+# This test is for a bug where the following happens:
+#
+# Inside the loop, %29.sub2 is used in a V_LSHLREV whose result is then used
+# in an LDS read. %29 is a 128 bit value that is linked by copies to
+# %45 (from phi elimination), %28 (the value in the loop pre-header),
+# %31 (defined and subreg-modified in the loop, and used after the loop)
+# and %30:
+#
+#     %45:vreg_128 = COPY killed %28
+# bb.39:
+#     %29:vreg_128 = COPY killed %45
+#     %39:vgpr_32 = V_LSHLREV_B32_e32 2, %29.sub2, implicit $exec
+#     %31:vreg_128 = COPY killed %29
+#     %31.sub1:vreg_128 = COPY %34
+#     %30:vreg_128 = COPY %31
+#     %45:vreg_128 = COPY killed %30
+#     S_CBRANCH_EXECNZ %bb.39, implicit $exec
+#     S_BRANCH %bb.40
+# bb.40:
+#     undef %32.sub0:vreg_128 = COPY killed %31.sub0
+#
+# So this coalesces together into a single 128 bit value whose sub1 is modified
+# in the loop, but the sub2 used in the V_LSHLREV is not modified in the loop.
+#
+# The bug is that the coalesced value has a L00000004 subrange (for sub2) that
+# says that it is not live up to the end of the loop block. The symptom is that
+# Rename Independent Subregs separates sub2 into its own register, and it is
+# not live round the loop, so that pass adds an IMPLICIT_DEF for it just before
+# the loop backedge.
+
+# GCN: bb.1 (%ir-block.6):
+# GCN: V_LSHLREV_B32_e32 2, [[val:%[0-9][0-9]*]].sub2
+# GCN-NOT: [[val]]:vreg_128 = IMPLICIT_DEF
+
+--- |
+  ; ModuleID = '../test/CodeGen/AMDGPU/coalescing-with-subregs-in-loop-bug.mir'
+  source_filename = "../test/CodeGen/AMDGPU/coalescing-with-subregs-in-loop-bug.mir"
+  target datalayout = "e-p:64:64-p1:64:64-p2:32:32-p3:32:32-p4:64:64-p5:32:32-p6:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-S32-A5"
+  target triple = "amdgcn--amdpal"
+  
+  define dllexport amdgpu_cs void @_amdgpu_cs_main(i32 inreg, i32 inreg, i32 inreg, <3 x i32> inreg, i32 inreg, <3 x i32>) local_unnamed_addr #0 {
+  .entry:
+    br label %6
+  
+  ; <label>:6:                                      ; preds = %6, %.entry
+    %7 = bitcast i32 addrspace(3)* undef to <2 x i32> addrspace(3)*
+    %8 = bitcast i32 addrspace(3)* undef to <2 x i32> addrspace(3)*
+    %9 = bitcast i32 addrspace(3)* undef to <2 x i32> addrspace(3)*
+    %10 = bitcast i32 addrspace(3)* undef to <2 x i32> addrspace(3)*
+    %11 = bitcast i32 addrspace(3)* undef to <2 x i32> addrspace(3)*
+    %12 = bitcast i32 addrspace(3)* undef to <2 x i32> addrspace(3)*
+    br i1 undef, label %13, label %6
+  
+  ; <label>:13:                                     ; preds = %6
+    ret void
+  }
+  
+  attributes #0 = { "target-cpu"="gfx803" }
+
+...
+---
+name:            _amdgpu_cs_main
+alignment:       0
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: sreg_64, preferred-register: '' }
+  - { id: 1, class: sreg_64, preferred-register: '' }
+  - { id: 2, class: sreg_64, preferred-register: '' }
+  - { id: 3, class: sgpr_32, preferred-register: '' }
+  - { id: 4, class: sgpr_32, preferred-register: '' }
+  - { id: 5, class: sgpr_32, preferred-register: '' }
+  - { id: 6, class: sgpr_32, preferred-register: '' }
+  - { id: 7, class: sreg_32_xm0, preferred-register: '' }
+  - { id: 8, class: sgpr_32, preferred-register: '' }
+  - { id: 9, class: sreg_32_xm0, preferred-register: '' }
+  - { id: 10, class: sreg_32_xm0, preferred-register: '' }
+  - { id: 11, class: sreg_32_xm0, preferred-register: '' }
+  - { id: 12, class: vreg_64, preferred-register: '' }
+  - { id: 13, class: vreg_64, preferred-register: '' }
+  - { id: 14, class: vreg_64, preferred-register: '' }
+  - { id: 15, class: vreg_64, preferred-register: '' }
+  - { id: 16, class: vreg_64, preferred-register: '' }
+  - { id: 17, class: vreg_64, preferred-register: '' }
+  - { id: 18, class: sreg_64, preferred-register: '$vcc' }
+  - { id: 19, class: vreg_128, preferred-register: '' }
+  - { id: 20, class: vreg_128, preferred-register: '' }
+  - { id: 21, class: vreg_128, preferred-register: '' }
+  - { id: 22, class: vreg_128, preferred-register: '' }
+  - { id: 23, class: vreg_128, preferred-register: '' }
+  - { id: 24, class: vreg_128, preferred-register: '' }
+  - { id: 25, class: vreg_128, preferred-register: '' }
+  - { id: 26, class: vreg_128, preferred-register: '' }
+  - { id: 27, class: vreg_128, preferred-register: '' }
+  - { id: 28, class: vreg_128, preferred-register: '' }
+  - { id: 29, class: vreg_128, preferred-register: '' }
+  - { id: 30, class: vreg_128, preferred-register: '' }
+  - { id: 31, class: vreg_128, preferred-register: '' }
+  - { id: 32, class: vreg_128, preferred-register: '' }
+  - { id: 33, class: vgpr_32, preferred-register: '' }
+  - { id: 34, class: sreg_32, preferred-register: '' }
+  - { id: 35, class: vreg_128, preferred-register: '' }
+  - { id: 36, class: vreg_128, preferred-register: '' }
+  - { id: 37, class: vreg_128, preferred-register: '' }
+  - { id: 38, class: vgpr_32, preferred-register: '' }
+  - { id: 39, class: vgpr_32, preferred-register: '' }
+  - { id: 40, class: vgpr_32, preferred-register: '' }
+  - { id: 41, class: vgpr_32, preferred-register: '' }
+  - { id: 42, class: vreg_128, preferred-register: '' }
+  - { id: 43, class: sreg_64, preferred-register: '' }
+  - { id: 44, class: vreg_128, preferred-register: '' }
+  - { id: 45, class: vreg_128, preferred-register: '' }
+liveins:         
+frameInfo:       
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  maxCallFrameSize: 4294967295
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:      
+stack:           
+constants:       
+body:             |
+  bb.0..entry:
+    successors: %bb.1(0x80000000)
+  
+    %3:sgpr_32 = S_MOV_B32 0
+    undef %19.sub1:vreg_128 = COPY undef %3
+    dead %4:sgpr_32 = S_MOV_B32 1
+    %20:vreg_128 = COPY killed %19
+    %20.sub1:vreg_128 = COPY undef %4
+    dead %5:sgpr_32 = S_MOV_B32 2
+    %21:vreg_128 = COPY killed %20
+    %21.sub1:vreg_128 = COPY undef %5
+    dead %6:sgpr_32 = S_MOV_B32 3
+    %22:vreg_128 = COPY killed %21
+    %22.sub1:vreg_128 = COPY undef %6
+    dead %7:sreg_32_xm0 = S_MOV_B32 4
+    %23:vreg_128 = COPY killed %22
+    %23.sub1:vreg_128 = COPY undef %7
+    dead %8:sgpr_32 = S_MOV_B32 5
+    %24:vreg_128 = COPY killed %23
+    %24.sub1:vreg_128 = COPY undef %8
+    dead %9:sreg_32_xm0 = S_MOV_B32 6
+    %25:vreg_128 = COPY killed %24
+    %25.sub1:vreg_128 = COPY undef %9
+    dead %10:sreg_32_xm0 = S_MOV_B32 7
+    %26:vreg_128 = COPY killed %25
+    %26.sub1:vreg_128 = COPY undef %10
+    %11:sreg_32_xm0 = S_MOV_B32 255
+    %27:vreg_128 = COPY killed %26
+    %27.sub1:vreg_128 = COPY %11
+    %28:vreg_128 = COPY killed %27
+    %28.sub2:vreg_128 = COPY killed %11
+    %2:sreg_64 = S_MOV_B64 0
+    %34:sreg_32 = S_MOV_B32 7
+    %37:vreg_128 = COPY undef %42:vreg_128
+    %43:sreg_64 = COPY killed %2
+    %44:vreg_128 = COPY killed %37
+    %45:vreg_128 = COPY killed %28
+  
+  bb.1 (%ir-block.6):
+    successors: %bb.2(0x04000000), %bb.1(0x7c000000)
+  
+    %29:vreg_128 = COPY killed %45
+    %36:vreg_128 = COPY killed %44
+    %0:sreg_64 = COPY killed %43
+    %39:vgpr_32 = V_LSHLREV_B32_e32 2, %29.sub2, implicit $exec
+    %41:vgpr_32 = V_ADD_I32_e32 1152, %39, implicit-def dead $vcc, implicit $exec
+    $m0 = S_MOV_B32 -1
+    %12:vreg_64 = DS_READ2_B32 killed %41, 0, 1, 0, implicit $m0, implicit $exec :: (load 8 from %ir.7, align 4, addrspace 3)
+    %13:vreg_64 = DS_READ2_B32 %39, -112, -111, 0, implicit $m0, implicit $exec :: (load 8 from %ir.8, align 4, addrspace 3)
+    %14:vreg_64 = DS_READ2_B32 %39, 0, 1, 0, implicit $m0, implicit $exec :: (load 8 from %ir.9, align 4, addrspace 3)
+    %40:vgpr_32 = V_ADD_I32_e32 1160, %39, implicit-def dead $vcc, implicit $exec
+    %15:vreg_64 = DS_READ2_B32 killed %40, 0, 1, 0, implicit $m0, implicit $exec :: (load 8 from %ir.10, align 4, addrspace 3)
+    %16:vreg_64 = DS_READ2_B32 %39, -110, -109, 0, implicit $m0, implicit $exec :: (load 8 from %ir.11, align 4, addrspace 3)
+    %17:vreg_64 = DS_READ2_B32 %39, 2, 3, 0, implicit $m0, implicit $exec :: (load 8 from %ir.12, align 4, addrspace 3)
+    undef %35.sub1:vreg_128 = COPY undef %34
+    %31:vreg_128 = COPY killed %29
+    %31.sub1:vreg_128 = COPY %34
+    %38:vgpr_32 = V_ADD_I32_e32 1, %36.sub0, implicit-def dead $vcc, implicit $exec
+    %18:sreg_64 = V_CMP_LT_I32_e64 5, %38, implicit $exec
+    %1:sreg_64 = S_OR_B64 killed %18, killed %0, implicit-def $scc
+    %30:vreg_128 = COPY %31
+    %43:sreg_64 = COPY %1
+    %44:vreg_128 = COPY %35
+    %45:vreg_128 = COPY killed %30
+    $exec = S_ANDN2_B64_term $exec, %1
+    S_CBRANCH_EXECNZ %bb.1, implicit $exec
+    S_BRANCH %bb.2
+  
+  bb.2 (%ir-block.13):
+    $exec = S_OR_B64 $exec, killed %1, implicit-def $scc
+    %33:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    undef %32.sub0:vreg_128 = COPY killed %31.sub0
+    %32.sub2:vreg_128 = COPY %33
+    S_ENDPGM
+
+...
+
+
+