Computer Science 220
Assembly Language & Computer Architecture

Fall 2010, Siena College

Home     Syllabus     Schedule

This week, you will learn some more about MIPS programming in part by using a real MIPS processor rather than the SPIM simulator. There is not a lot of programming to do. This is by design, because the lecture assignments will be a bit more significant during our digital logic topics.

You may work alone or with a partner on this lab.

Getting Set Up

Parts of this lab will require you to answer questions and generate several files. Create a directory where you will accumulate these files and open a plain text document lab5.txt  where you will answer the questions. Start out by putting your name(s) and the lab number at the top of that file.

Our MIPS Computer

Thanks to our School of Science network administrators, an old computer with a genuine MIPS processor has been resurrected and made available on the network for our use. The machine is called indy.cs.siena.edu. It is a Silicon Graphics (SGI) Indy, a low-end graphics workstation from the mid 1990's. It runs a flavor of Unix called Irix, SGI's proprietary Unix.

Accessing the MIPS Computer

The MIPS system is on the School of Science (SoS) network but it is in no way integrated with our regular systems. Your login and password and your file space there are completely local to the machine.

To log in, we will need to use the old telnet protocol, an insecure predecessor to ssh. From a computer on the SoS network:

telnet indy.cs.siena.edu

Your username is your SoS username, and your initial password is a capital P followed by your first and last initials, followed by your 9-digit Siena ID.

Each time you log in to indy.cs.siena.edu, you should issue the command

setenv TERM vt100

This will allow the system to understand the Linux terminal windows we use to connect via telnet.

Once you are logged in, you can change your password, if you like, with the command passwd.

Run the command uname -a to get some information about the system. Paste the output of this command into your file lab5.txt.

indy.cs.siena.edu has the standard selection of Unix command-line utilities, but has very little other software installed. Therefore, we will generally edit files on the lab machines and transfer files between there and indy.cs.siena.edu as needed.

Again, these file transfers will use an older protocol: ftp. From a computer on the SoS network:

ftp indy.cs.siena.edu

After you provide your username and password, you will be issued a prompt ftp>. The command ? will list all of the commands that ftp understands, but a few you should be aware of include:

• cd: change directory (on ftp server)
• lcd: change directory (on client)
• ls: list files on server
• put: transfer file from client to server
• get: transfer file from server to client

Obtaining Lab Files

A collection of files you will use in the remainder of this lab are located in the directory /home/jteresco/public/lab5 on indy.cs.siena.edu. Copy these to your directory on indy.cs.siena.edu. A regular old cp command will do this, ftp is not needed here.

These files are also available for your convenience on the Linux systems in

~jteresco/shared/cs220/labs/realmips

A Very Simple C Program

One of the files you copied from /home/jteresco/public/lab5 is hellomips.c, a simple "Hello, World" C program.

First, let's make sure we can compile and run the C program. As on our Linux systems, we have the gcc compiler on indy.cs.siena.edu. So we can compile hellomips.c into an executable program a.out with the command:

gcc hellomips.c

You can then run the program with ./a.out, as usual. Try this.

You've certainly seen similar programs before: we looked at a MIPS assembly "Hello, World" program and ran it in SPIM a few weeks ago. A slightly updated version of that program is in hellospim.s. This version can be assembled by the MIPS assembler (called as), but does not run correctly. But we can give it a try, at least:

as -o hellospim.o hellospim.s
gcc hellospim.o

This will produce an a.out file that we can run, but the real MIPS processor does not understand our syscall. The syscall mechanism exists in both SPIM and on real MIPS processors, but the codes and usage are different.

Next, let's see what MIPS assembly code is generated by the compiler when it compiles up the hellomips.c program. Normally, we do not pay any attention to the fact that our C compiler first generates assembly code (the compilation step), then assembles that code into object code. That object code is then used as input for linking with other object code to produce an executable file.

We can ask gcc to stop after the compilation to assembly code by providing the -S flag:

gcc -S hellomips.c

This will produce a hellomips.s that we can then pass to the assembler to generate an object file:

as -o hellomips.o hellomips.s

and then link it to an executable (linking with printf from the standard C library, which gcc will take care of for us) with the command:

gcc hellomips.o

But, we can also take a look at the assembly code, so let's do that. First, transfer (with ftp) a copy of hellomips.s to your directory back on the Linux system. Then you can use better tools like emacs or whatever else you'd like to look at it.

Questions to be answered in lab5.txt:

• What in the file looks familiar from our SPIM-based MIPS programming?
• What in the file is unfamiliar? What do you think these things represent or do?
• The string "Hello, MIPS world!" must be in there somewhere. Where is it?
• Does the subroutine call to printf follow the subroutine calling conventions we've been using?

Next, let's see if we can pare down this assembly file to its essentials. The compiler is designed to generate assembly code for situations much more complicated than a simple "Hello, World" program, so there's a good chance a lot of what it generated is irrelevant here.

Copy the file hellomips.s to helloshort.s. First, make sure you can still assemble, link, and run the unmodified version. If so, then you can go about removing (better: commenting out) lines that you suspect might be unimportant. Only do one or two lines at a time and then retry it. You may wish to do this by editing helloshort.s on the Linux system and transferring the file to indy.cs.siena.edu repeatedly for testing.

