Static Single-Assignment Form
Introduction: Static single-assignment form (SSA) is an intermediate representation that facilitates certain code optimizations. Two distinctive aspects distinguish SSA from three-address code. The first is that all assignments in SSA are to variables with distinct names; hence the term static single-assignment.
Figure 6.13 shows the same intermediate program in three-address code and in static single assignment form. Note that subscripts distinguish each definition of variables p and q in the SSA representation.
Figure 6.13: Intermediate program in three-address code and SSA
The same variable may be defined in two different control-flow paths in a program. For example, the source program
if ( f l a g ) x = -1; e l s e x = 1;
y = x * a;
has two control-flow paths in which the variable x gets defined. If we use different names for x in the true part and the false part of the conditional statement, then which name should we use in the assignment y = x * a? Here is where the second distinctive aspect of SSA comes into play. SSA uses a notational convention called the (^-function to combine the two definitions of x:
if ( f l a g ) xi = -1; e l s e x2 = 1;
x3 = 0 ( x i , x 2 ) ;
Here, (j)(x1,x2) has the value x2 if the control flow passes through the true part of the conditional and the value x2 if the control flow passes through the false part. That is to say, the ^-function returns the value of its argument that corresponds to the control-flow path that was taken to get to the assignment statement containing the ^-function.