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 anterior | Volver al principio del trabajo | Página siguiente  |