compiladores asignación de registros. 2 resumen ¿qué es asignación de registros? un asignador de...

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