Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 61 ยท Code Generation and Runtimes

Bytecode and Virtual Machines

Design a bytecode instruction set, compile an AST to it and run it on a stack-based virtual machine in Python, then compare it with CPython's own dis output.

A real CPU only understands its own machine code. A virtual machine (VM) is a program that pretends to be a computer with a simpler, friendlier instruction set. The instructions of that imaginary computer are called bytecode, and a compiler can translate your language into it just as it would translate to x86 or ARM. Instead of running the result on silicon, you run it in a loop inside the VM.

This is how Java (the JVM), Python (CPython), C# (the CLR), Lua and WebAssembly work. Bytecode is compact, runs the same on every operating system, is much faster to execute than walking a syntax tree, and is far easier to generate than real machine code. In this lesson you will design a small instruction set, write a compiler that turns an AST into it, build the VM that runs it, and finally look at Python's own bytecode for comparison.

Why a stack machine?

As the lesson on intermediate representations explains, a bytecode can be stack-based or register-based. Most teaching VMs, the JVM and CPython use a stack. Operands are pushed onto an operand stack, and each instruction pops its inputs and pushes its result. No instruction names a register, so instructions are short and the compiler is easy to write.

To evaluate (2 + 3) * 4 you push 2, push 3, add (pop two, push 5), push 4, multiply. The compiler produces this order with a simple post-order walk of the AST: compile the left operand, compile the right operand, then emit the operator. The operands always find themselves on top of the stack, in the right order.

Designing the instruction set

An instruction is an opcode (which operation) plus, for some opcodes, an operand (a constant, a variable slot or a jump target). Think of the set as a few families:

Family Instructions Stack effect
Constants PUSH n pushes one value
Variables LOAD i, STORE i LOAD pushes one, STORE pops one
Arithmetic ADD, SUB, MUL pops two, pushes one
Comparison LT pops two, pushes a truth value
Control flow JUMP t, JUMP_IF_FALSE t JUMP_IF_FALSE pops one
Output and control PRINT, HALT PRINT pops one

The stack effect of every instruction is fixed and known at compile time. That allows the compiler to compute the maximum stack depth a function needs and lets a verifier (as in the JVM) prove that bytecode never pops from an empty stack. It is a good habit to write the effect next to each opcode in your design notes.

Run the first machine by hand-writing a program in its instruction set. The trace prints the stack after every instruction.

Python A tiny stack machine, traced

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop at the heart of run is called the dispatch loop: fetch the instruction at the program counter pc, advance the counter, decode the opcode, perform the operation. Every VM has one. Notice the order in SUB: the right operand is on top of the stack, so you pop b first and a second. Getting this wrong makes 10 - 3 evaluate to -7, and it is the most common first bug in a stack VM.

Compiling an AST to bytecode

Expressions are the easy part. A number compiles to PUSH, a variable to LOAD, and a binary operation to left, right, operator. Every expression leaves exactly one value on the stack. A statement leaves the stack as it found it: an assignment compiles its expression and then STOREs the result, and print ends with PRINT.

Control flow is handled with jumps. A while loop becomes a test at the top, a conditional jump out of the loop, the body, and an unconditional jump back to the test.

flowchart TD
    A["top: evaluate the condition"] --> B{"JUMP_IF_FALSE exit"}
    B -->|"true: fall through"| C["loop body"]
    C --> D["JUMP top"]
    D --> A
    B -->|"false: jump"| E["exit: code after the loop"]

A while loop in bytecode: one conditional jump leaves the loop, one unconditional jump returns to the test.

There is one wrinkle. When you emit JUMP_IF_FALSE, you do not yet know where exit will be, because the body has not been compiled. The standard solution is backpatching: emit the jump with a placeholder, remember its index, and fill in the real target after the body is done. You will see it in the code below, together with a simple assembler that turns instructions into raw bytes and a disassembler that turns them back into readable text.

