Formulario estático de asignación única - Static single assignment form

En el diseño del compilador , la forma de asignación única estática (a menudo abreviada como forma SSA o simplemente SSA ) es una propiedad de una representación intermedia (IR), que requiere que cada variable se asigne exactamente una vez y que cada variable se defina antes de que se utilice. Las variables existentes en el IR original se dividen en versiones , las nuevas variables típicamente indicadas por el nombre original con un subíndice en los libros de texto, de modo que cada definición tiene su propia versión. En la forma SSA, las cadenas use-def son explícitas y cada una contiene un solo elemento.

La SSA fue propuesta por Barry K. Rosen , Mark N. Wegman y F. Kenneth Zadeck en 1988. Ron Cytron , Jeanne Ferrante y los tres investigadores anteriores de IBM desarrollaron un algoritmo que puede calcular la forma SSA de manera eficiente.

Se puede esperar encontrar SSA en un compilador para Fortran , C o C ++ , mientras que en los compiladores de lenguaje funcional , como los de Scheme y ML , generalmente se usa el estilo de paso de continuación (CPS). SSA es formalmente equivalente a un subconjunto de CPS de buen comportamiento que excluye el flujo de control no local, lo que no ocurre cuando se utiliza CPS como representación intermedia. Por tanto, las optimizaciones y transformaciones formuladas en términos de una se aplican inmediatamente a la otra.

Beneficios

La utilidad principal de SSA proviene de cómo simplifica y mejora simultáneamente los resultados de una variedad de optimizaciones del compilador , al simplificar las propiedades de las variables. Por ejemplo, considere este fragmento de código: 

y := 1
y := 2
x := y

Los humanos pueden ver que la primera asignación no es necesaria y que el valor de y ser utilizado en la tercera línea proviene de la segunda asignación de y . Un programa tendría que realizar un análisis de definición de alcance para determinar esto. Pero si el programa está en forma SSA, ambos son inmediatos: 

y1 := 1
y2 := 2
x1 := y2

Los algoritmos de optimización del compilador que están habilitados o fuertemente mejorados por el uso de SSA incluyen:

Conversión a SSA

Convertir código ordinario en formato SSA es principalmente una cuestión de reemplazar el objetivo de cada asignación con una nueva variable y reemplazar cada uso de una variable con la "versión" de la variable que llega a ese punto. Por ejemplo, considere el siguiente gráfico de flujo de control :

Un gráfico de flujo de control de ejemplo, antes de la conversión a SSA

Cambiar el nombre en el lado izquierdo de "x x - 3" y cambiar los siguientes usos de x a ese nuevo nombre dejaría el programa inalterado. Esto se puede aprovechar en SSA creando dos nuevas variables: x 1 y x 2 , cada una de las cuales se asigna solo una vez. Asimismo, otorgar subíndices distintivos a todas las demás variables da como resultado:

Un gráfico de flujo de control de ejemplo, parcialmente convertido a SSA

Está claro a qué definición se refiere cada uso, excepto en un caso: ambos usos de y en el bloque inferior podrían referirse a y 1 o y 2 , dependiendo de la ruta que tomó el flujo de control.

Para resolver esto, se inserta una declaración especial en el último bloque, llamada función Φ (Phi) . Esta declaración generará una nueva definición de y llamada y 3 "eligiendo" ya sea y 1 o y 2 , dependiendo del flujo de control en el pasado.

Un ejemplo de gráfico de flujo de control, completamente convertido a SSA

Ahora, el último bloque puede usar simplemente y 3 , y el valor correcto se obtendrá de cualquier manera. No se necesita una función Φ para x : solo una versión de x , es decir, x 2 está llegando a este lugar, por lo que no hay problema (en otras palabras, Φ ( x 1 , x 2 ) = x 2 ).

Dado un gráfico de flujo de control arbitrario, puede ser difícil saber dónde insertar funciones Φ y para qué variables. Esta pregunta general tiene una solución eficiente que se puede calcular utilizando un concepto llamado fronteras de dominancia (ver más abajo).

Φ Las funciones no se implementan como operaciones de máquina en la mayoría de las máquinas. Un compilador puede implementar una función Φ insertando operaciones "mover" al final de cada bloque predecesor. En el ejemplo anterior, el compilador podría insertar un movimiento de y 1 a y 3 al final del bloque del medio a la izquierda y un movimiento de y 2 a y 3 al final del bloque del medio a la derecha. Es posible que estas operaciones de movimiento no terminen en el código final según el procedimiento de asignación de registros del compilador . Sin embargo, este enfoque puede no funcionar cuando las operaciones simultáneas están produciendo entradas especulativamente para una función Φ, como puede suceder en máquinas con problemas amplios . Por lo general, una máquina de problemas generales tiene una instrucción de selección utilizada en tales situaciones por el compilador para implementar la función Φ.

