[PATCH 1/2] tree-scalar-evolution: Handle idempotent recurrences [PR124460]

SCEV does not represent recurrences such as repeated MIN_EXPR or
BIT_AND_EXPR updates.  Recognize MIN_EXPR, MAX_EXPR, BIT_AND_EXPR,
BIT_IOR_EXPR and ABS_EXPR updates with a loop-invariant second operand.
After any positive number of iterations their value is the operation
applied once to the initial value.

gcc/ChangeLog:

	PR middle-end/124460
	* tree-scalar-evolution.cc (loop_phi_for_update): New function.
	(build_loop_update): Likewise.
	(compute_idempotent_loop_value): Likewise.
	(final_value_replacement_loop): Use it.

gcc/testsuite/ChangeLog:

	PR middle-end/124460
	* gcc.dg/tree-ssa/pr124460-1.c: New test.
	* gcc.dg/tree-ssa/pr124460-2.c: Likewise.
	* gcc.dg/tree-ssa/pr124460-3.c: Likewise.
---
 gcc/testsuite/gcc.dg/tree-ssa/pr124460-1.c | 40 ++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr124460-2.c | 41 ++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr124460-3.c | 22 +++++++
 gcc/tree-scalar-evolution.cc               | 76 +++++++++++++++++++++-
 4 files changed, 176 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr124460-1.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr124460-2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr124460-3.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr124460-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-1.c
new file mode 100644
index 00000000000..24d0075ae86
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-1.c
@@ -0,0 +1,40 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+int
+test_min_zero (int f, int n)
+{
+  for (int i = 0; i < n; ++i)
+    f = f < 0 ? f : 0;
+  return f;
+}
+
+int
+test_max_100 (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x = x > 100 ? x : 100;
+  return x;
+}
+
+int
+test_max_50 (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x = x < 50 ? 50 : x;
+  return x;
+}
+
+int
+test_min_neg10 (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x = x > -10 ? -10 : x;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times {final value replacement} 4 "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: MIN_EXPR <f_[0-9]+\(D\), 0>} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: MAX_EXPR <x_[0-9]+\(D\), 100>} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: MAX_EXPR <x_[0-9]+\(D\), 50>} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: MIN_EXPR <x_[0-9]+\(D\), -10>} "sccp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr124460-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-2.c
new file mode 100644
index 00000000000..263b2e4c788
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-2.c
@@ -0,0 +1,41 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+int
+test_and_mask (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x &= 0xff;
+  return x;
+}
+
+int
+test_or_flags (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x |= 3;
+  return x;
+}
+
+unsigned long
+test_and_mask64 (unsigned long x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x &= 0xffffffff00000000UL;
+  return x;
+}
+
+unsigned
+test_or_bit (unsigned x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x |= 1U << 15;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times {final value replacement} 4 "sccp" { target lp64 } } } */
+/* { dg-final { scan-tree-dump-times {final value replacement} 3 "sccp" { target ilp32 } } } */
+/* { dg-final { scan-tree-dump {with expr: x_[0-9]+\(D\) & 255} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: x_[0-9]+\(D\) \| 3} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: x_[0-9]+\(D\) & 18446744069414584320} "sccp" { target lp64 } } } */
+/* { dg-final { scan-tree-dump {with expr: x_[0-9]+\(D\) \| 32768} "sccp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr124460-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-3.c
new file mode 100644
index 00000000000..692570eb047
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-3.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+int
+test_abs (int f, int n)
+{
+  for (int i = 0; i < n; ++i)
+    f = f < 0 ? -f : f;
+  return f;
+}
+
+int
+test_abs_alt (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x = x >= 0 ? x : -x;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times {final value replacement} 2 "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: ABS_EXPR <f_[0-9]+\(D\)>} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: ABS_EXPR <x_[0-9]+\(D\)>} "sccp" } } */
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index cd99cbe86ce..11fa70a162f 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3800,6 +3800,71 @@ enum bit_op_kind
   return fold_build2 (code1, type, inv, wide_int_to_tree (type, bits));
 }
 
+/* Return the header PHI for an update whose latch value is PHIDEF.  */
+static gphi *
+loop_phi_for_update (class loop *loop, tree phidef, tree op)
+{
+  if (TREE_CODE (op) != SSA_NAME)
+    return NULL;
+
+  gphi *phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (op));
+  if (phi
+      && gimple_bb (phi) == loop->header
+      && gimple_phi_num_args (phi) == 2
+      && PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)) == phidef)
+    return phi;
+
+  return NULL;
+}
+
+/* Rebuild CODE with the initial value of the recurrence that produces
+   PHIDEF.  OP1 is null for unary operations.  */
+static tree
+build_loop_update (class loop *loop, tree phidef, enum tree_code code,
+		   tree op0, tree op1, tree *init)
+{
+  gphi *phi = loop_phi_for_update (loop, phidef, op0);
+  tree invariant = op1;
+
+  if (!phi && op1)
+    {
+      phi = loop_phi_for_update (loop, phidef, op1);
+      invariant = op0;
+    }
+
+  if (!phi
+      || (invariant && !expr_invariant_in_loop_p (loop, invariant)))
+    return NULL_TREE;
+
+  tree initial = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+  if (init)
+    *init = initial;
+  if (!invariant)
+    return fold_build1 (code, TREE_TYPE (phidef), initial);
+
+  return fold_build2 (code, TREE_TYPE (phidef), initial, invariant);
+}
+
+/* Return the effect of a repeated idempotent update, if recognized.  */
+static tree
+compute_idempotent_loop_value (class loop *loop, tree phidef)
+{
+  gimple *def = SSA_NAME_DEF_STMT (phidef);
+  if (!is_gimple_assign (def))
+    return NULL_TREE;
+
+  enum tree_code code = gimple_assign_rhs_code (def);
+  if (code != MIN_EXPR && code != MAX_EXPR
+      && code != BIT_AND_EXPR && code != BIT_IOR_EXPR
+      && code != ABS_EXPR)
+    return NULL_TREE;
+
+  tree op0 = gimple_assign_rhs1 (def);
+  tree op1 = (code == ABS_EXPR) ? NULL_TREE : gimple_assign_rhs2 (def);
+
+  return build_loop_update (loop, phidef, code, op0, op1, NULL);
+}
+
 /* Match.pd function to match bitop with invariant expression
   .i.e.
   tmp_7 = _0 & _1; */
@@ -3979,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 loop_value, bit_def, phi_latch_final_value;
       unsigned HOST_WIDE_INT niter_num;
 
       gphi *header_phi = TREE_CODE (phidef) == SSA_NAME
@@ -3996,10 +4061,15 @@ final_value_replacement_loop (class loop *loop)
 	  tmp &= bit2;
 	if bit2 is an invariant in loop which could simple to
 	tmp &= bit2.  */
-      else if ((bitinv_def
+      else if ((loop_value
 		= analyze_and_compute_bitop_with_inv_effect (loop,
 							     phidef, niter)))
-	def = bitinv_def;
+	def = loop_value;
+
+      /* Handle simple recurrences not represented by SCEV.  */
+      else if ((loop_value
+		= compute_idempotent_loop_value (loop, phidef)))
+	def = loop_value;
 
       /* Handle bitwise induction expression.
 
-- 
2.34.1