[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

21–25 ↗

(On Diff #425998)

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

21–25 ↗

(On Diff #425998)

changed to __tmp_reg__

[aykevl]

Looks good to me.

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

21–25 ↗

(On Diff #425998)

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

21–25 ↗

(On Diff #425998)

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

[benshi001]

.

compiler-rt/lib/builtins/CMakeLists.txt

   avr/mulqi3.S
   avr/mulhi3.S
   avr/exit.S
+  avr/udivmodhi4.S
 )
 
 add_custom_target(builtins)

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,
+// R23:R22 holds the uint16 quotient, and R25:R24 holds the uint16 remainder,
+// 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 cycles 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