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 {};