SSAtypical

Why SSA Helps

Every use has exactly one reaching definition. Cash that one fact in four places: constant propagation needs no analysis, dead code is a use count, def-use chains are the IR itself, and copy propagation cannot be wrong because nothing is ever reassigned.

The question

Which specific analyses get cheaper under SSA, and by how much — or is "it makes optimization easier" all there is to it?

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

What the program is here

SSA IR viewed as a graph rather than a listing: the def-use edges implied by the operand names. In this view the instruction list is incidental and the real structure is a directed graph from each definition to its uses, in which a value with no outgoing edges is dead and a value whose defining instruction is a literal is constant everywhere. The representation exists to answer optimization queries by traversal instead of by fixed-point analysis.

What this phase may assume or do

Each of the four wins below rests on a precondition SSA construction has already established, and each is illegal without it. Constant propagation is legal because the single definition is the *only* definition — outside SSA it requires proving no other definition reaches. Dead code elimination is legal only for instructions with no side effect and no possibility of trapping; the empty use list is necessary, never sufficient. Copy propagation is legal because the source of a copy cannot be reassigned between the copy and the use, which is a theorem in SSA and an obligation elsewhere. And every one of them still requires that the value's definition dominates the use, which well-formed SSA guarantees.

Key points

The single fact SSA provides is that a use names its definition; every benefit is that fact spent somewhere.
Constant propagation needs no reaching-definitions analysis, because there is only one reaching definition by construction.
Dead code becomes an empty use list — necessary but never sufficient, because side-effecting instructions must survive regardless.
Copy propagation loses its correctness obligation entirely, because the source of a copy can never be reassigned.
Def-use chains are the IR rather than a side table, so they cannot go stale across rewrites.
Sparse analyses — propagating along def-use edges rather than over every program point — are only formulable because those edges exist.
SSA generates no faster code by itself; it makes analyses cheap enough that a compiler can afford to run more of them.

One fact, spent four ways

The claim "SSA makes optimization easier" is true and almost useless, because it does not say what changed. What changed is one thing: a use names its definition. Everything else is that fact spent somewhere. It is worth going through the four main places explicitly, because each of them is a data-flow analysis that stops being needed.

The general shape is always the same. Outside SSA, a question about a value is a question about all the paths that reach it, so it needs a fixed-point analysis over the CFG — which costs time, must be recomputed after every transformation that changes the graph, and has to be conservative wherever it cannot prove something. Inside SSA the same question is answered by following one edge.

What each optimization needs, with and without SSA

Optimization	Without SSA	With SSA	What is saved
Constant propagation	Reaching definitions over the whole CFG; propagate only if every reaching definition is the same literal	Look at the operand's single defining instruction	A whole forward data-flow analysis, recomputed after every change
Dead code elimination	Liveness analysis; a definition is dead if no path from it reaches a use	The use list is empty	A whole backward data-flow analysis
Copy propagation	Prove the source is not reassigned on any path between copy and use	Nothing is ever reassigned, so replace unconditionally	The proof obligation disappears entirely
Def-use chains	A side table, built by analysis and invalidated by every rewrite	The operand names are the edges	Building and maintaining the table
Value numbering	Local to a block, or global with an availability analysis	Two instructions with the same opcode and same operand names compute the same value	Availability reasoning for the register case

Constant propagation without an analysis

Take let x = 5; let y = x + 3;. To propagate the 5 into the addition, a non-SSA compiler must establish that no other assignment to x reaches that use — which means a reaching-definitions analysis over the function, because an assignment in a loop or on a branch could reach it too. In SSA the operand is %0, %0 is defined by exactly one instruction, and that instruction is const 5. There is nothing to analyse.

Our own optimizer states the legality condition in exactly these terms: *the value has exactly one definition and that definition is a literal — in SSA this is guaranteed by construction, which is most of why SSA exists.* The illegal case it names is the non-SSA one: the variable is reassigned on another path and two definitions reach the same use.

