RFC: cache uses_template_parms in tree node?

RFC: cache uses_template_parms in tree node?

[Richard Guenther]

Hi!

To address the for_each_template_parm() performance problem, would it be
possible to cache the outcome of uses_template_parms() in the tree
node? Or would this caching somehow be invalidated later?

Just before I start digging into gcc tree's and its wonders :/

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: cache uses_template_parms in tree node?

[Giovanni Bajo]

Richard Guenther wrote:

> To address the for_each_template_parm() performance problem, would it
> be possible to cache the outcome of uses_template_parms() in the tree
> node? Or would this caching somehow be invalidated later?
> Just before I start digging into gcc tree's and its wonders :/

To me, the right solution is to get rid of uses_template_parms() altogether. We
can check for type/value dependness instead (we already have functions for
that, and we even cache the outcome in the tree as you are suggesting), so it's
just a matter of removing the old code.

I asked Honza to provide me with some numbers about which calls to
uses_template_parms are the ones most important from a compile-time point of
view. I'm willing to look into this when I get the numbers.

Giovanni Bajo

Re: cache uses_template_parms in tree node?

[Richard Guenther]

On Thu, 22 Jan 2004, Giovanni Bajo wrote:

> Richard Guenther wrote:
>
> > To address the for_each_template_parm() performance problem, would it
> > be possible to cache the outcome of uses_template_parms() in the tree
> > node? Or would this caching somehow be invalidated later?
> > Just before I start digging into gcc tree's and its wonders :/
>
> To me, the right solution is to get rid of uses_template_parms() altogether. We
> can check for type/value dependness instead (we already have functions for
> that, and we even cache the outcome in the tree as you are suggesting), so it's
> just a matter of removing the old code.
>
> I asked Honza to provide me with some numbers about which calls to
> uses_template_parms are the ones most important from a compile-time point of
> view. I'm willing to look into this when I get the numbers.

For a POOMA testcase, a compile with a instrumented compiler yields the
following gprof callgraph for uses_template_parms:

-----------------------------------------------
                                  29             add_friend <cycle 1> [2505]
                                  38             duplicate_decls <cycle 1> [901]
                                  60             get_bindings_real <cycle 1> [2187]
                                 183             make_friend_class <cycle 1> [2376]
                                 201             tsubst_default_arguments <cycle 1> [3660]
                                 212             check_default_argument <cycle 1> [3591]
                                 528             xref_basetypes <cycle 1> [2131]
                                1001             try_one_overload <cycle 1> [2397]
                                1248             grokdeclarator <cycle 1> [484]
                                4720             instantiate_class_template <cycle 1> [628]
                               13723             expand_or_defer_fn <cycle 1> [2108]
                               20135             maybe_retrofit_in_chrg <cycle 1> [1736]
                               22341             unify <cycle 1> [483]
                               50560             register_specialization <cycle 1> [619]
                               51673             tsubst <cycle 1> [281]
                              150936             template_class_depth_real <cycle 1> [1039]
                              152948             tsubst_template_arg <cycle 1> [811]
                              214778             type_unification_real <cycle 1> [911]
                              270505             coerce_template_parms <cycle 1> [398]
                              459713             lookup_template_class <cycle 1> [242]
                0.00    0.00      14/101229133     bt_instantiate_type_proc <cycle 2> [2629]
                0.00    0.00      40/101229133     cp_parser_check_declarator_template_parameters [1881]
[1229]   0.0    0.03    0.00 1415586         uses_template_parms <cycle 1> [1229]
                             1415586             for_each_template_parm <cycle 1> [333]

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/

Re: cache uses_template_parms in tree node?

[Giovanni Bajo]

Richard Guenther wrote:

> For a POOMA testcase, a compile with a instrumented compiler yields
> the following gprof callgraph for uses_template_parms:

Thanks! I'm looking into this.

Giovanni Bajo

Re: RFC: cache uses_template_parms in tree node?

[Gabriel Dos Reis]

Richard Guenther <rguenth@tat.physik.uni-tuebingen.de> writes:

| Hi!
| 
| To address the for_each_template_parm() performance problem, would it be
| possible to cache the outcome of uses_template_parms() in the tree
| node? Or would this caching somehow be invalidated later?

It has been agreed (some time ago) that uses_template_parms() should
go away instead of being tweaked.   

-- Gaby

Re: RFC: cache uses_template_parms in tree node?

[Mark Mitchell]

Richard Guenther wrote:

> Hi!
> 
> To address the for_each_template_parm() performance problem, would it be
> possible to cache the outcome of uses_template_parms() in the tree
> node? Or would this caching somehow be invalidated later?

The right approach, as I've said before, is simply not to *use* 
for_each_template_parm.

It should be unncessary; the right approach should be to use 
type_dependent_p and its friends.

That's not a trivial change, but it's the right change.

There might be a very few places where for_each_template_parm would 
still be necessary -- but they will not be anything that should up on 
the profile.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

Re: RFC: cache uses_template_parms in tree node?

[Jan Hubicka]

> Richard Guenther wrote:
> 
> >Hi!
> >
> >To address the for_each_template_parm() performance problem, would it be
> >possible to cache the outcome of uses_template_parms() in the tree
> >node? Or would this caching somehow be invalidated later?
> 
> The right approach, as I've said before, is simply not to *use* 
> for_each_template_parm.
> 
> It should be unncessary; the right approach should be to use 
> type_dependent_p and its friends.
> 
> That's not a trivial change, but it's the right change.

Mark,
do you think such a change is possible for 3.4 GCC?  If not what would
you recommend to do for the release branch?  The for_each_template_parm
seems to be really one of the major CPU cycle consumers when it come to
C++ compilation and it would be shame to leave it that way for the
release.

Honza
> 
> There might be a very few places where for_each_template_parm would 
> still be necessary -- but they will not be anything that should up on 
> the profile.
> 
> -- 
> Mark Mitchell
> CodeSourcery, LLC
> mark@codesourcery.com

Re: RFC: cache uses_template_parms in tree node?

[Mark Mitchell]

Jan Hubicka wrote:

>>Richard Guenther wrote:
>>
>>
>>>Hi!
>>>
>>>To address the for_each_template_parm() performance problem, would it be
>>>possible to cache the outcome of uses_template_parms() in the tree
>>>node? Or would this caching somehow be invalidated later?
>>
>>The right approach, as I've said before, is simply not to *use* 
>>for_each_template_parm.
>>
>>It should be unncessary; the right approach should be to use 
>>type_dependent_p and its friends.
>>
>>That's not a trivial change, but it's the right change.
> 
> 
> Mark,
> do you think such a change is possible for 3.4 GCC?  If not what would
> you recommend to do for the release branch?  The for_each_template_parm
> seems to be really one of the major CPU cycle consumers when it come to
> C++ compilation and it would be shame to leave it that way for the
> release.

I'm looking into it as we speak.

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com

Re: RFC: cache uses_template_parms in tree node?

[Mark Mitchell]

I'm still testing various changes here.

Would one of you mind sending me preprocessed source where 
uses_template_parms shows up high on the profile, so that I can measure 
the improvements I'm getting?

Thanks,

-- 
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com