[CodeGen] Prevent overlapping subregs in getCoveringSubRegIndexes

[Pierre-vh]

Summary

If getCoveringSubRegIndexes returns a set of subregister indexes where some subregisters overlap others, it can create unsatisfiable copy bundles that eventually cause VirtRegRewriter to error out due to "cycles in copy bundle".

We can simply prevent this by making the algorithm skip over subregisters indexes that would cause an overlap with already-covered lanes.

Note that in the case of AMDGPU, this problem is caused by the lack of subregisters indexes for 13/14/15-register tuples. We have everything up until 12, then we have 16 and 32 but nothing between 12 and 16.
This means that the best candidate to do the least amount of copies when splitting a 29-register tuple was to copy (e.g.) 0-15 and 14-29, causing an overlap.
With this change, getCoveringSubRegIndexes will now prefer using something like 0-15, 16-28 and 1

[Pierre-vh]

Testing for this is a bit tricky, fortunately it looks like it's already covered by a test.
If another form of testing is needed, perhaps we could do a unit test? I feel like it'd be a lot more straightforward to just query TRI in a unit test and check all the corner cases there.

[arsenm]

llvm/lib/CodeGen/TargetRegisterInfo.cpp

580

s/as much/as many/

llvm/test/CodeGen/AMDGPU/extend-phi-subrange-not-in-parent.mir

61

Needs a new test for the cases that were failing

[foad]

llvm/test/CodeGen/AMDGPU/extend-phi-subrange-not-in-parent.mir

29

Did anything actually change here? If not can you first commit a patch to regenerate the checks for this file, and then rebase this patch?

[arsenm]

llvm/lib/CodeGen/TargetRegisterInfo.cpp

576

this isn't memory

[arsenm]

In D141576#4046355, @Pierre-vh wrote:

Testing for this is a bit tricky, fortunately it looks like it's already covered by a test.
If another form of testing is needed, perhaps we could do a unit test? I feel like it'd be a lot more straightforward to just query TRI in a unit test and check all the corner cases there.

You already have the reduced mir test?

[Pierre-vh]

In D141576#4051805, @arsenm wrote:

In D141576#4046355, @Pierre-vh wrote:

Testing for this is a bit tricky, fortunately it looks like it's already covered by a test.
If another form of testing is needed, perhaps we could do a unit test? I feel like it'd be a lot more straightforward to just query TRI in a unit test and check all the corner cases there.

You already have the reduced mir test?

Only for the virtregrewriter pass (so with already split liveranges). Plus, the testcase I have seems highly sensitive to register allocation changes, and as liverange splitting happens in the register allocator it's not a good test case as it may start passing not because of this change but because of other unrelated changes that affect regalloc (for instance it just passes now on trunk without any changes)
Any test case could also be made irrelevant if we add the missing 13-15 tuples subregister indexes

Should I try to come up with an artificial case like the ones in splitkit.mir? What should the structure be to tickle the register allocator just enough to make liverange splitting copy sub0-sub29 of a sreg_1024?

Maybe I can do something based on extend-phi-subrange-not-in-parent, just cleaned up and with a comment saying exactly what it needs to test.

llvm/test/CodeGen/AMDGPU/extend-phi-subrange-not-in-parent.mir

29

That indeed didn't change in this patch, I regenerated the test
https://github.com/llvm/llvm-project/commit/9bdfd7c8db2066e5b50b9599248660bdf8eda7f0

[Pierre-vh]

Rebase, address comments

[arsenm]

In D141576#4055520, @Pierre-vh wrote:

In D141576#4051805, @arsenm wrote:

In D141576#4046355, @Pierre-vh wrote:

Testing for this is a bit tricky, fortunately it looks like it's already covered by a test.
If another form of testing is needed, perhaps we could do a unit test? I feel like it'd be a lot more straightforward to just query TRI in a unit test and check all the corner cases there.

You already have the reduced mir test?

Only for the virtregrewriter pass (so with already split liveranges). Plus, the testcase I have seems highly sensitive to register allocation changes, and as liverange splitting happens in the register allocator it's not a good test case as it may start passing not because of this change but because of other unrelated changes that affect regalloc (for instance it just passes now on trunk without any changes)

This is a general issue, still having something is better than nothing

Any test case could also be made irrelevant if we add the missing 13-15 tuples subregister indexes

Could also try forcing it on a different target

Should I try to come up with an artificial case like the ones in splitkit.mir? What should the structure be to tickle the register allocator just enough to make liverange splitting copy sub0-sub29 of a sreg_1024?

That would also be good, it can be tricky and time consuming but it’s usually possible. It’s a bit of an art to craft these tests

Maybe I can do something based on extend-phi-subrange-not-in-parent, just cleaned up and with a comment saying exactly what it needs to test.

[Pierre-vh]

