CS 208: Computer Organization & Architecture

Function-calling in MIPS

You may work on this assignment alone or with a partner, as you prefer.

High-level languages like Java, C, C++, Python, Lisp, Pascal, Haskell, Go, Swift, Algol 58,... all give the program the ability to write functions of one sort or another. As a programmer using C, for example, you specify your function's prototype or signature, giving the function a name, a list of parameters and their types, and the function's return type. For example:

For many functions, the prototype is enough to tell other programmers how to use the function. For others, a comment describing the operation of the function is needed to turn a prototype into a usable functional interface. But in any case, once you have specified the prototype of a function and provided an implementation of the function, other programmers can use that function in their own programs by using the language's function-calling syntax:

Regardless of the particulars of the syntax of functions in your high-level language of choice, at some stage of the compilation and execution of your program, that function call needs to be translated into machine language for the particular processor your computer is using. For "compile to machine language" languages like C, C++, Objective C, Pascal, etc., the compiled version of your program is assembly or machine language, and is different for every type of CPU for which you compile your program. For "compile to intermediate language" languages like Java, the compiled form of your program (e.g. the Java .class files) is the same regardless of the target processor, but then there needs to be a separate interpreter program on the target device (e.g. the "java" program when I execute "java MyMainClass").

Either way, eventually function-calling has to be implemented at the machine language level. For this assignment, you will implement a function-calling mechanism in MIPS, plus a recursive function to test it.

A simplified function-calling system in MIPS

As we discussed in class Friday, MIPS has three registers supporting function calling: $ra (return address), $sp (stack pointer), and $fp (frame pointer). We took a close look at how the gcc C compiler translates C function calling into MIPS stack frame manipulation.

For this assignment, you will implement a simplified version of function calling in MIPS. In this system, every function call will have a rigid 4-word stack frame structure:

This implies a very limited function structure, of course, with just one 32-bit parameter and a 32-bit return value, and space for one 32-bit local variable which the function may use or not use depending on its needs.

Your code will consist of four pieces:

• A subroutine labeled call, whose job is to set up the stack frame of a function and then pass control to the function. Preconditions for call are that $a0 contains the function's parameter and $a1 contains the function's starting address.
• A subroutine labeled return, whose job is to tear down the function's stack frame, placing the return value in $v0 and then jumping to the return address that was stored in the stack frame.
• A function labeled fib to test your function-calling system. fib will compute the Nth Fibonacci number recursively. Specifically, fib(0) = 1, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) if n > 1. Don't worry about what happens if n < 0.
• A simple main program to call fib(n) for an n stored in the .data section.

To call a function under this system:

1. Put the function's parameter in $a0
2. Put the function's address in $a1
3. jal call

To return from a function:

1. Make sure you have stored the return value in its proper place in the stack frame.
2. jal return

Notes

• One of the tests the graders and I will perform will be to call and return from our own function using your versions of call and return. If your program doesn't adhere to the specification, this test won't work.
• call and return will be a little weird, since neither one of them will return to the place it's jal'd from. Part of what you need to figure out is how to manipulate return addresses appropriately.
• Just to be clear: if you ever want to compute the Nth Fibonacci number for its own sake, do not compute it recursively. Doing so gives you a number of function calls proportional to 2^N. The point of using recursive fib(n) here is to have a simple but non-trivial recursive function to give us a reasonable test of our calling/returning system.
• If you find yourself putting a loop in fib, you're doing it wrong. Reread the assignment, talk to me or classmates, and think some more.

Have fun!

This one is really cool when you get it working. Questions are welcome, as always.