C compile time

[Mark Mitchell]

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.

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 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