From meaning to instructions

By the time a Wahoo program reaches the code generator, everything about it is known: each name is a numbered slot, each expression has a type, each pipe has a signature. What is left is translation into a language with far fewer ideas. WebAssembly has no question, no bounce, no run, no text and no booleans: it has 32-bit integers, local slots, a linear array of bytes, and about a dozen ways of moving between instructions. Code generation is the art of saying rich things with a poor vocabulary.

§Intermediate representations

Real compilers rarely jump straight from a syntax tree to machine code. They pass through one or more intermediate representations (IRs), each closer to the machine than the last. The classic one is three-address code, in which every instruction has at most one operator:

// a + b * 2
t1 = b * 2
t2 = a + t1

Since the late 1980s most optimising compilers use a refinement of it, static single assignment form (SSA), in which every variable is assigned exactly once; a variable that changes in a loop is split into versions. SSA makes many optimisations simple, because the definition that reaches each use is obvious. LLVM, started by Chris Lattner in 2000, turned a well-designed SSA IR into a public interface: Clang, rustc, Swift, Julia and Zig all translate their languages into LLVM IR and let one shared back end do the rest. Without such a middle, M languages and N processors need M × N compilers; with it, M + N.

Wahoo's own IR is the typed HIR from chapter 03, and its target, WebAssembly, is itself an IR of sorts: the browser compiles it once more to the real processor (chapter 06).

§Stack machines

In a stack machine, instructions take their operands from the top of a stack and push their result back. i32.const 2 pushes a 2; i32.mul pops two numbers and pushes their product. Generating code for an expression is then a single walk of its tree in post-order: first the code for the operands, left to right, then the operator.

a + b * 2

local.get $a     ;; stack: a
local.get $b     ;; stack: a b
i32.const 2      ;; stack: a b 2
i32.mul          ;; stack: a (b*2)
i32.add          ;; stack: a+b*2

No temporary names, no registers to choose: the stack holds the intermediate results. That is why stack machines are popular as targets for virtual machines (the JVM, .NET's CIL, CPython's bytecode and WebAssembly all are), and why the expression part of a code generator for them fits in a few dozen lines.

§Lowering control flow

Processors do not have if or while, only conditional jumps. WebAssembly is a little more structured, deliberately: it has blocks, loops and if, and branches may only leave an enclosing block (br to a block) or go back to the top of an enclosing loop (br to a loop). There is no goto to an arbitrary address, which makes it possible to validate a module in one quick pass and to compile it safely. A branch names its target by depth: br 0 is the innermost enclosing construct, br 1 the next one out.

Here is what Wahoo's compiler actually emits for a bounce loop (the ;; comments with line numbers are added by the compiler, to tie each instruction to its source):

world 1-1 {
  coin lives = 3
  bounce lives > 0 {
    wahoo(lives)
    damage lives
  }
}

(func $world_1_1
  (local $lives i32)
  ;; 2: coin lives = 3
  i32.const 3
  local.set $lives
  ;; 3: bounce lives > 0 {
  block
    loop
      local.get $lives
      i32.const 0
      i32.gt_s
      i32.eqz
      br_if 1          ;; condition false: leave the block
      ;; 4: wahoo(lives)
      local.get $lives
      call $print_coins
      call $print_newline
      ;; 5: damage lives
      local.get $lives
      i32.const 1
      i32.sub
      local.set $lives
      br 0             ;; back to the top of the loop
    end
  end
)

The pattern is always the same: a block to have somewhere to escape to, a loop to have somewhere to come back to, the condition negated with i32.eqz so that br_if 1 leaves when it is false, the body, and an unconditional br 0. Notice damage lives: by now it is just lives = lives - 1, the desugaring from the checker. A run i from a to b loop is lowered the same way, with a hidden local holding b so that it is evaluated only once.

question maps onto WebAssembly's own if/else/end. The short-circuit operators use it too: a and b becomes “compute a; if it is true, compute b, else push 0”, an if that leaves a value on the stack (if (result i32)). That is how goomba and explode() never calls explode.

§Functions and calls

Each pipe becomes a WebAssembly function whose parameters are its first locals. A call pushes the arguments and executes call; the engine takes care of the call stack. flag becomes return. One detail shows how strict WebAssembly is:

pipe max(a: coins, b: coins) -> coins {
  question a > b {
    flag a
  } else {
    flag b
  }
}

(func $max (param $a i32) (param $b i32) (result i32)
  ;; 2: question a > b {
  local.get $a
  local.get $b
  i32.gt_s
  if
    ;; 3: flag a
    local.get $a
    return
  else
    ;; 5: flag b
    local.get $b
    return
  end
  unreachable
)

Both branches return, so the end of the function can never be reached. But the validator does not reason about that: it sees an if that leaves nothing on the stack, followed by the end of a function that must return an i32, and would reject the module. The final unreachable instruction tells it that control never gets there. Wahoo's checker has already proved it (chapter 03), so the code generator can say so safely.

§Data in memory

Numbers and switches fit in a stack slot, but texts do not. WebAssembly gives each module a linear memory, a plain array of bytes, and the compiler decides how to lay data out in it. Wahoo stores every text literal once, from address 16 onwards, as a four-byte length followed by its UTF-8 bytes, padded to a multiple of four. A text value is simply the address of its length. The bytes are placed there by a data segment, which the engine copies into memory when the module starts:

(data (i32.const 16) "\04\00\00\00fib(\04\00\00\00) = ")

Two identical literals are stored once, so they get the same address, and comparing addresses is comparing texts. The first sixteen bytes are left empty so that no text ever lives at address 0.

Printing is not something WebAssembly can do on its own: a module can only compute and touch its own memory. Everything else is imported from the host. Wahoo modules import four functions, print_coins, print_switch, print_text and print_newline, and export two things, their memory (so the host can read texts) and main, which plays every world in order. In the browser, the host is a few lines of JavaScript; on the command line, a few lines of Rust.

§What real back ends also do

Compiling to a stack machine skips the two hardest jobs of a back end for real processors. Instruction selection chooses, among the many instruction sequences that compute the same thing, a cheap one (x86 can multiply by 5 with a single address computation, lea). Register allocation decides which values live in the processor's handful of registers and which must be spilled to memory. In 1981 Gregory Chaitin showed how to treat it as colouring a graph, with one node per value and an edge between values alive at the same time: k registers means k colours. Graph colouring is NP-complete, so real allocators rely on good heuristics, and fast ones (in JITs) on simpler schemes such as linear scan. When a browser compiles a Wahoo module, it is the browser's engine that does this work.