Simple optimizing JIT compilation of higher-order dynamic programming languages
Thesis or Dissertation
2019-05 (degree granted: 2019-10-30)
Author(s)
Advisor(s)
Level
DoctoralDiscipline
InformatiqueKeywords
- Machine virtuelle
- Compilation à la volée
- Ordre supérieur
- Langage dynamique
- Spécialisation de code
- Scheme
- Inter-procédural
- VM
- JIT
- Compiler
- Higher-order
- Dynamic language
- Code specialization
- Interprocedural
- Applied Sciences - Computer Science / Sciences appliqués et technologie - Informatique (UMI : 0984)
Abstract(s)
Implémenter efficacement les langages de programmation dynamiques demande beaucoup d’effort de développement.
Les compilateurs ne cessent de devenir de plus en plus complexes.
Aujourd’hui, ils incluent souvent une phase d’interprétation, plusieurs phases de compilation, plusieurs représentations intermédiaires et des analyses de code. Toutes ces techniques permettent d’implémenter efficacement un langage de programmation dynamique, mais leur mise en oeuvre est difficile dans un contexte où les ressources de développement sont limitées.
Nous proposons une nouvelle approche et de nouvelles techniques dynamiques permettant de développer des compilateurs performants pour les langages dynamiques avec de relativement bonnes performances et un faible effort de développement.
Nous présentons une approche simple de compilation à la volée qui permet d’implémenter un langage en une seule phase de compilation, sans transformation vers des représentations intermédiaires.
Nous expliquons comment le versionnement de blocs de base, une technique de compilation existante, peut être étendue, sans effort de développement significatif, pour fonctionner interprocéduralement avec les langages de programmation d’ordre supérieur, permettant d’appliquer des optimisations interprocédurales sur ces langages.
Nous expliquons également comment le versionnement de blocs de base permet de supprimer certaines opérations utilisées pour implémenter les langages dynamiques et qui impactent les performances comme les vérifications de type.
Nous expliquons aussi comment les compilateurs peuvent exploiter les représentations dynamiques des valeurs par Tagging et NaN-boxing pour optimiser le code généré avec peu d’effort de développement.
Nous présentons également notre expérience de développement d’un compilateur à la volée pour le langage de programmation Scheme, pour montrer que ces techniques permettent effectivement de construire un compilateur avec un effort moins important que les compilateurs actuels et qu’elles permettent de générer du code efficace, qui rivalise avec les meilleures implémentations du langage Scheme. Efficiently implementing dynamic programming languages requires a significant development
effort. Over the years, compilers have become more complex. Today, they typically include
an interpretation phase, several compilation phases, several intermediate representations and
code analyses. These techniques allow efficiently implementing these programming languages
but are difficult to implement in contexts in which development resources are limited. We
propose a new approach and new techniques to build optimizing just-in-time compilers for
dynamic languages with relatively good performance and low development effort.
We present a simple just-in-time compilation approach to implement a language with
a single compilation phase, without the need to use code transformations to intermediate
representations. We explain how basic block versioning, an existing compilation technique,
can be extended without significant development effort, to work interprocedurally with higherorder
programming languages allowing interprocedural optimizations on these languages. We
also explain how basic block versioning allows removing operations used to implement dynamic
languages that degrade performance, such as type checks, and how compilers can use Tagging
and NaN-boxing to optimize the generated code with low development effort. We present our
experience of building a JIT compiler using these techniques for the Scheme programming
language to show that they indeed allow building compilers with less development effort
than other implementations and that they allow generating efficient code that competes with
current mature implementations of the Scheme language.
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.