builtins: Add ARM Thumb1 implementation for uidiv and uidivmod

[weimingz]

Summary

The current uidiv supports archs without clz. However, the asm is for thumb2/arm.
For uidivmod, the existing code calls the C version of uidivmodsi4, which then calls uidiv. The extra push/pop/bl makes it less efficient.

[compnerd]

lib/builtins/arm/aeabi_uidivmod.S

29 ↗

(On Diff #79943)

Nice using the shrink wrapping.

Do we want to maintain stack alignment and push the frame pointer as well?

31 ↗

(On Diff #79943)

Its there a benefit to popping into r3? Or does the thumb 1 encoding only allow popping into low registers?

lib/builtins/arm/udivsi3.S

80 ↗

(On Diff #79943)

Not your change, but do you mind creating a macro for the thumb2 case too?

103 ↗

(On Diff #79943)

Shouldn't the label be aligned, not the code?

106 ↗

(On Diff #79943)

Can we use or instead?

174 ↗

(On Diff #79943)

Please use defined.

[weimingz]

lib/builtins/arm/aeabi_uidivmod.S

29 ↗

(On Diff #79943)

Since thumb1 has no ldrd/strd, I think it's OK. And I see existing code like aeabi_idivmod.S, aeabi_cdcmp.S pushes odd number of regs.

31 ↗

(On Diff #79943)

right. can only pop to R0-R7 and PC

lib/builtins/arm/udivsi3.S

80 ↗

(On Diff #79943)

yes. I did plan to do.

103 ↗

(On Diff #79943)

yes, I thought the same. But I tried and didn't work. Will do more digging.

106 ↗

(On Diff #79943)

in Thumb1, ORR doesn't support immediate values.

174 ↗

(On Diff #79943)

will do

[weimingz]

Updated per Saleem's comments. For adc label alignment, not sure if it's the best way to do.

[compnerd]

lib/builtins/arm/udivsi3.S

200 ↗

(On Diff #80095)

Can you format this please? (clang-format).

254 ↗

(On Diff #80095)

Any reason to not just use the single definition of this label? (as in just move it for both cases.

106 ↗

(On Diff #79943)

Hmm, do we have some way to guarantee that the thumb bit would never be set by the linker? (at least with link, the linker will set the thumb bit on the relocation target if it is in the code section on a thumb block).

[weimingz]

lib/builtins/arm/udivsi3.S

200 ↗

(On Diff #80095)

Will do. I thought clang-format was only for C/C++.

254 ↗

(On Diff #80095)

Right, we don't need two definitions. Will remove this.

106 ↗

(On Diff #79943)

this is the same as the thumbe2 version (lne70-71)

if __ARM_ARCH_ISA_THUMB == 2

adr  ip, LOCAL_LABEL(div0block) + 1

Since it's PC-relative, there should be no relocation entry for this.

[weimingz]

clang-formatted the .h file but it doesn't support .S. Even if I force it to format, the output looks not very nice.

[compnerd]

A .S file is run through the C preprocessor. You are defining a macro. That macro should be something that clang-format can format just fine (in fact, I had done just that for the Thumb2 case).

[weimingz]

Thanks. I just picked the change on the macro def from git-clang-format output. I also replace the space with tab as the rest of the file uses tab for indention.

[compnerd]

Thanks for the various revisions. I don't think that the tests for the built-ins are run on the bots, so please do run them locally again before committing.

[rengolin]

In D27309#613371, @compnerd wrote:

Thanks for the various revisions. I don't think that the tests for the built-ins are run on the bots, so please do run them locally again before committing.

Wait, aren't them executed when "make check-all" is used on compiler-rt?

[weimingz]

In D27309#613384, @rengolin wrote:

In D27309#613371, @compnerd wrote:

Thanks for the various revisions. I don't think that the tests for the built-ins are run on the bots, so please do run them locally again before committing.

Wait, aren't them executed when "make check-all" is used on compiler-rt?

The default CMake file uses -march=armv7, so the "thumb1" path is not tested by check-all.
Locally, I changed the CMake to let udivsi3.S to be used for armv6m.

[rengolin]

In D27309#613515, @weimingz wrote:

The default CMake file uses -march=armv7, so the "thumb1" path is not tested by check-all.
Locally, I changed the CMake to let udivsi3.S to be used for armv6m.

Ah, of course!

[weimingz]

I manually build and run udivmodsi4_test.c and udivsi3_test.c, no error

[dim]

Apparently this and it's followup commit rL288777 cause problems for different ARM ISAs on FreeBSD, and __udivsi3 is even completely broken: https://github.com/strejda/tegra/commit/30914ba688cb987240e22b2c7641463446527783

[rengolin]

Did someone revert this? I think we should until we're sure how to fix the problem.

[dim]

In D27309#698613, @rengolin wrote:

Did someone revert this? I think we should until we're sure how to fix the problem.

In FreeBSD, @strejda committed this rather big hammer to work around it: https://reviews.freebsd.org/rS314907, basically disabling all thumb support. :(

I would certainly not object to reverting rL288710 for now, and put up a new review to handle all concerns. @strejda, you already had a bunch of suggestions in your github commit, right?

[rengolin]

In D27309#698618, @dim wrote:

In FreeBSD, @strejda committed this rather big hammer to work around it: https://reviews.freebsd.org/rS314907, basically disabling all thumb support. :(

Ouch, that's not good.

I would certainly not object to reverting rL288710 for now, and put up a new review to handle all concerns. @strejda, you already had a bunch of suggestions in your github commit, right?

We can do that offline. I'm OOO, so if anyone could revert the patch(es) for now, that'd be great. If not, I'll do when I'm back home.

--renato

[weimingz]

Most of the changes are guarded by __ARM_ARCH_ISA_THUMB == 1 and I reviewed again of the "else" part and they look OK except for one suspect:
https://reviews.llvm.org/D30867

[strejda]

In D27309#698696, @weimingz wrote:

Most of the changes are guarded by __ARM_ARCH_ISA_THUMB == 1 and I reviewed again of the "else" part and they look OK except for one suspect:
https://reviews.llvm.org/D30867

No, unfortunately, _ _ARM_ARCH_ISA_THUMB == n can't be used as selector for Thumb1 (or Thumb2) code.
Value of _ _ARM_ARCH_ISA_THUMB isn't based on actual compilation mode (-mthumb, -marm), its based on given CPU (or arch) capabilities.
Thus, if we compile library with '-marm -march=armv6' then _ _ARM_ARCH_ISA_THUMB is set to '1'. So we ends with Thumb1 code compiled using ARM ISA. Not a nice result, right?
So D30867 cannot help us.

I found these problems:

• Thumb[1][2] code selection is broken, "(_ _ARM_ARCH_ISA_THUMB == n && (defined(_ _THUMBEL_ _) || defined(_ _THUMBEB_ _))" is right condition. See: https://github.com/strejda/tegra/commit/91057bb46e54e350da87e354aed3189d469da458#diff-a8e5a4d82eadfcc89b4f54d6755a46b4L97
  
  This one is fatal for FreeBSD.

• all Thumb1 and some Thumb2 functions are not properly decorated by DEFINE_COMPILERRT_THUMB_FUNCTION() This breaks debugging.

• usage of '.thumb' directive is inconsistent across files

• Thumb 1 version of __udivsi3 is broken and doesn't not work at all. See:

	cmp	r0, r1, lsl IMM shift
 	addhs	r3, r3, IMM (1 << shift)
 	subhs	r0, r0, r1, lsl IMM shift

and

	lsls	r2, r1, IMM shift
	cmp	r0, r2
	blo	1f
	subs	r0, r0, r2
1:
	adcs	r3, r3

• There is no Thumb1 variant of __udivmodsi4

[weimingz]

In D27309#698801, @strejda wrote:

In D27309#698696, @weimingz wrote:

Most of the changes are guarded by __ARM_ARCH_ISA_THUMB == 1 and I reviewed again of the "else" part and they look OK except for one suspect:
https://reviews.llvm.org/D30867

No, unfortunately, _ _ARM_ARCH_ISA_THUMB == n can't be used as selector for Thumb1 (or Thumb2) code.
Value of _ _ARM_ARCH_ISA_THUMB isn't based on actual compilation mode (-mthumb, -marm), its based on given CPU (or arch) capabilities.
Thus, if we compile library with '-marm -march=armv6' then _ _ARM_ARCH_ISA_THUMB is set to '1'. So we ends with Thumb1 code compiled using ARM ISA. Not a nice result, right?
So D30867 cannot help us.

I found these problems:

• Thumb[1][2] code selection is broken, "(_ _ARM_ARCH_ISA_THUMB == n && (defined(_ _THUMBEL_ _) || defined(_ _THUMBEB_ _))" is right condition. See: https://github.com/strejda/tegra/commit/91057bb46e54e350da87e354aed3189d469da458#diff-a8e5a4d82eadfcc89b4f54d6755a46b4L97
  
  This one is fatal for FreeBSD.

• all Thumb1 and some Thumb2 functions are not properly decorated by DEFINE_COMPILERRT_THUMB_FUNCTION() This breaks debugging.

• usage of '.thumb' directive is inconsistent across files

• Thumb 1 version of __udivsi3 is broken and doesn't not work at all. See:

	cmp	r0, r1, lsl IMM shift
 	addhs	r3, r3, IMM (1 << shift)
 	subhs	r0, r0, r1, lsl IMM shift

and

	lsls	r2, r1, IMM shift
	cmp	r0, r2
	blo	1f
	subs	r0, r0, r2
1:
	adcs	r3, r3

• There is no Thumb1 variant of __udivmodsi4

Great! Thanks for finding out the root cause. Will you pull the github patch into upstream repo?
Regarding udivmodi4.S, we can work on it. Currently, the thumb1 lib can use the C version (udivmodsi4.c ), which simply calls __udivsi3 with extra mul and sub . Since we implemented _udivsi3 in asm, the perf won't be too bad.

[strejda]

Sure. Give me some time to rebase (and polish) patch to the current upstream. I prefer to create a new review for it because I'm still not sure if all bits of patch are acceptable for upstream.

compiler-rt/trunk/lib/builtins/arm/aeabi_uidivmod.S

 
 #if defined(__MINGW32__)
 #define __aeabi_uidivmod __rt_udiv
 #endif
 
         .syntax unified
         .p2align 2
 DEFINE_COMPILERRT_FUNCTION(__aeabi_uidivmod)
+#if __ARM_ARCH_ISA_THUMB == 1
+        cmp     r0, r1
+        bcc     LOCAL_LABEL(case_denom_larger)
+        push    {r0, r1, lr}
+        bl      SYMBOL_NAME(__aeabi_uidiv)
+        pop     {r1, r2, r3}
+        muls    r2, r2, r0 // r2 = quot * denom
+        subs    r1, r1, r2
+        JMP     (r3)
+LOCAL_LABEL(case_denom_larger):
+        movs    r1, r0
+        movs    r0, #0
+        JMP     (lr)
+#else
         push    { lr }
         sub     sp, sp, #4
         mov     r2, sp
 #if defined(__MINGW32__)
         mov     r3, r0
         mov     r0, r1
         mov     r1, r3
 #endif
         bl      SYMBOL_NAME(__udivmodsi4)
         ldr     r1, [sp]
         add     sp, sp, #4
         pop     { pc }
+#endif
 END_COMPILERRT_FUNCTION(__aeabi_uidivmod)
 
 NO_EXEC_STACK_DIRECTIVE
 

compiler-rt/trunk/lib/builtins/arm/udivsi3.S

 #if __ARM_ARCH_EXT_IDIV__
   tst     r1, r1
   beq     LOCAL_LABEL(divby0)
   udiv  r0, r0, r1
   bx    lr
 #else
   cmp r1, #1
   bcc LOCAL_LABEL(divby0)
+#if __ARM_ARCH_ISA_THUMB == 1
+  bne LOCAL_LABEL(num_neq_denom)
+  JMP(lr)
+LOCAL_LABEL(num_neq_denom):
+#else
   IT(eq)
   JMPc(lr, eq)
+#endif
   cmp r0, r1
+#if __ARM_ARCH_ISA_THUMB == 1
+  bhs LOCAL_LABEL(num_ge_denom)
+  movs r0, #0
+  JMP(lr)
+LOCAL_LABEL(num_ge_denom):
+#else
   ITT(cc)
   movcc r0, #0
   JMPc(lr, cc)
+#endif
+
   /*
    * Implement division using binary long division algorithm.
    *
    * r0 is the numerator, r1 the denominator.
    *
    * The code before JMP computes the correct shift I, so that
    * r0 and (r1 << I) have the highest bit set in the same position.
    * At the time of JMP, ip := .Ldiv0block - 12 * I.
    * This depends on the fixed instruction size of block.
    * For ARM mode, this is 12 Bytes, for THUMB mode 14 Bytes.
    *
    * block(shift) implements the test-and-update-quotient core.
    * It assumes (r0 << shift) can be computed without overflow and
    * that (r0 << shift) < 2 * r1. The quotient is stored in r3.
    */
 
-#  ifdef __ARM_FEATURE_CLZ
+#  if defined(__ARM_FEATURE_CLZ)
   clz ip, r0
   clz r3, r1
   /* r0 >= r1 implies clz(r0) <= clz(r1), so ip <= r3. */
   sub r3, r3, ip
 #    if __ARM_ARCH_ISA_THUMB == 2
   adr ip, LOCAL_LABEL(div0block) + 1
   sub ip, ip, r3, lsl #1
 #    else
   adr ip, LOCAL_LABEL(div0block)
 #    endif
   sub ip, ip, r3, lsl #2
   sub ip, ip, r3, lsl #3
   mov r3, #0
   bx  ip
-#  else
+#  else /* No CLZ Feature */
 #    if __ARM_ARCH_ISA_THUMB == 2
 #    error THUMB mode requires CLZ or UDIV
 #    endif
+#    if __ARM_ARCH_ISA_THUMB == 1
+#      define BLOCK_SIZE 10
+#    else
+#      define BLOCK_SIZE 12
+#    endif
+
   mov r2, r0
+#    if __ARM_ARCH_ISA_THUMB == 1
+  mov ip, r0
+  adr r0, LOCAL_LABEL(div0block)
+  adds r0, #1
+#    else
   adr ip, LOCAL_LABEL(div0block)
-
-  lsr r3, r2, #16
+#    endif
+  lsrs  r3, r2, #16
   cmp r3, r1
+#    if __ARM_ARCH_ISA_THUMB == 1
+  blo LOCAL_LABEL(skip_16)
+  movs r2, r3
+  subs r0, r0, #(16 * BLOCK_SIZE)
+LOCAL_LABEL(skip_16):
+#    else
   movhs r2, r3
-  subhs ip, ip, #(16 * 12)
+  subhs ip, ip, #(16 * BLOCK_SIZE)
+#    endif
 
-  lsr r3, r2, #8
+  lsrs  r3, r2, #8
   cmp r3, r1
+#    if __ARM_ARCH_ISA_THUMB == 1
+  blo LOCAL_LABEL(skip_8)
+  movs r2, r3
+  subs r0, r0, #(8 * BLOCK_SIZE)
+LOCAL_LABEL(skip_8):
+#    else
   movhs r2, r3
-  subhs ip, ip, #(8 * 12)
+  subhs ip, ip, #(8 * BLOCK_SIZE)
+#    endif
 
-  lsr r3, r2, #4
+  lsrs  r3, r2, #4
   cmp r3, r1
+#    if __ARM_ARCH_ISA_THUMB == 1
+  blo LOCAL_LABEL(skip_4)
+  movs r2, r3
+  subs r0, r0, #(4 * BLOCK_SIZE)
+LOCAL_LABEL(skip_4):
+#    else
   movhs r2, r3
-  subhs ip, #(4 * 12)
+  subhs ip, #(4 * BLOCK_SIZE)
+#    endif
 
-  lsr r3, r2, #2
+  lsrs  r3, r2, #2
   cmp r3, r1
+#    if __ARM_ARCH_ISA_THUMB == 1
+  blo LOCAL_LABEL(skip_2)
+  movs r2, r3
+  subs r0, r0, #(2 * BLOCK_SIZE)
+LOCAL_LABEL(skip_2):
+#    else
   movhs r2, r3
-  subhs ip, ip, #(2 * 12)
+  subhs ip, ip, #(2 * BLOCK_SIZE)
+#    endif
 
   /* Last block, no need to update r2 or r3. */
+#    if __ARM_ARCH_ISA_THUMB == 1
+  lsrs r3, r2, #1
+  cmp r3, r1
+  blo LOCAL_LABEL(skip_1)
+  subs r0, r0, #(1 * BLOCK_SIZE)
+LOCAL_LABEL(skip_1):
+  movs r2, r0
+  mov r0, ip
+  movs r3, #0
+  JMP (r2)
+
+#    else
   cmp r1, r2, lsr #1
-  subls ip, ip, #(1 * 12)
+  subls ip, ip, #(1 * BLOCK_SIZE)
 
-  mov r3, #0
+  movs  r3, #0
 
   JMP(ip)
-#  endif
+#    endif
+#  endif /* __ARM_FEATURE_CLZ */
+
 
 #define IMM #
+  /* due to the range limit of branch in Thumb1, we have to place the
+     block closer */
+LOCAL_LABEL(divby0):
+  movs  r0, #0
+#      if defined(__ARM_EABI__)
+  bl  __aeabi_idiv0 // due to relocation limit, can't use b.
+#      endif
+  JMP(lr)
+
 
+#if __ARM_ARCH_ISA_THUMB == 1
+#define block(shift)                                                           \
+  lsls r2, r1, IMM shift;                                                      \
+  cmp r0, r2;                                                                  \
+  blo LOCAL_LABEL(block_skip_##shift);                                         \
+  subs r0, r0, r2;                                                             \
+  LOCAL_LABEL(block_skip_##shift) :;                                           \
+  adcs r3, r3 /* same as ((r3 << 1) | Carry). Carry is set if r0 >= r2. */
+
+  /* TODO: if current location counter is not not word aligned, we don't
+     need the .p2align and nop */
+  /* Label div0block must be word-aligned. First align block 31 */
+  .p2align 2
+  nop /* Padding to align div0block as 31 blocks = 310 bytes */
+
+#else
 #define block(shift)                                                           \
   cmp  r0, r1, lsl IMM shift;                                         \
   ITT(hs);                                                               \
   WIDE(addhs)  r3, r3, IMM (1 << shift);                              \
   WIDE(subhs)  r0, r0, r1, lsl IMM shift
+#endif
 
   block(31)
   block(30)
   block(29)
   block(28)
   block(27)
   block(26)
   block(25)
#endif
   block(1)
 LOCAL_LABEL(div0block):
   block(0)
 
   mov r0, r3
   JMP(lr)
 #endif /* __ARM_ARCH_EXT_IDIV__ */
 
-LOCAL_LABEL(divby0):
-  mov r0, #0
-#ifdef __ARM_EABI__
-  b __aeabi_idiv0
-#else
-  JMP(lr)
-#endif
-
 END_COMPILERRT_FUNCTION(__udivsi3)
 
 NO_EXEC_STACK_DIRECTIVE
 

compiler-rt/trunk/lib/builtins/assembly.h

 
 #endif
 
 #if defined(__arm__)
 #if defined(__ARM_ARCH_4T__) || __ARM_ARCH >= 5
 #define ARM_HAS_BX
 #endif
 #if !defined(__ARM_FEATURE_CLZ) &&                                             \
-    (__ARM_ARCH >= 6 || (__ARM_ARCH == 5 && !defined(__ARM_ARCH_5__)))
+    ((__ARM_ARCH >= 6 && __ARM_ARCH_PROFILE != 'M') ||                         \
+     (__ARM_ARCH == 5 && !defined(__ARM_ARCH_5__)))
 #define __ARM_FEATURE_CLZ
 #endif
 
 #ifdef ARM_HAS_BX
 #define JMP(r) bx r
 #define JMPc(r, c) bx##c r
 #else
 #define JMP(r) mov pc, r