SSAtypical

Static Single Assignment

One rule, applied to a whole function: every value has exactly one defining instruction. `x = 1; x = x + 2` becomes `x1 = 1; x2 = x1 + 2`, and from that moment "which definition does this use read?" is answered by reading the operand name instead of by analysing the graph.

The question

What does SSA form actually change about an IR, and why is a rule about naming worth an entire pass?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

Three-address IR over virtual registers, carrying one extra invariant: every register is the destination of exactly one instruction in the text of the function. The question this form exists to answer is *which definition does this use read?* In ordinary three-address code that question requires a reaching-definitions analysis over the whole control-flow graph. In SSA the operand name is the answer, because there is only one instruction that could have written it.

What this phase may assume or do

Renaming preserves observable behavior because it changes the *identity* of values and never which value flows to which use: each use is rewritten to name the definition that already reached it on every path. The pass is entitled to assume the CFG is complete — every block terminated, every predecessor list accurate — and that the variables it promotes live in slots whose address never escapes. Promote a variable whose address was taken and the rename is a miscompilation: a store through the alias writes memory that no longer has a name, and the SSA value keeps the stale contents.

Key points

SSA is one invariant: every register is written by exactly one instruction in the function text.
"Static" means once in the program text, not once at run time. A definition in a loop body executes many times and is still SSA.
The payoff is that a use names its definition, which turns several whole-graph analyses into local lookups.
Promotion deletes memory traffic rather than renaming it, which is why register numbers come out with gaps.
The invariant is only maintainable if merges are made explicit, which is what phi nodes are for.
SSA is a property of the IR, not of the source language; a language with immutable bindings is not automatically in SSA, and a language full of reassignment converts to it fine.

The rule, on two lines

Take the smallest program in which a name means two different things. x = 1; x = x + 2; has one variable and two values. The second statement reads the first value and writes the second, and the name x is doing double duty — it is simultaneously a storage location and, at each point in the program, one particular value in that location.

SSA separates those two jobs by refusing the first one. Give every assignment its own name and the program stops being about storage: x1 is the number 1 and always was, x2 is the number 3 and always was, and the operand x1 in the second instruction names its definition directly. Nothing about what the program computes has changed. What changed is that a question which used to require an analysis is now answerable by reading.

The whole idea, on the smallest program that shows it

Three-address

x = 1
x = x + 2
print x

SSA

▸x1 = 1
▸x2 = x1 + 2
▸print x2

Read it asThe subscripts are not decoration. In the before column, deciding what the operand x in line 2 refers to means scanning backwards for the most recent assignment — and in a function with branches, backwards along every path. In the after column the operand *is* the reference. That is the entire trade being made, and everything else in this module is a consequence of it.

Static, not dynamic

simplifiedAtlasLang has no address-of operator, so every local is trivially promotable and toSSA promotes all of them unconditionally. A real mem2reg first proves that a variable's address never escapes; for the ones where it cannot, the loads and stores survive into SSA and the value stays in memory. In LLVM those two jobs are mem2reg and SROA, and code compiled at -O0 skips them entirely, which is why debug builds show every local in a stack slot.

The word doing the work in the name is static. It means "once in the text of the function", not "once while the program runs". A definition inside a loop body is a single static definition that executes on every iteration, producing a different value each time, and that is perfectly good SSA. Nothing about the form promises that a register holds one value for the lifetime of the process — it promises that one instruction is responsible for whatever the register holds.

This is where most first readings go wrong, and the loop below is the reason it matters. %5 is defined once and executes three times. %7 is defined once, by a phi, and takes a different value on each entry to the block. If SSA required one *dynamic* assignment it could not describe a loop at all, and would be useless as a compiler IR.

The same function after toSSA in src/compilers/sim/ir.ts

SSA

▸b0: ; entry
▸  %0 = param 0 ; k: int
▸  jump b1
▸b1: ; while.cond preds=b0,b2
▸  %7 = phi n [0 from b0, %5 from b2]
▸  %3 = bool %7 < %0
▸  branch %3 ? b2 : b3
▸b2: ; while.body preds=b1
▸  %5 = int %7 + 1
▸  jump b1
▸b3: ; while.exit preds=b1
▸  ret %7

Read it asThree things to notice. First, %5 has exactly one defining instruction and executes k times — that is what *static* single assignment means. Second, there are no load or store instructions left: promotion did not rename the memory traffic, it deleted it. Third, the register numbers have gaps, and the gaps are the deleted instructions. %1, %2, %4 and %6 were loads and stores against the slot @n; nothing renamed them, because nothing needed them.

The AtlasLang source for the listing below

1fn f(k: int): int {
2  let n = 0;
3  while (n < k) {
4    n = n + 1;
5  }
6  return n;
7}

One source variable n, one static definition of it per program point after promotion, and an unbounded number of dynamic assignments at run time.

What the invariant buys, question by question

