Deferred Compilation: The Automation of Run-Time Code Generation

by Mark Leone and Peter Lee

December 1993

CMU-CS-93-225

School of Computer Science

Carnegie Mellon University

Pittsburgh, PA 15212

A more recent revision of this paper is available in postscript.

Abstract:

Deferred compilation automates the translation of ordinary programs into native machine code that performs fast optimization and native-code generation at run time. Automation is obtained through the use of a compile-time staging analysis, which determines the portions of a program that may be safely and profitably compiled at run time. Fast run-time optimization is obtained by trading space for time: compile-time specialization yields numerous run-time code generators, each customized to optimize a small portion of the source program based on run-time information. Implementation strategies developed for a prototype compiler are discussed, and the results of preliminary experiments demonstrating significant overall speedup are presented.

• Introduction
• An Example
• Strategies for Deferred Compilation
  • Stages of Computation
  • Staging Analysis
  • Limitations of Static Specialization
  • Register Allocation for Deferred Compilation
    • Compile-Time Register Allocation
    • Run-Time Register Allocation
  • Specialized Run-Time Code Generators
• Implementation
• Costs of Deferred Compilation
• Deferred Compilation vs. Partial Evaluation
• Conclusions
• Acknowledgements
• References
• Appendix A Idealized RISC
• Appendix B Extended Example

This research was partially supported by the National Science Foundation under grant #CCR-9057567. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the National Science Foundation or the US Government.