On 10/16/18 3:12 AM, Richard Biener wrote: > > 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. Seems quite reasonable to me.
Jeff
