Re: [PATCH] Tree-level fix for PR 69526

[Robin Dapp <rdapp at linux dot vnet dot ibm dot com>]

Ping.

diff --git a/gcc/gimple-match-head.c b/gcc/gimple-match-head.c
index 2beadbc..d66fcb1 100644
--- a/gcc/gimple-match-head.c
+++ b/gcc/gimple-match-head.c
@@ -39,6 +39,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "internal-fn.h"
 #include "case-cfn-macros.h"
 #include "gimplify.h"
+#include "tree-vrp.h"
 
 
 /* Forward declarations of the private auto-generated matchers.
diff --git a/gcc/match.pd b/gcc/match.pd
index b24bfb4..f54b734 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1119,6 +1119,113 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
    (minus @0 (minus @0 @1))
    @1)
 
+  /* ((T)(A +- CST)) +- CST -> (T)(A) +- CST)  */
+#if GIMPLE
+   (for outer_op (plus minus)
+     (for inner_op (plus minus)
+       (simplify
+	 (outer_op (convert (inner_op@3 @0 INTEGER_CST@1)) INTEGER_CST@2)
+	   (with
+	    {
+	   /* If the inner operation is wrapped inside a conversion, we have to
+	      check it overflows/underflows and can only then perform the
+	      simplification, i.e. add the second constant to the first
+	      (wrapped) and convert afterwards.  This fixes
+	      https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69526 */
+	    bool inner_ovf = false;
+
+	    bool combine_ovf = true;
+	    tree cst = NULL_TREE;
+	    bool combine_constants = false;
+	    bool types_ok = false;
+
+	    tree inner_type = TREE_TYPE (@3);
+	    /* Check overflow in wrapped binop? */
+	    bool check_inner_ovf = !TYPE_OVERFLOW_UNDEFINED (inner_type);
+	    /* Check overflow when combining constants? */
+	    bool check_combine_ovf = TYPE_OVERFLOW_UNDEFINED (type);
+
+	    signop s1 = TYPE_SIGN (type);
+
+	    if (TYPE_PRECISION (type) >= TYPE_PRECISION (inner_type))
+	      {
+		types_ok = true;
+
+		/* Check if the inner binop does not overflow i.e. we have VRP
+		   information and can prove prove it.  */
+		if (check_inner_ovf)
+		  inner_ovf = binop_overflow (inner_op, @0, @1, inner_type);
+		else
+		  inner_ovf = false;
+
+		wide_int w1 = @1;
+		wide_int w2 = @2;
+
+		wide_int combined_cst;
+
+		/* Convert to TYPE keeping possible signedness even when
+		   dealing with unsigned types. */
+		wide_int v1;
+		v1 = v1.from (w1, w2.get_precision(), tree_int_cst_sign_bit
+			      (@1) ? SIGNED : UNSIGNED);
+
+		if (inner_op == MINUS_EXPR)
+		  w1 = wi::neg (w1);
+
+		if (outer_op == MINUS_EXPR)
+		  w2 = wi::neg (w2);
+
+		/* Combine in outer, larger type */
+		combined_cst = wi::add (v1, w2, TYPE_SIGN (type), &combine_ovf);
+
+		/* The combined constant is ok if its type does not exhibit
+		   undefined overflow or there was no overflow when
+		   combining.  */
+		bool combined_cst_ok = !check_combine_ovf || !combine_ovf;
+		if (!inner_ovf && combined_cst_ok)
+		  {
+		    /* convert to tree of outer type */
+		    cst = wide_int_to_tree (type, combined_cst);
+		    combine_constants = true;
+		  }
+	      }
+	  }
+	(if (types_ok && combine_constants && cst)
+	 (outer_op (convert { @0; }) { cst; }))
+	))))
+#endif
+
+  /* ((T)(A)) +- CST -> (T)(A +- CST)  */
+#if GIMPLE
+   (for outer_op (plus minus)
+    (simplify
+     (outer_op (convert @0) INTEGER_CST@2)
+     /* Perform binary operation inside the cast if the constant fits
+	and there is no overflow.  */
+       (with
+	{
+	  bool simplify = false;
+
+	  wide_int cst = @2;
+	  tree inner_type = TREE_TYPE (@0);
+	  tree cst_inner = wide_int_to_tree (inner_type, cst);
+	  bool inner_ovf = true;
+
+	  if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type)
+	      || TREE_CODE (inner_type) != INTEGER_TYPE)
+	    simplify = false;
+	  else
+	  {
+	    inner_ovf = binop_overflow (outer_op, @0, cst_inner, inner_type);
+	    if (!inner_ovf)
+	      simplify = true;
+	  }
+	}
+	(if (simplify && @0)
+	 (convert (outer_op @0 (convert { @2; }))))
+	)))
+#endif
+
   /* (A +- CST) +- CST -> A + CST  */
   (for outer_op (plus minus)
    (for inner_op (plus minus)
@@ -1132,6 +1239,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
       (if (cst && !TREE_OVERFLOW (cst))
        (inner_op @0 { cst; } ))))))
 
