[RegisterCoalescer] Fix for assert in removePartialRedundancy

[tpr]

Summary

I got "Use not jointly dominated by defs" when removePartialRedundancy
attempted to prune then re-extend a subrange whose only liveness was a
dead def at the copy being removed.

Change-Id: I6f894e9f517f71e921e0c6d81d28c5f344db8dad

[MatzeB]

It would help review if you could describe the exact situation this happens. I am wondering:

• Why isn't this fix necessary in the main liverange?
• Is the fix only necessary for removePartialRedundancy() or should be pruneValue() or extendToIndices() so it applies to all similar situations?

[MatzeB]

Please read https://llvm.org/docs/MIRLangRef.html#simplifying-mir-files

Generally we should have a short test that just exposes the problem (such short tests also often intuitively demonstrate the problem that is fixed) rather than hundreds of lines of dumped IR.

[tpr]

V2: Removed junk from test; improved comment.

[tpr]

Hi Matthias

Thanks for the pointer on MIR tests. I stripped out all the unnecessary IR, but I left the MIR as it was because that was already the result of bugpointing the original test case.

Is that comment better for understanding the situation in which it happens?

Why isn't this fix necessary in the main liverange?

The main liverange would never be immediately dead at the copy because the dead copy would have been removed before getting to removePartialRedundancy, right?

Is the fix only necessary for removePartialRedundancy() or should be pruneValue() or extendToIndices() so it applies to all similar situations?

I don't know the answer to that. But note that it is only valid to remove the endpoint at the same index as the copy because we know it must come from a dead def, rather than a normal use at the same place. We know that because the copy is a full copy. That same thing might not apply in other cases of pruneValue()/extendToIndices().

[MatzeB]

LGTM with nitpicks addressed.

lib/CodeGen/RegisterCoalescer.cpp

1141

Using SlotIndex::isSameInstr() would make the intention more clear.

test/CodeGen/AMDGPU/regcoalescing-remove-partial-redundancy-assert.mir

11–14

Could you try if the test still works with the registers: block removed? It seems the machine operands below have the register classes annotated anyway.

[tpr]

test/CodeGen/AMDGPU/regcoalescing-remove-partial-redundancy-assert.mir

11–14

Yes, it does work without the registers: block. I will remove it.

[tpr]

V3: Addressed minor review comments.
No need to re-approve.

lib/CodeGen/RegisterCoalescer.cpp

