CSE 378 Homework 3
Due: Wednesday 4/23/02
Purpose
The purpose of this homework is to familiarize yourself with the
Cebollita toolset. In particular, you'll be learning about the
assembler, linker, and simulator provided by the toolset. You'll
learn how to use the assembler and linker to build executables, and
then use the simulator to run/debug them. You will also try your hand
at a little assembly programming by making minor modifications to a
program we provide. Finally, you'll use the Cebollita compiler
to write/modify your first C-- program.
Introduction
For this assignment we'll use the following program, which computes
the factorial of 9. The line numbers you see are for reference only,
and are not part of the actual assembly program.
1 # compute the factorial of 9 using the following algorithm
2 # N = 9
3 # result = 1
4 # while (N != 0) {
5 # result = result * N
6 # N = N - 1
7 # }
8
9 .data # begin data section
10 msg: .asciiz "The factorial is: " # message string
11
12 .text # begin program text
13 __start:
14 addi $sp, $sp, -4 # make some space on the stack
15 addi $t0, $0, 1 # $t0 will hold result, initially 1
16 addi $t1, $0, 9 # $t1 will hold N, initially 9
17 top: beq $t1, $0, bottom
18 mult $t0, $t0, $t1 # result = result * N
19 addi $t1, $t1, -1 # decrement N
20 j top # goto top
21 bottom:
22 sw $t0, 0($sp) # we'd better save result
23 addi $v0, $0, 4 # finished w/ loop, now print out
24 addi $a0, $gp, msg # message, by invoking syscall 4
25 syscall # (print_string)
26
27 addi $v0, $0, 1 # now print out result, by
28 lw $a0, 0($sp) # invoking syscall 1 (print_int)
29 syscall
30
31 addi $sp, $sp, 4 # reset the stack
32 addi $v0, $0, 10 # exit syscall
33 syscall
Thankfully, you don't have to type the program in yourself, as you can
download it here. Simply download this
file to your home directory and use it. Make sure it's called fact.s
(not fact.s.txt, as Windows will happily try to name it).
Assembling/Linking Your Program
Currently, the Cebollita tools only run on the NT machines in the
lab. Eventually, you ought to be able to run these on Windows
machines at home, or even on UNIX machines.
In the lab, you'll need to build
an executable out of the provided program. This means:
- Start a BASH shell on one of the lab NT machines. Do this by
going to o:\cse\courses\cse378\cygwin and double-clicking
"Cygwin.bat". If all goes well, you'll have a UNIX like command
prompt. Most of your UNIX skills should be applicable at this
command prompt.
- Assemble the program. In your Cygwin window, change to
your work (home?) directory (where you put fact.s). Then, at
the prompt type:
java asm.parser fact.s
- If this step was successful, you should find a file called
fact.o in your directory. (You can type
ls to find
out.)
- Link the program. Now type
java asm.Linker fact.o.
This should create a file called a.out.
These are the basic steps you'll always need to assemble/link a program.
Learn them and love them. (Linking seems excessive now because there
are no other object files, but the Linker still has to get involved because
it resolves intra-file labels as well.)
Other useful tools are the object-file inspector and executable inspector.
Typing java asm.Module fact.o should dump interesting information
about the object file. Typing java util.Exe a.out should dump
interesting information about the executable.
Using the Simulator: Instructions and Questions
- You'll first want to read over the document,
Cebollita MIPS Simulator.
- Start the simulator (
java sim.UI a.out ought to do
it), and run it by single-stepping through it.
- Complete the following table by examining various registers and
memory location contents after the appropriate instructions are
executed. Using the breakpoint command may help in certain situations.
| Location |
Line 16 |
Line 19
3rd iteration |
Line 19
5th iteration |
Line 19
8th iteration |
Line 24 |
| $t0 |
|
|
|
|
|
| $t1 |
|
|
|
|
|
| 0($sp) |
|
|
|
|
|
- In total, how many instructions (in the simulator) are executed to
calculate the factorial of 9? The right way to answer this question
is not to step the program through 9 loops and count instructions,
but rather determine how many instructions are exectuted before the
loop, during one iteration of the loop, and after the loop. Then you
can give us an answer in terms of N, where N is the value we're
calculating the factorial of (as well as the number of times the loop
iterates).
Assembly Programming: Modifications
Modify the given code so that it reads a value of N from the user, and
then computes its factorial. Do this by reading the simulator user's
manual (above), as well as Appendix A, to figure out how to make the
appropriate syscall. Next, modify the program to continue prompting
the user for values of N and computing their factorials. Exit the
program when the user enters a negative number. You'll need to
re-assemble and re-link your program each time you make modifications.
Remember, there is no "development environment" here to do this for
you.
Compilers
The Cebollita toolkit provides a compiler that compiles a subset of
the C language (we call it C--). Below is the C-- version of the
factorial program. It can be found here. Copy
the program to your home directory; compile and run the program using
the simulator:
- Compile:
java comp.parser hw3.c. This will
create a file called hw3.s.
- Now assemble hw3.s (as above).
- Linking is a little trickier, because this file makes references
to printInt(), printString() and exit(), which are simple functions
that wrap up the associated system calls. (If we try to link
at this point, with
java asm.Linker hw3.o, we'll get
an error. Try it and see what kind of error you get.)
- These functions are defined in a file called syscall.s. Download this file and
assemble it into an object file.
- Now you're ready to build an executable. Link the two object
files (hw3.o and syscall.o) as follows:
java asm.Linker hw3.o
syscall.o. This should produce an executable (a.out).
Now run the resulting a.out in the simulator. Hopefully, you'll get
the same result as above.
__start() {
int N = 9;
int result = 1;
while (N != 0) {
result = result * N;
N = N - 1;
}
printString("The factorial is: ");
printInt(result);
exit();
}
Answer the following questions. How many cycles does it take?
How many load instructions are executed by the program?
How many arithmetic instructions are executed?
Finally, modify the above C-- program in the same manner as you modified the
assembly program (above). It should call the function readInt to get
an integer from the user. Below is an example C-- program that uses readInt:
__start() {
printString("Please enter a number: ");
int x = readInt();
if (x < 0) {
printString("Your number is negative.\n");
}
else {
printString("Your number is non-negative.\n");
}
exit();
}
Contrast the tradeoffs between programming in C-- and assembly code. How
long did it take you to make the respective modifications?
Deliverables
Please stay tuned.
dugan@cs.washington.edu