The LLVM Backend: Lowering to an IR Built for Compilers

The C backend translated Mere into another language for people — one with expressions, nested structure, local variables, and an if that behaves the way you’d expect. The next backend translates it into something built for a very different reader: LLVM’s intermediate representation, the form a compiler wants to consume. The features to support are the same ones the C backend already covered. What changes is how much of the lowering you have to do yourself, because the target has stripped away nearly everything C was quietly doing for you.

A target with no conveniences

Three differences define the shift from C to LLVM IR, and each moves work from the target onto the compiler.

The first is static single assignment. In LLVM IR every value is written to a virtual register exactly once — %1, %2, and so on, an endless supply, with the mapping to real machine registers left for LLVM to decide later. You do not reassign a variable; you produce a new register. That single rule reshapes everything downstream, and its sharpest consequence is control flow.

The second is that there is no structured if. C let the backend write cond ? a : b and move on. LLVM IR has only basic blocks and branches: to compile an if, you compute the condition as an i1, branch conditionally to two labelled blocks, let each block compute its own value, and then — because SSA forbids one variable holding two different values — reconcile the two results at the join point with a phi node, an instruction that says “this value is whichever one arrived, depending on which block we came from.” The humble if/then/else becomes four blocks and a phi. Every branch in the language, every arm of a match, lowers this way: extract the tag, icmp it against each constructor, chain of conditional branches, and a phi merging the arms back together.

The third is that types are explicit and close to the machine. A bool is i1 and gets zero-extended to i32 before it can be printed; a pointer is ptr; a tuple is a named struct type %tuple_int_str = type { i32, ptr } that you don’t fill in with a literal but assemble instruction by instruction with insertvalue, and read back with extractvalue. Addressing into a heap structure is a getelementptr. The runtime helpers C could #include are instead defined inline in the IR — string concatenation spelled out as malloc plus strlen plus memcpy — and functions like puts and strcmp are declared and called directly. A few things get easier, not harder: LLVM allows forward references within a module, so the forward declarations C needed for mutual recursion simply aren’t required.

The same ladder, climbed a second time

The striking thing about building the LLVM backend is how exactly it retraced the C backend’s steps. The same features arrived in the same order — integers, strings, tuples, records, variants with match, first-class functions, closures with captures, monomorphized polymorphic types, recursive variants, the full pattern language, show, and the whole memory model of regions and with and views — each one a small slice, each translating a construct that the C backend had already translated, but now into SSA and basic blocks instead of C expressions. A closure is still a two-word pair of a function pointer and an environment pointer; it is just now a %closure_T1_T2 = type { ptr, ptr } assembled with insertvalue rather than a C struct with a compound literal. By the last slice, the LLVM backend covered every feature the C backend did, in parallel.

Climbing the same ladder twice is not waste; it is a second kind of check. The C backend proved the language could be lowered into a human-facing target; the LLVM backend proves it can also be lowered into a compiler-facing one — a target with none of C’s structure, where you supply the basic blocks and the phi nodes and the explicit types by hand. A feature that lowers cleanly into both of those very different shapes is a feature that was defined clearly enough to survive the translation, which is a quiet form of design validation. And both lowerings are held to the same interpreter, so now three implementations must agree byte for byte — the interpreter, the C output, and the LLVM output — and each new one makes the differential test from two episodes ago stricter.

Why bother, when C already ran everywhere

If the C backend already produces portable native code, emitting LLVM IR by hand — doing all that lowering C did for free — needs a reason. The reason is what sits on the other side of the IR. LLVM’s optimizer and native code generator are among the best in existence, the same machinery behind Clang, Rust, and Swift: register allocation, instruction selection, inlining, aggressive optimization, and codegen for every platform LLVM targets. By emitting IR, Mere hands its programs to that infrastructure and inherits all of it. The trade is explicit and deliberate — do more of the lowering work up front, in exchange for professional-grade optimization and native code that no one on the project has to write.

That is the shape of the choice across the whole part: C for reach and simplicity, LLVM for optimization, the interpreter for the reference, all held to identical output. Two code generators now exist, feature-for-feature matched and byte-for-byte verified against each other and the interpreter. The natural question is whether that agreement survives contact with programs that aren’t small — a thousand-line parser, not a ten-line demo. Next: keeping them identical at scale, where a realistic program over a thousand lines long produces the exact same bytes on every backend, and what that costs to maintain.