Bytecode & Codegen

Bytecode is the IR flattened into machine-shaped instructions — small, uniform, and trivially executable by a VM. This chapter covers deciding the instruction set, emitting it from your IR, and keeping it correct.

Instruction Sets

Two families dominate; DSLs start with the first.

Stack machine: PUSH 1 PUSH 2 ADD with the operand stack evolving

Figure 1 — Stack bytecode has no operands in instructions; the stack carries them.

Stack Machines

Instructions like PUSH 1; PUSH 2; ADD need no destination register — operands come from an evaluation stack. Tiny, uniform, and perfect for a first VM.

Register Machines

Instructions name operands explicitly (ADD r1, r2, r3); closer to hardware, faster per instruction, but the emitter must allocate slots. A later optimization for DSLs that outgrow the stack model.

The Minimal Instruction Family

You can express almost any DSL with: constant loads, stack arithmetic, LOAD/STORE for names, CALL/RET, and JUMP*/IF* for control flow. Start with these; grow only when measured.

Emitting Bytecode

From IR to Opcodes

Walk the three-address IR once: each statement becomes one or two instructions, expressions become push-pop sequences, and names become slot indexes resolved during the Semantic Analysis chapter (look them up, never by string).

Constant Pools and Labels

Pack literals into a constants table (bytecode stores indexes, not text) and record jump targets as labels resolved in a final pass. Two small tables keep instructions tiny and the emitter simple.

The Disassembler Is the Docs

Ship a dis() that prints each instruction with its resolved data. It is the debugging window from Crafting Compilers, and it makes every bytecode discussion concrete.

Correctness

Stack Discipline

Every opcode’s stack effect is part of its contract (ADD pops 2, pushes 1). A verifier that simulates stack height over the whole program catches emitters that produce unbalanced code — before users ever run it.

Verification Step

Run the verifier as part of the build test lane: corrupted bytecode from a buggy emitter fails fast and loudly, keeping the VM free to assume well-formed programs.

Example: Emitting 1 + 2 * 3

From the three-address IR of the interest chapter to an instruction list, in one commented walk. Like the rest of this track, the emitter is written in Python because it reads clearly for everyone — a production toolchain would emit from a grammar-generated tree (ANTLR) or from a type-safe compiler core (OCaml, Racket), covered in the DSL Implementation Languages phase.

emit.py (commented)

# emit.py — IR to bytecode for the mini-language
def emit_arith(node, out):
    # postorder: children first -> stack operands in the right order
    emit(node.left); emit(node.right)
    out.append(token_of(node.op))       # ADD / SUB / MUL -- the one opcode

def emit(node, out=[]):
    if node.kind == "num":   out.append(("PUSH", node.value)); return out
    if node.kind == "binop": emit(node.left); emit(node.right)
                            out.append(("OP", node.op));   return out
    raise SyntaxError(node.kind)

# example: 1 + 2 * 3  ->  [PUSH 1, PUSH 2, PUSH 3, OP mul, OP add]

How to Read It

Postorder traversal means every operand is on the stack before its operator fires — precedence ended up in the tree (Parsing & Trees), so the emitter can be this dumb.

Next Steps

Continue Phase 2

Bytecode needs a machine: Virtual Machines & Runtimes executes and services it. Later, Code Generation does the same job natively.

Resources