La asignación de registros es un problema fundamental en la optimización de compiladores, crucial para el rendimiento del código generado. Su objetivo es mapear un número ilimitado de registros virtuales (vregs) a un conjunto limitado de registros físicos de la CPU, minimizando los accesos a memoria (spills). Este problema es NP-hard, lo que obliga a los compiladores a emplear heurísticas. La evolución de asignadores de escaneo lineal a enfoques basados en bin-packing por prioridad representa un avance en la búsqueda de un equilibrio entre la complejidad del algoritmo y la calidad del código resultante, especialmente en arquitecturas con convenciones de llamada complejas como x86-64. La relevancia actual reside en la necesidad continua de optimizar el rendimiento de las aplicaciones, donde la eficiencia en el uso de registros puede tener un impacto significativo en la latencia y el throughput.
El problema se agudiza con la creciente complejidad de los programas y la demanda de compiladores que generen código de alto rendimiento sin sacrificar excesivamente los tiempos de compilación. Un asignador de registros eficiente no solo reduce el número de instrucciones y accesos a memoria, sino que también puede simplificar el backend del compilador, como se demuestra en este caso al reducir la base de código del asignador en un 58% mientras mejora la calidad del código en un 3.6% (instrucciones) y un 22% (stores).
Arquitectura del Sistema
El asignador de registros opera en cinco fases secuenciales por función. Primero, la fase de 'Live Ranges' determina los intervalos de vida de cada vreg, representados como segmentos de slots (pares [start, end]) y calcula un peso de 'spill' basado en la profundidad del bucle. Se utiliza un enfoque de worklist para calcular los 'live-out sets' por vreg, evitando el costo de 'bloques * vregs'. Segundo, 'Fixed Registers' identifica los registros físicos ocupados por la convención de llamada o instrucciones específicas, marcándolos en máscaras de bits por slot. Tercero, 'Coalescing' fusiona vregs conectados por una instrucción de copia si sus rangos de vida no se solapan, eliminando la copia. Se priorizan las copias en bucles más profundos y se usa una estructura Union-Find para gestionar los 'bundles' (grupos de vregs fusionados).
Cuarto, 'Picking Registers' asigna un registro físico a cada 'bundle' en orden de prioridad decreciente (peso / sqrt(longitud)). Se consideran 'hints' de registros físicos y se priorizan los registros 'caller-saved' antes que los 'callee-saved'. La asignación es 'greedy': una vez que un 'bundle' obtiene un registro, lo mantiene durante toda su vida útil, sin desalojo ni división de rangos. Finalmente, 'Spilling' asigna slots de pila a los 'bundles' que no pudieron obtener un registro. El código se reescribe para cargar operandos 'spilled' en registros temporales (r10/r11) antes de su uso y almacenar resultados 'spilled' después de su definición. Se optimizan las copias entre registros y slots de pila, y se eliminan cargas/almacenamientos redundantes mediante un 'peephole pass' posterior.
Flujo de Asignación de Registros por Función
- 1 Live Ranges Calcular intervalos de vida de vregs y pesos de spill.
- 2 Fixed Registers Marcar registros físicos ocupados por convenciones/instrucciones.
- 3 Coalescing Fusionar vregs conectados por copias si no hay solapamiento.
- 4 Picking Registers Asignar registros físicos a bundles por prioridad (greedy).
- 5 Spilling & Rewrite Asignar slots de pila a bundles sin registro y reescribir código.
| Capa | Tecnología | Justificación |
|---|---|---|
| compute | x86-64 | Arquitectura de CPU objetivo para la generación de código y asignación de registros. |
| data-processing | Intermediate Representation (IR) | Representación interna del código fuente antes de la generación de código máquina, donde operan los vregs. |
| data-processing | Union-Find | Estructura de datos utilizada para gestionar la fusión de vregs en 'bundles' durante la fase de coalescing. |
Trade-offs
Ganancias
- ▲ Calidad del código (menos instrucciones, menos stores)
- ▲ Tiempo de compilación
- ▲ Complejidad del código del asignador
Costes
- △ Óptimo global en asignación de registros (debido a la ausencia de desalojo/splitting)
Fundamentos Teóricos
El problema de la asignación de registros está intrínsecamente ligado al problema de coloreado de grafos, como demostraron Chaitin et al. en su trabajo seminal. En este contexto, cada vreg es un nodo y una arista existe entre dos nodos si sus rangos de vida se solapan (interfieren). El objetivo es asignar un 'color' (registro físico) a cada nodo de tal manera que nodos adyacentes tengan colores diferentes, utilizando el menor número de colores posible. Dado que el coloreado de grafos es NP-completo, los asignadores de registros prácticos recurren a heurísticas.
El asignador de escaneo lineal original, mencionado en el artículo, se basa en los principios descritos por Poletto y Sarkar. El nuevo asignador de bin-packing por prioridad comparte similitudes con el asignador 'greedy' de LLVM 3.0, aunque simplificado al omitir características como el desalojo ('eviction') y la división de rangos ('splitting'). La idea de asignar prioridades basadas en el costo de 'spill' (peso) y la longitud del rango de vida es una heurística común para guiar la asignación en un contexto de recursos limitados, buscando minimizar el impacto de los 'spills' en el rendimiento.