Lab: MIPS Procedures

Assigned

• November 19, 2020

Due

• November 24, 2020 by 8:00am Grinnell time

Collaboration

Complete this lab with your randomly-assigned group. You may ask the instructor or class mentor for help, but you should not discuss your work with students in other groups.

Overview

Background

Now that you have learned how to support procedures in MIPS, we will practice encapsulating these sequences of instructions into callable, reusable sequences that use the stack and respect convention.

Preparation

To easily simulate MIPS code in software, we will once again use the MIPS Assembly and Runtime Simulator MARS.

To launch MARS on the MathLAN, you can type

java -jar /home/weinman/shared/Mars4_5.jar

In addition, you may also copy the JAR (Java ARchive) file from that location to your own computer and run it there, using a similar invocation of Java.

1. Download the starter file mips-procedures.asm

2. Open the file in MARS.

3. To assemble your code, click “Assemble” under the Run menu (or the Screwdriver and Wrench icon in the toolbar).

4. You can step through your code line by line with the F7 key (or the green and white arrow button with a “1”), but this is tedious. A better way is to switch to the “Execute” pane, which shows your assembled code (along with the actual instructions, the machine version, and its address in the virtual machine). The left-most column allows you to set any breakpoints at which you may want to investigate behavior. If you just want to run the whole test program, the nop at the end of main is good point at which to stop. Other points may arise as you wish to diagnose certain behaviors.

Grading Guidelines

1. Note that the MARS simulator does not enable simulation of the branch/jump delay by default. Do not enable it; branch delays will not be activated during grading for correctness, so your program would likely fail many tests, leading to a poor grade.

2. The only pseudoinstructions you may use for completing the problems in this assignment are:
   • move
   • nop
   • li
   • beqz and bnez

   In particular, you may NOT use ble, blt, etc.

3. Your procedures must follow all MIPS calling conventions (see Figures 2.11, 2.12, and 2.14).

4. Your grade on each procedure will depend on its correctness. I will use a test suite to validate each procedure’s correctness; the grade for each problem will be determined by how many tests each problem passes.

5. In addition to being graded on correctness, your code will be evaluated on its clarity, organization, and overall efficiency with respect to the number of instructions required to complete any given task. In part that means i. ensuring comments clearly indicate the purpose of each instruction (or short set of instructions), rather than the literal interpretation, AND ii. nicely aligning the various labels, fields, and comments in your code.

Problems

Problem 1: Going to Extremes

Write a procedure called extremes that takes four 32-bit signed integers in registers $a0, $a1, $a2, and $a3 and returns the smallest of the four values in register $v0 and the largest of the four values in $v1. In addition to correctness, which is paramount, your procedure will be graded in part on its efficiency. (Hint: Think about how you would put four items in order with a routine in C that used a minimum number of comparisons.)

Problem 2: The Remains of the Day

Branching gets more interesting when loops are involved.

Translate the following C procedure into MIPS to calculate the remainder of two 32-bit integers. We can consider them signed, but they should be positive.

// Repeatedly subtract (that's division after all) until we find the remainder
int
remainder (int a, int b) {
  while (a>=b)
    a = a-b;
  return a;
} // remainder

You may discover that MIPS has a rem pseudoinstruction to do just this, but for now we’re practicing the translation process. (You can certainly use rem in your testing, but your procedure should not use it or the div instruction upon which it is built.)

Problem 3: Who is the Greatest?

Euclid’s algorithm for finding the greatest common divisor between two numbers can be elegantly expressed recursively as follows:

int
gcd(int m, int n) {
  if (n==0)
    return m;
  else
    return gcd(n, remainder(m,n));
} // gcd

a. Translate this recursive function into MIPS “as is”, being sure to follow all the MIPS calling conventions. That is, you should use the stack and jal instructions to accomplish the recursion. Your MIPS gcd must call your remainder procedure, rather than use the rem pseudoinstruction.

b. Update another version of the function in MIPS that uses tail recursion to accomplish the iteration (i.e., the repeated call to the same function). Call this version gcdtail. Although it is still tail recursion when you use (necessarily) the stack for a call to a helper procedure like remainder, we instead will simplify your task here by allowing you to use the rem pseudoinstruction, which has the following syntax

rem rd, rs, rt

and is roughly equivalent to the C expression rd = rs % rt. Thus your code should be a tail recursive adaptation where the call remainder(m,n) is replaced by the simpler expression m % n.

Problem 4: What’s the Frequency, Kenneth?

Write a procedure in MIPS called count that has the following signature and returns the frequency of the value k in the array of n items starting at p.

int count (int * p, int n, int k)

In addition to being correct, your procedure should use pointer arithmetic to be as efficient as possible (running in as few instructions as possible).

Problem 5: Reversal of Fortune

Write a procedure reverse in MIPS that takes a pointer to a null-terminated string and reverses that string “in place.” (That is, no other memory addresses should be used). The C signature would be

void reverse (char* s)

Note: Within your procedure you will need to determine the length of the given string; there is no need to write a separate helper procedure formally.