Re: [PATCH 2/7] RISC-V: Add Zbb optimized memchr as ifunc

[Palmer Dabbelt <palmer@dabbelt.com>]

On Tue, 30 Apr 2024 10:45:12 PDT (-0700), adhemerval.zanella@linaro.org wrote:
>
>
> On 30/04/24 12:13, Palmer Dabbelt wrote:
>> On Wed, 24 Apr 2024 06:36:43 PDT (-0700), adhemerval.zanella@linaro.org wrote:
>>>
>>>
>>> On 24/04/24 10:16, Christoph Müllner wrote:
>>>> On Wed, Apr 24, 2024 at 2:53 PM Adhemerval Zanella Netto
>>>> <adhemerval.zanella@linaro.org> wrote:
>>>>>
>>>>>
>>>>>
>>>>> On 22/04/24 04:43, Christoph Müllner wrote:
>>>>>> When building with Zbb enabled, memchr benefits from using orc.b in
>>>>>> find_zero_all().  This patch changes the build system such, that a
>>>>>> non-Zbb version as well as a Zbb version of this routine is built.
>>>>>> Further, a ifunc resolver is provided that selects the right routine
>>>>>> based on the outcome of extension probing via hwprobe().
>>>>>>
>>>>>> Signed-off-by: Christoph Müllner <christoph.muellner@vrull.eu>
>>>>>> ---
>>>>>>  sysdeps/riscv/multiarch/memchr-generic.c      | 26 +++++++++
>>>>>>  sysdeps/riscv/multiarch/memchr-zbb.c          | 30 ++++++++++
>>>>>>  .../unix/sysv/linux/riscv/multiarch/Makefile  |  3 +
>>>>>>  .../linux/riscv/multiarch/ifunc-impl-list.c   | 31 ++++++++--
>>>>>>  .../unix/sysv/linux/riscv/multiarch/memchr.c  | 57 +++++++++++++++++++
>>>>>>  5 files changed, 142 insertions(+), 5 deletions(-)
>>>>>>  create mode 100644 sysdeps/riscv/multiarch/memchr-generic.c
>>>>>>  create mode 100644 sysdeps/riscv/multiarch/memchr-zbb.c
>>>>>>  create mode 100644 sysdeps/unix/sysv/linux/riscv/multiarch/memchr.c
>>>>>>
>>>>>> diff --git a/sysdeps/riscv/multiarch/memchr-generic.c b/sysdeps/riscv/multiarch/memchr-generic.c
>>>>>> new file mode 100644
>>>>>> index 0000000000..a96c36398b
>>>>>> --- /dev/null
>>>>>> +++ b/sysdeps/riscv/multiarch/memchr-generic.c
>>>>>> @@ -0,0 +1,26 @@
>>>>>> +/* Re-include the default memchr implementation.
>>>>>> +   Copyright (C) 2024 Free Software Foundation, Inc.
>>>>>> +   This file is part of the GNU C Library.
>>>>>> +
>>>>>> +   The GNU C Library is free software; you can redistribute it and/or
>>>>>> +   modify it under the terms of the GNU Lesser General Public
>>>>>> +   License as published by the Free Software Foundation; either
>>>>>> +   version 2.1 of the License, or (at your option) any later version.
>>>>>> +
>>>>>> +   The GNU C Library is distributed in the hope that it will be useful,
>>>>>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>>>>>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
>>>>>> +   Lesser General Public License for more details.
>>>>>> +
>>>>>> +   You should have received a copy of the GNU Lesser General Public
>>>>>> +   License along with the GNU C Library; if not, see
>>>>>> +   <https://www.gnu.org/licenses/>.  */
>>>>>> +
>>>>>> +#include <string.h>
>>>>>> +
>>>>>> +#if IS_IN(libc)
>>>>>> +# define MEMCHR __memchr_generic
>>>>>> +# undef libc_hidden_builtin_def
>>>>>> +# define libc_hidden_builtin_def(x)
>>>>>> +#endif
>>>>>> +#include <string/memchr.c>
>>>>>> diff --git a/sysdeps/riscv/multiarch/memchr-zbb.c b/sysdeps/riscv/multiarch/memchr-zbb.c
>>>>>> new file mode 100644
>>>>>> index 0000000000..bead0335ae
>>>>>> --- /dev/null
>>>>>> +++ b/sysdeps/riscv/multiarch/memchr-zbb.c
>>>>>> @@ -0,0 +1,30 @@
>>>>>> +/* Re-include the default memchr implementation for Zbb.
>>>>>> +   Copyright (C) 2024 Free Software Foundation, Inc.
>>>>>> +   This file is part of the GNU C Library.
>>>>>> +
>>>>>> +   The GNU C Library is free software; you can redistribute it and/or
>>>>>> +   modify it under the terms of the GNU Lesser General Public
>>>>>> +   License as published by the Free Software Foundation; either
>>>>>> +   version 2.1 of the License, or (at your option) any later version.
>>>>>> +
>>>>>> +   The GNU C Library is distributed in the hope that it will be useful,
>>>>>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>>>>>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
>>>>>> +   Lesser General Public License for more details.
>>>>>> +
>>>>>> +   You should have received a copy of the GNU Lesser General Public
>>>>>> +   License along with the GNU C Library; if not, see
>>>>>> +   <https://www.gnu.org/licenses/>.  */
>>>>>> +
>>>>>> +#include <string.h>
>>>>>> +
>>>>>> +#if IS_IN(libc)
>>>>>> +# define MEMCHR __memchr_zbb
>>>>>> +# undef libc_hidden_builtin_def
>>>>>> +# define libc_hidden_builtin_def(x)
>>>>>> +#endif
>>>>>> +/* Convince preprocessor to have Zbb instructions.  */
>>>>>> +#ifndef __riscv_zbb
>>>>>> +# define __riscv_zbb
>>>>>> +#endif
>>>>>
>>>>> Is there a way to specific the compiler to enable a extension, like aarch64
>>>>> -march=arch{+[no]feature}? I think ideally this should be enabled as CFLAGS
>>>>> instead of messing with compiler defined pre-processor.
>>>>
>>>> The tools expect a list of all extensions as parameter to the -march= option.
>>>> But there is no way to append extensions to an existing march string
>>>> on the command line.
>>>>
>>>> And if we would add this feature today, it would take many years until we could
>>>> use it here, because we want to remain compatible with old tools.
>>>> Or we enable the optimization only when being built with new tools, but that
>>>> adds even more complexity and build/test configurations.
>>>>
>>>> What we have is:
>>>> * Preprocessor (since forever): Extension test macros (__riscv_EXTENSION)
>>>> * Command line (since forever): -march=BASE_EXTENSIONLIST
>>>> * GAS (since Nov 21): .option arch, +EXTENSION (in combination with
>>>> option push/pop)
>>>> * GCC (since Nov 23): __attribute__((target("arch=+EXTENSION")))
>>>>
>>>> I was not sure about using __riscv_zbb as well, but I considered it safe within
>>>> ifdef tests that ensure the macro won't be set twice.
>>>> If that's a concern, I could change to use something like this:
>>>> #define __riscv_force_zbb
>>>> #include <impl.c>
>>>> #undef __riscv_force_zbb
>>>> ... and change string-fza.h like this:
>>>> #if defined(__riscv_zbb) || defined(__riscv_force_zbb)
>>>> // orc.b
>>>> #endif
>>>>
>>>> BR
>>>> Christoph
>>>
>>> Another options would to parse the current march and add the extension if required,
>>> something like:
>>>
>>> abi=$(riscv64-linux-gnu-gcc -Q --help=target | grep march | cut -d '=' -f2 | xargs)
>>> if [[ ! "$abi" =~ "_zbb" ]]
>>> then
>>>   abi="$abi"_zbb
>>> fi
>>
>> That alone likely won't do it, there's a bunch of ordering rules in the ISA string handling so we might get tripped up on them.  We've got a fairly relaxed version of the rules in GCC to try and match the various older rules, though, so it might be possible to make something similar work.
>>
>> We should probably just add some sort of -march=+zbb type argument.  IIRC Kito was going to do it at some point, not sure if he got around to it?
>
> I am just pointing this out because I think the way RISCV extension selection
> is currently implemented makes it awkward to provide ifunc implementation in
> a agnostic way (specially now that RISCV has dozens of extensions) without
> knowing the current target compiler is generating.
>
> Some other ABI allows to either specify a ISA/chip reference (like powerpc
> with -mcpu=powerX) or a ABI extension directly (like aarch64 with -march=+xxx).

