[PATCH 2/5] reassoc: Initial overflow support.

From: Robin Dapp <[email protected]>

This patch tries to start small and introduces simple signed-type
handling to reassoc.  It adds an tree_overflow_p function that checks a
PLUS_EXPR tree for overflow via global ranges, summing up the minima and
maxima of the operands.  This needs to happen before linearization.

If we confirmed there is no overflow, reassoc's optimizations can run
uninhibited.  There are currently just two exceptions, plus-mult rewriting
and undistribute_ops_list, which builds additional chains for each operand.

gcc/ChangeLog:

	* tree-ssa-reassoc.cc (tree_overflow_p): New function.
	(reassociate_bb): Use new function.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/reassoc-signed-1.c: New test.
---
 .../gcc.dg/tree-ssa/reassoc-signed-1.c        |  24 ++++
 gcc/tree-ssa-reassoc.cc                       | 119 ++++++++++++++++--
 2 files changed, 134 insertions(+), 9 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c
new file mode 100644
index 00000000000..bf0bab189b9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-signed-1.c
@@ -0,0 +1,24 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int foo (int a, int b, int c, int d)
+{
+  a &= 0xff;
+  b &= 0xff;
+  c &= 0xff;
+  d &= 0xff;
+  return a + b + a + c + a + d + b;
+}
+
+int bar (char a, char b, char c, char d)
+{
+  return a + b + a + c + a + d + b;
+}
+
+int baz (int a, int b, int c, int d)
+{
+  return a + b + a + c + a + d + b;
+}
+
+/* { dg-final { scan-tree-dump-times " \\* 3" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\* 2" 2 "optimized" } } */
diff --git a/gcc/tree-ssa-reassoc.cc b/gcc/tree-ssa-reassoc.cc
index f570c0164f4..211e8778d6c 100644
--- a/gcc/tree-ssa-reassoc.cc
+++ b/gcc/tree-ssa-reassoc.cc
@@ -55,6 +55,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-math-opts.h"
 #include "gimple-range.h"
 #include "internal-fn.h"
+#include "value-range.h"
 
 /*  This is a simple global reassociation pass.  It is, in part, based
     on the LLVM pass of the same name (They do some things more/less
@@ -7326,6 +7327,89 @@ rank_ops_for_fma (vec<operand_entry *> *ops)
     }
   return mult_num;
 }
+
+/* Check if we can linearize the expression tree starting at STMT.
+   FORNOW only support PLUS_EXPR is supported.  We sum all minima and
+   maxima of the operands in the tree in widest_int and check whether the
+   result exceeds the operands's type.  If so, or if we don't have range
+   information for any operand,  conservatively return true.  Otherwise
+   return false.  */
+
+static bool
+tree_overflow_p (tree_code code, gimple *stmt, struct loop *loop)
+{
+  if (!is_gimple_assign (stmt))
+    return true;
+
+  tree lhs = gimple_assign_lhs (stmt);
+  tree type = TREE_TYPE (lhs);
+
+  if (VECTOR_TYPE_P (type))
+    return true;
+
+  if (code != PLUS_EXPR)
+    return true;
+
+  signop sgn = TYPE_SIGN (type);
+  widest_int sum_hi = 0, sum_lo = 0;
+  widest_int zero = 0;
+
+  auto_vec <gimple *> worklist;
+  worklist.safe_push (stmt);
+  int_range_max range;
+
+  while (!worklist.is_empty ())
+    {
+      gimple *cur = worklist.pop ();
+
+      /* We always have two ops, because we only descend into PLUS_EXPRs.  */
+      for (int i = 1; i <= 2; i++)
+	{
+	  tree op = gimple_op (cur, i);
+
+	  /* Just like linearize_expr_tree, descend if the statement is
+	     plus-reassociable and doesn't throw.  */
+	  if (TREE_CODE (op) == SSA_NAME)
+	    {
+	      gimple *def_op = SSA_NAME_DEF_STMT (op);
+	      if (is_reassociable_op (def_op, PLUS_EXPR, loop)
+		  && !stmt_could_throw_p (cfun, def_op))
+		{
+		  worklist.safe_push (def_op);
+		  continue;
+		}
+	    }
+
+	  /* Add a leave's range to the global sums.
+	     We clamp the ranges to zero so we can catch e.g.
+	      (INT_MAX + 1) - 1
+	     whose total sum would be INT_MAX but (INT_MAX + 1) still
+	     overflows.  */
+	  if (get_range_query (cfun)->range_of_expr (range, op)
+	      && !range.undefined_p ())
+	    {
+	      sum_hi = wi::add (sum_hi,
+				wi::smax (widest_int::from
+					  (range.upper_bound (), sgn),
+					  zero));
+	      sum_lo = wi::add (sum_lo,
+				wi::smin (widest_int::from
+					  (range.lower_bound (), sgn),
+					  zero));
+	    }
+	  else
+	    return true;
+	}
+    }
+
+  bool hi_ok = wi::le_p
+    (sum_hi, widest_int::from (wi::max_value (type), sgn), sgn);
+  bool lo_ok = wi::ge_p
+    (sum_lo, widest_int::from (wi::min_value (type), sgn), sgn);
+  return !hi_ok || !lo_ok;
+}
+
+
 /* Reassociate expressions in basic block BB and its post-dominator as
    children.
 
@@ -7385,15 +7469,22 @@ reassociate_bb (basic_block bb)
 	  lhs = gimple_assign_lhs (stmt);
 	  rhs1 = gimple_assign_rhs1 (stmt);
 	  rhs2 = gimple_assign_rhs2 (stmt);
+	  tree type = TREE_TYPE (rhs1);
+
+	  bool type_can_overflow = INTEGRAL_TYPE_P (type)
+	    && TYPE_OVERFLOW_UNDEFINED (type);
+
+	  bool operation_can_overflow = rhs_code != BIT_IOR_EXPR
+	    && rhs_code != BIT_AND_EXPR
+	    && rhs_code != BIT_XOR_EXPR
+	    && rhs_code != MIN_EXPR
+	    && rhs_code != MAX_EXPR;
 
 	  /* For non-bit or min/max operations we can't associate
 	     all types.  Verify that here.  */
