Document Open Access Logo

Interprocedural Type Specialization of JavaScript Programs Without Type Analysis

Authors Maxime Chevalier-Boisvert, Marc Feeley

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECOOP.2016.7.pdf
  • Filesize: 0.54 MB
  • 24 pages

Document Identifiers

Subject Classification

Keywords
  • Just-In-Time Compilation
  • Dynamic Language
  • Optimization
  • Object Oriented
  • JavaScript

Metrics

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

Abstract

Previous work proposed lazy basic block versioning, a technique for just-in-time compilation of dynamic languages which we believe represents an interesting point in the design space. Basic block versioning is simple to implement, simple enough that a single developer can build a complete just-in-time compiler for JavaScript in a year, yet it performs surprisingly well as it propagates
context-sensitive type information to generate type-specialized code on the fly.

In this paper, we demonstrate that lazy basic block versioning
can be extended is simple ways to propagate type information across function call boundaries. This gives some of the benefits of whole-program analysis, or a tracing compiler, without having to implement the machinery for either. We have implemented this proposal in the Higgs JavaScript virtual machine and report on the empirical evaluation of this system on a set of industry standard benchmarks. The approach eliminates 94.3 of dynamic type tests on average,
which we show is more than what is achievable with any static whole-program type analysis.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ECOOP.2016.7

Author Details

Maxime Chevalier-Boisvert
Marc Feeley

References

  1. Keith Adams, Jason Evans, Bertrand Maher, Guilherme Ottoni, Andrew Paroski, Brett Simmers, Edwin Smith, and Owen Yamauchi. The HipHop virtual machine. In Proceedings of the 2014 conference on Object Oriented Programming Systems Languages &Applications (OOPSLA), pages 777-790. ACM New York, 2014. Google Scholar
  2. Ole Agesen. The cartesian product algorithm: Simple and precise type inference of parametric polymorphism. In European Conference on Object-Oriented Programming (ECOOP), pages 2-26, 1995. Google Scholar
  3. George Almási and David Padua. MaJIC: compiling MATLAB for speed and responsiveness. In Proceedings of the 2002 conference on Programming Language Design and Implementation (PLDI), pages 294-303. ACM New York, May 2002. Google Scholar
  4. Davide Ancona, Massimo Ancona, Antonio Cuni, and Nicholas D. Matsakis. RPython: a step towards reconciling dynamically and statically typed OO languages. In Proceedings of the 2007 Dynamic Languages Symposium (DLS), pages 53-64. ACM New York, 2007. Google Scholar
  5. Christopher Anderson, Paola Giannini, and Sophia Drossopoulou. Towards type inference for JavaScript. In Proceedings of ECOOP 2005, pages 428-452. Springer Berlin Heidelberg, 2005. Google Scholar
  6. V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: a transparent dynamic optimization system. In Proceedings of the 2000 conference on Programming, pages 1-12. ACM New York, 2000. Google Scholar
  7. Michael Bebenita, Mason Chang, Gregor Wagner, Andreas Gal, Christian Wimmer, and Michael Franz. Trace-based compilation in execution environments without interpreters. In Proceedings of the 8th International Conference on the Principles and Practice of Programming in Java, PPPJ '10, pages 59-68, New York, NY, USA, 2010. ACM. Google Scholar
  8. Carl Friedrich Bolz, Antonio Cuni, Maciej FijaBkowski, 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), pages 43-52. ACM New York, 2011. Google Scholar
  9. Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, 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, pages 18-25. ACM, 2009. Google Scholar
  10. Carl Friedrich Bolz, Tobias Pape, Jeremy Siek, and Sam Tobin-Hochstadt. Meta-tracing makes a fast Racket. Workshop on Dynamic Languages and Applications, 2014. Google Scholar
  11. C. Chambers, D. Ungar, and E. Lee. An efficient implementation of Self a dynamically-typed object-oriented language based on prototypes. SIGPLAN Not., 24(10):49-70, September 1989. Google Scholar
  12. Craig Chambers and David Ungar. Customization: optimizing compiler technology for Self, a dynamically-typed object-oriented programming language. In Proceedings of the 1989 conference on Programming Language Design and Implementation (PLDI), pages 146-160. ACM New York, June 1989. Google Scholar
  13. Craig Chambers and David Ungar. Iterative type analysis and extended message splitting: Optimizing dynamically-typed object-oriented programs. In Proceedings of the 1990 conference on Programming Language Design and Implementation (PLDI), pages 150-164. ACM New York, 1990. Google Scholar
  14. 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), volume 37 of Leibniz International Proceedings in Informatics (LIPIcs), pages 101-123. Schloss Dagstuhl, 2015. URL: http://arxiv.org/abs/1411.0352.
  15. Maxime Chevalier-Boisvert, Laurie Hendren, and Clark Verbrugge. Optimizing MATLAB through just-in-time specialization. In Proceedings of the 2010 international conference on Compiler Construction (CC), pages 46-65. Springer Berlin Heidelberg, 2010. Google Scholar
  16. Michael Furr, Jong-hoon (David) An, Jeffrey S. Foster, and Michael Hicks. Static type inference for Ruby. In Proceedings of the 2009 ACM Symposium on Applied Computing (SAC), pages 1859-1866. ACM New York, 2009. Google Scholar
  17. 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. SIGPLAN Not., 44(6):465-478, June 2009. Google Scholar
  18. 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), pages 144-153. ACM New York, 2006. Google Scholar
  19. Michael Gorbovitski, Yanhong A. Liu, Scott D. Stoller, Tom Rothamel, and Tuncay K. Tekle. Alias analysis for optimization of dynamic languages. In Proceedings of the 6th Symposium on Dynamic Languages, DLS '10, pages 27-42, New York, NY, USA, 2010. ACM. Google Scholar
  20. David Gudeman. Representing type information in dynamically typed languages, 1993. Google Scholar
  21. Brian Hackett and Shu-yu Guo. Fast and precise hybrid type inference for JavaScript. In Proceedings of the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation (PLDI), pages 239-250. ACM New York, June 2012. Google Scholar
  22. 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 '91, pages 21-38, London, UK, UK, 1991. Springer-Verlag. Google Scholar
  23. Simon Holm Jensen, Anders Møller, and Peter Thiemann. Type analysis for JavaScript. In Proceedings of the 16th International Symposium on Static Analysis (SAS), pages 238-255. Springer Berlin Heidelberg, 2009. Google Scholar
  24. Simon Holm Jensen, Anders Møller, and Peter Thiemann. Interprocedural analysis with lazy propagation. In Proceedings 17th International Static Analysis Symposium (SAS). Springer Berlin Heidelberg, September 2010. Google Scholar
  25. Vineeth Kashyap, John Sarracino, John Wagner, Ben Wiedermann, and Ben Hardekopf. Type refinement for static analysis of JavaScript. In Proceedings of the 2013 Dynamic Languages Symposium (DLS. ACM New York, 2013. Google Scholar
  26. Madhukar N. Kedlaya, Jared Roesch, Behnam Robatmili, Mehrdad Reshadi, and Ben Hardekopf. Improved type specialization for dynamic scripting languages. SIGPLAN Not., 49(2):37-48, October 2013. Google Scholar
  27. Francesco Logozzo and Herman Venter. RATA: rapid atomic type analysis by abstract interpretation; application to JavaScript optimization. In Proceedings of the 2010 international conference on Compiler Construction (CC), pages 66-83. Springer Berlin Heidelberg, 2010. Google Scholar
  28. John Plevyak and Andrew A. Chien. Type directed cloning for object-oriented programs. In Proceedings of the Workshop for Languages and Compilers for Parallel Computing (LCPC), pages 566-580, 1995. Google Scholar
  29. Gregor Richards, Andreas Gal, Brendan Eich, and Jan Vitek. Automated construction of JavaScript benchmarks. In Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA), pages 677-694, 2011. Google Scholar
  30. Gregor Richards, Sylvain Lesbrene, Brian Burg, and Jan Vitek. An analysis of the dynamic behavior of JavaScript programs. In Proceedings of the ACM Programming Language Design and Implementation Conference (PLDI), June 2010. Google Scholar
  31. Armin Rigo. Representation-based just-in-time specialization and the Psyco prototype for Python. In Proceedings of the 2004 ACM SIGPLAN Symposium on Partial Evaluation and Semantics-based Program Manipulation, PEPM '04, pages 15-26, New York, NY, USA, 2004. ACM. Google Scholar
  32. Baptiste Saleil and Marc Feeley. Code versioning and extremely lazy compilation of Scheme. In Scheme and Functional Programming Workshop, 2014. Google Scholar
  33. Henrique Nazare Santos, Pericles Alves, Igor Costa, and Fernando Magno Quintao Pereira. Just-in-time value specialization. In Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), CGO '13, pages 1-11, Washington, DC, USA, 2013. IEEE Computer Society. Google Scholar
  34. Rodrigo Sol, Christophe Guillon, FernandoMagno Quintão Pereira, and Mariza A.S. Bigonha. Dynamic elimination of overflow tests in a trace compiler. In Jens Knoop, editor, Proceedings of the 2011 international conference on Compiler Construction (CC), pages 2-21. Springer Berlin Heidelberg, 2011. Google Scholar
  35. Andreas Wöß, Christian Wirth, Daniele Bonetta, Chris Seaton, Christian Humer, and Hanspeter Mössenböck. An object storage model for the Truffle language implementation framework. In Proceedings of the 2014 International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools, pages 133-144, New York, NY, USA, 2014. ACM. Google Scholar
  36. Thomas Würthinger, Andreas Wöß, Lukas Stadler, Gilles Duboscq, Doug Simon, and Christian Wimmer. Self-optimizing AST interpreters. In Proceedings of the 2012 Dynamic Language Symposium (DLS), pages 73-82. ACM New York, 2012. 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