Instruction Set Design

Three concepts: the instruction set as an interface, instruction granularity, and how to decide whether something deserves an opcode.

By the end of this chapter you should be able to look at Ember's opcode table and say, for each entry, why it is there — and, more usefully, why several plausible opcodes are not.

Concept 1: The Instruction Set Is an Interface

1. Concept

An instruction set is the contract between the compiler and the virtual machine. The compiler promises to emit only these instructions, with operands in these ranges, leaving the stack in these shapes. The VM promises to execute them with these semantics.

2. Problem

Without a written contract, the compiler and the VM drift. You add an operand to CALL in the compiler, forget the VM, and get a wrong answer with no error — because a bytecode VM has no type system and no linker to catch the mismatch. The bug surfaces as "recursion returns nil sometimes".

There is a second, larger problem that arrives in Section 5: once you cache compiled bytecode, the instruction set becomes a compatibility surface. A .emberc file written by version 0.3 and loaded by version 0.4 must either work or be rejected loudly. Never silently.

3. Mental model

The instruction set is an API between two halves of your own program, and like any API its value comes from being small, written down, and stable. Every opcode you add is a function you must implement, document, test, disassemble, validate, and support forever.

4. Implementation

The contract has four parts, and Ember writes all four in the opcode reference:

The strongest of those is the second. A documented stack effect that is tested means the compiler and the VM cannot disagree about how many values an instruction consumes — which is the single most common way a bytecode implementation goes subtly wrong.

5. Alternatives

6. Decision

A, with C's verifier for anything not produced by our own compiler in this process.

Lua's position (B) is defensible: it never loads bytecode from an untrusted source in its default configuration, and luac output from a mismatched version is explicitly undefined behavior. Ember takes a stricter line because the stated production profile includes partially-trusted input, and because a validator is one pass and a hundred lines.

Option D is genuinely attractive at scale and the right answer for a thirty-person team. For one crate it is a build-system project competing with the actual work.

7. Tradeoffs

8. Production concerns

