SSAtypical

SSA Variants

Minimal, semi-pruned and pruned SSA differ only in how many phis they place and how much analysis they pay for it. Loop-closed SSA and gated SSA are different in kind, and much rarer — one is a normalization LLVM actually uses, the other is mostly a research form.

The question

People talk about pruned SSA and loop-closed SSA — are these different representations, or just different phi-placement policies?

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

What the program is here

The same SSA IR under different placement policies. Minimal, semi-pruned and pruned SSA are the same representation containing different numbers of phis; loop-closed SSA adds a structural constraint about where values may be used relative to loops; gated SSA changes the representation itself by giving each phi a predicate, which makes it executable and therefore a different object. Each exists to answer "how much do I want to pay before construction to avoid work afterwards?"

What this phase may assume or do

All three placement policies produce correct SSA — they differ only in how many phis are present, and a superset of the necessary phis is always correct. Pruning is legal because a phi whose result is dead at the merge cannot be read, so deleting it removes nothing observable; establishing that requires a liveness analysis, and pruning without one deletes phis that a later block still reads. Loop-closed SSA is a normalization that adds phis rather than removing them, so it is trivially behavior-preserving; it is *maintainable* only if every pass that changes loop structure restores the invariant. Gated SSA is legal only where the predicate the gate carries genuinely determines the incoming edge, which requires the control dependence to be exact.

Key points

Minimal, semi-pruned and pruned SSA are the same representation with different phi counts, not different forms.
Minimal means minimal with respect to the dominance-frontier criterion, not the fewest phis a correct form could have.
Pruned SSA removes phis whose results are dead, and pays for a full liveness analysis before construction to do it.
Semi-pruned skips only the variables that are never live across a block boundary, which is cheap and catches the common case.
Loop-closed SSA adds phis rather than removing them, so that every use of a loop-defined value is rewritable in one place.
Gated SSA attaches predicates to merges, making them executable; it is a research form far more than a production one.
Braun-style on-the-fly construction produces pruned SSA as a side effect, with no separate liveness pass.

Three placement policies, one representation

typicalWhich policy a given compiler uses is an implementation detail that changes between versions, and published phi-count comparisons date from the 1990s on 1990s code. The stable claim is the ordering — maximal places the most, pruned the fewest — not any particular ratio. Braun-style on-the-fly construction sidesteps the question by only creating a phi when something actually asks for the variable's value, which naturally yields pruned SSA with no separate liveness pass.

The names sound like different forms and they are not. Minimal, semi-pruned and pruned SSA are the same IR with different phi counts, and the only question separating them is how much analysis you are willing to run before construction in order to avoid placing phis nobody will read.

Minimal SSA is what Cytron's algorithm produces: a phi at the iterated dominance frontier of every definition, with no reference to liveness. It is "minimal" with respect to that criterion — no phi is placed where the frontier does not require one — which is not the same as "the fewest phis a correct SSA form could have". [[ssa-construction]] produces this, and so does AtlasLang.

Pruned SSA additionally requires that the phi's result is live at the merge. That removes every phi for a variable that is dead after the join, and on real code it removes a substantial fraction of them. The price is a liveness analysis before construction, which is a full backward data-flow pass over the function.

Semi-pruned is the pragmatic middle, from Briggs et al.: skip the liveness analysis, and instead skip phis for variables that are *never live across a block boundary* — a purely local property computable in one cheap pass. It catches the common case, which is temporaries confined to a single block, without paying for full liveness.

What each policy pays and what it avoids

Policy	Phi placed when	Analysis needed first	Typical result
Maximal	Every variable at every merge	None	Correct, enormous, only used as a proof device
Minimal (Cytron)typical	Block is on the iterated dominance frontier of a definition	Dominators and dominance frontiers	The textbook default; includes dead and trivially-identical phis
Semi-pruned	As minimal, but only for variables live across some block boundary	One local pass to find block-local variables	Most of pruned's benefit for a fraction of the cost
Pruned	As minimal, but only where the result is live at the merge	Full liveness analysis	Fewest phis; costs a backward data-flow pass before construction