This is not the same as constant folding. Folding evaluates an operation whose operands are already literals; propagation is what makes them literals in the first place. Under SSA the two together become a single fixed-point walk of the def-use graph, which is what [[constant-propagation]] builds on and what SCCP extends with reachability.

Propagation into a use

Before

%0 = const 5
%1 = const 3
%2 = int %0 + %1

After

%2 = int 5 + 3

Legal only when

The operand has exactly one definition and that definition is a literal. In SSA that is guaranteed by the form itself, so the transformation needs no supporting analysis. The defining instruction may then be deleted if nothing else uses it and it has no side effect.

Illegal when

The IR is not in SSA and %0 is also assigned on another path that reaches this instruction — for example inside a loop whose back edge reaches the use. Then two definitions reach and neither may be substituted. This is exactly the case a reaching-definitions analysis exists to rule out, and it is why the same rewrite is dangerous to apply by hand to three-address code.

Dead code as a use count

typicalMainstream optimizers implement dead code elimination this way over SSA — LLVM's ADCE and DCE both work from use lists. What counts as an unremovable effect differs by language and by IR: LLVM treats a readnone nounwind call as removable when its result is unused, while a C compiler must keep a volatile load even though nothing reads the value, because the language defines the access itself as observable.

A definition is dead when nothing reads its result. Outside SSA that is a liveness question — is there a path from here to a use? — and liveness is a backward fixed-point analysis over the whole graph. In SSA the definition has a use list, and the question is whether the list is empty.

The important caution is that an empty use list is *necessary but not sufficient*. An instruction with a side effect must survive even with no users: a call, a store, a print, or anything that can trap. Our optimizer's legality note is blunt about it — removing an effectful instruction because its value is unused is a miscompilation, not an optimization. SSA gives you the use count cheaply; it tells you nothing about effects, and the effect check is where the real risk lives.

Note also that this is a worklist, not a single sweep. Deleting an instruction removes its operands' uses, which can make *them* dead. Under SSA that cascade is a queue over def-use edges rather than a re-run of the liveness analysis.

Copy propagation cannot be wrong

Copy propagation replaces a use of a copied value with the original. The classic hazard on three-address code is that the source is reassigned between the copy and the use, so the substitution reads a newer value than the copy captured. That hazard cannot exist in SSA: the source has one definition and is never written again. Our optimizer's condition says exactly that — *in SSA the source cannot have been modified, because nothing is ever modified.*

This is also what cleans up after construction. A phi whose operands are all the same value is, in effect, a copy, and copy propagation replaces its uses with that value and deletes it. The trivially-identical phis that [[ssa-construction]] deliberately leaves behind are removed here, in a pass whose correctness argument is one sentence long.

The def-use graph is free, and stays correct

The subtler win is maintenance. A non-SSA compiler that wants def-use chains has to build them with an analysis and then keep them accurate as passes rewrite instructions — and a stale chain is worse than no chain, because the pass that reads it will not notice. In SSA the chain is the operand list: rewriting an operand *is* rewriting the edge, so the graph cannot go stale.

That, in turn, is what makes *sparse* analyses practical. A dense data-flow analysis computes a fact at every program point; a sparse one propagates facts along def-use edges and only revisits a value when one of its inputs changes. Sparse conditional constant propagation is the well-known example, and it is only formulable because the edges exist. [[fixed-point-iteration]] covers what the sparse version changes about the cost; the point here is that SSA is what made the edges available.

One honest deduction from all of this: SSA does not make any *particular* program faster. It makes analyses cheaper, which makes it affordable to run more of them, which is where the speed comes from. A compiler that ran all the same analyses on three-address code would generate the same code, more slowly.

How it works

The steps, in the order the compiler takes them.