Según Kenny Zadeck, las funciones Φ se conocían originalmente como funciones falsas mientras SSA se estaba desarrollando en IBM Research en la década de 1980. El nombre formal de una función Φ solo se adoptó cuando el trabajo se publicó por primera vez en un artículo académico.

Calcular SSA mínima usando fronteras de dominio

Primero, necesitamos el concepto de dominador : decimos que un nodo A domina estrictamente a un nodo B diferente en el gráfico de flujo de control si es imposible llegar a B sin pasar primero por A. Esto es útil, porque si alguna vez llegamos a B, sabemos que se ha ejecutado cualquier código en A. Decimos que A domina a B (B está dominado por A) si A domina estrictamente a B o A = B.

Ahora podemos definir la frontera de dominio : un nodo B está en la frontera de dominio de un nodo A si A no domina estrictamente a B, pero sí domina a algún predecesor inmediato de B, o si el nodo A es un predecesor inmediato de B, y, dado que cualquier nodo se domina a sí mismo, el nodo A se domina a sí mismo y, como resultado, el nodo A está en la frontera de dominio del nodo B. Desde el punto de vista de A, estos son los nodos en los que otras rutas de control, que no pasan por A, hacen su primera aparición.

Las fronteras de dominancia capturan los lugares precisos en los que necesitamos funciones Φ: si el nodo A define una determinada variable, entonces esa definición y esa definición por sí solas (o redefiniciones) llegarán a cada nodo que A domine. Solo cuando dejamos estos nodos y entramos en la frontera de dominancia, debemos dar cuenta de otros flujos que aportan otras definiciones de la misma variable. Además, no se necesitan otras funciones Φ en el gráfico de flujo de control para tratar con las definiciones de A, y no podemos hacerlo con menos.

Existe un algoritmo eficiente para encontrar las fronteras de dominio de cada nodo. Este algoritmo se describió originalmente en Cytron et al. 1991. También es útil el capítulo 19 del libro "Implementación del compilador moderno en Java" de Andrew Appel (Cambridge University Press, 2002). Consulte el documento para obtener más detalles.

Keith D. Cooper, Timothy J. Harvey y Ken Kennedy de Rice University describen un algoritmo en su artículo titulado A Simple, Fast Dominance Algorithm . El algoritmo utiliza estructuras de datos bien diseñadas para mejorar el rendimiento. Se expresa simplemente de la siguiente manera: 

for each node b
    dominance_frontier(b) := {}
for each node b
    if the number of immediate predecessors of b ≥ 2
        for each p in immediate predecessors of b
            runner := p
            while runner ≠ idom(b)
                dominance_frontier(runner) := dominance_frontier(runner) ∪ { b }
                runner := idom(runner)

Nota: en el código anterior, un predecesor inmediato del nodo n es cualquier nodo desde el cual se transfiere el control al nodo n, e idom (b) es el nodo que domina inmediatamente el nodo b (un conjunto singleton).

Variaciones que reducen el número de funciones Φ

SSA "Mínimo" inserta el número mínimo de funciones Φ requeridas para asegurar que a cada nombre se le asigne un valor exactamente una vez y que cada referencia (uso) de un nombre en el programa original aún pueda referirse a un nombre único. (El último requisito es necesario para garantizar que el compilador pueda escribir un nombre para cada operando en cada operación).

Sin embargo, algunas de estas funciones Φ podrían estar muertas . Por esta razón, la SSA mínima no produce necesariamente la menor cantidad de funciones Φ necesarias para un procedimiento específico. Para algunos tipos de análisis, estas funciones Φ son superfluas y pueden hacer que el análisis se ejecute de manera menos eficiente.

SSA podado

El formulario SSA podado se basa en una simple observación: las funciones Φ solo son necesarias para las variables que están "activas" después de la función Φ. (Aquí, "vivo" significa que el valor se usa a lo largo de una ruta que comienza en la función Φ en cuestión). Si una variable no está activa, el resultado de la función Φ no se puede usar y la asignación de la función Φ está muerta .

