stringtranslate.com

Asignación de registros

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/ procedimiento completo ( asignación de registros globales ) o a través de límites de funciones atravesados ​​a través de un gráfico de llamadas ( asignación de registros interprocedurales ). 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


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 puede haber más variables 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 recuperar más rápido si utiliza registros en lugar de memoria. Sin embargo, el número de registros es limitado. Por lo tanto, cuando el compilador traduce 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 "activas") al mismo tiempo, por lo que, durante la vida útil de un programa, un registro determinado puede usarse para contener diferentes variables. Sin embargo, dos variables en uso al mismo tiempo no se pueden asignar al mismo registro sin dañar 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 "derramar" los registros. [4] Durante la vida útil de un programa, una variable se puede dividir y almacenar 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 lento. 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 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 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 un origen y destino de una moveinstrucción siempre que sea posible. Esto es especialmente importante si el compilador utiliza una representación intermedia , como un formulario estático de asignación única (SSA). En particular, cuando SSA no está completamente optimizado, puede generar moveinstrucciones adicionales artificialmente.

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, registros internos o externos. Si la variable se va a almacenar en registros, entonces el asignador debe determinar en qué registros 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 centrales 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, en lugar de uno. Esto ocurre en el enfoque de área viva dividida.
Derramar
Esta acción consiste en almacenar una variable en la memoria en lugar de registros. [9]
Asignación
Esta acción consiste en asignar un registro a una variable. [10]
Fusionándose
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 activa en 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.

Registros Intel 386

Problemas comunes planteados 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:

alias
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 uso general que también se pueden utilizar 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 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 comúnmente se pasan en R3-R10 y el valor de retorno se pasa en R3. [12]
NP-Problema
Chaitín et al. demostró que la asignación de registros es un problema NP-completo . Reducen el problema de coloración de gráficos al problema de asignación de registros al mostrar que para un gráfico arbitrario, se puede construir un programa de modo 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 la coloración de gráficos es un problema NP-difícil y la asignación de registros está en NP, esto demuestra que el problema es NP-completo. [13]

Técnicas de asignación de registros

