/* Sparse array-based bitmaps.
|
/* Sparse array-based bitmaps.
|
Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
|
Contributed by Daniel Berlin <dberlin@dberlin.org>
|
Contributed by Daniel Berlin <dberlin@dberlin.org>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
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
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "flags.h"
|
#include "flags.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
#include "ebitmap.h"
|
#include "ebitmap.h"
|
|
|
/* The ebitmap data structure is a sparse bitmap structure that works
|
/* The ebitmap data structure is a sparse bitmap structure that works
|
by having two pieces:
|
by having two pieces:
|
1. An array of all nonzero words in the structures, organized as
|
1. An array of all nonzero words in the structures, organized as
|
an array of HOST_WIDE_INT's.
|
an array of HOST_WIDE_INT's.
|
2. A non-sparse bitmap saying which bitmap words are present in the
|
2. A non-sparse bitmap saying which bitmap words are present in the
|
array.
|
array.
|
|
|
As a consequence of this representation, testing whether a bit
|
As a consequence of this representation, testing whether a bit
|
exists in the bitmap is faster than linked-list bitmaps. For bits
|
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
|
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
|
words that exist, it requires O(n/sizeof(word)) time to perform the
|
test (ignoring the one element cache). It also has much better
|
test (ignoring the one element cache). It also has much better
|
locality than linked-list bitmaps.
|
locality than linked-list bitmaps.
|
|
|
To test whether a bit exists, we do the following:
|
To test whether a bit exists, we do the following:
|
1. Test whether the word the bit would appear in exists in the
|
1. Test whether the word the bit would appear in exists in the
|
bitmap (O(1) check of the mask). If not, fail.
|
bitmap (O(1) check of the mask). If not, fail.
|
|
|
2. Population count the mask up to the word containing the bit, to
|
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,
|
find the place in the array the word would be (popcount is cached,
|
but this is just as slow as the linked-list bitmap)
|
but this is just as slow as the linked-list bitmap)
|
3. Test the word to see if the bit exists.
|
3. Test the word to see if the bit exists.
|
|
|
Just like linked-list bitmaps, we cache the last element that has
|
Just like linked-list bitmaps, we cache the last element that has
|
been tested in order to speed up common access patterns.
|
been tested in order to speed up common access patterns.
|
|
|
Most of the other speedups are simply due to better locality of the
|
Most of the other speedups are simply due to better locality of the
|
single contiguous array.
|
single contiguous array.
|
|
|
As would be expected in a structure like this, insertion into an
|
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
|
empty word in the middle requires moving bits to make room for the
|
new word. As most operations that perform sets perform them in
|
new word. As most operations that perform sets perform them in
|
order, this is rarely a problem. We also take advantage of the
|
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).
|
same element cache to make repeated sets to the same word O(1).
|
|
|
Operations on the entire bitmap are also more efficient than linked
|
Operations on the entire bitmap are also more efficient than linked
|
list bitmaps, as they are all operating on contiguous memory, and
|
list bitmaps, as they are all operating on contiguous memory, and
|
can be easily vectorized. They are all O(number of words) +
|
can be easily vectorized. They are all O(number of words) +
|
O(number of bits that may end up in the destination), as the
|
O(number of bits that may end up in the destination), as the
|
appropriate operation is first performed on the word mask, and then
|
appropriate operation is first performed on the word mask, and then
|
only those elements that may generate results are touched.
|
only those elements that may generate results are touched.
|
|
|
Memory wise, the ebitmap starts out using less memory than the
|
Memory wise, the ebitmap starts out using less memory than the
|
linked-list bitmap, but its size in memory is technically bounded
|
linked-list bitmap, but its size in memory is technically bounded
|
by ((index of the highest bit set) / (size of a word) + (index of
|
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
|
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
|
is because the mask is non-sparse. The mask could be transformed
|
into a sparse bitmap at the cost of making bit testing
|
into a sparse bitmap at the cost of making bit testing
|
*theoretically* slower (real world numbers have not been computed
|
*theoretically* slower (real world numbers have not been computed
|
yet as to whether it matters or not). */
|
yet as to whether it matters or not). */
|
|
|
/* #define EBITMAP_DEBUGGING */
|
/* #define EBITMAP_DEBUGGING */
|
|
|
/* Find the last set bit in ebitmap MAP. */
|
/* Find the last set bit in ebitmap MAP. */
|
|
|
int
|
int
|
ebitmap_last_set_bit (ebitmap map)
|
ebitmap_last_set_bit (ebitmap map)
|
{
|
{
|
unsigned int i = 0;
|
unsigned int i = 0;
|
ebitmap_iterator ebi;
|
ebitmap_iterator ebi;
|
bool foundbit = false;
|
bool foundbit = false;
|
|
|
/* This is not the fastest way to do this, we could simply look for
|
/* 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
|
the popcount, and start there, but this function is not used
|
anywhere speed critical. */
|
anywhere speed critical. */
|
EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi)
|
{
|
{
|
foundbit = true;
|
foundbit = true;
|
}
|
}
|
|
|
|
|
if (foundbit)
|
if (foundbit)
|
return i;
|
return i;
|
return -1;
|
return -1;
|
}
|
}
|
|
|
/* Grow or shrink the internal word array for MAP to NEWSIZE
|
/* Grow or shrink the internal word array for MAP to NEWSIZE
|
elements. */
|
elements. */
|
|
|
static inline void
|
static inline void
|
ebitmap_array_grow (ebitmap map, unsigned int newsize)
|
ebitmap_array_grow (ebitmap map, unsigned int newsize)
|
{
|
{
|
if (newsize <= map->n_elts)
|
if (newsize <= map->n_elts)
|
{
|
{
|
map->n_elts = newsize;
|
map->n_elts = newsize;
|
return;
|
return;
|
}
|
}
|
|
|
newsize += newsize / 4;
|
newsize += newsize / 4;
|
|
|
map->n_elts = newsize;
|
map->n_elts = newsize;
|
map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize);
|
map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize);
|
}
|
}
|
|
|
/* Grow the internal word array for MAP so it is at least SIZE
|
/* Grow the internal word array for MAP so it is at least SIZE
|
elements. Will not shrink the array if it is already big
|
elements. Will not shrink the array if it is already big
|
enough. */
|
enough. */
|
|
|
static inline void
|
static inline void
|
ebitmap_array_maybe_grow (ebitmap map, unsigned int size)
|
ebitmap_array_maybe_grow (ebitmap map, unsigned int size)
|
{
|
{
|
if (size >= map->n_elts)
|
if (size >= map->n_elts)
|
ebitmap_array_grow (map, size + 1);
|
ebitmap_array_grow (map, size + 1);
|
}
|
}
|
|
|
/* Retrieve the IDX'th element from the word array for MAP. */
|
/* Retrieve the IDX'th element from the word array for MAP. */
|
|
|
static inline EBITMAP_ELT_TYPE
|
static inline EBITMAP_ELT_TYPE
|
ebitmap_array_get (ebitmap map, unsigned int idx)
|
ebitmap_array_get (ebitmap map, unsigned int idx)
|
{
|
{
|
gcc_assert (idx < map->n_elts);
|
gcc_assert (idx < map->n_elts);
|
return map->elts[idx];
|
return map->elts[idx];
|
}
|
}
|
|
|
/* Retrieve a pointer to the IDX'th element from the word array for
|
/* 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,
|
MAP. If the element index is greater than the size of the array,
|
the array will be grown to the correct size. */
|
the array will be grown to the correct size. */
|
|
|
static inline EBITMAP_ELT_TYPE *
|
static inline EBITMAP_ELT_TYPE *
|
ebitmap_array_grow_get (ebitmap map, unsigned int idx)
|
ebitmap_array_grow_get (ebitmap map, unsigned int idx)
|
{
|
{
|
if (idx >= map->n_elts)
|
if (idx >= map->n_elts)
|
ebitmap_array_grow (map, idx + 1);
|
ebitmap_array_grow (map, idx + 1);
|
return &map->elts[idx];
|
return &map->elts[idx];
|
}
|
}
|
|
|
/* Initialize the internal word array for MAP, so that it is SIZE
|
/* Initialize the internal word array for MAP, so that it is SIZE
|
elements. */
|
elements. */
|
|
|
static inline void
|
static inline void
|
ebitmap_array_init (ebitmap map, unsigned int size)
|
ebitmap_array_init (ebitmap map, unsigned int size)
|
{
|
{
|
if (size > 0)
|
if (size > 0)
|
{
|
{
|
map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size);
|
map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size);
|
map->n_elts = size;
|
map->n_elts = size;
|
}
|
}
|
else
|
else
|
{
|
{
|
map->n_elts = 0;
|
map->n_elts = 0;
|
map->elts = NULL;
|
map->elts = NULL;
|
}
|
}
|
}
|
}
|
|
|
/* Free the internal word array for MAP. */
|
/* Free the internal word array for MAP. */
|
|
|
static inline void
|
static inline void
|
ebitmap_array_clear (ebitmap map)
|
ebitmap_array_clear (ebitmap map)
|
{
|
{
|
if (map->elts)
|
if (map->elts)
|
{
|
{
|
free (map->elts);
|
free (map->elts);
|
map->elts = NULL;
|
map->elts = NULL;
|
}
|
}
|
map->n_elts = 0;
|
map->n_elts = 0;
|
}
|
}
|
|
|
/* Clear ebitmap MAP. */
|
/* Clear ebitmap MAP. */
|
|
|
void
|
void
|
ebitmap_clear (ebitmap map)
|
ebitmap_clear (ebitmap map)
|
{
|
{
|
ebitmap_array_clear (map);
|
ebitmap_array_clear (map);
|
sbitmap_zero (map->wordmask);
|
sbitmap_zero (map->wordmask);
|
map->wordmask = sbitmap_resize (map->wordmask, 1, 0);
|
map->wordmask = sbitmap_resize (map->wordmask, 1, 0);
|
map->numwords = 0;
|
map->numwords = 0;
|
map->cache = NULL;
|
map->cache = NULL;
|
map->cacheindex = 0;
|
map->cacheindex = 0;
|
}
|
}
|
|
|
/* Allocate an ebitmap with enough room for SIZE bits to start out. */
|
/* Allocate an ebitmap with enough room for SIZE bits to start out. */
|
|
|
ebitmap
|
ebitmap
|
ebitmap_alloc (unsigned int size)
|
ebitmap_alloc (unsigned int size)
|
{
|
{
|
ebitmap ret = XNEW (struct ebitmap_def);
|
ebitmap ret = XNEW (struct ebitmap_def);
|
if (size == 0)
|
if (size == 0)
|
size = EBITMAP_ELT_BITS;
|
size = EBITMAP_ELT_BITS;
|
ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS);
|
ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS);
|
ret->wordmask = sbitmap_alloc_with_popcount (size);
|
ret->wordmask = sbitmap_alloc_with_popcount (size);
|
sbitmap_zero (ret->wordmask);
|
sbitmap_zero (ret->wordmask);
|
ret->numwords = 0;
|
ret->numwords = 0;
|
ret->cache = NULL;
|
ret->cache = NULL;
|
ret->cacheindex = 0;
|
ret->cacheindex = 0;
|
|
|
return ret;
|
return ret;
|
}
|
}
|
|
|
/* Clear BIT from ebitmap MAP. */
|
/* Clear BIT from ebitmap MAP. */
|
|
|
void
|
void
|
ebitmap_clear_bit (ebitmap map, unsigned int bit)
|
ebitmap_clear_bit (ebitmap map, unsigned int bit)
|
{
|
{
|
unsigned int wordindex = bit / EBITMAP_ELT_BITS;
|
unsigned int wordindex = bit / EBITMAP_ELT_BITS;
|
unsigned int eltwordindex = 0;
|
unsigned int eltwordindex = 0;
|
unsigned int bitindex, shift;
|
unsigned int bitindex, shift;
|
bool have_eltwordindex = false;
|
bool have_eltwordindex = false;
|
EBITMAP_ELT_TYPE *elt_ptr;
|
EBITMAP_ELT_TYPE *elt_ptr;
|
|
|
/* If the bit can't exist in our bitmap, just return. */
|
/* If the bit can't exist in our bitmap, just return. */
|
if (map->numwords == 0)
|
if (map->numwords == 0)
|
return;
|
return;
|
|
|
if (wordindex >= map->wordmask->n_bits
|
if (wordindex >= map->wordmask->n_bits
|
|| !TEST_BIT (map->wordmask, wordindex))
|
|| !TEST_BIT (map->wordmask, wordindex))
|
return;
|
return;
|
|
|
if (map->cache != NULL && map->cacheindex == wordindex)
|
if (map->cache != NULL && map->cacheindex == wordindex)
|
elt_ptr = map->cache;
|
elt_ptr = map->cache;
|
else
|
else
|
{
|
{
|
eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
|
eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
|
elt_ptr = &map->elts[eltwordindex];
|
elt_ptr = &map->elts[eltwordindex];
|
have_eltwordindex = true;
|
have_eltwordindex = true;
|
}
|
}
|
|
|
bitindex = bit % EBITMAP_ELT_BITS;
|
bitindex = bit % EBITMAP_ELT_BITS;
|
shift = bitindex;
|
shift = bitindex;
|
|
|
*(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift);
|
*(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift);
|
|
|
/* Clear out the empty words. */
|
/* Clear out the empty words. */
|
if (*(elt_ptr) == 0)
|
if (*(elt_ptr) == 0)
|
{
|
{
|
if (!have_eltwordindex)
|
if (!have_eltwordindex)
|
eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
|
eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
|
|
|
if (map->cache != NULL)
|
if (map->cache != NULL)
|
{
|
{
|
if (map->cacheindex == wordindex)
|
if (map->cacheindex == wordindex)
|
map->cache = NULL;
|
map->cache = NULL;
|
else if (map->cacheindex > wordindex)
|
else if (map->cacheindex > wordindex)
|
map->cache = map->cache - 1;
|
map->cache = map->cache - 1;
|
}
|
}
|
|
|
RESET_BIT (map->wordmask, wordindex);
|
RESET_BIT (map->wordmask, wordindex);
|
|
|
memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
|
memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
|
sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
|
sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
|
map->numwords--;
|
map->numwords--;
|
}
|
}
|
}
|
}
|
|
|
/* Set BIT in ebitmap MAP. */
|
/* Set BIT in ebitmap MAP. */
|
|
|
void
|
void
|
ebitmap_set_bit (ebitmap map, unsigned int bit)
|
ebitmap_set_bit (ebitmap map, unsigned int bit)
|
{
|
{
|
unsigned int wordindex = bit / EBITMAP_ELT_BITS;
|
unsigned int wordindex = bit / EBITMAP_ELT_BITS;
|
unsigned int eltwordindex;
|
unsigned int eltwordindex;
|
unsigned int bitindex = bit % EBITMAP_ELT_BITS;
|
unsigned int bitindex = bit % EBITMAP_ELT_BITS;
|
|
|
/* If we have this element cached, just set the bit in it. */
|
/* If we have this element cached, just set the bit in it. */
|
if (map->cache && map->cacheindex == wordindex)
|
if (map->cache && map->cacheindex == wordindex)
|
{
|
{
|
(*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
|
(*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
|
return;
|
return;
|
}
|
}
|
|
|
/* Resize the wordmask if necessary. */
|
/* Resize the wordmask if necessary. */
|
if (wordindex >= map->wordmask->n_bits)
|
if (wordindex >= map->wordmask->n_bits)
|
map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
|
map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
|
|
|
/* Allocate a new word in the array and move whatever is in it's
|
/* Allocate a new word in the array and move whatever is in it's
|
place, if necessary. */
|
place, if necessary. */
|
if (!TEST_BIT (map->wordmask, wordindex))
|
if (!TEST_BIT (map->wordmask, wordindex))
|
{
|
{
|
unsigned long count;
|
unsigned long count;
|
unsigned int i;
|
unsigned int i;
|
|
|
SET_BIT (map->wordmask, wordindex);
|
SET_BIT (map->wordmask, wordindex);
|
count = sbitmap_popcount (map->wordmask, wordindex);
|
count = sbitmap_popcount (map->wordmask, wordindex);
|
gcc_assert (count <= map->numwords);
|
gcc_assert (count <= map->numwords);
|
|
|
for (i = map->numwords; i > count; i--)
|
for (i = map->numwords; i > count; i--)
|
{
|
{
|
EBITMAP_ELT_TYPE *newelt;
|
EBITMAP_ELT_TYPE *newelt;
|
newelt = ebitmap_array_grow_get (map, i);
|
newelt = ebitmap_array_grow_get (map, i);
|
*newelt = ebitmap_array_get (map, i - 1);
|
*newelt = ebitmap_array_get (map, i - 1);
|
}
|
}
|
map->numwords++;
|
map->numwords++;
|
eltwordindex = count;
|
eltwordindex = count;
|
ebitmap_array_maybe_grow (map, eltwordindex);
|
ebitmap_array_maybe_grow (map, eltwordindex);
|
map->elts[eltwordindex] = 0;
|
map->elts[eltwordindex] = 0;
|
}
|
}
|
else
|
else
|
{
|
{
|
eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
|
eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
|
}
|
}
|
|
|
/* Set the actual bit. */
|
/* Set the actual bit. */
|
bitindex = bit % EBITMAP_ELT_BITS;
|
bitindex = bit % EBITMAP_ELT_BITS;
|
|
|
map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
|
map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
|
map->cache = &map->elts[eltwordindex];
|
map->cache = &map->elts[eltwordindex];
|
map->cacheindex = wordindex;
|
map->cacheindex = wordindex;
|
}
|
}
|
|
|
|
|
/* Return true if MAP contains BIT. */
|
/* Return true if MAP contains BIT. */
|
|
|
bool
|
bool
|
ebitmap_bit_p (ebitmap map, unsigned int bit)
|
ebitmap_bit_p (ebitmap map, unsigned int bit)
|
{
|
{
|
unsigned int wordindex = bit / EBITMAP_ELT_BITS;
|
unsigned int wordindex = bit / EBITMAP_ELT_BITS;
|
unsigned int bitindex= bit % EBITMAP_ELT_BITS;
|
unsigned int bitindex= bit % EBITMAP_ELT_BITS;
|
|
|
/* Trivial empty ebitmap case. */
|
/* Trivial empty ebitmap case. */
|
if (map->numwords == 0)
|
if (map->numwords == 0)
|
return false;
|
return false;
|
|
|
if (map->cache && map->cacheindex == wordindex)
|
if (map->cache && map->cacheindex == wordindex)
|
return ((*map->cache) >> bitindex) & 1;
|
return ((*map->cache) >> bitindex) & 1;
|
|
|
/* If the wordindex is greater than the size of the wordmask, *or*
|
/* 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
|
it's not set in the wordmask, this bit can't exist in our
|
ebitmap. */
|
ebitmap. */
|
if (wordindex >= map->wordmask->n_bits
|
if (wordindex >= map->wordmask->n_bits
|
|| !TEST_BIT (map->wordmask, wordindex))
|
|| !TEST_BIT (map->wordmask, wordindex))
|
return false;
|
return false;
|
|
|
/* Find the bit and test it. */
|
/* Find the bit and test it. */
|
map->cacheindex = wordindex;
|
map->cacheindex = wordindex;
|
wordindex = sbitmap_popcount (map->wordmask, wordindex);
|
wordindex = sbitmap_popcount (map->wordmask, wordindex);
|
map->cache = &map->elts[wordindex];
|
map->cache = &map->elts[wordindex];
|
|
|
return (map->elts[wordindex] >> bitindex) & 1;
|
return (map->elts[wordindex] >> bitindex) & 1;
|
}
|
}
|
|
|
/* Copy ebitmap SRC to DST. */
|
/* Copy ebitmap SRC to DST. */
|
|
|
void
|
void
|
ebitmap_copy (ebitmap dst, ebitmap src)
|
ebitmap_copy (ebitmap dst, ebitmap src)
|
{
|
{
|
/* Blow away any existing wordmask, and copy the new one. */
|
/* Blow away any existing wordmask, and copy the new one. */
|
sbitmap_free (dst->wordmask);
|
sbitmap_free (dst->wordmask);
|
dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
|
dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
|
sbitmap_copy (dst->wordmask, src->wordmask);
|
sbitmap_copy (dst->wordmask, src->wordmask);
|
|
|
/* Make sure our destination array is big enough, and then copy the
|
/* Make sure our destination array is big enough, and then copy the
|
actual words. */
|
actual words. */
|
ebitmap_array_grow (dst, src->numwords);
|
ebitmap_array_grow (dst, src->numwords);
|
memcpy (dst->elts, src->elts,
|
memcpy (dst->elts, src->elts,
|
src->numwords * sizeof (EBITMAP_ELT_TYPE));
|
src->numwords * sizeof (EBITMAP_ELT_TYPE));
|
dst->numwords = src->numwords;
|
dst->numwords = src->numwords;
|
dst->cache = NULL;
|
dst->cache = NULL;
|
}
|
}
|
|
|
/* Dump ebitmap BMAP to FILE. */
|
/* Dump ebitmap BMAP to FILE. */
|
|
|
void
|
void
|
dump_ebitmap (FILE *file, ebitmap bmap)
|
dump_ebitmap (FILE *file, ebitmap bmap)
|
{
|
{
|
unsigned int pos;
|
unsigned int pos;
|
unsigned int i;
|
unsigned int i;
|
int res;
|
int res;
|
unsigned int size;
|
unsigned int size;
|
|
|
res = sbitmap_last_set_bit (bmap->wordmask);
|
res = sbitmap_last_set_bit (bmap->wordmask);
|
if (res == -1)
|
if (res == -1)
|
size = 0;
|
size = 0;
|
else
|
else
|
size = (res + 1) * EBITMAP_ELT_BITS;
|
size = (res + 1) * EBITMAP_ELT_BITS;
|
|
|
fprintf (file, "n_words = %d, set = {", bmap->numwords);
|
fprintf (file, "n_words = %d, set = {", bmap->numwords);
|
|
|
for (pos = 30, i = 0; i < size; i++)
|
for (pos = 30, i = 0; i < size; i++)
|
if (ebitmap_bit_p (bmap, i))
|
if (ebitmap_bit_p (bmap, i))
|
{
|
{
|
if (pos > 70)
|
if (pos > 70)
|
{
|
{
|
fprintf (file, "\n ");
|
fprintf (file, "\n ");
|
pos = 0;
|
pos = 0;
|
}
|
}
|
|
|
pos += fprintf (file, "%d ", i);
|
pos += fprintf (file, "%d ", i);
|
}
|
}
|
|
|
fprintf (file, "}\n");
|
fprintf (file, "}\n");
|
}
|
}
|
|
|
/* Dump ebitmap BMAP to stderr. */
|
/* Dump ebitmap BMAP to stderr. */
|
|
|
void
|
void
|
debug_ebitmap (ebitmap bmap)
|
debug_ebitmap (ebitmap bmap)
|
{
|
{
|
dump_ebitmap (stderr, bmap);
|
dump_ebitmap (stderr, bmap);
|
}
|
}
|
|
|
/* Perform the operation DST &= SRC. */
|
/* Perform the operation DST &= SRC. */
|
|
|
void
|
void
|
ebitmap_and_into (ebitmap dst, ebitmap src)
|
ebitmap_and_into (ebitmap dst, ebitmap src)
|
{
|
{
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
unsigned int i;
|
unsigned int i;
|
unsigned int neweltindex = 0;
|
unsigned int neweltindex = 0;
|
unsigned int dsteltindex = 0;
|
unsigned int dsteltindex = 0;
|
unsigned int srceltindex = 0;
|
unsigned int srceltindex = 0;
|
|
|
gcc_assert (dst != src);
|
gcc_assert (dst != src);
|
|
|
dst->cache = NULL;
|
dst->cache = NULL;
|
|
|
/* Short circuit the empty bitmap cases. */
|
/* Short circuit the empty bitmap cases. */
|
if (src->numwords == 0 || dst->numwords == 0)
|
if (src->numwords == 0 || dst->numwords == 0)
|
{
|
{
|
ebitmap_clear (dst);
|
ebitmap_clear (dst);
|
return;
|
return;
|
}
|
}
|
|
|
/* AND the masks, then walk the words that may actually appear in
|
/* AND the masks, then walk the words that may actually appear in
|
the result, AND'ing them. */
|
the result, AND'ing them. */
|
sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
|
sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
|
{
|
{
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
|
tmpword &= ebitmap_array_get (dst, dsteltindex++);
|
tmpword &= ebitmap_array_get (dst, dsteltindex++);
|
if (tmpword != 0)
|
if (tmpword != 0)
|
{
|
{
|
EBITMAP_ELT_TYPE *dstplace;
|
EBITMAP_ELT_TYPE *dstplace;
|
dstplace = ebitmap_array_grow_get (dst, neweltindex++);
|
dstplace = ebitmap_array_grow_get (dst, neweltindex++);
|
*dstplace = tmpword;
|
*dstplace = tmpword;
|
}
|
}
|
else
|
else
|
RESET_BIT (dst->wordmask, i);
|
RESET_BIT (dst->wordmask, i);
|
}
|
}
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
{
|
{
|
unsigned int i;
|
unsigned int i;
|
|
|
for (i = 0; i < dst->numwords; i++)
|
for (i = 0; i < dst->numwords; i++)
|
gcc_assert (dst->elts[i] != 0);
|
gcc_assert (dst->elts[i] != 0);
|
|
|
sbitmap_verify_popcount (dst->wordmask);
|
sbitmap_verify_popcount (dst->wordmask);
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
dst->wordmask->n_bits) == dst->numwords);
|
dst->wordmask->n_bits) == dst->numwords);
|
}
|
}
|
#endif
|
#endif
|
dst->numwords = neweltindex;
|
dst->numwords = neweltindex;
|
}
|
}
|
|
|
/* Perform the operation DST = SRC1 & SRC2. */
|
/* Perform the operation DST = SRC1 & SRC2. */
|
|
|
void
|
void
|
ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
|
ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
|
{
|
{
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
unsigned int i;
|
unsigned int i;
|
unsigned int neweltindex = 0;
|
unsigned int neweltindex = 0;
|
unsigned int src1eltindex = 0;
|
unsigned int src1eltindex = 0;
|
unsigned int src2eltindex = 0;
|
unsigned int src2eltindex = 0;
|
|
|
dst->cache = NULL;
|
dst->cache = NULL;
|
if (src1->numwords == 0 || src2->numwords == 0)
|
if (src1->numwords == 0 || src2->numwords == 0)
|
{
|
{
|
ebitmap_clear (dst);
|
ebitmap_clear (dst);
|
return;
|
return;
|
}
|
}
|
|
|
dst->wordmask
|
dst->wordmask
|
= sbitmap_resize (dst->wordmask,
|
= sbitmap_resize (dst->wordmask,
|
MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
|
MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
|
0);
|
0);
|
sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
|
sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
|
{
|
{
|
bool src1hasword, src2hasword;
|
bool src1hasword, src2hasword;
|
|
|
src1hasword = TEST_BIT (src1->wordmask, i);
|
src1hasword = TEST_BIT (src1->wordmask, i);
|
src2hasword = TEST_BIT (src2->wordmask, i);
|
src2hasword = TEST_BIT (src2->wordmask, i);
|
|
|
if (src1hasword && src2hasword)
|
if (src1hasword && src2hasword)
|
{
|
{
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
|
tmpword &= ebitmap_array_get (src2, src2eltindex++);
|
tmpword &= ebitmap_array_get (src2, src2eltindex++);
|
if (tmpword != 0)
|
if (tmpword != 0)
|
{
|
{
|
EBITMAP_ELT_TYPE *dstplace;
|
EBITMAP_ELT_TYPE *dstplace;
|
dstplace = ebitmap_array_grow_get (dst, neweltindex++);
|
dstplace = ebitmap_array_grow_get (dst, neweltindex++);
|
*dstplace = tmpword;
|
*dstplace = tmpword;
|
}
|
}
|
else
|
else
|
RESET_BIT (dst->wordmask, i);
|
RESET_BIT (dst->wordmask, i);
|
}
|
}
|
else if (src1hasword)
|
else if (src1hasword)
|
src1eltindex++;
|
src1eltindex++;
|
else
|
else
|
src2eltindex++;
|
src2eltindex++;
|
}
|
}
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
{
|
{
|
ebitmap_iterator ebi;
|
ebitmap_iterator ebi;
|
unsigned int i;
|
unsigned int i;
|
|
|
for (i = 0; i < dst->numwords; i++)
|
for (i = 0; i < dst->numwords; i++)
|
gcc_assert (dst->elts[i] != 0);
|
gcc_assert (dst->elts[i] != 0);
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
|
if (ebitmap_bit_p (src2, i))
|
if (ebitmap_bit_p (src2, i))
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
|
|
for (i = 0; i < dst->numwords; i++)
|
for (i = 0; i < dst->numwords; i++)
|
gcc_assert (dst->elts[i] != 0);
|
gcc_assert (dst->elts[i] != 0);
|
|
|
sbitmap_verify_popcount (dst->wordmask);
|
sbitmap_verify_popcount (dst->wordmask);
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
dst->wordmask->n_bits) == dst->numwords);
|
dst->wordmask->n_bits) == dst->numwords);
|
}
|
}
|
#endif
|
#endif
|
dst->numwords = neweltindex;
|
dst->numwords = neweltindex;
|
}
|
}
|
|
|
/* Perform the operation DST |= SRC. Return true if any bits in DST
|
/* Perform the operation DST |= SRC. Return true if any bits in DST
|
changed. */
|
changed. */
|
|
|
bool
|
bool
|
ebitmap_ior_into (ebitmap dst, ebitmap src)
|
ebitmap_ior_into (ebitmap dst, ebitmap src)
|
{
|
{
|
unsigned int dstsize = dst->wordmask->n_bits;
|
unsigned int dstsize = dst->wordmask->n_bits;
|
unsigned int srcsize = src->wordmask->n_bits;
|
unsigned int srcsize = src->wordmask->n_bits;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
unsigned int i;
|
unsigned int i;
|
sbitmap tempmask;
|
sbitmap tempmask;
|
unsigned int neweltindex = 0;
|
unsigned int neweltindex = 0;
|
unsigned int dsteltindex = 0;
|
unsigned int dsteltindex = 0;
|
unsigned int srceltindex = 0;
|
unsigned int srceltindex = 0;
|
bool changed = false;
|
bool changed = false;
|
EBITMAP_ELT_TYPE *newarray;
|
EBITMAP_ELT_TYPE *newarray;
|
unsigned int newarraysize;
|
unsigned int newarraysize;
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap_copy (dstcopy, dst);
|
ebitmap_copy (dstcopy, dst);
|
#endif
|
#endif
|
|
|
dst->cache = NULL;
|
dst->cache = NULL;
|
if (dst == src)
|
if (dst == src)
|
return false;
|
return false;
|
|
|
if (dst->numwords == 0 && src->numwords != 0)
|
if (dst->numwords == 0 && src->numwords != 0)
|
{
|
{
|
ebitmap_copy (dst, src);
|
ebitmap_copy (dst, src);
|
return true;
|
return true;
|
}
|
}
|
else if (src->numwords == 0)
|
else if (src->numwords == 0)
|
return false;
|
return false;
|
|
|
/* We can do without the temp mask if it's faster, but it would mean
|
/* We can do without the temp mask if it's faster, but it would mean
|
touching more words in the actual dense vector. */
|
touching more words in the actual dense vector. */
|
tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
|
tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
|
sbitmap_zero (tempmask);
|
sbitmap_zero (tempmask);
|
if (srcsize == dstsize)
|
if (srcsize == dstsize)
|
{
|
{
|
sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
|
sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
|
}
|
}
|
else
|
else
|
{
|
{
|
dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
|
dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
|
0);
|
0);
|
if (srcsize >= dstsize)
|
if (srcsize >= dstsize)
|
{
|
{
|
sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
|
sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
|
sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
|
sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
|
}
|
}
|
else
|
else
|
{
|
{
|
sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
|
sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
|
sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
|
sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
|
}
|
}
|
}
|
}
|
newarraysize = src->numwords + dst->numwords;
|
newarraysize = src->numwords + dst->numwords;
|
newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
|
newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
|
{
|
{
|
bool dsthasword, srchasword;
|
bool dsthasword, srchasword;
|
|
|
dsthasword = (i < dst->wordmask->n_bits
|
dsthasword = (i < dst->wordmask->n_bits
|
&& TEST_BIT (dst->wordmask, i));
|
&& TEST_BIT (dst->wordmask, i));
|
srchasword = (i < src->wordmask->n_bits
|
srchasword = (i < src->wordmask->n_bits
|
&& TEST_BIT (src->wordmask, i));
|
&& TEST_BIT (src->wordmask, i));
|
|
|
if (dsthasword && srchasword)
|
if (dsthasword && srchasword)
|
{
|
{
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
|
tmpword |= ebitmap_array_get (dst, dsteltindex);
|
tmpword |= ebitmap_array_get (dst, dsteltindex);
|
if (!changed)
|
if (!changed)
|
changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
|
changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
|
dsteltindex++;
|
dsteltindex++;
|
newarray[neweltindex++] = tmpword;
|
newarray[neweltindex++] = tmpword;
|
}
|
}
|
else if (dsthasword)
|
else if (dsthasword)
|
{
|
{
|
newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
|
newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
|
}
|
}
|
else
|
else
|
{
|
{
|
newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
|
newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
|
gcc_assert (i < dst->wordmask->n_bits);
|
gcc_assert (i < dst->wordmask->n_bits);
|
SET_BIT (dst->wordmask, i);
|
SET_BIT (dst->wordmask, i);
|
changed |= true;
|
changed |= true;
|
}
|
}
|
}
|
}
|
|
|
sbitmap_free (tempmask);
|
sbitmap_free (tempmask);
|
if (changed)
|
if (changed)
|
{
|
{
|
dst->numwords = neweltindex;
|
dst->numwords = neweltindex;
|
free (dst->elts);
|
free (dst->elts);
|
dst->elts = newarray;
|
dst->elts = newarray;
|
dst->n_elts = newarraysize;
|
dst->n_elts = newarraysize;
|
}
|
}
|
else
|
else
|
free (newarray);
|
free (newarray);
|
|
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
{
|
{
|
ebitmap_iterator ebi;
|
ebitmap_iterator ebi;
|
unsigned int i;
|
unsigned int i;
|
|
|
for (i = 0; i < dst->numwords; i++)
|
for (i = 0; i < dst->numwords; i++)
|
gcc_assert (dst->elts[i] != 0);
|
gcc_assert (dst->elts[i] != 0);
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
|
|
sbitmap_verify_popcount (dst->wordmask);
|
sbitmap_verify_popcount (dst->wordmask);
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
dst->wordmask->n_bits) == dst->numwords);
|
dst->wordmask->n_bits) == dst->numwords);
|
}
|
}
|
#endif
|
#endif
|
return changed;
|
return changed;
|
}
|
}
|
|
|
/* Perform the operation DST = SRC1 | SRC2. Return true if any bit
|
/* Perform the operation DST = SRC1 | SRC2. Return true if any bit
|
in DST has changed. */
|
in DST has changed. */
|
|
|
bool
|
bool
|
ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
|
ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
|
{
|
{
|
unsigned int src1size = src1->wordmask->n_bits;
|
unsigned int src1size = src1->wordmask->n_bits;
|
unsigned int src2size = src2->wordmask->n_bits;
|
unsigned int src2size = src2->wordmask->n_bits;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
unsigned int i;
|
unsigned int i;
|
sbitmap tempmask;
|
sbitmap tempmask;
|
unsigned int neweltindex = 0;
|
unsigned int neweltindex = 0;
|
unsigned int src1eltindex = 0;
|
unsigned int src1eltindex = 0;
|
unsigned int src2eltindex = 0;
|
unsigned int src2eltindex = 0;
|
bool changed = false;
|
bool changed = false;
|
EBITMAP_ELT_TYPE *newarray;
|
EBITMAP_ELT_TYPE *newarray;
|
unsigned int newarraysize;
|
unsigned int newarraysize;
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap_copy (dstcopy, dst);
|
ebitmap_copy (dstcopy, dst);
|
#endif
|
#endif
|
|
|
dst->cache = NULL;
|
dst->cache = NULL;
|
tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
|
tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
|
sbitmap_zero (tempmask);
|
sbitmap_zero (tempmask);
|
if (src1size == src2size)
|
if (src1size == src2size)
|
{
|
{
|
sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
|
sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
|
}
|
}
|
else
|
else
|
{
|
{
|
if (src1size >= src2size)
|
if (src1size >= src2size)
|
{
|
{
|
sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
|
sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
|
sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
|
sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
|
}
|
}
|
else
|
else
|
{
|
{
|
sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
|
sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
|
sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
|
sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
|
}
|
}
|
}
|
}
|
newarraysize = src1->numwords + src2->numwords;
|
newarraysize = src1->numwords + src2->numwords;
|
newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
|
newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
|
{
|
{
|
bool src1hasword, src2hasword;
|
bool src1hasword, src2hasword;
|
EBITMAP_ELT_TYPE tmpword;
|
EBITMAP_ELT_TYPE tmpword;
|
src1hasword = (i < src1->wordmask->n_bits
|
src1hasword = (i < src1->wordmask->n_bits
|
&& TEST_BIT (src1->wordmask, i));
|
&& TEST_BIT (src1->wordmask, i));
|
src2hasword = (i < src2->wordmask->n_bits
|
src2hasword = (i < src2->wordmask->n_bits
|
&& TEST_BIT (src2->wordmask, i));
|
&& TEST_BIT (src2->wordmask, i));
|
|
|
if (src1hasword && src2hasword)
|
if (src1hasword && src2hasword)
|
{
|
{
|
tmpword = (ebitmap_array_get (src1, src1eltindex++)
|
tmpword = (ebitmap_array_get (src1, src1eltindex++)
|
| ebitmap_array_get (src2, src2eltindex++));
|
| ebitmap_array_get (src2, src2eltindex++));
|
newarray[neweltindex++] = tmpword;
|
newarray[neweltindex++] = tmpword;
|
}
|
}
|
else if (src1hasword)
|
else if (src1hasword)
|
{
|
{
|
tmpword = ebitmap_array_get (src1, src1eltindex++);
|
tmpword = ebitmap_array_get (src1, src1eltindex++);
|
newarray [neweltindex++] = tmpword;
|
newarray [neweltindex++] = tmpword;
|
}
|
}
|
else
|
else
|
{
|
{
|
tmpword = ebitmap_array_get (src2, src2eltindex++);
|
tmpword = ebitmap_array_get (src2, src2eltindex++);
|
newarray [neweltindex++] = tmpword;
|
newarray [neweltindex++] = tmpword;
|
}
|
}
|
|
|
if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
|
if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
|
{
|
{
|
changed = true;
|
changed = true;
|
}
|
}
|
else if (!changed)
|
else if (!changed)
|
{
|
{
|
unsigned int count = sbitmap_popcount (dst->wordmask, i);
|
unsigned int count = sbitmap_popcount (dst->wordmask, i);
|
changed |= ebitmap_array_get (dst, count) != tmpword;
|
changed |= ebitmap_array_get (dst, count) != tmpword;
|
}
|
}
|
}
|
}
|
|
|
if (changed)
|
if (changed)
|
{
|
{
|
sbitmap_free (dst->wordmask);
|
sbitmap_free (dst->wordmask);
|
dst->wordmask = tempmask;
|
dst->wordmask = tempmask;
|
dst->numwords = neweltindex;
|
dst->numwords = neweltindex;
|
free (dst->elts);
|
free (dst->elts);
|
dst->elts = newarray;
|
dst->elts = newarray;
|
dst->n_elts = newarraysize;
|
dst->n_elts = newarraysize;
|
}
|
}
|
else
|
else
|
{
|
{
|
sbitmap_free (tempmask);
|
sbitmap_free (tempmask);
|
free (newarray);
|
free (newarray);
|
}
|
}
|
|
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
{
|
{
|
ebitmap_iterator ebi;
|
ebitmap_iterator ebi;
|
unsigned int i;
|
unsigned int i;
|
|
|
for (i = 0; i < dst->numwords; i++)
|
for (i = 0; i < dst->numwords; i++)
|
gcc_assert (dst->elts[i] != 0);
|
gcc_assert (dst->elts[i] != 0);
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
}
|
}
|
sbitmap_verify_popcount (dst->wordmask);
|
sbitmap_verify_popcount (dst->wordmask);
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
dst->wordmask->n_bits) == dst->numwords);
|
dst->wordmask->n_bits) == dst->numwords);
|
#endif
|
#endif
|
|
|
return changed;
|
return changed;
|
}
|
}
|
|
|
/* Perform the operation DST &= ~SRC. Return true if any bit in DST
|
/* Perform the operation DST &= ~SRC. Return true if any bit in DST
|
has changed. */
|
has changed. */
|
|
|
bool
|
bool
|
ebitmap_and_compl_into (ebitmap dst, ebitmap src)
|
ebitmap_and_compl_into (ebitmap dst, ebitmap src)
|
{
|
{
|
bool changed = false;
|
bool changed = false;
|
unsigned int i;
|
unsigned int i;
|
unsigned int neweltindex = 0;
|
unsigned int neweltindex = 0;
|
unsigned int dsteltindex = 0;
|
unsigned int dsteltindex = 0;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap_copy (dstcopy, dst);
|
ebitmap_copy (dstcopy, dst);
|
#endif
|
#endif
|
|
|
gcc_assert (dst != src);
|
gcc_assert (dst != src);
|
dst->cache = NULL;
|
dst->cache = NULL;
|
if (src->numwords == 0)
|
if (src->numwords == 0)
|
return false;
|
return false;
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
|
{
|
{
|
bool srchasword;
|
bool srchasword;
|
|
|
srchasword = (i < src->wordmask->n_bits
|
srchasword = (i < src->wordmask->n_bits
|
&& TEST_BIT (src->wordmask, i));
|
&& TEST_BIT (src->wordmask, i));
|
|
|
if (srchasword)
|
if (srchasword)
|
{
|
{
|
unsigned int srccount = sbitmap_popcount (src->wordmask, i);
|
unsigned int srccount = sbitmap_popcount (src->wordmask, i);
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
|
EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
|
tmpword &= ~(ebitmap_array_get (src, srccount));
|
tmpword &= ~(ebitmap_array_get (src, srccount));
|
if (!changed)
|
if (!changed)
|
changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
|
changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
|
dsteltindex++;
|
dsteltindex++;
|
if (tmpword != 0)
|
if (tmpword != 0)
|
{
|
{
|
EBITMAP_ELT_TYPE *dstplace;
|
EBITMAP_ELT_TYPE *dstplace;
|
dstplace = ebitmap_array_grow_get (dst, neweltindex++);
|
dstplace = ebitmap_array_grow_get (dst, neweltindex++);
|
*dstplace = tmpword;
|
*dstplace = tmpword;
|
}
|
}
|
else
|
else
|
RESET_BIT (dst->wordmask, i);
|
RESET_BIT (dst->wordmask, i);
|
}
|
}
|
else
|
else
|
{
|
{
|
dsteltindex++;
|
dsteltindex++;
|
neweltindex++;
|
neweltindex++;
|
}
|
}
|
}
|
}
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
{
|
{
|
unsigned int i;
|
unsigned int i;
|
ebitmap_iterator ebi;
|
ebitmap_iterator ebi;
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
|
{
|
{
|
if (!ebitmap_bit_p (src, i))
|
if (!ebitmap_bit_p (src, i))
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
}
|
}
|
|
|
for (i = 0; i < dst->numwords; i++)
|
for (i = 0; i < dst->numwords; i++)
|
gcc_assert (dst->elts[i] != 0);
|
gcc_assert (dst->elts[i] != 0);
|
|
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
dst->wordmask->n_bits) == neweltindex);
|
dst->wordmask->n_bits) == neweltindex);
|
sbitmap_verify_popcount (dst->wordmask);
|
sbitmap_verify_popcount (dst->wordmask);
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
dst->wordmask->n_bits) == dst->numwords);
|
dst->wordmask->n_bits) == dst->numwords);
|
}
|
}
|
#endif
|
#endif
|
dst->numwords = neweltindex;
|
dst->numwords = neweltindex;
|
/* sbitmap_popcount (dst->wordmask, -1); */
|
/* sbitmap_popcount (dst->wordmask, -1); */
|
|
|
return changed;
|
return changed;
|
}
|
}
|
|
|
/* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit
|
/* Perform the operation DST = SRC1 & ~SRC2. Return true if any bit
|
in DST has changed. */
|
in DST has changed. */
|
|
|
bool
|
bool
|
ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
|
ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
|
{
|
{
|
unsigned int src1size = src1->wordmask->n_bits;
|
unsigned int src1size = src1->wordmask->n_bits;
|
sbitmap_iterator sbi;
|
sbitmap_iterator sbi;
|
unsigned int i;
|
unsigned int i;
|
sbitmap tempmask;
|
sbitmap tempmask;
|
unsigned int neweltindex = 0;
|
unsigned int neweltindex = 0;
|
unsigned int src1eltindex = 0;
|
unsigned int src1eltindex = 0;
|
bool changed = false;
|
bool changed = false;
|
EBITMAP_ELT_TYPE *newarray;
|
EBITMAP_ELT_TYPE *newarray;
|
unsigned int newarraysize;
|
unsigned int newarraysize;
|
|
|
/* XXX: Optimize like the into version. */
|
/* XXX: Optimize like the into version. */
|
dst->cache = NULL;
|
dst->cache = NULL;
|
tempmask = sbitmap_alloc_with_popcount (src1size);
|
tempmask = sbitmap_alloc_with_popcount (src1size);
|
sbitmap_zero (tempmask);
|
sbitmap_zero (tempmask);
|
sbitmap_copy (tempmask, src1->wordmask);
|
sbitmap_copy (tempmask, src1->wordmask);
|
|
|
newarraysize = src1->numwords;
|
newarraysize = src1->numwords;
|
newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
|
newarray = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize);
|
|
|
EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
|
EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
|
{
|
{
|
bool src2hasword;
|
bool src2hasword;
|
EBITMAP_ELT_TYPE tmpword;
|
EBITMAP_ELT_TYPE tmpword;
|
|
|
src2hasword = (i < src2->wordmask->n_bits
|
src2hasword = (i < src2->wordmask->n_bits
|
&& TEST_BIT (src2->wordmask, i));
|
&& TEST_BIT (src2->wordmask, i));
|
|
|
if (src2hasword)
|
if (src2hasword)
|
{
|
{
|
unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
|
unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
|
tmpword = ebitmap_array_get (src1, src1eltindex++)
|
tmpword = ebitmap_array_get (src1, src1eltindex++)
|
& ~(ebitmap_array_get (src2, src2count));
|
& ~(ebitmap_array_get (src2, src2count));
|
if (tmpword)
|
if (tmpword)
|
{
|
{
|
newarray[neweltindex++] = tmpword;
|
newarray[neweltindex++] = tmpword;
|
}
|
}
|
else
|
else
|
RESET_BIT (tempmask, i);
|
RESET_BIT (tempmask, i);
|
|
|
}
|
}
|
else
|
else
|
{
|
{
|
tmpword = ebitmap_array_get (src1, src1eltindex++);
|
tmpword = ebitmap_array_get (src1, src1eltindex++);
|
gcc_assert (tmpword != 0);
|
gcc_assert (tmpword != 0);
|
newarray[neweltindex++] = tmpword;
|
newarray[neweltindex++] = tmpword;
|
}
|
}
|
|
|
if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
|
if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
|
{
|
{
|
changed = true;
|
changed = true;
|
}
|
}
|
else if (!changed)
|
else if (!changed)
|
{
|
{
|
unsigned int count = sbitmap_popcount (dst->wordmask, i);
|
unsigned int count = sbitmap_popcount (dst->wordmask, i);
|
changed |= ebitmap_array_get (dst, count) != tmpword;
|
changed |= ebitmap_array_get (dst, count) != tmpword;
|
}
|
}
|
}
|
}
|
if (changed)
|
if (changed)
|
{
|
{
|
sbitmap_free (dst->wordmask);
|
sbitmap_free (dst->wordmask);
|
dst->wordmask = tempmask;
|
dst->wordmask = tempmask;
|
dst->numwords = neweltindex;
|
dst->numwords = neweltindex;
|
free (dst->elts);
|
free (dst->elts);
|
dst->elts = newarray;
|
dst->elts = newarray;
|
dst->n_elts = newarraysize;
|
dst->n_elts = newarraysize;
|
}
|
}
|
else
|
else
|
{
|
{
|
free (tempmask);
|
free (tempmask);
|
free (newarray);
|
free (newarray);
|
}
|
}
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
{
|
{
|
unsigned int i;
|
unsigned int i;
|
ebitmap_iterator ebi;
|
ebitmap_iterator ebi;
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
|
{
|
{
|
if (!ebitmap_bit_p (src2, i))
|
if (!ebitmap_bit_p (src2, i))
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
}
|
}
|
for (i = 0; i < dst->numwords; i++)
|
for (i = 0; i < dst->numwords; i++)
|
gcc_assert (dst->elts[i] != 0);
|
gcc_assert (dst->elts[i] != 0);
|
|
|
sbitmap_verify_popcount (dst->wordmask);
|
sbitmap_verify_popcount (dst->wordmask);
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
gcc_assert (sbitmap_popcount (dst->wordmask,
|
dst->wordmask->n_bits) == dst->numwords);
|
dst->wordmask->n_bits) == dst->numwords);
|
}
|
}
|
#endif
|
#endif
|
return changed;
|
return changed;
|
}
|
}
|
|
|
/* Perform the operation DST = A | (B & ~C). */
|
/* Perform the operation DST = A | (B & ~C). */
|
|
|
bool
|
bool
|
ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
|
ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
|
{
|
{
|
bool changed;
|
bool changed;
|
ebitmap temp = ebitmap_alloc (1);
|
ebitmap temp = ebitmap_alloc (1);
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap dstcopy = ebitmap_alloc (1);
|
ebitmap_copy (dstcopy, dst);
|
ebitmap_copy (dstcopy, dst);
|
#endif
|
#endif
|
|
|
dst->cache = NULL;
|
dst->cache = NULL;
|
ebitmap_and_compl (temp, b, c);
|
ebitmap_and_compl (temp, b, c);
|
changed = ebitmap_ior (dst, a, temp);
|
changed = ebitmap_ior (dst, a, temp);
|
#ifdef EBITMAP_DEBUGGING
|
#ifdef EBITMAP_DEBUGGING
|
{
|
{
|
ebitmap_iterator ebi;
|
ebitmap_iterator ebi;
|
unsigned int i;
|
unsigned int i;
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
|
|
EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
|
EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
|
if (!ebitmap_bit_p (c, i))
|
if (!ebitmap_bit_p (c, i))
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (ebitmap_bit_p (dst, i));
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
|
}
|
}
|
#endif
|
#endif
|
ebitmap_free (temp);
|
ebitmap_free (temp);
|
|
|
return changed;
|
return changed;
|
}
|
}
|
|
|
/* Return true if ebitmap DST is equal to ebitmap SRC. */
|
/* Return true if ebitmap DST is equal to ebitmap SRC. */
|
|
|
bool
|
bool
|
ebitmap_equal_p (ebitmap dst, ebitmap src)
|
ebitmap_equal_p (ebitmap dst, ebitmap src)
|
{
|
{
|
unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
|
unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
|
|
|
if (dst->numwords != src->numwords)
|
if (dst->numwords != src->numwords)
|
return false;
|
return false;
|
|
|
/* sbitmap_equal compares up to the size of the first argument, so
|
/* sbitmap_equal compares up to the size of the first argument, so
|
if the two sbitmaps are not equally sized, we need to pass the
|
if the two sbitmaps are not equally sized, we need to pass the
|
smaller one as the first argument, or it will crash. */
|
smaller one as the first argument, or it will crash. */
|
if (which == dst->wordmask->size
|
if (which == dst->wordmask->size
|
&& !sbitmap_equal (dst->wordmask, src->wordmask))
|
&& !sbitmap_equal (dst->wordmask, src->wordmask))
|
return false;
|
return false;
|
else if (which == src->wordmask->size
|
else if (which == src->wordmask->size
|
&& !sbitmap_equal (src->wordmask, dst->wordmask))
|
&& !sbitmap_equal (src->wordmask, dst->wordmask))
|
return false;
|
return false;
|
|
|
return memcmp (dst->elts, src->elts,
|
return memcmp (dst->elts, src->elts,
|
dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
|
dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
|
return true;
|
return true;
|
}
|
}
|
|
|
