Implementation project: the beginning

In the project component of 7135, you will implement some of the ideas discussed in the class (or something relevant to those ideas). You get to choose what you want to implement and experiment with. In order to prepare you for your implementation I will give out two simple implementation projects that will familiarize you with the compiler infrastructure that we will use for the project. In these simple projects I will have you build tools that you will most likely find useful for your final project. In this document, I will first describe preliminaries for setting up the compiler infrastructure. Then I will lay out the first simple implementation project.

The SUIF-1 compiler infrastructure

The SUIF compiler infrastructure (SUIF stands for Stanford University Intermediate Format) is an infrastructure for compiler research for C and FORTRAN. (A newer version of SUIF that supports Java is being put together right now but it is still in the beta stages.) A SUIF compiler run is made up of a collection of passes. The first pass is "scc" which takes a C program and generates the SUIF representation for it in a file. For example:
scc -.spd hello.c
generates a SUIF file (with extension .spd) for "hello.c".
The last pass is typically s2c, which takes a single SUIF file and converts it to a C file. This C file can then be compiled with your favorite C compiler (typically gcc or egcs) and run. Between the first and the last pass there may be one or more other passes that analyze the program or optimize it. Each of these passes take in one or more SUIF files and produce one or more SUIF files.

For example, consider this sequence of calls:
scc -.spd hello.c
porky -Difs hello.suif hello.suifnoif
myoptimization hello.suifnoif hello.suifopt
s2c hello.suifopt hello.opt.c
gcc hello.opt.c
a.out
In this example, we run two passes after converting hello.c into the SUIF representation. The first pass "porky -Difs" is a pass that comes with the SUIF compiler. It takes "if" statements in the SUIF representation and breaks them down into conditional gotos. Porky has a collection of other similar options that simplify the SUIF representation by breaking down (dismantling) relatively complex SUIF nodes into their simpler equivalents.
For many of my analyses, I run this pass:
porky -Dfors -Dloops -Difs -Dblocks -no-call-expr -Ddivfloors -Ddivceils -Dmins -Dmaxs -Dmods
which does several simplifications to the SUIF file.
"myoptimization" is a pass that you can write--it takes in a SUIF file, does some optimizations (improvements) to it and writes it out in the file hello.suifopt. Finally, I convert the optimized SUIF file into C, compile it with gcc and run it.

What if my C program is made up of multiple files? In this case, I need to generate multiple SUIF files (one for each C file) and combine them using "mergesuif" and "linksuif" into a single file. Look at the man pages for porky, mergesuif, and linksuif for more information on these passes. For your first assignment, I recommend you stick to single file C programs. Later in the week I will introduce you to a script that makes it easy to handle multi-file C programs.

To view the contents of a SUIF file, use printsuif, e.g.,:
printsuif hello.suif

Getting ready to use the infrastructure

You need to set a number of environment variables that are used by the SUIF build and install process. Here is what my .bashrc looks like:
export SUIFHOME=/tools/cs/top/suif
export MACHINE=sparc-sun-solaris2
PATH=$SUIFHOME/$MACHINE/bin:$PATH
export LD_LIBRARY_PATH=$SUIFHOME/$MACHINE/solib:$LD_LIBRARY_PATH
export COMPILER_NAME=gcc
export INCLDIR=$SUIFHOME/$MACHINE/include
export MANPATH=$SUIFHOME/man:$MANPATH
export SUIFPATH=${SUIFHOME}/${MACHINE}/bin:/tools/cs/gcc/bin:$SUIFPATH

If you don't know how to set "MACHINE", look in the $SUIFHOME directory: there will be a subdirectory for each machine/OS for which it is compiled. Locate the machine that fits your machine and set MACHINE to it. Adapting the above bash commands to your favorite shell should be straightforward.

Once you have set these variables, test your setup by copying the directory ~diwan/suif-passes/example1 into your directory and doing a "make" in the example1 directory. This should create an executable called example1. Run this executable on a suif file (e.g., example1 hello.suif hello.counts). This example counts the number of top level SUIF nodes in each procedure and puts these counts as annotations on procedures. (For more information on SUIF nodes and annotations, read the document linked from the class home page).

Implementation project 1

Write a pass that finds basic blocks. For each block your pass should output the following information into a text file:
<proc name> :<basic block start> :<basic block end>
<proc name> is the procedure containing the basic block. <basic block start> is the number of the SUIF instruction that marks the start of the basic block. <basic block end> is the number of the SUIF instruction that marks the end of the basic block. Put information for each basic block on a new line.
Please follow the above format carefully--it will make my life much easier.

Due date

Email your SUIF pass and Makefile to diwan%40cs.colorado.edu by Feb 4th at 5:00 p.m. Later this week I will also give you a SUIF file for which you should email me your output.