GCC 4.2.0 release.

1 files changed, 477 insertions, 264 deletions

diff --git a/contrib/gcc/bitmap.h b/contrib/gcc/bitmap.h
index 4191542..3da58c5 100644
--- a/contrib/gcc/bitmap.h
+++ b/contrib/gcc/bitmap.h
@@ -1,5 +1,5 @@
 /* Functions to support general ended bitmaps.
-   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
+   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
    Free Software Foundation, Inc.
 
 This file is part of GCC.
@@ -16,37 +16,49 @@ 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.  */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
 
 #ifndef GCC_BITMAP_H
 #define GCC_BITMAP_H
+#include "hashtab.h"
 
 /* Fundamental storage type for bitmap.  */
 
-/* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */
-/* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */
 typedef unsigned long BITMAP_WORD;
-#define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG)
-#define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS
+/* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
+   it is used in preprocessor directives -- hence the 1u.  */
+#define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
 
 /* Number of words to use for each element in the linked list.  */
 
 #ifndef BITMAP_ELEMENT_WORDS
-#define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS)
+#define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
 #endif
 
-/* Number of bits in each actual element of a bitmap.  We get slightly better
-   code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
-   bits is unsigned, assuming it is a power of 2.  */
+/* Number of bits in each actual element of a bitmap.  */
 
-#define BITMAP_ELEMENT_ALL_BITS \
-  ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS))
+#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
+
+/* Obstack for allocating bitmaps and elements from.  */
+typedef struct bitmap_obstack GTY (())
+{
+  struct bitmap_element_def *elements;
+  struct bitmap_head_def *heads;
+  struct obstack GTY ((skip)) obstack;
+} bitmap_obstack;
 
 /* Bitmap set element.  We use a linked list to hold only the bits that
    are set.  This allows for use to grow the bitset dynamically without
-   having to realloc and copy a giant bit array.  The `prev' field is
-   undefined for an element on the free list.  */
+   having to realloc and copy a giant bit array.
+
+   The free list is implemented as a list of lists.  There is one
+   outer list connected together by prev fields.  Each element of that
+   outer is an inner list (that may consist only of the outer list
+   element) that are connected by the next fields.  The prev pointer
+   is undefined for interior elements.  This allows
+   bitmap_elt_clear_from to be implemented in unit time rather than
+   linear in the number of elements to be freed.  */
 
 typedef struct bitmap_element_def GTY(())
 {
@@ -61,22 +73,14 @@ typedef struct bitmap_head_def GTY(()) {
   bitmap_element *first;	/* First element in linked list.  */
   bitmap_element *current;	/* Last element looked at.  */
   unsigned int indx;		/* Index of last element looked at.  */
-  int using_obstack;		/* Are we using an obstack or ggc for
-                                   allocation?  */
+  bitmap_obstack *obstack;	/* Obstack to allocate elements from.
+				   If NULL, then use ggc_alloc.  */
 } bitmap_head;
-typedef struct bitmap_head_def *bitmap;
 
-/* Enumeration giving the various operations we support.  */
-enum bitmap_bits {
-  BITMAP_AND,			/* TO = FROM1 & FROM2 */
-  BITMAP_AND_COMPL,		/* TO = FROM1 & ~ FROM2 */
-  BITMAP_IOR,			/* TO = FROM1 | FROM2 */
-  BITMAP_XOR,			/* TO = FROM1 ^ FROM2 */
-  BITMAP_IOR_COMPL			/* TO = FROM1 | ~FROM2 */
-};
 
 /* Global data */
 extern bitmap_element bitmap_zero_bits;	/* Zero bitmap element */
+extern bitmap_obstack bitmap_default_obstack;   /* Default bitmap obstack */
 
 /* Clear a bitmap by freeing up the linked list.  */
 extern void bitmap_clear (bitmap);
@@ -85,14 +89,41 @@ extern void bitmap_clear (bitmap);
 extern void bitmap_copy (bitmap, bitmap);
 
 /* True if two bitmaps are identical.  */
-extern int bitmap_equal_p (bitmap, bitmap);
-
-/* Perform an operation on two bitmaps, yielding a third.  */
-extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits);
-
-/* `or' into one bitmap the `and' of a second bitmap witih the complement
-   of a third.  */
-extern void bitmap_ior_and_compl (bitmap, bitmap, bitmap);
+extern bool bitmap_equal_p (bitmap, bitmap);
+
+/* True if the bitmaps intersect (their AND is non-empty).  */
+extern bool bitmap_intersect_p (bitmap, bitmap);
+
+/* True if the complement of the second intersects the first (their
+   AND_COMPL is non-empty).  */
+extern bool bitmap_intersect_compl_p (bitmap, bitmap);
+
+/* True if MAP is an empty bitmap.  */
+#define bitmap_empty_p(MAP) (!(MAP)->first)
+
+/* Count the number of bits set in the bitmap.  */
+extern unsigned long bitmap_count_bits (bitmap);
+
+/* Boolean operations on bitmaps.  The _into variants are two operand
+   versions that modify the first source operand.  The other variants
+   are three operand versions that to not destroy the source bitmaps.
+   The operations supported are &, & ~, |, ^.  */
+extern void bitmap_and (bitmap, bitmap, bitmap);
+extern void bitmap_and_into (bitmap, bitmap);
+extern void bitmap_and_compl (bitmap, bitmap, bitmap);
+extern bool bitmap_and_compl_into (bitmap, bitmap);
+#define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
+extern void bitmap_compl_and_into (bitmap, bitmap);
+extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
+extern bool bitmap_ior (bitmap, bitmap, bitmap);
+extern bool bitmap_ior_into (bitmap, bitmap);
+extern void bitmap_xor (bitmap, bitmap, bitmap);
+extern void bitmap_xor_into (bitmap, bitmap);
+
+/* DST = A | (B & ~C).  Return true if DST changes.  */
+extern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C);
+/* A |= (B & ~C).  Return true if A changes.  */
+extern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C);
 
 /* Clear a single register in a register set.  */
 extern void bitmap_clear_bit (bitmap, int);
