This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

On 7/24/19 9:25 AM, Richard Biener wrote:
On Wed, Jul 24, 2019 at 12:56 AM Andrew MacLeod <> 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.
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);
    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?

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

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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]