Previous: Strategies for Deferred Compilation Up: Strategies for Deferred Compilation Next: Staging Analysis
A similar phenomenon occurs in programs with nested loops. The outer loop index is always computed before executing inner loops, and substantial benefits might be obtained by specializing inner loops to its value at each iteration. More deeply nested loops lead to more stages of computation.
Computation stages arise naturally from other programming language constructs. Macros in Scheme and other languages are early computation stages that have been manually identified by the programmer; macro expansion performs these computations before compiler optimizations are applied. In Standard ML the phase-distinction property of the modules sublanguage guarantees that arguments to functors are available at an earlier stage than arguments to functions [HMM90]. Hence, deferred compilation can be used to compile functors into code that will generate optimized function code at functor-application time. Functor application is similar to the linking of object code in conventional languages, the speed of which is not a high priority, so deferring highly aggressive optimizations to this stage appears practical [HBHM93]. Link-time optimization has also been studied by Srivastava and Wall [SW93].
In practice, programmers often arrange for computations to be staged so that the costs of early computations can be amortized over many late computations [CPW93]. For example, in a Standard ML implementation of a network communications system, Biagioni et al. [BHL93] describe the structure of a send procedure with the type
send : connection -> message -> unit
The computation is staged so that send analyzes the connection
and then selects one of several possible message-sending procedures (of
type message -> unit). Since many messages are usually sent on a
connection, this allows the cost of connection-specific processing to be
amortized over all of the message sends. Deferred compilation
can exploit such staging even if it is not explicit in the program text.
We have restricted our attention to two computation stages in this paper in order to simplify the presentation. In general, however, programs exhibit many more stages, and deferred compilation can in principle exploit an arbitrary number. Consider the case of a function of three arguments, f(x,y,z), in which the argument x changes more slowly than y which in turn changes more slowly than z. In this case it may be profitable to identify three computation stages (call them ``early,'' ``middle,'' and ``late'') and generate code for an fgen function that, given the first argument, generates the code of another specialized code generator.
