[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A uniform approach for compile-time and run-time specialization

  • Conference paper
  • First Online:
Partial Evaluation

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1110))

Abstract

As partial evaluation gets more mature, it is now possible to use this program transformation technique to tackle realistic languages and real-size application programs. However, this evolution raises a number of critical issues that need to be addressed before the approach becomes truly practical.

First of all, most existing partial evaluators have been developed based on the assumption that they could process any kind of application program. This attempt to develop universal partial evaluators does not address some critical needs of real-size application programs. Furthermore, as partial evaluators treat richer and richer languages, their size and complexity increase drastically. This increasing complexity revealed the need to enhance design principles. Finally, exclusively specializing programs at compile time seriously limits the applicability of partial evaluation since a large class of invariants in real-size programs are not known until run time and therefore cannot be taken into account.

In this paper, we propose design principles and techniques to deal with each of these issues.

By defining an architecture for a partial evaluator and its essential components, we are able to tackle a rich language like C without compromising the design and the structure of the resulting implementation.

By designing a partial evaluator targeted towards a specific application area, namely system software, we have developed a system capable of treating realistic programs.

Because our approach to designing a partial evaluator clearly separates preprocessing and processing aspects, we are able to introduce run-time specialization in our partial evaluation system as a new way of exploiting information produced by the preprocessing phase.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. L.O. Andersen.-Self-applicable C program specialization.-In Partial Evaluation and Semantics-Based Program Manipulation, pages 54–61, San Francisco, CA, USA, June 1992. Yale University, Hew Haven, CT, USA.-Technical Report YALEU/DCS/RR-909.

    Google Scholar 

  2. L.O. Andersen.-Program Analysis and Specialization for the C Programming Language.-PhD thesis, Computer Science Department, University of Copenhagen, May 1994.-DIKU Technical Report 94/19.

    Google Scholar 

  3. J. Auslander, M. Philipose, C. Chambers, S.J. Eggers, and B.N. Bershad.-Fast, effective dynamic compilation.-In PLDI96 [35].-To appear.

    Google Scholar 

  4. R. Baier, R. Glück, and R. Zöchling.-Partial evaluation of numerical programs in Fortran.-In PEPM94 [33], pages 119–132.

    Google Scholar 

  5. B.N. Bershad, S. Savage, P. Pardyak, E. Gün Sirer, M.E. Fiuczynski, D. Becker, C. Chambers, and S. Eggers.-Extensibility, safety and performance in the SPIN operating system.-In SOSP95 [41], pages 267–283.

    Google Scholar 

  6. L. Birkedal and M. Welinder.-Partial evaluation of Standard ML.-Master's thesis, Computer Science Department, University of Copenhagen, 1993.-Research Report 93/22.

    Google Scholar 

  7. D.R. Chase, M. Wegman, and F. Kenneth Zadeck.-Analysis of pointers and structures.-In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 296–310, White Plains, NY, USA, June 1990. ACM Press.-ACM SIGPLAN Notices, 25(6).

    Google Scholar 

  8. C. Consel.-Polyvariant binding-time analysis for applicative languages.-In PEPM93 [32]June, pages 145–154.

    Google Scholar 

  9. C. Consel.-A tour of Schism.-In PEPM93 [32]June, pages 66–77.

    Google Scholar 

  10. C. Consel and O. Danvy.-From interpreting to compiling binding times.-In N.D. Jones, editor, ESOP'90, 3 rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 88–105. Springer-Verlag, 1990.

    Google Scholar 

  11. C. Consel and O. Danvy.-For a better support of static data flow.-In J. Hughes, editor, Proceedings of the 5 th ACM conference on Functional Programming Languages and Computer Architecture, volume 523 of Lecture Notes in Computer Science, pages 496–519, Cambridge, MA, USA, August 1991. Springer-Verlag.

    Google Scholar 

  12. C. Consel and O. Danvy.-Tutorial notes on partial evaluation.-In Proceedings of the 20 th Annual ACM SIGPLAN-SIGACT Symposium on Principles Of Programming Languages, pages 493–501, Charleston, SC, USA, January 1993. ACM Press.

    Google Scholar 

  13. C. Consel and F. NoËl.-A general approach for run-time specialization and its application to C.-In POPL96 [36]., pages 145–156.

    Google Scholar 

  14. C. Consel, C. Pu, and J. Walpole.-Incremental specialization: The key to high performance, modularity and portability in operating systems.-In PEPM93 [32]June.

    Google Scholar 

  15. C. Consel, C. Pu, and J. Walpole.-Making production OS kernel adaptive: Incremental specialization in practice.-Technical report, Department of Computer Science and Engineering, Oregon Graduate Institute of Science & Technology, 1994.

    Google Scholar 

  16. M. Emami, R. Ghiya, and L.J. Hendren.-Context-sensitive interprocedural points-to analysis in the presence of function pointers.-In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 242–256. ACM Press, June 1994.-ACM SIGPLAN Notices, 29(6).

    Google Scholar 

  17. D.R. Engler, W.C. Hsieh, and M.F. Kaashoek.-C: A language for high-level, efficient, and machine-independent dynamic code generation.-In POPL96 [36]., pages 131–144.

    Google Scholar 

  18. D.R. Engler, M.F. Kaashoek, and J.W. O'Toole.-Exokernel: An operating system architecture for application-level resource management.-In SOSP95 [41], pages 251–266.

    Google Scholar 

  19. D.R. Engler and T.A. Proebsting.-DCG: An efficient retargetable dynamic code generation system.-In Proceedings of the Sixth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS VI), pages 263–273. ACM Press, November 1994.

    Google Scholar 

  20. A.M. Erosa and L.J. Hendren.-Taming control flow: A structured approach to eliminating goto statements.-In Proceedings of the IEEE 1994 International Conference on Computer Languages, May 1994.

    Google Scholar 

  21. A.P. Ershov.-On the essence of translation.-Computer Software and System Programming, 3(5):332–346, 1977.

    Google Scholar 

  22. N.D. Jones, C. Gomard, and P. Sestoft.-Partial Evaluation and Automatic Program Generation.-International Series in Computer Science. Prentice-Hall, June 1993.

    Google Scholar 

  23. N.D. Jones and S.S. Muchnick.-TEMPO: A Unified Treatment of Binding Time and Parameter Passing Concepts in Programming Languages, volume 66 of Lecture Notes in Computer Science.-Springer-Verlag, 1978.

    Google Scholar 

  24. N.D. Jones, P. Sestoft, and H. Søndergaard.-Mix: a self-applicable partial evaluator for experiments in compiler generation.-Lisp and Symbolic Computation, 2(1):9–50, 1989.

    Google Scholar 

  25. D. Keppel, S. Eggers, and R. Henry.-Evaluating runtime compiled value-specific optimizations.-Technical Report 93-11-02, Department of Computer Science, University of Washington, Seattle, WA, 1993.

    Google Scholar 

  26. M. Leone and P. Lee.-Lightweight run-time code generation.-In PEPM94 [33].

    Google Scholar 

  27. M. Leone and P. Lee.-Optimizing ML with run-time code generation.-In PLDI96 [35].-To appear.

    Google Scholar 

  28. U. Meyer.-Techniques for partial evaluation of imperative languages.-In Partial Evaluation and Semantics-Based Program Manipulation, pages 94–105, New Haven, CT, USA, September 1991.-ACM SIGPLAN Notices, 26(9).

    Google Scholar 

  29. A.B. Montz, D. Mosberger, S.W. O'Malley, L.L. Peterson, T.A. Proebsting, and J.H. Hartman.-Scout: A communications-oriented operating system.-Technical Report 94-20, Department of Computer Science, The University of Arizona, 1994.

    Google Scholar 

  30. F. Nielson.-A denotational framework for data flow analysis.-Acta Informatica, 18(3):265–287, 1982.

    Google Scholar 

  31. V. Nirkhe and W. Pugh.-Partial evaluation and high-level imperative programming languages with applications in hard real-time systems.-In Proceedings of the 19 th Annual ACM SIGPLAN-SIGACT Symposium on Principles Of Programming Languages, pages 269–280, Albuquerque, New Mexico, USA, January 1992. ACM Press.

    Google Scholar 

  32. Partial Evaluation and Semantics-Based Program Manipulation, Copenhagen, Denmark, June 1993. Yale University, Hew Haven, CT, USA.

    Google Scholar 

  33. ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation. Technical Report 94/9, University of Melbourne, Australia, 1994.

    Google Scholar 

  34. Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation. ACM Press, June 1995.-ACM SIGPLAN Notices, 30(6).

    Google Scholar 

  35. Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, Philadelphia, PA, May 1996. ACM Press.-To appear.

    Google Scholar 

  36. Proceedings of the 23rd Annual ACM SIGPLAN-SIGACT Symposium on Principles Of Programming Languages, St. Petersburg Beach, FL, USA, January 1996. ACM Press.

    Google Scholar 

  37. C. Pu, T. Autrey, A. Black, C. Consel, C. Cowan, J. Inouye, L. Kethana, J. Walpole, and K. Zhang.-Optimistic incremental specialization: Streamlining a commercial operating system.-In SOSP95 [41], pages 314–324.

    Google Scholar 

  38. C. Pu, H. Massalin, and J. Ioannidis.-The Synthesis kernel.-Computing Systems, 1(1):11–32, Winter 1988.

    Google Scholar 

  39. V. Rozier, V. Abrossimov, F. Armand, I. Boule, M. Gien, M. Guillemont, F. Herrmann, C. Kaiser, S. Langlois, P. Léonard, and W. Neuhauser.-Overview of the Chorus distributed operating system.-In USENIX — Workshop Proceedings-Micro-kernels and Other Kernel Architectures, pages 39–70, Seattle, WA, USA, April 1992.

    Google Scholar 

  40. E. Ruf.-Context-insensitive alias analysis reconsidered.-In PLDI95 [34], pages 13–22.-ACM SIGPLAN Notices, 30(6).

    Google Scholar 

  41. Proceedings of the 1995 ACM Symposium on Operating Systems Principles, Copper Mountain Resort, CO, USA, December 1995. ACM Operating Systems Reviews, 29(5).

    Google Scholar 

  42. E.N. Volanschi, G. Muller, and C. Consel.-Safe operating system specialization: the RPC case study.-In Workshop Record of WCSSS'96 — The Inaugural Workshop on Compiler Support for Systems Software, pages 24–28, Tucson, AZ, USA, February 1996.

    Google Scholar 

  43. R.P. Wilson, R.S. French, C.S. Wilson, S.P. Amarasinghe, J.M. Anderson, S.W.K. Tjiang, S.-W. Liao, C.-W. Tseng, M.W. Hall, M.S. Lam, and J.L. Hennessy.-SUIF: An infrastructure for research on parallelizing and optimizing compilers.-ACM SIGPLAN Notices, 29(12):31–37, December 94.

    Google Scholar 

  44. R.P. Wilson and M.S. Lam.-Efficient context-sensitive pointer analysis of C programs.-In PLDI95 [34], pages 1–12.-ACM SIGPLAN Notices, 30(6).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université de Rennes/Irisa Campus Universitaire de Beaulieu, 35042, Rennes Cedex, France

    Charles Consel, Luke Hornof, FranÇois NoËl, Jacques Noyé & Nicolae Volanschi

Authors
  1. Charles Consel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luke Hornof
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. FranÇois NoËl
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jacques Noyé
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Nicolae Volanschi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Olivier Danvy Robert Glück Peter Thiemann

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Consel, C., Hornof, L., NoËl, F., Noyé, J., Volanschi, N. (1996). A uniform approach for compile-time and run-time specialization. In: Danvy, O., Glück, R., Thiemann, P. (eds) Partial Evaluation. Lecture Notes in Computer Science, vol 1110. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61580-6_4

Download citation

  • DOI: https://doi.org/10.1007/3-540-61580-6_4

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61580-4

  • Online ISBN: 978-3-540-70589-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation