Encoding Instructions

The last chapter encoded everything but code. This one encodes function bodies: local declarations, opcodes, and the immediates that follow them. Then it puts everything together into a small encoder, about a hundred lines of Python, that writes modules an engine will run. The encoder is not meant to be used as it stands, but it shows every decision a real one makes, and it is a template for the backend of your own compiler.

#Function bodies13.1

The code section is a vector of bodies, one per function in the function section, in the same order. Each body is:

size        u32: the number of bytes in the rest of the body
locals      a vector of (count, value type) pairs
code        instructions, ending with 0b (end)

The local declarations are run-length encoded. A function with locals i32 i32 i32 f64 i32 declares them as three groups: (3, i32) (1, f64) (1, i32), which is 03 03 7f 01 7c 01 7f. Parameters are not declared here, since they come from the function's type; the declared locals are numbered after them.

#Opcodes and immediates13.2

Each instruction is an opcode byte, followed by its immediates, the operands that are part of the instruction rather than taken from the stack. Most instructions have none:

(module
  (func (export "f") (param i32 i32) (result i32)
    (local i64 i64 f32)
    (i32.mul (i32.add (local.get 0) (local.get 1)) (i32.const -2))))

wasm-objdump -d arith.wasm | tail -n +5

000020 func[0] <f>:
 000021: 02 7e                      | local[2..3] type=i64
 000023: 01 7d                      | local[4] type=f32
 000025: 20 00                      | local.get 0
 000027: 20 01                      | local.get 1
 000029: 6a                         | i32.add
 00002a: 41 7e                      | i32.const 4294967294
 00002c: 6c                         | i32.mul
 00002d: 0b                         | end

local.get (20) takes a local index. i32.const (41) takes its value in signed LEB128, so −2 is the single byte 7e; wasm-objdump prints it as unsigned. i64.const (42) is the same with up to ten bytes. f32.const (43) and f64.const (44) take four or eight raw bytes.

Here are the immediates of the instructions you have met so far:

Appendix A lists every opcode.

#Block types13.3

block, loop and if are followed by a block type, saying what the construct takes and leaves on the stack. It has three forms, chosen by the first byte:

• 40: no parameters and no results;
• a value type such as 7f: no parameters and that one result;
• a type index, as a signed LEB128 number (33 bits wide, so all valid indices are non-negative): the parameters and results of that function type. This form is needed for blocks with parameters or with more than one result.

The three can be told apart because value types are bytes in the range of small negative numbers, and 40 is −64, which no value type uses. The construct ends with 0b; an if with an else arm has 05 between the arms.

(module
  (type $pair (func (param i32) (result i32 i32)))
  (func (export "f") (param i32) (result i32)
    (block $outer (result i32)
      (loop $l
        (br_if $l (i32.eqz (local.get 0))))
      (local.get 0)
      (block (type $pair)
        (i32.const 1))
      (i32.add)
      (if (param i32) (result i32) (local.get 0)
        (then)
        (else (drop) (i32.const 0)))
      (br 0))))

wasm-objdump -d blocks.wasm | tail -n +6

000025 func[0] <f>:
 000026: 02 7f                      | block i32
 000028: 03 40                      |   loop
 00002a: 20 00                      |     local.get 0
 00002c: 45                         |     i32.eqz
 00002d: 0d 00                      |     br_if 0
 00002f: 0b                         |   end
 000030: 20 00                      |   local.get 0
 000032: 02 00                      |   block type[0]
 000034: 41 01                      |     i32.const 1
 000036: 0b                         |   end
 000037: 6a                         |   i32.add
 000038: 20 00                      |   local.get 0
 00003a: 04 01                      |   if type[1]
 00003c: 05                         |   else
 00003d: 1a                         |     drop
 00003e: 41 00                      |     i32.const 0
 000040: 0b                         |   end
 000041: 0c 00                      |   br 0
 000043: 0b                         | end
 000044: 0b                         | end

The if with a parameter needed a function type [i32] → [i32], which the assembler added to the type section as type 1. An encoder that supports blocks with parameters has to do the same: intern a function type for each such block signature.

#Memory immediates13.4

A load or store is followed by a memarg: the alignment, as a power of two (so align=4 is written 02), then the offset, both as unsigned LEB128:

(module
  (memory 1)
  (func (export "f") (param i32) (result i32)
    (i32.store8 offset=3 (local.get 0) (i32.const 7))
    (i32.load offset=1024 align=1 (local.get 0))))

wasm-objdump -d mem.wasm | tail -n +6

