Optimizeimplementation

Copy Propagation

If `a` is a copy of `b`, use `b` directly and let the copy die. In SSA this is legal by construction; outside SSA it needs a reaching-definitions analysis, and that difference is one of the clearest arguments for SSA there is.

The question

Why does the compiler bother emitting a = b at all, and what lets it get rid of the copy afterwards?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

SSA with explicit copy instructions and phi nodes. The representation is what makes the pass trivial: because a register is defined exactly once and never reassigned, a copy's source is guaranteed to hold the same value at every point the copy's destination is live. In three-address code without SSA that guarantee does not exist and has to be recovered by analysis.

What this phase may assume or do

The definition is a pure copy of another value that is still live and unmodified at every use of the copy. In SSA the "unmodified" half is free — nothing is ever modified — so the condition reduces to "this is a copy". AtlasLang additionally treats a phi whose incoming values are all identical as a copy, because a merge of one distinct value is not a merge; the legality there is that every incoming edge supplies the same value, so the phi's result is that value on every path that can reach it.

Key points

  • Replace uses of a copy with its source; the copy then dies to dead code elimination.
  • In SSA the legality condition is free, because the source can never have been reassigned. Outside SSA the same rewrite needs reaching definitions.
  • A phi whose incoming values are all identical is a copy, not a merge — SSA construction produces these routinely and something has to clean them up.
  • Most copies are generated by the compiler, not written by the programmer: lowering, inlining and leaving SSA all emit them deliberately.
  • The same idea recurs as coalescing in the register allocator and as redundant-move removal in the peephole, each seeing copies the earlier level could not.

The rewrite, and where the copies came from

Copy propagation is the one-line optimization: replace uses of a copy with its source. What makes it worth a lesson is that almost no copies are written by programmers. They are produced by the compiler itself, in bulk, by phases that had good reasons to emit them.

Lowering emits copies whenever it needs a value in a specific place: an argument moved into a parameter position, a return value moved into a return slot, a phi resolved into moves when leaving SSA — [[out-of-ssa]] produces them by the hundred. Inlining emits them when binding arguments to parameters. Each of those phases is easier to write if it may emit a redundant copy and rely on this pass to remove it, and that division of labour is a real design principle: let each pass be simple and correct, and let cleanup be someone else's pass.

The whole optimization
Before
%2 = copy %1
%3 = int %2 + 1
print %3
After
%3 = int %1 + 1
print %3
Legal only when

In SSA, %1 has exactly one definition and can never be reassigned, so at every point where %2 is live, %2 and %1 hold the same value. Substituting one for the other therefore cannot change any computed value. The copy instruction is then userless and dies to [[dead-code-elimination]].

Illegal when

The source is reassigned between the copy and the use. In three-address code, a = b; b = b + 1; c = a + 1 must NOT become c = b + 1 — b has changed and a still holds the old value. Establishing that this cannot happen requires [[reaching-definitions]]; SSA removes the need for the analysis by making reassignment impossible, which is most of the argument in [[why-ssa-helps]].

The phi that is not a merge

implementationAtlasLang follows copy chains up to sixteen hops and stops, which is a termination guard rather than a tuning parameter — a loop-carried phi can be cyclic, and following it forever is a hang rather than a wrong answer. LLVM handles the general case with its InstCombine and SimplifyCFG machinery plus a dedicated simplifyInstruction that folds trivial phis on the spot during construction, so trivial phis rarely reach a separate pass there at all.

SSA construction places a phi wherever the dominance frontier says a definition *might* need merging. It does not check whether the values arriving on the different edges actually differ, because checking would require the values to already be known, and they are not at construction time. The result is a supply of phi nodes whose incoming values are all the same value.

Such a phi is a copy. If every predecessor supplies %7, then the phi's result is %7 on every path that reaches it, and the phi can be replaced by %7 everywhere. AtlasLang detects this by collecting the distinct value keys of the incoming edges and treating a set of size one as a copy — and it follows chains, with a hop bound so that a cyclic phi (a loop-carried value that turns out to be constant) cannot hang the pass.

This is a good example of why the passes are separated rather than merged. Collapsing a trivial phi *feels* like folding, and AtlasLang deliberately does not do it in the folding pass: a learner who toggles the two passes independently can see which effect belonged to which, and that separation is worth more than the handful of instructions it costs.

