Monash University > School of Computer Science and Software Engineering > CSE1303 > Part B > Pracs > Prac B4

CSE1303 Computer Science
Semester 3 (summer), 2002
Part B
Prac B4

This prac covers material from lectures B01 to B11 and relates to material in Tutorial B4.

Background

For Questions 1 and 2 you will be using SPIM, a freely available MIPS R2000 simulator.

For Question 3 you will be making changes to a C program to make it generate MIPS code for arbitrary arithmetic expressions. A program like this might be one component of a compiler.

Preparation (3 marks)

The marks for Preparation will be awarded only if the preparation is completed before the start of the class.
Even if you do not get the marks for preparation, you will need to complete it before going on with the regular questions, because they will refer to its answers.

Try to work through as much of Question 1 as you can.
Draw a stack diagram for Question 2.
Write as much of the MIPS code for Question 2 as you can.
Review the question "Arithmetic" in tutorial B4.
Download, compile and run the program in Question 3 below.

Question 1 (2 marks)

This question assumes that you are using the Unix version of SPIM. If you are using the Windows version, you will find some things to be slightly different.

Type in the following program and save it into the file try.s:

        .data
n:      .space 4
prom:   .asciiz "Type a number: "
res:    .asciiz "Result is: "
nl:     .asciiz "\n"

        .text
main:   li $v0, 4     # print str
        la $a0, prom  # at prom
        syscall

        li $v0, 5     # read int
        syscall
        sw $v0, n     # store in n

        li $v0, 4     # print str
        la $a0, res   # at res
        syscall

        li $v0, 1     # print int
        lw $t0, n          # n
        sub $t1, $t0, 1    # n-1
        mul $t0, $t0, $t1  # *
        sra $a0, $t0, 1    # /2
        syscall

        li $v0, 4     # print str
        la $a0, nl    # at nl
        syscall

        li $v0, 10    # exit
        syscall

Starting SPIM

Now start up SPIM with this command:

xspim

(Note that the program spim is the command-line driven version of xspim. The graphical version is easier to use.)

You will see a window, similar to this one, with five panels:

Registers: The top panel displays all of the machine's registers, including the 32 general-purpose registers, as well as special registers such as PC, LO and HI. Also shown are floating-point registers, which are not used in CSE1303. All of these values are displayed in hexadecimal.
Commands: The second panel contains a number of buttons which you can press with the mouse. Most are self-explanatory. For example, to quit SPIM, press quit, then confirm your decision in the pop-up window that appears.
Text segment: The third panel displays the contents of the text segment (i.e., your program). There are a few lines there already when your program begins; this is the code which jumps to your code's main label when you run your program.
There are four columns here. The first shows the addresses of your code in memory. The second shows the actual bit pattern (in hex) of the word that makes up the instruction (i.e., the machine code). The third column contains a disassembly of the machine code, as you did in prac B3. The fourth column contains the actual source code of your program, which occasionally differs from the disassembly in the third column.
Data segment: The fourth panel displays the contents of your program's data segment and stack segment. They are displayed a word at a time, which is not always convenient.
Messages: The bottom panel is where you will find error messages and other information that SPIM thinks that you might like to know. Pay attention to this window, as it can provide a hint if your program doesn't seem to be working as expected.

If there is more information in a panel than can be displayed at once, a scrollbar will appear, which you can drag by pressing the middle mouse button (both buttons at once if you have a two-button mouse).

Loading programs

To run a MIPS program with SPIM, you will first need to load it. Press the load button in the second panel, then type the name of the file (say, try.c) into the popup window. Press assembly file and the file will be loaded.

Watch the message panel at the bottom of the window; if there are any syntax errors in your source code, you will be told about them here.

Assuming your program loaded properly, you can use the scrollbar in the text segment to view your program in memory. Note the line numbers in the fourth column.

While you are debugging your code, you may also like to use the reload button in the command panel, which is equivalent to clear | memory & registers plus load.

Load your program try.s into SPIM now. Fix any typographical errors SPIM finds.

Running Programs

You can run your program by using the run button. Both values in the popup box can be left with their default values, so just press ok.

If the MIPS program performs input or output, a new window will pop up. This is the SPIM console. You can read your program's output here, as well as type any input the program is expecting.

When the program is running, the register panel displays "Running...". If you see this, the program probably wants some input from you. Type it into the SPIM console window.

Run the try.s program now. Give it a number when it asks for one.

If you get a MIPS program into an infinite loop, press control-C. SPIM stops at the currently running instruction. You can examine register values to see what went wrong, or single-step through your code to find the error.

Debugging

Sooner or later you will need to debug MIPS programs. SPIM gives you two ways to debug your program: single stepping and breakpoints.

Single stepping

With single stepping, you run exactly one instruction at a time, then see the results of that instruction. By repeating this, you will eventually work your way through the whole program. Single stepping is helpful if you suspect you are near to the bug.

