Homework 2: Dataflow Framework

Due: Friday, February 1^th, 5:00 PM

Your assignment this week 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.

We have setup an environment for the programming assignments found at /usr/class/cs243/dataflow/parun.tar.gz. Download and unpack this archive in your home directory on a Stanford machine like elaine. For instance:


elaine:~$ cp /usr/class/cs243/dataflow/parun.tar.gz .
elaine:~$ gzip -d parun.tar.gz
elaine:~$ tar xvf parun.tar

The top level directory structure of the parun environment is:


parun/
parun/bin/
parun/lib/
parun/src/
parun/Makefile

The bin directory contains a script called parun that you can use to run analyses over programs. The lib directory contains the joeq.jar file which contains the joeq program analysis framework. The Makefile compiles all the java files into class files and generates the parun script.

The src directory contains the source files that you'll be using and creating for this programming assignment. The examples package contains the PrintQuads example from the joeq tutorial. The pa1 package contains Flow.java, ConstantProp.java, and Liveness.java. The file Flow.java contains the interfaces and the main program. The file ConstantProp.java contains classes that define a limited constant propagation analysis and likewise, Liveness.java contains classes for the liveness analysis. The pa1.submit package contains skeletons for MySolver.java and ReachingDefinitions.java. Any changes or new class you create must be restricted to this package.

Your task is twofold: 1) Create a class MySolver that implements the interface Flow.Solver. Use it to run the constant propagation and liveness algorithms we provide. 2) Create a class ReachingDefs that implements the interface Flow.Analysis and executes the reaching definitions analysis.

Running Analyses

To run the PrintQuads example from the joeq tutorial that printed out the basic blocks of the ExprTest class using the parun environment, simply make the environment and invoke the parun script on the PrintQuads and ExprTest:


elaine:~$ cd parun
elaine:~/parun$ make
elaine:~/parun$ parun examples.PrintQuads examples.ExprTest

To run MySolver using the ConstantProp analysis over a test program called Test, invoke the parun script on these four classes:


elaine:~/parun$ parun pa1.Flow pa1.MySolver pa1.ConstantProp pa1.test.Test

Testing your code

The pa1.test package contains a Test class that you can use to test your implementation of MySolver and ReachingDefinitions. The parun/src/pa1/test directory contains Test.cp.out, Test.lv.out, and Test.rd.out which are output files for running the ConstantProp, Liveness, and ReachingDefinitions analyses over the Test class. Diff the output of running your MySolver with these out files to check to test your implementation.

Submission

To submit your solutions, package up the parun/src/pa1/submit:


elaine:~/parun$ tar cvf hw1_submission.tar src/pa1/submit

and, then email the archive to the staff list. We will use unmodified versions of the remaining files to test your implementation. If you're working with a partner, indicate their name and SUNETID along with the email. Only one submission is required per pair. If you discover a bug after submitting (and before the due date), simply email us the new submission. We'll take the latest version.

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 and Liveness classes. You will find techniques that will be useful to you when you formulate ReachingDefinitions.

Read the joeq documentation carefully, and don't hesitate to look at the full javadocs if you get stuck. Joeq is still very much an experimental system; if you wish to attempt something particularly tricky, you may find it enlightening to sourcedive.