MIPS Procedures

Overview

You will continue practicing encapsulating sequences of instructions into callable, reusable sequences (procedures) that use the stack and respect conventions. You will also begin to use MIPS to operate on arrays and strings.

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.

Broader MIPS Background

Before we proceed, we will unpack a few additional bits of syntax and semantics it is helpful to understand.

Directives

The previous assignment introduced the notion directives as special indications to the MIPS assembler. This assignment re-introduces a few additional directives to support arrays, which must appear in the data section (as indicated by the .data directive) of the program.

.word

Within the data section, followed by a label, reserves and initializes word-aligned, comma-separated blocks of data. For example, if you declared the following global variable in C,

int [] sloane211 = {4, 3, 5, 6, 9, 13, 20, 31, 49};

then you might end up with the following MIPS assembly line

sloane211: .word 4, 3, 5, 6, 9, 13, 20, 31, 49
A single global variable (rather than an array) would also be indicated the same way (though with only a single value, rather than a comma-separated list). Note that just as in C, there is no data explicitly indicating to the programmer the number of data items; a separate “variable” must be used or it must somehow be known by the program (i.e., hard-coded).
.byte
Similar to word, except that a sequence of bytes are specified. (Note they will be stored within words according to the endian-ness of the particular platform.) To load a single byte from memory (rather than a whole word) from an address, you would use either lb (load byte) or lbu (load byte unsigned), depending on the contextual need.
.asciiz

Within a data section, followed by a label, reserves space for and initializes a null-terminated ASCII string of bytes. For example,

message: .asciiz "Hello, world!"
Note in particular that on a little endian machine like MARS, the words in memory would be displayed as
Byte 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0
Value l l e H w , o d l r o □ □ ␀ !

{:.table.table-bordered.table-nonfluid}

To place the address of a label into a register (i.e., for issuing a load or store command), you must use the la (load address) instruction. For example,

la $t0, sloane211  # Set $t0 to &sloane211[0] (address of the array's start)
lw $t1,0($t0)      # Dereference the pointer, i.e., put sloane211[0] into $t1

System Calls

Certain privileged or specialized operations on microprocessors are often accomplished by system calls. Toward the end of the term, we’ll revisit how those are implemented in hardware, but all you need to understand for now is that when a system call is invoked, control of the processor is transferred to a special program that enjoys certain elevated hardware permissions. When that special code concludes, control typically returns to your program just after the system call.

System calls in MIPS work by placing a specific integer (indicating the particular function) into the register $v0 and then invoking the syscall instruction.

For example, to terminate your program’s execution, you would invoke system call 10 as follows:

li $v0, 10  # Place the "exit" system call code in the appropriate register
syscall     # Invoke the system call
# No further instructions are reached or executed

Some system calls take arguments (in addition to specifying which specific system call is desired). To print a null-terminated string to the output terminal, one gives the address of the first byte of the string in argument register $a0. For example, if the string message were declared as above, you could print it in MIPS as follows anywhere in a text (program) region.

la $a0, message # Load the address of message into the argument register
li $v0, 4       # "Print string" system call
syscall
# Instructions here would continue executing after the printing has completed

For the curious, the MARS documentation gives the complete list of MIPS and MARS-specific system calls available in the MARS simulator.

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:

    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. A test suite will be used to validate your problem’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

    1. providing documentation for each procedure that indicates its purpose, parameters (with any preconditions), and return values or postconditions,
    2. ensuring comments clearly indicate the purpose of each instruction (or short set of instructions), rather than the literal interpretation, AND
    3. nicely aligning the various labels, fields, and comments in your code.

  6. Do not modify the existing .globl directives; the labels for your procedures are required to be global for them to be discoverable by the autograder. Moreover, do not add your main to the list of global labels; it will conflict with the autograder’s main.

Problems

Problem 1: The Remains of the Day

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

  1. 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.

  2. Create 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 considered tail recursion when you (necessarily) use 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 C expression m % n.

Problem 3: 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 4: 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.

Copyright © 2019, 2020, 2022 Jerod Weinman

CC-BY-NC-SA This work is licensed under a Creative Commons Attribution NonCommercial ShareAlike 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/4.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.