Overview. We are using the SOOT Java Optimization Framework for both of our programming projects this term. SOOT parses Java bytecodes and translates them into a typed 3-address intermediate language called Jimple. 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 develop expertise in points-to analysis. The second project will refine our first project analysis to include escape information about the objects, so as to obtain safe, thread-specific points-to information. We will compare this information with that obtained from other static and dynamic analyses.

The second project may be done in groups of 2 students or individually; there will be different required results reporting for the team and individual projects.

Project II Definition.

Our second project consists first of refining the code of our unsafe thread-specific points-to analysis, so as to account for objects that may escape the thread. Recall that our first project involved a projection of a flow-insensitive, context-insensitive points-to analysis onto the methods called by a specific thread. This was an unsafe analysis because there might be a chance for an object to escape this thread (i.e., be shared between 2 threads) and then to acquire relations to other objects as the result of code executed in another thread. Such relations are missed by our Project I analysis, which renders its results unsafe.

To correct this deficiency when we are calculating the side effects of pointer assignments during the thread-specific points-to analysis, we need to understand whether or not the object pointed to by a reference on the right-hand-side of the assignment can escape the current thread. If that object can escape the current thread, then we need to consult a global points-to analysis (i.e., 0-CFA) provided by SPARK and to use its points-to set for that object, rather than the local points-to analysis results (which we are computing for that object). For example, given the assignment statement: p.f = q, if p points to an escaping object o, then there is an escaping reference to any object pointed to by q through o.f. Thus, this statement results in all the objects pointed to by q being marked as escaping. For objects that do not escape, we can use the thread-specific points-to information during the analysis. However, for objects that do escape, we need to use the global points-to information, because we cannot ascertain the possible interleavings of writes from other threads with the execution of the thread we are analyzing. See algorithm details for more information on differences between these two points-to analyses.

This analysis will produce a Points-to set for each reference variable and reference field accessible from the thread. We can use this information to eliminate redundant synchronizations from the methods used in that thread or to manage storage more efficiently. Assume method foo() is a user (i.e., non-library) method executed in this thread. If we examine the points-to set of foo().this and we find that none of the objects reachable from this reference escape the executing thread, then we do not need synchronization on foo() during execution. Because of the limitations of the available data, we are not going to examine the possible effects of this transformation. Instead, we will gather different metrics to illustrate (i) the increased precision of the thread-specific analysis and (ii) the difference between the static analysis results and what we can observe dynamically by running the benchmarks.

After determining safe thread-specific points-to sets for all the reference variables and fields, the teams will collect the following information:

• call graph comparison Comparison of the number of reachible methods from the thread.start() method,
  
  • * using the safe thread-specific analysis
  • * using the O-CFA points-to analysis
  • using a dynamic analysis of observed methods called
• points-to set size comparison Comparison of the sizes of points-to sets calculated for each reference variable and field,
  
  • by the safe, thread-specific points-to analysis
  • by the O-CFA points-to analysis
  For the dynamic analysis cited above, we suggest you use JVMPI or *J rather than SOOT. The starred items are the metrics reported by those students choosing to complete the project individually.

  You will do final data gathering on the three benchmarks (Muffin, mtrt, and our artificial benchmark) which will be provided on the graduate servers.

  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. You also may looad SOOT on your personal machine.

  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 that documents the main architecture of your code, and gives 1 sentence comments about each method in each class.
  • 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 (i.e., the metrics gathered)

  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 April 19, 2006.