Previous: Stages of Computation Up: Strategies for Deferred Compilation Next: Limitations of Static Specialization
Staging Analysis
Programs can have many stages of computation, and so a key problem is
how to identify those for which deferred compilation will be
profitable. This is similar to the problem of deciding where to
inline procedures in conventional compilation [CHT91] and the
automatic determination of specialization points during partial
evaluation [BD91][JGS93]. But as we have seen, syntactic
features of programming languages often provide clear indications of
stages that can be usefully subjected to deferred compilation. In
some cases the use of programmer-supplied hints, such as the use of
curried function syntax, would also be useful.
Once useful program stages are identified, each subexpression of the
program can be analyzed to determine (approximately) to what stage it
belongs. This is essentially a dependency analysis: a subexpression
that only depends upon values computed at or before stage 
computes
a value that also belongs to stage . Although this is
conceptually simple, approximations must be made so that the stages of
computations involving recursion can be finitely computed. Hence,
this propagation of staging information is best accomplished via a
dataflow analysis or abstract interpretation. Of course, since the
analysis is necessarily approximate, early stages might be assigned to
some expressions that are actually late, and vice versa.
Optimization opportunities are lost in the former case, and
unnecessary run-time code generation occurs in the latter case.
Hence, refining the precision of staging analysis is of fundamental
importance.
Further technical details of the staging analysis problem are beyond
the scope of this paper, but we refer the reader to the literature on
conventional binding-time analysis [Con93][JSS89], which is
precisely a staging analysis for the special case of two stages. We
have, for the time being, restricted our attention to two stages, and
we use a conventional binding-time analyzer in our prototype
compiler with good results (see
Section 4). Note,
however, that in programs where there are more than two useful
stages, a binding-time analysis forces distinct stages to be merged,
thus causing opportunities for run-time code generation to be lost.
To gain maximum benefit from deferred compilation, a generalization of
binding-time analysis to an arbitrary number of computation stages is
required.
