Wasm32: a 32-bit stack machine for teaching, based on the i32 subset of WebAssembly. There are no general-purpose registers: instructions pop operands from a stack and push results. Control flow is structured (block, loop, if, each closed by end), and functions are called by address.

_start:
    i32.const 2        ; 2
    i32.const 3        ; 3:2
    i32.add            ; 5
    halt

Sections, labels and data directives are shared by all ISAs; see the Wrench documentation. Specific to wasm32:

• Mnemonics are WebAssembly text-format names. A line may hold several instructions. Comments start with ;.
• Execution starts at _start.
• i32.const takes a 32-bit number or a label. Other immediates are unsigned bytes, 0 to 255, checked at translation. A load or store offset is optional (default 0) and must be a number.
• An instruction is one byte, plus one per byte immediate, plus four for i32.const.
• .frame names a function's locals (see Functions and locals).

An immediate is written <name: type>. A stack effect ( before -- after ) has the top rightmost: i32.sub ( a: i32, b: i32 -- difference: i32 ) pops b, then a, and pushes a - b. An error stops the simulation with a message.

• Constants and arithmetic: i32.const, i32.add, i32.sub, i32.mul, i32.div_s, i32.rem_s
• Bitwise and shifts: i32.and, i32.or, i32.xor, i32.shl, i32.shr_s, i32.shr_u
• Comparison: i32.eqz, i32.eq, i32.lt_s, i32.le_s, i32.gt_s, i32.ge_s, i32.lt_u, i32.le_u, i32.gt_u, i32.ge_u
• Memory: i32.load, i32.load8_u, i32.load8_s, i32.store, i32.store8
• Control: block, loop, if, else, end, br, br_if, unreachable
• Functions: call, return
• Locals and stack: local.get, local.set, local.tee, locals.reserve, drop, select
• Machine: sp.init, halt

Unlike the other wrench ISAs, wasm32 has no general-purpose registers, no flags and no branches to labels. Values live on stacks in memory, loops are nested scopes, and each call gets its own frame. Each section builds on the previous one.

Code, data, I/O ports and both stacks share one byte-addressed memory. The stacks start at stackRoot (three quarters into memory, unless sp.init moves it) and grow apart: the operand stack down, the control stack up.

memory end   +---------------------+
             |         ...         |
ctrlSp    -> +---------------------+
             | control stack       |  grows up
stackRoot -> +=====================+
             | operand stack       |  grows down
sp        -> +---------------------+
             |                     |
             |         ...         |
             |                     |
             | .text, .data        |
0            +---------------------+

Besides memory, the machine keeps only pc, an instruction register and a few stack pointers, introduced below. The stacks are plain memory: a program can read and overwrite them, and nothing stops them from running into each other or into code and data.

Memory is read a word (4 bytes) at a time, from any address. The machine keeps the instructions it read in the instruction register. A fetch takes the instruction at pc from there at no cost; otherwise it reads words starting at pc, 1 read for an instruction of up to 4 bytes and 2 for i32.const, and keeps that instruction and every following one that ends inside the first word read. Here the first local.get reads the word holding both local.gets, and i32.mul the word holding local.set too, so the four instructions cost 2 fetch reads:

local.get $acc local.get $n i32.mul
local.set $acc

Data reads never come from the instruction register, and stores don't change it.

Every value is a 32-bit word. i32.const pushes a value; an operation pops its operands and pushes its result. sp is the address of the top value; a push moves it four bytes down, a pop four bytes up. Comments show the stack after each line as the stack view prints it: top first, separated by colons.

i32.const 7         ; 7
i32.const 2         ; 2:7
i32.sub             ; 5         7 - 2: the deeper value is the left operand
i32.const 3         ; 3:5
i32.mul             ; 15

Memory is accessed through the stack too: i32.load pops an address and pushes the word there; i32.store pops a value, then an address. I/O ports (memory_mapped_io in the configuration) are ordinary addresses: a load from an input port reads the next input, a store to an output port writes one. This copies one value from the input at 128 to the output at 132:

i32.const 132       ; 132
i32.const 128       ; 128:132
i32.load            ; x:132
i32.store           ;

A push writes its value to memory, and a pop reads it back: one access each. The machine also keeps copies of the last two values pushed in two top-of-stack registers, with the address of each one's slot, and popping one of them reads nothing. So most operations pay only for their fetch and their result: i32.add right after two pushes reads nothing but its fetch and writes only the sum. A register lets go of its value when it is popped, when a third push needs the register, or when anything writes to its slot, so memory always holds the whole stack and the registers never disagree with it. A slot at an I/O port is never held, since reading the port gives the next input instead. The registers start empty and are shown by the stack:tos-regs view.

