CSE logo University of Washington Computer Science & Engineering
 CSE 410 Computer Systems - Homework 2 - Spring 2009
  CSE Home   About Us    Search    Contact Info 

Due: Thursday, April 16, at 11 pm.

This assignment is intended to give you practice with the MIPS instruction set and the SPIM simulator for runing programs.

Part I. Written Questions

  1. Write a sequence of MIPS instructions corresponding to each of the following C (or Java) statements. You should assume that the variables are stored in registers as follows: x is in $t3, y is in $s2, the base address of the array d is in $a1, and i is in $a0. You may use any other registers you wish in your code for calculated values.
    1. x = x+y;
    2. d[3] = d[i]-y;

  2. Here is a snippet of MIPS assembly code: 
      start: beq   $s1, $s2, exit
         add   $t0, $s2, $s2
         add   $t0, $t0, $t0
         add   $t0, $t0, $s0
         lw    $t1, 0($t0)
         add   $t1, $t1, $t1
         sw    $t1, 0($t0)
         addi  $s2, $s2, 1
         j     start
  exit:
    We'd like to trace this code and discover what the program does. To organize the trace, here is a table showing the contents of part of memory right before execution begins.

    Address Initial
    contents    		 First time at
    "j start"    		 Second time at
    "j start"    		 ...
    400 11
    404 23
    408 63
    412 128
    416 911

    Here is a second table showing initial values of some of the registers right before starting execution. (Initial values for $t0 and $t1 are not shown because they are only used as temporary variables and their initial values do not matter.)

    Register Initial
    contents    		 First time at
    "j start"    		 Second time at
    "j start"    		 ...
    $s0 400
    $s1 5
    $s2 0
    $t0 N/A
    $t1 N/A

    Trace through the MIPS code above. Each time you reach the "j start" line, write down the contents of addresses 400-416 and registers $s0, $s1, $s2, $t0 and $t1 by filling in the tables above (you might need to add more columns to the tables). In one sentence describe what this program does.

Part II. Program Reading (and a little tinkering)

Download the file fibonacci.s and open it up in SPIM. Use SPIM to analyze the program and answer the following questions.

  1. What instructions replace the pseudo-instructions move and li when the code is stored in memory? What happens to the load address instruction la $a0,newline, and why?
  2. Before the program reaches main, it executes several instructions that initialize the stack pointers and argument pointers. These are inserted automatically by SPIM. The program then jumps to the beginning of main with the jal instruction at location 0x00400014. What happens to R31 ($ra) after this instruction is executed? What is the significance of this value?
  3. How many times does the program execute the section of code labeled loop?
  4. When the program terminates, what values are stored in the following registers? (Give your answers in hexadecimal)
    1. R8 (t0)
    2. R19 (s3)
    3. R16 (s0)
    4. R17 (s1)
  5. Modify the program so that each iteration of the loop only executes one branch statement instead of two. Put a comment that begins with the note #CHANGED to the right of each line of code that you change to do this. Run your new code in SPIM to ensure that it produces the same results as the original version. Save this file to turn in with the rest of this assignment.

Part III. A Little Programming

Download the file strlen.s and open it up in SPIM. This program contains a main program, a function to print an integer and a string, and the skeleton of a strlen function that is supposed to calculate the length of a zero-terminated string (like the ones created by the .asciiz assembler pseudo-instruction). Function strlen is not implemented at the moment and currently returns the value -1 when it is called.

For this part of the assignment, modify this file as follows:

  1. Implement strlen so that it returns in $v0 the number of characters in the zero-terminated string whose address is given in argument register $a0. As with the C library function strlen, the result should not count the null (zero) byte that terminates the string, so strlen of "abc" should return 3.
  2. Modify the main program so that it tests strlen by calculating the lengths of three different strings and printing the strings and their lengths by calling prstr.

Note: The functions in this code do not use the full MIPS calling conventions for procedures as discussed in class. In fact, they do not use the stack or have stack frames. Instead, all variables are global, arguments and results are passed in registers as described in the comments, and registers are used as needed in the code.

Hint: There is a discussion of string functions and an example of a string copy function in sec. 2.9 of the textbook. You may find that to be a useful source of ideas, but don't feel that you have to use the code you find there or write your code the same way if it doesn't fit your solution.

Turn-in Instructions: Use the turn-in drop box link on the main course web page to submit your assignment. This should include a text file with the answer to the written questions, a separate file fibonacci.s containing your modified code from part II and a third file strlen.s containing your modified code from part III. You can use any common file format for the written answers, including plain text, word, or pdf. If you wish, you could also scan in a hand-written solution and submit that, but if you do that, please be sure your handwriting is neat and legible. Please be sure to include your name at the top of each of the files you turn in.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Hal Perkins]