From patchwork Wed Apr 26 19:26:00 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1774241 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=AO74ickK; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Q684f4fW1z23vF for ; Thu, 27 Apr 2023 05:26:42 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 16EFE38555BF for ; Wed, 26 Apr 2023 19:26:39 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 16EFE38555BF DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682537199; bh=4EouVqwk98Mj0TBp06rMh8JPtLSs3a4y7BQ+rAlIa80=; h=Date:Subject:To:Cc:References:In-Reply-To:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=AO74ickKh072olhV3N9tpt/uuivdA5MUy+zZ+Eh8fJamR6K9ud7omoCc5FWyrwzoU T9UpD/UhU+3war4lvmzD0H6PCP+18EpveL9nUdSuUq9wxisOGRAiJtLAJPD+kTuDrU R/CgtXfuJcCyE3koJZflBH96aPtkiIlJpAPzigtc= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 D49FD3857713 for ; Wed, 26 Apr 2023 19:26:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org D49FD3857713 Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-468-dhbwCJI0M4abHOC1ESWtpw-1; Wed, 26 Apr 2023 15:26:02 -0400 X-MC-Unique: dhbwCJI0M4abHOC1ESWtpw-1 Received: by mail-qk1-f197.google.com with SMTP id af79cd13be357-74e1cdf9cbeso79850185a.0 for ; Wed, 26 Apr 2023 12:26:02 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682537162; x=1685129162; h=in-reply-to:from:references:cc:to:content-language:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=GGjrow1PCm7fRjMpnPpUyrcLfEnDUXFdIawVQxy15Tc=; b=NXGe41ZDzqTxU9qGkvAbrjaoSEZfaGW0xa+596PUuFH3dgye8lDInYp+EooBmyMX46 IWWQNzmkIcgkG2mG/yCxNTx63fnxd6VbBEv1LgXnV8CZEt+24YARgrdHIlGNDZoj8dey igo9B8Y483gZjsUIyxLR/ByWpxCbXtZKRxumpXxq8Afzg5S3s7YPkB999oYe0DEmDj8A +8lAIlotNUMRvQPOQVv7U1zjsrdLsZLdtxzHRH0LLcb4sWTrO2ySvIEQrWlTZVjFZPal oKDAsr7F5udjNyUn5UBEutMKr8WLw6ykHWJtwL5xvakbWTPKmlGzyJlbIE+hSMUYaDkt EhyA== X-Gm-Message-State: AC+VfDwDwckz1hd/v+4fWEY4dM5bfyv7S0CkWXhJbfs36Un3JoUjWGbg rJ/MJArf5z+3I9ycfEKy1eQjAw/h7wq1QBzQ2LIUzFikaB+8oqhTdK2nYjp9QDDE5cyEAfRKiPK bn/YReyYKfO5+0zVFXQ== X-Received: by 2002:ac8:5b95:0:b0:3f0:a108:8642 with SMTP id a21-20020ac85b95000000b003f0a1088642mr5676333qta.20.1682537162279; Wed, 26 Apr 2023 12:26:02 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ73cogplJZXrIu1mMxJhQHsrcfTnFdZPRxJSCc9H5JVxYg4XB/Qy+7uvdBOveGPf50W7ccQ4A== X-Received: by 2002:ac8:5b95:0:b0:3f0:a108:8642 with SMTP id a21-20020ac85b95000000b003f0a1088642mr5676310qta.20.1682537162012; Wed, 26 Apr 2023 12:26:02 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::1dcd? ([2607:fea8:51df:4200::1dcd]) by smtp.gmail.com with ESMTPSA id r16-20020ac85e90000000b003ef189ffa82sm5541208qtx.90.2023.04.26.12.26.01 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 26 Apr 2023 12:26:01 -0700 (PDT) Message-ID: Date: Wed, 26 Apr 2023 15:26:00 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 Subject: [COMMITTED 1/5] PR tree-optimization/109417 - Don't save ssa-name pointer in dependency cache. To: Jeff Law , Richard Biener Cc: gcc-patches@gcc.gnu.org, "hernandez, aldy" References: <428a4619-9653-ff0b-8092-25efc933ba80@gmail.com> <9c61bac0-b3ae-98e6-8abf-5a092db98f64@redhat.com> <6116962e-f273-2d5a-93ff-2408dc4a4cea@gmail.com> In-Reply-To: <6116962e-f273-2d5a-93ff-2408dc4a4cea@gmail.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" On 4/25/23 22:34, Jeff Law wrote: > > > On 4/24/23 07:51, Andrew MacLeod wrote: > >> >> Its not a real cache..  its merely a statement shortcut in dependency >> analysis to avoid re-parsing statements every time we look at them >> for dependency analysis >> >> It is not suppose to be used for anything other than dependency >> checking.   ie, if an SSA_NAME changes, we can check if it matches >> either of the 2 "cached" names on this DEF, and if so, we know this >> name is stale.  we are never actually suppose to use the dependency >> cached values to drive anything, merely respond to the question if >> either matches a given name.   So it doesnt matter if the name here >> has been freed > OK.  I'll take your word for it.  Note that a free'd SSA_NAME may have > an empty TREE_TYPE or an unexpected TREE_CHAIN field IIRC. So you have > to be a bit careful if you're going to allow them. > >> >> >>> We never re-use SSA names from within the pass releasing it.  But if >>> the ranger cache >>> persists across passes this could be a problem.  See >> >> >> This particular valueswould never persist beyond a current pass.. its >> just the dependency chains and they would get rebuilt every time >> because the IL has changed. > Good.  THat would limit the concerns significantly.  I don't think we > recycle names within a pass anymore (we used to within DOM due to the > way threading worked eons ago, but we no longer take things out of SSA > form to handle the CFG/SSA graph updates.  One could even argue we > don't need to maintain the freelist and recycle names anymore. > > Jeff > well, no worries.  taken care of thusly for the future. Its a hair slower, but nothing outrageous Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From a530eb642032da7ad4d30de51131421631055f72 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 25 Apr 2023 15:33:52 -0400 Subject: [PATCH 1/5] Don't save ssa-name pointer in dependency cache. If the direct dependence fields point directly to an ssa-name, its possible that an optimization frees an ssa-name, and the value pointed to may now be in the free list. Simply maintain the ssa version number instead. PR tree-optimization/109417 * gimple-range-gori.cc (range_def_chain::register_dependency): Save the ssa version number, not the pointer. (gori_compute::may_recompute_p): No need to check if a dependency is in the free list. * gimple-range-gori.h (class range_def_chain): Change ssa1 and ssa2 fields to be unsigned int instead of trees. (ange_def_chain::depend1): Adjust. (ange_def_chain::depend2): Adjust. * gimple-range.h: Include "ssa.h" to inline ssa_name(). --- gcc/gimple-range-gori.cc | 8 ++++---- gcc/gimple-range-gori.h | 14 ++++++++++---- gcc/gimple-range.h | 1 + 3 files changed, 15 insertions(+), 8 deletions(-) diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index d77e1f51ac2..5bba77c7b7b 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -182,9 +182,9 @@ range_def_chain::register_dependency (tree name, tree dep, basic_block bb) // Set the direct dependency cache entries. if (!src.ssa1) - src.ssa1 = dep; - else if (!src.ssa2 && src.ssa1 != dep) - src.ssa2 = dep; + src.ssa1 = SSA_NAME_VERSION (dep); + else if (!src.ssa2 && src.ssa1 != SSA_NAME_VERSION (dep)) + src.ssa2 = SSA_NAME_VERSION (dep); // Don't calculate imports or export/dep chains if BB is not provided. // This is usually the case for when the temporal cache wants the direct @@ -1316,7 +1316,7 @@ gori_compute::may_recompute_p (tree name, basic_block bb, int depth) // If the first dependency is not set, there is no recomputation. // Dependencies reflect original IL, not current state. Check if the // SSA_NAME is still valid as well. - if (!dep1 || SSA_NAME_IN_FREE_LIST (dep1)) + if (!dep1) return false; // Don't recalculate PHIs or statements with side_effects. diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h index 3ea4b45595b..526edc24b53 100644 --- a/gcc/gimple-range-gori.h +++ b/gcc/gimple-range-gori.h @@ -46,8 +46,8 @@ protected: bitmap_obstack m_bitmaps; private: struct rdc { - tree ssa1; // First direct dependency - tree ssa2; // Second direct dependency + unsigned int ssa1; // First direct dependency + unsigned int ssa2; // Second direct dependency bitmap bm; // All dependencies bitmap m_import; }; @@ -66,7 +66,10 @@ range_def_chain::depend1 (tree name) const unsigned v = SSA_NAME_VERSION (name); if (v >= m_def_chain.length ()) return NULL_TREE; - return m_def_chain[v].ssa1; + unsigned v1 = m_def_chain[v].ssa1; + if (!v1) + return NULL_TREE; + return ssa_name (v1); } // Return the second direct dependency for NAME, if there is one. @@ -77,7 +80,10 @@ range_def_chain::depend2 (tree name) const unsigned v = SSA_NAME_VERSION (name); if (v >= m_def_chain.length ()) return NULL_TREE; - return m_def_chain[v].ssa2; + unsigned v2 = m_def_chain[v].ssa2; + if (!v2) + return NULL_TREE; + return ssa_name (v2); } // GORI_MAP is used to accumulate what SSA names in a block can diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 7ed4d3870b8..b8ddca59d2d 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -22,6 +22,7 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_GIMPLE_RANGE_H #define GCC_GIMPLE_RANGE_H +#include "ssa.h" #include "range.h" #include "value-query.h" #include "gimple-range-op.h" -- 2.39.2 From patchwork Wed Apr 26 19:26:21 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1774242 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=d/uCdwOC; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Q684m57zWz23vF for ; Thu, 27 Apr 2023 05:26:48 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AFBF93854164 for ; Wed, 26 Apr 2023 19:26:46 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org AFBF93854164 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682537206; bh=edUT3M6aGdYeYiOrHa9pQzeoKXs3t/mFLjBurcZaEVg=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=d/uCdwOCqA8CXJ89CgqkEnh71zgYIRecIZOzHfW6J9wgFV8cdD9KU6lZ1PCulVstg CQrvaVjR8XilXm8Q4wja46jP5G5/+FTbI4DzEk2ZA5jk/rnzQ1Gt3/tn/fUG9Fs0uo 5+XDbV+XeoKrqVcQnv+cYbIPIkl9MxUjRd51rLhE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 826F53856DD9 for ; Wed, 26 Apr 2023 19:26:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 826F53856DD9 Received: from mail-qv1-f70.google.com (mail-qv1-f70.google.com [209.85.219.70]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-614-c7nvi4m7O2SEG0n6vqH-AQ-1; Wed, 26 Apr 2023 15:26:25 -0400 X-MC-Unique: c7nvi4m7O2SEG0n6vqH-AQ-1 Received: by mail-qv1-f70.google.com with SMTP id 6a1803df08f44-5f55eefb3b6so44174076d6.0 for ; Wed, 26 Apr 2023 12:26:25 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682537184; x=1685129184; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=kULoy/svlVO/GsZ6rYzdF8RS5xu+JoF5fJ00CRHpo7g=; b=DXbMD+WxCeZGQ/fqtIa8a/fMBRfII/VyAoBZpl8NDVFwED0gFjWSitnw3g1h4ZtCnK QroomLfPRtT9NwRWuPmpM7bBLYmzBkFkZXKVaYDu2HBDj5txhrPpCTYNTwKzNJKxKCdq gdoh2JlET1jzptjjBG2PJDbRtmHNbxKul1CMT9L+UQbifz77D8Rs2ZLBmJ5PZCtHxZVb oWkCUGPilDbVgn2qkQqHHhMYL8eBB9qPSm5KtaH/wF8i9/zyIfVj7x6e27CEcBIPRjmI 75Vvt85Y8ynzjBeelyLFizppQ9V3ugIeg4QzPuXk5kHXSve+uUQzb9KlBq4b+y9Fw8ZQ pYwg== X-Gm-Message-State: AC+VfDxVAA3wuLDRxb6uvk80TpKXBzFT/nv0U4OUwnE408Htnt2WvJV4 KMkJ9aW/TOtngT6CLKuK281CVe+hSSTdIV+3Ta8HcJOsaMzAya1eSChQvVzcpIvYyS3oRFvAS7n BJ3QDagCqTwaP2NODf7x9mWvdYjv2zC3okd0PgMtuCmh7bKcyTK3Uf0qnkvEuHVeQBrn4S6wI5L 7vOQ== X-Received: by 2002:a05:6214:c4b:b0:616:58f1:2844 with SMTP id r11-20020a0562140c4b00b0061658f12844mr7415403qvj.45.1682537184621; Wed, 26 Apr 2023 12:26:24 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ5pl7yaPhT+U7vkSp8rlgEEbu4tnyxS7kVC8vpA871a41bqVPop+fzpPJmBnCpVUMvjv+zwsw== X-Received: by 2002:a05:6214:c4b:b0:616:58f1:2844 with SMTP id r11-20020a0562140c4b00b0061658f12844mr7415226qvj.45.1682537182495; Wed, 26 Apr 2023 12:26:22 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::1dcd? ([2607:fea8:51df:4200::1dcd]) by smtp.gmail.com with ESMTPSA id dz2-20020a05620a2b8200b0074d3233487dsm5356763qkb.114.2023.04.26.12.26.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 26 Apr 2023 12:26:22 -0700 (PDT) Message-ID: <28bd16f7-f334-3245-c444-65a23e98d020@redhat.com> Date: Wed, 26 Apr 2023 15:26:21 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 2/5] Quicker relation check. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" If either of the SSA names in a comparison do not have any equivalences or relations, we can short-circuit the check slightly and be a bit faster. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From ee03aca78fb5739f4cd76cb30332f8aff2c5243a Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Wed, 8 Feb 2023 12:36:23 -0500 Subject: [PATCH 2/5] Quicker relation check. If either of the SSA names in a comparison do not have any equivalences or relations, we can short-circuit the check slightly. * value-relation.cc (dom_oracle::query_relation): Check early for lack of any relation. * value-relation.h (equiv_oracle::has_equiv_p): New. --- gcc/value-relation.cc | 6 ++++++ gcc/value-relation.h | 1 + 2 files changed, 7 insertions(+) diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc index 30a02d3c9d3..65cf7694d40 100644 --- a/gcc/value-relation.cc +++ b/gcc/value-relation.cc @@ -1374,6 +1374,12 @@ dom_oracle::query_relation (basic_block bb, tree ssa1, tree ssa2) if (v1 == v2) return VREL_EQ; + // If v1 or v2 do not have any relations or equivalences, a partial + // equivalence is the only possibility. + if ((!bitmap_bit_p (m_relation_set, v1) && !has_equiv_p (v1)) + || (!bitmap_bit_p (m_relation_set, v2) && !has_equiv_p (v2))) + return partial_equiv (ssa1, ssa2); + // Check for equivalence first. They must be in each equivalency set. const_bitmap equiv1 = equiv_set (ssa1, bb); const_bitmap equiv2 = equiv_set (ssa2, bb); diff --git a/gcc/value-relation.h b/gcc/value-relation.h index 3177ecb1ad0..be6e277421b 100644 --- a/gcc/value-relation.h +++ b/gcc/value-relation.h @@ -170,6 +170,7 @@ public: void dump (FILE *f) const override; protected: + inline bool has_equiv_p (unsigned v) { return bitmap_bit_p (m_equiv_set, v); } bitmap_obstack m_bitmaps; struct obstack m_chain_obstack; private: -- 2.39.2 From patchwork Wed Apr 26 19:26:40 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1774243 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=AvGqHaXt; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Q68574Dqpz23vF for ; Thu, 27 Apr 2023 05:27:07 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9F2713856940 for ; Wed, 26 Apr 2023 19:27:05 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9F2713856940 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682537225; bh=plOWSnPUmizQ9rZPdPot/7Ov7yrub7NyxGLmTMgUG08=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=AvGqHaXtkdoCM2rsKJDLcR5ev7RG29bQZ7rma3kJOjX5gPe34VWiHc9HDaVVYGez7 KBrKc/TJ3BOKRdZRZZz9TsFtaASdfcWQr58GSVYX3GSpBfbgaU7dXxt5jecoSr8TFi ze9GYWbpmn3VI5VsZZvdCItYxu8HMyFIqwdFQoYU= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 70CA43854154 for ; Wed, 26 Apr 2023 19:26:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 70CA43854154 Received: from mail-qv1-f69.google.com (mail-qv1-f69.google.com [209.85.219.69]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-529-jtTxxqIkPt2NPCxi6YD4Cw-1; Wed, 26 Apr 2023 15:26:43 -0400 X-MC-Unique: jtTxxqIkPt2NPCxi6YD4Cw-1 Received: by mail-qv1-f69.google.com with SMTP id 6a1803df08f44-5ef40d2af43so46810256d6.3 for ; Wed, 26 Apr 2023 12:26:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682537202; x=1685129202; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=AzagLYIz+FTnfGtWed8s7i28VbltM+RE+fd/OGB8EVI=; b=Yjqtu3yFWKa2/OBv3z94DPrQ9UsU1J5BiSl5IlIFRc8UD6bNfmOPIJ9vmKFcSypAkb zvPruqU9dbCeOSM9mk7XgWPC+guEXYh83cZCSe4ajkNgNJTDPERk84/gnqxfBm3T8o+c iUFKbqBwjq5AWHXH0Gw8Y+o+5ZR662lahVL6D93bUegH89ubj7IBbkwQzhU8OnPqEkdL VtrvdedHaR2ARtHxdDG07/PUmxpcc+mNyjGYAATuKev0cOqxSQV3jBz5IG6i0HxwVr60 XRg9J6Abm/KIu33GhDeU/tV7OPyWVwHStBf9MSD+chsUuol5ZR787kVpq1a4EXnBY7YF DyJw== X-Gm-Message-State: AAQBX9erv5VP6aKi0CsJychIYCua+kXRtD9IVTnqZ7J7QbCKuBove3NN UKxwhTxOQL83grjfo4SOKwirgDr/gIx3wLkcgY2fIvQbcIvEN8/B6gScqYZYK+aw8OMb8dr0YCQ Eieh/1/6DS7oDlhfveFZtB0EeEfm5gK5poLdRlcCP+RpchPFOCxwnV4Mebd1DxZhQNn1Kwq5jQc 5q7A== X-Received: by 2002:a05:6214:da7:b0:56e:9986:4fa9 with SMTP id h7-20020a0562140da700b0056e99864fa9mr40395993qvh.7.1682537202432; Wed, 26 Apr 2023 12:26:42 -0700 (PDT) X-Google-Smtp-Source: AKy350Y4os1oxmk+r/k7dt7v+N5cgXaFc8Sl46X7XbqHPUFHqKn2MDD4TBvXKoD7rUU6085P737e9A== X-Received: by 2002:a05:6214:da7:b0:56e:9986:4fa9 with SMTP id h7-20020a0562140da700b0056e99864fa9mr40395966qvh.7.1682537202091; Wed, 26 Apr 2023 12:26:42 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::1dcd? ([2607:fea8:51df:4200::1dcd]) by smtp.gmail.com with ESMTPSA id o15-20020a0ce40f000000b005ef616a7cc9sm5034784qvl.137.2023.04.26.12.26.41 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 26 Apr 2023 12:26:41 -0700 (PDT) Message-ID: Date: Wed, 26 Apr 2023 15:26:40 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 3/5] Add sbr_lazy_vector and adjust (e)vrp sparse cache X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This implements a sparse vector class for rangers cache and uses it bey default except when the CFG is very small, in qhich case the original full vectors are faster.  It works like a normal vector cache (in fact it inherits from it), but uses a sparse bitmap to determine whether a vector element is set or not.  This provide better performance for clearing the vector, as well as during initialization. A new param is added for this transition "vrp_vector_threshold" which defaults to 250.  Anything function with fewer than 250 basic blocks will use the simple vectors.  Various timing runs have indicated this is about the sweet spot where using the sparse bitmap overtakes the time required to clear the vector initially. Should we make ranger live across functions in the future, we'll probably want to lower this value again as clearing is significantly cheaper. This patch also rename the "evrp_*" params to "vrp_*" as there really is not a serperate EVRP pass any more, its all one vrp pass.   Eventually we'll probably want to change it to vrp1, vrp2 and vrp3 rather than evrp, vrp1  and vrp2.    But thats a task for later, perhaps when we reconsider pass orderings.. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From 6a3babfbd9a2b18b9e86d3d3a91564fcb9b8f9d7 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Thu, 13 Apr 2023 14:47:47 -0400 Subject: [PATCH 3/5] Add sbr_lazy_vector and adjust (e)vrp sparse cache Add a sparse vector class for cache and use if by default. Rename the evrp_* params to vrp_*, and add a param for small CFGS which use just the original basic vector. * gimple-range-cache.cc (sbr_vector::sbr_vector): Add parameter and local to optionally zero memory. (br_vector::grow): Only zero memory if flag is set. (class sbr_lazy_vector): New. (sbr_lazy_vector::sbr_lazy_vector): New. (sbr_lazy_vector::set_bb_range): New. (sbr_lazy_vector::get_bb_range): New. (sbr_lazy_vector::bb_range_p): New. (block_range_cache::set_bb_range): Check flags and Use sbr_lazy_vector. * gimple-range-gori.cc (gori_map::calculate_gori): Use param_vrp_switch_limit. (gori_compute::gori_compute): Use param_vrp_switch_limit. * params.opt (vrp_sparse_threshold): Rename from evrp_sparse_threshold. (vrp_switch_limit): Rename from evrp_switch_limit. (vrp_vector_threshold): New. --- gcc/gimple-range-cache.cc | 72 ++++++++++++++++++++++++++++++++++----- gcc/gimple-range-gori.cc | 4 +-- gcc/params.opt | 20 ++++++----- 3 files changed, 78 insertions(+), 18 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 2314478d558..868d2dda424 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -79,7 +79,7 @@ ssa_block_ranges::dump (FILE *f) class sbr_vector : public ssa_block_ranges { public: - sbr_vector (tree t, vrange_allocator *allocator); + sbr_vector (tree t, vrange_allocator *allocator, bool zero_p = true); virtual bool set_bb_range (const_basic_block bb, const vrange &r) override; virtual bool get_bb_range (vrange &r, const_basic_block bb) override; @@ -91,22 +91,25 @@ protected: vrange *m_undefined; tree m_type; vrange_allocator *m_range_allocator; + bool m_zero_p; void grow (); }; // Initialize a block cache for an ssa_name of type T. -sbr_vector::sbr_vector (tree t, vrange_allocator *allocator) +sbr_vector::sbr_vector (tree t, vrange_allocator *allocator, bool zero_p) : ssa_block_ranges (t) { gcc_checking_assert (TYPE_P (t)); m_type = t; + m_zero_p = zero_p; m_range_allocator = allocator; m_tab_size = last_basic_block_for_fn (cfun) + 1; m_tab = static_cast (allocator->alloc (m_tab_size * sizeof (vrange *))); - memset (m_tab, 0, m_tab_size * sizeof (vrange *)); + if (zero_p) + memset (m_tab, 0, m_tab_size * sizeof (vrange *)); // Create the cached type range. m_varying = m_range_allocator->alloc_vrange (t); @@ -132,7 +135,8 @@ sbr_vector::grow () vrange **t = static_cast (m_range_allocator->alloc (new_size * sizeof (vrange *))); memcpy (t, m_tab, m_tab_size * sizeof (vrange *)); - memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (vrange *)); + if (m_zero_p) + memset (t + m_tab_size, 0, (new_size - m_tab_size) * sizeof (vrange *)); m_tab = t; m_tab_size = new_size; @@ -183,6 +187,50 @@ sbr_vector::bb_range_p (const_basic_block bb) return false; } +// Like an sbr_vector, except it uses a bitmap to manage whetehr vale is set +// or not rather than cleared memory. + +class sbr_lazy_vector : public sbr_vector +{ +public: + sbr_lazy_vector (tree t, vrange_allocator *allocator, bitmap_obstack *bm); + + virtual bool set_bb_range (const_basic_block bb, const vrange &r) override; + virtual bool get_bb_range (vrange &r, const_basic_block bb) override; + virtual bool bb_range_p (const_basic_block bb) override; +protected: + bitmap m_has_value; +}; + +sbr_lazy_vector::sbr_lazy_vector (tree t, vrange_allocator *allocator, + bitmap_obstack *bm) + : sbr_vector (t, allocator, false) +{ + m_has_value = BITMAP_ALLOC (bm); +} + +bool +sbr_lazy_vector::set_bb_range (const_basic_block bb, const vrange &r) +{ + sbr_vector::set_bb_range (bb, r); + bitmap_set_bit (m_has_value, bb->index); + return true; +} + +bool +sbr_lazy_vector::get_bb_range (vrange &r, const_basic_block bb) +{ + if (bitmap_bit_p (m_has_value, bb->index)) + return sbr_vector::get_bb_range (r, bb); + return false; +} + +bool +sbr_lazy_vector::bb_range_p (const_basic_block bb) +{ + return bitmap_bit_p (m_has_value, bb->index); +} + // This class implements the on entry cache via a sparse bitmap. // It uses the quad bit routines to access 4 bits at a time. // A value of 0 (the default) means there is no entry, and a value of @@ -347,21 +395,29 @@ block_range_cache::set_bb_range (tree name, const_basic_block bb, if (!m_ssa_ranges[v]) { - // Use sparse representation if there are too many basic blocks. - if (last_basic_block_for_fn (cfun) > param_evrp_sparse_threshold) + // Use sparse bitmap representation if there are too many basic blocks. + if (last_basic_block_for_fn (cfun) > param_vrp_sparse_threshold) { void *r = m_range_allocator->alloc (sizeof (sbr_sparse_bitmap)); m_ssa_ranges[v] = new (r) sbr_sparse_bitmap (TREE_TYPE (name), m_range_allocator, &m_bitmaps); } - else + else if (last_basic_block_for_fn (cfun) < param_vrp_vector_threshold) { - // Otherwise use the default vector implementation. + // For small CFGs use the basic vector implemntation. void *r = m_range_allocator->alloc (sizeof (sbr_vector)); m_ssa_ranges[v] = new (r) sbr_vector (TREE_TYPE (name), m_range_allocator); } + else + { + // Otherwise use the sparse vector implementation. + void *r = m_range_allocator->alloc (sizeof (sbr_lazy_vector)); + m_ssa_ranges[v] = new (r) sbr_lazy_vector (TREE_TYPE (name), + m_range_allocator, + &m_bitmaps); + } } return m_ssa_ranges[v]->set_bb_range (bb, r); } diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc index 5bba77c7b7b..9d0cc97bf8c 100644 --- a/gcc/gimple-range-gori.cc +++ b/gcc/gimple-range-gori.cc @@ -486,7 +486,7 @@ gori_map::calculate_gori (basic_block bb) else { // Do not process switches if they are too large. - if (EDGE_COUNT (bb->succs) > (unsigned)param_evrp_switch_limit) + if (EDGE_COUNT (bb->succs) > (unsigned)param_vrp_switch_limit) return; gswitch *gs = as_a(stmt); name = gimple_range_ssa_p (gimple_switch_index (gs)); @@ -558,7 +558,7 @@ debug (gori_map &g) // Construct a gori_compute object. gori_compute::gori_compute (int not_executable_flag) - : outgoing (param_evrp_switch_limit), tracer ("GORI ") + : outgoing (param_vrp_switch_limit), tracer ("GORI ") { m_not_executable_flag = not_executable_flag; // Create a boolean_type true and false range. diff --git a/gcc/params.opt b/gcc/params.opt index 823cdb2ff85..66f1c99036a 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -130,14 +130,6 @@ Maximum size (in bytes) of objects tracked bytewise by dead store elimination. Common Joined UInteger Var(param_early_inlining_insns) Init(6) Optimization Param Maximal estimated growth of function body caused by early inlining of single call. --param=evrp-sparse-threshold= -Common Joined UInteger Var(param_evrp_sparse_threshold) Init(800) Optimization Param -Maximum number of basic blocks before EVRP uses a sparse cache. - --param=evrp-switch-limit= -Common Joined UInteger Var(param_evrp_switch_limit) Init(50) Optimization Param -Maximum number of outgoing edges in a switch before EVRP will not process it. - -param=fsm-scale-path-stmts= Common Joined UInteger Var(param_fsm_scale_path_stmts) Init(2) IntegerRange(1, 10) Param Optimization Scale factor to apply to the number of statements in a threading path crossing a loop backedge when comparing to max-jump-thread-duplication-stmts. @@ -1182,4 +1174,16 @@ The maximum factor which the loop vectorizer applies to the cost of statements i Common Joined UInteger Var(param_vect_induction_float) Init(1) IntegerRange(0, 1) Param Optimization Enable loop vectorization of floating point inductions. +-param=vrp-sparse-threshold= +Common Joined UInteger Var(param_vrp_sparse_threshold) Init(3000) Optimization Param +Maximum number of basic blocks before VRP uses a sparse bitmap cache. + +-param=vrp-switch-limit= +Common Joined UInteger Var(param_vrp_switch_limit) Init(50) Optimization Param +Maximum number of outgoing edges in a switch before VRP will not process it. + +-param=vrp-vector-threshold= +Common Joined UInteger Var(param_vrp_vector_threshold) Init(250) Optimization Param +Maximum number of basic blocks for VRP to use a basic cache vector. + ; This comment is to ensure we retain the blank line above. -- 2.39.2 From patchwork Wed Apr 26 19:26:53 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1774245 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=FRVmN6tY; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Q686K01bPz23vF for ; Thu, 27 Apr 2023 05:28:08 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 05C5638560A9 for ; Wed, 26 Apr 2023 19:28:07 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 05C5638560A9 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682537287; bh=2EzUT+nUs1/o3rO1mEYPDubf1ZeDU64cdG2pu6QW8Dg=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=FRVmN6tYa81R5O4o8xNFbVMFLSXrH8BygyaAiQUd9XFB4YOSFK1q4PdintOP340uK YJrMON7TfhTfVeiyoJUsGjUJPvQ+BP272JDoahWYThgeQO8kha2dr4o0HMZK+3W22X z42lh5OcSuEc3POa4tGLh7DzY0B5jwWHVWfTZs3k= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 5D7E73853839 for ; Wed, 26 Apr 2023 19:26:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5D7E73853839 Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-376-OJ1c3ZQSOJCckNGMxtFDRw-1; Wed, 26 Apr 2023 15:26:56 -0400 X-MC-Unique: OJ1c3ZQSOJCckNGMxtFDRw-1 Received: by mail-qk1-f197.google.com with SMTP id af79cd13be357-74e1cdf9cbeso80270985a.0 for ; Wed, 26 Apr 2023 12:26:56 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682537215; x=1685129215; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=c5TQ1UYaonOTNOET6EerW++h0aue8wjDf+rZfKXhimA=; b=QI19oxmxCPpCVvv+85dpcMviGyJMnwBokl3QVfMGsAMztaMpXLwNe7zM7BrHds1siq UL0675h4bjbgVCWk5g4JFXOog0Ji72fJQX7SJQqt0pE1w2WTcsD96Cpm2rCPWT8k073B XWrgUMSmppN729HOAqNC/n6Hm6HIWZACduBk5WV1/m0ySyrzOz98qVwdFughSHsxeQEz WbIRVRvmR8bLOiQCLS5QtFlGiHIBBixxrRcNAyqb8Xd5yfVtuJeFOsou1D+UNLkDEJXu ACjUKLIV2nJZVnjOO2qIsUHG0HSZ9LK/b2BScR/f2wzmszOqyAzfxu8QmBDP8/cxL7bn bwjw== X-Gm-Message-State: AC+VfDxsTbe7Xs27jI5SZ273Y75O32/xi/7OzBOahmCMfV5Yjif4DpA7 zzzNlKjSBpyjkrHM7or+Yv/nvpmN1CUFeMURZsnqjwfdsTtM98/zO4ZXZxaObQ9ZeYeDfCbFR60 8maCiiv4Dc+3Uxi9KM7oRoIkMUqKikU07nJx6u5KuJPCa7dioEKPvjSL6hrAj+aYZgnumouomQa UI9g== X-Received: by 2002:a05:6214:2aac:b0:5ac:d6e6:452b with SMTP id js12-20020a0562142aac00b005acd6e6452bmr5731190qvb.24.1682537215379; Wed, 26 Apr 2023 12:26:55 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ72+mhOWUzMDNVVEWROXIc6SAZzez1ueclrFRLtUQWnWthqDpR/Ejm2kGKEZGutGjRZV5aexQ== X-Received: by 2002:a05:6214:2aac:b0:5ac:d6e6:452b with SMTP id js12-20020a0562142aac00b005acd6e6452bmr5731159qvb.24.1682537214985; Wed, 26 Apr 2023 12:26:54 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::1dcd? ([2607:fea8:51df:4200::1dcd]) by smtp.gmail.com with ESMTPSA id z8-20020a0cf248000000b005f5a05448d8sm4994636qvl.100.2023.04.26.12.26.54 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 26 Apr 2023 12:26:54 -0700 (PDT) Message-ID: <5e014139-e9d6-52fa-bbdb-42c74981b9d7@redhat.com> Date: Wed, 26 Apr 2023 15:26:53 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 4/5] Rename ssa_global_cache to ssa_cache and add has_range X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" The original ssa_global_cache was intended to simply be the global cache for ranger, but uses of it have since percolated such that it is really just a range acche for a list of ssa-names. This patch renames it from "ssa_global_cache" to "ssa_cache". It also adds a method called "has_range" which didnt exist before which simply indicates if a range is set or not. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From bf07de561197559304c67bd46c7bea3da9eb63f9 Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 28 Mar 2023 11:32:21 -0400 Subject: [PATCH 4/5] Rename ssa_global_cache to ssa_cache and add has_range This renames the ssa_global_cache to be ssa_cache. The original use was to function as a global cache, but its uses have expanded. Remove all mention of "global" from the class and methods. Also add a has_range method. * gimple-range-cache.cc (ssa_cache::ssa_cache): Rename. (ssa_cache::~ssa_cache): Rename. (ssa_cache::has_range): New. (ssa_cache::get_range): Rename. (ssa_cache::set_range): Rename. (ssa_cache::clear_range): Rename. (ssa_cache::clear): Rename. (ssa_cache::dump): Rename and use get_range. (ranger_cache::get_global_range): Use get_range and set_range. (ranger_cache::range_of_def): Use get_range. * gimple-range-cache.h (class ssa_cache): Rename class and methods. (class ranger_cache): Use ssa_cache. * gimple-range-path.cc (path_range_query::path_range_query): Use ssa_cache. (path_range_query::get_cache): Use get_range. (path_range_query::set_cache): Use set_range. * gimple-range-path.h (class path_range_query): Use ssa_cache. * gimple-range.cc (assume_query::assume_range_p): Use get_range. (assume_query::range_of_expr): Use get_range. (assume_query::assume_query): Use set_range. (assume_query::calculate_op): Use get_range and set_range. * gimple-range.h (class assume_query): Use ssa_cache. --- gcc/gimple-range-cache.cc | 45 ++++++++++++++++++++++++--------------- gcc/gimple-range-cache.h | 15 +++++++------ gcc/gimple-range-path.cc | 8 +++---- gcc/gimple-range-path.h | 2 +- gcc/gimple-range.cc | 14 ++++++------ gcc/gimple-range.h | 2 +- 6 files changed, 49 insertions(+), 37 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 868d2dda424..6de96f6b8a9 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -530,27 +530,38 @@ block_range_cache::dump (FILE *f, basic_block bb, bool print_varying) // ------------------------------------------------------------------------- -// Initialize a global cache. +// Initialize an ssa cache. -ssa_global_cache::ssa_global_cache () +ssa_cache::ssa_cache () { m_tab.create (0); m_range_allocator = new obstack_vrange_allocator; } -// Deconstruct a global cache. +// Deconstruct an ssa cache. -ssa_global_cache::~ssa_global_cache () +ssa_cache::~ssa_cache () { m_tab.release (); delete m_range_allocator; } +// Return TRUE if the global range of NAME has a cache entry. + +bool +ssa_cache::has_range (tree name) const +{ + unsigned v = SSA_NAME_VERSION (name); + if (v >= m_tab.length ()) + return false; + return m_tab[v] != NULL; +} + // Retrieve the global range of NAME from cache memory if it exists. // Return the value in R. bool -ssa_global_cache::get_global_range (vrange &r, tree name) const +ssa_cache::get_range (vrange &r, tree name) const { unsigned v = SSA_NAME_VERSION (name); if (v >= m_tab.length ()) @@ -563,11 +574,11 @@ ssa_global_cache::get_global_range (vrange &r, tree name) const return true; } -// Set the range for NAME to R in the global cache. +// Set the range for NAME to R in the ssa cache. // Return TRUE if there was already a range set, otherwise false. bool -ssa_global_cache::set_global_range (tree name, const vrange &r) +ssa_cache::set_range (tree name, const vrange &r) { unsigned v = SSA_NAME_VERSION (name); if (v >= m_tab.length ()) @@ -584,7 +595,7 @@ ssa_global_cache::set_global_range (tree name, const vrange &r) // Set the range for NAME to R in the global cache. void -ssa_global_cache::clear_global_range (tree name) +ssa_cache::clear_range (tree name) { unsigned v = SSA_NAME_VERSION (name); if (v >= m_tab.length ()) @@ -592,19 +603,19 @@ ssa_global_cache::clear_global_range (tree name) m_tab[v] = NULL; } -// Clear the global cache. +// Clear the ssa cache. void -ssa_global_cache::clear () +ssa_cache::clear () { if (m_tab.address ()) memset (m_tab.address(), 0, m_tab.length () * sizeof (vrange *)); } -// Dump the contents of the global cache to F. +// Dump the contents of the ssa cache to F. void -ssa_global_cache::dump (FILE *f) +ssa_cache::dump (FILE *f) { /* Cleared after the table header has been printed. */ bool print_header = true; @@ -613,7 +624,7 @@ ssa_global_cache::dump (FILE *f) if (!gimple_range_ssa_p (ssa_name (x))) continue; Value_Range r (TREE_TYPE (ssa_name (x))); - if (get_global_range (r, ssa_name (x)) && !r.varying_p ()) + if (get_range (r, ssa_name (x)) && !r.varying_p ()) { if (print_header) { @@ -877,7 +888,7 @@ ranger_cache::dump_bb (FILE *f, basic_block bb) bool ranger_cache::get_global_range (vrange &r, tree name) const { - if (m_globals.get_global_range (r, name)) + if (m_globals.get_range (r, name)) return true; gimple_range_global (r, name); return false; @@ -902,7 +913,7 @@ ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p) || m_temporal->current_p (name, m_gori.depend1 (name), m_gori.depend2 (name)); else - m_globals.set_global_range (name, r); + m_globals.set_range (name, r); // If the existing value was not current, mark it as always current. if (!current_p) @@ -915,7 +926,7 @@ ranger_cache::get_global_range (vrange &r, tree name, bool ¤t_p) void ranger_cache::set_global_range (tree name, const vrange &r) { - if (m_globals.set_global_range (name, r)) + if (m_globals.set_range (name, r)) { // If there was already a range set, propagate the new value. basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (name)); @@ -954,7 +965,7 @@ ranger_cache::range_of_def (vrange &r, tree name, basic_block bb) gcc_checking_assert (!bb || bb == gimple_bb (SSA_NAME_DEF_STMT (name))); // Pick up the best global range available. - if (!m_globals.get_global_range (r, name)) + if (!m_globals.get_range (r, name)) { // If that fails, try to calculate the range using just global values. gimple *s = SSA_NAME_DEF_STMT (name); diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 4ff435dc5c1..2d41f0c5c67 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -52,14 +52,15 @@ private: // has been visited during this incarnation. Once the ranger evaluates // a name, it is typically not re-evaluated again. -class ssa_global_cache +class ssa_cache { public: - ssa_global_cache (); - ~ssa_global_cache (); - bool get_global_range (vrange &r, tree name) const; - bool set_global_range (tree name, const vrange &r); - void clear_global_range (tree name); + ssa_cache (); + ~ssa_cache (); + bool has_range (tree name) const; + bool get_range (vrange &r, tree name) const; + bool set_range (tree name, const vrange &r); + void clear_range (tree name); void clear (); void dump (FILE *f = stderr); private: @@ -95,7 +96,7 @@ public: void dump_bb (FILE *f, basic_block bb); virtual void dump (FILE *f) override; private: - ssa_global_cache m_globals; + ssa_cache m_globals; block_range_cache m_on_entry; class temporal_cache *m_temporal; void fill_block_cache (tree name, basic_block bb, basic_block def_bb); diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index f68b2029476..07868df5e6f 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -40,7 +40,7 @@ path_range_query::path_range_query (gimple_ranger &ranger, const vec &path, const bitmap_head *dependencies, bool resolve) - : m_cache (new ssa_global_cache), + : m_cache (new ssa_cache), m_has_cache_entry (BITMAP_ALLOC (NULL)), m_ranger (ranger), m_resolve (resolve) @@ -51,7 +51,7 @@ path_range_query::path_range_query (gimple_ranger &ranger, } path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) - : m_cache (new ssa_global_cache), + : m_cache (new ssa_cache), m_has_cache_entry (BITMAP_ALLOC (NULL)), m_ranger (ranger), m_resolve (resolve) @@ -94,7 +94,7 @@ path_range_query::get_cache (vrange &r, tree name) unsigned v = SSA_NAME_VERSION (name); if (bitmap_bit_p (m_has_cache_entry, v)) - return m_cache->get_global_range (r, name); + return m_cache->get_range (r, name); return false; } @@ -106,7 +106,7 @@ path_range_query::set_cache (const vrange &r, tree name) { unsigned v = SSA_NAME_VERSION (name); bitmap_set_bit (m_has_cache_entry, v); - m_cache->set_global_range (name, r); + m_cache->set_range (name, r); } void diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index e8b06b60e66..29e33c6c37b 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -83,7 +83,7 @@ private: void move_next () { --m_pos; } // Range cache for SSA names. - ssa_global_cache *m_cache; + ssa_cache *m_cache; // Set for each SSA that has an active entry in the cache. bitmap m_has_cache_entry; diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc index b4de8dd4ef9..49e9d6b4de6 100644 --- a/gcc/gimple-range.cc +++ b/gcc/gimple-range.cc @@ -737,7 +737,7 @@ disable_ranger (struct function *fun) bool assume_query::assume_range_p (vrange &r, tree name) { - if (global.get_global_range (r, name)) + if (global.get_range (r, name)) return !r.varying_p (); return false; } @@ -750,7 +750,7 @@ assume_query::range_of_expr (vrange &r, tree expr, gimple *stmt) if (!gimple_range_ssa_p (expr)) return get_tree_range (r, expr, stmt); - if (!global.get_global_range (r, expr)) + if (!global.get_range (r, expr)) r.set_varying (TREE_TYPE (expr)); return true; } @@ -781,7 +781,7 @@ assume_query::assume_query () unsigned prec = TYPE_PRECISION (lhs_type); int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec)); - global.set_global_range (op, lhs_range); + global.set_range (op, lhs_range); gimple *def = SSA_NAME_DEF_STMT (op); if (!def || gimple_get_lhs (def) != op) @@ -802,9 +802,9 @@ assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src) && !op_range.varying_p ()) { Value_Range range (TREE_TYPE (op)); - if (global.get_global_range (range, op)) + if (global.get_range (range, op)) op_range.intersect (range); - global.set_global_range (op, op_range); + global.set_range (op, op_range); gimple *def_stmt = SSA_NAME_DEF_STMT (op); if (def_stmt && gimple_get_lhs (def_stmt) == op) calculate_stmt (def_stmt, op_range, src); @@ -827,9 +827,9 @@ assume_query::calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src) // A symbol arg will be the LHS value. arg_range = lhs_range; range_cast (arg_range, TREE_TYPE (arg)); - if (!global.get_global_range (arg_range, arg)) + if (!global.get_range (arg_range, arg)) { - global.set_global_range (arg, arg_range); + global.set_range (arg, arg_range); gimple *def_stmt = SSA_NAME_DEF_STMT (arg); if (def_stmt && gimple_get_lhs (def_stmt) == arg) calculate_stmt (def_stmt, arg_range, src); diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index b8ddca59d2d..944e7692a0e 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -96,7 +96,7 @@ protected: void calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src); void check_taken_edge (edge e, fur_source &src); - ssa_global_cache global; + ssa_cache global; gori_compute m_gori; }; -- 2.39.2 From patchwork Wed Apr 26 19:27:06 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrew MacLeod X-Patchwork-Id: 1774244 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=YHZGl9S1; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Q685p34kQz23vF for ; Thu, 27 Apr 2023 05:27:42 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 518043850204 for ; Wed, 26 Apr 2023 19:27:40 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 518043850204 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1682537260; bh=zlbuBnGGYP+QNOYuhHihQ7BvSjBJmB+PIBImfkbuuyY=; h=Date:To:Cc:Subject:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=YHZGl9S1ul1iRu0Gk9Z5AeuKcNVcgImTKz4+MkrFiKJhbgnnG66a79561BeRrz5Yd fGQzYFIz/VS22QpqaGOGf+wZSXHmQ0hkXJITVmGwmOBJKmXsueXoQVtyVLpH6j5aCQ xtglN47rIGDKXBH6pq1IZqLXtvSN00/bIboaMxJs= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 81F833852767 for ; Wed, 26 Apr 2023 19:27:11 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 81F833852767 Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-488-GgqR6Px8NNSaqzbRqBIVbw-1; Wed, 26 Apr 2023 15:27:09 -0400 X-MC-Unique: GgqR6Px8NNSaqzbRqBIVbw-1 Received: by mail-qt1-f197.google.com with SMTP id d75a77b69052e-3ef5c322d56so42506281cf.1 for ; Wed, 26 Apr 2023 12:27:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682537229; x=1685129229; h=subject:from:cc:to:content-language:user-agent:mime-version:date :message-id:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=4N/V6+hM938929TH+0tfukdngZr/orH9RkFqLGc1LP4=; b=MFbo9v1mxpNn2wSN3mK1WdvrzrS2cPJ3x4W7zOmaBVFImRQOqgZMM9htVbwek3Ho7E JozHR37VSP7MNC0M+/y+XklvQNu4VbqDbSrYeVx+dzJXWXTJcSiNstOPty5jYjftI/Xp fKw/bNqTRa/wE6k0qEr43Jdip25C+uLAYx5Bn7jMUpZXOf4bMDVZU3L+IpQwUFWsIuin owZtdJyhDcbbSfvsL4SLYGet9sjThXlhF/Jd93rTe3FdOIRgAkjjK5Azz+armGRMhadk WlbueXb5EGtB1WXoHhTiKPxEv65EP72Yl09d2PI23ul7KbrHcEf38FAaCSfSiCOJ2S/U FxCQ== X-Gm-Message-State: AAQBX9db8juEwxQDYxdQefdvnz+QQL1hjaIDgIj5j3rH0zOXH7KQ1mss QTBPG1MZQQwl9wnLa8MpwgkB5UPWq3XUnla0MN19423erkQnuVcb6mLbp0vaZSfabqi4fIJvuPp AzRKuLFj3mrI3w822Fu9a0pVa3TcEG/NrgCqjnkkVGKTP71mcFqL6l9fUBmzwCZ+98D1aPOhg/o dz3Q== X-Received: by 2002:a05:622a:48a:b0:3ef:3b04:b8d8 with SMTP id p10-20020a05622a048a00b003ef3b04b8d8mr34982231qtx.0.1682537228842; Wed, 26 Apr 2023 12:27:08 -0700 (PDT) X-Google-Smtp-Source: AKy350aNtYs90ke9eXtmMuEkox4FruXUPcTX2lWirFxFBYsO8/I17eIP6ZKPiAcuXqJZcdGSh9HiAg== X-Received: by 2002:a05:622a:48a:b0:3ef:3b04:b8d8 with SMTP id p10-20020a05622a048a00b003ef3b04b8d8mr34982197qtx.0.1682537228522; Wed, 26 Apr 2023 12:27:08 -0700 (PDT) Received: from ?IPV6:2607:fea8:51df:4200::1dcd? ([2607:fea8:51df:4200::1dcd]) by smtp.gmail.com with ESMTPSA id az8-20020a05620a170800b0074e4c3719e9sm3483789qkb.69.2023.04.26.12.27.07 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 26 Apr 2023 12:27:08 -0700 (PDT) Message-ID: <8aab3ad2-f9cc-1211-a22f-491304685d8a@redhat.com> Date: Wed, 26 Apr 2023 15:27:06 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.8.0 To: gcc-patches Cc: "hernandez, aldy" Subject: [COMMITTED 5/5] PR tree-optimization/108697 - Create a lazy ssa_cache. X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, 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-Patchwork-Original-From: Andrew MacLeod via Gcc-patches From: Andrew MacLeod Reply-To: Andrew MacLeod Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Sparsely used ssa caches can benefit from using a bitmap to determine if a name already has an entry.  The path_query class was already managing something like this internally, but there is benefit to making it generally available. ssa_lazy_cache inherits from ssa_cache and adds management of the bitmap.   The self-managed version in path_query has been removed, cleaned up, and replaced with this lazy version.  It is also now used in "assume_query" processing. All 5 patches combined produce about  - a 0.4% speedup in total compilation time,  - about a 1% speedup in VRP  - and threading picks up a more impressive 13% improvement. This patch has the previous one as a prerequisite to rename ssa_global_cache to ssa_cache. Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed. Andrew From b3c81a4a6b7ff5adce6b5891729b79a0d6e4e54a Mon Sep 17 00:00:00 2001 From: Andrew MacLeod Date: Tue, 28 Mar 2023 11:35:26 -0400 Subject: [PATCH 5/5] Create a lazy ssa_cache. Sparsely used ssa caches can benefit from using a bitmap to determine if a name already has an entry. Utilize it in the path query and remove its private bitmap for tracking the same info. Also use it in the "assume" query class. PR tree-optimization/108697 * gimple-range-cache.cc (ssa_global_cache::clear_range): Do not clear the vector on an out of range query. (ssa_cache::dump): Use dump_range_query instead of get_range. (ssa_cache::dump_range_query): New. (ssa_lazy_cache::dump_range_query): New. (ssa_lazy_cache::set_range): New. * gimple-range-cache.h (ssa_cache::dump_range_query): New. (class ssa_lazy_cache): New. (ssa_lazy_cache::ssa_lazy_cache): New. (ssa_lazy_cache::~ssa_lazy_cache): New. (ssa_lazy_cache::get_range): New. (ssa_lazy_cache::clear_range): New. (ssa_lazy_cache::clear): New. (ssa_lazy_cache::dump): New. * gimple-range-path.cc (path_range_query::path_range_query): Do not allocate a ssa_cache object nor has_cache bitmap. (path_range_query::~path_range_query): Do not free objects. (path_range_query::clear_cache): Remove. (path_range_query::get_cache): Adjust. (path_range_query::set_cache): Remove. (path_range_query::dump): Don't call through a pointer. (path_range_query::internal_range_of_expr): Set cache directly. (path_range_query::reset_path): Clear cache directly. (path_range_query::ssa_range_in_phi): Fold with globals only. (path_range_query::compute_ranges_in_phis): Simply set range. (path_range_query::compute_ranges_in_block): Call cache directly. * gimple-range-path.h (class path_range_query): Replace bitmap and cache pointer with lazy cache object. * gimple-range.h (class assume_query): Use ssa_lazy_cache. --- gcc/gimple-range-cache.cc | 45 +++++++++++++++++++++++++-- gcc/gimple-range-cache.h | 35 ++++++++++++++++++++- gcc/gimple-range-path.cc | 65 +++++++++------------------------------ gcc/gimple-range-path.h | 7 +---- gcc/gimple-range.h | 2 +- 5 files changed, 92 insertions(+), 62 deletions(-) diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc index 6de96f6b8a9..5510efba1ca 100644 --- a/gcc/gimple-range-cache.cc +++ b/gcc/gimple-range-cache.cc @@ -592,14 +592,14 @@ ssa_cache::set_range (tree name, const vrange &r) return m != NULL; } -// Set the range for NAME to R in the global cache. +// Set the range for NAME to R in the ssa cache. void ssa_cache::clear_range (tree name) { unsigned v = SSA_NAME_VERSION (name); if (v >= m_tab.length ()) - m_tab.safe_grow_cleared (num_ssa_names + 1); + return; m_tab[v] = NULL; } @@ -624,7 +624,10 @@ ssa_cache::dump (FILE *f) if (!gimple_range_ssa_p (ssa_name (x))) continue; Value_Range r (TREE_TYPE (ssa_name (x))); - if (get_range (r, ssa_name (x)) && !r.varying_p ()) + // Invoke dump_range_query which is a private virtual version of + // get_range. This avoids performance impacts on general queries, + // but allows sharing of the dump routine. + if (dump_range_query (r, ssa_name (x)) && !r.varying_p ()) { if (print_header) { @@ -646,6 +649,42 @@ ssa_cache::dump (FILE *f) fputc ('\n', f); } +// Virtual private get_range query for dumping. + +bool +ssa_cache::dump_range_query (vrange &r, tree name) const +{ + return get_range (r, name); +} + +// Virtual private get_range query for dumping. + +bool +ssa_lazy_cache::dump_range_query (vrange &r, tree name) const +{ + return get_range (r, name); +} + + +// Set range of NAME to R in a lazy cache. Return FALSE if it did not already +// have a range. + +bool +ssa_lazy_cache::set_range (tree name, const vrange &r) +{ + unsigned v = SSA_NAME_VERSION (name); + if (!bitmap_set_bit (active_p, v)) + { + // There is already an entry, simply set it. + gcc_checking_assert (v < m_tab.length ()); + return ssa_cache::set_range (name, r); + } + if (v >= m_tab.length ()) + m_tab.safe_grow (num_ssa_names + 1); + m_tab[v] = m_range_allocator->clone (r); + return false; +} + // -------------------------------------------------------------------------- diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h index 2d41f0c5c67..9032df9e3e3 100644 --- a/gcc/gimple-range-cache.h +++ b/gcc/gimple-range-cache.h @@ -63,11 +63,44 @@ public: void clear_range (tree name); void clear (); void dump (FILE *f = stderr); -private: +protected: + virtual bool dump_range_query (vrange &r, tree name) const; vec m_tab; vrange_allocator *m_range_allocator; }; +// This is the same as global cache, except it maintains an active bitmap +// rather than depending on a zero'd out vector of pointers. This is better +// for sparsely/lightly used caches. +// It could be made a fully derived class, but at this point there doesnt seem +// to be a need to take the performance hit for it. + +class ssa_lazy_cache : protected ssa_cache +{ +public: + inline ssa_lazy_cache () { active_p = BITMAP_ALLOC (NULL); } + inline ~ssa_lazy_cache () { BITMAP_FREE (active_p); } + bool set_range (tree name, const vrange &r); + inline bool get_range (vrange &r, tree name) const; + inline void clear_range (tree name) + { bitmap_clear_bit (active_p, SSA_NAME_VERSION (name)); } ; + inline void clear () { bitmap_clear (active_p); } + inline void dump (FILE *f = stderr) { ssa_cache::dump (f); } +protected: + virtual bool dump_range_query (vrange &r, tree name) const; + bitmap active_p; +}; + +// Return TRUE if NAME has a range, and return it in R. + +bool +ssa_lazy_cache::get_range (vrange &r, tree name) const +{ + if (!bitmap_bit_p (active_p, SSA_NAME_VERSION (name))) + return false; + return ssa_cache::get_range (r, name); +} + // This class provides all the caches a global ranger may need, and makes // them available for gori-computes to query so outgoing edges can be // properly calculated. diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc index 07868df5e6f..7438b832b5a 100644 --- a/gcc/gimple-range-path.cc +++ b/gcc/gimple-range-path.cc @@ -40,8 +40,7 @@ path_range_query::path_range_query (gimple_ranger &ranger, const vec &path, const bitmap_head *dependencies, bool resolve) - : m_cache (new ssa_cache), - m_has_cache_entry (BITMAP_ALLOC (NULL)), + : m_cache (), m_ranger (ranger), m_resolve (resolve) { @@ -51,8 +50,7 @@ path_range_query::path_range_query (gimple_ranger &ranger, } path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) - : m_cache (new ssa_cache), - m_has_cache_entry (BITMAP_ALLOC (NULL)), + : m_cache (), m_ranger (ranger), m_resolve (resolve) { @@ -62,8 +60,6 @@ path_range_query::path_range_query (gimple_ranger &ranger, bool resolve) path_range_query::~path_range_query () { delete m_oracle; - BITMAP_FREE (m_has_cache_entry); - delete m_cache; } // Return TRUE if NAME is an exit dependency for the path. @@ -75,15 +71,6 @@ path_range_query::exit_dependency_p (tree name) && bitmap_bit_p (m_exit_dependencies, SSA_NAME_VERSION (name))); } -// Mark cache entry for NAME as unused. - -void -path_range_query::clear_cache (tree name) -{ - unsigned v = SSA_NAME_VERSION (name); - bitmap_clear_bit (m_has_cache_entry, v); -} - // If NAME has a cache entry, return it in R, and return TRUE. inline bool @@ -92,21 +79,7 @@ path_range_query::get_cache (vrange &r, tree name) if (!gimple_range_ssa_p (name)) return get_global_range_query ()->range_of_expr (r, name); - unsigned v = SSA_NAME_VERSION (name); - if (bitmap_bit_p (m_has_cache_entry, v)) - return m_cache->get_range (r, name); - - return false; -} - -// Set the cache entry for NAME to R. - -void -path_range_query::set_cache (const vrange &r, tree name) -{ - unsigned v = SSA_NAME_VERSION (name); - bitmap_set_bit (m_has_cache_entry, v); - m_cache->set_range (name, r); + return m_cache.get_range (r, name); } void @@ -130,7 +103,7 @@ path_range_query::dump (FILE *dump_file) fprintf (dump_file, "\n"); } - m_cache->dump (dump_file); + m_cache.dump (dump_file); } void @@ -174,7 +147,7 @@ path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt) if (m_resolve && defined_outside_path (name)) { range_on_path_entry (r, name); - set_cache (r, name); + m_cache.set_range (name, r); return true; } @@ -188,7 +161,7 @@ path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt) r.intersect (glob); } - set_cache (r, name); + m_cache.set_range (name, r); return true; } @@ -225,7 +198,7 @@ path_range_query::reset_path (const vec &path, m_path = path.copy (); m_pos = m_path.length () - 1; m_undefined_path = false; - bitmap_clear (m_has_cache_entry); + m_cache.clear (); compute_ranges (dependencies); } @@ -255,7 +228,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) if (m_resolve && m_ranger.range_of_expr (r, name, phi)) return; - // Try to fold the phi exclusively with global or cached values. + // Try to fold the phi exclusively with global values. // This will get things like PHI <5(99), 6(88)>. We do this by // calling range_of_expr with no context. unsigned nargs = gimple_phi_num_args (phi); @@ -264,7 +237,7 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi) for (size_t i = 0; i < nargs; ++i) { tree arg = gimple_phi_arg_def (phi, i); - if (range_of_expr (arg_range, arg, /*stmt=*/NULL)) + if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL)) r.union_ (arg_range); else { @@ -348,8 +321,6 @@ path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb) void path_range_query::compute_ranges_in_phis (basic_block bb) { - auto_bitmap phi_set; - // PHIs must be resolved simultaneously on entry to the block // because any dependencies must be satisfied with values on entry. // Thus, we calculate all PHIs first, and then update the cache at @@ -365,16 +336,8 @@ path_range_query::compute_ranges_in_phis (basic_block bb) Value_Range r (TREE_TYPE (name)); if (range_defined_in_block (r, name, bb)) - { - unsigned v = SSA_NAME_VERSION (name); - set_cache (r, name); - bitmap_set_bit (phi_set, v); - // Pretend we don't have a cache entry for this name until - // we're done with all PHIs. - bitmap_clear_bit (m_has_cache_entry, v); - } + m_cache.set_range (name, r); } - bitmap_ior_into (m_has_cache_entry, phi_set); } // Return TRUE if relations may be invalidated after crossing edge E. @@ -408,7 +371,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) { tree name = ssa_name (i); if (ssa_defined_in_bb (name, bb)) - clear_cache (name); + m_cache.clear_range (name); } // Solve dependencies defined in this block, starting with the PHIs... @@ -421,7 +384,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI && range_defined_in_block (r, name, bb)) - set_cache (r, name); + m_cache.set_range (name, r); } if (at_exit ()) @@ -457,7 +420,7 @@ path_range_query::compute_ranges_in_block (basic_block bb) if (get_cache (cached_range, name)) r.intersect (cached_range); - set_cache (r, name); + m_cache.set_range (name, r); if (DEBUG_SOLVER) { fprintf (dump_file, "outgoing_edge_range_p for "); @@ -500,7 +463,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb) r.set_varying (TREE_TYPE (name)); if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb)) - set_cache (r, name); + m_cache.set_range (name, r); } } diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h index 29e33c6c37b..34841e78c3d 100644 --- a/gcc/gimple-range-path.h +++ b/gcc/gimple-range-path.h @@ -54,9 +54,7 @@ private: path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } // Cache manipulation. - void set_cache (const vrange &r, tree name); bool get_cache (vrange &r, tree name); - void clear_cache (tree name); // Methods to compute ranges for the given path. bool range_defined_in_block (vrange &, tree name, basic_block bb); @@ -83,10 +81,7 @@ private: void move_next () { --m_pos; } // Range cache for SSA names. - ssa_cache *m_cache; - - // Set for each SSA that has an active entry in the cache. - bitmap m_has_cache_entry; + ssa_lazy_cache m_cache; // Path being analyzed. auto_vec m_path; diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h index 944e7692a0e..e3aa9475f5e 100644 --- a/gcc/gimple-range.h +++ b/gcc/gimple-range.h @@ -96,7 +96,7 @@ protected: void calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src); void check_taken_edge (edge e, fur_source &src); - ssa_cache global; + ssa_lazy_cache global; gori_compute m_gori; }; -- 2.39.2