[ARM] Don't expand sdiv when optimising for minsize

[SjoerdMeijer]

Summary

Don't expand a SDIV with an immediate that is a power of 2 if we optimise for minimum code size. For example:

    
sdiv %1, i32 4

this gets cleverly expanded to a sequence of 3 instructions: ASR, ADD (with a LSR in the addressing mode) and another ASR. But this is suboptimial for minimum code size, so instead we just generate a MOV and a SDIV.

[efriedma]

But this is suboptimial for minimum code size, so instead we just generate a MOV and a SDIV.

This saves two bytes, if I'm following correctly?

test/CodeGen/ARM/sdiv-opt-size.ll

3

What happens for targets that don't have an sdiv instruction? (For example, thumbv6m.)

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3237

Instead of isVector() should this be based on operation legality? Promotion/expansion could be just as (or more?) expensive as the pow2 expansion. i64 on 32-bits targets for instance.

[efriedma]

On thumbv8, if you're dividing by a power of two greater than 128, I think you save zero bytes (it's eight bytes either way); is that right?

This affects non-ARM targets; do you know what the effect is on those targets?

[SjoerdMeijer]

Thanks for commenting!
Yes, this should save 2 bytes.
I will check tomorrow:

• about the SDIV legality, and where exactly the SDIV is expanded when it is not supported in HW. I see that sdiv is expanded very early if it is not available, immediately after the initial SDAG, and this code in visitSDIVLike does not get triggered. But again, will double check where exactly the magic happens. I've noticed that at least some tests are in place for other targets: the minsize check is not enough, the !VT.isVector() is required for some X86 and AArch64 tests, and without it the (knock on) effect is that the vector operations get scalarized and these tests fail, but I don't think this is related the legality of SDIV.
• I missed this: "On Thumbv8, if you're dividing by a power of two greater than 128, I think you save zero byte", so will address that.
• what exactly the benefit is on some other targets.

[samparker]

test/CodeGen/ARM/sdiv-opt-size.ll

1

specifying the m33 is unnecessary and it's worth adding v8m.base too.

[SjoerdMeijer]

A little bit of progress:

What happens for targets that don't have an sdiv instruction? (For example, thumbv6m.)

The Legalizer takes care of it and turns it into a call to __aeabi_idiv. But it doesn't look beneficial though:

$ cat t.c
int foo(int f) {
  return f / 4;
}

before:

0x00000000:    17c1        ASRS     r1,r0,#31
0x00000002:    0f89        LSRS     r1,r1,#30
0x00000004:    1840       ADDS     r0,r0,r1
0x00000006:    1080       ASRS     r0,r0,#2
0x00000008:    4770       BX       lr

and after:

0x00000000:    b580        PUSH     {r7,lr}
0x00000002:    2104        MOVS     r1,#4
0x00000004:    f7fffffe    BL       __aeabi_idiv
0x00000008:    bd80         POP      {r7,pc}