+
   /* (CST - A) +- CST -> CST - A  */
   (for outer_op (plus minus)
    (simplify
diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-1.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-1.c
new file mode 100644
index 0000000..0afe99a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-1.c
@@ -0,0 +1,76 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-forwprop1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 11 "forwprop1" } } */
+
+#include <limits.h>
+
+// should simplify, ignore possible signed overflow in (a - 2) and combine
+// constants
+long foo(int a)
+{
+  return (long)(a - 2) + 1;
+}
+
+// should simplify
+long bar(int a)
+{
+  return (long)(a + 3) - 1;
+}
+
+// should simplify with combined constant in outer type
+long baz(int a)
+{
+  return (long)(a - 1) + 2;
+}
+
+// should simplify
+long baf(int a)
+{
+  return (long)(a + 1) - 2;
+}
+
+// should simplify (same as above)
+long bak(int a)
+{
+  return (long)(a + 1) + 3;
+}
+
+// should simplify (same)
+long bal(int a)
+{
+  return (long)(a - 7) - 4;
+}
+
+// should simplify with combined constant in inner type, no overflow in
+// combined constant in inner type (1 - INT_MAX) although it looks like it :)
+long bam(int a)
+{
+  return (long)(a - 1) - INT_MAX;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long bam2(int a)
+{
+  return (long)(a + 1) + INT_MAX;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long ban(int a)
+{
+  return (long)(a - 1) + INT_MIN;
+}
+
+// should simplify with combined constant in outer type, overflow in
+// combined constant in inner type
+long ban2(int a)
+{
+  return (long)(a + 1) - INT_MIN;
+}
+
+// should simplify, assumes no inner overflow
+unsigned long baq(int a)
+{
+  return (unsigned long)(a + 1) - 1;
+}
diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-2.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-2.c
new file mode 100644
index 0000000..9b166f6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-2.c
@@ -0,0 +1,26 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-forwprop1-details -fdump-tree-vrp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 0 "forwprop1" } } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 0 "vrp1" } } */
+
+#include <limits.h>
+#include <assert.h>
+
+// should not simplify, 2 + LONG_MAX overflows
+long bao(int a)
+{
+  return (long)(a + 2) + LONG_MAX;
+}
+
+// should not simplify
+long bar(int a)
+{
+  return (long)(a - 2) - LONG_MAX;
+}
+
+// should not simplify although at first looks like (long)(a - 1) + 1 on
+// tree level, but a is promoted to long
+long bas(int a)
+{
+  return (long)(a + UINT_MAX) + 1;
+}
diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-1.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-1.c
new file mode 100644
index 0000000..fb0463d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-1.c
@@ -0,0 +1,48 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-forwprop1-details -fdump-tree-vrp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 1 "forwprop1" } } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 5 "vrp1" } } */
+
+#include <limits.h>
+
+// should simplify (same as above with VRP)
+unsigned long oof2(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a - 1) + 1;
+}
+
+// same
+unsigned long bap(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) + ULONG_MAX;
+}
+
+// should simplify
+unsigned long bar3(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) - 5;
+}
+
+// should simplify in outer type as we cannot prove non-overflow
+unsigned long bar4(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) - 6;
+}
+
+// should simplify
+unsigned long baq(int a)
+{
+  return (unsigned long)(a - 2) + 1;
+}
+
+// should simplify
+long baq3(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (long)(a - 1) + 1;
+}
+
diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-2.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-2.c
new file mode 100644
index 0000000..3843b6d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-2.c
@@ -0,0 +1,29 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+#include <assert.h>
+#include <limits.h>
+
+unsigned int a = 3;
+unsigned int aa = UINT_MAX;
+
+int main()
+{
+  volatile unsigned long b = (unsigned long)(aa + 1) - 1;
+  assert (b == 18446744073709551615ul);
+
+  volatile unsigned long c = (unsigned long)(a - 4) + 1;
+  assert (c == 4294967296);
+
+  volatile unsigned long d = (unsigned long)(a + UINT_MAX - 4) + 2;
+  assert (d == 4294967296);
+
+  volatile unsigned long e = (unsigned long)(a - UINT_MAX) + UINT_MAX;
+  assert (e == 4294967299);
+
+  volatile unsigned long f = (unsigned long)(a + UINT_MAX) - UINT_MAX;
+  assert (f == 18446744069414584323ul);
+
+  volatile long g = (long)(a - 4) + 1;
+  assert (g == 4294967296);
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 4333d60..f9bf2d4 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3231,6 +3231,109 @@ extract_range_from_binary_expr (value_range *vr,
     }
 }
 
+/* Check if the binary operation overflows.  */
+bool binop_overflow (enum tree_code op, tree t1, tree t2, tree type)
+{
+  if (t1 == NULL_TREE || t2 == NULL_TREE || type == NULL_TREE)
+    return true;
+
+  if (TREE_CODE (type) != INTEGER_TYPE)
+    return true;
+
+  if (TREE_CODE (t1) != SSA_NAME)
+    return true;
+
+  if (op != PLUS_EXPR && op != MINUS_EXPR)
+    return true;
+
+  wide_int min1;
+  wide_int max1;
+  signop st1 = TYPE_SIGN (TREE_TYPE (t1));
+
+  if (TREE_CODE (t1) != INTEGER_CST)
+    {
+      enum value_range_type vrtype1 = get_range_info (t1, &min1, &max1);
+
+      if (!vrtype1 || (vrtype1 != VR_RANGE && vrtype1 != VR_ANTI_RANGE))
+	return true;
+
+      if (vrtype1 == VR_ANTI_RANGE)
+	{
+	  bool ovf;
+	  wide_int tmpmin = wi::add (min1, 1, st1, &ovf);
+	  if (st1 == SIGNED && ovf)
+	    return true;
+	  wide_int tmpmax = wi::sub (max1, 1, st1, &ovf);
+	  if (st1 == SIGNED && ovf)
+	    return true;
+	  min1 = tmpmin;
+	  max1 = tmpmax;
+	}
+    }
+  else
+    {
+      min1 = t1;
+      max1 = t1;
+    }
+
+  wide_int min2;
+  wide_int max2;
+  signop st2 = TYPE_SIGN (TREE_TYPE (t2));
+
+  if (TREE_CODE (t2) != INTEGER_CST)
+    {
+      enum value_range_type vrtype2 = get_range_info (t2, &min2, &max2);
+
+      if (!vrtype2 || (vrtype2 != VR_RANGE && vrtype2 != VR_ANTI_RANGE))
+	return true;
+
+      if (vrtype2 == VR_ANTI_RANGE)
+	{
+	  bool ovf;
+	  wide_int tmpmin = wi::add (min2, 1, st2, &ovf);
+	  if (st2 == SIGNED && ovf)
+	    return true;
+	  wide_int tmpmax = wi::sub (max2, 1, st2, &ovf);
+	  if (st2 == SIGNED && ovf)
+	    return true;
+	  min2 = tmpmin;
+	  max2 = tmpmax;
+	}
+    }
+  else
+    {
+      min2 = t2;
+      max2 = t2;
+    }
+
+  wide_int wmin, wmax;
+
+  bool ovf;
+  signop sgn = TYPE_SIGN (TREE_TYPE (t1)) == SIGNED
+    || TYPE_SIGN (TREE_TYPE (t2)) == SIGNED ? SIGNED : UNSIGNED;
+  if (op == MINUS_EXPR)
+    {
+      wmin = wi::sub (min1, min2, sgn, &ovf);
+      if (sgn == SIGNED && (ovf || wi::gt_p (wmin, min1, sgn)))
+	return true;
+      wmax = wi::sub (max1, max2, sgn, &ovf);
+      if (sgn == SIGNED && (ovf || wi::gt_p (wmax, max1, sgn)))
+	return true;
+    }
+  else
+    {
+      wmin = wi::add (min1, min2, sgn, &ovf);
+      if (sgn == SIGNED && (ovf || wi::lt_p (wmin, min1, sgn)))
+	return true;
+      wmax = wi::add (max1, max2, sgn, &ovf);
+      if (sgn == SIGNED && (ovf || wi::lt_p (wmax, max1, sgn)))
+	return true;
+    }
+
+  return wi::gt_p (wmin, wmax, TYPE_SIGN (TREE_TYPE (t1)));
+}
+
+
 /* Extract range information from a unary operation CODE based on
    the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE.
    The resulting range is stored in *VR.  */
