Registrar asignación

La distribución de registros en el proceso de compilación [1] es el mapeo de un conjunto de un gran número de variables de un fragmento de un programa de computadora (registros virtuales de una representación intermedia) sobre, por regla general, un pequeño conjunto de microprocesadores físicos . registros La asignación de registros se puede realizar en un solo bloque base ( asignación de registros locales ) o en todo el procedimiento ( asignación de registros globales ).

Por lo general, los programas de computadora tienen que trabajar con grandes cantidades de datos, pero la mayoría de los microprocesadores solo admiten operaciones en un número fijo de pequeñas "celdas" llamadas registros. Algunos procesadores permiten el uso de operandos almacenados en la memoria , pero acceder a los registros es mucho más rápido que acceder a la memoria (aunque el área de memoria especificada se puede almacenar en caché ).

Problemas

El problema de asignación de registros es NP-completo [2] [3] . Por lo general, la cantidad de variables en un programa supera con creces los registros físicos disponibles, por lo que algunas variables deben almacenarse en la pila local. Los accesos a la memoria se pueden minimizar almacenando allí las variables que se usan con menos frecuencia, pero determinar qué variables se usan menos no siempre es fácil.

También vale la pena señalar que algunos registros a menudo tienen un propósito de sistema o servicio y su uso es limitado.

Asignación de registros globales

Como la mayoría de las otras optimizaciones, la asignación de registros se basa en el uso de algún análisis. En este caso, lo más frecuente es el análisis de la vida útil de las variables y el análisis del flujo de datos.

La coloración del gráfico de incompatibilidad propuesta por el matemático Gregory Khaitin se considera un algoritmo tradicional de asignación de registros .

Cada variable (registro simbólico) corresponde a un nodo del gráfico . Si los tiempos de vida de las variables se cruzan, los nodos correspondientes están conectados por un arco. El gráfico debe colorearse con colores (donde corresponde al número de registros físicos disponibles) de tal manera que ningún par de nodos vecinos tenga el mismo color.

El grado de un nodo gráfico es el número de sus vecinos. Si el grado de un nodo gráfico es menor que , siempre es posible encontrar un color para él que no esté asignado a ninguno de los vecinos. Si todos los nodos tienen grado mayor que , una de las variables se almacena en memoria, dividiéndose en varios nodos de menor grado.

Hasta que la gráfica G se pueda colorear con los colores R Elimine iterativamente todos los nodos del gráfico de grado < R, empujándolos a la pila Si se han eliminado todos los nodos del gráfico, el gráfico se puede colorear con colores R Extraiga el nodo N de la pila y agréguelo al gráfico asignándole un color De lo contrario, el gráfico G no se puede colorear con colores R Simplifique G seleccionando un nodo para almacenar en la memoria y dividiéndolo en múltiples nodos (el nodo a almacenar en memoria se elige heurísticamente)

Preston Briggs propuso modificar el algoritmo de Khaitin [4] postergando el almacenamiento de la variable en la memoria hasta que se asignen los colores a los nodos del gráfico. Para algunos gráficos no coloreables , esto evita almacenar variables en la memoria. Por ejemplo, un cuadrado con nodos en los vértices se puede colorear con colores, mientras que el grado de todos sus nodos es igual a dos, y el algoritmo de Khaitin se verá obligado a almacenar una de las variables en la memoria.


Notas

  1. ↑ CONOCE EL INTUITO | Conferencia | Elección de Instrucciones en Generación de Código . Consultado el 28 de noviembre de 2017. Archivado desde el original el 28 de julio de 2021.
  2. ↑ Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins y Peter W. Markstein. "Registrar la asignación a través de la coloración". Lenguajes informáticos, 6:47-57, 1981  .
  3. ↑ Fernando Magno Quintão Pereira, Jens Palsberg, "Register Allocation after Classical SSA Elimination is NP-complete"  , http://pike.cs.ucla.edu/~palsberg/paper/fossacs06.pdf Archivado desde el 4 de marzo de 2016 en Wayback Máquina
  4. ↑ Preston Briggs, Keith D. Cooper, Ken Kennedy, Linda Torczon. "Colorear la heurística para la asignación de registros". Avisos ACM SIGPLAN, Volumen 24, Edición 7, 275-284, 1989  .

Enlaces