[PATCH v1 1/1] tree-optimization/114502 - final value replacement for idempotent negation

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