Memory SSA: Giving Loads and Stores Def-Use Chains

SSA form gives every scalar value a single definition. Memory has no such property. A store writes through a pointer, and nothing in the instruction says whether that pointer aliases the location another instruction later loads. Two stores to the same address are two definitions of the same location, and the IR cannot name the location at all when the address is computed.

The usual response is to treat memory as one large object with one definition and many uses, which makes every load depend on every store. That is sound and it destroys optimisation: a load after a store cannot be replaced by the stored value without proving the store writes the load’s location, a store whose value is never loaded cannot be removed without proving no later read observes it, and every pass that touches memory must consult an alias analysis directly. Memory SSA is the attempt to recover def-use chains for memory by introducing a distinguished value that represents the state of the heap, and by treating each store as a definition of that value.

The Heap as a Versioned Value

The construction introduces a name for memory, conventionally written with a subscript, and a version counter that increments at each write. A store produces a new version. A load is a use of the version that reaches it, not a definition: reading does not change the memory state, so it forwards the version it consumed to the operations that follow, and a later pass decides when two loads may share a version. A function entry defines version zero, representing the state left by the caller.

With a single version of the whole heap, this reduces to a chain: every store depends on the previous store, and every load depends on the most recent store on its path. The chain is exactly what the naive model gives, and it carries no more information. The value comes from splitting the single heap name into a family of names, one per alias class, so that a store to one class does not define a new version of another.

Alias analysis supplies the classes. A points-to analysis computes, for each pointer, the set of abstract locations it may refer to. Two pointers whose sets are disjoint cannot alias, and their stores are definitions of disjoint versions. Two pointers whose sets overlap must be modelled as writing the same version, which merges their chains and loses precision for both.

The precision of the resulting IR is therefore bounded above by the precision of the alias analysis, and that bound is the honest way to describe memory SSA: it does not solve aliasing, it makes aliasing decisions visible as graph structure so that later passes can consume them without re-deriving them.

Memory Phis and the Merge Problem

At a control-flow merge, the heap has as many versions as there are incoming edges, so a memory phi is inserted exactly as a scalar phi would be. The phi’s inputs are the versions defined at the end of each predecessor. A load after the merge reads the phi’s result, which means it depends on all the versions that could reach it.

The placement problem is the same dominance-frontier computation as for scalars, applied to the set of blocks that store. The difference is scale: the number of “variables” is the number of alias classes, which can be large, and the number of stores per class can be large, so a naive per-class worklist is expensive on big functions. Implementations either run the placement once over a partitioned heap with a combined worklist, or restrict the analysis to classes that are actually loaded, which is a liveness-like pruning.

The merge itself is where most of the practical benefit appears. If one branch stores a constant to a local variable and the other does not, the memory phi at the merge has one input that is a fresh version containing the constant and one input from before the branch. A load after the merge reads the phi’s result, which is not a single stored value, so the load cannot be replaced by one constant. If both branches store the same constant, the two phi inputs carry the same value, and the phi collapses to it, after which the load can be replaced. That collapse is what makes the analysis worthwhile on code where a variable is initialised in both arms of a conditional.

Promotion and the Escape Problem

The strongest use of memory SSA is not analysis but elimination. If a variable’s address never escapes the function — it is not passed to a call, not stored into another object, not returned — then every access to it is a direct load or store that the compiler can see. Such a variable can be promoted: each store becomes an assignment to a fresh SSA name, each load becomes a use of the name the most recent store defined, and the memory version for that variable disappears from the heap chain entirely, leaving the loads and stores to be handled by the scalar machinery.

Promotion requires proving non-escape, and that proof is interprocedural in the general case. A pointer passed to a function that the compiler cannot see may be stored anywhere, so the variable must be treated as escaping. A pointer stored into a field of a struct that itself escapes propagates the escape. The analysis is a fixpoint over the program’s assignments, and its precision determines how many variables get promoted.

The payoff is large. A promoted local has no address, so its accesses become register operations, and the register allocator handles it with the machinery already described. A local that stays in memory because of one escaping use costs a load or store at every access, and that asymmetry is why escape analysis is one of the highest-leverage analyses in an optimising compiler.

