SSA form y TSA Form

Que tengan un feliz día, hoy como de costumbre venimos con un tema más que interesante relacionado a la representación de código intermedio, concepto que es de mucha utilidad sobre todo cuando hablamos de la portabilidad de las aplicaciones programadas en x lenguaje.
La forma de representación de código intermedio de la cual trataremos este día, es la forma SSA(SSA form).
Dicha forma de representación, tiene como principal objetivo optimizar el código intermedio generado por un determinado lenguaje. Y lo optimiza en el sentido en que cada variable que se use en el código fuente es asignada exactamente una vez. Y en qué forma lo hace?, pues la forma es simple, solamente se divide la variable en distintas versiones dependiendo del número de veces que cambie su valor durante la ejecución del programa, y a cada versión la identificamos por un subíndice y el nombre original de la variable.

Por ejemplo:

y = 1
y = 2
x = y

Sería visto de la siguiente forma, aplicando SSA form.

y1 = 1
y2 = 2
x1 = yz

Además en ejemplos como el siguiente:

x = 5
x = x-3
if x < 3 then
y=x*2
w=y
else
y=x-3
w=x-y
z=x+y

Ahora nosotros podemos apreciar que después de que se evalúa la expresión if, cuando se usa posteriormente la variable “y”, no sabemos qué valor tendría ésta, si y=x*2 ó y=x-3. Entonces para esto nos auxiliamos de una función llamada phi(Φ), que nos dice que variable “y” usar. Ahora veamos como quedaría después de aplicarle la forma SSA.

x1 = 5
x2 = x1-3
if x2 < 3 then
y1=x2*2
w1=y1
else
y2=x2-3
y3= Φ(y1,y2)
w2=x2-y3
z1=x2+y3


En referencia al surgimiento de este tipo de IR(Intermediate Representation), les queremos comentar que ésta fue desarrollada por investigadores de IBM en la década de los 80s.

Ahora daremos un ejemplo, en el cual vamos a optimizar el código intermedio para alguna de las expresiones aritméticas de nuestro proyecto:

Si tuviéramos el siguiente código:

h=20
i=30
while(h>50) {
i=i+1
h=h+i
}

La representación en SSA form seria:

h0=20
i0=30
if (h0<=50) goto L0
L1: i1= Φ(i0,i2)
h1= Φ(h0,h2)
i2=i1+1
h2=h1+i2
if (i2>50) goto L1
L0: i3= Φ(i0,i2)
h3= Φ(h0,h2)

Como ustedes pueden ver, el valor de las variables i1 y h1, se obtiene haciendo uso de nuestra función phi, la cual la primera vez que entra al ciclo while toma el valor de i0 y h0, respectivamente. Pero después de la primera iteración, tomarían el valor de i2 y h2, de igual forma.

Espero que hayan comprendido la idea de este tipo de IR, entretanto, enseguida hablaremos de SafeTSA, la cual es otro tipo de IR.