Maintain, for each value, the list of instructions that name it as an operand — in most implementations this is a linked list threaded through the operand slots themselves.
For constant propagation: for each use, look at the single defining instruction; if it is a literal, substitute it and queue the users of the result.
For dead code elimination: seed a worklist with every instruction whose use list is empty, delete those with no side effects, and enqueue the operands whose use lists just shrank.
For copy propagation: for each copy or single-valued phi, replace every use of the destination with the source and delete the instruction.
For sparse analyses: attach a lattice value to each SSA value, propagate along def-use edges, and revisit a value only when an input changes.
After any transformation, the def-use edges are already correct, because rewriting an operand is what changed them.

How it breaks

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

Dead code elimination is implemented as "no uses, delete it" without an effect check, and a print, a store or a call disappears. The program runs and produces no output, or silently skips a side effect, and the cause is nowhere near the symptom.
A pass rewrites an instruction in place and reuses an existing register, breaking the single-definition invariant. Every later analysis that trusted the invariant now draws a wrong conclusion, and the wrong value appears several passes downstream.
A transformation adds a CFG edge and does not update the phis in the target. The def-use graph is now inconsistent with the control-flow graph, and the value taken on the new edge is whatever was in the register.
An engineer reads a -O1 dump, sees the constant already folded, and concludes the source-level expression was free. It was free *here*; the same expression behind a call that could not be inlined is not, and the dump does not say so.

When it helps

Compilers that run many passes. The savings compound: each pass that would have needed its own reaching-definitions or liveness analysis simply does not.
Interprocedural and whole-program work, where dense analyses over a large function are the compile-time bottleneck and sparse propagation over def-use edges is dramatically cheaper.
Building a new optimization. The def-use graph being free means a useful pass is often thirty lines, which changes what is worth attempting.

When it hurts

Memory. None of this applies to values behind pointers; a load and a store have no def-use edge without a memory-SSA layer and an alias analysis, and that is where the hard optimizations actually live.
Any analysis that genuinely is about program *points* rather than about values — available expressions over memory, for instance — still needs a dense data-flow framework. SSA sparsifies value questions, not all questions.
Very short pipelines, where the construction cost is not amortised over enough passes to pay for itself.

What it costs

Every one of these is paid by something.

Cheap analyses buy the ability to run more passes; they pay the construction cost up front and the destruction cost at the end, on every function, including the ones no pass will improve.
Free def-use edges buy correctness-by-construction for the graph; they pay a strict discipline in every pass — one in-place mutation that reuses a register silently invalidates every conclusion drawn afterwards, and the failure appears far from the cause.
Sparse propagation buys speed over dense analysis; it pays generality, because a fact that is not attached to a value has nowhere to live and needs the dense framework anyway.
Aggressive use of these cheap analyses buys smaller, faster code; it pays debuggability, because the more values are folded away, the fewer source variables have a location to report — see [[debugging-optimized-code]].

What else you could do

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

Run the classical dense analyses on three-address code and re-run them after each transformation. Simpler to implement and correct; the cost is quadratic-feeling compile times on large functions and a strong incentive to run fewer passes.
Compute def-use chains explicitly as a side table over non-SSA IR and invalidate them carefully. Workable, and the invalidation discipline is the part that goes wrong — which is exactly the discipline SSA makes structural.
Use a sea-of-nodes graph, where data and control dependencies live in one structure and even the instruction order is not fixed. Strictly more freedom for the optimizer, and considerably harder to print, diff and debug — a real trade that HotSpot's C2 accepted and most static compilers did not.
Do less optimization. A baseline JIT tier or a debug build skips all of this deliberately, because compile time and faithful debugging are worth more than generated-code quality at that tier.

See it for yourself

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

opt -passes=sccp -S t.ll runs sparse conditional constant propagation alone, so you can see how far constants travel with no other pass helping.
opt -passes=dce -S t.ll and -passes=adce show the difference between plain dead code elimination and the aggressive version that assumes instructions are dead until proven live.
clang -S -emit-llvm -O1 versus -O0 on the same file: the diff is almost entirely the four things in this lesson, applied after mem2reg.
Our pass-manager interactive lets you toggle constant propagation, copy propagation and dead code elimination individually over the real AtlasLang optimizer and watch the instruction count change.

