On Fri, Aug 7, 2026 at 9:26 PM Robin Dapp <[email protected]> wrote:
>
> From: Robin Dapp <[email protected]>
>
> This patch tries to start small and introduces simple signed-type
> handling to reassoc. It adds an tree_overflow_p function that checks a
> PLUS_EXPR tree for overflow via global ranges, summing up the minima and
> maxima of the operands. This needs to happen before linearization.
How often does this work in practice? That is, where do we get those
ranges from? When I thought about re-associating signed expressions
I've always thought we'll have to rewrite to unsigned arithmetic and the
important thing is to avoid that when the expressions do not simplify.
Also you seem to require the whole expression to have no possible
overflow (in any association). But if you'd integrate the check into
the linearization step itself you could stop expanding problematic
leafs instead? The key observation is that (a + b) might have
a smaller range than a and b individually (also not sure how often
this happens in practice).
That said, I think a tree_overflow_p check would be more useful
at the rewriting stage to assess whether we need to pun to
an unsigned type and also possibly to find an optimal association
that allows to keep signed arithmetic?
> If we confirmed there is no overflow, reassoc's optimizations can run
> uninhibited. There are currently just two exceptions, plus-mult rewriting
> and undistribute_ops_list, which builds additional chains for each operand.
>
> gcc/ChangeLog:
>
> * tree-ssa-reassoc.cc (tree_overflow_p): New function.
> (reassociate_bb): Use new function.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/reassoc-signed-1.c: New test.
> ---
> .../gcc.dg/tree-ssa/reassoc-signed-1.c | 24 ++++
> gcc/tree-ssa-reassoc.cc | 119 ++++++++++++++++--
> 2 files changed, 134 insertions(+), 9 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c
> new file mode 100644
> index 00000000000..bf0bab189b9
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c
> @@ -0,0 +1,24 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int foo (int a, int b, int c, int d)
> +{
> + a &= 0xff;
> + b &= 0xff;
> + c &= 0xff;
> + d &= 0xff;
> + return a + b + a + c + a + d + b;
> +}
> +
> +int bar (char a, char b, char c, char d)
> +{
> + return a + b + a + c + a + d + b;
> +}
> +
> +int baz (int a, int b, int c, int d)
> +{
> + return a + b + a + c + a + d + b;
> +}
> +
> +/* { dg-final { scan-tree-dump-times " \\* 3" 2 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times " \\* 2" 2 "optimized" } } */
> diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
> index f570c0164f4..211e8778d6c 100644
> --- a/gcc/tree-ssa-reassoc.cc
> +++ b/gcc/tree-ssa-reassoc.cc
> @@ -55,6 +55,7 @@ along with GCC; see the file COPYING3. If not see
> #include "tree-ssa-math-opts.h"
> #include "gimple-range.h"
> #include "internal-fn.h"
> +#include "value-range.h"
>
> /* This is a simple global reassociation pass. It is, in part, based
> on the LLVM pass of the same name (They do some things more/less
> @@ -7326,6 +7327,89 @@ rank_ops_for_fma (vec<operand_entry *> *ops)
> }
> return mult_num;
> }
> +
> +/* Check if we can linearize the expression tree starting at STMT.
> + FORNOW only support PLUS_EXPR is supported. We sum all minima and
> + maxima of the operands in the tree in widest_int and check whether the
> + result exceeds the operands's type. If so, or if we don't have range
> + information for any operand, conservatively return true. Otherwise
> + return false. */
> +
> +static bool
> +tree_overflow_p (tree_code code, gimple *stmt, struct loop *loop)
> +{
> + if (!is_gimple_assign (stmt))
> + return true;
> +
> + tree lhs = gimple_assign_lhs (stmt);
> + tree type = TREE_TYPE (lhs);
> +
> + if (VECTOR_TYPE_P (type))
> + return true;
> +
> + if (code != PLUS_EXPR)
> + return true;
> +
> + signop sgn = TYPE_SIGN (type);
> + widest_int sum_hi = 0, sum_lo = 0;
> + widest_int zero = 0;
> +
> + auto_vec <gimple *> worklist;
> + worklist.safe_push (stmt);
> + int_range_max range;
> +
> + while (!worklist.is_empty ())
> + {
> + gimple *cur = worklist.pop ();
> +
> + /* We always have two ops, because we only descend into PLUS_EXPRs. */
> + for (int i = 1; i <= 2; i++)
> + {
> + tree op = gimple_op (cur, i);
> +
> + /* Just like linearize_expr_tree, descend if the statement is
> + plus-reassociable and doesn't throw. */
> + if (TREE_CODE (op) == SSA_NAME)
> + {
> + gimple *def_op = SSA_NAME_DEF_STMT (op);
> + if (is_reassociable_op (def_op, PLUS_EXPR, loop)
> + && !stmt_could_throw_p (cfun, def_op))
> + {
> + worklist.safe_push (def_op);
> + continue;
> + }
> + }
> +
> + /* Add a leave's range to the global sums.
> + We clamp the ranges to zero so we can catch e.g.
> + (INT_MAX + 1) - 1
> + whose total sum would be INT_MAX but (INT_MAX + 1) still
> + overflows. */
> + if (get_range_query (cfun)->range_of_expr (range, op)
> + && !range.undefined_p ())
> + {
> + sum_hi = wi::add (sum_hi,
> + wi::smax (widest_int::from
> + (range.upper_bound (), sgn),
> + zero));
> + sum_lo = wi::add (sum_lo,
> + wi::smin (widest_int::from
> + (range.lower_bound (), sgn),
> + zero));
> + }
> + else
> + return true;
> + }
> + }
> +
> + bool hi_ok = wi::le_p
> + (sum_hi, widest_int::from (wi::max_value (type), sgn), sgn);
> + bool lo_ok = wi::ge_p
> + (sum_lo, widest_int::from (wi::min_value (type), sgn), sgn);
> + return !hi_ok || !lo_ok;
> +}
> +
> +
> /* Reassociate expressions in basic block BB and its post-dominator as
> children.
>
> @@ -7385,15 +7469,22 @@ reassociate_bb (basic_block bb)
> lhs = gimple_assign_lhs (stmt);
> rhs1 = gimple_assign_rhs1 (stmt);
> rhs2 = gimple_assign_rhs2 (stmt);
> + tree type = TREE_TYPE (rhs1);
> +
> + bool type_can_overflow = INTEGRAL_TYPE_P (type)
> + && TYPE_OVERFLOW_UNDEFINED (type);
> +
> + bool operation_can_overflow = rhs_code != BIT_IOR_EXPR
> + && rhs_code != BIT_AND_EXPR
> + && rhs_code != BIT_XOR_EXPR
> + && rhs_code != MIN_EXPR
> + && rhs_code != MAX_EXPR;
>
> /* For non-bit or min/max operations we can't associate
> all types. Verify that here. */
> - if ((rhs_code != BIT_IOR_EXPR
> - && rhs_code != BIT_AND_EXPR
> - && rhs_code != BIT_XOR_EXPR
> - && rhs_code != MIN_EXPR
> - && rhs_code != MAX_EXPR
> - && !can_reassociate_type_p (TREE_TYPE (lhs)))
> + if ((operation_can_overflow
> + && !can_reassociate_type_p (TREE_TYPE (lhs))
> + && !type_can_overflow)
> || !can_reassociate_op_p (rhs1)
> || !can_reassociate_op_p (rhs2))
> continue;
> @@ -7416,7 +7507,8 @@ reassociate_bb (basic_block bb)
> do so. While at it, remove 0-factor elements. */
> if ((rhs_code == PLUS_EXPR || rhs_code == MULT_EXPR)
> && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> - && has_single_use (lhs))
> + && has_single_use (lhs)
> + && !type_can_overflow)
> {
> if (rewrite_plus_mult_tree (stmt))
> {
> @@ -7430,13 +7522,22 @@ reassociate_bb (basic_block bb)
> }
> }
>
> + /* Check overflow before linearization as that can already
> + introduce undefined behavior by rewriting. */
> + if (type_can_overflow
> + && operation_can_overflow
> + && tree_overflow_p (rhs_code, stmt,
> + loop_containing_stmt (stmt)))
> + continue;
> +
> linearize_expr_tree (&ops, stmt, true, true);
> int orig_len = ops.length ();
> ops.qsort (sort_by_operand_rank);
> optimize_ops_list (rhs_code, &ops);
>
> - if (undistribute_ops_list (rhs_code, &ops,
> - loop_containing_stmt (stmt)))
> + if (!type_can_overflow
> + && undistribute_ops_list (rhs_code, &ops,
> + loop_containing_stmt (stmt)))
> {
> ops.qsort (sort_by_operand_rank);
> optimize_ops_list (rhs_code, &ops);
> --
> 2.54.0
>
