CS计算机代考程序代写 prolog mips assembler c/c++ assembly Von Neumann and MIPS

Von Neumann and MIPS

Midterm May 19th
• Same format as Quiz 1 and 2 (asynchronous, no
proctoring, open textbook and notes)
• Syllabus: Lec 1-18.pdf (fractions not included!)
• Duration: Approx 80 minutes ( will let you know the exact time before the exam date)

Data Layout

Where does the data come from?
■ Data is arranged in memory
■ Data can be initialized when a program starts (.data)
◆ Must be stored in the program with the instructions ■ Data may be not-initialized (or actually just zeroed) (.bss) ◆ This doesn’t need to be stored in the program itself
■ Data may be created during execution ◆ More later in the course!

Code and Data Addresses
■ The code (text) segment starts at 0x0040_0000
◆ Each instruction is 4 bytes ■ The data segment starts at
0x1001_0000
◆ Data is placed at next adjacent location
■ Both grow “up”
■ What is the limit of my program
size?
■ What is the limit of my data size?

Data Declarations
.data
var1: .word 3
# All of this will go in the “data” segment of memory # create a single integer variable with initial value 3
# create a 2-element character array
# initialized to ASCII a and b
array1: .byte ‘a’,’b’
half1: .half 0x1234 # create 16-bit word
array2: .space 40 # allocate 40 consecutive bytes, with storage # uninitialized
string1: .asciiz “Hello!\n” # string variable with end null string2: .ascii “Hello!\n” # string variable with NO end null

Data Segment Layout (Packing)
■ Memory is arranged least significant byte first ◆ .align directive can force alignment
.data
var1: .word 3 array1: .byte ’a’,’b’
half1: .half 0x1234 string1:.asciiz “Hello!\n”
Address
0x1001_0000
0x1001_0001
0x1001_0002
0x1001_0003
0x1001_0004
0x1001_0005
0x1001_0006
0x1001_0007
0x1001_0008
0x1001_0009
0x1001_000A
0x1001_000B
0x1001_000C
0x1001_000D
0x1001_000E
0x1001_000F
Value
03
00
00
00
a
b
34
12
H
e
l
l
o
!
\n
00

Computing Data Addresses
.data
var1: .word 3 array1: .byte ’a’,’b’
half1:
.half 0x1234
■ If data segment starts at 0x1001_0000… ◆ Whatisvar1?
◆ Whatisarray1? ◆ Whatishalf1?
Label
Address
Value
var1
0x1001_0000
03
0x1001_0001
00
0x1001_0002
00
0x1001_0003
00
array1
0x1001_0004
61 (a)
0x1001_0005
62 (b)
half1
0x1001_0006
34
0x1001_0007
12
Spaces or new lines don’t matter!

Arrays
■ Arrays are a continuous sequence of identical elements
◆ Elementscanbeanysize:byte,half word, word, or bigger
◆ Stringsareanarrayofcharacters ■ Remember iterating over a sequence

Array of Integers (4 bytes)
.data
list:
.word 3, 0, 1, 2, 6, -2, 7, 3, 7
# in C/C++, this is equivalent to :
# int list[ ]={3, 0, 1, 2, 6, -2, 7, 3, 7};
#Array index:
#the index of ANY array always begins from 0
#in C/C++, to access ith element of an array (list in example), #we say ‘list[ i ]’
#therefore, in given example #list[ 0 ]= 3
#list[ 1 ]= 0
#list[ 2 ]= 1
#list[ 3 ]= 2 #list[ 4 ]= 6 #list[ 5 ]= -2 #list[ 6 ]= 7 #list[ 7 ]= 3 #list[ 8 ]= 7
Address
Value
0x1001_0000
0x 03
0x1001_0001
0x 00
0x1001_0002
0x 00
0x1001_0003
0x 00
0x1001_0004
0x 00
0x1001_0005
0x 00
0x1001_0006
0x 00
0x1001_0007
0x 00
0x1001_0008
0x 01
0x1001_0009
0x 00
0x1001_000A
0x 00
0x1001_000B
0x 00
0x1001_000C
0x 02
0x1001_000D
0x 00
0x1001_000E
0x 00
0x1001_000F
0x 00
………..
……..

