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:
| Instruction | Effect |
|---|---|
PUSH n | push the number n |
LOAD x / STORE x | push the value of x / pop a value into x |
ADD, SUB, MUL, LESS | pop b, pop a, push a op b (LESS pushes 1 or 0) |
PRINT | pop a value and print it |
JUMP a | continue at address a |
JUMP_IF_FALSE a | pop 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))Line by line
parsebuilds trees with<at the lowest precedence, then+ -, then*.genemits post-order code;compile_programadds STORE, PRINT and the loop layout.- At
while, the start address 4 is recorded andJUMP_IF_FALSEis emitted at address 7 with no target. - At
end,JUMP 4is emitted at address 16, and the jump at 7 is patched to 17, the first address after the loop. - 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
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.