Do not abort on unresolved conflicts when joining subranges

[kparzysz]

Summary

These conflicts can legitimately happen when merging registers where subregister definitions of one taint, but not invalidate the other. While the main range conflict resolution can deal with it, the subrange conflicts will remain due to the overlapping segments.

[MatzeB]

This should ideally have a .mir test with a minimum reproducer. Maybe it is possible to make an actual test out of the comment in the code (see for example the other .mir tests in the AMDGPU directory on how you can model nearly all situations by appending implicit defs/uses to NOP instructions).

lib/CodeGen/RegisterCoalescer.cpp

2342–2377

I am trying to understand this, let's look at :sub1 for example: It is defined in 736 and read in 976, in that time :sub1 of vreg140 cannot be live or the join would be invalid. After that :sub1 is written in 1008 and read in 1248, in this time vreg131:sub1 cannot be live or the join would be invalid. I don't see an overlap in the subregisters here.

[kparzysz]

lib/CodeGen/RegisterCoalescer.cpp

2342–2377

Sub1 may not be the best choice here. Consider sub2 instead: vreg140:sub2 is first defined in 704, then it is live until 1008 and subsequently overwritten in 1040. The live subrange for it will be [704,1008)[1040,1248). This will overlap with the live range for vreg131:sub2. The join of vreg131 and vreg140 is valid, since all the lanes written via vreg131:subN = COPY ... are never actually used via vreg140:subN. They are considered "used" for the purpose of liveness tracking, but are not actually used by the program. The function resolveConflicts checks specifically for that (via taintExtent and usesLanes).

[kparzysz]

Created a reduced .mir testcase.

[qcolombet]

lib/CodeGen/RegisterCoalescer.cpp

2342–2377

I would not expect the example in the comment to pass the usesLanes checks because of the lack of undef flags, right?
I.e., that does not seem correct to jump to the Replace conclusion.

They are considered "used" for the purpose of liveness tracking, but are not actually used by the program.

But if they are alive that means they are used right? I mean we couldn't merge them unless vreg140:sub1 has read-undef, could we?

Basically, I don't like us making assumptions on what the liveness models compared to what the program actually uses. I am afraid it may work for some targets, but not all of them. Therefore, I would rather be conservatively correct (that we have right now) than guessing around the liveness.

[kparzysz]

The problem is somewhere else: live subranges should not be extended to other subregs' defs.

lib/CodeGen/RegisterCoalescer.cpp

2342–2377

My previous comments are incorrect. The problem is in the fact that live subranges were extended to other subregs' defs. I will submit another patch that corrects that issue.

[kparzysz]

New fix: https://reviews.llvm.org/D24190

