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

This is the first of a 4 part series to address the issues around 79095.

This patch addresses improvements in determining ranges of binary 
expressions in three ways.

First if we are otherwise unable to find a range for the result of a 
MINUS_EXPR, if we know the arguments are not equal, then we know the 
resultant range is ~[0,0].

Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then 
resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is 
rarely a useful range.   A resultant range of ~[0,0] is actually more 
useful since it often tells us something important about the difference 
of two pointers.

Finally, when vrp2 discovers an updated range for an object that had a 
range discovered by vrp1, if the new range is ~[0,0], prefer that new 
range in some cases.  This is needed to avoid losing the newly 
discovered ~[0,0] range for EXACT_DIV_EXPR.

Bootstrapped and regression tested with the other patches in this 
series.  OK for the trunk?

Jeff
* tree-vrp.c (extract_range_from_binary_expr): For EXACT_DIV_EXPR,
	if the numerator has the range ~[0,0] make the resultant range
	~[0,0].  For MINUS_EXPR with no derived range, if the operands are
	known to be not equal, then the resulting range is ~[0,0].
	(intersect_ranges): In some cases prefer ~[0,0].

commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
Author: Jeff Law <law@torsion.usersys.redhat.com>
Date:   Fri Feb 3 15:45:58 2017 -0500

    Improved ranges

Hi Jeff,

On 05/02/17 01:52, Jeff Law wrote:
> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
> +     as a result a ~[0,0] may be better than what has already
> +     been computed.
> +
> +     In particular if numerator has the range ~[0,0], then the
> +     result range is going to be something like
> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
> +
> +     So instead make the result range ~[0,0].  */
> +  if (code == EXACT_DIV_EXPR
> +      && TREE_CODE (op0) == SSA_NAME
> +      && vr0.type == VR_ANTI_RANGE
> +      && vr0.min == vr0.max
> +      && integer_zerop (vr0.min))
> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));

Just wondering if this has to be done only for POINTER_TYPE_P (TREE_TYPE 
(op))? Or is EXACT_DIV_EXPR always of POINTER_TYPE_P?

Thanks,
Kugan

On 02/05/2017 04:06 PM, kugan wrote:
> Hi Jeff,
>
> On 05/02/17 01:52, Jeff Law wrote:
>> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
>> +     as a result a ~[0,0] may be better than what has already
>> +     been computed.
>> +
>> +     In particular if numerator has the range ~[0,0], then the
>> +     result range is going to be something like
>> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
>> +
>> +     So instead make the result range ~[0,0].  */
>> +  if (code == EXACT_DIV_EXPR
>> +      && TREE_CODE (op0) == SSA_NAME
>> +      && vr0.type == VR_ANTI_RANGE
>> +      && vr0.min == vr0.max
>> +      && integer_zerop (vr0.min))
>> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>
> Just wondering if this has to be done only for POINTER_TYPE_P (TREE_TYPE
> (op))? Or is EXACT_DIV_EXPR always of POINTER_TYPE_P?
It can be done regardless of the type -- it just happens that 
EXACT_DIV_EXPR is primarily used on pointer types for pointer subtraction.


jeff

On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
> This is the first of a 4 part series to address the issues around 79095.
>
> This patch addresses improvements in determining ranges of binary
> expressions in three ways.
>
> First if we are otherwise unable to find a range for the result of a
> MINUS_EXPR, if we know the arguments are not equal, then we know the
> resultant range is ~[0,0].
>
> Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
> resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
> rarely a useful range.   A resultant range of ~[0,0] is actually more useful
> since it often tells us something important about the difference of two
> pointers.
>
> Finally, when vrp2 discovers an updated range for an object that had a range
> discovered by vrp1, if the new range is ~[0,0], prefer that new range in
> some cases.  This is needed to avoid losing the newly discovered ~[0,0]
> range for EXACT_DIV_EXPR.
>
> Bootstrapped and regression tested with the other patches in this series.
> OK for the trunk?
>
> Jeff
>
>         * tree-vrp.c (extract_range_from_binary_expr): For EXACT_DIV_EXPR,
>         if the numerator has the range ~[0,0] make the resultant range
>         ~[0,0].  For MINUS_EXPR with no derived range, if the operands are
>         known to be not equal, then the resulting range is ~[0,0].
>         (intersect_ranges): In some cases prefer ~[0,0].
>
> commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
> Author: Jeff Law <law@torsion.usersys.redhat.com>
> Date:   Fri Feb 3 15:45:58 2017 -0500
>
>     Improved ranges
>
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index b429217..3338d8b 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
>
>        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
>      }
> +
> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
> +     as a result a ~[0,0] may be better than what has already
> +     been computed.
> +
> +     In particular if numerator has the range ~[0,0], then the
> +     result range is going to be something like
> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
> +
> +     So instead make the result range ~[0,0].  */
> +  if (code == EXACT_DIV_EXPR
> +      && TREE_CODE (op0) == SSA_NAME
> +      && vr0.type == VR_ANTI_RANGE
> +      && vr0.min == vr0.max
> +      && integer_zerop (vr0.min))
> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));

