Lesson 19.10 — Memory SSA in depth: accesses, clobber walkers, optimized uses and cost limits¶

Techniques: Memory SSA as LLVM builds and uses it — MemoryDef, MemoryUse, MemoryPhi and liveOnEntry; construction by minimal SSA over one memory variable; the clobber walker; optimized uses; cost limits (Novillo's Memory SSA, 2007; LLVM MemorySSA) · Pebble implements: exercises E1 (pebble-dse) and E2 (pebble-loadfwd) are built on LLVM's MemorySSA and its walker · Prerequisites: Lesson 16.8 (the first look at Memory SSA: this lesson goes deeper), Lesson 16.2 (phi placement and renaming), Lesson 19.1 (alias and mod/ref queries) · Time: 4–5 hours

1. Problem and motivation¶

MemorySSA¶

Every memory optimization asks the same question at many places: which earlier write can this read observe? Walking the CFG backwards from each load, asking alias queries against every store on every path, costs \(O(\text{instructions} \times \text{paths})\) per load. Memory SSA answers it with def-use chains for memory. Rather than one SSA variable per memory location — unbounded, and "which location" is itself an alias question — all of memory is one variable: every instruction that may write memory defines a new version (a MemoryDef), every instruction that only reads uses one (a MemoryUse), and MemoryPhis merge versions at joins. Novillo designed it for GCC [Nov07]; LLVM's MemorySSA follows the same design and adds a walker that refines a use's version, on demand and with alias queries, to the nearest write that may actually clobber the location [LLVM-MemorySSADoc, LLVM-MSSA]. Lesson 16.8 introduced the representation; this lesson covers its invariants, the walker, the optimization of uses and the cost limits that keep it fast. LLVM's DSE, LICM, EarlyCSE and NewGVN are built on it, and so are exercises E1 and E2.

2. Definitions and algorithms¶

MemorySSA¶

Definition 19.10.1 (Memory accesses)

For a function \(F\), Memory SSA assigns: to every instruction that may write memory (stores, calls that are not memory(read)/none, fences, volatile and atomic accesses) a MemoryDef with a numeric ID; to every instruction that only reads memory a MemoryUse; to certain block entries a MemoryPhi with one operand per predecessor; and one liveOnEntry definition (ID 0) for the memory state on entry to \(F\). Each MemoryDef and MemoryUse has one defining access (a MemoryDef, MemoryPhi or liveOnEntry), printed MemoryDef(d) / MemoryUse(d). LLVM numbers MemoryDefs in block layout order starting at 1 and MemoryPhis after them.

Definition 19.10.2 (Well-formed Memory SSA)

Memory SSA is well formed if: (W1) every defining access dominates its user (for a phi operand: dominates the end of the corresponding predecessor), liveOnEntry dominating everything; (W2) the MemoryDefs form, together with the phis, a single SSA web for one variable — each def's defining access is the nearest def or phi above it on every path (before use optimization); (W3) a block has a MemoryPhi if it is in the iterated dominance frontier of the blocks containing MemoryDefs; (W4) for an optimized MemoryUse, the defining access is a clobber of the use's location (Definition 19.10.4), or a phi, or liveOnEntry.

Algorithm 19.10.3 (Memory SSA construction)

Input: a function in which every instruction's memory effect (none, read, may write) is known; its dominator tree.
Output: the accesses and defining accesses of Definition 19.10.1.
Precondition: the CFG is fixed; unreachable blocks get no accesses.
Postcondition: the result is well formed (W1–W3), and is minimal SSA for the single memory variable (Theorem 19.10.6).
Invariant: during the renaming walk, cur is the memory version that reaches the current instruction along the dominator-tree path.

function BuildMemorySSA(F):
    n ← 0
    for each block B in layout order, each instruction I in B:
        if I may write memory: n ← n + 1; create MemoryDef #n for I
        else if I may read memory: create MemoryUse for I
    DefBlocks ← blocks with at least one MemoryDef
    for each B in IDF(DefBlocks): create MemoryPhi at the top of B      # Ch 15's iterated DF
    Rename(entry, liveOnEntry)

function Rename(B, cur):
    if B has a MemoryPhi φ: cur ← φ
    for each access A in B, in order:
        definingAccess(A) ← cur
        if A is a MemoryDef: cur ← A
    for each successor S of B with a MemoryPhi φ_S: φ_S.operand(B) ← cur
    for each child C of B in the dominator tree: Rename(C, cur)

Definition 19.10.4 (Clobber, optimized use)

An access \(D\) (a MemoryDef) clobbers a location \(L\) if \(\mathit{MR}(D, L) \ni \mathsf{mod}\) (Definition 19.1.4: \(D\) may write a byte of \(L\)). The clobbering access of a MemoryUse \(U\) of location \(L\) is the nearest access above \(U\) on the memory SSA chain that may clobber \(L\): walk the defining accesses from \(U\), skipping MemoryDefs that do not clobber \(L\); at a MemoryPhi, if all incoming chains lead to the same clobber, continue with it, otherwise stop at the phi. A MemoryUse is optimized when its defining access has been replaced by its clobbering access.

Algorithm 19.10.5 (The clobber walker)

Input: a MemoryUse (or a MemoryDef, for "what clobbers its location above it") with location \(L\); a step limit \(K\) (LLVM: memssa-check-limit = 100).
Output: a clobbering access: a MemoryDef, a MemoryPhi or liveOnEntry.
Precondition: well-formed Memory SSA; a sound alias analysis.
Postcondition: every MemoryDef on any path between the result and the query that is skipped does not clobber \(L\) (Theorem 19.10.7); if the limit is hit, the result is a conservative access (the defining access or a phi), never an unsound one.
Invariant: active holds the phis on the current recursion path; each step decrements the budget.

function Clobber(U, L):
    return Up(definingAccess(U), L, active = ∅) or definingAccess(U)

function Up(A, L, active):
    loop:
        if budget exhausted: return A                         # give up conservatively
        if A = liveOnEntry: return A
        if A is a MemoryPhi:
            if A ∈ active: return none                         # a cycle back to this phi adds nothing
            R ← { Up(op, L, active ∪ {A}) : op operand of A } \ {none}
            if R = ∅: return none
            return the only element of R if |R| = 1, else A
        if MR(instruction of A, L) ∋ mod: return A            # a clobber
        A ← definingAccess(A)                                   # skip a non-clobbering def

LLVM's walker (ClobberWalker) is an optimized form of this search: it caches results, walks phi operands in a depth-first order that stops at the first path proving the phi necessary, and optimizes all uses of a block at once in OptimizeUses::optimizeUsesInBlock, keeping a stack of the defs seen per location [LLVM-MSSA].

3. Worked example¶

MemorySSA¶

The function of the second real-world box (§7): %a and %b are noalias arguments, so a store to one never clobbers the other; the call @ext(%a, %b) may write both. Blocks and memory operations (./course drill memoryssa-build uses the same notation, with B.i for the \(i\)-th memory operation of block \(B\)):

A: store a            -> B
B: (none)             -> C, F
C: store b; load a    -> D, E
D: call               -> E
E: load b             -> B
F: load a; load b     -> exit

flowchart TD
  A([A]) --> B[B]
  B --> C[C]
  B --> F[F]
  C --> D[D]
  C --> E[E]
  D --> E
  E --> B

Numbering. MemoryDefs in layout order: A.1 (store a) = 1, C.1 (store b) = 2, D.1 (call) = 3.

Phi placement. Def blocks \(\{A, C, D\}\). The immediate dominators are \(\mathrm{idom}(B) = A\), \(\mathrm{idom}(C) = \mathrm{idom}(F) = B\), \(\mathrm{idom}(D) = \mathrm{idom}(E) = C\). Dominance frontiers: \(\mathrm{DF}(A) = \emptyset\); \(\mathrm{DF}(C) = \{B\}\) (C dominates E, whose successor B it does not strictly dominate); \(\mathrm{DF}(D) = \{E\}\) (E has the second predecessor C); \(\mathrm{DF}(E) = \mathrm{DF}(B) = \{B\}\). So \(\mathrm{IDF}(\{A, C, D\}) = \{B, E\}\): MemoryPhis at the top of B (LLVM's ID 5) and E (ID 4).

Renaming along the dominator tree A → B → {C → {D, E}, F}:

block	cur on entry	accesses and their defining access	cur on exit	phi operands set
A	liveOnEntry	A.1 (def 1): liveOnEntry	1	phi@B[A] = 1
B	phi@B	—	phi@B	—
C	phi@B	C.1 (def 2): phi@B; C.2 (use): 2	2	phi@E[C] = 2
D	2	D.1 (def 3): 2	3	phi@E[D] = 3
E	phi@E	E.1 (use): phi@E	phi@E	phi@B[E] = phi@E
F	phi@B	F.1 (use): phi@B; F.2 (use): phi@B	phi@B	—

Optimized uses (Algorithm 19.10.5):

C.2 (load a): defining access 2 (store b) does not clobber a → skip to phi@B. Operand A: def 1 (store a) clobbers → 1. Operand E: phi@E; its operand C: def 2, skip, phi@B is active → none; operand D: def 3 (the call) clobbers a → 3. So phi@E gives 3, and phi@B has results \(\{1, 3\}\): two different clobbers → phi@B.
E.1 (load b): phi@E; operand C: def 2 (store b) clobbers → 2; operand D: def 3 → 3; different → phi@E.
F.1 (load a): as for C.2 → phi@B.
F.2 (load b): phi@B; operand A: def 1 (store a) skips to liveOnEntry → 0; operand E: phi@E → {2, 3} → phi@E; results \(\{0, \text{phi@E}\}\) → phi@B.

With LLVM's IDs (phi@B = 5, phi@E = 4) these are exactly the MemoryUse(5), MemoryUse(4), MemoryUse(5), MemoryUse(5) that opt -passes='print<memoryssa>' prints (the second box): print<memoryssa> shows uses after optimization. The course oracle agreed with opt on 400 random functions of this kind (tools/course/tests/test_ch19.py).

Try it yourself: ./course drill memoryssa-build --seed 3 --difficulty hard --solution.

4. Invariants and correctness¶

MemorySSA¶

Theorem 19.10.6 (Construction yields well-formed, minimal Memory SSA)

Algorithm 19.10.3 produces Memory SSA satisfying (W1)–(W3). With the single memory variable "all of memory", it is minimal SSA: no phi can be removed without some use seeing a wrong version.

Proof

(W3) holds by construction (phis exactly at \(\mathrm{IDF}(\mathit{DefBlocks})\)). The rest is the correctness of Cytron's renaming for one variable (Lesson 16.2; Theorem 16.8.17 states it for Memory SSA): by induction over the dominator-tree walk, cur on entry to a block \(B\) is the last memory definition on the dominator-tree path from the entry to \(B\) (a phi of \(B\) if any), and the IDF placement guarantees that this is the definition reaching \(B\) along every CFG path: a path that avoided the dominator-tree path's last def would pass through a join in the def's iterated dominance frontier, which has a phi. So each defining access is the nearest def or phi above the access on every path (W2), and it dominates the access (W1). Minimality is minimality of Cytron's placement: a block in \(\mathrm{IDF}(\mathit{DefBlocks})\) is reached by two different definitions along two paths.

Theorem 19.10.7 (The walker is sound)

If Algorithm 19.10.5 returns \(C\) for a use \(U\) of location \(L\), then on every CFG path from \(C\) (or from the entry, if \(C\) is liveOnEntry) to \(U\), no instruction strictly between them may write \(L\), except inside the region merged by a phi result \(C\) — in which case every write on those paths is accounted for by the phi. Replacing \(U\)'s defining access by \(C\) preserves the meaning of the use-def chain for \(L\).

Proof

Induction on the walk. Initially \(A\) is \(U\)'s defining access, which by (W2) is the nearest def or phi on every path. Skip step: if \(A\) is a MemoryDef with \(\mathsf{mod} \notin \mathit{MR}(A, L)\) — sound by Lemma 19.1.10 and the soundness of the AA — then the writes between \(\mathrm{definingAccess}(A)\) and \(U\) on any path are those between \(\mathrm{definingAccess}(A)\) and \(A\), then \(A\) (not writing \(L\)), then those between \(A\) and \(U\) (none that write \(L\), by the induction hypothesis). Phi step: if all operands' walks (excluding operands that cycle back through an active phi, which contribute only paths that re-enter the phi and hence are covered by the other operands) return the same \(C\), every path to the phi passes from \(C\) to the phi without a write to \(L\); otherwise the walker returns the phi itself, which is always a correct defining access by (W2). Budget: returning the current \(A\) early is correct by the induction hypothesis — it is a correct defining access, just not the nearest clobber.

Unoptimized and optimized uses differ

print<memoryssa> prints uses after optimization, so MemoryUse(1) may point far above the nearest def. A pass that needs "the def immediately above" must use getDefiningAccess() on a def (defs are not optimized in place) or walk the def chain; a pass that needs "the value this load sees" wants the clobber. Exercise E2 uses the walker's clobber; E1 walks def-use edges downward.

5. Complexity¶

Let \(n\) be the number of blocks, \(e\) CFG edges, \(a\) memory accesses, \(K\) the walker's step limit.

Operation	Time	Space
Construction (Algorithm 19.10.3)	\(O(n + e + a)\) with a linear-time IDF (LLVM's `ForwardIDFCalculator`)	\(O(a + n)\) accesses and phis
One clobber query (Algorithm 19.10.5)	\(O(\min(K, a))\) AA queries (each \(O(q)\), Lesson 19.1 §5), with caching	\(O(\text{visited})\)
Optimizing all uses	\(O(a \cdot K)\) worst case; LLVM's per-block stack optimization is near-linear in practice	\(O(a)\)

Justification. Construction is one-variable Cytron: numbering is one pass, the IDF is linear with the Sreedhar–Gao algorithm, and renaming visits each access once. Each walker step visits one access and makes at most one mod/ref query; phi operands multiply the visited set only up to the budget. Pathological family: a load after a chain of \(m\) stores to other noalias locations in straight-line code: the walker skips all \(m\) defs, so with \(m > K = 100\) it gives up and returns the def \(K\) steps up — a correct but unoptimized answer. The limit is -memssa-check-limit (default 100) in MemorySSA.cpp [LLVM-MSSA]; LICM uses its own caps on accesses per loop (licm-mssa-optimization-cap).

MemorySSA¶

Lazy use optimization. LLVM optimizes uses the first time a client asks for the walker (ensureOptimizedUses); trade-off: clients that never query pay only for construction.
Skip-self walker. getClobberingMemoryAccess(Def, Loc) for a def asks what clobbers the def's own location above it (used for no-op stores in E1); trade-off: another entry point with its own cache.
MemorySSAUpdater. Incremental updates when passes insert, delete or move accesses (LICM, DSE, loop unswitching); trade-off: every transformation must call it or invalidate the analysis.
Partitioned memory. GCC's early design used several virtual variables ("memory partitions") [Nov07], and HSSA used one per variable with μ/χ operators [SSAB, Ch. 16]; trade-off: more precise chains, much more memory. GCC and LLVM both settled on one memory variable plus alias queries.

7. In real compilers¶

MemorySSA¶

LLVM and GCC

LLVM llvm/lib/Analysis/MemorySSA.cpp — MemorySSA::buildMemorySSA, placePHINodes (IDF), renamePass, ClobberWalker::findClobber, OptimizeUses::optimizeUsesInBlock, and the MaxCheckLimit option memssa-check-limit = 100 [LLVM-MSSA]; llvm/docs/MemorySSA.md [LLVM-MemorySSADoc] (LLVM 23.1.2). Clients: DSE, LICM, the MemorySSA-based EarlyCSE instance of the -O2 pipeline, NewGVN, loop unswitching. GCC keeps a single virtual operand .MEM with VDEF/VUSE in its SSA form (Lesson 16.8's GCC box), which its DSE and PRE walk the same way [Nov07].

LLVM's MemorySSA for a loop with a noalias pair and an opaque call

Reproduce (clang 23.1.2, opt 23.1.2; Linux x86-64):

cat > m.c <<'C'
void touch(int *);
int f(int *restrict a, int *restrict b, int n) {
  *a = 0;
  for (int i = 0; i < n; i++) {
    *b = i;           /* writes b only: a load of *a can skip it */
    if (i & 1)
      touch(b);       /* an opaque call: may write anything b can reach */
  }
  return *a + *b;
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm m.c -o - \
  | opt -passes='sroa,simplifycfg' -S -o m.ll
opt -passes='print<memoryssa>' -disable-output m.ll 2>&1 | sed -n '/^define/,/^}/p' | grep -vE '^\s*$|icmp|br |add nsw|and i32|^for\.cond\.cleanup'
echo "== the walker (print<memoryssa-walker>) for the two final loads:"
opt -passes='print<memoryssa-walker>' -disable-output m.ll 2>&1 | grep -B1 -E '= load i32, ptr %[ab],' | tail -4

Output (complete):

define dso_local i32 @f(ptr noalias noundef %a, ptr noalias noundef %b, i32 noundef %n) #0 {
entry:
; 1 = MemoryDef(liveOnEntry)
  store i32 0, ptr %a, align 4, !tbaa !9
for.cond:                                         ; preds = %for.inc, %entry
; 5 = MemoryPhi({entry,1},{for.inc,4})
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
for.body:                                         ; preds = %for.cond
; 2 = MemoryDef(5)
  store i32 %i.0, ptr %b, align 4, !tbaa !9
if.then:                                          ; preds = %for.body
; 3 = MemoryDef(2)
  call void @touch(ptr noundef %b)
for.inc:                                          ; preds = %if.then, %for.body
; 4 = MemoryPhi({for.body,2},{if.then,3})
for.end:                                          ; preds = %for.cond
; MemoryUse(1)
  %0 = load i32, ptr %a, align 4, !tbaa !9
; MemoryUse(5)
  %1 = load i32, ptr %b, align 4, !tbaa !9
  ret i32 %add
}
== the walker (print<memoryssa-walker>) for the two final loads:
; MemoryUse(1) - clobbered by 1 = MemoryDef(liveOnEntry)->liveOnEntry
  %0 = load i32, ptr %a, align 4, !tbaa !9
; MemoryUse(5) - clobbered by 5 = MemoryPhi({entry,1},{for.inc,4})
  %1 = load i32, ptr %b, align 4, !tbaa !9

What to notice: the loop header gets 5 = MemoryPhi and the join after the conditional call 4 = MemoryPhi; the final load of *a is MemoryUse(1) — optimized past the phi and the loop, because neither the store to b nor touch(b) can write the noalias, uncaptured a — while the load of *b stays at the phi. The walker lines say the same: "clobbered by 1" versus "clobbered by 5 = MemoryPhi".

The worked example in LLVM

Reproduce (opt 23.1.2; any OS):

cat > ms.ll <<'LL'
declare void @ext(ptr, ptr)

define void @f(ptr noalias %a, ptr noalias %b, i1 %c1, i1 %c2) {
A:
  store i32 1, ptr %a
  br label %B
B:
  br i1 %c1, label %C, label %F
C:
  store i32 2, ptr %b
  %C.2 = load i32, ptr %a
  br i1 %c2, label %D, label %E
D:
  call void @ext(ptr %a, ptr %b)
  br label %E
E:
  %E.1 = load i32, ptr %b
  br label %B
F:
  %F.1 = load i32, ptr %a
  %F.2 = load i32, ptr %b
  ret void
}
LL
opt -passes='print<memoryssa>' -disable-output ms.ll 2>&1 | grep -vE '^$|^MemorySSA for'

Output (complete):

define void @f(ptr noalias %a, ptr noalias %b, i1 %c1, i1 %c2) {
A:
; 1 = MemoryDef(liveOnEntry)
  store i32 1, ptr %a, align 4
  br label %B
B:                                                ; preds = %E, %A
; 5 = MemoryPhi({A,1},{E,4})
  br i1 %c1, label %C, label %F
C:                                                ; preds = %B
; 2 = MemoryDef(5)
  store i32 2, ptr %b, align 4
; MemoryUse(5)
  %C.2 = load i32, ptr %a, align 4
  br i1 %c2, label %D, label %E
D:                                                ; preds = %C
; 3 = MemoryDef(2)
  call void @ext(ptr %a, ptr %b)
  br label %E
E:                                                ; preds = %D, %C
; 4 = MemoryPhi({C,2},{D,3})
; MemoryUse(4)
  %E.1 = load i32, ptr %b, align 4
  br label %B
F:                                                ; preds = %B
; MemoryUse(5)
  %F.1 = load i32, ptr %a, align 4
; MemoryUse(5)
  %F.2 = load i32, ptr %b, align 4
  ret void
}

What to notice: the numbering (defs 1–3 in layout order, phis 5 at B and 4 at E), the phi operands {A,1},{E,4} and {C,2},{D,3}, and the optimized uses MemoryUse(5), MemoryUse(4), MemoryUse(5), MemoryUse(5) are those computed by hand in §3.

Find where LLVM does it. In MemorySSA.cpp, find the command-line option that bounds the walker's search. What is its name and default value? (Check your answer against Algorithm 19.10.5.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
MemorySSA	Def-use chains for all memory; precision comes from the walker's alias queries (one variable, refined on demand); bounded by \(K\)	construction linear · queries capped at 100 steps	`print<memoryssa>`, `print<memoryssa-walker>`; readable versions	High (~2,700 lines plus the updater); for clients, low	LLVM DSE, LICM, EarlyCSE, NewGVN; GCC's `.MEM` virtual operands

Compared with the alternatives of Lesson 16.8 (HSSA with one virtual variable per location, Array SSA): choose Memory SSA for any modern optimizer; the single variable keeps construction linear and pushes precision into cached, budgeted queries. Choose per-location SSA only when a client needs precise chains for a few named locations and can afford their number.

9. Assessment¶

Quiz: memssa-phis, memssa-clobber-trace (tag memoryssa).
Drill: ./course drill memoryssa-build (easy: phis and defining accesses; medium: + phi operands; hard: + clobbers).
Flashcards: tag memoryssa.
Exercises: E1 pebble-dse walks MemorySSA def-use edges; E2 pebble-loadfwd uses the walker.

References¶

See the chapter references.

Lesson 19.10 — Memory SSA in depth: accesses, clobber walkers, optimized uses and cost limits¶

1. Problem and motivation¶

MemorySSA¶

2. Definitions and algorithms¶

MemorySSA¶

3. Worked example¶

MemorySSA¶

4. Invariants and correctness¶

MemorySSA¶

5. Complexity¶

6. Variants and refinements¶

MemorySSA¶

7. In real compilers¶

MemorySSA¶

8. Comparison¶

9. Assessment¶

References¶