diff options
| -rw-r--r-- | gcc/ChangeLog | 20 | ||||
| -rw-r--r-- | gcc/Makefile.in | 3 | ||||
| -rw-r--r-- | gcc/ebitmap.c | 1019 | ||||
| -rw-r--r-- | gcc/ebitmap.h | 175 | ||||
| -rw-r--r-- | gcc/sbitmap.c | 128 | ||||
| -rw-r--r-- | gcc/sbitmap.h | 35 |
6 files changed, 34 insertions, 1346 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7d963a8..2865cee 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,4 +1,22 @@ -2012-10-31 Lawrence Crowl <crowl@google.com> +2012-11-01 Lawrence Crowl <crowl@google.com> + + * ebitmap.h: Remove unused. + * ebitmap.c: Remove unused. + * Makefile.in: Remove ebitmap.h and ebitmap.c. + * sbitmap.h (SBITMAP_SIZE_BYTES): Move to source file. + (SET_BIT_WITH_POPCOUNT): Remove unused. + (RESET_BIT_WITH_POPCOUNT): Remove unused. + (bitmap_copy_n): Remove unused. + (bitmap_range_empty_p): Remove unused. + (sbitmap_popcount): Remove unused. + (sbitmap_verify_popcount): Make private to source file. + * sbitmap.c (SBITMAP_SIZE_BYTES): Move here from header. + (bitmap_copy_n): Remove unused. + (bitmap_range_empty_p): Remove unused. + (sbitmap_popcount): Remove unused. + (sbitmap_verify_popcount): Make private to source file. + +2012-11-01 Lawrence Crowl <crowl@google.com> * sbitmap.h (sbitmap_iter_init): Rename bmp_iter_set_init and add unused parameter to match bitmap iterator. Update callers. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 3a8ffbe..9aea03d 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -942,7 +942,6 @@ REAL_H = real.h $(MACHMODE_H) IRA_INT_H = ira.h ira-int.h $(CFGLOOP_H) alloc-pool.h LRA_INT_H = lra.h $(BITMAP_H) $(RECOG_H) $(INSN_ATTR_H) insn-codes.h lra-int.h DBGCNT_H = dbgcnt.h dbgcnt.def -EBITMAP_H = ebitmap.h sbitmap.h LTO_STREAMER_H = lto-streamer.h $(LINKER_PLUGIN_API_H) $(TARGET_H) \ $(CGRAPH_H) $(VEC_H) vecprim.h $(TREE_H) $(GIMPLE_H) \ $(GCOV_IO_H) $(DIAGNOSTIC_H) alloc-pool.h @@ -1200,7 +1199,6 @@ OBJS = \ dwarf2asm.o \ dwarf2cfi.o \ dwarf2out.o \ - ebitmap.o \ emit-rtl.o \ et-forest.o \ except.o \ @@ -1833,7 +1831,6 @@ graph.o: graph.c $(SYSTEM_H) coretypes.h $(TM_H) toplev.h $(DIAGNOSTIC_CORE_H) $ $(CONFIG_H) $(EMIT_RTL_H) sbitmap.o: sbitmap.c sbitmap.h $(CONFIG_H) $(SYSTEM_H) coretypes.h -ebitmap.o: ebitmap.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(EBITMAP_H) sparseset.o: sparseset.c $(SYSTEM_H) sparseset.h $(CONFIG_H) AR_LIBS = @COLLECT2_LIBS@ diff --git a/gcc/ebitmap.c b/gcc/ebitmap.c deleted file mode 100644 index 3349532..0000000 --- a/gcc/ebitmap.c +++ /dev/null @@ -1,1019 +0,0 @@ -/* Sparse array-based bitmaps. - Copyright (C) 2007-2012 Free Software Foundation, Inc. - Contributed by Daniel Berlin <dberlin@dberlin.org> - -This file is part of GCC. - -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 3, or (at your option) any later -version. - -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 GCC; see the file COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "ebitmap.h" - -/* The ebitmap data structure is a sparse bitmap structure that works - by having two pieces: - 1. An array of all nonzero words in the structures, organized as - an array of HOST_WIDE_INT's. - 2. A non-sparse bitmap saying which bitmap words are present in the - array. - - As a consequence of this representation, testing whether a bit - exists in the bitmap is faster than linked-list bitmaps. For bits - in words that are all zero, the time to test is O(1). For bits in - words that exist, it requires O(n/sizeof(word)) time to perform the - test (ignoring the one element cache). It also has much better - locality than linked-list bitmaps. - - To test whether a bit exists, we do the following: - 1. Test whether the word the bit would appear in exists in the - bitmap (O(1) check of the mask). If not, fail. - - 2. Population count the mask up to the word containing the bit, to - find the place in the array the word would be (popcount is cached, - but this is just as slow as the linked-list bitmap) - 3. Test the word to see if the bit exists. - - Just like linked-list bitmaps, we cache the last element that has - been tested in order to speed up common access patterns. - - Most of the other speedups are simply due to better locality of the - single contiguous array. - - As would be expected in a structure like this, insertion into an - empty word in the middle requires moving bits to make room for the - new word. As most operations that perform sets perform them in - order, this is rarely a problem. We also take advantage of the - same element cache to make repeated sets to the same word O(1). - - Operations on the entire bitmap are also more efficient than linked - list bitmaps, as they are all operating on contiguous memory, and - can be easily vectorized. They are all O(number of words) + - O(number of bits that may end up in the destination), as the - appropriate operation is first performed on the word mask, and then - only those elements that may generate results are touched. - - Memory wise, the ebitmap starts out using less memory than the - linked-list bitmap, but its size in memory is technically bounded - by ((index of the highest bit set) / (size of a word) + (index of - the highest bit set) / ((size of a word) * (size of a word))) This - is because the mask is non-sparse. The mask could be transformed - into a sparse bitmap at the cost of making bit testing - *theoretically* slower (real world numbers have not been computed - yet as to whether it matters or not). */ - -/* #define EBITMAP_DEBUGGING */ - -/* Find the last set bit in ebitmap MAP. */ - -int -bitmap_last_set_bit (ebitmap map) -{ - unsigned int i = 0; - ebitmap_iterator ebi; - bool foundbit = false; - - /* This is not the fastest way to do this, we could simply look for - the popcount, and start there, but this function is not used - anywhere speed critical. */ - EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi) - { - foundbit = true; - } - - - if (foundbit) - return i; - return -1; -} - -/* Grow or shrink the internal word array for MAP to NEWSIZE - elements. */ - -static inline void -ebitmap_array_grow (ebitmap map, unsigned int newsize) -{ - if (newsize <= map->n_elts) - { - map->n_elts = newsize; - return; - } - - newsize += newsize / 4; - - map->n_elts = newsize; - map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize); -} - -/* Grow the internal word array for MAP so it is at least SIZE - elements. Will not shrink the array if it is already big - enough. */ - -static inline void -ebitmap_array_maybe_grow (ebitmap map, unsigned int size) -{ - if (size >= map->n_elts) - ebitmap_array_grow (map, size + 1); -} - -/* Retrieve the IDX'th element from the word array for MAP. */ - -static inline EBITMAP_ELT_TYPE -ebitmap_array_get (ebitmap map, unsigned int idx) -{ - gcc_assert (idx < map->n_elts); - return map->elts[idx]; -} - -/* Retrieve a pointer to the IDX'th element from the word array for - MAP. If the element index is greater than the size of the array, - the array will be grown to the correct size. */ - -static inline EBITMAP_ELT_TYPE * -ebitmap_array_grow_get (ebitmap map, unsigned int idx) -{ - if (idx >= map->n_elts) - ebitmap_array_grow (map, idx + 1); - return &map->elts[idx]; -} - -/* Initialize the internal word array for MAP, so that it is SIZE - elements. */ - -static inline void -ebitmap_array_init (ebitmap map, unsigned int size) -{ - if (size > 0) - { - map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size); - map->n_elts = size; - } - else - { - map->n_elts = 0; - map->elts = NULL; - } -} - -/* Free the internal word array for MAP. */ - -static inline void -ebitmap_array_clear (ebitmap map) -{ - if (map->elts) - { - free (map->elts); - map->elts = NULL; - } - map->n_elts = 0; -} - -/* Clear ebitmap MAP. */ - -void -bitmap_clear (ebitmap map) -{ - ebitmap_array_clear (map); - bitmap_clear (map->wordmask); - map->wordmask = sbitmap_resize (map->wordmask, 1, 0); - map->numwords = 0; - map->cache = NULL; - map->cacheindex = 0; -} - -/* Allocate an ebitmap with enough room for SIZE bits to start out. */ - -ebitmap -ebitmap_alloc (unsigned int size) -{ - ebitmap ret = XNEW (struct ebitmap_def); - if (size == 0) - size = EBITMAP_ELT_BITS; - ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS); - ret->wordmask = sbitmap_alloc_with_popcount (size); - bitmap_clear (ret->wordmask); - ret->numwords = 0; - ret->cache = NULL; - ret->cacheindex = 0; - - return ret; -} - -/* Clear BIT from ebitmap MAP. */ - -void -bitmap_clear_bit (ebitmap map, unsigned int bit) -{ - unsigned int wordindex = bit / EBITMAP_ELT_BITS; - unsigned int eltwordindex = 0; - unsigned int bitindex, shift; - bool have_eltwordindex = false; - EBITMAP_ELT_TYPE *elt_ptr; - - /* If the bit can't exist in our bitmap, just return. */ - if (map->numwords == 0) - return; - - if (wordindex >= map->wordmask->n_bits - || !bitmap_bit_p (map->wordmask, wordindex)) - return; - - if (map->cache != NULL && map->cacheindex == wordindex) - elt_ptr = map->cache; - else - { - eltwordindex = sbitmap_popcount (map->wordmask, wordindex); - elt_ptr = &map->elts[eltwordindex]; - have_eltwordindex = true; - } - - bitindex = bit % EBITMAP_ELT_BITS; - shift = bitindex; - - *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift); - - /* Clear out the empty words. */ - if (*(elt_ptr) == 0) - { - if (!have_eltwordindex) - eltwordindex = sbitmap_popcount (map->wordmask, wordindex); - - if (map->cache != NULL) - { - if (map->cacheindex == wordindex) - map->cache = NULL; - else if (map->cacheindex > wordindex) - map->cache = map->cache - 1; - } - - bitmap_clear_bit_with_popcount (map->wordmask, wordindex); - - memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1], - sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex)); - map->numwords--; - } -} - -/* Set BIT in ebitmap MAP. */ - -void -bitmap_set_bit (ebitmap map, unsigned int bit) -{ - unsigned int wordindex = bit / EBITMAP_ELT_BITS; - unsigned int eltwordindex; - unsigned int bitindex = bit % EBITMAP_ELT_BITS; - - /* If we have this element cached, just set the bit in it. */ - if (map->cache && map->cacheindex == wordindex) - { - (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex; - return; - } - - /* Resize the wordmask if necessary. */ - if (wordindex >= map->wordmask->n_bits) - map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0); - - /* Allocate a new word in the array and move whatever is in it's - place, if necessary. */ - if (!bitmap_bit_p (map->wordmask, wordindex)) - { - unsigned long count; - unsigned int i; - - bitmap_set_bit_with_popcount (map->wordmask, wordindex); - count = sbitmap_popcount (map->wordmask, wordindex); - gcc_assert (count <= map->numwords); - - for (i = map->numwords; i > count; i--) - { - EBITMAP_ELT_TYPE *newelt; - newelt = ebitmap_array_grow_get (map, i); - *newelt = ebitmap_array_get (map, i - 1); - } - map->numwords++; - eltwordindex = count; - ebitmap_array_maybe_grow (map, eltwordindex); - map->elts[eltwordindex] = 0; - } - else - { - eltwordindex = sbitmap_popcount (map->wordmask, wordindex); - } - - /* Set the actual bit. */ - bitindex = bit % EBITMAP_ELT_BITS; - - map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex; - map->cache = &map->elts[eltwordindex]; - map->cacheindex = wordindex; -} - - -/* Return true if MAP contains BIT. */ - -bool -bitmap_bit_p (ebitmap map, unsigned int bit) -{ - unsigned int wordindex = bit / EBITMAP_ELT_BITS; - unsigned int bitindex= bit % EBITMAP_ELT_BITS; - - /* Trivial empty ebitmap case. */ - if (map->numwords == 0) - return false; - - if (map->cache && map->cacheindex == wordindex) - return ((*map->cache) >> bitindex) & 1; - - /* If the wordindex is greater than the size of the wordmask, *or* - it's not set in the wordmask, this bit can't exist in our - ebitmap. */ - if (wordindex >= map->wordmask->n_bits - || !bitmap_bit_p (map->wordmask, wordindex)) - return false; - - /* Find the bit and test it. */ - map->cacheindex = wordindex; - wordindex = sbitmap_popcount (map->wordmask, wordindex); - map->cache = &map->elts[wordindex]; - - return (map->elts[wordindex] >> bitindex) & 1; -} - -/* Copy ebitmap SRC to DST. */ - -void -bitmap_copy (ebitmap dst, ebitmap src) -{ - /* Blow away any existing wordmask, and copy the new one. */ - sbitmap_free (dst->wordmask); - dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits); - bitmap_copy (dst->wordmask, src->wordmask); - - /* Make sure our destination array is big enough, and then copy the - actual words. */ - ebitmap_array_grow (dst, src->numwords); - memcpy (dst->elts, src->elts, - src->numwords * sizeof (EBITMAP_ELT_TYPE)); - dst->numwords = src->numwords; - dst->cache = NULL; -} - -/* Dump ebitmap BMAP to FILE. */ - -void -dump_bitmap (FILE *file, ebitmap bmap) -{ - unsigned int pos; - unsigned int i; - int res; - unsigned int size; - - res = bitmap_last_set_bit (bmap->wordmask); - if (res == -1) - size = 0; - else - size = (res + 1) * EBITMAP_ELT_BITS; - - fprintf (file, "n_words = %d, set = {", bmap->numwords); - - for (pos = 30, i = 0; i < size; i++) - if (bitmap_bit_p (bmap, i)) - { - if (pos > 70) - { - fprintf (file, "\n "); - pos = 0; - } - - pos += fprintf (file, "%d ", i); - } - - fprintf (file, "}\n"); -} - -/* Dump ebitmap BMAP to stderr. */ - -DEBUG_FUNCTION void -debug_bitmap (ebitmap bmap) -{ - dump_bitmap (stderr, bmap); -} - -/* Perform the operation DST &= SRC. */ - -void -bitmap_and_into (ebitmap dst, ebitmap src) -{ - sbitmap_iterator sbi; - unsigned int i; - unsigned int neweltindex = 0; - unsigned int dsteltindex = 0; - unsigned int srceltindex = 0; - - gcc_assert (dst != src); - - dst->cache = NULL; - - /* Short circuit the empty bitmap cases. */ - if (src->numwords == 0 || dst->numwords == 0) - { - bitmap_clear (dst); - return; - } - - /* AND the masks, then walk the words that may actually appear in - the result, AND'ing them. */ - bitmap_and (dst->wordmask, dst->wordmask, src->wordmask); - - EXECUTE_IF_SET_IN_BITMAP (dst->wordmask, 0, i, sbi) - { - EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); - tmpword &= ebitmap_array_get (dst, dsteltindex++); - if (tmpword != 0) - { - EBITMAP_ELT_TYPE *dstplace; - dstplace = ebitmap_array_grow_get (dst, neweltindex++); - *dstplace = tmpword; - } - else - bitmap_clear_bit_with_popcount (dst->wordmask, i); - } -#ifdef EBITMAP_DEBUGGING - { - unsigned int i; - - for (i = 0; i < dst->numwords; i++) - gcc_assert (dst->elts[i] != 0); - - sbitmap_verify_popcount (dst->wordmask); - gcc_assert (sbitmap_popcount (dst->wordmask, - dst->wordmask->n_bits) == dst->numwords); - } -#endif - dst->numwords = neweltindex; -} - -/* Perform the operation DST = SRC1 & SRC2. */ - -void -bitmap_and (ebitmap dst, ebitmap src1, ebitmap src2) -{ - sbitmap_iterator sbi; - unsigned int i; - unsigned int neweltindex = 0; - unsigned int src1eltindex = 0; - unsigned int src2eltindex = 0; - - dst->cache = NULL; - if (src1->numwords == 0 || src2->numwords == 0) - { - bitmap_clear (dst); - return; - } - - dst->wordmask - = sbitmap_resize (dst->wordmask, - MIN (src1->wordmask->n_bits, src2->wordmask->n_bits), - 0); - bitmap_and (dst->wordmask, src1->wordmask, src2->wordmask); - - EXECUTE_IF_SET_IN_BITMAP (dst->wordmask, 0, i, sbi) - { - bool src1hasword, src2hasword; - - src1hasword = bitmap_bit_p (src1->wordmask, i); - src2hasword = bitmap_bit_p (src2->wordmask, i); - - if (src1hasword && src2hasword) - { - EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++); - tmpword &= ebitmap_array_get (src2, src2eltindex++); - if (tmpword != 0) - { - EBITMAP_ELT_TYPE *dstplace; - dstplace = ebitmap_array_grow_get (dst, neweltindex++); - *dstplace = tmpword; - } - else - bitmap_clear_bit_with_popcount (dst->wordmask, i); - } - else if (src1hasword) - src1eltindex++; - else - src2eltindex++; - } -#ifdef EBITMAP_DEBUGGING - { - ebitmap_iterator ebi; - unsigned int i; - - for (i = 0; i < dst->numwords; i++) - gcc_assert (dst->elts[i] != 0); - - EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) - if (bitmap_bit_p (src2, i)) - gcc_assert (bitmap_bit_p (dst, i)); - - for (i = 0; i < dst->numwords; i++) - gcc_assert (dst->elts[i] != 0); - - sbitmap_verify_popcount (dst->wordmask); - gcc_assert (sbitmap_popcount (dst->wordmask, - dst->wordmask->n_bits) == dst->numwords); - } -#endif - dst->numwords = neweltindex; -} - -/* Perform the operation DST |= SRC. Return true if any bits in DST - changed. */ - -bool -bitmap_ior_into (ebitmap dst, ebitmap src) -{ - unsigned int dstsize = dst->wordmask->n_bits; - unsigned int srcsize = src->wordmask->n_bits; - sbitmap_iterator sbi; - unsigned int i; - sbitmap tempmask; - unsigned int neweltindex = 0; - unsigned int dsteltindex = 0; - unsigned int srceltindex = 0; - bool changed = false; - EBITMAP_ELT_TYPE *newarray; - unsigned int newarraysize; -#ifdef EBITMAP_DEBUGGING - ebitmap dstcopy = ebitmap_alloc (1); - bitmap_copy (dstcopy, dst); -#endif - - dst->cache = NULL; - if (dst == src) - return false; - - if (dst->numwords == 0 && src->numwords != 0) - { - bitmap_copy (dst, src); - return true; - } - else if (src->numwords == 0) - return false; - - /* We can do without the temp mask if it's faster, but it would mean - touching more words in the actual dense vector. */ - tempmask = sbitmap_alloc (MAX (srcsize, dstsize)); - bitmap_clear (tempmask); - if (srcsize == dstsize) - { - bitmap_ior (tempmask, dst->wordmask, src->wordmask); - } - else - { - dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize), - 0); - if (srcsize >= dstsize) - { - bitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size); - bitmap_ior (tempmask, tempmask, src->wordmask); - } - else - { - bitmap_copy_n (tempmask, src->wordmask, src->wordmask->size); - bitmap_ior (tempmask, tempmask, dst->wordmask); - } - } - newarraysize = src->numwords + dst->numwords; - newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); - - EXECUTE_IF_SET_IN_BITMAP (tempmask, 0, i, sbi) - { - bool dsthasword, srchasword; - - dsthasword = (i < dst->wordmask->n_bits - && bitmap_bit_p (dst->wordmask, i)); - srchasword = (i < src->wordmask->n_bits - && bitmap_bit_p (src->wordmask, i)); - - if (dsthasword && srchasword) - { - EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++); - tmpword |= ebitmap_array_get (dst, dsteltindex); - if (!changed) - changed |= tmpword != ebitmap_array_get (dst, dsteltindex); - dsteltindex++; - newarray[neweltindex++] = tmpword; - } - else if (dsthasword) - { - newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++); - } - else - { - newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++); - gcc_assert (i < dst->wordmask->n_bits); - bitmap_set_bit_with_popcount (dst->wordmask, i); - changed |= true; - } - } - - sbitmap_free (tempmask); - if (changed) - { - dst->numwords = neweltindex; - free (dst->elts); - dst->elts = newarray; - dst->n_elts = newarraysize; - } - else - free (newarray); - -#ifdef EBITMAP_DEBUGGING - { - ebitmap_iterator ebi; - unsigned int i; - - for (i = 0; i < dst->numwords; i++) - gcc_assert (dst->elts[i] != 0); - - EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi) - gcc_assert (bitmap_bit_p (dst, i)); - EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) - gcc_assert (bitmap_bit_p (dst, i)); - - sbitmap_verify_popcount (dst->wordmask); - gcc_assert (changed == !bitmap_equal_p (dst, dstcopy)); - gcc_assert (sbitmap_popcount (dst->wordmask, - dst->wordmask->n_bits) == dst->numwords); - } -#endif - return changed; -} - -/* Perform the operation DST = SRC1 | SRC2. Return true if any bit - in DST has changed. */ - -bool -bitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2) -{ - unsigned int src1size = src1->wordmask->n_bits; - unsigned int src2size = src2->wordmask->n_bits; - sbitmap_iterator sbi; - unsigned int i; - sbitmap tempmask; - unsigned int neweltindex = 0; - unsigned int src1eltindex = 0; - unsigned int src2eltindex = 0; - bool changed = false; - EBITMAP_ELT_TYPE *newarray; - unsigned int newarraysize; -#ifdef EBITMAP_DEBUGGING - ebitmap dstcopy = ebitmap_alloc (1); - bitmap_copy (dstcopy, dst); -#endif - - dst->cache = NULL; - tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size)); - bitmap_clear (tempmask); - if (src1size == src2size) - { - bitmap_ior (tempmask, src1->wordmask, src2->wordmask); - } - else - { - if (src1size >= src2size) - { - bitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size); - bitmap_ior (tempmask, tempmask, src1->wordmask); - } - else - { - bitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size); - bitmap_ior (tempmask, tempmask, src2->wordmask); - } - } - newarraysize = src1->numwords + src2->numwords; - newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); - - EXECUTE_IF_SET_IN_BITMAP (tempmask, 0, i, sbi) - { - bool src1hasword, src2hasword; - EBITMAP_ELT_TYPE tmpword; - src1hasword = (i < src1->wordmask->n_bits - && bitmap_bit_p (src1->wordmask, i)); - src2hasword = (i < src2->wordmask->n_bits - && bitmap_bit_p (src2->wordmask, i)); - - if (src1hasword && src2hasword) - { - tmpword = (ebitmap_array_get (src1, src1eltindex++) - | ebitmap_array_get (src2, src2eltindex++)); - newarray[neweltindex++] = tmpword; - } - else if (src1hasword) - { - tmpword = ebitmap_array_get (src1, src1eltindex++); - newarray [neweltindex++] = tmpword; - } - else - { - tmpword = ebitmap_array_get (src2, src2eltindex++); - newarray [neweltindex++] = tmpword; - } - - if (i >= dst->wordmask->n_bits || !bitmap_bit_p (dst->wordmask, i)) - { - changed = true; - } - else if (!changed) - { - unsigned int count = sbitmap_popcount (dst->wordmask, i); - changed |= ebitmap_array_get (dst, count) != tmpword; - } - } - - if (changed) - { - sbitmap_free (dst->wordmask); - dst->wordmask = tempmask; - dst->numwords = neweltindex; - free (dst->elts); - dst->elts = newarray; - dst->n_elts = newarraysize; - } - else - { - sbitmap_free (tempmask); - free (newarray); - } - -#ifdef EBITMAP_DEBUGGING - { - ebitmap_iterator ebi; - unsigned int i; - - for (i = 0; i < dst->numwords; i++) - gcc_assert (dst->elts[i] != 0); - - EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) - gcc_assert (bitmap_bit_p (dst, i)); - - EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi) - gcc_assert (bitmap_bit_p (dst, i)); - } - sbitmap_verify_popcount (dst->wordmask); - gcc_assert (changed == !bitmap_equal_p (dst, dstcopy)); - gcc_assert (sbitmap_popcount (dst->wordmask, - dst->wordmask->n_bits) == dst->numwords); -#endif - - return changed; -} - -/* Perform the operation DST &= ~SRC. Return true if any bit in DST - has changed. */ - -bool -bitmap_and_compl_into (ebitmap dst, ebitmap src) -{ - bool changed = false; - unsigned int i; - unsigned int neweltindex = 0; - unsigned int dsteltindex = 0; - sbitmap_iterator sbi; -#ifdef EBITMAP_DEBUGGING - ebitmap dstcopy = ebitmap_alloc (1); - bitmap_copy (dstcopy, dst); -#endif - - gcc_assert (dst != src); - dst->cache = NULL; - if (src->numwords == 0) - return false; - - EXECUTE_IF_SET_IN_BITMAP (dst->wordmask, 0, i, sbi) - { - bool srchasword; - - srchasword = (i < src->wordmask->n_bits - && bitmap_bit_p (src->wordmask, i)); - - if (srchasword) - { - unsigned int srccount = sbitmap_popcount (src->wordmask, i); - EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex); - tmpword &= ~(ebitmap_array_get (src, srccount)); - if (!changed) - changed |= ebitmap_array_get (dst, dsteltindex) != tmpword; - dsteltindex++; - if (tmpword != 0) - { - EBITMAP_ELT_TYPE *dstplace; - dstplace = ebitmap_array_grow_get (dst, neweltindex++); - *dstplace = tmpword; - } - else - bitmap_clear_bit_with_popcount (dst->wordmask, i); - } - else - { - dsteltindex++; - neweltindex++; - } - } -#ifdef EBITMAP_DEBUGGING - { - unsigned int i; - ebitmap_iterator ebi; - - EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi) - { - if (!bitmap_bit_p (src, i)) - gcc_assert (bitmap_bit_p (dst, i)); - } - - for (i = 0; i < dst->numwords; i++) - gcc_assert (dst->elts[i] != 0); - - gcc_assert (sbitmap_popcount (dst->wordmask, - dst->wordmask->n_bits) == neweltindex); - sbitmap_verify_popcount (dst->wordmask); - gcc_assert (changed == !bitmap_equal_p (dst, dstcopy)); - gcc_assert (sbitmap_popcount (dst->wordmask, - dst->wordmask->n_bits) == dst->numwords); - } -#endif - dst->numwords = neweltindex; - /* sbitmap_popcount (dst->wordmask, -1); */ - - return changed; -} - -/* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit - in DST has changed. */ - -bool -bitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2) -{ - unsigned int src1size = src1->wordmask->n_bits; - sbitmap_iterator sbi; - unsigned int i; - sbitmap tempmask; - unsigned int neweltindex = 0; - unsigned int src1eltindex = 0; - bool changed = false; - EBITMAP_ELT_TYPE *newarray; - unsigned int newarraysize; - - /* XXX: Optimize like the into version. */ - dst->cache = NULL; - tempmask = sbitmap_alloc_with_popcount (src1size); - bitmap_clear (tempmask); - bitmap_copy (tempmask, src1->wordmask); - - newarraysize = src1->numwords; - newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); - - EXECUTE_IF_SET_IN_BITMAP (src1->wordmask, 0, i, sbi) - { - bool src2hasword; - EBITMAP_ELT_TYPE tmpword; - - src2hasword = (i < src2->wordmask->n_bits - && bitmap_bit_p (src2->wordmask, i)); - - if (src2hasword) - { - unsigned int src2count = sbitmap_popcount (src2->wordmask, i); - tmpword = ebitmap_array_get (src1, src1eltindex++) - & ~(ebitmap_array_get (src2, src2count)); - if (tmpword) - { - newarray[neweltindex++] = tmpword; - } - else - bitmap_clear_bit_with_popcount (tempmask, i); - - } - else - { - tmpword = ebitmap_array_get (src1, src1eltindex++); - gcc_assert (tmpword != 0); - newarray[neweltindex++] = tmpword; - } - - if (i >= dst->wordmask->n_bits || !bitmap_bit_p (dst->wordmask, i)) - { - changed = true; - } - else if (!changed) - { - unsigned int count = sbitmap_popcount (dst->wordmask, i); - changed |= ebitmap_array_get (dst, count) != tmpword; - } - } - if (changed) - { - sbitmap_free (dst->wordmask); - dst->wordmask = tempmask; - dst->numwords = neweltindex; - free (dst->elts); - dst->elts = newarray; - dst->n_elts = newarraysize; - } - else - { - free (tempmask); - free (newarray); - } -#ifdef EBITMAP_DEBUGGING - { - unsigned int i; - ebitmap_iterator ebi; - - EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi) - { - if (!bitmap_bit_p (src2, i)) - gcc_assert (bitmap_bit_p (dst, i)); - } - for (i = 0; i < dst->numwords; i++) - gcc_assert (dst->elts[i] != 0); - - sbitmap_verify_popcount (dst->wordmask); - gcc_assert (sbitmap_popcount (dst->wordmask, - dst->wordmask->n_bits) == dst->numwords); - } -#endif - return changed; -} - -/* Perform the operation DST = A | (B & ~C). */ - -bool -bitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c) -{ - bool changed; - ebitmap temp = ebitmap_alloc (1); -#ifdef EBITMAP_DEBUGGING - ebitmap dstcopy = ebitmap_alloc (1); - bitmap_copy (dstcopy, dst); -#endif - - dst->cache = NULL; - bitmap_and_compl (temp, b, c); - changed = bitmap_ior (dst, a, temp); -#ifdef EBITMAP_DEBUGGING - { - ebitmap_iterator ebi; - unsigned int i; - - EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi) - gcc_assert (bitmap_bit_p (dst, i)); - - EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi) - if (!bitmap_bit_p (c, i)) - gcc_assert (bitmap_bit_p (dst, i)); - gcc_assert (changed == !bitmap_equal_p (dst, dstcopy)); - } -#endif - ebitmap_free (temp); - - return changed; -} - -/* Return true if ebitmap DST is equal to ebitmap SRC. */ - -bool -bitmap_equal_p (ebitmap dst, ebitmap src) -{ - unsigned int which = MIN (dst->wordmask->size, src->wordmask->size); - - if (dst->numwords != src->numwords) - return false; - - /* bitmap_equal_p compares up to the size of the first argument, so - if the two sbitmaps are not equally sized, we need to pass the - smaller one as the first argument, or it will crash. */ - if (which == dst->wordmask->size - && !bitmap_equal_p (dst->wordmask, src->wordmask)) - return false; - else if (which == src->wordmask->size - && !bitmap_equal_p (src->wordmask, dst->wordmask)) - return false; - - return memcmp (dst->elts, src->elts, - dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0; - return true; -} diff --git a/gcc/ebitmap.h b/gcc/ebitmap.h deleted file mode 100644 index fef3154..0000000 --- a/gcc/ebitmap.h +++ /dev/null @@ -1,175 +0,0 @@ -/* Sparse array based bitmaps. - Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. - -This file is part of GCC. - -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 3, or (at your option) any later -version. - -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 GCC; see the file COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -#ifndef GCC_EBITMAP_H -#define GCC_EBITMAP_H - -#include "sbitmap.h" - -#define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT) -#define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT - -typedef struct ebitmap_def -{ - unsigned int n_elts; /* number of elements in the array. */ - sbitmap wordmask; /* wordmask saying which words are - nonzero. */ - unsigned int numwords; /* number of nonzero words. */ - unsigned int cacheindex; /* which word cache is. */ - EBITMAP_ELT_TYPE *elts; /* nonzero element array. */ - EBITMAP_ELT_TYPE *cache; /* last tested element, or NULL. */ -} *ebitmap; - - -inline bool bitmap_empty_p (ebitmap map) -{ - return map->numwords == 0; -} - -#define ebitmap_free(MAP) (free((MAP)->elts), \ - sbitmap_free ((MAP)->wordmask), \ - free((MAP))) - -extern void bitmap_set_bit (ebitmap, unsigned int); -extern void bitmap_clear_bit (ebitmap, unsigned int); -extern bool bitmap_bit_p (ebitmap, unsigned int); -extern void dump_bitmap (FILE *, ebitmap); -extern void dump_bitmap_file (FILE *, ebitmap); -extern void dump_bitmap_vector (FILE *, const char *, const char *, ebitmap *, - int); -extern ebitmap ebitmap_alloc (unsigned int); -extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int); -extern void bitmap_copy (ebitmap, ebitmap); -extern void bitmap_and (ebitmap, ebitmap, ebitmap); -extern void bitmap_and_into (ebitmap, ebitmap); -extern bool bitmap_and_compl (ebitmap, ebitmap, ebitmap); -extern bool bitmap_and_compl_into (ebitmap, ebitmap); -extern bool bitmap_ior_into (ebitmap, ebitmap); -extern bool bitmap_ior (ebitmap, ebitmap, ebitmap); -extern bool bitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap); -extern bool bitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap); -extern bool bitmap_equal_p (ebitmap, ebitmap); -extern void bitmap_clear (ebitmap); -extern int bitmap_last_set_bit (ebitmap); -extern void debug_bitmap (ebitmap); -extern unsigned long bitmap_popcount(ebitmap, unsigned long); - -/* The iterator for ebitmap. */ -typedef struct { - /* The pointer to the first word of the bitmap. */ - EBITMAP_ELT_TYPE *ptr; - - /* Element number inside ptr that we are at. */ - unsigned int eltnum; - - /* The size of the bitmap. */ - unsigned int size; - - /* Current bit index. */ - unsigned int bit_num; - - /* The words currently visited. */ - EBITMAP_ELT_TYPE word; - - /* The word mask iterator. */ - sbitmap_iterator maskiter; -} ebitmap_iterator; - -static inline void -ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min) -{ - unsigned unused; - bmp_iter_set_init (&i->maskiter, bmp->wordmask, - min / EBITMAP_ELT_BITS, &unused); - i->size = bmp->numwords; - if (i->size == 0) - { - i->ptr = NULL; - i->eltnum = 0; - i->bit_num = 0; - i->word = 0; - return; - } - i->ptr = bmp->elts; - i->bit_num = min; - i->eltnum = 0; - - if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits) - { - i->word = 0; - } - else - { - if (bitmap_bit_p (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0) - i->word = 0; - else - { - unsigned int wordindex = min / EBITMAP_ELT_BITS; - unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex); - i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS); - i->eltnum = count + 1; - } - } -} - -static inline bool -ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n) -{ - unsigned int ourn = 0; - unsigned unused; - - if (i->size == 0) - return false; - - if (i->word == 0) - { - bmp_iter_next (&i->maskiter, &unused); - if (!bmp_iter_set (&i->maskiter, &ourn)) - return false; - i->bit_num = ourn * EBITMAP_ELT_BITS; - i->word = i->ptr[i->eltnum++]; - } - - /* Skip bits that are zero. */ - - for (; (i->word & 1) == 0; i->word >>= 1) - i->bit_num++; - - *n = i->bit_num; - return true; -} - -static inline void -ebitmap_iter_next (ebitmap_iterator *i) -{ - i->word >>= 1; - i->bit_num++; -} - -/* Loop over all elements of EBITMAP, starting with MIN. In each - iteration, N is set to the index of the bit being visited. ITER is - an instance of ebitmap_iterator used to iterate the bitmap. */ - -#define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER) \ - for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN)); \ - ebitmap_iter_cond (&(ITER), &(N)); \ - ebitmap_iter_next (&(ITER))) - - -#endif /* ! GCC_EBITMAP_H */ diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index 191c826..b50c82e 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -44,6 +44,13 @@ static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE); typedef SBITMAP_ELT_TYPE *sbitmap_ptr; typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr; +/* Return the size in bytes of a bitmap MAP. */ + +static inline unsigned int sbitmap_size_bytes (const_sbitmap map) +{ + return map->size * sizeof (SBITMAP_ELT_TYPE); +} + /* This macro controls debugging that is as expensive as the operations it verifies. */ @@ -53,7 +60,7 @@ typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr; /* Verify the population count of sbitmap A matches the cached value, if there is a cached value. */ -void +static void sbitmap_verify_popcount (const_sbitmap a) { unsigned ix; @@ -111,7 +118,7 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) size = SBITMAP_SET_SIZE (n_elms); bytes = size * sizeof (SBITMAP_ELT_TYPE); - if (bytes > SBITMAP_SIZE_BYTES (bmap)) + if (bytes > sbitmap_size_bytes (bmap)) { amt = (sizeof (struct simple_bitmap_def) + bytes - sizeof (SBITMAP_ELT_TYPE)); @@ -125,7 +132,7 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) if (def) { memset (bmap->elms + bmap->size, -1, - bytes - SBITMAP_SIZE_BYTES (bmap)); + bytes - sbitmap_size_bytes (bmap)); /* Set the new bits if the original last element. */ last_bit = bmap->n_bits % SBITMAP_ELT_BITS; @@ -142,7 +149,7 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) else { memset (bmap->elms + bmap->size, 0, - bytes - SBITMAP_SIZE_BYTES (bmap)); + bytes - sbitmap_size_bytes (bmap)); if (bmap->popcount) memset (bmap->popcount + bmap->size, 0, (size * sizeof (unsigned char)) @@ -181,7 +188,7 @@ sbitmap_realloc (sbitmap src, unsigned int n_elms) amt = (sizeof (struct simple_bitmap_def) + bytes - sizeof (SBITMAP_ELT_TYPE)); - if (SBITMAP_SIZE_BYTES (src) >= bytes) + if (sbitmap_size_bytes (src) >= bytes) { src->n_bits = n_elms; return src; @@ -245,16 +252,6 @@ bitmap_copy (sbitmap dst, const_sbitmap src) memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size); } -/* Copy the first N elements of sbitmap SRC to DST. */ - -void -bitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n) -{ - memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n); - if (dst->popcount) - memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n); -} - /* Determine if a == b. */ int bitmap_equal_p (const_sbitmap a, const_sbitmap b) @@ -275,63 +272,13 @@ bitmap_empty_p (const_sbitmap bmap) return true; } -/* Return false if any of the N bits are set in MAP starting at - START. */ - -bool -bitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n) -{ - unsigned int i = start / SBITMAP_ELT_BITS; - SBITMAP_ELT_TYPE elm; - unsigned int shift = start % SBITMAP_ELT_BITS; - - gcc_assert (bmap->n_bits >= start + n); - - elm = bmap->elms[i]; - elm = elm >> shift; - - if (shift + n <= SBITMAP_ELT_BITS) - { - /* The bits are totally contained in a single element. */ - if (shift + n < SBITMAP_ELT_BITS) - elm &= ((1 << n) - 1); - return (elm == 0); - } - - if (elm) - return false; - - n -= SBITMAP_ELT_BITS - shift; - i++; - - /* Deal with full elts. */ - while (n >= SBITMAP_ELT_BITS) - { - if (bmap->elms[i]) - return false; - i++; - n -= SBITMAP_ELT_BITS; - } - - /* The leftover bits. */ - if (n) - { - elm = bmap->elms[i]; - elm &= ((1 << n) - 1); - return (elm == 0); - } - - return true; -} - - /* Zero all elements in a bitmap. */ void bitmap_clear (sbitmap bmap) { - memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap)); + memset (bmap->elms, 0, sbitmap_size_bytes (bmap)); if (bmap->popcount) memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char)); } @@ -343,7 +290,7 @@ bitmap_ones (sbitmap bmap) { unsigned int last_bit; - memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap)); + memset (bmap->elms, -1, sbitmap_size_bytes (bmap)); if (bmap->popcount) memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char)); @@ -790,50 +737,3 @@ sbitmap_elt_popcount (SBITMAP_ELT_TYPE a) return ret; } #endif - -/* Count the number of bits in SBITMAP a, up to bit MAXBIT. */ - -unsigned long -sbitmap_popcount (const_sbitmap a, unsigned long maxbit) -{ - unsigned long count = 0; - unsigned ix; - unsigned int lastword; - - if (maxbit == 0) - return 0; - - if (maxbit >= a->n_bits) - maxbit = a->n_bits; - - /* Count the bits in the full word. */ - lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1); - for (ix = 0; ix < lastword; ix++) - { - if (a->popcount) - { - count += a->popcount[ix]; -#ifdef BITMAP_DEBUGGING - gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix])); -#endif - } - else - count += do_popcount (a->elms[ix]); - } - - /* Count the remaining bits. */ - if (lastword < a->size) - { - unsigned int bitindex; - SBITMAP_ELT_TYPE theword = a->elms[lastword]; - - bitindex = maxbit % SBITMAP_ELT_BITS; - if (bitindex != 0) - { - theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex); - count += do_popcount (theword); - } - } - return count; -} - diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h index 96590d4..dce22d0 100644 --- a/gcc/sbitmap.h +++ b/gcc/sbitmap.h @@ -42,11 +42,10 @@ along with GCC; see the file COPYING3. If not see the size of the set universe: * clear : bitmap_clear - * cardinality : sbitmap_popcount * choose_one : bitmap_first_set_bit / bitmap_last_set_bit * forall : EXECUTE_IF_SET_IN_BITMAP - * set_copy : bitmap_copy / bitmap_copy_n + * set_copy : bitmap_copy * set_intersection : bitmap_and * set_union : bitmap_ior * set_difference : bitmap_and_compl @@ -93,7 +92,6 @@ struct simple_bitmap_def /* Return the set size needed for N elements. */ #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) -#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE)) /* Return the number of bits in BITMAP. */ #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits) @@ -117,20 +115,6 @@ bitmap_set_bit (sbitmap map, int bitno) |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; } -/* Like bitmap_set_bit, but updates population count. */ - -static inline void -bitmap_set_bit_with_popcount (sbitmap map, int bitno) -{ - bool oldbit; - gcc_checking_assert (map->popcount); - oldbit = bitmap_bit_p (map, bitno); - if (!oldbit) - map->popcount[bitno / SBITMAP_ELT_BITS]++; - map->elms[bitno / SBITMAP_ELT_BITS] - |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; -} - /* Reset bit number BITNO in the sbitmap MAP. */ static inline void @@ -141,20 +125,6 @@ bitmap_clear_bit (sbitmap map, int bitno) &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); } -/* Like bitmap_clear_bit, but updates population count. */ - -static inline void -bitmap_clear_bit_with_popcount (sbitmap map, int bitno) -{ - bool oldbit; - gcc_checking_assert (map->popcount); - oldbit = bitmap_bit_p (map, bitno); - if (oldbit) - map->popcount[bitno / SBITMAP_ELT_BITS]--; - map->elms[bitno / SBITMAP_ELT_BITS] - &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); -} - /* The iterator for sbitmap. */ typedef struct { /* The pointer to the first word of the bitmap. */ @@ -261,10 +231,8 @@ extern sbitmap sbitmap_alloc_with_popcount (unsigned int); extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); extern void bitmap_copy (sbitmap, const_sbitmap); -extern void bitmap_copy_n (sbitmap, const_sbitmap, unsigned int); extern int bitmap_equal_p (const_sbitmap, const_sbitmap); extern bool bitmap_empty_p (const_sbitmap); -extern bool bitmap_range_empty_p (const_sbitmap, unsigned int, unsigned int); extern void bitmap_clear (sbitmap); extern void bitmap_ones (sbitmap); extern void bitmap_vector_clear (sbitmap *, unsigned int); @@ -290,5 +258,4 @@ extern int bitmap_last_set_bit (const_sbitmap); extern void debug_bitmap (const_sbitmap); extern sbitmap sbitmap_realloc (sbitmap, unsigned int); extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long); -extern void sbitmap_verify_popcount (const_sbitmap); #endif /* ! GCC_SBITMAP_H */ |