Loop-closed SSA is a different kind of thing

LCSSA is not a placement policy; it is an invariant. It requires that no value defined inside a loop is used outside it directly — instead, a single-operand phi is placed in the loop's exit block, and the outside use reads that. It *adds* phis rather than removing them.

The point is locality of rewriting. If a pass wants to change what a loop computes — unroll it, vectorize it, replace an induction variable — it has to update every use of the loop's values. Without LCSSA those uses are scattered across the rest of the function. With it, every escape route passes through one phi in the exit block, so the pass rewrites one operand instead of hunting.

This one is genuinely used: LLVM maintains LCSSA around its loop pass pipeline and has a pass that restores it. It is the variant a working engineer is most likely to actually encounter in a dump, as a puzzling phi [ %x, %loop.body ] with a single operand in the exit block — which is not a redundant phi, it is the invariant.

Closing a loop-defined value

Before

loop.body:
  %v = int %i + 1
  branch %c ? loop.body : after
after:
  print %v            ; direct use of a value defined inside the loop

After

loop.body:
  %v = int %i + 1
  branch %c ? loop.body : after
after:
  %v.lcssa = phi [ %v from loop.body ]
  print %v.lcssa      ; the only way out is through the phi

Legal only when

Always — the transformation adds a single-operand phi in a block that the value already reached, so the value read is identical. It is a normalization, not an optimization, and the only obligation is that the exit block is genuinely dominated by the definition.

Illegal when

Nothing about the rewrite is unsafe; what is unsafe is *relying* on the invariant after a pass has broken it. A transformation that adds a new exit edge or moves code out of the loop invalidates LCSSA, and a later loop pass that assumes it will rewrite the wrong operands. This is why LLVM has an explicit pass to restore the form rather than assuming it holds.

Gated SSA, briefly and honestly

Gated SSA replaces the phi with a construct that carries the *predicate* under which each operand is selected — a gamma node for a branch merge, and separate constructs for loop entry and exit. The result is executable: unlike a phi, a gated node can be evaluated, because it does not need to know which edge you arrived by, only the value of the condition.

That makes it attractive for demand-driven analysis, for program slicing, and for turning control dependence into data dependence — which is what a vectorizer wants when it if-converts a branch. It is the basis of program dependence graph work and of several research IRs, and it shows up in academic literature far more than in production compilers.

The honest summary is that it is rare. Mainstream compilers keep ordinary phis and compute control dependence separately when they need it, because gated SSA costs more to construct and to maintain, and the predicate has to be kept accurate through every CFG change. If you meet it, it will most likely be in a paper or a research compiler rather than in a toolchain you ship with.

The variants that are not placement policies

Form	What it changes	Why	How common
Loop-closed (LCSSA)implementation	Adds a single-operand phi in each loop exit block	Every use of a loop value is rewritable in one place	Common — LLVM maintains it around loop passes
Gated (GSA)	Phi carries the predicate that selects the operand	Makes merges executable and control dependence explicit	Rare — mostly research and program-slicing tools
Memory SSAimplementation	Adds SSA-style versions for memory state alongside values	Gives loads and stores the def-use edges registers already have	Present in LLVM as an analysis, not a change to the IR itself
SSI (static single information)	Adds sigma nodes at branches, splitting values by outcome	Lets a branch condition refine the facts on each path	Rare, though the idea survives as predicate-based range analysis

What to actually remember

Two of these matter in practice. Know that minimal SSA — the one every textbook and this module's construction lesson describes — contains phis that are dead and phis whose operands agree, and that this is by design and cleaned up later. And know that LCSSA exists, so that a single-operand phi in a loop exit block reads as a normalization rather than as a bug.

The rest is worth recognising and not worth memorising. If a dump surprises you, the question to ask is which policy or invariant the compiler is maintaining at that point in its pipeline, because the answer changes between passes within a single compilation.

How it works

The steps, in the order the compiler takes them.

