[RegisterCoalescer] Extend a subrange if needed when filling range gap

[kparzysz]

Summary

Register live ranges may have had gaps that after coalescing should be removed. This is done by adding a new segment to the range, and merging it with neighboring segments. When doing so, do not assume that each subrange of the register ended at the same index. If a subrange ended earlier, adding this segment could make the live range invalid. Instead, if the subrange is not live at the start of the segment, extend it first.

[arsenm]

llvm/test/CodeGen/Hexagon/regalloc-coal-extend-short-subrange.mir

18

Can you reduce this further?

[kparzysz]

llvm/test/CodeGen/Hexagon/regalloc-coal-extend-short-subrange.mir

18

Not by much if at all. This is what I got from a bugpoint testcase that was reduced pretty much as far as it would go.

[kparzysz]

llvm/test/CodeGen/Hexagon/regalloc-coal-extend-short-subrange.mir

18

I just tried removing some things (replacing function arguments with undefs), but the testcase stopped failing.

[arsenm]

llvm/test/CodeGen/Hexagon/regalloc-coal-extend-short-subrange.mir

18

Reducing these kinds of thing is difficult and time consuming, but in my experience doable. One technique I've used before is dumping the MIR from the middle of the register coalescer before the final change that hits the verifier error (and a combination of manually coalescing some of the copies). If it's so fragile the test may not end up usefully stressing this situation in the future

[kparzysz]

Created a smaller testcase.

[kparzysz]

Our local development teams are hitting this problem. Is this patch reasonable? Could someone take a look?

[kparzysz]

Ping.

[kparzysz]

Committed in https://reviews.llvm.org/rG156092bbcc0782b049da3e346cad59b92438ce72

llvm/lib/CodeGen/RegisterCoalescer.cpp

bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
   for (LiveInterval::SubRange &S : IntB.subranges()) {
     // Check for SubRange Segments of the form [1234r,1234d:0) which can be
     // removed to prevent creating bogus SubRange Segments.
     LiveInterval::iterator SS = S.FindSegmentContaining(CopyIdx);
     if (SS != S.end() && SlotIndex::isSameInstr(SS->start, SS->end)) {
       S.removeSegment(*SS, true);
       continue;
     }
+    // The subrange may have ended before FillerStart. If so, extend it.
+    if (!S.getVNInfoAt(FillerStart)) {
+      SlotIndex BBStart =
+          LIS->getMBBStartIdx(LIS->getMBBFromIndex(FillerStart));
+      S.extendInBlock(BBStart, FillerStart);
+    }
     VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
     S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
     VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot());
     if (SubBValNo != SubValSNo)
       S.MergeValueNumberInto(SubBValNo, SubValSNo);
   }
 
   LLVM_DEBUG(dbgs() << "   result = " << IntB << '\n');

llvm/test/CodeGen/Hexagon/regalloc-coal-extend-short-subrange.mir

+# RUN: llc -march=hexagon -run-pass simple-register-coalescing -verify-coalescing %s -o - | FileCheck %s
+#
+# Check that this doesn't crash.
+# CHECK: ENDLOOP
+
+---
+name:            foo
+tracksRegLiveness: true
+body: |
+  bb.0:
+    successors: %bb.1(0x40000000), %bb.2(0x40000000)
+    liveins: $r0, $r1, $r2, $v0, $v1, $v2, $v3
+
+    %0:hvxwr = COPY $v0
+    %1:intregs = COPY $r0
+    %2:predregs = C2_cmpgtui %1, 2
+    %3:intregs = COPY $r1
+    %4:intregs = COPY $r2
+    %5:hvxvr = COPY $v1
+    %6:hvxwr = V6_vcombine $v1, $v0
+    %7:hvxqr = IMPLICIT_DEF
+    J2_loop0r %bb.1, %3, implicit-def $lc0, implicit-def $sa0, implicit-def $usr
+    J2_jumpf %2, %bb.2, implicit-def $pc
+    J2_jump %bb.1, implicit-def $pc
+
+  bb.1:
+    successors: %bb.2(0x04000000), %bb.1(0x7c000000)
+
+    %8:hvxwr = COPY %0
+    %9:hvxvr = V6_vL32b_ai %4, 0
+    %10:hvxvr = V6_vL32b_ai %4, 128
+    %5:hvxvr = V6_vaddwq %7, %5, %9
+    %11:hvxqr = V6_vgtuw %10, %0.vsub_lo
+    %12:hvxvr = V6_vL32b_ai %4, 256
+    %13:hvxvr = V6_vL32b_ai %4, 384
+    %5:hvxvr = V6_vaddwq %11, %5, %13
+    %7:hvxqr = V6_vgtuw %6.vsub_hi, %13
+    %0:hvxwr = COPY %8
+    %0:hvxwr = V6_vmpyhv_acc %0, %12, %12
+    %6:hvxwr = COPY %8
+    ENDLOOP0 %bb.1, implicit-def $pc, implicit-def $lc0, implicit $sa0, implicit $lc0
+    J2_jump %bb.2, implicit-def $pc
+
+  bb.2:
+...