Transcript Chapter 3 Machine Languages

Assembly Language
Chapter 3
Computer Languages

High-level languages


Low-level languages



Java, Python, C, ASP, HTML, …
Assembly language: symbolic representation of
machine instructions.
Assembler: a compiler which translates from
an assembly language to a machine language.
Machine languages
2301274
Chapter 3 Assembly Languages
2
Components of a computer: More
detail
processor
registers
memory
ALU
data
program
Instruction register
Program counter
address
data
Control units
2301274
Chapter 3 Assembly Languages
3
Levels of descriptions of computer systems
Applications
Operating systems
Instruction set
Functional units
Finite state machine
Logic gates
Electronics
2301274
• computer architecture begins
at the instruction set.
• An instruction set is what a
programmer at the lowest level
sees of a processor
• one instruction set with
different level of performance
for many models, based on the
implementation of a control
unit via “microprogram”.
• Present day processor
designs converge, their
instruction sets become more
similar than different.
Chapter 3 Assembly Languages
4
Registers
Name
Reg. No.
$zero
0
$v0-$v1
2-3
$a0-$a3
4-7
$t0-$t7
8-15
$s0-$s7
16-23
$t8-$t9
24-25
$gp
28
$sp
29
$fp
30
$ra
31
2301274
Usage
hardwired 0
return value and expression evaluation
arguments
temporary values
saved values
more temporary values
global pointer
stack pointer
frame pointer
return address
Chapter 3 Assembly Languages
5
MIPS operands
Name
Example
Comments
32 registers
$0, $1, $2,..., $31
Fast location for data. In MIPS,
data must be in registers to
perform arithmetic.
memory
words
Memory[0],
Accessed only by data transfer
Memory[4],...,
instructions. MIPS uses byte
Memory[4293967292] addresses, so sequential words
differ by 4. Memory holds data
structures, such as arrays, and
spilled registers, such as those
saved on procedure calls
2301274
Chapter 3 Assembly Languages
6
MIPS Assembly Instructions: Arithmetic
Instruction
Example
Meaning
add
add $rd,$rs,$rt
$rd = $rs + $rt
subtract
sub $rd,$rs,$rt
$rd = $rs - $rt
add unsigned
addu $rd,$rs,$rt
$rd = $rs + $rt
subtract unsigned
subu $rd,$rs,$rt
$rd = $rs - $rt
add immediate
addi $rd,$rs, 100
$rd = $rs + 100
2301274
Comments
3 operands; data in registers
3 operands; data in registers
3 operands; data in registers and
a constant
Chapter 3 Assembly Languages
7
MIPS Assembly Instructions: Data Transfer
Instruction
Example
Meaning
Comments
load word
lw $rt, 10($rs) $rt = Memory[$rs+10]
Data from memory to
register
store word
sw $rt, 10($rs) Memory[$rs+10] = $rt
Data from register to
memory
2301274
Chapter 3 Assembly Languages
8
MIPS Assembly Instructions: Logical
Instruction
and
Example
Meaning
and $rd,$rs,$rt
$rd = $rd & $rt
or
or $rd,$rs,$rt
$rd = $rd | $rt
nor
nor $rd,$rs,$rt
$rd = ~($rd & $rt)
and immediate
andi $rt,$rs,10
$rt = $rs & 10
or immediate
ori $rt,$rs,10
$rt = $rs | 10
shift left logical
sll $rd,$rt,10
$rd = $rt << 10
shift right logical
srl $rd,$rt,10
$rd = $rt >> 10
2301274
Chapter 3 Assembly Languages
Comments
3 register operands;
bitwise operation
bitwise operation with
constant
Shift left/right by
constant
9
MIPS Assembly Instructions
Instruction
Example
Meaning
Comments
jump
j 10000
goto 10000
Jump to target addr.
jump register
j $31
goto $31
For switch, procedure return
jump and link jal 1000
2301274
$31 = PC+4 ; go to 1000 For procedure call
Chapter 3 Assembly Languages
10
MIPS Assembly Instructions: Conditionals
Instruction
Example
Meaning
Comments
beq $rs,$rt,100
if ($rs == $rt)
go to PC+4+100
Equal test; PC relative
branch
branch on not = bne $rs,$rt,100
if ($rs != $rt)
go to PC+4+100
Not equal test; PC
relative branch
branch on =
set on <
slt $rd,$rs,$rt
set < immediate slti $rt,$rs,100
set < unsigned
sltu $rd,$rs,$rt
set < immediate sltiu $rt,$rs,100
unsigned
2301274
if ($rs < $rt) $rd = 1; Compare <; 2’s
else $rd = 0 complement
if ($rs < 100) $rt = 1;
else $rt = 0
Compare < constant;
2’s complement
if ($rs < $rt) $rd = 1; Compare <; natural
else $rd = 0 number
($rs < 100) $rt = 1;
else $rt = 0
Chapter 3 Assembly Languages
Compare < constant;
natural number
11
Example


