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

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

Found some time to look into this again.

> Index: tree-ssa-propagate.c
> ===================================================================
> --- tree-ssa-propagate.c        (revision 240133)
> +++ tree-ssa-propagate.c        (working copy)
> @@ -1105,10 +1105,10 @@ substitute_and_fold_dom_walker::before_d
>        /* Replace real uses in the statement.  */
>        did_replace |= replace_uses_in (stmt, get_value_fn);
> 
> -      /* If we made a replacement, fold the statement.  */
> -      if (did_replace)
> +      /* Fold the statement.  */
> +      if (fold_stmt (&i, follow_single_use_edges))
>         {
> -         fold_stmt (&i, follow_single_use_edges);
> +         did_replace = true;
>           stmt = gsi_stmt (i);
>         }
> 
> this would need compile-time cost evaluation (and avoid the tree-vrp.c
> folding part
> of your patch).

This causes an ICE and bootstrap errors with newer revisions. I tested
my patch on r240691 where it still works. How can this be done properly now?

> OTOH given that you use this to decide whether you can use a combined constant
> that doesn't look necessary (if the constant is correct, that is) --
> what you need
> to make sure is that the final operation, (T)(A) +- CST, does not overflow
> if ! TYPE_OVERFLOW_WRAPS and there wasn't any overflow in the
> original operation.  I think that always holds, thus the combine_ovf check looks
> superfluous to me.

Removed the check and addressed the other remarks.

> So now we know that for (T)(X + CST1) + CST2, (T)CST1 + CST2
> does not overflow.  But we do not really care for that, we want to know
> whether (T)X + CST' might invoke undefined behavior when the original
> expression did not.  This involves range information on X.  I don't
> see how we ensure this here.

I guess I'm still missing an undefined behavior case. In which case can
(T)X + CST' trigger undefined behavior where the original statement did
not? I see the need for checking in the second pattern ((T)(X) + CST' ->
(T)(X + CST')), of course.

> But that's "easily fixable" by computing it in unsigned arithmetic, that is
> doing
> 
>   (long)(a + 2) + LONG_MAX -> (long)((unsigned long)a + (LONG_MAX + 2))

Does this also work if (unsigned long)a + (LONG_MAX + 2) does not fit
into [0,LONG_MAX]? IIRC (unsigned long)(LONG_MAX + 2) is
implementation-defined and not undefined so it should work?

Revised patch version attached. One thing I'm still not sure about is
the handling of sth. like (unsigned long)(a + UINT_MAX) + 1 for a = 0.
In the current patch version I always do a sign-extend of the first
constant (UINT_MAX here) which seems to cause no problems in the
testsuite and some custom tests still worked. Can UINT_MAX, -1 and
similar cases be disambiguated (and correctly converted to the outer
type) when done in unsigned arithmetic?

Thinking about the second pattern, on s390x it introduces more casts
than just using the first one (e.g. in cases where the value will be
sign-extended after the operation which wouldn't have happened when
performing the operation in the larger type. Can we catch this
with a cost function?

On a side note: Can/should VRP infer ranges assuming no undefined
behavior will take place when -fstrict-overflow is in use? I.e.
inferring ~[INT_MIN,INT_MIN] for (long)(a - 1)? Would this even make sense?

Regards
 Robin

diff --git a/gcc/match.pd b/gcc/match.pd
index ba7e013..3d3f5bb 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -1150,6 +1150,86 @@ 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
+	    {
+	      bool range_split = false;
+	      tree cst = NULL_TREE;
+	      tree inner_type = TREE_TYPE (@3);
+	      value_range vr = VR_INITIALIZER;
+
+	      if (TYPE_OVERFLOW_UNDEFINED (inner_type))
+		range_split = false;
+	      else
+		{
+		  /* Check the inner binop using VRP information.  */
+		  extract_range_from_binary_expr (&vr, inner_op,
+			  inner_type, @0, @1, &range_split);
+		}
+
+	      wide_int w1 = @1;
+	      wide_int w2 = @2;
+
+	      wide_int combined_cst;
+
+	      /* Sign-extend @1 to TYPE.  */
+	      w1 = w1.from (w1, TYPE_PRECISION (type), SIGNED);
+
+	      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, SIGNED, &combine_ovf);
+
+	      /* Convert combined constant to tree of outer type if
+		 there was no value range split in the original operation.  */
+	      if (!range_split)
+		{
+		  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
+	{
+	  tree cst_inner;
+	  bool range_split = true;
+
+	  wide_int cst = @2;
+	  cst_inner = wide_int_to_tree (TREE_TYPE (@0), cst);
+	  value_range vr = VR_INITIALIZER;
+	  extract_range_from_binary_expr (&vr, outer_op, TREE_TYPE (@0),
+					  @0, cst_inner, &range_split);
+	}
+	(if (!range_split)
+	 (convert (outer_op @0 { cst_inner; })))
+	))))
+#endif
+
   /* (A +- CST) +- CST -> A + CST  */
   (for outer_op (plus minus)
    (for inner_op (plus minus)
@@ -1163,6 +1243,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..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-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index 97cfde5..16b4a6b 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -1106,9 +1106,10 @@ substitute_and_fold_dom_walker::before_dom_children (basic_block bb)
       did_replace |= replace_uses_in (stmt, get_value_fn);
 
       /* 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);
+	  did_replace = true;
 	  stmt = gsi_stmt (i);
 	}
 
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 7a08be7..1140402 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");
@@ -2199,7 +2198,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_,
+				  bool *range_split)
 {
   value_range vr0 = *vr0_, vr1 = *vr1_;
   value_range vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
@@ -2258,12 +2258,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_, range_split);
       if (vrtem1.type != VR_UNDEFINED)
 	{
 	  value_range vrres = VR_INITIALIZER;
 	  extract_range_from_binary_expr_1 (&vrres, code, expr_type,
-					    &vrtem1, vr1_);
+					    &vrtem1, vr1_, range_split);
 	  vrp_meet (vr, &vrres);
 	}
       return;
@@ -2272,12 +2273,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, range_split);
       if (vrtem1.type != VR_UNDEFINED)
 	{
 	  value_range vrres = VR_INITIALIZER;
 	  extract_range_from_binary_expr_1 (&vrres, code, expr_type,
-					    vr0_, &vrtem1);
+					    vr0_, &vrtem1, range_split);
 	  vrp_meet (vr, &vrres);
 	}
       return;
@@ -2490,6 +2492,11 @@ extract_range_from_binary_expr_1 (value_range *vr,
 		max_ovf = 1;
 	    }
 
+	  if (range_split != NULL)
+	    {
+	      *range_split = wi::gt_p (wmin, wmax, TYPE_SIGN (expr_type));
+	    }
+
 	  /* 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)
@@ -2832,7 +2839,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, range_split);
 	      flag_wrapv = saved_flag_wrapv;
 	      return;
 	    }
@@ -3210,35 +3217,65 @@ 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,
+				bool *range_split)
 {
   value_range vr0 = VR_INITIALIZER;
   value_range vr1 = VR_INITIALIZER;
+  if (range_split != NULL)
+    *range_split = 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 (range_split != 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 (range_split != 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,
+				    range_split);
 
   /* 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
@@ -3266,7 +3303,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,
+					range_split);
     }
 
   if (vr->type == VR_VARYING
@@ -3290,10 +3328,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,
+					range_split);
     }
 }
 
+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.  */
@@ -3699,14 +3746,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
@@ -10497,7 +10562,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..793b584 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,8 @@ struct GTY(()) value_range
   bitmap equiv;
 };
 
+#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 +61,8 @@ 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,
+				bool *ovf);
+#endif /* GCC_TREE_VRP_H */