Introduction
A syntax tree is good for checking a program but awkward for optimizing it or turning it into machine code, because the work is hidden inside nested nodes. Compilers therefore lower the tree into an intermediate representation (IR): a list of simple instructions, closer to the machine but not tied to any particular one. LLVM IR, GCC's GIMPLE and the bytecode of the Java and Python virtual machines are all intermediate representations. Most optimizations happen on the IR.
How it works
Three-address code is a classic IR. Each instruction has at most one operator and at most three names:
x = y op z x = y goto L ifFalse x goto L L:
To lower an expression, walk its tree in post-order (children before the node). Each operator gets a fresh temporary (t1, t2, …) to hold its result, and the instruction refers to the names or temporaries of its operands. a + b * c becomes t1 = b * c and then t2 = a + t1. When the expression is assigned to a variable, the last instruction can write straight to that variable: x = a + t1.
Control flow is lowered to labels and jumps. A while loop becomes:
L1: start of the loop
t = condition compute the condition
ifFalse t goto L2 leave the loop when it is false
...body...
goto L1 go back and test again
L2: the first instruction after the loop
An if without an else needs only one label, after its body. The labels are numbered in the order they are created, as are the temporaries.
Why bother? An IR separates the compiler into a front end (one per source language) and a back end (one per machine). With M languages and N machines, you write M + N pieces instead of M × N compilers. LLVM works this way: Clang, Rust and Swift all produce LLVM IR, and LLVM turns it into code for x86, ARM, WebAssembly and more.
Syntax
def expr(node, target=None):
if is_leaf(node):
return node # a name or a number
a, b = expr(node.left), expr(node.right) # post-order
dest = target or new_temp()
emit(f"{dest} = {a} {node.op} {b}")
return dest
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() in ("<", "<=", ">", ">=", "==", "!="):
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() in ("*", "/"):
node = (take(), node, atom())
return node
def atom():
token = take()
if token == "(":
node = compare()
take()
return node
return token
return compare()
class Lowerer:
def __init__(self):
self.code, self.temps, self.labels = [], 0, 0
def new_temp(self):
self.temps += 1
return f"t{self.temps}"
def new_label(self):
self.labels += 1
return f"L{self.labels}"
def expr(self, node, target=None):
if isinstance(node, str):
if target:
self.code.append(f"{target} = {node}")
return node
op, left, right = node
a = self.expr(left)
b = self.expr(right)
dest = target or self.new_temp()
self.code.append(f"{dest} = {a} {op} {b}")
return dest
def program(self, lines):
blocks = []
for line in lines:
tokens = re.findall(r"\d+|\w+|[<>=!]=|\S", line)
if tokens[0] == "while":
start, end = self.new_label(), self.new_label()
self.code.append(f"{start}:")
cond = self.expr(parse(tokens[1:]))
self.code.append(f"ifFalse {cond} goto {end}")
blocks.append((start, end))
elif tokens[0] == "if":
end = self.new_label()
cond = self.expr(parse(tokens[1:]))
self.code.append(f"ifFalse {cond} goto {end}")
blocks.append((None, end))
elif tokens[0] == "end":
start, end = blocks.pop()
if start:
self.code.append(f"goto {start}")
self.code.append(f"{end}:")
else:
self.expr(parse(tokens[2:]), target=tokens[0])
source = """total = 0
i = 1
while i < n
total = total + i * i
i = i + 1
end
result = total * 2""".splitlines()
lowerer = Lowerer()
lowerer.program(source)
for line in lowerer.code:
print(line)
print(f"-- {len(lowerer.code)} lines, {lowerer.temps} temporaries, {lowerer.labels} labels")Line by line
parsebuilds a tree with comparisons at the lowest precedence, then+ -, then* /.Lowerer.expremits one instruction per operator, children first, and returns the name that holds the result.- For an assignment, the root operator writes directly to the variable instead of a new temporary.
whilecreates two labels: one before the condition and one after the loop;endemits the jump back and places the exit label.- The loop body
total = total + i * ineeds only one temporary, t2, fori * i.
Expected result
total = 0
i = 1
L1:
t1 = i < n
ifFalse t1 goto L2
t2 = i * i
total = total + t2
i = i + 1
goto L1
L2:
result = total * 2
-- 11 lines, 2 temporaries, 2 labels
In the real world
Clang's -emit-llvm option and rustc --emit=llvm-ir show the LLVM IR of a program; it looks very much like three-address code. Python's dis module shows CPython's bytecode, a stack-based IR. Many IRs, including LLVM's, also use static single assignment (SSA) form, where every name is assigned exactly once, which makes the optimizations in the next lesson simpler.
Common mistakes
- Reusing one temporary for two live values, so one result overwrites another.
- Emitting the operator before its operands: lowering must be post-order.
- Placing the loop's start label after the condition, so the condition is never tested again.
- Forgetting the exit label, so the conditional jump has nowhere to go.
Best practices
- Make temporaries and labels with counters, so every one is unique.
- Print the IR while developing; it is the easiest place to see code generation bugs.
- Keep the IR simple: fewer instruction forms mean simpler optimizations and back ends.
Summary
Three-address code is a list of simple instructions with at most one operator each. Lowering an expression is a post-order walk that stores each partial result in a fresh temporary; lowering loops and conditions uses labels, conditional jumps and gotos. An IR like this sits between the front end and the back end, so it can be shared by many languages and machines.
Quick check
Key takeaways
- Every expression becomes a sequence of instructions with one operator each, in post-order.
- Loops and conditions become labels, conditional jumps and gotos.
- One IR lets many source languages share one optimizer and many back ends.
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.