The above belongs in extract_range_from_binary_expr_1, in principle the
cases below as well (though there's pre-existing VARYING result handling).
The _1 ones are supposed to be the actual range computations while
the routine you patched is responsible for interfacing with a lattice.  The
_1 routines can be used from code outside of VRP.

> +  /* 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)
> +          && vr0.min == vr0.max)
> +         || (vr1.type == VR_ANTI_RANGE
> +             && symbolic_range_based_on_p (&vr1, op0)
> +             && vr1.min == vr1.max)))
> +      set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>  }
>
>  /* Extract range information from a unary operation CODE based on
> @@ -8620,6 +8651,12 @@ 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.  */
> +         else if (*vr0type == VR_ANTI_RANGE
> +                  && *vr0min == *vr0max
> +                  && integer_zerop (*vr0min))
> +           ;

Huh.  If I spotted the place of the change correctly then we cannot arrive
here with vr0 == ~[0,0] as *vr0type is VR_RANGE.  In the case covered
we'd have the only case intersecting [-1, 1] and ~[0,0] that you'd change
to ~[0,0] instead of [-1,1] which generally would be a bad choice (apart
from your implementation error as vr1 is the anti-range here).

Richard.

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

On 02/06/2017 01:11 AM, Richard Biener wrote:
> On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>> This is the first of a 4 part series to address the issues around 79095.
>>
>> This patch addresses improvements in determining ranges of binary
>> expressions in three ways.
>>
>> First if we are otherwise unable to find a range for the result of a
>> MINUS_EXPR, if we know the arguments are not equal, then we know the
>> resultant range is ~[0,0].
>>
>> Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
>> resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
>> rarely a useful range.   A resultant range of ~[0,0] is actually more useful
>> since it often tells us something important about the difference of two
>> pointers.
>>
>> Finally, when vrp2 discovers an updated range for an object that had a range
>> discovered by vrp1, if the new range is ~[0,0], prefer that new range in
>> some cases.  This is needed to avoid losing the newly discovered ~[0,0]
>> range for EXACT_DIV_EXPR.
>>
>> Bootstrapped and regression tested with the other patches in this series.
>> OK for the trunk?
>>
>> Jeff
>>
>>         * tree-vrp.c (extract_range_from_binary_expr): For EXACT_DIV_EXPR,
>>         if the numerator has the range ~[0,0] make the resultant range
>>         ~[0,0].  For MINUS_EXPR with no derived range, if the operands are
>>         known to be not equal, then the resulting range is ~[0,0].
>>         (intersect_ranges): In some cases prefer ~[0,0].
>>
>> commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
>> Author: Jeff Law <law@torsion.usersys.redhat.com>
>> Date:   Fri Feb 3 15:45:58 2017 -0500
>>
>>     Improved ranges
>>
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index b429217..3338d8b 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
>>
>>        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
>>      }
>> +
>> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
>> +     as a result a ~[0,0] may be better than what has already
>> +     been computed.
>> +
>> +     In particular if numerator has the range ~[0,0], then the
>> +     result range is going to be something like
>> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
>> +
>> +     So instead make the result range ~[0,0].  */
>> +  if (code == EXACT_DIV_EXPR
>> +      && TREE_CODE (op0) == SSA_NAME
>> +      && vr0.type == VR_ANTI_RANGE
>> +      && vr0.min == vr0.max
>> +      && integer_zerop (vr0.min))
>> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>
> The above belongs in extract_range_from_binary_expr_1, in principle the
> cases below as well (though there's pre-existing VARYING result handling).
Do you want those existing cases moved, it's easy enough to do.

> The _1 ones are supposed to be the actual range computations while
> the routine you patched is responsible for interfacing with a lattice.  The
> _1 routines can be used from code outside of VRP.
OK.  Good to know.

>>  /* Extract range information from a unary operation CODE based on
>> @@ -8620,6 +8651,12 @@ 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.  */
>> +         else if (*vr0type == VR_ANTI_RANGE
>> +                  && *vr0min == *vr0max
>> +                  && integer_zerop (*vr0min))
>> +           ;
>
> Huh.  If I spotted the place of the change correctly then we cannot arrive
> here with vr0 == ~[0,0] as *vr0type is VR_RANGE.  In the case covered
> we'd have the only case intersecting [-1, 1] and ~[0,0] that you'd change
> to ~[0,0] instead of [-1,1] which generally would be a bad choice (apart
> from your implementation error as vr1 is the anti-range here).
Nope.  It's in the right place.  We have a ~[0,0] for vr0 and vr1 is 
typically going to be [4,4] or [8.8].  Thus we're in this case:

   else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
            && (mineq || operand_less_p (vr1min, *vr0min) == 1))
     {
       /* ( [  ] ) or ([  ] ) or ( [  ]) */

mineq and maxeq are both false.  So neither of these subcases apply:

           /* Choose the right gap if the left is empty.  */
           if (mineq)
[ ... ]
           /* Choose the left gap if the right is empty.  */
           else if (maxeq)

This doesn't apply either:

          /* Choose the anti-range if the range is effectively varying.  */
           else if (vrp_val_is_min (vr1min)
                    && vrp_val_is_max (vr1max))

Even if vr1 is something larger, we're almost never going to derive 
anything useful from vr1 because vr0 is ~[0,0].

On 02/06/2017 08:15 AM, Jeff Law wrote:
> On 02/06/2017 01:11 AM, Richard Biener wrote:
>> On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>>> This is the first of a 4 part series to address the issues around 79095.
>>>
>>> This patch addresses improvements in determining ranges of binary
>>> expressions in three ways.
>>>
>>> First if we are otherwise unable to find a range for the result of a
>>> MINUS_EXPR, if we know the arguments are not equal, then we know the
>>> resultant range is ~[0,0].
>>>
>>> Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
>>> resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
>>> rarely a useful range.   A resultant range of ~[0,0] is actually more
>>> useful
>>> since it often tells us something important about the difference of two
>>> pointers.
>>>
>>> Finally, when vrp2 discovers an updated range for an object that had
>>> a range
>>> discovered by vrp1, if the new range is ~[0,0], prefer that new range in
>>> some cases.  This is needed to avoid losing the newly discovered ~[0,0]
>>> range for EXACT_DIV_EXPR.
>>>
>>> Bootstrapped and regression tested with the other patches in this
>>> series.
>>> OK for the trunk?
>>>
>>> Jeff
>>>
>>>         * tree-vrp.c (extract_range_from_binary_expr): For
>>> EXACT_DIV_EXPR,
>>>         if the numerator has the range ~[0,0] make the resultant range
>>>         ~[0,0].  For MINUS_EXPR with no derived range, if the
>>> operands are
>>>         known to be not equal, then the resulting range is ~[0,0].
>>>         (intersect_ranges): In some cases prefer ~[0,0].
>>>
>>> commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
>>> Author: Jeff Law <law@torsion.usersys.redhat.com>
>>> Date:   Fri Feb 3 15:45:58 2017 -0500
>>>
>>>     Improved ranges
>>>
>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>> index b429217..3338d8b 100644
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
>>>
>>>        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0,
>>> &vr1);
>>>      }
>>> +
>>> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
>>> +     as a result a ~[0,0] may be better than what has already
>>> +     been computed.
>>> +
>>> +     In particular if numerator has the range ~[0,0], then the
>>> +     result range is going to be something like
>>> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
>>> +
>>> +     So instead make the result range ~[0,0].  */
>>> +  if (code == EXACT_DIV_EXPR
>>> +      && TREE_CODE (op0) == SSA_NAME
>>> +      && vr0.type == VR_ANTI_RANGE
>>> +      && vr0.min == vr0.max
>>> +      && integer_zerop (vr0.min))
>>> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>>
>> The above belongs in extract_range_from_binary_expr_1, in principle the
>> cases below as well (though there's pre-existing VARYING result
>> handling).
> Do you want those existing cases moved, it's easy enough to do.
>
>> The _1 ones are supposed to be the actual range computations while
>> the routine you patched is responsible for interfacing with a
>> lattice.  The
>> _1 routines can be used from code outside of VRP.
> OK.  Good to know.
>
>>>  /* Extract range information from a unary operation CODE based on
>>> @@ -8620,6 +8651,12 @@ 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.  */
>>> +         else if (*vr0type == VR_ANTI_RANGE
>>> +                  && *vr0min == *vr0max
>>> +                  && integer_zerop (*vr0min))
>>> +           ;
>>
>> Huh.  If I spotted the place of the change correctly then we cannot
>> arrive
>> here with vr0 == ~[0,0] as *vr0type is VR_RANGE.  In the case covered
>> we'd have the only case intersecting [-1, 1] and ~[0,0] that you'd change
>> to ~[0,0] instead of [-1,1] which generally would be a bad choice (apart
>> from your implementation error as vr1 is the anti-range here).
> Nope.  It's in the right place.  We have a ~[0,0] for vr0 and vr1 is
> typically going to be [4,4] or [8.8].  Thus we're in this case:
Sorry, vr1 is typically going to be some very wide range.  It's the 
range from the prior vrp pass, not the denominator.

