Previous: Deferred Compilation:
The Automation of Run-Time Code Generation Up: Deferred Compilation:
The Automation of Run-Time Code Generation Next: An Example
Many compiler optimization techniques depend on static analysis to determine invariants about a program's run-time behavior. As a result, a great deal of research has been invested in the development of various approaches to static program analysis, particularly in the areas of dataflow analysis, abstract interpretation, and nonstandard forms of type inference. Despite good progress, such analyses tend to be excessively conservative in practice, thus making it difficult for a compiler to achieve thorough optimization of programs. This is, of course, a fundamental problem since most aspects of program run-time behavior are undecidable. Also, as a practical matter, further compromises in precision must be made in order to cope with the complexity and inefficiency of many analysis algorithms.
An alternative approach is to defer at least some of the analysis and optimization (and therefore also code generation) to run time. While this does not avoid the fundamental problems of undecidability and inefficiency, it does make possible the use of run-time values in improving code quality. This is an old idea that has been applied in many different ways. For example, for regular expression search, Thompson describes what essentially amounts to a compiler for regular expressions. A program can invoke this compiler at run time to obtain machine code optimized for a specific regular expression [Tho68]. A similar approach has also been applied to bitblt [PLR85] and to the implementation of operating system services [MP89][Mas92]. For general programming, Keppel, Eggers, and Henry have studied several manual methods for obtaining such ``application-specific'' compilers, and they show that good results are possible for realistic C programs [KEH93].
There are other ways to improve program performance using run-time information. For example, the compiler can arrange for programs to collect run-time data during development and testing, and then use the collected profile information in optimizing the code for final delivery [Wal91]. Koopman and Lee obtained improvements in the performance of a lazy functional language by implementing graph reduction as self-modifying code [KLS92]. And, of course, there have been countless other applications of self-modifying code.
In this paper, we report on our experience with a new approach to generating optimized code at run time. We have implemented a prototype compiler, which we call FABIUS, that can automatically compile a general program into RISC machine code that in turn generates optimized machine code at run time. There are several notable examples of compilers for object-oriented languages that perform aspects of compilation at run time, including the Smalltalk-80 system by Deutsch and Schiffman [DS84] and the SELF compiler by Chambers and Ungar [CU89]. The approach we have taken differs in a number of crucial ways. Perhaps most fundamentally, we compile a functional programming language and hence are able to take advantage of previously developed techniques for compiling and transforming functional programs, including aspects of offline partial evaluation [JGS93][JSS89]. This also facilitates the development of an automatic staging analysis that allows code to be dynamically generated for any part of a program, rather than being restricted to particular points such as method (procedure) invocations.
Other salient characteristics of our approach, which we term deferred compilation, are as follows:
In preliminary experiments, we have found that the overhead of deferred compilation is often quite small when compared to the performance gain. Furthermore, we have encountered unique design tradeoffs in considering which aspects of optimization and code generation should be performed statically and which should be deferred to run time. We see some encouraging signs that deferred compilation can be practical, and find that there is much further work to be done.
To introduce deferred compilation, we begin with a simple example that illustrates the basic points. Then in Section 3 we give an overview of some strategies and techniques for deferred compilation. Our desire to keep the cost of run-time code generation as low as possible leads to several important practical considerations. In Section 4 we describe some of the details of a prototype implementation and present the results of preliminary experiments with the system. This is followed by sections on the secondary costs of run-time code generation and the connections between deferred compilation and partial evaluation.
