Hispanopedia Wiki
Articulo de referencia

Asignación de registro

En la optimización del compilador , la asignación de registros es el proceso de asignar variables automáticas locales y resultados de expresiones a un número limitado de registr...

Hispanopedia WikiContenido en espanolLectura gratuita

En la optimización del compilador , la asignación de registros es el proceso de asignar variables automáticas locales y resultados de expresiones a un número limitado de registros del procesador .

La asignación de registros puede ocurrir en un bloque básico ( asignación de registros local ), en una función o procedimiento completo ( asignación de registros global ) o entre límites de funciones recorridos mediante un grafo de llamadas ( asignación de registros interprocedimental ). Cuando se realiza por función o procedimiento, la convención de llamada puede requerir la inserción de instrucciones de guardar/restaurar alrededor de cada punto de llamada .

Contexto

Principio

En muchos lenguajes de programación , el programador puede usar cualquier número de variables . La computadora puede leer y escribir registros rápidamente en la CPU , por lo que el programa se ejecuta más rápido cuando hay más variables en los registros de la CPU. [ 1 ] Además, a veces el código que accede a los registros es más compacto, por lo que el código es más pequeño y se puede recuperar más rápido si usa registros en lugar de memoria. Sin embargo, el número de registros es limitado. Por lo tanto, cuando el compilador traduce el código a lenguaje máquina, debe decidir cómo asignar las variables al número limitado de registros en la CPU. [ 2 ] [ 3 ]

No todas las variables están en uso (o "activas") al mismo tiempo, por lo que, durante la vida útil de un programa, un registro determinado puede usarse para almacenar diferentes variables. Sin embargo, dos variables en uso simultáneamente no pueden asignarse al mismo registro sin corromper una de ellas. Si no hay suficientes registros para almacenar todas las variables, algunas pueden moverse hacia y desde la RAM . Este proceso se denomina "desbordamiento" de los registros. [ 4 ] Durante la vida útil de un programa, una variable puede ser desbordada y almacenada en registros: esta variable se considera entonces "dividida". [ 5 ] El acceso a la RAM es significativamente más lento que el acceso a los registros [ 6 ] y, por lo tanto, un programa compilado se ejecuta más lentamente. Por consiguiente, un compilador optimizador busca asignar tantas variables a los registros como sea posible. Una alta " presión de registros " es un término técnico que significa que se necesitan más desbordamientos y recargas; Braun et al. la definen como "el número de variables activas simultáneamente en una instrucción". [ 7 ]

Además, algunos diseños de computadoras almacenan en caché los registros de acceso frecuente. Por lo tanto, los programas pueden optimizarse aún más asignando el mismo registro al origen y al destino de una moveinstrucción siempre que sea posible. Esto es especialmente importante si el compilador utiliza una representación intermedia como la forma estática de asignación única (SSA). En particular, cuando SSA no está completamente optimizada, puede generar moveinstrucciones adicionales de forma artificial.

Componentes de la asignación de registros

La asignación de registros consiste, por lo tanto, en elegir dónde almacenar las variables en tiempo de ejecución, es decir, dentro o fuera de los registros. Si la variable se va a almacenar en registros, el asignador debe determinar en qué registro(s) se almacenará. Finalmente, otro desafío es determinar durante cuánto tiempo debe permanecer una variable en la misma ubicación.

Un asignador de registros, sin importar la estrategia de asignación elegida, puede basarse en un conjunto de acciones básicas para abordar estos desafíos. Estas acciones se pueden agrupar en varias categorías diferentes: [ 8 ]

Mover inserción
Esta acción consiste en aumentar el número de instrucciones de movimiento entre registros, es decir, hacer que una variable resida en diferentes registros durante su vida útil, en lugar de en uno solo. Esto ocurre en el enfoque de rango de vida dividido.
Derramándose
Esta acción consiste en almacenar una variable en la memoria ( almacenamiento primario como la RAM ) en lugar de en los registros. [ 9 ]
Asignación
Esta acción consiste en asignar un registro a una variable. [ 10 ]
Coalescencia
Esta acción consiste en limitar el número de movimientos entre registros, limitando así el número total de instrucciones. Por ejemplo, identificando una variable que permanece activa en diferentes métodos y almacenándola en un único registro durante toda su vida útil. [ 9 ]

Muchos métodos de asignación de registros optimizan el rendimiento para una o más categorías específicas de acciones.

Registros Intel 386

Problemas comunes que se presentan en la asignación de registros

La asignación de registros plantea varios problemas que pueden abordarse (o evitarse) mediante diferentes enfoques de asignación de registros. Tres de los problemas más comunes se identifican a continuación:

Aliasing
En algunas arquitecturas, asignar un valor a un registro puede afectar el valor de otro: esto se denomina aliasing. Por ejemplo, la arquitectura x86 tiene cuatro registros de propósito general de 32 bits que también pueden usarse como registros de 16 u 8 bits. [ 11 ] En este caso, asignar un valor de 32 bits al registro eax afectará el valor del registro al.
Precoloración
Este problema consiste en forzar la asignación de ciertas variables a registros específicos. Por ejemplo, en las convenciones de llamada de PowerPC , los parámetros se suelen pasar en R3-R10 y el valor de retorno se pasa en R3. [ 12 ]
Problema NP
Chaitin et al. demostraron que la asignación óptima de registros es un problema NP-completo . Esta NP-completitud depende completamente de la estructura exacta del problema. Se ha demostrado que, para programas en forma SSA, la parte de coloración de grafos del problema de asignación de registros se puede resolver en tiempo lineal. Las causas que hacen que el problema general de coloración de grafos sea NP-completo y las que hacen que algunas versiones del problema de asignación de registros sean NP-completas son distintas. [ 13 ]

