EE 361 Homework 4

Due Date: 9/19/02 (friday)

Assignment:

Problem 1. (2 pts) Consider the following C functions:

/*  Returns the minimum value of array a[], which has length "length" */
minarry(int a[], int length)
{  int i, k;
   k = a[0];
   for (i=0; i<length; i++) k = min(k,a[i]);
   return(k);
}

min(int i, int j)
{ if (i < j) return(i);
  else return(j);
}

Write a MIPS assembly language implementation of the functions. You may assume that parameters are passed to the functions through registers $a0 and $a1, where $a0 is the first parameter and $a1 is the second. You may use $t0-$t9 for temporary storage, as well as the stack. Also assume that all return parameters are passed through $2.

Problem 2. (1 pt) Consider the following machine code of a program that starts at memory location 16. Disassemble the code giving an assembly language equivalent, complete with labels (you may use whatever names you want for your labels, e.g., "Skip:", "Loop:"). Note that the machine code is in "decimal representation", which shows the decimal values of each field.

    +-----+-----+-----+-----+-----+-----+
    |  8  |  0  |  3  |       4         |
    +-----+-----+-----+-----+-----+-----+
    |  5  |  0  |  3  |       3         |
    +-----+-----+-----+-----+-----+-----+
    |  0  |  2  |  3  |  1  |  0  | 34  |
    +-----+-----+-----+-----+-----+-----+
    |  8  |  3  |  3  |       -1        |
    +-----+-----+-----+-----+-----+-----+
    |  2  |           5                 |
    +-----+-----+-----+-----+-----+-----+

Problem 3. (2 pts) For this part, you will be introduced to the MIPS simulator SPIM. The simulator will allow you to run MIPS assembly language programs. For additional reading, there is Appendix A.9 (page A-38 to A-49) which you can read if the following assignment is confusing. You may also go over Appendix A.10 which describes the MIPS assembly language. This goes into detail about different instructions, pseudo instructions, and assembler directives. Note that there are three questions to answer at the end.

The SPIM simulator is available on spectra and wiliki. There is also a free PC version that you can download   I believe the PC version is called PCSpim.. If you don't have your own computer, the PC version is available on the EE PC Server on the PCs in Holmes 486.  It will be in the folder labeled "spim".

