41.05Intermediate / Advanced4 topics19 min2 interactive animations

Dominators and structure

In a control-flow graph, block d dominates block v when every path from the entry to v passes through d. Dominator trees, dominance frontiers and the test for reducible graphs underpin loop detection and SSA construction in compilers.

Learning goals

Build basic blocks and the control-flow graph of a small program
Compute immediate dominators with the iterative algorithm
Test whether a flow graph is reducible
Compute dominance frontiers

Prerequisites

Directed graphs and DFS (Chapters 32-33)Trees (Chapter 25)

A compiler wants to know which code always runs before other code, where loops are, and where two definitions of a variable meet. All three questions are answered by dominance on the control-flow graph, and the algorithms are short enough to write by hand.

41.05.1

Dominator tree

In a flow graph with entry block 0, block d **dominates** block v if every path from 0 to v passes through d. Every block dominates itself; the entry dominates everything reachable. The **immediate dominator** idom(v) is the closest strict dominator, the last one on every path. Linking each block to its immediate dominator gives the **dominator tree**.

The iterative algorithm of Cooper, Harvey and Kennedy is short and fast in practice. Number the reachable blocks in **reverse postorder** (so that a block comes after its predecessors except along back edges). Start with idom[0] = 0. Then sweep the blocks in that order: idom[v] becomes the **common ancestor** (found by intersect, which walks two fingers up the tree) of the already-known immediate dominators of all predecessors of v. Repeat until a sweep changes nothing.

Open the animation on the default graph, a loop containing an if/else (0-1 1-2 1-3 2-4 3-4 4-1 4-5). The reverse postorder is 0, 1, 3, 2, 4, 5. The first sweep sets idom[1] = 0, then idom[3] = idom[2] = 1; block 4 has the predecessors 2 and 3, which meet at block 1, so idom[4] = 1; and idom[5] = 4. That is 5 updates. A second sweep confirms that nothing changes (the back edge 4→1 offers block 1 the estimate intersect(4, 0) = 0 again). Result: idom = 0 0 1 1 1 4. Blocks that are not reachable from the entry (the last preset) have no dominator and show -.

Java

1// succ[v] = successors of v in the control-flow graph; the entry is vertex 0.
2// Returns idom[v]: the immediate dominator (idom[0] = 0, and -1 for unreachable vertices).
3@SuppressWarnings("unchecked")
4static int[] immediateDominators(int n, List<Integer>[] succ) {
5    List<Integer>[] pred = new List[n];
6    for (int i = 0; i < n; i++) pred[i] = new ArrayList<>();
7    for (int u = 0; u < n; u++) for (int v : succ[u]) pred[v].add(u);
8    List<Integer> order = new ArrayList<>();                          // reverse postorder of the reachable vertices
9    postorder(0, succ, new boolean[n], order);
10    Collections.reverse(order);
11    int[] rank = new int[n];
12    Arrays.fill(rank, -1);
13    for (int i = 0; i < order.size(); i++) rank[order.get(i)] = i;
14    int[] idom = new int[n];
15    Arrays.fill(idom, -1);
16    idom[0] = 0;
17    boolean changed = true;
18    while (changed) {                                                 // iterate to a fixed point
19        changed = false;
20        for (int v : order) {
21            if (v == 0) continue;
22            int best = -1;
23            for (int p : pred[v]) {
24                if (idom[p] == -1) continue;                          // this predecessor has no dominator estimate yet
25                best = best == -1 ? p : intersect(p, best, idom, rank);
26            }
27            if (best != idom[v]) { idom[v] = best; changed = true; }
28        }
29    }
30    return idom;
31}
32static void postorder(int v, List<Integer>[] succ, boolean[] seen, List<Integer> out) {
33    seen[v] = true;
34    for (int w : succ[v]) if (!seen[w]) postorder(w, succ, seen, out);
35    out.add(v);
36}
37static int intersect(int a, int b, int[] idom, int[] rank) {          // walk both fingers up the dominator tree until they meet
38    while (a != b) {
39        while (rank[a] > rank[b]) a = idom[a];
40        while (rank[b] > rank[a]) b = idom[b];
41    }
42    return a;
43}

