Static single-assignment form
Additional statements that assign to new versions of variables may also need to be introduced at the join point of two control flow paths.
In functional language compilers, such as those for Scheme and ML, continuation-passing style (CPS) is generally used.
SSA is formally equivalent to a well-behaved subset of CPS excluding non-local control flow, so optimizations and transformations formulated in terms of one generally apply to the other.
Kenneth Zadeck, a key member of the team, moved to Brown University as development continued.
[3] In 1988, Barry Rosen, Mark N. Wegman, and Kenneth Zadeck replaced the identity assignments with Φ-functions, introduced the name "static single-assignment form", and demonstrated a now-common SSA optimization.
[3] Alpern, Wegman, and Zadeck presented another optimization, but using the name "static single assignment".
[7] Finally, in 1989, Rosen, Wegman, Zadeck, Cytron, and Ferrante found an efficient means of converting programs to SSA form.
This general question has an efficient solution that can be computed using a concept called dominance frontiers (see below).
These move operations might not end up in the final code based on the compiler's register allocation procedure.
However, this approach may not work when simultaneous operations are speculatively producing inputs to a Φ function, as can happen on wide-issue machines.
Typically, a wide-issue machine has a selection instruction used in such situations by the compiler to implement the Φ function.
This algorithm was originally described in "Efficiently Computing Static Single Assignment Form and the Control Graph" by Ron Cytron, Jeanne Ferrante, et al. in 1991.
For this reason, minimal SSA does not necessarily produce the fewest Φ functions that are needed by a specific procedure.
A Φ function will then be considered live as long as it is the nearest definition that dominates at least one use, or at least one argument of a live Φ. Semi-pruned SSA form[12] is an attempt to reduce the number of Φ functions without incurring the relatively high cost of computing live-variable information.
This can be accomplished by "constructing" SSA as a set of functions that map between parts of the existing IR (basic blocks, instructions, operands, etc.)
When the SSA form is no longer needed, these mapping functions may be discarded, leaving only the now-optimized IR.
Feature-specific extensions retain the single assignment property for variables, but incorporate new semantics to model additional features.
Some feature-specific extensions model high-level programming language features like arrays, objects and aliased pointers.
