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

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].

On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law <law@redhat.com> 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 (&vr0, &vrtem0, &vrtem1))
>      {
> +      /* 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, &vrtem0,
> 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, &n_vr0, &vr1);
>      }
> +
> +  /* 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 (&vr0, 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 (&vr1, 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, &overflow);
> +  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
>             {
>

On 02/08/2017 05:45 AM, Richard Biener wrote:
> On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law <law@redhat.com> 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 (&vr0, &vrtem0, &vrtem1))
>>      {
>> +      /* 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, &vrtem0,
>> 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, &n_vr0, &vr1);
>>      }
>> +
>> +  /* 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 (&vr0, 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 (&vr1, 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, &overflow);
>> +  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

On Fri, Feb 10, 2017 at 4:06 AM, Jeff Law <law@redhat.com> wrote:
> On 02/08/2017 05:45 AM, Richard Biener wrote:
>>
>> On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law <law@redhat.com> 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 (&vr0, &vrtem0, &vrtem1))
>>>      {
>>> +      /* 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, &vrtem0,
>>> 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, &n_vr0,
>>> &vr1);
>>>      }
>>> +
>>> +  /* 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 (&vr0, 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 (&vr1, 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, &overflow);
>>> +  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]

Ok, so let's do

          /* Choose the anti-range if it is ~[0,0], that range is special
              for pointer-like operations at least if the vr1's range is
              relatively wide.  This helps catching the fact when
              pointer subtraction results in a known non-zero value.  */
          else if (*vr0min == *vr0max
                     && integer_zerop (*vr0min)
                     && TYPE_PRECISION (TREE_TYPE (*vr0min)) ==
TYPE_PRECISION (ptr_type_node)
                     && TREE_CODE (vr1max) == INTEGER_CST
                     && TREE_CODE (vr1min) == INTEGER_CST
                     && wi::clz (wi::sub (vr1max, vr1min)) <
TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)
             ;

I'm still not 100% convinced this is the correct place to fix this (I
wonder if for the testcase
a carefully crafted match.pd pattern would be enough to simplify the
final != 0 comparison).
But let's defer more work on this to GCC 8 (where we hopefully get a
less stupid range representation
in VRP as well).

Thanks,
Richard.

>
> Jeff

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

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?

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

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<c) with a single range (and where 
it would naturally disappear when we start allowing multiple ranges), or 
do we prefer to put it in the few odd places where we have reason to 
believe that it will help, while the usual strategy (produce [a,d]) 
remains preferable in general? From your patch it seems to be the later 
case, which makes sense.

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<c) with a single range (and
> where it would naturally disappear when we start allowing multiple
> ranges), or do we prefer to put it in the few odd places where we have
> reason to believe that it will help, while the usual strategy (produce
> [a,d]) remains preferable in general? From your patch it seems to be the
> later case, which makes sense.
I suspect we'll still need both.  The code to prefer ~[0,0] when 
intersecting ranges likely needs to stay regardless of other 
improvements we make to EXACT_DIV_EXPR.

This is because we have to produce a wide range, including zero during 
vrp1 and it's only during vrp2 that we can exclude zero.  Thus no matter 
what we do, we end up in intersect_ranges and have to make a guess about 
whether to prefer the wide range of anti-singleton range of ~[0,0].

Jeff

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<c) with a single range (and
>> where it would naturally disappear when we start allowing multiple
>> ranges), or do we prefer to put it in the few odd places where we have
>> reason to believe that it will help, while the usual strategy (produce
>> [a,d]) remains preferable in general? From your patch it seems to be the
>> later case, which makes sense.
> I suspect we'll still need both.  The code to prefer ~[0,0] when intersecting 
> ranges likely needs to stay regardless of other improvements we make to 
> EXACT_DIV_EXPR.
>
> This is because we have to produce a wide range, including zero during vrp1 
> and it's only during vrp2 that we can exclude zero.  Thus no matter what we 
> do, we end up in intersect_ranges and have to make a guess about whether to 
> prefer the wide range of anti-singleton range of ~[0,0].

In the cases where intersect_ranges (with at least one anti-range) ends up 
with a union [a,b]U[c,d] with b+1<c, it could call union_ranges (or they 
could both call the same helper), and we would have all the logic in a 
single place to decide whether we want [a,d] or ~[b+1,c-1]. When we move 
to multiple range components, an interesting place will be the heuristics 
to go down from n components to 3 (or whatever number we pick), trying to 
preserve the largest holes, the hole containing 0 if there is one, the 
holes with numbers of small magnitude, etc.

In my opinion, having the logic in a non-central place like 
extract_range_from_binary_expr_1 makes sense if we want a different 
heuristic for this case than the general case. If the heuristic is 
duplicated in a central place like vrp_intersect, that's probably not the 
case, so I'd favor having the logic in exactly one place.

(I am not asking you to change anything, just discussing some 
possibilities)