Computer Science 253r -- Homework One

Due: Tuesday, March 1, 2005 before class

The point of this assignment is to familiarize you with the Machine SUIF compiler, which we'll use for several homework assignments on code analysis and optimization. For this first one, you'll

Part 1

Make up a short, one-file test program in C. Keep it simple. For example, it might use library utilities to sort its command-line arguments and print the resulting list on standard output. Test your program using GCC. Next, read this note: Using the Machine SUIF Compiler. Find the directions (near the bottom) for setting up your shell environment. Run the suif-setup script as described there to define the environment variables needed for use of SUIF. Also read the Machine SUIF Overview document to find out how to compile and run a program using Machine SUIF. Next, log into drdoom.eecs.harvard.edu and copy the directory ~cs253r/hw1 into your own area. For example, use the command 
cp -a ~cs253r/hw1 ~
In the hw1 directory, you'll find a subdirectory called tidy (which is for part 2 of the assignment) and a make file called Makefile.x86. The latter contains rules for compiling a C program to Linux/x86 assembly code, using the passes described in the Machine SUIF overview document. For example, if your test program is called mysort.c, you can compile and run it like this: 
  make -f Makefile.x86 mysort.s
  gcc -o mysort mysort.s
  ./mysort zebra xylophone yurt wimple
Part 1 of the assignment is to get set up and try running Machine SUIF on your little test program. Then mail in your .c and .s files to show you're playing along. (See below.)

Part 2

To get you acquainted with extending Machine SUIF, we've provided an incomplete and deliberately buggy pass called tidy. It's a nobbled version of the peep pass that's mentioned in the overview document. Tidy walks over the control flow graph of each procedure being compiled, and it uses information about liveness of variables and register values to recognize and remove unnecessary instructions. Your job is to compile tidy, fix the bugs we've planted, and extend it to handle a case that's described in the comments, but not yet implemented in the code. We provide a SUIF intermediate file called input.suif for your pass to read in and clean up. We also give you the effectiveness statistics (goodstats.txt) that the completed and debugged pass should print, so you'll know when you're finished. Before compiling tidy, make sure that you've set up your environment for working with SUIF. Be sure that $LOCAL_BASE points to a directory you can write it, and that it has the necessary subdirectories (bin, include, and solib). Go into your tidy directory and run make. We haven't introduced any syntactic errors, so that should build the pass and install the results under $LOCAL_BASE. To run the pass: 
  do_tidy -debug 1 -const_prop input.suif output.suif
The -debug option causes statistics to be printed on standard error when the pass ends. The file output.suif is the tidied output file. Both .suif files are binary, but you can dump their contents in a quasi-assembly format using the do_print command: 
  do_print output.suif output.suif.txt
Your assignment is to read and improve tidy.cpp; that's the only source file that we've broken. When you're finished, your version of the pass should print statistics as good as (or better than) those in goodstats.txt. By default, Machine SUIF passes and libraries are built with debugging information, so you can use GDB if you wish: 
  gdb do_tidy
Please work individually on this assignment. You'll need to consult the Machine SUIF documentation, particularly the documents about the "machine" library, the control-flow graph library, and the data-flow analysis library. As mentioned above, the tidy pass is a thinly disguised, broken version of the peep pass that comes with Machine SUIF. Therefore, please don't look at the code for peep until you've turned in your solution for this assignment.

What to turn in: Send an email message to Glenn containing three attachments: