Overview. This assignment is to familiarize you with the SOOT Java Optimization Framework, that is used for formulating analyses and transformations of Java bytecode programs. SOOT parses Java bytecodes and translates them into a typed 3-address intermediate language called Jimple. An important analysis for Java programs is reference analysis, that determines the set of objects which may be pointed to by a reference variable or field. For example, this information determines the targets of a dynamic dispatch off of that variable, and which objects experience side effects through stores to that variable. SOOT contains an analysis module called SPARK, which has various reference analyses -- context-sensitive and context-insensitive. The overall goal of the two projects this term will be to perform some sort of program optimization, enabled by a thread-specific points-to analysis. The choice of optimization may be determined by our ability to secure adequate benchmarks for experimentation. The first project will develop an unsafe thread-specific compile-time reference analysis that will only account for points-to relations resulting from methods reachable from a specific thread. This analysis is 'unsafe' primarily because some of the objects may 'escape' this thread and be acted upon by other threads while the original thread is executing, so we may be missing some of the relationships of such objects. The second project will refine the first analysis to include escape information about the objects, so as to get safe thread-specific points-to information. The current plan is to do the first project individually and the second project in groups of 2 students, if possible.
Project I Definition.
Our first project consists of coding an Anderson-style, flow-insensitive, context-insensitive points-to analysis, but restricting the reference assignments considered to those methods reachable during execution of one thread. Thus, you will look for the run method in a classt subclasses Thread or Runnable, and then perform points-to analysis on the reference variables and fields encountered. See points-to algorithm details, for more information. Part of this process will be to develop an on-the-fly call graph for this thread. A call graph is a compile-time representation of the possible calls that may occur during execution; its nodes are methods and its edges are calls. Note: that for call graph construction we treat interfaces similarly to classes.
The output of this analysis will be a points-to set for each reference variable and field in the application (not in the libraries, although the libraries have to be analyzed). Note: we will provide an XML DDT for you to use in outputting these points-to sets according to a command line option, to facilitate grading. You will collect the average size of these points-to sets in histograms as output of our analysis. As a 'sanity check', you can use the SPARK global points-to analysis (e.g., 0-CFA) to make sure that your unsafe thread-specific analysis results are a subset of these global results for each reference variable.
You will do final data gathering on mtrt benchmark which will be provided on paul. There will be a small threaded benchmark provided for your use in testing.
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
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.
Last updated by Barbara Ryder at 11:35pm on February 5, 2006.