bitmap.h (bitmap_equal_p): Return bool.

	* bitmap.h (bitmap_equal_p): Return bool.
	(bitmap_intersect_p, bitmap_intersect_compl_p): Declare.
	* bitmap.c (bitmap_equal_p): Return bool. Compare directly.
	(bitmap_intersect_p, bitmap_intersect_compl_p): New.
	* flow.c (calculate_global_regs_live): Use bitmap_intersect_p and
	bitmap_intersect_compl_p.
	* ifcvt (dead_or_predicable): Likewise.

From-SVN: r89981

5 files changed, 116 insertions, 43 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f581d1a..87d7e07 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,15 @@
 2004-11-02  Nathan Sidwell  <nathan@codesourcery.com>
 
+	* bitmap.h (bitmap_equal_p): Return bool.
+	(bitmap_intersect_p, bitmap_intersect_compl_p): Declare.
+	* bitmap.c (bitmap_equal_p): Return bool. Compare directly.
+	(bitmap_intersect_p, bitmap_intersect_compl_p): New.
+	* flow.c (calculate_global_regs_live): Use bitmap_intersect_p and
+	bitmap_intersect_compl_p.
+	* ifcvt (dead_or_predicable): Likewise.
+
+2004-11-02  Nathan Sidwell  <nathan@codesourcery.com>
+
 	PR rtl-optimization/17104
 	* config/rs6000/rs6000.c (rs6000_emit_move): Don't wrap small
 	loads in zero_extend.
diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 0a50d41..c78912b 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -663,20 +663,85 @@ bitmap_operation (bitmap to, bitmap from1, bitmap from2,
   return changed;
 }
 
-/* Return true if two bitmaps are identical.  */
+/* Return true if two bitmaps are identical.
+   We do not bother with a check for pointer equality, as that never
+   occurs in practice.  */
 
-int
+bool
 bitmap_equal_p (bitmap a, bitmap b)
 {
-  bitmap_head c;
-  int ret;
+  bitmap_element *a_elt;
+  bitmap_element *b_elt;
+  unsigned ix;
+  
+  for (a_elt = a->first, b_elt = b->first;
+       a_elt && b_elt;
+       a_elt = a_elt->next, b_elt = b_elt->next)
+    {
+      if (a_elt->indx != b_elt->indx)
+	return false;
+      for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+	if (a_elt->bits[ix] != b_elt->bits[ix])
+	  return false;
+    }
+  return !a_elt && !b_elt;
+}
+
+/* Return true if A AND B is not empty.  */
+
+bool
+bitmap_intersect_p (bitmap a, bitmap b)
+{
+  bitmap_element *a_elt;
+  bitmap_element *b_elt;
+  unsigned ix;
+  
+  for (a_elt = a->first, b_elt = b->first;
+       a_elt && b_elt;)
+    {
+      if (a_elt->indx < b_elt->indx)
+	a_elt = a_elt->next;
+      else if (b_elt->indx < a_elt->indx)
+	b_elt = b_elt->next;
+      else
+	{
+	  for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+	    if (a_elt->bits[ix] & b_elt->bits[ix])
+	      return true;
+	  a_elt = a_elt->next;
+	  b_elt = b_elt->next;
+	}
+    }
+  return false;
+}
 
-  memset (&c, 0, sizeof (c));
-  ret = ! bitmap_xor (&c, a, b);
-  bitmap_clear (&c);
+/* Return true if A AND NOT B is not empty.  */
 
-  return ret;
+bool
+bitmap_intersect_compl_p (bitmap a, bitmap b)
+{
+  bitmap_element *a_elt;
+  bitmap_element *b_elt;
+  unsigned ix;
+  for (a_elt = a->first, b_elt = b->first;
+       a_elt && b_elt;)
+    {
+      if (a_elt->indx < b_elt->indx)
+	return true;
+      else if (b_elt->indx < a_elt->indx)
+	b_elt = b_elt->next;
+      else
+	{
+	  for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+	    if (a_elt->bits[ix] & ~b_elt->bits[ix])
+	      return true;
+	  a_elt = a_elt->next;
+	  b_elt = b_elt->next;
+	}
+    }
+  return a_elt != NULL;
 }
+
 
 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
    bitmap FROM2.  */
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 67eb9d2..767fafa 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -85,8 +85,16 @@ extern void bitmap_clear (bitmap);
 extern void bitmap_copy (bitmap, bitmap);
 
 /* True if two bitmaps are identical.  */
