Construcción y destrucción estándar de SSA

La construcción de SSA es el proceso de traducir un programa que no está en SSA a otro que satisface sus restricciones. En un compilador optimizador ocurre en una de las primeras fases del middle-end, cuando el programa ya se ha convertido a código intermedio de tres direcciones. La destrucción de SSA —o out-of-SSA translation— se hace después de todas las optimizaciones y antes de la generación de código. Los algoritmos de este capítulo son los de los artículos fundacionales: fáciles de implementar, de eficiencia aceptable, y por eso implementados en la mayoría de compiladores actuales.

Usaremos como ejemplo el CFG del capítulo «4», que reproducimos con su código:

              +-------+
              |   r   |  entry
              +---+---+
                  |
                  v
       +----->+-------+
       |      |   A   |
       |      +---+---+
       |       /       \
       |      v         v
       |  +-------+  +-------------+
       |  |   B   |  |      C      |
       |  | y <- 0|  | tmp <- x    |
       |  | x <- 0|  | x   <- y    |
       |  +---+---+  | y   <- tmp  |
       |      |      +----+--------+
       |      |           |    \
       |      v           v     \
       |  +---------------+      |
       |  |       D       |      |
       |  | x <- f(x, y)  |      |
       |  +-------+-------+      |
       |          |   \          |
       +----------+    \         |
                        v        v
                     +---------------+
                     |       E       |
                     |     ret x     |
                     +---------------+

Obsérvese que en ciertos caminos hay variables que se usan sin haberse definido; por ejemplo x en el camino r → A → C. Volveremos sobre ello.

13.1 Las dos fases

El algoritmo original de construcción consta de dos fases distintas:

1. Inserción de funciones φ. Realiza división de rangos de vida (live-range splitting) para asegurar que todo uso de una variable v esté alcanzado por exactamente una definición de v. Los rangos resultantes tienen la propiedad de tener una única definición, situada al principio de cada rango.
2. Renombrado de variables. Asigna un nombre único a cada rango de vida. Esta segunda fase reescribe los nombres en las sentencias del programa de forma que el texto contenga una sola definición de cada variable, y que cada uso se refiera a su única definición alcanzable.

Nos centraremos en la SSA mínima, en el sentido del capítulo «12».

13.2 Fronteras de dominancia y DJ-graphs

Ya se definieron en el capítulo «4», pero recordemos lo esencial: DF(n) contiene todos los nodos x tales que n domina a un predecesor de x pero n no domina estrictamente a x; DF⁺(S) es la frontera iterada; y DF⁺(S) = J(S ∪ {r}).

La construcción de SSA mínima requiere insertar φ para cada variable v en J(Defs(v)). El algoritmo original usa DF⁺(Defs(v)), que es una sobreaproximación del conjunto de confluencia: supone implícitamente una definición de cada variable en el nodo de entrada r. Esa suposición es precisamente lo que produce la propiedad de dominancia.

Para calcular la frontera de dominancia, dado el árbol de dominadores, resulta cómoda la notación de DJ-graph. Su esqueleto es el árbol de dominadores, cuyas aristas son las D-edges (dominance edges). Se aumenta con las J-edges (join edges), que corresponden a todas las aristas del CFG cuyo origen no domina estrictamente a su destino. Una DF-edge es una arista cuyo destino está en la frontera de dominancia de su origen.

Por definición hay una DF-edge (a, b) entre dos nodos tales que a domina a un predecesor de b pero no domina estrictamente a b. Dicho de otro modo: para cada J-edge (a, b), todos los ancestros de a —incluido a— que no dominan estrictamente a b tienen a b en su frontera de dominancia. Eso da directamente el algoritmo:

DF_all(CFG):
    for each edge (a, b) in CFG do
        x := a
        while x does not strictly dominate b do
            DF(x) := DF(x) union {b}
            x := immediate_dominator(x)

Y como la frontera iterada es sencillamente la clausura transitiva de la frontera, el DF⁺-graph es la clausura transitiva del DF-graph. El capítulo «14» presenta algoritmos que evitan construirla explícitamente.

13.3 Inserción de las funciones φ