To step through your program, use the step button on the control panel. This pops up a dialogue box, which will remain there until you close it with the abort command button. Press step and SPIM will run the current instruction. SPIM highlights the current instruction (the one with the same address as PC's contents). As you step through the program, you will see this highlight move down the screen.

Press the continue button to stop single-stepping and run the remainder of the program at normal speed. Press the abort command button to pop down the dialogue box. You can pop it up again by pressing step again.

Breakpoints

If your program is big, single-stepping all the way from the start is not realistic. This is when breakpoints are useful. A breakpoint is an address at which SPIM will always stop running your program. You can set any number of breakpoints at any addresses you like, then run your program from the start. It will run just like normal, until an instruction located at a breakpoint is reached. SPIM then stops your program and gives you the opportunity to examine registers and memory. You can step through your program from that point, or continue running until the next breakpoint or the end of the program.

To set a breakpoint, determine which address you want to break at. You can get this information by examining the text segment panel: the first column is the address, and the fourth column is your source code. Thus, if you want to stop at line 58 of your source code, find line 58 in the fourth column, then read off the address. Enter this address (excluding the square brackets, but including the leading 0x) into the dialogue box that appears when you press the breakpoints button. This breakpoint is remembered until you clear it or reload the program.

Use single-stepping to advance through try.s. Take note of the values of registers and which instructions modify them. Also note the location in the data segment which contains the variable n.

The file b4-try2.s contains a bug. Use a combination of single-stepping and breakpoints to locate the bug and fix it. (Don't just ask a friend where the bug is! The next time you have a bug, your friend might not be around.)

If you ever have a problem with a MIPS program, use the same debugging techniques you already know for C:

Single-step through your code, examining registers and memory
Set a breakpoint to halt the program at a specific instruction
Have your program perform system calls to print helpful messages to the SPIM console (e.g., "In inner loop, i = 45")

Question 2 (2 marks)

Type in and run the following C code:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int num1;
    int num2;
    int average;

    printf("Enter first number: ");
    scanf("%d", &num1);
    printf("Enter second number: ");
    scanf("%d", &num2);

    average = (num1 + num2) / 2;

    printf("Integer average is %d.\n", average);

    exit(0);
}

Translate this C program into MIPS. Make your translation faithful; that is, do not perform optimization on the code.

Test your program in SPIM. Identify the locations on the stack which contain num1, num2 and average.

Question 3 (3 marks)

The following files constitute a C program which reads an infix arithmetic expression from the user, and outputs the equivalent expression in Reverse Polish Notation. (It is similar in function to the shunting algorithm seen in the bonus question for prac A2, but it uses a more sophisticated algorithm.) Download all of these files and place them in one directory.

Compile all of the C files together (using something as simple as

gcc -o b4 b4-*.c

under Unix), and run the program. The program understands the following operations:

+ (addition)
- (subtraction)
* (multiplication)
/ (division)
% (remainder)
= (assignment)
( ) (parentheses)
signed integers
identifiers (names for variables)

Try out the following expressions, and make up some of your own.

1
2 * 3
1 + 2 * 3
2 * 3 + 1
5 * (F - 32) / 9
C = 5 * (F - 32) / 9

Note that it is not necessary for you to understand all of the code in the supplied files. The program uses some concepts which will not be introduced until later in the subject. You will be told which functions you will need to modify (and thus understand). At the end of the subject you will know enough to understand all of this program's code (though perhaps not the theory behind it).

Modify the functions operator, put_ident, get_ident and number in the file b4-codegen.c so that the program prints out MIPS code to evaluate the expression entered. Each of these functions receives as a parameter a string containing the operator, identifier (variable name) or number to be operated on. put_ident is used to store a value in a variable; get_ident is used to fetch a value from a variable.

Assume that identifiers correspond to global variables, defined with matching labels in the MIPS code.

Assume that you have an infinite number of registers $t0, $t1, $t2, etc.

You need only generate the assembly language for the text segment, not the data segment. You need not generate any assembler directives.

When your program works, cut-and-paste its output into a file and try running it with SPIM (after adding necessary assembler directives to the file by hand).

Bonus question (2 bonus marks)

Complete either one of these bonus questions to get two additional bonus marks. (No, you can't get four extra marks by doing them both!)

Bonus Question 1

Modify your answer from Question 3 in some of the following ways:

Add some more operations to your program, say, & (bitwise AND) and | (bitwise OR). You will need to modify the files parser.c and codegen.c. For simplicity you can make the precedence of & the same as for *, and of | the same as for +.
Try to optimize the code generation so that it correctly uses immediate operands. That is, given
```
F = C * 9 / 5 + 32
```
your program generates something like
```
lw $t0, C
mul $t0, $t0, 9
div $t0, $t0, 5
add $t0, $t0, 32
sw $t0, F
```

Try to optimize the code generation so that it uses fewer registers. That is, given

C = 5 * (F - 32) / 9

your program generates something like

lw $t0, F
li $t1, 32
sub $t0, $t0, $t1
lw $t1, 5
mul $t0, $t0, $t1
li $t1, 9
div $t0, $t0, $t1
sw $t0, C

instead of

lw $t0, 5
lw $t1, F
li $t2, 32
sub $t1, $t1, $t2
mul $t0, $t0, $t1
li $t1, 9
div $t0, $t0, $t1
sw $t0, C

Have your program generate an entire MIPS program for calculating an expression, including .data, .word and .space directives. Your program will need to be able to determine which variables have been named in an expression.
Have your program detect when it runs out of registers, and switch to using memory instead.

Attempt any two of the above suggestions for full bonus marks.

Bonus Question 2

The date of the Christian feast of Easter changes each year, historically depending on the date of the March equinox, the phase of the moon and the day of the week. Here is an algorithm for computing the date of Easter Sunday, given the (four-digit) year y.

a = y % 19;
b = y / 100;
c = y % 100;
d = b / 4;
e = b % 4;
g = (b * 8 + 13) / 25;
h = (19 * a + b - d - g + 15) % 30;
m = (a + 11 * h) / 319;
j = c / 4;
k = c % 4;
l = (2 * e + 2 * j - k - h + m + 32) % 7;
n = (h - m + l + 90) / 25;
p = (h - m + l + n + 19) % 32;

n and p contain the month and day of Easter Sunday, respectively.

Write a MIPS program which implements the above algorithm, prompting the user for a year, and printing out the date of Easter Sunday. For instance:

Enter the year: 2003
Easter Sunday is 20/4/2003.

[ Top | Home ]

Last modified 2002-07-01

CSE1303 Computer Science Semester 3 (summer), 2002 Part B Prac B4