Re: [PATCH v4 09/10] util/bufferiszero: Add simd acceleration for aarch64

[Richard Henderson <richard.henderson@linaro.org>]

On 2/14/24 22:47, Alexander Monakov wrote:
> 
> On Wed, 14 Feb 2024, Richard Henderson wrote:
> 
>> Because non-embedded aarch64 is expected to have AdvSIMD enabled, merely
>> double-check with the compiler flags for __ARM_NEON and don't bother with
>> a runtime check.  Otherwise, model the loop after the x86 SSE2 function,
>> and use VADDV to reduce the four vector comparisons.
> 
> I am not very familiar with Neon but I wonder if this couldn't use SHRN
> for the final 128b->64b reduction similar to 2022 Glibc optimizations:
> https://inbox.sourceware.org/libc-alpha/20220620174628.2820531-1-danilak@google.com/

The reason they use SHRN for memchr is that they have also applied a mask
to the comparison so that they can identify which byte contained the match.
That is not required here, so any reduction will do.


> In git history I see the previous Neon buffer_is_zero was removed because
> it was not faster. Is it because integer LDP was as good as vector loads
> at saturating load bandwidth on older cores, and things are different now?

The old reduction was a bit silly,

-#define DO_NONZERO(X)  (vgetq_lane_u64((X), 0) | vgetq_lane_u64((X), 1))

performing two cross-register-set fetches.  It's also possible that we were saturating the 
load bandwidth on the old mustang.  This time I'm testing on a neoverse-n1, which is quite 
a few years newer.

The loop kernel compiles to this:

  19c:   ad401c20        ldp     q0, q7, [x1]
  1a0:   ad411823        ldp     q3, q6, [x1, #32]
  1a4:   ad421421        ldp     q1, q5, [x1, #64]
  1a8:   ad431022        ldp     q2, q4, [x1, #96]
  1ac:   91020021        add     x1, x1, #0x80
  1b0:   4ea71c00        orr     v0.16b, v0.16b, v7.16b
  1b4:   4ea61c63        orr     v3.16b, v3.16b, v6.16b
  1b8:   4ea51c21        orr     v1.16b, v1.16b, v5.16b
  1bc:   4ea41c42        orr     v2.16b, v2.16b, v4.16b
  1c0:   4ea31c00        orr     v0.16b, v0.16b, v3.16b
  1c4:   4ea21c21        orr     v1.16b, v1.16b, v2.16b
  1c8:   4ea11c00        orr     v0.16b, v0.16b, v1.16b
  1cc:   eb03003f        cmp     x1, x3
  1d0:   54000162        b.cs    1fc <buffer_is_zero_simd+0xb8>  // b.hs, b.nlast
  1d4:   4ea09800        cmeq    v0.4s, v0.4s, #0
  1d8:   4eb1b800        addv    s0, v0.4s
  1dc:   1e260000        fmov    w0, s0
  1e0:   3100101f        cmn     w0, #0x4
  1e4:   54fffdc0        b.eq    19c <buffer_is_zero_simd+0x58>  // b.none


r~

> 
> Alexander
> 
>>
>> Signed-off-by: Richard Henderson <richard.henderson@linaro.org>
>> ---
>>   util/bufferiszero.c | 74 +++++++++++++++++++++++++++++++++++++++++++++
>>   1 file changed, 74 insertions(+)
>>
>> diff --git a/util/bufferiszero.c b/util/bufferiszero.c
>> index 4eef6d47bc..2809b09225 100644
>> --- a/util/bufferiszero.c
>> +++ b/util/bufferiszero.c
>> @@ -214,7 +214,81 @@ bool test_buffer_is_zero_next_accel(void)
>>       }
>>       return false;
>>   }
>> +
>> +#elif defined(__aarch64__) && defined(__ARM_NEON)
>> +#include <arm_neon.h>
>> +
>> +#define REASSOC_BARRIER(vec0, vec1) asm("" : "+w"(vec0), "+w"(vec1))
>> +
>> +static bool buffer_is_zero_simd(const void *buf, size_t len)
>> +{
>> +    uint32x4_t t0, t1, t2, t3;
>> +
>> +    /* Align head/tail to 16-byte boundaries.  */
>> +    const uint32x4_t *p = QEMU_ALIGN_PTR_DOWN(buf + 16, 16);
>> +    const uint32x4_t *e = QEMU_ALIGN_PTR_DOWN(buf + len - 1, 16);
>> +
>> +    /* Unaligned loads at head/tail.  */
>> +    t0 = vld1q_u32(buf) | vld1q_u32(buf + len - 16);
>> +
>> +    /* Collect a partial block at tail end.  */
>> +    t1 = e[-7] | e[-6];
>> +    t2 = e[-5] | e[-4];
>> +    t3 = e[-3] | e[-2];
>> +    t0 |= e[-1];
>> +    REASSOC_BARRIER(t0, t1);
>> +    REASSOC_BARRIER(t2, t3);
>> +    t0 |= t1;
>> +    t2 |= t3;
>> +    REASSOC_BARRIER(t0, t2);
>> +    t0 |= t2;
>> +
>> +    /*
>> +     * Loop over complete 128-byte blocks.
>> +     * With the head and tail removed, e - p >= 14, so the loop
>> +     * must iterate at least once.
>> +     */
>> +    do {
>> +        /* Each comparison is [-1,0], so reduction is in [-4..0]. */
>> +        if (unlikely(vaddvq_u32(vceqzq_u32(t0)) != -4)) {
>> +            return false;
>> +        }
>> +
>> +        t0 = p[0] | p[1];
>> +        t1 = p[2] | p[3];
>> +        t2 = p[4] | p[5];
>> +        t3 = p[6] | p[7];
>> +        REASSOC_BARRIER(t0, t1);
>> +        REASSOC_BARRIER(t2, t3);
>> +        t0 |= t1;
>> +        t2 |= t3;
>> +        REASSOC_BARRIER(t0, t2);
>> +        t0 |= t2;
>> +        p += 8;
>> +    } while (p < e - 7);
>> +
>> +    return vaddvq_u32(vceqzq_u32(t0)) == -4;
>> +}
>> +
>> +static biz_accel_fn const accel_table[] = {
>> +    buffer_is_zero_int_ge256,
>> +    buffer_is_zero_simd,
>> +};
>> +
>> +static unsigned accel_index = 1;
>> +#define INIT_ACCEL buffer_is_zero_simd
>> +
>> +bool test_buffer_is_zero_next_accel(void)
>> +{
>> +    if (accel_index != 0) {
>> +        buffer_is_zero_accel = accel_table[--accel_index];
>> +        return true;
>> +    }
>> +    return false;
>> +}
>> +
>>   #else
>> +
>>   bool test_buffer_is_zero_next_accel(void)
>>   {
>>       return false;
>>