From: Richard Biener <rguenther@suse.de>
To: gcc-patches@gcc.gnu.org
Subject: [PATCH] tree-optimization/26854 - slow bitmap operations
Date: Tue, 7 Feb 2023 14:49:20 +0100 (CET) [thread overview]
Message-ID: <20230207134920.8BDD3139ED@imap2.suse-dmz.suse.de> (raw)
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%)
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
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.
---
gcc/tree-into-ssa.cc | 4 ++++
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 067d29698f9..2e322990456 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 7089e8b5bf3..81bc51ed4ad 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,
--
2.35.3
reply other threads:[~2023-02-07 13:49 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230207134920.8BDD3139ED@imap2.suse-dmz.suse.de \
--to=rguenther@suse.de \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).