Rebase on D141903

llvm/lib/CodeGen/TargetRegisterInfo.cpp

while (LanesLeft.any()) {
     for (unsigned Idx : PossibleIndexes) {
       LaneBitmask SubRegMask = getSubRegIndexLaneMask(Idx);
       // Early exit if we found a perfect match.
       if (SubRegMask == LanesLeft) {
         BestIdx = Idx;
         break;
       }
 
-      // Try to cover as much of the remaining lanes as possible but
-      // as few of the already covered lanes as possible.
-      int Cover = (SubRegMask & LanesLeft).getNumLanes() -
-                  (SubRegMask & ~LanesLeft).getNumLanes();
+      // Do not cover already-covered lanes to avoid creating cycles
+      // in copy bundles (= bundle contains copies that write to the
+      // registers).
+      if ((SubRegMask & ~LanesLeft).any())
+        continue;
+
+      // Try to cover as many of the remaining lanes as possible.
+      const int Cover = (SubRegMask & LanesLeft).getNumLanes();
       if (Cover > BestCover) {
         BestCover = Cover;
         BestIdx = Idx;
       }
     }
 
     if (BestIdx == 0)
       return false; // Impossible to handle

llvm/test/CodeGen/AMDGPU/extend-phi-subrange-not-in-parent.mir

body:             |
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[DEF:%[0-9]+]]:vgpr_32 = IMPLICIT_DEF
   ; CHECK-NEXT:   [[DEF1:%[0-9]+]]:vreg_1024_align2 = IMPLICIT_DEF
   ; CHECK-NEXT:   [[COPY:%[0-9]+]]:av_1024_align2 = COPY [[DEF1]]
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.1:
   ; CHECK-NEXT:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   dead [[DEF2:%[0-9]+]]:vreg_64 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_NOP 0, implicit [[DEF1]]
   ; CHECK-NEXT:   S_NOP 0, implicit [[DEF1]]
   ; CHECK-NEXT:   [[DEF3:%[0-9]+]]:vreg_1024_align2 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_CBRANCH_VCCNZ %bb.1, implicit undef $vcc
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.2:
   ; CHECK-NEXT:   successors: %bb.3(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   undef %6.sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16:av_1024_align2 = COPY [[COPY]].sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16 {
-  ; CHECK-NEXT:     internal %6.sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30_sub31:av_1024_align2 = COPY [[COPY]].sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30_sub31
+  ; CHECK-NEXT:     internal %6.sub17_lo16_sub17_hi16_sub18_lo16_sub18_hi16_sub19_lo16_sub19_hi16_sub20_lo16_sub20_hi16_sub21_lo16_sub21_hi16_sub22_lo16_sub22_hi16_sub23_lo16_sub23_hi16_sub24_lo16_sub24_hi16_sub25_lo16_sub25_hi16_sub26_lo16_sub26_hi16_sub27_lo16_sub27_hi16_sub28_lo16_sub28_hi16:av_1024_align2 = COPY [[COPY]].sub17_lo16_sub17_hi16_sub18_lo16_sub18_hi16_sub19_lo16_sub19_hi16_sub20_lo16_sub20_hi16_sub21_lo16_sub21_hi16_sub22_lo16_sub22_hi16_sub23_lo16_sub23_hi16_sub24_lo16_sub24_hi16_sub25_lo16_sub25_hi16_sub26_lo16_sub26_hi16_sub27_lo16_sub27_hi16_sub28_lo16_sub28_hi16
+  ; CHECK-NEXT:     internal %6.sub29_sub30_sub31:av_1024_align2 = COPY [[COPY]].sub29_sub30_sub31
   ; CHECK-NEXT:   }
   ; CHECK-NEXT:   %6.sub0:av_1024_align2 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_NOP 0, implicit %6.sub0
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.3:
   ; CHECK-NEXT:   successors: %bb.4(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   S_NOP 0, implicit %6
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.4:
   ; CHECK-NEXT:   successors: %bb.3(0x40000000), %bb.5(0x40000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   [[DEF3:%[0-9]+]]:av_1024_align2 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_CBRANCH_VCCNZ %bb.3, implicit undef $vcc
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.5:
   ; CHECK-NEXT:   undef %4.sub0:vreg_1024_align2 = COPY [[DEF]]
   ; CHECK-NEXT:   S_NOP 0, implicit %4
   bb.0:
     %0:vgpr_32 = IMPLICIT_DEF
     %1:vreg_1024_align2 = IMPLICIT_DEF
     %2:vreg_1024_align2 = COPY %1
 
   bb.1:
     %5:vreg_64 = IMPLICIT_DEF
     S_NOP 0, implicit %1
     S_NOP 0, implicit %1
     %1:vreg_1024_align2 = IMPLICIT_DEF
     S_CBRANCH_VCCNZ %bb.1, implicit undef $vcc

llvm/test/CodeGen/AMDGPU/split-liverange-overlapping-copies.mir

body:             |
   ; CHECK-NEXT:   S_NOP 0, implicit [[DEF1]]
   ; CHECK-NEXT:   [[DEF3:%[0-9]+]]:vreg_1024_align2 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_CBRANCH_VCCNZ %bb.1, implicit undef $vcc
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.2:
   ; CHECK-NEXT:   successors: %bb.3(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   undef %6.sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16:av_1024_align2 = COPY [[COPY]].sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16 {
-  ; CHECK-NEXT:     internal %6.sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30_sub31:av_1024_align2 = COPY [[COPY]].sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30_sub31
+  ; CHECK-NEXT:     internal %6.sub17_lo16_sub17_hi16_sub18_lo16_sub18_hi16_sub19_lo16_sub19_hi16_sub20_lo16_sub20_hi16_sub21_lo16_sub21_hi16_sub22_lo16_sub22_hi16_sub23_lo16_sub23_hi16_sub24_lo16_sub24_hi16_sub25_lo16_sub25_hi16_sub26_lo16_sub26_hi16_sub27_lo16_sub27_hi16_sub28_lo16_sub28_hi16:av_1024_align2 = COPY [[COPY]].sub17_lo16_sub17_hi16_sub18_lo16_sub18_hi16_sub19_lo16_sub19_hi16_sub20_lo16_sub20_hi16_sub21_lo16_sub21_hi16_sub22_lo16_sub22_hi16_sub23_lo16_sub23_hi16_sub24_lo16_sub24_hi16_sub25_lo16_sub25_hi16_sub26_lo16_sub26_hi16_sub27_lo16_sub27_hi16_sub28_lo16_sub28_hi16
+  ; CHECK-NEXT:     internal %6.sub29_sub30_sub31:av_1024_align2 = COPY [[COPY]].sub29_sub30_sub31
   ; CHECK-NEXT:   }
   ; CHECK-NEXT:   %6.sub0:av_1024_align2 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_NOP 0, implicit %6.sub0
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.3:
   ; CHECK-NEXT:   successors: %bb.4(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   S_NOP 0, implicit %6
body:             |
   ; CHECK-NEXT:   S_NOP 0, implicit [[DEF1]]
   ; CHECK-NEXT:   [[DEF3:%[0-9]+]]:vreg_1024 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_CBRANCH_VCCNZ %bb.1, implicit undef $vcc
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.2:
   ; CHECK-NEXT:   successors: %bb.3(0x80000000)
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT:   undef %6.sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16:av_1024 = COPY [[COPY]].sub1_sub2_sub3_sub4_sub5_sub6_sub7_sub8_sub9_sub10_sub11_sub12_sub13_sub14_sub15_sub16 {
-  ; CHECK-NEXT:     internal %6.sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30:av_1024 = COPY [[COPY]].sub15_sub16_sub17_sub18_sub19_sub20_sub21_sub22_sub23_sub24_sub25_sub26_sub27_sub28_sub29_sub30
+  ; CHECK-NEXT:     internal %6.sub17_lo16_sub17_hi16_sub18_lo16_sub18_hi16_sub19_lo16_sub19_hi16_sub20_lo16_sub20_hi16_sub21_lo16_sub21_hi16_sub22_lo16_sub22_hi16_sub23_lo16_sub23_hi16_sub24_lo16_sub24_hi16_sub25_lo16_sub25_hi16_sub26_lo16_sub26_hi16_sub27_lo16_sub27_hi16_sub28_lo16_sub28_hi16:av_1024 = COPY [[COPY]].sub17_lo16_sub17_hi16_sub18_lo16_sub18_hi16_sub19_lo16_sub19_hi16_sub20_lo16_sub20_hi16_sub21_lo16_sub21_hi16_sub22_lo16_sub22_hi16_sub23_lo16_sub23_hi16_sub24_lo16_sub24_hi16_sub25_lo16_sub25_hi16_sub26_lo16_sub26_hi16_sub27_lo16_sub27_hi16_sub28_lo16_sub28_hi16
+  ; CHECK-NEXT:     internal %6.sub29_sub30:av_1024 = COPY [[COPY]].sub29_sub30
   ; CHECK-NEXT:   }
   ; CHECK-NEXT:   %6.sub0:av_1024 = IMPLICIT_DEF
   ; CHECK-NEXT:   %6.sub31:av_1024 = IMPLICIT_DEF
   ; CHECK-NEXT:   S_NOP 0, implicit %6.sub0, implicit %6.sub31
   ; CHECK-NEXT: {{  $}}
   ; CHECK-NEXT: bb.3:
   ; CHECK-NEXT:   successors: %bb.4(0x80000000)
   ; CHECK-NEXT: {{  $}}