X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fbitmap.c;h=b735d1409d0b276069e077ac6e84d1f11eb7f7fb;hb=16cf5b3d55e6bf8328653afb0eadf8c0e023f532;hp=56a5fd7b3b9ad5a6ca731141a01a9e2224437629;hpb=d946ea19691c3dbff945842d584b6a94c5190d92;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/bitmap.c b/gcc/bitmap.c index 56a5fd7b3b9..b735d1409d0 100644 --- a/gcc/bitmap.c +++ b/gcc/bitmap.c @@ -1,22 +1,22 @@ /* Functions to support general ended bitmaps. - Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc. + Copyright (C) 1997, 1998, 1999, 2000, 2001 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" @@ -38,8 +38,8 @@ static int bitmap_obstack_init = FALSE; #endif /* Global data */ -bitmap_element bitmap_zero; /* An element of all zero bits. */ -bitmap_element *bitmap_free; /* Freelist of bitmap elements. */ +bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ +static bitmap_element *bitmap_free; /* Freelist of bitmap elements. */ static void bitmap_element_free PARAMS ((bitmap, bitmap_element *)); static bitmap_element *bitmap_element_allocate PARAMS ((void)); @@ -47,7 +47,8 @@ static int bitmap_element_zerop PARAMS ((bitmap_element *)); static void bitmap_element_link PARAMS ((bitmap, bitmap_element *)); static bitmap_element *bitmap_find_bit PARAMS ((bitmap, unsigned int)); -/* Free a bitmap element */ +/* Free a bitmap element. Since these are allocated off the + bitmap_obstack, "free" actually means "put onto the freelist". */ static INLINE void bitmap_element_free (head, elt) @@ -69,7 +70,11 @@ bitmap_element_free (head, elt) /* Since the first thing we try is to insert before current, make current the next entry in preference to the previous. */ if (head->current == elt) - head->current = next != 0 ? next : prev; + { + head->current = next != 0 ? next : prev; + if (head->current) + head->indx = head->current->indx; + } elt->next = bitmap_free; bitmap_free = elt; @@ -81,9 +86,6 @@ static INLINE bitmap_element * bitmap_element_allocate () { bitmap_element *element; -#if BITMAP_ELEMENT_WORDS != 2 - int i; -#endif if (bitmap_free != 0) { @@ -125,16 +127,24 @@ bitmap_element_allocate () sizeof (bitmap_element)); } -#if BITMAP_ELEMENT_WORDS == 2 - element->bits[0] = element->bits[1] = 0; -#else - for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) - element->bits[i] = 0; -#endif + memset (element->bits, 0, sizeof (element->bits)); return element; } +/* Release any memory allocated by bitmaps. */ + +void +bitmap_release_memory () +{ + bitmap_free = 0; + if (bitmap_obstack_init) + { + bitmap_obstack_init = FALSE; + obstack_free (&bitmap_obstack, NULL); + } +} + /* Return nonzero if all bits in an element are zero. */ static INLINE int @@ -229,7 +239,7 @@ bitmap_clear (head) head->first = head->current = 0; } -/* Copy a bitmap to another bitmap */ +/* Copy a bitmap to another bitmap. */ void bitmap_copy (to, from) @@ -337,7 +347,6 @@ bitmap_clear_bit (head, bit) } } - /* Set a single bit in a bitmap. */ void @@ -361,7 +370,7 @@ bitmap_set_bit (head, bit) else ptr->bits[word_num] |= bit_val; } - + /* Return whether a bit is set within a bitmap. */ int @@ -384,6 +393,112 @@ bitmap_bit_p (head, bit) return (ptr->bits[word_num] >> bit_num) & 1; } +/* Return the bit number of the first set bit in the bitmap, or -1 + if the bitmap is empty. */ + +int +bitmap_first_set_bit (a) + bitmap a; +{ + bitmap_element *ptr = a->first; + unsigned HOST_WIDE_INT word; + unsigned word_num, bit_num; + + if (ptr == NULL) + return -1; + +#if BITMAP_ELEMENT_WORDS == 2 + word_num = 0, word = ptr->bits[0]; + if (word == 0) + word_num = 1, word = ptr->bits[1]; +#else + for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num) + if ((word = ptr->bits[word_num]) != 0) + break; +#endif + + /* Binary search for the first set bit. */ + /* ??? It'd be nice to know if ffs or ffsl was available. */ + + bit_num = 0; + word = word & -word; + +#if HOST_BITS_PER_WIDE_INT > 64 + #error "Fill out the table." +#endif +#if HOST_BITS_PER_WIDE_INT > 32 + if ((word & 0xffffffff) == 0) + word >>= 32, bit_num += 32; +#endif + if ((word & 0xffff) == 0) + word >>= 16, bit_num += 16; + if ((word & 0xff) == 0) + word >>= 8, bit_num += 8; + if (word & 0xf0) + bit_num += 4; + if (word & 0xcc) + bit_num += 2; + if (word & 0xaa) + bit_num += 1; + + return (ptr->indx * BITMAP_ELEMENT_ALL_BITS + + word_num * HOST_BITS_PER_WIDE_INT + + bit_num); +} + +/* Return the bit number of the last set bit in the bitmap, or -1 + if the bitmap is empty. */ + +int +bitmap_last_set_bit (a) + bitmap a; +{ + bitmap_element *ptr = a->first; + unsigned HOST_WIDE_INT word; + unsigned word_num, bit_num; + + if (ptr == NULL) + return -1; + + while (ptr->next != NULL) + ptr = ptr->next; + +#if BITMAP_ELEMENT_WORDS == 2 + word_num = 1, word = ptr->bits[1]; + if (word == 0) + word_num = 0, word = ptr->bits[0]; +#else + for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; ) + if ((word = ptr->bits[word_num]) != 0) + break; +#endif + + /* Binary search for the last set bit. */ + + bit_num = 0; +#if HOST_BITS_PER_WIDE_INT > 64 + #error "Fill out the table." +#endif +#if HOST_BITS_PER_WIDE_INT > 32 + if (word & ~ (unsigned HOST_WIDE_INT) 0xffffffff) + word >>= 32, bit_num += 32; +#endif + if (word & 0xffff0000) + word >>= 16, bit_num += 16; + if (word & 0xff00) + word >>= 8, bit_num += 8; + if (word & 0xf0) + word >>= 4, bit_num += 4; + if (word & 0xc) + word >>= 2, bit_num += 2; + if (word & 0x2) + bit_num += 1; + + return (ptr->indx * BITMAP_ELEMENT_ALL_BITS + + word_num * HOST_BITS_PER_WIDE_INT + + bit_num); +} + /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using a specific bit manipulation. Return true if TO changes. */ @@ -458,21 +573,21 @@ bitmap_operation (to, from1, from2, operation) { indx = indx1; from1_tmp = from1_ptr; - from2_tmp = &bitmap_zero; + from2_tmp = &bitmap_zero_bits; from1_ptr = from1_ptr->next; indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX; } else { indx = indx2; - from1_tmp = &bitmap_zero; + from1_tmp = &bitmap_zero_bits; from2_tmp = from2_ptr; from2_ptr = from2_ptr->next; indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX; } /* Find the appropriate element from TO. Begin by discarding - elements that we've skipped. */ + elements that we've skipped. */ while (to_ptr && to_ptr->indx < indx) { changed = 1; @@ -507,7 +622,9 @@ bitmap_operation (to, from1, from2, operation) case BITMAP_IOR: DOIT (|); break; - + case BITMAP_IOR_COMPL: + DOIT (|~); + break; case BITMAP_XOR: DOIT (^); break; @@ -558,7 +675,7 @@ bitmap_equal_p (a, b) } /* Or into bitmap TO bitmap FROM1 and'ed with the complement of - bitmap FROM2. */ + bitmap FROM2. */ void bitmap_ior_and_compl (to, from1, from2) @@ -574,6 +691,25 @@ bitmap_ior_and_compl (to, from1, from2) bitmap_operation (to, to, &tmp, BITMAP_IOR); bitmap_clear (&tmp); } + +int +bitmap_union_of_diff (dst, a, b, c) + bitmap dst; + bitmap a; + bitmap b; + bitmap c; +{ + bitmap_head tmp; + int changed; + + tmp.first = tmp.current = 0; + + bitmap_operation (&tmp, b, c, BITMAP_AND_COMPL); + changed = bitmap_operation (dst, &tmp, a, BITMAP_IOR); + bitmap_clear (&tmp); + + return changed; +} /* Initialize a bitmap header. */ @@ -631,7 +767,7 @@ debug_bitmap_file (file, head) fprintf (file, " }\n"); } } - + /* Function to be called from the debugger to print the contents of a bitmap. */ @@ -641,7 +777,7 @@ debug_bitmap (head) { debug_bitmap_file (stdout, head); } - + /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, it does not print anything but the bits. */ @@ -663,16 +799,3 @@ bitmap_print (file, head, prefix, suffix) }); fputs (suffix, file); } - -/* Release any memory allocated by bitmaps. */ - -void -bitmap_release_memory () -{ - bitmap_free = 0; - if (bitmap_obstack_init) - { - bitmap_obstack_init = FALSE; - obstack_free (&bitmap_obstack, NULL); - } -}