Bad codegen for boolean reductions on thumbv7neon

[hsivonen]

Using cargo build --release --target thumbv7neon-unknown-linux-gnueabihf:

With packed_simd_2, this:

#[no_mangle]
#[inline(never)]
fn packed_any(s: m8x16) -> bool {
    s.any()
}

compiles to this:

00003e66 <packed_any>:
    3e66:       f960 0acf       vld1.64 {d16-d17}, [r0]
    3e6a:       ff40 0aa1       vpmax.u8        d16, d16, d17
    3e6e:       ec51 0b30       vmov    r0, r1, d16
    3e72:       4308            orrs    r0, r1
    3e74:       bf18            it      ne
    3e76:       2001            movne   r0, #1
    3e78:       4770            bx      lr
        ...

With core_simd, this:

#[no_mangle]
#[inline(never)]
fn core_any(s: mask8x16) -> bool {
    s.any()
}

compiles to this:

00003e66 <core_any>:
    3e66:       b5f0            push    {r4, r5, r6, r7, lr}
    3e68:       f960 0acf       vld1.64 {d16-d17}, [r0]
    3e6c:       eed0 0bb0       vmov.u8 r0, d16[1]
    3e70:       eed0 1b90       vmov.u8 r1, d16[0]
    3e74:       eed0 2bd0       vmov.u8 r2, d16[2]
    3e78:       eed0 3bf0       vmov.u8 r3, d16[3]
    3e7c:       eef0 cb90       vmov.u8 ip, d16[4]
    3e80:       eef0 ebb0       vmov.u8 lr, d16[5]
    3e84:       eef0 4bd0       vmov.u8 r4, d16[6]
    3e88:       eef0 7bf0       vmov.u8 r7, d16[7]
    3e8c:       eed1 5bf0       vmov.u8 r5, d17[3]
    3e90:       eef1 6b90       vmov.u8 r6, d17[4]
    3e94:       4308            orrs    r0, r1
    3e96:       eed1 1b90       vmov.u8 r1, d17[0]
    3e9a:       4310            orrs    r0, r2
    3e9c:       eed1 2bb0       vmov.u8 r2, d17[1]
    3ea0:       4318            orrs    r0, r3
    3ea2:       eed1 3bd0       vmov.u8 r3, d17[2]
    3ea6:       ea40 000c       orr.w   r0, r0, ip
    3eaa:       ea40 000e       orr.w   r0, r0, lr
    3eae:       4320            orrs    r0, r4
    3eb0:       eef1 4bb0       vmov.u8 r4, d17[5]
    3eb4:       4338            orrs    r0, r7
    3eb6:       eef1 7bd0       vmov.u8 r7, d17[6]
    3eba:       4308            orrs    r0, r1
    3ebc:       eef1 1bf0       vmov.u8 r1, d17[7]
    3ec0:       4310            orrs    r0, r2
    3ec2:       4318            orrs    r0, r3
    3ec4:       4328            orrs    r0, r5
    3ec6:       4330            orrs    r0, r6
    3ec8:       4320            orrs    r0, r4
    3eca:       4338            orrs    r0, r7
    3ecc:       4308            orrs    r0, r1
    3ece:       f000 0001       and.w   r0, r0, #1
    3ed2:       bdf0            pop     {r4, r5, r6, r7, pc}

Additional info

This seriously regresses performance (packed_simd_2 vs. core_simd) for encoding_rs.

Previously when migrating from simd to packed_simd.

Meta

rustc --version --verbose:

rustc 1.55.0-nightly (b1f8e27b7 2021-07-15)
binary: rustc
commit-hash: b1f8e27b74c541d3d555149c8efa4bfe9385cd56
commit-date: 2021-07-15
host: armv7-unknown-linux-gnueabihf
release: 1.55.0-nightly
LLVM version: 12.0.1

stdsimd rev 715f9ac

[calebzulawski]

