Chapter 3: MIPS Instruction Set
Review
Instruction
Meaning
add $s1,$s2,$s3
sub $s1,$s2,$s3
$s1 = $s2 + $s3
$s1 = $s2 $s3
addi $s1,$s2,4
ori $s1,$s2,4
$s1 = $s2 + 4
$s2 = $s2 | 4
lw $s1,100($s2)
sw $s1,100($s2)
$s1 = Memory[$s2+100]
Memory[$s2+100] = $s1
bne $s4,$s5,Label Next instr is at Label if $s4 $s5
beq $s4,$s5,Label Next instr is at Label if $s4 = $s5
slt $t1,$s2,$s3
if $s2 < $s3, $t1 = 1 else $t1 = 0
j Label
Next instr is at Label
Pseudo-instructions
r The MIPS assembler supports several pseudo-
instructions
m Programmers
can use pseudo-instructions
m Assembler translates them into actual instructions
or sequences of instructions
r Example
move $7,$18
contents of $18 are copied to $7
is translated into
add $7, $18, $0
r
Remember: $0 always contains 0
Other Examples:
m
blt, seq, sle, la, li (See Appendix A for complete list)
3
The jr (jump register) instruction
jr $s1
# jump to address in $s1
r Usage
m Switch/Case statements
m Returning from procedures/functions
Using jr for implementing a switch statement
switch (k) {
case 0: f = i + j; break;
case 1: f = g + h; break
case 2: f = g h; break
}
Assume
1.
f, g, h, i, j are in registers $16 to $21, register $10
contains the constant 4
2.
In memory, the code for case 0 is at address L0, the code
for case 1 is at address L1, and the code for case 2 is at
address L2
3.
An array JumpTable has already been created with the
first word (at address JumpTable) containing L0, the
second word (address JumpTable + 4) containing L1, and
the third word (JumpTable + 8) containing L2
5
L0:
L1:
L2:
Exit:
mult
lw
jr
add
j
add
j
sub
$9, $21, $10
$8, JumpTable[$9]
$8
$16, $19, $20
Exit
$16, $17, $18
Exit
$16, $17, $18
# $9 = k*4
Supporting procedure calls
r jr instruction
m Returning from a procedure
r Jump and link (jal) instruction
m Jump to address of procedure, while storing
the return address in register $31 ($ra)
What is the return address?
PC + 4
In MIPS, a special register called Program Counter
(PC) contains the address of the instruction currently
being
m jal
addr stores PC+4 in register $31, and then
jumps to location addr
m To return from the procedure, we can simply
execute jr $31
Supporting procedure calls (contd)
r
Passing arguments/parameters
m
Returning results
m
Parameters are passed in registers $4 - $7 ($a0 - $a3)
Results are returned in register $v0
Example
procA:
<code for procedure procA>
move $a0, $s1
# assume parameter for
# proc B is in register $s1
jal
procB
<more code for procedure procA>
jr
$ra
procB:
< code for procedure procB>
move $v0, $t1
# move result to $v0
jr
$ra
8
Supporting procedure calls (contd)
r
Problems:
m
What if procB calls another procedure?
Contents of $ra will be overwritten!
What if we have more than 4 parameters?
Solution:
m
Use stack in main memory for storing
1. Parameters (if procedure has more than 4)
2. Any registers that need to be preserved across procedure
calls, I.e. registers that should have the same values
before and after the procedure call
The stack is an area of memory that grows and
shrinks dynamically.
m
Register $29 ($sp) points to the top location of the
stack, I.e. register $29 is used as the stack pointer
9
Example: preserving registers across procedure calls
A:
B:
C:
jal B
addi
sw
jal
lw
addi
jr
jr
$sp, $sp,-4
$ra, 0($sp)
C
$ra, 0($sp)
$sp, $sp,4
$ra
} Save $ra on stack
} Restore $ra from stack
NOTE: In MIPS, the stack grows
downwards
$ra
10
1. After A calls B
Bs return
address
Memory
$ra
Top of stack
Bottom of stack
$sp
11
2. Just before B calls C
Bs return
address
$ra
Memory
New Top of stack
Bottom of stack
$sp
12
3. After B calls C
Cs return
address
Bs return
address
Memory
$ra
Top of stack
Bottom of stack
$sp
13
4. Just before B returns
Bs return
address
Memory
$ra
New Top of stack
Bottom of stack
$sp
14
Using the stack to save registers
Highaddress
$sp
$sp
Contents of register $t1
Contents of register $t0
$sp
Lowaddress
a.
Contents of register $s0
b.
c.
15
Procedure frames are pushed and
popped off the stack
High addres s
$fp
$fp
$sp
$sp
$fp
Saved argument
registers (if any)
Saved return address
Saved saved
registers (if any)
Local arrays and
structures (if any)
$sp
Low address
a.
b.
c.
16
Contents of a procedure frame
Higher memory addresses
Argument 6
Argument 5
$fp
Saved registers
Stack
grows
Local variables
$sp
Lower memory addresses
17
Why do running programs need a stack?
Modern programming
languages are
recursive
r Example: Factorial
program is recursive
r
Has a separate frame
for each invocation of
factorial()
Stack
Old $ra
Old $fp
main
Old $ra
Old $fp
Old $a0
fact (10)
Old $ra
Old $fp
Old $a0
fact (9)
Old $ra
Old $fp
Old $a0
fact (8)
Old $ra
Old $fp
Old $a0
fact (7)
Stack grows
18
Address space for a running program
Address Space =
Memory allocated to
program
r 3 segments
$sp
7ff f ffff
$gp
1000 8000
hex
m
m
Text (code)
Data
Static data
Dynamic data
Stack
Stack
Dynamic dat a
hex
1000 0000
hex
0040 0000
he x
Static data
Text
pc
Reserved
0
19
Conventions for saving and restoring registers
across procedure calls
r If a procedure modifies any registers
that are used by calling routine, some
convention is needed for saving &
restoring registers
1.
2.
3.
Caller save: calling procedure saves and
restores any registers that must be preserved
across the call
Callee save: called procedure saves and
restores any registers that it might use
MIPS convention: some registers are caller
saved and some registers are callee saved
20
10
MIPS procedure call convention
r
Caller:
1.
2.
3.
Callee: (before it starts running)
1.
2.
3.
Pass arguments. First 4 are in $a0-$a3. Remaining are
pushed on to stack and appear at the beginning of called
procedures stack frame
Save caller-saved registers ($a0-$a3,$t0 -$t9)
Execute jal
Allocate memory for stack frame
Save callee-saved registers in the stack frame ($s0$s7,$fp,$ra)
Establish frame pointer
Callee: (before returning)
1.
2.
3.
4.
Place return value in $v0
Restore all callee-saved registers
Pop the stack frame
Return by jumping to $ra
21
MIPS Assembly Language
r Assembler Directives
.allign n
e.g. .allign 2
.asciiz <str>
.data <addr>
See Appendix A for more
details and examples
.space n
.text
.globl
r System Calls for Input/Output
1. Load system call code into register $v0 and
arguments into $a0-$a3
See Figure A.17
2. Execute syscall
22
11
Assignment 2
Assignment 2: matrix multiplication
m Multiply
M1 (r1 rows, c1 columns) and M2 (r2 rows,
c2 columns) to obtain Mr (r1 rows, c2 columns)
Note c1 = r2
m Three
procedures
Main()
Matrix_multiply(r1,c1,M1,r2,c2,M2,Mr)
Inner_product(row,num_columns,M,column,num_rows,N)
m Need
to use the stack
for saving & restoring registers
Passing parameters
m Matrices
stored in single dimensional array using
row-major organization
23
Matrix Multiplication
Inner Product
n
Cij
ik
Bkj
k =1
n is the number of columns
in matrix A, and the
number of rows in matrix B
24
12
