Dynamo: A Staged Compiler Architecture
for Dynamic Program Optimization

Mark Leone and R. Kent Dybvig
Technical Report #490
Computer Science Department
Indiana University
September 1997


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 programs:

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.

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 representation.

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 necessary.