Grafos de flujo de control — dominadores, bucles e irreducibilidad

Fundamentos · Actualizado el 16 de agosto de 2026

El grafo de flujo de control es la estructura sobre la que se apoya todo lo demás. Este capítulo la construye, define la relación de dominancia —de la que dependen tanto la forma SSA como la reconstrucción de estructuras de control— y estudia los bucles, incluido el caso incómodo de los grafos irreducibles, que en binarios reales son mucho más frecuentes de lo que la literatura de compiladores sugiere.

4.1 Bloques básicos y grafo de flujo de control

Un bloque básico (basic block) es una secuencia máxima de instrucciones tal que el control entra por la primera y sale por la última, sin saltos intermedios ni destinos de salto en su interior. La partición de un programa en bloques básicos se obtiene marcando como líder (leader) toda instrucción que sea la primera del programa, destino de un salto, o inmediatamente posterior a un salto; cada bloque va de un líder al siguiente exclusive.

El grafo de flujo de control (CFG) es el grafo dirigido cuyos nodos son los bloques básicos y cuyas aristas representan las transferencias de control posibles. Se supone siempre un único nodo de entrada, entry o r (por root), y un único nodo de salida, exit. Cuando el programa tiene varios return, se añade un nodo exit artificial con aristas desde todos ellos; cuando el grafo se recorre en sentido inverso —cosa que hacen los análisis backward— ese nodo pasa a ser la raíz.

Escribiremos pred(v) y succ(v) para los conjuntos de predecesores y sucesores de v. Un nodo con |succ(v)| > 1 es un nodo de bifurcación; uno con |pred(v)| > 1 es un nodo de confluencia o join node, y son precisamente los nodos de confluencia los que hacen difícil el análisis: son los puntos donde hay que combinar información procedente de caminos distintos.

Éste es el CFG que usaremos como ejemplo en este capítulo y, sobre todo, en el capítulo «13», donde se le construye la forma SSA:

              +-------+
              |   r   |  entry
              +---+---+
                  |
                  v
       +----->+-------+
       |      |   A   |
       |      +---+---+
       |       /       \
       |      v         v
       |  +-------+  +----------+
       |  |   B   |  |    C     |
       |  | y <- 0|  | tmp <- x |
       |  | x <- 0|  | x <- y   |
       |  +---+---+  | y <- tmp |
       |      |      +----+-----+
       |      |           |    \
       |      v           v     \
       |  +---------------+      |
       |  |       D       |      |
       |  | x <- f(x, y)  |      |
       |  +-------+-------+      |
       |          |   \          |
       +----------+    \         |
                        v        v
                     +---------------+
                     |       E       |
                     |     ret x     |
                     +---------------+

CFG de ejemplo. Las variables son x, y, tmp; todas indefinidas a la entrada. La arista D → A es la única arista de retroceso.

Es decir: A → B, A → C, B → D, C → D, C → E, D → E y la arista de retroceso D → A.

4.2 Del binario al CFG

En un compilador, construir el CFG es trivial: la estructura sintáctica lo dicta. En un binario es un problema abierto, por el círculo vicioso ya señalado en el capítulo «1». El procedimiento real es un punto fijo:

build_cfg(entries):
    worklist := entries
    cfg      := empty
    while worklist not empty do
        a := pop(worklist)
        decode basic block starting at a, add to cfg
        for each successor s of the block:
            if s is a known address and s not in cfg then push s
        if the block ends in an indirect branch then
            T := value_analysis(cfg, branch operand)   // capitulo 8
            if T is bounded then
                for each t in T: if t not in cfg then push t
            else
                mark block as unresolved
    return cfg

Cada vuelta del bucle amplía el grafo, lo que mejora el análisis de valores, lo que puede resolver más saltos indirectos, lo que vuelve a ampliar el grafo. Se termina cuando ninguna iteración añade nada.

Los bloques marcados como unresolved son la deuda técnica del análisis. Un CFG con saltos indirectos sin resolver es incompleto, y todo análisis posterior debe tratarlo de forma conservadora: suponer que el salto puede ir a cualquier parte, lo cual destruye casi toda la precisión, o suponer que va a los destinos conocidos, lo cual es incorrecto. Las herramientas reales eligen lo segundo y no siempre lo advierten.

En ingeniería inversa

Tres fuentes habituales de saltos indirectos

Tablas de salto de switch. Son el caso amable: el compilador genera un patrón reconocible —comparación con la cota, salto condicional al default, carga indexada de la tabla, salto— y las herramientas lo reconocen por patrón por cada compilador y arquitectura. Cuando el patrón no está en la base de datos de patrones, el switch no se resuelve.