Promotion also interacts with the parallel-copy problem. A promoted variable’s definition at a merge becomes a phi, and destroying that phi later requires the moves discussed in Phi Functions: Parallel Semantics and the Out-of-SSA Problem. A variable that stays in memory needs no such moves, because the memory phi is not a register value at all. Promotion therefore trades memory traffic for register pressure and copy insertion, and the trade is not always favourable for large structures.

Store-to-Load Forwarding

The direct consumer of memory SSA is forwarding: a load whose memory input is defined by a store to the same location can be replaced by the stored value, and the load deleted. The condition is that the version reaching the load is exactly the version the store produced, with no intervening definition of an aliasing class. Forwarding is what feeds sparse constant propagation with values that live in memory rather than in registers, and it is also what lets a later pass remove the store itself once its value has been substituted into every reachable load.

In graph terms, look at the memory state that reaches the load. If it is a store to a location that must-alias the load’s address, the loaded value is the value the store wrote. If a call sits between the store and the load and the call’s summary says it does not modify that class, the store’s state still reaches the load and the forwarding holds. If the reaching state is a call that may write the class, forwarding stops. If it is a memory phi, each input is treated separately: the load is replaced by a phi of the forwarded values, one per input, and only the inputs whose store is overwritten by a may-aliasing write stop the forwarding, because the state reaching the load in that case is not the state the store produced.

The subtle failure is partial aliasing. A store of eight bytes to an address, followed by a load of four bytes from an address that overlaps but is not equal, cannot be forwarded by value substitution alone; the correct transformation is a bit-field extraction, which is only valid if the endianness and the alignment are known. Most compilers decline to forward in that case, which is why structure field accesses through casts often resist optimisation even when the alias analysis is precise.

A second failure is a store whose value is itself a load from the same location. Forwarding would produce a self-reference, which is not a value. The correct result is that the load is redundant and can be deleted, because the value it reads is the one already in the location; but the deletion must not remove the store’s memory effect. Distinguishing “the load is redundant” from “the load can be replaced” is a source of bugs in implementations that treat forwarding as a single rewrite.

Calls and the Mod/Ref Summary

A call is a definition of every memory class it might write. Without a summary, that is every class, so every call kills the memory chains and every load after a call is Overdefined. With a summary that lists the classes the callee may modify and the classes it may read, the call defines only the modified classes, and the rest of the chain survives.

Computing the summary is a fixpoint over the call graph, and it is complicated by recursion and by indirect calls. A recursive function’s summary must be computed from its own body, which requires assuming a summary and iterating until stable. An indirect call through a function pointer requires the points-to set of the pointer to enumerate candidate callees, and if that set is large the summary is the union of many, which is usually close to “modifies everything”.

The precision gained is worth the cost for direct calls to small functions, which is the common case in code that has not been aggressively inlined. For indirect calls, the summary is often so conservative that the memory SSA chain is broken at every call site anyway, which is one of the arguments for inlining and devirtualisation before memory analysis.

Why It Must Be Destroyed, Not Verified

Scalar SSA has a clean verifier: each name has one definition, each use is dominated by it, each phi has one input per edge. Memory SSA has no such check, because the “definitions” are stores whose addresses are not syntactically comparable, and the alias classes are an abstraction that the verifier cannot reconstruct.

The practical consequence is that a full memory SSA is a transient form. It is built with the same dominance-frontier placement and renaming machinery as scalar SSA, used by forwarding and dead-store elimination, and then destroyed, because keeping it consistent across transformations would require every pass that moves a store to update the memory phis and the version chains. Scalar SSA survives because renaming is cheap and the invariants are local; memory SSA does not, because a single store moved across a call invalidates the summaries that made the chain precise.

Some IRs keep a restricted form permanently, in which memory is accessed only through explicit load and store instructions with typed pointers and a separate alias metadata, and the analyses reconstruct the chains on demand. That is a different trade: the IR stays simple and verifiable, and each analysis pays the cost of rebuilding the version graph. The choice between the two is a choice about where the complexity lives, and both are defensible.

What memory SSA does establish is a discipline: aliasing decisions become explicit graph edges rather than implicit assumptions inside each pass. A pass that wants to know whether a load can see a store asks the graph. A pass that wants to change the graph must say which classes it affects. The discipline is what makes it possible to reason about memory at all in a compiler with many passes, even when the form itself is discarded between them.