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

["Christoph Müllner" <christoph.muellner@vrull.eu>]

On Tue, Apr 30, 2024 at 7:54 PM Palmer Dabbelt <palmer@dabbelt.com> wrote:
>
> 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 agree that `-march=+` would be the best solution.
As we don't have it, I've created a PR for the riscv-toolchain-conventions:
  https://github.com/riscv-non-isa/riscv-toolchain-conventions/pull/47
This will have to depend on GCC 15+ (assuming there will be consensus
in the next 10 months about it).

Thanks for the proposal with the function-attributes.
I'm working on a patchset for that and will send it out after some testing.
This will have to depend on GCC 14+.

> >>> 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