[Bug tree-optimization/26854] Inordinate compile times on large routines

[cvs-commit at gcc dot gnu.org]

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

--- Comment #147 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:4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980

commit r13-5750-g4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980
Author: Richard Biener <rguenther@suse.de>
Date:   Tue Feb 7 14:01:22 2023 +0100

    tree-optimization/26854 - slow bitmap operations

    With the compiler.i testcase from the PR one can see bitmap_set_bit
    very high in the profile, originating from SSA update and alias
    stmt walking.  For SSA update mark_block_for_update essentially
    performs redundant bitmap_set_bits and is called via
    insert_updated_phi_nodes_for as

          EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
    ...
              mark_block_for_update (bb);
              FOR_EACH_EDGE (e, ei, bb->preds)
                if (e->src->index >= 0)
                  mark_block_for_update (e->src);

    which is quite random in the access pattern and runs into the
    O(n) case of the linked list bitmap representation.  Switching
    blocks_to_update to tree view around insert_updated_phi_nodes_for
    improves SSA update time from

     tree SSA incremental               :   4.26 (  3%)

    to

     tree SSA incremental               :   2.98 (  2%)

    Likewise the visited bitmap allocated by the alias walker benefits
    from using the tree view in case of large CFGs and we see an
    improvement from

     alias stmt walking                 :  10.53 (  9%)

    to

     alias stmt walking                 :   4.05 (  4%)

            PR tree-optimization/26854
            * tree-into-ssa.cc (update_ssa): Turn blocks_to_update to tree
            view around insert_updated_phi_nodes_for.
            * tree-ssa-alias.cc (maybe_skip_until): Allocate visited bitmap
            in tree view.
            (walk_aliased_vdefs_1): Likewise.