[compiler-rt][builtins] Add several helper functions for AVR

[benshi001]

Summary

__mulqi3: int8 multiplication
__mulhi3: int16 multiplication
_exit   : golobal terminator

[benshi001]

Build libclang_rt.builtins-avr.a for target AVR, which contains math functions, such as mulsi3, divmodsi4, mulsf3, ...

[aykevl]

What about chip families other than avr2 (the default)? Some have a different PC pointer size (1-3 bytes, therefore affecting the ABI), some have different instructions, etc.

[benshi001]

In D123200#3436043, @aykevl wrote:

What about chip families other than avr2 (the default)? Some have a different PC pointer size (1-3 bytes, therefore affecting the ABI), some have different instructions, etc.

There are two options CMAKE_CXX_FLAGS and CMAKE_C_FLAGS can be specified when doing cmake against compiler-rt, we can specify -mmcu=avrX via them.

Since libgcc-avr has unique source code but built/distributed into several different libgcc.a files with different instruction set, I expect compiler-rt would be done in the way.

And of cource this patch just is an initial support, we still need much more patches to make it fully functional.

[MaskRay]

Initial support for a new target has a high standard. It needs to show decent support, otherwise it may just invite fixups which may in the end waste review resources.
Showing that these files buildable is far from enough. You'd need to show that the run-time tests actually work.

[MaskRay]

clang/lib/Basic/Targets/AVR.cpp

380 ↗

