Pointer and Escape Analysis

The goal of our pointer and escape analysis research is to understand how programs access objects, and use that understanding to drive large-scale program transformations such as automatic distribution, communication generation, parallelization, and memory management optimizations such as the elimination of local and distributed garbage collection. An overall theme of this research is the analysis of multithreaded programs.

A key problem with analyzing multithreaded programs is the need to characterize the effect of all potential interleavings of statements from parallel threads. My research group pioneered a compositional approach to this problem in which the algorithm analyzes each thread once to obtain a result that characterizes all potential interactions between that thread and other parallel threads. We have used this approach to develop a variety of analyses for different kinds of multithreaded programs. Here are several specific analyses:

• The first flow-sensitive pointer analysis algorithm for programs with structured multithreading. The algorithm was implemented for the Cilk multithreaded language. Our PLDI '99 paper on this topic describes the algorithm and presents some experimental results from the implementation. The analysis has been used in the the following projects:

  • The MIT RAW project used the analysis for memory bank disambiguation (see an ISCA 1999 paper on this topic).
  • A C-to-silicon compiler used the analysis to partition variables into separate memories (see an FCCM '99 paper on this topic).
  • The Bitwise project at MIT used the analysis as a foundation for another analysis that extracts the minimum number of bits required to represent computed values.
  • The PipeRench reconfigurable computing project at CMU also used the analysis for bitwidth computations.
  • The Superword level parallelism project at MIT used the analysis as a foundation for further analyses to identify SIMD operations and generate code to exploit wide superwords in new architectures.
  • The FlexCache project at MIT and UMass Amherst used the analysis as part of an effort to deliver a software-only solution for managing on-chip data caches.
  • We used the analysis as a foundation for our symbolic analysis of divide and conquer programs. Our compiler uses the results for static race detection for parallel divide and conquer programs, automatic parallelization of sequential divide and conquer programs, static detection of array bounds violations, and elimination of array bounds checks.

• The first combined pointer and escape analysis for programs with the unstructured form of multithreading present in Java. We used the implemented analysis for synchronization elimination and stack allocation of objects. A key concept underlying the analysis is the goal of representing interactions between analyzed and unanalyzed regions of the program. This approach delivered a flexible analysis that is capable of analyzing arbitrary parts of the program, with the analysis result becoming more precise as more of the program is analyzed. At every stage in the analysis, the algorithm can distinguish where it does and does not have complete information. Our OOPSLA 1999 paper on this topic presents the algorithm and provides experimental results from an implementation in a dynamic compiler for Java.

  The base analysis deals with multithreaded programs in a very conservative way - once an object becomes accessible to multiple threads, the analysis considers the object to permanently escape. We extended the analysis to analyze interactions between parallel threads, enabling the analysis to capture objects that do not escape a given multithreaded computation. Our PPoPP 2001 paper on this topic presents the algorithm and provides experimental results from an implementation in the MIT Flex compiler. We use the analysis to verify the correct use of region-based allocation.

• The first incrementalized pointer and escape analysis. Instead of analyzing the whole program, this algorithm builds on our compositional analysis to analyze only those parts of the program that may deliver useful optimization opportunities. An analysis policy monitors the analysis results to direct the incremental investment of analysis resources to those parts of the program that offer the highest expected optimization return.

  Our experimental results show that almost all of the objects are allocated at a small number of allocation sites and that an incremental analysis of a small region of the program surrounding each site can deliver almost all of the benefit of a whole-program analysis. Our analysis policy is usually able to deliver this benefit at a fraction of the whole-program analysis cost. Our PLDI 2001 paper on this topic presents the algorithm and provides experimental results from an implementation in the MIT Flex compiler. We use the results for stack allocation.

• A new symbolic analysis for characterizing regions of allocated memory blocks. In addition to loops and array accesses, the analysis is designed for programs that use pointers, pointer arithmetic, and recursion. The results have been used for static race detection for parallel divide and conquer programs, automatic parallelization of sequential divide and conquer programs, static detection of array bounds violations, and elimination of array bounds checks.

All of these algorithms have been implemented, either in the Stanford SUIF compiler infrastructure (for C) or the MIT Flex compiler infrastructure (for Java) and have been used to analyze and and perform a range of optimizations on complete benchmark programs.

Here are some papers on these topics:

• Purity and Side Effect Analysis for Java Programs
  (PostScript)
  Alexandru Salcianu and Martin C. Rinard
  Proceedings of the 6th International Conference on Verification, Model Checking and Abstract Interpretation
  Paris, France, January 2005

• A Classification System and Analysis for Aspect-Oriented Programs (Distinguished Paper Award)
  (PostScript)
  Martin C. Rinard, Alexandru Salcianu, and Suhabe Bugrara
  Proceedings of the Twelfth International Symposium on the Foundations of Software Engineering
  Newport Beach, California, November 2004

• Interprocedural Compatability Analysis for Static Object Preallocation
  (PostScript)
  Ovidiu Gheorghioiu, Alexandru Salcianu, and Martin C. Rinard
  Proceedings of the 30th Annual ACM Symposium on Principles of Programming Languages (POPL 2003)
  New Orleans, Louisiana, January 2003

• Incrementalized Pointer and Escape Analysis
  Frederic Vivien and Martin C. Rinard
  Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Im plementation
  Snowbird, Utah June 2001
  The full version of this paper is available.

• Pointer and Escape Analysis for Multithreaded Programs
  Alexandru Salcianu and Martin C. Rinard
  Proceedings of the 8th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
  Snowbird, Utah June 2001

• Compositional Pointer and Escape Analysis for Java Programs
  John Whaley and Martin Rinard
  Proceedings of the 14th Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications
  Denver, CO November 1999

• Pointer Analysis for Multithreaded Programs
  Radu Rugina and Martin C. Rinard
  Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design an d Implementation
  Atlanta, GA May 1999
  The full version of this paper is available.

I have also prepared an invited paper and an invited talk for SAS 2001 on the analysis of multithreaded programs.