* config/i386/i386.md (*cmpfp_<mode>): Enable for optimize_size.

[pf3gnuchains/gcc-fork.git] / gcc / bitmap.c

diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 3665394..c2a66f9 100644 (file)
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -1,12 +1,12 @@
 /* Functions to support general ended bitmaps.
 /* Functions to support general ended bitmaps.

-   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004
-   Free Software Foundation, Inc.
+   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
+   2006, 2007 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
 
 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 2, or (at your option) any later
+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
 version.
 
 GCC is distributed in the hope that it will be useful, but WITHOUT ANY


@@ -15,9 +15,8 @@ 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
 for more details.
 
 You should have received a copy of the GNU General Public License

-along with GCC; see the file COPYING.  If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA.  */
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */

 
 #include "config.h"
 #include "system.h"
 
 #include "config.h"
 #include "system.h"


@@ -28,46 +27,126 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "obstack.h"
 #include "ggc.h"
 #include "bitmap.h"
 #include "obstack.h"
 #include "ggc.h"
 #include "bitmap.h"

+#include "hashtab.h"

 
 

-/* Obstack to allocate bitmap elements from.  */
-static struct obstack bitmap_obstack;
-static int bitmap_obstack_init = FALSE;
-\f
-#ifndef INLINE
-#ifndef __GNUC__
-#define INLINE
-#else
-#define INLINE __inline__
-#endif
+#ifdef GATHER_STATISTICS
+
+/* Store information about each particular bitmap.  */
+struct bitmap_descriptor
+{
+  const char *function;
+  const char *file;
+  int line;
+  int allocated;
+  int created;
+  int peak;
+  int current;
+  int nsearches;
+};
+
+/* Hashtable mapping bitmap names to descriptors.  */
+static htab_t bitmap_desc_hash;
+
+/* Hashtable helpers.  */
+static hashval_t
+hash_descriptor (const void *p)
+{
+  const struct bitmap_descriptor *const d = p;
+  return htab_hash_pointer (d->file) + d->line;
+}
+struct loc
+{
+  const char *file;
+  const char *function;
+  int line;
+};
+static int
+eq_descriptor (const void *p1, const void *p2)
+{
+  const struct bitmap_descriptor *const d = p1;
+  const struct loc *const l = p2;
+  return d->file == l->file && d->function == l->function && d->line == l->line;
+}
+
+/* For given file and line, return descriptor, create new if needed.  */
+static struct bitmap_descriptor *
+bitmap_descriptor (const char *file, const char *function, int line)
+{
+  struct bitmap_descriptor **slot;
+  struct loc loc;
+
+  loc.file = file;
+  loc.function = function;
+  loc.line = line;
+
+  if (!bitmap_desc_hash)
+    bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
+
+  slot = (struct bitmap_descriptor **)
+    htab_find_slot_with_hash (bitmap_desc_hash, &loc,
+                             htab_hash_pointer (file) + line,
+                             1);
+  if (*slot)
+    return *slot;
+  *slot = xcalloc (sizeof (**slot), 1);
+  (*slot)->file = file;
+  (*slot)->function = function;
+  (*slot)->line = line;
+  return *slot;
+}
+
+/* Register new bitmap.  */
+void
+bitmap_register (bitmap b MEM_STAT_DECL)
+{
+  b->desc = bitmap_descriptor (_loc_name, _loc_function, _loc_line);
+  b->desc->created++;
+}
+
+/* Account the overhead.  */
+static void
+register_overhead (bitmap b, int amount)
+{
+  b->desc->current += amount;
+  if (amount > 0)
+    b->desc->allocated += amount;
+  gcc_assert (b->desc->current >= 0);
+  if (b->desc->peak < b->desc->current)
+    b->desc->peak = b->desc->current;
+}

 #endif
 
 /* Global data */
 #endif
 
 /* Global data */

-bitmap_element bitmap_zero_bits;       /* An element of all zero bits.  */
-static bitmap_element *bitmap_free;    /* Freelist of bitmap elements.  */
-static GTY((deletable)) bitmap_element *bitmap_ggc_free;
+bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
+bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
+static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
+                                                           GC'd elements.  */

 
 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
 static void bitmap_element_free (bitmap, bitmap_element *);
 static bitmap_element *bitmap_element_allocate (bitmap);
 
 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
 static void bitmap_element_free (bitmap, bitmap_element *);
 static bitmap_element *bitmap_element_allocate (bitmap);

-static int bitmap_element_zerop (bitmap_element *);
+static int bitmap_element_zerop (const bitmap_element *);

 static void bitmap_element_link (bitmap, bitmap_element *);
 static void bitmap_element_link (bitmap, bitmap_element *);

-static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *);
+static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);

 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
 \f
 
 /* Add ELEM to the appropriate freelist.  */
 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
 \f
 
 /* Add ELEM to the appropriate freelist.  */

-static INLINE void
+static inline void

 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 {
 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 {

-  if (head->using_obstack)
+  bitmap_obstack *bit_obstack = head->obstack;
+
+  elt->next = NULL;
+  if (bit_obstack)

     {
     {

-      elt->next = bitmap_free;
-      bitmap_free = elt;
+      elt->prev = bit_obstack->elements;
+      bit_obstack->elements = elt;

     }
   else
     {
     }
   else
     {

-      elt->next = bitmap_ggc_free;
+      elt->prev = bitmap_ggc_free;

       bitmap_ggc_free = elt;
     }
 }
       bitmap_ggc_free = elt;
     }
 }


@@ -75,7 +154,7 @@ bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 /* Free a bitmap element.  Since these are allocated off the
    bitmap_obstack, "free" actually means "put onto the freelist".  */
 
 /* Free a bitmap element.  Since these are allocated off the
    bitmap_obstack, "free" actually means "put onto the freelist".  */
 

-static INLINE void
+static inline void

 bitmap_element_free (bitmap head, bitmap_element *elt)
 {
   bitmap_element *next = elt->next;
 bitmap_element_free (bitmap head, bitmap_element *elt)
 {
   bitmap_element *next = elt->next;


@@ -97,84 +176,225 @@ bitmap_element_free (bitmap head, bitmap_element *elt)
       head->current = next != 0 ? next : prev;
       if (head->current)
        head->indx = head->current->indx;
       head->current = next != 0 ? next : prev;
       if (head->current)
        head->indx = head->current->indx;

+      else
+       head->indx = 0;

     }
     }

+#ifdef GATHER_STATISTICS
+  register_overhead (head, -((int)sizeof (bitmap_element)));
+#endif

   bitmap_elem_to_freelist (head, elt);
 }
 \f
 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 
   bitmap_elem_to_freelist (head, elt);
 }
 \f
 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 

