Marcos monótonos y los análisis clásicos

Aquí empieza la parte operativa. Con el CFG del capítulo «4» y los retículos del capítulo «5» ya se puede montar la maquinaria que resuelve, con un solo esquema, la mayoría de las preguntas de la tabla del capítulo «1».

6.1 El esquema general

El análisis clásico de flujo de datos parte de un CFG y de un retículo completo de altura finita. El retículo describe la información abstracta que queremos inferir para cada nodo del CFG; puede ser fijo para todos los programas o estar parametrizado por el programa concreto.

A cada nodo v del CFG se le asigna una variable de restricción ⟦v⟧ que toma valores en el retículo. Para cada nodo se define entonces una restricción de flujo de datos que relaciona el valor de esa variable con las de otros nodos —normalmente los vecinos— según qué construcción del lenguaje representa el nodo. Si todas las restricciones resultan ser ecuaciones o inecuaciones con partes derechas monótonas, el algoritmo de punto fijo del capítulo «5» calcula el resultado del análisis como la única solución mínima.

A la combinación de un retículo completo y un espacio de funciones monótonas se la llama marco monótono (monotone framework). Para un programa dado, un marco monótono se instancia especificando el CFG y las reglas que asignan restricciones a sus nodos.

Un análisis es correcto si todas las soluciones de las restricciones se corresponden con información verdadera sobre el programa. Las soluciones pueden ser más o menos imprecisas, pero calcular la mínima da el mayor grado de precisión posible.

En este capítulo usamos el subconjunto de TIP sin llamadas a función, sin punteros y sin registros; esas características se estudian en los capítulos «10», «17» y «18».

6.2 Análisis de signos

Retomamos el análisis de signos del capítulo «5». El objetivo es determinar el signo —positivo, cero, negativo— de todas las expresiones de un programa. Partimos del retículo diminuto Sign = flat({+, 0, -}), y como queremos un valor abstracto por variable, definimos el retículo de aplicaciones

donde Var es el conjunto de variables del programa. Cada elemento es un estado abstracto. A cada nodo v le asignamos una variable de restricción ⟦v⟧ que denota el estado abstracto inmediatamente después de v. El retículo Staten, con n el número de nodos, modela la información de todo el programa.

Definimos primero una función auxiliar que combina los estados abstractos de los predecesores:

Por ejemplo, en este CFG se tiene JOIN(⟦a=c+2⟧) = ⟦c=b⟧ ⊔ ⟦c=-5⟧:

             +---------+
             |  b > 5  |
             +----+----+
             true/    \false
                v      v
           +------+  +--------+
           | c=b  |  | c=-5   |
           +---+--+  +---+----+
                \       /
                 v     v
              +-----------+
              |  a = c+2  |
              +-----------+

La regla más interesante es la de la asignación, para nodos v de la forma X = E:

Es decir: el estado abstracto tras la asignación es igual al inmediatamente anterior, salvo que el valor abstracto de X pasa a ser el resultado de evaluar abstractamente E. La función eval realiza esa evaluación abstracta respecto de un estado σ:

eval(sigma, X)          = sigma(X)
eval(sigma, I)          = sign(I)
eval(sigma, input)      = T
eval(sigma, E1 op E2)   = op^(eval(sigma, E1), eval(sigma, E2))

donde sign da el signo de una constante entera y op^ es la versión abstracta del operador. Para la suma:

Para el producto:

Dos observaciones que se le escapan a mucha gente al implementar esto por primera vez. La primera: ⊥ es absorbente en todas las tablas. ⊥ significa «este punto es inalcanzable o el valor no es un número», y cualquier operación sobre un valor inexistente sigue siendo inexistente; si se pone 0 en su lugar el análisis deja de ser correcto. La segunda: la división no es tan simple como parece. + /^ + es ⊤, no +, porque la división entera trunca y 1/2 = 0. Y toda división por 0 da ⊥, porque no produce ningún valor.

Las reglas para el resto de nodos son inmediatas. Para las declaraciones var X₁,…,Xₙ, el estado asigna ⊤ a las nuevas variables —no están inicializadas—; para todos los demás nodos, ⟦v⟧ = JOIN(v).

6.3 La estructura común

Los análisis de esta familia se distinguen entre sí por cuatro elecciones, y sólo por cuatro.

Dirección. Un análisis hacia adelante (forward) calcula, para cada punto, información sobre lo que ha ocurrido antes; propaga desde los predecesores. Uno hacia atrás (backward) calcula información sobre lo que ocurrirá después; propaga desde los sucesores. La única diferencia técnica es si JOIN(v) recorre pred(v) o succ(v).