Plausible wrong readings

Stated the way a confident engineer states them.

"SSA makes the code faster." SSA makes analyses cheaper. The code gets faster because the compiler can afford more passes, which is a different causal chain and matters when you are deciding whether to pay for construction.
"If there are no uses, it can be deleted." Only if it also has no side effect and cannot trap. This is the single most dangerous simplification in the lesson.
"SSA gives you alias analysis for free." It gives you nothing at all about memory. Loads and stores have no def-use edges without a separate memory representation.
"Def-use chains and use-def chains are the same thing." They are the two directions, and SSA makes the use-def direction trivial — one definition — while the def-use direction still needs a list.

Misconceptions

The claim, and what is actually true.

SSA is itself an optimization.

It is a representation. It computes exactly what the input computed; the optimizations run afterwards and are what change the program.

Under SSA you no longer need data-flow analysis.

You no longer need it for questions about *values*. Questions about program points — availability of an expression over memory, for instance — still need the full framework.

An instruction with no users is dead.

Only if it is also pure. Effects are invisible in the use graph, and this is the standard way an optimizer written from this lesson miscompiles.

Go deeper

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

overview

Because each use in SSA names exactly one definition, questions that used to need a whole-function analysis become one lookup. Is this a constant? Look at the defining instruction. Is this dead? Check whether anything uses it. Can I replace this copy? Yes, unconditionally, because nothing is ever reassigned.

practical

When you write a pass over SSA, the two habits that matter are: never assign to an existing value — create a new one and rewrite uses — and never delete on use count alone without an effect check. Almost every optimizer bug of the "my print statement disappeared" kind is the second. The first is worse because it does not fail immediately; it corrupts the invariant that every pass after you is relying on.

advanced

The deeper structural claim is that SSA converts *dense* analyses into *sparse* ones. A dense analysis computes a fact at every program point and costs time proportional to points times facts; a sparse analysis attaches facts to values and propagates along def-use edges, costing time proportional to edges times lattice height. Wegman and Zadeck's sparse conditional constant propagation is the canonical demonstration, and it does something the dense version cannot: it tracks reachability at the same time, so a branch whose condition is known constant never propagates anything along the untaken edge, and code that a separate unreachable-block pass would need a second run to find is dead in the first pass. That interaction — one analysis being strictly stronger than the composition of two — is the strongest single argument for the whole representation.

How much this depends on

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

typicalThe four wins described are how mainstream SSA middle-ends are actually built, including LLVM and GCC. The magnitudes are not transferable: how much any of them gains depends on the language and the code, and a program dominated by pointer-heavy memory traffic can see almost none of it because none of the interesting values were promotable.

implementationThe legality conditions quoted are from PASSES in src/compilers/sim/optimize.ts, which our pass-manager interactive drives. LLVM's versions carry many more preconditions — overflow flags, fast-math flags, atomic ordering — each of which blocks a rewrite our simplified IR never has to consider.

simplifiedAtlasLang has no pointers, no floating point and no threads, so effects reduce to print, call and division by zero. In C or Rust the effect question is far harder, and it is the effect question rather than the use count that decides whether dead code elimination is legal.

If you were asked this in an interview

Name three analyses that get cheaper under SSA and say precisely what each of them no longer has to compute.
An instruction has no users. Under what conditions may you delete it?
Why is copy propagation safe without any supporting analysis in SSA but not in three-address code?
Does SSA make the generated code faster? Answer carefully.

Connections

DSAdirected-graph topological-sort hash-table

Performancejit-and-warmup

Domains that do not exist yet

Programming Languages & Runtime Internals — What the optimized code costs at run time — allocation, dispatch, cache behavior
This lesson argues about the cost of the *analyses*, which is compile time. Whether the resulting code is actually faster on a real machine is a measurement question, and the measuring is owned by the runtime and performance domains.