Re: [PATCH]: Add popcount and popcount caching for sbitmaps

[Ian Lance Taylor <iant at google dot com>]

"Daniel Berlin" <dberlin@dberlin.org> writes:

> +#if GCC_VERSION >= 3400
> +#define do_popcount(x) __builtin_popcountl((x))
> +#else
> +static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE);
> +#define do_popcount(x) sbitmap_elt_popcount((x))
> +#endif

When the builtin function exists, we are going to pass it a value of
type SBITMAP_ELT_TYPE, which is "unsigned HOST_WIDEST_FAST_INT".
__builtin_popcountl accepts a value of type "unsigned long".  This
will fail for any system which sets use_long_long_for_widest_fast_int
to "yes" in config.host.  Currently there is one such system:
ia64-hpux.  On such a system you need to call __builtin_popcountll.

The way to write this is something like:

#if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
#define do_popcount(x) __builtin_popcountl(x)
#elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG_LONG
#define do_popcount(x) __builtin_popcountll(x)
#else
#error "internal error: sbitmap.h and hwint.h are inconsistent"
#endif

> +void
> +sbitmap_verify_popcount (sbitmap a)
> +{
> +  unsigned long count = 0;
> +  unsigned ix;
> +  unsigned int lastword;
> +  
> +  if (!a->popcount)
> +    return;
> +
> +  lastword = a->size;
> +  for (ix = 0; ix < lastword; ix++)
> +    {
> +      if (a->popcount)
> +	{
> +	  count += a->popcount[ix];
> +	  gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
> +	}
> +    }
> +}
> +#endif

You don't need to check a->popcount in the loop, you already checked
it before the loop.

I don't know why you are putting a total into count.  It should be
removed unless I'm missing some reason for it to exist.

> @@ -45,7 +83,26 @@ sbitmap_alloc (unsigned int n_elms)
>    bmap = xmalloc (amt);
>    bmap->n_bits = n_elms;
>    bmap->size = size;
> -  bmap->bytes = bytes;
> +  bmap->popcount = NULL;
> +  return bmap;
> +}
> +
> +/* Allocate a simple bitmap of N_ELMS bits, and a popcount array.  */
> +
> +sbitmap
> +sbitmap_alloc_with_popcount (unsigned int n_elms)
> +{
> +  unsigned int bytes, size, amt;
> +  sbitmap bmap;
> +
> +  size = SBITMAP_SET_SIZE (n_elms);
> +  bytes = size * sizeof (SBITMAP_ELT_TYPE);
> +  amt = (sizeof (struct simple_bitmap_def)
> +	 + bytes - sizeof (SBITMAP_ELT_TYPE));
> +  bmap = xmalloc (amt);
> +  bmap->n_bits = n_elms;
> +  bmap->size = size;
> +  bmap->popcount = xmalloc (size * sizeof (unsigned char));
>    return bmap;
>  }

This is duplication.  I think it would be cleaner to just call
sbitmap_alloc and then set the popcount field.  Or have both of them
call some other function which returns the size, or something like
that.

> +/* Count the number of bits in SBITMAP a, up to bit MAXBIT.  */
> +
> +unsigned long
> +sbitmap_popcount (sbitmap a, unsigned long maxbit)
> +{
> +  unsigned long count = 0;
> +  unsigned ix;
> +  unsigned int lastword;
> +
> +  if (maxbit == 0)
> +    return 0;
> +  
> +  if (maxbit >= a->n_bits)
> +    maxbit = a->n_bits;
> +
> +  /* Count the bits in the full word.  */
> +  lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1)-1);

There should be spaces around the '-'.


OK with those changes.

Thanks.

Ian