Introduction
The optimizations of the last lesson worked on a straight block of code. Real programs have loops and branches, so the compiler first needs a map of how control can move through the code. That map is the control-flow graph (CFG). With it, a compiler can find loops to optimize, code that can never run, and, through dataflow analysis, facts such as which variables are still needed at each point, which is the key input to register allocation.
How it works
Basic blocks. A basic block is a maximal run of instructions that always executes from top to bottom: nothing jumps into its middle and nothing leaves before its end. To find them, mark the leaders:
- the first instruction;
- every label (a jump may land there);
- every instruction right after a jump (
goto,if,ifFalse).
Each block runs from one leader up to the next.
Edges. Look at each block's last instruction:
goto L: one edge, to the block that holds L;if … goto LorifFalse … goto L: two edges, to L's block and to the next block (when the condition does not jump);- anything else: an edge to the next block, or to the exit if it is the last.
An edge to an earlier block (or to the block itself) is a back edge; in code produced from structured loops, every back edge is a loop. A block that cannot be reached from the first block by following edges is unreachable and can be deleted.
Liveness. A variable is live at a point if its value may be read later before being overwritten. For each block, compute use (variables read before being assigned in the block) and def (variables assigned in it). Then:
- live out of a block = the union of live in of its successors (and, for the exit, the variables needed at the end);
- live in = use ∪ (live out − def).
Loops make these equations depend on each other in a circle, so start with empty sets and repeat over all blocks until nothing changes: the same fixed-point method used for FIRST and FOLLOW sets.
Syntax
leaders = {0} | {labels} | {i + 1 for each jump at i}
successors = {target} or {target, next} or {next}
repeat until no change:
live_in[b] = use[b] | (union(live_in[s] for s in successors[b]) - defs[b])
Example
code = """total = 0
i = 1
L1:
t1 = i < n
ifFalse t1 goto L2
t2 = i * i
total = total + t2
i = i + 1
goto L1
L2:
result = total * 2""".splitlines()
live_at_exit = {"result"}
leaders = {0}
for index, line in enumerate(code):
if line.endswith(":"):
leaders.add(index)
if line.split()[0] in ("goto", "if", "ifFalse") and index + 1 < len(code):
leaders.add(index + 1)
starts = sorted(leaders) + [len(code)]
blocks = [code[starts[k]:starts[k + 1]] for k in range(len(starts) - 1)]
EXIT = len(blocks)
block_of_label = {}
for k, block in enumerate(blocks):
for line in block:
if line.endswith(":"):
block_of_label[line[:-1]] = k
successors = []
for k, block in enumerate(blocks):
words = block[-1].split()
if words[0] == "goto":
successors.append({block_of_label[words[1]]})
elif words[0] in ("if", "ifFalse"):
successors.append({block_of_label[words[3]], k + 1})
else:
successors.append({k + 1})
def name(k):
return "exit" if k == EXIT else f"B{k + 1}"
for k, block in enumerate(blocks):
print(f"{name(k)}: " + " ; ".join(block))
print(" successors:", ", ".join(name(s) for s in sorted(successors[k])))
for s in successors[k]:
if s <= k:
print(f" back edge {name(k)} -> {name(s)}: a loop")
uses, defs = [], []
for block in blocks:
used, defined = set(), set()
for line in block:
words = line.split()
if line.endswith(":") or words[0] == "goto":
continue
if words[0] in ("if", "ifFalse", "print"):
read, written = [words[1]], None
else:
read, written = words[2:], words[0]
used |= {w for w in read if w.isidentifier() and w not in defined}
if written:
defined.add(written)
uses.append(used)
defs.append(defined)
live_in = [set() for _ in blocks]
changed = True
while changed:
changed = False
for k in reversed(range(len(blocks))):
out = set()
for s in successors[k]:
out |= live_at_exit if s == EXIT else live_in[s]
new = uses[k] | (out - defs[k])
if new != live_in[k]:
live_in[k], changed = new, True
for k in range(len(blocks)):
print(f"live at the start of {name(k)}:", " ".join(sorted(live_in[k])) or "-")Line by line
- The code is the three-address code of the loop from the three-address code lesson.
- Leaders give four blocks: the set-up, the loop test, the loop body and the code after the loop.
- The test block has two successors: the body (when the condition holds) and B4 (when it does not).
- The body's
goto L1gives the back edge B3 → B2, which is the loop. - Liveness shows that
nmust be supplied from outside (it is live at the start of B1), and thatt1andt2are never live across blocks, so they could share a register.
Expected result
B1: total = 0 ; i = 1
successors: B2
B2: L1: ; t1 = i < n ; ifFalse t1 goto L2
successors: B3, B4
B3: t2 = i * i ; total = total + t2 ; i = i + 1 ; goto L1
successors: B2
back edge B3 -> B2: a loop
B4: L2: ; result = total * 2
successors: exit
live at the start of B1: n
live at the start of B2: i n total
live at the start of B3: i n total
live at the start of B4: total
In the real world
Every optimizing compiler builds a CFG. LLVM IR is organised into basic blocks explicitly, and tools such as opt -dot-cfg draw the graph. Liveness drives register allocation; the same iterative method computes reaching definitions, available expressions and many other analyses. Static analysers such as the Clang Static Analyzer walk the CFG to find bugs like use of an uninitialised variable.
Common mistakes
- Forgetting that the instruction after a jump is a leader, which merges two blocks.
- Giving a conditional jump only one successor: it can also fall through.
- Computing liveness forwards: it depends on what happens later, so it flows backwards.
- Stopping after one pass over a loop: the sets may still grow.
Best practices
- Store the CFG explicitly (blocks and successor lists); many passes share it.
- Remove unreachable blocks before other analyses, so they do not add noise.
- Visit blocks in reverse order for backward analyses; the loop then settles in fewer passes.
Summary
Leaders split code into basic blocks, and each block's last instruction gives its edges, forming the control-flow graph. Back edges show loops, and blocks unreachable from the start can be removed. Dataflow analyses such as liveness compute facts for every block by applying an equation repeatedly until nothing changes.
Quick check
Key takeaways
- Leaders are the first instruction, every jump target and every instruction after a jump.
- A block's successors come from its last instruction: the jump target, the next block, or both.
- Liveness flows backwards: live in = used here ∪ (live out − defined here).
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.