τTau SolutionsForma SSA

Extensiones de SSA — GSA, Psi-SSA, HSSA y Array SSA

Avanzado · Actualizado el 16 de agosto de 2026

La forma SSA del capítulo «12» trata bien las variables escalares con nombre. Un binario, sin embargo, es casi todo memoria: accesos indirectos, campos de estructura, elementos de array, y variables locales que sólo existen como desplazamientos sobre rbp. Este capítulo recorre las extensiones que amplían SSA a ese territorio, y una de ellas —HSSA— es la que hace posible el análisis de memoria en un decompilador.

Las extensiones responden a limitaciones distintas de la forma básica:

Extensión Qué añade Para qué
SSI / e-SSA funciones σ en las bifurcaciones análisis hacia atrás y sensibles a la condición (cap. 15)
GSA funciones de puerta γ, μ, η representación ejecutable; análisis simbólico
Psi-SSA funciones ψ con predicados ejecución predicada, if-conversion
HSSA funciones μ y χ, variables virtuales aliasing y memoria indirecta
Array SSA φ de definición y arrays @ elementos de array y campos de objeto

De todas ellas, HSSA es la que importa en ingeniería inversa, y por eso ocupa la mayor parte del capítulo.

16.2 SSA y aliasing: las funciones μ y χ

La forma SSA hasheada (Hashed SSA, HSSA) es una extensión que representa eficazmente cómo afectan las relaciones de aliasing a un programa en forma SSA. Funciona igual de bien para el aliasing entre variables escalares y, más en general, para operaciones indirectas de carga y almacenamiento sobre posiciones de memoria arbitrarias, lo que permite aplicar uniformemente todas las optimizaciones basadas en SSA a variables locales y a áreas de memoria externas.

Conviene señalar desde el principio que HSSA es una técnica para representar los efectos del aliasing, no para detectarlo. Hace falta un pase separado de análisis de alias —capítulo «18»—, y la eficacia de HSSA depende directamente de la precisión de ese análisis.

Hay aliasing dentro de una unidad de compilación cuando una misma posición de almacenamiento puede accederse a través de «variables» distintas del programa. Ocurre de cuatro maneras:

  1. Cuando dos o más posiciones se solapan parcialmente. Es el caso de la construcción union de C, donde partes distintas del programa acceden a la misma posición con nombres distintos.
  2. Cuando una variable local se referencia mediante un puntero en una operación indirecta de memoria. Se puede acceder de dos formas: directamente por el nombre, e indirectamente por el puntero que guarda su dirección.
  3. Cuando la dirección de una variable local se pasa a una función, que puede entonces acceder indirectamente a ella.
  4. Cuando las posiciones tienen ámbito global y cualquier función puede accederlas; en ese caso toda llamada puede tocar cualquier global, salvo que el compilador aplique técnicas globales.

El problema real es que esos accesos son difíciles de predecir. Sólo en el primer caso el compilador sabe con exactitud cuándo ocurre cada acceso. En los demás, la situación se complica porque el acceso depende de la dirección efectivamente almacenada en la variable usada en la operación indirecta. Y eso importa porque toda optimización se ocupa del valor almacenado en cada variable y de dónde se usa. Si las variables pueden accederse en puntos imprevisibles, la única opción segura es tratarlas como volatile y no optimizarlas, lo que no es deseable.

La solución empieza por modelar formalmente los efectos de las definiciones y usos indirectos. Suponiendo hecho el análisis de alias, cada definición puede ser un operando MustDef, en el caso directo, o MayDef, en el indirecto; y cada uso, MustUse o MayUse. Se representan así:

  • χ (chi) representa un MayDef: una definición que puede modificar la variable.
  • μ (mu) representa un MayUse: un uso que puede leer la variable.