@@ -110,246 +141,428 @@ extern void debug_bitmap_file (FILE *, bitmap);
 /* Print a bitmap.  */
 extern void bitmap_print (FILE *, bitmap, const char *, const char *);
 
-/* Initialize a bitmap header.  If HEAD is NULL, a new header will be
-   allocated.  USING_OBSTACK indicates how elements should be allocated.  */
-extern bitmap bitmap_initialize (bitmap head, int using_obstack);
+/* Initialize and release a bitmap obstack.  */
+extern void bitmap_obstack_initialize (bitmap_obstack *);
+extern void bitmap_obstack_release (bitmap_obstack *);
+
+/* Initialize a bitmap header.  OBSTACK indicates the bitmap obstack
+   to allocate from, NULL for GC'd bitmap.  */
 
-/* Release all memory used by the bitmap obstack.  */
-extern void bitmap_release_memory (void);
+static inline void
+bitmap_initialize (bitmap head, bitmap_obstack *obstack)
+{
+  head->first = head->current = NULL;
+  head->obstack = obstack;
+}
+
+/* Allocate and free bitmaps from obstack, malloc and gc'd memory.  */
+extern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack);
+extern bitmap bitmap_gc_alloc (void);
+extern void bitmap_obstack_free (bitmap);
 
 /* A few compatibility/functions macros for compatibility with sbitmaps */
 #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
 #define bitmap_zero(a) bitmap_clear (a)
-#define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR)
-#define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND)
-extern int bitmap_union_of_diff (bitmap, bitmap, bitmap, bitmap);
-extern int bitmap_first_set_bit (bitmap);
-extern int bitmap_last_set_bit (bitmap);
+extern unsigned bitmap_first_set_bit (bitmap);
 
-/* Allocate a bitmap with oballoc.  */
-#define BITMAP_OBSTACK_ALLOC(OBSTACK)				\
-  bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1)
+/* Compute bitmap hash (for purposes of hashing etc.)  */
+extern hashval_t bitmap_hash(bitmap);
 
-/* Allocate a bitmap with ggc_alloc.  */
-#define BITMAP_GGC_ALLOC()			\
-  bitmap_initialize (NULL, 0)
+/* Allocate a bitmap from a bit obstack.  */
+#define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
 
-/* Allocate a bitmap with xmalloc.  */
-#define BITMAP_XMALLOC()                                        \
-  bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1)
+/* Allocate a gc'd bitmap.  */
+#define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
 
 /* Do any cleanup needed on a bitmap when it is no longer used.  */
 #define BITMAP_FREE(BITMAP)			\
