Lesson 16.8 — Beyond scalar SSA: SSI and e-SSA, gated SSA, Memory SSA, Array SSA, Hashed SSA¶

Techniques: static single information form (SSI) and extended SSA (e-SSA, π-assignments), gated SSA (γ, μ, η gating functions), Memory SSA (one memory variable, MemoryDef/MemoryUse/MemoryPhi), Array SSA (definition φ and control φ on whole arrays, heap arrays), Hashed SSA (virtual variables, μ and χ, zero versions, hash-consed expressions) · Pebble implements: none; these are theory + LLVM analyses that later chapters use (PredicateInfo in Ch 17's SCCP and GVN, MemorySSA in Ch 19) · Prerequisites: Lesson 16.2 (placement and renaming), Lesson 16.4 (what mem2reg cannot promote) · Time: 4–5 hours

SSA gives every scalar value one name. Three things fall outside that promise. First, facts learned at branches: after if (x < n), the same name x is known to be less than n on one side and not on the other, but SSA gives both sides one name, so a sparse analysis cannot attach the fact to it. Second, which predicate chose a phi operand: a phi says "one of these", not "this one when p holds". Third, memory: loads and stores through pointers are not assignments to names, so mem2reg leaves them alone and optimizers have no def-use chains for them. The five forms of this lesson extend SSA to each gap. Each is built with the placement and renaming machinery of Lesson 16.2, applied to a different "variable": a branch operand, a merge predicate, the whole memory, an array, a virtual variable.

1. Problem and motivation¶

The problem. Extend SSA so that sparse analyses (which follow def-use edges instead of iterating over the CFG) can see (a) branch conditions, (b) the predicate that selects a merge operand, and (c) memory state, without losing SSA's single-definition property.

SSI and e-SSA¶

A sparse analysis attaches one fact to one name. Range analysis of x after if (x < n) needs two facts, one per branch side, so it needs two names. Ananian's static single information form splits every variable at branches with σ-functions, the mirror image of φ-functions at joins, so that each name carries one piece of path information [Ana99]. Bodík, Gupta and Sarkar's extended SSA (e-SSA) keeps only what array-bounds-check elimination needs: a π-assignment x1 = π(x) on each outgoing edge of a branch that tests x [BGS00]. LLVM's PredicateInfo builds e-SSA on demand for SCCP and NewGVN [LLVM-PredicateInfo]: the copies are bitcast instructions that carry the predicate.

Gated SSA¶

A phi x3 = φ(x1, x2) records that x3 is one of two values but not which. Ballance, Maccabe and Ottenstein's program dependence web introduced gating functions that name the predicate: x3 = γ(p, x1, x2) at a merge, μ at a loop header, η at a loop exit [BMO90]. This makes the SSA graph executable on its own (a data-flow machine can evaluate it) and lets symbolic analyses reason about path conditions. Tu and Padua gave an efficient construction [TP95]. In LLVM the closest thing is select: SimplifyCFG turns a diamond's phi into select i1 %p, %a, %b, a γ.

Memory SSA¶

After mem2reg, the remaining memory operations (through pointers, globals, calls) have no SSA names. Rather than one variable per memory location (unbounded, and aliasing makes "which location" undecidable), Memory SSA treats all of memory as one variable: every instruction that may write memory defines a new memory version, every read uses one, and φs merge versions at joins. Novillo's design for GCC [Nov07] and LLVM's MemorySSA [LLVM-MSSA, LLVM-MemorySSADoc] both do this; LLVM's documentation notes that GCC later settled on a single memory name too. Dead-store elimination, LICM and GVN-style load elimination then follow def-use chains through memory.

Array SSA¶

Whole-array SSA is imprecise: a store A[i] := v changes one element but "defines" A. Knobe and Sarkar's Array SSA makes element-level reasoning possible: each store creates a new array name and a definition φ (dφ) merges the written element with the previous array, so a later load can ask whether its element came from that store [KS98]. Fink, Knobe and Sarkar applied it to object fields in Java (one "heap array" per field, indexed by object reference) for redundant load elimination in the Jikes RVM [FKS00, Jikes-ArraySSA].

Hashed SSA¶

Chow et al.'s HSSA handles aliasing and indirect memory in a scalar-SSA optimizer: virtual variables stand for indirectly accessed locations, χ (may-def) and μ (may-use) annotations record aliasing, zero versions collapse versions no real code reads, and every expression is hash-consed into a global table so equal expressions share one node [CCL+96]. Chow et al. developed it at SGI. GCC's early tree-SSA virtual operands followed the same per-variable may-def scheme (its documentation still describes it), before the move to one .MEM name.

2. Definitions and algorithms¶

SSI and e-SSA¶

Definition 16.8.1 (π-assignment; e-SSA form)

Let block \(B\) end in a two-way branch on \(c = a \mathbin{\mathit{op}} b\) with successors \(S_T\) (taken when \(c\) holds) and \(S_F\). A π-assignment \(x' = \pi(x)\) for an operand \(x \in \{a, b\}\) on edge \((B, S)\) is a copy placed where it executes exactly when that edge is taken, annotated with the predicate \(c\) (for \(S_T\)) or \(\lnot c\) (for \(S_F\)). A program is in e-SSA form if it is in strict SSA form and every use of a branch operand \(x\) that is dominated by an edge \((B, S)\) (every path from the entry to the use passes that edge) refers to the π-name of the nearest such edge.

Definition 16.8.2 (σ-function; SSI form)

A σ-function at a block \(B\) with successors \(S_1, \dots, S_k\) is \((x^1, \dots, x^k) = \sigma(x)\): on the edge to \(S_j\) it defines \(x^j\) as a copy of \(x\). A program is in SSI form if it is in SSA form and, for every variable \(x\), σ-functions are placed at the blocks of \(\mathrm{DF}^+_{\mathrm{rev}}\) (iterated dominance frontier in the reverse CFG, i.e. the iterated post-dominance frontier) of the blocks that use \(x\) or end a predecessor of a φ for \(x\), restricted to blocks where \(x\) is live-out, and φ-functions at \(\mathrm{DF}^+\) of the blocks that define \(x\) or follow a σ for \(x\), restricted to blocks where \(x\) is live-in [Ana99]. e-SSA is the special case that places σs only at branches that test \(x\), and only on edges below which \(x\) is used.

Example (Definition 16.8.1)

In if (x < n) { if (x > 0) return x + n; else return x; } else return n;, the use x + n is dominated by the true edges of both tests, so e-SSA renames it to the π-name created on the inner edge, which is itself a π of the outer one. §3 computes the full result; LLVM's output in §7 is identical.

Algorithm 16.8.3 (e-SSA construction by π insertion and dominator-tree renaming)

Input: a function \(F\) in strict SSA form with its dominator tree.
Output: \(F\) in e-SSA form (Definition 16.8.1).
Precondition: strict SSA.
Postcondition: strict SSA; every use dominated by a π-edge reads the nearest π-name; the program computes the same values (Theorem 16.8.13).
Invariant: during Rename(B), top(stack[x]) is the π-name of \(x\) on the nearest edge that dominates \(B\) and carries a π for \(x\), or empty if there is none.

function BuildESSA(F):
    PiDefs[S] ← [] for every block S
    for each block B ending in "if c goto S_T else S_F" with c = cmp(a, b):
        for each operand x of c that is an SSA name (not a constant):
            for each (S, sense) in [(S_T, true), (S_F, false)]:
                if S has a predecessor other than B:
                    S ← SplitEdge(B, S)                       # new block on the edge
                if some use of x lies in a block dominated by S:
                    create "x_S = π(x)" at the top of S, annotated (c, sense)
                    append (x, x_S) to PiDefs[S]
    stack[x] ← [] for every name x
    Rename(entry)

function Rename(B):                                           # dominator-tree preorder
    pushed ← []
    for each (x, x_S) in PiDefs[B]:
        if stack[x] not empty: set the operand of x_S's π to top(stack[x])
        push x_S on stack[x];  append x to pushed
    for each instruction I of B after the π's, for each operand x of I:
        if stack[x] not empty: replace x by top(stack[x])
    for each successor S of B, for each phi of S, operand x coming from B:
        if stack[x] not empty: replace x by top(stack[x])
    for each child C of B in the dominator tree: Rename(C)
    for each x in pushed: pop stack[x]

A use is renamed only when the π-name is on the stack, that is, when a π-edge dominates the use. A phi operand from \(B\) is a use at the end of \(B\), so it is renamed with \(B\)'s stack. SplitEdge is only needed for critical edges; LLVM avoids it (§6).

The σ-placement of full SSI adds one fixpoint around the placements of Lesson 16.2:

Algorithm 16.8.4 (SSI placement of σ and φ for one variable)

Input: a CFG, the blocks \(\mathit{Defs}(x)\) and \(\mathit{Uses}(x)\) of a variable \(x\), live-in and live-out sets of \(x\).
Output: the φ-blocks \(\Phi\) and σ-blocks \(\Sigma\) of Definition 16.8.2.
Precondition: every block is reachable and reaches the exit (so the reverse CFG has a dominator tree rooted at the exit).
Postcondition: \(\Phi = \mathrm{DF}^+(\mathit{Defs}(x) \cup \mathrm{succ}(\Sigma)) \cap \mathit{LiveIn}(x)\) and \(\Sigma = \mathrm{DF}^+_{\mathrm{rev}}(\mathit{Uses}(x) \cup \mathrm{pred}(\Phi)) \cap \mathit{LiveOut}(x)\) (Proposition 16.8.14).
Invariant: \(\Phi\) and \(\Sigma\) only grow, and each is contained in the fixpoint.

function PlaceSSI(x):
    Φ ← ∅;  Σ ← ∅
    repeat
        Φ' ← IDF(CFG,    Defs(x) ∪ succ(Σ))  ∩ LiveIn(x)          # Algorithm 16.2.4
        Σ' ← IDF(revCFG, Uses(x) ∪ pred(Φ')) ∩ LiveOut(x)
        changed ← (Φ' ≠ Φ or Σ' ≠ Σ);  Φ ← Φ';  Σ ← Σ'
    until not changed
    return Φ, Σ

