Chapter 3

A Stack Machine

WebAssembly code computes with an operand stack. Instructions pop their operands off it and push their results onto it. This chapter shows how that works, how the text format lets you write it in two different shapes, how local variables fit in, and why the stack, despite appearances, is not something the machine maintains at runtime.

#Pushing and popping3.1

Here is a function that computes (2 + 3) × 4:

(module
  (func (export "main") (result i32)
    i32.const 2
    i32.const 3
    i32.add
    i32.const 4
    i32.mul))

Each instruction has a fixed effect on the stack. i32.const 2 pushes 2. i32.add pops two i32s and pushes their sum. i32.mul pops two and pushes their product. When the body ends, the one value left is the function's result.

The operand stack after each instruction of (2 + 3) × 4.

The specification writes each instruction's effect as a type, with what it pops on the left and what it pushes on the right:

Instruction	Type
`i32.const 2`	`[] → [i32]`
`i32.add`	`[i32 i32] → [i32]`
`i32.eqz`	`[i32] → [i32]`
`drop`	`[t] → []`
`select`	`[t t i32] → [t]`
`nop`	`[] → []`

The order matters for instructions that are not commutative. The first operand is the one pushed first, so it is deeper in the stack:

(module
  (func (export "main") (result i32)
    i32.const 10
    i32.const 3
    i32.sub))     ;; 10 - 3, not 3 - 10

#Watching the stack3.2

wabt's wasm-interp is a simple interpreter, and with --trace it shows the stack as it runs. It is a good way to check your understanding of a piece of code:

(module
  (func (export "main") (result i32)
    i32.const 10
    i32.const 3
    i32.sub))

wasm-interp sub.wasm --run-all-exports --trace

>>> running export "main":
#0.    0: V:0  | i32.const 10
#0.    8: V:1  | i32.const 3
#0.   16: V:2  | i32.sub 10, 3
#0.   20: V:1  | return
main() => i32:7

Each line shows where the instruction is in the interpreter's own translation of the code (not the file), the stack depth before it runs (V:2 means two values), and for instructions that pop, the values they popped. The return at the end is the interpreter's rendering of the function's final end.

#The folded form3.3

Writing one instruction per line gets hard to read once expressions nest. The text format has a second shape for the same instructions, the folded form, where an instruction is written in parentheses with its operands inside it:

(module
  (func (export "main") (result i32)
    (i32.mul
      (i32.add (i32.const 2) (i32.const 3))
      (i32.const 4))))

This is pure notation. The assembler unfolds it, operands first, into exactly the same five instructions as before. You can mix the two forms freely, and this book does: folded where it makes the structure clearer, flat where the order of operations is the point.

(module
  (func (export "main") (result i32)
    (i32.add (i32.const 2) (i32.const 3))   ;; leaves 5 on the stack
    i32.const 4
    i32.mul))

wasm2wat always prints the flat form, since that is what is actually in the binary. It can print the folded form if you ask, with --fold-exprs.

#Locals3.4

A function's parameters and its local variables live in numbered slots called locals. local.get pushes a local's value. local.set pops a value into a local. local.tee stores into a local but leaves the value on the stack, like an assignment expression in C.

Parameters are the first locals. Any further locals are declared at the start of the function with (local ...), and they all start at zero:

(module
  (func (export "hypot2") (param $x i32) (param $y i32) (result i32)
    (local $xx i32)
    (local.set $xx (i32.mul (local.get $x) (local.get $x)))
    (i32.add
      (local.get $xx)
      (i32.mul (local.get $y) (local.get $y)))))

called as hypot2(3, 4)

$x is local 0, $y is local 1, and $xx is local 2. As with functions, the names are a text-format convenience. Here is the same function with indices, and local.tee saving a local.set and a local.get:

(module
  (func (export "hypot2") (param i32 i32) (result i32) (local i32)
    local.get 0
    local.get 0
    i32.mul
    local.tee 2          ;; store x*x in local 2, and keep it on the stack
    local.get 1
    local.get 1
    i32.mul
    i32.add))

called as hypot2(3, 4)

Locals are typed. Each holds one value of its declared type, and every local.get and local.set is checked against that type before the code ever runs.

#drop and select3.5

drop throws away the top of the stack. You need it whenever an instruction produces a value you do not want, since a function's stack must hold exactly its results when it ends:

(module
  (func (export "main") (result i32)
    i32.const 1
    i32.const 2
    drop))

select is a conditional move. It pops a condition and two values, and pushes the first value if the condition is non-zero and the second otherwise. Both values are always computed, so it is for cheap operands, like a C ternary whose arms have no side effects:

(module
  (func (export "max") (param $a i32) (param $b i32) (result i32)
    (select
      (local.get $a)
      (local.get $b)
      (i32.gt_s (local.get $a) (local.get $b)))))

called as max(3, 9), max(9, 3) and max(-5, -6)

9
9
-5

i32.gt_s compares two i32s as signed numbers and pushes 1 if the first is greater, 0 otherwise. There is no boolean type. Comparisons produce an i32 that is 0 or 1, and conditions accept any i32, treating zero as false and everything else as true.

#The stack is checked before anything runs3.6

Every function's code is validated when the module is compiled. The validator walks the instructions once, tracking the types on the stack, and rejects the module if any instruction would pop a value that is not there, or pop the wrong type, or if the stack does not hold exactly the function's results at the end.

Leaving an extra value behind is an error:

(module
  (func (export "main") (result i32)
    i32.const 1
    i32.const 2))

CompileError: WebAssembly.Module(): Compiling function #0 failed: expected 1 elements on the stack for fallthru, found 2 @+38

So is popping a value of the wrong type:

(module
  (func (export "main") (result i32)
    i32.const 1
    i64.const 2
    i32.add))

i32.add[1] expected type i32, found i64.const of type i64

These are V8's messages, which is what you would see in Chrome's console. @+38 is the byte offset in the binary where V8 found the problem; the fallthru is the end of the function, where control falls out of the body. Each engine words its messages differently. Wasmtime, for one, would say type mismatch: expected i32, found i64. Chapter 6 shows how validation handles control flow, and Chapter 27 shows how to get every engine's opinion on a module your compiler produced.

Because of validation, there is never any doubt about the stack at a given instruction. Its depth and the type of every slot are fixed, the same every time that instruction runs, no matter what path led there.

#The stack does not exist3.7

That last fact is what lets engines throw the stack away.

This has a practical consequence for compilers. There is no cost to the stack itself, so you do not need to minimise stack traffic, and there is no benefit to clever stack scheduling. Emit whatever shape of code is simplest for your compiler. The engine's register allocator will undo it.

What can matter is the number of locals and how long each one is live, since those are what the register allocator works with. That is the same problem a native backend has, and it is the engine's to solve, which is one of the main reasons WebAssembly is a good compilation target: instruction selection and register allocation, the hardest parts of a native backend, are done for you.

#What you have seen3.8

Instructions pop operands from a typed stack and push results. The folded form is a notation for writing nested expressions, and unfolds to the same instructions. Locals are numbered, typed slots, parameters first. Validation checks every stack effect before the code runs, which is what lets engines turn the stack into registers.

The next chapter looks at the values themselves.