Fang: A compiler for Tiger
Version 1.3.0

The field of compilers is enormous, so it's important to clearly define the scope of the project.

Appel's book is divided into two parts. The first guides the reader through the major parts of the compiler from start-to-finish. The second part discusses "advanced" techniques such as garbage collection, implementing functional programming languages, and optimizing for the memory hierarchy.

Fang focuses on the first part. In general, the goal is to do less but do it well. More specifically, I'd like Fang to:

• Generate correct assembly for all valid Tiger programs
• Be easy to use (eg., by showing clear and descriptive errors) and hard to misuse
• Offer insight into the stages of compilation
• Be structured, tested, and documented such that it can be modified with confidence

Some non-goals of Fang are to:

• Produce the fastest or cleanest possible assembly
• To explore advanced techniques in compiler design (I'd rather do so with a more interesting language than Tiger)
• To support a full-fledged programming language

fangc reads a Tiger program from the standard input device and, by default, writes x86 assembly directly to the standard output device.

For example,

$ echo 'let var x := 10 in x + 1 end' | fangc
    .intel_syntax noprefix
    .global fang

fang:
    mov rax, 10
    add rax, 1
    ret

(I encourage readers to try this on a terminal that supports colors, because fangc writes pretty coloured output!)

One goal of fangc is to make it easy to observe different stages of the compilation process. The --emit=FORMAT (or -e FORMAT for short) option writes output in an intermediate format instead of continuing to compile to assembly.

Any unambiguous prefix of the format name can be used.

For example,

$ echo 'let var x := 10 in x + 1 end' | fangc -e can
(frame fang no-fp (perform (move #16 10) (+ #16 1)))

By default, all compiled Tiger programs are safe. That is, unless Fang can statically infer that it's unnecessary, all accesses to record variables are checked for nil and all array indices are bounds-checked. If you'd like to live dangerously, you can eliminate these checks with the --unsafe (or -u) option. The resulting assembly is cleaner and programs may run marginally faster.

Compiling a Tiger program is only the first step. Fang also includes a run-time library for functionality like memory allocation. Since the details of compiling this library and linking it with the assembly emitted by fangc can vary greatly from system to system, Fang delegates this to CMake with a tool called fangu.

fangu automates the creation of a CMake project which compiles both the run-time library from its source and the Tiger program. The advantage of this approach is that both the assembly file and the run-time library can be compiled with arbitrary compiler and linker options.

Unlike fangc, fangu reads from a named file:

$ echo 'let var x := 10 in print_int(x + 1); print_line() end' > foo.tig
$ fangu foo.tig
$ _fangbuild/foo
11

fangu can also execute the resulting program directly:

$ fangu foo.tig -x
11

For example, this invocation of fangu compiles Tiger in unsafe-mode and adds debugging symbols to the run-time library:

$ fangu --tiger-compile-options=-u --c-compile-options=-g3 foo.tig -x
11

I first learned of the "tagless-final" style from this wonderful post on the OCaml discussion forum. Oleg Kiselyov writes about it in much depth on his website.

Intrigued, I structured the representation of both Tiger and the IR this way. I wanted to explore the impact of doing so on the rest of the implementation of the compiler, though I didn't know what to expect. If I've understood correctly, the result is interesting.

Instead of defining an abstract syntax tree for Tiger, Fang defines the "algebra" of the Tiger language as a module signature. A module which implements this signature is said to be an "interpreter" of this algebra.

For example, given the module Fang_Tiger.Pretty which implements the module signature TIGER, executing

let expr = Fang_tiger.Pretty.(scope [var "x" (int 10L)] (value (name "x")))

means that the value expr is a pretty-printer for precisely the Tiger expression that we constructed.

(Note, real code would need to include source locations for each of those elements.)

We can format to stdout:

Fmt.pr "%a@." Fang_tiger.Pretty.pp expr

producing the output "let var x := 10 in x end".

The important observation here is that there is no in-memory representation of the entire Tiger expression: just whatever state is necessary to implement a pretty-printer for it.

A common pattern in Fang is to define an interpreter that "forwards" its result to another interpreter. For example, the functor Validation (L : TIGER) is an interpreter which validates a Tiger expression "into" the interpreter L in addition to producing a "validator".

In this way, we can compose a pipeline of compiler stages however we wish.

Let's work backwards. (These functors are close approximations to real ones in Fang's implementation.)

The last step is to pretty-print the IR:

module M0 = Fang_ir.Pretty

Before that, we want to canonicalize it:

module M1 = Fang_ir.Canonical (M0)

Before that, we want to translate it from Tiger:

module M2 = Translate (M1)

Before that, we want to statically analyze the Tiger expression:

module M3 = Analyze (M2)

Before that, we want to validate that the Tiger expression type-checks:

module M4 = Validation (M3)

Before that, we want to parse Tiger from text:

module M5 = Parsing (M4)

The OCaml values that we get from M5.parse encode the entire process of pretty-printing canonical IR from Tiger source code, and without materializing an in-memory AST of either the Tiger or IR program.

This has many parallels to structuring code in continuation-passing style (CPS).

Tiger is parsed via the Menhir parser-generator.

Menhir supports generating a functor instead of just a module, which is what makes it possible to integrate parsing into the compiler pipeline without building an in-memory AST. Neat!

The advantage of using a parser-generator is knowing that the grammar is well-formed and that every case has been accounted for.

Alternatives, like a recursive-descent parser (either hand-made or constructed via combinators), would result in better error messages at the expense of confidence in the grammar.

Menhir supports tools for producing good error messages, but that's (possibly) work for a future version of Fang.

Fang performs some rudimentary static analysis on Tiger programs. This permits some interesting optimizations to be applied.

Instead of the IR-rewriting code Appel demonstrates in his book, I adopted the framework for optimizing DSLs in the tagless-style by Kiselyov.

The main advantages are that the optimizations are type-preserving (that is, I can be sure that all rewritten IR type-checks) and that it fits into the compiler "pipeline" as described earlier.

For simplicity, Appel uses lists to represent flow-graphs, but I found the code for manipulating graphs to be error-prone.

A paper by Ramsey and Dias describes an encoding of flow-graphs using a neat technique for navigating immutable data structures called "zippers". Their encoding ensures that invariants about the structure of the graph are maintained automatically, even as the graph is constructed piece-by-piece.

The authors also show how backwards and forwards analysis on such graphs can be written generically.

Fang adopts the implementation described in the paper, including an implementation of the generic analysis framework: it's specialized to calculate liveness information.

There are two complications to register allocation.

The first is how to deal with "spills": a situation in which no processor registers are available to assign to a temporary storage location.

The second is the problem of redundant move-instructions. For example, if a flow-graph consists of these instructions

mov #1, 10
mov #2, #1

then it may be possible to coalesce #1 and #2 so that the move from #1 to #2 is unnecessary and can be eliminated.

In his book, Appel summarizes a previously-published paper on a register-allocation algorithm called "iterated register coalescing".

The more simple version of the algorithm neither handles spills nor coalescing: they're marked as "advanced" exercises in the text. Fang's implementation handles both, which means most redundant move-instructions are eliminated in the assembly it emits and there is no limit on the number of local variables in a Tiger program.

Register allocators for compilers targeting x86-64 can be complex because its registers are segmented: rax is the 64 bit register and eax is the 32 bit one, for example. This is not an issue in Fang because all values are 64 bit.

For simplicity, Fang does not implement a garbage collector (GC).

Instead, a large buffer is allocated (32 MiB as of this writing) the first time a request to allocate memory is made.

A request for N B of memory advances a pointer into the buffer by N, so allocation is fast.

Of course, the program aborts once memory is exhausted. No attempt is made to reclaim memory.

There are many components in Fang that interact in complex ways. Fang's tests are most useful because they make the impact of changes very clear: that is, they permit Fang to be modified with confidence.

In addition to the usual unit and integration tests, two notable kinds of tests in Fang are:

• End-to-end: In these tests, a Tiger program is compiled and executed. Both the assembly produced and the result of executing the program are saved for reference. When something changes, it's compared against the reference versions with the diff utility.
• Distribution: These tests validate processes related to Fang's distribution: that a package can be built, that installed versions of executables can produce output, etc.

Fang makes use of tools that make "expectation tests" easy to write.