typicalLLVM IR, GCC's GIMPLE after the ssa pass, HotSpot's C2 and V8's TurboFan are all SSA-based, so this is the mainstream middle-end design rather than an exotic one. It is not universal: CPython's bytecode compiler has no SSA phase at all and does correspondingly little optimization, and register-transfer-level backends such as GCC's RTL leave SSA before instruction selection.

It is worth being concrete about what changes, because "SSA makes optimization easier" is the kind of sentence that can be repeated without being understood. The invariant buys exactly one thing — a use names its definition — and every other benefit is that one thing spent in a different place.

Def-use chains, which a non-SSA compiler has to build and maintain as a side table, become the operand list itself. Constant propagation stops needing an analysis and becomes a lookup. Dead code becomes a use-count of zero. And the merge points, where several definitions genuinely do reach the same use, are forced into the open as [[phi-functions]] rather than being left implicit in the graph.

The same question, asked of both forms

Question about a use	Three-address code	SSA
Which definition does it read?	A reaching-definitions data-flow analysis over the CFG	The operand name. There is only one candidate.
Is that definition a constant?	Only if every reaching definition is the same constant	Look at the one defining instruction
Is this value dead?	Only if no path from here reaches a use — a liveness analysis	The use list is empty and the instruction is pure
Where are all the uses of this value?	Maintained by hand in a side table, invalidated by every rewrite	The def-use edges are the IR
Do two names hold the same value?	Requires copy propagation plus a proof neither was reassigned	Nothing is ever reassigned, so a copy is an alias forever
What happens at a merge?	Implicit. Several definitions reach; you must discover which.	Explicit. A phi node lists them, one per incoming edge.

How it works

The steps, in the order the compiler takes them.

Start from three-address IR in which local variables are load/store against named slots — that is what a frontend naturally emits.
Establish that the slot's address never escapes the function, so nothing outside the function's own instructions can observe its storage.
Compute dominance over the CFG, and place a phi for the variable at the iterated dominance frontier of its definitions.
Walk the dominator tree keeping a stack of the current definition per variable; rewrite each store to a fresh register and each load to the top of the stack.
Drop the slot. The variable no longer exists as storage; it exists as a set of values connected by def-use edges.
Every later pass then maintains the invariant itself: an optimization that would write an existing register instead creates a new one.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A variable whose address was taken is promoted anyway. The program computes with a stale value while the memory holds the new one, and the wrong answer shows up wherever the pointer is read — usually in a different function.
A pass rewrites an instruction in place and reuses a register that was already defined. Nothing errors; the verifier catches it if there is one, and if there is not, a later pass reads the wrong definition and a value silently changes.
A phi is placed at a block that is not actually a merge, and the operand for a predecessor that does not exist is left undefined. The symptom is a crash in the verifier, or garbage in a register on one path only.
The engineer reads a -O0 LLVM IR dump, sees alloca, load and store everywhere, and concludes LLVM is not SSA-based. It is; promotion simply has not run, so all the interesting values are still in memory and every optimization looks like it did nothing.

When it helps

Any middle-end doing more than peephole work. Constant propagation, dead code elimination, common subexpression elimination and global value numbering are all substantially simpler over SSA.
Writing a new optimization pass at all: the def-use edges you would otherwise have to build and invalidate come for free and stay correct across rewrites.
Reading someone else's IR dump. A value with a single definition can be traced to its origin by grep, which is not true of three-address code.

When it hurts

Very short compilation budgets. Constructing SSA costs a dominance computation and a full renaming walk, and a baseline JIT tier or an -O0 build often declines to pay it.
Memory-heavy code where nothing can be promoted. If the interesting values are all behind pointers, SSA over registers buys nothing without an alias analysis and a memory SSA on top of it.
Backends that need to think in machine registers. SSA has to be destroyed before allocation, and destroying it badly is its own family of bugs — see [[out-of-ssa]].

What it costs

Every one of these is paid by something.

Buys single-definition reasoning; pays a dominance computation and a renaming walk over the whole function on every compile, plus the memory for a phi at every merge of every promoted variable.
Buys free def-use chains; pays the discipline of maintaining the invariant in every subsequent pass. A pass that quietly writes an existing register corrupts the IR for every pass after it, and the failure surfaces far from the cause.
Buys optimization power; pays debuggability. The source variable n no longer exists as a thing with an address, so a debugger can only report where it is if the compiler emitted enough metadata to say which register held it in which range — see [[debug-information]].
Buys clarity at merges; pays for a whole extra phase to get back out, and out-of-SSA has three classic bugs that only appear on code the test suite did not have.

What else you could do

What a different compiler or language does instead, and when that is better.

Stay in three-address code and run a reaching-definitions analysis whenever a pass needs one. This is what many teaching compilers and older production compilers did; it is simpler to build and considerably more expensive per pass, because every pass pays for its own analysis.
Continuation-passing style, used by several functional-language compilers. It is provably equivalent in expressive power to SSA — the phi corresponds to a continuation parameter — and some implementations prefer it because the binding structure makes scoping explicit rather than implicit in dominance.
A sea-of-nodes graph, as in HotSpot's C2 and V8's TurboFan, where control and data dependencies live in one graph and instruction order is not fixed until scheduling. More freedom for the optimizer, considerably harder to debug and to print.
Skip the middle-end entirely. A tree-walking interpreter or a simple bytecode compiler such as CPython's never builds SSA, and the right comparison is not "worse code" but "a compiler that finishes in a millisecond".

