Lesson 16.1 — SSA properties, phi semantics and the flavors of SSA¶

Techniques: minimal SSA (Cytron et al. 1991), semi-pruned SSA (Briggs et al. 1998), pruned SSA (Choi, Cytron & Ferrante 1991); the properties they share: single definition, the dominance property, def-use chains, conventional vs transformed SSA, the parallel semantics of phi · Pebble implements: pruned SSA in pebble-mem2reg (E1) and all three flavors in lab L1 · Prerequisites: Lesson 8.4 (SSA and block arguments), Lesson 14.3 (liveness), Lesson 15.3 (DF, DF⁺) · Time: 4–5 hours

Chapter 8 defined SSA and showed that phi functions and block arguments are two spellings of one idea. This chapter is about building and leaving SSA. Before the algorithms, you need to know what they are supposed to produce: SSA is not unique. The same program has many correct SSA forms that differ in how many phis they contain. On the running example of this chapter, below, the three classical flavors place 10, 7 and 5 phis. All three are correct; they differ in which useless phis they allow.

The running example is Chapter 15's CFG (blocks A to I) written as a three-address listing (the tac format of lab 8.L1); it is labs/ch16-ssa-construct/inputs/running.tac and RUNNING_TAC in the oracle tools/course/lib/ssa.py. Every variable starts at 0. t is a temporary that is always written before it is read inside a block.

A:  i = 0 ; x = 1
B:  y = add x, i ; ifz i goto E
C:  x = add y, 2 ; t = lt x, 20 ; ifz t goto H
D:  y = mul y, 2
E:  t = gt y, 0 ; ifz t goto H
F:  x = add x, y ; y = sub y, 7 ; goto G
G:  t = rem x, 3 ; if t goto E
H:  i = add i, 1 ; t = lt i, 4 ; if t goto B
I:  return x

flowchart TD
  A([A]) --> B[B]
  B --> E[E]
  B --> C[C]
  C --> H[H]
  C --> D[D]
  D --> E
  E --> H
  E --> F[F]
  F --> G[G]
  G --> E
  G --> H
  H --> B
  H --> I[I]
  classDef hl fill:#fde68a,stroke:#b45309;
  class B,E,H hl;

Successors are listed jump target first, then the fall-through block, as the ch08 leaders algorithm produces them. The highlighted blocks are the join points where phis can appear.

1. Problem and motivation¶

The problem. Given a program over variables on a CFG \(G = (N, E, r)\), choose, for every variable \(v\), the set of blocks that receive a phi for \(v\), so that after renaming every use of \(v\) refers to exactly one definition. Fewer phis mean less memory, faster analyses and fewer copies when leaving SSA; but a placement must never be too small, or some use would see two reaching definitions. Where in the pipeline: pebblec lowers Pebble to LLVM IR with every local in an alloca; pebble-mem2reg (E1) or LLVM's mem2reg then chooses the phi placement. Every SSA-based pass of Chapters 17-19 pays for each phi it sees.

Minimal SSA¶

Cytron, Ferrante, Rosen, Wegman and Zadeck defined minimal SSA: a phi for \(v\) exactly at the blocks where two different definitions of \(v\) first meet, which is the iterated dominance frontier of \(v\)'s definition blocks [CFRWZ91, §5.1]. "Minimal" is minimal among placements that depend only on where \(v\) is defined. It ignores uses: a variable that is dead at a join still gets a phi there. The IBM papers that introduced SSA used it for value numbering and redundancy elimination [AWZ88, RWZ88].

Semi-pruned SSA¶

Briggs, Cooper, Harvey and Simpson observed that most dead phis in minimal SSA belong to block-local names: temporaries such as t above that are always written before being read inside every block that reads them [BCHS98]. They keep minimal placement, but only for global names, the variables that are read in some block before being written there. It costs one linear scan; no liveness analysis. The Go compiler uses it for large functions [Go-SSAGen].

Pruned SSA¶

Choi, Cytron and Ferrante place a phi for \(v\) at a join block only if \(v\) is live on entry to that block [CCF91]. Every phi of pruned SSA can reach a real use, so none is dead. It needs liveness, but liveness of each promoted variable is a cheap backward walk. LLVM's mem2reg builds pruned SSA [LLVM-Mem2Reg], and so does GCC, by deleting the phis of minimal SSA that no use can reach [GCC-IntoSSA].

2. Definitions and algorithms¶

Chapter 8's Definition 8.4.1 (SSA, strict SSA) and Definition 8.4.2 (phi semantics) are assumed. This section makes the phi semantics precise enough to prove things about, and defines the flavors.

Definition 16.1.1 (Variable program)