x = y+z+5;
w = z-y;
10
14
w
lw
lw
add
addi
sw
sub
sw
2301274
$t0,
$t1,
$t2,
$t2,
$t2,
$t3,
$t3,

18
x
y
if (a<b)
a++;
else b++;
22
50
z
18($zero) # load y
22($zero) # load z
$t0, $t1
# y+z
$t2, 5
# (y+z)+5
14($zero) # store x
$t1, $t2
# z-y
10($zero) # store w
a
lw
lw
slt
beq
addi
sw
else:
addi
sw
$t0,
$t1,
$t2,
$t2,
$t0,
$t0,
54
b
50($zero) # load a
54($zero) # load b
$t0, $t1
# a<b
$zero, else # if
$t0, 1
# a++
50($zero) # store a
$t1, $t1, 1
# b++
$t1, 54($zero) # store b
Chapter 3 Assembly Languages
12
Basic instruction formats
31
R- format
26
25
op
21
20
rs
16
15
rt
11
10
rd
6
Shamt
5
0
funct
I- format
31
26
25
Op
21
rs
20
16
15
rt
0
Const/addr
J- format
31
26
Op code
2301274
25
0
address
Chapter 3 Assembly Languages
13
Instruction Representation: Examples
Instruction
Format Op rs
rt
rd
Shamt
funct Const/addr
add $rs,$rt,$rd
R
00 reg reg reg
00
20
NA
sub $rs,$rt,$rd
R
00 reg reg reg
00
22
NA
addi $rs,$rt, 100
I
08 reg reg NA
NA
NA
const
j 10000
J
02 NA NA NA
NA
NA
addr
beq $rs,$rt, 1000
I
04 reg reg NA
NA
NA
const
2301274
Chapter 3 Assembly Languages
14
Instruction Representation: Examples
Instruction
Format Op rs
add $rs,$rt,$rd
R
rt
rd Shamt funct
00 reg reg reg
00
Const/addr
20
NA
add $t0, $t1, $t2
31
26
25
21
20
16
15
11
10
6
5
0
op
rs
rt
rd
Shamt
funct
000000
01000
01001
01010
00000
100000
0
2301274
1
0
9
5
Chapter 3 Assembly Languages
0
3
0
15
Instruction Representation: Examples
Instruction
Format Op rs
sub $rs,$rt,$rd
R
rt
rd
Shamt
00 reg reg reg
funct Const/addr
00
22
NA
sub $s0, $s1, $s2
31
26
25
21
20
16
15
11
10
6
5
0
op
rs
rt
rd
Shamt
funct
000000
10000
10001
10010
00000
100010
0
2301274
2
1
1
9
Chapter 3 Assembly Languages
0
2
2
16
Instruction Representation: Examples
Instruction
Format Op rs
addi $rs,$rt, 100
I
rt
rd Shamt funct
08 reg reg NA
NA
Const/addr
NA
const
addi $s0, $s1, 100
31
26
25
21
20
16
15
0
op
rs
rt
Const/addr
001000
10000
10001
0000110010101100
2
2301274
2
1
1
0
Chapter 3 Assembly Languages
C
A
C
17
Instruction Representation: Examples
Instruction
Format Op rs
j 10000
J
rt
rd Shamt funct
02 NA NA NA
NA
Const/addr
NA
addr
j 10000
31
26
25
0
op
000010
0
2301274
Const/addr
00 0000 0000 0010 0111 0001 0000
8
0
0
2
7
Chapter 3 Assembly Languages
1
0
18
Instruction Representation: Examples
Instruction
Format Op rs
beq $rs,$rt, 1000
I
rt
rd
Shamt funct
04 reg reg NA
NA
NA
Const/addr
const
beq $s0, $s1, 100
31
26
25
21
20
16
15
0
op
rs
rt
Const/addr
000100
10000
10001
0000110010101100
1
2301274
2
1
1
0
Chapter 3 Assembly Languages
C
A
C
19
MIPS Simulator
http://pages.cs.wisc.edu/~larus/spim.html
2301274
Chapter 3 Assembly Languages
20
Case/ Switch statement
switch (i)
{
case 0:
case 1:
case 4:
}