A comparison pushes 1 (true) or 0 (false), and if pops it. If it is non-zero, execution enters the body, and reaching else jumps past the matching end. If it is zero, execution jumps past the matching else, or past end if there is none.

This writes -1 if x is negative, 1 otherwise:

i32.const 132                 ; 132
i32.const 128 i32.load        ; x:132
i32.const 0 i32.lt_s          ; (x<0):132
if                            ; 132
    i32.const -1              ; -1:132
else
    i32.const 1               ; 1:132
end
i32.store                     ;

What either part pushes stays on the stack after end. Nothing checks that both parts push the same number of values.

There is no table of end addresses. To skip, if or else reads the following instructions one by one, tracking nested block, loop and if, until it finds its own else or end. Each instruction it reads is fetched like any other, so each path pays for the part it skips. In the example, if comes in the same word as i32.lt_s, so its fetch is free, and the flag it pops is still in a top-of-stack register. When x is negative if costs nothing and else 4 (fetch, 2 for the five-byte i32.const 1, end); otherwise if costs 3 (2 for i32.const -1, else), as the mem:accesses view shows. An if's end does nothing; a missing end is noticed only when a skip looks for it.

The machine remembers its last four scans in the scan cache: where each scan started and where it ended. When the same if or else skips again while its entry is still there, it continues at the remembered address and reads nothing: in the example, a second negative x costs 1 access for the else (its fetch), and a second positive one nothing for the if. A hit moves its entry to the front, and a new scan pushes out the entry used longest ago, so a loop whose body skips at more than four places can lose an entry before it comes round again. The cache is part of the machine, not of memory, starts empty, and is shown by the cache:scan view.

if only skips forward, and a branch cannot name a label. To repeat code, wrap it in a scope and branch to the scope. Scopes nest, each closed by its own end:

• block ... end -- a branch to a block breaks out: execution continues after its end.
• loop ... end -- a branch to a loop continues it: execution returns to the start of its body. Without a branch the body runs once.

Open scopes live on the control stack. block or loop pushes an eight-byte record with the addresses a branch needs, and its end pops it. ctrlSp points just past the top record. To fill the record, block and loop search for their end the way if skips, through the same scan cache, so entering a scope again soon costs only its fetch and the record.

br n jumps to the scope n records down (0 is the innermost) and pops the records of the scopes it leaves; br_if n does the same if the value it pops is non-zero. if pushes no record, so it is not counted and cannot be a target. Branches leave the operand stack unchanged.

A taken branch reads its scope's record, 2 accesses, to learn where to go. The machine remembers its last four taken branches in the /branch cache/: where each branch was, which record it read, and where it went. When the same branch is taken again with the same record at the same place on the control stack, it goes to the remembered address without reading the record: in the example below, br 0 costs 3 accesses in the first round and only its fetch after that. A write that changes a remembered record makes the machine forget the branches that read it, so a remembered branch always goes where reading the record would. Like the scan cache, the branch cache is part of the machine, starts empty, and is shown by the cache:branch view.

This writes n, n - 1, ..., 1, with n a word in .data:

block                                 ; control stack: block
    loop                              ; control stack: loop:block
        i32.const n i32.load
        i32.eqz
        br_if 1                       ; n = 0 -> leave the block
        i32.const 132
        i32.const n i32.load
        i32.store                     ; write n
        i32.const n
        i32.const n i32.load
        i32.const 1 i32.sub
        i32.store                     ; n -= 1
        br 0                          ; back to the loop head
    end
end

Here block costs 21 accesses (19 reads to fetch it and the instructions up to its end, two record words), and loop the same. A missing end is reported when its scope runs.

example/wasm32/factorial.s is a complete program with a loop.

A function is a label; its address is an ordinary value:

i32.const 10          ; 10
i32.const fib         ; fib:10
call 1, 1             ; fib(10)     one parameter, one result

In f32a a call only saves a return address and the callee shares the caller's data stack. Here call p, r pops the target and gives the callee its own frame:

1. The top p values stay in place and become the callee's locals 0 to p-1 (local 0 was pushed first). These are its parameters; the caller's frame now ends below them.
2. A call record on the control stack saves the caller's frame, the return address and r.
3. The callee starts at the target with an empty operand stack.

A frame holds its locals, then its operands. While _start runs a function with two parameters and one more local:

ctrlSp    -> +---------------------+
             | call record         |  caller's frame, return address, r
stackRoot -> +=====================+
             | local 0, 1, ...     |  _start's frame
             | operands            |
frameBase -> | local 0  (param)    |  callee's frame
             | local 1  (param)    |
             | local 2             |
             | operands            |
sp        -> +---------------------+

frameBase is the address of local 0, localCount the number of locals. local.get i pushes local i, local.set i pops into it, and local.tee i stores the top value without popping it. locals.reserve n adds n locals after the existing ones. They are just the next n words down the stack, so reserve them before pushing anything; they are not cleared. _start has a frame without parameters and may reserve locals too.

