stringtranslate.com

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 es posible que sea 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]

Historia

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]

Beneficios

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 := 1y := 2x := 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  := 1y 2  := 2x1 :  = y2

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

Conversión a SSA

La conversión de código ordinario al formato SSA es básicamente 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 ejemplo de gráfico de flujo de control, antes de la conversión a SSA

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 1 y x 2 , 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:

Un ejemplo de gráfico de flujo de control, 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 a y 2 , 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 3 "eligiendo" y 1 o y 2 , según el flujo de control en el pasado.

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

Ahora, el último bloque puede simplemente usar y 3 , 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 2 , x 2 )= x 2 ).

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 1 a y 3 al final del bloque central izquierdo y un movimiento de y 2 a y 3 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 Φ.

Cálculo del SSA mínimo utilizando fronteras de dominancia

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.

Variaciones que reducen el número de funciones Φ

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.

SSA podado

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.

SSA semipodado

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 Φ.

Argumentos en bloque

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. MLton , Swift SIL y LLVM MLIR usan argumentos de bloque. [13]

Conversión del formulario SSA

La forma SSA no se utiliza normalmente para la ejecución directa (aunque es posible interpretar SSA [14] ), y con frecuencia se utiliza "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]

Extensiones

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.

Compiladores que utilizan el formato SSA

Código abierto

Comercial

Investigación y abandono

Referencias

