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 <rgue...@gcc.gnu.org>: https://gcc.gnu.org/g:4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980 commit r13-5750-g4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980 Author: Richard Biener <rguent...@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.
