CS计算机代考程序代写 prolog python data structure chain compiler Java Haskell arm assembly ada COPE-03 Functions.indd

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