[PATCH 5/5] reassoc: Rewrite signed plus/mult trees.

From: Robin Dapp <[email protected]>

With the wrappers in place, it's easy to add overflow handling for the
signed/plus rewriting.  This patch checks for overflow when adding or
multiplying the multiplicative factors using wi::overflow_type and tries
to prove factor * op overflow through ranges.  If we encounter an overflow, we
cancel the descent and don't rewrite.  Otherwise we can safely continue.

	PR tree-optimization/122209

gcc/ChangeLog:

	* tree-ssa-reassoc.cc (struct mult_factor): Handle overflows
	in plus/mul.
	(struct plus_mult_tree_state): Add overflow flag.
	(linearize_plus_mult_tree): Handle overflow.
	(rewrite_plus_mult_tree): Cancel on overflow.
	(reassociate_bb): Allow overflow for plus/mult rewrite.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/reassoc-52.c: Remove xfail.
	* gcc.dg/tree-ssa/reassoc-56.c: Likewise.
	* gcc.dg/tree-ssa/reassoc-58.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c |   4 +-
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c |  30 ++++
 gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c |  10 ++
 gcc/tree-ssa-reassoc.cc                    | 157 +++++++++++++++++----
 4 files changed, 172 insertions(+), 29 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
index 5a194a8c9dd..37a779fb0ab 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-52.c
@@ -45,5 +45,5 @@ baz (char fs)
 /* { dg-final { scan-tree-dump-times "\\* 14;" 1 "optimized" } } */
 /* { dg-final { scan-tree-dump-times "\\* 26;" 1 "optimized" } } */
 /* { dg-final { scan-tree-dump-times "\\* 5;" 1 "optimized" } } */
-/* { dg-final { scan-tree-dump-times "\\* 6;" 1 "optimized" { xfail *-*-* } } } */
-/* { dg-final { scan-tree-dump-times "\\* 80;" 1 "optimized" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-times "\\* 6;" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\* 80;" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
new file mode 100644
index 00000000000..65eafcaf026
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-58.c
@@ -0,0 +1,30 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O2 -fdump-tree-reassoc-details -fdump-tree-optimized" } */
+
+int
+foo (int t)
+{
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+  t += 3 + 3 * t;
+  t &= 0xFFF;
+
+  return t;
+}
+
+/* { dg-final { scan-tree-dump "4095" "optimized" } } */
+/* { dg-final { scan-tree-dump-times "Rewriting plus/mult" 8 "reassoc1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c
new file mode 100644
index 00000000000..804bcf12ce9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-59.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-O2 -fdump-tree-reassoc-details -fdump-tree-optimized" } */
+
+int
+foo (int t)
+{
+  return t + 0x3fffffff + 0x3fffffff + t;
+}
+
+/* { dg-final { scan-tree-dump-times "cannot prove no overflow" 2 "reassoc1" } } */
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index 54a7be64e54..c99cb953f0c 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -1916,7 +1916,7 @@ struct mult_factor
 	return real_equal (&fcst, &dconst0);
     }
 
