VRP: abstract out POINTER_TYPE_P handling

[Aldy Hernandez]

On 09/04/2018 08:29 AM, Richard Biener wrote:
> On Tue, Sep 4, 2018 at 2:09 PM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 09/04/2018 07:42 AM, Richard Biener wrote:
>>> On Thu, Aug 30, 2018 at 9:39 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>>>
>>>>
>>>>
>>>> On 08/29/2018 12:32 PM, David Malcolm wrote:
>>>>> On Wed, 2018-08-29 at 06:54 -0400, Aldy Hernandez wrote:
>>>>>> Never say never.  Just when I thought I was done...
>>>>>>
>>>>>> It looks like I need the special casing we do for pointer types in
>>>>>> extract_range_from_binary_expr_1.
>>>>>>
>>>>>> The code is simple enough that we could just duplicate it anywhere
>>>>>> we
>>>>>> need it, but I hate code duplication and keeping track of multiple
>>>>>> versions of the same thing.
>>>>>>
>>>>>> No change in functionality.
>>>>>>
>>>>>> Tested on x86-64 Linux with all languages.
>>>>>>
>>>>>> OK?
>>>>>
>>>>> A couple of nits I spotted:
>>>>>
>>>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>>>> index f20730a85ba..228f20b5203 100644
>>>>> --- a/gcc/tree-vrp.c
>>>>> +++ b/gcc/tree-vrp.c
>>>>> @@ -1275,6 +1275,32 @@ set_value_range_with_overflow (value_range &vr,
>>>>>         }
>>>>>     }
>>>>>
>>>>> +/* Value range wrapper for wide_int_range_pointer.  */
>>>>> +
>>>>> +static void
>>>>> +vrp_range_pointer (value_range *vr,
>>>>> +                enum tree_code code, tree type,
>>>>> +                value_range *vr0, value_range *vr1)
>>>>>
>>>>> Looking at the signature of the function, I wondered what the source
>>>>> and destination of the information is...
>>>>
>>>> vr being the destination and vr0/vr1 being the sources are standard
>>>> operating procedure within tree-vrp.c.  All the functions are basically
>>>> that, that's why I haven't bothered.
>>>>
>>>>>
>>>>> Could vr0 and vr1 be const?
>>>>>
>>>>> ...which would require extract_range_into_wide_ints to take a const
>>>>> value_range *
>>>>
>>>> Yes, but that would require changing all of tree-vrp.c to take const
>>>> value_range's.  For instance, range_int_cst_p and a slew of other
>>>> functions throughout.
>>>>
>>>>>
>>>>>      ... which would require range_int_cst_p to take a const value_range *
>>>>>
>>>>> (I *think* that's where the yak-shaving would end)
>>>>>
>>>>> +{
>>>>> +  signop sign = TYPE_SIGN (type);
>>>>> +  unsigned prec = TYPE_PRECISION (type);
>>>>> +  wide_int vr0_min, vr0_max;
>>>>> +  wide_int vr1_min, vr1_max;
>>>>> +
>>>>> +  extract_range_into_wide_ints (vr0, sign, prec, vr0_min, vr0_max);
>>>>> +  extract_range_into_wide_ints (vr1, sign, prec, vr1_min, vr1_max);
>>>>> +  wide_int_range_nullness n;
>>>>> +  n = wide_int_range_pointer (code, sign, vr0_min, vr0_max, vr1_min,
>>>>> vr1_max);
>>>>> +  if (n == WIDE_INT_RANGE_UNKNOWN)
>>>>> +    set_value_range_to_varying (vr);
>>>>> +  else if (n == WIDE_INT_RANGE_NULL)
>>>>> +    set_value_range_to_null (vr, type);
>>>>> +  else if (n == WIDE_INT_RANGE_NONNULL)
>>>>> +    set_value_range_to_nonnull (vr, type);
>>>>> +  else
>>>>> +    gcc_unreachable ();
>>>>> +}
>>>>> +
>>>>>
>>>>> Would it be better to use a "switch (n)" here, rather than a series of
>>>>> "if"/"else if" for each enum value?
>>>>
>>>> I prefer ifs for a small amount of options, but having the compiler warn
>>>> on missing enum alternatives is nice, so I've changed it.  Notice
>>>> there's more code now though :-(.
>>>
>>> I don't like the names *_range_pointer, please change them to sth more
>>> specific like *_range_pointer_binary_op.
>>
>> Sure.
>>
>>>
>>> What's the advantage of "hiding" the resulting ranges behind the
>>> wide_int_range_nullness enum rather than having regular range output?
>>
>> Our upcoming work has another representation for non-nulls in particular
>> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.  I want to share
>> whatever VRP is currently doing for pointers, without having to depend
>> on the internals of vrp (value_range *).
>>
>>> What's the value in separating pointer operations at all in the
>>> wide-int interfaces?  IIRC the difference is that whenever unioning
>>> is required that when it's a pointer result we should possibly
>>> preserve non-nullness.  It's of course also doing less work overall.
>>
>> I don't follow.  What are you suggesting?
> 
> I'm thinking out loud.  Here adding sort-of a "preferencing" to the
> more general handling of the ops would do the same trick, without
> restricting that to "pointers".  For example if a pass would be interested
> in knowing whether a divisor is zero it would also rather preserve
> non-nullness and trade that for precision in other parts of the range,
> say, if you had [-1, -1] [1, +INF] then the smallest unioning result
> is [-1, +INF] but ~[0, 0] is also a valid result which preserves non-zeroness.
> 
> So for wide-int workers I don't believe in tagging sth as pointers.  Rather
> than that ops might get one of
> 
>   enum vr_preference { VR_PREF_SMALL, VR_PREF_NONNULL, VR_PREF_NONNEGATIVE, ... }
> 
> ?

Neat.  I think this is worth exploring, but perhaps something to be 
looked at as a further enhancement?

> 
>>>
>>> So - in the end I'm not convinced that adding this kind of interface
>>> to the wide_int_ variants is worth it and I'd rather keep the existing
>>> VRP code?
>>
>> Again, I don't want to depend on vr_values or VRP in general.
> 
> Sure.  But the general handling of the ops (just treat POINTER_PLUS like PLUS)
> should do range operations just fine.  It's only the preferencing you'd lose
> and that preferencing looks like a more general feature than "lets have this
> function dealing with a small subset of binary ops on pointers"?

Something like MIN/MAX, that is specially handled for binary ops, can't 
be treated with the general min/max range operations.  Take for instance 
MIN(NULL, NON-NULL) which is basically MIN([0], [1..MAX]).  Generic 
range ops would yield 0/NULL, whereas current VRP returns VARYING.

Similarly for BIT_AND_EXPR.  Imagine [1,5] & [10,20] for pointers. 
Handling this generically would yield [0] (NULL), whereas the correct 
answer is NON-NULL.  And yes, [1,5] and [10,20] can actually happen, as 
I've mentioned in another thread.  I think it's libgcc that has code 
that does:

if (some_pointer == (pointer_type *) 1)
else if (some_pointer == (pointer_type *) 2)
etc etc.

Again, I think we could address your preference idea as an enhancement 
if you feel strongly about it.

We could make wide_int_range_pointer an inline function, and the penalty 
for VRP would only be the conversion to wide ints in vrp_range_pointer 
(extract_range_into_wide_ints actually).

> 
> The preferencing above would get passed down to the range unioning code.
> 
> Btw, since your wide-int-range code doesn't even have ANTI_RANGE, how
> do you represent non-zero in the API?

The way god intended of course, with the truth!  As I said earlier:

 >> Our upcoming work has another representation for non-nulls in particular
 >> ([-MIN,-1][1,+MAX]), since we don't have anti ranges.

:-)

> 
> As said, splitting this out in the way of your patch looks "premature",
> there's not enough of the big picture visible for me to say it makes sense.

You could always look at svn/ssa-range :-P.  It's been merged with 
mainline as of early last week.

Splitting this out makes my life a lot easier, with virtually no penalty 
to VRP.  And we could always revisit it later.  But if you feel strongly 
about it, I could inline the pointer handling into our code, and revisit 
this later with you.

Aldy