Transcript Document

CMPT 334 Computer Organization
Chapter 2
Instructions: Language of the Computer
[Adapted from Computer Organization and Design 5th Edition,
Patterson & Hennessy, © 2014, MK]
When: Tuesday, March 25 2:30PM
Where: RLC 105
Team based: one, two or three people per team
Languages: C/C++ and Java
IDEs: Visual Studio, Eclipse, NetBeans
Event Schedule
2:30 – 4:30 pm – Contest (RLC 105)
4:30 pm – Award Ceremony (RLC 203)
4:30 pm – Pizza Party (RLC 203)
Register your team in RLC 203 by March 24
(Find the registration list on the bulletin board)
Contact Dr. Val Kolesnikov or Dr. Tina Tian for
questions.
Programming Styles
• Procedures (subroutines, functions) allow the
programmer to structure programs making
them
▫ easier to understand and debug and
▫ allowing code to be reused
• Procedures allow the programmer to
concentrate on one portion of the code at a
time
▫ parameters act as barriers between the
procedure and the rest of the program and data,
allowing the procedure to be passed values
(arguments) and to return values (results)
Six Steps in Execution of a Procedure
1. Main routine (caller) places parameters in a
place where the procedure (callee) can access
them
▫
2.
3.
4.
5.
$a0 - $a3: four argument registers
Caller transfers control to the callee
Callee acquires the storage resources needed
Callee performs the desired task
Callee places the result value in a place where
the caller can access it
▫
$v0 - $v1: two value registers for result values
6. Callee returns control to the caller
▫
$ra: one return address register to return to the
point of origin
Instruction for Calling a Procedure
• MIPS procedure call instruction:
jal ProcAddress #jump and link
• Saves PC+4 in register $ra as the link to the
following instruction to set up the procedure
return
• Machine format:
op
3
26 bit address
????
• Then can do procedure return with just
jr $ra
#return
J format
Basic Procedure Flow
• For a procedure that computes the GCD of
two values i (in $a0) and j (in $a1)
gcd(i,j);
caller puts the i and j (the parameters
values) in $a0 and $a1 and issues a
jal gcd
#jump to routine gcd
 The
 The
callee computes the GCD, puts the result
in $v0, and returns control to the caller using
gcd: . . .
#code to compute gcd
jr $ra
#return
Spilling Registers
• What if the callee needs to use more registers
than allocated to argument and return values?
▫ callee uses a stack – a last-in-first-out queue
high addr
top of stack

$sp
One of the general registers, $sp
($29), is used to address the stack
(which “grows” from high address
to low address)

add data onto the stack – push
$sp = $sp – 4
data on stack at new $sp

low addr
remove data from the stack – pop
data from stack at $sp
$sp = $sp + 4
Compiling a C Leaf Procedure
• Leaf procedures are ones that do not call other
procedures. Give the MIPS assembler code for
int leaf_ex (int g, int h, int i, int j)
{
int f;
f = (g+h) – (i+j);
return f;
}
where g, h, i, and j are in $a0, $a1, $a2, $a3
• Leaf procedures are ones that do not call other
procedures. Give the MIPS assembler code for
int leaf_ex (int g, int h, int i, int j)
{ int f;
f = (g+h) – (i+j);
return f; }
where g, h, i, and j are in $a0, $a1, $a2, $a3
leaf_ex:
addi
sw
sw
add
add
sub
lw
lw
addi
jr
$sp,$sp,-8
$t1,4($sp)
$t0,0($sp)
$t0,$a0,$a1
$t1,$a2,$a3
$v0,$t0,$t1
$t0,0($sp)
$t1,4($sp)
$sp,$sp,8
$ra
#make stack room
#save $t1 on stack
#save $t0 on stack
#restore $t0
#restore $t1
#adjust stack ptr
Nested Procedures
• What happens to return addresses with nested
procedures?
int rt_1 (int i) {
if (i == 0) return 0;
else return rt_2(i-1); }
caller: jal rt_1
next:
. . .
rt_1:
to_2:
rt_2:
bne
add
jr
addi
jal
jr
$a0, $zero, to_2
$v0, $zero, $zero
$ra
$a0, $a0, -1
rt_2
$ra
. . .
Nested Procedures Outcome
caller:
jal rt_1
next: . . .
rt_1: bne $a0, $zero, to_2
add $v0, $zero, $zero
jr $ra
to_2: addi $a0, $a0, -1
jal rt_2
jr $ra
rt_2: . . .
the call to rt_1, the return address (next
in the caller routine) gets stored in $ra. What
happens to the value in $ra (when i != 0)
when rt_1 makes a call to rt_2?
 On
