This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Add popcount and popcount caching for sbitmaps
- From: "Daniel Berlin" <dberlin at dberlin dot org>
- To: gcc-patches <gcc-patches at gcc dot gnu dot org>
- Cc: "Ian Lance Taylor" <iant at google dot com>
- Date: Wed, 27 Dec 2006 11:51:55 -0500
- Subject: [PATCH]: Add popcount and popcount caching for sbitmaps
This patch adds support for popcount's to sbitmaps, and adds an
optional popcount cache.
I reused the useless "bytes" member of the sbitmap (which was just
storing sbitmap->size * sizeof (SBITMAP_ELT_TYPE)), so that no extra
memory is taken by sbitmaps that do not want to cache the popcount.
The main usage of caching the popcount is in my upcoming "faster
sparse bitmap" patch, where we store an sbitmap word mask saying which
words have bits set, and a single contiguous array of those bits.
In such a representation, the array member that stores bit x is
sbitmap_popcount (word_mask, x / word size).
The caching helps significantly (real world measurements) in speeding
up the bitmap accesses.
The default is still to allocate an sbitmap without popcount, and i've
verified there are no slowdowns from using this patch (which also
changes RESET_BIT/SET_BIT to be functions).
I have also added asserts to the functions that don't respect the
popcount cache that there is no popcount cache.
Bootstrapped and regtested on i686-darwin.
Okay for mainline?
2006-12-27 Daniel Berlin <dberlin@dberlin.org>
* sbitmap.c (BITMAP_DEBUGGING): New macro.
(do_popcount): Ditto.
(sbitmap_verify_popcount): New function.
(sbitmap_alloc): Set popcount to NULL, remove set of bytes
member.
(sbitmap_alloc_with_popcount): New function.
(sbitmap_resize): Remove uses of bytes member and update
popcount.
(sbitmap_realloc): Remove uses of bytes member.
(sbitmap_copy): Copy popcount.
(sbitmap_copy_n): New function.
(sbitmap_zero): Update popcount cache.
(sbitmap_ones): Ditto.
(sbitmap_a_and_b): Ditto.
(sbitmap_a_or_b): Ditto.
(sbitmap_a_xor_b): Ditto.
(sbitmap_union_of_diff_cg): Assert non-existence of popcount
cache.
(sbitmap_union_of_diff): Ditto.
(sbitmap_not): Ditto.
(sbitmap_difference): Ditto.
(sbitmap_a_and_b_cg): Ditto.
(sbitmap_a_xor_b_cg): Ditto.
(sbitmap_a_or_b_cg): Ditto.
(sbitmap_a_or_b_and_c_cg): Ditto.
(sbitmap_a_and_b_or_c_cg): Ditto.
(sbitmap_intersection_of_succs): Ditto.
(sbitmap_intersection_of_preds): Ditto.
(sbitmap_union_of_succs): Ditto.
(sbitmap_union_of_preds): Ditto.
(popcount_table): New.
(sbitmap_elt_popcount): New function.
(sbitmap_popcount): Ditto.
* sbitmap.h (sbitmap): Remove bytes member.
Add popcount member.
(SET_BIT): Macro turned into function.
(RESET_BIT): Ditto.
(SBITMAP_SIZE_BYTES): New macro.
(sbitmap_free): Free popcount too.
(sbitmap_alloc_with_popcount): New prototype.
(sbitmap_copy_n): Ditto.
(sbitmap_verify_popcount): Ditto.
Index: sbitmap.c
===================================================================
--- sbitmap.c (revision 120211)
+++ sbitmap.c (working copy)
@@ -28,6 +28,44 @@ Software Foundation, 51 Franklin Street,
#include "obstack.h"
#include "basic-block.h"
+#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
+
+/* This macro controls debugging that is as expensive as the
+ operations it verifies. */
+
+/* #define BITMAP_DEBUGGING */
+#ifdef BITMAP_DEBUGGING
+
+/* Verify the population count of sbitmap A matches the cached value,
+ if there is a cached value. */
+
+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
+
/* Bitmap manipulation routines. */
/* Allocate a simple bitmap of N_ELMS bits. */
@@ -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;
}
@@ -61,18 +118,22 @@ sbitmap_resize (sbitmap bmap, unsigned i
size = SBITMAP_SET_SIZE (n_elms);
bytes = size * sizeof (SBITMAP_ELT_TYPE);
- if (bytes > bmap->bytes)
+ if (bytes > SBITMAP_SIZE_BYTES (bmap))
{
amt = (sizeof (struct simple_bitmap_def)
+ bytes - sizeof (SBITMAP_ELT_TYPE));
bmap = xrealloc (bmap, amt);
+ if (bmap->popcount)
+ bmap->popcount = xrealloc (bmap->popcount,
+ size * sizeof (unsigned char));
}
if (n_elms > bmap->n_bits)
{
if (def)
{
- memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes);
+ memset (bmap->elms + bmap->size, -1,
+ bytes - SBITMAP_SIZE_BYTES (bmap));
/* Set the new bits if the original last element. */
last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
@@ -87,20 +148,31 @@ sbitmap_resize (sbitmap bmap, unsigned i
&= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
}
else
- memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes);
+ {
+ memset (bmap->elms + bmap->size, 0,
+ bytes - SBITMAP_SIZE_BYTES (bmap));
+ if (bmap->popcount)
+ memset (bmap->popcount + bmap->size, 0,
+ (size * sizeof (unsigned char))
+ - (bmap->size * sizeof (unsigned char)));
+
+ }
}
else if (n_elms < bmap->n_bits)
{
/* Clear the surplus bits in the last word. */
last_bit = n_elms % SBITMAP_ELT_BITS;
if (last_bit)
- bmap->elms[size - 1]
- &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
+ {
+ bmap->elms[size - 1]
+ &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
+ if (bmap->popcount)
+ bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
+ }
}
bmap->n_bits = n_elms;
bmap->size = size;
- bmap->bytes = bytes;
return bmap;
}
@@ -117,7 +189,7 @@ sbitmap_realloc (sbitmap src, unsigned i
amt = (sizeof (struct simple_bitmap_def)
+ bytes - sizeof (SBITMAP_ELT_TYPE));
- if (src->bytes >= bytes)
+ if (SBITMAP_SIZE_BYTES (src) >= bytes)
{
src->n_bits = n_elms;
return src;
@@ -126,7 +198,6 @@ sbitmap_realloc (sbitmap src, unsigned i
bmap = (sbitmap) xrealloc (src, amt);
bmap->n_bits = n_elms;
bmap->size = size;
- bmap->bytes = bytes;
return bmap;
}
@@ -166,7 +237,7 @@ sbitmap_vector_alloc (unsigned int n_vec
bitmap_vector[i] = b;
b->n_bits = n_elms;
b->size = size;
- b->bytes = bytes;
+ b->popcount = NULL;
}
return bitmap_vector;
@@ -178,6 +249,18 @@ void
sbitmap_copy (sbitmap dst, sbitmap src)
{
memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
+ if (dst->popcount)
+ memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
+}
+
+/* Copy the first N elements of sbitmap SRC to DST. */
+
+void
+sbitmap_copy_n (sbitmap dst, sbitmap src, unsigned int n)
+{
+ memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
+ if (dst->popcount)
+ memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
}
/* Determine if a == b. */
@@ -192,7 +275,9 @@ sbitmap_equal (sbitmap a, sbitmap b)
void
sbitmap_zero (sbitmap bmap)
{
- memset (bmap->elms, 0, bmap->bytes);
+ memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
+ if (bmap->popcount)
+ memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
}
/* Set all elements in a bitmap to ones. */
@@ -202,12 +287,19 @@ sbitmap_ones (sbitmap bmap)
{
unsigned int last_bit;
- memset (bmap->elms, -1, bmap->bytes);
+ memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
+ if (bmap->popcount)
+ memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
if (last_bit)
- bmap->elms[bmap->size - 1]
- = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
+ {
+ bmap->elms[bmap->size - 1]
+ = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
+ if (bmap->popcount)
+ bmap->popcount[bmap->size - 1]
+ = do_popcount (bmap->elms[bmap->size - 1]);
+ }
}
/* Zero a vector of N_VECS bitmaps. */
@@ -246,6 +338,8 @@ sbitmap_union_of_diff_cg (sbitmap dst, s
sbitmap_ptr cp = c->elms;
SBITMAP_ELT_TYPE changed = 0;
+ gcc_assert (!dst->popcount);
+
for (i = 0; i < n; i++)
{
SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
@@ -265,6 +359,9 @@ sbitmap_union_of_diff (sbitmap dst, sbit
sbitmap_ptr bp = b->elms;
sbitmap_ptr cp = c->elms;
+ gcc_assert (!dst->popcount && !a->popcount
+ && !b->popcount && !c->popcount);
+
for (i = 0; i < n; i++)
*dstp++ = *ap++ | (*bp++ & ~*cp++);
}
@@ -279,6 +376,8 @@ sbitmap_not (sbitmap dst, sbitmap src)
sbitmap_ptr srcp = src->elms;
unsigned int last_bit;
+ gcc_assert (!dst->popcount);
+
for (i = 0; i < n; i++)
*dstp++ = ~*srcp++;
@@ -301,6 +400,8 @@ sbitmap_difference (sbitmap dst, sbitmap
sbitmap_ptr ap = a->elms;
sbitmap_ptr bp = b->elms;
+ gcc_assert (!dst->popcount);
+
/* A should be at least as large as DEST, to have a defined source. */
gcc_assert (a->size >= dst_size);
/* If minuend is smaller, we simply pretend it to be zero bits, i.e.
@@ -346,6 +447,8 @@ sbitmap_a_and_b_cg (sbitmap dst, sbitmap
sbitmap_ptr bp = b->elms;
SBITMAP_ELT_TYPE changed = 0;
+ gcc_assert (!dst->popcount);
+
for (i = 0; i < n; i++)
{
SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
@@ -363,9 +466,25 @@ sbitmap_a_and_b (sbitmap dst, sbitmap a,
sbitmap_ptr dstp = dst->elms;
sbitmap_ptr ap = a->elms;
sbitmap_ptr bp = b->elms;
+ bool has_popcount = dst->popcount != NULL;
+ unsigned char *popcountp = dst->popcount;
for (i = 0; i < n; i++)
- *dstp++ = *ap++ & *bp++;
+ {
+ SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
+ if (has_popcount)
+ {
+ bool wordchanged = (*dstp ^ tmp) != 0;
+ if (wordchanged)
+ *popcountp = do_popcount (tmp);
+ popcountp++;
+ }
+ *dstp++ = tmp;
+ }
+#ifdef BITMAP_DEBUGGING
+ if (has_popcount)
+ sbitmap_verify_popcount (dst);
+#endif
}
/* Set DST to be (A xor B)).
@@ -379,6 +498,8 @@ sbitmap_a_xor_b_cg (sbitmap dst, sbitmap
sbitmap_ptr ap = a->elms;
sbitmap_ptr bp = b->elms;
SBITMAP_ELT_TYPE changed = 0;
+
+ gcc_assert (!dst->popcount);
for (i = 0; i < n; i++)
{
@@ -397,9 +518,25 @@ sbitmap_a_xor_b (sbitmap dst, sbitmap a,
sbitmap_ptr dstp = dst->elms;
sbitmap_ptr ap = a->elms;
sbitmap_ptr bp = b->elms;
+ bool has_popcount = dst->popcount != NULL;
+ unsigned char *popcountp = dst->popcount;
for (i = 0; i < n; i++)
- *dstp++ = *ap++ ^ *bp++;
+ {
+ SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
+ if (has_popcount)
+ {
+ bool wordchanged = (*dstp ^ tmp) != 0;
+ if (wordchanged)
+ *popcountp = do_popcount (tmp);
+ popcountp++;
+ }
+ *dstp++ = tmp;
+ }
+#ifdef BITMAP_DEBUGGING
+ if (has_popcount)
+ sbitmap_verify_popcount (dst);
+#endif
}
/* Set DST to be (A or B)).
@@ -414,6 +551,8 @@ sbitmap_a_or_b_cg (sbitmap dst, sbitmap
sbitmap_ptr bp = b->elms;
SBITMAP_ELT_TYPE changed = 0;
+ gcc_assert (!dst->popcount);
+
for (i = 0; i < n; i++)
{
SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
@@ -431,9 +570,25 @@ sbitmap_a_or_b (sbitmap dst, sbitmap a,
sbitmap_ptr dstp = dst->elms;
sbitmap_ptr ap = a->elms;
sbitmap_ptr bp = b->elms;
+ bool has_popcount = dst->popcount != NULL;
+ unsigned char *popcountp = dst->popcount;
for (i = 0; i < n; i++)
- *dstp++ = *ap++ | *bp++;
+ {
+ SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
+ if (has_popcount)
+ {
+ bool wordchanged = (*dstp ^ tmp) != 0;
+ if (wordchanged)
+ *popcountp = do_popcount (tmp);
+ popcountp++;
+ }
+ *dstp++ = tmp;
+ }
+#ifdef BITMAP_DEBUGGING
+ if (has_popcount)
+ sbitmap_verify_popcount (dst);
+#endif
}
/* Return nonzero if A is a subset of B. */
@@ -464,6 +619,8 @@ sbitmap_a_or_b_and_c_cg (sbitmap dst, sb
sbitmap_ptr cp = c->elms;
SBITMAP_ELT_TYPE changed = 0;
+ gcc_assert (!dst->popcount);
+
for (i = 0; i < n; i++)
{
SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
@@ -483,6 +640,8 @@ sbitmap_a_or_b_and_c (sbitmap dst, sbitm
sbitmap_ptr bp = b->elms;
sbitmap_ptr cp = c->elms;
+ gcc_assert (!dst->popcount);
+
for (i = 0; i < n; i++)
*dstp++ = *ap++ | (*bp++ & *cp++);
}
@@ -500,6 +659,8 @@ sbitmap_a_and_b_or_c_cg (sbitmap dst, sb
sbitmap_ptr cp = c->elms;
SBITMAP_ELT_TYPE changed = 0;
+ gcc_assert (!dst->popcount);
+
for (i = 0; i < n; i++)
{
SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
@@ -535,6 +696,8 @@ sbitmap_intersection_of_succs (sbitmap d
edge e;
unsigned ix;
+ gcc_assert (!dst->popcount);
+
for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
{
e = EDGE_SUCC (b, ix);
@@ -575,6 +738,8 @@ sbitmap_intersection_of_preds (sbitmap d
edge e;
unsigned ix;
+ gcc_assert (!dst->popcount);
+
for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
{
e = EDGE_PRED (b, ix);
@@ -615,6 +780,8 @@ sbitmap_union_of_succs (sbitmap dst, sbi
edge e;
unsigned ix;
+ gcc_assert (!dst->popcount);
+
for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
{
e = EDGE_SUCC (b, ix);
@@ -655,6 +822,8 @@ sbitmap_union_of_preds (sbitmap dst, sbi
edge e;
unsigned ix;
+ gcc_assert (!dst->popcount);
+
for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
{
e = EDGE_PRED (b, ix);
@@ -795,3 +964,82 @@ dump_sbitmap_vector (FILE *file, const c
fprintf (file, "\n");
}
+
+#if GCC_VERSION < 3400
+/* Table of number of set bits in a character, indexed by value of char. */
+static unsigned char popcount_table[] =
+{
+ 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
+};
+
+/* Count the bits in an SBITMAP element A. */
+
+static unsigned long
+sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
+{
+ unsigned long ret = 0;
+ unsigned i;
+
+ if (a == 0)
+ return 0;
+
+ /* Just do this the table way for now */
+ for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
+ ret += popcount_table[(a >> i) & 0xff];
+ return ret;
+}
+#endif
+
+/* 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);
+ for (ix = 0; ix < lastword; ix++)
+ {
+ if (a->popcount)
+ {
+ count += a->popcount[ix];
+#ifdef BITMAP_DEBUGGING
+ gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
+#endif
+ }
+ else
+ count += do_popcount (a->elms[ix]);
+ }
+
+ /* Count the remaining bits. */
+ if (lastword < a->size)
+ {
+ unsigned int bitindex;
+ SBITMAP_ELT_TYPE theword = a->elms[lastword];
+
+ bitindex = maxbit % SBITMAP_ELT_BITS;
+ if (bitindex != 0)
+ {
+ theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
+ count += do_popcount (theword);
+ }
+ }
+ return count;
+}
+
Index: sbitmap.h
===================================================================
--- sbitmap.h (revision 120211)
+++ sbitmap.h (working copy)
@@ -28,11 +28,19 @@ Software Foundation, 51 Franklin Street,
#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
+/* Can't use SBITMAP_ELT_BITS in this macro because it contains a
+ cast. There is no perfect macro in GCC to test against. This
+ suffices for roughly 99% of the hosts we run on, and the rest
+ don't have 256 bit integers. */
+#if HOST_BITS_PER_WIDEST_FAST_INT > 255
+#error Need to increase size of datatype used for popcount
+#endif
+
typedef struct simple_bitmap_def
{
+ unsigned char *popcount; /* Population count. */
unsigned int n_bits; /* Number of bits. */
unsigned int size; /* Size in elements. */
- unsigned int bytes; /* Size in bytes. */
SBITMAP_ELT_TYPE elms[1]; /* The elements. */
} *sbitmap;
@@ -40,20 +48,47 @@ typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
/* Return the set size needed for N elements. */
#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
-
-/* Set bit number bitno in the bitmap. */
-#define SET_BIT(BITMAP, BITNO) \
- ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \
- |= (SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS)
+#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
/* Test if bit number bitno in the bitmap is set. */
#define TEST_BIT(BITMAP, BITNO) \
((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1)
-/* Reset bit number bitno in the bitmap. */
-#define RESET_BIT(BITMAP, BITNO) \
- ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \
- &= ~((SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS))
+/* Set bit number BITNO in the sbitmap MAP. Updates population count
+ if this bitmap has one. */
+
+static inline void
+SET_BIT (sbitmap map, unsigned int bitno)
+{
+ if (map->popcount)
+ {
+ bool oldbit;
+ oldbit = TEST_BIT (map, bitno);
+ if (!oldbit)
+ map->popcount[bitno / SBITMAP_ELT_BITS]++;
+ }
+ map->elms[bitno / SBITMAP_ELT_BITS]
+ |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
+}
+
+
+
+/* Reset bit number BITNO in the sbitmap MAP. Updates population
+ count if this bitmap has one. */
+
+static inline void
+RESET_BIT (sbitmap map, unsigned int bitno)
+{
+ if (map->popcount)
+ {
+ bool oldbit;
+ oldbit = TEST_BIT (map, bitno);
+ if (oldbit)
+ map->popcount[bitno / SBITMAP_ELT_BITS]--;
+ }
+ map->elms[bitno / SBITMAP_ELT_BITS]
+ &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
+}
/* The iterator for sbitmap. */
typedef struct {
@@ -165,7 +200,7 @@ do { \
} \
} while (0)
-#define sbitmap_free(MAP) free(MAP)
+#define sbitmap_free(MAP) (free((MAP)->popcount), free((MAP)))
#define sbitmap_vector_free(VEC) free(VEC)
struct int_list;
@@ -175,9 +210,11 @@ extern void dump_sbitmap_file (FILE *, s
extern void dump_sbitmap_vector (FILE *, const char *, const char *, sbitmap *,
int);
extern sbitmap sbitmap_alloc (unsigned int);
+extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
extern void sbitmap_copy (sbitmap, sbitmap);
+extern void sbitmap_copy_n (sbitmap, sbitmap, unsigned int);
extern int sbitmap_equal (sbitmap, sbitmap);
extern void sbitmap_zero (sbitmap);
extern void sbitmap_ones (sbitmap);
@@ -224,4 +261,6 @@ extern void sbitmap_union_of_preds (sbit
extern void debug_sbitmap (sbitmap);
extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
+extern unsigned long sbitmap_popcount(sbitmap, unsigned long);
+extern void sbitmap_verify_popcount (sbitmap);
#endif /* ! GCC_SBITMAP_H */