aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLawrence Crowl <crowl@google.com>2012-11-01 22:39:26 +0000
committerLawrence Crowl <crowl@gcc.gnu.org>2012-11-01 22:39:26 +0000
commit5fd39ce63cb4ce431fbb4c668ad14e1c2335e76a (patch)
tree721953d1607e06b4dcb3e4e0e522f8d20d151d17
parentc291b2adc6f25d897928c79f431d987eb74e4bc5 (diff)
downloadgcc-5fd39ce63cb4ce431fbb4c668ad14e1c2335e76a.zip
gcc-5fd39ce63cb4ce431fbb4c668ad14e1c2335e76a.tar.gz
gcc-5fd39ce63cb4ce431fbb4c668ad14e1c2335e76a.tar.bz2
This patch removes the unused ebitmap, and then removes some sbitmap functions only used by ebitmap.
This patch removes the unused ebitmap, and then removes some sbitmap functions only used by ebitmap. The functions removed are: SET_BIT_WITH_POPCOUNT RESET_BIT_WITH_POPCOUNT bitmap_copy_n bitmap_range_empty_p sbitmap_popcount In addition, two functions have been made private to the implementation file: SBITMAP_SIZE_BYTES sbitmap_verify_popcount Tested on x86-64. Index: gcc/ChangeLog 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> From-SVN: r193072
-rw-r--r--gcc/ChangeLog20
-rw-r--r--gcc/Makefile.in3
-rw-r--r--gcc/ebitmap.c1019
-rw-r--r--gcc/ebitmap.h175
-rw-r--r--gcc/sbitmap.c128
-rw-r--r--gcc/sbitmap.h35
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 */