-extern int bitmap_equal_p (bitmap, bitmap);
+extern bool bitmap_equal_p (bitmap, bitmap);
 
+/* True if the bitmaps intersect (their AND is non-empty).  */
+extern bool bitmap_intersect_p (bitmap, bitmap);
+
+/* True if the complement of the second intersects the first (their
+   AND_COMPL is non-empty).  */
+extern bool bitmap_intersect_compl_p (bitmap, bitmap);
+
+/* True if MAP is an empty bitmap.  */
 #define bitmap_empty_p(MAP) (!(MAP)->first)
 
 /* Perform an operation on two bitmaps, yielding a third.  */
diff --git a/gcc/flow.c b/gcc/flow.c
index 6e599c8..163e5c9 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -1185,38 +1185,32 @@ calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
 	     rescan the block.  This wouldn't be necessary if we had
 	     precalculated local_live, however with PROP_SCAN_DEAD_CODE
 	     local_live is really dependent on live_at_end.  */
-	  CLEAR_REG_SET (tmp);
-	  rescan = bitmap_and_compl (tmp, bb->global_live_at_end,
-				     new_live_at_end);
-
-	  if (! rescan)
-	    {
-	      /* If any of the registers in the new live_at_end set are
-		 conditionally set in this basic block, we must rescan.
-	         This is because conditional lifetimes at the end of the
-		 block do not just take the live_at_end set into account,
-		 but also the liveness at the start of each successor
-		 block.  We can miss changes in those sets if we only
-		 compare the new live_at_end against the previous one.  */
-	      CLEAR_REG_SET (tmp);
-	      rescan = bitmap_and (tmp, new_live_at_end,
-				   bb->cond_local_set);
-	    }
-
-	  if (! rescan)
+	  rescan = bitmap_intersect_compl_p (bb->global_live_at_end,
+					     new_live_at_end);
+
+	  if (!rescan)
+	    /* If any of the registers in the new live_at_end set are
+	       conditionally set in this basic block, we must rescan.
+	       This is because conditional lifetimes at the end of the
+	       block do not just take the live_at_end set into
+	       account, but also the liveness at the start of each
+	       successor block.  We can miss changes in those sets if
+	       we only compare the new live_at_end against the
+	       previous one.  */
+	    rescan = bitmap_intersect_p (new_live_at_end,
+					 bb->cond_local_set);
+
+	  if (!rescan)
 	    {
 	      /* Find the set of changed bits.  Take this opportunity
 		 to notice that this set is empty and early out.  */
-	      CLEAR_REG_SET (tmp);
-	      changed = bitmap_xor (tmp, bb->global_live_at_end,
-					  new_live_at_end);
-	      if (! changed)
+	      bitmap_xor (tmp, bb->global_live_at_end, new_live_at_end);
+	      if (bitmap_empty_p (tmp))
 		continue;
-
+  
 	      /* If any of the changed bits overlap with local_set,
-		 we'll have to rescan the block.  Detect overlap by
-		 the AND with ~local_set turning off bits.  */
-	      rescan = bitmap_and_compl_into (tmp, bb->local_set);
+ 		 we'll have to rescan the block.  */
+	      rescan = bitmap_intersect_p (tmp, bb->local_set);
 	    }
 	}
 
diff --git a/gcc/ifcvt.c b/gcc/ifcvt.c
index 72bb393..a033f35 100644
--- a/gcc/ifcvt.c
+++ b/gcc/ifcvt.c
@@ -3217,13 +3217,9 @@ dead_or_predicable (basic_block test_bb, basic_block merge_bb,
 	   TEST_SET & merge_bb->global_live_at_start
 	 are empty.  */
 
-      bitmap_ior (tmp, test_set, test_live);
-      bitmap_and_into (tmp, merge_set);
-      if (!bitmap_empty_p (tmp))
-	fail = 1;
-
-      bitmap_and (tmp, test_set, merge_bb->global_live_at_start);
-      if (!bitmap_empty_p (tmp))
+      if (bitmap_intersect_p (test_set, merge_set)
+	  || bitmap_intersect_p (test_live, merge_set)
+	  || bitmap_intersect_p (test_set, merge_bb->global_live_at_start))
 	fail = 1;
 
       FREE_REG_SET (tmp);