* lib/bitset-int.h, lib/bitset.c, lib/bitset.h, lib/bitsetv.c,

* lib/bitsetv.h, lib/ebitset.c, lib/ebitset.h, lib/lbitset.c,
* lib/lbitset.h, lib/sbitset.c, lib/sbitset.h: New.
* src/closure.c (fderives): Be an array of bitsets.

12 files changed, 4915 insertions, 0 deletions

diff --git a/lib/Makefile.am b/lib/Makefile.am
index 99ec8c8e..5dfdb11c 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -42,5 +42,10 @@ libbison_a_SOURCES = \
   xalloc.h xmalloc.c xstrdup.c xstrndup.c \
   readpipe.c
 
+# Implementation of bitsets
+libbison_a_SOURCES += \
+	bitset-int.h bitset.h bitsetv.h ebitset.h lbitset.h sbitset.h \
+	bitset.c bitsetv.c ebitset.c lbitset.c sbitset.c
+
 libbison_a_LIBADD = @LIBOBJS@ @ALLOCA@
 libbison_a_DEPENDENCIES = $(libbison_a_LIBADD)
diff --git a/lib/bitset-int.h b/lib/bitset-int.h
new file mode 100644
index 00000000..6c51166f
--- /dev/null
+++ b/lib/bitset-int.h
@@ -0,0 +1,112 @@
+/* Internal bitset definitions.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef _BITSET_INT_H
+#define _BITSET_INT_H
+
+#ifdef HAVE_LIMITS_H
+#include <limits.h>
+#endif
+
+/* Currently we support three flavours of bitsets:
+   BITSET_ARRAY:  Array of bits (fixed size, faster).
+   BITSET_LIST:   Linked list of array of bits (variable size, least storage
+   for large very sparse sets).
+   BITSET_TABLE:  Expandable table of pointers to array of bits
+   (variable size, less storage for large sparse sets).
+*/
+enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_TYPE_NUM};
+#define BITSET__TYPE_NAMES {"sbitset", "lbitset", "ebitset"}
+
+/* Non-zero to enable bitset caching.  */
+#define BITSET_CACHE 1
+
+/* Non-zero to use inline functions instead of macros.  */
+#define BITSET_INLINE 0
+
+/* Non-zero to enable bitset statistics gathering.  */
+#define BITSET_STATS 1
+
+/* Non-zero to enable bitset type checking.  */
+#define BITSET_CHECK 0
+
+typedef unsigned long bitset_word;
+#define BITSET_WORD_BITS ((unsigned) CHAR_BIT * sizeof (bitset_word))
+
+/* Bit index.  */
+typedef unsigned long bitset_bindex;
+
+/* Word index.  */
+typedef unsigned long bitset_windex;
+
+#define BITSET_INDEX_MAX ((1U << (BITSET_WORD_BITS - 1)))
+
+#define BITSET_MSB (1U << (BITSET_WORD_BITS - 1))
+
+#define BITSET_LIST_SIZE 1024
+
+enum bitset_ops {BITSET_ZERO, BITSET_ONES, BITSET_EMPTY_P,
+		 BITSET_COPY, BITSET_EQUAL_P, BITSET_SUBSET_P, BITSET_NOT,
+		 BITSET_AND, BITSET_OR, BITSET_XOR, BITSET_ANDN, BITSET_ORN,
+		 BITSET_OR_AND, BITSET_AND_OR, BITSET_ANDN_OR};
+
+/* Return size in bits of bitset SRC.  */
+#define BITSET__SIZE(SRC) (SRC)->ops->size (SRC)
+
+/* Set bit BITNO in bitset DST.  */
+#define BITSET__SET(DST, BITNO) (DST)->ops->set (DST, BITNO)
+
+/* Reset bit BITNO in bitset DST.  */
+#define BITSET__RESET(DST, BITNO) (DST)->ops->reset (DST, BITNO)
+
+/* Return non-zero if bit BITNO in bitset SRC is set.  */
+#define BITSET__TEST(SRC, BITNO) (SRC)->ops->test (SRC, BITNO)
+
+/* Free bitset SRC.  */
+#define BITSET__FREE(SRC) ((SRC)->ops->free) (SRC)
+
+/* Perform operation OP on DST.  */
+#define BITSET__OP1(DST, OP) (DST)->ops->op1 (DST, OP)
+
+/* Perform operation OP on SRC and store in DST.  */
+#define BITSET__OP2(DST, SRC, OP) (DST)->ops->op2 (DST, SRC, OP)
+
+/* DST = SRC1 OP SRC2.  */
+#define BITSET__OP3(DST, SRC1, SRC2, OP) \
+(DST)->ops->op3 (DST, SRC1, SRC2, OP)
+
+/* DST = (SRC1 OP1 SRC2) OP2 SRC3.  */
+#define BITSET__OP4(DST, SRC1, SRC2, SRC3, OP) \
+(DST)->ops->op4 (DST, SRC1, SRC2, SRC3, OP)
+
+/* DST = SRC.  */
+#define BITSET__COPY(DST, SRC) BITSET__OP2 (DST, SRC, BITSET_COPY)
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT.  Return with actual number of bits found and with *NEXT
+   indicating where search stopped.  */
+#define BITSET__LIST(BSET, LIST, NUM, NEXT) \
+(BSET)->ops->list (BSET, LIST, NUM, NEXT)
+
+/* Find reverse list of up to NUM bits set in BSET starting from and
+   including NEXT.  Return with actual number of bits found and with
+   *NEXT indicating where search stopped.  */
+#define BITSET__REVERSE_LIST(BSET, LIST, NUM, NEXT) \
+(BSET)->ops->reverse_list (BSET, LIST, NUM, NEXT)
+
+#endif /* _BITSET_INT_H  */
diff --git a/lib/bitset.c b/lib/bitset.c
new file mode 100644
index 00000000..c68ed788
--- /dev/null
+++ b/lib/bitset.c
@@ -0,0 +1,835 @@
+/* General bitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdlib.h>
+#include "bitset.h"
+#include "obstack.h"
+
+static void bitset_print PARAMS ((FILE *, bitset, int));
+
+#if BITSET_CHECK
+#define BITSET__CHECK2(DST, SRC) \
+if ((DST)->OPS != (SRC)->OPS) abort ();
+
+#define BITSET__CHECK3(DST, SRC1, SRC2) \
+if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS) abort ();
+
+#define BITSET__CHECK4(DST, SRC1, SRC2) \
+if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS \
+    || (DST)->OPS != (SRC3)->OPS) abort ();
+#else
+#define BITSET__CHECK2(DST, SRC)
+
+#define BITSET__CHECK3(DST, SRC1, SRC2)
+
+#define BITSET__CHECK4(DST, SRC1, SRC2, SRC3)
+#endif
+
+#if BITSET_STATS
+#define BITSET_STATS_FILE "bitset.dat"
+
+#define BITSET_LOG_COUNT_BINS 10
+#define BITSET_LOG_SIZE_BINS  16
+#define BITSET_DENSITY_BINS  20
+
+struct bitset_type_stats_struct
+{
+  unsigned int xmallocs;
+  unsigned int xfrees;
+  unsigned int oballocs;
+  unsigned int obfrees;
+  unsigned int lists;
+  unsigned int list_counts[BITSET_LOG_COUNT_BINS];
+  unsigned int list_sizes[BITSET_LOG_SIZE_BINS];
+  unsigned int list_density[BITSET_DENSITY_BINS];
+};
+
+struct bitset_stats_struct
+{
+    unsigned int runs;
+    struct bitset_type_stats_struct types[BITSET_TYPE_NUM];
+};
+
+struct bitset_stats_struct bitset_stats_data;
+struct bitset_stats_struct *bitset_stats;
+
+static void bitset_percent_histogram_print PARAMS ((FILE *, const char *,
+						    const char *,
+						    unsigned int,
+						    unsigned int *));
+static void bitset_log_histogram_print PARAMS ((FILE *, const char *,
+						const char *,
+						unsigned int, unsigned int *));
+static void bitset_stats_print_1 PARAMS ((FILE *, const char *,
+					  struct bitset_type_stats_struct *));
+static void bitset_stats_print PARAMS ((FILE *, int));
+static void bitset_stats_read PARAMS ((void));
+static void bitset_stats_write PARAMS ((void));
+
+#define BITSET_STATS_XMALLOCS_INC(TYPE) 		\
+  if (bitset_stats)					\
+    bitset_stats->types[(TYPE)].xmallocs++
+
+#define BITSET_STATS_XFREES_INC(BSET) 			\
+  if (bitset_stats)					\
+    bitset_stats->types[(BSET)->ops->type].xfrees++
+
+#define BITSET_STATS_OBALLOCS_INC(TYPE) 		\
+  if (bitset_stats)					\
+    bitset_stats->types[(TYPE)].oballocs++
+
+#define BITSET_STATS_OBFREES_INC(BSET) 		\
+  if (bitset_stats)					\
+    bitset_stats->types[(BSET)->ops->type].obfrees++
+
+#define BITSET_STATS_LISTS_INC(BSET) 			\
+  if (bitset_stats)					\
+    bitset_stats->types[(BSET)->ops->type].lists++
+
+#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) 		\
+  if (bitset_stats)					\
+    bitset_stats->types[(BSET)->ops->type].list_counts[(I)]++
+
+#define BITSET_STATS_LIST_SIZES_INC(BSET, I) 		\
+  if (bitset_stats)					\
+    bitset_stats->types[(BSET)->ops->type].list_sizes[(I)]++
+
+#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) 		\
+  if (bitset_stats)					\
+    bitset_stats->types[(BSET)->ops->type].list_density[(I)]++
+
+#else
+#define BITSET_STATS_XMALLOCS_INC(TYPE)
+
+#define BITSET_STATS_XFREES_INC(BSET)
+
+#define BITSET_STATS_OBALLOCS_INC(TYPE)
+
+#define BITSET_STATS_OBFREES_INC(BSET)
+
+#define BITSET_STATS_LISTS_INC(BSET)
+
+#define BITSET_STATS_LIST_COUNTS_INC(BSET, I)
+
+#define BITSET_STATS_LIST_SIZES_INC(BSET, I)
+
+#define BITSET_STATS_LIST_DENSITY_INC(BSET, I)
+#endif /* BITSET_STATS  */
+
+
+
+/* Return number of bytes required to create a N_BIT bitset
+   of TYPE.  The bitset may grow to require more bytes than this.  */
+int
+bitset_bytes (type, n_bits)
+     enum bitset_type type;
+     bitset_bindex n_bits;
+{
+  unsigned int bytes;
+
+  switch (type)
+    {
+    case BITSET_ARRAY:
+      bytes = sbitset_bytes (n_bits);
+      break;
+
+    case BITSET_LIST:
+      bytes = lbitset_bytes (n_bits);
+      break;
+
+    case BITSET_TABLE:
+      bytes = ebitset_bytes (n_bits);
+      break;
+
+    default:
+      abort ();
+    }
+
+  return bytes;
+}
+
+
+/* Initialise bitset BSET of TYPE for N_BITS.  */
+bitset
+bitset_init (bset, n_bits, type)
+     bitset bset;
+     bitset_bindex n_bits;
+     enum bitset_type type;
+{
+  switch (type)
+    {
+    case BITSET_ARRAY:
+      return sbitset_init (bset, n_bits);
+
+    case BITSET_LIST:
+      return lbitset_init (bset, n_bits);
+
+    case BITSET_TABLE:
+      return ebitset_init (bset, n_bits);
+
+    default:
+      abort ();
+    }
+}
+
+
+/* Select a bitset type for a set of N_BITS and with attribute hints
+   specified by ATTR.  For variable size bitsets, N_BITS is only a
+   hint and may be zero.  */
+enum bitset_type
+bitset_type_choose (n_bits, attr)
+     bitset_bindex n_bits ATTRIBUTE_UNUSED;
+     unsigned int attr;
+{
+  enum bitset_type type;
+
+#ifdef ENABLE_CHECKING
+  /* Check attributes.  */
+  if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
+    abort ();
+  if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
+    abort ();
+
+  /* Note that sometimes we will be asked for a zero length
+     fixed size bitset.  */
+#endif
+
+  /* Choose the type of bitset.  */
+
+  type = BITSET_ARRAY;
+  /* Currently, the simple bitsets do not support a variable size.  */
+  if (attr & BITSET_VARIABLE || attr & BITSET_SPARSE)
+    {
+      type = BITSET_LIST;
+      if (attr & BITSET_DENSE || attr & BITSET_GREEDY)
+	type = BITSET_TABLE;
+    }
+
+  return type;
+}
+
+
+/* Create a bitset of N_BITS of type TYPE.  */
+bitset
+bitset_alloc (n_bits, type)
+     bitset_bindex n_bits;
+     enum bitset_type type;
+{
+  unsigned int bytes;
+  bitset bset;
+
+  BITSET_STATS_XMALLOCS_INC (type);
+
+  bytes = bitset_bytes (type, n_bits);
+
+  bset = (bitset) xmalloc (bytes);
+
+  return bitset_init (bset, n_bits, type);
+}
+
+
+/* Create a bitset of N_BITS of type TYPE.  */
+bitset
+bitset_obstack_alloc (bobstack, n_bits, type)
+    struct obstack *bobstack;
+    bitset_bindex n_bits;
+    enum bitset_type type;
+{
+  unsigned int bytes;
+
+  BITSET_STATS_OBALLOCS_INC (type);
+
+  bytes = bitset_bytes (type, n_bits);
+
+  return bitset_init (obstack_alloc (bobstack, bytes), n_bits, type);
+}
+
+
+/* Create a bitset of N_BITS and with attribute hints specified by
+   ATTR.  */
+bitset
+bitset_create (n_bits, attr)
+     bitset_bindex n_bits;
+     unsigned int attr;
+{
+  enum bitset_type type;
+
+  type = bitset_type_choose (n_bits, attr);
+
+  return bitset_alloc (n_bits, type);
+}
+
+
+/* Free bitset BSET.  */
+void
+bitset_free (bset)
+     bitset bset;
+{
+  BITSET_STATS_XFREES_INC (bset);
+
+  if (bset->ops->free)
+    BITSET__FREE (bset);
+
+  bset->ops = NULL;
+  free (bset);
+}
+
+
+/* Free bitset BSET allocated on obstack.  */
+void
+bitset_obstack_free (bset)
+     bitset bset;
+{
+  BITSET_STATS_OBFREES_INC (bset);
+
+  if (bset->ops->free)
+    BITSET__FREE (bset);
+  bset->ops = NULL;
+}
+
+
+/* Find next bit set in SRC starting from and including BITNO.
+   Return -1 if SRC empty.  */
+int
+bitset_next (src, bitno)
+     bitset src;
+     bitset_bindex bitno;
+{
+  bitset_bindex val;
+  bitset_bindex next = bitno;
+
+  if (!bitset_list (src, &val, 1, &next))
+    return -1;
+  return val;
+}
+
+
+/* Find previous bit set in SRC starting from and including BITNO.
+   Return -1 if SRC empty.  */
+int
+bitset_prev (src, bitno)
+     bitset src;
+     bitset_bindex bitno;
+{
+  bitset_bindex val;
+  bitset_bindex next = bitno;
+
+  if (!bitset_reverse_list (src, &val, 1, &next))
+    return -1;
+  return val;
+}
+
+
+/* Find first set bit.   */
+int
+bitset_first (src)
+     bitset src;
+{
+  return bitset_next (src, 0);
+}
+
+
+/* Find last set bit.   */
+int
+bitset_last (src)
+     bitset src;
+{
+  return bitset_prev (src, 0);
+}
+
+
+static void
+bitset_print (file, bset, verbose)
+     FILE *file;
+     bitset bset;
+     int verbose;
+{
+  unsigned int i, pos;
+
+  if (verbose)
+    fprintf (file, "n_bits = %d, set = {", bitset_size (bset));
+
+  pos = 30;
+  BITSET_EXECUTE (bset, 0, i,
+  {
+    if (pos > 70)
+      {
+	fprintf (file, "\n");
+	pos = 0;
+      }
+
+    fprintf (file, "%d ", i);
+    pos += 1 + (i >= 10) + (i >= 100);
+  });
+
+  if (verbose)
+    fprintf (file, "}\n");
+}
+
+
+int
+bitset_copy (dst, src)
+    bitset dst;
+    bitset src;
+{
+    unsigned int i;
+
+    if (dst->ops == src->ops)
+	return BITSET__COPY (dst, src);
+
+    /* Convert bitset types.  We assume that the DST bitset
+       is large enough to hold the SRC bitset.  */
+    bitset_zero (dst);
+    BITSET_EXECUTE (src, 0, i,
+     {
+       bitset_set (dst, i);
+     });
+
+    return 1;
+}
+
+
+/* Return size in bits of bitset SRC.  */
+int
+bitset_size (src)
+    bitset src;
+{
+    return BITSET__SIZE (src);
+}
+
+
+/* DST = 0.  */
+int
+bitset_zero (dst)
+    bitset dst;
+{
+    return BITSET__OP1 (dst, BITSET_ZERO);
+}
+
+
+/* DST = ~0.  */
+int
+bitset_ones (dst)
+    bitset dst;
+{
+    return BITSET__OP1 (dst, BITSET_ONES);
+}
+
+
+/* Return non-zero if all bits in bitset SRC are reset.  */
+int
+bitset_empty_p (src)
+    bitset src;
+{
+    return BITSET__OP1 (src, BITSET_EMPTY_P);
+}
+
+
+/* Return DST == DST | SRC.  */
+int
+bitset_subset_p (dst, src)
+    bitset dst;
+    bitset src;
+{
+    return BITSET__OP2 (dst, src, BITSET_SUBSET_P);
+}
+
+
+/* Return DST == SRC.  */
+int
+bitset_equal_p (dst, src)
+    bitset dst;
+    bitset src;
+{
+    BITSET__CHECK2 (dst, src);
+    return BITSET__OP2 (dst, src, BITSET_EQUAL_P);
+}
+
+
+/* DST = ~SRC.  */
+int
+bitset_not (dst, src)
+    bitset dst;
+    bitset src;
+{
+    BITSET__CHECK2 (dst, src);
+    return BITSET__OP2 (dst, src, BITSET_NOT);
+}
+
+
+/* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
+int
+bitset_or (dst, src1, src2)
+    bitset dst;
+    bitset src1;
+    bitset src2;
+{
+    BITSET__CHECK3 (dst, src1, src2);
+    return BITSET__OP3 (dst, src1, src2, BITSET_OR);
+}
+
+
+/* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
+int
+bitset_and (dst, src1, src2)
+    bitset dst;
+    bitset src1;
+    bitset src2;
+{
+    BITSET__CHECK3 (dst, src1, src2);
+    return BITSET__OP3 (dst, src1, src2, BITSET_AND);
+}
+
+
+/* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
+int
+bitset_xor (dst, src1, src2)
+    bitset dst;
+    bitset src1;
+    bitset src2;
+{
+    BITSET__CHECK3 (dst, src1, src2);
+    return BITSET__OP3 (dst, src1, src2, BITSET_XOR);
+}
+
+
+/* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
+int
+bitset_andn (dst, src1, src2)
+    bitset dst;
+    bitset src1;
+    bitset src2;
+{
+    BITSET__CHECK3 (dst, src1, src2);
+    return BITSET__OP3 (dst, src1, src2, BITSET_ANDN);
+}
+
+
+/* DST = SRC1 | ~SRC2.  Return non-zero if DST != SRC1 | ~SRC2.  */
+int
+bitset_orn (dst, src1, src2)
+    bitset dst;
+    bitset src1;
+    bitset src2;
+{
+    BITSET__CHECK3 (dst, src1, src2);
+    return BITSET__OP3 (dst, src1, src2, BITSET_ORN);
+}
+
+
+/* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
+   DST != (SRC1 | SRC2) & SRC3.  */
+int
+bitset_or_and (dst, src1, src2, src3)
+    bitset dst;
+    bitset src1;
+    bitset src2;
+    bitset src3;
+{
+    BITSET__CHECK4 (dst, src1, src2, src3);
+    return BITSET__OP4 (dst, src1, src2, src3, BITSET_OR_AND);
+}
+
+
+/* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
+   DST != (SRC1 & SRC2) | SRC3.  */
+int
+bitset_and_or (dst, src1, src2, src3)
+    bitset dst;
+    bitset src1;
+    bitset src2;
+    bitset src3;
+{
+    BITSET__CHECK4 (dst, src1, src2, src3);
+    return BITSET__OP4 (dst, src1, src2, src3, BITSET_AND_OR);
+}
+
+
+/* Dump bitset BSET to FILE.  */
+void
+bitset_dump (file, bset)
+     FILE *file;
+     bitset bset;
+{
+  bitset_print (file, bset, 0);
+}
+
+
+/* Function to be called from debugger to print bitset.  */
+void
+debug_bitset (bset)
+     bitset bset;
+{
+  bitset_print (stderr, bset, 1);
+}
+
+
+/* Release memory associated with bitsets.  */
+void
+bitset_release_memory ()
+{
+  lbitset_release_memory ();
+  ebitset_release_memory ();
+}
+
+
+#if BITSET_STATS
+int
+bitset_list (bset, list, num, next)
+    bitset bset;
+    bitset_bindex *list;
+    bitset_bindex num;
+    bitset_bindex *next;
+{
+    bitset_bindex count;
+
+    count = BITSET__LIST (bset, list, num, next);
+
+    if (bitset_stats)
+      {
+	bitset_bindex tmp;
+	bitset_bindex size;
+	bitset_bindex i;
+	enum bitset_type type;
+
+	type = bset->ops->type;
+	BITSET_STATS_LISTS_INC (bset);
+
+	/* Log histogram of number of set bits.  */
+	for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
+	  continue;
+	if (i >= BITSET_LOG_COUNT_BINS)
+	  i = BITSET_LOG_COUNT_BINS - 1;
+	BITSET_STATS_LIST_COUNTS_INC (bset, i);
+
+	/* Log histogram of number of bits in set.  */
+	size = bitset_size (bset);
+	for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
+	  continue;
+	if (i >= BITSET_LOG_SIZE_BINS)
+	  i = BITSET_LOG_SIZE_BINS - 1;
+	BITSET_STATS_LIST_SIZES_INC (bset, i);
+
+	/* Histogram of fraction of bits set.  */
+	i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
+	if (i >= BITSET_DENSITY_BINS)
+	  i = BITSET_DENSITY_BINS - 1;
+	BITSET_STATS_LIST_DENSITY_INC (bset, i);
+      }
+    return count;
+}
+
+
+/* Print a percentage histogram with message MSG to FILE.  */
+static void
+bitset_percent_histogram_print (file, name, msg, n_bins, bins)
+     FILE *file;
+     const char *name;
+     const char *msg;
+     unsigned int n_bins;
+     unsigned int *bins;
+{
+  unsigned int i;
+  unsigned int total;
+
+  total = 0;
+  for (i = 0; i < n_bins; i++)
+    total += bins[i];
+
+  if (!total)
+      return;
+
+  fprintf (file, "%s %s", name, msg);
+  for (i = 0; i < n_bins; i++)
+    fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n",
+	     i * 100.0 / n_bins,
+	     (i + 1) * 100.0 / n_bins,
+	     bins[i], (100.0 * bins[i]) / total);
+}
+
+
+/* Print a log histogram with message MSG to FILE.  */
+static void
+bitset_log_histogram_print (file, name, msg, n_bins, bins)
+     FILE *file;
+     const char *name;
+     const char *msg;
+     unsigned int n_bins;
+     unsigned int *bins;
+{
+  unsigned int i;
+  unsigned int total;
+  unsigned int max_width;
+
+  total = 0;
+  for (i = 0; i < n_bins; i++)
+    total += bins[i];
+
+  if (!total)
+      return;
+
+  /* 2 * ceil (log10(2) * (N - 1)) + 1  */
+  max_width = 2 * (unsigned int)(0.30103 * (n_bins - 1) + 0.9999) + 1;
+
+  fprintf (file, "%s %s", name, msg);
+  for (i = 0; i < 2; i++)
+    fprintf (file, "%*d\t%8d (%5.1f%%)\n",
+	     max_width, i, bins[i], 100.0 * bins[i] / total);
+
+  /* Perhaps we should bail out once the histogram goes to zero.  */
+  for (; i < n_bins; i++)
+    fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n",
+	     max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
+	     1 << (i - 1), (1 << i) - 1, bins[i], (100.0 * bins[i]) / total);
+}
+
+
+/* Print bitset statistics to FILE.  */
+static void
+bitset_stats_print_1 (file, name, stats)
+     FILE *file;
+     const char *name;
+     struct bitset_type_stats_struct *stats;
+{
+  if (!stats)
+    return;
+
+  fprintf (file, "%d %ss xmalloced, %d freed.\n",
+	   stats->xmallocs, name, stats->xfrees);
+  fprintf (file, "%d %ss oballoced, %d freed.\n",
+	   stats->oballocs, name, stats->obfrees);
+
+  fprintf (file, "%d bitset_lists\n", stats->lists);
+
+  bitset_log_histogram_print (file, name, "count log histogram\n",
+	   BITSET_LOG_COUNT_BINS, stats->list_counts);
+
+  bitset_log_histogram_print (file, name, "size log histogram\n",
+	   BITSET_LOG_SIZE_BINS, stats->list_sizes);
+
+  bitset_percent_histogram_print (file, name, "density histogram\n",
+				  BITSET_DENSITY_BINS, stats->list_density);
+}
+
+
+/* Print all bitset statistics to FILE.  */
+static void
+bitset_stats_print (file, verbose)
+     FILE *file;
+     int verbose ATTRIBUTE_UNUSED;
+{
+  int i;
+  static const char *names[] = BITSET__TYPE_NAMES;
+
+  if (!bitset_stats)
+    return;
+
+  fprintf (file, "Bitset statistics:\n\n");
+
+  if (bitset_stats->runs > 1)
+    fprintf (file, "Accumulated runs = %d\n", bitset_stats->runs);
+
+  for (i = 0; i < BITSET_TYPE_NUM; i++)
+      bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]);
+}
+#endif /* BITSET_STATS  */
+
+
+/* Initialise bitset statistics logging.  */
+void
+bitset_stats_init ()
+{
+#if BITSET_STATS
+    bitset_stats = &bitset_stats_data;
+    bitset_stats_read ();
+#endif  /* BITSET_STATS  */
+}
+
+
+/* Read bitset statistics file.  */
+static void
+bitset_stats_read ()
+{
+    FILE *file;
+
+    if (!bitset_stats)
+      return;
+
+    file = fopen (BITSET_STATS_FILE, "r");
+    if (file)
+      {
+	if (fread (&bitset_stats_data, sizeof (bitset_stats_data),
+		   1, file) != 1)
+	  {
+	    if (ferror (file))
+	      perror ("Could not read stats file");
+	    else
+	      fprintf (stderr, "Bad stats file size\n");
+	  }
+	fclose (file);
+      }
+    bitset_stats_data.runs++;
+}
+
+
+/* Write bitset statistics file.  */
+static void
+bitset_stats_write ()
+{
+    FILE *file;
+
+    if (!bitset_stats)
+      return;
+
+    file = fopen (BITSET_STATS_FILE, "w");
+    if (file)
+      {
+	if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data),
+		    1, file) != 1)
+	  perror ("Could not write stats file");
+	fclose (file);
+      }
+    else
+      perror ("Could not open stats file for writing");
+}
+
+
+/* Dump bitset statistics to FILE.  */
+void
+bitset_stats_dump (file)
+     FILE *file;
+{
+#if BITSET_STATS
+  bitset_stats_print (file, 0);
+  bitset_stats_write ();
+#endif /* BITSET_STATS  */
+}
+
+
+/* Function to be called from debugger to print bitset stats.  */
+void
+debug_bitset_stats (void)
+{
+#if BITSET_STATS
+  bitset_stats_print (stderr, 1);
+#endif /* BITSET_STATS  */
+}
diff --git a/lib/bitset.h b/lib/bitset.h
new file mode 100644
index 00000000..4afbbf4f
--- /dev/null
+++ b/lib/bitset.h
@@ -0,0 +1,395 @@
+/* Generic bitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef _BITSET_H
+#define _BITSET_H
+
+#if HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#define BITSET_STATS 1
+
+# ifndef PARAMS
+#  if defined PROTOTYPES || (defined __STDC__ && __STDC__)
+#   define PARAMS(Args) Args
+#  else
+#   define PARAMS(Args) ()
+#  endif
+# endif
+
+# ifndef __attribute__
+#  if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
+#   define __attribute__(x)
+#  endif
+# endif
+
+# ifndef ATTRIBUTE_NORETURN
+#  define ATTRIBUTE_NORETURN __attribute__ ((__noreturn__))
+# endif
+
+# ifndef ATTRIBUTE_UNUSED
+#  define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
+# endif
+
+#include "bitset-int.h"
+#include "sbitset.h"
+#include "lbitset.h"
+#include "ebitset.h"
+#include "obstack.h"
+#include <stdio.h>
+#include "xalloc.h"
+
+enum bitset_attr {BITSET_FIXED = 1,    /* Bitset size fixed.  */
+		  BITSET_VARIABLE = 2, /* Bitset size variable.  */
+		  BITSET_DENSE = 4,    /* Bitset dense.  */
+		  BITSET_SPARSE = 8,   /* Bitset sparse.  */
+		  BITSET_FRUGAL = 16,  /* Prefer most compact.  */
+		  BITSET_GREEDY = 32}; /* Prefer fastest.  */
+
+typedef unsigned int bitset_attrs;
+
+/* The elements of these structures should be considered
+   to be private.  */
+typedef struct bitset_struct
+{
+  struct bitset_ops_struct *ops;
+  bitset_windex cindex;		/* Cache word index.  */
+  bitset_windex csize;		/* Cache size in words.  */
+  bitset_word *cdata;		/* Cache data pointer.  */
+  union bitset_data
+  {
+    struct sbitset_struct s;
+    struct lbitset_struct l;
+    struct ebitset_struct e;
+  } u;
+} *bitset;
+
+
+/* The contents of this structure should be considered private.  */
+struct bitset_ops_struct
+{
+  void (*set) PARAMS ((struct bitset_struct *, bitset_bindex));
+  void (*reset) PARAMS ((struct bitset_struct *, bitset_bindex));
+  int (*test) PARAMS ((struct bitset_struct *, bitset_bindex));
+  int (*size) PARAMS ((struct bitset_struct *));
+  int (*op1) PARAMS ((struct bitset_struct *, enum bitset_ops));
+  int (*op2) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+		      enum bitset_ops));
+  int (*op3) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+		      struct bitset_struct *, enum bitset_ops));
+  int (*op4) PARAMS ((struct bitset_struct *, struct bitset_struct *,
+		      struct bitset_struct *, struct bitset_struct *,
+		      enum bitset_ops));
+  int (*list) PARAMS ((struct bitset_struct *, bitset_bindex *,
+		       bitset_bindex, bitset_bindex *));
+  int (*reverse_list) PARAMS ((struct bitset_struct *, bitset_bindex *,
+			       bitset_bindex, bitset_bindex *));
+  void (*free) PARAMS ((struct bitset_struct *));
+  enum bitset_type type;
+};
+
+
+/* Return bytes required for bitset of desired type and size.  */
+extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
+
+/* Initialise a bitset with desired type and size.  */
+extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
+
+extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
+						    bitset_attrs));
+
+/* Create a bitset of desired type and size.  */
+extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
+
+/* Free bitset.  */
+extern void bitset_free PARAMS ((bitset));
+
+/* Create a bitset of desired type and size using obstack.  */
+extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
+					    bitset_bindex, enum bitset_type));
+
+/* Free bitset allocated on obstack.  */
+extern void bitset_obstack_free PARAMS ((bitset));
+
+/* Create a bitset of desired size and attributes.  */
+extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
+
+/* Return size in bits of bitset SRC.  */
+extern int bitset_size PARAMS ((bitset));
+
+#if BITSET_CACHE && BITSET_INLINE
+static inline void bitset_set PARAMS ((bitset, bitset_bindex));
+static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
+static inline int bitset_test PARAMS ((bitset, bitset_bindex));
+
+/* Set bit BITNO in bitset BSET.  */
+static inline void bitset_set (bset, bitno)
+    bitset bset;
+    bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = index - bset->cindex;
+
+  if (offset < bset->csize)
+    bset->cdata[offset] |= (1 << (bitno % BITSET_WORD_BITS));
+  else
+    BITSET__SET (bset, bitno);
+}
+
+
+/* Reset bit BITNO in bitset BSET.  */
+static inline void bitset_reset (bset, bitno)
+    bitset bset;
+    bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = index - bset->cindex;
+
+  if (offset < bset->csize)
+    bset->cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
+  else
+    BITSET__RESET (bset, bitno);
+}
+
+
+/* Test bit BITNO in bitset BSET.  */
+static inline int bitset_test (bset, bitno)
+    bitset bset;
+    bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = index - bset->cindex;
+
+  if (offset < bset->csize)
+    return (bset->cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
+  else
+    return BITSET__TEST (bset, bitno);
+}
+#endif
+
+#if BITSET_CACHE && ! BITSET_INLINE
+
+/* Set bit BITNO in bitset BSET.  */
+#define bitset_set(bset, bitno)					\
+do   								\
+{    								\
+  bitset_bindex _bitno = (bitno);				\
+  bitset_windex _index = _bitno / BITSET_WORD_BITS; 		\
+  bitset_windex _offset = _index - (bset)->cindex;		\
+  								\
+  if (_offset < (bset)->csize)					\
+    (bset)->cdata[_offset] |= (1 << (_bitno % BITSET_WORD_BITS)); 	\
+  else  							\
+    BITSET__SET ((bset), _bitno);				\
+} while (0)
+
+
+/* Reset bit BITNO in bitset BSET.  */
+#define bitset_reset(bset, bitno)				\
+do   								\
+{    								\
+  bitset_bindex _bitno = (bitno);				\
+  bitset_windex _index = _bitno / BITSET_WORD_BITS; 		\
+  bitset_windex _offset = _index - (bset)->cindex;		\
+  								\
+  if (_offset < (bset)->csize)					\
+    (bset)->cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); 	\
+  else  							\
+    BITSET__RESET ((bset), _bitno);				\
+} while (0)
+
+
+/* Test bit BITNO in bitset BSET.  */
+#define bitset_test(bset, bitno) \
+(((((bitno) / BITSET_WORD_BITS) - (bset)->cindex) < (bset)->csize) \
+  ? ((bset)->cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->cindex)] \
+     >> ((bitno) % BITSET_WORD_BITS)) & 1 \
+  : (unsigned int) BITSET__TEST ((bset), (bitno)))
+#endif
+
+#if ! BITSET_CACHE
+/* Set bit BITNO in bitset SRC.  */
+#define bitset_set(SRC, BITNO) BITSET__SET (SRC, BITNO)
+
+/* Reset bit BITNO in bitset SRC.  */
+#define bitset_reset(SRC, BITNO) BITSET__RESET (SRC, BITNO)
+
+/* Return non-zero if bit BITNO in bitset SRC is set.  */
+#define bitset_test(SRC, BITNO) BITSET__TEST (SRC, BITNO)
+#endif
+
+/* DST = 0.  */
+extern int bitset_zero PARAMS ((bitset));
+
+/* DST = ~0.  */
+extern int bitset_ones PARAMS ((bitset));
+
+/* Return non-zero if all bits in bitset SRC are reset.  */
+extern int bitset_empty_p PARAMS ((bitset));
+
+/* Return DST == DST | SRC.  */
+extern int bitset_subset_p PARAMS ((bitset, bitset));
+
+/* Return DST == SRC.  */
+extern int bitset_equal_p PARAMS ((bitset, bitset));
+
+/* DST == SRC.  */
+extern int bitset_copy PARAMS ((bitset, bitset));
+
+/* DST = ~SRC.  */
+extern int bitset_not PARAMS ((bitset, bitset));
+
+/* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
+extern int bitset_or PARAMS ((bitset, bitset, bitset));
+
+/* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
+extern int bitset_and PARAMS ((bitset, bitset, bitset));
+
+/* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
+extern int bitset_xor PARAMS ((bitset, bitset, bitset));
+
+/* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
+extern int bitset_andn PARAMS ((bitset, bitset, bitset));
+
+/* DST = SRC1 | ~SRC2.  Return non-zero if DST != SRC1 | ~SRC2.  */
+extern int bitset_orn PARAMS ((bitset, bitset, bitset));
+
+/* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
+   DST != (SRC1 | SRC2) & SRC3.  */
+extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
+
+/* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
+   DST != (SRC1 & SRC2) | SRC3.  */
+extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
+
+/* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
+   DST != (SRC1 & ~SRC2) | SRC3.  */
+#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
+
+/* Find next bit set in BSET starting from and including BITNO.  */
+extern int bitset_next PARAMS ((bitset, bitset_bindex));
+
+/* Find previous bit set in BSET starting from and including BITNO.  */
+extern int bitset_prev PARAMS ((bitset, bitset_bindex));
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT.  Return with actual number of bits found and with *NEXT
+   indicating where search stopped.  */
+#if BITSET_STATS
+extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
+				bitset_bindex *));
+#else
+#define bitset_list(BSET, LIST, NUM, NEXT) \
+BITSET__LIST (BSET, LIST, NUM, NEXT)
+#endif
+
+/* Find reverse list of up to NUM bits set in BSET starting from and
+   including NEXT.  Return with actual number of bits found and with
+   *NEXT indicating where search stopped.  */
+#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
+BITSET__REVERSE_LIST (BSET, LIST, NUM, NEXT)
+
+/* Find first set bit.  */
+extern int bitset_first PARAMS ((bitset));
+
+/* Find last set bit.  */
+extern int bitset_last PARAMS ((bitset));
+
+/* Dump bitset.  */
+extern void bitset_dump PARAMS ((FILE *, bitset));
+
+/* Loop over all elements of BSET, starting with MIN, executing CODE.  */
+#define BITSET_EXECUTE(BSET, MIN, N, CODE)				\
+do {									\
+  bitset_bindex _list[BITSET_LIST_SIZE];				\
+  bitset_bindex _next = (MIN);						\
+  int _num;								\
+    									\
+  while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\
+    {									\
+       int _i;								\
+									\
+       for (_i = 0; _i < _num; _i++)					\
+	 {								\
+	    (N) = _list[_i];						\
+            CODE;							\
+	 }								\
+       if (_num < BITSET_LIST_SIZE)					\
+         break;								\
+    }									\
+} while (0)
+
+
+/* Loop over all elements of BSET, in reverse order starting with
+   MIN, executing CODE.  */
+#define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE)			\
+do {									\
+  bitset_bindex _list[BITSET_LIST_SIZE];				\
+  bitset_bindex _next = (MIN);						\
+  int _num;								\
+    									\
+  while ((_num = bitset_reverse_list ((BSET), _list, 			\
+                                      BITSET_LIST_SIZE, &_next)))	\
+    {									\
+       int _i;								\
+									\
+       for (_i = 0; _i < _num; _i++)					\
+	 {								\
+	    (N) = _list[_i];						\
+            CODE;							\
+	 }								\
+       if (_num < BITSET_LIST_SIZE)					\
+         break;								\
+    }									\
+} while (0)
+
+
+/* Define set operations in terms of bit operations.  */
+
+#define bitset_diff(DST, SRC1, SRC2)  bitset_andn (DST, SRC1, SRC2)
+
+#define bitset_intersection(DST, SRC1, SRC2)  bitset_and (DST, SRC1, SRC2)
+
+#define bitset_union(DST, SRC1, SRC2)  bitset_or (DST, SRC1, SRC2)
+
+#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
+bitset_andn_or (DST, SRC1, SRC2, SRC3)
+
+/* Release any memory tied up with bitsets.  */
+extern void bitset_release_memory PARAMS ((void));
+
+/* Initialise bitset stats.  */
+extern void bitset_stats_init PARAMS ((void));
+
+/* Dump bitset stats.  */
+extern void bitset_stats_dump PARAMS ((FILE *));
+
+/* Function to debug bitset from debugger.  */
+extern void debug_bitset PARAMS ((bitset));
+
+/* Function to debug bitset stats from debugger.  */
+extern void debug_bitset_stats PARAMS ((void));
+
+extern bitset sbitset_init PARAMS ((bitset, bitset_bindex));
+
+extern bitset lbitset_init PARAMS ((bitset, bitset_bindex));
+
+extern bitset ebitset_init PARAMS ((bitset, bitset_bindex));
+
+#endif /* _BITSET_H  */
diff --git a/lib/bitsetv.c b/lib/bitsetv.c
new file mode 100644
index 00000000..7fd82268
--- /dev/null
+++ b/lib/bitsetv.c
@@ -0,0 +1,128 @@
+/* Bitset vectors.
+   Copyright (C) 2001 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdlib.h>
+#include "bitsetv.h"
+
+
+/* Create a vector of N_VECS bitsets, each of N_BITS, and of
+   type TYPE.  */
+bitset *
+bitsetv_alloc (n_vecs, n_bits, type)
+    unsigned int n_vecs;
+    unsigned int n_bits;
+    enum bitset_type type;
+{
+    unsigned int vector_bytes;
+    unsigned int bytes;
+    bitset *bsetv;
+    unsigned int i;
+
+    /* Determine number of bytes for each set.  */
+    bytes = bitset_bytes (type, n_bits);
+
+    /* Allocate vector table at head of bitset array.  */
+    vector_bytes = n_vecs * sizeof (bitset);
+    bsetv = (bitset *) xmalloc (vector_bytes + bytes * n_vecs);
+
+    for (i = 0; i < n_vecs; i++)
+    {
+      bsetv[i] = (bitset)((char *)bsetv + vector_bytes + i * bytes);
+
+      bitset_init (bsetv[i], n_bits, type);
+    }
+    return bsetv;
+}
+
+
+/* Create a vector of N_VECS bitsets, each of N_BITS, and with
+   attribute hints specified by ATTR.  */
+bitset *
+bitsetv_create (n_vecs, n_bits, attr)
+    unsigned int n_vecs;
+    unsigned int n_bits;
+    unsigned int attr;
+{
+    enum bitset_type type;
+
+    type = bitset_type_choose (n_bits, attr);
+    return bitsetv_alloc (n_vecs, n_bits, type);
+}
+
+
+/* Free bitset vector BSETV.  */
+void
+bitsetv_free (bsetv)
+    bitset *bsetv;
+{
+    free (bsetv);
+}
+
+
+/* Zero a vector of N_VECS bitsets.  */
+void
+bitsetv_zero (bsetv, n_vecs)
+     struct bitset_struct **bsetv;
+     unsigned int n_vecs;
+{
+  unsigned int i;
+
+  for (i = 0; i < n_vecs; i++)
+      bitset_zero (bsetv[i]);
+}
+
+
+/* Set a vector of N_VECS bitsets to ones.  */
+void
+bitsetv_ones (bsetv, n_vecs)
+     bitset *bsetv;
+     unsigned int n_vecs;
+{
+  unsigned int i;
+
+  for (i = 0; i < n_vecs; i++)
+    bitset_ones (bsetv[i]);
+}
+
+
+/* Dump the contents of a bitset vector BSETV with N_VECS elements to
+   FILE.  */
+void
+bitsetv_dump (file, title, subtitle, bsetv, n_vecs)
+     FILE *file;
+     const char *title, *subtitle;
+     bitset *bsetv;
+     unsigned int n_vecs;
+{
+  unsigned int i;
+
+  fprintf (file, "%s\n", title);
+  for (i = 0; i < n_vecs; i++)
+    {
+      fprintf (file, "%s %d\n", subtitle, i);
+      bitset_dump (file, bsetv[i]);
+    }
+
+  fprintf (file, "\n");
+}
diff --git a/lib/bitsetv.h b/lib/bitsetv.h
new file mode 100644
index 00000000..cac4eb07
--- /dev/null
+++ b/lib/bitsetv.h
@@ -0,0 +1,49 @@
+/* Bitset vectors.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef _BITSETV_H
+#define _BITSETV_H
+
+#include "bitset.h"
+
+typedef bitset * bitsetv;
+
+/* Create a vector of N_VECS bitsets, each of N_BITS, and of
+   type TYPE.  */
+extern bitsetv bitsetv_alloc PARAMS ((unsigned int, unsigned int,
+				      enum bitset_type));
+
+/* Create a vector of N_VECS bitsets, each of N_BITS, and with
+   attribute hints specified by ATTR.  */
+extern bitsetv bitsetv_create PARAMS ((unsigned int, unsigned int,
+				       unsigned int));
+
+/* Free vector of bitsets.  */
+extern void bitsetv_free PARAMS ((bitsetv));
+
+/* Zero vector of bitsets.  */
+extern void bitsetv_zero PARAMS ((bitsetv, unsigned int));
+
+/* Set vector of bitsets.  */
+extern void bitsetv_ones PARAMS ((bitsetv, unsigned int));
+
+/* Dump vector of bitsets.  */
+extern void bitsetv_dump PARAMS ((FILE *, const char *,
+				  const char *, bitsetv,
+				  unsigned int));
+#endif  /* _BITSETV_H  */
diff --git a/lib/ebitset.c b/lib/ebitset.c
new file mode 100644
index 00000000..0a6cbd41
--- /dev/null
+++ b/lib/ebitset.c
@@ -0,0 +1,1245 @@
+/* Functions to support efficient bitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "bitset.h"
+#include "obstack.h"
+#include <stdlib.h>
+
+# if WITH_DMALLOC
+#  define DMALLOC_FUNC_CHECK
+#  include <dmalloc.h>
+# endif /* WITH_DMALLOC */
+
+/* This file implements linked-list bitsets.  These bitsets can be of
+   arbitrary length and are more efficient than arrays of bits for
+   large sparse sets.
+
+   Usually if all the bits in an element are zero we remove the element
+   from the list.  However, a side effect of the bit caching is that we
+   do not always notice when an element becomes zero.  Hence the
+   ebitset_weed function which removes zero elements.
+
+   Empty elements are represented by a NULL pointer in the table of
+   element pointers.  An alternative is to point to a special zero
+   element.  Similarly, we could represent an all 1's element with
+   another special ones element pointer.
+
+   Bitsets are commonly empty so we need to ensure that this special
+   case is fast.  A zero bitset is indicated when cdata is 0.  This is
+   conservative since cdata may be non zero and the bitset may still
+   be zero.
+
+   The bitset cache can be disabled either by setting cindex to
+   some large number or by setting csize to 0.  Here
+   we use the former approach since cindex needs to be updated whenever
+   cdata is changed.
+*/
+
+/* Number of elements to initially allocate.  */
+#ifndef EBITSET_INITIAL_SIZE
+#define EBITSET_INITIAL_SIZE 2
+#endif
+
+/* Minimum number of elements to grow table.  */
+#ifndef EBITSET_GROW_SIZE
+#define EBITSET_GROW_SIZE 4
+#endif
+
+
+enum ebitset_find_mode {EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST};
+
+static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits.  */
+
+/* Obstack to allocate bitset elements from.  */
+static struct obstack ebitset_obstack;
+static int ebitset_obstack_init = 0;
+static ebitset_elt *ebitset_free_list; /* Free list of bitset elements.  */
+
+static void ebitset_elts_grow PARAMS ((bitset, unsigned int));
+static ebitset_elt *ebitset_elt_alloc PARAMS ((void));
+static ebitset_elt *ebitset_elt_calloc PARAMS ((void));
+static void ebitset_elt_add PARAMS ((bitset, ebitset_elt *, unsigned int));
+static void ebitset_elt_remove PARAMS ((bitset, unsigned int));
+static void ebitset_elt_free PARAMS ((ebitset_elt *));
+static ebitset_elt *ebitset_elt_find PARAMS ((bitset, bitset_windex,
+					      enum ebitset_find_mode));
+static ebitset_elt *ebitset_elt_last PARAMS ((bitset));
+static int ebitset_elt_zero_p PARAMS ((ebitset_elt *));
+
+static int ebitset_weed PARAMS ((bitset));
+static void ebitset_zero PARAMS((bitset));
+static int ebitset_equal_p PARAMS((bitset, bitset));
+static void ebitset_copy PARAMS((bitset, bitset));
+static int ebitset_copy_compare PARAMS((bitset, bitset));
+static void ebitset_set PARAMS((bitset, bitset_bindex));
+static void ebitset_reset PARAMS((bitset, bitset_bindex));
+static int ebitset_test PARAMS((bitset, bitset_bindex));
+static int ebitset_size PARAMS((bitset));
+static int ebitset_op1 PARAMS((bitset, enum bitset_ops));
+static int ebitset_op2 PARAMS((bitset, bitset, enum bitset_ops));
+static int ebitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops));
+static int ebitset_op4 PARAMS((bitset, bitset, bitset, bitset,
+			       enum bitset_ops));
+static int ebitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
+				bitset_bindex *));
+static int ebitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
+					bitset_bindex *));
+static void ebitset_free PARAMS((bitset));
+
+
+#define EBITSET_ELTS(BSET) ((BSET)->u.e.elts)
+#define EBITSET_SIZE(BSET) ((BSET)->u.e.size)
+
+#define EBITSET_NEXT(ELT) ((ELT)->u.next)
+#define EBITSET_WORDS(ELT) ((ELT)->u.words)
+
+/* Disable bitset cache and mark BSET as being zero.  */
+#define EBITSET_ZERO_SET(BSET) ((BSET)->cindex = BITSET_INDEX_MAX, \
+        (BSET)->cdata = 0)
+
+#define EBITSET_CACHE_DISABLE(BSET)  ((BSET)->cindex = BITSET_INDEX_MAX)
+
+/* Disable bitset cache and mark BSET as being possibly non-zero.  */
+#define EBITSET_NONZERO_SET(BSET) \
+ (EBITSET_CACHE_DISABLE (BSET), (BSET)->cdata = (bitset_word *)~0)
+
+/* A conservative estimate of whether the bitset is zero.
+   This is non-zero only if we know for sure that the bitset is zero.  */
+#define EBITSET_ZERO_P(BSET) ((BSET)->cdata == 0)
+
+/* Enable cache to point to element with table index EINDEX.
+   The element must exist.  */
+#define EBITSET_CACHE_SET(BSET, EINDEX) \
+ ((BSET)->cindex = (EINDEX) * EBITSET_ELT_WORDS, \
+  (BSET)->cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
+
+
+/* Grow the expandable table for BSET by SIZE elements.  */
+static void
+ebitset_elts_grow (bset, size)
+    bitset bset;
+    unsigned int size;
+{
+  unsigned int oldsize;
+  unsigned int newsize;
+
+  oldsize = EBITSET_SIZE (bset);
+  newsize = oldsize + size;
+
+  EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
+				   newsize * sizeof (ebitset_elt *));
+  EBITSET_SIZE (bset) = newsize;
+
+  memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *));
+}
+
+
+/* Allocate a ebitset element.  The bits are not cleared.  */
+static inline ebitset_elt *
+ebitset_elt_alloc ()
+{
+  ebitset_elt *elt;
+
+  if (ebitset_free_list != 0)
+    {
+      elt = ebitset_free_list;
+      ebitset_free_list = EBITSET_NEXT (elt);
+    }
+  else
+    {
+      /* We can't use gcc_obstack_init to initialize the obstack since
+	 print-rtl.c now calls bitset functions, and bitset is linked
+	 into the gen* functions.  */
+      if (!ebitset_obstack_init)
+	{
+	  ebitset_obstack_init = 1;
+
+	  /* Let particular systems override the size of a chunk.  */
+#ifndef OBSTACK_CHUNK_SIZE
+#define OBSTACK_CHUNK_SIZE 0
+#endif
+	  /* Let them override the alloc and free routines too.  */
+#ifndef OBSTACK_CHUNK_ALLOC
+#define OBSTACK_CHUNK_ALLOC xmalloc
+#endif
+#ifndef OBSTACK_CHUNK_FREE
+#define OBSTACK_CHUNK_FREE free
+#endif
+
+#if !defined(__GNUC__) || (__GNUC__ < 2)
+#define __alignof__(type) 0
+#endif
+
+	  obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
+				      __alignof__ (ebitset_elt),
+				      (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
+				      (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
+	}
+
+      /* Perhaps we should add a number of new elements to the free
+         list.  */
+      elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,
+					   sizeof (ebitset_elt));
+    }
+
+  return elt;
+}
+
+
+/* Allocate a ebitset element.  The bits are not cleared.  */
+static inline ebitset_elt *
+ebitset_elt_calloc ()
+{
+  ebitset_elt *elt;
+
+  elt = ebitset_elt_alloc ();
+  memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt)));
+  return elt;
+}
+
+
+static inline void
+ebitset_elt_free (elt)
+     ebitset_elt *elt;
+{
+  EBITSET_NEXT (elt) = ebitset_free_list;
+  ebitset_free_list = elt;
+}
+
+
+/* Remove element with index EINDEX from bitset BSET.  */
+static inline void
+ebitset_elt_remove (bset, eindex)
+     bitset bset;
+     unsigned int eindex;
+{
+  ebitset_elts *elts;
+  ebitset_elt *elt;
+
+  elts = EBITSET_ELTS (bset);
+
+  elt = elts[eindex];
+
+  elts[eindex] = 0;
+  ebitset_elt_free (elt);
+}
+
+
+/* Add ELT into elts at index EINDEX of bitset BSET.  */
+static inline void
+ebitset_elt_add (bset, elt, eindex)
+     bitset bset;
+     ebitset_elt *elt;
+     unsigned int eindex;
+{
+  ebitset_elts *elts;
+
+  elts = EBITSET_ELTS (bset);
+  /* Assume that the elts entry not allocated.  */
+  elts[eindex] = elt;
+}
+
+
+/* Return nonzero if all bits in an element are zero.  */
+static inline int
+ebitset_elt_zero_p (elt)
+     ebitset_elt *elt;
+{
+  int i;
+
+  for (i = 0; i < EBITSET_ELT_WORDS; i++)
+    if (EBITSET_WORDS (elt)[i])
+      return 0;
+
+  return 1;
+}
+
+
+static ebitset_elt *
+ebitset_elt_find (bset, index, mode)
+     bitset bset;
+     bitset_windex index;
+     enum ebitset_find_mode mode;
+{
+  ebitset_elt *elt;
+  bitset_windex size;
+  unsigned int eindex;
+  ebitset_elts *elts;
+
+  eindex = index / EBITSET_ELT_WORDS;
+
+  elts = EBITSET_ELTS (bset);
+  size = EBITSET_SIZE (bset);
+
+  if (eindex < size)
+    {
+      ebitset_elt *elt;
+
+      if ((elt = elts[eindex]))
+	{
+	  if (EBITSET_WORDS (elt) == bset->cdata)
+	    return elt;
+
+	  EBITSET_CACHE_SET (bset, eindex);
+	  return elt;
+	}
+    }
+
+  /* The element could not be found.  */
+
+  switch (mode)
+    {
+    case EBITSET_FIND:
+      return 0;
+
+    case EBITSET_CREATE:
+      if (eindex >= size)
+	{
+	  unsigned int extra;
+
+	  extra = eindex - size + 1;
+
+	  /* We need to expand the table by EXTRA elements.  It may be
+	     better with large bitsets to grow the number of
+	     elements by some fraction of the current size otherwise
+	     we can spend a lot of time slowly increasing the size of the
+	     bitset.  */
+	  if (extra < EBITSET_GROW_SIZE)
+	    extra = EBITSET_GROW_SIZE;
+
+	  ebitset_elts_grow (bset, extra);
+	}
+
+      /* Create a new element.  */
+      elt = ebitset_elt_calloc ();
+      ebitset_elt_add (bset, elt, eindex);
+      EBITSET_CACHE_SET (bset, eindex);
+      return elt;
+
+    case EBITSET_SUBST:
+      return &ebitset_zero_elts[0];
+
+    default:
+      abort ();
+    }
+}
+
+
+static inline ebitset_elt *
+ebitset_elt_last (bset)
+     bitset bset;
+{
+  ebitset_elts *elts;
+
+  elts = EBITSET_ELTS (bset);
+
+  /* Assume that have at least one element in elts.  */
+  return elts[EBITSET_SIZE (bset) - 1];
+}
+
+
+/* Weed out the zero elements from the elts.  */
+static inline int
+ebitset_weed (bset)
+     bitset bset;
+{
+  ebitset_elts *elts;
+  bitset_windex j;
+  int count;
+
+  if (EBITSET_ZERO_P (bset))
+    return 0;
+
+  elts = EBITSET_ELTS (bset);
+  count = 0;
+  for (j = 0; j < EBITSET_SIZE (bset); j++)
+    {
+      ebitset_elt *elt = elts[j];
+
+      if (elt)
+	{
+	  if (elt && ebitset_elt_zero_p (elt))
+	    {
+	      ebitset_elt_remove (bset, j);
+	      count++;
+	    }
+	}
+      else
+	count++;
+    }
+
+  count = j - count;
+  if (!count)
+    {
+      /* All the bits are zero.  We could shrink the elts.
+	 For now just mark BSET as known to be zero.  */
+      EBITSET_ZERO_SET (bset);
+    }
+  else
+    EBITSET_NONZERO_SET (bset);
+
+  return  count;
+}
+
+
+/* Set all bits in the bitset to zero.  */
+static inline void
+ebitset_zero (bset)
+     bitset bset;
+{
+  ebitset_elts *elts;
+  bitset_windex j;
+
+  if (EBITSET_ZERO_P (bset))
+    return;
+
+  elts = EBITSET_ELTS (bset);
+  for (j = 0; j < EBITSET_SIZE (bset); j++)
+    {
+      ebitset_elt *elt = elts[j];
+
+      if (elt)
+	ebitset_elt_remove (bset, j);
+    }
+
+  /* All the bits are zero.  We could shrink the elts.
+     For now just mark BSET as known to be zero.  */
+  EBITSET_ZERO_SET (bset);
+}
+
+
+static inline int
+ebitset_equal_p (dst, src)
+     bitset dst;
+     bitset src;
+{
+  ebitset_elts *selts;
+  ebitset_elts *delts;
+  bitset_windex j;
+
+  if (src == dst)
+    return 1;
+
+  ebitset_weed (dst);
+  ebitset_weed (src);
+
+  if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
+    return 0;
+
+  selts = EBITSET_ELTS (src);
+  delts = EBITSET_ELTS (dst);
+
+  for (j = 0; j < EBITSET_SIZE (src); j++)
+    {
+      unsigned int i;
+      ebitset_elt *selt = selts[j];
+      ebitset_elt *delt = delts[j];
+
+      if (! selt && ! delt)
+	continue;
+      if ((selt && ! delt) || (!selt && delt))
+	return 0;
+
+      for (i = 0; i < EBITSET_ELT_WORDS; i++)
+	if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
+	  return 0;
+    }
+  return 1;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  */
+static inline void
+ebitset_copy (dst, src)
+     bitset dst;
+     bitset src;
+{
+  ebitset_elts *selts;
+  ebitset_elts *delts;
+  bitset_windex j;
+
+  if (src == dst)
+    return;
+
+  ebitset_zero (dst);
+
+  if (EBITSET_SIZE (dst) < EBITSET_SIZE (src))
+    ebitset_elts_grow (dst, EBITSET_SIZE (src) - EBITSET_SIZE (dst));
+
+  selts = EBITSET_ELTS (src);
+  delts = EBITSET_ELTS (dst);
+  for (j = 0; j < EBITSET_SIZE (src); j++)
+    {
+      ebitset_elt *selt = selts[j];
+
+      if (selt)
+	{
+	  ebitset_elt *tmp;
+
+	  tmp = ebitset_elt_alloc ();
+	  delts[j] = tmp;
+	  memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
+		  sizeof (EBITSET_WORDS (selt)));
+	}
+    }
+  EBITSET_NONZERO_SET (dst);
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  Return non-zero if
+   bitsets different.  */
+static inline int
+ebitset_copy_compare (dst, src)
+     bitset dst;
+     bitset src;
+{
+  if (src == dst)
+    return 0;
+
+  if (EBITSET_ZERO_P (dst))
+    {
+      ebitset_copy (dst, src);
+      return ! EBITSET_ZERO_P (src);
+    }
+
+  if (ebitset_equal_p (dst, src))
+    return 0;
+
+  ebitset_copy (dst, src);
+  return 1;
+}
+
+
+/* Return size in bits of bitset SRC.  */
+static int
+ebitset_size (src)
+     bitset src;
+{
+  /* Return current size of bitset in bits.  */
+  return EBITSET_SIZE (src) * EBITSET_ELT_BITS;
+}
+
+
+/* Set bit BITNO in bitset DST.  */
+static void
+ebitset_set (dst, bitno)
+     bitset dst;
+     bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+
+  ebitset_elt_find (dst, index, EBITSET_CREATE);
+
+  dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS));
+}
+
+
+/* Reset bit BITNO in bitset DST.  */
+static void
+ebitset_reset (dst, bitno)
+     bitset dst;
+     bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+
+  if (!ebitset_elt_find (dst, index, EBITSET_FIND))
+      return;
+
+  dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
+
+  /* If all the data is zero, perhaps we should remove it now...
+     However, there could be a good chance that the element will be needed
+     again soon.  */
+}
+
+
+/* Test bit BITNO in bitset SRC.  */
+static int
+ebitset_test (src, bitno)
+     bitset src;
+     bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+
+  if (!ebitset_elt_find (src, index, EBITSET_FIND))
+    return 0;
+
+  return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
+}
+
+
+static void
+ebitset_free (bset)
+     bitset bset;
+{
+  ebitset_zero (bset);
+  free (EBITSET_ELTS (bset));
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static int
+ebitset_reverse_list (bset, list, num, next)
+     bitset bset;
+     bitset_bindex *list;
+     bitset_bindex num;
+     bitset_bindex *next;
+{
+  bitset_bindex n_bits;
+  bitset_bindex bitno;
+  bitset_bindex rbitno;
+  unsigned int bitcnt;
+  bitset_bindex bitoff;
+  bitset_windex index;
+  unsigned int eindex;
+  bitset_windex windex;
+  bitset_bindex count;
+  bitset_windex size;
+  bitset_word word;
+  ebitset_elts *elts;
+
+  if (EBITSET_ZERO_P (bset))
+    return 0;
+
+  size = EBITSET_SIZE (bset);
+  n_bits = size * EBITSET_ELT_BITS;
+  rbitno = *next;
+
+  if (rbitno >= n_bits)
+      return 0;
+
+  elts = EBITSET_ELTS (bset);
+
+  bitno = n_bits - (rbitno + 1);
+
+  index = bitno /  BITSET_WORD_BITS;
+  eindex = bitno / EBITSET_ELT_BITS;
+  windex = index - eindex * EBITSET_ELT_WORDS;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  count = 0;
+  bitcnt = bitno % BITSET_WORD_BITS;
+  bitoff = index * BITSET_WORD_BITS;
+
+  for (; eindex != ~0U; eindex--)
+    {
+      ebitset_elt *elt;
+      bitset_word *srcp;
+
+      elt = elts[eindex];
+      if (!elt)
+	continue;
+
+      srcp = EBITSET_WORDS (elt);
+
+      for (; windex != ~0U; windex--, bitoff -= BITSET_WORD_BITS,
+	     bitcnt = BITSET_WORD_BITS - 1)
+	{
+	  word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
+
+	  for (; word; bitcnt--)
+	    {
+	      if (word & BITSET_MSB)
+		{
+		  list[count++] = bitoff + bitcnt;
+		  if (count >= num)
+		    {
+		      *next = n_bits - (bitoff + bitcnt);
+		      return count;
+		    }
+		}
+	      word <<= 1;
+	    }
+	}
+
+      windex = EBITSET_ELT_WORDS;
+    }
+
+  *next = n_bits - (bitoff + 1);
+  return count;
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static int
+ebitset_list (bset, list, num, next)
+     bitset bset;
+     bitset_bindex *list;
+     bitset_bindex num;
+     bitset_bindex *next;
+{
+  bitset_bindex bitno;
+  bitset_windex index;
+  unsigned int eindex;
+  bitset_bindex count;
+  bitset_windex size;
+  ebitset_elt *elt;
+  bitset_word word;
+  ebitset_elts *elts;
+
+  if (EBITSET_ZERO_P (bset))
+    return 0;
+
+  bitno = *next;
+  count = 0;
+
+  elts = EBITSET_ELTS (bset);
+  size = EBITSET_SIZE (bset);
+  eindex = bitno / EBITSET_ELT_BITS;
+
+  if (bitno % EBITSET_ELT_BITS)
+    {
+      /* We need to start within an element.  This is not very common.  */
+
+      elt = elts[eindex];
+      if (elt)
+	{
+	  bitset_windex windex;
+	  bitset_word *srcp = EBITSET_WORDS (elt);
+
+	  index = bitno / BITSET_WORD_BITS;
+	  windex = eindex / EBITSET_ELT_WORDS;
+
+	  for (; (index - windex) < EBITSET_ELT_WORDS; index++)
+	    {
+	      word = srcp[index - windex] >> (bitno % BITSET_WORD_BITS);
+
+	      for (; word; bitno++)
+		{
+		  if (word & 1)
+		    {
+		      list[count++] = bitno;
+		      if (count >= num)
+			{
+			  *next = bitno + 1;
+			  return count;
+			}
+		    }
+		  word >>= 1;
+		}
+	      bitno = (index + 1) * BITSET_WORD_BITS;
+	    }
+	}
+
+      /* Skip to next element.  */
+      eindex++;
+    }
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  for (; eindex < size; eindex++)
+    {
+      int i;
+      ebitset_elt *elt;
+      bitset_word *srcp;
+
+      elt = elts[eindex];
+      if (!elt)
+	continue;
+
+      srcp = EBITSET_WORDS (elt);
+      index = eindex * EBITSET_ELT_WORDS;
+
+      if ((count + EBITSET_ELT_BITS) < num)
+	{
+	  /* The coast is clear, plant boot!  */
+
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++, index++)
+	    {
+	      bitno = index * BITSET_WORD_BITS;
+
+	      word = srcp[i];
+	      if (word)
+		{
+		  if (! (word & 0xffff))
+		    {
+		      word >>= 16;
+		      bitno += 16;
+		    }
+		  if (! (word & 0xff))
+		    {
+		      word >>= 8;
+		      bitno += 8;
+		    }
+		  for (; word; bitno++)
+		    {
+		      if (word & 1)
+			list[count++] = bitno;
+		      word >>= 1;
+		    }
+		}
+	    }
+	}
+      else
+	{
+	  /* Tread more carefully since we need to check
+	     if array overflows.  */
+
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++, index++)
+	    {
+	      bitno = index * BITSET_WORD_BITS;
+
+	      for (word = srcp[i]; word; bitno++)
+		{
+		  if (word & 1)
+		    {
+		      list[count++] = bitno;
+		      if (count >= num)
+			{
+			  *next = bitno + 1;
+			  return count;
+			}
+		    }
+		  word >>= 1;
+		}
+	    }
+	}
+    }
+
+  *next = bitno;
+  return count;
+}
+
+
+static int
+ebitset_op1 (dst, op)
+     bitset dst;
+     enum bitset_ops op;
+{
+  bitset_windex j;
+  ebitset_elt *elt;
+
+  switch (op)
+    {
+    case BITSET_ZERO:
+      ebitset_zero (dst);
+      return 1;
+
+    case BITSET_ONES:
+      for (j = 0; j < EBITSET_SIZE (dst); j++)
+	{
+	  /* Create new elements if they cannot be found.  Perhaps
+	   we should just add pointers to a ones element.  */
+	  elt = ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+	  memset (EBITSET_WORDS (elt), ~0, sizeof (EBITSET_WORDS (elt)));
+	}
+      break;
+
+    case BITSET_EMPTY_P:
+      return ! ebitset_weed (dst);
+
+    default:
+      abort ();
+    }
+
+  EBITSET_NONZERO_SET (dst);
+  return 1;
+}
+
+
+static int
+ebitset_op2 (dst, src, op)
+     bitset dst;
+     bitset src;
+     enum bitset_ops op;
+{
+  ebitset_elt *selt;
+  ebitset_elt *delt;
+  unsigned int i;
+  bitset_windex j;
+
+  switch (op)
+    {
+    case BITSET_COPY:
+      ebitset_copy (dst, src);
+      break;
+
+    case BITSET_NOT:
+      for (j = 0; j < EBITSET_SIZE (src); j++)
+	{
+	  /* Create new elements for dst if they cannot be found
+	     or substitute zero elements if src elements not found.  */
+	  selt = ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
+	  delt = ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
+
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++)
+	    EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
+	}
+      break;
+
+    case BITSET_EQUAL_P:
+      return ebitset_equal_p (dst, src);
+
+      /* Return 1 if DST == DST | SRC.  */
+    case BITSET_SUBSET_P:
+      {
+	ebitset_elts *selts;
+	ebitset_elts *delts;
+	bitset_windex ssize;
+	bitset_windex dsize;
+
+	selts = EBITSET_ELTS (src);
+	delts = EBITSET_ELTS (dst);
+
+	ssize = EBITSET_SIZE (src);
+	dsize = EBITSET_SIZE (dst);
+
+	for (j = 0; j < ssize; j++)
+	  {
+	    ebitset_elt *selt;
+	    ebitset_elt *delt;
+
+	    selt = j < ssize ? selts[j] : 0;
+	    delt = j < dsize ? delts[j] : 0;
+
+	    if (! selt && ! delt)
+	      continue;
+
+	    if (!selt)
+	      selt = &ebitset_zero_elts[0];
+	    if (!delt)
+	      delt = &ebitset_zero_elts[0];
+
+	    for (i = 0; i < EBITSET_ELT_WORDS; i++)
+	      if (EBITSET_WORDS (delt)[i]
+		  != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
+		return 0;
+	  }
+	return 1;
+      }
+      break;
+
+    default:
+      abort ();
+    }
+
+  EBITSET_NONZERO_SET (dst);
+  return 1;
+}
+
+
+static int
+ebitset_op3 (dst, src1, src2, op)
+     bitset dst;
+     bitset src1;
+     bitset src2;
+     enum bitset_ops op;
+{
+  bitset_windex ssize1;
+  bitset_windex ssize2;
+  bitset_windex dsize;
+  bitset_windex size;
+  ebitset_elts *selts1;
+  ebitset_elts *selts2;
+  ebitset_elts *delts;
+  bitset_word *srcp1;
+  bitset_word *srcp2;
+  bitset_word *dstp;
+  int changed = 0;
+  unsigned int i;
+  bitset_windex j;
+
+  /* Fast track common, simple cases.  */
+  if (EBITSET_ZERO_P (src2))
+    {
+      if (op == BITSET_AND)
+	{
+	  ebitset_weed (dst);
+	  changed = EBITSET_ZERO_P (dst);
+	  ebitset_zero (dst);
+	  return changed;
+	}
+      else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR)
+	{
+	  return ebitset_copy_compare (dst, src1);
+	}
+    }
+  else if (EBITSET_ZERO_P (src1))
+    {
+      if (op == BITSET_AND || op == BITSET_ANDN)
+	{
+	  ebitset_weed (dst);
+	  changed = EBITSET_ZERO_P (dst);
+	  ebitset_zero (dst);
+	  return changed;
+	}
+      else if (op == BITSET_OR || op == BITSET_XOR)
+	{
+	  return ebitset_copy_compare (dst, src2);
+	}
+    }
+
+  ssize1 = EBITSET_SIZE (src1);
+  ssize2 = EBITSET_SIZE (src2);
+  dsize = EBITSET_SIZE (dst);
+  size = ssize1;
+  if (size < ssize2)
+    size = ssize2;
+
+  if (size > dsize)
+      ebitset_elts_grow (dst, size - dsize);
+
+  selts1 = EBITSET_ELTS (src1);
+  selts2 = EBITSET_ELTS (src2);
+  delts = EBITSET_ELTS (dst);
+
+  for (j = 0; j < size; j++)
+    {
+      ebitset_elt *selt1;
+      ebitset_elt *selt2;
+      ebitset_elt *delt;
+
+      selt1 = j < ssize1 ? selts1[j] : 0;
+      selt2 = j < ssize2 ? selts2[j] : 0;
+      delt = j < dsize ? delts[j] : 0;
+
+      if (! selt1 && ! selt2)
+	{
+	  if (delt)
+	    {
+	      changed = 1;
+	      ebitset_elt_remove (dst, j);
+	    }
+	  continue;
+	}
+
+      if (!selt1)
+	selt1 = &ebitset_zero_elts[0];
+      if (!selt2)
+	selt2 = &ebitset_zero_elts[0];
+      if (!delt)
+	delt = ebitset_elt_calloc ();
+      else
+	delts[j] = 0;
+
+      srcp1 = EBITSET_WORDS (selt1);
+      srcp2 = EBITSET_WORDS (selt2);
+      dstp = EBITSET_WORDS (delt);
+      switch (op)
+	{
+	case BITSET_OR:
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ | *srcp2++;
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_AND:
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ & *srcp2++;
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_XOR:
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ ^ *srcp2++;
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_ANDN:
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_ORN:
+	  for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ | ~(*srcp2++);
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	default:
+	  abort ();
+	}
+
+      if (! ebitset_elt_zero_p (delt))
+	{
+	  ebitset_elt_add (dst, delt, j);
+	}
+      else
+	{
+	  ebitset_elt_free (delt);
+	}
+    }
+
+  /* If we have elements of DST left over, free them all.  */
+  for (; j < dsize; j++)
+    {
+      ebitset_elt *delt;
+
+      changed = 1;
+
+      delt = delts[j];
+
+      if (delt)
+	ebitset_elt_remove (dst, j);
+    }
+
+  EBITSET_NONZERO_SET (dst);
+  return changed;
+}
+
+
+static int
+ebitset_op4 (dst, src1, src2, src3, op)
+     bitset dst;
+     bitset src1;
+     bitset src2;
+     bitset src3;
+     enum bitset_ops op;
+{
+  int changed = 0;
+  bitset tmp;
+
+  tmp = bitset_create (BITSET_LIST, 0);
+
+  switch (op)
+    {
+    case BITSET_OR_AND:
+      bitset_or (tmp, src1, src2);
+      changed = bitset_and (dst, src3, tmp);
+      break;
+
+    case BITSET_AND_OR:
+      bitset_and (tmp, src1, src2);
+      changed = bitset_or (dst, src3, tmp);
+      break;
+
+    case BITSET_ANDN_OR:
+      bitset_andn (tmp, src1, src2);
+      changed = bitset_or (dst, src3, tmp);
+      break;
+
+    default:
+      abort ();
+    }
+
+  bitset_free (tmp);
+  EBITSET_NONZERO_SET (dst);
+  return changed;
+}
+
+
+/* Vector of operations for linked-list bitsets.  */
+struct bitset_ops_struct ebitset_ops =
+  {
+    ebitset_set,
+    ebitset_reset,
+    ebitset_test,
+    ebitset_size,
+    ebitset_op1,
+    ebitset_op2,
+    ebitset_op3,
+    ebitset_op4,
+    ebitset_list,
+    ebitset_reverse_list,
+    ebitset_free,
+    BITSET_TABLE
+  };
+
+
+/* Return size of initial structure.  */
+int
+ebitset_bytes (n_bits)
+     bitset_bindex n_bits ATTRIBUTE_UNUSED;
+{
+  return sizeof (struct bitset_struct);
+}
+
+
+/* Initialize a bitset.  */
+
+bitset
+ebitset_init (bset, n_bits)
+     bitset bset;
+     bitset_bindex n_bits;
+{
+  unsigned int size;
+
+  bset->ops = &ebitset_ops;
+
+  bset->csize = EBITSET_ELT_WORDS;
+
+  EBITSET_ZERO_SET (bset);
+
+  size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
+    : EBITSET_INITIAL_SIZE;
+
+  EBITSET_SIZE (bset) = 0;
+  EBITSET_ELTS (bset) = 0;
+  ebitset_elts_grow (bset, size);
+
+  return bset;
+}
+
+
+void
+ebitset_release_memory ()
+{
+  ebitset_free_list = 0;
+  if (ebitset_obstack_init)
+    {
+      ebitset_obstack_init = 0;
+      obstack_free (&ebitset_obstack, NULL);
+    }
+}
diff --git a/lib/ebitset.h b/lib/ebitset.h
new file mode 100644
index 00000000..5b481dbf
--- /dev/null
+++ b/lib/ebitset.h
@@ -0,0 +1,58 @@
+/* Functions to support ebitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef _EBITSET_H
+#define _EBITSET_H
+
+#include "bitset-int.h"
+
+/* Number of words to use for each element.  */
+#ifndef EBITSET_ELT_WORDS
+#define EBITSET_ELT_WORDS 2
+#endif
+
+/* Number of bits stored in each element.  */
+#define EBITSET_ELT_BITS \
+  ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
+
+/* Ebitset element.  We use an array of bits.  */
+typedef struct ebitset_elt_struct
+{
+  union
+  {
+    bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set.  */
+    struct ebitset_elt_struct *next;
+  } u;
+} ebitset_elt;
+
+
+typedef ebitset_elt *ebitset_elts;
+
+/* Head of ebitset linked list.  */
+typedef struct ebitset_struct
+{
+  unsigned int size;		/* Number of elements.  */
+  ebitset_elts *elts;		/* Expanding array of pointers to elements.  */
+} *ebitset;
+
+
+extern int ebitset_bytes PARAMS ((bitset_bindex));
+
+extern void ebitset_release_memory PARAMS ((void));
+
+#endif
diff --git a/lib/lbitset.c b/lib/lbitset.c
new file mode 100644
index 00000000..e400df3d
--- /dev/null
+++ b/lib/lbitset.c
@@ -0,0 +1,1321 @@
+/* Functions to support link list bitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "bitset.h"
+#include "obstack.h"
+#include <stdlib.h>
+
+# if WITH_DMALLOC
+#  define DMALLOC_FUNC_CHECK
+#  include <dmalloc.h>
+# endif /* WITH_DMALLOC */
+
+/* This file implements linked-list bitsets.  These bitsets can be of
+   arbitrary length and are more efficient than arrays of bits for
+   large sparse sets.
+
+  Usually if all the bits in an element are zero we remove the element
+  from the list.  However, a side effect of the bit caching is that we
+  do not always notice when an element becomes zero.  Hence the
+  lbitset_weed function which removes zero elements.  */
+
+enum lbitset_find_mode {LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST};
+
+static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits.  */
+
+/* Obstack to allocate bitset elements from.  */
+static struct obstack lbitset_obstack;
+static int lbitset_obstack_init = 0;
+static lbitset_elt *lbitset_free_list; /* Free list of bitset elements.  */
+
+static lbitset_elt *lbitset_elt_alloc PARAMS ((void));
+static lbitset_elt *lbitset_elt_calloc PARAMS ((void));
+static void lbitset_elt_link PARAMS ((bitset, lbitset_elt *));
+static void lbitset_elt_unlink PARAMS ((bitset, lbitset_elt *));
+static void lbitset_elt_free PARAMS ((lbitset_elt *));
+static lbitset_elt *lbitset_elt_find PARAMS ((bitset, bitset_windex,
+					      enum lbitset_find_mode));
+static int lbitset_elt_zero_p PARAMS ((lbitset_elt *));
+
+static void lbitset_prune PARAMS ((bitset, lbitset_elt *));
+static void lbitset_weed PARAMS ((bitset));
+static void lbitset_zero PARAMS((bitset));
+static int lbitset_equal_p PARAMS((bitset, bitset));
+static void lbitset_copy PARAMS((bitset, bitset));
+static int lbitset_copy_compare PARAMS((bitset, bitset));
+static void lbitset_set PARAMS((bitset, bitset_bindex));
+static void lbitset_reset PARAMS((bitset, bitset_bindex));
+static int lbitset_test PARAMS((bitset, bitset_bindex));
+static int lbitset_size PARAMS((bitset));
+static int lbitset_op1 PARAMS((bitset, enum bitset_ops));
+static int lbitset_op2 PARAMS((bitset, bitset, enum bitset_ops));
+static int lbitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops));
+static int lbitset_op4 PARAMS((bitset, bitset, bitset, bitset,
+			       enum bitset_ops));
+static int lbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
+				bitset_bindex *));
+static int lbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
+					bitset_bindex *));
+static void lbitset_free PARAMS((bitset));
+
+
+#define LBITSET_CURRENT1(X) (lbitset_elt *)((char *)(X) + ((char *)&(((lbitset_elt *)(X))->next) - (char *)&(((lbitset_elt *)(X))->words)))
+
+#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->cdata)
+
+#define LBITSET_HEAD(X) ((X)->u.l.head)
+#define LBITSET_TAIL(X) ((X)->u.l.tail)
+
+/* Allocate a lbitset element.  The bits are not cleared.  */
+static inline lbitset_elt *
+lbitset_elt_alloc ()
+{
+  lbitset_elt *elt;
+
+  if (lbitset_free_list != 0)
+    {
+      elt = lbitset_free_list;
+      lbitset_free_list = elt->next;
+    }
+  else
+    {
+      /* We can't use gcc_obstack_init to initialize the obstack since
+	 print-rtl.c now calls bitset functions, and bitset is linked
+	 into the gen* functions.  */
+      if (!lbitset_obstack_init)
+	{
+	  lbitset_obstack_init = 1;
+
+	  /* Let particular systems override the size of a chunk.  */
+#ifndef OBSTACK_CHUNK_SIZE
+#define OBSTACK_CHUNK_SIZE 0
+#endif
+	  /* Let them override the alloc and free routines too.  */
+#ifndef OBSTACK_CHUNK_ALLOC
+#define OBSTACK_CHUNK_ALLOC xmalloc
+#endif
+#ifndef OBSTACK_CHUNK_FREE
+#define OBSTACK_CHUNK_FREE free
+#endif
+
+#if !defined(__GNUC__) || (__GNUC__ < 2)
+#define __alignof__(type) 0
+#endif
+
+	  obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
+				      __alignof__ (lbitset_elt),
+				      (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
+				      (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
+	}
+
+      /* Perhaps we should add a number of new elements to the free
+         list.  */
+      elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack,
+					   sizeof (lbitset_elt));
+    }
+
+  return elt;
+}
+
+
+/* Allocate a lbitset element.  The bits are not cleared.  */
+static inline lbitset_elt *
+lbitset_elt_calloc ()
+{
+  lbitset_elt *elt;
+
+  elt = lbitset_elt_alloc ();
+  memset (elt->words, 0, sizeof (elt->words));
+  return elt;
+}
+
+
+static inline void
+lbitset_elt_free (elt)
+     lbitset_elt *elt;
+{
+  elt->next = lbitset_free_list;
+  lbitset_free_list = elt;
+}
+
+
+/* Unlink element ELT from bitset BSET.  */
+static inline void
+lbitset_elt_unlink (bset, elt)
+     bitset bset;
+     lbitset_elt *elt;
+{
+  lbitset_elt *next = elt->next;
+  lbitset_elt *prev = elt->prev;
+
+  if (prev)
+    prev->next = next;
+
+  if (next)
+    next->prev = prev;
+
+  if (LBITSET_HEAD (bset) == elt)
+    LBITSET_HEAD (bset) = next;
+  if (LBITSET_TAIL (bset) == elt)
+    LBITSET_TAIL (bset) = prev;
+
+  /* Update cache pointer.  Since the first thing we try is to insert
+     before current, make current the next entry in preference to the
+     previous.  */
+  if (LBITSET_CURRENT (bset) == elt)
+    {
+      if (next)
+	{
+	  bset->cdata = next->words;
+	  bset->cindex = next->index;
+	}
+      else if (prev)
+	{
+	  bset->cdata = prev->words;
+	  bset->cindex = prev->index;
+	}
+      else
+	{
+	  bset->csize = 0;
+	  bset->cdata = 0;
+	}
+    }
+
+  lbitset_elt_free (elt);
+}
+
+
+/* Cut the chain of bitset BSET before element ELT and free the
+   elements.  */
+static inline void
+lbitset_prune (bset, elt)
+     bitset bset;
+     lbitset_elt *elt;
+{
+  lbitset_elt *next;
+
+  if (!elt)
+      return;
+
+  if (elt->prev)
+  {
+      LBITSET_TAIL (bset) = elt->prev;
+      bset->cdata = elt->prev->words;
+      bset->cindex = elt->prev->index;
+      elt->prev->next = 0;
+  }
+  else
+  {
+      LBITSET_HEAD (bset) = 0;
+      LBITSET_TAIL (bset) = 0;
+      bset->cdata = 0;
+      bset->csize = 0;
+  }
+
+  for (; elt; elt = next)
+    {
+      next = elt->next;
+      lbitset_elt_free (elt);
+    }
+}
+
+
+/* Return nonzero if all bits in an element are zero.  */
+static inline int
+lbitset_elt_zero_p (elt)
+     lbitset_elt *elt;
+{
+  int i;
+
+  for (i = 0; i < LBITSET_ELT_WORDS; i++)
+    if (elt->words[i])
+      return 0;
+
+  return 1;
+}
+
+
+/* Link the bitset element into the current bitset linked list.  */
+static inline void
+lbitset_elt_link (bset, elt)
+     bitset bset;
+     lbitset_elt *elt;
+{
+  bitset_windex index = elt->index;
+  lbitset_elt *ptr;
+  lbitset_elt *current;
+
+  if (bset->csize)
+      current = LBITSET_CURRENT (bset);
+  else
+      current = LBITSET_HEAD (bset);
+
+  /* If this is the first and only element, add it in.  */
+  if (LBITSET_HEAD (bset) == 0)
+    {
+      elt->next = elt->prev = 0;
+      LBITSET_HEAD (bset) = elt;
+      LBITSET_TAIL (bset) = elt;
+    }
+
+  /* If this index is less than that of the current element, it goes
+     somewhere before the current element.  */
+  else if (index < bset->cindex)
+    {
+      for (ptr = current;
+	   ptr->prev && ptr->prev->index > index;
+	   ptr = ptr->prev)
+	continue;
+
+      if (ptr->prev)
+	ptr->prev->next = elt;
+      else
+	LBITSET_HEAD (bset) = elt;
+
+      elt->prev = ptr->prev;
+      elt->next = ptr;
+      ptr->prev = elt;
+    }
+
+  /* Otherwise, it must go somewhere after the current element.  */
+  else
+    {
+      for (ptr = current;
+	   ptr->next && ptr->next->index < index;
+	   ptr = ptr->next)
+	continue;
+
+      if (ptr->next)
+	ptr->next->prev = elt;
+      else
+	LBITSET_TAIL (bset) = elt;
+
+      elt->next = ptr->next;
+      elt->prev = ptr;
+      ptr->next = elt;
+    }
+
+  /* Set up so this is the first element searched.  */
+  bset->cindex = index;
+  bset->csize = LBITSET_ELT_WORDS;
+  bset->cdata = elt->words;
+}
+
+
+static lbitset_elt *
+lbitset_elt_find (bset, index, mode)
+     bitset bset;
+     bitset_windex index;
+     enum lbitset_find_mode mode;
+{
+  lbitset_elt *elt;
+  lbitset_elt *current;
+
+  if (bset->csize)
+    {
+      current = LBITSET_CURRENT (bset);
+      /* Check if element is the cached element.  */
+      if ((index - bset->cindex) < bset->csize)
+	return current;
+    }
+  else
+    {
+      current = LBITSET_HEAD (bset);
+    }
+
+  if (current)
+    {
+      if (index < bset->cindex)
+	{
+	  for (elt = current;
+	       elt->prev && elt->index > index;
+	       elt = elt->prev)
+	    continue;
+	}
+      else
+	{
+	  for (elt = current;
+	       elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < index;
+	       elt = elt->next)
+	    continue;
+	}
+
+      /* `element' is the nearest to the one we want.  If it's not the one
+	 we want, the one we want does not exist.  */
+      if (elt && (index - elt->index) < LBITSET_ELT_WORDS)
+	{
+	  bset->cindex = elt->index;
+          bset->csize = LBITSET_ELT_WORDS;
+	  bset->cdata = elt->words;
+	  return elt;
+	}
+    }
+
+  switch (mode)
+    {
+    case LBITSET_FIND:
+      return 0;
+
+    case LBITSET_CREATE:
+      index = (index / (unsigned) LBITSET_ELT_WORDS) * LBITSET_ELT_WORDS;
+
+      elt = lbitset_elt_calloc ();
+      elt->index = index;
+      lbitset_elt_link (bset, elt);
+      return elt;
+
+    case LBITSET_SUBST:
+      return &lbitset_zero_elts[0];
+
+    default:
+      abort ();
+    }
+}
+
+
+/* Weed out the zero elements from the list.  */
+static inline void
+lbitset_weed (bset)
+     bitset bset;
+{
+  lbitset_elt *elt;
+  lbitset_elt *next;
+
+  for (elt = LBITSET_HEAD (bset); elt; elt = next)
+    {
+      next = elt->next;
+      if (lbitset_elt_zero_p (elt))
+	lbitset_elt_unlink (bset, elt);
+    }
+}
+
+
+/* Set all bits in the bitset to zero.  */
+static inline void
+lbitset_zero (bset)
+     bitset bset;
+{
+  lbitset_elt *head;
+
+  head = LBITSET_HEAD (bset);
+  if (!head)
+    return;
+
+  /* Clear a bitset by freeing the linked list at the head element.  */
+  lbitset_prune (bset, head);
+}
+
+
+static inline int
+lbitset_equal_p (dst, src)
+     bitset dst;
+     bitset src;
+{
+  lbitset_elt *selt;
+  lbitset_elt *delt;
+  int j;
+
+  if (src == dst)
+    return 1;
+
+  lbitset_weed (src);
+  lbitset_weed (dst);
+  for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+       selt && delt; selt = selt->next, delt = delt->next)
+    {
+      if (selt->index != delt->index)
+	return 0;
+
+      for (j = 0; j < LBITSET_ELT_WORDS; j++)
+	if (delt->words[j] != selt->words[j])
+	  return 0;
+    }
+  return ! selt && ! delt;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  */
+static inline void
+lbitset_copy (dst, src)
+     bitset dst;
+     bitset src;
+{
+  lbitset_elt *elt;
+  lbitset_elt *head;
+  lbitset_elt *prev;
+  lbitset_elt *tmp;
+
+  if (src == dst)
+    return;
+
+  lbitset_zero (dst);
+
+  head = LBITSET_HEAD (src);
+  if (!head)
+    return;
+
+  prev = 0;
+  for (elt = head; elt; elt = elt->next)
+    {
+      tmp = lbitset_elt_alloc ();
+      tmp->index = elt->index;
+      tmp->prev = prev;
+      tmp->next = 0;
+      if (prev)
+	prev->next = tmp;
+      else
+	LBITSET_HEAD (dst) = tmp;
+      prev = tmp;
+
+      memcpy (tmp->words, elt->words, sizeof (elt->words));
+    }
+  LBITSET_TAIL (dst) = tmp;
+
+  dst->csize = LBITSET_ELT_WORDS;
+  dst->cdata = LBITSET_HEAD (dst)->words;
+  dst->cindex = LBITSET_HEAD (dst)->index;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  Return non-zero if
+   bitsets different.  */
+static inline int
+lbitset_copy_compare (dst, src)
+     bitset dst;
+     bitset src;
+{
+  if (src == dst)
+    return 0;
+
+  if (! LBITSET_HEAD (dst))
+    {
+      lbitset_copy (dst, src);
+      return LBITSET_HEAD (src) != 0;
+    }
+
+  if (lbitset_equal_p (dst, src))
+    return 0;
+
+  lbitset_copy (dst, src);
+  return 1;
+}
+
+
+/* Return size in bits of bitset SRC.  */
+static int
+lbitset_size (src)
+     bitset src;
+{
+  lbitset_elt *elt;
+
+  elt = LBITSET_TAIL (src);
+  if (!elt)
+	return 0;
+
+  /* Return current size of bitset in bits.  */
+  return (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
+}
+
+
+/* Set bit BITNO in bitset DST.  */
+static void
+lbitset_set (dst, bitno)
+     bitset dst;
+     bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+
+  lbitset_elt_find (dst, index, LBITSET_CREATE);
+
+  dst->cdata[index - dst->cindex] |= (1 << (bitno % BITSET_WORD_BITS));
+}
+
+
+/* Reset bit BITNO in bitset DST.  */
+static void
+lbitset_reset (dst, bitno)
+     bitset dst;
+     bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+
+  if (!lbitset_elt_find (dst, index, LBITSET_FIND))
+      return;
+
+  dst->cdata[index - dst->cindex] &= ~(1 << (bitno % BITSET_WORD_BITS));
+
+  /* If all the data is zero, perhaps we should unlink it now...  */
+}
+
+
+/* Test bit BITNO in bitset SRC.  */
+static int
+lbitset_test (src, bitno)
+     bitset src;
+     bitset_bindex bitno;
+{
+  bitset_windex index = bitno / BITSET_WORD_BITS;
+
+  if (!lbitset_elt_find (src, index, LBITSET_FIND))
+    return 0;
+
+  return (src->cdata[index - src->cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
+}
+
+
+static void
+lbitset_free (bset)
+     bitset bset;
+{
+  lbitset_zero (bset);
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static int
+lbitset_reverse_list (bset, list, num, next)
+     bitset bset;
+     bitset_bindex *list;
+     bitset_bindex num;
+     bitset_bindex *next;
+{
+  bitset_bindex rbitno;
+  bitset_bindex bitno;
+  unsigned int bitcnt;
+  bitset_bindex bitoff;
+  bitset_windex index;
+  bitset_bindex count;
+  lbitset_elt *elt;
+  bitset_word word;
+  bitset_bindex n_bits;
+
+  elt = LBITSET_TAIL (bset);
+  if (!elt)
+    return 0;
+
+  n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
+  rbitno = *next;
+
+  if (rbitno >= n_bits)
+      return 0;
+
+  bitno = n_bits - (rbitno + 1);
+
+  index = bitno / BITSET_WORD_BITS;
+
+  /* Skip back to starting element.  */
+  for (; elt && elt->index > index; elt = elt->prev)
+    continue;
+
+  if (!elt)
+    return 0;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  count = 0;
+  bitcnt = bitno % BITSET_WORD_BITS;
+  bitoff = index * BITSET_WORD_BITS;
+
+  while (elt)
+    {
+      bitset_word *srcp = elt->words;
+
+      for (; (index - elt->index) < LBITSET_ELT_WORDS;
+	   index--, bitoff -= BITSET_WORD_BITS,
+	       bitcnt = BITSET_WORD_BITS - 1)
+	{
+	  word = srcp[index - elt->index] << (BITSET_WORD_BITS - 1 - bitcnt);
+
+	  for (; word; bitcnt--)
+	    {
+	      if (word & BITSET_MSB)
+		{
+		  list[count++] = bitoff + bitcnt;
+		  if (count >= num)
+		    {
+		      *next = n_bits - (bitoff + bitcnt);
+		      return count;
+		    }
+		}
+	      word <<= 1;
+	    }
+	}
+
+      elt = elt->prev;
+      if (elt)
+	{
+	  index = elt->index + LBITSET_ELT_WORDS - 1;
+	  bitoff = index * BITSET_WORD_BITS;
+	}
+    }
+
+  *next = n_bits - (bitoff + 1);
+  return count;
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static int
+lbitset_list (bset, list, num, next)
+     bitset bset;
+     bitset_bindex *list;
+     bitset_bindex num;
+     bitset_bindex *next;
+{
+  bitset_bindex bitno;
+  bitset_windex index;
+  bitset_bindex count;
+  lbitset_elt *elt;
+  lbitset_elt *head;
+  bitset_word word;
+
+  head = LBITSET_HEAD (bset);
+  if (!head)
+      return 0;
+
+  bitno = *next;
+  count = 0;
+
+  if (!bitno)
+    {
+      /* This is the most common case.  */
+
+      /* Start with the first element.  */
+      elt = head;
+      index = elt->index;
+      bitno = index * BITSET_WORD_BITS;
+    }
+  else
+    {
+      index = bitno / BITSET_WORD_BITS;
+
+      /* Skip to starting element.  */
+      for (elt = head;
+	   elt && (elt->index + LBITSET_ELT_WORDS - 1) < index;
+	   elt = elt->next)
+	continue;
+
+      if (!elt)
+	return 0;
+
+      if (index < elt->index)
+	{
+	  index = elt->index;
+	  bitno = index * BITSET_WORD_BITS;
+	}
+      else
+	{
+	  bitset_word *srcp = elt->words;
+
+	  /* We are starting within an element.  */
+
+	  for (; (index - elt->index) < LBITSET_ELT_WORDS; index++)
+	    {
+	      word = srcp[index - elt->index] >> (bitno % BITSET_WORD_BITS);
+
+	      for (; word; bitno++)
+		{
+		  if (word & 1)
+		    {
+		      list[count++] = bitno;
+		      if (count >= num)
+			{
+			  *next = bitno + 1;
+			  return count;
+			}
+		    }
+		  word >>= 1;
+		}
+	      bitno = (index + 1) * BITSET_WORD_BITS;
+	    }
+
+	  elt = elt->next;
+	  if (elt)
+	    {
+	      index = elt->index;
+	      bitno = index * BITSET_WORD_BITS;
+	    }
+	}
+    }
+
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  while (elt)
+    {
+      int i;
+      bitset_word *srcp = elt->words;
+
+      if ((count + LBITSET_ELT_BITS) < num)
+	{
+	  /* The coast is clear, plant boot!  */
+
+#if LBITSET_ELT_WORDS == 2
+	  word = srcp[0];
+	  if (word)
+	    {
+	      if (! (word & 0xffff))
+		{
+		  word >>= 16;
+		  bitno += 16;
+		}
+	      if (! (word & 0xff))
+		{
+		  word >>= 8;
+		  bitno += 8;
+		}
+	      for (; word; bitno++)
+		{
+		  if (word & 1)
+		    list[count++] = bitno;
+		  word >>= 1;
+		}
+	    }
+	  index++;
+	  bitno = index * BITSET_WORD_BITS;
+
+	  word = srcp[1];
+	  if (word)
+	    {
+	      if (! (word & 0xffff))
+		{
+		  word >>= 16;
+		  bitno += 16;
+		}
+	      for (; word; bitno++)
+		{
+		  if (word & 1)
+		    list[count++] = bitno;
+		  word >>= 1;
+		}
+	    }
+	  index++;
+	  bitno = index * BITSET_WORD_BITS;
+#else
+	  for (i = 0; i < LBITSET_ELT_WORDS; i++)
+	    {
+	      word = srcp[i];
+	      if (word)
+		{
+		  if (! (word & 0xffff))
+		    {
+		      word >>= 16;
+		      bitno += 16;
+		    }
+		  if (! (word & 0xff))
+		    {
+		      word >>= 8;
+		      bitno += 8;
+		    }
+		  for (; word; bitno++)
+		    {
+		      if (word & 1)
+			list[count++] = bitno;
+		      word >>= 1;
+		    }
+		}
+	      index++;
+	      bitno = index * BITSET_WORD_BITS;
+	    }
+#endif
+	}
+      else
+	{
+	  /* Tread more carefully since we need to check
+	     if array overflows.  */
+
+	  for (i = 0; i < LBITSET_ELT_WORDS; i++)
+	    {
+	      for (word = srcp[i]; word; bitno++)
+		{
+		  if (word & 1)
+		    {
+		      list[count++] = bitno;
+		      if (count >= num)
+			{
+			  *next = bitno + 1;
+			  return count;
+			}
+		    }
+		  word >>= 1;
+		}
+	      index++;
+	      bitno = index * BITSET_WORD_BITS;
+	    }
+	}
+
+      elt = elt->next;
+      if (elt)
+	{
+	  index = elt->index;
+	  bitno = index * BITSET_WORD_BITS;
+	}
+    }
+
+  *next = bitno;
+  return count;
+}
+
+
+static int
+lbitset_op1 (dst, op)
+     bitset dst;
+     enum bitset_ops op;
+{
+  unsigned int i;
+  bitset_windex index;
+  lbitset_elt *elt;
+
+  switch (op)
+    {
+    case BITSET_ZERO:
+      lbitset_zero (dst);
+      break;
+
+    case BITSET_ONES:
+      /* This is a decidedly unfriendly operation for a linked list
+	 bitset!   */
+      elt = LBITSET_TAIL (dst);
+      /* Ignore empty set.  */
+      if (!elt)
+	return 0;
+
+      index = elt->index;
+      for (i = 0; i < index; i += LBITSET_ELT_WORDS)
+	{
+	  /* Create new elements if they cannot be found.  */
+	  elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+	  memset (elt->words, ~0, sizeof (elt->words));
+	}
+      break;
+
+    case BITSET_EMPTY_P:
+      lbitset_weed (dst);
+      if (LBITSET_HEAD (dst))
+	return 0;
+      break;
+
+    default:
+      abort ();
+    }
+
+  return 1;
+}
+
+
+static int
+lbitset_op2 (dst, src, op)
+     bitset dst;
+     bitset src;
+     enum bitset_ops op;
+{
+  lbitset_elt *elt;
+  lbitset_elt *selt;
+  lbitset_elt *delt;
+  unsigned int i;
+  unsigned int j;
+  bitset_windex index;
+
+  switch (op)
+    {
+    case BITSET_COPY:
+      lbitset_copy (dst, src);
+      break;
+
+    case BITSET_NOT:
+      /* This is another unfriendly operation for a linked list
+	 bitset!  */
+      elt = LBITSET_TAIL (dst);
+      /* Ignore empty set.  */
+      if (!elt)
+	return 0;
+
+      index = elt->index;
+      for (i = 0; i < index; i += LBITSET_ELT_WORDS)
+	{
+	  /* Create new elements for dst if they cannot be found
+	     or substitute zero elements if src elements not found.  */
+	  selt = lbitset_elt_find (dst, i, LBITSET_SUBST);
+	  delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+
+	  for (j = 0; j < LBITSET_ELT_WORDS; j++)
+	    delt->words[j] = ~selt->words[j];
+	}
+      lbitset_weed (dst);
+      break;
+
+    case BITSET_EQUAL_P:
+      return lbitset_equal_p (dst, src);
+      break;
+
+    case BITSET_SUBSET_P:
+      for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+	   selt || delt; selt = selt->next, delt = delt->next)
+	{
+	  if (!selt)
+	    selt = &lbitset_zero_elts[0];
+	  else if (!delt)
+	    delt = &lbitset_zero_elts[0];
+	  else if (selt->index != delt->index)
+	    {
+	      if (selt->index < delt->index)
+		{
+		  lbitset_zero_elts[2].next = delt;
+		  delt = &lbitset_zero_elts[2];
+		}
+	      else
+		{
+		  lbitset_zero_elts[1].next = selt;
+		  selt = &lbitset_zero_elts[1];
+		}
+	    }
+
+	  for (j = 0; j < LBITSET_ELT_WORDS; j++)
+	    if (delt->words[j] != (selt->words[j] | delt->words[j]))
+	      return 0;
+	}
+      break;
+
+    default:
+      abort ();
+    }
+
+  return 1;
+}
+
+
+static int
+lbitset_op3 (dst, src1, src2, op)
+     bitset dst;
+     bitset src1;
+     bitset src2;
+     enum bitset_ops op;
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+  lbitset_elt *delt = LBITSET_HEAD (dst);
+  bitset_windex index1;
+  bitset_windex index2;
+  bitset_windex index;
+  lbitset_elt *stmp1;
+  lbitset_elt *stmp2;
+  lbitset_elt *dtmp;
+  bitset_word *srcp1;
+  bitset_word *srcp2;
+  bitset_word *dstp;
+  int changed = 0;
+  unsigned int i;
+
+  /* Fast track common, simple cases.  */
+  if (!selt2)
+    {
+      if (op == BITSET_AND)
+	{
+	  lbitset_weed (dst);
+	  changed = ! LBITSET_HEAD (dst);
+	  lbitset_zero (dst);
+	  return changed;
+	}
+      else if (op == BITSET_ANDN || op == BITSET_OR || op == BITSET_XOR)
+	{
+	  return lbitset_copy_compare (dst, src1);
+	}
+    }
+  else if (!selt1)
+    {
+      if (op == BITSET_AND || op == BITSET_ANDN)
+	{
+	  lbitset_weed (dst);
+	  changed = ! LBITSET_HEAD (dst);
+	  lbitset_zero (dst);
+	  return changed;
+	}
+      else if (op == BITSET_OR || op == BITSET_XOR)
+	{
+	  return lbitset_copy_compare (dst, src2);
+	}
+    }
+
+
+  LBITSET_HEAD (dst) = 0;
+  dst->csize = 0;
+
+  index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
+  index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
+
+  while (selt1 || selt2)
+    {
+      /* Figure out whether we need to substitute zero elements for
+	 missing links.  */
+      if (index1 == index2)
+	{
+	  index = index1;
+	  stmp1 = selt1;
+	  stmp2 = selt2;
+	  selt1 = selt1->next;
+	  index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
+	  selt2 = selt2->next;
+	  index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
+	}
+      else if (index1 < index2)
+	{
+	  index = index1;
+	  stmp1 = selt1;
+	  stmp2 = &lbitset_zero_elts[0];
+	  selt1 = selt1->next;
+	  index1 = (selt1) ? selt1->index : BITSET_INDEX_MAX;
+	}
+      else
+	{
+	  index = index2;
+	  stmp1 = &lbitset_zero_elts[0];
+	  stmp2 = selt2;
+	  selt2 = selt2->next;
+	  index2 = (selt2) ? selt2->index : BITSET_INDEX_MAX;
+	}
+
+      /* Find the appropriate element from DST.  Begin by discarding
+	 elements that we've skipped.  */
+      while (delt && delt->index < index)
+	{
+	  changed = 1;
+	  dtmp = delt;
+	  delt = delt->next;
+	  lbitset_elt_free (dtmp);
+	}
+      if (delt && delt->index == index)
+	{
+	  dtmp = delt;
+	  delt = delt->next;
+	}
+      else
+	dtmp = lbitset_elt_calloc ();
+
+      /* Do the operation, and if any bits are set, link it into the
+	 linked list.  */
+      srcp1 = stmp1->words;
+      srcp2 = stmp2->words;
+      dstp = dtmp->words;
+      switch (op)
+	{
+	case BITSET_OR:
+	  for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ | *srcp2++;
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_AND:
+	  for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ & *srcp2++;
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_XOR:
+	  for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ ^ *srcp2++;
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_ANDN:
+	  for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	case BITSET_ORN:
+	  for (i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+	    {
+	      bitset_word tmp = *srcp1++ | ~(*srcp2++);
+
+	      if (*dstp != tmp)
+		{
+		  changed = 1;
+		  *dstp = tmp;
+		}
+	    }
+	  break;
+
+	default:
+	  abort ();
+	}
+
+      if (! lbitset_elt_zero_p (dtmp))
+	{
+	  dtmp->index = index;
+	  /* Perhaps this could be optimised...  */
+	  lbitset_elt_link (dst, dtmp);
+	}
+      else
+	{
+	  lbitset_elt_free (dtmp);
+	}
+    }
+
+  /* If we have elements of DST left over, free them all.  */
+  if (delt)
+    {
+      changed = 1;
+      lbitset_prune (dst, delt);
+    }
+
+  return changed;
+}
+
+
+static int
+lbitset_op4 (dst, src1, src2, src3, op)
+     bitset dst;
+     bitset src1;
+     bitset src2;
+     bitset src3;
+     enum bitset_ops op;
+{
+  int changed = 0;
+  bitset tmp;
+
+#ifdef ENABLE_CHECKING
+  /* Check for compatiblity.  */
+  if (src1->ops != dst->ops || src2->ops != dst->ops || src3->ops != dst->ops)
+    abort ();
+#endif
+
+  tmp = bitset_create (BITSET_LIST, 0);
+
+  switch (op)
+    {
+    case BITSET_OR_AND:
+      bitset_or (tmp, src1, src2);
+      changed = bitset_and (dst, src3, tmp);
+      break;
+
+    case BITSET_AND_OR:
+      bitset_and (tmp, src1, src2);
+      changed = bitset_or (dst, src3, tmp);
+      break;
+
+    case BITSET_ANDN_OR:
+      bitset_andn (tmp, src1, src2);
+      changed = bitset_or (dst, src3, tmp);
+      break;
+
+    default:
+      abort ();
+    }
+
+  bitset_free (tmp);
+  return changed;
+}
+
+
+/* Vector of operations for linked-list bitsets.  */
+struct bitset_ops_struct lbitset_ops =
+  {
+    lbitset_set,
+    lbitset_reset,
+    lbitset_test,
+    lbitset_size,
+    lbitset_op1,
+    lbitset_op2,
+    lbitset_op3,
+    lbitset_op4,
+    lbitset_list,
+    lbitset_reverse_list,
+    lbitset_free,
+    BITSET_LIST
+  };
+
+
+/* Return size of initial structure.  */
+int
+lbitset_bytes (n_bits)
+     bitset_bindex n_bits ATTRIBUTE_UNUSED;
+{
+  return sizeof (struct bitset_struct);
+}
+
+
+/* Initialize a bitset.  */
+
+bitset
+lbitset_init (bset, n_bits)
+     bitset bset;
+     bitset_bindex n_bits ATTRIBUTE_UNUSED;
+{
+  LBITSET_HEAD (bset) = 0;
+  LBITSET_TAIL (bset) = 0;
+
+  bset->ops = &lbitset_ops;
+
+  bset->cindex = 0;
+  /* Disable cache until have some elements allocated.
+     If we have variable length arrays, then we may
+     need to allocate dummy element.  */
+  bset->csize = 0;
+  bset->cdata = 0;
+  return bset;
+}
+
+
+void
+lbitset_release_memory ()
+{
+  lbitset_free_list = 0;
+  if (lbitset_obstack_init)
+    {
+      lbitset_obstack_init = 0;
+      obstack_free (&lbitset_obstack, NULL);
+    }
+}
diff --git a/lib/lbitset.h b/lib/lbitset.h
new file mode 100644
index 00000000..9af651f1
--- /dev/null
+++ b/lib/lbitset.h
@@ -0,0 +1,62 @@
+/* Functions to support lbitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef _LBITSET_H
+#define _LBITSET_H
+
+#include "bitset-int.h"
+
+/* Number of words to use for each element.  The larger the value the
+   greater the size of the cache and the shorter the time to find a given bit
+   but the more memory wasted for sparse bitsets and the longer the time
+   to search for set bits.  */
+#ifndef LBITSET_ELT_WORDS
+#define LBITSET_ELT_WORDS 2
+#endif
+
+typedef bitset_word lbitset_word;
+#define LBITSET_WORD_BITS BITSET_WORD_BITS
+
+/* Number of bits stored in each element.  */
+#define LBITSET_ELT_BITS \
+  ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
+
+/* Lbitset element.   We use an array of bits for each element.
+   These are linked together in a doubly-linked list.  */
+typedef struct lbitset_elt_struct
+{
+  struct lbitset_elt_struct *next; /* Next element.  */
+  struct lbitset_elt_struct *prev; /* Previous element.  */
+  bitset_windex index;		/* bitno / BITSET_WORD_BITS.  */
+  bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set.  */
+} lbitset_elt;
+
+
+/* Head of lbitset linked list.  */
+typedef struct lbitset_struct
+{
+  lbitset_elt *head;		/* First element in linked list.  */
+  lbitset_elt *tail;		/* Last element in linked list.  */
+} *lbitset;
+
+
+extern int lbitset_bytes PARAMS ((bitset_bindex));
+
+extern void lbitset_release_memory PARAMS ((void));
+
+#endif
diff --git a/lib/sbitset.c b/lib/sbitset.c
new file mode 100644
index 00000000..807b71dd
--- /dev/null
+++ b/lib/sbitset.c
@@ -0,0 +1,672 @@
+/* Simple bitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include "bitset.h"
+#include <stdlib.h>
+
+# if WITH_DMALLOC
+#  define DMALLOC_FUNC_CHECK
+#  include <dmalloc.h>
+# endif /* WITH_DMALLOC */
+
+/* This file implements fixed size bitsets stored as an array
+   of words.  Any unused bits in the last word must be zero.  */
+
+static void sbitset_unused_clear PARAMS((bitset));
+
+static int sbitset_small_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
+				      bitset_bindex *));
+
+static void sbitset_set PARAMS((bitset, bitset_bindex));
+static void sbitset_reset PARAMS((bitset, bitset_bindex));
+static int sbitset_test PARAMS((bitset, bitset_bindex));
+static int sbitset_size PARAMS((bitset));
+static int sbitset_op1 PARAMS((bitset, enum bitset_ops));
+static int sbitset_op2 PARAMS((bitset, bitset, enum bitset_ops));
+static int sbitset_op3 PARAMS((bitset, bitset, bitset, enum bitset_ops));
+static int sbitset_op4 PARAMS((bitset, bitset, bitset, bitset,
+			       enum bitset_ops));
+static int sbitset_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
+				bitset_bindex *));
+static int sbitset_reverse_list PARAMS((bitset, bitset_bindex *, bitset_bindex,
+					bitset_bindex *));
+
+#define SBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
+#define SBITSET_WORDS(X) ((X)->u.s.words)
+#define SBITSET_N_BITS(X) ((X)->u.s.n_bits)
+
+
+/* Return size in bits of bitset SRC.  */
+static int
+sbitset_size (src)
+     bitset src;
+{
+    return SBITSET_N_BITS (src);
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static int
+sbitset_small_list (src, list, num, next)
+     bitset src;
+     bitset_bindex *list;
+     bitset_bindex num;
+     bitset_bindex *next;
+{
+  bitset_bindex bitno;
+  bitset_bindex count;
+  bitset_windex size;
+  bitset_word word;
+
+  word = SBITSET_WORDS (src)[0];
+
+  /* Short circuit common case.  */
+  if (!word)
+    return 0;
+
+  size = SBITSET_N_BITS (src);
+  bitno = *next;
+  if (bitno >= size)
+    return 0;
+
+  word >>= bitno;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  if (num >= BITSET_WORD_BITS)
+  {
+      for (count = 0; word; bitno++)
+      {
+	  if (word & 1)
+	      list[count++] = bitno;
+	  word >>= 1;
+      }
+  }
+  else
+  {
+      for (count = 0; word; bitno++)
+      {
+	  if (word & 1)
+	  {
+	      list[count++] = bitno;
+	      if (count >= num)
+	      {
+		  bitno++;
+		  break;
+	      }
+	  }
+	  word >>= 1;
+      }
+  }
+
+  *next = bitno;
+  return count;
+}
+
+
+/* Set bit BITNO in bitset DST.  */
+static void
+sbitset_set (dst, bitno)
+     bitset dst ATTRIBUTE_UNUSED;
+     bitset_bindex bitno ATTRIBUTE_UNUSED;
+{
+    /* This should never occur for sbitsets.  */
+    abort ();
+}
+
+
+/* Reset bit BITNO in bitset DST.  */
+static void
+sbitset_reset (dst, bitno)
+     bitset dst ATTRIBUTE_UNUSED;
+     bitset_bindex bitno ATTRIBUTE_UNUSED;
+{
+    /* This should never occur for sbitsets.  */
+    abort ();
+}
+
+
+/* Test bit BITNO in bitset SRC.  */
+static int
+sbitset_test (src, bitno)
+     bitset src ATTRIBUTE_UNUSED;
+     bitset_bindex bitno ATTRIBUTE_UNUSED;
+{
+    /* This should never occur for sbitsets.  */
+    abort ();
+    return 0;
+}
+
+
+/* Find list of up to NUM bits set in BSET in reverse order, starting
+   from and including NEXT and store in array LIST.  Return with
+   actual number of bits found and with *NEXT indicating where search
+   stopped.  */
+static int
+sbitset_reverse_list (src, list, num, next)
+     bitset src;
+     bitset_bindex *list;
+     bitset_bindex num;
+     bitset_bindex *next;
+{
+  bitset_bindex bitno;
+  bitset_bindex rbitno;
+  bitset_bindex count;
+  bitset_windex index;
+  unsigned int bitcnt;
+  bitset_bindex bitoff;
+  bitset_word word;
+  bitset_word *srcp = SBITSET_WORDS (src);
+  bitset_bindex n_bits = SBITSET_N_BITS (src);
+
+  rbitno = *next;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  if (rbitno >= n_bits)
+      return 0;
+
+  count = 0;
+
+  bitno = n_bits - (rbitno + 1);
+
+  index = bitno / BITSET_WORD_BITS;
+  bitcnt = bitno % BITSET_WORD_BITS;
+  bitoff = index * BITSET_WORD_BITS;
+
+  for (; index != ~0U; index--, bitoff -= BITSET_WORD_BITS,
+	   bitcnt = BITSET_WORD_BITS - 1)
+    {
+      word = srcp[index] << (BITSET_WORD_BITS - 1 - bitcnt);
+      for (; word; bitcnt--)
+	{
+	  if (word & BITSET_MSB)
+	    {
+	      list[count++] = bitoff + bitcnt;
+	      if (count >= num)
+		{
+		  *next = n_bits - (bitoff + bitcnt);
+		  return count;
+		}
+	    }
+	  word <<= 1;
+	}
+    }
+
+  *next = n_bits - (bitoff + 1);
+  return count;
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static int
+sbitset_list (src, list, num, next)
+     bitset src;
+     bitset_bindex *list;
+     bitset_bindex num;
+     bitset_bindex *next;
+{
+  bitset_bindex bitno;
+  bitset_bindex count;
+  bitset_windex index;
+  bitset_bindex bitoff;
+  bitset_windex size = src->csize;
+  bitset_word *srcp = SBITSET_WORDS (src);
+  bitset_word word;
+
+  bitno = *next;
+
+  count = 0;
+  if (! bitno)
+    {
+      /* Many bitsets are zero, so make this common case fast.  */
+      for (index = 0; index < size && ! srcp[index]; index++)
+	continue;
+      if (index >= size)
+	return 0;
+
+      /* If num is 1, we could speed things up with a binary search
+	 of the current word.  */
+
+      bitoff = index * BITSET_WORD_BITS;
+    }
+  else
+    {
+      if (bitno >= SBITSET_N_BITS (src))
+	return 0;
+
+      index = bitno / BITSET_WORD_BITS;
+      bitno = bitno % BITSET_WORD_BITS;
+
+      if (bitno)
+	{
+	  /* Handle the case where we start within a word.
+	     Most often, this is executed with large bitsets
+	     with many set bits where we filled the array
+	     on the previous call to this function.  */
+
+	  bitoff = index * BITSET_WORD_BITS;
+	  word = srcp[index] >> bitno;
+	  for (bitno = bitoff + bitno; word; bitno++)
+	    {
+	      if (word & 1)
+		{
+		  list[count++] = bitno;
+		  if (count >= num)
+		    {
+		      *next = bitno + 1;
+		      return count;
+		    }
+		}
+	      word >>= 1;
+	    }
+	  index++;
+	}
+      bitoff = index * BITSET_WORD_BITS;
+    }
+
+  for (; index < size; index++, bitoff += BITSET_WORD_BITS)
+    {
+      if (! (word = srcp[index]))
+	continue;
+
+      if ((count + BITSET_WORD_BITS) < num)
+      {
+	for (bitno = bitoff; word; bitno++)
+	  {
+	    if (word & 1)
+	      list[count++] = bitno;
+	    word >>= 1;
+	  }
+      }
+      else
+	{
+	  for (bitno = bitoff; word; bitno++)
+	    {
+	      if (word & 1)
+		{
+		  list[count++] = bitno;
+		  if (count >= num)
+		    {
+		      *next = bitno + 1;
+		      return count;
+		    }
+		}
+	      word >>= 1;
+	    }
+	}
+    }
+
+  *next = bitoff;
+  return count;
+}
+
+
+/* Ensure that any unused bits within the last word are clear.  */
+static inline void
+sbitset_unused_clear (dst)
+     bitset dst;
+{
+  unsigned int last_bit;
+
+  last_bit = SBITSET_N_BITS (dst) % BITSET_WORD_BITS;
+  if (last_bit)
+    SBITSET_WORDS (dst)[dst->csize - 1] &= (bitset_word)((1 << last_bit) - 1);
+}
+
+
+static int
+sbitset_op1 (dst, op)
+     bitset dst;
+     enum bitset_ops op;
+{
+  unsigned int i;
+  bitset_word *dstp = SBITSET_WORDS (dst);
+  unsigned int bytes;
+
+  bytes = sizeof (bitset_word) * dst->csize;
+
+  switch (op)
+    {
+    case BITSET_ZERO:
+      memset (dstp, 0, bytes);
+      break;
+
+    case BITSET_ONES:
+      memset (dstp, ~0, bytes);
+      sbitset_unused_clear (dst);
+      break;
+
+    case BITSET_EMPTY_P:
+      for (i = 0; i < dst->csize; i++)
+	if (dstp[i])
+	  return 0;
+      break;
+
+    default:
+      abort ();
+    }
+
+  return 1;
+}
+
+
+static int
+sbitset_op2 (dst, src, op)
+     bitset dst;
+     bitset src;
+     enum bitset_ops op;
+{
+  unsigned int i;
+  bitset_word *srcp = SBITSET_WORDS (src);
+  bitset_word *dstp = SBITSET_WORDS (dst);
+  bitset_windex size = dst->csize;
+
+#ifdef ENABLE_CHECKING
+  /* Check for compatiblity.  */
+  if (src->ops != dst->ops || SBITSET_N_BITS (src) != SBITSET_N_BITS (dst))
+    abort ();
+#endif
+
+  switch (op)
+    {
+    case BITSET_COPY:
+      if (srcp == dstp)
+	break;
+      memcpy (dstp, srcp, sizeof (bitset_word) * size);
+      break;
+
+    case BITSET_NOT:
+      for (i = 0; i < size; i++)
+	*dstp++ = ~(*srcp++);
+      sbitset_unused_clear (dst);
+      break;
+
+    case BITSET_EQUAL_P:
+      for (i = 0; i < size; i++)
+	if (*dstp++ != *srcp++)
+	  return 0;
+      break;
+
+    case BITSET_SUBSET_P:
+      for (i = 0; i < size; i++, dstp++, srcp++)
+	{
+	  if (*dstp != (*srcp | *dstp))
+	    return 0;
+	}
+      break;
+
+    default:
+      abort ();
+    }
+
+  return 1;
+}
+
+
+static int
+sbitset_op3 (dst, src1, src2, op)
+     bitset dst;
+     bitset src1;
+     bitset src2;
+     enum bitset_ops op;
+{
+  unsigned int i;
+  int changed = 0;
+  bitset_word *src1p = SBITSET_WORDS (src1);
+  bitset_word *src2p = SBITSET_WORDS (src2);
+  bitset_word *dstp = SBITSET_WORDS (dst);
+  bitset_windex size = dst->csize;
+
+#ifdef ENABLE_CHECKING
+  /* Check for compatiblity.  */
+  if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
+      || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst))
+    abort ();
+#endif
+
+  switch (op)
+    {
+    case BITSET_OR:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = *src1p++ | *src2p++;
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      break;
+
+    case BITSET_AND:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = *src1p++ & *src2p++;
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      break;
+
+    case BITSET_XOR:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = *src1p++ ^ *src2p++;
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      break;
+
+    case BITSET_ANDN:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = *src1p++ & ~(*src2p++);
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      break;
+
+    case BITSET_ORN:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = *src1p++ | ~(*src2p++);
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      sbitset_unused_clear (dst);
+      break;
+
+    default:
+      abort ();
+    }
+
+  return changed;
+}
+
+
+static int
+sbitset_op4 (dst, src1, src2, src3, op)
+     bitset dst;
+     bitset src1;
+     bitset src2;
+     bitset src3;
+     enum bitset_ops op;
+{
+  unsigned int i;
+  int changed = 0;
+  bitset_word *src1p = SBITSET_WORDS (src1);
+  bitset_word *src2p = SBITSET_WORDS (src2);
+  bitset_word *src3p = SBITSET_WORDS (src3);
+  bitset_word *dstp = SBITSET_WORDS (dst);
+  bitset_windex size = dst->csize;
+
+#ifdef ENABLE_CHECKING
+  /* Check for compatiblity.  */
+  if (src1->ops != dst->ops || SBITSET_N_BITS (src1) != SBITSET_N_BITS (dst)
+      || src2->ops != dst->ops || SBITSET_N_BITS (src2) != SBITSET_N_BITS (dst)
+      || src3->ops != dst->ops || SBITSET_N_BITS (src3) != SBITSET_N_BITS (dst))
+    abort ();
+#endif
+
+  switch (op)
+    {
+    case BITSET_OR_AND:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      break;
+
+    case BITSET_AND_OR:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      break;
+
+    case BITSET_ANDN_OR:
+      for (i = 0; i < size; i++, dstp++)
+	{
+	  bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
+
+	  if (*dstp != tmp)
+	    {
+	      changed = 1;
+	      *dstp = tmp;
+	    }
+	}
+      break;
+
+    default:
+      abort ();
+    }
+
+  return changed;
+}
+
+
+/* Vector of operations for single word bitsets.  */
+struct bitset_ops_struct sbitset_small_ops =
+  {
+    sbitset_set,
+    sbitset_reset,
+    sbitset_test,
+    sbitset_size,
+    sbitset_op1,
+    sbitset_op2,
+    sbitset_op3,
+    sbitset_op4,
+    sbitset_small_list,
+    sbitset_reverse_list,
+    NULL,
+    BITSET_ARRAY
+  };
+
+
+/* Vector of operations for multiple word bitsets.  */
+struct bitset_ops_struct sbitset_ops =
+  {
+    sbitset_set,
+    sbitset_reset,
+    sbitset_test,
+    sbitset_size,
+    sbitset_op1,
+    sbitset_op2,
+    sbitset_op3,
+    sbitset_op4,
+    sbitset_list,
+    sbitset_reverse_list,
+    NULL,
+    BITSET_ARRAY
+};
+
+
+int
+sbitset_bytes (n_bits)
+     bitset_bindex n_bits;
+{
+  unsigned int bytes, size;
+
+  size = SBITSET_N_WORDS (n_bits);
+  bytes = size * sizeof (bitset_word);
+  return sizeof (struct bitset_struct) + bytes - sizeof (bitset_word);
+}
+
+
+bitset
+sbitset_init (bset, n_bits)
+     bitset bset;
+     bitset_bindex n_bits;
+{
+  bitset_windex size;
+
+  size = SBITSET_N_WORDS (n_bits);
+  SBITSET_N_BITS (bset) = n_bits;
+
+  /* Use optimized routines if bitset fits within a single word.
+     There is probably little merit if using caching since
+     the small bitset will always fit in the cache.  */
+  if (size == 1)
+    bset->ops = &sbitset_small_ops;
+  else
+    bset->ops = &sbitset_ops;
+
+  bset->cindex = 0;
+  bset->csize = size;
+  bset->cdata = SBITSET_WORDS (bset);
+  return bset;
+}
diff --git a/lib/sbitset.h b/lib/sbitset.h
new file mode 100644
index 00000000..777feea1
--- /dev/null
+++ b/lib/sbitset.h
@@ -0,0 +1,33 @@
+/* Functions to support sbitsets.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+This program 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 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+#ifndef _SBITSET_H
+#define _SBITSET_H
+
+#include "bitset-int.h"
+
+typedef struct sbitset_struct
+{
+    unsigned int n_bits;	/* Number of bits.  */
+    bitset_word words[1];	/* The array of bits.  */
+} *sbitset;
+
+
+extern int sbitset_bytes PARAMS ((bitset_bindex));
+
+#endif