Memory Allocation and Program Execution Overview
C
C
h
h
a
a
p
p
t
t
e
e
r
r
1
1
0
0
M
M
e
e
m
m
o
o
r
r
y
y
M
M
o
o
d
d
e
e
l
l
f
f
o
o
r
r
P
P
r
r
o
o
g
g
r
r
a
a
m
m
E
E
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
Original slides by Chris Wilcox,
Modified by Phil Sharp
Colorado State University
1
1
2
2
H
o
w
d
o
w
e
a
l
l
o
c
a
t
e
m
e
m
o
r
y
d
u
r
i
n
g
t
h
e
e
x
e
c
u
t
i
o
n
o
f
a
p
r
o
g
r
a
m
?
P
r
o
g
r
a
m
s
n
e
e
d
m
e
m
o
r
y
f
o
r
c
o
d
e
a
n
d
d
a
t
a
•
I
n
s
t
r
u
c
t
i
o
n
s
,
g
l
o
b
a
l
,
l
o
c
a
l
,
a
n
d
d
y
n
a
m
i
c
a
l
l
y
a
l
l
o
c
a
t
e
d
v
a
r
i
a
b
l
e
s
,
e
t
c
.
M
o
d
e
r
n
p
r
o
g
r
a
m
m
i
n
g
p
r
a
c
t
i
c
e
s
e
n
c
o
u
r
a
g
e
m
a
n
y
(
r
e
u
s
a
b
l
e
)
f
u
n
c
t
i
o
n
s
,
c
a
l
l
a
b
l
e
f
r
o
m
a
n
y
w
h
e
r
e
.
•
F
u
n
c
t
i
o
n
m
a
y
b
e
c
a
l
l
e
d
m
u
l
t
i
p
l
e
t
i
m
e
s
b
e
f
o
r
e
f
i
r
s
t
c
a
l
l
r
e
t
u
r
n
s
S
o
m
e
m
e
m
o
r
y
c
a
n
b
e
s
t
a
t
i
c
a
l
l
y
a
l
l
o
c
a
t
e
d
,
s
i
n
c
e
t
h
e
s
i
z
e
a
n
d
t
y
p
e
i
s
k
n
o
w
n
a
t
c
o
m
p
i
l
e
t
i
m
e
.
•
(
g
l
o
b
a
l
v
a
r
i
a
b
l
e
s
)
S
o
m
e
m
e
m
o
r
y
m
u
s
t
b
e
a
l
l
o
c
a
t
e
d
d
y
n
a
m
i
c
a
l
l
y
,
s
i
z
e
a
n
d
t
y
p
e
i
s
u
n
k
n
o
w
n
a
t
c
o
m
p
i
l
e
t
i
m
e
.
•
(
d
y
n
a
m
i
c
a
l
l
y
a
l
l
o
c
a
t
e
d
m
e
m
o
r
y
,
i
.
e
.
m
a
l
l
o
c
)
2
2
3
3
W
h
y
i
s
m
e
m
o
r
y
a
l
l
o
c
a
t
i
o
n
i
m
p
o
r
t
a
n
t
?
T
T
o
o
d
d
o
o
u
u
s
s
e
e
f
f
u
u
l
l
w
w
o
o
r
r
k
k
a
a
l
l
l
l
p
p
r
r
o
o
g
g
r
r
a
a
m
m
s
s
m
m
u
u
s
s
t
t
b
b
e
e
a
a
b
b
l
l
e
e
t
t
o
o
s
s
t
t
o
o
r
r
e
e
d
d
a
a
t
t
a
a
.
.
T
T
h
h
e
e
r
r
e
e
a
a
r
r
e
e
n
n
o
o
t
t
e
e
n
n
o
o
u
u
g
g
h
h
r
r
e
e
g
g
i
i
s
s
t
t
e
e
r
r
s
s
t
t
o
o
s
s
t
t
o
o
r
r
e
e
e
e
v
v
e
e
r
r
y
y
t
t
h
h
i
i
n
n
g
g
t
t
h
h
a
a
t
t
i
i
s
s
r
r
e
e
q
q
u
u
i
i
r
r
e
e
d
d
i
i
n
n
a
a
r
r
e
e
g
g
i
i
s
s
t
t
e
e
r
r
.
.
•
P
P
a
a
s
s
s
s
i
i
n
n
g
g
s
s
t
t
u
u
c
c
t
t
s
s
b
b
y
y
v
v
a
a
l
l
u
u
e
e
D
D
y
y
n
n
a
a
m
m
i
i
c
c
(
(
h
h
e
e
a
a
p
p
)
)
a
a
l
l
l
l
o
o
c
c
a
a
t
t
i
i
o
o
n
n
i
i
s
s
s
s
l
l
o
o
w
w
e
e
r
r
t
t
h
h
a
a
t
t
s
s
t
t
a
a
t
t
i
i
c
c
a
a
l
l
l
l
o
o
c
c
a
a
t
t
i
i
o
o
n
n
s
s
o
o
n
n
o
o
t
t
i
i
d
d
e
e
a
a
l
l
f
f
o
o
r
r
a
a
l
l
l
l
m
m
e
e
m
m
o
o
r
r
y
y
s
s
t
t
o
o
r
r
a
a
g
g
e
e
.
.
S
S
t
t
a
a
t
t
i
i
c
c
a
a
l
l
l
l
o
o
c
c
a
a
t
t
i
i
o
o
n
n
o
o
f
f
m
m
e
e
m
m
o
o
r
r
y
y
r
r
e
e
s
s
o
o
u
u
r
r
c
c
e
e
s
s
i
i
s
s
i
i
n
n
f
f
l
l
e
e
x
x
i
i
b
b
l
l
e
e
a
a
n
n
d
d
c
c
a
a
n
n
b
b
e
e
i
i
n
n
e
e
f
f
f
f
i
i
c
c
i
i
e
e
n
n
t
t
.
.
3
3
4
4
W
h
a
t
d
o
w
e
c
a
r
e
a
b
o
u
t
?
•
F
F
a
a
s
s
t
t
p
p
r
r
o
o
g
g
r
r
a
a
m
m
e
e
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
•
E
E
f
f
f
f
i
i
c
c
i
i
e
e
n
n
t
t
m
m
e
e
m
m
o
o
r
r
y
y
u
u
s
s
a
a
g
g
e
e
•
A
A
v
v
o
o
i
i
d
d
m
m
e
e
m
m
o
o
r
r
y
y
f
f
r
r
a
a
g
g
m
m
e
e
n
n
t
t
a
a
t
t
i
i
o
o
n
n
•
M
M
a
a
i
i
n
n
t
t
a
a
i
i
n
n
d
d
a
a
t
t
a
a
l
l
o
o
c
c
a
a
l
l
i
i
t
t
y
y
•
A
A
l
l
l
l
o
o
w
w
r
r
e
e
c
c
u
u
r
r
s
s
i
i
v
v
e
e
c
c
a
a
l
l
l
l
s
s
•
S
S
u
u
p
p
p
p
o
o
r
r
t
t
p
p
a
a
r
r
a
a
l
l
l
l
e
e
l
l
e
e
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
•
M
M
i
i
n
n
i
i
m
m
i
i
z
z
e
e
r
r
e
e
s
s
o
o
u
u
r
r
c
c
e
e
a
a
l
l
l
l
o
o
c
c
a
a
t
t
i
i
o
o
n
n
•
M
e
m
o
r
y
s
h
o
u
l
d
n
’
t
b
e
a
l
l
o
c
a
t
e
d
f
o
r
f
u
n
c
t
i
o
n
s
t
h
a
t
a
r
e
n
o
t
e
x
e
c
u
t
e
d
.
5
5
C
o
n
s
i
d
e
r
t
h
e
f
o
l
l
o
w
i
n
g
c
o
d
e
:
int
i = 10;
int
main(){int
a = 5;
int
b = 20;
int
c = foo(a, b);
}
int
foo(int x, int y){int
z;
z = x + y;
return z;
}
What needs to be stored?
•
Code, parameters, locals, globals, return values
5
5
6
6
S
t
o
r
a
g
e
R
e
q
u
i
r
e
m
e
n
t
s
•
C
C
o
o
d
d
e
e
m
m
u
u
s
s
t
t
b
b
e
e
s
s
t
t
o
o
r
r
e
e
d
d
i
i
n
n
m
m
e
e
m
m
o
o
r
r
y
y
s
s
o
o
t
t
h
h
a
a
t
t
w
w
e
e
c
c
a
a
n
n
e
e
x
x
e
e
c
c
u
u
t
t
e
e
t
t
h
h
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
.
.
•
T
T
h
h
e
e
r
r
e
e
t
t
u
u
r
r
n
n
a
a
d
d
d
d
r
r
e
e
s
s
s
s
m
m
u
u
s
s
t
t
b
b
e
e
s
s
t
t
o
o
r
r
e
e
d
d
s
s
o
o
t
t
h
h
a
a
t
t
c
c
o
o
n
n
t
t
r
r
o
o
l
l
c
c
a
a
n
n
b
b
e
e
r
r
e
e
t
t
u
u
r
r
n
n
e
e
d
d
t
t
o
o
t
t
h
h
e
e
c
c
a
a
l
l
l
l
e
e
r
r
.
.
•
P
P
a
a
r
r
a
a
m
m
e
e
t
t
e
e
r
r
s
s
m
m
u
u
s
s
t
t
b
b
e
e
s
s
e
e
n
n
t
t
f
f
r
r
o
o
m
m
t
t
h
h
e
e
c
c
a
a
l
l
l
l
e
e
r
r
t
t
o
o
t
t
h
h
e
e
c
c
a
a
l
l
l
l
e
e
e
e
•
R
R
e
e
t
t
u
u
r
r
n
n
v
v
a
a
l
l
u
u
e
e
s
s
m
m
u
u
s
s
t
t
b
b
e
e
s
s
e
e
n
n
t
t
f
f
r
r
o
o
m
m
t
t
h
h
e
e
c
c
a
a
l
l
l
l
e
e
e
e
t
t
o
o
t
t
h
h
e
e
c
c
a
a
l
l
l
l
e
e
r
r
•
L
L
o
o
c
c
a
a
l
l
v
v
a
a
r
r
i
i
a
a
b
b
l
l
e
e
s
s
f
f
o
o
r
r
t
t
h
h
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
m
m
u
u
s
s
t
t
b
b
e
e
s
s
t
t
o
o
r
r
e
e
d
d
s
s
o
o
m
m
e
e
w
w
h
h
e
e
r
r
e
e
,
,
i
i
s
s
o
o
n
n
e
e
c
c
o
o
p
p
y
y
e
e
n
n
o
o
u
u
g
g
h
h
?
?
6
6
7
7
P
P
o
o
s
s
s
s
i
i
b
b
l
l
e
e
S
S
o
o
l
l
u
u
t
t
i
i
o
o
n
n
:
:
M
M
i
i
x
x
e
e
d
d
C
C
o
o
d
d
e
e
a
a
n
n
d
d
D
D
a
a
t
t
a
a
Function implementation:
Function implementation:
foo BR foo_begin ; skip over save locations
foo BR foo_begin ; skip over save locations
foo_rv .BLKW 1 ; return value
foo_rv .BLKW 1 ; return value
foo_ra .BLKW 1 ; return address
foo_ra .BLKW 1 ; return address
foo_paramx .BLKW 1 ; ‘x’ parameter
foo_paramx .BLKW 1 ; ‘x’ parameter
foo_paramy .BLKW 1 ; ‘y’ parameter
foo_paramy .BLKW 1 ; ‘y’ parameter
foo_localz .BLKW 1 ; ‘z’ local
foo_localz .BLKW 1 ; ‘z’ local
foo_begin ST R7, foo_ra ; save return
foo_begin ST R7, foo_ra ; save return
…
…
LD R7, foo_ra ; restore return
LD R7, foo_ra ; restore return
RET
RET
Construct data section by appending foo_
Construct data section by appending foo_
7
7
8
8
P
o
s
s
i
b
l
e
S
o
l
u
t
i
o
n
:
M
i
x
e
d
C
o
d
e
a
n
d
D
a
t
a
Calling sequence
Calling sequence
ST R1, foo_paramx ; R1 has ‘x’
ST R1, foo_paramx ; R1 has ‘x’
ST R2, foo_paramy ; R2 has ‘y’
ST R2, foo_paramy ; R2 has ‘y’
JSR foo ; Function call
JSR foo ; Function call
LD R3, foo_rv ; R3 = return value
LD R3, foo_rv ; R3 = return value
•
C
o
d
e
g
e
n
e
r
a
t
i
o
n
i
s
r
e
l
a
t
i
v
e
l
y
s
i
m
p
l
e
.
•
F
e
w
i
n
s
t
r
u
c
t
i
o
n
s
a
r
e
s
p
e
n
t
m
o
v
i
n
g
d
a
t
a
.
8
8
9
9
P
P
o
o
s
s
s
s
i
i
b
b
l
l
e
e
S
S
o
o
l
l
u
u
t
t
i
i
o
o
n
n
:
:
M
M
i
i
x
x
e
e
d
d
C
C
o
o
d
d
e
e
a
a
n
n
d
d
D
D
a
a
t
t
a
a
Advantages
Advantages
:
:
•
C
C
o
o
d
d
e
e
a
a
n
n
d
d
d
d
a
a
t
t
a
a
a
a
r
r
e
e
c
c
l
l
o
o
s
s
e
e
t
t
o
o
g
g
e
e
t
t
h
h
e
e
r
r
•
C
C
o
o
n
n
c
c
e
e
p
p
t
t
u
u
a
a
l
l
l
l
y
y
e
e
a
a
s
s
y
y
t
t
o
o
u
u
n
n
d
d
e
e
r
r
s
s
t
t
a
a
n
n
d
d
•
M
M
i
i
n
n
i
i
m
m
i
i
z
z
e
e
s
s
r
r
e
e
g
g
i
i
s
s
t
t
e
e
r
r
u
u
s
s
a
a
g
g
e
e
f
f
o
o
r
r
v
v
a
a
r
r
i
i
a
a
b
b
l
l
e
e
s
s
•
D
D
a
a
t
t
a
a
p
p
e
e
r
r
s
s
i
i
s
s
t
t
s
s
t
t
h
h
r
r
o
o
u
u
g
g
h
h
l
l
i
i
f
f
e
e
o
o
f
f
p
p
r
r
o
o
g
g
r
r
a
a
m
m
Disadvantages:
Disadvantages:
•
C
C
a
a
n
n
n
n
o
o
t
t
h
h
a
a
n
n
d
d
l
l
e
e
r
r
e
e
c
c
u
u
r
r
s
s
i
i
o
o
n
n
o
o
r
r
p
p
a
a
r
r
a
a
l
l
l
l
e
e
l
l
e
e
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
•
C
C
o
o
d
d
e
e
i
i
s
s
v
v
u
u
l
l
n
n
e
e
r
r
a
a
b
b
l
l
e
e
t
t
o
o
s
s
e
e
l
l
f
f
-
-
m
m
o
o
d
d
i
i
f
f
i
i
c
c
a
a
t
t
i
i
o
o
n
n
•
C
C
o
o
n
n
s
s
u
u
m
m
e
e
s
s
r
r
e
e
s
s
o
o
u
u
r
r
c
c
e
e
f
f
o
o
r
r
i
i
n
n
a
a
c
c
t
t
i
i
v
v
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
s
s
9
9
10
10
P
o
s
s
i
b
l
e
S
o
l
u
t
i
o
n
:
S
e
p
a
r
a
t
e
C
o
d
e
a
n
d
D
a
t
a
Data Storage:
Data Storage:
;memory location x4000
;memory location x4000
foo_rv .BLKW 1 ; foo return value
foo_rv .BLKW 1 ; foo return value
foo_ra .BLKW 1 ; foo return address
foo_ra .BLKW 1 ; foo return address
foo_paramx .BLKW 1 ; foo ‘x’ parameter
foo_paramx .BLKW 1 ; foo ‘x’ parameter
foo_paramy .BLKW 1 ; foo ‘y’ parameter
foo_paramy .BLKW 1 ; foo ‘y’ parameter
foo_localz .BLKW 1 ; foo ‘z’ local
foo_localz .BLKW 1 ; foo ‘z’ local
bar_rv .BLKW 1 ; bar return value
bar_rv .BLKW 1 ; bar return value
bar_ra .BLKW 1 ; bar return address
bar_ra .BLKW 1 ; bar return address
bar_paramw .BLKW 1 ; bar ‘w’ parameter
bar_paramw .BLKW 1 ; bar ‘w’ parameter
Code for foo() and bar() are somewhere else
Code for foo() and bar() are somewhere else
•
say x3000
say x3000
Function call code is similar to mixed solution
Function call code is similar to mixed solution
•
Why might this not be the case
Why might this not be the case
10
10
P
o
s
s
i
b
l
e
S
o
l
u
t
i
o
n
:
S
e
p
a
r
a
t
e
C
o
d
e
a
n
d
D
a
t
a
Advantages:
Advantages:
•
C
C
o
o
d
d
e
e
c
c
a
a
n
n
b
b
e
e
m
m
a
a
r
r
k
k
e
e
d
d
‘
‘
r
r
e
e
a
a
d
d
o
o
n
n
l
l
y
y
’
’
-
-
B
B
e
e
c
c
a
a
u
u
s
s
e
e
c
c
o
o
d
d
e
e
i
i
s
s
s
s
e
e
p
p
a
a
r
r
a
a
t
t
e
e
d
d
f
f
r
r
o
o
m
m
d
d
a
a
t
t
a
a
i
i
n
n
m
m
e
e
m
m
o
o
r
r
y
y
•
C
C
o
o
n
n
c
c
e
e
p
p
t
t
u
u
a
a
l
l
l
l
y
y
e
e
a
a
s
s
y
y
t
t
o
o
u
u
n
n
d
d
e
e
r
r
s
s
t
t
a
a
n
n
d
d
•
E
E
a
a
r
r
l
l
y
y
F
F
o
o
r
r
t
t
r
r
a
a
n
n
u
u
s
s
e
e
d
d
t
t
h
h
i
i
s
s
s
s
c
c
h
h
e
e
m
m
e
e
•
D
D
a
a
t
t
a
a
p
p
e
e
r
r
s
s
i
i
s
s
t
t
s
s
t
t
h
h
r
r
o
o
u
u
g
g
h
h
l
l
i
i
f
f
e
e
o
o
f
f
p
p
r
r
o
o
g
g
r
r
a
a
m
m
Disadvantages:
Disadvantages:
•
C
C
a
a
n
n
n
n
o
o
t
t
h
h
a
a
n
n
d
d
l
l
e
e
r
r
e
e
c
c
u
u
r
r
s
s
i
i
o
o
n
n
o
o
r
r
p
p
a
a
r
r
a
a
l
l
l
l
e
e
l
l
e
e
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
•
C
C
o
o
n
n
s
s
u
u
m
m
e
e
s
s
r
r
e
e
s
s
o
o
u
u
r
r
c
c
e
e
f
f
o
o
r
r
i
i
n
n
a
a
c
c
t
t
i
i
v
v
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
s
s
•
I
I
n
n
s
s
t
t
r
r
u
u
c
c
t
t
i
i
o
o
n
n
s
s
a
a
r
r
e
e
s
s
t
t
o
o
r
r
e
e
d
d
i
i
n
n
c
c
o
o
d
d
e
e
s
s
e
e
g
g
m
m
e
e
n
n
t
t
•
G
G
l
l
o
o
b
b
a
a
l
l
d
d
a
a
t
t
a
a
i
i
s
s
s
s
t
t
o
o
r
r
e
e
d
d
i
i
n
n
d
d
a
a
t
t
a
a
s
s
e
e
g
g
m
m
e
e
n
n
t
t
•
S
S
t
t
a
a
t
t
i
i
c
c
a
a
l
l
l
l
y
y
a
a
l
l
l
l
o
o
c
c
a
a
t
t
e
e
d
d
m
m
e
e
m
m
o
o
r
r
y
y
u
u
s
s
e
e
s
s
s
s
t
t
a
a
c
c
k
k
•
D
D
y
y
n
n
a
a
m
m
i
i
c
c
a
a
l
l
l
l
y
y
a
a
l
l
l
l
o
o
c
c
a
a
t
t
e
e
d
d
m
m
e
e
m
m
o
o
r
r
y
y
u
u
s
s
e
e
s
s
h
h
e
e
a
a
p
p
12
12
R
e
a
l
S
o
l
u
t
i
o
n
:
E
x
e
c
u
t
i
o
n
S
t
a
c
k
•
C
C
o
o
d
d
e
e
s
s
e
e
g
g
m
m
e
e
n
n
t
t
i
i
s
s
w
w
r
r
i
i
t
t
e
e
p
p
r
r
o
o
t
t
e
e
c
c
t
t
e
e
d
d
•
P
P
r
r
o
o
g
g
r
r
a
a
m
m
c
c
a
a
n
n
’
’
t
t
m
m
o
o
d
d
i
i
f
f
y
y
i
i
t
t
s
s
e
e
l
l
f
f
•
D
D
a
a
t
t
a
a
s
s
e
e
g
g
m
m
e
e
n
n
t
t
f
f
o
o
r
r
i
i
n
n
i
i
t
t
i
i
a
a
l
l
i
i
z
z
e
e
d
d
a
a
n
n
d
d
u
u
n
n
i
i
n
n
i
i
t
t
i
i
a
a
l
l
i
i
z
z
e
e
d
d
g
g
l
l
o
o
b
b
a
a
l
l
s
s
•
H
H
e
e
a
a
p
p
c
c
a
a
n
n
b
b
e
e
f
f
r
r
a
a
g
g
m
m
e
e
n
n
t
t
e
e
d
d
•
S
S
t
t
a
a
c
c
k
k
s
s
i
i
z
z
e
e
i
i
s
s
u
u
s
s
u
u
a
a
l
l
l
l
y
y
l
l
i
i
m
m
i
i
t
t
e
e
d
d
•
S
S
t
t
a
a
c
c
k
k
c
c
a
a
n
n
g
g
r
r
o
o
w
w
e
e
i
i
t
t
h
h
e
e
r
r
d
d
i
i
r
r
e
e
c
c
t
t
i
i
o
o
n
n
(
(
u
u
s
s
u
u
a
a
l
l
c
c
o
o
n
n
v
v
e
e
n
n
t
t
i
i
o
o
n
n
i
i
s
s
d
d
o
o
w
w
n
n
)
)
12
12
S
t
a
c
k
s
A
L
I
F
O
(
l
a
s
t
-
i
n
f
i
r
s
t
-
o
u
t
)
A
b
s
t
r
a
c
t
D
a
t
a
T
y
p
e
.
•
T
h
e
f
i
r
s
t
t
h
i
n
g
y
o
u
p
u
t
i
n
i
s
t
h
e
l
a
s
t
t
h
i
n
g
y
o
u
t
a
k
e
o
u
t
.
•
T
h
e
l
a
s
t
t
h
i
n
g
y
o
u
p
u
t
i
n
i
s
t
h
e
f
i
r
s
t
t
h
i
n
g
y
o
u
t
a
k
e
o
u
t
.
A
b
s
t
r
a
c
t
D
a
t
a
T
y
p
e
(
A
D
T
)
:
A
d
a
t
a
t
y
p
e
t
h
a
t
i
s
d
e
f
i
e
d
b
y
i
t
s
b
e
h
a
v
i
o
r
.
T
h
e
u
s
e
r
o
f
t
h
e
A
D
T
d
o
e
s
n
o
t
n
e
e
d
t
o
k
n
o
w
h
o
w
t
h
e
b
e
h
a
v
i
o
r
i
s
a
c
h
i
e
v
e
d
.
O
t
h
e
r
e
x
a
m
p
l
e
s
:
L
i
s
t
s
,
Q
u
e
u
e
s
,
H
e
a
p
s
,
S
e
t
s
,
M
a
p
s
,
e
t
c
.
T
w
o
m
a
i
n
o
p
e
r
a
t
i
o
n
s
:
P
U
S
H
:
a
d
d
a
n
i
t
e
m
t
o
t
h
e
s
t
a
c
k
P
O
P
:
r
e
m
o
v
e
a
n
i
t
e
m
f
r
o
m
t
h
e
s
t
a
c
k
S
t
a
c
k
s
a
r
e
u
s
e
d
i
n
m
a
n
y
a
r
e
a
s
o
f
C
o
m
p
u
t
e
r
S
c
i
e
n
c
e
e
x
.
C
o
m
p
i
l
e
r
s
,
G
r
a
p
h
/
T
r
e
e
t
r
a
v
e
r
s
a
l
s
,
P
D
A
A
P
h
y
s
i
c
a
l
S
t
a
c
k
C
o
i
n
r
e
s
t
i
n
t
h
e
a
r
m
o
f
a
n
a
u
t
o
m
o
b
i
l
e
F
i
r
s
t
q
u
a
r
t
e
r
o
u
t
i
s
t
h
e
l
a
s
t
q
u
a
r
t
e
r
i
n
.
1
9
9
5
1
9
9
6
1
9
9
8
1
9
8
2
1
9
9
5
1
9
9
8
1
9
8
2
1
9
9
5
Initial State
After
One Push
After Three
More Pushes
After
One Pop
A
S
o
f
t
w
a
r
e
I
m
p
l
e
m
e
n
t
a
t
i
o
n
D
a
t
a
i
t
e
m
s
d
o
n
'
t
m
o
v
e
i
n
m
e
m
o
r
y
,
j
u
s
t
o
u
r
i
d
e
a
a
b
o
u
t
t
h
e
r
e
t
h
e
T
O
P
o
f
t
h
e
s
t
a
c
k
i
s
.
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
T
O
P
/ / / / / /
/ / / / / /
/ / / / / /
#18
/ / / / / /
T
O
P
#12
#5
#31
#18
/ / / / / /
T
O
P
#12
#5
#31
#18
/ / / / / /
T
O
P
Initial State
After
One Push
After Three
More Pushes
After
Two Pops
x4000
x3FFF
x3FFC
x3FFE
R
6
R
6
R
6
R
6
B
y
c
o
n
v
e
n
t
i
o
n
,
R
6
h
o
l
d
s
t
h
e
T
o
p
o
f
S
t
a
c
k
(
T
O
S
)
p
o
i
n
t
e
r
.
16
16
H
o
w
d
o
e
s
t
h
e
E
x
e
c
u
t
i
o
n
S
t
a
c
k
w
o
r
k
?
•
F
F
i
i
r
r
s
s
t
t
I
I
n
n
,
,
L
L
a
a
s
s
t
t
O
O
u
u
t
t
(
(
F
F
I
I
L
L
O
O
)
)
d
d
a
a
t
t
a
a
s
s
t
t
r
r
u
u
c
c
t
t
u
u
r
r
e
e
•
P
P
U
U
S
S
H
H
a
a
d
d
d
d
s
s
d
d
a
a
t
t
a
a
,
,
P
P
O
O
P
P
r
r
e
e
m
m
o
o
v
v
e
e
s
s
d
d
a
a
t
t
a
a
•
S
S
t
t
a
a
c
c
k
k
g
g
r
r
o
o
w
w
s
s
a
a
n
n
d
d
s
s
h
h
r
r
i
i
n
n
k
k
s
s
a
a
s
s
d
d
a
a
t
t
a
a
i
i
s
s
a
a
d
d
d
d
e
e
d
d
a
a
n
n
d
d
r
r
e
e
m
m
o
o
v
v
e
e
d
d
•
S
S
t
t
a
a
c
c
k
k
g
g
r
r
o
o
w
w
s
s
d
d
o
o
w
w
n
n
w
w
a
a
r
r
d
d
i
i
n
n
m
m
e
e
m
m
o
o
r
r
y
y
•
F
F
u
u
n
n
c
c
t
t
i
i
o
o
n
n
c
c
a
a
l
l
l
l
s
s
a
a
l
l
l
l
o
o
c
c
a
a
t
t
e
e
s
s
p
p
a
a
c
c
e
e
o
o
n
n
t
t
h
h
e
e
s
s
t
t
a
a
c
c
k
k
f
f
o
o
r
r
a
a
s
s
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
(
(
p
p
u
u
s
s
h
h
)
)
•
A
A
c
c
t
t
i
i
v
v
a
a
t
t
i
i
o
o
n
n
r
r
e
e
c
c
o
o
r
r
d
d
i
i
s
s
a
a
n
n
o
o
t
t
h
h
e
e
r
r
w
w
o
o
r
r
d
d
f
f
o
o
r
r
s
s
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
•
R
R
e
e
t
t
u
u
r
r
n
n
i
i
n
n
g
g
f
f
r
r
o
o
m
m
a
a
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
c
c
l
l
e
e
a
a
n
n
s
s
u
u
p
p
b
b
y
y
r
r
e
e
m
m
o
o
v
v
i
i
n
n
g
g
(
(
p
p
o
o
p
p
p
p
i
i
n
n
g
g
)
)
t
t
h
h
e
e
s
s
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
•
D
D
o
o
n
n
e
e
s
s
i
i
m
m
p
p
l
l
y
y
b
b
y
y
c
c
h
h
a
a
n
n
g
g
i
i
n
n
g
g
t
t
h
h
e
e
v
v
a
a
l
l
u
u
e
e
i
i
n
n
R
R
6
6
•
N
N
e
e
s
s
t
t
e
e
d
d
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
c
c
a
a
l
l
l
l
s
s
p
p
u
u
s
s
h
h
o
o
n
n
s
s
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
o
o
f
f
c
c
a
a
l
l
l
l
e
e
d
d
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
•
B
y
l
o
o
k
i
n
g
a
t
t
h
e
e
n
t
i
r
e
s
t
a
c
k
i
n
m
e
m
o
r
y
i
t
i
s
p
o
s
s
i
b
l
e
t
o
s
e
e
t
h
e
h
i
s
t
o
r
y
o
f
f
u
n
c
t
i
o
n
c
a
l
l
s
t
h
a
t
l
e
a
d
t
o
t
h
e
c
u
r
r
e
n
t
f
u
n
c
t
i
o
n
•
U
s
e
f
u
l
f
o
r
d
e
b
u
g
g
i
n
g
•
S
t
a
c
k
t
r
a
c
e
16
16
17
17
E
x
e
c
u
t
i
o
n
/
R
u
n
T
i
m
e
S
t
a
c
k
•
Each rectangle corresponds to one stack frame, which is the stack space allocated
Each rectangle corresponds to one stack frame, which is the stack space allocated
to a particular invocation of a function
to a particular invocation of a function
•
main() calls foo(5,6)
main() calls foo(5,6)
•
foo() calls bar(‘A’)
foo() calls bar(‘A’)
•
bar() calls baz(7)
bar() calls baz(7)
•
baz() calls baz(6)
baz() calls baz(6)
17
17
18
18
W
W
h
h
a
a
t
t
h
h
a
a
s
s
t
t
o
o
h
h
a
a
p
p
p
p
e
e
n
n
i
i
n
n
a
a
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
c
c
a
a
l
l
l
l
•
Caller
Caller
passes arguments to Callee
passes arguments to Callee
•
Caller
Caller
invokes subroutine (JSR).
invokes subroutine (JSR).
•
Callee
Callee
allocates space for return value.
allocates space for return value.
•
Callee
Callee
executes function code.
executes function code.
•
Callee
Callee
stores result into return value space.
stores result into return value space.
•
Callee
Callee
returns (JMP R7).
returns (JMP R7).
•
Caller
Caller
loads return value.
loads return value.
Parameters, return value, return address, and locals are stored on the stack.
Parameters, return value, return address, and locals are stored on the stack.
18
18
S
S
t
t
a
a
c
c
k
k
F
F
r
r
a
a
m
m
e
e
/
/
A
A
c
c
t
t
i
i
v
v
a
a
t
t
i
i
o
o
n
n
R
R
e
e
c
c
o
o
r
r
d
d
19
19
A
A
s
s
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
o
o
r
r
a
a
c
c
t
t
i
i
v
v
a
a
t
t
i
i
o
o
n
n
r
r
e
e
c
c
o
o
r
r
d
d
h
h
o
o
l
l
d
d
s
s
t
t
h
h
e
e
m
m
e
e
m
m
o
o
r
r
y
y
r
r
e
e
q
q
u
u
i
i
r
r
e
e
d
d
f
f
o
o
r
r
a
a
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
c
c
a
a
l
l
l
l
:
:
•
S
S
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
b
b
e
e
l
l
o
o
w
w
t
t
h
h
i
i
s
s
f
f
r
r
a
a
m
m
e
e
c
c
o
o
n
n
t
t
a
a
i
i
n
n
s
s
t
t
h
h
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
t
t
h
h
a
a
t
t
c
c
a
a
l
l
l
l
e
e
d
d
t
t
h
h
i
i
s
s
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
.
.
•
S
S
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
a
a
b
b
o
o
v
v
e
e
t
t
h
h
i
i
s
s
f
f
r
r
a
a
m
m
e
e
c
c
o
o
n
n
t
t
a
a
i
i
n
n
s
s
t
t
h
h
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
s
s
c
c
a
a
l
l
l
l
e
e
d
d
f
f
r
r
o
o
m
m
t
t
h
h
i
i
s
s
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
.
.
•
C
C
a
a
l
l
l
l
e
e
r
r
p
p
u
u
s
s
h
h
e
e
s
s
p
p
a
a
r
r
a
a
m
m
e
e
t
t
e
e
r
r
s
s
.
.
•
C
C
a
a
l
l
l
l
e
e
e
e
a
a
l
l
l
l
o
o
c
c
a
a
t
t
e
e
s
s
s
s
p
p
a
a
c
c
e
e
f
f
o
o
r
r
t
t
h
h
e
e
r
r
e
e
t
t
u
u
r
r
n
n
v
v
a
a
l
l
u
u
e
e
,
,
s
s
a
a
v
v
e
e
s
s
t
t
h
h
e
e
r
r
e
e
t
t
u
u
r
r
n
n
a
a
d
d
d
d
r
r
e
e
s
s
s
s
,
,
a
a
l
l
l
l
o
o
c
c
a
a
t
t
e
e
s
s
/
/
f
f
r
r
e
e
e
e
s
s
l
l
o
o
c
c
a
a
l
l
v
v
a
a
r
r
i
i
a
a
b
b
l
l
e
e
s
s
,
,
a
a
n
n
d
d
s
s
t
t
o
o
r
r
e
e
s
s
t
t
h
h
e
e
r
r
e
e
t
t
u
u
r
r
n
n
v
v
a
a
l
l
u
u
e
e
.
.
19
19
20
20
S
S
t
t
a
a
c
c
k
k
P
P
o
o
i
i
n
n
t
t
e
e
r
r
s
s
•
W
W
e
e
w
w
i
i
l
l
l
l
n
n
e
e
e
e
d
d
a
a
v
v
a
a
r
r
i
i
a
a
b
b
l
l
e
e
t
t
o
o
s
s
t
t
o
o
r
r
e
e
t
t
h
h
e
e
s
t
a
c
k
p
o
i
n
t
e
r
(
(
S
S
P
P
)
)
,
,
•
L
L
C
C
3
3
a
a
s
s
s
s
e
e
m
m
b
b
l
l
y
y
u
u
s
s
e
e
s
s
R
R
6
6
.
.
•
S
S
t
t
a
a
c
c
k
k
e
e
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
i
i
s
s
u
u
b
b
i
i
q
q
u
u
i
i
t
t
o
o
u
u
s
s
,
,
s
s
o
o
h
h
a
a
r
r
d
d
w
w
a
a
r
r
e
e
c
c
a
a
n
n
h
h
a
a
v
v
e
e
a
a
s
s
p
p
e
e
c
c
i
i
a
a
l
l
r
r
e
e
g
g
i
i
s
s
t
t
e
e
r
r
t
t
o
o
h
h
o
o
l
l
d
d
t
t
h
h
e
e
s
s
t
t
a
a
c
c
k
k
p
p
o
o
i
i
n
n
t
t
e
e
r
r
,
,
s
s
o
o
m
m
e
e
t
t
i
i
m
m
e
e
s
s
e
e
v
v
e
e
n
n
s
s
p
p
e
e
c
c
i
i
f
f
i
i
c
c
i
i
n
n
s
s
t
t
r
r
u
u
c
c
t
t
i
i
o
o
n
n
s
s
.
.
•
P
P
r
r
o
o
b
b
l
l
e
e
m
m
:
:
s
s
t
t
a
a
c
c
k
k
p
p
o
o
i
i
n
n
t
t
e
e
r
r
i
i
s
s
d
d
i
i
f
f
f
f
i
i
c
c
u
u
l
l
t
t
t
t
o
o
u
u
s
s
e
e
t
t
o
o
a
a
c
c
c
c
e
e
s
s
s
s
d
d
a
a
t
t
a
a
,
,
s
s
i
i
n
n
c
c
e
e
i
i
t
t
m
m
o
o
v
v
e
e
s
s
a
a
r
r
o
o
u
u
n
n
d
d
c
c
o
o
n
n
s
s
t
t
a
a
n
n
t
t
l
l
y
y
.
.
•
S
S
o
o
l
l
u
u
t
t
i
i
o
o
n
n
:
:
a
a
l
l
l
l
o
o
c
c
a
a
t
t
e
e
a
a
n
n
o
o
t
t
h
h
e
e
r
r
v
v
a
a
r
r
i
i
a
a
b
b
l
l
e
e
c
c
a
a
l
l
l
l
e
e
d
d
a
a
f
r
a
m
e
p
o
i
n
t
e
r
(
(
F
F
P
P
)
)
,
,
f
f
o
o
r
r
s
s
t
t
a
a
c
c
k
k
f
f
r
r
a
a
m
m
e
e
,
,
u
u
s
s
e
e
s
s
R
R
5
5
.
.
•
F
F
r
r
a
a
m
m
e
e
p
p
o
o
i
i
n
n
t
t
e
e
r
r
p
p
o
o
i
i
n
n
t
t
s
s
t
t
o
o
t
t
h
h
e
e
s
s
a
a
m
m
e
e
l
l
o
o
c
c
a
a
t
t
i
i
o
o
n
n
f
f
o
o
r
r
d
d
u
u
r
r
a
a
t
t
i
i
o
o
n
n
o
o
f
f
t
t
h
h
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
•
W
W
h
h
e
e
r
r
e
e
s
s
h
h
o
o
u
u
l
l
d
d
f
f
r
r
a
a
m
m
e
e
p
p
o
o
i
i
n
n
t
t
e
e
r
r
p
p
o
o
i
i
n
n
t
t
?
?
O
O
u
u
r
r
c
c
o
o
n
n
v
v
e
e
n
n
t
t
i
i
o
o
n
n
s
s
e
e
t
t
s
s
i
i
t
t
t
t
o
o
p
p
o
o
i
i
n
n
t
t
t
t
o
o
t
t
h
h
e
e
f
f
i
i
r
r
s
s
t
t
l
l
o
o
c
c
a
a
l
l
v
v
a
a
r
r
i
i
a
a
b
b
l
l
e
e
.
.
•
E
E
v
v
e
e
n
n
i
i
f
f
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
h
h
a
a
s
s
n
n
o
o
l
l
o
o
c
c
a
a
l
l
v
v
a
a
r
r
i
i
a
a
b
b
l
l
e
e
s
s
.
.
20
20
E
E
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
S
S
t
t
a
a
c
c
k
k
21
21
•
R
R
e
e
g
g
i
i
s
s
t
t
e
e
r
r
R
R
5
5
s
s
t
t
o
o
r
r
e
e
s
s
F
F
r
r
a
a
m
m
e
e
p
p
o
o
i
i
n
n
t
t
e
e
r
r
,
,
u
u
s
s
e
e
a
a
s
s
i
i
g
g
n
n
e
e
d
d
o
o
f
f
f
f
s
s
e
e
t
t
t
t
o
o
a
a
c
c
c
c
e
e
s
s
s
s
e
e
i
i
t
t
h
h
e
e
r
r
d
d
i
i
r
r
e
e
c
c
t
t
i
i
o
o
n
n
s
s
.
.
•
O
O
n
n
l
l
y
y
n
n
e
e
e
e
d
d
s
s
m
m
a
a
l
l
l
l
o
o
f
f
f
f
s
s
e
e
t
t
s
s
s
s
o
o
6
6
b
b
i
i
t
t
s
s
o
o
f
f
s
s
i
i
g
g
n
n
e
e
d
d
o
o
f
f
f
f
s
s
e
e
t
t
i
i
n
n
L
L
D
D
R
R
/
/
S
S
T
T
R
R
i
i
s
s
e
e
n
n
o
o
u
u
g
g
h
h
.
.
•
L
L
o
o
c
c
a
a
l
l
s
s
a
a
r
r
e
e
a
a
c
c
c
c
e
e
s
s
s
s
e
e
d
d
b
b
y
y
n
n
e
e
g
g
a
a
t
t
i
i
v
v
e
e
o
o
f
f
f
f
s
s
e
e
t
t
s
s
f
f
r
r
o
o
m
m
f
f
r
r
a
a
m
m
e
e
p
p
o
o
i
i
n
n
t
t
e
e
r
r
.
.
•
P
P
a
a
r
r
a
a
m
m
e
e
t
t
e
e
r
r
s
s
a
a
n
n
d
d
r
r
e
e
t
t
u
u
r
r
n
n
v
v
a
a
l
l
u
u
e
e
a
a
r
r
e
e
a
a
c
c
c
c
e
e
s
s
s
s
e
e
d
d
b
b
y
y
p
p
o
o
s
s
i
i
t
t
i
i
v
v
e
e
o
o
f
f
f
f
s
s
e
e
t
t
s
s
.
.
21
21
22
22
F
F
r
r
a
a
m
m
e
e
P
P
o
o
i
i
n
n
t
t
e
e
r
r
•
I
n
t
h
e
p
r
e
v
i
o
u
s
s
o
l
u
t
i
o
n
s
,
t
h
e
c
o
m
p
i
l
e
r
/
a
s
s
e
m
b
l
y
p
r
o
g
r
a
m
m
e
r
a
l
l
o
c
a
t
e
d
p
a
r
a
m
e
t
e
r
s
a
n
d
l
o
c
a
l
s
i
n
f
i
x
e
d
m
e
m
o
r
y
l
o
c
a
t
i
o
n
s
.
•
U
s
i
n
g
a
n
e
x
e
c
u
t
i
o
n
s
t
a
c
k
m
e
a
n
s
p
a
r
a
m
e
t
e
r
s
a
n
d
l
o
c
a
l
s
a
r
e
c
o
n
s
t
a
n
t
l
y
m
o
v
i
n
g
a
r
o
u
n
d
.
•
T
h
e
f
r
a
m
e
p
o
i
n
t
e
r
s
o
l
v
e
s
t
h
i
s
p
r
o
b
l
e
m
b
y
u
s
i
n
g
f
i
x
e
d
o
f
f
s
e
t
s
i
n
s
t
e
a
d
o
f
a
d
d
r
e
s
s
e
s
.
•
T
h
e
a
s
s
e
m
b
l
e
r
c
a
n
g
e
n
e
r
a
t
e
c
o
d
e
u
s
i
n
g
o
f
f
s
e
t
s
,
w
i
t
h
o
u
t
k
n
o
w
i
n
g
w
h
e
r
e
t
h
e
s
t
a
c
k
f
r
a
m
e
w
i
l
l
r
e
s
i
d
e
.
•
F
r
a
m
e
p
o
i
n
t
e
r
n
e
e
d
s
t
o
b
e
s
a
v
e
d
a
n
d
r
e
s
t
o
r
e
d
a
r
o
u
n
d
f
u
n
c
t
i
o
n
c
a
l
l
s
.
H
o
w
a
b
o
u
t
t
h
e
s
t
a
c
k
p
o
i
n
t
e
r
?
22
22
N
N
e
e
s
s
t
t
e
e
d
d
C
C
a
a
l
l
l
l
s
s
b
a
z
(
7
)
b
b
a
a
r
r
(
(
‘
‘
A
A
’
’
)
)
f
f
o
o
o
o
(
(
5
5
,
,
6
6
)
)
m
a
i
n
(
)
•
L
L
o
o
c
c
a
a
l
l
s
s
a
a
r
r
e
e
a
a
c
c
c
c
e
e
s
s
s
s
e
e
d
d
b
b
y
y
n
n
e
e
g
g
a
a
t
t
i
i
v
v
e
e
o
o
f
f
f
f
s
s
e
e
t
t
s
s
f
f
r
r
o
o
m
m
f
f
r
r
a
a
m
m
e
e
p
p
o
o
i
i
n
n
t
t
e
e
r
r
.
.
•
P
P
a
a
r
r
a
a
m
m
e
e
t
t
e
e
r
r
s
s
a
a
n
n
d
d
r
r
e
e
t
t
u
u
r
r
n
n
v
v
a
a
l
l
u
u
e
e
a
a
r
r
e
e
a
a
c
c
c
c
e
e
s
s
s
s
e
e
d
d
b
b
y
y
p
p
o
o
s
s
i
i
t
t
i
i
v
v
e
e
o
o
f
f
f
f
s
s
e
e
t
t
s
s
.
.
•
M
M
o
o
s
s
t
t
o
o
f
f
f
f
s
s
e
e
t
t
s
s
a
a
r
r
e
e
s
s
m
m
a
a
l
l
l
l
,
,
t
t
h
h
i
i
s
s
e
e
x
x
p
p
l
l
a
a
i
i
n
n
s
s
L
L
D
D
R
R
/
/
S
S
T
T
R
R
i
i
m
m
p
p
l
l
e
e
m
m
e
e
n
n
t
t
a
a
t
t
i
i
o
o
n
n
.
.
•
O
O
n
n
e
e
u
u
s
s
e
e
f
f
o
o
r
r
t
t
h
h
e
e
6
6
b
b
i
i
t
t
o
o
f
f
f
f
s
s
e
e
t
t
p
p
o
o
r
r
t
t
i
i
o
o
n
n
o
o
f
f
L
L
D
D
R
R
/
/
S
S
T
T
R
R
•
B
B
a
a
s
s
e
e
r
r
e
e
g
g
i
i
s
s
t
t
e
e
r
r
s
s
t
t
o
o
r
r
e
e
s
s
p
p
o
o
i
i
n
n
t
t
e
e
r
r
,
,
s
s
i
i
g
g
n
n
e
e
d
d
o
o
f
f
f
f
s
s
e
e
t
t
a
a
c
c
c
c
e
e
s
s
s
s
e
e
s
s
b
b
o
o
t
t
h
h
d
d
i
i
r
r
e
e
c
c
t
t
i
i
o
o
n
n
s
s
.
.
F
F
P
P
(
(
b
b
a
a
z
z
)
)
F
F
P
P
(
(
b
b
a
a
r
r
)
)
F
F
P
P
(
(
f
f
o
o
o
o
)
)
24
24
E
E
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
S
S
t
t
a
a
c
c
k
k
Advantages
Advantages
:
:
•
C
C
o
o
d
d
e
e
c
c
a
a
n
n
b
b
e
e
m
m
a
a
r
r
k
k
e
e
d
d
‘
‘
r
r
e
e
a
a
d
d
o
o
n
n
l
l
y
y
’
’
•
C
C
o
o
n
n
c
c
e
e
p
p
t
t
u
u
a
a
l
l
l
l
y
y
e
e
a
a
s
s
y
y
t
t
o
o
u
u
n
n
d
d
e
e
r
r
s
s
t
t
a
a
n
n
d
d
•
S
S
u
u
p
p
p
p
o
o
r
r
t
t
s
s
r
r
e
e
c
c
u
u
r
r
s
s
i
i
o
o
n
n
a
a
n
n
d
d
p
p
a
a
r
r
a
a
l
l
l
l
e
e
l
l
e
e
x
x
e
e
c
c
u
u
t
t
i
i
o
o
n
n
•
N
N
o
o
r
r
e
e
s
s
o
o
u
u
r
r
c
c
e
e
s
s
f
f
o
o
r
r
i
i
n
n
a
a
c
c
t
t
i
i
v
v
e
e
f
f
u
u
n
n
c
c
t
t
i
i
o
o
n
n
s
s
•
G
G
o
o
o
o
d
d
d
d
a
a
t
t
a
a
l
l
o
o
c
c
a
a
l
l
i
i
t
t
y
y
,
,
n
n
o
o
f
f
r
r
a
a
g
g
m
m
e
e
n
n
t
t
i
i
n
n
g
g
•
M
M
i
i
n
n
i
i
m
m
i
i
z
z
e
e
s
s
r
r
e
e
g
g
i
i
s
s
t
t
e
e
r
r
u
u
s
s
a
a
g
g
e
e
Disadvantages:
Disadvantages:
•
M
M
o
o
r
r
e
e
m
m
e
e
m
m
o
o
r
r
y
y
t
t
h
h
a
a
n
n
s
s
t
t
a
a
t
t
i
i
c
c
a
a
l
l
l
l
o
o
c
c
a
a
t
t
i
i
o
o
n
n
24
24
25
25
POP and PUSH
POP and PUSH
: pseudo-instructions that have the following semantics.
: pseudo-instructions that have the following semantics.
•
Not needed but can make working with the stack easier.
Not needed but can make working with the stack easier.
PUSH Rx
PUSH Rx
ADD R6,R6,#-1 ; Decrement SP
ADD R6,R6,#-1 ; Decrement SP
STR Rx,R6,#0 ; Store value
STR Rx,R6,#0 ; Store value
POP Rx
POP Rx
LDR Rx,R6,#0 ; Load value
LDR Rx,R6,#0 ; Load value
ADD R6,R6,#1 ; Increment SP
ADD R6,R6,#1 ; Increment SP
25
25
P
P
O
O
P
P
a
a
n
n
d
d
P
P
U
U
S
S
H
H
S
S
u
u
m
m
m
m
a
a
r
r
y
y
o
o
f
f
L
L
C
C
-
-
3
3
F
F
u
u
n
n
c
c
t
t
i
i
o
o
n
n
C
C
a
a
l
l
l
l
I
I
m
m
p
p
l
l
e
e
m
m
e
e
n
n
t
t
a
a
t
t
i
i
o
o
n
n
1.
Caller
Caller
pushes arguments (last to first).
pushes arguments (last to first).
2.
Caller
Caller
invokes subroutine (JSR).
invokes subroutine (JSR).
3.
Callee
Callee
allocates return value, pushes R7 and R5.
allocates return value, pushes R7 and R5.
4.
Callee
Callee
sets up new R5; allocates space for local variables.
sets up new R5; allocates space for local variables.
5.
Callee
Callee
executes function code.
executes function code.
6.
Callee
Callee
stores result into return value slot.
stores result into return value slot.
7.
Callee
Callee
pops local vars, pops R5, pops R7.
pops local vars, pops R5, pops R7.
8.
Callee
Callee
returns (JMP R7).
returns (JMP R7).
9.
Caller
Caller
loads return value and pops arguments.
loads return value and pops arguments.
10.
Caller
Caller
resumes computation
resumes computation
28
28
D
D
e
e
t
t
a
a
i
i
l
l
e
e
d
d
E
E
x
x
a
a
m
m
p
p
l
l
e
e
–
–
C
C
s
s
t
t
a
a
r
r
t
t
e
e
r
r
c
c
o
o
d
d
e
e
int
int
A = 5;
A = 5;
int
int
B = 20;
B = 20;
int
int
C;
C;
int
main(){ main(){C = FOO(A, B);
C = FOO(A, B);
}
}
int
int
FOO(int x, int y){FOO(int x, int y){int
int
temp;
temp;
temp = x + y;
temp = x + y;
return temp;
return temp;
}
}
28
28
29
29
D
D
e
e
t
t
a
a
i
i
l
l
e
e
d
d
E
E
x
x
a
a
m
m
p
p
l
l
e
e
Main program to illustrate stack convention:
Main program to illustrate stack convention:
.ORIG x3000
.ORIG x3000
MAIN LD R6,STACK ; init stack pointer
MAIN LD R6,STACK ; init stack pointer
LD R0, B
LD R0, B
; load second operand
; load second operand
PUSH R0 ; PUSH second operand
PUSH R0 ; PUSH second operand
LD R1, A
LD R1, A
; load first operand
; load first operand
PUSH R1 ; PUSH first operand
PUSH R1 ; PUSH first operand
JSR FOO
JSR FOO
; call function
; call function
LDR R0,R6,#0 ; POP return value
LDR R0,R6,#0 ; POP return value
ADD R6,R6,#3 ; unwind stack
ADD R6,R6,#3 ; unwind stack
ST R0, C
ST R0, C
; store result
; store result
HALT
HALT
29
29
1.
Caller
Caller
pushes arguments (last to first).
pushes arguments (last to first).
2.
Caller
Caller
invokes subroutine (JSR).
invokes subroutine (JSR).
30
30
D
D
e
e
t
t
a
a
i
i
l
l
e
e
d
d
E
E
x
x
a
a
m
m
p
p
l
l
e
e
S
S
P
P
S
S
t
t
a
a
c
c
k
k
b
b
e
e
f
f
o
o
r
r
e
e
J
J
S
S
R
R
i
i
n
n
s
s
t
t
r
r
u
u
c
c
t
t
i
i
o
o
n
n
30
30
31
31
D
D
e
e
t
t
a
a
i
i
l
l
e
e
d
d
E
E
x
x
a
a
m
m
p
p
l
l
e
e
•
Function code to illustrate stack convention:
FOO
ADD R6,R6,#-1 ; alloc return value
ADD R6,R6,#-1 ; alloc return value
PUSH R7 ; PUSH return address
PUSH R7 ; PUSH return address
PUSH R5 ; PUSH frame pointer
PUSH R5 ; PUSH frame pointer
ADD R5,R6,#-1 ; FP = SP-1
ADD R5,R6,#-1 ; FP = SP-1
ADD R6,R6,#-1 ; alloc local variable
ADD R6,R6,#-1 ; alloc local variable
LDR R2,R5,#4 ; load first operand / A
LDR R2,R5,#4 ; load first operand / A
LDR R3,R5,#5 ; load second operand / B
LDR R3,R5,#5 ; load second operand / B
ADD R4,R3,R2 ; add operands
ADD R4,R3,R2 ; add operands
STR R4,R5,#0 ; store local variable
STR R4,R5,#0 ; store local variable
31
31
1.
Caller
Caller
pushes arguments (last to first).
pushes arguments (last to first).
2.
Caller
Caller
invokes subroutine (JSR).
invokes subroutine (JSR).
3.
Callee
Callee
allocates return value, pushes R7
allocates return value, pushes R7
and R5.
and R5.
4.
Callee
Callee
sets up new R5; allocates space for
sets up new R5; allocates space for
local variables.
local variables.
5.
Callee
Callee
executes function code.
executes function code.
6.
Callee
Callee
stores result into return value slot.
stores result into return value slot.
7.
Callee
Callee
pops local vars, pops R5, pops R7.
pops local vars, pops R5, pops R7.
8.
Callee
Callee
returns (JMP R7).
returns (JMP R7).
9.
Caller
Caller
loads return value and pops
loads return value and pops
arguments.
arguments.
10.
Caller
Caller
resumes computation
resumes computation
32
32
D
D
e
e
t
t
a
a
i
i
l
l
e
e
d
d
E
E
x
x
a
a
m
m
p
p
l
l
e
e
F
F
P
P
S
S
t
t
a
a
c
c
k
k
d
d
u
u
r
r
i
i
n
n
g
g
b
b
o
o
d
d
y
y
o
o
f
f
F
F
U
U
N
N
C
C
T
T
I
I
O
O
N
N
FP[0]
FP[1]
FP[2]
FP[3]
FP[4]
FP[5]
32
32
33
33
D
D
e
e
t
t
a
a
i
i
l
l
e
e
d
d
E
E
x
x
a
a
m
m
p
p
l
l
e
e
Function code to illustrate stack convention:
Function code to illustrate stack convention:
FOO ; stack exit code
FOO ; stack exit code
STR R4,R5,#3 ; store return value
STR R4,R5,#3 ; store return value
ADD R6,R5,#1 ; SP = FP+1
ADD R6,R5,#1 ; SP = FP+1
POP R5 ; POP frame pointer
POP R5 ; POP frame pointer
POP R7 ; POP return address
POP R7 ; POP return address
RET ; return
RET ; return
A
A
.FILL #5
.FILL #5
; first operand
; first operand
B
B
.FILL #20
.FILL #20
; second operand
; second operand
C
C
.BLKW 1
.BLKW 1
; result
; result
STACK .FILL x4000
STACK .FILL x4000
; stack address
; stack address
33
33
1.
Caller
Caller
pushes arguments (last to first).
pushes arguments (last to first).
2.
Caller
Caller
invokes subroutine (JSR).
invokes subroutine (JSR).
3.
Callee
Callee
allocates return value, pushes R7
allocates return value, pushes R7
and R5.
and R5.
4.
Callee
Callee
sets up new R5; allocates space for
sets up new R5; allocates space for
local variables.
local variables.
5.
Callee
Callee
executes function code.
executes function code.
6.
Callee
Callee
stores result into return value slot.
stores result into return value slot.
7.
Callee
Callee
pops local vars, pops R5, pops R7.
pops local vars, pops R5, pops R7.
8.
Callee
Callee
returns (JMP R7).
returns (JMP R7).
9.
Caller
Caller
loads return value and pops
loads return value and pops
arguments.
arguments.
10.
Caller
Caller
resumes computation
resumes computation
34
34
R
R
1
1
5
5
a
a
n
n
d
d
P
P
7
7
R15
R15
•
Walks you through writing a recursive function in LC3 assembly. Very useful for P7
Walks you through writing a recursive function in LC3 assembly. Very useful for P7
P7
P7
•
Given a recursive function in C, implement the same function in assembly code,
Given a recursive function in C, implement the same function in assembly code,
managing memory using the stack model.
managing memory using the stack model.
34
34
S
S
u
u
m
m
m
m
a
a
r
r
y
y
o
o
f
f
L
L
C
C
-
-
3
3
F
F
u
u
n
n
c
c
t
t
i
i
o
o
n
n
C
C
a
a
l
l
l
l
I
I
m
m
p
p
l
l
e
e
m
m
e
e
n
n
t
t
a
a
t
t
i
i
o
o
n
n
1.
Caller
Caller
pushes arguments (last to first).
pushes arguments (last to first).
2.
Caller
Caller
invokes subroutine (JSR).
invokes subroutine (JSR).
3.
Callee
Callee
allocates return value, pushes R7 and R5.
allocates return value, pushes R7 and R5.
4.
Callee
Callee
sets up new R5; allocates space for local variables.
sets up new R5; allocates space for local variables.
5.
Callee
Callee
executes function code.
executes function code.
6.
Callee
Callee
stores result into return value slot.
stores result into return value slot.
7.
Callee
Callee
pops local vars, pops R5, pops R7.
pops local vars, pops R5, pops R7.
8.
Callee
Callee
returns (JMP R7).
returns (JMP R7).
9.
Caller
Caller
loads return value and pops arguments.
loads return value and pops arguments.
10.
Caller
Caller
resumes computation
resumes computation
Understanding memory allocation is crucial for efficient program execution. This content delves into the importance of memory allocation, considerations for storing data during program execution, and the requirements for allocating memory efficiently. It also explores solutions for managing memory storage within programs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Chapter 10 Memory Model for Program Execution Original slides by Chris Wilcox, Modified by Phil Sharp Colorado State University 1
How do we allocate memory during the execution of a program? Programs need memory for code and data Instructions, global, local, and dynamically allocated variables, etc. Modern programming practices encourage many (reusable) functions, callable from anywhere. Function may be called multiple times before first call returns Some memory can be statically allocated, since the size and type is known at compile time. (global variables) Some memory must be allocated dynamically, size and type is unknown at compile time. (dynamically allocated memory, i.e. malloc) 2 2
Why is memory allocation important? To do useful work all programs must be able to store data. There are not enough registers to store everything that is required in a register. Passing stucts by value Dynamic (heap) allocation is slower that static allocation so not ideal for all memory storage. Static allocation of memory resources is inflexible and can be inefficient. 3 3
What do we care about? Fast program execution Efficient memory usage Avoid memory fragmentation Maintain data locality Allow recursive calls Support parallel execution Minimize resource allocation Memory shouldn t be allocated for functions that are not executed. 4
Consider the following code: int i = 10; int main(){ int a = 5; int b = 20; int c = foo(a, b); } int foo(int x, int y){ int z; z = x + y; return z; } What needs to be stored? Code, parameters, locals, globals, return values 5 5
Storage Requirements Code must be stored in memory so that we can execute the function. The return address must be stored so that control can be returned to the caller. Parameters must be sent from the caller to the callee Return values must be sent from the callee to the caller Local variables for the function must be stored somewhere, is one copy enough? 6 6
Possible Solution: Mixed Code and Data Function implementation: foo BR foo_begin ; skip over save locations foo_rv .BLKW 1 ; return value foo_ra .BLKW 1 ; return address foo_paramx .BLKW 1 ; x parameter foo_paramy .BLKW 1 ; y parameter foo_localz .BLKW 1 ; z local foo_begin ST R7, foo_ra ; save return LD R7, foo_ra ; restore return RET Construct data section by appending foo_ 7 7
Possible Solution: Mixed Code and Data Calling sequence ST R1, foo_paramx ; R1 has x ST R2, foo_paramy ; R2 has y JSR foo ; Function call LD R3, foo_rv ; R3 = return value Code generation is relatively simple. Few instructions are spent moving data. 8 8
Possible Solution: Mixed Code and Data Advantages: Code and data are close together Conceptually easy to understand Minimizes register usage for variables Data persists through life of program Disadvantages: Cannot handle recursion or parallel execution Code is vulnerable to self-modification Consumes resource for inactive functions 9 9
Possible Solution: Separate Code and Data Data Storage: foo_rv .BLKW 1 ; foo return value foo_ra .BLKW 1 ; foo return address foo_paramx .BLKW 1 ; foo x parameter foo_paramy .BLKW 1 ; foo y parameter foo_localz .BLKW 1 ; foo z local bar_rv .BLKW 1 ; bar return value bar_ra .BLKW 1 ; bar return address bar_paramw .BLKW 1 ; bar w parameter ;memory location x4000 Code for foo() and bar() are somewhere else say x3000 Function call code is similar to mixed solution Why might this not be the case 10 10
Possible Solution: Separate Code and Data Advantages: Code can be marked read only - Because code is separated from data in memory Conceptually easy to understand Early Fortran used this scheme Data persists through life of program Disadvantages: Cannot handle recursion or parallel execution Consumes resource for inactive functions
Real Solution: Execution Stack Instructions are stored in code segment Global data is stored in data segment Statically allocated memory uses stack Dynamically allocated memory uses heap Code segment is write protected Program can t modify itself Data segment for initialized and uninitialized globals Heap can be fragmented Stack size is usually limited Stack can grow either direction (usual convention is down) Code Data Heap Stack 12 12
Stacks A LIFO (last-in first-out) Abstract Data Type. The first thing you put in is the last thing you take out. The last thing you put in is the first thing you take out. Abstract Data Type (ADT): A data type that is defied by its behavior. The user of the ADT does not need to know how the behavior is achieved. Other examples: Lists, Queues, Heaps, Sets, Maps, etc. Two main operations: PUSH: add an item to the stack POP: remove an item from the stack Stacks are used in many areas of Computer Science ex. Compilers, Graph/Tree traversals, PDA
A Physical Stack Coin rest in the arm of an automobile 1995 1996 1998 1982 1995 1998 1982 1995 Initial State After After Three More Pushes After One Pop One Push First quarter out is the last quarter in.
A Software Implementation Data items don't move in memory, just our idea about there the TOP of the stack is. TOP / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / #18 / / / / / / #12 #5 #31 #18 / / / / / / #12 #5 #31 #18 / / / / / / TOP TOP TOP R6 R6 R6 R6 x4000 x3FFF x3FFC x3FFE Initial State After After Three More Pushes After One Push Two Pops By convention, R6 holds the Top of Stack (TOS) pointer.
How does the Execution Stack work? First In, Last Out (FILO) data structure PUSH adds data, POP removes data Stack grows and shrinks as data is added and removed Stack grows downward in memory Function calls allocate space on the stack for a stack frame (push) Activation record is another word for stack frame Returning from a function cleans up by removing (popping) the stack frame Done simply by changing the value in R6 Nested function calls push on stack frame of called function By looking at the entire stack in memory it is possible to see the history of function calls that lead to the current function Useful for debugging Stack trace 16 16
Execution / Run Time Stack Each rectangle corresponds to one stack frame, which is the stack space allocated to a particular invocation of a function main() calls foo(5,6) foo() calls bar( A ) bar() calls baz(7) baz() calls baz(6) baz(6) baz(7) bar( A ) foo(5,6) main() 17 17
What has to happen in a function call Caller passes arguments to Callee Caller invokes subroutine (JSR). Callee allocates space for return value. Callee executes function code. Callee stores result into return value space. Callee returns (JMP R7). Caller loads return value. Parameters, return value, return address, and locals are stored on the stack. 18 18
Stack Frame / Activation Record A stack frame or activation record holds the memory required for a function call: Stack frame below this frame contains the function that called this function. Locals Stack frame above this frame contains the functions called from this function. Return Address Caller pushes parameters. Return Value Callee allocates space for the return value, saves the return address, allocates/frees local variables, and stores the return value. Parameters 19 19
Stack Pointers We will need a variable to store the stack pointer (SP), LC3 assembly uses R6. Stack execution is ubiquitous, so hardware can have a special register to hold the stack pointer, sometimes even specific instructions. Problem: stack pointer is difficult to use to access data, since it moves around constantly. Solution: allocate another variable called a frame pointer (FP), for stack frame, uses R5. Frame pointer points to the same location for duration of the function Where should frame pointer point? Our convention sets it to point to the first local variable. Even if function has no local variables. 20 20
Execution Stack Register R5 stores Frame pointer, use a signed offset to access Locals either directions. Return Address Only need small offsets so 6 bits of signed offset in LDR/STR is Frame Pointer enough. Return Value Locals are accessed by negative offsets from frame pointer. Parameters Parameters and return value are accessed by positive offsets. 21 21
Frame Pointer In the previous solutions, the compiler/assembly programmer allocated parameters and locals in fixed memory locations. Using an execution stack means parameters and locals are constantly moving around. The frame pointer solves this problem by using fixed offsets instead of addresses. The assembler can generate code using offsets, without knowing where the stack frame will reside. Frame pointer needs to be saved and restored around function calls. How about the stack pointer? 22 22
Nested Calls Locals are accessed by negative offsets from frame pointer. Parameters and return value are accessed by positive offsets. baz(7) bar( A ) foo(5,6) main() Most offsets are small, this explains LDR/STR implementation. One use for the 6 bit offset portion of LDR/STR Base register stores pointer, signed offset accesses both FP(baz) baz(7) directions. FP(bar) bar( A ) foo(5,6) FP(foo) main()
Execution Stack Advantages: Code can be marked read only Conceptually easy to understand Supports recursion and parallel execution No resources for inactive functions Good data locality, no fragmenting Minimizes register usage Disadvantages: More memory than static allocation 24 24
POP and PUSH POP and PUSH: pseudo-instructions that have the following semantics. Not needed but can make working with the stack easier. PUSH Rx ADD R6,R6,#-1 ; Decrement SP STR Rx,R6,#0 ; Store value POP Rx LDR Rx,R6,#0 ; Load value ADD R6,R6,#1 ; Increment SP 25 25
Summary of LC-3 Function Call Implementation 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Caller resumes computation Caller pushes arguments (last to first). Caller invokes subroutine (JSR). Callee allocates return value, pushes R7 and R5. Callee sets up new R5; allocates space for local variables. Callee executes function code. Callee stores result into return value slot. Callee pops local vars, pops R5, pops R7. Callee returns (JMP R7). Caller loads return value and pops arguments.
Detailed Example C starter code int A = 5; int B = 20; int C; int main(){ C = FOO(A, B); } int FOO(int x, int y){ int temp; temp = x + y; return temp; } 28 28
Detailed Example Main program to illustrate stack convention: 1. Caller pushes arguments (last to first). 2. Caller invokes subroutine (JSR). .ORIG x3000 MAIN LD R6,STACK ; init stack pointer LD R0, B ; load second operand PUSH R0 ; PUSH second operand LD R1, A ; load first operand PUSH R1 ; PUSH first operand JSR FOO LDR R0,R6,#0 ; POP return value ADD R6,R6,#3 ; unwind stack ST R0, C ; store result HALT ; call function 29 29
Detailed Example SP A B Stack before JSR instruction 30 30
Detailed Example Function code to illustrate stack convention: 1. Caller pushes arguments (last to first). FOO 2. Caller invokes subroutine (JSR). ADD R6,R6,#-1 ; alloc return value PUSH R7 ; PUSH return address PUSH R5 ; PUSH frame pointer ADD R5,R6,#-1 ; FP = SP-1 3. Callee allocates return value, pushes R7 and R5. 4. Callee sets up new R5; allocates space for local variables. 5. Callee executes function code. ADD R6,R6,#-1 ; alloc local variable LDR R2,R5,#4 ; load first operand / A LDR R3,R5,#5 ; load second operand / B ADD R4,R3,R2 ; add operands STR R4,R5,#0 ; store local variable 6. Callee stores result into return value slot. 7. Callee pops local vars, pops R5, pops R7. 8. Callee returns (JMP R7). 9. Caller loads return value and pops arguments. 10.Caller resumes computation 31 31
Detailed Example FP[0] FP[1] FP[2] FP[3] FP[4] FP[5] Local Variable / temp FP Frame Pointer Return Address Return Value First Operand / A Second Operand / B Stack during body of FUNCTION 32 32
Detailed Example Function code to illustrate stack convention: 1. Caller pushes arguments (last to first). 2. Caller invokes subroutine (JSR). FOO ; stack exit code STR R4,R5,#3 ; store return value ADD R6,R5,#1 ; SP = FP+1 POP R5 ; POP frame pointer POP R7 ; POP return address RET ; return 3. Callee allocates return value, pushes R7 and R5. 4. Callee sets up new R5; allocates space for local variables. 5. Callee executes function code. 6. Callee stores result into return value slot. 7. Callee pops local vars, pops R5, pops R7. A B C STACK .FILL x4000 ; stack address .FILL #5 .FILL #20 .BLKW 1 ; first operand ; second operand ; result 8. Callee returns (JMP R7). 9. Caller loads return value and pops arguments. 10.Caller resumes computation 33 33
R15 and P7 R15 Walks you through writing a recursive function in LC3 assembly. Very useful for P7 P7 Given a recursive function in C, implement the same function in assembly code, managing memory using the stack model. 34 34
Summary of LC-3 Function Call Implementation 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Caller resumes computation Caller pushes arguments (last to first). Caller invokes subroutine (JSR). Callee allocates return value, pushes R7 and R5. Callee sets up new R5; allocates space for local variables. Callee executes function code. Callee stores result into return value slot. Callee pops local vars, pops R5, pops R7. Callee returns (JMP R7). Caller loads return value and pops arguments.