Local indices are relative to the current frameBase, so a function sees only its own locals, and a call, recursive or not, leaves the caller's frame intact. Indices are not checked against localCount.

.frame names locals: parameters in parentheses, then reserved locals. .frame ($a, $b) $acc makes $a and $b locals 0 and 1 (filled by call 2, r) and $acc local 2; .frame () $acc has no parameters. Names become indices at translation: local.get $acc is local.get 2. .frame emits no code, so the function still needs locals.reserve, and nothing checks the names against the counts of call or locals.reserve. Names start with $, last until the next label or the end of the section, and mix freely with indices. A malformed .frame or a repeated name is a translation error.

return keeps the top r values and discards the rest of the frame (parameters, locals, leftover operands), the call record and any scope still open. The results replace the parameters on the caller's stack, and the caller continues after call. return outside a function is an error, and br cannot leave a function.

A factorial with n as its parameter and the product in a reserved local:

factorial:
    .frame ($n) $acc                  ; locals 0, 1
    locals.reserve 1                  ; $acc
    i32.const 1 local.set $acc
    block
        loop
            local.get $n i32.const 1 i32.le_s
            br_if 1                   ; n <= 1 -> leave the block
            local.get $acc local.get $n i32.mul
            local.set $acc            ; acc *= n
            local.get $n i32.const 1 i32.sub
            local.set $n              ; n -= 1
            br 0                      ; back to the loop head
        end
    end
    local.get $acc
    return

Since the target is a value, calling a computed address (from a function table, say) uses the same instruction.

example/wasm32/factorial-recursive.s computes the factorial recursively, with if and return.

Besides the common views (pc, mem:dump, io), wasm32 has these, each with :dec (default) or :hex:

stack

The current frame's operands, top first, e.g. 14:14.

locals

The current frame's locals, local 0 first. There is no localCount view; this shows that many words.

sp, frame-base, ctrl-sp, stack-root

The pointers.

cache:scan

The scan cache, most recently used first, each entry as start->end, e.g. 0x02e->0x044, 0x011->0x070.

cache:branch

The branch cache, most recently used first, each entry as from->to, e.g. 0x0e->0x36, 0x32->0x06.

stack:layout

Every frame, oldest first: locals, control records, operands. stack:layout:hex:2 shows only the last two frames.

stack:dump

Memory from sp to the end, by address. Each word appears once, with every frame it belongs to; a frame's locals are grouped, control records decoded, everything else (such as memory above ctrl-sp) raw. stack:dump:hex:2 also limits it to two frames.

stack:tos-regs

The top-of-stack registers, the last pushed first, each as slot=value, e.g. 0xb8=0x00000003, 0xbc=0x00000002.

{stack:layout:hex} at the halt of example/wasm32/frames.s: _start called foo with two arguments, and foo, inside a block, called bar with one:

#0 _start (pc=0x44)
  mem[0x7c..0x7f]: (operands)
    0x7c..0x7f: 0x0000000a (0)
#1 foo (pc=0x15)
  mem[0x70..0x7b]: locals
    0x78..0x7b: 0x0000000b (0)
    0x74..0x77: 0x0000000c (1)
    0x70..0x73: 0x00000001 (2)
  mem[0x80..0x87]: CallScope
    { csCallerFrameBase = 0x7c
    , csCallerLocalCount = 0
    , csReturnPc = 0x44
    , csResultCount = 1 }
  mem[0x88..0x8f]: BlockScope { csEnd = 0x16 }
  (operands): empty, base=0x70
#2 bar (pc=0x25, live)
  mem[0x6c..0x6f]: locals
    0x6c..0x6f: 0x00000001 (0) [frameBase]
  mem[0x90..0x97]: CallScope
    { csCallerFrameBase = 0x78
    , csCallerLocalCount = 3
    , csReturnPc = 0x15
    , csResultCount = 1 }
  mem[0x64..0x6b]: (operands)
    0x68..0x6b: 0x0000000e (0)
    0x64..0x67: 0x0000000e (1) [sp]

• Only i32. Missing: i32.ne, i32.div_u, i32.rem_u, rotations, clz/ctz/popcnt, 16-bit loads and stores, br_table, nop, globals, memory.size/memory.grow.
• No modules, function declarations or types: a function is a label, and call takes its target from the stack (like call_indirect) and its parameter and result counts from the instruction.
• Locals are added at run time by locals.reserve and named by .frame ($n) $acc instead of (param $n i32) and (local $acc i32).
• Scopes have no result types, if is not a branch target, and branches neither unwind nor check the operand stack.
• The stacks live in ordinary memory, readable and writable by the program; sp.init places them.
• A program ends with halt.