| Message ID | 1434072342-14126-1-git-send-email-patrick@parcs.ath.cx |
|---|---|
| State | New |
| Headers | show |
On 06/11/2015 09:25 PM, Patrick Palka wrote: > + parameter_vec = make_tree_vec > + (TREE_VEC_LENGTH (TREE_VALUE (current_template_parms)) + 1); > + > + for (int i = 0; i < TREE_VEC_LENGTH (parameter_vec) - 1; i++) > + TREE_VEC_ELT (parameter_vec, i) > + = TREE_VEC_ELT (TREE_VALUE (current_template_parms), i); > + > + TREE_VEC_ELT (parameter_vec, TREE_VEC_LENGTH (parameter_vec) - 1) > + = tree_last (parameter_list); Any reason not to use grow_tree_vec?
On Mon, Jun 15, 2015 at 2:05 PM, Jason Merrill <jason@redhat.com> wrote: > On 06/11/2015 09:25 PM, Patrick Palka wrote: >> >> + parameter_vec = make_tree_vec >> + (TREE_VEC_LENGTH (TREE_VALUE (current_template_parms)) + 1); >> + >> + for (int i = 0; i < TREE_VEC_LENGTH (parameter_vec) - 1; i++) >> + TREE_VEC_ELT (parameter_vec, i) >> + = TREE_VEC_ELT (TREE_VALUE (current_template_parms), i); >> + >> + TREE_VEC_ELT (parameter_vec, TREE_VEC_LENGTH (parameter_vec) - 1) >> + = tree_last (parameter_list); > > > Any reason not to use grow_tree_vec? Doing so causes a lot of ICEs in the testsuite. I think it's because grow_tree_vec invalidates the older parameter_vec which some trees may still be holding a reference to in their DECL_TEMPLATE_PARMS field. > >
On 06/15/2015 02:32 PM, Patrick Palka wrote: > On Mon, Jun 15, 2015 at 2:05 PM, Jason Merrill <jason@redhat.com> wrote: >> Any reason not to use grow_tree_vec? > > Doing so causes a lot of ICEs in the testsuite. I think it's because > grow_tree_vec invalidates the older parameter_vec which some trees may > still be holding a reference to in their DECL_TEMPLATE_PARMS field. Hmm, that's unfortunate, as doing it this way means we get a bunch of garbage TREE_VECs in the process. But I guess the patch is OK as is. Jason
On Tue, Jun 23, 2015 at 12:38 AM, Jason Merrill <jason@redhat.com> wrote: > On 06/15/2015 02:32 PM, Patrick Palka wrote: >> >> On Mon, Jun 15, 2015 at 2:05 PM, Jason Merrill <jason@redhat.com> wrote: >>> >>> Any reason not to use grow_tree_vec? >> >> >> Doing so causes a lot of ICEs in the testsuite. I think it's because >> grow_tree_vec invalidates the older parameter_vec which some trees may >> still be holding a reference to in their DECL_TEMPLATE_PARMS field. > > > Hmm, that's unfortunate, as doing it this way means we get a bunch of > garbage TREE_VECs in the process. But I guess the patch is OK as is. Yeah, though I can't think of a simple way to work around this -- any solution I think of seems to require a change in the representation of current_template_parms, something that would be quite invasive.... Will commit the patch shortly. > > Jason >
On 2015.06.23 at 19:40 -0400, Patrick Palka wrote: > On Tue, Jun 23, 2015 at 12:38 AM, Jason Merrill <jason@redhat.com> wrote: > > On 06/15/2015 02:32 PM, Patrick Palka wrote: > >> > >> On Mon, Jun 15, 2015 at 2:05 PM, Jason Merrill <jason@redhat.com> wrote: > >>> > >>> Any reason not to use grow_tree_vec? > >> > >> > >> Doing so causes a lot of ICEs in the testsuite. I think it's because > >> grow_tree_vec invalidates the older parameter_vec which some trees may > >> still be holding a reference to in their DECL_TEMPLATE_PARMS field. > > > > > > Hmm, that's unfortunate, as doing it this way means we get a bunch of > > garbage TREE_VECs in the process. But I guess the patch is OK as is. > > Yeah, though I can't think of a simple way to work around this -- any > solution I think of seems to require a change in the representation of > current_template_parms, something that would be quite invasive.... > Will commit the patch shortly. Your patch causes LLVM build to hang on the attached testcase. (I killed gcc after ~10 minutes compile time.) perf shows: 23.03% cc1plus cc1plus [.] comp_template_parms 19.41% cc1plus cc1plus [.] structural_comptypes 16.28% cc1plus cc1plus [.] cp_type_quals 15.89% cc1plus cc1plus [.] comp_template_parms_position 14.01% cc1plus cc1plus [.] comp_type_attributes 6.58% cc1plus cc1plus [.] comptypes ... To reproduce just run: g++ -c -O3 -std=c++11 gtest-all.ii
On Wed, Jun 24, 2015 at 5:08 AM, Markus Trippelsdorf <markus@trippelsdorf.de> wrote: > On 2015.06.23 at 19:40 -0400, Patrick Palka wrote: >> On Tue, Jun 23, 2015 at 12:38 AM, Jason Merrill <jason@redhat.com> wrote: >> > On 06/15/2015 02:32 PM, Patrick Palka wrote: >> >> >> >> On Mon, Jun 15, 2015 at 2:05 PM, Jason Merrill <jason@redhat.com> wrote: >> >>> >> >>> Any reason not to use grow_tree_vec? >> >> >> >> >> >> Doing so causes a lot of ICEs in the testsuite. I think it's because >> >> grow_tree_vec invalidates the older parameter_vec which some trees may >> >> still be holding a reference to in their DECL_TEMPLATE_PARMS field. >> > >> > >> > Hmm, that's unfortunate, as doing it this way means we get a bunch of >> > garbage TREE_VECs in the process. But I guess the patch is OK as is. >> >> Yeah, though I can't think of a simple way to work around this -- any >> solution I think of seems to require a change in the representation of >> current_template_parms, something that would be quite invasive.... >> Will commit the patch shortly. > > Your patch causes LLVM build to hang on the attached testcase. (I killed > gcc after ~10 minutes compile time.) > > perf shows: > 23.03% cc1plus cc1plus [.] comp_template_parms > 19.41% cc1plus cc1plus [.] structural_comptypes > 16.28% cc1plus cc1plus [.] cp_type_quals > 15.89% cc1plus cc1plus [.] comp_template_parms_position > 14.01% cc1plus cc1plus [.] comp_type_attributes > 6.58% cc1plus cc1plus [.] comptypes > ... > > To reproduce just run: > g++ -c -O3 -std=c++11 gtest-all.ii Thanks. I don't think infinite recursion is going on. Rather, it seems that this patch causes a quadratic slowdown (in the number of template template parameters in a parameter list and in the number of partial specializations of a template) in the structural_comptypes -> comp_template_parms -> comptypes loop when comparing two TEMPLATE_TEMPLATE_PARMs to find the canonical template template parameter of a partial specialization. The test case has a good amount of mechanical partial specializations of templates with big parameter lists containing lots of template template parameters so it's very sensitive to this quadratic slowdown. To compare two template template parameters for structural equality, structural_comptypes must compare their DECL_TEMPLATE_PARMS for structural equality. Since the patch gives the DECL_TEMPLATE_PARMS field a level containing all previously declared template parameters in the parameter list it's defined in, this comparison becomes recursive and quadratic if all the parameters of the template are template template parameters which is what the test has starting at line 48518. In the meantime I will revert this patch since I won't be able to find a solution in time. What should be done about the PR? I suppose I should reopen it... > > -- > Markus
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c index 5fdb2a7..d0a3c09 100644 --- a/gcc/cp/parser.c +++ b/gcc/cp/parser.c @@ -13259,6 +13259,11 @@ cp_parser_template_parameter_list (cp_parser* parser) begin_template_parm_list (); + current_template_parms + = tree_cons (size_int (processing_template_decl), + make_tree_vec (0), + current_template_parms); + /* The loop below parses the template parms. We first need to know the total number of template parms to be able to compute proper canonical types of each dependent type. So after the loop, when @@ -13271,6 +13276,7 @@ cp_parser_template_parameter_list (cp_parser* parser) bool is_non_type; bool is_parameter_pack; location_t parm_loc; + tree parameter_vec; /* Parse the template-parameter. */ parm_loc = cp_lexer_peek_token (parser->lexer)->location; @@ -13295,8 +13301,27 @@ cp_parser_template_parameter_list (cp_parser* parser) break; /* Otherwise, consume the `,' token. */ cp_lexer_consume_token (parser->lexer); + + /* Add the parameter we just processed to current_template_parms. */ + + parameter_vec = make_tree_vec + (TREE_VEC_LENGTH (TREE_VALUE (current_template_parms)) + 1); + + for (int i = 0; i < TREE_VEC_LENGTH (parameter_vec) - 1; i++) + TREE_VEC_ELT (parameter_vec, i) + = TREE_VEC_ELT (TREE_VALUE (current_template_parms), i); + + TREE_VEC_ELT (parameter_vec, TREE_VEC_LENGTH (parameter_vec) - 1) + = tree_last (parameter_list); + + current_template_parms + = tree_cons (TREE_PURPOSE (current_template_parms), + parameter_vec, + TREE_CHAIN (current_template_parms)); } + current_template_parms = TREE_CHAIN (current_template_parms); + return end_template_parm_list (parameter_list); } diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index 7f04fe6..d1eb833 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -3990,21 +3990,6 @@ template_parms_to_args (tree parms) args = a; } - if (length > 1 && TREE_VEC_ELT (args, 0) == NULL_TREE) - /* This can happen for template parms of a template template - parameter, e.g: - - template<template<class T, class U> class TT> struct S; - - Consider the level of the parms of TT; T and U both have - level 2; TT has no template parm of level 1. So in this case - the first element of full_template_args is NULL_TREE. If we - leave it like this TMPL_ARGS_DEPTH on args returns 1 instead - of 2. This will make tsubst wrongly consider that T and U - have level 1. Instead, let's create a dummy vector as the - first element of full_template_args so that TMPL_ARGS_DEPTH - returns the correct depth for args. */ - TREE_VEC_ELT (args, 0) = make_tree_vec (1); return args; } @@ -4647,6 +4632,9 @@ check_default_tmpl_args (tree decl, tree parms, bool is_primary, else msg = G_("default argument for template parameter for class enclosing %qD"); + /* By default check everything. */ + last_level_to_check = 1; + if (current_class_type && TYPE_BEING_DEFINED (current_class_type)) /* If we're inside a class definition, there's no need to examine the parameters to the class itself. On the one @@ -4656,10 +4644,12 @@ check_default_tmpl_args (tree decl, tree parms, bool is_primary, struct S { template <class U> void f(U); }; Here the default argument for `S' has no bearing on the declaration of `f'. */ - last_level_to_check = template_class_depth (current_class_type) + 1; - else - /* Check everything. */ - last_level_to_check = 0; + last_level_to_check += template_class_depth (current_class_type); + + if (processing_template_parmlist) + /* Likewise for parameters outside of the nested parameter list we have + just finished defining. */ + last_level_to_check += processing_template_parmlist; for (parm_level = parms; parm_level && TMPL_PARMS_DEPTH (parm_level) >= last_level_to_check; @@ -22348,11 +22338,6 @@ splice_late_return_type (tree type, tree late_return_type) return type; argvec = make_tree_vec (1); TREE_VEC_ELT (argvec, 0) = late_return_type; - if (processing_template_parmlist) - /* For a late-specified return type in a template type-parameter, we - need to add a dummy argument level for its parmlist. */ - argvec = add_to_template_args - (make_tree_vec (processing_template_parmlist), argvec); if (current_template_parms) argvec = add_to_template_args (current_template_args (), argvec); return tsubst (type, argvec, tf_warning_or_error, NULL_TREE); diff --git a/gcc/testsuite/g++.dg/cpp0x/auto45.C b/gcc/testsuite/g++.dg/cpp0x/auto45.C new file mode 100644 index 0000000..5f539a2 --- /dev/null +++ b/gcc/testsuite/g++.dg/cpp0x/auto45.C @@ -0,0 +1,5 @@ +// Addendum to auto23.C, now with nested template parameter lists +// { dg-do compile { target c++11 } } + +template<template <auto f()->int> class> struct A { }; +template<template <template <auto f()->int> class> class> struct A { }; diff --git a/gcc/testsuite/g++.dg/cpp0x/variadic18.C b/gcc/testsuite/g++.dg/cpp0x/variadic18.C index fc0e2dd..57fdc86 100644 --- a/gcc/testsuite/g++.dg/cpp0x/variadic18.C +++ b/gcc/testsuite/g++.dg/cpp0x/variadic18.C @@ -1,7 +1,7 @@ // { dg-do compile { target c++11 } } template<typename...> class tuple { }; -template<typename T, template<typename T> class... Metafunctions> +template<typename T, template<typename U> class... Metafunctions> struct apply_all { typedef tuple<typename Metafunctions<T>::type...> type; diff --git a/gcc/testsuite/g++.dg/cpp0x/variadic19.C b/gcc/testsuite/g++.dg/cpp0x/variadic19.C index 0ae2672..3be9bb0 100644 --- a/gcc/testsuite/g++.dg/cpp0x/variadic19.C +++ b/gcc/testsuite/g++.dg/cpp0x/variadic19.C @@ -4,7 +4,7 @@ struct tuple { static const int value = 0; }; -template<typename T, template<class T> class... Metafunctions> +template<typename T, template<class U> class... Metafunctions> struct tuple<Metafunctions<T>...> { static const int value = 1; }; diff --git a/gcc/testsuite/g++.dg/template/canon-type-13.C b/gcc/testsuite/g++.dg/template/canon-type-13.C index 4f3702b..5a8d37d 100644 --- a/gcc/testsuite/g++.dg/template/canon-type-13.C +++ b/gcc/testsuite/g++.dg/template/canon-type-13.C @@ -11,7 +11,7 @@ struct S1 { }; -template<class T, template<class T> class A, template<class T> class B = A> +template<class T, template<class U> class A, template<class U> class B = A> struct C { B<T> m; diff --git a/gcc/testsuite/g++.dg/template/crash83.C b/gcc/testsuite/g++.dg/template/crash83.C index b83dd21..7dcbed9 100644 --- a/gcc/testsuite/g++.dg/template/crash83.C +++ b/gcc/testsuite/g++.dg/template/crash83.C @@ -2,4 +2,4 @@ template<int> struct A {}; -template<typename = class A<0>: > struct B {}; // { dg-error "explicit specialization|expected" } +template<typename = class A<0>: > struct B {}; // { dg-error "" } diff --git a/gcc/testsuite/g++.dg/template/pr30044.C b/gcc/testsuite/g++.dg/template/pr30044.C new file mode 100644 index 0000000..c1d0d29 --- /dev/null +++ b/gcc/testsuite/g++.dg/template/pr30044.C @@ -0,0 +1,14 @@ +template <typename T1, typename T2, template <T2> class Comp, class Result = Comp<1> > +struct sort { }; + + +template <typename Type, template <Type, Type> class Comp, class Result = Comp<1, 2> > +struct sort2 { }; + +template <typename Type, template <int, Type> class Comp, class Result = Comp<1, 2> > +struct sort3 { }; + +template <template <typename T1, typename T2, template <T2> class Comp, class Result = Comp<1> > class Foo> +struct sort4 { }; + + diff --git a/gcc/testsuite/g++.old-deja/g++.pt/ttp42.C b/gcc/testsuite/g++.old-deja/g++.pt/ttp42.C index 53bdae1..a2ac239 100644 --- a/gcc/testsuite/g++.old-deja/g++.pt/ttp42.C +++ b/gcc/testsuite/g++.old-deja/g++.pt/ttp42.C @@ -1,5 +1,5 @@ // { dg-do run } -template <class T, template <class T> class C> +template <class T, template <class U> class C> struct X {};
The crux of the issue causing PR 30044 is that, in the middle of processing a template parameter list, current_template_parms is not up-to-date. This causes problems particularly when we attempt to instantiate a type that's defined within the very parameter list we are processing. Of course, more details to follow... When processing the default template argument C<1> in (this is not the reproducer in the PR but it better exhibits the same problem) template <class A, class B, template <B> class C, class D = C<1> > struct Z { }; we try to "instantiate" B with itself before the parameter list that B resides has been finished. At that point B is not even in current_template_parms because we only update current_template_parms when the entire parameter list is finished. So when tsubst gets called on B with an incomplete template argument list (because current_template_parms hasn't been updated), tsubst ICEs with an out-of-bounds error when trying to look up the template argument to substitute for B, which has level=1 and index=1. [ Note that we don't ICE for the similar test case template <class B, template <B> class C, class D = C<1> > struct Z { }; because of a hack in template_parms_to_args() to add a dummy argument corresponding to level=1 and index=0 in the template argument list of a template template. Here tsubst() has to look up the argument corresponding to B, which now has level=1 and index=0. The lookup succeeds (returning NULL_TREE) and tsubst proceeds. ] To fix this PR, this patch attempts to more frequently update current_template_parms. Instead of updating current_template_parms only after the whole parameter list has been processed, this patch makes current_template_parms get updated as soon as each template parameter is processed. Aside from directly fixing the PR, this approach allows us to remove two now-obsolete hacks (there may be more) which attempted to work around this delay in updating. One hack is in the aforementioned template_parms_to_args() and another is in splite_lat_return_type(). As a plus, we now detect shadowing of template variables across nested template parameter lists, e.g. template <typename T, template <typename T> class> struct A { }; and now we no longer bogusly error out on late-specified return types inside nested template parameter lists: template <template <auto f()->int> class> struct A { }; [ We can't use vec_grow() (which uses ggc_realloc()) to update current_template_parms because of sharing issues that I haven't investigated deeply. ] [ In check_default_tmpl_args we now have to account for nested template parameter lists the same way we account for template class depth, so that we don't inspect default template args not belonging to the nested parameter list we just finished. last_level_to_check now defaults to 1 instead of 0 since template "level"s are 1-based anyway. ] Does this approach make sense? OK to install after bootstrap + regtesting succeeds? gcc/cp/ChangeLog: * parser.c (cp_parser_template_parameter_list): Update current_template_parms right after processing a paramater. * pt.c (template_parms_to_args): Remove obsolete hack for giving template template arguments the proper level. (check_default_tmpl_args): Account for tested template parameter_lists. (splite_late_return_type): Remove obsolete hack for giving template template arguments the proper level. gcc/testsuite/ChangeLog * g++.dg/cpp0x/auto45.C: New test. * g++.dg/template/pr30044.C: New test. * g++.dg/template/crash83.C: Accept any error string. * g++.dg/cpp0x/variadic18.C: Adjust to not shadow template parameters. * g++.dg/cpp0x/variadic18.C: Likewise * g++.dg/template/canon-type-13.C: Likewise. * g++.old-deja/g++.pt/ttp42.C: Likewise. --- gcc/cp/parser.c | 25 ++++++++++++++++++++ gcc/cp/pt.c | 33 ++++++++------------------- gcc/testsuite/g++.dg/cpp0x/auto45.C | 5 ++++ gcc/testsuite/g++.dg/cpp0x/variadic18.C | 2 +- gcc/testsuite/g++.dg/cpp0x/variadic19.C | 2 +- gcc/testsuite/g++.dg/template/canon-type-13.C | 2 +- gcc/testsuite/g++.dg/template/crash83.C | 2 +- gcc/testsuite/g++.dg/template/pr30044.C | 14 ++++++++++++ gcc/testsuite/g++.old-deja/g++.pt/ttp42.C | 2 +- 9 files changed, 58 insertions(+), 29 deletions(-) create mode 100644 gcc/testsuite/g++.dg/cpp0x/auto45.C create mode 100644 gcc/testsuite/g++.dg/template/pr30044.C