Formulario estático de asignación única

En el diseño de compiladores , la forma de asignación única estática (a menudo abreviada como forma SSA o simplemente SSA ) es un tipo de representación intermedia (IR) donde cada variable se asigna exactamente una vez. SSA se utiliza en la mayoría de los compiladores de optimización de alta calidad para lenguajes imperativos, incluidos LLVM , GNU Compiler Collection y muchos compiladores comerciales.

Existen algoritmos eficientes para convertir programas al formato SSA. Para convertirlos al formato SSA, las variables existentes en el IR original se dividen en versiones; las nuevas variables suelen indicarse con el nombre original con un subíndice, de modo que cada definición tenga su propia versión. También puede ser necesario introducir instrucciones adicionales que asignen nuevas versiones de variables en el punto de unión de dos rutas de flujo de control. La conversión del formato SSA al código de máquina también es eficiente.

SSA facilita la realización de numerosos análisis necesarios para las optimizaciones, como la determinación de cadenas de uso y definición , porque al observar el uso de una variable solo hay un lugar donde esa variable puede haber recibido un valor. La mayoría de las optimizaciones se pueden adaptar para conservar la forma SSA, de modo que se pueda realizar una optimización después de otra sin análisis adicionales. Las optimizaciones basadas en SSA suelen ser más eficientes y más potentes que sus equivalentes anteriores que no están basadas en SSA.

En los compiladores de lenguajes funcionales , como los de Scheme y ML , se utiliza generalmente el estilo de paso de continuación (CPS). SSA es formalmente equivalente a un subconjunto de CPS con buen comportamiento que excluye el flujo de control no local, por lo que las optimizaciones y transformaciones formuladas en términos de uno generalmente se aplican al otro. El uso de CPS como representación intermedia es más natural para funciones de orden superior y análisis interprocedimental. CPS también codifica fácilmente call/cc , mientras que SSA no lo hace. ^[1]

SSA fue desarrollado en la década de 1980 por varios investigadores de IBM . Kenneth Zadeck, un miembro clave del equipo, se trasladó a la Universidad Brown mientras continuaba el desarrollo. ^{[2] [3]} Un artículo de 1986 introdujo puntos de nacimiento, asignaciones de identidad y cambio de nombre de variables de modo que las variables tuvieran una única asignación estática. ^[4] Un artículo posterior de 1987 de Jeanne Ferrante y Ronald Citron ^[5] demostró que el cambio de nombre realizado en el artículo anterior elimina todas las dependencias falsas para los escalares. ^[3] En 1988, Barry Rosen, Mark N. Wegman y Kenneth Zadeck reemplazaron las asignaciones de identidad con funciones Φ, introdujeron el nombre "forma de asignación única estática" y demostraron una optimización SSA ahora común. ^[6] El nombre Φ-función fue elegido por Rosen para ser una versión más publicable de "función falsa". ^[3] Alpern, Wegman y Zadeck presentaron otra optimización, pero utilizando el nombre "asignación única estática". ^[7] Finalmente, en 1989, Rosen, Wegman, Zadeck, Cytron y Ferrante encontraron un medio eficiente para convertir programas al formato SSA. ^[8]

La principal utilidad 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 yque se utiliza 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 formato SSA, ambos son inmediatos:

y 1  := 1
y 2  := 2
x1 :  = y2

Los algoritmos de optimización del compilador que se habilitan o mejoran considerablemente mediante el uso de SSA incluyen:

• Propagación constante : conversión de cálculos desde el 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 del rango de valores ^[9] : calcula previamente los rangos potenciales que podría tener un cálculo, lo que permite la creación de predicciones de ramificación por adelantado
• Propagación constante condicional dispersa : verificación del 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 : reemplaza los cálculos duplicados que producen el mismo resultado
• Eliminación de redundancia parcial : eliminación de cálculos duplicados realizados previamente en algunas ramas del programa
• Reducción de fuerza : reemplazar operaciones costosas por otras menos costosas pero equivalentes, por ejemplo, reemplazar la multiplicación o división de números enteros por potencias de 2 con el potencialmente menos costoso desplazamiento a la izquierda (para multiplicar) o desplazamiento a 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

La conversión de código ordinario al 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 del 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 ₁ y x ₂ , cada una de las cuales se asigna solo una vez. De la misma manera, dar subíndices distintivos a todas las demás variables da como resultado: ${\displaystyle \flecha izquierda}$

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 ₁ o a y ₂ , dependiendo del camino 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 ₃ "eligiendo" y ₁ o y ₂ , según el flujo de control en el pasado.

Ahora, el último bloque puede simplemente usar y ₃ , y se obtendrá el valor correcto de cualquier manera. No se necesita una función Φ para x : solo una versión de x , a saber x _{2 ,} llega a este punto, por lo que no hay problema (en otras palabras, Φ( x ₂ , x ₂ )= x ₂ ).

