[PATCH 2/2] tree-scalar-evolution: Handle toggle recurrences

Recognize NEGATE_EXPR, BIT_NOT_EXPR and BIT_XOR_EXPR recurrences.
Fold constant iteration counts and use a conditional for symbolic counts.

Require may_be_zero to be false, since otherwise niter does not
necessarily give the latch count.  Keep trapping signed negations
unchanged.  This replaces the old invariant bit-operation helper;
idempotent AND and IOR updates are handled by the preceding patch.

gcc/ChangeLog:

	PR middle-end/124460
	PR middle-end/114502
	PR middle-end/112104
	PR middle-end/98909
	* tree-scalar-evolution.cc
	(analyze_and_compute_bitop_with_inv_effect): Remove.
	(compute_toggle_loop_value): New function.
	(final_value_replacement_loop): Use it.

gcc/testsuite/ChangeLog:

	PR middle-end/124460
	PR middle-end/114502
	PR middle-end/112104
	PR middle-end/98909
	* gcc.dg/tree-ssa/pr124460-4.c: New test.
	* gcc.dg/tree-ssa/pr124460-5.c: Likewise.
	* gcc.target/i386/pr105735-1.c: Adjust scan count.
	* gcc.target/i386/pr105735-3.c: Likewise.
	* gcc.target/i386/pr92080-12.c: Keep the XOR operand variant.
---
 gcc/testsuite/gcc.dg/tree-ssa/pr124460-4.c | 96 ++++++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr124460-5.c | 40 +++++++++
 gcc/testsuite/gcc.target/i386/pr105735-1.c |  2 +-
 gcc/testsuite/gcc.target/i386/pr105735-3.c |  2 +-
 gcc/testsuite/gcc.target/i386/pr92080-12.c | 12 +--
 gcc/tree-scalar-evolution.cc               | 91 +++++++-------------
 6 files changed, 174 insertions(+), 69 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr124460-4.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr124460-5.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr124460-4.c b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-4.c
