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.
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.
| source | three-address code |
|---|---|
h = 60 * 24 * 7 | t1 = 60 * 24h = t1 * 7 |
s = s + k * i | t2 = k * is = s + t2 |
k = h | k = 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.
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:
- the first instruction (line 1);
- every jump target:
L1,L2,L3,L4(lines 5, 11, 14, 15); - 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 instruction | edges | here |
|---|---|---|
goto L | one, to the block of L | B3 → B2, B5 → B7 |
ifFalse … goto L | two: fall through, and to the block of L | B2 → B3, B2 → B4; B4 → B5, B4 → B6 |
return | none: the exit | B7 |
| anything else | one, fall through to the next block | B1 → 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.
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 run | instructions | executed for n = 3 |
|---|---|---|
| none (as translated) | 15 | 27 |
| dead code only | 15 | 27 |
| constant folding, then dead code | 14 | 26 |
| copy propagation, then dead code | 14 | 24 |
| folding, copy propagation, dead code | 13 | 23 |
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.