-do {						\
-  if (BITMAP)					\
-    {						\
-      bitmap_clear (BITMAP);			\
-      (BITMAP) = 0;				\
-    }						\
-} while (0)
-
-/* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
-#define BITMAP_XFREE(BITMAP)			\
-do {						\
-  if (BITMAP)					\
-    {						\
-      bitmap_clear (BITMAP);			\
-      free (BITMAP);				\
-      (BITMAP) = 0;				\
-    }						\
-} while (0)
-
-/* Do any one-time initializations needed for bitmaps.  */
-#define BITMAP_INIT_ONCE()
-
-/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
-   bit number and executing CODE for all bits that are set.  */
-
-#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)		\
-do {									\
-  bitmap_element *ptr_ = (BITMAP)->first;				\
-  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
-  unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS;				\
-  unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;	\
-									\
-									\
-  /* Find the block the minimum bit is in.  */				\
-  while (ptr_ != 0 && ptr_->indx < indx_)				\
-    ptr_ = ptr_->next;							\
-									\
-  if (ptr_ != 0 && ptr_->indx != indx_)					\
-    {									\
-      bit_num_ = 0;							\
-      word_num_ = 0;							\
-    }									\
-									\
-  for (; ptr_ != 0; ptr_ = ptr_->next)					\
-    {									\
-      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
-	{								\
-	  BITMAP_WORD word_ = ptr_->bits[word_num_];			\
-									\
-	  if (word_ != 0)						\
-	    {								\
-	      for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++)		\
-		{							\
-		  BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_;	\
-									\
-		  if ((word_ & mask_) != 0)				\
-		    {							\
-		      word_ &= ~ mask_;					\
-		      (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
-				  + word_num_ * BITMAP_WORD_BITS	\
-				  + bit_num_);				\
-		      CODE;						\
-									\
-		      if (word_ == 0)					\
-			break;						\
-		    }							\
-		}							\
-	    }								\
-									\
-	  bit_num_ = 0;							\
-	}								\
-									\
-      word_num_ = 0;							\
-    }									\
-} while (0)
-
-/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
-   BITNUM to the bit number and executing CODE for all bits that are set in
-   the first bitmap and not set in the second.  */
-
-#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
-do {									\
-  bitmap_element *ptr1_ = (BITMAP1)->first;				\
-  bitmap_element *ptr2_ = (BITMAP2)->first;				\
-  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
-  unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS;				\
-  unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;	\
-									\
-  /* Find the block the minimum bit is in in the first bitmap.  */	\
-  while (ptr1_ != 0 && ptr1_->indx < indx_)				\
-    ptr1_ = ptr1_->next;						\
-									\
-  if (ptr1_ != 0 && ptr1_->indx != indx_)				\
-    {									\
-      bit_num_ = 0;							\
-      word_num_ = 0;							\
-    }									\
-									\
-  for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)				\
-    {									\
-      /* Advance BITMAP2 to the equivalent link, using an all		\
-	 zero element if an equivalent link doesn't exist.  */		\
-      bitmap_element *tmp2_;						\
-									\
-      while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)			\
-	ptr2_ = ptr2_->next;						\
-									\
-      tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)		\
-	       ? ptr2_ : &bitmap_zero_bits);				\
-									\
-      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
-	{								\
-	  BITMAP_WORD word_ = (ptr1_->bits[word_num_]			\
-			       & ~ tmp2_->bits[word_num_]);		\
-	  if (word_ != 0)						\
-	    {								\
-	      for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++)		\
-		{							\
-		  BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_;	\
-									\
-		  if ((word_ & mask_) != 0)				\
-		    {							\
-		      word_ &= ~ mask_;					\
-		      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
-				  + word_num_ * BITMAP_WORD_BITS	\
-				  + bit_num_);				\
-									\
-		      CODE;						\
-		      if (word_ == 0)					\
-			break;						\
-		    }							\
-		}							\
-	    }								\
-									\
-	  bit_num_ = 0;							\
-	}								\
-									\
-      word_num_ = 0;							\
-    }									\
-} while (0)
-
-/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
-   BITNUM to the bit number and executing CODE for all bits that are set in
-   the both bitmaps.  */
-
-#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)	\
-do {									\
-  bitmap_element *ptr1_ = (BITMAP1)->first;				\
-  bitmap_element *ptr2_ = (BITMAP2)->first;				\
-  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
-  unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS;				\
-  unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;	\
-									\
-  /* Find the block the minimum bit is in in the first bitmap.  */	\
-  while (ptr1_ != 0 && ptr1_->indx < indx_)				\
-    ptr1_ = ptr1_->next;						\
-									\
-  if (ptr1_ != 0 && ptr1_->indx != indx_)				\
-    {									\
-      bit_num_ = 0;							\
-      word_num_ = 0;							\
-    }									\
-									\
-  for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)				\
-    {									\
-      /* Advance BITMAP2 to the equivalent link.  */			\
-      while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)			\
-	ptr2_ = ptr2_->next;						\
-									\
-      if (ptr2_ == 0)							\
-	{								\
-	  /* If there are no more elements in BITMAP2, exit loop now.  */ \
-	  ptr1_ = (bitmap_element *)0;					\
-	  break;							\
-	}								\
-      else if (ptr2_->indx > ptr1_->indx)				\
-	{								\
-	  bit_num_ = word_num_ = 0;					\
-	  continue;							\
-	}								\
-									\
-      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
-	{								\
-	  BITMAP_WORD word_ = (ptr1_->bits[word_num_]			\
-			       & ptr2_->bits[word_num_]);		\
-	  if (word_ != 0)						\
-	    {								\
-	      for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++)		\
-		{							\
-		  BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_;	\
-									\
-		  if ((word_ & mask_) != 0)				\
-		    {							\
-		      word_ &= ~ mask_;					\
-		      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
-				  + word_num_ * BITMAP_WORD_BITS	\
-				  + bit_num_);				\
-									\
-		      CODE;						\
-		      if (word_ == 0)					\
-			break;						\
-		    }							\
-		}							\
-	    }								\
-									\
-	  bit_num_ = 0;							\
-	}								\
-									\
-      word_num_ = 0;							\
-    }									\
-} while (0)
+	((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
+
+/* Iterator for bitmaps.  */
+
+typedef struct
+{
+  /* Pointer to the current bitmap element.  */
+  bitmap_element *elt1;
+
+  /* Pointer to 2nd bitmap element when two are involved.  */
+  bitmap_element *elt2;
+
+  /* Word within the current element.  */
+  unsigned word_no;
+
+  /* Contents of the actually processed word.  When finding next bit
+     it is shifted right, so that the actual bit is always the least
+     significant bit of ACTUAL.  */
+  BITMAP_WORD bits;
+} bitmap_iterator;
+
+/* Initialize a single bitmap iterator.  START_BIT is the first bit to
+   iterate from.  */
+
+static inline void
+bmp_iter_set_init (bitmap_iterator *bi, bitmap map,
+		   unsigned start_bit, unsigned *bit_no)
+{
+  bi->elt1 = map->first;
+  bi->elt2 = NULL;
+
+  /* Advance elt1 until it is not before the block containing start_bit.  */
+  while (1)
+    {
+      if (!bi->elt1)
+	{
+	  bi->elt1 = &bitmap_zero_bits;
+	  break;
+	}
+
+      if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
+	break;
+      bi->elt1 = bi->elt1->next;
+    }
+
+  /* We might have gone past the start bit, so reinitialize it.  */
+  if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
+    start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
+
+  /* Initialize for what is now start_bit.  */
+  bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
+  bi->bits = bi->elt1->bits[bi->word_no];
+  bi->bits >>= start_bit % BITMAP_WORD_BITS;
+
+  /* If this word is zero, we must make sure we're not pointing at the
+     first bit, otherwise our incrementing to the next word boundary
+     will fail.  It won't matter if this increment moves us into the
+     next word.  */
+  start_bit += !bi->bits;
+
+  *bit_no = start_bit;
+}
+
+/* Initialize an iterator to iterate over the intersection of two
+   bitmaps.  START_BIT is the bit to commence from.  */
+
+static inline void
+bmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
+		   unsigned start_bit, unsigned *bit_no)
+{
+  bi->elt1 = map1->first;
+  bi->elt2 = map2->first;
+
+  /* Advance elt1 until it is not before the block containing
+     start_bit.  */
+  while (1)
+    {
+      if (!bi->elt1)
+	{
+	  bi->elt2 = NULL;
+	  break;
+	}
+
+      if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
+	break;
+      bi->elt1 = bi->elt1->next;
+    }
+
+  /* Advance elt2 until it is not before elt1.  */
+  while (1)
+    {
+      if (!bi->elt2)
+	{
+	  bi->elt1 = bi->elt2 = &bitmap_zero_bits;
+	  break;
+	}
+
+      if (bi->elt2->indx >= bi->elt1->indx)
+	break;
+      bi->elt2 = bi->elt2->next;
+    }
+
+  /* If we're at the same index, then we have some intersecting bits.  */
+  if (bi->elt1->indx == bi->elt2->indx)
+    {
+      /* We might have advanced beyond the start_bit, so reinitialize
+	 for that.  */
+      if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
+	start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
+
+      bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
+      bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
+      bi->bits >>= start_bit % BITMAP_WORD_BITS;
+    }
+  else
+    {
+      /* Otherwise we must immediately advance elt1, so initialize for
+	 that.  */
+      bi->word_no = BITMAP_ELEMENT_WORDS - 1;
+      bi->bits = 0;
+    }
+
+  /* If this word is zero, we must make sure we're not pointing at the
+     first bit, otherwise our incrementing to the next word boundary
+     will fail.  It won't matter if this increment moves us into the
+     next word.  */
+  start_bit += !bi->bits;
+
+  *bit_no = start_bit;
+}
+
+/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
+   */
+
+static inline void
+bmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
+			 unsigned start_bit, unsigned *bit_no)
+{
+  bi->elt1 = map1->first;
+  bi->elt2 = map2->first;
+
+  /* Advance elt1 until it is not before the block containing start_bit.  */
+  while (1)
+    {
+      if (!bi->elt1)
+	{
+	  bi->elt1 = &bitmap_zero_bits;
+	  break;
+	}
+
+      if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
+	break;
+      bi->elt1 = bi->elt1->next;
+    }
+
+  /* Advance elt2 until it is not before elt1.  */
+  while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
+    bi->elt2 = bi->elt2->next;
+
+  /* We might have advanced beyond the start_bit, so reinitialize for
+     that.  */
+  if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
+    start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
+
+  bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
+  bi->bits = bi->elt1->bits[bi->word_no];
+  if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
+    bi->bits &= ~bi->elt2->bits[bi->word_no];
+  bi->bits >>= start_bit % BITMAP_WORD_BITS;
+
+  /* If this word is zero, we must make sure we're not pointing at the
+     first bit, otherwise our incrementing to the next word boundary
+     will fail.  It won't matter if this increment moves us into the
+     next word.  */
+  start_bit += !bi->bits;
+
+  *bit_no = start_bit;
+}
+
+/* Advance to the next bit in BI.  We don't advance to the next
+   nonzero bit yet.  */
+
+static inline void
+bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
+{
+  bi->bits >>= 1;
+  *bit_no += 1;
+}
+
+/* Advance to the next nonzero bit of a single bitmap, we will have
+   already advanced past the just iterated bit.  Return true if there
+   is a bit to iterate.  */
+
+static inline bool
+bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
+{
+  /* If our current word is nonzero, it contains the bit we want.  */
+  if (bi->bits)
+    {
+    next_bit:
+      while (!(bi->bits & 1))
+	{
+	  bi->bits >>= 1;
+	  *bit_no += 1;
+	}
+      return true;
+    }
+
+  /* Round up to the word boundary.  We might have just iterated past
+     the end of the last word, hence the -1.  It is not possible for
+     bit_no to point at the beginning of the now last word.  */
+  *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
+	     / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
+  bi->word_no++;
+
+  while (1)
+    {
+      /* Find the next nonzero word in this elt.  */
+      while (bi->word_no != BITMAP_ELEMENT_WORDS)
+	{
+	  bi->bits = bi->elt1->bits[bi->word_no];
+	  if (bi->bits)
+	    goto next_bit;
+	  *bit_no += BITMAP_WORD_BITS;
+	  bi->word_no++;
+	}
+
+      /* Advance to the next element.  */
+      bi->elt1 = bi->elt1->next;
+      if (!bi->elt1)
+	return false;
+      *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
+      bi->word_no = 0;
+    }
+}
+
+/* Advance to the next nonzero bit of an intersecting pair of
+   bitmaps.  We will have already advanced past the just iterated bit.
+   Return true if there is a bit to iterate.  */
+
+static inline bool
+bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
+{
+  /* If our current word is nonzero, it contains the bit we want.  */
+  if (bi->bits)
+    {
+    next_bit:
+      while (!(bi->bits & 1))
+	{
+	  bi->bits >>= 1;
+	  *bit_no += 1;
+	}
+      return true;
+    }
+
+  /* Round up to the word boundary.  We might have just iterated past
+     the end of the last word, hence the -1.  It is not possible for
+     bit_no to point at the beginning of the now last word.  */
+  *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
+	     / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
+  bi->word_no++;
+
+  while (1)
+    {
+      /* Find the next nonzero word in this elt.  */
+      while (bi->word_no != BITMAP_ELEMENT_WORDS)
+	{
+	  bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
+	  if (bi->bits)
+	    goto next_bit;
+	  *bit_no += BITMAP_WORD_BITS;
+	  bi->word_no++;
+	}
+
+      /* Advance to the next identical element.  */
+      do
+	{
+	  /* Advance elt1 while it is less than elt2.  We always want
+	     to advance one elt.  */
+	  do
+	    {
+	      bi->elt1 = bi->elt1->next;
+	      if (!bi->elt1)
+		return false;
+	    }
+	  while (bi->elt1->indx < bi->elt2->indx);
+
+	  /* Advance elt2 to be no less than elt1.  This might not
+	     advance.  */
+	  while (bi->elt2->indx < bi->elt1->indx)
+	    {
+	      bi->elt2 = bi->elt2->next;
+	      if (!bi->elt2)
+		return false;
+	    }
+	}
+      while (bi->elt1->indx != bi->elt2->indx);
+
+      *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
+      bi->word_no = 0;
+    }
+}
+
+/* Advance to the next nonzero bit in the intersection of
+   complemented bitmaps.  We will have already advanced past the just
+   iterated bit.  */
+
+static inline bool
+bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
+{
+  /* If our current word is nonzero, it contains the bit we want.  */
+  if (bi->bits)
+    {
+    next_bit:
+      while (!(bi->bits & 1))
+	{
+	  bi->bits >>= 1;
+	  *bit_no += 1;
+	}
+      return true;
+    }
+
+  /* Round up to the word boundary.  We might have just iterated past
+     the end of the last word, hence the -1.  It is not possible for
+     bit_no to point at the beginning of the now last word.  */
+  *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
+	     / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
+  bi->word_no++;
+
+  while (1)
+    {
+      /* Find the next nonzero word in this elt.  */
+      while (bi->word_no != BITMAP_ELEMENT_WORDS)
+	{
+	  bi->bits = bi->elt1->bits[bi->word_no];
+	  if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
+	    bi->bits &= ~bi->elt2->bits[bi->word_no];
+	  if (bi->bits)
+	    goto next_bit;
+	  *bit_no += BITMAP_WORD_BITS;
+	  bi->word_no++;
+	}
+
+      /* Advance to the next element of elt1.  */
+      bi->elt1 = bi->elt1->next;
+      if (!bi->elt1)
+	return false;
+
+      /* Advance elt2 until it is no less than elt1.  */
+      while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
+	bi->elt2 = bi->elt2->next;
+
+      *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
+      bi->word_no = 0;
+    }
+}
+
+/* Loop over all bits set in BITMAP, starting with MIN and setting
+   BITNUM to the bit number.  ITER is a bitmap iterator.  BITNUM
+   should be treated as a read-only variable as it contains loop
+   state.  */
+
+#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)		\
+  for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));		\
+       bmp_iter_set (&(ITER), &(BITNUM));				\
+       bmp_iter_next (&(ITER), &(BITNUM)))
+
+/* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
+   and setting BITNUM to the bit number.  ITER is a bitmap iterator.
+   BITNUM should be treated as a read-only variable as it contains
+   loop state.  */
+
+#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER)	\
+  for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),		\
+			  &(BITNUM));					\
+       bmp_iter_and (&(ITER), &(BITNUM));				\
+       bmp_iter_next (&(ITER), &(BITNUM)))
+
+/* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
+   and setting BITNUM to the bit number.  ITER is a bitmap iterator.
+   BITNUM should be treated as a read-only variable as it contains
+   loop state.  */
+
+#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
+  for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN),	\
+				&(BITNUM));				\
+       bmp_iter_and_compl (&(ITER), &(BITNUM));				\
+       bmp_iter_next (&(ITER), &(BITNUM)))
 
 #endif /* GCC_BITMAP_H */