El argumento de μ es la variable potencialmente usada, lo cual es evidente. Menos evidente es que el argumento de χ es la propia variable asignada: eso expresa que χ sólo modifica potencialmente la variable, de modo que el valor original puede «fluir a través» de ella.

 (a) codigo C inicial      (b) tras insertar mu y chi        (c) tras phi y versionado

 1  i = 2                  1  i = 2                          1  i1 = 2
 2  if j then              2  if j then                      2  if j1 then
 3      ...                3      ...                        3      ...
 4  else                   4  else                           4  else
 5      f()                5      f() || mu(i)               5      f() || mu(i1)
 6      *p = 3             6      *p = 3 || i = chi(i)       6      *p = 3 || i2 = chi(i1)
                                                             7  i3 = phi(i1, i2)
 7  i = 4                  7  i = 4                          8  i4 = 4
 8  return                 8  return || mu(i)                9  return || mu(i4)
Insercion de mu y chi. En este programa *p podria aliasar con i, y la funcion f podria usar i indirectamente pero no alterarla.

El símbolo ‖ indica ejecución en paralelo con la instrucción que provocó la inserción. Idealmente, μ y χ van en paralelo a esa instrucción; las implementaciones reales suelen insertar las μ inmediatamente antes y las χ inmediatamente después, lo que además modela correctamente el efecto de las llamadas: la función llamada parece usar los valores antes de la llamada y modificarlos después.

El uso de μ y χ no altera la complejidad de transformar un programa a SSA: basta un pase previo que los inserte.

Y el resultado es notable. Gracias a la inserción sistemática de μ y χ, una asignación a cualquier variable escalar puede considerarse muerta con seguridad si la eliminación estándar de código muerto sobre SSA no la marca viva. En el ejemplo, el efecto lateral potencial de cualquier asignación a i, representado por la μ del return, permite detectar que la asignación a i₄ no es muerta. Y la asignación del valor 2 a i se habría considerado muerta de no ser por la llamada a f(), que potencialmente la usa —detectado a través de su μ—.

16.3 Versiones cero

Aplicar lo anterior tal cual en un compilador de producción sería terriblemente ineficiente. Las χ provocan una explosión del número de valores de las variables, lo que induce la inserción de más φ, que a su vez crean más versiones.

El problema de fondo es que las versiones introducidas por las χ son inútiles para la mayoría de optimizaciones: una definición por χ añade incertidumbre, porque el valor real tras ella puede ser el original o el asignado indirectamente.

La solución es factorizar todas las versiones inútiles en una sola, a la que se asigna el número 0 y se llama versión cero (zero version).

La noción de «inútil» se apoya en la de ocurrencia real de una variable: una definición o uso efectivo en el programa original. Las ocurrencias en μ, χ y φ no son reales. La idea es que las versiones sin ocurrencia real no influyen en la salida del programa: al deshacer SSA desaparecen del código, y como no aparecen directamente y su valor suele ser desconocido, distinguirlas es casi inútil.

La pérdida de información apenas tiene consecuencias. Como las variables con versión cero tienen valores inciertos, no poder distinguirlas afecta poco a las optimizaciones que operan sobre valores. Sólo hay un caso donde la pérdida se nota: una versión cero puede usarse en una μ y definirse en una χ que tenga como argumento una ocurrencia real; si alguna optimización elimina la μ, esa ocurrencia real se vuelve muerta y no se detectará, porque la χ se marca conservadoramente como no muerta. Es lo bastante raro en código real como para que las versiones cero compensen.

16.4 Variables virtuales

Lo anterior sólo se aplica a variables «regulares». Falta lo esencial: las posiciones de memoria arbitrarias accedidas indirectamente.

Considérese en C una estructura typedef struct { double x; double y; } point; y el código m = (p->x * p->x) + (p->y * p->y);. A ojo es evidente que x se accede dos veces y ambos accesos dan el mismo valor, así que el segundo podría eliminarse. El problema es que x e y no son variables regulares: p lo es, pero p->x y p->y son operaciones indirectas. Poner ese fragmento en SSA nos dice que el valor de p no cambia, pero no revela nada sobre los valores guardados en p->x y p->y. Los elementos de array sufren exactamente el mismo problema.

