On Wed, Jun 24, 2015 at 5:08 AM, Markus Trippelsdorf <mar...@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 <ja...@redhat.com> wrote: >> > On 06/15/2015 02:32 PM, Patrick Palka wrote: >> >> >> >> On Mon, Jun 15, 2015 at 2:05 PM, Jason Merrill <ja...@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
