Static Single Assignment Form

An intermediate form widely used by modern optimizing compilers; a program in SSA form assigns to each variable only once. To convert a program to SSA form, merely create new variables for every assignment beyond the first:

 i = 1; print i; i = 2; print i;

becomes

 i = 1; print i; i2 = 2; print i2;

and insert "phi" functions at the places where variable definitions merge:

 if (rand() %2) { i = 1; } else { i = 2; } print i;

becomes

 if (rand() %2) { i = 1; } else { i2 = 2; } i3 = phi(i,i2); print i3;

The phi function has nondeterministic semantics [to be precise, phi(a,b) is equal to a if a was the reaching definition in the preconverted program and b otherwise], but that doesn't matter, as it serves mainly as a place-holding function for the optimizer.

The value of SSA form is that many popular compiler optimizations (constant propagation, e.g.) become easier to write (and in some cases, algorithmically faster) when applied to programs in SSA form.

-- ThomasColthurst

Note that conversion to SSA form introduces a lot of assignments; so compilers that do this need to have good register allocators that can eliminate most of them again. Fortunately, that's a pretty well understood problem these days.

An alternative (the writer of this sentence prefers) is register forwarding form: It is related to SSA form, although there are no phi functions. Instead, each label which can be a branch target takes parameters, and you can only use the parameters and assignments done within the current basic block; you cannot read variables from other blocks (you have to pass them as parameters instead).