Optimización de registros

El uso optimizado de los registros de una máquina es responsabilidad del compilador cuya misión es mantener en registros ( y no en memoria) los operandos necesarios para el mayor número posible de cálculos, minimizando las operaciones de carga/almacenamiento de registros que requieren el acceso a memoria

El proceso de asignación óptima de registros se realiza en dos fase:

1) Diseño del grafo de interferencias entre las variables del programa: nodos: las variables arcos: entre variables que están activas simultáneamente en el programa

2) Coloreado del grafo

Se intenta colorear el grafo con n colores, siendo n el nº de registros disponibles en la máquina. A los nodos no coloreados se le asignan posiciones de memoria y se utilizan instrucciones de carga/almacenamiento.

Como se sabe este es un problema NP-duro que requiere el uso de heurísticas muy elaboradas para acortar el tiempo de proceso.

Ejemplo

Asignación de las 6 variables (V1,…V6) que aparecen en el segmento de programa de la siguiente figura, en la que se indica de forma gráfica sus interferencias. Se disponen de 3 registros en la máquina: R1, R2 y R3.

1) Se construye el grafo de interferencias tal como se muestra en la siguiente figura.

2) Se colorea el grafo asignando a los nodos los tres registros de manera que no se asigne el mismo registro a dos nodos conectados por un arco en el grafo.

3) Los nodos que no pueden ser asignados a registros se asignan a memoria (V7)

Fuente: Estructura de Computadores, Facultad de Informática, UCM