Patchwork Remove unused ebitmap and unused sbitmap functions.

login
register
mail settings
Submitter Lawrence Crowl
Date Oct. 31, 2012, 10:47 p.m.
Message ID <CAGqM8fZ2WVDrQ-hQwE8tMYpst_bHTPGKivWh=LtuxyvvLZ8BCw@mail.gmail.com>
Download mbox | patch
Permalink /patch/196027/
State New
Headers show

Comments

Lawrence Crowl - Oct. 31, 2012, 10:47 p.m.
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.

Okay for trunk?
Diego Novillo - Nov. 1, 2012, 1:55 p.m.
On 2012-10-31 18:47 , Lawrence Crowl wrote:

> 2012-10-31  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.
>
> Index: gcc/sbitmap.c
> ===================================================================
> --- gcc/sbitmap.c	(revision 193049)
> +++ gcc/sbitmap.c	(working copy)
> @@ -22,6 +22,9 @@ along with GCC; see the file COPYING3.
>   #include "coretypes.h"
>   #include "sbitmap.h"
>
> +/* Return the set size needed for N elements.  */
> +#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
> +

Not terribly important, but maybe take advantage of the change and 
convert it into a static inline function?

OK, otherwise.


Diego.
Lawrence Crowl - Nov. 1, 2012, 6:06 p.m.
On 11/1/12, Diego Novillo <dnovillo@google.com> wrote:
> On 2012-10-31 18:47 , Lawrence Crowl wrote:
>> 2012-10-31  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.
>>
>> Index: gcc/sbitmap.c
>> ===================================================================
>> --- gcc/sbitmap.c	(revision 193049)
>> +++ gcc/sbitmap.c	(working copy)
>> @@ -22,6 +22,9 @@ along with GCC; see the file COPYING3.
>>   #include "coretypes.h"
>>   #include "sbitmap.h"
>>
>> +/* Return the set size needed for N elements.  */
>> +#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof
>> (SBITMAP_ELT_TYPE))
>> +
>
> Not terribly important, but maybe take advantage of the change and
> convert it into a static inline function?

Sure.

> OK, otherwise.

I will merge and commit.

Patch

Index: gcc/ChangeLog

2012-10-31  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.

Index: gcc/sbitmap.c
===================================================================
--- gcc/sbitmap.c	(revision 193049)
+++ gcc/sbitmap.c	(working copy)
@@ -22,6 +22,9 @@  along with GCC; see the file COPYING3.
 #include "coretypes.h"
 #include "sbitmap.h"

+/* Return the set size needed for N elements.  */
+#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
+
 /* This suffices for roughly 99% of the hosts we run on, and the rest
    don't have 256 bit integers.  */
 #if SBITMAP_ELT_BITS > 255
@@ -53,7 +56,7 @@  typedef const SBITMAP_ELT_TYPE *const_sb
 /* 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;
@@ -245,16 +248,6 @@  bitmap_copy (sbitmap dst, const_sbitmap
     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,56 +268,6 @@  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.  */

@@ -790,50 +733,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;
-}
-
Index: gcc/sbitmap.h
===================================================================
--- gcc/sbitmap.h	(revision 193049)
+++ gcc/sbitmap.h	(working copy)
@@ -42,11 +42,10 @@  along with GCC; see the file COPYING3.
    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_SBITMAP
-     * 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 @@  SET_BIT (sbitmap map, unsigned int bitno
     |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
 }

-/* Like SET_BIT, but updates population count.  */
-
-static inline void
-SET_BIT_WITH_POPCOUNT (sbitmap map, unsigned int bitno)
-{
-  bool oldbit;
-  gcc_checking_assert (map->popcount);
-  oldbit = TEST_BIT (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 @@  RESET_BIT (sbitmap map,  unsigned int bi
     &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
 }

-/* Like RESET_BIT, but updates population count.  */
-
-static inline void
-RESET_BIT_WITH_POPCOUNT (sbitmap map,  unsigned int bitno)
-{
-  bool oldbit;
-  gcc_checking_assert (map->popcount);
-  oldbit = TEST_BIT (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.  */
@@ -285,10 +255,8 @@  extern sbitmap sbitmap_alloc_with_popcou
 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);
@@ -314,5 +282,4 @@  extern int bitmap_last_set_bit (const_sb
 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 */
Index: gcc/ebitmap.c
===================================================================
--- gcc/ebitmap.c	(revision 193049)
+++ gcc/ebitmap.c	(working copy)
@@ -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
-      || !TEST_BIT (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;
-        }
-
-      RESET_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 (!TEST_BIT (map->wordmask, wordindex))
-    {
-      unsigned long count;
-      unsigned int i;
-
-      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
-      || !TEST_BIT (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_SBITMAP (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
-	RESET_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_SBITMAP (dst->wordmask, 0, i, sbi)
-    {
-      bool src1hasword, src2hasword;
-
-      src1hasword = TEST_BIT (src1->wordmask, i);
-      src2hasword = TEST_BIT (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
-	    RESET_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_SBITMAP (tempmask, 0, i, sbi)
-    {
-      bool dsthasword, srchasword;
-
-      dsthasword = (i < dst->wordmask->n_bits
-		    && TEST_BIT (dst->wordmask, i));
-      srchasword = (i < src->wordmask->n_bits
-		    && TEST_BIT (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);
-	  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_SBITMAP (tempmask, 0, i, sbi)
-    {
-      bool src1hasword, src2hasword;
-      EBITMAP_ELT_TYPE tmpword;
-      src1hasword = (i < src1->wordmask->n_bits
-		    && TEST_BIT (src1->wordmask, i));
-      src2hasword = (i < src2->wordmask->n_bits
-		    && TEST_BIT (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 || !TEST_BIT (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_SBITMAP (dst->wordmask, 0, i, sbi)
-    {
-      bool srchasword;
-
-      srchasword = (i < src->wordmask->n_bits
-		    && TEST_BIT (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
-	    RESET_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_SBITMAP (src1->wordmask, 0, i, sbi)
-    {
-      bool src2hasword;
-      EBITMAP_ELT_TYPE tmpword;
-
-      src2hasword = (i < src2->wordmask->n_bits
-		     && TEST_BIT (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
-	    RESET_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 || !TEST_BIT (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;
-}
Index: gcc/ebitmap.h
===================================================================
--- gcc/ebitmap.h	(revision 193049)
+++ gcc/ebitmap.h	(working copy)
@@ -1,173 +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)
-{
-  sbitmap_iter_init (&i->maskiter, bmp->wordmask,
-		     min / EBITMAP_ELT_BITS);
-  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 (TEST_BIT (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;
-
-  if (i->size == 0)
-    return false;
-
-  if (i->word == 0)
-    {
-      sbitmap_iter_next (&i->maskiter);
-      if (!sbitmap_iter_cond (&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 */
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 193049)
+++ gcc/Makefile.in	(working copy)
@@ -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
     $(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@