Re: C compile time

[Chris Lattner <sabre at nondot dot org>]

Zach said:
> With information about the complete translation unit in hand, I don't
> think bottom-up has to be quadratic.  Consider the following
> algorithm.
> 1) Construct a complete call graph for the translation unit.
 ...

> The key property of this algorithm is that each function is processed
> for inlining exactly once, and we never have to inline more than one
> level, because all call sites in an inlinee have already been either
> inlined or marked do-not-inline.  Thus, no quadratic term.  IIRC
> topological sort is O(n log n), which we can live with.

This is similar to what we do in LLVM, except that we don't build an
explicit call graph.  If you're interested, here's the code for the
heuristic:
http://llvm.cs.uiuc.edu/doxygen/FunctionInlining_8cpp-source.html

Basically we do a bottom-up inlining based on what amounts to the call
graph (we just don't explicitly create one).  Our heuristic currently is
set to only inline when it will shrink the program, thus the cut-off is
set to be very conservative.  Besides that though, you may be interested
in why we try harder to inline some functions than others.

The only major problem that I have with the LLVM implementation right now
is that it doesn't cache information about the size of the function it is
considering inlining (it recalculates it every time it considers the
function).  Aside from this though (and the fact that it happens to use an
std::map instead of a hash_map), the algorithm is linear in the number of
function inlines it performs.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/