[PATCH] middle-end/108786 - add bitmap_clear_first_set_bit

[PATCH] middle-end/108786 - add bitmap_clear_first_set_bit

[Richard Biener]

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.

Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

Richard.

	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.
---
 gcc/bitmap.cc                  | 41 ++++++++++++++++++++++++++++++----
 gcc/bitmap.h                   |  3 +++
 gcc/df-core.cc                 |  3 +--
 gcc/graphite-scop-detection.cc |  3 +--
 gcc/sanopt.cc                  |  6 ++---
 gcc/tree-cfgcleanup.cc         |  3 +--
 gcc/tree-into-ssa.cc           |  3 +--
 gcc/tree-ssa-dce.cc            |  3 +--
 gcc/tree-ssa-sccvn.cc          |  3 +--
 9 files changed, 48 insertions(+), 20 deletions(-)

diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc
index 20de562caac..d1d0324b633 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,9 +1269,42 @@ 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;
 }
 
+/* Return the bit number of the first set bit in the bitmap.  The
+   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.  */
 
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 43337d2e9d9..5432f386dbd 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -110,6 +110,7 @@ along with GCC; see the file COPYING3.  If not see
 
      * clear			: bitmap_clear
      * smallest_member		: bitmap_first_set_bit
+     * pop_smallest		: bitmap_clear_first_set_bit
      * choose_one		: (not implemented, but could be
 				   in constant time)
 
@@ -133,6 +134,7 @@ along with GCC; see the file COPYING3.  If not see
    amortized time with O(E) worst-case behavior.
 
      * smallest_member
+     * pop_smallest
      * largest_member
      * set_size
      * member_p
@@ -501,6 +503,7 @@ extern void debug (const bitmap_head &ref);
 extern void debug (const bitmap_head *ptr);
 
 extern unsigned bitmap_first_set_bit (const_bitmap);
+extern unsigned bitmap_clear_first_set_bit (bitmap);
 extern unsigned bitmap_last_set_bit (const_bitmap);
 
 /* Compute bitmap hash (for purposes of hashing etc.)  */
diff --git a/gcc/df-core.cc b/gcc/df-core.cc
index 38f69ac5743..3286ffda2ce 100644
--- a/gcc/df-core.cc
+++ b/gcc/df-core.cc
@@ -1040,8 +1040,7 @@ df_worklist_dataflow_doublequeue (struct dataflow *dataflow,
 
       do
 	{
-	  unsigned index = bitmap_first_set_bit (worklist);
-	  bitmap_clear_bit (worklist, index);
+	  unsigned index = bitmap_clear_first_set_bit (worklist);
 
 	  unsigned bb_index;
 	  dcount++;
diff --git a/gcc/graphite-scop-detection.cc b/gcc/graphite-scop-detection.cc
index f976451949d..99551990e54 100644
--- a/gcc/graphite-scop-detection.cc
+++ b/gcc/graphite-scop-detection.cc
@@ -469,8 +469,7 @@ scop_detection::merge_sese (sese_l first, sese_l second) const
      its border it acts more like a visited bitmap.  */
   do
     {
-      int index = bitmap_first_set_bit (worklist);
-      bitmap_clear_bit (worklist, index);
+      int index = bitmap_clear_first_set_bit (worklist);
       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
       edge_iterator ei;
       edge e;
diff --git a/gcc/sanopt.cc b/gcc/sanopt.cc
index 85489739507..ce8393b9518 100644
--- a/gcc/sanopt.cc
+++ b/gcc/sanopt.cc
@@ -1012,8 +1012,7 @@ sanitize_asan_mark_unpoison (void)
   /* 2) Propagate the information to all reachable blocks.  */
   while (!bitmap_empty_p (worklist))
     {
-      unsigned i = bitmap_first_set_bit (worklist);
-      bitmap_clear_bit (worklist, i);
+      unsigned i = bitmap_clear_first_set_bit (worklist);
       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
       gcc_assert (bb);
 
@@ -1109,8 +1108,7 @@ sanitize_asan_mark_poison (void)
   /* 2) Propagate the information to all definitions blocks.  */
   while (!bitmap_empty_p (worklist))
     {
-      unsigned i = bitmap_first_set_bit (worklist);
-      bitmap_clear_bit (worklist, i);
+      unsigned i = bitmap_clear_first_set_bit (worklist);
       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
       gcc_assert (bb);
 
diff --git a/gcc/tree-cfgcleanup.cc b/gcc/tree-cfgcleanup.cc
index 64ff16fc45b..42b25312122 100644
--- a/gcc/tree-cfgcleanup.cc
+++ b/gcc/tree-cfgcleanup.cc
@@ -1133,8 +1133,7 @@ cleanup_tree_cfg_noloop (unsigned ssa_update_flags)
   /* Now process the altered blocks, as long as any are available.  */
   while (!bitmap_empty_p (cfgcleanup_altered_bbs))
     {
-      unsigned i = bitmap_first_set_bit (cfgcleanup_altered_bbs);
-      bitmap_clear_bit (cfgcleanup_altered_bbs, i);
+      unsigned i = bitmap_clear_first_set_bit (cfgcleanup_altered_bbs);
       if (i < NUM_FIXED_BLOCKS)
 	continue;
 
diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc
index 2e322990456..5cfe7c516cc 100644
--- a/gcc/tree-into-ssa.cc
+++ b/gcc/tree-into-ssa.cc
@@ -2348,8 +2348,7 @@ rewrite_blocks (basic_block entry, enum rewrite_mode what)
 	}
       while (!bitmap_empty_p (worklist))
 	{
-	  int idx = bitmap_first_set_bit (worklist);
-	  bitmap_clear_bit (worklist, idx);
+	  int idx = bitmap_clear_first_set_bit (worklist);
 	  basic_block bb = BASIC_BLOCK_FOR_FN (cfun, idx);
 	  bb->flags |= in_region;
 	  extra_rgn.safe_push (bb);
diff --git a/gcc/tree-ssa-dce.cc b/gcc/tree-ssa-dce.cc
index 0ae998f86f9..bda780876f3 100644
--- a/gcc/tree-ssa-dce.cc
+++ b/gcc/tree-ssa-dce.cc
@@ -2102,8 +2102,7 @@ simple_dce_from_worklist (bitmap worklist)
   while (! bitmap_empty_p (worklist))
     {
       /* Pop item.  */
-      unsigned i = bitmap_first_set_bit (worklist);
-      bitmap_clear_bit (worklist, i);
+      unsigned i = bitmap_clear_first_set_bit (worklist);
 
       tree def = ssa_name (i);
       /* Removed by somebody else or still in use.  */
diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
index 9692911e31b..7fa2a154e84 100644
--- a/gcc/tree-ssa-sccvn.cc
+++ b/gcc/tree-ssa-sccvn.cc
@@ -8491,8 +8491,7 @@ do_rpo_vn_1 (function *fn, edge entry, bitmap exit_bbs,
       bitmap_set_bit (worklist, 0);
       while (!bitmap_empty_p (worklist))
 	{
-	  int idx = bitmap_first_set_bit (worklist);
-	  bitmap_clear_bit (worklist, idx);
+	  int idx = bitmap_clear_first_set_bit (worklist);
 	  basic_block bb = BASIC_BLOCK_FOR_FN (fn, rpo[idx]);
 	  gcc_assert ((bb->flags & BB_EXECUTABLE)
 		      && !rpo_state[idx].visited);
-- 
2.35.3