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. [1] Ron Cytron , Jeanne Ferrante y los tres investigadores anteriores de IBM desarrollaron un algoritmo que puede calcular la forma SSA de manera eficiente. [2]
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. [3] 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: = 1y: = 2x: = y
Los seres 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:
y 1 : = 1y 2 : = 2x 1 : = y 2
Los algoritmos de optimización del compilador que están habilitados o fuertemente mejorados por el uso de SSA incluyen:
- Propagación constante : conversión de cálculos del tiempo de ejecución al tiempo de compilación, por ejemplo, tratar la instrucción
a=3*4+5;
como si fueraa=17;
- Propagación de rango de valor [4] : calcule previamente los rangos potenciales que podría ser un cálculo, lo que permite la creación de predicciones de rama por adelantado.
- Propagación constante condicional dispersa : verifique el rango de algunos valores, lo que permite que las pruebas predigan la rama más probable
- Eliminación de código muerto : elimine el código que no tendrá ningún efecto en los resultados
- Numeración de valores globales : reemplace los cálculos duplicados que producen el mismo resultado
- Eliminación de redundancia parcial : eliminación de cálculos duplicados realizados anteriormente en algunas ramas del programa
- Reducción de fuerza : reemplazar operaciones costosas por otras menos costosas pero equivalentes, por ejemplo, reemplazar la multiplicación entera o dividir por potencias de 2 con el desplazamiento potencialmente menos costoso hacia la izquierda (para multiplicar) o hacia la derecha (para dividir).
- Asignación de registros : optimice la forma en que se puede utilizar el número limitado de registros de la máquina para los cálculos.
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 :
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 explotar en SSA creando dos nuevas variables: x 1 y x 2 , cada una de las cuales se asigna solo una vez. distinguir subíndices de todas las demás variables produce:
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.
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, [5] Φ 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. [6]
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 . [7] El algoritmo utiliza estructuras de datos bien diseñadas para mejorar el rendimiento. Se expresa simplemente de la siguiente manera: [7]
para cada nodo b frontera_de_dominio (b): = {}para cada nodo b si el número de predecesores inmediatos de b ≥ 2 para cada p en predecesores inmediatos de b corredor: = p mientras corredor ≠ idom (b) dominance_frontier (corredor): = dominance_frontier (corredor) ∪ {b} corredor: = idom (corredor)
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 cualquier uso en el programa de entrada se reescribirá en ella, 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á viva siempre que sea la definición más cercana que domine al menos un uso, o al menos un argumento de una Φ viva.
SSA semi-podado
El formulario SSA semi-podado [8] es un intento de reducir el número de funciones Φ sin incurrir en el costo relativamente alto de calcular 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 de variables en vivo completo, 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 [9] ), y se usa frecuentemente "encima" de otro IR con el que permanece en correspondencia directa. Esto se puede lograr "construyendo" SSA como un conjunto de funciones que mapean 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. [10]
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 características específicas modelan características 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. Algunos 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 mayor 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. [11]
- El backend del compilador de Microsoft Visual C ++ disponible en Microsoft Visual Studio 2015 Update 3 usa SSA [12]
- 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 [13] 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. [14]
- 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. [15]
- El compilador PHP y Hack HHVM usa SSA en su IR. [dieciséis]
- El compilador R-Stream de Reservoir Labs admite formularios que no son SSA (lista cuádruple), SSA y SSI (Información única estática [17] ). [18]
- Go (1.7: solo para arquitectura x86-64; 1.8: para todas las arquitecturas compatibles). [19] [20]
- SPIR-V , el estándar de lenguaje de sombreado para la API de gráficos Vulkan y el lenguaje del kernel para la API de cómputo OpenCL , es una representación SSA. [21]
- Varios controladores de Mesa a través de NIR, una representación SSA para los idiomas de sombreado. [22]
- WebKit usa SSA en sus compiladores JIT. [23] [24]
- Swift define su propio formulario SSA por encima de LLVM IR, llamado SIL (Swift Intermediate Language). [25] [26]
- 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. [27]
Referencias
Notas
- ^ Barry Rosen; Mark N. Wegman; F. Kenneth Zadeck (1988). "Números de valor global y cálculos redundantes" (PDF) . Actas del 15º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación .
- ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K .; Wegman, Mark N. y Zadeck, F. Kenneth (1991). "Cálculo eficiente del formulario de asignación única estática y el gráfico de dependencia de control" (PDF) . Transacciones ACM sobre lenguajes y sistemas de programación . 13 (4): 451–490. CiteSeerX 10.1.1.100.6361 . doi : 10.1145 / 115372.115320 . S2CID 13243943 .
- ^ Kelsey, Richard A. (1995). "Una correspondencia entre el estilo de aprobación de continuación y el formulario de asignación única estática" (PDF) . Artículos del taller de 1995 ACM SIGPLAN sobre representaciones intermedias : 13–22. doi : 10.1145 / 202529.202532 . ISBN 0897917545. S2CID 6207179 .
- ^ propagación del rango de valores
- ^ ver página 43 ["El origen de las funciones Ф y el nombre"] de Zadeck, F. Kenneth, Presentación sobre la historia de SSA en el Seminario SSA'09 , Autrans, Francia, abril de 2009
- ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K .; Wegman, Mark N .; Zadeck, F. Kenneth (1 de octubre de 1991). "Cálculo eficiente de la forma de asignación única estática y el gráfico de dependencia de control". Transacciones ACM sobre lenguajes y sistemas de programación . 13 (4): 451–490. doi : 10.1145 / 115372.115320 . S2CID 13243943 .
- ^ a b Cooper, Keith D .; Harvey, Timothy J .; Kennedy, Ken (2001). "Un algoritmo de dominancia simple y rápido" (PDF) . Cite journal requiere
|journal=
( ayuda ) - ^ Briggs, Preston; Cooper, Keith D .; Harvey, Timothy J .; Simpson, L. Taylor (1998). "Mejoras prácticas en la construcción y destrucción del formulario de asignación única estática" (PDF) . Archivado desde el original (PDF) el 7 de junio de 2010. Cite journal requiere
|journal=
( ayuda ) - ^ von Ronne, Jeffery; Ning Wang; Michael Franz (2004). "Interpretación de programas en forma estática de asignación única" . Cite journal requiere
|journal=
( ayuda ) - ^ Boissinot, Benoit; Darte, Alain; Rastello, Fabrice; Dinechin, Benoît Dupont de; Guillon, Christophe (2008). "Revisando la traducción fuera de SSA para la corrección, la calidad del código y la eficiencia" . HAL-Inria Cs.DS : 14.
- ^ "La arquitectura del motor de rendimiento de Java HotSpot" . Oracle Corporation.
- ^ "Presentamos un nuevo y avanzado optimizador de código de Visual C ++" .
- ^ "Proyecto de conciertos de Illinois" .
- ^ "Descripción general de IonMonkey" .,
- ^ "Optimizaciones de Bytecode" . el proyecto LuaJIT.
- ^ "Representación intermedia de HipHop (HHIR)" .
- ^ Ananian, C. Scott; Rinard, Martin (1999). "Formulario de información única estática". CiteSeerX 10.1.1.1.9976 . Cite journal requiere
|journal=
( ayuda ) - ^ "Enciclopedia de Computación Paralela" .
- ^ "Notas de la versión Go 1.7 - El lenguaje de programación Go" . golang.org . Consultado el 17 de agosto de 2016 .
- ^ "Notas de la versión Go 1.8 - El lenguaje de programación Go" . golang.org . Consultado el 17 de febrero de 2017 .
- ^ "Especificaciones SPIR-V" (PDF) .
- ^ Ekstrand, Jason. "Reintroduciendo NIR, un nuevo IR para mesa" .
- ^ "Presentación del WebKit FTL JIT" .
- ^ "Presentación del compilador B3 JIT" .
- ^ "Lenguaje intermedio rápido (GitHub)" .
- ^ "IR de alto nivel de Swift: un estudio de caso de complementar LLVM IR con optimización específica del idioma, LLVM Developers Meetup 10/2015" .
- ^ "Notas de la versión OTP 22.0" .
Referencias generales
- Appel, Andrew W. (1999). Implementación del compilador moderno en ML . Prensa de la Universidad de Cambridge. ISBN 978-0-521-58274-2.También disponible en Java ( ISBN 0-521-82060-X , 2002) y C ( ISBN 0-521-60765-5 , 1998) versiones.
- Cooper, Keith D. y Torczon, Linda (2003). Ingeniería de un compilador . Morgan Kaufmann. ISBN 978-1-55860-698-2.
- Muchnick, Steven S. (1997). Diseño e implementación de compiladores avanzados . Morgan Kaufmann. ISBN 978-1-55860-320-2.
- Kelsey, Richard A. (marzo de 1995). "Una correspondencia entre el estilo de paso de continuación y el formulario de asignación única estática". Avisos ACM SIGPLAN . 30 (3): 13-22. doi : 10.1145 / 202530.202532 .
- Appel, Andrew W. (abril de 1998). "SSA es programación funcional". Avisos ACM SIGPLAN . 33 (4): 17-20. doi : 10.1145 / 278283.278285 . S2CID 207227209 .
- Pop, Sebastián (2006). "El marco de representación de la SSA: semántica, análisis e implementación de GCC" (PDF) . Cite journal requiere
|journal=
( ayuda ) - Matthias Braun; Sebastian Buchwald; Sebastian Hack; Roland Leißa; Christoph Mallon; Andreas Zwinkau (2013), "Construcción simple y eficiente de un formulario de asignación única estática" , Construcción del compilador , Notas de conferencia en Ciencias de la Computación, 7791 , Springer Berlin Heidelberg, pp. 102-122, doi : 10.1007 / 978-3-642-37051 -9_6 , ISBN 978-3-642-37050-2, consultado el 24 de marzo de 2013
enlaces externos
- Bosscher, Steven; y Novillo, Diego. GCC obtiene un nuevo Optimizer Framework . Un artículo sobre el uso de SSA por parte de GCC y cómo mejora con respecto a los RI más antiguos.
- La bibliografía de la SSA . Amplio catálogo de trabajos de investigación de la SSA.
- Zadeck, F. Kenneth. "El Formulario de Desarrollo de Asignación Única Estática" , diciembre de 2007 charla sobre los orígenes de SSA.
- VV.AA. "Diseño de compilador basado en SSA" (2014)