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]
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 := 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:
a=3*4+5;como si fueraa=17;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 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:
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.
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 Φ.
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.
{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ){{cite journal}}: Requiere citar revista |journal=( ayuda )