[RegisterCoalescer] passs Undefs to extendToIndices()

[ruiling]

Summary

When extending the subranges, the reaching-def may be an undefs. When
extending such kind of subrange, it will try to search for the reaching
def first. If the reaching def is an undef and we did not provide 'Undefs',
The findReachingDefs() will fail with message:
"Use of $noreg does not have a corresponding definition on every path:
LLVM ERROR: Use not jointly dominated by defs."
So we computeSubRangeUndefs() and pass the result to extendToIndices().

[arsenm]

llvm/test/CodeGen/AMDGPU/coalescer-removepartial-extend-undef-subrange.mir

21

$noreg doesn't have liveness?

30

Can you reduce this any further? -run-pass=none will also compact the register numbers

[arsenm]

Typo passs in commit message

[ruiling]

llvm/test/CodeGen/AMDGPU/coalescer-removepartial-extend-undef-subrange.mir

21

I am not sure what you are really asking here. I know the assert message is a little bit misleading. The reason it output $noreg is we are passing 0 to argument 'PhyReg' of LiveRangeCalc::extend() in LiveIntervals::extendToIndices(). When assert happens, we are trying to extend a subrange of register %90. The offending subrange has a def point in one of bb.4 predecessor chain, so it has liveness in this path. but in another predecessor chain 4->27->1->0, it only has one undef point in bb.0.

30

I just tried to remove each one of the most blocks containing instructions in MIR, I failed to trigger the crash after removing them. If you have any good idea to simplify further, I can try it. Some more notes: The test case is already a much simplified version than original failure IR with 100+ basic blocks. I have tried removing each basic block in IR before and it would cause problem disappear. The problem is hard to trigger, it also depends on the order of coalescing work. For example, if I reorder the blocks, the problem may disappear because the coalescing of registers will be different then.

[ruiling]

address some review comments from Matt

[arsenm]

llvm/test/CodeGen/AMDGPU/coalescer-removepartial-extend-undef-subrange.mir

30

I've reduced coalescer cases by dumping the MIR at intermediate points during the coalescer. Presumably not every step is relevant to get to the problem

[ruiling]

further reduce .mir with intermediate result from coalescer.

[ruiling]

further reduce .mir to trigger the issue. @arsenm Could you take a look?

[ruiling]

further simplify .mir test

[arsenm]

LGTM with test converted to generated checks

llvm/test/CodeGen/AMDGPU/coalescer-removepartial-extend-undef-subrange.mir

2

Add a -mcpu=gfx900 or some other target

4–6

These checks are really weak, I would rather just generate these

llvm/lib/CodeGen/RegisterCoalescer.cpp

for (LiveInterval::SubRange &SR : IntB.subranges()) {
     for (unsigned I = 0; I != EndPoints.size(); ) {
       if (SlotIndex::isSameInstr(EndPoints[I], CopyIdx)) {
         EndPoints[I] = EndPoints.back();
         EndPoints.pop_back();
         continue;
       }
       ++I;
     }
-    LIS->extendToIndices(SR, EndPoints);
+    SmallVector<SlotIndex, 8> Undefs;
+    IntB.computeSubRangeUndefs(Undefs, SR.LaneMask, *MRI,
+                               *LIS->getSlotIndexes());
+    LIS->extendToIndices(SR, EndPoints, Undefs);
   }
   // If any dead defs were extended, truncate them.
   shrinkToUses(&IntB);
 
   // Finally, update the live-range of IntA.
   shrinkToUses(&IntA);
   return true;
 }

llvm/test/CodeGen/AMDGPU/coalescer-removepartial-extend-undef-subrange.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -march=amdgcn -mcpu=gfx900 -run-pass simple-register-coalescing -verify-machineinstrs -o - %s | FileCheck %s
+#
+# The failure occurs when the coalescer tries to removePartialRedundency() on the
+# "%2:vreg_64 = COPY %3" in bb.1. The coalescer tries to prune and extend each
+# subrange of %2, the subrange for %2.sub1 has a def location (in bb.2) in the
+# predecessor path 2->3->1. But for another predecessor path 0->4->1,
+# the subrange has only one undef location in bb.0. If we don't compute Undef set,
+# it will fail to find the reaching def for %2.sub1 in predecessor bb.4 and bb.0
+# and crash with error message:
+# "Use of $noreg does not have a corresponding definition on every path
+#  LLVM ERROR: Use not jointly dominated by defs"
+
+---
+name:            _amdgpu_ps_main
+alignment:       1
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: _amdgpu_ps_main
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.4(0x40000000)
+  ; CHECK:   liveins: $sgpr2, $sgpr3, $vgpr3
+  ; CHECK:   [[COPY:%[0-9]+]]:sgpr_32 = COPY $sgpr2
+  ; CHECK:   undef %1.sub0:vreg_64 = COPY [[COPY]]
+  ; CHECK:   undef %2.sub0:vreg_64 = COPY [[COPY]]
+  ; CHECK:   S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
+  ; CHECK:   S_BRANCH %bb.4
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   S_NOP 0, implicit %2.sub0
+  ; CHECK: bb.2:
+  ; CHECK:   successors: %bb.3(0x04000000), %bb.2(0x7c000000)
+  ; CHECK:   [[COPY1:%[0-9]+]]:vreg_64 = COPY %2
+  ; CHECK:   %1.sub0:vreg_64 = COPY [[COPY1]].sub0
+  ; CHECK:   %2:vreg_64 = COPY %1
+  ; CHECK:   S_CBRANCH_EXECNZ %bb.2, implicit undef $exec
+  ; CHECK:   S_BRANCH %bb.3
+  ; CHECK: bb.3:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   %2:vreg_64 = COPY [[COPY1]]
+  ; CHECK:   S_BRANCH %bb.1
+  ; CHECK: bb.4:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   S_BRANCH %bb.1
+  bb.0:
+    liveins: $sgpr2, $sgpr3, $vgpr3
+
+    %0:sgpr_32 = COPY $sgpr2
+    undef %1.sub0:vreg_64 = COPY %0
+    undef %2.sub0:vreg_64 = COPY %0
+    S_CBRANCH_VCCNZ %bb.2, implicit undef $vcc
+    S_BRANCH %bb.4
+
+  bb.1:
+    %2:vreg_64 = COPY %3
+    S_NOP 0, implicit %2.sub0
+
+  bb.2:
+    successors: %bb.3(0x04000000), %bb.2(0x7c000000)
+
+    %3:vreg_64 = COPY %2
+    %1.sub0:vreg_64 = COPY %3.sub0
+    %2:vreg_64 = COPY %1
+    S_CBRANCH_EXECNZ %bb.2, implicit undef $exec
+    S_BRANCH %bb.3
+
+  bb.3:
+    S_BRANCH %bb.1
+
+  bb.4:
+    %3:vreg_64 = COPY %2
+    S_BRANCH %bb.1
+
+...