diff options
| -rw-r--r-- | gcc/ChangeLog | 8 | ||||
| -rw-r--r-- | gcc/Makefile.in | 7 | ||||
| -rw-r--r-- | gcc/basic-block.h | 107 | ||||
| -rw-r--r-- | gcc/flow.c | 496 | ||||
| -rw-r--r-- | gcc/sbitmap.c | 469 | ||||
| -rw-r--r-- | gcc/sbitmap.h | 122 |
6 files changed, 606 insertions, 603 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 8207d2cda38..e9463238076 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +Tue Jan 12 00:06:00 1999 Richard Henderson <rth@cygnus.com> + + * Makefile.in (OBJECTS): Add sbitmap.o. + (BASIC_BLOCK_H): Add sbitmap.h. + * basic-block.h: Move simple bitmap code to sbitmap.h. + * flow.c: Move simple bitmap code to sbitmap.c + * sbitmap.h, sbitmap.c: New files. + Mon Jan 11 23:51:50 1999 Richard Henderson <rth@cygnus.com> * alpha.h (TARGET_SWITCHES): Document switches. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index b07d3d6bb85..4db32f0571f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -655,7 +655,7 @@ OBJS = toplev.o version.o tree.o print-tree.o stor-layout.o fold-const.o \ insn-peep.o reorg.o $(SCHED_PREFIX)sched.o final.o recog.o reg-stack.o \ insn-opinit.o insn-recog.o insn-extract.o insn-output.o insn-emit.o \ profile.o insn-attrtab.o $(out_object_file) getpwd.o $(EXTRA_OBJS) convert.o \ - mbchar.o dyn-string.o splay-tree.o graph.o + mbchar.o dyn-string.o splay-tree.o graph.o sbitmap.o # GEN files are listed separately, so they can be built before doing parallel # makes for cc1 or cc1plus. Otherwise sequent parallel make attempts to load @@ -731,7 +731,7 @@ CONFIG_H = RTL_BASE_H = rtl.h rtl.def machmode.h machmode.def RTL_H = $(RTL_BASE_H) genrtl.h TREE_H = tree.h real.h tree.def machmode.h machmode.def tree-check.h -BASIC_BLOCK_H = basic-block.h bitmap.h +BASIC_BLOCK_H = basic-block.h bitmap.h sbitmap.h DEMANGLE_H = $(srcdir)/../include/demangle.h RECOG_H = recog.h EXPR_H = expr.h insn-codes.h @@ -1298,7 +1298,8 @@ c-iterate.o: c-iterate.c $(CONFIG_H) system.h $(TREE_H) $(RTL_H) c-tree.h \ flags.h toplev.h $(EXPR_H) mbchar.o: mbchar.c $(CONFIG_H) system.h mbchar.h graph.o: graph.c $(CONFIG_H) system.h toplev.h flags.h output.h $(RTL_H) \ - hard-reg-set.h basic-block.h + hard-reg-set.h $(BASIC_BLOCK_H) +sbitmap.o: sbitmap.c $(CONFIG_H) system.h $(RTL_H) flags.h $(BASIC_BLOCK_H) collect2$(exeext): collect2.o tlink.o hash.o cplus-dem.o underscore.o \ version.o choose-temp.o mkstemp.o $(LIBDEPS) diff --git a/gcc/basic-block.h b/gcc/basic-block.h index 2bd575c725e..d54ffe8b26c 100644 --- a/gcc/basic-block.h +++ b/gcc/basic-block.h @@ -20,6 +20,7 @@ Boston, MA 02111-1307, USA. */ #include "bitmap.h" +#include "sbitmap.h" typedef bitmap regset; /* Head of register set linked list. */ @@ -188,114 +189,12 @@ extern void free_regset_vector PROTO ((regset *, int nelts)); extern int *uid_block_number; #define BLOCK_NUM(INSN) uid_block_number[INSN_UID (INSN)] -extern void compute_preds_succs PROTO ((int_list_ptr *, int_list_ptr *, - int *, int *)); extern void dump_bb_data PROTO ((FILE *, int_list_ptr *, int_list_ptr *, int)); extern void free_bb_mem PROTO ((void)); extern void free_basic_block_vars PROTO ((int)); - -/* Simple bitmaps. - It's not clear yet whether using bitmap.[ch] will be a win. - It should be straightforward to convert so for now we keep things simple - while more important issues are dealt with. */ - -#define SBITMAP_ELT_BITS HOST_BITS_PER_WIDE_INT -#define SBITMAP_ELT_TYPE unsigned HOST_WIDE_INT - -typedef struct simple_bitmap_def { - /* Number of bits. */ - int n_bits; - /* Size in elements. */ - int size; - /* Size in bytes. */ - int bytes; - /* The elements. */ - SBITMAP_ELT_TYPE elms[1]; -} *sbitmap; - -typedef SBITMAP_ELT_TYPE *sbitmap_ptr; - -/* Return the set size needed for N elements. */ -#define SBITMAP_SET_SIZE(n) (((n) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) - -/* set bit number bitno in the bitmap */ -#define SET_BIT(bitmap, bitno) \ -do { \ - (bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; \ -} while (0) - -/* test if bit number bitno in the bitmap is set */ -#define TEST_BIT(bitmap, bitno) \ -((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] & ((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS)) - -/* reset bit number bitno in the bitmap */ -#define RESET_BIT(bitmap, bitno) \ -do { \ - (bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); \ -} while (0) - -/* Loop over all elements of SBITSET, starting with MIN. */ -#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \ -do { \ - unsigned int bit_num_ = (MIN) % (unsigned) SBITMAP_ELT_BITS; \ - unsigned int word_num_ = (MIN) / (unsigned) SBITMAP_ELT_BITS; \ - unsigned int size_ = (SBITMAP)->size; \ - SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \ - \ - while (word_num_ < size_) \ - { \ - SBITMAP_ELT_TYPE word_ = ptr_[word_num_]; \ - if (word_ != 0) \ - { \ - for (; bit_num_ < SBITMAP_ELT_BITS; ++bit_num_) \ - { \ - SBITMAP_ELT_TYPE mask_ = (SBITMAP_ELT_TYPE)1 << bit_num_; \ - if ((word_ & mask_) != 0) \ - { \ - word_ &= ~mask_; \ - (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \ - CODE; \ - if (word_ == 0) \ - break; \ - } \ - } \ - } \ - bit_num_ = 0; \ - word_num_++; \ - } \ -} while (0) - -#define sbitmap_free(map) free(map) -#define sbitmap_vector_free(vec) free(vec) - -extern void dump_sbitmap PROTO ((FILE *, sbitmap)); -extern void dump_sbitmap_vector PROTO ((FILE *, char *, char *, - sbitmap *, int)); -extern sbitmap sbitmap_alloc PROTO ((int)); -extern sbitmap *sbitmap_vector_alloc PROTO ((int, int)); -extern void sbitmap_copy PROTO ((sbitmap, sbitmap)); -extern void sbitmap_zero PROTO ((sbitmap)); -extern void sbitmap_ones PROTO ((sbitmap)); -extern void sbitmap_vector_zero PROTO ((sbitmap *, int)); -extern void sbitmap_vector_ones PROTO ((sbitmap *, int)); -extern int sbitmap_union_of_diff PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); -extern void sbitmap_difference PROTO ((sbitmap, sbitmap, sbitmap)); -extern void sbitmap_not PROTO ((sbitmap, sbitmap)); -extern int sbitmap_a_or_b_and_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); -extern int sbitmap_a_and_b_or_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); -extern int sbitmap_a_and_b PROTO ((sbitmap, sbitmap, sbitmap)); -extern int sbitmap_a_or_b PROTO ((sbitmap, sbitmap, sbitmap)); -extern void sbitmap_intersect_of_predsucc PROTO ((sbitmap, sbitmap *, - int, int_list_ptr *)); -extern void sbitmap_intersect_of_predecessors PROTO ((sbitmap, sbitmap *, int, - int_list_ptr *)); -extern void sbitmap_intersect_of_successors PROTO ((sbitmap, sbitmap *, int, - int_list_ptr *)); -extern void sbitmap_union_of_predecessors PROTO ((sbitmap, sbitmap *, int, - int_list_ptr *)); -extern void sbitmap_union_of_successors PROTO ((sbitmap, sbitmap *, int, - int_list_ptr *)); +extern void compute_preds_succs PROTO ((int_list_ptr *, int_list_ptr *, + int *, int *)); extern void compute_dominators PROTO ((sbitmap *, sbitmap *, int_list_ptr *, int_list_ptr *)); diff --git a/gcc/flow.c b/gcc/flow.c index 88466872985..fa19d9eb8b8 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -3505,46 +3505,6 @@ dump_bb_data (file, preds, succs, live_info) fprintf (file, "\n"); } -void -dump_sbitmap (file, bmap) - FILE *file; - sbitmap bmap; -{ - int i,j,n; - int set_size = bmap->size; - 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); - } - } - fprintf (file, "\n"); -} - -void -dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) - FILE *file; - char *title, *subtitle; - sbitmap *bmaps; - int n_maps; -{ - int bb; - - fprintf (file, "%s\n", title); - for (bb = 0; bb < n_maps; bb++) - { - fprintf (file, "%s %d\n", subtitle, bb); - dump_sbitmap (file, bmaps[bb]); - } - fprintf (file, "\n"); -} - /* Free basic block data storage. */ void @@ -3552,462 +3512,6 @@ free_bb_mem () { free_int_list (&pred_int_list_blocks); } - -/* Bitmap manipulation routines. */ - -/* Allocate a simple bitmap of N_ELMS bits. */ - -sbitmap -sbitmap_alloc (n_elms) - int n_elms; -{ - 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)); - bmap = (sbitmap) xmalloc (amt); - bmap->n_bits = n_elms; - bmap->size = size; - bmap->bytes = bytes; - return bmap; -} - -/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ - -sbitmap * -sbitmap_vector_alloc (n_vecs, n_elms) - int n_vecs, n_elms; -{ - int i, bytes, offset, elm_bytes, size, amt, vector_bytes; - sbitmap *bitmap_vector; - - size = SBITMAP_SET_SIZE (n_elms); - bytes = size * sizeof (SBITMAP_ELT_TYPE); - elm_bytes = (sizeof (struct simple_bitmap_def) - + bytes - sizeof (SBITMAP_ELT_TYPE)); - vector_bytes = n_vecs * sizeof (sbitmap *); - - /* Round up `vector_bytes' to account for the alignment requirements - of an sbitmap. One could allocate the vector-table and set of sbitmaps - separately, but that requires maintaining two pointers or creating - a cover struct to hold both pointers (so our result is still just - one pointer). Neither is a bad idea, but this is simpler for now. */ - { - /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ - struct { char x; SBITMAP_ELT_TYPE y; } align; - int alignment = (char *) & align.y - & align.x; - vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); - } - - 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) - { - sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); - bitmap_vector[i] = b; - b->n_bits = n_elms; - b->size = size; - b->bytes = bytes; - } - - return bitmap_vector; -} - -/* Copy sbitmap SRC to DST. */ - -void -sbitmap_copy (dst, src) - sbitmap dst, src; -{ - bcopy ((PTR) src->elms, (PTR) dst->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); -} - -/* Zero all elements in a bitmap. */ - -void -sbitmap_zero (bmap) - sbitmap bmap; -{ - bzero ((char *) bmap->elms, bmap->bytes); -} - -/* Set to ones all elements in a bitmap. */ - -void -sbitmap_ones (bmap) - sbitmap bmap; -{ - memset (bmap->elms, -1, bmap->bytes); -} - -/* Zero a vector of N_VECS bitmaps. */ - -void -sbitmap_vector_zero (bmap, n_vecs) - sbitmap *bmap; - int n_vecs; -{ - int i; - - for (i = 0; i < n_vecs; i++) - sbitmap_zero (bmap[i]); -} - -/* Set to ones a vector of N_VECS bitmaps. */ - -void -sbitmap_vector_ones (bmap, n_vecs) - sbitmap *bmap; - int n_vecs; -{ - int i; - - for (i = 0; i < n_vecs; i++) - sbitmap_ones (bmap[i]); -} - -/* Set DST to be A union (B - C). - DST = A | (B & ~C). - Return non-zero if any change is made. */ - -int -sbitmap_union_of_diff (dst, a, b, c) - sbitmap dst, a, b, c; -{ - int i,changed; - sbitmap_ptr dstp, ap, bp, cp; - - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - cp = c->elms; - for (i = 0; i < dst->size; i++) - { - SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp); - if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; cp++; - } - return changed; -} - -/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ - -void -sbitmap_not (dst, src) - sbitmap dst, src; -{ - int i; - sbitmap_ptr dstp, ap; - - dstp = dst->elms; - ap = src->elms; - for (i = 0; i < dst->size; i++) - { - SBITMAP_ELT_TYPE tmp = ~(*ap); - *dstp = tmp; - dstp++; ap++; - } -} - -/* 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). */ - -void -sbitmap_difference (dst, a, b) - sbitmap dst, a, b; -{ - int i; - sbitmap_ptr dstp, ap, bp; - - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - for (i = 0; i < dst->size; i++) - *dstp++ = *ap++ & (~*bp++); -} - -/* 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; - sbitmap_ptr dstp, ap, bp; - - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - for (i = 0; i < dst->size; i++) - { - SBITMAP_ELT_TYPE tmp = *ap & *bp; - if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; - } - return changed; -} -/* Set DST to be (A or B)). - Return non-zero if any change is made. */ - -int -sbitmap_a_or_b (dst, a, b) - sbitmap dst, a, b; -{ - int i,changed; - sbitmap_ptr dstp, ap, bp; - - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - for (i = 0; i < dst->size; i++) - { - SBITMAP_ELT_TYPE tmp = *ap | *bp; - if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; - } - return changed; -} - -/* Set DST to be (A or (B and C)). - Return non-zero if any change is made. */ - -int -sbitmap_a_or_b_and_c (dst, a, b, c) - sbitmap dst, a, b, c; -{ - int i,changed; - sbitmap_ptr dstp, ap, bp, cp; - - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - cp = c->elms; - for (i = 0; i < dst->size; i++) - { - SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp); - if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; cp++; - } - return changed; -} - -/* Set DST to be (A ann (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; - sbitmap_ptr dstp, ap, bp, cp; - - changed = 0; - dstp = dst->elms; - ap = a->elms; - bp = b->elms; - cp = c->elms; - for (i = 0; i < dst->size; i++) - { - SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp); - if (*dstp != tmp) - changed = 1; - *dstp = tmp; - dstp++; ap++; bp++; cp++; - } - return changed; -} - -/* Set the bitmap DST to the intersection of SRC of all predecessors or - successors of block number BB (PRED_SUCC says which). */ - -void -sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ) - sbitmap dst; - sbitmap *src; - int bb; - int_list_ptr *pred_succ; -{ - int_list_ptr ps; - int ps_bb; - int set_size = dst->size; - - ps = pred_succ[bb]; - - /* It is possible that there are no predecessors(/successors). - This can happen for example in unreachable code. */ - - if (ps == NULL) - { - /* 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; - } - - /* 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. */ - break; - } - if (ps == NULL) - return; - - /* Now do the remaining predecessors/successors. */ - - for (ps = ps->next; ps != NULL; ps = ps->next) - { - int i; - sbitmap_ptr p,r; - - ps_bb = INT_LIST_VAL (ps); - if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) - continue; - - p = src[ps_bb]->elms; - r = dst->elms; - - for (i = 0; i < set_size; i++) - *r++ &= *p++; - } -} - -/* Set the bitmap DST to the intersection of SRC of all predecessors - of block number BB. */ - -void -sbitmap_intersect_of_predecessors (dst, src, bb, s_preds) - sbitmap dst; - sbitmap *src; - int bb; - int_list_ptr *s_preds; -{ - sbitmap_intersect_of_predsucc (dst, src, bb, s_preds); -} - -/* Set the bitmap DST to the intersection of SRC of all successors - of block number BB. */ - -void -sbitmap_intersect_of_successors (dst, src, bb, s_succs) - sbitmap dst; - sbitmap *src; - int bb; - int_list_ptr *s_succs; -{ - sbitmap_intersect_of_predsucc (dst, src, bb, s_succs); -} - -/* Set the bitmap DST to the union of SRC of all predecessors/successors of - block number BB. */ - -void -sbitmap_union_of_predsucc (dst, src, bb, pred_succ) - sbitmap dst; - sbitmap *src; - int bb; - int_list_ptr *pred_succ; -{ - int_list_ptr ps; - int ps_bb; - int set_size = dst->size; - - ps = pred_succ[bb]; - - /* It is possible that there are no predecessors(/successors). - This can happen for example in unreachable code. */ - - if (ps == NULL) - { - /* 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; - } - - /* 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. */ - break; - } - if (ps == NULL) - return; - - /* Now do the remaining predecessors/successors. */ - - for (ps = ps->next; ps != NULL; ps = ps->next) - { - int i; - sbitmap_ptr p,r; - - ps_bb = INT_LIST_VAL (ps); - if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) - continue; - - p = src[ps_bb]->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 of - block number BB. */ - -void -sbitmap_union_of_predecessors (dst, src, bb, s_preds) - sbitmap dst; - sbitmap *src; - int bb; - int_list_ptr *s_preds; -{ - sbitmap_union_of_predsucc (dst, src, bb, s_preds); -} - -/* Set the bitmap DST to the union of SRC of all predecessors of - block number BB. */ - -void -sbitmap_union_of_successors (dst, src, bb, s_succ) - sbitmap dst; - sbitmap *src; - int bb; - int_list_ptr *s_succ; -{ - sbitmap_union_of_predsucc (dst, src, bb, s_succ); -} /* Compute dominator relationships. */ void diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c new file mode 100644 index 00000000000..db47d327ea5 --- /dev/null +++ b/gcc/sbitmap.c @@ -0,0 +1,469 @@ +/* Simple bitmaps. + Copyright (C) 1999 Free Software Foundation, Inc. + +This file is part of GNU CC. + +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. + +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. + +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. */ + +#include "config.h" +#include "system.h" +#include "rtl.h" +#include "flags.h" +#include "basic-block.h" + +/* Bitmap manipulation routines. */ + +/* Allocate a simple bitmap of N_ELMS bits. */ + +sbitmap +sbitmap_alloc (n_elms) + int n_elms; +{ + 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)); + bmap = (sbitmap) xmalloc (amt); + bmap->n_bits = n_elms; + bmap->size = size; + bmap->bytes = bytes; + return bmap; +} + +/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ + +sbitmap * +sbitmap_vector_alloc (n_vecs, n_elms) + int n_vecs, n_elms; +{ + int i, bytes, offset, elm_bytes, size, amt, vector_bytes; + sbitmap *bitmap_vector; + + size = SBITMAP_SET_SIZE (n_elms); + bytes = size * sizeof (SBITMAP_ELT_TYPE); + elm_bytes = (sizeof (struct simple_bitmap_def) + + bytes - sizeof (SBITMAP_ELT_TYPE)); + vector_bytes = n_vecs * sizeof (sbitmap *); + + /* Round up `vector_bytes' to account for the alignment requirements + of an sbitmap. One could allocate the vector-table and set of sbitmaps + separately, but that requires maintaining two pointers or creating + a cover struct to hold both pointers (so our result is still just + one pointer). Neither is a bad idea, but this is simpler for now. */ + { + /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ + struct { char x; SBITMAP_ELT_TYPE y; } align; + int alignment = (char *) & align.y - & align.x; + vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); + } + + 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) + { + sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); + bitmap_vector[i] = b; + b->n_bits = n_elms; + b->size = size; + b->bytes = bytes; + } + + return bitmap_vector; +} + +/* Copy sbitmap SRC to DST. */ + +void +sbitmap_copy (dst, src) + sbitmap dst, src; +{ + bcopy (src->elms, dst->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); +} + +/* Zero all elements in a bitmap. */ + +void +sbitmap_zero (bmap) + sbitmap bmap; +{ + bzero ((char *) bmap->elms, bmap->bytes); +} + +/* Set to ones all elements in a bitmap. */ + +void +sbitmap_ones (bmap) + sbitmap bmap; +{ + memset (bmap->elms, -1, bmap->bytes); +} + +/* Zero a vector of N_VECS bitmaps. */ + +void +sbitmap_vector_zero (bmap, n_vecs) + sbitmap *bmap; + int n_vecs; +{ + int i; + + for (i = 0; i < n_vecs; i++) + sbitmap_zero (bmap[i]); +} + +/* Set to ones a vector of N_VECS bitmaps. */ + +void +sbitmap_vector_ones (bmap, n_vecs) + sbitmap *bmap; + int n_vecs; +{ + int i; + + for (i = 0; i < n_vecs; i++) + sbitmap_ones (bmap[i]); +} + +/* Set DST to be A union (B - C). + DST = A | (B & ~C). + Return non-zero if any change is made. */ + +int +sbitmap_union_of_diff (dst, a, b, c) + sbitmap dst, a, b, c; +{ + int i,changed; + sbitmap_ptr dstp, ap, bp, cp; + + changed = 0; + dstp = dst->elms; + ap = a->elms; + bp = b->elms; + cp = c->elms; + for (i = 0; i < dst->size; i++) + { + SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp); + if (*dstp != tmp) + changed = 1; + *dstp = tmp; + dstp++; ap++; bp++; cp++; + } + return changed; +} + +/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ + +void +sbitmap_not (dst, src) + sbitmap dst, src; +{ + int i; + sbitmap_ptr dstp, ap; + + dstp = dst->elms; + ap = src->elms; + for (i = 0; i < dst->size; i++) + { + SBITMAP_ELT_TYPE tmp = ~(*ap); + *dstp = tmp; + dstp++; ap++; + } +} + +/* 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). */ + +void +sbitmap_difference (dst, a, b) + sbitmap dst, a, b; +{ + int i; + sbitmap_ptr dstp, ap, bp; + + dstp = dst->elms; + ap = a->elms; + bp = b->elms; + for (i = 0; i < dst->size; i++) + *dstp++ = *ap++ & (~*bp++); +} + +/* 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; + sbitmap_ptr dstp, ap, bp; + + changed = 0; + dstp = dst->elms; + ap = a->elms; + bp = b->elms; + for (i = 0; i < dst->size; i++) + { + SBITMAP_ELT_TYPE tmp = *ap & *bp; + if (*dstp != tmp) + changed = 1; + *dstp = tmp; + dstp++; ap++; bp++; + } + return changed; +} +/* Set DST to be (A or B)). + Return non-zero if any change is made. */ + +int +sbitmap_a_or_b (dst, a, b) + sbitmap dst, a, b; +{ + int i,changed; + sbitmap_ptr dstp, ap, bp; + + changed = 0; + dstp = dst->elms; + ap = a->elms; + bp = b->elms; + for (i = 0; i < dst->size; i++) + { + SBITMAP_ELT_TYPE tmp = *ap | *bp; + if (*dstp != tmp) + changed = 1; + *dstp = tmp; + dstp++; ap++; bp++; + } + return changed; +} + +/* Set DST to be (A or (B and C)). + Return non-zero if any change is made. */ + +int +sbitmap_a_or_b_and_c (dst, a, b, c) + sbitmap dst, a, b, c; +{ + int i,changed; + sbitmap_ptr dstp, ap, bp, cp; + + changed = 0; + dstp = dst->elms; + ap = a->elms; + bp = b->elms; + cp = c->elms; + for (i = 0; i < dst->size; i++) + { + SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp); + if (*dstp != tmp) + changed = 1; + *dstp = tmp; + dstp++; ap++; bp++; cp++; + } + return changed; +} + +/* Set DST to be (A ann (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; + sbitmap_ptr dstp, ap, bp, cp; + + changed = 0; + dstp = dst->elms; + ap = a->elms; + bp = b->elms; + cp = c->elms; + for (i = 0; i < dst->size; i++) + { + SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp); + if (*dstp != tmp) + changed = 1; + *dstp = tmp; + dstp++; ap++; bp++; cp++; + } + return changed; +} + +/* Set the bitmap DST to the intersection of SRC of all predecessors or + successors of block number BB (PRED_SUCC says which). */ + +void +sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ) + sbitmap dst; + sbitmap *src; + int bb; + int_list_ptr *pred_succ; +{ + int_list_ptr ps; + int ps_bb; + int set_size = dst->size; + + ps = pred_succ[bb]; + + /* It is possible that there are no predecessors(/successors). + This can happen for example in unreachable code. */ + + if (ps == NULL) + { + /* 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; + } + + /* 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. */ + break; + } + if (ps == NULL) + return; + + /* Now do the remaining predecessors/successors. */ + + for (ps = ps->next; ps != NULL; ps = ps->next) + { + int i; + sbitmap_ptr p,r; + + ps_bb = INT_LIST_VAL (ps); + if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) + continue; + + p = src[ps_bb]->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. */ + +void +sbitmap_union_of_predsucc (dst, src, bb, pred_succ) + sbitmap dst; + sbitmap *src; + int bb; + int_list_ptr *pred_succ; +{ + int_list_ptr ps; + int ps_bb; + int set_size = dst->size; + + ps = pred_succ[bb]; + + /* It is possible that there are no predecessors(/successors). + This can happen for example in unreachable code. */ + + if (ps == NULL) + { + /* 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; + } + + /* 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. */ + break; + } + if (ps == NULL) + return; + + /* Now do the remaining predecessors/successors. */ + + for (ps = ps->next; ps != NULL; ps = ps->next) + { + int i; + sbitmap_ptr p,r; + + ps_bb = INT_LIST_VAL (ps); + if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK) + continue; + + p = src[ps_bb]->elms; + r = dst->elms; + + for (i = 0; i < set_size; i++) + *r++ |= *p++; + } +} + +void +dump_sbitmap (file, bmap) + FILE *file; + sbitmap bmap; +{ + int i,j,n; + int set_size = bmap->size; + 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); + } + } + fprintf (file, "\n"); +} + +void +dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) + FILE *file; + char *title, *subtitle; + sbitmap *bmaps; + int n_maps; +{ + int bb; + + fprintf (file, "%s\n", title); + for (bb = 0; bb < n_maps; bb++) + { + fprintf (file, "%s %d\n", subtitle, bb); + dump_sbitmap (file, bmaps[bb]); + } + fprintf (file, "\n"); +} diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h new file mode 100644 index 00000000000..350142d809d --- /dev/null +++ b/gcc/sbitmap.h @@ -0,0 +1,122 @@ +/* Simple bitmaps. + Copyright (C) 1999 Free Software Foundation, Inc. + +This file is part of GNU CC. + +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. + +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. + +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. */ + +/* It's not clear yet whether using bitmap.[ch] will be a win. + It should be straightforward to convert so for now we keep things simple + while more important issues are dealt with. */ + +#define SBITMAP_ELT_BITS HOST_BITS_PER_WIDE_INT +#define SBITMAP_ELT_TYPE unsigned HOST_WIDE_INT + +typedef struct simple_bitmap_def { + /* Number of bits. */ + int n_bits; + /* Size in elements. */ + int size; + /* Size in bytes. */ + int bytes; + /* The elements. */ + SBITMAP_ELT_TYPE elms[1]; +} *sbitmap; + +typedef SBITMAP_ELT_TYPE *sbitmap_ptr; + +/* Return the set size needed for N elements. */ +#define SBITMAP_SET_SIZE(n) (((n) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) + +/* set bit number bitno in the bitmap */ +#define SET_BIT(bitmap, bitno) \ + ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] \ + |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS) + +/* test if bit number bitno in the bitmap is set */ +#define TEST_BIT(bitmap, bitno) \ +((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] >> (bitno) % SBITMAP_ELT_BITS & 1) + +/* reset bit number bitno in the bitmap */ +#define RESET_BIT(bitmap, bitno) \ + ((bitmap)->elms [(bitno) / SBITMAP_ELT_BITS] \ + &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS)) + +/* Loop over all elements of SBITSET, starting with MIN. */ +#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \ +do { \ + unsigned int bit_num_ = (MIN) % (unsigned) SBITMAP_ELT_BITS; \ + unsigned int word_num_ = (MIN) / (unsigned) SBITMAP_ELT_BITS; \ + unsigned int size_ = (SBITMAP)->size; \ + SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \ + \ + while (word_num_ < size_) \ + { \ + SBITMAP_ELT_TYPE word_ = ptr_[word_num_]; \ + if (word_ != 0) \ + { \ + for (; bit_num_ < SBITMAP_ELT_BITS; ++bit_num_) \ + { \ + SBITMAP_ELT_TYPE mask_ = (SBITMAP_ELT_TYPE)1 << bit_num_; \ + if ((word_ & mask_) != 0) \ + { \ + word_ &= ~mask_; \ + (N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \ + CODE; \ + if (word_ == 0) \ + break; \ + } \ + } \ + } \ + bit_num_ = 0; \ + word_num_++; \ + } \ +} while (0) + +#define sbitmap_free(map) free(map) +#define sbitmap_vector_free(vec) free(vec) + +extern void dump_sbitmap PROTO ((FILE *, sbitmap)); +extern void dump_sbitmap_vector PROTO ((FILE *, char *, char *, + sbitmap *, int)); + +extern sbitmap sbitmap_alloc PROTO ((int)); +extern sbitmap *sbitmap_vector_alloc PROTO ((int, int)); + +extern void sbitmap_copy PROTO ((sbitmap, sbitmap)); +extern void sbitmap_zero PROTO ((sbitmap)); +extern void sbitmap_ones PROTO ((sbitmap)); +extern void sbitmap_vector_zero PROTO ((sbitmap *, int)); +extern void sbitmap_vector_ones PROTO ((sbitmap *, int)); + +extern int sbitmap_union_of_diff PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); +extern void sbitmap_difference PROTO ((sbitmap, sbitmap, sbitmap)); +extern void sbitmap_not PROTO ((sbitmap, sbitmap)); +extern int sbitmap_a_or_b_and_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); +extern int sbitmap_a_and_b_or_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap)); +extern int sbitmap_a_and_b PROTO ((sbitmap, sbitmap, sbitmap)); +extern int sbitmap_a_or_b PROTO ((sbitmap, sbitmap, sbitmap)); + +struct int_list; +extern void sbitmap_intersect_of_predsucc PROTO ((sbitmap, sbitmap *, + int, struct int_list **)); +#define sbitmap_intersect_of_predecessors sbitmap_intersect_of_predsucc +#define sbitmap_intersect_of_successors sbitmap_intersect_of_predsucc + +extern void sbitmap_union_of_predsucc PROTO ((sbitmap, sbitmap *, int, + struct int_list **)); +#define sbitmap_union_of_predecessors sbitmap_union_of_predsucc +#define sbitmap_union_of_successors sbitmap_union_of_predsucc |