El concepto de frontera de dominancia lleva de manera natural a un algoritmo que coloca las φ variable a variable: para una variable v, se colocan φ en DF⁺(Defs(v)).

Para el ejemplo, el conjunto de nodos que contienen definiciones de x es {B, C, D}. Su frontera de dominancia iterada es {A, D, E} —y coincide con DF, aquí no hace falta iterar—. Por tanto hay que insertar φ para x al principio de A, D y E:

              +-------+
              |   r   |  entry
              +---+---+
                  |
                  v
       +----->+------------------+
       |      |   A              |
       |      |  x <- phi(x, x)  |
       |      +---+----------+---+
       |       /                \
       |      v                  v
       |  +-------+     +-------------+
       |  |   B   |     |      C      |
       |  | y <- 0|     | tmp <- x    |
       |  | x <- 0|     | x   <- y    |
       |  +---+---+     | y   <- tmp  |
       |      |         +----+--------+
       |      v              |     \
       |  +--------------------+    |
       |  |       D            |    |
       |  |  x <- phi(x, x)    |    |
       |  |  x <- f(x, y)      |    |
       |  +-------+------------+    |
       |          |   \             |
       +----------+    \            |
                        v           v
                +------------------------+
                |       E                |
                |   x <- phi(x, x)       |
                |   ret x                |
                +------------------------+

El algoritmo supone precalculada la frontera de dominancia de cada nodo y calcula la iterada sobre la marcha. Usa una lista de trabajo W de puntos de definición pendientes y un conjunto F de bloques donde ya se ha insertado una φ, para evitar inserciones repetidas:

for v : cada variable del programa original do
    F := {}          // bloques donde ya hay una phi para v
    W := {}          // bloques que contienen definiciones de v
    for d in Defs(v) do
        let B be the basic block containing d
        W := W union {B}
    while W != {} do
        remove a basic block X from W
        for Y in DF(X) do
            if Y not in F then
                add  v <- phi(...)  at entry of Y
                F := F union {Y}
                if Y not in Defs(v) then
                    W := W union {Y}

Como una φ es a su vez una definición, puede exigir insertar más φ: ésa es la causa de las inserciones en W dentro del bucle interior, y es como se calcula DF⁺ sobre la marcha. El conjunto F es necesario porque las fronteras de dominancia de nodos distintos pueden intersecarse —en el ejemplo, DF(B) y DF(C) contienen ambos a D— pero una sola φ por variable y bloque basta para tratar todas las definiciones entrantes.

Traza completa para la variable x:

Una vez insertadas las φ, el programa suele contener todavía varias definiciones por variable, pero ahora hay una sola sentencia de definición que alcanza cada uso. Para los usos que aparecen como argumentos de una φ, el convenio es tratarlos como si ocurrieran en la arista de entrada correspondiente, o al final del predecesor correspondiente. Con ese convenio, las cadenas def-use quedan alineadas con el árbol de dominadores: la única definición que alcanza cada uso lo domina.

13.4 Renombrado de variables

La inserción de φ ha dividido los rangos de vida de cada variable original en trozos. El renombrado asocia a cada rango un nombre nuevo, también llamado versión (version).

Gracias a la propiedad de dominancia, renombrar es sencillo mediante un recorrido en profundidad del árbol de dominadores. Durante el recorrido, para cada variable v hay que recordar la versión de su única definición alcanzable en el punto actual, que es la definición más cercana que lo domina. La guardamos en una ranura por variable, v.reachingDef, que se actualiza a medida que avanza el recorrido:

foreach v : Variable do
    v.reachingDef := bottom

foreach BB in preorden DFS del arbol de dominadores do
    foreach i : instruccion de BB en orden do
        foreach v usada por i, si i no es una phi do
            updateReachingDef(v, i)
            replace this use of v by v.reachingDef in i
        foreach v definida por i (puede ser una phi) do
            updateReachingDef(v, i)
            create fresh variable v'
            replace this definition of v by v' in i
            v'.reachingDef := v.reachingDef
            v.reachingDef  := v'
    foreach phi en un sucesor de BB do
        foreach v usada por phi do
            updateReachingDef(v, phi)
            replace this use of v by v.reachingDef in phi

con la función auxiliar