Iterating over a String (Array of
Characters)
.text: init:
la $t0, hello_string
loop_start:
lb $t2, ($t0)
beq $t2, 0, loop_end
loop_body:
move $a0, $t2
li $v0, 11
syscall update:
addi $t0, $t0, 1
b loop_start
loop_end:
nop .data
hello_string:
.asciiz “Hello World!”

Accessing Array of Byte elements
.data
list:
.byte 3, 0, 1, 2, 6, -2, 7, 3, 7 #equivalent to list[3]=2 in C/C++
Address
Value
0x1001_0000
0x 03
0x1001_0001
0x 00
0x1001_0002
0x 01
0x1001_0003
0x 02
0x1001_0004
0xFE (-2inhex2s Compliment)
0x1001_0005
0x 07
0x1001_0006
0x 03
0x1001_0007
0x 07
.text
la $t3, list
li $t2, 3
add $t1, $t2, $t3
lw $t4, 0($t1)
# put address of list into $t3 # put the index into $t2
# combine the two parts of the #address
# get the value from the array cell

Accessing Array of Integers (4 bytes)
.data
list:
.word 3, 0, 1, 2, 6, -2, 7, 3, 7#equivalent to list[3]=2 in C/C++
Address
Value
0x1001_0000
0x 03
0x1001_0001
0x 00
0x1001_0002
0x 00
0x1001_0003
0x 00
0x1001_0004
0x 00
0x1001_0005
0x 00
0x1001_0006
0x 00
0x1001_0007
0x 00
0x1001_0008
0x 01
0x1001_0009
0x 00
0x1001_000A
0x 00
0x1001_000B
0x 00
0x1001_000C
0x 02
0x1001_000D
0x 00
0x1001_000E
0x 00
0x1001_000F
0x 00
………..
……..
.text
la $t3, list
li $t2, 3
sll $t2, $t2, 2
add $t1, $t2, $t3
#address
lw $t4, 0($t1)
# put address of list into $t3
# put the index into $t2
# Multiple index by 4 (1 word is 4 bytes)
# combine the two parts of the
# get the value from the array cell

Functions

Functions calls in MIPS
 We’ll talk about the 3 steps in handling function calls:
1. Theprogram’sflowofcontrolmustbechanged.
2. Argumentsandreturnvaluesarepassedbackandforth. 3. Localvariablescanbeallocatedanddestroyed.
 And how they are handled in MIPS:
– New instructions for calling functions.
– Conventions for sharing registers between functions.
– Use of a stack.
15

Control flow in C
 Invoking a function changes the control flow of a program twice.
1. Calling the function
2. Returning from the function
 In this example the main function calls fact twice, and fact returns twice—but to different locations in main.
 Each time fact is called, the CPU has to remember the appropriate return address.
 Notice that main itself is also a function! It is called by the operating system when you run the program.
int main() {

t1 = CalcCube(8); t3 = t1 + t2;
t2 = CalcCube(3); …
}
int CalcCube (int n) {
int f ;
f = n * n *n ;
return f;
}
16

Control flow in MIPS
 MIPS uses the jump-and-link instruction jal to call functions.
– The jal saves the return address (the address of the next instruction) in the dedicated register $ra, before jumping to the function.
– jal is the only MIPS instruction that can access the value of the program counter, so it can store the return address PC+4 in $ra.
jal CalcCube
 To transfer control back to the caller, the function just has to jump to the address that was stored in $ra.
jr $ra
 Let’s now add the jal and jr instructions that are necessary for our factorial example.
17

Changing the control flow in MIPS
int main()
{

jal CalcCube;

t3 = t1 + t2;

jal CalcCube;
… }
int CalcCube (int n)
{
int f ;
f = n * n *n ;
jr $ra;
}
18

Data flow in C
 Functions accept arguments
 The black parts of the program show the actual and formal arguments of the fact function.
 The purple parts of the code deal with returning and using a result.
int main() {

t1 = CalcCube(8); t3 = t1 + t2;
t2 = CalcCube(3); …
}
int CalcCube (int n) {
int f ;
}
f = n * n *n ;
return f;
and produce return values.
44

