Leaving SSA
Phis become copies at the end of their predecessors — and that sentence hides three classic miscompilations: the swap problem, the lost copy, and critical edges with nowhere to put the copies. AtlasLang breaks copy cycles by rescuing the value about to be *clobbered*, and the sim test proves it by simulating the moves.
How do phi nodes turn into real instructions, and why does doing the obvious thing produce wrong code?
SSA IR on the way out, becoming machine-shaped IR over virtual registers with no phis. The intermediate object that matters is the *parallel copy*: for each edge into a merge block, the set of all that block's phi assignments, taken simultaneously. It exists to answer the question the phi deferred — where, physically, does the value get moved, and in what order do the moves happen so that the simultaneity is preserved.
Replacing a phi with copies preserves observable behavior only if three conditions hold. Each copy is placed on the edge it belongs to — at the end of the predecessor when the predecessor has one successor, and on a split edge otherwise. All phis at the top of a block are sequenced as one parallel copy per edge, so that no destination is written before every read of it has happened, with cycles broken by a temporary. And the phi's destination must not be live along any other path out of the predecessor where the copy is placed. Violate the first and a copy runs on a path that never entered the merge; violate the second and a swap turns into a duplication; violate the third and a value the other path still needed is destroyed.
Key points
- A phi becomes copies on its incoming edges; for a predecessor with one successor, that means at the end of the predecessor.
- All phis at the top of a block form one parallel copy per edge and must be sequenced, not emitted in listing order.
- A move is safe to emit when nothing left to emit still reads its destination; when everything left is a cycle, break it with a temporary.
- Break the cycle by rescuing the value about to be clobbered — the victim's destination. Rescuing the source produces a duplication instead of a swap.
- The lost-copy problem: a back-edge copy placed in a block that also carries the exit branch destroys the phi result the code after the loop still needs.
- A critical edge has no block to hold its copies; splitting it is the standard fix and also fixes the lost copy.
- Most of the resulting copies are removed by the allocator's coalescing; cycle-breaking temporaries are the ones that survive.
The straightforward case, and what it hides
A phi says "on the edge from b1 this value is 1". The natural place to make that true is at the end of b1, and for a predecessor with a single successor that is exactly right. Below is the real translation of the diamond from [[phi-functions]]: two copies, one per arm, and the phi is gone.
That is the entire idea, and it works for the majority of phis in real code. The three hazards in this lesson are the minority cases, and they all fail the same way — silently, with a wrong value, on a path the tests did not take.
outOfSSA output — two copies replace one phib1: ; if.then preds=b0 jump b3 b2: ; if.else preds=b0 jump b3 b3: ; if.join preds=b1,b2 %3 = phi x [1 from b1, 2 from b2] print %3
▸b1: ; if.then preds=b0▸ %3 = copy 1▸ jump b3▸b2: ; if.else preds=b0▸ %3 = copy 2▸ jump b3▸b3: ; if.join preds=b1,b2▸ print %3
Read it as%3 is now assigned twice, which is no longer SSA — and that is the point. The form has been destroyed on purpose, because a register allocator needs to think about one storage location receiving different values on different paths, which is precisely what SSA refused to express.
Hazard one: the swap problem
outOfSSA in src/compilers/sim/ir.ts on the AtlasLang source shown. LLVM does the same job in PHIElimination followed by a register coalescer, and in practice most of these copies are then coalesced away; the cycle-breaking temporary is the one that usually survives, because a cycle is exactly the case coalescing cannot resolve.All the phis at the top of one block take effect *simultaneously*, reading the predecessor's state as it was on the edge. Emit them as copies in listing order and that simultaneity is lost. The pathological case is a loop that swaps two variables, which is a program anyone can write in one line.
Below is the real SSA for exactly that loop. Look at the header: %11 = phi y [..., %12 from b2] and %12 = phi x [..., %11 from b2]. On the back edge these two form a cycle. Emitting them in order gives %11 = copy %12 followed by %12 = copy %11, and the second copy reads the register the first one just overwrote — so both end up holding the old %12, and the loop stops swapping and starts duplicating.
The fix is to treat the whole set as one parallel copy and *sequence* it: emit a move only when nothing still left to emit needs to read its destination, and when everything remaining is a cycle, break it with a temporary. That is sequenceParallelCopies in src/compilers/sim/ir.ts, and it lives in the IR layer rather than the backend because the same problem occurs in three places — resolving phis, shuffling call arguments into ABI registers, and reconciling register assignments across an edge.
b1: ; while.cond preds=b0,b2 %9 = phi t [0 from b0, %12 from b2] %10 = phi i [0 from b0, %6 from b2] %11 = phi y [2 from b0, %12 from b2] %12 = phi x [1 from b0, %11 from b2] %1 = bool %10 < 3 branch %1 ? b2 : b3
▸b2: ; while.body preds=b1▸ %6 = int %10 + 1▸ %9 = copy %12 ; nothing reads %9, safe to emit first▸ %10 = copy %6 ; nothing reads %10 either▸ %13 = copy %11 ; rescue the value about to be clobbered▸ %11 = copy %12▸ %12 = copy %13▸ jump b1
Read it asRead the last three lines as a unit. The cycle is %11 <- %12 and %12 <- %11. The sequencer picks a victim — the move %11 <- %12 — and saves the victim's destination %11 into a fresh %13 before overwriting it. Then it rewrites every remaining move that read %11 to read %13 instead, and emits the rest normally. Five moves, one temporary, and the swap survives.
1let x = 1;2let y = 2;3let i = 0;4while (i < 3) {5 let t = x;6 x = y;7 y = t;8 i = i + 1;9}10print(x);11print(y);Rescue the destination, not the source
The cycle-breaking step has a subtly wrong twin that is worth spelling out, because it looks equally reasonable and is a genuine miscompilation. The temptation is to save the *source* of the move — "copy the value somewhere safe before it gets overwritten" — and it produces the wrong answer.
Work it through on a swap of a and b, with the parallel copy a <- b, b <- a. Saving the source gives tmp <- b; a <- tmp; b <- a. The first two moves put b's value in a. The third then reads a — which has already been overwritten — so b receives b's own value, and both registers end up holding the original b. The temporary was allocated, and it protected the wrong thing.
Rescuing the destination gives tmp <- a; a <- b; b <- tmp. The value at risk is the one that is about to be *clobbered*, because after the clobber it is unrecoverable; the source is still readable right up until something overwrites it, and the sequencing rule already guarantees nothing does. So the rule is: save what you are about to destroy, then rewrite every remaining reader of that location to read the temporary instead. That is the third and fourth lines of sequenceParallelCopies, and the comment in the source says so in as many words.
This is the kind of claim that should not be taken on trust from prose, and in this repository it is not. scripts/compilers-sim.test.ts verifies the sequencer by *simulating* the emitted move list against an initial register state and checking the final state — deliberately not by comparing against an expected sequence, because a hand-written expectation can itself encode the wrong algorithm and pass.
parallel: a <- b b <- a
tmp <- a ; rescue the DESTINATION of the victim move a <- b b <- tmp
Emitting a move is legal once no remaining move needs to read its destination. When every remaining move is part of a cycle, that condition can never be reached, so one move is chosen as the victim, its destination is copied to a fresh temporary first, and every remaining move that read that destination is rewritten to read the temporary. One temporary per cycle is sufficient, and the temporary must not be a register live across this point.
The temporary rescues the victim's *source* instead: tmp <- b; a <- tmp; b <- a leaves both registers holding the original b, because the last move reads an a that has already been overwritten. Also illegal is emitting the moves in listing order with no sequencing at all, which is the same bug without the wasted temporary. Both compile cleanly and produce a program that quietly does not swap.
Hazard two: the lost copy
The second hazard needs the phi's *result* to still be live after the loop. Take a loop whose header phi is x2 = phi(x1, x3) with x3 = x2 + 1 in the body, and a use of x2 after the loop. Naive destruction puts x2 <- x3 at the end of the block that also carries the exit branch. On the final iteration that copy runs, overwrites x2 with the value for the iteration that never happens, and the code after the loop reads a value one step too far along.
It is called the lost-copy problem because a copy that a careful translation would have kept — a copy of the phi result to a separate register for the outside use — has been lost. It becomes much more likely after copy propagation and coalescing, which is why Briggs, Cooper, Harvey and Simpson wrote it up as a hazard of *practical* SSA destruction rather than of the textbook algorithm: the textbook version is safe, and the version that runs after the optimizer has extended live ranges is not.
There are two standard repairs and they are the same repair viewed twice. Split the edge, so the back-edge copies live in a block that only the back edge reaches and the exit path never executes them. Or keep a temporary holding the phi result's value before the back-edge copy overwrites it, and rewrite the out-of-loop use to read the temporary. Edge splitting is the more common choice because it also fixes the third hazard.
AtlasLang does not hit this one, and it is worth saying why rather than claiming immunity. Our while lowering puts the exit branch in the *header* and gives the latch block a single successor, so the back-edge copies land in a block the exit path cannot reach. That is a property of our lowering, not a property of the algorithm — an IR where the branch and the back edge share a block is exposed.
- prepreheaderentry
x1 = 1
- headloop header↺ loop header
x2 = phi(x1 from pre, x3 from body)
x2 is also used after the loop. - bodybody + latchlatch
x3 = x2 + 1 branch cond ? head : exit
Two successors. A copy `x2 <- x3` placed here runs on the exit path too. - exitexit
use x2
Reads the value the stray copy just destroyed.
- pre→head
- head→body
- body→head
- body→exit
- preidompre(entry)
- headidompre
- bodyidomhead
- exitidombody
Read it asThe damage comes from body having two successors while carrying a copy that belongs to only one of them. Splitting the body -> head edge into its own block moves the copy off the exit path and the problem disappears — which is the same fix as for critical edges, arrived at from a different direction.
Hazard three: critical edges have nowhere to put the copies
outOfSSA. LLVM instead runs edge splitting as a normalization before PHIElimination, so by the time phis are lowered every phi predecessor has a single successor. A production backend should do the same rather than rely on a lowering's shape.A *critical edge* runs from a block with several successors to a block with several predecessors. The copies for a phi belong on that edge, and there is no block that corresponds to it: putting them at the end of the source block runs them on the source's other successors too, and putting them at the top of the target block runs them for the target's other predecessors too. Neither end is the edge.
The remedy is to split it — insert a new block on the edge whose only content is the copies and a jump. It is a cheap transformation, it is usually done before destruction as a normalization pass, and it costs a branch target and slightly worse block layout.
AtlasLang's outOfSSA detects critical edges and reports them in its result rather than pretending they do not exist. It still places the copies at the end of the predecessor, which is honest to look at: in the example below the stray %3 = copy 0 at the end of b0 also executes on the path to b1, and it is harmless *here* only because b1 assigns %3 again before reaching b2. That is a property of this program, not of the placement. Change the shape so the destination is live on the other path and the same placement is a miscompilation.
b0: ; entry %1 = bool 1 > 0 branch %1 ? b1 : b2 b1: ; if.then preds=b0 jump b2 b2: ; if.join preds=b0,b1 %3 = phi x [0 from b0, 1 from b1] print %3
▸b0: ; entry▸ %1 = bool 1 > 0▸ %3 = copy 0 ; belongs on the b0->b2 edge, but runs on b0->b1 as well▸ branch %1 ? b1 : b2▸b1: ; if.then preds=b0▸ %3 = copy 1▸ jump b2▸b2: ; if.join preds=b0,b1▸ print %3
Read it asThe reported critical edge is the useful output here. Splitting b0 -> b2 would create a block containing only %3 = copy 0; jump b2, reached only when the branch falls through, and the stray write on the b1 path would not happen at all. The general rule for a backend: split every critical edge before destroying SSA, and the placement question stops being interesting.
1let a = 1;2let x = 0;3if (a > 0) { x = 1; }4print(x);And then most of the copies disappear
It would be reasonable to read all this and conclude that leaving SSA is expensive. Usually it is not, because the copies are the register allocator's problem next, and coalescing exists to remove them: if the phi destination and an operand do not interfere, they can be given the same register and the copy becomes a no-op that is deleted. [[coalescing-and-rematerialization]] is where that happens.
What survives coalescing is the interesting residue — the cycle-breaking temporaries, which by construction *do* interfere, and copies across edges where register pressure forced different assignments. That is a small number of mov instructions in most functions, and it is the honest cost of having had SSA at all.
How it works
The steps, in the order the compiler takes them.
- For each block with phis, and for each predecessor of that block, collect one move per phi: destination is the phi's register, source is the operand tagged with that predecessor.
- Detect whether the edge is critical — predecessor has several successors and the block has several predecessors — and split it, or report it.
- Sequence the register-to-register moves as a parallel copy: repeatedly emit any move whose destination is not still read by a remaining move.
- When no such move exists, every remaining move is in a cycle; choose a victim, copy the victim's destination into a fresh temporary, rewrite remaining moves that read that destination to read the temporary, then emit the victim.
- Emit moves whose source is a constant directly — they cannot participate in a cycle.
- Append the sequenced moves to the predecessor, before its terminator, and delete the phis from the block.
- Hand the result to the register allocator, which coalesces away the copies whose source and destination do not interfere.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- The phis are emitted in listing order and a loop that should swap two variables instead assigns both the same value. The program runs, produces plausible output, and is wrong only for inputs that make the swap observable.
- The lost copy fires and a value read after a loop is one iteration ahead of what the source says. Off-by-one results, correct for zero-iteration loops, wrong for the rest.
- Copies are placed on a critical edge's source block and clobber a register that the other successor still needed. The failure appears only when that branch direction is taken, so it survives most test suites and shows up in production.
- The cycle-breaking temporary is allocated from a register that is live across the copy sequence. The rescue itself destroys a live value, and the corruption is in a variable unrelated to the swap.
- A phi is left in the IR because its block was unreachable and the destruction pass skipped it. Code generation hits an instruction it has no encoding for, and the compiler crashes — which is the friendliest outcome in this list.
When it helps
- Always, in the sense that it is not optional: no machine executes a phi, so every SSA compiler contains this pass.
- Doing it well — splitting critical edges, sequencing properly, then coalescing — is what keeps the copy count near zero on ordinary code, so the whole SSA middle-end costs almost nothing at run time.
- The parallel-copy sequencer earns its keep three times over, because argument shuffling into ABI registers and edge reconciliation in a linear-scan allocator are the same problem.
When it hurts
- Under high register pressure, where coalescing cannot remove the copies and every phi becomes real
movinstructions on a hot path. - On targets with few registers, where the cycle-breaking temporary may itself force a spill, turning a register move into two memory accesses.
- When it interacts with optimizations that extended live ranges. Copy propagation and coalescing before destruction are exactly what turn the textbook-safe algorithm into the lost-copy hazard.
What it costs
Every one of these is paid by something.
- Sequencing parallel copies buys correct swaps; it pays a temporary register per cycle, which under pressure can force a spill and turn two register moves into memory traffic.
- Splitting critical edges buys a place to put the copies and removes two of the three hazards at once; it pays an extra basic block and an extra branch target, which costs code size and can hurt block layout and branch prediction.
- Coalescing after destruction buys back nearly all the copies; it pays compile time in the allocator and couples two passes that would otherwise be independent — a coalescing decision can create interference that forces a spill elsewhere.
- Reporting critical edges rather than splitting them, as AtlasLang does, buys a simpler pass and a visible diagnostic; it pays correctness margin, because the placement is then only safe for the CFG shapes the lowering happens to produce.
What else you could do
What a different compiler or language does instead, and when that is better.
- Split every critical edge as a normalization pass before destruction, which is what LLVM effectively does. Then every phi predecessor has one successor, the placement question is trivial, and only the swap problem remains.
- Sreedhar, Ju, Gillies and Santhanam's method translates out of SSA by building congruence classes of phi-related values and inserting copies only where they interfere. It produces substantially fewer copies than naive destruction plus coalescing, at the cost of an interference computation before allocation rather than during it.
- Use block arguments instead of phis — MLIR, Swift SIL, Cranelift — so the values are supplied at the branch. The parallel-copy problem does not vanish; it moves to the branch, where the same sequencer resolves it, but the critical-edge question is answered structurally.
- Keep SSA all the way into allocation with an SSA-based register allocator, exploiting the fact that the interference graph of a strict SSA program is chordal and therefore colourable in polynomial time. The copies still have to be inserted eventually, but spilling decisions are made with better information first.
See it for yourself
The flag, dump or tool that shows you this directly.
llc -print-after=phi-node-elimination t.llshows machine IR immediately after phis have become copies, before coalescing removes them.llc -print-after=register-coalescer t.llon the same input shows how many of those copies survived. The diff between the two dumps is the honest cost of SSA.opt -passes=break-crit-edges -S t.llsplits critical edges so you can see the extra blocks that a well-behaved backend creates before destruction.- Our SSA converter shows the post-destruction function and the
criticalEdgeslist fromoutOfSSA;scripts/compilers-sim.test.tscontains the swap and rotation tests that verify the sequencer by simulation.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Out-of-SSA is just deleting the phis." Deleting them is the last step. Everything before it is deciding where the copies go and in what order, and that is where the bugs are.
- "A parallel copy is just several copies." It is several copies that all read the pre-copy state. Turning it into a sequence is a real algorithm with a cycle case, and the sequence is not unique.
- "Save the value before it gets overwritten" — and then saving the source. The value at risk is the destination, because the source is still readable until something writes it, and the sequencing rule guarantees nothing does before its last reader.
- "Critical edges are a theoretical concern." A single
ifwith noelseproduces one. They are everywhere, and the reason they are usually invisible is that backends split them as a matter of routine. - "All these copies make SSA expensive at run time." Coalescing removes most of them. What is left is small, and measurable — look at the two
llcdumps above rather than guessing.
Misconceptions
The claim, and what is actually true.
if with no else produces one. They are ordinary, and backends split them routinely, which is why they are rarely visible in a dump.Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
No machine can execute a phi, so before code generation each one is replaced by copies placed on the edges it describes. For a simple if/else that means one copy at the end of each arm. The complications are that the copies for a block must happen simultaneously, that some edges have nowhere to put a copy, and that a copy on the wrong path can destroy a value something else still needed.
practical
If you are debugging a backend that produces wrong values on one branch direction only, or off by one iteration after a loop, this pass is the first place to look. The three signatures are distinctive: a swap that duplicates instead is the parallel-copy sequencing; a value one iteration too far along after a loop is the lost copy; a value clobbered on a path that never entered the merge is a critical edge. All three are silent, and none of them show up in a verifier, because the resulting IR is perfectly well-formed.
internals
The hazards are not three bugs but one, seen from three sides: a phi describes an assignment that happens *on an edge*, and an instruction list has no place to write an edge. Every repair is a way of manufacturing one. Splitting a critical edge manufactures a block for it. Sequencing a parallel copy manufactures an order that is observationally equivalent to simultaneity. The lost-copy temporary manufactures a place to keep the value the edge is about to overwrite. Sreedhar et al. attack the same problem earlier by asking which phi-related values interfere at all, and inserting copies only for those — which is why it produces fewer copies than naive destruction plus coalescing, and why the interference question moves before allocation instead of during it. An SSA-based register allocator pushes the boundary the other way, keeping the form until after spilling decisions are made, on the strength of the result that a strict SSA program's interference graph is chordal.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
outOfSSA output from src/compilers/sim/ir.ts on the AtlasLang sources shown. Our pass reports critical edges rather than splitting them, and places copies at the end of the predecessor regardless; LLVM splits critical edges first in a separate normalization, so its phi elimination never faces the placement question.while lowering puts the exit branch in the loop header and gives the latch a single successor, which is why the lost-copy problem cannot arise in our output. That is a property of the lowering, not of the algorithm, and an IR that shares a block between the branch and the back edge is exposed to it.If you were asked this in an interview
- A block starts with two phis whose operands are each other's destinations. What does the source program do, and what does naive lowering produce?
- Why does breaking a copy cycle rescue the destination rather than the source? Work through a two-element swap.
- What is a critical edge, and what is the standard fix?
- You have a loop whose result is one iteration too far along. Which pass do you suspect, and what would you look at first?
Connections
- Testing & Reliability Engineering — Verifying an algorithm by simulating its output rather than by comparing against an expected resultOur parallel-copy tests run the emitted move sequence against an initial state and check the final state, because an expected move list can itself encode the wrong algorithm and pass. The general testing principle is owned there;
[[differential-testing]]is the compiler-specific version.