From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x12e.google.com (mail-lf1-x12e.google.com [IPv6:2a00:1450:4864:20::12e]) by sourceware.org (Postfix) with ESMTPS id 07F02385696F for ; Tue, 30 May 2023 07:00:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 07F02385696F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-lf1-x12e.google.com with SMTP id 2adb3069b0e04-4f3b5881734so4577626e87.0 for ; Tue, 30 May 2023 00:00:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1685430057; x=1688022057; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=Y4kJ2y6juebhLG8o9amlS9X8cNR2kE3o1mieWYaxMMI=; b=SedQ1Zv3OC9z9ZPbRmFl9RTnadk9SMGSUQ0IziGfg8a9dHWljToxMtwac4PsQpPvcc JwXcq0AJ/lrzOEKKG+vG11FlzFd2ICB/Py1vmNOk6/37cxbkLRJ9exUI/7TnIecbsy/E lMjYpZ6ZFBSXNpqfLgrsOBQVa9sWBLb73U24mvnOkgr5PKpGWHXylYmcbKL6GOprC52/ Qlpu/jhljIChpjgNDt1+jGj55FLyYi+avZ0IOU8cQJ8wtZe6dJLQMsZnHFQrhJwXbGg1 osZy81wkD77yORKSDtEnRUY10RQdsTVY/oPWuUL5UDbCOpQ6HUwcHGUYK0qpgMgYq6Iw icTg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685430057; x=1688022057; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Y4kJ2y6juebhLG8o9amlS9X8cNR2kE3o1mieWYaxMMI=; b=awQXErUbcNqO0hhbElN9/WIEbY520XgKWEiFf2j+EJa63AaIFr65lXn1iW275TxBEj 31WQlY0La2z9uYeXvV773CwGl4po0ldRvas01PHYVnFHX3iO0poFNM8IellN8SwMwkq9 0xJGEA/SoPLXRBE/b7rQDK8hsvqc8JJy6zCFZQf48LvcQ/43CJiGv0lYao0HfK7eWHG9 89+S74q3a/jYWidrGUnbKUdCJYrr1M6gUkQOKE7y+hsbR5sLDCIHTfAlBtNxl4lY64Jt K0fQiCXV+mPEFhBHSOzpAFfEwMdDh26n9HK1pBnl5baRzQJXHZso/Qmg0EVqdHJNkJOJ eYtg== X-Gm-Message-State: AC+VfDxBIZIMaEppUxEaABXNW3ldIbrdJvHA056pSCJan5D4r9dCWwN2 U0pHztN6lp/SLD1+3e0jBzjArDP7LOo3FRXOZ5I= X-Google-Smtp-Source: ACHHUZ7w6YcYpoSkekae5hEM8JB1FNs6X9JS1cnVAd5nCyxaICpftCk/H379tByBqXcaPq05uaSWwkcTl4iQypYJhLE= X-Received: by 2002:a2e:6a09:0:b0:2ad:98a6:4af0 with SMTP id f9-20020a2e6a09000000b002ad98a64af0mr263061ljc.23.1685430057250; Tue, 30 May 2023 00:00:57 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Tue, 30 May 2023 08:58:45 +0200 Message-ID: Subject: Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS To: Martin Jambor Cc: GCC Patches , Jan Hubicka Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,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: On Mon, May 29, 2023 at 6:20=E2=80=AFPM Martin Jambor wro= te: > > 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 trouble? Comments below ... > Bootstrapped, tested and LTO bootstrapped on x86_64-linux, both as-is > and with themagical constant dropped to 4 so that the has lookup path > is also well excercised. OK for master? > > Thanks, > > Martin > > > gcc/ChangeLog: > > 2023-05-26 Martin Jambor > > * ipa-prop.h (struct ipcp_transformation): Rearrange members > according to C++ class coding convention, add m_tree_to_idx, > get_param_index and maybe_create_parm_idx_map. > * ipa-cp.cc (ipcp_transformation::get_param_index): New function. > (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 NU= LL. > (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 | 45 +++++++++++++++++++++++++++++++++++++++++++++ > gcc/ipa-prop.cc | 44 +++++++++++++++++++------------------------- > gcc/ipa-prop.h | 33 +++++++++++++++++++++++++-------- > 3 files changed, 89 insertions(+), 33 deletions(-) > > diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc > index 0f37bb5e336..9f8b07b2398 100644 > --- a/gcc/ipa-cp.cc > +++ b/gcc/ipa-cp.cc > @@ -6761,3 +6761,48 @@ 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= THIS, > + return its index in the DECL_ARGUMENTS chain, using a pre-computed ha= sh map > + if avialable (which is pre-computed only if there are many parameters= ). Can > + return -1 if param is static chain not represented among DECL_ARGUMEN= TS. */ > + > +int > +ipcp_transformation::get_param_index (const_tree fndecl, const_tree para= m) const > +{ > + gcc_assert (TREE_CODE (param) =3D=3D PARM_DECL); > + if (m_tree_to_idx) > + { > + unsigned *pr =3D m_tree_to_idx->get(param); > + if (!pr) > + { > + gcc_assert (DECL_STATIC_CHAIN (fndecl)); > + return -1; > + } > + return (int) *pr; > + } > + > + unsigned index =3D 0; > + for (tree p =3D DECL_ARGUMENTS (fndecl); p; p =3D DECL_CHAIN (p), inde= x++) > + if (p =3D=3D param) > + return (int) index; > + > + gcc_assert (DECL_STATIC_CHAIN (fndecl)); > + return -1; > +} > + > +/* Assuming THIS describes FNDECL and it has sufficiently many parameter= s to > + justify the overhead, creat a has map from parameter trees to their > + indices. */ > +void > +ipcp_transformation::maybe_create_parm_idx_map (tree fndecl) > +{ > + int c =3D count_formal_params (fndecl); > + if (c < 32) > + return; > + > + 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), inde= x++) > + 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 lo= ad factor of at most 3/4 upon insertion. But - I wonder if a UID sorted array isn't a very much better data structure for this? That is, a vec >? > +} > 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= _int *mask) > if (!ts || vec_safe_length (ts->bits) =3D=3D 0) > return false; > > - 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, wides= t_int *mask) > return true; > } > > - > -/* Update bits info of formal parameters as described in > - ipcp_transformation. */ > +/* Update bits info of formal parameters of NODE as described in TS. */ > > 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) > } > } > > -/* Update value range of formal parameters as described in > - ipcp_transformation. */ > +/* Update value range of formal parameters of NODE as described in TS. = */ > > 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 ()); > > - 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..211b12ff6b3 100644 > --- a/gcc/ipa-prop.h > +++ b/gcc/ipa-prop.h > @@ -925,16 +925,10 @@ ipa_is_param_used_by_polymorphic_call (class ipa_no= de_params *info, int i) > > 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_tree_to_idx (nullptr) > { } > > /* Default destructor. */ > @@ -944,6 +938,29 @@ 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-com= puted > + hash map if avialable (which is pre-computed only if there are many > + parameters). Can return -1 if param is static chain not represente= d among > + DECL_ARGUMENTS. */ > + int get_param_index (const_tree fndecl, const_tree param) const; > + > + /* Assuming THIS describes FUNC and it has sufficiently many parameter= s to > + justify the overhead, creat a has map from parameter trees to their > + indices. */ > + > + 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, a hash map to speed-up look-ups of th= eir > + indices. */ > + hash_map *m_tree_to_idx; > }; > > inline > -- > 2.40.1 >