Técnicas de asignación de registros

La asignación de registros puede ocurrir sobre un bloque básico de código: se dice que es "local" y fue mencionada por primera vez por Horwitz et al. [ 14 ] Como los bloques básicos no contienen bifurcaciones, se cree que el proceso de asignación es rápido, porque la gestión de los puntos de fusión del grafo de flujo de control en la asignación de registros resulta ser una operación que consume mucho tiempo. [ 15 ] Sin embargo, se cree que este enfoque no produce un código tan optimizado como el enfoque "global", que opera sobre toda la unidad de compilación (un método o procedimiento, por ejemplo). [ 16 ]

Asignación de coloración de grafos

La asignación por coloración de grafos es el enfoque predominante para resolver la asignación de registros. [ 17 ] [ 18 ] Fue propuesta por primera vez por Chaitin et al. [ 4 ] En este enfoque, los nodos en el grafo representan rangos activos ( variables , temporales , registros virtuales/simbólicos) que son candidatos para la asignación de registros. Las aristas conectan rangos activos que interfieren, es decir, rangos activos que están activos simultáneamente en al menos un punto de programa. La asignación de registros se reduce entonces al problema de coloración de grafos en el que se asignan colores (registros) a los nodos de tal manera que dos nodos conectados por una arista no reciban el mismo color. [ 19 ]

Mediante el análisis de vivacidad , se puede construir un grafo de interferencia. Este grafo, que es un grafo de intervalos donde los nodos son las variables del programa, se utiliza para modelar qué variables no pueden asignarse al mismo registro. [ 20 ]

Principio

Las fases principales en un asignador de registros de coloración de grafos al estilo Chaitin son: [ 18 ]

Asignador de registros basado en coloración de grafos iterativa de Chaitin et al.
  1. Renumerar : descubre información sobre el rango en tiempo real en el programa de origen.
  2. Construir : construir el gráfico de interferencia.
  3. Coalesce : fusiona los rangos activos de variables que no interfieren entre sí, relacionadas por instrucciones de copia.
  4. Costo de desbordamiento : calcula el costo de desbordamiento de cada variable. Esto evalúa el impacto de asignar una variable a la memoria en la velocidad del programa final.
  5. Simplificar : construir un ordenamiento de los nodos en el grafo de inferencias.
  6. Código de desbordamiento : inserta instrucciones de desbordamiento, es decir, cargas y almacenamientos para conmutar valores entre registros y memoria.
  7. Seleccionar : asignar un registro a cada variable.

Inconvenientes y mejoras adicionales

La asignación de coloración de grafos tiene tres inconvenientes principales. Primero, se basa en la coloración de grafos, que es un problema NP-completo , para decidir qué variables se desbordan. Aunque encontrar una coloración mínima para grafos generales es de hecho un problema NP-completo, [ 21 ] la coloración mínima de grafos de intervalo (incluidos los grafos de interferencia) se puede hacer en tiempo lineal (ver escaneo lineal más adelante); [ 22 ] [ 23 ] Por lo tanto, esta técnica no utiliza completamente los supuestos del problema. Segundo, a menos que se utilice la división de rango de vida, las variables desalojadas se desbordan en todas partes: las instrucciones de almacenamiento se insertan lo antes posible, es decir, justo después de las definiciones de variables; las instrucciones de carga se insertan respectivamente tarde, justo antes del uso de la variable. Tercero, una variable que no se desborda se mantiene en el mismo registro durante toda su vida útil. [ 24 ]

Por otro lado, un mismo nombre de registro puede aparecer en múltiples clases de registros, donde una clase es un conjunto de nombres de registros intercambiables en una función específica. Además, varios nombres de registro pueden ser alias de un único registro de hardware. [ 25 ] Finalmente, la coloración de grafos es una técnica agresiva para la asignación de registros, pero computacionalmente costosa debido al uso del grafo de interferencia, cuyo tamaño en el peor de los casos puede ser cuadrático en el número de rangos activos. [ 26 ] La formulación tradicional de la asignación de registros mediante coloración de grafos asume implícitamente un único banco de registros de propósito general no superpuestos y no maneja características arquitectónicas irregulares como pares de registros superpuestos, registros de propósito especial y múltiples bancos de registros. [ 27 ]

Briggs et al. encontraron una mejora posterior del enfoque de coloración de grafos al estilo Chaitin: se denomina coalescencia conservadora. Esta mejora añade un criterio para decidir cuándo se pueden fusionar dos rangos de vida. Principalmente, además de los requisitos de no interferencia, dos variables solo se pueden fusionar si su fusión no provoca un derrame adicional. Briggs et al. introducen una segunda mejora a los trabajos de Chaitin, que es la coloración sesgada. La coloración sesgada intenta asignar el mismo color en la coloración de grafos a los rangos de vida que están relacionados por copia. [ 18 ]

Escaneo lineal

