middle-end/108786 - add bitmap_clear_first_set_bit

This adds bitmap_clear_first_set_bit and uses it where previously
bitmap_clear_bit followed bitmap_first_set_bit.  The advantage
is speeding up the search and avoiding to clobber ->current.

	PR middle-end/108786
	* bitmap.h (bitmap_clear_first_set_bit): New.
	* bitmap.cc (bitmap_first_set_bit_worker): Rename from
	bitmap_first_set_bit and add optional clearing of the bit.
	(bitmap_first_set_bit): Wrap bitmap_first_set_bit_worker.
	(bitmap_clear_first_set_bit): Likewise.
	* df-core.cc (df_worklist_dataflow_doublequeue): Use
	bitmap_clear_first_set_bit.
	* graphite-scop-detection.cc (scop_detection::merge_sese):
	Likewise.
	* sanopt.cc (sanitize_asan_mark_unpoison): Likewise.
	(sanitize_asan_mark_poison): Likewise.
	* tree-cfgcleanup.cc (cleanup_tree_cfg_noloop): Likewise.
	* tree-into-ssa.cc (rewrite_blocks): Likewise.
	* tree-ssa-dce.cc (simple_dce_from_worklist): Likewise.
	* tree-ssa-sccvn.cc (do_rpo_vn_1): Likewise.

1 files changed, 37 insertions, 4 deletions

diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc
index 20de562..d1d0324 100644
--- a/gcc/bitmap.cc
+++ b/gcc/bitmap.cc
@@ -1217,12 +1217,12 @@ bitmap_single_bit_set_p (const_bitmap a)
 
 
 /* Return the bit number of the first set bit in the bitmap.  The
-   bitmap must be non-empty.  */
+   bitmap must be non-empty.  When CLEAR is true it clears the bit.  */
 
-unsigned
-bitmap_first_set_bit (const_bitmap a)
+static unsigned
+bitmap_first_set_bit_worker (bitmap a, bool clear)
 {
-  const bitmap_element *elt = a->first;
+  bitmap_element *elt = a->first;
   unsigned bit_no;
   BITMAP_WORD word;
   unsigned ix;
@@ -1269,6 +1269,21 @@ bitmap_first_set_bit (const_bitmap a)
 
  gcc_checking_assert (word & 1);
 #endif
+
+ if (clear)
+   {
+     elt->bits[ix] &= ~((BITMAP_WORD) 1 << (bit_no % BITMAP_WORD_BITS));
+     /* If we cleared the entire word, free up the element.  */
+     if (!elt->bits[ix]
+	 && bitmap_element_zerop (elt))
+       {
+	 if (!a->tree_form)
+	   bitmap_list_unlink_element (a, elt);
+	 else
+	   bitmap_tree_unlink_element (a, elt);
+       }
+   }
+
  return bit_no;
 }
 
@@ -1276,6 +1291,24 @@ bitmap_first_set_bit (const_bitmap a)
    bitmap must be non-empty.  */
 
 unsigned
+bitmap_first_set_bit (const_bitmap a)
+{
+  return bitmap_first_set_bit_worker (const_cast<bitmap> (a), false);
+}
+
+/* Return and clear the bit number of the first set bit in the bitmap.  The
+   bitmap must be non-empty.  */
+
+unsigned
+bitmap_clear_first_set_bit (bitmap a)
+{
+  return bitmap_first_set_bit_worker (a, true);
+}
+
+/* Return the bit number of the first set bit in the bitmap.  The
+   bitmap must be non-empty.  */
+
+unsigned
 bitmap_last_set_bit (const_bitmap a)
 {
   const bitmap_element *elt;