Lesson 8.2 — Basic blocks, control-flow graphs and traversal orders¶

Techniques: basic blocks and the leaders algorithm, control-flow graphs and critical edges (and their splitting), depth-first orders (preorder, postorder, reverse postorder) · Pebble uses: PIR is written as basic blocks; every analysis from Ch 14 on walks CFGs in RPO · Lab: labs/ch08-cfg · Prerequisites: Lesson 8.1 · Time: 4–6 hours

A TAC listing (Lesson 8.1) is a flat list with jumps. Almost every analysis wants a graph instead: nodes that execute as a unit, and edges for the possible jumps. This lesson builds that graph (the control-flow graph), fixes its one troublesome kind of edge, and defines the traversal orders that the rest of the course iterates in.

1. Problem and motivation¶

The problem. Given a listing $c_0 \dots c_{n-1}$ (Definition 8.1.2), partition it into the largest pieces that always execute from start to end, connect the pieces by the jumps between them, and number the pieces so that "earlier" means "before, unless a loop brings you back".

Basic blocks and the leaders algorithm¶

A basic block is a maximal straight-line run: control enters only at its first instruction and leaves only after its last. Treating a block as one node shrinks the graph (the running example has 19 instructions and 10 blocks) and makes local reasoning (Lesson 8.3) sound. The one-pass leaders algorithm is in every compiler textbook [Dragon2, §8.4.1; EaC3, Ch. 4]. Allen's 1970 paper made basic blocks and flow graphs the foundation of control-flow analysis [All70].

Control-flow graphs and critical edges¶

The control-flow graph (CFG) has the blocks as nodes and an edge $u \to v$ when control can pass from the end of $u$ to the start of $v$. One kind of edge causes trouble: a critical edge leaves a block with several successors and enters a block with several predecessors. No existing block can hold code that runs only on that edge (Lemma 8.2.11). Out-of-SSA translation (Ch 16), partial redundancy elimination (Ch 17) and register allocation (Ch 22) all need to place code on edges, so compilers split critical edges. LLVM's break-crit-edges pass and Swift's mandatory critical-edge splitting [SIL-Docs] are two examples.

Depth-first orders¶

A depth-first search (DFS) from the entry numbers blocks in preorder (on discovery) and postorder (when finished). Reversing the postorder gives reverse postorder (RPO), which puts every block before its successors except along loop back edges (Theorem 8.2.14). This is why forward dataflow analyses converge fastest in RPO (Ch 14), why dominator algorithms process blocks in RPO (Ch 15), and why LLVM ships a ReversePostOrderTraversal class [LLVM-RPOT]. Tarjan's paper introduced the DFS numbering and edge classification used here [Tar72].

2. Definitions and algorithms¶

Definition 8.2.1 (Jumps, targets, fall-through)

In a listing $c_0 \dots c_{n-1}$ (Definition 8.1.2), $c_i$ is a jump if it is goto, if, ifz or return. Its targets $T(i)$ are the positions of the labels it names (none for return). It falls through to $i+1$ unless it is goto or return. A listing is closed if every named label exists and $c_{n-1}$ does not fall through. (The lab's TAC reader accepts only closed listings.) An execution is the sequence of positions $p_0 = 0, p_1, \dots$ visited by the semantics.

Basic blocks and the leaders algorithm¶

Definition 8.2.2 (Basic block)

A basic block of a closed listing is an interval $[s, e]$ of positions such that (i) no instruction $c_i$ with $s \le i < e$ is a jump, and (ii) no position $j$ with $s < j \le e$ is the target of any jump. A partition of $\{0, \dots, n-1\}$ into basic blocks is maximal if no two consecutive blocks $[s, e]$, $[e+1, e']$ can be merged into the basic block $[s, e']$.

Algorithm 8.2.3 (Leaders)

Input: a closed listing $c_0 \dots c_{n-1}$, $n \ge 1$.
Output: the sorted leaders $\ell_0 = 0 < \ell_1 < \dots < \ell_{m-1}$ and the blocks $[\ell_k, \ell_{k+1} - 1]$ (the last one ends at $n - 1$).
Precondition: the label table (label to position) has been built.
Postcondition: the blocks form the unique maximal partition into basic blocks (Theorem 8.2.9).
Invariant: after scanning $c_0 \dots c_i$, the set $\mathit{Lead}$ contains $0$, every target of $c_0 \dots c_i$, and every $j + 1 \le i + 1$ with $c_j$ a jump, $j \le i$.

function Leaders(c[0..n)):
    Lead ← {0}                                      # rule 1: the first instruction
    for i in 0 .. n-1:
        for t in T(i): Lead ← Lead ∪ {t}           # rule 2: a jump target
        if c[i] is a jump and i + 1 < n:
            Lead ← Lead ∪ {i + 1}                   # rule 3: after a jump
    ℓ ← sort(Lead)
    blocks ← [ (ℓ[k], ℓ[k+1] - 1) for k in 0 .. |ℓ|-2 ] + [ (ℓ[|ℓ|-1], n - 1) ]
    return ℓ, blocks

Control-flow graphs and critical edges¶

Definition 8.2.4 (Control-flow graph of a listing)

Let $B_0, \dots, B_{m-1}$ be the blocks of Algorithm 8.2.3 in order, $B_k = [\ell_k, e_k]$. The CFG is $G = (N, E, r)$ with $N = \{B_0, \dots, B_{m-1}\}$, entry $r = B_0$, and $B_k \to B_j \in E$ iff $\ell_j \in T(e_k)$, or $c_{e_k}$ falls through and $j = k + 1$. The successor list of $B_k$ is ordered: the jump target first, then the fall-through block, with duplicates removed. (This order matters for DFS.) $\mathrm{preds}(v)$ and $\mathrm{succs}(v)$ are as in NOTATION.md §3.

Definition 8.2.5 (Critical edge; splitting)

An edge $u \to v$ is critical if $\lvert \mathrm{succs}(u) \rvert > 1$ and $\lvert \mathrm{preds}(v) \rvert > 1$. Splitting $u \to v$ adds a new block $x$ and replaces the edge by $u \to x \to v$, where $x$ contains only a jump to $v$.

Algorithm 8.2.6 (Split every critical edge of a listing)

Input: a closed listing $L$ with CFG $G = (N, E, r)$ (Definition 8.2.4).
Output: a closed listing $L'$ whose CFG is $G$ with every critical edge split.
Precondition: the critical edges $C \subseteq E$ are computed on $G$ (not updated during the loop).
Postcondition: $L'$ has no critical edge; $\lvert N' \rvert = \lvert N \rvert + \lvert C \rvert$ and $\lvert E' \rvert = \lvert E \rvert + \lvert C \rvert$; $L'$ and $L$ return the same value (Theorem 8.2.12).
Invariant: every edge already processed is either not critical in $G$ or has been replaced by a path through a new block whose only instruction is goto.

function SplitCriticalEdges(L):
    (G, blocks) ← CFG(L); C ← { u→v ∈ E : |succs(u)| > 1 and |preds(v)| > 1 }
    appended ← []; after ← empty map
    for each block u whose last instruction j = c[e_u] is `if a goto L` or `ifz a goto L`:
        taken ← block of L; fall ← the block after u
        if u→taken ∈ C:
            x ← FreshLabel(); appended.add( x: goto LabelOf(taken) )
            retarget j to x                           # u → x → taken
        if fall ≠ taken and u→fall ∈ C:
            after[e_u] ← goto LabelOf(fall)          # a new block right after u
    return L with after[i] inserted after position i, then appended at the end
# LabelOf(b) returns b's first label, adding a fresh one if b has none.
# A `goto` or `return` block has one successor at most, so only if/ifz blocks are sources.

Depth-first orders¶

Definition 8.2.7 (DFS, pre-, post- and reverse postorder, edge kinds)

Let $G = (N, E, r)$ have ordered successor lists. The DFS from $r$ is Visit(r) with Visit(n): mark $n$; append $n$ to the preorder; for each $s \in \mathrm{succs}(n)$ in order, if $s$ is unmarked, Visit(s); append $n$ to the postorder. $\mathrm{pre}(n)$ and $\mathrm{post}(n)$ are the positions (from 0) in these sequences. Reverse postorder is the postorder reversed: $\mathrm{rpo}(n) = \lvert N_r \rvert - 1 - \mathrm{post}(n)$, where $N_r$ is the set of nodes reachable from $r$. An edge $u \to v$ between reachable nodes is a tree edge if Visit(u) called Visit(v). Otherwise it is a back edge if $v$ is an ancestor of $u$ in the DFS tree $T$ ($v \preceq_T u$, including $u = v$), a forward edge if $u \prec_T v$, and a cross edge otherwise.

Algorithm 8.2.8 (Iterative DFS with orders and edge kinds)

Input: $G = (N, E, r)$ with ordered successor lists.
Output: preorder, postorder, RPO of the nodes reachable from $r$, and the kind of every edge between reachable nodes.
Precondition: none (any graph, reducible or not).
Postcondition: the output equals that of the recursive Visit of Definition 8.2.7.
Invariant: the stack holds exactly the nodes whose Visit has started but not finished, in call order, each with the index of the next successor to try. A node is on the stack iff it is an ancestor of the node on top (the "gray" nodes).

function DFS(G = (N, E, r)):
    pre ← []; post ← []; kind ← {}; onStack ← {}
    Enter(r)
    while stack is not empty:
        (n, i) ← top(stack)
        if i < |succs(n)|:
            top(stack).i ← i + 1; s ← succs(n)[i]
            if s not in pre:  kind[n→s] ← tree; Enter(s)
            else if s ∈ onStack: kind[n→s] ← back
            else if index of s in pre > index of n in pre: kind[n→s] ← forward
            else: kind[n→s] ← cross
        else:
            pop(stack); onStack ← onStack \ {n}; append n to post
    return pre, post, reverse(post), kind

function Enter(n): append n to pre; onStack ← onStack ∪ {n}; push (n, 0) on stack

3. Worked example¶

The running example's TAC (Lesson 8.1 §3, labs/ch08-cfg/inputs/euler1.tac).

Leaders on the running example¶

One pass over the 19 instructions; each row is one rule firing (from tools/course/lib/irforms.py, leaders(listing, trace)):

step	instruction	rule
1	0	first instruction
2	18	target of `ifz t.0 goto L.1` at 4
3	5	follows the jump `ifz t.0 goto L.1` at 4
4	13	target of `if t.3 goto L.4` at 7
5	8	follows the jump `if t.3 goto L.4` at 7
6	13	target of `if t.5 goto L.4` at 10
7	11	follows the jump `if t.5 goto L.4` at 10
8	14	target of `goto L.5` at 12
9	13	follows the jump `goto L.5` at 12
10	16	target of `ifz t.1 goto L.3` at 14
11	15	follows the jump `ifz t.1 goto L.3` at 14
12	3	target of `goto L.0` at 17
13	18	follows the jump `goto L.0` at 17

Leaders (sorted): 0 3 5 8 11 13 14 15 16 18, so ten blocks:

block	instructions	last instruction	successors (target first)
B0	0..2	`i = 1`	B1 (falls through)
B1	3..4	`ifz t.0 goto L.1`	B9, B2
B2	5..7	`if t.3 goto L.4`	B5, B3
B3	8..10	`if t.5 goto L.4`	B5, B4
B4	11..12	`goto L.5`	B6
B5	13..13	`t.1 = 1`	B6 (falls through)
B6	14..14	`ifz t.1 goto L.3`	B8, B7
B7	15..15	`s = add s, i`	B8 (falls through)
B8	16..17	`goto L.0`	B1
B9	18..18	`return s`	none

flowchart TD
  B0([B0]) --> B1[B1]
  B1 --> B9[B9]
  B1 --> B2[B2]
  B2 --> B5[B5]
  B2 --> B3[B3]
  B3 --> B5
  B3 --> B4[B4]
  B4 --> B6[B6]
  B5 --> B6
  B6 --> B8[B8]
  B6 --> B7[B7]
  B7 --> B8
  B8 --> B1

Critical edges on the running example¶

edge	$\lvert\mathrm{succs}(u)\rvert$	$\lvert\mathrm{preds}(v)\rvert$	critical?
B0→B1	1	2	no
B1→B9	2	1	no
B1→B2	2	1	no
B2→B5	2	2	yes
B2→B3	2	1	no
B3→B5	2	2	yes
B3→B4	2	1	no
B4→B6	1	2	no
B5→B6	1	2	no
B6→B8	2	2	yes
B6→B7	2	1	no
B7→B8	1	2	no
B8→B1	1	2	no

Algorithm 8.2.6 handles all three as taken edges: it retargets if t.3 goto L.4 to crit.0, if t.5 goto L.4 to crit.1 and ifz t.1 goto L.3 to crit.2, then appends crit.0: goto L.4, crit.1: goto L.4, crit.2: goto L.3. The new listing has 22 instructions and 13 blocks, the report of ch08-cfg ends in critical: (none), and it still returns 33 (ch08-cfg --split euler1.tac | ch08-run --form=tac -; the lab's lit test tests/ch08/lit/cfg-split.test).

DFS orders on the running example¶

Every event of Algorithm 8.2.8 (successors in the order of the table above; tree edges show up as the following "visit" row):

#	event	DFS stack (bottom→top)	preorder so far	postorder so far
1	visit B0	B0	B0
2	visit B1	B0 B1	B0 B1
3	visit B9	B0 B1 B9	B0 B1 B9
4	finish B9	B0 B1	B0 B1 B9	B9
5	visit B2	B0 B1 B2	B0 B1 B9 B2	B9
6	visit B5	B0 B1 B2 B5	… B2 B5	B9
7	visit B6	B0 B1 B2 B5 B6	… B5 B6	B9
8	visit B8	B0 B1 B2 B5 B6 B8	… B6 B8	B9
9	edge B8→B1: B1 is on the stack → back	B0 B1 B2 B5 B6 B8		B9
10	finish B8	B0 B1 B2 B5 B6		B9 B8
11	visit B7	B0 B1 B2 B5 B6 B7	… B8 B7	B9 B8
12	edge B7→B8: finished, not a descendant → cross	B0 B1 B2 B5 B6 B7		B9 B8
13	finish B7	B0 B1 B2 B5 B6		B9 B8 B7
14	finish B6	B0 B1 B2 B5		B9 B8 B7 B6
15	finish B5	B0 B1 B2		… B6 B5
16	visit B3	B0 B1 B2 B3	… B7 B3	… B5
17	edge B3→B5: cross	B0 B1 B2 B3
18	visit B4	B0 B1 B2 B3 B4	… B3 B4
19	edge B4→B6: cross	B0 B1 B2 B3 B4
20	finish B4	B0 B1 B2 B3		… B5 B4
21	finish B3	B0 B1 B2		… B4 B3
22	finish B2	B0 B1		… B3 B2
23	finish B1	B0		… B2 B1
24	finish B0	(empty)	B0 B1 B9 B2 B5 B6 B8 B7 B3 B4	B9 B8 B7 B6 B5 B4 B3 B2 B1 B0

preorder: B0 B1 B9 B2 B5 B6 B8 B7 B3 B4
postorder: B9 B8 B7 B6 B5 B4 B3 B2 B1 B0
RPO: B0 B1 B2 B3 B4 B5 B6 B7 B8 B9
back: B8→B1; forward: none; cross: B3→B5, B4→B6, B7→B8.

Preorder visits the exit B9 third, and RPO puts it last. Every edge except the back edge B8→B1 goes forward in RPO (Theorem 8.2.14). Here RPO happens to equal the layout order, because Algorithm 8.1.4 emits structured code in source order. LLVM's layout differs (the RPO box in §7).

The edge cases (labs/ch08-cfg/inputs/edges.tac)

 0  x = 3                        6  if x goto next
 1  y = 0                        7  ifz y goto done
unused:                          8  y = add y, 100
 2  y = add y, 1                done:
 3  if x goto next               9  return y
next:                           dead:
 4  x = sub x, 1                10  y = 7
 5  y = add y, x                11  goto done

Leaders 0 4 7 8 9 10. The label unused is not a leader: no jump names it, so instructions 1 and 2 stay in one block (maximality, Theorem 8.2.9). Instruction 3 jumps to its own fall-through, which gives one edge B0→B1 (Definition 8.2.4 removes the duplicate). B1 = [4, 6] has the self-loop B1→B1, a back edge. The unreachable block B5 = [10, 11] appears in the block list but not in any order, and its edge B5→B4 still makes B2→B4 critical. The self-loop B1→B1 is critical too (B1 has two successors and two predecessors).

Try it

./course drill leaders --seed 5 --difficulty hard --solution (leaders, successors and critical edges of a random listing), and ./course drill traversal-orders --seed 3 --difficulty medium --solution (the same DFS trace as above on a random CFG; traversal-orders is an alias of the rpo drill that Chapter 15 also uses).

4. Invariants and correctness¶

Basic blocks and the leaders algorithm¶

Theorem 8.2.9 (The leaders partition is the unique maximal basic-block partition)

For a closed listing, the intervals produced by Algorithm 8.2.3 (a) partition $\{0, \dots, n-1\}$, (b) are basic blocks (Definition 8.2.2), and (c) form a maximal partition. (d) Every partition of the listing into basic blocks refines it: each of its blocks lies inside one leaders block.

Proof

(a) The leaders are sorted, and $\ell_0 = 0$ because of rule 1. The intervals $[\ell_k, \ell_{k+1} - 1]$ and $[\ell_{m-1}, n - 1]$ are consecutive and cover $0 \dots n-1$. (b) Take a block $[s, e]$ and $s \le i < e$. If $c_i$ were a jump, rule 3 would make $i + 1$ a leader, with $s < i + 1 \le e$, contradicting the fact that the block contains no leader other than $s$. So condition (i) holds. If some $j$ with $s < j \le e$ were a target, rule 2 would make $j$ a leader. So (ii) holds. (c) Take consecutive blocks $[s, e]$ and $[e + 1, e']$. Their boundary $e + 1$ is a leader other than $0$, so it was added by rule 2 (then $e + 1$ is a target inside $[s, e']$, violating (ii)) or by rule 3 (then $c_e$ is a jump with $e < e'$, violating (i)). Either way the merge is not a basic block. (d) Let $P$ be any partition into basic blocks and $[a, b] \in P$. Suppose some leader $\ell$ satisfies $a < \ell \le b$. Rule 1 does not apply ($\ell > 0$). Rule 2 makes $\ell$ a target inside $[a, b]$, violating (ii). Rule 3 makes $c_{\ell-1}$ a jump with $a \le \ell - 1 < b$, violating (i). So $[a, b]$ contains no leader except possibly $a$ and lies inside the leaders block that starts at the last leader $\le a$. By (d), a maximal partition cannot be strictly finer than the leaders partition (some two of its blocks would lie in one leaders block and could be merged), so the maximal partition is unique.

Lemma 8.2.10 (Blocks execute as units; executions are CFG paths)

In every execution, whenever position $\ell_k$ (the start of $B_k$) is visited, the next $e_k - \ell_k$ steps visit $\ell_k + 1, \dots, e_k$ in order (unless the program stops at a return). The sequence of blocks entered is a path in the CFG starting at $B_0$.

Proof

By Definition 8.2.2(i), no instruction before $e_k$ in the block is a jump, so each one falls through to the next. The step after $e_k$ goes to a target of $c_{e_k}$ or to $e_k + 1$ (if it falls through). Both positions are leaders: a target by rule 2, and $e_k + 1$ is $\ell_{k+1}$ because the blocks are consecutive. The block started there is a successor of $B_k$ by Definition 8.2.4. Induction on the number of blocks entered gives the path, starting at $B_0$ because execution starts at 0.

Control-flow graphs and critical edges¶

Lemma 8.2.11 (Why a critical edge needs a new block)

Let $u \to v$ be critical. Code placed at the end of $u$ (before its jump) also runs on some other edge $u \to w$ with $w \ne v$. Code placed at the start of $v$ also runs on some other edge $x \to v$ with $x \ne u$. So no existing block can hold code that executes exactly when control traverses $u \to v$.

Proof

Since $\lvert \mathrm{succs}(u) \rvert > 1$, there is a successor $w \neq v$ (successor lists have no duplicates), and every execution that leaves $u$ toward $w$ runs the end of $u$. Since $\lvert \mathrm{preds}(v) \rvert > 1$, there is a predecessor $x \ne u$, and every entry into $v$ from $x$ runs the start of $v$. Any other block is not on every traversal of $u \to v$, because traversing the edge enters $v$ directly after leaving $u$ (Lemma 8.2.10).

Theorem 8.2.12 (Algorithm 8.2.6 is correct)

For a closed listing $L$ with critical edges $C$, Algorithm 8.2.6 returns a closed listing $L'$ that (a) returns the same value as $L$ on every run, (b) has CFG $G'$ equal to $G$ with every edge $u \to v \in C$ replaced by $u \to x_{uv} \to v$ for a fresh block $x_{uv}$, and (c) has no critical edge.

Proof

(a) Each change inserts a block whose only instruction is goto L_v. A retargeted jump now reaches crit.k: goto L_v, which transfers to the same position as before in one extra step. An inserted fall-through goto L_fall executes exactly when the branch falls through and then transfers to the old fall-through position. No variable changes, so the value returned is the same. The appended blocks come after the final instruction of $L$, which is a goto or return (closedness), so nothing falls into them, and each ends in goto, so $L'$ is closed. (b) The new instructions are jumps, and each is preceded by a jump or carries a fresh label that is a jump target. So by rules 2 and 3 each is its own leader and its own block, and the old blocks keep their extents. Old edges not in $C$ are unchanged, and each $u \to v \in C$ now passes through its new block, which has exactly one predecessor and one successor. (c) An edge of $G'$ is an old non-critical edge (its endpoints' degrees are unchanged: in each critical edge replaced at $u$ or $v$, one edge was swapped for another), or $u \to x$ with $\lvert\mathrm{preds}(x)\rvert = 1$, or $x \to v$ with $\lvert\mathrm{succs}(x)\rvert = 1$. None is critical.

Depth-first orders¶

Lemma 8.2.13 (Postorder decreases along every edge that is not a back edge)

For every edge $u \to v$ between reachable nodes: if it is not a back edge, then $\mathrm{post}(v) < \mathrm{post}(u)$. If it is a back edge, then $\mathrm{post}(v) \ge \mathrm{post}(u)$.

Proof

Consider the moment Algorithm 8.2.8 examines $u \to v$, while $u$ is on top of the stack. Case 1: $v$ is unvisited. Then $u \to v$ is a tree edge, $v$ is pushed and finishes before $u$ resumes, so $\mathrm{post}(v) < \mathrm{post}(u)$. Case 2: $v$ is on the stack. Then $v$ is an ancestor of $u$ (invariant of Algorithm 8.2.8), so this is a back edge, and $v$ finishes after $u$ or is $u$ itself, so $\mathrm{post}(v) \ge \mathrm{post}(u)$. Case 3: $v$ was visited and is no longer on the stack. Then $v$ has already finished, while $u$ has not, so $\mathrm{post}(v) < \mathrm{post}(u)$. The edge is forward or cross, not back, because back edges are exactly case 2 (an ancestor of $u$ is still on the stack).

Theorem 8.2.14 (RPO is a topological order of the graph without its back edges)

Let $G_r$ be the subgraph of $G$ induced by the nodes reachable from $r$, and let $A$ be $G_r$ minus the DFS back edges. Then $A$ is acyclic, and for every edge $u \to v$ of $A$, $\mathrm{rpo}(u) < \mathrm{rpo}(v)$. In particular the entry comes first in RPO, and if $G$ is acyclic, RPO is a topological order of $G_r$.

Proof

By Lemma 8.2.13, every edge $u \to v$ of $A$ has $\mathrm{post}(v) < \mathrm{post}(u)$, so $\mathrm{rpo}(u) = \lvert N_r \rvert - 1 - \mathrm{post}(u) < \lvert N_r \rvert - 1 - \mathrm{post}(v) = \mathrm{rpo}(v)$. A cycle $u_1 \to u_2 \to \dots \to u_1$ in $A$ would give $\mathrm{rpo}(u_1) < \mathrm{rpo}(u_2) < \dots < \mathrm{rpo}(u_1)$, a contradiction, so $A$ is acyclic. The entry $r$ is the last node to finish, so $\mathrm{post}(r) = \lvert N_r \rvert - 1$ and $\mathrm{rpo}(r) = 0$. If $G$ is acyclic it has no back edges (a back edge $u \to v$ with $v \preceq_T u$ closes a cycle through tree edges), so $A = G_r$.

Corollary 8.2.15 (Every cycle contains a back edge; RPO is not preorder)

(a) Every cycle of $G_r$ contains at least one DFS back edge. (b) Preorder is not a topological order of $A$ in general: in the running example, the cross edge B7→B8 has $\mathrm{pre}(B7) = 7 > 6 = \mathrm{pre}(B8)$.

Proof

(a) Otherwise the whole cycle lies in $A$, which Theorem 8.2.14 shows is acyclic. (b) The preorder of §3 is B0 B1 B9 B2 B5 B6 B8 B7 B3 B4, which puts B8 (position 6) before B7 (position 7), yet B7→B8 is an edge of $A$. Cross edges always point from a later-visited subtree to an earlier one in preorder. RPO puts B7 (position 7) before B8 (position 8).

Back edges depend on the DFS — unless the CFG is reducible

Which edges are back edges depends on the successor order in general. For reducible CFGs (all of the running examples, all Tiny and PIR programs from structured sources) the back edges are the same for every DFS: exactly the edges whose target dominates their source. Chapter 15 proves this (Theorem 15.6.4 in Lesson 15.6).

5. Complexity¶

Variables: $n$ = instructions, $m = \lvert N \rvert$ blocks, $e = \lvert E \rvert$ edges ($e \le 2m$ for TAC, since a block has at most two successors), $c$ = number of critical edges.

Technique	Time (worst)	Time (typical)	Space	Justification
Leaders (Alg. 8.2.3)	$O(n + m \log m)$; $O(n)$ with a boolean array instead of sorting	$O(n)$	$O(n)$ label table	one pass, $O(1)$ per instruction with a hash map of labels
CFG construction	$O(n)$	$O(n)$	$O(m + e)$	one lookup per block's last instruction
Critical edges and splitting (Alg. 8.2.6)	$O(n + e)$	$O(n)$	$c$ new blocks	in-degrees in one pass; $O(1)$ per edge; $c \le e$
DFS orders (Alg. 8.2.8)	$\Theta(m + e)$	same	$O(m)$ stack	each node entered once, each edge examined once

Pathological family. The listing $\mathsf{if}\ x\ \mathsf{goto}\ L_0; \mathsf{if}\ x\ \mathsf{goto}\ L_1; \dots$ where every instruction is a jump makes every instruction a leader: $m = n$. The CFG is then no smaller than the listing, and a chain of $n$ conditional jumps all targeting one label $L$ gives $n$ critical edges into $L$, so splitting doubles the number of blocks. For DFS, a chain of $m$ blocks makes the recursive formulation $m$ frames deep. This is why Algorithm 8.2.8 and LLVM's po_iterator keep an explicit stack instead of recursing (a 100 000-block function is realistic in generated code).

At scale. Splitting all critical edges can add many blocks. That is why LLVM splits lazily, only the edges a pass needs (SplitCriticalEdge [LLVM-BCE]), while Swift SIL splits eagerly only for terminators that cannot carry block arguments (§7).

Basic blocks and the leaders algorithm¶

Extended basic blocks (a tree of blocks in which each non-root block has one predecessor) enlarge the scope of local optimizations such as value numbering (superlocal VN, [EaC3, Ch. 8]) without needing dataflow. The trade-off: a tree, not a path, must be tracked.
Traces and superblocks (Fisher's trace scheduling; superblocks = traces with a single entry) optimize along a likely path and duplicate code to remove side entrances (Ch 23). The trade-off is code growth.
Exceptions. Instructions that may throw end a block in some IRs (LLVM invoke), or blocks carry "abnormal" exceptional edges (GCC). The trade-off: more, smaller blocks versus special edges every analysis must respect.

Control-flow graphs and critical edges¶

Lazy splitting (LLVM SplitCriticalEdge on demand; GCC split_critical_edges when a pass requires it) keeps the CFG small until code must be placed on an edge [LLVM-BCE; GCC-TreeCFG].
Block arguments instead of edge code (Lesson 8.4): an edge's parallel copy is written in the branch, so many clients (for example SSA destruction in MLIR and Cranelift) never need a separate block. A critical edge whose two branch operands differ still needs splitting when lowering to phi (Lemma 8.4.11).
Multi-edges. Some IRs keep duplicate edges (LLVM allows br i1 %c, label %a, label %a and a switch with several cases to one block). Then phi nodes must list the predecessor once per edge with equal values. Definition 8.2.4 deduplicates instead.

Depth-first orders¶

Postorder on the reverse CFG (from the exit) is the right order for backward problems such as liveness (Ch 14). Note that the reverse graph's RPO is not the forward postorder in general.
Iterative worklists in RPO priority (Ch 14) process each block once per pass in RPO. On reducible graphs this bounds the number of passes by the loop-connectedness $d(G) + 2$ [Dragon2, §9.6].
Numbered DFS intervals ($\mathrm{pre}$, $\mathrm{post}$) give $O(1)$ ancestor tests: $u \preceq_T v$ iff $\mathrm{pre}(u) \le \mathrm{pre}(v)$ and $\mathrm{post}(v) \le \mathrm{post}(u)$. LLVM's dominator tree uses the same trick with its {in,out} numbers (Ch 15).

7. In real compilers¶

Basic blocks and the leaders algorithm¶

GCC partitions GIMPLE into blocks in make_blocks and connects them in make_edges, both in gcc/tree-cfg.cc (build_gimple_cfg; gcc 15.1) [GCC-TreeCFG]. LLVM IR is written directly as basic blocks. Every block must end in exactly one terminator, which the IR verifier checks (llvm/lib/IR/Verifier.cpp) [LLVM-LangRef]. PIR blocks are numbered bb0, bb1, … and each ends in exactly one terminator (pir-spec §6).

GCC's CFG dump: the leaders of the GIMPLE listing

Reproduce (gcc 14.2.0; euler1.c as in Lesson 8.1's GIMPLE box):

gcc-14 -O0 -c -fdump-tree-cfg=stdout euler1.c -o /dev/null

Output (the function body; the ;; Function header, loop summary and ;; N succs { … } lines that precede it are omitted):

long int euler1 (long int n)
{
  long int i;
  long int s;
  long int D.2781;

  <bb 2> :
  s = 0;
  i = 1;
  goto <bb 7>; [INV]

  <bb 3> :
  _1 = i % 3;
  if (_1 == 0)
    goto <bb 5>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 4> :
  _2 = i % 5;
  if (_2 == 0)
    goto <bb 5>; [INV]
  else
    goto <bb 6>; [INV]

  <bb 5> :
  s = s + i;

  <bb 6> :
  i = i + 1;

  <bb 7> :
  if (i <= n)
    goto <bb 3>; [INV]
  else
    goto <bb 8>; [INV]

  <bb 8> :
  D.2781 = s;

  <bb 9> :
<L6>:
  return D.2781;

}

What to notice: the GIMPLE listing of Lesson 8.1 cut at its leaders: every label that is a jump target starts a block, and every instruction after a goto or if starts one. Blocks 0 and 1 are GCC's artificial entry and exit. bb 9 exists only because the return carries a label (<L6>), which GCC treats as a leader. Algorithm 8.2.3 would merge it into bb 8 because nothing jumps to it (Theorem 8.2.9(c)), and GCC's later cfgcleanup does the same. [INV] means "no profile count yet".

Control-flow graphs and critical edges¶

LLVM: isCriticalEdge in llvm/lib/Analysis/CFG.cpp, SplitCriticalEdge and the break-crit-edges pass (BreakCriticalEdgesPass::run) in llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp (LLVM 23.1.2) [LLVM-BCE]. GCC: split_critical_edges in gcc/tree-cfg.cc [GCC-TreeCFG]. Swift: swift::splitCriticalEdge in lib/SILOptimizer/Utils/CFGOptUtils.cpp (swift-6.1-RELEASE) [SWIFT-CFGOpt]. Swift's SIL documentation lists critical-edge splitting among the mandatory passes, for "terminators that don't support arbitrary basic block arguments (all non cond_branch terminators)" [SIL-Docs].

LLVM splits the three critical edges of the running example

Reproduce (clang 23.1.2, opt 23.1.2):

clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm euler1.c -o euler1.O0.ll
opt -passes=sroa -S euler1.O0.ll -o euler1.ssa.ll
opt -passes=break-crit-edges -S euler1.ssa.ll | sed -n '/define/,/^}/p'

Output (complete function):

define dso_local i64 @euler1(i64 noundef %n) #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %s.0 = phi i64 [ 0, %entry ], [ %s.1, %for.inc ]
  %i.0 = phi i64 [ 1, %entry ], [ %inc, %for.inc ]
  %cmp = icmp sle i64 %i.0, %n
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %rem = srem i64 %i.0, 3
  %cmp1 = icmp eq i64 %rem, 0
  br i1 %cmp1, label %for.body.if.then_crit_edge, label %lor.lhs.false

for.body.if.then_crit_edge:                       ; preds = %for.body
  br label %if.then

lor.lhs.false:                                    ; preds = %for.body
  %rem2 = srem i64 %i.0, 5
  %cmp3 = icmp eq i64 %rem2, 0
  br i1 %cmp3, label %lor.lhs.false.if.then_crit_edge, label %lor.lhs.false.if.end_crit_edge

lor.lhs.false.if.end_crit_edge:                   ; preds = %lor.lhs.false
  br label %if.end

lor.lhs.false.if.then_crit_edge:                  ; preds = %lor.lhs.false
  br label %if.then

if.then:                                          ; preds = %lor.lhs.false.if.then_crit_edge, %for.body.if.then_crit_edge
  %add = add nsw i64 %s.0, %i.0
  br label %if.end

if.end:                                           ; preds = %lor.lhs.false.if.end_crit_edge, %if.then
  %s.1 = phi i64 [ %add, %if.then ], [ %s.0, %lor.lhs.false.if.end_crit_edge ]
  br label %for.inc

for.inc:                                          ; preds = %if.end
  %inc = add nsw i64 %i.0, 1
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  ret i64 %s.0
}

What to notice: clang lowers || as jumping code, so its CFG differs from ours, but it has three critical edges as well: for.body→if.then, lor.lhs.false→if.then and lor.lhs.false→if.end. Each gets a …_crit_edge block with a single br, which is Definition 8.2.5's splitting, and the phi in if.end now names the new block as its predecessor. That block is where an out-of-SSA copy %s.1 ← %s.0 can go (Lemma 8.2.11).

Depth-first orders¶

LLVM: post_order and ReversePostOrderTraversal in llvm/include/llvm/ADT/PostOrderIterator.h, an explicit-stack DFS over any graph with GraphTraits (LLVM 23.1.2) [LLVM-RPOT]. GCC: post_order_compute and pre_and_rev_post_order_compute in gcc/cfganal.cc [GCC-CFGAnal]. GCC's value numbering is even named for the order: do_rpo_vn in gcc/tree-ssa-sccvn.cc.

LLVM's own postorder and RPO of the running example

Reproduce (clang++ 23.1.2 against the LLVM 23.1.2 libraries; euler1.ssa.ll from the previous box):

cat > rpo.cpp <<'EOF'
// Print LLVM's own DFS orders for every function in a module.
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IRReader/IRReader.h"
#include "llvm/Support/SourceMgr.h"
#include "llvm/Support/raw_ostream.h"

int main(int argc, char **argv) {
  llvm::LLVMContext Ctx;
  llvm::SMDiagnostic Err;
  auto M = llvm::parseIRFile(argv[1], Err, Ctx);
  if (!M) { Err.print(argv[0], llvm::errs()); return 1; }
  for (llvm::Function &F : *M) {
    if (F.isDeclaration()) continue;
    llvm::outs() << F.getName() << "\n  postorder:";
    for (llvm::BasicBlock *BB : llvm::post_order(&F))
      llvm::outs() << " " << BB->getName();
    llvm::outs() << "\n  rpo:      ";
    llvm::ReversePostOrderTraversal<llvm::Function *> RPOT(&F);
    for (llvm::BasicBlock *BB : RPOT)
      llvm::outs() << " " << BB->getName();
    llvm::outs() << "\n";
  }
}
EOF
clang++-23 -std=c++23 $(llvm-config --cxxflags) rpo.cpp $(llvm-config --ldflags --libs core irreader support) -Wl,-rpath,$(llvm-config --libdir) -o rpo
./rpo euler1.ssa.ll

Output (complete):

euler1
  postorder: for.inc if.end if.then lor.lhs.false for.body for.end for.cond entry
  rpo:       entry for.cond for.end for.body lor.lhs.false if.then if.end for.inc

What to notice: LLVM visits a br instruction's successors in operand order (for.body before for.end). The whole loop body finishes first, so the exit block for.end lands third in RPO, before the loop body, although it is last in the file. Every non-back edge still goes forward in this order (Theorem 8.2.14). The only back edge is for.inc→for.cond. (On Linux with the course's conda LLVM, add --gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14 -Wl,-rpath,$(llvm-config --libdir).)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Basic blocks and the leaders algorithm	exact: the unique maximal partition (Theorem 8.2.9)	$O(n)$ · one pass; 19 instructions → 10 blocks on the running example	blocks named by their leaders; unreferenced labels vanish	very low	every compiler that starts from a linear IR (GCC's `make_blocks`, JVM and Wasm JITs)
Control-flow graphs and critical edges	exact successor relation; splitting adds one block per critical edge	$O(n + e)$ · 3 critical edges, 10 → 13 blocks on the running example	a new block per split edge (`…_crit_edge` in LLVM)	low	every optimizer; splitting before out-of-SSA, PRE, code placement
Depth-first orders	RPO is a topological order modulo back edges (Theorem 8.2.14)	$\Theta(m + e)$ · linear, explicit stack	three sequences plus an edge classification	low (iterative DFS needs care)	dataflow iteration order, dominators, SSA construction, scheduling

Choose the leaders algorithm whenever you start from a linear IR, since it is cheap and gives the unique answer. Split critical edges before any transformation that places code on edges (out-of-SSA copies, PRE insertions, spill code), and preferably only the edges it needs. Iterate in RPO for forward problems, in postorder of the reverse CFG for backward ones, and never in preorder (Corollary 8.2.15).

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch08.yaml`)	Drill	Flashcard tag	Exercises
Basic blocks and the leaders algorithm	`leaders-listing`, `leader-unreferenced-label`	`./course drill leaders`	`leaders`	L2 (R1–R2)
Control-flow graphs and critical edges	`critical-edges-set`, `split-count`, `llvm-where-critical`	`./course drill leaders --difficulty hard`	`critical-edges`	L2 (R5–R7)
Depth-first orders	`rpo-sequence`, `llvm-where-rpo`	`./course drill traversal-orders` (alias of `rpo`)	`dfs-orders`	L2 (R3–R4)

RPO is not 'the order of the blocks in the file'

It happens to coincide for the lab's structured TAC, but not for LLVM's layout (the box above), nor after any pass that moves blocks. Always compute it.

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Justification
Leaders (Alg. 8.2.3)	\(O(n + m \log m)\); \(O(n)\) with a boolean array instead of sorting	\(O(n)\)	\(O(n)\) label table	one pass, \(O(1)\) per instruction with a hash map of labels
CFG construction	\(O(n)\)	\(O(n)\)	\(O(m + e)\)	one lookup per block's last instruction
Critical edges and splitting (Alg. 8.2.6)	\(O(n + e)\)	\(O(n)\)	\(c\) new blocks	in-degrees in one pass; \(O(1)\) per edge; \(c \le e\)
DFS orders (Alg. 8.2.8)	\(\Theta(m + e)\)	same	\(O(m)\) stack	each node entered once, each edge examined once

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Basic blocks and the leaders algorithm	exact: the unique maximal partition (Theorem 8.2.9)	\(O(n)\) · one pass; 19 instructions → 10 blocks on the running example	blocks named by their leaders; unreferenced labels vanish	very low	every compiler that starts from a linear IR (GCC's `make_blocks`, JVM and Wasm JITs)
Control-flow graphs and critical edges	exact successor relation; splitting adds one block per critical edge	\(O(n + e)\) · 3 critical edges, 10 → 13 blocks on the running example	a new block per split edge (`…_crit_edge` in LLVM)	low	every optimizer; splitting before out-of-SSA, PRE, code placement
Depth-first orders	RPO is a topological order modulo back edges (Theorem 8.2.14)	\(\Theta(m + e)\) · linear, explicit stack	three sequences plus an edge classification	low (iterative DFS needs care)	dataflow iteration order, dominators, SSA construction, scheduling

Lesson 8.2 — Basic blocks, control-flow graphs and traversal orders¶

1. Problem and motivation¶

Basic blocks and the leaders algorithm¶

Control-flow graphs and critical edges¶

Depth-first orders¶

2. Definitions and algorithms¶

Basic blocks and the leaders algorithm¶

Control-flow graphs and critical edges¶

Depth-first orders¶

3. Worked example¶

Leaders on the running example¶

Critical edges on the running example¶

DFS orders on the running example¶

4. Invariants and correctness¶

Basic blocks and the leaders algorithm¶

Control-flow graphs and critical edges¶

Depth-first orders¶

5. Complexity¶

6. Variants and refinements¶

Basic blocks and the leaders algorithm¶

Control-flow graphs and critical edges¶

Depth-first orders¶

7. In real compilers¶

Basic blocks and the leaders algorithm¶

Control-flow graphs and critical edges¶

Depth-first orders¶

8. Comparison¶

9. Assessment¶

References¶