Memory Memory Registers ALU Control Stack Código Generado Heap Objetos Arrays locales (parámetros)
Registers Arquitectura load/store Todas las operaciones se ejecutan en registros Necesitamos mover datos de/a memoria a/de registros
Importante para rendimiento Limitados en número ALU Control Memory Registers
Otras Interacciones Otras operaciones Input/Output Operaciones Privilegiadas / seguras Manejo de hardware especial TLBs, Caches etc.
La mayoría via system calls Codificadas a mano en assembler El compilador las puede tratar como una llamada normal a una función ALU Control Memory Registers
Las máquinas entienden… location data
0x4009b0: 3c1c0fc0 0x4009b4: 279c7640 0x4009b8: 0399e021 0x4009bc: 8f998044 0x4009c0: 27bdffe0 0x4009c4: afbf001c 0x4009c8: afbc0018 0x4009cc: 0320f809 0x4009d0: 2404000a 0x4009d4: 8fbf001c 0x4009d8: 8fbc0018 0x4009dc: 27bd0020 0x4009e0: 03e00008 0x4009e4: 00001025
Las máquinas entienden… location data assembly instruction main: [test.c: 3] 0x4009b0: 3c1c0fc0 lui gp,0xfc0 [test.c: 3] 0x4009b4: 279c7640 addiu gp,gp,30272 [test.c: 3] 0x4009b8: 0399e021 addu gp,gp,t9 [test.c: 3] 0x4009bc: 8f998044 lw t9,-32700(gp) [test.c: 3] 0x4009c0: 27bdffe0 addiu sp,sp,-32 [test.c: 3] 0x4009c4: afbf001c sw ra,28(sp) [test.c: 3] 0x4009c8: afbc0018 sw gp,24(sp) [test.c: 3] 0x4009cc: 0320f809 jalr ra,t9 [test.c: 3] 0x4009d0: 2404000a li a0,10 [test.c: 3] 0x4009d4: 8fbf001c lw ra,28(sp) [test.c: 3] 0x4009d8: 8fbc0018 lw gp,24(sp) [test.c: 3] 0x4009dc: 27bd0020 addiu sp,sp,32 [test.c: 3] 0x4009e0: 03e00008 jr ra [test.c: 3] 0x4009e4: 00001025 move v0,zero
Representación Intermedia (Gp:) Programa (character stream)
Generador de Código (Gp:) Código en Assembler
High-level IR Analizador Léxico (Scanner) Analizador Sintáctico (Parser) (Gp:) Token Stream
Arbol de Parseo Low-level IR Generador de Código Intermedio
Representación Intermedia (Gp:) Programa (character stream)
Generador de Código (Gp:) Código en Assembler
High-level IR Analizador Léxico (Scanner) Analizador Sintáctico (Parser) (Gp:) Token Stream
Arbol de Parseo Low-level IR Generador de Código Intermedio Assembler & linker Binario Ejecutable Procesador
Lenguaje Ensamblador Ventajas Simplifica la generación de código debido al uso de instrucciones simbólicas y nombres simbólicos Capa de abstracción lógica Las arquitecturas pueden ser descritas por un lenguaje ensamblador ? podemos modificar la implementación Instrucciones de macro assembler Desventajas Proceso adicional de ensamblaje y linking
Lenguaje Ensamblador Lenguaje de Máquina Reposicionable (object modules) Todas las posiciones (direcciones) representadas por símbolos Mapeadas a direcciones de memoria en tiempo de linking y loading Flexibilidad de compilación separada Lenguaje de Máquina Absoluto Direcciones hard-coded Implementación simple y directa Inflexible – difícil de recargar el código generado
Ejemplo de Assembler item: .word 1 .text fib: subu $sp, 40 sw $31, 28($sp) sw $4, 40($sp) sw $16, 20($sp) .frame $sp, 40, $31 # 7 if(n == 0) return 0; lw $14, 40($sp) bne $14, 0, $32 move $2, $0 b lab2 lab1: lw $15, 40($sp) bne $15, 1, $33 li $2, 1 b lab1
Compatibilidad Necesitamos Manejar Procedimientos múltiples Llamadas a librerías Código compilado por otros compiladores, escrito en lenguajes distintos, assembler escrito a mano Convenciones de llamado Layout de memoria Registros Stack
Layout de Memoria Inicio del Stack Manejo del Heap free lists Posición de inicio en el segmento de texto Stack Text segment Heap Objects Arrays locals (parameters)
0x7fffffff 0x400000 Reserved
Disciplinas de paso de parámetros Muchos métodos distintos Llamada por referencia Llamada por valor Llamada por valor-resultado ¿Cómo pasamos los parámetros? Por el stack Por los registros O una combinación
Pregunta: ¿Cuáles son las ventajas/desventajas de que: El callee guarde los registros? El caller guarde los registros? ¿Qué registros deben ser usados por el caller y callee si la mitad es guardada por el caller y la otra mitad es guardada por el callee? Caller-saved t0 – t9 Calliee-saved s0-s7 21
Registros En una llamada a procedimiento los temporales: Son guardados por el caller Son guardados por el callee Alguna combinación de ambos
Stack Guarda los parámetros y las variables locales Cada invocación obtiene una nueva copia Caller tiene que guardar Cualquier registro caller-saved que tiene un valor Cualesquiera parámetros pasados Return address (de cuando se hizo el branch) Callee tiene que guardar Dirección anterior del stack pointer Cualquier registro callee-saved que use 23
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area fp sp Dirección del n-ésimo argumento es -(n-4)*4*$fp Variables locales son constantes positivas de $fp
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area fp sp Al llamar un nuevo procedimiento
24
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area fp sp Al llamar un nuevo procedimiento, el caller:
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area Caller saved registers fp sp Al llamar un nuevo procedimiento, el caller: push de cualquier t0-t9 que tenga un valor importante al stack
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area Caller saved registers arguments
fp sp Al llamar un nuevo procedimiento, el caller: push de cualquier t0-t9 que tenga un valor importante al stack poner argumentos 1-4 en registros a0-a3 push del resto de los argumentos al stack
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area Caller saved registers arguments
fp sp Al llamar un nuevo procedimiento, el caller: push de cualquier t0-t9 que tenga un valor importante al stack poner argumentos 1-4 en registros a0-a3 push del resto de los argumentos al stack hacer un jal o jalr
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area Caller saved registers arguments
fp (Gp:) sp
En el procedimiento, el calliee al principio: 25
return address old frame pointer Stack Local variables Calliee saved registers Stack temporaries … argument 5 argument 4
Dynamic area Caller saved registers arguments
fp En el procedimiento, el calliee al principio : copiar $sp a $fp (Gp:) sp
Programa Ejemplo class auxmath { int sum3d(int ax, int ay, int az, int bx, int by, int bz) { int dx, dy, dz; if(ax > ay) dx = ax – bx; else dx = bx – ax; … retrun dx + dy + dz; } }
Programa Ejemplo class auxmath { int sum3d(int ax, int ay, int az, int bx, int by, int bz) { int dx, dy, dz; if(ax > ay) dx = ax – bx; else dx = bx – ax; … retrun dx + dy + dz; } }
… int px, py, pz; … auxmath am; am.sum3d(px, py, pz, 0, 0, 0);
Programa Ejemplo class auxmath { int sum3d(int ax, int ay, int az, int bx, int by, int bz) { int dx, dy, dz; if(ax > ay) dx = ax – bx; else dx = bx – ax; … retrun dx + dy + dz; } }
… int px, py, pz; px = 10; py = 20; pz = 30; auxmath am; am.sum3d(px, py, pz, 0, 1, -1); Dynamic area Caller saved registers Argument 7: bz (-1) fp Argument 6: by (1) Argument 5: bx (0)
Programa Ejemplo class auxmath { int sum3d(int ax, int ay, int az, int bx, int by, int bz) { int dx, dy, dz; if(ax > ay) dx = ax – bx; else dx = bx – ax; … retrun dx + dy + dz; } }
… int px, py, pz; px = 10; py = 20; pz = 30; auxmath am; am.sum3d(px, py, pz, 0, 1, -1); return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0)
Programa Ejemplo class auxmath { int sum3d(int ax, int ay, int az, int bx, int by, int bz) { int dx, dy, dz; if(ax > ay) dx = ax – bx; else dx = bx – ax; … retrun dx + dy + dz; } }
… int px, py, pz; px = 10; py = 20; pz = 30; auxmath am; am.sum3d(px, py, pz, 0, 1, -1); return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0) Local variable dx (??) Local variable dy (??) Local variable dz (??)
Creación de Expresiones Algoritmo ingenuo de generación de código x = y op z Seleccionar un registro Rsrc1 (digamos $t0) para cargar el valor y Generar instrucción para copiar, si y está: En otro registro (digamos $t7) add $t0, $t7, zero Es constante (digamos 1024) li $t0, 1024 En memoria (digamos que $t7 apunta a y) lw $t0, $t7 En una dirección simbólica (digamos lab1) la $t0, lab1 Seleccionar registro Rsrc2 (digamos $t1) y cargar el valor z Seleccionar registro Rdest (digamos $t2) para guardar x Hacer la operación (digamos and) and $t2, $t1, $t0
Programa Ejemplo class auxmath { int sum3d(int ax, int ay, int az, int bx, int by, int bz) { int dx, dy, dz; if(ax > ay) dx = ax – bx;
sp return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0) Local variable dx (??) Local variable dy (??) Local variable dz (??)
Programa Ejemplo class auxmath { int sum3d(int ax, int ay, int az, int bx, int by, int bz) { int dx, dy, dz; if(ax > ay) dx = ax – bx;
sp return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0) Local variable dx (??) Local variable dy (??) Local variable dz (??) add $t0, $a1, zero lw $t1, 0($fp) sub $t2, $t0, $t1 sw $t2, -12($fp) address src1 src2 dest
Cuidado Los temporales son limitados Cuándo el árbol es grande, 18 registros temporales pueden ser insuficientes ? asignar espacio en el stack No hay instrucción de máquina Puede ser que haya que expandir la operación intermedia a múltiples operaciones de máquina Muy ineficiente Muchas copias, sumas con cero, etc. No se preocupen, vamos a arreglarlas en la optimización Mantengan el generador de código muy muy simple
Generación de control de flujo Aplanar la estructura del control Usar un template Poner etiquetas únicas para puntos donde el control se une (join points) Ahora generamos el código apropiado
Template para condicionales if (test) true_body else false_body
boper …, lab_true
j lab_end lab_true:
lab_end: 38
Programa Ejemplo
if(ax > bx) dx = ax – bx; else dx = bx – ax;
return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0) Local variable dx (??) Local variable dy (??) Local variable dz (??)
address src1 src2 dest
boper …, …, lab0
j lab1 lab0:
lab1:
Programa Ejemplo
if(ax > bx) dx = ax – bx; else dx = bx – ax;
return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0) Local variable dx (??) Local variable dy (??) Local variable dz (??)
address src1 src2 dest
add $t0, $a1, zero lw $t1, 0($fp) bgt $t0, $t1, lab0
j lab1 lab0:
lab1:
Programa Ejemplo
if(ax > bx) dx = ax – bx; else dx = bx – ax;
return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0) Local variable dx (??) Local variable dy (??) Local variable dz (??)
address src1 src2 dest
add $t0, $a1, zero lw $t1, 0($fp) bgt $t0, $t1, lab0 lw $t0, 0($fp) add $t1, $a1, zero sub $t2, $t0, $t1 sw $t2, -12($fp) j lab1 lab0:
lab1:
Programa Ejemplo
if(ax > bx) dx = ax – bx; else dx = bx – ax;
return address old frame pointer Dynamic area Caller saved registers Argument 7: bz (-1) fp sp Argument 6: by (1) Argument 5: bx (0) Local variable dx (??) Local variable dy (??) Local variable dz (??)
address src1 src2 dest
add $t0, $a1, zero lw $t1, 0($fp) bgt $t0, $t1, lab0 lw $t0, 0($fp) add $t1, $a1, zero sub $t2, $t0, $t1 sw $t2, -12($fp) j lab1 lab0: add $t0, $a1, zero lw $t1, 0($fp) sub $t2, $t0, $t1 sw $t2, -12($fp) lab1:
Template para ciclos while while (test) body
Template para ciclos while while (test) body
lab_cont:
boper …, lab_body j lab_end lab_
j lab_cont lab_end:
Template para ciclos while while (test) body
lab_cont:
boper …, lab_body j lab_end lab_
j lab_cont lab_end: Una template optimizada 43 (Gp:) lab_cont:
boper …, lab_end
j lab_cont lab_end:
| Página siguiente |