Generating code for a stack machine

Advanced

Introduction

The back end of a compiler turns the program into instructions for a target. Two families of target are common. Register machines such as x86 and ARM keep values in a few named registers. Stack machines keep them on a stack: ADD pops two values and pushes their sum. The Java virtual machine, CPython, .NET and WebAssembly are all stack machines, because their code is easy to generate and compact. In the first lesson you compiled arithmetic to stack code; this lesson adds variables, loops and conditions.

How it works

The instruction set used here:

InstructionEffect
PUSH npush the number n
LOAD x / STORE xpush the value of x / pop a value into x
ADD, SUB, MUL, LESSpop b, pop a, push a op b (LESS pushes 1 or 0)
PRINTpop a value and print it
JUMP acontinue at address a
JUMP_IF_FALSE apop a value; if it is 0, continue at address a

Expressions compile in post-order, exactly as before: the code for the left operand, the code for the right, then the operator. Names become LOAD. Assignments compile the expression and then STORE the result; print compiles the expression and then PRINT.

A while loop becomes:

start:  code for the condition
        JUMP_IF_FALSE end
        code for the body
        JUMP start
end:

The trouble is that when the compiler emits JUMP_IF_FALSE, it does not yet know where the loop ends. The solution is backpatching: emit the jump with a blank address, remember its position, and fill the address in when end is reached. The backward JUMP start is easy, because the start address was recorded when the loop began. An if uses the same idea with one forward jump.

The virtual machine is a loop around a program counter: fetch the instruction at pc, move pc on by one, and carry it out. A jump just sets pc to a new value.

Syntax

start = len(code)                     # where the loop begins
gen(condition)
jump = emit("JUMP_IF_FALSE", None)    # target unknown yet
...body...
emit("JUMP", start)
code[jump][1] = len(code)             # backpatch: the loop ends here

Example

import re


def parse(tokens):
    pos = 0

    def peek():
        return tokens[pos] if pos < len(tokens) else None

    def take():
        nonlocal pos
        pos += 1
        return tokens[pos - 1]

    def compare():
        node = arith()
        while peek() == "<":
            node = (take(), node, arith())
        return node

    def arith():
        node = term()
        while peek() in ("+", "-"):
            node = (take(), node, term())
        return node

    def term():
        node = atom()
        while peek() == "*":
            node = (take(), node, atom())
        return node

    def atom():
        token = take()
        if token == "(":
            node = compare()
            take()
            return node
        return token

    return compare()


def compile_program(lines):
    code, blocks = [], []

    def emit(*instruction):
        code.append(list(instruction))
        return len(code) - 1

    def gen(node):
        if isinstance(node, str):
            if node.isdigit():
                emit("PUSH", int(node))
            else:
                emit("LOAD", node)
            return
        op, left, right = node
        gen(left)
        gen(right)
        emit({"+": "ADD", "-": "SUB", "*": "MUL", "<": "LESS"}[op])

    for line in lines:
        tokens = re.findall(r"\d+|\w+|\S", line)
        if tokens[0] == "while":
            start = len(code)
            gen(parse(tokens[1:]))
            blocks.append((start, emit("JUMP_IF_FALSE", None)))
        elif tokens[0] == "end":
            start, jump = blocks.pop()
            emit("JUMP", start)
            code[jump][1] = len(code)
        elif tokens[0] == "print":
            gen(parse(tokens[1:]))
            emit("PRINT")
        else:
            gen(parse(tokens[2:]))
            emit("STORE", tokens[0])
    return code


def run(code):
    stack, memory, pc, steps = [], {}, 0, 0
    while pc < len(code):
        op, *arg = code[pc]
        pc += 1
        steps += 1
        if op == "PUSH":
            stack.append(arg[0])
        elif op == "LOAD":
            stack.append(memory.get(arg[0], 0))
        elif op == "STORE":
            memory[arg[0]] = stack.pop()
        elif op == "PRINT":
            print("output:", stack.pop())
        elif op == "JUMP":
            pc = arg[0]
        elif op == "JUMP_IF_FALSE":
            if stack.pop() == 0:
                pc = arg[0]
        else:
            b, a = stack.pop(), stack.pop()
            stack.append({"ADD": a + b, "SUB": a - b, "MUL": a * b, "LESS": int(a < b)}[op])
    return steps


source = """n = 5
f = 1
while 0 < n
f = f * n
n = n - 1
end
print f""".splitlines()
code = compile_program(source)
for address, instruction in enumerate(code):
    print(f"{address:2}  {' '.join(str(part) for part in instruction)}")
print("instructions run:", run(code))
Open in compiler

Line by line

  1. parse builds trees with < at the lowest precedence, then + -, then *.
  2. gen emits post-order code; compile_program adds STORE, PRINT and the loop layout.
  3. At while, the start address 4 is recorded and JUMP_IF_FALSE is emitted at address 7 with no target.
  4. At end, JUMP 4 is emitted at address 16, and the jump at 7 is patched to 17, the first address after the loop.
  5. The VM runs the 19 instructions, printing 5! = 120 after 75 steps: the loop body runs five times, and the condition six times.

Expected result

 0  PUSH 5
 1  STORE n
 2  PUSH 1
 3  STORE f
 4  PUSH 0
 5  LOAD n
 6  LESS
 7  JUMP_IF_FALSE 17
 8  LOAD f
 9  LOAD n
10  MUL
11  STORE f
12  LOAD n
13  PUSH 1
14  SUB
15  STORE n
16  JUMP 4
17  LOAD f
18  PRINT
output: 120
instructions run: 75

In the real world

Python's dis module shows CPython bytecode: dis.dis on a loop shows instructions such as LOAD_FAST, BINARY_OP and POP_JUMP_IF_FALSE, the same ideas with different names. javap -c shows JVM bytecode such as iload, imul and if_icmpge. WebAssembly's text format uses local.get, i32.mul and br_if. Just-in-time compilers in the JVM and in JavaScript engines then turn the hottest bytecode into register-machine code.

Common mistakes

  • Popping the operands of SUB in the wrong order: the right operand is on top, so pop b first, then a.
  • Forgetting to backpatch a jump, so it jumps to a blank address.
  • Jumping back to the body instead of the condition, so the loop never stops.
  • Leaving values on the stack after a statement, so the stack grows with every loop.

Best practices

  • Print the code with addresses; most code generation bugs are visible in the listing.
  • Count the stack depth in the VM while testing: after each statement it should be back to zero.
  • Keep the instruction set small and orthogonal; each instruction should do one thing.

Summary

A stack machine takes operands from a stack, so expressions compile in post-order and variables use LOAD and STORE. Loops and conditions become conditional and unconditional jumps; forward jumps are emitted first and backpatched once their targets are known. A virtual machine runs the code with a program counter in a fetch-decode-execute loop.

Quick check

1. Which code does a = b - 1 compile to?
2. Why is backpatching needed?
3. Where does the JUMP at the end of a while loop go?
4. What does a VM do with the program counter for each instruction?

Key takeaways

  • Expressions compile in post-order; a variable is read with LOAD and written with STORE.
  • A while loop is: condition, JUMP_IF_FALSE past the loop, body, JUMP back to the condition.
  • Forward jumps are emitted with a blank address and patched once the target is known.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.