Staged Compiler Architecture
for Dynamic Program Optimization
Mark Leone and R. Kent Dybvig
Technical Report #490
Computer Science Department
Optimizing code at run time is appealing because run-time
optimizations can make use of values and invariants that cannot be
exploited statically. Dynamic optimization can yield code that is
superior to statically optimal code.
Recent research has shown that dynamic
compilation can dramatically improve the performance of
a wide range of applications including network packet demultiplexing,
sparse matrix computations, pattern matching, and many forms of mobile
code (such as ``applets'').
Several obstacles have prevented the widespread use of dynamic
compilation as a general-purpose optimization technique for stand-alone
Our goal is to design and implement a compiler architecture, called
Dynamo, that provides effective dynamic optimization with little
programmer effort and low run-time overhead.
- Overhead: Many traditional compilation techniques are too time consuming
to perform at run time. Dynamic optimization is profitable only
when the time spent optimizing and compiling code is repaid by
- Ease of use: Until recently, effective dynamic optimizations
could only be obtained manually, by writing code that explicitly
generates code at run time. Some progress has been made in building
tools and designing languages that better support automatic dynamic
optimization, but state-of-the-art systems are still difficult to use.
- Effectiveness: Existing dynamic
optimization systems provide a narrow range of optimizations and offer
little control over the optimization process. Such systems provide
either ``lightweight'' or ``heavyweight'' dynamic optimization: they
feature a single dynamic compilation model that offers either fast
compilation or high-quality code, but not both.
An important characteristic of Dynamo will be its staged
compilation model. To reduce the overhead of dynamic compilation, it
is necessary to perform some analysis, translation, and optimization
at compile time. To achieve ``lightweight'' dynamic optimization,
most compilation steps are performed statically, resulting in a
low-level intermediate representation that admits a few simple dynamic
optimizations. ``Heavyweight'' dynamic optimization employs a
high-level intermediate representation and a wide range of
optimizations. A staged compiler architecture supports a broad
spectrum of optimization models (including ``middleweight''
optimizations) by permitting static compilation to be suspended after
reaching a high-level, mid-level, or low-level intermediate
Selective dynamic optimization is also critical to obtaining
good performance, since the time spent performing unnecessary
optimizations contributes to a program's overall execution time.
Dynamo will incorporate a suite of automatic program analyses and
profiling tools to uncover opportunities for dynamic optimization in
ordinary code, and a rich set of optimization directives will give the
programmer fine-grained control over dynamic optimization when