Henceforth - SSA compiler for an imperative stack-based language

Overview

After working on the Henceforth compiler on and off for about a year, my friend João Novo and I have organized our work and released a v1.0.

Henceforth is a stack-based language where stack effects and types are verified at compile time rather than relying on runtime features, which are commonly present in stack-based languages in order to resolve some challenges¹¹In Forth, for example, a loop can change the depth of the stack however it wants, so the stack depth depends on the trip count. If you allowed that in a compiled language, you wouldn’t know how many elements to return from a function! that arise with the paradigm. A code example would look something like this:

fn pow: (/* base */ i32 /* exp */ i32) -> (i32) {
    let exp: i32;  &= exp;   // `&=` pops the top of the stack, so the
    let base: i32; &= base;  // last argument binds first

    let i: i32; @(0) &= i;   // `@( ... )` is a stack expression, in postfix

    @(1)  // begin accumulating the result on the stack
    while @(i exp !=) {
        @(base *)       // consume the accumulator, multiply, push it back
        @(i 1 +) &= i;  // i += 1
    }
    // the accumulator is still sitting on the stack, and whatever
    // the body leaves behind is the return value
}

// called like:
@(2 10) &> pow;

fn pow: (i32 i32) -> (i32) {
    let i: i32; @(0) &= i; 
    @(1 @rrot)
    while @(@dup i !=) {
        @(@rrot @dup @rot *)
        @(@rrot @swap)
        @(i 1 +) &= i;
    }
    @pop @pop
}

To showcase the language used in practice, we have also implemented Tetris, which you can find in the testsuite:

Project goals

With these examples, people familiar with other stack-based languages will notice a strong presence of imperative elements here that is largely uncommon in other languages with this paradigm. There are a couple of reasons for that:

First, stack languages usually ask you to adopt the paradigm all at once, largely without compromising with other common paradigms, and that makes it difficult to introduce a large number of people that come from either imperative or functional languages. Secondly, these people tend to find stack languages difficult to read and too implicit.

From that, we decided to make a language that bridges the gap between an imperative language (such as C) and something like Forth. The language allows people to experiment with the main features of a stack language (such as explicit data flow, multiple returns, values that don’t need names) as first class features that come in a familiar format.

Personally, another goal I had for the project this time around was to try to write a scalable and modular compiler,²²While implementing this compiler I went through literature like Cooper & Torczon’s Engineering a Compiler, as I wanted it to be a more informed and structured project than last time. rather than solely focusing on language features. This meant simplifying the frontend language in some places and leaving interesting features for later releases in order to actually complete an initial minimal version (which still took a year!).

In my previous compiler, I had to redo some sections many times as I discovered the challenges and needs of each part of the compiler (such as semantic analysis, lowering to a CFG, etc). The codebase itself also made a lot of assumptions about what previous phases of the compiler did during a pass, and that meant that returning to it after a few months was very difficult, as a lot of these assumptions weren’t explicit or enforced.

Why Cranelift instead of LLVM

While the project provides an interpreter (mainly for testing purposes), Henceforth primarily targets an AOT Cranelift backend.

Unlike last time, I chose not to use LLVM as a target. First of all, Henceforth is written in Rust, and we were interested in using a Rust-native backend. Secondly, we wanted a minimal dependency that could support various different targets, and wanted the project to remain small where possible. Additionally, Henceforth implements its own optimizing SSA middle end, so we would have turned off most of LLVM’s optimizations anyway.

Cranelift acts as a convenient way to allow us to compile to multiple targets while still letting Henceforth implement its own middle end optimizations on top of it. In the future it would be nice to get rid of Cranelift as a dependency as well, but that would require a lot more time and work.

The language

Those interested in knowing more about the language in detail can check out the Language Reference & Getting Started Guide. Henceforth supports move & vs copy : operators from the stack on assignments and function calls. These decide if a value on the stack should be copied or popped. It is the main mechanism to interact between the imperative and the stack-based side of the language, and pass along values.

let a: i32; @(10) &= a;  // this pops `10` from the stack 
let c: i32; @(a)  := c;  // stack value is copied, the stack still has the value
let b: i32;       &= b;  //  we pop `a` from the stack (which is now empty)

Function parameters specify how much of the stack of the caller we can access when calling it. The return type specifies the state the stack has to be in after the function returns.

fn divmod: (i32 i32) -> (i32 i32) {
    let d: i32; &= d;
    let n: i32; &= n;
    @(n d /)  // quotient
    @(n d %)  // remainder
}

