Static Single Assignment (SSA) Form

A single program is in SSA form if: each variable is the target of exactly one assignment statement in the program text.

Which values to version?

Scalars? iN, iN*8, fN, ...
Arrays? A[], *x, ...
- Any operation of the type p[i] or *p that can potentially write to A[i] or *x will then cause a new version of the array (A[]) or the object (*x) to be created.
- For example, a statement of the form *p = 42 will be written to: *p = 42, A2=A1[*p=42], (*x)_2 = *x_1[*p=42], ....
- Properties (e.g., constant-ness) may then be tracked separately for A1, A2, (*x)_1, (*x)_2, and so on.
- In the absence of such versioning, there is a single A and (*x) that get tracked. If we are implementing a flow-insensitive analysis, their values at different program points will get conflated (using the meet operator) making the analysis less precise than desired.
I/O devices? console, printer, ...
- Properties (e.g., colour state) may then be tracked for every "version" (state as identified statically) of a device.

Versioning at higher granularities presents a tradeoff between precision improvement and complexity. Complexity here includes programmability (IR complexity), and also time and space complexity.

Usually, e.g., in LLVM IR, the versioning is only done for scalar pseudo-registers. Memory and other stateful resources are much more complex to version.

Translation to SSA (high level)

Replace the original program with a new program with the same CFG using the following steps:

For non-empty paths x-->z and y-->z where z is a convergence point, add a trivial phi node, e.g., z: v = \phi(v, v, ..., v).
Each mention of a variable v is replaced by a new version, say v_l (at location l), which now leaves the program in SSA form, such that:
- At all uses of a variable v (in the original program) and the corresponding v_l (in the new program), the read value must be identical.

There are many ways to add phi nodes and version the variables to obtain an SSA program, but we want the Minimal SSA program where the number of inserted phi nodes is as small as possible. For example, if x-->z-->w and y-->z-->w are two paths, then a phi node should only be added to z, but not to w. Minimizing the number of phi nodes avoids an increase in the program size, making all future analyses faster.

Pruned SSA: Forego placing a phi node at a convergence point z if no more uses of v in or after z (i.e., v is dead at the beginning of z). This requires a backward liveness analysis, and is a further optimization on minimal SSA.

Sketch of the SSA translation algorithm

This algorithm is based on the the paper by R. Cytron, J. Ferrante, B. Rosen, M. Wegman, K. Zadeck, "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph", ACM TOPLAS vol. 13, no. 4, Oct. 1991, pp. 451-490.

Identify the minimal set of convergence points and place trivial phi nodes (dominance frontiers).
Rename the mentions of a variable v such that the use-def and def-use relationships remain unchanged (variable renaming).