Dado un gráfico de flujo de control arbitrario, puede resultar difícil determinar 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 de "movimiento" al final de cada bloque predecesor. En el ejemplo anterior, el compilador podría insertar un movimiento de y ₁ a y ₃ al final del bloque central izquierdo y un movimiento de y ₂ a y ₃ al final del bloque central derecho. Estas operaciones de movimiento podrían no terminar 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 especulativamente entradas para una función Φ, como puede suceder en máquinas de emisión amplia . Por lo general, una máquina de emisión amplia tiene una instrucción de selección utilizada en tales situaciones por el compilador para implementar la función Φ.

En un gráfico de flujo de control, se dice que un nodo A domina estrictamente a un nodo B diferente si es imposible llegar a B sin pasar primero por A. En otras palabras, si se llega al nodo B, se puede suponer que A ha llegado. Se dice que A domina a B (o que B está dominado por A) si A domina estrictamente a B o A = B.

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

La frontera de dominio 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 en los que múltiples rutas de control se fusionan nuevamente en una sola ruta.

Por ejemplo, en el siguiente código:

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

El nodo 1 domina estrictamente al 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 funciones Φ. En el ejemplo anterior, cuando el control se transfiere al nodo 4, la definición de resultutilizado depende de si el control se transfirió desde el nodo 2 o 3. Las funciones Φ no son necesarias para las variables definidas en un dominador, ya que solo hay una definición posible que se puede aplicar.

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" de Ron Cytron, Jeanne Ferrante y otros 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_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)
                dominancia_frontera(corredor) := dominancia_frontera(corredor) ∪ { b }
                corredor := idom(corredor)

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

El SSA "mínimo" inserta la cantidad mínima de funciones Φ necesarias para garantizar que a cada nombre se le asigne un valor exactamente una vez y que cada referencia (uso) de un nombre en el programa original pueda seguir haciendo referencia a un nombre único. (Este ú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 inactivas . Por este motivo, el SSA mínimo no necesariamente produce la menor cantidad de funciones Φ que necesita un procedimiento específico. Para algunos tipos de análisis, estas funciones Φ son superfluas y pueden hacer que el análisis se ejecute con menor eficiencia.

La forma SSA podada se basa en una observación simple: las funciones Φ solo son necesarias para las variables que están "activas" después de la función Φ. (Aquí, "activa" significa que el valor se utiliza a lo largo de alguna 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 por parte de la función Φ está inactiva.

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 Φ, la función Φ no se inserta.

Otra posibilidad es tratar la poda como un problema de eliminación de código muerto . 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 formato SSA, cada uso se reescribe en 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 la cantidad de funciones Φ sin incurrir en el costo relativamente alto de calcular información de variables vivas. Se basa en la siguiente observación: si una variable nunca está viva al ingresar a un bloque básico, nunca necesita una función Φ. Durante la construcción de SSA, se omiten las funciones Φ para cualquier variable "local del 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 vivas, lo que hace que la forma SSA semipodada sea más eficiente de calcular que la forma SSA podada. Por otro lado, la forma SSA semipodada contendrá más funciones Φ.

Los argumentos de bloque son una alternativa a las funciones Φ que es representativamente idéntica pero en la práctica puede ser más conveniente durante la optimización. Los bloques se nombran y toman una lista de argumentos de bloque, anotados como parámetros de función. Cuando se llama a un bloque, los argumentos de bloque se vinculan a valores específicos. Swift SIL y MLIR usan argumentos de bloque. ^[13]

La forma SSA no se utiliza normalmente para la ejecución directa (aunque es posible interpretar SSA ^[14] ), y se utiliza con frecuencia "encima" de otro IR con el que permanece en correspondencia directa. Esto se puede lograr "construyendo" SSA como un conjunto de funciones que se asignan entre partes del IR existente (bloques básicos, instrucciones, operandos, etc. ) y su contraparte SSA. Cuando la forma SSA ya no se necesita, estas funciones de asignación se pueden descartar, dejando solo el IR ahora optimizado.

La realización de optimizaciones en la forma SSA generalmente conduce a redes SSA enredadas, lo que significa que hay instrucciones Φ cuyos operandos no tienen todos el mismo operando raíz. En tales casos, se utilizan algoritmos de coloración para salir de SSA. Los algoritmos ingenuos introducen una copia a lo largo de cada ruta predecesora que provocó que se colocara en Φ una fuente de símbolo raíz diferente al destino de Φ. Hay múltiples algoritmos para salir de SSA con menos copias, la mayoría utiliza gráficos de interferencia o alguna aproximación de ellos para hacer la coalescencia de copias. ^[15]

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

Las extensiones del esquema de cambio de nombre modifican el criterio de cambio de nombre. Recordemos que la forma SSA cambia el nombre de cada variable cuando se le asigna un valor. Los esquemas alternativos incluyen la forma estática de uso único (que cambia el nombre de cada variable en cada enunciado cuando se utiliza) 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 posterior a la dominancia).

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

• 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]}
• Erlang reescribió su compilador en OTP 22.0 para "utilizar internamente una representación intermedia basada en Asignación Única Estática (SSA)", con planes para futuras optimizaciones basadas en SSA en futuras versiones. ^[20]
• La infraestructura del compilador LLVM utiliza el formato SSA para todos los valores de registros escalares (todos excepto la memoria) en su representación de código principal. El formato SSA solo se elimina una vez que se produce la asignación de registros, en una etapa avanzada del proceso de compilación (generalmente en el momento del enlace).
• La Colección de compiladores GNU (GCC) hace un uso extensivo de SSA desde la versión 4 (publicada en abril de 2005). Los frontends generan código " GENERIC " que luego es convertido en código " GIMPLE " por el "gimplificador". Luego se aplican optimizaciones de alto nivel sobre la forma SSA de "GIMPLE". El código intermedio optimizado resultante se traduce luego a RTL , sobre el cual se aplican optimizaciones de bajo nivel. Los backends específicos de la arquitectura finalmente 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 Extended Array SSA, 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 está habilitado en el nivel de optimización máximo, que se aplica a las partes de código que se ejecutan con más 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 compilador Crankshaft como se anunció en diciembre de 2010
• PyPy utiliza una representación SSA lineal para los seguimientos en su compilador JIT.
• La máquina virtual Dalvik de Android utiliza SSA en su compilador JIT.
• El nuevo compilador de optimización de Android para Android Runtime utiliza SSA para su IR. ^[24]
• El compilador ML estándar MLton utiliza SSA en uno de sus lenguajes intermedios.
• LuaJIT hace un uso intensivo de optimizaciones basadas en SSA. ^[25]
• El compilador PHP y Hack HHVM utiliza SSA en su IR. ^[26]
• libFirm, una biblioteca para usar como extremo intermedio y posterior de un compilador , utiliza el formato SSA para todos los valores de registros escalares hasta la generación de código mediante el uso de un asignador de registros compatible con SSA. ^[27]
• Varios controladores Mesa a través de NIR, una representación SSA para lenguajes de sombreado. ^[28]