A variable program is a flowgraph \(G = (N, E, r)\) (Definition 15.1.1) whose blocks hold sequences of statements over a finite set \(V\) of variables. Each statement defines at most one variable and uses zero or more. \(\mathrm{defs}(v) \subseteq N\) is the set of blocks that define \(v\), including the entry \(r\): every variable has an implicit initial definition at the start of \(r\) (0 in Tiny and TAC, undef in LLVM). A use of \(v\) in block \(B\) is upward exposed if no statement of \(B\) before it defines \(v\); \(\mathrm{UE}(B)\) is the set of variables with an upward-exposed use in \(B\) and \(\mathrm{Kill}(B)\) the set of variables defined in \(B\).

Definition 16.1.2 (Phi function; operational semantics)

Let \(B\) have predecessors \(P_1, \dots, P_k\) (a fixed order) and phis \(x_\ell \gets \phi(a_{\ell 1}, \dots, a_{\ell k})\) for \(\ell = 1, \dots, m\). A state is a map \(\sigma\) from names to values. The transition along the edge \(P_j \to B\) is

\[ \sigma \xrightarrow{P_j \to B} \sigma[x_1 \mapsto \sigma(a_{1j}), \dots, x_m \mapsto \sigma(a_{mj})], \]

where \(\sigma(c) = c\) for a constant \(c\). All right-hand sides are read in the state before the edge, then all left-hand sides are written: a parallel copy selected by the edge. Phis are not instructions of \(B\); they happen on the edge, before the first instruction of \(B\) runs. A multi-edge (two edges \(P \to B\), as in cbr c, B, B) needs two predecessor slots, one per edge.

Why the parallel reading matters

Take \(a \gets \phi(1, b)\) and \(b \gets \phi(2, a)\) at the loop header of swap in Lesson 16.5 (its first real-world box runs it). Along the back edge the new state has \(a = \sigma(b)\) and \(b = \sigma(a)\): the values are swapped. Executing the phis one after the other would give \(a = \sigma(b)\), then \(b = a = \sigma(b)\): both equal to the old \(b\).

Proposition 16.1.3 (Parallel and sequential phis differ exactly on read-after-write)

For the phis of \(B\) on the edge \(P_j \to B\), executing \(x_\ell \gets a_{\ell j}\) one at a time in the order \(\ell = 1, \dots, m\) yields the state of Definition 16.1.2 for every initial state \(\sigma\) if and only if there are no \(\ell' < \ell\) with \(a_{\ell j} = x_{\ell'}\) and \(a_{\ell' j} \neq x_{\ell'}\): no copy reads a phi result that an earlier, non-trivial copy has already written.

Proof

