Table des Contenus

Behind the Scenes of the OCaml Optimising Compiler Flambda2: Introduction and Roadmap

Date: 2024-03-18
Catégorie: OCaml



Introducing our Flambda2 snippets

At OCamlPro, the main ongoing task on the OCaml Compiler is to improve the high-level optimisation. This is something that we have been doing for quite some time now. Indeed, we are the authors behind the Flambda optimisation pass and today we would like to introduce the series of blog snippets showcasing the direct successor to it, the creatively named Flambda2.

This series of blog posts will cover everything about Flambda2, a new optimising backend for the OCaml native compiler. This introductory episode will provide you with some context and history about Flambda2 but also about its predecessor Flambda and, of course, the OCaml compiler!

This work may be considered as a completement to an on-going documentation effort at OCamlPro as well as to the many different talks we have given last year on the subject, two of which you can watch online: OCaml Workshop ( slideshow ), ML Workshop ( slideshow ).

This work was developed in collaboration with, and funded by Jane Street. Warm thanks to Mark Shinwell for shepherding the Flambda project and to Ron Minsky for his support.

Compiling OCaml

The compiling of OCaml is done through a multitude of passes (see simplified representation below), and the bulk of high-level optimisations happens between the Lambda IR (Intermediate Representation) and CMM (which stands for C--). This set of optimisations will be the main focus of this series of snippets.

The different passes of the OCaml compilers, from sources to executable code, before the addition of <code>Flambda</code>.

The different passes of the OCaml compilers, from sources to executable code, before the addition of Flambda.

Indeed, that part of the compiler is quite crowded. Originally, after the frontend has type-checked the sources, the Closure pass was in charge of transforming the Lambda IR (see source code) into the Clambda IR (see source code). This transformation handles Constant Propagation, some inlining, and some Constant Lifting (moving constant structures to static allocation). Then, a subsequent pass (called Cmmgen) transforms the Clambda IR into the CMM IR (see source code) and handles some peep-hole optimisations and unboxing. This final representation will be used by architecture-specific backends to produce assembler code.

Before we get any further into the hairy details of Flambda2 in the upcoming snippets, it is important that we address some context.

We introduced the Flambda framework which was released with OCaml 4.03. This was a success in improving inlining and related optimisations, and has been stable ever since, with very few bug reports.

We kept both Closure and Flambda alive together because some users cared a lot about the compilation speed of OCaml - Flambda is indeed a bit slower than Closure.

<code>Flambda</code> provides an alternative to the classic <code>Closure</code> transformation, with additionnal optimizations.

Flambda provides an alternative to the classic Closure transformation, with additionnal optimizations.

Now is time to introduce another choice to both Flambda and Closure: Flambda2, which is meant to eventually replace Flambda and potentially Closure as well. In fact, Janestreet has been gradually moving from Closure and Flambda to Flambda2 during the past year and has to this day no more systems relying on Closure or Flambda.

You can read more about the transition from staging to production-level workloads of Flambda2 right here.

Flambda is still maintained and will be for the forseeable future. However, we have noticed some limitations that prevented us from doing some kinds of optimisations and on which we will elaborate in the following episodes of The Flambda2 Snippets series.

<code>Flambda2</code> provides a much extended alternative to Flambda, from <code>Lambda</code> IR to <code>CMM</code>.

Flambda2 provides a much extended alternative to Flambda, from Lambda IR to CMM.

One obvious difference to notice is that Flambda2 translates directly to CMM, circumventing the Clambda IR, allowing us to lift some limitations inherent to Clambda itself.

Furthermore, we experimented after releasing Flambda with the aim to incrementally improve and add new optimisations. We tried to improve its internal representation and noticed that we could gain a lot by doing so, but also that it required deeper changes and that is what led us to Flambda2.

Snippets Roadmap

This is but the zeroth snippet of the series. It aims at providing you with history and context for Flambda2.

You can expect the rest of the snippets to alternate between deep dives into the technical aspects of Flambda2, and user-facing descriptions of the new optimisations that we enable.

The F2S Series!

  • Episode 1: Foundational Design Decisions in Flambda2

    The first snippet covers the characteristics and benefits of a CPS-based internal representation for the optimisation of the OCaml language. It was already covered in part at the OCaml Workshop in 2023 and we go deeper into the subject in these blog posts.

  • Episode 2: Loopifying Tail-Recursive Functions

    Loopify is the first optimisation algorithm that we introduce in the F2S series. In this post, we breakdown the concept of transforming tail-recursive functions in the context of reducing memory allocations inside of the Flambda2 compiler. We start with giving broader context around tail-recursion and tail-recursion optimisation before diving into how this transformation is both simple and representative of the philosophy behind all the optimisations conducted by the Flambda2 compiler.

  • Episode 3: Speculative Inlining

    This article introduces Speculative Inlining, which is the name of the algorithm responsible for computing and inlining optimised function code inside of Flambda2. We cover how quickly we are faced with complex questions with only heuristic answers when it comes down to an optimal inlining choice. Speculative Inlining is also the best demonstration of how we traverse code in our compilation pipeline.

  • Episode 4: Upward and Downward Traversals

    Coming soon...

Stay tuned, and thank you for reading!



Au sujet d'OCamlPro :

OCamlPro développe des applications à haute valeur ajoutée depuis plus de 10 ans, en utilisant les langages les plus avancés, tels que OCaml et Rust, visant aussi bien rapidité de développement que robustesse, et en ciblant les domaines les plus exigeants (méthodes formelles, cybersécurité, systèmes distribués/blockchain, conception de DSLs). Fort de plus de 20 ingénieurs R&D, avec une expertise unique sur les langages de programmation, aussi bien théorique (plus de 80% de nos ingénieurs ont une thèse en informatique) que pratique (participation active au développement de plusieurs compilateurs open-source, prototypage de la blockchain Tezos, etc.), diversifiée (OCaml, Rust, Cobol, Python, Scilab, C/C++, etc.) et appliquée à de multiples domaines. Nous dispensons également des [formations sur mesure certifiées Qualiopi sur OCaml, Rust, et les méthodes formelles] (https://training.ocamlpro.com/) Pour nous contacter : contact@ocamlpro.com.