[PATCH] Make BITMAP_WORD more easily configurable

[PATCH] Make BITMAP_WORD more easily configurable

[Richard Biener]

I've played with different BITMAP_WORD and BITMAP_ELEMENT_WORDS
values and found the code using CTZ and friends a bit unwieldly
to adjust.  So I came up with a set of macros wrapping them
(_maybe_ inline overloads would be a cleaner solution, but ...).

Specifically it looks like for PR91257 making bitmap_element
cache-line aligned and 32byte in size by using an unsigned
int BITMAP_WORD and BITMAP_ELEMENT_WORDS 3 (thus reducing
the load factor from 0.4 to 0.375) is a slight win (in both
memory use and compile-time).  Enlarging to 64 bytes and keeping
unsigned long (and the padding) is worst, even using only
a single unsigned long (but then aligning to 32bytes again)
is faster than the current state.  Surprisingly the division/modulo
by 3 or the larger number of loads/stores didn't matter or were
at least offsetted by reliably touching only a single cache-line
per bitmap_element.

I would guess the optimal setting should depend on the host.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

Any objection to the macro-ification below?

Richard.

2019-07-30  Richard Biener  <rguenther@suse.de>

	* bitmap.h (BITMAP_WORD_CTZ): New define.
	(BITMAP_WORD_CLZ): Likewise.
	(BITMAP_WORD_POPCOUNT): Likewise.
	(bmp_iter_next_bit): Use BITMAP_WORD_CTZ, remove assert.
	* bitmap.c (bitmap_count_bits_in_word): use BITMAP_WORD_POPCOUNT.
	(bitmap_single_bit_set_p): likewise.
	(bitmap_first_set_bit): Use BITMAP_WORD_CTZ, remove assert.
	(bitmap_last_set_bit): Use BITMAP_WORD_CLZ, remove assert.

Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c	(revision 273795)
+++ gcc/bitmap.c	(working copy)
@@ -1016,7 +1020,7 @@ bitmap_count_bits_in_word (const BITMAP_
 #if GCC_VERSION >= 3400
       /* Note that popcountl matches BITMAP_WORD in type, so the actual size
 	 of BITMAP_WORD is not material.  */
-      count += __builtin_popcountl (bits[ix]);
+      count += BITMAP_WORD_POPCOUNT (bits[ix]);
 #else
       count += bitmap_popcount (bits[ix]);
 #endif
@@ -1101,7 +1105,7 @@ bitmap_single_bit_set_p (const_bitmap a)
 #if GCC_VERSION >= 3400
       /* Note that popcountl matches BITMAP_WORD in type, so the actual size
 	 of BITMAP_WORD is not material.  */
-      count += __builtin_popcountl (elt->bits[ix]);
+      count += BITMAP_WORD_POPCOUNT (elt->bits[ix]);
 #else
       count += bitmap_popcount (elt->bits[ix]);
 #endif
@@ -1142,8 +1146,7 @@ bitmap_first_set_bit (const_bitmap a)
   bit_no += ix * BITMAP_WORD_BITS;
 
 #if GCC_VERSION >= 3004
-  gcc_assert (sizeof (long) == sizeof (word));
-  bit_no += __builtin_ctzl (word);
+  bit_no += BITMAP_WORD_CTZ (word);
 #else
   /* Binary search for the first set bit.  */
 #if BITMAP_WORD_BITS > 64
@@ -1200,8 +1203,7 @@ bitmap_last_set_bit (const_bitmap a)
  found_bit:
   bit_no += ix * BITMAP_WORD_BITS;
 #if GCC_VERSION >= 3004
-  gcc_assert (sizeof (long) == sizeof (word));
-  bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
+  bit_no += BITMAP_WORD_BITS - BITMAP_WORD_CLZ (word) - 1;
 #else
   /* Hopefully this is a twos-complement host...  */
   BITMAP_WORD x = word;
Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h	(revision 273795)
+++ gcc/bitmap.h	(working copy)
@@ -272,6 +272,10 @@ extern mem_alloc_description<bitmap_usag
 /* Fundamental storage type for bitmap.  */
 
 typedef unsigned long BITMAP_WORD;
+/* Word primitives.  */
+#define BITMAP_WORD_CTZ __builtin_ctzl
+#define BITMAP_WORD_CLZ __builtin_clzl
+#define BITMAP_WORD_POPCOUNT __builtin_popcountl
 /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
    it is used in preprocessor directives -- hence the 1u.  */
 #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
@@ -683,8 +688,7 @@ bmp_iter_next_bit (bitmap_iterator * bi,
 {
 #if (GCC_VERSION >= 3004)
   {
-    unsigned int n = __builtin_ctzl (bi->bits);
-    gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
+    unsigned int n = BITMAP_WORD_CTZ (bi->bits);
     bi->bits >>= n;
     *bit_no += n;
   }

Re: [PATCH] Make BITMAP_WORD more easily configurable

[Martin Sebor]

On 7/30/19 8:37 AM, Richard Biener wrote:
> 
> I've played with different BITMAP_WORD and BITMAP_ELEMENT_WORDS
> values and found the code using CTZ and friends a bit unwieldly
> to adjust.  So I came up with a set of macros wrapping them
> (_maybe_ inline overloads would be a cleaner solution, but ...).
> 
> Specifically it looks like for PR91257 making bitmap_element
> cache-line aligned and 32byte in size by using an unsigned
> int BITMAP_WORD and BITMAP_ELEMENT_WORDS 3 (thus reducing
> the load factor from 0.4 to 0.375) is a slight win (in both
> memory use and compile-time).  Enlarging to 64 bytes and keeping
> unsigned long (and the padding) is worst, even using only
> a single unsigned long (but then aligning to 32bytes again)
> is faster than the current state.  Surprisingly the division/modulo
> by 3 or the larger number of loads/stores didn't matter or were
> at least offsetted by reliably touching only a single cache-line
> per bitmap_element.
> 
> I would guess the optimal setting should depend on the host.
> 
> Bootstrap & regtest running on x86_64-unknown-linux-gnu.
> 
> Any objection to the macro-ification below?

The built-ins are general purpose (but poorly named) and could be
handy elsewhere (I just recently looked for one of them) so rather
than adding BITMAP_WORD_CTZ et al. to bitmap (and continuing to
support the GCC 3 conditional in the bitmap code) I'd suggest
introducing a general purpose wrapper function with a good name
as the portable interface to __builtin_ctz et al.

Say something like this POC:

   static inline unsigned
   count_trailing_zeros (unsigned x)
   {
   #if (GCC_VERSION >= 3004)
     return __builtin_ctz (x);
   #else
     unsigned n = 0;
     while ((n < sizeof n * CHAR_BIT) && !(x & 1))
       {
         x >>= 1;
         ++n;
        }
     return n;
   #endif
   }

Martin

> Richard.
> 
> 2019-07-30  Richard Biener  <rguenther@suse.de>
> 
> 	* bitmap.h (BITMAP_WORD_CTZ): New define.
> 	(BITMAP_WORD_CLZ): Likewise.
> 	(BITMAP_WORD_POPCOUNT): Likewise.
> 	(bmp_iter_next_bit): Use BITMAP_WORD_CTZ, remove assert.
> 	* bitmap.c (bitmap_count_bits_in_word): use BITMAP_WORD_POPCOUNT.
> 	(bitmap_single_bit_set_p): likewise.
> 	(bitmap_first_set_bit): Use BITMAP_WORD_CTZ, remove assert.
> 	(bitmap_last_set_bit): Use BITMAP_WORD_CLZ, remove assert.
> 
> Index: gcc/bitmap.c
> ===================================================================
> --- gcc/bitmap.c	(revision 273795)
> +++ gcc/bitmap.c	(working copy)
> @@ -1016,7 +1020,7 @@ bitmap_count_bits_in_word (const BITMAP_
>   #if GCC_VERSION >= 3400
>         /* Note that popcountl matches BITMAP_WORD in type, so the actual size
>   	 of BITMAP_WORD is not material.  */
> -      count += __builtin_popcountl (bits[ix]);
> +      count += BITMAP_WORD_POPCOUNT (bits[ix]);
>   #else
>         count += bitmap_popcount (bits[ix]);
>   #endif
> @@ -1101,7 +1105,7 @@ bitmap_single_bit_set_p (const_bitmap a)
>   #if GCC_VERSION >= 3400
>         /* Note that popcountl matches BITMAP_WORD in type, so the actual size
>   	 of BITMAP_WORD is not material.  */
> -      count += __builtin_popcountl (elt->bits[ix]);
> +      count += BITMAP_WORD_POPCOUNT (elt->bits[ix]);
>   #else
>         count += bitmap_popcount (elt->bits[ix]);
>   #endif
> @@ -1142,8 +1146,7 @@ bitmap_first_set_bit (const_bitmap a)
>     bit_no += ix * BITMAP_WORD_BITS;
>   
>   #if GCC_VERSION >= 3004
> -  gcc_assert (sizeof (long) == sizeof (word));
> -  bit_no += __builtin_ctzl (word);
> +  bit_no += BITMAP_WORD_CTZ (word);
>   #else
>     /* Binary search for the first set bit.  */
>   #if BITMAP_WORD_BITS > 64
> @@ -1200,8 +1203,7 @@ bitmap_last_set_bit (const_bitmap a)
>    found_bit:
>     bit_no += ix * BITMAP_WORD_BITS;
>   #if GCC_VERSION >= 3004
> -  gcc_assert (sizeof (long) == sizeof (word));
> -  bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1;
> +  bit_no += BITMAP_WORD_BITS - BITMAP_WORD_CLZ (word) - 1;
>   #else
>     /* Hopefully this is a twos-complement host...  */
>     BITMAP_WORD x = word;
> Index: gcc/bitmap.h
> ===================================================================
> --- gcc/bitmap.h	(revision 273795)
> +++ gcc/bitmap.h	(working copy)
> @@ -272,6 +272,10 @@ extern mem_alloc_description<bitmap_usag
>   /* Fundamental storage type for bitmap.  */
>   
>   typedef unsigned long BITMAP_WORD;
> +/* Word primitives.  */
> +#define BITMAP_WORD_CTZ __builtin_ctzl
> +#define BITMAP_WORD_CLZ __builtin_clzl
> +#define BITMAP_WORD_POPCOUNT __builtin_popcountl
>   /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
>      it is used in preprocessor directives -- hence the 1u.  */
>   #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
> @@ -683,8 +688,7 @@ bmp_iter_next_bit (bitmap_iterator * bi,
>   {
>   #if (GCC_VERSION >= 3004)
>     {
> -    unsigned int n = __builtin_ctzl (bi->bits);
> -    gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
> +    unsigned int n = BITMAP_WORD_CTZ (bi->bits);
>       bi->bits >>= n;
>       *bit_no += n;
>     }
> 

Re: [PATCH] Make BITMAP_WORD more easily configurable

[Martin Sebor]

On 7/30/19 9:19 AM, Jakub Jelinek wrote:
> On Tue, Jul 30, 2019 at 09:16:45AM -0600, Martin Sebor wrote:
>> Say something like this POC:
> 
> We have those already, see ctz_hwi, clz_hwi etc.
> The thing is that BITMAP_WORD isn't always the same type as unsigned
> HOST_WIDE_INT, and so we need ones with the BITMAP_WORD type.

That sounds like a problem overloading would solve to the benefit
of all clients.  I.e., overload count_trailing_zeros (or whatever
other name) to take integer arguments of all widths (signed and
unsigned) and call the appropriate built-in from each.  That way
we just have to remember one function name and know that it will
be the right choice regardless of the type of the argument.

Martin

Re: [PATCH] Make BITMAP_WORD more easily configurable

[Jakub Jelinek]

On Tue, Jul 30, 2019 at 09:16:45AM -0600, Martin Sebor wrote:
> Say something like this POC:

We have those already, see ctz_hwi, clz_hwi etc.
The thing is that BITMAP_WORD isn't always the same type as unsigned
HOST_WIDE_INT, and so we need ones with the BITMAP_WORD type.

	Jakub

Re: [PATCH] Make BITMAP_WORD more easily configurable

[Richard Biener]

On Tue, 30 Jul 2019, Martin Sebor wrote:

> On 7/30/19 9:19 AM, Jakub Jelinek wrote:
> > On Tue, Jul 30, 2019 at 09:16:45AM -0600, Martin Sebor wrote:
> > > Say something like this POC:
> > 
> > We have those already, see ctz_hwi, clz_hwi etc.
> > The thing is that BITMAP_WORD isn't always the same type as unsigned
> > HOST_WIDE_INT, and so we need ones with the BITMAP_WORD type.
> 
> That sounds like a problem overloading would solve to the benefit
> of all clients.  I.e., overload count_trailing_zeros (or whatever
> other name) to take integer arguments of all widths (signed and
> unsigned) and call the appropriate built-in from each.  That way
> we just have to remember one function name and know that it will
> be the right choice regardless of the type of the argument.

The problem with clz at least is that you have to make sure
to only allow overloads to exactly match the type of the
operand since semantics change once you do any promotion.
For popcount and ctz that's only an issue for signed arguments,
but still.

And I don't see any optimization of (uint){clzl,popcountl}((ulong)uintvar)
-> {clz,popcount} (uintvar)

unsigned int foo (unsigned int x)
{
  unsigned long y = x;
  unsigned long z = __builtin_popcountl (y);
  return z;
}

calls __popcountdi2 for me.

So if you dislike the macros then we could add 
{popcount,clz,ctz}_bitmap_word () functions.

Still having the plumbing in once place looks like an improvement
to me - not sure if your comments were an objection to the original
patch?

Thanks,
Richard.

Re: [PATCH] Make BITMAP_WORD more easily configurable

[Martin Sebor]

On 7/31/19 4:00 AM, Richard Biener wrote:
> On Tue, 30 Jul 2019, Martin Sebor wrote:
> 
>> On 7/30/19 9:19 AM, Jakub Jelinek wrote:
>>> On Tue, Jul 30, 2019 at 09:16:45AM -0600, Martin Sebor wrote:
>>>> Say something like this POC:
>>>
>>> We have those already, see ctz_hwi, clz_hwi etc.
>>> The thing is that BITMAP_WORD isn't always the same type as unsigned
>>> HOST_WIDE_INT, and so we need ones with the BITMAP_WORD type.
>>
>> That sounds like a problem overloading would solve to the benefit
>> of all clients.  I.e., overload count_trailing_zeros (or whatever
>> other name) to take integer arguments of all widths (signed and
>> unsigned) and call the appropriate built-in from each.  That way
>> we just have to remember one function name and know that it will
>> be the right choice regardless of the type of the argument.
> 
> The problem with clz at least is that you have to make sure
> to only allow overloads to exactly match the type of the
> operand since semantics change once you do any promotion.
> For popcount and ctz that's only an issue for signed arguments,
> but still.
> 
> And I don't see any optimization of (uint){clzl,popcountl}((ulong)uintvar)
> -> {clz,popcount} (uintvar)
> 
> unsigned int foo (unsigned int x)
> {
>    unsigned long y = x;
>    unsigned long z = __builtin_popcountl (y);
>    return z;
> }
> 
> calls __popcountdi2 for me.
> 
> So if you dislike the macros then we could add
> {popcount,clz,ctz}_bitmap_word () functions.
> 
> Still having the plumbing in once place looks like an improvement
> to me - not sure if your comments were an objection to the original
> patch?

Not an objection, just as an encouragement to consider going
the wrapper route you mentioned.  I think that would make
for a more broadly applicable improvement with a more user
friendly interface than what's available today.

Martin

Re: [PATCH] Make BITMAP_WORD more easily configurable

[Richard Biener]

On Wed, 31 Jul 2019, Martin Sebor wrote:

> On 7/31/19 4:00 AM, Richard Biener wrote:
> > On Tue, 30 Jul 2019, Martin Sebor wrote:
> > 
> > > On 7/30/19 9:19 AM, Jakub Jelinek wrote:
> > > > On Tue, Jul 30, 2019 at 09:16:45AM -0600, Martin Sebor wrote:
> > > > > Say something like this POC:
> > > > 
> > > > We have those already, see ctz_hwi, clz_hwi etc.
> > > > The thing is that BITMAP_WORD isn't always the same type as unsigned
> > > > HOST_WIDE_INT, and so we need ones with the BITMAP_WORD type.
> > > 
> > > That sounds like a problem overloading would solve to the benefit
> > > of all clients.  I.e., overload count_trailing_zeros (or whatever
> > > other name) to take integer arguments of all widths (signed and
> > > unsigned) and call the appropriate built-in from each.  That way
> > > we just have to remember one function name and know that it will
> > > be the right choice regardless of the type of the argument.
> > 
> > The problem with clz at least is that you have to make sure
> > to only allow overloads to exactly match the type of the
> > operand since semantics change once you do any promotion.
> > For popcount and ctz that's only an issue for signed arguments,
> > but still.
> > 
> > And I don't see any optimization of (uint){clzl,popcountl}((ulong)uintvar)
> > -> {clz,popcount} (uintvar)
> > 
> > unsigned int foo (unsigned int x)
> > {
> >    unsigned long y = x;
> >    unsigned long z = __builtin_popcountl (y);
> >    return z;
> > }
> > 
> > calls __popcountdi2 for me.
> > 
> > So if you dislike the macros then we could add
> > {popcount,clz,ctz}_bitmap_word () functions.
> > 
> > Still having the plumbing in once place looks like an improvement
> > to me - not sure if your comments were an objection to the original
> > patch?
> 
> Not an objection, just as an encouragement to consider going
> the wrapper route you mentioned.  I think that would make
> for a more broadly applicable improvement with a more user
> friendly interface than what's available today.

Overload resolution is a bit weird given it seems to be applied
after promotion and given it is not matching "identical" types
like long long and long as soon as I have two overloads, one
for int and one for long.

So I'd rather have the type explicit in the name of the function
since semantics depend on the actual chosen computation type.

Otherwise we'd have to provide overloads for all standard integer
types and simply not implement some (but what's the point then...).
For that using templates and specialization is probably a better
match then (same issue with long vs. long long but that could
be solved with more template magic).

template <typename T>
int
gcc_popcount (T) { typename T::not implemented; }

template <>
int
gcc_popcount (HOST_WIDE_INT x) { return popcount_whi (x); }

etc.

?  (or xpopcount to mimic libiberty style naming)

As said it would still say not implemented for 'long long' or
'long' depending on how HOST_WIDE_INT is defined.  More C++-fu
can solve this though.

Richard.

Re: [PATCH] Make BITMAP_WORD more easily configurable

[Martin Sebor]

On 8/1/19 2:49 AM, Richard Biener wrote:
> On Wed, 31 Jul 2019, Martin Sebor wrote:
> 
>> On 7/31/19 4:00 AM, Richard Biener wrote:
>>> On Tue, 30 Jul 2019, Martin Sebor wrote:
>>>
>>>> On 7/30/19 9:19 AM, Jakub Jelinek wrote:
>>>>> On Tue, Jul 30, 2019 at 09:16:45AM -0600, Martin Sebor wrote:
>>>>>> Say something like this POC:
>>>>>
>>>>> We have those already, see ctz_hwi, clz_hwi etc.
>>>>> The thing is that BITMAP_WORD isn't always the same type as unsigned
>>>>> HOST_WIDE_INT, and so we need ones with the BITMAP_WORD type.
>>>>
>>>> That sounds like a problem overloading would solve to the benefit
>>>> of all clients.  I.e., overload count_trailing_zeros (or whatever
>>>> other name) to take integer arguments of all widths (signed and
>>>> unsigned) and call the appropriate built-in from each.  That way
>>>> we just have to remember one function name and know that it will
>>>> be the right choice regardless of the type of the argument.
>>>
>>> The problem with clz at least is that you have to make sure
>>> to only allow overloads to exactly match the type of the
>>> operand since semantics change once you do any promotion.
>>> For popcount and ctz that's only an issue for signed arguments,
>>> but still.
>>>
>>> And I don't see any optimization of (uint){clzl,popcountl}((ulong)uintvar)
>>> -> {clz,popcount} (uintvar)
>>>
>>> unsigned int foo (unsigned int x)
>>> {
>>>     unsigned long y = x;
>>>     unsigned long z = __builtin_popcountl (y);
>>>     return z;
>>> }
>>>
>>> calls __popcountdi2 for me.
>>>
>>> So if you dislike the macros then we could add
>>> {popcount,clz,ctz}_bitmap_word () functions.
>>>
>>> Still having the plumbing in once place looks like an improvement
>>> to me - not sure if your comments were an objection to the original
>>> patch?
>>
>> Not an objection, just as an encouragement to consider going
>> the wrapper route you mentioned.  I think that would make
>> for a more broadly applicable improvement with a more user
>> friendly interface than what's available today.
> 
> Overload resolution is a bit weird given it seems to be applied
> after promotion and given it is not matching "identical" types
> like long long and long as soon as I have two overloads, one
> for int and one for long.
> 
> So I'd rather have the type explicit in the name of the function
> since semantics depend on the actual chosen computation type.
> 
> Otherwise we'd have to provide overloads for all standard integer
> types and simply not implement some (but what's the point then...).
> For that using templates and specialization is probably a better
> match then (same issue with long vs. long long but that could
> be solved with more template magic).
> 
> template <typename T>
> int
> gcc_popcount (T) { typename T::not implemented; }
> 
> template <>
> int
> gcc_popcount (HOST_WIDE_INT x) { return popcount_whi (x); }
> 
> etc.
> 
> ?  (or xpopcount to mimic libiberty style naming)

With the overload approach one would need to be provided for each
integer type starting with int, both signed and unsigned.  With
C++ templates (SFINAE and type traits) there may be ways to
reduce the number of definitions at the cost of the complexity
of the implementation (while still keeping the interface simple).

The biggest drawback of "mangling" the type name in the names of
functions is that users have to know what type they're dealing
with, and remember the mangling scheme (is it foo_ull or foo_llu
or foo_ullong or something else?).  Even in C with typedefs that's
an error-prone PITA.  A mistake can cause bugs due to slicing.
In C++ it makes the functions unsuitable for use in templates.
In both languages it makes it difficult to change the data types
used in data structures.  Going from long to int like in your
experiment means changing the code that works on the data.  C
solves it by "parameterizing" everything on macros.  The C++
approach is templates.  Mixing the two doesn't work very well.

Martin

> 
> As said it would still say not implemented for 'long long' or
> 'long' depending on how HOST_WIDE_INT is defined.  More C++-fu
> can solve this though.
> 
> Richard.
>