Análisis interprocedural — call strings y enfoque funcional

Operativo · Actualizado el 16 de agosto de 2026

Hasta aquí sólo hemos analizado cuerpos de funciones aisladas, lo que se llama análisis intraprocedural. Un binario real tiene miles de funciones que se llaman entre sí, y casi ninguna pregunta interesante se responde mirando una sola. Este capítulo cruza la frontera.

10.1 El grafo de flujo de control interprocedural

Partimos del subconjunto de TIP con funciones, pero todavía sin punteros ni funciones como valores; eso llega en el capítulo «17». Con esa restricción, el CFG de un programa completo es sencillo de obtener.

Se construyen primero los CFG de todos los cuerpos de función, como de costumbre. Lo único que queda es pegarlos para reflejar correctamente las llamadas, y para eso hay que ocuparse del paso de parámetros, del valor de retorno y de los valores de las variables locales del llamador a través de la llamada. Por simplicidad suponemos que toda llamada aparece asociada a una asignación, X = f(E₁, …, Eₙ);, lo que siempre puede conseguirse normalizando.

Cada sentencia de llamada se representa con dos nodos: un nodo de llamada (call node), que representa la conexión del llamador con la entrada de f, y un nodo posterior a la llamada (after-call node), donde la ejecución se reanuda tras volver de la salida de f. Y cada return E; se representa como una asignación a una variable especial llamada result.

        llamador                               llamado

    +----------------+
    | = f(E1,...,En) |------------------> +----------------+
    +----------------+                    | f(b1,...,bn)   |
            :                             +-------+--------+
            : arista especial                     |
            :                                    ...
            :                             +-------+--------+
            v                             |  result = E    |
    +----------------+ <----------------- +----------------+
    |  X =           |
    +----------------+

Union de llamador y llamado. La arista discontinua conecta el nodo de llamada con el posterior a la llamada y transporta las variables locales del llamador.

La conexión entre el nodo de llamada y su nodo posterior es una arista especial, que no forma parte de succ ni de pred. Su papel es propagar los valores abstractos de las variables locales del llamador, que la llamada no puede modificar. Sin ella habría que recorrer el cuerpo del llamado arrastrando todo el estado del llamador, que es justamente lo que se quiere evitar.

Con este CFG interprocedural en su sitio, se aplica el marco monótono del capítulo «6» sin más cambios que las reglas de las cuatro clases de nodos nuevos.

10.2 Análisis interprocedural insensible al contexto

Tomemos el análisis de signos, con Sign y State = Var → Sign. En cualquier punto del programa, el estado abstracto sólo da información sobre las variables en ámbito; todas las demás se ponen a ⊥.

Los nodos de llamada se tratan como no-ops que se limitan a recoger información de sus predecesores: si v es un nodo de llamada, ⟦v⟧ = JOIN(v).

Para un nodo de entrada v de una función f(b₁,…,bₙ) se consideran los estados abstractos de todos los llamadores y se modela el paso de parámetros:

⟦v⟧ = ⊔_{w ∈ pred(v)} s_w donde s_w = ⊥[ b₁ ↦ eval(⟦w⟧, E₁^w), …, bₙ ↦ eval(⟦w⟧, Eₙ^w) ]

siendo Eᵢ^w el i-ésimo argumento en el nodo de llamada w. Como se vio en el capítulo «5», las restricciones pueden expresarse con inecuaciones en vez de ecuaciones, y aquí la forma con inecuaciones es más natural:

s_w ⊑ ⟦v⟧

Léase: la información fluye del nodo de llamada —parte izquierda— al nodo de entrada de la función —parte derecha—. Esta formulación encaja bien con los algoritmos de propagación por lista de trabajo del capítulo «7».

Para el nodo de entrada de main, con parámetros b₁,…,bₙ, hay una regla especial que modela el hecho de que se invoca implícitamente con argumentos desconocidos:

⟦v⟧ = ⊥[ b₁ ↦ ⊤, …, bₙ ↦ ⊤ ]

Los nodos de salida de función se modelan también como no-ops: ⟦v⟧ = JOIN(v). Y para un nodo posterior a la llamada v que guarda el valor de retorno en la variable X, siendo v' su nodo de llamada asociado y w ∈ pred(v) el nodo de salida de la función:

