VRP: x+1 and -x cannot be INT_MIN

VRP: x+1 and -x cannot be INT_MIN

[Marc Glisse]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 921 bytes --]

Hello,

with undefined overflow, just because we know nothing about one of the 
arguments of an addition doesn't mean we can't say something about the 
result. We could constrain more the cases where we replace VR_VARYING with 
a full VR_RANGE, but I didn't want to duplicate too much logic.

The 20040409 testcases were introduced to test an RTL transformation, so I 
don't feel too bad adding -fwrapv to work around the undefined overflows 
they exhibit.

Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

2017-11-13  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	* tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR,
 	MINUS_EXPR]: Use a full range for VR_VARYING.

gcc/testsuite/
 	PR testsuite/82951
 	* gcc.c-torture/execute/20040409-1.c: Use -fwrapv.
 	* gcc.c-torture/execute/20040409-2.c: Likewise.
 	* gcc.c-torture/execute/20040409-3.c: Likewise.
 	* gcc.dg/tree-ssa/vrp118.c: New file.

-- 
Marc Glisse

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: TEXT/x-diff; name=vrp.patch, Size: 3491 bytes --]

Index: gcc/testsuite/gcc.c-torture/execute/20040409-1.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-1.c	(revision 254629)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-1.c	(working copy)
@@ -1,10 +1,12 @@
+/* { dg-options "-fwrapv" } */
+
 #include <limits.h>
 
 extern void abort ();
 
 int test1(int x)
 {
   return x ^ INT_MIN;
 }
 
 unsigned int test1u(unsigned int x)
Index: gcc/testsuite/gcc.c-torture/execute/20040409-2.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-2.c	(revision 254629)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-2.c	(working copy)
@@ -1,10 +1,12 @@
+/* { dg-options "-fwrapv" } */
+
 #include <limits.h>
 
 extern void abort ();
 
 int test1(int x)
 {
   return (x ^ INT_MIN) ^ 0x1234;
 }
 
 unsigned int test1u(unsigned int x)
Index: gcc/testsuite/gcc.c-torture/execute/20040409-3.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-3.c	(revision 254629)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-3.c	(working copy)
@@ -1,10 +1,12 @@
+/* { dg-options "-fwrapv" } */
+
 #include <limits.h>
 
 extern void abort ();
 
 int test1(int x)
 {
   return ~(x ^ INT_MIN);
 }
 
 unsigned int test1u(unsigned int x)
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp118.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp118.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp118.c	(working copy)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void eliminate_me();
+void f(int x,int y){
+    if (y < 4)
+      __builtin_unreachable();
+    x += y;
+    if (x == -__INT_MAX__)
+      eliminate_me ();
+}
+
+/* { dg-final { scan-tree-dump-not "eliminate_me" "optimized" } } */
Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c	(revision 254629)
+++ gcc/tree-vrp.c	(working copy)
@@ -2086,20 +2086,38 @@ extract_range_from_binary_expr_1 (value_
       else
 	set_value_range_to_varying (vr);
 
       return;
     }
 
   /* For integer ranges, apply the operation to each end of the
      range and see what we end up with.  */
   if (code == PLUS_EXPR || code == MINUS_EXPR)
     {
+      /* If one argument is varying, we can sometimes still deduce a
+	 range for the output: any + [3, +INF] is in [MIN+3, +INF].  */
+      if (TYPE_OVERFLOW_UNDEFINED (expr_type))
+	{
+	  if(vr0.type == VR_VARYING && vr1.type == VR_RANGE)
+	    {
+	      vr0.type = type = VR_RANGE;
+	      vr0.min = vrp_val_min (expr_type);
+	      vr0.max = vrp_val_max (expr_type);
+	    }
+	  if(vr1.type == VR_VARYING && vr0.type == VR_RANGE)
+	    {
+	      vr1.type = VR_RANGE;
+	      vr1.min = vrp_val_min (expr_type);
+	      vr1.max = vrp_val_max (expr_type);
+	    }
+	}
+
       const bool minus_p = (code == MINUS_EXPR);
       tree min_op0 = vr0.min;
       tree min_op1 = minus_p ? vr1.max : vr1.min;
       tree max_op0 = vr0.max;
       tree max_op1 = minus_p ? vr1.min : vr1.max;
       tree sym_min_op0 = NULL_TREE;
       tree sym_min_op1 = NULL_TREE;
       tree sym_max_op0 = NULL_TREE;
       tree sym_max_op1 = NULL_TREE;
       bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1;

Re: VRP: x+1 and -x cannot be INT_MIN

[Jakub Jelinek]

On Sat, Nov 11, 2017 at 11:03:06PM +0100, Marc Glisse wrote:
> --- gcc/tree-vrp.c	(revision 254629)
> +++ gcc/tree-vrp.c	(working copy)
> @@ -2086,20 +2086,38 @@ extract_range_from_binary_expr_1 (value_
>        else
>  	set_value_range_to_varying (vr);
>  
>        return;
>      }
>  
>    /* For integer ranges, apply the operation to each end of the
>       range and see what we end up with.  */
>    if (code == PLUS_EXPR || code == MINUS_EXPR)
>      {
> +      /* If one argument is varying, we can sometimes still deduce a
> +	 range for the output: any + [3, +INF] is in [MIN+3, +INF].  */
> +      if (TYPE_OVERFLOW_UNDEFINED (expr_type))
> +	{
> +	  if(vr0.type == VR_VARYING && vr1.type == VR_RANGE)
> +	    {
> +	      vr0.type = type = VR_RANGE;
> +	      vr0.min = vrp_val_min (expr_type);
> +	      vr0.max = vrp_val_max (expr_type);
> +	    }
> +	  if(vr1.type == VR_VARYING && vr0.type == VR_RANGE)

Missing space before ( in 2 places.
Shouldn't this second if be actually else if?

> +	    {
> +	      vr1.type = VR_RANGE;
> +	      vr1.min = vrp_val_min (expr_type);
> +	      vr1.max = vrp_val_max (expr_type);
> +	    }
> +	}
> +

	Jakub

Re: VRP: x+1 and -x cannot be INT_MIN

[Marc Glisse]

On Sat, 11 Nov 2017, Jakub Jelinek wrote:

> On Sat, Nov 11, 2017 at 11:03:06PM +0100, Marc Glisse wrote:
>> --- gcc/tree-vrp.c	(revision 254629)
>> +++ gcc/tree-vrp.c	(working copy)
>> @@ -2086,20 +2086,38 @@ extract_range_from_binary_expr_1 (value_
>>        else
>>  	set_value_range_to_varying (vr);
>>
>>        return;
>>      }
>>
>>    /* For integer ranges, apply the operation to each end of the
>>       range and see what we end up with.  */
>>    if (code == PLUS_EXPR || code == MINUS_EXPR)
>>      {
>> +      /* If one argument is varying, we can sometimes still deduce a
>> +	 range for the output: any + [3, +INF] is in [MIN+3, +INF].  */
>> +      if (TYPE_OVERFLOW_UNDEFINED (expr_type))
>> +	{
>> +	  if(vr0.type == VR_VARYING && vr1.type == VR_RANGE)
>> +	    {
>> +	      vr0.type = type = VR_RANGE;
>> +	      vr0.min = vrp_val_min (expr_type);
>> +	      vr0.max = vrp_val_max (expr_type);
>> +	    }
>> +	  if(vr1.type == VR_VARYING && vr0.type == VR_RANGE)
>
> Missing space before ( in 2 places.

Thanks.

> Shouldn't this second if be actually else if?

I don't think it matters, since you cannot satisfy both sets of 
conditions. But you are right that it may be clearer, so I added the 
"else" locally.

-- 
Marc Glisse

Re: VRP: x+1 and -x cannot be INT_MIN

[Martin Sebor]

On 11/11/2017 03:03 PM, Marc Glisse wrote:
> Hello,
>
> with undefined overflow, just because we know nothing about one of the
> arguments of an addition doesn't mean we can't say something about the
> result. We could constrain more the cases where we replace VR_VARYING
> with a full VR_RANGE, but I didn't want to duplicate too much logic.
>
> The 20040409 testcases were introduced to test an RTL transformation, so
> I don't feel too bad adding -fwrapv to work around the undefined
> overflows they exhibit.
>
> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>
> 2017-11-13  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>     * tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR,
>     MINUS_EXPR]: Use a full range for VR_VARYING.
>
> gcc/testsuite/
>     PR testsuite/82951
>     * gcc.c-torture/execute/20040409-1.c: Use -fwrapv.
>     * gcc.c-torture/execute/20040409-2.c: Likewise.
>     * gcc.c-torture/execute/20040409-3.c: Likewise.
>     * gcc.dg/tree-ssa/vrp118.c: New file.
>

I'm curious about the 4 in the added test case (copied below).
Is there some significance to it or is actually meant to be
(or could it be) a 2?

FWIW, if there's some significance to the 4 then it would be
nice to have a comment there explaining it.  If there isn't
any then may I suggest to either change it to 2 or, perhaps
even better, change the second if condition to
(x < -__INT_MAX__ + 3) to make the effect on the range of
x clear and (presumably) also obviate questions like this
one.

Martin

+++ gcc/testsuite/gcc.dg/tree-ssa/vrp118.c	(working copy)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void eliminate_me();
+void f(int x,int y){
+    if (y < 4)
+      __builtin_unreachable();
+    x += y;
+    if (x == -__INT_MAX__)
+      eliminate_me ();
+}
+
+/* { dg-final { scan-tree-dump-not "eliminate_me" "optimized" } } */

Re: VRP: x+1 and -x cannot be INT_MIN

[Marc Glisse]

On Sun, 12 Nov 2017, Martin Sebor wrote:

> On 11/11/2017 03:03 PM, Marc Glisse wrote:
>> Hello,
>> 
>> with undefined overflow, just because we know nothing about one of the
>> arguments of an addition doesn't mean we can't say something about the
>> result. We could constrain more the cases where we replace VR_VARYING
>> with a full VR_RANGE, but I didn't want to duplicate too much logic.
>> 
>> The 20040409 testcases were introduced to test an RTL transformation, so
>> I don't feel too bad adding -fwrapv to work around the undefined
>> overflows they exhibit.
>> 
>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>> 
>> 2017-11-13  Marc Glisse  <marc.glisse@inria.fr>
>> 
>> gcc/
>>     * tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR,
>>     MINUS_EXPR]: Use a full range for VR_VARYING.
>> 
>> gcc/testsuite/
>>     PR testsuite/82951
>>     * gcc.c-torture/execute/20040409-1.c: Use -fwrapv.
>>     * gcc.c-torture/execute/20040409-2.c: Likewise.
>>     * gcc.c-torture/execute/20040409-3.c: Likewise.
>>     * gcc.dg/tree-ssa/vrp118.c: New file.
>> 
>
> I'm curious about the 4 in the added test case (copied below).
> Is there some significance to it or is actually meant to be
> (or could it be) a 2?
>
> FWIW, if there's some significance to the 4 then it would be
> nice to have a comment there explaining it.  If there isn't
> any then may I suggest to either change it to 2 or, perhaps
> even better, change the second if condition to
> (x < -__INT_MAX__ + 3) to make the effect on the range of
> x clear and (presumably) also obviate questions like this
> one.

I picked 4 (I was too lazy to type '2' and make it the usual 42) so there 
would be some margin, and people reading the testcase (i.e. me) wouldn't 
need to think too hard to know that -INT_MAX (shorter to type than 
-INT_MAX-1) falls in the forbidden region. Otherwise I would need to think 
if the inequality is strict, if I may have an off-by-1 error, etc. The 
goal is to check if a range computation is happening at all, not to check 
the exact bounds computed. If we want to make it tight, I guess we could 
test y<=0 and x==-INT_MAX-1 for instance.

My first idea was a test that -z can never be INT_MIN, but we have 
transformations that move negate_expr to the other side of comparisons, so 
that was more complicated to test than the addition.

> Martin
>
> +++ gcc/testsuite/gcc.dg/tree-ssa/vrp118.c	(working copy)
> @@ -0,0 +1,13 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +void eliminate_me();
> +void f(int x,int y){
> +    if (y < 4)
> +      __builtin_unreachable();
> +    x += y;
> +    if (x == -__INT_MAX__)
> +      eliminate_me ();
> +}
> +
> +/* { dg-final { scan-tree-dump-not "eliminate_me" "optimized" } } */

-- 
Marc Glisse

Re: VRP: x+1 and -x cannot be INT_MIN

[Richard Biener]

On Sat, Nov 11, 2017 at 11:03 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> Hello,
>
> with undefined overflow, just because we know nothing about one of the
> arguments of an addition doesn't mean we can't say something about the
> result. We could constrain more the cases where we replace VR_VARYING with a
> full VR_RANGE, but I didn't want to duplicate too much logic.
>
> The 20040409 testcases were introduced to test an RTL transformation, so I
> don't feel too bad adding -fwrapv to work around the undefined overflows
> they exhibit.
>
> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

Index: gcc/testsuite/gcc.c-torture/execute/20040409-1.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (revision 254629)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (working copy)
@@ -1,10 +1,12 @@
+/* { dg-options "-fwrapv" } */
+

I think you should use dg-additional-options (if that works).  As said in the PR
it would be safest to copy the tests, add -fwrapv and just remove the -fno-wrapv
cases that do not work.

I think a better fix would be in the caller of extract_range_from_binary_expr_1,
like simply always replacing VARYING with [min,max] if either of the two
ranges is not varying.  In vr_values::extract_range_from_binary_expr that is,
and doing an early out for varying & varying in _1.  Might simplify some
special case code for other opts as well.

Richard.

> 2017-11-13  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * tree-vrp.c (extract_range_from_binary_expr_1) [PLUS_EXPR,
>         MINUS_EXPR]: Use a full range for VR_VARYING.
>
> gcc/testsuite/
>         PR testsuite/82951
>         * gcc.c-torture/execute/20040409-1.c: Use -fwrapv.
>         * gcc.c-torture/execute/20040409-2.c: Likewise.
>         * gcc.c-torture/execute/20040409-3.c: Likewise.
>         * gcc.dg/tree-ssa/vrp118.c: New file.
>
> --
> Marc Glisse

Re: VRP: x+1 and -x cannot be INT_MIN

[Marc Glisse]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3196 bytes --]

On Mon, 13 Nov 2017, Richard Biener wrote:

> On Sat, Nov 11, 2017 at 11:03 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> with undefined overflow, just because we know nothing about one of the
>> arguments of an addition doesn't mean we can't say something about the
>> result. We could constrain more the cases where we replace VR_VARYING with a
>> full VR_RANGE, but I didn't want to duplicate too much logic.
>>
>> The 20040409 testcases were introduced to test an RTL transformation, so I
>> don't feel too bad adding -fwrapv to work around the undefined overflows
>> they exhibit.
>>
>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>
> Index: gcc/testsuite/gcc.c-torture/execute/20040409-1.c
> ===================================================================
> --- gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (revision 254629)
> +++ gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (working copy)
> @@ -1,10 +1,12 @@
> +/* { dg-options "-fwrapv" } */
> +
>
> I think you should use dg-additional-options (if that works).  As said in the PR
> it would be safest to copy the tests, add -fwrapv and just remove the -fno-wrapv
> cases that do not work.
>
> I think a better fix would be in the caller of extract_range_from_binary_expr_1,
> like simply always replacing VARYING with [min,max] if either of the two
> ranges is not varying.  In vr_values::extract_range_from_binary_expr that is,
> and doing an early out for varying & varying in _1.  Might simplify some
> special case code for other opts as well.

Like this? I didn't add the early out yet, among other things because I am 
tempted to add that pointer_diff_expr can never be the min value. I didn't 
see any obvious simplification of other special cases (I only looked 
briefly), the other place where we replace VR_VARYING with a full range is 
for conversions (unary). I guess I could drop the restriction to integers 
with undefined overflow...

I had to adapt one testcase where for VR_VARYING | [1, 1] we used to 
produce ~[0, 0] and now produce [-INT_MAX, INT_MAX]. I am surprised at how 
late the transformation now happens (only after removing 
__builtin_unreachable, in forwprop3, while trunk currently has it in evrp 
IIRC), but I didn't investigate, doesn't seem like the right time with all 
the VRP changes going on.

The tests that moved to -fwrapv are not undefined for all tested values, 
just a few, but subdividing further really doesn't seem worth the trouble.

Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

2017-11-20  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	* vr-values.c (extract_range_from_binary_expr): Use a full range
 	for VR_VARYING.

gcc/testsuite/
 	PR testsuite/82951
 	* gcc.c-torture/execute/20040409-1.c: Move invalid tests...
 	* gcc.c-torture/execute/20040409-1w.c: ... here with -fwrapv.
 	* gcc.c-torture/execute/20040409-2.c: Move invalid tests...
 	* gcc.c-torture/execute/20040409-2w.c: ... here with -fwrapv.
 	* gcc.c-torture/execute/20040409-3.c: Move invalid tests...
 	* gcc.c-torture/execute/20040409-3w.c: ... here with -fwrapv.
 	* gcc.dg/tree-ssa/cmpmul-1.c: Tweak condition.
 	* gcc.dg/tree-ssa/vrp118.c: New file.

-- 
Marc Glisse

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: TEXT/x-diff; name=vrp.patch, Size: 13792 bytes --]

Index: gcc/testsuite/gcc.c-torture/execute/20040409-1.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-1.c	(revision 254916)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-1.c	(working copy)
@@ -5,92 +5,62 @@ extern void abort ();
 int test1(int x)
 {
   return x ^ INT_MIN;
 }
 
 unsigned int test1u(unsigned int x)
 {
   return x ^ (unsigned int)INT_MIN;
 }
 
-int test2(int x)
-{
-  return x + INT_MIN;
-}
-
 unsigned int test2u(unsigned int x)
 {
   return x + (unsigned int)INT_MIN;
 }
 
-int test3(int x)
-{
-  return x - INT_MIN;
-}
-
 unsigned int test3u(unsigned int x)
 {
   return x - (unsigned int)INT_MIN;
 }
 
 int test4(int x)
 {
   int y = INT_MIN;
   return x ^ y;
 }
 
 unsigned int test4u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   return x ^ y;
 }
 
-int test5(int x)
-{
-  int y = INT_MIN;
-  return x + y;
-}
-
 unsigned int test5u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   return x + y;
 }
 
-int test6(int x)
-{
-  int y = INT_MIN;
-  return x - y;
-}
-
 unsigned int test6u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   return x - y;
 }
 
 
 
 void test(int a, int b)
 {
   if (test1(a) != b)
     abort();
-  if (test2(a) != b)
-    abort();
-  if (test3(a) != b)
-    abort();
   if (test4(a) != b)
     abort();
-  if (test5(a) != b)
-    abort();
-  if (test6(a) != b)
-    abort();
 }
 
 void testu(unsigned int a, unsigned int b)
 {
   if (test1u(a) != b)
     abort();
   if (test2u(a) != b)
     abort();
   if (test3u(a) != b)
     abort();
Index: gcc/testsuite/gcc.c-torture/execute/20040409-1w.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-1w.c	(nonexistent)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-1w.c	(working copy)
@@ -0,0 +1,65 @@
+/* { dg-additional-options "-fwrapv" } */
+
+#include <limits.h>
+
+extern void abort ();
+
+int test2(int x)
+{
+  return x + INT_MIN;
+}
+
+int test3(int x)
+{
+  return x - INT_MIN;
+}
+
+int test5(int x)
+{
+  int y = INT_MIN;
+  return x + y;
+}
+
+int test6(int x)
+{
+  int y = INT_MIN;
+  return x - y;
+}
+
+
+
+void test(int a, int b)
+{
+  if (test2(a) != b)
+    abort();
+  if (test3(a) != b)
+    abort();
+  if (test5(a) != b)
+    abort();
+  if (test6(a) != b)
+    abort();
+}
+
+
+int main()
+{
+#if INT_MAX == 2147483647
+  test(0x00000000,0x80000000);
+  test(0x80000000,0x00000000);
+  test(0x12345678,0x92345678);
+  test(0x92345678,0x12345678);
+  test(0x7fffffff,0xffffffff);
+  test(0xffffffff,0x7fffffff);
+#endif
+
+#if INT_MAX == 32767
+  test(0x0000,0x8000);
+  test(0x8000,0x0000);
+  test(0x1234,0x9234);
+  test(0x9234,0x1234);
+  test(0x7fff,0xffff);
+  test(0xffff,0x7fff);
+#endif
+
+  return 0;
+}
Index: gcc/testsuite/gcc.c-torture/execute/20040409-2.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-2.c	(revision 254916)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-2.c	(working copy)
@@ -15,55 +15,35 @@ unsigned int test1u(unsigned int x)
 int test2(int x)
 {
   return (x ^ 0x1234) ^ INT_MIN;
 }
 
 unsigned int test2u(unsigned int x)
 {
   return (x ^ 0x1234) ^ (unsigned int)INT_MIN;
 }
 
-int test3(int x)
-{
-  return (x + INT_MIN) ^ 0x1234;
-}
-
 unsigned int test3u(unsigned int x)
 {
   return (x + (unsigned int)INT_MIN) ^ 0x1234;
 }
 
-int test4(int x)
-{
-  return (x ^ 0x1234) + INT_MIN;
-}
-
 unsigned int test4u(unsigned int x)
 {
   return (x ^ 0x1234) + (unsigned int)INT_MIN;
 }
 
-int test5(int x)
-{
-  return (x - INT_MIN) ^ 0x1234;
-}
-
 unsigned int test5u(unsigned int x)
 {
   return (x - (unsigned int)INT_MIN) ^ 0x1234;
 }
 
-int test6(int x)
-{
-  return (x ^ 0x1234) - INT_MIN;
-}
-
 unsigned int test6u(unsigned int x)
 {
   return (x ^ 0x1234) - (unsigned int)INT_MIN;
 }
 
 int test7(int x)
 {
   int y = INT_MIN;
   int z = 0x1234;
   return (x ^ y) ^ z;
@@ -83,103 +63,59 @@ int test8(int x)
   return (x ^ y) ^ z;
 }
 
 unsigned int test8u(unsigned int x)
 {
   unsigned int y = 0x1234;
   unsigned int z = (unsigned int)INT_MIN;
   return (x ^ y) ^ z;
 }
 
-int test9(int x)
-{
-  int y = INT_MIN;
-  int z = 0x1234;
-  return (x + y) ^ z;
-}
-
 unsigned int test9u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   unsigned int z = 0x1234;
   return (x + y) ^ z;
 }
 
-int test10(int x)
-{
-  int y = 0x1234;
-  int z = INT_MIN;
-  return (x ^ y) + z;
-}
-
 unsigned int test10u(unsigned int x)
 {
   unsigned int y = 0x1234;
   unsigned int z = (unsigned int)INT_MIN;
   return (x ^ y) + z;
 }
 
-int test11(int x)
-{
-  int y = INT_MIN;
-  int z = 0x1234;
-  return (x - y) ^ z;
-}
-
 unsigned int test11u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   unsigned int z = 0x1234;
   return (x - y) ^ z;
 }
 
-int test12(int x)
-{
-  int y = 0x1234;
-  int z = INT_MIN;
-  return (x ^ y) - z;
-}
-
 unsigned int test12u(unsigned int x)
 {
   unsigned int y = 0x1234;
   unsigned int z = (unsigned int)INT_MIN;
   return (x ^ y) - z;
 }
 
 
 void test(int a, int b)
 {
   if (test1(a) != b)
     abort();
   if (test2(a) != b)
     abort();
-  if (test3(a) != b)
-    abort();
-  if (test4(a) != b)
-    abort();
-  if (test5(a) != b)
-    abort();
-  if (test6(a) != b)
-    abort();
   if (test7(a) != b)
     abort();
   if (test8(a) != b)
     abort();
-  if (test9(a) != b)
-    abort();
-  if (test10(a) != b)
-    abort();
-  if (test11(a) != b)
-    abort();
-  if (test12(a) != b)
-    abort();
 }
 
 void testu(unsigned int a, unsigned int b)
 {
   if (test1u(a) != b)
     abort();
   if (test2u(a) != b)
     abort();
   if (test3u(a) != b)
     abort();
Index: gcc/testsuite/gcc.c-torture/execute/20040409-2w.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-2w.c	(nonexistent)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-2w.c	(working copy)
@@ -0,0 +1,99 @@
+/* { dg-additional-options "-fwrapv" } */
+
+#include <limits.h>
+
+extern void abort ();
+
+int test3(int x)
+{
+  return (x + INT_MIN) ^ 0x1234;
+}
+
+int test4(int x)
+{
+  return (x ^ 0x1234) + INT_MIN;
+}
+
+int test5(int x)
+{
+  return (x - INT_MIN) ^ 0x1234;
+}
+
+int test6(int x)
+{
+  return (x ^ 0x1234) - INT_MIN;
+}
+
+int test9(int x)
+{
+  int y = INT_MIN;
+  int z = 0x1234;
+  return (x + y) ^ z;
+}
+
+int test10(int x)
+{
+  int y = 0x1234;
+  int z = INT_MIN;
+  return (x ^ y) + z;
+}
+
+int test11(int x)
+{
+  int y = INT_MIN;
+  int z = 0x1234;
+  return (x - y) ^ z;
+}
+
+int test12(int x)
+{
+  int y = 0x1234;
+  int z = INT_MIN;
+  return (x ^ y) - z;
+}
+
+
+void test(int a, int b)
+{
+  if (test3(a) != b)
+    abort();
+  if (test4(a) != b)
+    abort();
+  if (test5(a) != b)
+    abort();
+  if (test6(a) != b)
+    abort();
+  if (test9(a) != b)
+    abort();
+  if (test10(a) != b)
+    abort();
+  if (test11(a) != b)
+    abort();
+  if (test12(a) != b)
+    abort();
+}
+
+
+int main()
+{
+#if INT_MAX == 2147483647
+  test(0x00000000,0x80001234);
+  test(0x00001234,0x80000000);
+  test(0x80000000,0x00001234);
+  test(0x80001234,0x00000000);
+  test(0x7fffffff,0xffffedcb);
+  test(0xffffffff,0x7fffedcb);
+#endif
+
+#if INT_MAX == 32767
+  test(0x0000,0x9234);
+  test(0x1234,0x8000);
+  test(0x8000,0x1234);
+  test(0x9234,0x0000);
+  test(0x7fff,0xedcb);
+  test(0xffff,0x6dcb);
+#endif
+
+  return 0;
+}
+
Index: gcc/testsuite/gcc.c-torture/execute/20040409-3.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-3.c	(revision 254916)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-3.c	(working copy)
@@ -5,92 +5,62 @@ extern void abort ();
 int test1(int x)
 {
   return ~(x ^ INT_MIN);
 }
 
 unsigned int test1u(unsigned int x)
 {
   return ~(x ^ (unsigned int)INT_MIN);
 }
 
-int test2(int x)
-{
-  return ~(x + INT_MIN);
-}
-
 unsigned int test2u(unsigned int x)
 {
   return ~(x + (unsigned int)INT_MIN);
 }
 
-int test3(int x)
-{
-  return ~(x - INT_MIN);
-}
-
 unsigned int test3u(unsigned int x)
 {
   return ~(x - (unsigned int)INT_MIN);
 }
 
 int test4(int x)
 {
   int y = INT_MIN;
   return ~(x ^ y);
 }
 
 unsigned int test4u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   return ~(x ^ y);
 }
 
-int test5(int x)
-{
-  int y = INT_MIN;
-  return ~(x + y);
-}
-
 unsigned int test5u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   return ~(x + y);
 }
 
-int test6(int x)
-{
-  int y = INT_MIN;
-  return ~(x - y);
-}
-
 unsigned int test6u(unsigned int x)
 {
   unsigned int y = (unsigned int)INT_MIN;
   return ~(x - y);
 }
 
 
 
 void test(int a, int b)
 {
   if (test1(a) != b)
     abort();
-  if (test2(a) != b)
-    abort();
-  if (test3(a) != b)
-    abort();
   if (test4(a) != b)
     abort();
-  if (test5(a) != b)
-    abort();
-  if (test6(a) != b)
-    abort();
 }
 
 void testu(unsigned int a, unsigned int b)
 {
   if (test1u(a) != b)
     abort();
   if (test2u(a) != b)
     abort();
   if (test3u(a) != b)
     abort();
Index: gcc/testsuite/gcc.c-torture/execute/20040409-3w.c
===================================================================
--- gcc/testsuite/gcc.c-torture/execute/20040409-3w.c	(nonexistent)
+++ gcc/testsuite/gcc.c-torture/execute/20040409-3w.c	(working copy)
@@ -0,0 +1,65 @@
+/* { dg-additional-options "-fwrapv" } */
+
+#include <limits.h>
+
+extern void abort ();
+
+int test2(int x)
+{
+  return ~(x + INT_MIN);
+}
+
+int test3(int x)
+{
+  return ~(x - INT_MIN);
+}
+
+int test5(int x)
+{
+  int y = INT_MIN;
+  return ~(x + y);
+}
+
+int test6(int x)
+{
+  int y = INT_MIN;
+  return ~(x - y);
+}
+
+
+void test(int a, int b)
+{
+  if (test2(a) != b)
+    abort();
+  if (test3(a) != b)
+    abort();
+  if (test5(a) != b)
+    abort();
+  if (test6(a) != b)
+    abort();
+}
+
+
+int main()
+{
+#if INT_MAX == 2147483647
+  test(0x00000000,0x7fffffff);
+  test(0x80000000,0xffffffff);
+  test(0x12345678,0x6dcba987);
+  test(0x92345678,0xedcba987);
+  test(0x7fffffff,0x00000000);
+  test(0xffffffff,0x80000000);
+#endif
+
+#if INT_MAX == 32767
+  test(0x0000,0x7fff);
+  test(0x8000,0xffff);
+  test(0x1234,0x6dcb);
+  test(0x9234,0xedcb);
+  test(0x7fff,0x0000);
+  test(0xffff,0x8000);
+#endif
+
+  return 0;
+}
+
Index: gcc/testsuite/gcc.dg/tree-ssa/cmpmul-1.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/cmpmul-1.c	(revision 254916)
+++ gcc/testsuite/gcc.dg/tree-ssa/cmpmul-1.c	(working copy)
@@ -1,11 +1,11 @@
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-optimized-raw" } */
 
 int f(int a, int b, int c){
-  c |= 1; // c cannot be 0
+  if (c == 0) __builtin_unreachable();
   a *= c;
   b *= c;
   return a == b;
 }
 
 /* { dg-final { scan-tree-dump-not "bit_ior_expr" "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp118.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp118.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp118.c	(working copy)
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void eliminate_me();
+void f(int x,int y){
+    if (y <= 0)
+      __builtin_unreachable();
+    x += y;
+    if (x == -__INT_MAX__ - 1)
+      eliminate_me ();
+}
+
+/* { dg-final { scan-tree-dump-not "eliminate_me" "optimized" } } */
Index: gcc/vr-values.c
===================================================================
--- gcc/vr-values.c	(revision 254916)
+++ gcc/vr-values.c	(working copy)
@@ -764,20 +764,39 @@ vr_values::extract_range_from_binary_exp
   else
     set_value_range_to_varying (&vr0);
 
   if (TREE_CODE (op1) == SSA_NAME)
     vr1 = *(get_value_range (op1));
   else if (is_gimple_min_invariant (op1))
     set_value_range_to_value (&vr1, op1, NULL);
   else
     set_value_range_to_varying (&vr1);
 
+  /* If one argument is varying, we can sometimes still deduce a
+     range for the output: any + [3, +INF] is in [MIN+3, +INF].  */
+  if (INTEGRAL_TYPE_P (TREE_TYPE (op0))
+      && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
+    {
+      if (vr0.type == VR_VARYING && vr1.type != VR_VARYING)
+	{
+	  vr0.type = VR_RANGE;
+	  vr0.min = vrp_val_min (expr_type);
+	  vr0.max = vrp_val_max (expr_type);
+	}
+      else if (vr1.type == VR_VARYING && vr0.type != VR_VARYING)
+	{
+	  vr1.type = VR_RANGE;
+	  vr1.min = vrp_val_min (expr_type);
+	  vr1.max = vrp_val_max (expr_type);
+	}
+    }
+
   extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
 
   /* 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
      symbolic comparison.  When a bound of the range of the first operand
      is invariant, we set the corresponding bound of the new range to INF
      in order to avoid recursing on the range of the second operand.  */
   if (vr->type == VR_VARYING
       && (code == PLUS_EXPR || code == MINUS_EXPR)
       && TREE_CODE (op1) == SSA_NAME

Re: VRP: x+1 and -x cannot be INT_MIN

[Jeff Law]

On 11/19/2017 03:41 AM, Marc Glisse wrote:
> On Mon, 13 Nov 2017, Richard Biener wrote:
> 
>> On Sat, Nov 11, 2017 at 11:03 PM, Marc Glisse <marc.glisse@inria.fr>
>> wrote:
>>> Hello,
>>>
>>> with undefined overflow, just because we know nothing about one of the
>>> arguments of an addition doesn't mean we can't say something about the
>>> result. We could constrain more the cases where we replace VR_VARYING
>>> with a
>>> full VR_RANGE, but I didn't want to duplicate too much logic.
>>>
>>> The 20040409 testcases were introduced to test an RTL transformation,
>>> so I
>>> don't feel too bad adding -fwrapv to work around the undefined overflows
>>> they exhibit.
>>>
>>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>>
>> Index: gcc/testsuite/gcc.c-torture/execute/20040409-1.c
>> ===================================================================
>> --- gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (revision 254629)
>> +++ gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (working copy)
>> @@ -1,10 +1,12 @@
>> +/* { dg-options "-fwrapv" } */
>> +
>>
>> I think you should use dg-additional-options (if that works).  As said
>> in the PR
>> it would be safest to copy the tests, add -fwrapv and just remove the
>> -fno-wrapv
>> cases that do not work.
>>
>> I think a better fix would be in the caller of
>> extract_range_from_binary_expr_1,
>> like simply always replacing VARYING with [min,max] if either of the two
>> ranges is not varying.  In vr_values::extract_range_from_binary_expr
>> that is,
>> and doing an early out for varying & varying in _1.  Might simplify some
>> special case code for other opts as well.
> 
> Like this? I didn't add the early out yet, among other things because I
> am tempted to add that pointer_diff_expr can never be the min value. I
> didn't see any obvious simplification of other special cases (I only
> looked briefly), the other place where we replace VR_VARYING with a full
> range is for conversions (unary). I guess I could drop the restriction
> to integers with undefined overflow...
> 
> I had to adapt one testcase where for VR_VARYING | [1, 1] we used to
> produce ~[0, 0] and now produce [-INT_MAX, INT_MAX]. I am surprised at
> how late the transformation now happens (only after removing
> __builtin_unreachable, in forwprop3, while trunk currently has it in
> evrp IIRC), but I didn't investigate, doesn't seem like the right time
> with all the VRP changes going on.
> 
> The tests that moved to -fwrapv are not undefined for all tested values,
> just a few, but subdividing further really doesn't seem worth the trouble.
> 
> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
> 
> 2017-11-20  Marc Glisse  <marc.glisse@inria.fr>
> 
> gcc/
>     * vr-values.c (extract_range_from_binary_expr): Use a full range
>     for VR_VARYING.
> 
> gcc/testsuite/
>     PR testsuite/82951
>     * gcc.c-torture/execute/20040409-1.c: Move invalid tests...
>     * gcc.c-torture/execute/20040409-1w.c: ... here with -fwrapv.
>     * gcc.c-torture/execute/20040409-2.c: Move invalid tests...
>     * gcc.c-torture/execute/20040409-2w.c: ... here with -fwrapv.
>     * gcc.c-torture/execute/20040409-3.c: Move invalid tests...
>     * gcc.c-torture/execute/20040409-3w.c: ... here with -fwrapv.
>     * gcc.dg/tree-ssa/cmpmul-1.c: Tweak condition.
>     * gcc.dg/tree-ssa/vrp118.c: New file.
> 
Slick.  I wish I had thought of this last year -- I think it would have
made a BZ I was looking at easier to tackle.  Richi's already engaged on
the issue, so I'll let him handle the review side, I just wanted to note
that I see value in discovering these ranges.

Jeff

Re: VRP: x+1 and -x cannot be INT_MIN

[Richard Biener]

On Sun, Nov 19, 2017 at 11:41 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 13 Nov 2017, Richard Biener wrote:
>
>> On Sat, Nov 11, 2017 at 11:03 PM, Marc Glisse <marc.glisse@inria.fr>
>> wrote:
>>>
>>> Hello,
>>>
>>> with undefined overflow, just because we know nothing about one of the
>>> arguments of an addition doesn't mean we can't say something about the
>>> result. We could constrain more the cases where we replace VR_VARYING
>>> with a
>>> full VR_RANGE, but I didn't want to duplicate too much logic.
>>>
>>> The 20040409 testcases were introduced to test an RTL transformation, so
>>> I
>>> don't feel too bad adding -fwrapv to work around the undefined overflows
>>> they exhibit.
>>>
>>> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.
>>
>>
>> Index: gcc/testsuite/gcc.c-torture/execute/20040409-1.c
>> ===================================================================
>> --- gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (revision 254629)
>> +++ gcc/testsuite/gcc.c-torture/execute/20040409-1.c    (working copy)
>> @@ -1,10 +1,12 @@
>> +/* { dg-options "-fwrapv" } */
>> +
>>
>> I think you should use dg-additional-options (if that works).  As said in
>> the PR
>> it would be safest to copy the tests, add -fwrapv and just remove the
>> -fno-wrapv
>> cases that do not work.
>>
>> I think a better fix would be in the caller of
>> extract_range_from_binary_expr_1,
>> like simply always replacing VARYING with [min,max] if either of the two
>> ranges is not varying.  In vr_values::extract_range_from_binary_expr that
>> is,
>> and doing an early out for varying & varying in _1.  Might simplify some
>> special case code for other opts as well.
>
>
> Like this? I didn't add the early out yet, among other things because I am
> tempted to add that pointer_diff_expr can never be the min value. I didn't
> see any obvious simplification of other special cases (I only looked
> briefly), the other place where we replace VR_VARYING with a full range is
> for conversions (unary). I guess I could drop the restriction to integers
> with undefined overflow...
>
> I had to adapt one testcase where for VR_VARYING | [1, 1] we used to produce
> ~[0, 0] and now produce [-INT_MAX, INT_MAX]. I am surprised at how late the
> transformation now happens (only after removing __builtin_unreachable, in
> forwprop3, while trunk currently has it in evrp IIRC), but I didn't
> investigate, doesn't seem like the right time with all the VRP changes going
> on.

Interesting - can you open a bugreport so we don't forget?  I suspect it's
the effect of zero_nonzero_bits_from_vr handling VARYING and [INT_MIN, INT_MAX]
differently rippling down.  At some point in time I wanted to get rid of VARYING
in favor of [INT_MIN, INT_MAX] ...

>
> The tests that moved to -fwrapv are not undefined for all tested values,
> just a few, but subdividing further really doesn't seem worth the trouble.
>
> Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

Ok.

Thanks,
Richard.

> 2017-11-20  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         * vr-values.c (extract_range_from_binary_expr): Use a full range
>         for VR_VARYING.
>
> gcc/testsuite/
>         PR testsuite/82951
>         * gcc.c-torture/execute/20040409-1.c: Move invalid tests...
>         * gcc.c-torture/execute/20040409-1w.c: ... here with -fwrapv.
>         * gcc.c-torture/execute/20040409-2.c: Move invalid tests...
>         * gcc.c-torture/execute/20040409-2w.c: ... here with -fwrapv.
>         * gcc.c-torture/execute/20040409-3.c: Move invalid tests...
>         * gcc.c-torture/execute/20040409-3w.c: ... here with -fwrapv.
>         * gcc.dg/tree-ssa/cmpmul-1.c: Tweak condition.
>
>         * gcc.dg/tree-ssa/vrp118.c: New file.
>
> --
> Marc Glisse

Re: VRP: x+1 and -x cannot be INT_MIN

[Marc Glisse]

On Mon, 20 Nov 2017, Richard Biener wrote:

>> I had to adapt one testcase where for VR_VARYING | [1, 1] we used to produce
>> ~[0, 0] and now produce [-INT_MAX, INT_MAX]. I am surprised at how late the
>> transformation now happens (only after removing __builtin_unreachable, in
>> forwprop3, while trunk currently has it in evrp IIRC), but I didn't
>> investigate, doesn't seem like the right time with all the VRP changes going
>> on.
>
> Interesting - can you open a bugreport so we don't forget?  I suspect it's
> the effect of zero_nonzero_bits_from_vr handling VARYING and [INT_MIN, INT_MAX]
> differently rippling down.  At some point in time I wanted to get rid of VARYING
> in favor of [INT_MIN, INT_MAX] ...

I filed PR 83072 about missing the optimization in evrp, but now I am not 
sure if that's what you wanted in the PR or if you wanted one about 
chosing between ~[0, 0] and [-INT_MAX, INT_MAX] for VR_VARYING | [1, 1]...

-- 
Marc Glisse

Re: VRP: x+1 and -x cannot be INT_MIN

[Richard Biener]

On Mon, Nov 20, 2017 at 3:10 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 20 Nov 2017, Richard Biener wrote:
>
>>> I had to adapt one testcase where for VR_VARYING | [1, 1] we used to
>>> produce
>>> ~[0, 0] and now produce [-INT_MAX, INT_MAX]. I am surprised at how late
>>> the
>>> transformation now happens (only after removing __builtin_unreachable, in
>>> forwprop3, while trunk currently has it in evrp IIRC), but I didn't
>>> investigate, doesn't seem like the right time with all the VRP changes
>>> going
>>> on.
>>
>>
>> Interesting - can you open a bugreport so we don't forget?  I suspect it's
>> the effect of zero_nonzero_bits_from_vr handling VARYING and [INT_MIN,
>> INT_MAX]
>> differently rippling down.  At some point in time I wanted to get rid of
>> VARYING
>> in favor of [INT_MIN, INT_MAX] ...
>
>
> I filed PR 83072 about missing the optimization in evrp, but now I am not
> sure if that's what you wanted in the PR or if you wanted one about chosing
> between ~[0, 0] and [-INT_MAX, INT_MAX] for VR_VARYING | [1, 1]...

Yes, the one choosing between these two.  The EVRP missed optimization
is of course also useful to track.

Richard.

> --
> Marc Glisse