r15-6657 canonicalized signed arithmetic to unsigned, exposing a 17.5%
code-size regression in SPEC CPU2017 507.cactuBSSN_r at -O2. The resulting
nested sign-changing conversions and unsigned additions hide the common
induction variable from affine decomposition, causing IVOPTS to create an
extra outer-loop invariant.
The fix also slightly improves 507.cactuBSSN_r performance and improves
548.exchange2_r by about 6% on Intel GNR, AMD Zen 5, and Arm Graviton 5.
Since r15-6657 primarily regressed outer-loop IV computations, this is a
general improvement for workloads sensitive to outer-loop performance.
tree-affine normally uses the global range query, which ignores statement
context for SSA names. It therefore cannot prove that the conversions
preserve values or that modular additions do not wrap, even when both are
known at the IV use. Create a local ranger in IVOPTS and pass the use
statement to affine decomposition, making these contextual facts available
and allowing the common induction variable to cancel. Keep candidate
elimination bounds on context-free ranges because those bounds may be
materialized in the loop preheader.
Bootstrapped and regtested on x86_64-pc-linux-gnu{-m32,}.
Ok for trunk?
gcc/ChangeLog:
PR tree-optimization/126486
* tree-affine.cc (expr_to_aff_combination): Accept statement and
range-query context. Handle range-preserving sign changes and
unsigned modular additions.
(tree_to_aff_combination): Accept and propagate statement and range
query context.
* tree-affine.h (tree_to_aff_combination): Update declaration.
* tree-ssa-loop-ivopts.cc: Include gimple-range.h.
(ivopts_data::ranger): New member.
(tree_ssa_iv_optimize_init): Initialize it.
(get_computation_aff_1): Pass statement-local range context.
(cand_value_at): Explain why statement-local ranges are not used.
(tree_ssa_iv_optimize): Create a ranger for affine computations.
gcc/testsuite/ChangeLog:
PR tree-optimization/126486
* gcc.dg/tree-ssa/pr126486.c: New test.
Assisted-by: openai.gpt-5.6-sol xhigh <[email protected]>
---
gcc/testsuite/gcc.dg/tree-ssa/pr126486.c | 29 ++++
gcc/tree-affine.cc | 160 ++++++++++++++++++++---
gcc/tree-affine.h | 4 +-
gcc/tree-ssa-loop-ivopts.cc | 20 ++-
4 files changed, 188 insertions(+), 25 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr126486.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr126486.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr126486.c
new file mode 100644
index 00000000000..7ec81e2ecdd
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr126486.c
@@ -0,0 +1,29 @@
+/* PR tree-optimization/126486 */
+/* { dg-do compile { target lp64 } } */
+/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
+
+int
+foo (int n_dims, int *actual_indices, const long *input_array_dims,
+ int max_iter)
+{
+ int sum = 0;
+ int iter = 0;
+
+ while (iter < max_iter)
+ {
+ sum = actual_indices[0];
+ for (int k = n_dims - 1; k > 0; k--)
+ {
+ int product = 1;
+ for (int j = k - 1; j >= 0; j--)
+ product *= input_array_dims[j];
+ sum += actual_indices[k] * product;
+ }
+ iter++;
+ }
+ return sum;
+}
+
+/* The only invariant expression containing both K and INPUT_ARRAY_DIMS
+ should be the base of the address candidate. */
+/* { dg-final { scan-tree-dump-times "inv_expr \[0-9\]+:.*\\(unsigned long\\)
k_\[0-9\]+ \\* 8 \\+ \\(unsigned long\\) input_array_dims" 1 "ivopts" } } */
diff --git a/gcc/tree-affine.cc b/gcc/tree-affine.cc
index 181fd6fb33c..89e3cf207fc 100644
--- a/gcc/tree-affine.cc
+++ b/gcc/tree-affine.cc
@@ -265,22 +265,23 @@ aff_combination_convert (aff_tree *comb, tree type)
static bool
expr_to_aff_combination (aff_tree *comb, tree_code code, tree type,
- tree op0, tree op1 = NULL_TREE)
+ tree op0, tree op1 = NULL_TREE, gimple *at = NULL,
+ range_query *query = NULL)
{
aff_tree tmp;
switch (code)
{
case POINTER_PLUS_EXPR:
- tree_to_aff_combination (op0, type, comb);
- tree_to_aff_combination (op1, sizetype, &tmp);
+ tree_to_aff_combination (op0, type, comb, at, query);
+ tree_to_aff_combination (op1, sizetype, &tmp, at, query);
aff_combination_add (comb, &tmp);
return true;
case PLUS_EXPR:
case MINUS_EXPR:
- tree_to_aff_combination (op0, type, comb);
- tree_to_aff_combination (op1, type, &tmp);
+ tree_to_aff_combination (op0, type, comb, at, query);
+ tree_to_aff_combination (op1, type, &tmp, at, query);
if (code == MINUS_EXPR)
aff_combination_scale (&tmp, -1);
aff_combination_add (comb, &tmp);
@@ -289,18 +290,18 @@ expr_to_aff_combination (aff_tree *comb, tree_code code,
tree type,
case MULT_EXPR:
if (TREE_CODE (op1) != INTEGER_CST)
break;
- tree_to_aff_combination (op0, type, comb);
+ tree_to_aff_combination (op0, type, comb, at, query);
aff_combination_scale (comb, wi::to_widest (op1));
return true;
case NEGATE_EXPR:
- tree_to_aff_combination (op0, type, comb);
+ tree_to_aff_combination (op0, type, comb, at, query);
aff_combination_scale (comb, -1);
return true;
case BIT_NOT_EXPR:
/* ~x = -x - 1 */
- tree_to_aff_combination (op0, type, comb);
+ tree_to_aff_combination (op0, type, comb, at, query);
aff_combination_scale (comb, -1);
aff_combination_add_cst (comb, -1);
return true;
@@ -311,14 +312,108 @@ expr_to_aff_combination (aff_tree *comb, tree_code code,
tree type,
tree inner = op0;
tree itype = TREE_TYPE (inner);
enum tree_code icode = TREE_CODE (inner);
+ range_query *rquery = query;
/* STRIP_NOPS */
if (tree_nop_conversion_p (otype, itype))
{
- tree_to_aff_combination (op0, type, comb);
+ tree_to_aff_combination (op0, type, comb, at, query);
return true;
}
+ /* Remove a same-precision sign-changing intermediate conversion when
+ range information proves that it preserves the value. */
+ if (CONVERT_EXPR_P (inner)
+ && TREE_CODE (otype) == INTEGER_TYPE
+ && TREE_CODE (itype) == INTEGER_TYPE
+ && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
+ {
+ tree inner_op = TREE_OPERAND (inner, 0);
+ tree inner_type = TREE_TYPE (inner_op);
+
+ if (TREE_CODE (inner_type) == INTEGER_TYPE
+ && TYPE_PRECISION (inner_type) == TYPE_PRECISION (itype)
+ && TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (itype))
+ {
+ int_range_max vr;
+
+ if (!rquery)
+ rquery = get_range_query (cfun);
+ if (rquery->range_of_expr (vr, inner_op, at)
+ && !vr.varying_p ()
+ && !vr.undefined_p ()
+ && (TYPE_UNSIGNED (inner_type)
+ ? !wi::neg_p (vr.upper_bound (), SIGNED)
+ : !wi::neg_p (vr.lower_bound (), SIGNED)))
+ {
+ inner_op = fold_convert (otype, inner_op);
+ tree_to_aff_combination (inner_op, type, comb, at, query);
+ return true;
+ }
+ }
+ }
+
+ /* Handle a sign-changing conversion between an unsigned operation
+ and a wider conversion:
+
+ (T1) (T2) ((U) X + CST)
+
+ where T2 and U have the same precision and T2 is signed. If the
+ operation interpreted in T2 does not overflow, distribute the
+ conversion through the operation. */
+ if (CONVERT_EXPR_P (inner)
+ && TREE_CODE (otype) == INTEGER_TYPE
+ && TREE_CODE (itype) == INTEGER_TYPE
+ && !TYPE_UNSIGNED (itype)
+ && TYPE_PRECISION (otype) > TYPE_PRECISION (itype))
+ {
+ tree wrapped = TREE_OPERAND (inner, 0);
+ tree wtype = TREE_TYPE (wrapped);
+ tree_code wcode = TREE_CODE (wrapped);
+
+ if ((wcode == PLUS_EXPR || wcode == MINUS_EXPR)
+ && TREE_CODE (wtype) == INTEGER_TYPE
+ && TYPE_UNSIGNED (wtype)
+ && TYPE_PRECISION (wtype) == TYPE_PRECISION (itype)
+ && TREE_CODE (TREE_OPERAND (wrapped, 1)) == INTEGER_CST)
+ {
+ tree wop0 = fold_convert (itype, TREE_OPERAND (wrapped, 0));
+ tree wop1 = fold_convert (itype, TREE_OPERAND (wrapped, 1));
+ int_range_max vr;
+
+ if (!rquery)
+ rquery = get_range_query (cfun);
+ if (rquery->range_of_expr (vr, wop0, at)
+ && !vr.varying_p ()
+ && !vr.undefined_p ())
+ {
+ wi::overflow_type ovf1 = wi::OVF_NONE;
+ wi::overflow_type ovf2 = wi::OVF_NONE;
+ wide_int cst = wi::to_wide (wop1);
+
+ if (wcode == PLUS_EXPR)
+ {
+ wi::add (vr.lower_bound (), cst, SIGNED, &ovf1);
+ wi::add (vr.upper_bound (), cst, SIGNED, &ovf2);
+ }
+ else
+ {
+ wi::sub (vr.lower_bound (), cst, SIGNED, &ovf1);
+ wi::sub (vr.upper_bound (), cst, SIGNED, &ovf2);
+ }
+
+ if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE)
+ {
+ wop0 = fold_convert (otype, wop0);
+ wop1 = fold_convert (otype, wop1);
+ return expr_to_aff_combination (comb, wcode, otype,
+ wop0, wop1, at,
+ query);
+ }
+ }
+ }
+ }
+
/* In principle this is a valid folding, but it isn't necessarily
an optimization, so do it here and not in fold_unary. */
if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR)
@@ -338,7 +433,8 @@ expr_to_aff_combination (aff_tree *comb, tree_code code,
tree type,
{
op0 = fold_convert (otype, op0);
op1 = fold_convert (otype, op1);
- return expr_to_aff_combination (comb, icode, otype, op0, op1);
+ return expr_to_aff_combination (comb, icode, otype, op0, op1,
+ at, query);
}
wide_int minv, maxv;
/* If inner type has wrapping overflow behavior, fold conversion
@@ -346,10 +442,12 @@ expr_to_aff_combination (aff_tree *comb, tree_code code,
tree type,
(T1)(X *+- CST) -> (T1)X *+- (T1)CST
if X *+- CST doesn't overflow by range information. */
int_range_max vr;
+ if (!rquery)
+ rquery = get_range_query (cfun);
if (TYPE_UNSIGNED (itype)
&& TYPE_OVERFLOW_WRAPS (itype)
&& TREE_CODE (op1) == INTEGER_CST
- && get_range_query (cfun)->range_of_expr (vr, op0)
+ && rquery->range_of_expr (vr, op0, at)
&& !vr.varying_p ()
&& !vr.undefined_p ())
{
@@ -369,7 +467,24 @@ expr_to_aff_combination (aff_tree *comb, tree_code code,
tree type,
op0 = fold_convert (otype, op0);
op1 = fold_convert (otype, op1);
return expr_to_aff_combination (comb, icode, otype, op0,
- op1);
+ op1, at, query);
+ }
+ else if (icode == PLUS_EXPR
+ && wi::neg_p (wi::to_wide (op1), SIGNED))
+ {
+ wide_int pos_cst = wi::neg (wi::to_wide (op1));
+
+ /* X + CST in the wrapping type is X - -CST when X is
+ known to be at least -CST. */
+ if (wi::geu_p (minv, pos_cst))
+ {
+ op0 = fold_convert (otype, op0);
+ op1 = fold_convert (otype,
+ wide_int_to_tree (itype, pos_cst));
+ return expr_to_aff_combination (comb, MINUS_EXPR,
+ otype, op0, op1, at,
+ query);
+ }
}
}
}
@@ -385,7 +500,8 @@ expr_to_aff_combination (aff_tree *comb, tree_code code,
tree type,
/* Splits EXPR into an affine combination of parts. */
void
-tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
+tree_to_aff_combination (tree expr, tree type, aff_tree *comb, gimple *at,
+ range_query *query)
{
aff_tree tmp;
enum tree_code code;
@@ -404,13 +520,14 @@ tree_to_aff_combination (tree expr, tree type, aff_tree
*comb)
case MINUS_EXPR:
case MULT_EXPR:
if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
- TREE_OPERAND (expr, 1)))
+ TREE_OPERAND (expr, 1), at, query))
return;
break;
case NEGATE_EXPR:
case BIT_NOT_EXPR:
- if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0)))
+ if (expr_to_aff_combination (comb, code, type, TREE_OPERAND (expr, 0),
+ NULL_TREE, at, query))
return;
break;
@@ -418,7 +535,8 @@ tree_to_aff_combination (tree expr, tree type, aff_tree
*comb)
/* ??? TREE_TYPE (expr) should be equal to type here, but IVOPTS
calls this with not showing an outer widening cast. */
if (expr_to_aff_combination (comb, code,
- TREE_TYPE (expr), TREE_OPERAND (expr, 0)))
+ TREE_TYPE (expr), TREE_OPERAND (expr, 0),
+ NULL_TREE, at, query))
{
aff_combination_convert (comb, type);
return;
@@ -430,8 +548,10 @@ tree_to_aff_combination (tree expr, tree type, aff_tree
*comb)
if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
{
expr = TREE_OPERAND (expr, 0);
- tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb);
- tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp);
+ tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb, at,
+ query);
+ tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp,
+ at, query);
aff_combination_add (comb, &tmp);
return;
}
@@ -454,12 +574,12 @@ tree_to_aff_combination (tree expr, tree type, aff_tree
*comb)
aff_combination_add_elt (comb, core, 1);
else
{
- tree_to_aff_combination (core, type, &tmp);
+ tree_to_aff_combination (core, type, &tmp, at, query);
aff_combination_add (comb, &tmp);
}
if (toffset)
{
- tree_to_aff_combination (toffset, type, &tmp);
+ tree_to_aff_combination (toffset, type, &tmp, at, query);
aff_combination_add (comb, &tmp);
}
return;
diff --git a/gcc/tree-affine.h b/gcc/tree-affine.h
index 38d32ef1b4b..8ea648f0f1b 100644
--- a/gcc/tree-affine.h
+++ b/gcc/tree-affine.h
@@ -65,6 +65,7 @@ public:
};
class name_expansion;
+class range_query;
void aff_combination_const (aff_tree *, tree, const poly_widest_int &);
void aff_combination_elt (aff_tree *, tree, tree);
@@ -74,7 +75,8 @@ void aff_combination_add (aff_tree *, aff_tree *);
void aff_combination_add_elt (aff_tree *, tree, const widest_int &);
void aff_combination_remove_elt (aff_tree *, unsigned);
void aff_combination_convert (aff_tree *, tree);
-void tree_to_aff_combination (tree, tree, aff_tree *);
+void tree_to_aff_combination (tree, tree, aff_tree *, gimple * = NULL,
+ range_query * = NULL);
tree aff_combination_to_tree (aff_tree *);
void unshare_aff_combination (aff_tree *);
bool aff_combination_constant_multiple_p (aff_tree *, aff_tree *,
diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
index 5a4254290d8..f70d39cd978 100644
--- a/gcc/tree-ssa-loop-ivopts.cc
+++ b/gcc/tree-ssa-loop-ivopts.cc
@@ -133,6 +133,7 @@ along with GCC; see the file COPYING3. If not see
#include "dbgcnt.h"
#include "cfganal.h"
#include "gimple-fold.h"
+#include "gimple-range.h"
/* For lang_hooks.types.type_for_mode. */
#include "langhooks.h"
@@ -620,6 +621,9 @@ struct ivopts_data
/* Cache used by tree_to_aff_combination_expand. */
hash_map<tree, name_expansion *> *name_expansion_cache;
+ /* Range query for statement-local affine simplifications. */
+ range_query *ranger;
+
/* The hashtable of common candidates derived from iv uses. */
hash_table<iv_common_cand_hasher> *iv_common_cand_tab;
@@ -1086,6 +1090,7 @@ tree_ssa_iv_optimize_init (struct ivopts_data *data)
data->vcands.create (20);
data->inv_expr_tab = new hash_table<iv_inv_expr_hasher> (10);
data->name_expansion_cache = NULL;
+ data->ranger = NULL;
data->base_object_map = NULL;
data->iv_common_cand_tab = new hash_table<iv_common_cand_hasher> (10);
data->iv_common_cands.create (20);
@@ -4037,9 +4042,11 @@ get_computation_aff_1 (struct ivopts_data *data, gimple
*at, struct iv_use *use,
common_type = determine_common_wider_type (&ubase, &cbase);
/* use = ubase - ratio * cbase + ratio * var. */
- tree_to_aff_combination (ubase, common_type, aff_inv);
- tree_to_aff_combination (cbase, common_type, &aff_cbase);
- tree_to_aff_combination (var, uutype, aff_var);
+ tree_to_aff_combination (ubase, common_type, aff_inv, at,
+ data->ranger);
+ tree_to_aff_combination (cbase, common_type, &aff_cbase, at,
+ data->ranger);
+ tree_to_aff_combination (var, uutype, aff_var, at, data->ranger);
/* We need to shift the value if we are after the increment. */
if (stmt_after_increment (data->current_loop, cand, at))
@@ -4051,7 +4058,8 @@ get_computation_aff_1 (struct ivopts_data *data, gimple
*at, struct iv_use *use,
else
cstep_common = cstep;
- tree_to_aff_combination (cstep_common, common_type, &cstep_aff);
+ tree_to_aff_combination (cstep_common, common_type, &cstep_aff, at,
+ data->ranger);
aff_combination_add (&aff_cbase, &cstep_aff);
}
@@ -5105,6 +5113,8 @@ cand_value_at (class loop *loop, struct iv_cand *cand,
gimple *at,
}
}
+ /* The result may be materialized in the loop preheader. Do not use range
+ information that is only valid at AT when simplifying it. */
tree_to_aff_combination (iv->step, TREE_TYPE (iv->step), &step);
aff_combination_convert (&step, steptype);
tree_to_aff_combination (niter, TREE_TYPE (niter), &nit);
@@ -8245,6 +8255,8 @@ tree_ssa_iv_optimize (void)
tree_ssa_iv_optimize_init (&data);
mark_ssa_maybe_undefs ();
+ gimple_ranger ranger (false);
+ data.ranger = &ranger;
/* Optimize the loops starting with the innermost ones. */
for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
--
2.34.1
