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.133.124]) by sourceware.org (Postfix) with ESMTPS id 4B1C23858C74 for ; Thu, 11 Aug 2022 15:11:21 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4B1C23858C74 Received: from mail-oo1-f69.google.com (mail-oo1-f69.google.com [209.85.161.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-532-PySbqt7fMGWpS7HVBdnXAQ-1; Thu, 11 Aug 2022 11:11:19 -0400 X-MC-Unique: PySbqt7fMGWpS7HVBdnXAQ-1 Received: by mail-oo1-f69.google.com with SMTP id d4-20020a4a9cc4000000b0033331e32ee0so8309754ook.20 for ; Thu, 11 Aug 2022 08:11:19 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=9/xJhwk1TWyaQOs2kNQDJC3ioRwOey0jVdoWJDBxAsM=; b=p9RfsQecREHpvazsxujK/kb93AOaFnPJwZTh/N1cH941haDa1HZqZ79fwdpSiDxFpD c0eTwgrB/bH1YrnLpUiF7M5F7Ywx/ObeO+UBloC3pRrddeAn7OQXnAWx4VRFHSnbepT9 zhSkbtNIXB6UIFfFu0cTx4/x7tfQVKT3Fns3Jbp3hopMevMfRnasw9/husYYeHh1KkAq 6QTRX/jcpvvZbx6PBVnEA/76IneImYwbCK/JftgtPyVzaEa7vRkTJtVYydB+f//XpcYr +wHoCKDQZNGTLNW+NkObnHmAttZrAFEVa9FHJi2x5F7YoEDYp4Qw3mcqBbfUPHMfkKKo u0sQ== X-Gm-Message-State: ACgBeo36mRSWSfcdSZzi46qeNP1C3TnuXe7kd3p7I7J9wYNPMkKSgaim +MzlbytXYs0RNXi8oMiyECPkZ9Oc9OJ9ik9Z1+hsxR3LZK1Jlig80RpPCBNrBJG/9QynjJAbb/m BSQ/62NOThubQq8rz3EYbO0VNIVpCy1dq8g== X-Received: by 2002:a05:6808:14cb:b0:343:195e:d587 with SMTP id f11-20020a05680814cb00b00343195ed587mr3731818oiw.265.1660230679177; Thu, 11 Aug 2022 08:11:19 -0700 (PDT) X-Google-Smtp-Source: AA6agR4RgUN5F2xisWYZ5fM5iFfn/u27OrJRDIvIlBpMFguWOSsVqBaKgdhqrFvqQZKmgL240dSzdFMAkd7nAqUrKSc= X-Received: by 2002:a05:6808:14cb:b0:343:195e:d587 with SMTP id f11-20020a05680814cb00b00343195ed587mr3731800oiw.265.1660230678753; Thu, 11 Aug 2022 08:11:18 -0700 (PDT) MIME-Version: 1.0 References: <73820.122081107421800679@us-mta-533.us.mimecast.lan> In-Reply-To: From: Aldy Hernandez Date: Thu, 11 Aug 2022 17:11:07 +0200 Message-ID: Subject: Re: [PATCH] Tame path_range_query::compute_imports To: Andrew MacLeod Cc: Richard Biener , gcc-patches X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-5.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: Thu, 11 Aug 2022 15:11:27 -0000 On Thu, Aug 11, 2022 at 3:59 PM Andrew MacLeod wrote: > > > On 8/11/22 07:42, Richard Biener wrote: > > This avoids going BBs outside of the path when adding def chains > > to the set of imports. It also syncs the code with > > range_def_chain::get_def_chain to not miss out on some imports > > this function would identify. > > > > Bootstrap / regtest pending on x86_64-unknown-linux-gnu. > > > > The question still stands on what the path_range_query::compute_ranges > > actually needs in its m_imports - at least I don't easily see how > > the range-folds will use the path range cache or be path sensitive > > at all. > > All the range folding code is in gimple_range_fold.{h,cc}, and its > driven by the mystical FUR_source classes. fur_source stands for > Fold_Using_Range source, and its basically just an API class which all > the folding routines use to make queries. it is used by all the fold > routines to ask any questions about valueizing relations, ssa name, > etc.. but abstracts the actual source of the information. Its the > distillation from previous incarnations where I use to pass an edge, a > stmt and other stuff to each routine that it might need, and decided to > abstract since it was very unwieldy. The base class requires only a > range_query which is then used for all queries. Note that not only is ranger and path_query a range_query, so is vr_values from legacy land. It all shares the same API. And the simplify_using_ranges class takes a range_query, so it can work with legacy or ranger, or even (untested) the path_query class. > > Then I derive fur_stmt which is instantiated additionally with the stmt > you wish to fold at, and it will perform queries using that stmt as the > context source.. Any requests for ranges/relations/etc will occur as > if that stmt location is the source. If folding a particular stmt, you > use that stmt as the fur_stmt source. This is also how I do > recalculations.. when we see > bb4: > a_32 = f_16 + 10 > <...> > bb88: > if (f_16 < 20) > b_8 = a_32 + 8 > and there is sufficient reason to think that a_32 would have a different > value , we can invoke a re-fold of a_32's defintion stmt at the use > point in b_8.. using that stmt as the fur_source. Ranger will take into > account the range of f_16 being [0,19] at that spot, and recalculate > a_32 as [10,29]. Its expensive to do this at every use point, so we > only do it if we think there is a good reason at this point. > > The point is that the fur_source mechanism is how we provide a context, > and that class talkes care of the details of what the source actually is. > > There are other fur_sources.. fur_edge allows all the same questions to > be answered, but using an edge as the source. Meaning we can calculate > an arbitrary stmt/expressions as if it occurs on an edge. > > There are also a couple of specialized fur_sources.. there is an > internal one in ranger which communicates some other information called > fur_depend which acts like range_of_stmt, but with additional > functionality to register dependencies in GORI as they are seen. This is a really good explanation. I think you should save it and included it in the documentation when you/we get around to writing it ;-). > > Aldy overloads the fur_depend class (called jt_fur_source-- Im not sure > the origination of the name) to work with the values in the path_query > class. You will note that the path_range_query class inherits from a > range_query, so it supports all the range_of_expr, range_of_stmt, and > range_on_edge aspect of rangers API. The name comes from "jump thread" fur_source. I should probably rename that to path_fur_source. Note that even though the full range_query API is available in path_range_query, only range_of_expr and range_of_stmt are supported (or tested). As I mention in the comment for the class: // This class is a basic block path solver. Given a set of BBs // indicating a path through the CFG, range_of_expr and range_of_stmt // will calculate the range of an SSA or STMT as if the BBs in the // path would have been executed in order. So using range_on_edge would probably give unexpected results, using stuff in the cache as it would appear at the end of the path, or some such. We could definitely harden this class and make it work solidly across the entire API, but we've had no uses so far for anything but range_of_expr and range_of_stmt-- and even those are only supported for a range as it would appear at the end of the path. So if you call range_of_expr with a statement anywhere but the end of the path, you're asking for trouble. > > I believe all attempts are first made to pick up the value from the path > cache, and failing that, a query is made from ranger at the start of the > path. So as the walk thru the path happens, and edges are taken/chosen, > all the context information local to the path should be placed into the > path cache, and used in any future queries using the path_range_query. > Ranger will only be invoked if there is no entry in the path query, and > it would provide the range as it would appear at entry to the path. > > Thats my high level understanding of how the path_query class provides > context. That's actually a really good explanation of how it all works (or at least how it's supposed to work ;-)). Thanks. > > So I think to answer the other question, the m_imports list Is probably > the list of ssa-names that may have relevant context information which > the path_query would provide ranges during the walk instead of ranger? > I think Aldy pre-calculates all those during the walk, and then uses > this pre-filled cache to answer questions at the thread exit? Thats my > guess Yeah, though I should probably sit down and do some testing, making sure we're not adding more imports than we need to. Richi has found a whole bunch of imports that ended up in the list that were ultimately not needed. My original comment that adding more imports to the bitmap had no penalty should be nuked-- it obviously has a performance effect, especially for pathological cases. Regarding the name "imports". I think it's confusing all of us, because GORI has a very clear definition of what imports are. OTOH, the path solver starts with the imports from GORI land, but ends up adding more SSA names that would be useful to solve, to provide context as Andrew says. Maybe, we should call the "imports" in the path solver something else to avoid confusion. Interesting names? Must-be-solved? Context-SSA? Suggestions? Aldy