Lesson 16.2 — Construction with dominance frontiers: Cytron et al. and Sreedhar–Gao¶

Techniques: Cytron et al.'s construction (phi placement at iterated dominance frontiers, renaming with one stack per variable), Sreedhar–Gao's linear-time placement on the DJ graph · Pebble implements: Cytron placement and renaming in lab L1 (minimal, semi-pruned and pruned), pebble-mem2reg (E1) with Sreedhar–Gao through llvm::ForwardIDFCalculator or your own DF⁺ · Prerequisites: Lesson 16.1, Lesson 15.3 · Time: 5–6 hours

Lesson 16.1 said where the phis go. Construction has a second half: renaming. After phis are placed, every definition gets a fresh name and every use must be rewritten to the name of the definition that reaches it. Cytron et al. solve both halves with the dominator tree: phis go to iterated dominance frontiers, and a preorder walk of the dominator tree with one stack per variable finds, for every use, the nearest dominating definition [CFRWZ91]. Sreedhar and Gao replace the first half by a walk of the DJ graph that is linear per variable even when frontiers are quadratic [SG95]. Chapter 15 taught the frontier algorithms themselves; this lesson treats them as phi-placement engines and proves the whole construction correct.

1. Problem and motivation¶

The problem. Input: a variable program (Definition 16.1.1) on a CFG with its dominator tree. Output: an equivalent program in strict SSA (Definition 16.1.4) of a chosen flavor. pebblec needs this once per function, right after lowering, and LLVM runs it (as mem2reg or inside sroa) at the start of every optimization pipeline.

Cytron et al.¶

Before 1989 SSA was built by ad hoc methods that could place a phi for every variable at every join. Cytron, Ferrante, Rosen, Wegman and Zadeck made construction efficient with two observations [CFRWZ91]: the blocks that need a phi are exactly the iterated dominance frontier of the definition blocks (Theorem 15.3.10), and the definition that reaches a use is always the nearest definition above it in the dominator tree, so one walk of that tree renames everything. GCC's tree-into-ssa.cc is a direct implementation [GCC-IntoSSA].

Sreedhar–Gao¶

Cytron's placement computes every frontier first, and \(\sum_X \lvert \mathrm{DF}(X) \rvert\) can be \(\Theta(n^2)\) (Lesson 15.3 §5). Sreedhar and Gao showed that DF⁺ of a set can be read off the DJ graph (dominator-tree edges plus the other CFG edges) in time linear in the graph, without materializing any frontier [SG95]. LLVM's IDFCalculator implements it and adds a live-in filter, which turns minimal placement into pruned placement in the same walk [LLVM-IDF]. Go uses it for functions above 500 blocks [Go-SSAGen].

2. Definitions and algorithms¶

\(G = (N, E, r)\) with dominator tree \(\mathcal{D}\); \(\mathrm{children}(X)\) lists \(X\)'s tree children in reverse postorder of \(G\) (this fixes the order of the walk and hence the version numbers); \(\mathrm{preds}(Y)\) is in a fixed order, and the \(j\)-th phi operand belongs to the \(j\)-th predecessor.

Cytron et al.¶

Algorithm 16.2.1 (Cytron et al.: phi placement for all variables)

Input: a variable program; \(\mathrm{DF}(X)\) for every block; a flavor filter \(\mathit{keep}(v, Y)\) (always true for minimal; "\(v\) global" for semi-pruned; "\(v \in \mathrm{LiveIn}(Y)\)" for pruned).
Output: the phis to insert: a set of pairs \((Y, v)\).
Precondition: all blocks reachable; \(\mathrm{defs}(v)\) includes \(r\).
Postcondition: \((Y, v)\) is inserted iff \(Y \in \mathrm{DF}^{+}(\mathrm{defs}(v))\) and \(\mathit{keep}(v, Y)\).
Invariant: HasAlready[Y] = iter iff a phi for the current variable was considered at \(Y\); Work[Y] = iter iff \(Y\) has been on the current worklist. Using the counter iter instead of clearing the arrays keeps the cost per variable proportional to its work [CFRWZ91, §5.1].

function PlacePhis(G, DF, keep):
    iter ← 0
    for Y in N: HasAlready[Y] ← 0; Work[Y] ← 0
    phis ← {}
    for v in V:
        iter ← iter + 1
        W ← []
        for X in defs(v):
            Work[X] ← iter; append X to W
        while W not empty:
            X ← remove any element of W
            for Y in DF(X):
                if HasAlready[Y] < iter:
                    HasAlready[Y] ← iter
                    if keep(v, Y): phis ← phis ∪ {(Y, v)}
                    if Work[Y] < iter:            # a phi is a new definition of v
                        Work[Y] ← iter; append Y to W
    return phis