When you believe you have the shortest assembly file that still works, save a copy (you'll be submitting it).

A Simple Subroutine

Next, we'll look at the files print17.c and seventeen.c.

First, compile and link these C programs on indy.cs.siena.edu into an executable a.out with the single command:

gcc print17.c seventeen.c

Run the program and verify that it works as expected.

Now, compile each of these to MIPS assembly source using gcc with the -S flag, obtaining print17.s and seventeen.s.

Again, we can see that the compiler makes things quite a bit more complex than necessary. Instead of paring down the seventeen.s that the compiler generated, let's just write our own very simple version (you should be able to do it with a handful of assembler directives and only 2 instructions - after all, it does nothing but return a constant value!). Call it simple17.s, but be sure to name the subroutine seventeen so we can still call it from the main program.

This is an example of where assembly programming "by hand" can improve upon what a compiler can generate. An assembly programmer can write the simplest and most efficient code possible, while a compiler is going to follow rules that need to apply to all situations and may not be able to detect a very simple case (like this one).

Once you've created your version, try it out. To do so, assemble the compiler-generated print17.s and your simple17.s, then link them together into an executable:

as -o print17.o print17.s
as -o simple17.o simple17.s
gcc print17.o simple17.o

Once it works, place your version of simple17.s into your Linux directory for inclusion in your submission.

Finally, let's see how much faster your version of simple17.s is than the compiler-generated seventeen.s. There is a C program print17s.c that will call seventeen() in a loop ten million times. Compile this and link it first with the compiler-generated code for seventeen():

gcc print17s.c seventeen.c

Run the program several times, using the time command to see how long it takes:

time ./a.out

The third number in the output tells you how much time the program spent executing on the CPU. Paste the output for the fastest run into your lab5.txt file. (Why the fastest and not the average?)

Now, link with your version of the subroutine:

gcc print17s.c simple17.o

Again run it several times with time and choose the fastest time. Also paste that output into your lab5.txt file.

Subroutines

For the next task, start with the C file f.c. There's no main function here, so we'll just look at the assembly code. Generate the f.s MIPS assembly code using gcc -S.

One of the things we notice here (and in previous examples) is the use of the frame pointer, register $fp. In many ways, $fp is used similarly to the stack pointer, $sp. In fact, it is always a pointer into the memory that houses the stack. The difference is that while the stack pointer may change during the execution of a subroutine, the frame pointer should remain fixed. This allows it to be used to refer to specific places on the stack that are used for things like local variables. If space is allocated on the stack for variables, we can determine a fixed offset from the frame pointer where those variables are located.

In this example, the compiler has assigned space on the stack to hold the local variables ga and gb at 24($fp) and 28($fp), respectively. Additionally, it has assigned space on the stack to hold copies of our parameters a and b at 48($fp) and 52($fp). By using this stack space, the compiler is certain that those values (unlike those in registers) cannot be modified unexpectedly by subroutine g.

So far, we have assumed that all local variables are simply assigned registers and we're done. This is only possible when we have enough registers to hold all of the variables that need to exist simultaneously in our subroutine. And...we can't assume any values in t-registers will retain their values across calls to other subroutines. So sometimes, we need space on the stack for local variables.

Now, answer these questions in lab5.txt:

• Which lines of the assembly code are retrieving the parameters to f and storing them in the allocated stack space?
• Which lines set up the parameter to pass to g (for each call)?
• Which lines utilize the return value from g (for each call), putting those values into the memory allocated for local variables ga and gb?

shortf.c is a modification of f.c that implements the function in a single line of code:

   return g(a) + g(b);

Generate shortf.s for this modified version, and answer these questions in lab5.txt:

• How is the generated code simpler? How much less space is allocated on the stack?
• Describe how you could simplify this code even further as an assembly programmer.

It should be pointed out here that we are using gcc to generate MIPS assembly code without any compiler-driven optimizations. Any modern compiler, including gcc, is capable of generating better code than we have seen here. We can see what it does on the original f.c file (note the "O" in -O2 is the letter "O" not the number "0"):

gcc -O2 -S f.c

Answer the following questions about the optimized version of f.s in lab5.txt:

• What registers did the compiler choose to use to store values?
• Did any of these need to be saved on the stack?

Optimizing

Our last example can be found in qpr.c. This contains a simple C function that takes two parameters and computes the sum of their quotient and their remainder when the first is divided by the second.

Generate the MIPS assembly for this function using gcc -S. Note that the function uses two psuedoinstructions you have not seen: div and rem, which compute the quotient and remainder, respectively. However, each of these pseudoinstructions involves using the real instruction div, which computes both the quotient and the remainder, but places them into special registers called LO and HI. The psuedoinstructions as seen in the code will each result in two real instructions being executed:

	div $2, $2, $3

becomes

	div $2, $3
	mflo $2

and

	rem $3, $3, $4

becomes

	div $3, $4
	mfhi $3

As an assembly programmer, however, we can notice that the first div instruction has both pieces of information available. In lab5.txt, describe how you can rewrite the main part of qpr to use only one div instruction and still get the right answer?

This is an example where a compiler is severely limited in its ability to perform an optimization that is readily apparent to an assembly programmer who can take a look at the meaning of a statement rather than just the individual operations that make it up. Our high-level language (in this case, C) does not have the ability to express "divide this number by that and put the quotient in this place and the remainder in that place" so the code we can write by hand would not be generated.

Submission and Evaluation

This lab is graded out of 30 points.

By 10:00 AM, Friday, October 29, 2010, submit the required files packaged into a single tar file lab5.tar, by email to jteresco AT siena.edu.

Please do not include any additional files, such as emacs backup files.