For pruned SSA: run liveness first, then place a phi only where the frontier requires one *and* the variable is live-in at that block.
For semi-pruned: in one pass, mark every variable that is used in a block other than the one that defines it; place phis only for those.
For LCSSA: for each loop, for each value defined inside it and used outside, insert a single-operand phi in the exit block and rewrite the outside uses to read it.
For gated SSA: compute control dependence, then annotate each merge with the predicate that selects each operand, and maintain that predicate across every CFG change.
In all cases, run a verifier afterwards. The invariant being maintained is not visible in the IR, so only a checker can tell you whether a pass broke it.

How it breaks

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

Pruning is implemented with stale liveness information and a phi that something did read is removed. A use reads an undefined register, and on most targets that is whatever the last instruction left there — so the program often produces a plausible wrong number rather than crashing.
A pass adds an exit edge to a loop and does not restore LCSSA. A later loop transformation rewrites the operands it can see and misses the ones that escape directly, and the loop produces a stale value for the code after it.
An engineer sees a single-operand phi in an exit block, concludes it is redundant, and deletes it. Nothing breaks immediately; the next loop pass to run then rewrites the wrong uses.
Two passes in the same pipeline assume different variants — one expects pruned, one expects minimal — and the disagreement shows up as a phi count that changes depending on pass ordering, which makes the bug appear and disappear with unrelated flag changes.

When it helps

Pruned or semi-pruned SSA on large functions, where the phi count directly drives the cost of every subsequent pass.
LCSSA whenever a pipeline contains loop transformations, which is every optimizing compiler above the lowest tier.
Gated SSA for tools rather than compilers: program slicers, demand-driven analyses, and if-conversion for vectorization, where the predicate is the thing you actually want.

When it hurts

Paying for full liveness before construction in a fast tier, where the analysis costs more than the phis it would have avoided.
Maintaining LCSSA in a pipeline that rearranges control flow frequently, where the restoration pass runs repeatedly and the invariant is a recurring source of pass-ordering bugs.
Adopting gated SSA in a production compiler, where every CFG-modifying pass acquires an obligation to keep predicates accurate, and getting it wrong is a miscompilation rather than a missed optimization.

What it costs

Every one of these is paid by something.

Pruned SSA buys the fewest phis and therefore cheaper subsequent passes; it pays a full backward liveness analysis before construction, on every function, including the ones with almost no phis to save.
Semi-pruned buys most of that benefit for a single cheap local pass; it pays by leaving some dead phis behind, so a later cleanup is still worth running.
LCSSA buys locality — one place to rewrite every loop-escaping value; it pays extra phis, an extra pass to restore the invariant after anything breaks it, and dumps that confuse readers who do not know the convention.
Gated SSA buys executable merges and explicit control dependence; it pays a predicate to compute and maintain on every merge, a heavier construction, and a maintenance obligation on every pass that touches the CFG.

What else you could do

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

Place minimal SSA and clean up afterwards with copy propagation and dead code elimination. This is what LLVM and AtlasLang effectively do, and it keeps construction a pure function of the CFG — easier to test, at the cost of a population of useless phis in between.
Braun et al.'s on-the-fly construction, which never creates a phi for a value nobody asks for and removes trivial ones immediately. It produces pruned SSA with no liveness pass and no dominance computation, and is a good fit for JIT frontends where construction time is on the critical path.
Compute control dependence as a separate analysis instead of adopting gated SSA. You get the same information where you need it without changing the representation, which is why almost every production compiler does this.
Skip loop normalization and have each loop pass find its own escaping uses. Simpler pipeline, more work and more chances for error inside each pass — the reason LLVM chose the invariant instead.

See it for yourself

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

opt -passes=lcssa -S t.ll on a function with a loop whose value is used afterwards inserts the single-operand exit phis, so you can see the invariant being established.
opt -passes='print<memoryssa>' -disable-output t.ll prints LLVM's MemorySSA, which is the memory analogue of everything in this module and worth seeing once.
gcc -fdump-tree-ssa phi counts before and after loop passes show how many phis a normalization added and how many the optimizer removed.
Count phis in our SSA converter output — phisInserted in the pipeline result is minimal-SSA placement, so the trivially-identical and dead ones are visible in it.