Combinación. Cuando confluyen varios caminos hay que combinar. Si la combinación es unión, el análisis detecta propiedades que se cumplen en al menos un camino de ejecución: son los análisis may. Si es intersección, detecta propiedades que se cumplen en todos los caminos: son los análisis must.

Aquí conviene un aviso que ha confundido a varias generaciones de estudiantes: la relación de orden del retículo se elige para que la combinación sea siempre el supremo ⊔. En un análisis may eso significa ⊑ = ⊆ y ⊔ = ∪; en uno must, ⊑ = ⊇ y ⊔ = ∩. Algunos libros clásicos dibujan los retículos «del revés» y llaman meet a la operación de combinación —de ahí el nombre MOP, meet over all paths—. No cambia ningún resultado, pero cambia todos los símbolos.

Función de transferencia. Qué le hace cada nodo a la información. En la enorme mayoría de los análisis clásicos tiene la forma

donde kill es lo que el bloque destruye y gen lo que produce. A los análisis cuya función de transferencia tiene esta forma se los llama problemas gen/kill, o marcos de vector de bits (bit vector frameworks), porque el estado se representa como un vector de bits y las funciones de transferencia se implementan con dos máscaras y dos instrucciones.

Valor extremal. Qué información hay en el punto de partida: ι en las etiquetas iniciales E, y ⊥ en las demás.

Con estas cuatro elecciones, el sistema de ecuaciones de cualquier análisis clásico tiene la forma:

donde ιℓE vale ι si ℓ ∈ E y ⊥ en caso contrario, y F es flow(S) para los análisis hacia adelante y flowR(S) —el flujo invertido— para los de hacia atrás. Para los análisis hacia adelante, Analysis∘ es la información a la entrada del bloque y Analysis• la de la salida; para los de hacia atrás es al revés.

6.4 Los cuatro análisis clásicos

Se presentan sobre WHILE, con la notación de etiquetas del capítulo «3». AExp es el conjunto de expresiones no triviales que aparecen en el programa, Var el de variables, Lab el de etiquetas, y FV(a) el conjunto de variables libres de la expresión a.

6.4.1 Definiciones alcanzables (reaching definitions)

Una asignación —llamada definición en la literatura clásica— de la forma [x := a]ℓ alcanza un punto del programa si hay una ejecución en la que x se asignó por última vez en ℓ al llegar a ese punto.

Es el análisis fundamental para la reconstrucción de dependencias de datos, y es el que se sustituye por la forma SSA en el capítulo «12». Es forward y may: ⊑ = ⊆, ⊔ = ∪, ⊥ = ∅.

Los conjuntos gen y kill para una asignación [x := a]ℓ:

kill([x := a]^l)  = { (x, l') | l' es una definicion de x en el programa }
                    union { (x, ?) }
gen([x := a]^l)   = { (x, l) }

kill([skip]^l)    = {}          gen([skip]^l)  = {}
kill([b]^l)       = {}          gen([b]^l)     = {}

El valor extremal es ι = { (x, ?) | x ∈ FV(S) }: el símbolo ? es una pseudo-etiqueta que representa «definida antes de empezar», y sirve para registrar la posibilidad de que una variable no inicializada alcance un punto. Es un truco notacional que merece recordarse, porque convierte «uso de variable no inicializada» en un caso particular del mismo análisis.

Para el programa factorial del capítulo «1», [y:=x]¹; [z:=1]²; while [y>1]³ do ([z:=z*y]⁴; [y:=y-1]⁵); [y:=0]⁶, el resultado es:

Léase la fila 4: al ejecutarse z := z*y, el valor de z puede venir de la inicialización ² o de la iteración anterior ⁴, y el de y de ¹ o de ⁵. Eso es exactamente la información que un decompilador necesita para dibujar las flechas de dependencia de datos.

6.4.2 Variables vivas (live variables)

Una variable está viva en un punto si existe algún camino desde ese punto hasta un uso de la variable sin que se le asigne nada por el camino. Es backward y may.

El retículo es State = (℘(Var), ⊆), con JOIN(v) = ⋃w ∈ succ(v) ⟦w⟧. La regla para asignaciones:

El conjunto de variables vivas antes de la asignación es el de después, quitando la variable que se escribe y añadiendo las que hacen falta para evaluar la parte derecha. Para condiciones de rama y salidas, ⟦v⟧ = JOIN(v) ∪ vars(E); para declaraciones, ⟦v⟧ = JOIN(v) \ {X₁,…,Xₙ}; y ⟦exit⟧ = ∅.

Un ejemplo completo, que además muestra para qué sirve. Sea el programa:

var x,y,z;
x = input;
while (x>1) {
    y = x/2;
    if (y>3) x = x-y;
    z = x-4;
    if (z>0) x = x/2;
    z = z-1;
}
output x;

El sistema de restricciones es:

[[entry]]      = [[var x,y,z]]
[[var x,y,z]]  = [[x=input]] \ {x,y,z}
[[x=input]]    = [[x>1]] \ {x}
[[x>1]]        = ([[y=x/2]] union [[output x]]) union {x}
[[y=x/2]]      = ([[y>3]] \ {y}) union {x}
[[y>3]]        = [[x=x-y]] union [[z=x-4]] union {y}
[[x=x-y]]      = ([[z=x-4]] \ {x}) union {x,y}
[[z=x-4]]      = ([[z>0]] \ {z}) union {x}
[[z>0]]        = [[x=x/2]] union [[z=z-1]] union {z}
[[x=x/2]]      = ([[z=z-1]] \ {x}) union {x}
[[z=z-1]]      = ([[x>1]] \ {z}) union {z}
[[output x]]   = [[exit]] union {x}
[[exit]]       = {}

y su solución mínima:

[[entry]] = {}          [[z=x-4]]    = {x}
[[var ...]] = {}        [[z>0]]      = {x,z}
[[x=input]] = {}        [[x=x/2]]    = {x,z}
[[x>1]]  = {x}          [[z=z-1]]    = {x,z}
[[y=x/2]] = {x}         [[output x]] = {x}
[[y>3]]  = {x,y}        [[exit]]     = {}
[[x=x-y]] = {x,y}

De aquí un compilador listo deduce dos cosas: que y y z nunca están vivas a la vez, luego pueden compartir registro; y que el valor escrito en z = z-1 nunca se lee, luego la asignación puede eliminarse. El programa se optimiza a:

var x,yz;
x = input;
while (x>1) {
    yz = x/2;
    if (yz>3) x = x-yz;
    yz = x-4;
    if (yz>0) x = x/2;
}
output x;

6.4.3 Expresiones disponibles (available expressions)

Una expresión no trivial está disponible en un punto si su valor actual ya se ha calculado antes en la ejecución, por todos los caminos. Es forward y must, así que el retículo se ordena por inclusión inversa: State = (℘(AExp), ⊇), con ⊥ = AExp, ⊤ = ∅ y ⊔ = ∩.

Para el programa

var x,y,z,a,b;
z = a+b;
y = a*b;
while (y > a+b) {
    a = a+1;
    x = a+b;
}

hay cuatro expresiones no triviales, {a+b, a*b, y>a+b, a+1}, y el retículo es el retículo de partes de ese conjunto ordenado por ⊇. El elemento máximo es ∅, que corresponde a la información trivial «no hay nada disponible».

Los conjuntos gen y kill para una asignación [x := a]ℓ:

gen([x := a]^l)  = { a' in AExp(a) | x not in FV(a') }
kill([x := a]^l) = { a' in AExp | x in FV(a') }

Es decir, la asignación genera las subexpresiones de su parte derecha que no dependen de la variable asignada, y mata todas las expresiones del programa que sí dependen de ella. Este análisis es la base de la eliminación de subexpresiones comunes, que el capítulo «22» generaliza a PRE.

6.4.4 Expresiones muy ocupadas (very busy expressions)

Una expresión está muy ocupada en un punto si se evaluará seguro antes de que se modifique ninguna de sus variables, por todos los caminos. Es backward y must. Sirve para el movimiento de código hacia atrás (code hoisting): si una expresión está muy ocupada en un punto, se puede calcular allí y reutilizar en todas las ramas.

6.5 Las cuatro instancias, en una tabla

Toda la «sección 6.4 · Los cuatro análisis clásicos» se resume así. Ésta es la tabla que conviene tener a mano al implementar cualquier análisis nuevo, porque lo que se hace en la práctica es rellenar una columna más.

y en los cuatro casos

Los cuatro son marcos monótonos y, además, distributivos.

6.6 Coste

Estimemos el coste del análisis de variables vivas con el algoritmo ingenuo del capítulo «5». Si el programa tiene n nodos y b variables, el retículo ℘(Var)n tiene altura b·n, lo que acota el número de iteraciones. Cada elemento se representa como un vector de bits de longitud b·n. Suponiendo |succ(v)| ≤ 2 para todo nodo —lo que siempre puede conseguirse—, en cada iteración hay que hacer O(n) operaciones de intersección, diferencia o igualdad sobre conjuntos de tamaño b, cada una en tiempo O(b). En total, O(b·n) por iteración y O(b²·n²) en el peor caso.

Es una cota pesimista: el algoritmo ingenuo recalcula todo en cada vuelta, incluidas las componentes que no pueden haber cambiado. El capítulo «7» se dedica a evitarlo.