Re: C compile time

[Zack Weinberg <zack at codesourcery dot com>]

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.

1) Construct a complete call graph for the translation unit.
2) Mark all calls to functions not visible in the call graph
   not-to-be-inlined.
3) Topologically sort the call graph.  When cycles are detected,
   pick an edge in the cycle and mark that call site not-to-be-inlined.
   (Need a good heuristic for that.)  The sort goes bottom-up: if A
   calls B, B sorts before A.

4) For each function in the order produced by the topological sort:
   a) For each call site in the function which is not already marked
      not-to-be-inlined, decide heuristically whether to inline at
      that call site, and either perform the inlining or mark the call
      not-to-be-inlined.
   b) If possible, perform basic optimizations on the function -
      constant propagation and unreachable code elimination would
      probably be the biggest wins.

5) Discard function bodies which are now unreferenced and not
   externally visible.

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.

zw