HSSA lo resuelve representando las posiciones destino de las operaciones indirectas mediante variables virtuales (virtual variables). Una variable virtual es una abstracción de un área de memoria, y aparece en HSSA gracias a la inserción de μ y χ: igual que cualquier otra variable, puede aliasar con un operando.

 (a) codigo inicial   (b) v* y w* aliasan con 3,5,7,8   (c) x* aliasa con 3; y* con 5,7,8

 1 p = b              1 p = b                           1 p = b
 2 q = b              2 q = b                           2 q = b
 3 *p = ...           3 *p=... || v*=chi(v*)            3 *p=... || x*=chi(x*)
                              || w*=chi(w*)
 4 p = p+1            4 p = p+1                         4 p = p+1
 5 ... = *p           5 ...=*p || mu(v*) || mu(w*)      5 ...=*p || mu(y*)
 6 q = q+1            6 q = q+1                         6 q = q+1
 7 *p = ...           7 *p=... || v*=chi(v*)            7 *p=... || y*=chi(y*)
                              || w*=chi(w*)
 8 ... = *q           8 ...=*q || mu(v*) || mu(w*)      8 ...=*q || mu(y*)
Dos elecciones distintas de variables virtuales para el mismo codigo.

Hay muchas formas posibles de elegir las variables virtuales. La única disciplina que impone HSSA es que cada operando indirecto de memoria esté asociado a una única variable virtual. En un extremo, habría una variable virtual por cada operación indirecta; el factorizado de asignaciones (assignment factoring) consiste en que una variable virtual represente varios operandos; en el otro extremo, la forma más factorizada tendría una sola variable virtual para todo el programa.

En (c) se ha supuesto que el análisis de alias ha demostrado que b y b+1 no aliasan, y se han elegido dos variables virtuales para las dos posiciones distintas. En el caso general, las variables virtuales pueden aliasar entre sí, como en (b).

Éste es el punto donde la calidad del análisis de punteros se convierte en calidad del análisis entero. Con un análisis de alias pobre, todo acabará en una sola variable virtual, todas las escrituras la matarán y no se podrá optimizar nada. Con uno bueno, cada campo de cada estructura tendrá su propia variable virtual y las optimizaciones sobre memoria funcionarán tan bien como sobre escalares.

16.5 HSSA

El último paso que da nombre a la forma es aplicar numeración global de valores (global value numbering, GVN — capítulo «22») a todo lo anterior. El GVN se implementa con una tabla hash que asigna un número de valor a cada expresión, de forma que dos expresiones con el mismo número calculan con seguridad el mismo valor. De ahí lo de «hasheada».

En HSSA, las variables escalares, las variables virtuales, las operaciones indirectas y las expresiones ordinarias viven todas en la misma tabla de valores y se tratan uniformemente. La consecuencia práctica es que la eliminación de redundancias funciona igual sobre p->x que sobre una variable local, que era el objetivo desde el principio.

16.6 Funciones de puerta y GSA

Cambiamos de familia. La función φ del capítulo «12» tiene un defecto: no es ejecutable, porque no codifica cuál de sus argumentos hay que elegir. Las funciones de puerta (gating functions) lo arreglan añadiendo la condición como argumento explícito. La forma resultante se llama GSA (Gated SSA):

  • γ(P, a, b) —a veces escrita φif— sustituye a la φ en los puntos de confluencia de un condicional: devuelve a si el predicado P es cierto y b si no.
  • μ(init, iter) aparece en las cabeceras de bucle: devuelve el valor inicial en la primera iteración y el valor de la iteración anterior después. (No confundir con la μ de HSSA; la colisión de nombres es histórica y desafortunada.)
  • η(P, valor) aparece en las salidas de bucle: selecciona el valor de la última iteración.

