Constructing a compiler

There is a lot of tutorials out there on how to write a simple interpreter or a compiler. There is most certainly no need in just another one of this kind. This tutorial is the opposite, it tells how to write a complex compiler with all the bells and whistles, while still leaving the unimportant details out and keeping things easy to understand.

As a source language we're using a very simple, somewhat functional language. It's eager, expression--oriented, no explicit destructive assignment to variables, functions may have I/O and memory side effects (using some impure intrinsics). No explicit looping constructs besides recursion, tail recursion optimisation is guaranteed by the compiler.

We build a compiler on top of this simple language, and then extend the core language with more features added as syntax extensions and compile-time macros, demonstrating a number of different important approaches used together.

There is no intention to write just another one short and dense compiler. We're fully embracing the nanopass-style of compiler construction, therefore code is deliberately verbose, but on the other hand, every step made in the compilation pipeline is easy to understand and easy to reason about.

This compiler takes its eager functional source language and reduces it to an imperative low level intermediate representation, so both functional and imperative compilation techniques are covered here, with more emphasis on the imperative side (e.g., we do not go the CPS way, using an SSA representation instead).

Naming languages is hard and does not make much sense, so we'll simply call our source language lang0, with all the consequent IR names derived from this notation.

Topics covered in this tutorial include (but not limited to):

• ASTs
• Parsing
• Macro expansion
• Syntax sugar elimination
• Lexical scope handling
• Lambda lifting
• Tail calls handling, tail recursion optimisation
• Converting an expression-oriented language to statements + expressions
• Producing a flat SSA IR
• Converting to the abstract SSA IR and back

This is also a showcase for a range of new MBase features - recform ASTs support, abstract SSA library, AST pretty printing, etc.

Initial AST

Language starts with a definition of its Abstract Syntax Tree. This is the very first AST in our compilation chain, it is generated by the parser frontend directly and contains some syntax sugar that ought to be eliminated straight away.

Since this is a "functional" (sort of) language, everything is an expression. We will split statements and expressions further down the compilation pipeline.

Very often we will have to define a new AST which is only slighly different from another one. It does not make sense to copy-paste the same thing over and over again. Instead, new ASTs should be rewritten from the existing ones. The language after macro expansion will be the following:

Parser

As we have defined the structure of this language, we can start building a parser for it.

Parsers in PFront are based on an extended PEG. Normally, a new language parser will inherit one of the existing parsers, to avoid defining common stuff like whitespace, comments, identifiers, number and string literals and so on. In this case we're inheriting PFront language entirely, though only use few primitive nodes from it.

Let's not dwell on it, ok? Far too many compiler tutorials are stuck on parsing, and parsing is the least important part of a language implementation.

An example of a language accepted by this parser would look like this:

We will use this foldl function to illustrate the compilation pipeline.

There is nothing interesting to see there yet. Leaving it here just for a reference - this function straight after parsing:

Macro expansion

Logically, this is the next step straight after parsing. Though, it is a relatively advanced subject that probably should be skipped at first, straight to the syntax sugar lowering. Feel free to come back and review this section after reading about the runtime-compiler feedback loop. At this moment we don't have any feedback loop, it can only be defined later, when the rest of the compiler pipeline is finalised. We'll leave an empty stub here meanwhile.

Unfortunately, macros imply a very eary exposure to the concept of environment, which, again, we'd prefer to leave for much later down the pipeline. We'll keep a dummy stub here instead.

In order to be able to implement macros we need an access to AST constructing functions. The easiest way of abstracting them out nicely is to use quasiquotation: any AST inside the quasiquotation is translated into an AST-constructing code that calls the appropriate runtime library functions.

Expression expansion pass includes handling the quasiquote nodes (consider quasiquote a special kind of a "macro") and user-defined macros applied via the compiler feedback loop.

Cleanup

Now all the quasiquotations, macro applications and top lift nodes are eliminated and we can turn our AST into a form suitable for the rest of the compiler pipeline.

For the compiler pipeline demo purposes we need a dummy environment:

Lowering

Our first AST is designed for parsing, but it is not very useful for any further analysis, optimisations and a code generation. Before we start actually compiling anything we have to eliminate some syntax sugar and make this AST simpler.

