bitmap.c (bitmap_element_free, [...]): Added code to properly maintain the variants associated with the CURRENT and...

2005-12-29 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.

From-SVN: r109153

1 files changed, 274 insertions, 28 deletions

diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 3ee8bbd..f69fd27 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -40,7 +40,7 @@ static void bitmap_element_free (bitmap, bitmap_element *);
 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_element *elt)
       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_element *element)
    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,59 @@ 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;
+
+  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 +663,9 @@ bitmap_and (bitmap dst, bitmap a, bitmap b)
 	  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 +759,9 @@ bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
 	{
 	  /* 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 +776,9 @@ bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
 	  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 +855,195 @@ bitmap_and_compl_into (bitmap a, bitmap b)
   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 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 = 0;
+	      first_mask = ~first_mask;
+	    }	      
+	    
+	  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 = 0;
+	      last_mask = ~last_mask;
+	    }
+	  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 +1081,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap b)
 	    {
 	      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 +1127,9 @@ bitmap_ior (bitmap dst, bitmap a, bitmap b)
 	    {
 	      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 +1167,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 +1238,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b)
 	  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 +1273,9 @@ bitmap_xor (bitmap dst, bitmap a, bitmap b)
 	    }
 
 	  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 +1307,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;