diff options
author | obrien <obrien@FreeBSD.org> | 2002-02-01 18:16:02 +0000 |
---|---|---|
committer | obrien <obrien@FreeBSD.org> | 2002-02-01 18:16:02 +0000 |
commit | c9ab9ae440a8066b2c2b85b157b1fdadcf09916a (patch) | |
tree | 086d9d6c8fbd4fc8fe4495059332f66bc0f8d12b /contrib/gcc/sbitmap.c | |
parent | 2ecfd8bd04b63f335c1ec6295740a4bfd97a4fa6 (diff) | |
download | FreeBSD-src-c9ab9ae440a8066b2c2b85b157b1fdadcf09916a.zip FreeBSD-src-c9ab9ae440a8066b2c2b85b157b1fdadcf09916a.tar.gz |
Enlist the FreeBSD-CURRENT users as testers of what is to become Gcc 3.1.0.
These bits are taken from the FSF anoncvs repo on 1-Feb-2002 08:20 PST.
Diffstat (limited to 'contrib/gcc/sbitmap.c')
-rw-r--r-- | contrib/gcc/sbitmap.c | 546 |
1 files changed, 353 insertions, 193 deletions
diff --git a/contrib/gcc/sbitmap.c b/contrib/gcc/sbitmap.c index 2a41792..cd9deba 100644 --- a/contrib/gcc/sbitmap.c +++ b/contrib/gcc/sbitmap.c @@ -1,27 +1,28 @@ /* Simple bitmaps. - Copyright (C) 1999 Free Software Foundation, Inc. + Copyright (C) 1999, 2000 Free Software Foundation, Inc. -This file is part of GNU CC. +This file is part of GCC. -GNU CC is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 2, or (at your option) any later +version. -GNU CC is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. You should have received a copy of the GNU General Public License -along with GNU CC; see the file COPYING. If not, write to -the Free Software Foundation, 59 Temple Place - Suite 330, -Boston, MA 02111-1307, USA. */ +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. */ #include "config.h" #include "system.h" #include "rtl.h" #include "flags.h" +#include "hard-reg-set.h" #include "basic-block.h" /* Bitmap manipulation routines. */ @@ -30,9 +31,9 @@ Boston, MA 02111-1307, USA. */ sbitmap sbitmap_alloc (n_elms) - int n_elms; + unsigned int n_elms; { - int bytes, size, amt; + unsigned int bytes, size, amt; sbitmap bmap; size = SBITMAP_SET_SIZE (n_elms); @@ -50,9 +51,9 @@ sbitmap_alloc (n_elms) sbitmap * sbitmap_vector_alloc (n_vecs, n_elms) - int n_vecs, n_elms; + unsigned int n_vecs, n_elms; { - int i, bytes, offset, elm_bytes, size, amt, vector_bytes; + unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; sbitmap *bitmap_vector; size = SBITMAP_SET_SIZE (n_elms); @@ -76,11 +77,10 @@ sbitmap_vector_alloc (n_vecs, n_elms) amt = vector_bytes + (n_vecs * elm_bytes); bitmap_vector = (sbitmap *) xmalloc (amt); - for (i = 0, offset = vector_bytes; - i < n_vecs; - i++, offset += elm_bytes) + for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) { sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); + bitmap_vector[i] = b; b->n_bits = n_elms; b->size = size; @@ -96,26 +96,39 @@ void sbitmap_copy (dst, src) sbitmap dst, src; { - bcopy ((PTR) src->elms, (PTR) dst->elms, - sizeof (SBITMAP_ELT_TYPE) * dst->size); + memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); } +/* Determine if a == b. */ +int +sbitmap_equal (a, b) + sbitmap a, b; +{ + return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); +} /* Zero all elements in a bitmap. */ void sbitmap_zero (bmap) sbitmap bmap; { - bzero ((char *) bmap->elms, bmap->bytes); + memset ((PTR) bmap->elms, 0, bmap->bytes); } -/* Set to ones all elements in a bitmap. */ +/* Set all elements in a bitmap to ones. */ void sbitmap_ones (bmap) sbitmap bmap; { - memset (bmap->elms, -1, bmap->bytes); + unsigned int last_bit; + + memset ((PTR) bmap->elms, -1, bmap->bytes); + + 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); } /* Zero a vector of N_VECS bitmaps. */ @@ -123,22 +136,22 @@ sbitmap_ones (bmap) void sbitmap_vector_zero (bmap, n_vecs) sbitmap *bmap; - int n_vecs; + unsigned int n_vecs; { - int i; + unsigned int i; for (i = 0; i < n_vecs; i++) sbitmap_zero (bmap[i]); } -/* Set to ones a vector of N_VECS bitmaps. */ +/* Set a vector of N_VECS bitmaps to ones. */ void sbitmap_vector_ones (bmap, n_vecs) sbitmap *bmap; - int n_vecs; + unsigned int n_vecs; { - int i; + unsigned int i; for (i = 0; i < n_vecs; i++) sbitmap_ones (bmap[i]); @@ -152,22 +165,22 @@ int sbitmap_union_of_diff (dst, a, b, c) sbitmap dst, a, b, c; { - int i,changed; + unsigned int i; sbitmap_ptr dstp, ap, bp, cp; + int changed = 0; - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - cp = c->elms; - for (i = 0; i < dst->size; i++) + for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0; + i < dst->size; i++, dstp++) { - SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp); + SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); + if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; cp++; + { + changed = 1; + *dstp = tmp; + } } + return changed; } @@ -177,61 +190,78 @@ void sbitmap_not (dst, src) sbitmap dst, src; { - int i; - sbitmap_ptr dstp, ap; + unsigned int i; + sbitmap_ptr dstp, srcp; - dstp = dst->elms; - ap = src->elms; - for (i = 0; i < dst->size; i++) - { - SBITMAP_ELT_TYPE tmp = ~(*ap); - *dstp = tmp; - dstp++; ap++; - } + for (dstp = dst->elms, srcp = src->elms, i = 0; i < dst->size; i++) + *dstp++ = ~(*srcp++); } /* Set the bits in DST to be the difference between the bits - in A and the bits in B. i.e. dst = a - b. - The - operator is implemented as a & (~b). */ + in A and the bits in B. i.e. dst = a & (~b). */ void sbitmap_difference (dst, a, b) sbitmap dst, a, b; { - int i; + unsigned int i; sbitmap_ptr dstp, ap, bp; - - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - for (i = 0; i < dst->size; i++) + + for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; i++) *dstp++ = *ap++ & (~*bp++); } -/* Set DST to be (A and B)). +/* Set DST to be (A and B). Return non-zero if any change is made. */ int sbitmap_a_and_b (dst, a, b) sbitmap dst, a, b; { - int i,changed; + unsigned int i; sbitmap_ptr dstp, ap, bp; + int changed = 0; + + for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; + i++, dstp++) + { + SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; + + if (*dstp != tmp) + { + changed = 1; + *dstp = tmp; + } + } + + return changed; +} + +/* Set DST to be (A xor B)). + Return non-zero if any change is made. */ - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - for (i = 0; i < dst->size; i++) +int +sbitmap_a_xor_b (dst, a, b) + sbitmap dst, a, b; +{ + unsigned int i; + sbitmap_ptr dstp, ap, bp; + int changed = 0; + + for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; + i++, dstp++) { - SBITMAP_ELT_TYPE tmp = *ap & *bp; + SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; + if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; + { + changed = 1; + *dstp = tmp; + } } return changed; } + /* Set DST to be (A or B)). Return non-zero if any change is made. */ @@ -239,24 +269,41 @@ int sbitmap_a_or_b (dst, a, b) sbitmap dst, a, b; { - int i,changed; + unsigned int i; sbitmap_ptr dstp, ap, bp; + int changed = 0; - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - for (i = 0; i < dst->size; i++) + for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; + i++, dstp++) { - SBITMAP_ELT_TYPE tmp = *ap | *bp; + SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; + if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; + { + changed = 1; + *dstp = tmp; + } } + return changed; } +/* Return non-zero if A is a subset of B. */ + +int +sbitmap_a_subset_b_p (a, b) + sbitmap a, b; +{ + unsigned int i; + sbitmap_ptr ap, bp; + + for (ap = a->elms, bp = b->elms, i = 0; i < a->size; i++, ap++, bp++) + if ((*ap | *bp) != *bp) + return 0; + + return 1; +} + /* Set DST to be (A or (B and C)). Return non-zero if any change is made. */ @@ -264,169 +311,256 @@ int sbitmap_a_or_b_and_c (dst, a, b, c) sbitmap dst, a, b, c; { - int i,changed; + unsigned int i; sbitmap_ptr dstp, ap, bp, cp; + int changed = 0; - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - cp = c->elms; - for (i = 0; i < dst->size; i++) + for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0; + i < dst->size; i++, dstp++) { - SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp); + SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); + if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; cp++; + { + changed = 1; + *dstp = tmp; + } } + return changed; } -/* Set DST to be (A ann (B or C)). +/* Set DST to be (A and (B or C)). Return non-zero if any change is made. */ int sbitmap_a_and_b_or_c (dst, a, b, c) sbitmap dst, a, b, c; { - int i,changed; + unsigned int i; sbitmap_ptr dstp, ap, bp, cp; + int changed = 0; - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - cp = c->elms; - for (i = 0; i < dst->size; i++) + for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0; + i < dst->size; i++, dstp++) { - SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp); + SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); + if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; cp++; + { + changed = 1; + *dstp = tmp; + } } + return changed; } -/* Set the bitmap DST to the intersection of SRC of all predecessors or - successors of block number BB (PRED_SUCC says which). */ +#ifdef IN_GCC +/* Set the bitmap DST to the intersection of SRC of successors of + block number BB, using the new flow graph structures. */ void -sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ) +sbitmap_intersection_of_succs (dst, src, bb) sbitmap dst; sbitmap *src; int bb; - int_list_ptr *pred_succ; { - int_list_ptr ps; - int ps_bb; - int set_size = dst->size; + basic_block b = BASIC_BLOCK (bb); + unsigned int set_size = dst->size; + edge e; - ps = pred_succ[bb]; - - /* It is possible that there are no predecessors(/successors). - This can happen for example in unreachable code. */ - - if (ps == NULL) + for (e = b->succ; e != 0; e = e->succ_next) { - /* In APL-speak this is the `and' reduction of the empty set and thus - the result is the identity for `and'. */ - sbitmap_ones (dst); - return; - } + if (e->dest == EXIT_BLOCK_PTR) + continue; - /* Set result to first predecessor/successor. */ - - for ( ; ps != NULL; ps = ps->next) - { - ps_bb = INT_LIST_VAL (ps); - if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) - continue; - sbitmap_copy (dst, src[ps_bb]); - /* Break out since we're only doing first predecessor. */ + sbitmap_copy (dst, src[e->dest->index]); break; } - if (ps == NULL) - return; - /* Now do the remaining predecessors/successors. */ + if (e == 0) + sbitmap_ones (dst); + else + for (e = e->succ_next; e != 0; e = e->succ_next) + { + unsigned int i; + sbitmap_ptr p, r; + + if (e->dest == EXIT_BLOCK_PTR) + continue; + + p = src[e->dest->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ &= *p++; + } +} - for (ps = ps->next; ps != NULL; ps = ps->next) - { - int i; - sbitmap_ptr p,r; +/* Set the bitmap DST to the intersection of SRC of predecessors of + block number BB, using the new flow graph structures. */ - ps_bb = INT_LIST_VAL (ps); - if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) - continue; +void +sbitmap_intersection_of_preds (dst, src, bb) + sbitmap dst; + sbitmap *src; + int bb; +{ + basic_block b = BASIC_BLOCK (bb); + unsigned int set_size = dst->size; + edge e; - p = src[ps_bb]->elms; - r = dst->elms; + for (e = b->pred; e != 0; e = e->pred_next) + { + if (e->src == ENTRY_BLOCK_PTR) + continue; - for (i = 0; i < set_size; i++) - *r++ &= *p++; + sbitmap_copy (dst, src[e->src->index]); + break; } + + if (e == 0) + sbitmap_ones (dst); + else + for (e = e->pred_next; e != 0; e = e->pred_next) + { + unsigned int i; + sbitmap_ptr p, r; + + if (e->src == ENTRY_BLOCK_PTR) + continue; + + p = src[e->src->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ &= *p++; + } } -/* Set the bitmap DST to the union of SRC of all predecessors/successors of - block number BB. */ +/* Set the bitmap DST to the union of SRC of successors of + block number BB, using the new flow graph structures. */ void -sbitmap_union_of_predsucc (dst, src, bb, pred_succ) +sbitmap_union_of_succs (dst, src, bb) sbitmap dst; sbitmap *src; int bb; - int_list_ptr *pred_succ; { - int_list_ptr ps; - int ps_bb; - int set_size = dst->size; + basic_block b = BASIC_BLOCK (bb); + unsigned int set_size = dst->size; + edge e; - ps = pred_succ[bb]; - - /* It is possible that there are no predecessors(/successors). - This can happen for example in unreachable code. */ - - if (ps == NULL) + for (e = b->succ; e != 0; e = e->succ_next) { - /* In APL-speak this is the `or' reduction of the empty set and thus - the result is the identity for `or'. */ - sbitmap_zero (dst); - return; + if (e->dest == EXIT_BLOCK_PTR) + continue; + + sbitmap_copy (dst, src[e->dest->index]); + break; } - /* Set result to first predecessor/successor. */ + if (e == 0) + sbitmap_zero (dst); + else + for (e = e->succ_next; e != 0; e = e->succ_next) + { + unsigned int i; + sbitmap_ptr p, r; + + if (e->dest == EXIT_BLOCK_PTR) + continue; + + p = src[e->dest->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ |= *p++; + } +} + +/* Set the bitmap DST to the union of SRC of predecessors of + block number BB, using the new flow graph structures. */ + +void +sbitmap_union_of_preds (dst, src, bb) + sbitmap dst; + sbitmap *src; + int bb; +{ + basic_block b = BASIC_BLOCK (bb); + unsigned int set_size = dst->size; + edge e; - for ( ; ps != NULL; ps = ps->next) + for (e = b->pred; e != 0; e = e->pred_next) { - ps_bb = INT_LIST_VAL (ps); - if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) - continue; - sbitmap_copy (dst, src[ps_bb]); - /* Break out since we're only doing first predecessor. */ + if (e->src== ENTRY_BLOCK_PTR) + continue; + + sbitmap_copy (dst, src[e->src->index]); break; } - if (ps == NULL) - return; - /* Now do the remaining predecessors/successors. */ + if (e == 0) + sbitmap_zero (dst); + else + for (e = e->pred_next; e != 0; e = e->pred_next) + { + unsigned int i; + sbitmap_ptr p, r; + + if (e->src == ENTRY_BLOCK_PTR) + continue; + + p = src[e->src->index]->elms; + r = dst->elms; + for (i = 0; i < set_size; i++) + *r++ |= *p++; + } +} +#endif - for (ps = ps->next; ps != NULL; ps = ps->next) - { - int i; - sbitmap_ptr p,r; +/* Return number of first bit set in the bitmap, -1 if none. */ + +int +sbitmap_first_set_bit (bmap) + sbitmap bmap; +{ + unsigned int n; + + EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; }); + return -1; +} - ps_bb = INT_LIST_VAL (ps); - if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) - continue; +/* Return number of last bit set in the bitmap, -1 if none. */ - p = src[ps_bb]->elms; - r = dst->elms; +int +sbitmap_last_set_bit (bmap) + sbitmap bmap; +{ + int i; + SBITMAP_ELT_TYPE *ptr = bmap->elms; - for (i = 0; i < set_size; i++) - *r++ |= *p++; + for (i = bmap->size - 1; i >= 0; i--) + { + SBITMAP_ELT_TYPE word = ptr[i]; + + if (word != 0) + { + unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; + SBITMAP_ELT_TYPE mask + = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); + + while (1) + { + if ((word & mask) != 0) + return index; + + mask >>= 1; + index--; + } + } } + + return -1; } void @@ -434,24 +568,49 @@ dump_sbitmap (file, bmap) FILE *file; sbitmap bmap; { - int i,j,n; - int set_size = bmap->size; - int total_bits = bmap->n_bits; + unsigned int i, n, j; + unsigned int set_size = bmap->size; + unsigned int total_bits = bmap->n_bits; fprintf (file, " "); for (i = n = 0; i < set_size && n < total_bits; i++) - { - for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) - { - if (n != 0 && n % 10 == 0) - fprintf (file, " "); - fprintf (file, "%d", (bmap->elms[i] & (1L << j)) != 0); - } - } + for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) + { + if (n != 0 && n % 10 == 0) + fprintf (file, " "); + + fprintf (file, "%d", + (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); + } + fprintf (file, "\n"); } void +debug_sbitmap (bmap) + sbitmap bmap; +{ + unsigned int i, pos; + + fprintf (stderr, "n_bits = %d, set = {", bmap->n_bits); + + for (pos = 30, i = 0; i < bmap->n_bits; i++) + if (TEST_BIT (bmap, i)) + { + if (pos > 70) + { + fprintf (stderr, "\n"); + pos = 0; + } + + fprintf (stderr, "%d ", i); + pos += 1 + (i >= 10) + (i >= 100); + } + + fprintf (stderr, "}\n"); +} + +void dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) FILE *file; const char *title, *subtitle; @@ -466,5 +625,6 @@ dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) fprintf (file, "%s %d\n", subtitle, bb); dump_sbitmap (file, bmaps[bb]); } + fprintf (file, "\n"); } |