El escaneo lineal es otro enfoque de asignación global de registros. Fue propuesto por primera vez por Poletto et al. en 1999. [ 28 ] En este enfoque, el código no se convierte en un grafo. En cambio, todas las variables se escanean linealmente para determinar su rango de vida, representado como un intervalo. Una vez que se han determinado los rangos de vida de todas las variables, los intervalos se recorren cronológicamente. Si bien este recorrido podría ayudar a identificar variables cuyos rangos de vida interfieren, no se construye ningún grafo de interferencia y las variables se asignan de forma voraz. [ 26 ]

La motivación para este enfoque es la velocidad; no en términos del tiempo de ejecución del código generado, sino en términos del tiempo empleado en la generación de código. Por lo general, los enfoques estándar de coloración de grafos producen código de calidad, pero tienen una sobrecarga significativa , [ 29 ] [ 30 ] el algoritmo de coloración de grafos utilizado tiene un costo cuadrático. [ 31 ] Debido a esta característica, el escaneo lineal es el enfoque que se utiliza actualmente en varios compiladores JIT, como el compilador cliente Hotspot , V8 , Jikes RVM , [ 5 ] y Android Runtime (ART). [ 32 ] El compilador servidor Hotspot utiliza coloración de grafos para su código superior. [ 33 ]

Pseudocódigo

Esto describe el algoritmo tal como fue propuesto inicialmente por Poletto et al., [ 34 ] donde:

  • R es el número de registros disponibles.
  • active es la lista, ordenada en orden ascendente según el punto final, de intervalos activos que se superponen al punto actual y que se encuentran en registros.
Asignación de registro de escaneo lineal activo ← {} para cada intervalo vivo i , en orden creciente de punto de inicio hacer ExpireOldIntervals(i) si length(activo) = R entonces DerramarEnIntervalo(i) demás registro[i] ← un registro eliminado del grupo de registros libres agregar i a activo, ordenado por punto final creciente ExpireOldIntervals(i) para cada intervalo j en activo, en orden creciente de punto final hacer si endpoint[j] ≥ startpoint[i] entonces devolver eliminar j de activo agregar register[j] al grupo de registros libres DerramarEnIntervalo(i) derrame ← último intervalo en activo si endpoint[spill] > endpoint[i] entonces registrar[i] ← registrar[derrame] ubicación[derrame] ← nueva ubicación de la pila eliminar derrame de activo agregar i a activo, ordenado por punto final creciente de lo contrario ubicación[i] ← nueva ubicación de pila

Inconvenientes y mejoras adicionales

Sin embargo, el escaneo lineal presenta dos inconvenientes importantes. Primero, debido a su naturaleza voraz, no toma en cuenta los huecos de tiempo de vida, es decir, "rangos donde el valor de la variable no es necesario". [ 35 ] [ 36 ] Además, una variable derramada permanecerá derramada durante todo su tiempo de vida.

Alcances de vida más cortos con el enfoque SSA

Muchos otros trabajos de investigación dieron seguimiento al algoritmo de escaneo lineal de Poletto. Traub et al., por ejemplo, propusieron un algoritmo llamado empaquetamiento de contenedores de segunda oportunidad con el objetivo de generar código de mejor calidad. [ 37 ] [ 38 ] En este enfoque, las variables desbordadas tienen la oportunidad de almacenarse posteriormente en un registro mediante el uso de una heurística diferente a la utilizada en el algoritmo de escaneo lineal estándar. En lugar de usar intervalos vivos, el algoritmo se basa en rangos vivos, lo que significa que si un rango necesita ser desbordado, no es necesario desbordar todos los demás rangos correspondientes a esta variable.

La asignación de escaneo lineal también se adaptó para aprovechar la forma SSA : las propiedades de esta representación intermedia simplifican el algoritmo de asignación y permiten calcular directamente los huecos de vida útil. [ 39 ] En primer lugar, se reduce el tiempo empleado en el análisis del grafo de flujo de datos, destinado a construir los intervalos de vida útil, principalmente porque las variables son únicas. [ 40 ] En consecuencia, produce intervalos de vida más cortos, porque cada nueva asignación corresponde a un nuevo intervalo de vida. [ 41 ] [ 42 ] Para evitar modelar intervalos y huecos de vida útil, Rogers mostró una simplificación llamada conjuntos activos futuros que eliminó con éxito los intervalos para el 80 % de las instrucciones. [ 43 ]

Rematerialización

Coalescencia

En el contexto de la asignación de registros, la coalescencia consiste en fusionar operaciones de movimiento de variables asignando dichas variables a la misma ubicación. La operación de coalescencia se realiza después de que se construye el grafo de interferencia. Una vez que dos nodos se han coalescido, deben tener el mismo color y asignarse al mismo registro, cuando la operación de copia deja de ser necesaria. [ 44 ]

La coalescencia puede tener impactos tanto positivos como negativos en la colorabilidad del grafo de interferencia. [ 9 ] Por ejemplo, un impacto negativo que la coalescencia podría tener en la colorabilidad de la inferencia del grafo es cuando se fusionan dos nodos, ya que el nodo resultante tendrá una unión de las aristas de los nodos fusionados. [ 9 ] Un impacto positivo de la coalescencia en la colorabilidad del grafo de inferencia es, por ejemplo, cuando un nodo interfiere con ambos nodos fusionados, el grado del nodo se reduce en uno, lo que lleva a mejorar la colorabilidad general del grafo de interferencia. [ 45 ]

