diff options
author | Kenneth Zadeck <zadeck@gcc.gnu.org> | 2005-12-29 19:41:21 +0000 |
---|---|---|
committer | Kenneth Zadeck <zadeck@gcc.gnu.org> | 2005-12-29 19:41:21 +0000 |
commit | 1bc40c7e8ac62eafdef41e04276e9cab85488af7 (patch) | |
tree | 9e78cf08041b019d6700dc377e3c95a96775f9a7 | |
parent | 3dd9b65f61603ae3504abe0a0e95725c511f46be (diff) | |
download | gcc-1bc40c7e8ac62eafdef41e04276e9cab85488af7.zip gcc-1bc40c7e8ac62eafdef41e04276e9cab85488af7.tar.gz gcc-1bc40c7e8ac62eafdef41e04276e9cab85488af7.tar.bz2 |
bitmap.c (bitmap_element_free, [...]): Added code to properly maintain the variants associated with the CURRENT and...
2005-12-29 Kenneth Zadeck <zadeck@naturalbridge.com>
* bitmap.c (bitmap_element_free, bitmap_element_link,
bitmap_elt_insert_after, bitmap_and, bitmap_and_compl,
bitmap_and_compl, bitmap_ior, bitmap_ior_into, bitmap_xor,
bitmap_xor_into): Added code to properly maintain the variants
associated with the CURRENT and HEAD fields.
(bitmap_popcount, bitmap_clear_range, bitmap_compl_and_into): New
functions. * bitmap.h: Added defs for bitmap_popcount,
bitmap_clear_range, and bitmap_compl_and_into.
From-SVN: r109153
-rw-r--r-- | gcc/bitmap.c | 302 | ||||
-rw-r--r-- | gcc/bitmap.h | 6 |
2 files changed, 280 insertions, 28 deletions
diff --git a/gcc/bitmap.c b/gcc/bitmap.c index 3ee8bbd..f69fd27 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -40,7 +40,7 @@ static void bitmap_element_free (bitmap, bitmap_element *); static bitmap_element *bitmap_element_allocate (bitmap); static int bitmap_element_zerop (bitmap_element *); static void bitmap_element_link (bitmap, bitmap_element *); -static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *); +static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); static void bitmap_elt_clear_from (bitmap, bitmap_element *); static bitmap_element *bitmap_find_bit (bitmap, unsigned int); @@ -89,6 +89,8 @@ bitmap_element_free (bitmap head, bitmap_element *elt) head->current = next != 0 ? next : prev; if (head->current) head->indx = head->current->indx; + else + head->indx = 0; } bitmap_elem_to_freelist (head, elt); } @@ -351,14 +353,18 @@ bitmap_element_link (bitmap head, bitmap_element *element) new element. */ static bitmap_element * -bitmap_elt_insert_after (bitmap head, bitmap_element *elt) +bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) { bitmap_element *node = bitmap_element_allocate (head); + node->indx = indx; if (!elt) { if (!head->current) - head->current = node; + { + head->current = node; + head->indx = indx; + } node->next = head->first; if (node->next) node->next->prev = node; @@ -521,6 +527,59 @@ bitmap_bit_p (bitmap head, int bit) return (ptr->bits[word_num] >> bit_num) & 1; } +#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, +}; + +static unsigned long +bitmap_popcount (BITMAP_WORD a) +{ + unsigned long ret = 0; + unsigned i; + + /* Just do this the table way for now */ + for (i = 0; i < BITMAP_WORD_BITS; i+= 8) + ret += popcount_table[(a >> i) & 0xff]; + return ret; +} +#endif +/* Count the number of bits set in the bitmap, and return it. */ + +unsigned long +bitmap_count_bits (bitmap a) +{ + unsigned long count = 0; + bitmap_element *elt; + unsigned ix; + + for (elt = a->first; elt; elt = elt->next) + { + for (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 (elt->bits[ix]); +#else + count += bitmap_popcount (elt->bits[ix]); +#endif + } + } + return count; +} + + + /* Return the bit number of the first set bit in the bitmap. The bitmap must be non-empty. */ @@ -604,9 +663,9 @@ bitmap_and (bitmap dst, bitmap a, bitmap b) BITMAP_WORD ior = 0; if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev); - - dst_elt->indx = a_elt->indx; + dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); + else + dst_elt->indx = a_elt->indx; for (ix = BITMAP_ELEMENT_WORDS; ix--;) { BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; @@ -700,9 +759,9 @@ bitmap_and_compl (bitmap dst, bitmap a, bitmap b) { /* Copy a_elt. */ if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev); - - dst_elt->indx = a_elt->indx; + dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); + else + dst_elt->indx = a_elt->indx; memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits)); dst_prev = dst_elt; dst_elt = dst_elt->next; @@ -717,9 +776,9 @@ bitmap_and_compl (bitmap dst, bitmap a, bitmap b) BITMAP_WORD ior = 0; if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev); - - dst_elt->indx = a_elt->indx; + dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); + else + dst_elt->indx = a_elt->indx; for (ix = BITMAP_ELEMENT_WORDS; ix--;) { BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; @@ -796,6 +855,195 @@ bitmap_and_compl_into (bitmap a, bitmap b) return changed != 0; } +/* Clear COUNT bits from START in HEAD. */ +void +bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) +{ + unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS; + unsigned int end_bit_plus1 = start + count; + unsigned int end_bit = end_bit_plus1 - 1; + unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS; + bitmap_element *elt = bitmap_find_bit (head, start); + + /* If bitmap_find_bit returns zero, the current is the closest block + to the result. If the current is less than first index, find the + next one. Otherwise, just set elt to be current. */ + if (!elt) + { + if (head->current) + { + if (head->indx < first_index) + { + elt = head->current->next; + if (!elt) + return; + } + else + elt = head->current; + } + else + return; + } + + while (elt && (elt->indx <= last_index)) + { + bitmap_element * next_elt = elt->next; + unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; + unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; + + + if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) + /* Get rid of the entire elt and go to the next one. */ + bitmap_element_free (head, elt); + else + { + /* Going to have to knock out some bits in this elt. */ + unsigned int first_word_to_mod; + BITMAP_WORD first_mask; + unsigned int last_word_to_mod; + BITMAP_WORD last_mask; + unsigned int i; + bool clear = true; + + if (elt_start_bit <= start) + { + /* The first bit to turn off is somewhere inside this + elt. */ + first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; + + /* This mask should have 1s in all bits >= start position. */ + first_mask = + (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; + first_mask = ~first_mask; + } + else + { + /* The first bit to turn off is below this start of this elt. */ + first_word_to_mod = 0; + first_mask = 0; + first_mask = ~first_mask; + } + + if (elt_end_bit_plus1 <= end_bit_plus1) + { + /* The last bit to turn off is beyond this elt. */ + last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; + last_mask = 0; + last_mask = ~last_mask; + } + else + { + /* The last bit to turn off is inside to this elt. */ + last_word_to_mod = + (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; + + /* The last mask should have 1s below the end bit. */ + last_mask = + (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; + } + + + if (first_word_to_mod == last_word_to_mod) + { + BITMAP_WORD mask = first_mask & last_mask; + elt->bits[first_word_to_mod] &= ~mask; + } + else + { + elt->bits[first_word_to_mod] &= ~first_mask; + for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) + elt->bits[i] = 0; + elt->bits[last_word_to_mod] &= ~last_mask; + } + for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) + if (elt->bits[i]) + { + clear = false; + break; + } + /* Check to see if there are any bits left. */ + if (clear) + bitmap_element_free (head, elt); + } + elt = next_elt; + } + + if (elt) + { + head->current = elt; + head->indx = head->current->indx; + } +} + +/* A = ~A & B. */ + +void +bitmap_compl_and_into (bitmap a, bitmap b) +{ + bitmap_element *a_elt = a->first; + bitmap_element *b_elt = b->first; + bitmap_element *a_prev = NULL; + bitmap_element *next; + + gcc_assert (a != b); + + if (bitmap_empty_p (a)) + { + bitmap_copy (a, b); + return; + } + if (bitmap_empty_p (b)) + { + bitmap_clear (a); + return; + } + + while (a_elt || b_elt) + { + if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) + { + /* A is before B. Remove A */ + next = a_elt->next; + a_prev = a_elt->prev; + bitmap_element_free (a, a_elt); + a_elt = next; + } + else if (!a_elt || b_elt->indx < a_elt->indx) + { + /* B is before A. Copy B. */ + next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); + memcpy (next->bits, b_elt->bits, sizeof (next->bits)); + a_prev = next; + b_elt = b_elt->next; + } + else + { + /* Matching elts, generate A = ~A & B. */ + unsigned ix; + BITMAP_WORD ior = 0; + + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + { + BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; + BITMAP_WORD r = b_elt->bits[ix] ^ cleared; + + a_elt->bits[ix] = r; + ior |= r; + } + next = a_elt->next; + if (!ior) + bitmap_element_free (a, a_elt); + else + a_prev = a_elt; + a_elt = next; + b_elt = b_elt->next; + } + } + gcc_assert (!a->current == !a->first); + gcc_assert (!a->current || a->indx == a->current->indx); + return; +} + /* DST = A | B. Return true if DST changes. */ bool @@ -833,8 +1081,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap b) { changed = true; if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev); - dst_elt->indx = a_elt->indx; + dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); + else + dst_elt->indx = a_elt->indx; for (ix = BITMAP_ELEMENT_WORDS; ix--;) { BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; @@ -878,8 +1127,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap b) { changed = true; if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev); - dst_elt->indx = src->indx; + dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); + else + dst_elt->indx = src->indx; memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); } @@ -917,9 +1167,7 @@ bitmap_ior_into (bitmap a, bitmap b) if (!a_elt || b_elt->indx < a_elt->indx) { /* Copy b_elt. */ - bitmap_element *dst = bitmap_elt_insert_after (a, a_prev); - - dst->indx = b_elt->indx; + bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); a_prev = dst; b_elt = b_elt->next; @@ -990,9 +1238,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b) BITMAP_WORD ior = 0; if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev); - - dst_elt->indx = a_elt->indx; + dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); + else + dst_elt->indx = a_elt->indx; for (ix = BITMAP_ELEMENT_WORDS; ix--;) { BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; @@ -1025,9 +1273,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b) } if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev); - - dst_elt->indx = src->indx; + dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); + else + dst_elt->indx = src->indx; memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); dst_prev = dst_elt; dst_elt = dst_elt->next; @@ -1059,9 +1307,7 @@ bitmap_xor_into (bitmap a, bitmap b) if (!a_elt || b_elt->indx < a_elt->indx) { /* Copy b_elt. */ - bitmap_element *dst = bitmap_elt_insert_after (a, a_prev); - - dst->indx = b_elt->indx; + bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); a_prev = dst; b_elt = b_elt->next; diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 3400c05..fb56e4e 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -102,6 +102,9 @@ extern bool bitmap_intersect_compl_p (bitmap, bitmap); /* True if MAP is an empty bitmap. */ #define bitmap_empty_p(MAP) (!(MAP)->first) +/* Count the number of bits set in the bitmap. */ +extern unsigned long bitmap_count_bits (bitmap); + /* Boolean operations on bitmaps. The _into variants are two operand versions that modify the first source operand. The other variants are three operand versions that to not destroy the source bitmaps. @@ -110,6 +113,9 @@ extern void bitmap_and (bitmap, bitmap, bitmap); extern void bitmap_and_into (bitmap, bitmap); extern void bitmap_and_compl (bitmap, bitmap, bitmap); extern bool bitmap_and_compl_into (bitmap, bitmap); +#define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A) +extern void bitmap_compl_and_into (bitmap, bitmap); +extern void bitmap_clear_range (bitmap, unsigned int, unsigned int); extern bool bitmap_ior (bitmap, bitmap, bitmap); extern bool bitmap_ior_into (bitmap, bitmap); extern void bitmap_xor (bitmap, bitmap, bitmap); |