Chapter 10: Designing the instruction set

This chapter:

• Choose a stack machine over a register machine for Muspel's bytecode, and defend the choice.
• Design the instruction encoding: opcode byte, fixed-width operands, a constant pool.
• Write opcodes.odin, the single-source-of-truth table every later chapter extends.
• Write a first-cut disassembler and prove the format is sound with a hand-assembled program, before any compiler exists to generate one automatically.

Where we left off: Chapter 9 measured, concretely, why the tree-walker is slow. This chapter stops explaining the destination and starts building the road there: bytecode, not yet a compiler to produce it or a VM to run it, just the format itself.

10.1 Stack machine or register machine

This is the most consequential design decision the whole book makes, and it's worth stating plainly before a single opcode is named.

Design decision: a stack machine, not a register machine. Alternatives considered: a register-based VM, in the style of Lua 5.x's own bytecode (instructions that name their operands' locations directly, ADD r1, r2, r3, rather than implicitly operating on whatever's on top of a stack). Trade-off: a register machine can be meaningfully faster: fewer instructions per expression (no separate PUSH for every operand), and no redundant stack traffic for values that are about to be consumed immediately. The cost is a real compiler-engineering problem a stack machine never has to solve at all: register allocation, deciding which of a fixed (or virtual, spill- to-stack) set of registers holds which live value at every point in a function, correctly, across arbitrarily nested expressions and control flow. That's a legitimately hard problem on its own, one Lua's own implementation spends real, dedicated code on, and it's out of proportion to what an embedded game-scripting language needs. Choice: a stack machine. Every instruction operates on an implicit value stack: push operands, pop them, push the result. Compiling an expression is almost mechanical (post-order: compile the children, then emit the operator), which is exactly why Chapter 11's compiler is as short as it is. The cost, some redundant push/pop traffic a register machine would have optimised away, is real and worth naming, not hidden: it's the read half of section 9.4's honest "fast enough, not fastest possible" promise, paid here specifically.

10.2 Instruction encoding

Every instruction is one opcode byte, followed by zero or more fixed-width operand bytes: a u8 for a constant-pool index, a local slot, or an argument count, or a signed i16 for a jump offset. op_operand_bytes is the one place that width is recorded:

op_operand_bytes :: proc(op: Op_Code) -> int {
	#partial switch op {
	case .Constant, .Get_Local, .Set_Local, .Get_Global, .Set_Global, .Define_Global, .Call:
		return 1
	case .Jump, .Jump_If_False:
		return 2
	case:
		return 0
	}
}

A more compact, variable-width encoding (distinguishing "small index fits in one byte" from "needs two") would save space on larger programs, at the cost of every consumer of the bytecode, the compiler emitting it, the disassembler reading it back, the VM dispatching it, needing to agree on a more complicated decoding rule. Fixed width loses that space but means offset + 1 + op_operand_bytes(op) is always the next instruction's offset, a one-line invariant the disassembler (section 10.8) and the VM's own dispatch loop (Chapter 13) can both lean on without duplicating any decoding logic between them.

10.3 The constant pool

Literals, numbers and strings, are referenced by index into a per-chunk constant pool, rather than embedded inline in the instruction stream:

Const_Value :: union {
	f64,
	string,
	^Func_Proto,
	^Struct_Layout,
}

Chunk :: struct {
	code:      [dynamic]u8,
	constants: [dynamic]Const_Value,
	lines:     [dynamic]int,
}

