x86 Programming III CSE 351 Autumn 2016
Function calls and Jumps
Call Stack
Register Convention
Program memory layout
Agenda
1
CS295
L08 – RISC V – Function Calls
Transfer Control
Caller Routine
Routine Caller
Pass Arguments to and from the routine
fixed length, variable length, recursively
Get return value back to the caller
Manage Registers
Allow each routine to use registers
Prevent routines from clobbering each others’ data
Calling Convention for Procedure Calls
2
CS295
L08 – RISC V – Function Calls
Six Steps of Calling a Function
Put arguments in a place where the function can access them
Transfer control to the function
The function will acquire any (local) storage resources it needs
The function performs its desired task
The function puts return value in an accessible place and “cleans up”
Control is returned to you
3
CS295
L08 – RISC V – Function Calls
4
Jumps are not enough
main:
j myfn
after1:
add x1,x2,x3
myfn:
…
…
j after1
Jumps to the callee
Jumps back
1
2
CS295
L08 – RISC V – Function Calls
Jumps and branches can transfer control to the callee (called procedure)
Jumps and branches can transfer control back
4
myfn:
…
…
5
Jumps are not enough
main:
j myfn
after1:
add x1,x2,x3
j myfn
after2:
sub x3,x4,x5
Jumps to the callee
Jumps back
What about multiple sites?
1
2
??? Change target
on the fly ???
j after2
3
4
j after1
CS295
L08 – RISC V – Function Calls
Jumps and branches can transfer control to the callee (called procedure)
Jumps and branches can transfer control back
5
6
Takeaway 1: Need Jump And Link
JAL (Jump And Link) instruction moves a new value into the PC, and simultaneously saves the old value in register x1 (aka $ra or return address)
Thus, can get back from the subroutine to the instruction immediately following the jump by transferring control back to PC in register x1
CS295
L08 – RISC V – Function Calls
7
Jump-and-Link / Jump Register
main:
jal myfn
after1:
add x1,x2,x3
jal myfn
after2:
sub x3,x4,x5
myfn:
…
…
jr x1
JAL saves the PC in register $31
Subroutine returns by jumping to $31
1
2
x1
after1
First call
CS295
L08 – RISC V – Function Calls
after1
8
Jump-and-Link / Jump Register
main:
jal myfn
after1:
add x1,x2,x3
jal myfn
after2:
sub x3,x4,x5
myfn:
…
…
jr x1
JAL saves the PC in register x1
Subroutine returns by jumping to x1
What happens for recursive invocations?
1
2
x1
after2
Second call
4
3
CS295
L08 – RISC V – Function Calls
9
int main (int argc, char* argv[ ]) {
int n = 9;
int result = myfn(n);
}
int myfn(int n) {
if(n > 0) {
return n * myfn(n – 1);
} else {
return 1;
}
}
JAL / JR for Recursion?
CS295
L08 – RISC V – Function Calls
10
JAL / JR for Recursion?
main:
jal myfn
after1:
add x1,x2,x3
myfn:
if (test)
jal myfn
after2:
jr x1
Problems with recursion:
overwrites contents of x1
1
x1
after1
First call
CS295
L08 – RISC V – Function Calls
11
JAL / JR for Recursion?
main:
jal myfn
after1:
add x1,x2,x3
myfn:
if (test)
jal myfn
after2:
jr x1
Problems with recursion:
overwrites contents of x1
1
x1
Recursive Call
2
after1
after2
CS295
L08 – RISC V – Function Calls
12
JAL / JR for Recursion?
main:
jal myfn
after1:
add x1,x2,x3
myfn:
if (test)
jal myfn
after2:
jr x1
Problems with recursion:
overwrites contents of x1
1
x1
after2
Return from Recursive Call
2
3
CS295
L08 – RISC V – Function Calls
13
JAL / JR for Recursion?
main:
jal myfn
after1:
add x1,x2,x3
myfn:
if (test)
jal myfn
after2:
jr x1
Problems with recursion:
overwrites contents of x1
1
x1
after2
Return from Original Call???
2
3
4
Stuck!
CS295
L08 – RISC V – Function Calls
14
JAL / JR for Recursion?
main:
jal myfn
after1:
add x1,x2,x3
myfn:
if (test)
jal myfn
after2:
jr x1
Problems with recursion:
overwrites contents of x1
Need a way to save and restore register contents
1
x1
after2
Return from Original Call???
2
3
4
Stuck!
CS295
L08 – RISC V – Function Calls
Function calls and Jumps
Call Stack
Register Convention
Program memory layout
Agenda
15
CS295
L08 – RISC V – Function Calls
16
Takeaway2: Need a Call Stack
JAL (Jump And Link) instruction moves a new value into the PC, and simultaneously saves the old value in register x1 (aka ra or return address) Thus, can get back from the subroutine to the instruction immediately following the jump by transferring control back to PC in register x1
Need a Call Stack to return to correct calling procedure. To maintain a stack, need to store an activation record (aka a “stack frame”) in memory. Stacks keep track of the correct return address by storing the contents of x1 in memory (the stack).
CS295
L08 – RISC V – Function Calls
17
Need a “Call Stack”
Call stack
contains activation records (aka stack frames)
Each activation record contains
the return address for that invocation
the local variables for that procedure
A stack pointer (sp) keeps track of the top of the stack
dedicated register (x2) on the RISC-V
Manipulated by push/pop operations
push: move sp down, store
pop: load, move sp up
CS295
L08 – RISC V – Function Calls
Stack Before, During, After Call
18
ra
CS295
L08 – RISC V – Function Calls
Exact ordering of saved registers is up to you (make sure you keep track, though!).
(actually don’t need to save argument registers)
18
Local Variables and Arrays
Any local variables the compiler cannot assign to registers will be allocated as part of the stack frame (Recall: spilling to memory)
Locally declared arrays and structs are also allocated as part of the stack frame
Stack manipulation is same as before
Move sp down an extra amount and use the space it created as storage
19
CS295
L08 – RISC V – Function Calls
Function Call Example
int Leaf(int g, int h, int i, int j) {
int f;
f = (g + h) – (i + j);
return f;
}
Parameter variables g, h, i, and j in argument registers a0, a1, a2, and a3, and f in s0
Assume need one temporary register s1
CS295
L08 – RISC V – Function Calls
RISC-V Code for Leaf()
Leaf: addi sp,sp,-8 # adjust stack for 2 items
sw s1, 4(sp) # save s1 for use afterwards
sw s0, 0(sp) # save s0 for use afterwards
add s0,a0,a1 # f = g + h
add s1,a2,a3 # s1 = i + j
sub a0,s0,s1 # return value (g + h) – (i + j)
lw s0, 0(sp) # restore register s0 for caller
lw s1, 4(sp) # restore register s1 for caller
addi sp,sp,8 # adjust stack to delete 2 items
jr ra # jump back to calling routine
CS295
L08 – RISC V – Function Calls
21
Stack Before, During, After Function
Need to save old values of s0 and s1
sp
Before call
sp
Saved s1
During call
Saved s0
sp
After call
Saved s1
Saved s0
CS295
L08 – RISC V – Function Calls
22
Function calls and Jumps
Call Stack
Register Convention
Program memory layout
Agenda
23
CS295
L08 – RISC V – Function Calls
CalleR: the calling function
CalleE: the function being called
When callee returns from executing, the caller needs to know which registers may have changed and which are guaranteed to be unchanged.
Register Conventions: A set of generally accepted rules as to which registers will be unchanged after a procedure call (jal) and which may be changed.
Register Conventions
CS295
L08 – RISC V – Function Calls
Basic Structure of a Function
func_label:
addi sp,sp, -framesize
sw ra,
save other regs if need be
restore other regs if need be
lw ra,
addi sp,sp, framesize
jr ra
25
Epilogue
Prologue
Body (call other functions…)
ra
stack
…
$ra
$ra
…
CS295
L08 – RISC V – Function Calls
Substitute the proper immediate for
Can order registers on stack however you want to, but must make sure to restore them properly.
Using Stack to Backup Registers
Limited number of registers for everyone to use (limited desk space)
All functions use the same conventions — look for arguments/return addresses in the same places
What happens if a function calls another function?
(ra would get overwritten!)
26
To reduce expensive loads and stores from spilling and restoring registers, RISC-V function-calling convention divides registers into two categories:
CS295
L08 – RISC V – Function Calls
27
CS295
L08 – RISC V – Function Calls
28
Convention Summary
first eight arg words passed in $a0-$a7
Space for args in child’s stack frame
return value (if any) in $a0, $a1
stack frame ($fp to $sp) contains:
$ra (clobbered on JALs)
local variables
space for 8 arguments to Callees
arguments 9+ to Callees
callee save regs: preserved
caller save regs: not preserved
global data accessed via $gp
saved ra
saved fp
saved regs
($s0 … $s7)
locals
incoming
args
$fp
$sp
CS295
L08 – RISC V – Function Calls
Saved Registers
These registers are expected to be the same before and after a function call
If calleE uses them, it must restore values before returning
This means save the old values, use the registers, then reload the old values back into the registers
s0-s11 (saved registers)
sp (stack pointer)
If not in same place, the caller won’t be able to properly restore values from the stack
ra (return address)
29
ra
CS295
L08 – RISC V – Function Calls
Volatile Registers
These registers can be freely changed by the calleE
If calleR needs them, it must save those values before making a procedure call
t0-t6 (temporary registers)
a0-a7 (return address and arguments)
These will change if calleE invokes another function (nested function means calleE is also a calleR)
30
$t
a
CS295
L08 – RISC V – Function Calls
31
int test(int a, int b) {
int tmp = (a&b)+(a|b);
int s = sum(tmp,1,2,3,4,5,6,7,8);
int u = sum(s,tmp,b,a,b,a);
return u + a + b;
}
Correct Order:
Body First
Determine stack frame size
Complete Prologue/Epilogue
Activity #1: Calling Convention Example
CS295
L08 – RISC V – Function Calls
32
int test(int a, int b) {
int tmp = (a&b)+(a|b);
int s =sum(tmp,1,2,3,4,5,6,7,8);
int u = sum(s,tmp,b,a,b,a);
return u + a + b;
}
test:
MOVE s1, a0
MOVE s2, a1
AND t0, a0, a1
OR t1, a0, a1
ADD t0, t0, t1
MOVE a0, t0
LI a1, 1
LI a2, 2
…
LI a7, 7
LI t1, 8
SW t1, -4(sp)
SW t0, 0(sp)
JAL sum
LW t0, 0(sp)
MOVE a0, a0 # s
MOVE a1, t0 # tmp
MOVE a2, s2 # b
MOVE a3, s1 # a
MOVE a4, s2 # b
MOVE a5, s1 # a
JAL sum
# add u (a0) and a (s1)
ADD a0, a0, s1
ADD a0, a0, s2
# a0 = u + a + b
Prologue
Epilogue
CS295
L08 – RISC V – Function Calls
33
int test(int a, int b) {
int tmp = (a&b)+(a|b);
int s =sum(tmp,1,2,3,4,5,6,7,8);
int u = sum(s,tmp,b,a,b,a);
return u + a + b;
}
Prologue
Epilogue
How many bytes do we
need to allocate for the
stack frame?
24
28
36
40
48
test:
MOVE s1, a0
MOVE s2, a1
AND t0, a0, a1
OR t1, a0, a1
ADD t0, t0, t1
MOVE a0, t0
LI a1, 1
LI a2, 2
…
LI a7, 7
LI t1, 8
SW t1, -4(sp)
SW t0, 0(sp)
JAL sum
LW t0, 0(sp)
MOVE a0, a0 # s
MOVE a1, t0 # tmp
MOVE a2, s2 # b
MOVE a3, s1 # a
MOVE a4, s2 # b
MOVE a5, s1 # a
JAL sum
# add u (a0) and a (s1)
ADD a0, a0, s1
ADD a0, a0, s2
# a0 = u + a + b
CS295
L08 – RISC V – Function Calls
34
int test(int a, int b) {
int tmp = (a&b)+(a|b);
int s =sum(tmp,1,2,3,4,5,6,7,8);
int u = sum(s,tmp,b,a,b,a);
return u + a + b;
}
Prologue
Epilogue
saved ra
saved fp
saved regs
(s1 … s11)
locals
(t0)
outgoing args
space for a0 – a7
and 9th arg
$fp
$sp
space for a1
space for a0
test:
MOVE s1, a0
MOVE s2, a1
AND t0, a0, a1
OR t1, a0, a1
ADD t0, t0, t1
MOVE a0, t0
LI a1, 1
LI a2, 2
…
LI a7, 7
LI t1, 8
SW t1, -4(sp)
SW t0, 0(sp)
JAL sum
LW t0, 0(sp)
MOVE a0, v0 # s
MOVE a1, t0 # tmp
MOVE a2, s2 # b
MOVE a3, s1 # a
MOVE a4, s2 # b
MOVE a5, s1 # a
JAL sum
# add u (a0) and a (s1)
ADD a0, a0, s1
ADD a0, a0, s2
# a0 = u + a + b
CS295
L08 – RISC V – Function Calls
35
int test(int a, int b) {
int tmp = (a&b)+(a|b);
int s =sum(tmp,1,2,3,4,5,6,7,8);
int u = sum(s,tmp,b,a,b,a);
return u + a + b;
}
Prologue
Epilogue
saved ra
saved fp
$fp
$sp
saved reg s2
saved reg s1
local t0
outgoing 9th arg
space for a7
space for a6
…
space for a1
space for a0
-28
…
-12
-8
-36
-4
0
4
8
12
16
space incoming for a1
space incoming for a0
20
24
test:
MOVE s1, a0
MOVE s2, a1
AND t0, a0, a1
OR t1, a0, a1
ADD t0, t0, t1
MOVE a0, t0
LI a1, 1
LI a2, 2
…
LI a7, 7
LI t1, 8
SW t1, -4(sp)
SW t0, 0(sp)
JAL sum
LW t0, 0(sp)
MOVE a0, a0 # s
MOVE a1, t0 # tmp
MOVE a2, s2 # b
MOVE a3, s1 # a
MOVE a4, s2 # b
MOVE a5, s1 # a
JAL sum
# add u (a0) and a (s1)
ADD a0, a0, s1
ADD a0, a0, s2
# a0 = u + a + b
CS295
L08 – RISC V – Function Calls
-4 9th outgoing arg
-8 a7
-12 a6
-16 a5
-20 a4
-24 a3
-28 a2
-32 a1
-36 a0
35
36
Activity #2: Calling Convention Example:
# allocate frame
# save $ra
# save old $fp
# callee save …
# callee save …
# set new frame ptr
…
…
# restore …
# restore …
# restore old $fp
# restore $ra
# dealloc frame
test:
saved ra
saved fp
$fp
$sp
saved reg s2
saved reg s1
local t0
outgoing 9th arg
space for a7
space for a6
…
space for a1
space for a0
-28
…
-12
-8
-36
-4
0
4
8
12
16
space incoming for a1
Space incoming for a0
20
24
CS295
L08 – RISC V – Function Calls
37
# allocate frame
# save $ra
# save old $fp
# callee save …
# callee save …
# set new frame ptr
…
…
# restore …
# restore …
# restore old $fp
# restore $ra
# dealloc frame
test:
ADDI sp, sp, -28
SW ra, sp, 16
SW fp, sp, 12
SW s2, sp, 8
SW s1, sp, 4
ADDI fp, sp, 24
LW s1, sp, 4
LW s2, sp, 8
LW fp, sp, 12
LW ra, sp, 16
ADDI sp, sp, 28
JR ra
Body
(previous slide, Activity #1)
Space for t0
saved ra
saved fp
$fp
$sp
saved reg s2
saved reg s1
local t0
outgoing 9th arg
space for a7
space for a6
…
space for a1
space for a0
-28
…
-12
-8
-36
-4
0
4
8
12
16
space incoming for a1
Space incoming for a0
20
24
Space for a0 and a1
CS295
L08 – RISC V – Function Calls
Function Call Example
… sum(a,b); … /* a→s0,b→s1 */
int sum(int x, int y) {
return x+y;
}
1000 addi a0,s0,0 # x = a
1004 addi a1,s1,0 # y = b
1008 addi ra,x0,1016 # ra=1016
1012 j sum # jump to sum
1016
…
2000 sum: add a0,a0,a1
2004 jr ra # return
38
C
RISC-V
Would we know this before compiling?
address (decimal)
jr ra
Otherwise we don’t know where we came from
CS295
L08 – RISC V – Function Calls
Function Call Example
… sum(a,b); … /* a→s0,b→s1 */
int sum(int x, int y) {
return x+y;
}
1000 addi a0,s0,0 # x = a
1004 addi a1,s1,0 # y = b
1008 jal sum # ra=1012, goto sum
1012
…
2000 sum: add v0,a0,a1
2004 jr ra # return
39
address (decimal)
C
RISCV
CS295
L08 – RISC V – Function Calls
Example: sumSquare
int sumSquare(int x, int y) {
return mult(x,x)+ y; }
What do we need to save?
Call to mult will overwrite ra, so save it
Reusing a1 to pass 2nd argument to mult, but need current value (y) later, so save a1
To save something to the Stack, move sp down the required amount and fill the “created” space
40
CS295
L08 – RISC V – Function Calls
In general, you would also want to save $a0 to the Stack, in case the function you call calls another function can overwrites $a0.
40
Example: sumSquare
int sumSquare(int x, int y) {
return mult(x,x)+ y; }
sumSquare:
addi sp,sp,-8 # make space on stack
sw ra, 4(sp) # save ret addr
sw a1, 0(sp) # save y
add a1,a0,x0 # set 2nd mult arg
jal mult # call mult
lw a1, 0(sp) # restore y
add a0,a0,a1 # ret val = mult(x,x)+y
lw ra, 4(sp) # get ret addr
addi sp,sp,8 # restore stack
jr ra
mult: …
41
“push”
“pop”
CS295
L08 – RISC V – Function Calls
Example: Using Volatile Registers
myFunc: # Uses t0
addiu sp,sp,-4
sw ra,0(sp) # Save saved registers
… # Do stuff with t0
addiu sp,sp,-4 # Save volatile registers
sw t0,0(sp) # before calling a function
jal func1 # Function may change t0
lw t0,0(sp) # Restore volatile registers
addiu sp,sp,4 # before you use them again
… # Do stuff with t0
lw ra,0(sp)
addiu sp,sp,4 # Restore saved registers
jr ra # return
42
# This is the Prologue
# This is the Epilogue
CS295
L08 – RISC V – Function Calls
Example: Using Saved Registers
myFunc: # Uses s0 and s1
addiu sp,sp,-12 # This is the Prologue
sw ra,8(sp) # Save saved registers
sw s0,4(sp)
sw s1,0(sp)
… # Do stuff with s0 and s1
jal func1 # s0 and s1 unchanged by
… # function calls, so can keep
jal func2 # using them normally
… # Do stuff with s0 and s1
lw s1,0(sp) # This is the Epilogue
lw s0,4(sp) # Restore saved registers
lw ra,8(sp)
addiu sp,sp,12
jr ra # return
43
# This is the Prologue
# This is the Epilogue
CS295
L08 – RISC V – Function Calls
Choosing Your Registers
Minimize register footprint
Optimize to reduce number of registers you need to save by choosing which registers to use in a function
Only save when you absolutely have to
Function does NOT call another function
Use only t0-t6 and there is nothing to save!
Function calls other function(s)
Values you need throughout go in s0-s11, others go in t0-t6
At each function call, check number arguments and return values for whether you or not you need to save
44
CS295
L08 – RISC V – Function Calls
Recall: memory is MUCH slower than registers.
The more you know about the internals of the other functions you call, the more you can get away with (e.g. using temporary registers that you know the other functions don’t use, so you don’t bother saving them across function calls).
44
45
Arguments & Return Values
Need consistent way of passing args and result
Given a procedure signature, need to know where arguments should be placed
int min(int a, int b);
int subf(int a, int b, int c, int d, int e, int f, int g, int h, int i);
int isalpha(char c);
int treesort(struct Tree *root);
struct Node *createNode();
struct Node mynode();
Too many combinations of char, short, int, void *, struct, etc.
RISC-V treats char, short, int and void * identically
$a0, $a1
stack?
$a0
$a0, $a1
$a0
CS295
L08 – RISC V – Function Calls
46
Simple Argument Passing (1-8 args)
First eight arguments:
passed in registers x10-x17
aka $a0, $a1, …, $a7
Returned result:
passed back in a register
Specifically, x10, aka a0
And x11, aka a1
main:
li x10, 6
li x11, 7
jal myfn
addi x5, x10, 2
main() {
int x = myfn(6, 7);
x = x + 2;
}
Note: This is not the entire story for 1-8 arguments.
Please see the Full Story slides.
CS295
L08 – RISC V – Function Calls
47
Conventions so far:
args passed in $a0, $a1, …, $a7
return value (if any) in $a0, $a1
stack frame at $sp
contains $ra (clobbered on JAL to sub-functions)
Q: What about argument lists?
CS295
L08 – RISC V – Function Calls
48
Many Arguments (8+ args)
First eight arguments:
passed in registers x10-x17
aka a0, a1, …, a7
Subsequent arguments:
”spill” onto the stack
Args passed in child’s stack frame
main:
li x10, 0
li x11, 1
…
li x17, 7
li x5, 8
sw x5, -8(x2)
li x5, 9
sw x5, -4(x2)
jal myfn
main() {
myfn(0,1,2,..,7,8,9);
…
}
Note: This is not the entire story for 9+ args.
Please see the Full Story slides.
9
8
sp
space for x17
space for x16
space for x15
space for x14
space for x13
space for x12
space for x11
space for x10
CS295
L08 – RISC V – Function Calls
49
Many Arguments (8+ args)
First eight arguments:
passed in registers x10-x17
aka a0, a1, …, a7
Subsequent arguments:
”spill” onto the stack
Args passed in child’s stack frame
main:
li a0, 0
li a1, 1
…
li a7, 7
li t0, 8
sw t0, -8(sp)
li t0, 9
sw t0, -4(sp)
jal myfn
main() {
myfn(0,1,2,..,7,8,9);
…
}
Note: This is not the entire story for 9+ args.
Please see the Full Story slides.
9
8
sp
space for x17
space for x16
space for x15
space for x14
space for x13
space for x12
space for x11
space for x10
CS295
L08 – RISC V – Function Calls
50
Argument Passing: the Full Story
main() {
myfn(0,1,2,..,7,8,9);
…
}
Arguments 1-8:
passed in x10-x17 room on stack
Arguments 9+:
placed on stack
Args passed in child’s stack frame
-40($sp)
-36($sp)
-32($sp)
-28($sp)
-24($sp)
-20($sp)
9
8
sp
space for x17
space for x16
space for x15
space for x14
space for x13
space for x12
space for x11
space for x10
-16($sp)
-12($sp)
-8($sp)
-4($sp)
main:
li a0, 0
li a1, 1
…
li a7, 7
li t0, 8
sw t0, -8(x2)
li t0, 9
sw t0, -4(x2)
jal myfn
CS295
L08 – RISC V – Function Calls
51
Pros of Argument Passing Convention
Consistent way of passing arguments to and from subroutines
Creates single location for all arguments
Caller makes room for a0-a7 on stack
Callee must copy values from a0-a7 to stack
callee may treat all args as an array in memory
Particularly helpful for functions w/ variable length inputs: printf(“Scores: %d %d %d\n”, 1, 2, 3);
Aside: not a bad place to store inputs if callee needs to call a function (your input cannot stay in $a0 if you need to call another function!)
CS295
L08 – RISC V – Function Calls
52
Frame Layout & the Frame Pointer
blue() {
pink(0,1,2,3,4,5);
}
blue’s Ret Addr
sp
blue’s stack frame
sp
CS295
L08 – RISC V – Function Calls
53
Frame Layout & the Frame Pointer
space for a4
space for a3
space for a2
space for a1
space for a0
space for a5
blue’s Ret Addr
pink’s Ret Addr
sp
fp
pink’s stack frame
blue() {
pink(0,1,2,3,4,5);
}
pink(int a, int b, int c, int d, int e, int f) {
…
}
Notice
Pink’s arguments are on pink’s stack
sp changes as functions call other functions, complicates accesses
Convenient to keep pointer to bottom of stack == frame pointer
x8, aka fp (also known as s0)
can be used to restore sp on exit
sp
blue’s stack frame
CS295
L08 – RISC V – Function Calls
Function calls and Jumps
Call Stack
Register Convention
Program memory layout
Agenda
54
CS295
L08 – RISC V – Function Calls
Where is the Stack in Memory?
RV32 convention (RV64 and RV128 have different memory layouts)
Stack starts in high memory and grows down
Hexadecimal: bfff_fff0hex
Stack must be aligned on 16-byte boundary (not true in examples above)
RV32 programs (text segment) in low end
0001_0000hex
static data segment (constants and other static variables) above text for static variables
RISC-V convention global pointer (gp) points to static
RV32 gp = 1000_0000hex
Heap above static for data structures that grow and shrink ; grows up to high addresses
CS295
L08 – RISC V – Function Calls
56
top
bottom
system reserved
stack
system reserved
.data
.text
0xfffffffc
0x00000000
0x7ffffffc
0x80000000
0x10000000
0x00400000
code (text)
static data
dynamic data (heap)
CS295
L08 – RISC V – Function Calls
57
x2000
x1FD0
Return Address lives in Stack Frame
Stack Manipulated by push/pop operations
Context: after 2nd JAL to myfn (from myfn)
PUSH: ADDI sp, sp, -20 // move sp down
SW x1, 16(sp) // store retn PC 1st
Context: 2nd myfn is done (x1 == ???)
POP: LW x1, 16(sp) // restore retn PC r31
ADDI sp, sp, 20 // move sp up
JR x1 // return
myfn stack frame
main stack frame
myfn stack frame
after2
r31
r29
x2000
For now: Assume each frame = x20 bytes
(just to make this example concrete)
x1FD0
after2
XXXX
CS295
L08 – RISC V – Function Calls
58
Stack contains stack frames (aka “activation records”)
1 stack frame per dynamic function
Exists only for the duration of function
Grows down, “top” of stack is sp, x2
Example: lw x5, 0(sp) puts word at top of stack into x5
Each stack frame contains:
Local variables, return address (later), register
backups (later)
int main(…) {
…
myfn(x);
}
int myfn(int n) {
…
myfn();
}
system reserved
stack
code
heap
system reserved
static data
myfn stack frame
myfn stack frame
main stack frame
$sp
CS295
L08 – RISC V – Function Calls
59
Frame Pointer
It is often cumbersome to keep track of location of data on the stack
The offsets change as new values are pushed onto and popped off of the stack
Keep a pointer to the bottom of the top stack frame
Simplifies the task of referring to items on the stack
A frame pointer, x8, aka fp/s0
Value of sp upon procedure entry
Can be used to restore sp on exit
CS295
L08 – RISC V – Function Calls
60
The Heap
Heap holds dynamically allocated memory
Program must maintain pointers to anything allocated
Example: if x5 holds x
lw x6, 0(x5) gets first word x points to
Data exists from malloc() to free()
void some_function() {
int *x = malloc(1000);
int *y = malloc(2000);
free(y);
int *z = malloc(3000);
}
system reserved
stack
X
Y
z
code
heap
system reserved
static data
1000 bytes
2000 bytes
3000 bytes
CS295
L08 – RISC V – Function Calls
60
61
Data Segment
Data segment contains global variables
Exist for all time, accessible to all routines
Accessed w/global pointer
gp, x3, points to middle of segment
Example: lw x5, 0(gp) gets middle-most word
(here, max_players)
int max_players = 4;
int main(…) {
…
}
gp
4
system reserved
stack
code
heap
system reserved
static data
CS295
L08 – RISC V – Function Calls
62
int n = 100;
int main (int argc, char* argv[ ]) {
int i, m = n, sum = 0;
int* A = malloc(4*m + 4);
for (i = 1; i <= m; i++) {
sum += i; A[i] = sum; }
printf ("Sum 1 to %d is %d\n", n, sum);
}
Variables Visibility Lifetime Location
Function-Local
Global
Dynamic
Where is i ?
Stack
Heap
Global Data
Text
Where is n ?
Stack
Heap
Global Data
Text
Where is main ?
Stack
Heap
Global Data
Text
CS295
L08 – RISC V – Function Calls
function / func invocation / stack
file or prog / prog execution / data segment
undef / malloc to free / heap
bug in this code
62
63
top
bottom
system reserved
stack
system reserved
0xfffffffc
0x00000000
0x7ffffffc
0x80000000
0x10000000
0x00400000
code (text)
static data
dynamic data (heap)
“Data Memory”
“Program Memory”
CS295
L08 – RISC V – Function Calls
64
int n = 100;
int main (int argc, char* argv[ ]) {
int i, m = n, sum = 0;
int* A = malloc(4*m + 4);
for (i = 1; i <= m; i++) {
sum += i; A[i] = sum; }
printf ("Sum 1 to %d is %d\n", n, sum);
}
Variables Visibility Lifetime Location
Function-Local
Global
Dynamic
i, m, sum, A
n, str
w/in function
function
invocation
stack
whole program
program
execution
.data
b/w malloc
and free
heap
Anywhere that
has a pointer
*A
CS295
L08 – RISC V – Function Calls
function / func invocation / stack
file or prog / prog execution / data segment
undef / malloc to free / heap
bug in this code
64
65
Global and Locals
How does a function load global data?
global variables are just above 0x10000000
Convention: global pointer
x3 is gp (pointer into middle of global data section)
gp = 0x10000800
Access most global data using LW at gp +/- offset
LW t0, 0x800(gp)
LW t1, 0x7FF(gp)
CS295
L08 – RISC V – Function Calls
# data at 0x10000000
# data at 0x10000FFF
(4KB range)
65
66
top
bottom
system reserved
stack
system reserved
Anatomy of an executing program
0xfffffffc
0x00000000
0x7ffffffc
0x80000000
0x10000000
0x00400000
code (text)
static data
dynamic data (heap)
$gp
CS295
L08 – RISC V – Function Calls
67
Calling Convention for Procedure Calls
Transfer Control
Caller Routine
Routine Caller
Pass Arguments to and from the routine
fixed length, variable length, recursively
Get return value back to the caller
CS295
L08 – RISC V – Function Calls