From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 857CD3858292 for ; Tue, 5 Jul 2022 14:06:45 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 857CD3858292 Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-446-gyCcwatKN1itUcSUola26A-1; Tue, 05 Jul 2022 10:06:44 -0400 X-MC-Unique: gyCcwatKN1itUcSUola26A-1 Received: by mail-qk1-f200.google.com with SMTP id bl27-20020a05620a1a9b00b0069994eeb30cso11439531qkb.11 for ; Tue, 05 Jul 2022 07:06:44 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:date:to:cc:subject:in-reply-to:message-id :references:mime-version; bh=fyYUFitv+Nfa014vWzhvA5ysHdvHNHFAwpy1y+ogQuY=; b=j8UT+6At9nprhCD2+ri4ibpOEsZq27zRJgfnTOY8ClzBxIPHsiv0PQgKy6kCoZtWeF akosJXN7rXiux1+xpqZgi6Q/czeLHQdEtqVEJhZLijsLOYAvDnDKAxrZNuPtTQ96QbwQ tTy8cJqBcpykMOD5wR82WX8Xrk7pYHZLd4lNa1LComGf4qnpDyxHyykm0EHpUMAMoBo7 prT+SUaU4vE+oPpSbvjWIgZHdIUCjnrGz0dWM9sLQPvs4jewso7AME0TRhwArWrJJ+3w 6KtFIvjbp/rQS4JyPsOrZowD690Zp2aLNI+v5A2OztihJrJPKyhx50BRXKo0xVs6sTEY ekNg== X-Gm-Message-State: AJIora/CChGh+isiOrKzKnrY0ikSqYmzqJ7V3S+7yzy1ze/JnXeknmzh FaFwdFIR3csjV2TU5e55L3N+TaBjWGn8w9CqvYZwjSEfzNby9F5Mnx8bWJoAGpB75nV14W4yQmy gL1+yjBQhgWP4Vzvr9g== X-Received: by 2002:a05:620a:4101:b0:6b2:6e4b:cfe8 with SMTP id j1-20020a05620a410100b006b26e4bcfe8mr11328688qko.411.1657030003192; Tue, 05 Jul 2022 07:06:43 -0700 (PDT) X-Google-Smtp-Source: AGRyM1v2XaJjob4vJEb9bNzhfk75SxQNeCMOBtuDgqMqDZXa/J+6ra+MYpIe7ECdozJrRdpsJIU9pw== X-Received: by 2002:a05:620a:4101:b0:6b2:6e4b:cfe8 with SMTP id j1-20020a05620a410100b006b26e4bcfe8mr11328618qko.411.1657030002543; Tue, 05 Jul 2022 07:06:42 -0700 (PDT) Received: from [192.168.1.130] (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id u12-20020a05620a454c00b006afd667535asm17861603qkp.83.2022.07.05.07.06.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 05 Jul 2022 07:06:26 -0700 (PDT) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Tue, 5 Jul 2022 10:06:19 -0400 (EDT) To: Jason Merrill cc: Patrick Palka , gcc-patches@gcc.gnu.org Subject: Re: [PATCH] c++: generic targs and identity substitution [PR105956] In-Reply-To: Message-ID: <9bc79bbc-bbe5-e8c9-2d09-ff02308ec754@idea> References: <20220629174236.3390391-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-24.4 required=5.0 tests=BAYES_00, DKIM_INVALID, DKIM_SIGNED, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 05 Jul 2022 14:06:49 -0000 On Fri, 1 Jul 2022, Jason Merrill wrote: > On 6/29/22 13:42, Patrick Palka wrote: > > In r13-1045-gcb7fd1ea85feea I assumed that substitution into generic > > DECL_TI_ARGS corresponds to an identity mapping of the given arguments, > > and hence its safe to always elide such substitution. But this PR > > demonstrates that such a substitution isn't always the identity mapping, > > in particular when there's an ARGUMENT_PACK_SELECT argument, which gets > > handled specially during substitution: > > > > * when substituting an APS into a template parameter, we strip the > > APS to its underlying argument; > > * and when substituting an APS into a pack expansion, we strip the > > APS to its underlying argument pack. > > Ah, right. For instance, in variadic96.C we have > > 10 template < typename... T > > 11 struct derived > 12 : public base< T, derived< T... > >... > > so when substituting into the base-specifier, we're approaching it from the > outside in, so when we get to the inner T... we need some way to find the T > pack again. It might be possible to remove the need for APS by substituting > inner pack expansions before outer ones, which could improve worst-case > complexity, but I don't know how relevant that is in real code; I imagine most > inner pack expansions are as simple as this one. Aha, that makes sense. > > > In this testcase, when expanding the pack expansion pattern (idx + Ns)... > > with Ns={0,1}, we specialize idx twice, first with Ns=APS<0,{0,1}> and > > then Ns=APS<1,{0,1}>. The DECL_TI_ARGS of idx are the generic template > > arguments of the enclosing class template impl, so before r13-1045, > > we'd substitute into its DECL_TI_ARGS which gave Ns={0,1} as desired. > > But after r13-1045, we elide this substitution and end up attempting to > > hash the original Ns argument, an APS, which ICEs. > > > > So this patch partially reverts this part of r13-1045. I considered > > using preserve_args in this case instead, but that'd break the > > static_assert in the testcase because preserve_args always strips APS to > > its underlying argument, but here we want to strip it to its underlying > > argument pack, so we'd incorrectly end up forming the specializations > > impl<0>::idx and impl<1>::idx instead of impl<0,1>::idx. > > > > Although we can't elide the substitution into DECL_TI_ARGS in light of > > ARGUMENT_PACK_SELECT, it should still be safe to elide template argument > > coercion in the case of a non-template decl, which this patch preserves. > > > > It's unfortunate that we need to remove this optimization just because > > it doesn't hold for one special tree code. So this patch implements a > > heuristic in tsubst_template_args to avoid allocating a new TREE_VEC if > > the substituted elements are identical to those of a level from ARGS. > > It turns out that about 30% of all calls to tsubst_template_args benefit > > from this optimization, and it reduces memory usage by about 1.5% for > > e.g. stdc++.h (relative to r13-1045). (This is the maybe_reuse stuff, > > the rest of the changes to tsubst_template_args are just drive-by > > cleanups.) > > > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for > > trunk? Patch generated with -w to ignore noisy whitespace changes. > > > > PR c++/105956 > > > > gcc/cp/ChangeLog: > > > > * pt.cc (tsubst_template_args): Move variable declarations > > closer to their first use. Replace 'orig_t' with 'r'. Rename > > 'need_new' to 'const_subst_p'. Heuristically detect if the > > substituted elements are identical to that of a level from > > 'args' and avoid allocating a new TREE_VEC if so. > > (tsubst_decl) : Revert > > r13-1045-gcb7fd1ea85feea change for avoiding substitution into > > DECL_TI_ARGS, but still avoid coercion in this case. > > > > gcc/testsuite/ChangeLog: > > > > * g++.dg/cpp0x/variadic183.C: New test. > > --- > > gcc/cp/pt.cc | 113 ++++++++++++++--------- > > gcc/testsuite/g++.dg/cpp0x/variadic183.C | 14 +++ > > 2 files changed, 85 insertions(+), 42 deletions(-) > > create mode 100644 gcc/testsuite/g++.dg/cpp0x/variadic183.C > > > > diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc > > index 8672da123f4..7898834faa6 100644 > > --- a/gcc/cp/pt.cc > > +++ b/gcc/cp/pt.cc > > @@ -27,6 +27,7 @@ along with GCC; see the file COPYING3. If not see > > Fixed by: C++20 modules. */ > > #include "config.h" > > +#define INCLUDE_ALGORITHM // for std::equal > > #include "system.h" > > #include "coretypes.h" > > #include "cp-tree.h" > > @@ -13544,17 +13545,22 @@ tsubst_argument_pack (tree orig_arg, tree args, > > tsubst_flags_t complain, > > tree > > tsubst_template_args (tree t, tree args, tsubst_flags_t complain, tree > > in_decl) > > { > > - tree orig_t = t; > > - int len, need_new = 0, i, expanded_len_adjust = 0, out; > > - tree *elts; > > - > > if (t == error_mark_node) > > return error_mark_node; > > - len = TREE_VEC_LENGTH (t); > > - elts = XALLOCAVEC (tree, len); > > + const int len = TREE_VEC_LENGTH (t); > > + tree *elts = XALLOCAVEC (tree, len); > > + int expanded_len_adjust = 0; > > - for (i = 0; i < len; i++) > > + /* True iff no element of T was changed by the substitution. */ > > + bool const_subst_p = true; > > + > > + /* If MAYBE_REUSE is non-NULL, as an optimization we'll try to reuse and > > + return this TREE_VEC instead of allocating a new one if possible. > > This > > + will either be ARGS or a level from ARGS. */ > > + tree maybe_reuse = NULL_TREE; > > + > > + for (int i = 0; i < len; i++) > > { > > tree orig_arg = TREE_VEC_ELT (t, i); > > tree new_arg; > > @@ -13580,56 +13586,90 @@ tsubst_template_args (tree t, tree args, > > tsubst_flags_t complain, tree in_decl) > > else if (ARGUMENT_PACK_P (orig_arg)) > > new_arg = tsubst_argument_pack (orig_arg, args, complain, in_decl); > > else > > + { > > new_arg = tsubst_template_arg (orig_arg, args, complain, in_decl); > > + /* If T heuristically appears to be a set of generic template > > + arguments, set MAYBE_REUSE to the corresponding level from > > + ARGS. */ > > + if (maybe_reuse == NULL_TREE && orig_arg != NULL_TREE) > > + { > > + if (TEMPLATE_PARM_P (orig_arg)) > > + { > > This doesn't handle the case of variadic template parameters, which are > represented in the generic args with a pack expansion. If this is a choice, > there should be a comment about it. AFAICT substituting such a pack expansion will never be an identity transform -- the relevant targ during tsubst_pack_expansion will be an ARGUMENT_PACK, and we'll return the TREE_VEC from that ARGUMENT_PACK instead of the ARGUMENT_PACK itself, so there's no way we can reuse (a level from) 'args' in this case. So variadic template parameters act as an optimization barrier here unfortunately. I can add a comment to that effect, and perhaps explicitly give up in this case by also setting maybe_reuse to error_mark_node in the PACK_EXPANSION_P branch of tsubst_template_args? > > > + int level, index; > > + template_parm_level_and_index (orig_arg, &level, &index); > > + if (index == i && TMPL_ARGS_DEPTH (args) >= level) > > + maybe_reuse = TMPL_ARGS_LEVEL (args, level); > > + else > > + maybe_reuse = error_mark_node; > > + } > > + else > > + /* T is not a set of generic template arguments; use > > + error_mark_node to denote this. */ > > + maybe_reuse = error_mark_node; > > + } > > + } > > + > > if (new_arg == error_mark_node) > > return error_mark_node; > > elts[i] = new_arg; > > if (new_arg != orig_arg) > > - need_new = 1; > > + const_subst_p = false; > > } > > - if (!need_new) > > + if (const_subst_p) > > return t; > > + /* If ARGS and T are both multi-level, then substituted T may be > > + identical to ARGS (if each level was pairwise identical). */ > > + if (maybe_reuse == NULL_TREE > > + && TMPL_ARGS_HAVE_MULTIPLE_LEVELS (t) > > + && TMPL_ARGS_HAVE_MULTIPLE_LEVELS (args)) > > + maybe_reuse = args; > > + > > + /* Return MAYBE_REUSE and avoid allocating a new TREE_VEC if the > > substituted > > + result is identical to it. */ > > + if (NON_ERROR (maybe_reuse) != NULL_TREE > > + && TREE_VEC_LENGTH (maybe_reuse) == len > > + && std::equal (elts, elts+len, TREE_VEC_BEGIN (maybe_reuse))) > > + return maybe_reuse; > > + > > /* Make space for the expanded arguments coming from template > > argument packs. */ > > - t = make_tree_vec (len + expanded_len_adjust); > > - /* ORIG_T can contain TREE_VECs. That happens if ORIG_T contains the > > + tree r = make_tree_vec (len + expanded_len_adjust); > > + /* T can contain TREE_VECs. That happens if T contains the > > arguments for a member template. > > - In that case each TREE_VEC in ORIG_T represents a level of template > > - arguments, and ORIG_T won't carry any non defaulted argument count. > > + In that case each TREE_VEC in T represents a level of template > > + arguments, and T won't carry any non defaulted argument count. > > It will rather be the nested TREE_VECs that will carry one. > > - In other words, ORIG_T carries a non defaulted argument count only > > + In other words, T carries a non defaulted argument count only > > if it doesn't contain any nested TREE_VEC. */ > > - if (NON_DEFAULT_TEMPLATE_ARGS_COUNT (orig_t)) > > + if (NON_DEFAULT_TEMPLATE_ARGS_COUNT (t)) > > { > > - int count = GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (orig_t); > > + int count = GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (t); > > count += expanded_len_adjust; > > - SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (t, count); > > + SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (r, count); > > } > > - for (i = 0, out = 0; i < len; i++) > > + for (int i = 0, out = 0; i < len; i++) > > { > > - tree orig_arg = TREE_VEC_ELT (orig_t, i); > > + tree orig_arg = TREE_VEC_ELT (t, i); > > if (orig_arg > > && (PACK_EXPANSION_P (orig_arg) || ARGUMENT_PACK_P (orig_arg)) > > && TREE_CODE (elts[i]) == TREE_VEC) > > { > > - int idx; > > - > > /* Now expand the template argument pack "in place". */ > > - for (idx = 0; idx < TREE_VEC_LENGTH (elts[i]); idx++, out++) > > - TREE_VEC_ELT (t, out) = TREE_VEC_ELT (elts[i], idx); > > + for (int idx = 0; idx < TREE_VEC_LENGTH (elts[i]); idx++, out++) > > + TREE_VEC_ELT (r, out) = TREE_VEC_ELT (elts[i], idx); > > } > > else > > { > > - TREE_VEC_ELT (t, out) = elts[i]; > > + TREE_VEC_ELT (r, out) = elts[i]; > > out++; > > } > > } > > - return t; > > + return r; > > } > > /* Substitute ARGS into one level PARMS of template parameters. */ > > @@ -14965,32 +15005,21 @@ tsubst_decl (tree t, tree args, tsubst_flags_t > > complain) > > if (!spec) > > { > > - int args_depth = TMPL_ARGS_DEPTH (args); > > - int parms_depth = TMPL_ARGS_DEPTH (DECL_TI_ARGS (t)); > > tmpl = DECL_TI_TEMPLATE (t); > > gen_tmpl = most_general_template (tmpl); > > - if (args_depth == parms_depth > > - && !PRIMARY_TEMPLATE_P (gen_tmpl)) > > - /* The DECL_TI_ARGS in this case are the generic template > > - arguments for the enclosing class template, so we can > > - shortcut substitution (which would just be the identity > > - mapping). */ > > - argvec = args; > > - else > > - { > > argvec = tsubst (DECL_TI_ARGS (t), args, complain, in_decl); > > - /* Coerce the innermost arguments again if necessary. If > > - there's fewer levels of args than of parms, then the > > - substitution could not have changed the innermost args > > - (modulo level lowering). */ > > - if (args_depth >= parms_depth && argvec != > > error_mark_node) > > + if (argvec != error_mark_node > > + && PRIMARY_TEMPLATE_P (gen_tmpl) > > + && TMPL_ARGS_DEPTH (args) >= TMPL_ARGS_DEPTH (argvec)) > > + /* We're fully specializing a template declaration, so > > + we need to coerce the innermost arguments corresponding > > + to the template. */ > > argvec = (coerce_innermost_template_parms > > (DECL_TEMPLATE_PARMS (gen_tmpl), > > argvec, t, complain, > > /*all*/true, /*defarg*/true)); > > if (argvec == error_mark_node) > > RETURN (error_mark_node); > > - } > > hash = spec_hasher::hash (gen_tmpl, argvec); > > spec = retrieve_specialization (gen_tmpl, argvec, hash); > > } > > diff --git a/gcc/testsuite/g++.dg/cpp0x/variadic183.C > > b/gcc/testsuite/g++.dg/cpp0x/variadic183.C > > new file mode 100644 > > index 00000000000..3938e52e0e7 > > --- /dev/null > > +++ b/gcc/testsuite/g++.dg/cpp0x/variadic183.C > > @@ -0,0 +1,14 @@ > > +// PR c++/105956 > > +// { dg-do compile { target c++11 } } > > + > > +template struct list; > > + > > +template struct impl { > > + static const int idx = 0; > > + using type = list<(idx + Ns)...>; > > + > > + static constexpr const int* a[2] = {(Ns, &idx)...}; > > + static_assert(a[0] == &idx && a[1] == &idx, ""); > > +}; > > + > > +template struct impl<0, 1>; > >