i++;
j++;
k++;
break;
break;
Jump (address) table

2301274
Table storing addresses of different cases
3010
2010
k=0
3014
2045
k=1
3018
2077
k=2
301C
2077
k=3
3020
2085
k=4
Chapter 3 Assembly Languages
21
Case statement and jr instruction
switch (i)
{ case 0:
i++;
break;
case 1:
j++;
break;
case 4:
k++;
}
2301274
# variable i is in $t1, const 5 is in $t0
# start addr of jump table (e.g. 3010) is in $s0
blt
$t1, $zero, out
bge $t1, $t0, out
# multiply i by 4 for word size
sll
$t1, $t1, 2
# find entry in the jump table
add $t1, $t1, $s0
# load addr in jump table to $t2
lw
$t2, 0($t1)
jr
$t2
L2010:
…
j
out
L20485:
…
out:
Chapter 3 Assembly Languages
22
Procedure calls

Steps to Execute procedure






2301274
place parameters in a place where procedure can access
them
transfer control to the procedure
acquire the storage needed for the procedure
perform the desired task
place the result value in a place where the calling
program can access it
return to the control point of origin
Chapter 3 Assembly Languages
23
Memory allocation for programs
$sp
Stack
$fp
Heap
(dynamic data)
Static data
$gp
Code
(text segment)
pc
Reserved
2301274
Chapter 3 Assembly Languages
24
Registers

$a0-$a3


$v0-$v1


four argument registers in which to pass
parameters
two value registers in which to return values
$ra

2301274
one return address register to return to the
point of origin
Chapter 3 Assembly Languages
25
jal jump and link

jumps to an address and simultaneously
saves the address of the following
instruction in register $ra



jal ProcedureAddress
jal puts PC + 4 in $ra
to return, after completion of the
procedure:

jr $ra
calling program (caller) puts parameter
values in $a0-$a3
 callee performs calculations and places
result in $v0-$v1

2301274
Chapter 3 Assembly Languages
26
Call sequence
Put arguments in $a0-$a3
 The rest of the arguments (if exist) are
placed in the frame or activation record
 Allocate a frame in stack (update $sp)
 Save values of $s0-$s7, $fp, $ra in the
frame
 Update $fp
 Execute jal instruction

2301274
Chapter 3 Assembly Languages
27
Return sequence
Put the return value in $v0
 Restore registers $s0-$s7
 Restore $fp
 Pop the frame from stack
 Execute jr $ra

