This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR
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
>