Renaming then follows Algorithm 16.2.3, with a σ acting as a definition at the start of each successor edge.

Gated SSA¶

Definition 16.8.5 (Gating functions γ, μ, η)

\(\gamma(p, v_T, v_F)\) has the value \(v_T\) if the predicate \(p\) is true and \(v_F\) otherwise. It replaces a φ at an acyclic merge; nested γs express multi-way merges.
\(\mu(v_{\mathrm{init}}, v_{\mathrm{iter}})\) at a loop header takes \(v_{\mathrm{init}}\) on entry to the loop and \(v_{\mathrm{iter}}\) on every later iteration.
\(\eta(P, v)\) at a loop exit has the value \(v\) had in the iteration in which the exit predicate \(P\) first became true.

A program is in gated SSA (GSA) form when every φ has been replaced by one of these [BMO90]. The symbol \(\bot\) inside a γ means "this side does not reach the merge".

Algorithm 16.8.6 (Gating a merge with γ trees; μ and η for a natural loop)

Input: a φ x = φ(x_1 from P_1, …, x_k from P_k) in block \(M\), \(D = \mathrm{idom}(M)\); for a loop, the header \(H\), its entry edge and back edge, and its exit edge.
Output: a gating expression for \(x\).
Preconditions: (γ) \(M\) is not a loop header, blocks have at most two successors, and every cycle that contains a block strictly dominated by \(D\) contains \(D\); (μ) \(H\) has exactly two predecessors, one entry and one back edge; (η) the loop has one exit edge \((B, X)\), \(X\) has no other predecessor, and \(B\) leaves the loop when its branch predicate \(p\) has the value \(e\).
Postcondition: evaluating the expression at \(M\) gives the operand the φ would select (Theorem 16.8.15, Proposition 16.8.16).
Invariant: G(B) is the gating expression of "the value that reaches \(M\) if control is at the start of \(B\)"; memo holds each block's expression once.

function GateMerge(M, φ):
    D ← idom(M);  memo ← {}
    return G(D)
function G(B):
    if B ∈ memo: return memo[B]
    match the terminator of B:
        "goto S":                     r ← E(B, S)
        "if p goto S_T else S_F":     r ← MakeGamma(p, E(B, S_T), E(B, S_F))
        "return …":                   r ← ⊥
    memo[B] ← r;  return r
function E(B, S):                     # value for the edge B → S
    if S = M: return x_j where P_j = B
    if S = D or D does not strictly dominate S or S cannot reach M: return ⊥
    return G(S)
function MakeGamma(p, t, f):
    if t = f or f = ⊥: return t
    if t = ⊥: return f
    return the node γ(p, t, f)        # hash-consed, so equal subtrees are shared

GateLoop(H, x = φ(x_e from entry edge, x_b from back edge)):   x ← μ(x_e, x_b)
GateExit(B → X, x used after the loop):  at the top of X, x' ← η(p = e, x); rename uses in X's dominator subtree

Dropping the predicate when one side is \(\bot\) is valid for the value at \(M\): if control reaches \(M\), it came through the non-\(\bot\) side.

Memory SSA¶

Definition 16.8.7 (Memory SSA)

Let \(\mathsf{M}\) be one variable standing for the whole memory. Every instruction that may write memory (store, call, fence, volatile or ordered access) is a MemoryDef \(\mathsf{M}_i = \mathrm{Def}(\mathsf{M}_j)\): it defines a new version and uses the previous one. Every instruction that may only read memory is a MemoryUse \(\mathrm{Use}(\mathsf{M}_j)\). At merges, MemoryPhis \(\mathsf{M}_i = \phi(\mathsf{M}_{j_1}, \dots)\) join versions. \(\mathsf{M}_0\) (LLVM: liveOnEntry) is the memory on function entry. The operand \(\mathsf{M}_j\) of an access is its defining access [LLVM-MemorySSADoc].

