ELO311Estructuras de Computadores Digitales

Ensamblador MIPS

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: Ciclo de Ejecución

Processor

Control

Datapath

Memory

Devices

Input

Outputcontents Reg #4 ADD contents Reg #2results put in Reg #2

El camino de datos (datapath) ejecuta las instrucciones bajo dirección de control

000000 00100 00010 00010 00000100000

La memoria almacena instrucciones y datos

Repaso: Organización del Procesador� Control tiene que tener la

�Habilidad de leer instrucciones de memoria

� Lógica para controlar la secuenciación de

instrucciones

� Lógica para generar señales que controlen

la manera en que la información fluye entre

componentes del camino de datos

� Lógica para controlar las operaciones de las FUs del camino de datos

� Camino de datos tiene que tener los

�Componentes – unidades funcionales (e.g., sumador) y almacenamiento (e.g., set de registros) – necesario para ejecutar instrucciones

�Componentes interconectados para que las instrucciones se puedanejecutar

�Capacidad de leer y almacenar datos en la memoria

Leer

DecodeExec

For a given level of function, however, that system is best in which one can specify things with the most simplicity and straightforwardness. … Simplicity and straightforwardness proceed from conceptual integrity. … Ease of use, then, dictates unity of design, conceptual integrity.

The Mythical Man-Month, Brooks, pg 44

MIPS = RISC (Reduced Instruction Set Computer)

�Filosofía RISC�Instrucciones de largo fijo

�Sets de instrucciones de lectura-escritura (load-store)

�Modos de direccionamiento limitado

�Operaciones limitadas

�MIPS, Sun SPARC, HP PA-RISC, IBM PowerPC, Intel (Compaq) Alpha, …

�Conjuntos de instrucciones se miden por la manera en la cual los compiladores las usan no como los programadores los usan

Organización General de MIPS

ProcessorMemory

32 bits

230

words

read/writeaddr

read data

write data

word address(binary)

0…00000…01000…10000…1100

1…1100Register File

src1 addr

src2 addr

dst addr

write data

32 bits

src1data

src2data

32registers

($zero - $ra)

32

32

3232

32

32

5

5

5

PC

ALU

32 32

3232

32

0 1 2 37654

byte address(big Endian)

FetchPC = PC+4

DecodeExec

Add32

324

Add32

32br offset

Procesador Monociclo

� Esquema General por unidad

Unidad de Control

AluOut

32 busA

32 busB

Unidad

Registros

rs

rt

32busW

RegWr AluCtr

AluSrc

RegDst

rd

ExtOp

Inm16AddrD

Mem oria

Datos DoutDin

MemRd

MemWr

0

1

MemtoReg

Unidad

de

Operaciones

nPC_sel

Unidad

de

Instrucción

COp+

Funct

Equal

Reloj

5

5

5

WE PC

Instrucciónes Aritméticas MIPS

�Comandos de asembler MIPS

add $t0, $s1, $s2

sub $t0, $s1, $s2

�Cada instrucción aritmética hace solo una operación

�Cada instrucción aritmética tiene exactamente tresoperandos

destination ← source1 op source2

�Los operandos se contienen en el set de registros del camino de datos o register file ($t0,$s1,$s2 )

�Orden de los operandos es fijo (destino primero)

Instrucciónes Aritméticas MIPS

�Comandos de asembler MIPS

add $t0, $s1, $s2

sub $t0, $s1, $s2

�Cada instrucción aritmética hace solo una operacion

�Cada instrucción aritmética tiene exactamente tresoperandos

destination ← source1 op source2

�Los operandos se contienen en el set de registros del camino de datos o register file ($t0,$s1,$s2 )

�Orden de los operandos es fijo (destino primero)

Comandos Más Complejos

�Asumiendo que la variable b es almacenado en el registro $s1 , c es almacenado en $s2 , y d es almacenado en $s3 y el resultado debe guardarse en $s0 , cual es el equivalente en asembler de?

h = (b - c) + d