fn main: () -> () {
    @(17 5) &> divmod;
    let rem: i32;  &= rem;  // top of the stack binds first
    let quot: i32; &= quot;
}

The following example doesn’t compile: Henceforth has a lot of logic to verify at compile time that all control flow constructs agree on what the types and length of the stack is on all paths, and it also checks that paths that return match the function signature.

fn f: (bool bool bool) -> (i32) {
    let cond1: bool; &= cond1;
    let cond2: bool; &= cond2;
    let cond3: bool; &= cond3;
    if @(cond1) {
        @(1)
    } else if @(cond2) {
        if @(cond3) {
            @(1.5)    // leaves the wrong type, so it is invalid
            return;   // the return keyword lets functions end early
        }
        @(1)
    } else {
        @(1 2)  // leaves one value too many
    }
}

Output:

error: in f: (bool, bool, bool) -> (i32): expected i32 on stack for return, found f32
  --> tests/compile_tests/f.hfs:10:13
   |
10 |             return;   // the return keyword lets functions end early
   |             ^^^^^^
   |
error: in f: (bool, bool, bool) -> (i32): expected a stack depth of 1, found a stack depth of 2
  --> tests/compile_tests/f.hfs:14:9
   |
14 |         @(1 2)  // leaves one value too many
   |         ^^^^^^
   |

Various stack keywords exist in the language to allow for stack introspection:

@(1 2 3)
@dup      // 1 2 3 3
@depth    // 1 2 3 3 4

Arrays are supported as well:

fn sum: ([]i32 i32) -> (i32) {
    let n: i32; &= n;
    let arr: [n]i32; &= arr;
    let i: i32; @(0) &= i;
    @(0)  // the running total, unnamed
    while @(i n !=) {
        @(arr i [] +)  // reads arr[i] and adds it to the total
        @(i 1 +) &= i;
    }
}

fn main: () -> () {
    let arr: [5]i32;
    @([0 1 2 3 4]) &= arr;  // create an array literal on the stack
    @(arr 5) &> sum &> print;
}

Semantically, putting values on the @(...) stack will always result in “copying” them onto the stack, so no aliasing ever happens. Internally, nothing is ever actually lowered to stack push and pop operations, so if stack values aren’t used they aren’t lowered to anything (this is explained in the lowering section).

Henceforth also supports runtime-sized locals, and supports writing []i32 in functions so you don’t have to specify the size of an array in a function like bubble_sort (the array size is passed on the 2nd argument).

fn bubble_sort: ([]i32 i32) -> ([]i32) {
    let N: i32; &= N;
    let arr: [N]i32; &= arr;

    let i: i32; @(0) &= i;
    while @(i N !=) {
        let j: i32; @(0) &= j;
        while @(j N 1 - i - !=) {
            if @(arr j [] arr j 1 + [] >) {
                let tmp: i32; @(arr j []) &= tmp;
                @(arr j 1 + [] j) [&]= arr;
                @(tmp j 1 +)      [&]= arr;
            }
            @(j 1 +) &= j;
        }
        @(i 1 +) &= i;
    }
    @(arr)
}

Frontend

The recursive descent parser is actually quite simple compared to many other languages. One main reason for this is that the parser doesn’t need to deal with any operator precedence, since that isn’t present in stack-based languages like Henceforth.

Most of the frontend work went into the stack analyzer pass, which simulates the stack at compile time and reconstructs the AST as an “imperative” language’s AST from the stack semantics. This is the core idea that makes it so most stack operations don’t really emit any codegen. The other half of stack simulation involves keeping track of the depth and types of each control flow branch, as shown in this earlier example.

The next section showcases how the IR lowerer pass takes our AST from the previous pass and runs another round of stack simulation, in order to output SSA IR that is agnostic to any stack related semantics.

We decided to run stack simulation twice because we assumed we wouldn’t have to do much work on the second pass, but in practice we ended up with 2 copies of the same stack simulation that would often go out of sync. A better solution would’ve been to annotate the AST with the computed information so that later passes could use it. This would’ve also improved error reporting and other parts of the frontend as well.

Lowering to a CFG and SSA IR

In practice, Henceforth never does any “push” and “pop” from any real stack, all of these operations are interpreted at compile time. For example:

let foo: i32;
let bar: i32;
@(3 4 *) := foo; // copies the top of the stack into foo
&= bar; // pops the stack and reads the values

Would emit this IR: Note that the frontend emits memory-form IR with alloca/store pairs and Mem2Reg promotes it later, similarly to what LLVM does.

