Pointer analysis for structured parallel 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. The algorithm is designed to handle programs with structured parallel constructs, including fork-join constructs, parallel loops, and conditionally spawned threads. 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 wide range of programming language constructs, including recursive functions, recursively generated parallelism, function pointers, structures, arrays, nested structures and arrays, pointer arithmetic, casts between different pointer 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 set of multithreaded programs written in the Cilk programming language. Our experimental results show that the analysis has good precision and converges quickly for our set of Cilk programs.

REFERENCES

• 1: Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
• 2: Andersen, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis, DIKU, University of Copenhagen.
• 3: Jonathan Babb , Martin Rinard , Csaba Andras Moritz , Walter Lee , Matthew Frank , Rajeev Barua , Saman Amarasinghe, Parallelizing Applications into Silicon, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.70, April 21-23, 1999
• 4: Vasanth Balasundaram , Ken Kennedy, Compile-time detection of race conditions in a parallel program, Proceedings of the 3rd international conference on Supercomputing, p.175-185, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318809]
• 5: 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
• 6: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 7: Johann Blieberger , Bernd Burgstaller , Bernhard Scholz, Symbolic Data Flow Analysis for Detecting Deadlocks in Ada Tasking Programs, Proceedings of the 5th Ada-Europe International Conference on Reliable Software Technologies, p.225-237, June 26-30, 2000
• 8: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 9: 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
• 10: Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.56-69, October 14-18, 2001, Tampa Bay, FL, USA
• 11: Mihai Budiu , Majd Sakr , Kip Walker , Seth Copen Goldstein, BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.969-979, August 29-September 01, 2000
• 12: D. Callahan , K. Kennedy , J. Subhlok, Analysis of event synchronization in a parallel programming tool, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.21-30, March 14-16, 1990, Seattle, Washington, United States
• 13: David Callahan , Jaspal Sublok, Static analysis of low-level synchronization, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.100-111, May 05-06, 1988, Madison, Wisconsin, United States
• 14: 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
• 15: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 16: 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]
• 17: 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]
• 18: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 19: Jyh-Herng Chow , William Ludwell Harrison, III, Compile-time analysis of parallel programs that share memory, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143194]
• 20: Chow, J.-H. and Harrison, W. 1992b. A general framework for analyzing shared-memory programs. In Proceedings of the 1992 International Conference on Parallel Processing, Ann Arbor, MI.
• 21: James C. Corbett, Evaluating Deadlock Detection Methods for Concurrent Software, IEEE Transactions on Software Engineering, v.22 n.3, p.161-180, March 1996 [doi>10.1109/32.489078]
• 22: Cousot, P. and Cousot, R. 1984. Automatic Program Construction Techniques. Macmillan Publishing Company, New York, NY.
• 23: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 24: Detlefs, D., Leino, K. R., Nelson, G., and Saxe, J. 1998. Extended static checking. Tech. Rep. 159, Compaq Systems Research Center.
• 25: Laura K. Dillon, Using symbolic execution for verification of Ada tasking programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.643-669, Oct. 1990 [doi>10.1145/88616.96551]
• 26: 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]
• 27: Pedro C. Diniz , Martin C. Rinard, Lock coarsening: eliminating lock overhead in automatically parallelized object-based programs, Journal of Parallel and Distributed Computing, v.49 n.2, p.218-244, March 15, 1998 [doi>10.1006/jpdc.1998.1441]
• 28: Anne Dinning , Edith Schonberg, Detecting access anomalies in programs with critical sections, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.85-96, May 20-21, 1991, Santa Cruz, California, United States
• 29: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.106-117, June 17-19, 1998, Montreal, Quebec, Canada
• 30: Evelyn Duesterwald , Mary Lou Soffa, Concurrency analysis in the presence of procedures using a data-flow framework, Proceedings of the symposium on Testing, analysis, and verification, p.36-48, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120811]
• 31: Matthew B. Dwyer , Lori A. Clarke, Data flow analysis for verifying properties of concurrent programs, Proceedings of the 2nd ACM SIGSOFT symposium on Foundations of software engineering, p.62-75, December 06-09, 1994, New Orleans, Louisiana, United States
• 32: 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
• 33: P. A. Emrath , S. Chosh , D. A. Padua, Event synchronization analysis for debugging parallel programs, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.580-588, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76329]
• 34: Perry A. Emrath , David A. Padua, Automatic detection of nondeterminacy in parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.89-99, May 05-06, 1988, Madison, Wisconsin, United States
• 35: 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
• 36: Cormac Flanagan , Martín Abadi, Types for Safe Locking, Proceedings of the 8th European Symposium on Programming Languages and Systems, p.91-108, March 22-28, 1999
• 37: Cormac Flanagan , Stephen N. Freund, Type-based race detection for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.219-232, June 18-21, 2000, Vancouver, British Columbia, Canada
• 38: 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
• 39: Patrice Godefroid , Pierre Wolper, A partial approach to model checking, Information and Computation, v.110 n.2, p.305-326, May 1, 1994
• 40: 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
• 41: 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
• 42: Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.254-263, June 2001, Snowbird, Utah, United States
• 43: 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]
• 44: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 45: Knoop, J. 1998. Code motion for explicitly parallel programs. In Proceedings of the 4th European Conference on Parallel Processing (Euro-Par'98), Southampton, UK.
• 46: Jens Knoop , Bernhard Steffen, Code motion for explicitly parallel programs, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.13-24, May 04-06, 1999, Atlanta, Georgia, United States
• 47: 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]
• 48: Arvind Krishnamurthy , Katherine Yelick, Optimizing parallel programs with explicit synchronization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.196-204, June 18-21, 1995, La Jolla, California, United States
• 49: Arvind Krishnamurthy , Katherine Yelick, Analyses and optimizations for shared address space programs, Journal of Parallel and Distributed Computing, v.38 n.2, p.130-144, Nov. 1, 1996 [doi>10.1006/jpdc.1996.0136]
• 50: 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
• 51: Jaejin Lee , Samuel P. Midkiff , David A. Padua, A Constant Propagation Algorithm for Explicitly Parallel Programs, International Journal of Parallel Programming, v.26 n.5, p.563-589, October 1998 [doi>10.1023/A:1018772514882]
• 52: Jaejin Lee , David A. Padua, Hiding Relaxed Memory Consistency with Compilers, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.111, October 15-19, 2000
• 53: Jaejin Lee , David A. Padua , Samuel P. Midkiff, Basic compiler algorithms for parallel programs, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 04-06, 1999, Atlanta, Georgia, United States
• 54: Douglas Long , Lori A. Clarke, Data flow analysis of concurrent systems that use the rendezvous model of synchronization, Proceedings of the symposium on Testing, analysis, and verification, p.21-35, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120810]
• 55: Masticola, S. and Ryder, B. 1990. Static infinite wait anomaly detection in polynomial time. In Proceedings of the 1990 International Conference on Parallel Processing, St. Charles, IL.
• 56: Stephen P. Masticola , Barbara G. Ryder, Non-concurrency analysis, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.129-138, May 19-22, 1993, San Diego, California, United States
• 57: John Mellor-Crummey, On-the-fly detection of data races for programs with nested fork-join parallelism, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.24-33, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125861]
• 58: Midkiff, S. and Padua, D. 1990. Issues in the optimization of parallel programs. In Proceedings of the 1990 International Conference on Parallel Processing, II--105--113.
• 59: Jong-Deok Choi , Sang Lyul Min, Race Frontier: reproducing data races in parallel-program debugging, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.145-154, April 21-24, 1991, Williamsburg, Virginia, United States
• 60: Csaba Andras Moritz , Matthew Frank , Saman P. Amarasinghe, FlexCache: A Framework for Flexible Compiler Generated Data Caching, Revised Papers from the Second International Workshop on Intelligent Memory Systems, p.135-146, November 12, 2000
• 61: Gleb Naumovich , George S. Avrunin, A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.24-34, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 62: Gleb Naumovich , George S. Avrunin , Lori A. Clarke, An efficient algorithm for computing MHP information for concurrent Java programs, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.338-354, September 06-10, 1999, Toulouse, France
• 63: Robert H. B. Netzer , Barton P. Miller, Improving the accuracy of data race detection, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.133-144, April 21-24, 1991, Williamsburg, Virginia, United States
• 64: 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]
• 65: John Hamilton Reppy, Higher-order concurrency, Cornell University, Ithaca, NY, 1992
• 66: Martin C. Rinard, Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitives, ACM Transactions on Computer Systems (TOCS), v.17 n.4, p.337-371, Nov. 1999 [doi>10.1145/329466.329486]
• 67: Martin C. Rinard, Analysis of Multithreaded Programs, Proceedings of the 8th International Symposium on Static Analysis, p.1-19, July 16-18, 2001
• 68: Atanas Rountev , Satish Chandra, Off-line variable substitution for scaling points-to analysis, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.47-56, June 18-21, 2000, Vancouver, British Columbia, Canada
• 69: 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
• 70: Erik Ruf, Effective synchronization removal for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.208-218, June 18-21, 2000, Vancouver, British Columbia, Canada
• 71: 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
• 72: Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.182-195, June 18-21, 2000, Vancouver, British Columbia, Canada
• 73: Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001 [doi>10.1145/383043.381532]
• 74: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.1-50, Jan. 1998 [doi>10.1145/271510.271517]
• 75: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 76: Vivek Sarkar, Analysis and Optimization of Explicitly Parallel Programs Using the Parallel Program Graph Representation, Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, p.94-113, August 07-09, 1997
• 77: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 78: 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]
• 79: Dennis Shasha , Marc Snir, Efficient and correct execution of parallel programs that share memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.282-312, April 1988 [doi>10.1145/42190.42277]
• 80: Harini Srinivasan , James Hook , Michael Wolfe, Static single assignment for explicitly parallel programs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.260-272, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158644]
• 81: Guy L. Steele, Jr., Making asynchronous parallelism safe for the world, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.218-231, December 1989, San Francisco, California, United States [doi>10.1145/96709.96731]
• 82: 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]
• 83: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 84: Sterling, N. 1994. Warlock: A static data race analysis tool. In Proceedings of the 1993 Winter Usenix Conference, San Diego, CA.
• 85: Richard N. Taylor, A general-purpose algorithm for analyzing concurrent programs, Communications of the ACM, v.26 n.5, p.361-376, May 1983 [doi>10.1145/69586.69587]
• 86: Chau-Wen Tseng, Compiler optimizations for eliminating barrier synchronization, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.144-155, July 19-21, 1995, Santa Barbara, California, United States
• 87: Antti Valmari, A Stubborn Attack On State Explosion, Proceedings of the 2nd International Workshop on Computer Aided Verification, p.156-165, June 18-21, 1990
• 88: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 89: 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
• 90: Yingchun Zhu , L. J. Hendren, Locality Analysis For Parallel C Programs, Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, p.2, November 11-15, 1997
• 91: 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:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

General Terms:
Algorithms, Experimentation, Languages, Measurement, Theory

Keywords:
Pointer analysis