Filtering with keep does not change the worklist: a block where the phi is not kept is still a join where \(v\)'s definitions meet, so its frontier must still be explored.

Definition 16.2.2 (Current definition)

During renaming, \(S(v)\) is a stack of names of \(v\). For a point \(p\) in block \(B\), the current definition of \(v\) at \(p\) is: the last definition of \(v\) before \(p\) in \(B\) (a statement, or a phi for \(v\) at the top of \(B\)) if there is one; otherwise the current definition of \(v\) at the end of \(\mathrm{idom}(B)\); and for \(B = r\) with no earlier definition, the implicit initial definition \(v_0\).

Algorithm 16.2.3 (Cytron et al.: renaming)

Input: the program with phis placed (Algorithm 16.2.1); \(\mathcal{D}\).
Output: every definition renamed \(v_k\) (fresh \(k\)), every use and phi operand rewritten.
Precondition: phis placed at a superset of the needed blocks (Theorem 16.1.10(a)).
Postcondition: strict SSA; each use names the current definition (Definition 16.2.2) at the use; each phi operand for \(P_j \to Y\) names the current definition at the end of \(P_j\).
Invariant: when the walk is at point \(p\), \(\mathrm{top}(S(v))\) is the current definition of \(v\) at \(p\), for every \(v\) (Lemma 16.2.5).

function Rename(G, D):
    for v in V: C[v] ← 1; S[v] ← [v0]          # v0: the implicit initial value
    Search(r)

function Search(X):
    pushed ← []
    for each phi "v ← φ(...)" at the top of X:
        name ← v_{C[v]}; C[v] ← C[v] + 1
        replace the phi's result by name; push name on S[v]; append v to pushed
    for each statement s of X, in order:
        for each use of v in s: replace it by top(S[v])
        if s defines v:
            name ← v_{C[v]}; C[v] ← C[v] + 1
            replace the definition by name; push name on S[v]; append v to pushed
    for Y in succs(X):                         # once per edge
        j ← the position of this edge among preds(Y)
        for each phi "... ← φ(...)" of Y for variable v:
            replace its j-th operand by top(S[v])
    for Z in children_D(X):                    # reverse postorder of G
        Search(Z)
    for v in pushed, last first: pop S[v]

