Project 4 : Data Dependence Test

Project 4: Data Dependence Test

Due Date: 04/20/09

Programs should be submitted using the turnin program on csnet.cs.tamu.edu by the announced time. Submissions should be in the form of a single file named project5_UIN.tar.gz file (where UIN is your UIN number) containing the relevant source code and a README file explaining your approach (see Creating .tar.gz File below on how to create and submit this file.)

Introduction

In this project, you need to do data dependence analysis on the input program in its SSA form. As an exercise, you will implement scalar data and array dependence (DD) tests to discover all loop-carried flow, output, and anti dependence relations.

The algorithms you will implement in Project 5 are described in Chapter 6,7 of Wolfe book. To simplify design, the project is broken into three parts :

Flow/Output Scalar Data Dependence. (50 %)
Scalar Anti-Dependence. (20%)
Array Data Dependece. (30%)

Input and Output

The input/output process will be the same as previous projects.

Program Design

Switches

All the routines for Scalar DD and Array DD should be controlled by switches. For these passes you will use the following switches :

ddtest     1  locate Data Dependencies (0=dont,1=do)
dds_flow     1  locate Scalar flow-dependencies (0=dont,1=do)
dds_output   1  locate Scalar output-dependencies (0=dont,1=do)
dds_anti     1  locate Scalar anti-dependencies (0=dont,1=do)
dda_flow     1  locate Array flow-dependencies (0=dont,1=do)
dda_output   1  locate Array output-dependencies (0=dont,1=do)
dda_anti     1  locate Array anti-dependencies (0=dont,1=do)
p_ddtest   2  print after DD test pass (0=dont,1=FORTRAN,2=detailed)

These values are the default as specified in the file switches in your work directory (do not remove this file since it is a symbolic link to the default switchfile -- copy it to another file and specify that filename with the -f option when running mypolaris.)

The driver program will only call the routines in these passes if ddtest is 1. The print switches will only be examined if the relevant passes are turned on. It is your responsibility to examine dds_flow, dds_output, dds_anti, dda_flow, dda_output and dda_anti, to determine what types of dependency checking you will perform.

DD test Pass

The Data Dependence test pass should be implemented in the cvdl/ddtest directory. The file ddtest.h shows the prototype of the function called from the driver program

void ddtest(ProgramUnit & pgm);

This is a simple pass which takes one program unit as input, analyzes any relevant statements inside, and outputs a summary of all dependence relations found. This function can only be called if ssa() was already called.

The file cvdl/ddtest/Makefile includes the lines :

CPPSRCS = ddtest.cc # add your other .cc files here

CPPHDRS = ddtest.h # add your other .h files here

Algorithm Design

The scalar DD test algorithms for this pass are described in section 6.7 of Wolfe. To find flow dependence relations you will use the FUD chains in a straightforward manner. Output dependence relations will require a slight modification, and Anti dependence relations require the construction of FRUD chains. You should implement each type of dependence testing individually in sequence, testing as you go. The output should be of the format :

    LOOP looplabel contains the following dependencies :

        Flow :

            statement_label1 to statement_label2 (distance_vector1)

        Output :

            statement_label3 to statement_label4 (distance_vector2)

        Anti :

            statement_label5 to statement_label6 (distance_vector3)

The array DD test algorithm for this pass are described in section 7.2 of Wolfe. You need to use GCD (greatest common divisor test) to find out if there are dependences for all array variables in the loop. The output should be of the format :

    LOOP looplabel contains the following dependencies :

        Flow :

            statement_label1 to statement_label2 (array variables)

        Output :

            statement_label3 to statement_label4 (array variables)

        Anti :

            statement_label5 to statement_label6 (array variables)

Note, for each loop. If a loop does not contain a dependence, indicate this as well.

Compiling

You can re-compile your files from within the ddtest directory as long as you have compiled mini_polaris for once. In another word, there is already a mini_polaris generated.

If you have not compiled out mini_polaris yet, change to your work directory and run make

If you make some changes and want to recompile, just type make at the ddtest directory. Or, if you want to do it from the top-level makefile, you should do (suppose you are at the ddtest directory)

rm libddtest_pkg.so.1

cd ~/minipolaris

make

Creating .tar.gz File

The files necessary for submission should be all source code (.cc and .h) and the Makefiles in the directory cvdl/ddtest in your personal work directory. To create the file proj-ddtest.tar.gz, first clean out all non-relevant files from the ddtest directory, including any objects or libraries (i.e., any .o files.) Then change to your cvdl directory and then tar and compress the files as in the following example :

cd ~/minipolaris/cvdl/ddtest

rm *.o libddtest_pkg.so.1

cd ..

tar cf - ddtest | gzip > project5_UIN.tar.gz

gzcat project5_UIN.tar.gz | tar tvf -       # this will list the files for verification

Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU