Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Marc Glisse]

On Mon, 13 Feb 2017, Jeff Law wrote:


On 02/13/2017 09:15 AM, Marc Glisse wrote:

On Mon, 13 Feb 2017, Jeff Law wrote:


On 02/12/2017 12:13 AM, Marc Glisse wrote:

On Tue, 7 Feb 2017, Jeff Law wrote:


* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range ~[0,0].


If I understand correctly, for x /[ex] 4 with x!=0, we currently split
~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
could change the union function, but this patch prefers changing the
code elsewhere so that the new behavior is restricted to the
EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
a new non-contiguous version of ranges, where union would already work).
Is that it?

That was one of alternate approaches I suggested.

Part of the problem is the conversion of ~[0,0] is imprecise when it's
going to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the
thread.  As a result of that imprecision, the ranges we get are
[INT_MIN/4,0] U [0,INT_MAX/4].


If VRP for [1, INT_MAX] /[ex] 4 produces [0, INT_MAX/4] instead of [1,
INT_MAX/4], that's a bug that should be fixed in any case. You shouldn't
need [4, INT_MAX] for that.
Agreed.  But given it doesn't actually make anything around 79095 easier, I'd 
just assume defer to gcc-8.


That all depends how you handle the intersection/union thing.

I suspect that we'll see nicely refined anti-ranges, but rarely see 
improvements in the generated code.





If we fix that imprecision so that the conversion yields [INT_MIN,-4]
U [4, INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U
[1,INT_MAX/4], which union_ranges turns into [INT_MIN/4,INT_MAX/4].
We still end up needing a hack in union_ranges that will look a hell
of a lot like the one we're contemplating for intersect_ranges.


That was the point of my question. Do we want to put that "hack" (prefer
an anti-range in some cases) in a central place where it would apply any
time we try to replace [a,b]U[c,d] (b+1

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Jeff Law]

On 02/13/2017 09:15 AM, Marc Glisse wrote:

On Mon, 13 Feb 2017, Jeff Law wrote:


On 02/12/2017 12:13 AM, Marc Glisse wrote:

On Tue, 7 Feb 2017, Jeff Law wrote:


* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range ~[0,0].


If I understand correctly, for x /[ex] 4 with x!=0, we currently split
~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
could change the union function, but this patch prefers changing the
code elsewhere so that the new behavior is restricted to the
EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
a new non-contiguous version of ranges, where union would already work).
Is that it?

That was one of alternate approaches I suggested.

Part of the problem is the conversion of ~[0,0] is imprecise when it's
going to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the
thread.  As a result of that imprecision, the ranges we get are
[INT_MIN/4,0] U [0,INT_MAX/4].


If VRP for [1, INT_MAX] /[ex] 4 produces [0, INT_MAX/4] instead of [1,
INT_MAX/4], that's a bug that should be fixed in any case. You shouldn't
need [4, INT_MAX] for that.
Agreed.  But given it doesn't actually make anything around 79095 
easier, I'd just assume defer to gcc-8.


I suspect that we'll see nicely refined anti-ranges, but rarely see 
improvements in the generated code.





If we fix that imprecision so that the conversion yields [INT_MIN,-4]
U [4, INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U
[1,INT_MAX/4], which union_ranges turns into [INT_MIN/4,INT_MAX/4].
We still end up needing a hack in union_ranges that will look a hell
of a lot like the one we're contemplating for intersect_ranges.


That was the point of my question. Do we want to put that "hack" (prefer
an anti-range in some cases) in a central place where it would apply any
time we try to replace [a,b]U[c,d] (b+1

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Marc Glisse]

On Mon, 13 Feb 2017, Jeff Law wrote:


On 02/12/2017 12:13 AM, Marc Glisse wrote:

On Tue, 7 Feb 2017, Jeff Law wrote:


* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range ~[0,0].


If I understand correctly, for x /[ex] 4 with x!=0, we currently split
~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
could change the union function, but this patch prefers changing the
code elsewhere so that the new behavior is restricted to the
EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
a new non-contiguous version of ranges, where union would already work).
Is that it?

That was one of alternate approaches I suggested.

Part of the problem is the conversion of ~[0,0] is imprecise when it's going 
to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the thread.  As a 
result of that imprecision, the ranges we get are [INT_MIN/4,0] U 
[0,INT_MAX/4].


If VRP for [1, INT_MAX] /[ex] 4 produces [0, INT_MAX/4] instead of [1, 
INT_MAX/4], that's a bug that should be fixed in any case. You shouldn't 
need [4, INT_MAX] for that.


If we fix that imprecision so that the conversion yields [INT_MIN,-4] U [4, 
INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U [1,INT_MAX/4], 
which union_ranges turns into [INT_MIN/4,INT_MAX/4].  We still end up needing 
a hack in union_ranges that will look a hell of a lot like the one we're 
contemplating for intersect_ranges.


That was the point of my question. Do we want to put that "hack" (prefer 
an anti-range in some cases) in a central place where it would apply any 
time we try to replace [a,b]U[c,d] (b+1

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Jeff Law]

On 02/12/2017 12:13 AM, Marc Glisse wrote:

On Tue, 7 Feb 2017, Jeff Law wrote:


* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range ~[0,0].


If I understand correctly, for x /[ex] 4 with x!=0, we currently split
~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
could change the union function, but this patch prefers changing the
code elsewhere so that the new behavior is restricted to the
EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
a new non-contiguous version of ranges, where union would already work).
Is that it?

That was one of alternate approaches I suggested.

Part of the problem is the conversion of ~[0,0] is imprecise when it's 
going to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the 
thread.  As a result of that imprecision, the ranges we get are 
[INT_MIN/4,0] U [0,INT_MAX/4].


If we fix that imprecision so that the conversion yields [INT_MIN,-4] U 
[4, INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U 
[1,INT_MAX/4], which union_ranges turns into [INT_MIN/4,INT_MAX/4].  We 
still end up needing a hack in union_ranges that will look a hell of a 
lot like the one we're contemplating for intersect_ranges.


Jeff

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Marc Glisse]

On Tue, 7 Feb 2017, Jeff Law wrote:


* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range ~[0,0].


If I understand correctly, for x /[ex] 4 with x!=0, we currently split 
~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR which 
gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the union of 
those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We could change 
the union function, but this patch prefers changing the code elsewhere so 
that the new behavior is restricted to the EXACT_DIV_EXPR case (and 
supposedly the patch will be reverted if we get a new non-contiguous 
version of ranges, where union would already work). Is that it?


--
Marc Glisse

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Jeff Law]

On 02/09/2017 08:06 PM, Jeff Law wrote:






+  && *vr0min == *vr0max
+  && integer_zerop (*vr0min)
+  && TREE_CODE (vr1max) == INTEGER_CST
+  && TREE_CODE (vr1min) == INTEGER_CST
+  && difference_larger_than (vr1max, vr1min, 65536))
+   ;


in the case that interests us for the PR what is vr1?

[-2305843009213693952, 2305843009213693951]
And just for completeness, I instrumented the compiler to dump the range 
every time this code triggered to see what kind of ranges we'd be 
changing into ~[0,0].


It triggers 1260 times during a bootstrap.  20 most common:

 20 [-1073741824,1073741823]
 20 [-65535,65535]
 22 [-2147483647,2147483646]
 23 [-1152921504606846976,1152921504606846975]
 24 [-2147483648,39]
 24 [-72057594037927936,72057594037927935]
 24 [-8388608,8388607]
 27 [-536870912,536870911]
 28 [-2305843009213693952,2305843009213693951]
 28 [-536870910,536870910]
 32 [-2147483648,113]
 41 [-2147483648,32767]
 48 [-1,2147483646]
 48 [-2147483647,2147483647]
 48 [-2147483648,63]
 48 [-9223372036854775807,9223372036854775807]
 53 [-214748364,214748364]
 70 [-2147483648,1]
160 [-2147483648,2147483647]
162 [-2147483648,2147483646]

Obviously it's harder to know how many of those ultimately lead to 
optimizing something better.


With your heuristic we get 378 triggers with the most common being:


 17 [-2147483648,113]
 17 [-9223372036854775808,9223372036854775806]
 18 [-1,2147483646]
 18 [-2147483648,32767]
 23 [-1152921504606846976,1152921504606846975]
 24 [-72057594037927936,72057594037927935]
 27 [-536870912,536870911]
 28 [-2305843009213693952,2305843009213693951]
 45 [-2147483648,2147483646]
 48 [-9223372036854775807,9223372036854775807]

Anyway, I'll do the usual testing with your version.

jeff

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Richard Biener]

On Fri, Feb 10, 2017 at 4:06 AM, Jeff Law  wrote:
> On 02/08/2017 05:45 AM, Richard Biener wrote:
>>
>> On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law  wrote:
>>>
>>>
>>> This patch addresses issues Richi raised from V1.  Specifically it moves
>>> EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less
>>> aggressively uses ~[0,0] when intersecting ranges -- only doing so when
>>> vr1's range is > 65536 elements.  That number is highly arbitrary.  I'm
>>> certainly open to other values, not sure if a PARAM makes sense or not,
>>> but
>>> can certainly do that if folks think it would be useful.  There were
>>> other
>>> minor nits Richi pointed out that were fixed too.
>>>
>>> Bootstrapped and regression tested as part of the full patch series.
>>>
>>> OK for the trunk?
>>>
>>>
>>> * tree-vrp.c (extract_range_from_binary_expr_1): For
>>> EXACT_DIV_EXPR,
>>> if the numerator has the range ~[0,0] make the resultant range
>>> ~[0,0].
>>> (extract_range_from_binary_expr): For MINUS_EXPR with no derived
>>> range,
>>> if the operands are known to be not equal, then the resulting
>>> range
>>> is ~[0,0].
>>> (difference_larger_than): New function.
>>> (intersect_ranges): If the new range is ~[0,0] and the old range
>>> is
>>> wide, then prefer ~[0,0].
>>>
>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>> index b429217..ad8173c 100644
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
>>>if (vr0.type == VR_ANTI_RANGE
>>>&& ranges_from_anti_range (, , ))
>>>  {
>>> +  /* We get imprecise results from ranges_from_anti_range when
>>> +code is EXACT_DIV_EXPR.  We could mask out bits in the resulting
>>> +range, but then we also need to hack up vrp_meet.  It's just
>>> +easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR.
>>> */
>>> +  if (code == EXACT_DIV_EXPR
>>> + && vr0.type == VR_ANTI_RANGE
>>> + && vr0.min == vr0.max
>>> + && integer_zerop (vr0.min))
>>> +   {
>>> + set_value_range_to_nonnull (vr, expr_type);
>>> + return;
>>> +   }
>>> +
>>
>>
>> Please move this before the surrounding if.
>
> Yea.  I wasn't sure about best location.  Before the surrounding IF works
> for me.
>
>>
>>>extract_range_from_binary_expr_1 (vr, code, expr_type, ,
>>> vr1_);
>>>if (vrtem1.type != VR_UNDEFINED)
>>> {
>>> @@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,
>>>
>>>extract_range_from_binary_expr_1 (vr, code, expr_type, _vr0,
>>> );
>>>  }
>>> +
>>> +  /* If we didn't derive a range for MINUS_EXPR, and
>>> + op1's range is ~[op0,op0] or vice-versa, then we
>>> + can derive a non-null range.  This happens often for
>>> + pointer subtraction.  */
>>> +  if (vr->type == VR_VARYING
>>> +  && code == MINUS_EXPR
>>> +  && TREE_CODE (op0) == SSA_NAME
>>> +  && ((vr0.type == VR_ANTI_RANGE
>>> +  && symbolic_range_based_on_p (, op1)
>>
>>
>> Just seeing this again this also covers ~[op1 - 1, op1 - 1] and you are
>> just lucky because of the vr0.min == vr0.max equality compare and
>> both op1 - 1 hopefully not tree-shared (I'm not confident in that...).
>>
>> So I think it would be better written as simply
>>
>>&& vr0.min == op1
>>
>> together with vr0.min == vr0.max you'd get what you are after.
>
> You're right.  Fixed.
>
>>
>>> +  && vr0.min == vr0.max)
>>> + || (vr1.type == VR_ANTI_RANGE
>>> + && symbolic_range_based_on_p (, op0)
>>
>>
>> Likewise of course.
>
> Likewise.
>
>
>>
>>> + && vr1.min == vr1.max)))
>>> +  set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>>>  }
>>>
>>>  /* Extract range information from a unary operation CODE based on
>>> @@ -8448,6 +8476,17 @@ give_up:
>>>*vr0max = NULL_TREE;
>>>  }
>>>
>>> +/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT
>>> (HOST_WIDE_INT)
>>> +   or overflows, FALSE otherwise.  */
>>> +
>>> +static bool
>>> +difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
>>> +{
>>> +  bool overflow;
>>> +  wide_int res = wi::sub (max, min, SIGNED, );
>>> +  return wi::gt_p (res, limit, UNSIGNED) || overflow;
>>> +}
>>> +
>>>  /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
>>> { VR1TYPE, VR0MIN, VR0MAX } and store the result
>>> in { *VR0TYPE, *VR0MIN, *VR0MAX }.  This may not be the smallest
>>> @@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
>>>   else if (vrp_val_is_min (vr1min)
>>>&& vrp_val_is_max (vr1max))
>>> ;
>>> + /* Choose the anti-range if it is ~[0,0], that range is special
>>> +enough to special case when vr1's range is relatively wide.
>>> */
>>> + else if (*vr0type == VR_ANTI_RANGE
>>
>>
>> 

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Jeff Law]

On 02/08/2017 05:45 AM, Richard Biener wrote:

On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law  wrote:


This patch addresses issues Richi raised from V1.  Specifically it moves
EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less
aggressively uses ~[0,0] when intersecting ranges -- only doing so when
vr1's range is > 65536 elements.  That number is highly arbitrary.  I'm
certainly open to other values, not sure if a PARAM makes sense or not, but
can certainly do that if folks think it would be useful.  There were other
minor nits Richi pointed out that were fixed too.

Bootstrapped and regression tested as part of the full patch series.

OK for the trunk?


* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range
~[0,0].
(extract_range_from_binary_expr): For MINUS_EXPR with no derived
range,
if the operands are known to be not equal, then the resulting range
is ~[0,0].
(difference_larger_than): New function.
(intersect_ranges): If the new range is ~[0,0] and the old range is
wide, then prefer ~[0,0].

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b429217..ad8173c 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
   if (vr0.type == VR_ANTI_RANGE
   && ranges_from_anti_range (, , ))
 {
+  /* We get imprecise results from ranges_from_anti_range when
+code is EXACT_DIV_EXPR.  We could mask out bits in the resulting
+range, but then we also need to hack up vrp_meet.  It's just
+easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR.  */
+  if (code == EXACT_DIV_EXPR
+ && vr0.type == VR_ANTI_RANGE
+ && vr0.min == vr0.max
+ && integer_zerop (vr0.min))
+   {
+ set_value_range_to_nonnull (vr, expr_type);
+ return;
+   }
+


Please move this before the surrounding if.
Yea.  I wasn't sure about best location.  Before the surrounding IF 
works for me.





   extract_range_from_binary_expr_1 (vr, code, expr_type, ,
vr1_);
   if (vrtem1.type != VR_UNDEFINED)
{
@@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,

   extract_range_from_binary_expr_1 (vr, code, expr_type, _vr0, );
 }
+
+  /* If we didn't derive a range for MINUS_EXPR, and
+ op1's range is ~[op0,op0] or vice-versa, then we
+ can derive a non-null range.  This happens often for
+ pointer subtraction.  */
+  if (vr->type == VR_VARYING
+  && code == MINUS_EXPR
+  && TREE_CODE (op0) == SSA_NAME
+  && ((vr0.type == VR_ANTI_RANGE
+  && symbolic_range_based_on_p (, op1)


Just seeing this again this also covers ~[op1 - 1, op1 - 1] and you are
just lucky because of the vr0.min == vr0.max equality compare and
both op1 - 1 hopefully not tree-shared (I'm not confident in that...).

So I think it would be better written as simply

   && vr0.min == op1

together with vr0.min == vr0.max you'd get what you are after.

You're right.  Fixed.




+  && vr0.min == vr0.max)
+ || (vr1.type == VR_ANTI_RANGE
+ && symbolic_range_based_on_p (, op0)


Likewise of course.

Likewise.




+ && vr1.min == vr1.max)))
+  set_value_range_to_nonnull (vr, TREE_TYPE (op0));
 }

 /* Extract range information from a unary operation CODE based on
@@ -8448,6 +8476,17 @@ give_up:
   *vr0max = NULL_TREE;
 }

+/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT
(HOST_WIDE_INT)
+   or overflows, FALSE otherwise.  */
+
+static bool
+difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
+{
+  bool overflow;
+  wide_int res = wi::sub (max, min, SIGNED, );
+  return wi::gt_p (res, limit, UNSIGNED) || overflow;
+}
+
 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
{ VR1TYPE, VR0MIN, VR0MAX } and store the result
in { *VR0TYPE, *VR0MIN, *VR0MAX }.  This may not be the smallest
@@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
  else if (vrp_val_is_min (vr1min)
   && vrp_val_is_max (vr1max))
;
+ /* Choose the anti-range if it is ~[0,0], that range is special
+enough to special case when vr1's range is relatively wide.  */
+ else if (*vr0type == VR_ANTI_RANGE


That's already known to be true here.

Yes.  Removed.





+  && *vr0min == *vr0max
+  && integer_zerop (*vr0min)
+  && TREE_CODE (vr1max) == INTEGER_CST
+  && TREE_CODE (vr1min) == INTEGER_CST
+  && difference_larger_than (vr1max, vr1min, 65536))
+   ;


in the case that interests us for the PR what is vr1?

[-2305843009213693952, 2305843009213693951]

Jeff

Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Richard Biener]

On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law  wrote:
>
> This patch addresses issues Richi raised from V1.  Specifically it moves
> EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less
> aggressively uses ~[0,0] when intersecting ranges -- only doing so when
> vr1's range is > 65536 elements.  That number is highly arbitrary.  I'm
> certainly open to other values, not sure if a PARAM makes sense or not, but
> can certainly do that if folks think it would be useful.  There were other
> minor nits Richi pointed out that were fixed too.
>
> Bootstrapped and regression tested as part of the full patch series.
>
> OK for the trunk?
>
>
> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
> if the numerator has the range ~[0,0] make the resultant range
> ~[0,0].
> (extract_range_from_binary_expr): For MINUS_EXPR with no derived
> range,
> if the operands are known to be not equal, then the resulting range
> is ~[0,0].
> (difference_larger_than): New function.
> (intersect_ranges): If the new range is ~[0,0] and the old range is
> wide, then prefer ~[0,0].
>
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index b429217..ad8173c 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
>if (vr0.type == VR_ANTI_RANGE
>&& ranges_from_anti_range (, , ))
>  {
> +  /* We get imprecise results from ranges_from_anti_range when
> +code is EXACT_DIV_EXPR.  We could mask out bits in the resulting
> +range, but then we also need to hack up vrp_meet.  It's just
> +easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR.  */
> +  if (code == EXACT_DIV_EXPR
> + && vr0.type == VR_ANTI_RANGE
> + && vr0.min == vr0.max
> + && integer_zerop (vr0.min))
> +   {
> + set_value_range_to_nonnull (vr, expr_type);
> + return;
> +   }
> +

Please move this before the surrounding if.

>extract_range_from_binary_expr_1 (vr, code, expr_type, ,
> vr1_);
>if (vrtem1.type != VR_UNDEFINED)
> {
> @@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,
>
>extract_range_from_binary_expr_1 (vr, code, expr_type, _vr0, );
>  }
> +
> +  /* If we didn't derive a range for MINUS_EXPR, and
> + op1's range is ~[op0,op0] or vice-versa, then we
> + can derive a non-null range.  This happens often for
> + pointer subtraction.  */
> +  if (vr->type == VR_VARYING
> +  && code == MINUS_EXPR
> +  && TREE_CODE (op0) == SSA_NAME
> +  && ((vr0.type == VR_ANTI_RANGE
> +  && symbolic_range_based_on_p (, op1)

Just seeing this again this also covers ~[op1 - 1, op1 - 1] and you are
just lucky because of the vr0.min == vr0.max equality compare and
both op1 - 1 hopefully not tree-shared (I'm not confident in that...).

So I think it would be better written as simply

   && vr0.min == op1

together with vr0.min == vr0.max you'd get what you are after.

> +  && vr0.min == vr0.max)
> + || (vr1.type == VR_ANTI_RANGE
> + && symbolic_range_based_on_p (, op0)

Likewise of course.

> + && vr1.min == vr1.max)))
> +  set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>  }
>
>  /* Extract range information from a unary operation CODE based on
> @@ -8448,6 +8476,17 @@ give_up:
>*vr0max = NULL_TREE;
>  }
>
> +/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT
> (HOST_WIDE_INT)
> +   or overflows, FALSE otherwise.  */
> +
> +static bool
> +difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
> +{
> +  bool overflow;
> +  wide_int res = wi::sub (max, min, SIGNED, );
> +  return wi::gt_p (res, limit, UNSIGNED) || overflow;
> +}
> +
>  /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
> { VR1TYPE, VR0MIN, VR0MAX } and store the result
> in { *VR0TYPE, *VR0MIN, *VR0MAX }.  This may not be the smallest
> @@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
>   else if (vrp_val_is_min (vr1min)
>&& vrp_val_is_max (vr1max))
> ;
> + /* Choose the anti-range if it is ~[0,0], that range is special
> +enough to special case when vr1's range is relatively wide.  */
> + else if (*vr0type == VR_ANTI_RANGE

That's already known to be true here.

> +  && *vr0min == *vr0max
> +  && integer_zerop (*vr0min)
> +  && TREE_CODE (vr1max) == INTEGER_CST
> +  && TREE_CODE (vr1min) == INTEGER_CST
> +  && difference_larger_than (vr1max, vr1min, 65536))
> +   ;

in the case that interests us for the PR what is vr1?

>   /* Else choose the range.  */
>   else
> {
>

[RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2

[Jeff Law]

This patch addresses issues Richi raised from V1.  Specifically it moves 
EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less 
aggressively uses ~[0,0] when intersecting ranges -- only doing so when 
vr1's range is > 65536 elements.  That number is highly arbitrary.  I'm 
certainly open to other values, not sure if a PARAM makes sense or not, 
but can certainly do that if folks think it would be useful.  There were 
other minor nits Richi pointed out that were fixed too.


Bootstrapped and regression tested as part of the full patch series.

OK for the trunk?

* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range ~[0,0].
(extract_range_from_binary_expr): For MINUS_EXPR with no derived range,
if the operands are known to be not equal, then the resulting range
is ~[0,0].
(difference_larger_than): New function.
(intersect_ranges): If the new range is ~[0,0] and the old range is
wide, then prefer ~[0,0].

diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b429217..ad8173c 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
   if (vr0.type == VR_ANTI_RANGE
   && ranges_from_anti_range (, , ))
 {
+  /* We get imprecise results from ranges_from_anti_range when
+code is EXACT_DIV_EXPR.  We could mask out bits in the resulting
+range, but then we also need to hack up vrp_meet.  It's just
+easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR.  */
+  if (code == EXACT_DIV_EXPR
+ && vr0.type == VR_ANTI_RANGE
+ && vr0.min == vr0.max
+ && integer_zerop (vr0.min))
+   {
+ set_value_range_to_nonnull (vr, expr_type);
+ return;
+   }
+
   extract_range_from_binary_expr_1 (vr, code, expr_type, , vr1_);
   if (vrtem1.type != VR_UNDEFINED)
{
@@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,
 
   extract_range_from_binary_expr_1 (vr, code, expr_type, _vr0, );
 }
+
+  /* If we didn't derive a range for MINUS_EXPR, and
+ op1's range is ~[op0,op0] or vice-versa, then we
+ can derive a non-null range.  This happens often for
+ pointer subtraction.  */
+  if (vr->type == VR_VARYING
+  && code == MINUS_EXPR
+  && TREE_CODE (op0) == SSA_NAME
+  && ((vr0.type == VR_ANTI_RANGE
+  && symbolic_range_based_on_p (, op1)
+  && vr0.min == vr0.max)
+ || (vr1.type == VR_ANTI_RANGE
+ && symbolic_range_based_on_p (, op0)
+ && vr1.min == vr1.max)))
+  set_value_range_to_nonnull (vr, TREE_TYPE (op0));
 }
 
 /* Extract range information from a unary operation CODE based on
@@ -8448,6 +8476,17 @@ give_up:
   *vr0max = NULL_TREE;
 }
 
+/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT (HOST_WIDE_INT)
+   or overflows, FALSE otherwise.  */
+
+static bool
+difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
+{
+  bool overflow;
+  wide_int res = wi::sub (max, min, SIGNED, );
+  return wi::gt_p (res, limit, UNSIGNED) || overflow;
+}
+
 /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
{ VR1TYPE, VR0MIN, VR0MAX } and store the result
in { *VR0TYPE, *VR0MIN, *VR0MAX }.  This may not be the smallest
@@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
  else if (vrp_val_is_min (vr1min)
   && vrp_val_is_max (vr1max))
;
+ /* Choose the anti-range if it is ~[0,0], that range is special
+enough to special case when vr1's range is relatively wide.  */
+ else if (*vr0type == VR_ANTI_RANGE
+  && *vr0min == *vr0max
+  && integer_zerop (*vr0min)
+  && TREE_CODE (vr1max) == INTEGER_CST
+  && TREE_CODE (vr1min) == INTEGER_CST
+  && difference_larger_than (vr1max, vr1min, 65536))
+   ;
  /* Else choose the range.  */
  else
{