Construcción avanzada y reconstrucción incremental

Avanzado · Actualizado el 16 de agosto de 2026

El algoritmo del capítulo «13» precalcula la frontera de dominancia de todos los nodos, y el tamaño total de esas fronteras puede ser cuadrático en el número de nodos. Este capítulo presenta dos algoritmos que evitan ese coste, y después aborda un problema distinto y muy práctico: qué hacer cuando una transformación rompe la forma SSA y hay que repararla sin reconstruirla entera.

Usaremos este CFG de ejemplo, con Defs(v) = {1, 3, 4, 7}:

Sus aristas son 1→2, 2→3, 2→11, 3→4, 3→5, 3→8, 4→5, 5→6, 6→7, 7→2, 8→9, 9→6, 9→10 y 10→8. Los nodos 1, 3, 4 y 7 definen v; los nodos 9 y 11 la usan.

                       1            profundidad 0
                       |
                       2            profundidad 1
                      / \
                     3   11         profundidad 2
                  /  |  \  \
                 4   5   6   8      profundidad 3
                         |   |
                         7   9      profundidad 4
                             |
                             10     profundidad 5

Arbol de dominadores del CFG de ejemplo, anotado con la profundidad de cada nodo. Las aristas dibujadas son las D (dominancia).

Las aristas J —las del CFG cuyo origen no domina estrictamente al destino— son cinco: 4→5, 5→6, 7→2, 9→6 y 10→8. El DJ-graph es la superposición de las dos figuras: el árbol de dominadores más esas cinco aristas.

14.1 Una propiedad clave de los DJ-graphs

La profundidad (depth) de un nodo es su distancia a la raíz en el árbol de dominadores.

Formalización

Las aristas DF nunca bajan

Una arista DF nunca va a una profundidad mayor: si (x, z) es una arista DF, entonces z.depth ≤ x.depth.

Intuición. Supóngase que hubiera una arista DF de 8 a 7 en el ejemplo. Entonces existiría un camino de 3 a 7 pasando por 8 sin pasar por 6, lo que contradice que 6 domine a 7. ∎

La consecuencia es operativa: para calcular DF(x) basta bajar por el árbol de dominadores desde x y, en cada nodo visitado y, mirar las aristas J que salen de y hacia nodos z con z.depth ≤ x.depth. Formalmente:

DF(x) = { z : ∃ y ∈ dominated(x) ∧ (y → z) ∈ aristas J ∧ z.depth ≤ x.depth }

donde dominated(x) = { y : x dom y }.

En el ejemplo, para calcular DF(8) se recorre el subárbol dominado por 8, que es {8, 9, 10}, y se encuentran las aristas J 10→8 (con 8.depth = 3 ≤ 3 ✓) y 9→6 (con 6.depth = 3 ≤ 3 ✓). Luego DF(8) = {6, 8}.

14.2 Cálculo de DF⁺ de abajo arriba

La idea anterior se extiende al cálculo de DF⁺ de un conjunto de nodos, y con una observación adicional se vuelve eficiente.

Observación. Sea w un ancestro de x en el árbol de dominadores. Si DF(x) ya se ha calculado antes que DF(w), el recorrido de dominated(x) puede evitarse y usarse directamente DF(x) en el cálculo de DF(w), porque los nodos alcanzables desde dominated(x) ya están en DF(x). El recíproco no vale, así que el orden del cálculo es crucial: hay que calcular primero el de los nodos más profundos.

En el ejemplo, para calcular DF⁺({3, 8}): si se empieza por 3 se recorre todo su subárbol, incluido 8, y luego al procesar 8 se repite trabajo. Ordenando al revés —primero 8, luego 3— se evita revisitar el subárbol de 8. La fórmula que formaliza la reutilización:

DF(w) = { z ∈ DF(x) : z.depth ≤ w.depth } ∪ { z' : y ∈ subtree(w) \ subtree(x) ∧ (y → z') ∈ J ∧ z'.depth ≤ w.depth }

El algoritmo usa un simple vector de conjuntos, el OrderedBucket, indexado por profundidad, con dos operaciones: InsertNode(n), que inserta n en OrderedBucket[n.depth], y GetDeepestNode(), que devuelve un nodo de la profundidad mayor disponible.

