Static Single Assignment form

Static Single Assignement (SSA) form is a property of an Intermediate Representation where each variable is assigned exactly once and it is defined before it is used, and existing variables are split into versions.

This technique enables lots of compiler optimizations.

Converting to SSA

In order to convert an IR to SSA form, the target of each assignment should be replaced with a new variable and each use of these variables should be substituted with the version of that variable reaching that point.

$\phi$ (phi) function

A $\phi$ function is a special statement which generates a new definition of a variable depending on the control flow. In the last block depicted below, we do not know which version of y to use:

We use a $\phi$ function, which selects the right version according to the flow, so the last block becomes:

In order to determine where to insert a Phi function and for which variables, we use the concept of dominance frontiers.

4 May 2019