Efficient incremental run-time specialization for free

ABSTRACT

Availability 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 of incremental specialization is to factorize the specialization process. As a result, specializing a program at a given stage costs considerably less than specializing it once all the data are available.We present a realistic and flexible approach to achieve efficient incremental run-time specialization. Rather than developing specific techniques, as previously proposed, we are able to re-use existing technology by iterating a specialization process. Moreover, in doing so, we do not lose any specialization opportunities. This approach makes it possible to exploit nested quasi-invariants and to speed up the run-time specialization process.This approach has been implemented in Tempo, a specializer for C programs that is publicly available. A preliminary experiment confirm that incremental that incremental specialization can greatly speed up the specialization process.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Alexander Aiken , Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su, A Toolkit for Constructing Type- and Constraint-Based Program Analyses, Proceedings of the Second International Workshop on Types in Compilation, p.78-96, March 25-27, 1998
• 3: Joel Auslander , Matthai Philipose , Craig Chambers , Susan J. Eggers , Brian N. Bershad, Fast, effective dynamic compilation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.149-159, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 4: Tito Autrey , Michael Wolfe, Initial Results for Glacial Variable Analysis, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.120-134, August 08-10, 1996
• 5: C. Consel , L. Hornof , R. Marlet , G. Muller , S. Thibault , E.-N. Volanschi , J. Lawall , J. Noyé, Tempo: specializing systems applications and beyond, ACM Computing Surveys (CSUR), v.30 n.3es, Sept. 1998 [doi>10.1145/289121.289140]
• 6: Charles Consel , Luke Hornof , François Noël , Jacques Noyé , Nicolae Volansche, A Uniform Approach for Compile-Time and Run-Time Specialization, Selected Papers from the Internaltional Seminar on Partial Evaluation, p.54-72, February 12-16, 1996
• 7: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 8: Charles Consel , Calton Pu , Jonathan Walpole, Incremental partial evaluation: the key to high performance, modularity and portability in operating systems, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.44-46, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154635]
• 9: Dawson R. Engler , Wilson C. Hsieh , M. Frans Kaashoek, C: a language for high-level, efficient, and machine-independent dynamic code generation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.131-144, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237765]
• 10: Bertil Folliot , Ian Piumarta , Fabio Riccardi, A dynamically configurable, multi-language execution platform, Proceedings of the 8th ACM SIGOPS European workshop on Support for composing distributed applications, p.175-181, September 1998, Sintra, Portugal [doi>10.1145/319195.319222]
• 11: Robert Glück, Towards multiple self-application, ACM SIGPLAN Notices, v.26 n.9, p.309-320, Sept. 1991
• 12: Robert Glück , Jesper Jørgensen, Efficient Multi-level Generating Extensions for Program Specialization, Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.259-278, September 20-22, 1995
• 13: Robert Glück , Jesper Jørgensen, An Automatic Program Generator for Multi-Level Specialization, Lisp and Symbolic Computation, v.10 n.2, p.113-158, July 1997 [doi>10.1023/A:1007763000430 ]
• 14: Brian Grant , Markus Mock , Matthai Philipose , Craig Chambers , Susan J. Eggers, Annotation-directed run-time specialization in C, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.163-178, June 12-13, 1997, Amsterdam, The Netherlands
• 15: Luke Hornof , Charles Consel , Jacques Noyé, Effective Specialization of Realistic Programs via Use Sensitivity, Proceedings of the 4th International Symposium on Static Analysis, p.293-314, September 08-10, 1997
• 16: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 17: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• 18: J.L. Lawall. Faster Fourier transforms via automatic program specialization. Publication interne 1192, IRISA, Rennes, France, May 1998.
• 19: Peter Lee , Mark Leone, Optimizing ML with run-time code generation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.137-148, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 20: R. Marlet , S. Thibault , C. Consel, Mapping software architectures to efficient implementations via partial evaluation, Proceedings of the 12th international conference on Automated software engineering (formerly: KBSE), p.183, November 02-05, 1997
• 21: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 22: G. Muller , R. Marlet , E.-N. Volanschi , C. Consel , C. Pu , A. Goel, Fast, Optimized Sun RPC Using Automatic Program Specialization, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.240, May 26-29, 1998
• 23: F. NoiS1. Sp~cialisation dynamique de code par ~valuation partielle. PhD thesis, Universit~ de Rennes I, October 1996. In French.
• 24: Francois Noel , Luke Hornof , Charles Consel , Julia L. Lawall, Automatic, Template-Based Run-Time Specialization: Implementation and Experimental Study, Proceedings of the 1998 International Conference on Computer Languages, p.132, May 14-16, 1998
• 25: Proceedings of the A CM $IGPLAN '96 Conference on Programming Language Design and Implementation, Philadelphia, PA, May 1996. ACM SIG- PLAN Notices, 31 (5).
• 26: Proceedings of the A CM SIGPLAN '97 Conference on Programming Language Design and Implementation, Las Vegas, Nevada, June 15-18, 1997.
• 27: Massimiliano Poletto , Dawson R. Engler , M. Frans Kaashoek, tcc: a system for fast, flexible, and high-level dynamic code generation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.109-121, June 16-18, 1997, Las Vegas, Nevada, United States
• 28: Conference Record of the 23rd Annual A CM $IGPLAN-$IGACT Symposium on Principles Of Programming Languages, St. Petersburg Beach, FL, USA, January 1996. ACM Press.
• 29: C. Pu , T. Autrey , A. Black , C. Consel , C. Cowan , J. Inouye , L. Kethana , J. Walpole , K. Zhang, Optimistic incremental specialization: streamlining a commercial operating system, ACM SIGOPS Operating Systems Review, v.29 n.5, p.314-321, Dec. 3, 1995
• 30: Michael Sperber , Peter Thiemann, Two for the price of one: composing partial evaluation and compilation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.215-225, June 16-18, 1997, Las Vegas, Nevada, United States
• 31: S. Thibault , C. Consel , G. Muller, Safe and Efficient Active Network Programming, Proceedings of the The 17th IEEE Symposium on Reliable Distributed Systems, p.135, October 20-23, 1998
• 32: S. Thibault, R. Marlet, and C. ConseI. A domainspecific language for video device drivers: from design to implementation. In Conference on Domain Specific Languages, pages 11-26, Santa Barbara, CA, October 1997. Usenix.
• 33: Peter J. Thiemann, Cogen in six lines, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.180-189, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 34: E. N. Volanschi. Une approche automatique d la sp~cialisation de composants syst~me. Th~se de doctorat, Universit~ de Rennes I, February 1998.
• 35: Philip Wickline , Peter Lee , Frank Pfenning, Run-time code generation and modal-ML, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.224-235, June 17-19, 1998, Montreal, Quebec, Canada
• 36: Kwangkeun Yi , Williams Ludwell Harrison, III, Automatic generation and management of interprocedural program analyses, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.246-259, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158642]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Design, Experimentation, Languages, Performance, Theory