Bytecode and Intermediate Representations

Walking a tree is slow because the interpreter keeps hopping between nodes.

Learning Objectives

Explain why runtimes introduce bytecode and how it differs from source and machine code.

Design a virtual instruction set: encoding, opcodes and operands, constant pools, literal loading, local slots, global access, stack versus register bytecode, typed versus untyped and fixed versus variable-width instructions.

Decode instructions, manage the instruction pointer, jumps, labels and relocation; write an assembler, disassembler and serialiser; version bytecode and attach debug metadata.

Verify bytecode and handle malformed modules; relate bytecode to other IRs (SSA, lowering, optimisation passes); explain why bytecode is not automatically portable across versions.

Plain-Language Explanation

Walking a tree is slow because the interpreter keeps hopping between nodes. Bytecode flattens the program into a list of simple numbered instructions — "push constant 0", "push constant 1", "add", "print" — stored in a compact byte array. A virtual machine runs that list very quickly with a loop. The list also includes a table of constants and enough information to report errors at the right source line.

Precise Technical Explanation

Why introduce bytecode?

A linear, compact encoding improves cache locality, removes per-node pointer chasing and repeated type dispatch on tree nodes, can be cached on disk (.pyc, class files), and is a convenient target for verification and JIT compilation.

Bytecode versus source code Source is for people and has nesting and punctuation; bytecode is for a VM, linear, with explicit control flow (jumps) and resolved operands (slot numbers, constant indices).

Bytecode versus native machine code Machine code targets a real CPU's ISA and ABI; bytecode targets an abstract machine and needs an interpreter or compiler to run. Bytecode instructions are usually higher level (CALL handles frames; ADD checks dynamic types).

Virtual instruction set The set of opcodes with precisely defined effects — MiniLang's 30 instructions are listed below.

How an instruction is laid out in bytes. MiniLang: one opcode byte followed by its operands; one-byte operands for indices and counts, two-byte (big-endian) offsets for jumps, and a variable-length operand list for CLOSURE.

Opcodes and operands An opcode names the operation; operands parameterise it (CONSTANT 0 — operand 0 is a constant-pool index).

Literals (numbers, strings, nested function prototypes) are stored once in a per-function table; instructions refer to them by index. Duplicates are merged (MiniLang reuses an existing constant). JVM class files have one constant pool per class containing far more kinds of entries (class, method and field references).

CONSTANT k pushes constants[k]; frequent literals get dedicated opcodes (NIL, TRUE, FALSE; JVM iconst_0…iconst_5, bipush).

Local variable slots Locals are compiled to indices into the current frame (GET_LOCAL 0), so no name lookup happens at run time.

Global variable access Globals stay names (late binding): GET_GLOBAL n looks up names[n] in a global table at run time.

Operands are implicit (top of stack): GET_LOCAL 0; GET_LOCAL 0; MULTIPLY. Compact; easy to compile from trees.

Operands are explicit virtual registers: MUL r0, r1, r1. Fewer instructions, bigger encodings (Module 10).

Typed versus untyped instructions The JVM has typed instructions (iadd, ladd, fadd, dadd) checked by the verifier; MiniLang and CPython have one untyped ADD that checks value types at run time; CIL's add is untyped in encoding but verified by type inference over the stack.

Fixed-width versus variable-width instructions Fixed-width encodings (Lua 5's 32-bit instructions) decode quickly; variable-width (JVM, MiniLang) are compact. CPython ≥ 3.6 uses 2-byte "wordcode" units with EXTENDED_ARG prefixes for large operands.

Read the opcode at the instruction pointer, then its operands according to the opcode's format, then advance.

Instruction pointer / program counter The offset of the next instruction within the current function's code; saved in each call frame.

Jump offsets and branch targets MiniLang jumps encode a 16-bit offset relative to the *next* instruction (JUMP_IF_FALSE forward, LOOP backward); the disassembler shows the absolute target (→ 14).

Labels and relocation A compiler emits a jump before it knows the target, writes a placeholder, and patches it once the label's offset is known (MiniLang's emitJump/patchJump). Linkers do the same across files (relocation).

