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 4D36A3858280 for ; Tue, 5 Jul 2022 20:29:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4D36A3858280 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.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-34-pmQRdnMHP52CZoWmm_U1qg-1; Tue, 05 Jul 2022 16:29:05 -0400 X-MC-Unique: pmQRdnMHP52CZoWmm_U1qg-1 Received: by mail-qt1-f197.google.com with SMTP id q21-20020ac84115000000b0031bf60d9b35so10287970qtl.4 for ; Tue, 05 Jul 2022 13:29:04 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:cc:references:from:in-reply-to :content-transfer-encoding; bh=10Ft5xlUanIRHZefLnk/RJ3CeZFs1hiQx2/EY6yYI7M=; b=UUcWCTGYHTdiSgAGWTK4s9iGg4D6PqZeU++L5DPLJGRh/xm4hlssaqequ9CXb+oBGY T0aZoe/EgveekZzT9E8vHJawDfob3BoLNWPh3T/7e+5v7lxTT6DntvYlXNMJ+2DUcUd3 0WkV/7wkxuGXKdwTK+QQWEgRU+YznVOrSa3nfrqHxkL7aQQBr1KPtbZhtMGuSNWeVbNQ ssdaFXAyGDJPqWJ7eJgr5QpUWoxFK1cRVxds2UZfNhelx9AlXKzD0lpPc1miej0nZKaC g4fXBpSKi5/WffoY6wuvp4LY3YcfmA5MbXwnfi+Lz7zJMJrWOT+w/i1f8eyLR9MsLpwD wCtw== X-Gm-Message-State: AJIora/8nBCmUH28B1cxIM/ZUmFShFcYEBG6a3NVpd21ELM8w/wxK/sM 5eLrXyMayW2LVLyvIqMR2ScK4KNc4JsQtTr6EtigsuToFNRU7Kr9sR5mfv1J1PT5hGwXW1bscDu 38p1UOVI5xIEjsxgy4g== X-Received: by 2002:a05:620a:d83:b0:6a7:a68c:6118 with SMTP id q3-20020a05620a0d8300b006a7a68c6118mr24654871qkl.337.1657052944256; Tue, 05 Jul 2022 13:29:04 -0700 (PDT) X-Google-Smtp-Source: AGRyM1vLK0ieFQj+mjC3nBgO23NiqetoV37bFiiswv//V45W9NCdoSk0UVl7ofBmMZXWxB6LyeI8Cw== X-Received: by 2002:a05:620a:d83:b0:6a7:a68c:6118 with SMTP id q3-20020a05620a0d8300b006a7a68c6118mr24654854qkl.337.1657052943811; Tue, 05 Jul 2022 13:29:03 -0700 (PDT) Received: from [192.168.1.100] (130-44-159-43.s15913.c3-0.arl-cbr1.sbo-arl.ma.cable.rcncustomer.com. [130.44.159.43]) by smtp.gmail.com with ESMTPSA id br31-20020a05620a461f00b006af290182c8sm23230374qkb.86.2022.07.05.13.29.03 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 05 Jul 2022 13:29:03 -0700 (PDT) Message-ID: <07a63134-41bb-4467-57b3-59d514940fb7@redhat.com> Date: Tue, 5 Jul 2022 16:29:02 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: Re: [PATCH] c++: generic targs and identity substitution [PR105956] To: Patrick Palka Cc: gcc-patches@gcc.gnu.org References: <20220629174236.3390391-1-ppalka@redhat.com> <9bc79bbc-bbe5-e8c9-2d09-ff02308ec754@idea> From: Jason Merrill In-Reply-To: <9bc79bbc-bbe5-e8c9-2d09-ff02308ec754@idea> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-25.6 required=5.0 tests=BAYES_00, DKIM_INVALID, DKIM_SIGNED, GIT_PATCH_0, KAM_DMARC_NONE, KAM_DMARC_STATUS, NICE_REPLY_A, 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 20:29:08 -0000 On 7/5/22 10:06, Patrick Palka wrote: > 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. Hmm, when replacing a level of T... we start with a TREE_VEC containing an ARGUMENT_PACK around a TREE_VEC containing a PACK_EXPANSION, and substitution should replace that with the argument level, a TREE_VEC containing an ARGUMENT_PACK around a TREE_VEC containing an actual set of args, so reuse ought to be possible? > 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>; >> >> >