Pointer analysis for multithreaded programs
Radu Rugina, Martin Rinard · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1999
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. 1
Cited by 133 works. doi:10.1145/301618.301645
Authors
References
- Eraser
- Points-to analysis in almost linear time
- The implementation of the Cilk-5 multithreaded language
- Efficient context-sensitive pointer analysis for C programs
- Context-sensitive interprocedural points-to analysis in the presence of function pointers
- Efficient context-sensitive pointer analysis for C programs
- A safe approximate algorithm for interprocedural aliasing
- Proceedings of the 2000 International Conference on Parallel Processing
- Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
- A safe approximate algorithm for interprocedural pointer aliasing