In this assignment, you will use the SUIF1 compiler testbed and the OMEGA library to perform dependence analysis. The objective of the assignment is to get you started on working with SUIF and OMEGA, and to familiarize you with dependence abstractions.
To do this assignment, you need a CS department UNIX shell account.
If you do not have one - send mail to ezick@cs.cornell.edu.
There are three parts to the assignment. In the first part, you must
compute dependence vectors for a few simple loop nests by invoking the Omega calculator.
This part does not require
you to use SUIF. In the second part, you must run these loop nests through the SUIF compiler, print out the dependence
vectors
computed by SUIF, and compare them with your hand-generated results.
In the third part, you must extract systems of dependence constraints from SUIF, use the Omega library to compute dependence
vectors from these constraints, and compare them with dependence vectors obtained from the previous two parts.
1. Dependence Analysis using the Omega Calculator
For each of the loop nests given below, write down the dependence
systems (sets of integer linear inequalities) for computing flow, anti, and output dependences.
Your dependence systems must include
inequalities generated from loop bounds. Enter these systems by hand into the
Omega Calculator
(binary available on the CS systems at ~pidgin/sww/sparc-solaris/bin/oc),
and compute dependence distance/direction vectors.
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
for(int k=0; k<N; ++k)
A[i][k] = B[i][j] * C[j][k];
for(int i=0; i<N; ++i)
for(int j=i; j<N; ++j)
A[j] = A[2i+1];
for(int i=0; i<N; ++i)
for(int j=0; j<i; ++j)
for(int k=i; k<N; ++k)
A[i][j] = A[i][j-4] * A[k][i-1];
for(int i=0; i<100; ++i)
x[i+100] = 2*x[i]
for(int i=0; i<100; ++i)
x[i+100] = 2*x[i+1]
Turn in the dependence systems, the queries submitted to Omega, and the dependence vectors computed in this manner.
For the second loop nest, graph the iteration space and use arrows to show the dependences between the iterations.
2. Dependence Analysis using SUIF
The SUIF system is a compiler toolkit which compiles C programs to an intermediate format on which analysis and optimizations can be performed. The system is reasonably robust and and has libraries to do a number of common types of analysis. Go to the SUIF homepage, download and install the SUIF1 (not SUIF2) system in your account (or use the version in ~pidgin/attic/suif/basesuif-1.1.2). Also download and install the cookbook package. The web page and the tar.gz files contain documentation on how to do this. Pay careful attention the setting in your path and to the distinction between make and gmake (you need to use gmake with SUIF makefiles).
The fourth example in the cookbook package contains the code to perform the loop dependence vector analysis that we have done in class. Compile this example and then run it on the loops shown above (you will have to create a C source file for the codes). See cookbook example 1 for info on how to compile such a program to an spd file. Examine the dependence vectors produced by SUIF and interpret the output, comparing it with the results from the previous step.
Turn in the dependence vectors produced by SUIF.
3. Dependence Analysis using SUIF and the Omega Library
In the final part, use/modify the code SUIF cookbook example 4 that walks over the loop nests and replace the call to "DependenceTest" with code that invokes the Omega Library (~pidgin/attic/omega/omega) to compute dependence vectors. You may find it useful to look at the source code for Dependence Test and for the relevant SUIF data structures.
Your code should be able to handle any perfectly nested loop in which loops bounds are affine expressions involving constants, loop invariant variables, and outer loop variables, and in which array subscripts are affine functions of loop variables, loop invariant variables, and constants.
Turn in your code, and the dependence vectors produced by Omega.
4. Conclusions
Are the dependence vectors produced by the three approaches the same? If not, explain why not.