From: Rachit Mehta <[email protected]>
SCEV cannot represent a period-2 recurrence, so recognize loops of the
form 'c = -c' with a constant trip count in the final-value replacement
and replace the exit value by c or -c depending on the parity of the trip
count. Bail out when signed overflow must trap (-ftrapv) or be sanitized,
mirroring the existing bitop special-cases.
PR tree-optimization/114502
gcc/ChangeLog:
* tree-scalar-evolution.cc (analyze_and_compute_negate_effect): New.
(final_value_replacement_loop): Call it.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/scev-negate-1.c: New test.
* gcc.dg/tree-ssa/scev-negate-2.c: New test.
* gcc.dg/tree-ssa/scev-negate-3.c: New test.
Signed-off-by: Rachit Mehta <[email protected]>
---
gcc/testsuite/gcc.dg/tree-ssa/scev-negate-1.c | 47 ++++++++
gcc/testsuite/gcc.dg/tree-ssa/scev-negate-2.c | 65 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/scev-negate-3.c | 82 ++++++++++++++
gcc/tree-scalar-evolution.cc | 103 +++++++++++++++++-
4 files changed, 296 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-negate-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-negate-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-negate-3.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-1.c
new file mode 100644
index 0000000000000..c3ef0704532be
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-1.c
@@ -0,0 +1,47 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+/* Test idempotent NEGATE_EXPR optimization with constant trip counts.
+ Even iteration count leaves value unchanged; odd count negates it.
+ Trip counts are kept large enough to avoid complete loop unrolling,
+ so the recurrence reaches the SCCP final-value replacement. */
+
+unsigned
+neg_even (unsigned c)
+{
+ for (int i = 0; i < 1024; i++)
+ c *= -1;
+ return c;
+}
+
+unsigned
+neg_odd (unsigned c)
+{
+ for (int i = 0; i < 1025; i++)
+ c *= -1;
+ return c;
+}
+
+unsigned
+neg_while (unsigned c)
+{
+ int i = 0;
+ while (i < 100)
+ {
+ c = -c;
+ i++;
+ }
+ return c;
+}
+
+unsigned
+neg_odd2 (unsigned c)
+{
+ for (int i = 0; i < 101; i++)
+ c *= -1;
+ return c;
+}
+
+/* { dg-final { scan-tree-dump-times "Idempotent NEGATE_EXPR" 4 "sccp" } } */
+/* { dg-final { scan-tree-dump-times "with expr: c_\[0-9\]+\\(D\\)" 2 "sccp" }
} */
+/* { dg-final { scan-tree-dump-times "with expr: -c_\[0-9\]+\\(D\\)" 2 "sccp"
} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-2.c
new file mode 100644
index 0000000000000..64388c165f67e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-2.c
@@ -0,0 +1,65 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+/* Edge cases with constant trip counts. */
+
+unsigned
+neg_conditional (unsigned c, int cond)
+{
+ if (cond)
+ for (int i = 0; i < 100; i++)
+ c *= -1;
+ return c;
+}
+
+unsigned
+neg_nested (unsigned c)
+{
+ for (int j = 0; j < 100; j++)
+ for (int i = 0; i < 100; i++)
+ c *= -1;
+ return c;
+}
+
+unsigned
+neg_do_while (unsigned c)
+{
+ int i = 0;
+ do
+ {
+ c = -c;
+ i++;
+ }
+ while (i < 100);
+ return c;
+}
+
+unsigned
+neg_odd_extra (unsigned c)
+{
+ for (int i = 0; i < 101; i++)
+ c *= -1;
+ return c;
+}
+
+unsigned
+neg_large_even (unsigned c)
+{
+ for (int i = 0; i < 1000000; i++)
+ c *= -1;
+ return c;
+}
+
+unsigned
+neg_large_odd (unsigned c)
+{
+ for (int i = 0; i < 999999; i++)
+ c *= -1;
+ return c;
+}
+
+/* { dg-final { scan-tree-dump-times "Idempotent NEGATE_EXPR" 6 "sccp" } } */
+/* neg_nested's inner loop is replaced by an intermediate value, not a
+ parameter default-def, so only 3 even cases match the "(D)" pattern. */
+/* { dg-final { scan-tree-dump-times "with expr: c_\[0-9\]+\\(D\\)" 3 "sccp" }
} */
+/* { dg-final { scan-tree-dump-times "with expr: -c_\[0-9\]+\\(D\\)" 2 "sccp"
} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-3.c
new file mode 100644
index 0000000000000..1694d9d69c240
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-negate-3.c
@@ -0,0 +1,82 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fwrapv -fdump-tree-sccp-details" } */
+
+#include <limits.h>
+
+/* noipa keeps the loop bodies intact and forces real calls. */
+
+unsigned __attribute__((noipa))
+neg_runtime (unsigned c, int n)
+{
+ for (int i = 0; i < n; i++)
+ c *= -1;
+ return c;
+}
+
+int __attribute__((noipa))
+neg_signed_even (int c)
+{
+ for (int i = 0; i < 100; i++)
+ c = -c;
+ return c;
+}
+
+int __attribute__((noipa))
+neg_signed_odd (int c)
+{
+ for (int i = 0; i < 101; i++)
+ c = -c;
+ return c;
+}
+
+long __attribute__((noipa))
+neg_long_even (long c)
+{
+ for (int i = 0; i < 1000; i++)
+ c = -c;
+ return c;
+}
+
+int
+main (void)
+{
+ /* Zero-iteration path returns the initial value. */
+ if (neg_runtime (5u, 0) != 5u)
+ __builtin_abort ();
+
+ /* Even parity -> unchanged. */
+ if (neg_runtime (7u, 1024) != 7u)
+ __builtin_abort ();
+ if (neg_runtime (7u, 2) != 7u)
+ __builtin_abort ();
+
+ /* Odd parity -> negated (unsigned wraps: -7u). */
+ if (neg_runtime (7u, 1025) != (unsigned) -7)
+ __builtin_abort ();
+ if (neg_runtime (7u, 1) != (unsigned) -7)
+ __builtin_abort ();
+
+ /* Signed even count, incl. INT_MIN: even parity introduces no negation. */
+ if (neg_signed_even (INT_MIN) != INT_MIN)
+ __builtin_abort ();
+ if (neg_signed_even (-9) != -9)
+ __builtin_abort ();
+
+ /* Signed odd count: value negated. */
+ if (neg_signed_odd (5) != -5)
+ __builtin_abort ();
+ if (neg_signed_odd (-3) != 3)
+ __builtin_abort ();
+
+ /* Long type even count: value unchanged. */
+ if (neg_long_even (123L) != 123L)
+ __builtin_abort ();
+ if (neg_long_even (-456L) != -456L)
+ __builtin_abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Idempotent NEGATE_EXPR" 3 "sccp" } } */
+/* { dg-final { scan-tree-dump-times "with expr: c_\[0-9\]+\\(D\\)" 2 "sccp" }
} */
+/* { dg-final { scan-tree-dump-times "with expr: -c_\[0-9\]+\\(D\\)" 1 "sccp"
} } */
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index cd99cbe86ce5a..43125926a22e6 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3862,6 +3862,100 @@ analyze_and_compute_bitop_with_inv_effect (class loop*
loop, tree phidef,
return fold_build2 (code1, type, inv, match_op[0]);
}
+/* Recognize and analyze the unary negation loop pattern.
+
+ Detects loops of the form
+ for (i = 0; i < n; i++)
+ c = -c;
+ such as those produced by writing c *= -1.
+
+ The loop body negates C exactly N times, so the final value depends only
+ on the parity of the (constant) trip count N:
+ N even -> c_init (unchanged)
+ N odd -> -c_init (negated)
+
+ NITER is the number of latch executions (N == NITER + 1) and must be
+ constant so the parity is known at compile time.
+
+ Return the replacement expression, or NULL_TREE when the pattern does
+ not apply. */
+
+static tree
+analyze_and_compute_negate_effect (class loop *loop, tree phidef, tree niter)
+{
+ tree op_arg, init;
+ gphi *header_phi = NULL;
+ gimple *def;
+
+ /* PHIDEF must be a plain SSA name; reject virtual operands and names
+ that occur in abnormal PHIs. */
+ if (TREE_CODE (phidef) != SSA_NAME
+ || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phidef))
+ return NULL_TREE;
+
+ /* PHIDEF must be defined by a NEGATE_EXPR inside the loop. */
+ def = SSA_NAME_DEF_STMT (phidef);
+ if (!is_gimple_assign (def)
+ || gimple_assign_rhs_code (def) != NEGATE_EXPR
+ || !flow_bb_inside_loop_p (loop, gimple_bb (def)))
+ return NULL_TREE;
+
+ op_arg = gimple_assign_rhs1 (def);
+
+ /* The operand must be a 2-arg PHI in the loop header. */
+ if (TREE_CODE (op_arg) != SSA_NAME
+ || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op_arg)
+ || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (op_arg)))
+ || gimple_bb (header_phi) != loop->header
+ || gimple_phi_num_args (header_phi) != 2)
+ return NULL_TREE;
+
+ /* Pattern: op_arg = PHI <phidef (latch), init (preheader)>. */
+ if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
+ return NULL_TREE;
+
+ init = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
+
+ /* Need a constant trip count to know the parity. */
+ if (!tree_fits_uhwi_p (niter))
+ return NULL_TREE;
+
+ tree type = TREE_TYPE (phidef);
+ unsigned HOST_WIDE_INT niter_num = tree_to_uhwi (niter);
+
+ /* Only integral recurrences are handled here. The caller already
+ restricts final value replacement to pointer and integral types, and
+ NEGATE_EXPR is not generated for pointers, so this is normally an
+ integral type; make the requirement explicit. */
+ if (!INTEGRAL_TYPE_P (type))
+ return NULL_TREE;
+
+ /* -INT_MIN overflows. */
+ if (TYPE_OVERFLOW_TRAPS (type) || TYPE_OVERFLOW_SANITIZED (type))
+ return NULL_TREE;
+
+ /* NITER is the number of latch executions, so the loop body (the
+ negation) runs NITER + 1 times. The final value depends on the
+ parity of NITER + 1:
+ NITER odd -> NITER + 1 even -> value unchanged
+ NITER even -> NITER + 1 odd -> value negated. */
+
+ /* Even number of negations: value is unchanged. */
+ if (niter_num & 1)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ " Idempotent NEGATE_EXPR: even count, value unchanged\n");
+ return init;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file,
+ " Idempotent NEGATE_EXPR: odd count, value negated\n");
+
+ return fold_build1 (NEGATE_EXPR, type, init);
+}
+
/* Try to compute the final value of PHIDEF when PHIDEF is the result of a
loop-header PHI.
@@ -3979,7 +4073,7 @@ final_value_replacement_loop (class loop *loop)
def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
&folded_casts);
- tree bitinv_def, bit_def, phi_latch_final_value;
+ tree bitinv_def, bit_def, negate_def, phi_latch_final_value;
unsigned HOST_WIDE_INT niter_num;
gphi *header_phi = TREE_CODE (phidef) == SSA_NAME
@@ -4001,6 +4095,13 @@ final_value_replacement_loop (class loop *loop)
phidef, niter)))
def = bitinv_def;
+ else if (integer_zerop (niter_desc.may_be_zero)
+ && (negate_def
+ = analyze_and_compute_negate_effect (loop,
+ phidef,
+ niter)))
+ def = negate_def;
+
/* Handle bitwise induction expression.
.i.e.
--
2.54.0