Main: #Caller function
# Initialize registers for mem addresses addi $t5, $zero, 5000
addi $t6, $zero, 5004
# Compute cube of 3
addi $t0, $zero, 3 # Pass argument of 3 jal CalcCube # Call CalcCube
sw $t1, 0($t5) # Store result to
mem[5000]
# Compute cube of 17
addi $t0, $zero, 17 # Pass argument of 17 jal CalcCube # Call CalcCube
sw $t1, 0($t6) # Store result to
mem[5004]
j Done
CalcCube: #Callee function
# $t0 is subroutine argument
# $t1 is subroutine return value mul $t1, $t0, $t0
mul $t1, $t1, $t0
jr $ra # Return from
Done:
subroutine
Simple function example: CalcCube
NOTE: Here, we assumed that the same author wrote both main and CalcCube function !
Thus, we can keep track of the values of each register

The reality of writing functions in general
 In the typical “black box” programming approach, the caller and callee do not know anything about each other’s implementation.
– Different functions may be written by different people or companies.
– A function should be able to interface with any client, and different implementations of the same function should be substitutable.

Daily IssuesTM…. A new comic strip

Data flow in MIPS
 MIPS uses the following conventions for function arguments and results.
– Up to four function arguments can be “passed” by placing them in argument registers $a0-
$a3 before calling the function with jal.
– A function can “return” up to two values by placing them in registers $v0-$v1,
before returning via jr.
 These conventions are not enforced by the hardware or assembler, but programmers agree to them so functions written by different people can interface with each other.
 Later we’ll talk about handling additional arguments or return values.
23

Leaf vs Non Leaf functions
 Leaf functions
– Does not call other functions (only behaves like a callee)
– No need to save and restore $ra
 Non- Leaf functions
– Calls other functions (behaves like a callee to parent function and a caller to its child
function)
– Must save and restore $ra (done through the entity called Stack, explained later)
f1
f2
f4
.text section of main memory
f3
f5
Here, f2, f4, f6 are leaf functions
A call sequence f1->f3->f5->f6 would be called a nested function call
f6

Nested functions
A: …
# Put B’s args in $a0-$a3
jal B #$ra=A2
A2: …
 What happens when you call a functionthatthen callsanother function?
 Let’s say A calls B, which calls C.
– The arguments for the call to C would be placed in
$a0-$a3, thus overwriting the original arguments for B.
– Similarly, jal C overwrites the return address that was saved in $ra by the earlier jal B.
B: …
# Put C’s args in $a0-$a3, # erasing B’s args!
jal C #$ra=B2
B2: …
jr $ra # Where does
# this go???
C: …
jr $ra
46

Spilling registers
 The CPU has a limited number of registers for use by all functions, and it’s possible
that several functions will need the same registers.
 We can keep important registers from being overwritten by a function call, by saving
them before the function executes, and restoring them after the function completes.
 But there are two important questions.
– Who is responsible for saving registers—the caller or the callee? – Where exactly are the register contents saved?
26

Who saves the registers to main memory?
 However, in the typical “black box” programming approach, the caller and callee do not know anything about each other’s implementation.
– Different functions may be written by different people or companies.
– A function should be able to interface with any client, and different
implementations of the same function should be substitutable.
 Who is responsible for saving important registers across function calls?
– The caller knows which registers are important to it and should be saved.
– The callee knows exactly which registers it will use and potentially overwrite.
 So how can two functions cooperate and share registers when they don’t know anything about each other?
27

The caller could save the registers…
 One possibility is for the caller to save any important registers that it needs before making a function call, and to restore them after.
 But the caller does not know what registers are actually written by the function, so it may save more registers than necessary.
 In the example on the right, frodo wants to preserve $a0,
•$a1, $s0 and $s1 from gollum, but gollum may not even use those registers.
frodo: li li li li
$a0, 3 $a1, 1 $s0, 4 $s1, 1
# Save registers to memory
# $a0, $a1, $s0, $s1
jal gollum
# Restore registers # $a0, $a1, $s0, $s1
add $v0, $a0, $a1 add $v1, $s0, $s1 jr $ra
49

…or the callee could save the registers…
 Another possibility is if the callee saves and restores any registers it might overwrite.
 For instance, a gollum function that uses registers $a0, $a2, $s0 and $s2 could save the original values first, and restore them before returning.
 But the callee does not know what registers are important to the caller, so again it may save more registers than necessary.
gollum:
# Save registers # $a0 $a2 $s0 $s2
li $a0, 2 li $a2, 7 li $s0, 1 li $s2, 8 …
# Restore registers # $a0 $a2 $s0 $s2
jr $ra
29

…or they could work together
 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!
30

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
31

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.
32

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
4
C: …
jr $ra
33

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
34

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 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
36

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
37

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.
40