Punteros a función y métodos virtuales. Requieren análisis de flujo de control (capítulo «17») y de punteros (capítulo «18»). Para C++, las técnicas específicas de devirtualización se apoyan en la estructura de las vtables.

Trampolines, hooking y ofuscación. Aquí no hay solución general. La ofuscación por aplanamiento de flujo de control (control-flow flattening) convierte deliberadamente todos los saltos en un despachador indirecto gobernado por una variable de estado, precisamente para que la construcción del CFG falle. Deshacerlo requiere ejecución simbólica o análisis de valores muy preciso sobre la variable de estado.

4.3 Dominancia

Sea G un CFG con raíz r.

El nodo d domina al nodo n, escrito d dom n, si todo camino desde r hasta n pasa por d.
d domina estrictamente a n si d dom n y d ≠ n.
El dominador inmediato de n, idom(n), es el dominador estricto de n más próximo a n; es decir, el único d que domina estrictamente a n y que no domina estrictamente a ningún otro dominador estricto de n.

La relación de dominancia es reflexiva, transitiva y antisimétrica, y idom induce un árbol —el árbol de dominadores (dominator tree)— con raíz en r, en el que el padre de n es idom(n). Para el CFG de la «sección 4.1 · Bloques básicos y grafo de flujo de control»:

        r
        |
        A
      / | \
     B  C  \
            \
     D-------E

     idom(A)=r  idom(B)=A  idom(C)=A  idom(D)=A  idom(E)=A

Arbol de dominadores del CFG de ejemplo. Notese que D no domina a E, porque a E se llega tambien por C.

En efecto: A domina a todos salvo a r, pero ni B, ni C, ni D dominan a E, porque a E se puede llegar por r → A → C → E, que evita B y D, y por r → A → B → D → E, que evita C. El dominador inmediato de los cuatro es A.

Formalización

Cálculo de dominadores

La formulación como problema de flujo de datos es directa. Sea DOM(n) el conjunto de dominadores de n:

DOM(r) = {r}

DOM(n) = {n} ∪ ( ⋂_{p ∈ pred(n)} DOM(p) ) para n ≠ r

Es un análisis forward, must (usa intersección), sobre el retículo ℘(N) ordenado por ⊇. Se resuelve por iteración hasta punto fijo, y la existencia y unicidad de la menor solución están garantizadas por el teorema de Kleene (capítulo «5»).

La implementación ingenua es O(N²) en espacio, prohibitiva para funciones grandes. En la práctica se usa una de dos:

Cooper, Harvey y Kennedy (2001): iteración sobre el árbol de dominadores representado sólo por el vector idom, recorriendo los nodos en orden inverso de postorden. La operación de intersección se implementa como el ancestro común más próximo mediante dos punteros que suben en paralelo. Es O(N²) en el peor caso pero en la práctica se comporta casi lineal, y es la que usan LLVM y GCC por su simplicidad y sus constantes bajas.
Lengauer y Tarjan (1979): basado en árboles de recubrimiento en profundidad y en la noción de semidominador. Es O(E α(E, N)) con la versión sofisticada de la estructura de conjuntos disjuntos, y O(E log N) con la simple. Asintóticamente mejor, notablemente más difícil de implementar correctamente.

Para un binario típico, donde las funciones rara vez pasan de unos miles de bloques, la diferencia práctica es despreciable y se prefiere la primera.

4.4 Postdominancia y dependencia de control

Aplicando la definición de dominancia al grafo con las aristas invertidas y raíz en exit se obtiene la postdominancia: p postdom n si todo camino desde n hasta exit pasa por p.

Con las dos relaciones se define la dependencia de control (control dependence), que responde a la pregunta «¿de qué decisión depende que esta instrucción se ejecute?». Un nodo n es control-dependiente de b si:

existe un camino de b a n en el que todo nodo intermedio es postdominado por n, y
b no es postdominado por n.

Intuitivamente: b es una bifurcación en la que una rama lleva necesariamente a n y la otra no. El grafo de dependencias de control (control dependence graph, CDG) recoge esta relación y, combinado con el grafo de dependencias de datos, forma el grafo de dependencias del programa (program dependence graph, PDG), que reaparece en el capítulo «16».

4.5 Conjuntos de confluencia y fronteras de dominancia

Estos dos conceptos son la clave del algoritmo de construcción de SSA, y conviene entenderlos aquí, con independencia de SSA.

Dado un conjunto de nodos S de un CFG, el conjunto de confluencia (join set) J(S) es el conjunto de nodos del CFG a los que se puede llegar desde dos o más elementos distintos de S mediante caminos disjuntos.

