Lesson 16.4 — Case study: LLVM's mem2reg, SROA and SSAUpdater

Techniques: mem2reg (PromoteMemToReg: promotable allocas, single-store and single-block fast paths, live-in blocks, IDFCalculator, renaming, phi simplification), SROA (scalar replacement of aggregates, which ends in mem2reg), SSA repair with SSAUpdater and SSAUpdaterBulk · Pebble implements: pebble-mem2reg (E1), checked phi-for-phi against an independent oracle and against LLVM's mem2reg · Prerequisites: Lessons 16.1–16.3, Ch 9 (loads, stores, allocas, phi rules), Ch 12 (writing a pass) · Time: 5–6 hours (plus E1)

Clang does not build SSA. It emits every local variable as an alloca in the entry block, every assignment as a store and every read as a load (the -O0 output of every real-world box in this chapter). SSA for scalars is then built by an LLVM pass, mem2reg, which is Cytron's construction specialized to memory slots, with Sreedhar–Gao placement and a liveness filter. Structs and arrays are first split into scalars by SROA, which calls the same promotion code. And when a transformation duplicates code (loop rotation, jump threading, LCSSA formation), it repairs SSA locally with SSAUpdater, a Braun-style on-demand lookup. This lesson reads the three as algorithms; exercise E1 has you write the first.

1. Problem and motivation

The problem. Given LLVM IR in which some local variables live in stack slots, rewrite every load and store of each eligible slot into SSA values and phis, delete the slot, and keep the IR verified and equivalent. pebblec emits Pebble locals as allocas for the same reason Clang does: the front end stays simple and a single pass builds SSA for all of them.

mem2reg

mem2reg is the thin wrapper PromotePass around PromoteMemToReg [LLVM-Mem2RegPass, LLVM-Mem2Reg]: collect the promotable allocas of the entry block, promote them, repeat until none is left. PromoteMemToReg handles the common cases (one store; one block) without any phi machinery, and runs pruned Cytron construction for the rest: definition blocks from stores, live-in blocks from loads, ForwardIDFCalculator with setLiveInBlocks, and a renaming walk. It finishes with InstSimplify's phi folding.

SROA

An aggregate alloca (%struct.pair, [8 x i32]) is not promotable: it is accessed through GEPs and memcpy. Scalar replacement of aggregates splits it into one alloca per independently accessed slice and rewrites every access; the resulting scalar allocas are promoted by the same PromoteMemToReg call [LLVM-SROA]. In LLVM's -O1+ pipelines SROA runs before and instead of mem2reg.

SSAUpdater

After a transformation clones a block, a value defined there has two definitions, and every use must be rewired to "the value that reaches here". SSAUpdater answers this for one value at a time: the caller registers the available definitions per block and asks for the value at a use; the updater walks predecessors backwards, as Braun's readVariable does, and places phis on the explored subgraph with a small Cytron-style computation [LLVM-SSAUpdater]. SSAUpdaterBulk does the same for many values at once with IDFCalculator [LLVM-SSAUpdaterBulk]. [SSAB, Ch. 5] calls this family SSA reconstruction.

2. Definitions and algorithms

mem2reg

Definition 16.4.1 (Promotable alloca)

An alloca in the entry block is promotable if each of its users is (a) a load from it that is not volatile, (b) a store into it (the alloca is the pointer operand, never the stored value) that is not volatile, or (c) a llvm.lifetime.start/end intrinsic; and all its loads and stores access one type. (LLVM's isAllocaPromotable also accepts droppable intrinsics and zero-index GEPs or bitcasts used only by lifetime markers [LLVM-Mem2Reg]; clang's -O0 output never needs those.) A promotable alloca plays the role of a variable \(v\): its stores are definitions, its loads are uses, and its initial value is undef.

Algorithm 16.4.2 (Live-in blocks of one alloca)

• Input: an alloca \(a\); the blocks \(D\) containing stores to \(a\) (reachable ones only).
• Output: \(L = \{\, B \mid a \in \mathrm{LiveIn}(B) \,\}\) (Definition 16.1.6).
• Precondition: \(a\) is promotable.
• Postcondition: \(B \in L\) iff some path from the start of \(B\) reaches a load of \(a\) without a store to \(a\) before it.
• Invariant: every block on the worklist is live-in; a block enters the worklist at most once.

