Previous: Staging Analysis Up: Strategies for Deferred Compilation Next: Register Allocation for Deferred Compilation
powgen(exp) =
))
This definition of powgen can be obtained by creating a table of
specialized versions of power, each of which is created by
choosing a value for exp from the set and
then applying a partial evaluator [Bon93] to power and
exp. Similar transformations might also be obtained
by applying staging transformation [JS86], program
bifurcation [DBV91], or procedure cloning [CHK93].
In either case, highly optimized definitions of the specialized
functions can be obtained, which can then be compiled into
high-quality machine code. Hence, one might expect this approach to
be useful in the same situations as deferred compilation.
However, there are two practical problems in performing such a
transformation automatically. First of all, there is the matter of
choosing the set of values on which to specialize. In powgen,
for example, there is no guarantee that the set
is a good one, since the range of exponents that will be supplied at
run time usually cannot be predicted. In fact, the specialization
would not in general be on simple integer values, but possibly on
arbitrary data structures.
A second problem is that all of the specialized functions must appear
in the transformed source program. This incurs a serious cost in
space usage, and is wasteful since only a few of the functions might
be used in a single program execution. In practice, a relatively
small limit must be placed on the number of specialized functions
created at compile time (represented by the constant in the above
example).
Hence, a key aspect of deferred compilation is to arrange for specialization to occur ``on demand'' (or ``just in time''). Furthermore, our desire to minimize the cost of run-time code generation leads us to specialize the compilation process itself. In other words, we wish to avoid the overhead of manipulating source programs, which one finds in a general compiler, and instead create code generators that are specialized to optimizing a fixed piece of code based on run-time values.
One can consider incorporating conventional compilation techniques into specialized run-time code generators. In fact, one of the key design issues in deferred compilation is deciding how to apportion the costs of optimization and code generation between compile time and run time. In the next section we consider the particular case of register allocation.