Comandos Más Complejos

�Asumiendo que la variable b es almacenado en el registro $s1 , c es almacenado en $s2 , y d es almacenado en $s3 y el resultado debe guardarse en $s0 , cual es el equivalente en asembler de?

h = (b - c) + d

sub $t0, $s1, $s2

add $s0, $t0, $s3

Conjunto de Registros MIPS� Operandos de instrucciones aritméticos deben ser del conjunto

de registros (register file) de ubicaciones especiales contenidas en el camino de datos (datapath)�Tiene 32 registros de 32 bits

� Con dos puertos de lectura y

� Un puerto de escritura

� Registros son �Mas rápidos que memoria principal (e.g. DRAM)

�Mas fácil de usar para un compilador� e.g., (A*B) – (C*D) – (E*F) puede hacer multiplicaciones en cualquier

orden (vs stack)

�Puede tener variables� Densidad del código es mayor (registros usan menos bits que memoria)

� Direcciones de registros se indican usando $

Register File

src1 addr

src2 addr

dst addr

write data

32 bits

src1data

src2data

32locations

325

32

5

5

32

0 $zero constant 0 (Hdware)

1 $at reserved for assembler

2 $v0 expression evaluation &

3 $v1 function results

4 $a0 arguments

5 $a1

6 $a2

7 $a3

8 $t0 temporary: caller saves

. . . (callee can clobber)

15 $t7

Nombres de registros

16 $s0 callee saves

. . . (caller can clobber)

23 $s7

24 $t8 temporary (cont’d)

25 $t9

26 $k0 reserved for OS kernel

27 $k1

28 $gp pointer to global area

29 $sp stack pointer

30 $fp frame pointer

31 $ra return address (Hdware)

Registros vs. Memoria

� Operandos de instrucciones aritméticas deben ser registros,

— solo hay 32 registro disponibles

� Compiladores asocian variables con registros

� Que pasa con programas con muchas variables?

Processor

Control

Datapath

Memory

Devices

Input

Output

Registros vs. Memoria

� Operandos de instrucciones aritméticas deben ser registros,

— solo hay 32 registro disponibles

� Compiladores asocian variables con registros

� Que pasa con programas con muchas variables?

Processor

Control

Datapath

Memory

Devices

Input

Output

Accediendo a la Memoria

�MIPS tiene dos instrucciones básicas de transferencia de datos para acceder a la memoria

lw $t0, 4($s3) #load word from memory

sw $t0, 8($s3) #store word to memory

(assume $s3 tiene 2410)

�La instrucción de transferencia de datos debe especificar�De donde leer (load) o escribir (write) en memoria – memory

address

�Desde donde en los registros leer o cargar

�La dirección de memoria se forma al sumar la dirección constante de la instrucción y los contenidos del segundo registro

Accediendo a la Memoria

�MIPS tiene dos instrucciones básicas de transferencia de datos para acceder a la memoria

lw $t0, 4($s3) #load word from memory

sw $t0, 8($s3) #store word to memory

(assume $s3 tiene 2410)

�La instrucción de transferencia de datos debe especificar�De donde leer (load) o escribir (write) en memoria – memory

address

�Desde donde en los registros leer o cargar

�La dirección de memoria se forma al sumar la dirección constante de la instrucción y los contenidos del segundo registro

28

32

Memoria

�Asumiendo que la variable h esta asociada con el registro $s2 , y la dirección base de arreglo A esta en $s3 , cual es el equivalente en asembler de?

A[12] = h + A[8]

Memoria

�Asumiendo que la variable h esta asociada con el registro $s2 , y la dirección base de arreglo A esta en $s3 , cual es el equivalente en asembler de?

A[12] = h + A[8]

lw $t0, 32($s3) # Temp $t0 gets A[8]

add $t0, $s2,$t0 # Temp $t0 gets h+A[8]

sw $t0, 48($s3) # Store h+A[8] into A[12]

�La memoria se ve como un arreglo de ubicaciones de almacenamiento con direcciones

�Una dirección de memoria es un índice para el arreglo

Interconexión del Procesador y Memoria

ProcessorMemory

32 bits

numero posible deubicaciones?

read addr/write addr

read data

write data

�La memoria se ve como un arreglo de ubicaciones de almacenamiento con direcciones

�Una dirección de memoria es un índice para el arreglo

Interconexión del Procesador y Memoria

ProcessorMemory

32 bits

?ubicaciones

read addr/write addr

read data

write data

32

32

32

232 → 230 words

Tipos de datos MIPS

Bit : 0, 1

Bit String : secuencia de bits de un largo particular4 bits is a nibble8 bits is a byte

16 bits is a half-word32 bits (4 bytes) is a word64 bits is a double-word

Caracter :ASCII 7 bit code

Decimal :dígitos 0-9 codificados como 0000b a 1001bdos dígitos decimales por cada byte de 8 bits

Integers: complemento 2's

Floating Point

Direcciones de Bytes

�Dado que bytes de 8-bits son tan útiles, la mayoría de las arquitecturas direccionan bytes individuales de la memoria

�Entonces, la dirección de memoria de una palabra tiene que ser un múltiple de 4 (restricción de alineamiento)

�Procesadores MIPS generalmente pueden ser configurados como Big o Little Endian.

�Big Endian: byte de la izquierda es dirección de wordIBM 360/370, Motorola 68k, Sparc, HP PA

�Little Endian: byte de la derecha es dirección de wordIntel 80x86, DEC Vax, DEC Alpha (Windows NT)

Direcionamiento: Endianess y Alineamiento

�Big Endian: byte de la izquierda es dirección de word

�Little Endian: byte de la derecha es dirección de word

msb lsb

little endian

big endian0 1 2 3

Aligned

NotAligned

Direcionamiento: Endianess y Alineamiento

�Big Endian: byte de la izquierda es dirección de word

�Little Endian: byte de la derecha es dirección de word

msb lsb

3 2 1 0

little endian byte 0

0 1 2 3big endian byte 0

0 1 2 3

Aligned

NotAligned

0 1 2 3

Direccionamiento de Memoria en MIPS�La dirección de memoria se forma sumando la parte

constante de la instrucción y el contenido del segundo registro (base) (Asumir Little Endian)

lw $t0, 4($s3) #que? se carga en $t0

sw $t0, 8($s3) #$t0 se almacena adonde?

Memory

. . . 0 1 0 0Data Word Address

0

4

8

12

16

20

24

. . . 1 0 0 0

. . . 0 0 1 0

. . . 0 0 0 1

. . . 1 1 0 0

. . . 0 1 0 1

. . . 0 1 1 0$s3 holds 8

Direccionamiento de Memoria en MIPS�La dirección de memoria se forma sumando la parte

constante de la instrucción y el contenido del segundo registro (base)

lw $t0, 4($s3) #que? se carga en $t0

sw $t0, 8($s3) #$t0 se almacena adonde?

Memory

. . . 0 1 0 0Data Word Address

0

4

8

12

16

20

24

. . . 1 0 0 0

. . . 0 0 1 0

. . . 0 0 0 1

. . . 1 1 0 0

. . . 0 1 0 1

. . . 0 1 1 0$s3 holds 8

en ubicación 16

. . . 0001

. . . 0001

Compilando con Loads and Stores

�Si la variable b se almacena en $s2 y la dirección base de un arreglo A esta en $s3 , cual es el código assembler MIPS para el siguiente código en C?

A[8] = A[2] - b

$s3

$s3 +4

$s3 +8

$s3 +12

. . .

A[2]

A[3]

. . .

A[1]

A[0]

Compilando con Loads and Stores

�Si la variable b se almacena en $s2 y la dirección base de un arreglo A esta en $s3 , cual es el código assembler MIPS para el siguiente código en C?

A[8] = A[2] - b

$s3

$s3 +4

$s3 +8

$s3 +12

. . .

A[2]

A[3]

. . .

A[1]

A[0]lw $t0, 8($s3)

sub $t0, $t0, $s2

sw $t0, 32($s3)

Compilando con un índice de un arreglo

�Asumiendo que A es un arreglo de 50 elementos para los cuales su base esta en $s4 , y que las variables b, c, i están en $s1 , $s2 , y $s3 respectivamente. Cual es el código MIPS para la siguiente línea en C?

c = A[i] - b

add $t1, $s3, $s3 #array index i is in $s3

add $t1, $t1, $t1 #temp reg $t1 holds 4*i

Compilando con un índice de un arreglo

�Asumiendo que A es un arreglo de 50 elementos para los cuales su base esta en $s4 , y que las variables b, c, i están en $s1 , $s2 , y $s3 , respectivamente, cual es el código MIPS para la siguiente línea en C?

c = A[i] - b

add $t1, $s3, $s3 #array index i is in $s3

add $t1, $t1, $t1 #temp reg $t1 holds 4*i

add $t1, $t1, $s4 #addr of A[i]

lw $t0, 0($t1)

sub $s2, $t0, $s1

Instrucciones MIPS hasta ahora

43

35

0 and 34

0 and 32

Op Code

Memory($s2+100) = $s1sw $s1, 100($s2)store word

$s1 = Memory($s2+100)lw $s1, 100($s2)load wordData

transfer

(I format)

$s1 = $s2 - $s3sub $s1, $s2, $s3subtract

$s1 = $s2 + $s3add $s1, $s2, $s3addArithmetic

(R format)

MeaningExampleInstrCategory

Repaso: Organización MIPS

ProcessorMemory

32 bits

230

words

read/writeaddr

read data

write data

word address(binary)

0…00000…01000…10000…1100

1…1100

Register File

src1 addr

src2 addr

dst addr

write data

32 bits

src1data

src2data

32registers

($zero - $ra)

32

32

32

32

32

32

5

5

5

ALU32

32

32 3 2 1 04567

byte address(little Endian)

� Instrucciones aritméticas – hacia/desde register file

� Instrucciones load/store – hacia/desde memoria

0 $zero constant 0 (Hdware)

1 $at reserved for assembler

2 $v0 expression evaluation &

3 $v1 function results

4 $a0 arguments

5 $a1

6 $a2

7 $a3

8 $t0 temporary: caller saves

. . . (callee can clobber)

15 $t7

Nombres de registros

16 $s0 callee saves

. . . (caller can clobber)

23 $s7

24 $t8 temporary (cont’d)

25 $t9

26 $k0 reserved for OS kernel

27 $k1

28 $gp pointer to global area

29 $sp stack pointer

30 $fp frame pointer

31 $ra return address (Hdware)

Representación Binaria Sin Signo (Unsigned)

0xFFFFFFFF

0xFFFFFFFE

0xFFFFFFFD

0xFFFFFFFC

0x00000009

0x00000008

0x00000007

0x00000006

0x00000005

0x00000004

0x00000003

0x00000002

0x00000001

0x00000000

Hex

1…1111

1…1110

1…1101

1…1100

…

90…1001

80…1000

70…0111

60…0110

50…0101

40…0100

30…0011

20…0010

10…0001

00…0000

DecimalBinary

232 - 1232 - 2

232 - 3232 - 4

232 - 1

1 1 1 . . . 1 1 1 1 bit

31 30 29 . . . 3 2 1 0 posición

231 230 229 . . . 23 22 21 20 valor del bit

1 0 0 0 . . . 0 0 0 0 - 1

Representación Binaria con Signo (Signed)

-81000

-71001

70111

60110

50101

40100

30011

20010

10001

00000

-11111

-21110

-31101

-41100

-51011

-61010

decimal2’sc binary

23 - 1 =

-(23 - 1) =

-23 =

1010

complementa los bits

1011

y suma un 1

� Instrucciones como registros y words de datos son de 32 bits de largo� Ejemplo: add $t0, $s1, $s2

� Registros tienen números $t0=$8, $s1=$17, …

� Formato de instrucción aritmética:

Para que son los nombres de los campos?

Instrucción Aritmética en Machine Language

op rs rt rd shamt funct

000000 10001 10010 01000 00000 100000

� Instrucciones como registros y words de datos son de 32 bits de largo� Ejemplo: add $t0, $s1, $s2

� Registros tienen números $t0=$8, $s1=$17, …

� Formato de instrucción aritmética:

Cuales son los nombres de los campos?

Instrucción Aritmética en Machine Language

op rs rt rd shamt funct

000000 10001 10010 01000 00000 100000

Nombres de los campos en MIPS

�op

�rs

�rt

�rd

�shamt

�funct

op rs rt rd shamt funct6 bits 5 bits 5 bits 5 bits 5 bits 6 bits = 32 bits

Nombres de los campos en MIPS

�op

�rs

�rt

�rd

�shamt

�funct

op rs rt rd shamt funct6 bits 5 bits 5 bits 5 bits 5 bits 6 bits = 32 bits

Opcode indicando la operación (instrucción)

Dirección del primer registro (source) operando

Dirección del segundo registro (source) operando

Dirección del registro destino

Cantidad de rotación (para instrucción de rotación)

Código de función que selecciona variante de la operación especificada en opcode

� Considere las instrucciones para load-word y store-word

� Introduce un nuevo tipo de formato de instrucción

� I-type para transferencia de datos

� formato previo era R-type para registros

� Ejemplo: lw $t0, 24($s2)

Lenguaje de Maquina – Instruccion Load

op rs rt 16 bit number

35 18 8 24

100011 10010 01000 0000000000011000

� Considere las instrucciones para load-word y store-word

� Introduce un nuevo tipo de formato de instrucción

� I-type para transferencia de datos

� formato previo era R-type para registros

� Ejemplo: lw $t0, 24($s2)

Lenguaje de Maquina – Instruccion Load

op rs rt 16 bit number

35 18 8 24

100011 10010 01000 0000000000011000

Dirección de Memoria

�Ejemplo: lw $t0, 24($s2)Memory

data word address (hex)0x000000000x000000040x000000080x0000000c

0xf f f f f f f f

$s2 0x12004094

0x00000002

2410 + $s2 =

El offset puede ser positivo o negativo

Ubicación de Dirección de Memoria

�Ejemplo: lw $t0, 24($s2)Memory

data word address (hex)0x000000000x000000040x000000080x0000000c

0xf f f f f f f f

$s2 0x12004094

0x00000002

2410 + $s2 =

El offset puede ser positivo o negativo

. . . 1001 0100+ . . . 0001 1000

. . . 1010 1100 =0x120040ac

0x120040ac

� Ejemplo: sw $t0, 24($s2)

� Una dirección de 16-bits significa que acceso esta limitado a ubicaciones de memoria dentro de una región de ±213 o 8,192 words (±215 o 32,768 bytes) en el rango de direcciones del registro base $s2

Lenguaje de Maquina – Instruccion Store

op rs rt 16 bit number

43 18 8 24

101011 10010 01000 0000000000011000

� Ejemplo: sw $t0, 24($s2)

� Una dirección de 16-bits significa que acceso esta limitado a ubicaciones de memoria dentro de una región de ±213 o 8,192 words (±215 o 32,768 bytes) en el rango de direcciones del registro base $s2

Lenguaje de Maquina – Instruccion Store

op rs rt 16 bit number

43 18 8 24

101011 10010 01000 0000000000011000

Código Assembler�Recuerde el programa que se hizo anteriormente

A[8] = A[2] - b

lw $t0, 8($s3) #load A[2] into $t0sub $t0, $t0, $s2 #subtract b from A[2]sw $t0, 32($s3) #store result in A[8]

Cual seria el código maquina para estas instrucciones?

