From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x236.google.com (mail-lj1-x236.google.com [IPv6:2a00:1450:4864:20::236]) by sourceware.org (Postfix) with ESMTPS id 8F8DE3858D20 for ; Wed, 31 May 2023 07:05:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 8F8DE3858D20 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-lj1-x236.google.com with SMTP id 38308e7fff4ca-2af189d323fso7595971fa.1 for ; Wed, 31 May 2023 00:05:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1685516716; x=1688108716; 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=tb3Ei0jP6vUxKxcYNgdCya2n8kexVQChMRs5UhakpoU=; b=c1CHnGJ+VwlEUAr6bZpsbE6sYbtMYqMUEHnnYWj1r0F3kGxyP3SP3p5p4FzFf9G9et AVuJz7jr9ZwneTcS0LesaBO1K7JtswIhs7TyEaUEbdx6lVnsPQWAQ5rXCxdhWh5nkpJN gvLA5Q1UbB0hw4x1WGndFFPZlgBCvr7NOso2UbHP+i7RjhIynzN0Z9S7VrsFCZ4Oa86Z Fdcf5yTApaafUt+W0EYn/RqWc4Ljl97nWL2vanXCaqWL16ilxr4lXGE2TMrUOChXN3fu hnyM8KsnWFpY4uf04wO6+t3sJeUVVFv6Xm6+iHgyxFUteONyXZNgaTELatxOtaC64XVz 4bZQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1685516716; x=1688108716; 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=tb3Ei0jP6vUxKxcYNgdCya2n8kexVQChMRs5UhakpoU=; b=U0uyQHaCkrvBMErWEKXVuhz5fN9XedmEhvXV8bhEcFZz8gaBMYvxuA0FzwqCRAyMpy TxEJtrvJ/sVbTSOEjCWKfZj2kbiYdCiABj1FiGu7atk9aSEcK4o8enMy4O2KgaOKra93 AEUp40n9+8kaQS0eHIxqsHvlzqk1rKfTcyqG+VnKQvu3XMiXUPVeW+NBz0w3O03vph05 3bBDfmE1Qj8jiGzRCed7+WAjMtOUbXYZY4n4WG8nTlehL4HE49+OwKnztJyAuaXA7kWq qfOWOHyZqqW1yEsZegc23Q4FbIo3/P3rd7ZiLU4VfdVGHMznBYsDwvi/MVGGRrrYg9l9 p/Kw== X-Gm-Message-State: AC+VfDzbEfafTD/KkHnJXIIJSQ7Is44PiyODPDJOaUd6e4HMV/nP8aHx H36eVOjxUFPd7P7GH04UGhVhR7ylko1s6OFI0cA= X-Google-Smtp-Source: ACHHUZ5AG/cnkPtuDAIoQ6rp9ek7/q0TQ9g0si/NYnQvnace4xQ1x7YOIrrdngaV817YCcHw8hUutbj9763a7wbYZdM= X-Received: by 2002:a05:651c:2044:b0:2af:222d:9695 with SMTP id t4-20020a05651c204400b002af222d9695mr4177542ljo.9.1685516715616; Wed, 31 May 2023 00:05:15 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Wed, 31 May 2023 09:03:02 +0200 Message-ID: Subject: Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS To: Jan Hubicka Cc: Martin Jambor , GCC Patches Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.5 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 Tue, May 30, 2023 at 4:21=E2=80=AFPM Jan Hubicka wrote: > > > 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 troub= le? > > Comments below ... > > It lives from ipa-cp time to WPA stream-out or IPA transform stage, > so memory consumption is a concern with -flto. > > > + 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. > > > > 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. Richard. > Honza > > > > > +} > > > 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, wi= dest_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, w= idest_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 T= S. */ > > > > > > 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 ip= a_node_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 descri= bed by > > > + THIS, return its index in the DECL_ARGUMENTS chain, using a pre= -computed > > > + hash map if avialable (which is pre-computed only if there are = many > > > + parameters). Can return -1 if param is static chain not repres= ented among > > > + DECL_ARGUMENTS. */ > > > + int get_param_index (const_tree fndecl, const_tree param) const; > > > + > > > + /* Assuming THIS describes FUNC and it has sufficiently many param= eters to > > > + justify the overhead, creat a has map from parameter trees to t= heir > > > + 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 o= f their > > > + indices. */ > > > + hash_map *m_tree_to_idx; > > > }; > > > > > > inline > > > -- > > > 2.40.1 > > >