updateReachingDef(v, i):
    // recorre la cadena de definiciones de v hasta encontrar la mas
    // cercana que domina i, y actualiza v.reachingDef in situ
    r := v.reachingDef
    while not (r == bottom or definition(r) dominates i) do
        r := r.reachingDef
    v.reachingDef := r

Nótese el orden dentro de cada bloque: primero los usos, luego las definiciones. Y nótese que los argumentos de las φ de los sucesores se renombran al terminar el bloque, coherentemente con el convenio de la sección anterior.

Aplicado al ejemplo, se obtiene:

              +-----------------------------+
              |   A                         |
       +----->|  l1: x1 <- phi(x5, _|_)     |
       |      |      y1 <- phi(y4, _|_)     |
       |      +---+---------------------+---+
       |         /                       \
       |        v                         v
       |  +-----------+        +---------------------+
       |  |   B       |        |     C               |
       |  |  y2 <- 0  |        | l3: tmp1 <- x1      |
       |  | l2:x2 <- 0|        | l4: x3   <- y1      |
       |  +-----+-----+        |     y3   <- tmp1    |
       |        |              +------+--------------+
       |        v                     |       \
       |  +------------------------+  |        |
       |  |   D                    |<-+        |
       |  | l5: x4 <- phi(x2, x3)  |           |
       |  |     y4 <- phi(y2, y3)  |           |
       |  | l6: x5 <- f(x4, y4)    |           |
       |  +-------+----------------+           |
       |          |    \                       |
       +----------+     \                      |
                         v                     v
              +---------------------------------+
              |   E                             |
              | l7: x6 <- phi(x5, x3)           |
              |     y5 <- phi(y4, y3)           |
              | l8: ret x6                      |
              +---------------------------------+

Traza del renombrado, siguiendo únicamente x. Las etiquetas lᵢ marcan las instrucciones que mencionan x:

Las líneas donde x.reachingDef se «actualiza a» un valor anterior son las llamadas a updateReachingDef que suben por la cadena porque la definición registrada ya no domina el punto actual. Es el mecanismo que sustituye a la pila del algoritmo original.

13.5 Qué sabor produce este algoritmo

Volviendo a las propiedades del capítulo «12», el algoritmo anterior produce una forma SSA que:

• Es mínima. Tras la inserción de φ y antes del renombrado, el CFG contiene el número mínimo de φ para que exactamente una definición de cada variable alcance cada punto del grafo.
• No es podada. Algunas de las φ insertadas pueden estar muertas; en el ejemplo, y₅ no se usa nunca.
• Es convencional. La transformación que renombra todas las variables φ-relacionadas a un representante único y elimina las φ es un algoritmo de destrucción correcto.
• Tiene la propiedad de dominancia. Cada uso está dominado por su única definición, y eso se debe precisamente a haber usado fronteras de dominancia iteradas en lugar de conjuntos de confluencia. Cuando DF⁺(Defs(v)) difiere de J(Defs(v)), existe al menos un punto alcanzable tanto desde r como desde un punto de definición. En el ejemplo, uno de los usos de la φ insertada en A para x no tiene ninguna definición alcanzable real que lo domine: es el ⊥ con que se inicializa cada ranura reachingDef. Una implementación real puede usar un NULL, crear una variable indefinida ficticia en la entrada del CFG, o crear pseudo-operaciones indefinidas sobre la marcha justo antes del uso.

13.6 Destrucción de SSA

Las funciones φ no son instrucciones máquina ejecutables, así que hay que eliminarlas antes de generar código.

Cuando el código SSA está recién construido y no se ha transformado, es convencional y su destrucción es directa: basta renombrar todas las variables φ-relacionadas —operandos fuente y destino de la misma φ— a una variable representante única. Entonces cada φ tiene nombres sintácticamente idénticos en todos sus operandos y puede eliminarse, fusionando los rangos de vida.

El descubrimiento de las φ-webs se hace eficientemente con union-find:

for each variable v do
    phiweb(v) := {v}
for each instruction of the form  a_dest = phi(a_1, ..., a_n) do
    for each source operand a_i do
        union(phiweb(a_dest), phiweb(a_i))

El problema aparece después de optimizar. La propagación de copias, entre otras, convierte SSA convencional en no convencional, y entonces hay que insertar copias para volver atrás.