lib/CodeGen/RegisterCoalescer.cpp

 bool JoinVals::resolveConflicts(JoinVals &Other) {
   for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
     Val &V = Vals[i];
     assert (V.Resolution != CR_Impossible && "Unresolvable conflict");
     if (V.Resolution != CR_Unresolved)
       continue;
     DEBUG(dbgs() << "\t\tconflict at " << PrintReg(Reg) << ':' << i
                  << '@' << LR.getValNumInfo(i)->def << '\n');
-    if (SubRangeJoin)
-      return false;
+    if (SubRangeJoin) {
+      // Unresolved subrange conflicts may remain here as a result of merging
+      // registers where subregister definitions of one register are
+      // overwritten by corresponding definitions of the other register.
+      // For example, in this case, whem coalescing vreg140 into vreg131:
+      //   704B     %vreg140<def> = ...
+      //   720B     %vreg131<def> = COPY %vreg140
+      //   736B     %vreg131:sub1<def> = COPY %vreg48
+      //   768B     %vreg131:sub2<def> = COPY %vreg23
+      //   800B     %vreg131:sub3<def> = COPY %vreg24
+      //   832B     %vreg131:sub4<def> = COPY %vreg25
+      //   864B     %vreg131:sub5<def> = COPY %vreg26
+      //   896B     %vreg131:sub6<def> = COPY %vreg40
+      //   928B     %vreg131:sub7<def> = COPY %vreg42
+      //   960B     %vreg131:sub8<def> = COPY %vreg44
+      //   976B     ... = use %vreg131
+      //   1008B    %vreg140:sub1<def> = COPY %vreg54
+      //   1040B    %vreg140:sub2<def> = COPY %vreg23
+      //   1072B    %vreg140:sub3<def> = COPY %vreg24
+      //   1104B    %vreg140:sub4<def> = COPY %vreg25
+      //   1136B    %vreg140:sub5<def> = COPY %vreg26
+      //   1168B    %vreg140:sub6<def> = COPY %vreg50
+      //   1200B    %vreg140:sub7<def> = COPY %vreg51
+      //   1232B    %vreg140:sub8<def> = COPY %vreg52
+      //   1248B    ... = use %vreg140
+      // The conflict resolution for the main live ranges of both registers
+      // can determine that the coalescing is legal and may proceed, but the
+      // subregister ranges will still contain conflicts, since the subranges
+      // will overlap between the two virtual registers. Since repeating of
+      // the resolution code below for subregisters could only result in
+      // CR_Replace, and the legality has already been determined, assume
+      // the resolution to be CR_Replace without repeating the work.
+      V.Resolution = CR_Replace;
+      continue;
+    }
 
     ++NumLaneConflicts;
     assert(V.OtherVNI && "Inconsistent conflict resolution.");
     VNInfo *VNI = LR.getValNumInfo(i);
     const Val &OtherV = Other.Vals[V.OtherVNI->id];
 
     // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
     // join, those lanes will be tainted with a wrong value. Get the extent of
     // the tainted lanes.
DEBUG({
     for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {
       dbgs() << EndPoints[i];
       if (i != n-1)
         dbgs() << ',';
     }
     dbgs() << ":  " << LRange << '\n';
   });
   LIS->extendToIndices(LRange, EndPoints);
+  ShrinkMask |= LaneMask;
 }
 
 void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
                                           const LiveRange &ToMerge,
                                           LaneBitmask LaneMask,
                                           CoalescerPair &CP) {
   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
   for (LiveInterval::SubRange &R : LI.subranges()) {

test/CodeGen/AMDGPU/coalescer-subreg-join.mir

+# RUN: llc -march=amdgcn -run-pass simple-register-coalescing -o - %s | FileCheck %s
+# Check that %11 and %20 have been coalesced.
+# CHECK: IMAGE_SAMPLE_C_D_O_V1_V16 %[[REG:[0-9]+]]
+# CHECK: IMAGE_SAMPLE_C_D_O_V1_V16 %[[REG]]
+
+---
+name:            main
+alignment:       0
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: sreg_64 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: vgpr_32 }
+  - { id: 3, class: sreg_256 }
+  - { id: 4, class: sreg_128 }
+  - { id: 5, class: sreg_256 }
+  - { id: 6, class: sreg_128 }
+  - { id: 7, class: sreg_512 }
+  - { id: 9, class: vreg_512 }
+  - { id: 11, class: vreg_512 }
+  - { id: 18, class: vgpr_32 }
+  - { id: 20, class: vreg_512 }
+  - { id: 27, class: vgpr_32 }
+liveins:
+  - { reg: '%sgpr2_sgpr3', virtual-reg: '%0' }
+  - { reg: '%vgpr2', virtual-reg: '%1' }
+  - { reg: '%vgpr3', virtual-reg: '%2' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+body:             |
+  bb.0:
+    liveins: %sgpr2_sgpr3, %vgpr2, %vgpr3
+
+    %0 = COPY %sgpr2_sgpr3
+    %1 = COPY %vgpr2
+    %2 = COPY %vgpr3
+    %3 = S_LOAD_DWORDX8_IMM %0, 0
+    %4 = S_LOAD_DWORDX4_IMM %0, 12
+    %5 = S_LOAD_DWORDX8_IMM %0, 16
+    %6 = S_LOAD_DWORDX4_IMM %0, 28
+    undef %7.sub0 = S_MOV_B32 212739
+    %20 = COPY %7
+    %11 = COPY %20
+    %11.sub1 = COPY %1
+    %11.sub2 = COPY %1
+    %11.sub3 = COPY %1
+    %11.sub4 = COPY %1
+    %11.sub5 = COPY %1
+    %11.sub6 = COPY %1
+    %11.sub7 = COPY %1
+    %11.sub8 = COPY %1
+    dead %18 = IMAGE_SAMPLE_C_D_O_V1_V16 %11, %3, %4, 1, 0, 0, 0, 0, 0, 0, -1, implicit %exec
+    %20.sub1 = COPY %2
+    %20.sub2 = COPY %2
+    %20.sub3 = COPY %2
+    %20.sub4 = COPY %2
+    %20.sub5 = COPY %2
+    %20.sub6 = COPY %2
+    %20.sub7 = COPY %2
+    %20.sub8 = COPY %2
+    dead %27 = IMAGE_SAMPLE_C_D_O_V1_V16 %20, %5, %6, 1, 0, 0, 0, 0, 0, 0, -1, implicit %exec
+
+...