Static Single Assignment (with relevant examples)

Static Single Assignment was presented in 1988 by Barry K. Rosen, Mark N, Wegman, and F. Kenneth Zadeck. 

In compiler design, Static Single Assignment ( shortened SSA) is a means of structuring the IR (intermediate representation) such that every variable is allotted a value only once and every variable is defined before it's use. The prime use of SSA is it simplifies and improves the results of compiler optimisation algorithms, simultaneously by simplifying the variable properties. Some Algorithms improved by application of SSA - 

1. Constant Propagation - 
   Translation of calculations from runtime to compile time. E.g. - the instruction v = 2*7+13 is treated like v = 27
2. Value Range Propagation - 
   Finding the possible range of values a calculation could result in.
3. Dead Code Elimination -
   Removing the code which is not accessible and will have no effect on results whatsoever.
4. Strength Reduction -
   Replacing computationally expensive calculations by inexpensive ones.
5. Register Allocation -
   Optimising the use of registers for calculations.

Any code can be converted to SSA form by simply replacing the target variable of each code segment with a new variable and substituting each use of a variable with the new edition of the variable reaching that point. Versions are created by splitting the original variables existing in IR and are represented by original name with a subscript such that every variable gets its own version.

Example #1:

Convert the following code segment to SSA form:

x = y - z
s = x + s
x = s + p
s = z * q
s = x * s

Solution:

x = y - z
s2 = x + s
x2 = s2 + p
s3 = z * q
s4 = x2 * s3

Here x,y,z,s,p,q are original variables and x₂, s₂, s₃, s₄ are versions of x and s. 

Example #2:

Convert the following code segment to SSA form:

a = s - b
q = a * e
a = q + d
q = b - c
q = a * q

Solution:

a = s - b
q = a * e
a2 = q + d
q2 = b - c
q3 = a2 * q2

Here a,b,c,d,e,q,s are original variables and a₂, q₂, q₃ are versions of a and q. 

Phi function and SSA codes

The three address codes may also contain goto statements, and thus a variable may assume value from two different paths.

Consider the following example:-

Example #3:

x = 1
if x < 10 goto L1
goto L2
L1: 
x = 10
L2:
y = x

When we try to convert the above three address code to SSA form, the output looks like:-

Attempt #3:

x1 = 1
if x1 = 10 goto L1
goto L2
L1: 
x2 = 10
L2:
y = ???

We need to be able to decide what value shall y take, out of x₁ and x₂. We thus introduce the notion of phi functions, which resolves the correct value of the variable from two different computation paths due to branching.

Hence, the correct SSA codes for the example will be:-

Solution #3:

x1 = 1
if x1 < 10 goto L1
goto L2
L1: 
x2 = 10
L2:
y = ?(x1,x2)

Thus, whenever a three address code has a branch and control may flow along two different paths, we need to use phi functions for appropriate addresses.

vibhutijain99

Follow

Improve

Article Tags :

• Compiler Design
• GATE CS