◄ WORLD V · SONNY 5DART 153 · a helldive at the net

COPY PROPAGATION follow the copy to its source; the middleman dies

After b <- a, every later use of b (until b is redefined) can read a directly. On its own it changes nothing; its job is to expose the copy b as dead so dead-code elimination can delete it, and to line up operands so value-numbering sees more equalities. The small pass that makes the big ones fire.

THE TECHNIQUE substitute the source; strand the copy

Given a chain of copies and one real use, rewrite each use to its ultimate source and mark the now-unused copies dead. Watch c = b + 1 become c = a + 1 and b strand: live demo







  
HISTORY & CREDIT classical/folklore dataflow; Kildall 1973, Dragon Book

  
“Copy propagation removes the copy.” — not by itself. It only rewrites the uses; the copy statement is removed later by dead-code elimination, once nothing reads it. Two passes, one enabling the other. cited

  
1971–72 · Allen & Cocke — “A Catalogue of Optimizing Transformations” names copy propagation’s relatives (constant propagation, dead-code elimination) but not copy propagation itself; it is classical/folklore, subsumed by the dataflow framework below.
1973 · Kildall’s dataflow framework (POPL) gives it a fixed-point footing (copy-available sets).
1986 · the Dragon Book (Aho, Sethi & Ullman) makes it a textbook staple; SSA (1991) makes it a single walk of the def-use edges.

  
On SSA it is almost free: a copy b = a means every use of b is literally the use of a’s single definition — substitute and the copy is unreferenced. Allen & Cocke, 1971






  
RECOMMEND FOR I-13 same value through the source

  
That the rewrite preserves the value — c via b equals c via a — holds on the canonical compiler:

  
$ i13 run copy.i13   # b <- a ; c <- b+1  is the same as  c <- a+1
a = 10
b = 10   (copy of a)
c = 11   -- c <- b + 1
cp = 11  -- c <- a + 1  (propagated; b now unused)

  
Recommend: copy-propagation is LIT and enabling — verified c is 11 whether computed through the copy b or directly through a, so an I-13 pass can rewrite the use and leave b dead for elimination. Its value is not its own output but the redundancy it exposes to GVN (152) and the copies it hands to dead-code cleanup — the quiet pass that unlocks the loud ones.