Lesson 19.11 — Memory optimizations: SROA, dead-store elimination, forwarding and load PRE, MemCpyOpt, LICM promotion¶

Techniques: scalar replacement of aggregates (LLVM SROA: slices, partitions, rewriting, promotion); dead-store elimination on MemorySSA (killing defs, complete and partial overwrites, stores dead at function exit, no-op stores); store-to-load forwarding, redundant-load elimination and load PRE (LLVM GVN); MemCpyOpt (memset formation, memcpy forwarding, call-slot optimization); LICM scalar promotion (link: Ch 18) · Pebble implements: pebble-dse (exercise E1) and pebble-loadfwd (exercise E2), on LLVM's AAResults and MemorySSA · Prerequisites: Lessons 19.1, 19.2 and 19.10; mem2reg (Lesson 16.4); PRE (Lesson 17.6) · Time: 6–8 hours

1. Problem and motivation¶

The previous lessons built the questions: may these accesses alias (19.1–19.9), which write does this read see (19.10). This lesson is about the answers' clients: the transformations that delete, move and merge memory operations. Each is a classic, and each is only as good as the alias analysis underneath.

SROA¶

Aggregates on the stack — a struct local, a small array, a struct returned by value — are allocas that mem2reg cannot promote, because they are accessed through GEPs and memcpy. Scalar replacement of aggregates splits such an alloca into one alloca per independently used byte range, rewrites every access, and then promotes the new allocas to SSA values. It runs early and often in LLVM's pipeline because most C++ abstractions (small structs, std::pair, iterators) disappear only after it [LLVM-SROA].

Dead-store elimination¶

A store is dead if no load can observe its value: a later store overwrites it on every path before any read, or the memory dies (a local at function exit). Deleting it saves work and exposes more optimization. LLVM's DSE finds dead stores by walking MemorySSA from each candidate to a killing definition [LLVM-DSE]; Lesson 17.3 introduced it next to ADCE.

Store-to-load forwarding and load PRE¶

A load that reads a location whose value is already in a register — from an earlier store or an earlier load of the same location, with no clobber in between — can be replaced by that value (forwarding and redundant-load elimination). If the value is available on some incoming paths only, load PRE inserts the load on the other paths and merges with a phi, the memory analogue of Lesson 17.6's PRE. LLVM's GVN does both [LLVM-GVN].

MemCpyOpt¶

memcpy and memset hide stores. MemCpyOpt turns runs of adjacent constant stores into one memset, forwards the source of a memcpy through another memcpy (b = a; c = b becomes c = a), turns "memset a temporary then copy it" into a direct memset, and lets a call write straight into the final destination (call-slot optimization) [LLVM-MemCpyOpt].

LICM scalar promotion¶

A loop that loads and stores the same location in every iteration (total += a[i] with a global total) can keep the value in a register: load once before the loop, store once after. This scalar promotion is part of LICM (Ch 18); it needs alias analysis to prove that no other access in the loop touches the location [LLVM-LICM].

2. Definitions and algorithms¶

SROA¶

Definition 19.11.1 (Slice)

A slice of an alloca \(A\) is a byte interval \([b, e)\) of \(A\) together with the use that accesses it: a load or store of a known offset and size (through GEPs with constant offsets), a memcpy, memmove or memset of a constant length, or a lifetime marker. A slice is splittable if its use can be divided into smaller accesses (memory intrinsics and integer loads/stores of a whole range). A use with an unknown offset or size (a variable GEP, an escaping pointer) makes the alloca unanalyzable.

Definition 19.11.2 (Partition)

Sort the slices by begin offset. A partition is a maximal interval \([b, e)\) such that every unsplittable slice overlapping it lies inside it; splittable slices that cross partition borders are cut at the borders. Each partition becomes one new alloca, whose type is chosen from the accesses (a common scalar type if all accesses agree, a vector or integer type otherwise).

Algorithm 19.11.3 (Scalar replacement of aggregates)

Input: a function; its allocas.
Output: a function in which analyzable aggregate allocas are replaced by per-partition allocas, promoted to SSA values where possible.
Precondition: the alloca's address does not escape (every use is an analyzable slice).
Postcondition: the function computes the same results (Theorem 19.11.13).
Invariant: every byte of the old alloca that some use accesses is covered by exactly one new alloca, at the same relative offset within its partition.

function SROA(F):
    for each alloca A in F:
        S ← slices of A (Definition 19.11.1); if some use is unanalyzable: skip A
        P ← partitions of S (Definition 19.11.2)
        for each partition p = [b, e):
            A_p ← new alloca of the type chosen for p
            for each slice s overlapping p:
                rewrite s's use to access A_p at offset (s.begin − b), or the part of it inside p
                (a memcpy into A becomes one load/store or smaller memcpy per partition)
        delete A
    PromoteMemToReg(all new allocas whose uses are now only simple loads and stores)   # Ch 16

Dead-store elimination¶

Definition 19.11.4 (Killing store, dead store)

Let \(S\) be a simple (non-volatile, non-atomic) store to location \(L_S\). A store \(K\) completely overwrites \(S\) if it is simple, MustAlias with \(L_S\) at the same start, and at least as large. \(S\) is dead if every path from \(S\) to the function exit — including an exit by unwinding out of a call — either reaches a complete overwrite of the bytes \(S\) wrote before any instruction that may read them, or ends when \(L_S\) belongs to a local that does not escape (its memory dies). "The bytes \(S\) wrote" matters in loops: a pointer computed in a loop names a different address in each iteration, so a later execution of the same pointer expression need not overwrite them. \(S\) is a no-op store if it stores the value just loaded from the same location with no intervening write to it.

