CompGen: Generation of Fast Compilers in a Multi-Language VM

CompGen: Generation of Fast Compilers in a Multi-Language VM

Florian Latifi, David Leopoldseder, Christian Wimmer, Hanspeter Moessenboeck

16 October 2021

The first Futamura projection enables compilation and high performance code generation of user programs by partial evaluation of language interpreters. Previous work has shown that it is sufficient to leverage profiling information and use partial evaluation directives in interpreters as hints to drive partial evaluation towards compiled code efficiency. However, this comes with the downside of additional application warm-up time: Partial evaluation of language interpreters has to specialize interpreter code on the fly to the dynamic types used at run time to create efficient target code. As a result, the tie spend on partial evaluation itself is a significant contributor to the overall compile time of a method. The second Futamura projection solves this problem by self-applying partial evaluation on the partial evaluation algorithm, effectively generating language-specific compilers from interpreters. This typically reduces compilation time compared to the first projection. Previous work employed the second projection to some extent, however to this day, no generic second Futamura projection approach is used in a state-of-the-art language runtime. Ultimately, the problems of code-size explosion for compiler generation and warm-up time increases are unsolved problems subject to research to this day. To solve the problems of code-size explosion and self-application warm-up this paper proposes \emph{CompGen}, an approach based on code generation of subsets of language interpreters which is loosely based upon the idea of the second Futamura projection. We implemented a prototype of CompGen for \textit{GraalVM} and show that our usage of a novel code-generation algorithm, incorporating interpreter directives allows to generate efficient compilers that emit fast target programs which easily outperform the first Fumatura projection in compilation time. We evaluated our approach with \textit{GraalJS}, an ECMAScript-compliant interpreter, and standard JavaScript benchmarks, showing that our approach achieves $2-3X$ speedups of partial evaluation.


Venue : Dynamic Language Symposium, DLS co-located with SPLASH conference 2021. DLS 2021 https://conf.researchr.org/home/dls-2021 SPLASH 2021 Sun 17 - Fri 22 October 2021 Chicago, Illinois Dates * Wed 2 Jun 2021 Abstract submission (optional) * Wed 9 Jun 2021 Paper submission * Thu 8 Jul 2021 First phase notification * Wed 4 Aug 2021 First phase notifications Thu 19 Aug 2021 Final notificat