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

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.

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.

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.

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