License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2015.101
URN: urn:nbn:de:0030-drops-52196
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5219/
Go to the corresponding LIPIcs Volume Portal

Chevalier-Boisvert, Maxime ; Feeley, Marc

Simple and Effective Type Check Removal through Lazy Basic Block Versioning

pdf-format:
9.pdf (0.9 MB)

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.

BibTeX - Entry

@InProceedings{chevalierboisvert_et_al:LIPIcs:2015:5219,
  author =	{Maxime Chevalier-Boisvert and Marc Feeley},
  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 =	{John Tang Boyland},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5219},
  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}
}

Keywords: Just-In-Time Compilation, Dynamic Optimization, Type Checking, Code Generation, JavaScript
Collection: 29th European Conference on Object-Oriented Programming (ECOOP 2015)
Issue Date: 2015
Date of publication: 29.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI