[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