[PATCH]: Add popcount and popcount caching for sbitmaps

Daniel Berlin dberlin@dberlin.org
Thu Dec 28 05:44:00 GMT 2006


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
>



More information about the Gcc-patches mailing list