* bitmap.h: Add explanation of sparse set as linked-list bitmap.

	* sbitmap.h: Add explanation about non-sparse sets as simple bitmap.
	(TEST_BIT): Make a static inline function for stronger type checking.
	(SET_BIT): Don't handle sbitmaps with popcount.
	(RESET_BIT): Likewise.
	(SET_BIT_WITH_POPCOUNT): New, like SET_BIT but with popcount.
	(RESET_BIT_WITH_POPCOUNT): New, like RESET_BIT but with popcount.
	* ebitmap.c (ebitmap_clear_bit): Use SET_BIT_WITH_POPCOUNT and
	RESET_BIT_WITH_POPCOUNT on wordmask bitmaps.
	(ebitmap_set_bit, ebitmap_and_into, ebitmap_and, ebitmap_ior_into,
	ebitmap_and_compl_into, ebitmap_and_compl): Likewise.
	* sparseset.h: Add explanation of sparse set representation.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@189888 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 112 insertions, 31 deletions

diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h
index 231dfd4195c..84aeb8718bc 100644
--- a/gcc/sbitmap.h
+++ b/gcc/sbitmap.h
@@ -1,6 +1,5 @@
 /* Simple bitmaps.
-   Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008, 2010
-   Free Software Foundation, Inc.
+   Copyright (C) 1999-2012  Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -21,9 +20,65 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef GCC_SBITMAP_H
 #define GCC_SBITMAP_H
 
-/* It's not clear yet whether using bitmap.[ch] will be a win.
-   It should be straightforward to convert so for now we keep things simple
-   while more important issues are dealt with.  */
+/* 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			: TEST_BIT
+     * add_member		: SET_BIT
+     * remove_member		: RESET_BIT
+
+   Most other operations on this set representation are O(U) where U is
+   the size of the set universe:
+
+     * clear			: sbitmap_zero
+     * cardinality		: sbitmap_popcount
+     * choose_one		: sbitmap_first_set_bit /
+				  sbitmap_last_set_bit
+     * forall			: EXECUTE_IF_SET_IN_SBITMAP
+     * set_copy			: sbitmap_copy / sbitmap_copy_n
+     * set_intersection		: sbitmap_a_and_b
+     * set_union		: sbitmap_a_or_b
+     * set_difference		: sbitmap_difference
+     * set_disjuction		: (not implemented)
+     * set_compare		: sbitmap_equal
+
+   Some operations on 3 sets that occur frequently in in data flow problems
+   are also implemented:
+
+      * A | (B & C)		: sbitmap_a_or_b_and_c
+      * A | (B & ~C)		: sbitmap_union_of_diff
+      * A & (B | C)		: sbitmap_a_and_b_or_c
+
+   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
@@ -40,42 +95,62 @@ struct simple_bitmap_def
 #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
 #define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
 
+/* Return the number of bits in BITMAP.  */
+#define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
+
 /* Test if bit number bitno in the bitmap is set.  */
-#define TEST_BIT(BITMAP, BITNO) \
-((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1)
+static inline SBITMAP_ELT_TYPE
+TEST_BIT (const_sbitmap map, unsigned 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.  Updates population count
-   if this bitmap has one.  */
+/* Set bit number BITNO in the sbitmap MAP.  */
 
 static inline void
 SET_BIT (sbitmap map, unsigned int bitno)
 {
-  if (map->popcount)
-    {
-      bool oldbit;
-      oldbit = TEST_BIT (map, bitno);
-      if (!oldbit)
-	map->popcount[bitno / SBITMAP_ELT_BITS]++;
-    }
+  gcc_checking_assert (! map->popcount);
   map->elms[bitno / SBITMAP_ELT_BITS]
     |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
 }
 
+/* Like SET_BIT, but updates population count.  */
 
+static inline void
+SET_BIT_WITH_POPCOUNT (sbitmap map, unsigned int bitno)
+{
+  bool oldbit;
+  gcc_checking_assert (map->popcount);
+  oldbit = TEST_BIT (map, bitno);
+  if (!oldbit)
+    map->popcount[bitno / SBITMAP_ELT_BITS]++;
+  map->elms[bitno / SBITMAP_ELT_BITS]
+    |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
+}
 
-/* Reset bit number BITNO in the sbitmap MAP.  Updates population
-   count if this bitmap has one.  */
+/* Reset bit number BITNO in the sbitmap MAP.  */
 
 static inline void
 RESET_BIT (sbitmap map,  unsigned int bitno)
 {
-  if (map->popcount)
-    {
-      bool oldbit;
-      oldbit = TEST_BIT (map, bitno);
-      if (oldbit)
-	map->popcount[bitno / SBITMAP_ELT_BITS]--;
-    }
+  gcc_checking_assert (! map->popcount);
+  map->elms[bitno / SBITMAP_ELT_BITS]
+    &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
+}
+
+/* Like RESET_BIT, but updates population count.  */
+
+static inline void
+RESET_BIT_WITH_POPCOUNT (sbitmap map,  unsigned int bitno)
+{
+  bool oldbit;
+  gcc_checking_assert (map->popcount);
+  oldbit = TEST_BIT (map, bitno);
+  if (oldbit)
+    map->popcount[bitno / SBITMAP_ELT_BITS]--;
   map->elms[bitno / SBITMAP_ELT_BITS]
     &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
 }
@@ -211,14 +286,20 @@ extern void sbitmap_ones (sbitmap);
 extern void sbitmap_vector_zero (sbitmap *, unsigned int);
 extern void sbitmap_vector_ones (sbitmap *, unsigned int);
 
-extern void sbitmap_union_of_diff (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
-extern bool sbitmap_union_of_diff_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
+extern void sbitmap_union_of_diff (sbitmap, const_sbitmap,
+				   const_sbitmap, const_sbitmap);
+extern bool sbitmap_union_of_diff_cg (sbitmap, const_sbitmap,
+				      const_sbitmap, const_sbitmap);
 extern void sbitmap_difference (sbitmap, const_sbitmap, const_sbitmap);
 extern void sbitmap_not (sbitmap, const_sbitmap);
-extern void sbitmap_a_or_b_and_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
-extern bool sbitmap_a_or_b_and_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
-extern void sbitmap_a_and_b_or_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
-extern bool sbitmap_a_and_b_or_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
+extern void sbitmap_a_or_b_and_c (sbitmap, const_sbitmap,
+				  const_sbitmap, const_sbitmap);
+extern bool sbitmap_a_or_b_and_c_cg (sbitmap, const_sbitmap,
+				     const_sbitmap, const_sbitmap);
+extern void sbitmap_a_and_b_or_c (sbitmap, const_sbitmap,
+				  const_sbitmap, const_sbitmap);
+extern bool sbitmap_a_and_b_or_c_cg (sbitmap, const_sbitmap,
+				     const_sbitmap, const_sbitmap);
 extern bool sbitmap_any_common_bits (const_sbitmap, const_sbitmap);
 extern void sbitmap_a_and_b (sbitmap, const_sbitmap, const_sbitmap);
 extern bool sbitmap_a_and_b_cg (sbitmap, const_sbitmap, const_sbitmap);