Existen varias heurísticas de coalescencia disponibles: [ 46 ]

Coalición agresiva
Se introdujo por primera vez en el asignador de registros original de Chaitin. Esta heurística tiene como objetivo fusionar cualquier nodo relacionado con copias que no interfiera. [ 47 ] Desde la perspectiva de la eliminación de copias, esta heurística ofrece los mejores resultados. [ 48 ] Por otro lado, una fusión agresiva podría afectar la colorabilidad del grafo de inferencia. [ 45 ]
Coalición conservadora
Utiliza principalmente la misma heurística que la coalescencia agresiva, pero fusiona movimientos si, y solo si, no compromete la colorabilidad del grafo de interferencia. [ 49 ]
Coalescencia iterada
Elimina un movimiento en particular a la vez, manteniendo la capacidad de colorear el gráfico. [ 50 ]
Coalición optimista
Se basa en la coalescencia agresiva, pero si la colorabilidad del grafo de inferencia se ve comprometida, entonces renuncia a la menor cantidad de movimientos posible. [ 51 ]

Enfoques mixtos

Asignación híbrida

Algunos otros enfoques de asignación de registros no se limitan a una sola técnica para optimizar su uso. Cavazos et al., por ejemplo, propusieron una solución que permite utilizar tanto el algoritmo de escaneo lineal como el de coloración de grafos. [ 52 ] En este enfoque, la elección entre una u otra solución se determina dinámicamente: primero, se utiliza un algoritmo de aprendizaje automático "fuera de línea", es decir, fuera de tiempo de ejecución, para construir una función heurística que determine qué algoritmo de asignación debe utilizarse. Posteriormente, la función heurística se utiliza en tiempo de ejecución; en función del comportamiento del código, el asignador puede elegir entre uno de los dos algoritmos disponibles. [ 53 ]

La asignación de registros de traza es un enfoque reciente desarrollado por Eisl et al. [ 3 ] [ 5 ]. Esta técnica gestiona la asignación localmente: se basa en datos de perfilado dinámico para determinar qué ramas serán las más utilizadas en un grafo de flujo de control dado. Luego, infiere un conjunto de "trazas" (es decir, segmentos de código) en los que se ignora el punto de fusión en favor de la rama más utilizada. Cada traza es procesada de forma independiente por el asignador. Este enfoque puede considerarse híbrido porque es posible utilizar diferentes algoritmos de asignación de registros entre las distintas trazas. [ 54 ]

Asignación dividida

La asignación dividida es otra técnica de asignación de registros que combina diferentes enfoques, generalmente considerados opuestos. Por ejemplo, la técnica de asignación híbrida puede considerarse dividida porque la primera etapa de construcción heurística se realiza fuera de línea y el uso de la heurística se realiza en línea. [ 26 ] De manera similar, B. Diouf et al. propusieron una técnica de asignación que se basa tanto en comportamientos fuera de línea como en línea, a saber, compilación estática y dinámica. [ 55 ] [ 56 ] Durante la etapa fuera de línea, primero se recopila un conjunto de desbordamiento óptimo utilizando Programación Lineal Entera . Luego, los rangos vivos se anotan utilizando el compressAnnotationalgoritmo que se basa en el conjunto de desbordamiento óptimo previamente identificado. La asignación de registros se realiza posteriormente durante la etapa en línea, basándose en los datos recopilados en la fase fuera de línea. [ 57 ]

En 2007, Bouchez et al. también sugirieron dividir la asignación de registros en diferentes etapas, dedicando una etapa al desbordamiento y otra a la coloración y coalescencia. [ 58 ]

Comparación entre las diferentes técnicas

Se han utilizado diversas métricas para evaluar el rendimiento de una técnica de asignación de registros frente a otra. La asignación de registros suele implicar un equilibrio entre la calidad del código, es decir, un código que se ejecute rápidamente, y la sobrecarga del análisis, es decir, el tiempo dedicado a analizar el código fuente para generar código con una asignación de registros optimizada. Desde esta perspectiva, el tiempo de ejecución del código generado y el tiempo dedicado al análisis de vivacidad son métricas relevantes para comparar las diferentes técnicas. [ 59 ]

Una vez seleccionadas las métricas pertinentes, el código sobre el que se aplicarán dichas métricas debe estar disponible y ser relevante para el problema, ya sea reflejando el comportamiento de una aplicación real o siendo relevante para el problema específico que el algoritmo pretende abordar. Los artículos más recientes sobre asignación de registros utilizan especialmente el conjunto de pruebas de rendimiento Dacapo. [ 60 ]

Véase también

  • Número de Strahler , el número mínimo de registros necesarios para evaluar un árbol de expresiones. [ 61 ]
  • Registro (palabra clave) , la indicación en C y C++ para que una variable se coloque en un registro.
  • El algoritmo de Sethi-Ullman es un algoritmo que produce la asignación de registros más eficiente para evaluar una sola expresión cuando el número de registros necesarios para evaluar la expresión excede el número de registros disponibles.

