Transcript Ch. 8 Functions slides

Ch. 8 Functions
Functions

High-level languages have functions (methods)
–
–
–

2
For modularity – easier to change
To eliminate duplication of code – code reuse
allows different programmers to write different parts
of the same program
Assembly language programs have similar
structure
Comp Sci 251 -- functions
High-level function example
void helloWorld(){
print("Hello, world");
}
void main(){
helloWorld();
. . .
}
3
Comp Sci 251 -- functions
Mechanism for implementing functions
Steps in the invocation and execution of a
function:
 save return address
 call the function
 execute the function
 return
4
Comp Sci 251 -- functions
Machine Language mechanism

What is the return address?
–

What is the function call?
–

jump or branch to first instruction in the function
What is a return?
–
5
Address of the instruction following call
jump or branch to return address
Comp Sci 251 -- functions
Functions in assembly language
6

Labels to name functions

Instructions to support function call & return

System stack to track pending calls

Programming conventions for parameter
passing
Comp Sci 251 -- functions
MIPS function example
.text
# Prints the string
# "Hello, world"
helloWorld:
la $a0, hello
li
$v0, 4
syscall
jr $ra
7
__start:
jal helloWorld
...
.data
hello: .asciiz "Hello,
world"
Comp Sci 251 -- functions
Assembly language functions

Function name Label on first instruction

Function call:
Jump And Link instruction:
jal label


8
Jump to label
Save return address in $ra
Comp Sci 251 -- functions
Assembly language functions

Return from function
Jump Register instruction:
jr Rsrc
Jump to the address in the register
jr $ra  jump to return address
9
Comp Sci 251 -- functions
Code Review

10
See helloFunc.a in /shared/huen/251
Comp Sci 251 -- functions
Complications:

What if function calls another function?
–
–

What if a function modifies some registers?
–

–
–
11
Should it restore the original values before returning?
Solution:
–

Must keep track of multiple return addresses
There is only one $ra i.e. $31
have a way to save return addresses as they are generated
This data is generated dynamically; while the program is running.
These return addresses will need to be used (for returning) in the
reverse order that they are saved.
use system stack
Comp Sci 251 -- functions
Program memory model
0x00000000 Reserved
Memory contains three
important segments
 Text segment: program
instructions
 Data segment: global
variables & constants
 Stack segment:
arguments & local
variables
12
0x00400000 Text segment
0x10000000 Data segment
0x7FFFEFFC Stack segment
0x80000000 Operating
0xFFFFFFFF system
Comp Sci 251 -- functions
System stack

Stack: Last-in-first-out (LIFO)
data structure
–
–

Implementation
–
–
–
–
13
Push: place a new item on the top
Pop: remove the top item
Stack segment of memory holds
stacked items
Each item is one word
$sp register points to top of stack
Stack grows toward low
addresses
$sp
Stacked
items
Comp Sci 251 -- functions
Stack operations

Low
Push $t0 to top of
stack:
subu $sp, $sp, 4
sw
$t0, ($sp)
word
$sp

Pop top of stack to $t0:
lw
$t0, ($sp)
addu $sp, $sp, 4
High
14
Comp Sci 251 -- functions
Example: Problem - stack1.a
Problem:
Count the number of negative integers on the
stack by popping the stack until a nonnegative integer is found, and print out the
number of words popped.

15
Comp Sci 251 -- functions
Example: Solution stack1.a

Integers from an array are first pushed onto the stack
–
–
–
16
Then the integers are popped and checked in turn until a
non-negative integer is encountered
Prints out the count
The program portion to be written should be independent of
the data and the rest of the program given
Comp Sci 251 -- functions
.text
.globl __start
__start:
la
$t0, test
lw
$t1, num
loop: lw
$t2, ($t0)
subu
$sp, $sp, 4
sw
$t2, ($sp)
add
$t0, $t0, 4
add
$t1, $t1, -1
bnez $t1, loop
#
#
#
#
#
#
#
#
#
#
17
# execution starts here
# This code sets up the stack
# Do not alter
# push stack w/ integers
# from test array
# Stack is set up now....
At this point, the stack looks somewhat like
the following but in hexadecimal of course:
$sp ->|
-9|
|
-4|
|
-3|
|0xfffabfff|
|0xffffffd5|
|
2|
| etc.
|
Put your answer between dashed lines.
Comp Sci 251 -- functions
# loop to pop the stack and count
# Put your answer between dashed lines.
#-------------- start cut -----------------------
next:
li
lw
addu
bgez
addi
j
$t3,
$t2,
$sp,
$t2,
$t3,
next
0
($sp)
$sp, 4
done
$t3, 1
# count = 0;
# pop the stack
# encounter non-negative
# count++
# At this point, the stack looks somewhat like
# the following but in hexadecimal of course:
#
|
-9|
#
|
-4|
#
|
-3|
#
|0xfffabfff|
#
|0xffffffd5|
# $sp ->|
2|
#
| etc.
|
#
done:
18
Comp Sci 251 -- functions
Example 2 stack2.a