-	  if ((rhs_code != BIT_IOR_EXPR
-	       && rhs_code != BIT_AND_EXPR
-	       && rhs_code != BIT_XOR_EXPR
-	       && rhs_code != MIN_EXPR
-	       && rhs_code != MAX_EXPR
-	       && !can_reassociate_type_p (TREE_TYPE (lhs)))
+	  if ((operation_can_overflow
+	       && !can_reassociate_type_p (TREE_TYPE (lhs))
+	       && !type_can_overflow)
 	      || !can_reassociate_op_p (rhs1)
 	      || !can_reassociate_op_p (rhs2))
 	    continue;
@@ -7416,7 +7507,8 @@ reassociate_bb (basic_block bb)
 		 do so.  While at it, remove 0-factor elements.  */
 	      if ((rhs_code == PLUS_EXPR || rhs_code == MULT_EXPR)
 		  && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
-		  && has_single_use (lhs))
+		  && has_single_use (lhs)
+		  && !type_can_overflow)
 		{
 		  if (rewrite_plus_mult_tree (stmt))
 		    {
@@ -7430,13 +7522,22 @@ reassociate_bb (basic_block bb)
 		    }
 		}
 
+	      /* Check overflow before linearization as that can already
+		 introduce undefined behavior by rewriting.  */
+	      if (type_can_overflow
+		  && operation_can_overflow
+		  && tree_overflow_p (rhs_code, stmt,
+				      loop_containing_stmt (stmt)))
+		continue;
+
 	      linearize_expr_tree (&ops, stmt, true, true);
 	      int orig_len = ops.length ();
 	      ops.qsort (sort_by_operand_rank);
 	      optimize_ops_list (rhs_code, &ops);
 
-	      if (undistribute_ops_list (rhs_code, &ops,
-					 loop_containing_stmt (stmt)))
+	      if (!type_can_overflow
+		  && undistribute_ops_list (rhs_code, &ops,
+					    loop_containing_stmt (stmt)))
 		{
 		  ops.qsort (sort_by_operand_rank);
 		  optimize_ops_list (rhs_code, &ops);
-- 
2.54.0