En el diseño del compilador , la forma estática de asignación única (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 convertir a SSA, las variables existentes en el IR original se dividen en versiones; las nuevas variables generalmente se indican con el nombre original con un subíndice, de modo que cada definición tenga su propia versión. Es posible que también sea necesario introducir declaraciones adicionales que se asignan a nuevas versiones de variables en el punto de unión de dos rutas de flujo de control. La conversión del formulario 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 cuando se analiza 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 preservar la forma SSA, de modo que se pueda realizar una optimización tras otra sin análisis adicionales. Las optimizaciones basadas en SSA suelen ser más eficientes y potentes que sus equivalentes anteriores que no son SSA.
En los compiladores de lenguajes funcionales , como los de Scheme y ML , generalmente se utiliza el estilo de paso de continuación (CPS). SSA es formalmente equivalente a un subconjunto de CPS que se comporta bien excluyendo el flujo de control no local, por lo que las optimizaciones y transformaciones formuladas en términos de uno generalmente se aplican al otro. Usar 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. [1]
SSA fue desarrollado en la década de 1980 por varios investigadores de IBM . Kenneth Zadeck, un miembro clave del equipo, se mudó a la Universidad de 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 de los escalares. [3] En 1988, Barry Rosen, Mark N. Wegman y Kenneth Zadeck reemplazaron las asignaciones de identidad con funciones Φ, introdujeron el nombre "forma estática de asignación única" y demostraron una optimización SSA ahora común. [6] Rosen eligió el nombre función Φ para que fuera 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 estática única". [7] Finalmente, en 1989, Rosen, Wegman, Zadeck, Cytron y Ferrante encontraron un medio eficaz 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 := 1y := 2x := y
Los humanos pueden ver que la primera asignación no es necesaria y que el valor de yser 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 formato SSA, ambos son inmediatos:
y 1 := 1y 2 := 2x 1 := y 2
Los algoritmos de optimización del compilador que se habilitan o se mejoran fuertemente mediante el uso de SSA incluyen:
a=3*4+5;como si lo fuera.a=17;Convertir 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 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. Del mismo modo, al asignar subíndices distintivos a todas las demás variables se obtiene:
Está claro a qué definición se refiere cada uso, excepto por un caso: ambos usos de y en el bloque inferior podrían referirse a y 1 o y 2 , dependiendo de qué camino 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 , dependiendo del flujo de control en el pasado.
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 , es decir, x 2 , llega a este lugar, 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 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 de "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 central izquierdo y un movimiento de y 2 a y 3 al final del bloque central derecho. 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 operaciones simultáneas producen especulativamente entradas para una función Φ, como puede suceder en máquinas de emisión amplia . Normalmente, una máquina de edición amplia tiene una instrucción de selección que el compilador utiliza en tales situaciones 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 alcanza el nodo B, se puede suponer que A se ha ejecutado. 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 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 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 = "caras"demás [3] resultado = "cruz"fin[4] imprimir (resultado)
El nodo 1 domina estrictamente a 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 pasa al nodo 4, la definición de resultusado depende de si el control se pasó 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 puede aplicar.
Existe un algoritmo eficiente para encontrar las fronteras de dominancia de cada nodo. Este algoritmo se describió originalmente en "Computación eficiente de la forma de asignación única estática y el gráfico de control" por 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 rápido y simple : [11]
para cada nodo b frontera_dominación(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) frontera_dominio(corredor) := frontera_dominio(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.
El SSA "mínimo" inserta el número mínimo 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 aún pueda hacer referencia 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, un 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 de manera menos eficiente.
La forma SSA podada se basa en una observación simple: las funciones Φ solo son necesarias para variables que están "activas" después de la función Φ. (Aquí, "en vivo" significa que el valor se usa a lo largo de alguna ruta que comienza en la función Φ en cuestión). Si una variable no está en vivo, 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 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 se reescribe cualquier uso en el programa de entrada, o si se usa 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. 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.
La forma SSA semipodada [12] es un intento de reducir el número de funciones Φ sin incurrir en el costo relativamente alto de calcular información de variables en vivo. Se basa en la siguiente observación: si una variable nunca está activa 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 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 el cálculo de la forma SSA semipodada sea más eficiente 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 son representativamente idénticas pero que en la práctica pueden ser más convenientes durante la optimización. Los bloques reciben nombre y toman una lista de argumentos de bloque, anotados como parámetros de función. Al llamar a un bloque, los argumentos del bloque están vinculados a valores específicos. Swift SIL y MLIR utilizan argumentos de bloque. [13]
La forma SSA normalmente no se usa para ejecución directa (aunque es posible interpretar SSA [14] ), y con frecuencia se usa "sobre" 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 el formulario SSA ya no sea necesario, estas funciones de mapeo pueden descartarse, dejando solo el IR ahora optimizado.
La realización de optimizaciones en formato SSA generalmente conduce a SSA-Webs entrelazados, lo que significa que hay Φ instrucciones cuyos operandos no tienen todos el mismo operando raíz. En tales casos, se utilizan algoritmos de color 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 de raíz diferente al 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 de ellos para fusionar las copias. [15]
Las extensiones al 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 un formulario estático de uso único (que cambia el nombre de cada variable en cada declaración cuando se usa) y un formulario estático 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 variables, pero incorporan nueva semántica para modelar funciones adicionales. Algunas extensiones de características específicas modelan características del lenguaje de programación de alto nivel, como matrices, objetos y punteros con alias. Otras extensiones específicas de características modelan características arquitectónicas de bajo nivel como la especulación y la predicción.
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace ){{cite journal}}: Citar diario requiere |journal=( ayuda )