[Prev][Next][Index][Thread]
PL seminar - Oscar Waddell and Kent Dybvig
Programming Languages Seminar
Friday, Nov.1, 1996
10am-11am, LH 101
Fast and Effective Procedure Inlining
Oscar Waddell and Kent Dybvig
Procedural abstraction is an important tool for writing modular,
maintainable code. Procedure inlining is an important tool for
optimizing such code. When the compiler can determine that only one
procedure is ever reached from a particular call site, that call can be
replaced with an inline expansion of the procedure body. This
eliminates the procedure linkage overhead and may reveal new
opportunities for optimization. Naively expanding all calls inline,
however, can lead to unbounded compile time and/or code growth. The
merit of a particular inlining strategy is therefore determined by its
ability to recognize inlining opportunities and its discretion in
exercising those opportunities.
In this talk we will present an inlining algorithm that effectively
optimizes input programs with minimal compile-time overhead. The
algorithm incorporates simple control and data flow analysis to
identify inlining opportunities even in the presence of procedure
arguments and return values. It is \emph{polyvariant}, in that
inlining decisions are based not only on the text of potential inlined
procedures, but also on the procedure operands at each call site. It
is an \emph{online} algorithm: integration decisions are made
on-the-fly while constant folding, copy propagation, useless code
elimination, and procedure integration are performed. The algorithm is
linear in the size of the input program. We will discuss our
experience with an implementation of this algorithm that is now part of
the next generation Chez Scheme compiler.