COPE-03 Functions.indd
3
Functions
Uwe R. Zimmer – The Australian National University
Computer Organisation & Program Execution 2021
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 153 of 487 (chapter 3: “Functions” up to page 232)
References for this chapter
[Patterson17]
David A. Patterson & John L. Hennessy
Computer Organization and Design – The Hardware/Software Interface
Chapter 2 “Instructions: Language of the Computer”
ARM edition, Morgan Kaufmann 2017
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 154 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 155 of 487 (chapter 3: “Functions” up to page 232)
(Greatness from …) Small beginnings
plus_1 :: (Num a) => a -> a
plus_1 x = x + 1
int plus1 (int x) {
return x + 1;
}
function Plus_1 (x : Integer) return Integer is (x + 1);
def plus1 (x):
return x + 1;
pure function plus_1 (x)
int, intent (in) :: x
int :: plus_1
plus_1 = x + 1;
end function;
function Plus_1 (x : integer) : integer;
begin
Plus_1 := x + 1;
end;
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 156 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Plus_1
mov r4, r0
…
…
…
…
Plus_1:
add r0, #1
bx lr
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 157 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Plus_1
mov r4, r0
…
…
…
…
Plus_1:
add r0, #1
bx lrlr
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 158 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Plus_1
mov r4, r0
…
…
…
…
Plus_1:
add r0, #1
bx lrlr
How is the parameter x passed?
Where do you fi nd the result after the function returns?
Could it be done differently?
Does it work?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 159 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
add r0, #1
mov r4, r0
…
…
…
…
Can/should this always be done?
This is called inlining
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 160 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 161 of 487 (chapter 3: “Functions” up to page 232)
(Greatness from …) Small beginnings
plus_2 :: (Num a) => a -> a
plus_2 x = plus_1 $ plus_1 x
int plus2 (int x) {
return plus1 (plus1 (x));
}
function Plus_2 (x : Integer) return Integer is (Plus_1 (Plus_1 (x)));
def plus2 (x):
return plus1 (plus1 (x));
pure function plus_2 (x)
int, intent (in) :: x
int :: plus_2
plus_2 = plus_1 (plus_1 (x));
end function;
function Plus_2 (x : integer) : integer;
begin
Plus_2 := Plus_1 (Plus_1 (x));
end;
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 162 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Plus_2
mov r3, r0
…
…
…
…
Plus_2:
…
bl Plus_1
bl Plus_1
…
bx lr
Plus_1:
add r0, #1
bx lr
bx lr
is used three times
What is the value of lr in each case?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 163 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Plus_2
mov r3, r0
…
…
…
…
Plus_2:
str lr, [sp, #-4]!
bl Plus_1
bl Plus_1
ldr lr, [sp], #4
bx lr
Plus_1:
add r0, #1
bx lr
bx lr
is used three times
What is the value of lr in each case?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 164 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
add r0, #2
mov r3, r0
…
…
…
…
… we need an example, where a compiler
will not just remove all our code!
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 165 of 487 (chapter 3: “Functions” up to page 232)
(Greatness from …) Small beginnings
fib_fact :: (Num a) => a -> a
fib_fact x = (fib x) + (fact x)
unsigned int fibFact (unsigned int x) {
return fib (x) + fact (x);
}
function Fib_Fact (x : Natural) return Natural is (Fib (x) + Fact (x));
def fibFact (x):
return fib (x) + fact (x);
pure function fib_fact (x)
int, intent (in) :: x
int :: fib_fact
fib_fact = fib (x) + fact (x);
end function;
function Fib_Fact (x : cardinal) : cardinal;
begin
Fib_Fact := Fib (x) + Fact (x);
end;
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 166 of 487 (chapter 3: “Functions” up to page 232)
sp
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
…
…
…
…
bl Fib
mov r4, r0
…
bl Fact
add r0, r4
…
…
bx lr
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 167 of 487 (chapter 3: “Functions” up to page 232)
sp
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
…
…
…
…
bl Fib
mov r4, r0
…
bl Fact
add r0, r4
…
…
bx lr
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
167 f
bx lr
… where does this lead us?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 168 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
str lr, [sp, #-4]!
…
…
…
bl Fib
mov r4, r0
…
bl Fact
add r0, r4
…
ldr lr, [sp], #4
bx lr
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
lrsp
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 169 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
str lr, [sp, #-4]!
…
…
…
bl Fib
mov r4, r0
…
bl Fact
add r0, r4
…
ldr lr, [sp], #4
bx lr
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
lrsp
N page 169National University page 1y
r4
… what if this was holding some information
at the time when we were called?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 170 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
stmdb sp!, {r4, lr}
…
…
…
bl Fib
mov r4, r0
…
bl Fact
add r0, r4
…
ldmia sp!, {r4, lr}
bx lr
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
F
i
b
_
F
a
c
t
r4
sp lr
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 171 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
stmdb sp!, {r4, lr}
…
…
…
bl Fib
mov r4, r0
…
bl Fact
add r0, r4
…
ldmia sp!, {r4, lr}
bx lr
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
F
i
b
_
F
a
c
t
r4
sp lr
niversity page 17yi it
What happens to our parameter x (1)
during the function?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 172 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
stmdb sp!, {r4, lr}
…
sub sp, #4
str r0, [sp]
bl Fib
mov r4, r0
ldr r0, [sp]
bl Fact
add r0, r4
add sp, #4
ldmia sp!, {r4, lr}
bx lr
F
i
b
_
F
a
c
t
r4
sp
lr
x (3)
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 173 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
stmdb sp!, {r4, lr}
…
sub sp, #4
str r0, [sp]
bl Fib
mov r4, r0
ldr r0, [sp]
bl Fact
add r0, r4
add sp, #4
ldmia sp!, {r4, lr}
bx lr
F
i
b
_
F
a
c
t
r4
sp
lr
x (3)
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
e R. Zimmer, The Australian National University page y
While addressing via the sp is possible, it may also be
complex to keep track of, as the sp may change further.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 174 of 487 (chapter 3: “Functions” up to page 232)
…
…
…
mov r0, #1
bl Fib_Fact
mov r3, r0
…
…
…
…
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
F
i
b
_
F
a
c
t
r4fp
fp
lr
x (1)
Fib:
…
…
…
bx lr
Fact:
…
…
…
bx lr
2021 Uwe R. Zimmer, The Australian National University page 174 of y2021 Uwe R. Zimmer, The Australian National University page 174y
Keeping a reference to the start of the Stack Frame
for this function (with the frame-pointer fp) makes things neater
and enables structured access to the dynamic context.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 175 of 487 (chapter 3: “Functions” up to page 232)
Recursive
unsigned int fib (unsigned int x) {
switch (x) {
case 0 : return 0;
case 1 : return 1;
default : return fib (x – 1) + fib (x – 2);
} }
function Fib (x : Natural) return Natural is
(case x is
when 0 => 0,
when 1 => 1,
when others => Fib (x – 1) + Fib (x – 2));
unsigned int fact (unsigned int x) {
if (x == 0) return 1;
else return x * fact (x – 1);
}
function Fact (x : Natural) return Positive is
(if x = 0 then 1
else x * Fact (x – 1));
Will our stack handling work
for recursive functions?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 176 of 487 (chapter 3: “Functions” up to page 232)
F
i
b
_
F
a
c
t
F
a
c
t
1
F
a
c
t
0
F
a
c
t
2
F
a
c
t
3
fp
r4
fp
fp
lr
fp
x (3)
lr
fp
x (3)
lr
x (2)
fp
lr
x (1)
fp
lr
x (0)
fp
fp
fp
sp
Fact:
stmdb sp!, {fp, lr}
add fp, sp, #4
sub sp, #4
str r0, [fp, #-8]
cmp r0, #0
bne Case_Others
mov r0, #1
b End_Fact
Case_Others:
sub r0, #1
bl Fact
mov r1, r0
ldr r0, [fp, #-8]
mul r0, r1
End_Fact:
add sp, #4
ldmia sp!, {fp, lr}
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
}}
Where is the last lr stored?
How high do
we stack?Fact
Is Fact reentrant?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 177 of 487 (chapter 3: “Functions” up to page 232)
A compiler will likely
replace such a recursion!
177 f 487 ( h 3 “F i ” 27
function Fact (x : Natural) return Positive is
Fac : Positive := 1;
begin
for i in 1 .. x loop
Fac := Fac * i;
end loop;
return Fac;
end Fact;
function Fact (x : Natural) return Positive is
(if x = 0 then 1
else x * Fact (x – 1));
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 178 of 487 (chapter 3: “Functions” up to page 232)
A compiler will likely
replace such a recursion!
unsigned int fact (unsigned int x) {
if (x == 0) return 1;
else return x * fact (x – 1);
}
178 f 487 ( h 3 “F i ” 27
unsigned int fact (unsigned int x) {
int fac = 1;
for (i = 1, i <= x, i++) {
fac = fac * i;
}
return fac;
}
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 179 of 487 (chapter 3: “Functions” up to page 232)
Fact:
adds r3, r0, #0
mov r0, #1
beq End_Fact
Fact_Loop:
mul r0, r3
subs r3, #1
bne Fact_Loop
End_Fact:
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
}}
Fib:
…
…
…
bx lr
2021 Uwe R. Zimmer, The Australian National University page y2021 Uwe R. Zimmer, The Australian National University pay
Besides all the inlining, unrolling, fl attening, etc. :
Stack operations are still vital for any non-trivial program.
Complexity?
Runtimes?
Is Fact reentrant?
F
i
b
_
F
a
c
t
r4fp
fp
lr
x (3)
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 180 of 487 (chapter 3: “Functions” up to page 232)
Fact:
adds r3, r0, #0
mov r0, #1
beq End_Fact
Fact_Loop:
mul r0, r3
subs r3, #1
bne Fact_Loop
End_Fact:
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
}}
Fib:
…
…
…
bx lr
…
…
bx lr
Why do we save r4?
But we don’t save r3?
F
i
b
_
F
a
c
t
r4fp
fp
lr
x (3)
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 181 of 487 (chapter 3: “Functions” up to page 232)
Fact:
adds r3, r0, #0
mov r0, #1
beq End_Fact
Fact_Loop:
mul r0, r3
subs r3, #1
bne Fact_Loop
End_Fact:
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
}}
Fib:
…
…
…
bx lr
Fact:
}}
bbx lr
We keep a copy of r0 here.
But we don’t keep
a copy of r0 here!
F
i
b
_
F
a
c
t
r4fp
fp
lr
x (3)
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 182 of 487 (chapter 3: “Functions” up to page 232)
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
tytytytyy
Fib:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
cmp r0, #0
beq End_Fib
cmp r0, #1
beq End_Fib
sub r0, r0, #1
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
sub r0, r0, #2
bl Fib
add r0, r4, r0
End_Fib:
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
F
i
b
_
F
a
c
t
r4fp
fp
lr
x (3)
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 183 of 487 (chapter 3: “Functions” up to page 232)
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
tytytytyy
Fib:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
cmp r0, #0
beq End_Fib
cmp r0, #1
beq End_Fib
sub r0, r0, #1
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
sub r0, r0, #2
bl Fib
add r0, r4, r0
End_Fib:
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
F
i
b
_
F
a
c
t
r4fp
fp
lr
x (3)
p
p
r
4, r04, r0
0, [fp, #-12]
act
0, r0, r4
p, #4
p!, {r4, fp, lr}
r
There could be
two
further Fib-calls
for each call
to Fib …
What would the
stack look like?
What would be
the maximal depth
for the stack?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 184 of 487 (chapter 3: “Functions” up to page 232)
Components / phases of a function call:
• Values (parameters) to be passed to a function.
• Local variables inside a function.
• Values (results) to be returned from a function.
So far we:
… passed parameter values in registers (r0 - r3).
… called the function (store the return address and jump to the beginning of the function).
… pushed the return address, the previous stack frame and used registers (r4 …).
… created a new stack frame (and addressed all local variables relative to this).
… grew the stack such that it can hold the local variables.
… done the calculations/operations based on the local variables and scratch registers.
… passed return values in registers (r0 - r1).
… restored the stack pointer (and thus de-allocated all local variables).
… popped the return address, the previous stack frame and used registers (r4 …).
… jumped back to the next instruction after the original function call.
… used the return values found in r0 - r1.
Prologue
Epilogue
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 185 of 487 (chapter 3: “Functions” up to page 232)
Prologue
Epilogue
Components / phases of a function call:
• Values (parameters) to be passed to a function.
• Local variables inside a function.
• Values (results) to be returned from a function.
So far we:
… passed parameter values in registers (r0 - r3).
… called the function (store the return address and jump to the beginning of the function).
… pushed the return address, the previous stack frame and used registers (r4 …).
… created a new stack frame (and addressed all local variables relative to this).
… grew the stack such that it can hold the local variables.
… done the calculations/operations based on the local variables and scratch registers.
… passed return values in registers (r0 - r1).
… restored the stack pointer (and thus de-allocated all local variables).
… popped the return address, the previous stack frame and used registers (r4 …).
… jumped back to the next instruction after the original function call.
… used the return values found in r0 - r1.
What happens if the parameters or
return values won’t fi t into registers?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 186 of 487 (chapter 3: “Functions” up to page 232)
Conventions
ARM architecture calling practice
• r0-r3 are used for parameters.
• r0-r1 are used for return values.
• r0-r3 are not expected to be intact after a function call
… all other registers are expected to be intact!
If those registers do not suffi ce, additional parameters
and results are passed via the stack.
Conventions are different in other
architectures (e.g. x86, where parameters
are generally passed via the stack).
f h
Why are these conventions
architecture related at all?
There are also memory
alignment constraints.
(Mostly due to memory
bus constraints)
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 187 of 487 (chapter 3: “Functions” up to page 232)
Parameter passing
Call by …
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 188 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
by copyy pyy pyy py yby referenceyy
Access
by copy by reference
C
Full control over those three modes.
“by value” parameters are local variables.
“in & out, by reference” syntactically as “by pointer value” paramet
ers.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 189 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
Haskell
Only control over information fl ow – not over access.
sity page 189 of y 487 (chapter 3: “Functions7
tttttttttttttttttttttttttttttttttttteeeeeeeeeeeeeeeeeeeeeeee
nooooooooooooooooooooooooooooo
r is copied to a local F tir is copied to a local
and copied back at return.
Function can read and writ
time. Outside code shall n“in & out” parameters are side-effecting and can
therefore not exist in a pure functional language.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 190 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
Python
All parameter access is double-indirect ( handles).
by reference
Access
b
… this has an impact on performance.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 191 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
Access
Ada
Limited control over “by value result”.
“by value” parameters are constants.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 192 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
Assembly
“By reference” semantics by convention only.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 193 of 487 (chapter 3: “Functions” up to page 232)
Parameter passing
Call by name
… is conceptually a call-by-value, where the value has not been calculated yet.
Technically a reference to a function is passed and the evaluation
of this parameter (function) is left to the called function.
Features:
• Values are only evaluated if and when they are needed.
• Values can change during the life-time of a function (in case of side-effecting functions).
• Values can be stored once calculated (in case of side-effect-free functions).
While this is possible to a degree in most programming languages …
(even if there is no specifi c passing mode, you can still pass a reference to a function)
… it is a core concept for functional, lazy evaluation languages, like e.g. Haskell,
and it does fi nd its way back into mainstream languages like C++, .NET languages or Python
as anonymous functions (sometimes referred to as m-functions or m-expressions).
Pops up in programming
languages since the 60’s.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 194 of 487 (chapter 3: “Functions” up to page 232)
F
i
b
_
F
a
c
t
F
a
c
t
1
F
a
c
t
0
F
a
c
t
2
F
a
c
t
3
Fact:
stmdb sp!, {fp, lr}
add fp, sp, #4
sub sp, #4
str r0, [fp, #-8]
cmp r0, #0
bne Case_Others
mov r0, #1
b End_Fact
Case_Others:
sub r0, #1
bl Fact
mov r1, r0
ldr r0, [fp, #-8]
mul r0, r1
End_Fact:
add sp, #4
ldmia sp!, {fp, lr}
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
ldr r0, [fp, #-12]
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
}}
fp
r4
fp
fp
lr
fp
x (3)
lr
fp
x (3)
lr
x (2)
fp
lr
x (1)
fp
lr
x (0)
fp
fp
fp
sp
How about using call
by reference here?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 195 of 487 (chapter 3: “Functions” up to page 232)
Fact:
stmdb sp!, {r5, fp, lr}
add fp, sp, #4
mov r5, r0
ldr r0, [r5]
cmp r0, #0
bne Case_Others
mov r0, #1
b End_Fact
Case_Others:
sub r0, #1
str r0, [r5]
mov r0, r5
bl Fact
mov r1, r0
ldr r0, [r5]
mul r0, r1
End_Fact:
mov sp, fp
ldmia sp!, {r5, fp, lr}
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
sub r0, fp, #12
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
}}
ttyy
r5 has been nominated to hold
the reference to x inside Fact
F
i
b
_
F
a
c
t
F
a
c
t
1
F
a
c
t
0
F
a
c
t
2
F
a
c
t
3
r5
r4
fp
fp
fp
fp
lr
lr
r5
x (0)
fp
lr
r5
fp
lr
r5
fp
lr
fp
fp
fp
sp
FFFFFF
aaaaa
ccccc
t
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 196 of 487 (chapter 3: “Functions” up to page 232)
Fact:
stmdb sp!, {r5, fp, lr}
add fp, sp, #4
mov r5, r0
ldr r0, [r5]
cmp r0, #0
bne Case_Others
mov r0, #1
b End_Fact
Case_Others:
sub r0, #1
str r0, [r5]
mov r0, r5
bl Fact
mov r1, r0
ldr r0, [r5]
mul r0, r1
End_Fact:
mov sp, fp
ldmia sp!, {r5, fp, lr}
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
sub r0, fp, #12
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
}}
tytyy
We turned Fact into
the constant 0.
F
i
b
_
F
a
c
t
F
a
c
t
1
F
a
c
t
0
F
a
c
t
2
F
a
c
t
3
r5
r4
fp
fp
lr
lr
r5
x (0)
fp
lr
r5
fp
lr
r5
fp
lr
fp
sp
FFFFFF
aaaaa
ccccc
t
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
r5
r4
fp
fp
fp
lr
lr
r5
x (0
fp
lr
r5
fp
lr
r5
fp
lr
fp
ffffffffffffpppppp
fp, sp, #4
r5, r0
r0, [r5]
r0, #0
Case_Others
r0, #1
End_Fa
thers
r000, ###1
r0, [r555]
r0, r5
Fact
r1, r0
r0, [r5]
r0, r1
ct:
s
iiiiiiiiiiiiiiiiiii
s
_______FFFFFFFFFFFFFFFFFFFFFFFFFFaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccccccccccccct
sssssssssssssssssssssssssssssssssss:::::::::::::::::::
0 #1
55]]]]]]]]]]]]]]]]]]]]]]]]]]]]
rrrrrrrrrrrrrrr11111111111111111111111111111111111
fp
sssssssssssssssssssssssssssssssssssppppppppppppppppppppppppppppppppppp
lr
p!, {r5, fpp, lr}
lll
ct:
i
c
i
p, fffffp
iiaaa ssssspp!, {r5, fp, lr}
fp
ct:
iiiii
sssssp
iiiiiaaaa
What did we overlook?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 197 of 487 (chapter 3: “Functions” up to page 232)
Fact:
stmdb sp!, {r5, fp, lr}
add fp, sp, #4
mov r5, r0
ldr r0, [r5]
cmp r0, #0
bne Case_Others
mov r0, #1
b End_Fact
Case_Others:
sub r0, #1
str r0, [r5]
mov r0, r5
bl Fact
mov r1, r0
ldr r0, [r5]
mul r0, r1
End_Fact:
mov sp, fp
ldmia sp!, {r5, fp, lr}
bx lr
Fib_Fact:
stmdb sp!, {r4, fp, lr}
add fp, sp, #8
sub sp, #4
str r0, [fp, #-12]
bl Fib
mov r4, r0
sub r0, fp, #12
bl Fact
add r0, r0, r4
add sp, #4
ldmia sp!, {r4, fp, lr}
bx lr
tytyy
p,
Fib
db ! { 4 fmdb sp!, {r4, fp, lr
d fp, sp, #8
b sp, #4
r r0, [fp, #-12]
}}
What is the value of x during
one execution of Fact?
F
i
b
_
F
a
c
t
F
a
c
t
1
F
a
c
t
0
F
a
c
t
2
F
a
c
t
3
r5
r4
fp
fp
fp
fp
lr
lr
r5
x (0)
fp
lr
r5
fp
lr
r5
fp
lr
fp
fp
fp
sp
FFFFFF
aaaaa
ccccc
t
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
FFFFFFFF
aaaaaaa
ccccccc
tttt
r5
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 198 of 487 (chapter 3: “Functions” up to page 232)
Parameter passing
Call by …
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
of 487 (chapter 3: “Functions” up to page 232)7f 487 ( h 3
Yet we used this mode
e No read access from inside the
)
e
)
by reference (mutable, no read)
N d f i id th
We should have used either of those modes
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 199 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
A
When to use what?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 200 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
A
FunctionsOne-way and by-copy
Those are side-effect-free and hence the resulting scenarios are ea
sy to analyse.
Copying large data structures might be time consuming or infeasib
le.
Values can be passed in registers.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 201 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
A
FunctionsTwo-way and by-copy
Still side-effect-free within the function (but not on the outside).
Potentially more convenient as memory space can be reused.
Values can be passed in registers.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 202 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
A
FunctionsTwo-way and by-reference
Side-effecting and particular care is required as multiple entities co
uld write on this.
No data has to be replicated.
Values have to be passed in memory.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 203 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
A
FunctionsOne-way-Out and by-reference
Side-effect-free, if new memory is allocated on return
– cannot be enforced on assembly level (requires compiler).
Values have to be passed in memory.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 204 of 487 (chapter 3: “Functions” up to page 232)
Access
by copy by reference
Information
fl ow
in
by value
Parameter becomes a constant
inside the function or is
copied into a local variable.
by reference (immutable)
No write access is allowed
while the function runs (also
from outside the function).
out
by result
Calling function expects the
parameter value to appear in
a specifi c space at return.
by reference (mutable, no read)
No read access from inside the
function, write access on return.
in
&
out
by value result
Parameter is copied to a local
variable and copied back at return.
by reference (mutable)
Function can read and write at any
time. Outside code shall not write.
A
FunctionsOne-way-In and by-reference
Side-effect-free – cannot be enforced on assembly level (requires c
ompiler).
No data has to be replicated.
Values have to be passed in memory.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 205 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
Let there be some (global) data on the stack.
Stack-Base (SB) is a static address,
always pointing to the … well.
Stack-Pointer (SP) points to the current top of the stack.
page 205 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Global variables can also
be stored someplace else.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 206 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The current code prepared to call a function:
Push parameters on the stack.
Works for any data size (unless the stack overfl ows)
and parameter passing mode.
page 206 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
© 2021 Uwe R Zimmer The Australian National Universityy© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
a
Types, storage structures and
passing modes have to be agreed
upon between caller and callee.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 207 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The current code prepared to call a function:
Push parameters on the stack.
Works for any data size (unless the stack overfl ows)
and parameter passing mode.
page 207 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
© 2021 Uwe R Zimmer The Australian National Universityy© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Types, storage structures and
passing modes have to be agreed
upon between caller and callee.
Solved if it’s the same
language, compiler and program.
If the languages or the compilers are
different, then standards will be required.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 208 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
Functions (in programming languages) have a context.
E.g. the surrounding function or the hosting object.
The caller knows this context and provides it.
page 208 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
Context (static) link
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 209 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
Functions (in programming languages) have a context.
E.g. the surrounding function or the hosting object.
The caller knows this context and provides it.
page 209 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
Context (static) link
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Some languages will not have a context
by default, like C or Assembly.
(gnu C expands the C standard
and provides it though)
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 210 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The caller also provides a reference to its own stack frame.
This builds a linear chain of calls through the stack.
Will be used e.g. for debugging (stack trace)
and exception propagation.
page 210 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
The static and dynamic link might
be identical in some cases.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 211 of 487 (chapter 3: “Functions” up to page 232)
Static vs. dynamic links
function a (x : Integer) return Integer is
function b (y : Integer) return Integer is (x + y);
function c (z : Integer) return Integer is (b (z));
begin
return c (x);
end a;
a :: Integer -> Integer
a x = c x
where
b :: Integer -> Integer
b y = x + y
c :: Integer -> Integer
c z = b z
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 212 of 487 (chapter 3: “Functions” up to page 232)
Static vs. dynamic links
function a (x : Integer) return Integer is
function b (y : Integer) return Integer is (x + y);
function c (z : Integer) return Integer is (b (z));
begin
return c (x);
end a;
a :: Integer -> Integer
a x = c x
where
b :: Integer -> Integer
b y = x + y
c :: Integer -> Integer
c z = b z
The dynamic and static link for
function c are both function a.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 213 of 487 (chapter 3: “Functions” up to page 232)
Static vs. dynamic links
function a (x : Integer) return Integer is
function b (y : Integer) return Integer is (x + y);
function c (z : Integer) return Integer is (b (z));
begin
return c (x);
end a;
a :: Integer -> Integer
a x = c x
where
b :: Integer -> Integer
b y = x + y
c :: Integer -> Integer
c z = b z
Dynamic link (prior frame)
The caller of function b is function c.
Hence exceptions raised in b are
handled fi rst in b, then in c, and then a.
The dynamic and static link for
function c are both function a.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 214 of 487 (chapter 3: “Functions” up to page 232)
Static vs. dynamic links
function a (x : Integer) return Integer is
function b (y : Integer) return Integer is (x + y);
function c (z : Integer) return Integer is (b (z));
begin
return c (x);
end a;
a :: Integer -> Integer
a x = c x
where
b :: Integer -> Integer
b y = x + y
c :: Integer -> Integer
c z = b z
Dynamic link (prior frame)
The caller of function b is function c.
Static link (context)
The context for function b is function a.
page 214 of 487 (chapter 3: “Functions” up to page 232)7page 214 of 487 (chapter 3: “Functions” up to page 232)7
Hence b can access x (but not z).
Hence exceptions raised in b are
handled fi rst in b, then in c, and then a.
The dynamic and static link for
function c are both function a.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 215 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The caller also provides a reference to its own stack frame.
This builds a linear chain of calls through the stack.
Will be used e.g. for debugging (stack trace)
and exception propagation.
page 215 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 216 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The last item to be stored before handing over control
is the address of the following instruction.
The control fl ow can later return to this address.
page 216 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 217 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
Control is handed over to the callee.
The Instruction Pointer (IP), sometimes also called
Program Counter (PC) is changed to a new address.
Operations from here are in the control of the callee.
page 217 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 218 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
A Frame Pointer (FP) is established at the bound-
ary between the caller and the callee.
Upwards from the FP: data from this function.
Downwards from the FP:
data provided by the previous function.
page 218 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee SP
Saved resources
FP
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
Saved resources are for instance registers
which the callee is planning to use.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 219 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
Local variables are allocated (by moving the stack pointer).
Local variables can be of any size or structure,
unless the stack overfl ows.
The completes a new stack frame.
page 219 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
SP
Local variables
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
Local variables
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 220 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
Local variables are allocated (by moving the stack pointer).
Local variables can be of any size or structure,
unless the stack overfl ows.
The completes a new stack frame.
page 220 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
SP
Local variables
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
Local variables
While this function is
executing, local variables
can still be added.
Handy, if e.g. the size of a local
variable is not yet determined
when the function starts.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 221 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The next function call will produce the next stack frame.
Variables and parameters from the context stay visible
(via the chain of static links).
page 221 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
SP
Local variables
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Saved resources
FP
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Prior frame (dynamic) link
Return address
SaSaSavvved resoured resoured resourcescesces
Caller
Callee
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 222 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The next function call will produce the next stack frame.
Variables and parameters from the context stay visible
(via the chain of static links).
page 222 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
SP
Local variables
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Saved resources
FP
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Prior frame (dynamic) link
Return address
SaSaSavvved resoured resoured resourcescesces
Caller
Callee
Local variables can only
be added to the currently
executing function.
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 223 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The next function call will produce the next stack frame.
Note which variables and parameters are visible.
page 223 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
SP
Local variables
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
Parameters
Prior frame (dynamic) link
Return address
Local variables
FP
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Saved resources
Caller
Callee
Saved resources
ParPP ameters
Context (static) link
Prior frame (dynamic) link
Return address
Local vLocal vLocal variablesariablesariables
Prior frame (dynamic) link
Return address
SaSaSaSavvvved resoured resoured resoured resourcescescesces
Context (static) link
SB
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 224 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
The next function call will produce the next stack frame.
Note which variables and parameters are visible.
page 224 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
SP
Local variables
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
Parameters
Prior frame (dynamic) link
Return address
Local variables
FP
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Saved resources
Caller
Callee
Saved resources
ParPP ameters
Context (static) link
Prior frame (dynamic) link
Return address
Local vLocal vLocal variablesariablesariables
Prior frame (dynamic) link
Return address
SaSaSaSavvvved resoured resoured resoured resourcescescesces
Context (static) link
SB
Accessing the context like
that can be ineffi cient!
Compilers may chose other
mechanism (e.g. displays,
which make all context
levels accessible at once).
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 225 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame
page 225 of 487 (chapter 3: “Functions” up to page 237 hf h
(Global) variables
SB
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Caller
Callee
Saved resources
FP
SP
Local variables
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
Parameters
Prior frame (dynamic) link
Return address
Local variables
FP
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Saved resources
Caller
Callee
Saved resources
ParPP ameters
Context (static) link
Prior frame (dynamic) link
Return address
Local vLocal vLocal variablesariablesariables
Prior frame (dynamic) link
Return address
SaSaSaSavvvved resoured resoured resoured resourcescescesces
Context (static) link
SB
How fast / complex is the
allocation and deallocation
of local variables and parameters on the stack?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 226 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame – Caller
Pre_Call:
… ; Allocate/identify space for the parameters
… ; Copy the in and in-out
… ; parameters to this space
… ; Potentially provide links
… ; Provide a return address (“Post_Call”)
… ; (usually implicit with the call itself)
Call the function
Post_Call:
… ; Copy the out and in-out parameters
… ; to local variables or registers
… ; Potentially restore the frame pointer
… ; Restore the stack to its previous state
… ; (if the stack has been used)
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
Parameters
Prior frame (dynamic) link
Return address
Local variables
FP
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Saved resources
Caller
Callee
Saved resources
ParPP ameters
Context (static) link
Prior frame (dynamic) link
Return address
Local vLocal vLocal variablesariablesariables
Prior frame (dynamic) link
Return address
SaSaSaSavvvved resoured resoured resoured resourcescescesces
Context (static) link
SB
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 227 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame – Callee
Prologue:
… ; Save all registers which are needed
… ; inside this function to the stack
… ; Establish a new frame pointer
… ; while potentially saving the previous fp
… ; Allocate/identify space for local variables
… ; Potentially initialize local variables
Operations, which will use
local and context variables and parameters
(via the FP(s))
Epilogue:
… ; Potentially restore the prior frame pointer
… ; Restore the stack to its state at entry
Return from function
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
Parameters
Prior frame (dynamic) link
Return address
Local variables
FP
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Saved resources
Caller
Callee
Saved resources
ParPP ameters
Context (static) link
Prior frame (dynamic) link
Return address
Local vLocal vLocal variablesariablesariables
Prior frame (dynamic) link
Return address
SaSaSaSavvvved resoured resoured resoured resourcescescesces
Context (static) link
SB
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 228 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame – Heap
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
Parameters
Prior frame (dynamic) link
Return address
Local variables
FP
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Saved resources
Caller
Callee
Saved resources
ParPP ameters
Context (static) link
Prior frame (dynamic) link
Return address
Local vLocal vLocal variablesariablesariables
Prior frame (dynamic) link
Return address
SaSaSaSavvvved resoured resoured resoured resourcescescesces
Context (static) link
SB
How to keep any memory
allocation after function return?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 229 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame – Heap
By using an out, by-reference parameter,
the link to the newly allocated
memory area is kept.
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
Parameters
Prior frame (dynamic) link
Return address
Local variables
FP
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Saved resources
Saved resources
ParPP ameters
Context (static) link
Prior frame (dynamic) link
Return address
Local vLocal vLocal variablesariablesariables
Prior frame (dynamic) link
Return address
SaSaSaSavvvved resoured resoured resoured resourcescescesces
Context (static) link
SB
Heap
memory
How to keep any memory
allocation after function return?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 230 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame – Heap
By using an out, by-reference parameter,
the link to the newly allocated
memory area is kept.
… and a local variable in the calling
function can keep this link.
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Saved resources
FP
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Prior frame (dynamic) link
Return address
SaSaSavvved resoured resoured resourcescesces
Heap
memory
How to keep any memory
allocation after function return?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 231 of 487 (chapter 3: “Functions” up to page 232)
Generic Stack-Frame – Heap
By using an out, by-reference parameter,
the link to the newly allocated
memory area is kept.
… and a local variable in the calling
function can keep this link.
© 2021 Uwe R Zimmer The Australian National Universityy© 2021
(Global) variables
SB
SP
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Saved resources
FP
Local variables
Parameters
Context (static) link
Prior frame (dynamic) link
Return address
Local variables
Prior frame (dynamic) link
Return address
SaSaSavvved resoured resoured resourcescesces
Heap
memory
How to keep any memory
allocation after function return?
pagpage 231 of 487 (chapter 3: “Functions” up to p7
When to deallocate though?
• Garbage collection (Java)?
• Smart pointers (C++)?
• Reference ownerships (Rust)?
• Scoped pointers / storage pools (Ada)?
Functions
© 2021 Uwe R. Zimmer, The Australian National University page 232 of 487 (chapter 3: “Functions” up to page 232)
Functions
• Framework
• Return address
• Relative addressing
• Parameter passing modes and mechanisms
• Copy versus reference
• Information fl ow directions
• Late evaluation
• Stackframes
• Static and dynamic links
• Parameters
• Local variables
Summary