CS 301 Lab: Nested Procedures


        In this lab you will learn how to write nested procedures and
        how to preserve register contents across procedure calls.

Nested Procedures

In CS 201 you learned how to write simple procedures. They look something like this: 
############################
# Simple procedure call
############################

        .text
	.globl __start
__start:
        #Do some stuff
	jal	subProc1	#convert value to fixed point
	#Do more stuff
	li	$v0, 10         #exit program
	syscall

	
############################
#subProc1
############################
#Simple procedure
############################
#Input:  None
#Output: Prints a message on the console
############################
	.text
subProc1:
	la	$a0, s1out1     #print a message
	li	$v0, 4
	syscall
	jr	$ra             #return from procedure

	.data
s1out1:	.asciiz "***Hello from subProc1***\n"
Simple, but that doesn't work for procedures that need to call other procedures. For example this program: 
############################
# Functions calling Functions
#
# A demo program showing how to do robust function calls using the stack.
############################

#Main program
	.text
	.globl __start
__start:

	la	$a0, out1       #print a message
	li	$v0, 4
	syscall
	jal	subProc1	#call a simple procedure
	la	$a0, bye        #print a good bye message
	li	$v0, 4
	syscall
	li	$v0, 10         #exit program
	syscall
	
	.data
out1:	.asciiz "Welcome to main. I will now call some procedures...\n"
bye:	.asciiz "Goodbye. Come again soon.\n"

	
############################
#subProc1
############################
#Simple procedure
############################
#Input:  None
#Output: Prints a message on the console
############################
	.data
s1out1:	.asciiz "***Hello from subProc1***\n"

	.text
subProc1:
	jal	subProc2        #call subprogram
	la	$a0, s1out1     #print a message
	li	$v0, 4
	syscall
	jr	$ra             #return to caller

	
############################
#subProc2
############################
#Simple procedure
############################
#Input:  None
#Output: Prints a message on the console
############################
	.data
s2out1:	.asciiz "***Hello from subProc2***\n"

	.text
subProc2:
	la	$a0, s2out1     #print a message
	li	$v0, 4
	syscall
	jr	$ra             #return to caller
Which you might expect to produce this output: 
Welcome to main. I will now call some procedures...
***Hello from subProc2***
***Hello from subProc1***
Goodbye. Come again soon.
instead it gets stuck in an endless loop and writes 
***Hello from subProc1***
***Hello from subProc1***
***Hello from subProc1***
***Hello from subProc1***
***Hello from subProc1***
Until you force it to quit. Why?

The answer is in the jal and jr $ra instructions. jal automatically stores the next instruction's address in $ra. When jr $ra is called it puts that value in the program counter and the program picks up with the instruction after the procedure call. However, when a procedure calls a procedure the same register, $ra, is used. If the value is not saved somewhere else and restored before returning then jr $ra will just go back to the last address stored in $ra. Execution will resume after the last function call and you have a loop.

The solution is to save $ra somewhere. If you know the procedure you are calling doesn't use a register you also are not using you could save $ra there. The problem with that is you will eventually run out of registers. You need a storage space that can get as big as you need and that is easily accessible. The stack is such a space. You should push and pop $ra at the beginning and end of every procedure that needs to call another so it always remembers where it came from.

Safe Nested Procedures

$ra isn't the only register that needs saving. When you call a procedure you expect it to do its job and leave the registers you were using alone so that you can finish your work. Certain registers are always preserved by convention. Responsibility for saving registers is divided between the caller and the callee.

Caller-saved registers: $v0-$v1, $t0-$t9
Callee-saved registers: $ra, $a0-$a3, $s0-$s7, $gp, $sp, $fp

Bold registers must must have the same value before and after a procedure is called. If you need to keep the values in any of the other registers your code should save them before calling a procedure just in case it needs them too.

There are four tasks that should be done to make a safe procedure call:

  1. Prepare to call (caller)
  2. Save and prepare to run (callee)
  3. Restore and return (callee)
  4. Prepare to continue (caller)

Lets look at the tasks in detail:

  1. Prepare to call (caller)
    1. Look at the code around the call. Does the algorithm depend on any of the $t* or $v* registers? Then you need to save them.
    2. If you need to pass parameters on the stack make space for them and load them.
  2. Save and prepare to run (callee)
    1. Save any of the $gp, $s*, or $a* registers you use in the procedure before using them.
    2. If this procedure will call another save $ra
    3. If this procedure needs local variable space save $fp on the stack, give $fp the value $sp had when the procedure started, and make sure there's room on the stack for the variables. Initialize those variables.
  3. Restore and return (callee)
    1. Restore any saved registers in the correct order.
    2. Shrink the stack to account for local variables and saved registers.
  4. Prepare to continue (caller)
    1. If you passed arguments on the stack, shrink the stack accordingly.
    2. If you saved any registers, restore them in the correct order.

For convenience you can use these two macros: push_and_allocate and pop_and_deallocate. Download them here (stackOps.m4). They will be used in the following example.

Macro Description
push_and_allocate
  • Allocates space on the stack to accomodate listed registers plus any extra space needed for variables or parameters.
    • Quotes around the list of registers are not optional.
  • Stores the registers in order - first one at the bottom, next above it, etc.
    • Space for parameters or variables is at the top of the stack.
