SSA

Alcance de una definición

Muchas optimizaciones y transformaciones de programas requieren saber cuándo se usa o no se usa una variable. El caso paradigmático es la eliminación de código muerto.

a=1
b=2
f(a)

Está claro que la segunda línea no es necesaria ya que "b" no se usa luego en el programa.

La forma de saber si se usa y dónde se usa una variable (o, dualmente, si se define y dónde se define una variable) es mediante un análisis de alcance. El gran problema de un análisis de este tipo es que una misma variable puede estar definida en varios lugares y usarse en varios lugares. Incluso, cuando no hay estructuras de control de flujo.

a=1
b=2
f(a) //Se usa el "a" de la primera línea
a=3 //Ahora redefinimos el "a"
f(b)
b=4
g(a,b)

Renombrado de variables

De esta forma es muy lioso trabajar. Sin embargo, dado que las cadenas de definición-uso son alfa-equivalentes (se puede renombrar la variable con otro nombre no usado en el programa) es posible obtener un renombrado donde cada variable se defina únicamente una vez. En el caso de arriba sería

a1=1
b1=2
f(a1)
a2=3
f(b1)
b2=4
g(a2,b2)

Todo esto funciona bien, hasta que introducimos estructuras de control de flujo.

Supongamos una simple selección.

if(cond) a=1
else a=2
f(a)

Si intento renombrar, me encuentro con un problema: Tengo dos definiciones para un uso.

if(cond) a1=1
else a2=2
f(...) //a1 o a2

Funciones φ

Lo que se hace para solucionar este problema es la introducción de funciones φ. Estas funciones devuelven el valor correspondiente según el lugar desde donde provenga el flujo de control.

if(cond) a1=1
else a2=2
a3 = φ (a1, a2) //Usamos "a1" si venimos de la rama "then" y usamos "a2" si es de la rama "else"
f(a3)

Cuando se usa este sistema se dice que el programa está en forma SSA. En esta forma todas las cadenas de definición-uso (y sus duales de uso-definición) son inmediatas de obtener. Esto simplifica muchísimo esas transformaciones y optimizaciones mencionadas al inicio.

Por otra parte, las funciones φ se utilizan como funciones normales hasta que se quiera salir de la forma SSA. Tanto para convertir un programa en SSA como para salir de esta forma existen ya algorimos muy trillados. Quizás hablemos de ellos algún día ya que usan conceptos muy curiosos como las fronteras de dominio.