SSA — definición, propiedades y sabores
En programación, como en la vida real, los nombres son asideros útiles para entidades concretas. El mensaje central de este bloque es que tener nombres únicos para entidades distintas reduce la incertidumbre y la imprecisión.
Si uno oye una conversación sobre «Homero», sin más pistas de contexto no puede distinguir entre Homer Simpson y el poeta griego. En cuanto se menciona Springfield en lugar de Esmirna, la duda se resuelve. Si todo el mundo tuviera un nombre único, la confusión no habría sido posible.
12.1 Qué es SSA
La forma de asignación única estática (static single assignment form, SSA) es un convenio de nombrado para las posiciones de almacenamiento —las variables— en representaciones de bajo nivel de programas. El término estática indica que SSA se refiere a propiedades del texto del programa. Única se refiere a la propiedad de unicidad que SSA impone a los nombres. Y asignación significa definición de variable.
La definición más simple y menos restrictiva:
Existen variedades más especializadas de SSA que imponen restricciones adicionales, y este capítulo las recorre. Pero hay una propiedad que se cumple en todas, incluida la definición mínima anterior: la transparencia referencial (referential transparency). Como sólo hay una definición por variable en el texto, el valor de una variable es independiente de su posición en el programa.
Podemos refinar lo que sabemos de una variable a partir de las condiciones de rama —dentro del bloque que sigue a if (x == 0) sabemos algo más sobre x— pero el valor subyacente de x no cambia en ese if. Los programas escritos en lenguajes funcionales puros son referencialmente transparentes, lo que los hace más dóciles al razonamiento matemático: el significado de una expresión depende sólo del de sus subexpresiones, y no del orden de evaluación ni de los efectos laterales de otras expresiones.
Un fragmento referencialmente opaco:
x = 1;
y = x + 1;
x = 2;
z = x + 1;
Un análisis ingenuo —e incorrecto— podría suponer que y y z son iguales, ya que tienen definiciones idénticas (x + 1). Pero el valor de x depende de si estamos antes o después de la segunda definición. Al pasar a SSA, el fragmento se vuelve transparente:
x1 = 1;
y = x1 + 1;
x2 = 2;
z = x2 + 1;
Ahora es evidente que y y z son iguales si y sólo si x₁ y x₂ lo son.
12.2 La función φ
La función φ es el concepto de SSA que hay que entender bien. Es una sentencia especial, una pseudo-asignación; algunos la llaman «una ficción notacional». Su propósito es fusionar valores procedentes de caminos de entrada distintos, en los puntos de confluencia del flujo de control.
Considérese este código y su CFG:
x = input(); +----------------+
if (x == 42) | x <- input() |
then | (x = 42)? |
y = 1; +---+--------+---+
else | |
y = x + 2; A v v B
end +---------+ +-----------+
print(y); | y <- 1 | | y <- x+2 |
+----+----+ +-----+-----+
| |
+------+------+
v
+-------------+
| print(y) |
+-------------+
Hay una definición distinta de y en cada rama, luego múltiples definiciones alcanzan el print en el punto de confluencia. Al pasar a SSA, se renombran como y₁ e y₂, pero el print podría usar cualquiera de las dos según el resultado del condicional. La función φ introduce una variable nueva, y₃, que toma el valor de y₁ o de y₂:
x = input(); +----------------+
if (x == 42) | x <- input() |
then | (x = 42)? |
y1 = 1; +---+--------+---+
else | |
y2 = x + 2; A v v B
end +---------+ +-----------+
y3 = phi(y1, y2); | y1 <- 1 | | y2 <- x+2 |
print(y3); +----+----+ +-----+-----+
| |
+------+------+
v
+--------------------------+
| y3 <- phi(A: y1, B: y2) |
| print(y3) |
+--------------------------+
Las funciones φ se colocan en los puntos de confluencia, es decir, al principio de los bloques básicos con más de un predecesor. Una φ en el bloque b tiene n parámetros si hay n caminos de entrada a b. Su comportamiento es seleccionar dinámicamente el valor del parámetro asociado al camino que realmente se ha ejecutado.
Nótese que el CFG de arriba usa una sintaxis más explícita de lo habitual, asociando cada etiqueta de bloque predecesor Bᵢ con el nombre SSA correspondiente aᵢ, es decir, a₀ = φ(B₁: a₁, …, Bₙ: aₙ). De aquí en adelante se omiten las etiquetas cuando no hay ambigüedad.
Tres precisiones importantes:
Las φ de una misma cabecera de bloque se ejecutan en paralelo, simultáneamente y no en secuencia. Esta distinción se vuelve crítica cuando el destino de una φ coincide con el origen de otra, cosa que ocurre a menudo tras optimizaciones como la propagación de copias. Al eliminar las φ en la fase de destrucción de SSA, hay que secuencializarlas con operaciones de copia; el capítulo «13» explica cómo, y por qué hacerlo mal produce código incorrecto.
Las φ no son directamente ejecutables, porque el camino de flujo de control que lleva a la φ no está codificado como entrada suya. Esto es tolerable, ya que las φ sólo se usan durante el análisis estático y se eliminan antes de cualquier ejecución. Existen extensiones ejecutables —las funciones φif y γ del capítulo «16»— que llevan un parámetro extra codificando la dependencia de control implícita.
SSA no es asignación única dinámica. SSA no impide que una variable se asigne muchas veces durante la ejecución. Sólo restringe el texto del programa.
Un ejemplo con bucle lo aclara:
x = 0; +--------------------+
y = 0; | x1 <- 0 |
| y1 <- 0 |
+---------+----------+
|
v
+--> +--------------------------+
| | x2 <- phi(x1, x3) |
| | y2 <- phi(y1, y3) |
while (x < 10) { | | (x2 < 10)? |
| +------+-------------+-----+
| | si | no
| v |
y = y + x; | +--------------+ |
x = x + 1; | | y3 <- y2+x2 | |
} | | x3 <- x2+1 | |
+----+--------------+ |
v
print(y); +--------------------+
| print(y2) |
+--------------------+
Las dos φ de la cabecera fusionan las definiciones de antes del bucle, para la primera iteración, con las del cuerpo, para las siguientes. Y x₃ e y₃ se redefinen dinámicamente con valores nuevos en cada iteración: eso es perfectamente compatible con SSA.
12.3 Cadenas def-use y use-def
Bajo SSA, cada variable se define una sola vez. Las cadenas def-use (def-use chains) proporcionan, para la única definición de una variable, el conjunto de todos sus usos. Y una cadena use-def, que bajo SSA consiste en un solo nombre, especifica unívocamente la definición que alcanza cada uso.
SSA simplifica ambas de dos maneras.
Combina la información lo antes posible. En código no-SSA, la cadena def-use requiere tantas fusiones como usos tenga la variable; en SSA, la fusión se hace una sola vez, en la φ:
(a) no-SSA (b) SSA
x <- 1 x <- 2 x1 <- 1 x2 <- 2
\ / \ /
\ / x3 <- phi(x1, x2)
\ / | |
y <- x+1 z <- x+2 y <- x3+1 z <- x3+2
Las cadenas use-def salen gratis. Como es inmediato asociar cada variable con su única operación de definición, las cadenas use-def se representan y se mantienen prácticamente sin coste. Eso constituye el esqueleto del llamado grafo SSA (capítulo «16»), de forma que al trabajar con un programa en SSA las cadenas use-def se dan implícitamente por supuestas. La representación explícita simplifica la propagación hacia atrás, lo que favorece algoritmos como la eliminación de código muerto.
Para la propagación hacia adelante, las cadenas def-use son exactamente las inversas, así que calcularlas es fácil y mantenerlas cuesta poco. Pero incluso sin ellas, algoritmos ligeros como el plegado de copias (copy folding) son posibles: basta una pasada que procese las operaciones en orden topológico del CFG forward —la reducción acíclica del CFG obtenida eliminando las aristas de retroceso—, con lo que la mayoría de definiciones se procesan antes que sus usos. Cuando en una cabecera de bucle una φ encuentra un argumento no procesado, se hace una fusión conservadora.
12.4 Minimalidad
La construcción de SSA es un proceso en dos fases: colocación de las φ y después renombrado. La minimalidad es una propiedad del código con φ ya insertadas, pero antes del renombrado.
Una definición D de la variable v alcanza un punto p del CFG si existe un camino de D a p que no pasa por otra definición de v. Decimos que un código tiene la propiedad de definición alcanzable única si ningún punto del programa puede ser alcanzado por dos definiciones de la misma variable. Bajo esa hipótesis, la propiedad de minimalidad establece que el número de φ insertadas es mínimo.
Se caracteriza con los conjuntos de confluencia del capítulo «4». Sean n₁ y n₂ bloques distintos. Un bloque n₃, que puede coincidir o no con ellos, es nodo de confluencia de n₁ y n₂ si existen al menos dos caminos no vacíos, de n₁ a n₃ y de n₂ a n₃, tales que n₃ es el único bloque que aparece en ambos. Dado un conjunto S, J(S) es el conjunto de nodos de confluencia de al menos dos elementos de S.
Intuitivamente, el conjunto de confluencia corresponde a la colocación de las φ: si Dv es el conjunto de bloques que contienen definiciones de v, deberían instanciarse φ en todos los bloques de J(Dv). Y como las φ son a su vez puntos de definición, habría que insertar más en J(Dv ∪ J(Dv)).
12.5 SSA estricta y propiedad de dominancia
Un procedimiento es estricto (strict) si toda variable se define antes de usarse a lo largo de todo camino desde la entrada hasta la salida; en caso contrario es no estricto. Algunos lenguajes, como Java, imponen la estrictez por definición; otros, como C y C++, no.
Bajo SSA, como hay una única definición estática por variable, la estrictez equivale a la propiedad de dominancia: cada uso de una variable está dominado por su definición.
Añadir una pseudo-definición indefinida de cada variable en el nodo de entrada del procedimiento garantiza la estrictez. La propiedad de definición alcanzable única exige que cada punto del programa sea alcanzado por exactamente una definición —o pseudo-definición— de cada variable. Si un punto U es un uso de v, la definición alcanzable D lo dominará; de lo contrario existiría un camino desde la entrada hasta U que no incluye a D, y habría que insertar una φ en J(r, D).
(a) codigo no estricto (b) SSA con dominancia
a <- ... b <- ... a0 <- ... b0 <- ...
\ / \ /
\ / a1 <- phi(a0, _|_)
\ / b1 <- phi(_|_, b0)
... <- a ... <- b ... <- a1 ... <- b1
La llamada SSA mínima (minimal SSA) es la variedad que satisface a la vez la minimalidad y la dominancia. Se obtiene colocando las φ de v en J(Dv, r) usando el formalismo de la frontera de dominancia. Si el procedimiento original era no estricto, la conversión a SSA mínima produce una representación estricta —lo que no arregla los errores por variables sin inicializar del programa original, sólo hace estricta la representación—.
La SSA con propiedad de dominancia es útil por muchas razones, todas derivadas de las propiedades estructurales de los rangos de vida:
- El rango de vida de cada variable es un subárbol del árbol de dominadores. De ahí se sigue un método rápido para consultar si una variable está viva en un punto, y un algoritmo sin iteración para calcular conjuntos de vivas (capítulo «23»).
- Dos rangos de vida se intersecan si y sólo si uno contiene la definición del otro. Eso da algoritmos eficientes para comprobar interferencia (capítulo «13»).
- El grafo de intersección de rangos de vida es un grafo cordal (chordal graph). Los grafos cordales son importantes porque varios problemas NP-completos en grafos generales tienen solución lineal en ellos, incluida la coloración. Como la asignación de registros se expresa como coloración del grafo de interferencia, la cordalidad simplifica enormemente el problema: un simple recorrido del árbol de dominadores —un tree scan— colorea todas las variables sin necesidad de construir explícitamente el grafo de interferencia (capítulo «23»).
Un aviso: la propiedad de dominancia se puede romper con la propagación de copias. En el ejemplo anterior, el argumento a₁ de la copia a₂ = φ(a₁, ⊥) puede propagarse y toda ocurrencia de a₂ sustituirse por a₁; la φ identidad resultante se elimina y volvemos al código inicial, que sigue siendo SSA pero ya no es estricto. Volver a hacer estricto un código SSA cuesta aproximadamente lo mismo que construir SSA, aunque en la práctica la «estrictificación» afecta a pocas variables y a una región limitada del CFG, y la actualización incremental del capítulo «14» lo resuelve con mucho menos esfuerzo.
12.6 SSA podada
Un inconveniente de la SSA mínima es que puede colocar φ para una variable en un punto del CFG donde la variable no estaba viva antes de la conversión. Muchos análisis y optimizaciones, en particular la asignación de registros, sólo se interesan por la región donde la variable está viva.
La SSA podada (pruned SSA) mantiene la minimalidad y la dominancia, pero cambia la condición: cada punto de uso debe ser alcanzado por exactamente una definición, en lugar de cada punto del programa. Bajo SSA mínima, las φ de v se colocan en J(S, r); bajo SSA podada, se suprime la instanciación si v no está viva a la entrada del bloque. Hay dos formas de conseguirlo: hacer un análisis de variables vivas antes de construir SSA y usarlo para suprimir φ, o construir SSA mínima y luego eliminar las φ muertas con eliminación de código muerto.
La ventaja es que hay muchas menos φ. Pero la SSA no podada tiene también sus usos:
(a) SSA no podada (b) tras value numbering
if (P1) if (P1)
Y1<-1 Y2<-X1 Y1<-1 Y2<-X1
..<-Y1 ..<-Y2 ..<-Y1 ..<-Y2
Y3 <- phi(Y1, Y2) Y3 <- phi(Y1, Y2)
... ...
if (P1)
Z1<-1 Z2<-X1
Z3 <- phi(Z1, Z2)
... <- Z3 ... <- Y3
La φ que define Y₃ es muerta —Y₁ e Y₂ sólo se usan en sus bloques de definición— y la SSA podada la eliminaría. Pero al conservarla, el value numbering del capítulo «22» descubre que Y₃ y Z₃ calculan lo mismo y elimina toda la segunda estructura.
12.7 SSA convencional y transformada
En muchos esquemas de asignación de registros por coloración, la asignación se hace con granularidad de web: la unión maximal de cadenas def-use que comparten un uso o una definición. La conversión a SSA mínima reemplaza cada web de una variable v por unos cuantos nombres vᵢ. En SSA podada, esos nombres particionan el rango de vida de la web.
Definimos las φ-webs así: x e y están φ-relacionados si están referenciados por la misma función φ, es decir, si son parámetros suyos o su destino. La clausura transitiva de esta relación es una relación de equivalencia que particiona las variables del procedimiento. Para código SSA recién construido, las φ-webs se corresponden exactamente con las webs de registro del código original.
- La SSA convencional (conventional SSA, C-SSA) es la forma SSA en la que cada φ-web está libre de interferencia.
- La SSA transformada (transformed SSA, T-SSA) es aquella en la que alguna variable de una misma φ-web interfiere con otra.
Muchas optimizaciones —la propagación de copias, señaladamente— convierten C-SSA en T-SSA:
(a) codigo original (b) SSA convencional (c) SSA transformada
a <- ... a1 <- ... a1 <- ...
tmp <- a tmp <- a1
a<-a a<-a+1 a2<-a1 a3<-a1+1 a3<-a1+1
... <- a a4 <- phi(a2, a3) a4 <- phi(a1, a3)
... <- tmp ... <- a4 ... <- a4
... <- tmp ... <- a1
En (b) las φ-webs son {a₁} y {a₂, a₃, a₄}, y ninguna interfiere consigo misma. En (c), tras propagar la copia a₂ ← a₁, la variable a₁ interfiere con a₂, a₃ y a₄, porque se define arriba y se usa al final.
Destruir SSA convencional es trivial: cada φ-web se reemplaza por una sola variable, se renombran todas sus definiciones y usos, y se eliminan las φ correspondientes. Destruir SSA no convencional requiere pasar antes por la convencional, insertando copias que disocien las variables que interfieren. Como esas copias habrá que insertarlas de todos modos, para transformaciones a nivel máquina —asignación de registros, planificación— T-SSA da una visión inexacta del uso de recursos.
Comprobar si una φ-web dada está libre de interferencia —y devolverla a esa condición si no lo está— puede hacerse en tiempo lineal en el tamaño de la φ-web, en lugar del cuadrático ingenuo; el capítulo «13» lo detalla. Aun así, la mayoría de compiladores actuales optan por no mantener la propiedad convencional.
12.8 Una noción más fuerte de interferencia
Hasta aquí, dos variables interfieren si sus rangos de vida se intersecan. Es suficiente para la corrección, pero es una definición restrictiva y puramente estática. La noción definitiva de interferencia —indecidible, por reducción al problema de la parada— debería decidir si existe alguna ejecución en la que dos variables distintas contengan simultáneamente valores diferentes. Caben varias extensiones estáticas.
Primera: caminos mutuamente excluyentes. En el grafo de doble rombo de la «sección 12.5 · SSA estricta y propiedad de dominancia», si las dos condiciones son la misma, el programa pasa o bien por la definición y el uso de a, o bien por los de b, nunca por ambos. Luego basta una sola posición de almacenamiento. Un refinamiento sencillo del test de interferencia consiste en comprobar si una de las variables está viva en el punto de definición de la otra. Con esa noción, a y b del código no estricto no interferirían, mientras que a₁ y b₁ de su forma SSA sí. Esto ilustra que la división de rangos de vida que hace falta para cumplir la dominancia puede empeorar la precisión de los análisis posteriores. Para código SSA con propiedad de dominancia, ambas nociones son estrictamente equivalentes: dos rangos de vida se intersecan si y sólo si uno contiene la definición del otro.
Segunda: valores iguales. Si se puede demostrar que u y v tienen siempre el mismo valor allí donde ambas están vivas, no interfieren realmente. El criterio es en general indecidible, pero el global value numbering —muy fácil de implementar sobre SSA, capítulo «22»— hace un trabajo bastante bueno, especialmente cuando hay muchas copias de variable a variable, como ocurre tras una destrucción ingenua de SSA.
Esta noción refinada tiene una consecuencia importante: el grafo de interferencia deja de ser cordal, porque cualquier arista entre dos variables con vidas solapadas podría eliminarse por esta vía. Se gana precisión y se pierde el algoritmo lineal de coloración.
12.9 Cuatro mitos sobre SSA
| Mito | Realidad |
|---|---|
| SSA aumenta enormemente el número de variables | Algunas variedades introducen muchas menos que la formulación original. Ver 12.6 y 12.7 |
| La propiedad SSA es difícil de mantener | Hay técnicas sencillas de reparación de invariantes rotos por las optimizaciones. Ver capítulo «14» |
| La destrucción de SSA genera muchas copias | Existen algoritmos eficaces. Ver capítulo «13» |
| SSA es una forma de asignación única dinámica | No lo es: sólo restringe el texto, no la ejecución. Ver 12.2 |
12.10 SSA en el análisis de binarios
12.11 Lecturas
La noción de SSA mínima y su algoritmo eficiente son de Cytron, Ferrante, Rosen, Wegman y Zadeck (1991), que desarrollaron para ello la frontera de dominancia; el resultado J(S ∪ J(S)) = J(S) es posterior, con una demostración simple debida a Wolfe. La SSA podada es de Choi, Cytron y Ferrante (1991). Las nociones convencional y transformada son de Sreedhar et al. (1999). La explotación de la estrictez para destruir SSA rápidamente es de Budimlić et al. (2002).