diff options
| author | Richard Biener <rguenther@suse.de> | 2023-02-07 14:01:22 +0100 |
|---|---|---|
| committer | Richard Biener <rguenther@suse.de> | 2023-02-09 08:24:30 +0100 |
| commit | 4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980 (patch) | |
| tree | e95b698aac611d9a960a99b8fd4949195e763af4 /gcc | |
| parent | f6fc79d0c90ff3a924d272eff74b32656bdf5481 (diff) | |
| download | gcc-4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980.zip gcc-4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980.tar.gz gcc-4b19ff1b5ef684c2d9ccd4fb275aeef0a4b0b980.tar.bz2 | |
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.
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/tree-into-ssa.cc | 4 | ||||
| -rw-r--r-- | gcc/tree-ssa-alias.cc | 10 |
2 files changed, 12 insertions, 2 deletions
diff --git a/gcc/tree-into-ssa.cc b/gcc/tree-into-ssa.cc index 067d296..2e32299 100644 --- a/gcc/tree-into-ssa.cc +++ b/gcc/tree-into-ssa.cc @@ -3561,6 +3561,8 @@ update_ssa (unsigned update_flags) bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack); compute_dominance_frontiers (dfs); + bitmap_tree_view (blocks_to_update); + /* insert_update_phi_nodes_for will call add_new_name_mapping when inserting new PHI nodes, but it will not add any new members to OLD_SSA_NAMES. */ @@ -3574,6 +3576,8 @@ update_ssa (unsigned update_flags) FOR_EACH_VEC_ELT (symbols_to_rename, i, sym) insert_updated_phi_nodes_for (sym, dfs, update_flags); + bitmap_list_view (blocks_to_update); + FOR_EACH_BB_FN (bb, cfun) bitmap_clear (&dfs[bb->index]); free (dfs); diff --git a/gcc/tree-ssa-alias.cc b/gcc/tree-ssa-alias.cc index 7089e8b..81bc51e 100644 --- a/gcc/tree-ssa-alias.cc +++ b/gcc/tree-ssa-alias.cc @@ -3657,7 +3657,10 @@ maybe_skip_until (gimple *phi, tree &target, basic_block target_bb, basic_block bb = gimple_bb (phi); if (!*visited) - *visited = BITMAP_ALLOC (NULL); + { + *visited = BITMAP_ALLOC (NULL); + bitmap_tree_view (*visited); + } bitmap_set_bit (*visited, SSA_NAME_VERSION (PHI_RESULT (phi))); @@ -3949,7 +3952,10 @@ walk_aliased_vdefs_1 (ao_ref *ref, tree vdef, { unsigned i; if (!*visited) - *visited = BITMAP_ALLOC (NULL); + { + *visited = BITMAP_ALLOC (NULL); + bitmap_tree_view (*visited); + } for (i = 0; i < gimple_phi_num_args (def_stmt); ++i) { int res = walk_aliased_vdefs_1 (ref, |