From: Robin Dapp <[email protected]>
With the wrappers in place, it's easy to add overflow handling for the
signed/plus rewriting. This patch checks for overflow when adding or
multiplying the multiplicative factors using wi::overflow_type and tries
to prove factor * op overflow through ranges. If we encounter an overflow, we
cancel the descent and don't rewrite. Otherwise we can safely continue.
PR tree-optimization/122209
gcc/ChangeLog:
* tree-ssa-reassoc.cc (struct mult_factor): Handle overflows
in plus/mul.
(struct plus_mult_tree_state): Add overflow flag.
(linearize_plus_mult_tree): Handle overflow.
(rewrite_plus_mult_tree): Cancel on overflow.
(reassociate_bb): Allow overflow for plus/mult rewrite.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/reassoc-52.c: Remove xfail.
* gcc.dg/tree-ssa/reassoc-56.c: Likewise.
* gcc.dg/tree-ssa/reassoc-58.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c | 4 +-
gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c | 30 ++++
gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c | 10 ++
gcc/tree-ssa-reassoc.cc | 157 +++++++++++++++++----
4 files changed, 172 insertions(+), 29 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
index 5a194a8c9dd..37a779fb0ab 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
@@ -45,5 +45,5 @@ baz (char fs)
/* { dg-final { scan-tree-dump-times "\\* 14;" 1 "optimized" } } */
/* { dg-final { scan-tree-dump-times "\\* 26;" 1 "optimized" } } */
/* { dg-final { scan-tree-dump-times "\\* 5;" 1 "optimized" } } */
-/* { dg-final { scan-tree-dump-times "\\* 6;" 1 "optimized" { xfail *-*-* } }
} */
-/* { dg-final { scan-tree-dump-times "\\* 80;" 1 "optimized" { xfail *-*-* } }
} */
+/* { dg-final { scan-tree-dump-times "\\* 6;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\* 80;" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
new file mode 100644
index 00000000000..65eafcaf026
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O2 -fdump-tree-reassoc-details
-fdump-tree-optimized" } */
+
+int
+foo (int t)
+{
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+ t += 3 + 3 * t;
+ t &= 0xFFF;
+
+ return t;
+}
+
+/* { dg-final { scan-tree-dump "4095" "optimized" } } */
+/* { dg-final { scan-tree-dump-times "Rewriting plus/mult" 8 "reassoc1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c
b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c
new file mode 100644
index 00000000000..804bcf12ce9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O2 -fdump-tree-reassoc-details
-fdump-tree-optimized" } */
+
+int
+foo (int t)
+{
+ return t + 0x3fffffff + 0x3fffffff + t;
+}
+
+/* { dg-final { scan-tree-dump-times "cannot prove no overflow" 2 "reassoc1" }
} */
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index 54a7be64e54..c99cb953f0c 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -1916,7 +1916,7 @@ struct mult_factor
return real_equal (&fcst, &dconst0);
}
- void mul (tree other)
+ bool mul (tree other)
{
tree other_type = TREE_TYPE (other);
gcc_checking_assert ((!is_float
@@ -1929,24 +1929,19 @@ struct mult_factor
other = uniform_vector_p (other);
if (!is_float)
- cst = wi::mul (cst, wi::to_wide (other));
+ {
+ wi::overflow_type ovf;
+ cst = wi::mul (cst, wi::to_wide (other), TYPE_SIGN (type), &ovf);
+ if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+ return false;
+ }
else
real_arithmetic (&fcst, MULT_EXPR, &fcst,
TREE_REAL_CST_PTR (other));
+ return true;
}
- void mul (mult_factor &other)
- {
- gcc_checking_assert (is_float == other.is_float);
- gcc_checking_assert (is_vector == other.is_vector);
- if (!is_float)
- cst = wi::mul (cst, other.cst);
- else
- real_arithmetic (&fcst, MULT_EXPR, &fcst,
- &other.fcst);
- }
-
- void plus (tree other)
+ bool plus (tree other)
{
tree other_type = TREE_TYPE (other);
gcc_checking_assert ((!is_float
@@ -1959,29 +1954,47 @@ struct mult_factor
other = uniform_vector_p (other);
if (!is_float)
- cst = wi::add (cst, wi::to_wide (other));
+ {
+ wi::overflow_type ovf;
+ cst = wi::add (cst, wi::to_wide (other), TYPE_SIGN (type), &ovf);
+ if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+ return false;
+ }
else
real_arithmetic (&fcst, PLUS_EXPR, &fcst,
TREE_REAL_CST_PTR (other));
+ return true;
}
- void plus (mult_factor &other)
+ bool plus (mult_factor &other)
{
gcc_checking_assert (is_float == other.is_float);
gcc_checking_assert (is_vector == other.is_vector);
if (!is_float)
- cst = wi::add (cst, other.cst);
+ {
+ wi::overflow_type ovf;
+ cst = wi::add (cst, other.cst, TYPE_SIGN (type), &ovf);
+ if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+ return false;
+ }
else
real_arithmetic (&fcst, PLUS_EXPR, &fcst,
&other.fcst);
+ return true;
}
- void neg ()
+ bool neg ()
{
if (!is_float)
- cst = wi::neg (cst);
+ {
+ wi::overflow_type ovf;
+ cst = wi::neg (cst, &ovf);
+ if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+ return false;
+ }
else
fcst = real_value_negate (&fcst);
+ return true;
}
bool is_one ()
@@ -2072,6 +2085,9 @@ struct plus_mult_tree_state
be considered not worthwhile according to costing. */
bool changed;
+ /* True if we introduced overflow. */
+ bool overflow;
+
/* Operands of the cst/plus/mult sequence in program order. */
auto_vec<tree> ops;
/* Maps SSA names to their multiplicative factors. */
@@ -2089,6 +2105,7 @@ struct plus_mult_tree_state
maybe_expensive_constants_before (0),
maybe_expensive_constants_after (0),
changed (false),
+ overflow (false),
cst (build_zero_cst (type)) {}
};
@@ -2115,8 +2132,18 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
{
if (constant_maybe_expensive (op))
state->maybe_expensive_constants_before++;
- factor.mul (op);
- state->cst.plus (factor);
+ bool ok = factor.mul (op);
+ if (!ok)
+ {
+ state->overflow = true;
+ return;
+ }
+ ok = state->cst.plus (factor);
+ if (!ok)
+ {
+ state->overflow = true;
+ return;
+ }
if (!state->cst.is_zero () || !factor.is_one ())
state->changed = true;
return;
@@ -2128,7 +2155,7 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
&& has_single_use (op)
&& (((INTEGRAL_TYPE_P (TREE_TYPE (op))
|| VECTOR_INTEGER_TYPE_P (TREE_TYPE (op)))
- && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op)))
+ /*&& TYPE_OVERFLOW_WRAPS (TREE_TYPE (op))*/)
|| FLOAT_TYPE_P (TREE_TYPE (op))))
{
gimple *stmt = SSA_NAME_DEF_STMT (op);
@@ -2154,7 +2181,12 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
{
state->mults_before++;
state->visited.safe_push (stmt);
- factor.mul (rhs2);
+ bool ok = factor.mul (rhs2);
+ if (!ok)
+ {
+ state->overflow = true;
+ return;
+ }
linearize_plus_mult_tree (rhs1, factor, state, loop);
return;
}
@@ -2169,7 +2201,12 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
else if (opcode == NEGATE_EXPR)
{
state->visited.safe_push (stmt);
- factor.neg ();
+ bool ok = factor.neg ();
+ if (!ok)
+ {
+ state->overflow = true;
+ return;
+ }
linearize_plus_mult_tree (rhs1, factor, state, loop);
return;
}
@@ -2182,7 +2219,14 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
bool existed;
mult_factor &slot = state->op_factor_map.get_or_insert (op, &existed);
if (existed)
- slot.plus (factor);
+ {
+ bool ok = slot.plus (factor);
+ if (!ok)
+ {
+ state->overflow = true;
+ return;
+ }
+ }
else
slot = factor;
@@ -2355,6 +2399,44 @@ cost_plus_mult_tree (plus_mult_tree_state *state)
return worthwhile;
}
+/* Return true if the tree in rewritten form as described by STATE can
+ overflow or false otherwise.
+ This relies on the ranges of the linearized ops. We check the overflow
+ mult_factor * OP
+ as well as the partial sum up to OP. */
+
+static bool
+plus_mult_tree_overflow_p (struct plus_mult_tree_state *state)
+{
+ wide_int sum_lo = state->cst.cst;
+ wide_int sum_hi = state->cst.cst;
+ for (tree op : state->ops)
+ {
+ mult_factor &factor = *state->op_factor_map.get (op);
+ if (factor.is_zero ())
+ continue;
+ int_range_max r;
+ get_range_query (cfun)->range_of_expr (r, op);
+
+ wi::overflow_type ovf1, ovf2;
+ wide_int lo1 = wi::mul (r.lower_bound (), factor.cst, TYPE_SIGN
+ (TREE_TYPE (op)), &ovf1);
+ wide_int hi1 = wi::mul (r.upper_bound (), factor.cst, TYPE_SIGN
+ (TREE_TYPE (op)), &ovf2);
+ if (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE)
+ return true;
+
+ sum_hi = wi::add (sum_hi, wi::smax (hi1, lo1),
+ TYPE_SIGN (TREE_TYPE (op)), &ovf2);
+ sum_lo = wi::add (sum_lo, wi::smin (lo1, hi1),
+ TYPE_SIGN (TREE_TYPE (op)), &ovf1);
+ if (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE)
+ return true;
+ }
+
+ return false;
+}
+
/* Try to rewrite/expand a tree consisting of additions, multiplications
by constants, and negates like
a + 3 * (a + b + 1) + 2
@@ -2389,8 +2471,30 @@ rewrite_plus_mult_tree (gimple *stmt)
if (!state.changed)
return false;
+ if (state.overflow)
+ return false;
+
gather_plus_mult_tree_stats (&state);
+ /* Check for overflow. */
+ if ((INTEGRAL_TYPE_P (type)
+ || VECTOR_INTEGER_TYPE_P (type))
+ && TYPE_OVERFLOW_UNDEFINED (type))
+ {
+ if ((INTEGRAL_TYPE_P (type)
+ && plus_mult_tree_overflow_p (&state))
+ || VECTOR_INTEGER_TYPE_P (type))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Not rewriting plus/mult tree at ");
+ print_generic_expr (dump_file, lhs);
+ fprintf (dump_file, ": cannot prove no overflow.\n");
+ }
+ return false;
+ }
+ }
+
/* Check if it's worthwhile to follow through with the expansion. */
bool worthwhile = cost_plus_mult_tree (&state);
@@ -7716,8 +7820,7 @@ reassociate_bb (basic_block bb)
|| (FLOAT_TYPE_P (TREE_TYPE (lhs))
&& !HONOR_NANS (TREE_TYPE (lhs))
&& !HONOR_SIGNED_ZEROS (TREE_TYPE (lhs))))
- && has_single_use (lhs)
- && !type_can_overflow)
+ && has_single_use (lhs))
{
if (rewrite_plus_mult_tree (stmt))
{
--
2.54.0