La construcción del formulario SSA podado utiliza información variable en vivo en la fase de inserción de la función Φ para decidir si se necesita una función Φ dada. Si el nombre de la variable original no está activo en el punto de inserción de la función Φ, la función Φ no se inserta.

Otra posibilidad es tratar la poda como un problema de eliminación de códigos muertos . Entonces, una función Φ está activa solo si se le reescribirá cualquier uso en el programa de entrada, o si se usará como argumento en otra función Φ. Al ingresar al formulario SSA, cada uso se reescribe a la definición más cercana que lo domina. Entonces, una función Φ se considerará en vivo siempre que sea la definición más cercana que domine al menos un uso, o al menos un argumento de un live vivo.

SSA semi-podado

El formulario SSA semi-podado es un intento de reducir el número de funciones Φ sin incurrir en el costo relativamente alto de computar información variable en vivo. Se basa en la siguiente observación: si una variable nunca está viva al entrar en un bloque básico, nunca necesita una función Φ. Durante la construcción de SSA, se omiten las funciones Φ para cualquier variable "local de bloque".

Calcular el conjunto de variables locales de bloque es un procedimiento más simple y rápido que el análisis completo de variables en vivo, lo que hace que la forma SSA semiportada sea más eficiente de calcular que la forma SSA podada. Por otro lado, el formulario SSA semi-podado contendrá más funciones Φ.

Conversión fuera del formulario SSA

El formulario SSA no se usa normalmente para ejecución directa (aunque es posible interpretar SSA), y con frecuencia se usa "encima" de otro IR con el que permanece en correspondencia directa. Esto se puede lograr "construyendo" SSA como un conjunto de funciones que se correlacionan entre partes del IR existente (bloques básicos, instrucciones, operandos, etc. ) y su contraparte SSA. Cuando ya no se necesita el formulario SSA, estas funciones de mapeo pueden descartarse, dejando solo el IR ahora optimizado.

La realización de optimizaciones en el formulario SSA generalmente conduce a SSA-Web entrelazados, lo que significa que hay instrucciones Φ cuyos operandos no tienen todos el mismo operando raíz. En tales casos , se utilizan algoritmos de eliminación de color para salir de SSA. Los algoritmos ingenuos introducen una copia a lo largo de cada ruta predecesora, lo que provoca que se coloque una fuente de símbolo raíz diferente en Φ que el destino de Φ. Existen múltiples algoritmos para salir de SSA con menos copias, la mayoría usa gráficos de interferencia o alguna aproximación para hacer copias fusionadas.

Extensiones

Las extensiones del formulario SSA se pueden dividir en dos categorías.

Las extensiones del esquema de cambio de nombre alteran el criterio de cambio de nombre. Recuerde que el formulario SSA cambia el nombre de cada variable cuando se le asigna un valor. Los esquemas alternativos incluyen la forma estática de un solo uso (que cambia el nombre de cada variable en cada declaración cuando se usa) y la forma estática de información única (que cambia el nombre de cada variable cuando se le asigna un valor, y en la frontera de posdominio).

Las extensiones específicas de características conservan la propiedad de asignación única para las variables, pero incorporan nueva semántica para modelar características adicionales. Algunas extensiones de funciones específicas modelan funciones de lenguaje de programación de alto nivel como matrices, objetos y punteros con alias. Otras extensiones de características específicas modelan características arquitectónicas de bajo nivel como la especulación y la predicación.

Compiladores que utilizan el formulario SSA

