Due date: Tuesday, March 11, 2003 - In class
NEWS:
Introduction
In this assignment, you will use the Bernoulli Compiler Construction Kit (BCCK) compiler testbed and the OMEGA library to perform dependence analysis. The objective of the assignment is to get you started on working with BCCK and OMEGA, and to familiarize you with dependence abstractions.
There are two 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 BCCK. In the second part, you must use BCCK to extract extract systems of dependence constraints from a small C program and use the Omega library to compute dependence vectors from these constraints.
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
(Win32/Cygwin binary available here),
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]
Hint: Put all your queries in a file and pipe that file through the Omega Calculator.
C:\oc> notepad hw2_1.oc C:\oc> .\bin\oc.exe < hw2_1.oc
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. Using BCCK
The BCCK system is a compiler toolkit written in C# that compiles C programs to an intermediate format on which analysis and optimizations can be performed. In the problem, you will download and install BCCK on your machine.
The source code is available from here. To compile BCCK on your machine,
Windows: Either,
Linux: Direction will be posted shortly.
FreeBSD: It should be possible to use the BCCK under FreeBSD using Rotor, but we are not able to support this.
Note: The Mono and Portable.NET C# compilers do not compile the BCCK.
Run BCC.exe on the "C/Samples/cs612/test.c". The output should be,
Function: test1 Function: test2 Function: test3 Function: test4 Function: test5 Done!
Make sure that you have this working before continuing to 3.
3. Dependence Analysis using BCCK and the Omega Library
The file "BCC/DependenceAnalysis.cs" is skeleton for doing dependence analysis using BCCK. Using the techniques presented in class, add code to DependenceAnalysis.cs to compute distance and direction vectors.
Run your compiler on "test.c". Turn in your code, and the dependence vectors produced by your compiler.
Here is additional documentation that you might find useful,
Some C# pointers,