⟦v⟧ = ⟦v'⟧[ X ↦ ⟦w⟧(result) ]

La restricción toma los valores abstractos de las variables locales del nodo de llamada v' —por la arista especial— y el valor abstracto de result del nodo de salida w. Ahí es donde la arista especial hace su trabajo.

Conviene notar qué se está dando por supuesto: que el lenguaje no tiene variables globales, ni montón, ni funciones anidadas, ni funciones de orden superior. Cada una de esas características rompe alguna de las cuatro reglas anteriores, y las tres últimas se abordan en los capítulos «17» y «18».

Un detalle de implementación que importa: los nodos de entrada pueden tener muchísimos predecesores, y los de salida muchísimos sucesores. Por eso, para análisis interprocedural, se prefieren los algoritmos de lista de trabajo con propagación —los que empujan información hacia adelante cuando una variable cambia— frente a los que reevalúan la ecuación completa de un nodo.

10.3 El problema: caminos interprocedurales inválidos

El enfoque anterior se llama insensible al contexto (context insensitive), porque no distingue entre distintas llamadas a la misma función. Considérese el análisis de signos aplicado a:

f(z) {
    return z*42;
}
main() {
    var x,y;
    x = f(0);   // llamada 1
    y = f(87);  // llamada 2
    return x + y;
}

Por la primera llamada, z puede ser 0; por la segunda, puede ser positiva. Así que en el estado abstracto a la entrada de f, el valor de z es ⊤. Ese ⊤ se propaga por el cuerpo de f y vuelve a los dos llamadores, de modo que tanto x como y acaban siendo ⊤.

Esto es flujo de datos a lo largo de caminos interprocedurales inválidos: según las restricciones, el flujo que entra desde un nodo de llamada se propaga por el cuerpo de la función y retorna no sólo al nodo posterior que le corresponde, sino a todos. El análisis sigue siendo correcto, pero la pérdida de precisión puede ser inaceptable.

      main                          f
   +----------+  llamada 1   +--------------+
   | x = f(0) |------------->|              |
   +----------+              |   z * 42     |
   +----------+  llamada 2   |              |
   | y = f(87)|------------->|              |
   +----------+              +------+-------+
        ^                           |
        |                           |
        +---------------------------+
          retorno: vuelve a AMBOS puntos

Caminos interprocedurales invalidos. El flujo entra por la llamada 1 y sale por el retorno 2.

Una solución ingenua es la clonación de funciones: duplicar f para que las dos llamadas invoquen funciones distintas pero idénticas. El efecto sería el mismo que integrar el cuerpo (inlining) en cada punto de llamada. En general, sin embargo, esto puede aumentar mucho el tamaño del programa, y con funciones recursivas —o mutuamente recursivas— daría programas infinitos.

En lugar de eso, se codifica la información que distingue las llamadas usando retículos más expresivos, exactamente igual que con la sensibilidad al camino del capítulo «9».

10.4 El retículo de la sensibilidad al contexto

Un análisis insensible al contexto se expresa mediante el retículo Stateⁿ, o equivalentemente Node → State. Un análisis sensible al contexto (context-sensitive) usa en su lugar un retículo de la forma

(Context → lift(State))ⁿ

—o cualquiera de sus formas equivalentes: Node → Context → lift(State), Context × Node → lift(State)— donde Context es un conjunto de contextos de llamada (call contexts).

La razón de usar lift(State) y no State a secas es que Context puede ser grande, y sólo queremos inferir estados abstractos para los contextos que sean factibles. El elemento mínimo de lift(State), que llamaremos unreachable, marca los contextos inalcanzables desde la entrada del programa. Cuando State ya aporta esa información por sí mismo, la elevación es innecesaria.

El flujo de datos para los nodos que no involucran llamadas ni retornos se modela como siempre, salvo que ahora hay un estado abstracto —o el valor unreachable— por cada contexto. La regla de la asignación del capítulo «6» se convierte en:

X = E:   [[v]](c) = s[X -> eval(s, E)]    si s = JOIN(v,c) pertenece a State
                  = unreachable           si JOIN(v,c) = unreachable

         JOIN(v,c) = join over w in pred(v) of [[w]](c)

La información de contextos distintos se mantiene separada y la información de alcanzabilidad se propaga junto con ella. Lo que cambia según la estrategia de sensibilidad al contexto son sólo las reglas de los cuatro tipos de nodos de llamada.

