Propagación dispersa — SSA, SSI y SCCP

Operativo · Actualizado el 16 de agosto de 2026

El análisis de flujo de datos del capítulo «6» asocia información a cada pareja (variable, punto del programa). Este capítulo muestra que, bajo SSA, buena parte de esa información es redundante, y que eliminarla no sólo ahorra memoria y tiempo sino que además, combinada con la alcanzabilidad, mejora la precisión.

15.1 Denso frente a disperso

Considérese el problema de análisis de rangos —estimar el intervalo de valores que puede tomar cada variable entera— sobre este programa, con los puntos de programa numerados de 0 a 7:

0:
1:   i <- 0
2:   s <- 0
3:   while (i < 100) do
4:       i <- i + 1
5:       s <- s + i
6:   return s
7:

Una implementación tradicional encuentra, para cada pareja (v, p), el intervalo de valores que v puede tomar en p. A eso lo llamaremos análisis denso (dense):

punto	`[i]`	`[s]`
0	⊤	⊤
1	`[0,0]`	⊤
2	`[0,0]`	`[0,0]`
3	`[0,100]`	`[0,+∞)`
4	`[100,100]`	`[0,+∞)`
5	`[0,99]`	`[0,+∞)`
6	`[0,100]`	`[0,+∞)`
7	`[0,100]`	`[0,+∞)`

El enfoque denso conserva muchísima información redundante. Aquí, por ejemplo, [i]₁ = [i]₂, [s]₅ = [s]₆ y [i]₆ = [i]₇. La redundancia aparece porque muchas funciones de transferencia son la identidad: una instrucción que ni define ni usa una variable no aporta nada sobre ella.

El objetivo del análisis disperso (sparse analysis) es cortocircuitar las funciones de transferencia identidad, agrupando puntos de programa contiguos ligados por identidades en regiones más grandes. Y si la información asociada a una variable es invariante a lo largo de todo su rango de vida, entonces se puede ligar la información a la variable misma: sustituir todas las variables de restricción [v]_p por una sola [v], para cada v y todo p ∈ live(v).

Eso es exactamente lo que SSA proporciona. Al dividir los rangos de vida de forma que cada nombre se defina una sola vez, SSA garantiza que la información sea invariante a lo largo del rango de vida de cada nombre —al menos para los análisis que extraen información en los puntos de definición—.

15.2 El grafo SSA

El análisis de flujo de datos bajo SSA se apoya en una representación específica, el grafo SSA, que se parece a las cadenas def-use tradicionales. Sus nodos son las operaciones del programa, incluidas las φ, que se representan con nodos propios. Sus aristas conectan la única definición de una variable con todos sus usos; es decir, representan dependencias verdaderas de datos, no flujo de control.

   (a) codigo SSA          (b) grafo SSA             (c) CFG

   1: y1 <- 6         3: x1<-4    4: x2<-5           1: y1 <- 6
   2: if (...) then         \       /                     |
   3:     x1 <- 4            \     /                 2: if (...)
      else               5: x3 <- phi(x1,x2)          /        \
   4:     x2 <- 5                 |      1: y1<-6    3: x1<-4  4: x2<-5
   5: x3 <- phi(x1,x2)            |       /               \      /
   6: z1 <- x3 + y1        6: z1 <- x3 + y1          5: x3 <- phi(x1,x2)
                                                          |
                                                     6: z1 <- x3 + y1

Un programa en SSA, su grafo SSA y su CFG. Notese que en el grafo SSA la informacion va directamente de la definicion de y1 a su unico uso.

Supóngase que queremos propagar información desde la asignación de y₁, al principio, hasta su único uso, al final. La representación CFG obliga a pasar por varios puntos intermedios que sólo tienen que ver con x₁, x₂ y x₃, y son por tanto irrelevantes para y₁. El grafo SSA propaga la información directamente de la definición al uso, sin pasos intermedios. Y al mismo tiempo, el punto de confluencia del flujo de control queda correctamente representado por la φ que define x₃.

Ahora bien, el grafo SSA captura las dependencias de datos y los puntos de confluencia relevantes, pero carece de información sobre las demás dependencias de control. Si en el ejemplo la condición del if fuera siempre falsa, la φ seleccionaría siempre x₂, cuyo valor es la constante 5; con el grafo SSA solo no se puede deducir. Por eso el algoritmo que sigue usa los dos grafos a la vez.

15.3 El motor de propagación dispersa

