Re: [PATCH 04/17] Add string vectorized find and detection functions

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 03/09/22 10:13, Wilco Dijkstra wrote:
> Hi Adhemerval,
> 
> +static inline unsigned int
> +__clz (op_t x)
> +{
> +#if !HAVE_BUILTIN_CLZ
> +  unsigned r;
> +  op_t i;
> +
> +  x |= x >> 1;
> +  x |= x >> 2;
> +  x |= x >> 4;
> +  x |= x >> 8;
> +  x |= x >> 16;
> +# if __WORDSIZE == 64
> +  x |= x >> 32;
> +  i = x * 0x03F79D71B4CB0A89ull >> 58;
> +# else
> +  i = x * 0x07C4ACDDU >> 27;
> +# endif
> +  r = index_access (i);
> +  return r ^ (sizeof (op_t) * CHAR_BIT - 1);
> +#else
> +  if (sizeof (op_t) == sizeof (long int))
> +    return __builtin_clzl (x);
> +  else
> +    return __builtin_clzll (x);
> +#endif
> +}
> 
> This is a really bad idea. Firstly it is incorrect - sizeof (op_t) != __WORDSIZE due to
> the odd way it is defined (it can be 64 bits on 32-bit targets). That in itself is
> problematic since it isn't clear that using 64 bits operations extensively is efficient
> on 32-bit targets (using 64-bit multiplies in GMP is different from using 64-bit
> load/store in memcpy/memset which is different from 64-bit logical operations and
> shifts, so all of these should be decoupled rather than forced together).
> 
> Secondly, there are already several ways to use count leading zeroes in GLIBC.
> One is use the builtin unconditionally (done in lots of places, eg. by math code),
> another is count_leading_zeros defined in longlong.h. This would add the third way. 
> It's not clear how much gain inlining gives over using the libgcc implementation,
> but if it is significant then we could provide a generic inline clzl/clzll that can be
> used throughout GLIBC (replacing existing builtin_clz and count_leading_zeros).
> 

Fair enough, I can't really recall I have added another count bits routine instead
of using the already provided ones on longlong.h.  The longlong.h already take care
of avoiding libcall, so I adjusted the patch to use them instead.

> Finally, emulating a full clz is inefficient. If you have already called find_zero_low
> then there are at most 4 bits set on a 32-bit LE target, so you can trivially get the
> index of the first zero byte via:
> 
> x = x & -x;
> x = (x >> 15) + (x >> 22) + 3 * (x >> 31);
> 
> This is many times faster. There may be similar sequences for big-endian, but
> you could just do a multiply with a magic word that gives the correct result
> without needing a lookup table.

I take that on recent architectures it would be faster assuming the existence of
clz instruction, and this specific code is just used on memrchr tail call. So
I think we can optimize it further on a subsequent patch.