[SplitKit] Handle early clobber + tied to def correctly

[kito-cheng]

Summary

Spliter will try to extend a live range into r slot for a use operand,
that's works on most situaion, however that not work correctly when the operand
has tied to def, and the def operand is early clobber.

Give an example to demo what's wrong:

0  %0 = ...

16 early-clobber %0 = Op %0 (tied-def 0), ...
32 ... = Op %0

Before extend:
%0 = [0r, 0d) [16e, 32d)

The point we want to extend is 0d to 16e not 16r in this case, but if
we use 16r here we will extend nothing because that already contained
in [16e, 32d).

This patch add check for detect such case and adjust the extend point.

Detailed explanation for testcase: https://reviews.llvm.org/D126047

[MatzeB]

This seems to make sense to me (though I am not super familiar with the code here). Some ideas for clearer code below:

llvm/lib/CodeGen/SplitKit.cpp

1354–1391

Hmm I found the (existing) logic here somewhat confusing... line 1361 doing getNextSlot() just seems to counteract line 1355 moving to the previous slot, but forces line 1359 to unnaturally chose the early clobber slot.

Anyway can we streamline the code somewhat like this:

1405

Use getOperandNo that's faster and avoids trouble if multiple operands use the same register.

[kito-cheng]

Changes:

• Address @MatzeB's commnet
• Rebase and fix a regression.

[kito-cheng]

llvm/lib/CodeGen/SplitKit.cpp

1354–1391

Thanks!

1405

Seems like getOperandNo only work with iterator? and that is what we don't have here :(

Anyway I change to that, but it is because I hit a regression for a testcase from X86...so I just try to traverse all input operand see which operand is tied-def and using same register as MO here...

See CodeGen/X86/statepoint-invoke-ra.mir:

dead %40:gr64 = STATEPOINT 2882400000, 0, 1, target-flags(x86-plt) @quux, $edi, 2, 0, 2, 0, 2, 6, 1, 4, %stack.0, 0, 1, 4, %stack.1, 0, 1, 4, %stack.2, 0, 1, 4, %stack.3, 0, %40:gr64, 1, 4, %stack.4, 0, 2, 1, %40:gr64(tied-def 0), 2, 0, 2, 1, 0, 0, <regmask $bh $bl $bp $bph $bpl $bx $ebp $ebx $hbp $hbx $rbp $rbx $r12 $r13 $r14 $r15 $r12b $r13b $r14b $r15b $r12bh $r13bh $r14bh $r15bh $r12d $r13d $r14d $r15d $r12w $r13w $r14w $r15w $r12wh and 3 more...>, implicit-def $rsp, implicit-def $ssp :: (volatile load store (s32) on %stack.0), (volatile load store (s32) on %stack.1), (volatile load store (s32) on %stack.2), (volatile load store (s32) on %stack.3), (volatile load store (s32) on %stack.4)

%40 appeared 3 times in this instruction, one for def, and two for use, and only one def has tied-def 0.

[arcbbb]

llvm/lib/CodeGen/SplitKit.cpp

1381

The logic here looks similar to LiveIntervalCalc::extendToUses that checks for early-clobber redefs.
Can it be simplified with OpIdx = (&MO - &MI->getOperand(0)) and MI->isRegTiedToDefOperand(OpIdx, &DefOpIdx)?

[kito-cheng]

llvm/lib/CodeGen/SplitKit.cpp

1381

MI->getOperandNo(MOItr) did almost similar thing[1] as (&MO - &MI->getOperand(0)), but having better readability.

And isRegTiedToDefOperand called findTiedOperandIdx in the function implementation[2], so I am not sure it's a simplification?

[1] https://llvm.org/doxygen/MachineInstr_8h_source.html#l00685
[2] https://llvm.org/doxygen/MachineInstr_8h_source.html#l00685

[arcbbb]

llvm/lib/CodeGen/SplitKit.cpp

1381

I think it can save the for loop and do checks for you
so the code would look like

-    } else
-      Idx = Idx.getRegSlot(true);
+    } else {
+      unsigned OpNo = MI->getOperandNo(&MO);
+      unsigned DefIdx;
+      bool isEarlyClobber = false;
+      if (MI->isRegTiedToDefOperand(OpNo, &DefIdx))
+        isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
+      Idx = Idx.getRegSlot(isEarlyClobber);
+    }