function LiveInBlocks(a, D):
    W ← []
    for each block B containing a load of a:
        if B ∉ D: append B to W
        else if the first access to a in B is a load: append B to W   # load before store
    L ← {}
    while W not empty:
        B ← pop W
        if B ∈ L: continue
        L ← L ∪ {B}
        for P in preds(B):
            if P ∉ D and P is reachable: push P on W                 # a store in P kills
    return L

Algorithm 16.4.3 (pebble-mem2reg / PromoteMem2Reg)

• Input: a function with a dominator tree.
• Output: the function with every promotable alloca replaced by SSA values.
• Precondition: the IR verifies.
• Postcondition: no promotable alloca remains; the IR verifies; the behavior is unchanged; the phis inserted are exactly the pruned placement of each promoted alloca (Theorem 16.4.7).
• Invariant: each round promotes a set of allocas that were promotable at its start; the dominator tree stays valid (no CFG change).

function Mem2Reg(F, DT):
    repeat                                                # promotion can expose new candidates
        A ← promotable allocas of F's entry block (Definition 16.4.1)
        if A empty: return
        for a in A: delete a's lifetime intrinsics
        for a in A:                                       # placement, one alloca at a time
            D ← blocks with a store to a
            L ← LiveInBlocks(a, D)                        # Algorithm 16.4.2
            for Y in SreedharGaoPhis(G, DT, D, L):        # Algorithm 16.2.4
                insert an empty phi for a at the top of Y
        RenameAll(F, DT, A)                               # Algorithm 16.2.3 with loads/stores
        for a in A: delete a (its remaining users are in unreachable code: replace by poison)

function RenameAll(F, DT, A):
    for a in A: S[a] ← [undef]
    walk the dominator tree in preorder (iteratively):
        entering X:
            for each inserted phi p for a at the top of X: push p on S[a]
            for each instruction I of X, in order:
                if I = load from a ∈ A:  replace all uses of I by top(S[a]); delete I
                if I = store v into a ∈ A: push v on S[a]; delete I
            for each CFG edge X → Y, for each inserted phi p for a at Y:
                add the incoming value top(S[a]) for X to p
        leaving X: pop what X pushed
    for each inserted phi p and each unreachable predecessor P of its block:
        add the incoming value poison for P to p

LLVM's PromoteMem2Reg::run differs in three ways: (1) before placement it tries two fast paths, rewriteSingleStoreAlloca (one store: replace every load it dominates by the stored value) and promoteSingleBlockAlloca (all accesses in one block: a linear sweep); (2) RenamePass walks the CFG depth-first from the entry, carrying the current values along each edge, instead of the dominator tree; (3) at the end it folds every new phi that simplifyInstruction can fold (Lesson 16.3, Aycock–Horspool's rules). Pebble's pass omits (1) and (3), so its phi count is exactly the pruned count.

SROA

Definition 16.4.4 (Slices and partitions)

For an alloca of \(s\) bytes, every use that accesses it at a constant byte range \([b, e) \subseteq [0, s)\) is a slice: loads, stores, memcpy/memset into or out of it, GEPs with constant offsets. A partition is a maximal range covered by overlapping slices; slices that straddle two partitions force them to merge. An alloca is splittable if every use is a slice (no pointer escapes, no variable offsets).

Algorithm 16.4.5 (Scalar replacement of aggregates, simplified)

• Input: an alloca \(a\) of \(s\) bytes.
• Output: one new alloca per partition, every use rewritten, then promotion.
• Precondition: \(a\) is splittable (Definition 16.4.4).
• Postcondition: the program is equivalent; no use of \(a\) remains; each new alloca covers one partition.
• Invariant: after rewriting use \(u\), the bytes \(u\) reads or writes are exactly the bytes of the new allocas covering \(u\)'s slice.

function SROA(a):
    slices ← [(begin, end, use) for each use of a]        # fails if a use is not a slice
    sort slices by begin
    partitions ← []
    for (b, e, u) in slices:
        if partitions not empty and b < end(last(partitions)):
            extend last(partitions) to max(end, e)          # overlap: same partition
        else:
            append [b, e) to partitions
    for P in partitions:
        new[P] ← alloca of a type of size |P| (the type of the uses when they agree, else iN)
    for (b, e, u) in slices:
        if u covers exactly one partition P: rewrite u to access new[P] at offset b - begin(P)
        else:                                                # memcpy/memset over several
            split u into one load/store (or memcpy piece) per covered partition
    delete a
    PromoteMemToReg({ new[P] | new[P] is promotable })     # Algorithm 16.4.3

LLVM's SROA::runOnAlloca builds AllocaSlices, forms partitions with a sweep over the sorted slices, rewrites with AllocaSliceRewriter, and promotes with PromoteMemToReg; it also handles vector and integer "widening" of partitions and speculates loads through select and phi [LLVM-SROA].

SSAUpdater

Algorithm 16.4.6 (SSAUpdater: value of a variable at a use)

• Input: available definitions \(\mathrm{Avail}[B]\) (the value at the end of \(B\)) for some blocks; a use in block \(U\).
• Output: the value that reaches the use; new phis where needed.
• Precondition: every path from the entry to \(U\) passes through a block with an available value (else the answer is poison along that path).
• Postcondition: the returned value's definition dominates the use and equals, on every execution, the last available definition executed.
• Invariant: the explored block list contains exactly the blocks reachable backwards from \(U\) without passing a block in \(\mathrm{Avail}\).

function GetValueInMiddleOfBlock(U):                 # the value at a use inside U
    if U has a single predecessor P: return GetValueAtEndOfBlock(P)
    if U has no predecessor: return poison
    vals ← [GetValueAtEndOfBlock(P) for P in preds(U)]
    if all vals are the same value: return it
    return an existing phi of U with exactly these incoming values, or a new one