000024 func[0] <f>:
 000025: 20 00                      | local.get 0
 000027: 41 07                      | i32.const 7
 000029: 3a 00 03                   | i32.store8 0 3
 00002c: 20 00                      | local.get 0
 00002e: 28 00 80 08                | i32.load 0 1024
 000032: 0b                         | end

3a 00 03 is i32.store8 with alignment 2⁰ and offset 3. 28 00 80 08 is i32.load with alignment 2⁰ (the align=1 the text asked for) and offset 1024 in LEB128. With multiple memories, a memarg whose alignment field has bit 6 set (64 added to it) is followed by a memory index.

#Prefixed opcodes13.5

One byte allows only 256 opcodes, and they ran out. Newer instructions use a prefix byte followed by a second opcode in unsigned LEB128:

(module
  (memory 1)
  (func (export "f") (param f64) (result i32)
    (memory.fill (i32.const 0) (i32.const 0) (i32.const 16))
    (i32.trunc_sat_f64_s (local.get 0))))

wasm-objdump -d prefixed.wasm | tail -n +6

000024 func[0] <f>:
 000025: 41 00                      | i32.const 0
 000027: 41 00                      | i32.const 0
 000029: 41 10                      | i32.const 16
 00002b: fc 0b 00                   | memory.fill 0
 00002e: 20 00                      | local.get 0
 000030: fc 02                      | i32.trunc_sat_f64_s
 000032: 0b                         | end

#An encoder13.6

That is everything needed to write an encoder. A real one has three parts: a byte buffer with methods for each encoding (LEB128, names, vectors), a module builder that collects types, imports, functions and so on and assigns their indices, and a function builder that turns instructions into bytes. Here they are, small enough to read in one go.

First, the encodings. leb and sleb are from the last chapter:

import struct

def uleb(n):
    out = bytearray()
    while True:
        byte, n = n & 0x7f, n >> 7
        out.append(byte | (0x80 if n else 0))
        if not n:
            return bytes(out)

def sleb(n):
    out = bytearray()
    while True:
        byte, n = n & 0x7f, n >> 7
        done = (n == 0 and not byte & 0x40) or (n == -1 and byte & 0x40)
        out.append(byte if done else byte | 0x80)
        if done:
            return bytes(out)

def name(s):
    b = s.encode("utf-8")
    return uleb(len(b)) + b

def vec(items):
    return uleb(len(items)) + b"".join(items)

def section(id, contents):
    return bytes([id]) + uleb(len(contents)) + contents

I32, I64, F32, F64 = 0x7f, 0x7e, 0x7d, 0x7c

section sidesteps the size problem the last chapter mentioned: it builds the contents first, as a separate bytes object, and only then writes the size in front. The cost is a copy of each section, which is negligible. Encoders that care about every copy, such as one generating code on the fly in a browser, reserve five bytes for each size and fill them in with a padded LEB128 afterwards instead.

Next, a function builder. It has a method per instruction that the examples need, and every method returns self, so calls can be chained. A real encoder would generate these methods from a table:

class Func:
    def __init__(self, params, results):
        self.params, self.results = params, results
        self.locals = []
        self.code = bytearray()

    def local(self, ty):
        """Declare a local, and return its index."""
        self.locals.append(ty)
        return len(self.params) + len(self.locals) - 1

    def op(self, opcode, *immediates):
        self.code.append(opcode)
        for imm in immediates:
            self.code += imm
        return self

    # a few instructions
    def local_get(self, i): return self.op(0x20, uleb(i))
    def local_set(self, i): return self.op(0x21, uleb(i))
    def local_tee(self, i): return self.op(0x22, uleb(i))
    def call(self, f):      return self.op(0x10, uleb(f))
    def i64_const(self, n): return self.op(0x42, sleb(n))
    def i32_const(self, n): return self.op(0x41, sleb(n))
    def f64_const(self, x): return self.op(0x44, struct.pack("<d", x))
    def block(self):        return self.op(0x02, b"\x40")
    def loop(self):         return self.op(0x03, b"\x40")
    def end(self):          return self.op(0x0b)
    def br(self, depth):    return self.op(0x0c, uleb(depth))
    def br_if(self, depth): return self.op(0x0d, uleb(depth))
    def i64_eqz(self):      return self.op(0x50)
    def i64_mul(self):      return self.op(0x7e)
    def i64_sub(self):      return self.op(0x7d)

    def body(self):
        # run-length encode the locals: consecutive locals of one type form a group
        groups = []
        for ty in self.locals:
            if groups and groups[-1][1] == ty:
                groups[-1][0] += 1
            else:
                groups.append([1, ty])
        decls = vec([uleb(n) + bytes([ty]) for n, ty in groups])
        contents = decls + bytes(self.code) + b"\x0b"      # the function's own end
        return uleb(len(contents)) + contents