[MatzeB]

llvm/lib/CodeGen/SplitKit.cpp

1405

Well it's defined as using const_mop_iterator = const MachineOperand *;, so you should be good passing in the pointer, there's a some other places in the code that do the same.

[MatzeB]

llvm/lib/CodeGen/SplitKit.cpp

1373–1380

[kito-cheng]

Changes:

• Apply @arcbbb's and @MatzeB's suggesion.

llvm/lib/CodeGen/SplitKit.cpp

1381

Thanks, save the loop seems great!

1405

Thanks, I didn't notice it's just an alias name of MachineOperand pointer :P

[kito-cheng]

ping

[MatzeB]

LGTM, thanks

[kito-cheng]

Revert due to failed on LLVM_ENABLE_EXPENSIVE_CHECKS=On.

[kito-cheng]

D127642 will resolved the LLVM_ENABLE_EXPENSIVE_CHECKS=On issue, will reland this patch after that land.

[Allen]

llvm/lib/CodeGen/SplitKit.cpp

1369

sorry for the naive question, what's the mean of (tied-def 0)?

Does it only mean that the operand is early-clobber? or tied-def 0 implicit defined the higher bits are zero ?
I also don't known what is the mean of "0r, 0d, 16e and 32d".

[MatzeB]

llvm/lib/CodeGen/SplitKit.cpp

1369

when an operand is marked with tied-def 0 then it must get the same register assigned as operand 0 (after two-address instruction pass anyway).

16e etc. is the way slot indexes are printed (slot index 16, early clobber instruction slot). You could look in SlotIndexes.h or watch my regalloc tutorial from the developers meeting.

llvm/lib/CodeGen/SplitKit.cpp

for (MachineOperand &MO :
     if (!ExtendRanges || MO.isUndef())
       continue;
 
     // Skip instructions that don't read Reg.
     if (MO.isDef()) {
       if (!MO.getSubReg() && !MO.isEarlyClobber())
         continue;
       // We may want to extend a live range for a partial redef, or for a use
       // tied to an early clobber.
-      Idx = Idx.getPrevSlot();
-      if (!Edit->getParent().liveAt(Idx))
+      if (!Edit->getParent().liveAt(Idx.getPrevSlot()))
         continue;
-    } else
-      Idx = Idx.getRegSlot(true);
+    } else {
+      assert(MO.isUse());
+      bool IsEarlyClobber = false;
+      if (MO.isTied()) {
+        // We want to extend a live range into `e` slot rather than `r` slot if
+        // tied-def is early clobber, because the `e` slot already contained
+        // in the live range of early-clobber tied-def operand, give an example
+        // here:
+        //  0  %0 = ...
+        // 16  early-clobber %0 = Op %0 (tied-def 0), ...
+        // 32  ... = Op %0
+        // Before extend:
+        //   %0 = [0r, 0d) [16e, 32d)
+        // The point we want to extend is 0d to 16e not 16r in this case, but if
+        // we use 16r here we will extend nothing because that already contained
+        // in [16e, 32d).
+        MachineInstr::const_mop_iterator MOItr;
+        for (MOItr = MI->uses().begin(); MOItr != MI->uses().end(); ++MOItr) {
+          if (MOItr->isReg() && MOItr->isTied() &&
+              MOItr->getReg() == MO.getReg())
+            break;
+        }
+        assert(MOItr != MI->uses().end());
+        unsigned OpIdx = MI->getOperandNo(MOItr);
+        unsigned DefOpIdx = MI->findTiedOperandIdx(OpIdx);
+        const MachineOperand &DefOp = MI->getOperand(DefOpIdx);
+        if (DefOp.isEarlyClobber())
+          IsEarlyClobber = true;
+      }
+
+      Idx = Idx.getRegSlot(IsEarlyClobber);
+    }
 
