https://gcc.gnu.org/g:9d4c1687d172b53c672d8ee8636667c7f0f33255
commit r17-4990-g9d4c1687d172b53c672d8ee8636667c7f0f33255 Author: Kyrylo Tkachov <[email protected]> Date: Wed Sep 30 08:38:59 2026 +0200 tree-ssa-dom: Avoid repeated walks in back_propagate_equivalences [PR127661] When DOM records an equivalence NAME = VALUE on an edge, back_propagate_equivalences walks all uses of NAME and looks for statements that dominate the edge and fold to a constant or a name with the new value. In the testcase of the PR at N=2048, dom2 records V = K about 16k times and each time walks the more than 14k uses of V. All of them are conditions, so no walk finds anything. dom3 repeats this. This patch records the names for which a walk finds no assignment or call that defines an SSA name, and skips the walk for them later. PHI nodes never give an equivalence because gimple_fold_stmt_to_constant_1 does not fold them, so the walk now skips them too. A name only gets a new use of this kind when DOM propagates it into a statement, so before_dom_children clears the bits of the uses of each statement that defines an SSA name after optimize_stmt. This also covers statements that folding inserts, because the statement loop visits them. With checking enabled, the walk still runs for recorded names and asserts that it finds no such use. For the testcase at -O2 on Grace, the time in "dominator optimization" drops by 85% at N=2048 and by 91% at N=4096. The whole compilation executes 6.5% fewer instructions at N=2048 and 6.1% fewer at N=4096. The dom2 and dom3 dumps with -details do not change for the testcase and 4 large GCC sources at -O2. The generated code does not change for the testcase, 10 large GCC sources and gcc.c-torture at -O2 and -O3. For the large GCC sources the instruction count goes up by 0.01% on average, and by at most 0.03%. The new test checks that a name loses its bit when DOM propagates it into an assignment. Bootstrapped and tested on aarch64-linux-gnu and x86_64-linux-gnu. PR rtl-optimization/127661 gcc/ChangeLog: * tree-ssa-dom.cc (names_without_foldable_uses): New variable. (pass_dominator::execute): Allocate and free it. (back_propagate_equivalences): Return early for the names in names_without_foldable_uses unless checking is enabled. Skip PHI nodes. Record LHS in names_without_foldable_uses if no use can give an equivalence. (dom_opt_dom_walker::before_dom_children): After optimize_stmt, remove the uses of a statement that defines an SSA name from names_without_foldable_uses. gcc/testsuite/ChangeLog: * gcc.dg/tree-ssa/pr127661.c: New test. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/testsuite/gcc.dg/tree-ssa/pr127661.c | 48 ++++++++++++++++++++++++++++ gcc/tree-ssa-dom.cc | 55 ++++++++++++++++++++++++++++---- 2 files changed, 96 insertions(+), 7 deletions(-) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr127661.c b/gcc/testsuite/gcc.dg/tree-ssa/pr127661.c new file mode 100644 index 000000000000..c6095eb83456 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr127661.c @@ -0,0 +1,48 @@ +/* PR rtl-optimization/127661 */ +/* { dg-do compile } */ +/* { dg-options "-O -fgimple -fdump-tree-dom2-details" } */ + +void bar (void); + +/* On the edge to bb 3, DOM finds no use of Y that defines an SSA name. + DOM then propagates Y into the definition of Z in bb 5, so the + equivalence Y == 6 on the edge to bb 6 must still give Z == 10. */ + +int __GIMPLE (ssa,startwith("dom")) +foo (int y, int r) +{ + int w; + int z; + + __BB(2): + if (y_5(D) == 1) + goto __BB3; + else + goto __BB4; + + __BB(3): + bar (); + goto __BB4; + + __BB(4): + w_2 = r_6(D) * 3; + if (w_2 == y_5(D)) + goto __BB5; + else + goto __BB7; + + __BB(5): + z_4 = w_2 + 4; + if (y_5(D) == 6) + goto __BB6; + else + goto __BB7; + + __BB(6): + return z_4; + + __BB(7): + return 0; +} + +/* { dg-final { scan-tree-dump "COPY z_4 = 10" "dom2" } } */ diff --git a/gcc/tree-ssa-dom.cc b/gcc/tree-ssa-dom.cc index 26c1d8dc1207..27381e0a4737 100644 --- a/gcc/tree-ssa-dom.cc +++ b/gcc/tree-ssa-dom.cc @@ -94,6 +94,11 @@ static bool cfg_altered; static bitmap need_eh_cleanup; static vec<gimple *> need_noreturn_fixup; +/* Bitmap of SSA names that have no use in an assignment or call that + defines an SSA name, so back_propagate_equivalences has nothing to do + for them. A bit is cleared when DOM adds such a use. */ +static bitmap names_without_foldable_uses; + /* Statistics for dominator optimizations. */ struct opt_stats_d { @@ -731,6 +736,8 @@ pass_dominator::execute (function *fun) class const_and_copies *const_and_copies = new class const_and_copies (); need_eh_cleanup = BITMAP_ALLOC (NULL); need_noreturn_fixup.create (0); + names_without_foldable_uses = BITMAP_ALLOC (NULL); + bitmap_tree_view (names_without_foldable_uses); calculate_dominance_info (CDI_DOMINATORS); cfg_altered = false; @@ -903,6 +910,7 @@ pass_dominator::execute (function *fun) /* Free asserted bitmaps and stacks. */ BITMAP_FREE (need_eh_cleanup); need_noreturn_fixup.release (); + BITMAP_FREE (names_without_foldable_uses); delete avail_exprs_stack; delete const_and_copies; @@ -943,6 +951,14 @@ back_propagate_equivalences (tree lhs, edge e, imm_use_iterator iter; basic_block dest = e->dest; bool domok = (dom_info_state (CDI_DOMINATORS) == DOM_OK); + unsigned version = SSA_NAME_VERSION (lhs); + + /* If an earlier walk found no use of LHS that can produce an + equivalence, there is nothing to do. With checking enabled, walk + the uses anyway to verify that no such use has been added. */ + bool cached_p = bitmap_bit_p (names_without_foldable_uses, version); + if (cached_p && !flag_checking) + return; /* Iterate over the uses of LHS to see if any dominate E->dest. If so, they may create useful equivalences too. @@ -950,21 +966,28 @@ back_propagate_equivalences (tree lhs, edge e, ??? If the code gets re-organized to a worklist to catch more indirect opportunities and it is made to handle PHIs then this should only consider use_stmts in basic-blocks we have already visited. */ + bool foldable_use_p = false; FOR_EACH_IMM_USE_FAST (use_p, iter, lhs) { gimple *use_stmt = USE_STMT (use_p); - /* Often the use is in DEST, which we trivially know we can't use. - This is cheaper than the dominator set tests below. */ - if (dest == gimple_bb (use_stmt)) - continue; - /* Filter out statements that can never produce a useful - equivalence. */ + equivalence. gimple_fold_stmt_to_constant_1 does not fold + PHI nodes. */ + if (gimple_code (use_stmt) == GIMPLE_PHI) + continue; tree lhs2 = gimple_get_lhs (use_stmt); if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME) continue; + gcc_checking_assert (!cached_p); + foldable_use_p = true; + + /* Often the use is in DEST, which we trivially know we can't use. + This is cheaper than the dominator set tests below. */ + if (dest == gimple_bb (use_stmt)) + continue; + if (domok) { if (!dominated_by_p (CDI_DOMINATORS, dest, gimple_bb (use_stmt))) @@ -989,6 +1012,9 @@ back_propagate_equivalences (tree lhs, edge e, if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res))) record_equality (lhs2, res, const_and_copies); } + + if (!foldable_use_p) + bitmap_set_bit (names_without_foldable_uses, version); } /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied @@ -1584,7 +1610,22 @@ dom_opt_dom_walker::before_dom_children (basic_block bb) bool removed_p = false; taken_edge = this->optimize_stmt (bb, &gsi, &removed_p); if (!removed_p) - gimple_set_visited (gsi_stmt (gsi), true); + { + gimple *stmt = gsi_stmt (gsi); + gimple_set_visited (stmt, true); + + /* Propagation and folding may have added uses to STMT, which + back_propagate_equivalences has to consider. */ + tree lhs = gimple_get_lhs (stmt); + if (lhs && TREE_CODE (lhs) == SSA_NAME) + { + ssa_op_iter iter; + tree use; + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) + bitmap_clear_bit (names_without_foldable_uses, + SSA_NAME_VERSION (use)); + } + } /* Go back and visit stmts inserted by folding after substituting into the stmt at gsi. */