La forma más simple —aunque no la más eficiente— de destruir SSA no convencional consiste en dividir todas las aristas críticas y después reemplazar las φ por copias al final de los bloques predecesores. Una arista crítica (critical edge) es una arista que va de un nodo con varios sucesores a un nodo con varios predecesores; dividirla consiste en sustituir (b₁, b₂) por una arista de b₁ a un bloque nuevo y otra de ese bloque a b₂.

Como las φ tienen semántica paralela, lo mismo debe valer para las copias correspondientes. Para eso se crea una pseudo-instrucción llamada copia paralela (parallel copy), que representa un conjunto de copias que deben ejecutarse simultáneamente:

foreach B : bloque basico del CFG do
    sean (E1, ..., En) las aristas de entrada de B
    foreach Ei = (Bi, B) do
        sea PCi una copia paralela vacia
        if Bi tiene varias aristas de salida then
            crear bloque fresco vacio Bi'
            reemplazar la arista Ei por Bi -> Bi' y Bi' -> B
            insertar PCi en Bi'
        else
            anadir PCi al final de Bi
    foreach phi a la entrada de B, de la forma a0 = phi(B1: a1, ..., Bn: an) do
        foreach ai (argumento correspondiente a Bi) do
            sea ai' una variable fresca
            anadir la copia  ai' <- ai  a PCi
            reemplazar ai por ai' en la phi

Este algoritmo hace convencional una SSA que no lo era. Eliminando la creación de las variables frescas y añadiendo la eliminación de la φ se obtiene directamente un algoritmo de destrucción.

Tiene, sin embargo, varios inconvenientes serios. Primero, por restricciones arquitectónicas, fronteras de región o código de manejo de excepciones, el compilador puede no tener permitido dividir una arista dada. Segundo, el código resultante contiene muchísimas copias temporal-a-temporal. En teoría, reducir su frecuencia es tarea del coalescing durante la asignación de registros; también puede hacerse antes, con menos esfuerzo, en forma de coalescing agresivo que no se preocupa por la colorabilidad del grafo de interferencia. El capítulo «23» trata ambas cosas.

13.7 Secuencializar copias paralelas

Una vez reemplazadas las φ por copias paralelas, hay que secuencializarlas: convertirlas en una sucesión de copias simples. Esta fase puede hacerse justo después de la destrucción o mucho más tarde, incluso después de la asignación de registros.

Conviene posponerla, porque introduce interferencias arbitrarias. Por ejemplo, a₁ ← a₂ ‖ b₁ ← b₂ —donde ‖ indica ejecución simultánea— puede secuencializarse como a₁ ← a₂ ; b₁ ← b₂, lo que hace que b₂ interfiera con a₁; o al revés, b₁ ← b₂ ; a₁ ← a₂, lo que hace que a₂ interfiera con b₁. La elección importa.

El algoritmo:

sea pcopy la copia paralela a secuencializar
sea seq = () la secuencia de copias resultante
while not (para toda (b <- a) en pcopy se cumple a = b) do
    if existe (b <- a) en pcopy tal que no existe (c <- b) en pcopy then
        // b no es live-in de pcopy: se puede escribir ya
        anadir  b <- a  a seq
        eliminar  b <- a  de pcopy
    else
        // pcopy consta solo de ciclos: hay que romper uno
        sea (b <- a) en pcopy con a != b
        sea a' una variable fresca
        anadir  a' <- a  a seq
        reemplazar en pcopy  b <- a  por  b <- a'

Para ver que converge, conviene visualizar la copia paralela como un grafo cuyos nodos son recursos y cuyas aristas representan transferencias de valor: el número de pasos es exactamente el número de ciclos más el número de aristas que no son bucles propios. La corrección se sigue de la invarianza del comportamiento de seq; pcopy.

13.8 En binarios

13.9 Lecturas

Las referencias clásicas sobre el problema de la copia perdida y el del intercambio son Briggs, Cooper, Harvey y Simpson (1998).

Los algoritmos avanzados de construcción se tratan en el capítulo «14»; la destrucción a nivel de código máquina, con aristas no divisibles y coalescing agresivo, en el capítulo «23».