Eliminating syntax sugar

The two argument application node was only introduced to simplify binary expressions parsing and must go.

This is our first introduction to visitors - a fundamental building block in PFront. Visitor walks over an AST in a defined order and builds a new AST, transforming certain nodes with given expressions. In this case we only rewrite apply2 variant of an expr node, with all the boilerplate covering all possible paths to expr nodes being inferred automatically.

Variant constructors like mk:apply are context-dependent, in this visitor we know that the resulting AST is the same as the original AST, so it constructs lang0:expr:apply variants.

This function takes a list of toplevel statements as an argument, and returns a list of transformed toplevel statements.

A two-armed if does not make sense in an expression--based language and it must go. An implicit false branch returns a nil constant.

And a list constructor is just a sequence of nested cons applications. We do not care if it's entirely constant at this stage, all the optimisations can be done at a later stage.

And everything together now:

Lexical scope

This is a lexically scoped language, allowing new definitions to override an outer scope. This is a default design decision for languages with pattern matching, for example. Our core language does not have any pattern matching support, but it can be added later with macros and syntax extensions.

The simplest approach to lexical scope implementation is to just rename all the variables to make them unique. In a consequent pass we'll collect variable and argument declarations and sort everything into categories - global variables, local variables and lambda arguments. Another category to appear later (after a lambda lifting pass) is a closure variable.

It would be nice to keep a track of all the renames we did, it could help with producing debug information and with giving error messages more context.

Now it's time to stop using the initial AST and move on. We eliminated few variants, and are going to introduce more specific variable variants: global, local, argument or a closure variable. We're also introducing variants for a consequent lambda lifting.

The new AST is derived from the previous one (lang0), with few modifications made to the expr node.

Now we can make our variables more specific, and since all the names are unique now we can do it easily in a depth--first order. Of course we could do it in the previous pass, but it's better to keep passes as simple as possible.

Lambda lifting

Lambda lifting pass will turn all the nested lambda functions into toplevel definitions, capturing closure environments where necessary. We did the lexical scoping pass previously, and now all the names inside any given context are unique, which makes it easy to produce lists of externally defined variables used under each lambda context.

First we have to propagate the free variables lists (with bound variables already collected in the lexical scoping pass), from top to bottom.

Now we can use an intersection between a bound variables list and a free variable list to form a closure environment.

Obviously we do not need to lift lambda expressions that are already on top, so we have to make an exception for this case.

Lambda--lifting a single top level statement may produce any number of new top level statements, so we'll just collect all the new statements together into one flat list.

And now, all the lexical scope and lambda lifting passes together:

Preparing for a code generation

By now we moved all the lambdas into top level definitions, made closure environments explicit, eliminated lexical scope and reduced some syntax sugar.

Let's refine our AST further. We can classify top level statements as functions (i.e., lambdas with an empty closure environment), closures, constants, evaluated definitions and, finally, toplevel expressions.

We also eliminated the temporary elambda variant previously, and are going to get rid of nested let bindings and replace them with flat imperative assignments. Same AST is introducing a special tail call variant.

Another variant introduced here is splitexpr, it is required for separating expressions and statements further down the pipeline.

Removing toplevel lambdas

Flattening bindings

Instead of our nice and clean functional variable binding we'll produce an imperative sequence of destructive assignments here. Some other passes will also introduce true destructive assignments, e.g., lifting the statement expressions and optimising direct tail recursion, so we're not losing any purity here. A consequent SSA transform will make our IR clean again.

Redundant nested seq

There is no reason for doing this besides pure aesthetics. If you want to dump IR somewhere in the middle, deeply nested seq may be quite annoying.

Marking tail calls

At this stage, IR is suitable for the tail call analysis, which could have been more difficult previously and will be more clumsy later. Results of this marking will be used further down in a direct tail recursion optimisation and are required for the statement vs. expression split, since we're also introducing explicit return statements here.

Statement expressions

A procedure very similar to tail call marking, but for the statement expressions (like if and seq yielding value that is used inside another expression). We'll need it later on when we actually split statements and expressions.

