From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 81734 invoked by alias); 31 Jul 2019 08:37:15 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 81726 invoked by uid 89); 31 Jul 2019 08:37:14 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=arrive, play X-HELO: mail-lf1-f67.google.com Received: from mail-lf1-f67.google.com (HELO mail-lf1-f67.google.com) (209.85.167.67) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 31 Jul 2019 08:37:12 +0000 Received: by mail-lf1-f67.google.com with SMTP id h28so46804169lfj.5 for ; Wed, 31 Jul 2019 01:37:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=fCPwFa74cPmX916lyTx09ZyIuDCWHWc4obUg0lIsS4k=; b=ZqFZxt9RbgD/+olcgCnfSoR7wKsoOrYAvyExBBAKXnigDK08TL77XOLD//0y7nPRUL 6V7QALdRGnTiiSj68+T4RoAGjU7m41KOknFoNKGlKnMviHNZincc0Y6b9c17XVUhz2Cd 5JqRhajj6bFe9DqQJ+qz5xq/aZfJpljTbxQ7fig2a0qg8v/daw6EThaiokqQO4X+0iBQ vKzhotjxYkETf1MK5wKYi5RuDLqwL7DA8T0/RIjz8zoeGtvaP5CHeMDyBoSoi2O5NSxW g+Ui6uqskUZ8uwCzupGFuDgxG2KyMEZ0/veG89pr/vy3coeac9Y7hh7385UGcFtcSFYi aYzA== MIME-Version: 1.0 References: <481033aa-6ecc-3bcb-c874-becee14c5605@redhat.com> <27d3db25-ea95-33f4-57fb-e9a4a40d7341@redhat.com> <1a0a328e-74bb-15cb-40fb-09944fe2b84c@redhat.com> <3ebd8a38-9478-7899-5067-b4cb220d2edf@redhat.com> <828e67b6-d52c-f50d-27bb-46b3734a0493@redhat.com> In-Reply-To: From: Richard Biener Date: Wed, 31 Jul 2019 08:37:00 -0000 Message-ID: Subject: Re: [range-ops] patch 01/04: types for VR_UNDEFINED and VR_VARYING To: Andrew MacLeod Cc: Jeff Law , Aldy Hernandez , gcc-patches Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2019-07/txt/msg01853.txt.bz2 On Tue, Jul 30, 2019 at 4:54 PM Andrew MacLeod wrote: > > On 7/30/19 4:55 AM, Richard Biener wrote: > > On Fri, Jul 26, 2019 at 4:32 PM Andrew MacLeod 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 > >>>> 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