CSE 378 Fall 2006

CSE Home

CSE 378 Fall 2006

About Us

Search

Contact Info

Home Administrative  Syllabus  Office Hours  Mailing List Assignments  Reading  Homework  Labs  Exams Resources  Lecture Slides  Handouts  Wiki  MIPS Resources  AHDL Resources Anonymous Feedback  Feedback Form

Assignment 2 - Function Calling in MIPS Assembly (Wikified Version) Assigned: 10/9/2006 Due: 10/18/2006 at 5 pm Objective The objective of this assignment is to write a program that utilizes function calling while following the proper function calling conventions in MIPS assembly. To demonstrate your understanding of this topic, you will write a recursive implementation of Quicksort or Mergesort. Writing MIPS functions In assembly, you will write and call functions in assembly. Unlike in a higher level language where you would simply use something like "someFunction()" to call a function, you must actually tell the program to jump to a specific location in memory and store the address of the next instruction so that it can resume execution after it has completed the function. In order to do this, we use the JAL instruction to make the jump and store the location to continue execution from (which is the address of the JAL instruction + 4 bytes), and the JR instruction to jump back to that point in the program once the function execution is completed. Apart from methods of calling functions, a second key difference between a higher level programming language and assembly is that in assembly, you must manage the preservation of register values across function calls. For example, if you are using the register $t0, which is defined as being a temporary register, you are not guaranteed that its value will be preserved after a function call. The implication of this is that if you wish to preserve the value of the register to use it after a function call, you must store it to the stack, or place it in one of the safe registers ($s0 - $s7). Conversely, if your function makes use of one of the safe registers, like $s0, you must be able to restore the value of $s0 once your function completes, so that the calling function will still have the value that it expects in that register. You can accomplish this by pushing the value of $s0 onto the stack when your function begins, then popping it when your function completes. When modifying safe registers, you must ALWAYS assume that they have data in them and take steps to preserve these values, regardless of whether or not they are being used prior to your function's execution. It is especially important that you know which registers are considered volatile (that is, they can be modified by a function that you call) and non-volatile. A list of registers along with their volatility is available on the green card. You must take the appropriate steps to preserve those values as the assembler will not do this for you. It is particularly important that you do this with $ra, which contains the return address for your function. If you make a function call from within your function without preserving $ra, you will be unable to return to your calling function, and will likely cause an infinite loop instead. It is good practice to always put $ra on the stack at the start of your function and restore it at the end to make sure that you can return to the proper location in the program. This is also a good point to introduce some conventions regarding the stack pointer. The first is that the stack grows downwards as more data is put on it. That is, the stack starts at 0x7FFFEFFC in SPIM, and each time you add something to the stack, you decrement $sp by 4. To pop something from the stack, you simply set $sp equal to $sp + 4. We will be following the convention where the stack pointer will point to the top of the stack (used memory) when your function begins and you must allocate space based on this for your function to use. It is best to perform one stack allocation at the start of the function with enough room for any variables that you will require, then unallocate this space at once at the end of the function. To access various parts of the stack, use offsets with your load and store instructions. At a minimum, you will allocate 20 bytes on the stack, where the lower 16 bytes (in other words, the top of the stack) are reserved for storing arguments to pass to any functions that you call, and the next 4 bytes are used for the return address. As a result, arguments a0-a3 will be at locations $sp through $sp+12, while the return address for your function will always be at $sp+16. Depending on the situation, you may allocate more space to allow you to store register values in the $s0-s7 registers, local variables, and other such things. Function calling warmup exercises Write assembly code to accomplish the following tasks. You must follow proper register usage and function calling conventions to receive full credit. Assume that you are writing a function that will overwrite the following registers: $s0, $s1, $s2, $t1, $a0, $a1, and $v0. Write two code blocks: one that saves the registers that need to be saved at the beginning of your function and one that restores those registers after your function has finished execution. Write a function that iteratively prints out the first 10 fibonacci numbers. To print integers to the screen, place the value that you wish to print in $a0, the value 1 in $v0, then use the command "syscall" on a line by itself. To print a char, store the ASCII value of the character in $a0, and the value 11 in $v0 then use the "syscall" instruction. Write a function that recursively calculates the first 10 fibonacci numbers and prints them out. Writing a Quicksort/Mergesort function The main goal of this assignment is to write an assembly version of either the Quicksort or Mergesort function. You will be sorting an array of 32-bit signed numbers stored in memory in ascending order. The address of the first element in this array will be provided to you in $a0, and it is expected that after sorting, the array will still occupy the same location in memory as the original array did. Your implementation must be recursive and follow proper register usage and function calling conventions. If you have forgotten the algorithms, a decent description of mergesort is available here, and a description of Quicksort is available here. A template which you can use, which includes a test set of data, is available here. When we test your implementations, we will replace the data in the template with our own set of data and you will be graded based on how well your program sorts our data set. There is a possibility that there will be a prize for the person who writes the fastest implementation (based on number of instructions executed) of a sort function. The results of this will be based on a run of your function on our data set. Turnin When you are satisfied with your solutions, produce a zip file containing two files: solutions to the problems, and your sort function. Place the resulting zip file in a location accessible via attu and use "turnin -c cse378 -p a2 'your .zip file'" to submit your program for grading. If you are using a late day, use "turnin -c cse378 -p a2_late 'your .zip file'" instead.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to Course Staff]