Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 61 ยท Intermediate Code and Optimization

Intermediate Representations

Learn what an intermediate representation is and compare ASTs, three-address code, SSA, stack bytecode and register code with runnable Python examples.

After parsing and type checking, a compiler knows that your program is valid and what it means. It does not translate it straight into machine code. Instead it rewrites the program into one or more intermediate representations (IRs): forms that are neither the source language nor the final machine language, but that are far better suited to analyzing and improving code.

Why bother with a middle layer? Imagine m source languages and n machine targets. Going directly from every language to every machine needs m x n translators. With one shared IR you need only m front ends (source to IR) and n back ends (IR to machine), and every optimization written for the IR helps all of them. This is exactly the design of LLVM, GCC's GIMPLE and RTL, the JVM's bytecode and CPython's bytecode.

A good IR has a job

There is no single "right" IR. Each form makes some questions easy and others hard, and real compilers often use several in sequence, moving from high level to low level (this is called lowering).

flowchart LR
    A["Source code"] --> B["AST<br/>(structure, types)"]
    B --> C["Three-address code<br/>(explicit temporaries)"]
    C --> D["SSA form<br/>(one assignment per name)"]
    D --> E["Machine-like IR<br/>(registers, stack slots)"]
    E --> F["Machine code"]

Each step trades source-level structure for machine-level detail; most optimizations happen in the middle.

Roughly, the higher the IR, the more it resembles the source (loops, types, objects), which is good for language-specific checks. The lower the IR, the closer it is to hardware, which is good for instruction selection and register allocation. The middle, with simple instructions but still machine-independent, is where most optimizers live.

The AST as an IR

You already know the first IR: the abstract syntax tree. It keeps the nested structure of the program, so it is perfect for type checking and for source-level tools such as formatters and refactoring. But it is awkward for optimization. Evaluation order is hidden in the shape of the tree, control flow is spread through nested statements, and there is nowhere to put a temporary value that two subtrees want to share.

Three-address code

Three-address code (TAC) flattens expressions into a list of simple instructions. Each instruction has at most one operator and at most three addresses: two operands and one result.

TEXT
x = y op z        t1 = a + b
if x goto L       t2 = t1 * c
goto L            t3 = a + b
L:                t4 = t2 - t3

Every intermediate value gets its own named temporary, so evaluation order is explicit and each instruction is trivial to analyze. Control flow becomes labels and jumps, the shape of every real processor. Generating three-address code is the next lesson's subject.

Stack machines and register machines

When the IR is meant to be executed (by an interpreter or a VM), two designs dominate.

A stack machine has no named operands in its arithmetic instructions. ADD pops two values from an operand stack and pushes the sum. The code is compact and trivial to generate (a post-order walk of the tree), which is why the JVM, CPython and WebAssembly use stack-based bytecode.

A register machine has instructions with explicit operand names, like ADD r0, r0, r1. The code is longer to encode per instruction but needs fewer instructions overall, because values do not move through the stack. Real CPUs are register machines, and Lua and Android's Dalvik/ART picked register-based virtual machines for speed.

The first example builds all of these forms from a single tree, for the expression (a + b) * c - (a + b).

Python One expression, four representations

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 same tree gives four very different texts. The TAC has 4 instructions, one per operator, and names every intermediate result, so you can immediately see that t1 and t3 are the same computation (a + b). The stack bytecode has 9 instructions because every operand needs its own LOAD; the register code is 9 instructions too, but its arithmetic names the registers. Notice how to_registers reuses r1 for the second b once the first one is dead: that is a tiny taste of register allocation.

Running both kinds of virtual machine

Both designs compute the same answer. The stack machine keeps temporaries on a stack, the register machine keeps them in named slots. Executing the two programs side by side makes the difference tangible.

Python Stack machine versus register machine

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.

Both give 15. The stack machine's ADD needs no operand fields at all, which makes its instructions short, but it executes the same count of instructions here. On larger programs a register machine often needs fewer, because it can keep a value in a register and use it many times without reloading. You will build a real stack VM in bytecode and virtual machines.