We have -mcpu, but for RISC-V that's even more fragmented than -march 
(-mcpu essentially just rolls together -march and -mtune, and only 
allows a curated list).  The `-march=+`-type stuff has been a pretty 
common request, I think someone just needst oget around to actually 
implementing it.

>>> I don't have a strong preference, it is just that by not using the compiler flag
>>> we won't be able to either use the builtin (__builtin_riscv_orc_b_32) and/or get
>>> a possible better code generation from compiler.
>>
>> I think we'd likely get slightly better codgen from telling the compiler about the bitmanip extensions.  Maybe we want something like
>>
>>    diff --git a/string/memchr.c b/string/memchr.c
>>    index 08b5c41667..1b62dce8d8 100644
>>    --- a/string/memchr.c
>>    +++ b/string/memchr.c
>>    @@ -29,15 +29,19 @@
>>     # define __memchr MEMCHR
>>     #endif
>>       +#ifndef __MEMCHR_CODEGEN_ATTRIBUTE
>>    +#define __MEMCHR_CODEGEN_ATTRIBUTE
>>    +#endif
>>    +
>>     static __always_inline const char *
>>    -sadd (uintptr_t x, uintptr_t y)
>>    +sadd (uintptr_t x, uintptr_t y) __MEMCHR_CODEGEN_ATTRIBUTE
>>     {
>>       return (const char *)(y > UINTPTR_MAX - x ? UINTPTR_MAX : x + y);
>>     }
>>        /* Search no more than N bytes of S for C.  */
>>     void *
>>    -__memchr (void const *s, int c_in, size_t n)
>>    +__memchr (void const *s, int c_in, size_t n) __MEMCHR_CODEGEN_ATTRIBUTE
>>     {
>>       if (__glibc_unlikely (n == 0))
>>         return NULL;
>>
>> in the generic versions, so we can add a
>>
>>    #define __MEMCHR_CODEGEN_ATTRIBUTE __attribuet__((target("+zbb")))
>>
>> (or whatever the syntax is) to the Zbb-flavored versions of these routines?
>
> Yeah, this might work and it is clear than messing with compiler-defined
> macros.
>
>>
>> It might also be worth just jumping to the fast-misaligned versions for these routines, too --the slow-misaligned stuff is there for compatibility with old stuff (though memchr aligns the pointer, so it doesn't matter so much here).
>
> I was hopping that ABIs that would like to provide unaligned variants
> for mem* routines to improve the generic code, but it seems that for some
> it is easier to just add an assembly routine (as loongarch did).
>
> For memchr, I think it should be easy to provide a unaligned version.
> Something like (completely untested):
>
> /* Search no more than N bytes of S for C.  */
> void *
> __memchr (void const *s, int c_in, size_t n)
> {
>   if (__glibc_unlikely (n == 0))
>     return NULL;
>
> #ifdef USE_MEMCHR_UNALIGNED
>   /* Read the first word, but munge it so that bytes before the array
>      will not match goal.  */
>   const op_t *word_ptr = PTR_ALIGN_DOWN (s, sizeof (op_t));
>   uintptr_t s_int = (uintptr_t) s;
>
>   op_t word = *word_ptr;
>   op_t repeated_c = repeat_bytes (c_in);
>   /* Compute the address of the last byte taking in consideration possible
>      overflow.  */
>   const char *lbyte = sadd (s_int, n - 1);
>   /* And also the address of the word containing the last byte. */
>   const op_t *lword = (const op_t *) PTR_ALIGN_DOWN (lbyte, sizeof (op_t));
>
>   find_t mask = shift_find (find_eq_all (word, repeated_c), s_int);
>   if (mask != 0)
>     {
>       char *ret = (char *) s + index_first (mask);
>       return (ret <= lbyte) ? ret : NULL;
>     }
>   if (word_ptr == lword)
>     return NULL;
> #endif
>
>   word = *++word_ptr;
>   while (word_ptr != lword)
>     {
>       if (has_eq (word, repeated_c))
>         return (char *) word_ptr + index_first_eq (word, repeated_c);
>       word = *++word_ptr;
>     }
>
>   if (has_eq (word, repeated_c))
>     {
>       /* We found a match, but it might be in a byte past the end of the
>          array.  */
>       char *ret = (char *) word_ptr + index_first_eq (word, repeated_c);
>       if (ret <= lbyte)
>         return ret;
>     }
>   return NULL;
> }
>
>>
>>>>>> +#include <string/memchr.c>
>>>>>> diff --git a/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile b/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile
>>>>>> index fcef5659d4..5586d11c89 100644
>>>>>> --- a/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile
>>>>>> +++ b/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile
>>>>>> @@ -1,5 +1,8 @@
>>>>>>  ifeq ($(subdir),string)
>>>>>>  sysdep_routines += \
>>>>>> +  memchr \
>>>>>> +  memchr-generic \
>>>>>> +  memchr-zbb \
>>>>>>    memcpy \
>>>>>>    memcpy-generic \
>>>>>>    memcpy_noalignment \
>>>>>> diff --git a/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c b/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c
>>>>>> index 9f806d7a9e..7321144a32 100644
>>>>>> --- a/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c
>>>>>> +++ b/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c
>>>>>> @@ -20,19 +20,40 @@
>>>>>>  #include <string.h>
>>>>>>  #include <sys/hwprobe.h>
>>>>>>
>>>>>> +#define ARRAY_SIZE(A) (sizeof (A) / sizeof ((A)[0]))
>>>>>> +
>>>>>>  size_t
>>>>>>  __libc_ifunc_impl_list (const char *name, struct libc_ifunc_impl *array,
>>>>>>                       size_t max)
>>>>>>  {
>>>>>>    size_t i = max;
>>>>>> +  struct riscv_hwprobe pairs[] = {
>>>>>> +    { .key = RISCV_HWPROBE_KEY_IMA_EXT_0 },
>>>>>> +    { .key = RISCV_HWPROBE_KEY_CPUPERF_0 },
>>>>>> +  };
>>>>>>
>>>>>> +  bool has_zbb = false;
>>>>>>    bool fast_unaligned = false;
>>>>>>
>>>>>> -  struct riscv_hwprobe pair = { .key = RISCV_HWPROBE_KEY_CPUPERF_0 };
>>>>>> -  if (__riscv_hwprobe (&pair, 1, 0, NULL, 0) == 0
>>>>>> -      && (pair.value & RISCV_HWPROBE_MISALIGNED_MASK)
>>>>>> -          == RISCV_HWPROBE_MISALIGNED_FAST)
>>>>>> -    fast_unaligned = true;
>>>>>> +  if (__riscv_hwprobe (pairs, ARRAY_SIZE (pairs), 0, NULL, 0) == 0)
>>>>>> +    {
>>>>>> +      struct riscv_hwprobe *pair;
>>>>>> +
>>>>>> +      /* RISCV_HWPROBE_KEY_IMA_EXT_0  */
>>>>>> +      pair = &pairs[0];
>>>>>> +      if (pair->value & RISCV_HWPROBE_EXT_ZBB)
>>>>>> +        has_zbb = true;
>>>>>> +
>>>>>> +      /* RISCV_HWPROBE_KEY_CPUPERF_0  */
>>>>>> +      pair = &pairs[1];
>>>>>> +      if ((pair->value & RISCV_HWPROBE_MISALIGNED_MASK)
>>>>>> +        == RISCV_HWPROBE_MISALIGNED_FAST)
>>>>>> +        fast_unaligned = true;
>>>>>> +    }
>>>>>> +
>>>>>> +  IFUNC_IMPL (i, name, memchr,
>>>>>> +           IFUNC_IMPL_ADD (array, i, memchr, has_zbb, __memchr_zbb)
>>>>>> +           IFUNC_IMPL_ADD (array, i, memchr, 1, __memchr_generic))
>>>>>>
>>>>>>    IFUNC_IMPL (i, name, memcpy,
>>>>>>             IFUNC_IMPL_ADD (array, i, memcpy, fast_unaligned,
>>>>>> diff --git a/sysdeps/unix/sysv/linux/riscv/multiarch/memchr.c b/sysdeps/unix/sysv/linux/riscv/multiarch/memchr.c
>>>>>> new file mode 100644
>>>>>> index 0000000000..bc076cbf24
>>>>>> --- /dev/null
>>>>>> +++ b/sysdeps/unix/sysv/linux/riscv/multiarch/memchr.c
>>>>>> @@ -0,0 +1,57 @@
>>>>>> +/* Multiple versions of memchr.
>>>>>> +   All versions must be listed in ifunc-impl-list.c.
>>>>>> +   Copyright (C) 2017-2024 Free Software Foundation, Inc.
>>>>>> +   This file is part of the GNU C Library.
>>>>>> +
>>>>>> +   The GNU C Library is free software; you can redistribute it and/or
>>>>>> +   modify it under the terms of the GNU Lesser General Public
>>>>>> +   License as published by the Free Software Foundation; either
>>>>>> +   version 2.1 of the License, or (at your option) any later version.
>>>>>> +
>>>>>> +   The GNU C Library is distributed in the hope that it will be useful,
>>>>>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>>>>>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
>>>>>> +   Lesser General Public License for more details.
>>>>>> +
>>>>>> +   You should have received a copy of the GNU Lesser General Public
>>>>>> +   License along with the GNU C Library; if not, see
>>>>>> +   <https://www.gnu.org/licenses/>.  */
>>>>>> +
>>>>>> +#if IS_IN (libc)
>>>>>> +/* Redefine memchr so that the compiler won't complain about the type
>>>>>> +   mismatch with the IFUNC selector in strong_alias, below.  */
>>>>>> +# undef memchr
>>>>>> +# define memchr __redirect_memchr
>>>>>> +# include <stdint.h>
>>>>>> +# include <string.h>
>>>>>> +# include <ifunc-init.h>
>>>>>> +# include <riscv-ifunc.h>
>>>>>> +# include <sys/hwprobe.h>
>>>>>> +
>>>>>> +extern __typeof (__redirect_memchr) __libc_memchr;
>>>>>> +
>>>>>> +extern __typeof (__redirect_memchr) __memchr_generic attribute_hidden;
>>>>>> +extern __typeof (__redirect_memchr) __memchr_zbb attribute_hidden;
>>>>>> +
>>>>>> +static inline __typeof (__redirect_memchr) *
>>>>>> +select_memchr_ifunc (uint64_t dl_hwcap, __riscv_hwprobe_t hwprobe_func)
>>>>>> +{
>>>>>> +  unsigned long long int v;
>>>>>> +  if (__riscv_hwprobe_one (hwprobe_func, RISCV_HWPROBE_KEY_IMA_EXT_0, &v) == 0
>>>>>> +      && (v & RISCV_HWPROBE_EXT_ZBB))
>>>>>> +    return __memchr_zbb;
>>>>>> +
>>>>>> +  return __memchr_generic;
>>>>>> +}
>>>>>> +
>>>>>> +riscv_libc_ifunc (__libc_memchr, select_memchr_ifunc);
>>>>>> +
>>>>>> +# undef memchr
>>>>>> +strong_alias (__libc_memchr, memchr);
>>>>>> +# ifdef SHARED
>>>>>> +__hidden_ver1 (memchr, __GI_memchr, __redirect_memchr)
>>>>>> +  __attribute__ ((visibility ("hidden"))) __attribute_copy__ (memchr);
>>>>>> +# endif
>>>>>> +#else
>>>>>> +# include <string/memchr.c>
>>>>>> +#endif