Re: [PATCH 0/5] reassoc: Linearize and optimize plus/mult trees.

On Fri, Aug 7, 2026 at 9:26 PM Robin Dapp <[email protected]> wrote:
>
> From: Robin Dapp <[email protected]>
>
> This is something that has been cooking since over two years ago.  The
> idea originated in PR113583 where we should eliminate and conflate
> floating-point factors and constants in order to reduce the number of
> FMAs in a loop.
>
> I dropped the patch and picked it up back up multiple times as I wasn't
> terribly motivated by the rarity of suitable sequences.  Also, initially
> I intended to enhance linearize_expr_tree to always handle plus/mult
> trees but that turned out to be much too complicated in several ways.
>
> Only recently, when realizing that backprop cannot solve PR122209, I
> figured that a simpler approach could also work and happens to help both
> PRs.

Some highlevel comments here.

> A motivating example is:
>   2 + a + 3 * (a + 4)
>
> Reassoc normally only linearizes trees with the same operation and would
> give up at the first * in the tree (with some exceptions that don't
> apply to my case).
>
> As long as we restrict ourselves to +, *, and constants, the tree can be
> considered "linear with factors" like a polynomial.  We can
> "pre-linearize" such a tree and optimize the whole "polynomial" as one.
> Afterwards, we expand the optimized output and linearize in the usual
> way.

I'll note this applies to other operator pairs as well, & and | mainly, with
either one being able to stand in for the other.  There's also negation
to be considered (or bit-not), but we currently handle this by
pre-processing negates, but recursively for  2 + a - 3 * (a + 4) IIRC.

There's undistribute_ops_list which does the reverse of "expanding"
(hardwired to plus/mult).  This handles non-constant factors just fine,
so I wonder why you want to restrict expanding to constant factors?

> Patch 1 adds the basic plumbing and a cost model for rewriting
> unsigned-integer trees.
>
> Patch 3 and 4 extend the basic structure to floating-point and vectors.
>
> Patch 2 adds restricted but general overflow/signed-type support to
> reassoc.  It is not a perfect fit here and it could also work
> independently of the plus/mult-tree handling.  As combining both nicely
> increases applicability of overflow handling, I still went ahead.

I do like to see this independently.  I'll note that we have to be careful
to not throw away all UB overflow knowledge without good reason.  If
we consider CSE and (a + b) + c vs. a + (b + c) then with unsigned
arithmetic we achieve that by reassoc canonicalizing the summation
order.  For signed arithmetic we'd like to do the same, but we have to
realize that the associated sequence is already computed at a
dominating place to avoid rewriting the sequence into unsigned.

> Patch 5 follows through with the combination and allows rewriting signed
> scalar integer and vector integer trees.  Note this is still range based
> and does not perform a (int)((unsigned) + (unsigned)) rewrite that would
> allow us to go ahead without considering overflow.  With the cost model,
> we'd even have a chance of selecting which sequences to transform,
> rather than just everything.
>
> I wanted to get this out of the door to give people a chance to have a
> glimpse, even though I'm going to be unavailable for the next two weeks
> and won't be able to respond to feedback.
>
> As mentioned in the beginning, the whole scheme doesn't have
> particularly many hits across SPEC.  I observed a whopping 0.0%
> improvement in icount for SPECint.  The heaviest hitter is 519.lbm when
> built with -ffast-math were we should be seeing double-digit
> improvements, at least when not vectorized.  I'd still argue the whole
> thing is not pointless as we can still relax some restrictions and do
> better.
>
> The commit message of patch 1 has some more details regarding tradeoffs
> and costing.  The latter is likely going to be controversial.
>
> Bootstrapped and regtested on x86, power10, and aarch64.
> Regtested on riscv64 with a bit of acceptable test-expectation fallout.
>
> Robin Dapp (5):
>   reassoc: Linearize mixed plus/mult trees.
>   reassoc: Initial overflow support.
>   reassoc: Rewrite floating-point plus/mult trees.
>   reassoc: Rewrite vector plus/mult trees.
>   reassoc: Rewrite signed plus/mult trees.
>
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-45.c    |   4 +-
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c    |  49 ++
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-53.c    |  30 +
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-54.c    |  18 +
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-55.c    |  30 +
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-56.c    |  53 ++
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-57.c    |  53 ++
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c    |  30 +
>  gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c    |  10 +
>  .../gcc.dg/tree-ssa/reassoc-signed-1.c        |  24 +
>  gcc/tree-ssa-reassoc.cc                       | 815 +++++++++++++++++-
>  11 files changed, 1105 insertions(+), 11 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-53.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-54.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-55.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-56.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-57.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c
>
> --
> 2.54.0
>