copy.pl
Copy propagation, run after promote: copy_module/2 removes copies and trivial phis from each function in strict SSA form, replacing every use by the value it copies.
What disappears
- A copy of a temporary of the same class.
- A copy of an integer constant at class
worl, reduced modulo 2^32 or 2^64. - Then each trivial phi: one whose operands, ignoring its own temporary, all name one value.
Everything else stays. An l to w copy narrows, and a p copy of a symbol or literal must still materialize a pointer, keeping the module's ABI and mode. Functions that are not in strict SSA form, and functions that call setjmp, are left alone.
How
The eligible copies are indexed, then each chain is resolved once, memoizing every link on the way back, so source order need not be dependency order. The copy work is O((definitions + uses) log definitions), not repeated whole-function scans or one chain walk per use. Trivial phis are found by a worklist that revisits only the phis that read a simplified one.
Dead code
strict_ssa/3 checks dominance only in reachable blocks, so:
- Dead definitions are never removed: they may contain cycles or uses before definitions. Only copies in reachable blocks are eligible, and only phis in reachable blocks are simplified.
- Dead uses of removed live copies are rewritten, including phi edges, so every temporary stays defined.
- Phi simplification counts dead incoming edges too, and leaves all-self phis and nontrivial cycles alone.
M is the module M0 with copies and trivial phis propagated away in each strict SSA function.
Item is the module item Item0, with copies propagated if it is a function. Reps (here and below): assoc Temp -> the value that replaces it.
A substitution is history, not a new primary name for its survivor.
assoc Temp -> class of its definition.
Reps is Reps0 with the value that replaces D, and every link on the way to it, added. Strict dominance rules out cycles among the live copy definitions. copy_chain/6 is tail recursive even when a chain has thousands of links.
following copies (and the values already in Reps) from V0 ends at V, a value that is not one; Path is the temps on the way that are not in Reps, in front of Path0. Copies and Reps hold temps and constants only.
Copy propagation exposes invariant phis. Index their users so that a simplification revisits only dependent phis, not the whole function. Redirect those dependencies too: if A becomes B and B later becomes C, every remaining phi that used A must see C.
Reps is Reps0 with the value of each trivial phi, as found by a worklist over the phi temps Pending. Phis0: assoc D -> operand values, for the phis not yet simplified; Users0: assoc S -> ordset of the phis that read tmp(S). Invariant: no phi left in Phis0 reads the temp of a phi already simplified, and each one that may have become trivial is in Pending.
in Phis, phi U reads V wherever it reads tmp(D) in Phis0.
Substitution
Block is Block0 without the phis and copies whose temp is in Reps, and with every use of such a temp replaced by its value.