Algoritmos de punto fijo — worklist, orden de iteración y complejidad

El capítulo «5» demostró que el punto fijo existe y dio un algoritmo para calcularlo. Ese algoritmo es inservible en la práctica. Este capítulo lo convierte en algo que funciona sobre un binario de cien mil bloques, y termina con la pregunta incómoda de si el punto fijo es realmente la respuesta que queríamos.

7.1 Del ingenuo al round-robin

Recapitulemos. Para un CFG con nodos Node = {v₁, …, vₙ} trabajamos en el retículo Ln, donde L modela estados abstractos. Suponiendo que el nodo vᵢ genera la ecuación ⟦vᵢ⟧ = fᵢ(⟦v₁⟧, …, ⟦vₙ⟧), construimos la función combinada f : Ln → Ln y aplicamos el algoritmo de punto fijo.

El problema del algoritmo ingenuo es que en cada iteración aplica todas las funciones de restricción, y la mayor parte de ese cálculo es redundante: si f₂ sólo depende de x₁ y x₁ no ha cambiado, recalcular f₂ es tirar el tiempo.

El primer paso hacia algo mejor es el round-robin, que explota que el retículo tiene la estructura Ln y que f está compuesta de f₁, …, fₙ:

procedure RoundRobin(f1, ..., fn)
    (x1, ..., xn) := (bottom, ..., bottom)
    repeat
        changed := false
        for i := 1 to n do
            y := fi(x1, ..., xn)
            if y != xi then xi := y; changed := true
    until not changed
    return (x1, ..., xn)

La diferencia esencial con el algoritmo ingenuo es que una iteración del bucle externo no hace lo mismo: al calcular fᵢ(x₁,…,xₙ), los valores de x₁,…,xᵢ₋₁ ya han sido actualizados por las iteraciones anteriores del bucle interno, mientras que xᵢ,…,xₙ vienen todavía de la vuelta anterior. Aun así, el algoritmo termina siempre y produce el mismo resultado que el ingenuo. Cada iteración cuesta lo mismo, pero hacen falta menos.

7.2 Iteración caótica

Se puede ir más lejos. El orden i := 1 … n es irrelevante para la corrección, y tampoco hace falta aplicar todas las funciones en cada vuelta. Lo único que importa es que las funciones de restricción se apliquen hasta alcanzar el punto fijo para todas ellas. De ahí la iteración caótica (chaotic iteration), de Cousot y de Kildall:

procedure ChaoticIteration(f1, ..., fn)
    (x1, ..., xn) := (bottom, ..., bottom)
    while (x1, ..., xn) != f(x1, ..., xn) do
        choose i in {1..n} such that xi != fi(x1, ..., xn)
        xi := fi(x1, ..., xn)
    return (x1, ..., xn)

No es un algoritmo práctico: su eficiencia y su terminación dependen de cómo se elija i, y evaluar ingenuamente la condición del bucle puede costar más que el cuerpo. Pero si termina, produce el resultado correcto. Su valor es conceptual: cualquier estrategia de elección es correcta, lo que deja libertad total para optimizar el orden.

7.3 El algoritmo de lista de trabajo

En el caso general, cada variable de restricción ⟦vᵢ⟧ podría depender de todas las demás. En la práctica, una instancia concreta de fᵢ sólo lee unas pocas. Esa información se representa como una aplicación

que para cada nodo v da el subconjunto de nodos en cuyas ecuaciones aparece ⟦v⟧ de forma no trivial. Es decir, dep(v) es el conjunto de nodos cuya información puede depender de la de v. Cuando ⟦v⟧ cambia, sólo hay que recalcular las funciones de dep(v).

procedure WorkList(f1, ..., fn)
    (x1, ..., xn) := (bottom, ..., bottom)
    W := {v1, ..., vn}
    while W != empty do
        vi := W.removeNext()
        y := fi(x1, ..., xn)
        if y != xi then
            xi := y
            for each vj in dep(vi) do W.add(vj)
    return (x1, ..., xn)

La lista de trabajo contiene inicialmente todos los nodos, de modo que cada fᵢ se aplique al menos una vez. Termina siempre: en cada iteración, o bien se sube en el retículo Ln, o bien decrece el tamaño de la lista; sólo se puede subir un número finito de veces porque el retículo tiene altura finita, y el bucle acaba cuando la lista se vacía. Y es correcto porque cada iteración tiene sobre (x₁,…,xₙ) el mismo efecto que una iteración de la iteración caótica para alguna elección de i.

La elección de dep es un compromiso entre precisión y coste. Devolver siempre el conjunto de todos los nodos es correcto pero inútil: degenera en el algoritmo ingenuo. Para el análisis de signos, la elección natural es dep = succ; para el de variables vivas, dep = pred. En general, dep es la relación de dependencia del sistema de ecuaciones leída al revés.

