On Tue, Jul 30, 2019 at 4:54 PM Andrew MacLeod <amacl...@redhat.com> wrote:
>
> On 7/30/19 4:55 AM, Richard Biener wrote:
> > On Fri, Jul 26, 2019 at 4:32 PM Andrew MacLeod <amacl...@redhat.com> wrote:
> >> On 7/25/19 11:37 PM, Jeff Law wrote:
> >>> On 7/24/19 12:33 PM, Richard Biener wrote:
> >>>> On July 24, 2019 8:18:57 PM GMT+02:00, Jeff Law <l...@redhat.com>
> >>>> wrote:
> >>>>> On 7/24/19 11:00 AM, Richard Biener wrote: [ Big snip, ignore
> >>>>> missing reply attributions... ]
> >>>>>
> >>>>>>> it. But I'd claim that if callers are required not to change
> >>>>>>> these ranges, then the callers are fundamentally broken. I'm
> >>>>>>> not sure what the "sanitization" is really buying you here.
> >>>>>>> Can you point to something specific?
> >>>>>>>
> >>>>>>>> But you lose the sanitizing that nobody can change it and the
> >>>>>>>> changed info leaks to other SSA vars.
> >>>>>>>>
> >>>>>>>> As said, fix all callers to deal with NULL.
> >>>>>>>>
> >>>>>>>> But I argue the current code is exactly optimal and safe.
> >>>>>>> ANd I'd argue that it's just plain broken and that the
> >>>>>>> sanitization you're referring to points to something broken
> >>>>>>> elsewhere, higher up in the callers.
> >>>>>> Another option is to make get_value_range return by value and
> >>>>>> the only way to change the lattice to call an appropriate set
> >>>>>> function. I think we already do the latter in all cases (but we
> >>>>>> use get_value_range in the setter) and returning by reference is
> >>>>>> just eliding the copy.
> >>>>> OK, so what I think you're getting at (and please correct me if
> >>>>> I'm wrong) is that once the lattice values are set, you don't want
> >>>>> something changing the recorded ranges underneath?
> >>>>>
> >>>>> ISTM the way to enforce that is to embed the concept in the class
> >>>>> and enforce it by not allowing direct manipulation of range by the
> >>>>> clients. So a client that wants this behavior somehow tells the
> >>>>> class that ranges are "set in stone" and from that point the
> >>>>> setters don't allow changing the underlying ranges.
> >>>> Yes. You'll see that nearly all callers do
> >>>>
> >>>> Value_range vr = *get_value_range (name);
> >>>>
> >>>> Modify
> >>>>
> >>>> Update_value_range (name, &vr) ;
> >>>>
> >>>> And returning by reference was mostly an optimization. We _did_ have
> >>>> callers Changing the range in place and the const varying catched
> >>>> those.
> >>>>
> >>>> When returning by value we can return individual VARYINGs not in the
> >>>> lattice if we decide that's what we want.
> >>>>
> >>>>> I just want to make sure we're on the same page WRT why you think
> >>>>> the constant varying range object is useful.
> >>>> As said it's an optimization. We do not want to reallocate the
> >>>> lattice. And we want lattice updating to happen in a controlled
> >>>> manner, so returning a pointer into the lattice is bad design at this
> >>>> point.
> >>> But I would claim that the current state is dreadful. Consider that
> >>> when gimple-fold asks for a new SSA_NAME, it could get a recycled one,
> >>> in which case we get a real range. Or if it doens't get a recycled
> >>> name, then we get the const varying node. The inconsistently is silly
> >>> when we can just reallocate the underlying object.
> >>>
> >>> Between recycling of SSA_NAMEs and allocating a bit of additional space
> >>> (say rounding up to some reasonable boundary) I'd bet you'd never be
> >>> able to measure the reallocation in practice.
> >>>
> >> I annotated the patch yesterday to actually log reallocations and ran a
> >> couple of bootstraps...
> >>
> >> If we don't add any extra space in the vector initially (as it is
> >> allocated today) , it is re-sized a total of 201 times. Of those, 93
> >> get back the same pointer so no resize actually happens.
> >>
> >> IF we use the patch as I initially propose, where we add 10% to the
> >> vector to start, we re-size 10 times, all from either 18 to 25 , or 8 to
> >> 14,so very small numbers of ssaname functions, where the 10% doesnt
> >> really do much. Those were all re-allocations but one. The initial
> >> resize does seem to help prevent any larger reallocations,
> >>
> >> THat doesn't seem like that bad of a thing over all, and we could tweak
> >> the initial size a bit more if it would help? to deal with the small
> >> cases, we could make it num_names+10%+10 or something even.
> >>
> >> I feel it would be safer.. It seems to me the CONST solution cannot be
> >> disabled.. ie, even a non-checking production compiler would go boom if
> >> it triggered.
> >>
> >> As for addressing the issue that the CONST approach is trying to
> >> resolve, Could we change all the set/update routines to do something like
> >>
> >> gcc_checking_assert (new_range->varying_p () || !values_propagated);
> >>
> >> that way we'll trigger an assert if we try to change any value to
> >> something other than varying when values_propagated is set?
> > I think the constness is appropriately addressed by my recent API update
> > to split the get-value from get-lattice-entry and properly forcing lattice
> > update to go through the few setters.
> >
> > I'm not totally against making the lattice expandable, as the followup
> > patch to the original re-org notices we do run into "new" stmts during
> > the combined analysis/propagation stages the DOM-based users use.
> > And yes, allocating the lattice with some initial head-room is of course
> > the way to go (I'd even just do 2 * num_ssa_names...). Avoiding
> > "useless" allocations of VR_VARYING lattice entries (where a NULL
> > does it just fine) is another optimization. But yeah, we do not
> > "free" lattice entries when they become VR_VARYING and further
> > return the shared const entry (but we could).
> sure, 2 * num_ssa_names is a good start, it'll probably never trigger
> the growth code.
> > That still leaves me with the objection to making VARYING typed.
>
> Even the original author of the code says that is irrelevant. its just a
> choice he made at the time. As I pointed out, in practice you cannot
> disassociate VARYING from the type since a varying char and a varying
> long are not equivalent. So varying only means something in the context
> of an ssa-name or expression, and those must have a type. And it means
> [min, max] for that type.
>
> > IMHO the vr-values.c lattice should look like
> >
> > enum lattice_val { UNDEFINED, CONST, VARYING };
> > struct lattice_entry {
> > lattice_val val;
> > value_range *range;
> > };
> >
> > and we'd have _no_ value_range (NULL) for UNDEFINED and VARYING
> > in the _lattice_. And CONST (aka classical we have a value) would then
> > record a value_range.
> Thats sounds great, and there is nothing preventing you from doing
> that. Then value range can look *exactly* like we want... just a
> range. We're just uniting the current implementation of value-range to
> properly reflect varying and [min,max] for consistency, which it doesn't
> have right now. We can put this code in now, and then if you later get
> to implementing a new view of lattices, its pretty easy to change a few
> places where we called set_varying with a type. That's incredibly
> trivial. Or you could just ignore the type parameter. That would work
> too. Regardless, when you want the range of a varying node, you'll have
> to get the MIN and MAX appropriate for the type of that name, and we'll
> have done that part.
> > That we currently mix lattice state and the value-range types
> > (range, anti-range) is just historical. The CONST lattice state could even
> > be split further, CONST_SCALAR, CONST_RANGE, VARYING and the
> > entry be a union of either value_range * or tree.
> >
> > Richard.
> Everything in this compiler is historical. We did everything we could to
> save memory back in the old days, I know, I was there when we did this.
> Combining the lattice and the range made sense in that context. In
> fact, you could get rid of the lattice structure entirely with the way
> we represent irange... we have varying and undefined values query-able
> from the range without anything special. That seems even more efficient
> to me, and that's the way I'd implement it today... no artificial
> lattice overlay needed, just the range.
>
> Lattices will eventually go away. I personally don't see any point in us
> spinning our wheels re-implementing them when they are slated to be
> removed. Until then, there is absolutely nothing wrong with the way it
> works right now. Adding the min and max to the varying node has no
> impact on how lattices work, it just allows value_range to interact with
> new range code better..
>
> This change is trivial. it actually fixes a few warts. It lets us move
> on with other more significant things.
>
> I've been trying to play nice and get agreement, but after a week and a
> half it seems like that isn't going to happen. I welcome any further
> comments on the patch, but otherwise I will approve the patch.
>
> I will note this is the first time in a very long time that I have had
> to exercise my maintainer authority as one of the original architects of
> tree-ssa. I have been content to let others review and arrive at a
> consensus, but the system is not working this time. Its unclear to me
> why you are being so insistent about this trivial matter. I will
> continue to make approvals as necessary going forward, but I still
> welcome your input and would prefer to settle on agreement to future
> patches.
Fair enough - have fun.
Richard.
> Andrew
