Page 1 Chapter 9 Procedures1 A high level language programmer uses procedures for several reasons Code becomes modular facilitating later modification The writing of code within a modular program can be done by more than one programmer All that is necessary is that the functionality and parameters of the different procedures be well defined A compiler needs to generate assembly langugage code for implementing procedure calls returns and parameter passing There are many correct ways for doing these tasks The high level language specifies rules for syntax and functionality and a compiler will implement a set of conventions The conventions vary from computer to computer and they vary from language to language This chapter discusses how procedures are implemented at the assembly language level 9 1 MAL Procedure Call and Return Mechanisms Here are the four steps that need to be accomplished in order to call and return from a procedure 1 save return address 2 procedure call 3 execute procedure 4 return From Chapter 2 the SAL instructions that invoke a procedure by saving a return address and calling the procedure are the following la b proc1 ret ret addr proc1 ret addr MAL provides a single instruction that does both operations The MAL jal jump and link instruction simplifies the procedure call sequence The instruction jal procedure label does two things It places the address of the instruction following the jal instruction into register 31 also called ra and it branches to the instruction labeled procedure label The choice of register 31 is arbitrary but it it is fixed Its use is implied by the jal instruction The MAL jr jump register instruction is convenient to use for procedure returns Its execution causes the value contained in the register specified to be loaded into the Program Counter The effect of this is an unconditional jump to the address contained in the register 1 Copyright 1999 Oxford University Press Use by permission only Contact Peter Gordon pcg oup usa org REVISED September 7 1999 Page 2 Figure 1 contains skeleton code for a procedure that has no parameters The procedure call text call jal proc done proc procedure code here jr ra Figure 1 Procedure implementation using jal and jr instructions and return use jal and jr instructions 9 2 Dynamic Storage Allocation Placing a return address in a register works fine as long as there are no nested procedure calls A nested call is a procedure call within the body of a procedure If a nested procedure is invoked the value held in register ra will be overwritten To avoid the loss of return addresses a safe place for storing return addresses is needed For each procedure that has been invoked but not completed a return address must be saved Note that once a procedure has returned the space for the return address is no longer needed and can be reused for example to store a return address for a newly invoked procedure A method that can dynamically allocate space for procedures when they are invoked and deallocate the space when they return is needed The amount of memory required to save all the return addresses is therefore limited only by the number of levels of procedure calls permitted In many modern programming languages this limit is very large To provide space for storing many return addresses a stack is employed The space is said to be dynamically allocated Many computer systems implement a stack as part of the environment provided when a program is running This stack is referred to as the system stack It is such an important and frequently used structure that some computers provide assembly language support for accessing the stack efficiently The MIPS RISC architecture system stack has its bottom of the stack also known as the base at a very large memory address As items are pushed on the stack it grows towards smaller memory addresses By convention register 29 also called sp is a stack pointer for the system stack It contains the address of the first empty location at the top of the stack It is REVISED September 7 1999 Page 3 initialized prior to the beginning of a program s execution Figure 2 shows a diagram of the initial small memory addresses sp bottom of stack large memory addresses Figure 2 Initial empty state of the system stack state of the system stack A push operation to the system stack can be coded as sw 8 0 sp sub sp sp 4 or sub sp sp 4 sw 8 4 sp where the content of register 8 is the data being pushed onto the stack A pop operation from the system stack can be coded as add sp sp 4 lw 8 0 sp or lw 8 4 sp add sp sp 4 Using the Stack for Return Addresses One common use of the system stack is saving return addresses They can be pushed onto the stack once a procedure has been called using jal and popped off just before a return instruction REVISED September 7 1999 Page 4 jr is executed Figure 3 contains a MAL procedure that implements a power function Given a text li 16 10 li 18 1 move 19 17 jal power done power sub sp sp 4 sw ra 4 sp if sub 19 19 1 blez 19 endif base 10 calculations 18 will contain the result 19 is a counter 17 contains the power save return address by pushing it on the stack jal power recursive procedure call endif mul 18 18 16 16 contains base lw ra 4 sp restore return address by add sp sp 4 popping it off the stack return jr ra Figure 3 MAL implementation of power function base and a power the procedure calculates basepower The implementation given in Figure 3 uses global variables instead of parameters This is done in order to give an example of using the system stack for saving a return address while ignoring the issue of parameter passing The procedure is recursive Recursive procedure calls are a special case of nested procedure calls An example of recursion is when a procedure directly calls itself Because of the recursion it is necessary that return addresses be saved on the stack so that they are not overwritten and lost After being invoked the procedure pushes its return address saved in register ra by the jal instruction onto the stack Before it returns the procedure must restore the return address by popping it off the stack into register ra A procedure that does not call any other procedures is known as a leaf procedure It does not need to store its return address onto the stack the value can be held in register ra It may execute the push and pop but the push and pop of a return address is not required If it executes the push it must also execute the pop 9 3 Activation Records The