Re: [PATCH] Fix PR c++/30044

[Patrick Palka <patrick@parcs.ath.cx>]

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