Re: [range-ops] patch 01/04: types for VR_UNDEFINED and VR_VARYING

[Andrew MacLeod <amacleod@redhat.com>]

On 7/24/19 9:25 AM, Richard Biener wrote:
> On Wed, Jul 24, 2019 at 12:56 AM Andrew MacLeod <amacleod@redhat.com> wrote:
>> On 7/23/19 5:33 AM, Richard Biener wrote:
>>
>>>>    From my point of view, a range object is similar to a tree node. A tree
>>>> node has the bits to indicate what the value is, but also associates a
>>>> type with those bits within the same object.  This is less error prone
>>>> than passing around the bits and the type separately.  As ranges are
>>>> starting to be used in many places outside of VRP, we should do the same
>>>> thing with ranges.  WIth value_range it would actually be free since
>>>> there is already a tree for the bounds already which contains the type.
>>> Not for VARYING or UNDEFINED.
>> Personally, Id put it in both for consistency.  I view a range as an
>> object we are associating with either an expression or an ssa-name. That
>> range should then have a consistent type with that name or expression.
>> Even if the range is empty, I would still expect it to be compatible
>> since I'm usually associating it with an ssa_name or expression.
> Imagine you have int i; long l; and you want to ask if both variables
> have the same value range, how would you do that?  What is "same" here?


you would do it exactly the same as you do with value_range today. What 
does adding a type() method which maps to TREE_TYPE (range.min()), which 
also works on VARYING now, have to do with any of this?
We aren't suddenly adding a bunch of restrictions to value_range...

you are arguing about irrelevant things to this patch.   we aren't 
adding a new set of restrictions that don't allow you to do something 
you could do before.


>
>> Because you seem so dead set against it, I can also see some consistency
>> in not having a type for undefined... Since there are 0 ranges, we can't
>> ask for a lower_bound () or upper_bound () on an empty range, so I can
>> see an argument for extending that not being able to ask the type()
>> either.  I agree that this is also a plausible viewpoint, and we are
>> changing our code to make that happen, even though we have to pass a few
>> extra types around and will lose some minor sanity checking when doing
>> intersection or union with an empty range.   To me an empty range is
>> akin to a NaN.. it isn't a real float value, but it does still have a
>> type associated with it.
> Both VARYING and UNDEFINED are currently lattice states, not real
> (integer) ranges.  irange (rightfully so) isn't convering the lattice state
> and the current value_range does so for historical reasons.  In
> principle the VRP lattice could be
>
>    struct { enum lattice_state state; irange *range; };
>
> where for state != VR_[ANTI]RANGE 'range' is NULL.
>
> You shouldn't tie your hands by trying to design something that plugs
> 1:1 into the existing uses.  That constrains you too much IMHO.
>
> Given that we do not represent VARYING as [-INF, +INF] currently
> and you appearantly want to preserve that(?) it should be
> straight-forward to add a irange_from_varying  (type)
> irange_from_undefined (type)
> if you want to get a range for a lattice state VARYING/UNDEFINED.
>

You've read the patch...  of course that is the main change we are 
proposing.
varying == [-INF, +INF] ==  [MIN, MAX]

the patch enforces that if you set the state to varying, it will set the 
endpoints to [MIN, MAX] for that object.
It also enforces that if you set the range to [MIN, MAX], it will also 
change the lattice value to VARYING for you, which doesn't always happen 
today.

And it is disengenuous to suggest that VARYING is typeless.   a varying 
char and a varying long are not equivalent.
If we assign a varying char to an unsigned int, the result is no longer 
varying, we get  a range of [0,255].
By claiming its some magical typeless state, the unsigned int would then 
become varying as well , or [0, 4294967295] which is wrong.

so varying is *not* typeless, and it is always representative of 
something which has a type.

A varying char has a range of [0,255]. We just want to make that 
available in value_range without everyone having to write
   if (r.varying_p())
      lbound = min_for_type (type_passed in);
   else
     lbound = r.min()

everytime they want to look at the lower bound.   The lower bound is now 
just always set.


thats it.  Thats what the patch is about.




>> So we can now normalize that code to not special case varying.. simply
>> ask for lower_bound and upper_bound ().  Its less special casing, its
>> consistent, costs no memory.. It all seems like a really good cleanup
>> which you appear to be opposing for reasons I can't quite fathom.
>>
>>
>>>>
>>> Well, I don't agree.  It's not archaic, it's the way GCC works everywhere
>>> else.  So it's consistent.  Archaically consistend in your view.
>> Are you really arguing we should write code the same way for 30+ years
>> and never change?
> Yes..

That is problematic at best.

>> Indeed, I would argue that when we have the opportunity to modernize
>> code in our code base, we really ought to be doing it... and we don't do
>> it nearly enough.
>>
>> Why don't we just pass a type along with every tree node instead of
>> including it in the node? we'd save memory in each tree node.   I
>> *really* fail to understand this argument of keeping the type separate
>> from the range when the range by definition represents sub-ranges of a
>> specific type.
> Does it?  Only if you consider the narrow view that each range
> comes from an operation on a GIMPLE/GENERIC expression.
>
> But like wide_ints iranges might be used for general range computations
> (see my example above).

