CS61C Spring 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

Copy the contents of ~cs61c/labs/sp12/06 to a suitable location in your home directory:

 

$ cp -r ~cs61c/labs/sp12/06/ lab06

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 listmanips.s. In this exercise, you will complete an implementation of the map function in MIPS assembly.

 

For each node in a singly-linked list, map calls a user-specified function with the value of the node, then sets the value of the node to the function’s return value.  map takes two 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 a pointer to a user-specified function that takes an int 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 map 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:

 

void map(node* head, int (*f)(int))
{
 if (head == NULL)
   return;

 head->value = f(head->value);
 map(head->next,f);
}

 

If you haven't seen the int (*f)(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 one int argument.  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 map 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 map, and to provide a sample call to map with square as the function argument. When you've filled in these instructions, running the code should provide you with the following output:

 

Test one:

List before: 9 8 7 6 5 4 3 2 1 0

List after: 81 64 49 36 25 16 9 4 1 0

 

Test two:

List before: 81 64 49 36 25 16 9 4 1 0

List after: 162 128 98 72 50 32 18 8 2 0

 

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.