Fix regalloc assignment of overlapping registers

[rampitec]

Summary

SplitEditor::defFromParent() can create a register copy. If register is a tuple of other registers and not all lanes are used a copy will be done on a full tuple regardless. Later register unit for an unused lane will be considered free and another overlapping register tuple can be assigned to a different value even though first register is live at that point. That is because interference only look at liveness info, while full register copy clobbers all lanes, even unused.

This patch fixes copy to only cover used lanes.

This is how it happens in the app I was debugging:

Before Virtual Register Rewriter:

187344B         %vreg16749:sub0<def,read-undef> = V_ADD_I32_e32 %vreg12357, %vreg16754, %VCC<imp-def>, %EXEC<imp-use>; VReg_64:%vreg16749 SReg_32_XM0:%vreg12357 VGPR_32:%vreg16754
187360B         %vreg16749:sub1<def> = V_ADDC_U32_e32 %vreg16742, %vreg15898, %VCC<imp-def,dead>, %VCC<imp-use>, %EXEC<imp-use>; VReg_64:%vreg16749 VGPR_32:%vreg16742,%vreg15898
...
197648B         %vreg21888<def> = COPY %vreg21887; VReg_64:%vreg21888,%vreg21887
...
197988B         %vreg12551<def> = FLAT_LOAD_DWORDX2 %vreg16749, 0, 0, 0, %EXEC<imp-use>, %FLAT_SCR<imp-use>; mem:LD8[%arrayidx112.i18013006(addrspace=2)](tbaa=!11) VReg_64:%vr

After Virtual Register Rewriter:

187344B         %VGPR119<def> = V_ADD_I32_e32 %SGPR3, %VGPR1<kill>, %VCC<imp-def>, %EXEC<imp-use>
187360B         %VGPR120<def> = V_ADDC_U32_e32 %VGPR8<kill>, %VGPR19, %VCC<imp-def,dead>, %VCC<imp-use>, %EXEC<imp-use>
...
197648B         %VGPR118_VGPR119<def> = COPY %VGPR33_VGPR34
...
197988B         %VGPR52_VGPR53<def> = FLAT_LOAD_DWORDX2 %VGPR119_VGPR120, 0, 0, 0, %EXEC<imp-use>, %FLAT_SCR<imp-use>; mem:LD8[%arrayidx112.i18013006(addrspace=2)](tbaa=!11)

The RA debug log excerpt:

selectOrSplit VReg_64:%vreg21888 [197648r,200388r:0)  0@197648r L00000001 [197648r,200388r:0)  0@197648r w=4.824841e-04
assigning %vreg21888 to %VGPR118_VGPR119: VGPR118 [197648r,200388r:0)  0@197648r

selectOrSplit VReg_64:%vreg16749 [187344r,187360r:0)[187360r,197988r:1)  0@187344r 1@187360r L00000001 [187344r,197988r:0)  0@187344r L00000002 [187360r,197988r:0)  0@187360r
assigning %vreg16749 to %VGPR119_VGPR120: VGPR119 [187344r,197988r:0)  0@187344r VGPR120 [187360r,197988r:0)  0@187360r

[%vreg16749 -> %VGPR119_VGPR120] VReg_64
[%vreg21888 -> %VGPR118_VGPR119] VReg_64

One can see that live intervals for vreg21888 and vreg16749 do overlap, but only lane 0 of %vreg21888 is used, so VGPR119 considered free. This allows rewriter to assign pair of registers 119~120 to vreg16749. Then VGPR119 is clobbered by the %VGPR118_VGPR119<def> = COPY %VGPR33_VGPR34.

After the fix the copy will become %vreg21888:sub0<def, read-undef> = COPY %vreg21887:sub0.

I’m struggling to create a small and robust testcase so far. The original testcase is more than 12000 lines or IR and MIR does not give a reproducible result. If/when I have a smaller and better testcase I will add it.

[alex-t]

lib/CodeGen/SplitKit.cpp

535 ↗