(On Diff #420772)

The clang preprocessor changes are unrelated to compiler-rt and should be contribute separated with tests.

[benshi001]

clang/lib/Basic/Targets/AVR.cpp

380 ↗

(On Diff #420772)

I have created another patch as you suggested, thanks.

https://reviews.llvm.org/D123567

[benshi001]

In D123200#3444520, @MaskRay wrote:

Initial support for a new target has a high standard. It needs to show decent support, otherwise it may just invite fixups which may in the end waste review resources.
Showing that these files buildable is far from enough. You'd need to show that the run-time tests actually work.

Could you please tell me more about show that the run-time tests actually work ? AVR is 8-bit MCU with any OS, so I just want some math functions in compiler-rt/lib/builtins, to avoid linking to libgcc.a.

I have checked that there are tests at compiler-rt/test/builtins/Unit/arm, and I guess them to be run on a ARM host. So I have to make a new directory compiler-rt/test/builtins/Unit/avr with some test cases, and promiss that they can run on an AVR board? (https://www.arduino.cc/en/hardware#boards-1)

[benshi001]

I added three functions

__mulqi3: int8 multiplication
__mulhi3: int16 multiplication
_exit   : golobal terminator

All of them are contained in libgcc and are necessary.

Some key points,

1. The functions are written in the minimal avrtiny instruction set, so they should be compatible for all devices.

2. We build them to higher/upper AVR ELF files by specifying CMAKE_CXX_FLAGS and CMAKE_C_FLAGS when doing cmake.

3. I have refered to libgcc, but not simply copy. Actually my implementation is shorter than libgcc's, but may cost more cycles. However this is something about tradeoff.

4. I have tested against avr hardware multiplier, the results are all the same on ArduinoNano (atmega328).

5. My test program locates at https://github.com/benshi001/avr-test/blob/main/mul_int16_int8.ino, I only added 300 pairs of random numbers as test cases, due to the limitation of my device (atmega328 has only 2KB SRAM, more test cases will lead to too large data section). Acutally I have tested 900 pairs.

[MaskRay]

compiler-rt/cmake/Modules/CompilerRTUtils.cmake

172

Keep the list in alphabetical order. Move avr to the beginning. Ignore some entries which are unordered.

218

Keep the list in alphabetical order. Move avr to the beginning. Ignore some entries which are unordered.

compiler-rt/cmake/builtin-config-ix.cmake

56

Keep the list in alphabetical order. Move avr to the beginning. Ignore some entries which are unordered.

compiler-rt/lib/builtins/CMakeLists.txt

678

Keep the *_SOURCES in alphabetical order. Move avr to the beginning. Ignore some entries which are unordered.

[benshi001]

compiler-rt/lib/builtins/CMakeLists.txt

678

I will fix all your concerns about "alphabetical order" when committing.

[aykevl]

@benshi001 I have been looking through the GCC code and I think avr-gcc also has a special calling convention for many other functions, including __mulqi3 and __mulhi3.

Source:

1. I think this is where the ABI is specified in the compiler: https://github.com/gcc-mirror/gcc/blob/releases/gcc-5.4.0/gcc/config/avr/avr.md#L1543-L1549 You can see that it multiplies R24 with R22 and stores the result in R24, and clobbers R22 in the process. But no other registers.
2. In this code sample, avr-gcc doesn't save char c (r20) across the __mulqi3 and __mulhi3 calls, which is normally call-clobbered.

Therefore, I think we need to be a bit more careful with defining these AVR builtins and check the ABI in avr-gcc first.
Also, we can make use of this and optimize the AVR backend more (you can see that the Clang generated code is much worse than avr-gcc in the above examples).

[benshi001]

In D123200#3495356, @aykevl wrote:

@benshi001 I have been looking through the GCC code and I think avr-gcc also has a special calling convention for many other functions, including __mulqi3 and __mulhi3.

Source:

1. I think this is where the ABI is specified in the compiler: https://github.com/gcc-mirror/gcc/blob/releases/gcc-5.4.0/gcc/config/avr/avr.md#L1543-L1549 You can see that it multiplies R24 with R22 and stores the result in R24, and clobbers R22 in the process. But no other registers.
2. In this code sample, avr-gcc doesn't save char c (r20) across the __mulqi3 and __mulhi3 calls, which is normally call-clobbered.

Therefore, I think we need to be a bit more careful with defining these AVR builtins and check the ABI in avr-gcc first.
Also, we can make use of this and optimize the AVR backend more (you can see that the Clang generated code is much worse than avr-gcc in the above examples).

Let us discuss that at https://github.com/llvm/llvm-project/issues/55279

compiler-rt/cmake/Modules/CompilerRTUtils.cmake

elseif("${COMPILER_RT_DEFAULT_TARGET_ARCH}" STREQUAL "${arch}" AND
          COMPILER_RT_HAS_EXPLICIT_DEFAULT_TARGET_TRIPLE)
     # Bail out if we cannot target the architecture we plan to test.
     message(FATAL_ERROR "Cannot compile for ${arch}:\n${TARGET_${arch}_OUTPUT}")
   endif()
 endmacro()
 
 macro(detect_target_arch)
   check_symbol_exists(__arm__ "" __ARM)
+  check_symbol_exists(__AVR__ "" __AVR)
   check_symbol_exists(__aarch64__ "" __AARCH64)
   check_symbol_exists(__x86_64__ "" __X86_64)
   check_symbol_exists(__i386__ "" __I386)
   check_symbol_exists(__mips__ "" __MIPS)
   check_symbol_exists(__mips64__ "" __MIPS64)
   check_symbol_exists(__powerpc__ "" __PPC)
   check_symbol_exists(__powerpc64__ "" __PPC64)
   check_symbol_exists(__powerpc64le__ "" __PPC64LE)
   check_symbol_exists(__riscv "" __RISCV)
   check_symbol_exists(__s390x__ "" __S390X)
   check_symbol_exists(__sparc "" __SPARC)
   check_symbol_exists(__sparcv9 "" __SPARCV9)
   check_symbol_exists(__wasm32__ "" __WEBASSEMBLY32)
   check_symbol_exists(__wasm64__ "" __WEBASSEMBLY64)
   check_symbol_exists(__ve__ "" __VE)
   if(__ARM)
     add_default_target_arch(arm)
+  elseif(__AVR)
+    add_default_target_arch(avr)
   elseif(__AARCH64)
     add_default_target_arch(aarch64)
   elseif(__X86_64)
     if(CMAKE_SIZEOF_VOID_P EQUAL "4")
       add_default_target_arch(x32)
     elseif(CMAKE_SIZEOF_VOID_P EQUAL "8")
       add_default_target_arch(x86_64)
     else()
macro(detect_target_arch)
   elseif(__SPARC)
     add_default_target_arch(sparc)
   elseif(__WEBASSEMBLY32)
     add_default_target_arch(wasm32)
   elseif(__WEBASSEMBLY64)
     add_default_target_arch(wasm64)
   elseif(__VE)
     add_default_target_arch(ve)
   endif()
 endmacro()
 
 function(get_compiler_rt_root_source_dir ROOT_DIR_VAR)
   # Compute the path to the root of the Compiler-RT source tree
   # regardless of how the project was configured.
   #
   # This function is useful because using `${CMAKE_SOURCE_DIR}`
   # is error prone due to the numerous ways Compiler-RT can be

compiler-rt/cmake/base-config-ix.cmake

elseif(NOT APPLE) # Supported archs for Apple platforms are generated later
     elseif("${COMPILER_RT_DEFAULT_TARGET_ARCH}" MATCHES "arm")
       if(WIN32)
         test_target_arch(arm "" "" "")
       else()
         test_target_arch(arm "" "-march=armv7-a" "-mfloat-abi=soft")
         test_target_arch(armhf "" "-march=armv7-a" "-mfloat-abi=hard")
         test_target_arch(armv6m "" "-march=armv6m" "-mfloat-abi=soft")
       endif()
+    elseif("${COMPILER_RT_DEFAULT_TARGET_ARCH}" MATCHES "avr")
+      test_target_arch(avr "__AVR__" "--target=avr")
     elseif("${COMPILER_RT_DEFAULT_TARGET_ARCH}" MATCHES "aarch32")
       test_target_arch(aarch32 "" "-march=armv8-a")
     elseif("${COMPILER_RT_DEFAULT_TARGET_ARCH}" MATCHES "aarch64")
       test_target_arch(aarch64 "" "-march=armv8-a")
     elseif("${COMPILER_RT_DEFAULT_TARGET_ARCH}" MATCHES "riscv32")
       test_target_arch(riscv32 "" "")
     elseif("${COMPILER_RT_DEFAULT_TARGET_ARCH}" MATCHES "riscv64")
       test_target_arch(riscv64 "" "")

compiler-rt/cmake/builtin-config-ix.cmake

 builtin_check_c_compiler_source(COMPILER_RT_HAS_ASM_LSE
 "
 asm(\".arch armv8-a+lse\");
 asm(\"cas w0, w1, [x2]\");
 ")
 
 set(ARM64 aarch64)
 set(ARM32 arm armhf armv6m armv7m armv7em armv7 armv7s armv7k armv8m.main armv8.1m.main)
+set(AVR avr)
 set(HEXAGON hexagon)
 set(X86 i386)
 set(X86_64 x86_64)
 set(MIPS32 mips mipsel)
 set(MIPS64 mips64 mips64el)
 set(PPC32 powerpc powerpcspe)
 set(PPC64 powerpc64 powerpc64le)
 set(RISCV32 riscv32)
 set(RISCV64 riscv64)
 set(SPARC sparc)
 set(SPARCV9 sparcv9)
 set(WASM32 wasm32)
 set(WASM64 wasm64)
 set(VE ve)
 
 if(APPLE)
   set(ARM64 arm64 arm64e)
   set(ARM32 armv7 armv7k armv7s)
   set(X86_64 x86_64 x86_64h)
 endif()
 
 set(ALL_BUILTIN_SUPPORTED_ARCH
-  ${X86} ${X86_64} ${ARM32} ${ARM64}
+  ${X86} ${X86_64} ${ARM32} ${ARM64} ${AVR}
   ${HEXAGON} ${MIPS32} ${MIPS64} ${PPC32} ${PPC64}
   ${RISCV32} ${RISCV64} ${SPARC} ${SPARCV9}
   ${WASM32} ${WASM64} ${VE})
 
 include(CompilerRTUtils)
 include(CompilerRTDarwinUtils)
 
 if(APPLE)

compiler-rt/cmake/config-ix.cmake

 # platform. We use the results of these tests to build only the various target
 # runtime libraries supported by our current compilers cross-compiling
 # abilities.
 set(SIMPLE_SOURCE ${CMAKE_BINARY_DIR}${CMAKE_FILES_DIRECTORY}/simple.cc)
 file(WRITE ${SIMPLE_SOURCE} "#include <stdlib.h>\n#include <stdio.h>\nint main() { printf(\"hello, world\"); }\n")
 
 # Detect whether the current target platform is 32-bit or 64-bit, and setup
 # the correct commandline flags needed to attempt to target 32-bit and 64-bit.
+# AVR and MSP430 are omitted since they have 16-bit pointers.
 if (NOT CMAKE_SIZEOF_VOID_P EQUAL 4 AND
-    NOT CMAKE_SIZEOF_VOID_P EQUAL 8)
+    NOT CMAKE_SIZEOF_VOID_P EQUAL 8 AND
+    NOT ${arch} MATCHES "avr|msp430")
   message(FATAL_ERROR "Please use architecture with 4 or 8 byte pointers.")
 endif()
 
 test_targets()
 
 # Returns a list of architecture specific target cflags in @out_var list.
 function(get_target_flags_for_arch arch out_var)
   list(FIND COMPILER_RT_SUPPORTED_ARCH ${arch} ARCH_INDEX)

compiler-rt/lib/builtins/CMakeLists.txt

 
 # macho_embedded archs
 set(armv6m_SOURCES ${thumb1_SOURCES})
 set(armv7m_SOURCES ${arm_SOURCES})
 set(armv7em_SOURCES ${arm_SOURCES})
 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
+)
+
 # hexagon arch
 set(hexagon_SOURCES
   hexagon/common_entry_exit_abi1.S
   hexagon/common_entry_exit_abi2.S
   hexagon/common_entry_exit_legacy.S
   hexagon/dfaddsub.S
   hexagon/dfdiv.S
   hexagon/dffma.S

 )
 
 set(ve_SOURCES
   ve/grow_stack.S
   ve/grow_stack_align.S
   ${GENERIC_TF_SOURCES}
   ${GENERIC_SOURCES})
 
 add_custom_target(builtins)
 set_target_properties(builtins PROPERTIES FOLDER "Compiler-RT Misc")
 
 if (APPLE)
   add_subdirectory(Darwin-excludes)
   add_subdirectory(macho_embedded)
   darwin_add_builtin_libraries(${BUILTIN_SUPPORTED_OS})
 else ()
   set(BUILTIN_CFLAGS "")

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

+//===------------ exit.S - global terminator for AVR ----------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+  .text
+  .align 2
+
+  .globl _exit
+  .type  _exit, @function
+
+_exit:
+  cli                 ; Disable all interrupts.
+__stop_program:
+  rjmp __stop_program ; Fall into an infinite loop.

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

+//===------------ mulhi3.S - int16 multiplication -------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// The corresponding C code is something like:
+//
+// int __mulhi3(int A, int B) {
+//   int S = 0;
+//   while (A != 0) {
+//     if (A & 1)
+//       S += B;
+//     A = ((unsigned int) A) >> 1;
+//     B <<= 1;
+//   }
+//   return S;
+// }
+//
+//===----------------------------------------------------------------------===//
+
+  .text
+  .align 2
+
+  .globl __mulhi3
+  .type  __mulhi3, @function
+
+__mulhi3:
+  eor    r28, r28
+  eor    r20, r20
+  eor    r21, r21         ; Initialize the result to 0: `S = 0;`.
+
+__mulhi3_loop:
+  cp     r24, r28
+  cpc    r25, r28         ; `while (A != 0) { ... }`
+  breq   __mulhi3_end     ; End the loop if A is 0.
+
+  mov    r29, r24
+  andi   r29, 1           ; `if (A & 1) { ... }`
+  breq   __mulhi3_loop_a  ; Omit the accumulation (`S += B;`) if  A's LSB is 0.
+
+  add    r20, r22
+  adc    r21, r23         ; Do the accumulation: `S += B;`.
+
+__mulhi3_loop_a:
+  lsr    r25
+  ror    r24              ; `A = ((unsigned int) A) >> 1;`.
+  lsl    r22
+  rol    r23              ; `B <<= 1;`
+
+  rjmp   __mulhi3_loop
+
+__mulhi3_end:
+  mov    r24, r20
+  mov    r25, r21
+  ret

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

+//===------------ mulhi3.S - int8 multiplication --------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// The corresponding C code is something like:
+//
+// int __mulqi3(char A, char B) {
+//   return __mulhi3((int) A, (int) B);
+// }
+//
+//===----------------------------------------------------------------------===//
+
+  .text
+  .align 2
+
+  .globl __mulqi3
+  .type  __mulqi3, @function
+
+__mulqi3:
+  mov    r25, r24
+  lsl    r25
+  sbc    r25, r25         ; Promote A from char to int: `(int) A`.
+  mov    r23, r22
+  lsl    r23
+  sbc    r23, r23         ; Promote B from char to int: `(int) B`.
+  rcall  __mulhi3         ; `__mulhi3((int) A, (int) B);`.
+  ret