Asignaciones de registro en la generación de código – Part 1

Los registros son las ubicaciones más rápidas en la jerarquía de la memoria. Pero desafortunadamente, este recurso es limitado. Viene bajo los recursos más limitados del procesador de destino. La asignación de registros es un problema NP-completo. Sin embargo, este problema se puede reducir a la coloración de gráficos para lograr la asignación y la asignación. Por lo tanto, un buen asignador de registros calcula una solución aproximada efectiva para un problema difícil. 
 

Figura – Entrada-Salida 

El asignador de registros determina qué valores residirán en el registro y qué registro contendrá cada uno de esos valores. Toma como entrada un programa con un número arbitrario de registros y produce un programa con un conjunto finito de registros que puede caber en la máquina de destino. (Ver imagen) 

Asignación vs Asignación: 

Asignación: 
asigna un espacio de nombres ilimitado a ese conjunto de registros de la máquina de destino. 

• registro al reg. Modelo: asigna registros virtuales a registros físicos, pero derrama el exceso de cantidad en la memoria.
• Mem. a la memoria Modelo: asigna algún subconjunto de la ubicación de la memoria a un conjunto de nombres que modela el conjunto de registros físicos.

La asignación garantiza que el código se ajuste al registro de la máquina de destino. establecido en cada instrucción. 

Asignación: 
asigna un conjunto de nombres asignado al conjunto de registros físicos de la máquina de destino.  

• Supone que se ha realizado la asignación para que el código encaje en el conjunto de registros físicos.
• No se designan más de ‘k’ valores en los registros, donde ‘k’ es el número. de registros físicos.

La asignación de registros generales es un problema NP-completo:  

• Resuelto en tiempo polinomial, cuando (n° de registros requeridos) <= (n° de registros físicos disponibles).
• Se puede producir una asignación en tiempo lineal utilizando Coloración de gráficos de intervalos.

Asignación y asignación de registro local: 
la asignación dentro de un bloque básico se denomina registro local. Asignación. Dos enfoques para el registro local. asignación: enfoque de arriba hacia abajo y enfoque de abajo hacia arriba. 

El enfoque de arriba hacia abajo es un enfoque simple basado en el ‘recuento de frecuencias’. Identificar los valores que deben mantenerse en los registros y que deben mantenerse en la memoria. 

Algoritmo: 

1. Calcule una prioridad para cada registro virtual.
2. Ordenar los registros en orden de prioridad.
3. Asigne registros en orden de prioridad.
4. Reescribe el código.

Más allá de los bloques individuales:  

• Más complicado porque el flujo de control entra en escena.
• Liveness y Live Ranges: Los rangos en vivo consisten en un conjunto de definiciones y usos que están relacionados entre sí, es decir, ningún registro único puede ser común en tal par de instrucciones/datos.

La siguiente es una forma de averiguar los rangos en vivo en un bloque. Un rango en vivo se representa como un intervalo [i, j], donde i es la definición y j es el último uso. 

Asignación y asignación de registros globales: 
1. El problema principal de un asignador de registros es minimizar el impacto del código de derrame; 

• Tiempo de ejecución del código de derrame.
• Codifique el espacio para la operación de derrame.
• Espacio de datos para valores derramados.

2. La asignación global no puede garantizar una solución óptima para el tiempo de ejecución del código de derrame. 
3. Principales diferencias entre la asignación local y global: 

• La estructura de un rango vivo global es naturalmente más compleja que la local.
• Dentro de un rango vivo global, distintas referencias pueden ejecutarse un número diferente de veces. (Cuando los bloques básicos forman un bucle)

4. Para tomar la decisión sobre la asignación y las asignaciones, el asignador global utiliza principalmente la coloración de gráficos mediante la creación de un gráfico de interferencia. 
5. El asignador de registros luego intenta construir una coloración k para ese gráfico donde ‘k’ es el no. de registros físicos. 

• En caso de que el compilador no pueda construir directamente una coloración k para ese gráfico, modifica el código subyacente derramando algunos valores en la memoria y vuelve a intentarlo.
• Derramar en realidad simplifica ese gráfico, lo que garantiza que el algoritmo se detenga.

6. Global Allocator utiliza varios enfoques, sin embargo, veremos estrategias de asignación de arriba hacia abajo y de abajo hacia arriba. Subproblemas asociados con los enfoques anteriores.  