function GetValueAtEndOfBlock(B):
    if B ∈ Avail: return Avail[B]
    list ← blocks found by walking predecessors from B until blocks in Avail  # BuildBlockList
    idom' ← dominators of that subgraph, rooted at a pseudo-entry above the Avail blocks (CHK)
    phiBlocks ← blocks of list in the iterated frontier of the Avail blocks, by fixpoint
    for B' in list in reverse postorder:
        Avail[B'] ← a phi at B' if B' ∈ phiBlocks, else Avail[idom'(B')]
    fill the operands of the new phis from Avail of their predecessors
    return Avail[B]

This is SSAUpdaterImpl::GetValue with BuildBlockList, FindDominators, FindPHIPlacement and FindAvailableVals in llvm/include/llvm/Transforms/Utils/SSAUpdaterImpl.h; it reuses an existing phi when one matches (FindExistingPHI) [LLVM-SSAUpdater].

3. Worked example

mem2reg on the swap loop

swap.c (the fib loop of the real-world box below) has five allocas. For each one, the facts Algorithm 16.4.3 computes (blocks: entry, for.cond, for.body, for.inc, for.end):

alloca	stores (D)	loads	path LLVM takes	live-in blocks (Alg. 16.4.2)	DF⁺(D)	phis
%n.addr	entry	for.cond	single store, the argument %n is noundef: every load becomes %n	—	—	0
%a	entry, for.body	for.body (before its store), for.end	general	for.body, for.cond, for.inc, for.end	{for.cond}	1
%b	entry, for.body	for.body (before its store, twice)	general	for.body, for.cond, for.inc	{for.cond}	1
%i	entry, for.inc	for.cond, for.inc (before its store)	general	for.cond, for.inc, for.body	{for.cond}	1
%t	for.body	for.body (after its store)	single block: the load takes the stored value	—	—	0

• For %a: the load in for.body precedes the store there (t = a then a = b), so for.body is live-in; walking back: for.cond (no store) joins, then its predecessors entry (a store: stop) and for.inc (no store: joins), whose predecessor for.body is already in. DF(for.body) = {for.cond} (it dominates for.inc, which jumps back to for.cond), and DF(for.cond) = {for.cond}.
• The frontier of entry is empty, so the initial stores never cause phis themselves (Theorem 15.3.10).

pebble-mem2reg<stats> reports it (output of the solution build):

pebble-mem2reg: @fib: promoted 5 allocas, inserted 3 phis

Renaming then fills %a.phi = phi [0, %entry], [%b.phi, %for.inc]: at the end of for.inc the top of %a's stack is the value stored in for.body, which was the loaded %b, which is %b.phi. The copy through %t has been folded by renaming itself: a load is replaced by the stored value, so t = a; a = b; b = t + b becomes %add = add %a.phi, %b.phi with no copies. The result is transformed SSA (Definition 16.1.8): %a.phi uses %b.phi of the same block.

SROA on a struct

For sroa.c's struct pair p, q (8 bytes each), the slices of %p are: the initializing memcpy [0, 8), the loads p.a [0, 4) and p.b [4, 8), and the memcpy from %q [0, 8). The partitions are [0, 4) and [4, 8): the two memcpys are split per partition. The same for %q. The four new i32 allocas are promotable, and promotion yields the two phis %p.sroa.0.0 and %p.sroa.4.0 of the real-world box; %q's slices vanish entirely because q's fields are stored and immediately reloaded in one block.

SSAUpdater in loop rotation

In count of the SSAUpdater box, rotation clones the header (%sq = mul %i, %i, the test) into the preheader. %sq now has two definitions: the clone in the entry (constant-folded to 0 because %i is 0 there) and the original, which moves to the bottom of the loop. Its use at the top of the body asks GetValueInMiddleOfBlock(body): two predecessors, two different values (0 from the new preheader, %sq from the latch), so a phi %sq3 = phi [0, %body.lr.ph], [%sq, %body] is created. The use in the exit block gets the value through the LCSSA phi.

Try it

After E1, run opt -load-pass-plugin=build/<preset>/lib/PebblePasses.so -passes='pebble-mem2reg<stats>' -disable-output swap.ll on the box's input, and compare with opt -passes=mem2reg; ./course drill phi-placement --difficulty hard --solution shows the same liveness walk on random CFGs.

4. Invariants and correctness

mem2reg

Theorem 16.4.7 (pebble-mem2reg is correct and pruned)

Algorithm 16.4.3 terminates; afterwards the function verifies, has no promotable alloca, and has the same behavior; the phis inserted for each promoted alloca \(a\) are exactly \(\Phi_{\mathrm{pruned}}(a)\). LLVM's mem2reg places a subset of the same phis: exactly those that survive repeated simplifyInstruction.

Proof

Termination: each round deletes at least one alloca and creates none. Pruned: a promotable alloca is a variable of Definition 16.1.1 whose definitions are its stores (plus the entry's undef), whose uses are its loads, and whose liveness is computed exactly by Algorithm 16.4.2 (it is the backward reachability of Definition 16.1.6 from the upward-exposed loads, stopping at killing stores). Algorithm 16.2.4 with that set returns \(\mathrm{DF}^{+}(D) \cap L\) (Theorem 16.2.7), and \(\mathrm{DF}^{+}(D) = \mathrm{DF}^{+}(D \cup \{r\})\) (Theorem 15.3.10). Behavior: RenameAll is Algorithm 16.2.3 with loads as uses and stores as definitions, so Theorem 16.2.6 applies: every load is replaced by the value of the last store executed on the path to it, or by undef if none, which is what the load returned; loads of other memory are unaffected because a promotable alloca's address never escapes (Definition 16.4.1). Verification: phis are at block tops with one entry per predecessor edge (unreachable predecessors get poison), and every replacement value dominates its uses by Theorem 16.2.6(c). LLVM: its fast paths place no phi where pruned SSA places none (Lemma 16.4.8), its general path is the same placement, and the final loop removes exactly the phis that simplify, iterated to a fixed point. The test ch16.Fixture.MatchesLLVMAfterSimplification checks the last sentence function by function.

Lemma 16.4.8 (The fast paths agree with pruned SSA)

(a) If \(a\) has a single store, in block \(s\), that dominates every load of \(a\) (a load in \(s\) itself comes after the store), then \(\Phi_{\mathrm{pruned}}(a) = \emptyset\). (b) If all loads and stores of \(a\) are in one block and no load precedes the first store, then \(\Phi_{\mathrm{pruned}}(a) = \emptyset\).

Proof

(a) First, no block of \(\mathrm{DF}^{+}(\{s\})\) is strictly dominated by \(s\). By induction over Definition 15.3.2: blocks of \(\mathrm{DF}(s)\) are not, by definition. Let \(y \in \mathrm{DF}^{+}(\{s\})\) not be strictly dominated by \(s\), and let \(z \in \mathrm{DF}(y)\) with witness predecessor \(p\) (\(y \mathrel{\mathrm{dom}} p\)). If \(s \mathrel{\mathrm{sdom}} z\), then \(s \mathrel{\mathrm{dom}} p\) (every path to \(p\) extends to \(z\)), so \(s\) and \(y\), both dominators of \(p\), are comparable. If \(y = s\), then \(z \in \mathrm{DF}(s)\) is not strictly dominated by \(s\): contradiction. If \(s\) does not dominate \(y\), then \(y \mathrel{\mathrm{sdom}} s \mathrel{\mathrm{sdom}} z\), contradicting \(z \in \mathrm{DF}(y)\). The case \(s \mathrel{\mathrm{sdom}} y\) is excluded by hypothesis. Now let \(Y \in \mathrm{DF}^{+}(\{s\}) \cap L\) (\(\mathrm{DF}(r) = \emptyset\), so the entry's undef adds nothing) and let \(\pi\) be a path from the start of \(Y\) to a load \(\ell\) that passes no store. If \(Y = s\), \(\pi\) must pass the store before leaving \(s\), so \(\ell\) is in \(s\) before the store: excluded. Otherwise \(s\) does not dominate \(Y\), so a path \(r \leadsto Y\) avoids \(s\), and followed by \(\pi\) it reaches \(\ell\) without the store, contradicting the store's dominance of \(\ell\). (b) A block is live-in only if some path from it reaches an upward-exposed load. The only loads are in the single block \(B\), and they follow the first store, so none is upward exposed: \(L = \emptyset\).

SROA

Theorem 16.4.9 (SROA preserves behavior)

If \(a\) is splittable, Algorithm 16.4.5 produces an equivalent program.

Proof

The partitions are disjoint and cover every byte any use touches. Each rewritten use touches the same bytes as before, now in the new allocas covering its slice, at the same relative offsets; a split memcpy copies the same bytes piece by piece, and pieces of different partitions cannot alias (distinct allocas). Since no use observes \(a\)'s address (splittable: no escape), the mapping from \(a\)'s bytes to the new allocas' bytes is invisible to the program. Promotion is Theorem 16.4.7.

SSAUpdater

Theorem 16.4.10 (SSAUpdater returns the reaching definition)

Under Algorithm 16.4.6's precondition, the returned value is, on every execution, the last available definition executed before the use, and its definition dominates the use.

Proof sketch (full proof: [SSAB, Ch. 5]; the code in SSAUpdaterImpl.h)

The explored subgraph contains every block reachable backwards from the use without an available definition, so every path into it from outside enters through an Avail block, which the pseudo-entry makes a root. Phi placement on the subgraph is Cytron's (\(\mathrm{DF}^{+}\) of the definitions, computed by fixpoint), and the values are assigned by walking subgraph dominators (Algorithm 16.2.3's rule "nearest dominating definition"), so Theorem 16.2.6 applies to the subgraph. A block outside the subgraph never needs a value.

When it breaks. mem2reg must not run on an alloca whose address escapes (a call, a ptrtoint, a store of the pointer): the loads through the escaped pointer would not be renamed. A load of a different type than the stores (type punning through memory) also blocks promotion. SSAUpdater misbehaves when a use and a definition sit in the same block with the use first; loop rotation checks this explicitly ("SSAUpdater can't handle a non-PHI use in the same block as an earlier def", in LoopRotationUtils.cpp).

5. Complexity

\(n\) = blocks, \(m\) = edges, \(I\) = instructions, \(\lvert A \rvert\) = promoted allocas, \(u_a\) = uses of alloca \(a\).

Technique	Time (worst)	Time (typical)	Space
mem2reg (Pebble)	\(O(I)\) scan + \(\sum_a O(n + m)\) for live-in and IDF + \(O(I + \lvert A \rvert n)\) renaming (checking each block's phis per alloca)	the fast paths handle most allocas in \(O(u_a)\)	\(O(\lvert A \rvert + \text{phis})\)
SROA	\(O(u_a \log u_a)\) to sort slices per alloca, plus rewriting and promotion	linear	\(O(u_a)\)
SSAUpdater	\(O(k \cdot (d + 2))\) per query, for \(k\) explored blocks and loop connectedness \(d\) of the explored subgraph (CHK passes)	a few blocks per query	\(O(k)\)

Justification. Algorithm 16.4.2 visits each block and edge at most once per alloca; Algorithm 16.2.4 is linear per alloca (Theorem 15.3.18). The renaming walk touches each instruction once; the Pebble solution looks up phis per (block, alloca), which LLVM avoids with a map keyed by block number. SROA sorts the slices once. SSAUpdater runs CHK (Lesson 15.1) on the explored subgraph, whose pass count is bounded by its loop connectedness plus two.

Proposition 16.4.11 (Per-alloca placement is quadratic in the worst case)

With \(\lvert A \rvert = \Theta(n)\) allocas each stored in a different block of a CFG where each live-in set has \(\Theta(n)\) blocks, placement costs \(\Theta(n^2)\) even though the output can have \(O(n)\) phis.

Proof

A chain of \(n\) blocks inside one loop; alloca \(a_j\) is stored in block \(j\) and loaded in the loop header. Each \(a_j\) is live-in at the header and at every block on the path back to it, \(\Theta(n)\) blocks, and Algorithm 16.4.2 visits them all: \(\Theta(n^2)\) total. Each \(a_j\) gets one phi (at the header): \(n\) phis. LLVM accepts this cost; the SSA book's merge-set methods trade memory for time here [SSAB, Ch. 4].

At scale. mem2reg/sroa run on every function in every LLVM pipeline, usually several times; on -O0 IR most allocas take a fast path, which is why PromoteMem2Reg::run counts them separately (NumSingleStore, NumLocalPromoted statistics in [LLVM-Mem2Reg]).

6. Variants and refinements

mem2reg

• CFG-walk renaming (LLVM's RenamePass with a worklist of (block, predecessor, incoming values)) — trade-off: no dominator-tree walk, but values must be carried per edge.
• Debug-info preservation: #dbg_declare records are converted to #dbg_value at stores and phis (ConvertDebugDeclareToDebugValue) — trade-off: extra work per store so debuggers still find the variable.
• Assumption-preserving loads: loads with !nonnull/!noundef metadata become llvm.assume calls when replaced (convertMetadataToAssumes) — trade-off: keeps facts the load promised.

SROA

• Pre-splitting of loads and stores across partitions and vector promotion of partitions accessed as vectors — trade-off: more rewriting logic, fewer leftover allocas [LLVM-SROA].
• Speculation through select/phi of loads from two allocas — trade-off: may execute a load that was conditional; only when both addresses are safe to load.

SSAUpdater

• SSAUpdaterBulk: live-in blocks + IDFCalculator for many variables in one go — trade-off: faster for bulk updates, needs a dominator tree [LLVM-SSAUpdaterBulk].
• MemorySSAUpdater: the same repair for MemorySSA's memory phis (Lesson 16.8).
• Braun-style repair without dominators: exactly Algorithm 16.3.2 on a sealed CFG, used by Cranelift after its own CFG edits.

7. In real compilers

mem2reg

Five allocas become three phis (and a phi that reads another phi)

Reproduce (clang 23.1.2, opt 23.1.2):

cat > swap.c <<'EOF'
int fib(int n) {
  int a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    int t = a;
    a = b;
    b = t + b;
  }
  return a;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm swap.c -o swap.ll
grep -c alloca swap.ll
opt -passes=mem2reg -S swap.ll | sed -n '/^define/,/^}/p'

Output (complete):

5
define dso_local i32 @fib(i32 noundef %n) #0 {
entry:
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %b.0 = phi i32 [ 1, %entry ], [ %add, %for.inc ]
  %a.0 = phi i32 [ 0, %entry ], [ %b.0, %for.inc ]
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %cmp = icmp slt i32 %i.0, %n
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %add = add nsw i32 %a.0, %b.0
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  ret i32 %a.0
}

What to notice: the table of §3 predicted it: %n.addr and %t vanished through the fast paths, %a, %b, %i got one phi each at for.cond, the only block of their DF⁺ where they are live. %a.0 = phi [..], [%b.0, %for.inc] reads the other phi of the same block: with Definition 16.1.2's parallel semantics this is the swap a, b = b, a + b. It is transformed SSA; leaving it naively would hit the swap problem (Lesson 16.6).

SROA

SROA splits a struct into two phis; mem2reg alone cannot

Reproduce (clang 23.1.2, opt 23.1.2):

cat > sroa.c <<'EOF'
struct pair { int a, b; };
int fibp(int n) {
  struct pair p = {0, 1};
  for (int i = 0; i < n; i++) {
    struct pair q = {p.b, p.a + p.b};
    p = q;
  }
  return p.a;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm sroa.c -o sroa.ll
opt -passes=mem2reg -S sroa.ll | grep -E 'alloca|memcpy|phi'
opt -passes=sroa -S sroa.ll | sed -n '/^define/,/^}/p'

Output (complete):

  %p = alloca %struct.pair, align 4
  %q = alloca %struct.pair, align 4
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %p, ptr align 4 @__const.fibp.p, i64 8, i1 false)
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  call void @llvm.memcpy.p0.p0.i64(ptr align 4 %p, ptr align 4 %q, i64 8, i1 false)
declare void @llvm.memcpy.p0.p0.i64(ptr noalias writeonly captures(none), ptr noalias readonly captures(none), i64, i1 immarg) #1
define dso_local i32 @fibp(i32 noundef %n) #0 {
entry:
  %p.sroa.0.0.copyload = load i32, ptr @__const.fibp.p, align 4
  %p.sroa.4.0.copyload = load i32, ptr getelementptr inbounds (i8, ptr @__const.fibp.p, i64 4), align 4
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %p.sroa.0.0 = phi i32 [ %p.sroa.0.0.copyload, %entry ], [ %p.sroa.4.0, %for.inc ]
  %p.sroa.4.0 = phi i32 [ %p.sroa.4.0.copyload, %entry ], [ %add, %for.inc ]
  %cmp = icmp slt i32 %i.0, %n
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %add = add nsw i32 %p.sroa.0.0, %p.sroa.4.0
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %inc = add nsw i32 %i.0, 1
  br label %for.cond, !llvm.loop !5

for.end:                                          ; preds = %for.cond
  ret i32 %p.sroa.0.0
}

What to notice: mem2reg promotes only i and n: %p and %q are used by memcpy and GEPs, so they fail Definition 16.4.1. SROA forms the partitions [0, 4) and [4, 8) of %p (names p.sroa.0 and p.sroa.4: the byte offset is in the name), splits the memcpys (the initializer became two loads from the constant), and promotes the slices: the same two phis as fib, with the same swap shape. %q disappeared entirely.

SSAUpdater

Loop rotation repairs SSA with SSAUpdater

Reproduce (opt 23.1.2):

cat > rot.ll <<'EOF'
declare void @work(i32)

define i32 @count(i32 %n) {
entry:
  br label %header

header:
  %i = phi i32 [ 0, %entry ], [ %i.next, %body ]
  %sq = mul i32 %i, %i
  %c = icmp slt i32 %sq, %n
  br i1 %c, label %body, label %exit

body:
  call void @work(i32 %sq)
  %i.next = add i32 %i, 1
  br label %header

exit:
  ret i32 %sq
}
EOF
opt -passes=loop-rotate -S rot.ll | sed -n '/^define/,/^}/p'

Output (complete):

define i32 @count(i32 %n) {
entry:
  %c1 = icmp slt i32 0, %n
  br i1 %c1, label %body.lr.ph, label %exit

body.lr.ph:                                       ; preds = %entry
  br label %body

body:                                             ; preds = %body.lr.ph, %body
  %sq3 = phi i32 [ 0, %body.lr.ph ], [ %sq, %body ]
  %i2 = phi i32 [ 0, %body.lr.ph ], [ %i.next, %body ]
  call void @work(i32 %sq3)
  %i.next = add i32 %i2, 1
  %sq = mul i32 %i.next, %i.next
  %c = icmp slt i32 %sq, %n
  br i1 %c, label %body, label %header.exit_crit_edge

header.exit_crit_edge:                            ; preds = %body
  %split = phi i32 [ %sq, %body ]
  br label %exit

exit:                                             ; preds = %header.exit_crit_edge, %entry
  %sq.lcssa = phi i32 [ %split, %header.exit_crit_edge ], [ 0, %entry ]
  ret i32 %sq.lcssa
}

What to notice: LoopRotate copied the header into the entry (where %sq folds to 0) and moved it to the loop bottom. The value %sq now has two definitions, registered with SSA.AddAvailableValue(OrigHeader, ...) and (OrigPreheader, ...) in llvm/lib/Transforms/Utils/LoopRotationUtils.cpp; each use asks the updater, which creates %sq3 at the loop's new header (two predecessors, two values, Algorithm 16.4.6) and %sq.lcssa at the exit. The single-entry phi %split comes from splitting the exit edge to keep loop-closed SSA (Lesson 15.7).

Find where LLVM does it. In llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp (LLVM 23.1.2), PromoteMem2Reg::run tries two special cases before computing any frontier. Question: what is the name of the function that handles an alloca with exactly one store? (Quiz llvm-where-single-store.)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
mem2reg	scalar allocas with only loads and stores; pruned phis, then simplified	linear per alloca after the dominator tree · fast paths for one store or one block	TSSA (loads folded into stored values)	PromoteMemoryToRegister.cpp is ~1 200 lines; Pebble's E1 ~250	every LLVM -O0-to-SSA step; pebblec after lowering
SROA	aggregates with constant-offset accesses; then mem2reg	\(O(u \log u)\) per alloca · the most expensive of the three	scalar phis per field, splits memcpy	SROA.cpp is ~6 400 lines	the first scalar pass of -O1+ pipelines
SSAUpdater	one value, arbitrary set of definitions, any CFG	proportional to the explored subgraph · cheap per query	reuses matching phis	SSAUpdaterImpl.h ~500 lines	loop rotation, jump threading, LCSSA, LICM promotion

Choose mem2reg when a front end emitted scalars as memory (always, for LLVM). Choose SROA when structs, arrays or memcpy stand between the variables and promotion; in practice run SROA and let it promote. Choose SSAUpdater when a transformation creates a second definition of an existing value; use SSAUpdaterBulk when there are many such values.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch16.yaml)	Drill	Flashcard tag	Exercises
mem2reg	mem2reg-table, llvm-where-single-store, llvm-where-livein	./course drill phi-placement --difficulty hard (pruned column = mem2reg's placement)	mem2reg	E1
SROA	sroa-partitions, sroa-why	no drill: slicing is mechanical; practiced through the box and sroa-partitions	sroa	—
SSAUpdater	ssaupdater-phi, ssaupdater-vs-bulk	./course drill phi-placement (the same DF⁺ on a subgraph)	ssaupdater	—

Promoting an alloca whose address escapes

store ptr %x, ptr %p stores the address of %x; after that any call may read or write %x through %p. Such an alloca is not promotable (Definition 16.4.1(b)). A pass that only checks "all users are loads and stores" without checking which operand the alloca is miscompiles pointer_local in the E1 corpus.

References

See the chapter references.