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

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