compiladores asignación de registros. 2 resumen ¿qué es asignación de registros? un asignador de...
TRANSCRIPT
Compiladores
Asignación de Registros
2
Resumen
• ¿Qué es asignación de registros?• Un asignador de registros simple• Webs• Grafos de interferencia• Coloreando grafos• Splitting• Más optimizaciones
3
Asignación de Registros
• Usar de forma óptima uno de los recursos más críticos del procesador
• Asignación de variables (hasta ahora en memoria) a registros de hardware– Pseudo registros: número ilimitado de registros
virtuales, es espacio se asigna normalmente en el stack
– Registros reales: conjunto de registros disponibles en el procesador
4
Importancia de Asignación de Registros
• Sólo hay un número finito y pequeño de registros disponibles– Usualmente 32 registros enteros y 32 de punto flotante– Algunos de esos registros tienen usos fijos (r0, ra, sp, fp)
• El acceso a registros es mucho más rápido que el acceso a memoria– La diferencia es mucho más grande en procesadores modernos
• Menos instrucciones cuándo usamos registros– La mayoría de instrucciones son registro-a-registro– Se necesitan instrucciones adicionales para llevar los datos de
memoria a un registro
5
Importancia de Asignación de Registros
• Permite otras optimizaciones– CSE asume que las variables están en registros
• Asignación de registros tiene un impacto directo en el rendimiento– Afecta casi todo statement del programa
– Elimina instrucciones caras de memoria
– El # de instrucciones baja debido a la manipulación directa de registros (no hay necesidad de instrucciones load/store)
– ¡Es probablemente la optimización que tiene el mayor impacto!
6
¿Qué se puede poner en un registro?
• Variables escalares• Constantes grandes• Algunos elementos de arreglos y campos de
records
• El conjunto de registros depende del tipo de datos– floating-point en registros fp– fixed-point en registros enteros
7
Resumen
• ¿Qué es asignación de registros?• Un asignador de registros simple• Webs• Grafos de interferencia• Coloreando grafos• Splitting• Más optimizaciones
8
Un asignador de registros simple “siempre o nunca”
• Estimar el beneficio de poner cada variable en un registro para un bloque básico en particular– costo(var, bb) = número de usos y definiciones de la
variable.
• Estimar el beneficio general– CostoTotal(var) = costo(var, bb)*freq(bb) para todo bb
• Assignar las R variables de mayor beneficio a registros
9
Ejemplo
def zuse z
def xdef yuse xuse xuse y
use z
10
Ejemplo
def zuse z
def xdef yuse xuse xuse y
use z
• Costo para bloques básicos– costo(x, bb1) = 0– costo(x, bb2) = 3– costo(x, bb3) = 0– costo(y, bb1) = 0– costo(y, bb2) = 2– costo(y, bb3) = 0– costo(z, bb1) = 2– costo(z, bb2) = 0– costo(z, bb3) = 1
11
Ejemplo
def zuse z
def xdef yuse xuse xuse y
use z
• Frecuencia– freq(bb1) = 1– freq(bb2) = 100– freq(bb3) = 1
• Costo para bloques básicos– costo(x, bb1) = 0– costo(x, bb2) = 3– costo(x, bb3) = 0– costo(y, bb1) = 0– costo(y, bb2) = 2– costo(y, bb3) = 0– costo(z, bb1) = 2– costo(z, bb2) = 0– costo(z, bb3) = 1
12
Ejemplo
def zuse z
def xdef yuse xuse xuse y
use z
• Costo para bloques básicos– costo(x, bb1) = 0– costo(x, bb2) = 3– costo(x, bb3) = 0– costo(y, bb1) = 0– costo(y, bb2) = 2– costo(y, bb3) = 0– costo(z, bb1) = 2– costo(z, bb2) = 0– costo(z, bb3) = 1
• Costo total– CostoTotal(x) = 0*1 + 3*100 + 0*1 = 300– CostoTotal(y) = 0*1 + 2*100 + 0*1 = 200– CostoTotal(z) = 3*1 + 0*100 + 1*1 = 4
• Frecuencia– freq(bb1) = 1– freq(bb2) = 100– freq(bb3) = 1
13
Ejemplo
def zuse z
def xdef yuse xuse xuse y
use z
• Costo total– CostoTotal(x) = 300– CostoTotal(y) = 200– CostoTotal(z) = 4
• Asumimos que hay 2 registros disponibles– Asignamos x e y a registros
14
Problema 1
• Asignación es igual que antes– x e y van en registros, z no
• Las variables ocupan el registro incluso cuándo no lo necesitan
• Todas (x, y, & z) pueden tener registros
def zuse z
def xdef yuse xuse xuse y
def zuse z
15
Problema 1
def zuse z
def xdef yuse xuse xuse y
def zuse z
x y z
• Asignación es igual que antes– x e y van en registros, z no
• Las variables ocupan el registro incluso cuándo no lo necesitan
• Todas (x, y, & z) pueden tener registros
16
Problema 1
def zuse z
def xdef yuse xuse xuse y
def zuse z
x y z
r1r2
r1
r1
• Asignación es igual que antes– x e y van en registros, z no
• Las variables ocupan el registro incluso cuándo no lo necesitan
• Todas (x, y, & z) pueden tener registros
17
Problema 2
• Incluso las variables que no se interfieren no pueden compartir registros
18
Problema 2
• Incluso las variables que no se interfieren no pueden compartir registros
{ int x; … } { int y; … }
19
Problema 2
• Incluso las variables que no se interfieren no pueden compartir registros
• x e y pueden usar el mismo registro
{ int x; … } { int y; … }
20
Problema 3
• Diferentes fases del programa se comportan de distinta forma
• Un registro disponible– registro para x en el primer loop– registro para y en el segundo loop– no nos importa mucho el resto
• Tenemos que “derramar” (spill)– todo o nada no va a funcionar
def & use xuse & use y
use & def x
use & def y
use xuse y
21
Lo que un asignador inteligente debe hacer
• Determinar rangos para cada variable en los que haya beneficio al usar un registro (webs)
• Determinar cuáles de estos rangos se traslapan (interference)
• Encontrar los beneficios de mantener cada variable en un registro (spill cost)
• Decidir cuáles webs obtienen un registro (allocation)• Dividir webs si es necesario (spilling and splitting)• Asignar registros reales a webs (assignment)• Generar código incluyendo spills (code generation)
22
Resumen
• ¿Qué es asignación de registros?• Un asignador de registros simple• Webs• Grafos de interferencia• Coloreando grafos• Splitting• Más optimizaciones
23
Webs• Lo que debe ser memorizado es el valor• dividir accesos a variables en múltiples webs
– Todas las definiciones que llegan a un uso en mismo web
– Todos los usos que usan el valor definido en mismo web
– Dividir la variable en rangos de vida
• Implementación: Usar cadenas DU– Una cadena du conecta la definición a todos los usos que
alcanza esta definición
– Un web combina las cadenas du que contienen un uso común
24
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
25
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
26
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
27
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
28
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
29
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
30
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
31
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
s1
s2
s3
s4
32
Webs
• En dos webs de la misma variable:– Ningún uso en un web va a usar nunca un valor definido por
el otro web– Por lo tanto, ningún valor necesita ser llevado entre webs– Cada web puede ser tratada independientemente
• Web es usado como la unidad de asignación de registros– Si se le asigna un registro a un web, todos los usos y
definiciones dentro del web no necesitan load ni store de memoria
– Diferentes webs pueden ser asignados a diferentes registros o uno a un registro y otro a memoria
33
Resumen
• ¿Qué es asignación de registros?• Un asignador de registros simple• Webs• Grafos de interferencia• Coloreando grafos• Splitting• Más optimizaciones
34
Interferencia
• Dos webs interfieren si el rango de vida de dos webs se traslapa en el tiempo
• Webs que no se interfieren pueden ser asignados al mismo registro
35
Ejemplo
def y
def xuse y
def xdef y
use xdef x
use x
use xuse y
s1
s2
s3
s4
36
Ejemplo
def y
def xuse y
use xdef x
use x
s1
s2
s3
s4
def xdef y
use xuse y
37
Ejemplo
def y
def xuse y
use xdef x
use x
s1
s2
s3
s4
def xdef y
use xuse y
Webs s1 y s2 interfierenWebs s2 y s3 interfieren
38
Grafo de Interferencia
• Representación de webs y sus interferencias– Nodos son webs– Existe una arista entre nodos si estos interfieren
s1 s2
s3 s4
39
Ejemplo
def y
def xuse y
use xdef x
use x
s1
s2
s3
s4
def xdef y
use xuse y
s1 s2
s3 s4
40
Ejemplo
def y
def xuse y
use xdef x
use x
s1
s2
s3
s4
def xdef y
use xuse y
Webs s1 y s2 interfierenWebs s2 y s3 interfieren
s1 s2
s3 s4
41
Resumen
• ¿Qué es asignación de registros?• Un asignador de registros simple• Webs• Grafos de interferencia• Coloreando grafos• Splitting• Más optimizaciones
42
Asignación de Registros usando Graph Coloring
• A cada web se le asigna un registro– cada nodo obtiene un registro (color)
• Si dos webs interfieren no pueden usar el mismo registro– si dos nodos tienen una arista entre ellos, no pueden
tener el mismo color
s1 s2
s3 s4
43
Graph Coloring
• ¿Cuál es el número mínimo de colores con el que se pueden colorerar los nodos del grafo tal que cualesquiera nodos conectados mediante una arista no tengan el mismo color?
• Problema clásico en teoría de grafos
44
Ejemplo de Graph Coloring
45
Ejemplo de Graph Coloring
• 1 Color
46
Ejemplo de Graph Coloring
47
Ejemplo de Graph Coloring
• 2 Colores
48
Ejemplo de Graph Coloring
49
Ejemplo de Graph Coloring
• Todavía 2 Colores
50
Ejemplo de Graph Coloring
51
Ejemplo de Graph Coloring
• 3 Colores
52
Heuristicas para Colorear Registros
• Coloreando un grafo con N colores
• Si grado < N (grado de un nodo = # de aristas)– Nodo siempre puede ser coloreado– Luego de colorear el resto de los nodos va a quedar
al menos un color para colorear el nodo actual
• Si grado >= N– Puede que todavía sea coloreable con N colores– Solución exacta es NP complete
53
Heuristicas para Colorear Registros
• Eliminar nodos que tengan grado < N– meter los nodos eliminados a un stack
• Si todos los nodos tienen grado >= N– encontrar un nodo para “spill” (no hay color para ese nodo)
– eliminar ese nodo
• Cuando esté vacío, comenzamos a colorerar– sacar un nodo del stack
– asignarle un color que sea diferente de sus nodos conectados (como el grado < N, debe existir un color)
54
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
55
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
56
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4
57
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2
58
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2s1
59
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2s1s3
60
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2s1s3
61
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2s1s3
62
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2s1
63
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2s1
64
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2
65
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s2
66
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4
67
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4
68
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
69
Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
70
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
71
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4
72
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4
73
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s3
74
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s3s2
75
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s3s2
76
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s3s2
77
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s3
78
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4s3
79
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4
80
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
s4
81
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
82
Otro Ejemplo de Colorear
s1 s2
s3 s4
s0
N = 3
83
Resumen
• ¿Qué es asignación de registros?• Un asignador de registros simple• Webs• Grafos de interferencia• Coloreando grafos• Splitting• Más optimizaciones
84
Spilling y Splitting
• Cuándo el grafo no es N-coloreable• Seleccionamos un web para “spill”
– Encontrar el web de menor costo de spill
– Los usos y definiciones de ese web son leidos y escritos a memoria
• Dividir el web (Split)– Dividir un web en múltiples webs para que haya menos
interferencias en el grafo volviendolo N-coloreable
– Derramar (spill) el valor a memoria y cargarlo de regreso en los puntos donde se dividió el web
85
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
86
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
x y
z
87
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
x y
z
¿2-coloreable?
88
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
x y
z
¿2-coloreable?¡No!
89
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
90
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
91
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
x y
z2
z1
92
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
x y
z2
z1
¿2-coloreable?
93
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
x y
z2
z1
¿2-coloreable?¡Sí!
94
Ejemplo de Splitting
def zuse z
def xdef yuse xuse xuse y
use z
x y z
r1r2
r1
r1
x y
z2
z1
¿2-coloreable?¡Sí!
95
Ejemplo de Splittingdef zuse zstr z
def xdef yuse xuse xuse y
ld zuse z
x y z
r1r2
r1
r1
x y
z2
z1
¿2-coloreable?¡Sí!
96
Splitting
• Identificar un punto en el programa donde el grafo no es R-coloreable (punto donde # de webs > N)– Elegir un web que no es usado en el bloque
envolvente más grande al rededor de ese punto en el programa
– Dividir ese web (split)– Rehacer el grafo de interferencia– Tratar de re colorear el grafo
97
Costo y beneficio de splitting
• Costo de dividir un nodo– Proporcional al número de veces que la arista dividida tenga que
ser cruzada dinámicamente
– Estimable mediante anidamiento de loops
• Beneficios– Aumenta la colorabilidad de los nodos con los que interfiere el
web que dividimos
– Puede aproximarse por su grado en el grafo de interferencia
• Heuristica ambiciosa– Elegir el rango de vida con la mayor razón beneficio/costo para
dividir
98
Resumen
• ¿Qué es asignación de registros?• Un asignador de registros simple• Webs• Grafos de interferencia• Coloreando grafos• Splitting• Más optimizaciones
99
Otras Optimizaciones
• Register coalescing
• Register targeting (pre-coloring)
• Presplitting of webs
• Interprocedural register allocation
100
Register Coalescing
• Encontrar instrucciones de copia de registros como sj = si
• Si sj y si no interfieren, combinar sus webs
• Pros– similar a copy propagation– reduce el número de instrucciones
• Cons– puede incrementar el grado del nodo combinado– un grafo coloreable se puede volver incoloreable
101
Register Targeting (pre-coloring)
• Algunas variables tienen que estar en registros especiales en momentos determinados– primeros 4 argumentos de una función– valor de retorno
• Pre-colorear esos webs y asociarlos al registro adecuado
• Elimina instrucciones de copia innecesarias
102
Pre-splitting de webs
• Algunos rangos de vida tienen regiones “muertas” muy grandes– Región grande donde la variable no es usada
• Romper los rangos de vida– hay que pagar un pequeño costo de spilling– pero el grafo va ser mucho más fácil de colorear
• Podemos encontrar localidades estratégicas para romperlos– en un punto de llamada (hay que hacer spill de todas formas)– al rededor de un loop grande (reservar registros para valores
usados dentro del loop)
103
Interprocedural register allocation
• Guardar registros en llamdas a procedimientos es caro– especialmente para programas con muchas
funciones pequeñas
• Convenciones de llamado son muy generales e ineficientes
• Customizar las convenciones de llamado por función mediante asignación de registros interprocedural
104
Lecturas
• Ballena– Capítulo 16