(^Func_Proto, a compiled function, joins the union in Chapter 12; ^Struct_Layout is this chapter's own addition, section 10.7. Both are shown here because opcodes.odin is where the union lives for the rest of the book, not because every chapter that touches this file uses every case yet.)

Two things worth noticing about the name Const_Value, deliberately not Value. First, this book already has one runtime value type, the tree-walker's own Value (Chapter 8), and this isn't it: a constant-pool entry is a compile-time literal, not a running value with the full range a script's expressions can produce. Second, and more important: naming it distinctly now is what lets Chapter 13 introduce the real VM value type under the name Value without a collision, at the point where the tree-walker's own throwaway types finally get renamed out of the way (Chapter 13 says exactly when and why).

Booleans and nil don't need a pool slot at all, Nil/True/False are their own zero-operand instructions (section 10.4), pushing their value directly. A u8 constant index caps a chunk at 256 constants, a real, named limit rather than a hidden one: wider encodings exist and this book isn't using one, because no example or Embers script needs more literals than that in one function.

10.4 The opcode table

Every instruction Muspel needs through Chapter 15, grouped, documented once here and never silently changed elsewhere:

YIELD (Chapter 15) belongs in this table too, chronologically; section 15.4 introduces it alongside the resumable VM it exists for, rather than here where it would have nothing yet to demonstrate.

An enum member needs no opcode of its own at all: Phase.Attacking compiles straight to CONSTANT with its resolved integer tag (Chapter 11), reusing machinery this table already has, the direct payoff of Chapter 5's decision to keep enum members payload-free.

SET_LOCAL/SET_GLOBAL leave the assigned value on the stack rather than popping it, which is what makes assignment usable as an expression (x = y = 1, or an assignment whose result is itself printed); an assignment used as a bare statement gets an explicit trailing POP from the compiler, the same way any other expression statement does.

JUMP_IF_FALSE is worth dwelling on, because it's the one entry in this table that looks like it should pop and doesn't. It peeks: the tested value stays on the stack whether or not the jump is taken. Chapter 11 leans on this directly, twice: an if/while's own condition needs an explicit POP on both branches (this chapter's disassembly in section 10.8 doesn't show one yet, there's no compiler to emit it), and &&/||'s short-circuit evaluation needs the left-hand value to still be there, ready to become the whole expression's result, exactly when the jump is taken.

10.5 Resolving Chapter 5's deferred question: an arena per VM instance

Chapter 5 named a question it couldn't yet answer: where does a struct instance actually live? The tree-walker (Chapter 8) ducked it, Odin's own heap, values never reclaimed, a stepping stone's honest simplification. The bytecode VM (Chapter 13) is where the question finally has a real answer, because it's the first thing in this book with a well-defined instance lifetime to hang the answer on.

Design decision: a bump-allocated arena, one per VM instance, never a general-purpose heap. Alternatives considered: a general-purpose heap with reference counting or a tracing garbage collector, the way most dynamically-typed scripting languages manage struct and array values. Trade-off: a general heap can reclaim an individual object's memory the moment nothing references it any more, real flexibility a long-running program with unpredictable object lifetimes genuinely needs. The cost is real, ongoing bookkeeping: every reference counted or traced, a cycle-detection problem if references can form loops, and, in most implementations, unpredictable pause times exactly when a script's timing matters most, mid-frame. A bump allocator has none of that cost, and also none of that flexibility: it can never free a single object early, only every object it's ever allocated, all at once. Choice: the arena, because Chapter 17 gives every VM instance exactly the short, well-defined lifetime (one instance per scripted entity, destroyed when the entity dies) that makes "free everything at once, at one well-defined point" both correct and cheap. Allocating is "bump the arena's offset and return a slice," an O(1) operation with no allocator metadata to maintain; tearing an instance down is one call, mem.arena_free_all, reclaiming its entire struct/array population in one step, no per-object trace, no reference count, no cycle check, because nothing is ever freed except everything at once. This is exactly the trade Odin's own context.temp_allocator makes at a smaller scale (bump-allocate freely, reset the whole arena at a well-defined boundary), applied here to a scripting VM's entire struct/array value lifetime instead of one frame.

