Basic blocks, control-flow graphs and liveness

Advanced

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:

  1. the first instruction;
  2. every label (a jump may land there);
  3. 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 L or ifFalse … 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 "-")
Open in compiler

Line by line

  1. The code is the three-address code of the loop from the three-address code lesson.
  2. Leaders give four blocks: the set-up, the loop test, the loop body and the code after the loop.
  3. The test block has two successors: the body (when the condition holds) and B4 (when it does not).
  4. The body's goto L1 gives the back edge B3 → B2, which is the loop.
  5. Liveness shows that n must be supplied from outside (it is live at the start of B1), and that t1 and t2 are 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

1. Which of these is NOT a leader?
2. How many successors does a block ending in ifFalse t goto L2 have?
3. What does a back edge usually show?
4. What is live in of a block?

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.