Referencias

  1. ^ Ditzel y McLellan 1982 , pág. 48.
  2. ^ Runeson y Nyström 2003 , pág. 242.
  3. ^ Eisl y col. 2016 , pág. 14:1.
  4. ^ Chaitin et al. 1981 , pág. 47.
  5. ^ Eisl y cols . 2016 , pág. 1.
  6. ↑ "Números de comparación de latencia en computadoras/redes" . blog.morizyun.com. 6 de enero de 2018. Consultado el 8 de enero de 2019 .
  7. ↑ Braun y Hack 2009 , pág. 174.
  8. ↑ Koes y Goldstein 2009 , pág. 21.
  9. ^ Bouchez , Darté y Rastello 2007b , pág . 103. 
  10. ↑ Colombet, Brandner y Darté 2011 , p. 26.
  11. ↑ "Manual del desarrollador de software para arquitecturas Intel® 64 e IA-32, Sección 3.4.1" (PDF) . Intel. Mayo de 2019. Archivado del original (PDF) el 25 de mayo de 2019.
  12. ↑ "Convenciones de llamada a funciones PowerPC de 32 bits" .
  13. ↑ Bouchez, Darté y Rastello 2006 , pág. 4.
  14. ^ Horwitz y col. 1966 , pág. 43.
  15. ↑ Farach y Liberatore 1998 , pág. 566.
  16. ↑ Eisl et al. 2017 , pág. 92.
  17. ↑ Eisl, Leopoldseder y Mössenböck 2018 , p. 1.
  18. 1 2 3 Briggs, Cooper y Torczon 1992 , pág. 316.
  19. ^ Poletto y Sarkar 1999 , pág. 896.
  20. ^ Runeson y Nyström 2003 , pág. 241.
  21. ↑ Libro 1975 , págs. 618–619.
  22. ↑ Cormen, Thomas H.; Leiserson, Charles Eric; Rivest, Ronald L.; Stein, Clifford (2022). Introducción a los algoritmos (4.ª ed.). MIT Press. 15.1-4: problema de coloración de grafos de intervalos. ISBN  9780262046305.
  23. ↑ Cormen, Thomas H. (2022). Manual del instructor para acompañar Introducción a los algoritmos, cuarta edición . MIT Press. págs. 219–220 . 
  24. ↑ Colombet, Brandner y Darté 2011 , p. 1.
  25. ↑ Smith, Ramsey y Holloway 2004 , pág. 277.
  26. ^ Cavazos , Moss y O'Boyle 2006 , pág . 124. 
  27. ^ Runeson y Nyström 2003 , pág. 240.
  28. ^ Poletto y Sarkar 1999 , pág. 895.
  29. ^ Poletto y Sarkar 1999 , pág. 902.
  30. ↑ Wimmer y Mössenböck 2005 , pág. 132.
  31. ↑ Johansson y Sagonas 2002 , pág. 102.
  32. ↑ La evolución del ART - Google I/O 2016. Google . 25 de mayo de 2016. El evento ocurre a los 3m47s.
  33. ↑ Paleczny, Vick y Click 2001 , pág. 1.
  34. ^ Poletto y Sarkar 1999 , pág. 899.
  35. ↑ Eisl et al. 2016 , pág. 2.
  36. ↑ Traub, Holloway y Smith 1998 , pág. 143.
  37. ↑ Traub, Holloway y Smith 1998 , pág. 141.
  38. ^ Poletto y Sarkar 1999 , pág. 897.
  39. ↑ Wimmer y Franz 2010 , pág. 170.
  40. ↑ Mössenböck y Pfeiffer 2002 , pág. 234.
  41. ↑ Mössenböck y Pfeiffer 2002 , pág. 233.
  42. ↑ Mössenböck y Pfeiffer 2002 , pág. 229.
  43. ↑ Rogers 2020 .
  44. ↑ Chaitin 1982 , pág. 90.
  45. 1 2 Ahn y Paek 2009 , pág. 7.
  46. ↑ Park y Moon 2004 , pág. 736.
  47. ↑ Chaitin 1982 , pág. 99.
  48. ↑ Park y Moon 2004 , pág. 738.
  49. ↑ Briggs, Cooper y Torczon 1994 , pág. 433.
  50. ^ George y Appel 1996 , pág. 212.
  51. ↑ Park y Moon 2004 , pág. 741.
  52. ↑ Eisl et al. 2017 , pág. 11.
  53. ^ Cavazos, Moss y O'Boyle 2006 , pág. 124-127.
  54. ↑ Eisl et al. 2016 , pág. 4.
  55. ^ Diouf y otros. 2010 , pág. 66.
  56. ↑ Cohen y Rohou 2010 , pág. 1.
  57. ^ Diouf y otros. 2010 , pág. 72.
  58. ↑ Bouchez, Darté y Rastello 2007a , p. 1.
  59. ^ Poletto y Sarkar 1999 , pág. 901-910.
  60. ↑ Blackburn et al. 2006 , pág. 169.
  61. ↑ Flajolet, Raoult y Vuillemin 1979 .