The following function, just like a tail call marker pass before, will follow the returning branches of expressions only --- i.e., last entry in a sequence and both arms of an if, but instead of inserting a return or a tail call marker it will assign that value to a variable or wrap it into a drop marker, meaning that the result is going to be discarded anyway.

The next function is identifying statement--expressions and treats them in a special way: any value returned from the non--terminal sequence elements is dropped, and any value of a complex statement--expression that is actually used is assigned to a variable, and a special splitexpr variant is created, holding both the statement that generates the value and an expression to access this value. After the split between statements and expressions is completed those inner statements will be lifted to their nearest statement scopes.

The previous function could have created some new variables, so we have to add corresponding allocas to the beginning of the outer context.

Detecting tail recursion

Some tail calls are tail recursive, and this is a right moment to replace them with a goto. The language does not have gotos and labels? Not a problem at all, we'll make a new language now:

If a function is directly tail recursive, we have to create temporary variables that will initially contain copies of the argument values and then will be used to pass arguments in a tail--recursive call. In this case all the argument references in the function body must be replaced with local variable references.

All together

At this point, the foldl function looks like this:

Code generation: an imperative IR

By now our source functional language got transformed into an imperative one, with explicitly allocated variables, destructive assignments and properly marked tail calls. Nested lambda functions and lexical scope were eliminated. There is already a clear separation between statements and expressions that occured naturally during the previous passes. Goto, seq, drop, alloca, set, if, return and tailapply are statements, while everything else is an expression.

If our target was a stack machine, it would have been possible to keep an expression-based IR all the way down. Unfortunately, stack machines are not quite fit for optimisations and analysis, and we're not going down the CPS route either.

In an SSA-based IR we have to *assign* results to named registers. Control flow statements must be habdled differently from the expressions yielding results, and for this reason we're starting this split here.

It is an important compiler construction pattern that occurs even in the languages that had distinct statements from the beginning.

We can formalise this split now. The new AST lang0k defines everything that returns a value as an expresssion and everything control flow as a statement. An if3 statement does not return anything any longer, we ensured this by assigning its return value to a variable previously, in a preparation phase.

The following pass dows not change the tree structure (besides renaming the toplevel expr to eval), it merely sorts out the variants into their new nodes.

After this pass we still have that splitexpr thing in our IR, and it would be nice to flatten it before we go any further.

Flat IR

With a clean and simple low level imperative IR we can now turn to all the different set of compiler construction tools. First we'll lower this IR into an SSA form and apply all the standard SSA-based torture techniques to it.

The first step in flattening will produce almost the same IR, with all the complex expressions broken down to register assignments. We could have used local variable assignments here, but since we're going into an SSA soon anyway it does not matter if "registers" are introduced a bit earlier.

Note this lock node here - it is merely an optimisation, to ensure the visitor is not going into an already flattened code.

Expresison flattening

Getting ready to descend to SSA. This involves adding explicit load and store instructions for the local stack--allocated variables, so we'll lift local references alongside with compound expressions here.

The lock nodes introduced were temporary and must be eliminated now:

Statement flattening

Now we can get rid of the compound statements, replacing them with a goto and labels. At the moment we only have one kind of a compound statement - an if.

The previous passes could produce nested seq blocks. Since this is the only compound statement left by now we can just flatten everything into a single topmost sequence.

And our sample foldl function looks like this after flattening:

Basic blocks

Now everything is perfectly flat, so we can sort instructions into basic blocks. Also it's a right moment to do another node split - separate compound expressions and leaf values, it will help to enforce the SSA guarantee of not reassigning simple values (with the only exception of the $\varphi$ nodes, but this will be sorted out later).

Note that tailapply is gone now as it served its purpose already, replaced with an expr node - it will be useful later when we have to annotate calls.

This will be our main IR quite for a while now.

First pass over a flat code is to eliminate redundancy: e.g., if there is a sequence of labels, only one should remain (and be referred to), because a basic block can only have one name. If a terminal instruction is following another terminal instruction, it is unreachable and must be eliminated.

Once this filtering is done, rules for accumulating instructions into basic blocks are much simpler.

