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

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

> So we have (uint64_t)(uint32 + -1U) + 1 and using TYPE_SIGN (inner_type)
> produces (uint64_t)uint32 + -1U + 1.  This simply means that we cannot ignore
> overflow of the inner operation and for some reason your change
> to extract_range_from_binary_expr didn't catch this.  That is _8 + 4294967295
> overflows but we ignored that.

In this case the range of _8 was [1,1] so no overflow.
I think the problem is rather about the interpretation of the inner
constant. I tried discerning two cases now, a range split (i.e. when the
single range of a binop variable becomes an anti range or two ranges
after combining it with the binop's other range) and an overflow of the
range's min and max.
If the range didn't split, we can perform the simplification. If there
was a min and max overflow, we have to interpret the inner constant as
signed and perform a sign extension before converting it to the outer
type. Without overflow we can use TYPE_SIGN (inner_type).
Does this make sense?

Included the remarks and attached the new version.

Regards
 Robin

diff --git a/gcc/match.pd b/gcc/match.pd
index feaa4a1..19df142 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1195,6 +1195,81 @@ 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)
+	   (if (TREE_CODE (type) == INTEGER_TYPE
+		&& TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (@3)))
+	    (with
+	    {
+	      struct vr_binop_overflow ovf;
+	      tree cst = NULL_TREE;
+	      tree inner_type = TREE_TYPE (@3);
+	      value_range vr = VR_INITIALIZER;
+
+	      /* Convert combined constant to tree of outer type if
+		 there was no value range split in the original operation.  */
+	      if (TYPE_OVERFLOW_UNDEFINED (inner_type)
+		  || (extract_range_from_binary_expr (&vr, inner_op,
+		    inner_type, @0, @1, &ovf), !ovf.range_split))
+	      {
+		wide_int w1 = @1;
+		wide_int w2 = @2;
+
+		wide_int combined_cst;
+
+		/* Extend @1 to TYPE.  Perform sign extension if the range
+		   overflowed but did not split.  */
+		w1 = w1.from (w1, TYPE_PRECISION (type), ovf.ovf ? SIGNED :
+		    TYPE_SIGN (inner_type));
+
+		if (inner_op == MINUS_EXPR)
+		  w1 = wi::neg (w1);
+
+		if (outer_op == MINUS_EXPR)
+		  w2 = wi::neg (w2);
+
+		/* Combine in outer, larger type.  */
+		bool combine_ovf = true;
+		combined_cst = wi::add (w1, w2);
+
+		cst = wide_int_to_tree (type, combined_cst);
+	      }
+	    }
+	(if (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)
+      (if (TYPE_PRECISION (type) > TYPE_PRECISION (TREE_TYPE (@0))
+	   && TREE_CODE (TREE_TYPE (@0)) == INTEGER_TYPE
+	   && TREE_CODE (type) == INTEGER_TYPE)
+       /* Perform binary operation inside the cast if the constant fits
+	  and there is no overflow.  */
+       (with
+	{
+	  struct vr_binop_overflow ovf;
+
+	  int_fits_type_p (@2, TREE_TYPE (@0));
+	  tree cst_inner = fold_convert (TREE_TYPE (@0), @2);
+
+	  value_range vr = VR_INITIALIZER;
+	  extract_range_from_binary_expr (&vr, outer_op, TREE_TYPE (@0),
+					  @0, cst_inner, &ovf);
+	}
+	(if (!ovf.range_split)
+	 (convert (outer_op @0 { cst_inner; })))
+	))))
+#endif
+
   /* (A +- CST1) +- CST2 -> A + CST3  */
   (for outer_op (plus minus)
    (for inner_op (plus minus)
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..19b787b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-1.c
@@ -0,0 +1,60 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ccp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 11 "ccp1" } } */
+
+#include <limits.h>
+
+long foo(int a)
+{
+  return (long)(a - 2) + 1;
+}
+
+long bar(int a)
+{
+  return (long)(a + 3) - 1;
+}
+
+long baz(int a)
+{
+  return (long)(a - 1) + 2;
+}
+
+long baf(int a)
+{
+  return (long)(a + 1) - 2;
+}
+
+long bak(int a)
+{
+  return (long)(a + 1) + 3;
+}
+
+long bal(int a)
+{
+  return (long)(a - 7) - 4;
+}
+
+long bam(int a)
+{
+  return (long)(a - 1) - INT_MAX;
+}
+
+long bam2(int a)
+{
+  return (long)(a + 1) + INT_MAX;
+}
+
+long ban(int a)
+{
+  return (long)(a - 1) + INT_MIN;
+}
+
+long ban2(int a)
+{
+  return (long)(a + 1) - INT_MIN;
+}
+
+unsigned long baq(int a)
+{
+  return (unsigned long)(a + 1) - 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..8befc96
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-1.c
@@ -0,0 +1,51 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ccp1-details -fdump-tree-evrp-details -fdump-tree-vrp1-details" } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 1 "ccp1" } } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 1 "evrp" } } */
+/* { dg-final { scan-tree-dump-times "gimple_simplified to" 5 "vrp1" } } */
+
+#include <limits.h>
+
+unsigned long oof2(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a - 1) + 1;
+}
+
+unsigned long bap(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) + ULONG_MAX;
+}
+
+unsigned long bar3(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) - 5;
+}
+
+unsigned long bar4(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (unsigned long)(a + 1) - 6;
+}
+
+unsigned long baq(int a)
+{
+  return (unsigned long)(a - 2) + 1;
+}
+
+long baq3(unsigned int a)
+{
+  if (a > 3 && a < INT_MAX - 100)
+    return (long)(a - 1) + 1;
+}
+
+// should simplify (combined constant is 0 not (unsigned long)UINT_MAX + 1
+// VRP creates an anti-range for a
+unsigned long foo(short b)
+{
+  unsigned int a = b;
+  return (unsigned long)(a + UINT_MAX) + 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..fb6d3d9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-2.c
@@ -0,0 +1,32 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+#include <assert.h>
+#include <limits.h>
+
+unsigned int a = 3;
+int aa = 3;
+
+int main()
+{
+  volatile unsigned long b = (unsigned long)(UINT_MAX + 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);
+
+  volatile long h = (long)(aa + UINT_MAX) + 1;
+  assert (h == 3);
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 600634d..7b8714d 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -62,8 +62,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "alloc-pool.h"
 #include "domwalk.h"
 #include "tree-cfgcleanup.h"
-
-#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
+#include "tree-vrp.h"
 
 /* Allocation pools for tree-vrp allocations.  */
 static object_allocator<value_range> vrp_value_range_pool ("Tree VRP value ranges");
@@ -2214,7 +2213,8 @@ extract_range_from_multiplicative_op_1 (value_range *vr,
 static void
 extract_range_from_binary_expr_1 (value_range *vr,
 				  enum tree_code code, tree expr_type,
-				  value_range *vr0_, value_range *vr1_)
+				  value_range *vr0_, value_range *vr1_,
+				  struct vr_binop_overflow *ovf)
 {
   value_range vr0 = *vr0_, vr1 = *vr1_;
   value_range vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
@@ -2273,12 +2273,13 @@ extract_range_from_binary_expr_1 (value_range *vr,
   if (vr0.type == VR_ANTI_RANGE
       && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
     {
-      extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
+      extract_range_from_binary_expr_1 (vr, code, expr_type,
+					&vrtem0, vr1_, ovf);
       if (vrtem1.type != VR_UNDEFINED)
 	{
 	  value_range vrres = VR_INITIALIZER;
 	  extract_range_from_binary_expr_1 (&vrres, code, expr_type,
-					    &vrtem1, vr1_);
+					    &vrtem1, vr1_, ovf);
 	  vrp_meet (vr, &vrres);
 	}
       return;
@@ -2287,12 +2288,13 @@ extract_range_from_binary_expr_1 (value_range *vr,
   if (vr1.type == VR_ANTI_RANGE
       && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
     {
-      extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0);
+      extract_range_from_binary_expr_1 (vr, code, expr_type,
+					vr0_, &vrtem0, ovf);
       if (vrtem1.type != VR_UNDEFINED)
 	{
 	  value_range vrres = VR_INITIALIZER;
 	  extract_range_from_binary_expr_1 (&vrres, code, expr_type,
-					    vr0_, &vrtem1);
+					    vr0_, &vrtem1, ovf);
 	  vrp_meet (vr, &vrres);
 	}
       return;
@@ -2505,6 +2507,13 @@ extract_range_from_binary_expr_1 (value_range *vr,
 		max_ovf = 1;
 	    }
 
+	  if (ovf != NULL)
+	    {
+	      ovf->range_split = min_ovf != max_ovf;
+	      ovf->ovf = (min_ovf == 1 && max_ovf == 1)
+		|| (min_ovf == -1 && max_ovf == -1);
+	    }
+
 	  /* If we have overflow for the constant part and the resulting
 	     range will be symbolic, drop to VR_VARYING.  */
 	  if ((min_ovf && sym_min_op0 != sym_min_op1)
@@ -2847,7 +2856,7 @@ extract_range_from_binary_expr_1 (value_range *vr,
 	      saved_flag_wrapv = flag_wrapv;
 	      flag_wrapv = 1;
 	      extract_range_from_binary_expr_1 (vr, MULT_EXPR, expr_type,
-						&vr0, &vr1p);
+						&vr0, &vr1p, ovf);
 	      flag_wrapv = saved_flag_wrapv;
 	      return;
 	    }
@@ -3225,35 +3234,70 @@ extract_range_from_binary_expr_1 (value_range *vr,
     set_value_range (vr, type, min, max, NULL);
 }
 
+static void
+extract_range_from_binary_expr_1 (value_range *vr,
+				  enum tree_code code, tree expr_type,
+				  value_range *vr0_, value_range *vr1_)
+{
+  extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, vr1_,
+      NULL);
+}
+
 /* Extract range information from a binary expression OP0 CODE OP1 based on
    the ranges of each of its operands with resulting type EXPR_TYPE.
    The resulting range is stored in *VR.  */
 
-static void
+void
 extract_range_from_binary_expr (value_range *vr,
 				enum tree_code code,
-				tree expr_type, tree op0, tree op1)
+				tree expr_type, tree op0, tree op1,
+				struct vr_binop_overflow *ovf)
 {
   value_range vr0 = VR_INITIALIZER;
   value_range vr1 = VR_INITIALIZER;
+  /*
+  if (ovf != NULL)
+    {
+      ovf->range_split = true;
+      ovf->ovf = true;
+    }
+    */
 
   /* Get value ranges for each operand.  For constant operands, create
      a new value range with the operand to simplify processing.  */
   if (TREE_CODE (op0) == SSA_NAME)
-    vr0 = *(get_value_range (op0));
+    {
+      value_range *vtmp = get_value_range (op0);
+      if (ovf != NULL && vtmp == NULL)
+	{
+	  vr->type = VR_VARYING;
+	  return;
+	}
+      else
+	vr0 = *vtmp;
+    }
   else if (is_gimple_min_invariant (op0))
     set_value_range_to_value (&vr0, op0, NULL);
   else
     set_value_range_to_varying (&vr0);
 
   if (TREE_CODE (op1) == SSA_NAME)
-    vr1 = *(get_value_range (op1));
+    {
+      value_range *vtmp = get_value_range (op1);
+      if (ovf != NULL && vtmp == NULL)
+	{
+	  vr->type = VR_VARYING;
+	  return;
+	}
+      else
+	vr1 = *vtmp;
+    }
   else if (is_gimple_min_invariant (op1))
     set_value_range_to_value (&vr1, op1, NULL);
   else
     set_value_range_to_varying (&vr1);
 
-  extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
+  extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1, ovf);
 
   /* Try harder for PLUS and MINUS if the range of one operand is symbolic
      and based on the other operand, for example if it was deduced from a
@@ -3281,7 +3325,8 @@ extract_range_from_binary_expr (value_range *vr,
       else
 	set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
 
-      extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
+      extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1,
+					ovf);
     }
 
   if (vr->type == VR_VARYING
@@ -3305,10 +3350,19 @@ extract_range_from_binary_expr (value_range *vr,
       else
 	set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
 
-      extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
+      extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1,
+					ovf);
     }
 }
 
+static void
+extract_range_from_binary_expr (value_range *vr,
+				enum tree_code code,
+				tree expr_type, tree op0, tree op1)
+{
+  extract_range_from_binary_expr (vr, code, expr_type, op0, op1, NULL);
+}
+
 /* 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.  */
@@ -3714,14 +3768,32 @@ check_for_binary_op_overflow (enum tree_code subcode, tree type,
   value_range vr0 = VR_INITIALIZER;
   value_range vr1 = VR_INITIALIZER;
   if (TREE_CODE (op0) == SSA_NAME)
-    vr0 = *get_value_range (op0);
+    {
+      value_range *vrtmp = get_value_range (op0);
+      if (vrtmp != NULL)
+	vr0 = *vrtmp;
+      else
+	{
+	  *ovf = true;
+	return true;
+	}
+    }
   else if (TREE_CODE (op0) == INTEGER_CST)
     set_value_range_to_value (&vr0, op0, NULL);
   else
     set_value_range_to_varying (&vr0);
 
   if (TREE_CODE (op1) == SSA_NAME)
-    vr1 = *get_value_range (op1);
+    {
+      value_range *vrtmp = get_value_range (op1);
+      if (vrtmp != NULL)
+	vr1 = *vrtmp;
+      else
+	{
+	  *ovf = true;
+	  return true;
+	}
+    }
   else if (TREE_CODE (op1) == INTEGER_CST)
     set_value_range_to_value (&vr1, op1, NULL);
   else
@@ -10553,7 +10625,7 @@ identify_jump_threads (void)
       /* We're basically looking for a switch or any kind of conditional with
 	 integral or pointer type arguments.  Note the type of the second
 	 argument will be the same as the first argument, so no need to
-	 check it explicitly. 
+	 check it explicitly.
 
 	 We also handle the case where there are no statements in the
 	 block.  This come up with forwarder blocks that are not
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 5cea709..3ddffad 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.h
@@ -17,6 +17,9 @@ You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
+#ifndef GCC_TREE_VRP_H
+#define GCC_TREE_VRP_H
+
 /* Type of value ranges.  See value_range_d In tree-vrp.c for a
    description of these types.  */
 enum value_range_type { VR_UNDEFINED, VR_RANGE,
@@ -48,6 +51,21 @@ struct GTY(()) value_range
   bitmap equiv;
 };
 
+/* Overflow properties of a binop's value range.  */
+struct GTY(()) vr_binop_overflow
+{
+  /* True if both min_ovf and max_ovf occurred.  */
+  bool ovf;
+  /* True if the range split during range calculation i.e. either
+     min_ovf or max_ovf occurred  e.g. [0,1] + [UINT_MAX, UINT_MAX].  */
+  bool range_split;
+
+  vr_binop_overflow() :
+    ovf(true), range_split(true) {}
+};
+
+#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
+
 extern void vrp_intersect_ranges (value_range *vr0, value_range *vr1);
 extern void vrp_meet (value_range *vr0, const value_range *vr1);
 extern void dump_value_range (FILE *, const value_range *);
@@ -56,4 +74,9 @@ extern void extract_range_from_unary_expr (value_range *vr,
 					   tree type,
 					   value_range *vr0_,
 					   tree op0_type);
+extern void extract_range_from_binary_expr (value_range *vr,
+				enum tree_code code,
+				tree expr_type, tree op0, tree op1,
+				struct vr_binop_overflow *overflow);
 
+#endif /* GCC_TREE_VRP_H */

diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index fbe7e13..110587d 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -1065,13 +1065,15 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
 
       /* Replace real uses in the statement.  */
       did_replace |= replace_uses_in (stmt, get_value_fn);
+      if (did_replace)
+	gimple_set_modified (stmt, true);
 
       /* If we made a replacement, fold the statement.  */
-      if (did_replace)
+      if (fold_stmt (&i, follow_single_use_edges))
 	{
-	  fold_stmt (&i, follow_single_use_edges);
 	  stmt = gsi_stmt (i);
 	  gimple_set_modified (stmt, true);
+	  did_replace = true;
 	}
 
       /* Some statements may be simplified using propagator