[VRP] Improve value ranges for unsigned division

[VRP] Improve value ranges for unsigned division

[Kugan]

[-- Attachment #1: Type: text/plain, Size: 641 bytes --]

As discussed in PR64130, this patch improves the VRP value ranges for
unsigned division.

Bootstrapped and regression tested on x86_64-linux-gnu and regression
tested on arm-none-linux-gnu with no new regression.

Is this OK for trunk?

Thanks,
Kugan

gcc/ChangeLog:

2015-06-20  Kugan Vivekanandarajah  <kuganv@linaro.org>

	PR middle-end/64130
	* tree-vrp.c (extract_range_from_binary_expr_1): For unsigned
	division, compute minimum when value ranges for dividend and
	divisor are available.


gcc/testsuite/ChangeLog:

2015-06-20  Kugan Vivekanandarajah  <kuganv@linaro.org>

	PR middle-end/64130
	* gcc.dg/tree-ssa/pr64130.c: New test.

[-- Attachment #2: p.txt --]
[-- Type: text/plain, Size: 1118 bytes --]

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
index e69de29..9e96abb 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
@@ -0,0 +1,11 @@
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int funsigned(unsigned a)
+{
+  return 0x1ffffffffL / a == 0;
+}
+
+/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "vrp1" } } */
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b517363..2e1c84b 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3158,7 +3158,16 @@ extract_range_from_binary_expr_1 (value_range_t *vr,
 		type = VR_VARYING;
 	      cmp = compare_values (vr0.min, zero);
 	      if (cmp == 1)
-		min = zero;
+		{
+		  /* For unsigned division when value ranges for dividend
+		     and divisor are available.  */
+		  if (vr1.type == VR_RANGE
+		      && !symbolic_range_p (&vr0)
+		      && !symbolic_range_p (&vr1))
+		    min = int_const_binop (code, vr0.min, vr1.max);
+		  else
+		    min = zero;
+		}
 	      else if (cmp == 0 || cmp == -1)
 		min = vr0.min;
 	      else

Re: [VRP] Improve value ranges for unsigned division

[Richard Biener]

On Sat, Jun 20, 2015 at 9:12 AM, Kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> As discussed in PR64130, this patch improves the VRP value ranges for
> unsigned division.
>
> Bootstrapped and regression tested on x86_64-linux-gnu and regression
> tested on arm-none-linux-gnu with no new regression.
>
> Is this OK for trunk?

Hum, the patch is at least incomplete not covering the
cmp == -1 case in the max value computation, no?

Also I wonder if we have two VR_RANGEs as you require
the code using extract_range_from_multiplicative_op_1 isn't
better suited and already handles the case properly?

Richard.

> Thanks,
> Kugan
>
> gcc/ChangeLog:
>
> 2015-06-20  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>         PR middle-end/64130
>         * tree-vrp.c (extract_range_from_binary_expr_1): For unsigned
>         division, compute minimum when value ranges for dividend and
>         divisor are available.
>
>
> gcc/testsuite/ChangeLog:
>
> 2015-06-20  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>         PR middle-end/64130
>         * gcc.dg/tree-ssa/pr64130.c: New test.

Re: [VRP] Improve value ranges for unsigned division

[Kugan]

[-- Attachment #1: Type: text/plain, Size: 1643 bytes --]



On 23/06/15 01:09, Richard Biener wrote:
> On Sat, Jun 20, 2015 at 9:12 AM, Kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>> As discussed in PR64130, this patch improves the VRP value ranges for
>> unsigned division.
>>
>> Bootstrapped and regression tested on x86_64-linux-gnu and regression
>> tested on arm-none-linux-gnu with no new regression.
>>
>> Is this OK for trunk?
> 
> Hum, the patch is at least incomplete not covering the
> cmp == -1 case in the max value computation, no?

Thanks for the review. Attached patch adds this as well.

> 
> Also I wonder if we have two VR_RANGEs as you require
> the code using extract_range_from_multiplicative_op_1 isn't
> better suited and already handles the case properly?
>

I tried with this approach. But, for value range of vr1 where min or max
is zero,  extract_range_from_multiplicative_op_1 will not be able to
infer range.

If we check for vr1 having zero before calling
extract_range_from_multiplicative_op_1, then it is not going get the
value range for the test case in PR (which is  2305843009213693951 / a
 where a has a range [0, 4294967295])


Thanks,
Kugan



> Richard.
> 
>> Thanks,
>> Kugan
>>
>> gcc/ChangeLog:
>>
>> 2015-06-20  Kugan Vivekanandarajah  <kuganv@linaro.org>
>>
>>         PR middle-end/64130
>>         * tree-vrp.c (extract_range_from_binary_expr_1): For unsigned
>>         division, compute minimum when value ranges for dividend and
>>         divisor are available.
>>
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2015-06-20  Kugan Vivekanandarajah  <kuganv@linaro.org>
>>
>>         PR middle-end/64130
>>         * gcc.dg/tree-ssa/pr64130.c: New test.

[-- Attachment #2: p.txt --]
[-- Type: text/plain, Size: 1680 bytes --]

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
index e69de29..9e96abb 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c
@@ -0,0 +1,11 @@
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+int funsigned(unsigned a)
+{
+  return 0x1ffffffffL / a == 0;
+}
+
+/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "vrp1" } } */
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b517363..0b8fb31 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -3151,14 +3151,33 @@ extract_range_from_binary_expr_1 (value_range_t *vr,
 		 and all numbers from min to 0 for negative min.  */
 	      cmp = compare_values (vr0.max, zero);
 	      if (cmp == -1)
-		max = zero;
+		{
+		  /* When vr0.max < 0, vr1.min != 0 and value
+		     ranges for dividend and divisor are available.  */
+		  if (vr1.type == VR_RANGE
+		      && !symbolic_range_p (&vr0)
+		      && !symbolic_range_p (&vr1)
+		      && !compare_values (vr1.min, zero))
+		    max = int_const_binop (code, vr0.max, vr1.min);
+		  else
+		    max = zero;
+		}
 	      else if (cmp == 0 || cmp == 1)
 		max = vr0.max;
 	      else
 		type = VR_VARYING;
 	      cmp = compare_values (vr0.min, zero);
 	      if (cmp == 1)
-		min = zero;
+		{
+		  /* For unsigned division when value ranges for dividend
+		     and divisor are available.  */
+		  if (vr1.type == VR_RANGE
+		      && !symbolic_range_p (&vr0)
+		      && !symbolic_range_p (&vr1))
+		    min = int_const_binop (code, vr0.min, vr1.max);
+		  else
+		    min = zero;
+		}
 	      else if (cmp == 0 || cmp == -1)
 		min = vr0.min;
 	      else

Re: [VRP] Improve value ranges for unsigned division

[Jeff Law]

On 06/24/2015 12:36 AM, Kugan wrote:
>
>
> On 23/06/15 01:09, Richard Biener wrote:
>> On Sat, Jun 20, 2015 at 9:12 AM, Kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> As discussed in PR64130, this patch improves the VRP value ranges for
>>> unsigned division.
>>>
>>> Bootstrapped and regression tested on x86_64-linux-gnu and regression
>>> tested on arm-none-linux-gnu with no new regression.
>>>
>>> Is this OK for trunk?
>>
>> Hum, the patch is at least incomplete not covering the
>> cmp == -1 case in the max value computation, no?
>
> Thanks for the review. Attached patch adds this as well.
Please add a testcase for the cmp == -1 case too.  With that addition 
this is OK for the trunk.

jeff

Re: [VRP] Improve value ranges for unsigned division

[Kugan]

On 26/06/15 04:27, Jeff Law wrote:
> On 06/24/2015 12:36 AM, Kugan wrote:
>>
>>
>> On 23/06/15 01:09, Richard Biener wrote:
>>> On Sat, Jun 20, 2015 at 9:12 AM, Kugan
>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>> As discussed in PR64130, this patch improves the VRP value ranges for
>>>> unsigned division.
>>>>
>>>> Bootstrapped and regression tested on x86_64-linux-gnu and regression
>>>> tested on arm-none-linux-gnu with no new regression.
>>>>
>>>> Is this OK for trunk?
>>>
>>> Hum, the patch is at least incomplete not covering the
>>> cmp == -1 case in the max value computation, no?
>>
>> Thanks for the review. Attached patch adds this as well.
> Please add a testcase for the cmp == -1 case too.  With that addition
> this is OK for the trunk.
> 

Committed as r225108 with the updated test-case after fresh bootstrap
and regression testing for x86_64-linux-gnu.

Thanks,
Kugan

> jeff
>