This is the mail archive of the gcc-patches@gcc.gnu.org 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/30/19 4:55 AM, Richard Biener wrote:

On Fri, Jul 26, 2019 at 4:32 PM Andrew MacLeod <amacleod@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 <law@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. 

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