Worst

O(V² ) per sweep in theory, a few sweeps in practice (O(V + E) for reducible graphs in reverse postorder)

Space

O(V + E)

Dominators: immediate dominators, dominance frontiers and reducibility of a control-flow graph

Interactive · edit the input

directed graph · 6 vertices · 7 edges

idom 0

idom ?

Edge that is also a dominator-tree edgeBack edge (head dominates tail)Retreating edge whose head does not dominate its tailVertex being updated

reverse postorder (rank of each reachable block)

0#0

1#1

3#2

2#3

4#4

5#5

immediate dominator idom[v]

Setup

Block d dominates block v when every path from the entry 0 to v goes through d. The immediate dominator idom[v] is the closest strict dominator. The iterative algorithm visits the blocks in reverse postorder and sets idom[v] to the common ancestor ("intersect") of the dominator estimates of v's predecessors, until nothing changes.

Step 1 / 11

Java

1// succ[v] = successors of v in the control-flow graph; the entry is vertex 0.
2// Returns idom[v]: the immediate dominator (idom[0] = 0, and -1 for unreachable vertices).
3@SuppressWarnings("unchecked")
4static int[] immediateDominators(int n, List<Integer>[] succ) {
5    List<Integer>[] pred = new List[n];
6    for (int i = 0; i < n; i++) pred[i] = new ArrayList<>();
7    for (int u = 0; u < n; u++) for (int v : succ[u]) pred[v].add(u);
8    List<Integer> order = new ArrayList<>();                          // reverse postorder of the reachable vertices
9    postorder(0, succ, new boolean[n], order);
10    Collections.reverse(order);
11    int[] rank = new int[n];
12    Arrays.fill(rank, -1);
13    for (int i = 0; i < order.size(); i++) rank[order.get(i)] = i;
14    int[] idom = new int[n];
15    Arrays.fill(idom, -1);
16    idom[0] = 0;
17    boolean changed = true;
18    while (changed) {                                                 // iterate to a fixed point
19        changed = false;
20        for (int v : order) {
21            if (v == 0) continue;
22            int best = -1;
23            for (int p : pred[v]) {
24                if (idom[p] == -1) continue;                          // this predecessor has no dominator estimate yet
25                best = best == -1 ? p : intersect(p, best, idom, rank);
26            }
27            if (best != idom[v]) { idom[v] = best; changed = true; }
28        }
29    }
30    return idom;
31}
32static void postorder(int v, List<Integer>[] succ, boolean[] seen, List<Integer> out) {
33    seen[v] = true;
34    for (int w : succ[v]) if (!seen[w]) postorder(w, succ, seen, out);
35    out.add(v);
36}
37static int intersect(int a, int b, int[] idom, int[] rank) {          // walk both fingers up the dominator tree until they meet
38    while (a != b) {
39        while (rank[a] > rank[b]) a = idom[a];
40        while (rank[b] > rank[a]) b = idom[b];
41    }
42    return a;
43}
44@SuppressWarnings("unchecked")
45static List<Set<Integer>> dominanceFrontier(int n, List<Integer>[] succ, int[] idom) {
46    List<Integer>[] pred = new List[n];
47    List<Set<Integer>> df = new ArrayList<>();
48    for (int i = 0; i < n; i++) { pred[i] = new ArrayList<>(); df.add(new TreeSet<>()); }
49    for (int u = 0; u < n; u++) if (idom[u] != -1) for (int v : succ[u]) pred[v].add(u);
50    for (int b = 0; b < n; b++) {
51        if (idom[b] == -1) continue;
52        int stop = b == 0 ? -1 : idom[b];
53        for (int p : pred[b]) {
54            int runner = p;
55            while (runner != -1 && runner != stop) {                  // climb from each predecessor up to b's immediate dominator
56                df.get(runner).add(b);
57                runner = runner == 0 ? -1 : idom[runner];
58            }
59        }
60    }
61    return df;
62}
63static boolean dominates(int d, int v, int[] idom) {                  // is d on the idom chain of v?
64    while (true) {
65        if (v == d) return true;
66        if (v == 0 || v == -1) return false;
67        v = idom[v];
68    }
69}
70static boolean isReducible(List<Integer>[] succ, int[] idom) {        // every retreating edge of a DFS must be a back edge
71    return retreating(0, succ, idom, new int[succ.length]);
72}
73static boolean retreating(int u, List<Integer>[] succ, int[] idom, int[] state) {   // state: 0 new, 1 on the stack, 2 done
74    state[u] = 1;
75    for (int v : succ[u]) {
76        if (state[v] == 1 && !dominates(v, u, idom)) return false;    // an edge up the DFS tree whose head does not dominate its tail
77        if (state[v] == 0 && !retreating(v, succ, idom, state)) return false;
78    }
79    state[u] = 2;
80    return true;
81}

Live state

0 rounds0 updates

edges

reachable

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L4	n=6 edges=7 reachable=6	Block d dominates block v when every path from the entry 0 to v goes through d. The immediate dominator idom[v] is the closest strict dominator. The iterative algorithm visits the blocks in reverse postorder and sets idom[v] to the common ancestor ("intersect") of the dominator estimates of v's predecessors, until nothing changes.
2	L27	round=1 block=1 idom=0	Block 1: its processed predecessors 0 meet at 0, so idom[1] = 0.
3	L27	round=1 block=3 idom=1	Block 3: its processed predecessors 1 meet at 1, so idom[3] = 1.
4	L27	round=1 block=2 idom=1	Block 2: its processed predecessors 1 meet at 1, so idom[2] = 1.
5	L27	round=1 block=4 idom=1	Block 4: its processed predecessors 2, 3 meet at 1, so idom[4] = 1.
6	L27	round=1 block=5 idom=4	Block 5: its processed predecessors 4 meet at 4, so idom[5] = 4.
7	L18	round=1 changed=yes	Round 1 changed some estimates, so another round is needed (a back edge may feed an improved estimate to an earlier block).
8	L18	round=2 changed=no	Round 2 changed nothing: the estimates are the dominator tree.
9	L45	DF=0:- 1:1 2:4 3:4 4:1 5:-	Dominance frontier: DF(x) holds the blocks y where x dominates a predecessor of y but does not strictly dominate y, the first blocks where x's dominance ends. For every join block b, climb from each predecessor up to idom[b] and add b to every block passed.
10	L70	retreating_edges=1 reducible=yes	A DFS finds 1 retreating edge 4→1 (head dominates tail: back edge). The graph is reducible exactly when every retreating edge is a back edge.
11	L30	return=0 0 1 1 1 4 DF=0:- 1:1 2:4 3:4 4:1 5:- reducible=yes	Dominator tree: 0→1, 1→2, 1→3, 1→4, 4→5. The graph is reducible: every loop has a single entry, its header.

41.05.2

Control-flow graph

A **control-flow graph (CFG)** has one vertex for every **basic block**, a maximal straight-line run of instructions with one way in (the top) and one way out (the bottom). An edge A → B means control may pass from the end of A to the start of B: by a jump, a branch or by falling through.

Blocks are found by marking **leaders**: the first instruction, every jump target, and every instruction that follows a jump or a return. A block runs from one leader up to the next. For the loop 0: x = 0; 1: if (i >= n) goto 5; 2: x += i; 3: i++; 4: goto 1; 5: return the leaders are 0, 1, 2 and 5, so the blocks are {0}, {1}, {2, 3, 4} and {5}, with edges B0 → B1, B1 → B3 (the branch taken), B1 → B2 (fall-through) and B2 → B1 (the back edge of the loop).

The code below takes the program as pairs {kind, target} (0 ordinary, 1 conditional jump, 2 unconditional jump, 3 return) and returns the successor lists. Everything else in this lesson, dominators, loops and SSA, runs on this graph. Unreachable blocks, such as code after an unconditional jump that nothing targets, are in the graph but have no dominator.

Instruction kind	Ends a block?	Edges leaving the block
ordinary	only if the next instruction is a leader	fall-through to the next block
conditional jump	yes	jump target and fall-through
unconditional jump	yes	jump target only
return	yes	none

