CS61C Fall 2012 Lab 6:  More MIPS Assembly

Goals

These exercises are intended to give you more practice with function calling—in particular, calling conventions and stack manipulation.

Setup

Pull the contents of ~cs61c/labs/fa12/06.

 

$ cd ~/work 

$ git pull ~cs61c/labs/fa12/06 master

 

Running Assembly programs

For this lab we will be running our code in MARS, a MIPS simulator which provides a rich debugging GUI, rather than trying to run on bare hardware. Assembly programmers often prefer this mode of development, as it is far easier to debug and work with the code interactively.

To run the program remotely, you may either run via an instructional server (but not one of the Macs), or through a local installation. You can invoke MARS with the following command:

 

$ mars &

 

To run MARS on your own computer, you can download Mars.jar at this link. To run it, simply open a command line, navigate to the directory containing Mars.jar and run java -jar Mars.jar . Of course, this will only work if you have java installed properly.

 

If you are coding your .s file on the (non-Mac) instructional computers with no intent of running it, please don’t use the MARS editor.  Use another (non-graphical) editor such as emacs or vi so that we don't overwhelm these aging servers.

 

After starting MARS, you can load your .s file using File->Open. You can edit your code by clicking the "Edit" tab and run or debug your program by clicking the "Execute" tab. In order to be able to execute your program, you must assemble the code first using Run->Assemble (F3).

To debug your assembly code in MARS you can set breakpoints, step through instructions one by one, view what are in your registers or in memory, as well as initialize values in registers before your program starts.

Exercise 1

This exercise uses the file reduce.s. In this exercise, you will complete an implementation of the reduce function in MIPS assembly.

 

For each node in a singly-linked list, reduce calls a user-specified function to combine the value of a node with the total value up to that point. When it reaches the end of the list, it returns the result of combining all the values in the list. reduce takes three parameters.  The first is a pointer to the head node of a singly-linked list whose values are 32-bit integers. In C, the structure would be defined as

 

typedef struct node
{
 int value;
 struct node* next;
} node;

 

The second parameter is the base value for the reduce. For example, if you are summing a list, your base value would be 0, but if you're instead multiplying each element in a list together, you would want your base value to be 1.

 

The third parameter is a pointer to a user-specified function that takes two ints as an argument and returns an int. We'll use the jalr instruction (which we discuss below) to call this function on the list node values.

 

Our reduce function will recursively go down the list, applying the function to each value of the list nodes, storing the value returned in that node. In C, this would be something like this:

 

int reduce(node* head, int base, int (*f)(int, int))
{
 if (head == NULL)
   return base;


 reduce(head->next,f(base,head->value), f);
}

 

If you haven't seen the int (*f)(int, int) syntax before, it means that f is a pointer to a function.  The function to which f points has return type int and accepts two int arguments.  In C, a function pointer can be called like any other function.

 

You'll need to use an instruction you might not yet have seen: jalr. jalr is to jr as jal is to j. It jumps to the address in the given register and stores the return address (i.e., PC+4) in $ra. For example, the following code sequence is equivalent to jal garply:

 

# I want to call the function garply, but not use jal.
la $t0, garply # use la to load the address of garply into register $t0
jalr $t0       # and then use jalr to jump and link to it.

 

There are 8 places (6 in reduce and 2 in main) in the provided code where it says "YOUR_INSTRUCTION_HERE". Replace these with instructions that perform as indicated in the comments to finish the implementation of reduce, and to provide sample calls to reduce with add, and then multiply, as the function argument. When you've filled in these instructions, running the code should provide you with the following output:

 

Test one:

List: 9 8 7 6 5 4 3 2 1

Result: 45

 

Test two:

List: 9 8 7 6 5 4 3 2 1

Result: 362880

 

Exercise 2

Add the prologue and epilogue (i.e., the code to save and restore registers, manipulate the stack pointer, and return to the caller) to the code in nchoosek.s so that it computes "n choose k". the number of combinations of n distinct elements taken k at a time. (This is also the (n,k) entry in Pascal's triangle.)

 

Show your test run to your TA for checkoff.