CS61C $ummer 2017 Lab 3 - MIPS Assembly on an Adjacent Planet (not Venus)

HEY THERE, LAB 3er. Welcome to lab 3. Project 1 got you down? It's okay! You've still got some time. Remember that my ancestors lab 2 and lab 1 introduced tools to you called CGDB and Valgrind, which are there to help you. And if worst comes to worst, you still have three slip days to use. We believe in you!

Goals

Setup

Copy the lab files from the instructional servers to your lab account with

$ cp -r ~cs61c/labs/03/ ~/labs/03/

Alternatively, secure-copy (scp) them from the instructional servers to your own laptop with

$ scp -r cs61c-xxx@hive10.cs.berkeley.edu:~cs61c/labs/03/ ~/YOUR_FILEPATH

And if you want to secure-copy them back to your class account:

$ scp -r ~/YOUR_FILEPATH/03 cs61c-xxx@hive10.cs.berkeley.edu:~/YOUR_LABACCT_FILEPATH

Intro to Assembly with MARS

The following exercises use a MIPS simulator called MARS, which provides a rich debugging GUI. You can run MARS on your home computer by downloading the jar file from the Internet or by copying it from ~cs61c/bin/Mars4_5.jar on the instructional machines. NOTE: You will need Java J2SE 1.5.0 (or later) SDK installed on your computer, which can be obtained from Sun. If your home computer is a Mac, you can also follow the instructions here to install MARS as an app in one step (thanks to Sagar, a former TA).

To avoid all of this installation, I really really really really really recommend that you just use a lab machine to do the lab, and if there aren't enough, find someone who is working alone and partner up with him or her. Really.

You can run MARS in lab by typing 'java -jar ~cs61c/bin/Mars4_5.jar' at the command line. To run the program remotely, you may either run via an instructional server (but NOT one of the Orchard machines), or through a local installation (recommended). When on an instructional server, you will need to be running an X-Server (like XMing), and enabling X11 tunneling. But honestly, just don't run it remotely. See below for some words on why.

Tip: Although it is possible, you should avoid running MARS remotely at all costs - it will be painfully slow to use and will overwhelm the servers if many students attempt to do so. It is in your best interest to setup/run a local copy of MARS.

Assembly Basics:

Exercises

Exercise 1: Familiarizing yourself with MARS

Getting started:

  1. Run MARS. Reread the section about half a screen upwards if you missed how to.
  2. Load lab3_ex1.s using File-->Open.
  3. View and edit your code in the "Edit" tab. Notice the code highlighting and 'completion suggestion' features.
  4. When ready, assemble your code using Run-->Assemble (or press F3).
  5. This will take you automatically to the "Execute" tab, which is where you can run and debug your program.
  6. Step through the program using Run-->Step (or press F7).
  7. You should take the time to familiarize yourself with everything in the Run menu (and the keyboard shortcuts).