El formulario SSA es un desarrollo relativamente reciente en la comunidad de compiladores. Como tal, muchos compiladores más antiguos solo usan el formulario SSA para alguna parte del proceso de compilación u optimización, pero la mayoría no confía en él. Ejemplos de compiladores que dependen en gran medida de la forma SSA incluyen:

  • El compilador ETH Oberon-2 fue uno de los primeros proyectos públicos en incorporar "GSA", una variante de SSA.
  • La infraestructura del compilador LLVM utiliza el formulario SSA para todos los valores de registro escalar (todo excepto la memoria) en su representación de código principal. El formulario SSA solo se elimina una vez que se realiza la asignación de registros, al final del proceso de compilación (a menudo en el momento del enlace).
  • El compilador de Open64 usa la forma SSA en su optimizador escalar global, aunque el código se lleva a la forma SSA antes y luego se saca de la forma SSA. Open64 usa extensiones de la forma SSA para representar la memoria en forma SSA, así como valores escalares.
  • A partir de la versión 4 (publicada en abril de 2005) GCC, la colección de compiladores GNU , hace un uso extensivo de SSA. Las interfaces generan código " GENÉRICO " que luego se convierte en código " GIMPLE " por el "gimplifier". Las optimizaciones de alto nivel se aplican luego en la forma SSA de "GIMPLE". El código intermedio optimizado resultante se traduce luego a RTL , en el que se aplican optimizaciones de bajo nivel. Los backends específicos de la arquitectura finalmente convierten RTL en lenguaje ensamblador .
  • La máquina virtual Java adaptativa de código abierto de IBM , Jikes RVM , utiliza Array SSA extendido, una extensión de SSA que permite el análisis de escalares, matrices y campos de objetos en un marco unificado. El análisis Extended Array SSA solo se habilita en el nivel de optimización máximo, que se aplica a las partes del código que se ejecutan con más frecuencia.
  • En 2002, investigadores modificaron JikesRVM de IBM (denominado Jalapeño en el momento) para funcionar tanto estándar de Java de código de bytes y un typesafe SSA ( SafeTSA archivos de clase de código de bytes), y demostradas ventajas de rendimiento significativas en el uso de la SSA código de bytes.
  • Oracle 's HotSpot Java Virtual Machine utiliza un lenguaje intermedio basado en SSA en su compilador JIT.
  • El backend del compilador de Microsoft Visual C ++ disponible en Microsoft Visual Studio 2015 Update 3 usa SSA
  • Mono usa SSA en su compilador JIT llamado Mini.
  • jackcc es un compilador de código abierto para el conjunto de instrucción académica Jackal 3.0. Utiliza un código simple de 3 operandos con SSA para su representación intermedia. Como variante interesante, reemplaza las funciones Φ con la llamada instrucción SAME, que indica al asignador de registros que coloque los dos rangos en vivo en el mismo registro físico.
  • Aunque no es un compilador, el descompilador Boomerang usa la forma SSA en su representación interna. SSA se utiliza para simplificar la propagación de expresiones, la identificación de parámetros y retornos, el análisis de preservación y más.
  • Portable.NET usa SSA en su compilador JIT.
  • libFirm una representación intermedia SSA completamente basada en gráficos para compiladores. libFirm usa el formulario SSA para todos los valores de registro escalar hasta la generación de código mediante el uso de un asignador de registro compatible con SSA.
  • El Compilador de Conciertos de Illinois alrededor de 1994 usó una variante de SSA llamada SSU (Static Single Use) que cambia el nombre de cada variable cuando se le asigna un valor y en cada contexto condicional en el que se usa esa variable; esencialmente el formulario de información único estático mencionado anteriormente. El formulario SSU está documentado en la tesis doctoral de John Plevyak .
  • El compilador COINS utiliza optimizaciones de formularios SSA como se explica aquí: http://www.is.titech.ac.jp/~sassa/coins-www-ssa/english/
  • El motor de JavaScript Mozilla Firefox SpiderMonkey utiliza IR basado en SSA.
  • El motor JavaScript Chromium V8 implementa SSA en su infraestructura de compilador Crankshaft como se anunció en diciembre de 2010
  • PyPy usa una representación SSA lineal para las trazas en su compilador JIT.
  • La máquina virtual Dalvik de Android usa SSA en su compilador JIT.
  • Androide nuevo compilador de optimización 's para el tiempo de ejecución de Android utiliza la SSA por su IR.
  • El compilador MLton estándar usa SSA en uno de sus lenguajes intermedios.
  • LuaJIT hace un uso intensivo de optimizaciones basadas en SSA.
  • El compilador PHP y Hack HHVM usa SSA en su IR.
  • El compilador R-Stream de Reservoir Labs admite formularios que no son SSA (lista cuádruple), SSA y SSI (Información única estática).
  • Go (1.7: solo para arquitectura x86-64; 1.8: para todas las arquitecturas compatibles).
  • SPIR-V , el lenguaje de sombreado estándar para la API de gráficos Vulkan y el lenguaje del kernel para la API de cómputo OpenCL , es una representación SSA.
  • Varios controladores de Mesa a través de NIR, una representación SSA para los idiomas de sombreado.
  • WebKit usa SSA en sus compiladores JIT.
  • Swift define su propio formulario SSA por encima de LLVM IR, llamado SIL (Swift Intermediate Language).
  • Erlang reescribió su compilador en OTP 22.0 para "usar internamente una representación intermedia basada en la asignación única estática (SSA)". Con planes para optimizaciones adicionales construidas sobre SSA en versiones futuras.

Referencias

Notas

Referencias generales

enlaces externos