Re: C compile time

[Jan Hubicka <jh at suse dot cz>]

> On Wed, 2003-06-18 at 13:05, Zack Weinberg wrote:
> > Mark Mitchell <mark@codesourcery.com> writes:
> > 
> > > For 3.4, we could consider going back to the "bottom-up" inlining
> > > strategy.  That might be better than what we have now, even though it's
> > > inherently quadratic.  Implementing bottom-up inlining wouldn't be
> > > terribly hard; all the same tree-inlining machinery would work.
> > 
> > With information about the complete translation unit in hand, I don't
> > think bottom-up has to be quadratic.  Consider the following
> > algorithm.
> 
> I think we need to say quadratic in what.  You're right that it's a
> linear number of inlining operations, but that's quadratic in terms of
> the number of nodes in the trees.

As I described in the other mail, we can do the inlining decisions first
and the do the top-down inlining based on these.  It is possible to get
upper estimate of function body after the inlining, on the other hand we
can probably do significantly better if we were doing inlining
step-by-step and optimizing the intermediate results so we have better
idea about how far the inlined version simplify.

> 
> For example:
> 
>   void f1() { return v1; }
>   void f2() { return v2 + f1(); }
>   void f3() { return v3 + f2(); }
>   ...
> 
> When you inline into f27 you'll have 27 copies of f1 lying around, 26
> copies of f2, 25 copies of f3, and so forth.
> 
> You can do better, but you have to be smarter.  If you're lucky, and
> some of these functions needn't actually be emitted in the .o file, you
> can do better.  For example, if f3 is needed, but f1 and f2 aren't, then
> you can inline f2 and f1 directly into f3, and not bother inlining f1
> into f2.

In unit-at-a-time I already do have analysis to recognize these cases.
How hard would be to make current tree-inline.c to not do the copy and
modify trees in place instead?

Honza
> 
> In C++, this is a typical case -- f27 may well be the only function
> which needs to be emitted, while all the other ones are inline template
> functions that need not be emitted and -- often -- are used nowhere else
> in the translation unit.
> 
> -- 
> Mark Mitchell
> CodeSourcery, LLC
> mark@codesourcery.com