Las dos estrategias clásicas, ambas de Sharir y Pnueli (1981), están en los dos extremos: tomar Context como un conjunto unitario da el análisis insensible al contexto; tomar Context = State da la sensibilidad total.

10.5 Call strings

Sea Call el conjunto de nodos de llamada del CFG. El enfoque de las cadenas de llamada (call strings) define

Context = Call^≤k

para un entero positivo k. Se obtiene un efecto parecido al de la clonación o el inlining, pero sin modificar el CFG. La tupla (c₁, c₂, …, c_m) ∈ Call^≤k identifica los m marcos superiores de la pila de llamadas. La tupla vacía, ε, identifica la pila vacía, es decir, la ejecución iniciada en main. Las tuplas con m < k identifican pilas de altura exactamente m —en cuyo caso c_m debe ser un nodo de llamada de main—, y las de longitud k identifican pilas de altura al menos k: intuitivamente, las cadenas más largas que k se truncan.

Volvamos al programa de la «sección 10.3 · El problema: caminos interprocedurales inválidos», con c₁ y c₂ los dos nodos de llamada. Con k = 1, es decir Context = {ε, c₁, c₂}, el análisis sólo recuerda el punto de llamada más reciente. En la entrada de f se obtiene:

[ epsilon -> unreachable,
  c1      -> [x -> bottom, y -> bottom, z -> 0],
  c2      -> [x -> bottom, y -> bottom, z -> +] ]

con valores distintos para z según el llamador. La información del contexto ε es unreachable, porque f no es main y siempre se ejecuta desde c₁ o c₂.

El paso de parámetros se modela igual que en el caso insensible, pero teniendo en cuenta los contextos. Si w es un nodo de llamada y v el nodo de entrada de f(b₁,…,bₙ):

