Programming Assignment 1: Dataflow Framework

Due: Friday, February 3, 5:00 PM

Assignment Description

Your assignment is to implement a basic dataflow framework for the joeq system. We will provide the interfaces that your framework must support. You will write the iterative algorithm for any analysis matching these interfaces, and also phrase Reaching Definitions in terms that any implementation of the solver can understand.

• The skeleton and sample analysis are available in /usr/class/cs243/dataflow.
• You can also download thea assignment files and the joeq framework. If you use Eclipse for development, you can download an Eclipse project that you can simply import into your existing Eclipse Workspace.
• The file Flow.java contains the interfaces and the main program. The file ConstantProp.java contains classes that define a limited constant propagation algorithm.

Your task is twofold:

• Create a class MySolver that implements Flow.Solver. Use it to run the constant propagation algorithm we provide.
• Create a class ReachingDefs that implements Flow.Analysis and solves the reaching definitions problem.

You may define any other classes you need to solve this problem. However, do not modify either Flow.java or ConstantProp.java. We will be using our own copies for grading purposes.

Running Your Code

Flow is runnable, and takes three (or more) arguments. The first argument is the name of the class that holds the analysis you want to run. The second is the name of the solver to use. All others are the names of classes to analyze. So, to run constant propagation on test.class, enter the command:

    java Flow MySolver ConstantProp test

And it should do the right thing.

A Makefile is included to help you compile and run your code. To compile you solver, enter the command:

    make solver

To compile your reaching definitions analysis, enter the command:

    make reachingdefs

Testing Your Code

We have provided a very simple program, called test.java, in the code directory. The file test.txt produces output that should match your output when you run your Solver with it. We also provide the test.class to ensure everyone has the same, so you shouldn't compile it yourself.

Here again, the Makefile is here to help you. To test constant propagation, just type

    make test_constantprop

And to test reaching definition:

    make test_reachingdefs

To test both:

    make test

Turning it in

A submit.sh script is available in the usr/class/cs243/dataflow/submit.sh. Follow these steps:

1. Name your solution MySolver.java and ReachingDefs.java.
2. Run the script from the directory containing these 2 files.
3. If you are working with a partner, then only one of you needs to submit the assignment and put your partner Sunet ID as an argument to the submit script. For example :

       /usr/class/cs243/dataflow/submit.sh foo

   where foo is the Sunet ID of your partner.

Hints

• GET STARTED EARLY. This is a sizable project, and you need to familiarize yourself with joeq at the same time. If you wait until the last minute, you will not be able to finish.
• Look at the ConstantProp classes. You will find techniques that will be useful to you when you formulate ReachingDefs.
• Read the joeq documentation carefully, and don't hesitate to look at the full javadocs if you get stuck. joeq is still an experimental system; if you wish to attempt something particularly tricky, you may find it enlightening to sourcedive.
• Study the QuadIterator interface carefully. It does a great deal of the work for you.