Eliminación de redundancias — PRE, GVN y desofuscación

Aquí cambia la dirección. Hasta ahora todo eran análisis: calcular información sobre el programa. Esta última parte usa esa información para transformar el programa, y muestra que las mismas transformaciones que un compilador aplica para optimizar sirven, aplicadas al binario, para deshacer la ofuscación.

22.1 Redundancia total y parcial

Durante la ejecución de un programa, ciertos cálculos pueden repetirse muchas veces produciendo el mismo resultado. Esos cálculos redundantes se eliminan guardando el resultado de los anteriores y reutilizándolo en vez de recalcularlo.

Hay dos tipos:

• Un cálculo es totalmente redundante (fully redundant) si ya ha ocurrido antes con independencia del flujo de control. Su eliminación es la clásica eliminación de subexpresiones comunes.
• Un cálculo es parcialmente redundante (partially redundant) si ha ocurrido sólo por algunos caminos.

La redundancia total es el caso particular de la parcial en que el cálculo previo ocurre por todos los caminos. La eliminación de redundancias parciales (partial redundancy elimination, PRE) es potente porque subsume a la vez la eliminación de subexpresiones comunes globales y el movimiento de código invariante de bucle.

  (a)  a+b se calcula solo por la rama izquierda

        ... <- a+b                   ... <- a+b      ... <- a+b
             \      /                     \             /
              \    /                       \           /
           ... <- a+b                    (eliminado)

  (b)  a+b es invariante de bucle

        ... <- a+b                    ... <- a+b
             |    ^                        |     ^
             v    |                        v     |
        ... <- a+b                     (eliminado)

Ambos son ejemplos de redundancia estrictamente parcial, en los que hacen falta inserciones para eliminarla. Una redundancia total, en cambio, se borra sin insertar nada.

Hay además dos maneras de mirar un cálculo: cómo se calcula y qué valor produce. La primera se refiere al operador y a sus operandos, es decir, a cómo está escrito; la segunda, al valor generado. De ahí dos familias de algoritmos:

• Dirigidos por la sintaxis (syntax-driven): dos cálculos son el mismo si son la misma operación sobre los mismos operandos. La redundancia sólo puede surgir si los valores de las variables no han cambiado entre ambas ocurrencias.
• Dirigidos por el valor (value-driven): hay redundancia siempre que dos cálculos produzcan el mismo valor. Así, a + b y a + c calculan lo mismo si se puede determinar que b y c valen lo mismo.

Este capítulo trata sobre todo el caso sintáctico, y la «sección 22.7 · Promoción de registros» extiende la discusión al basado en valores.

Supondremos la forma SSA convencional del capítulo «12», en la que cada φ-web está libre de interferencia, y la forma HSSA del capítulo «16», que modela completamente el aliasing. Y trabajaremos con árboles de expresión maximales: a + b*c - d se representa tal cual, sin asignaciones a temporales para los valores intermedios.

22.2 Por qué PRE y SSA están relacionados

La conexión es más profunda de lo que parece, y merece verse antes que el algoritmo.

Considérese una única ocurrencia de a + b en el programa. En la región del CFG dominada por esa ocurrencia, cualquier aparición posterior de a + b es totalmente redundante, suponiendo que a y b no se modifiquen. Siguiendo el flujo, una vez que se pasan las fronteras de dominancia, cualquier aparición posterior es parcialmente redundante.

              +----------------+
              |  ... <- a + b  |
              +--------+-------+
                       |
        region dominada|  --> aqui a+b es TOTALMENTE redundante
                       |
     - - - - - - - - - + - - - - - - - -   frontera de dominancia
                       |
                       |  --> aqui a+b es PARCIALMENTE redundante
                       v

Y las fronteras de dominancia son exactamente donde se insertan las φ al construir SSA. Como las redundancias parciales empiezan en las fronteras de dominancia, tienen que estar relacionadas con las φ de SSA. De hecho, el mismo enfoque disperso que modela las relaciones use-def entre las apariciones de una variable sirve para modelar las relaciones de redundancia entre las apariciones de a + b.

22.3 El grafo de redundancia factorizado

El algoritmo que presentamos, SSAPRE, explota esa observación. Si una ocurrencia aⱼ + bⱼ es redundante respecto de aᵢ + bᵢ, SSAPRE construye una arista de redundancia que las conecta. Para exponer las redundancias parciales potenciales se introduce el operador Φ —mayúscula, para distinguirlo de la φ de las variables— en las fronteras de dominancia de las ocurrencias, lo que factoriza las aristas de redundancia en los puntos de confluencia.

El grafo resultante se llama grafo de redundancia factorizado (factored redundancy graph, FRG), y puede entenderse como la forma SSA de las expresiones.

Para hacerlo intuitivo se introduce un temporal hipotético h, que puede pensarse como el temporal donde se guardará el valor de la expresión. El FRG es entonces el grafo SSA de h. Obsérvese que todavía no se ha decidido dónde debe definirse ni usarse h: eso es precisamente lo que el algoritmo va a calcular.

