This patch recognizes and optimizes loops that repeatedly apply abs()
to the same variable, exploiting the idempotence property of ABS_EXPR:
abs(abs(x)) == abs(x). After the first iteration, the value no longer
changes, so the loop's final value can be replaced with abs(init).
The optimization is guarded by may_be_zero to ensure the loop executes
at least once, preventing speculation of abs() on zero-iteration paths.
It is restricted to integral types and includes overflow guards for
-ftrapv and -fsanitize=signed-integer-overflow.
gcc/ChangeLog:
* tree-scalar-evolution.cc (analyze_and_compute_abs_effect): New
helper function to recognize and optimize idempotent ABS_EXPR
loop patterns.
(final_value_replacement_loop): Call analyze_and_compute_abs_effect
when may_be_zero is known false.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/scev-abs-1.c: New test for basic abs() loops.
* gcc.dg/tree-ssa/scev-abs-2.c: New test for edge cases.
* gcc.dg/tree-ssa/scev-abs-3.c: New runtime test.
* gcc.dg/tree-ssa/scev-abs-4.c: New negative test for may_be_zero.
---
gcc/testsuite/gcc.dg/tree-ssa/scev-abs-1.c | 29 ++++++++
gcc/testsuite/gcc.dg/tree-ssa/scev-abs-2.c | 53 ++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/scev-abs-3.c | 56 +++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/scev-abs-4.c | 20 ++++++
gcc/tree-scalar-evolution.cc | 81 +++++++++++++++++++++-
5 files changed, 238 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-abs-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-abs-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-abs-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/scev-abs-4.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-1.c
new file mode 100644
index 00000000000..d92d3cc89f5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-1.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+/* Test abs () idempotent loop optimization on loops proven to run >= 1 time.
+ abs (abs (x)) == abs (x), so the loop collapses to r = abs (r_initial).
+ Constant trip counts keep may_be_zero == 0 so the guarded transform fires.
*/
+
+int
+test_abs_basic (int r)
+{
+ for (int i = 0; i < 100; i++)
+ r = __builtin_abs (r);
+ return r;
+}
+
+int
+test_abs_while (int r)
+{
+ int i = 0;
+ while (i < 100)
+ {
+ r = __builtin_abs (r);
+ i++;
+ }
+ return r;
+}
+
+/* The transform fires once per function (2 functions). */
+/* { dg-final { scan-tree-dump-times "Optimizing idempotent ABS_EXPR
operation" 2 "sccp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-2.c
new file mode 100644
index 00000000000..508ef0b30ce
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-2.c
@@ -0,0 +1,53 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+/* Edge cases for abs () idempotent loop optimization, using constant trip
+ counts so each loop is provably entered (may_be_zero == 0). */
+
+int
+test_abs_conditional (int r, int cond)
+{
+ if (cond)
+ {
+ for (int i = 0; i < 100; i++)
+ r = __builtin_abs (r);
+ }
+ return r;
+}
+
+int
+test_abs_nested (int r)
+{
+ for (int j = 0; j < 100; j++)
+ for (int i = 0; i < 100; i++)
+ r = __builtin_abs (r);
+ return r;
+}
+
+int
+test_abs_multiple (int r1, int r2)
+{
+ for (int i = 0; i < 100; i++)
+ {
+ r1 = __builtin_abs (r1);
+ r2 = __builtin_abs (r2);
+ }
+ return r1 + r2;
+}
+
+int
+test_abs_do_while (int r)
+{
+ int i = 0;
+ do
+ {
+ r = __builtin_abs (r);
+ i++;
+ }
+ while (i < 100);
+ return r;
+}
+
+/* Optimizations: conditional (1) + nested inner loop (1) + multiple (2)
+ + do-while (1, provably >= 1 iteration with a constant bound) = 5. */
+/* { dg-final { scan-tree-dump-times "Optimizing idempotent ABS_EXPR
operation" 5 "sccp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-3.c
new file mode 100644
index 00000000000..b56fd543828
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-3.c
@@ -0,0 +1,56 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+#include <limits.h>
+
+/* noipa keeps the body intact and forces real calls, so the loop transform
+ is exercised inside the function rather than folded at the call site. */
+
+/* Parametric trip count: exercises the zero-iteration path. */
+int __attribute__((noipa))
+test_abs_runtime (int r, int n)
+{
+ for (int i = 0; i < n; i++)
+ r = __builtin_abs (r);
+ return r;
+}
+
+/* Constant positive trip count: checks the optimized closed form gives
+ correct runtime results. */
+int __attribute__((noipa))
+abs_fixed (int r)
+{
+ for (int i = 0; i < 100; i++)
+ r = __builtin_abs (r);
+ return r;
+}
+
+int
+main (void)
+{
+ /* Zero-iteration path must return the initial value unchanged. */
+ if (test_abs_runtime (-5, 0) != -5)
+ __builtin_abort ();
+ if (test_abs_runtime (INT_MIN, 0) != INT_MIN)
+ __builtin_abort ();
+ if (test_abs_runtime (42, 0) != 42)
+ __builtin_abort ();
+
+ /* Positive-iteration paths (parametric). */
+ if (test_abs_runtime (-42, 1) != 42)
+ __builtin_abort ();
+ if (test_abs_runtime (-42, 100) != 42)
+ __builtin_abort ();
+ if (test_abs_runtime (-1, 5) != 1)
+ __builtin_abort ();
+ if (test_abs_runtime (0, 100) != 0)
+ __builtin_abort ();
+
+ /* Fixed positive-trip path (optimized closed form). */
+ if (abs_fixed (-9) != 9)
+ __builtin_abort ();
+ if (abs_fixed (9) != 9)
+ __builtin_abort ();
+
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-4.c
new file mode 100644
index 00000000000..3dcc6d55400
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/scev-abs-4.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-ch -fdump-tree-sccp-details" } */
+
+/* The trip count may be zero (n <= 0) and nothing proves otherwise, so the
+ loop may run zero times. Replacing the final value with abs (init) would
+ speculate abs () on the zero-iteration path (e.g. n == 0 must return the
+ initial value unchanged), so the transform must be declined here.
+
+ -fno-tree-ch keeps the loop from being guarded/rotated before sccp, so its
+ may_be_zero stays non-trivial and the guard is exercised. */
+
+int
+abs_may_be_zero (int r, int n)
+{
+ for (int i = 0; i < n; i++)
+ r = __builtin_abs (r);
+ return r;
+}
+
+/* { dg-final { scan-tree-dump-not "Optimizing idempotent ABS_EXPR operation"
"sccp" } } */
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index 279ff46474e..ad1d0bfdf78 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3854,6 +3854,79 @@ 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 idempotent ABS_EXPR loop pattern.
+
+ Detects loops of the form:
+ for (i = 0; i < n; i++)
+ r = abs (r);
+
+ which exploit the idempotence of ABS_EXPR (abs (abs (x)) == abs (x)):
+ after the first iteration the value no longer changes.
+
+ The caller must guarantee the loop executes at least once (niter's
+ may_be_zero is known false); given that, the exact exit value is simply
+ abs (r_init), and abs is never speculated onto a zero-iteration path.
+
+ Return the replacement expression, or NULL_TREE when the pattern does
+ not apply. */
+
+static tree
+analyze_and_compute_abs_effect (class loop *loop, tree phidef)
+{
+ 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
+ || virtual_operand_p (phidef)
+ || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (phidef))
+ return NULL_TREE;
+
+ /* Only integer abs is handled */
+ tree type = TREE_TYPE (phidef);
+ if (!INTEGRAL_TYPE_P (type))
+ return NULL_TREE;
+
+ /* abs (INT_MIN) overflows. Do not introduce an abs that could trap
+ (-ftrapv) or be reported by the signed-overflow sanitizer on a value
+ the transformed program would compute unconditionally. */
+ if (TYPE_OVERFLOW_TRAPS (type) || TYPE_OVERFLOW_SANITIZED (type))
+ return NULL_TREE;
+
+ /* PHIDEF must be defined by an ABS_EXPR inside the loop. */
+ def = SSA_NAME_DEF_STMT (phidef);
+ if (!is_gimple_assign (def)
+ || gimple_assign_rhs_code (def) != ABS_EXPR
+ || !flow_bb_inside_loop_p (loop, gimple_bb (def)))
+ return NULL_TREE;
+
+ op_arg = gimple_assign_rhs1 (def);
+
+ /* The operand should be defined by a PHI node 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;
+
+ /* Verify that the PHI's latch argument is phidef (creating the loop).
+ 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));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Optimizing idempotent ABS_EXPR operation\n");
+
+ /* Loop runs >= 1 time (guaranteed by caller), so the exit value is
+ exactly abs (init). */
+ return fold_build1 (ABS_EXPR, type, init);
+}
+
/* Try to compute the final value of PHIDEF when PHIDEF is the result of a
loop-header PHI.
@@ -3971,7 +4044,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, abs_def, phi_latch_final_value;
unsigned HOST_WIDE_INT niter_num;
gphi *header_phi = TREE_CODE (phidef) == SSA_NAME
@@ -3993,6 +4066,12 @@ final_value_replacement_loop (class loop *loop)
phidef, niter)))
def = bitinv_def;
+ /* Handle idempotent abs () recurrence. */
+ else if (integer_zerop (niter_desc.may_be_zero)
+ && (abs_def = analyze_and_compute_abs_effect (loop,
+ phidef)))
+ def = abs_def;
+
/* Handle bitwise induction expression.
.i.e.
--
2.34.1