Fuentes

  • Ahn, Minwook; Paek, Yunheung (2009). "Técnicas de coalescencia de registros para arquitectura de registros heterogénea con filtrado de copias". ACM Transactions on Embedded Computing Systems . 8 (2): 1– 37. CiteSeerX 10.1.1.615.5767 . doi : 10.1145/1457255.1457263 . ISSN 1539-9087 . S2CID 14143277 .   
  • Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006). Compiladores: Principios, técnicas y herramientas (segunda  edición). Addison-Wesley Longman Publishing Co., Inc. ISBN 978-0321486813.
  • Appel, Andrew W.; George, Lal (2001). "Optimal spilling for CISC machines with few registers". Actas de la conferencia ACM SIGPLAN 2001 sobre diseño e implementación de lenguajes de programación - PLDI '01 . págs. 243–253 . CiteSeerX 10.1.1.37.8978 . doi : 10.1145/378795.378854 . ISBN   978-1581134148. S2CID 1380545 . 
  • Barik, Rajkishore; Grothoff, Christian; Gupta, Rahul; Pandit, Vinayaka; Udupa, Raghavendra (2007). "Asignación óptima de registros bit a bit mediante programación lineal entera". Lenguajes y compiladores para computación paralela . Notas de clase en ciencias de la computación. Vol.  4382. pp. 267–282 . CiteSeerX 10.1.1.75.6911 . doi : 10.1007/978-3-540-72521-3_20 . ISBN   978-3-540-72520-6.
  • Bergner, Peter; Dahl, Peter; Engebretsen, David; O'Keefe, Matthew (1997). «Minimización del código de desbordamiento mediante desbordamiento de regiones de interferencia». Actas de la conferencia ACM SIGPLAN 1997 sobre diseño e implementación de lenguajes de programación - PLDI '97 . págs. 287–295 . doi : 10.1145/258915.258941 . ISBN  978-0897919074. S2CID 16952747 . 
  • Blackburn, Stephen M.; Guyer, Samuel Z.; Hirzel, Martin; Hosking, Antony; Jump, Maria; Lee, Han; Eliot, J.; Moss, B.; Phansalkar, Aashish; Stefanović, Darko; VanDrunen, Thomas; Garner, Robin; von Dincklage, Daniel; Wiedermann, Ben; Hoffmann, Chris; Khang, Asjad M.; McKinley, Kathryn S.; Bentzur, Rotem; Diwan, Amer; Feinberg, Daniel; Frampton, Daniel (2006). "The DaCapo benchmarks". Actas de la 21.ª conferencia anual ACM SIGPLAN sobre sistemas, lenguajes y aplicaciones de programación orientada a objetos - OOPSLA '06 . p.  169. doi : 10.1145/1167473.1167488 . hdl : 1885/33723 . ISBN 978-1595933485. S2CID 9255051 . 
  • Book, Ronald V. (diciembre de 1975). "Karp Richard M. Reducibilidad entre problemas combinatorios. Complejidad de los cálculos computacionales, Actas de un simposio sobre la complejidad de los cálculos computacionales, celebrado del 20 al 22 de marzo de 1972 en el Centro IBM Thomas J. Watson, Yorktown Heights, Nueva York, editado por Miller Raymond E. y Thatcher James W., Plenum Press, Nueva York y Londres, 1972, pp. 85–103". The Journal of Symbolic Logic . 40 (4): 618– 619. doi : 10.2307/2271828 . ISSN 0022-4812 . JSTOR 2271828 .  
  • Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2006). "Asignación de registros: ¿Qué demuestra realmente la prueba de NP-completitud de Chaitin et al.? O Revisando la asignación de registros: Por qué y cómo". Asignación de registros: ¿Qué demuestra realmente la prueba de NP-completitud de Chaitin et al.? . Lecture Notes in Computer Science. Vol.  4382. pp. 2–14 . doi : 10.1007/978-3-540-72521-3_21 . ISBN  978-3-540-72520-6.
  • Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2007a). «Sobre la complejidad de la coalescencia de registros». Simposio Internacional sobre Generación y Optimización de Código (CGO'07) . págs. 102–114 . CiteSeerX 10.1.1.101.6801 . doi : 10.1109/CGO.2007.26 . ISBN   978-0-7695-2764-2. S2CID 7683867 . 
  • Bouchez, Florent; Darté, Alain; Rastello, Fabrice (2007b). "Sobre la complejidad del derrame en todas partes bajo forma SSA". Avisos ACM SIGPLAN . 42 (7): 103–114 . arXiv : 0710.3642 . doi : 10.1145/1273444.1254782 . ISSN 0362-1340 . 
  • Braun, Matthias; Hack, Sebastian (2009). "Register Spilling and Live-Range Splitting for SSA-Form Programs". Compiler Construction . Lecture Notes in Computer Science. Vol. 5501.  pp. 174–189 . CiteSeerX 10.1.1.219.5318 . doi : 10.1007/978-3-642-00722-4_13 . ISBN   978-3-642-00721-7ISSN 0302-9743​​ 
  • Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). "Rematerialización". ACM SIGPLAN Notices . 27 (7): 311– 321. doi : 10.1145/143103.143143 . ISSN 0362-1340 . 
  • Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1994). "Mejoras en la asignación de registros de coloración de grafos". ACM Transactions on Programming Languages ​​and Systems . 16 (3): 428– 455. CiteSeerX 10.1.1.23.253 . doi : 10.1145/177492.177575 . ISSN 0164-0925 . S2CID 6571479 .   
  • Cavazos, John; Moss, J. Eliot B.; O'Boyle, Michael FP (2006). "Optimizaciones híbridas: ¿Qué algoritmo de optimización utilizar?". Construcción de compiladores . Notas de clase en ciencias de la computación. Vol.  3923. pp. 124–138 . doi : 10.1007/11688839_12 . ISBN  978-3-540-33050-9ISSN 0302-9743​​ 
  • Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; Markstein, Peter W. (1981). "Asignación de registros mediante coloración". Computer Languages . 6 (1): 47– 57. doi : 10.1016/0096-0551(81)90048-5 . ISSN 0096-0551 . 
  • Chaitin, GJ (1982). "Asignación y desbordamiento de registros mediante coloración de grafos". Actas del simposio SIGPLAN de 1982 sobre construcción de compiladores - SIGPLAN '82 . págs. 98–101 . doi : 10.1145/800230.806984 . ISBN  978-0897910743. S2CID 16872867 . 
  • Chen, Wei-Yu; Lueh, Guei-Yuan; Ashar, Pratik; Chen, Kaiyu; Cheng, Buqi (2018). "Asignación de registros para gráficos de procesadores Intel". Actas del Simposio Internacional de Generación y Optimización de Código de 2018 - CGO 2018. págs. 352–364 . doi : 10.1145/3168806 . ISBN  9781450356176. S2CID 3367270 . 
  • Cohen, Albert; Rohou, Erven (2010). «Virtualización de procesadores y compilación dividida para sistemas embebidos multinúcleo heterogéneos». Actas de la 47.ª Conferencia de Automatización del Diseño (DAC '10 ). pág.  102. CiteSeerX 10.1.1.470.9701 . doi : 10.1145/1837274.1837303 . ISBN  9781450300025. S2CID 14314078 . 
  • Colombet, Quentin; Brandner, Florian; Darte, Alain (2011). «Estudio del desbordamiento óptimo a la luz de SSA». Actas de la 14.ª conferencia internacional sobre compiladores, arquitecturas y síntesis para sistemas embebidos - CASES '11 . p.  25. doi : 10.1145/2038698.2038706 . ISBN 9781450307130. S2CID 8296742 . 
  • Diouf, Boubacar; Cohen, Albert; Rastello, Fabrice; Cavazos, John (2010). "Asignación de registros divididos: complejidad lineal sin penalización de rendimiento". Arquitecturas y compiladores embebidos de alto rendimiento . Notas de clase en ciencias de la computación. Vol.  5952. pp. 66–80 . CiteSeerX 10.1.1.229.3988 . doi : 10.1007/978-3-642-11515-8_7 . ISBN   978-3-642-11514-1ISSN 0302-9743​​ 
  • Ditzel, David R.; McLellan, HR (1982). «Asignación de registros gratuita». Actas del primer simposio internacional sobre soporte arquitectónico para lenguajes de programación y sistemas operativos - ASPLOS-I . págs. 48–56 . doi : 10.1145/800050.801825 . ISBN  978-0897910668. S2CID 2812379 . 
  • Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). «Asignación de registros basada en trazas en un compilador JIT». Actas de la 13.ª Conferencia Internacional sobre Principios y Prácticas de Programación en la Plataforma Java: Máquinas Virtuales, Lenguajes y Herramientas - PPPJ '16 . págs. 1–11 . doi : 10.1145/2972206.2972211 . ISBN  9781450341356. S2CID 31845919 . 
  • Eisl, Josef; Marr, Stefan; Würthinger, Thomas; Mössenböck, Hanspeter (2017). «Políticas de asignación de registros de traza» (PDF) . Actas de la 14.ª Conferencia Internacional sobre Lenguajes y Entornos de Ejecución Gestionados - Man Lang 2017. págs. 92–104 . doi : 10.1145/3132190.3132209 . ISBN  9781450353403. S2CID 1195601 . 
  • Eisl, Josef; Leopoldseder, David; Mössenböck, Hanspeter (2018). «Asignación paralela de registros de trazas». Actas de la 15.ª Conferencia Internacional sobre Lenguajes y Entornos de Ejecución Gestionados - Man Lang '18 . págs. 1–7 . doi : 10.1145/3237009.3237010 . ISBN  9781450364249. S2CID 52137887 . 
  • Koes, David Ryan; Goldstein, Seth Copen (2009). «Register Allocation Deconstructed» . Escrito en Niza, Francia. Actas del 12.º Taller Internacional sobre Software y Compiladores para Sistemas Embebidos . SCOPES '09. Nueva York, NY, EE. UU.: ACM. págs. 21-30 . ISBN  978-1-60558-696-0.
  • Farach, Martin; Liberatore, Vincenzo (1998). «Sobre la asignación de registros locales» . Escrito en San Francisco, California, EE. UU. Actas del Noveno Simposio Anual ACM-SIAM sobre Algoritmos Discretos . SODA '98. Filadelfia, PA, EE. UU.: Society for Industrial and Applied Mathematics. págs. 564–573 . ISBN  0-89871-410-9.
  • Flajolet, P .; Raoult, JC; Vuillemin, J. (1979), "El número de registros necesarios para evaluar expresiones aritméticas", Theoretical Computer Science , 9 (1): 99–125 , doi : 10.1016/0304-3975(79)90009-4
  • George, Lal; Appel, Andrew W. (1996). "Iterated register coalescing" . ACM Transactions on Programming Languages ​​and Systems . 18 (3): 300– 324. doi : 10.1145/229542.229546 . ISSN 0164-0925 . S2CID 12281734 .  
  • Horwitz, LP; Karp, RM; Miller, RE; Winograd, S. (1966). "Asignación de registro de índice" . Journal of the ACM . 13 (1): 43– 61. doi : 10.1145/321312.321317 . ISSN 0004-5411 . S2CID 14560597 .  
  • Johansson, Erik; Sagonas, Konstantinos (2002). "Asignación de registros de escaneo lineal en un compilador Erlang de alto rendimiento". Aspectos prácticos de los lenguajes declarativos . Notas de clase en informática. Vol.  2257. pp. 101–119 . doi : 10.1007/3-540-45587-6_8 . ISBN  978-3-540-43092-6ISSN 0302-9743​​ 
  • Kurdahi, FJ; Parker, AC (1987). "REAL: un programa para la asignación de registros". Actas de la 24.ª conferencia ACM/IEEE sobre automatización del diseño - DAC '87 . págs. 210–215 . doi : 10.1145/37888.37920 . ISBN  978-0818607813. S2CID 17598675 . 
  • Mössenböck, Hanspeter; Pfeiffer, Michael (2002). "Asignación de registros de escaneo lineal en el contexto de la forma SSA y las restricciones de registro". Construcción de compiladores . Notas de clase en ciencias de la computación. Vol.  2304. págs. 229–246 . doi : 10.1007/3-540-45937-5_17 . ISBN  978-3-540-43369-9ISSN 0302-9743​​ 
  • Nickerson, Brian R. (1990). "Asignación de registros de coloración de grafos para procesadores con operandos de múltiples registros". ACM SIGPLAN Notices . 25 (6): 40– 52. doi : 10.1145/93548.93552 . ISSN 0362-1340 . 
  • Paleczny, Michael; Vick, Christopher; Click, Cliff (2001). "El compilador del servidor Java HotSpot". Actas del Simposio de Investigación y Tecnología de la Máquina Virtual Java (JVM01) . Monterey, California, EE. UU. pp. 1–12 . CiteSeerX 10.1.1.106.1919 .  
  • Park, Jinpyo; Moon, Soo-Mook (2004). "Coalescencia de registros optimista". ACM Transactions on Programming Languages ​​and Systems . 26 (4): 735– 765. CiteSeerX 10.1.1.33.9438 . doi : 10.1145/1011508.1011512 . ISSN 0164-0925 . S2CID 15969885 .   
  • Poletto, Massimiliano; Sarkar, Vivek (1999). "Asignación de registro de exploración lineal". ACM Transactions on Programming Languages ​​and Systems . 21 (5): 895– 913. CiteSeerX 10.1.1.27.2462 . doi : 10.1145/330249.330250 . ISSN 0164-0925 . S2CID 18180752 .   
  • Rogers, Ian (2020). "Asignación eficiente de registros globales". arXiv : 2011.05608 [ cs.PL ].
  • Runeson, Johan; Nyström, Sven-Olof (2003). "Asignación de registros de coloración de grafos reorientable para arquitecturas irregulares". Software y compiladores para sistemas embebidos . Notas de clase en ciencias de la computación. Vol.  2826. pp. 240–254 . CiteSeerX 10.1.1.6.6186 . doi : 10.1007/978-3-540-39920-9_17 . ISBN   978-3-540-20145-8ISSN 0302-9743​​ 
  • Smith, Michael D.; Ramsey, Norman; Holloway, Glenn (2004). "Un algoritmo generalizado para la asignación de registros mediante coloración de grafos". ACM SIGPLAN Notices . 39 (6): 277. CiteSeerX 10.1.1.71.9532 . doi : 10.1145/996893.996875 . ISSN 0362-1340 .  
  • Traub, Omri; Holloway, Glenn; Smith, Michael D. (1998). "Calidad y velocidad en la asignación de registros de exploración lineal". ACM SIGPLAN Notices . 33 (5): 142– 151. CiteSeerX 10.1.1.52.8730 . doi : 10.1145/277652.277714 . ISSN 0362-1340 .  
  • Wimmer, Christian; Mössenböck, Hanspeter (2005). «División de intervalos optimizada en un asignador de registros de exploración lineal». Actas de la 1.ª conferencia internacional ACM/USENIX sobre entornos de ejecución virtual - VEE '05 . pág.  132. CiteSeerX 10.1.1.394.4054 . doi : 10.1145/1064979.1064998 . ISBN  978-1595930477. S2CID 494490 . 
  • Wimmer, Christian; Franz, Michael (2010). "Asignación de registro de exploración lineal en formato SSA". Actas del 8.º simposio internacional anual IEEE/ACM sobre generación y optimización de código - CGO '10 . p.  170. CiteSeerX 10.1.1.162.2590 . doi : 10.1145/1772954.1772979 . ISBN  9781605586359. S2CID 1820765 . 
  • Tutorial sobre programación entera archivado el 5 de septiembre de 2009 en Wayback Machine.
  • Conferencia sobre Programación Entera y Optimización Combinatoria, IPCO
  • Taller de Optimización Combinatoria de Aussois
  • 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 las versiones anteriores de IR.
  • La bibliografía del SSA . Amplio catálogo de trabajos de investigación sobre el SSA.
  • Zadeck, F. Kenneth. "El desarrollo del formato de asignación única estática" Archivado el 20 de junio de 2010 en Wayback Machine , charla de diciembre de 2007 sobre los orígenes de SSA.
  • VV.AA. "Diseño de compiladores basado en SSA" (2014)
  • Citas de CiteSeer
  • Manuales de optimización de Agner Fog : documentación sobre la arquitectura del procesador x86 y la optimización de código de bajo nivel.