// Value_Arena is every struct and array a single VM instance ever creates, in one bump-allocated
// buffer. core:mem's own Arena (a plain buffer-backed bump allocator, no OS virtual memory) is
// reused rather than hand-rolled, and works identically on every target this book's code runs on,
// native or js_wasm32 alike.
Value_Arena :: struct {
	buf:   []byte,
	arena: mem.Arena,
}

value_arena_init :: proc(a: ^Value_Arena, allocator := context.allocator) {
	a.buf = make([]byte, Value_Arena_Size, allocator)
	mem.arena_init(&a.arena, a.buf)
}

value_arena_reset :: proc(a: ^Value_Arena) {
	mem.arena_free_all(&a.arena)
}

The cost, named honestly rather than hidden: a struct or array can never be freed early to reclaim memory mid-script, and a script that allocates unboundedly inside one long tick can exhaust its instance's arena entirely. That's a real new failure mode, and this chapter only names it; Chapter 18's fault isolation is where MAKE_STRUCT/MAKE_ARRAY actually check remaining arena space and turn exhaustion into a recoverable script-level error instead of letting it happen unguarded.

10.6 Struct values in bytecode: field access by name, not by static index

The tidy version of this story, and the one worth naming even though it isn't quite what gets built, would give every struct field a fixed, compile-time-known index, and make GET_FIELD as cheap as GET_LOCAL, an operand that's already the exact slot to read. That version needs one more thing Muspel doesn't have: a static type system tracking which struct type a variable holds, so that enemy.pos.x can be proven, before running anything, to mean "index 0 of whatever Vec2 instance enemy.pos evaluates to." Chapter 7 was explicit that this pass stops short of that: it validates a struct literal's keys against its own declared type, but it does not trace a variable's type through the rest of the program.

*Design decision: GET_FIELD/SET_FIELD take a field name, resolved at run time against the instance's own field table, not a compile-time index. Alternatives considered: a full static type system, inferring or tracking every expression's struct type through assignment and control flow, precisely enough to resolve every .field access to a fixed index ahead of time. Trade-off: static field indices would make field access exactly as cheap as a local slot read, and would catch a field-name typo on any* struct-typed expression, not just a fresh literal. Building it is a genuinely large, separate project, the kind of thing a from-scratch language usually earns its own book; it's named in the preface's own "where to go next" list for a reason. Choice: every struct instance already carries its own type's field-name table (shared, read-only, across every instance of that type, exactly like Struct_Layout below). GET_FIELD takes a field name as a constant-pool string operand and scans that table at run time, the same by-name lookup Chapter 8's tree-walker already does. It costs a linear scan over a small, fixed-size list, not a single array index, a real but small price for structs with the handful of fields any of this book's examples ever declare, and it's honest about being a "good enough" answer rather than the theoretically fastest one.

MAKE_STRUCT's own operand is a Struct_Layout constant, not a raw field count: it has to carry enough information to route each pushed value to the right slot, since Chapter 5's keyed literals let a script provide fields in any order, or omit one entirely.

// Struct_Layout is Make_Struct's own constant-pool payload: the declaring struct's full field
// order (shared by every instance of this type) and, for this one literal, which pushed value
// lands at which field index. An omitted field has no entry pointing at it and is left nil.
Struct_Layout :: struct {
	type_name:     string,
	field_names:   []string,
	field_indices: []int,
}

10.7 Array values in bytecode

Arrays need less new machinery than structs: no keyed construction, no name-based field lookup, just a fixed-length run of values and a length. MAKE_ARRAY's u8 operand is a plain element count; GET_INDEX/SET_INDEX take no operand at all, since an array index, unlike a struct field, is a runtime value, already sitting on the stack as whatever expression computed it, not a compile-time constant the instruction could bake in. Both perform the bounds check Chapter 6 promised as a language guarantee, turning an out-of-range index into a recoverable error rather than an Odin-level out-of-bounds read; Chapter 13 shows exactly what that looks like once a real VM exists to fail gracefully in.

10.8 A first-cut disassembler