• Version the bytecode. A Chunk serialized to disk carries a format version and a hash of the opcode table. Loading a mismatch is an error, never a best-effort. Lua's luac header carries a version byte, a format byte, and a set of size/endianness checks precisely because getting this wrong executes garbage.
• Do not renumber. If Op ever becomes a byte encoding, adding an opcode in the middle renumbers everything after it. Append only. (Ember's Rust enum makes this a non-issue today and a real one the moment you serialize.)
• The debug information is separate from the code. local_names and lines are for humans; execution never reads them. Keeping that boundary means you can strip debug info for size without changing semantics — and it means an attacker-supplied chunk with a corrupt name table cannot affect execution.

9. References

• The JVM Specification, chapter 4 (class file format) and chapter 6 (the instruction set). Read §4.10 on verification even if you read nothing else; it is the most thorough treatment of "how do you trust bytecode" in existence.
• The WebAssembly Core Specification, "Validation" chapter — the same problem, solved thirty years later, much more compactly.
• Lua's lundump.c — the bytecode loader, including its header checks. Note how much of it is "refuse to load anything suspicious."

Concept 2: Granularity — How Much Work Per Instruction

1. Concept

Granularity is how much work one instruction does. ADD does very little. SET_LIST n, off does a bounded amount. A hypothetical SORT_TABLE would do an unbounded amount.

2. Problem

Every instruction costs a dispatch: a fetch, a branch on the opcode, and (in a real CPU) a likely branch misprediction. If instructions are too fine-grained, you pay dispatch overhead for trivial work. If they are too coarse, the instruction set explodes, the VM becomes a pile of special cases, and the compiler cannot express anything the designer did not anticipate.

3. Mental model

Dispatch is a fixed tax per instruction. Granularity is choosing how much work to put behind each tax payment. Too fine and you pay the tax constantly; too coarse and you have written a library, not a machine.

   FINE                                                          COARSE
   ────                                                          ──────
   ADD           GET_FIELD         CALL          SET_LIST      SORT_TABLE
   ~1 dispatch   ~1 dispatch +     frame setup   n stores      unbounded
   per operation hash lookup       + jump        1 dispatch    → NOT an opcode

4. Implementation

Ember's rule, stated once and applied everywhere:

An operation gets an opcode if it is (a) a primitive of the language, (b) a bounded amount of work, and (c) something the compiler can identify statically.

Applying it:

That last row is the interesting one. ADD_INT fails test (c) in a dynamically-typed language, which is exactly why fast dynamic runtimes need profiling rather than just a bigger instruction set. Static languages get this for free: the JVM has iadd, ladd, fadd, and dadd as four separate opcodes, because javac knows the types. Ember's ADD is a decision tree because it cannot.

javap -c YourClass.class | grep -E 'iadd|dadd|ladd'   # four opcodes, chosen at COMPILE time

5. Alternatives

6. Decision

B now; C and D are Section 7, gated on benchmarks.

The discipline that matters is not which philosophy you pick — it is refusing to add opcodes on intuition. Every opcode Ember has is either a language primitive or has a stated reason in the reference. When Section 7 adds ADD_INT, it will arrive with a baseline, a hypothesis, and a measurement.

7. Tradeoffs

8. Production concerns

• Unbounded work inside one instruction defeats the instruction budget. The budget ticks once per fetch, so an opcode that could run for a second is a hole in the sandbox. That is the real reason SORT_TABLE is not an opcode: it is not about taste, it is that the budget lives in the fetch position and only bounded instructions respect it. Library functions get charged separately, in Section 5.
• SET_LIST n is bounded by an operand, which is fine, but n is attacker-controlled. A chunk claiming SET_LIST 65535 must be validated against the actual stack depth, or the VM reads out of bounds. Validator rule 9.
• Opcode count affects cache behavior. A dispatch match over 44 arms compiles to a jump table that fits in cache; over 400 it may not. This is a real effect and it is a reason to be conservative even when an opcode looks free.

9. References

• PEP 659, Specializing Adaptive Interpreter — option D, argued carefully, with the rationale for why CPython did not just add more static opcodes.
• The Lua 5.4 opcode list, lopcodes.h. Note OP_ADDI, OP_ADDK, OP_MMBIN: Lua added specializations for "add an immediate" and "add a constant" in 5.4 — options C and B, chosen by measurement.
• Ertl & Gregg, The Structure and Performance of Efficient Interpreters (2003), on superinstructions and dispatch cost. The paper that quantifies the tax.

Concept 3: Deriving Ember's Instruction Set

1–3. Concept, problem, mental model

Start from the language, not from a list of opcodes you have seen elsewhere. Every construct in the grammar must compile to something. Walk the grammar; for each production ask "what instruction does this need?"; only then look at what other VMs did, and only to check whether you missed something.

4. Implementation — the derivation, in order

Forty-four opcodes, and every one traces to a line of the grammar. That table is the design document, and if you cannot produce it for your own instruction set you have not designed one, you have collected one.

5–7. Alternatives, decision, tradeoffs

Two opcodes in that list are not forced by the grammar and are worth defending individually, because they are the only judgment calls:

• SELF_FIELD. t:m(a) could compile as GET_FIELD m plus a duplicated t. But Ember has no DUP opcode, and adding one to serve a single construct is worse than a specialized instruction that also documents its intent. It also guarantees t is evaluated once, which a naive desugaring in the parser would not.
• SET_LIST. {1, 2, 3} could be three SET_INDEXes. SET_LIST turns n dispatches into one and, more importantly, avoids pushing n copies of the table. Lua has OP_SETLIST for the same reasons.

Both would be reasonable to omit. Note them in ADR-002 as the two opcodes you would cut first if the set ever felt too big — an ADR that records what you would undo is unusually useful.

8. Production concerns

The instruction set constrains the language, not the other way round. Two examples you will meet:

• Ember has no goto because it has no opcode for "jump into a scope while closing the right upvalues", and adding one means the validator must prove the jump is legal. Lua 5.4 does have goto, and its parser carries a pile of machinery (gotostat, createlabel, undefgoto) to enforce "you may not jump into the scope of a local." That machinery is the actual cost of the feature.
• Ember has no coroutines because a coroutine needs multiple call stacks, which is a VM structure decision, not an opcode. That is why it is a capstone project rather than a lab: it changes the machine, not the instruction set.

9. References

rg -n 'OP_[A-Z]+' lopcodes.h | head -90        # Lua's 83, with their A/B/C operand modes
python3 -c "import opcode; print(len(opcode.opname))"

• lopcodes.h in Lua, with the comment block at the top describing each instruction's semantics in pseudo-C. That comment block is Lua's version of this page and it is excellent.
• CPython's Include/opcode.h and Doc/library/dis.rst.
• The Dalvik bytecode reference, for a register machine's answer to the same grammar.

Things to Notice

• An instruction set is an API between two halves of your own program, and it becomes a compatibility surface the moment you cache it.
• Every opcode has a fixed dispatch tax. Granularity is deciding how much work to put behind each payment.
• The JVM has four add opcodes and Ember has one, and the difference is entirely that Java knows types at compile time. That single observation explains why dynamic languages need profiling and speculation to get fast, and it is the thread that runs through Section 7.
• Unbounded work inside one instruction is a sandbox hole, not just a design smell. The budget ticks per fetch.
• Derive the set from the grammar. If you cannot produce the grammar-to-opcode table, you collected an instruction set instead of designing one.
• The instruction set constrains the language. goto and coroutines are missing from Ember for reasons that live at this layer.

Validation / Self-check

1. Name the four parts of the instruction-set contract and what enforces each in Ember.
2. What is the dispatch tax, and how does granularity relate to it?
3. Give Ember's three-part test for "does this deserve an opcode?" and apply it to table.sort, generic for, and ADD_INT.
4. Why does the JVM have iadd, ladd, fadd, and dadd while Ember has one ADD? What does that force Ember to do later?
5. Why is an unbounded-work opcode a security problem and not merely inelegant?
6. Which two of Ember's opcodes are not forced by the grammar? Defend each, then argue for cutting it.
7. Why does Ember have no goto? Name the specific machinery Lua needs for it.
8. What must a serialized Chunk carry, and what should happen on a mismatch?

Next: Stack vs Register.