2301274
Chapter 3 Assembly Languages
28
Example 1
int leaf_example (int g, int h, int i, int j)
{ int f;
f = (g + h) - (i + j);
return f;
}
leaf example:
addi $sp, $sp, -12
sw $t1, 8($sp)
sw $t0, 4($sp)
sw $s0, 0($sp)
add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1
add $v0, $s0, $zero
lw
$s0, 0($sp)
lw
$t0, 4($sp)
lw
$t1, 8($sp)
addi $sp, $sp, 12
jr
$ra
2301274
#adjust stack to make room for 3 items
#save register $t1 for use afterwards
#save register $t0 for use afterwards
#save register $s0 for use afterwards
#register $t0 contains g + h
#register $t1 contains i + j
#f = $t0 - $t1, which is (g+h)-(i+j)
#returns f ($v0 = $s0 + 0)
#restore register $s0 for caller
#restore register $t0 for caller
#restore register $t1 for caller
#adjust stack to delete 3 items
#jump back to calling routing
Chapter 3 Assembly Languages
29
Example 2
int fact (int n)
{ if (n<2)
return(1);
else return(n*fact(n-1);
}
fact:
addi $sp, $sp, -8 #adjust stack to make room for 2
items
sw $ra, 4($sp)
#save the return address
sw $a0, 0($sp) #save the argument n
slti $t0, $a0, 2
#test for n<2
beq $t0, $zero, L1 #if n>=2 goto L1
addi $sp, $sp, 8
#adjust stack to delete 2 items
addi $v0, $zero, 1 #else return 1
jr $ra
#jump back to calling routing
L1:
addi $a0, $a0, -1 #if n>=1 calculate n-1
jal fact
#call fact with n-1
lw $a0, 0($sp) #return from jal, restore argument
lw $ra, 4($sp)
#restore return address
addi $sp, $sp, 8
#adjust stack to delete 2 items
mul $v0, $a0, $v0 # return n* fact(n-1)
jr $ra
#jump back to calling routing
2301274
Chapter 3 Assembly Languages
30
int fact (int n)
{ if (n<2) return(1);
else return(n*fact(n-1);
}
Execution example
fact:
addi
Push sw
frame
sw
slti
beq
addi
addi
n<2
ret 1
jr
L1:
addi
(0340) jal
lw
restore
lw
addi
mul
n>=2
ret n*(n-1)! jr
2301274
$sp, $sp, -8
$ra, 4($sp)
$a0, 0($sp)
$t0, $a0, 2
$t0, $zero, L1
$sp, $sp, 8
$v0, $zero, 1
$ra
$a0, $a0, -1
fact
$a0, 0($sp)
$ra, 4($sp)
$sp, $sp, 8
$v0, $a0, $v0
$ra
… fact(2);
Call fact (2) addi $a0, $zero, 2
(03A0)
jal fact
$a0
12
$ra
03A4
0344
$v0
03A4 ($ra)
2($a0)
0344 ($ra)
1($a0)
21
Chapter 3 Assembly Languages
stack
31
32-bit constants
A register can contain an integer between
-2147483648 (-231) and 2147483647
 Immediate data can be between -32768
(-215) and 32767



addi
$t0, $zero, 32767
How can we use 32-bit constant?

2301274
lui (load upper immediate) instruction
Chapter 3 Assembly Languages
32
load upper immediate instruction: lui

Store 16-bit immediate data in the upper
half of the register
lui $t0, 16384 # put 0100 0000 0000 0000 in the upper half of $t0
0100 0000 0000 0000

To store a 32-bit constant in a register
add
lui
addi
2301274
$t0, $zero, $zero
$t0, 16384
$t0, $t0, 5435
Chapter 3 Assembly Languages
33
Jumping to far-away instruction
In beq or bne instructions, only  215
distance can be specified.
 To jump to further instructions

beq
...
L1:
j
...
$t0, $t1, L1
L2
L2:
2301274
Chapter 3 Assembly Languages
34
Memory Addressing Modes

direct


register indirect



mem[content[reg]]
mem[content[address]]
register indirect displacement



mem[address]
mem[content[reg]+displacement]
mem[content[address]+displacement]
register indirect index and displacement
2301274
Chapter 3 Assembly Languages
35
MIPS Addressing Modes

Register addressing (R-format)

add $t0,$t1,$t2
op

rs
rt
rd
…
funct
Base (Displacement) addressing (I-format)

register
lw $t1, 12($t2)
op
rs
memory
rt
address
+
register

Immediate addressing (J-format)

addi $t0, $t1, 34
op
2301274
rs
rt
Immediate data
Chapter 3 Assembly Languages
36
MIPS Addressing Modes

PC-relative addressing (I-format)

beq $t0, $t1, label
op

rs
memory
rt
address
Pseudo-direct addressing

PC
j label
op
+
address
:
PC
2301274
Chapter 3 Assembly Languages
37