Use: push_and_allocate(`$t1, $t2, $v0',4)
Output: 
        addi    $sp, -16
        sw      $t1, $sp + 12
        sw      $t2, $sp + 8
        sw      $v0, $sp + 4
pop_and_deallocate
  • Loads values off the stack into specified registers in order.
    • Quotes around the list of registers are not optional.
  • Shrinks the stack. The last parameter may be used to account for other space allocated on stack.
Use: pop_and_deallocate(`$t1, $t2, $v0',4)
Output: 
        sw      $t1, $sp + 12
        sw      $t2, $sp + 8
        sw      $v0, $sp + 4
        addi    $sp, 16

Note: When you use the stack, words must be aligned on a 4 byte boundary. That means you should allocate stack space for variables and arguments in multiples of 4 bytes even if you don't need the last few bytes.

Dissection of a Safe Procedure

One form of procedure calls itself over and over again to solve a problem. This is called a recursive procedure. This kind of procedure absolutely must follow safe procedure writing rules. The following is an example of such a procedure. You can download it here: recurse.m4. It requires these macro libraries for preprocessing: printLib.m4, stackOps.m4, foreach.m4.

Code Nesting Role 
############################
#
# recurse.[m4|s]
#
# A recursive string decoder.
# Decodes strings where the first part of the message is after a '~'
# and the second is in reverse before the '~'
#
# Written to demonstrate the following MIPS procedure tricks:
#	- saving caller and callee registers
#	- passing arguments on the stack
#	- creating local variables on the stack
#	- nested functions
#
############################

include(printLib.m4)
include(stackOps.m4)

############################
#decode
############################
#decodes messages encoded in reverse.forward form.
############################
#Input: Argument 1(stack) - memory address pointing to a location in a 
#	string
#Output: Prints the decoded message on the console
#
#Algorithm:
#  examine character c.
#    case c == '~' 
#       print everything after c
#    case c == end of string
#       break
#    default (c is a reversed character)
#       call decode with next character on string
#	print c
#	break
#  return from procedure
#
#Variable map
#  d_c - argument. frame pointer.  Pointer to current character
#  d_pchr - local. frame pointer - 20. Two character string for
#           printing d_c
############################
	.text
decode:

			#set up procedure
	push_and_allocate(`$ra, $fp, $s0, $a0', 4)
	addi $fp, $sp, 20	#set up frame pointer
	define(`d_pchr', `-20')	dnl give a convenient name to the variable
	define(`d_c', `0')	dnl name for argument 1.
2. Save and Prepare to Run
			#examine character d_c
	lw $s0, d_c`'($fp)	#get the address of the character
	lb $t1, ($s0)		#get the character itself
				#begin case statement
	li $t2, '~'
	beq $t1, $t2, caseDot
	beq $t1, 0, caseEOL
	j default
caseDot:	
	addi $a0, $s0, 1	#point to next character
	printStr($a0)		#print the rest of the string
caseEOL:	
	j endCase
default:	

	addi $s0, $s0, 1	#point to next character

			#Set up procedure call to decode
				#Save caller registers
	push_and_allocate($t1, 4)	
	sw $s0, d_c ($sp)	#pass pointer to next character
1. Prepare to call
	jal 	decode		#recursively call decode


			#clean up after procedure call
				#Restore caller saved registers and close stack
	pop_and_deallocate($t1, 4)
4. Prepare to Continue
			#print c
	sb $t1, d_pchr ($fp)	#put the character in our local variable
	li $t1, 0      		#0 for null terminated string 
	sb $t1, 1 + d_pchr ($fp)#put a null on the local variable
	addi $a0, $fp, d_pchr	#explicit pointer to local variable
	printStr($a0)		#print the local variable

endCase:

			#prepare to return from procedure
	pop_and_deallocate(`$ra, $fp, $s0, $a0',4)
	jr $ra
3. Restore and Return

############################
#Main program
############################
	.data
msg:	.asciiz "\n!dedoced yllufsseccus~String "
		
	.text
	.globl __start
__start:

			#prepare to call procedure
	addi $sp, $sp, -4	#make space on stack for argument
	la $a0, msg		#get address of string
	sw  $a0, d_c ($sp)	#Load argument on stack
1. Prepare to Call
	jal	decode		#call procedure

	addi $sp, $sp, 4	#close space for argument on stack
4. Prepare to Continue
	li	$v0, 10
	syscall

Things to notice:

Extra Safe Procedures

Sometimes the rules for writing safe procedures aren't enough. There are two cases to be aware of.

  1. Reentrant code: This is code that can have more than one active copy. The recursive procedure above is an example of such code. OS procedures and library procedures on multitasking operating systems must also be reentrant. The rules for a reentrant procedure are:
  2. Interrupt code: This is code that handles a hardware request. It may be called at any time during any procedure. It must leave the CPU in exactly the same state it found it.

Lab Assignment

Complete a reentrant procedure that performs an in-order traversal of a tree that contains a message.
This page last modified:
Accessed     times.

CS Dept Home Page
CS Dept Class Files
CS115 Lab Files

Copyright: Department of Computer Science, University of Regina.