Python Compile, assemble and run a loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop sums the squares 1, 4, 9, 16 and 25 and prints 55. Read the disassembly next to the diagram: instruction 7 is the conditional exit (its target, 19, is the first instruction after the loop), and instruction 18 jumps back to 4, the start of the condition. The program is 44 bytes: 22 instructions of two bytes each. The first twelve bytes shown are [0, 0, 2, 0, ...], which decode as PUSH 0 and STORE 0. This is a real, if tiny, executable format.

Making the dispatch loop fast

The if/elif chain above is simple but slow, because it compares the opcode with every name in turn. Real VMs avoid that:

  • Switch dispatch. In C, a switch over a dense range of opcode numbers compiles to a jump table, so decoding takes one indirect jump.
  • Threaded code. Each instruction handler ends by jumping straight to the next handler (using computed goto in GCC and Clang) instead of returning to the top of the loop. This helps the CPU's branch predictor, because each handler gets its own jump.
  • Superinstructions. If two instructions often appear together, merge them into one. This saves a dispatch and is one reason bytecode sets keep growing.
  • Caching. Instructions such as attribute lookups remember the result of the previous execution and reuse it when nothing changed.

The cost of interpretation is mostly this per-instruction overhead: fetch, decode, branch. That is why JIT compilers translate hot bytecode into machine code and skip the dispatch altogether.

Python's own bytecode

CPython compiles every function to bytecode and keeps it in the function's code object. The dis module shows it. Run the next example and compare it with the design above: the function f(a, b) returns a * b + 1000.

Python Peek at CPython's bytecode with dis

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can recognize the same ideas. LOAD_CONST is our PUSH, BINARY_OP is a single instruction for all arithmetic with the operator as its argument, and RETURN_VALUE ends the function. The co_consts and co_varnames tuples are the constant pool and variable table. co_stacksize is the maximum stack depth the compiler computed, which is exactly the stack-effect bookkeeping from the design table. The loop in g uses a conditional jump to leave and a backward jump to repeat, the same shape as our diagram.

Two details differ from our toy. The first instruction, RESUME, is a marker the interpreter uses for its own bookkeeping. And the first load, which fetches both a and b in one instruction, is a superinstruction. The code size is larger than six instructions at two bytes because CPython reserves inline cache slots after some instructions. Instruction names and details change between Python versions, so treat the printed names as a snapshot of the interpreter that runs here, not as a stable API.

Bytecode in other systems

System Machine model Notable feature
JVM stack-based, typed instructions (iadd, fadd) a verifier checks stack safety before running
CPython stack-based adaptive instructions that specialize at run time
Lua register-based fewer, wider instructions
WebAssembly stack-based, structured control flow designed to be validated and compiled fast
.NET CIL stack-based compiled to machine code at load time

Register VMs, such as Lua's, name their operands inside the instruction (ADD r1, r2, r3), so they need fewer instructions but each one is wider. Neither style is always faster; the best choice depends on the language and on how the VM will be optimized.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A stack VM executes ADD. What does it do?

    ADD has the stack effect pop two, push one. The operands were pushed earlier by the code compiled for the left and right sub-expressions.
  2. 2. In which order does the compiler emit code for the expression a - b?

    A post-order walk emits the left operand, then the right operand, then the operator, so the VM pops b first and a second.
  3. 3. Why does the compiler use backpatching for the exit jump of a while loop?

    When JUMP_IF_FALSE is emitted, the instructions after the loop do not exist yet. The compiler leaves a placeholder and writes the real address afterwards.
  4. 4. What is a superinstruction?

    Merging frequent pairs of instructions saves dispatch work. CPython's combined local-variable loads are an example.

Summary

  • Bytecode is the instruction set of a virtual machine; a compiler can target it like any other machine.
  • A stack machine pops its operands and pushes its result; a post-order walk of the AST produces the right order.
  • Expressions leave one value on the stack, statements leave the stack unchanged, and loops and conditionals compile to jumps fixed by backpatching.
  • The dispatch loop (fetch, decode, execute) is the core of every VM; switch dispatch, threaded code and superinstructions make it faster.
  • CPython's dis module shows a real stack bytecode with constants, variable tables and a computed stack depth.

Next: Interpreters, JIT and Ahead-of-Time Compilation