Mapping a Language onto WebAssembly

A compiler targeting WebAssembly makes the same decisions as any backend (how values are represented, how functions are called, where memory comes from) but against a machine with unusual constraints. This chapter goes through those decisions in the order a backend meets them, collecting the advice of the earlier chapters into one place, and finishes by compiling a small program by hand.

#The decisions24.1

Here they are as a checklist. Each row refers to where the book covers it.

#Scalars24.2

Every scalar in your language becomes one of the four number types, as Chapter 4 described:

Choosing i32 for pointers means your language's usize is 32 bits on this target, and code that assumes 64-bit pointers will break, just as it would on any 32-bit platform. For a game in a browser, the 4 GiB limit is rarely a problem, and 32-bit pointers make every pointer-heavy data structure smaller and faster.

#Aggregates and unions24.3

Structs, tuples and fixed-size arrays live in linear memory with whatever layout your language specifies, as Chapter 10 described, or are scalarised into separate locals when the compiler can see every use of them. A local struct whose address is never taken does not need memory at all: each field can be its own local.

Tagged unions (enums with data, Option, Result) are a tag followed by storage for the largest variant. In memory, that is the usual layout. As values, a small union can be represented as several scalars, with the tag in one and the payload in others, which suits multiple results. Here is an Option<i32>, returned without touching memory:

(module
  (memory 1)
  (data (i32.const 0) "\0a\00\00\00" "\14\00\00\00" "\1e\00\00\00" "\28\00\00\00")
  ;; fn index_of(x: i32) -> Option<i32>, searching a 4-element array at 0
  ;; returns (tag, value): tag 0 is None, 1 is Some
  (func (export "index_of") (param $x i32) (result i32 i32)
    (local $i i32)
    (block $not_found
      (loop $next
        (br_if $not_found (i32.ge_u (local.get $i) (i32.const 4)))
        (if (i32.eq (i32.load (i32.shl (local.get $i) (i32.const 2))) (local.get $x))
          (then (return (i32.const 1) (local.get $i))))
        (local.set $i (i32.add (local.get $i) (i32.const 1)))
        (br $next)))
    (i32.const 0) (i32.const 0)))

1 2
0 0

A union whose variants hold different types, such as an i64 in one and an f64 in another, can share one i64 slot, with f64.reinterpret_i64 to read the float. For nullable pointers, use 0 as None and no tag at all, the same trick native compilers use, since address 0 is never a valid object in a sensible memory layout.

#Calling convention24.4

A calling convention decides how arguments and results are passed. With WebAssembly, most of it comes for free: parameters are parameters, and the engine assigns them to registers. What remains is deciding how to pass the things that are not single scalars:

• Small aggregates (up to four or so scalar fields) are passed as separate parameters, and returned as multiple results.
• Large aggregates are passed by pointer. To pass one by value, the caller copies it into its own shadow stack frame and passes the address. To return one, the caller passes the address where the callee should write it.
• Slices and strings are a pointer and a length, as two parameters.
• Closures take their environment as an extra first parameter (Chapter 11).
• Methods take the receiver as the first parameter.
• Variadic functions receive a pointer to a buffer in the caller's frame holding the extra arguments, which is how C's printf works on WebAssembly.

If your compiler ever needs to call C code compiled by Clang, or be called by it, follow the C ABI documented in the WebAssembly tool conventions repository, which pins down these choices for C types. Otherwise, the convention is entirely yours.

#Generics24.5

A generic function can be compiled once per instantiation (monomorphisation), or once for all instantiations, with values boxed and operations passed in as function pointers or dictionaries.

Monomorphisation produces the fastest code, and is what Rust, C++ and Zig do, but it multiplies code size, and on the web, code size is download size and compile time. A middle path compiles one copy per representation rather than per type: one for every type that is an i32, one for every f64, one for every pointer. Since WebAssembly only distinguishes a handful of value types, that bounds the number of copies of each generic function by a small constant.

#Control flow and the call stack24.6

Compile structured control flow straight from the syntax tree when you can, and use a stackifier when you have a control flow graph (Chapter 7). Keep every local whose address is never taken in a WebAssembly local, and everything else in a shadow stack frame (Chapter 10).

Three features need more than this, because they need to suspend a computation partway through and resume it later, and WebAssembly offers no way to capture its call stack:

• Generators, iterators and async functions can be compiled into state machines: each suspension point becomes a state, the function's live variables are saved in a heap object between calls, and resuming dispatches on the state (Chapter 7's dispatch loop). C#, Kotlin and JavaScript itself compile async this way, and it works well for functions that suspend only at points visible in their own body.
• Suspending through ordinary calls, as with green threads, fibers, or a synchronous API built on an asynchronous browser call, needs the whole call stack captured. Binaryen's Asyncify transformation does it by rewriting every function on the path to save its locals to memory and unwind, then rewind on resumption. It works, at a cost in code size and speed of roughly half again or more.
• JSPI (JavaScript Promise Integration), standardised in the JS API and shipping in Chrome, lets an import return a promise and suspends the entire WebAssembly computation until it resolves, with no transformation. The broader stack switching proposal, adding first-class continuations, is the eventual general solution for fibers and effect handlers.

For a game engine, the common case is a script that wants to wait for the next frame or for an asset to load. State machines handle that well, and are the easiest to debug.

#Runtime24.7

Every language needs some runtime code, compiled into the module or provided by the host: an allocator, panic handling, string formatting, perhaps a garbage collector. On the web, everything in the module is downloaded and compiled, so the runtime's size matters. Write it in your own language, or in C compiled to WebAssembly and linked in, and keep it small enough that a "hello world" is a few kilobytes, not hundreds.

The host side of the runtime is JavaScript: the glue that provides imports and calls exports. Generate it from your compiler, so that it always matches the module.

#A worked example24.8

Here is a small program in an imaginary game scripting language:

struct Vec2 { x: f32, y: f32 }

fn length_sq(v: Vec2) -> f32 {
    return v.x * v.x + v.y * v.y
}

fn total_length_sq(points: []Vec2) -> f32 {
    var total: f32 = 0
    for p in points {
        total += length_sq(p)
    }
    return total
}

Applying the decisions above:

• Vec2 has two f32 fields, so it is passed flattened, as two f32 parameters. In memory, it is 8 bytes: x at offset 0 and y at 4.
• []Vec2 is a slice, so a pointer and a count.
• total and p never have their addresses taken, so they are locals, and p is scalarised into its two fields.
• The for loop is a block and a loop, with the test at the top.

(module
  (import "env" "print_f32" (func $print (param f32)))
  (memory 1)
  ;; three points: (3, 4), (1, 1), (0, 2)
  (data (i32.const 64)
    "\00\00\40\40" "\00\00\80\40"
    "\00\00\80\3f" "\00\00\80\3f"
    "\00\00\00\00" "\00\00\00\40")

  (func $length_sq (param $v.x f32) (param $v.y f32) (result f32)
    (f32.add
      (f32.mul (local.get $v.x) (local.get $v.x))
      (f32.mul (local.get $v.y) (local.get $v.y))))

  (func $total_length_sq (param $points.ptr i32) (param $points.len i32) (result f32)
    (local $total f32)
    (local $end i32)
    (local.set $end (i32.add (local.get $points.ptr)
                             (i32.shl (local.get $points.len) (i32.const 3))))
    (block $break
      (loop $continue
        (br_if $break (i32.ge_u (local.get $points.ptr) (local.get $end)))
        (local.set $total (f32.add (local.get $total)
          (call $length_sq
            (f32.load offset=0 (local.get $points.ptr))
            (f32.load offset=4 (local.get $points.ptr)))))
        (local.set $points.ptr (i32.add (local.get $points.ptr) (i32.const 8)))
        (br $continue)))
    (local.get $total))

  (func (export "main")
    (call $print (call $total_length_sq (i32.const 64) (i32.const 3)))))

31

Three things are worth noticing. The loop iterates with a pointer rather than an index, a classic strength reduction that saves a multiplication per iteration; engines will not do this for you in their baseline tier. The slice's ptr parameter is reused as the loop cursor, since parameters are just locals. And $length_sq is small enough that a compiler would probably inline it, which engines' optimising tiers also do, but only for hot code, and only after it has run unoptimised for a while.

Naming locals after the source variables, $points.ptr and $v.x, costs nothing, since names go in the name section, and makes the output far easier to read when debugging the compiler.

#What you have seen24.9

Mapping a language onto WebAssembly comes down to a series of decisions: where objects live, how scalars and aggregates are represented, how functions are called, how generics are instantiated, how control flow and suspension are compiled, and what runtime the module carries. For most of them, there is a well-trodden default. The next chapter looks at what the engine does with the result.