Nested Procedures

A nested procedure is called from within another procedure as shown below. The Main program calls procedure A, which calls procedure B:

When the jal B instruction is executed, the return address in register $ra for procedure A will be overwritten with the return address for procedure B. Procedure B will return correctly to A, but when procedure A executes the jr instruction, it will return again to the return address for B, which is the next instruction after jal B in procedure A. This puts procedure A in an infinite loop.

To implement the linkage for nested procedures, the return address for each procedure must be saved somewhere other than register $ra. Note that the procedure call/return sequence is a LIFO process: the last procedure called is the first to return. A stack is the natural data structure for saving the return addresses for nested procedure calls.

The system stack is located at the top of the user memory space and grows downward toward smaller memory addresses. Register $29, also called $sp, is the stack pointer to the system stack. It contains the address of the first empty location at the top of the stack. The system stack is intended for the storage of addresses and is structured for word-sized data.

The system stack is commonly used to save return addresses. They can be pushed on the stack when a procedure is called and popped off to execute a return instruction.

A return address in register $ra can be pushed onto the system stack with the following MAL code:

        sw      $ra, ($sp)
        add     $sp, -4

The following code pops a return address from the top of the stack and returns it in register $ra:

        add     $sp, 4
        lw      $ra, ($sp)

Any procedure which calls another procedure should save its return address on the system stack. The skeleton code for saving the return address for procedure A is:

A:      sw      $ra, ($sp)  # save the return address
        add     $sp, -4     # on the system stack
        #
        # body of procedure A
        #
        add     $sp, 4      # restore the return address
        lw      $ra, ($sp)  # from the system stack
        jr      $ra         # return to calling program

Inside a procedure, the number of pushes must equal the number of pops to ensure that the stack pointer is returned to its original position after each procedure call/return sequence. Unmatched pushes or pops from the system stack corrupt the procedure linkage and produce unpredictable results, such as illegal instructions or memory access violations.