(On Diff #85654)

What if in parent LiveInterval there are more then one subrange (i.e. several not adjacent lanes are in use) ? Let's say we copy sub0 and sub2.
LaneMask will be 1010 and the condition "TRI.getSubRegIndexLaneMask(I) == LM" will never met.
Given the assert below this, why this never expected to happen?

[alex-t]

lib/CodeGen/SplitKit.cpp

535 ↗

(On Diff #85654)

Oops... forget it ) I missed that getSubRegIndexLaneMask and setSubreg treat the parameter as a plane integer...

[rampitec]

lib/CodeGen/SplitKit.cpp

535 ↗

(On Diff #85654)

It looks like it does not happen, but in case if lane combination is not supported by target here is the assert. To me it is better to see an assert rather than silently clobber register.

[MatzeB]

lib/CodeGen/SplitKit.cpp

535 ↗

(On Diff #85654)

This can definitely happen. And we probably need a better scheme to deal with that. At the very least you should make it a report_fatal_error() so even release compilers abort instead of producing invalid code!

[MatzeB]

lib/CodeGen/SplitKit.cpp

535 ↗

(On Diff #85654)

Doesn't this also fail if a full register is copied (the parts that do not have all lanes alive could be somewhere else in the program).

[rampitec]

lib/CodeGen/SplitKit.cpp

535 ↗

(On Diff #85654)

If all lanes are used that is recorded in the liveness, then the full register is copied. That is correct. If some lanes are unused, then we are looking for a subreg to cover only used lanes, and if found that is correct again. The only problem is as discussed if such a subreg cannot be found. Too bad, I cannot insert more than copy here, neither extend liveness here to cover all lanes if we fail to find a subreg index.

I.e. from correctness point of view it seems to be fine, with exception of subreg index absence of course. I will insert fatal error here.

535 ↗

(On Diff #85654)

Agree, will insert fatal error and update the review.

[rampitec]

Replaced assert with report_fatal_error.

[rampitec]

Fixed typo in condition.

[rampitec]

The conditions to come into this situation are quite complicated. Unfortunately I lost a hope to create a non fragile and non gigantic test for it, neither I found any existing lit tests touching this condition.

[alex-t]

Given that AMDGPU backend is the only one tracking lane liveness, I'd like this change to be accepted now.
LGTM

[MatzeB]

In D29105#661368, @alex-t wrote:

Given that AMDGPU backend is the only one tracking lane liveness, I'd like this change to be accepted now.
LGTM

Hexagon is using subreg liveness as well and there is at least 1 more out-of-tree target using it.

This patch feels incomplete, it should just be a question of time until you run into the report_fatal_error() condition, but it's better than the status quo, so go ahead and push it there is not better solution.

[rampitec]

In D29105#662438, @MatzeB wrote:

In D29105#661368, @alex-t wrote:

Given that AMDGPU backend is the only one tracking lane liveness, I'd like this change to be accepted now.
LGTM

Hexagon is using subreg liveness as well and there is at least 1 more out-of-tree target using it.

This patch feels incomplete, it should just be a question of time until you run into the report_fatal_error() condition, but it's better than the status quo, so go ahead and push it there is not better solution.

I agree, it is incomplete but better than what we have now. At least we will see this fatal error. It took me 2 months to catch this error in a huge program without any diagnostics from the compiler. Next time we will see it right away.

[MatzeB]

This commit broke an internal target for us as it can choose subregister indexes which are not compatible with a given register class. Maybe we should go for the simpler LI->clearSubRanges() instead of the whole subreg aware copying for now even though that may pessimize the code.

[rampitec]

In D29105#668628, @MatzeB wrote:

This commit broke an internal target for us as it can choose subregister indexes which are not compatible with a given register class. Maybe we should go for the simpler LI->clearSubRanges() instead of the whole subreg aware copying for now even though that may pessimize the code.

It's been broken before, but now we have indication, right?
I have tried to use LI->clearSubRanges() either as an alone solution or as a backup if subreg search fails. It does not work, later on we hit assertion that a new subrange (because by clearing ranges we are creating new in fact) was not found in parent LI...

llvm/trunk/lib/CodeGen/SplitKit.cpp

VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
   }
   if (!DidRemat) {
     // Can't remat, just insert a copy from parent.
     CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
                .addReg(Edit->getReg());
     Def = LIS.getSlotIndexes()
               ->insertMachineInstrInMaps(*CopyMI, Late)
               .getRegSlot();
+    if (LI->hasSubRanges()) {
+      LaneBitmask LM = LaneBitmask::getNone();
+      for (LiveInterval::SubRange &S : LI->subranges())
+        LM |= S.LaneMask;
+
+      if (MRI.getMaxLaneMaskForVReg(LI->reg) != LM) {
+        // Find subreg for the lane mask.
+        unsigned SubIdx = 0;
+        for (unsigned I = 1, E = TRI.getNumSubRegIndices(); I < E; ++I) {
+          if (TRI.getSubRegIndexLaneMask(I) == LM) {
+            SubIdx = I;
+            break;
+          }
+        }
+        if (SubIdx == 0)
+          report_fatal_error("Cannot find subreg index to cover all alive lanes");
+        CopyMI->getOperand(0).setSubReg(SubIdx);
+        CopyMI->getOperand(1).setSubReg(SubIdx);
+        CopyMI->getOperand(0).setIsUndef(true);
+      }
+    }
     ++NumCopies;
   }
 
   // Define the value in Reg.
   return defValue(RegIdx, ParentVNI, Def, false);
 }
 
 /// Create a new virtual register and live interval.