[AArch64] Suboptimal code for multiplication by certain constants

[Kmeakin]

For some constants, GCC is able to generate sequences of add where LLVM generates mul. I have checked all constants between 1 and 100 (https://godbolt.org/z/rxej44fGj):

For all of the examples below(11, 13, 19, 21, 25, 27, 35, 37, 41, 49, 51, 69, 73, 81, 85), LLVM generates

mulK:
        mov     w8, K
        mul     w0, w0, w8
        ret

mul11:
        add     w1, w0, w0, lsl 2
        add     w0, w0, w1, lsl 1
        ret

mul13:
        add     w1, w0, w0, lsl 1
        add     w0, w0, w1, lsl 2
        ret

mul19:
        add     w1, w0, w0, lsl 3
        add     w0, w0, w1, lsl 1
        ret

mul21:
        add     w1, w0, w0, lsl 2
        add     w0, w0, w1, lsl 2
        ret

mul25:
        add     w0, w0, w0, lsl 2
        add     w0, w0, w0, lsl 2
        ret

mul27:
        add     w0, w0, w0, lsl 1
        add     w0, w0, w0, lsl 3
        ret

mul35:
        add     w1, w0, w0, lsl 4
        add     w0, w0, w1, lsl 1
        ret

mul37:
        add     w1, w0, w0, lsl 3
        add     w0, w0, w1, lsl 2
        ret

mul41:
        add     w1, w0, w0, lsl 2
        add     w0, w0, w1, lsl 3
        ret

mul49:
        add     w1, w0, w0, lsl 1
        add     w0, w0, w1, lsl 4
        ret

mul51:
        add     w0, w0, w0, lsl 1
        add     w0, w0, w0, lsl 4
        ret

mul69:
        add     w1, w0, w0, lsl 4
        add     w0, w0, w1, lsl 2
        ret

mul73:
        add     w1, w0, w0, lsl 3
        add     w0, w0, w1, lsl 3
        ret

mul81:
        add     w0, w0, w0, lsl 3
        add     w0, w0, w0, lsl 3
        ret

mul85:
        add     w0, w0, w0, lsl 2
        add     w0, w0, w0, lsl 4
        ret

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Karl Meakin (Kmeakin)

For some constants, GCC is able to generate sequences of `add` where LLVM generates `mul`. I have checked all constants between 1 and 100 (https://godbolt.org/z/rxej44fGj):

For all of the examples below(11, 13, 19, 21, 25, 27, 35, 37, 41, 49, 51, 69, 73, 81, 85), LLVM generates

mulK:
        mov     w8, K
        mul     w0, w0, w8
        ret

mul11:
        add     w1, w0, w0, lsl 2
        add     w0, w0, w1, lsl 1
        ret

mul13:
        add     w1, w0, w0, lsl 1
        add     w0, w0, w1, lsl 2
        ret

mul19:
        add     w1, w0, w0, lsl 3
        add     w0, w0, w1, lsl 1
        ret

mul21:
        add     w1, w0, w0, lsl 2
        add     w0, w0, w1, lsl 2
        ret

mul25:
        add     w0, w0, w0, lsl 2
        add     w0, w0, w0, lsl 2
        ret

mul27:
        add     w0, w0, w0, lsl 1
        add     w0, w0, w0, lsl 3
        ret

mul35:
        add     w1, w0, w0, lsl 4
        add     w0, w0, w1, lsl 1
        ret

mul37:
        add     w1, w0, w0, lsl 3
        add     w0, w0, w1, lsl 2
        ret

mul41:
        add     w1, w0, w0, lsl 2
        add     w0, w0, w1, lsl 3
        ret

mul49:
        add     w1, w0, w0, lsl 1
        add     w0, w0, w1, lsl 4
        ret

mul51:
        add     w0, w0, w0, lsl 1
        add     w0, w0, w0, lsl 4
        ret

mul69:
        add     w1, w0, w0, lsl 4
        add     w0, w0, w1, lsl 2
        ret

mul73:
        add     w1, w0, w0, lsl 3
        add     w0, w0, w1, lsl 3
        ret

mul81:
        add     w0, w0, w0, lsl 3
        add     w0, w0, w0, lsl 3
        ret

mul85:
        add     w0, w0, w0, lsl 2
        add     w0, w0, w0, lsl 4
        ret

[dtcxzyw]

I believe #88791 and its follow-up patches will fix this :)

[efriedma-quic]

We have to be a bit careful weighing these optimizations; for certain combinations of target CPU/shift amount/register width, two add-with-shift instructions are actually more expensive than a multiply.

[efriedma-quic]

Also, gcc misses some combinations, for example:

#include <stdint.h>
typedef uint32_t u32;
u32 a(u32 x, u32 y) { return x -y*4; }
u32 b(u32 x) { return x * -7;}
u32 c(u32 x) { return a(x, b(x)); }

[davemgreen]

Do we have any evidence that these are better as add+shift? As far as I understand GCC optimized it this way because older cores had slower mul and faster add+lsl, but that has changed in more recent cores and mul is now usually relatively quick.

[vfdff]

the all above numbers listed (11, 13, 19, 21, 25, 27, 35, 37, 41, 49, 51, 69, 73, 81, 85) can be optimized With FeatureALULSLFast

• 11 = (((1<<2) + 1) << 1) + 1
• 13 = (((1<<1) + 1) << 2) + 1
• 19 = (((1<<3) + 1) << 1) + 1
• 21 = (((1<<2) + 1) << 2) + 1
• 25 = ((1<<2) + 1) * ((1<<2) + 1)
• 27 = ((1<<1) + 1) * ((1<<3) + 1)
• 35 = ((1<<1) + 1) * ((1<<3) + 1)
• ...

[vfdff]

Also, gcc misses some combinations, for example:

#include <stdint.h>
typedef uint32_t u32;
u32 a(u32 x, u32 y) { return x -y*4; }
u32 b(u32 x) { return x * -7;}
u32 c(u32 x) { return a(x, b(x)); }

This case is also not supported by llvm now