Procedure Execution in Programming
Week 7
Where is all the knowledge we lost with
information?
T. S. Eliot
Procedures
1
-
M
A
L
P
r
o
c
e
d
u
r
e
C
a
l
l
&
R
e
t
u
r
n
M
e
c
h
a
n
i
s
m
s
2
-
D
y
n
a
m
i
c
S
t
o
r
a
g
e
A
l
l
o
c
a
t
i
o
n
3
-
A
c
t
i
v
a
t
i
o
n
R
e
c
o
r
d
s
4
-
P
a
r
a
m
e
t
e
r
P
a
s
s
i
n
g
5
-
S
a
v
i
n
g
R
e
g
i
s
t
e
r
s
6
-
M
I
P
S
R
e
g
i
s
t
e
r
U
s
a
g
e
7
-
S
a
m
p
l
e
M
A
L
P
r
o
g
r
a
m
t
h
a
t
u
s
e
s
P
r
o
c
e
d
u
r
e
s
W
h
y
U
s
e
P
r
o
c
e
d
u
r
e
s
?
•
Code is easier to understand.
•
Easier to develop and maintain.
•
Different programmers can write
different parts of the program
•
Code becomes modular
W
h
y
P
r
o
c
e
d
u
r
e
s
C
o
n
t
.
•
Allows reduction in size of program in
exchange for somewhat reduced
performance (overhead of Call, Return,
and certain associated overhead)
H
L
L
C
o
m
p
i
l
e
r
s
.
.
•
g
e
n
e
r
a
t
e
a
s
s
e
m
b
l
y
l
a
n
g
u
a
g
e
•
i
n
s
t
r
u
c
t
i
o
n
s
t
o
i
m
p
l
e
m
e
n
t
–
c
a
l
l
i
n
g
t
h
e
p
r
o
c
e
d
u
r
e
–
r
e
t
u
r
n
i
n
g
f
r
o
m
t
h
e
p
r
o
c
e
d
u
r
e
–
p
a
s
s
i
n
g
p
a
r
a
m
e
t
e
r
s
t
o
t
h
e
p
r
o
c
e
d
u
r
e
–
r
e
t
u
r
n
i
n
g
p
a
r
a
m
e
t
e
r
s
f
r
o
m
t
h
e
p
r
o
c
e
d
u
r
e
M
A
L
P
r
o
c
e
d
u
r
e
C
a
l
l
&
R
e
t
u
r
n
M
e
c
h
a
n
i
s
m
1
-
S
a
v
e
t
h
e
r
e
t
u
r
n
a
d
d
r
e
s
s
2
-
C
a
l
l
t
h
e
p
r
o
c
e
d
u
r
e
3
-
E
x
e
c
u
t
e
t
h
e
p
r
o
c
e
d
u
r
e
4
-
R
e
t
u
r
n
t
o
c
a
l
l
i
n
g
p
r
o
g
r
a
m
R
e
a
l
i
t
y
-
P
r
o
c
e
d
u
r
e
E
x
e
c
u
t
i
o
n
S
t
e
p
s
1
.
S
a
v
e
p
a
r
a
m
e
t
e
r
s
.
W
h
e
r
e
?
–
I
n
r
e
g
i
s
t
e
r
s
(
f
a
s
t
)
o
r
i
n
m
e
m
o
r
y
(
s
l
o
w
)
2
.
S
a
v
e
r
e
t
u
r
n
a
d
d
r
e
s
s
.
W
h
e
r
e
?
–
I
n
r
e
g
i
s
t
e
r
s
(
f
a
s
t
)
o
r
i
n
m
e
m
o
r
y
(
s
l
o
w
)
3
.
C
a
l
l
p
r
o
c
e
d
u
r
e
.
H
o
w
?
–
n
e
w
j
u
m
p
i
n
s
t
r
u
c
t
i
o
n
P
r
o
c
e
d
u
r
e
E
x
e
c
u
t
i
o
n
S
t
e
p
s
C
o
n
t
.
4
.
A
l
l
o
c
a
t
e
s
p
a
c
e
t
o
s
t
o
r
e
p
r
o
c
e
d
u
r
e
’
s
v
a
r
i
a
b
l
e
s
(
l
o
c
a
l
v
a
r
i
a
b
l
e
s
)
.
W
h
y
?
–
V
a
r
i
a
b
l
e
s
a
r
e
u
s
e
d
t
e
m
p
o
r
a
r
i
l
y
,
s
p
a
c
e
c
a
n
b
e
r
e
c
l
a
i
m
e
d
u
p
o
n
r
e
t
u
r
n
.
–
F
o
r
r
e
c
u
r
s
i
v
e
p
r
o
c
e
d
u
r
e
c
a
l
l
,
m
u
s
t
h
a
v
e
m
u
l
t
i
p
l
e
c
o
p
i
e
s
o
f
l
o
c
a
l
v
a
r
i
a
b
l
e
s
,
o
n
e
f
o
r
e
a
c
h
r
e
c
u
r
s
i
o
n
.
H
o
w
?
–
u
s
i
n
g
a
s
p
e
c
i
a
l
s
t
a
c
k
,
t
h
e
“
s
y
s
t
e
m
s
t
a
c
k
”
P
r
o
c
e
d
u
r
e
E
x
e
c
u
t
i
o
n
S
t
e
p
s
C
o
n
t
.
5
.
E
x
e
c
u
t
e
p
r
o
c
e
d
u
r
e
6
.
D
e
a
l
l
o
c
a
t
e
l
o
c
a
l
v
a
r
i
a
b
l
e
s
.
H
o
w
?
–
P
o
p
t
h
e
m
o
f
f
t
h
e
s
y
s
t
e
m
s
t
a
c
k
7
.
S
a
v
e
r
e
t
u
r
n
v
a
l
u
e
s
,
i
f
a
n
y
.
W
h
e
r
e
?
–
I
n
r
e
g
i
s
t
e
r
s
(
f
a
s
t
)
o
r
i
n
m
e
m
o
r
y
(
s
l
o
w
)
8
.
G
e
t
r
e
t
u
r
n
a
d
d
r
e
s
s
9
.
R
e
t
u
r
n
.
H
o
w
?
–
n
e
w
j
u
m
p
i
n
s
t
r
u
c
t
i
o
n
P
r
o
c
e
d
u
r
e
C
a
l
l
•
M
A
L
h
a
s
a
s
p
e
c
i
a
l
j
u
m
p
i
n
s
t
r
u
c
t
i
o
n
f
o
r
p
r
o
c
e
d
u
r
e
c
a
l
l
s
,
J
u
m
p
a
n
d
L
i
n
k
(
j
a
l
)
•
Instruction’s assembly format:
–
j
a
l
p
r
o
c
_
l
a
b
e
l
•
Instruction’s action:
–
p
r
o
g
r
a
m
j
u
m
p
s
t
o
t
h
e
a
d
d
r
e
s
s
r
e
p
r
e
s
e
n
t
e
d
b
y
p
r
o
c
_
l
a
b
e
l
–
r
e
t
u
r
n
a
d
d
r
e
s
s
(
a
d
d
r
e
s
s
o
f
i
n
s
t
r
u
c
t
i
o
n
a
f
t
e
r
j
a
l
)
i
s
s
a
v
e
d
i
n
$
3
1
,
c
a
l
l
e
d
t
h
e
“
l
i
n
k
r
e
g
i
s
t
e
r
”
b
e
c
a
u
s
e
i
t
l
i
n
k
s
t
h
e
p
r
o
c
e
d
u
r
e
b
a
c
k
t
o
t
h
e
r
e
t
u
r
n
l
o
c
a
t
i
o
n
.
P
r
o
c
e
d
u
r
e
R
e
t
u
r
n
•
A
n
e
w
i
n
s
t
r
u
c
t
i
o
n
J
u
m
p
R
e
g
i
s
t
e
r
(
j
r
)
i
s
u
s
e
d
f
o
r
r
e
t
u
r
n
i
n
g
f
r
o
m
a
p
r
o
c
e
d
u
r
e
•
Instruction’s assembly format:
–
j
r
$
x
•
Instruction’s action:
–
program jumps to the address contained in
register x.
•
T
o
g
e
t
h
e
r
j
a
l
a
n
d
j
r
a
l
l
o
w
f
o
r
s
i
m
p
l
e
a
n
d
f
a
s
t
s
u
b
r
o
u
t
i
n
e
c
a
l
l
s
/
r
e
t
u
r
n
s
:
M
A
L
P
r
o
c
e
d
u
r
e
C
a
l
l
S
u
m
m
a
r
y
j
a
l
p
r
o
c
1
n
e
x
t
_
i
n
s
t
r
u
c
t
i
o
n
:
.
.
.
.
.
.
d
o
n
e
p
r
o
c
1
:
.
.
.
.
.
.
j
r
$
3
1
next_instruction
M
I
P
S
J
u
m
p
I
n
s
t
r
u
c
t
i
o
n
s
•
j
j
u
m
p
t
o
a
l
a
b
e
l
(
s
i
m
i
l
a
r
t
o
b
r
a
n
c
h
)
–
A
b
s
o
l
u
t
e
a
d
d
r
e
s
s
•
j
a
l
j
u
m
p
a
n
d
l
i
n
k
–
j
u
m
p
s
t
o
a
p
r
o
c
e
d
u
r
e
–
s
a
v
e
s
t
h
e
r
e
t
u
r
n
a
d
d
r
e
s
s
i
n
$
3
1
•
j
r
R
j
u
m
p
r
e
g
i
s
t
e
r
–
j
u
m
p
s
t
o
t
h
e
l
o
c
a
t
i
o
n
–
p
o
i
n
t
e
d
t
o
b
y
r
e
g
i
s
t
e
r
R
P
r
o
c
e
d
u
r
e
C
a
l
l
a
n
d
R
e
t
u
r
n
•
j
a
l
l
a
b
e
l
1
–
#
J
u
m
p
a
n
d
L
i
n
k
–
j
u
m
p
s
t
o
t
h
e
i
n
s
t
r
u
c
t
i
o
n
a
t
l
a
b
e
l
1
–
s
a
v
e
s
t
h
e
r
e
t
u
r
n
a
d
d
r
e
s
s
i
n
$
3
1
•
j
r
$
3
1
–
#
J
u
m
p
R
e
g
i
s
t
e
r
–
c
o
p
i
e
s
v
a
l
u
e
i
n
r
e
g
i
s
t
e
r
$
3
1
t
o
t
h
e
P
C
N
e
s
t
e
d
P
r
o
c
e
d
u
r
e
C
a
l
l
s
•
We have a problem: when procedure
A
calls
another procedure
B
(a “nested procedure
call”) the contents of $31 are overwritten and
the return address for
A
is lost:
N
e
s
t
e
d
P
r
o
c
e
d
u
r
e
C
a
l
l
s
C
o
n
t
.
•
Solution: transfer the return address to
another register
–
In A, before call to B:
move $16,$31
# save return address in reg 16
–
To return from A:
jr $16
# return address is in reg 16
•
This has limitations:
–
Limited by number of nested procedures
–
Programmer must keep return addresses
straight
D
y
n
a
m
i
c
S
t
o
r
a
g
e
A
l
l
o
c
a
t
i
o
n
•
r
e
t
u
r
n
a
d
d
r
e
s
s
i
n
r
e
g
i
s
t
e
r
$
r
a
(
$
3
1
)
•
m
u
s
t
s
a
v
e
t
h
i
s
r
e
t
u
r
n
a
d
d
r
e
s
s
f
o
r
–
n
e
s
t
e
d
p
r
o
c
e
d
u
r
e
c
a
l
l
s
–
r
e
c
u
r
s
i
v
e
p
r
o
c
e
d
u
r
e
c
a
l
l
s
R
e
c
u
r
s
i
v
e
P
r
o
c
e
d
u
r
e
C
a
l
l
s
•
It is possible for a procedure to conditionally
call itself, a “recursive procedure call”.
–
T
h
e
n
u
m
b
e
r
o
r
r
e
c
u
r
s
i
v
e
c
a
l
l
s
c
a
n
b
e
i
n
d
e
f
i
n
i
t
e
–
C
a
n
n
o
t
s
a
v
e
r
e
t
u
r
n
a
d
d
r
e
s
s
i
n
r
e
g
i
s
t
e
r
s
•
Solution: save return addresses on the
“system stack”
–
W
a
n
t
a
s
t
a
c
k
,
b
e
c
a
u
s
e
a
d
d
r
e
s
s
e
s
a
r
e
n
e
e
d
e
d
i
n
t
h
e
r
e
v
e
r
s
e
o
r
d
e
r
t
h
e
y
a
r
e
p
r
o
d
u
c
e
d
.
•
A register ($29) is designated as the system
stack pointer
M
I
P
S
S
y
s
t
e
m
S
t
a
c
k
•
s
t
a
c
k
p
o
i
n
t
e
r
$
s
p
(
$
2
9
)
•
b
a
s
e
o
f
s
t
a
c
k
a
t
h
i
g
h
m
e
m
o
r
y
•
s
t
a
c
k
g
r
o
w
s
d
o
w
n
(
t
o
w
a
r
d
s
m
a
l
l
e
r
a
d
d
r
e
s
s
e
s
)
•
$
s
p
p
o
i
n
t
s
t
o
f
i
r
s
t
e
m
p
t
y
l
o
c
a
t
i
o
n
a
t
t
h
e
t
o
p
o
f
t
h
e
s
t
a
c
k
P
u
s
h
s
w
$
8
,
0
(
$
s
p
)
a
d
d
i
$
s
p
,
$
s
p
,
-
4
o
r
a
d
d
i
$
s
p
,
$
s
p
,
-
4
s
w
$
8
,
4
(
$
s
p
)
S
t
a
c
k
i
n
g
t
h
e
R
e
t
u
r
n
A
d
d
r
e
s
s
•
T
h
e
s
y
s
t
e
m
s
t
a
c
k
g
r
o
w
s
f
r
o
m
h
i
g
h
-
n
u
m
b
e
r
e
d
m
e
m
o
r
y
t
o
w
a
r
d
l
o
w
-
n
u
m
b
e
r
e
d
m
e
m
o
r
y
Proc1:
addi $sp, $sp, -4
# make room on stack for return addr.
sw $ra, 4($sp)
# save return address to the stack
...
beq $8, $9, exit
# test some condition
jal Proc1
# recursive call
...
exit:
lw $10, 4($sp)
# restore return address from the stack
addi $sp, $sp, 4
# deallocate the stack space
jr $10
# return to the calling routine
P
o
p
a
d
d
i
$
s
p
,
$
s
p
,
4
l
w
$
8
,
0
(
$
s
p
)
o
r
l
w
$
8
,
4
(
$
s
p
)
a
d
d
i
$
s
p
,
$
s
p
,
4
A
c
t
i
v
a
t
i
o
n
R
e
c
o
r
d
s
-
C
o
n
c
e
p
t
•
When a procedure is invoked
–
old environment must be saved.
–
new environment is created
•
When the procedure terminates this new
environment disappears and the old
environment must be restored.
•
An activation record consists of all the
information that corresponds to the state
of a procedure.
S
a
v
i
n
g
a
n
d
R
e
s
t
o
r
i
n
g
•
Activation Record (or Stack Frame) is
pushed onto the stack just like a word.
–
Can consist of multiple words
–
Varies in size.
•
Stack pointer ($29) must be adjusted by
this size
–
After pushing
–
After popping.
P
u
s
h
i
n
g
o
n
e
a
t
a
t
i
m
e
s
w
$
8
,
0
(
$
s
p
)
a
d
d
$
s
p
,
$
s
p
,
-
4
s
w
$
1
2
,
0
(
$
s
p
)
a
d
d
$
s
p
,
$
s
p
,
-
4
s
w
$
6
,
0
(
$
s
p
)
a
d
d
$
s
p
,
$
s
p
,
-
4
j
a
l
p
r
o
c
.
.
.
p
r
o
c
:
s
w
$
3
1
,
0
(
$
s
p
)
a
d
d
$
s
p
,
$
s
p
,
-
4
P
u
s
h
A
c
t
i
v
a
t
i
o
n
R
e
c
o
r
d
t
h
e
n
I
n
c
r
e
m
e
n
t
s
p
s
w
$
8
,
0
(
$
s
p
)
s
w
$
1
2
,
-
4
(
$
s
p
)
s
w
$
6
,
-
8
(
$
s
p
)
j
a
l
p
r
o
c
.
.
.
p
r
o
c
:
s
w
$
3
1
,
-
1
2
(
$
s
p
)
a
d
d
$
s
p
,
$
s
p
,
-
1
6
.
.
.
a
d
d
$
s
p
,
$
s
p
,
1
6
I
n
c
r
e
m
e
n
t
s
p
t
h
e
n
P
u
s
h
A
c
t
i
v
a
t
i
o
n
R
e
c
o
r
d
M
o
s
t
C
o
m
m
o
n
M
e
t
h
o
d
a
d
d
$
s
p
,
$
s
p
,
-
1
6
s
w
$
8
,
1
6
(
$
s
p
)
s
w
$
1
2
,
1
2
(
$
s
p
)
s
w
$
6
,
8
(
$
s
p
)
j
a
l
p
r
o
c
a
d
d
$
s
p
,
$
s
p
,
1
6
.
.
.
p
r
o
c
:
s
w
$
3
1
,
4
(
$
s
p
)
A
c
c
e
s
s
i
n
g
P
a
r
a
m
e
t
e
r
s
i
n
t
h
e
P
r
o
c
e
d
u
r
e
l
w
$
4
,
4
(
$
f
p
)
#
p
a
r
a
m
e
t
e
r
1
l
w
$
5
,
8
(
$
f
p
)
#
p
a
r
a
m
e
t
e
r
2
l
w
$
6
,
1
2
(
$
f
p
)
#
p
a
r
a
m
e
t
e
r
3
•
This assumes that the parameters are
not passed via register.
C
a
l
l
e
r
-
S
a
v
e
d
/
C
a
l
l
e
e
-
S
a
v
e
d
R
e
g
i
s
t
e
r
s
•
T
o
a
v
o
i
d
u
n
n
e
c
e
s
s
a
r
y
r
e
g
i
s
t
e
r
s
a
v
e
s
/
r
e
s
t
o
r
e
s
,
s
o
f
t
w
a
r
e
c
o
n
v
e
n
t
i
o
n
d
i
v
i
d
e
s
t
h
e
r
e
g
i
s
t
e
r
s
i
n
t
o
t
w
o
s
e
t
s
:
–
“
c
a
l
l
e
e
s
a
v
e
d
r
e
g
i
s
t
e
r
s
”
(
a
l
s
o
c
a
l
l
e
d
“
s
a
v
e
d
r
e
g
i
s
t
e
r
s
”
)
:
–
p
r
e
s
e
r
v
e
d
a
c
r
o
s
s
a
c
a
l
l
•
c
a
l
l
e
r
d
o
e
s
n
o
t
h
a
v
e
t
o
w
o
r
r
y
a
b
o
u
t
s
a
v
i
n
g
t
h
e
m
.
–
T
h
e
c
a
l
l
e
e
m
u
s
t
s
a
v
e
t
h
e
m
i
f
i
t
w
a
n
t
s
t
o
u
s
e
t
h
e
m
.
•
c
a
l
l
e
e
s
a
v
e
d
r
e
g
i
s
t
e
r
s
a
r
e
$
1
6
-
$
2
3
,
$
3
0
(
$
f
p
)
Caller-Saved/Callee-Saved Registers
Cont.
–
“caller saved registers” (also called
“temporary registers”):
–
may be destroyed by the callee without
saving them.
–
The caller must save these registers if it
wants to preserve the values
•
caller saved registers (except those reserved for
system use): $2-$15, $24-25, $31 ($ra)
P
a
s
s
i
n
g
P
a
r
a
m
e
t
e
r
s
•
A fast method of passing parameters to a
procedure is using registers (they are fast)
–
MIPS uses the software convention that the
first 4 parameters are passed in registers $4-
$7
–
Handles most procedure calls, because usually
few parameters are passed.
–
Additional parameters are passed on the
system stack.
P
a
s
s
i
n
g
P
a
r
a
m
e
t
e
r
s
C
o
n
t
.
move $4, param1
move $5, param2
move $6, param3
move $7, param4
addi $29, $29, -12
# make room on stack for two params
# and return address
sw $31, 4($29)
# save return address in top stack
# location
sw $14, 8($29)
# store 6th param in next stack location
sw $15, 12($29)
# store 5th param in next stack location
jal Proc1
# call procedure
...
P
a
s
s
i
n
g
P
a
r
a
m
e
t
e
r
s
C
o
n
t
.
Proc1:
# params 1-4 are in registers $4-$7,
# can use them directly from those regs.
lw $8, 12($29)
# put 5th parameter in a register
lw $9, 8($29)
# put 6th parameter in a register
...
lw $10, 4($29)
# put return address in a register
addi $29, $29, 12
# deallocate stack space
jr $10
# return to caller
...
R
e
t
u
r
n
V
a
l
u
e
s
•
P
r
o
c
e
d
u
r
e
r
e
t
u
r
n
v
a
l
u
e
s
a
r
e
h
a
n
d
l
e
d
s
i
m
i
l
a
r
l
y
:
–
F
i
r
s
t
2
r
e
t
u
r
n
v
a
l
u
e
s
a
r
e
r
e
t
u
r
n
e
d
i
n
r
e
g
i
s
t
e
r
s
,
$
2
a
n
d
$
3
.
–
A
d
d
i
t
i
o
n
a
l
r
e
t
u
r
n
v
a
l
u
e
s
a
r
e
p
a
s
s
e
d
b
a
c
k
o
n
t
h
e
s
t
a
c
k
.
•
B
y
c
o
n
v
e
n
t
i
o
n
w
i
t
h
H
L
L
,
o
n
l
y
1
v
a
l
u
e
i
s
r
e
t
u
r
n
e
d
–
V
o
a
n
d
V
1
s
u
p
p
o
r
t
d
o
u
b
l
e
l
e
n
g
t
h
r
e
t
u
r
n
v
a
l
u
e
s
.
D
y
n
a
m
i
c
S
t
o
r
a
g
e
A
l
l
o
c
a
t
i
o
n
•
A
p
r
o
c
e
d
u
r
e
’
s
l
o
c
a
l
v
a
r
i
a
b
l
e
s
c
a
n
b
e
a
l
l
o
c
a
t
e
d
o
n
t
h
e
s
y
s
t
e
m
s
t
a
c
k
,
o
n
p
r
o
c
e
d
u
r
e
e
n
t
r
y
–
A
l
l
o
w
s
i
n
s
t
a
n
c
e
s
o
f
v
a
r
i
a
b
l
e
f
o
r
r
e
c
u
r
s
i
v
e
c
a
l
l
s
–
P
r
o
v
i
d
e
s
p
r
o
p
e
r
v
a
r
i
a
b
l
e
s
c
o
p
e
–
A
l
l
o
w
s
e
a
s
y
d
e
a
l
l
o
c
a
t
i
o
n
•
E
.
g
.
,
a
l
l
o
c
a
t
i
n
g
2
l
o
c
a
l
i
n
d
e
x
v
a
r
i
a
b
l
e
s
.
R
a
t
h
e
r
t
h
a
n
w
r
i
t
e
:
.data
i:
.word
j:
.word
•
Y
o
u
w
r
i
t
e
:
.text
myproc: addi $29, $29, -8
#allocate space for 2 local variables
D
y
n
a
m
i
c
S
t
o
r
a
g
e
A
l
l
o
c
a
t
i
o
n
(
c
o
n
t
.
)
The first index variable is accessed as:
lw/sw $x, 4($29)
# its location is on the top of the stack
The second index variable is access as:
lw/sw $x, 8($29)
# its location is second from top of the stack
•
Local variables are pushed on top of return
address and any parameters passed on stack:
T
o
p
O
f
S
t
a
c
k
T
h
e
o
n
l
y
l
o
c
a
l
v
a
r
i
a
b
l
e
s
a
l
l
o
c
a
t
e
d
s
p
a
c
e
o
n
t
h
e
s
t
a
c
k
a
r
e
t
h
o
s
e
t
h
a
t
c
a
n
n
o
t
s
t
a
y
i
n
a
r
e
g
i
s
t
e
r
t
h
e
i
r
e
n
t
i
r
e
l
i
f
e
.
SumN Example
SumN Example.
SumN, Full AR creation
SumN, Full AR creation.
•
Same code as before
F
i
b
o
n
a
c
c
i
S
e
q
u
e
n
c
e
•
Defined as a recursive function
–
F(n) =
0
;
n=0
1
; n=1
F(n-1) + F(n-2)
;
otherwise
•
Generates the numbers
F
i
b
o
n
a
c
c
i
S
e
q
u
e
n
c
e
•
Java code
public int fibonacci(int n) {if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
F
i
b
o
n
a
c
c
i
S
e
q
u
e
n
c
e
Must create a dummy AR for
initial procedure call
Don’t have to save old a0
first time in
N
is loaded into a0 the
parameter
Save return value
somewhere safe
F
i
b
o
n
a
c
c
i
S
e
q
u
e
n
c
e
ra is stored in AR, we decide
to use s1 and s2, so they
must be saved onto the AR
There are 2 base cases,
each must be identified
Create a new AR for Fib(n-1),
saving a0 onto stack.
After Fib(n-1) return we must
undo the AR created above
F
i
b
o
n
a
c
c
i
S
e
q
u
e
n
c
e
Same as previous call,
except on return we save the
result in a different register.
Branch to code to add S1
and S2, the results of the 2
Fib calls
F
i
b
o
n
a
c
c
i
S
e
q
u
e
n
c
e
Load return value of each
base case as appropriate
into return register
Branch to code to add S1
and S2, the results of the 2
Fib calls
Restore the saved S1 and
S2 from AR, load the stored
ra from the AR, then return
from the procedure
W
h
e
n
t
o
c
r
e
a
t
e
a
n
A
R
•
Leaf function is one that does not call
any other function, including it’s self.
–
In this case an AR can be avoided.
–
Jal target, and jr $ra will suffice
•
All other cases require a full AR
D
y
n
a
m
i
c
a
n
d
S
t
a
t
i
c
L
i
n
k
s
•
Dynamic links are simply the old fp,
which binds together the AR.
•
When a function contains a function, a
static link will point back to the level of
nested function.
•
E.g. If
p
is contained in
f
then the static
link points from p to the AR of f.
Regardless if p calls itself recursively.
S
t
a
t
i
c
l
i
n
k
E
x
a
m
p
l
e
F(){int
x
P(int y){x
=2;
if (y>0)
P(y-1);
}
}
•
The AR for F will have x declared at
x -> fp-12
To access x from P
lw t0, -8(fp)
lw t1, -12(t0)
M
a
i
n
(
)
a
s
a
P
r
o
c
e
d
u
r
e
•
Main () is called by the operating system,
somewhat like a procedure, except:
–
Return address is not saved, so called using jump
rather than JAL
•
OS does not necessarily want to execute the next
instruction after jump to user code
–
Return is via a special instruction SYSCALL, which
jumps to a special return location in the OS.
•
User is blocked from jumping to other locations in the OS,
for security and reliability
•
SYSCALL exit.
G
l
o
b
a
l
D
a
t
a
.
•
.globl
•
Allows the label to be referenced by
other programs.
•
Similar to public and private in Java.
G
l
o
b
a
l
D
a
t
a
•
Non-local data that can be accessed
in all procedures (called Global Data)
is kept in a special region of memory
–
Global data space is accessed via global
pointer ($gp)
–
Created by:
.extern name size_in_bytes.
•
Compiler and linker then reference
this data as offsets to $gp
•
Normally used when multiple
programs wish to access common
resources.
End
Delve into the intricate process of procedure execution in programming, covering topics such as parameter passing, storage allocation, register usage, and more. Gain insights into why procedures are essential for code modularity and efficiency, as well as the steps involved in executing procedures effectively.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Week 7 Where is all the knowledge we lost with information? T. S. Eliot 1
Procedures 1 - MAL Procedure Call & Return Mechanisms 2 - Dynamic Storage Allocation 3 - Activation Records 4 - Parameter Passing 5 - Saving Registers 6 - MIPS Register Usage 7 - Sample MAL Program that uses Procedures 2
Why Use Procedures? Code is easier to understand. Easier to develop and maintain. Different programmers can write different parts of the program Code becomes modular 3
Why Procedures Cont. Allows reduction in size of program in exchange for somewhat reduced performance (overhead of Call, Return, and certain associated overhead) 4
HLL Compilers .. generate assembly language instructions to implement calling the procedure returning from the procedure passing parameters to the procedure returning parameters from the procedure 5
MAL Procedure Call & Return Mechanism 1 - Save the return address 2 - Call the procedure 3 - Execute the procedure 4 - Return to calling program 6
Reality -Procedure Execution Steps 1. Save parameters. Where? In registers (fast) or in memory (slow) 2. Save return address. Where? In registers (fast) or in memory (slow) 3. Call procedure. How? new jump instruction 7
Procedure Execution Steps Cont. 4. Allocate space to store procedure s variables (local variables). Why? Variables are used temporarily, space can be reclaimed upon return. For recursive procedure call, must have multiple copies of local variables, one for each recursion. How? using a special stack, the system stack 8
Procedure Execution Steps Cont. 5. Execute procedure 6. Deallocate local variables. How? Pop them off the system stack 7. Save return values, if any. Where? In registers (fast) or in memory (slow) 8. Get return address 9. Return. How? new jump instruction 9
Procedure Call MAL has a special jump instruction for procedure calls, Jump and Link ( jal ) Instruction s assembly format: jal proc_label Instruction s action: program jumps to the address represented by proc_label return address (address of instruction after jal ) is saved in $31, called the link register because it links the procedure back to the return location. 10
Procedure Return A new instruction Jump Register ( jr ) is used for returning from a procedure Instruction s assembly format: jr $x Instruction s action: program jumps to the address contained in register x. Together jal and jr allow for simple and fast subroutine calls/returns: 11
MAL Procedure Call Summary jal proc1 next_instruction: ... ... done next_instruction proc1: ... ... jr $31 12
MIPS Jump Instructions j jump to a label (similar to branch) Absolute address jal jump and link jumps to a procedure saves the return address in $31 jr R jumps to the location pointed to by register R jump register 13
Procedure Call and Return jal label1 # Jump and Link jumps to the instruction at label1 saves the return address in $31 jr $31 # Jump Register copies value in register $31 to the PC 14
Nested Procedure Calls We have a problem: when procedure A calls another procedure B (a nested procedure call ) the contents of $31 are overwritten and the return address for A is lost: 15
Nested Procedure Calls Cont. Solution: transfer the return address to another register In A, before call to B: move $16,$31 # save return address in reg 16 To return from A: jr $16 # return address is in reg 16 This has limitations: Limited by number of nested procedures Programmer must keep return addresses straight 16
Dynamic Storage Allocation return address in register $ra ($31) must save this return address for nested procedure calls recursive procedure calls 17
Recursive Procedure Calls It is possible for a procedure to conditionally call itself, a recursive procedure call . The number or recursive calls can be indefinite Cannot save return address in registers Solution: save return addresses on the system stack Want a stack, because addresses are needed in the reverse order they are produced. A register ($29) is designated as the system stack pointer 18
MIPS System Stack stack pointer $sp ($29) base of stack at high memory stack grows down (toward smaller addresses) $sp points to first empty location at the top of the stack 0x7fffffff Stack Segment Data Segment Test Segment 0x400000 Reserved 19
Push sw addi $8, 0($sp) $sp, $sp, -4 or addi sw $sp, $sp, -4 $8, 4($sp) 20
Stacking the Return Address The system stack grows from high- numbered memory toward low-numbered memory addi $sp, $sp, -4# make room on stack for return addr. sw $ra, 4($sp) # save return address to the stack ... beq $8, $9, exit# test some condition jal Proc1 # recursive call ... lw $10, 4($sp) # restore return address from the stack addi $sp, $sp, 4# deallocate the stack space jr $10 # return to the calling routine Proc1: exit: 21
Pop addi lw $sp, $sp, 4 $8, 0($sp) or lw addi $8, 4($sp) $sp, $sp, 4 22
Activation Records - Concept When a procedure is invoked old environment must be saved. new environment is created When the procedure terminates this new environment disappears and the old environment must be restored. An activation record consists of all the information that corresponds to the state of a procedure. 23
Saving and Restoring Activation Record (or Stack Frame) is pushed onto the stack just like a word. Can consist of multiple words Varies in size. Stack pointer ($29) must be adjusted by this size After pushing After popping. 24
Pushing one at a time sw add $sp, $sp, -4 sw $12, 0($sp) add $sp, $sp, -4 sw $6, 0($sp) add $sp, $sp, -4 jal proc ... sw $31, 0($sp) add $sp, $sp, -4 $8, 0($sp) proc: 25
Push Activation Record then Increment sp sw sw sw jal ... sw add $sp, $sp, -16 ... add $sp, $sp, 16 $8, 0($sp) $12, -4($sp) $6, -8($sp) proc proc: $31, -12($sp) 26
Increment sp then Push Activation Record Most Common Method add $sp, $sp, -16 sw $8, 16($sp) sw $12, 12($sp) sw $6, 8($sp) jal proc add $sp, $sp, 16 ... sw $31, 4($sp) proc: 27
Accessing Parameters in the Procedure lw lw lw $4, 4($fp) $5, 8($fp) $6, 12($fp) # parameter 1 # parameter 2 # parameter 3 This assumes that the parameters are not passed via register. 28
Caller-Saved/Callee-Saved Registers To avoid unnecessary register saves/restores, software convention divides the registers into two sets: callee saved registers (also called saved registers ): preserved across a call caller does not have to worry about saving them. The callee must save them if it wants to use them. callee saved registers are $16-$23, $30 ($fp) 29
Caller-Saved/Callee-Saved Registers Cont. caller saved registers (also called temporary registers ): may be destroyed by the callee without saving them. The caller must save these registers if it wants to preserve the values caller saved registers (except those reserved for system use): $2-$15, $24-25, $31 ($ra) 30
Passing Parameters A fast method of passing parameters to a procedure is using registers (they are fast) MIPS uses the software convention that the first 4 parameters are passed in registers $4- $7 Handles most procedure calls, because usually few parameters are passed. Additional parameters are passed on the system stack. 31
Passing Parameters Cont. move $4, param1 move $5, param2 move $6, param3 move $7, param4 addi $29, $29, -12 sw $31, 4($29) sw $14, 8($29) sw $15, 12($29) jal Proc1 ... # make room on stack for two params # and return address # save return address in top stack # location # store 6th param in next stack location # store 5th param in next stack location # call procedure 32
Passing Parameters Cont. # params 1-4 are in registers $4-$7, # can use them directly from those regs. # put 5th parameter in a register # put 6th parameter in a register Proc1: lw $8, 12($29) lw $9, 8($29) ... lw $10, 4($29) addi $29, $29, 12 # deallocate stack space jr $10 ... # put return address in a register # return to caller 33
Return Values Procedure return values are handled similarly: First 2 return values are returned in registers, $2 and $3. Additional return values are passed back on the stack. By convention with HLL, only 1 value is returned Vo and V1 support double length return values. 34
Dynamic Storage Allocation A procedure s local variables can be allocated on the system stack, on procedure entry Allows instances of variable for recursive calls Provides proper variable scope Allows easy deallocation E.g., allocating 2 local index variables. Rather than write: .data i: .word j: .word You write: .text myproc: addi $29, $29, -8 #allocate space for 2 local variables 35
Dynamic Storage Allocation (cont.) The first index variable is accessed as: lw/sw $x, 4($29) The second index variable is access as: lw/sw $x, 8($29) # its location is second from top of the stack Local variables are pushed on top of return address and any parameters passed on stack: # its location is on the top of the stack Top Of Stack The only local variables allocated space on the stack are those that cannot stay in a register their entire life. 36
SumN Example 37
SumN, Full AR creation. Same code as before 40
Fibonacci Sequence Defined as a recursive function F(n) = 0 1 F(n-1) + F(n-2) Generates the numbers ; n=0 ; n=1 ; otherwise 41
Fibonacci Sequence Java code public int fibonacci(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fibonacci(n - 1) + fibonacci(n - 2); } 42
Fibonacci Sequence Must create a dummy AR for initial procedure call Don t have to save old a0 first time in N is loaded into a0 the parameter Save return value somewhere safe 43
Fibonacci Sequence ra is stored in AR, we decide to use s1 and s2, so they must be saved onto the AR There are 2 base cases, each must be identified Create a new AR for Fib(n-1), saving a0 onto stack. After Fib(n-1) return we must undo the AR created above 44
Fibonacci Sequence Same as previous call, except on return we save the result in a different register. Branch to code to add S1 and S2, the results of the 2 Fib calls 45
Fibonacci Sequence Load return value of each base case as appropriate into return register Branch to code to add S1 and S2, the results of the 2 Fib calls Restore the saved S1 and S2 from AR, load the stored ra from the AR, then return from the procedure 46
When to create an AR Leaf function is one that does not call any other function, including it s self. In this case an AR can be avoided. Jal target, and jr $ra will suffice All other cases require a full AR 47
Dynamic and Static Links Dynamic links are simply the old fp, which binds together the AR. When a function contains a function, a static link will point back to the level of nested function. E.g. If p is contained in f then the static link points from p to the AR of f. Regardless if p calls itself recursively. 48
Static link Example F(){ int x P(int y){ } RA Dynamic Static } The AR for F will have x declared at x -> fp-12 To access x from P lw t0, -8(fp) lw t1, -12(t0) x=2; if (y>0) P(y-1); 49
Main () as a Procedure Main () is called by the operating system, somewhat like a procedure, except: Return address is not saved, so called using jump rather than JAL OS does not necessarily want to execute the next instruction after jump to user code Return is via a special instruction SYSCALL, which jumps to a special return location in the OS. User is blocked from jumping to other locations in the OS, for security and reliability SYSCALL exit. 50