The following instructions are for SPIM on spectra and wiliki (it's calle xspim).  The operation of PCSpim should be similar but the format may not be the same.  For example, instead of buttons, there may be pull-down menu options.  Also instead of "loading" a assembly language file, you "open" it.

The following are preliminaries before running spim on wiliki or spectra (which you can skip if you are using PCSpim)

Before running spin on wiliki or spectra, make sure you have the correct path to xspim, which is in the ~ee361/bin.  Your .cshrc file should have the following line somewhere:

set path=($path  ~ee361/bin)

If you just entered it into your .cshrc file then you must restart by logging out and relogging in.

Now we can start.  On spectra and wiliki, you can invoke SPIM by typing:

xspim

A window will pop up, as shown below. Now if the you are running the simulator remotely then you'll have to direct the output of SPIM to your terminal. For example, suppose you're in the College of Engineering computer room, and you're at workstation "wailana". Then you can open a window, and telnet to wiliki. You should let wiliki know that you want the output of xspim to go to wailana. So you type at wiliki

setenv DISPLAY wailana:0.0

This will direct the output of wiliki to wailana. Next you have to prepare "wailana" to accept the output from wiliki (and to subsequently display it). So at "wailana", you type

xhost +

This tells wailana that anything that comes from the network should be displayed on the screen. To be more discriminating, you can type instead

xhost +wiliki

Once you have xspim (or PCSpim) going, you should have the following display.  (In the case of the xspim, it will be displayed on "wailana".)

Now notice that the window has five panels.

1. Register Display: This displays all the registers in the MIPs microprocessor. Note that the general registers $0-$31 are shown as R0-R31. The registers are updated whenever your program stops running.
2. Control Buttons: These buttons are used to control the simulator. These buttons will be discussed in greater detail later.
3. Text Segments: This displays instructions of your program. This will also be discussed in more detail below.
4. Data Segments: This shows the data stored in memory. For this homework, this panel is not important. However, it is important for most programs.
5. SPIM messages: This displays all error messages for SPIM. If your program has syntax errors, it will show up here after your program has been loaded.

Text Segment This shows the instructions of your program. An example line in this panel is

[0x00400000]    0x8fa40000   lw   $4,0($29)    ;   89:  lw  $a0,0($sp)

• [0x00400000] is the memory address of the instruction. The address is encoded in hexadecimal. Here the "0x" prefix means that the number is a hexadecimal number.  Recall that a hexadecimal number has a base of 16, and the digits are 0, 1, 2, ...., 9, a, b, c, d, e, f, where a = 10, b = 11, ..., f = 15.  Hexadecimal numbers are convenient for representing binary numbers.  Recall that to convert a binary number to hexadecimal, partition the binary number into chunks of four bits starting from the right.  Then convert each chunk to a hexadecimal digit.  For example, consider the binary number 10010101011111.  After partitioning, we get 10  0101  0101  1111.  Then we can translate each chunk into a hexadecimal digit:  2 5 5 f.
• 0x8fa40000 is the 32-bit word machine code for the instruction.
• lw $4,0($29) is the instruction's description in MIPS assembly language. This is called a mneumonic, which means it's a way of writing the instruction to make it easy to recognize and remember.
• 89: lw $a0,0($sp) is the actual line from your assembly-language program file that produced the instruction. The number "89" is the line number in that file.

Control Buttons

• load: This will load an assembly language program.
• run: This will run the program. To stop the run, have the cursor somewhere over xspim's window and then type control-C.
• set value: This can set values of registers and memory cells.
• step: This is useful for debugging. It allows you to execute one instruction of the program at a time. This way you can carefully check how instructions are executed, including how memory cell values change. It also allows you to execute multiple instructions at a time.
• breakpt: This is useful for debugging. A breakpoint is is like a "flag" for an instruction. When a breakpoint is set for an instruction, then the simulator will stop running right before it executes the instruction. So we can set breakpoints at instructions where we would like to examine the contents of registers and memory cells.
• clear: This will clear memory and registers. It's useful when you reload a program, and you'd like to run the program with all registers initialized to zero.

Let's run an assembly language program.

Loading an example program. First, download the following program from the web, by clicking here and saving the file as test2.s.

#
#  This program multiplies $20 and $21, and puts the product in $22.
#
main:	
	move	$22,$0		# This initializes $22 to zero.
	move	$23,$20		# $23 is a temp. reg., used as a counter.
loop:	
	beq	$0,$23,quit	# if the counter is zero, then quit
	add	$22,$22,$21	# $22 = $22 + $21
	addi	$23,$23,-1	# $23 = $23 - 1 (update counter)
				#     Note: "addi" is a new instruction
	j 	loop
quit:
	jr	$31

First Run -- No Frills.

• Use the load control button to load test2.s. Note that the test2.s is loaded at address 0x00400020. The set of instructions that starts from 0x0040000 is some housekeeping to be done before executing to test2.s. These instructions are

                lw $4, 0($29)
                addiu $5, $29, 4
                addiu $6, $5, 4
                sll $2, $4, 2
                addu $6, $6, $2
                jal 0x00400020 [main]
                ori $2, $0, 10
  

• You may not be able to see all of test2.s in the Text Segment Panel (last instruction is jr $31 at address 0x00400038). To make the Panel longer notice that there's a small black box in the lower right corner of the Panel. Put the cursor there. The cursor should now change to an icon having arrows pointing up and down. Click the left mouse button, and use the mouse to make the panel bigger until you see all of the program (it should include the instruction jr $31 at memory location 0x03e00008.
• Initialize $20 and $21 to the values 3 and 4, respectively. using the set value control button. Notice that the changes appear in the Register Display.
• Run the program using the run control button. Note the default address of where to start running is 0x00400000 which is okay because we want to do the "housekeeping"
• When the program stops, check if $22 has the product 3x4 = 12. In hexadecimal this is 0xc.

Second Run -- Single Stepping. This time we will use the single step feature.

• Initialize $20 and $21 to the values 3 and 4 respectively, by using the set value control button. (These registers may be initialized already.)
• Load test2.s using the load control button.
• Step through the instructions using the step control button. Note that every time you click the step button in the prompt window, an instruction is executed. By stepping through the instructions starting from 0x00400004, you can see how the "housekeeping instructions"

                lw $4, 0($29)
                addiu $5, $29, 4
                addiu $6, $5, 4
                sll $2, $4, 2
                addu $6, $6, $2
                jal 0x00400020 [main]
  

  Before the program is executed. Note that the loop of the program is executed three times. Notice that the register values will change as the program is executed.

  The program is completed after the jr $31 instruction is executed, and we jump back to ori $2, $0, 10, which is one of the "housekeeping instructions".

  Notice that we have the option of stepping through multiple instructions. Try this exercise again, but using different step sizes to see what happens.

Third Run -- Breakpoints. This time we will use breakpoints.

• Initialize $20 and $21 to the values 4 and 5, respectively, using the set value button. Check to see that the values are properly loaded into the registers.
• Set a breakpoints at
  • "main:" which is 0x00400020
  • "loop:" which is 0x00400028
  • the instruction ori $2, $0, 10 which is at 0x00400018
  To set breakpoints, simply click the breakpoints button, and add the breakpoint addresses. To check that you entered the right breakpoints, click the breakpoints button, and then click list. The breakpoint addresses will be listed in the bottom panel below "Data Segments".
• Run the program starting at the default address. (Notice the instructions at the breakpoints have been replaced by an instruction break $1 . This is a special instruction recognized by the processor. Whenever the processor executes this instruction it goes to a special location to execute a program. This is called a "software interrupt" and the program is called an "interrupt handler". The interrupt handler determines the proper operation to be executed at the breakpoint, updates register values, etc accordingly.)
• You will hit the breakpoint at "main" which is 0x00400020.
• Continue running the program until you hit the breakpoint at "loop:".
• Question 1. What are the values in the registers $20, $21, $22, and $23?
• Continue running the program until you hit the breakpoint at "loop:" again.
• Question 2. What are the values in the registers $20, $21, $22, and $23?
• Keep continuing until you hit the breakpoint at 0x00400018.
• Question 3. What are the values in the registers $20, $21, $22, and $23?

main()
{
int addall(int n0, int n1, int n2, int n3, int n4, int n5);
int i;

i = addall(10,11,12,13,14,15);
}

addall(int x0, int x1, int x2, int x3, int x4, int x5)
{
return x0+x1+x2+x3+x4+x5;
}

    .file    1 "test4.c"

 # GNU C 2.5.7 [AL 1.1, MM 40] BSD Mips compiled by CC

 # Cc1 defaults:

 # Cc1 arguments (-G value = 8, Cpu = default, ISA = 1):
 # -quiet -dumpbase -O -fno-delayed-branch

gcc2_compiled.:
__gnu_compiled_c:
    .text
    .align    2
    .globl    main

    .loc    1 2
    .ent    main
main:
    .frame    $sp,32,$31        # vars= 0, regs= 1/0, args= 24, extra= 0
    .mask    0x80000000,-8
    .fmask    0x00000000,0
    subu    $sp,$sp,32
    sw    $31,24($sp)
    li    $2,0x0000000e        # 14
    sw    $2,16($sp)
    li    $2,0x0000000f        # 15
    sw    $2,20($sp)
    li    $4,0x0000000a        # 10
    li    $5,0x0000000b        # 11
    li    $6,0x0000000c        # 12
    li    $7,0x0000000d        # 13
    jal    addall
    lw    $31,24($sp)
    addu    $sp,$sp,32
    j    $31
    .end    main
    .align    2
    .globl    addall

    .loc    1 10
    .ent    addall
addall:
    .frame    $sp,0,$31        # vars= 0, regs= 0/0, args= 0, extra= 0
    .mask    0x00000000,0
    .fmask    0x00000000,0
    addu    $2,$4,$5
    addu    $2,$2,$6
    lw    $3,16($sp)
    lw    $8,20($sp)
    addu    $2,$2,$7
    addu    $2,$2,$3
    addu    $2,$2,$8
    j    $31
    .end    addall