[compiler-rt][builtins] Add helper functions for uint16/sint16/uint8/sint8 div&mod

[benshi001]

Summary

__udivmodhi4: uint16 div and mod
__udivmodqi4: uint8 div and mod
__divmodhi4 : sint16 div and mod
__divmodqi4 : sint8 div and mod

The above helper functions in libgcc have special ABI as described at
https://gcc.gnu.org/wiki/avr-gcc#Exceptions_to_the_Calling_Convention .

[benshi001]

Some key points

1. All helper functions are written in the minimal AVR instruction set, so they can run on all devices.
2. Currently llvm generates call to __divmodhi4 for int8 div/mod, so we omit __divmodqi4.
3. They can be built for different device families via specifying CMAKE_CXX_FLAGS and CMAKE_C_FLAGS when doing cmake.
4. They have all been tested with random numbers, and all run correctly. divmodhi4: https://github.com/benshi001/avr-test/blob/main/divmod_sint16.ino udivmodhi4: https://github.com/benshi001/avr-test/blob/main/divmod_uint16.ino udivmodqi4: https://github.com/benshi001/avr-test/blob/main/divmod_uint8.ino
5. The implementation of the unsigned ones are easy to understand, but divmodhi4 is more tricky, it has sub functions and even calls __udivmodhi4. So it is hard to make a clear decription comment among the source code lines.
6. I am quite confident they are correct since they do work on my AVR board, my final goal is making "clang+llvm+compiler-rt+lld" fully functional and can replace gnu tool chain.

[aykevl]

Looks good to me.

It would be nice to write these functions in C instead of in assembly (for easier debugging and improved code generation for more advanced chips) but the special calling convention makes this difficult.

A future improvement could be to implement this special calling convention in the AVR backend of LLVM, so that LLVM can generate more efficient code. But I don't think it's necessary right now.

compiler-rt/lib/builtins/avr/divmodhi4.S

22–26

Can you use __tmp_reg__ instead of manually defining rtmp?

[aykevl]

The following code produces __divmodqi4, so I think it is still needed:

define i8 @divqi4(i8 %a, i8 %b) addrspace(1) {
  %result = sdiv i8 %a, %b
  ret i8 %result
}

See: https://llvm.godbolt.org/z/nTbcTfbb7

[benshi001]

In D124600#3492627, @aykevl wrote:

The following code produces __divmodqi4, so I think it is still needed:

define i8 @divqi4(i8 %a, i8 %b) addrspace(1) {
  %result = sdiv i8 %a, %b
  ret i8 %result
}

See: https://llvm.godbolt.org/z/nTbcTfbb7

I have implemented __divmodqi4. Here are the contrast tests:

divmodhi4: https://github.com/benshi001/avr-test/blob/main/divmod_sint16.ino

divmodqi4: https://github.com/benshi001/avr-test/blob/main/divmod_sint8.ino

udivmodhi4: https://github.com/benshi001/avr-test/blob/main/divmod_uint16.ino

udivmodqi4: https://github.com/benshi001/avr-test/blob/main/divmod_uint8.ino

compiler-rt/lib/builtins/avr/divmodhi4.S

22–26

changed to __tmp_reg__

[aykevl]

Looks good to me.

compiler-rt/lib/builtins/avr/divmodhi4.S

22–26

No I mean, can you remove this .set __tmp_reg__, num entirely? Since D119807 this should not be needed anymore. Or do you want to keep it for backwards compatibility with Clang 14?

[benshi001]

compiler-rt/lib/builtins/avr/divmodhi4.S

22–26

I expect they can be built with older version of clang. :)

[benshi001]

.

