Static Single-Assignment Form

Quoting from Appel in [App98]:

Many dataflow analyses need to find the use-sites of each defined variable, or the definition-sites of each variable used in an expression. The def-use chain is a data structure that makes this efficient: for each statement in the flow graph, the compiler can keep a list of pointers to all the use sites of variables defined there, and a list of pointers to all definition sites of the variables used there....

An improvement on the idea of def-use chains is static single-assignment form, or SSA form, an intermediate representation in which each variable has only one definition in the program text. The one (static) definition-site may be in a loop that is executed many (dynamic) times, thus the name static single-assignment form.

An example of the use of SSA form is shown in figure 1. Simple variable renaming suffices to transform straight-line code into SSA form. Subscripts are used to emphasize the relationship of the renamed variables to the original variables. A benefit of SSA form which is obvious from the example is that unrelated uses of the same variable in the source program ($\tt i_1$, $\tt i_2$) become different variables in the SSA form, eliminating false dependencies.

  

Figure 1: SSA transformation of straight-line code.

SSA form becomes more complex when we introduce branches and loops. Figure 2 shows the necessary transformation. You will notice the introduction of phi functions at locations where control flow merges. The $\phi$-function ``magically'' chooses a value from among its arguments based on the control flow path used to reach it. Note that, although $\phi$-functions are impossible to implement directly in an instruction set (due to their magical properties), they can be replaced by move instructions along each control flow edge leading to the $\phi$-function. Doing so violates the static single assignment constraints, but leads to code executable by real processors.

Unless you are implementing code generator backends, it is unlikely you will need to so replace $\phi$-functions or view them as anything but magical n-ary operators. However, it is important to observe and maintain the ordering relationship between control-flow edges and $\phi$-function arguments during transformation and analysis.

  

Figure 2: SSA transformation of branching code.

Analysis, transformation, and optimization of the IR is simplified by its SSA form. In addition, the QuadSSA form is maximally factored. Constants are not allowed as quadruple operands (except for a special const operation); which creates a unique mapping from variable names to values in the computation. This simplifies value analysis.

Appel describes several other benefits of the SSA form in [App98]:

-- If a variable has N uses and M definitions (which occupy about N+M instructions in a program), it takes space (and time) proportional to $N\cdot M$ to represent def-use chains--a quadratic blowup. For almost all realistic programs, the size of the SSA form is linear in the size of the original program.

-- Uses and defs of variables in SSA form relate in a useful way to the dominator structure of the control flow graph, which simplifies algorithms such as interference-graph construction.