Saving the Return Address
• Nested procedures (i passed in $a0, return value
in $v0)
high addr
old TOS
$sp
low addr
rt_1:bne
add
jr
to_2:addi
sw
sw
addi
jal
bk_2:lw
lw
addi
jr
$a0,
$v0,
$ra
$sp,
$ra,
$a0,
$a0,
rt_2
$a0,
$ra,
$sp,
$ra
$zero, to_2
$zero, $zero
$sp, -8
4($sp)
0($sp)
$a0, -1
0($sp)
4($sp)
$sp, 8
$ra
• Save the return address (and arguments) on the
stack
Saving the Return Address
• Nested procedures (i passed in $a0, return value
in $v0) high addr
old TOS
 $sp
caller rt addr
old $a0
$sp
low addr
rt_1:bne
add
jr
to_2:addi
sw
sw
addi
jal
bk_2:lw
lw
addi
jr
$a0,
$v0,
$ra
$sp,
$ra,
$a0,
$a0,
rt_2
$a0,
$ra,
$sp,
$ra
$zero, to_2
$zero, $zero
$sp, -8
4($sp)
0($sp)
$a0, -1
0($sp)
4($sp)
$sp, 8
caller
bk_2 rt addr $ra
• Save the return address (and arguments) on the
stack
14
The Stack
The register scratchpad for a procedure seems volatile –
it seems to disappear every time we switch procedures –
a procedure’s values are therefore backed up in memory
on a stack
High address
Proc A
Proc A’s values
Proc B’s values
Proc C’s values
…
Stack grows
this way
Low address
call Proc B
…
call Proc C
…
return
return
return
15
Memory Organization
Stack
Dynamic data (heap)
Static data (globals)
Text (instructions)
MIPS Register Convention
Name
Register
Number
$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
Usage
the constant 0
returned values
arguments
temporaries
saved values
temporaries
global pointer
stack pointer
frame pointer
return address
Preserve
on call?
n.a.
no
yes
no
yes
no
yes
yes
yes
yes
Compiling a Recursive Procedure
• A procedure for calculating factorial
int fact (int n) {
if (n < 1) return 1;
else return (n * fact (n-1)); }
• A recursive procedure (one that calls itself!)
fact (0) = 1
fact (1) = 1 * 1 = 1
fact (2) = 2 * 1 * 1 = 2
fact (3) = 3 * 2 * 1 * 1 = 6
fact (4) = 4 * 3 * 2 * 1 * 1 = 24
...
• Assume n is passed in $a0; result returned in
$v0
fact:slti
beq
addi
jr
L1:
$t0, $a0, 1
$t0, $zero, L1
$v0, $zero, 1
$ra
#test for n < 1
#if n >=1, go to L1
#else return 1 in $v0
#return to caller (1st)
addi $sp, $sp, -8
sw
$ra, 4($sp)
sw
$a0, 0($sp)
#adjust stack pointer
#save return address
#save argument n
addi $a0, $a0, -1
jal fact
#n >=1, so decrement n
#call fact with (n-1)
#this is where fact returns
lw
$a0, 0($sp)
#restore argument n
lw
$ra, 4($sp)
#restore return address
addi $sp, $sp, 8
#adjust stack pointer
mul $v0, $a0, $v0
#$v0 = n * fact(n-1)
jr
$ra
#return to caller (2nd)
19
Dealing with Characters
• Instructions are also provided to deal with byte-sized
and half-word quantities: lb (load-byte), sb, lh, sh
• These data types are most useful when dealing with
characters, pixel values, etc.
• C employs ASCII formats to represent characters – each
character is represented with 8 bits and a string ends in
the null character (corresponding to the 8-bit number 0)
20
Example
Convert to assembly:
void strcpy (char x[], char y[])
{
int i;
i=0;
while ((x[i] = y[i]) != `\0’)
i += 1;
}
21
Example
Convert to assembly:
void strcpy (char x[], char y[])
{
int i;
i=0;
while ((x[i] = y[i]) != `\0’)
i += 1;
}
strcpy:
add $s0, $zero, $zero
L1: add $t1, $s0, $a1
lb
$t2, 0($t1)
add $t3, $s0, $a0
sb
$t2, 0($t3)
beq $t2, $zero, L2
addi $s0, $s0, 1
j
L1
L2: jr
$ra
Review: MIPS Instructions, so far
Category
Instr
Arithmetic add
(R & I
subtract
format)
add immediate
OpC
Example
Meaning
0 & 20 add $s1, $s2, $s3
$s1 = $s2 + $s3
0 & 22 sub $s1, $s2, $s3
$s1 = $s2 - $s3
8
addi $s1, $s2, 4
$s1 = $s2 + 4
shift left logical
0 & 00 sll
$s1, $s2, 4
$s1 = $s2 << 4
shift right
logical
0 & 02 srl
$s1, $s2, 4
$s1 = $s2 >> 4 (fill with
zeros)
shift right
arithmetic
0 & 03 sra $s1, $s2, 4
$s1 = $s2 >> 4 (fill with
sign bit)
and
0 & 24 and $s1, $s2, $s3
$s1 = $s2 & $s3
or
0 & 25 or
$s1 = $s2 | $s3
nor
0 & 27 nor $s1, $s2, $s3
$s1, $s2, $s3
$s1 = not ($s2 | $s3)
and immediate
c
and $s1, $s2, ff00
$s1 = $s2 & 0xff00
or immediate
d
or
$s1 = $s2 | 0xff00
load upper
immediate
f
lui $s1, 0xffff
$s1, $s2, ff00
$s1 = 0xffff0000
Review: MIPS Instructions, so far
Category
Instr
Data
transfer
(I format)
load word
23
lw
store word
2b
sw $s1, 100($s2) Memory($s2+100) = $s1
load byte
20
lb
$s1, 101($s2)
$s1 = Memory($s2+101)
store byte
28
sb $s1, 101($s2)
Memory($s2+101) = $s1
load half
21
lh
$s1, 101($s2)
$s1 = Memory($s2+102)
store half
29
sh $s1, 101($s2)
Memory($s2+102) = $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
set on less
than immediate
a
slti $s1, $s2,
100
if ($s2<100) $s1=1;
else $s1=0
Cond.
branch
(I & R
format)
set on less
than
Uncond.
jump
jump
jump register
jump and link
OpC
Example
0 & 2a slt
2
j
0 & 08 jr
3
jal
Meaning
$s1, 100($s2) $s1 = Memory($s2+100)
$s1, $s2, $s3 if ($s2<$s3) $s1=1;
else $s1=0
2500
go to 10000
$t1
go to $t1
2500
go to 10000; $ra=PC+4
Design Principles Review
• Simplicity favors regularity
▫ fixed size instructions – 32-bits
▫ small number of instruction formats
• Smaller is faster
▫ limited instruction set
▫ limited number of registers in register file
▫ limited number of addressing modes
• Good design demands good compromises
▫ three instruction formats
• Make the common case fast
▫ arithmetic operands from the register file (loadstore machine)
▫ allow instructions to contain immediate operands
The Code Translation Hierarchy
C program
compiler
assembly code
assembler
object code
Assembler
Does a syntactic check of the code (i.e., did you type it
in correctly) and then transforms the symbolic
assembler code into object (machine) code
• Advantages of assembler
▫ much easier than remembering instr’s binary codes
▫ can use labels for addresses – and let the assembler do
the arithmetic
▫ can use pseudo-instructions
 e.g., “move $t0, $t1” exists only in assembler (would be
implemented using “add $t0,$t1,$zero”)
• When considering performance, you should count
instructions executed, not code size
The Two Main Tasks of the Assembler
1.
Builds a symbol table which holds the symbolic
names (labels) and their corresponding addresses
▫
A label is local if it is used only within the file
where its defined. Labels are local by default.
▫
A label is external (global) if it refers to code or
data in another file or if it is referenced from
another file. Global labels must be explicitly
declared global (e.g., .globl main)
2. Translates each assembly language statement into
object (machine) code by “assembling” the numeric
equivalents of the opcodes, register specifiers, shift
amounts, and jump/branch targets/offsets
An Example
Gbl?
yes
yes
Symbol
Address
str
cr
main
loop
brnc
done
printf
1000 0000
1000 000b
0040 0000
0040 000c
0040 001c
0040 0024
...
str:
cr:
main:
loop:
brnc:
done:
.data
.asciiz "The answer is "
.asciiz "\n“
.text
.align 2
.globl main
.globl printf
ori
$2, $0,
syscall
move
$8, $2
beq
$8, $9,
blt
$8, $9,
sub
$8, $8,
j
loop
sub
$9, $9,
j
loop
jal
printf
5
done
brnc
$9
$8
29
Directives
File add.s
.text
.globl main
main:
addi $t0, $zero, 5
addi $t1, $zero, 7
add $t2, $t0, $t1
…
jal
swap_proc
jr
$ra
.globl swap_proc
swap_proc:
…
Stack
Dynamic data (heap)
Static data (globals)
Text (instructions)
This function is visible to other files
30
Labels
File add.s
.data
in1 .word 5
in2 .word 7
c1 .byte 25
str .asciiz “the answer is”
.text
.globl main
main:
lw
$t0, in1
lw
$t1, in2
add $t2, $t0, $t1
…
jal
swap_proc
jr
$ra
Stack
Dynamic data (heap)
Static data (globals)
Text (instructions)
31
System Calls
• SPIM/Mars provides some OS services: most useful are
operations for I/O: read, write, file open, file close
• The arguments for the syscall are placed in $a0-$a3
• The type of syscall is identified by placing the appropriate
number in $v0 – 1 for print_int, 4 for print_string,
5 for read_int, etc.
• $v0 is also used for the syscall’s return value
32
Service
print_int
print_string
read_int
exit
print_char
read_char
System Call
Arguments
Code
1
$a0 = integer
4
5
10
11
12
Results
$a0 = string
integer
(in $v0)
$a0 = char
char
(in $v0)
33
Example Print Routine
.data
str: .asciiz “the answer is ”
.text
li $v0, 4
# load immediate; 4 is the code for print_string
la $a0, str
# the print_string syscall expects the string
# address as the argument; la is the instruction
# to load the address of the operand (str)
syscall
# invoke syscall-4
li $v0, 1
# syscall-1 corresponds to print_int
li $a0, 5
# print_int expects the integer as its argument
syscall
# invoke syscall-1
34
Example
• Write an assembly program to prompt the user for two numbers and
print the sum of the two numbers
35
Example
.text
.globl main
main:
li $v0, 4
la $a0, str1
syscall
li $v0, 5
syscall
add $t0, $v0, $zero
li $v0, 5
syscall
add $t1, $v0, $zero
li $v0, 4
la $a0, str2
syscall
li $v0, 1
add $a0, $t1, $t0
syscall
.data
str1: .asciiz “Enter 2 numbers:”
str2: .asciiz “The sum is ”
36
Put it all together..
• Write a program to display the nth Fibonacci
number (n is from the user input).
▫ Build function fib(n)