This isn't great in many ways: same size, it's slower, and we still need to pull in code for __aeabi_idiv (if it isn't already linked in). Easiest and best thing to do here is to expand SDIV as before. I will see if I can query if SDIV is legal, and add that as a check here.

For X86, this code path doesn't seem to be triggered at all and it is already generating an idiv:

0:	89 f8                	mov    %edi,%eax
2:	6a 05                	pushq  $0x5
4:	59                   	pop    %rcx
5:	99                   	cltd   
6:	f7 f9                	idiv   %ecx
8:	c3                   	retq

From a quick look for X86, it leaves the SDIV intact, because it disappears in function BuildSDIVPow2 on line 3233 just before my addition there, queries TLI.BuildSDIVPow2, which returns this SDIV node.

[SjoerdMeijer]

While looking what X86 was doing (and why it was doing the right thing), I noticed that I should just implement TargetLowering::BuildSDIVPow2. So that's what I am doing now, and thus it's no longer a DAGCombine change but just an ARM one.
Different tests and targets have been added, and a check for larger constants.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

7806 ↗

(On Diff #174747)

ARM mode? It looks like the rest of the function doesn't handle it correctly, and you don't have any tests.

test/CodeGen/ARM/sdiv-opt-size.ll

12

Could you also check that we don't generate any libcalls for v6m?

19

This sxth is redundant? Probably need to implement ComputeNumSignBits for SDIV, or something like that.

[SjoerdMeijer]

lib/Target/ARM/ARMISelLowering.cpp

7806 ↗

(On Diff #174747)

Oops, thanks for catching this! I completely focused on Thumb, and forgot about ARM. But yes, will add ARM too.

test/CodeGen/ARM/sdiv-opt-size.ll

12

Yep, will do.

19

Interesting! Hadn't looked at that, but yes, that's redundant. Will address that in a follow-up patch.

[RKSimon]

lib/Target/ARM/ARMISelLowering.cpp

7812 ↗

(On Diff #174747)

Why do you need this? BuildSDIVPow2 is only called with constant (pow2) divisors, also it'll fail for constant vectors.

[SjoerdMeijer]

Thanks for reviewing!

• removed the unnecessary assert
• added support for ARM mode, and tests.

[efriedma]

test/CodeGen/ARM/sdiv-pow2-arm-size.ll

14 ↗

(On Diff #174930)

Not sure the libcall is the right choice... yes, in your tiny testcase, it saves one instruction, but a libcall is going to force spilling for most realistic functions.

[SjoerdMeijer]

test/CodeGen/ARM/sdiv-pow2-arm-size.ll

14 ↗

(On Diff #174930)

Ok, yes, fair enough. I will change this and also in ARM mode won't generate the sdiv if hwdiv is unsupported.

[SjoerdMeijer]

• Don't create div libcalls in ARM mode,
• Bail for SREM instructions. This wasn't checked, and resulted in a crash. Thanks to @dmgreen for pointing this out. Will follow up on this.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

7820 ↗

(On Diff #175129)

Please early return here instead of changing the value of SDIV.

[SjoerdMeijer]

Bail earlier if minsize or hwdiv is not enabled.

[SjoerdMeijer]

friendly ping

[efriedma]

LGTM

[SjoerdMeijer]

Thanks!

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitSDIVLike(SDValue N0, SDValue N1, SDNode *N) {
   // FIXME: We check for the exact bit here because the generic lowering gives
   // better results in that case. The target-specific lowering should learn how
   // to handle exact sdivs efficiently.
   if (!N->getFlags().hasExact() && ISD::matchUnaryPredicate(N1, IsPowerOfTwo)) {
     // Target-specific implementation of sdiv x, pow2.
     if (SDValue Res = BuildSDIVPow2(N))
       return Res;
 
+    if (DAG.getMachineFunction().getFunction().optForMinSize() &&
+        !VT.isVector())
+      return SDValue();
+
     // Create constants that are functions of the shift amount value.
     EVT ShiftAmtTy = getShiftAmountTy(N0.getValueType());
     SDValue Bits = DAG.getConstant(BitWidth, DL, ShiftAmtTy);
     SDValue C1 = DAG.getNode(ISD::CTTZ, DL, VT, N1);
     C1 = DAG.getZExtOrTrunc(C1, DL, ShiftAmtTy);
     SDValue Inexact = DAG.getNode(ISD::SUB, DL, ShiftAmtTy, Bits, C1);
     if (!isConstantOrConstantVector(Inexact))
       return SDValue();

test/CodeGen/ARM/sdiv-opt-size.ll

+; RUN: llc -mtriple=thumbv8m.main -mcpu=cortex-m33 %s -o - | FileCheck %s
+; RUN: llc -mtriple=thumbv7em %s -o - | FileCheck %s
+; RUN: llc -mtriple=thumbv8 %s -o - | FileCheck %s
+
+; Test sdiv i16
+
+define dso_local signext i16 @f0(i16 signext %F) local_unnamed_addr #0 {
+; CHECK-LABEL: f0
+; CHECK:       movs    r1, #2
+; CHECK-NEXT:  sdiv    r0, r0, r1
+; CHECK-NEXT:  sxth    r0, r0
+; CHECK-NEXT:  bx      lr
+
+entry:
+  %0 = sdiv i16 %F, 2
+  ret i16 %0
+}
+
+; Same as above, but now with i32
+
+define dso_local i32 @f1(i32 %F) local_unnamed_addr #0 {
+; CHECK-LABEL: f1
+; CHECK:       movs    r1, #4
+; CHECK-NEXT:  sdiv    r0, r0, r1
+; CHECK-NEXT:  bx      lr
+
+entry:
+  %div = sdiv i32 %F, 4
+  ret i32 %div
+}
+
+; The immediate is not a power of 2, so we expect a sdiv.
+
+define dso_local i32 @f2(i32 %F) local_unnamed_addr #0 {
+; CHECK-LABEL: f2
+; CHECK:       movs    r1, #5
+; CHECK-NEXT:  sdiv    r0, r0, r1
+; CHECK-NEXT:  bx      lr
+
+entry:
+  %div = sdiv i32 %F, 5
+  ret i32 %div
+}
+
+; Try a larger power of 2 immediate
+
+define dso_local i32 @f3(i32 %F) local_unnamed_addr #0 {
+; CHECK-LABEL:  f3
+; CHECK:        mov.w  r1, #8192
+; CHECK-NEXT:   sdiv r0, r0, r1
+; CHECK-NEXT:   bx lr
+entry:
+  %div = sdiv i32 %F, 8192
+  ret i32 %div
+}
+
+attributes #0 = { minsize norecurse nounwind optsize readnone }
+
+
+; These functions dont have the minsize attribute, so should
+; not lower the sdiv to sdiv, but to the faster instruction
+; sequence.
+
+define dso_local signext i16 @f4(i16 signext %F) {
+; CHECK-LABEL: f4
+; CHECK:  uxth    r1, r0
+; CHECK-NEXT:   add.w   r0, r0, r1, lsr #15
+; CHECK-NEXT:   sxth    r0, r0
+; CHECK-NEXT:   asrs    r0, r0, #1
+; CHECK-NEXT:   bx      lr
+entry:
+  %0 = sdiv i16 %F, 2
+  ret i16 %0
+}
+
+define dso_local i32 @f5(i32 %F) {
+; CHECK-LABEL: f5
+; CHECK:        asrs  r1, r0, #31
+; CHECK-NEXT:   add.w   r0, r0, r1, lsr #30
+; CHECK-NEXT:   asrs    r0, r0, #2
+; CHECK-NEXT:   bx      lr
+entry:
+  %div = sdiv i32 %F, 4
+  ret i32 %div
+}