• La máquina virtual Java HotSpot de Oracle utiliza un lenguaje intermedio basado en SSA en su compilador JIT. ^[29]
• El backend del compilador de Microsoft Visual C++ disponible en Microsoft Visual Studio 2015 Update 3 utiliza SSA ^[30]
• 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. ^[31]
• La familia de compiladores XL de IBM, que incluye C, C++ y Fortran. ^[32]
• NVIDIA CUDA ^[33]

• El compilador ETH Oberon-2 fue uno de los primeros proyectos públicos en incorporar "GSA", una variante de SSA.
• El compilador Open64 utilizó el formato SSA en su optimizador escalar global, aunque el código se convierte en formato SSA antes y se saca de él después. Open64 utiliza extensiones del formato SSA para representar la memoria en formato SSA y también los valores escalares.
• En 2002, los investigadores modificaron JikesRVM de IBM (llamado Jalapeño en ese momento) para ejecutar tanto el código de bytes estándar de Java como archivos de clase de código de bytes SSA de tipos seguros ( SafeTSA ), y demostraron importantes beneficios de rendimiento al utilizar 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 llamada instrucción 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 1994 ^[34] utilizó 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 utiliza esa variable; esencialmente, el formato de información estática única mencionado anteriormente. El formato SSU está documentado 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 que no son SSA (lista cuádruple), SSA y SSI (información única estática ^{[35] ). [36]}
• Aunque no es un compilador, el descompilador Boomerang utiliza el formato 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 conservación y más.
• DotGNU Portable.NET utilizó 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.S2CID63274602  .​{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )
• Appel, Andrew W. (1999). Implementación de compiladores modernos en aprendizaje automático . Cambridge University Press. ISBN 978-0-521-58274-2.También disponible en versiones Java ( ISBN 0-521-82060-X , 2002) y C ( ISBN 0-521-60765-5 , 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 de compiladores avanzados . Morgan Kaufmann. ISBN 978-1-55860-320-2.
• Kelsey, Richard A. (marzo de 1995). "Correspondencia entre el estilo de aprobación continua y la forma estática de asignación única". 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 de GCC" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )
• 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, págs. 102–122, doi : 10.1007/978-3-642-37051-9_6 , ISBN 978-3-642-37050-2, consultado el 24 de marzo de 2013

• Bosscher, Steven; y Novillo, Diego. GCC obtiene un nuevo marco de optimización. Un artículo sobre el uso de SSA por parte de GCC y cómo mejora con respecto a los IR anteriores.
• Bibliografía de la SSA. Amplio catálogo de artículos de investigación de la SSA.
• Zadeck, F. Kenneth. "El desarrollo del formulario de asignación única estática", charla de diciembre de 2007 sobre los orígenes de la SSA.