[ARM] Honour ABI for rem under -O0 for EABI, GNUEABI, Android and Musl

[rovka]

Summary

At higher optimization levels, we generate the libcall for DIVREM_Ix, which is
fine: aeabi_{u|i}divmod. At -O0 we generate the one for REM_Ix, which is the
default {u}mod{q|h|s|d}i3.

This commit makes sure that we don't generate REM_Ix calls for ABIs that
don't support them (i.e. where we need to use DIVREM_Ix instead). This is
achieved by bailing out of FastISel, which can't handle non-double multi-reg
returns, and letting the legalization infrastructure expand the REM_Ix calls.

It also updates the divmod-eabi.ll test to run under -O0 as well, and adds some
Windows checks to it to make sure we don't break things for it.

Fixes PR27068

[rovka]

I'm not sure this is the most principled way to test this. I think unit tests for getLibcallName might be a better idea, but I notice we don't have an awful lot of unit tests. Any suggestions?

[rengolin]

test/CodeGen/ARM/divmod-eabi.ll

20

Removing the ABI registers will make the test a lot weaker and PR28164 tells me that this can already be broken in some cases.

Can you expand on what happens to the registers and why the test fails? My gut feeling is that a CHECK-DAG could fix the problem, but worst case scenario, we'll need two sets of CHECKs for O0 and O1.

[rovka]

I'm not sure this is the most principled way to test this. I think unit tests for getLibcallName might be a better idea, but I notice we don't have an awful lot of unit tests. Any suggestions?

test/CodeGen/ARM/divmod-eabi.ll

20

I think it's just some spills getting in the way, I'll try CHECK-DAG. Thanks.

[rovka]

Changed the test to check the registers too.

For the first 2 run lines (eabi, eabihf) i got away by adding -optimize-regalloc, but for the other lines I wasn't so lucky. It seems androideabi, gnueabi and musleabi all fail to merge div and divmod into a single call at O0, so I had to add another set of checks for that. I also had to add another set of checks for Darwin, because the scheduling is a bit different at O0 so instead of an add right after one of the libcalls we get a mov and then the corresponding add at the end of the function (I might be able to fiddle with some llc scheduling options to get rid of this...).

I think there's a problem with the androideabi, gnueabi and musleabi tests, which seem to be using r0 instead of r1 to get the remainder from idivmod (either that or it's just Friday evening and I'm being clumsy).

Please let me know if this looks like a good approach for the test and I'll update the rest of it (currently only the first function in the test is updated for the new sets of checks).

[compnerd]

test/CodeGen/ARM/divmod-eabi.ll

14

I think naming the prefix something more pertinent to what is being tested is helpful. How about EABI-RAOPT ?

23

Please add a test for non-EABI targets as do not get the EABI library calls.. How about something like thumbv7-windows?

46

Am I mistaken or couldnt these cases be collapsed? The idea is that on darwin targets, the calls are identical across the two? The math would be different, but you could have a single check for the calls in both cases.

[rovka]

This patch is wrong, I need to work on it some more. Thanks for the comments, I'll incorporate them into the next version of the patch.

test/CodeGen/ARM/divmod-eabi.ll

54

+ ; DARWIN-O0: __modsi3

[rovka]

