From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x536.google.com (mail-ed1-x536.google.com [IPv6:2a00:1450:4864:20::536]) by sourceware.org (Postfix) with ESMTPS id F0D403858D39 for ; Wed, 22 Sep 2021 08:25:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F0D403858D39 Received: by mail-ed1-x536.google.com with SMTP id c21so7018336edj.0 for ; Wed, 22 Sep 2021 01:25:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=pi8ZlcMw3MzLJlQrJq8fegmDZR+OSJpA3gSSoWKysIU=; b=bm/E3kycyLOJmSZ+Z1DeZ5axeq+9h4Ekgdsbh/KrhGKimTiHVZOWr3YLApNFJe3MwW VlGKF/tF5MLo6vhZp9UhmqhTn2WpLFR2x0axnimkk82guq2JyotkPSMYSdQZ5K/covq7 vAGdGMR/wR/cHW64xManw6o6H065wz4pxX+O97VLlphovyj790QFW4cIqLQdtaFVVFR6 txnGemNVi/8k9zcIfgMHqHRuGve5PBWDAm6ZETAsPYggSWcbNl1ARM9bBHJwd1K1O4CB erF2/aisuu7XAeJPBBeCjBocESRU0SjQQ2u3LXJnhOV80cUUskBu2XugeE78hkQ73vWd jOcQ== X-Gm-Message-State: AOAM531/jRWu8EscOMbKZi8cfZnCB/Ow/+15bm0sSywmEdrny62DiZSo poZ+btS6YP+9QieBEYZUpf69N+5QGPOhgKb3eFQ= X-Google-Smtp-Source: ABdhPJzLcOP+/ABqPAjeBZEGuLe/IrlVFK7wk42nM/sC8JXzbP431+POKvPSs5vIFVO5VBBzSU1um2ER/YMkVIami4s= X-Received: by 2002:a17:906:584:: with SMTP id 4mr39538893ejn.56.1632299119759; Wed, 22 Sep 2021 01:25:19 -0700 (PDT) MIME-Version: 1.0 References: <29e973c8-31c9-21af-f078-f73df0c53045@redhat.com> In-Reply-To: <29e973c8-31c9-21af-f078-f73df0c53045@redhat.com> From: Richard Biener Date: Wed, 22 Sep 2021 10:25:08 +0200 Message-ID: Subject: Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges. To: Andrew MacLeod Cc: gcc-patches Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 22 Sep 2021 08:25:23 -0000 On Tue, Sep 21, 2021 at 3:50 PM Andrew MacLeod wrote: > > On 9/21/21 9:32 AM, Richard Biener wrote: > > On Tue, Sep 21, 2021 at 2:57 PM Andrew MacLeod wrote: > >> On 9/21/21 2:14 AM, Richard Biener wrote: > >>> On Tue, Sep 21, 2021 at 8:09 AM Richard Biener > >>> wrote: > >>>> On Tue, Sep 21, 2021 at 12:01 AM Andrew MacLeod via Gcc-patches > >>>> wrote: > >>>>> The patch sets the EXECUTABLE property on edges like VRP does, and then > >>>>> removes that flag when an edge is determined to be un-executable. > >>>>> > >>>>> This information is then used to return UNDEFINED for any requests on > >>>>> un-executable edges, and to register equivalencies if all executable > >>>>> edges of a PHI node are the same SSA_NAME. > >>>>> > >>>>> This catches up a number of the cases VRP gets that ranger was missing, > >>>>> and reduces the EVRP discrepancies to almost 0. > >>>>> > >>>>> On a side note, is there any interest/value in reversing the meaning of > >>>>> that flag? It seems to me that we could assume edges are EXECUTABLE by > >>>>> default, then set a NON_EXECUTABLE flag when a pass determines the edge > >>>>> cannot be executed. This would rpevent a number fo passes from having > >>>>> to loop through all the edges and set the EXECUTABLE property... It > >>>>> just seems backwards to me. > >>>> The flag is simply not kept up-to-date and it's the passes responsibility to > >>>> make use of it (aka install a default state upon entry). > >>>> > >>>> To me not having EDGE_EXECUTABLE set on entry is more natural > >>>> for optimistic propagation passes, but yes, if you do on-demand greedy > >>>> processing then you need a conservative default. But then how do you > >>>> denote a 'VARYING' (executable) state that may not drop back to 'CONSTANT" > >>>> (not executable)? For optimistic propagation EDGE_EXECUTABLE set is > >>>> simply the varying state and since we never clear it again there's no chance > >>>> of oscillation. > >> Different model, we dont have a lattice whereby we track state and move > >> form one to another.. we just track currently best known values for > >> everything and recalculate them when the old values are stale. We move > >> the edge to unexecutable when those values allow us to rewrite a branch > >> such that an edge can no longer be taken. everything else is executable. > >> Any values on an unexecutable edge are then considered UNDEFINED when > >> combined with other values.. > >> > >>> Btw, I fail to see how the patch makes ranger assure a sane initial state of > >>> EDGE_EXECUTABLE (or make its use conditional). Is the code you patched > >>> not also used on-demand? > >> THe constructor for a ranger makes everything executable to start. > >> Calls the same routine VRP does. > >> > >> gimple_ranger::gimple_ranger () : tracer ("") > >> { > >> @@ -41,6 +42,7 @@ gimple_ranger::gimple_ranger () : tracer ("") > >> m_oracle = m_cache.oracle (); > >> if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE)) > >> tracer.enable_trace (); > >> + set_all_edges_as_executable (cfun); > >> } > > Ah, I see. I had the impression that with ranger we can now > > do a cheap query everywhere on the range of an SSA name. But then > > the above is O(CFG size)... > > One of the reasons I'd like to see it persistent :-) We could > alternatively add another new one, something like EDGE_NEVER_EXECUTED > which is cleared by default when created and only ranger/other > interested passes utilize it and it is kept persistent. Just seems > more appropriate to "fix" the current flag. I took a quick look at that, > but it seemed like one or more of the propagation passes may use the > flag for other nefarious purposes. It would require fixing everyone to > maintain the value properly. > > Queries are still "cheap", but there are varying amounts of lookups > and allocations that are done. If the lack of a persistent EXECUTABLE > edge flag continues, I may make some further tweaks and make it > sensitive to whether EXECUTABLE is to be looked at or not and perhaps > only have the VRPs initiate that. I prefer avoiding different modes > when possible tho. > > Currently most/all uses of ranger are instantiated and used for the > duration of a pass, so the O(cfg) is pretty minimal with all the CFG > traversing and caching required. Btw, there's auto_edge_flag (fun) that gets you a new flag allocated and it's supposed to be cleared on all edges (but I don't think we actually verify that - I suppose we should). The downside is you have to clear it after use - but it would in theory be possible to elide that by keeping a set of "dirty" flags and only clear all of those when we run out of non-dirty free flags. Richard. > > > > > I guess I'm confusing something - but yes, clearly in a ranger VRP "pass" > > that all sounds OK. > > > > Richard. > > >