Formulario estático de asignación única

En un grafo de flujo de control, se dice que un nodo A domina estrictamente a otro nodo B si es imposible llegar a B sin pasar primero por A. En otras palabras, si se llega al nodo B, se puede asumir que A se ha ejecutado. Se dice que A domina a B (o que B es dominado por A) si A domina estrictamente a B o si A = B.

Un nodo que transfiere el control a un nodo A se denomina predecesor inmediato de A.

La frontera de dominancia del nodo A es el conjunto de nodos B donde A no domina estrictamente a B, pero sí domina a algún predecesor inmediato de B. Estos son los puntos donde múltiples rutas de control se fusionan en una sola ruta.

Por ejemplo, en el siguiente código:

[1] x = aleatorio() si x < 0,5 [2] resultado = "caras" demás [3] resultado = "colas" fin [4] imprimir(resultado) 

El nodo 1 domina estrictamente a los nodos 2, 3 y 4, y los predecesores inmediatos del nodo 4 son los nodos 2 y 3.

Las fronteras de dominancia definen los puntos en los que se necesitan las funciones Φ. En el ejemplo anterior, cuando el control se transfiere al nodo 4, la definición resultutilizada depende de si el control se transfirió desde el nodo 2 o el 3. Las funciones Φ no son necesarias para las variables definidas en un dominador, ya que solo existe una definición posible.

Existe un algoritmo eficiente para encontrar las fronteras de dominancia de cada nodo. Este algoritmo fue descrito originalmente en "Efficiently Computing Static Single Assignment Form and the Control Graph" por Ron Cytron, Jeanne Ferrante, et al. en 1991. ^{[ 10 ]}

Keith D. Cooper, Timothy J. Harvey y Ken Kennedy de la Universidad Rice describen un algoritmo en su artículo titulado Un algoritmo de dominancia simple y rápido : ^{[ 11 ]}

para cada nodo b frontera_de_dominancia(b) := {} para cada nodo b si el número de predecesores inmediatos de b ≥ 2 para cada p en los predecesores inmediatos de b corredor := p mientras corredor ≠ idom(b) frontera_de_dominancia(corredor) := frontera_de_dominancia(corredor) ∪ { b } corredor := idom(corredor)

En el código anterior, idom(b)es el dominador inmediato de b, el nodo único que domina estrictamente a b pero no domina estrictamente a ningún otro nodo que domine estrictamente a b.