@@ -8906,6 +9009,37 @@ simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
   return true;
 }
 
+/* Simplify ((type) (b +- CST1)) + CST2 to (type) b + (CST1 + CST2)
+   if (b +- CST1) does not underflow.  */
+
+static bool
+simplify_plus_or_minus_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
+{
+  enum tree_code code = gimple_assign_rhs_code (stmt);
+  tree op0 = gimple_assign_rhs1 (stmt);
+  tree op1 = gimple_assign_rhs2 (stmt);
+
+  if ((code == PLUS_EXPR || code == MINUS_EXPR) &&
+      op0 != NULL && op1 != NULL)
+    {
+      gimple *stmt1 = SSA_NAME_DEF_STMT (op0);
+      if (gassign *def = dyn_cast <gassign *> (stmt1))
+	{
+	  if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def))
+	      && TREE_CODE (op1) == INTEGER_CST)
+	    {
+	      /* Only mark the stmt as updated here, so fold_stmt in
+	         tree-ssa-propagate will call the matching pattern in
+		 match.pd.  */
+	      update_stmt (gsi_stmt (*gsi));
+	      return true;
+	    }
+	}
+    }
+
+  return false;
+}
+
 /* Simplify a division or modulo operator to a right shift or
    bitwise and if the first operand is unsigned or is greater
    than zero and the second operand is an exact power of two.
@@ -9905,6 +10039,12 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
 	  return simplify_min_or_max_using_ranges (stmt);
 	  break;
 
+	case MINUS_EXPR:
+	case PLUS_EXPR:
+	  if (TREE_CODE (rhs1) == SSA_NAME)
+	    return simplify_plus_or_minus_using_ranges (gsi, stmt);
+	  break;
+
 	default:
 	  break;
 	}
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
new file mode 100644
index 0000000..5a867bc
--- /dev/null
+++ b/gcc/tree-vrp.h
@@ -0,0 +1,2 @@
+extern bool
+binop_overflow (enum tree_code op, tree t1, tree t2, tree type);