• Collapsed common checks between O0 and default
• Added Windows checks (would be great if someone could double-check these, the Microsoft docs that I've found are pretty vague).
• Fixed the patch to use the right register for the remainder. For this I had to basically bail out of FastISel, because it doesn't handle non-double multi-reg returns. I hope this hammer isn't too big for this problem, but getting FastISel to do the right thing here seemed like quite some work.

[rengolin]

Much simpler, great tests. Thanks! LGTM.

include/llvm/Target/TargetLowering.h

public:
   /// Return true if integer divide is usually cheaper than a sequence of
   /// several shifts, adds, and multiplies for this target.
   /// The definition of "cheaper" may depend on whether we're optimizing
   /// for speed or for size.
   virtual bool isIntDivCheap(EVT VT, AttributeSet Attr) const {
     return false;
   }
 
+  /// Return true if the target can handle a standalone remainder operation.
+  virtual bool hasStandaloneRem(EVT VT) const {
+    return true;
+  }
+
   /// Return true if sqrt(x) is as cheap or cheaper than 1 / rsqrt(x)
   bool isFsqrtCheap() const {
     return FsqrtIsCheap;
   }
 
   /// Returns true if target has indicated at least one type should be bypassed.
   bool isSlowDivBypassed() const { return !BypassSlowDivWidths.empty(); }
 

lib/Target/ARM/ARMFastISel.cpp

 }
 
 bool ARMFastISel::SelectRem(const Instruction *I, bool isSigned) {
   MVT VT;
   Type *Ty = I->getType();
   if (!isTypeLegal(Ty, VT))
     return false;
 
+  // Many ABIs do not provide a libcall for standalone remainder, so we need to
+  // use divrem (see the RTABI 4.3.1). Since FastISel can't handle non-double
+  // multi-reg returns, we'll have to bail out.
+  if (!TLI.hasStandaloneRem(VT)) {
+    return false;
+  }
+
   RTLIB::Libcall LC = RTLIB::UNKNOWN_LIBCALL;
   if (VT == MVT::i8)
     LC = isSigned ? RTLIB::SREM_I8 : RTLIB::UREM_I8;
   else if (VT == MVT::i16)
     LC = isSigned ? RTLIB::SREM_I16 : RTLIB::UREM_I16;
   else if (VT == MVT::i32)
     LC = isSigned ? RTLIB::SREM_I32 : RTLIB::UREM_I32;
   else if (VT == MVT::i64)

lib/Target/ARM/ARMISelLowering.h

public:
 
     bool isCheapToSpeculateCttz() const override;
     bool isCheapToSpeculateCtlz() const override;
 
     bool supportSwiftError() const override {
       return true;
     }
 
+    bool hasStandaloneRem(EVT VT) const override {
+      return HasStandaloneRem;
+    }
+
   protected:
     std::pair<const TargetRegisterClass *, uint8_t>
     findRepresentativeClass(const TargetRegisterInfo *TRI,
                             MVT VT) const override;
 
   private:
     /// Subtarget - Keep a pointer to the ARMSubtarget around so that we can
     /// make the right decision when generating code for different targets.
     const ARMSubtarget *Subtarget;
 
     const TargetRegisterInfo *RegInfo;
 
     const InstrItineraryData *Itins;
 
     /// ARMPCLabelIndex - Keep track of the number of ARM PC labels created.
     ///
     unsigned ARMPCLabelIndex;
 
     // TODO: remove this, and have shouldInsertFencesForAtomic do the proper
     // check.
     bool InsertFencesForAtomic;
 
+    bool HasStandaloneRem = true;
+
     void addTypeForNEON(MVT VT, MVT PromotedLdStVT, MVT PromotedBitwiseVT);
     void addDRTypeForNEON(MVT VT);
     void addQRTypeForNEON(MVT VT);
     std::pair<SDValue, SDValue> getARMXALUOOp(SDValue Op, SelectionDAG &DAG, SDValue &ARMcc) const;
 
     typedef SmallVector<std::pair<unsigned, SDValue>, 8> RegsToPassVector;
     void PassF64ArgInRegs(const SDLoc &dl, SelectionDAG &DAG, SDValue Chain,
                           SDValue &Arg, RegsToPassVector &RegsToPass,

lib/Target/ARM/ARMISelLowering.cpp

ARMTargetLowering::ARMTargetLowering(const TargetMachine &TM,
 
   setOperationAction(ISD::SREM,  MVT::i32, Expand);
   setOperationAction(ISD::UREM,  MVT::i32, Expand);
   // Register based DivRem for AEABI (RTABI 4.2)
   if (Subtarget->isTargetAEABI() || Subtarget->isTargetAndroid() ||
       Subtarget->isTargetGNUAEABI() || Subtarget->isTargetMuslAEABI()) {
     setOperationAction(ISD::SREM, MVT::i64, Custom);
     setOperationAction(ISD::UREM, MVT::i64, Custom);
+    HasStandaloneRem = false;
 
     setLibcallName(RTLIB::SDIVREM_I8,  "__aeabi_idivmod");
     setLibcallName(RTLIB::SDIVREM_I16, "__aeabi_idivmod");
     setLibcallName(RTLIB::SDIVREM_I32, "__aeabi_idivmod");
     setLibcallName(RTLIB::SDIVREM_I64, "__aeabi_ldivmod");
     setLibcallName(RTLIB::UDIVREM_I8,  "__aeabi_uidivmod");
     setLibcallName(RTLIB::UDIVREM_I16, "__aeabi_uidivmod");
     setLibcallName(RTLIB::UDIVREM_I32, "__aeabi_uidivmod");

test/CodeGen/ARM/divmod-eabi.ll

+; We run the tests with both the default optimization level and O0, to make sure
+; we don't have any ABI differences between them. In principle, the ABI checks
+; should be the same for both optimization levels (there could be exceptions
+; from this when a div and a mod with the same operands are not coallesced into
+; the same divmod, but luckily this doesn't occur in practice even at O0).
+; Sometimes the checks that the correct registers are used after the libcalls
+; are different between optimization levels, so we have to separate them.
 ; RUN: llc -mtriple armv7-none-eabi %s -o - | FileCheck %s --check-prefix=EABI
+; RUN: llc -mtriple armv7-none-eabi %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefix=EABI
 ; RUN: llc -mtriple armv7-none-eabihf %s -o - | FileCheck %s --check-prefix=EABI
+; RUN: llc -mtriple armv7-none-eabihf %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefix=EABI
 ; All "eabi" (Bare, GNU and Android) must lower SREM/UREM to __aeabi_{u,i}divmod
 ; RUN: llc -mtriple armv7-linux-androideabi %s -o - | FileCheck %s --check-prefix=EABI
+; RUN: llc -mtriple armv7-linux-androideabi %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefix=EABI
 ; RUN: llc -mtriple armv7-linux-gnueabi %s -o - | FileCheck %s --check-prefix=EABI
+; RUN: llc -mtriple armv7-linux-gnueabi %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefix=EABI
 ; RUN: llc -mtriple armv7-linux-musleabi %s -o - | FileCheck %s --check-prefix=EABI
-; RUN: llc -mtriple armv7-apple-darwin %s -o - | FileCheck %s --check-prefix=DARWIN
+; RUN: llc -mtriple armv7-linux-musleabi %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefix=EABI
+; RUN: llc -mtriple armv7-apple-darwin %s -o - | FileCheck %s --check-prefixes=DARWIN,DARWIN-DEFAULT
+; RUN: llc -mtriple armv7-apple-darwin %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefixes=DARWIN,DARWIN-O0
 ; FIXME: long-term, we will use "-apple-macho" and won't need this exception:
-; RUN: llc -mtriple armv7-apple-darwin-eabi %s -o - | FileCheck %s --check-prefix=DARWIN
+; RUN: llc -mtriple armv7-apple-darwin-eabi %s -o - | FileCheck %s --check-prefixes=DARWIN,DARWIN-DEFAULT
+; RUN: llc -mtriple armv7-apple-darwin-eabi %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefixes=DARWIN,DARWIN-O0
+; RUN: llc -mtriple thumbv7-windows %s -o - | FileCheck %s --check-prefixes=WINDOWS,WINDOWS-DEFAULT
+; RUN: llc -mtriple thumbv7-windows %s -o - -O0 -optimize-regalloc | FileCheck %s --check-prefixes=WINDOWS,WINDOWS-O0
 
 define signext i16 @f16(i16 signext %a, i16 signext %b) {
 ; EABI-LABEL: f16:
 ; DARWIN-LABEL: f16:
+; WINDOWS-LABEL: f16:
 entry:
   %conv = sext i16 %a to i32
   %conv1 = sext i16 %b to i32
   %div = sdiv i32 %conv, %conv1
   %rem = srem i32 %conv, %conv1
 ; EABI: __aeabi_idivmod
 ; EABI: mov [[div:r[0-9]+]], r0
 ; EABI: mov [[rem:r[0-9]+]], r1
 ; DARWIN: ___divsi3
-; DARWIN: mov [[sum:r[0-9]+]], r0
+; DARWIN: mov [[div:r[0-9]+]], r0
 ; DARWIN: __modsi3
-; DARWIN: add [[sum]]{{.*}}r0
+; DARWIN-DEFAULT: add [[sum:r[0-9]+]], r0, [[div]]
+; DARWIN-O0: mov [[rem:r[0-9]+]], r0
+; WINDOWS: __rt_sdiv
+; WINDOWS-DEFAULT: mls [[rem:r[0-9]+]], r0,
+; WINDOWS-DEFAULT: adds [[sum:r[0-9]+]], [[rem]], r0
+; WINDOWS-O0: mov [[div:r[0-9]+]], r0
+; WINDOWS-O0: mls [[rem:r[0-9]+]], [[div]],
   %rem8 = srem i32 %conv1, %conv
 ; EABI: __aeabi_idivmod
 ; DARWIN: __modsi3
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem1:r[0-9]+]], r0,
   %add = add nsw i32 %rem, %div
   %add13 = add nsw i32 %add, %rem8
   %conv14 = trunc i32 %add13 to i16
 ; EABI: add r0{{.*}}r1
 ; EABI: sxth r0, r0
-; DARWIN: add r0{{.*}}[[sum]]
-; DARWIN: sxth r0, r0
+; DARWIN-DEFAULT: add [[res:r[0-9]+]], [[sum]], r0
+; DARWIN-O0: add [[sum:r[0-9]+]], [[rem]], [[div]]
+; DARWIN-O0: add [[res:r[0-9]+]], [[sum]], r0
+; DARWIN: sxth r0, [[res]]
+; WINDOWS-O0: adds [[sum:r[0-9]+]], [[rem]], [[div]]
+; WINDOWS: add [[rem1]], [[sum]]
+; WINDOWS: sxth [[res:r[0-9]+]], [[rem1]]
   ret i16 %conv14
 }
 
 define i32 @f32(i32 %a, i32 %b) {
 ; EABI-LABEL: f32:
 ; DARWIN-LABEL: f32:
+; WINDOWS-LABEL: f32:
 entry:
   %div = sdiv i32 %a, %b
   %rem = srem i32 %a, %b
 ; EABI: __aeabi_idivmod
 ; EABI: mov [[div:r[0-9]+]], r0
 ; EABI: mov [[rem:r[0-9]+]], r1
 ; DARWIN: ___divsi3
-; DARWIN: mov [[sum:r[0-9]+]], r0
+; DARWIN: mov [[div:r[0-9]+]], r0
 ; DARWIN: __modsi3
-; DARWIN: add [[sum]]{{.*}}r0
+; DARWIN-DEFAULT: add [[sum:r[0-9]+]], r0, [[div]]
+; DARWIN-O0: mov [[rem:r[0-9]+]], r0
+; WINDOWS: __rt_sdiv
+; WINDOWS: mov [[div:r[0-9]+]], r0
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem:r[0-9]+]], r0,
+; WINDOWS-DEFAULT: add [[div]], [[rem]]
   %rem1 = srem i32 %b, %a
 ; EABI: __aeabi_idivmod
 ; DARWIN: __modsi3
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem1:r[0-9]+]], r0,
   %add = add nsw i32 %rem, %div
   %add2 = add nsw i32 %add, %rem1
 ; EABI: add r0{{.*}}r1