Finally, the module builder. It interns function types, so each signature is in the type section once, and numbers functions with imports first:

class Module:
    def __init__(self):
        self.types, self.imports, self.funcs, self.exports = [], [], [], []

    def type_index(self, params, results):
        t = (tuple(params), tuple(results))
        if t not in self.types:
            self.types.append(t)
        return self.types.index(t)

    def import_func(self, module, field, params, results):
        assert not self.funcs, "imports must be added before functions"
        self.imports.append((module, field, self.type_index(params, results)))
        return len(self.imports) - 1

    def func(self, params, results, export=None):
        f = Func(params, results)
        self.funcs.append(f)
        index = len(self.imports) + len(self.funcs) - 1
        if export:
            self.exports.append((export, index))
        return f, index

    def encode(self):
        for f in self.funcs:
            self.type_index(f.params, f.results)
        types = vec([b"\x60" + vec([bytes([p]) for p in ps]) + vec([bytes([r]) for r in rs])
                     for ps, rs in self.types])
        imports = vec([name(m) + name(f) + b"\x00" + uleb(t) for m, f, t in self.imports])
        funcs = vec([uleb(self.type_index(f.params, f.results)) for f in self.funcs])
        exports = vec([name(n) + b"\x00" + uleb(i) for n, i in self.exports])
        code = vec([f.body() for f in self.funcs])
        out = b"\x00asm\x01\x00\x00\x00" + section(1, types)
        if self.imports:
            out += section(2, imports)
        return out + section(3, funcs) + section(7, exports) + section(10, code)

Now a program that uses it: an iterative factorial on i64s, and a main that prints two results through the book's host:

m = Module()
print_i64 = m.import_func("env", "print_i64", [I64], [])

# fac(n): acc = 1; while (n != 0) { acc *= n; n -= 1 } return acc
fac, fac_index = m.func([I64], [I64], export="fac")
n = 0
acc = fac.local(I64)
(fac.i64_const(1).local_set(acc)
    .block().loop()
        .local_get(n).i64_eqz().br_if(1)
        .local_get(acc).local_get(n).i64_mul().local_set(acc)
        .local_get(n).i64_const(1).i64_sub().local_set(n)
        .br(0)
    .end().end()
    .local_get(acc))

main, _ = m.func([], [], export="main")
main.i64_const(10).call(fac_index).call(print_i64)
main.i64_const(20).call(fac_index).call(print_i64)

wasm = m.encode()
open("out.wasm", "wb").write(wasm)
print(len(wasm), "bytes")

119 bytes
3628800
2432902008176640000

The book's harness validated out.wasm with V8 and ran it, which is the same thing the encoder's own tests should do. Part VIII builds on exactly that.

#Things a real encoder adds13.7

The toy above leaves out several things a production encoder needs:

• Every instruction, ideally generated from a table such as the one in Appendix A, so that no opcode is mistyped by hand.
• Label depths from names. Asking the code generator to count depths invites mistakes. Better to have block() and loop() return a label object, keep a stack of open constructs, and compute the depth when a branch to a label object is emitted.
• Validation as it goes. Tracking the operand stack's types while emitting, as the validator would, catches code generator bugs at the instruction that caused them, rather than as an opaque error from the engine later. Binaryen and the wasm-encoder crate leave this to a separate validator; some JIT encoders build it in.
• The other sections, and their order: memory, tables, globals, data and element segments, the data count section (needed whenever the code uses memory.init or data.drop), and custom sections.

You may not want to write an encoder at all. Libraries exist for most languages a compiler is written in. In Rust, wasm-encoder (part of wasm-tools) is a thin, complete, fast encoder much like the one above. Binaryen, usable from C, C++, JavaScript and through bindings elsewhere, is a whole compiler infrastructure with its own IR, optimiser and validator. Its IR is an expression tree, so a code generator can hand it nested expressions and let it worry about the stack. Writing your own gives you full control and no dependencies; using Binaryen gives you its optimiser, which Chapter 25 shows is worth having.

#What you have seen13.8

A function body is its size, run-length-encoded local declarations, and instructions ending with 0b. Each instruction is an opcode, or a prefix and an opcode, followed by immediates: indices and constants in LEB128, float constants as raw bytes, block types in one of three forms, and memargs giving alignment and offset. An encoder is a byte buffer, a module builder that assigns indices and interns types, and a function builder that appends instructions, and the result can be tested by running it.

The next chapter covers the bytes that are not code at all: custom sections, names and debugging information.