La construcción sigue los mismos dos pasos que la de SSA ordinaria.

Inserción de Φ. Se insertan Φ en las fronteras de dominancia de todas las ocurrencias de la expresión, para no perder ninguna posición posible de colocación. Y se insertan además las Φ provocadas por alteración de la expresión: éstas se disparan por la aparición de una φ de cualquiera de los operandos de la expresión.

  (a) frontera de dominancia            (b) alteracion de la expresion

  1: ... <- a1 + b1  [h]                 1: ... <- a1+b1 [h]     2: a2 <- ...
          \        /                              \                 /
           \      /                            3:  a3 <- phi(a1,a2)
   2: [h] <- Phi([h], [h])                         [h] <- Phi([h], [h])

Renombrado. Se asignan versiones SSA a h de forma que las ocurrencias renombradas a la misma versión de h calculen el mismo valor. Se recorre el árbol de dominadores en preorden, como en la construcción de SSA, con dos modificaciones: se mantiene una pila de renombrado para la expresión además de las de las variables, y las entradas de la pila de la expresión se desapilan al retroceder más allá de los bloques donde la expresión recibió su versión.

Hay tres clases de ocurrencia: las reales, que estaban en el programa original; las Φ-def, insertadas; y las Φ-use, los operandos de las Φ, que se consideran ocurridos al final de los bloques predecesores correspondientes.

Una Φ recibe siempre una versión nueva. Para las otras dos clases se comprueba la versión actual de cada variable de la expresión —la cima de su pila— contra la versión de la variable correspondiente en la ocurrencia que está en la cima de la pila de la expresión:

• si todas las versiones de variable coinciden, se asigna la misma versión de h que la cima de la pila de la expresión;
• si alguna no coincide y la ocurrencia es real, se asigna una versión nueva;
• si alguna no coincide y la ocurrencia es un Φ-use, se le asigna la clase especial ⊥, que denota que el valor de la expresión no está disponible en ese punto.

  (a)                                    (b)
       ... <- a1+b1 [h1]                        [h1] <- Phi([h1], _|_)
        /            \                          ... <- a1+b1 [h1]
  ... <- a1+b1 [h1]   b2 <- ...
                      ... <- a1+b2 [h2]

El FRG captura todas las redundancias de a + b en el programa, y contiene exactamente la información necesaria para determinar la colocación óptima del código. Y como las redundancias estrictamente parciales sólo pueden ocurrir en los nodos Φ, las inserciones sólo hay que considerarlas en las Φ.

22.4 Los cuatro criterios

Llamemos X a la expresión que se optimiza. Una colocación (placement) es el conjunto de puntos del programa optimizado donde se calcula X; los puntos de cálculo originales son los del programa de partida. El objetivo de SSAPRE es encontrar una colocación que satisfaga, en este orden, cuatro criterios:

Cada ocurrencia de X en su punto original se califica con exactamente uno de tres atributos: totalmente redundante, estrictamente parcialmente redundante o no redundante.

Como todo algoritmo de PRE, SSAPRE procede en dos pasos: primero determina el mejor conjunto de puntos de inserción, de modo que el máximo número de ocurrencias estrictamente parcialmente redundantes se vuelvan totalmente redundantes; y después borra los cálculos totalmente redundantes, teniendo en cuenta los insertados. El segundo paso es rutinario; la dificultad está en el primero.

Se supone que todas las aristas críticas del CFG se han eliminado insertando bloques vacíos, exactamente como en la destrucción de SSA del capítulo «13». Las inserciones se realizan sólo en los Φ-use, lo que en la práctica significa insertar al final del bloque predecesor correspondiente.

22.5 Seguridad: downsafety

El criterio de seguridad implica que sólo se debe insertar en las Φ donde X es downsafe, es decir, totalmente anticipado: donde se sabe que la expresión se calculará seguro más adelante.

Una Φ no es downsafe si existe un camino desde ella a lo largo del cual la expresión no se calcula antes de la salida del programa o antes de que alguna de sus variables se redefina. Salvo por bucles sin salida, eso sólo puede ocurrir por dos causas: (muerta) hay un camino a la salida, o a una alteración de la expresión, en el que la versión resultado de la Φ no se usa; o (transitiva) la versión resultado aparece como operando de otra Φ que no es downsafe.

El caso (muerta) es la inicialización de la propagación hacia atrás de ¬downsafe; todas las demás Φ se marcan inicialmente como downsafe. La propagación se basa en el caso (transitiva), con una salvedad importante: una ocurrencia real de la expresión bloquea la propagación. Para expresarlo se asocia a cada operando de Φ una bandera has_real_use, que se pone a cierto cuando el operando está definido por otra Φ y el camino desde su Φ definidora hasta su aparición como operando cruza una ocurrencia real.