-; DARWIN: add r0{{.*}}[[sum]]
+; DARWIN-DEFAULT: add r0, [[sum]], r0
+; DARWIN-O0: add [[sum:r[0-9]+]], [[rem]], [[div]]
+; DARWIN-O0: add [[res:r[0-9]+]], [[sum]], r0
+; WINDOWS-DEFAULT: add [[rem1]], [[div]]
+; WINDOWS-O0: adds [[sum:r[0-9]+]], [[rem]], [[div]]
+; WINDOWS-O0: add [[rem1]], [[sum]]
   ret i32 %add2
 }
 
 define i32 @uf(i32 %a, i32 %b) {
 ; EABI-LABEL: uf:
 ; DARWIN-LABEL: uf:
+; WINDOWS-LABEL: uf:
 entry:
   %div = udiv i32 %a, %b
   %rem = urem i32 %a, %b
 ; EABI: __aeabi_uidivmod
 ; DARWIN: ___udivsi3
-; DARWIN: mov [[sum:r[0-9]+]], r0
+; DARWIN: mov [[div:r[0-9]+]], r0
 ; DARWIN: __umodsi3
-; DARWIN: add [[sum]]{{.*}}r0
+; DARWIN-DEFAULT: add [[sum:r[0-9]+]], r0, [[div]]
+; DARWIN-O0: mov [[rem:r[0-9]+]], r0
+; WINDOWS: __rt_udiv
+; WINDOWS: mov [[div:r[0-9]+]], r0
+; WINDOWS: __rt_udiv
+; WINDOWS: mls [[rem:r[0-9]+]], r0,
+; WINDOWS-DEFAULT: add [[div]], [[rem]]
   %rem1 = urem i32 %b, %a
 ; EABI: __aeabi_uidivmod
 ; DARWIN: __umodsi3
+; WINDOWS: __rt_udiv
+; WINDOWS: mls [[rem1:r[0-9]+]], r0,
   %add = add nuw i32 %rem, %div
   %add2 = add nuw i32 %add, %rem1
 ; EABI: add r0{{.*}}r1
-; DARWIN: add r0{{.*}}[[sum]]
+; DARWIN-DEFAULT: add r0, [[sum]], r0
+; DARWIN-O0: add [[sum:r[0-9]+]], [[rem]], [[div]]
+; DARWIN-O0: add [[res:r[0-9]+]], [[sum]], r0
+; WINDOWS-DEFAULT: add [[rem1]], [[div]]
+; WINDOWS-O0: adds [[sum:r[0-9]+]], [[rem]], [[div]]
+; WINDOWS-O0: add [[rem1]], [[sum]]
   ret i32 %add2
 }
 
 define i64 @longf(i64 %a, i64 %b) {
 ; EABI-LABEL: longf:
 ; DARWIN-LABEL: longf:
+; WINDOWS-LABEL: longf:
 entry:
   %div = sdiv i64 %a, %b
   %rem = srem i64 %a, %b
 ; EABI: __aeabi_ldivmod
 ; EABI-NEXT: adds r0
 ; EABI-NEXT: adc r1
 ; EABI-NOT: __aeabi_ldivmod
 ; DARWIN: ___divdi3
 ; DARWIN: mov [[div1:r[0-9]+]], r0
 ; DARWIN: mov [[div2:r[0-9]+]], r1
 ; DARWIN: __moddi3
+; WINDOWS: __rt_sdiv64
+; WINDOWS: mov [[div1:r[0-9]+]], r0
+; WINDOWS: mov [[div2:r[0-9]+]], r1
+; WINDOWS: __moddi3
   %add = add nsw i64 %rem, %div
 ; DARWIN: adds r0{{.*}}[[div1]]
 ; DARWIN: adc r1{{.*}}[[div2]]
+; WINDOWS: adds.w r0, r0, [[div1]]
+; WINDOWS: adc.w r1, r1, [[div2]]
   ret i64 %add
 }
 
 define i16 @shortf(i16 %a, i16 %b) {
 ; EABI-LABEL: shortf:
 ; DARWIN-LABEL: shortf:
+; WINDOWS-LABEL: shortf:
 entry:
   %div = sdiv i16 %a, %b
   %rem = srem i16 %a, %b
 ; EABI: __aeabi_idivmod
 ; DARWIN: ___divsi3
 ; DARWIN: mov [[div1:r[0-9]+]], r0
 ; DARWIN: __modsi3
+; WINDOWS: __rt_sdiv
+; WINDOWS: mov [[div:r[0-9]+]], r0
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem:r[0-9]+]], r0,
   %add = add nsw i16 %rem, %div
