198:515 - Programming Languages and Compilers I
Fall 2005
Java Homework Assignment
due: December 13, 2005 at midnight

Overview. This assignment is designed to get you familiar with the relative accuracy of several compile-time reference analyses of Java by comparing their results with respect to call graph construction using the SOOT Java Optimization Framework. A call graph of a program is a compile-time representation of the possible calls that may occur in a program during execution. We will be comparing the accuracy of two approaches for estimating call targets in a call graph of all methods reachable from main in a Java program. The two analyses -- CHA (Class Hierarchy Analysis) and flow-based points-to analysis (points-to) -- safely approximate the possible types of objects (or the objects themselves) that a reference variable or reference field may point to during execution. CHA only uses information about the type hierarchy of a program, whereas points-to analysis incorporates knowledge of the value flow between reference variables and fields by analyzing assignments, object creation sites and parameter passing by calls in the code. We expect a points-to call graph to be more accurate than a CHA call graph, especially at polymorphic call sites, where CHA will assume that objects of all subtypes of the receiver type may reach the call site.

We will use the SOOT system developed at McGill University, a Java bytecode to bytecode translation system, to perform these analyses. SOOT parses Java bytecodes and translates them into a typed 3-address intermediate language called Jimple. We will using the class hierarchy and the call graph calculated by points-to analysis in SOOT to compare the sets of calculated call targets that would result from using these two differnt analyses. After performing points-to analysis, SOOT provides a means for querying the points-to call graph to acertain call target methods at a call site. You will then use the hierarchy to determine the set of call targets that CHA would assume are possible at that call site. We have defined metrics below to be calculated at each call site to measure the relative inaccurary of CHA with respect to points-to analysis. Note that interfaces present similar problems to classes in dermining dynamic dispatch on a reference of an interface type, in that they can be nested and thereby inherit method specifications.

Technical issues.

You will do final data gathering on two of the Java Spec98 benchmarks which will be provided on paul; however, we also provide a smaller Java program on which you can initially test your metrics-gathering code. This Java program involves a simulation of a seashore using the Java GUI libraries. Click on the readme file to learn more about this data and then click to download the tar file whose classes are described in a javadocs tar file. Please read the readme file BEFORE running. Your results should show that the points-to call graph has fewer edges than the CHA call graph which is more approximate.

Accessing SOOT Execution Framework. We have installed SOOT version 2.2.2 on the graduate server paul where it works in conjunction with Java 1.4.2. To use this installation of SOOT you will have to add one line (with no line breaks) to your .cshrc file:

setenv CLASSPATH /grad/cs515/spec_jvm98:/grad/cs515/soot222/polyglotclasses-1.3.2.jar:/grad/cs515/soot222/sootclasses-2.2.2.jar:/grad/cs515/soot222/jasminclasses-2.2.2.jar

If you have already defined CLASSPATH then the line should be:

setenv CLASSPATH ${CLASSPATH}:/grad/cs515/spec_jvm98:/grad/cs515/soot222/polyglotclasses-1.3.2.jar:/grad/cs515/soot222/sootclasses-2.2.2.jar:/grad/cs515/soot222/jasminclasses-2.2.2.jar

Because of the size of the files to be generated by the project, we have arranged for a large shared working space for this project in: /grad/cs515/soot222/working. You should create a subdirectory of this directory in which you do your project; make sure to set the protections so that others cannot read your subdirectory.

Recall that you can access SOOT from any of the grad servers: george, ringo or john, as the load on paul is usually the highest.

What to turn in? You will hand in a tar file of your project including implementation, output and documentation files, using the online handin program, including the following:

The README file should explain the role of each class and key methods in your implementation or you can choose to use Javadocs instead . Click here for more on how to write and process Javadocs. Make sure to include documentation to briefly explain the key ideas in your approach including clever data structures and algorithms.

Q's still unresolved:

Last updated by Barbara Ryder at 8:12am GMT December 5, 2005