bool RegisterCoalescer::removePartialRedundancy(const CoalescerPair &CP,
 
   // Now, do the same for its subranges.
   for (LiveInterval::SubRange &SR : IntB.subranges()) {
     EndPoints.clear();
     VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
     assert(BValNo && "All sublanes should be live");
     LIS->pruneValue(SR, CopyIdx.getRegSlot(), &EndPoints);
     BValNo->markUnused();
+    // We can have a situation where the result of the original copy is live,
+    // but is immediately dead in this subrange, e.g. [336r,336d:0). That makes
+    // the copy appear as an endpoint from pruneValue(), but we don't want it
+    // to because the copy has been removed.  We can go ahead and remove that
+    // endpoint; there is no other situation here that there could be a use at
+    // the same place as we know that the copy is a full copy.
+    for (unsigned I = 0; I != EndPoints.size(); ) {
+      if (!EndPoints[I].getInstrDistance(CopyIdx)) {
+        EndPoints[I] = EndPoints.back();
+        EndPoints.pop_back();
+        continue;
+      }
+      ++I;
+    }
     LIS->extendToIndices(SR, EndPoints);
   }
   // If any dead defs were extended, truncate them.
   shrinkToUses(&IntB);
 
   // Finally, update the live-range of IntA.
   shrinkToUses(&IntA);
   return true;

test/CodeGen/AMDGPU/regcoalescing-remove-partial-redundancy-assert.mir

+# RUN: llc -march=amdgcn -mcpu=gfx803 -run-pass simple-register-coalescing -verify-machineinstrs -o - %s | FileCheck --check-prefix=GCN %s
+#
+# This test gave "Use not jointly dominated by defs" when
+# removePartialRedundancy attempted to prune and then re-extend a subrange.
+#
+# GCN: {{^body}}
+
+---
+name:            _amdgpu_ps_main
+tracksRegLiveness: true
+registers:       
+  - { id: 0, class: sreg_128 }
+  - { id: 1, class: sreg_128 }
+  - { id: 2, class: sreg_128 }
+  - { id: 3, class: sreg_128 }
+  - { id: 4, class: vreg_128 }
+  - { id: 5, class: vgpr_32 }
+  - { id: 6, class: sreg_128 }
+  - { id: 7, class: sreg_128 }
+  - { id: 8, class: sreg_128 }
+  - { id: 9, class: sreg_128 }
+  - { id: 10, class: sreg_128 }
+  - { id: 11, class: sreg_128 }
+  - { id: 12, class: sreg_128 }
+  - { id: 13, class: sreg_128 }
+  - { id: 14, class: sreg_128 }
+  - { id: 15, class: sreg_128 }
+  - { id: 16, class: sreg_128 }
+  - { id: 17, class: sreg_128 }
+  - { id: 18, class: sreg_128 }
+  - { id: 19, class: sreg_128 }
+  - { id: 20, class: sreg_128 }
+  - { id: 21, class: vgpr_32 }
+  - { id: 22, class: vgpr_32 }
+  - { id: 23, class: vgpr_32 }
+  - { id: 24, class: sreg_32_xm0 }
+  - { id: 25, class: sreg_32_xm0 }
+  - { id: 26, class: sreg_32 }
+  - { id: 27, class: sreg_128 }
+  - { id: 28, class: sreg_32_xm0_xexec }
+  - { id: 29, class: sreg_128 }
+  - { id: 30, class: sreg_128 }
+  - { id: 31, class: sreg_32_xm0 }
+  - { id: 32, class: sreg_32_xm0 }
+  - { id: 33, class: sreg_128 }
+  - { id: 34, class: sreg_32_xm0 }
+  - { id: 35, class: vgpr_32 }
+  - { id: 36, class: sreg_32_xm0_xexec }
+  - { id: 37, class: sreg_128 }
+  - { id: 38, class: vgpr_32 }
+  - { id: 39, class: vgpr_32 }
+  - { id: 40, class: vgpr_32 }
+  - { id: 41, class: vgpr_32 }
+  - { id: 42, class: vgpr_32 }
+  - { id: 43, class: vgpr_32 }
+  - { id: 44, class: vgpr_32 }
+  - { id: 45, class: sreg_32 }
+  - { id: 46, class: vgpr_32 }
+  - { id: 47, class: vgpr_32 }
+  - { id: 48, class: sreg_128 }
+  - { id: 49, class: vgpr_32 }
+  - { id: 50, class: sreg_64_xexec }
+  - { id: 51, class: sreg_128 }
+  - { id: 52, class: sreg_32_xm0 }
+  - { id: 53, class: sreg_128 }
+  - { id: 54, class: sgpr_32 }
+  - { id: 55, class: vgpr_32 }
+  - { id: 56, class: vgpr_32 }
+  - { id: 57, class: sgpr_32 }
+  - { id: 58, class: vgpr_32 }
+  - { id: 59, class: vgpr_32 }
+  - { id: 60, class: sgpr_32 }
+  - { id: 61, class: vgpr_32 }
+  - { id: 62, class: vgpr_32 }
+  - { id: 63, class: sreg_128 }
+  - { id: 64, class: sreg_64 }
+  - { id: 65, class: sreg_64 }
+  - { id: 66, class: sreg_32_xm0_xexec }
+  - { id: 67, class: sreg_128 }
+  - { id: 68, class: sreg_128 }
+  - { id: 69, class: sreg_32_xm0 }
+  - { id: 70, class: sreg_32_xm0 }
+  - { id: 71, class: sreg_32_xm0 }
+  - { id: 72, class: sreg_32_xm0 }
+  - { id: 73, class: sreg_32_xm0 }
+  - { id: 74, class: sreg_32_xm0 }
+  - { id: 75, class: sreg_32_xm0 }
+  - { id: 76, class: vgpr_32 }
+  - { id: 77, class: vgpr_32 }
+  - { id: 78, class: vgpr_32 }
+  - { id: 79, class: sreg_32_xm0 }
+  - { id: 80, class: sreg_32_xm0 }
+  - { id: 81, class: sreg_128 }
+  - { id: 82, class: vgpr_32 }
+  - { id: 83, class: sreg_32_xm0 }
+  - { id: 84, class: sreg_128 }
+  - { id: 85, class: sreg_32_xm0 }
+  - { id: 86, class: sreg_32_xm0 }
+  - { id: 87, class: sreg_32_xm0 }
+  - { id: 88, class: sreg_32_xm0 }
+  - { id: 89, class: sreg_128 }
+  - { id: 90, class: sreg_128 }
+  - { id: 91, class: sreg_32_xm0 }
+  - { id: 92, class: sreg_128 }
+  - { id: 93, class: sreg_32_xm0 }
+  - { id: 94, class: sreg_32_xm0 }
+  - { id: 95, class: sreg_64 }
+  - { id: 96, class: sreg_64 }
+  - { id: 97, class: sreg_32_xm0 }
+  - { id: 98, class: sreg_32_xm0 }
+  - { id: 99, class: sreg_32_xm0 }
+  - { id: 100, class: sreg_32_xm0 }
+  - { id: 101, class: sreg_128 }
+  - { id: 102, class: sreg_32_xm0 }
+  - { id: 103, class: sreg_32_xm0 }
+  - { id: 104, class: sreg_32_xm0 }
+  - { id: 105, class: sreg_32_xm0 }
+  - { id: 106, class: sreg_128 }
+  - { id: 107, class: sreg_64_xexec }
+  - { id: 108, class: vgpr_32 }
+  - { id: 109, class: vreg_128 }
+  - { id: 110, class: vreg_128 }
+  - { id: 111, class: vreg_128 }
+  - { id: 112, class: vgpr_32 }
+  - { id: 113, class: vreg_128 }
+  - { id: 114, class: vgpr_32 }
+  - { id: 115, class: vreg_128 }
+  - { id: 116, class: vgpr_32 }
+  - { id: 117, class: vreg_128 }
+  - { id: 118, class: vgpr_32 }
+  - { id: 119, class: vreg_128 }
+  - { id: 120, class: vreg_128 }
+  - { id: 121, class: vreg_128 }
+  - { id: 122, class: vgpr_32 }
+  - { id: 123, class: vgpr_32 }
+  - { id: 124, class: vgpr_32 }
+  - { id: 125, class: vreg_128 }
+  - { id: 126, class: vgpr_32 }
+  - { id: 127, class: vreg_128 }
+  - { id: 128, class: vreg_128 }
+  - { id: 129, class: vgpr_32 }
+  - { id: 130, class: vreg_128 }
+  - { id: 131, class: vgpr_32 }
+  - { id: 132, class: vgpr_32 }
+  - { id: 133, class: vgpr_32 }
+  - { id: 134, class: vgpr_32 }
+  - { id: 135, class: vgpr_32 }
+  - { id: 136, class: vreg_128 }
+  - { id: 137, class: vreg_128 }
+  - { id: 138, class: vreg_128 }
+  - { id: 139, class: vreg_128 }
+body:             |
+  bb.0:
+    successors: %bb.1, %bb.2
+  
+    %21:vgpr_32 = V_TRUNC_F32_e32 undef %22:vgpr_32, implicit $exec
+    %23:vgpr_32 = V_CVT_U32_F32_e32 killed %21, implicit $exec
+    %108:vgpr_32 = V_LSHRREV_B32_e32 4, killed %23, implicit $exec
+    undef %109.sub1:vreg_128 = COPY %108
+    %28:sreg_32_xm0_xexec = S_BUFFER_LOAD_DWORD_IMM undef %29:sreg_128, 3044, 0 :: (dereferenceable invariant load 4)
+    S_CMP_EQ_U32 killed %28, 0, implicit-def $scc
+    S_CBRANCH_SCC0 %bb.2, implicit killed $scc
+  
+  bb.1:
+    %138:vreg_128 = COPY killed %109
+    S_BRANCH %bb.9
+  
+  bb.2:
+    successors: %bb.3, %bb.4
+  
+    S_CBRANCH_SCC0 %bb.4, implicit undef $scc
+  
+  bb.3:
+    %136:vreg_128 = COPY killed %109
+    S_BRANCH %bb.5
+  
+  bb.4:
+    %136:vreg_128 = COPY killed %109
+  
+  bb.5:
+    successors: %bb.6, %bb.8
+  
+    %110:vreg_128 = COPY killed %136
+    dead %32:sreg_32_xm0 = S_MOV_B32 0
+    %111:vreg_128 = COPY %110
+    %111.sub3:vreg_128 = COPY undef %32
+    S_CBRANCH_SCC1 %bb.8, implicit undef $scc
+    S_BRANCH %bb.6
+  
+  bb.6:
+    %36:sreg_32_xm0_xexec = S_BUFFER_LOAD_DWORD_IMM undef %37:sreg_128, 2708, 0 :: (dereferenceable invariant load 4)
+    %39:vgpr_32 = nnan arcp contract reassoc V_MAD_F32 0, killed %110.sub1, 0, target-flags(amdgpu-gotprel32-lo) 0, 0, 0, 0, 0, implicit $exec
+    %40:vgpr_32 = V_MAD_F32 0, %111.sub1, 0, target-flags(amdgpu-gotprel32-lo) 0, 0, 0, 0, 0, implicit $exec
+    %41:vgpr_32 = V_MUL_F32_e64 0, 0, 0, killed %40, 1, 0, implicit $exec
+    %43:vgpr_32 = V_MUL_F32_e32 0, %39, implicit $exec
+    %44:vgpr_32 = COPY killed %43
+    %44:vgpr_32 = V_MAC_F32_e32 0, killed %41, %44, implicit $exec
+    %47:vgpr_32 = V_MOV_B32_e32 2143289344, implicit $exec
+    %46:vgpr_32 = COPY killed %47
+    %46:vgpr_32 = V_MAC_F32_e32 0, killed %39, %46, implicit $exec
+    undef %115.sub0:vreg_128 = COPY %46
+    %115.sub1:vreg_128 = COPY killed %46
+    %115.sub2:vreg_128 = COPY killed %44
+    %50:sreg_64_xexec = V_CMP_NE_U32_e64 0, killed %36, implicit $exec
+    dead %118:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %137:vreg_128 = IMPLICIT_DEF
+  
+  bb.7:
+    successors: %bb.7, %bb.8
+  
+    %119:vreg_128 = COPY killed %137
+    %121:vreg_128 = COPY killed %119
+    %121.sub3:vreg_128 = COPY undef %32
+    %56:vgpr_32 = V_ADD_F32_e32 %115.sub2, %121.sub2, implicit $exec
+    %59:vgpr_32 = V_ADD_F32_e32 %115.sub1, %121.sub1, implicit $exec
+    %62:vgpr_32 = V_ADD_F32_e32 %115.sub0, killed %121.sub0, implicit $exec
+    undef %117.sub0:vreg_128 = COPY killed %62
+    %117.sub1:vreg_128 = COPY killed %59
+    %117.sub2:vreg_128 = COPY killed %56
+    %64:sreg_64 = S_AND_B64 $exec, %50, implicit-def dead $scc
+    $vcc = COPY killed %64
+    %137:vreg_128 = COPY killed %117
+    S_CBRANCH_VCCNZ %bb.7, implicit killed $vcc
+    S_BRANCH %bb.8
+  
+  bb.8:
+    dead %66:sreg_32_xm0_xexec = S_BUFFER_LOAD_DWORD_IMM undef %67:sreg_128, 2704, 0 :: (dereferenceable invariant load 4)
+    %138:vreg_128 = COPY killed %111
+  
+  bb.9:
+    %113:vreg_128 = COPY killed %138
+    S_CBRANCH_SCC1 %bb.18, implicit undef $scc
+    S_BRANCH %bb.10
+  
+  bb.10:
+    S_CBRANCH_SCC1 %bb.12, implicit undef $scc
+    S_BRANCH %bb.11
+  
+  bb.11:
+  
+  bb.12:
+    successors: %bb.13, %bb.18
+  
+    S_CBRANCH_SCC1 %bb.18, implicit undef $scc
+    S_BRANCH %bb.13
+  
+  bb.13:
+    successors: %bb.14, %bb.17
+  
+    S_CBRANCH_SCC1 %bb.17, implicit undef $scc
+    S_BRANCH %bb.14
+  
+  bb.14:
+    S_CBRANCH_SCC1 %bb.16, implicit undef $scc
+    S_BRANCH %bb.15
+  
+  bb.15:
+  
+  bb.16:
+  
+  bb.17:
+  
+  bb.18:
+    S_CBRANCH_SCC1 %bb.26, implicit undef $scc
+    S_BRANCH %bb.19
+  
+  bb.19:
+    S_CBRANCH_SCC1 %bb.26, implicit undef $scc
+    S_BRANCH %bb.20
+  
+  bb.20:
+    S_CBRANCH_SCC1 %bb.25, implicit undef $scc
+    S_BRANCH %bb.21
+  
+  bb.21:
+    successors: %bb.22, %bb.24
+  
+    S_CBRANCH_SCC1 %bb.24, implicit undef $scc
+    S_BRANCH %bb.22
+  
+  bb.22:
+    successors: %bb.23, %bb.24
+  
+    S_CBRANCH_SCC1 %bb.24, implicit undef $scc
+    S_BRANCH %bb.23
+  
+  bb.23:
+  
+  bb.24:
+  
+  bb.25:
+  
+  bb.26:
+    S_CBRANCH_SCC1 %bb.33, implicit undef $scc
+    S_BRANCH %bb.27
+  
+  bb.27:
+    S_CBRANCH_SCC1 %bb.33, implicit undef $scc
+    S_BRANCH %bb.28
+  
+  bb.28:
+    dead %77:vgpr_32 = V_MOV_B32_e32 0, implicit $exec
+    %78:vgpr_32 = nnan arcp contract reassoc V_MAD_F32 0, killed %113.sub1, 0, target-flags(amdgpu-gotprel32-lo) 0, 0, 1065353216, 0, 0, implicit $exec
+    dead %80:sreg_32_xm0 = S_MOV_B32 0
+    dead %82:vgpr_32 = V_MUL_F32_e32 killed %78, %78, implicit $exec
+    dead %126:vgpr_32 = V_MOV_B32_e32 2143289344, implicit $exec
+    dead %125:vreg_128 = IMPLICIT_DEF
+    dead %91:sreg_32_xm0 = S_MOV_B32 2143289344
+    %96:sreg_64 = S_AND_B64 $exec, 0, implicit-def dead $scc
+    %139:vreg_128 = IMPLICIT_DEF
+  
+  bb.29:
+    successors: %bb.30, %bb.31
+  
+    dead %127:vreg_128 = COPY killed %139
+    S_CBRANCH_SCC0 %bb.31, implicit undef $scc
+  
+  bb.30:
+    S_BRANCH %bb.32
+  
+  bb.31:
+    successors: %bb.32, %bb.34
+  
+    $vcc = COPY %96
+    S_CBRANCH_VCCNZ %bb.34, implicit killed $vcc
+    S_BRANCH %bb.32
+  
+  bb.32:
+    dead %130:vreg_128 = IMPLICIT_DEF
+    dead %128:vreg_128 = COPY undef %130
+    %139:vreg_128 = IMPLICIT_DEF
+    S_BRANCH %bb.29
+  
+  bb.33:
+    S_ENDPGM
+  
+  bb.34:
+    S_ENDPGM
+
+...