A phi whose arms turned out to agree, after propagation made both arms constant
After constant propagation
b1:
  jump b3
b2:
  jump b3
b3:
  %5 = phi x [1 from b1, 1 from b2]
  print %5
After copy propagation
▸b3:
▸  print 1

Read it asThe phi had two incoming edges and one distinct value, so it merged nothing. Note the ordering dependency: this only became visible *after* constant propagation replaced both arms with the literal 1. Run copy propagation first and there is nothing to find. That is [[phase-ordering]] in one example, and it is why the pass manager iterates rather than making a single pass.

Why the copies come back, and who removes them then

Propagating copies away in SSA does not mean the program has no copies. Leaving SSA reintroduces them: a phi becomes a set of parallel moves placed in the predecessor blocks, and those moves are genuine machine-level copies. Register allocation then tries to remove them again by *coalescing* — assigning the source and destination of a copy to the same physical register, at which point the copy is a move from a register to itself and can be deleted.

So the same idea appears three times at three levels: copy propagation over SSA values, coalescing over physical registers, and peephole removal of redundant mov instructions in the final assembly. Each level removes copies the previous level could not see, and each is limited by something different — SSA propagation by nothing much, coalescing by interference, peephole by its window size. See [[coalescing-and-rematerialization]] and [[peephole-optimization]].

The one place copies must not be removed naively is the parallel copy itself. Resolving a <- b and b <- a by sequencing them does not swap the values, it makes both equal to the original b. AtlasLang has a dedicated sequenceParallelCopies for exactly this, and the same problem shows up in three places in any backend — phi resolution, argument shuffling into ABI registers, and reconciling allocations across a control-flow edge.

How it works

The steps, in the order the compiler takes them.

  • Scan every instruction, recording each explicit copy as a mapping from its destination to its source value.
  • Also record each phi whose incoming values reduce to a single distinct value key, mapping its destination to that value.
  • Rewrite every use by following the mapping transitively, with a hop bound so a cyclic phi terminates.
  • Delete the instructions whose destinations were mapped, since nothing refers to them any more.
  • Report the change count so the pass manager knows to iterate — a propagation can expose a phi that has just become trivial.

How it breaks

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

  • Outside SSA, a copy is propagated across a reassignment of its source, and a variable silently reads a newer value than it should. The program computes a wrong number with no crash and no warning — the hardest class of compiler bug to notice.
  • A cyclic phi chain is followed without a bound and the compiler hangs on a specific input. The symptom is a build that never finishes on one file.
  • Parallel copies from phi resolution are sequenced naively and a swap becomes a duplicate. Two variables that should have exchanged values both end up with one of them.
  • Copies are propagated so aggressively that a value's live range stretches across a call, the allocator has to spill it around the call anyway, and the removed copy is replaced by a store and a load.

When it helps

  • Immediately after inlining, where argument binding produced one copy per parameter and none of them carry information.
  • After leaving SSA, where phi resolution produced parallel moves and many of them turn out to be self-moves once registers are assigned.
  • As an enabler: propagating a copy is often what lets constant propagation or CSE see through to the real definition, which is why the three run in a loop rather than in sequence.

When it hurts

  • When it lengthens live ranges. A copy is sometimes doing useful work — holding a value in a cheap place so the original can die — and removing it hands the allocator a longer range to colour.
  • When debugging: a copy often corresponds to a named source variable, and propagating it away removes the only instruction that variable could be mapped to, contributing to values reading as optimized out.

What it costs

Every one of these is paid by something.

  • Copy propagation buys removed moves and simpler downstream analysis, and pays in live-range length: the source value must now stay live until the last use of what was the copy, which can raise register pressure and cause a spill.
  • Relying on this pass buys enormous simplicity in every phase that emits copies — lowering, inlining, out-of-SSA can all be written naively — and costs a mandatory cleanup pass that must be correct, because every one of those phases now depends on it.
  • Following copy chains transitively buys completeness in one pass and costs a termination guard plus the reasoning about cycles that goes with it; iterating single hops instead is simpler and costs more pass-manager rounds.

