Pointer analysis for structured parallel programs
- 1 January 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 25 (1), 70-116
- https://doi.org/10.1145/596980.596982
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.Keywords
This publication has 67 references indexed in Scilit:
- A schema for interprocedural modification side-effect analysis with pointer aliasingACM Transactions on Programming Languages and Systems, 2001
- Effective fine-grain synchronization for automatically parallelized programs using optimistic synchronization primitivesACM Transactions on Computer Systems, 1999
- Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based ProgramsJournal of Parallel and Distributed Computing, 1998
- Solving shape-analysis problems in languages with destructive updatingACM Transactions on Programming Languages and Systems, 1998
- EraserACM Transactions on Computer Systems, 1997
- Parallelism for freeACM Transactions on Programming Languages and Systems, 1996
- Evaluating deadlock detection methods for concurrent softwareIEEE Transactions on Software Engineering, 1996
- Using symbolic execution for verification of Ada tasking programsACM Transactions on Programming Languages and Systems, 1990
- Efficient and correct execution of parallel programs that share memoryACM Transactions on Programming Languages and Systems, 1988
- A general-purpose algorithm for analyzing concurrent programsCommunications of the ACM, 1983