[Bug middle-end/108786] New: bitmap_first_set_bit misses a bitmap_clear_first_bit

[Bug middle-end/108786] New: bitmap_first_set_bit misses a bitmap_clear_first_bit

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108786

            Bug ID: 108786
           Summary: bitmap_first_set_bit misses a bitmap_clear_first_bit
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rguenth at gcc dot gnu.org
  Target Milestone: ---

We have a repeated pattern for worklists doing

  unsigned idx = bitmap_first_set_bit (b);
  bitmap_clear_bit (b, idx);

but bitmap_clear_bit is more expensive and in particular prone to
clobber ->current which will pessimize other accesses to the same
bitmap.

bitmap_clear_first_bit would return the bit number cleared so it can
be used to pop an item from a worklist efficiently.

If the order doesn't matter a pick-one API also is missing which would
be more efficient for the tree form.

[Bug middle-end/108786] bitmap_first_set_bit misses a bitmap_clear_first_bit

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108786

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-02-14
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Mine.

[Bug middle-end/108786] bitmap_first_set_bit misses a bitmap_clear_first_bit

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108786

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:f548ece7abc0a0c81dd049e9f8b480ff2c38e18b

commit r14-41-gf548ece7abc0a0c81dd049e9f8b480ff2c38e18b
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Feb 14 16:36:03 2023 +0100

    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.

[Bug middle-end/108786] bitmap_first_set_bit misses a bitmap_clear_first_bit

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108786

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for GCC 14+