En el CFG de la «sección 4.1 · Bloques básicos y grafo de flujo de control»:

J({B, C}) = {D}, porque se puede ir de B a D y de C a D por caminos distintos y sin solaparse.
J({r, A, B, C, D, E}) = {A, D, E}, porque A, D y E son los únicos nodos con más de un predecesor.

La frontera de dominancia (dominance frontier) de un nodo n, escrita DF(n), es el borde de la región del CFG dominada por n. Formalmente, DF(n) contiene todos los nodos x tales que n domina a un predecesor de x pero n no domina estrictamente a x.

En el ejemplo: la frontera de dominancia del bloque B es {D}. La de C es {D, E}. La de D es {A, E} —A por la arista de retroceso D → A, y E porque D no domina estrictamente a E.

DF se define sobre nodos individuales, pero se extiende a conjuntos por unión: DF(S) = ⋃_{s ∈ S} DF(s). La frontera de dominancia iterada DF⁺(S) se obtiene iterando el cálculo hasta alcanzar un punto fijo:

DF¹(S) = DF(S)

DFⁱ⁺¹(S) = DF(S ∪ DFⁱ(S))

Y DF⁺(S) es el límite de esa sucesión.

La relación con los conjuntos de confluencia es exacta y merece recordarse:

DF⁺(S) = J(S ∪ {r})

Es decir, la frontera de dominancia iterada es el conjunto de confluencia suponiendo una definición implícita en el nodo raíz. Es una sobreaproximación de J(S), y es la razón de que el algoritmo clásico de construcción de SSA inserte a veces funciones φ que no hacían falta.

Para el CFG del ejemplo, si las definiciones de x están en {B, C, D}, entonces DF⁺({B, C, D}) = {A, D, E}, y no hace falta iterar: la primera aplicación de DF ya da el resultado.

4.6 Bucles

Una arista de retroceso (back edge) es una arista u → v tal que v dom u. El bucle natural (natural loop) asociado a la arista de retroceso u → v es el conjunto formado por v —la cabecera (header) del bucle— más todos los nodos que pueden alcanzar u sin pasar por v.

En el ejemplo, D → A es arista de retroceso porque A dom D, y el bucle natural es {A, B, C, D}.

Dos bucles naturales distintos o son disjuntos, o uno está contenido en el otro, o comparten cabecera —en cuyo caso se suelen fusionar. Eso permite organizarlos en un bosque de anidamiento de bucles (loop nesting forest): un bosque cuyos nodos son los bucles, con un bucle como hijo de otro si está anidado dentro.

Notación útil, que se usará en los capítulos «14» y «23»: para un nodo v, HLC(v) (headers of loops containing v) es el conjunto de cabeceras de los bucles que contienen a v.

Formalización

La contribución de los bucles a DF⁺

Un grafo reducible se descompone en un grafo acíclico más un conjunto de aristas de retroceso. Eso permite calcular DF⁺ en dos partes.

Sobre el CFG forward G_fwd —el grafo sin aristas de retroceso, que es acíclico— basta un recorrido en orden topológico: un nodo pertenece a DF⁺ si le llegan dos definiciones distintas. La contribución de las aristas de retroceso se recupera del bosque de bucles: si un bucle contiene una definición, su cabecera pertenece a DF⁺. Combinando ambas:

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

El algoritmo sobre el grafo acíclico es este:

DFplus_acyclic(G_fwd, S):
    DFplus := {}
    for each node n do UniqueReachingDef(n) := {r}
    for each node u != r in topological order do
        ReachingDefs := {}
        for each v in pred(u) do
            if v in DFplus union S union {r} then
                ReachingDefs := ReachingDefs union {v}
            else
                ReachingDefs := ReachingDefs union UniqueReachingDef(v)
        if |ReachingDefs| = 1 then
            UniqueReachingDef(u) := ReachingDefs
        else
            DFplus := DFplus union {u}
    return DFplus

Este esquema, debido a Das, Ramakrishna y Sreedhar, evita construir explícitamente las fronteras de dominancia de todos los nodos, cuyo tamaño total puede ser cuadrático. El capítulo «14» lo desarrolla junto con la alternativa basada en DJ-graphs.

4.7 Reducibilidad

Un CFG es reducible (reducible) si toda arista de retroceso u → v cumple v dom u; equivalentemente, si al eliminar las aristas de retroceso el grafo resultante es acíclico. Otra caracterización clásica, debida a Hecht y Ullman, es que el grafo se colapsa a un único nodo aplicando repetidamente dos transformaciones: T1, eliminar un bucle propio, y T2, fusionar un nodo con su único predecesor.