jeff

On 02/06/2017 01:11 AM, Richard Biener wrote:
> On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>> This is the first of a 4 part series to address the issues around 79095.
>>
>> This patch addresses improvements in determining ranges of binary
>> expressions in three ways.
>>
>> First if we are otherwise unable to find a range for the result of a
>> MINUS_EXPR, if we know the arguments are not equal, then we know the
>> resultant range is ~[0,0].
>>
>> Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
>> resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
>> rarely a useful range.   A resultant range of ~[0,0] is actually more useful
>> since it often tells us something important about the difference of two
>> pointers.
>>
>> Finally, when vrp2 discovers an updated range for an object that had a range
>> discovered by vrp1, if the new range is ~[0,0], prefer that new range in
>> some cases.  This is needed to avoid losing the newly discovered ~[0,0]
>> range for EXACT_DIV_EXPR.
>>
>> Bootstrapped and regression tested with the other patches in this series.
>> OK for the trunk?
>>
>> Jeff
>>
>>         * tree-vrp.c (extract_range_from_binary_expr): For EXACT_DIV_EXPR,
>>         if the numerator has the range ~[0,0] make the resultant range
>>         ~[0,0].  For MINUS_EXPR with no derived range, if the operands are
>>         known to be not equal, then the resulting range is ~[0,0].
>>         (intersect_ranges): In some cases prefer ~[0,0].
>>
>> commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
>> Author: Jeff Law <law@torsion.usersys.redhat.com>
>> Date:   Fri Feb 3 15:45:58 2017 -0500
>>
>>     Improved ranges
>>
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index b429217..3338d8b 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
>>
>>        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
>>      }
>> +
>> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
>> +     as a result a ~[0,0] may be better than what has already
>> +     been computed.
>> +
>> +     In particular if numerator has the range ~[0,0], then the
>> +     result range is going to be something like
>> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
>> +
>> +     So instead make the result range ~[0,0].  */
>> +  if (code == EXACT_DIV_EXPR
>> +      && TREE_CODE (op0) == SSA_NAME
>> +      && vr0.type == VR_ANTI_RANGE
>> +      && vr0.min == vr0.max
>> +      && integer_zerop (vr0.min))
>> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>
> The above belongs in extract_range_from_binary_expr_1, in principle the
> cases below as well (though there's pre-existing VARYING result handling).
> The _1 ones are supposed to be the actual range computations while
> the routine you patched is responsible for interfacing with a lattice.  The
> _1 routines can be used from code outside of VRP.
So moving the new MINUS_EXPR code or the existing PLUS_EXPR/MINUS_EXPR 
code is easy, but would require passing in op0/op1.  I'm guessing we 
don't want to do that.

We can still move the EXACT_DIV_EXPR case as that doesn't depend on 
looking at the actual operand.

jeff

On Mon, Feb 6, 2017 at 4:18 PM, Jeff Law <law@redhat.com> wrote:
> On 02/06/2017 08:15 AM, Jeff Law wrote:
>>
>> On 02/06/2017 01:11 AM, Richard Biener wrote:
>>>
>>> On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>>>>
>>>> This is the first of a 4 part series to address the issues around 79095.
>>>>
>>>> This patch addresses improvements in determining ranges of binary
>>>> expressions in three ways.
>>>>
>>>> First if we are otherwise unable to find a range for the result of a
>>>> MINUS_EXPR, if we know the arguments are not equal, then we know the
>>>> resultant range is ~[0,0].
>>>>
>>>> Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
>>>> resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
>>>> rarely a useful range.   A resultant range of ~[0,0] is actually more
>>>> useful
>>>> since it often tells us something important about the difference of two
>>>> pointers.
>>>>
>>>> Finally, when vrp2 discovers an updated range for an object that had
>>>> a range
>>>> discovered by vrp1, if the new range is ~[0,0], prefer that new range in
>>>> some cases.  This is needed to avoid losing the newly discovered ~[0,0]
>>>> range for EXACT_DIV_EXPR.
>>>>
>>>> Bootstrapped and regression tested with the other patches in this
>>>> series.
>>>> OK for the trunk?
>>>>
>>>> Jeff
>>>>
>>>>         * tree-vrp.c (extract_range_from_binary_expr): For
>>>> EXACT_DIV_EXPR,
>>>>         if the numerator has the range ~[0,0] make the resultant range
>>>>         ~[0,0].  For MINUS_EXPR with no derived range, if the
>>>> operands are
>>>>         known to be not equal, then the resulting range is ~[0,0].
>>>>         (intersect_ranges): In some cases prefer ~[0,0].
>>>>
>>>> commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
>>>> Author: Jeff Law <law@torsion.usersys.redhat.com>
>>>> Date:   Fri Feb 3 15:45:58 2017 -0500
>>>>
>>>>     Improved ranges
>>>>
>>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>>> index b429217..3338d8b 100644
>>>> --- a/gcc/tree-vrp.c
>>>> +++ b/gcc/tree-vrp.c
>>>> @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
>>>>
>>>>        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0,
>>>> &vr1);
>>>>      }
>>>> +
>>>> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
>>>> +     as a result a ~[0,0] may be better than what has already
>>>> +     been computed.
>>>> +
>>>> +     In particular if numerator has the range ~[0,0], then the
>>>> +     result range is going to be something like
>>>> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
>>>> +
>>>> +     So instead make the result range ~[0,0].  */
>>>> +  if (code == EXACT_DIV_EXPR
>>>> +      && TREE_CODE (op0) == SSA_NAME
>>>> +      && vr0.type == VR_ANTI_RANGE
>>>> +      && vr0.min == vr0.max
>>>> +      && integer_zerop (vr0.min))
>>>> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>>>
>>>
>>> The above belongs in extract_range_from_binary_expr_1, in principle the
>>> cases below as well (though there's pre-existing VARYING result
>>> handling).
>>
>> Do you want those existing cases moved, it's easy enough to do.
>>
>>> The _1 ones are supposed to be the actual range computations while
>>> the routine you patched is responsible for interfacing with a
>>> lattice.  The
>>> _1 routines can be used from code outside of VRP.
>>
>> OK.  Good to know.
>>
>>>>  /* Extract range information from a unary operation CODE based on
>>>> @@ -8620,6 +8651,12 @@ 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.  */
>>>> +         else if (*vr0type == VR_ANTI_RANGE
>>>> +                  && *vr0min == *vr0max
>>>> +                  && integer_zerop (*vr0min))
>>>> +           ;
>>>
>>>
>>> Huh.  If I spotted the place of the change correctly then we cannot
>>> arrive
>>> here with vr0 == ~[0,0] as *vr0type is VR_RANGE.  In the case covered
>>> we'd have the only case intersecting [-1, 1] and ~[0,0] that you'd change
>>> to ~[0,0] instead of [-1,1] which generally would be a bad choice (apart
>>> from your implementation error as vr1 is the anti-range here).
>>
>> Nope.  It's in the right place.  We have a ~[0,0] for vr0 and vr1 is
>> typically going to be [4,4] or [8.8].  Thus we're in this case:

I matched the above hunk to the following context:

  else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
           && (mineq || operand_less_p (vr1min, *vr0min) == 1))
    {
      /* ( [  ] ) or ([  ] ) or ( [  ]) */
      if (*vr0type == VR_RANGE
          && vr1type == VR_RANGE)
        /* Choose the inner range.  */
        ;
      else if (*vr0type == VR_ANTI_RANGE
               && vr1type == VR_RANGE)
        {
...
          /* Choose the anti-range if the range is effectively varying.  */
          else if (vrp_val_is_min (vr1min)
                   && vrp_val_is_max (vr1max))
            ;
          /* Else choose the range.  */
          else
            {
              *vr0type = vr1type;
              *vr0min = vr1min;
              *vr0max = vr1max;
            }
        }

ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case
of a range with an anti-range "inside".  This also covers [-1,1] v ~[0,0]
where you choose the much larger anti-range now.  So at least we
want to have some idea about the sizes of the ranges (ideally we'd
choose the smaller though for most further propagations anti-ranges
often degenerate to varying...)

> Sorry, vr1 is typically going to be some very wide range.  It's the range
> from the prior vrp pass, not the denominator.
>
> jeff
>

On Mon, Feb 6, 2017 at 4:28 PM, Jeff Law <law@redhat.com> wrote:
> On 02/06/2017 01:11 AM, Richard Biener wrote:
>>
>> On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>>>
>>> This is the first of a 4 part series to address the issues around 79095.
>>>
>>> This patch addresses improvements in determining ranges of binary
>>> expressions in three ways.
>>>
>>> First if we are otherwise unable to find a range for the result of a
>>> MINUS_EXPR, if we know the arguments are not equal, then we know the
>>> resultant range is ~[0,0].
>>>
>>> Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
>>> resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
>>> rarely a useful range.   A resultant range of ~[0,0] is actually more
>>> useful
>>> since it often tells us something important about the difference of two
>>> pointers.
>>>
>>> Finally, when vrp2 discovers an updated range for an object that had a
>>> range
>>> discovered by vrp1, if the new range is ~[0,0], prefer that new range in
>>> some cases.  This is needed to avoid losing the newly discovered ~[0,0]
>>> range for EXACT_DIV_EXPR.
>>>
>>> Bootstrapped and regression tested with the other patches in this series.
>>> OK for the trunk?
>>>
>>> Jeff
>>>
>>>         * tree-vrp.c (extract_range_from_binary_expr): For
>>> EXACT_DIV_EXPR,
>>>         if the numerator has the range ~[0,0] make the resultant range
>>>         ~[0,0].  For MINUS_EXPR with no derived range, if the operands
>>> are
>>>         known to be not equal, then the resulting range is ~[0,0].
>>>         (intersect_ranges): In some cases prefer ~[0,0].
>>>
>>> commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
>>> Author: Jeff Law <law@torsion.usersys.redhat.com>
>>> Date:   Fri Feb 3 15:45:58 2017 -0500
>>>
>>>     Improved ranges
>>>
>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>> index b429217..3338d8b 100644
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
>>>
>>>        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0,
>>> &vr1);
>>>      }
>>> +
>>> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
>>> +     as a result a ~[0,0] may be better than what has already
>>> +     been computed.
>>> +
>>> +     In particular if numerator has the range ~[0,0], then the
>>> +     result range is going to be something like
>>> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
>>> +
>>> +     So instead make the result range ~[0,0].  */
>>> +  if (code == EXACT_DIV_EXPR
>>> +      && TREE_CODE (op0) == SSA_NAME
>>> +      && vr0.type == VR_ANTI_RANGE
>>> +      && vr0.min == vr0.max
>>> +      && integer_zerop (vr0.min))
>>> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>>
>>
>> The above belongs in extract_range_from_binary_expr_1, in principle the
>> cases below as well (though there's pre-existing VARYING result handling).
>> The _1 ones are supposed to be the actual range computations while
>> the routine you patched is responsible for interfacing with a lattice.
>> The
>> _1 routines can be used from code outside of VRP.
>
> So moving the new MINUS_EXPR code or the existing PLUS_EXPR/MINUS_EXPR code
> is easy, but would require passing in op0/op1.  I'm guessing we don't want
> to do that.
>
> We can still move the EXACT_DIV_EXPR case as that doesn't depend on looking
> at the actual operand.

Yes please.

Richard.

> jeff
>

On 02/06/2017 08:33 AM, Richard Biener wrote:
> On Mon, Feb 6, 2017 at 4:18 PM, Jeff Law <law@redhat.com> wrote:
>> On 02/06/2017 08:15 AM, Jeff Law wrote:
>>>
>>> On 02/06/2017 01:11 AM, Richard Biener wrote:
>>>>
>>>> On Sat, Feb 4, 2017 at 3:52 PM, Jeff Law <law@redhat.com> wrote:
>>>>>
>>>>> This is the first of a 4 part series to address the issues around 79095.
>>>>>
>>>>> This patch addresses improvements in determining ranges of binary
>>>>> expressions in three ways.
>>>>>
>>>>> First if we are otherwise unable to find a range for the result of a
>>>>> MINUS_EXPR, if we know the arguments are not equal, then we know the
>>>>> resultant range is ~[0,0].
>>>>>
>>>>> Second, for EXACT_DIV_EXPR, if the numerator has the range ~[0,0], then
>>>>> resultant range is currently [TYPE_MIN/DENOM,TYPE_MAX/DENOM].  That is
>>>>> rarely a useful range.   A resultant range of ~[0,0] is actually more
>>>>> useful
>>>>> since it often tells us something important about the difference of two
>>>>> pointers.
>>>>>
>>>>> Finally, when vrp2 discovers an updated range for an object that had
>>>>> a range
>>>>> discovered by vrp1, if the new range is ~[0,0], prefer that new range in
>>>>> some cases.  This is needed to avoid losing the newly discovered ~[0,0]
>>>>> range for EXACT_DIV_EXPR.
>>>>>
>>>>> Bootstrapped and regression tested with the other patches in this
>>>>> series.
>>>>> OK for the trunk?
>>>>>
>>>>> Jeff
>>>>>
>>>>>         * tree-vrp.c (extract_range_from_binary_expr): For
>>>>> EXACT_DIV_EXPR,
>>>>>         if the numerator has the range ~[0,0] make the resultant range
>>>>>         ~[0,0].  For MINUS_EXPR with no derived range, if the
>>>>> operands are
>>>>>         known to be not equal, then the resulting range is ~[0,0].
>>>>>         (intersect_ranges): In some cases prefer ~[0,0].
>>>>>
>>>>> commit b7baf46ab62e28d2dbc22e9dcd4404926d59df18
>>>>> Author: Jeff Law <law@torsion.usersys.redhat.com>
>>>>> Date:   Fri Feb 3 15:45:58 2017 -0500
>>>>>
>>>>>     Improved ranges
>>>>>
>>>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>>>> index b429217..3338d8b 100644
>>>>> --- a/gcc/tree-vrp.c
>>>>> +++ b/gcc/tree-vrp.c
>>>>> @@ -3298,6 +3298,37 @@ extract_range_from_binary_expr (value_range *vr,
>>>>>
>>>>>        extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0,
>>>>> &vr1);
>>>>>      }
>>>>> +
>>>>> +  /* EXACT_DIV_EXPR is typically used for pointer subtraction;
>>>>> +     as a result a ~[0,0] may be better than what has already
>>>>> +     been computed.
>>>>> +
>>>>> +     In particular if numerator has the range ~[0,0], then the
>>>>> +     result range is going to be something like
>>>>> +     [MININT/DIVISOR,MAXINT/DIVISOR], which is rarely useful.
>>>>> +
>>>>> +     So instead make the result range ~[0,0].  */
>>>>> +  if (code == EXACT_DIV_EXPR
>>>>> +      && TREE_CODE (op0) == SSA_NAME
>>>>> +      && vr0.type == VR_ANTI_RANGE
>>>>> +      && vr0.min == vr0.max
>>>>> +      && integer_zerop (vr0.min))
>>>>> +    set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>>>>
>>>>
>>>> The above belongs in extract_range_from_binary_expr_1, in principle the
>>>> cases below as well (though there's pre-existing VARYING result
>>>> handling).
>>>
>>> Do you want those existing cases moved, it's easy enough to do.
>>>
>>>> The _1 ones are supposed to be the actual range computations while
>>>> the routine you patched is responsible for interfacing with a
>>>> lattice.  The
>>>> _1 routines can be used from code outside of VRP.
>>>
>>> OK.  Good to know.
>>>
>>>>>  /* Extract range information from a unary operation CODE based on
>>>>> @@ -8620,6 +8651,12 @@ 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.  */
>>>>> +         else if (*vr0type == VR_ANTI_RANGE
>>>>> +                  && *vr0min == *vr0max
>>>>> +                  && integer_zerop (*vr0min))
>>>>> +           ;
>>>>
>>>>
>>>> Huh.  If I spotted the place of the change correctly then we cannot
>>>> arrive
>>>> here with vr0 == ~[0,0] as *vr0type is VR_RANGE.  In the case covered
>>>> we'd have the only case intersecting [-1, 1] and ~[0,0] that you'd change
>>>> to ~[0,0] instead of [-1,1] which generally would be a bad choice (apart
>>>> from your implementation error as vr1 is the anti-range here).
>>>
>>> Nope.  It's in the right place.  We have a ~[0,0] for vr0 and vr1 is
>>> typically going to be [4,4] or [8.8].  Thus we're in this case:
>
> I matched the above hunk to the following context:
>
>   else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
>            && (mineq || operand_less_p (vr1min, *vr0min) == 1))
>     {
>       /* ( [  ] ) or ([  ] ) or ( [  ]) */
>       if (*vr0type == VR_RANGE
>           && vr1type == VR_RANGE)
>         /* Choose the inner range.  */
>         ;
>       else if (*vr0type == VR_ANTI_RANGE
>                && vr1type == VR_RANGE)
>         {
> ...
>           /* Choose the anti-range if the range is effectively varying.  */
>           else if (vrp_val_is_min (vr1min)
>                    && vrp_val_is_max (vr1max))
>             ;
>           /* Else choose the range.  */
>           else
>             {
>               *vr0type = vr1type;
>               *vr0min = vr1min;
>               *vr0max = vr1max;
>             }
>         }
>
> ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case
> of a range with an anti-range "inside".  This also covers [-1,1] v ~[0,0]
> where you choose the much larger anti-range now.  So at least we
> want to have some idea about the sizes of the ranges (ideally we'd
> choose the smaller though for most further propagations anti-ranges
> often degenerate to varying...)
Hmm, let me do some refining on that hunk.

What's kind of interesting here is that the wider range ~[0,0] is 
sometimes more useful, but we may not have enough context here to know 
when that's true.  Making guesses based on the size of vr1 may be the 
best we can do.

Jeff

On 02/06/2017 08:33 AM, Richard Biener wrote:

> ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case
> of a range with an anti-range "inside".  This also covers [-1,1] v ~[0,0]
> where you choose the much larger anti-range now.  So at least we
> want to have some idea about the sizes of the ranges (ideally we'd
> choose the smaller though for most further propagations anti-ranges
> often degenerate to varying...)
vr0 as an anti-singleton range like ~[0,0] is the only one likely of any 
interest right now and that's always going to have a range that is all 
but one value :-)

