patch to bitmap.[ch] for mainline to add new functions and fix minor performance issue.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

The new functions are used in the upcoming enhancements to the rtl dataflow:

Bitmap_clear_range provides one of the three orders of magnitude 
performance gain that the new df.c gets when solving reaching 
definitions or reaching uses or build def-use chains on hardware 
registers.  The new version of df.c builds the bit vectors with all of 
the defs for a pseudo being contiguous.  Bitmap_clear_range allows all 
of the bits to be cleared in time proportional to the number of bits set 
(typically 1 or 2) rather than number of definitions for the pseudo. 

Bitmap_count_bits is used in several places and is much faster than 
using a bitmap iterator to count the bits. 

Bitmap_compl_and_into is used in a couple of places.  It is a function 
that cannot be easily fabricated from other functions since the 
complement of the and is expensive to represent in the sparse bitmaps.

The current and next fields are defined to be set in certain ways as a 
byproduct of other operations.  These fields were not always maintained 
properly.

2005-12-08  Kenneth Zadeck <zadeck@naturalbridge.com
   * bitmap.c (bitmap_element_free, bitmap_element_link,
   bitmap_elt_insert_after, bitmap_and, bitmap_and_compl,
   bitmap_and_compl, bitmap_ior, bitmap_ior_into, bitmap_xor,
   bitmap_xor_into): Added code to properly maintain the variants
   associated with the CURRENT and HEAD fields.
   (bitmap_popcount, bitmap_clear_range, bitmap_compl_and_into): New
   functions.  
   * bitmap.h: Added defs for bitmap_popcount,
   bitmap_clear_range, and bitmap_compl_and_into.
   
   

Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c	(.../trunk)	(revision 108124)
+++ gcc/bitmap.c	(.../branches/dataflow-branch)	(revision 108124)
@@ -40,7 +40,7 @@ static void bitmap_element_free (bitmap,
 static bitmap_element *bitmap_element_allocate (bitmap);
 static int bitmap_element_zerop (bitmap_element *);
 static void bitmap_element_link (bitmap, bitmap_element *);
-static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *);
+static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
 
@@ -89,6 +89,8 @@ bitmap_element_free (bitmap head, bitmap
       head->current = next != 0 ? next : prev;
       if (head->current)
 	head->indx = head->current->indx;
+      else 
+	head->indx = 0;
     }
   bitmap_elem_to_freelist (head, elt);
 }