Intuitivamente, un grafo reducible es aquél en el que todo bucle tiene un único punto de entrada. Los programas escritos con las construcciones estructuradas habituales —while, for, do, if, switch, break, continue— producen siempre grafos reducibles. Por eso la literatura de compiladores trata la irreducibilidad como una curiosidad.

Un grafo irreducible tiene al menos un bucle con dos o más entradas:

        +-------+
        | entry |
        +---+---+
           / \
          v   v
      +-----+ +-----+
      |  u  |<->|  s  |
      +-----+ +-----+

El grafo irreducible minimo. El ciclo u <-> s tiene dos entradas: ni u domina a s ni s domina a u.

Ni u domina a s ni s domina a u, luego ninguna de las dos aristas del ciclo es de retroceso según la definición, y no hay bucle natural.

En ingeniería inversa

La irreducibilidad no es una rareza en binarios

En código compilado, la irreducibilidad aparece con frecuencia por cuatro vías:

Optimizaciones del compilador. La rotación de bucles, el loop unswitching, la duplicación de cola (tail duplication) y el if-conversion pueden crear entradas múltiples. En particular, un compilador que aplica loop inversion y luego duplica el test de guarda produce a menudo grafos que ya no son reducibles tras el inlining.
Recursión de cola convertida en salto. Una llamada recursiva de cola optimizada a jmp puede entrar en mitad del cuerpo de una función.
Ofuscación deliberada. Es una de las técnicas más baratas y eficaces contra los decompiladores: basta introducir un segundo punto de entrada a un bucle para que la estructuración falle y el pseudocódigo se llene de goto.
Ensamblador escrito a mano, rutinas de biblioteca optimizadas y código generado por thunks del enlazador.

Cuando su decompilador produce un while(1) gigante con goto dentro, la causa suele ser exactamente ésta: el grafo no era reducible y no existe ninguna combinación de construcciones estructuradas que lo exprese sin duplicar código.

Hay dos formas de tratar la irreducibilidad. La primera es evitarla: casi todos los algoritmos tienen una variante que funciona sobre grafos arbitrarios, normalmente a costa de más iteraciones. La segunda es eliminarla transformando el grafo mediante duplicación de nodos (node splitting): se replica el cuerpo del bucle una vez por cada entrada, lo que convierte cada entrada en la cabecera de un bucle natural distinto. El coste es que la duplicación puede ser exponencial en el peor caso, y por eso se usan variantes controladas que limitan el factor de expansión.

4.8 De vuelta al código fuente: estructuración

Reconstruir while y if a partir del CFG —la operación inversa de la «sección 3.5 · Árboles sintácticos y grafos de flujo de control»— se llama estructuración de control (control-flow structuring) y es la última fase de un decompilador. Hay tres generaciones de técnicas:

Análisis por intervalos y análisis estructural (Cifuentes, años noventa). Se busca en el CFG, de dentro hacia fuera, la aparición de esquemas conocidos —bucle while, bucle do-while, if-then, if-then-else, switch de n vías— y cada coincidencia se colapsa en un nodo abstracto. Si al final queda un solo nodo, el programa era completamente estructurable; lo que no encaja en ningún esquema se emite como goto. Es lo que hacen los decompiladores clásicos, y es la razón de que Hex-Rays produzca goto en algunas funciones.
Estructuración basada en condiciones semánticas (pattern-independent structuring, Yakdan et al., 2015). En vez de buscar esquemas topológicos, se calcula para cada nodo la condición de alcanzabilidad —una fórmula booleana sobre las condiciones de rama que describe cuándo se ejecuta ese nodo— y se genera el código a partir de esas fórmulas, simplificándolas con un solucionador. El resultado es código sin goto en la gran mayoría de funciones, a cambio de condiciones a veces más complejas.
Enfoques híbridos actuales, que combinan lo anterior con duplicación controlada de nodos para tratar los casos irreducibles y con heurísticas de legibilidad.

Este es el punto en el que la teoría de este capítulo se convierte en el pseudocódigo que uno lee en pantalla, y el capítulo «24» lo retoma dentro del pipeline completo.

4.9 Lecturas

Las referencias sobre estructuración son Cifuentes (1994) para el análisis estructural y Yakdan et al. (2015) para la estructuración independiente de patrones; sobre reducibilidad, Hecht y Ullman (1972); sobre cálculo de dominadores, Lengauer y Tarjan (1979) y Cooper, Harvey y Kennedy (2001).