Previous discussions on why flambda IR introduced?

Learning
1

I remember when flambda was introduced, there were some discussions on why a new intermediate language was introduced instead of doing optimizations on lambda or clambda.

This is the only link I found, do we have some documents explaining why such layer is justified?

A side question, if you revisit the history, is an extra layer the right choice?

Thanks! – Hongbo

2

I’m not aware of any documents explaining why we introduced an extra layer, but the existing Lambda and Clambda languages are not well-suited to the optimisations that Flambda does.
Lambda represents functions as lambda-terms instead of closures, so it’s a pain when inlining (you have to make sure all the free variables are still in scope). Clambda is better, but is missing a good way to represent statically allocated structures.

I guess another factor is that when you want to write an optimisation, you need to make sure it’s correct even in presence of other optimisations. On Lambda in particular, this has proved very frustrating (there are lots of existing optimisations, most of them written independently, but they do interfere regularly with each other in strange ways). Writing a dedicated pass means that we are less at risk of such kind of interference.

I don’t know what the right choice is, but for Flambda 2, with our experience from Flambda 1, we decided to use yet another representation. However, unlike Flambda 1 we don’t go back to Clambda: we translate from Lambda to the new representation, then afterwards we go directly to Cmm.
Personally I would never try to write a full optimisation engine on a representation that is not made with program transformations in mind. In the native compiler, except for Flambda, only Mach (a low-level representation on which we do a number of passes including register allocation) is designed that way.

2 Likes
3

Is it publicly available somewhere? It would be interesting to see the discussions of the tradeoff between different encodings. I experimented a little bit with ANF and CPS but did not find it particularly useful compared with direct style, it might be that I missed something obvious.

4

The Flambda 2 repo (still experimental) is available at https://github.com/ocaml-flambda/flambda-backend. You can see the exact representation in middle-end/flambda2/terms/flambda.mli.