Static Single Assignment Form

Created: 2020-09-28T23:30:58+00:00

A compiler technique where each value is assigned to once and read from many times.

Conversion to SSA Form

You take any assignments (or ones that might potentially change a value) and instead of writing them to the same slot you create a new slot each time.

Something like this:

hp = 50
echo "you have ", hp, " hit points"
hp -= 10
echo "you have ", hp, " hit points"

becomes something like this:

hp_0 = 50
echo "you have ", hp_0, " hit points"
hp_1 = hp_0 - 10
echo "you have ", hp_1, " hit points"

Phi Functions

"phi functions" are an encrypted way of saying the value depends on context.

For example:

hp = 50
echo "you have ", hp, " hit points"
hp -= 10
echo "you have ", hp, " hit points"
if used_potion:
hp += 50
else:
hp -= 20

becomes something like this:

hp_0 = 50
echo "you have ", hp_0, " hit points"
hp_1 = hp_0 - 10
echo "you have ", hp_1, " hit points"
if used_potion:
hp_2a = hp_1 + 50
else:
hp_2b = hp_1 - 20
hp_3 = phi(hp_2a, hp_2b)

It is a formalism which says whichever of these values was actually assigned last is now assigned to a new name. It is a trick so code analyzers can trace that both hp_2a and hp_2b are "alive" until this point.

Why

It is easier to track the lifecycle of values. This means compilers can make smarter decisions more easily about where to store things during a function.

For example if hp_0 is used only once (to assign hp_1), the space can be re-used. So code can use as many temporary variables as it needs to be readable but it will not use more space at runtime than it truly needs to.

Also if hp_0 is assigned, then a loop happens which does not use it, then the program does use it, the compiler knows that value can be set aside temporarily to make room for memory the loop needs. This is important when dealing with CPU registers.