[PATCH 5/5] tree-ssa-dom: Avoid repeated walks in back_propagate_equivalences [PR127661]
Jeff Law
jeffrey.law@oss.qualcomm.com
Thu Oct 8 02:32:36 GMT 2026
On 10/6/26 3:34 AM, ktkachov@nvidia.com wrote:
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> 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 83% at N=2048 and by 90% at N=4096. The whole compilation
> executes 18% fewer instructions at N=2048 and 24% fewer at N=4096.
>
> The new test checks that a name loses its bit when DOM propagates it
> into an assignment.
>
> Bootstrapped and tested as a series on aarch64-linux-gnu and
> x86_64-linux-gnu.
>
> Ok for trunk?
> Thanks,
> Kyrill
>
> Cc: Jeff Law <jeffrey.law@oss.qualcomm.com>
>
> gcc/ChangeLog:
>
> PR rtl-optimization/127661
> * 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:
>
> PR rtl-optimization/127661
> * gcc.dg/tree-ssa/pr127661.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
>
OK. I fear I'm like to reintroduce problems here when I revisit 90036,
but we'll deal with that at the appropriate time.
jeff
More information about the Gcc-patches
mailing list