Step 4 — Memory model: alloca / load / store

LLVM IR is in SSA, which means every register is assigned exactly once. But MiniLang variables — let x = 0; x = x + 1; — are not single-assignment. How does a frontend bridge that gap?

The alloca trick

You don't emit SSA directly. You emit memory:

%x.addr = alloca i64           ; reserve a stack slot
store i64 0, i64* %x.addr       ; x = 0

%v1 = load  i64, i64* %x.addr   ; read x
%v2 = add   i64 %v1, 1          ; v1 + 1
store i64 %v2, i64* %x.addr     ; x = ...

Every named local becomes an alloca in the entry block, every read becomes a load, every write a store. The SSA registers (%v1, %v2) are short-lived temporaries that hold loaded values.

The IR you produce this way is trivially SSA-valid (every register defined once), but it's pessimistic — it leaves variables in memory when they could live in registers.

mem2reg does the rest

LLVM's mem2reg pass (technically PromoteMemoryToRegister) scans for allocas that are only loaded from and stored to (no address taken, no escape) and promotes them into proper SSA values with phi nodes at join points.

opt -O2  ← runs mem2reg first, then everything else

After mem2reg:

L0:
  %x.1 = ...
  br label %L1
L1:
  %x.2 = phi i64 [%x.1, %L0], [%x.3, %L1]
  %x.3 = add i64 %x.2, 1
  br label %L1

The frontend never had to compute a dominator tree, never had to insert phi nodes, never had to think about variable renaming. The optimiser did it.

This is the design decision that makes Clang's frontend maintainable. C-style mutable locals would otherwise force the frontend to implement Cytron-style SSA construction.

When does alloca go where?

Always in the entry block. This is critical for performance. alloca in a non-entry block creates a dynamic stack allocation (real sub $rsp, size at runtime); in the entry block it's collapsed by the backend into a single stack-frame reservation.

The entry block is also the only place mem2reg will consider promoting. An alloca in a loop body stays in memory forever.

Our emitter respects this:

// 1. Emit all alloca instructions first (in the implicit entry block).
for (const auto& name : localsWritten) {
    out << "  %" << esc(name) << ".addr = alloca i64\n";
}
// 2. Then branch to the first IR block of the function body.
out << "  br label %L" << fn.blocks[0].id << "\n";

Function parameters

Parameters arrive as SSA registers (%arg0, %arg1). To let them be reassigned, we immediately spill them into an alloca:

define i64 @add(i64 %arg0, i64 %arg1) {
  %a.addr = alloca i64
  %b.addr = alloca i64
  store i64 %arg0, i64* %a.addr
  store i64 %arg1, i64* %b.addr
  ...
}

Again, mem2reg cleans this up after the optimiser runs.

Globals

Globals are top-level @-prefixed pointers:

@x = global i64 0

The variable @x is itself an i64*; you load i64, i64* @x to read and store i64 N, i64* @x to write. This is unlike alloca (which returns a pointer to a stack slot); @x's pointer is the address of the global's storage.

Globals are not promoted by mem2reg — that pass operates only on stack allocas. Promoting a global to register is a different optimisation (sometimes called "globalopt" or "internalize + mem2reg") and requires whole-module analysis.

Pointer typing — old vs new

In LLVM ≤ 14, pointers carry the pointee type (i64*). In LLVM ≥ 15, the opaque-pointer revolution made all pointers just ptr, and the instruction carries the type (load i64, ptr %x.addr). Our text-form emitter uses the older typed-pointer form because it's self-documenting; modern lli accepts either.