The idea: one operator per instruction

After parsing, a compiler has a syntax tree. Before it picks machine instructions, it usually rewrites the tree into a simple intermediate code. A popular form is three-address code (TAC): each instruction has at most one operator and at most three names, like x = y + z. Loops and ifs become labels and jumps. The code is flat and easy to analyse, so the optimizer works on it. The page follows one small program through four stages.

Four boxes left to right: source with a while loop and an if, three-address code with 15 instructions, a control-flow graph with 7 blocks and 8 edges, and optimized code with 13 instructions. Arrows lead from each stage to the next.
Source → three-address code → basic blocks and a control-flow graph → optimized code: 15 instructions become 13.

The program sums h * i for i from 0 to n − 1, then subtracts h if the sum is larger:

h = 60 * 24 * 7;
s = 0;
i = 0;
while (i < n) {
    k = h;
    s = s + k * i;
    i = i + 1;
}
if (s > h) r = s - h; else r = 0;
return r;

Temporaries for expressions

An expression with two operators is too big for one instruction. The generator walks the tree bottom-up. Each inner operation gets a new temporary, a compiler-made name t1, t2, …. The last operation writes straight into the target variable. An assignment with no operator, like k = h, is a copy.

sourcethree-address code
h = 60 * 24 * 7t1 = 60 * 24
h = t1 * 7
s = s + k * it2 = k * i
s = s + t2
k = hk = h (a copy)

The order follows the tree: 60 * 24 is deeper than * 7, and k * i is deeper than s + …, so they come first. (Demo: translate to three-address code)

Labels and jumps for if and while

TAC has no blocks in braces. A while loop and an if / else each get two new labels and follow a fixed shape. ifFalse c goto L jumps when the condition is false; otherwise the next line runs.

Left: while (c) S becomes L1: ifFalse c goto L2, then the body S, then goto L1, then L2. Right: if (c) S1 else S2 becomes ifFalse c goto L3, S1, goto L4, L3: S2, L4. Arrows show each jump.
The two shapes: a loop jumps back up to its test; an if / else jumps over the branch that should not run.

For the program that gives 15 instructions, 2 temporaries (t1, t2), 4 labels (L1 to L4) and 4 jumps:

 1      t1 = 60 * 24
 2      h = t1 * 7
 3      s = 0
 4      i = 0
 5  L1: ifFalse i < n goto L2
 6      k = h
 7      t2 = k * i
 8      s = s + t2
 9      i = i + 1
10      goto L1
11  L2: ifFalse s > h goto L3
12      r = s - h
13      goto L4
14  L3: r = 0
15  L4: return r

The loop's exit label L2 lands on the first instruction after the loop, which is the test of the if. Run with n = 3, this code executes 27 instructions and returns r = 20160.

Basic blocks and leaders

A basic block is a run of instructions that control enters only at the top and leaves only at the bottom. If its first instruction runs, all of them run. To find blocks, mark the leaders:

  1. the first instruction (line 1);
  2. every jump target: L1, L2, L3, L4 (lines 5, 11, 14, 15);
  3. every instruction right after a jump (lines 6, 11, 12, 14).

That gives 7 leaders: 1, 5, 6, 11, 12, 14 and 15. Each block runs from a leader to just before the next one, so there are 7 blocks, B1 to B7. B1 has 4 instructions and the loop body B3 has 5.

The control-flow graph

The control-flow graph (CFG) has one node per block. Its edges come from how each block ends:

last instructionedgeshere
goto Lone, to the block of LB3 → B2, B5 → B7
ifFalse … goto Ltwo: fall through, and to the block of LB2 → B3, B2 → B4; B4 → B5, B4 → B6
returnnone: the exitB7
anything elseone, fall through to the next blockB1 → B2, B6 → B7

That is 8 edges. B3 → B2 goes back to an earlier block: a back edge. B2 and B3 together are the while loop. The same graph is what test coverage is measured on; see Control-Flow Coverage. (Demo: basic blocks and the control-flow graph)

Constant folding

The optimizations on this page are local: they look at one block at a time and know nothing at the top of a block. Constant folding computes an operation whose operands are both constants at compile time. It also remembers which variables got a constant earlier in the same block and uses the constant instead. In B1:

t1 = 60 * 24     →   t1 = 1440
h = t1 * 7       →   h = 1440 * 7   →   h = 10080

Two instructions change, but the count stays 15 and the program still executes 27 instructions. Now t1 is read nowhere. (Demo: constant folding)

Copy propagation

After a copy x = y, a later read of x in the same block can read y instead, until x or y gets a new value. In B3, k = h is followed by t2 = k * i, which becomes t2 = h * i. One instruction changes. Now k is read nowhere. (Demo: copy propagation)

Dead-code elimination

An assignment x = … is dead if no instruction ever reads x: it can be deleted without changing what the program returns. Deleting one can make another dead, so the pass repeats until nothing changes. On the code as translated, it finds nothing: t1 is read by line 2, k by line 7. (Demo: dead-code elimination first finds nothing) After folding and copy propagation, it deletes t1 = 1440 and k = h.

Blocks B1 and B3 shown in four columns: as translated, after constant folding, after copy propagation, and after dead-code elimination. B1 goes from 4 to 3 instructions and B3 from 5 to 4; the deleted lines t1 = 1440 and k = h are crossed out in red.
Folding and copy propagation do not shorten the code; they leave t1 and k unread, and dead-code elimination then deletes them.

Passes feed each other

Each pass on its own does little. Together they shrink the code, and the order matters. (Demo: fold, copy, then dead code: 15 → 13)

passes runinstructionsexecuted for n = 3
none (as translated)1527
dead code only1527
constant folding, then dead code1426
copy propagation, then dead code1424
folding, copy propagation, dead code1323

Removing k = h saves more at run time than removing t1, because it sat in the loop body and ran 3 times. The answer, r = 20160, never changes. The blocks get shorter, but the graph keeps its 7 blocks and 8 edges.

Where real compilers go further

Here h is a constant everywhere, but a local pass forgets that at the top of B3. A global pass follows facts along the CFG edges (dataflow analysis), so it could also turn t2 = h * i into t2 = 10080 * i. Modern compilers such as GCC and LLVM first rewrite the code into SSA form, where each variable is assigned once, which makes these passes simple and fast. After that come instruction selection and register allocation; see Register Allocation by Graph Coloring. For the front end that builds the tree, see Inside a Tiny Compiler and LR Parsing.

See also Hindley-Milner type inference for the semantic check that runs on the tree before it is turned into three-address code.

What the page leaves out

The page uses one fixed program and integer variables only. It leaves out type checking, arrays and address arithmetic, function calls and parameters, short-circuit && and || (backpatching), quadruples versus triples, global dataflow (reaching definitions, liveness across blocks), SSA and φ-functions, common subexpression elimination, loop-invariant code motion, strength reduction, and removing unreachable blocks.

On the mind map

Open the Java & the JVM mind mapJava & the JVMFrom source to bytecode: translate first, or while runningFrom source to bytecodeStartup and class loading: what happens before main()Startup and class loadingJIT compilers: compile hot code using profilesJIT compilersMemory and GC: find and free unreachable objectsMemory and GCCollections: how java.util stores keysCollectionsThreads and memory model: Java threads on real coresThreads and memory modelSpring framework: a container builds your objectsSpring frameworkCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceHindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingLL(1) ParsingStack top + one token pick the productionLR parsingLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links onceOpen the Java & the JVM mind mapJava & the JVMtranslate first, or while runningFrom source to bytecodeCompiler vs interpreterCompiler vs interpretercompile once ahead, or decode every runTiny compilerTiny compilerlexer, parser, code generator, VMThree-address codeFold + copy prop make code dead: 15→13Hindley-Milner inferenceHindley-Milner inferenceEquations per node, unify into SStatic vs Dynamic ScopingStatic vs Dynamic ScopingWritten-in vs called-from decides xLL(1) ParsingLL(1) ParsingStack top + one token pick the productionLR parsingLR parsingShift tokens, reduce handles bottom upjavacjavacsource to type-checked .class bytecodeLambdas and invokedynamicLambdas and invokedynamicfirst call bootstraps, then links once
This page on the Java & the JVM mind map · 35 pages in 7 branches · open it to see the whole map and test yourself in recall mode.