Asignación de registros
Técnica de optimización del compilador informático

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 locales ), en una función o procedimiento completo ( asignación de registros globales ) o a través de los límites de funciones atravesados ​​a través del gráfico de llamadas ( asignación de registros entre procedimientos ). Cuando se realiza por función o procedimiento, la convención de llamadas puede requerir la inserción de una operación de guardar/restaurar alrededor de cada sitio de llamada .

Contexto

Principio

Diferentes números de registros escalares en las arquitecturas más comunes
Arquitectura32 bits64 bits
BRAZO1531
Intel x86816
MIPS3232
ENERGÍA/PowerPC3232
RISC-V16/3232
SPARC3131


En muchos lenguajes de programación , el programador puede utilizar cualquier número de variables . La computadora puede leer y escribir rápidamente registros en la CPU , por lo que el programa de computadora se ejecuta más rápido cuando puede haber 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 está traduciendo código a lenguaje de máquina, debe decidir cómo asignar 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 al mismo tiempo no pueden asignarse al mismo registro sin corromper una de las variables. Si no hay suficientes registros para contener todas las variables, algunas variables pueden moverse hacia y desde la RAM . Este proceso se llama "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 como "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 lo tanto, un compilador optimizador tiene como objetivo asignar tantas variables a los registros como sea posible. Una " presión de registro " alta es un término técnico que significa que se necesitan más desbordamientos y recargas; Braun et al. la define como "la cantidad de variables activas simultáneamente en una instrucción". [7]

Además, algunos diseños de computadoras almacenan en caché los registros a los que se accede con frecuencia. Por lo tanto, los programas se pueden optimizar aún más asignando el mismo registro a una fuente y un destino de una moveinstrucción siempre que sea posible. Esto es especialmente importante si el compilador utiliza una representación intermedia, como la forma de asignación única estática (SSA). En particular, cuando la 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á esta variable. Finalmente, otro desafío es determinar el tiempo durante el cual una variable debe permanecer en la misma ubicación.

Un asignador de registros, independientemente de la estrategia de asignación elegida, puede confiar 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 viva 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 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 está viva en diferentes métodos y almacenándola en un registro durante toda su vida útil. [9]

Muchos enfoques de asignación de registros se optimizan para una o más categorías específicas de acciones.

Registros Intel 386

Problemas comunes que surgen en la asignación de registros

La asignación de registros plantea varios problemas que pueden abordarse (o evitarse) mediante distintos enfoques de asignación de registros. A continuación se indican tres de los problemas más comunes:

Alias
En algunas arquitecturas, la asignación de un valor a un registro puede afectar el valor de otro: esto se denomina aliasing. Por ejemplo, la arquitectura x86 tiene cuatro registros de 32 bits de propósito general que también se pueden utilizar como registros de 16 u 8 bits. [11] En este caso, la asignación de un valor de 32 bits al registro eax afectará el valor del registro al.
Pre-coloración
Este problema es un acto para forzar que algunas variables se asignen a registros particulares. Por ejemplo, en las convenciones de llamadas de PowerPC , los parámetros se pasan comúnmente en R3-R10 y el valor de retorno se pasa en R3. [12]
Problema NP
Chaitin et al. demostraron que la asignación de registros es un problema NP-completo . Reducen el problema de coloración de grafos al problema de asignación de registros al demostrar que para un grafo arbitrario, se puede construir un programa de manera que la asignación de registros para el programa (donde los registros representan nodos y los registros de la máquina representan colores disponibles) sería una coloración para el grafo original. Como la coloración de grafos es un problema NP-difícil y la asignación de registros está en NP, esto demuestra la NP-completitud del problema. [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 mencionado por primera vez por Horwitz et al. [14] Como los bloques básicos no contienen ramas, se piensa que el proceso de asignación es rápido, porque la gestión de los puntos de fusión del gráfico de flujo de control en la asignación de registros se revela [ aclaración necesaria ] como una operación que consume mucho tiempo. [15] Sin embargo, se piensa 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 gráficos

La asignación de coloración de gráficos 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 gráfico representan rangos vivos ( variables , temporales , registros virtuales/simbólicos) que son candidatos para la asignación de registros. Los bordes conectan rangos vivos que interfieren, es decir, rangos vivos que están activos simultáneamente en al menos un punto del programa. La asignación de registros luego se reduce al problema de coloración de gráficos en el que se asignan colores (registros) a los nodos de modo que dos nodos conectados por un borde no reciben el mismo color. [19]

Mediante el análisis de vitalidad se puede construir un gráfico de interferencias. El gráfico de interferencias, que es un gráfico no dirigido donde los nodos son las variables del programa, se utiliza para modelar qué variables no se pueden asignar al mismo registro. [20]

Principio

Las fases principales de un asignador de registros de coloración de gráficos de estilo Chaitin son: [18]

Asignador de registros basado en coloración de gráficos iterativa de Chaitin et al.
  1. Renumerar : descubre información de rango en vivo en el programa fuente.
  2. Construir : construye el gráfico de interferencia.
  3. Coalesce : fusionar los rangos en vivo de variables que no interfieren relacionadas mediante instrucciones de copia.
  4. Coste de derrame : calcula el coste de derrame de cada variable. Esto evalúa el impacto de la asignación de una variable a la memoria en la velocidad del programa final.
  5. Simplificar : construir un ordenamiento de los nodos en el gráfico de inferencias
  6. Código de derrame : inserta instrucciones de derrame, es decir, carga y almacena para conmutar valores entre registros y memoria.
  7. Seleccionar : asigna un registro a cada variable.

Desventajas y mejoras adicionales

La asignación de coloración de grafos tiene tres desventajas principales. En primer lugar, se basa en la coloración de grafos, que es un problema NP-completo , para decidir qué variables se derraman. Encontrar un grafo de coloración mínima es de hecho un problema NP-completo. [21] En segundo lugar, a menos que se utilice la división de rango en vivo, las variables expulsadas se derraman en todas partes: las instrucciones de almacenamiento se insertan lo antes posible, es decir, justo después de las definiciones de las variables; las instrucciones de carga se insertan respectivamente tarde, justo antes del uso de la variable. En tercer lugar, una variable que no se derrama se mantiene en el mismo registro durante toda su vida útil. [22]

Por otra parte, un único nombre de registro puede aparecer en múltiples clases de registros, donde una clase es un conjunto de nombres de registros que son intercambiables en una función particular. Entonces, múltiples nombres de registros pueden ser alias para un único registro de hardware. [23] Finalmente, la coloración de gráficos es una técnica agresiva para asignar registros, pero es computacionalmente costosa debido a su uso del gráfico de interferencia, que puede tener un tamaño de peor caso que es cuadrático en el número de rangos activos. [24] La formulación tradicional de la asignación de registros por coloración de gráficos supone 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. [25]

Briggs et al. descubrieron una mejora posterior del método de coloración de gráficos al estilo Chaitin: se denomina coalescencia conservadora. Esta mejora agrega un criterio para decidir cuándo se pueden fusionar dos rangos vivos. Básicamente, además de los requisitos de no interferencia, dos variables solo se pueden fusionar si su fusión no causará más derrames. Briggs et al. introduce 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 gráficos a rangos vivos que están relacionados con copias. [18]

Exploración lineal

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

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

Pseudocódigo

Esto describe el algoritmo propuesto por primera vez por Poletto et al., [32] donde:

  • R es el número de registros disponibles.
  • activo es la lista, ordenada en orden creciente de punto final, de intervalos en vivo que se superponen al punto actual y se colocan en registros.
Asignación de registro de escaneo lineal activo ← {} para cada intervalo en vivo i , en orden creciente de punto de inicio do Intervalos de caducidad antiguos (i) si longitud(activa) = R entonces DerrameEnIntervalo(i) demás register[i] ← un registro eliminado del grupo de registros libres Agregar i a activo, ordenado por punto final crecienteExpireOldIntervals(i)  para cada intervalo j  en activo, en orden creciente de punto final ,  si endpoint[j] ≥ startpoint[i], entonces  devuelve eliminar j del activo añadir register[j] al grupo de registros libresDerrameEnIntervalo(i) derrame ← último intervalo en activo si punto final[spill] > punto final[i] entonces registrarse[i] ← registrarse[spill] Ubicación[spill] ← nueva ubicación de la pila eliminar el derrame del activo añadir i al activo, ordenado por punto final creciente de lo contrario Ubicación[i] ← nueva ubicación de la pila

Desventajas y mejoras adicionales

Sin embargo, el escaneo lineal presenta dos inconvenientes importantes. En primer lugar, debido a su aspecto voraz, no tiene en cuenta los agujeros de tiempo de vida, es decir, "los intervalos en los que no se necesita el valor de la variable". [33] [34] Además, una variable derramada permanecerá derramada durante toda su vida útil.

Alcances de vida más cortos con el enfoque SSA

Muchos otros trabajos de investigación siguieron el algoritmo de escaneo lineal de Poletto. Traub et al., por ejemplo, propusieron un algoritmo llamado binpacking de segunda oportunidad que apunta a generar código de mejor calidad. [35] [36] En este enfoque, las variables derramadas tienen la oportunidad de almacenarse más tarde en un registro utilizando una heurística diferente de la utilizada en el algoritmo de escaneo lineal estándar. En lugar de utilizar intervalos en vivo, el algoritmo se basa en rangos en vivo, lo que significa que si es necesario derramar un rango, no es necesario derramar 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 que los agujeros de vida se calculen directamente. [37] Primero, el tiempo empleado en el análisis del gráfico de flujo de datos, destinado a construir los intervalos de vida, se reduce, es decir, porque las variables son únicas. [38] En consecuencia, produce intervalos vivos más cortos, porque cada nueva asignación corresponde a un nuevo intervalo vivo. [39] [40] Para evitar intervalos de modelado y agujeros de vida, Rogers mostró una simplificación llamada conjuntos activos futuros que eliminaron con éxito los intervalos para el 80% de las instrucciones. [41]

Rematerialización

Coalescencia

En el contexto de la asignación de registros, la fusión es el acto de fusionar operaciones de movimiento de variable a variable asignando esas dos variables a la misma ubicación. La operación de fusión se lleva a cabo después de que se construye el gráfico de interferencia. Una vez que se han fusionado dos nodos, deben obtener el mismo color y asignarse al mismo registro, una vez que la operación de copia se vuelve innecesaria. [42]

La realización de la coalescencia puede tener impactos tanto positivos como negativos en la colorabilidad del gráfico de interferencia. [9] Por ejemplo, un impacto negativo que la coalescencia podría tener en la colorabilidad de la inferencia del gráfico es cuando se fusionan dos nodos, ya que el nodo resultante tendrá una unión de los bordes de los que se están fusionando. [9] Un impacto positivo de la coalescencia en la colorabilidad del gráfico de inferencia es, por ejemplo, cuando un nodo interfiere con ambos nodos que se están fusionando, el grado del nodo se reduce en uno, lo que conduce a una mejora en la colorabilidad general del gráfico de interferencia. [43]

Hay varias heurísticas de coalescencia disponibles: [44]

Coalescencia agresiva
Fue introducido por primera vez por el asignador de registros original de Chaitin. Esta heurística tiene como objetivo fusionar todos los nodos relacionados con copias que no interfieran. [45] Desde la perspectiva de la eliminación de copias, esta heurística tiene los mejores resultados. [46] Por otro lado, la coalescencia agresiva podría afectar la colorabilidad del gráfico de inferencia. [43]
Conservación fusionándose
Utiliza principalmente la misma heurística que la coalescencia agresiva pero fusiona movimientos si, y solo si, no compromete la colorabilidad del gráfico de interferencia. [47]
Coalescencia iterada
Elimina un movimiento en particular a la vez, mientras mantiene la colorabilidad del gráfico. [48]
Coalición optimista
Se basa en una coalescencia agresiva, pero si se compromete la colorabilidad del gráfico de inferencia, entonces se renuncia a la menor cantidad de movimientos posible. [49]

Enfoques mixtos

Asignación híbrida

Otros enfoques de asignación de registros no se limitan a una sola técnica para optimizar el uso de los registros. Cavazos et al., por ejemplo, propusieron una solución en la que es posible utilizar tanto el algoritmo de escaneo lineal como el de coloración de gráficos. [50] 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, no en tiempo de ejecución, para construir una función heurística que determina qué algoritmo de asignación se debe utilizar. Luego, la función heurística se utiliza en tiempo de ejecución; a la luz del comportamiento del código, el asignador puede elegir entre uno de los dos algoritmos disponibles. [51]

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

Asignación dividida

La asignación dividida es otra técnica de asignación de registros que combina diferentes enfoques, generalmente considerados como opuestos. Por ejemplo, la técnica de asignación híbrida puede considerarse dividida porque la primera etapa de construcción de la heurística se realiza fuera de línea y el uso de la heurística se realiza en línea. [24] De la misma manera, 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, la compilación estática y dinámica. [53] [54] Durante la etapa fuera de línea, primero se recopila un conjunto de derrame óptimo utilizando la Programación Lineal Entera . Luego, los rangos en vivo se anotan utilizando el compressAnnotationalgoritmo que se basa en el conjunto de derrame óptimo previamente identificado. La asignación de registros se realiza después durante la etapa en línea, en función de los datos recopilados en la fase fuera de línea. [55]

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

Comparación entre las diferentes técnicas

Se han utilizado varias métricas para evaluar el rendimiento de una técnica de asignación de registros frente a otra. La asignación de registros normalmente tiene que lidiar con un equilibrio entre la calidad del código, es decir, código que se ejecuta rápidamente, y la sobrecarga de análisis, es decir, el tiempo dedicado a determinar el análisis del 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 la actividad son métricas relevantes para comparar las diferentes técnicas. [57]

Una vez elegidas las métricas pertinentes, el código en el que se aplicarán las métricas debe estar disponible y ser pertinente al problema, ya sea reflejando el comportamiento de la aplicación en el mundo real o siendo pertinente al problema particular que el algoritmo desea abordar. Los artículos más recientes sobre la asignación de registros utilizan especialmente el conjunto de pruebas de rendimiento Dacapo. [58]

Véase también

  • Número de Strahler , el número mínimo de registros necesarios para evaluar un árbol de expresión. [59]
  • Registrar (palabra clave) , la sugerencia en C y C++ para que una variable se coloque en un registro.
  • Algoritmo de Sethi-Ullman , un algoritmo para producir la asignación de registros más eficiente para evaluar una sola expresión cuando la cantidad de registros necesarios para evaluar la expresión excede la cantidad de registros disponibles.

Referencias

  1. ^ Ditzel y McLellan 1982, pág. 48.
  2. ^ Runeson y Nyström 2003, pág. 242.
  3. ^ ab Eisl et al. 2016, pág. 14:1.
  4. ^ ab Chaitin et al. 1981, pág. 47.
  5. ^ abc Eisl y otros, 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 & Hack 2009, pág. 174.
  8. ^ Koes y Goldstein 2009, pág. 21.
  9. ^ abcd Bouchez, Darte y Rastello 2007b, p. 103.
  10. ^ Colombet, Brandner y Darte 2011, pág. 26.
  11. ^ "Manual del desarrollador de software de arquitecturas Intel® 64 e IA-32, sección 3.4.1" (PDF) . Intel. Mayo de 2019. Archivado desde el original (PDF) el 25 de mayo de 2019.
  12. ^ "Convenciones de llamada de funciones PowerPC de 32 bits".
  13. ^ Bouchez, Darté y Rastello 2006, p. 4.
  14. ^ Horwitz y otros. 1966, pág. 43.
  15. ^ Farach y Liberatore 1998, pág. 566.
  16. ^ Eisl y otros. 2017, pág. 92.
  17. ^ Eisl, Leopoldseder y Mössenböck 2018, p. 1.
  18. ^ abc 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ág. 618–619.
  22. ^ Colombet, Brandner y Darte 2011, pág. 1.
  23. ^ Smith, Ramsey y Holloway 2004, pág. 277.
  24. ^ abc Cavazos, Moss y O'Boyle 2006, p. 124.
  25. ^ Runeson y Nyström 2003, pág. 240.
  26. ^ Poletto y Sarkar 1999, pág. 895.
  27. ^ Poletto y Sarkar 1999, pág. 902.
  28. ^ Wimmer y Mössenböck 2005, pág. 132.
  29. ^ Johansson y Sagonas 2002, pág. 102.
  30. ^ La evolución del ARTE - Google I/O 2016. Google . 25 de mayo de 2016. El evento ocurre a los 3m47s.
  31. ^ Paleczny, Vick & Click 2001, pág. 1.
  32. ^ Poletto y Sarkar 1999, pág. 899.
  33. ^ Eisl y otros. 2016, pág. 2.
  34. ^ Traub, Holloway y Smith 1998, pág. 143.
  35. ^ Traub, Holloway y Smith 1998, pág. 141.
  36. ^ Poletto y Sarkar 1999, pág. 897.
  37. ^ Wimmer y Franz 2010, pág. 170.
  38. ^ Mössenböck y Pfeiffer 2002, pág. 234.
  39. ^ Mössenböck y Pfeiffer 2002, pág. 233.
  40. ^ Mössenböck y Pfeiffer 2002, pág. 229.
  41. ^ Rogers 2020.
  42. ^ Chaitin 1982, pág. 90.
  43. ^ ab Ahn & Paek 2009, pág. 7.
  44. ^ Park y Moon 2004, pág. 736.
  45. ^ Chaitin 1982, pág. 99.
  46. ^ Park y Moon 2004, pág. 738.
  47. ^ Briggs, Cooper y Torczon 1994, pág. 433.
  48. ^ George y Appel 1996, pág. 212.
  49. ^ Park y Moon 2004, pág. 741.
  50. ^ Eisl y otros. 2017, pág. 11.
  51. ^ Cavazos, Moss y O'Boyle 2006, pág. 124-127.
  52. ^ Eisl y otros. 2016, pág. 4.
  53. ^ Diouf y otros, 2010, pág. 66.
  54. ^ Cohen y Rohou 2010, pág. 1.
  55. ^ Diouf y otros, 2010, pág. 72.
  56. ^ Bouchez, Darté y Rastello 2007a, pág. 1.
  57. ^ Poletto y Sarkar 1999, pág. 901-910.
  58. ^ Blackburn y otros. 2006, pág. 169.
  59. ^ Flajolet, Raoult y Vuillemin 1979.

Fuentes

  • Ahn, Minwook; Paek, Yunheung (2009). "Técnicas de coalescencia de registros para arquitectura de registros heterogéneos con cribado 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). "Desbordamiento óptimo para máquinas CISC con pocos registros". 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 . Apuntes de clase en informática. Vol. 4382. págs. 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 derrame mediante el derrame de la región 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.S2CID16952747  .​
  • 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). "Los puntos de referencia de DaCapo". Actas de la 21.ª conferencia anual ACM SIGPLAN sobre sistemas, lenguajes y aplicaciones de programación orientada a objetos - OOPSLA '06 . pág. 169. doi :10.1145/1167473.1167488. ISBN : 978-0-84-0-33723-0-1 978-1595933485.S2CID 9255051  .
  • Libro, Ronald V. (diciembre de 1975). "Karp Richard M.. Reducibilidad entre problemas combinatorios. Complejidad de los cálculos informáticos, Actas de un simposio sobre la complejidad de los cálculos informáticos, celebrado del 20 al 22 de marzo de 1972 en el IBM Thomas J. Watson Center, Yorktown Heights, Nueva York, editado por Miller Raymond E. y Thatcher James W., Plenum Press, Nueva York y Londres 1972, págs. 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. . Apuntes de clase en informática. Vol. 4382. págs. 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 fusión de registros". Simposio internacional sobre generación y optimización de código (CGO'07) . pp. 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). "Desbordamiento de registros y división de rango en tiempo real para programas en formato SSA". Construcción de compiladores . Notas de clase en informática. Vol. 5501. págs. 174–189. CiteSeerX  10.1.1.219.5318 . doi :10.1007/978-3-642-00722-4_13. ISBN . 978-3-642-00721-7. ISSN  0302-9743.
  • Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). "Rematerialización". Avisos SIGPLAN de la ACM . 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 . Apuntes de clase en informática. Vol. 3923. págs. 124–138. doi :10.1007/11688839_12. ISBN 978-3-540-33050-9. ISSN  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". Lenguajes informáticos . 6 (1): 47–57. doi :10.1016/0096-0551(81)90048-5. ISSN  0096-0551.
  • Chaitin, GJ (1982). "Asignación de registros y derrames 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.ID S2C  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 2018 sobre generación y optimización de código - CGO 2018 . págs. 352–364. doi :10.1145/3168806. ISBN 9781450356176. Número de identificación del sujeto  3367270.
  • Cohen, Albert; Rohou, Erven (2010). "Virtualización de procesadores y compilación dividida para sistemas integrados multinúcleo heterogéneos". Actas de la 47.ª Conferencia de Automatización del Diseño sobre DAC '10 . pág. 102. CiteSeerX  10.1.1.470.9701 . doi :10.1145/1837274.1837303. ISBN. 9781450300025.S2CID14314078  .​
  • 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ág. 25. doi :10.1145/2038698.2038706. ISBN 9781450307130.S2CID8296742  .​
  • Diouf, Boubacar; Cohen, Albert; Rastello, Fabrice; Cavazos, John (2010). "Asignación de registros divididos: complejidad lineal sin penalización de rendimiento". Arquitecturas integradas de alto rendimiento y compiladores . Apuntes de clase en informática. Vol. 5952. págs. 66–80. CiteSeerX  10.1.1.229.3988 . doi :10.1007/978-3-642-11515-8_7. ISBN . 978-3-642-11514-1. ISSN  0302-9743.
  • Ditzel, David R.; McLellan, HR (1982). "Registro de asignación gratuito". 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. Número de identificación del sujeto  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. Número de identificación del sujeto  31845919.
  • Eisl, Josef; Marr, Stefan; Würthinger, Thomas; Mössenböck, Hanspeter (2017). "Políticas de asignación de registros de seguimiento" (PDF) . Actas de la 14.ª Conferencia internacional sobre lenguajes gestionados y tiempos de ejecución - Man Lang 2017. págs. 92–104. doi :10.1145/3132190.3132209. ISBN 9781450353403.S2CID1195601  .​
  • Eisl, Josef; Leopoldseder, David; Mössenböck, Hanspeter (2018). "Asignación paralela de registros de seguimiento". Actas de la 15.ª Conferencia internacional sobre lenguajes administrados y tiempos de ejecución - Man Lang '18. págs. 1–7. doi :10.1145/3237009.3237010. ISBN 9781450364249. Número de identificación del sujeto  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 integrados . SCOPES '09. Nueva York, NY, EE. UU.: ACM. pp. 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). "Coalescencia iterada de registros". 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 registros de índice". Revista de la 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 . Apuntes de clase en informática. Vol. 2257. págs. 101–119. doi :10.1007/3-540-45587-6_8. ISBN 978-3-540-43092-6. ISSN  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.S2CID17598675  .​
  • Mössenböck, Hanspeter; Pfeiffer, Michael (2002). "Asignación de registros de escaneo lineal en el contexto de la forma SSA y restricciones de registro". Construcción de compiladores . Notas de clase en informática. Vol. 2304. págs. 229–246. doi :10.1007/3-540-45937-5_17. ISBN 978-3-540-43369-9. ISSN  0302-9743.
  • Nickerson, Brian R. (1990). "Asignación de registros de coloración de grafos para procesadores con operandos multiregistro". ACM SIGPLAN Notices . 25 (6): 40–52. doi :10.1145/93548.93552. ISSN  0362-1340.
  • Paleczny, Michael; Vick, Christopher; Click, Cliff (2001). "El compilador de servidor Java HotSpot". Actas del Simposio de investigación y tecnología de la máquina virtual Java (JVM01) . Monterey, California, EE. UU., págs. 1–12. CiteSeerX  10.1.1.106.1919 .
  • Park, Jinpyo; Moon, Soo-Mook (2004). "Coalescencia de registros optimistas". 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 registros de barrido 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 reorientables para arquitecturas irregulares". Software y compiladores para sistemas embebidos . Apuntes de clase en informática. Vol. 2826. págs. 240–254. CiteSeerX  10.1.1.6.6186 . doi :10.1007/978-3-540-39920-9_17. ISBN . 978-3-540-20145-8. ISSN  0302-9743.
  • Smith, Michael D.; Ramsey, Norman; Holloway, Glenn (2004). "Un algoritmo generalizado para la asignación de registros de 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 barrido 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 barrido 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 registros de escaneo 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  .
  • Un tutorial sobre programación entera
  • 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 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.
  • VV.AA. "Diseño de compiladores basados ​​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
Obtenido de "https://es.wikipedia.org/w/index.php?title=Asignación_de_registros&oldid=1235984312"