Static Single Assignment Form - Converting To SSA

Converting To SSA

Converting ordinary code into SSA form is primarily a simple matter of replacing the target of each assignment with a new variable, and replacing each use of a variable with the "version" of the variable reaching that point. For example, consider the following control flow graph:

Notice that we could change the name on the left side of "x x - 3", and change the following uses of x to use that new name, and the program would still do the same thing. We exploit this in SSA by creating two new variables, x₁ and x₂, each of which is assigned only once. We likewise give distinguishing subscripts to all the other variables, and we get this:

We've figured out which definition each use is referring to, except for one thing: the uses of y in the bottom block could be referring to either y₁ or y₂, depending on which way the control flow came from. So how do we know which one to use?

The answer is that we add a special statement, called a Φ (Phi) function, to the beginning of the last block. This statement will generate a new definition of y, y₃, by "choosing" either y₁ or y₂, depending on which arrow control arrived from:

Now, the uses of y in the last block can simply use y₃, and they'll obtain the correct value either way. You might ask at this point, do we need to add a Φ function for x too? The answer is no; only one version of x, namely x₂ is reaching this place, so there's no problem.

A more general question along the same lines is, given an arbitrary control flow graph, how can I tell where to insert Φ functions, and for what variables? This is a difficult question, but one that has an efficient solution that can be computed using a concept called dominance frontiers.

Note: the Φ functions are not actually implemented; instead, they're just markers for the compiler to place the value of all the variables, which are grouped together by the Φ function, in the same location in memory (or same register).

According to Kenny Zadeck Φ functions were originally known as phoney functions while SSA was being developed at IBM Research in the 1980s. The formal name of Φ function was only adopted when the work was first published in an academic paper.