[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 ↗

(On Diff #174102)

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

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3237 ↗

(On Diff #174102)

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 ↗

(On Diff #174102)

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

11 ↗

(On Diff #174747)

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

18 ↗

(On Diff #174747)

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

11 ↗

(On Diff #174747)

Yep, will do.

18 ↗

(On Diff #174747)

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!

llvm/trunk/lib/Target/ARM/ARMISelLowering.h

private:
     SDValue LowerFP_ROUND(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerFP_EXTEND(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerFP_TO_INT(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerINT_TO_FP(SDValue Op, SelectionDAG &DAG) const;
 
     unsigned getRegisterByName(const char* RegName, EVT VT,
                                SelectionDAG &DAG) const override;
 
+    SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor, SelectionDAG &DAG,
+                          SmallVectorImpl<SDNode *> &Created) const override;
+
     /// isFMAFasterThanFMulAndFAdd - Return true if an FMA operation is faster
     /// than a pair of fmul and fadd instructions. fmuladd intrinsics will be
     /// expanded to FMAs when this method returns true, otherwise fmuladd is
     /// expanded to fmul + fadd.
     ///
     /// ARM supports both fused and unfused multiply-add operations; we already
     /// lower a pair of fmul and fadd to the latter so it's not clear that there
     /// would be a gain or that the gain would be worthwhile enough to risk

llvm/trunk/lib/Target/ARM/ARMISelLowering.cpp

SDValue ARMTargetLowering::LowerWindowsDIVLibCall(SDValue Op, SelectionDAG &DAG,
   CLI.setDebugLoc(dl)
     .setChain(Chain)
     .setCallee(CallingConv::ARM_AAPCS_VFP, VT.getTypeForEVT(*DAG.getContext()),
                ES, std::move(Args));
 
   return LowerCallTo(CLI).first;
 }
 
+// This is a code size optimisation: return the original SDIV node to
+// DAGCombiner when we don't want to expand SDIV into a sequence of
+// instructions, and an empty node otherwise which will cause the
+// SDIV to be expanded in DAGCombine.
+SDValue
+ARMTargetLowering::BuildSDIVPow2(SDNode *N, const APInt &Divisor,
+                                 SelectionDAG &DAG,
+                                 SmallVectorImpl<SDNode *> &Created) const {
+  // TODO: Support SREM
+  if (N->getOpcode() != ISD::SDIV)
+    return SDValue();
+
+  const auto &ST = static_cast<const ARMSubtarget&>(DAG.getSubtarget());
+  const auto &MF = DAG.getMachineFunction();
+  const bool MinSize = MF.getFunction().optForMinSize();
+  const bool HasDivide = ST.isThumb() ? ST.hasDivideInThumbMode()
+                                      : ST.hasDivideInARMMode();
+
+  // Don't touch vector types; rewriting this may lead to scalarizing
+  // the int divs.
+  if (N->getOperand(0).getValueType().isVector())
+    return SDValue();
+
+  // Bail if MinSize is not set, and also for both ARM and Thumb mode we need
+  // hwdiv support for this to be really profitable.
+  if (!(MinSize && HasDivide))
+    return SDValue();
+
+  // ARM mode is a bit simpler than Thumb: we can handle large power
+  // of 2 immediates with 1 mov instruction; no further checks required,
+  // just return the sdiv node.
+  if (!ST.isThumb())
+    return SDValue(N, 0);
+
+  // In Thumb mode, immediates larger than 128 need a wide 4-byte MOV,
+  // and thus lose the code size benefits of a MOVS that requires only 2.
+  // TargetTransformInfo and 'getIntImmCodeSizeCost' could be helpful here,
+  // but as it's doing exactly this, it's not worth the trouble to get TTI.
+  if (Divisor.sgt(128))
+    return SDValue();
+
+  return SDValue(N, 0);
+}
+
 SDValue ARMTargetLowering::LowerDIV_Windows(SDValue Op, SelectionDAG &DAG,
                                             bool Signed) const {
   assert(Op.getValueType() == MVT::i32 &&
          "unexpected type for custom lowering DIV");
   SDLoc dl(Op);
 
   SDValue DBZCHK = DAG.getNode(ARMISD::WIN__DBZCHK, dl, MVT::Other,
                                DAG.getEntryNode(), Op.getOperand(1));

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

+; RUN: llc -mtriple=armv7a -mattr=+hwdiv-arm %s -o - | FileCheck %s --check-prefixes=CHECK,DIV
+; RUN: llc -mtriple=armv7a -mattr=-hwdiv-arm %s -o - | FileCheck %s --check-prefixes=CHECK,NODIV
+
+; Check SREM
+define dso_local i32 @test_rem(i32 %F) local_unnamed_addr #0 {
+; CHECK-LABEL: test_rem 
+; CHECK:       asr   r1, r0, #31
+; CHECK-NEXT:  add   r1, r0, r1, lsr #30
+; CHECK-NEXT:  bic   r1, r1, #3
+; CHECK-NEXT:  sub   r0, r0, r1
+
+entry:
+  %div = srem i32 %F, 4
+  ret i32 %div
+}
+
+; Try an i16 sdiv, with a small immediate.
+define dso_local signext i16 @f0(i16 signext %F) local_unnamed_addr #0 {
+; CHECK-LABEL: f0
+
+; DIV:         mov     r1, #2
+; DIV-NEXT:    sdiv    r0, r0, r1
+; DIV-NEXT:    sxth    r0, r0
+; DIV-NEXT:    bx      lr
+
+; NODIV:       uxth r1, r0
+; NODIV-NEXT:  add  r0, r0, r1, lsr #15
+; NODIV-NEXT:  sxth r0, r0
+; NODIV-NEXT:  asr  r0, r0, #1
+; NODIV-NEXT:  bx   lr
+
+entry:
+  %0 = sdiv i16 %F, 2
+  ret i16 %0
+}
+
+; Try an i32 sdiv, with a small immediate.
+define dso_local i32 @f1(i32 %F) local_unnamed_addr #0 {
+; CHECK-LABEL: f1
+
+; DIV:       mov     r1, #4
+; DIV-NEXT:  sdiv    r0, r0, r1
+; DIV-NEXT:  bx      lr
+
+; NODIV:       asr  r1, r0, #31
+; NODIV-NEXT:  add  r0, r0, r1, lsr #30
+; NODIV-NEXT:  asr  r0, r0, #2
+; NODIV-NEXT:  bx   lr
+
+entry:
+  %div = sdiv i32 %F, 4
+  ret i32 %div
+}
+
+; Try a large power of 2 immediate, which should also be materialised with 1
+; move immediate instruction.
+define dso_local i32 @f2(i32 %F) local_unnamed_addr #0 {
+; CHECK-LABEL:  f2
+; DIV:        mov r1, #131072
+; DIV-NEXT:   sdiv  r0, r0, r1
+; DIV-NEXT:   bx  lr
+entry:
+  %div = sdiv i32 %F, 131072
+  ret i32 %div
+}
+
+; MinSize not set, so should expand to the faster but longer sequence.
+define dso_local i32 @f3(i32 %F) {
+; CHECK-LABEL: f3
+; CHECK:       asr r1, r0, #31
+; CHECK-NEXT:  add r0, r0, r1, lsr #30
+; CHECK-NEXT:  asr r0, r0, #2
+; CHECK-NEXT:  bx  lr
+entry:
+  %div = sdiv i32 %F, 4
+  ret i32 %div
+}
+
+attributes #0 = { minsize norecurse nounwind optsize readnone }

llvm/trunk/test/CodeGen/ARM/sdiv-pow2-thumb-size.ll

+; RUN: llc -mtriple=thumbv8 %s -o -       | FileCheck %s --check-prefixes=CHECK,T2
+; RUN: llc -mtriple=thumbv8m.main %s -o - | FileCheck %s --check-prefixes=CHECK,T2
+; RUN: llc -mtriple=thumbv8m.base %s -o - | FileCheck %s --check-prefixes=CHECK,T1
+; RUN: llc -mtriple=thumbv7em %s -o -     | FileCheck %s --check-prefixes=CHECK,T2
+; RUN: llc -mtriple=thumbv6m %s -o -      | FileCheck %s --check-prefixes=V6M
+
+; Armv6m targets don't have a sdiv instruction, so sdiv should not appear at
+; all in the output:
+
+; V6M: .file {{.*}}
+; V6M-NOT:  sdiv
+; V6M-NOT:  idiv
+
+; 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: immediates larger than
+; 128 don't give any code size savings.
+define dso_local i32 @f3(i32 %F) local_unnamed_addr #0 {
+; CHECK-LABEL:  f3
+; CHECK-NOT:    sdiv
+entry:
+  %div = sdiv i32 %F, 256
+  ret i32 %div
+}
+
+attributes #0 = { minsize norecurse nounwind optsize readnone }
+
+
+; These functions don't have the minsize attribute set, so should not lower
+; the sdiv to sdiv, but to the faster instruction sequence.
+
+define dso_local signext i16 @f4(i16 signext %F) {
+; T2-LABEL:  f4
+; T2:        uxth    r1, r0
+; T2-NEXT:   add.w   r0, r0, r1, lsr #15
+; T2-NEXT:   sxth    r0, r0
+; T2-NEXT:   asrs    r0, r0, #1
+; T2-NEXT:   bx      lr
+
+; T1-LABEL: f4
+; T1:       uxth  r1, r0
+; T1-NEXT:  lsrs  r1, r1, #15
+; T1-NEXT:  adds  r0, r0, r1
+; T1-NEXT:  sxth  r0, r0
+; T1-NEXT:  asrs  r0, r0, #1
+; T1-NEXT:  bx  lr
+
+entry:
+  %0 = sdiv i16 %F, 2
+  ret i16 %0
+}
+
+define dso_local i32 @f5(i32 %F) {
+; T2-LABEL: f5
+; T2:       asrs  r1, r0, #31
+; T2-NEXT:  add.w   r0, r0, r1, lsr #30
+; T2-NEXT:  asrs    r0, r0, #2
+; T2-NEXT:  bx      lr
+
+; T1-LABEL: f5
+; T1:       asrs r1, r0, #31
+; T1-NEXT:  lsrs  r1, r1, #30
+; T1-NEXT:  adds  r0, r0, r1
+; T1-NEXT:  asrs  r0, r0, #2
+; T1-NEXT:  bx  lr
+
+entry:
+  %div = sdiv i32 %F, 4
+  ret i32 %div
+}