compiler-rt/lib/builtins/CMakeLists.txt

 set(armv8m.main_SOURCES ${arm_SOURCES})
 set(armv8.1m.main_SOURCES ${arm_SOURCES})
 
 # 8-bit AVR MCU
 set(avr_SOURCES
   avr/mulqi3.S
   avr/mulhi3.S
   avr/exit.S
+  avr/divmodhi4.S
+  avr/udivmodhi4.S
+  avr/divmodqi4.S
+  avr/udivmodqi4.S
   ${GENERIC_SOURCES}
 )
 
 # hexagon arch
 set(hexagon_SOURCES
   hexagon/common_entry_exit_abi1.S
   hexagon/common_entry_exit_abi2.S
   hexagon/common_entry_exit_legacy.S

compiler-rt/lib/builtins/avr/divmodhi4.S

+//===------------- divmodhi4.S - sint16 div & mod -------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// As described at
+// https://gcc.gnu.org/wiki/avr-gcc#Exceptions_to_the_Calling_Convention, the
+// prototype is `struct {sint16, sint16}  __divmodhi4(sint16, sint16)`.
+// The sint16 quotient is returned via R23:R22, and the sint16 remainder is
+// returned via R25:R24, while registers R21/R26/27/Rtmp and bit T in SREG
+// are clobbered.
+//
+//===----------------------------------------------------------------------===//
+
+  .text
+  .align 2
+
+#ifdef __AVR_TINY__
+  .set __tmp_reg__, 16
+#else
+  .set __tmp_reg__, 0
+#endif
+
+  .globl __divmodhi4
+  .type  __divmodhi4, @function
+
+__divmodhi4:
+  bst     r25, 7
+  mov     __tmp_reg__, r23
+  brtc    __divmodhi4_a
+  com     __tmp_reg__
+  rcall   __divmodhi4_b
+
+__divmodhi4_a:
+  sbrc    r23, 7
+  rcall   __divmodhi4_c
+  rcall   __udivmodhi4 ; Call __udivmodhi4 to do real calculation.
+  sbrc    __tmp_reg__, 7
+  rcall   __divmodhi4_c
+  brtc    __divmodhi4_exit
+
+__divmodhi4_b:
+  com     r25
+  neg     r24
+  sbci    r25, 255
+  ret                  ; Return quotient via R23:R22 and remainder via R25:R24.
+
+__divmodhi4_c:
+  com     r23
+  neg     r22
+  sbci    r23, 255
+
+__divmodhi4_exit:
+  ret                  ; Return quotient via R23:R22 and remainder via R25:r24.

compiler-rt/lib/builtins/avr/divmodqi4.S

+//===------------- divmodqi4.S - sint8 div & mod --------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// As described at
+// https://gcc.gnu.org/wiki/avr-gcc#Exceptions_to_the_Calling_Convention, the
+// prototype is `struct {sint8, sint8}  __divmodqi4(sint8, sint8)`.
+// The sint8 quotient is returned via R24, and the sint8 remainder is returned
+// via R25, while registers R23/Rtmp and bit T in SREG are clobbered.
+//
+//===----------------------------------------------------------------------===//
+
+  .text
+  .align 2
+
+#ifdef __AVR_TINY__
+  .set __tmp_reg__, 16
+#else
+  .set __tmp_reg__, 0
+#endif
+
+  .globl __divmodqi4
+  .type  __divmodqi4, @function
+
+__divmodqi4:
+  bst     r24, 7
+  mov     __tmp_reg__, r24
+  eor     __tmp_reg__, r22
+  sbrc    r24, 7
+  neg     r24
+  sbrc    r22, 7
+  neg     r22
+  rcall   __udivmodqi4   ; Call __udivmodqi4 to do real calculation.
+  brtc    __divmodqi4_1
+  neg     r25
+
+__divmodqi4_1:
+  sbrc    __tmp_reg__, 7
+  neg     r24
+  ret                    ; Return quotient via R24 and remainder via R25.

compiler-rt/lib/builtins/avr/udivmodhi4.S

+//===------------ udivmodhi4.S - uint16 div & mod -------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// As described at
+// https://gcc.gnu.org/wiki/avr-gcc#Exceptions_to_the_Calling_Convention, the
+// prototype is `struct {uint16, uint16}  __udivmodhi4(uint16, uint16)`.
+// The uint16 quotient is returned via R23:R22, and the uint16 remainder is
+// returned via R25:R24, while R21/R26/R27 are clobbered.
+//
+//===----------------------------------------------------------------------===//
+
+  .text
+  .align 2
+
+  .globl __udivmodhi4
+  .type  __udivmodhi4, @function
+
+__udivmodhi4:
+  sub     r26, r26
+  sub     r27, r27           ; Initialize the remainder to zero.
+  ldi     r21, 17            ; Only loop 16 rounds for uint16.
+
+__udivmodhi4_loop:
+  adc     r24, r24
+  adc     r25, r25
+  dec     r21
+  breq    __udivmodhi4_end
+  adc     r26, r26
+  adc     r27, r27
+  cp      r26, r22
+  cpc     r27, r23           ; Compare with the divisor.
+  brcs    __udivmodhi4_loop
+  sub     r26, r22
+  sbc     r27, r23           ; Subtract the divisor.
+  rjmp    __udivmodhi4_loop
+
+__udivmodhi4_end:
+  com     r24
+  com     r25
+  mov     r22, r24
+  mov     r23, r25           ; The quotient is returned in R23:R22.
+  mov     r24, r26
+  mov     r25, r27           ; The remainder is returned in in R25:R24.
+  ret

compiler-rt/lib/builtins/avr/udivmodqi4.S

+//===------------ udivmodqi4.S - uint8 div & mod --------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// As described at
+// https://gcc.gnu.org/wiki/avr-gcc#Exceptions_to_the_Calling_Convention, the
+// prototype is `struct {uint8, uint8} __udivmodqi4(uint8, uint8)`.
+// The uint8 quotient is returned via R24, and the uint8 remainder is returned
+// via R25, while R23 is clobbered.
+//
+//===----------------------------------------------------------------------===//
+
+  .text
+  .align 2
+
+  .globl __udivmodqi4
+  .type  __udivmodqi4, @function
+
+__udivmodqi4:
+  sub     r25, r25           ; Initialize the remainder to zero.
+  ldi     r23, 9             ; Only loop 8 rounds for uint8.
+
+__udivmodqi4_loop:
+  adc     r24, r24
+  dec     r23
+  breq    __udivmodqi4_end
+  adc     r25, r25
+  cp      r25, r22           ; Compare with the divisor.
+  brcs    __udivmodqi4_loop
+  sub     r25, r22           ; Subtract the divisor.
+  rjmp    __udivmodqi4_loop
+
+__udivmodqi4_end:
+  com     r24                ; The uint8 quotient is returned via R24.
+  ret                        ; The uint8 remainder is returned via R25.