The code after basic blocks extraction and before the generic SSA transform is following:

Generic SSA

Now we're all set for an SSA--transform (i.e., memory to register). For this we'll use a specific simplified IR, not to be confused with a more complex Abstract SSA we'll use later.

Back from the generic SSA

After the generic SSA transform, we have all allocas, loads and stores eliminated, new phi nodes introduced and equivalent registers renamed. Now we have to apply the results back to our original AST.

And a simple wrapper function to run the generic SSA transform over top level entries:

Everything to this point

Now, back from the generic SSA, our foldl function looks like this:

And a control flow graph for this example is following:

Abstract SSA

The next few sections are entirely optional. We already have an IR suitable for code generation, but also fit for SSA-based optimisations. MBase provides an abstract SSA library which, with a help of a user--defined IR model, provide, among others, the following transforms:

• Constant folding
• ADCE
• CFG simplification
• Loop analysis
• Loop invariant motion
• Loop unrolling
• Common subexpression elimination

For the implementation details see ssa-fold.pdf.

Some of these optimisations are enabling and may be useful for our code generation even if the target platform is capable of doing the similar optimisations on a lower level.

Keep in mind that Abstract SSA is an old, list--form AST, and by converting our nice recform AST into it we're discarding any associated metadata (most importantly, source code locations). Also, some semantics is lost and must be recovered on a way back (e.g., both arguments and closure variables are represented as registers).

We did not have any select instructions before, but they may appear after the Abstract SSA optimisations. Backend must be aware of this.

Model

Abstract SSA implementation is IR-agnostic and therefore must be provided with some hints about the nature of this particular IR. We have to be able to tell pure intrinsics from those that might have some side effects in order to get the constant folding working. We have to provide a way to evaluate those intrinsics when all of their arguments are constant. We must tell how to create a boolean constant and how to tell if a constant is a boolean truth. All such things are forming a model which compliments abstract SSA passes.

Optimisations

Back from the abstract SSA

Feedback codegen backend

Since this language allows compile time macros, we need two different backends - one for emiting the final code, and another for interpreting the code that might be used by the macros. For the latter we'll implement a primitive .net backend. Partly because it's an opportunity to showcase a few patterns in compiling an SSA IR into a stack-based target. It will consist of the following steps:

• Out of SSA: we'll simply eliminate all the phi nodes and replace them with loads and stores placed accordingly.
• Back to trees: collapse the register assignment sequences into expression trees where possible without affecting the effect order.
• Register elimination: all the register assignments left after the previous pass must now be converted into local variables (with explicit loads and stores).
• Stack machine codegen.

One might ask, why did we go through all those complex rewrite steps to get back to the expression trees again? Firstly, the expression trees are a bit different now - they do not contain any control flow inside, it's broken into basic blocks already. Secondly, we had an opportunity to do all the SSA-based stuff which is not possible on a primitive expression tree based IR. And, also, it is a bit ironic, but we're doing a redundant work here by making our IR stack-friendly - the .net engine will quickly turn it back into SSA again at a first opportunity.

Out of SSA

The only cases where a registers are set to load(something) are from the previous pass here, and it is safe to demote all such loads to values.

Back to trees

.NET target is a stack machine, so it makes sense to fold the sequential single use register assignments back into expression trees.

No more registers

Just a nominal pass by now - just demote the remaining registers to loads/stores and issue explicit allocas for them.

Environment

We managed to keep the compiler clean and self-contained up until now, but for a real backend we have to deal with a runtime library and a global environment, so this final pass will have to keep looking things up and keeping a track of classes, fields and methods it generated. Environment contains references to some core library methods (e.g., a select function), FFI methods, the already compiled classes and methods and, in another layer, fields and methods in the class that is being compiled now.

.NET codegen

The general approach is simple - for every chunk of code (a number of definitions) a class is created. Constants are stored in static fields, all functions are turned into static methods. A special 'init' method is generated to fill all the static fields. We're not using static constructors here, because some side effect actions of this init method may not touch any of this class static fields, but affect the other global variables instead, so we have to ensure the initialisation order explicitly.

Driver

Top level driver

Bringing all the passes together here: