Story Transcript
ELO311 Estructuras de Computadores Digitales Operaciones MIPS para Control de flujo Tomás Arredondo Vidal Este material está basado en: material de apoyo del texto de David Patterson, John Hennessy, "Computer Organization & Design", (segunda y tercera edición), Morgan Kaufmann, CA. 2005 material del curso anterior ELO311 del Prof. Leopoldo Silva material del curso CSE331 de Mary Jane Irving de Penn State www.wikipedia.org
Repaso: Representación Binaria con Signo -23 = -(23 - 1) =
1011 y sumar un 1 1010 complementar los bits
23 - 1 =
2’sc binary 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111
decimal -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7
Repaso: Organización MIPS
Instrucciones aritméticas – hacia/desde register file
Instrucciones load/store – hacia/desde memoria Memory Processor
1…1100
Register File src1 addr
src1 data 32
5
src2 addr
32 5 registers dst addr ($zero - $ra) src2 5 write data data 32 32 32 bits 32 ALU 32
read/write addr 230 words
32
read data 32
write data 32
32
7 3 byte address (little Endian)
6 2
5 1
32 bits
4 0
0…1100 0…1000 0…0100 0…0000 word address (binary)
Repaso: Instrucciones MIPS Hasta Ahora
Category
Instr
Op Code
Example
Meaning
Arithmetic
add
0 and 32 add $s1, $s2, $s3
$s1 = $s2 + $s3
(R format)
subtract
0 and 34 sub $s1, $s2, $s3
$s1 = $s2 - $s3
Data
load word
35
lw
$s1, 100($s2)
$s1 = Memory($s2+100)
transfer
store word
43
sw $s1, 100($s2)
Memory($s2+100) = $s1
(I format)
load byte
32
lb
$s1, 101($s2)
$s1 = Memory($s2+101)
store byte
40
sb $s1, 101($s2)
Memory($s2+101) = $s1
Instrucciones para Toma de Decisiones Instrucciones para Toma de Decisiones alterar el flujo de control e.g., cambiar la próxima instrucción a ser ejecutada
Bifurcaciones condicionales (conditional branch): bne $s0, $s1, Label beq $s0, $s1, Label
#go to Label if $s0≠$s1 #go to Label if $s0=$s1
Ejemplo: if (i==j) h = i + j;
Lab1:
bne $s0, $s1, Lab1 add $s3, $s0, $s1 ...
Múltiples Bifurcaciones (Branches) Instrucciones: bne $s0, $s1, Label beq $s0, $s1, Label
#go to Label if $s0≠$s1 #go to Label if $s0=$s1
Formato del lenguaje de máquina: op
rs
rt
16 bit number
5
16
17
????
4
16
17
????
I format
Como se especifica la dirección destino de la bifurcación?
Especificando el Destino de Bifurcaciones
Se podría especificar la dirección en memoria – pero eso requeriria todos los 32 bits de la instruccion Podría usar un registro y sumarlo a un valor agregado (offset) de 16 bits cual registro?
PC → bne $s0,$s1,Lab1 add $s3,$s0,$s1 Lab1:
...
Registro de dirección de instrucciones (PC = program counter) Su uso esta automáticamente implicado por la instrucción PC se actualiza (PC+4) durante el ciclo de lectura (fetch) asi que contiene la dirección de la próxima instrucción
Limita la distancia de una bifurcación a -215 a +215-1 instrucciones desde la instrucción, pero La mayoría de las bifurcaciones son locales - principio de localidad (principle of locality)
Desensamblar Destinos de Bifurcaciones Los contenidos del PC actualizado (PC+4) se suman a los 16 bits bajos de la instrucción de branch que se convierte en un valor de 32 bits vía Concatenar dos ceros para crear un numero de 18 bits Extender el signo de esos 18 bits
El resultado se escribe en el PC si es que el resultado del condición de bifurcación es verdad antes que el ciclo de lectura de la próximo instrucción (Fetch cycle) from the low order 16 bits of the branch instruction 16
offset sign-extend 00 32 Add
32
PC 32
32 4
32
Add
32
branch dst address 32
?
Ejemplo de Bifurcaciones Código assembler bne $s0, $s1, Lab1 add $s3, $s0, $s1 ...
Lab1:
Formato de máquina de bne:
op
rs
rt
5
16
17
16 bit offset
I format
Recordar
Después de que bne se lee, el PC se actualiza para apuntar a la instrucción add (PC = PC + 4).
Dos ceros se concatenan al numero de offset y ese valor se suma al PC actualizado
Ejemplo de Bifurcaciones Código assembler bne $s0, $s1, Lab1 add $s3, $s0, $s1 ...
Lab1:
Formato de máquina de bne:
op
rs
rt
5
16
17
16 bit offset
I format
1
Recordar
Después de que bne se lee, el PC se actualiza para apuntar a la instrucción add (PC = PC + 4).
Dos ceros se concatenan al numero de offset y ese valor se suma al PC actualizado
Repaso: Organización MIPS
Instrucciones aritméticas – hacia/desde register file
Instrucciones load/store – hacia/desde memoria Memory Processor
1…1100
Register File src1 addr
src1 data 32
5
src2 addr
32 5 registers dst addr ($zero - $ra) src2 5 write data data 32 32 32 bits 32 ALU 32
read/write addr 230 words
32
read data 32
write data 32
32
7 3 byte address (little Endian)
6 2
5 1
32 bits
4 0
0…1100 0…1000 0…0100 0…0000 word address (binary)
Otra Instrucción para Cambio de Flujo MIPS tiene también una instrucción para bifurcación incondicional o salto (jump): j
label
Ejemplo:
Lab1: Lab2:
#go to label if (i!=j) h=i+j; else h=i-j;
beq add j sub ...
$s0, $s1, Lab1 $s3, $s0, $s1 Lab2 $s3, $s0, $s1
Código Assembler de Saltos (jumps) Instrucción: j label
#go to label
Formato de máquina : op 2
26-bit address
J format
????
Como se especifica las dirección del salto? Como una dirección absoluta formada al Concatenar los 4 bits altos del PC actual (PC+4) a la dirección de 26 bits y Concatenar 00 como los 2 bits bajos
Desensamblar Destinos de Saltos Los 26 bits de la instrucción se convierten en una instrucción de salto de 32 bits al Concatenar dos ceros para crear una dirección de 28 bit y Concatenar los 4 bits superiores del PC actual (PC+4)
Los 32 bits se ponen en el PC antes que el próximo ciclo de lectura de instrucción (Fetch cycle) from the low order 26 bits of the jump instruction 26
00 32 32
PC
32
Ensamblar Bifurcaciones y Saltos Ensamblar el código de maquina MIPS de la siguiente secuencia. Asuma que la dirección de la instrucción beq es 0x00400020
Lab1: Lab2:
beq add j sub ...
$s0, $s1, Lab1 $s3, $s0, $s1 Lab2 $s3, $s0, $s1
Ensamblar Bifurcaciones y Saltos Ensamblar el código de maquina MIPS de la siguiente secuencia. Asuma que la dirección de la instrucción beq es 0x00400020
Lab1: Lab2:
0x00400020 0x00400024 0x00400028
beq add j sub ...
$s0, $s1, Lab1 $s3, $s0, $s1 Lab2 $s3, $s0, $s1
4 0
16 16
17 17
19
2 0
32
2 0000 0100 0 ... 0 0011 002 jmp dst = (0x0) 0x040003 002(002) = 0x00400030
0x0040002c
0
0x00400030
...
16
17
19
0
34
Compilando Instrucciones con While Compile el código assembly para las instrucciones en C donde i esta en $s0, j en $s1, y k en $s2 while (i!=k) i=i+j;
Compilando Instrucciones con While Compile el código assembly para las instrucciones en C donde i esta en $s0, j en $s1, y k en $s2 while (i!=k) i=i+j;
Loop: Exit:
beq $s0, $s2, Exit add $s0, $s0, $s1 j Loop . . .
Otras Instrucciones para Tomar Decisiones Tenemos beq, bne, pero falta branch si menor que… Nueva instrucción: slt $t0, $s0, $s1
# if $s0 < $s1 # then # $t0 = 1 # else # $t0 = 0
Formato de máquina: op
0
rs
rt
16
17
rd
8
funct
0
42 = 0x2a
2
Otras Instrucciones para Bifurcaciones Se puede usar slt, beq, bne, y el valor fijo de 0 en el registro $zero para crear otras condiciones less than
blt $s1, $s2, Label
less than or equal to greater than greater than or equal to
ble $s1, $s2, Label bgt $s1, $s2, Label bge $s1, $s2, Label
Como seudo instrucciones son reconocidas y expandidas por el ensamblador (macros) El ensamblador usa un registro reservado ($at)
Otras Instrucciones para Bifurcaciones Se puede usar slt, beq, bne, y el valor fijo de 0 en el registro $zero para crear otras condiciones less than slt bne
blt $s1, $s2, Label $t0, $s1, $s2 $t0, $zero, Label
less than or equal to greater than greater than or equal to
#$t0 set to 1 if # $s1 < $s2
ble $s1, $s2, Label bgt $s1, $s2, Label bge $s1, $s2, Label
Como seudo instrucciones son reconocidas y expandidas por el ensamblador (macros) El ensamblador usa un registro reservado ($at)
Otra Instrucción para Cambio de Flujo Muchos lenguajes tienen un comando como case o switch que permiten al código seleccionar una de muchas alternativas dependiendo de un valor. Instrucción: jr
$t1
#go to address in $t1
Machine format: op
rs
0
9
funct
0
0
0
8 = 0x08
2
Compilando un comando Case (Switch) switch (k) { case 0: h=i+j; case 1: h=i+h; case 2: h=i-j;
Memory break; /*k=0*/ break; /*k=1*/ break; /*k=2*/
$t4→
Asumiendo que las direcciones L0, L1, L2 estan en tres palabras secuénciales en memoria comenzando por la dirección en $t4 y k esta en $s2
L2:
add add add lw jr add j add j sub
Exit:
. . .
L0: L1:
$t1, $t1, $t1, $t0, $t0 $s3, Exit $s3, Exit $s3,
$s2, $s2 $t1, $t1 $t1, $t4 0($t1)
L0 L1 L2
$s0, $s1
#$t1 = 2*k #$t1 = 4*k #$t1 = addr of JT[k] #$t0 = JT[k] #jump based on $t0 #k=0 so h=i+j
$s0, $s3
#k=1 so h=i+h
$s0, $s1
#k=2 so h=i-j
Resumen: Instrucciones MIPS hasta ahora Category
Instr
Op Code
Example
Meaning
Arithmetic
add
0 and 32 add $s1, $s2, $s3
$s1 = $s2 + $s3
(R format)
subtract
0 and 34 sub $s1, $s2, $s3
$s1 = $s2 - $s3
Data
load word
35
lw
$s1, 100($s2)
$s1 = Memory($s2+100)
transfer
store word
43
sw $s1, 100($s2)
Memory($s2+100) = $s1
load byte
32
lb
$s1, 101($s2)
$s1 = Memory($s2+101)
store byte
40
sb
$s1, 101($s2)
Memory($s2+101) = $s1
br on equal
4
beq $s1, $s2, L
if ($s1==$s2) go to L
br on not equal
5
bne $s1, $s2, L
if ($s1 !=$s2) go to L
(I format) Cond. Branch
set on less than Uncond. Jump
jump jump register
0 and 42 slt
$s1, $s2, $s3
2
j
2500
if ($s2=1, so decrement n fact #call fact with (n-1) is where fact returns $a0, 0($sp) #restore argument n $ra, 4($sp) #restore return address $sp, $sp, 8 #adjust stack pointer $v0, $a0, $v0 #$v0 = n * fact(n-1) $ra #return to caller
addi jal #this bk_f: lw lw addi mul jr
$sp, -8 4($sp) 0($sp) $a0, 1 $zero, L1 $zero, 1 $sp, 8
#adjust stack pointer #save return address #save argument n #test for n < 1 #if n >=1, go to L1 #else return 1 in $v0 #adjust stack pointer #return to caller
Ejemplo: Una Mirada al Stack Ejemplo: Asuma que main( ) llamo fact(2) old TOS
← $sp
Estado del stack después de la ejecución de la llamada a la rutina fact con $a0 conteniendo un 2
main rt addr 2
$ra
$a0
$v0
tiene dirección de retorno (return address) a la rutina llamante (caller) (i.e., ubicación en rutina main despues del jal donde se hizo la primera llamada) en $ra tiene parametro (2) en $a0
Ejemplo: Una Mirada al Stack (cont) Ejemplo: Asuma que fact(2) llamo fact(1) old TOS
← $sp
main rt addr $a0 = 2
main rt bk_f addr
2 1
← $sp
$ra
$a0
$v0
Estado del stack después de la ejecución de la instrucción jal (segunda llamada a la rutina fact con $a0 conteniendo un 1) tiene dirección de retorno (return address) a la rutina llamante (caller) (i.e., ubicación en rutina main despues del jal donde se hizo la primera llamada) en el stack tiene valor original de $a0 en el stack
Ejemplo: Una Mirada al Stack (cont) Ejemplo: Asuma que fact(1) llamo fact(0) old TOS main rt addr $a0 = 2
← $sp
bk_f $a0 = 1
← $sp
bk_f
$ra
1 0
$a0
$v0
Estado del stack después de la ejecución de la instrucción jal (tercera llamada a la rutina fact con $a0 conteniendo un 0) tiene dirección de retorno (return address) a la rutina llamante (caller) (i.e., ubicación en rutina fact después del jal) en el stack tiene valor original de $a0 en el stack
Ejemplo: Una Mirada al Stack (cont) Ejemplo: Se ejecuta jr en fact(0) old TOS main rt addr $a0 = 2 bk_f $a0 = 1
← $sp
bk_f $a0 = 0
← $sp
bk_f
$ra
0
$a0
1
$v0
Estado del stack después de la ejecución de la primera instrucción jr de retorno ($v0 es 1) el puntero al stack apunta a la tercera llamada a fact
Ejemplo: Una Mirada al Stack (cont) Ejemplo: Se ejecuta jr en fact(1) old TOS main rt addr $a0 = 2
← $sp
bk_f $a0 = 1
← $sp
bk_f $a0 = 0
bk_f
$ra
0 1
$a0
1 *1 1
$v0
Estado del stack después de ejecución de la segunda instrucción jr (retorno de rutina fact después de actualizar $v0 a 1 * 1) dirección de retorno a rutina llamante (bk_f en rutina fact) se repone en $ra del stack valor previo de $a0 se repone del stack puntero de stack apunta a la segunda llamada a fact
Ejemplo: Una Mirada al Stack (cont) Ejemplo: Se ejecuta jr en fact(2) old TOS
← $sp
main rt addr $a0 = 2
← $sp
bk_f $a0 = 1 bk_f $a0 = 0
main bk_f rt addr
$ra
1 2
$a0
1 1 * * 1 1 * 2
$v0
Estado del stack después de ejecución de la segunda instrucción jr (retorno de rutina fact después de actualizar $v0 a 1 * 1 * 2) dirección de retorno a rutina llamante (main) se repone a $ra del stack valor original de $a0 se repone del stack puntero del stack stack apunta a posición original
Repaso: MIPS R3000 ISA Categorías
Registers
Leer/Guardar (Load/Store) Aritméticas (Computational) Jump and Branch Punto Flotante (Floating Point)
R0 - R31
coprocessador
PC HI
Memory Management Special
LO
3 Formatos: todos de 32 bits 6 bits
5 bits
5 bits
5 bits rd
OP
rs
rt
OP
rs
rt
OP
5 bits shamt
16 bit number 26 bit jump target
6 bits funct
R format I format J format
Registros MIPS Nombre
Numero Registro
$zero $v0 - $v1 $a0 - $a3 $t0 - $t7 $s0 - $s7 $t8 - $t9 $gp $sp $fp $ra
0 2-3 4-7 8-15 16-23 24-25 28 29 30 31
Uso
the constant 0 returned values arguments temporaries saved values temporaries global pointer stack pointer frame pointer return address
Debe preservar en llamada? n.a. no no no yes no yes yes yes yes
Repaso: Instrucciones MIPS Hasta Ahora Category
Instr
Op Code
Example
Meaning
Arithmetic
add
0 and 32 add $s1, $s2, $s3
$s1 = $s2 + $s3
(R format)
subtract
0 and 34 sub $s1, $s2, $s3
$s1 = $s2 - $s3
Data
load word
35
lw
$s1, 100($s2)
$s1 = Memory($s2+100)
transfer
store word
43
sw $s1, 100($s2)
Memory($s2+100) = $s1
load byte
32
lb
$s1, 101($s2)
$s1 = Memory($s2+101)
store byte
40
sb
$s1, 101($s2)
Memory($s2+101) = $s1
br on equal
4
beq $s1, $s2, L
if ($s1==$s2) go to L
br on not equal
5
bne $s1, $s2, L
if ($s1 !=$s2) go to L
(I format) Cond. Branch
set on less than Uncond. Jump
2
j
2500
if ($s2