Three-address code

Advanced

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")
Open in compiler

Line by line

  1. parse builds a tree with comparisons at the lowest precedence, then + -, then * /.
  2. Lowerer.expr emits one instruction per operator, children first, and returns the name that holds the result.
  3. For an assignment, the root operator writes directly to the variable instead of a new temporary.
  4. while creates two labels: one before the condition and one after the loop; end emits the jump back and places the exit label.
  5. The loop body total = total + i * i needs only one temporary, t2, for i * 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

1. How is a + b * c lowered?
2. What is a temporary?
3. Where does the loop's start label go?
4. Why do compilers use an IR?

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.