Algorithm 16.8.8 (Memory SSA construction)

Input: a function with its dominator tree and a classification of every instruction as may-write, may-read-only or no memory access.
Output: the accesses of Definition 16.8.7 with their defining accesses.
Precondition: the classification is conservative (every instruction that can write memory is a MemoryDef).
Postcondition: minimal SSA for \(\mathsf{M}\) (Theorem 16.8.17).
Invariant: during the walk, current is the memory version reaching the program point.

function BuildMemorySSA(F):
    DefBlocks ← { blocks containing a MemoryDef }
    for B in IDF(CFG, DefBlocks): create MemoryPhi at the top of B          # no live-in filter
    Rename(entry, M_0)
function Rename(B, current):                  # dominator-tree preorder
    if B has a MemoryPhi P: current ← P
    for each memory instruction I of B in order:
        if I is a MemoryDef: create M_new = Def(current);  current ← M_new
        else:                create Use(current)
    for each successor S with a MemoryPhi P: add incoming (B, current) to P
    for each dominator-tree child C of B: Rename(C, current)

LLVM's MemorySSA::placePHINodes passes the defining blocks to a ForwardIDFCalculator without live-in blocks [LLVM-MSSA]: its MemoryPhis are minimal, not pruned (compare mem2reg in Lesson 16.4, which prunes).

Array SSA¶

Definition 16.8.9 (Array SSA: definition φ, control φ, timestamps)

