Memory SSA Construction

Problem definition

LLVM IR uses SSA for registers but not for memory (load/store/alloca), which makes flow‑sensitive memory analyses (aliasing, LICM, call‑graph precision) expensive and imprecise.

Prerequisite: an initial flow‑insensitive points‑to analysis must run first to tell us which loads and stores may interact. These conservative points‑to sets are used to partition and annotate memory, and a more precise (flow‑sensitive) points‑to pass will further tighten the SSA form when rerun.

Memory SSA solves the problem by treating the entire memory state as one SSA variable:

Insert memφ nodes at merge points to join memory versions.
Rename each alloca or store (definition) and each load (use) to a unique memory version.

The result is a sparse, flow‑sensitive def‑use graph for memory, enabling precise pointer analysis, aggressive optimizations, and improved call‑graph resolution.

Note: after you run your full flow‑sensitive points‑to solver, you can rebuild Memory SSA using the refined alias information to produce an even tighter def‑use graph.

Plain text algorithm

Build Memory SSA in two main phases:

Φ‑node placement (using FI points‑to info):
- Compute the CFG and its dominator tree.
- Using the flow‑insensitive points‑to results, find all DefBlocks containing a memory definition (alloca or store).
- Compute dominance frontiers DF(d) for each d ∈ DefBlocks.
- Let MemPhiBlocks be the union of those frontiers; in each such block insert a memφ node.
Renaming (version assignment):
- Initialize versionStack with the initial memory version M0 at the entry block.
- Traverse the dominator tree depth‑first:
  - If the block has a memφ, assign it a new version Mφ and push onto versionStack.
  - For each instruction in the block in order:
    - alloca or store: assign a fresh version Ms and push onto versionStack.
    - load: rewrite its pointer to the current top of versionStack.
  - Recurse on children in the dominator tree.
  - After recursion, restore versionStack to its prior state.

After a complete flow‑sensitive points‑to pass, you can re-run this construction to further reduce spurious φ‑nodes and version merges.

Pseudo‑code

// Phase 1: Φ‑node placement
computeCFG()
computeDominatorTree()
DefBlocks = { B | B contains alloca or store, per FI points-to }
MemPhiBlocks = ⋃_{d ∈ DefBlocks} DF(d)
for each B in MemPhiBlocks:
  insert memφ at start of B

// Phase 2: Renaming
versionStack = [ M0 ]    // initial version at entry
function renameBlock(B):
  saveStack = versionStack.copy()
  if B has memφ:
    Mφ = newVersion()
    B.memφ.version = Mφ
    versionStack.push(Mφ)
  for instr in B.instructions:
    if instr is alloca or store:
      Ms = newVersion()
      instr.version = Ms
      versionStack.push(Ms)
    else if instr is load:
      instr.version = versionStack.top()
  for child in dominatorTree.childrenOf(B):
    renameBlock(child)
  versionStack = saveStack

renameBlock(entryBlock)

// To refine: rerun after FS points-to to rebuild MemSSA with tighter defs/uses

Mathematical Formulation

\[ \mathrm{DefBlocks} = \{\,B \mid B \text{ contains a } \texttt{alloca}\text{ or }\texttt{store},\text{ per FI points-to}\} \] \[ \mathrm{MemPhiBlocks} = \bigcup_{d \in \mathrm{DefBlocks}} \mathrm{DF}(d) \] \[ \mathrm{InsertMemPhi}(B)\!:\; M_B \;=\; \phi\bigl(M_{p_1},M_{p_2},\dots,M_{p_k}\bigr) \quad\text{for }p_i\in\mathrm{preds}(B) \] \[ \mathrm{versionStack}\colon B\;\mapsto\;\text{stack of memory versions at entry to }B,\quad \mathrm{versionStack}(\mathrm{entry})=[M_0] \]

Notation:

FI points-to — flow‑insensitive points‑to sets used to guide where loads/stores may interact
CFG — control‑flow graph
DefBlocks — blocks containing a memory definition
DF(d) — dominance frontier of block d
MemPhiBlocks — blocks where a memφ is inserted
memφ — memory φ‑node merging incoming versions
alloca — stack allocation (memory definition)
store — memory write (definition)
load — memory read (use)
M0 — initial memory version at entry
Mφ, Ms — fresh versions for φ‑nodes and stores
preds(B) — predecessors of block B in the CFG
versionStack — stack of current memory versions during renaming