- Compilers: Principles, Techniques and Tools — Ch. 6 §6.6 (control flow, boolean expressions, flow-of-control statements), §6.7 (backpatching); Ch. 8 §8.4 (basic blocks and flow graphs), §8.5 (optimization of basic blocks), §8.7 (peephole optimization); Ch. 9 §9.1 (the principal sources of optimization), §9.2 (introduction to data-flow analysis). Review §4.4–4.5.
- §9.1 is the single most useful twenty pages in the book for this project — it names and justifies every transformation you are about to implement.
- Browse §9.3 (foundations of data-flow analysis) for why the iterative algorithm terminates. You do not need the lattice theory, but you should know it exists.
0Where this topic sits
Two things arrive together in this topic, and their arrival together is not a coincidence. Loops mean the program's control flow is no longer a straight line, so the compiler needs a way to talk about the paths a program may take. Optimization becomes worth doing for the first time, because an instruction inside a loop that runs a thousand times costs a thousand instructions.
The connecting idea is the flow graph. It is the representation that makes 'this instruction is inside a loop' a statement the compiler can check rather than a remark a programmer makes.
1There are no loops in a machine
A processor has exactly two control-flow instructions: jump unconditionally, and jump if a register is (or is not) zero. Every while, for, if and switch in every language you have used is a pattern of those two. Turning a structured statement into that pattern is called lowering, and Dragon §6.6.3 gives the standard schemes.
for is a while with two extra pieces; a do-while is a while with the test moved to the bottom. Once you have lowered one, you have lowered all of them — which is the payoff for having done the work carefully the first time.Read the three columns side by side. The for loop is a while loop with an initializer hoisted above and an update appended to the body; the do-while is a while with the test at the bottom. This is why many compilers desugar — rewrite one form into another in the front end — and only ever lower one loop shape.
A while whose condition is initially false must execute its body zero times. That is not an implementation detail, it is what the construct means, and it is fixed by where the test is emitted. Put the test at the bottom and you have silently implemented do-while — a real language construct, but not the one you documented. Your test suite needs a program whose loop runs zero times, or this bug will not show up.
break, and why it is not a grammar question
A break means jump to the exit label of the innermost enclosing loop. The compiler needs no analysis to work that out: when it starts lowering a loop it pushes that loop's exit label on a stack, and pops it when it finishes. Any break in between emits a jump to whatever is on top. Nesting then works for free.
Whether a break is legal is a different question, and it is the smallest possible example of a context-sensitive rule. No grammar can express 'this statement is legal only inside a loop', because the grammar for break_stmt is satisfied wherever the statement appears. A depth counter in the semantic analyzer settles it — and that is exactly the territory Topic 2 §8 said phase 3 exists to cover.
2Basic blocks and the flow graph
Once control flow branches, the instruction list is no longer the right way to think about the program. Dragon §8.4 introduces the two structures that are.
A basic block is a maximal sequence of consecutive instructions such that control enters only at the first and leaves only at the last. Finding them is a three-rule algorithm:
A flow graph then has one node per basic block and an edge from B to C whenever control can pass directly from the end of B to the start of C:
Two things become sayable that were not sayable before. A loop is a set of nodes with a single entry point, reachable from each other — identified in practice by a back edge, an edge from a node to one that dominates it (Dragon §9.6). And this instruction executes n times per entry to the procedure becomes a property of the graph rather than a guess.
A label is the start of a basic block, which means control can arrive there from any of its predecessors. A fact established on one incoming path — 'x holds 5' — is not a fact on the others. Without a flow graph the compiler cannot tell which predecessors exist, so the only safe policy is to discard what it knew. Building the flow graph is exactly what would let it do better, and that is the single largest improvement available to your optimizer.
3The principal sources of optimization
Dragon §9.1 catalogues the transformations, and divides them in a way worth keeping:
Function-preserving transformations
These change how a computation is performed without changing what it computes, and they apply anywhere:
| Transformation | The condition that makes it safe |
|---|---|
| Common subexpression elimination | the expression was previously computed and none of its operands has changed since |
| Copy propagation | after x = y, uses of x may become y until either is reassigned |
| Constant folding | both operands are literals — so the compiler can do the arithmetic instead of the processor |
| Constant propagation | the variable provably holds that constant at this point on every path reaching it |
| Dead-code elimination | nothing reads the result afterward, and computing it has no other effect |
Note how many of those conditions contain the words previously, since, afterward, or every path. Each one is a question about the flow graph, which is why §4 exists.
Loop optimizations, which matter more
| Transformation | What it does | Why it pays |
|---|---|---|
| Code motion | move a loop-invariant computation out of the loop | executes once instead of once per iteration |
| Induction-variable elimination | recognize variables that advance in lockstep and keep only one | removes a whole variable and its updates |
| Strength reduction | replace an expensive operation with a cheaper one computing the same thing | a multiply per iteration becomes an add |
| Loop unrolling | replicate the body, doing several iterations per test | removes tests and jumps — at the cost of code size |
You have already met one strength reduction: array indexing emits a shift rather than a multiply, because the element width is a power of two. It was there before phase 5 existed, in the code generator, which is a reminder that optimization is not confined to the phase named after it.
4Data-flow analysis
Every condition in the table above is a question of the form what is true at this point, given all the ways control could have reached it? Dragon §9.2 gives a single framework that answers all of them.
Three classical analyses instantiate the framework, and they are worth knowing by name because almost every optimization is built on one of them:
| Analysis | Question it answers | Direction | Enables |
|---|---|---|---|
| Reaching definitions | which assignments to x could be the one in effect here? | forward | constant propagation; use-before-definition warnings |
| Live variables | will the value in x be read again before being overwritten? | backward | dead-code elimination; register allocation |
| Available expressions | has b - c already been computed on every path here? | forward | common-subexpression elimination |
The solution method is the same in all three cases: initialize, then apply the equations repeatedly until nothing changes. That it terminates is not obvious, and Dragon §9.3 proves it: the values form a lattice of finite height, the transfer functions are monotone, so the iteration can only move in one direction and must stop. You do not need the proof — but knowing that a termination argument exists is the difference between using a technique and hoping.
What ours does instead
Our optimizer performs no data-flow analysis. It walks the instruction list, keeps a small set of facts about constants and copies, and discards all of them at every label. That is local optimization — Dragon §8.5, within a basic block — and it is safe precisely because it never claims anything across a control-flow join.
The upgrade path is clear and is the best optional extension in this topic: build the flow graph, implement reaching definitions, and constant propagation becomes valid across blocks. That is the difference between a local optimizer and a global one.
Why is it unsafe to propagate a constant across a label without further analysis?
5Optimizing within a basic block
Dragon §8.5 shows what can be done with no flow analysis at all, using a DAG built from the block: one node per computed value, with identical subexpressions sharing a node. Building it detects common subexpressions automatically, since two occurrences of b - c map to the same node. Reading the DAG back out yields the optimized block, and dead code is simply whatever the reconstruction does not visit.
Peephole optimization (Dragon §8.7) is the other technique that needs no analysis. Slide a small window over the generated code and rewrite recognizable patterns:
redundant load/store eliminate flow-of-control
sw $t0, x goto L1 -> goto L2
lw $t0, x -> L1: goto L2
(the load is redundant)
algebraic simplification strength reduction
add $t0, $t0, 0 -> gone mul $t, $t, 4 -> sll $t, $t, 2Peephole passes are cheap, are usually run repeatedly because one rewrite can enable another, and catch a surprising amount of what earlier phases leave behind.
6Running to a fixed point
The transformations feed each other, so no single pass finds everything:
This is why optimizeTAC repeats until a pass reports no changes, and why it reports how many passes it took. It is also a small instance of the same iterate-to-convergence idea that underlies data-flow analysis — which is why understanding it here makes §9.2 much easier to read.
7Measuring the result
Project 4 asks you to quantify the gain, and quantifying is where most reported speedups fall apart. Two distinct numbers are available:
What makes a number defensible
- State the baseline. 'Thirty per cent faster' is meaningless without 'than the unoptimized output of the same compiler on the same program'.
- State the benchmark. A speedup measured on a program with a hot loop tells you about hot loops. Include the source.
- Repeat the measurement. Three runs minimum, and report the spread. If the spread is eight per cent, a five per cent improvement is not a result.
- Say which metric. Code size and work done are different questions, and the gap between them is itself informative.
It does not model pipelines, caches or memory latency, so wall-clock seconds from SPIM mean very little. Instructions executed is the honest metric: it is deterministic, exactly reproducible, and directly attributable to your compiler's output rather than to the machine you happened to run on.
8The approach for this milestone
Lower one loop form completely before starting the second
Get while through all six phases and running in SPIM before touching for. The second form then takes an hour, because the machinery — labels, jumps, the break stack, the branch cases in the back end — already exists and is tested.
Decide desugaring versus direct lowering deliberately
Desugaring for into while in the parser keeps the back end smaller and guarantees the two forms cannot drift apart. A dedicated case keeps the generated TAC readable and leaves room to optimize for specifically. Both are defensible; Lab Question 18 asks which you chose.
Write the zero-iteration test first
A loop whose condition is false at entry must run its body zero times. It is the one behavior that distinguishes correct lowering from plausible lowering, and it is the test people forget.
Make the optimizer report what it did
A count per technique, and a pass count. Without it you cannot tell a working optimizer from one that silently does nothing, and you have no evidence for the write-up. The report is the deliverable for half of Project 4.
Do the measurement in week 11, not the night before
It takes longer than expected, and the same numbers are reused in Project 6. Doing it properly once saves doing it badly twice.
9Self-check
Where does a basic block begin?
Your optimizer reports 35% fewer TAC instructions, but SPIM reports only 4% fewer instructions executed. What is the most likely explanation?
Which analysis would you need in order to eliminate t = a + b when t is never used again?
Why must the optimizer be run repeatedly rather than once?
A while loop whose condition is false at entry runs its body zero times. What in the lowering guarantees that?
10References
- Aho, Lam, Sethi & Ullman, 2nd ed. — §6.6 (control flow and flow-of-control statements), §6.7 (backpatching); §8.4 (basic blocks and flow graphs, Algorithm 8.5), §8.5 (the DAG representation and optimization of basic blocks), §8.7 (peephole optimization); §9.1 (the principal sources of optimization), §9.2 (introduction to data-flow analysis: reaching definitions, live variables, available expressions), §9.3 (foundations — lattices, monotonicity, termination), §9.6 (loops in flow graphs, dominators, back edges).
- Cooper & Torczon, Engineering a Compiler, ch. 8–9 — a more implementation-oriented treatment of the same material.
- SPIM documentation on the statistics it reports after a run.