Static Single Assignment Form

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

Return to the Index

This card can also be read via Gemini.

Conversion to SSA Form

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.