CS计算机代考程序代写 data structure prolog mips assembly Von Neumann and MIPS

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