Código Assembler�Recuerde el programa que se hizo anteriormente

A[8] = A[2] - b

lw $t0, 8($s3) #load A[2] into $t0sub $t0, $t0, $s2 #subtract b from A[2]sw $t0, 32($s3) #store result in A[8]

El código MIPS es el siguiente:

35lw 19 8 8

43sw 19 8 32

0sub 8 18 8 0 34

Repaso: Tipos de datos MIPS

Bit : 0, 1

Bit String : secuencia de bits de un largo particular4 bits is a nibble8 bits is a byte

16 bits is a half-word32 bits (4 bytes) is a word64 bits is a double-word

Caracter :ASCII 7 bit code

Decimal :dígitos 0-9 codificados como 0000b a 1001bdos dígitos decimales por cada byte de 8 bits

Integers: complemento 2's

Floating Point

ASCII�La mayoría de las computadoras usan bytes de 8 bits para

representar caracteres con ASCII (American Std Code forInfo Interchange)

�Por eso necesitamos instrucciones para mover bytes

|124l108L76<60,44FF12

{123k107K75;59+4311

z122j106J74:58*42LF10

y121i105I73957)41tab9

x120h104H72856(40bksp8

w119g103G71755‘397

ACK

EOT

Null

Char

15

6

5

4

3

2

1

0

ASCII

v118f102F70654&38

u117e101E69553%37

DEL

t

s

r

q

p

Char

127

116

115

114

113

112

ASCII

o111O79?63/47

d100D68452$36

c99C67351#35

b98B66250“34

a97A65149!33

`96@64048space32

CharASCIICharASCIICharASCIICharASCII

Leyendo y Guardando (Load/Store) Bytes

�MIPS provee instrucciones para mover bytes

lb $t0, 1($s3) #load byte from memory

sb $t0, 6($s3) #store byte to memory

�Que 8 bits se leen y guardan?� load byte pone el byte de memoria en los 8 bits mas a la derecha

del registro destino

� que pasa con los otros bits del registro?

�store byte toma el bite de los 8 bits mas a la derecha del registro y los escribe a un byte en la memoria

op rs rt 16 bit number

Ejemplo: Leyendo y Guardando Bytes�Dado el siguiente código cuales son los valores de

memoria y los registros después de ejecutarlo?add $s3, $zero, $zerolb $t0, 1($s3)sb $t0, 6($s3)

Memory

0 0 9 0 1 2 A 0Data Word

Address (Decimal)

0

4

8

12

16

20

24

F F F F F F F F

0 1 0 0 0 4 0 2

1 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

� Que queda en $t0 si la maquina es big Endian?

� Y si la maquina fuera little Endian?

$t0 = 0x00000090

mem(4) = 0xFFFF90FF

mem(4) = 0xFF12FFFF$t0 = 0x00000012

Repaso: Instrucciones MIPS hasta ahora

Memory($s2+101) = $s1sb $s1, 101($s2)40store byte

$s1 = Memory($s2+101)lb $s1, 101($s2)32load byte

43

35

0 and 34

0 and 32

Op Code

Memory($s2+100) = $s1sw $s1, 100($s2)store word

$s1 = Memory($s2+100)lw $s1, 100($s2)load wordData

transfer

(I format)

$s1 = $s2 - $s3sub $s1, $s2, $s3subtract

$s1 = $s2 + $s3add $s1, $s2, $s3addArithmetic

(R format)

MeaningExampleInstrCategory

Repaso: MIPS R3000 ISA

� Categorías� Leer/Guardar (Load/Store)

� Aritméticas (Computational)

� Jump and Branch

� Punto Flotante (Floating Point)� coprocessador

� Memory Management

� Special

� 3 Formatos: todos de 32 bits

R0 - R31

PCHI

LO

OP rs rt rd shamt funct

OP rs rt 16 bit number

OP 26 bit jump target

Registers

R format

I format

6 bits 5 bits 5 bits 5 bits 5 bits 6 bits