La asignación de registros puede ocurrir a través de 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 ramas, se cree 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 resulta ser [ se necesita aclaración ] una operación que requiere 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 color 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 activos ( 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 en vivo simultáneamente en al menos un punto del programa. La asignación de registros luego se reduce al problema de coloración del gráfico en el que se asignan colores (registros) a los nodos de manera que dos nodos conectados por un borde no reciban 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 se pueden asignar al mismo registro. [20]

Principio

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

Asignador de registros basado en coloración de gráficos iterativos de Chaitin et al.
  1. Renumerar : descubra información de alcance en vivo en el programa fuente.
  2. Construir : construye el gráfico de interferencia.
  3. Fusionarse : fusiona los rangos activos de variables que no interfieren relacionadas mediante instrucciones de copia.
  4. Costo del derrame : calcule el costo del derrame 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 orden 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 : asignar un registro a cada variable.

Inconvenientes y mejoras adicionales.

La asignación de colores de gráficos tiene tres inconvenientes principales. En primer lugar, 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 coloración mínimo es de hecho un problema NP-completo. [21] En segundo lugar, a menos que se utilice la división del rango en vivo, las variables desalojadas se derraman por todas partes: las instrucciones de la tienda 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 variable. En tercer lugar, una variable que no se derrama se mantiene en el mismo registro durante toda su vida. [22]

Por otro lado, 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, varios 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 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 activos. [24] La formulación tradicional de asignación de registros de 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 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. Básicamente, además de los requisitos de no interferencia, dos variables sólo pueden fusionarse si su fusión no causa más derrames. Briggs y cols. introduce una segunda mejora en 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 que está 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 de vida, representado como un intervalo. Una vez que se han determinado los rangos reales de todas las variables, los intervalos se recorren cronológicamente. Aunque este recorrido podría ayudar a identificar variables cuyos rangos activos interfieren, no se construye ningún gráfico de interferencia y las variables se asignan de forma codiciosa. [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 dedicado a la generación del código. Normalmente, los enfoques estándar de coloración de gráficos 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 del cliente Hotspot , V8 , Jikes RVM , [5] y Android Runtime (ART). [30] El compilador del servidor Hotspot utiliza colores 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:

Asignación de registro de escaneo lineal activo ← {} para cada intervalo en vivo i , en orden creciente del punto de inicio, haga ExpireOldIntervals(i) si longitud (activa) = R entonces Derrame en el intervalo (i) demás registrarse[i] ← un registro eliminado del grupo de registros gratuitos agregue i a activo, ordenado por punto final crecienteExpireOldIntervals(i)  para cada intervalo j  en activo, en orden de aumento del punto final ,  si el punto final [j] ≥ punto de inicio [i] , luego  regrese y elimine j del activo agregue registro [j] al grupo de registros gratuitosDerrame en el intervalo (i) derrame ← último intervalo en activo si punto final[derrame] > punto final[i] entonces registrar[i] ← registrar[derramar] ubicación[derrame] ← nueva ubicación de la pila eliminar el derrame de activo agregue i a activo, ordenado por punto final creciente ubicación[i] ← nueva ubicación de la pila

Inconvenientes y mejoras adicionales.

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

Alcance en vivo más corto con enfoque SSA

Muchos otros trabajos de investigación siguieron al 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. [35] [36] 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 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 dividir un rango, no es necesario dividir 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 agujeros de vida útil. [37] En primer lugar, se reduce el tiempo dedicado al análisis del gráfico de flujo de datos, destinado a construir los intervalos de vida útil, principalmente porque las variables son únicas. [38] En consecuencia, produce intervalos de vida más cortos, porque cada nueva asignación corresponde a un nuevo intervalo de vida. [39] [40] Para evitar intervalos de modelado y agujeros de vida, Rogers mostró una simplificación llamada conjuntos activos futuros que eliminó con éxito intervalos para el 80% de las instrucciones. [41]

Rematerialización

Fusionándose

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 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 se vuelve innecesaria. [42]

La fusión podría 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 gráficos es cuando se fusionan dos nodos, 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, lo que conduce a mejorar la colorabilidad general del gráfico de interferencia. [43]

Hay varias heurísticas fusionadas disponibles: [44]

Fusión agresiva
Fue introducido por primera vez por el asignador de registros original de Chaitin. Esta heurística tiene como objetivo fusionar cualquier nodo relacionado con la copia que no interfiera. [45] Desde la perspectiva de la eliminación de copias, esta heurística tiene los mejores resultados. [46] Por otro lado, la fusión agresiva podría afectar la colorabilidad del gráfico de inferencia. [43]
Unión conservadora
Utiliza principalmente la misma heurística que la fusión agresiva, pero fusiona movimientos si, y sólo si, no compromete la colorabilidad del gráfico de interferencia. [47]
Fusión iterada
elimina un movimiento particular a la vez, manteniendo la colorabilidad del gráfico. [48]
Fusionándose 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. [49]

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 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 necesita. para ser utilizado. 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 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 gráfico de flujo de control determinado. Luego infiere un conjunto de "rastros" (es decir, segmentos de código) en los que el punto de fusión se ignora en favor de la rama más utilizada. Luego, el asignador procesa cada seguimiento 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 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 heurístico se realiza en línea. [24] Del mismo modo, B. Diouf et al. propuso una técnica de asignación que se basa tanto en comportamientos en línea como fuera de línea, es decir, compilación estática y dinámica. [53] [54] Durante la etapa fuera de línea, primero se recopila un conjunto de derrames óptimo utilizando la programación lineal entera . Luego, los rangos vivos se anotan utilizando el compressAnnotationalgoritmo que se basa en el conjunto de derrames óptimo previamente identificado. La asignación de registros se realiza posteriormente durante la fase online, en base a los datos recogidos en la fase offline. [55]

En 2007, Bouchez et al. También sugirió dividir la asignación del registro en diferentes etapas, teniendo una etapa dedicada al vertido 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 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 del 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 vida son métricas relevantes para comparar las diferentes técnicas. [57]

Una vez que se han elegido las métricas relevantes, el código al 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 desea abordar. Los artículos más recientes sobre la asignación de registros utilizan especialmente el conjunto de pruebas Dacapo. [58]

Ver también

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 col. 2016, pág. 1.
  6. ^ "Números de comparación de latencia en computadora/red". 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. ^ 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 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 y col. 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, pag. 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 y Click 2001, pág. 1.
  32. ^ Poletto y Sarkar 1999, pág. 899.
  33. ^ Eisl y col. 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, pag. 90.
  43. ^ ab Ahn y Paek 2009, pág. 7.
  44. ^ Parque y Luna 2004, pag. 736.
  45. ^ Chaitin 1982, pag. 99.
  46. ^ Parque y Luna 2004, pag. 738.
  47. ^ Briggs, Cooper y Torczon 1994, pág. 433.
  48. ^ George y Appel 1996, pág. 212.
  49. ^ Parque y Luna 2004, pag. 741.
  50. ^ Eisl y col. 2017, pág. 11.
  51. ^ Cavazos, Moss y O'Boyle 2006, pág. 124-127.
  52. ^ Eisl y col. 2016, pág. 4.
  53. ^ Diouf y col. 2010, pág. 66.
  54. ^ Cohen y Rohou 2010, pag. 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 col. 2006, pág. 169.
  59. ^ Flajolet, Raoult y Vuillemin 1979.

Fuentes

enlaces externos