Un marco de propagación dispersa bajo SSA consta de cuatro ingredientes, en lugar de los tres del capítulo «6»:

un retículo completo que representa el espacio de propiedades,
un conjunto de funciones de transferencia para las operaciones,
el grafo de flujo de control, que captura el flujo de ejecución,
el grafo SSA, que representa las dependencias de datos.

Se busca de nuevo la solución de punto fijo con un algoritmo de lista de trabajo, pero la información no se propaga por las aristas del CFG sino por las del grafo SSA. Para los usos ordinarios la propagación es directa, ya que cada uso recibe su valor de una única definición. Sólo hay que tener cuidado con las φ, que seleccionan entre sus operandos según la arista de control entrante: ahí se combina con el supremo del retículo.

Como la información se propaga por aristas SSA con un único origen, basta almacenar la información en el nodo del grafo SSA. Los conjuntos in y out del enfoque tradicional se vuelven innecesarios, porque las φ ya proporcionan el amortiguamiento que hacía falta. Y el CFG se usa para llevar la cuenta de qué operaciones son inalcanzables en toda ejecución y pueden ignorarse.

El algoritmo maneja dos listas de trabajo:

1. Inicializacion
   - marcar toda arista del CFG como NO ejecutable
   - CFGWorkList := aristas salientes del nodo inicial del CFG
   - SSAWorkList := vacia

2. Extraer el elemento superior de una de las dos listas.

3. Si el elemento es una arista del CFG:
   - marcarla como ejecutable
   - visitar toda phi asociada al nodo destino
   - si el nodo destino se alcanza por primera vez via CFGWorkList,
     visitar todas sus operaciones
   - si el nodo destino tiene una unica arista saliente no ejecutable,
     anadirla a CFGWorkList

4. Si el elemento es una arista del grafo SSA, procesar la operacion destino:
   a. si es una phi, visitarla
   b. si no, examinar el indicador de ejecutable de las aristas de entrada
      del nodo CFG correspondiente; visitarla si alguna es ejecutable

5. Repetir desde 2 hasta que ambas listas esten vacias.

y la operación de visita:

Visitar una operacion:

1. Propagar la informacion segun el tipo de operacion:
   a. phi:
      combinar la informacion de los operandos CUYA ARISTA DE CONTROL
      CORRESPONDIENTE ESTA MARCADA COMO EJECUTABLE
   b. salto condicional:
      examinar la condicion con la informacion disponible de sus operandos;
      determinar las aristas salientes cuya condicion puede satisfacerse;
      anadir a CFGWorkList las que no estaban marcadas ejecutables
   c. resto de operaciones:
      aplicar su funcion de transferencia

2. Si la informacion de la operacion ha cambiado, anadir a SSAWorkList
   todas las aristas salientes del grafo SSA de esa operacion.

La CFGWorkList lleva la cuenta de las aristas del CFG que se han descubierto ejecutables, es decir, aquéllas en las que el análisis no puede descartar que exista una ejecución que las recorra. Cuando una arista se marca ejecutable hay que reevaluar todas las φ de su nodo destino, porque hasta ese momento el paso 1a de la visita estaba descartando el operando correspondiente. Y si es la primera arista entrante que se marca ejecutable, hay que evaluar además todas las operaciones del nodo; sólo la primera vez, porque a partir de ahí el paso 4b dispara la reevaluación automáticamente a través del grafo SSA.

15.4 SCCP: propagación de constantes condicional dispersa

La instancia más conocida de este esquema es la propagación de constantes condicional dispersa (sparse conditional constant propagation, SCCP), de Wegman y Zadeck. Vale la pena ver el ejemplo de la «sección 15.2 · El grafo SSA» en los dos escenarios.

Caso 1: la condición no se puede evaluar estáticamente. Hay que suponer que ambos sucesores son alcanzables, así que todas las aristas del CFG acaban marcadas como ejecutables. Eso dispara la evaluación de las asignaciones constantes a x₁, x₂ e y₁, que resultan valer 4, 5 y 6. Esa información nueva dispara la reevaluación de la φ de x₃: como ambas aristas entrantes están marcadas ejecutables, se combina 4 ⊔ 5 = ⊤, es decir, no se sabe. Finalmente se reevalúa z₁, que también resulta ⊤.

