From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTP id E78CF3858C3A for ; Tue, 21 Sep 2021 13:50:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E78CF3858C3A Received: from mail-ot1-f69.google.com (mail-ot1-f69.google.com [209.85.210.69]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-33-0IzJyoNZMRedpEuGoTT_xQ-1; Tue, 21 Sep 2021 09:50:33 -0400 X-MC-Unique: 0IzJyoNZMRedpEuGoTT_xQ-1 Received: by mail-ot1-f69.google.com with SMTP id r14-20020a056830080e00b0053b7b79c0d0so45685202ots.6 for ; Tue, 21 Sep 2021 06:50:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=NtqC31LpbGXHMXiOhvOEUMFjjmLiK6ZALGmgns8o3Gg=; b=yGhpr+DXPMXzmczktzmy/OCYnhKaygE65OK2XzLngNOLIWdmsQZJUGjhdii1cViIKs gNK5LtiTpg31dA4pATDmBRwblHO5etikvDvtBzG6b3ZW2c8neW/p0la2zy/Q/S5/AQNM hzblKtzftwYKxQB9Pl40nct5xL6CEfPvYqY3N2DYmr/kwa8iB0sG/4u2VD121BSLQi30 UYgOwXkWgBkdfc+569QVZlV6c+CSRjIc8hDkzZzbPV+vKnvAu4leVKEk5Ra07kvAoHDH flcy0hwNOmID6kl+ZKfjvUQzwEtd5doKgFErsKEpQe0JLt+zveWaBUzs/MndEDobwKHR vvnQ== X-Gm-Message-State: AOAM533Lx3BYyl+3TnBCW72uUAQJf/00XXID7HSwNqR4FoIb7yZgMgtI QV1Fegqu+CP+yVKu0fYE4N6zCGO2V6EYzQMB1ua+7RIB1m2P2cPckqg6+FumlrttxJ18l4YTIB7 SAvCo9yhmCw1sux+k0gpUQsaMqgdrcOsvTeDQpdjoj2Too5if+rGz77Clg+upcYyA9vWktw== X-Received: by 2002:a9d:4a8d:: with SMTP id i13mr26162402otf.180.1632232232047; Tue, 21 Sep 2021 06:50:32 -0700 (PDT) X-Google-Smtp-Source: ABdhPJzKRgkqnWE7oGPNy2qLOPPMDCNVmcGGnGZPMz0tr/pEd18Gs3X7eGunHB4WoEZXM+XK+2bu/g== X-Received: by 2002:a9d:4a8d:: with SMTP id i13mr26162379otf.180.1632232231693; Tue, 21 Sep 2021 06:50:31 -0700 (PDT) Received: from ?IPv6:2607:fea8:a261:d400::5989? ([2607:fea8:a261:d400::5989]) by smtp.gmail.com with ESMTPSA id k2sm749997oog.5.2021.09.21.06.50.30 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 21 Sep 2021 06:50:31 -0700 (PDT) Subject: Re: [COMMITTED] Use EDGE_EXECUTABLE in ranger and return UNDEFINED for those edges. To: Richard Biener Cc: gcc-patches References: From: Andrew MacLeod Message-ID: <29e973c8-31c9-21af-f078-f73df0c53045@redhat.com> Date: Tue, 21 Sep 2021 09:50:29 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 In-Reply-To: X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-CA X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, NICE_REPLY_A, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_NONE, 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: Tue, 21 Sep 2021 13:50:36 -0000 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. > > I guess I'm confusing something - but yes, clearly in a ranger VRP "pass" > that all sounds OK. > > Richard. >