vr1 is the tricky case.  We could do v1.max - vr1.min and if that 
overflows or is some "large" value (say > 65536 just to throw out a 
value), then we conclude creating the singleton anti-range like ~[0,0] 
is more useful.

Jeff

On Mon, Feb 6, 2017 at 10:57 PM, Jeff Law <law@redhat.com> wrote:
> On 02/06/2017 08:33 AM, Richard Biener wrote:
>
>> ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case
>> of a range with an anti-range "inside".  This also covers [-1,1] v ~[0,0]
>> where you choose the much larger anti-range now.  So at least we
>> want to have some idea about the sizes of the ranges (ideally we'd
>> choose the smaller though for most further propagations anti-ranges
>> often degenerate to varying...)
>
> vr0 as an anti-singleton range like ~[0,0] is the only one likely of any
> interest right now and that's always going to have a range that is all but
> one value :-)
>
> vr1 is the tricky case.  We could do v1.max - vr1.min and if that overflows
> or is some "large" value (say > 65536 just to throw out a value), then we
> conclude creating the singleton anti-range like ~[0,0] is more useful.

Yes, but it's hard to tell.  As said, anti-ranges quickly degrade in
further propagation
and I fear that without a better range representation it's hard to do better in
all cases here.  The fact is we can't represent the result of the
intersection and
thus we have to conservatively choose an approximation.  Sometimes we have
the other range on an SSA name and thus can use equivalences (when coming
from assert processing), but most of the time not and thus we can't use
equivalences (which use SSA name versions rather than an index into a
ranges array - one possible improvement to the range representation).
Iff ~[0,0]
is useful information querying sth for non-null should also look at equivalences
btw.

