Chapter 9 -- procedures
All about Procedures
--------------------
an introduction to procedures
why have procedures?
-- reuse of code simplifies program writing
-- modular code facilitates modification
-- allows different programmers to write different parts of the
same program
-- etc.
Assembly languages typically provide little or no support for
procedure implementation.
So, we get to build a mechanism for implementing procedures out
of what we already know.
First, some terms and what we need.
begin
.
.
.
x := larger(a, b); CALL
.
.
.
end.
HEADER PARAMETERS
function larger (one, two: integer): integer;
begin
if ( one > two ) then
larger := one; BODY
else
larger := two
end;
Steps in the execution of the procedure:
1. save return address
2. procedure call
3. execute procedure
4. return
what is return address? instruction following call
what is procedure call? jump or branch to first instruction
in the procedure
what is return? jump or branch to return address
MAL implementation of SAL procedure call:
la $5, rtn1
b proc1 # one procedure call
rtn1: # next instruction here
.
.
.
la $5, rtn2
b proc1 # another procedure call
rtn2: # next instruction here
.
.
.
proc1: # 1st instruction of procedure here
.
.
.
jr $5
jr is a new instruction --
It does an unconditional branch to the address contained
in the register specified.
MIPS R2000 (MAL, actually) provides a convenient instruction for procedure
calls.
jal procname
does 2 things
1. it places the address of the instruction following it
into register $31. (The choice of 31 is arbitrary, but
fixed.)
2. it branches to the address given by the label (procname).
the example re-written:
jal proc1
.
.
.
jal proc1
.
.
.
proc1: # 1st instruction of procedure here
.
.
.
jr $31
one problem with this scheme. What happens if a procedure
calls itself (recursion), or if a procedure calls another
procedure (nesting) (using jal)?
The value in register $31 gets overwritten with each
jal instruction. Return addresses are lost. This
is an unrecoverable error!
What is needed to handle this problem is to have a way to
save return addresses as they are generated. For a recursive
subroutine, it is not known ahead of time how many times
the subroutine will be called. This data is generated
dynamically; while the program is running.
The best way to save dynamically generated data is on a stack.
SYSTEM STACK
------------
A stack is so frequently used in implementing procedure call/return,
that many computer systems predefine a stack, the SYSTEM STACK.
STATIC -- can be defined when program is written (compile time)
DYNAMIC -- is defined when a program is executed (run time)
in this case, it is the amount of storage that cannot be
determined until run time.
The size of the system stack is very large. In theory, it should
be infinitely large. In practice, it must have a size limit.
address | |
0 | your |
| program |
| here |
| |
| |
| |
| |
| |
| system | / \
very | stack | | grows towards smaller addresses
large | here | |
addresses
terminology:
Some people say that this stack grows DOWN in memory.
This means that the stack grows towards smaller memory
addresses. Their picture would show address 0 at the
bottom (unlike my picture).
DOWN and UP are vague terms, unless you know what the
picture looks like.
The MIPS system stack is defined to grow towards smaller
addresses, and the stack pointer points to an empty location
at the top of the stack. The stack pointer is register $29,
also called $sp, and it is defined before program execution
begins.
push, in MAL:
sw $?, ($sp) # the ? is replaced by whateger register
sub $sp, $sp, 4 # contains the data to be pushed.
OR
sub $sp, $sp, 4
sw $?, 4($sp)
pop, in MAL:
add $sp, $sp, 4 # the ? is replace by a register number
lw $?, ($sp)
OR
lw $?, 4($sp)
add $sp, $sp, 4
NOTE: if $29 is used for any other purpose, then the stack pointer
is lost.
An example of using the system stack to save return addresses:
jal doit
.
.
.
jal doit
.
.
.
doit: sw $31, ($sp) # save return address
sub $sp, $sp, 4
.
.
.
jal another # this would overwrite the return
# address if it had not been saved.
.
.
.
add $sp, $sp, 4 # restore return address
lw $31, ($sp)
jr $31
about STACK FRAMES (ACTIVATION RECORDS)
---------------------------------------
from a compiler's point of view, there are a bunch of things
that should go on the stack relating to procedure call/return.
They include:
return address (register)
parameters
other various registers
Each procedure has different requirements for numbers of
parameters, their size, and how many registers (which ones)
will need to be saved on the stack. So, we compose a
STACK FRAME or ACTIVATION RECORD that is specific to a
procedure.
Space for a stack frame gets placed on the stack each time
a procedure is called, and taken off the stack each time a
return occurs. These stack frames are pushed/popped
DYNAMICALLY (while the program is running).
example:
jal A
jal B
.
.
A: jal C
jal D
jr $31
B: jal D
jr $31
C: jal E
jr $31
D: jr $31
E: jr $31
show stack for a trace through this calling sequence
parameter passing.
------------------
parameter = argument
Just as there is little/no support for implementing procedures
in many assembly languages, there is little/no support for passing
parameters to those procedures.
Remember, when it comes to the implementation,
-- convention
-- its up to the programmer to follow the conventions
Passing parameters means getting data into a place set aside
for the parameters. Both the calling program and the procedure
need to know where the parameters are.
The calling program places them there, and possibly uses
values returned by the procedure. The procedure uses
the parameters.
Simplest mechanism -- registers
-------------------------------
the calling program puts the parameter(s) into specific registers,
and the procedure uses them.
example:
.
.
.
add $4, $20, $0 # put parameter in register 4
jal decrement
move $20, $4 # recopy parameter to its correct place.
.
.
.
decrement: add $4, $4, -1
jr $31
Notes: -- This is a trivial example, since the procedure is 1 line
long.
-- Why not just use $20 within the procedure?
1. convention -- parameters are passed in specific registers.
2. same procedure could be used to decrement the value
in other registers -- just copy the value to register $4
first, and copy it out afterwards.
MIPS convention -- when passing parameters in registers,
the first 4 parameters are passed in registers $4-7.
Then, any and all procdures use those registers for their parameters.
If there are nested subroutine calls, and registers $4-7 are
used for parameters, the values would be lost (just like the
return address would lost for 'jal' if not saved). There are
2 possible solutions.
1. For non-recursive nested calls, each procedure has associated
with it a section of memory. Before a nested call is made,
the parameters are stored in that memory. After the return
from the nested call, the values are restored.
2. For recursive calls, parameters are stored on the stack before
a nested call. After the return from the nested call, the
parameters are restored.
here's a general layout of how this second option is used
(with 4 or fewer parameters):
subroutine layout:
push return address on stack
subroutine calculations
to set up a call to subroutine2,
push current parameters (in $4-7) on stack
set up parameters to subroutine2 in $4-7
call subroutine2 (jal subr2)
copy any return values out of $4-7
pop current parameters from stack back to $4-7
more subroutine calculations
pop return address from stack
return (jr $31)
more about parameter passing.
a trivial example that contains nested calls, so saves
current parameters on the stack:
# a set of procedures that do the following,
# if a < b, then switch a with b and decrement both
# a is in register 20
# b is in register 21
.text
sub $8, $20, $21
bgtz $8, othercode
move $4, $20 # place parameters in registers
move $5, $21
jal s_and_d
move $20, $4 # copy out return values
move $21, $5
othercode:
done
# switch is a procedure to switch its 2 parameters, and then
# decrement each of the 2 parameters
# $4 -- first parameter
# $5 -- second parameter
# $8 -- temporary for switching
s_and_d: sw $31, 0($sp) # save return address on stack
addi $sp, $sp, -4
add $8, $4, $0 # switch the 2 parameters
add $4, $5, $0
add $5, $8, $0
jal decrement # the value to decrement is already
# in $4.
sw $4, 0($sp) # push current parameter on stack
addi $sp, $sp, -4
add $4, $5, $0 # set up parameter in $4
jal decrement
add $5, $4, $0 # copy return value
addi $sp, $sp, 4 # pop current parameter off stack
lw $4, 0($sp)
addi $sp, $sp, 4 # pop return address off stack
lw $31, 0($sp)
jr $31
# procedure decrement subtracts 1 from its parameter
# $4 -- parameter to be decremented
decrement: addi $4, $4, -1
jr $31
Summary and other ideas:
1. use registers
+ easy, and don't have to store data in memory (faster)
- limited number of registers
- doesn't work for recursion, and must be careful when
using it where there are nested subroutines
2. use some registers, and place the rest on the stack
+ since many procedures have few parameters, get the advantages
of (1) most of the time.
- lots of "data shuffling"
3. put all parameters on the stack (an unsophisticated compiler might
do this)
+ simple, clean method (easy to implement)
- lots of stack operations (meaning slow, since the stack is in
memory)
4. put parameters in memory set aside for them
+ simple, clean method
- lots of memory operations (slow)
- doesn't work for recursion
Note: whatever you do, try to be consistant. Don't use all 4 methods
in the same program. (Its poor style.)
New problem:
What happens if you've got lots of variables, and your procedure
runs out of registers to put them in. This occurs when you are
following the conventions for register usage, and you shouldn't
overwrite the values in certain registers.
Most common solution: store register values temporarily on the
stack.
a note on parameter passing --
a HLL specifies rules for passing parameters. There are basically
2 types of parameters.
Note that a language can offer 1 or both types.
call by value -- what C has. In Pascal, these are parameters
declared without the var in front of the variable name.
Fortran doesn't have this type of parameter.
The parameter passed may not be modified by the procedure.
This can be implemented by passing a copy of the value.
What call by value really implies is that the procedure can
modify the value (copy) passed to it, but that the value
is not changed outside the scope of the procedure.
call by reference -- what Fortran has. In Pascal, these are
"var type" parameters.
The parameter passed to the subroutine can be modified,
and the modification is seen outside the scope of the
subroutine. It is sort of like having access to global
variable.
There are many ways of implementing these 2 variable types.
If call by value is the only parameter type allowed, how
can we implement a reference type parameter?
Pass the address of the variable as the parameter. Then
access to the variable is made through its address. This
is what is done in C.
what the mechanisms should look like from the compiler's
point of view:
THE CODE:
call setup
procedure call
return cleanup
.
.
.
procedure: prologue
calculations
epilogue
CALL SETUP
allocate a stack frame
move $sp to give enough space for the procedure's frame
place parameters into stack frame
save registers (could go in prologue)
PROLOGUE
save return address in stack frame
copy needed parameters from stack into registers
save registers (could go in call setup)
EPILOGUE
restore (copy) return address from stack frame into $31
restore registers from stack frame (if saved in prologue)
RETURN CLEANUP
copy needed return values and parameters from $4-7 or stack
frame to correct places
restore registers from stack frame (if saved in call setup)
de-allocate stack frame
move $sp so the space for the procedure's frame is gone