Lab 11: MIPS Assembly Programming (Intermediate)

Overview

In this lab, you are going to write a program in MIPS assembly that uses proper function calls and the stack.

Lab - Getting Started

To begin this lab, start by obtaining the necessary boilerplate code.  Enter the class repository:

unix>  cd ~/bitbucket/2016_fall_ecpe170_boilerplate/

Pull the latest version of the repository, and update your local copy of it:

unix>  hg pull
unix>  hg update

Copy the files you want from the class repository to your private repository:
(In this case, it is two folders you want)

unix>  cp -R ~/bitbucket/2016_fall_ecpe170_boilerplate/lab11/* ~/bitbucket/2016_fall_ecpe170/lab11

Enter your private repository now, specifically the lab11 folder:

unix>  cd ~/bitbucket/2016_fall_ecpe170/lab11

Add the new files to version control in your private repository:

unix>  hg add *

Commit the new files in your personal repository, so you can easily go back to the original starter code if necessary

unix>  hg commit -m "Starting Lab 11 with boilerplate code"

Push the new commit to the bitbucket.org website

unix>  hg push

Lab

In this lab, you must convert a C program (provided as boilerplate code) to an equivalent MIPS program in a faithful manner. In other words, if the C code calls a function, your code must also call a function. If the C code prints a string from memory, your program must print a string from memory. If the C code has an array with 100 elements in it to save the result, your code must have an array with 100 elements in it. And so on... (A few exceptions to this general rule are permitted. For example, we don't have a way to do #ifndef/#define statements in assembly, nor do we need to create header files)

Requirements:

• Your MIPS program must faithfully follow the algorithm and organization of the C program
• Your MIPS program must produce character-for-character identical output as the C program
• Your MIPS program must use the procedure call convention described below
• **Each line** of assembly code must be documented with a comment!
• Each region of assembly code must clearly have a **comment block** documenting the overall purpose of that region, along with what values each register holds. You can use your own judgement for a reasonable region size.

The original C program performs recursive quick sort on an array that contains 100 randomly generated elements. For repeatability, the random number generator is initialized (seeded) with the same starting value. Note that the seed may be changed when grading your program. Thus, you should not hardwire specific values in your program, print it to the screen, and call it a day!

Lab Submission:
(1) There is no lab report for this lab.
(2) All source code must be submitted via Mercurial. Place the source files inside the lab11 folder.

Optional Feedback: 
(Feel free to include a text file with comments/feedback on the lab)
(1) How would you suggest improving this lab in future semesters?

Procedure Call Convention

For this lab, we will follow a slightly simplified version of the procedure call convention described in the Hennessy and Patterson textbook, Appendix A. (See the PDF found in the Canvas site, Files section for a full discussion).  As a reminder, recall that the MIPS architecture provides 32 general-purpose registers, numbered 0–31. The subset of registers that will be used during this lab are:

Other registers are reserved for specific functions and are beyond the scope of this lab.

The following calling convention is used whenever one function (the caller) calls another function (the callee).  The process is as follows:

Immediately before the caller invokes the callee, the caller function must do the following:

1. Place the arguments to the callee function in the standard location (registers $a0-$a3)
2. Decide if any of the caller-saved registers ($a0-$a3 and $t0-t9) need to be used after the function call.  If so, those values must be saved onto the stack now, and restored after the function call.
3. Execute a jal instruction which jumps to the callee's first instruction and saves the return address in register $ra

At the beginning of the callee function (before execution):

1. Save callee-saved registers ($s0 - $s7 and $ra) onto the stack, adjusting the stack pointer at the same time. These registers must be saved before altering them since the caller expects to find these registers unchanged after the call.
   Note: Register $ra only needs to be saved if the callee itself makes a call. 
   Note: Registers $s0 - $s7 only need to be saved if they are modified in the callee

At the end of the callee function (after execution):

1. If the callee is a function that returns a value, place the returned value in register(s) $v0-$v1.
2. Restore all callee-saved registers from the stack in reverse order, adjusting the stack pointer at the same time
3. Return to the caller function by jumping to the address in register $ra. 

Random Number Generation

There is no "C Standard Library" in MIPS.  The simulator provides analogous functions for printf() and scanf(), but nothing to generate random numbers.  This snippet code of C code from Wikipedia provides an acceptable random number generator and is used in the boilerplate C program. Note that it produces a random 32-bit number, so if you want a random number in a smaller range, use modular division afterwards. The m_w and m_z variables should be global, or at least persist after the function finishes. (Otherwise, the random number generator will always produce the same output).

m_w = <choose-initializer>;    /* must not be zero */
m_z = <choose-initializer>; /* must not be zero */

uint32_t get_random()
{
  m_z = 36969 * (m_z & 65535) + (m_z >> 16);
  m_w = 18000 * (m_w & 65535) + (m_w >> 16);
  return (m_z << 16) + m_w; /* 32-bit result */
}

Resources

The MIPS Instruction Set and MIPS Example Programs will be very useful in this project.  Don't forget about the H&P Appendix A PDF in Sakai!  (It shows the full list of branch instructions)