X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fsbitmap.c;h=5ef7f08d2c5398eaabfd184a0d956c0355f49418;hb=86b36930b73951cf9a87107b45c3fd53a79e8bc5;hp=8514a22122745b1305c91341ec02a0a7e8e3b17e;hpb=805e22b2051e9c6a75377ea6599654d7415da483;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index 8514a221227..5ef7f08d2c5 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -1,5 +1,5 @@ /* Simple bitmaps. - Copyright (C) 1999, 2000, 2002 Free Software Foundation, Inc. + Copyright (C) 1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc. This file is part of GCC. @@ -15,8 +15,8 @@ for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ #include "config.h" #include "system.h" @@ -25,6 +25,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "rtl.h" #include "flags.h" #include "hard-reg-set.h" +#include "obstack.h" #include "basic-block.h" /* Bitmap manipulation routines. */ @@ -32,8 +33,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA /* Allocate a simple bitmap of N_ELMS bits. */ sbitmap -sbitmap_alloc (n_elms) - unsigned int n_elms; +sbitmap_alloc (unsigned int n_elms) { unsigned int bytes, size, amt; sbitmap bmap; @@ -42,7 +42,88 @@ sbitmap_alloc (n_elms) bytes = size * sizeof (SBITMAP_ELT_TYPE); amt = (sizeof (struct simple_bitmap_def) + bytes - sizeof (SBITMAP_ELT_TYPE)); - bmap = (sbitmap) xmalloc (amt); + bmap = xmalloc (amt); + bmap->n_bits = n_elms; + bmap->size = size; + bmap->bytes = bytes; + return bmap; +} + +/* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the + size of BMAP, clear the new bits to zero if the DEF argument + is zero, and set them to one otherwise. */ + +sbitmap +sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) +{ + unsigned int bytes, size, amt; + unsigned int last_bit; + + size = SBITMAP_SET_SIZE (n_elms); + bytes = size * sizeof (SBITMAP_ELT_TYPE); + if (bytes > bmap->bytes) + { + amt = (sizeof (struct simple_bitmap_def) + + bytes - sizeof (SBITMAP_ELT_TYPE)); + bmap = xrealloc (bmap, amt); + } + + if (n_elms > bmap->n_bits) + { + if (def) + { + memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes); + + /* Set the new bits if the original last element. */ + 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)); + + /* Clear the unused bit in the new last element. */ + last_bit = n_elms % SBITMAP_ELT_BITS; + if (last_bit) + bmap->elms[size - 1] + &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); + } + else + memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes); + } + 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->n_bits = n_elms; + bmap->size = size; + bmap->bytes = bytes; + return bmap; +} + +/* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */ + +sbitmap +sbitmap_realloc (sbitmap src, 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)); + + if (src->bytes >= bytes) + { + src->n_bits = n_elms; + return src; + } + + bmap = (sbitmap) xrealloc (src, amt); bmap->n_bits = n_elms; bmap->size = size; bmap->bytes = bytes; @@ -52,8 +133,7 @@ sbitmap_alloc (n_elms) /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ sbitmap * -sbitmap_vector_alloc (n_vecs, n_elms) - unsigned int n_vecs, n_elms; +sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) { unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; sbitmap *bitmap_vector; @@ -77,7 +157,7 @@ sbitmap_vector_alloc (n_vecs, n_elms) } amt = vector_bytes + (n_vecs * elm_bytes); - bitmap_vector = (sbitmap *) xmalloc (amt); + bitmap_vector = xmalloc (amt); for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) { @@ -95,16 +175,14 @@ sbitmap_vector_alloc (n_vecs, n_elms) /* Copy sbitmap SRC to DST. */ void -sbitmap_copy (dst, src) - sbitmap dst, src; +sbitmap_copy (sbitmap dst, sbitmap src) { memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); } /* Determine if a == b. */ int -sbitmap_equal (a, b) - sbitmap a, b; +sbitmap_equal (sbitmap a, sbitmap b) { return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); } @@ -112,21 +190,19 @@ sbitmap_equal (a, b) /* Zero all elements in a bitmap. */ void -sbitmap_zero (bmap) - sbitmap bmap; +sbitmap_zero (sbitmap bmap) { - memset ((PTR) bmap->elms, 0, bmap->bytes); + memset (bmap->elms, 0, bmap->bytes); } /* Set all elements in a bitmap to ones. */ void -sbitmap_ones (bmap) - sbitmap bmap; +sbitmap_ones (sbitmap bmap) { unsigned int last_bit; - memset ((PTR) bmap->elms, -1, bmap->bytes); + memset (bmap->elms, -1, bmap->bytes); last_bit = bmap->n_bits % SBITMAP_ELT_BITS; if (last_bit) @@ -137,9 +213,7 @@ sbitmap_ones (bmap) /* Zero a vector of N_VECS bitmaps. */ void -sbitmap_vector_zero (bmap, n_vecs) - sbitmap *bmap; - unsigned int n_vecs; +sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs) { unsigned int i; @@ -150,9 +224,7 @@ sbitmap_vector_zero (bmap, n_vecs) /* Set a vector of N_VECS bitmaps to ones. */ void -sbitmap_vector_ones (bmap, n_vecs) - sbitmap *bmap; - unsigned int n_vecs; +sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs) { unsigned int i; @@ -165,8 +237,7 @@ sbitmap_vector_ones (bmap, n_vecs) Returns true if any change is made. */ bool -sbitmap_union_of_diff_cg (dst, a, b, c) - sbitmap dst, a, b, c; +sbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -186,8 +257,7 @@ sbitmap_union_of_diff_cg (dst, a, b, c) } void -sbitmap_union_of_diff (dst, a, b, c) - sbitmap dst, a, b, c; +sbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -202,33 +272,37 @@ sbitmap_union_of_diff (dst, a, b, c) /* Set bitmap DST to the bitwise negation of the bitmap SRC. */ void -sbitmap_not (dst, src) - sbitmap dst, src; +sbitmap_not (sbitmap dst, sbitmap src) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; sbitmap_ptr srcp = src->elms; + unsigned int last_bit; for (i = 0; i < n; i++) *dstp++ = ~*srcp++; + + /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */ + last_bit = src->n_bits % SBITMAP_ELT_BITS; + if (last_bit) + dst->elms[n-1] = dst->elms[n-1] + & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); } /* Set the bits in DST to be the difference between the bits in A and the bits in B. i.e. dst = a & (~b). */ void -sbitmap_difference (dst, a, b) - sbitmap dst, a, b; +sbitmap_difference (sbitmap dst, sbitmap a, sbitmap b) { unsigned int i, dst_size = dst->size; unsigned int min_size = dst->size; sbitmap_ptr dstp = dst->elms; sbitmap_ptr ap = a->elms; sbitmap_ptr bp = b->elms; - + /* A should be at least as large as DEST, to have a defined source. */ - if (a->size < dst_size) - abort (); + gcc_assert (a->size >= dst_size); /* If minuend is smaller, we simply pretend it to be zero bits, i.e. only copy the subtrahend into dest. */ if (b->size < min_size) @@ -242,12 +316,29 @@ sbitmap_difference (dst, a, b) *dstp++ = *ap++; } +/* Return true if there are any bits set in A are also set in B. + Return false otherwise. */ + +bool +sbitmap_any_common_bits (sbitmap a, sbitmap b) +{ + sbitmap_ptr ap = a->elms; + sbitmap_ptr bp = b->elms; + unsigned int i, n; + + n = MIN (a->size, b->size); + for (i = 0; i < n; i++) + if ((*ap++ & *bp++) != 0) + return true; + + return false; +} + /* Set DST to be (A and B). Return nonzero if any change is made. */ bool -sbitmap_a_and_b_cg (dst, a, b) - sbitmap dst, a, b; +sbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -258,7 +349,7 @@ sbitmap_a_and_b_cg (dst, a, b) for (i = 0; i < n; i++) { SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; - changed = *dstp ^ tmp; + changed |= *dstp ^ tmp; *dstp++ = tmp; } @@ -266,8 +357,7 @@ sbitmap_a_and_b_cg (dst, a, b) } void -sbitmap_a_and_b (dst, a, b) - sbitmap dst, a, b; +sbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -282,8 +372,7 @@ sbitmap_a_and_b (dst, a, b) Return nonzero if any change is made. */ bool -sbitmap_a_xor_b_cg (dst, a, b) - sbitmap dst, a, b; +sbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -294,7 +383,7 @@ sbitmap_a_xor_b_cg (dst, a, b) for (i = 0; i < n; i++) { SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; - changed = *dstp ^ tmp; + changed |= *dstp ^ tmp; *dstp++ = tmp; } @@ -302,8 +391,7 @@ sbitmap_a_xor_b_cg (dst, a, b) } void -sbitmap_a_xor_b (dst, a, b) - sbitmap dst, a, b; +sbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -318,8 +406,7 @@ sbitmap_a_xor_b (dst, a, b) Return nonzero if any change is made. */ bool -sbitmap_a_or_b_cg (dst, a, b) - sbitmap dst, a, b; +sbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -330,7 +417,7 @@ sbitmap_a_or_b_cg (dst, a, b) for (i = 0; i < n; i++) { SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; - changed = *dstp ^ tmp; + changed |= *dstp ^ tmp; *dstp++ = tmp; } @@ -338,8 +425,7 @@ sbitmap_a_or_b_cg (dst, a, b) } void -sbitmap_a_or_b (dst, a, b) - sbitmap dst, a, b; +sbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -353,8 +439,7 @@ sbitmap_a_or_b (dst, a, b) /* Return nonzero if A is a subset of B. */ bool -sbitmap_a_subset_b_p (a, b) - sbitmap a, b; +sbitmap_a_subset_b_p (sbitmap a, sbitmap b) { unsigned int i, n = a->size; sbitmap_ptr ap, bp; @@ -370,8 +455,7 @@ sbitmap_a_subset_b_p (a, b) Return nonzero if any change is made. */ bool -sbitmap_a_or_b_and_c_cg (dst, a, b, c) - sbitmap dst, a, b, c; +sbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -391,8 +475,7 @@ sbitmap_a_or_b_and_c_cg (dst, a, b, c) } void -sbitmap_a_or_b_and_c (dst, a, b, c) - sbitmap dst, a, b, c; +sbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -408,8 +491,7 @@ sbitmap_a_or_b_and_c (dst, a, b, c) Return nonzero if any change is made. */ bool -sbitmap_a_and_b_or_c_cg (dst, a, b, c) - sbitmap dst, a, b, c; +sbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -429,8 +511,7 @@ sbitmap_a_and_b_or_c_cg (dst, a, b, c) } void -sbitmap_a_and_b_or_c (dst, a, b, c) - sbitmap dst, a, b, c; +sbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) { unsigned int i, n = dst->size; sbitmap_ptr dstp = dst->elms; @@ -447,20 +528,19 @@ sbitmap_a_and_b_or_c (dst, a, b, c) block number BB, using the new flow graph structures. */ void -sbitmap_intersection_of_succs (dst, src, bb) - sbitmap dst; - sbitmap *src; - int bb; +sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb) { basic_block b = BASIC_BLOCK (bb); unsigned int set_size = dst->size; edge e; + unsigned ix; - for (e = b->succ; e != 0; e = e->succ_next) + for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) { + e = EDGE_SUCC (b, ix); if (e->dest == EXIT_BLOCK_PTR) continue; - + sbitmap_copy (dst, src[e->dest->index]); break; } @@ -468,11 +548,12 @@ sbitmap_intersection_of_succs (dst, src, bb) if (e == 0) sbitmap_ones (dst); else - for (e = e->succ_next; e != 0; e = e->succ_next) + for (++ix; ix < EDGE_COUNT (b->succs); ix++) { unsigned int i; sbitmap_ptr p, r; + e = EDGE_SUCC (b, ix); if (e->dest == EXIT_BLOCK_PTR) continue; @@ -487,17 +568,16 @@ sbitmap_intersection_of_succs (dst, src, bb) block number BB, using the new flow graph structures. */ void -sbitmap_intersection_of_preds (dst, src, bb) - sbitmap dst; - sbitmap *src; - int bb; +sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb) { basic_block b = BASIC_BLOCK (bb); unsigned int set_size = dst->size; edge e; + unsigned ix; - for (e = b->pred; e != 0; e = e->pred_next) + for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) { + e = EDGE_PRED (b, ix); if (e->src == ENTRY_BLOCK_PTR) continue; @@ -508,11 +588,12 @@ sbitmap_intersection_of_preds (dst, src, bb) if (e == 0) sbitmap_ones (dst); else - for (e = e->pred_next; e != 0; e = e->pred_next) + for (++ix; ix < EDGE_COUNT (b->preds); ix++) { unsigned int i; sbitmap_ptr p, r; + e = EDGE_PRED (b, ix); if (e->src == ENTRY_BLOCK_PTR) continue; @@ -527,17 +608,16 @@ sbitmap_intersection_of_preds (dst, src, bb) block number BB, using the new flow graph structures. */ void -sbitmap_union_of_succs (dst, src, bb) - sbitmap dst; - sbitmap *src; - int bb; +sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb) { basic_block b = BASIC_BLOCK (bb); unsigned int set_size = dst->size; edge e; + unsigned ix; - for (e = b->succ; e != 0; e = e->succ_next) + for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) { + e = EDGE_SUCC (b, ix); if (e->dest == EXIT_BLOCK_PTR) continue; @@ -545,14 +625,15 @@ sbitmap_union_of_succs (dst, src, bb) break; } - if (e == 0) + if (ix == EDGE_COUNT (b->succs)) sbitmap_zero (dst); else - for (e = e->succ_next; e != 0; e = e->succ_next) + for (ix++; ix < EDGE_COUNT (b->succs); ix++) { unsigned int i; sbitmap_ptr p, r; + e = EDGE_SUCC (b, ix); if (e->dest == EXIT_BLOCK_PTR) continue; @@ -567,17 +648,16 @@ sbitmap_union_of_succs (dst, src, bb) block number BB, using the new flow graph structures. */ void -sbitmap_union_of_preds (dst, src, bb) - sbitmap dst; - sbitmap *src; - int bb; +sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb) { basic_block b = BASIC_BLOCK (bb); unsigned int set_size = dst->size; edge e; + unsigned ix; - for (e = b->pred; e != 0; e = e->pred_next) + for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) { + e = EDGE_PRED (b, ix); if (e->src== ENTRY_BLOCK_PTR) continue; @@ -585,14 +665,15 @@ sbitmap_union_of_preds (dst, src, bb) break; } - if (e == 0) + if (ix == EDGE_COUNT (b->preds)) sbitmap_zero (dst); else - for (e = e->pred_next; e != 0; e = e->pred_next) + for (ix++; ix < EDGE_COUNT (b->preds); ix++) { unsigned int i; sbitmap_ptr p, r; + e = EDGE_PRED (b, ix); if (e->src == ENTRY_BLOCK_PTR) continue; @@ -607,20 +688,20 @@ sbitmap_union_of_preds (dst, src, bb) /* Return number of first bit set in the bitmap, -1 if none. */ int -sbitmap_first_set_bit (bmap) - sbitmap bmap; +sbitmap_first_set_bit (sbitmap bmap) { - unsigned int n; + unsigned int n = 0; + sbitmap_iterator sbi; - EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; }); + EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi) + return n; return -1; } /* Return number of last bit set in the bitmap, -1 if none. */ int -sbitmap_last_set_bit (bmap) - sbitmap bmap; +sbitmap_last_set_bit (sbitmap bmap) { int i; SBITMAP_ELT_TYPE *ptr = bmap->elms; @@ -650,9 +731,7 @@ sbitmap_last_set_bit (bmap) } void -dump_sbitmap (file, bmap) - FILE *file; - sbitmap bmap; +dump_sbitmap (FILE *file, sbitmap bmap) { unsigned int i, n, j; unsigned int set_size = bmap->size; @@ -673,9 +752,7 @@ dump_sbitmap (file, bmap) } void -dump_sbitmap_file (file, bmap) - FILE *file; - sbitmap bmap; +dump_sbitmap_file (FILE *file, sbitmap bmap) { unsigned int i, pos; @@ -698,18 +775,14 @@ dump_sbitmap_file (file, bmap) } void -debug_sbitmap (bmap) - sbitmap bmap; +debug_sbitmap (sbitmap bmap) { dump_sbitmap_file (stderr, bmap); } void -dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) - FILE *file; - const char *title, *subtitle; - sbitmap *bmaps; - int n_maps; +dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle, + sbitmap *bmaps, int n_maps) { int bb;