+; EABI: add r0, r1
 ; DARWIN: add r0{{.*}}[[div1]]
+; WINDOWS: add [[rem]], [[div]]
   ret i16 %add
 }
 
 define i32 @g1(i32 %a, i32 %b) {
 ; EABI-LABEL: g1:
 ; DARWIN-LABEL: g1:
+; WINDOWS-LABEL: g1:
 entry:
   %div = sdiv i32 %a, %b
   %rem = srem i32 %a, %b
 ; EABI: __aeabi_idivmod
 ; DARWIN: ___divsi3
 ; DARWIN: mov [[sum:r[0-9]+]], r0
 ; DARWIN: __modsi3
+; WINDOWS: __rt_sdiv
+; WINDOWS: mov [[div:r[0-9]+]], r0
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem:r[0-9]+]], r0,
   %add = add nsw i32 %rem, %div
 ; EABI: add r0{{.*}}r1
 ; DARWIN: add r0{{.*}}[[sum]]
+; WINDOWS: add [[rem]], [[div]]
   ret i32 %add
 }
 
 ; On both Darwin and Gnu, this is just a call to __modsi3
 define i32 @g2(i32 %a, i32 %b) {
 ; EABI-LABEL: g2:
 ; DARWIN-LABEL: g2:
+; WINDOWS-LABEL: g2:
 entry:
   %rem = srem i32 %a, %b
 ; EABI: __aeabi_idivmod
 ; DARWIN: __modsi3
+; WINDOWS: __rt_sdiv
   ret i32 %rem
 ; EABI: mov r0, r1
+; WINDOWS: mls r0, r0,
 }
 
 define i32 @g3(i32 %a, i32 %b) {
 ; EABI-LABEL: g3:
 ; DARWIN-LABEL: g3:
+; WINDOWS-LABEL: g3:
 entry:
   %rem = srem i32 %a, %b
 ; EABI: __aeabi_idivmod
 ; EABI: mov [[mod:r[0-9]+]], r1
 ; DARWIN: __modsi3
 ; DARWIN: mov [[sum:r[0-9]+]], r0
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem:r[0-9]+]], r0,
   %rem1 = srem i32 %b, %rem
 ; EABI: __aeabi_idivmod
 ; DARWIN: __modsi3
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem1:r[0-9]+]], r0,
   %add = add nsw i32 %rem1, %rem
 ; EABI: add r0, r1, [[mod]]
 ; DARWIN: add r0{{.*}}[[sum]]
+; WINDOWS: add [[rem1]], [[rem]]
   ret i32 %add
 }
 
 define i32 @g4(i32 %a, i32 %b) {
 ; EABI-LABEL: g4:
 ; DARWIN-LABEL: g4:
+; WINDOWS-LABEL: g4:
 entry:
   %div = sdiv i32 %a, %b
 ; EABI: __aeabi_idiv{{$}}
 ; EABI: mov [[div:r[0-9]+]], r0
 ; DARWIN: ___divsi3
 ; DARWIN: mov [[sum:r[0-9]+]], r0
+; WINDOWS: __rt_sdiv
+; WINDOWS: mov [[div:r[0-9]+]], r0
   %rem = srem i32 %b, %div
 ; EABI: __aeabi_idivmod
 ; DARWIN: __modsi3
+; WINDOWS: __rt_sdiv
+; WINDOWS: mls [[rem:r[0-9]+]], r0,
   %add = add nsw i32 %rem, %div
 ; EABI: add r0, r1, [[div]]
 ; DARWIN: add r0{{.*}}[[sum]]
+; WINDOWS: add [[rem]], [[div]]
   ret i32 %add
 }