(\(\Leftarrow\)) By induction on \(\ell\): when \(x_\ell \gets a_{\ell j}\) runs, \(a_{\ell j}\) has not been written by the earlier copies (by hypothesis), so it still holds \(\sigma(a_{\ell j})\); and later copies never write \(x_\ell\) again because the \(x_\ell\) are distinct names (single assignment). So every \(x_\ell\) ends with \(\sigma(a_{\ell j})\) and nothing else changes. (\(\Rightarrow\)) Suppose \(a_{\ell j} = x_{\ell'}\) with \(\ell' < \ell\) and the copy into \(x_{\ell'}\) is not trivial (\(a_{\ell' j} \neq x_{\ell'}\)). Choose \(\sigma\) with \(\sigma(x_{\ell'}) \neq \sigma(a_{\ell' j})\) (names can hold any value; if \(a_{\ell' j}\) is a constant pick \(\sigma(x_{\ell'})\) different from it). The sequential execution sets \(x_{\ell'}\) to \(\sigma(a_{\ell' j})\) first, so \(x_\ell\) receives \(\sigma(a_{\ell' j})\), whereas Definition 16.1.2 gives it \(\sigma(x_{\ell'})\): the states differ.

This is the swap problem of Lesson 16.6 in its smallest form, and the reason Lesson 16.7 needs a sequentialization algorithm.

Definition 16.1.4 (Dominance property; def-use chains)

An SSA program has the dominance property (is strict, Definition 8.4.1) if the definition of every name dominates each of its uses, where the use of \(a_{\ell j}\) by a phi counts as a use at the end of \(P_j\). Its def-use chains map each name to the list of its uses; its use-def chains map each use to the unique definition of the name it uses.

Proposition 16.1.5 (Size of def-use information)

Let a non-SSA program have \(D\) definition sites and \(U\) use sites. Reaching-definition chains can need \(\Theta(D \cdot U)\) pairs. In SSA, use-def chains have exactly \(U'\) entries, where \(U'\) is the number of uses including phi operands.

Proof

Upper bound in SSA: each name has one definition, so each use has one use-def entry. Lower bound without SSA: take \(k\) blocks \(d_1, \dots, d_k\), each assigning \(x\) and jumping to one join block \(J\), which reads \(x\) in \(k\) statements. Every definition reaches every use: \(D \cdot U = k^2\) reaching pairs. In SSA one phi at \(J\) with \(k\) operands merges the definitions and the \(k\) uses name the phi: \(2k\) use-def entries.

Definition 16.1.6 (Liveness of a variable)

\(v\) is live-in at \(B\), written \(v \in \mathrm{LiveIn}(B)\), if some path from the start of \(B\) reaches an upward-exposed use of \(v\) without passing a definition of \(v\). This is the least solution of \(\mathrm{LiveOut}(B) = \bigcup_{S \in \mathrm{succs}(B)} \mathrm{LiveIn}(S)\), \(\mathrm{LiveIn}(B) = \mathrm{UE}(B) \cup (\mathrm{LiveOut}(B) \setminus \mathrm{Kill}(B))\) (Lesson 14.3).

Definition 16.1.7 (Minimal, semi-pruned and pruned placement)

For a variable \(v\) let \(\Phi_{\min}(v) = \mathrm{DF}^{+}(\mathrm{defs}(v))\) (Definition 15.3.2). A variable is global if \(v \in \mathrm{UE}(B)\) for some block \(B\). Then

\[ \begin{aligned} \Phi_{\min}(v) &= \mathrm{DF}^{+}(\mathrm{defs}(v)) \\ \Phi_{\mathrm{semi}}(v) &= \Phi_{\min}(v) \text{ if } v \text{ is global, else } \emptyset \\ \Phi_{\mathrm{pruned}}(v) &= \Phi_{\min}(v) \cap \{\, B \mid v \in \mathrm{LiveIn}(B) \,\}. \end{aligned} \]

Minimal, semi-pruned and pruned SSA are the SSA forms obtained by placing a phi for \(v\) at the blocks of \(\Phi_{\min}(v)\), \(\Phi_{\mathrm{semi}}(v)\) and \(\Phi_{\mathrm{pruned}}(v)\) respectively and then renaming (Algorithm 16.2.3).

Definition 16.1.8 (Dead phi; conventional and transformed SSA)

A phi is useful if its result reaches a non-phi use through a chain of phi operands; otherwise it is dead (this includes cycles of phis that only use each other). Two names interfere if their live ranges intersect (in strict SSA: one is live at the definition of the other, Lemma 16.7.1). The phi congruence classes are the classes of the smallest equivalence relation relating the result and the operands of every phi. The program is in conventional SSA (CSSA) if no two names of one phi congruence class interfere; otherwise it is transformed SSA (TSSA) [SJGS99].

CSSA and TSSA on the swap loop

In the LLVM output of the swap loop (§7 box of Lesson 16.4) %a.0 = phi [0, %entry], [%b.0, %for.inc] and %b.0 = phi [1, %entry], [%add, %for.inc]: \(a_0\) and \(b_0\) are in one congruence class (one is an operand of the other's phi) and both are live at the loop header: TSSA. Dropping the phis by giving all names of a class one variable would be wrong exactly here.

The algorithm that computes all three placements from one scan, one liveness solution and one DF⁺ per variable:

Algorithm 16.1.9 (Flavor placement)

Input: a variable program (Definition 16.1.1) with its dominance frontiers.
Output: \(\Phi_{\min}(v)\), \(\Phi_{\mathrm{semi}}(v)\), \(\Phi_{\mathrm{pruned}}(v)\) for every \(v\).
Precondition: every block is reachable; \(\mathrm{DF}\) is correct (Algorithm 15.3.6 or 15.3.8).
Postcondition: the three sets satisfy Definition 16.1.7.
Invariant: after the scan, global[v] iff \(v \in \mathrm{UE}(B)\) for a scanned \(B\); after the liveness loop, LiveIn is the least solution of Definition 16.1.6.

function FlavorPlacement(G, DF):
    for B in N:                                    # one scan: UE, Kill, defs, globals
        killed ← {}
        for statement s in B, in order:
            for v in uses(s):
                if v ∉ killed: UE[B] ← UE[B] ∪ {v}; global[v] ← true
            if s defines v: killed ← killed ∪ {v}; defs[v] ← defs[v] ∪ {B}
        Kill[B] ← killed
    for v in V: defs[v] ← defs[v] ∪ {r}            # the implicit initial value
    LiveIn ← least solution of Definition 16.1.6   # round-robin in postorder
    for v in V:
        M ← IteratedDF(DF, defs[v])                # Algorithm 15.3.11
        Phi_min[v] ← M
        Phi_semi[v] ← M if global[v] else {}
        Phi_pruned[v] ← { B ∈ M | v ∈ LiveIn[B] }
    return Phi_min, Phi_semi, Phi_pruned

3. Worked example¶

The oracle tools/course/lib/ssa.py computes every table below (phi_placement, var_liveness); ./course drill phi-placement --solution prints the same tables for random programs.

Minimal SSA on the running example¶

Definition blocks (with the entry for the initial values) and DF⁺, from the frontiers of Lesson 15.3 (\(\mathrm{DF}(B) = \{B\}\), \(\mathrm{DF}(C) = \{E, H\}\), \(\mathrm{DF}(D) = \{E\}\), \(\mathrm{DF}(E) = \mathrm{DF}(F) = \mathrm{DF}(G) = \{E, H\}\), \(\mathrm{DF}(H) = \{B\}\), \(\mathrm{DF}(A) = \mathrm{DF}(I) = \emptyset\)):

variable	defs(v)	DF⁺ worklist pops (added)	\(\Phi_{\min}(v)\)
i	{A, H}	A; H (+B); B	{B}
x	{A, C, F}	A; C (+E, H); F; E; H (+B); B	{B, E, H}
y	{A, B, D, F}	A; B (+B); D (+E); F (+H); E; H	{B, E, H}
t	{A, C, E, G, H}	A; C (+E, H); E; G; H (+B); B	{B, E, H}

Minimal SSA has \(1 + 3 + 3 + 3 = 10\) phis. Three of them, the phis for t, are useless: t is overwritten before every read.

Semi-pruned SSA on the running example¶

The scan of Algorithm 16.1.9 gives the upward-exposed sets: \(\mathrm{UE}(B) = \{i, x\}\), \(\mathrm{UE}(C) = \{y\}\), \(\mathrm{UE}(D) = \{y\}\), \(\mathrm{UE}(E) = \{y\}\), \(\mathrm{UE}(F) = \{x, y\}\), \(\mathrm{UE}(G) = \{x\}\), \(\mathrm{UE}(H) = \{i\}\), \(\mathrm{UE}(I) = \{x\}\), \(\mathrm{UE}(A) = \emptyset\). So \(i, x, y\) are global and \(t\) is not. Semi-pruned SSA drops the three phis of t: 7 phis.

Pruned SSA on the running example¶

Liveness, round-robin in postorder (I, H, G, F, E, D, C, B, A), with \(\mathrm{Kill}(A) = \{i, x\}\), \(\mathrm{Kill}(B) = \{y\}\), \(\mathrm{Kill}(C) = \{x, t\}\), \(\mathrm{Kill}(D) = \{y\}\), \(\mathrm{Kill}(E) = \mathrm{Kill}(G) = \{t\}\), \(\mathrm{Kill}(F) = \{x, y\}\), \(\mathrm{Kill}(H) = \{i, t\}\):

block	pass 1 LiveIn	pass 2 LiveIn	pass 3 LiveIn
I	{x}	{x}	{x}
H	{i, x}	{i, x}	{i, x}
G	{i, x}	{i, x, y}	{i, x, y}
F	{i, x, y}	{i, x, y}	{i, x, y}
E	{i, x, y}	{i, x, y}	{i, x, y}
D	{i, x, y}	{i, x, y}	{i, x, y}
C	{i, y}	{i, y}	{i, y}
B	{i, x}	{i, x}	{i, x}
A	{}	{}	{}

Pass 1: G is visited before E, so y, which G's successor E needs, arrives only in pass 2 (bold). Pass 3 changes nothing.
\(y\) is not live at B (B writes y before reading it) and not live at H; it is live at E.

variable	\(\Phi_{\min}\)	live-in blocks	\(\Phi_{\mathrm{pruned}}\)
i	{B}	{B, C, D, E, F, G, H}	{B}
x	{B, E, H}	{B, D, E, F, G, H, I}	{B, E, H}
y	{B, E, H}	{C, D, E, F, G}	{E}
t	{B, E, H}	{}	{}

Pruned SSA has 5 phis: \(i\) at B, \(x\) at B, E, H, and \(y\) at E. Chapter 15's mem2reg box placed \(x\)'s phis at the same B, E, H.

Try it

./course drill phi-placement --seed 4 --difficulty medium --solution shows the three flavors, the DF⁺ worklists and the liveness passes on a random 8-block CFG.

4. Invariants and correctness¶

Minimal SSA¶

Theorem 16.1.10 (Minimal placement is the least placement determined by definitions)

(a) If phis for \(v\) are placed at a set \(P \supseteq \mathrm{DF}^{+}(\mathrm{defs}(v))\), renaming (Algorithm 16.2.3) gives every use of \(v\) a name whose definition is, on every path from \(r\), the last definition of \(v\) before the use. (b) For every \(Y \in \mathrm{DF}^{+}(\mathrm{defs}(v))\) there is a program with the same CFG and the same definition sites of \(v\) in which no correct SSA form omits a phi for \(v\) at \(Y\). So \(\Phi_{\min}(v)\) is the least placement that depends only on \(\mathrm{defs}(v)\).

Proof sketch (full proof: [CFRWZ91, §5.1])

(a) is Theorem 16.2.6 of the next lesson. (b) By Theorem 15.3.10, \(\mathrm{DF}^{+}(\mathrm{defs}(v)) = J^{+}(\mathrm{defs}(v))\). For \(Y \in J(\mathrm{defs}(v) \cup \Phi)\), where \(\Phi\) is the part of \(\mathrm{DF}^{+}\) found so far, there are two paths from different definition points that meet first at \(Y\) (Definition 15.3.9). Insert a use of \(v\) at the start of \(Y\). Along the two paths it must see two different definitions (choose the program's values so that they differ), so a single name can serve it only if that name is defined at \(Y\) itself, before the use: a phi at \(Y\). Induction on the iteration of Definition 15.3.2 covers all of \(\mathrm{DF}^{+}\), because a phi placed at \(Y\) is itself a definition that the next iteration must treat as such.

Semi-pruned SSA¶

Theorem 16.1.11 (Semi-pruning removes only dead phis)

If \(v\) is not global, every phi for \(v\) in minimal SSA is dead.

Proof

If \(v\) is not global, every use of \(v\) in any block \(B\) is preceded in \(B\) by a definition of \(v\), so renaming gives it the name of that local definition, never a phi's name: no non-phi use names a phi for \(v\). A phi for \(v\) can then only be used by other phis for \(v\) (the operand of a phi for \(v\) at the end of a predecessor is the current name of \(v\)). So no chain of phi operands reaches a non-phi use: all phis for \(v\) are dead (Definition 16.1.8).

Pruned SSA¶

Theorem 16.1.12 (Flavor inclusions)

For every variable \(v\): \(\Phi_{\mathrm{pruned}}(v) \subseteq \Phi_{\mathrm{semi}}(v) \subseteq \Phi_{\min}(v)\).

Proof

The second inclusion is immediate from Definition 16.1.7. For the first, let \(B \in \Phi_{\mathrm{pruned}}(v)\), so \(B \in \Phi_{\min}(v)\) and \(v \in \mathrm{LiveIn}(B)\). By Definition 16.1.6 there is a path from the start of \(B\) to an upward-exposed use of \(v\) in some block \(B'\). Then \(v \in \mathrm{UE}(B')\), so \(v\) is global and \(\Phi_{\mathrm{semi}}(v) = \Phi_{\min}(v) \ni B\).

Lemma 16.1.13 (Current names along definition-free paths)

In minimal SSA after renaming, let \(\mathrm{cur}(q)\) be the name a use of \(v\) at point \(q\) receives. If a path \(\pi\) from point \(p\) to point \(q\) passes no statement defining \(v\) and enters no block holding a phi for \(v\), then \(\mathrm{cur}(p) = \mathrm{cur}(q)\).

Proof

By Theorem 16.2.6, on every path from \(r\) to a point, the last definition of \(v\) (a statement or a phi) before that point is the one renaming names there. Extend \(\pi\) by any path \(r \leadsto p\). The last definition before \(q\) on \(r \leadsto p \cdot \pi\) is the last one before \(p\), because \(\pi\) contains none; so both points name the same definition.

Theorem 16.1.14 (Pruned = minimal minus dead phis)

In minimal SSA, the phi for \(v\) at \(Y\) is useful if and only if \(v \in \mathrm{LiveIn}(Y)\). Hence deleting the dead phis of minimal SSA (and nothing else) yields exactly pruned SSA.

Proof

(\(\Leftarrow\)) Let \(\pi\) be a path from the start of \(Y\) to an upward-exposed use \(u\) of \(v\) passing no statement that defines \(v\). Induct on the number \(k\) of block entries on \(\pi\) after the start of \(Y\) into blocks that hold a phi for \(v\). If \(k = 0\), Lemma 16.1.13 applied from the point just after \(Y\)'s phis (where \(\mathrm{cur}\) is \(Y\)'s phi) to \(u\) shows that \(u\) names \(Y\)'s phi: useful. If \(k \geq 1\), let \(a \to b\) be the first such entry on \(\pi\). By Lemma 16.1.13 on the prefix up to the end of \(a\), the operand of \(b\)'s phi for the edge \(a \to b\) is \(Y\)'s phi. The suffix of \(\pi\) from the start of \(b\) shows \(v \in \mathrm{LiveIn}(b)\) with \(k - 1\) phi entries, so by induction \(b\)'s phi is useful, and through it \(Y\)'s phi is useful. (\(\Rightarrow\)) Let \(Y\)'s phi \(p_0\) be useful: phis \(p_0, p_1, \dots, p_k\) for \(v\) where \(p_s\) is the operand of \(p_{s+1}\) on an edge \(a_s \to b_{s+1}\) (\(b_{s+1}\) the block of \(p_{s+1}\)), and a non-phi use \(u\) of \(p_k\). Since \(\mathrm{cur}(\text{end of } a_s) = p_s\), Theorem 16.2.6 on any path \(r \leadsto a_s\) says the last definition of \(v\) on it is \(p_s\); its suffix from the start of \(p_s\)'s block to the end of \(a_s\) passes no statement defining \(v\). The same holds for the use \(u\) and \(p_k\). Concatenating these suffixes with the edges \(a_s \to b_{s+1}\) gives a path from the start of \(Y\) to \(u\) that passes no statement defining \(v\) (phis are not statements of the original program): \(v \in \mathrm{LiveIn}(Y)\).

This theorem is why GCC can compute pruned SSA without liveness sets: it places minimal phis and runs a small dead-phi elimination from the uses (prune_unused_phi_nodes in gcc/tree-into-ssa.cc [GCC-IntoSSA]), and why the oracle test test_inclusions_and_pruned_is_minimal_minus_dead checks useful_phis(minimal) == pruned on 400 random programs.

Theorem 16.1.15 (Construction yields conventional SSA)

Renaming (Algorithm 16.2.3) applied to any of the three placements, without copy propagation, yields CSSA: every phi congruence class consists of versions of one variable and no two of them interfere.

Proof sketch (full proof: [SJGS99]; [SSAB, Ch. 3])

A phi for \(v\) only mentions versions of \(v\), so each class holds versions of one variable. At any point \(p\), the version of \(v\) that is live at \(p\) is the top of \(v\)'s renaming stack at \(p\) (the nearest definition dominating \(p\)): any live version \(v_i\) has a use \(q\) reachable from \(p\) without redefinition, and \(q\) names the nearest dominating definition of \(v\) at \(q\), which is also the nearest one at \(p\) (Lemma 16.1.13). Two distinct versions therefore never are live at the same point. Copy propagation breaks this: after replacing uses of \(v_i\) by \(w_j\) (a copy \(v_i \gets w_j\)), a version of \(w\) can be live together with a version of \(w\) in its own class, which is how TSSA arises (Lesson 16.6).

When the arguments break. Unreachable blocks are excluded from \(\mathrm{DF}\) and from liveness; a definition in an unreachable block must not be counted in \(\mathrm{defs}(v)\) or its frontier would add bogus phis. Irreducible CFGs are fine for all three flavors: nothing above assumed reducibility.

5. Complexity¶

\(n\) = blocks, \(m\) = CFG edges, \(\lvert V \rvert\) = variables, \(S\) = statements, \(\lvert \mathrm{DF} \rvert = \sum_X \lvert \mathrm{DF}(X) \rvert\), \(A\) = the number of phis placed.

Technique	Time (worst)	Time (typical)	Space	Phis
Minimal	\(O(S + \lvert V \rvert \cdot \lvert \mathrm{DF} \rvert)\) with the worklist, \(O(S + \lvert V \rvert (n + m))\) with Sreedhar-Gao	linear	\(O(\lvert \mathrm{DF} \rvert + A)\)	\(\le \lvert V \rvert \cdot n\)
Semi-pruned	minimal + one \(O(S)\) scan	slightly below minimal (fewer variables)	+ \(\lvert V \rvert\) bits	\(\le\) minimal
Pruned	minimal + liveness: \(O(\lvert V \rvert (n + m))\) with one backward walk per variable	a few percent above semi-pruned	+ live-in sets	\(\le\) semi-pruned

Justification. The scan of Algorithm 16.1.9 visits each statement once. Algorithm 15.3.11 costs \(O(\lvert \mathrm{DF} \rvert)\) per variable (each block popped once, each frontier scanned once), Algorithm 16.2.4 \(O(n + m)\) per variable (Theorem 15.3.18). Liveness of one variable by the backward walk of Algorithm 16.4.2 visits each block and edge once; the round-robin solver of Definition 16.1.6, visiting blocks in postorder (reverse postorder of the reverse CFG), needs at most \(d(G^{R}) + 2\) passes over all blocks for all variables at once (Theorem 14.4.6 on the reverse CFG).

Proposition 16.1.16 (The flavors can differ by a factor of n)

(a) There are programs with \(\Theta(\lvert V \rvert)\) variables, \(n\) blocks and \(\lvert V \rvert\) minimal phis but no semi-pruned phi. (b) There are programs where semi-pruned SSA places \(\Theta(n)\) phis and pruned SSA none.

Proof

(a) One loop (header \(H\), body \(L\), back edge \(L \to H\)) whose body assigns \(k\) temporaries \(t_1, \dots, t_k\) and reads each after assigning it. \(\mathrm{DF}(L) = \{H\}\), so each \(t_j\) gets a minimal phi at \(H\): \(k\) phis. No \(t_j\) is upward exposed anywhere, so semi-pruned SSA places none. (b) Block \(W\) reads \(x\) (so \(x\) is global), then \(k\) diamonds \(D_1, \dots, D_k\) in sequence where one arm of each assigns \(x\), then a block \(U\) that assigns \(x\) before its only read. Each diamond's join \(J_j\) is in \(\mathrm{DF}\) of the assigning arm, so minimal and semi-pruned SSA place \(k\) phis. \(x\) is live at no \(J_j\) (every path from \(J_j\) reaches \(U\)'s definition before any read), so pruned SSA places none. With \(n = 3k + 3\) blocks both gaps are \(\Theta(n)\).

At scale. On the 303 listings of the lab corpus (tests/ch16/Inputs/construct-goldens.txt, lowered random Tiny programs and random goto programs), minimal SSA places 19 106 phis, semi-pruned 8 620 and pruned 4 477: temporaries account for most of the difference, as Briggs et al. observed on Fortran code [BCHS98].

Minimal SSA¶

Maximal SSA (a phi for every variable at every join, Aycock-Horspool's starting point, Lesson 16.3) — trade-off: trivial to place, far more phis before minimization.
Minimal in Braun et al.'s sense (no redundant phi sets after copy folding, Definition 16.3.1) — trade-off: smaller than Cytron-minimal because copies are folded, but the phi set then depends on the values, not only on the definition sites [BBH+13].

Semi-pruned SSA¶

Local-name elimination during parsing: many front ends give temporaries fresh names from the start, so they never become variables (LLVM's instruction results, Go's SSA values) — trade-off: only user variables and address-taken slots remain to be placed.
Single-block variables (GCC's NEED_PHI_STATE_NO, Go's "prunes any basic-block-only variables") skip even the frontier computation — trade-off: a cheaper filter than full globality, same result on block-local names [GCC-IntoSSA, Go-SSAGen].

Pruned SSA¶

Dead-phi elimination after minimal placement (GCC's prune_unused_phi_nodes) — trade-off: no liveness sets; relies on Theorem 16.1.14.
Per-variable live-in walk (LLVM ComputeLiveInBlocks) — trade-off: one backward walk per promoted variable, cheap because allocas have few uses [LLVM-Mem2Reg].
Fast liveness checking answers "is \(v\) live-in at \(B\)?" from the dominator tree without sets [BHG+08] — trade-off: precomputation per CFG, queries in near-constant time; used in Lesson 16.7.

7. In real compilers¶

Minimal SSA¶

No production compiler emits minimal SSA as its final product: every one prunes. But the phi placement machinery is Cytron's, and the minimal set is visible as the blocks LLVM's frontier analysis reports, before liveness filters them.

DF⁺ says two phis for x, LLVM places one

Reproduce (clang 23.1.2, opt 23.1.2; any OS):

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

Output (complete):

  DomFrontier for BB %do.body is:    %do.body
  DomFrontier for BB %do.cond is:    %do.body
  DomFrontier for BB %do.end is:    
  DomFrontier for BB %entry is: 
  DomFrontier for BB %if.end is:     %do.body
  DomFrontier for BB %if.then is:    %if.end
DominanceFrontier for function: minimal
entry:
do.body:                                          ; preds = %do.cond, %entry
  %s.0 = phi i32 [ 0, %entry ], [ %add, %do.cond ]
if.then:                                          ; preds = %do.body
if.end:                                           ; preds = %if.then, %do.body
  %x.0 = phi i32 [ 1, %if.then ], [ %0, %do.body ]
do.cond:                                          ; preds = %if.end
do.end:                                           ; preds = %do.cond

What to notice: x is stored in entry, do.body and if.then, so \(\Phi_{\min}(x) = \mathrm{DF}^{+}(\{\mathit{entry}, \mathit{do.body}, \mathit{if.then}\}) = \{\mathit{if.end}, \mathit{do.body}\}\) (read it off the frontiers: \(\mathrm{DF}(\mathit{if.then}) \ni \mathit{if.end}\) and \(\mathrm{DF}(\mathit{do.body}) \ni \mathit{do.body}\)). Minimal SSA would place two phis for x. LLVM places one, at if.end: at do.body the old x is dead, because the loop body overwrites it before reading it (Theorem 16.1.14). s, live around the loop, gets its minimal phi at do.body.

Semi-pruned SSA¶

The Go compiler builds SSA with Braun et al.'s algorithm for functions of at most 500 blocks and with Sreedhar-Gao for larger ones (smallBlocks in src/cmd/compile/internal/ssagen/phi.go [Go-SSAGen]). The large-function path first collects the variables that have an upward-exposed read (a FwdRef), "prun[ing] any basic-block-only variables", and places DF⁺ phis for those, with a "TODO: if the variable is dead at c, skip it": semi-pruned SSA.

Go places a dead phi in a 1 000-block function, and not in a small one

Reproduce (Go 1.24.7, linux/amd64; the generator writes one function with 300 ifs and one with 3):

mkdir big && cd big
python3 - <<'EOF'
def gen(n, name):
    L = [f"func {name}(c []int) int {{", "\tx, s := 0, 0", "\tif c[0] > 0 {", "\t\tx = 1",
         "\t} else {", "\t\tx = 2", "\t}", "\tx = c[1]"]
    for i in range(n):
        L.append(f"\tif c[{i%7}] > {i} {{\n\t\ts += {i}\n\t}}")
    L += ["\tif c[2] > 0 {", "\t\ts += x", "\t}", "\treturn s", "}"]
    return "\n".join(L)
open("big.go", "w").write("package big\n\n" + gen(300, "Big") + "\n\n" + gen(3, "Small") + "\n")
open("go.mod", "w").write("module big\ngo 1.24\n")
EOF
for f in Small Big; do
  GOSSAFUNC="$f+" go build . 2>&1 | sed -n "/^compiling $f/,/pass number lines begin/p" | grep -c 'Phi.*(x\[int\])'
done
GOSSAFUNC="Big+" go build . 2>&1 | sed -n '/^compiling Big/,/pass number lines begin/p' | grep -B1 -A2 'Phi.*(x\[int\])'

Output (complete):

0
1
  b2: <- b3 b4
    (-10) v4243 = Phi <int> v17 v18 (x[int]) DEAD
    (-10) v19 = Copy <[]int> v6 (c[[]int])
    (10) v20 = SliceLen <int> v19

What to notice: x is assigned in both arms (v17 = 1, v18 = 2) and then overwritten by x = c[1] before any read, yet it is a global name: the final s += x reads it in another block. In Big (1 212 blocks after construction) the Sreedhar-Gao path places the minimal phi at the join b2, and Go's own printer already marks it DEAD: semi-pruned SSA keeps a phi that pruned SSA would not (Proposition 16.1.16(b)). In Small Braun's on-demand construction never creates it. Go's early deadcode pass removes it afterwards.

Pruned SSA¶

LLVM's mem2reg: no phi for a variable that is dead at the join

Reproduce (clang 23.1.2, opt 23.1.2):

cat > pruned.c <<'EOF'
int pruned(int c, int n) {
  int x;
  if (c)
    x = 1;
  else
    x = 2;
  x = n;
  return x;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm pruned.c -o pruned.ll
opt -passes=mem2reg -S pruned.ll | sed -n '/^define/,/^}/p'

Output (complete):

define dso_local i32 @pruned(i32 noundef %c, i32 noundef %n) #0 {
entry:
  %tobool = icmp ne i32 %c, 0
  br i1 %tobool, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  br label %if.end

if.else:                                          ; preds = %entry
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  ret i32 %n
}

What to notice: if.end is in \(\mathrm{DF}^{+}\) of the two stores, so minimal SSA would put phi i32 [1, %if.then], [2, %if.else] there. x is not live at if.end (the store of n comes before the load), so PromoteMem2Reg::ComputeLiveInBlocks leaves if.end out of the live-in set, and IDFCalculator::setLiveInBlocks filters it (Definition 16.1.7). The stores of 1 and 2 simply disappear.

Find where LLVM does it. Open llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp (LLVM 23.1.2) and read PromoteMem2Reg::ComputeLiveInBlocks. Question: when a block both stores to and loads from the alloca, how does the function decide whether that block is live-in? (Quiz llvm-where-livein.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Minimal SSA	every phi merges two definitions, but dead phis remain	DF⁺ per variable · fastest placement	19 106 phis on the lab corpus	DF⁺ only	textbooks; the basis of the other two
Semi-pruned SSA	no phis for block-local names; dead phis of global names remain	+ one linear scan · as fast as minimal	8 620 phis on the lab corpus	+ UE scan (~15 lines)	Go (≥ 500 blocks), EaC's construction
Pruned SSA	no dead phis (Theorem 16.1.14)	+ liveness per variable · cheap for allocas	4 477 phis on the lab corpus	+ liveness (~30 lines)	LLVM mem2reg, GCC into-SSA, Pebble E1

Choose minimal SSA when you study the construction or feed an optimizer that deletes dead phis anyway. Choose semi-pruned SSA when you want most of the saving with no dataflow analysis, for example in a fast JIT tier. Choose pruned SSA when later passes pay for each phi, which is almost always; allocas have few uses, so their liveness is cheap.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch16.yaml`)	Drill	Flashcard tag	Exercises
Minimal SSA	`flavor-counts`, `minimal-dead-phi`, `phi-parallel`	`./course drill phi-placement`	`minimal-ssa`	lab L1 R3
Semi-pruned SSA	`flavor-counts`, `semi-pruned-global`	`./course drill phi-placement --difficulty medium`	`semi-pruned-ssa`	lab L1 R4
Pruned SSA	`flavor-counts`, `pruned-theorem`, `llvm-where-livein`	`./course drill phi-placement --difficulty hard`	`pruned-ssa`	E1, lab L1 R5

\"Minimal\" does not mean \"fewest phis\"

Minimal SSA is minimal only among placements computed from definition sites. It can have many more phis than pruned SSA (Proposition 16.1.16), and Braun et al.'s "minimal" is a third notion (Lesson 16.3). When a paper says "minimal", check which one it means.

References¶

See the chapter references.

Lesson 16.1 — SSA properties, phi semantics and the flavors of SSA¶

1. Problem and motivation¶

Minimal SSA¶

Semi-pruned SSA¶

Pruned SSA¶

2. Definitions and algorithms¶

3. Worked example¶

Minimal SSA on the running example¶

Semi-pruned SSA on the running example¶

Pruned SSA on the running example¶

4. Invariants and correctness¶

Minimal SSA¶

Semi-pruned SSA¶

Pruned SSA¶

5. Complexity¶

6. Variants and refinements¶

Minimal SSA¶

Semi-pruned SSA¶

Pruned SSA¶

7. In real compilers¶

Minimal SSA¶

Semi-pruned SSA¶

Pruned SSA¶

8. Comparison¶

9. Assessment¶

References¶