For this exercise, we calculate the Fibonacci numbers using fib[0] = 0; fib[1] = 1; fib[n] = fib[n-1] + fib[n-2].
Task: Follow the steps below and record your answers to the questions. The Help menu (F1) may come in handy.

  1. What do the .data, .word, .text directives mean (i.e. what do you use them for)? Hint: think about the 4 sections of memory. Hint2: Today's lecture (6/29) slides.
  2. How do you set a breakpoint in MARS? Set a breakpoint on line 14 and run to it. What is the instruction address? Has line 14 executed yet? ARE YOU SURE?
  3. Once at a breakpoint, how do you continue to execute your code? How do you step through your code? Run the code to completion.
  4. Find the "Run I/O" window. What number did the program output? If 0 is the 0th fib number, which fib number is this? How did you get that answer without looking up the list of Fibonacci numbers (AKA just by looking at the code)?
  5. At what address is n stored in memory? Hint: Look at the box titled "Data Segment."
  6. The next two tasks will take away your rights again. Throwback to set_bit, am I right? (sorry :///)
  7. Without using the "Edit" tab, have the program calculate the 13th fib number (0-indexed) by manually modifying this memory location before execution (but after assembling). You may find it helpful to uncheck the "Hexadecimal Values" box at the bottom of the Data Segment.
  8. How do you view and modify the contents of a register? Reset the simulation (Run-->Reset or F12) and now calculate the 13th fib number by (1) breaking at a well-chosen spot, (2) modifying a single register, and then (3) unsetting the breakpoint. We suggest breaking right after n gets loaded into a register.
  9. Lines 19 and 21 use the syscall instruction. How does syscall work in general and specifically what do syscall 1 and syscall 10 do? Hint: Look in Help.

Checkoff [1/4]

Exercise 2: Compiling from C to MIPS

For this exercise we need to use a program called mips-gcc (a cross-compiler for MIPS) that allows us to compile programs for the MIPS architecture on our x86 machines. AT THIS POINT, if you are doing this lab remotely, you should SSH into one of the hive machines.

Compile The file lab3_ex2.c into MIPS code using the command:

$ mips-gcc -S -O2 -fno-delayed-branch -I/usr/include lab3_ex2.c -o lab3_ex2.s

Whew, what a stacked command. The -O2 option (capital letter "O" and 2) turns on a level of optimization. The -S option generates assembly code. Don't worry about the delayed branch option for now; we will revisit this topic again when we talk about pipelining. The above command should generate assembly language output for the C code. Please note that you will NOT be able to run this code through MARS.

Task: Look at the C code. Now find the assembly code for the loop that copies source's values to destination's values. Then find where the source and dest pointers you see in lab3_ex2.c are originally stored in the assembly file. Finally, explain how these pointers are manipulated through the loop.

HUGE hint: Try to understand what is going on starting at the main label first. In particular, you should be able to answer the following questions: Please note that %hi(x) means the upper 16 bits of x and %lo(x) means the lower 16 bits of x.

Hopefully, the answers to these questions, along with the information that $2 is acting as an index/offset, should help you understand what goes on in the rest of the code.

Checkoff [2/4]

Exercise 3: MIPS function calling with map

This exercise uses the file listmanips.s.

In this exercise, you will complete an implementation of map in MIPS. Our function will be simplified to mutate the list in-place, rather than creating and returning a new list with the modified values.

Our map procedure will take two parameters; the first parameter will be the address of the head node of a singly-linked list whose values are 32-bit integers. So, in C, the structure would be defined as: 

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

Our second parameter will be the address of a function that takes one int as an argument and returns an int. We'll use jalr (see 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(struct node *head, int (*f)(int))
{
  if(!head) { return; }
  head->value = f(head->value);
  map(head->next,f);
}

If you haven't seen the int (*f)(int) kind of declaration before, don't worry too much about it. Basically it means that f is a pointer to a function, which in C is used exactly like any other function.

You'll need to use an instruction you might not have learned before to implement this: jalr. jalr is to jr as jal is to j. It jumps to the address in the given register and stores the address of the next instruction (i.e., PC+4) in $ra. So, if I didn't want to use jal, I could use jalr to call a function like this: 

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

There are exactly seven (7) places (6 in map and 1 in main) in the provided code where it says "YOUR_INSTRUCTION_HERE".

Task: 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: 

List Before: 9 8 7 6 5 4 3 2 1 0
List After: 81 64 49 36 25 16 9 4 1 0

Checkoff [3/4]

Exercise 3.5 - set_bit version 2

Now we're going to implement set_bit without the use of bitwise operators, local variables, semicolons, a computer, and indoor plumbing, silently, while blindfolded. I'm just kidding.

Checkoff [3.5/4]

Exercise 4 - Writing function prologues and epilogues

The reason why we call them the prologue and epilogue isn't just because they're lines of code that come before and after the meat of the function. It's because the function itself is an awe-inspiring story. Think about it: every function you write starts out with nothing but the $a0-3 registers, and you have to take them through a long journey of instructions that finally mould them into the desired result: what you save in the $v0-1 registers. Likewise, you are going through a similar journey in your own life. I hope that the stuff you do today will shape you to become a better person.

So basically, you are writing a story in MIPS while you are going through your own story in real life. That's a recursive function call. Speaking of which.

Task: add the prologue and epilogue 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 can be computed through factorials, however we will be computing this through finding the (n,k) entry in Pascal's triangle. Well...we already did. You don't have to compute this. You just have to write the prologue and epilogue. Remember, this function utilizes a recursive definition which is stated in the code. That means our function makes more function calls. What do you have to save on the stack if your function makes further function calls???

Checkoff [4/4]