packed-simd uses specific arm instructions which we wont be able to do (since target_feature doesn't apply to std). stdsimd uses an integer "or" reduction, so unfortunately LLVM doesn't know that the vector must contain only 0 or -1. Perhaps we can add an intrinsic that does a truncation before the reduction and hope that it is smart enough to produce similar code.

[hsivonen]

Doesn't target_feature apply to std even when compiling std? I expected it to work when NEON-availability is part of the target as with thumbv7neon-unknown-linux-gnueabihf and not an application compile-time option.

[calebzulawski]

Good point--i missed the neon in the target. It would work for this particular target, but not for any other arm target that doesn't have neon baked in (even if using the target_feature attribute or compiler flag). I'm guessing other architectures likely see a similar codegen issue, as well.

[programmerjake]

packed-simd uses specific arm instructions which we wont be able to do (since target_feature doesn't apply to std). stdsimd uses an integer "or" reduction, so unfortunately LLVM doesn't know that the vector must contain only 0 or -1. Perhaps we can add an intrinsic that does a truncation before the reduction and hope that it is smart enough to produce similar code.

LLVM produces better code if truncating to i1 first, but it's still waay worse than packed-simd:
https://llvm.godbolt.org/z/3v71P9Wdo

reduce_or:
        vorr    d16, d1, d0
        vzip.8  d16, d17
        vorr    d16, d17, d16
        vmov.u16        r0, d16[0]
        vmov.32 d17[0], r0
        vmov.u16        r0, d16[1]
        vmov.32 d17[1], r0
        vmov.u16        r0, d16[2]
        vmov.32 d18[0], r0
        vmov.u16        r0, d16[3]
        vmov.32 d18[1], r0
        vorr    d16, d18, d17
        vmov.32 r0, d16[0]
        vmov.32 r1, d16[1]
        orr     r0, r1, r0
        and     r0, r0, #1
        bx      lr

[hsivonen]

It would work for this particular target, but not for any other arm target that doesn't have neon baked in (even if using the target_feature attribute or compiler flag).

The thumbv7neon-* targets exist precisely to address this problem: To allow things to perform better than after-the-fact +neon by baking NEON in at std compile time.

[calebzulawski]

We actually use the reduce-or intrinsic which does exceptionally poorly: https://llvm.godbolt.org/z/aEha7dh5b

It would work for this particular target, but not for any other arm target that doesn't have neon baked in (even if using the target_feature attribute or compiler flag).

The thumbv7neon-* targets exist precisely to address this problem: To allow things to perform better than after-the-fact +neon by baking NEON in at std compile time.

Yes, it does, but that doesn't help for anyone who wants to runtime check for neon. It looks to me like this is a case that should be built into the LLVM reduce-or intrinsic for i1. We could partially solve it by bypassing codegen with explicit neon intrinsics, but the subpar LLVM codegen is the root of the problem.

[hsivonen]

Yes, it does, but that doesn't help for anyone who wants to runtime check for neon. It looks to me like this is a case that should be built into the LLVM reduce-or intrinsic for i1.

Ideally, yes, but in the interim, it would be great to have a core_simd level conditionally-compiled implementation the produces the same instructions as the same reduction in simd and in packed_simd.

[calebzulawski]

That's a possibility, but I'm concerned about special casing every codegen issue for every target (this is certainly not the only one) and having a heap of target-specific code getting in the way of making stdsimd actually portable and stable. At a minimum we should also report this to LLVM (it may be relevant to more targets than just armv7)

[hsivonen]

I agree that reporting to LLVM makes sense and that it's problematic to have a lot of conditional target-specific code. However, another point of view is that if the application programmer can't trust that core::simd compiles to the best instructions, the value proposition for portable SIMD in general suffers. I think it's less bad to put the target-specific code in core::simd than e.g. in encoding_rs.

[calebzulawski]

I would argue that even with the sometimes-enabled target specific code, it still can't be trusted to compile to the best instructions. Regardless, I opened https://bugs.llvm.org/show_bug.cgi?id=51122. It appears there was a similar issue on x86-64 a couple years ago, but that was fixed.

[calebzulawski]

I was able to fix the codegen on Aarch64 by implementing any as self.to_int().horizontal_min() == -1, but this still fails on ARM and produces:

reduce_or:
 push    {r4, r5, r6, r7, r11, lr}
 vld1.64 {d16, d17}, [r0]
 vmin.s8 d16, d16, d17
 vmov.u8 r0, d16[0]
 vmov.u8 r1, d16[1]
 vmov.u8 r2, d16[2]
 vmov.u8 r3, d16[3]
 vmov.u8 r12, d16[4]
 vmov.u8 lr, d16[5]
 vmov.u8 r4, d16[6]
 vmov.u8 r5, d16[7]
 lsl     r0, r0, #24
 lsl     r1, r1, #24
 asr     r6, r0, #24
 asr     r7, r1, #24
 cmp     r6, r1, asr, #24
 asrlt   r7, r0, #24
 lsl     r0, r2, #24
 cmp     r7, r0, asr, #24
 asrge   r7, r0, #24
 lsl     r0, r3, #24
 cmp     r7, r0, asr, #24
 asrge   r7, r0, #24
 lsl     r0, r12, #24
 cmp     r7, r0, asr, #24
 asrge   r7, r0, #24
 lsl     r0, lr, #24
 cmp     r7, r0, asr, #24
 asrge   r7, r0, #24
 lsl     r0, r4, #24
 cmp     r7, r0, asr, #24
 asrge   r7, r0, #24
 lsl     r0, r5, #24
 cmp     r7, r0, asr, #24
 asrge   r7, r0, #24
 and     r0, r7, #255
 sub     r0, r0, #255
 clz     r0, r0
 lsr     r0, r0, #5
 pop     {r4, r5, r6, r7, r11, pc}

LLVM does not seem to be aware of vpmin at all.

[workingjubilee]

We changed some stuff around and LLVM is now LLVM 13. No action on the bug, but is this still an issue today?

[calebzulawski]

I just checked godbolt and yes, it's still an issue (for both armv7 and aarch64).

[thomcc]

We've been concerned about this kind of thing for a while, it's... part of what the whole mask representation arguments were about near the start (and this looks somewhat like my examples of LLVM doing bad things from back then 😬).

While I'm unsure we need to be above a target-specific fix (libcore even has these in the scalar numerics, after all), it sounds like this is not just an arm problem... (the indication I'm getting is that this is bad on several targets)

Boolean reductions are a super common operation. Do... we actually have a feeling this is fixable? (Perhaps with a new intrinsic which is UB to use if the input is not a mask type?)