https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127661
--- Comment #5 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Kyrylo Tkachov <[email protected]>: 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]>