Richard.

> Jeff

On 02/07/2017 01:39 AM, Richard Biener wrote:
> On Mon, Feb 6, 2017 at 10:57 PM, Jeff Law <law@redhat.com> wrote:
>> On 02/06/2017 08:33 AM, Richard Biener wrote:
>>
>>> ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case of a
>>> range with an anti-range "inside".  This also covers [-1,1] v
>>> ~[0,0] where you choose the much larger anti-range now.  So at
>>> least we want to have some idea about the sizes of the ranges
>>> (ideally we'd choose the smaller though for most further
>>> propagations anti-ranges often degenerate to varying...)
>>
>> vr0 as an anti-singleton range like ~[0,0] is the only one likely
>> of any interest right now and that's always going to have a range
>> that is all but one value :-)
>>
>> vr1 is the tricky case.  We could do v1.max - vr1.min and if that
>> overflows or is some "large" value (say > 65536 just to throw out a
>> value), then we conclude creating the singleton anti-range like
>> ~[0,0] is more useful.
>
> Yes, but it's hard to tell.  As said, anti-ranges quickly degrade in
> further propagation and I fear that without a better range
> representation it's hard to do better in all cases here.
All very true.  What I threw into testing overnight was the >65536 
heuristic.   While I don't expect we're going to see any testing 
failures, I also suspect we don't have a lot of cases where wide ranges 
are all that useful and even less testsuite coverage of those cases.

One more targeted approach would be to *wipe* the old range when it is 
wide and we discover ~[0,0] as a new range.  We could do this just for 
EXACT_DIV_EXPR.  We'd do this much earlier than vrp_intersect so that 
we'd still have enough context to know we're dealing with 
EXACT_DIV_EXPR.  It's obviously much less likely to have side effects, 
but feels even more like a hack to me.

*If* we come up with something useful, it might suggest a different 
approach to even discovering the ~[0,0] case for EXACT_DIV_EXPR.  Part 
of the problem is we have a numerator of ~[0,0].  We covert that into 
[MININT,-1] U [1,MAXINT]  Then apply the denominator's range to both 
generating [MININT/4,0] U [0, MAXINT/4], which we convert to 
[MININT/4,MAXINT/4]

But the initial conversion of the numerator's range is imprecise for 
EXACT_DIV_EXPR.  If we mask out the low order bits at conversion time we 
end up generating the (reasonable) [MININT/4,-1] U [1,MAXINT/4].  Then 
we union those together into [MININT/4,MAXINT/4], but if we had a good 
heuristic we might be able to realize ~[0,0] is better.



  The fact is
> we can't represent the result of the intersection and thus we have to
> conservatively choose an approximation.
Right.  There's no way apriori to absolutely know which range 
representation is better.  Though we have some sense that a wide range 
is not generally useful (for some definition of wide) and a singleton 
anti-range sometimes has value (because it can be used to propagate 
simple equivalences).  We could approximate the latter by looking at 
uses of the SSA_NAME and guess which of those would benefit from the 
propagation enabled by a singleton anti-range.  That sounds painful though.


  Sometimes we have the other
> range on an SSA name and thus can use equivalences (when coming from
> assert processing), but most of the time not and thus we can't use
> equivalences (which use SSA name versions rather than an index into
> a ranges array - one possible improvement to the range
> representation).
Right.

  Iff ~[0,0] is useful information querying sth for
> non-null should also look at equivalences btw.
~[0,0] is primarily useful in pointer contexts -- null pointer check 
elimination and pointer arithmetic.  Outside those contexts I doubt it 
has all that much value.

Sadly, I don't think we can rely on types either -- IIRC everything is 
casted to a generic integer type, so we can't key on ptrdiff_t.

Jeff

