Charles Consel
ABSTRACT
Specializing programs with respect to run-time invariants is an optimization technique that has shown to improve the performance of programs substantially. It allows a program to adapt to execution contexts that are valid for a limited time.Run-time specialization is being actively investigated in a variety of areas. For example, recently, major operating system research projects have been focusing on run-time specialization as a means to obtain efficiency from highly extensible and parameterized systems.This paper describes a general approach to run-time specialization. For a given program and a declaration of its run-time invariants, it automatically produces source templates at compile time, and transforms them so that they can be processed by a standard compiler. At run time, only minor operations need to be performed: selecting and copying templates, filling holes with run-time values, and relocating jump targets. As a consequence, run-time specialization is performed very efficiently and thus does not require the specialized code to be executed many times before its cost is amortized.Our approach improves on previous work in that: (1) templates are automatically produced from the source program and its invariants, (2) the approach is not machine dependent, (3) it is formally defined and proved correct, (4) it is efficient, as shown by our implementation for the C language.
- 1.C. Chambers and D. Ungar. Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language. In ACM SIG- PLAN Conference on Programmin9 Language Design and Implementation, pages 146-160, 1989. Google Scholar
Digital Library
- 2.C. Consel and O. Danvy. From interpreting to compiling binding times. In N. D. Jones, editor, ESOP'90, 3#e European Symposium on Programming, pages 88-105, #pJ:inger-Verlo, g, 1990. Google ScholarDigital Library
- 3.C. Consel and O. Danvy. Tutorial notes on partial evaluation. In A CM Symposium on Principles of Programmzng Languages, pages 493-501, 1993. Google ScholarDigital Library
- 4.C. Consel, L. Hornof, F. No#l, J. Noy6, and N. Volanschi. A Uniform Approach for Compile-Time and Run- Tzrae Specializatton. Technical Report, University of Rennes/Inria, 1995. In preparation.Google Scholar
- 5.C. Consel and S.C. Khoo. On-hne # Off-line Partial Evaluation: Semantic Specifications and Correctness Proofs. Research Report, Yale University, New Haven, Connecticut, USA, 1993. Extended version. To appear in Journal of Functional Programming.Google Scholar
- 6.D. R. Engler and T. A. Proebsting. DCG: an efficient, retargetable dynamic code generation system. In ACM Conference on Architectural Support for Programming Languages and Operating Systems, 1994. Google ScholarDigital Library
- 7.C. W. Fraser and D. R. Hanson. A code generation interface for ANSI C. Software - Practice and Experience, 21(9):963-988, 1991. Google ScholarDigital Library
- 8.N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluatwn and Automatic Program Generation. Prentice-HM1 International, 1993. Google ScholarDigital Library
- 9.D. Keppel, S. Eggers, and R. Henry. A Ca#e for Runtime Code Generation. Technical Report, University of Washington, Seattle, Washington, 1991.Google Scholar
- 10.D. Keppel, S. Eggers, and R. Henry. Evaluating Runtime Compded Value-Specific Optimzzations. Technical Report 93-11-02, University of Washington, Seattle, Washington, 1993.Google Scholar
- 11.M. Leone and P. Lee. Lightweight run-time code generation. In A CM Workshop on Partial Evaluation and Semantics-Based Program Man,pulatzon, pages 97-106, 1994.Google Scholar
- 12.B. N. Locanthi. Fast bitblt with asm() and cpp. In European Unzx Users Group Conference Proceedings (#UUG), 1987.Google Scholar
- 13.H. Massalin and C. Pu. Threads and input/output in the Synthesis kernel. In A CM Symposium on Operating Systems Princwles, pages 191-201, 1989. Google ScholarDigital Library
- 14.R. Pike, B. N. Locanthi, and J.F. Raiser. Hardware/software trade-offs for bitmap graphics on the blit. Software - Practice and Expemence, 15(2):131-151, 1985.Google Scholar
- 15.C. Pu, T. Autrey, A. Black, C. Consel, C. Cowan, J. Inouye, L. Kethana, J. WMpole, and K. Zhang. Optimistic incremental specialization: streamlining a commercial operating system. In A CM Symposium on Operating Systems Principles, 1995. To appear. Google ScholarDigital Library
- 16.C. Pu, H. Massalin, and J. Ioannidis. The Synthesis kernel. A CM Computing Systems, 1(1):11-32, 1988.Google Scholar
Index Terms
- A general approach for run-time specialization and its application to C
Recommendations
Efficient incremental run-time specialization for free
PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementationAvailability of data in a program determines computation stages. Incremental partial evaluation exploit these stages for optimization: it allows further specialization to be performed as data become available at later stages. The fundamental advantage ...
Supporting objects in run-time bytecode specialization
ASIA-PEPM '02: Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulationThis paper describes a run-time specialization system for the Java language. One of the main difficulties of supporting the full Java language resides in a sound yet effective management of references to objects. This is because the specialization ...
Automatic, Template-Based Run-Time Specialization: Implementation and Experimental Study
ICCL '98: Proceedings of the 1998 International Conference on Computer LanguagesSpecializing programs with respect to run-time values has been shown to drastically improve code performance on realistic programs ranging from operating systems to graphics. Recently, various approaches to specializing code at run-time have been ...
Comments