Last updated December 3, 1997.Brian Grant (grant@cs.washington.edu)
Staged compilation is a compilation strategy in which the code-compilation process is completed in multiple stages: for example, at traditional (static) compile time, at link time, at load time, and (on demand) at run time. By delaying a portion of the compilation process, it becomes possible to take advantage of information available only at the later stages, with the goal of improving performance of the resulting code. (This is in contrast to incremental compilation, the primary goal of which is to reduce compilation time.)
The portion of compilation postponed until run time is called dynamic compilation. The principle challenge and trade-off in dynamic compilation is achieving high-quality dynamically generated code at low run-time cost, since the time to perform run-time compilation and optimization must be recovered before any benefit from dynamic compilation can be obtained. Consequently, a key design issue in developing an effective dynamic-compilation system is the method for determining where, when, and on what run-time state to apply dynamic compilation. Ideally, the compiler would make these decisions automatically, as in other compiler optimizations; however, this ideal is beyond current state-of-the-art for general-purpose systems.
Instead, current dynamic compilation systems rely on some form of programmer direction to indicate where dynamic compilation would most profitably be applied. Some systems take an imperative, or operational, approach to user direction, requiring the user to write programs that explicitly manipulate, compose, and compile program fragments at run time. This kind of system offers great flexibility and control to the programmer, at the cost of significant programmer effort and debugging difficulty.
Alternatively, several dynamic compilation systems take a declarative, or transformational, approach, with user annotations guiding the dynamic-compilation process. Each of these declarative approaches adapts ideas from partial evaluation, expressing dynamic compilation as run-time specialization, where known, or static, values correspond to run-time state on which programs are specialized. Declarative approaches offer the advantages of an easier interface to dynamic compilation for the programmer and easier program understanding and debugging. (For a good discussion of the advantages of declarative approaches to dynamic compilation relative to imperative approaches, read the introduction and related-work sections of A Declarative Approach to Run-Time Code Generation by Leone and Lee.) However, declarative systems usually offer less expressiveness and control over the dynamic-compilation process than do imperative systems.
Our declarative dynamic-compilation system, DyC, attempts to combine the advantages of both approaches by providing powerful and expressive but easy-to-use annotations, and declarative policies for controlling crucial aspects of the dynamic-compilation process. This approach has the potential to make declarative systems as expressive as imperative ones and to provide sufficient control to enable successful dynamic compilation of a broad range of applications.
Last updated December 3, 1997.