s_w^c' = unreachable                                     si [[w]](c') = unreachable
       = bottom[b1 -> eval([[w]](c'), E1^w), ...,
                bn -> eval([[w]](c'), En^w)]             en otro caso

y la restricción para el nodo de entrada, con w ∈ pred(v) un llamador y c' ∈ Context un contexto del llamador:

s_w^c' ⊑ ⟦v⟧(c) donde c = w

Informalmente: para cualquier contexto c' en el nodo de llamada w, se construye el estado s_w^c' evaluando los argumentos y se propaga al contexto c del nodo de entrada. Con k = 1 el contexto nuevo es directamente el nodo de llamada; para k mayor hay que expresar cómo se apila el punto de llamada sobre la cadena que traía el llamador, truncando por la izquierda si se supera k.

Para el nodo posterior a la llamada v que guarda el retorno en X, con v' su nodo de llamada y w el nodo de salida de la función:

[[v]](c) = unreachable                            si [[v']](c) = unreachable
                                                  o [[w]](v') = unreachable
         = [[v']](c)[X -> [[w]](v')(result)]      en otro caso

Nótese la elegancia del mecanismo: con esta forma de sensibilidad al contexto, v' es a la vez un nodo de llamada y un contexto de llamada, y el valor abstracto de result se recoge del nodo de salida w en el contexto v'. Ahí es donde se cierra el camino interprocedural válido y se descartan los inválidos.

10.6 El enfoque funcional

Considérese esta variante del programa anterior:

f(z) {
    return z*42;
}
main() {
    var x,y;
    x = f(42);  // llamada 1
    y = f(87);  // llamada 2
    return x + y;
}

Las cadenas de llamada con k ≥ 1 analizarán f dos veces, lo cual es innecesario: el valor abstracto del argumento es + en ambas llamadas, así que el resultado será idéntico.

En lugar de distinguir las llamadas por información de flujo de control procedente de la pila, el enfoque funcional (functional approach) las distingue por los datos: por el estado abstracto en el punto de llamada. En su forma más general,

Context = State

aunque a menudo basta un subconjunto. El retículo del análisis pasa a ser (State → lift(State))ⁿ.

La idea es que el elemento de retículo asociado a un nodo v es una aplicación m_v : State → lift(State) tal que m_v(s) aproxima los estados posibles en v suponiendo que la función que contiene a v se entró en un estado que encaja con s. Que m_v(s) = unreachable significa que no hay ninguna ejecución del programa en la que la función se entre en un estado compatible con s y se alcance v.

Y aquí está lo importante: si v es el nodo de salida de una función f, entonces m_v es un resumen de f (function summary), que aplica estados abstractos de entrada a estados abstractos de salida. Es a la función entera lo que una función de transferencia es a una instrucción.

Para el programa de la «sección 10.3 · El problema: caminos interprocedurales inválidos», en la salida de f se obtiene:

[ bottom[z -> 0] -> bottom[z -> 0, result -> 0],
  bottom[z -> +] -> bottom[z -> +, result -> +],
  todos los demas contextos -> unreachable ]

Esto dice que la salida de f es inalcanzable salvo que z sea 0 o + a la entrada, y que el signo de result coincide con el de z. El contexto en que z es negativa se aplica a unreachable porque f nunca se llama con entradas negativas en este programa.

La regla para el nodo de entrada es la misma que en las cadenas de llamada, salvo por la condición sobre c:

s_w^c' ⊑ ⟦v⟧(c) donde c = s_w^c'

es decir, el contexto es el estado abstracto de entrada.

Las dos estrategias, comparadas:

	Cadenas de llamada	Enfoque funcional
`Context`	`Call^≤k`	`State`, o un subconjunto
Criterio	de dónde se llamó	con qué datos se llamó
Reanaliza si	cambia el punto de llamada	cambia el estado de entrada
Recursión	truncamiento por `k`	punto fijo sobre los resúmenes
Nº de contextos	`O(card(Call)^k)`	hasta `card(State)`
Reutilización	ninguna entre llamadas distintas	total entre llamadas con igual estado

Ninguna domina a la otra. Las cadenas de llamada distinguen llamadas que el enfoque funcional fusiona —cuando los estados de entrada coinciden pero el contexto de retorno importa— y el enfoque funcional distingue llamadas que las cadenas fusionan —cuando dos puntos de llamada distintos pasan datos distintos pero la cadena ya se ha truncado—.

La combinación de ambas se usa en la práctica, y el capítulo «11» presenta un tercer enfoque, IFDS, que consigue sensibilidad total al contexto en tiempo polinómico a cambio de restringir la clase de análisis expresables.

10.7 En binarios

En ingeniería inversa

Los cuatro problemas que no aparecen en el fuente

El convenio de llamada hay que inferirlo. El análisis interprocedural de la «sección 10.2 · Análisis interprocedural insensible al contexto» supone conocidos los parámetros y el valor de retorno. En un binario sin símbolos ni información de depuración, eso es un resultado de análisis: los parámetros son los registros y posiciones de pila que la función lee antes de escribir —variables vivas a la entrada, capítulo «6»— y el valor de retorno es lo que escribe y el llamador lee después. Si el análisis de variables vivas se equivoca, el prototipo se equivoca, y con él todo el análisis interprocedural.

Peor: las funciones que no siguen el convenio estándar —código ensamblado a mano, funciones internas del compilador como memcpy optimizado, rutinas de arranque— rompen esa inferencia en silencio. Es la causa más frecuente de que un decompilador muestre una llamada con el número de argumentos equivocado.

Los resúmenes de biblioteca son obligatorios. No se puede analizar la libc entera cada vez. Todas las herramientas serias llevan resúmenes precalculados de las funciones de biblioteca conocidas —qué registros modifican, qué punteros desreferencian, qué devuelven, si liberan memoria—, que es exactamente el m_v del enfoque funcional escrito a mano. La calidad de esa base de datos determina la calidad del análisis mucho más que el algoritmo.

La recursión es más frecuente de lo que parece. No sólo la recursión explícita: las tablas de despacho, las máquinas de estados y los intérpretes embebidos producen ciclos en el grafo de llamadas que obligan a calcular punto fijo sobre los resúmenes.

Las llamadas de cola desaparecen. Un jmp a otra función optimizado como tail call no crea un nodo de llamada ni un nodo posterior: el retorno del llamado retorna directamente al llamador del llamador. Un análisis que no lo detecte construirá el CFG interprocedural mal, fusionando dos funciones en una o perdiendo el retorno. El síntoma típico es una función que «cae» dentro de otra en el desensamblado.

10.8 Lecturas

Las ideas originales del análisis interprocedural, tanto la formulación con call strings como el enfoque funcional, son de Sharir y Pnueli (1981).