198:516 - Programming Languages and Compilers II
Spring 2006
Programming Project II
Safe Thread-specific Points-to Analysis
Results due: April 24, 2006 at midnight
In-class presentations of results: May 1, 2006 during class

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: