diff mbox series

[v3,04/18] Add string vectorized find and detection functions

Message ID 1515588482-15744-5-git-send-email-adhemerval.zanella@linaro.org
State New
Headers show
Series Improve generic string routines | expand

Commit Message

Adhemerval Zanella Netto Jan. 10, 2018, 12:47 p.m. UTC
This patch adds generic string find and detection implementation meant
to be used in generic vectorized string implementation.  The idea is to
decompose the basic string operation so each architecture can reimplement
if it provides any specialized hardware instruction.

The 'string-fza.h' provides zero byte detection functions (find_zero_low,
find_zero_all, find_eq_low, find_eq_all, find_zero_eq_low, find_zero_eq_all,
find_zero_ne_low, and find_zero_ne_all).  They are used on both functions
provided by 'string-fzb.h' and 'string-fzi'.

The 'string-fzb.h' provides boolean zero byte detection with the
functions:

  - has_zero: determine if any byte within a word is zero.
  - has_eq: determine byte equality between two words.
  - has_zero_eq: determine if any byte within a word is zero along with
    byte equality between two words.

The 'string-fzi.h' provides zero byte detection along with its positions:

  - index_first_zero: return index of first zero byte within a word.
  - index_first_eq: return index of first byte different between two words.
  - index_first_zero_eq: return index of first zero byte within a word or
    first byte different between two words.
  - index_first_zero_ne: return index of first zero byte within a word or
    first byte equal between two words.
  - index_last_zero: return index of last zero byte within a word.
  - index_last_eq: return index of last byte different between two words.

Also, to avoid libcalls in the '__builtin_c{t,l}z{l}' calls (which may
add performance degradation), inline implementation based on De Bruijn
sequences are added (enabled by a configure check).

	Richard Henderson  <rth@twiddle.net>
	Adhemerval Zanella  <adhemerval.zanella@linaro.org>

	* config.h.in (HAVE_BUILTIN_CTZ, HAVE_BUILTIN_CLZ): New defines.
	* configure.ac: Check for __builtin_ctz{l} with no external
	dependencies
	* sysdeps/generic/string-extbyte.h: New file.
	* sysdeps/generic/string-fza.h: Likewise.
	* sysdeps/generic/string-fzb.h: Likewise.
	* sysdeps/generic/string-fzi.h: Likewise.
---
 config.h.in                      |   8 ++
 configure                        |  54 ++++++++++
 configure.ac                     |  34 +++++++
 sysdeps/generic/string-extbyte.h |  35 +++++++
 sysdeps/generic/string-fza.h     | 117 +++++++++++++++++++++
 sysdeps/generic/string-fzb.h     |  49 +++++++++
 sysdeps/generic/string-fzi.h     | 215 +++++++++++++++++++++++++++++++++++++++
 7 files changed, 512 insertions(+)
 create mode 100644 sysdeps/generic/string-extbyte.h
 create mode 100644 sysdeps/generic/string-fza.h
 create mode 100644 sysdeps/generic/string-fzb.h
 create mode 100644 sysdeps/generic/string-fzi.h

-- 
2.7.4

Comments

Joseph Myers Jan. 11, 2018, 1:34 p.m. UTC | #1
On Wed, 10 Jan 2018, Adhemerval Zanella wrote:

> +

> +static inline unsigned char

> +extractbyte (op_t x, unsigned idx)


Missing comment on the semantics of this function.  "unsigned int".

> +/* For architecture which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ)

> +   and/or __builtin_ctz{l} (HAVE_BUILTIN_CTZ) which uses external libcalls

> +   (for intance __c{l,t}z{s,d}i2 from libgcc) the following wrapper provides

> +   inline implementation for both count leading zeros and count trailing

> +   zeros using branchless computation.  */


I think the comments need to say a bit more about the semantics of these 
functions.  In particular, do they follow the same rule as the built-in 
functions that behavior is undefined if the argument is zero?  If they do, 
then I'd expect the comments on the functions that call them to specify 
that they must not be called with a zero argument (zero arguments in this 
case generally corresponding to words that are not at the end of the 
string etc., so the functions indeed don't get called in that case).

-- 
Joseph S. Myers
joseph@codesourcery.com
Luis Machado Jan. 11, 2018, 1:44 p.m. UTC | #2
Some quick typos i noticed while skimming through it.

On 01/10/2018 10:47 AM, Adhemerval Zanella wrote:
> +/* If compiler supports __builtin_ctz{l} without any external depedencies


typo... dependencies

More cases of this.

> diff --git a/sysdeps/generic/string-extbyte.h b/sysdeps/generic/string-extbyte.h

> new file mode 100644

> index 0000000..69a78ce

> --- /dev/null

> +++ b/sysdeps/generic/string-extbyte.h

> @@ -0,0 +1,35 @@

> +/* Extract by from memory word.  Generic C version.


Extract byte?

> diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h

> new file mode 100644

> index 0000000..57101f2

> --- /dev/null

> +++ b/sysdeps/generic/string-fzi.h

> @@ -0,0 +1,215 @@

> +/* Zero byte detection; indexes.  Generic C version.

> +   Copyright (C) 2018 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

> +   <http://www.gnu.org/licenses/>.  */

> +

> +#ifndef STRING_FZI_H

> +#define STRING_FZI_H 1

> +

> +#include <limits.h>

> +#include <endian.h>

> +#include <string-fza.h>

> +

> +/* An improved bitscan routine, multiplying the De Bruijn sequence with a

> +   0-1 mask separated by the least significant one bit of a scanned integer

> +   or bitboard [1].

> +

> +   [1] https://chessprogramming.wikispaces.com/Kim+Walisch  */

> +

> +static inline unsigned

> +index_access (const op_t i)

> +{

> +  static const char index[] =

> +  {

> +# if __WORDSIZE == 64

> +     0, 47,  1, 56, 48, 27,  2, 60,

> +    57, 49, 41, 37, 28, 16,  3, 61,

> +    54, 58, 35, 52, 50, 42, 21, 44,

> +    38, 32, 29, 23, 17, 11,  4, 62,

> +    46, 55, 26, 59, 40, 36, 15, 53,

> +    34, 51, 20, 43, 31, 22, 10, 45,

> +    25, 39, 14, 33, 19, 30,  9, 24,

> +    13, 18,  8, 12,  7,  6,  5, 63

> +# else

> +     0,  9,  1, 10, 13, 21,  2, 29,

> +    11, 14, 16, 18, 22, 25,  3, 30,

> +     8, 12, 20, 28, 15, 17, 24,  7,

> +    19, 27, 23,  6, 26,  5,  4, 31

> +# endif

> +  };

> +  return index[i];

> +}

> +

> +/* For architecture which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ)


For architectures?
Paul Eggert Jan. 11, 2018, 4:47 p.m. UTC | #3
On 01/10/2018 04:47 AM, Adhemerval Zanella wrote:
> +  op_t lsb = (op_t)-1 / 0xff;

> +  op_t msb = lsb << (CHAR_BIT - 1);

This would be simpler and clearer if it were rewritten as:

     opt_t lsb = repeat_bytes (0x01);
     opt_t msb = repeat_bytes (0x80);

There are several other opportunities for this kind of simplification.

> +static inline op_t

> +find_zero_eq_low (op_t x1, op_t x2)

> +{

> +  op_t lsb = (op_t)-1 / 0xff;

> +  op_t msb = lsb << (CHAR_BIT - 1);

> +  op_t eq = x1 ^ x2;

> +  return (((x1 - lsb) & ~x1) | ((eq - lsb) & ~eq)) & msb;

> +}


How about the following simpler implementation instead? I expect it's 
just as fast:

    return find_zero_low (x1) | find_zero_low (x1 ^ x2);

Similarly for find_zero_eq_all, find_zero_ne_low, find_zero_ne_all.

> +static inline unsigned

> +__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);


The Gnulib integer_length module has a faster implementation, at least 
for 32-bit platforms. Do we still care about 32-bit platforms? If so, 
you might want to take a look at it.
Adhemerval Zanella Netto Jan. 11, 2018, 6:25 p.m. UTC | #4
On 11/01/2018 11:44, Luis Machado wrote:
> Some quick typos i noticed while skimming through it.

> 

> On 01/10/2018 10:47 AM, Adhemerval Zanella wrote:

>> +/* If compiler supports __builtin_ctz{l} without any external depedencies

> 

> typo... dependencies

> 

> More cases of this.

> 

>> diff --git a/sysdeps/generic/string-extbyte.h b/sysdeps/generic/string-extbyte.h

>> new file mode 100644

>> index 0000000..69a78ce

>> --- /dev/null

>> +++ b/sysdeps/generic/string-extbyte.h

>> @@ -0,0 +1,35 @@

>> +/* Extract by from memory word.  Generic C version.

> 

> Extract byte?

> 

>> diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h

>> new file mode 100644

>> index 0000000..57101f2

>> --- /dev/null

>> +++ b/sysdeps/generic/string-fzi.h

>> @@ -0,0 +1,215 @@

>> +/* Zero byte detection; indexes.  Generic C version.

>> +   Copyright (C) 2018 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

>> +   <http://www.gnu.org/licenses/>.  */

>> +

>> +#ifndef STRING_FZI_H

>> +#define STRING_FZI_H 1

>> +

>> +#include <limits.h>

>> +#include <endian.h>

>> +#include <string-fza.h>

>> +

>> +/* An improved bitscan routine, multiplying the De Bruijn sequence with a

>> +   0-1 mask separated by the least significant one bit of a scanned integer

>> +   or bitboard [1].

>> +

>> +   [1] https://chessprogramming.wikispaces.com/Kim+Walisch  */

>> +

>> +static inline unsigned

>> +index_access (const op_t i)

>> +{

>> +  static const char index[] =

>> +  {

>> +# if __WORDSIZE == 64

>> +     0, 47,  1, 56, 48, 27,  2, 60,

>> +    57, 49, 41, 37, 28, 16,  3, 61,

>> +    54, 58, 35, 52, 50, 42, 21, 44,

>> +    38, 32, 29, 23, 17, 11,  4, 62,

>> +    46, 55, 26, 59, 40, 36, 15, 53,

>> +    34, 51, 20, 43, 31, 22, 10, 45,

>> +    25, 39, 14, 33, 19, 30,  9, 24,

>> +    13, 18,  8, 12,  7,  6,  5, 63

>> +# else

>> +     0,  9,  1, 10, 13, 21,  2, 29,

>> +    11, 14, 16, 18, 22, 25,  3, 30,

>> +     8, 12, 20, 28, 15, 17, 24,  7,

>> +    19, 27, 23,  6, 26,  5,  4, 31

>> +# endif

>> +  };

>> +  return index[i];

>> +}

>> +

>> +/* For architecture which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ)

> 

> For architectures?


Thanks, I fixed all locally.
Adhemerval Zanella Netto Jan. 11, 2018, 6:25 p.m. UTC | #5
On 11/01/2018 11:34, Joseph Myers wrote:
> On Wed, 10 Jan 2018, Adhemerval Zanella wrote:

> 

>> +

>> +static inline unsigned char

>> +extractbyte (op_t x, unsigned idx)

> 

> Missing comment on the semantics of this function.  "unsigned int".


I applied this change locally:

diff --git a/sysdeps/generic/string-extbyte.h b/sysdeps/generic/string-extbyte.h
index 69a78ce..c4693b2 100644
--- a/sysdeps/generic/string-extbyte.h
+++ b/sysdeps/generic/string-extbyte.h
@@ -23,8 +23,10 @@
 #include <endian.h>
 #include <string-optype.h>
 
+/* Extract the byte at index IDX from word X, with index 0 being the
+   least significant byte.  */
 static inline unsigned char
-extractbyte (op_t x, unsigned idx)
+extractbyte (op_t x, unsigned int idx)
 {
   if (__BYTE_ORDER == __LITTLE_ENDIAN)
     return x >> (idx * CHAR_BIT);


> 

>> +/* For architecture which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ)

>> +   and/or __builtin_ctz{l} (HAVE_BUILTIN_CTZ) which uses external libcalls

>> +   (for intance __c{l,t}z{s,d}i2 from libgcc) the following wrapper provides

>> +   inline implementation for both count leading zeros and count trailing

>> +   zeros using branchless computation.  */

> 

> I think the comments need to say a bit more about the semantics of these 

> functions.  In particular, do they follow the same rule as the built-in 

> functions that behavior is undefined if the argument is zero?  If they do, 

> then I'd expect the comments on the functions that call them to specify 

> that they must not be called with a zero argument (zero arguments in this 

> case generally corresponding to words that are not at the end of the 

> string etc., so the functions indeed don't get called in that case).

> 


I think it is reasonable to set the same semantic as the builtins and I
did not pay attention to outline this mainly because they are not indeed
used called in such cases (which would be UB for the builtin case in
fact).  I applied this patch locally:

diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h
index 57101f2..534babb 100644
--- a/sysdeps/generic/string-fzi.h
+++ b/sysdeps/generic/string-fzi.h
@@ -29,7 +29,7 @@
 
    [1] https://chessprogramming.wikispaces.com/Kim+Walisch  */
 
-static inline unsigned
+static inline unsigned int
 index_access (const op_t i)
 {
   static const char index[] =
@@ -53,13 +53,14 @@ index_access (const op_t i)
   return index[i];
 }
 
-/* For architecture which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ)
+/* For architectures which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ)
    and/or __builtin_ctz{l} (HAVE_BUILTIN_CTZ) which uses external libcalls
    (for intance __c{l,t}z{s,d}i2 from libgcc) the following wrapper provides
    inline implementation for both count leading zeros and count trailing
-   zeros using branchless computation.  */
+   zeros using branchless computation.  As for builtin, if x is 0 the
+   result is undefined.*/
 
-static inline unsigned
+static inline unsigned int
 __ctz (op_t x)
 {
 #if !HAVE_BUILTIN_CTZ
@@ -78,7 +79,7 @@ __ctz (op_t x)
 #endif
 };
 
-static inline unsigned
+static inline unsigned int
 __clz (op_t x)
 {
 #if !HAVE_BUILTIN_CLZ
Adhemerval Zanella Netto Jan. 11, 2018, 6:54 p.m. UTC | #6
On 11/01/2018 14:47, Paul Eggert wrote:
> On 01/10/2018 04:47 AM, Adhemerval Zanella wrote:

>> +  op_t lsb = (op_t)-1 / 0xff;

>> +  op_t msb = lsb << (CHAR_BIT - 1);

> This would be simpler and clearer if it were rewritten as:

> 

>     opt_t lsb = repeat_bytes (0x01);

>     opt_t msb = repeat_bytes (0x80);

> 

> There are several other opportunities for this kind of simplification.


Indeed, I changed it locally

> 

>> +static inline op_t

>> +find_zero_eq_low (op_t x1, op_t x2)

>> +{

>> +  op_t lsb = (op_t)-1 / 0xff;

>> +  op_t msb = lsb << (CHAR_BIT - 1);

>> +  op_t eq = x1 ^ x2;

>> +  return (((x1 - lsb) & ~x1) | ((eq - lsb) & ~eq)) & msb;

>> +}

> 

> How about the following simpler implementation instead? I expect it's just as fast:

> 

>    return find_zero_low (x1) | find_zero_low (x1 ^ x2);

> 

> Similarly for find_zero_eq_all, find_zero_ne_low, find_zero_ne_all.


I think this seems ok and code generation for at least aarch64, powerpc64le,
sparc64, and x86_64 seems similar.

> 

>> +static inline unsigned

>> +__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);

> 

> The Gnulib integer_length module has a faster implementation, at least for 32-bit platforms. Do we still care about 32-bit platforms? If so, you might want to take a look at it.


Do you mean the version which uses double to integer, the one with 6 comparisons
or the naive one? Indeed I think for 32 bits is issuing a lot of instruction,
the only advantage I see it is branchless (which might be a gain in some kind
of architectures).
Paul Eggert Jan. 12, 2018, 1:08 a.m. UTC | #7
On 01/11/2018 10:54 AM, Adhemerval Zanella wrote:
>> The Gnulib integer_length module has a faster implementation, at least for 32-bit platforms. Do we still care about 32-bit platforms? If so, you might want to take a look at it.

> Do you mean the version which uses double to integer, the one with 6 comparisons

> or the naive one?


I meant the one that converts int to double. It can be branchless since 
we assume the int is nonzero.
Adhemerval Zanella Netto Jan. 12, 2018, 1:30 p.m. UTC | #8
On 11/01/2018 16:54, Adhemerval Zanella wrote:
> 

> 

> On 11/01/2018 14:47, Paul Eggert wrote:

>> On 01/10/2018 04:47 AM, Adhemerval Zanella wrote:

>>> +  op_t lsb = (op_t)-1 / 0xff;

>>> +  op_t msb = lsb << (CHAR_BIT - 1);

>> This would be simpler and clearer if it were rewritten as:

>>

>>     opt_t lsb = repeat_bytes (0x01);

>>     opt_t msb = repeat_bytes (0x80);

>>

>> There are several other opportunities for this kind of simplification.

> 

> Indeed, I changed it locally

> 

>>

>>> +static inline op_t

>>> +find_zero_eq_low (op_t x1, op_t x2)

>>> +{

>>> +  op_t lsb = (op_t)-1 / 0xff;

>>> +  op_t msb = lsb << (CHAR_BIT - 1);

>>> +  op_t eq = x1 ^ x2;

>>> +  return (((x1 - lsb) & ~x1) | ((eq - lsb) & ~eq)) & msb;

>>> +}

>>

>> How about the following simpler implementation instead? I expect it's just as fast:

>>

>>    return find_zero_low (x1) | find_zero_low (x1 ^ x2);

>>

>> Similarly for find_zero_eq_all, find_zero_ne_low, find_zero_ne_all.

> 

> I think this seems ok and code generation for at least aarch64, powerpc64le,

> sparc64, and x86_64 seems similar.


While trying to compose find_zero_new_{low,all} with find_zero_{low,all}
made me not so sure if it would be gain. To accomplish we will need to add
another operation, such as:

---
static inline op_t
find_zero_ne_low (op_t x1, op_t x2)
{
  op_t x = repeat_bytes (0x80);
  return find_zero_low (x1) | (find_zero_low (x1 ^ x2) ^ x);
}
---

Which seems slight worse than current regarding generated instructions.
Using GCC 7.2.1 for x86_64 I see:

* Patch version:

find_zero_ne_low.constprop.0:
.LFB28: 
        .cfi_startproc
        movabsq $1229782938247303441, %rdx
        movq    %rdx, %rcx
        movabsq $9187201950435737471, %rdx
        leaq    (%rdi,%rdx), %rax
        xorq    %rdi, %rcx
        addq    %rcx, %rdx
        orq     %rdi, %rax
        orq     %rcx, %rdx
        movabsq $-9187201950435737472, %rdi
        notq    %rax
        orq     %rdx, %rax
        andq    %rdi, %rax
        ret


* find_zero_low version above:

find_zero_ne_low.constprop.0:
.LFB28: 
        .cfi_startproc
        movabsq $1229782938247303441, %rax
        movabsq $-72340172838076673, %rdx
        movabsq $-1229782938247303442, %rcx
        xorq    %rdi, %rax
        xorq    %rdi, %rcx
        addq    %rdx, %rax
        addq    %rdi, %rdx
        notq    %rdi
        andq    %rcx, %rax
        andq    %rdi, %rdx
        movabsq $-9187201950435737472, %rdi
        notq    %rax
        orq     %rdx, %rax
        andq    %rdi, %rax
        ret
Joseph Myers Jan. 12, 2018, 5:08 p.m. UTC | #9
On Thu, 11 Jan 2018, Paul Eggert wrote:

> On 01/11/2018 10:54 AM, Adhemerval Zanella wrote:

> > > The Gnulib integer_length module has a faster implementation, at least for

> > > 32-bit platforms. Do we still care about 32-bit platforms? If so, you

> > > might want to take a look at it.

> > Do you mean the version which uses double to integer, the one with 6

> > comparisons

> > or the naive one?

> 

> I meant the one that converts int to double. It can be branchless since we

> assume the int is nonzero.


Looking at glibc architectures (and architectures with recently proposed 
ports):

* The following have clz patterns in GCC, unconditionally, meaning this 
glibc patch will always use __builtin_clz functions and any fallback code 
is irrelevant: aarch64 i386 ia64 powerpc tilegx x86_64.  (On ia64 the 
pattern uses conversion to floating point.)

* The following have clz patterns in GCC, conditionally: alpha arm m68k 
microblaze mips s390 sparc (and arc).  I have not checked whether in some 
of those cases the conditions might in fact be true for every 
configuration for which glibc can be built.

* The following lack clz patterns in GCC: hppa nios2 sh (and riscv).

If the configuration lacking clz is also soft-float, converting int to 
double is an extremely inefficient way ending up calling the libgcc clz 
implementation (both soft-fp and fp-bit use __builtin_clz).  I think 
that's sufficient reason to avoid an approach involving conversion to 
double unless an architecture has opted in to using it as an efficient 
approach on that architecture.

(For arm, for example, clz is supported if "TARGET_32BIT && arm_arch5", so 
the only configurations without __builtin_clz expanded inline by the 
compiler are armv4t ones - which are also all soft-float, so the expansion 
using double can never make sense for arm.)

-- 
Joseph S. Myers
joseph@codesourcery.com
Adhemerval Zanella Netto Jan. 12, 2018, 5:58 p.m. UTC | #10
On 12/01/2018 15:08, Joseph Myers wrote:
> On Thu, 11 Jan 2018, Paul Eggert wrote:

> 

>> On 01/11/2018 10:54 AM, Adhemerval Zanella wrote:

>>>> The Gnulib integer_length module has a faster implementation, at least for

>>>> 32-bit platforms. Do we still care about 32-bit platforms? If so, you

>>>> might want to take a look at it.

>>> Do you mean the version which uses double to integer, the one with 6

>>> comparisons

>>> or the naive one?

>>

>> I meant the one that converts int to double. It can be branchless since we

>> assume the int is nonzero.

> 

> Looking at glibc architectures (and architectures with recently proposed 

> ports):

> 

> * The following have clz patterns in GCC, unconditionally, meaning this 

> glibc patch will always use __builtin_clz functions and any fallback code 

> is irrelevant: aarch64 i386 ia64 powerpc tilegx x86_64.  (On ia64 the 

> pattern uses conversion to floating point.)

> 

> * The following have clz patterns in GCC, conditionally: alpha arm m68k 

> microblaze mips s390 sparc (and arc).  I have not checked whether in some 

> of those cases the conditions might in fact be true for every 

> configuration for which glibc can be built.

> 

> * The following lack clz patterns in GCC: hppa nios2 sh (and riscv).

> 

> If the configuration lacking clz is also soft-float, converting int to 

> double is an extremely inefficient way ending up calling the libgcc clz 

> implementation (both soft-fp and fp-bit use __builtin_clz).  I think 

> that's sufficient reason to avoid an approach involving conversion to 

> double unless an architecture has opted in to using it as an efficient 

> approach on that architecture.


Thanks for remind about soft-float, also for some architectures that does
have hardware floating pointer units the int to/from float is also a costly
operation.

Regarding index_{first,last}_ fallback implementation, maybe simpler 
implementation which just check the mask bits instead of fallback ones for
leading/trailing zero bit should better, I am open to suggestions here.

> 

> (For arm, for example, clz is supported if "TARGET_32BIT && arm_arch5", so 

> the only configurations without __builtin_clz expanded inline by the 

> compiler are armv4t ones - which are also all soft-float, so the expansion 

> using double can never make sense for arm.)

>
diff mbox series

Patch

diff --git a/config.h.in b/config.h.in
index d928e7d..03bcfe6 100644
--- a/config.h.in
+++ b/config.h.in
@@ -245,4 +245,12 @@ 
    in i386 6 argument syscall issue).  */
 #define CAN_USE_REGISTER_ASM_EBP 0
 
+/* If compiler supports __builtin_ctz{l} without any external depedencies
+   (libgcc for instance).  */
+#define HAVE_BUILTIN_CTZ 0
+
+/* If compiler supports __builtin_clz{l} without any external depedencies
+   (libgcc for instance).  */
+#define HAVE_BUILTIN_CLZ 0
+
 #endif
diff --git a/configure b/configure
index 7a8bd3f..ff4464f 100755
--- a/configure
+++ b/configure
@@ -6592,6 +6592,60 @@  if test $libc_cv_builtin_trap = yes; then
 
 fi
 
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_ctz{l} with no external dependencies" >&5
+$as_echo_n "checking for __builtin_ctz{l} with no external dependencies... " >&6; }
+if ${libc_cv_builtin_ctz+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  libc_cv_builtin_ctz=yes
+echo 'int foo (unsigned long x) { return __builtin_ctz (x); }' > conftest.c
+if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&5'
+  { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5
+  (eval $ac_try) 2>&5
+  ac_status=$?
+  $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
+  test $ac_status = 0; }; }; then
+  if grep '__ctz[s,d]i2' conftest.s > /dev/null; then
+    libc_cv_builtin_ctz=no
+  fi
+fi
+rm -f conftest.c conftest.s
+
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $libc_cv_builtin_ctz" >&5
+$as_echo "$libc_cv_builtin_ctz" >&6; }
+if test x$libc_cv_builtin_ctz = xyes; then
+  $as_echo "#define HAVE_BUILTIN_CTZ 1" >>confdefs.h
+
+fi
+
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_clz{l} with no external dependencies" >&5
+$as_echo_n "checking for __builtin_clz{l} with no external dependencies... " >&6; }
+if ${libc_cv_builtin_clz+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  libc_cv_builtin_clz=yes
+echo 'int foo (unsigned long x) { return __builtin_clz (x); }' > conftest.c
+if { ac_try='${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&5'
+  { { eval echo "\"\$as_me\":${as_lineno-$LINENO}: \"$ac_try\""; } >&5
+  (eval $ac_try) 2>&5
+  ac_status=$?
+  $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
+  test $ac_status = 0; }; }; then
+  if grep '__clz[s,d]i2' conftest.s > /dev/null; then
+    libc_cv_builtin_clz=no
+  fi
+fi
+rm -f conftest.c conftest.s
+
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $libc_cv_builtin_clz" >&5
+$as_echo "$libc_cv_builtin_clz" >&6; }
+if test x$libc_cv_builtin_clz = xyes; then
+  $as_echo "#define HAVE_BUILTIN_CLZ 1" >>confdefs.h
+
+fi
+
 ac_ext=cpp
 ac_cpp='$CXXCPP $CPPFLAGS'
 ac_compile='$CXX -c $CXXFLAGS $CPPFLAGS conftest.$ac_ext >&5'
diff --git a/configure.ac b/configure.ac
index ca1282a..7f9c9f8 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1675,6 +1675,40 @@  if test $libc_cv_builtin_trap = yes; then
   AC_DEFINE([HAVE_BUILTIN_TRAP])
 fi
 
+AC_CACHE_CHECK(for __builtin_ctz{l} with no external dependencies,
+	       libc_cv_builtin_ctz, [dnl
+libc_cv_builtin_ctz=yes
+echo 'int foo (unsigned long x) { return __builtin_ctz (x); }' > conftest.c
+if AC_TRY_COMMAND(${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&AS_MESSAGE_LOG_FD); then
+changequote(,)dnl
+  if grep '__ctz[s,d]i2' conftest.s > /dev/null; then
+    libc_cv_builtin_ctz=no
+  fi
+changequote([,])dnl
+fi
+rm -f conftest.c conftest.s
+])
+if test x$libc_cv_builtin_ctz = xyes; then
+  AC_DEFINE(HAVE_BUILTIN_CTZ)
+fi
+
+AC_CACHE_CHECK(for __builtin_clz{l} with no external dependencies,
+	       libc_cv_builtin_clz, [dnl
+libc_cv_builtin_clz=yes
+echo 'int foo (unsigned long x) { return __builtin_clz (x); }' > conftest.c
+if AC_TRY_COMMAND(${CC-cc} $CFLAGS $CPPFLAGS -S conftest.c -o conftest.s 1>&AS_MESSAGE_LOG_FD); then
+changequote(,)dnl
+  if grep '__clz[s,d]i2' conftest.s > /dev/null; then
+    libc_cv_builtin_clz=no
+  fi
+changequote([,])dnl
+fi
+rm -f conftest.c conftest.s
+])
+if test x$libc_cv_builtin_clz = xyes; then
+  AC_DEFINE(HAVE_BUILTIN_CLZ)
+fi
+
 dnl C++ feature tests.
 AC_LANG_PUSH([C++])
 
diff --git a/sysdeps/generic/string-extbyte.h b/sysdeps/generic/string-extbyte.h
new file mode 100644
index 0000000..69a78ce
--- /dev/null
+++ b/sysdeps/generic/string-extbyte.h
@@ -0,0 +1,35 @@ 
+/* Extract by from memory word.  Generic C version.
+   Copyright (C) 2018 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
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef STRING_EXTBYTE_H
+#define STRING_EXTBYTE_H 1
+
+#include <limits.h>
+#include <endian.h>
+#include <string-optype.h>
+
+static inline unsigned char
+extractbyte (op_t x, unsigned idx)
+{
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    return x >> (idx * CHAR_BIT);
+  else
+    return x >> (sizeof (x) - 1 - idx) * CHAR_BIT;
+}
+
+#endif /* STRING_EXTBYTE_H */
diff --git a/sysdeps/generic/string-fza.h b/sysdeps/generic/string-fza.h
new file mode 100644
index 0000000..ab208bf
--- /dev/null
+++ b/sysdeps/generic/string-fza.h
@@ -0,0 +1,117 @@ 
+/* Basic zero byte detection.  Generic C version.
+   Copyright (C) 2018 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
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef STRING_FZA_H
+#define STRING_FZA_H 1
+
+#include <limits.h>
+#include <string-optype.h>
+
+/* This function returns non-zero if any byte in X is zero.
+   More specifically, at least one bit set within the least significant
+   byte that was zero; other bytes within the word are indeterminate.  */
+
+static inline op_t
+find_zero_low (op_t x)
+{
+  /* This expression comes from
+       https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
+     Subtracting 1 sets 0x80 in a byte that was 0; anding ~x clears
+     0x80 in a byte that was >= 128; anding 0x80 isolates that test bit.  */
+  op_t lsb = (op_t)-1 / 0xff;
+  op_t msb = lsb << (CHAR_BIT - 1);
+  return (x - lsb) & ~x & msb;
+}
+
+/* This function returns at least one bit set within every byte of X that
+   is zero.  The result is exact in that, unlike find_zero_low, all bytes
+   are determinate.  This is usually used for finding the index of the
+   most significant byte that was zero.  */
+
+static inline op_t
+find_zero_all (op_t x)
+{
+  /* For each byte, find not-zero by
+     (0) And 0x7f so that we cannot carry between bytes,
+     (1) Add 0x7f so that non-zero carries into 0x80,
+     (2) Or in the original byte (which might have had 0x80 set).
+     Then invert and mask such that 0x80 is set iff that byte was zero.  */
+  op_t m = ((op_t)-1 / 0xff) * 0x7f;
+  return ~(((x & m) + m) | x | m);
+}
+
+/* With similar caveats, identify bytes that are equal between X1 and X2.  */
+
+static inline op_t
+find_eq_low (op_t x1, op_t x2)
+{
+  return find_zero_low (x1 ^ x2);
+}
+
+static inline op_t
+find_eq_all (op_t x1, op_t x2)
+{
+  return find_zero_all (x1 ^ x2);
+}
+
+/* With similar caveats, identify zero bytes in X1 and bytes that are
+   equal between in X1 and X2.  */
+
+static inline op_t
+find_zero_eq_low (op_t x1, op_t x2)
+{
+  op_t lsb = (op_t)-1 / 0xff;
+  op_t msb = lsb << (CHAR_BIT - 1);
+  op_t eq = x1 ^ x2;
+  return (((x1 - lsb) & ~x1) | ((eq - lsb) & ~eq)) & msb;
+}
+
+static inline op_t
+find_zero_eq_all (op_t x1, op_t x2)
+{
+  op_t m = ((op_t)-1 / 0xff) * 0x7f;
+  op_t eq = x1 ^ x2;
+  op_t c1 = ((x1 & m) + m) | x1;
+  op_t c2 = ((eq & m) + m) | eq;
+  return ~((c1 & c2) | m);
+}
+
+/* With similar caveats, identify zero bytes in X1 and bytes that are
+   not equal between in X1 and X2.  */
+
+static inline op_t
+find_zero_ne_low (op_t x1, op_t x2)
+{
+  op_t m = ((op_t)-1 / 0xff) * 0x7f;
+  op_t eq = x1 ^ x2;
+  op_t nz1 = (x1 + m) | x1;	/* msb set if byte not zero */
+  op_t ne2 = (eq + m) | eq;	/* msb set if byte not equal */
+  return (ne2 | ~nz1) & ~m;	/* msb set if x1 zero or x2 not equal */
+}
+
+static inline op_t
+find_zero_ne_all (op_t x1, op_t x2)
+{
+  op_t m = ((op_t)-1 / 0xff) * 0x7f;
+  op_t eq = x1 ^ x2;
+  op_t nz1 = ((x1 & m) + m) | x1;
+  op_t ne2 = ((eq & m) + m) | eq;
+  return (ne2 | ~nz1) & ~m;
+}
+
+#endif /* STRING_FZA_H */
diff --git a/sysdeps/generic/string-fzb.h b/sysdeps/generic/string-fzb.h
new file mode 100644
index 0000000..d4ab59b
--- /dev/null
+++ b/sysdeps/generic/string-fzb.h
@@ -0,0 +1,49 @@ 
+/* Zero byte detection, boolean.  Generic C version.
+   Copyright (C) 2018 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
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef STRING_FZB_H
+#define STRING_FZB_H 1
+
+#include <endian.h>
+#include <string-fza.h>
+
+/* Determine if any byte within X is zero.  This is a pure boolean test.  */
+
+static inline _Bool
+has_zero (op_t x)
+{
+  return find_zero_low (x) != 0;
+}
+
+/* Likewise, but for byte equality between X1 and X2.  */
+
+static inline _Bool
+has_eq (op_t x1, op_t x2)
+{
+  return find_eq_low (x1, x2) != 0;
+}
+
+/* Likewise, but for zeros in X1 and equal bytes between X1 and X2.  */
+
+static inline _Bool
+has_zero_eq (op_t x1, op_t x2)
+{
+  return find_zero_eq_low (x1, x2);
+}
+
+#endif /* STRING_FZB_H */
diff --git a/sysdeps/generic/string-fzi.h b/sysdeps/generic/string-fzi.h
new file mode 100644
index 0000000..57101f2
--- /dev/null
+++ b/sysdeps/generic/string-fzi.h
@@ -0,0 +1,215 @@ 
+/* Zero byte detection; indexes.  Generic C version.
+   Copyright (C) 2018 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
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef STRING_FZI_H
+#define STRING_FZI_H 1
+
+#include <limits.h>
+#include <endian.h>
+#include <string-fza.h>
+
+/* An improved bitscan routine, multiplying the De Bruijn sequence with a
+   0-1 mask separated by the least significant one bit of a scanned integer
+   or bitboard [1].
+
+   [1] https://chessprogramming.wikispaces.com/Kim+Walisch  */
+
+static inline unsigned
+index_access (const op_t i)
+{
+  static const char index[] =
+  {
+# if __WORDSIZE == 64
+     0, 47,  1, 56, 48, 27,  2, 60,
+    57, 49, 41, 37, 28, 16,  3, 61,
+    54, 58, 35, 52, 50, 42, 21, 44,
+    38, 32, 29, 23, 17, 11,  4, 62,
+    46, 55, 26, 59, 40, 36, 15, 53,
+    34, 51, 20, 43, 31, 22, 10, 45,
+    25, 39, 14, 33, 19, 30,  9, 24,
+    13, 18,  8, 12,  7,  6,  5, 63
+# else
+     0,  9,  1, 10, 13, 21,  2, 29,
+    11, 14, 16, 18, 22, 25,  3, 30,
+     8, 12, 20, 28, 15, 17, 24,  7,
+    19, 27, 23,  6, 26,  5,  4, 31
+# endif
+  };
+  return index[i];
+}
+
+/* For architecture which only provides __builtin_clz{l} (HAVE_BUILTIN_CLZ)
+   and/or __builtin_ctz{l} (HAVE_BUILTIN_CTZ) which uses external libcalls
+   (for intance __c{l,t}z{s,d}i2 from libgcc) the following wrapper provides
+   inline implementation for both count leading zeros and count trailing
+   zeros using branchless computation.  */
+
+static inline unsigned
+__ctz (op_t x)
+{
+#if !HAVE_BUILTIN_CTZ
+  op_t i;
+# if __WORDSIZE == 64
+  i = (x ^ (x - 1)) * 0x03F79D71B4CB0A89ull >> 58;
+# else
+  i = (x ^ (x - 1)) * 0x07C4ACDDU >> 27;
+# endif
+  return index_access (i);
+#else
+  if (sizeof (op_t) == sizeof (long))
+    return __builtin_ctzl (x);
+  else
+    return __builtin_ctzll (x);
+#endif
+};
+
+static inline unsigned
+__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))
+    return __builtin_clzl (x);
+  else
+    return __builtin_clzll (x);
+#endif
+}
+
+/* A subroutine for the index_zero functions.  Given a test word C, return
+   the (memory order) index of the first byte (in memory order) that is
+   non-zero.  */
+
+static inline unsigned int
+index_first_ (op_t c)
+{
+  _Static_assert (sizeof (op_t) == sizeof (long)
+		  || sizeof (op_t) == sizeof (long long),
+		  "Unhandled word size");
+
+  unsigned r;
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    r = __ctz (c);
+  else
+    r = __clz (c);
+  return r / CHAR_BIT;
+}
+
+/* Similarly, but return the (memory order) index of the last byte
+   that is non-zero.  */
+
+static inline unsigned int
+index_last_ (op_t c)
+{
+  _Static_assert (sizeof (op_t) == sizeof (long)
+		  || sizeof (op_t) == sizeof (long long),
+		  "Unhandled word size");
+
+  unsigned r;
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    r = __clz (c);
+  else
+    r = __ctz (c);
+  return sizeof (op_t) - 1 - (r / CHAR_BIT);
+}
+
+/* Given a word X that is known to contain a zero byte, return the
+   index of the first such within the word in memory order.  */
+
+static inline unsigned int
+index_first_zero (op_t x)
+{
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    x = find_zero_low (x);
+  else
+    x = find_zero_all (x);
+  return index_first_ (x);
+}
+
+/* Similarly, but perform the search for byte equality between X1 and X2.  */
+
+static inline unsigned int
+index_first_eq (op_t x1, op_t x2)
+{
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    x1 = find_eq_low (x1, x2);
+  else
+    x1 = find_eq_all (x1, x2);
+  return index_first_ (x1);
+}
+
+/* Similarly, but perform the search for zero within X1 or
+   equality between X1 and X2.  */
+
+static inline unsigned int
+index_first_zero_eq (op_t x1, op_t x2)
+{
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    x1 = find_zero_eq_low (x1, x2);
+  else
+    x1 = find_zero_eq_all (x1, x2);
+  return index_first_ (x1);
+}
+
+/* Similarly, but perform the search for zero within X1 or
+   inequality between X1 and X2.  */
+
+static inline unsigned int
+index_first_zero_ne (op_t x1, op_t x2)
+{
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    x1 = find_zero_ne_low (x1, x2);
+  else
+    x1 = find_zero_ne_all (x1, x2);
+  return index_first_ (x1);
+}
+
+/* Similarly, but search for the last zero within X.  */
+
+static inline unsigned int
+index_last_zero (op_t x)
+{
+  if (__BYTE_ORDER == __LITTLE_ENDIAN)
+    x = find_zero_all (x);
+  else
+    x = find_zero_low (x);
+  return index_last_ (x);
+}
+
+static inline unsigned int
+index_last_eq (op_t x1, op_t x2)
+{
+  return index_last_zero (x1 ^ x2);
+}
+
+#endif /* STRING_FZI_H */