Re: Sigh. Inlining heuristics.

[Alexandre Oliva <aoliva at redhat dot com>]

On Jul 10, 2001, Linus Torvalds <torvalds@transmeta.com> wrote:

> For example, constant arguments may make 99% of the inlined function go
> away statically - but if you make your instruction estimate based on the
> pre-optimized tree (which I assume you'd do - anything else would be
> rather expensive), you'd never see this.

Yep.  This is quite important for C++'s STL.  Back in 1996, I was
working on optimization algorithms in graphs, in a parallel
programming course, and I carefully studied the generated code, and
found GCC was inlining everything that mattered (namely, dozens of
accessor functions, iterator increments, etc, etc, and a lot of the
code ended up being optimized away), and leaving out-of-line
everything that shouldn't be inlined (namely, memory allocators that
had synchronization primitives in them).  At that time, I concluded it
was doing a great job.  But it's not like the algorithms were complex
beasts.  Perhaps with more complex algorithms, it would have been
important to cut off inlining earlier.  But then comes the problem of
deciding where to cut it off.

It appears to me that inlining a function, and only then deciding
whether to inline the functions it calls, is exactly the wrong
approach, because then we're likely to end up leaving calls inside
inner loops out-of-line.  If we do it the other way round, by first
inlining the innermost calls, and only then deciding whether the
inline the resulting function into another one, if possible after
applying other optimizations to the already-inlined functions to get a
better idea of the actual size of the function to be inlined, we could
do a better job.  Taking into account the likelihood of a function
call being actually executed can certainly be used to improve the
heuristics that decide whether or not to inline a function.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                  aoliva@{cygnus.com, redhat.com}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist    *Please* write to mailing lists, not to me