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 26EB43858C74 for ; Thu, 11 Aug 2022 13:59:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 26EB43858C74 Received: from mail-io1-f69.google.com (mail-io1-f69.google.com [209.85.166.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_128_GCM_SHA256) id us-mta-138-pEgzY8agPKaIKsmjI4rFVw-1; Thu, 11 Aug 2022 09:59:50 -0400 X-MC-Unique: pEgzY8agPKaIKsmjI4rFVw-1 Received: by mail-io1-f69.google.com with SMTP id q20-20020a6bd214000000b00680799e0fbaso9683703iob.16 for ; Thu, 11 Aug 2022 06:59:47 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc; bh=vEID7FsDFuuYiH1476YyQK+x3oa0TaCK1P9GtyXATjQ=; b=k+b+54KaJKNWuknnjYdAKAQuFGMM2iRL57s8CYNoDOnEuRJwWrE+gq6wdyk/tFbQe0 UFkzpjXldHCgsmz3KD/FQhS850uxlQvx+R/asrCSFUtrz/eerKoGd9nrNOJH7UrGvYZQ E1/RoVBNSUcYJkK31YAAFCO9HGMNCXTCYzkiW8DEYqofng+vmIaCqwbIROmCj43EMDeY IJiRJUtQ1QDPZgPgVv64REpVF/QhSIbm5CP1JLXVHv1YOV4Bql3f2JRR43/mcveOZD9+ hUIQCOeZc2cRzIbwJYm8x+5lQxEqtA3gsnySQLNHvdVwEY/AjoD/SQy3zwG679YOdHun Fpsg== X-Gm-Message-State: ACgBeo0kP8vSRxoENx+w9DtEPYCqw4DTA3xYtpdpgcCU5lA+WE3cOkcM kP4w6pKQ0ZD+yHTD1N/a4GlB2h0j8z7jgeO/cJvOYydilhI4YMzLmBBL8rmAxzsjbufHREVmlEM DAxg/hkHS8AvpGDd77g== X-Received: by 2002:a05:6e02:1a48:b0:2df:443:fe1a with SMTP id u8-20020a056e021a4800b002df0443fe1amr15814345ilv.264.1660226384080; Thu, 11 Aug 2022 06:59:44 -0700 (PDT) X-Google-Smtp-Source: AA6agR7Gi3/8NcciZE/kUCwv+1au2d6nXWy4gK6XufCYMnB43pflJkksf9Zszcsh+/7UfIFzEnD3eg== X-Received: by 2002:a05:6e02:1a48:b0:2df:443:fe1a with SMTP id u8-20020a056e021a4800b002df0443fe1amr15814331ilv.264.1660226383751; Thu, 11 Aug 2022 06:59:43 -0700 (PDT) Received: from [192.168.0.135] ([192.24.49.145]) by smtp.gmail.com with ESMTPSA id p10-20020a92da4a000000b002dd0cf02f42sm3320179ilq.44.2022.08.11.06.59.42 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 11 Aug 2022 06:59:43 -0700 (PDT) Message-ID: Date: Thu, 11 Aug 2022 09:59:43 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: Re: [PATCH] Tame path_range_query::compute_imports To: Richard Biener , gcc-patches@gcc.gnu.org References: <73820.122081107421800679@us-mta-533.us.mimecast.lan> From: Andrew MacLeod In-Reply-To: <73820.122081107421800679@us-mta-533.us.mimecast.lan> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, 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 13:59:56 -0000 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. 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. 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. 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. 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 > K? > > Thanks, > Richard. > > * gimple-range-path.cc (path_range_query::compute_imports): > Restrict walking SSA defs to blocks inside the path. Track > the same operands as range_def_chain::get_def_chain does. > --- > gcc/gimple-range-path.cc | 39 ++++++++++++++++++++++++++++----------- > 1 file changed, 28 insertions(+), 11 deletions(-) > > diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc > index 5ae374df3a2..5ff2c733b4e 100644 > --- a/gcc/gimple-range-path.cc > +++ b/gcc/gimple-range-path.cc > @@ -575,18 +575,11 @@ path_range_query::compute_imports (bitmap imports, const vec &path) > { > tree name = worklist.pop (); > gimple *def_stmt = SSA_NAME_DEF_STMT (name); > + if (SSA_NAME_IS_DEFAULT_DEF (name) > + || !path.contains (gimple_bb (def_stmt))) > + continue; > > - if (is_gimple_assign (def_stmt)) > - { > - add_to_imports (gimple_assign_rhs1 (def_stmt), imports); > - tree rhs = gimple_assign_rhs2 (def_stmt); > - if (rhs && add_to_imports (rhs, imports)) > - worklist.safe_push (rhs); > - rhs = gimple_assign_rhs3 (def_stmt); > - if (rhs && add_to_imports (rhs, imports)) > - worklist.safe_push (rhs); > - } > - else if (gphi *phi = dyn_cast (def_stmt)) > + if (gphi *phi = dyn_cast (def_stmt)) > { > for (size_t i = 0; i < gimple_phi_num_args (phi); ++i) > { > @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec &path) > worklist.safe_push (arg); > } > } > + else if (gassign *ass = dyn_cast (def_stmt)) > + { > + tree ssa[3]; > + if (range_op_handler (ass)) > + { > + ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass)); > + ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass)); > + ssa[2] = NULL_TREE; > + } > + else if (gimple_assign_rhs_code (ass) == COND_EXPR) > + { > + ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass)); > + ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass)); > + ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass)); > + } > + else > + continue; > + for (unsigned j = 0; j < 3; ++j) > + { > + tree rhs = ssa[j]; > + if (rhs && add_to_imports (rhs, imports)) > + worklist.safe_push (rhs); > + } > + } > } > // Exported booleans along the path, may help conditionals. > if (m_resolve)