| Message ID | 20220629174236.3390391-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | c++: generic targs and identity substitution [PR105956] | expand |
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. > 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) <case TYPE_DECL, case VAR_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. > + 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<int... Ns> struct list; > + > +template<int... Ns> 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>;
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) <case TYPE_DECL, case VAR_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<int... Ns> struct list; > > + > > +template<int... Ns> 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>; > >
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) <case TYPE_DECL, case VAR_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<int... Ns> struct list; >>> + >>> +template<int... Ns> 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>; >> >> >
On Tue, 5 Jul 2022, Jason Merrill wrote: > 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) <case TYPE_DECL, case VAR_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? Ah, I think see what you mean. For that, I think it suffices to just handle in tsubst_template_args the case where we're substituting into a single-elt TREE_VEC such as {T...}. That'll allow us to reuse the inner TREE_VEC containing the actual set of args at least. And AFAICT that's the best we can do, since we'll always be creating a new ARGUMENT_PACK which doesn't appear in any other TREE_VEC we have at our disposal. So like this? I also added an assert that 'out' never exceeds 'len', and simplified the test orig_arg && (PACK_EXPANSION_P (orig_arg) || ARGUMENT_PACK_P (orig_arg)) && TREE_CODE (elts[i]) == TREE_VEC to just orig_arg && PACK_EXPANSION_P (orig_arg) && TREE_CODE (elts[i]) == TREE_VEC since substitution into an ARGUMENT_PACK will never yield a TREE_VEC. -- >8 -- Subject: [PATCH] c++: generic targs and identity substitution [PR105956] 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. Assert that 'out' doesn't exceed 'len', and remove useless ARGUMENT_PACK_P test. (tsubst_decl) <case TYPE_DECL, case VAR_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 | 128 +++++++++++++++-------- gcc/testsuite/g++.dg/cpp0x/variadic183.C | 14 +++ 2 files changed, 99 insertions(+), 43 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..c290174a390 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 the substituted result is identical to T. */ + bool const_subst_p = true; + + /* If MAYBE_REUSE is a TREE_VEC, 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,103 @@ 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. + Otherwise set it to error_mark_node. (Note that this doesn't + handle variadic template parameters, which are represented as a + generic arg by an ARGUMENT_PACK around a one-element TREE_VEC + containing a PACK_EXPANSION. We partially handle that case + later.) */ + if (maybe_reuse == NULL_TREE && orig_arg != NULL_TREE) + { + if (TEMPLATE_PARM_P (orig_arg)) + { + 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 + 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, the substituted result 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; + + /* If T consists of only a pack expansion for which substitution resulted + in a TREE_VEC of the expanded elements, then reuse that TREE_VEC instead + of effectively making a copy. */ + if (len == 1 + && PACK_EXPANSION_P (TREE_VEC_ELT (t, 0)) + && TREE_CODE (elts[0]) == TREE_VEC) + return elts[0]; + /* 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++) + + int out = 0; + for (int i = 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)) + && PACK_EXPANSION_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++; } } + gcc_assert (out <= TREE_VEC_LENGTH (r)); - return t; + return r; } /* Substitute ARGS into one level PARMS of template parameters. */ @@ -14965,32 +15018,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..27444ebb594 --- /dev/null +++ b/gcc/testsuite/g++.dg/cpp0x/variadic183.C @@ -0,0 +1,14 @@ +// PR c++/105956 +// { dg-do compile { target c++11 } } + +template<int...> struct list; + +template<int... Ns> 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>;
On 7/6/22 15:26, Patrick Palka wrote: > On Tue, 5 Jul 2022, Jason Merrill wrote: > >> 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) <case TYPE_DECL, case VAR_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? > > Ah, I think see what you mean. For that, I think it suffices to just > handle in tsubst_template_args the case where we're substituting into a > single-elt TREE_VEC such as {T...}. That'll allow us to reuse the inner > TREE_VEC containing the actual set of args at least. Sounds good. > And AFAICT that's > the best we can do, since we'll always be creating a new ARGUMENT_PACK > which doesn't appear in any other TREE_VEC we have at our disposal. Why always? Why can't tsubst_argument_pack recognize the {T...} case and return the corresponding ARGUMENT_PACK from args? template <class... Ts> struct A { A<Ts...>* a; }; A<int,char> a; With your patch, the substitution into A<Ts...> reuses the inner TREE_VEC, but why not reuse the ARGUMENT_PACK as well? And why not set maybe_reuse for the enclosing arg level? > So like this? I also added an assert that 'out' never exceeds 'len', > and simplified the test > > orig_arg > && (PACK_EXPANSION_P (orig_arg) || ARGUMENT_PACK_P (orig_arg)) > && TREE_CODE (elts[i]) == TREE_VEC > > to just > > orig_arg > && PACK_EXPANSION_P (orig_arg) > && TREE_CODE (elts[i]) == TREE_VEC > > since substitution into an ARGUMENT_PACK will never yield a TREE_VEC. > > -- >8 -- > > Subject: [PATCH] c++: generic targs and identity substitution [PR105956] > > 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. Assert that > 'out' doesn't exceed 'len', and remove useless ARGUMENT_PACK_P > test. > (tsubst_decl) <case TYPE_DECL, case VAR_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 | 128 +++++++++++++++-------- > gcc/testsuite/g++.dg/cpp0x/variadic183.C | 14 +++ > 2 files changed, 99 insertions(+), 43 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..c290174a390 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 the substituted result is identical to T. */ > + bool const_subst_p = true; > + > + /* If MAYBE_REUSE is a TREE_VEC, 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,103 @@ 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. > + Otherwise set it to error_mark_node. (Note that this doesn't > + handle variadic template parameters, which are represented as a > + generic arg by an ARGUMENT_PACK around a one-element TREE_VEC > + containing a PACK_EXPANSION. We partially handle that case > + later.) */ > + if (maybe_reuse == NULL_TREE && orig_arg != NULL_TREE) > + { > + if (TEMPLATE_PARM_P (orig_arg)) > + { > + 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 > + 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, the substituted result 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; > + > + /* If T consists of only a pack expansion for which substitution resulted > + in a TREE_VEC of the expanded elements, then reuse that TREE_VEC instead > + of effectively making a copy. */ > + if (len == 1 > + && PACK_EXPANSION_P (TREE_VEC_ELT (t, 0)) > + && TREE_CODE (elts[0]) == TREE_VEC) > + return elts[0]; > + > /* 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++) > + > + int out = 0; > + for (int i = 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)) > + && PACK_EXPANSION_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++; > } > } > + gcc_assert (out <= TREE_VEC_LENGTH (r)); > > - return t; > + return r; > } > > /* Substitute ARGS into one level PARMS of template parameters. */ > @@ -14965,32 +15018,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..27444ebb594 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/cpp0x/variadic183.C > @@ -0,0 +1,14 @@ > +// PR c++/105956 > +// { dg-do compile { target c++11 } } > + > +template<int...> struct list; > + > +template<int... Ns> 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>;
On Thu, 7 Jul 2022, Jason Merrill wrote: > On 7/6/22 15:26, Patrick Palka wrote: > > On Tue, 5 Jul 2022, Jason Merrill wrote: > > > > > 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) <case TYPE_DECL, case VAR_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? > > > > Ah, I think see what you mean. For that, I think it suffices to just > > handle in tsubst_template_args the case where we're substituting into a > > single-elt TREE_VEC such as {T...}. That'll allow us to reuse the inner > > TREE_VEC containing the actual set of args at least. > > Sounds good. > > > And AFAICT that's > > the best we can do, since we'll always be creating a new ARGUMENT_PACK > > which doesn't appear in any other TREE_VEC we have at our disposal. > > Why always? Why can't tsubst_argument_pack recognize the {T...} case and > return the corresponding ARGUMENT_PACK from args? > > template <class... Ts> struct A > { > A<Ts...>* a; > }; > > A<int,char> a; > > With your patch, the substitution into A<Ts...> reuses the inner TREE_VEC, but > why not reuse the ARGUMENT_PACK as well? And why not set maybe_reuse for the > enclosing arg level? D'oh, you're totally right, I didn't notice this opportunity. Here's a patch that makes tsubst_argument_pack reuse the ARGUMENT_PACK from 'args' when possible, and in turn makes tsubst_template_args reuse the enclosing arg level. Relative to the previous patch, this increases the % of calls to tsubst_template_args that benefit from this optimization a further 10% (30% -> 40%), and reduces memory usage for e.g. zip.cpp from range-v3 a further 2.5% (1.5% -> 4%). -- >8 -- Subject: [PATCH] c++: generic targs and identity substitution [PR105956] 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. 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 reverts that 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, and a similar heuristic for tsubst_argument_pack. It turns out that about 40% of all calls to tsubst_template_args benefit from this, and it reduces memory usage by about 4% for e.g. zip.cpp from range-v3 (relative to r13-1045) which more than makes up for the reversion. PR c++/105956 gcc/cp/ChangeLog: * pt.cc (template_arg_to_parm): Define. (tsubst_argument_pack): Try to reuse the corresponding ARGUMENT_PACK from 'args' when substituting into an ARGUMENT_PACK for a generic template argument. (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. Assert that 'out' never exceeds the length of the new TREE_VEC, and remove dead ARGUMENT_PACK_P test. (tsubst_decl) <case TYPE_DECL, case VAR_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 | 172 ++++++++++++++++------- gcc/testsuite/g++.dg/cpp0x/variadic183.C | 14 ++ 2 files changed, 138 insertions(+), 48 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..85f3462a0ac 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" @@ -4916,6 +4917,33 @@ template_parm_to_arg (tree t) return t; } +/* If T looks like a generic template argument produced by template_parm_to_arg, + return the corresponding template parameter, otherwise return NULL_TREE. */ + +static tree +template_arg_to_parm (tree t) +{ + if (t == NULL_TREE) + return NULL_TREE; + + if (ARGUMENT_PACK_P (t)) + { + tree args = ARGUMENT_PACK_ARGS (t); + if (TREE_VEC_LENGTH (args) == 1 + && PACK_EXPANSION_P (TREE_VEC_ELT (args, 0))) + { + t = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (args, 0)); + if (REFERENCE_REF_P (t)) + t = TREE_OPERAND (t, 0); + } + } + + if (TEMPLATE_PARM_P (t)) + return t; + + return NULL_TREE; +} + /* Given a single level of template parameters (a TREE_VEC), return it as a set of template arguments. */ @@ -13516,12 +13544,38 @@ tree tsubst_argument_pack (tree orig_arg, tree args, tsubst_flags_t complain, tree in_decl) { + /* This flag is used only during deduction, and we don't expect to + see such ARGUMENT_PACKs during substitution. */ + gcc_assert (!ARGUMENT_PACK_INCOMPLETE_P (orig_arg)); + /* Substitute into each of the arguments. */ tree pack_args = tsubst_template_args (ARGUMENT_PACK_ARGS (orig_arg), args, complain, in_decl); - tree new_arg = error_mark_node; - if (pack_args != error_mark_node) + if (pack_args == error_mark_node) + return error_mark_node; + + if (pack_args == ARGUMENT_PACK_ARGS (orig_arg)) + return orig_arg; + + /* If we're substituting into an ARGUMENT_PACK for a generic template + argument, we might be able to avoid allocating a new ARGUMENT_PACK + by reusing the corresponding ARGUMENT_PACK from ARGS if the + substituted result is identical to it. */ + if (tree parm = template_arg_to_parm (orig_arg)) { + int level, index; + template_parm_level_and_index (parm, &level, &index); + if (TMPL_ARGS_DEPTH (args) >= level) + if (tree arg = TMPL_ARG (args, level, index)) + if (TREE_CODE (arg) == TREE_CODE (orig_arg) + && ARGUMENT_PACK_ARGS (arg) == pack_args) + { + gcc_assert (!ARGUMENT_PACK_INCOMPLETE_P (arg)); + return arg; + } + } + + tree new_arg; if (TYPE_P (orig_arg)) { new_arg = cxx_make_type (TREE_CODE (orig_arg)); @@ -13532,10 +13586,7 @@ tsubst_argument_pack (tree orig_arg, tree args, tsubst_flags_t complain, new_arg = make_node (TREE_CODE (orig_arg)); TREE_CONSTANT (new_arg) = TREE_CONSTANT (orig_arg); } - ARGUMENT_PACK_ARGS (new_arg) = pack_args; - } - return new_arg; } @@ -13544,17 +13595,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 the substituted result is identical to T. */ + bool const_subst_p = true; + + /* If MAYBE_REUSE is a TREE_VEC, 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; @@ -13587,49 +13643,80 @@ tsubst_template_args (tree t, tree args, tsubst_flags_t complain, tree in_decl) 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 T appears to be a set of generic template arguments, set + MAYBE_REUSE to the corresponding level from ARGS. */ + if (tree parm = template_arg_to_parm (TREE_VEC_ELT (t, 0))) + { + int level, index; + template_parm_level_and_index (parm, &level, &index); + if (index == 0 && TMPL_ARGS_DEPTH (args) >= level) + maybe_reuse = TMPL_ARGS_LEVEL (args, level); + } + /* If ARGS and T are both multi-level, the substituted result may be + identical to ARGS (if each level was pairwise identical). */ + else if (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 (maybe_reuse != NULL_TREE + && TREE_VEC_LENGTH (maybe_reuse) == len + && std::equal (elts, elts+len, TREE_VEC_BEGIN (maybe_reuse))) + return maybe_reuse; + + /* If T consists of only a pack expansion for which substitution yielded + a TREE_VEC of the expanded elements, then reuse that TREE_VEC instead + of effectively making a copy. */ + if (len == 1 + && PACK_EXPANSION_P (TREE_VEC_ELT (t, 0)) + && TREE_CODE (elts[0]) == TREE_VEC) + return elts[0]; + /* 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++) + + int out = 0; + for (int i = 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)) + && PACK_EXPANSION_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++; } } + gcc_assert (out <= TREE_VEC_LENGTH (r)); - return t; + return r; } /* Substitute ARGS into one level PARMS of template parameters. */ @@ -14965,32 +15052,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..27444ebb594 --- /dev/null +++ b/gcc/testsuite/g++.dg/cpp0x/variadic183.C @@ -0,0 +1,14 @@ +// PR c++/105956 +// { dg-do compile { target c++11 } } + +template<int...> struct list; + +template<int... Ns> 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>;
On Thu, 7 Jul 2022, Patrick Palka wrote: > On Thu, 7 Jul 2022, Jason Merrill wrote: > > > On 7/6/22 15:26, Patrick Palka wrote: > > > On Tue, 5 Jul 2022, Jason Merrill wrote: > > > > > > > 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) <case TYPE_DECL, case VAR_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? > > > > > > Ah, I think see what you mean. For that, I think it suffices to just > > > handle in tsubst_template_args the case where we're substituting into a > > > single-elt TREE_VEC such as {T...}. That'll allow us to reuse the inner > > > TREE_VEC containing the actual set of args at least. > > > > Sounds good. > > > > > And AFAICT that's > > > the best we can do, since we'll always be creating a new ARGUMENT_PACK > > > which doesn't appear in any other TREE_VEC we have at our disposal. > > > > Why always? Why can't tsubst_argument_pack recognize the {T...} case and > > return the corresponding ARGUMENT_PACK from args? > > > > template <class... Ts> struct A > > { > > A<Ts...>* a; > > }; > > > > A<int,char> a; > > > > With your patch, the substitution into A<Ts...> reuses the inner TREE_VEC, but > > why not reuse the ARGUMENT_PACK as well? And why not set maybe_reuse for the > > enclosing arg level? > > D'oh, you're totally right, I didn't notice this opportunity. Here's a > patch that makes tsubst_argument_pack reuse the ARGUMENT_PACK from > 'args' when possible, and in turn makes tsubst_template_args reuse the > enclosing arg level. Relative to the previous patch, this increases > the % of calls to tsubst_template_args that benefit from this > optimization a further 10% (30% -> 40%), and reduces memory usage for > e.g. zip.cpp from range-v3 a further 2.5% (1.5% -> 4%). > > -- >8 -- > > Subject: [PATCH] c++: generic targs and identity substitution [PR105956] > > 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. > > 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 reverts that 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, > and a similar heuristic for tsubst_argument_pack. It turns out that > about 40% of all calls to tsubst_template_args benefit from this, and it > reduces memory usage by about 4% for e.g. zip.cpp from range-v3 (relative > to r13-1045) which more than makes up for the reversion. > > PR c++/105956 > > gcc/cp/ChangeLog: > > * pt.cc (template_arg_to_parm): Define. > (tsubst_argument_pack): Try to reuse the corresponding > ARGUMENT_PACK from 'args' when substituting into an > ARGUMENT_PACK for a generic template argument. > (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. Assert that > 'out' never exceeds the length of the new TREE_VEC, and remove > dead ARGUMENT_PACK_P test. > (tsubst_decl) <case TYPE_DECL, case VAR_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 | 172 ++++++++++++++++------- > gcc/testsuite/g++.dg/cpp0x/variadic183.C | 14 ++ > 2 files changed, 138 insertions(+), 48 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..85f3462a0ac 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" > @@ -4916,6 +4917,33 @@ template_parm_to_arg (tree t) > return t; > } > > +/* If T looks like a generic template argument produced by template_parm_to_arg, > + return the corresponding template parameter, otherwise return NULL_TREE. */ > + > +static tree > +template_arg_to_parm (tree t) > +{ > + if (t == NULL_TREE) > + return NULL_TREE; > + > + if (ARGUMENT_PACK_P (t)) > + { > + tree args = ARGUMENT_PACK_ARGS (t); > + if (TREE_VEC_LENGTH (args) == 1 > + && PACK_EXPANSION_P (TREE_VEC_ELT (args, 0))) > + { > + t = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (args, 0)); > + if (REFERENCE_REF_P (t)) > + t = TREE_OPERAND (t, 0); Whoops, we should look through REFERENCE_REF_P even in the non-variadic case to more closely mirror template_parm_to_arg, consider that fixed. > + } > + } > + > + if (TEMPLATE_PARM_P (t)) > + return t; > + > + return NULL_TREE; > +} > + > /* Given a single level of template parameters (a TREE_VEC), return it > as a set of template arguments. */ > > @@ -13516,12 +13544,38 @@ tree > tsubst_argument_pack (tree orig_arg, tree args, tsubst_flags_t complain, > tree in_decl) > { > + /* This flag is used only during deduction, and we don't expect to > + see such ARGUMENT_PACKs during substitution. */ > + gcc_assert (!ARGUMENT_PACK_INCOMPLETE_P (orig_arg)); > + > /* Substitute into each of the arguments. */ > tree pack_args = tsubst_template_args (ARGUMENT_PACK_ARGS (orig_arg), > args, complain, in_decl); > - tree new_arg = error_mark_node; > - if (pack_args != error_mark_node) > + if (pack_args == error_mark_node) > + return error_mark_node; > + > + if (pack_args == ARGUMENT_PACK_ARGS (orig_arg)) > + return orig_arg; > + > + /* If we're substituting into an ARGUMENT_PACK for a generic template > + argument, we might be able to avoid allocating a new ARGUMENT_PACK > + by reusing the corresponding ARGUMENT_PACK from ARGS if the > + substituted result is identical to it. */ > + if (tree parm = template_arg_to_parm (orig_arg)) > { > + int level, index; > + template_parm_level_and_index (parm, &level, &index); > + if (TMPL_ARGS_DEPTH (args) >= level) > + if (tree arg = TMPL_ARG (args, level, index)) > + if (TREE_CODE (arg) == TREE_CODE (orig_arg) > + && ARGUMENT_PACK_ARGS (arg) == pack_args) > + { > + gcc_assert (!ARGUMENT_PACK_INCOMPLETE_P (arg)); > + return arg; > + } > + } > + > + tree new_arg; > if (TYPE_P (orig_arg)) > { > new_arg = cxx_make_type (TREE_CODE (orig_arg)); > @@ -13532,10 +13586,7 @@ tsubst_argument_pack (tree orig_arg, tree args, tsubst_flags_t complain, > new_arg = make_node (TREE_CODE (orig_arg)); > TREE_CONSTANT (new_arg) = TREE_CONSTANT (orig_arg); > } > - > ARGUMENT_PACK_ARGS (new_arg) = pack_args; > - } > - > return new_arg; > } > > @@ -13544,17 +13595,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 the substituted result is identical to T. */ > + bool const_subst_p = true; > + > + /* If MAYBE_REUSE is a TREE_VEC, 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; > @@ -13587,49 +13643,80 @@ tsubst_template_args (tree t, tree args, tsubst_flags_t complain, tree in_decl) > > 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 T appears to be a set of generic template arguments, set > + MAYBE_REUSE to the corresponding level from ARGS. */ > + if (tree parm = template_arg_to_parm (TREE_VEC_ELT (t, 0))) > + { > + int level, index; > + template_parm_level_and_index (parm, &level, &index); > + if (index == 0 && TMPL_ARGS_DEPTH (args) >= level) > + maybe_reuse = TMPL_ARGS_LEVEL (args, level); > + } > + /* If ARGS and T are both multi-level, the substituted result may be > + identical to ARGS (if each level was pairwise identical). */ > + else if (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 (maybe_reuse != NULL_TREE > + && TREE_VEC_LENGTH (maybe_reuse) == len > + && std::equal (elts, elts+len, TREE_VEC_BEGIN (maybe_reuse))) > + return maybe_reuse; > + > + /* If T consists of only a pack expansion for which substitution yielded > + a TREE_VEC of the expanded elements, then reuse that TREE_VEC instead > + of effectively making a copy. */ > + if (len == 1 > + && PACK_EXPANSION_P (TREE_VEC_ELT (t, 0)) > + && TREE_CODE (elts[0]) == TREE_VEC) > + return elts[0]; > + > /* 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++) > + > + int out = 0; > + for (int i = 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)) > + && PACK_EXPANSION_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++; > } > } > + gcc_assert (out <= TREE_VEC_LENGTH (r)); And I think this could be strengthed to ==. > > - return t; > + return r; > } > > /* Substitute ARGS into one level PARMS of template parameters. */ > @@ -14965,32 +15052,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..27444ebb594 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/cpp0x/variadic183.C > @@ -0,0 +1,14 @@ > +// PR c++/105956 > +// { dg-do compile { target c++11 } } > + > +template<int...> struct list; > + > +template<int... Ns> 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>; > -- > 2.37.0.3.g30cc8d0f14 > >
On 7/7/22 11:16, Patrick Palka wrote: > On Thu, 7 Jul 2022, Jason Merrill wrote: > >> On 7/6/22 15:26, Patrick Palka wrote: >>> On Tue, 5 Jul 2022, Jason Merrill wrote: >>> >>>> 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) <case TYPE_DECL, case VAR_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? >>> >>> Ah, I think see what you mean. For that, I think it suffices to just >>> handle in tsubst_template_args the case where we're substituting into a >>> single-elt TREE_VEC such as {T...}. That'll allow us to reuse the inner >>> TREE_VEC containing the actual set of args at least. >> >> Sounds good. >> >>> And AFAICT that's >>> the best we can do, since we'll always be creating a new ARGUMENT_PACK >>> which doesn't appear in any other TREE_VEC we have at our disposal. >> >> Why always? Why can't tsubst_argument_pack recognize the {T...} case and >> return the corresponding ARGUMENT_PACK from args? >> >> template <class... Ts> struct A >> { >> A<Ts...>* a; >> }; >> >> A<int,char> a; >> >> With your patch, the substitution into A<Ts...> reuses the inner TREE_VEC, but >> why not reuse the ARGUMENT_PACK as well? And why not set maybe_reuse for the >> enclosing arg level? > > D'oh, you're totally right, I didn't notice this opportunity. Here's a > patch that makes tsubst_argument_pack reuse the ARGUMENT_PACK from > 'args' when possible, and in turn makes tsubst_template_args reuse the > enclosing arg level. Relative to the previous patch, this increases > the % of calls to tsubst_template_args that benefit from this > optimization a further 10% (30% -> 40%), and reduces memory usage for > e.g. zip.cpp from range-v3 a further 2.5% (1.5% -> 4%). > > -- >8 -- > > Subject: [PATCH] c++: generic targs and identity substitution [PR105956] > > 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. > > 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 reverts that 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, > and a similar heuristic for tsubst_argument_pack. It turns out that > about 40% of all calls to tsubst_template_args benefit from this, and it > reduces memory usage by about 4% for e.g. zip.cpp from range-v3 (relative > to r13-1045) which more than makes up for the reversion. > > PR c++/105956 > > gcc/cp/ChangeLog: > > * pt.cc (template_arg_to_parm): Define. > (tsubst_argument_pack): Try to reuse the corresponding > ARGUMENT_PACK from 'args' when substituting into an > ARGUMENT_PACK for a generic template argument. > (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. Assert that > 'out' never exceeds the length of the new TREE_VEC, and remove > dead ARGUMENT_PACK_P test. > (tsubst_decl) <case TYPE_DECL, case VAR_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 | 172 ++++++++++++++++------- > gcc/testsuite/g++.dg/cpp0x/variadic183.C | 14 ++ > 2 files changed, 138 insertions(+), 48 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..85f3462a0ac 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" > @@ -4916,6 +4917,33 @@ template_parm_to_arg (tree t) > return t; > } > > +/* If T looks like a generic template argument produced by template_parm_to_arg, > + return the corresponding template parameter, otherwise return NULL_TREE. */ > + > +static tree > +template_arg_to_parm (tree t) > +{ > + if (t == NULL_TREE) > + return NULL_TREE; > + > + if (ARGUMENT_PACK_P (t)) > + { > + tree args = ARGUMENT_PACK_ARGS (t); > + if (TREE_VEC_LENGTH (args) == 1 > + && PACK_EXPANSION_P (TREE_VEC_ELT (args, 0))) > + { > + t = PACK_EXPANSION_PATTERN (TREE_VEC_ELT (args, 0)); > + if (REFERENCE_REF_P (t)) > + t = TREE_OPERAND (t, 0); > + } > + } > + > + if (TEMPLATE_PARM_P (t)) > + return t; > + > + return NULL_TREE; > +} > + > /* Given a single level of template parameters (a TREE_VEC), return it > as a set of template arguments. */ > > @@ -13516,12 +13544,38 @@ tree > tsubst_argument_pack (tree orig_arg, tree args, tsubst_flags_t complain, > tree in_decl) > { > + /* This flag is used only during deduction, and we don't expect to > + see such ARGUMENT_PACKs during substitution. */ > + gcc_assert (!ARGUMENT_PACK_INCOMPLETE_P (orig_arg)); > + > /* Substitute into each of the arguments. */ > tree pack_args = tsubst_template_args (ARGUMENT_PACK_ARGS (orig_arg), > args, complain, in_decl); > - tree new_arg = error_mark_node; > - if (pack_args != error_mark_node) > + if (pack_args == error_mark_node) > + return error_mark_node; > + > + if (pack_args == ARGUMENT_PACK_ARGS (orig_arg)) > + return orig_arg; > + > + /* If we're substituting into an ARGUMENT_PACK for a generic template > + argument, we might be able to avoid allocating a new ARGUMENT_PACK > + by reusing the corresponding ARGUMENT_PACK from ARGS if the > + substituted result is identical to it. */ > + if (tree parm = template_arg_to_parm (orig_arg)) > { > + int level, index; > + template_parm_level_and_index (parm, &level, &index); > + if (TMPL_ARGS_DEPTH (args) >= level) > + if (tree arg = TMPL_ARG (args, level, index)) > + if (TREE_CODE (arg) == TREE_CODE (orig_arg) > + && ARGUMENT_PACK_ARGS (arg) == pack_args) > + { > + gcc_assert (!ARGUMENT_PACK_INCOMPLETE_P (arg)); > + return arg; > + } > + } > + > + tree new_arg; > if (TYPE_P (orig_arg)) > { > new_arg = cxx_make_type (TREE_CODE (orig_arg)); > @@ -13532,10 +13586,7 @@ tsubst_argument_pack (tree orig_arg, tree args, tsubst_flags_t complain, > new_arg = make_node (TREE_CODE (orig_arg)); > TREE_CONSTANT (new_arg) = TREE_CONSTANT (orig_arg); > } > - > ARGUMENT_PACK_ARGS (new_arg) = pack_args; > - } > - > return new_arg; > } > > @@ -13544,17 +13595,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 the substituted result is identical to T. */ > + bool const_subst_p = true; > + > + /* If MAYBE_REUSE is a TREE_VEC, 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; Looks like we can move this declaration further down now. > + for (int i = 0; i < len; i++) > { > tree orig_arg = TREE_VEC_ELT (t, i); > tree new_arg; > @@ -13587,49 +13643,80 @@ tsubst_template_args (tree t, tree args, tsubst_flags_t complain, tree in_decl) > > 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 T appears to be a set of generic template arguments, set > + MAYBE_REUSE to the corresponding level from ARGS. */ > + if (tree parm = template_arg_to_parm (TREE_VEC_ELT (t, 0))) > + { > + int level, index; > + template_parm_level_and_index (parm, &level, &index); > + if (index == 0 && TMPL_ARGS_DEPTH (args) >= level) > + maybe_reuse = TMPL_ARGS_LEVEL (args, level); > + } > + /* If ARGS and T are both multi-level, the substituted result may be > + identical to ARGS (if each level was pairwise identical). */ > + else if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (t) > + && TMPL_ARGS_HAVE_MULTIPLE_LEVELS (args)) Maybe compare TMPL_ARGS_DEPTH? OK with or without these tweaks. > + maybe_reuse = args; > + > + /* Return MAYBE_REUSE and avoid allocating a new TREE_VEC if the substituted > + result is identical to it. */ > + if (maybe_reuse != NULL_TREE > + && TREE_VEC_LENGTH (maybe_reuse) == len > + && std::equal (elts, elts+len, TREE_VEC_BEGIN (maybe_reuse))) > + return maybe_reuse; > + /* If T consists of only a pack expansion for which substitution yielded > + a TREE_VEC of the expanded elements, then reuse that TREE_VEC instead > + of effectively making a copy. */ > + if (len == 1 > + && PACK_EXPANSION_P (TREE_VEC_ELT (t, 0)) > + && TREE_CODE (elts[0]) == TREE_VEC) > + return elts[0]; > + > /* 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++) > + > + int out = 0; > + for (int i = 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)) > + && PACK_EXPANSION_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++; > } > } > + gcc_assert (out <= TREE_VEC_LENGTH (r)); > > - return t; > + return r; > } > > /* Substitute ARGS into one level PARMS of template parameters. */ > @@ -14965,32 +15052,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..27444ebb594 > --- /dev/null > +++ b/gcc/testsuite/g++.dg/cpp0x/variadic183.C > @@ -0,0 +1,14 @@ > +// PR c++/105956 > +// { dg-do compile { target c++11 } } > + > +template<int...> struct list; > + > +template<int... Ns> 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>;
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)) + { + 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<int... Ns> struct list; + +template<int... Ns> 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>;
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. 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) <case TYPE_DECL, case VAR_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