Table of content

• Static Single-Assignment
• Example

Static Single-Assignment

Basic idea is you have a program and seek to convert it to Static Single-Assignment form so that every variable has one and only one assignment location. In this form, many opimizations can be performed easily as there’s no dependency graph to consider.

Example

Given the original program

x = 5
x = x - 3
if(x < 3):
    y = x * 2
    w = y
else:
    y = x - 3

w = x - y
z = x + y

In the SSA form, you get

x1 = 5
x2 = x1 - 3
if(x2 < 3):
    y1 = x2 * 2
    w1 = y1
else:
    y2 = x2 - 3

y3 = phi(y1,y2)
w2 = x2 - y3
z = x2 + y3

You see that we just go through and treat every new assignment as if it was make a new variable. Essentially, treating the entire program as if it was a giant composition function $f \circ g$. Note that after the if statement, we have two possible paths for y. We can still have single assignment by introducing a new function $\phi(y1,y2)$ that simply returns the correct y depending on the branch.