What else you could do

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

  • Do not emit the copies in the first place: a lowering that writes directly into the destination avoids the copy and the pass, at the cost of a much more complicated lowering that has to know about destinations.
  • Handle it entirely in the register allocator by coalescing, which removes copies with full knowledge of interference and is where the decision genuinely belongs for machine-level moves — [[coalescing-and-rematerialization]].
  • Outside SSA, use reaching definitions to establish the same condition. It works, it is a standard data-flow analysis, and it is strictly more machinery for a strictly weaker result — which is the argument for SSA in miniature.
  • Value numbering subsumes copy propagation: a copy and its source get the same value number by construction, so a GVN-based pipeline gets this for free rather than as a separate pass.

See it for yourself

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

  • Toggle copy propagation alone at /compilers/passes on the phi example (let x = 0; if (c > 3) { x = 1; } else { x = 2; } print(x);) and change the arms to be equal — the phi collapses only when they agree.
  • LLVM: opt -passes=instcombine -S folds trivial phis; llc -debug-only=regalloc shows coalescing decisions on the machine-level copies later.
  • GCC: -fdump-tree-copyprop-details and -fdump-tree-forwprop-details print each propagation.
  • To see the copies that this pass cannot reach, dump machine IR before and after register allocation: llc -print-after=phi-node-elimination shows the moves that phi resolution introduced.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Assignments between variables cost an instruction." At the IR level they usually cost nothing after this pass, and at the machine level they usually cost nothing after coalescing. Writing let tmp = value; for clarity is close to free.
  • "SSA removes the need for this pass." SSA makes the pass trivial to *justify*; the copies still exist and still have to be removed, and leaving SSA creates a fresh batch.
  • "A phi is always a merge." A phi is placed where a merge might be needed. Whether it merges anything is a separate question, answered later, by this pass.

Misconceptions

The claim, and what is actually true.

Copy propagation is a micro-optimization not worth implementing.
It is what makes every phase that emits copies simple. Removing it does not cost you a few moves; it costs you the ability to write a naive lowering, a naive inliner and a naive out-of-SSA.
You need SSA to do copy propagation.
You need SSA to do it *cheaply*. Outside SSA the same rewrite is legal under a reaching-definitions analysis — more machinery, weaker result.
After copy propagation there are no copies left.
Leaving SSA reintroduces them as parallel moves, and only the register allocator's coalescing can remove those, because only it knows which values can share a register.

Go deeper

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

overview

If one name is just another name for the same value, use the original and delete the alias. Under SSA that is always safe, because no name is ever given a second value.

practical

Do not contort source code to avoid temporaries — intermediate locals are removed by this pass and cost nothing. Do notice that the pass is why a debugger cannot always show you a variable you named: if the only instruction that corresponded to it was a copy, it is gone.

advanced

The interesting frontier is out-of-SSA, where phi resolution creates parallel copies that must be sequenced without clobbering. The naive sequencing is wrong for swaps and for any cycle; the correct algorithm emits every move whose destination nothing still needs to read, and breaks genuine cycles with one temporary. The same routine is needed for shuffling call arguments into ABI-mandated registers and for reconciling different allocations on the two sides of a control-flow edge, which is why a backend factors it out once rather than writing it three times.

How much this depends on

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

implementationAtlasLang runs copy propagation as its own pass and detects trivial phis in it. LLVM folds most trivial phis during SSA construction and instruction simplification, so a separate copy-propagation pass barely exists there; GCC has explicit copyprop and forwprop passes. The transformation is universal; whether it has a name in the pass list is not.
targetWhether the remaining machine-level copies cost anything depends on the microarchitecture. Modern x86-64 and AArch64 cores frequently eliminate register-to-register moves during register renaming, so a mov that survives to the assembly may cost zero cycles — which is why counting instructions in a disassembly is a poor proxy for time.
typicalMainstream compilers rely on this pass being present, which is why their lowering and inlining phases emit copies freely. A hand-written backend that omits copy propagation will produce visibly worse code than the same backend with it, out of proportion to how simple the pass is.

If you were asked this in an interview

  • Why is copy propagation legal without any analysis in SSA form, and what would you need to prove without SSA?
  • Where do all the copies in a compiler's IR actually come from?
  • You resolve a phi into two moves, a <- b and b <- a. What goes wrong and how do you fix it?

Connections

Computer Architectureregister-renamingregisters