SSA ( forma de asignación única estática ) es una representación intermedia utilizada por los compiladores , en la que a cada variable se le asigna un valor una sola vez . Las variables del programa de origen se versionan, generalmente agregando un sufijo, de modo que cada asignación se realice a una versión única de la variable. En la representación SSA, las cadenas DU ( def -use ) se definen explícitamente y contienen un solo elemento.
La vista SSA fue desarrollada por los investigadores de IBM Ron Cytron , Jeanne Ferrante , Barry Rosen , Mark N. Wegman y Ken Zadeck en la década de 1980.
Los compiladores de lenguajes de programación funcionales como Scheme , ML y Haskell suelen utilizar la representación CPS ( estilo de paso de continuación ) en lugar de SSA . Formalmente, estas representaciones son equivalentes, por lo que las optimizaciones y transformaciones formuladas en una de las representaciones pueden aplicarse a la otra.
Para el código en formato SSA, es más fácil y eficiente realizar muchos tipos de optimizaciones del compilador . Por ejemplo, en el siguiente código:
y := 1 y := 2 x := yes obvio para un humano que la primera asignación es innecesaria, ya que el valor de y usado en la tercera línea corresponde a la segunda asignación. Sin embargo, para resolver esto, el compilador tendría que recurrir al análisis de las definiciones de alcance . Pero con la representación de la SSA, se vuelve mucho más fácil:
y1 := 1 y2 := 2 x1 := y2SSA hace posible o simplifica enormemente los siguientes algoritmos de optimización:
La traducción del código de programa habitual a la representación SSA se logra reemplazando la variable del lado izquierdo con una nueva variable en cada operación de asignación. Para cada uso del valor de la variable, el nombre original se reemplaza con el nombre de la "versión" correspondiente al bloque base deseado. Considere el siguiente gráfico de flujo de control :
De acuerdo con la definición de SSA, en lugar de la variable x, crearemos dos nuevas variables x 1 y x 2 . A cada uno de ellos se le asignará un valor exactamente una vez. Del mismo modo, reemplazamos las variables restantes, después de lo cual obtenemos el siguiente gráfico:
Todavía no está claro qué valor de y se usará en el bloque inferior. Allí, el nombre y puede significar y 1 o y 2 . Para resolver ambigüedades de este tipo, se ha introducido una función Φ especial en SSA. Esta función crea una nueva versión de la variable y, a la que se le asignará el valor de y 1 o y 2 , según la rama de la que provenga el control.
No hay necesidad de usar la función Φ en la variable x, ya que solo una versión de x (a saber, x 2 ) "alcanza" el último bloque.
La función Φ no está realmente implementada; es simplemente una instrucción para que el compilador almacene todas las variables enumeradas en su lista de argumentos en el mismo lugar en la memoria (o registro ).
Una pregunta más general es si, dado un gráfico de flujo de control dado, es posible comprender dónde y para qué variables en la representación SSA es necesario insertar funciones Φ. La respuesta a esta pregunta se puede obtener con la ayuda de los dominadores .