This adds bitmap_clear_first_set_bit to replace the common
unsigned idx = bitmap_first_set_bit (b);
bitmap_clear_bit (b, idx);
pattern which disturbs the bitmap lookup cached element. We can
always find and clear the first set bit in O(1) so this implements
this as a primitive.
Alternatively one could make sure to never be equal to first
(but for the only element -- 'current' is a bit weird if you look at
bitmap_find_bit). That would make clearing the first bit never
update ->current.
For the weird testcase in PR63155 this makes a noticable difference
(~5% compile-time).
Thoughts?
Thanks,
Richard.
2018-10-16 Richard Biener <rguent...@suse.de>
* bitmap.h (bitmap_clear_first_set_bit): Declare.
* bitmap.c (bitmap_first_set_bit): Make a wrapper around ...
(bitmap_first_set_bit_1): ... this worker that now also can
clear the bit.
(bitmap_clear_first_set_bit): New.
* tree-ssa-propagate.c (ssa_propagation_engine::simulate_stmt):
Clear stmt from the worklist in callers.
(ssa_propagation_engine::simulate_block): Here.
(ssa_propagation_engine::ssa_propagate): Use
bitmap_clear_first_set_bit to pop off worklist items.
* tree-ssa-sccvn.c (do_rpo_vn): Likewise.
* tree-ssa-dce.c (simple_dce_from_worklist): Likewise.
* tree-cfgcleanup.c (cleanup_tree_cfg_noloop): Likewise.
Index: gcc/bitmap.c
===================================================================
--- gcc/bitmap.c (revision 265185)
+++ gcc/bitmap.c (working copy)
@@ -771,12 +771,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. Clear the bit if clear_p is true. */
-unsigned
-bitmap_first_set_bit (const_bitmap a)
+static unsigned
+bitmap_first_set_bit_1 (bitmap a, bool clear_p)
{
- const bitmap_element *elt = a->first;
+ bitmap_element *elt = a->first;
unsigned bit_no;
BITMAP_WORD word;
unsigned ix;
@@ -818,9 +818,29 @@ bitmap_first_set_bit (const_bitmap a)
gcc_checking_assert (word & 1);
#endif
+ if (clear_p)
+ {
+ BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << (bit_no % BITMAP_WORD_BITS);
+ elt->bits[ix] &= ~bit_val;
+ if (!elt->bits[ix]
+ && bitmap_element_zerop (elt))
+ bitmap_element_free (a, elt);
+ }
return bit_no;
}
+unsigned
+bitmap_clear_first_set_bit (bitmap a)
+{
+ return bitmap_first_set_bit_1 (a, true);
+}
+
+unsigned
+bitmap_first_set_bit (const_bitmap a)
+{
+ return bitmap_first_set_bit_1 (const_cast<bitmap>(a), false);
+}
+
/* Return the bit number of the first set bit in the bitmap. The
bitmap must be non-empty. */
Index: gcc/bitmap.h
===================================================================
--- gcc/bitmap.h (revision 265185)
+++ gcc/bitmap.h (working copy)
@@ -52,9 +52,10 @@ along with GCC; see the file COPYING3.
The following operations can always be performed in O(1) time:
+ * empty_p : bitmap_empty_p
* clear : bitmap_clear
- * choose_one : (not implemented, but could be
- implemented in constant time)
+ * choose_one : bitmap_first_set_bit
+ * remove_one : bitmap_clear_first_set_bit
The following operations can be performed in O(E) time worst-case (with
E the number of elements in the linked list), but in O(1) time with a
@@ -359,6 +360,7 @@ extern void debug (const bitmap_head &re
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.) */
Index: gcc/tree-ssa-propagate.c
===================================================================
--- gcc/tree-ssa-propagate.c (revision 265185)
+++ gcc/tree-ssa-propagate.c (working copy)
@@ -213,9 +213,6 @@ ssa_propagation_engine::simulate_stmt (g
edge taken_edge = NULL;
tree output_name = NULL_TREE;
- /* Pull the stmt off the SSA edge worklist. */
- bitmap_clear_bit (ssa_edge_worklist, gimple_uid (stmt));
-
/* Don't bother visiting statements that are already
considered varying by the propagator. */
if (!prop_simulate_again_p (stmt))
@@ -322,7 +319,10 @@ ssa_propagation_engine::simulate_block (
/* Always simulate PHI nodes, even if we have simulated this block
before. */
for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
- simulate_stmt (gsi_stmt (gsi));
+ {
+ bitmap_clear_bit (ssa_edge_worklist, gimple_uid (gsi_stmt (gsi)));
+ simulate_stmt (gsi_stmt (gsi));
+ }
/* If this is the first time we've simulated this block, then we
must simulate each of its statements. */
@@ -334,7 +334,10 @@ ssa_propagation_engine::simulate_block (
edge_iterator ei;
for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
- simulate_stmt (gsi_stmt (j));
+ {
+ bitmap_clear_bit (ssa_edge_worklist, gimple_uid (gsi_stmt (j)));
+ simulate_stmt (gsi_stmt (j));
+ }
/* Note that we have simulated this block. */
block->flags |= BB_VISITED;
@@ -794,7 +797,8 @@ ssa_propagation_engine::ssa_propagate (v
|| next_block_order <= next_stmt_bb_order))
{
curr_order = next_block_order;
- bitmap_clear_bit (cfg_blocks, next_block_order);
+ int num = bitmap_clear_first_set_bit (cfg_blocks);
+ gcc_checking_assert (num == next_block_order);
basic_block bb
= BASIC_BLOCK_FOR_FN (cfun, cfg_order_to_bb [next_block_order]);
simulate_block (bb);
@@ -808,6 +812,8 @@ ssa_propagation_engine::ssa_propagate (v
fprintf (dump_file, "\nSimulating statement: ");
print_gimple_stmt (dump_file, next_stmt, 0, dump_flags);
}
+ int num = bitmap_clear_first_set_bit (ssa_edge_worklist);
+ gcc_checking_assert (num == next_stmt_uid);
simulate_stmt (next_stmt);
}
}
Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c (revision 265185)
+++ gcc/tree-ssa-sccvn.c (working copy)
@@ -6585,8 +6585,7 @@ do_rpo_vn (function *fn, edge entry, bit
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);
Index: gcc/tree-ssa-dce.c
===================================================================
--- gcc/tree-ssa-dce.c (revision 265185)
+++ gcc/tree-ssa-dce.c (working copy)
@@ -1698,8 +1698,7 @@ simple_dce_from_worklist (bitmap worklis
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. */
Index: gcc/tree-cfgcleanup.c
===================================================================
--- gcc/tree-cfgcleanup.c (revision 265185)
+++ gcc/tree-cfgcleanup.c (working copy)
@@ -908,8 +908,7 @@ cleanup_tree_cfg_noloop (void)
/* 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;