Las puertas se calculan con un análisis de flujo de datos que determina, para cada punto y cada variable, su definición alcanzable única y el conjunto de caminos que la alcanzan, abstraído como una expresión de caminos (path expression). Hay además una relación directa entre las puertas y las dependencias de control del capítulo «4»: partiendo de código en SSA estricta y convencional, las puertas de una φif se derivan de las dependencias de control de sus operandos.

La utilidad principal de GSA es el análisis simbólico bajo demanda. Tradicionalmente el análisis simbólico se hace propagando expresiones hacia adelante, lo cual es caro y produce mucha información inútil. Con GSA se pueden hacer sustituciones hacia atrás y bajo demanda. Considérese:

1  JMAX <- EXPR
2  if p then
3      J <- JMAX - 1
4  else
5      J <- JMAX
6  assert (J <= JMAX)

Con sustitución hacia adelante, para verificar la aserción hay que descubrir el valor simbólico de J empezando por la línea 1, y el resultado en la línea 6 es assert((if p then EXPR-1 else EXPR) ≤ EXPR). En programas reales estas expresiones se vuelven innecesariamente largas.

En GSA el programa es:

1  JMAX1 <- EXPR
2  if p then
3      J1 <- JMAX1 - 1
4  else
5      J2 <- JMAX1
6  J3 <- phi_if(p, J1, J2)
7  assert (J3 <= JMAX1)

y la sustitución empieza en la línea 7 siguiendo los enlaces SSA desde J₃, saltándose todas las sentencias intermedias que no afectan:

J3 = phi_if(p, J1, J2)
   = phi_if(p, JMAX1 - 1, JMAX1)

y ahí se detiene, porque ya hay información suficiente: no hace falta sustituir JMAX₁ por EXPR. En programas no triviales esto reduce enormemente el número de sustituciones redundantes.

Las funciones de puerta permiten además construir representaciones basadas únicamente en dependencias de datos, sin CFG. El grafo de dependencia de valor y estado (Value State Dependence Graph, VSDG) es una de ellas: un grafo dirigido G = (N, EV, ES, ℓ, N₀, N∞) con nodos de operación, nodos de bucle y de confluencia, aristas de dependencia de valor EV y aristas de dependencia de estado ES. Estas últimas son las que ordenan las operaciones con efectos laterales —lecturas y escrituras de memoria, llamadas— que las dependencias de valor no ordenan por sí solas.

16.7 Psi-SSA

En arquitecturas con ejecución predicada —ARM en modo clásico, Itanium, muchos DSP— las instrucciones llevan un predicado que decide si su efecto se aplica. Tras la if-conversion del capítulo «23», varias instrucciones predicadas pueden definir la misma variable, lo que rompe SSA de una forma que la φ no sabe expresar: no hay un punto de confluencia del flujo de control donde colocarla, porque el flujo ya no se bifurca.

Psi-SSA introduce la función ψ, que combina definiciones predicadas de una misma variable:

x = ψ(p₁ ? x₁, p₂ ? x₂, …, pₙ ? xₙ)

donde cada argumento va guardado por su predicado. La semántica es tomar el valor del último argumento cuyo predicado sea cierto. Su destrucción —psi-normalize seguido de psi-web— es análoga a la de la φ pero teniendo en cuenta los predicados.

16.8 Array SSA

Array SSA resuelve un problema complementario al de las variables virtuales: cómo tratar los elementos de un array como valores individuales sin explotar. La idea es asociar a cada array A un array auxiliar A@ que registra, para cada elemento, el índice de la última definición que lo escribió. La asignación A[i] = v genera una nueva versión de A mediante una φ de definición (definition-φ, dφ) que fusiona el elemento recién escrito con el estado anterior del array; en los puntos de confluencia se usan además φ ordinarias, llamadas aquí de control.

Con esa maquinaria se puede hacer propagación dispersa de constantes sobre elementos de array —descubriendo, por ejemplo, que A[3] vale siempre 7— y, extendiendo la idea a objetos, eliminación de cargas redundantes, apoyada en dos análisis auxiliares: definitely-same y definitely-different sobre los índices.

16.9 Por qué HSSA es la extensión que importa en RE