foreach f in {Phi's del programa} do
    if existe camino P a la salida o a una alteracion de la expresion
       a lo largo del cual f no se usa then
        downsafe(f) := false

foreach f in {Phi's del programa} do
    if not downsafe(f) then
        foreach operando w de f do
            if not has_real_use(w) then Reset_downsafe(w)

function Reset_downsafe(X):
    if def(X) no es una Phi then return
    f := def(X)
    if not downsafe(f) then return
    downsafe(f) := false
    foreach operando w de f do
        if not has_real_use(w) then Reset_downsafe(w)

Obsérvese que el análisis de flujo de datos se hace sobre el FRG, no sobre el CFG, y por eso tiene complejidad lineal: es propagación dispersa, exactamente en el sentido del capítulo «15».

22.6 Optimalidad computacional y de rango de vida

Eliminadas las Φ inseguras, hay que descartar las que no pueden ser candidatas a inserción en ninguna colocación computacionalmente óptima. Se define el atributo can_be_avail, cuyo propósito es identificar la región donde, tras las inserciones adecuadas, el cálculo puede llegar a estar totalmente disponible. Una Φ es ¬can_be_avail si y sólo si insertar allí violaría la optimalidad computacional:

Podría calcularse avail por separado con un análisis de disponibilidad total, pero se haría trabajo inútil, porque no hace falta su valor dentro de la región donde las Φ son downsafe. Se calcula por tanto can_be_avail directamente: se inicializa una Φ a ¬can_be_avail si no es downsafe y alguno de sus operandos es ⊥, y se propaga ¬can_be_avail hacia adelante cuando una Φ no downsafe tiene un operando definido por una Φ que es ¬can_be_avail y ese operando no está marcado has_real_use.

Tras esto ya sería posible insertar en todas las Φ con can_be_avail. El resultado sería computacionalmente óptimo, pero no óptimo en rango de vida: se estarían insertando cálculos antes de lo necesario. Por eso se calcula un tercer atributo, later, que marca las Φ en las que la inserción puede posponerse sin perder ningún cálculo. Los puntos de inserción definitivos son

y en ellos se inserta el cálculo, se introduce el temporal real que sustituye a h, y se procede al segundo paso: borrar las ocurrencias totalmente redundantes.

22.7 Promoción de registros

La misma maquinaria sirve para un problema aparentemente distinto: decidir qué variables de memoria conviene mantener en registro. Se plantea como optimización de colocación de dos operaciones:

• colocación de cargas (load placement): tratar cada carga x como una expresión y aplicarle PRE. Las cargas parcialmente redundantes se convierten en totalmente redundantes y se eliminan; el resultado es que el valor se carga una vez y se mantiene en el temporal.
• colocación de almacenamientos (store placement): el problema dual, resuelto por el algoritmo simétrico —PRE «al revés», sobre el CFG invertido—, que retrasa los almacenamientos hasta el último punto posible.

La combinación de ambos es la promoción de registros (register promotion), y es una de las optimizaciones más rentables de un compilador. Que se reduzca a PRE es un resultado elegante y no evidente.

22.8 Value numbering

Todo lo anterior es sintáctico: a + b y a + c se consideran distintos aunque b y c valgan lo mismo. La numeración de valores (value numbering) levanta esa restricción asignando a cada cálculo un número de valor, de forma que dos cálculos con el mismo número producen con seguridad el mismo valor.

La versión local, dentro de un bloque básico, es un algoritmo clásico y trivial: se recorre el bloque manteniendo una tabla hash de expresiones ya vistas; cada expresión se busca por su operador y los números de valor de sus operandos, y si está, reutiliza su número; si no, recibe uno nuevo. Con SSA se generaliza a todo el procedimiento —numeración global de valores (global value numbering, GVN)— de dos maneras:

• Pesimista, basada en tabla hash: se recorre el árbol de dominadores manteniendo la tabla, con la ventaja de que un valor calculado en un bloque está disponible en todos los que domina. Es simple y rápida, y no descubre congruencias a través de las φ de los bucles.
• Optimista, por particionamiento: se supone inicialmente que todas las expresiones con el mismo operador son congruentes y se refina la partición hasta el punto fijo. Descubre congruencias en bucles que la anterior no ve, a costa de más trabajo.

Con los números de valor, la eliminación de redundancias basada en valores es directa: un cálculo es redundante si otro con el mismo número de valor lo domina. Y la combinación con PRE —GVN-PRE— es la forma más potente y la que implementan LLVM y GCC.

22.9 Desofuscación

22.10 Lecturas

Las referencias clásicas son Morel y Renvoise (1979) para la formulación original de PRE, Knoop, Rüthing y Steffen (1992) para lazy code motion —de donde procede la separación entre optimalidad computacional y de rango de vida—, Chow et al. (1997) para SSAPRE, Alpern, Wegman y Zadeck (1988) para el particionamiento en GVN, y Briggs, Cooper y Simpson (1997) para las variantes basadas en tabla hash.