diff options
Diffstat (limited to 'gcc/bitmap.c')
-rw-r--r-- | gcc/bitmap.c | 63 |
1 files changed, 54 insertions, 9 deletions
diff --git a/gcc/bitmap.c b/gcc/bitmap.c index ac20ae5..0c05512 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -662,6 +662,26 @@ bitmap_popcount (BITMAP_WORD a) return ret; } #endif + +/* Count and return the number of bits set in the bitmap word BITS. */ +static unsigned long +bitmap_count_bits_in_word (const BITMAP_WORD *bits) +{ + unsigned long count = 0; + + for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) + { +#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]); +#else + count += bitmap_popcount (bits[ix]); +#endif + } + return count; +} + /* Count the number of bits set in the bitmap, and return it. */ unsigned long @@ -669,19 +689,44 @@ bitmap_count_bits (const_bitmap a) { unsigned long count = 0; const bitmap_element *elt; - unsigned ix; for (elt = a->first; elt; elt = elt->next) + count += bitmap_count_bits_in_word (elt->bits); + + return count; +} + +/* Count the number of unique bits set in A and B and return it. */ + +unsigned long +bitmap_count_unique_bits (const_bitmap a, const_bitmap b) +{ + unsigned long count = 0; + const bitmap_element *elt_a, *elt_b; + + for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; ) { - for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) + /* If we're at different indices, then count all the bits + in the lower element. If we're at the same index, then + count the bits in the IOR of the two elements. */ + if (elt_a->indx < elt_b->indx) { -#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]); -#else - count += bitmap_popcount (elt->bits[ix]); -#endif + count += bitmap_count_bits_in_word (elt_a->bits); + elt_a = elt_a->next; + } + else if (elt_b->indx < elt_a->indx) + { + count += bitmap_count_bits_in_word (elt_b->bits); + elt_b = elt_b->next; + } + else + { + BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; + for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) + bits[ix] = elt_a->bits[ix] | elt_b->bits[ix]; + count += bitmap_count_bits_in_word (bits); + elt_a = elt_a->next; + elt_b = elt_b->next; } } return count; |