@@ -351,14 +353,18 @@ bitmap_element_link (bitmap head, bitmap
    new element.  */
 
 static bitmap_element *
-bitmap_elt_insert_after (bitmap head, bitmap_element *elt)
+bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
 {
   bitmap_element *node = bitmap_element_allocate (head);
+  node->indx = indx;
 
   if (!elt)
     {
       if (!head->current)
-	head->current = node;
+	{
+	  head->current = node;
+	  head->indx = indx;
+	}
       node->next = head->first;
       if (node->next)
 	node->next->prev = node;
@@ -521,6 +527,62 @@ bitmap_bit_p (bitmap head, int bit)
   return (ptr->bits[word_num] >> bit_num) & 1;
 }
 
+#if GCC_VERSION < 3400
+/* Table of number of set bits in a character, indexed by value of char.  */
+static unsigned char popcount_table[] = 
+{
+    0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+    2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+    3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
+};
+
+static unsigned long
+bitmap_popcount (BITMAP_WORD a)
+{
+  unsigned long ret = 0;
+  unsigned i;
+
+  /* Just do this the table way for now  */
+  for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
+    ret += popcount_table[(a >> i) & 0xff];
+  return ret;
+}
+#endif
+/* Count the number of bits set in the bitmap, and return it.  */
+
+unsigned long
+bitmap_count_bits (bitmap a)
+{
+  unsigned long count = 0;
+  bitmap_element *elt;
+  unsigned ix;
+
+  if (!a->first) 
+    return 0;
+
+  for (elt = a->first; elt; elt = elt->next)
+    {
+      for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+	{
+#if GCC_VERSION >= 3400
+ 	  /* Note that popcountl matches BITMAP_WORD in type, so the actual size
+	 of BITMAP_WORD is not material.  */
+	  count += __builtin_popcountl (elt->bits[ix]);
+#else
+	  count += bitmap_popcount (elt->bits[ix]);	  
+#endif
+	}
+    }
+  return count;
+}
+      
+
+
 /* Return the bit number of the first set bit in the bitmap.  The
    bitmap must be non-empty.  */
 
@@ -604,9 +666,9 @@ bitmap_and (bitmap dst, bitmap a, bitmap
 	  BITMAP_WORD ior = 0;
 
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-	  
-	  dst_elt->indx = a_elt->indx;
+	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	  else 
+	    dst_elt->indx = a_elt->indx;
 	  for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 	    {
 	      BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
@@ -700,9 +762,9 @@ bitmap_and_compl (bitmap dst, bitmap a, 
 	{
 	  /* Copy a_elt.  */
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-	  
-	  dst_elt->indx = a_elt->indx;
+	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	  else
+	    dst_elt->indx = a_elt->indx;
 	  memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
 	  dst_prev = dst_elt;
 	  dst_elt = dst_elt->next;
@@ -717,9 +779,9 @@ bitmap_and_compl (bitmap dst, bitmap a, 
 	  BITMAP_WORD ior = 0;
 
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-	  
-	  dst_elt->indx = a_elt->indx;
+	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	  else 
+	    dst_elt->indx = a_elt->indx;
 	  for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 	    {
 	      BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
@@ -796,6 +858,195 @@ bitmap_and_compl_into (bitmap a, bitmap 
   return changed != 0;
 }
 
+/* Clear COUNT bits from START in HEAD.  */
+void
+bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
+{
+  unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS;
+  unsigned int end_bit_plus1 = start + count;
+  unsigned int end_bit = end_bit_plus1 - 1;
+  unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS;
+  bitmap_element * elt = bitmap_find_bit (head, start);
+
+  /* If bitmap_find_bit returns zero, the current is the closest block
+     to the result.  If the current is less than first index, find the
+     next one.  Otherwise, just set elt to be current.  */
+  if (!elt)
+    { 
+      if (head->current)
+	{
+	  if (head->indx < first_index)
+	    {
+	      elt = head->current->next;
+	      if (!elt)
+		return;
+	    }
+	  else 
+	    elt = head->current;
+	}
+      else
+	return;
+    }
+
+  while (elt && (elt->indx <= last_index))
+    {
+      bitmap_element * next_elt = elt->next;
+      unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
+      unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
+
+
+      if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
+	/* Get rid of the entire elt and go to the next one.  */
+	bitmap_element_free (head, elt);
+      else 
+	{
+	  /* Going to have to knock out some bits in this the elt.  */
+	  unsigned int first_word_to_mod; 
+	  BITMAP_WORD first_mask; 
+	  unsigned int last_word_to_mod;
+	  BITMAP_WORD last_mask;
+	  unsigned int i;
+	  bool clear = true;
+
+	  if (elt_start_bit <= start)
+	    {
+	      /* The first bit to turn off is somewhere inside this
+		 elt.  */
+	      first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
+
+	      /* This mask should have 1s in all bits >= start position. */
+	      first_mask = 
+		(((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
+	      first_mask = ~first_mask;
+	    }
+	  else
+	    {
+	      /* The first bit to turn off is below this start of this elt.  */
+	      first_word_to_mod = 0;
+	      first_mask = (long) -1;
+	    }	      
+	    
+	  if (elt_end_bit_plus1 <= end_bit_plus1)
+	    {
+	      /* The last bit to turn off is beyond this elt.  */
+	      last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
+	      last_mask = (long) -1;
+	    }
+	  else
+	    {
+	      /* The last bit to turn off is inside to this elt.  */
+	      last_word_to_mod = 
+		(end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
+
+	      /* The last mask should have 1s below the end bit.  */
+	      last_mask = 
+		(((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
+	    }
+
+
+	  if (first_word_to_mod == last_word_to_mod)
+	    {
+	      BITMAP_WORD mask = first_mask & last_mask;
+	      elt->bits[first_word_to_mod] &= ~mask;
+	    }
+	  else
+	    {
+	      elt->bits[first_word_to_mod] &= ~first_mask;
+	      for (i=first_word_to_mod + 1; i<last_word_to_mod; i++)
+		elt->bits[i] = 0;
+	      elt->bits[last_word_to_mod] &= ~last_mask;
+	    }
+	  for (i=0; i<BITMAP_ELEMENT_WORDS; i++)
+	    if (elt->bits[i])
+	      {
+		clear = false;
+		break;
+	      }
+	  /* Check to see if there are any bits left.  */
+	  if (clear)
+	    {
+	      bitmap_element_free (head, elt);
+	    }
+	}
+      elt = next_elt;
+    }
+  
+  if (elt)
+    {
+      head->current = elt;
+      head->indx = head->current->indx;
+    }
+}
+
+/* A = ~A & B. */
+
+void
+bitmap_compl_and_into (bitmap a, bitmap b)
+{
+  bitmap_element *a_elt = a->first;
+  bitmap_element *b_elt = b->first;
+  bitmap_element *a_prev = NULL;
+  bitmap_element *next;
+
+  gcc_assert (a != b);
+
+  if (bitmap_empty_p (a))
+    {
+      bitmap_copy (a, b);
+      return;
+    }
+  if (bitmap_empty_p (b))
+    {
+      bitmap_clear (a);
+      return;
+    }
+
+  while (a_elt || b_elt)
+    {
+      if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
+	{
+	  /* A is before B.  Remove A */
+	  next = a_elt->next;
+	  a_prev = a_elt->prev;
+	  bitmap_element_free (a, a_elt);
+	  a_elt = next;
+	}
+      else if (!a_elt || b_elt->indx < a_elt->indx)
+	{
+	  /* B is before A.  Copy B. */
+	  next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
+	  memcpy (next->bits, b_elt->bits, sizeof (next->bits));
+	  a_prev = next;
+	  b_elt = b_elt->next;
+	}
+      else
+	{
+	  /* Matching elts, generate A = ~A & B.  */
+	  unsigned ix;
+	  BITMAP_WORD ior = 0;
+
+	  for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+	    {
+	      BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
+	      BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
+
+	      a_elt->bits[ix] = r;
+	      ior |= r;
+	    }
+	  next = a_elt->next;
+	  if (!ior)
+	    bitmap_element_free (a, a_elt);
+	  else
+	    a_prev = a_elt;
+	  a_elt = next;
+	  b_elt = b_elt->next;
+	}
+    }
+  gcc_assert (!a->current == !a->first);
+  gcc_assert (!a->current || a->indx == a->current->indx);
+  return;
+}
+
 /* DST = A | B.  Return true if DST changes.  */
 
 bool
@@ -833,8 +1116,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap
 	    {
 	      changed = true;
 	      if (!dst_elt)
-		dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-	      dst_elt->indx = a_elt->indx;
+		dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	      else 
+		dst_elt->indx = a_elt->indx;
 	      for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 		{
 		  BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
@@ -878,8 +1162,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap
 	    {
 	      changed = true;
 	      if (!dst_elt)
-		dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-	      dst_elt->indx = src->indx;
+		dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
+	      else 
+		dst_elt->indx = src->indx;
 	      memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 	    }
 	  
@@ -917,9 +1202,7 @@ bitmap_ior_into (bitmap a, bitmap b)
       if (!a_elt || b_elt->indx < a_elt->indx)
 	{
 	  /* Copy b_elt.  */
-	  bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
-	  
-	  dst->indx = b_elt->indx;
+	  bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
 	  memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 	  a_prev = dst;
 	  b_elt = b_elt->next;
@@ -990,9 +1273,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap
 	  BITMAP_WORD ior = 0;
 
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-	  
-	  dst_elt->indx = a_elt->indx;
+	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+	  else
+	    dst_elt->indx = a_elt->indx;
 	  for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 	    {
 	      BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
@@ -1025,9 +1308,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap
 	    }
 
 	  if (!dst_elt)
-	    dst_elt = bitmap_elt_insert_after (dst, dst_prev);
-	  
-	  dst_elt->indx = src->indx;
+	    dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
+	  else 
+	    dst_elt->indx = src->indx;
 	  memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 	  dst_prev = dst_elt;
 	  dst_elt = dst_elt->next;
@@ -1059,9 +1342,7 @@ bitmap_xor_into (bitmap a, bitmap b)
       if (!a_elt || b_elt->indx < a_elt->indx)
 	{
 	  /* Copy b_elt.  */
-	  bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
-	  
-	  dst->indx = b_elt->indx;
+	  bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
 	  memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 	  a_prev = dst;
 	  b_elt = b_elt->next;
Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h	(.../trunk)	(revision 108124)
+++ gcc/bitmap.h	(.../branches/dataflow-branch)	(revision 108124)
@@ -102,6 +102,9 @@ extern bool bitmap_intersect_compl_p (bi
 /* True if MAP is an empty bitmap.  */
 #define bitmap_empty_p(MAP) (!(MAP)->first)
 
+/* Count the number of bits set in the bitmap.  */
+extern unsigned long bitmap_count_bits (bitmap);
+
 /* Boolean operations on bitmaps.  The _into variants are two operand
    versions that modify the first source operand.  The other variants
    are three operand versions that to not destroy the source bitmaps.
@@ -110,6 +113,8 @@ extern void bitmap_and (bitmap, bitmap, 
 extern void bitmap_and_into (bitmap, bitmap);
 extern void bitmap_and_compl (bitmap, bitmap, bitmap);
 extern bool bitmap_and_compl_into (bitmap, bitmap);
+extern void bitmap_compl_and_into (bitmap, bitmap);
+extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
 extern bool bitmap_ior (bitmap, bitmap, bitmap);
 extern bool bitmap_ior_into (bitmap, bitmap);
 extern void bitmap_xor (bitmap, bitmap, bitmap);