[AArch64] Avoid materialising bitwise immediate arguments by decomposing into 2 arguments

[Kmeakin]

The ORR, AND and EOR instructions only accept immediates in a specific form. For immediates that do not fit in this form, we have to materialise it with MOV+MOVK. However, sometimes instead of materialising, we could decompose the immediate into two immediates that are accepted.

C++ example: https://godbolt.org/z/vzzaTzseE
(The volatile keyword is required to prevent LLVM performing constant folding)
alive proof: https://alive2.llvm.org/ce/z/NmrTqz

#include <cstdint>

typedef uint32_t u32;

u32 src1(u32 x) { return x | 0xF0'00'00'F0; }
u32 tgt1(volatile u32 x) {
    x |= 0xF0'00'00'0;
    x |= 0x00'00'00'F0;
    return x;
}

u32 src2(u32 x) { return x & 0xF0'00'00'F0; }
u32 tgt2(volatile u32 x) {
    x &= 0xF0'00'00'FF;
    x &= 0xFF'FF'FF'F0;
    return x;
}

u32 src3(u32 x) { return x ^ 0xF0'00'00'F0; }
u32 tgt3(volatile u32 x) {
    x ^= 0xF0'00'00'00;
    x ^= 0x00'00'00'F0;
    return x;
}

src1(unsigned int):
        mov     w8, #240
        movk    w8, #61440, lsl #16
        orr     w0, w0, w8
        ret

tgt1(unsigned int):
        sub     sp, sp, #16
        str     w0, [sp, #12]
        ldr     w8, [sp, #12]
        orr     w8, w8, #0xf000000
        str     w8, [sp, #12]
        ldr     w8, [sp, #12]
        orr     w8, w8, #0xf0
        str     w8, [sp, #12]
        ldr     w0, [sp, #12]
        add     sp, sp, #16
        ret

src2(unsigned int):
        and     w8, w0, #0xfffffff0
        and     w0, w8, #0xf00000ff
        ret

tgt2(unsigned int):
        sub     sp, sp, #16
        str     w0, [sp, #12]
        ldr     w8, [sp, #12]
        and     w8, w8, #0xf00000ff
        str     w8, [sp, #12]
        ldr     w8, [sp, #12]
        and     w8, w8, #0xfffffff0
        str     w8, [sp, #12]
        ldr     w0, [sp, #12]
        add     sp, sp, #16
        ret

src3(unsigned int):
        mov     w8, #240
        movk    w8, #61440, lsl #16
        eor     w0, w0, w8
        ret

tgt3(unsigned int):
        sub     sp, sp, #16
        str     w0, [sp, #12]
        ldr     w8, [sp, #12]
        eor     w8, w8, #0xf0000000
        str     w8, [sp, #12]
        ldr     w8, [sp, #12]
        eor     w8, w8, #0xf0
        str     w8, [sp, #12]
        ldr     w0, [sp, #12]
        add     sp, sp, #16
        ret

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Karl Meakin (Kmeakin)

The `ORR`, `AND` and `EOR` instructions only accept immediates in a specific form. For immediates that do not fit in this form, we have to materialise it with `MOV+MOVK`. However, sometimes instead of materialising, we could decompose the immediate into two immediates that are accepted:

https://godbolt.org/z/oYnbYj9We
(The volatile keyword is required to prevent LLVM performing constant folding)

#include <cstdint>

typedef uint32_t u32;

u32 src1(u32 x) { return x | 0xF0'00'00'F0; }
u32 tgt1(volatile u32 x) {
    x |= 0xF0'00'00'0;
    x |= 0x00'00'00'F0;
    return x;
}

u32 src2(u32 x) { return x & 0xF0'00'00'F0; }
u32 tgt2(volatile u32 x) {
    x &= 0xF0'00'00'FF;
    x &= 0xFF'FF'FF'F0;
    return x;
}

u32 src3(u32 x) { return x ^ 0xF0'00'00'F0; }
u32 tgt3(volatile u32 x) {
    x ^= 0xF0'00'00'00;
    x ^= 0x00'00'00'F0;
    return x;
}

src1(unsigned int):
        mov     w8, #<!-- -->240
        movk    w8, #<!-- -->61440, lsl #<!-- -->16
        orr     w0, w0, w8
        ret

tgt1(unsigned int):
        sub     sp, sp, #<!-- -->16
        str     w0, [sp, #<!-- -->12]
        ldr     w8, [sp, #<!-- -->12]
        orr     w8, w8, #<!-- -->0xf000000
        str     w8, [sp, #<!-- -->12]
        ldr     w8, [sp, #<!-- -->12]
        orr     w8, w8, #<!-- -->0xf0
        str     w8, [sp, #<!-- -->12]
        ldr     w0, [sp, #<!-- -->12]
        add     sp, sp, #<!-- -->16
        ret

src2(unsigned int):
        and     w8, w0, #<!-- -->0xfffffff0
        and     w0, w8, #<!-- -->0xf00000ff
        ret

tgt2(unsigned int):
        sub     sp, sp, #<!-- -->16
        str     w0, [sp, #<!-- -->12]
        ldr     w8, [sp, #<!-- -->12]
        and     w8, w8, #<!-- -->0xf00000ff
        str     w8, [sp, #<!-- -->12]
        ldr     w8, [sp, #<!-- -->12]
        and     w8, w8, #<!-- -->0xfffffff0
        str     w8, [sp, #<!-- -->12]
        ldr     w0, [sp, #<!-- -->12]
        add     sp, sp, #<!-- -->16
        ret

src3(unsigned int):
        mov     w8, #<!-- -->240
        movk    w8, #<!-- -->61440, lsl #<!-- -->16
        eor     w0, w0, w8
        ret

tgt3(unsigned int):
        sub     sp, sp, #<!-- -->16
        str     w0, [sp, #<!-- -->12]
        ldr     w8, [sp, #<!-- -->12]
        eor     w8, w8, #<!-- -->0xf0000000
        str     w8, [sp, #<!-- -->12]
        ldr     w8, [sp, #<!-- -->12]
        eor     w8, w8, #<!-- -->0xf0
        str     w8, [sp, #<!-- -->12]
        ldr     w0, [sp, #<!-- -->12]
        add     sp, sp, #<!-- -->16
        ret

[rj-jesus]

I think this could be done in AArch64MIPeepholeOpt, where there's already infrastructure to split MOVi32imm + ANDWrr into ANDWri + ANDWri (and likewise for 64-bit).

Besides EOR and ORR, I think this should also be doable for ANDS.

[davemgreen]

There are some details in https://reviews.llvm.org/D109963 as to why it was done in the peephole optimizer, and how it is not always beneficial (in loops for example).

[rj-jesus]

Thanks for the link, do you think it's worth pursuing this, @davemgreen? From skimming through the comments I got the impression that most concerns regarding loops were addressed by adding loop invariance checks, for example, but maybe I misunderstood.

[davemgreen]

Yeah I should think the code in the peephole pass is OK and can be expanded to the other kinds. It was apparently useful enough to add AND (and ADD), presumably the other would behave similarly performance-wise. It's less instructions overall but a slightly longer critical path.

[rj-jesus]

Thanks, that makes sense. In that case I'll have a look at fixing the mask computation logic for EOR and ORR in #149095.