-static INLINE bitmap_element *
+static inline bitmap_element *

 bitmap_element_allocate (bitmap head)
 {
   bitmap_element *element;
 bitmap_element_allocate (bitmap head)
 {
   bitmap_element *element;

+  bitmap_obstack *bit_obstack = head->obstack;

 
 

-  if (head->using_obstack)
+  if (bit_obstack)

     {
     {

-      if (bitmap_free != 0)
-       {
-         element = bitmap_free;
-         bitmap_free = element->next;
-       }
+      element = bit_obstack->elements;
+
+      if (element)
+       /* Use up the inner list first before looking at the next
+          element of the outer list.  */
+       if (element->next)
+         {
+           bit_obstack->elements = element->next;
+           bit_obstack->elements->prev = element->prev;
+         }
+       else
+         /*  Inner list was just a singleton.  */
+         bit_obstack->elements = element->prev;

       else
       else

-       {
-         /* We can't use gcc_obstack_init to initialize the obstack since
-            print-rtl.c now calls bitmap functions, and bitmap is linked
-            into the gen* functions.  */
-         if (!bitmap_obstack_init)
-           {
-             bitmap_obstack_init = TRUE;
+       element = XOBNEW (&bit_obstack->obstack, bitmap_element);
+    }
+  else
+    {
+      element = bitmap_ggc_free;
+      if (element)
+       /* Use up the inner list first before looking at the next
+          element of the outer list.  */
+       if (element->next)
+         {
+           bitmap_ggc_free = element->next;
+           bitmap_ggc_free->prev = element->prev;
+         }
+       else
+         /*  Inner list was just a singleton.  */
+         bitmap_ggc_free = element->prev;
+      else
+       element = GGC_NEW (bitmap_element);
+    }

 
 

-#if !defined(__GNUC__) || (__GNUC__ < 2)
-#define __alignof__(type) 0
+#ifdef GATHER_STATISTICS
+  register_overhead (head, sizeof (bitmap_element));

 #endif
 #endif

+  memset (element->bits, 0, sizeof (element->bits));

 
 

-             obstack_specify_allocation (&bitmap_obstack, OBSTACK_CHUNK_SIZE,
-                                         __alignof__ (bitmap_element),
-                                         obstack_chunk_alloc,
-                                         obstack_chunk_free);
-           }
+  return element;
+}
+
+/* Remove ELT and all following elements from bitmap HEAD.  */
+
+void
+bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
+{
+  bitmap_element *prev;
+  bitmap_obstack *bit_obstack = head->obstack;
+#ifdef GATHER_STATISTICS
+  int n;
+#endif
+
+  if (!elt) return;
+#ifdef GATHER_STATISTICS
+  n = 0;
+  for (prev = elt; prev; prev = prev->next)
+    n++;
+  register_overhead (head, -sizeof (bitmap_element) * n);
+#endif

 
 

-         element = XOBNEW (&bitmap_obstack, bitmap_element);
+  prev = elt->prev;
+  if (prev)
+    {
+      prev->next = NULL;
+      if (head->current->indx > prev->indx)
+       {
+         head->current = prev;
+         head->indx = prev->indx;

        }
     }
   else
     {
        }
     }
   else
     {

-      if (bitmap_ggc_free != NULL)
-       {
-          element = bitmap_ggc_free;
-          bitmap_ggc_free = element->next;
-       }
-      else
-       element = GGC_NEW (bitmap_element);
+      head->first = NULL;
+      head->current = NULL;
+      head->indx = 0;

     }
 
     }
 

-  memset (element->bits, 0, sizeof (element->bits));
+  /* Put the entire list onto the free list in one operation. */
+  if (bit_obstack)
+    {
+      elt->prev = bit_obstack->elements;
+      bit_obstack->elements = elt;
+    }
+  else
+    {
+      elt->prev = bitmap_ggc_free;
+      bitmap_ggc_free = elt;
+    }
+}

 
 

-  return element;
+/* Clear a bitmap by freeing the linked list.  */
+
+inline void
+bitmap_clear (bitmap head)
+{
+  if (head->first)
+    bitmap_elt_clear_from (head, head->first);
+}
+\f
+/* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
+   the default bitmap obstack.  */
+
+void
+bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
+{
+  if (!bit_obstack)
+    bit_obstack = &bitmap_default_obstack;
+
+#if !defined(__GNUC__) || (__GNUC__ < 2)
+#define __alignof__(type) 0
+#endif
+
+  bit_obstack->elements = NULL;
+  bit_obstack->heads = NULL;
+  obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
+                             __alignof__ (bitmap_element),
+                             obstack_chunk_alloc,
+                             obstack_chunk_free);
+}
+
+/* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
+   release the default bitmap obstack.  */
+
+void
+bitmap_obstack_release (bitmap_obstack *bit_obstack)
+{
+  if (!bit_obstack)
+    bit_obstack = &bitmap_default_obstack;
+
+  bit_obstack->elements = NULL;
+  bit_obstack->heads = NULL;
+  obstack_free (&bit_obstack->obstack, NULL);
+}
+
+/* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
+   it on the default bitmap obstack.  */
+
+bitmap
+bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL)
+{
+  bitmap map;
+
+  if (!bit_obstack)
+    bit_obstack = &bitmap_default_obstack;
+  map = bit_obstack->heads;
+  if (map)
+    bit_obstack->heads = (void *)map->first;
+  else
+    map = XOBNEW (&bit_obstack->obstack, bitmap_head);
+  bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
+#ifdef GATHER_STATISTICS
+  register_overhead (map, sizeof (bitmap_head));
+#endif
+
+  return map;
+}
+
+/* Create a new GCd bitmap.  */
+
+bitmap
+bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL)
+{
+  bitmap map;
+
+  map = GGC_NEW (struct bitmap_head_def);
+  bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
+#ifdef GATHER_STATISTICS
+  register_overhead (map, sizeof (bitmap_head));
+#endif
+
+  return map;

 }
 
 }
 

-/* Release any memory allocated by bitmaps.  */
+/* Release an obstack allocated bitmap.  */

 
 void
 
 void

-bitmap_release_memory (void)
+bitmap_obstack_free (bitmap map)

 {
 {

-  bitmap_free = 0;
-  if (bitmap_obstack_init)
+  if (map)

     {
     {

-      bitmap_obstack_init = FALSE;
-      obstack_free (&bitmap_obstack, NULL);
+      bitmap_clear (map);
+      map->first = (void *)map->obstack->heads;
+#ifdef GATHER_STATISTICS
+      register_overhead (map, -((int)sizeof (bitmap_head)));
+#endif
+      map->obstack->heads = map;

     }
 }
 
     }
 }
 

+\f

 /* Return nonzero if all bits in an element are zero.  */
 
 /* Return nonzero if all bits in an element are zero.  */
 