start_1:
  %0 = i32 1
  %1 = i32 alloca %0 // let foo: i32;
  %2 = i32 1
  %3 = i32 alloca %2 // let bar: i32;
  %4 = i32 3
  %5 = i32 4
  %6 = i32 %4 * %5
  store %6, %1
  store %6, %3

The compiler simulates the stack in order to associate each usage of a stack value to its user, which is why the IR doesn’t have to emit any stack operations, all uses are solved during lowering. Naturally, this is a lot cheaper at runtime than if we naively lowered them to actual operations with the stack pointer.

Note that, since the first := foo is a copy, the next &= bar statement will use the same result computed for foo without applying any optimizations.

Additionally, if we did:

@(3 4 5) @pop @pop @pop

The @pop doesn’t exist by the time we emit the IR, since the stack has already been interpreted. The frontend will emit these constants (before DCE is ran):

start_1:
  %0 = i32 3
  %1 = i32 4
  %2 = i32 5

Stack operations like @rot, @pop, @swap and others are frontend constructs that exist purely in the compiler, and there is no real concept of a stack by the time we have interpreted them and are emitting our SSA IR.

Optimizations and middle end work

Henceforth implements its own optimizer on top of the SSA IR generated by the frontend. The optimizer uses various constructs implemented by the analysis part of the middle end, such as def-use chains with RAUW, a dominator tree, dominance frontiers, RPO/postorder traversal, and LoopInfo construction, which are built once per function and then reused across passes.

It is relevant to note that the middle end isn’t really tied to the frontend language. Since it doesn’t assume any stack semantics when targeted by a frontend, it works as its own standalone project, and could be used for other frontends in the future.

Mutable IR and def-use chains in Rust

In Rust, it is usually quite awkward to work with mutable graph data structures, although this is what you end up wanting for an IR where instructions reference each other, the CFG has cycles, and passes delete things that other nodes still point to.

Henceforth avoids most of this by storing everything in arenas and referring to nodes by id, so nothing ever holds a reference to anything else. Since ids are Copy, analyses like def-use chains or the dominator tree are just side tables keyed by ids.

The AST’s arena just uses Vec because it never needs to delete anything, however the IR arena uses SlotMap instead, since passes delete instructions and blocks. It looks something like this:

pub struct IrArena {
    pub functions: SlotMap<IrFuncId, IrFunction>,
    pub blocks: SlotMap<BlockId, BasicBlock>,
    pub instructions: SlotMap<InstId, Instruction>,
    pub terminators: SlotMap<TermInstId, TerminatorInst>,
    // ...
}

SlotMap keys carry a generation counter, so an id for a deleted instruction fails the lookup rather than pointing at whatever reused that slot. This lets passes like Mem2Reg delete instructions as they go and clean up later without worrying about stale ids.

The main disadvantage of using ids instead of references is that you need to constantly call various getter methods to obtain the actual data, and it makes pattern matching a little less ergonomic. The tradeoff is still worth it, as it just requires more boilerplate at each call site and in each arena.

Implemented optimizations

Currently, the middle end implements DeadCodeElimination, CleanCFG and Mem2Reg. The effect these optimizations have on generated IR is showcased in the following example, which is output by Henceforth with the --emit-cfg-dot flag:

fn factorial: (i32) -> (i32) {
    let n: i32; &= n;
    let result: i32;
    @(1) &= result;
    while @(n 1 >) {
        @(result n *) &= result;
        @(n 1 -) &= n;
    }
    @(result);
}

fn main: () -> () {
    @(5) &> factorial;
    if @(@dup 120 ==) {
        @("factorial\n") &> print
    }
    @pop
}

After optimizations:

Dominators are computed with Cooper, Harvey, and Kennedy’s iterative algorithm, and dominance frontiers are derived from the resulting idom tree.

Mem2Reg implements Cytron et al.’s SSA construction, inserting phis at the iterated dominance frontier of each promotable alloca’s stores and renaming in a single dominator tree walk.

CleanCFG complements DCE quite well, since it gets to do more work if it is run after it. This pass deletes empty blocks, merges blocks with a single predecessor, and hoists branches through empty targets.

Infrastructure for testing the compiler

Henceforth comes with hfscheck, which is a small test framework like LLVM’s FileCheck or DejaGNU. You write a .hfs or .hfsir program and annotate it with //? CHECK directives, then the runner asserts those patterns show up (or don’t) in the compiler’s output.