Java

1// instruction i is {kind, target}: kind 0 = ordinary, 1 = conditional jump to target (otherwise falls through),
2// 2 = unconditional jump to target, 3 = return. Returns the successor lists of the basic blocks.
3@SuppressWarnings("unchecked")
4static List<Integer>[] controlFlowGraph(int[][] code) {
5    int n = code.length;
6    boolean[] leader = new boolean[n + 1];
7    leader[0] = true;
8    for (int i = 0; i < n; i++) {
9        if (code[i][0] == 1 || code[i][0] == 2) leader[code[i][1]] = true;       // a jump target starts a block
10        if (code[i][0] != 0 && i + 1 < n) leader[i + 1] = true;                  // so does the instruction after a jump or return
11    }
12    int[] block = new int[n];
13    int blocks = 0;
14    for (int i = 0; i < n; i++) { if (leader[i] && i > 0) blocks++; block[i] = blocks; }
15    blocks++;
16    List<Integer>[] succ = new List[blocks];
17    for (int b = 0; b < blocks; b++) succ[b] = new ArrayList<>();
18    for (int i = 0; i < n; i++) {
19        boolean last = i + 1 == n || block[i + 1] != block[i];                   // only the last instruction of a block ends it
20        if (!last) continue;
21        int kind = code[i][0];
22        if (kind == 1 || kind == 2) succ[block[i]].add(block[code[i][1]]);       // the jump edge
23        if ((kind == 0 || kind == 1) && i + 1 < n) succ[block[i]].add(block[i + 1]);   // the fall-through edge
24    }
25    return succ;
26}

41.05.3

Reducible graphs

Structured programs (if, while, for, no goto into a loop) give **reducible** flow graphs: every loop has a single entry block, its **header**, which dominates all blocks of the loop. Compilers rely on this: loops are easy to find and optimise. A flow graph with a loop that can be entered at two different places is **irreducible**.

The test uses dominators. Run a DFS from the entry. An edge to an ancestor on the DFS stack is a **retreating edge**. The graph is reducible exactly when every retreating edge is a **back edge**, meaning its head dominates its tail. If some retreating edge points to a block that does not dominate its source, the cycle can be entered from outside through another block.

The animation's irreducible preset is the classic case: entry 0 jumps to both 1 and 2, and 1 and 2 jump to each other. The DFS finds a retreating edge between them, but neither dominates the other (both have idom 0), so the result is reducible = no. In the nested-loops preset both retreating edges (3→2 and 3→1) go to dominating headers and the graph is reducible.

Java

1static boolean dominates(int d, int v, int[] idom) {                  // is d on the idom chain of v?
2    while (true) {
3        if (v == d) return true;
4        if (v == 0 || v == -1) return false;
5        v = idom[v];
6    }
7}
8static boolean isReducible(List<Integer>[] succ, int[] idom) {        // every retreating edge of a DFS must be a back edge
9    return retreating(0, succ, idom, new int[succ.length]);
10}
11static boolean retreating(int u, List<Integer>[] succ, int[] idom, int[] state) {   // state: 0 new, 1 on the stack, 2 done
12    state[u] = 1;
13    for (int v : succ[u]) {
14        if (state[v] == 1 && !dominates(v, u, idom)) return false;    // an edge up the DFS tree whose head does not dominate its tail
15        if (state[v] == 0 && !retreating(v, succ, idom, state)) return false;
16    }
17    state[u] = 2;
18    return true;
19}

Dominators: immediate dominators, dominance frontiers and reducibility of a control-flow graph

Interactive · edit the input

directed graph · 6 vertices · 7 edges

idom 0

idom ?

Edge that is also a dominator-tree edgeBack edge (head dominates tail)Retreating edge whose head does not dominate its tailVertex being updated

reverse postorder (rank of each reachable block)

0#0

1#1

3#2

2#3

4#4

5#5

immediate dominator idom[v]

Setup

Step 1 / 11

Java

1// succ[v] = successors of v in the control-flow graph; the entry is vertex 0.
2// Returns idom[v]: the immediate dominator (idom[0] = 0, and -1 for unreachable vertices).
3@SuppressWarnings("unchecked")
4static int[] immediateDominators(int n, List<Integer>[] succ) {
5    List<Integer>[] pred = new List[n];
6    for (int i = 0; i < n; i++) pred[i] = new ArrayList<>();
7    for (int u = 0; u < n; u++) for (int v : succ[u]) pred[v].add(u);
8    List<Integer> order = new ArrayList<>();                          // reverse postorder of the reachable vertices
9    postorder(0, succ, new boolean[n], order);
10    Collections.reverse(order);
11    int[] rank = new int[n];
12    Arrays.fill(rank, -1);
13    for (int i = 0; i < order.size(); i++) rank[order.get(i)] = i;
14    int[] idom = new int[n];
15    Arrays.fill(idom, -1);
16    idom[0] = 0;
17    boolean changed = true;
18    while (changed) {                                                 // iterate to a fixed point
19        changed = false;
20        for (int v : order) {
21            if (v == 0) continue;
22            int best = -1;
23            for (int p : pred[v]) {
24                if (idom[p] == -1) continue;                          // this predecessor has no dominator estimate yet
25                best = best == -1 ? p : intersect(p, best, idom, rank);
26            }
27            if (best != idom[v]) { idom[v] = best; changed = true; }
28        }
29    }
30    return idom;
31}
32static void postorder(int v, List<Integer>[] succ, boolean[] seen, List<Integer> out) {
33    seen[v] = true;
34    for (int w : succ[v]) if (!seen[w]) postorder(w, succ, seen, out);
35    out.add(v);
36}
37static int intersect(int a, int b, int[] idom, int[] rank) {          // walk both fingers up the dominator tree until they meet
38    while (a != b) {
39        while (rank[a] > rank[b]) a = idom[a];
40        while (rank[b] > rank[a]) b = idom[b];
41    }
42    return a;
43}
44@SuppressWarnings("unchecked")
45static List<Set<Integer>> dominanceFrontier(int n, List<Integer>[] succ, int[] idom) {
46    List<Integer>[] pred = new List[n];
47    List<Set<Integer>> df = new ArrayList<>();
48    for (int i = 0; i < n; i++) { pred[i] = new ArrayList<>(); df.add(new TreeSet<>()); }
49    for (int u = 0; u < n; u++) if (idom[u] != -1) for (int v : succ[u]) pred[v].add(u);
50    for (int b = 0; b < n; b++) {
51        if (idom[b] == -1) continue;
52        int stop = b == 0 ? -1 : idom[b];
53        for (int p : pred[b]) {
54            int runner = p;
55            while (runner != -1 && runner != stop) {                  // climb from each predecessor up to b's immediate dominator
56                df.get(runner).add(b);
57                runner = runner == 0 ? -1 : idom[runner];
58            }
59        }
60    }
61    return df;
62}
63static boolean dominates(int d, int v, int[] idom) {                  // is d on the idom chain of v?
64    while (true) {
65        if (v == d) return true;
66        if (v == 0 || v == -1) return false;
67        v = idom[v];
68    }
69}
70static boolean isReducible(List<Integer>[] succ, int[] idom) {        // every retreating edge of a DFS must be a back edge
71    return retreating(0, succ, idom, new int[succ.length]);
72}
73static boolean retreating(int u, List<Integer>[] succ, int[] idom, int[] state) {   // state: 0 new, 1 on the stack, 2 done
74    state[u] = 1;
75    for (int v : succ[u]) {
76        if (state[v] == 1 && !dominates(v, u, idom)) return false;    // an edge up the DFS tree whose head does not dominate its tail
77        if (state[v] == 0 && !retreating(v, succ, idom, state)) return false;
78    }
79    state[u] = 2;
80    return true;
81}

Live state

0 rounds0 updates

edges