• Descubriendo las gamas vivas globales.
• Estimación de los costos de derrames.
• Construcción de un gráfico de interferencia.

Descubriendo rangos en vivo globales: 
¿Cómo descubrir el rango en vivo para una variable? 

Figura: descubrimiento de rangos en vivo en un solo bloque 

El diagrama anterior explica todo correctamente. Tomemos el ejemplo de Rarp, se ha inicializado en el punto de programa 1 y su último uso es en el punto de programa 11. Por lo tanto, el rango en vivo de Rarp, es decir, Larp, es [1,11]. Del mismo modo, otros hacen un seguimiento.  

Figura: descubrimiento de rangos en vivo 

Estimación del costo global de derrames: 

• Esencial para tomar una decisión de derrame que incluye: cálculo de direcciones, costo de operación de memoria y frecuencia de ejecución estimada.
• Para obtener beneficios de rendimiento, estos valores derramados se guardan normalmente para los registros de activación.
• Algunos procesadores integrados ofrecen memoria ScratchPad para contener dichos valores derramados.
• Costo de derrame negativo : el almacenamiento de carga consecutivo para una sola dirección debe eliminarse, ya que aumenta la carga y, por lo tanto, incurre en un costo de derrame negativo.
• Costo de derrame infinito : un rango en vivo debe tener un costo de derrame infinito si ningún otro rango en vivo termina entre su definición y su uso.

Gráfico de interferencia e interferencia: 

Figura: Gráfico de interferencia de construcción a partir de rangos en vivo 
 

Del diagrama anterior, se puede observar que el LRA de rango vivo comienza en el primer bloque básico y termina en el último bloque básico. Por lo tanto, compartirá una ventaja con todos los demás rangos en vivo, es decir, Lrb, Lrc, Lrd. Sin embargo, Lrb, Lrc, Lrd no se superponen con ningún otro rango en vivo, excepto Lra, por lo que solo comparten una ventaja con Lra. 

Creación de un asignador: 

• Tenga en cuenta que el hallazgo de un gráfico k-coloreable es un problema NP-completo, por lo que necesitamos una aproximación para esto.
• Intente dividir el rango en vivo en algunos fragmentos no triviales (los más utilizados).

Coloración de arriba hacia abajo : 

1. Intenta colorear el rango en vivo en un orden determinado por algunas funciones de clasificación, es decir, basado en la prioridad.
2. Si no hay ningún color disponible para un rango en vivo, el asignador invoca el derrame o la división para manejar los que no tienen color.
3. Los rangos en vivo que tienen k o más vecinos se denominan Nodes restringidos y son difíciles de manejar.
4. Los Nodes sin restricciones son comparativamente fáciles de manejar.
5. Manejo de derrames: cuando no se encuentra color para algunos rangos en vivo, es necesario realizar un derrame, pero esta puede no ser una solución definitiva, por supuesto.
6. División de rango en vivo: para los no coloreados, divida el rango en vivo en sub-rangos, que pueden tener menos interferencias que el original para que al menos algunos de ellos puedan colorearse.

La idea de Chaitin: 

• Elija un Node arbitrario de (grado < k) y colóquelo en la pila.
• Elimina ese Node y todos sus bordes del gráfico. (Esto puede disminuir el grado de algunos otros Nodes y causar que algunos Nodes más tengan un grado = k, algún Node tiene que ser derramado.
• Si no es necesario derramar ningún vértice, extraiga sucesivamente los vértices de la pila y coloréelos con un color que no usen los vecinos. (reutilizar colores en la medida de lo posible).

Copias fusionadas para reducir el grado: 
el compilador puede usar el gráfico de interferencia para fusionar dos rangos en vivo. Entonces, al fusionarse, ¿qué tipo de beneficios puede obtener? 

Figura: rangos en vivo fusionados 

Comparación del asignador Top-Down y Bottom-Up: 

• El asignador de arriba hacia abajo podría adoptar la filosofía de ‘derramar e iterar’ que se usa en los de abajo hacia arriba.
• ‘Spill and iterate’ intercambia tiempo de compilación adicional por una asignación que, potencialmente, utiliza menos código de vertido.
• Top-Down utiliza la clasificación de prioridad para ordenar todos los Nodes restringidos. (Sin embargo, colorea los Nodes sin restricciones en un orden arbitrario)
• Bottom-up construye un orden en el que la mayoría de los Nodes están coloreados en un gráfico donde no están restringidos.

Figura: rangos en vivo fusionados