[AVR] Implement `__mulsi3` in compiler-rt/builtins

[benshi001]

__mulsi3 is needed for int32 multiplication, and called by __addsf3/__subsf3/__mulsf3/__divsf3.

__divmodsi4 is already implemented as common code.

[aykevl]

__mulsi3 is needed for int32 multiplication, and called by __addsf3/__subsf3/__mulsf3/__divsf3.

I have an implementation in Go that I can easily convert to C. Or do you have one already?

__divmodsi4 is already implemented as common code.

Unfortunately it is incorrect. The signature is different. AVR expects the following signature:

struct {int32_t, int32_t} __divmodsi4(int32_t, int32_t);

It can be implemented this way (untested, not optimized):

uint64_t  __udivmodsi4(uint32_t a, uint32_t b) {
    uint32_t div = __udivsi3(a, b);
    uint32_t rem = a - (div * b);
    return ((uint64_t)div) | (((uint64_t)rem)<<32);
}

And similarly for __divmodsi4.

[benshi001]

No, I have not implemented all int32 helper functions. I will appreciate if you can submit your implementation of __mulsi3/__divmodsi4/udivmodsi4.

[benshi001]

As @aykevl mentioned in https://reviews.llvm.org/D123200

@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]

I have checked with libgcc's code,

1. for __mulhi3,

;;; R25:R24 = R23:R22 * R25:R24
;;; (C1:C0) = (A1:A0) * (B1:B0)
;;; Clobbers: __tmp_reg__, R21..R23

2. For __mulqi3

r24 is used for return result, r22 and __tmp_reg__ are clobbered.

So both __mulqi3 and __mulhi3 need to be refactored.

[benshi001]

I have refactored them at https://reviews.llvm.org/D125077

[aykevl]

I looked at __mulsi3 today. There are two different versions:

1. For parts that support mul: there is a version with a special calling convention that only clobbers R26:R27, SREG, and R0.
2. For parts that don't support mul: these use a generic version that could be implemented in C but is probably more efficient to implement in assembly. I have an assembly version already. Unfortunately, it does not adhere to the calling convention required for parts with mul support.

To properly support __mulsi3, we need to have definitions like __AVR_HAVE_MUL__.

[aykevl]

I have implemented __mulsi3 here: https://reviews.llvm.org/D137581
It's slow (especially on chips with mul support) but it should work on all chips except avrtiny.

[aykevl]

And now for __udivmodsi4 and __divmodsi4: https://reviews.llvm.org/D138166