Sobre este esquema básico caben más mejoras. Conviene tratar por separado, en turnos sucesivos, las componentes fuertemente conexas del grafo inducido por dep; la lista de trabajo puede convertirse en una cola de prioridad que aproveche conocimiento específico del problema; y en algunos análisis la información de dependencia puede afinarse haciendo que dep consulte también el valor actual de (x₁,…,xₙ) y no sólo el nodo.

7.4 El orden de iteración importa

De todas las decisiones de implementación, la que más afecta al tiempo real es el orden en que se extraen los nodos de la lista de trabajo. No cambia el resultado —cualquier orden converge al mismo punto fijo— pero cambia el número de iteraciones en un factor que puede ser de diez o más.

La regla, para análisis hacia adelante, es orden inverso de postorden (reverse postorder, RPO) sobre un recorrido en profundidad del CFG; para análisis hacia atrás, orden de postorden sobre el CFG invertido. La intuición es evidente: procesar un nodo después de sus predecesores evita recalcularlo cuando llegue la información que faltaba.

Cuando el retículo tiene altura infinita y hay que usar widening (capítulo «8»), el orden deja de ser una cuestión sólo de eficiencia y pasa a afectar a la precisión: el orden topológico débil (weak topological ordering) de Bourdoncle define, además del orden de iteración, en qué nodos se aplica el widening, y elegirlos mal degrada el resultado.

7.5 La solución MFP

En la literatura clásica, la solución que calculan estos algoritmos se llama MFP (Maximal Fixed Point), aunque de hecho lo que se calcula es el menor punto fijo. El nombre viene de que la literatura clásica se centraba en análisis donde ⊔ es ∩, y allí el menor punto fijo respecto de ⊇ es el mayor respecto de ⊆. Es una fuente inagotable de confusión y conviene saber de dónde viene.

La formulación clásica del algoritmo, sobre una instancia (L, ℱ, F, E, ι, f) de un marco monótono, opera sobre etiquetas y aristas en vez de sobre nodos:

INPUT:  una instancia (L, F_set, F, E, iota, f) de un marco monotono
OUTPUT: MFP_o, MFP_.

Paso 1 (inicializacion)
    W := nil
    for all (l, l') in F do W := cons((l, l'), W)
    for all l in F or E do
        if l in E then Analysis[l] := iota else Analysis[l] := bottom

Paso 2 (iteracion)
    while W != nil do
        (l, l') := head(W);  W := tail(W)
        if f_l(Analysis[l]) not_subsumed_by Analysis[l'] then
            Analysis[l'] := Analysis[l'] join f_l(Analysis[l])
            for all l'' with (l', l'') in F do W := cons((l', l''), W)

Paso 3 (presentacion)
    for all l in F or E do
        MFP_o[l] := Analysis[l]
        MFP_.[l] := f_l(Analysis[l])

Es el mismo algoritmo de la «sección 7.3 · El algoritmo de lista de trabajo» con la lista de trabajo poblada de aristas en lugar de nodos. Su terminación se argumenta igual: los pasos 1 y 3 son bucles acotados; en el paso 2, si el programa tiene b etiquetas, la lista contiene inicialmente a lo sumo b² elementos, y cada iteración o bien elimina un elemento sin añadir nada, o bien aumenta estrictamente Analysis[ℓ'] en el retículo, cosa que sólo puede ocurrir un número finito de veces por la condición de cadena ascendente.

El coste, para una instancia con e aristas y retículo de altura h, es O(e·h) operaciones básicas; y como e ≤ b², una cota más burda es O(b²·h). Para reaching definitions con v variables y b etiquetas se tiene h ≤ v·b, lo que da O(v·b³); con un poco más de cuidado se baja a O(b²·v).

7.6 MOP: la solución que realmente queríamos

Hasta ahora hemos aceptado sin discusión que la respuesta correcta es el menor punto fijo del sistema de ecuaciones. Pero el sistema de ecuaciones ya es una aproximación: en cada nodo de confluencia mezcla información de caminos distintos antes de aplicar las funciones de transferencia posteriores, y esa mezcla prematura pierde precisión.

La alternativa ideal es propagar la información a lo largo de cada camino por separado y combinar sólo al final. Es la solución MOP (Meet Over all Paths; el nombre usa meet por el mismo motivo histórico de antes, aunque aquí sea supremo).

Definamos un camino hasta la etiqueta ℓ, sin incluirla, y hasta ℓ incluida:

Para un camino ℓ⃗ = [ℓ₁,…,ℓₙ] se define la función de transferencia compuesta

de modo que para el camino vacío f[] = id. Y entonces:

Hay dos resultados que gobiernan la relación entre ambas soluciones, y son de los más importantes de la disciplina.

Aquí llega la sorpresa. Si MOP es más preciso, ¿por qué no calcularlo directamente?

7.7 Qué significa esto en la práctica

7.8 Lecturas

El resultado sobre conectividad de bucle y convergencia en d + 2 pasadas es de Hecht y Ullman (1975) y Kam y Ullman (1976). El orden topológico débil es de Bourdoncle (1993) y se retoma en el capítulo «8».