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