diff options
author | dberlin <dberlin@138bc75d-0d04-0410-961f-82ee72b054a4> | 2007-06-11 18:02:15 +0000 |
---|---|---|
committer | dberlin <dberlin@138bc75d-0d04-0410-961f-82ee72b054a4> | 2007-06-11 18:02:15 +0000 |
commit | 3072d30e7983a3ca5ad030f1f98a5c39bcc2c07b (patch) | |
tree | fdb9e9f8a0700a2713dc690fed1a2cf20dae8392 /gcc/bitmap.c | |
parent | 8ceb1bfd33bc40bf0cbe1fab8903c2c31efd10ee (diff) | |
download | ppe42-gcc-3072d30e7983a3ca5ad030f1f98a5c39bcc2c07b.tar.gz ppe42-gcc-3072d30e7983a3ca5ad030f1f98a5c39bcc2c07b.zip |
Merge dataflow branch into mainline
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@125624 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'gcc/bitmap.c')
-rw-r--r-- | gcc/bitmap.c | 538 |
1 files changed, 395 insertions, 143 deletions
diff --git a/gcc/bitmap.c b/gcc/bitmap.c index 96889e0c7a4..740a883b203 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -1,6 +1,6 @@ /* Functions to support general ended bitmaps. - Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005 - Free Software Foundation, Inc. + Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005, + 2006, 2007 Free Software Foundation, Inc. This file is part of GCC. @@ -852,72 +852,151 @@ bitmap_and_into (bitmap a, bitmap b) gcc_assert (!a->current || a->indx == a->current->indx); } + +/* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT + if non-NULL. CHANGED is true if the destination bitmap had already been + changed; the new value of CHANGED is returned. */ + +static inline bool +bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, + bitmap_element *src_elt, bool changed) +{ + if (!changed && dst_elt && dst_elt->indx == src_elt->indx) + { + unsigned ix; + + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + if (src_elt->bits[ix] != dst_elt->bits[ix]) + { + dst_elt->bits[ix] = src_elt->bits[ix]; + changed = true; + } + } + else + { + changed = true; + if (!dst_elt) + dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx); + else + dst_elt->indx = src_elt->indx; + memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); + } + return changed; +} + + + /* DST = A & ~B */ -void +bool bitmap_and_compl (bitmap dst, bitmap a, bitmap b) { bitmap_element *dst_elt = dst->first; bitmap_element *a_elt = a->first; bitmap_element *b_elt = b->first; bitmap_element *dst_prev = NULL; + bitmap_element **dst_prev_pnext = &dst->first; + bool changed = false; gcc_assert (dst != a && dst != b); if (a == b) { + changed = !bitmap_empty_p (dst); bitmap_clear (dst); - return; + return changed; } while (a_elt) { - if (!b_elt || a_elt->indx < b_elt->indx) + while (b_elt && b_elt->indx < a_elt->indx) + b_elt = b_elt->next; + + if (!b_elt || b_elt->indx > a_elt->indx) { - /* Copy a_elt. */ - if (!dst_elt) - 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; + changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed); + dst_prev = *dst_prev_pnext; + dst_prev_pnext = &dst_prev->next; + dst_elt = *dst_prev_pnext; a_elt = a_elt->next; } - else if (b_elt->indx < a_elt->indx) - b_elt = b_elt->next; + else { /* Matching elts, generate A & ~B. */ unsigned ix; BITMAP_WORD ior = 0; - if (!dst_elt) - dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); + if (!changed && dst_elt && dst_elt->indx == a_elt->indx) + { + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + { + BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; + + if (dst_elt->bits[ix] != r) + { + changed = true; + dst_elt->bits[ix] = r; + } + ior |= r; + } + } else - dst_elt->indx = a_elt->indx; - for (ix = BITMAP_ELEMENT_WORDS; ix--;) { - BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; + bool new_element; + if (!dst_elt || dst_elt->indx > a_elt->indx) + { + dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); + new_element = true; + } + else + { + dst_elt->indx = a_elt->indx; + new_element = false; + } - dst_elt->bits[ix] = r; - ior |= r; + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + { + BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; + + dst_elt->bits[ix] = r; + ior |= r; + } + + if (ior) + changed = true; + else + { + changed |= !new_element; + bitmap_element_free (dst, dst_elt); + dst_elt = *dst_prev_pnext; + } } + if (ior) { - dst_prev = dst_elt; - dst_elt = dst_elt->next; + dst_prev = *dst_prev_pnext; + dst_prev_pnext = &dst_prev->next; + dst_elt = *dst_prev_pnext; } a_elt = a_elt->next; b_elt = b_elt->next; } } + /* Ensure that dst->current is valid. */ dst->current = dst->first; - bitmap_elt_clear_from (dst, dst_elt); + + if (dst_elt) + { + changed = true; + bitmap_elt_clear_from (dst, dst_elt); + } gcc_assert (!dst->current == !dst->first); if (dst->current) dst->indx = dst->current->indx; + + return changed; } /* A &= ~B. Returns true if A changes */ @@ -974,15 +1053,120 @@ bitmap_and_compl_into (bitmap a, bitmap b) return changed != 0; } +/* Set COUNT bits from START in HEAD. */ +void +bitmap_set_range (bitmap head, unsigned int start, unsigned int count) +{ + unsigned int first_index, end_bit_plus1, last_index; + bitmap_element *elt, *elt_prev; + unsigned int i; + + if (!count) + return; + + first_index = start / BITMAP_ELEMENT_ALL_BITS; + end_bit_plus1 = start + count; + last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; + elt = bitmap_find_bit (head, start); + + /* If bitmap_find_bit returns zero, the current is the closest block + to the result. Otherwise, just use bitmap_element_allocate to + ensure ELT is set; in the loop below, ELT == NULL means "insert + at the end of the bitmap". */ + if (!elt) + { + elt = bitmap_element_allocate (head); + elt->indx = first_index; + bitmap_element_link (head, elt); + } + + gcc_assert (elt->indx == first_index); + elt_prev = elt->prev; + for (i = first_index; i <= last_index; i++) + { + unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS; + unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; + + unsigned int first_word_to_mod; + BITMAP_WORD first_mask; + unsigned int last_word_to_mod; + BITMAP_WORD last_mask; + unsigned int ix; + + if (!elt || elt->indx != i) + elt = bitmap_elt_insert_after (head, elt_prev, i); + + if (elt_start_bit <= start) + { + /* The first bit to turn on 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 on is below this start of this elt. */ + first_word_to_mod = 0; + first_mask = ~(BITMAP_WORD) 0; + } + + if (elt_end_bit_plus1 <= end_bit_plus1) + { + /* The last bit to turn on is beyond this elt. */ + last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; + last_mask = ~(BITMAP_WORD) 0; + } + else + { + /* The last bit to turn on 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; + if (BITMAP_ELEMENT_WORDS > 2) + for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++) + elt->bits[ix] = ~(BITMAP_WORD) 0; + elt->bits[last_word_to_mod] |= last_mask; + } + + elt_prev = elt; + elt = elt->next; + } + + head->current = elt ? elt : elt_prev; + head->indx = head->current->indx; +} + /* 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); + unsigned int first_index, end_bit_plus1, last_index; + bitmap_element *elt; + + if (!count) + return; + + first_index = start / BITMAP_ELEMENT_ALL_BITS; + end_bit_plus1 = start + count; + last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; + 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 @@ -1070,8 +1254,9 @@ bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) 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; + if (BITMAP_ELEMENT_WORDS > 2) + 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++) @@ -1163,6 +1348,66 @@ bitmap_compl_and_into (bitmap a, bitmap b) return; } + +/* Insert an element corresponding to A_ELT | B_ELT after DST_PREV, + overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap + had already been changed; the new value of CHANGED is returned. */ + +static inline bool +bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, + bitmap_element *a_elt, bitmap_element *b_elt, + bool changed) +{ + gcc_assert (a_elt || b_elt); + + if (a_elt && b_elt && a_elt->indx == b_elt->indx) + { + /* Matching elts, generate A | B. */ + unsigned ix; + + if (!changed && dst_elt && dst_elt->indx == a_elt->indx) + { + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + { + BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; + if (r != dst_elt->bits[ix]) + { + dst_elt->bits[ix] = r; + changed = true; + } + } + } + else + { + changed = true; + if (!dst_elt) + 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]; + dst_elt->bits[ix] = r; + } + } + } + else + { + /* Copy a single element. */ + bitmap_element *src; + + if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) + src = a_elt; + else + src = b_elt; + + gcc_assert (src); + changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed); + } + return changed; +} + + /* DST = A | B. Return true if DST changes. */ bool @@ -1172,89 +1417,31 @@ bitmap_ior (bitmap dst, bitmap a, bitmap b) bitmap_element *a_elt = a->first; bitmap_element *b_elt = b->first; bitmap_element *dst_prev = NULL; + bitmap_element **dst_prev_pnext = &dst->first; bool changed = false; gcc_assert (dst != a && dst != b); while (a_elt || b_elt) { + changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); + if (a_elt && b_elt && a_elt->indx == b_elt->indx) { - /* Matching elts, generate A | B. */ - unsigned ix; - - if (!changed && dst_elt && dst_elt->indx == a_elt->indx) - { - for (ix = BITMAP_ELEMENT_WORDS; ix--;) - { - BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; - - if (r != dst_elt->bits[ix]) - { - dst_elt->bits[ix] = r; - changed = true; - } - } - } - else - { - changed = true; - if (!dst_elt) - 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]; - - dst_elt->bits[ix] = r; - } - } a_elt = a_elt->next; b_elt = b_elt->next; - dst_prev = dst_elt; - dst_elt = dst_elt->next; } else { - /* Copy a single element. */ - bitmap_element *src; - - if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) - { - src = a_elt; - a_elt = a_elt->next; - } - else - { - src = b_elt; - b_elt = b_elt->next; - } - - if (!changed && dst_elt && dst_elt->indx == src->indx) - { - unsigned ix; - - for (ix = BITMAP_ELEMENT_WORDS; ix--;) - if (src->bits[ix] != dst_elt->bits[ix]) - { - dst_elt->bits[ix] = src->bits[ix]; - changed = true; - } - } - else - { - changed = true; - if (!dst_elt) - 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; + if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) + a_elt = a_elt->next; + else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) + b_elt = b_elt->next; } + + dst_prev = *dst_prev_pnext; + dst_prev_pnext = &dst_prev->next; + dst_elt = *dst_prev_pnext; } if (dst_elt) @@ -1276,6 +1463,7 @@ bitmap_ior_into (bitmap a, bitmap b) bitmap_element *a_elt = a->first; bitmap_element *b_elt = b->first; bitmap_element *a_prev = NULL; + bitmap_element **a_prev_pnext = &a->first; bool changed = false; if (a == b) @@ -1283,48 +1471,23 @@ bitmap_ior_into (bitmap a, bitmap b) while (b_elt) { - if (!a_elt || b_elt->indx < a_elt->indx) + /* If A lags behind B, just advance it. */ + if (!a_elt || a_elt->indx == b_elt->indx) { - /* Copy b_elt. */ - 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; + changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); b_elt = b_elt->next; - changed = true; - } - else if (a_elt->indx < b_elt->indx) - { - a_prev = a_elt; - a_elt = a_elt->next; } - else + else if (a_elt->indx > b_elt->indx) { - /* Matching elts, generate A |= B. */ - unsigned ix; - - if (changed) - for (ix = BITMAP_ELEMENT_WORDS; ix--;) - { - BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; - - a_elt->bits[ix] = r; - } - else - for (ix = BITMAP_ELEMENT_WORDS; ix--;) - { - BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; - - if (a_elt->bits[ix] != r) - { - changed = true; - a_elt->bits[ix] = r; - } - } + changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed); b_elt = b_elt->next; - a_prev = a_elt; - a_elt = a_elt->next; } + + a_prev = *a_prev_pnext; + a_prev_pnext = &a_prev->next; + a_elt = *a_prev_pnext; } + gcc_assert (!a->current == !a->first); if (a->current) a->indx = a->current->indx; @@ -1548,15 +1711,103 @@ bitmap_intersect_compl_p (bitmap a, bitmap b) /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ bool -bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2) +bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap b, bitmap kill) { - bitmap_head tmp; - bool changed; + bool changed = false; - bitmap_initialize (&tmp, &bitmap_default_obstack); - bitmap_and_compl (&tmp, from1, from2); - changed = bitmap_ior (dst, a, &tmp); - bitmap_clear (&tmp); + bitmap_element *dst_elt = dst->first; + bitmap_element *a_elt = a->first; + bitmap_element *b_elt = b->first; + bitmap_element *kill_elt = kill->first; + bitmap_element *dst_prev = NULL; + bitmap_element **dst_prev_pnext = &dst->first; + + gcc_assert (dst != a && dst != b && dst != kill); + + /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ + if (b == kill || bitmap_empty_p (b)) + { + changed = !bitmap_equal_p (dst, a); + if (changed) + bitmap_copy (dst, a); + return changed; + } + if (bitmap_empty_p (kill)) + return bitmap_ior (dst, a, b); + if (bitmap_empty_p (a)) + return bitmap_and_compl (dst, b, kill); + + while (a_elt || b_elt) + { + bool new_element = false; + + if (b_elt) + while (kill_elt && kill_elt->indx < b_elt->indx) + kill_elt = kill_elt->next; + + if (b_elt && kill_elt && kill_elt->indx == b_elt->indx + && (!a_elt || a_elt->indx >= b_elt->indx)) + { + bitmap_element tmp_elt; + unsigned ix; + + BITMAP_WORD ior = 0; + tmp_elt.indx = b_elt->indx; + for (ix = BITMAP_ELEMENT_WORDS; ix--;) + { + BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix]; + ior |= r; + tmp_elt.bits[ix] = r; + } + + if (ior) + { + changed = bitmap_elt_ior (dst, dst_elt, dst_prev, + a_elt, &tmp_elt, changed); + new_element = true; + if (a_elt && a_elt->indx == b_elt->indx) + a_elt = a_elt->next; + } + + b_elt = b_elt->next; + kill_elt = kill_elt->next; + } + else + { + changed = bitmap_elt_ior (dst, dst_elt, dst_prev, + a_elt, b_elt, changed); + new_element = true; + + if (a_elt && b_elt && a_elt->indx == b_elt->indx) + { + a_elt = a_elt->next; + b_elt = b_elt->next; + } + else + { + if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) + a_elt = a_elt->next; + else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) + b_elt = b_elt->next; + } + } + + if (new_element) + { + dst_prev = *dst_prev_pnext; + dst_prev_pnext = &dst_prev->next; + dst_elt = *dst_prev_pnext; + } + } + + if (dst_elt) + { + changed = true; + bitmap_elt_clear_from (dst, dst_elt); + } + gcc_assert (!dst->current == !dst->first); + if (dst->current) + dst->indx = dst->current->indx; return changed; } @@ -1576,6 +1827,7 @@ bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2) return changed; } + /* Debugging function to print out the contents of a bitmap. */ |