Initial checkin of GCC 4.9.0 from trunk (r208799).

Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba

1 files changed, 265 insertions, 0 deletions

diff --git a/gcc-4.9/gcc/sbitmap.h b/gcc-4.9/gcc/sbitmap.h
new file mode 100644
index 000000000..487e39228
--- /dev/null
+++ b/gcc-4.9/gcc/sbitmap.h
@@ -0,0 +1,265 @@
+/* Simple bitmaps.
+   Copyright (C) 1999-2014 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_SBITMAP_H
+#define GCC_SBITMAP_H
+
+/* Implementation of sets using simple bitmap vectors.
+
+   This set representation is suitable for non-sparse sets with a known
+   (a priori) universe.  The set is represented as a simple array of the
+   host's fastest unsigned integer.  For a given member I in the set:
+     - the element for I will be at sbitmap[I / (bits per element)]
+     - the position for I within element is I % (bits per element)
+
+   This representation is very space-efficient for large non-sparse sets
+   with random access patterns.
+
+   The following operations can be performed in O(1) time:
+
+     * set_size			: SBITMAP_SIZE
+     * member_p			: bitmap_bit_p
+     * add_member		: bitmap_set_bit
+     * remove_member		: bitmap_clear_bit
+
+   Most other operations on this set representation are O(U) where U is
+   the size of the set universe:
+
+     * clear			: bitmap_clear
+     * choose_one		: bitmap_first_set_bit /
+				  bitmap_last_set_bit
+     * forall			: EXECUTE_IF_SET_IN_BITMAP
+     * set_copy			: bitmap_copy
+     * set_intersection		: bitmap_and
+     * set_union		: bitmap_ior
+     * set_difference		: bitmap_and_compl
+     * set_disjuction		: (not implemented)
+     * set_compare		: bitmap_equal_p
+
+   Some operations on 3 sets that occur frequently in in data flow problems
+   are also implemented:
+
+      * A | (B & C)		: bitmap_or_and
+      * A | (B & ~C)		: bitmap_ior_and_compl
+      * A & (B | C)		: bitmap_and_or
+
+   Most of the set functions have two variants: One that returns non-zero
+   if members were added or removed from the target set, and one that just
+   performs the operation without feedback.  The former operations are a
+   bit more expensive but the result can often be used to avoid iterations
+   on other sets.
+
+   Allocating a bitmap is done with sbitmap_alloc, and resizing is
+   performed with sbitmap_resize.
+
+   The storage requirements for simple bitmap sets is O(U) where U is the
+   size of the set universe (colloquially the number of bits in the bitmap).
+
+   This set representation works well for relatively small data flow problems
+   (there are special routines for that, see sbitmap_vector_*).  The set
+   operations can be vectorized and there is almost no computating overhead,
+   so that even sparse simple bitmap sets outperform dedicated sparse set
+   representations like linked-list bitmaps.  For larger problems, the size
+   overhead of simple bitmap sets gets too high and other set representations
+   have to be used.  */
+
+#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
+#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
+
+struct simple_bitmap_def
+{
+  unsigned char *popcount;      /* Population count.  */
+  unsigned int n_bits;		/* Number of bits.  */
+  unsigned int size;		/* Size in elements.  */
+  SBITMAP_ELT_TYPE elms[1];	/* The elements.  */
+};
+
+/* Return the set size needed for N elements.  */
+#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
+
+/* Return the number of bits in BITMAP.  */
+#define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
+
+/* Test if bit number bitno in the bitmap is set.  */
+static inline SBITMAP_ELT_TYPE
+bitmap_bit_p (const_sbitmap map, int bitno)
+{
+  size_t i = bitno / SBITMAP_ELT_BITS;
+  unsigned int s = bitno % SBITMAP_ELT_BITS;
+  return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1;
+}
+
+/* Set bit number BITNO in the sbitmap MAP.  */
+
+static inline void
+bitmap_set_bit (sbitmap map, int bitno)
+{
+  gcc_checking_assert (! map->popcount);
+  map->elms[bitno / SBITMAP_ELT_BITS]
+    |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
+}
+
+/* Reset bit number BITNO in the sbitmap MAP.  */
+
+static inline void
+bitmap_clear_bit (sbitmap map, int bitno)
+{
+  gcc_checking_assert (! map->popcount);
+  map->elms[bitno / SBITMAP_ELT_BITS]
+    &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
+}
+
+/* The iterator for sbitmap.  */
+struct sbitmap_iterator {
+  /* The pointer to the first word of the bitmap.  */
+  const SBITMAP_ELT_TYPE *ptr;
+
+  /* The size of the bitmap.  */
+  unsigned int size;
+
+  /* The current word index.  */
+  unsigned int word_num;
+
+  /* The current bit index (not modulo SBITMAP_ELT_BITS).  */
+  unsigned int bit_num;
+
+  /* The words currently visited.  */
+  SBITMAP_ELT_TYPE word;
+};
+
+/* Initialize the iterator I with sbitmap BMP and the initial index
+   MIN.  */
+
+static inline void
+bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp,
+		   unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED)
+{
+  i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
+  i->bit_num = min;
+  i->size = bmp->size;
+  i->ptr = bmp->elms;
+
+  if (i->word_num >= i->size)
+    i->word = 0;
+  else
+    i->word = (i->ptr[i->word_num]
+	       >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
+}
+
+/* Return true if we have more bits to visit, in which case *N is set
+   to the index of the bit to be visited.  Otherwise, return
+   false.  */
+
+static inline bool
+bmp_iter_set (sbitmap_iterator *i, unsigned int *n)
+{
+  /* Skip words that are zeros.  */
+  for (; i->word == 0; i->word = i->ptr[i->word_num])
+    {
+      i->word_num++;
+
+      /* If we have reached the end, break.  */
+      if (i->word_num >= i->size)
+	return false;
+
+      i->bit_num = i->word_num * SBITMAP_ELT_BITS;
+    }
+
+  /* Skip bits that are zero.  */
+  for (; (i->word & 1) == 0; i->word >>= 1)
+    i->bit_num++;
+
+  *n = i->bit_num;
+
+  return true;
+}
+
+/* Advance to the next bit.  */
+
+static inline void
+bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED)
+{
+  i->word >>= 1;
+  i->bit_num++;
+}
+
+/* Loop over all elements of SBITMAP, starting with MIN.  In each
+   iteration, N is set to the index of the bit being visited.  ITER is
+   an instance of sbitmap_iterator used to iterate the bitmap.  */
+
+#ifndef EXECUTE_IF_SET_IN_BITMAP
+/* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP.  */
+#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)	\
+  for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));	\
+       bmp_iter_set (&(ITER), &(BITNUM));			\
+       bmp_iter_next (&(ITER), &(BITNUM)))
+#endif
+
+inline void sbitmap_free (sbitmap map)
+{
+  free (map->popcount);
+  free (map);
+}
+
+inline void sbitmap_vector_free (sbitmap * vec)
+{
+  free (vec);
+}
+
+extern void dump_bitmap (FILE *, const_sbitmap);
+extern void debug_raw (const simple_bitmap_def &ref);
+extern void debug_raw (const simple_bitmap_def *ptr);
+extern void dump_bitmap_file (FILE *, const_sbitmap);
+extern void debug (const simple_bitmap_def &ref);
+extern void debug (const simple_bitmap_def *ptr);
+extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *,
+				 int);
+extern sbitmap sbitmap_alloc (unsigned int);
+extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
+extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
+extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
+extern void bitmap_copy (sbitmap, const_sbitmap);
+extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
+extern bool bitmap_empty_p (const_sbitmap);
+extern void bitmap_clear (sbitmap);
+extern void bitmap_ones (sbitmap);
+extern void bitmap_vector_clear (sbitmap *, unsigned int);
+extern void bitmap_vector_ones (sbitmap *, unsigned int);
+
+extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap,
+				      const_sbitmap, const_sbitmap);
+extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap);
+extern void bitmap_not (sbitmap, const_sbitmap);
+extern bool bitmap_or_and (sbitmap, const_sbitmap,
+				     const_sbitmap, const_sbitmap);
+extern bool bitmap_and_or (sbitmap, const_sbitmap,
+				     const_sbitmap, const_sbitmap);
+extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap);
+extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap);
+extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap);
+extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap);
+extern bool bitmap_subset_p (const_sbitmap, const_sbitmap);
+
+extern int bitmap_first_set_bit (const_sbitmap);
+extern int bitmap_last_set_bit (const_sbitmap);
+
+extern void debug_bitmap (const_sbitmap);
+extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
+extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
+#endif /* ! GCC_SBITMAP_H */