Von Neumann and MIPS
MIPS register saving conventions in
function call
MIPS uses conventions again to split the register spilling chores. The caller is responsible for saving and restoring any of the
following caller-saved registers that it cares about.
$t0-$t9 $a0-$a3 $v0-$v1
In other words, the callee may freely modify these registers, under the assumption that the caller already saved them if necessary.
The callee is responsible for saving and restoring any of the following callee-saved registers that it uses. (Remember that $ra is “used” by jal.)
$s0-$s7 $ra
Thus the caller may assume these registers are not changed by the callee.
– $ra is tricky; it is saved by a callee who is also a caller.
Be especially careful when writing nested functions, which act as both a caller and a callee!
2
Register spilling example
This convention ensures that the caller and callee together save all of the important registers—frodo only needs to save registers
$a0 and $a1, while gollum only has to save registers $s0 and
$s2.
frodo:
li $a0, 3 li $a1, 1 li $s0, 4 li $s1, 1
# Save register values to #stack
# $a0, $a1
jal gollum
# Restore registers # $a0 and $a1
add $v0, $a0, $a1 add $v1, $s0, $s1
gollum:
jal gollum
# Save registers # $s0,$s2
li $a0, 2 li $a2, 7
li $s0, 1
li 8 …
# Save $ra,$a0 & $a2
jal gollumson
# Restore registers
# $a0 & $a2
…
# Restore $s0,$s2,$ra jr $ra
3
Where are the registers saved?
Now we know who is responsible for saving which registers, but we still need to discuss where those registers are saved.
It would be nice if each function call had its own private memory area.
– This would prevent other function calls from overwriting our saved registers.
– We could use this private memory for other purposes too, like storing local variables.
4
Stack
• A type of Data Structure
• You can “Push” or “Pop” a data item from this data structre
• Need to keep track of the top of the stack (TOS)
• LIFO: Last In First Out
• Push (item#) – if you want to push a specific date item# into stack
• TOS- indicates the current height of the stack
• Pop() – pop off the data item from TOS
A “Stack” of books
• Push book 1
• Push book 2
• Push book 3
• Push book 4
• Push book 5
BOOK 5
BOOK 4
BOOK 3
BOOK 2
BOOK 1
A “Stack” of books
• Push book 1
• Push book 2
• Push book 3
• Push book 4
• Push book 5
• Pop
• Pop
• Pop
• Pop
• Pop
BOOK 5
BOOK 4
BOOK 3
BOOK 2
BOOK 1
Function calls and stacks
Notice function calls and returns occur in a stack-like order: the most recently called functionis thefirstonetoreturn.
1
2
6
5
A: …
jal B A2: …
jr $ra
1. 2. 3. 4. 5. 6.
Someone calls A
A calls B
B calls C
C returns to B
B returns to A
A returns
B: …
jal C B2: …
jr $ra
Here, for example, C must return to B before B
can return to A. 3
C: …
jr $ra
4
C’ stackframe
B’ stackframe
A’s stackframe
8
Function calls and stacks
Notice function calls and returns occur in a stack-like order: the most recently called functionis thefirstonetoreturn.
1
2
6
5
A: …
jal B A2: …
jr $ra
1. 2. 3. 4. 5. 6.
Someone calls A
A calls B
B calls C
C returns to B
B returns to A
A returns
B: …
jal C B2: …
jr $ra
Here, for example, C must return to B before B
can return to A. 3
C: …
jr $ra
4
C’ stackframe
B’ stackframe
A’s stackframe
9
Program Stack
It’s natural to use a stack for function call storage. A block of stack space, called a stack frame, can be allocated for each function call.
– When a function is called, it creates a new frame onto the stack, which will be used for local storage.
– Before the function returns, it must pop its stack frame, to restore the stack to its original state.
The stack frame (so called “activation frame” or “activation record”) can be used for several purposes.
– Caller- and callee-save registers can be put in the stack.
– The stack frame can also hold local variables such as arrays, or extra
arguments and return values.
Prologue (entering the function): Allocates an activation frame on the
stack
Epilogue (exit from function): De-allocates the frame, does actual return
10
The MIPS stack
In MIPS machines, part of main memory is reserved for a stack.
– The stack grows downward in terms of memory addresses.
– The address of the top element of the stack (TOS) is stored (by convention) in the “stack pointer” register, $sp
MIPS does not provide “push” and “pop” instructions. Instead, they must be done explicitlybythe programmer.
Pushing elements
To push elements onto the stack:
– Move the stack pointer $sp down to
make room for the new data.
– Store the elements into the stack.
For example, to push registers $t1 and $t2 onto the stack:
addi $sp, $sp, -8
sw $t1, 4($sp)
sw $t2, 0($sp)
An equivalent sequence is:
sw $t1, -4($sp)
sw $t2, -8($sp)
addi $sp, $sp, -8
Before and after diagrams of the stack are shown on the right.
$sp
word 1
word 2
$sp
Before
word 1
word 2
($t1)
($t2)
After
12
Accessing and popping elements
You can access any element in the stack (not just the top one) if you know where it is relative to $sp.
For example, to retrieve the value of $t1:
lw $s0, 4($sp)
You can pop, or “erase,” elements simply by adjusting the stack pointer upwards.
To pop the value of $t2, yielding the stack shown at the bottom:
addi $sp, $sp, 4
Note that the popped data is still present in memory, but data past the stack pointer is considered invalid.
word 1
word 2
($t1)
($t2)
$sp
word 1
word 2
($t1)
($t2)
$sp
13
Summary
Today we focused on implementing function calls in MIPS.
– We call functions using jal, passing arguments in registers $a0-
$a3.
– Functions place results in $v0-$v1 and return using jr $ra.
Managing resources is an important part of function calls.
– To keep important data from being overwritten, registers are saved according to conventions for caller-save and callee-save registers.
– Each function call uses stack memory for saving registers, storing local variables and passing extra arguments and return values.
Assembly programmers must follow many conventions. Nothing prevents a rogue program from overwriting registers or stack memory used by some other function.
16