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.

• Your call graphs may be large since the Java 1.4 libraries are large.
• We will be comparing the accuracy of these two approaches to call graph construction in several ways:
  • calculate the total number of edges in each call graph (i.e., #calls in the entire call graph including the application and libraries)
  • compare the precision of CHA versus points-to at each dynamically dispatched call site in the application (not in the JDK library code) by calculating the possible function targets reported by CHA (C), the set of possible function targets reported by points-to (P) and combining them in the following metric: (|C| - |P|)/|C|. This metric measures the relative improvement of points-to over CHA at each call site (Note both CHA and PT have to find at least one target at each call site, but it is possible for this metric to be zero. Count the number of times that this metric is zero and report that as well.) for those methods reachable from the main of the application.

    You will aggregate this metric for each program in two ways:
    (i) average these findings over all call sites in the application to calculate one precision metric per program
    (ii) histogram your findings, by counting the application call sites for which this metric is between 0-5%, 6-10% etc. You will need to look over your data to see what values are appropriate for these ranges.

  • enumerate (and count) the distinct call chains lying completely within the application in the points-to call graph. This is equivalent to calculating the number of paths in a depth-first search of the call graph, barring any cycle. Note that if the call graph contains cycles, you will need to remove them by taking the strongly connected component decomposition of the graph which results in an acyclic digraph. In this case, you will represent all the nodes in a cycle on a path with one name in your call chains and then also provide a list of the methods in that cycle.

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:

• a README file
• an executable version of your program (the *.class files) with the class containing the main() that starts the execution of your code being named Test. (This is so we can write a script to run your codes; make sure what you turn in is actually executable.)
• the *.java files that you wrote (do not include the SOOT files with the main)
• your results on the test data (including the metrics gathered)
• a file (for each program) containing its call chains

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:

• which spec benchmarks should we specify?

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