-  void mul (tree other)
+  bool mul (tree other)
     {
       tree other_type = TREE_TYPE (other);
       gcc_checking_assert ((!is_float
@@ -1929,24 +1929,19 @@ struct mult_factor
 	other = uniform_vector_p (other);
 
       if (!is_float)
-	cst = wi::mul (cst, wi::to_wide (other));
+	{
+	  wi::overflow_type ovf;
+	  cst = wi::mul (cst, wi::to_wide (other), TYPE_SIGN (type), &ovf);
+	  if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+	    return false;
+	}
       else
 	real_arithmetic (&fcst, MULT_EXPR, &fcst,
 			 TREE_REAL_CST_PTR (other));
+      return true;
     }
 
-  void mul (mult_factor &other)
-    {
-      gcc_checking_assert (is_float == other.is_float);
-      gcc_checking_assert (is_vector == other.is_vector);
-      if (!is_float)
-	cst = wi::mul (cst, other.cst);
-      else
-	real_arithmetic (&fcst, MULT_EXPR, &fcst,
-			 &other.fcst);
-    }
-
-  void plus (tree other)
+  bool plus (tree other)
     {
       tree other_type = TREE_TYPE (other);
       gcc_checking_assert ((!is_float
@@ -1959,29 +1954,47 @@ struct mult_factor
 	other = uniform_vector_p (other);
 
       if (!is_float)
-	cst = wi::add (cst, wi::to_wide (other));
+	{
+	  wi::overflow_type ovf;
+	  cst = wi::add (cst, wi::to_wide (other), TYPE_SIGN (type), &ovf);
+	  if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+	    return false;
+	}
       else
 	real_arithmetic (&fcst, PLUS_EXPR, &fcst,
 			 TREE_REAL_CST_PTR (other));
+      return true;
     }
 
-  void plus (mult_factor &other)
+  bool plus (mult_factor &other)
     {
       gcc_checking_assert (is_float == other.is_float);
       gcc_checking_assert (is_vector == other.is_vector);
       if (!is_float)
-	cst = wi::add (cst, other.cst);
+	{
+	  wi::overflow_type ovf;
+	  cst = wi::add (cst, other.cst, TYPE_SIGN (type), &ovf);
+	  if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+	    return false;
+	}
       else
 	real_arithmetic (&fcst, PLUS_EXPR, &fcst,
 			 &other.fcst);
+      return true;
     }
 
-  void neg ()
+  bool neg ()
     {
       if (!is_float)
-	cst = wi::neg (cst);
+	{
+	  wi::overflow_type ovf;
+	  cst = wi::neg (cst, &ovf);
+	  if (!TYPE_OVERFLOW_WRAPS (type) && ovf != wi::OVF_NONE)
+	    return false;
+	}
       else
 	fcst = real_value_negate (&fcst);
+      return true;
     }
 
   bool is_one ()
@@ -2072,6 +2085,9 @@ struct plus_mult_tree_state
      be considered not worthwhile according to costing.  */
   bool changed;
 
+  /* True if we introduced overflow.  */
+  bool overflow;
+
   /* Operands of the cst/plus/mult sequence in program order.  */
   auto_vec<tree> ops;
   /* Maps SSA names to their multiplicative factors.  */
@@ -2089,6 +2105,7 @@ struct plus_mult_tree_state
       maybe_expensive_constants_before (0),
       maybe_expensive_constants_after (0),
       changed (false),
+      overflow (false),
       cst (build_zero_cst (type)) {}
 };
 
@@ -2115,8 +2132,18 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
     {
       if (constant_maybe_expensive (op))
 	state->maybe_expensive_constants_before++;
-      factor.mul (op);
-      state->cst.plus (factor);
+      bool ok = factor.mul (op);
+      if (!ok)
+	{
+	  state->overflow = true;
+	  return;
+	}
+      ok = state->cst.plus (factor);
+      if (!ok)
+	{
+	  state->overflow = true;
+	  return;
+	}
       if (!state->cst.is_zero () || !factor.is_one ())
 	state->changed = true;
       return;
@@ -2128,7 +2155,7 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
       && has_single_use (op)
       && (((INTEGRAL_TYPE_P (TREE_TYPE (op))
 	    || VECTOR_INTEGER_TYPE_P (TREE_TYPE (op)))
-	   && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op)))
+	   /*&& TYPE_OVERFLOW_WRAPS (TREE_TYPE (op))*/)
 	  || FLOAT_TYPE_P (TREE_TYPE (op))))
     {
       gimple *stmt = SSA_NAME_DEF_STMT (op);
@@ -2154,7 +2181,12 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
 		{
 		  state->mults_before++;
 		  state->visited.safe_push (stmt);
-		  factor.mul (rhs2);
+		  bool ok = factor.mul (rhs2);
+		  if (!ok)
+		    {
+		      state->overflow = true;
+		      return;
+		    }
 		  linearize_plus_mult_tree (rhs1, factor, state, loop);
 		  return;
 		}
@@ -2169,7 +2201,12 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
 	      else if (opcode == NEGATE_EXPR)
 		{
 		  state->visited.safe_push (stmt);
-		  factor.neg ();
+		  bool ok = factor.neg ();
+		  if (!ok)
+		    {
+		      state->overflow = true;
+		      return;
+		    }
 		  linearize_plus_mult_tree (rhs1, factor, state, loop);
 		  return;
 		}
@@ -2182,7 +2219,14 @@ linearize_plus_mult_tree (tree op, mult_factor factor,
   bool existed;
   mult_factor &slot = state->op_factor_map.get_or_insert (op, &existed);
   if (existed)
-    slot.plus (factor);
+    {
+      bool ok = slot.plus (factor);
+      if (!ok)
+	{
+	  state->overflow = true;
+	  return;
+	}
+    }
   else
     slot = factor;
 
@@ -2355,6 +2399,44 @@ cost_plus_mult_tree (plus_mult_tree_state *state)
   return worthwhile;
 }
 
+/* Return true if the tree in rewritten form as described by STATE can
+   overflow or false otherwise.
+   This relies on the ranges of the linearized ops.  We check the overflow
+    mult_factor * OP
+   as well as the partial sum up to OP.  */
+
+static bool
+plus_mult_tree_overflow_p (struct plus_mult_tree_state *state)
+{
+  wide_int sum_lo = state->cst.cst;
+  wide_int sum_hi = state->cst.cst;
+  for (tree op : state->ops)
+    {
+      mult_factor &factor = *state->op_factor_map.get (op);
+      if (factor.is_zero ())
+	continue;
+      int_range_max r;
+      get_range_query (cfun)->range_of_expr (r, op);
+
+      wi::overflow_type ovf1, ovf2;
+      wide_int lo1 = wi::mul (r.lower_bound (), factor.cst, TYPE_SIGN
+			      (TREE_TYPE (op)), &ovf1);
+      wide_int hi1 = wi::mul (r.upper_bound (), factor.cst, TYPE_SIGN
+			      (TREE_TYPE (op)), &ovf2);
+      if (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE)
+	return true;
+
+      sum_hi = wi::add (sum_hi, wi::smax (hi1, lo1),
+			TYPE_SIGN (TREE_TYPE (op)), &ovf2);
+      sum_lo = wi::add (sum_lo, wi::smin (lo1, hi1),
+			TYPE_SIGN (TREE_TYPE (op)), &ovf1);
+      if (ovf1 != wi::OVF_NONE || ovf2 != wi::OVF_NONE)
+	return true;
+    }
+
+  return false;
+}
+
 /* Try to rewrite/expand a tree consisting of additions, multiplications
    by constants, and negates like
      a + 3 * (a + b + 1) + 2
@@ -2389,8 +2471,30 @@ rewrite_plus_mult_tree (gimple *stmt)
   if (!state.changed)
     return false;
 
+  if (state.overflow)
+    return false;
+
   gather_plus_mult_tree_stats (&state);
 
+  /* Check for overflow.  */
+  if ((INTEGRAL_TYPE_P (type)
+       || VECTOR_INTEGER_TYPE_P (type))
+      && TYPE_OVERFLOW_UNDEFINED (type))
+    {
+      if ((INTEGRAL_TYPE_P (type)
+	   && plus_mult_tree_overflow_p (&state))
+	  || VECTOR_INTEGER_TYPE_P (type))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Not rewriting plus/mult tree at ");
+	      print_generic_expr (dump_file, lhs);
+	      fprintf (dump_file,  ": cannot prove no overflow.\n");
+	    }
+	  return false;
+	}
+    }
+
   /* Check if it's worthwhile to follow through with the expansion.  */
   bool worthwhile = cost_plus_mult_tree (&state);
 
@@ -7716,8 +7820,7 @@ reassociate_bb (basic_block bb)
 		      || (FLOAT_TYPE_P (TREE_TYPE (lhs))
 			  && !HONOR_NANS (TREE_TYPE (lhs))
 			  && !HONOR_SIGNED_ZEROS (TREE_TYPE (lhs))))
-		  && has_single_use (lhs)
-		  && !type_can_overflow)
+		  && has_single_use (lhs))
 		{
 		  if (rewrite_plus_mult_tree (stmt))
 		    {
-- 
2.54.0