Static single assignment (SSA)

Many optimizations need to ask "where did this value come from?". In ordinary code the answer is complicated because a variable can be assigned many times. Static single assignment form fixes that with one rule: every variable is assigned exactly once in the program text. Each assignment creates a new version of the variable (x1, x2, ...), and each use refers to exactly one version.

Straight-line code is easy to convert. Branches are the problem: after an if, which version of x do you use? SSA introduces a special instruction at the merge point, the phi function, which picks a value according to which predecessor block control came from. Static single assignment covers how to place the phi functions. For now, run a small example: the renaming of straight-line code and an interpreter that evaluates a diamond-shaped program with a phi.

Python SSA renaming and a phi function

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 renaming makes the dependencies obvious. x2 = y1 * x1 uses exactly the versions that were current at that point, and nobody can accidentally read a stale x. The phi x3 = phi(then: x1, else: x2) is not a real machine instruction; it is a notation that says "x3 is x1 if we arrive from then, and x2 if we arrive from else". The interpreter resolves it by remembering the block it just left. Later phases translate phis back into ordinary copies before generating machine code.

Peeking at LLVM IR (read-only)

LLVM's IR is SSA-based, typed, and sits between nearly every modern language and its machine code. The site cannot run LLVM, so this is shown as text only. A C function like int f(int a, int b, int c) { return (a+b)*c - (a+b); } becomes, after optimization, roughly:

TEXT
define i32 @f(i32 %a, i32 %b, i32 %c) {
entry:
  %sum  = add i32 %a, %b
  %prod = mul i32 %sum, %c
  %res  = sub i32 %prod, %sum
  ret i32 %res
}

Compare it with the TAC from earlier. It is three-address code in SSA form, with types on every value, and the optimizer has already noticed that a + b is computed twice and reused it. The exact text depends on the compiler version and options, but that shape is what you will see. CPython's dis output, which you saw in what is a compiler, is the stack-machine equivalent for Python.

Choosing an IR for your own compiler

  • If your language is small, the AST plus a stack bytecode may be all you need (that is how many scripting languages work).
  • If you want serious optimization, flatten to three-address code, split it into basic blocks (see basic blocks and control flow graphs) and convert to SSA.
  • Keep the IR simple and regular: few instruction kinds, each with a precise meaning. Every analysis you write later must handle each kind.
  • Make it printable and testable. An IR you can dump as text is an IR you can debug and write golden tests for.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do compilers use a shared intermediate representation instead of translating each source language directly to each machine?

    With a common IR, each language needs one translator into it and each machine one translator out of it, and optimizers written once for the IR benefit all combinations.
  2. 2. What is a defining property of three-address code?

    TAC flattens nested expressions so that each instruction does one simple thing, using named temporaries for intermediate results.
  3. 3. Which statement about stack machines and register machines is correct?

    In a stack machine ADD takes its operands from the top of the stack. Register machines (including real CPUs) name the registers in each instruction.
  4. 4. What does a phi function do in SSA form?

    At a merge point where several versions of a variable could arrive, a phi function chooses the version that matches the path actually taken.
  5. 5. In SSA, how many times may a variable name be assigned in the program text?

    That is the defining rule of SSA. Re-assignments in the source become new versions (x1, x2, ...) so every use refers to exactly one definition.

Summary

  • An intermediate representation sits between the front end and the back end so that optimizations and back ends are shared across languages.
  • The AST preserves structure; three-address code flattens expressions into simple instructions with named temporaries; SSA gives each value exactly one definition, using phi functions at merges.
  • Stack machines use implicit operands and compact code; register machines name their operands and usually run fewer instructions.
  • LLVM IR is typed three-address code in SSA form; CPython and the JVM use stack bytecode.
  • Good IRs are simple, regular and easy to print and test.

Next: Generating Three-Address Code