La forma SSA simplificada se basa en una observación simple: las funciones Φ solo son necesarias para las variables que permanecen activas después de su aplicación. (Aquí, "activa" significa que el valor se utiliza 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 utilizar y la asignación realizada por dicha función queda anulada.

La construcción de la forma SSA podada utiliza información de variables activas en la fase de inserción de la función Φ para decidir si se necesita una función Φ determinada. Si el nombre de la variable original no está activo en el punto de inserción de la función Φ, esta no se inserta.

Otra posibilidad es tratar la poda como un problema de eliminación de código muerto . En ese caso, una función Φ solo se considera activa si algún uso en el programa de entrada se reescribe a ella, o si se utiliza como argumento en otra función Φ. Al entrar en la forma SSA, cada uso se reescribe a la definición más cercana que lo domina. Una función Φ se considerará activa siempre que sea la definición más cercana que domine al menos un uso, o al menos un argumento de una función Φ activa.

La forma SSA semi-podada ^{[ 12 ]} es un intento de reducir el número de funciones Φ sin incurrir en el costo relativamente alto de calcular información sobre variables activas. Se basa en la siguiente observación: si una variable nunca está activa 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 sencillo y rápido que el análisis completo de variables en tiempo real, lo que hace que la forma SSA semi-podada sea más eficiente de calcular que la forma SSA podada. Por otro lado, la forma SSA semi-podada contendrá más funciones Φ.

Los argumentos de bloque son una alternativa a las funciones Φ que es idéntica en representación, pero en la práctica puede ser más conveniente durante la optimización. Los bloques tienen nombre y toman una lista de argumentos de bloque, anotados como parámetros de función. Al llamar a un bloque, los argumentos de bloque se vinculan a valores específicos. MLton , Swift SIL y MLIR usan argumentos de bloque. ^{[ 13 ]} Los argumentos de bloque hacen más evidente la conexión con el estilo de paso de continuaciones (CPS): los bloques básicos son funciones, las variables de función son argumentos de bloque (funciones Φ).

• Mono utiliza SSA en su compilador JIT llamado Mini.
• WebKit utiliza SSA en sus compiladores JIT. ^{[ 16 ] [ 17 ]}
• Swift define su propia forma SSA por encima de LLVM IR, llamada SIL (Swift Intermediate Language). ^{[ 18 ] [ 19 ]}
• El compilador de Erlang fue reescrito en OTP 22.0 para "utilizar internamente una representación intermedia basada en Asignación Única Estática (SSA)", con planes para optimizaciones adicionales basadas en SSA en futuras versiones. ^{[ 20 ]}
• La infraestructura del compilador LLVM utiliza la notación SSA para todos los valores de registro escalares (excepto la memoria) en su representación de código principal. La notación SSA solo se elimina una vez que se produce la asignación de registros, al final del proceso de compilación (a menudo en tiempo de enlace).
• La colección de compiladores GNU (GCC) utiliza ampliamente SSA desde la versión 4 (lanzada en abril de 2005). Los frontends generan código " GENERIC " que luego se convierte en código " GIMPLE " mediante el "gimplifier". Posteriormente, se aplican optimizaciones de alto nivel a la forma SSA de "GIMPLE". El código intermedio optimizado resultante se traduce a RTL , sobre el cual se aplican optimizaciones de bajo nivel. Finalmente, los backends específicos de la arquitectura convierten RTL en lenguaje ensamblador .
• Go (1.7: solo para arquitectura x86-64 ; 1.8: para todas las arquitecturas compatibles). ^{[ 21 ] [ 22 ]}
• La máquina virtual Java adaptativa de código abierto de IBM , Jikes RVM , utiliza SSA de matrices extendidas, una extensión de SSA que permite el análisis de escalares, matrices y campos de objetos en un marco unificado. El análisis de SSA de matrices extendidas solo se habilita en el nivel máximo de optimización, que se aplica a las partes del código que se ejecutan con mayor frecuencia.
• El motor JavaScript SpiderMonkey de Mozilla Firefox utiliza IR basado en SSA. ^{[ 23 ]}
• El motor JavaScript Chromium V8 implementa SSA en su infraestructura de compilación Crankshaft, tal como se anunció en diciembre de 2010.
• PyPy utiliza una representación SSA lineal para las trazas en su compilador JIT.
• El entorno de ejecución de Android ^{[ 24 ]} y la máquina virtual Dalvik utilizan SSA. ^{[ 25 ]}
• El compilador ML estándar MLton utiliza SSA en uno de sus lenguajes intermedios.
• LuaJIT hace un uso intensivo de optimizaciones basadas en SSA. ^{[ 26 ]}
• El compilador PHP y Hack HHVM utiliza SSA en su IR. ^{[ 27 ]}
• El compilador de OCaml utiliza SSA en su CMM IR (que significa C--). ^{[ 28 ]}
• libFirm, una biblioteca para usar como el backend y el middleend de un compilador , usa la forma SSA para todos los valores de registro escalares hasta la generación de código mediante el uso de un asignador de registros compatible con SSA. ^{[ 29 ]}
• Varios controladores Mesa a través de NIR, una representación SSA para lenguajes de sombreado. ^{[ 30 ]}

• La máquina virtual Java HotSpot de Oracle utiliza un lenguaje intermedio basado en SSA en su compilador JIT. ^{[ 31 ]}
• El backend del compilador de Microsoft Visual C++ disponible en Microsoft Visual Studio 2015 Update 3 utiliza SSA ^{[ 32 ]}
• SPIR-V , el estándar de lenguaje de sombreado para la API gráfica Vulkan y lenguaje de kernel para la API de cómputo OpenCL , es una representación SSA. ^{[ 33 ]}
• DXIL , el lenguaje de sombreado para el compilador de sombreadores de Microsoft DirectX, utiliza la representación SSA debido a que es una bifurcación de LLVM. ^{[ 34 ]}
• La familia de compiladores XL de IBM, que incluye C, C++ y Fortran . ^{[ 35 ]}
• NVIDIA CUDA ^{[ 36 ]}

• El compilador ETH Oberon-2 fue uno de los primeros proyectos públicos en incorporar "GSA", una variante de SSA.
• El compilador Open64 utiliza el formato SSA en su optimizador escalar global, aunque el código se convierte a formato SSA antes y se vuelve a convertir a formato SSA después. Open64 utiliza extensiones del formato SSA para representar la memoria en formato SSA, así como los valores escalares.
• En 2002, los investigadores modificaron JikesRVM de IBM (llamado Jalapeño en aquel entonces) para ejecutar tanto código de bytes Java estándar como archivos de clase de código de bytes SSA ( SafeTSA ) con tipado seguro, y demostraron importantes ventajas de rendimiento al usar el código de bytes SSA.
• jackcc es un compilador de código abierto para el conjunto de instrucciones académicas 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 una instrucción denominada SAME, que indica al asignador de registros que coloque los dos rangos activos en el mismo registro físico.
• El compilador de conciertos de Illinois de alrededor de 1994 ^{[ 37 ]} utilizaba una variante de SSA llamada SSU (Static Single Use) que renombra cada variable cuando se le asigna un valor y en cada contexto condicional en el que se utiliza esa variable; esencialmente la forma estática de información única mencionada anteriormente. La forma SSU está documentada en la tesis doctoral de John Plevyak .
• El compilador COINS utiliza optimizaciones de formato SSA como se explica aquí .
• El compilador R-Stream de Reservoir Labs admite formatos no SSA (lista cuádruple), SSA y SSI (Información Única Estática ^{[ 38 ]} ). ^{[ 39 ]}
• Aunque no es un compilador, el descompilador Boomerang utiliza la notación SSA en su representación interna. SSA se utiliza para simplificar la propagación de expresiones, la identificación de parámetros y valores de retorno, el análisis de preservación y mucho más.
• DotGNU Portable.NET utilizaba SSA en su compilador JIT.

• Rastello, Fabrice; Tichadou, Florent Bouchez, eds. (2022). Diseño de compilador basado en SSA (PDF) . Cham. doi : 10.1007/978-3-030-80515-9 . ISBN 978-3-030-80515-9. S2CID 63274602 . {{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
• Appel, Andrew W. (1999). Modern Compiler Implementation in ML . Cambridge University Press. ISBN 978-0-521-58274-2.También disponible en Java ( ISBN) 0-521-82060-X, 2002) y C ( ISBN 0-521-60765-5versiones de 1998.
• 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 avanzados de compiladores . 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 la forma de asignación única estática" . ACM SIGPLAN Notices . 30 (3): 13– 22. doi : 10.1145/202530.202532 .
• Appel, Andrew W. (abril de 1998). "SSA es programación funcional" . ACM SIGPLAN Notices . 33 (4): 17– 20. doi : 10.1145/278283.278285 . S2CID 207227209 . 
• Pop, Sebastian (2006). El marco de representación SSA: semántica, análisis e implementación GCC (tesis doctoral). École des Mines de Paris .
• Matthias Braun; Sebastian Buchwald; Sebastian Hack; Roland Leißa; Christoph Mallon; Andreas Zwinkau (2013), "Construcción simple y eficiente de la forma de asignación única estática" , Compiler Construction , Lecture Notes in Computer Science, vol.  7791, Springer Berlin Heidelberg, pp. 102–122 , doi : 10.1007/978-3-642-37051-9_6 , ISBN  978-3-642-37050-2Consultado el 24 de marzo de 2013.