reachable

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L4	n=6 edges=7 reachable=6	Block d dominates block v when every path from the entry 0 to v goes through d. The immediate dominator idom[v] is the closest strict dominator. The iterative algorithm visits the blocks in reverse postorder and sets idom[v] to the common ancestor ("intersect") of the dominator estimates of v's predecessors, until nothing changes.
2	L27	round=1 block=1 idom=0	Block 1: its processed predecessors 0 meet at 0, so idom[1] = 0.
3	L27	round=1 block=3 idom=1	Block 3: its processed predecessors 1 meet at 1, so idom[3] = 1.
4	L27	round=1 block=2 idom=1	Block 2: its processed predecessors 1 meet at 1, so idom[2] = 1.
5	L27	round=1 block=4 idom=1	Block 4: its processed predecessors 2, 3 meet at 1, so idom[4] = 1.
6	L27	round=1 block=5 idom=4	Block 5: its processed predecessors 4 meet at 4, so idom[5] = 4.
7	L18	round=1 changed=yes	Round 1 changed some estimates, so another round is needed (a back edge may feed an improved estimate to an earlier block).
8	L18	round=2 changed=no	Round 2 changed nothing: the estimates are the dominator tree.
9	L45	DF=0:- 1:1 2:4 3:4 4:1 5:-	Dominance frontier: DF(x) holds the blocks y where x dominates a predecessor of y but does not strictly dominate y, the first blocks where x's dominance ends. For every join block b, climb from each predecessor up to idom[b] and add b to every block passed.
10	L70	retreating_edges=1 reducible=yes	A DFS finds 1 retreating edge 4→1 (head dominates tail: back edge). The graph is reducible exactly when every retreating edge is a back edge.
11	L30	return=0 0 1 1 1 4 DF=0:- 1:1 2:4 3:4 4:1 5:- reducible=yes	Dominator tree: 0→1, 1→2, 1→3, 1→4, 4→5. The graph is reducible: every loop has a single entry, its header.

41.05.4

Dominance frontier overview

The **dominance frontier** DF(x) of a block x is the set of blocks y such that x dominates a predecessor of y but does **not strictly dominate** y itself. Informally: where x's dominance ends, the first blocks that other paths can also reach.

Cytron et al. use it to place the φ-functions of **static single assignment (SSA)** form: if a variable is assigned in block x, then every block in DF(x) needs a φ-function for it, because there the definition from x merges with other definitions; the newly placed φ counts as a new definition and the rule is applied again.

The code computes the frontier without looking at all pairs: for every join block b (one with several predecessors) and for each predecessor p, climb the dominator tree from p to idom(b), adding b to the frontier of every block on the way. On the animation's default graph the frontiers are DF(1) = {1}, DF(2) = DF(3) = {4} and DF(4) = {1}: the merge block 4 belongs to the frontier of the two branches 2 and 3, and the loop header 1 belongs to the frontier of the loop body. In the diamond preset, the merge block 3 is in both DF(1) and DF(2).

Java

1@SuppressWarnings("unchecked")
2static List<Set<Integer>> dominanceFrontier(int n, List<Integer>[] succ, int[] idom) {
3    List<Integer>[] pred = new List[n];
4    List<Set<Integer>> df = new ArrayList<>();
5    for (int i = 0; i < n; i++) { pred[i] = new ArrayList<>(); df.add(new TreeSet<>()); }
6    for (int u = 0; u < n; u++) if (idom[u] != -1) for (int v : succ[u]) pred[v].add(u);
7    for (int b = 0; b < n; b++) {
8        if (idom[b] == -1) continue;
9        int stop = b == 0 ? -1 : idom[b];
10        for (int p : pred[b]) {
11            int runner = p;
12            while (runner != -1 && runner != stop) {                  // climb from each predecessor up to b's immediate dominator
13                df.get(runner).add(b);
14                runner = runner == 0 ? -1 : idom[runner];
15            }
16        }
17    }
18    return df;
19}

Worst

O(V + E + size of the frontiers)

Space

O(V + size of the frontiers)

Practice ladder

Now try it yourself

Easy

Course Schedule

Medium

Course Schedule II

Advanced

Critical Connections in a Network

Key takeaways

d dominates v when every path from the entry to v goes through d; idom links each block to its closest strict dominator.
A flow graph is reducible when every DFS retreating edge is a back edge (its head dominates its tail).
DF(x) = the first blocks where x's dominance ends; it tells SSA construction where φ-functions go.