Von Neumann and MIPS
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
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
3
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
4
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
5
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:
//push ($t1) into stack
//make room for 1 word in stack
addi $sp, $sp, -4
//store ($t1) into stack
sw $t1, 0($sp)
//push ($t2) into stack
//make room for 1 word in stack
addi $sp, $sp, -4
//store ($t1) into stack
sw $t2, 0($sp)
$sp
word 1
word 2
$sp
Before
word 1
word 2
($t1)
($t2)
After
7
Pushing elements (alternatively)
word 1
word 2
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
$sp
Before
word 1
word 2
($t1)
($t2)
After
8
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
9
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.
10
Memory Management (concerning Lab 4)
MMIO( Memory Mapped I/O) helps to interface between CPU and I/O peripherals
IN MARS, we can emulate pixels stored from 0xffff 000 connected to an external Bitmap display
Memory Management (concerning Lab 4)
NOTE: We are not drawing Mario in Lab4; just using him as an example!
Stacks, Static data… but what is the Heap?
Heap
■ Static memory is used for…
◆ global variable storage
◆ Put in .data section of code
◆ permanent for the entire run of the program
■ Stack memory is used for…
◆ Passing arguments to functions
◆ Returning values from functions
◆ Saving/restoring values in functions
◆ Dynamically allocating local variables in a function
■ Heap memory is used for…
◆ Dynamically allocating memory that persists throughout a program
★ For example, malloc in C, new in C++ (or Java) ◆ Stackmemorygoesawayafterafunctionreturns
The computer does not store different heap memory contents at consecutive locations, UNLIKE stack memory!
Remember C code syntax is not part of CSE12 syllabus! The only purpose here is to illustrate the concept of heap memory