On Tue, Feb 7, 2017 at 7:34 PM, Jeff Law <law@redhat.com> wrote:
> On 02/07/2017 01:39 AM, Richard Biener wrote:
>>
>> On Mon, Feb 6, 2017 at 10:57 PM, Jeff Law <law@redhat.com> wrote:
>>>
>>> On 02/06/2017 08:33 AM, Richard Biener wrote:
>>>
>>>> ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case of a
>>>> range with an anti-range "inside".  This also covers [-1,1] v
>>>> ~[0,0] where you choose the much larger anti-range now.  So at
>>>> least we want to have some idea about the sizes of the ranges
>>>> (ideally we'd choose the smaller though for most further
>>>> propagations anti-ranges often degenerate to varying...)
>>>
>>>
>>> vr0 as an anti-singleton range like ~[0,0] is the only one likely
>>> of any interest right now and that's always going to have a range
>>> that is all but one value :-)
>>>
>>> vr1 is the tricky case.  We could do v1.max - vr1.min and if that
>>> overflows or is some "large" value (say > 65536 just to throw out a
>>> value), then we conclude creating the singleton anti-range like
>>> ~[0,0] is more useful.
>>
>>
>> Yes, but it's hard to tell.  As said, anti-ranges quickly degrade in
>> further propagation and I fear that without a better range
>> representation it's hard to do better in all cases here.
>
> All very true.  What I threw into testing overnight was the >65536
> heuristic.   While I don't expect we're going to see any testing failures, I
> also suspect we don't have a lot of cases where wide ranges are all that
> useful and even less testsuite coverage of those cases.
>
> One more targeted approach would be to *wipe* the old range when it is wide
> and we discover ~[0,0] as a new range.  We could do this just for
> EXACT_DIV_EXPR.  We'd do this much earlier than vrp_intersect so that we'd
> still have enough context to know we're dealing with EXACT_DIV_EXPR.  It's
> obviously much less likely to have side effects, but feels even more like a
> hack to me.
>
> *If* we come up with something useful, it might suggest a different approach
> to even discovering the ~[0,0] case for EXACT_DIV_EXPR.  Part of the problem
> is we have a numerator of ~[0,0].  We covert that into [MININT,-1] U
> [1,MAXINT]  Then apply the denominator's range to both generating
> [MININT/4,0] U [0, MAXINT/4], which we convert to [MININT/4,MAXINT/4]
>
> But the initial conversion of the numerator's range is imprecise for
> EXACT_DIV_EXPR.  If we mask out the low order bits at conversion time we end
> up generating the (reasonable) [MININT/4,-1] U [1,MAXINT/4].  Then we union
> those together into [MININT/4,MAXINT/4], but if we had a good heuristic we
> might be able to realize ~[0,0] is better.
>
>
>
>  The fact is
>>
>> we can't represent the result of the intersection and thus we have to
>> conservatively choose an approximation.
>
> Right.  There's no way apriori to absolutely know which range representation
> is better.  Though we have some sense that a wide range is not generally
> useful (for some definition of wide) and a singleton anti-range sometimes
> has value (because it can be used to propagate simple equivalences).  We
> could approximate the latter by looking at uses of the SSA_NAME and guess
> which of those would benefit from the propagation enabled by a singleton
> anti-range.  That sounds painful though.
>
>
>  Sometimes we have the other
>>
>> range on an SSA name and thus can use equivalences (when coming from
>> assert processing), but most of the time not and thus we can't use
>> equivalences (which use SSA name versions rather than an index into
>> a ranges array - one possible improvement to the range
>> representation).
>
> Right.
>
>  Iff ~[0,0] is useful information querying sth for
>>
>> non-null should also look at equivalences btw.
>
> ~[0,0] is primarily useful in pointer contexts -- null pointer check
> elimination and pointer arithmetic.  Outside those contexts I doubt it has
> all that much value.
>
> Sadly, I don't think we can rely on types either -- IIRC everything is
> casted to a generic integer type, so we can't key on ptrdiff_t.

Bah.

Add a nonnull_p flag to value_range ...

/me runs...

Honestly, the way to go is ditch VR_ANTI_RANGE and make value_range be

// template <unsigned N>
struct GTY(()) value_range
{
  enum value_range_type type;
  // The value range is the union of [ min[0], max[0] ], [ min[1], max[1] ] ...
  tree min[N];
  tree max[N];
  bitmap equiv;
};

or better use a sub-struct for the individual sub-ranges (and maybe a vec so
that the actual N is variable and we just impose an upper limit somewhere).

for the moment with fixed N == 2.  Then we can represent [MIN/4, 1] U [MAX/4, 1]
exactly.

Btw, there's always much talk about that mysterious VRP improvements by Andrew.
I hope he doesn't mind if his work gets torn apart during hypothetical
review which
usually happens if you develop stuff somewhere hidden in a dark
corner...  and yes,
I didn't want to duplicate any work and thus I refrained from doing
the above kind of
refactorings at the end of stage1.

Richard.


> Jeff
>

On 02/08/2017 05:53 AM, Richard Biener wrote:
>
> Bah.
>
> Add a nonnull_p flag to value_range ...
>
> /me runs...
>
> Honestly, the way to go is ditch VR_ANTI_RANGE and make value_range be
>
> // template <unsigned N>
> struct GTY(()) value_range
> {
>   enum value_range_type type;
>   // The value range is the union of [ min[0], max[0] ], [ min[1], max[1] ] ...
>   tree min[N];
>   tree max[N];
>   bitmap equiv;
> };
>
> or better use a sub-struct for the individual sub-ranges (and maybe a vec so
> that the actual N is variable and we just impose an upper limit somewhere).
Agreed.  Seems like a gcc-8 thing though.


>
> for the moment with fixed N == 2.  Then we can represent [MIN/4, 1] U [MAX/4, 1]
> exactly.
And probably other important cases as well.  But I suspect there's 
little to be gained beyond N == 2.

>
> Btw, there's always much talk about that mysterious VRP improvements by Andrew.
> I hope he doesn't mind if his work gets torn apart during hypothetical
> review which
> usually happens if you develop stuff somewhere hidden in a dark
> corner...  and yes,
> I didn't want to duplicate any work and thus I refrained from doing
> the above kind of
> refactorings at the end of stage1.
Yea.  I've been trying to steer him away from that methodology  :-) He 
won't mind the work being torn apart.  We'll actually be talking about 
its state next week..

I think his work is largely outside VRP right now, so if you want to go 
forward with refactorings, I'd say go for it without worrying abou 
tAndrew's work.  Odds are there won't be a lot of overlap.  I'm happy to 
drag Andrew onto a call where the three of us can your refactoring plans 
and Andrew's plans around to see where there's overlap.