Entrada: DJ-graph del programa, S: conjunto de nodos
Salida:  DF+(S)

DFplus := {}
foreach x in S do
    InsertNode(x)
    x.visited := false

while x := GetDeepestNode() do
    current_x := x
    x.visited := true
    Visit(x)
return DFplus

Visit(y):
    foreach J-edge  y -> z  do
        if z.depth <= current_x.depth then
            if z not in DFplus then
                DFplus := DFplus union {z}
                if z not in S then InsertNode(z)
    foreach D-edge  y -> y'  do
        if y'.visited = false then
            y'.visited := true
            Visit(y')

Los nodos se procesan de abajo arriba. Visit(x) baja por el DJ-graph evitando los nodos ya visitados, y de paso mira los destinos de las aristas J. Cuando la profundidad del destino de una arista J es menor o igual que la del nodo actual, ese destino se añade a DF⁺; y si no estaba en S, se inserta también en el OrderedBucket, porque las φ son a su vez definiciones.

Traza para S = Defs(v) = {1, 3, 4, 7}:

Paso	`OrderedBucket` por profundidad	`DF⁺`
inicio	0:{1} · 2:{3} · 3:{4} · 4:{7}	`{}`
`Visit(7)`	0:{1} · 1:{2} · 2:{3} · 3:{4}	`{2}`
`Visit(4)`	0:{1} · 1:{2} · 2:{3} · 3:{5}	`{2, 5}`
`Visit(5)`	0:{1} · 1:{2} · 2:{3} · 3:{6}	`{2, 5, 6}`
`Visit(6)`	0:{1} · 1:{2} · 2:{3}	`{2, 5, 6}`
`Visit(3)`, `Visit(2)`, `Visit(1)`	—	`{2, 5, 6}`

Merece la pena seguir el caso de Visit(3): al bajar por las aristas D acaba visitando 8, 9 y 10. Al llegar a 10 se considera la arista J 10→8, pero no se añade nada a DF⁺ porque 8.depth = 3 es mayor que 3.depth = 2. Ésa es la condición de profundidad haciendo su trabajo.

14.3 Cálculo de DF⁺ como problema de flujo de datos

Hay una tercera vía, que calcula la relación DF⁺ completa —para todos los nodos a la vez— formulándola como un problema de flujo de datos y resolviéndola iterativamente, sin construir explícitamente el DF-graph ni su clausura transitiva.

Formalización

Ecuación de flujo de datos para DF⁺

Ecuación. Considérese una arista J y → z. Entonces, para todo nodo x tal que x domina a y y x.depth ≥ z.depth:

DF⁺(x) = DF⁺(x) ∪ DF⁺(z) ∪ {z}

El sistema se resuelve con una pasada descendente por el DJ-graph. Para saber si hacen falta más pasadas antes de alcanzar el punto fijo se usa una condición de inconsistencia:

Condición de inconsistencia. Para una arista J y' → x, si y' no satisface DF⁺(y') ⊇ DF⁺(x), entonces y' es inconsistente.

Si tras una pasada descendente completa ningún nodo es inconsistente, todos han alcanzado su solución de punto fijo. Si alguno lo es, hacen falta más pasadas.

Esta formulación tiene una ventaja práctica notable: calcula DF⁺(x) para todos los nodos, no sólo para un conjunto S. Compensa cuando hay que insertar φ para muchas variables, porque el trabajo se comparte; el algoritmo de la «sección 14.2 · Cálculo de DF⁺ de abajo arriba» es preferible cuando S es pequeño.

La tercera alternativa, basada en el bosque de anidamiento de bucles, ya se presentó en el capítulo «4»: se calcula DF⁺ sobre el CFG forward acíclico y se añade la contribución de las aristas de retroceso mediante HLC, la relación de cabeceras de bucles contenedores, usando

DF⁺(S) = HLC(S) ∪ DF⁺_fwd( S ∪ HLC(S) )

14.4 Cuando una optimización rompe SSA

Cambiamos de problema. Algunas optimizaciones rompen la propiedad de asignación única insertando definiciones adicionales de un valor SSA ya existente. El caso más común es la división de rangos de vida al insertar copias, o el código de volcado y recarga (spill y reload) durante la asignación de registros. Otras, como el desenrollado de bucles o el jump threading, duplican código y modifican el flujo de control.

El ejemplo canónico:

  (a) original          (b) tras spilling, SSA rota    (c) SSA reconstruida

    x0 <- ...              x0 <- ...                     x0 <- ...
                           X <- spill x0                 X <- spill x0
   ..<-x0  ..<-x0        ..<-x0    :                   ..<-x0    :
                                   :                             :
                           x0 <- reload X                x1 <- reload X
    ... <- x0              ... <- x0                     x2 <- phi(x0, x1)
                                                         ... <- x2

Una fase de spilling rompe SSA. El reload es una segunda definicion de x0, y reparar SSA exige colocar una phi nueva.

Obsérvese que reparar SSA no consiste sólo en renombrar: hay que colocar funciones φ nuevas. Mantener SSA es una de las partes más complicadas y propensas a errores de este tipo de optimizaciones.

El escenario general: el programa está en SSA con propiedad de dominancia; cada instrucción escribe una sola variable; y una transformación ha insertado definiciones adicionales de una variable SSA existente. La variable original y las definiciones adicionales pueden verse como una única variable no-SSA v con múltiples definiciones y usos.

Reconstruir SSA para v consiste en dos pasos: crear variables frescas para cada definición de v, restableciendo la propiedad de asignación única, y después asociar cada uso con la definición apropiada. Escribiremos v.defs para el conjunto de instrucciones que definen v; un uso es un par (instrucción, índice del operando).

El esqueleto común a los dos algoritmos que veremos:

Entrada: v, variable que rompe la propiedad SSA

foreach d in v.defs do
    crear variable fresca v'
    reescribir la definicion de v por v' en d
    b := d.block
    insertar d en b.defs

foreach uso (inst, index) de v do
    if inst es una phi then
        b := inst.block.pred(index)
        d := FindDefFromBottom(v, b)
    else
        d := bottom
        b := inst.block
        foreach l in b.defs de abajo arriba do
            if l esta antes que inst en b then
                d := l ; break
        if d = bottom then
            d := FindDefFromTop(v, b)     // no hay def local: buscar en los preds
    v' := version de v definida por d
    reescribir el uso de v por v' en inst

FindDefFromBottom(v, b):
    if b.defs != {} then return la ultima instruccion de b.defs
    else return FindDefFromTop(v, b)

Conviene mantener b.defs ordenada según la planificación de instrucciones del bloque, de atrás hacia adelante, de modo que la definición más tardía sea la primera de la lista. Y nótese el tratamiento diferenciado de los usos en φ: ocurren al final del bloque predecesor correspondiente a la posición del operando, así que la búsqueda empieza desde el final de ese bloque.

Los dos algoritmos se diferencian únicamente en la implementación de FindDefFromTop.

14.5 Reconstrucción basada en la frontera de dominancia

Sigue los mismos principios que el algoritmo clásico del capítulo «13». Se calcula primero DF⁺(v.defs), que es una aproximación segura del conjunto donde deben colocarse las φ —puede contener bloques donde la φ sería muerta—. Después, para cada uso u se busca su definición alcanzable empezando en el bloque de u:

FindDefFromTop(v, b):        // version basada en fronteras de dominancia
    if b in DFplus(v.defs) then
        v' := variable fresca
        d  := nueva phi en b:  v' <- phi(...)
        anadir d a b.defs
        foreach p in b.preds do
            o  := FindDefFromBottom(v, p)
            v'' := version de v definida por o
            fijar el operando correspondiente de d a v''
    else
        d := FindDefFromBottom(v, b.idom)   // buscar en el dominador inmediato
    return d

Si el bloque está en DF⁺, hay que colocar una φ a su entrada; esa φ es una definición nueva de v y se inserta en v.defs y en b.defs. Sus operandos se resuelven con llamadas recursivas a FindDefFromBottom sobre los predecesores. Insertar la φ en b.defs antes de buscar los argumentos es lo que impide la recursión infinita, que si no se produciría con las aristas de retroceso de los bucles.

Si el bloque no está en DF⁺, la búsqueda continúa en su dominador inmediato. La razón es que en SSA todo uso está dominado por su definición —y la definición de un operando de una φ tiene que dominar el bloque predecesor correspondiente—, luego la definición alcanzable es la misma para todos los predecesores del bloque y, por tanto, la del dominador inmediato.

14.6 Reconstrucción por búsqueda

El segundo algoritmo procede de una técnica diseñada para construir SSA a partir del AST, pero funciona bien sobre CFG. Su ventaja decisiva es que no necesita información de dominancia ni fronteras de dominancia, por lo que resulta idóneo en transformaciones que modifican el propio grafo de flujo de control —desenrollado, jump threading, duplicación de caminos— donde recalcular los dominadores tras cada cambio sería prohibitivo.

Su desventaja es que potencialmente hay que visitar más bloques durante la búsqueda, y que no construye SSA mínima en general: puede insertar φ innecesarias. A cambio, no necesita actualizar ninguna estructura interna cuando el CFG cambia.

La idea es buscar hacia atrás desde los usos hasta las definiciones, colocando φ bajo demanda: al llegar a un bloque con varios predecesores cuya definición alcanzable no se conoce, se inserta una φ provisional, se marca el bloque como visitado para cortar los ciclos, y se resuelven recursivamente sus operandos. Si al terminar todos los operandos resultan ser la misma versión, la φ es trivial y se elimina, propagando el resultado a sus usuarios; es lo que se conoce como inserción pesimista de φ, en contraste con la inserción optimista basada en DF⁺.

Los dos, comparados:

	Basado en `DF⁺`	Basado en búsqueda
Requiere dominadores	sí	no
Requiere `DF⁺`	sí	no
Produce SSA mínima	sí	no siempre
Coste si cambia el CFG	recalcular dominadores	ninguno
Bloques visitados	los de `DF⁺`	potencialmente más

Regla práctica: si la transformación no cambia el CFG —spilling, división de rangos de vida, propagación de copias— conviene el basado en DF⁺, que aprovecha los dominadores ya calculados. Si la transformación sí cambia el CFG, conviene el basado en búsqueda.

14.7 Reconstrucción incremental en el análisis de binarios

En ingeniería inversa

Por qué esto es el corazón de un decompilador interactivo

En un compilador, la construcción de SSA ocurre una vez y las reparaciones son ocasionales. En un decompilador interactivo la situación se invierte: el análisis se reconstruye continuamente porque el analista no para de cambiar cosas.

Cada una de estas acciones rompe la forma SSA y obliga a repararla:

Corregir el prototipo de una función. Cambian los parámetros y el valor de retorno, luego cambian las definiciones y usos en todos sus puntos de llamada.
Marcar una función como noreturn. Desaparecen aristas del CFG, y con ellas operandos de φ.
Resolver a mano un salto indirecto. Aparecen aristas y predecesores nuevos, luego hacen falta φ nuevas exactamente en DF⁺ de los bloques afectados.
Definir una estructura y aplicarla a una variable. Se subdivide una posición de memoria en campos, cada uno con sus propias definiciones.
Forzar un tipo o un rango de valores. No rompe SSA, pero invalida los resultados de los análisis construidos sobre ella.

Reconstruir todo desde cero en cada acción sería inaceptable en una función de miles de bloques. De ahí que las herramientas usen exactamente los algoritmos de las secciones «14.5» y «14.6»: reparación local, limitada a la región afectada.

Y hay una razón adicional, específica del análisis de binarios: el propio análisis descubre definiciones nuevas mientras avanza. Cuando el análisis de punteros del capítulo «18» concluye que un mov [rax], rbx puede escribir en la ranura de pila [rbp-0x18], acaba de crear una definición adicional de la variable que ocupa esa ranura, exactamente igual que el reload del ejemplo de la «sección 14.4 · Cuando una optimización rompe SSA». El bucle completo —analizar, descubrir definiciones, reparar SSA, volver a analizar— es la forma general del análisis de binarios, y la reconstrucción incremental es lo que lo hace viable.