-    SlotIndex Next = Idx.getNextSlot();
+    SlotIndex Next = Idx;
     if (LI.hasSubRanges()) {
       // We have to delay extending subranges until we have seen all operands
       // defining the register. This is because a <def,read-undef> operand
       // will create an "undef" point, and we cannot extend any subranges
       // until all of them have been accounted for.
       if (MO.isUse())
         ExtPoints.push_back(ExtPoint(MO, RegIdx, Next));
     } else {
       LiveIntervalCalc &LIC = getLICalc(RegIdx);
       LIC.extend(LI, Next, 0, ArrayRef<SlotIndex>());
     }
   }
 
   for (ExtPoint &EP : ExtPoints) {
     LiveInterval &LI = LIS.getInterval(Edit->get(EP.RegIdx));
     assert(LI.hasSubRanges());
 
     LiveIntervalCalc SubLIC;
     Register Reg = EP.MO.getReg(), Sub = EP.MO.getSubReg();
     LaneBitmask LM = Sub != 0 ? TRI.getSubRegIndexLaneMask(Sub)
                               : MRI.getMaxLaneMaskForVReg(Reg);
     for (LiveInterval::SubRange &S : LI.subranges()) {
       if ((S.LaneMask & LM).none())

llvm/test/CodeGen/RISCV/early-clobber-tied-def-subreg-liveness.ll

 ; CHECK-NEXT:    #APP
 ; CHECK-NEXT:    #NO_APP
 ; CHECK-NEXT:    lui a0, %hi(.L__const._Z3foov.var_44)
 ; CHECK-NEXT:    addi a0, a0, %lo(.L__const._Z3foov.var_44)
 ; CHECK-NEXT:    vsetivli zero, 2, e16, m2, ta, mu
 ; CHECK-NEXT:    addi a1, sp, 16
 ; CHECK-NEXT:    csrr a2, vlenb
 ; CHECK-NEXT:    slli a2, a2, 1
-; CHECK-NEXT:    vl2r.v v8, (a1) # Unknown-size Folded Reload
-; CHECK-NEXT:    add a1, a1, a2
 ; CHECK-NEXT:    vl2r.v v10, (a1) # Unknown-size Folded Reload
 ; CHECK-NEXT:    add a1, a1, a2
 ; CHECK-NEXT:    vl2r.v v12, (a1) # Unknown-size Folded Reload
 ; CHECK-NEXT:    add a1, a1, a2
 ; CHECK-NEXT:    vl2r.v v14, (a1) # Unknown-size Folded Reload
-; CHECK-NEXT:    vle16.v v14, (a0)
+; CHECK-NEXT:    add a1, a1, a2
+; CHECK-NEXT:    vl2r.v v16, (a1) # Unknown-size Folded Reload
+; CHECK-NEXT:    vle16.v v16, (a0)
 ; CHECK-NEXT:    vsetivli zero, 2, e16, m2, ta, mu
 ; CHECK-NEXT:    lui a0, %hi(.L__const._Z3foov.var_40)
 ; CHECK-NEXT:    addi a0, a0, %lo(.L__const._Z3foov.var_40)
 ; CHECK-NEXT:    vle16.v v8, (a0)
 ; CHECK-NEXT:    vsetivli zero, 2, e16, m2, ta, mu
 ; CHECK-NEXT:    lui a0, 1048572
 ; CHECK-NEXT:    addiw a0, a0, 928
 ; CHECK-NEXT:    vmsbc.vx v0, v8, a0
 ; CHECK-NEXT:    vsetivli zero, 2, e16, m2, tu, mu
 ; CHECK-NEXT:    csrr a0, vlenb
 ; CHECK-NEXT:    slli a0, a0, 3
 ; CHECK-NEXT:    add a0, sp, a0
 ; CHECK-NEXT:    addi a0, a0, 16
-; CHECK-NEXT:    vl1r.v v16, (a0) # Unknown-size Folded Reload
-; CHECK-NEXT:    vsext.vf2 v8, v16, v0.t
+; CHECK-NEXT:    vl1r.v v8, (a0) # Unknown-size Folded Reload
+; CHECK-NEXT:    vsext.vf2 v10, v8, v0.t
 ; CHECK-NEXT:    lui a0, %hi(var_47)
 ; CHECK-NEXT:    addi a0, a0, %lo(var_47)
-; CHECK-NEXT:    vsseg4e16.v v8, (a0)
+; CHECK-NEXT:    vsseg4e16.v v10, (a0)
 ; CHECK-NEXT:    csrr a0, vlenb
 ; CHECK-NEXT:    li a1, 10
 ; CHECK-NEXT:    mul a0, a0, a1
 ; CHECK-NEXT:    add sp, sp, a0
 ; CHECK-NEXT:    addi sp, sp, 16
 ; CHECK-NEXT:    ret
 entry:
   %0 = tail call <vscale x 8 x i16> @llvm.riscv.vle.nxv8i16.i64(<vscale x 8 x i16> undef, ptr nonnull @__const._Z3foov.var_49, i64 2)

llvm/test/CodeGen/RISCV/early-clobber-tied-def-subreg-liveness.mir

bb.0.entry:
     ; CHECK-NEXT:   rewr %bb.0  464e:0  early-clobber %28.sub_vrm2_0:vrn4m2nov0 = PseudoVSEXT_VF2_M2_MASK %25.sub_vrm2_0:vrn4m2nov0(tied-def 0), %5:vr, $v0, 2, 4, 0, implicit $vl, implicit $vtype
     ; CHECK-NEXT:   rewr %bb.0  288r:0  %28.sub_vrm2_3:vrn4m2nov0 = PseudoVLE16_V_M2 %13:gpr, 2, 4, implicit $vl, implicit $vtype
     ; CHECK-NEXT:   rewr %bb.0  208r:1  %29.sub_vrm2_2:vrn4m2nov0 = PseudoVLE16_V_M2 %10:gpr, 2, 4, implicit $vl, implicit $vtype
     ; CHECK-NEXT:   rewr %bb.0  160r:1  %29.sub_vrm2_1:vrn4m2nov0 = PseudoVLE16_V_M2 %7:gpr, 2, 4, implicit $vl, implicit $vtype
     ; CHECK-NEXT:   rewr %bb.0  64r:1 undef %29.sub_vrm2_0:vrn4m2nov0 = PseudoVLE16_V_M2 %1:gpr, 2, 4, implicit $vl, implicit $vtype
     ; CHECK-NEXT:   rewr %bb.0  464B:0  early-clobber %28.sub_vrm2_0:vrn4m2nov0 = PseudoVSEXT_VF2_M2_MASK %28.sub_vrm2_0:vrn4m2nov0(tied-def 0), %5:vr, $v0, 2, 4, 0, implicit $vl, implicit $vtype
     ; CHECK-NEXT:   rewr %bb.0  512B:0  PseudoVSSEG4E16_V_M2 %28:vrn4m2nov0, %27:gpr, 2, 4, implicit $vl, implicit $vtype
     ; CHECK-NEXT:   rewr %bb.0  216B:1  undef %28.sub_vrm1_0_sub_vrm1_1_sub_vrm1_2_sub_vrm1_3_sub_vrm1_4_sub_vrm1_5:vrn4m2nov0 = COPY %29.sub_vrm1_0_sub_vrm1_1_sub_vrm1_2_sub_vrm1_3_sub_vrm1_4_sub_vrm1_5:vrn4m2nov0
-    ; CHECK-NEXT: queuing new interval: %28 [216r,288r:0)[288r,464e:1)[464e,512r:2) 0@216r 1@288r 2@464e  L000000000000000C [216r,216d:0)[464e,512r:1) 0@216r 1@464e  L0000000000000300 [288r,512r:0) 0@288r  L00000000000000C0 [216r,512r:0) 0@216r  L0000000000000030 [216r,512r:0) 0@216r  weight:8.706897e-03
+    ; CHECK-NEXT: queuing new interval: %28 [216r,288r:0)[288r,464e:1)[464e,512r:2) 0@216r 1@288r 2@464e L000000000000000C [216r,464e:0)[464e,512r:1) 0@216r 1@464e L0000000000000300 [288r,512r:0) 0@288r L00000000000000C0 [216r,512r:0) 0@216r L0000000000000030 [216r,512r:0) 0@216r weight:8.706897e-03
     %26:gpr = LUI target-flags(riscv-hi) @var_47
     %27:gpr = ADDI %26, target-flags(riscv-lo) @var_47
     PseudoVSSEG4E16_V_M2 %25, %27, 2, 4 /* e16 */, implicit $vl, implicit $vtype
     PseudoRET
 
 ...