Turns textual instructions into bytes, resolving labels — useful for tests and hand-written bytecode (the security lab assembles malformed code this way).

Turns bytes back into readable instructions with offsets, operands, constants and source lines — javap -c, dis, MiniLang's disassembleText.

Writing code objects to disk with a header (magic number, version, flags) and constant pools: CPython's marshal-based .pyc files, JVM class files.

Versioning and compatibility Formats carry versions: class files have major/minor versions (Java 21 = 65); .pyc files start with a magic number that changes when CPython's bytecode changes. Runtimes reject formats they do not support.

Source maps / debug metadata Line-number tables map instruction offsets to source lines (MiniLang keeps a line and span per byte; JVM LineNumberTable; CPython's location table); local-variable tables give names to slots for debuggers.

Static checks before execution (MiniLang's verify): valid opcodes, operands within their tables, jumps landing on instruction boundaries, no stack underflow on any path, consistent stack depth where paths merge, no path running off the end. The JVM verifier additionally checks types on the stack.

Invalid instructions and malformed modules Unknown opcodes, truncated operands, out-of-range indices, jumps into the middle of instructions — a verifier rejects them before the VM runs, instead of letting the VM read garbage.

IR versus bytecode IRs serve optimisation inside a compiler (graphs, SSA, rich types); bytecode is an executable, serialisable interchange format. Some formats are both (WebAssembly is validated, compact and compiled further by engines).

SSA (Static Single Assignment) overview In SSA every variable is assigned exactly once; merges use φ-functions (x3 = φ(x1, x2)). SSA makes data flow explicit and simplifies optimisations; JIT compilers convert bytecode into SSA-based IR (Module 16).

Lowering and optimization passes AST → bytecode is one lowering; optimisers then rewrite IR: constant folding, dead-code elimination, peephole rewrites.

Portable versus implementation-specific bytecode JVM bytecode, CIL and WebAssembly are specified portable formats; CPython bytecode, V8's Ignition bytecode and Ruby's YARV instructions are internal implementation formats.

Why bytecode is not automatically cross-version compatible Internal formats change freely between releases (CPython 3.11 rewrote much of its instruction set; 3.12 and 3.13 changed it again), so caches are keyed by version and must be regenerated. Specified formats stay backward-compatible but newer files may use features older runtimes reject.

Example instruction set (specification's illustrative format)

For constants 40 and 2, the stack trace is:

Stack convention of the teaching VM: operands are pushed left to right, so a binary instruction pops the right operand first, then the left, and pushes the result. Other VMs may use different conventions (register VMs name operands explicitly). MiniLang's real bytecode uses the name CONSTANT for CONST; the trace for print(40 + 2); is shown below.

CONST 0        ; push constant #0
CONST 1        ; push constant #1
ADD            ; pop two values and push their sum
PRINT          ; print top value
HALT

Instruction     Stack after instruction
CONST 0         [40]
CONST 1         [40, 2]
ADD             [42]
PRINT           []
HALT            []

Why It Matters in Real Systems

Bytecode is the contract between compilers and runtimes: tooling (debuggers, profilers, coverage, obfuscators, AOP weavers) reads and writes it, and verification is a security boundary.

Key Terms

Opcode / operand Operation code / its parameter Per-function table of literals Offset of the next instruction Patch (backpatching)

Filling in a jump offset once the target is known Checks bytecode before execution IR where each variable is assigned once

Syntax or Instruction Format

MiniLang instruction set (operand kinds: k = constant index, n = global-name index, s = local slot, u = upvalue index, a = argument count — one byte each; j/l = 16-bit forward/backward offset):

push constants[k] NIL / TRUE / FALSE push a literal discard the top value GET_LOCAL / SET_LOCAL read / write local slot s (SET keeps the value) push global names[n] (runtime error if undefined) pop and bind global names[n] assign existing global names[n] GET_UPVALUE / SET_UPVALUE read / write captured variable u EQUAL, GREATER, LESS comparisons (!=, >=, <= compile to these plus NOT) ADD, SUBTRACT, MULTIPLY, DIVIDE arithmetic with runtime type checks logical not, numeric negation print the value if c is falsy, ip += offset (does not pop) call f with a arguments create a closure from function constants[k] capturing (isLocal, index) pairs move a captured local to the heap, then pop return v to the caller end of the script

Complete Example

Control flow compiled to jumps — the course's real compiler and disassembler (offsets, source lines, operands and decoded targets):

Output (MiniLang reference implementation):

The raw bytes behind the listing, and the verifier rejecting hand-assembled malformed bytecode (Node.js 24, using the course's MiniLang module):

Bytecode formats carry versions — CPython's .pyc magic number (CPython 3.13.1; the value differs in other versions):

let i = 0;
while (i < 3) {
  if (i == 1) print("one"); else print(i);
  i = i + 1;
}

== <script> ==
constants: 0 → 0, 1 → 3, 2 → 1, 3 → "one"
names:     0 → i
0000    1 CONSTANT         0    ; 0
0002    | DEFINE_GLOBAL    0    ; 'i'
0004    2 GET_GLOBAL       0    ; 'i'
0006    | CONSTANT         1    ; 3
0008    | LESS
0009    | JUMP_IF_FALSE   31    ; → 43
0012    | POP
0013    3 GET_GLOBAL       0    ; 'i'
0015    | CONSTANT         2    ; 1
0017    | EQUAL
0018    | JUMP_IF_FALSE    7    ; → 28
0021    | POP
0022    | CONSTANT         3    ; "one"
0024    | PRINT
0025    | JUMP             4    ; → 32
0028    | POP
0029    | GET_GLOBAL       0    ; 'i'
0031    | PRINT
0032    4 GET_GLOBAL       0    ; 'i'
0034    | CONSTANT         2    ; 1
0036    | ADD
0037    | SET_GLOBAL       0    ; 'i'
0039    | POP
0040    2 LOOP            39    ; → 4
0043    | POP
0044    | HALT

import { compile, verify, rawScript, OP } from "file:///D:/Projects/EngineerHub/src/cs/tracks/runtimes/minilang/minilang.ts";

const fn = compile("print(40 + 2);").script;
console.log("bytes:", fn.chunk.code.map((b) => b.toString(16).padStart(2, "0")).join(" "));
console.log("constants:", fn.chunk.constants);

const samples = {
  "unknown opcode": rawScript([0xee]),
  "constant index out of range": rawScript([OP.CONSTANT, 7, OP.PRINT, OP.HALT], [1]),
  "jump into the middle of an instruction": rawScript([OP.JUMP, 0, 1, OP.CONSTANT, 0, OP.PRINT, OP.HALT], [1]),
  "stack underflow": rawScript([OP.ADD, OP.HALT]),
  "runs off the end": rawScript([OP.CONSTANT, 0, OP.PRINT], [1]),
};
for (const [label, script] of Object.entries(samples)) {
  const errs = verify(script);
  console.log(`${label.padEnd(40)} → ${errs.length ? errs.map((e) => `offset ${e.offset}: ${e.message}`).join("; ") : "accepted"}`);
}

bytes: 00 00 00 01 0f 15 1d
constants: [ 40, 2 ]
unknown opcode                           → offset 0: unknown opcode 238
constant index out of range              → offset 0: CONSTANT constant index 7 is out of range (pool size 1)
jump into the middle of an instruction   → offset 4: jump target 4 is not the start of an instruction
stack underflow                          → offset 0: ADD needs 2 value(s) on the stack but only 0 can be there (stack underflow)
runs off the end                         → offset 2: execution can run past the end of the code (no HALT/RETURN)

import importlib.util, sys
print(sys.version_info[:3], "pyc magic:", importlib.util.MAGIC_NUMBER.hex())

(3, 13, 1) pyc magic: f30d0d0a

Line-by-Line Explanation

The while loop compiles to: condition, JUMP_IF_FALSE past the body (with a POP on each path because the jump does not pop), the body, and LOOP back to the condition.

if/else compiles to JUMP_IF_FALSE to the else branch and a JUMP over it at the end of the then branch.

i = i + 1; is an assignment *expression* followed by POP (its value is discarded).

Bytes: 00 00 = CONSTANT 0, 00 01 = CONSTANT 1, 0f = ADD (15), 15 = PRINT (21), 1d = HALT (29).

Each malformed sample is rejected by a different verifier rule before any instruction runs.

Step-by-Step Runtime Behavior

With i = 1, EQUAL pushes true, JUMP_IF_FALSE does not jump, POP removes the condition, the then-branch prints one, and JUMP skips the else branch.

Common Misconceptions

"Bytecode is machine code for a fake CPU and therefore slow." It is interpreted or compiled; its design aims for fast interpretation and easy JIT compilation.

"Disassembly output is stable." javap and dis output change with compiler and runtime versions.

"Verification guarantees the program is correct." Only that it is well-formed and safe to execute — it can still divide by zero or loop forever.

Common Bugs and Failure Modes

Off-by-one jump offsets, forgetting to patch a jump, inconsistent stack depth on two paths, operand overflow (more than 256 constants with one-byte operands), stale cached bytecode after an upgrade.

Corrected or Safer Patterns

Centralise jump emission and patching; check limits and report compile errors; verify every compiled chunk in tests; key caches by version.

Debugging and Inspection Techniques

Disassemble after compiling (the course's bytecode compiler explorer shows AST and bytecode side by side); run the verifier in debug builds; diff disassembly between compiler versions.

Performance Considerations

Instruction count, instruction size and dispatch cost trade off; superinstructions and specialised opcodes (Module 25) reduce dispatch.

Security Considerations

Never execute unverified bytecode from untrusted sources; malformed bytecode is a classic attack vector against VMs (Module 24). CPython does *not* verify bytecode — loading untrusted .pyc files or code objects is unsafe.

Portability and Version Caveats

MiniLang's bytecode is a teaching format; CPython's bytecode differs between 3.11, 3.12 and 3.13; JVM bytecode is versioned and backward-compatible.

Real-World Use Cases

Python's .pyc caches, Java class files and JARs, .NET assemblies, WebAssembly modules, Lua's luac output, eBPF programs (verified by the Linux kernel before running).

Best Practices

Document every instruction's stack effect; keep line tables; verify; version the format; write a disassembler before the VM.

Exercises

E1 · Beginner. Write MiniLang bytecode for print(2 * 3); with its constant pool.

Answer: constants 0 → 2, 1 → 3; CONSTANT 0; CONSTANT 1; MULTIPLY; PRINT; HALT.

E2 · Intermediate. Why does JUMP_IF_FALSE not pop its condition in MiniLang?

Answer: So and/or can leave the left operand as the expression's value when they short-circuit; statements like if emit an explicit POP on both paths instead.

E3 · Advanced challenge. Describe how the verifier detects that a program pushes one value on one branch and none on the other before they merge.

Answer: It propagates an abstract stack depth along every control-flow edge; when an instruction is reached a second time with a different depth than recorded, it reports "stack depth differs where paths meet".

Quiz

? What does `CONSTANT 1` do in MiniLang?
+ Pushes the value at index 1 of the current function's constant pool. :: The operand is an index, not a value.
- Pushes the number 1. :: The operand is a pool index.
- Defines a constant named 1. :: There are no constant declarations.
- Jumps to offset 1. :: That would be a jump instruction.

? Why must CPython regenerate .pyc files after an upgrade to a new minor version?
+ Its bytecode is an implementation detail that changes between versions; the magic number detects this. :: Caches are version-specific.
- .pyc files expire after a time. :: They are validated by source timestamp or hash and by magic number.
- Python source changes meaning each version. :: Mostly backward compatible.
- Because .pyc files are machine code. :: They are bytecode.

? Which does a bytecode verifier check? (select all that apply)
+ Jump targets land on instruction boundaries :: Otherwise the VM decodes operands as opcodes.
+ No path underflows the operand stack :: Abstract stack-depth analysis.
- The program terminates :: Termination is undecidable in general.
+ Operand indices are within their tables :: Constant and name indices.

Summary and Key Takeaways

Bytecode is a compact, linear, verifiable instruction format with constant pools, slot-resolved locals, explicit jumps and debug metadata. Specified formats (JVM, CIL, Wasm) are portable and versioned; internal formats (CPython, V8) change freely.