Análisis de flujo de control y basado en restricciones

Avanzado · Actualizado el 16 de agosto de 2026

El capítulo «10» supuso conocido el grafo de llamadas. Cuando hay funciones como valores, punteros a función o métodos virtuales, el grafo de llamadas es en sí mismo el resultado de un análisis, y es el mismo problema que plantea un call rax en un binario. Este capítulo lo resuelve, y de paso presenta el segundo de los cuatro enfoques del capítulo «1»: el análisis basado en restricciones.

17.1 El problema

Si se introducen funciones como valores —y con ellas funciones de orden superior—, en cada punto de llamada deja de ser trivial saber qué función se llama. Un problema análogo aparece en lenguajes orientados a objetos con métodos invocados por despacho dinámico.

La tarea del análisis de flujo de control (control flow analysis) es aproximar conservadoramente el flujo de control interprocedural, es decir, el grafo de llamadas (call graph). Un grafo de llamadas indica, para cada punto de llamada, qué funciones pueden llamarse, expresado como aristas desde el nodo del AST o del CFG que representa el punto de llamada hasta las funciones posibles. Se busca normalmente una sobreaproximación: puede haber aristas de más, nunca de menos. Con ese grafo se puede después hacer análisis de flujo de datos interprocedural.

17.2 Análisis de clausuras para el λ-cálculo

El análisis de flujo de control en su forma más pura se ilustra mejor con el λ-cálculo clásico, cuya sintaxis abstracta es:

Exp -> lambda Id . Exp
     | Id
     | Exp Exp

Suponemos, por simplicidad, que todas las variables ligadas por λ son distintas. Para construir un CFG de un término hay que aproximar, para cada expresión E, el conjunto de clausuras (closures) a las que puede evaluar. Una clausura se modela con un símbolo λX que identifica una λ-abstracción concreta. Este problema se llama análisis de clausuras (closure analysis).

Como el flujo de control intraprocedural es trivial en este lenguaje, el análisis puede hacerse directamente sobre el AST. Para cada nodo v se introduce una variable de restricción ⟦v⟧ que denota el conjunto de clausuras resultantes.

Para una abstracción λX.E:

λX ∈ ⟦λX.E⟧

—la función evalúa ciertamente a sí misma—. Y para una aplicación E₁ E₂, para cada abstracción λX.E del programa, la restricción condicional:

λX ∈ ⟦E₁⟧ ⟹ ( ⟦E₂⟧ ⊆ ⟦X⟧ ∧ ⟦E⟧ ⊆ ⟦E₁ E₂⟧ )

que modela que el argumento real E₂ puede fluir al argumento formal X, y que el valor del cuerpo E está entre los resultados posibles de la llamada.

Como ejemplo, el programa (λs.λz.sz)(λn.λt.λe.e)(λr.λp.r), que contiene 7 abstracciones y 3 aplicaciones, genera 7 restricciones del primer tipo y 21 del segundo. Su menor solución es:

[[s]] = {ln}                 [[ls.lz.sz]] = {ls}
[[z]] = {lr}                 [[lz.sz]]    = {lz}
[[n]] = {lr}                 [[sz]]       = {lt}
[[t]] = {}                   [[ln.lt.le.e]] = {ln}
[[e]] = {}                   [[lt.le.e]]  = {lt}
[[r]] = {}                   [[le.e]]     = {le}
[[p]] = {}                   [[lr.lp.r]]  = {lr}
                             [[lp.r]]     = {lp}
[[(ls.lz.sz)(ln.lt.le.e)]]              = {lz}
[[(ls.lz.sz)(ln.lt.le.e)(lr.lp.r)]]     = {lt}

(donde l abrevia λ). De ella se lee que la s de la aplicación sz sólo puede ser la abstracción λn.λt.λe.e, y que en la aplicación más externa la abstracción aplicada sólo puede ser λz.sz.

Obsérvese la forma de las restricciones: pertenencia de un token a un conjunto, e inclusión condicionada por una pertenencia. Esa forma tiene un algoritmo dedicado.

17.3 El algoritmo cúbico

Las restricciones del análisis de clausuras son una instancia de una clase general que se resuelve en tiempo cúbico. Como muchos problemas caen en esa categoría, merece la pena estudiar el algoritmo de cerca.

Tenemos un conjunto finito de tokens T = {t₁, …, t_k} y un conjunto finito de variables V = {x₁, …, xₙ} cuyos valores son conjuntos de tokens. La tarea es leer una colección de restricciones de las formas

t ∈ x y t ∈ x ⟹ y ⊆ z

y producir la menor solución, que existe y es única porque las soluciones son cerradas bajo intersección.

El algoritmo mantiene un grafo dirigido cuyos nodos son las variables de restricción y cuyas aristas reflejan restricciones de inclusión. Para cada variable x:

x.sol ⊆ T es la solución de x,
x.succ ⊆ V es el conjunto de sucesores de x, es decir, las aristas del grafo,
x.cond(t) ⊆ V × V es el conjunto de restricciones condicionales de x y t.

Y además una lista de trabajo W ⊆ T × V. Todos los conjuntos empiezan vacíos.

procedure addToken(t, x)
    if t not in x.sol then
        x.sol.add(t)
        W.add(t, x)

procedure addEdge(x, y)
    if x != y and y not in x.succ then
        x.succ.add(y)
        for t in x.sol do
            addToken(t, y)

procedure propagate()
    while W is not empty do
        (t, x) := W.removeNext()
        for (y, z) in x.cond(t) do
            addEdge(y, z)
        for y in x.succ do
            addToken(t, y)

Y las restricciones se procesan así:

para  t in x :
    addToken(t, x)
    propagate()

para  t in x  =>  y subset z :
    if t in x.sol then
        addEdge(y, z)
        propagate()
    else
        x.cond(t).add(y, z)

Formalización

Coste: el cuello de botella cúbico

Supongamos que el número de tokens y el de variables son ambos O(n), lo cual es el caso en el análisis de clausuras de un programa de tamaño n. El número de restricciones generadas es O(n) del primer tipo y O(n²) del segundo.

Cada pareja (token, variable) se añade a lo sumo una vez a la lista de trabajo, así que el número de iteraciones de propagate es O(n²); por lo mismo, W se implementa con un array y operaciones de tiempo constante. La función addEdge se llama O(n²) veces en total, porque hay O(n²) restricciones condicionales y cada una se procesa de inmediato o a lo sumo una vez en propagate. addToken cuesta O(1) si cada x.sol es un vector de bits.

addEdge llama a addToken O(n³) veces en total, porque hay O(n²) aristas y O(n) tokens; con x.succ en arrays o tablas hash, cada operación cuesta O(n), de modo que todas las llamadas a addEdge cuestan O(n³). Cada iteración de propagate cuesta O(n) sin contar addEdge. Sumando:

O(n³)

Y esto parece ser también una cota inferior, fenómeno que se conoce como el cuello de botella cúbico (cubic time bottleneck). Con una representación por vectores de bits sobre una máquina de palabra Θ(log n) puede mejorarse ligeramente a O(n³ / log n).

Son posibles numerosas mejoras algorítmicas, casi todas estudiadas en conexión con el análisis de punteros del capítulo «18»:

eliminación de ciclos (colapsar nodos cuando hay un ciclo de restricciones de inclusión),
mantener la lista de trabajo en orden topológico,
entrelazar la propagación de la solución con el procesamiento de restricciones,
representación compartida de vectores de bits para ahorrar memoria,
filtrado por tipos,
procesamiento bajo demanda,
propagación por diferencias,
compactación de nodos subsumidos.

17.4 TIP con funciones de primera clase

Trasladado a TIP: en una llamada calculada E(E₁,…,Eₙ) no se ve por la sintaxis qué funciones pueden llamarse. Un CFG burdo pero correcto se obtendría suponiendo que puede llamarse cualquier función con el número adecuado de argumentos. Con análisis de flujo de control se hace mucho mejor.

El retículo es el retículo de partes del conjunto de tokens que contiene un token X por cada nombre de función, ordenado por inclusión. Las restricciones:

para una función llamada f: f ∈ ⟦f⟧
para una asignación X = E: ⟦E⟧ ⊆ ⟦X⟧
para una llamada calculada E(E₁,…,Eₙ), y para cada definición de función f con argumentos a¹_f, …, aⁿ_f y expresión de retorno E'_f:

f ∈ ⟦E⟧ ⟹ ( ⟦E₁⟧ ⊆ ⟦a¹_f⟧ ∧ … ∧ ⟦Eₙ⟧ ⊆ ⟦aⁿ_f⟧ ∧ ⟦E'_f⟧ ⊆ ⟦E(E₁,…,Eₙ)⟧ )

Se obtiene un análisis aún más preciso si se restringe a programas tipables y sólo se generan restricciones para las funciones f cuya llamada sería correcta en tipos. Es el filtrado por tipos mencionado antes, y en binarios equivale a filtrar por número y tamaño de argumentos.

Para llamadas directas, donde la función se da por nombre, se puede usar la regla incondicional correspondiente, que es más barata.

Un ejemplo completo:

inc(i) { return i+1; }
dec(j) { return j-1; }
ide(k) { return k; }
foo(n,f) {
    var r;
    if (n==0) { f = ide; }
    r = f(n);
    return r;
}
main() {
    var x,y;
    x = input;
    if (x>0) { y = foo(x,inc); } else { y = foo(x,dec); }
    return y;
}

Las restricciones no triviales son:

inc in [[inc]]        dec in [[dec]]        ide in [[ide]]
[[ide]] subset [[f]]
[[f(n)]] subset [[r]]
inc in [[f]]  =>  [[n]] subset [[i]]  and  [[i+1]] subset [[f(n)]]
dec in [[f]]  =>  [[n]] subset [[j]]  and  [[j-1]] subset [[f(n)]]
ide in [[f]]  =>  [[n]] subset [[k]]  and  [[k]]   subset [[f(n)]]
[[x]] subset [[n]]  and  [[inc]] subset [[f]]  and  [[r]] subset [[foo(x,inc)]]
[[x]] subset [[n]]  and  [[dec]] subset [[f]]  and  [[r]] subset [[foo(x,dec)]]

y los valores no vacíos de la menor solución son ⟦inc⟧ = {inc}, ⟦dec⟧ = {dec}, ⟦ide⟧ = {ide}, ⟦foo⟧ = {foo} y, lo interesante,

⟦f⟧ = { inc, dec, ide }

Con eso se construye el CFG interprocedural del capítulo «10», con aristas desde el punto de llamada f(n) a las tres funciones posibles:

      main                    foo                        ide    inc    dec
   +---------+          +-------------+                  |      |      |
   | x=input |          | if (n == 0) |                  v      v      v
   +----+----+          +--+-------+--+              +------+ +------+ +------+
        |               si |       | no              |ret k | |ret   | |ret   |
   +----v-----+        +---v---+   |                 |      | | i+1  | | j-1  |
   |if (x > 0)|        |f = ide|   |                 +---+--+ +---+--+ +---+--+
   +--+-----+-+        +---+---+   |                     |        |        |
      |     |              |       |                     +--------+--------+
      v     v              +---+---+                              |
  foo(x,inc) foo(x,dec)        |                                  |
      |     |             +----v--------+ ------------------------+
      +--+--+             | ... = f(n)  | <---- tres aristas de llamada
         |                +----+--------+
         v                     |
     +--------+           +----v----+
     |return y|           |return r |
     +--------+           +---------+

CFG interprocedural resultante. La llamada calculada f(n) tiene tres destinos posibles.

17.5 Flujo de control en lenguajes orientados a objetos

En un lenguaje con despacho dinámico, la llamada o.m(args) puede ir a cualquier implementación de m en cualquier subclase del tipo estático de o. Hay una jerarquía de técnicas, ordenadas por precisión y coste:

Técnica	Qué usa	Precisión
CHA — Class Hierarchy Analysis	sólo la jerarquía de clases y el tipo estático del receptor	baja, muy barata
RTA — Rapid Type Analysis	CHA restringida a las clases que el programa instancia	media, casi igual de barata
VTA — Variable Type Analysis	propagación de tipos por el grafo de asignaciones	alta
k-CFA	análisis de flujo de control con contextos, como el de este capítulo	máxima, cara

CHA es sorprendentemente eficaz en la práctica porque la mayoría de los métodos no se redefinen. RTA la mejora casi gratis: si el programa nunca hace new Derivada(), no hace falta considerar Derivada.m(). VTA y k-CFA se reservan para los puntos de llamada que las anteriores no consiguen resolver a un solo destino.

17.6 En binarios

En ingeniería inversa

Los tres problemas de flujo de control desconocido

Punteros a función. Es el caso más directamente análogo al análisis de clausuras. Cada call rax es una aplicación cuyo operando hay que resolver, y cada dirección de función que aparezca como constante en el binario es un token. El análisis basado en restricciones de la «sección 17.3 · El algoritmo cúbico» se aplica casi literalmente: los tokens son direcciones de función y las variables de restricción son registros y posiciones de memoria en forma SSA. En la práctica se combina con el análisis de valores del capítulo «8», que resuelve directamente los casos fáciles.

Métodos virtuales de C++. Aquí hay estructura que explotar y las herramientas la explotan. Una llamada virtual compilada tiene una forma reconocible: cargar el puntero a la vtable desde el desplazamiento 0 del objeto, cargar la entrada k de la vtable, y llamar. Recuperar la jerarquía de clases a partir de las vtables —que están en secciones de sólo lectura y suelen llevar RTTI si no se ha desactivado— permite aplicar CHA y RTA tal cual. Es la base de todos los plugins de reconstrucción de clases C++.

El punto delicado: el desplazamiento k dentro de la vtable es el análisis de valores otra vez. Si el análisis no acota k, la llamada puede ir a cualquier entrada de la tabla, y CHA degenera en «cualquier método de cualquier clase».

Tablas de despacho y máquinas de estados. El caso peor. Un intérprete embebido, una máquina de estados generada, o un binario con aplanamiento de flujo de control, tienen un único punto de llamada indirecta al que llegan todos los destinos. Aquí el análisis basado en restricciones converge a la respuesta trivial —todos los destinos son posibles desde todos los puntos— y hay que recurrir a sensibilidad al camino (capítulo «9») sobre la variable de estado.

Y una observación sobre el coste. El cuello de botella cúbico se refiere al tamaño del programa; sobre un binario grande, n³ es prohibitivo. Por eso las herramientas reales aplican casi siempre las mejoras de la «sección 17.3 · El algoritmo cúbico» —eliminación de ciclos y orden topológico son las que más rinden— y limitan el análisis a un componente conexo del grafo de llamadas cada vez.

17.7 El enfoque basado en restricciones, en perspectiva

Éste es el primer capítulo en el que las restricciones no se derivan recorriendo un CFG, sino directamente de la sintaxis. Merece la pena señalar por qué eso importa.

En el capítulo «6», las restricciones se generaban a partir de las aristas del CFG, lo que presupone conocer el CFG. Aquí no: las restricciones se generan a partir del AST, y el grafo de flujo es la solución, no la entrada. Ésa es la razón de que el análisis basado en restricciones sea el enfoque natural para todo lo que involucre flujo de control desconocido: llamadas indirectas, métodos virtuales, closures, y también —como se verá en el capítulo «18»— punteros.

La otra diferencia es la insensibilidad al flujo. El análisis de este capítulo no distingue puntos del programa: ⟦f⟧ es un solo conjunto para toda la función. Eso lo hace mucho más barato y es lo que permite tratar programas enteros; el precio es que si f apunta a inc en la primera mitad y a dec en la segunda, el análisis dirá que apunta a ambos siempre.

Formalización

La equivalencia con el flujo de datos

El análisis de clausuras de la «sección 17.2 · Análisis de clausuras para el λ-cálculo» puede reformularse como un marco monótono del capítulo «6», con el retículo ℘(Λ) de conjuntos de abstracciones, un CFG trivial de un solo nodo por función y funciones de transferencia derivadas de las restricciones condicionales. Recíprocamente, cualquier marco monótono puede expresarse como un sistema de restricciones de inclusión, según se vio en el capítulo «5».

Lo que cambia no es el poder expresivo sino qué es dato y qué es incógnita. En el flujo de datos el grafo es dato; en las restricciones puede ser incógnita. Ésa es la construcción que el capítulo «1» anunciaba entre el primer y el segundo enfoque, hecha explícita.

17.8 Lecturas

La «sección 17.5 · Flujo de control en lenguajes orientados a objetos» sintetiza la literatura estándar sobre análisis de flujo de control en lenguajes orientados a objetos: Dean, Grove y Chambers (1995) para CHA, Bacon y Sweeney (1996) para RTA, Sundaresan et al. (2000) para VTA y Shivers (1991) para k-CFA.