Document Open Access Logo

Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis

Authors Baptiste Saleil, Marc Feeley

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECOOP.2017.23.pdf
  • Filesize: 0.74 MB
  • 23 pages

Document Identifiers

Subject Classification

Keywords
  • Just-in-time compilation
  • Interprocedural optimization
  • Dynamic language
  • Higher-order function
  • Scheme

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Function duplication is widely used by JIT compilers to efficiently implement dynamic languages. When the source language supports higher order functions, the called function's identity is not generally known when compiling a call site, thus limiting the use of function duplication. This paper presents a JIT compilation technique enabling function duplication in the presence of higher order functions. Unlike existing techniques, our approach uses dynamic dispatch at call sites instead of relying on a conservative analysis to discover function identity. We have implemented the technique in a JIT compiler for Scheme.
Experiments show that it is efficient at removing type checks, allowing the removal of almost all the run time type checks for several benchmarks.
This allows the compiler to generate code up to 50% faster. We show that the technique can be used to duplicate functions using other run time information opening up new applications such as register allocation based duplication and aggressive inlining.

Cite As Get BibTex

Baptiste Saleil and Marc Feeley. Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis. In 31st European Conference on Object-Oriented Programming (ECOOP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 74, pp. 23:1-23:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECOOP.2017.23

Author Details

Baptiste Saleil
Marc Feeley

Supplementary Materials

References

  1. Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia. Dynamo: a transparent dynamic optimization system. In Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2000, pages 1-12, 2000. Google Scholar
  2. Spenser Bauman, Carl Friedrich Bolz, Robert Hirschfeld, Vasily Kirilichev, Tobias Pape, Jeremy G. Siek, and Sam Tobin-Hochstadt. Pycket: a tracing JIT for a functional language. In Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming, ICFP 2015, pages 22-34, 2015. Google Scholar
  3. Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, Michael Leuschel, Samuele Pedroni, and Armin Rigo. Allocation removal by partial evaluation in a tracing JIT. In Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM '11, pages 43-52, 2011. Google Scholar
  4. Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, and Armin Rigo. Tracing the meta-level: Pypy’s tracing JIT compiler. In Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, ICOOOLPS 2009, pages 18-25, 2009. Google Scholar
  5. Solomon Boulos and Jeremy Sugerman. Optimized execution of dynamic languages, January 26 2016. US Patent 9,244,665. Google Scholar
  6. Craig Chambers, David Ungar, and Elgin Lee. An efficient implementation of Self a dynamically-typed object-oriented language based on prototypes. In Proceedings of the 1989 Conference on Object-oriented Programming Systems, Languages and Applications, OOPSLA 1989, pages 49-70, 1989. Google Scholar
  7. Maxime Chevalier-Boisvert. On the fly type specialization without type analysis. PhD thesis, Université de Montréal, 2015. Google Scholar
  8. Maxime Chevalier-Boisvert and Marc Feeley. Simple and effective type check removal through lazy basic block versioning. In 29th European Conference on Object-Oriented Programming, ECOOP 2015, pages 101-123, 2015. Google Scholar
  9. Maxime Chevalier-Boisvert and Marc Feeley. Interprocedural type specialization of JavaScript programs without type analysis. In 30th European Conference on Object-Oriented Programming, ECOOP 2016, pages 7:1-7:24, 2016. Google Scholar
  10. Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, TOPLAS, 13(4):451-490, 1991. Google Scholar
  11. L. Peter Deutsch and Allan M. Schiffman. Efficient implementation of the Smalltalk-80 system. In Proceedings of the 11th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1984, pages 297-302, 1984. Google Scholar
  12. R. Kent Dybvig. Three Implementation Models for Scheme. PhD thesis, University of North Carolina at Chapel Hill, 1987. Google Scholar
  13. Marc Feeley. Gambit Scheme compiler v4.8.7, January 2017. URL: http://gambitscheme.org/.
  14. Andreas Gal, Brendan Eich, Mike Shaver, David Anderson, David Mandelin, Mohammad R. Haghighat, Blake Kaplan, Graydon Hoare, Boris Zbarsky, Jason Orendorff, Jesse Ruderman, Edwin W. Smith, Rick Reitmaier, Michael Bebenita, Mason Chang, and Michael Franz. Trace-based just-in-time type specialization for dynamic languages. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, pages 465-478, 2009. Google Scholar
  15. Andreas Gal, Christian W. Probst, and Michael Franz. Hotpathvm: an effective JIT compiler for resource-constrained devices. In Proceedings of the 2nd International Conference on Virtual Execution Environments, VEE 2006, pages 144-153, 2006. Google Scholar
  16. Urs Hölzle, Craig Chambers, and David Ungar. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In Proceedings of the European Conference on Object-Oriented Programming, ECOOP 1991, pages 21-38, 1991. Google Scholar
  17. Richard Kelsey, William D. Clinger, and Jonathan Rees. Revised^5 report on the algorithmic language Scheme. SIGPLAN Notices, 33(9):26-76, 1998. Google Scholar
  18. Monica Lam, Ravi Sethi, JD Ullman, and Alfred Aho. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 2006. Google Scholar
  19. Matthew Might. Environment analysis of higher-order languages. PhD thesis, Georgia Institute of Technology, 2007. Google Scholar
  20. Baptiste Saleil and Marc Feeley. Code versioning and extremely lazy compilation of Scheme. In Scheme and Functional Programming Workshop, 2014. Google Scholar
  21. Baptiste Saleil and Marc Feeley. Type check removal using lazy interprocedural code versioning. In Scheme and Functional Programming Workshop, 2015. Google Scholar
  22. Olin Shivers. Control-flow analysis of higher-order languages. PhD thesis, Carnegie Mellon University, 1991. Google Scholar
  23. Rodrigo Sol, Christophe Guillon, Fernando Magno Quintão Pereira, and Mariza A. S. Bigonha. Dynamic elimination of overflow tests in a trace compiler. In Proceedings of the 20th International Conference on Compiler Construction: Part of the Joint European Conferences on Theory and Practice of Software, CC'11/ETAPS'11, pages 2-21, 2011. Google Scholar
  24. Gerald J. Sussman and Guy L. Steele Jr. Scheme: A interpreter for extended lambda calculus. Higher-Order and Symbolic Computation, 11(4):405-439, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact