Basic Blocks and Flow Graphs

Three rules find the leaders, the leaders make the blocks, and a cycle in the graph is a loop.

A basic block is a maximal run of instructions entered only at the top and left only at the bottom; joining blocks by their possible transfers of control gives the flow graph every optimisation is defined over.

The point of grouping

Inside a basic block, control flow is completely uninteresting: every instruction runs, in order, exactly once per entry. That is precisely what makes analysis tractable — within a block you can reason as if the code were straight-line, because it is.

All the difficulty of control flow is then pushed into the edges between blocks, where it can be handled once, systematically.

Finding the leaders

A leader is the first instruction of a block. Three rules find every one of them, and they are worth memorising because exam questions ask for exactly this:

1The first instruction of the program is a leader.
2Any instruction that is the target of a jump — conditional or not — is a leader.
3Any instruction immediately following a jump is a leader.

Each leader's block then runs up to, but not including, the next leader. Rules 2 and 3 are the two halves of the same idea: you cannot jump into the middle of a block, and you cannot fall off the end of one without it ending.

Building the graph

Add an edge from block B to block C whenever control can pass directly from the end of B to the start of C — either because B ends in a jump to C, or because C simply follows B and B does not end in an unconditional jump.

Block	Instructions	Ends with	Goes to
B1	1–2	falls through	B2
B2	3	conditional jump	B3 or B4
B3	4–7	goto (3)	B2
B4	8	return	—

A cycle in the flow graph is a loop. The compiler never has to be told a for was written — it would find the same loop in code assembled from raw gotos.

What it is all for

Local optimisation works inside one block: common subexpression elimination, constant folding, dead code removal. Easy, because there are no branches to worry about.
Global optimisation works across blocks by pushing facts along the edges until nothing changes — live variable analysis, reaching definitions, constant propagation. These are the dataflow problems.
Loop optimisation targets cycles specifically: hoisting invariant code out, strength reduction, unrolling. Worth disproportionate effort, because that is where the running time is.
Register allocation needs liveness, which needs the graph.

None of these can even be stated without the flow graph, which is why building it is the first thing the back end does.

Advantages and disadvantages

Advantages

Straight-line code inside a block makes local analysis simple and exact.
Loops are discovered structurally, whatever the source language looked like.
One representation supports essentially every optimisation a compiler performs.

Disadvantages

Indirect jumps and computed gotos can make the graph imprecise.
Blocks are often very short, so global analysis does most of the real work.
Exception handling adds edges that are easy to get wrong and easy to forget.