19
The stack is set up with integers and the top
of stack contains the number of integers
Required to find the sum of integers on the
stack
The top of stack number should not be
included.
Comp Sci 251 -- functions
Use of system stack






20
Stores temporary information
Key support for functions
Pending function calls
Saved register values
Parameters
Local variables
Comp Sci 251 -- functions
Functions that call functions
f:
jal g
jr $ra

#call g
#return
–

g:
jr $ra
__start:
jal f
21
Main calls f
f calls g
–
#return
#call f


$ra = return addr. to main
$ra = return addr. to f
Problem:
return addr. to main lost.
Solution?
Comp Sci 251 -- functions
Functions that call functions
f:
# push $ra
subu $sp, $sp, 4
sw
$ra, ($sp)
. . .
jal g
#call g
. . .
# pop $ra
lw
$ra, ($sp)
addu $sp, $sp, 4
. . .
jr
$ra # f return
22
g:
. . .
jr
$ra
_start:
jal f
# g return
#call f
Comp Sci 251 -- functions
Leaf vs. non-leaf functions

Leaf function:
–
–

Non-leaf function:
–
–
23
Does not call other functions
No need to save & restore $ra
Calls other functions
Must save & restore $ra (use the stack)
Comp Sci 251 -- functions
MIPS function structure
24

Prologue: push items on stack

Body: do required computation

Epilogue: pop items off stack & return
Comp Sci 251 -- functions
What items must be stacked?
25

$ra (if function is non-leaf)

Some registers…

But not others…
Comp Sci 251 -- functions
MIPS register conventions





26
Callee-saved registers
$s0 -- $s7, $ra, $sp, $fp
All functions must guarantee:
value upon return == value before call
Caller-saved registers: $t0--$t9
Functions may freely modify these $t_ registers
Caller must save these registers $t_ if values will be
re-used after the call
Comp Sci 251 -- functions
Return value

Some functions return a value

MIPS register convention:
use $v0
27
Comp Sci 251 -- functions
Functions with parameters



28
Parameters are special local variables
Initial values come from arguments
More MIPS register conventions
Arguments: $a0 -- $a3
Comp Sci 251 -- functions
Example: Vowel Count -1


Count the number of vowels in a string str
Main program
–
–

function vcount( address of String str)
–
–

Checks one char at a time for vowel
returns the number of vowels in str
function vowelp( char c)
–
29
Call vcount with the address of str
Print the return value
Returns 1 if c is a vowel, 0 if not
Comp Sci 251 -- functions
Example: vowel count -2

Main program
–
–
–
–
30
a0 points to str
Calls vcount passing a0
Print answer
Terminate the program
Comp Sci 251 -- functions
Example: vowel count-3

Function Vcount
– Input: a0 holds address of str
– Internal: s0 holds number of vowels, i.e. count
–
s1 points to a character in str
– Output: v0 holds result
s1
Long time ago in a galaxy far away
Pseudo code
count = 0;
set s1 to point to first character in str and call the character c
while (c != 0) {
count += vowelp( c ); // call another function vowelp
move s1 to point to next character and call it c
}
Done: return count;

31
Comp Sci 251 -- functions
Example: vowel count-4

Function int vowelp(char c)
result = 0;
if c == ‘a’ result = 1;
if c == ‘e’ result = 1;
if c == ‘i’ result = 1;
if c == ‘o’ result = 1;
if c == ‘u’ result = 1;
return result;
32
Comp Sci 251 -- functions
Example: vowel count- 5

33
Integrate all together in vowel.a
Comp Sci 251 -- functions
Local variables

Global variables (static allocation)
–
–

Local variables (dynamic allocation)
–
–
–
34
Accessible throughout entire program execution
Exist in data segment
Created upon function call
Deleted upon function return
Where? How to access them?
Comp Sci 251 -- functions
Local variables

Implement locals on the stack
–
–
Reserve space in prologue
Release it in epilogue
$sp
Local
Variables
Saved
registers
35
Comp Sci 251 -- functions
Example: Translate to MIPS
int sum(){
int x;
int y;
Stack:
x = read int;
y = read int;
return x + y;
}
36
y
x
$sp
Saved
registers
Comp Sci 251 -- functions
Stack frame

Data on the stack associated w/
function call
–
–

$sp
$fp
Use register to point to fixed point
in the stack frame
–
–
–
37
Saved registers
Local variables
$sp may change during function call
Use $fp (frame pointer) to access
locals
$fp is callee-save
(like $ra and s-registers)
}
Local
Variables
Saved
registers
Stack
frame
Comp Sci 251 -- functions
Re-work example w/ $fp
# prologue
subu $sp, $sp, 12
sw
$fp, 8($sp)
addu $fp, $sp, 8
# epilogue
lw
$fp, 0($fp)
addu $sp, $sp, 12
jr $ra
#create frame
#save old $fp
#set up $fp
# restore $fp
# remove frame
y
$sp
$fp

38
x
old $fp
Exercise: re-work function body w/ $fp
Comp Sci 251 -- functions
Functions with parameters



39
Parameters are special local variables
Initial values come from arguments
More MIPS register conventions
Arguments: $a0 -- $a3
Comp Sci 251 -- functions
Example function w/ parameters
int power(int base, int exp){
int result = 1;
int i;
i
for(i = 0; i < exp; i++)
result *= base;
return result;
result
exp
}



40
base
Sketch stack frame
Write prologue & epilogue
Write function body
$fp
old $fp
Comp Sci 251 -- functions
Example function w/ parameters
#prologue
subu $sp,
sw
$fp,
addu $fp,
sw
$a0,
sw
$a1,
$sp, 20
16($sp)
$sp, 16
-4($fp)
-8($fp)
#epilogue
lw
$fp, 0($fp)
addu $sp, $sp, 20
jr
$ra
$sp
# base
# exp
result
exp
base
$fp
Old $sp
41
i
old $fp
Prev frame
Comp Sci 251 -- functions
Non-leaf function with parameters
int power(int base, int exp){
int result;
result
if(exp == 0) result = 1;
else result = base *
power(base, exp – 1);
return result;
exp
base
old $fp
}



42
Sketch stack frame
Write prologue & epilogue
Write function body
$fp
$ra
Comp Sci 251 -- functions
Wait a minute!

43
What if your function has more than 4
parameters?
Comp Sci 251 -- functions
Call by value vs. call by reference



C++ has reference parameters
Java passes all objects by reference
Assembly language implementation?
–
44
Pass the address of the argument
Comp Sci 251 -- functions
Pass By Value
// This program uses variables as function parameters.
#include <iostream>
using namespace std;
// Function prototypes. The function uses pass by value
void doubleNum(int );
45
Comp Sci 251 -- functions
Pass By Value
int main()
{
int value;
// Get a number and store it in value.
cout << "Enter a number: ";
cin >> value;
cout << "That value entered is " << value << endl;
// Double the number stored in value.
doubleNum(value);
cout << "That value doubled is " << value << endl;
return 0;
}
46
Comp Sci 251 -- functions
Pass By Value
//**********************************************************
// Definition of doubleNum.
// The parameter valueVar is a value variable. The value
// in valueVar is doubled.
//**********************************************************
void doubleNum (int valueVar)
{
valueVar *= 2;
// display valueVar in doubleNum
cout << "In doubleNum, valueVar is " << valueVar << endl;
}
47
Comp Sci 251 -- functions
Pass By Reference
// This program uses reference variables as function
// parameters.
#include <iostream>
using namespace std;
// Function prototypes. Both functions use reference
// variables
// as parameters.
void doubleNum( int & );
void getNum( int & );
48
Comp Sci 251 -- functions
Pass By Reference
int main()
{
int value;
// Get a number and store it in value.
getNum(value);
// Display the resulting number.
cout << "That value entered is " << value << endl;
// Double the number stored in value.
doubleNum(value);
// Display the resulting number.
cout << "That value doubled is " << value << endl;
return 0;
49
}
Comp Sci 251 -- functions
Pass By Reference
// The parameter userNum is a reference variable. The user is
// asked to enter a number, which is stored in userNum.
void getNum(int &userNum)
{
cout << "Enter a number: ";
cin >> userNum;
}
// The parameter refVar is a reference variable. The value
// in refVar is doubled.
50
void doubleNum (int &refVar)
{
refVar *= 2;
}
Comp Sci 251 -- functions
Example
// x is passed by ref.
void increment(int &x){
x++;
}
int foo = 5;
increment(foo);
// foo contains 6
increment:
#prologue...
lw $t0, -4($fp)
lw $t1, ($t0)
addi $t1, $t1, 1
sw $t1, ($t0)
#epilogue...
__start:
foo:
51
la $a0, foo
jal increment
.data
.word 5
Comp Sci 251 -- functions
Example

52
Value_ref.a
Comp Sci 251 -- functions
Arrays are passed by reference
void f(int[] a){...}
f:
int bar[1000];
f(bar);
__start:
bar:
53
.text
...
jr $ra
la $a0, bar
jal f
.data
.space 4000
Comp Sci 251 -- functions
Exercise: function to sum an array
int sum(int[] a, int size){
int result = 0;
int i;
for(i=0; i< size; i++)
result += a[i];
return result
}
sum:
jr $ra
__start:
int bar[1000];
cout << sum(bar, 1000);
bar:
54
.text
# fill in code
la $a0, bar
li $a1, 1000
jal sum
.data
.space 4000
Comp Sci 251 -- functions