Plausible wrong readings

Stated the way a confident engineer states them.

"Pruned SSA is a different IR." It is the same IR with fewer phis. Any pass that works on minimal SSA works on pruned SSA unchanged.
"Minimal SSA means the minimum possible number of phis." It means minimal under the dominance-frontier criterion. Pruned SSA has fewer, and is also correct.
"A phi with one operand is a bug." In a loop exit block it is almost certainly LCSSA, deliberately placed to keep every escaping use rewritable in one place.
"Gated SSA is what LLVM uses." LLVM uses ordinary phis and computes control dependence separately. Gated SSA is mostly a research form.

Misconceptions

The claim, and what is actually true.

Choosing a variant is a correctness decision.

All the placement policies are correct. It is a compile-time-versus-later-cleanup decision, and every choice ships in some production compiler.

LCSSA is an optimization.

It is a normalization that adds instructions. It exists to make other passes simpler and safer to write, not to make the program faster.

Pruned SSA is strictly better, so everyone should use it.

It requires a liveness analysis before construction. In a fast JIT tier that analysis can cost more than the phis it saves, which is why on-the-fly construction — which gets pruning for free — is the more interesting answer there.

Go deeper

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

overview

The SSA "variants" mostly differ in how many phi nodes get placed. Minimal places one wherever dominance says it might be needed; pruned skips the ones whose result is dead, at the cost of a liveness analysis first; semi-pruned is a cheap approximation of pruned. Loop-closed SSA is different — it adds phis in loop exit blocks so that loop passes have one place to rewrite.

practical

Two things to carry away. A phi whose operands are identical, or whose result is dead, is normal output from minimal construction and not evidence of a broken compiler. And a single-operand phi in a loop exit block is LCSSA doing its job; deleting it will not break anything today and will break a loop pass later.

advanced

The variants are best read as answers to one question — where in the pipeline do you pay for precision? Pruned SSA pays before construction with a liveness analysis. Minimal-plus-cleanup pays after, with copy propagation and dead code elimination. Braun-style construction pays neither, by making the query lazy: a phi is created only when a block is asked for a variable's value it does not have, and a phi that turns out trivial is removed the moment it is completed. That is why the same paper gives you pruning and trivial-phi removal without either analysis, and why it is the natural fit for a JIT where construction time is on the critical path. Gated SSA sits outside this axis entirely: it is not about how many phis but about what a phi *is*, and making it executable is what buys demand-driven evaluation and costs a maintenance obligation on every pass.

How much this depends on

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

typicalThe ordering — maximal places the most phis, pruned the fewest — is stable. Published ratios are not: they come from 1990s measurements on 1990s code, and which policy a given compiler uses changes between versions and between tiers within the same compiler.

implementationLCSSA as described is LLVM's: it maintains the invariant around its loop pass pipeline and has an explicit pass to restore it. GCC does not use the same normalization, and a single-operand phi in a GCC dump means something else. MemorySSA is likewise an LLVM analysis, not a general SSA variant.

simplifiedAtlasLang implements minimal SSA only. There is no pruning, no LCSSA and no gating in toSSA, so the phi counts our interactive reports are the unpruned ones — which is exactly why the trivially-identical phi in the construction lesson is visible at all.

If you were asked this in an interview

What is the difference between minimal and pruned SSA, and what does the difference cost?
You see a phi with a single operand in a loop exit block. What is it, and what happens if you delete it?
Why would a JIT prefer an on-the-fly SSA construction to Cytron's algorithm?

Connections

DSAdirected-graph dfs

Domains that do not exist yet

Programming Languages & Runtime Internals — Compile-time budgets inside a running VM
Which SSA variant a JIT tier can afford is decided by how much time it may spend while the program is waiting. That budget is a runtime-system property, and the tiering policy that sets it is owned there.