This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


On 27 Dec 2006 14:44:25 -0800, Ian Lance Taylor <iant@google.com> wrote:
"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.

Urgh, i noticed this afterwards, actually. Fixed the way you've suggested.


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.

Fixed.

> @@ -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.
Fixed.


> +/* 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 '-'.

Fixed


OK with those changes.

Thanks.

Ian



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]