again, we are not talking about irange.  we are using value range. In 
trunk.  In our branch.  everywhere.   Back to the patch please.

Not to mention the presence of a 'type' field in the structure has 
absolutely nothing to do with what you can do with irange.  We can 
extract the none-type part into a base class.. and implement it as:

class range_base {
   wide_int [num]
}

class gcc_irange : range_base
{
   tree type;
}

and you can do whatever you want with range_base in a typeless way.


This entire argument line is pointless and  has nothing to do with this 
patch.




>>
>>> that irange storage should not be wide_int but trailing-widest-int.
>>> Because obviously irange has storage requirement.  It makes
>>> in-place modification of iranges impossible but that's the way modern
>>> C++ code works (and be consistent with how wide-int works).
>>>
>>> I don't really like you invented an API unlike any existing in GCC.
>>>
>> I'd say you are kidding, but I'm afraid you aren't.
>>
>> Regardless, we don't need to discuss irange_storage details as we aren't
>> proposing integration of irange, nor irange_storage in the near
>> future... so I don't think the internal details of that prototype matter
>> at this point, only what we are trying to do with value_range.
> Oh, you are not?  Why do we argue changing tree-vrp.c then?

because we are using value_range as the range representation and setting 
the min/max for varying is important.
forget irange.
we may NEVER use irange.
We may instead extend value_range to handle multiple subranges someday.

And we aren't doing that right now either, so lets not comment on that 
either.


>> The API we are proposing here applies only to ranges, and specifically
>> value_range. It is designed to mirror what we do with tree nodes. It is
>> designed to promote ranges to be "just another kind of type" in GCC, one
>> that we could eventually represent with a tree_node if we wanted to. Its
>> really a type which specifies one or more sub-ranges for a type.   As
>> such, it contains values which are expected to be of that type. Thats it.
>>
>> Our value_range type() query is simply extracting TREE_TYPE () from one
>> of the bounds...  its really shorthand for the tree equivalent of
>> TREE_TYPE (TREE_OPERAND (t, 0)) if there were a RANGE_TYPE tree node.
>>
>> If we want to know the bounds for what is referred to as  a varying
>> node  ([MIN, MAX]), you have to have a type available. and if we store
>> min and max, its always there.
>>
>> I still fail to understand why you are so dead set against representing
>> varying as [MIN, MAX].  Its what varying *is*.
> But you are actually _not_ doing that because then you'd not need to
> store the type!  And generally we are only using operands with
> lattice state(!) VARYING for operations that possibly narrow its range
> (as an optimization, saving compile-time).
>

Are you talking about irange again?   we aren't storing a type in 
value_range.

we are merely accessing the type of the minimum range value, and for 
convenience making sure the bounds are also set for varying nodes which 
represents [min, max] for a type..






>> And really, that's the only only fundamental change we are proposing
>> here... And we aren't even adding a field to the structure to do it!
> You are changing a function that essentially sets the lattice state
> from "has a range" to "varying" to need a type.  That's fundamentally
> wrong.


And thats where we disagree.  As I pointed out earlier, varying is not a 
magical typeless state, no matter how much you pretend it is.

"has a range" obviously has a type, I can look at the lower bound and 
see what it is.  Moving it to varying doesn't magically change that.  I 
don't  "need" a type, its right there.  Of course it has a type.  The 
range of that object is now [MIN, MAX], which for convenience of VRP's 
algorithm, also has a lattice value of 'varying'     And that's all 
we're doing is actually setting those MIN/MAX values when it is moved to 
varying. How can that possibly be "fundamentally wrong".   Thats just an 
opinion mired in history because in 2005 Diego didn't bother setting the 
min/max for varying when he wrote it, but he easily could have.

In fact, It prompted me to chat with him about this...  I will quote 
him.  "you can also do VARYING == RANGE[MIN, MAX].    inyour 
is_varying_p() predicate you just return true when the range is [min, 
max].  It's really that simple."

If he had done that in the first place we wouldn't even be having this 
conversation. The change we are proposing has *ZERO* impact on how value 
range is used today (other than fixing some lurking issues).    In every 
single place where set_varying is called, we are setting varying for an 
object which has a type.  We never have to "make up" a type.

I can see no technical argument for why this is not acceptable. 
Everything you have argued has merely been vague opinions along the 
lines of "varying shouldn't have a type, or maybe I want to do this... 
", yet everywhere in the compiler where we use it, it *is* associated 
with a type.

Its an easy patch and this is taking far too long for something so 
trivial. I still can't figure out why its an issue you choose to 
resist.  Quite frankly, the painfulness of this is an example of why it 
is so hard to get people to contribute to gcc.   We really need to 
encourage innovation in our compiler, not stifle it.... or we will be dead.

Andrew