A city's road network can be described street by street, but planners prefer a map: stretches of road with no junctions are drawn as single lines, and the junctions where you can turn are drawn as points connecting them. Inside a stretch there is nothing to decide; you simply drive from one end to the other. All the interesting decisions happen at the junctions.
Three-address code has the same structure. Long runs of instructions execute one after another with no possibility of jumping in or out, and then a jump (a junction) sends control somewhere else. Before the compiler can optimize code or allocate registers, it draws this map. The straight stretches are basic blocks, and the map is the flow graph.
A basic block is a maximal sequence of consecutive three-address instructions such that control enters only at the first instruction and leaves only after the last instruction, with no halting or branching in between. A flow graph is a directed graph whose nodes are the basic blocks and which has an edge from block B to block C whenever C can immediately follow B in some execution.
In this chapter we partition code into basic blocks with the leader algorithm, build the flow graph, identify loops using dominators and back edges, and compute next-use information inside a block. Every partition, edge list, dominator set and next-use table here was produced by a Python script, and the three-address code was executed on hundreds of random inputs to confirm it does what the source program says.
Why Basic Blocks?
Inside a basic block, if the first instruction executes, every instruction executes, in order, exactly once. That simple fact makes reasoning easy:
Local optimizations (common subexpressions, dead code, constant folding within a block) can be done by looking at the block alone. The DAG Representation of Basic Blocks chapter does exactly this.
Register allocation inside a block can keep values in registers without worrying that control might arrive from somewhere else halfway through.
Global optimization and data-flow analysis work on the flow graph: instead of thousands of instructions, they track information across a much smaller number of blocks.
Partitioning Into Basic Blocks: The Leader Algorithm
A leader is the first instruction of a basic block. Find all leaders using three rules:
The first instruction of the program (or procedure) is a leader.
Any instruction that is the target of a conditional or unconditional jump is a leader.
Any instruction that immediately follows a conditional or unconditional jump (or a return/halt) is a leader.
Then each basic block consists of a leader and all instructions up to, but not including, the next leader (or the end of the program).
Why these rules? Rule 2: a jump target can be entered from somewhere other than the instruction above it, so control does not enter only at the top of whatever block it would otherwise belong to; it must start a new block. Rule 3: after a jump, control may leave, so the block must end at the jump; the next instruction starts a new block.
Worked Example 1
This loop adds up the even elements of an integer array a of length n (4 bytes per element):
s = 0;
i = 0;
while (i < n) {
if (a[i] % 2 == 0) s = s + a[i];
i = i + 1;
}
return s;Its three-address code, numbered from 1:
(1) s = 0
(2) i = 0
(3) if i >= n goto (13)
(4) t1 = 4 * i
(5) t2 = a[t1]
(6) t3 = t2 % 2
(7) if t3 != 0 goto (10)
(8) t4 = s + t2
(9) s = t4
(10) t5 = i + 1
(11) i = t5
(12) goto (3)
(13) return sStep 1: find the leaders.
Leader | Reason |
|---|---|
(1) | Rule 1: first instruction |
(3) | Rule 2: target of |
(4) | Rule 3: follows the conditional jump (3) |
(8) | Rule 3: follows the conditional jump (7) |
(10) | Rule 2: target of the jump at (7) |
(13) | Rule 2: target of the jump at (3); also Rule 3: follows (12) |
Step 2: form the blocks. Leaders 1, 3, 4, 8, 10, 13 give six blocks:
Block | Instructions | Contents |
|---|---|---|
B1 | (1) - (2) | s = 0; i = 0 |
B2 | (3) | loop test |
B3 | (4) - (7) | load a[i], test if even |
B4 | (8) - (9) | s = s + a[i] |
B5 | (10) - (12) | i = i + 1; jump back |
B6 | (13) | return s |
Notice that a block may contain a single instruction (B2, B6). That is perfectly normal.
Flow Graphs
There is an edge from block B to block C if and only if:
the last instruction of B is a jump (conditional or unconditional) to the first instruction of C, or
C immediately follows B in program order and B does not end in an unconditional jump (or return). This is the "fall-through" edge.
B is a predecessor of C, and C a successor of B. Two extra nodes, ENTRY (with an edge to the first block) and EXIT (with edges from every block that can end the program), are often added so that every graph has a single start and a single end.
For Worked Example 1:
Block | Last instruction | Successors |
|---|---|---|
B1 | s = 0 ... i = 0 (no jump) | B2 (fall-through) |
B2 | if i >= n goto (13) | B6 (jump), B3 (fall-through) |
B3 | if t3 != 0 goto (10) | B5 (jump), B4 (fall-through) |
B4 | s = t4 (no jump) | B5 (fall-through) |
B5 | goto (3) | B2 only (unconditional: no fall-through) |
B6 | return s | EXIT |
That is 7 edges between the six blocks (plus ENTRY → B1 and B6 → EXIT if those nodes are drawn).
ENTRY
|
v
+--------------+
| B1 s = 0 |
| i = 0 |
+--------------+
|
v
+------------------+
+-->| B2 if i>=n goto |------------------+
| +------------------+ |
| | (false) | (true)
| v v
| +------------------+ +-------------+
| | B3 t1 = 4*i | | B6 return s |
| | t2 = a[t1] | +-------------+
| | t3 = t2 % 2 | |
| | if t3!=0 goto|---+ v
| +------------------+ | EXIT
| | (false) | (true)
| v |
| +------------------+ |
| | B4 t4 = s + t2 | |
| | s = t4 | |
| +------------------+ |
| | |
| v |
| +------------------+ |
| | B5 t5 = i + 1 |<--+
| | i = t5 |
| | goto (3) |
| +------------------+
| |
+----------+In the graph, jump targets are usually written as block names rather than instruction numbers: if i >= n goto B6. Then blocks can be moved or rebuilt by the optimizer without renumbering anything, the same idea we met with indirect triples in Quadruples, Triples & Indirect Triples.
How Is a Flow Graph Stored?
Each block is a record holding its list of instructions (often a linked list, so instructions can be inserted and deleted cheaply), its list of predecessors and its list of successors. Data-flow analyses then attach sets (live variables, reaching definitions and so on) to each block.
Loops in Flow Graphs
Programs spend most of their time in loops, so optimizers care a lot about them. But a flow graph has no while keyword; loops must be discovered from the edges. The standard tool is dominance.
Block d dominates block n (written d dom n) if every path from ENTRY to n passes through d. Every block dominates itself.
For Worked Example 1, computed by the usual iterative algorithm (dom(B1) = {B1}; for every other block, dom(n) = {n} ∪ the intersection of dom(p) over all predecessors p, repeated until nothing changes):
Block | Dominators | Why |
|---|---|---|
B1 | B1 | entry block |
B2 | B1, B2 | reached from B1 and from B5; only B1 is on both kinds of path |
B3 | B1, B2, B3 | only predecessor is B2 |
B4 | B1, B2, B3, B4 | only predecessor is B3 |
B5 | B1, B2, B3, B5 | reached from B3 directly or via B4, so B4 does not dominate it |
B6 | B1, B2, B6 | only predecessor is B2 |
Now the definitions that identify loops:
A back edge is an edge a → h whose head h dominates its tail a. Here: B5 → B2 (B2 dominates B5).
The natural loop of a back edge a → h is h together with every block that can reach a without passing through h. h is the loop's header, its only entry point. Here: start from B5, go backwards: B5's predecessors are B3 and B4; B4's predecessor is B3; B3's predecessor is B2 (the header, stop). Loop = {B2, B3, B4, B5}, header B2.
Why insist that the header dominates the tail? It guarantees that the loop has a single entry, which is what makes loop optimizations safe: code moved out of the loop can be placed in a preheader, a new block just before the header, and it will run exactly once before the loop starts.
Worked Example 2: Nested Loops
This code counts pairs (i, j) with 1 ≤ i, j ≤ n and i·j ≤ m (assume n ≥ 1; the loops are do-while style):
(1) c = 0
(2) i = 1
(3) j = 1
(4) t1 = i * j
(5) if t1 > m goto (7)
(6) c = c + 1
(7) j = j + 1
(8) if j <= n goto (4)
(9) i = i + 1
(10) if i <= n goto (3)
(11) return cLeaders: (1) first; (3) target of (10); (4) target of (8); (6) after the jump at (5); (7) target of (5); (9) after (8); (11) after (10). So leaders are 1, 3, 4, 6, 7, 9, 11, giving 7 blocks:
Block | Instructions | Successors |
|---|---|---|
B1 | (1) - (2) | B2 |
B2 | (3) | B3 |
B3 | (4) - (5) | B5 (jump), B4 (fall-through) |
B4 | (6) | B5 |
B5 | (7) - (8) | B3 (jump), B6 (fall-through) |
B6 | (9) - (10) | B2 (jump), B7 (fall-through) |
B7 | (11) | EXIT |
There are 9 edges among B1 to B7. Dominators: dom(B5) = {B1, B2, B3, B5} and dom(B6) = {B1, B2, B3, B5, B6}. The back edges and loops:
B5 → B3 (B3 dom B5): natural loop {B3, B4, B5}, the inner j-loop.
B6 → B2 (B2 dom B6): natural loop {B2, B3, B4, B5, B6}, the outer i-loop.
The inner loop is entirely contained in the outer one. Two natural loops are always either disjoint or nested, unless they share the same header (in which case they are usually combined into one loop).
Next-Use Information
When generating code for a block, the code generator needs to know whether the value in a register will be used again. If not, the register can be reused immediately. This is next-use information.
If instruction i assigns a value to x and instruction j uses x as an operand, with no assignment to x in between, then j uses the value of x computed at i, and x is live after i with next use at j.
Algorithm (One Backward Pass Over the Block)
Start with what is known at the end of the block. A common simple assumption: all program variables are live on exit (they might be used later) and temporaries are dead on exit (unless data-flow analysis says otherwise). Then scan the instructions from last to first. For each instruction i: x = y op z:
Attach to instruction i the current liveness and next-use information of x, y and z (this describes the situation after i).
Set x to "not live, no next use". Instruction i overwrites x, so whatever value x had before i is never seen by the instructions after i.
Set y and z to "live, next use = i".
The order of steps 2 and 3 matters: in a = a * b, a must end up live (it is used at i), so the "dead" update for x is done first and the "live" update for the operands second.
Worked Example 3
Variables a, b, c, d are live on exit; t1, t2, t3 are temporaries.
(1) t1 = a + b
(2) t2 = t1 * c
(3) a = t2 - t1
(4) t3 = a * a
(5) d = t3 + t2Scanning backward from (5), the information attached to each instruction is:
Instruction | x (result) | y | z |
|---|---|---|---|
(5) d = t3 + t2 | d: live, no next use in block | t3: dead | t2: dead |
(4) t3 = a * a | t3: next use (5) | a: live, no next use in block | (same a) |
(3) a = t2 - t1 | a: next use (4) | t2: next use (5) | t1: dead |
(2) t2 = t1 * c | t2: next use (3) | t1: next use (3) | c: live, no next use in block |
(1) t1 = a + b | t1: next use (2) | a: dead | b: live, no next use in block |
Two entries deserve a second look:
After (1), the variable
ais dead, even though it is a program variable: its next event is the assignment at (3), so the value from before (1) is never needed again. A register holding the oldacan be reused right after (1).After (3),
t1is dead: (3) was its last use. Its register is free from then on.
At the start of the block, the pass also tells us that a, b and c are live on entry (next uses (1), (1), (2)), while d and the temporaries are not. Liveness across blocks, computed for the whole flow graph, is the subject of Data-Flow Analysis.
Common Mistakes
Forgetting Rule 3. The instruction after a conditional jump is a leader even if nothing jumps to it.
Adding a fall-through edge after an unconditional goto. A block ending in
goto(or return) has only the jump edge.Missing the fall-through edge after a conditional jump. A block ending in
if ... gotohas two successors (unless both happen to be the same block).Making the jump instruction the start of the next block. The jump is the last instruction of its block; the leader is the instruction after it.
Calling any cycle a natural loop. A back edge needs its head to dominate its tail. A cycle that can be entered at two different points (an irreducible region) has no single header.
Running next-use forwards. Next-use information is computed in a backward pass, and x is marked dead before y and z are marked live.
Interview and Exam Questions
Q1. State the rules for finding leaders.
(1) The first instruction is a leader. (2) Every target of a conditional or unconditional jump is a leader. (3) Every instruction immediately after a conditional or unconditional jump is a leader. A block runs from a leader up to the instruction before the next leader.
Q2. Code: (1) i = 1 (2) j = 1 (3) t = i * j (4) if t > 10 goto (7) (5) j = j + 1 (6) goto (3) (7) i = i + 1 (8) if i < 5 goto (2) (9) halt. How many basic blocks and edges?
Leaders: 1 (first); 2, 3 and 7 (jump targets); 5 (after 4), 7 (after 6) and 9 (after 8). So the leaders are 1, 2, 3, 5, 7, 9, giving 6 blocks: B1 = (1), B2 = (2), B3 = (3)-(4), B4 = (5)-(6), B5 = (7)-(8), B6 = (9). Edges: B1→B2, B2→B3, B3→B5, B3→B4, B4→B3, B5→B2, B5→B6: 7 edges.
Q3. In Q2, what are the back edges and natural loops?
B4→B3: B3 dominates B4, natural loop {B3, B4}. B5→B2: B2 dominates B5, natural loop {B2, B3, B4, B5}. The first is nested inside the second.
Q4. Why is the instruction after a conditional jump a leader?
Because control can leave the block at the jump. If the next instruction were in the same block, control would not always flow through the whole block in order, breaking the definition of a basic block.
Q5. What is a back edge, and why must the header dominate the tail?
An edge a → h where h dominates a. Dominance guarantees the loop has a single entry (the header), so code can safely be placed in a preheader that runs once before the loop, which is what loop optimizations need.
Q6. What is next-use information used for?
In code generation and register allocation: if a value in a register has no next use and is not live, the register can be reused immediately without storing the value back to memory.
Q7. What is the maximum number of successors of a basic block in three-address code without switch/jump tables?
Two: the jump target and the fall-through block of a conditional jump. An unconditional jump gives one; a return gives none (or an edge to EXIT).
Summary
A basic block is a maximal straight-line run of instructions with one entry (the top) and one exit (the bottom).
Leaders: the first instruction, every jump target, every instruction right after a jump. Each block runs from a leader to just before the next leader.
A flow graph has blocks as nodes, with edges for jumps and for fall-through (except after an unconditional jump or return).
d dominates n if every path from entry to n goes through d. An edge a → h with h dom a is a back edge; its natural loop is h plus all blocks that reach a without passing through h.
Next-use information is computed by one backward pass through a block, marking the result dead and the operands live at each instruction.
Each basic block can now be studied on its own. The next chapter, DAG Representation of Basic Blocks, turns a block into a directed acyclic graph to find common subexpressions and dead code automatically.