Pointer analysis for multithreaded programs

ABSTRACT

This paper presents a novel interprocedural, flow-sensitive, and context-sensitive pointer analysis algorithm for multithreaded programs that may concurrently update shared pointers. For each pointer and each program point, the algorithm computes a conservative approximation of the memory locations to which that pointer may point. The algorithm correctly handles a full range of constructs in multithreaded programs, including recursive functions, function pointers, structures, arrays, nested structures and arrays, pointer arithmetic, casts between pointer variables of different types, heap and stack allocated memory, shared global variables, and thread-private global variables.We have implemented the algorithm in the SUIF compiler system and used the implementation to analyze a sizable set of multithreaded programs written in the Cilk multithreaded programming language. Our experimental results show that the analysis has good precision and converges quickly for our set of Cilk programs.

REFERENCES

• 1: Lars Ole Andersen. Program Analysis and Specializa- DIKU, University of Copenhagen, May 1994.
• 2: Rajeev Barua , Walter Lee , Saman Amarasinghe , Anant Agarwal, Maps: a compiler-managed memory system for raw machines, Proceedings of the 26th annual international symposium on Computer architecture, p.4-15, May 01-04, 1999, Atlanta, Georgia, United States
• 3: Phillip Bogle , Barbara Liskov, Reducing cross domain call overhead using batched futures, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.341-354, October 23-28, 1994, Portland, Oregon, United States
• 4: Martin C. Carlisle , Anne Rogers, Software caching and computation migration in Olden, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.29-38, July 19-21, 1995, Santa Barbara, California, United States
• 5: Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , Andrew F. Stark, Detecting data races in Cilk programs that use locks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277696]
• 6: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 7: Pedro Diniz , Martin Rinard, Synchronization transformations for parallel computing, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.187-200, January 15-17, 1997, Paris, France [doi>10.1145/263699.263718]
• 8: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 9: Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 conference on Supercomputing, p.380-389, December 1994, Washington, D.C., United States
• 10: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 11: Dirk Grunwald , Harini Srinivasan, Data flow equations for explicitly parallel programs, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.159-168, May 19-22, 1993, San Diego, California, United States
• 12: Carl Hauser , Christian Jacobi , Marvin Theimer , Brent Welch , Mark Weiser, Using threads in interactive systems: a case study, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.94-105, December 05-08, 1993, Asheville, North Carolina, United States
• 13: James Hicks, Experiences with compiler-directed storage reclamation, Proceedings of the conference on Functional programming languages and computer architecture, p.95-105, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165194]
• 14: Jens Knoop , Bernhard Steffen , Jürgen Vollmer, Parallelism for free: efficient and optimal bitvector analyses for parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.268-299, May 1996 [doi>10.1145/229542.229545]
• 15: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 16: S. Midkiff and D. Padua. Issues in the optimization of parallel programs. In Proceedings of the 1990 International Conference on Parallel Processing, pages II-105- 113, 1990.
• 17: Robert O'Callahan , Daniel Jackson, Lackwit: a program understanding tool based on type inference, Proceedings of the 19th international conference on Software engineering, p.338-348, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253351]
• 18: John Hamilton Reppy, Higher-order concurrency, Cornell University, Ithaca, NY, 1992
• 19: Erik Ruf, Context-insensitive alias analysis reconsidered, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.13-22, June 18-21, 1995, La Jolla, California, United States
• 20: Radu Rugina , Martin Rinard, Automatic parallelization of divide and conquer algorithms, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.72-83, May 04-06, 1999, Atlanta, Georgia, United States
• 21: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multi-threaded programs, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.27-37, October 05-08, 1997, Saint Malo, France
• 22: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 23: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 24: Philip A. Stocks , Barbara G. Ryder , William A. Landi , Sean Zhang, Comparing flow and context sensitivity on the modification-side-effects problem, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.21-31, March 02-04, 1998, Clearwater Beach, Florida, United States
• 25: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 26: Yingchun Zhu , Laurie J. Hendren, Communication optimizations for parallel C programs, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.199-211, June 17-19, 1998, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Threads

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General
          Subjects: Standards

General Terms:
Algorithms, Design, Measurement, Performance, Standardization, Theory