jeff

On 02/07/2017 01:39 AM, Richard Biener wrote:
> On Mon, Feb 6, 2017 at 10:57 PM, Jeff Law <law@redhat.com> wrote:
>> On 02/06/2017 08:33 AM, Richard Biener wrote:
>>
>>> ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case of a
>>> range with an anti-range "inside".  This also covers [-1,1] v
>>> ~[0,0] where you choose the much larger anti-range now.  So at
>>> least we want to have some idea about the sizes of the ranges
>>> (ideally we'd choose the smaller though for most further
>>> propagations anti-ranges often degenerate to varying...)
>>
>> vr0 as an anti-singleton range like ~[0,0] is the only one likely
>> of any interest right now and that's always going to have a range
>> that is all but one value :-)
>>
>> vr1 is the tricky case.  We could do v1.max - vr1.min and if that
>> overflows or is some "large" value (say > 65536 just to throw out a
>> value), then we conclude creating the singleton anti-range like
>> ~[0,0] is more useful.
>
> Yes, but it's hard to tell.  As said, anti-ranges quickly degrade in
> further propagation and I fear that without a better range
> representation it's hard to do better in all cases here.  The fact is
> we can't represent the result of the intersection and thus we have to
> conservatively choose an approximation.  Sometimes we have the other
> range on an SSA name and thus can use equivalences (when coming from
> assert processing), but most of the time not and thus we can't use
> equivalences (which use SSA name versions rather than an index into
> a ranges array - one possible improvement to the range
> representation). Iff ~[0,0] is useful information querying sth for
> non-null should also look at equivalences btw.
I spoke with Andrew a bit today, he's consistently seeing cases where 
the union of 3 ranges is necessary to resolve the kinds of queries we're 
interested in.  He's made a design decision not to use anti-ranges in 
his work, so y'all are in sync on that long term.

He and Aldy have some bits to change the underlying range representation 
that might make sense to hash through right after stage1 reopens.

Jeff

On Tue, Feb 14, 2017 at 12:19 AM, Jeff Law <law@redhat.com> wrote:
> On 02/07/2017 01:39 AM, Richard Biener wrote:
>>
>> On Mon, Feb 6, 2017 at 10:57 PM, Jeff Law <law@redhat.com> wrote:
>>>
>>> On 02/06/2017 08:33 AM, Richard Biener wrote:
>>>
>>>> ah, indeed vr0type is VR_ANTI_RANGE and yes we have the case of a
>>>> range with an anti-range "inside".  This also covers [-1,1] v
>>>> ~[0,0] where you choose the much larger anti-range now.  So at
>>>> least we want to have some idea about the sizes of the ranges
>>>> (ideally we'd choose the smaller though for most further
>>>> propagations anti-ranges often degenerate to varying...)
>>>
>>>
>>> vr0 as an anti-singleton range like ~[0,0] is the only one likely
>>> of any interest right now and that's always going to have a range
>>> that is all but one value :-)
>>>
>>> vr1 is the tricky case.  We could do v1.max - vr1.min and if that
>>> overflows or is some "large" value (say > 65536 just to throw out a
>>> value), then we conclude creating the singleton anti-range like
>>> ~[0,0] is more useful.
>>
>>
>> Yes, but it's hard to tell.  As said, anti-ranges quickly degrade in
>> further propagation and I fear that without a better range
>> representation it's hard to do better in all cases here.  The fact is
>> we can't represent the result of the intersection and thus we have to
>> conservatively choose an approximation.  Sometimes we have the other
>> range on an SSA name and thus can use equivalences (when coming from
>> assert processing), but most of the time not and thus we can't use
>> equivalences (which use SSA name versions rather than an index into
>> a ranges array - one possible improvement to the range
>> representation). Iff ~[0,0] is useful information querying sth for
>> non-null should also look at equivalences btw.
>
> I spoke with Andrew a bit today, he's consistently seeing cases where the
> union of 3 ranges is necessary to resolve the kinds of queries we're
> interested in.  He's made a design decision not to use anti-ranges in his
> work, so y'all are in sync on that long term.

Ok.  I'd also not hard-code the number of union ranges but make the code
agnostic.  Still the actual implementation might take a #define / template param
for an upper bound.

> He and Aldy have some bits to change the underlying range representation
> that might make sense to hash through right after stage1 reopens.

Good.

> Jeff

On 02/14/2017 01:58 AM, Richard Biener wrote:
>>
>> I spoke with Andrew a bit today, he's consistently seeing cases where the
>> union of 3 ranges is necessary to resolve the kinds of queries we're
>> interested in.  He's made a design decision not to use anti-ranges in his
>> work, so y'all are in sync on that long term.
>
> Ok.  I'd also not hard-code the number of union ranges but make the code
> agnostic.  Still the actual implementation might take a #define / template param
> for an upper bound.
Andrew was in-sync on not hard-coding the number of ranges either -- 
essentially he's considering the possibility that consumers might want 
different levels of detail and thus a different number of recorded union 
ranges.

I'm not 100% sure that level of engineering is needed, but a design 
which accounts for that inherently avoids hard-coding the upper bound.

Jeff

On Tue, Feb 14, 2017 at 10:41 PM, Jeff Law <law@redhat.com> wrote:
> On 02/14/2017 01:58 AM, Richard Biener wrote:
>>>
>>>
>>> I spoke with Andrew a bit today, he's consistently seeing cases where the
>>> union of 3 ranges is necessary to resolve the kinds of queries we're
>>> interested in.  He's made a design decision not to use anti-ranges in his
>>> work, so y'all are in sync on that long term.
>>
>>
>> Ok.  I'd also not hard-code the number of union ranges but make the code
>> agnostic.  Still the actual implementation might take a #define / template
>> param
>> for an upper bound.
>
> Andrew was in-sync on not hard-coding the number of ranges either --
> essentially he's considering the possibility that consumers might want
> different levels of detail and thus a different number of recorded union
> ranges.
>
> I'm not 100% sure that level of engineering is needed, but a design which
> accounts for that inherently avoids hard-coding the upper bound.

Yeah.  And then there's (independently) SSA_NAME_RANGE_INFO
which needs a memory-compact representation which means it might
make sense to retain anti-ranges for that and use at most one range/anti-range.

Richard.

> Jeff