Algorithm 19.11.5 (Dead-store elimination on MemorySSA)

Input: a function with MemorySSA, alias analysis, post-dominator tree.
Output: the function with dead and no-op stores deleted.
Precondition: MemorySSA is well formed (Definition 19.10.2).
Postcondition: only stores that are dead or no-op (Definition 19.11.4) are deleted (Theorem 19.11.14).
Invariant: the exploration from \(S\)'s MemoryDef visits exactly the accesses reachable along MemorySSA def-use edges before a complete overwrite; every alias answer it relies on is valid for the iteration it is applied to (below); the step count is bounded by a cap (200 in the reference solution, dse-memoryssa-scanlimit in LLVM).

function DSE(F):
    for each simple store S:
        if S stores (load P) back to P and Walker.clobber(S's defining access, L_S) dominates that load: delete S; continue
        if not KilledOnAllPaths(S): continue
        if ReadBeforeOverwrite(MemoryDef(S)): continue
        delete S (and its MemoryDef)

function KilledOnAllPaths(S):
    if the underlying object of L_S is an alloca that is never captured: return true   # dies at exit
    return some store K completely overwrites S, with nothing between S and K that may unwind, and
           either K is in S's block after S, or K post-dominates S and both pointers are Invariant

function ReadBeforeOverwrite(D):          # D = MemoryDef of S
    W ← users of D, each tagged "no phi passed";  seen ← W
    while W ≠ ∅:
        (A, passed) ← pop(W); if the step budget is exhausted: return true
        if A is a MemoryPhi:
            if not Invariant(ptr of L_S): return true               # maybe a later iteration
            push its users not in seen, tagged "phi passed"; continue
        I ← A's instruction
        if I = S: continue                                         # around a loop back to S itself
        if MR(I, L_S) ∋ ref: return true                            # a possible read of the value
        if A is a MemoryDef and I completely overwrites S
           and (not passed or Invariant(ptr of I)): continue       # this path is killed
        if A is a MemoryDef: push its users not in seen, with the same tag
    return false

function Invariant(p):   # p's value is the same in every loop iteration
    strip casts and constant-index GEPs from p
    return p is not an instruction, or it lies in the entry block or outside every loop

Alias answers compare two pointers as they are at one moment. After the walk passes a MemoryPhi it may be in a later iteration of a loop, where a loop-variant gep %a, %i names a different address than it did at \(S\): a[i-1] then does read what a[i] wrote, and a store through the same SSA value %p after the loop overwrites only the last iteration's element. Invariant restores the validity of the answers; LLVM's DSE makes the same check (isGuaranteedLoopInvariant) [LLVM-DSE]. Unwinding is the other hidden exit: if a call between \(S\) and \(K\) throws, the caller can read \(S\)'s value.

LLVM's DSE works the other way round (from each killing candidate upwards with getDomMemoryDef), and adds partial-overwrite tracking: a store or memset whose bytes are overwritten piecewise is shortened (tryToShorten) or deleted when the pieces cover it [LLVM-DSE].

Store-to-load forwarding and load PRE¶

Definition 19.11.6 (Available value)

A value \(v\) is available for a simple load \(L\) of type \(T\) from location \(\ell\) if (a) there is a simple store of \(v\) (of type \(T\)) to a location MustAlias with \(\ell\) that dominates \(L\), and no instruction on any path from it to \(L\) may write \(\ell\); or (b) \(v\) is a simple load of type \(T\) from a MustAlias location that dominates \(L\), with no write to \(\ell\) on any path between them.

Algorithm 19.11.7 (Store-to-load forwarding and redundant-load elimination, exercise E2)

Input: a function with MemorySSA and its walker, alias analysis, dominator tree.
Output: the function with loads that have an available value replaced by it.
Precondition: well-formed MemorySSA.
Postcondition: every replaced load had an available value (Theorem 19.11.15).
Invariant: Kept holds the simple loads already visited and not replaced, in a dominator-respecting order (depth-first preorder).

function LoadForward(F):
    Kept ← []
    for each simple load L in depth-first preorder of the CFG:
        C ← Walker.clobber(L)                                  # Algorithm 19.10.5
        if C is a MemoryDef of a simple store S of type(L), S dominates L, and S MustAlias L:
            replace L by S's stored value; continue
        for L2 in Kept:
            if type(L2) = type(L), L2 dominates L, L2 MustAlias L, and C dominates MemoryUse(L2):
                replace L by L2; break
        if L was not replaced: Kept.append(L)

Algorithm 19.11.8 (Load PRE, as in LLVM's GVN)

Input: a load \(L\) in block \(B\) with predecessors \(P_1, \dots, P_k\); memory dependence information.
Output: \(L\) replaced by a phi of values available at the end of each \(P_i\), with at most one new load inserted.
Precondition: \(L\)'s address is available in every \(P_i\) (or can be phi-translated), and \(L\) may be executed on the path where it is inserted (the address is dereferenceable there, or \(L\) is anticipated).
Postcondition: every path through \(B\) executes at most as many loads of \(\ell\) as before, and the value is the same (Theorem 19.11.16).
Invariant: for every predecessor, either an available value (Definition 19.11.6) or "unavailable" is recorded.

function LoadPRE(L in B):
    for each predecessor P of B:
        avail[P] ← the value of ℓ available at the end of P (a store's value, an earlier load), or none
    U ← { P : avail[P] = none }
    if U = ∅: replace L by phi(avail[P] for P in preds(B)); return      # fully redundant
    if |U| > 1 or the load is not safe to execute at the end of the P ∈ U: return
    P ← the single element of U (split the edge P → B if it is critical)
    insert L' = load ℓ at the end of P;  avail[P] ← L'
    replace L by phi(avail[P] for P in preds(B))

MemCpyOpt¶

Definition 19.11.9 (memcpy dependence)

For memcpy(d2, s2, n2) whose source \(s_2\) is MustAlias with the destination \(d_1\) of an earlier memcpy(d1, s1, n1) with \(n_2 \le n_1\), the second copy depends on the first if the first's MemoryDef is the clobber of the second's source location and nothing between them writes \(s_1\)'s bytes. A run of adjacent stores is a sequence of stores of the same byte value to consecutive, non-overlapping byte ranges.

Algorithm 19.11.10 (MemCpyOpt's main transforms)

Input: a function with MemorySSA and alias analysis.
Output: the function with memory intrinsics simplified.
Precondition: simple (non-volatile) intrinsics and stores only.
Postcondition: each rewrite writes the same bytes to the same destinations (Theorem 19.11.17).
Invariant: each rewrite replaces instructions by an equivalent sequence of at most the same length.

for each run of adjacent constant stores of one byte value (≥ a small threshold):
    replace them by memset(start, byte, total length)                        # memset formation
for each memcpy(d2, s2, n2) that depends on memcpy(d1, s1, n1) (Definition 19.11.9):
    replace it by memcpy(d2, s1, n2)                                           # memcpy forwarding
    (the first memcpy may then become dead: DSE)
for each memcpy(d, t, n) whose source t was entirely written by memset(t, c, n):
    replace it by memset(d, c, n)                                              # memset-then-copy
for each memcpy(d, t, n) where t is a local written only by a preceding call f(t, …):
    if d is not accessed between the call and the copy and f cannot see d: pass d to f instead of t
                                                                               # call-slot optimization

LICM scalar promotion¶

Definition 19.11.11 (Promotable location)

In a loop \(\Lambda\) with a preheader, a set \(M\) of simple loads and stores whose pointer operands are loop-invariant and pairwise MustAlias (one location \(\ell\)) is promotable if (a) no other instruction of \(\Lambda\) may write \(\ell\), and (b) either no other instruction may read \(\ell\) (full promotion), or \(M\) contains stores that must stay in the loop (load-only promotion: only the loads are replaced). A full promotion also needs the store sunk to the exits to be safe: \(\ell\) is written on every iteration that executes (a store is guaranteed to execute), or \(\ell\) is a local that is not captured, so an extra store at the exits cannot be observed by another thread.

Algorithm 19.11.12 (LICM scalar promotion)

Input: a loop in LCSSA form with a preheader; MemorySSA; alias analysis.
Output: promoted locations kept in SSA values across the loop.
Precondition: Definition 19.11.11 holds for the chosen set \(M\).
Postcondition: the loop computes the same values and leaves memory in the same state at its exits (Theorem 19.11.18).
Invariant: inside the loop, the SSA value (a phi in the header) always equals the contents \(\ell\) would have in the original program.

function Promote(Λ):
    sets ← alias sets of Λ's loop-invariant simple loads and stores (Lesson 19.1 §6: alias sets)
    keep the sets that are MustAlias and contain a store; drop a set if any other access of Λ may write it;
    mark it "reads outside" if some other access may read it
    for each remaining set M with location ℓ:
        v0 ← load ℓ in the preheader
        with an SSA updater: every load in M becomes the current value; every store in M defines a new value
        if not "reads outside" and the store is safe to sink:
            delete M's stores; store the live-out value to ℓ in every exit block
        else:
            keep the stores in the loop (load-only promotion)

3. Worked examples¶

SROA¶

The pair function of the first box (§7): struct pair p = {a, b}; struct pair q = p; int buf[2]; buf[0] = q.hi; buf[1] = q.lo; return buf[0] - buf[1];. Clang's -O0-style IR has five allocas (a, b, p, q, buf), two memcpys (the initializer and q = p) and twelve loads and stores. SROA on q (8 bytes):

slice	bytes	use	splittable
1	[0, 8)	`memcpy(q, p, 8)`	yes
2	[4, 8)	`load i32 q.hi`	no
3	[0, 4)	`load i32 q.lo`	no

Partitions: \([0, 4)\) (slice 3, and slice 1 cut to \([0, 4)\)) and \([4, 8)\) (slice 2 and the rest of slice 1). The memcpy becomes two i32 loads from p's partitions and two stores into q.lo/q.hi; the same happens to p and buf. After rewriting, every new alloca has only i32 loads and stores, and PromoteMemToReg turns the function into ret (b − a): the box's single sub.

Dead-store elimination¶

The second box's function, store by store (Algorithm 19.11.5 and LLVM's dse):

store	killed on all paths?	read before the overwrite?	result
`*p = 1`	yes: `*p = 2` post-dominates it, same size, MustAlias	no access in between	deleted
`memset(buf, 0, 64)`	bytes 0–15: overwritten by `memcpy(buf, src, 16)`; bytes 16–63: no	`consume(buf)` reads them	shortened to `memset(buf + 16, 0, 48)` (LLVM's partial-overwrite rule; the lesson's algorithm keeps it)
`*q = 3`	yes: `*q = 4` post-dominates it	`consume` may read `*q` (`q` is an argument, `consume` has unknown effects)	kept
`buf[0] = 1`	`buf` is a local captured by `consume`, but no instruction reads memory after the store and it dies at return	—	deleted by LLVM (it knows `buf`'s lifetime ends); the lesson's algorithm keeps it (the local escaped)

Store-to-load forwarding and load PRE¶

The third box's function f(p, c, v):

if (c) r = *p + v;   /* block if.then: %0 = load p */
else   r = v;        /* block if.else: no load */
return r + *p;       /* block if.end: load p again */

At if.end, Algorithm 19.11.8: avail[if.then] = %0 (the earlier load; nothing writes *p in between), avail[if.else] = none. One unavailable predecessor, and the load is safe there (it is executed on every path after the join anyway, and if.else → if.end is not critical): GVN inserts %.pre = load p in if.else and replaces the load in if.end by phi [%0, if.then], [%.pre, if.else]. The path through if.then now executes one load instead of two; the other path still one. A plain forwarding pass (Algorithm 19.11.7) does nothing here: neither load dominates the other's path completely.

MemCpyOpt¶

The fourth box. init: memset(tmp, 0, 64); memcpy(out, tmp, 64) — the memcpy's source was entirely written by the memset, so it becomes memset(out, 0, 64); tmp's memset is then dead (DSE removes it; the alloca stays until a later pass). zero_fields: four stores of 0 to p[0..3] are adjacent 8-byte stores of the same byte value, so they become one memset(p, 0, 32).

LICM scalar promotion¶

The fifth box: for (i) total += (int)a[i]; with int total global and const float *a. The set \(M = \{\)load total, store total\(\}\). The other access is load a[i]. With BasicAA alone, a[i] may alias total (both are arbitrary pointers into memory), but it is a read: condition (a) holds, (b) does not — load-only promotion. LLVM loads total once in for.body.lr.ph and carries it in the phi %add1, but keeps store i32 %add, ptr @total in the loop body, so that each read of a[i] still sees the up-to-date value if it happens to be total. With TBAA added, the float load cannot alias the int global: full promotion, and the store moves to the exit block for.cond.for.end_crit_edge.

4. Invariants and correctness¶

SROA¶

Theorem 19.11.13 (SROA preserves behavior)

If every use of an alloca \(A\) is an analyzable slice, replacing \(A\) by its partitions' allocas and rewriting the uses (Algorithm 19.11.3) preserves every value loaded and the final state of all other memory.

Proof

Define the correspondence \(\beta\) from bytes of \(A\) to bytes of the new allocas: byte \(x\) of \(A\) in partition \([b, e)\) maps to byte \(x - b\) of \(A_p\). It is a bijection on the accessed bytes (invariant). Each rewritten use accesses the images of exactly the bytes the original use accessed, in the same order (a cut memcpy copies the same bytes piece by piece; since the pieces do not overlap and no other instruction runs between them, the effect is the same). By induction over the execution, the contents of \(A\) at byte \(x\) equal the contents of \(\beta(x)\), so every load reads the same value. \(A\)'s address never escapes (precondition), so no other instruction can access its bytes, and other memory is untouched. PromoteMemToReg then preserves behavior by Ch 16's theorem.

Dead-store elimination¶

Theorem 19.11.14 (Deleting a dead store preserves behavior)

If Algorithm 19.11.5 deletes \(S\), every execution of the transformed function performs the same observable reads and leaves the same values in memory that is live after the function returns.

Proof

No-op store. The walker's clobber of \(S\)'s location, taken from \(S\)'s defining access, dominates the load of the stored value: by Theorem 19.10.7 nothing between the load and \(S\) writes the location, so memory already holds the stored value and the store changes nothing. Dead store. Consider an execution that reaches \(S\), writing the bytes \(\beta\). Every later instruction that reads a byte of \(\beta\) before it is overwritten would be reachable from \(S\)'s MemoryDef along MemorySSA def-use edges (its clobber chain passes through \(S\)'s def or a phi that merges it, by (W2)), before any complete overwrite; ReadBeforeOverwrite visits those accesses and returned false. Its mod/ref answers describe \(\beta\): before any MemoryPhi the execution is still in \(S\)'s iteration of every loop, so \(L_S\)'s pointer still has the value it had at \(S\); after a phi, the walk continued only because \(L_S\)'s pointer is invariant, and a kill counted only through an invariant pointer. So no such read exists (mod/ref answers are sound). Every path from \(S\) to the exit reaches a complete overwrite of \(\beta\) — in \(S\)'s block, or post-dominating with both pointers invariant, so that MustAlias holds between the values at \(S\) and at \(K\) — with no unwinding exit in between, or ends with \(L_S\) in a non-escaping local, whose memory is not live after the function returns or unwinds (Lemma 19.2.12). Hence the value stored by \(S\) is never read and never survives the function: deleting \(S\) changes no observation. Volatile and atomic stores are excluded, because their execution is itself observable.

Store-to-load forwarding and load PRE¶

Theorem 19.11.15 (Forwarding is correct)

If Algorithm 19.11.7 replaces \(L\) by a value \(v\), then in every execution \(L\) would have loaded \(v\).

Proof

Store case. \(C\) is the clobber of \(L\) (Theorem 19.10.7): no instruction between \(C\) and \(L\) on any path writes \(L\)'s location. \(C\) is a simple store \(S\) that MustAliases \(L\) with the same type (size), and \(S\) dominates \(L\), so every execution reaching \(L\) executed \(S\) last among the writes to the location: the bytes \(L\) reads are the bytes \(S\) wrote, i.e. \(v\). Load case. \(L_2\) dominates \(L\) and reads the same location; \(C\) (the clobber of \(L\)) dominates \(L_2\)'s MemoryUse, so no write between \(C\) and \(L\) exists and in particular none between \(L_2\) and \(L\) (they lie after \(C\) on every path to \(L\)): both loads read the same bytes, unchanged in between.

Theorem 19.11.16 (Load PRE is correct and never adds loads on a path)

Under Algorithm 19.11.8's precondition, the transformed function returns the same values, and every execution performs at most as many loads of \(\ell\) as before.

Proof

For each predecessor \(P\), the phi receives either an available value — equal to the contents of \(\ell\) at the end of \(P\) (Theorem 19.11.15's argument per edge) — or the new load \(L'\) placed at the end of \(P\), which reads the contents there; nothing between the end of \(P\) and \(L\) in \(B\) writes \(\ell\) (the available-value computation starts at \(L\)'s position in \(B\)). So the phi equals what \(L\) would load. Safety: \(L'\) executes only on paths that continue to \(B\) and hence to \(L\) (the edge \(P \to B\) is split if critical), where the original program loads \(\ell\) anyway, so it cannot trap where the original did not, and the count of loads on that path is unchanged; on paths through available predecessors one load disappears.

MemCpyOpt¶

Theorem 19.11.17 (MemCpyOpt's rewrites are correct)

Each transform of Algorithm 19.11.10, applied under Definition 19.11.9's conditions, leaves every destination byte with the same value and changes no other memory.

Proof

memset formation: the stores write the same byte value to consecutive disjoint ranges; the memset writes that byte to their union, and nothing reads in between (they are adjacent). memcpy forwarding: by Definition 19.11.9, the bytes at \(s_2 = d_1\) read by the second copy were written by the first copy from \(s_1\) and \(s_1\) was not written since, so reading from \(s_1\) gives the same bytes; \(n_2 \le n_1\) keeps the read inside the copied range. memset-then-copy: the source bytes all equal \(c\), so copying them writes \(c\) to \(d\). Call-slot: the call's writes to \(t\) would be copied to \(d\); writing to \(d\) directly gives the same final bytes in \(d\), provided the call does not read \(d\) and nothing accesses \(d\) in between (the conditions checked), and \(t\)'s own contents are dead afterwards.

LICM scalar promotion¶

Theorem 19.11.18 (Scalar promotion preserves behavior)

Under Definition 19.11.11, Algorithm 19.11.12 preserves every value read in the loop and the contents of \(\ell\) at every loop exit.

Proof

Invariant: at every point inside the loop, the SSA value equals the contents of \(\ell\) in the original program. Initially (the header's phi from the preheader) it is the loaded contents. The only writes to \(\ell\) in the loop are the stores of \(M\) (condition (a)), each updating the SSA value to the stored value; so the invariant is maintained and every promoted load reads the right value. Load-only promotion: the stores still execute, so memory is exactly as before, and other readers see it. Full promotion: no other instruction reads \(\ell\) in the loop (condition (b)), so deferring the writes is invisible inside the loop; at each exit the SSA value is stored, giving \(\ell\) the value of the last original store. Safety of that store: either some store of \(M\) executed on every path (so writing \(\ell\) at the exit writes a location the original also wrote), or \(\ell\) is an uncaptured local (no other thread can observe a store the original did not make).

5. Complexity¶

Technique	Time	Notes (variables: \(a\) accesses, \(s\) slices, \(K\) scan limits)
SROA	\(O(s \log s)\) per alloca (sorting slices) plus rewriting, then mem2reg	runs several times in the `-O2` pipeline (`PassBuilderPipelines.cpp`); allocas with unknown offsets are skipped
DSE	per store \(O(\min(K, a))\) MemorySSA steps and AA queries	LLVM caps the walk (`dse-memoryssa-scanlimit` = 150, `dse-memoryssa-walklimit` = 90), so worst case \(O(a \cdot K)\)
Forwarding (E2)	per load one walker query plus a scan of kept loads: \(O(a)\), so \(O(a^2)\) worst	LLVM's GVN uses MemoryDependenceAnalysis with its own block and instruction limits
Load PRE	per load \(O(p \cdot q)\) for \(p\) predecessors, \(q\) the cost of an availability query	GVN performs it only for a single unavailable predecessor
MemCpyOpt	linear scans plus MemorySSA queries	bounded by the pass's own limits
LICM promotion	alias-set construction \(O(a \alpha)\) per loop plus SSA updating	capped by `licm-mssa-optimization-cap` = 100 and `licm-mssa-max-acc-promotion` = 250 [LLVM-LICM]

Justification. Each algorithm makes a bounded number of MemorySSA or AA queries per memory instruction; the caps turn potential quadratic behavior into linear with a large constant. Pathological family for DSE: \(m\) stores to distinct noalias arguments followed by one call that reads all of them: every store's exploration reaches the call quickly, but a variant with \(m\) loads in between, each to a different location, makes every exploration visit \(m\) accesses: \(\Theta(m^2)\) steps without a cap.

SROA¶

Vector promotion. Partitions accessed as vector elements become vector values (<4 x float>); trade-off: needs consistent element types.
Speculative loads through selects and phis. SROA rewrites load (select c, p, q) into select c, (load p), (load q) when both are safe to load, unlocking promotion; trade-off: loads that may not have executed.
GCC's SRA (tree-sra.cc) does the same at the GIMPLE level, including across function boundaries in IPA-SRA; trade-off: interprocedural cost.

Dead-store elimination¶

Partial overwrites (LLVM's tryToShorten, store merging of smaller later stores into an earlier constant store); trade-off: byte-interval bookkeeping.
Stores dead because the object's lifetime ends (lifetime.end, free, function exit for allocas); trade-off: needs capture information.
Multiple killing stores on different paths (a killing store in each branch): LLVM's DSE handles them by checking all paths from the candidate; the lesson's algorithm requires one post-dominating kill; trade-off: completeness vs simplicity.

Store-to-load forwarding and load PRE¶

Forwarding with type coercion (a store of i64 feeding a load of i32 of the low half: extract with a shift and truncate); trade-off: endianness and bit-level reasoning (GVN does it; E2 does not).
MemorySSA-based GVN (NewGVN, Lesson 17.5) and EarlyCSE with memory generations (Lesson 17.4); trade-off: different pass structure, same availability notion.

MemCpyOpt¶

memmove to memcpy when the ranges are proved disjoint; trade-off: an alias query per memmove.
Stack-move optimization (merging two allocas when one is only copied into the other); trade-off: lifetime analysis.

LICM scalar promotion¶

Promotion with speculation of the store only on paths that already store; trade-off: conditional stores need guarded exits.
Register promotion in loop nests (promote across inner loops); trade-off: more complex alias sets. See Ch 18 for LICM's other parts.

7. In real compilers¶

SROA¶

LLVM, GCC

LLVM llvm/lib/Transforms/Scalar/SROA.cpp — AllocaSlices (Definition 19.11.1), SROA::splitAlloca (partitions and rewriting), SROA::promoteAllocas [LLVM-SROA] (LLVM 23.1.2). GCC gcc/tree-sra.cc and gcc/ipa-sra.cc.

SROA turns a struct, a struct copy and an array into one subtraction

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

cat > s.c <<'C'
struct pair { int lo, hi; };
int f(int a, int b) {
  struct pair p = {a, b};
  struct pair q = p;             /* an aggregate copy: a memcpy */
  int buf[2];
  buf[0] = q.hi;
  buf[1] = q.lo;
  return buf[0] - buf[1];
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm s.c -o s.ll
echo "== before: $(grep -cE '= alloca' s.ll) allocas, $(grep -cE '@llvm.memcpy' s.ll) memcpy, $(grep -cE ' = load |store ' s.ll) loads and stores"
echo "== opt -passes=sroa"
opt -passes=sroa -S s.ll | sed -n '/^define.*@f(/,/^}/p'

Output (complete):

== before: 5 allocas, 2 memcpy, 12 loads and stores
== opt -passes=sroa
define dso_local i32 @f(i32 noundef %a, i32 noundef %b) #0 {
entry:
  %sub = sub nsw i32 %b, %a
  ret i32 %sub
}

What to notice: before: 5 allocas, 2 memcpys and 12 loads and stores; after opt -passes=sroa alone: no memory operations at all, just sub nsw i32 %b, %a — the two partitions of each 8-byte aggregate became SSA values (§3).

Dead-store elimination¶

LLVM

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp — eliminateDeadStores drives DSEState::getDomMemoryDef (walk from a killing def up to a dead candidate), isCompleteOverwrite, tryToShorten for partial overwrites and eliminateRedundantStoresOfExistingValues [LLVM-DSE]. Pebble: exercise E1 (pebble-dse).

LLVM's DSE: a killed store, a shortened memset, a kept store, a store dead at exit

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

cat > d.c <<'C'
#include <string.h>
void consume(char *);
void f(int *p, int *q, const char *src) {
  *p = 1;                 /* dead: overwritten before any read */
  *p = 2;
  char buf[64];
  memset(buf, 0, 64);     /* bytes 0..15 are overwritten below: shortened */
  memcpy(buf, src, 16);
  *q = 3;                 /* not dead: consume() may read *q */
  consume(buf);
  *q = 4;
  buf[0] = 1;             /* dead: buf is not read after this */
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm d.c -o - \
  | opt -passes='sroa' -S -o d.ll
show() { sed -n '/^define.*@f(/,/^}/p' | grep -E 'store|memset|memcpy|@consume' | sed 's/, !tbaa ![0-9]*//; s/ #[0-9]*$//'; }
echo "== before"; show < d.ll
echo "== opt -passes=dse"; opt -passes=dse -S d.ll | show

Output (complete):

== before
  store i32 1, ptr %p, align 4
  store i32 2, ptr %p, align 4
  call void @llvm.memset.p0.i64(ptr align 16 %arraydecay, i8 0, i64 64, i1 false)
  call void @llvm.memcpy.p0.p0.i64(ptr align 16 %arraydecay1, ptr align 1 %src, i64 16, i1 false)
  store i32 3, ptr %q, align 4
  call void @consume(ptr noundef %arraydecay2)
  store i32 4, ptr %q, align 4
  store i8 1, ptr %arrayidx, align 16
== opt -passes=dse
  store i32 2, ptr %p, align 4
  call void @llvm.memset.p0.i64(ptr align 16 %0, i8 0, i64 48, i1 false)
  call void @llvm.memcpy.p0.p0.i64(ptr align 16 %arraydecay1, ptr align 1 %src, i64 16, i1 false)
  store i32 3, ptr %q, align 4
  call void @consume(ptr noundef %arraydecay2)
  store i32 4, ptr %q, align 4

What to notice: store i32 1 is gone (killed by store i32 2); the 64-byte memset is now 48 bytes starting 16 bytes later (%0), because the memcpy overwrites the first 16; *q = 3 stays because consume may read it; buf[0] = 1 is gone because buf is dead after it — the four rows of the §3 table.

Find where LLVM does it. Which function in DeadStoreElimination.cpp shortens a partially overwritten memset or memcpy, and why does it round the removed part to the intrinsic's alignment? (Quiz llvm-where-dse-shorten.)

Store-to-load forwarding and load PRE¶

LLVM

llvm/lib/Transforms/Scalar/GVN.cpp — GVNPass::processLoad, AnalyzeLoadAvailability (per predecessor), GVNPass::PerformLoadPRE [LLVM-GVN]; EarlyCSE forwards within dominator scopes. GCC's FRE and PRE (tree-ssa-sccvn.cc, tree-ssa-pre.cc) do the same on GIMPLE. Pebble: exercise E2 (pebble-loadfwd).

GVN's load PRE inserts the missing load

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

cat > g.c <<'C'
int f(int *p, int c, int v) {
  int r = 0;
  if (c)
    r = *p + v;      /* the load is available on this path only */
  else
    r = v;
  return r + *p;     /* partially redundant: load PRE */
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm g.c -o - \
  | opt -passes='sroa' -S -o g.ll
echo "== opt -passes=gvn"
opt -passes=gvn -S g.ll | sed -n '/^define/,/^}/p' | sed 's/, !tbaa ![0-9]*//; s/, align 4//'

Output (complete):

== opt -passes=gvn
define dso_local i32 @f(ptr noundef %p, i32 noundef %c, i32 noundef %v) #0 {
entry:
  %tobool = icmp ne i32 %c, 0
  br i1 %tobool, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %0 = load i32, ptr %p
  %add = add nsw i32 %0, %v
  br label %if.end

if.else:                                          ; preds = %entry
  %.pre = load i32, ptr %p
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  %1 = phi i32 [ %0, %if.then ], [ %.pre, %if.else ]
  %r.0 = phi i32 [ %add, %if.then ], [ %v, %if.else ]
  %add1 = add nsw i32 %r.0, %1
  ret i32 %add1
}

What to notice: the new %.pre = load in if.else and the phi %1 = phi [%0, %if.then], [%.pre, %if.else] replacing the load in if.end — Algorithm 19.11.8 with one unavailable predecessor; the path through if.then now loads once.

MemCpyOpt¶

LLVM

llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp — tryMergingIntoMemset, processMemCpyMemCpyDependence, performMemCpyToMemSetOptzn, performCallSlotOptzn [LLVM-MemCpyOpt].

MemCpyOpt forms memsets

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

cat > mc.c <<'C'
#include <string.h>
struct big { long a[8]; };
void init(struct big *out) {
  struct big tmp;
  memset(&tmp, 0, sizeof tmp);
  *out = tmp;                 /* memset to a temporary then copy: memset the destination */
}
void zero_fields(long *p) {
  p[0] = 0; p[1] = 0; p[2] = 0; p[3] = 0;   /* adjacent zero stores: one memset */
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm mc.c -o - \
  | opt -passes='sroa' -S -o mc.ll
echo "== opt -passes=memcpyopt"
opt -passes=memcpyopt,dse -S mc.ll | sed -n '/^define/,/^}/p' | grep -vE 'lifetime|^\s*$' | sed 's/, !tbaa ![0-9]*//'

Output (complete):

== opt -passes=memcpyopt
define dso_local void @init(ptr noundef %out) #0 {
entry:
  %tmp.sroa.0 = alloca [8 x i64], align 8
  call void @llvm.memset.p0.i64(ptr align 8 %out, i8 0, i64 64, i1 false)
  ret void
}
define dso_local void @zero_fields(ptr noundef %p) #0 {
entry:
  %arrayidx = getelementptr inbounds i64, ptr %p, i64 0
  %arrayidx1 = getelementptr inbounds i64, ptr %p, i64 1
  %arrayidx2 = getelementptr inbounds i64, ptr %p, i64 2
  %arrayidx3 = getelementptr inbounds i64, ptr %p, i64 3
  call void @llvm.memset.p0.i64(ptr align 8 %arrayidx, i8 0, i64 32, i1 false)
  ret void
}

What to notice: init copies a zeroed temporary: after memcpyopt,dse the destination is zeroed directly (memset(out, 0, 64)) and the temporary's memset is gone (the unused alloca remains for a later pass); zero_fields's four zero stores became one 32-byte memset.

LICM scalar promotion¶

LLVM

llvm/lib/Transforms/Scalar/LICM.cpp — collectPromotionCandidates (must-alias sets with a mod, "reads outside the set") and llvm::promoteLoopAccessesToScalars (SSA updating, load-only promotion when stores must stay) [LLVM-LICM]. Ch 18 covers LICM's hoisting and sinking.

Load-only versus full promotion depends on alias analysis

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

cat > l.c <<'C'
int total;
void acc(const float *a, int n) {
  for (int i = 0; i < n; i++)
    total += (int)a[i];     /* load and store of @total in every iteration */
}
C
clang-23 -O1 -Xclang -disable-llvm-optzns -fno-discard-value-names -S -emit-llvm l.c -o - \
  | opt -passes='sroa,simplifycfg,loop-simplify,lcssa,loop-rotate' -S -o l.ll
for aa in basic-aa 'basic-aa,tbaa'; do
  echo "== opt -aa-pipeline=$aa -passes='loop-mssa(licm)'"
  opt -aa-pipeline=$aa -passes='loop-mssa(licm)' -S l.ll | sed -n '/^define/,/^}/p' \
    | grep -E '@total|%total|^[a-z._]+:' | sed 's/, !tbaa ![0-9]*//; s/, align 4//; s/ *;.*//'
done

Output (complete):

== opt -aa-pipeline=basic-aa -passes='loop-mssa(licm)'
entry:
for.body.lr.ph:
  %total.promoted = load i32, ptr @total
for.body:
  %add1 = phi i32 [ %total.promoted, %for.body.lr.ph ], [ %add, %for.body ]
  store i32 %add, ptr @total
for.cond.for.end_crit_edge:
for.end:
== opt -aa-pipeline=basic-aa,tbaa -passes='loop-mssa(licm)'
entry:
for.body.lr.ph:
  %total.promoted = load i32, ptr @total
for.body:
  %add1 = phi i32 [ %total.promoted, %for.body.lr.ph ], [ %add, %for.body ]
for.cond.for.end_crit_edge:
  store i32 %add.lcssa, ptr @total
for.end:

What to notice: with BasicAA only, total is loaded once in the preheader (%total.promoted) and carried in the phi, but the store stays in for.body: the float load may alias it (load-only promotion). With TBAA the store moves to the exit block for.cond.for.end_crit_edge (full promotion) — Definition 19.11.11's two cases.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
SROA	Removes whole aggregates with constant-offset uses; blocked by escaping or variable-offset uses	\(O(s \log s)\) per alloca · runs several times per pipeline	Promoted SSA values; readable IR	High (~6,400 lines in `SROA.cpp`: slicing, rewriting, types)	LLVM SROA, GCC SRA; essential for C++ abstraction removal
Dead-store elimination	Complete and partial overwrites, stores dead at exit; limited by mod/ref of calls	per store \(O(\min(K, a))\) · capped scans	Deleted or shortened stores	High in LLVM, medium for E1	LLVM `dse` (function simplification pipeline), GCC `dse`
Store-to-load forwarding and load PRE	Forwarding needs a dominating available value; PRE handles one missing predecessor	per load one clobber query (+ PRE per predecessor)	Replaced loads, inserted `.pre` loads and phis	Medium (E2), high (GVN)	LLVM GVN and EarlyCSE; GCC FRE/PRE
MemCpyOpt	Pattern-based: memset formation, copy forwarding, call-slot	linear with MemorySSA queries	Fewer, larger intrinsics	Medium–high	LLVM `memcpyopt` (after SROA and before DSE)
LICM scalar promotion	Whole loops' accesses to one must-alias location; full or load-only	alias sets per loop, capped	Preheader load, exit stores, header phis	Medium (SSA updater, safety)	LLVM LICM, GCC `tree-ssa-loop-im.cc`

Choose SROA first in any pipeline: it creates the SSA values every other pass needs. Choose DSE after optimizations that make stores redundant (inlining, GVN, LICM). Choose forwarding and load PRE as part of global value numbering. Choose MemCpyOpt where front ends produce aggregate copies (C++, Rust). Choose promotion for any loop that accumulates in memory — and give it good alias analysis, or it can only promote the loads.

9. Assessment¶

Quiz: sroa-partitions, sroa-escape (tag sroa); dse-table, llvm-where-dse-shorten (tag dse); loadpre-insert, forwarding-conditions (tag load-forwarding); memcpyopt-forward, memcpyopt-memset (tag memcpyopt); licm-promotion-kind, licm-promotion-safety (tag licm-promotion).
Drill: ./course drill memoryssa-build (the def-use chains DSE and forwarding walk); ./course drill licm-legality (Ch 18) for promotion's legality conditions; ./course drill lcm-sets (Ch 17) for PRE's placement. SROA and MemCpyOpt are pattern transformations practised in the quiz.
Flashcards: tags sroa, dse, load-forwarding, memcpyopt, licm-promotion.
Exercises: E1 pebble-dse, E2 pebble-loadfwd.

References¶

See the chapter references.

Lesson 19.11 — Memory optimizations: SROA, dead-store elimination, forwarding and load PRE, MemCpyOpt, LICM promotion¶

1. Problem and motivation¶

SROA¶

Dead-store elimination¶

Store-to-load forwarding and load PRE¶

MemCpyOpt¶

LICM scalar promotion¶

2. Definitions and algorithms¶

SROA¶

Dead-store elimination¶

Store-to-load forwarding and load PRE¶

MemCpyOpt¶

LICM scalar promotion¶

3. Worked examples¶

SROA¶

Dead-store elimination¶

Store-to-load forwarding and load PRE¶

MemCpyOpt¶

LICM scalar promotion¶

4. Invariants and correctness¶

SROA¶

Dead-store elimination¶

Store-to-load forwarding and load PRE¶

MemCpyOpt¶

LICM scalar promotion¶

5. Complexity¶

6. Variants and refinements¶

SROA¶

Dead-store elimination¶

Store-to-load forwarding and load PRE¶

MemCpyOpt¶

LICM scalar promotion¶

7. In real compilers¶

SROA¶

Dead-store elimination¶

Store-to-load forwarding and load PRE¶

MemCpyOpt¶

LICM scalar promotion¶

8. Comparison¶

9. Assessment¶

References¶