C compile time

[Mark Mitchell]

On Wed, 2003-06-18 at 14:07, Zack Weinberg wrote:
> Mark Mitchell <mark@codesourcery.com> writes:
> 
> >   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.
> 
> I think that can be done as a trivial adjustment to the algorithm I
> proposed -- you attach a "number of call sites" reference count to
> each FUNCTION_DECL, and decrement it every time it gets inlined; when
> it gets to zero, throw away the function body.  This effectively does
> the last step of my original algorithm at the same time as the main
> loop.  Obviously, externally visible decls have to be pinned.

If I understand correctly, that improvement decreases the total memory
usage (by throwing things away sooner), but still leaves you quadratic
in the number of node-copies you have to do.

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