The SPAN Pointer Analysis Package

The SPAN pointer analysis package is an implementation of our flow and context sensitive pointer analysis for multithreaded C programs. It is implemented in the SUIF Compiler Infrastructure, and has been used for memory access disambiguation in our research group and other research groups.

Source code and documentation for the SPAN pointer analysis package are available here.

Here is our PLDI paper on the SPAN pointer analysis algorithm:

• Pointer Analysis for Multithreaded Programs
  Radu Rugina and Martin C. Rinard
  Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and I mplementation, pp. 77-90
  Atlanta, GA May 1999
  The full version of this paper is available.
  

• The MIT RAW CC compiler used the pointer analysis to promote memory accesses to the static network, eliminating the need to use the slower dynamically scheduled network. A paper reporting the results of this research appeared in ISCA '99:

  Maps: A Compiler-Managed Memory System for Raw Machines
  Rajeev Barua, Walter Lee, Saman Amarasinghe, and Anant Agarwal
  Proceedings of the 26th International Symposium on Computer Architecture
  Atlanta, GA May 1999
  

• The MIT DeepC project used the pointer analysis in the context of a C to silicon compilation system. The idea is to split the memory of the machine into multiple smaller, more efficient memories. The pointer analysis ruled out connections between specific memories and pieces of the computation, eliminating the need to route wires between these two hardware components. A paper reporting the results of this research appeared in FCCM '99:

  Parallelizing Applications Into Silicon
  Jonathan Babb, Martin Rinard, Andras Moritz, Walter Lee, Matthew Frank, Rajeev Barua, and Saman Amarasinghe
  Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines '99 (FCCM '99)
  Napa Valley, CA, April 1999
  

• The Bitwise project at MIT and the PipeRench project at CMU used the results for bitwidth analysis, which computes the number of bits required to store computed values. The following papers report the results of this research:

  Bitwidth Analysis with Application to Silicon Compilation
  Mark Stephenson, Jonathan Babb, and Saman Amarasinghe
  Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation
  Vancouver, Canada June 2000
  

  BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations
  Mihai Budiu, Majd Sakr, Kip Walker, and Seth Copen Goldstein
  Proceedings of Euro-Par 2000
  Munich, Germany September 2000
  

• The MIT Superword Level Parallelism project used the pointer analysis to disambiguate memory accesses, enabling multiple source-level operations to be packed into a single machine instruction. A paper reporting the results of this research appeared in PLDI '00:

  Exploiting Superword Level Parallelism with Multimedia Instruction Sets
  Sam Larsen and Saman Amarasinghe
  Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation
  Vancouver, Canada June 2000
  

• The FlexCache project at MIT and the University of Massachusetts, Amherst, used the analysis to eliminate a large portion of cache tag lookups. A paper reporting the results of this research appeared in IRAM '00:

  FlexCache: A Framework for Flexible Compiler Generated Data Caching
  Csaba Andras Mortiz, Matt Frank, and Saman Amarasinghe
  Proceedings of the 2nd Intelligent Memory Workshop, IRAM00
  Cambridge, Massachusetts November 2000
  

• We used the pointer analysis results as a foundation for our symbolic analysis of accessed memory regions. A paper reporting the results of this research appeared in PLDI '00:

  Symbolic Bounds Analysis of Pointers, Array Indices, and Accessed Memory Regions
  Radu Rugina and Martin C. Rinard
  Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation
  Vancouver, Canada June 2000
  The full version of this paper is available.