Table of contents

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

Date: 2024-03-18
Category: 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: Upward and Downward Traversals

    Coming soon...

Stay tuned, and thank you for reading!



About OCamlPro:

OCamlPro is a R&D lab founded in 2011, with the mission to help industrial users benefit from experts with a state-of-the-art knowledge of programming languages theory and practice.

  • We provide audit, support, custom developer tools and training for both the most modern languages, such as Rust, Wasm and OCaml, and for legacy languages, such as COBOL or even home-made domain-specific languages;
  • We design, create and implement software with great added-value for our clients. High complexity is not a problem for our PhD-level experts. For example, we helped the French Income Tax Administration re-adapt and improve their internally kept M language, we designed a DSL to model and express revenue streams in the Cinema Industry, codename Niagara, and we also developed the prototype of the Tezos proof-of-stake blockchain from 2014 to 2018.
  • We have a long history of creating open-source projects, such as the Opam package manager, the LearnOCaml web platform, and contributing to other ones, such as the Flambda optimizing compiler, or the GnuCOBOL compiler.
  • We are also experts of Formal Methods, developing tools such as our SMT Solver Alt-Ergo (check our Alt-Ergo Users' Club) and using them to prove safety or security properties of programs.

Please reach out, we'll be delighted to discuss your challenges: contact@ocamlpro.com or book a quick discussion.