Search Results

Documents authored by Feeley, Marc

Document
DOI: 10.4230/LIPIcs.ECOOP.2024.28
Static Basic Block Versioning

Authors: Olivier Melançon, Marc Feeley, and Manuel Serrano

Published in: LIPIcs, Volume 313, 38th European Conference on Object-Oriented Programming (ECOOP 2024)

Abstract
Basic Block Versioning (BBV) is a compilation technique for optimizing program execution. It consists in duplicating and specializing basic blocks of code according to the execution contexts of the blocks, up to a version limit. BBV has been used in Just-In-Time (JIT) compilers for reducing the dynamic type checks of dynamic languages. Our work revisits the BBV technique to adapt it to Ahead-of-Time (AOT) compilation. This Static BBV (SBBV) raises new challenges, most importantly how to ensure the convergence of the algorithm when the specializations of the basic blocks are not based on profiled variable values and how to select the good specialization contexts. SBBV opens new opportunities for more precise optimizations as the compiler can explore multiple versions and only keep those within the version limit that yield better generated code. In this paper, we present the main SBBV algorithm and its use to optimize the dynamic type checks, array bound checks, and mixed-type arithmetic operators often found in dynamic languages. We have implemented SBBV in two AOT compilers for the Scheme programming language that we have used to evaluate the technique’s effectiveness. On a suite of benchmarks, we have observed that even with a low limit of 2 versions, SBBV greatly reduces the number of dynamic type tests (by 54% and 62% on average) and accelerates the execution time (by about 10% on average). Previous work has needed a higher version limit to achieve a similar level of optimization. We also observe a small impact on compilation time and code size (a decrease in some cases).
Cite as

Olivier Melançon, Marc Feeley, and Manuel Serrano. Static Basic Block Versioning. In 38th European Conference on Object-Oriented Programming (ECOOP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 313, pp. 28:1-28:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{melancon_et_al:LIPIcs.ECOOP.2024.28,
  author =	{Melan\c{c}on, Olivier and Feeley, Marc and Serrano, Manuel},
  title =	{{Static Basic Block Versioning}},
  booktitle =	{38th European Conference on Object-Oriented Programming (ECOOP 2024)},
  pages =	{28:1--28:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-341-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{313},
  editor =	{Aldrich, Jonathan and Salvaneschi, Guido},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2024.28},
  URN =		{urn:nbn:de:0030-drops-208770},
  doi =		{10.4230/LIPIcs.ECOOP.2024.28},
  annote =	{Keywords: Compiler, Ahead-of-Time Compilation, Optimization, Dynamic Languages}
}
Document
DOI: 10.4230/DARTS.3.2.14
Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis (Artifact)

Authors: Baptiste Saleil and Marc Feeley

Published in: DARTS, Volume 3, Issue 2, Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract
This artifact is based on LC, a research oriented JIT compiler for Scheme. The compiler is extended to allow interprocedural, type based, code specialization using the technique and its implementation presented in the paper. Because the technique is directly implemented in LC, the package contains the build of the compiler used for our experiments. To support repeatability, the artifact allows the user to easily extract the data presented in the paper such as the number of executed type checks or the generated code size. The user can repeat the experiments using a set of standard benchmarks as well as its own programs. Instructions for building the compiler from scratch are also provided.
Cite as

Baptiste Saleil and Marc Feeley. Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis (Artifact). In Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017). Dagstuhl Artifacts Series (DARTS), Volume 3, Issue 2, pp. 14:1-14:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{saleil_et_al:DARTS.3.2.14,
  author =	{Saleil, Baptiste and Feeley, Marc},
  title =	{{Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis (Artifact)}},
  pages =	{14:1--14:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2017},
  volume =	{3},
  number =	{2},
  editor =	{Saleil, Baptiste and Feeley, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.3.2.14},
  URN =		{urn:nbn:de:0030-drops-72952},
  doi =		{10.4230/DARTS.3.2.14},
  annote =	{Keywords: just-in-time compilation, interprocedural optimization, dynamic language, higher-order function, scheme}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2017.23
Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis

Authors: Baptiste Saleil and Marc Feeley

Published in: LIPIcs, Volume 74, 31st European Conference on Object-Oriented Programming (ECOOP 2017)

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

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)

Copy BibTex To Clipboard

@InProceedings{saleil_et_al:LIPIcs.ECOOP.2017.23,
  author =	{Saleil, Baptiste and Feeley, Marc},
  title =	{{Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{23:1--23:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{M\"{u}ller, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.23},
  URN =		{urn:nbn:de:0030-drops-72711},
  doi =		{10.4230/LIPIcs.ECOOP.2017.23},
  annote =	{Keywords: Just-in-time compilation, Interprocedural optimization, Dynamic language, Higher-order function, Scheme}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2016.7
Interprocedural Type Specialization of JavaScript Programs Without Type Analysis

Authors: Maxime Chevalier-Boisvert and Marc Feeley

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

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

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)

Copy BibTex To Clipboard

@InProceedings{chevalierboisvert_et_al:LIPIcs.ECOOP.2016.7,
  author =	{Chevalier-Boisvert, Maxime and Feeley, Marc},
  title =	{{Interprocedural Type Specialization of JavaScript Programs Without Type Analysis}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.7},
  URN =		{urn:nbn:de:0030-drops-61019},
  doi =		{10.4230/LIPIcs.ECOOP.2016.7},
  annote =	{Keywords: Just-In-Time Compilation, Dynamic Language, Optimization, Object Oriented, JavaScript}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2015.101
Simple and Effective Type Check Removal through Lazy Basic Block Versioning

Authors: Maxime Chevalier-Boisvert and Marc Feeley

Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract
Dynamically typed programming languages such as JavaScript and Python defer type checking to run time. In order to maximize performance, dynamic language VM implementations must attempt to eliminate redundant dynamic type checks. However, type inference analyses are often costly and involve tradeoffs between compilation time and resulting precision. This has lead to the creation of increasingly complex multi-tiered VM architectures. This paper introduces lazy basic block versioning, a simple JIT compilation technique which effectively removes redundant type checks from critical code paths. This novel approach lazily generates type-specialized versions of basic blocks on-the-fly while propagating context-dependent type information. This does not require the use of costly program analyses, is not restricted by the precision limitations of traditional type analyses and avoids the implementation complexity of speculative optimization techniques. We have implemented intraprocedural lazy basic block versioning in a JavaScript JIT compiler. This approach is compared with a classical flow-based type analysis. Lazy basic block versioning performs as well or better on all benchmarks. On average, 71% of type tests are eliminated, yielding speedups of up to 50%. We also show that our implementation generates more efficient machine code than TraceMonkey, a tracing JIT compiler for JavaScript, on several benchmarks. The combination of implementation simplicity, low algorithmic complexity and good run time performance makes basic block versioning attractive for baseline JIT compilers.
Cite as

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 101-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{chevalierboisvert_et_al:LIPIcs.ECOOP.2015.101,
  author =	{Chevalier-Boisvert, Maxime and Feeley, Marc},
  title =	{{Simple and Effective Type Check Removal through Lazy Basic Block Versioning}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{101--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.101},
  URN =		{urn:nbn:de:0030-drops-52196},
  doi =		{10.4230/LIPIcs.ECOOP.2015.101},
  annote =	{Keywords: Just-In-Time Compilation, Dynamic Optimization, Type Checking, Code Generation, JavaScript}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact