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

[Richard Biener <richard dot guenther at gmail dot com>]

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