En la optimización del compilador , la asignación de registros es el proceso de asignar una gran cantidad de variables de programa de destino a una pequeña cantidad de registros de la CPU .
La asignación de registros puede ocurrir en un bloque básico ( asignación de registro local ), en una función / procedimiento completo ( asignación de registro global ), o a través de los límites de funciones atravesados a través de un gráfico de llamada ( asignación de registro interprocedimiento ). Cuando se realiza por función / procedimiento, la convención de llamada puede requerir la inserción de guardar / restaurar alrededor de cada sitio de llamada .
Contexto
Principio
Arquitectura | 32 bits | 64 bits |
---|---|---|
BRAZO | 15 | 31 |
Intel x86 | 8 | dieciséis |
MIPS | 32 | 32 |
POTENCIA / PowerPC | 32 | 32 |
RISC-V | 16/32 | 32 |
SPARC | 31 | 31 |
En muchos lenguajes de programación , el programador puede utilizar cualquier número de variables . La computadora puede leer y escribir registros rápidamente en la CPU , por lo que el programa de computadora se ejecuta más rápido cuando más variables pueden estar en los registros de la CPU. [1] Además, a veces el código de acceso a los registros es más compacto, por lo que el código es más pequeño y se puede obtener 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 al 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 "en vivo") al mismo tiempo, por lo que, durante la vida útil de un programa, un registro dado puede usarse para contener diferentes variables. Sin embargo, dos variables en uso al mismo tiempo no se pueden asignar al mismo registro sin corromper una de las variables. Si no hay suficientes registros para contener todas las variables, algunas variables se pueden mover hacia y desde la RAM . Este proceso se llama "derramar" los registros. [4] Durante la vida útil de un programa, una variable se puede derramar y almacenar en registros: esta variable se considera entonces como "dividida". [5] Acceder a la RAM es significativamente más lento que acceder a los registros [6], por lo que un programa compilado se ejecuta más lento. Por lo tanto, un compilador de optimización 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 derrames y recargas; está definido por Braun et al. como "el número de variables activas simultáneamente en una instrucción". [7]
Además, algunos diseños de computadora 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 destino de una move
instrucción siempre que sea posible. Esto es especialmente importante si el compilador utiliza una representación intermedia , como el formulario estático de asignación única (SSA). En particular, cuando SSA no está completamente optimizado, puede generar move
instrucciones adicionales de forma artificial .
Componentes de la asignación de registros
La asignación de registros consiste, por 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, entonces el asignador debe determinar en qué registro (s) se almacenará esta variable. Finalmente, otro desafío es determinar la duración durante la cual una variable debe permanecer en la misma ubicación.
Un asignador de registros, sin tener en cuenta 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 incrementar el número de instrucciones de movimiento entre registros, es decir, hacer que una variable viva en diferentes registros durante su vida, en lugar de uno. Esto ocurre en el enfoque de rango en vivo dividido.
- Derramar
- Esta acción consiste en almacenar una variable en memoria en lugar de registros. [9]
- Asignación
- Esta acción consiste en asignar un registro a una variable. [10]
- Coalescente
- 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 en vivo a través de diferentes métodos y almacenándola en un registro durante toda su vida. [9]
Muchos enfoques de asignación de registros se optimizan para una o más categorías específicas de acciones.
Problemas comunes que surgen 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 llama aliasing. Por ejemplo, la arquitectura x86 tiene cuatro registros de 32 bits de propósito general que también se pueden usar 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 la asignación de algunas variables 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]
- NP-Problema
- Chaitin y col. mostró que la asignación de registros es un problema NP-completo . Reducen el problema de coloración del gráfico al problema de asignación de registros al mostrar que para un gráfico arbitrario, se puede construir un programa de manera que la asignación de registros para el programa (con registros que representan nodos y registros de máquina que representan colores disponibles) sería un color para el gráfico original. Como Graph Coloring es un problema NP-Hard y la asignación de registros está en NP, esto prueba la NP-completitud del problema. [13]
Registrar técnicas de asignación
La asignación de registros puede ocurrir en 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 revela [ aclaración necesaria ] 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 en toda la unidad de compilación (un método o procedimiento, por ejemplo). [dieciséis]
Asignación de coloración de gráficos
La asignación de colores de gráficos es el enfoque predominante para resolver la asignación de registros. [17] [18] Fue propuesto por primera vez por Chaitin et al. [4] En este enfoque, los nodos en el gráfico representan rangos en vivo ( variables , temporales , registros virtuales / simbólicos) que son candidatos para la asignación de registros. Los bordes conectan rangos en vivo que interfieren, es decir, rangos en vivo que están simultáneamente en vivo en al menos un punto del programa. La asignación de registros se reduce entonces al problema de coloración del gráfico en el que los colores (registros) se asignan a los nodos de manera que dos nodos conectados por un borde no reciben el mismo color. [19]
Utilizando el análisis de vida , se puede construir un gráfico de interferencia. El gráfico de interferencia, que es un gráfico no dirigido donde los nodos son las variables del programa, se utiliza para modelar qué variables no pueden asignarse al mismo registro. [20]
Principio
Las principales fases en un asignador de registros de coloración de gráficos de estilo Chaitin son: [18]
- Renumerar : descubre información de rango en vivo en el programa fuente.
- Construir : construye el gráfico de interferencia.
- Coalesce : fusiona los rangos en vivo de las variables que no interfieren relacionadas con las instrucciones de copia.
- Costo del derrame : calcule el costo del derrame de cada variable. Esto evalúa el impacto de mapear una variable a la memoria en la velocidad del programa final.
- Simplificar : construir un orden de los nodos en el gráfico de inferencias.
- Código de derrame : inserte instrucciones de derrame, es decir, cargas y almacenes para conmutar valores entre registros y memoria.
- Seleccionar : asigna un registro a cada variable.
Inconvenientes y mejoras adicionales
La asignación de colores de gráficos tiene tres inconvenientes principales. Primero, se basa en la coloración de gráficos, que es un problema NP-completo , para decidir qué variables se derraman. Encontrar un gráfico de color mínimo es de hecho un problema NP-completo. [21] En segundo lugar, a menos que se use la división de rango en vivo, las variables desalojadas se derraman en todas partes: las instrucciones de almacenamiento (respectivamente carga) se insertan lo antes (respectivamente tarde) como sea posible, es decir, justo después (respectivamente antes) de las definiciones de variable (respectivamente usos) . En tercer lugar, una variable que no se derrama se mantiene en el mismo registro durante toda su vida. [22]
Por otro lado, un solo nombre de registro puede aparecer en múltiples clases de registro, donde una clase es un conjunto de nombres de registro que son intercambiables en un rol particular. Entonces, varios nombres de registros pueden ser alias de un solo registro de hardware. [23] Finalmente, la coloración de gráficos es una técnica agresiva para asignar registros, pero es computacionalmente costosa debido al uso del gráfico de interferencia, que puede tener un tamaño en el peor de los casos que es cuadrático en el número de rangos en vivo. [24] La formulación tradicional de asignación de registros de coloración de gráficos asume implícitamente un solo 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 bancos de registros múltiples. [25]
Briggs et al encontraron una mejora posterior del enfoque de coloración de gráficos al estilo Chaitin: se llama fusión conservadora. Esta mejora agrega un criterio para decidir cuándo se pueden fusionar dos rangos en vivo. Principalmente, además de los requisitos de no interferencia, dos variables solo pueden fusionarse si su fusión no provocará más derrames. Briggs y col. introduce una segunda mejora a las obras de Chaitin que es la coloración sesgada. La coloración sesgada intenta asignar el mismo color en la coloración del gráfico al rango en vivo relacionado con la copia. [18]
Escaneo lineal
El escaneo lineal es otro enfoque de asignación de registros global. 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 calculado los rangos en vivo de todas las variables, los intervalos se recorren cronológicamente. Aunque este recorrido podría ayudar a identificar las variables cuyos rangos en vivo interfieren, no se está construyendo un gráfico de interferencia y las variables se asignan de manera codiciosa. [24]
La motivación de este enfoque es la velocidad; no en términos de tiempo de ejecución del código generado, sino en términos de tiempo dedicado a la generación de código. Normalmente, los enfoques de coloración de gráficos estándar producen un 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, la exploración lineal es el enfoque que se utiliza actualmente en varios compiladores JIT, como el compilador Hotspot , V8 y Jikes RVM . [5]
Pseudocódigo
Esto describe el algoritmo propuesto por primera vez por Poletto et al, [30] donde:
- R es el número de registros disponibles.
- activa es la lista, ordenada en orden de punto final creciente, de intervalos en vivo que se superponen al punto actual y se colocan en registros.
LinearScanRegisterAllocation activo ← {} para cada intervalo en vivo i , en orden de punto de inicio creciente hacer ExpireOldIntervals (i) si longitud (activo) = R entonces SpillAtInterval (i) demás registro [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 de punto final creciente, haga si el punto final [j] ≥ punto de inicio [i] luego devuelve eliminar j de activo agregar registro [j] al grupo de registros gratuitosSpillAtInterval (i) derrame ← último intervalo en activo si punto final [derrame]> punto final [i] entonces registrar [i] ← registrar [derrame] ubicación [derrame] ← nueva ubicación de la pila eliminar el derrame de activo agregar i a activo, ordenado aumentando el punto final else location [i] ← nueva ubicación de pila
Inconvenientes y mejoras adicionales
Sin embargo, la exploración lineal presenta dos grandes inconvenientes. Primero, debido a su aspecto codicioso, no tiene en cuenta los huecos de por vida, es decir, "rangos donde no se necesita el valor de la variable". [31] [32] Además, una variable derramada permanecerá derramada durante toda su vida.
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 con el objetivo de generar código de mejor calidad. [33] [34] En este enfoque, las variables derramadas tienen la oportunidad de almacenarse más tarde en un registro mediante el uso de una heurística diferente a la utilizada en el algoritmo estándar de exploración lineal. En lugar de utilizar intervalos en vivo, el algoritmo se basa en rangos en vivo, lo que significa que si se necesita derramar un rango, no es necesario derramar todos los demás rangos correspondientes a esta variable.
La asignación de exploración lineal también se adaptó para aprovechar la forma SSA : las propiedades de esta representación intermedia se utilizan para simplificar el algoritmo de asignación. [35] En primer lugar, se reduce el tiempo empleado en el análisis del gráfico de flujo de datos, destinado a construir los intervalos de vida útil, principalmente porque las variables son únicas. [36] En consecuencia, produce intervalos en vivo más cortos, porque cada nueva asignación corresponde a un nuevo intervalo en vivo. [37] [38] Para evitar intervalos de modelado y agujeros de vitalidad, Rogers mostró una simplificación llamada conjuntos activos en el futuro que eliminó con éxito los intervalos para el 80% de las instrucciones. [39]
Rematerialización
El problema de la asignación óptima de registros es NP-completo. Como consecuencia, los compiladores emplean técnicas heurísticas para aproximar su solución.
Chaitin y col. discutir varias ideas para mejorar la calidad del código de derrames. Señalan que ciertos valores se pueden volver a calcular en una sola instrucción y que el operando requerido siempre estará disponible para el cálculo. Ellos llaman a estos valores excepcionales "nunca muertos" y notan que dichos valores deben recalcularse en lugar de derramarse y recargarse. Además, señalan que una copia no fusionada de un valor nunca muerto se puede eliminar volviéndola a calcular directamente en el registro deseado. [40]
Estas técnicas se denominan rematerialización. En la práctica, las oportunidades de rematerialización incluyen:
- cargas inmediatas de constantes enteras y, en algunas máquinas, constantes de punto flotante,
- calcular un desplazamiento constante desde el puntero de la trama o el área de datos estáticos, y
- carga de punteros de marco no locales desde una pantalla. [40]
Briggs y Al amplían el trabajo de Chaitin para aprovechar las oportunidades de rematerialización para rangos en vivo complejos y de múltiples valores. Descubrieron que cada valor debe etiquetarse con suficiente información para permitir que el asignador lo maneje correctamente. El enfoque de Briggs es el siguiente: primero, divida cada rango en vivo en los valores de sus componentes, luego propague etiquetas de rematerialización a cada valor y forme nuevos rangos en vivo a partir de valores conectados que tengan etiquetas idénticas. [40]
Coalescente
En el contexto de la asignación de registros, la fusión es el acto de fusionar operaciones de movimiento de variable a variable mediante la asignación de esas dos variables a la misma ubicación. La operación de fusión tiene lugar 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 sea innecesaria. [41]
La fusión puede tener impactos tanto positivos como negativos en la colorabilidad del gráfico de interferencia. [9] Por ejemplo, un impacto negativo que la fusión podría tener en la colorabilidad de la inferencia de grafos es cuando dos nodos se fusionan, ya que el nodo resultante tendrá una unión de los bordes de los que se fusionan. [9] Un impacto positivo de la fusión en la colorabilidad del gráfico de inferencia es, por ejemplo, cuando un nodo interfiere con la fusión de ambos nodos, el grado del nodo se reduce en uno que conduce a mejorar la colorabilidad general del gráfico de interferencia. [42]
Hay varias heurísticas combinadas disponibles: [43]
- Fusión agresiva
- fue introducido por primera vez por el asignador de registros originales de Chaitin. Esta heurística tiene como objetivo fusionar cualquier nodo relacionado con la copia que no interfiera. [44] Desde la perspectiva de la eliminación de copias, esta heurística tiene los mejores resultados. [45] Por otro lado, la fusión agresiva podría afectar la colorabilidad del gráfico de inferencia. [42]
- Fusión conservadora
- utiliza principalmente la misma heurística que la fusión agresiva, pero fusiona movimientos si, y solo si, no compromete la colorabilidad del gráfico de interferencia. [46]
- Fusión iterada
- elimina un movimiento en particular a la vez, mientras mantiene la colorabilidad del gráfico. [47]
- Fusión optimista
- se basa en una fusión agresiva, pero si la colorabilidad del gráfico de inferencia se ve comprometida, renuncia a la menor cantidad de movimientos posible. [48]
Enfoques mixtos
Asignación híbrida
Algunos otros enfoques de asignación de registros no se limitan a una técnica para optimizar el uso del registro. Cavazos et.al, por ejemplo, propusieron una solución en la que es posible utilizar tanto el escaneo lineal como los algoritmos de coloración de gráficos. [49] En este enfoque, la elección entre una u otra solución se determina dinámicamente: primero, se usa 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 determine qué algoritmo de asignación necesita para ser utilizado. La función heurística se utiliza luego en tiempo de ejecución; a la luz del comportamiento del código, el asignador puede elegir entre uno de los dos algoritmos disponibles. [50]
La asignación de registros de seguimiento es un enfoque reciente desarrollado por Eisl et al. [3] [5] Esta técnica maneja la asignación localmente: se basa en datos de perfiles dinámicos para determinar qué ramas serán las más utilizadas en un diagrama de flujo de control dado. Luego infiere un conjunto de "trazas" (es decir, segmentos de código) en el que el punto de fusión se ignora a favor de la rama más utilizada. A continuación, 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. [51]
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 se puede considerar dividida porque la primera etapa de construcción heurística se realiza fuera de línea y el uso heurístico se realiza en línea. [24] Del mismo modo, B. Diouf et al. propuso una técnica de asignación basada tanto en comportamientos fuera de línea como en línea, a saber, compilación estática y dinámica. [52] [53] Durante la etapa fuera de línea, primero se recopila un conjunto de derrames óptimo mediante la programación lineal entera . Luego, los rangos en vivo se anotan utilizando el compressAnnotation
algoritmo que se basa en el conjunto de derrames óptimo identificado previamente. La asignación de registros se realiza posteriormente durante la etapa en línea, en función de los datos recopilados en la fase fuera de línea. [54]
En 2007, Bouchez et al sugirieron también dividir la asignación del registro en diferentes etapas, teniendo una etapa dedicada al derrame y otra dedicada a la coloración y fusión. [55]
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 la otra. La asignación de registros normalmente tiene que lidiar con una compensación entre la calidad del código, es decir, el 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 asignación de registro optimizada. Desde esta perspectiva, el tiempo de ejecución del código generado y el tiempo dedicado al análisis de la vida son métricas relevantes para comparar las diferentes técnicas. [56]
Una vez que se han elegido las métricas relevantes, el código en el que se aplicarán las métricas debe estar disponible y ser relevante para el problema, ya sea reflejando el comportamiento de la aplicación del mundo real o siendo relevante para el problema particular que el algoritmo quiere abordar. Los artículos más recientes sobre la asignación de registros utilizan especialmente la suite de referencia Dacapo. [57]
Ver también
- Número de Strahler , el número mínimo de registros necesarios para evaluar un árbol de expresión. [58]
- Registro (palabra clave) , la sugerencia en C y C ++ para que una variable se coloque en un registro.
Referencias
- ^ Ditzel y McLellan 1982 , p. 48.
- ^ Runeson y Nyström 2003 , p. 242.
- ^ a b Eisl y col. 2016 , pág. 14: 1.
- ^ a b Chaitin y col. 1981 , pág. 47.
- ^ a b c Eisl y col. 2016 , pág. 1.
- ^ "Números de comparación de latencia en computadora / red" . blog.morizyun.com . Consultado el 8 de enero de 2019 .
- ^ Braun y Hack 2009 , p. 174.
- ^ Koes y Goldstein 2009 , p. 21.
- ↑ a b c d Bouchez, Darte y Rastello 2007 , p. 103. Error sfn: múltiples objetivos (2 ×): CITEREFBouchezDarteRastello2007 ( ayuda )
- ^ Colombet, Brandner y Darte 2011 , p. 26.
- ^ "Manual del desarrollador de software de arquitecturas Intel® 64 e IA-32, sección 3.4.1" (PDF) .
- ^ "Convenciones de llamada a funciones PowerPC de 32 bits" .
- ^ Bouchez, Darte y Rastello 2006 , p. 4.
- ^ Horwitz y col. 1966 , pág. 43.
- ^ Farach y Liberatore 1998 , p. 566.
- ^ Eisl y col. 2017 , pág. 92.
- ^ Eisl, Leopoldseder y Mössenböck 2018 , p. 1.
- ↑ a b c Briggs, Cooper y Torczon 1992 , p. 316.
- ^ Poletto y Sarkar 1999 , p. 896.
- ^ Runeson y Nyström 2003 , p. 241.
- ^ Libro 1975 , p. 618–619.
- ^ Colombet, Brandner y Darte 2011 , p. 1.
- ^ Smith, Ramsey y Holloway 2004 , p. 277.
- ↑ a b c Cavazos, Moss & O'Boyle , 2006 , p. 124.
- ^ Runeson y Nyström 2003 , p. 240.
- ^ Poletto y Sarkar 1999 , p. 895.
- ^ Poletto y Sarkar 1999 , p. 902.
- ^ Wimmer y Mössenböck , 2005 , p. 132.
- ^ Johansson y Sagonas 2002 , p. 102.
- ^ Poletto y Sarkar 1999 , p. 899.
- ^ Eisl y col. 2016 , pág. 2.
- ^ Traub, Holloway y Smith 1998 , p. 143.
- ^ Traub, Holloway y Smith 1998 , p. 141.
- ^ Poletto y Sarkar 1999 , p. 897.
- ^ Wimmer y Franz 2010 , p. 170.
- ^ Mössenböck y Pfeiffer 2002 , p. 234.
- ^ Mössenböck y Pfeiffer 2002 , p. 233.
- ^ Mössenböck y Pfeiffer 2002 , p. 229.
- ^ Rogers 2020 .
- ↑ a b c Briggs, Cooper y Torczon 1992 , p. 313.
- ^ Chaitin 1982 , p. 90.
- ↑ a b Ahn y Paek , 2009 , p. 7.
- ↑ Park & Moon , 2004 , p. 736.
- ^ Chaitin 1982 , p. 99.
- ↑ Park & Moon , 2004 , p. 738.
- ^ Briggs, Cooper y Torczon 1994 , p. 433.
- ^ George y Appel 1996 , p. 212.
- ↑ Park & Moon , 2004 , p. 741.
- ^ Eisl y col. 2017 , pág. 11.
- ^ Cavazos, Moss y O'Boyle , 2006 , p. 124-127.
- ^ Eisl y col. 2016 , pág. 4.
- ^ Diouf y col. 2010 , pág. 66.
- ^ Cohen y Rohou 2010 , p. 1.
- ^ Diouf y col. 2010 , pág. 72.
- ^ Bouchez, Darte y Rastello 2007 , p. 1. Error sfn: múltiples objetivos (2 ×): CITEREFBouchezDarteRastello2007 ( ayuda )
- ^ Poletto y Sarkar 1999 , p. 901-910.
- ^ Blackburn y col. 2006 , pág. 169.
- ^ Flajolet, Raoult y Vuillemin 1979 .
Fuentes
- Ahn, Minwook; Paek, Yunheung (2009). "Registro de técnicas de coalescencia para arquitectura de registro heterogénea con tamizado de copia". Transacciones ACM en sistemas informáticos integrados . 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 (2ª ed.). Addison-Wesley Longman Publishing Co., Inc. ISBN 978-0321486813.
- Appel, Andrew W .; George, Lal (2001). "Derrame ó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, cristiano; Gupta, Rahul; Pandit, Vinayaka; Udupa, Raghavendra (2007). "Asignación óptima de registros bit a bit mediante programación lineal de enteros". Lenguajes y compiladores para computación paralela . Apuntes de conferencias en informática. 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. S2CID 16952747 .
- Blackburn, Stephen M .; Guyer, Samuel Z .; Hirzel, Martin; Hosking, Antonio; Salta, María; 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 . pag. 169. doi : 10.1145 / 1167473.1167488 . ISBN 978-1595933485. S2CID 9255051 .
- Book, Ronald V. (diciembre de 1975). "Karp Richard M .. Reducibilidad entre problemas combinatorios. Complexity of computer computations, Proceedings of a Symposium on the Complexity of Computer Computations, 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 ". El diario de la lógica simbólica . 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é prueba realmente la NP-Completeness Proof de Chaitin et al. O revisando la asignación de registros: por qué y cómo". Asignación de registros: ¿qué hace la prueba NP-Completeness de Chaitin et al. realmente probar? . Apuntes de conferencias en informática. 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 (2007). "Sobre la complejidad de la fusión 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; Darte, Alain; Rastello, Fabrice (2007). "Sobre la complejidad del derrame en todas partes bajo la forma SSA". Avisos ACM SIGPLAN . 42 (7): 103. arXiv : 0710.3642 . doi : 10.1145 / 1273444.1254782 . ISSN 0362-1340 .
- Braun, Matthias; Hack, Sebastián (2009). "Registro de derrames y división de rango vivo para programas en forma de SSA". Construcción del compilador . Apuntes de conferencias en informática. 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 ACM SIGPLAN . 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 gráficos". Transacciones ACM sobre lenguajes y sistemas de programación . 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 del compilador . Apuntes de conferencias en informática. 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). "Registrar asignación a través de colorear". Idiomas informáticos . 6 (1): 47–57. doi : 10.1016 / 0096-0551 (81) 90048-5 . ISSN 0096-0551 .
- Chaitin, GJ (1982). "Registro de asignación y derrame mediante coloración de gráficos". 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 procesador Intel". Actas del Simposio Internacional 2018 sobre Generación y Optimización de Código - 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 en - DAC '10 . pag. 102. CiteSeerX 10.1.1.470.9701 . doi : 10.1145 / 1837274.1837303 . ISBN 9781450300025. S2CID 14314078 .
- Colombet, Quentin; Brandner, Florian; Darte, Alain (2011). "Estudio de derrames óptimos a la luz de SSA". Actas de la 14ª conferencia internacional sobre compiladores, arquitecturas y síntesis para sistemas integrados - CASES '11 . pag. 25. doi : 10.1145 / 2038698.2038706 . ISBN 9781450307130. S2CID 8296742 .
- Diouf, Boubacar; Cohen, Albert; Rastello, Fabrice; Cavazos, John (2010). "Asignación de registro dividido: complejidad lineal sin penalización de rendimiento". Arquitecturas y compiladores integrados de alto rendimiento . Apuntes de conferencias en informática. 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). "Registrar asignación 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; Más sombrío, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016). "Asignación de registros basada en seguimiento en un compilador JIT". Actas de la XIII 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 seguimiento" (PDF) . Actas de la 14th International Conference on Managed Languages and Runtimes - Man Lang 2017 (PDF) . págs. 92-104. doi : 10.1145 / 3132190.3132209 . ISBN 9781450353403. S2CID 1195601 .
- Eisl, Josef; Leopoldseder, David; Mössenböck, Hanspeter (2018). "Asignación de registros de seguimiento en paralelo". Actas de la 15ª Conferencia Internacional sobre lenguajes gestionados y tiempos de ejecución - Man Lang '18 . págs. 1-7. doi : 10.1145 / 3237009.3237010 . ISBN 9781450364249. S2CID 52137887 .
- Koes, David Ryan; Goldstein, Seth Copen (2009). "Asignación de registros deconstruida" . Escrito en Niza, Francia. Actas del XII Taller Internacional sobre Software y Compiladores para Sistemas Embebidos . ALCANCE '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 .: Sociedad de Matemáticas Industriales y Aplicadas. 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", Informática teórica , 9 (1): 99-125, doi : 10.1016 / 0304-3975 (79) 90009-4
- George, Lal; Appel, Andrew W. (1996). "Registro iterado coalescente". Transacciones ACM sobre lenguajes y sistemas de programación . 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 exploración lineal en un compilador Erlang de alto rendimiento". Aspectos prácticos de los lenguajes declarativos . Apuntes de conferencias en informática. 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 REGISTRO ALlocation". Actas de la 24a conferencia ACM / IEEE sobre la conferencia de 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 exploración lineal en el contexto de restricciones de registro y formulario SSA". Construcción del compilador . Apuntes de conferencias en informática. 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 gráficos para procesadores con operandos de múltiples registros". Avisos ACM SIGPLAN . 25 (6): 40–52. doi : 10.1145 / 93548.93552 . ISSN 0362-1340 .
- Park, Jinpyo; Moon, Soo-Mook (2004). "Registro optimista coalescente". Transacciones ACM sobre lenguajes y sistemas de programación . 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 exploración lineal". Transacciones ACM sobre lenguajes y sistemas de programación . 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 gráficos retardables para arquitecturas irregulares". Software y compiladores para sistemas embebidos . Apuntes de conferencias en informática. 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 gráficos". Avisos ACM SIGPLAN . 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 escaneo lineal". Avisos ACM SIGPLAN . 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 intervalo optimizada en un asignador de registro de exploración lineal". Actas de la 1ª conferencia internacional ACM / USENIX sobre entornos de ejecución virtual - VEE '05 . pag. 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 formulario SSA". Actas del octavo simposio internacional anual IEEE / ACM sobre generación y optimización de código - CGO '10 . pag. 170. CiteSeerX 10.1.1.162.2590 . doi : 10.1145 / 1772954.1772979 . ISBN 9781605586359. S2CID 1820765 .
enlaces externos
- Un tutorial sobre programación de enteros
- Programación de enteros de conferencias y optimización combinatoria, IPCO
- El taller de optimización combinatoria de Aussois
- Bosscher, Steven; y Novillo, Diego. GCC obtiene un nuevo Optimizer Framework . Un artículo sobre el uso de SSA por parte de GCC y cómo mejora con respecto a los RI más antiguos.
- La bibliografía de la SSA . Amplio catálogo de trabajos de investigación de la SSA.
- Zadeck, F. Kenneth. "El Formulario de Desarrollo de Asignación Única Estática" , diciembre de 2007 charla sobre los orígenes de SSA.
- VV.AA. "Diseño de compilador 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