See it for yourself

The flag, dump or tool that shows you this directly.

clang -S -emit-llvm -O0 -o - t.c shows the pre-promotion form, with an alloca per local. Run it again with -O1 and diff: the allocas disappear and the values become SSA registers. That diff *is* mem2reg.
opt -passes=mem2reg -S t.ll runs promotion alone on unoptimized IR, which is the cleanest way to see what the pass does without any other transformation confusing the picture.
gcc -fdump-tree-ssa writes a .ssa dump of GIMPLE in SSA form, where the renamed variables keep their source names with a version suffix — n_3, n_5 — which is far more readable than numbered registers.
Our SSA converter at /compilers/ssa runs toSSA from src/compilers/sim/ir.ts on whatever AtlasLang you type, and shows the pre-SSA and post-SSA functions side by side.

Plausible wrong readings

Stated the way a confident engineer states them.

"SSA means the variable is assigned once, so the language must be immutable." No — the *IR value* is written once. The source variable is reassigned as often as the programmer wrote it; each reassignment simply gets its own name.
"A loop breaks SSA, because the induction variable changes every iteration." It changes dynamically, which SSA permits. What a loop actually needs is a phi at the header, and that is a notation, not an exception.
"If I see store in the IR dump, it is not SSA." Stores to memory are perfectly legal in SSA; the invariant constrains virtual registers, not memory. What promotion removes is stores to *promotable slots*.
"SSA is an optimization." It is a representation. It performs no transformation on its own — every listing in this lesson computes exactly what the input computed.

Misconceptions

The claim, and what is actually true.

SSA and immutability are the same idea.

They are related but not the same. Immutability is a source-language property; SSA is an IR invariant that a compiler imposes on any language, including ones where every variable is mutable.

Converting to SSA makes the program bigger, so it must be slower.

It adds phi nodes and deletes loads and stores; on promotable code it is normally a net reduction in instructions. And phis are not executed at all — they are erased when SSA is destroyed.

You need SSA to optimize.

You need reaching-definitions information to optimize. SSA is a way of having it permanently instead of recomputing it. Compilers optimized for decades without it, more slowly.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

SSA is a naming discipline for a compiler's internal representation: every value gets its own name and no name is ever reused. x = 1; x = x + 2 becomes x1 = 1; x2 = x1 + 2. The point is that a use now names its definition, so questions like "is this a constant" and "is this dead" stop needing an analysis.

practical

When you read an optimized IR dump, the single-definition rule is what makes it readable: pick any operand, search for it once, and you have found where it came from. When you read an unoptimized dump and see alloca/load/store everywhere, promotion has not run and almost nothing else will have either. If you are writing a pass, the rule you must not break is that you never assign to an existing register — you create a new one and rewrite uses. Most SSA-corruption bugs are one in-place mutation that seemed harmless.

advanced

The deep reason SSA works is that dominance and definition coincide. In a well-formed SSA function, the definition of a value dominates every use of it, and that single structural fact is what licenses code motion: an instruction can be hoisted anywhere that is still dominated by all its operands' definitions and still dominates all its uses. It is also what makes phi nodes necessary rather than convenient — at a merge, no single definition dominates the use, so the form needs a construct that says "one of these, depending on the edge". Everything else in this module follows from that sentence.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalLLVM, GCC (GIMPLE), HotSpot C2 and TurboFan are all SSA-based middle-ends, so this is the mainstream design. It is not universal: CPython has no SSA phase, and GCC leaves SSA before its RTL backend runs, so the same compiler is SSA in one half and not in the other.

implementationThe listings are AtlasLang output from toSSA in src/compilers/sim/ir.ts at this commit. Register numbering, block ids and the decision to delete rather than rename loads are all ours; LLVM numbers differently and GCC keeps source names with version suffixes.

simplifiedOur promotion is unconditional because AtlasLang has no way to take an address. A real compiler promotes only slots it has proved do not escape, and the ones it cannot prove stay in memory — which is the single biggest difference between our SSA and the SSA of a C compiler.

If you were asked this in an interview

Convert this five-line function to SSA on the whiteboard, then tell me which blocks needed a phi and why.
What does the word "static" rule out, and what does it deliberately allow?
You are looking at an LLVM IR dump full of alloca and load. What does that tell you about which passes have run?

Connections

DSAdfs directed-graph

Domains that do not exist yet

Programming Languages & Runtime Internals — Immutable bindings and persistent data structures as a language feature
SSA is the same idea applied to a compiler's internal names rather than to the programmer's. The reasons it helps a compiler are the reasons immutability helps a reader, but the mechanism and the costs are entirely different, and the language-level version is owned there.