Pattern-based checks are a good way to add coverage to a language implementation and to optimizations and avoid having tests break from unrelated changes, since they assert on the shape of the test and what it is about rather than match exact outputs. It was also something we could implement in the scope of the project, so we decided to make hfscheck.

One important use case is optimization tests. A test can start from lowered IR using an .hfsir file, so a pass can be checked in isolation without depending on what the frontend happens to lower a given .hfs program to:

//? OPT -O0 -iterative
fn fizz_buzz: (i32) -> (str) {
    ...
}
//? CHECK FN "fizz_buzz"
//? CHECK BLOCK "start_2"
//? CHECK NOT "alloca"

For example, CHECK NOT asserts something is gone after a pass runs (such as no leftover alloca after Mem2Reg), and CHECK COUNT n asserts an exact number of occurrences exist. Together they let a test assert the shape of the output, which allows for better coverage of what a pass actually does.

Henceforth also has various failure tests to provide diagnostic coverage, which use the ERROR directive to assert that a specific compiler error fires on a specific line:

fn main: () -> () {
    let a: i32;
    @(true) &= a; //? ERROR "expected i32 found bool"
}

Future goals

The middle end only implements DCE, Mem2Reg and CleanCFG because the goal was to first make a minimal proof of concept set of passes to test the infrastructure and the APIs of the compiler, and only work on adding more optimizations once we had a solid base to work on. LICM would be interesting to work on next when I have the time, as LoopInfo is already implemented.

Postponed features

We aimed for the language itself to be quite minimal on this initial release, so complex features like user types or pattern matching weren’t added, although we did get a lot of work done on tuples:

fn divmod: (i32 i32) -> ((i32 i32)) {
    let d: i32; &= d;
    let n: i32; &= n;
    let q: i32; @(n d /) &= q;
    let r: i32; @(n d %) &= r;
    @((q r))  // both results travel as a single value
}

fn main: () -> () {
    let result: (i32 i32);
    @(17 5) &> divmod &= result;
}

The idea was that tuples could be used to pass around sections of the stack as a single value, and syntactically they fit in very naturally. In practice, we never found a use case that convinced us they were worth it, or a syntax for accessing members that we were happy with, so they were left out of the language.

Support for pointers was also added, but we ultimately decided not to include it in this release³³If you try using them, you might get lucky and manage to compile a program, but these were definitely not tested!:

fn add_through: (i32* i32**) -> (i32) {
    let pp: i32**; &= pp;
    let p: i32*;   &= p;
    @(p^ pp^^ +)  // `^` dereferences, `^^` goes through two levels
}

fn main: () -> () {
    let x: i32; @(2) &= x;
    let y: i32; @(3) &= y;
    let py: i32*; @(y&) &= py; // `&` is the `AddressOf` operator
    @(x& py&) &> add_through &> print;
}

The problem with pointers is that they make it too easy to ignore the stack and write what is basically C, which goes against the idea of the language to begin with. The goal was for users to want (and have) to use stack features, and pointers were too “powerful” in what they allowed. They would also break the guarantee that stack values are always copies, which makes the flow of values much harder to reason about.

Using the language

While writing Tetris, I noticed that there are some patterns that feel very natural, such as writing while loops without a temporary variable:

fn func: () -> () {
    @(0) while @( @dup 100 !=) {
        // ... do things in the loop 
        @(1 +)  // increment the counter
    } @pop
} 

But since the only real data structure supported for this release is arrays and we didn’t add user types, you end up writing code that relies on passing around state in the form of specific i32 arguments, and that made it feel like it was hard to model some ideas. With support for user types, the language would probably be much more pleasant to use.

To my surprise, I had a lot of fun writing programs in Henceforth, and with more work on it, it could genuinely be used for non-trivial programs.

Conclusion

Henceforth was a great project to work on to further improve my understanding of compilers. It was my second full compiler implementation, and I was very happy to be able to try my hand at implementing a compiler again, but this time spending most of my effort in designing good APIs and making the codebase scalable.

Further development will be going on hiatus while I focus on the PhD prep phase at Saarland, and João has his Masters to work on as well.

I would’ve liked to implement more optimizations and expand the capabilities of our SSA middle end in general, but this is what we managed to implement over the last year with the free time we had. I hope to return to this codebase in the future to test out new optimizations in my own SSA middle end, and I’m very happy that I have a stable project where I get to play around with compiler related ideas.

For anyone interested in trying out the language or looking at the compiler, you can find it on GitHub, or you can go through the Language Reference & Getting Started Guide.