Martin Rinard

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:

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:

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