new file mode 100644
index 00000000000..95cdd245a21
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-4.c
@@ -0,0 +1,96 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-details" } */
+
+int
+test_neg_odd (int x)
+{
+  for (int i = 0; i < 103; ++i)
+    x = -x;
+  return x;
+}
+
+int
+test_neg_even (int x)
+{
+  for (int i = 0; i < 104; ++i)
+    x = -x;
+  return x;
+}
+
+unsigned
+test_not_odd (unsigned x)
+{
+  for (int i = 0; i < 105; ++i)
+    x = ~x;
+  return x;
+}
+
+unsigned
+test_not_even (unsigned x)
+{
+  for (int i = 0; i < 106; ++i)
+    x = ~x;
+  return x;
+}
+
+int
+test_xor_odd (int x)
+{
+  for (int i = 0; i < 107; ++i)
+    x ^= 0xff;
+  return x;
+}
+
+int
+test_xor_even (int x)
+{
+  for (int i = 0; i < 108; ++i)
+    x ^= 0xff;
+  return x;
+}
+
+int
+test_neg_variable (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x = -x;
+  return x;
+}
+
+unsigned
+test_not_variable (unsigned x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x = ~x;
+  return x;
+}
+
+int
+test_xor_variable (int x, int n)
+{
+  for (int i = 0; i < n; ++i)
+    x ^= 0xff;
+  return x;
+}
+
+/* NITER is not exact when the latch can be skipped.  */
+int
+test_neg_may_be_zero (int x, int i, int n)
+{
+  do
+    {
+      x = -x;
+      ++i;
+    }
+  while (i < n);
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times {final value replacement} 9 "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: -x_[0-9]+\(D\)} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: ~x_[0-9]+\(D\)} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: x_[0-9]+\(D\) \^ 255} "sccp" } } */
+/* { dg-final { scan-tree-dump-times {(?n)with expr: x_[0-9]+\(D\)$} 3 "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: .* == 0 \? -x_[0-9]+\(D\) : x_[0-9]+\(D\)} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: .* == 0 \? ~x_[0-9]+\(D\) : x_[0-9]+\(D\)} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: .* == 0 \? x_[0-9]+\(D\) \^ 255 : x_[0-9]+\(D\)} "sccp" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr124460-5.c b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-5.c
new file mode 100644
index 00000000000..548b5b51623
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr124460-5.c
@@ -0,0 +1,40 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -ftrapv -fdump-tree-sccp-details" } */
+
+int
+test_neg_trapv (int n)
+{
+  for (int i = 0; i < 1024; ++i)
+    n = -n;
+  return n;
+}
+
+unsigned
+test_neg_unsigned (unsigned u)
+{
+  for (int i = 0; i < 1024; ++i)
+    u = -u;
+  return u;
+}
+
+int
+test_not_trapv (int b)
+{
+  for (int i = 0; i < 1024; ++i)
+    b = ~b;
+  return b;
+}
+
+int
+test_xor_trapv (int x)
+{
+  for (int i = 0; i < 1024; ++i)
+    x ^= 0xff;
+  return x;
+}
+
+/* { dg-final { scan-tree-dump-times {final value replacement} 3 "sccp" } } */
+/* { dg-final { scan-tree-dump-not {with expr: n_[0-9]+\(D\)} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: u_[0-9]+\(D\)} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: b_[0-9]+\(D\)} "sccp" } } */
+/* { dg-final { scan-tree-dump {with expr: x_[0-9]+\(D\)} "sccp" } } */
diff --git a/gcc/testsuite/gcc.target/i386/pr105735-1.c b/gcc/testsuite/gcc.target/i386/pr105735-1.c
index 69de6b2911a..4d9ca085127 100644
--- a/gcc/testsuite/gcc.target/i386/pr105735-1.c
+++ b/gcc/testsuite/gcc.target/i386/pr105735-1.c
@@ -1,6 +1,6 @@
 /* { dg-do compile } */
 /* { dg-options "-O1 -fdump-tree-sccp-details" } */
-/* { dg-final { scan-tree-dump-times {final value replacement} 8 "sccp" } } */
+/* { dg-final { scan-tree-dump-times {final value replacement} 9 "sccp" } } */
 
 unsigned int
 __attribute__((noipa))
diff --git a/gcc/testsuite/gcc.target/i386/pr105735-3.c b/gcc/testsuite/gcc.target/i386/pr105735-3.c
index 9e268a1a997..a3280ba6860 100644
--- a/gcc/testsuite/gcc.target/i386/pr105735-3.c
+++ b/gcc/testsuite/gcc.target/i386/pr105735-3.c
@@ -1,6 +1,6 @@
 /* { dg-do compile } */
 /* { dg-options "-O1 -fdump-tree-sccp-details" } */
-/* { dg-final { scan-tree-dump-times {final value replacement} 8 "sccp" } } */
+/* { dg-final { scan-tree-dump-times {final value replacement} 9 "sccp" } } */
 
 unsigned int
 __attribute__((noipa))
diff --git a/gcc/testsuite/gcc.target/i386/pr92080-12.c b/gcc/testsuite/gcc.target/i386/pr92080-12.c
index cb09eb2f0a8..97f092604c4 100644
--- a/gcc/testsuite/gcc.target/i386/pr92080-12.c
+++ b/gcc/testsuite/gcc.target/i386/pr92080-12.c
@@ -2,15 +2,17 @@
 /* { dg-additional-options "-O3 -mno-mmx -march=icelake-server" } */
 /* { dg-final { scan-assembler-times "vpbroadcastb" 1 } } */
 
+/* Keep the XOR operand loop variant so SCCP leaves vector code to CSE.  */
+
 signed char a;
 signed char f (int i, int j)
 {
   signed char c;
   while (i != 0)
-  {
-    a ^= j;
-    ++c;
-    ++i;
-  }
+    {
+      a ^= j + i;
+      ++c;
+      ++i;
+    }
   return c;
 }
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index 11fa70a162f..9200866d3a4 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -3865,66 +3865,40 @@ compute_idempotent_loop_value (class loop *loop, tree phidef)
   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; */
-extern bool gimple_bitop_with_inv_p (tree, tree *, tree (*)(tree));
-
-/* Return the inductive expression of bitop with invariant if possible,
-   otherwise returns DEF.  */
+/* Return the effect of a repeated toggle update, if recognized.  */
 static tree
-analyze_and_compute_bitop_with_inv_effect (class loop* loop, tree phidef,
-					   tree niter)
+compute_toggle_loop_value (class loop *loop, tree phidef, tree niter)
 {
-  tree match_op[2],inv;
-  tree type = TREE_TYPE (phidef);
-  gphi* header_phi = NULL;
-  enum tree_code code;
-  /* match thing like op0 (match[0]), op1 (match[1]), phidef (PHIDEF)
-
-    op1 =  PHI <phidef, inv>
-    phidef = op0 & op1
-    if op0 is an invariant, it could change to
-    phidef = op0 & inv.  */
-  gimple *def;
-  def = SSA_NAME_DEF_STMT (phidef);
-  if (!(is_gimple_assign (def)
-      && ((code = gimple_assign_rhs_code (def)), true)
-      && (code == BIT_AND_EXPR || code == BIT_IOR_EXPR
-	  || code == BIT_XOR_EXPR)))
+  gimple *def = SSA_NAME_DEF_STMT (phidef);
+  if (!is_gimple_assign (def))
     return NULL_TREE;
 
-  match_op[0] = gimple_assign_rhs1 (def);
-  match_op[1] = gimple_assign_rhs2 (def);
-
-  if (expr_invariant_in_loop_p (loop, match_op[1]))
-    std::swap (match_op[0], match_op[1]);
-
-  if (TREE_CODE (match_op[1]) != SSA_NAME
-      || !expr_invariant_in_loop_p (loop, match_op[0])
-      || !(header_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (match_op[1])))
-      || gimple_bb (header_phi) != loop->header
-      || gimple_phi_num_args (header_phi) != 2)
+  enum tree_code code = gimple_assign_rhs_code (def);
+  if (code != NEGATE_EXPR && code != BIT_NOT_EXPR && code != BIT_XOR_EXPR)
     return NULL_TREE;
 
-  if (PHI_ARG_DEF_FROM_EDGE (header_phi, loop_latch_edge (loop)) != phidef)
+  tree type = TREE_TYPE (phidef);
+  if (code == NEGATE_EXPR && TYPE_OVERFLOW_TRAPS (type))
     return NULL_TREE;
 
-  enum tree_code code1
-    = gimple_assign_rhs_code (def);
+  tree op0 = gimple_assign_rhs1 (def);
+  tree op1 = (code == BIT_XOR_EXPR) ? gimple_assign_rhs2 (def) : NULL_TREE;
 
-  if (code1 == BIT_XOR_EXPR)
-    {
-       if (!tree_fits_uhwi_p (niter))
-	return NULL_TREE;
-       unsigned HOST_WIDE_INT niter_num;
-       niter_num = tree_to_uhwi (niter);
-       if (niter_num % 2 != 0)
-	match_op[0] =  build_zero_cst (type);
-    }
+  tree initial;
+  tree toggled = build_loop_update (loop, phidef, code, op0, op1, &initial);
+  if (!toggled)
+    return NULL_TREE;
 
-  inv = PHI_ARG_DEF_FROM_EDGE (header_phi, loop_preheader_edge (loop));
-  return fold_build2 (code1, type, inv, match_op[0]);
+  /* NITER counts latch executions, so the body runs NITER + 1 times.  */
+  if (tree_fits_uhwi_p (niter))
+    return (tree_to_uhwi (niter) & 1) ? initial : toggled;
+
+  tree niter_type = TREE_TYPE (niter);
+  tree even = fold_build2 (EQ_EXPR, boolean_type_node,
+			   fold_build2 (BIT_AND_EXPR, niter_type, niter,
+					build_one_cst (niter_type)),
+			   build_zero_cst (niter_type));
+  return fold_build3 (COND_EXPR, type, even, toggled, initial);
 }
 
 /* Try to compute the final value of PHIDEF when PHIDEF is the result of a
@@ -4054,23 +4028,16 @@ final_value_replacement_loop (class loop *loop)
       if (def != chrec_dont_know)
 	def = compute_overall_effect_of_inner_loop (ex_loop, def);
 
-      /* Handle bitop with invariant induction expression.
-
-	.i.e
-	for (int i =0 ;i < 32; i++)
-	  tmp &= bit2;
-	if bit2 is an invariant in loop which could simple to
-	tmp &= bit2.  */
-      else if ((loop_value
-		= analyze_and_compute_bitop_with_inv_effect (loop,
-							     phidef, niter)))
-	def = loop_value;
-
       /* Handle simple recurrences not represented by SCEV.  */
       else if ((loop_value
 		= compute_idempotent_loop_value (loop, phidef)))
 	def = loop_value;
 
+      else if (integer_zerop (niter_desc.may_be_zero)
+	       && (loop_value
+		   = compute_toggle_loop_value (loop, phidef, niter)))
+	def = loop_value;
+
       /* Handle bitwise induction expression.
 
 	 .i.e.
-- 
2.34.1