From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 184E9385734F for ; Wed, 31 May 2023 16:08:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 184E9385734F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 2AFB521958; Wed, 31 May 2023 16:08:11 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1685549291; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Wz0Qof76myUIjC8icgcDW/37i+6GDBtANG99X88uZQg=; b=XbBpZYAnhyOT9/5MtkuQOA2Jd79k84QxO5Kuhl8bkHQa20RF7iejGufuLgaX7MOj+IwSxU 9PLlBTymSAw5BojNu+NjDG+wyjzWn3pToQ9C96LfRw26RH2mR98XZc4XsCGhqZsmm2kx75 neyePzQUNHhXJ43SQN0yzsy3rOG4BbM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1685549291; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Wz0Qof76myUIjC8icgcDW/37i+6GDBtANG99X88uZQg=; b=MkDpGyvgllgByA+WIOp6QgtkIC+ie41xBum4f/dBWvHaYSGkRDwgQGFQRdK6tv8PfJiAjm 2ANbsadWlJws21DA== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 1B2F5138E8; Wed, 31 May 2023 16:08:11 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id 9a2gButwd2RCXgAAMHmgww (envelope-from ); Wed, 31 May 2023 16:08:11 +0000 From: Martin Jambor To: Richard Biener , Jan Hubicka Cc: GCC Patches Subject: Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS In-Reply-To: References: User-Agent: Notmuch/0.37 (https://notmuchmail.org) Emacs/28.2 (x86_64-suse-linux-gnu) Date: Wed, 31 May 2023 18:08:10 +0200 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,SPF_HELO_NONE,SPF_SOFTFAIL,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 List-Id: Hello, On Wed, May 31 2023, Richard Biener wrote: > On Tue, May 30, 2023 at 4:21=E2=80=AFPM Jan Hubicka wrot= e: >> >> > On Mon, May 29, 2023 at 6:20=E2=80=AFPM Martin Jambor wrote: >> > > >> > > Hi, >> > > >> > > there have been concerns that linear searches through DECL_ARGUMENTS >> > > that are often necessary to compute the index of a particular >> > > PARM_DECL which is the key to results of IPA-CP can happen often >> > > enough to be a compile time issue, especially if we plug the results >> > > into value numbering, as I intend to do with a follow-up patch. >> > > >> > > This patch creates a hash map to do the look-up for all functions >> > > which have some information discovered by IPA-CP and which have 32 >> > > parameters or more. 32 is a hard-wired magical constant here to >> > > capture the trade-off between the memory allocation overhead and >> > > length of the linear search. I do not think it is worth making it a >> > > --param but if people think it appropriate, I can turn it into one. >> > >> > Since ipcp_transformation is short-lived (is it?) is it worth the trou= ble? >> > Comments below ... >> >> It lives from ipa-cp time to WPA stream-out or IPA transform stage, >> so memory consumption is a concern with -flto. It lives longer, until the function is finished, it holds the information we want to use during PRE, after all (and Honza also already added queries to it to tree-ssa-ccp.cc though those probably could be avoided). The proposed mapping for long chains would only be created in the transformation IPA-CP hook, so would only live in LTRANS and only throughout the compilation of a single function. (But I am adding a pointer to the transformation summary of all.) >> > > + m_tree_to_idx =3D hash_map::create_ggc (c); >> > > + unsigned index =3D 0; >> > > + for (tree p =3D DECL_ARGUMENTS (fndecl); p; p =3D DECL_CHAIN (p),= index++) >> > > + m_tree_to_idx->put (p, index); >> > >> > I think allocating the hash-map with 'c' for some numbers (depending >> > on the "prime" >> > chosen) will necessarily cause re-allocation of the hash since we keep= a load >> > factor of at most 3/4 upon insertion. Oh, right. >> > >> > But - I wonder if a UID sorted array isn't a very much better data >> > structure for this? >> > That is, a vec >? >> >> Yeah, I was thinking along this lines too. >> Having field directly in PARM_DECL node would be probably prettiest. >> In general this is probably not that important as wast amount of time we >> have few parameters and linear lookup is just fine. > > There is 6 bits of DECL_OFFSET_ALIGN that could be re-purposed, but > 64 parameters is a bit low. _Maybe_ PARM_DECL doesn't need any of > the tree_base bits so could use the full word for sth else as well ... > > I also though it might be interesting to only record PARM_DECLs that > we have interesting info for and skip VARYING ones. So with an > indirection DECL_OFFSET_ALIGN -> index to non-varying param or > -1 the encoding space could shrink. > > But still using a vec<> looks like a straight-forward improvement here. Yeah, 64 parameters seems too tight. I guess a testcase in which we would record information for that many parameters would be quite artificial, but I can imagine something like that in machine generated code. Below is the patch based on DECL_UIDs in a vector. The problem with std::pair is that it is not GC-friendly and the transformation summary unfortunately needs to live in GC. So I added a simple GTY marked structure. Bootstrapped, tested and (together with the subsequent patch) LTO bootstrapped on an x86_64-linux, as is and with lower threshold to create the mapping. OK for master now? Thanks, Martin Subject: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUME= NTS There have been concerns that linear searches through DECL_ARGUMENTS that are often necessary to compute the index of a particular PARM_DECL which is the key to results of IPA-CP can happen often enough to be a compile time issue, especially if we plug the results into value numbering, as I intend to do with a follow-up patch. This patch creates a vector sorted according to PARM_DECLs to do the look-up for all functions which have some information discovered by IPA-CP and which have 32 parameters or more. 32 is a hard-wired magical constant here to capture the trade-off between the memory allocation overhead and length of = the linear search. I do not think it is worth making it a --param but if people think it appropriate, I can turn it into one. gcc/ChangeLog: 2023-05-31 Martin Jambor * ipa-prop.h (ipa_uid_to_idx_map_elt): New type. (struct ipcp_transformation): Rearrange members according to C++ class coding convention, add m_uid_to_idx, get_param_index and maybe_create_parm_idx_map. * ipa-cp.cc (ipcp_transformation::get_param_index): New function. (compare_uids): Likewise. (ipcp_transformation::maype_create_parm_idx_map): Likewise. * ipa-prop.cc (ipcp_get_parm_bits): Use get_param_index. (ipcp_update_bits): Accept TS as a parameter, assume it is not NULL. (ipcp_update_vr): Likewise. (ipcp_transform_function): Call, maybe_create_parm_idx_map of TS, bail out quickly if empty, pass it to ipcp_update_bits and ipcp_update_vr. --- gcc/ipa-cp.cc | 76 +++++++++++++++++++++++++++++++++++++++++++++++++ gcc/ipa-prop.cc | 44 +++++++++++++--------------- gcc/ipa-prop.h | 44 ++++++++++++++++++++++------ 3 files changed, 131 insertions(+), 33 deletions(-) diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc index 0f37bb5e336..fb069bf2319 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -6761,3 +6761,79 @@ ipa_cp_cc_finalize (void) orig_overall_size =3D 0; ipcp_free_transformation_sum (); } + +/* Given PARAM which must be a parameter of function FNDECL described by T= HIS, + return its index in the DECL_ARGUMENTS chain, using a pre-computed + DECL_UID-sorted vector if available (which is pre-computed only if ther= e are + many parameters). Can return -1 if param is static chain not represent= ed + among DECL_ARGUMENTS. */ + +int +ipcp_transformation::get_param_index (const_tree fndecl, const_tree param)= const +{ + gcc_assert (TREE_CODE (param) =3D=3D PARM_DECL); + if (m_uid_to_idx) + { + unsigned puid =3D DECL_UID (param); + const ipa_uid_to_idx_map_elt *res + =3D std::lower_bound (m_uid_to_idx->begin(), m_uid_to_idx->end (), puid, + [] (const ipa_uid_to_idx_map_elt &elt, unsigned uid) + { + return elt.uid < uid; + }); + if (res =3D=3D m_uid_to_idx->end () + || res->uid !=3D puid) + { + gcc_assert (DECL_STATIC_CHAIN (fndecl)); + return -1; + } + return res->index; + } + + unsigned index =3D 0; + for (tree p =3D DECL_ARGUMENTS (fndecl); p; p =3D DECL_CHAIN (p), index+= +) + if (p =3D=3D param) + return (int) index; + + gcc_assert (DECL_STATIC_CHAIN (fndecl)); + return -1; +} + +/* Helper function to qsort a vector of ipa_uid_to_idx_map_elt elements + according to the uid. */ + +static int +compare_uids (const void *a, const void *b) +{ + const ipa_uid_to_idx_map_elt *e1 =3D (const ipa_uid_to_idx_map_elt *) a; + const ipa_uid_to_idx_map_elt *e2 =3D (const ipa_uid_to_idx_map_elt *) b; + if (e1->uid < e2->uid) + return -1; + if (e1->uid > e2->uid) + return 1; + gcc_unreachable (); +} + +/* Assuming THIS describes FNDECL and it has sufficiently many parameters = to + justify the overhead, create a DECL_UID-sorted vector to speed up mappi= ng + from parameters to their indices in DECL_ARGUMENTS chain. */ + +void +ipcp_transformation::maybe_create_parm_idx_map (tree fndecl) +{ + int c =3D count_formal_params (fndecl); + if (c < 32) + return; + + m_uid_to_idx =3D NULL; + vec_safe_reserve (m_uid_to_idx, c, true); + unsigned index =3D 0; + for (tree p =3D DECL_ARGUMENTS (fndecl); p; p =3D DECL_CHAIN (p), index+= +) + { + ipa_uid_to_idx_map_elt elt; + elt.uid =3D DECL_UID (p); + elt.index =3D index; + m_uid_to_idx->quick_push (elt); + } + m_uid_to_idx->qsort (compare_uids); +} diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc index ab6de9f10da..f0976e363f7 100644 --- a/gcc/ipa-prop.cc +++ b/gcc/ipa-prop.cc @@ -5776,16 +5776,9 @@ ipcp_get_parm_bits (tree parm, tree *value, widest_i= nt *mask) if (!ts || vec_safe_length (ts->bits) =3D=3D 0) return false; =20 - int i =3D 0; - for (tree p =3D DECL_ARGUMENTS (current_function_decl); - p !=3D parm; p =3D DECL_CHAIN (p)) - { - i++; - /* Ignore static chain. */ - if (!p) - return false; - } - + int i =3D ts->get_param_index (current_function_decl, parm); + if (i < 0) + return false; clone_info *cinfo =3D clone_info::get (cnode); if (cinfo && cinfo->param_adjustments) { @@ -5802,16 +5795,12 @@ ipcp_get_parm_bits (tree parm, tree *value, widest_= int *mask) return true; } =20 - -/* Update bits info of formal parameters as described in - ipcp_transformation. */ +/* Update bits info of formal parameters of NODE as described in TS. */ =20 static void -ipcp_update_bits (struct cgraph_node *node) +ipcp_update_bits (struct cgraph_node *node, ipcp_transformation *ts) { - ipcp_transformation *ts =3D ipcp_get_transformation_summary (node); - - if (!ts || vec_safe_length (ts->bits) =3D=3D 0) + if (vec_safe_is_empty (ts->bits)) return; vec &bits =3D *ts->bits; unsigned count =3D bits.length (); @@ -5913,14 +5902,12 @@ ipcp_update_bits (struct cgraph_node *node) } } =20 -/* Update value range of formal parameters as described in - ipcp_transformation. */ +/* Update value range of formal parameters of NODE as described in TS. */ =20 static void -ipcp_update_vr (struct cgraph_node *node) +ipcp_update_vr (struct cgraph_node *node, ipcp_transformation *ts) { - ipcp_transformation *ts =3D ipcp_get_transformation_summary (node); - if (!ts || vec_safe_length (ts->m_vr) =3D=3D 0) + if (vec_safe_is_empty (ts->m_vr)) return; const vec &vr =3D *ts->m_vr; unsigned count =3D vr.length (); @@ -5996,10 +5983,17 @@ ipcp_transform_function (struct cgraph_node *node) fprintf (dump_file, "Modification phase of node %s\n", node->dump_name ()); =20 - ipcp_update_bits (node); - ipcp_update_vr (node); ipcp_transformation *ts =3D ipcp_get_transformation_summary (node); - if (!ts || vec_safe_is_empty (ts->m_agg_values)) + if (!ts + || (vec_safe_is_empty (ts->m_agg_values) + && vec_safe_is_empty (ts->bits) + && vec_safe_is_empty (ts->m_vr))) + return 0; + + ts->maybe_create_parm_idx_map (cfun->decl); + ipcp_update_bits (node, ts); + ipcp_update_vr (node, ts); + if (vec_safe_is_empty (ts->m_agg_values)) return 0; param_count =3D count_formal_params (node->decl); if (param_count =3D=3D 0) diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index f306f8a377e..c570e8ec25a 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -921,20 +921,24 @@ ipa_is_param_used_by_polymorphic_call (class ipa_node= _params *info, int i) return (*info->descriptors)[i].used_by_polymorphic_call; } =20 +/* GTY-marked structure used to map DECL_UIDs of APRAMs to their indices in + their DECL_ARGUMENTs chain. */ +struct GTY(()) ipa_uid_to_idx_map_elt +{ + /* DECL_UID of the PARAM. */ + unsigned uid; + /* Its index in the DECL_ARGUMETs chain. */ + unsigned index; +}; + /* Structure holding information for the transformation phase of IPA-CP. = */ =20 struct GTY(()) ipcp_transformation { - /* Known aggregate values. */ - vec *m_agg_values; - /* Known bits information. */ - vec *bits; - /* Value range information. */ - vec *m_vr; - /* Default constructor. */ ipcp_transformation () - : m_agg_values (NULL), bits (NULL), m_vr (NULL) + : m_agg_values (nullptr), bits (nullptr), m_vr (nullptr), + m_uid_to_idx (nullptr) { } =20 /* Default destructor. */ @@ -944,6 +948,30 @@ struct GTY(()) ipcp_transformation vec_free (bits); vec_free (m_vr); } + + /* Given PARAM which must be a parameter of function FNDECL described by + THIS, return its index in the DECL_ARGUMENTS chain, using a pre-compu= ted + DECL_UID-sorted vector if available (which is pre-computed only if th= ere + are many parameters). Can return -1 if param is static chain not + represented among DECL_ARGUMENTS. */ + + int get_param_index (const_tree fndecl, const_tree param) const; + + /* Assuming THIS describes FNDECL and it has sufficiently many parameter= s to + justify the overhead, create a DECL_UID-sorted vector to speed up map= ping + from parameters to their indices in DECL_ARGUMENTS chain. */ + + void maybe_create_parm_idx_map (tree fndecl); + + /* Known aggregate values. */ + vec *m_agg_values; + /* Known bits information. */ + vec *bits; + /* Value range information. */ + vec *m_vr; + /* If there are many parameters, this is a vector sorted by their DECL_U= IDs + to map them to their indices in the DECL_ARGUMENT chain. */ + vec *m_uid_to_idx; }; =20 inline --=20 2.40.1