Each array variable \(A\) is renamed so that every store and every merge defines a new array name. A store A[k] := v becomes two definitions: \(A_j := [k \mapsto v]\) (a partial array, defined only at index \(k\)) followed by the definition φ \(A_{j'} := d\phi(A_j, A_{\mathrm{prev}})\), where \(A_{\mathrm{prev}}\) is the array name reaching the store. With a timestamp array \(@A\) recording when each element was last written,

\[ d\phi(A_j, A_{\mathrm{prev}})[i] = \begin{cases} A_j[i] & \text{if } @A_j[i] \ge @A_{\mathrm{prev}}[i],\\ A_{\mathrm{prev}}[i] & \text{otherwise.} \end{cases} \]

At a join, a control φ \(A_m := \phi(A_{i_1}, \dots)\) selects the array of the incoming edge, as a scalar φ does. (Knobe and Sarkar also give control φs a timestamp-based element-wise definition, so that the analysis can reason per element [KS98].) A heap array \(H_f\) for a field \(f\) is an array indexed by object reference: p.f := v is H_f[p] := v [FKS00].

Algorithm 16.8.10 (Array SSA construction)

Input: a function whose array (or field) accesses are A[k] := v and x := A[k].
Output: the function in Array SSA form.
Precondition: array names do not alias (each array or field is its own variable).
Postcondition: every load reads the array name that holds the current array (Theorem 16.8.18).
Invariant: as in Algorithm 16.2.3, top(stack[A]) names the current array.

function BuildArraySSA(F):
    for each array A:
        Defs(A) ← blocks containing a store to A
        place control φs for A at IDF(CFG, Defs(A)) (∩ LiveIn(A) for the pruned flavor)
    Rename with Algorithm 16.2.3, where a store "A[k] := v" is rewritten as
        A_j := [k ↦ v];  A_j' := dφ(A_j, top(stack[A]));  push A_j'
    and a load "x := A[k]" as "x := top(stack[A])[k]"

Hashed SSA¶

Definition 16.8.11 (Virtual variables, μ and χ, zero versions, hashed expressions)

A virtual variable \(v^*\) stands for the locations accessed through an indirect reference such as *p [CCL+96].
At an instruction that may define a variable \(a\) (a store through a pointer that may point to \(a\), a call), a χ-assignment \(a_{j} = \chi(a_{i})\) defines a new version that is either the old value or the stored one. At an instruction that may use \(a\), \(\mu(a_i)\) marks a use.
A version is a zero version if it has no real (non-μ, non-χ) occurrence and its value comes from at least one χ, possibly through φs. All zero versions of a variable are given the version number 0 and their definitions are not tracked.
Hashed form: every expression tree (constants, variable versions, operators) is entered bottom-up into one hash table, so structurally identical expressions share one node.

Algorithm 16.8.12 (HSSA construction, after Chow et al.)

Input: a function, alias information (a may-point-to set per indirect reference and a may-mod/may-ref set per call).
Output: HSSA: SSA over real and virtual variables with μ/χ, zero versions and a hash table of expression nodes.
Precondition: alias information is conservative.
Postcondition: every real occurrence has an exact SSA version; equal node ⇒ equal value (Theorem 16.8.19).
Invariant: the hash table contains exactly one node per distinct (operator, operand nodes) combination seen so far.

function BuildHSSA(F):
    1. assign a virtual variable to each class of indirect references
    2. at each may-def insert χ for every variable (real or virtual) it may define;
       at each may-use insert μ for every variable it may use
    3. place φs for every variable (χ counts as a definition) and rename (Algorithms 16.2.1, 16.2.3)
    4. mark zero versions: versions with no real occurrence whose value comes from a χ
       (through φs); renumber them 0
    5. walk the dominator tree in preorder; for each expression, bottom-up:
           node ← Hash(operator, node(operand_1), …, node(operand_k))   # insert if absent

3. Worked example¶

SSI and e-SSA¶

The nested example of Definition 16.8.1 in TAC:

entry: c1 = lt x, n ; if c1 goto A ; goto R
A:     c2 = gt x, 0 ; if c2 goto B ; goto R2
B:     y = add x, n ; return y
R:     return n
R2:    return x

Every successor has one predecessor, so no edge is split. Algorithm 16.8.3's insertion loop:

branch	operand	edge	uses of the operand dominated by the edge's target	π inserted
entry (`c1 = lt x, n`)	x	entry → A	A (`c2`), B (`y`), R2	`x1 = π(x)` [c1]
entry	n	entry → A	B (`y`)	`n1 = π(n)` [c1]
entry	x	entry → R	none	—
entry	n	entry → R	R	`n2 = π(n)` [¬c1]
A (`c2 = gt x, 0`)	x	A → B	B	`x2 = π(x)` [c2]
A	x	A → R2	R2	`x3 = π(x)` [¬c2]

Renaming in dominator-tree preorder (entry, A, B, R2, R):

block	stack[x] after the π's	stack[n]	rewrites
entry	—	—	none
A	x1	n1	`c2 = gt x1, 0`
B	x1, x2 (π operand set to x1)	n1	`y = add x2, n1`
R2	x1, x3 (π operand set to x1)	n1	`return x3`
R	—	n2	`return n2`

Five π-assignments; x2 and x3 are copies of x1, carrying \(x < n \land x > 0\) and \(x < n \land x \le 0\) along their chain. The x operand on edge entry → R gets no π because nothing below R uses x: this is the liveness pruning LLVM also applies.

Gated SSA¶

γ. Take a φ at \(M\) with three incoming edges: \(D\) branches on \(p\) to \(T\) and \(F\); \(T\) branches on \(q\) to \(T_1\) and \(T_2\); \(T_1\), \(T_2\), \(F\) jump to \(M\) with \(x_1\), \(x_2\), \(x_3\). Then \(G(T_1) = x_1\), \(G(T_2) = x_2\), \(G(F) = x_3\), \(G(T) = \gamma(q, x_1, x_2)\) and

\[ x = G(D) = \gamma\bigl(p,\ \gamma(q, x_1, x_2),\ x_3\bigr). \]

If \(F\) returned instead of jumping to \(M\), then \(\mathrm{idom}(M) = T\) and the result is \(\gamma(q, x_1, x_2)\); and if \(T_2\) returned, \(E(T, T_2) = \bot\) and \(G(D) = \gamma(p, x_1, x_3)\): \(q\) disappears, because reaching \(M\) through \(T\) implies \(q\) held.

μ and η. The summation loop

entry: s0 = 0 ; i0 = 0 ; goto H
H:     s1 = φ(s0, s2) ; i1 = φ(i0, i2) ; c = lt i1, n ; if c goto L ; goto X
L:     s2 = add s1, i1 ; i2 = add i1, 1 ; goto H
X:     return s1

becomes s1 = μ(s0, s2), i1 = μ(i0, i2), and at the exit s3 = η(¬c, s1), return s3. For \(n = 4\) the μ for s1 takes the values 0, 0, 1, 3, 6 in successive iterations; \(\lnot c\) first holds in the fifth evaluation of the header, so \(\eta\) yields 6.

Memory SSA¶

For the function of §7's box,

entry: store 1 → *p        ; M1 = Def(M0)
       if n > 0 goto then ; goto join
then:  store n → g        ; M2 = Def(M1)
       call work(p)       ; M3 = Def(M2)
join:  M4 = φ(M1 from entry, M3 from then)
       load *p            ; Use(M4)
       load g             ; Use(M4)

\(\mathit{DefBlocks} = \{\mathit{entry}, \mathit{then}\}\), \(\mathrm{DF}(\mathit{then}) = \{\mathit{join}\}\), \(\mathrm{DF}(\mathit{entry}) = \emptyset\), so there is one MemoryPhi, at join. The def chain is \(M3 \to M2 \to M1 \to M0\). Both loads use \(M4\): the call work(p) may write *p and g, so neither load can skip past it.

Array SSA¶

A1 := [i ↦ 1] ;  A2 := dφ(A1, A0)          # A[i] := 1
if t goto S ; goto J
S: A3 := [j ↦ 2] ;  A4 := dφ(A3, A2)       # A[j] := 2
J: A5 := φ(A2, A4)
   x := A5[i]

If the branch is not taken, \(x = A_2[i] = 1\). If it is, \(x = A_4[i]\), which is \(2\) when \(j = i\) (the dφ picks the later timestamp) and \(A_2[i] = 1\) otherwise. So x := A[i] can be replaced by 1 exactly when \(i \neq j\) is known: the element-level question a redundant-load eliminator asks, and the one whole-array SSA (\(A_5\) "some array") cannot answer.

Hashed SSA¶

With int a, b, *p and \(p\) possibly pointing to \(a\):

a1 = 1
*p = 2          # χ: a2 = χ(a1);  virtual variable: v1 = χ(v0)
x  = a2 + b1    # node N1 = Hash(+, a2, b1)
y  = a2 + b1    # same operator, same operand nodes: N1 again

The store kills the constant: x reads \(a_2\), not \(a_1\). The two additions hash to one node \(N_1\), so y is recognized as a copy of x with no separate value-numbering pass. If the program stored through p in a loop and never read a there, the χ-defined versions of a in the loop would be zero versions: tracked as \(a_0\), with no use-def edges to maintain.

4. Invariants and correctness¶

SSI and e-SSA¶

Theorem 16.8.13 (e-SSA is strict SSA, preserves behavior, and renamed uses see their predicate)

After Algorithm 16.8.3: (i) the program is in strict SSA form and computes the same values; (ii) if a use \(u\) reads the π-name \(x_S\) created on edge \((B, S)\) with predicate \(c\) (or \(\lnot c\)), then whenever \(u\) executes, \(c\) (or \(\lnot c\)), evaluated on the current values of its operands, holds.

Proof

(i) A π is a copy, so values are unchanged if each renamed use reads a name holding the value of \(x\). By the invariant, a use in \(B'\) is renamed to \(x_S\) only when \(S\) dominates \(B'\), and the π for \(x_S\) sits at the top of \(S\), so its definition dominates the use. The π's own operand is the π-name of the nearest dominating π-edge, or \(x\), whose definition dominates \(B\) and hence \(S\). So the program is strict. The invariant holds because pushes happen on entering \(S\) and pops on leaving its dominator subtree.

(ii) Let \(u\) execute. \(S\) dominates \(u\)'s block, so the execution passed \(S\). Take its last visit to \(S\) before \(u\). \(S\)'s only predecessor is \(B\), so the edge \((B, S)\) was just taken, and \(c\) had that edge's truth value on the operands' values at that moment.

Suppose an operand \(a\) of \(c\) were redefined between that visit and \(u\). First, \(S\) does not dominate \(\mathrm{def}(a)\). If it did, then since \(\mathrm{def}(a)\) dominates \(B\) (the use in \(c\) is in \(B\)), \(S\) would dominate \(B\). But every path to \(S\) passes \(B\) first, so no path could reach either one, and \(B\) would be unreachable.

So some path from the entry reaches \(\mathrm{def}(a)\) without passing \(S\). Continuing it along the execution from \(\mathrm{def}(a)\) to \(u\), which does not revisit \(S\), gives an entry-to-\(u\) path that avoids \(S\). That contradicts the dominance of \(S\) over \(u\). Hence the operands still have the values under which \(c\) was evaluated.

Proposition 16.8.14 (SSI placement terminates in at most \(2\lvert N \rvert + 1\) rounds)

Algorithm 16.8.4 terminates, and its result satisfies the postcondition's two equations. With the linear-time IDF of Algorithm 16.2.4, it costs \(O((\lvert N \rvert + \lvert E \rvert) \cdot \lvert N \rvert)\) per variable in the worst case.

Proof

\(\mathrm{DF}^+\) is monotone in its argument and the liveness filters are fixed, so if \(\Phi\) and \(\Sigma\) grow, the next \(\Phi'\) and \(\Sigma'\) contain them: by induction both sequences are increasing. They are subsets of \(N\), so the pair can strictly grow at most \(2\lvert N \rvert\) times; the loop stops one round after the last growth, and at that point \(\Phi' = \Phi\) and \(\Sigma' = \Sigma\), which are the two equations. Each round costs two IDF computations, \(O(\lvert N \rvert + \lvert E \rvert)\) each (Theorem 16.2.7).

Gated SSA¶

Theorem 16.8.15 (γ trees select the φ operand)

Under the γ preconditions of Algorithm 16.8.6, GateMerge terminates, and for every execution that enters \(M\) through edge \((P_j, M)\), evaluating \(G(D)\) at \(M\) with the current values of its predicates gives \(x_j\).

Proof

Termination. G recurses along edges into blocks strictly dominated by \(D\) other than \(M\) (E stops at \(M\), at \(D\) and at blocks \(D\) does not strictly dominate). A recursion that revisited a block would trace a cycle of blocks strictly dominated by \(D\) that avoids \(D\), which the precondition excludes. Memoization makes each block's expression computed once.

The segment. Take the part of the execution from the last visit to \(D\) before this entry into \(M\), up to that entry: \(D = B_0, B_1, \dots, B_m = P_j\), then \(M\). Every \(B_i\) (\(i \ge 1\)) is strictly dominated by \(D\): otherwise some entry path reaches \(B_i\) without \(D\), and continuing along the segment reaches \(M\) without \(D\), contradicting \(D = \mathrm{idom}(M)\). No block repeats, since a repetition would be a cycle of strictly dominated blocks avoiding \(D\). Every \(B_i\) reaches \(M\), so no edge of the segment is mapped to \(\bot\).

Induction from the end. We claim that \(G(B_i)\) evaluates to \(x_j\) for \(i = m, \dots, 0\). If \(B_i\) ends in goto, \(G(B_i) = E(B_i, B_{i+1})\), which is \(x_j\) for \(i = m\) and \(G(B_{i+1})\) otherwise. If \(B_i\) branches on \(p\), the branch took the edge to \(B_{i+1}\) (or \(M\)), and \(G(B_i)\) is a γ on \(p\) (or a simplification of one) whose side for that edge is \(E(B_i, B_{i+1})\). The value of \(p\) at \(M\) is its value at the branch: its definition dominates \(B_i\) and, as in Theorem 16.8.13, a re-execution between \(B_i\) and \(M\) would give an entry path to \(B_i\) avoiding it. So the γ selects the segment's side. The simplifications are sound: if both sides are equal the choice does not matter, and a \(\bot\) side is never the one on the segment.

Proposition 16.8.16 (μ and η give the loop values)

Under the μ and η preconditions, \(\mu(x_e, x_b)\) at \(H\) equals the φ it replaces, and \(\eta(p = e, x)\) at \(X\) equals the value \(x\) had in the iteration that took the exit edge.

Proof

The φ at \(H\) selects \(x_e\) when \(H\) is entered by the entry edge and \(x_b\) by the back edge. The entry edge is taken exactly once per entry into the loop, before any back edge, which is μ's definition. \(X\)'s only predecessor is \(B\), and the only way out of the loop is \((B, X)\), taken in the first iteration whose evaluation of \(p\) gives \(e\). At that moment \(x\) holds its value of that iteration, which is η's definition.

Memory SSA¶

Theorem 16.8.17 (Memory SSA is minimal SSA for one memory variable)

Treat every MemoryDef as the assignment \(\mathsf{M} \gets f(\mathsf{M})\) and every MemoryUse as a read of \(\mathsf{M}\). Then (i) Algorithm 16.8.8 produces Cytron's minimal SSA for \(\mathsf{M}\), so every access's defining access is the most recent MemoryDef or MemoryPhi on every path to it; (ii) following defining accesses from any access reaches \(\mathsf{M}_0\), and the MemoryDefs form a single chain.

Proof

(i) Placement at \(\mathrm{IDF}(\mathit{DefBlocks})\) is Algorithm 16.1.9's minimal placement for the one variable \(\mathsf{M}\), and Rename is Algorithm 16.2.3 specialized to one stack (current is the top). Theorem 16.2.6 gives the reaching-definition property.

(ii) A MemoryDef's or MemoryUse's defining access is either earlier in the same block, or the MemoryPhi or last MemoryDef of a strictly dominating block. So from any Def or Use, each step to a defining access that is a MemoryDef strictly decreases the pair (dominator-tree depth of the block, position in the block). The walk therefore ends at a MemoryPhi or at \(\mathsf{M}_0\).

Every MemoryDef has exactly one defining access, so the Defs form chains linked only through MemoryPhis. This is the "single Def chain" of LLVM's documentation [LLVM-MemorySSADoc].

The chain says only that a store may clobber the location; to find the access that actually clobbers a load, LLVM's ClobberWalker walks the chain, asking alias analysis at each step (§6).

Array SSA¶

Theorem 16.8.18 (Definition φs compute the array after a store)

Let A[k] := v execute at time \(t\), strictly later than every earlier write, and let \(A_{\mathrm{prev}}\) be the array reaching it. Then \(d\phi(A_j, A_{\mathrm{prev}})\) with \(A_j = [k \mapsto v]\), \(@A_j[k] = t\) and \(@A_j[i] = -\infty\) for \(i \neq k\), equals \(A_{\mathrm{prev}}\) with element \(k\) replaced by \(v\). Consequently, with control φs selecting the incoming array, every array name holds the array the original program holds at that point.

Proof

For \(i = k\): \(@A_j[k] = t > @A_{\mathrm{prev}}[k]\), so the dφ takes \(A_j[k] = v\). For \(i \neq k\): \(@A_j[i] = -\infty < @A_{\mathrm{prev}}[i]\) (an element never written has timestamp \(-\infty\) in both, and then either choice is the initial value), so it takes \(A_{\mathrm{prev}}[i]\). That is the store's semantics on the whole array. The second part is Theorem 16.2.6 applied to the variable \(A\), where each store is the assignment \(A \gets d\phi([k \mapsto v], A)\) and control φs are ordinary φs.

Hashed SSA¶

Theorem 16.8.19 (Hashed nodes denote equal values; χ keeps use-def chains conservative)

(i) Two expression occurrences mapped to the same node compute the same function of the current instances of the same SSA versions, so they are equal whenever both read the same instances. (ii) If alias information is conservative, the version a real occurrence reads is defined by the last instruction that may have written that location, on every path.

Proof

(i) By induction on the height of the node. Leaves are constants or SSA versions. A version names one value per execution of its definition. An inner node has one operator and the same child nodes for every occurrence, so by induction the same operand values, hence the same result.

(ii) With χ counted as a definition, step 3 is Cytron's construction for each variable, and Theorem 16.2.6 says that every use reads the version of the most recent definition. Every instruction that may write \(a\) has a χ for \(a\) by step 2. So no write to \(a\) happens between the reported definition and the use without being that definition. Zero versioning renames only versions with no real occurrence, so the real occurrences' versions are untouched.

5. Complexity¶

\(n = \lvert N \rvert\), \(m = \lvert E \rvert\) (blocks, edges), \(b\) = conditional branches, \(u\) = uses of branch operands, \(a\) = memory accesses, \(s\) = stores, \(V\) = variables (real and virtual), \(\lvert R \rvert\) = size of a merge region.

Technique	Time	Space	Notes
e-SSA (Algorithm 16.8.3)	\(O(n + m + u \log u)\) as LLVM does it (sorts uses by dominator-tree DFS number); \(O(b \cdot n)\) for the naive "some use dominated" tests	\(\le 4b\) π's (2 operands × 2 edges)	LLVM inserts only live π's
SSI (Algorithm 16.8.4)	\(O(n (n + m))\) per variable worst case (Proposition 16.8.14); usually two or three rounds	\(O(n)\) σ and φ per variable	the reverse CFG needs a unique exit
Gated SSA (Algorithm 16.8.6)	\(O(\lvert R \rvert)\) per merge with memoization; \(\Omega(2^{k})\) without it on a region of \(3k+2\) blocks (Proposition 16.8.20)	\(O(\lvert R \rvert)\) γ nodes per merge	[TP95] gives an almost-linear-time construction for general reducible CFGs
Memory SSA (Algorithm 16.8.8)	\(O(n + m + a)\) with a linear IDF	\(O(a + n)\)	clobber queries cost extra: LLVM caps each walk at 100 steps (`memssa-check-limit`)
Array SSA (Algorithm 16.8.10)	Cytron per array: \(O(n + m + s)\) with a linear IDF	two names per store	timestamps are analysis-time only
HSSA (Algorithm 16.8.12)	\(O(V (n + m) + \#\chi + \#\mu)\)	\(\#\chi\) can be \(s \cdot V\) (Proposition 16.8.21)	virtual variables and zero versions bound it in practice

Proposition 16.8.20 (Gating without sharing is exponential)

For \(i = 1, \dots, k\) let \(B_i\) branch on \(p_i\) to \(L_i\) and \(R_i\); \(L_i\) branch on \(q_i\) to \(B_{i+1}\) and to \(M\) (bringing \(x_i\)); \(R_i\) jump to \(B_{i+1}\); and \(B_{k+1}\) jump to \(M\) (bringing \(x_0\)). Then \(\mathrm{idom}(M) = B_1\). Expanding G without memo makes at least \(2^k\) calls and yields a γ tree with at least \(2^k\) leaves. Algorithm 16.8.6 makes \(O(k)\) calls and builds \(O(k)\) shared nodes.

Proof

Let \(T(i)\) be the number of calls made to expand \(G(B_i)\) without memoization. Then \(T(k+1) = 1\), and \(T(i) \ge 2\,T(i+1)\), because \(B_{i+1}\) is expanded once below \(L_i\) and once below \(R_i\). So \(T(1) \ge 2^k\).

The expression is \(G(B_i) = \gamma(p_i, \gamma(q_i, G(B_{i+1}), x_i), G(B_{i+1}))\). Its two sides differ, since only one of them contains \(x_i\), so MakeGamma does not fold it. As a tree, it contains two copies of \(G(B_{i+1})\), which gives at least \(2^k\) leaves.

With memo, each of the \(3k + 1\) blocks is expanded once, and hash-consing stores each \(G(B_i)\) once: \(2k\) γ nodes.

Proposition 16.8.21 (χ-assignments can be quadratic)

A function with \(s\) stores through pointers that may each point to any of \(V\) address-taken variables has \(s \cdot V\) χ-assignments in HSSA before zero versioning.

Proof

Step 2 inserts one χ per (may-def, variable) pair, and every pair qualifies.

Justification of the table. e-SSA inserts at most one π per (operand, edge) and renames each use once; LLVM's renamer sorts the uses and π's of each operand by DFS number and sweeps with a stack, hence the \(u \log u\) term. Memory SSA is one-variable Cytron: one IDF call and one dominator-tree walk. Array SSA is Cytron per array. HSSA's φ placement runs once per variable.

SSI and e-SSA¶

LLVM places the copy before the branch (not at the top of the successor) and renames only uses dominated by the edge, so no critical edge is split; the predicate is attached through a side table keyed by the copy [LLVM-PredicateInfo] — trade-off: no CFG change, but a copy in \(B\) is "valid" only in the dominated region, which every client must respect. (The file-header comment of PredicateInfo.h still shows the copy in the successor.)
Assumes as predicates: PredicateInfo also renames after llvm.assume(c) — trade-off: extra copies for facts that hold after the assume point.
Full SSI with σ at every branch — trade-off: more names; supports backward analyses (liveness, "value used on this side") as well as forward ones [Ana99].

Gated SSA¶

Thinned gates (drop predicates that do not affect the value, as MakeGamma does with \(\bot\)) — trade-off: smaller graphs, but the form is no longer directly executable for paths that do not reach the merge.
Gating by path expressions [TP95] handles arbitrary reducible CFGs with nested loops between \(D\) and \(M\) — trade-off: more complex construction.
select in LLVM: SimplifyCFG and if-conversion produce γs only for cheap, speculatable diamonds — trade-off: both operands are computed.

Memory SSA¶

Optimized uses: LLVM's MemorySSA repoints each MemoryUse at its nearest clobber, found by the walker with the step cap. It does this lazily, in MemorySSA::ensureOptimizedUses, the first time a client asks for the walker [LLVM-MSSA] — trade-off: precise use-def chains, paid for only by clients that need them.
Memory partitions (Novillo's paper, one memory variable per alias class) — trade-off: more precise chains, more φs; both GCC and LLVM now use one memory variable.
Incremental update (MemorySSAUpdater, the Memory SSA analogue of SSAUpdater in Lesson 16.4) — trade-off: passes must keep it up to date.

Array SSA¶

Heap arrays for fields [FKS00] — trade-off: no alias analysis needed between different fields (different arrays), but two references to one field must be proved distinct to optimize.
Scalar replacement of array elements after Array SSA shows a load redundant — trade-off: register pressure.

Hashed SSA¶

One virtual variable per indirect-reference class instead of one per location — trade-off: fewer χs, less precision.
A single memory variable (Memory SSA) is the extreme case with one virtual variable for all memory — trade-off: simplest, and precision comes back through alias queries on demand.

7. In real compilers¶

SSI and e-SSA¶

LLVM PredicateInfo: five π-copies for the nested branches

Reproduce (opt 23.1.2):

cat > nested.ll <<'EOF'
define i32 @nested(i32 %x, i32 %n) {
entry:
  %c1 = icmp slt i32 %x, %n
  br i1 %c1, label %A, label %R
A:
  %c2 = icmp sgt i32 %x, 0
  br i1 %c2, label %B, label %R2
B:
  %y = add i32 %x, %n
  ret i32 %y
R:
  ret i32 %n
R2:
  ret i32 %x
}
EOF
opt -disable-output -passes='print<predicate-info>' nested.ll 2>&1

Output (complete):

PredicateInfo for function: nested
define i32 @nested(i32 %x, i32 %n) {
entry:
  %c1 = icmp slt i32 %x, %n
; branch predicate info { TrueEdge: 1 Comparison:  %c1 = icmp slt i32 %x, %n Edge: [label %entry,label %A], RenamedOp: %x }
  %x.0 = bitcast i32 %x to i32
; branch predicate info { TrueEdge: 1 Comparison:  %c1 = icmp slt i32 %x, %n Edge: [label %entry,label %A], RenamedOp: %n }
  %n.0 = bitcast i32 %n to i32
; branch predicate info { TrueEdge: 0 Comparison:  %c1 = icmp slt i32 %x, %n Edge: [label %entry,label %R], RenamedOp: %n }
  %n.1 = bitcast i32 %n to i32
  br i1 %c1, label %A, label %R

A:                                                ; preds = %entry
  %c2 = icmp sgt i32 %x.0, 0
; branch predicate info { TrueEdge: 1 Comparison:  %c2 = icmp sgt i32 %x.0, 0 Edge: [label %A,label %B], RenamedOp: %x.0 }
  %x.0.1 = bitcast i32 %x.0 to i32
; branch predicate info { TrueEdge: 0 Comparison:  %c2 = icmp sgt i32 %x.0, 0 Edge: [label %A,label %R2], RenamedOp: %x.0 }
  %x.0.2 = bitcast i32 %x.0 to i32
  br i1 %c2, label %B, label %R2

B:                                                ; preds = %A
  %y = add i32 %x.0.1, %n.0
  ret i32 %y

R:                                                ; preds = %entry
  ret i32 %n.1

R2:                                               ; preds = %A
  ret i32 %x.0.2
}

What to notice: exactly the five π's of §3 (%x.0 = x1, %n.0 = n1, %n.1 = n2, %x.0.1 = x2, %x.0.2 = x3), with the inner ones copying %x.0, as the renaming stack predicts. There is no %x copy on the edge to R, where %x is unused. The copies sit before the branch, and the Edge: field says which edge's dominated region they are valid in (§6).

Gated SSA¶

SimplifyCFG turns a diamond's φ into a γ (select)

Reproduce (opt 23.1.2):

cat > gate.ll <<'EOF'
define i32 @gate(i1 %c, i32 %x, i32 %y) {
entry:
  br i1 %c, label %then, label %else
then:
  %a = add i32 %x, 1
  br label %join
else:
  %b = mul i32 %y, 3
  br label %join
join:
  %p = phi i32 [ %a, %then ], [ %b, %else ]
  ret i32 %p
}
EOF
opt -S -passes=simplifycfg gate.ll

Output (complete):

; ModuleID = 'gate.ll'
source_filename = "gate.ll"

define i32 @gate(i1 %c, i32 %x, i32 %y) {
entry:
  %a = add i32 %x, 1
  %b = mul i32 %y, 3
  %p = select i1 %c, i32 %a, i32 %b
  ret i32 %p
}

What to notice: GateMerge on this φ gives \(G(\mathit{entry}) = \gamma(c, a, b)\), and that is the select. LLVM only does this when both sides are cheap and safe to execute unconditionally (it hoisted %a and %b into entry); GSA keeps the γ without speculating.

Memory SSA¶

LLVM MemorySSA: three MemoryDefs, one MemoryPhi at the IDF

Reproduce (clang 23.1.2, opt 23.1.2):

cat > mssa.c <<'EOF'
int g;
void work(int *);
int mem(int *p, int n) {
  *p = 1;
  if (n > 0) {
    g = n;
    work(p);
  }
  return *p + g;
}
EOF
clang-23 -O1 -S -emit-llvm mssa.c -o mssa.ll
opt -disable-output -passes='print<memoryssa>' mssa.ll 2>&1 | sed -n '/^define/,/^}/p'

Output (complete):

define dso_local i32 @mem(ptr noundef initializes((0, 4)) %0, i32 noundef %1) local_unnamed_addr #0 {
; 1 = MemoryDef(liveOnEntry)
  store i32 1, ptr %0, align 4, !tbaa !9
  %3 = icmp sgt i32 %1, 0
  br i1 %3, label %4, label %5

4:                                                ; preds = %2
; 2 = MemoryDef(1)
  store i32 %1, ptr @g, align 4, !tbaa !9
; 3 = MemoryDef(2)
  tail call void @work(ptr noundef nonnull %0) #2
  br label %5

5:                                                ; preds = %4, %2
; 4 = MemoryPhi({%2,1},{%4,3})
; MemoryUse(4)
  %6 = load i32, ptr %0, align 4, !tbaa !9
; MemoryUse(4)
  %7 = load i32, ptr @g, align 4, !tbaa !9
  %8 = add nsw i32 %7, %6
  ret i32 %8
}

What to notice: §3's worked example exactly: the call is a MemoryDef, and the MemoryPhi is in the one block of \(\mathrm{DF}^+(\{\%2, \%4\})\). print<memoryssa> optimizes uses first (unless given <no-ensure-optimized-uses>), so each MemoryUse already names its nearest clobber. Both loads still name the phi: on the path through %4 the call may write both locations, and on the other path *p's clobber is access 1, so the paths disagree and the walk stops at the phi.

GCC's virtual operands are the same Memory SSA

Reproduce (gcc-14 14.2.0, Ubuntu 24.04; mssa.c from the previous box):

gcc-14 -O1 -c -fdump-tree-ssa-vops mssa.c -o /dev/null
cat mssa.c.022t.ssa

Output (complete):

;; Function mem (mem, funcdef_no=0, decl_uid=2773, cgraph_uid=1, symbol_order=1)

int mem (int * p, int n)
{
  int _1;
  int g.0_2;
  int _10;

  <bb 2> :
  # .MEM_6 = VDEF <.MEM_4(D)>
  *p_5(D) = 1;
  if (n_7(D) > 0)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  # .MEM_8 = VDEF <.MEM_6>
  g = n_7(D);
  # .MEM_9 = VDEF <.MEM_8>
  work (p_5(D));

  <bb 4> :
  # .MEM_3 = PHI <.MEM_6(2), .MEM_9(3)>
  # VUSE <.MEM_3>
  _1 = *p_5(D);
  # VUSE <.MEM_3>
  g.0_2 = g;
  _10 = _1 + g.0_2;
  # VUSE <.MEM_3>
  return _10;

}

What to notice: .MEM is GCC's single memory variable: VDEF = MemoryDef, VUSE = MemoryUse, and .MEM_3 = PHI = the MemoryPhi, in the same block as LLVM's. .MEM_4(D) is the default definition, LLVM's liveOnEntry. GCC also gives the return a VUSE (the caller may observe memory), which LLVM leaves implicit.

Array SSA¶

Jikes RVM: a putfield uses and defines the field's heap array

Reproduce (curl 8.x; Jikes RVM source at tag 3.1.4, printed unmodified):

curl -sS https://raw.githubusercontent.com/JikesRVM/JikesRVM/3.1.4/rvm/src/org/jikesrvm/compilers/opt/ssa/SSADictionary.java \
  | sed -n '/private void putFieldHelper/,/^  }/p'

Output (complete):

  private void putFieldHelper(Instruction s, BasicBlock b) {
    LocationOperand locOp = PutField.getLocation(s);
    FieldReference field = locOp.getFieldRef();
    registerUse(s, field);
    registerDef(s, b, field);
  }

What to notice: the store p.f = v both uses and defines the heap variable of field f: it is Definition 16.8.9's \(H_f[p] := v\), i.e. \(H_{f,j'} = d\phi([p \mapsto v], H_{f,\mathrm{prev}})\), which reads the previous heap array. The same file's header comment says that all Heap Array SSA information lives in this side structure, not in the scalar IR, and points to the SAS 2000 paper [FKS00, Jikes-ArraySSA].

Hashed SSA¶

GCC documents per-variable may-definitions (χ) in its virtual operands

Reproduce (curl 8.x; GCC source at tag releases/gcc-14.2.0, quoted from the documentation, not run):

curl -sS https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-14.2.0/gcc/doc/tree-ssa.texi \
  | sed -n '/^  # a = VDEF <a>/,/^@end smallexample/p'

Output (complete):

  # a = VDEF <a>
  # b = VDEF <b>
  *p = 5;

  # VUSE <a>
  # VUSE <b>
  return *p;
@}
@end smallexample

What to notice: the store through p, which may point to a or b, gets one may-definition per variable: a = VDEF <a> is HSSA's \(a_j = \chi(a_i)\), and the VUSEs are μs. The manual's next paragraph explains that the second copy of the variable marks a non-killing definition. GCC 14's actual dump (the Memory SSA box above) no longer has per-variable operands; it uses the single .MEM. The quadratic count of per-variable operands (Proposition 16.8.21) is the cost that a single memory variable avoids. LLVM's MemorySSA documentation notes that GCC eventually swapped to just one [LLVM-MemorySSADoc].

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
SSI / e-SSA	one name per (value, path fact): sparse range and predicate analyses	\(O(n + m + u \log u)\) · cheap, built on demand	at most 4 copies per branch, only where live	~900 lines (LLVM `PredicateInfo.cpp`)	LLVM SCCP, IPSCCP and NewGVN; ABCD bounds-check elimination [BGS00]
Gated SSA	φs become executable γ/μ/η with explicit predicates	\(O(\lvert R \rvert)\) per merge with sharing · exponential without	exact gates for structured code; thinned gates otherwise	~200 lines structured, more with path expressions	symbolic and dependence analysis; `select` after if-conversion
Memory SSA	def-use chains for all memory, one version stream	linear construction · clobber walks capped	minimal MemoryPhis; uses optimized lazily	~2,700 lines (`MemorySSA.cpp`, with the walker) plus the updater	LLVM LICM, DSE, EarlyCSE, NewGVN; GCC's `.MEM` web
Array SSA	element-level def-use through dφ and timestamps	Cytron per array · fast	exact for known indices; needs index analysis otherwise	~1,600 lines (Jikes `SSADictionary.java`, heap arrays)	redundant load elimination, parallelization of array code
Hashed SSA	per-variable μ/χ precision plus global hash-consing	\(O(\#\chi)\) can be \(s \cdot V\) · zero versions keep it small	exact versions for real occurrences	large: alias classes, virtual variables, hashing	SGI's optimizer [CCL+96]; the per-variable virtual operands GCC's manual describes

Choose e-SSA when an analysis needs different facts on the two sides of a branch (ranges, constants, equalities): it is cheap and LLVM gives it to you. Choose gated SSA when you need the predicate of a merge (symbolic evaluation, dependence testing), not just its operands. Choose Memory SSA for any memory optimization in a modern compiler; it is the default in both LLVM and GCC. Choose Array SSA when array or field elements must be tracked individually (load elimination in Java-like languages, loop parallelization). HSSA is the historical design that led to Memory SSA; its hash-consing idea lives on in GVN (Ch 17).

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch16.yaml`)	Drill	Flashcard tag	Exercises
SSI / e-SSA	`essa-pi-count`, `essa-renamed-uses`, `llvm-where-predicateinfo`	`./course drill idf` on the reverse CFG (σ placement is IDF placement there)	`ssi`	—
Gated SSA	`gsa-gamma-tree`, `gsa-eta-value`	none (see below)	`gated-ssa`	—
Memory SSA	`mssa-phi-blocks`, `mssa-def-chain`, `llvm-where-mssa-phis`	`./course drill phi-placement` (treat every store as a definition of one variable `M`)	`memory-ssa`	—
Array SSA	`array-ssa-load`, `array-ssa-heap`	`./course drill phi-placement` (control φs of one array)	`array-ssa`	—
Hashed SSA	`hssa-chi-count`, `hssa-zero-version`	`./course drill ssa-renaming` (χ is a definition that reads the old version)	`hashed-ssa`	—

Find where LLVM does it.

Open llvm/lib/Transforms/Utils/PredicateInfo.cpp (LLVM 23.1.2) and find CreateSSACopy. Which LLVM instruction does it create as the π-copy? (Quiz llvm-where-predicateinfo.)
Open llvm/lib/Analysis/MemorySSA.cpp and read MemorySSA::placePHINodes. Which class computes the MemoryPhi blocks, and does it get live-in blocks? (Quiz llvm-where-mssa-phis.)

No gating drill: a γ tree follows directly from the branch structure of a single region, and the quiz questions gsa-gamma-tree and gsa-eta-value already make you compute one. A generator would only produce more instances of the same small recursion.

Reading a MemoryUse as the store that wrote the value

MemoryUse(4) names the memory version that reaches the load, not the store whose bytes the load reads. In §7's box, load g may read the value from store i32 %1, ptr @g (access 2) if work leaves g alone, or from work itself, or, on the other path, from before the function. To ask which access clobbers a given location, call MSSA.getWalker()->getClobberingMemoryAccess(I). It walks the defining accesses and queries alias analysis at each step. Don't try to derive the answer from the operand.

References¶

See the chapter references.

Lesson 16.8 — Beyond scalar SSA: SSI and e-SSA, gated SSA, Memory SSA, Array SSA, Hashed SSA¶

1. Problem and motivation¶

SSI and e-SSA¶

Gated SSA¶

Memory SSA¶

Array SSA¶

Hashed SSA¶

2. Definitions and algorithms¶

SSI and e-SSA¶

Gated SSA¶

Memory SSA¶

Array SSA¶

Hashed SSA¶

3. Worked example¶

SSI and e-SSA¶

Gated SSA¶

Memory SSA¶

Array SSA¶

Hashed SSA¶

4. Invariants and correctness¶

SSI and e-SSA¶

Gated SSA¶

Memory SSA¶

Array SSA¶

Hashed SSA¶

5. Complexity¶

6. Variants and refinements¶

SSI and e-SSA¶

Gated SSA¶

Memory SSA¶

Array SSA¶

Hashed SSA¶

7. In real compilers¶

SSI and e-SSA¶

Gated SSA¶

Memory SSA¶

Array SSA¶

Hashed SSA¶

8. Comparison¶

9. Assessment¶

References¶