The course code (ssa.py's rename_var_program, the lab solution) runs Search iteratively with an explicit stack of (enter, exit) frames, because the lab graphs are deep.

Sreedhar–Gao¶

Algorithm 16.2.4 (Sreedhar–Gao phi placement with a live-in filter)

Input: \(G\), \(\mathcal{D}\) with levels and DFS numbers, the definition blocks \(S\) of one variable, and optionally a set \(L\) of blocks where it is live-in.
Output: \(\mathrm{DF}^{+}(S)\), or \(\mathrm{DF}^{+}(S) \cap L\) when \(L\) is given.
Precondition: \(\mathcal{D}\) is the dominator tree of \(G\).
Postcondition: as the output says (Theorem 16.2.7).
Invariant: roots are popped in order of non-increasing level; when a root at level \(\ell\) is popped, every result block deeper than \(\ell\) has been found (Algorithm 15.3.14).

function SreedharGaoPhis(G, D, S, L):
    PQ ← max-priority queue on (level(x), dfsIn(x)) holding every x ∈ S
    walked ← S; inResult ← {}; result ← []
    while PQ not empty:
        root ← pop the maximum of PQ
        stack ← [root]
        while stack not empty:
            x ← pop stack
            for y in succs(x):
                if level(y) > level(root): continue      # D edges, deeper J edges
                if y ∈ inResult: continue
                if L is given and y ∉ L: continue        # pruned: v dead at y
                inResult ← inResult ∪ {y}; append y to result
                if y ∉ S: insert y into PQ               # the phi is a new definition
            for c in children_D(x):
                if c ∉ walked: walked ← walked ∪ {c}; push c on stack
    return result

This is Algorithm 15.3.14 with the one line that makes IDFCalculatorBase::calculate compute pruned SSA when setLiveInBlocks was called [LLVM-IDF]. The oracle is idf_sreedhar_gao(..., live_in=...) in tools/course/lib/cfa.py.

3. Worked example¶

Cytron et al. on the running example¶

Placement with the pruned filter (Lesson 16.1 §3 has the DF⁺ worklists) gives \((B, i)\), \((B, x)\), \((E, x)\), \((E, y)\) and \((H, x)\). Renaming walks the dominator tree in preorder A, B, C, D, E, F, G, H, I (B's children in reverse postorder: C, E, H). The temporary t never has a phi and is left out of the table to keep it readable (it only pushes and pops in its own block). Versions follow the drill convention: \(v_0\) is the initial value. Bold marks a stack that changed.

step	block	action	var	version	stack i	stack x	stack y
1	A	enter	—	—	i0	x0	y0
2	A	def	i	i1	i0 i1	x0	y0
3	A	def	x	x1	i0 i1	x0 x1	y0
4	A	arg A→B	i	i1	i0 i1	x0 x1	y0
5	A	arg A→B	x	x1	i0 i1	x0 x1	y0
6	B	enter	—	—	i0 i1	x0 x1	y0
7	B	phi	i	i2	i0 i1 i2	x0 x1	y0
8	B	phi	x	x2	i0 i1 i2	x0 x1 x2	y0
9	B	use	x	x2	i0 i1 i2	x0 x1 x2	y0
10	B	use	i	i2	i0 i1 i2	x0 x1 x2	y0
11	B	def	y	y1	i0 i1 i2	x0 x1 x2	y0 y1
12	B	use	i	i2	i0 i1 i2	x0 x1 x2	y0 y1
13	B	arg B→E	x	x2	i0 i1 i2	x0 x1 x2	y0 y1
14	B	arg B→E	y	y1	i0 i1 i2	x0 x1 x2	y0 y1
15	C	enter	—	—	i0 i1 i2	x0 x1 x2	y0 y1
16	C	use	y	y1	i0 i1 i2	x0 x1 x2	y0 y1
17	C	def	x	x3	i0 i1 i2	x0 x1 x2 x3	y0 y1
18	C	use	x	x3	i0 i1 i2	x0 x1 x2 x3	y0 y1
19	C	arg C→H	x	x3	i0 i1 i2	x0 x1 x2 x3	y0 y1
20	D	enter	—	—	i0 i1 i2	x0 x1 x2 x3	y0 y1
21	D	use	y	y1	i0 i1 i2	x0 x1 x2 x3	y0 y1
22	D	def	y	y2	i0 i1 i2	x0 x1 x2 x3	y0 y1 y2
23	D	arg D→E	x	x3	i0 i1 i2	x0 x1 x2 x3	y0 y1 y2
24	D	arg D→E	y	y2	i0 i1 i2	x0 x1 x2 x3	y0 y1 y2
25	D	pop	y	y2	i0 i1 i2	x0 x1 x2 x3	y0 y1
26	C	pop	x	x3	i0 i1 i2	x0 x1 x2	y0 y1
27	E	enter	—	—	i0 i1 i2	x0 x1 x2	y0 y1
28	E	phi	x	x4	i0 i1 i2	x0 x1 x2 x4	y0 y1
29	E	phi	y	y3	i0 i1 i2	x0 x1 x2 x4	y0 y1 y3
30	E	use	y	y3	i0 i1 i2	x0 x1 x2 x4	y0 y1 y3
31	E	arg E→H	x	x4	i0 i1 i2	x0 x1 x2 x4	y0 y1 y3
32	F	enter	—	—	i0 i1 i2	x0 x1 x2 x4	y0 y1 y3
33	F	use	x	x4	i0 i1 i2	x0 x1 x2 x4	y0 y1 y3
34	F	use	y	y3	i0 i1 i2	x0 x1 x2 x4	y0 y1 y3
35	F	def	x	x5	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3
36	F	use	y	y3	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3
37	F	def	y	y4	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3 y4
38	G	enter	—	—	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3 y4
39	G	use	x	x5	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3 y4
40	G	arg G→E	x	x5	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3 y4
41	G	arg G→E	y	y4	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3 y4
42	G	arg G→H	x	x5	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3 y4
43	F	pop	y	y4	i0 i1 i2	x0 x1 x2 x4 x5	y0 y1 y3
44	F	pop	x	x5	i0 i1 i2	x0 x1 x2 x4	y0 y1 y3
45	E	pop	y	y3	i0 i1 i2	x0 x1 x2 x4	y0 y1
46	E	pop	x	x4	i0 i1 i2	x0 x1 x2	y0 y1
47	H	enter	—	—	i0 i1 i2	x0 x1 x2	y0 y1
48	H	phi	x	x6	i0 i1 i2	x0 x1 x2 x6	y0 y1
49	H	use	i	i2	i0 i1 i2	x0 x1 x2 x6	y0 y1
50	H	def	i	i3	i0 i1 i2 i3	x0 x1 x2 x6	y0 y1
51	H	use	i	i3	i0 i1 i2 i3	x0 x1 x2 x6	y0 y1
52	H	arg H→B	i	i3	i0 i1 i2 i3	x0 x1 x2 x6	y0 y1
53	H	arg H→B	x	x6	i0 i1 i2 i3	x0 x1 x2 x6	y0 y1
54	I	enter	—	—	i0 i1 i2 i3	x0 x1 x2 x6	y0 y1
55	I	use	x	x6	i0 i1 i2 i3	x0 x1 x2 x6	y0 y1
56	H	pop	i	i3	i0 i1 i2	x0 x1 x2 x6	y0 y1
57	H	pop	x	x6	i0 i1 i2	x0 x1 x2	y0 y1
58	B	pop	y	y1	i0 i1 i2	x0 x1 x2	y0
59	B	pop	x	x2	i0 i1 i2	x0 x1	y0
60	B	pop	i	i2	i0 i1	x0 x1	y0
61	A	pop	x	x1	i0 i1	x0	y0
62	A	pop	i	i1	i0	x0	y0

Reading the result off the table: the phis are \(i_2 \gets \phi(i_1, i_3)\) at B (preds A, H), \(x_2 \gets \phi(x_1, x_6)\) at B, \(x_4 \gets \phi(x_2, x_3, x_5)\) at E (preds B, D, G), \(y_3 \gets \phi(y_1, y_2, y_4)\) at E, and \(x_6 \gets \phi(x_3, x_4, x_5)\) at H (preds C, E, G). Three details to check against Algorithm 16.2.3:

Step 26: C's version \(x_3\) is popped before E is entered, so the operand of E's phi from B (step 13) is \(x_2\), and the operand from D (step 23) is \(x_3\): D is below C in the tree, B is not.
Step 42: G fills H's phi operand with \(x_5\), F's version, even though H is not G's tree child. Operands are filled along CFG edges, stacks are unwound along tree edges.
The use in I (step 55) reads \(x_6\), the phi at H, which dominates I.

The lab prints the same function in block-argument form (ch16-ssa --algo=pruned running.tac), naming the first real definition x.0 and passing the initial values as constants:

ssa
A:
  i.0 = 0
  x.0 = 1
  br B(i.0, x.0)
B(i.1, x.1):
  y.0 = add x.1, i.1
  cbr i.1, C(), E(x.1, y.0)
C:
  x.2 = add y.0, 2
  t.0 = lt x.2, 20
  cbr t.0, D(), H(x.2)
D:
  y.1 = mul y.0, 2
  br E(x.2, y.1)
E(x.3, y.2):
  t.1 = gt y.2, 0
  cbr t.1, F(), H(x.3)
F:
  x.4 = add x.3, y.2
  y.3 = sub y.2, 7
  br G()
G:
  t.2 = rem x.4, 3
  cbr t.2, E(x.4, y.3), H(x.4)
H(x.5):
  i.2 = add i.1, 1
  t.3 = lt i.2, 4
  cbr t.3, B(i.2, x.5), I()
I:
  ret x.5

Sreedhar–Gao on the running example¶

For \(y\), with \(S = \mathrm{defs}(y) = \{A, B, D, F\}\) and the live-in filter \(L = \{C, D, E, F, G\}\) from Lesson 16.1. Levels: A 0; B 1; C, E, H 2; D, F, I 3; G 4. J edges: C→H, D→E, E→H, G→E, G→H, H→B.

step	pop root (level)	subtree walked	J edges with level(y) ≤ level(root)	effect	queue after (top first)
0	—	—	—	—	F (3), D (3), B (1), A (0)
1	F (3)	F, G	G→E (2 ≤ 3); G→H (2 ≤ 3)	E added (live); H skipped (not in L)	D, E, B, A
2	D (3)	D	D→E	E already found	E, B, A
3	E (2)	E (F was walked)	E→H	H skipped (not in L)	B, A
4	B (1)	B, H, I, E, C	H→B (1 ≤ 1)	B skipped (not in L)	A
5	A (0)	A	—	—	(empty)

Result \(\{E\}\): pruned SSA's single phi for \(y\). Without \(L\), step 1 would also add H and step 4 would add B, giving the minimal \(\{B, E, H\}\) (the ch15-style trace is ./course drill idf --solution).

Try it

./course drill ssa-renaming --seed 2 --difficulty medium --solution prints the full stack trace for a random program; ./course drill idf --seed 4 --solution prints Cytron's worklist next to the DJ-graph walk.

4. Invariants and correctness¶

Cytron et al.¶

Lemma 16.2.5 (Stack invariant)

Throughout Search, at the moment the walk processes a point \(p\) of block \(X\) (a phi, a statement, or the end of \(X\) when successors' operands are filled), \(\mathrm{top}(S(v))\) is the current definition of \(v\) at \(p\) (Definition 16.2.2) for every variable \(v\).

Proof

By induction on the walk. At the start of Search(r) every stack holds only \(v_0\), the implicit definition: correct because nothing precedes the start of \(r\). Within \(X\), each phi and each defining statement pushes its own name, which becomes the nearest definition for the following points of \(X\); uses do not change stacks. When Search(Z) starts for a child \(Z\), the stacks are as at the end of \(X = \mathrm{idom}(Z)\): every name pushed by the siblings of \(Z\) visited earlier, and by their subtrees, has been popped again (each call pops exactly what it pushed, by the pushed list). So at the start of \(Z\) the top is the current definition at the end of \(\mathrm{idom}(Z)\), which by Definition 16.2.2 is the current definition at the start of \(Z\) unless \(Z\) has a phi for \(v\), in which case the phi is pushed first. The pops at the end of Search(X) restore the state of the start of \(X\), which maintains the invariant for \(X\)'s later siblings.

Theorem 16.2.6 (Correctness of Cytron's construction)

Let phis for \(v\) be placed at every block of \(\mathrm{DF}^{+}(\mathrm{defs}(v))\) (possibly more, and for pruned SSA possibly only those where \(v\) is live-in). After Algorithm 16.2.3: (a) every name has exactly one definition; (b) on every path from \(r\) to a use of \(v\) (or to the end of \(P_j\) for a phi operand), the last definition of \(v\), counting phis, is the one the use names; (c) the program is strict; (d) the program computes the same values as the original, when phis get the semantics of Definition 16.1.2.

Proof

(a) Every definition gets a fresh \(v_{C[v]}\) and \(C[v]\) only grows. (b) Let \(d\) be the definition named at the use point \(p\) in block \(B\); by Lemma 16.2.5 it is the current definition at \(p\), the nearest definition of \(v\) above \(p\) in the dominator tree. Suppose some path \(\pi : r \leadsto p\) has, after its last occurrence of \(d\), a definition \(d'\) of \(v\) at a point \(q\) in block \(B'\), and let \(d'\) be the last one before \(p\). If \(B'\) dominated \(B\), then \(d'\) would be above \(p\) in the tree and at least as near as \(d\) (if \(B' = B\), \(q\) would lie between \(d\) and \(p\) in \(B\)), contradicting the choice of \(d\). So \(B'\) does not dominate \(B\), and the part of \(\pi\) from \(q\) to \(p\) leaves the region dominated by \(B'\): it crosses an edge \(a \to b\) where \(B'\) dominates \(a\) but does not strictly dominate \(b\), that is, \(b \in \mathrm{DF}(B')\). \(B'\) is a definition block or a phi block, so \(b \in \mathrm{DF}^{+}(\mathrm{defs}(v))\) by closure, and \(b\) holds a phi for \(v\): a definition after \(q\) on \(\pi\), contradicting the choice of \(d'\). Under pruning, \(b\) might have no phi only if \(v\) is not live-in at \(b\); but the rest of \(\pi\) from \(b\) reaches the use \(p\) with no definition of \(v\), so \(v\) is live-in at \(b\): the same contradiction. (c) The named definition \(d\) dominates \(p\) by construction (it is taken from the dominator-tree ancestors of \(p\) or earlier in \(p\)'s block). (d) By (b), in any execution the value a use reads in the SSA program is the value written by the last definition of \(v\) executed, which is the value the original program reads; phis forward exactly the value current at the end of the predecessor taken, which is again the last definition executed.

This is the main correctness result of [CFRWZ91, §5] in its dominator-tree form; the textbook proof in [Appel, §19.1] follows the same path argument. It also proves Theorem 16.1.10(a).

When it breaks. Placing phis at fewer blocks than DF⁺ (for example DF instead of DF⁺, or a stale frontier after a CFG change) breaks step (b): the path argument finds a frontier block without a phi. Walking children in a different order changes only the version numbers, never correctness.

Sreedhar–Gao¶

Theorem 16.2.7 (Correctness and cost of Algorithm 16.2.4)

Without \(L\), Algorithm 16.2.4 returns \(\mathrm{DF}^{+}(S)\) and walks each block at most twice. With \(L\), it returns \(\mathrm{DF}^{+}(S) \cap L\) whenever \(L\) is closed backwards under definition-free paths (a set of live-in blocks is), which is pruned placement.

Proof sketch (full proof of the unfiltered case: [SG95] and Theorem 15.3.18)

The unfiltered case is Theorem 15.3.18. With \(L\), a block outside \(L\) is never added or queued, so the result \(R\) is contained in \(\mathrm{DF}^{+}(S) \cap L\); and since the walk from a queued root finds that root's frontier (as in the unfiltered proof), minus the blocks outside \(L\), \(R\) satisfies \(\mathrm{DF}(q) \cap L \subseteq R\) for every \(q \in S \cup R\). For the converse, write \(\mathrm{DF}^{+}(S) = \bigcup_j D_j\) with \(D_0 = S\), \(D_{j+1} = D_j \cup \mathrm{DF}(D_j)\), and show by induction on \(j\) that every \(y \in D_j \cap L\) lies in \(S \cup R\). Let \(y \in \mathrm{DF}(x)\), \(x \in D_{j-1}\), with witness edge \(a \to y\) (\(x\) dominates \(a\)), and take a path \(\rho\) from \(x\) to \(a\) all of whose blocks \(x\) dominates (the suffix after the last \(x\) of any path \(r \leadsto a\)). If \(\rho\) holds a block of \(S\), let \(s\) be the last one and walk the dominance chain of \(\rho' = \rho[s..a] \cdot y\): \(c_0 = s\), and \(c_{i+1}\) is the first block after \(c_i\) on \(\rho'\) that \(c_i\) does not strictly dominate. The block before \(c_{i+1}\) is dominated by \(c_i\), so \(c_{i+1} \in \mathrm{DF}(c_i)\); \(c_{i+1}\) lies after \(s\) on \(\rho'\), so it holds no definition, and the rest of \(\rho'\) followed by a definition-free path from \(y\) to a use shows \(c_{i+1} \in L\); hence \(c_{i+1} \in R\) by induction on \(i\). The chain stops at \(y\) itself, because a chain block \(c\) before \(y\) that strictly dominated \(y\) would be dominated by \(x\) (it lies on \(\rho\)), making \(x\) strictly dominate \(y\), contrary to \(y \in \mathrm{DF}(x)\). If \(\rho\) holds no block of \(S\), then \(x \notin S\) holds no definition, \(\rho \cdot y\) followed by a path from \(y\) to a use shows \(x \in L\), so \(x \in D_{j-1} \cap L \subseteq S \cup R\) by induction, and \(y \in \mathrm{DF}(x) \cap L \subseteq R\). The oracle test test_filtered_idf checks the equality on 1 500 random programs.

5. Complexity¶

\(n\) = blocks, \(m\) = edges, \(S\) = statements, \(\lvert V \rvert\) = variables, \(A\) = phis inserted, \(\lvert \mathrm{DF} \rvert\) = total frontier size.

Technique	Time (worst)	Time (typical)	Space
Cytron placement	\(O(\lvert V \rvert \cdot \lvert \mathrm{DF} \rvert)\) plus \(O(m + \lvert \mathrm{DF} \rvert)\) for the frontiers	about linear: frontiers are small on real code	\(O(\lvert \mathrm{DF} \rvert)\)
Cytron renaming	\(O(S + A + m)\) uses, definitions and operands, each touched once	linear	\(O(S)\) stack entries
Sreedhar–Gao placement	\(O(n + m)\) per variable, \(O((n + m) \log n)\) with LLVM's heap	linear	\(O(n)\)

Justification. Algorithm 16.2.1 processes a block for variable \(v\) at most once (Work) and scans its frontier once, so the work for \(v\) is at most \(\lvert \mathrm{DF} \rvert\); the counters avoid an \(O(n)\) reset per variable. Search visits each block once; each statement use is rewritten once; each phi operand is written once per edge; each push has one pop. Sreedhar–Gao is Theorem 15.3.18.

Proposition 16.2.8 (Frontier size can be quadratic while phis stay linear)

For the family of \(k\) nested repeat-until loops of Lesson 15.3 §5 (\(n = 2k + 2\) blocks), \(\lvert \mathrm{DF} \rvert = k(k + 1)\), but a variable assigned in the innermost body gets only \(k\) phis. So Cytron's frontier precomputation costs \(\Theta(n^2)\) for \(\Theta(n)\) output, while Sreedhar–Gao costs \(O(n)\).

Proof

The frontier count is Lesson 15.3 §5's derivation: \(\mathrm{DF}(H_i) = \mathrm{DF}(T_i) = \{H_1, \dots, H_i\}\), so the sum is \(2 \sum_{i=1}^{k} i = k(k+1)\). A variable assigned in the innermost block has \(\mathrm{DF}^{+} = \{H_1, \dots, H_k\}\): \(k\) phis. Sreedhar–Gao walks each block at most twice (Theorem 16.2.7) and never builds a frontier.

At scale. Cytron et al. measured frontier sizes linear in program size on real Fortran [CFRWZ91, §8]; the quadratic case needs deep nests of loops sharing exits. The real-world box below shows the quadratic growth in LLVM's own frontier printer on four nested do-while loops: 16 frontier entries for 4 phis.

Cytron et al.¶

Semi-pruned and pruned filters (Lesson 16.1) — trade-off: a scan or a liveness pass buys fewer phis; the frontier cost is unchanged.
Placement by DJ-graph merge sets (Das & Ramakrishna, [SSAB, Ch. 4]) — trade-off: precompute \(\mathrm{DF}^{+}(\{X\})\) for every \(X\) once, then each variable's placement is a union; quadratic space.
Renaming without stacks: record, for each block, the name live at its end and look up dominators on demand (the approach of SSA reconstruction, Lesson 16.4) — trade-off: no global walk, more lookups.

Sreedhar–Gao¶

Bucket queue instead of a heap (the original paper's "piggy bank" array indexed by level) — trade-off: truly linear, but LLVM prefers std::priority_queue keyed by (level, DFS number) for a deterministic output order.
Liveness filter inside the walk (LLVM setLiveInBlocks) — trade-off: pruned SSA for free, but requires the caller to compute live-in blocks per variable.
Merge relation and loop-nesting-forest methods (Ramalingam's construction on loop forests, [SSAB, Ch. 4]) — trade-off: other linear-time routes to DF⁺, more machinery.

7. In real compilers¶

Cytron et al.¶

GCC: phis at the IDF of each variable, versions from the renaming walk

Reproduce (gcc-14 = GCC 14.2.0, Ubuntu build 14.2.0-4ubuntu2~24.04.1; the source pointers are to the gcc-15 branch; any Linux):

cat > cyt.c <<'EOF'
int cyt(int n) {
  int x = 0, y = 1;
  while (n > 0) {
    if (n & 1)
      x = x + y;
    else
      y = y * 2;
    n = n - 1;
  }
  return x + y;
}
EOF
gcc-14 -O1 -fdump-tree-ssa-details=cyt.ssa -c cyt.c -o /dev/null
grep -E '^creating PHI' cyt.ssa
sed -n '/^int cyt/,$p' cyt.ssa

Output (complete from the creating lines and from the function header on):

creating PHI node in block #7 for n
creating PHI node in block #6 for x
creating PHI node in block #7 for x
creating PHI node in block #6 for y
creating PHI node in block #7 for y
int cyt (int n)
{
  int y;
  int x;
  int _1;
  int _10;

  <bb 2> :
  x_7 = 0;
  y_8 = 1;
  goto <bb 7>; [INV]

  <bb 3> :
  _1 = n_2 & 1;
  if (_1 != 0)
    goto <bb 4>; [INV]
  else
    goto <bb 5>; [INV]

  <bb 4> :
  x_13 = x_4 + y_6;
  goto <bb 6>; [INV]

  <bb 5> :
  y_12 = y_6 * 2;

  <bb 6> :
  # x_3 = PHI <x_13(4), x_4(5)>
  # y_5 = PHI <y_6(4), y_12(5)>
  n_14 = n_2 + -1;

  <bb 7> :
  # n_2 = PHI <n_9(D)(2), n_14(6)>
  # x_4 = PHI <x_7(2), x_3(6)>
  # y_6 = PHI <y_8(2), y_5(6)>
  if (n_2 > 0)
    goto <bb 3>; [INV]
  else
    goto <bb 8>; [INV]

  <bb 8> :
  _10 = x_4 + y_6;
  return _10;

}

What to notice: x is defined in blocks 2 and 4, so its IDF is \(\{6, 7\}\): 6 joins the two arms, 7 is the loop header, reached from 6 (Algorithm 16.2.1's second round). The operand x_4(5) of the phi in block 6 is the renaming stack's top at the end of block 5, which assigned only y: the version defined by block 7's phi, the nearest dominating definition (Lemma 16.2.5). n_9(D) is GCC's name for the parameter's "default definition", the implicit initial value \(v_0\) of Algorithm 16.2.3.

GCC's pipeline: insert_phi_nodes computes frontiers and compute_idf per variable, prune_unused_phi_nodes removes phis no use can reach (Theorem 16.1.14), and rewrite_blocks does the renaming walk with rewrite_stmt and rewrite_add_phi_arguments [GCC-IntoSSA].

Sreedhar–Gao¶

LLVM: 16 frontier entries, 4 phis

Reproduce (clang 23.1.2, opt 23.1.2):

cat > nest.c <<'EOF'
int nest(int *c) {
  int x = 0;
  do {
    do {
      do {
        do {
          x++;
        } while (c[3]);
      } while (c[2]);
    } while (c[1]);
  } while (c[0]);
  return x;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm nest.c -o nest.ll
opt -passes='simplifycfg,print<domfrontier>' -disable-output nest.ll 2>&1 | LC_ALL=C sort
opt -passes='simplifycfg,mem2reg' -S nest.ll | grep -E '^[a-z.0-9]+:| phi '

Output (complete):

  DomFrontier for BB %do.body is:    %do.body
  DomFrontier for BB %do.body1 is:   %do.body1 %do.body
  DomFrontier for BB %do.body2 is:   %do.body2 %do.body1 %do.body
  DomFrontier for BB %do.body3 is:   %do.body3 %do.body2 %do.body1 %do.body
  DomFrontier for BB %do.cond12 is:  %do.body
  DomFrontier for BB %do.cond4 is:   %do.body2 %do.body1 %do.body
  DomFrontier for BB %do.cond8 is:   %do.body1 %do.body
  DomFrontier for BB %do.end15 is:  
  DomFrontier for BB %entry is: 
DominanceFrontier for function: nest
entry:
do.body:                                          ; preds = %do.cond12, %entry
  %x.0 = phi i32 [ 0, %entry ], [ %inc, %do.cond12 ]
do.body1:                                         ; preds = %do.cond8, %do.body
  %x.1 = phi i32 [ %x.0, %do.body ], [ %inc, %do.cond8 ]
do.body2:                                         ; preds = %do.cond4, %do.body1
  %x.2 = phi i32 [ %x.1, %do.body1 ], [ %inc, %do.cond4 ]
do.body3:                                         ; preds = %do.body3, %do.body2
  %x.3 = phi i32 [ %x.2, %do.body2 ], [ %inc, %do.body3 ]
do.cond4:                                         ; preds = %do.body3
do.cond8:                                         ; preds = %do.cond4
do.cond12:                                        ; preds = %do.cond8
do.end15:                                         ; preds = %do.cond12

What to notice: the frontier sets grow like a triangle, \(1 + 2 + 3 + 4 + 3 + 2 + 1 = 16\) entries for 9 blocks (Proposition 16.2.8 with \(k = 4\)). mem2reg never builds them: it asks IDFCalculator for \(\mathrm{DF}^{+}(\{\mathit{entry}, \mathit{do.body3}\})\) restricted to the live-in blocks, a DJ-graph walk that touches each block at most twice (Algorithm 16.2.4), and gets the 4 loop headers.

Find where LLVM does it. Open llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp (LLVM 23.1.2), function PromoteMem2Reg::run. Question: after IDF.calculate(PHIBlocks), the blocks are sorted before phis are queued. By what key, and why does the comment-free sort matter for the output? (Quiz llvm-where-phiblocks-sort.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Cytron et al.	any flavor (filter at placement); renaming handles any CFG	\(O(\lvert V \rvert \cdot \lvert \mathrm{DF} \rvert + S)\), quadratic frontiers on nested repeat-until loops · fast on real code; lab: 130 ms for all three flavors on 306 listings	deterministic names from the dominator-tree walk	~120 lines (placement + renaming)	GCC into-SSA, textbooks, the lab's Cytron flavors
Sreedhar–Gao	same placement, pruned via a live-in filter; renaming as Cytron	\(O(n + m)\) per variable, no frontiers · immune to the quadratic case	deterministic order via (level, DFS) keys	~50 lines for placement	LLVM IDFCalculator (mem2reg, SSAUpdaterBulk, MemorySSA), Go (≥ 500 blocks)

Choose Cytron's placement when frontiers are available anyway (GCC keeps them for other passes) or when teaching. Choose Sreedhar–Gao when functions can be large or machine-generated: it is linear per variable and fits a live-in filter for free. Both need Cytron's renaming walk (or Braun's on-demand lookup, Lesson 16.3).

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch16.yaml`)	Drill	Flashcard tag	Exercises
Cytron et al.	`cytron-rename-trace`, `cytron-phi-operands`, `cytron-invariant`	`./course drill ssa-renaming`, `./course drill phi-placement`	`cytron`	lab L1 R3–R5, E1
Sreedhar–Gao	`sg-live-in`, `llvm-where-phiblocks-sort`	`./course drill idf --solution` (DJ-graph trace)	`sreedhar-gao`	E1 (with `ForwardIDFCalculator`)

Filling phi operands along tree edges

The operand of \(Y\)'s phi for the edge \(P \to Y\) is filled when the walk is in \(P\), from \(P\)'s stacks, not when it is in \(\mathrm{idom}(Y)\). \(P\) need not be \(Y\)'s parent in the dominator tree (G → H in the example); filling operands from the parent's stacks is the most common renaming bug, and the lab's Construct.* tests catch it by execution.

References¶

See the chapter references.

Lesson 16.2 — Construction with dominance frontiers: Cytron et al. and Sreedhar–Gao¶

1. Problem and motivation¶

Cytron et al.¶

Sreedhar–Gao¶

2. Definitions and algorithms¶

Cytron et al.¶

Sreedhar–Gao¶

3. Worked example¶

Cytron et al. on the running example¶

Sreedhar–Gao on the running example¶

4. Invariants and correctness¶

Cytron et al.¶

Sreedhar–Gao¶

5. Complexity¶

6. Variants and refinements¶

Cytron et al.¶

Sreedhar–Gao¶

7. In real compilers¶

Cytron et al.¶

Sreedhar–Gao¶

8. Comparison¶

9. Assessment¶

References¶