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(-)
@@ -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. */
@@ -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.) */
@@ -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++;
@@ -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;
@@ -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);
@@ -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;
@@ -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);
@@ -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. */
@@ -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);