Caso 2: la condición es siempre falsa. Ni la arista que lleva a la asignación de x₁ ni su arista saliente hacia la φ se marcan ejecutables. En consecuencia, la reevaluación de la φ considera sólo el operando x₂, que vale 5. Y entonces z₁ = 5 + 6 = 11, constante.

  (a) todo el codigo alcanzable        (b) con codigo inalcanzable

   x1 <- 4      x2 <- 5                 x1 <- 4       x2 <- 5
    (x1, 4)      (x2, 5)                (inalcanz.)    (x2, 5)
        \        /                            \        /
     x3 <- phi(x1, x2)     y1 <- 6         x3 <- phi(x1, x2)    y1 <- 6
        (x3, T)             (y1, 6)           (x3, 5)            (y1, 6)
             \             /                       \            /
           z1 <- x3 + y1                          z1 <- x3 + y1
              (z1, T)                                (z1, 11)

Los dos escenarios de SCCP sobre el mismo programa.

Ésta es la razón del adjetivo condicional: el análisis no se limita a propagar constantes, sino que usa las constantes que descubre para descartar ramas, y las ramas descartadas para descubrir más constantes. Los dos procesos se refuerzan mutuamente hasta el punto fijo, y el resultado es estrictamente más preciso que hacer primero propagación de constantes y luego eliminación de código muerto, o al revés, por muchas veces que se alternen.

Formalización

Coste de la propagación dispersa

Cada arista del grafo SSA se procesa al menos una vez, cuando la operación de su definición resulta ejecutable. Después puede revisitarse varias veces, acotadas por la altura h del retículo. Las aristas del CFG, en cambio, se procesan como mucho una vez, porque una vez marcadas ejecutables ya no vuelven a la lista. De ahí la cota

O( |E_SSA| · h + |E_CFG| )

Compárese con la cota O(|E_CFG| · h) del algoritmo denso del capítulo «7». El tamaño del grafo SSA crece respecto del programa original, pero las mediciones indican que ese crecimiento es lineal, con lo que la cota resulta comparable.

En la práctica, sin embargo, el motor disperso supera claramente al denso, por dos razones. La primera es la propagación directa de la definición al uso, sin los costosos pasos intermedios sobre el CFG. La segunda es el consumo de memoria: en lugar de almacenar conjuntos in y out con el espacio de propiedades completo en cada punto del programa, basta asociar a cada nodo del grafo SSA la información de su variable.

15.5 Limitaciones

El enfoque tiene límites, derivados de que sólo propaga información entre operaciones ligadas por dependencia de datos. Eso impide modelar problemas de flujo de datos que necesitan llevar información a puntos que no están directamente relacionados por una definición ni por un uso de la variable.

El ejemplo canónico es el de expresiones disponibles del capítulo «6». Una expresión está disponible en un punto cuando se ha calculado y no se ha modificado después en todos los caminos que llevan allí; eso puede incluir puntos que son independientes de la expresión y de sus operandos, es decir, que ni definen ni usan ninguno de ellos. El grafo SSA no cubre esos puntos.

La segunda limitación es que, tal como está planteado, el análisis por grafo SSA sirve para problemas hacia adelante. Los problemas hacia atrás —variables vivas, por ejemplo— no encajan directamente, porque las φ están colocadas en los puntos de confluencia del flujo hacia adelante y no en los del flujo hacia atrás. Ése es exactamente el problema que resuelve la forma SSI.

15.6 SSI: cuando SSA no basta

El objetivo de un análisis de flujo de datos es descubrir hechos ciertos sobre un programa; llamemos información a cada hecho, es decir, a cada elemento del retículo. Muchos análisis clásicos ligan la información a parejas (variable, punto). Pero si un invariante se cumple para una variable v en todo punto donde v está viva, podemos asociar ese invariante directamente a v.

La cuestión decisiva es que una representación puede dar la propiedad SSI a unos análisis y no a otros, según de dónde extraiga cada análisis su información:

SSA da la propiedad SSI a todo análisis que obtiene información en los puntos de definición de las variables: propagación de constantes, propagación de copias, definiciones alcanzables. Por eso el motor de la «sección 15.3 · El motor de propagación dispersa» funciona con ellos.
SSA no la da a los análisis que extraen información de los puntos de uso —por ejemplo, la inferencia de clases en lenguajes orientados a objetos— ni a los que la extraen de las condiciones de rama. Para esos, la información asociada a una variable no es única a lo largo de su rango de vida ni siquiera bajo SSA.

Existen dos extensiones clásicas, ambas basadas en la misma estrategia —más división de rangos de vida—:

e-SSA (Extended SSA) da la propiedad SSI a los análisis que toman información de los puntos de definición y de las condiciones de prueba donde las variables se usan. Es lo que hace falta para el análisis de rangos con sensibilidad al control del capítulo «9»: tras if (i < 100), se crea un nombre nuevo i' en la rama verdadera, al que se puede asociar directamente el intervalo [-∞, 99].
SSI (Static Single Information form, de Ananian y Singer) da la propiedad a los análisis que extraen información de los puntos de definición y de los últimos puntos de uso. Para ello introduce, además de las φ en los puntos de confluencia, unas funciones σ en los puntos de divergencia del flujo de control: donde la φ fusiona, la σ separa.

        bifurcacion                        confluencia

        +--------------+                 +---+     +---+
        |  (i < 100)?  |                  \ /       \ /
        +---+------+---+                   \         /
            |      |                        \       /
   sigma:  i1     i2                         \     /
     i1 <- [-inf,99]                    +-----------------+
     i2 <- [100,+inf]                   | i3 <- phi(i1,i2)|
                                        +-----------------+

Donde se colocan las funciones phi y sigma. La phi va en la confluencia; la sigma, en la bifurcacion.

Formalización

Problemas de retículo particionado por variable

La clase de análisis a la que se aplica todo esto se llama de retículo particionado por variable (Partitioned Lattice per Variable, PLV).

Sea V = {v₁, …, vₙ} el conjunto de variables del programa. Considérese, sin pérdida de generalidad, un análisis hacia adelante que busca un máximo, escrito como sistema de ecuaciones que asocia a cada punto p un elemento del retículo L:

x_p = ⊓_{s ∈ preds(p)} F_s→p(x_s)

El análisis pertenece a la clase PLV si el retículo L puede escribirse como producto L = L_v₁ × … × L_vₙ de un retículo por variable, y las funciones de transferencia respetan esa partición: la componente de vᵢ en la salida depende sólo de las componentes de entrada, no de forma cruzada arbitraria.

Todo problema PLV puede resolverse de forma dispersa sobre una representación que le proporcione la propiedad SSI. Los ejemplos abundan: propagación de constantes, análisis de rangos, análisis de signos, inferencia de clases, detección de punteros nulos, análisis de taint. Los que no son PLV son los relacionales del capítulo «9» —octógonos, poliedros— y los que ligan información a expresiones en lugar de a variables, como expresiones disponibles.

15.7 Aplicación al análisis de binarios

En ingeniería inversa

Por qué SCCP es el algoritmo más rentable sobre un binario

De todos los análisis que aquí se tratan, SCCP es probablemente el que mejor relación resultado/coste ofrece en ingeniería inversa, y por tres razones.

Resuelve saltos indirectos. Un jmp [rax*8 + tabla] con rax constante se convierte en un salto directo. Cada salto indirecto que SCCP resuelve amplía el CFG, lo que a su vez alimenta más análisis: es la iteración del capítulo «4» en acción.

Elimina ramas muertas del ofuscador. Un predicado opaco cuyo valor sea constante hace que SCCP nunca marque como ejecutable la arista de la rama falsa. Todo lo que cuelga de ahí desaparece sin necesidad de un pase separado de eliminación de código muerto. Y como la eliminación de la rama puede volver constantes otras variables, el efecto se propaga: es habitual que un solo predicado opaco resuelto colapse decenas de bloques.

Es barato. Coste lineal en el tamaño del grafo SSA por la altura del retículo, y la altura del retículo de propagación de constantes es 2.

Sobre la forma SSI, dos observaciones prácticas. La primera: las funciones σ son exactamente lo que hace falta para explotar las banderas. Tras un cmp eax, 10 ; jbe, las dos ramas saben cosas distintas sobre eax, y sin σ no hay dónde escribirlas. Binary Ninja modela esto en su forma SSA de MLIL, y es la razón de que su análisis de rangos sea notablemente mejor que el de herramientas que no lo hacen.

La segunda: el análisis de variables vivas sobre un binario es un problema hacia atrás, y es el que se necesita para inferir los parámetros de una función sin símbolos (capítulo «10»). Ése es el caso de uso que justifica SSI en un decompilador, más que cualquier optimización.

15.8 Lecturas

La formulación general de los marcos monótonos está en el capítulo «6» y aquí no se repite.

El algoritmo SCCP original es de Wegman y Zadeck (1991); la forma SSI es de Ananian (1999) y Singer (2006); la forma e-SSA es de Bodik, Gupta y Sarkar (2000).