Inlining heuristics in Gambit

[Brad Lucier <lucier at math dot purdue dot edu>]

Marc Feeley's Gambit is a Scheme->C compiler for which inlining
(here in the form of beta-reduction) is an important, perhaps
crucial, optimization.  This is because there are no "loops" per
se in Scheme, loops are just tail-recursive functions, so any type
of loop unrolling is implemented through the function inliner.  On the
other hand, in Scheme the callee manages the stack frame for
all function calls, so a tail function call in Scheme has the
semantics of a goto with arguments, so this is an efficient
way to write a loop.

All recent versions of Gambit use the heuristic suggested by
Linus---inline a function to the function call site if the
expanded body of the inlined function is no more than X times
as large as the function call (the size of the S-expression
expresing the function call).  X is a tunable parameter,
defaulting to 3.  (The universal small constant.;-)

There is also the question of whether to do-top down or
bottom-up inlining.  The current released version of Gambit (3.0)
does top-down inlining, but I believe the next version will
do bottom-up inlining as it has slightly better-understood
semantics.  In Gambit, if you have the call chain:

f1 -> f2 -> f3 -> f4 -> f5 -> f6 -> f7 -> f8

then one begins by seing if f8 can be inlined in f7; if
so, then f7 is actually replaced by a new f7 that has
the body of f8 inlined in it.  Then one sees if the new
f7 can be inlined in f6.  Assuming it can be, then a
new f6 is generated.

If the new, larger, f6 cannot be inlined in f5, the whole
process starts again.  So one is actually coalescing
certain paths in the call chain.  What one ends up with
is, say.

f1 -> F2 -> F6

where F2 is the completely expanded version of f2->f3->f4->f5
and F6 is the completely expanded version of f6->f7->f8.  There
are also lying around for later use

f8
F7 == f7->f8 (expanded)
f5
F4 == f4->f5 (expanded)
F3 == f3->f4->f5 (expanded)

The old f2, f3, f4, f6, and f7 no longer exist internally
during the compilation process, they are always called as
F2, F3, etc.  In other words, one is grouping the call
chain into contiguous chunks that eliminates some call overhead.

Of course, this does not help in deciding the following
important problem: if one has a function f1 that calls 
f2, f3, and f4, which function does one inline first?  And does
one do a depth-first function inline expansion (i.e., inline f2 to
get a new function F1 that calls f3 and f4 and now any function
that f2 called, and now make a new inlining decision) or does
one do a breadth-first expansion (after inlining f2, inline both
f3 and f4 (if possible) before inlining any function that f2 might
call)?

Brad Lucier