-static INLINE int
-bitmap_element_zerop (bitmap_element *element)
+static inline int
+bitmap_element_zerop (const bitmap_element *element)

 {
 #if BITMAP_ELEMENT_WORDS == 2
   return (element->bits[0] | element->bits[1]) == 0;
 #else
 {
 #if BITMAP_ELEMENT_WORDS == 2
   return (element->bits[0] | element->bits[1]) == 0;
 #else

-  int i;
+  unsigned i;

 
   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
     if (element->bits[i] != 0)
 
   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
     if (element->bits[i] != 0)


@@ -186,7 +406,7 @@ bitmap_element_zerop (bitmap_element *element)
 \f
 /* Link the bitmap element into the current bitmap linked list.  */
 
 \f
 /* Link the bitmap element into the current bitmap linked list.  */
 

-static INLINE void
+static inline void

 bitmap_element_link (bitmap head, bitmap_element *element)
 {
   unsigned int indx = element->indx;
 bitmap_element_link (bitmap head, bitmap_element *element)
 {
   unsigned int indx = element->indx;


@@ -244,14 +464,18 @@ bitmap_element_link (bitmap head, bitmap_element *element)
    new element.  */
 
 static bitmap_element *
    new element.  */
 
 static bitmap_element *

-bitmap_elt_insert_after (bitmap head, bitmap_element *elt)
+bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)

 {
   bitmap_element *node = bitmap_element_allocate (head);
 {
   bitmap_element *node = bitmap_element_allocate (head);

+  node->indx = indx;

 
   if (!elt)
     {
       if (!head->current)
 
   if (!elt)
     {
       if (!head->current)

-       head->current = node;
+       {
+         head->current = node;
+         head->indx = indx;
+       }

       node->next = head->first;
       if (node->next)
        node->next->prev = node;
       node->next = head->first;
       if (node->next)
        node->next->prev = node;


@@ -269,48 +493,14 @@ bitmap_elt_insert_after (bitmap head, bitmap_element *elt)
     }
   return node;
 }
     }
   return node;
 }

-
-/* Remove ELT and all following elements from bitmap HEAD.  */
-
-void
-bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
-{
-  bitmap_element *next;
-
-  while (elt)
-    {
-      next = elt->next;
-      bitmap_element_free (head, elt);
-      elt = next;
-    }
-}
-
-\f
-/* Clear a bitmap by freeing the linked list.  */
-
-INLINE void
-bitmap_clear (bitmap head)
-{
-  bitmap_element *element, *next;
-
-  for (element = head->first; element != 0; element = next)
-    {
-      next = element->next;
-      bitmap_elem_to_freelist (head, element);
-    }
-
-  head->first = head->current = 0;
-}

 \f
 /* Copy a bitmap to another bitmap.  */
 
 void
 \f
 /* Copy a bitmap to another bitmap.  */
 
 void

-bitmap_copy (bitmap to, bitmap from)
+bitmap_copy (bitmap to, const_bitmap from)

 {
 {

-  bitmap_element *from_ptr, *to_ptr = 0;
-#if BITMAP_ELEMENT_WORDS != 2
-  int i;
-#endif
+  const bitmap_element *from_ptr;
+  bitmap_element *to_ptr = 0;

 
   bitmap_clear (to);
 
 
   bitmap_clear (to);
 


@@ -320,14 +510,7 @@ bitmap_copy (bitmap to, bitmap from)
       bitmap_element *to_elt = bitmap_element_allocate (to);
 
       to_elt->indx = from_ptr->indx;
       bitmap_element *to_elt = bitmap_element_allocate (to);
 
       to_elt->indx = from_ptr->indx;

-
-#if BITMAP_ELEMENT_WORDS == 2
-      to_elt->bits[0] = from_ptr->bits[0];
-      to_elt->bits[1] = from_ptr->bits[1];
-#else
-      for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
-       to_elt->bits[i] = from_ptr->bits[i];
-#endif
+      memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));

 
       /* Here we have a special case of bitmap_element_link, for the case
         where we know the links are being entered in sequence.  */
 
       /* Here we have a special case of bitmap_element_link, for the case
         where we know the links are being entered in sequence.  */


@@ -353,24 +536,39 @@ bitmap_copy (bitmap to, bitmap from)
    would hold the bitmap's bit to make eventual allocation
    faster.  */
 
    would hold the bitmap's bit to make eventual allocation
    faster.  */
 

-static INLINE bitmap_element *
+static inline bitmap_element *

 bitmap_find_bit (bitmap head, unsigned int bit)
 {
   bitmap_element *element;
   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
 
 bitmap_find_bit (bitmap head, unsigned int bit)
 {
   bitmap_element *element;
   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
 

+#ifdef GATHER_STATISTICS
+  head->desc->nsearches++;
+#endif

   if (head->current == 0
       || head->indx == indx)
     return head->current;
 
   if (head->current == 0
       || head->indx == indx)
     return head->current;
 

-  if (head->indx > indx)
+  if (head->indx < indx)
+    /* INDX is beyond head->indx.  Search from head->current
+       forward.  */
+    for (element = head->current;
+        element->next != 0 && element->indx < indx;
+        element = element->next)
+      ;
+
+  else if (head->indx / 2 < indx)
+    /* INDX is less than head->indx and closer to head->indx than to
+       0.  Search from head->current backward.  */

     for (element = head->current;
         element->prev != 0 && element->indx > indx;
         element = element->prev)
       ;
 
   else
     for (element = head->current;
         element->prev != 0 && element->indx > indx;
         element = element->prev)
       ;
 
   else

-    for (element = head->current;
+    /* INDX is less than head->indx and closer to 0 than to
+       head->indx.  Search from head->first forward.  */
+    for (element = head->first;

         element->next != 0 && element->indx < indx;
         element = element->next)
       ;
         element->next != 0 && element->indx < indx;
         element = element->next)
       ;


@@ -390,7 +588,7 @@ bitmap_find_bit (bitmap head, unsigned int bit)
 void
 bitmap_clear_bit (bitmap head, int bit)
 {
 void
 bitmap_clear_bit (bitmap head, int bit)
 {

-  bitmap_element *ptr = bitmap_find_bit (head, bit);
+  bitmap_element *const ptr = bitmap_find_bit (head, bit);

 
   if (ptr != 0)
     {
 
   if (ptr != 0)
     {


@@ -444,126 +642,163 @@ bitmap_bit_p (bitmap head, int bit)
   return (ptr->bits[word_num] >> bit_num) & 1;
 }
 \f
   return (ptr->bits[word_num] >> bit_num) & 1;
 }
 \f

-/* Return the bit number of the first set bit in the bitmap, or -1
-   if the bitmap is empty.  */
-
-int
-bitmap_first_set_bit (bitmap a)
+#if GCC_VERSION < 3400
+/* Table of number of set bits in a character, indexed by value of char.  */
+static const unsigned char popcount_table[] =

 {
 {

-  bitmap_element *ptr = a->first;
-  BITMAP_WORD word;
-  unsigned word_num, bit_num;
+    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+    3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
+};
+
+static unsigned long
+bitmap_popcount (BITMAP_WORD a)
+{
+  unsigned long ret = 0;
+  unsigned i;

 
 

-  if (ptr == NULL)
-    return -1;
+  /* Just do this the table way for now  */
+  for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
+    ret += popcount_table[(a >> i) & 0xff];
+  return ret;
+}
+#endif
+/* Count the number of bits set in the bitmap, and return it.  */

 
 

-#if BITMAP_ELEMENT_WORDS == 2
-  word_num = 0, word = ptr->bits[0];
-  if (word == 0)
-    word_num = 1, word = ptr->bits[1];
+unsigned long
+bitmap_count_bits (const_bitmap a)
+{
+  unsigned long count = 0;
+  const bitmap_element *elt;
+  unsigned ix;
+
+  for (elt = a->first; elt; elt = elt->next)
+    {
+      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+       {
+#if GCC_VERSION >= 3400
+         /* Note that popcountl matches BITMAP_WORD in type, so the actual size
+        of BITMAP_WORD is not material.  */
+         count += __builtin_popcountl (elt->bits[ix]);

 #else
 #else

-  for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num)
-    if ((word = ptr->bits[word_num]) != 0)
-      goto word_found;
-  gcc_unreachable ();
- word_found:
+         count += bitmap_popcount (elt->bits[ix]);

 #endif
 #endif

+       }
+    }
+  return count;
+}

 
 

-  /* Binary search for the first set bit.  */
-  /* ??? It'd be nice to know if ffs or ffsl was available.  */
+/* Return true if the bitmap has a single bit set.  Otherwise return
+   false.  */

 
 

-  bit_num = 0;
-  word = word & -word;
+bool
+bitmap_single_bit_set_p (const_bitmap a)
+{
+  unsigned long count = 0;
+  const bitmap_element *elt;
+  unsigned ix;

 
 

-#if nBITMAP_WORD_BITS > 64
- #error "Fill out the table."
-#endif
-#if nBITMAP_WORD_BITS > 32
-  if ((word & 0xffffffff) == 0)
-    word >>= 32, bit_num += 32;
+  if (bitmap_empty_p (a))
+    return false;
+
+  elt = a->first;
+  /* As there are no completely empty bitmap elements, a second one
+     means we have more than one bit set.  */
+  if (elt->next != NULL)
+    return false;
+
+  for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+    {
+#if GCC_VERSION >= 3400
+      /* Note that popcountl matches BITMAP_WORD in type, so the actual size
+        of BITMAP_WORD is not material.  */
+      count += __builtin_popcountl (elt->bits[ix]);
+#else
+      count += bitmap_popcount (elt->bits[ix]);

 #endif
 #endif

-  if ((word & 0xffff) == 0)
-    word >>= 16, bit_num += 16;
-  if ((word & 0xff) == 0)
-    word >>= 8, bit_num += 8;
-  if (word & 0xf0)
-    bit_num += 4;
-  if (word & 0xcc)
-    bit_num += 2;
-  if (word & 0xaa)
-    bit_num += 1;
-
-  return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
-         + word_num * BITMAP_WORD_BITS
-         + bit_num);
+      if (count > 1)
+       return false;
+    }
+
+  return count == 1;

 }
 
 }
 

-/* Return the bit number of the last set bit in the bitmap, or -1
-   if the bitmap is empty.  */

 
 

-int
-bitmap_last_set_bit (bitmap a)
+/* Return the bit number of the first set bit in the bitmap.  The
+   bitmap must be non-empty.  */
+
+unsigned
+bitmap_first_set_bit (const_bitmap a)

 {
 {

-  bitmap_element *ptr = a->first;
+  const bitmap_element *elt = a->first;
+  unsigned bit_no;

   BITMAP_WORD word;
   BITMAP_WORD word;

-  unsigned word_num, bit_num;
-
-  if (ptr == NULL)
-    return -1;
+  unsigned ix;

 
 

-  while (ptr->next != NULL)
-    ptr = ptr->next;
+  gcc_assert (elt);
+  bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
+  for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+    {
+      word = elt->bits[ix];
+      if (word)
+       goto found_bit;
+    }
+  gcc_unreachable ();
+ found_bit:
+  bit_no += ix * BITMAP_WORD_BITS;

 
 

-#if BITMAP_ELEMENT_WORDS == 2
-  word_num = 1, word = ptr->bits[1];
-  if (word == 0)
-    word_num = 0, word = ptr->bits[0];
+#if GCC_VERSION >= 3004
+  gcc_assert (sizeof(long) == sizeof (word));
+  bit_no += __builtin_ctzl (word);

 #else
 #else

-  for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; )
-    if ((word = ptr->bits[word_num]) != 0)
-      goto word_found;
-  gcc_unreachable ();
- word_found:
+  /* Binary search for the first set bit.  */
+#if BITMAP_WORD_BITS > 64
+#error "Fill out the table."

 #endif
 #endif

-
-  /* Binary search for the last set bit.  */
-
-  bit_num = 0;
-#if nBITMAP_WORD_BITS > 64
- #error "Fill out the table."
+#if BITMAP_WORD_BITS > 32
+  if (!(word & 0xffffffff))
+    word >>= 32, bit_no += 32;

 #endif
 #endif

-#if nBITMAP_WORD_BITS > 32
-  if (word & ~(BITMAP_WORD)0xffffffff)
-    word >>= 32, bit_num += 32;
+  if (!(word & 0xffff))
+    word >>= 16, bit_no += 16;
+  if (!(word & 0xff))
+    word >>= 8, bit_no += 8;
+  if (!(word & 0xf))
+    word >>= 4, bit_no += 4;
+  if (!(word & 0x3))
+    word >>= 2, bit_no += 2;
+  if (!(word & 0x1))
+    word >>= 1, bit_no += 1;
+
+ gcc_assert (word & 1);

 #endif
 #endif

-  if (word & 0xffff0000)
-    word >>= 16, bit_num += 16;
-  if (word & 0xff00)
-    word >>= 8, bit_num += 8;
-  if (word & 0xf0)
-    word >>= 4, bit_num += 4;
-  if (word & 0xc)
-    word >>= 2, bit_num += 2;
-  if (word & 0x2)
-    bit_num += 1;
-
-  return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
-         + word_num * BITMAP_WORD_BITS
-         + bit_num);
+ return bit_no;

 }
 \f
 
 }
 \f
 

-/* DST = A & B. */
+/* DST = A & B.  */

 
 void
 
 void

-bitmap_and (bitmap dst, bitmap a, bitmap b)
+bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)

 {
   bitmap_element *dst_elt = dst->first;
 {
   bitmap_element *dst_elt = dst->first;

-  bitmap_element *a_elt = a->first;
-  bitmap_element *b_elt = b->first;
+  const bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;

   bitmap_element *dst_prev = NULL;
 
   bitmap_element *dst_prev = NULL;
 

-  gcc_assert (dst != a && dst != b && a != b);
+  gcc_assert (dst != a && dst != b);
+
+  if (a == b)
+    {
+      bitmap_copy (dst, a);
+      return;
+    }
+

   while (a_elt && b_elt)
     {
       if (a_elt->indx < b_elt->indx)
   while (a_elt && b_elt)
     {
       if (a_elt->indx < b_elt->indx)


@@ -577,9 +812,9 @@ bitmap_and (bitmap dst, bitmap a, bitmap b)
          BITMAP_WORD ior = 0;
 
          if (!dst_elt)
          BITMAP_WORD ior = 0;
 
          if (!dst_elt)

-           dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-         
-         dst_elt->indx = a_elt->indx;
+           dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+         else
+           dst_elt->indx = a_elt->indx;

          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
            {
              BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
            {
              BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];


@@ -596,6 +831,8 @@ bitmap_and (bitmap dst, bitmap a, bitmap b)
          b_elt = b_elt->next;
        }
     }
          b_elt = b_elt->next;
        }
     }

+  /* Ensure that dst->current is valid.  */
+  dst->current = dst->first;

   bitmap_elt_clear_from (dst, dst_elt);
   gcc_assert (!dst->current == !dst->first);
   if (dst->current)
   bitmap_elt_clear_from (dst, dst_elt);
   gcc_assert (!dst->current == !dst->first);
   if (dst->current)


@@ -605,13 +842,15 @@ bitmap_and (bitmap dst, bitmap a, bitmap b)
 /* A &= B.  */
 
 void
 /* A &= B.  */
 
 void

-bitmap_and_into (bitmap a, bitmap b)
+bitmap_and_into (bitmap a, const_bitmap b)

 {
   bitmap_element *a_elt = a->first;
 {
   bitmap_element *a_elt = a->first;

-  bitmap_element *b_elt = b->first;
+  const bitmap_element *b_elt = b->first;

   bitmap_element *next;
 
   bitmap_element *next;
 

-  gcc_assert (a != b);
+  if (a == b)
+    return;
+

   while (a_elt && b_elt)
     {
       if (a_elt->indx < b_elt->indx)
   while (a_elt && b_elt)
     {
       if (a_elt->indx < b_elt->indx)


@@ -647,76 +886,174 @@ bitmap_and_into (bitmap a, bitmap b)
   gcc_assert (!a->current || a->indx == a->current->indx);
 }
 
   gcc_assert (!a->current || a->indx == a->current->indx);
 }
 

+
+/* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
+   if non-NULL.  CHANGED is true if the destination bitmap had already been
+   changed; the new value of CHANGED is returned.  */
+
+static inline bool
+bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
+                const bitmap_element *src_elt, bool changed)
+{
+  if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
+    {
+      unsigned ix;
+
+      for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+       if (src_elt->bits[ix] != dst_elt->bits[ix])
+         {
+           dst_elt->bits[ix] = src_elt->bits[ix];
+           changed = true;
+         }
+    }
+  else
+    {
+      changed = true;
+      if (!dst_elt)
+       dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
+      else
+       dst_elt->indx = src_elt->indx;
+      memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
+    }
+  return changed;
+}
+
+
+

 /* DST = A & ~B  */
 
 /* DST = A & ~B  */
 

-void
-bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
+bool
+bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)

 {
   bitmap_element *dst_elt = dst->first;
 {
   bitmap_element *dst_elt = dst->first;

-  bitmap_element *a_elt = a->first;
-  bitmap_element *b_elt = b->first;
+  const bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;

   bitmap_element *dst_prev = NULL;
   bitmap_element *dst_prev = NULL;

+  bitmap_element **dst_prev_pnext = &dst->first;
+  bool changed = false;
+
+  gcc_assert (dst != a && dst != b);
+
+  if (a == b)
+    {
+      changed = !bitmap_empty_p (dst);
+      bitmap_clear (dst);
+      return changed;
+    }

 
 

-  gcc_assert (dst != a && dst != b && a != b);
-  

   while (a_elt)
     {
   while (a_elt)
     {

-      if (!b_elt || a_elt->indx < b_elt->indx)
+      while (b_elt && b_elt->indx < a_elt->indx)
+       b_elt = b_elt->next;
+
+      if (!b_elt || b_elt->indx > a_elt->indx)

        {
        {

-         /* Copy a_elt. */
-         if (!dst_elt)
-           dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-         
-         dst_elt->indx = a_elt->indx;
-         memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
-         dst_prev = dst_elt;
-         dst_elt = dst_elt->next;
+         changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
+         dst_prev = *dst_prev_pnext;
+         dst_prev_pnext = &dst_prev->next;
+         dst_elt = *dst_prev_pnext;

          a_elt = a_elt->next;
        }
          a_elt = a_elt->next;
        }

-      else if (b_elt->indx < a_elt->indx)
-       b_elt = b_elt->next;
+

       else
        {
          /* Matching elts, generate A & ~B.  */
          unsigned ix;
          BITMAP_WORD ior = 0;
 
       else
        {
          /* Matching elts, generate A & ~B.  */
          unsigned ix;
          BITMAP_WORD ior = 0;
 

-         if (!dst_elt)
-           dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-         
-         dst_elt->indx = a_elt->indx;
-         for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+         if (!changed && dst_elt && dst_elt->indx == a_elt->indx)

            {
            {

-             BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
+             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+               {
+                 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];

 
 

-             dst_elt->bits[ix] = r;
-             ior |= r;
+                 if (dst_elt->bits[ix] != r)
+                   {
+                     changed = true;
+                     dst_elt->bits[ix] = r;
+                   }
+                 ior |= r;
+               }
+           }
+         else
+           {
+             bool new_element;
+             if (!dst_elt || dst_elt->indx > a_elt->indx)
+               {
+                 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+                 new_element = true;
+               }
+             else
+               {
+                 dst_elt->indx = a_elt->indx;
+                 new_element = false;
+               }
+
+             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+               {
+                 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
+
+                 dst_elt->bits[ix] = r;
+                 ior |= r;
+               }
+
+             if (ior)
+               changed = true;
+             else
+               {
+                 changed |= !new_element;
+                 bitmap_element_free (dst, dst_elt);
+                 dst_elt = *dst_prev_pnext;
+               }

            }
            }

+

          if (ior)
            {
          if (ior)
            {

-             dst_prev = dst_elt;
-             dst_elt = dst_elt->next;
+             dst_prev = *dst_prev_pnext;
+             dst_prev_pnext = &dst_prev->next;
+             dst_elt = *dst_prev_pnext;

            }
          a_elt = a_elt->next;
          b_elt = b_elt->next;
        }
     }
            }
          a_elt = a_elt->next;
          b_elt = b_elt->next;
        }
     }

-  bitmap_elt_clear_from (dst, dst_elt);
-  gcc_assert (!dst->current == !dst->first);
+
+  /* Ensure that dst->current is valid.  */
+  dst->current = dst->first;
+
+  if (dst_elt)
+    {
+      changed = true;
+      bitmap_elt_clear_from (dst, dst_elt);
+    }
+  gcc_assert (!dst->current == !dst->first);

   if (dst->current)
     dst->indx = dst->current->indx;
   if (dst->current)
     dst->indx = dst->current->indx;

+
+  return changed;

 }
 
 }
 

-/* A &= ~B */
+/* A &= ~B. Returns true if A changes */

 
 

-void
-bitmap_and_compl_into (bitmap a, bitmap b)
+bool
+bitmap_and_compl_into (bitmap a, const_bitmap b)

 {
   bitmap_element *a_elt = a->first;
 {
   bitmap_element *a_elt = a->first;

-  bitmap_element *b_elt = b->first;
+  const bitmap_element *b_elt = b->first;

   bitmap_element *next;
   bitmap_element *next;

+  BITMAP_WORD changed = 0;
+
+  if (a == b)
+    {
+      if (bitmap_empty_p (a))
+       return false;
+      else
+       {
+         bitmap_clear (a);
+         return true;
+       }
+    }

 
 

-  gcc_assert (a != b);

   while (a_elt && b_elt)
     {
       if (a_elt->indx < b_elt->indx)
   while (a_elt && b_elt)
     {
       if (a_elt->indx < b_elt->indx)


@@ -731,9 +1068,11 @@ bitmap_and_compl_into (bitmap a, bitmap b)
 
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
            {
 
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
            {

-             BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
+             BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
+             BITMAP_WORD r = a_elt->bits[ix] ^ cleared;

 
              a_elt->bits[ix] = r;
 
              a_elt->bits[ix] = r;

+             changed |= cleared;

              ior |= r;
            }
          next = a_elt->next;
              ior |= r;
            }
          next = a_elt->next;


@@ -745,98 +1084,399 @@ bitmap_and_compl_into (bitmap a, bitmap b)
     }
   gcc_assert (!a->current == !a->first);
   gcc_assert (!a->current || a->indx == a->current->indx);
     }
   gcc_assert (!a->current == !a->first);
   gcc_assert (!a->current || a->indx == a->current->indx);

+  return changed != 0;

 }
 
 }
 

-/* DST = A | B.  Return true if DST changes.  */
+/* Set COUNT bits from START in HEAD.  */
+void
+bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
+{
+  unsigned int first_index, end_bit_plus1, last_index;
+  bitmap_element *elt, *elt_prev;
+  unsigned int i;
+
+  if (!count)
+    return;
+
+  first_index = start / BITMAP_ELEMENT_ALL_BITS;
+  end_bit_plus1 = start + count;
+  last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
+  elt = bitmap_find_bit (head, start);
+
+  /* If bitmap_find_bit returns zero, the current is the closest block
+     to the result.  Otherwise, just use bitmap_element_allocate to
+     ensure ELT is set; in the loop below, ELT == NULL means "insert
+     at the end of the bitmap".  */
+  if (!elt)
+    {
+      elt = bitmap_element_allocate (head);
+      elt->indx = first_index;
+      bitmap_element_link (head, elt);
+    }

 
 

-bool
-bitmap_ior (bitmap dst, bitmap a, bitmap b)
+  gcc_assert (elt->indx == first_index);
+  elt_prev = elt->prev;
+  for (i = first_index; i <= last_index; i++)
+    {
+      unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
+      unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
+
+      unsigned int first_word_to_mod;
+      BITMAP_WORD first_mask;
+      unsigned int last_word_to_mod;
+      BITMAP_WORD last_mask;
+      unsigned int ix;
+
+      if (!elt || elt->indx != i)
+       elt = bitmap_elt_insert_after (head, elt_prev, i);
+
+      if (elt_start_bit <= start)
+       {
+         /* The first bit to turn on is somewhere inside this
+            elt.  */
+         first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
+
+         /* This mask should have 1s in all bits >= start position. */
+         first_mask =
+           (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
+         first_mask = ~first_mask;
+       }
+      else
+       {
+         /* The first bit to turn on is below this start of this elt.  */
+         first_word_to_mod = 0;
+         first_mask = ~(BITMAP_WORD) 0;
+       }
+
+      if (elt_end_bit_plus1 <= end_bit_plus1)
+       {
+         /* The last bit to turn on is beyond this elt.  */
+         last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
+         last_mask = ~(BITMAP_WORD) 0;
+       }
+      else
+       {
+         /* The last bit to turn on is inside to this elt.  */
+         last_word_to_mod =
+           (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
+
+         /* The last mask should have 1s below the end bit.  */
+         last_mask =
+           (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
+       }
+
+      if (first_word_to_mod == last_word_to_mod)
+       {
+         BITMAP_WORD mask = first_mask & last_mask;
+         elt->bits[first_word_to_mod] |= mask;
+       }
+      else
+       {
+         elt->bits[first_word_to_mod] |= first_mask;
+         if (BITMAP_ELEMENT_WORDS > 2)
+           for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
+             elt->bits[ix] = ~(BITMAP_WORD) 0;
+         elt->bits[last_word_to_mod] |= last_mask;
+       }
+
+      elt_prev = elt;
+      elt = elt->next;
+    }
+
+  head->current = elt ? elt : elt_prev;
+  head->indx = head->current->indx;
+}
+
+/* Clear COUNT bits from START in HEAD.  */
+void
+bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)

 {
 {

-  bitmap_element *dst_elt = dst->first;
-  bitmap_element *a_elt = a->first;
-  bitmap_element *b_elt = b->first;
-  bitmap_element *dst_prev = NULL;
-  bool changed = false;  
+  unsigned int first_index, end_bit_plus1, last_index;
+  bitmap_element *elt;

 
 

-  gcc_assert (dst != a && dst != b && a != b);
-  while (a_elt || b_elt)
+  if (!count)
+    return;
+
+  first_index = start / BITMAP_ELEMENT_ALL_BITS;
+  end_bit_plus1 = start + count;
+  last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
+  elt = bitmap_find_bit (head, start);
+
+  /* If bitmap_find_bit returns zero, the current is the closest block
+     to the result.  If the current is less than first index, find the
+     next one.  Otherwise, just set elt to be current.  */
+  if (!elt)

     {
     {

-      if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+      if (head->current)

        {
        {

-         /* Matching elts, generate A | B.  */
-         unsigned ix;
-             
-         if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
+         if (head->indx < first_index)

            {
            {

-             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
-               {
-                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
+             elt = head->current->next;
+             if (!elt)
+               return;
+           }
+         else
+           elt = head->current;
+       }
+      else
+       return;
+    }

 
 

-                 if (r != dst_elt->bits[ix])
-                   {
-                     dst_elt->bits[ix] = r;
-                     changed = true;
-                   }
-               }
+  while (elt && (elt->indx <= last_index))
+    {
+      bitmap_element * next_elt = elt->next;
+      unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
+      unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
+
+
+      if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
+       /* Get rid of the entire elt and go to the next one.  */
+       bitmap_element_free (head, elt);
+      else
+       {
+         /* Going to have to knock out some bits in this elt.  */
+         unsigned int first_word_to_mod;
+         BITMAP_WORD first_mask;
+         unsigned int last_word_to_mod;
+         BITMAP_WORD last_mask;
+         unsigned int i;
+         bool clear = true;
+
+         if (elt_start_bit <= start)
+           {
+             /* The first bit to turn off is somewhere inside this
+                elt.  */
+             first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
+
+             /* This mask should have 1s in all bits >= start position. */
+             first_mask =
+               (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
+             first_mask = ~first_mask;

            }
          else
            {
            }
          else
            {

-             changed = true;
-             if (!dst_elt)
-               dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-             dst_elt->indx = a_elt->indx;
-             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
-               {
-                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
-                 
-                 dst_elt->bits[ix] = r;
-               }
+             /* The first bit to turn off is below this start of this elt.  */
+             first_word_to_mod = 0;
+             first_mask = 0;
+             first_mask = ~first_mask;

            }
            }

-         a_elt = a_elt->next;
+
+         if (elt_end_bit_plus1 <= end_bit_plus1)
+           {
+             /* The last bit to turn off is beyond this elt.  */
+             last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
+             last_mask = 0;
+             last_mask = ~last_mask;
+           }
+         else
+           {
+             /* The last bit to turn off is inside to this elt.  */
+             last_word_to_mod =
+               (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
+
+             /* The last mask should have 1s below the end bit.  */
+             last_mask =
+               (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
+           }
+
+
+         if (first_word_to_mod == last_word_to_mod)
+           {
+             BITMAP_WORD mask = first_mask & last_mask;
+             elt->bits[first_word_to_mod] &= ~mask;
+           }
+         else
+           {
+             elt->bits[first_word_to_mod] &= ~first_mask;
+             if (BITMAP_ELEMENT_WORDS > 2)
+               for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
+                 elt->bits[i] = 0;
+             elt->bits[last_word_to_mod] &= ~last_mask;
+           }
+         for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
+           if (elt->bits[i])
+             {
+               clear = false;
+               break;
+             }
+         /* Check to see if there are any bits left.  */
+         if (clear)
+           bitmap_element_free (head, elt);
+       }
+      elt = next_elt;
+    }
+
+  if (elt)
+    {
+      head->current = elt;
+      head->indx = head->current->indx;
+    }
+}
+
+/* A = ~A & B. */
+
+void
+bitmap_compl_and_into (bitmap a, const_bitmap b)
+{
+  bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;
+  bitmap_element *a_prev = NULL;
+  bitmap_element *next;
+
+  gcc_assert (a != b);
+
+  if (bitmap_empty_p (a))
+    {
+      bitmap_copy (a, b);
+      return;
+    }
+  if (bitmap_empty_p (b))
+    {
+      bitmap_clear (a);
+      return;
+    }
+
+  while (a_elt || b_elt)
+    {
+      if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
+       {
+         /* A is before B.  Remove A */
+         next = a_elt->next;
+         a_prev = a_elt->prev;
+         bitmap_element_free (a, a_elt);
+         a_elt = next;
+       }
+      else if (!a_elt || b_elt->indx < a_elt->indx)
+       {
+         /* B is before A.  Copy B. */
+         next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
+         memcpy (next->bits, b_elt->bits, sizeof (next->bits));
+         a_prev = next;

          b_elt = b_elt->next;
          b_elt = b_elt->next;

-         dst_prev = dst_elt;
-         dst_elt = dst_elt->next;

        }
       else
        {
        }
       else
        {

-         /* Copy a single element.  */
-         bitmap_element *src;
+         /* Matching elts, generate A = ~A & B.  */
+         unsigned ix;
+         BITMAP_WORD ior = 0;

 
 

-         if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
+         for (ix = BITMAP_ELEMENT_WORDS; ix--;)

            {
            {

-             src = a_elt;
-             a_elt = a_elt->next;
+             BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
+             BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
+
+             a_elt->bits[ix] = r;
+             ior |= r;

            }
            }

+         next = a_elt->next;
+         if (!ior)
+           bitmap_element_free (a, a_elt);

          else
          else

-           {
-             src = b_elt;
-             b_elt = b_elt->next;
-           }
+           a_prev = a_elt;
+         a_elt = next;
+         b_elt = b_elt->next;
+       }
+    }
+  gcc_assert (!a->current == !a->first);
+  gcc_assert (!a->current || a->indx == a->current->indx);
+  return;
+}
+
+
+/* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
+   overwriting DST_ELT if non-NULL.  CHANGED is true if the destination bitmap
+   had already been changed; the new value of CHANGED is returned.  */
+
+static inline bool
+bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
+               const bitmap_element *a_elt, const bitmap_element *b_elt,
+               bool changed)
+{
+  gcc_assert (a_elt || b_elt);

 
 

-         if (!changed && dst_elt && dst_elt->indx == src->indx)
+  if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+    {
+      /* Matching elts, generate A | B.  */
+      unsigned ix;
+
+      if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
+       {
+         for (ix = BITMAP_ELEMENT_WORDS; ix--;)

            {
            {

-             unsigned ix;
-             
-             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
-               if (src->bits[ix] != dst_elt->bits[ix])
-                 {
-                   dst_elt->bits[ix] = src->bits[ix];
-                   changed = true;
-                 }
+             BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
+             if (r != dst_elt->bits[ix])
+               {
+                 dst_elt->bits[ix] = r;
+                 changed = true;
+               }

            }
            }

+       }
+      else
+       {
+         changed = true;
+         if (!dst_elt)
+           dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);

          else
          else

+           dst_elt->indx = a_elt->indx;
+         for (ix = BITMAP_ELEMENT_WORDS; ix--;)

            {
            {

-             changed = true;
-             if (!dst_elt)
-               dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-             dst_elt->indx = src->indx;
-             memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
+             BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
+             dst_elt->bits[ix] = r;

            }
            }

-         
-         dst_prev = dst_elt;
-         dst_elt = dst_elt->next;

        }
     }
        }
     }

+  else
+    {
+      /* Copy a single element.  */
+      const bitmap_element *src;
+
+      if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
+       src = a_elt;
+      else
+       src = b_elt;
+
+      gcc_assert (src);
+      changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
+    }
+  return changed;
+}
+
+
+/* DST = A | B.  Return true if DST changes.  */
+
+bool
+bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
+{
+  bitmap_element *dst_elt = dst->first;
+  const bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;
+  bitmap_element *dst_prev = NULL;
+  bitmap_element **dst_prev_pnext = &dst->first;
+  bool changed = false;
+
+  gcc_assert (dst != a && dst != b);
+
+  while (a_elt || b_elt)
+    {
+      changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
+
+      if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+       {
+         a_elt = a_elt->next;
+         b_elt = b_elt->next;
+       }
+      else
+       {
+         if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
+            a_elt = a_elt->next;
+          else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
+            b_elt = b_elt->next;
+       }
+
+      dst_prev = *dst_prev_pnext;
+      dst_prev_pnext = &dst_prev->next;
+      dst_elt = *dst_prev_pnext;
+    }

 
   if (dst_elt)
     {
 
   if (dst_elt)
     {


@@ -852,60 +1492,36 @@ bitmap_ior (bitmap dst, bitmap a, bitmap b)
 /* A |= B.  Return true if A changes.  */
 
 bool
 /* A |= B.  Return true if A changes.  */
 
 bool

-bitmap_ior_into (bitmap a, bitmap b)
+bitmap_ior_into (bitmap a, const_bitmap b)

 {
   bitmap_element *a_elt = a->first;
 {
   bitmap_element *a_elt = a->first;

-  bitmap_element *b_elt = b->first;
+  const bitmap_element *b_elt = b->first;

   bitmap_element *a_prev = NULL;
   bitmap_element *a_prev = NULL;

+  bitmap_element **a_prev_pnext = &a->first;

   bool changed = false;
 
   bool changed = false;
 

-  gcc_assert (a != b);
+  if (a == b)
+    return false;
+

   while (b_elt)
     {
   while (b_elt)
     {

-      if (!a_elt || b_elt->indx < a_elt->indx)
+      /* If A lags behind B, just advance it.  */
+      if (!a_elt || a_elt->indx == b_elt->indx)

        {
        {

-         /* Copy b_elt.  */
-         bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
-         
-         dst->indx = b_elt->indx;
-         memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
-         a_prev = dst;
+         changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);

          b_elt = b_elt->next;
          b_elt = b_elt->next;

-         changed = true;
-       }
-      else if (a_elt->indx < b_elt->indx)
-       {
-         a_prev = a_elt;
-         a_elt = a_elt->next;

        }
        }

-      else
+      else if (a_elt->indx > b_elt->indx)

        {
        {

-         /* Matching elts, generate A |= B.  */
-         unsigned ix;
-
-         if (changed)
-           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
-             {
-               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
-               
-               a_elt->bits[ix] = r;
-             }
-         else
-           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
-             {
-               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
-
-               if (a_elt->bits[ix] != r)
-                 {
-                   changed = true;
-                   a_elt->bits[ix] = r;
-                 }
-             }
+          changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);

          b_elt = b_elt->next;
          b_elt = b_elt->next;

-         a_prev = a_elt;
-         a_elt = a_elt->next;

        }
        }

+
+      a_prev = *a_prev_pnext;
+      a_prev_pnext = &a_prev->next;
+      a_elt = *a_prev_pnext;

     }
     }

+

   gcc_assert (!a->current == !a->first);
   if (a->current)
     a->indx = a->current->indx;
   gcc_assert (!a->current == !a->first);
   if (a->current)
     a->indx = a->current->indx;


@@ -915,14 +1531,20 @@ bitmap_ior_into (bitmap a, bitmap b)
 /* DST = A ^ B  */
 
 void
 /* DST = A ^ B  */
 
 void

-bitmap_xor (bitmap dst, bitmap a, bitmap b)
+bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)

 {
   bitmap_element *dst_elt = dst->first;
 {
   bitmap_element *dst_elt = dst->first;

-  bitmap_element *a_elt = a->first;
-  bitmap_element *b_elt = b->first;
+  const bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;

   bitmap_element *dst_prev = NULL;
 
   bitmap_element *dst_prev = NULL;
 

-  gcc_assert (dst != a && dst != b && a != b);
+  gcc_assert (dst != a && dst != b);
+  if (a == b)
+    {
+      bitmap_clear (dst);
+      return;
+    }
+

   while (a_elt || b_elt)
     {
       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
   while (a_elt || b_elt)
     {
       if (a_elt && b_elt && a_elt->indx == b_elt->indx)


@@ -932,9 +1554,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b)
          BITMAP_WORD ior = 0;
 
          if (!dst_elt)
          BITMAP_WORD ior = 0;
 
          if (!dst_elt)

-           dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-         
-         dst_elt->indx = a_elt->indx;
+           dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+         else
+           dst_elt->indx = a_elt->indx;

          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
            {
              BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
            {
              BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];


@@ -953,7 +1575,7 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b)
       else
        {
          /* Copy a single element.  */
       else
        {
          /* Copy a single element.  */

-         bitmap_element *src;
+         const bitmap_element *src;

 
          if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
            {
 
          if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
            {


@@ -967,14 +1589,16 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b)
            }
 
          if (!dst_elt)
            }
 
          if (!dst_elt)

-           dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-         
-         dst_elt->indx = src->indx;
+           dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
+         else
+           dst_elt->indx = src->indx;

          memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
          dst_prev = dst_elt;
          dst_elt = dst_elt->next;
        }
     }
          memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
          dst_prev = dst_elt;
          dst_elt = dst_elt->next;
        }
     }

+  /* Ensure that dst->current is valid.  */
+  dst->current = dst->first;

   bitmap_elt_clear_from (dst, dst_elt);
   gcc_assert (!dst->current == !dst->first);
   if (dst->current)
   bitmap_elt_clear_from (dst, dst_elt);
   gcc_assert (!dst->current == !dst->first);
   if (dst->current)


@@ -984,21 +1608,24 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b)
 /* A ^= B */
 
 void
 /* A ^= B */
 
 void

-bitmap_xor_into (bitmap a, bitmap b)
+bitmap_xor_into (bitmap a, const_bitmap b)

 {
   bitmap_element *a_elt = a->first;
 {
   bitmap_element *a_elt = a->first;

-  bitmap_element *b_elt = b->first;
+  const bitmap_element *b_elt = b->first;

   bitmap_element *a_prev = NULL;
 
   bitmap_element *a_prev = NULL;
 

-  gcc_assert (a != b);
+  if (a == b)
+    {
+      bitmap_clear (a);
+      return;
+    }
+

   while (b_elt)
     {
       if (!a_elt || b_elt->indx < a_elt->indx)
        {
          /* Copy b_elt.  */
   while (b_elt)
     {
       if (!a_elt || b_elt->indx < a_elt->indx)
        {
          /* Copy b_elt.  */

-         bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
-         
-         dst->indx = b_elt->indx;
+         bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);

          memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
          a_prev = dst;
          b_elt = b_elt->next;
          memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
          a_prev = dst;
          b_elt = b_elt->next;


@@ -1040,12 +1667,12 @@ bitmap_xor_into (bitmap a, bitmap b)
    occurs in practice.  */
 
 bool
    occurs in practice.  */
 
 bool

-bitmap_equal_p (bitmap a, bitmap b)
+bitmap_equal_p (const_bitmap a, const_bitmap b)

 {
 {

-  bitmap_element *a_elt;
-  bitmap_element *b_elt;
+  const bitmap_element *a_elt;
+  const bitmap_element *b_elt;

   unsigned ix;
   unsigned ix;

-  
+

   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;
        a_elt = a_elt->next, b_elt = b_elt->next)
   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;
        a_elt = a_elt->next, b_elt = b_elt->next)


@@ -1062,12 +1689,12 @@ bitmap_equal_p (bitmap a, bitmap b)
 /* Return true if A AND B is not empty.  */
 
 bool
 /* Return true if A AND B is not empty.  */
 
 bool

-bitmap_intersect_p (bitmap a, bitmap b)
+bitmap_intersect_p (const_bitmap a, const_bitmap b)

 {
 {

-  bitmap_element *a_elt;
-  bitmap_element *b_elt;
+  const bitmap_element *a_elt;
+  const bitmap_element *b_elt;

   unsigned ix;
   unsigned ix;

-  
+

   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;)
     {
   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;)
     {


@@ -1090,10 +1717,10 @@ bitmap_intersect_p (bitmap a, bitmap b)
 /* Return true if A AND NOT B is not empty.  */
 
 bool
 /* Return true if A AND NOT B is not empty.  */
 
 bool

-bitmap_intersect_compl_p (bitmap a, bitmap b)
+bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)

 {
 {

-  bitmap_element *a_elt;
-  bitmap_element *b_elt;
+  const bitmap_element *a_elt;
+  const bitmap_element *b_elt;

   unsigned ix;
   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;)
   unsigned ix;
   for (a_elt = a->first, b_elt = b->first;
        a_elt && b_elt;)


@@ -1118,16 +1745,103 @@ bitmap_intersect_compl_p (bitmap a, bitmap b)
 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
 
 bool
 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
 
 bool

-bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
+bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)

 {
 {

-  bitmap_head tmp;
-  bool changed;
-  
-  tmp.first = tmp.current = 0;
-  tmp.using_obstack = 0;
-  bitmap_and_compl (&tmp, from1, from2);
-  changed = bitmap_ior (dst, a, &tmp);
-  bitmap_clear (&tmp);
+  bool changed = false;
+
+  bitmap_element *dst_elt = dst->first;
+  const bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;
+  const bitmap_element *kill_elt = kill->first;
+  bitmap_element *dst_prev = NULL;
+  bitmap_element **dst_prev_pnext = &dst->first;
+
+  gcc_assert (dst != a && dst != b && dst != kill);
+
+  /* Special cases.  We don't bother checking for bitmap_equal_p (b, kill).  */
+  if (b == kill || bitmap_empty_p (b))
+    {
+      changed = !bitmap_equal_p (dst, a);
+      if (changed)
+       bitmap_copy (dst, a);
+      return changed;
+    }
+  if (bitmap_empty_p (kill))
+    return bitmap_ior (dst, a, b);
+  if (bitmap_empty_p (a))
+    return bitmap_and_compl (dst, b, kill);
+
+  while (a_elt || b_elt)
+    {
+      bool new_element = false;
+
+      if (b_elt)
+       while (kill_elt && kill_elt->indx < b_elt->indx)
+         kill_elt = kill_elt->next;
+
+      if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
+         && (!a_elt || a_elt->indx >= b_elt->indx))
+        {
+         bitmap_element tmp_elt;
+         unsigned ix;
+
+         BITMAP_WORD ior = 0;
+         tmp_elt.indx = b_elt->indx;
+          for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+            {
+              BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
+              ior |= r;
+              tmp_elt.bits[ix] = r;
+            }
+
+         if (ior)
+           {
+             changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
+                                       a_elt, &tmp_elt, changed);
+             new_element = true;
+             if (a_elt && a_elt->indx == b_elt->indx)
+                a_elt = a_elt->next;
+           }
+
+         b_elt = b_elt->next;
+         kill_elt = kill_elt->next;
+       }
+      else
+       {
+         changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
+                                   a_elt, b_elt, changed);
+         new_element = true;
+
+          if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+           {
+             a_elt = a_elt->next;
+             b_elt = b_elt->next;
+           }
+          else
+           {
+             if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
+                a_elt = a_elt->next;
+              else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
+                b_elt = b_elt->next;
+           }
+       }
+
+      if (new_element)
+       {
+         dst_prev = *dst_prev_pnext;
+         dst_prev_pnext = &dst_prev->next;
+         dst_elt = *dst_prev_pnext;
+       }
+    }
+
+  if (dst_elt)
+    {
+      changed = true;
+      bitmap_elt_clear_from (dst, dst_elt);
+    }
+  gcc_assert (!dst->current == !dst->first);
+  if (dst->current)
+    dst->indx = dst->current->indx;

 
   return changed;
 }
 
   return changed;
 }


@@ -1135,52 +1849,37 @@ bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
 
 bool
 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
 
 bool

-bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
+bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)

 {
   bitmap_head tmp;
   bool changed;
 {
   bitmap_head tmp;
   bool changed;

-  
-  tmp.first = tmp.current = 0;
-  tmp.using_obstack = 0;
+
+  bitmap_initialize (&tmp, &bitmap_default_obstack);

   bitmap_and_compl (&tmp, from1, from2);
   changed = bitmap_ior_into (a, &tmp);
   bitmap_clear (&tmp);
 
   return changed;
 }
   bitmap_and_compl (&tmp, from1, from2);
   changed = bitmap_ior_into (a, &tmp);
   bitmap_clear (&tmp);
 
   return changed;
 }

-\f
-/* Initialize a bitmap header.  */
-
-bitmap
-bitmap_initialize (bitmap head, int using_obstack)
-{
-  if (head == NULL && ! using_obstack)
-    head = GGC_NEW (struct bitmap_head_def);
-
-  head->first = head->current = 0;
-  head->using_obstack = using_obstack;

 
 

-  return head;
-}

 \f
 /* Debugging function to print out the contents of a bitmap.  */
 
 void
 \f
 /* Debugging function to print out the contents of a bitmap.  */
 
 void

-debug_bitmap_file (FILE *file, bitmap head)
+debug_bitmap_file (FILE *file, const_bitmap head)

 {
 {

-  bitmap_element *ptr;
+  const bitmap_element *ptr;

 
 

-  fprintf (file, "\nfirst = " HOST_PTR_PRINTF
-          " current = " HOST_PTR_PRINTF " indx = %u\n",
+  fprintf (file, "\nfirst = %p current = %p indx = %u\n",

           (void *) head->first, (void *) head->current, head->indx);
 
   for (ptr = head->first; ptr; ptr = ptr->next)
     {
       unsigned int i, j, col = 26;
 
           (void *) head->first, (void *) head->current, head->indx);
 
   for (ptr = head->first; ptr; ptr = ptr->next)
     {
       unsigned int i, j, col = 26;
 

-      fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
-              " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
-              (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
+      fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
+              (const void*) ptr, (const void*) ptr->next,
+              (const void*) ptr->prev, ptr->indx);

 
       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
        for (j = 0; j < BITMAP_WORD_BITS; j++)
 
       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
        for (j = 0; j < BITMAP_WORD_BITS; j++)


@@ -1205,7 +1904,7 @@ debug_bitmap_file (FILE *file, bitmap head)
    of a bitmap.  */
 
 void
    of a bitmap.  */
 
 void

-debug_bitmap (bitmap head)
+debug_bitmap (const_bitmap head)

 {
   debug_bitmap_file (stdout, head);
 }
 {
   debug_bitmap_file (stdout, head);
 }


@@ -1214,7 +1913,7 @@ debug_bitmap (bitmap head)
    it does not print anything but the bits.  */
 
 void
    it does not print anything but the bits.  */
 
 void

-bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
+bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)

 {
   const char *comma = "";
   unsigned i;
 {
   const char *comma = "";
   unsigned i;


@@ -1228,5 +1927,80 @@ bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
     }
   fputs (suffix, file);
 }
     }
   fputs (suffix, file);
 }

+#ifdef GATHER_STATISTICS
+
+
+/* Used to accumulate statistics about bitmap sizes.  */
+struct output_info
+{
+  int count;
+  int size;
+};
+
+/* Called via htab_traverse.  Output bitmap descriptor pointed out by SLOT
+   and update statistics.  */
+static int
+print_statistics (void **slot, void *b)
+{
+  struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
+  struct output_info *i = (struct output_info *) b;
+  char s[4096];
+
+  if (d->allocated)
+    {
+      const char *s1 = d->file;
+      const char *s2;
+      while ((s2 = strstr (s1, "gcc/")))
+       s1 = s2 + 4;
+      sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
+      s[41] = 0;
+      fprintf (stderr, "%-41s %6d %10d %10d %10d %10d\n", s,
+              d->created, d->allocated, d->peak, d->current, d->nsearches);
+      i->size += d->allocated;
+      i->count += d->created;
+    }
+  return 1;
+}
+#endif
+/* Output per-bitmap memory usage statistics.  */
+void
+dump_bitmap_statistics (void)
+{
+#ifdef GATHER_STATISTICS
+  struct output_info info;
+
+  if (!bitmap_desc_hash)
+    return;
+
+  fprintf (stderr, "\nBitmap                                     Overall "
+                  "Allocated     Peak        Leak   searched "
+                  "  per search\n");
+  fprintf (stderr, "---------------------------------------------------------------------------------\n");
+  info.count = 0;
+  info.size = 0;
+  htab_traverse (bitmap_desc_hash, print_statistics, &info);
+  fprintf (stderr, "---------------------------------------------------------------------------------\n");
+  fprintf (stderr, "%-40s %7d %10d\n",
+          "Total", info.count, info.size);
+  fprintf (stderr, "---------------------------------------------------------------------------------\n");
+#endif
+}
+
+/* Compute hash of bitmap (for purposes of hashing).  */
+hashval_t
+bitmap_hash (const_bitmap head)
+{
+  const bitmap_element *ptr;
+  BITMAP_WORD hash = 0;
+  int ix;
+
+  for (ptr = head->first; ptr; ptr = ptr->next)
+    {
+      hash ^= ptr->indx;
+      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+       hash ^= ptr->bits[ix];
+    }
+  return (hashval_t)hash;
+}

 
 #include "gt-bitmap.h"
 
 #include "gt-bitmap.h"