Notas

  1. ^ Kelsey, Richard A. (1995). "Una correspondencia entre el estilo de paso de continuación y la forma estática de asignación única" (PDF) . Documentos del taller ACM SIGPLAN de 1995 sobre representaciones intermedias . págs. 13–22. doi :10.1145/202529.202532. ISBN 0897917545. Número de identificación del sujeto  6207179.
  2. ^ Rastello y Tichadou 2022, sec. 1.4.
  3. ^ abc Zadeck, Kenneth (abril de 2009). El desarrollo de un formulario estático de asignación única (PDF) . Seminario sobre el formulario estático de asignación única. Autrans, Francia.
  4. ^ Cytron, Ron; Lowry, Andy; Zadeck, F. Kenneth (1986). "Movimiento de código de estructuras de control en lenguajes de alto nivel". Actas del 13.º Simposio ACM SIGACT-SIGPLAN sobre principios de lenguajes de programación - POPL '86 : 70–85. doi :10.1145/512644.512651. S2CID  9099471.
  5. ^ Cytron, Ronald Kaplan; Ferrante, Jeanne. ¿Qué hay en un nombre? O el valor de renombrar para la detección de paralelismo y la asignación de almacenamiento . Conferencia internacional sobre procesamiento paralelo, ICPP'87 1987. págs. 19–27.
  6. ^ 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 .
  7. ^ Alpern, B.; Wegman, MN; Zadeck, FK (1988). "Detección de igualdad de variables en programas". Actas del 15.º simposio ACM SIGPLAN-SIGACT sobre Principios de lenguajes de programación - POPL '88 . págs. 1–11. doi :10.1145/73560.73561. ISBN 0897912527.S2CID18384941  .​
  8. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N. y Zadeck, F. Kenneth (1991). "Computación eficiente de la forma de asignación única estática y el gráfico de dependencia de control" (PDF) . ACM Transactions on Programming Languages ​​and Systems . 13 (4): 451–490. CiteSeerX 10.1.1.100.6361 . doi :10.1145/115372.115320. S2CID  13243943. 
  9. ^ propagación del rango de valores
  10. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; Zadeck, F. Kenneth (1 de octubre de 1991). "Computación eficiente de la forma de asignación única estática y el gráfico de dependencia de control". ACM Transactions on Programming Languages ​​and Systems . 13 (4): 451–490. doi : 10.1145/115372.115320 . S2CID  13243943.
  11. ^ Cooper, Keith D.; Harvey, Timothy J.; Kennedy, Ken (2001). Un algoritmo de dominancia simple y rápido (PDF) (informe técnico). Universidad Rice, Informe técnico CS 06-33870. Archivado desde el original (PDF) el 26 de marzo de 2022.
  12. ^ Briggs, Preston; Cooper, Keith D.; Harvey, Timothy J.; Simpson, L. Taylor (1998). Mejoras prácticas en la construcción y destrucción de formularios estáticos de asignación única (PDF) (informe técnico). Archivado desde el original (PDF) el 7 de junio de 2010.
  13. ^ "Argumentos de bloque frente a nodos PHI: fundamentos de MLIR". mlir.llvm.org . Consultado el 4 de marzo de 2022 .
  14. ^ von Ronne, Jeffery; Ning Wang; Michael Franz (2004). "Interpretación de programas en formato estático de asignación única". Actas del taller de 2004 sobre intérpretes, máquinas virtuales y emuladores - IVME '04. p. 23. doi :10.1145/1059579.1059585. ISBN 1581139098.S2CID 451410  .
  15. ^ Boissinot, Benoit; Darté, Alain; Rastello, Fabrice; Dinechin, Benoît Dupont de; Guillón, Christophe (2008). "Revisando la traducción fuera de SSA para determinar la corrección, la calidad del código y la eficiencia". HAL-Inria Cs.DS : 14.
  16. ^ "Presentación del WebKit FTL JIT". 13 de mayo de 2014.
  17. ^ "Presentación del compilador JIT B3". 15 de febrero de 2016.
  18. ^ "Lenguaje intermedio Swift (GitHub)". GitHub . 30 de octubre de 2021.
  19. ^ "IR de alto nivel de Swift: un estudio de caso sobre cómo complementar LLVM IR con optimización específica del lenguaje, LLVM Developers Meetup 10/2015". YouTube . 9 de noviembre de 2015. Archivado desde el original el 21 de diciembre de 2021.
  20. ^ "Notas de la versión OTP 22.0".
  21. ^ "Notas de la versión de Go 1.7: el lenguaje de programación Go". golang.org . Consultado el 17 de agosto de 2016 .
  22. ^ "Notas de la versión de Go 1.8: el lenguaje de programación Go". golang.org . Consultado el 17 de febrero de 2017 .
  23. ^ "Descripción general de IonMonkey".,
  24. ^ La evolución del ARTE - Google I/O 2016. Google . 25 de mayo de 2016. El evento ocurre a los 3m47s.
  25. ^ "Optimizaciones de bytecode". el proyecto LuaJIT.
  26. ^ "Representación intermedia del hip hop (HHIR)". GitHub . 30 de octubre de 2021.
  27. ^ "Firma - Optimización y Generación de Código Máquina".
  28. ^ Ekstrand, Jason (16 de diciembre de 2014). "Reintroduciendo NIR, un nuevo IR para mesa".
  29. ^ "La arquitectura del motor de rendimiento Java HotSpot". Oracle Corporation.
  30. ^ "Presentamos un nuevo y avanzado optimizador de código para Visual C++". 4 de mayo de 2016.
  31. ^ "Especificaciones del SPIR-V" (PDF) .
  32. ^ Sarkar, V. (mayo de 1997). "Selección automática de transformaciones de orden superior en los compiladores IBM XL FORTRAN" (PDF) . IBM Journal of Research and Development . 41 (3). IBM: 233–264. doi :10.1147/rd.413.0233.
  33. ^ Chakrabarti, Gautam; Grover, Vinod; Aarts, Bastiaan; Kong, Xiangyun; Kudlur, Manjunath; Lin, Yuan; Marathe, Jaydeep; Murphy, Mike; Wang, Jian-Zhong (2012). "CUDA: compilación y optimización para una plataforma GPU". Procedia Computer Science . 9 : 1910–1919. doi : 10.1016/j.procs.2012.04.209 .
  34. ^ "Proyecto de conciertos de Illinois". Archivado desde el original el 13 de marzo de 2014.
  35. ^ Ananian, C. Scott; Rinard, Martin (1999). Formulario de información única estática (PDF) (informe técnico). CiteSeerX 10.1.1.1.9976 . 
  36. ^ Enciclopedia de computación paralela.

Referencias generales

Enlaces externos