Before any compiler exists to generate bytecode automatically, the format itself needs proving: hand-assemble a chunk, byte by byte, and read it back correctly.

disassemble_instruction :: proc(c: ^Chunk, offset: int) -> int {
	op := Op_Code(c.code[offset])
	line := c.lines[offset]
	// ... print one line per instruction, decoding operand bytes per op_operand_bytes(op) ...
	return offset + 1 + op_operand_bytes(op)
}

musc asm-demo builds (1 + 2) * 3 directly, with no .mus source and no compiler involved at all, just Chunk, chunk_write_op, and chunk_add_const called by hand:

./run.sh asm-demo

== (1 + 2) * 3 ==
0000 0001 CONSTANT       0000 '1'
0002 0001 CONSTANT       0001 '2'
0004 0001 ADD
0005 0001 CONSTANT       0002 '3'
0007 0001 MUL
0008 0001 RETURN

Every offset advances by exactly 1 + op_operand_bytes(op), every constant-pool index resolves back to the literal it was given, and the whole thing reads, left to right, exactly like the arithmetic it represents. That agreement is the entire point of this chapter: the format is sound on its own terms, checked by hand, before Chapter 11 ever writes a line of code that generates one of these automatically.

Checkpoint

opcodes.odin compiles, documents every instruction Part III-IV needs through Chapter 15 in one table (including MAKE_STRUCT/GET_FIELD/SET_FIELD and MAKE_ARRAY/GET_INDEX/SET_INDEX), arena.odin gives the design behind those new opcodes' allocations a name, and musc asm-demo proves the encoding round-trips correctly for a hand-assembled program, with no compiler and no VM anywhere in the loop yet.

Exercises

1. Hand-assemble a chunk for -(4 - 1) (a NEGATE wrapped around a SUB) and disassemble it. Work out the expected constant pool and byte offsets on paper first, then check musc asm-demo (modified to build your chunk) against your prediction.
2. Op_Code.Dup is in the table but nothing in this chapter uses it yet. Skim ahead to Chapter 15's wait/wait_until library functions and section 10.4's comparison operators, and guess which future construct might need to duplicate a value it's about to consume twice. (You don't need to be right, the point is forming a real guess before the answer arrives.)
3. Explain, in your own words, why JUMP_IF_FALSE peeking instead of popping is what makes && able to leave its left operand as the whole expression's result when that operand is falsy. Section 10.4's last paragraph is a hint, not the answer.
4. Section 10.3 caps the constant pool at 256 entries per chunk via a u8 index. Sketch (in words, no code required) what would have to change, in chunk_add_const, in op_operand_bytes, and in every consumer of a CONSTANT instruction's operand, to lift that to 65536 entries. Is it a bigger change than it first looks?
5. Hand-assemble a MAKE_STRUCT call for a two-field struct, providing both fields, and disassemble it; then do the same providing only one, and confirm the Struct_Layout you built by hand has one fewer entry in field_indices than field_names.
6. Section 10.6's Design decision names the cost of by-name field lookup as "a linear scan over a small, fixed-size list." Sketch, on paper, what Struct_Layout (and GET_FIELD's own operand) would need to look like instead if every struct field access really were a compile-time index, and identify the one fact about a running program that a resolver would need to track, and currently doesn't, to make that safe in general.

Further reading

• Crafting Interpreters, Chunks of Bytecode, the direct model for this chapter's Chunk, constant pool, and fixed-width operand encoding: https://craftinginterpreters.com/chunks-of-bytecode.html
• Lua's own register-based VM design, the real prior art section 10.1's Design decision is declining: the Lua 5.0 implementation paper, "The Implementation of Lua 5.0" by Ierusalimschy, de Figueiredo and Celes, is the primary, freely available source.
• Wren's bytecode design notes, a small, production, stack-based embeddable language making close to the same choice this chapter makes, for closely related reasons: https://wren.io/performance.html