CS61C Summer 07
Homework 4

MIPS Procedures

Due July 15th at 11:59PM.

"TA" in charge: Scott

Goals

This assignment will give you practice with MIPS and SPIM. By the end of the homework assignment, you should be comfortable writing and reading MIPS code.

Background reading

Submitting Your Solution

Submit your solution by creating a directory named hw4 that contains files named hw4q1.s, hw4q2.s, hw4q3.s, hw4q4.s, hw4q5.s. (Note that capitalization matters in file names; the submission program will not accept your submission if your file names differ at all from those specified.) From within that directory, type submit hw4. This is not a partnership assignment; hand in your own work.

Problem 0

Copy the contents of ~cs61c/hw/04 to a suitable location in your home directory.

$ cp -r ~cs61c/hw/04/ ~/hw4

All the files referred in this homework will be in the folder you copied.

Problem 1 (hw4q1.s)

P&H Exercise 2.14. Reproduced here for ease of reference:

The MIPS translation of the C segment:

while (save[i] == k)
    i = i + 1;

on page 74 uses both a conditional branch and an unconditional jump each time through the loop. Only poor compilers would produce code with this loop over-head. Rewrite the assembly code so that it uses at most one branch or jump each time through the loop. How many instructions are executed before and after the optimization if the number of iterations of the loop is 10.

Save your answer to a file named hw4q1.s.

Problem 2 (hw4q2.s)

P&H Exercise 2.15. (Page 149)

Save your answer to a file named hw4q2.s.

Problem reproduced here for ease of reference.

Implement the following C code in MIPS, assuming that set_array is the first function called:

int i;
void set_array(int num){
	int array[10];
	for (i=0; i<10; i++){
		array[i] = compare(num, i);
	}
}

int compare(int a, int b){
	if (sub(a, b) >= 0)
		return 1;
	else
		return 0;
}

int sub (int a, int b) {
	return a-b;
}

Be sure to handle the stack pointer appropriately. The Array declared in set_array is allocated on the stack, and i corresponds to $s0. Draw the status of the stack before calling set_array and during each function call. Indicate the names of registers and variables stored on the stack and mark the location of $sp.

NOTE: I removed all references to $fp that are seen in the book for this problem. Since we did not cover the $fp register in lecture, using $fp is optional for this problem

Problem 3 (hw4q3.s)

P&H Exercise 2.16. Reproduced here for ease of reference:

Write a MIPS procedure to compute the nth Fibonacci number F(n) where:

F(n) = 0, if n = 0;
        1, if n = 1;
        F(n-1) + F(n-2), otherwise;

Base your algorithm on the recursive algorithm below (do not compile to an iterative solution):

int fib(int n){
        if (n == 0)
                return 0;
        else if (n == 1)
                return 1;
        else
                return fib(n-1) + fib(n-2);
}

Save your answer to a file named hw4q3.s.

Problem 4 (hw4q4.s and smc.s)

Self-Modifying code! You are given the code for function foo and bar inside hw4q4.s file. The code follows all MIPS conventions (use of argument registers, return value register, save registers, etc). Look over the code and try to understand what it does. Then answer the five questions (A-E) that follow the code at the bottom of the file. You should answer the questions in order given.

Problem 5 (hw4q5.s)

Write the following VectorSum function as a MIPS procedure call:

struct vector {
    int x;
    int y;
};

void VectorSum(struct vector* vp, struct vector** vectors, int len) {
       ...
}

The function VectorSum takes an array of pointers to struct vector and calculates the sum of all vectors. The sum of two vectors (x1,y1) and (x2,y2) is simply (x1+x2, y1+y2). The resulting vector should be stored in the struct vector pointed to by vp.

You can assume the integer x is stored at lower memory address than y. Therefore, if the address of a struct vector is at 0x50000, than the member x is located at 0x50000, and the member y is located at 0x50004.

Save your answer to a file named hw4q5.s.