Instance-wise points-to analysis for loop-based dependence testing

ABSTRACT

We present a points-to analysis that aims at enabling loop-based dependence analysis in the presence of Java references. The analysis is based on an abstraction called element-wise points-to (ewpt) mapping. An ewpt mapping summarizes, in a compact representation, the relation between a pointer and the heap object it points to, for every instance of the pointer inside a loop and for every array element directly accessible through this pointer. Such instance-wise and element-wise information is especially important for loop-based dependence analyses and for a language where multi-dimensional arrays are implemented as arrays of pointers. We describe an iterative algorithm to compute ewpt mappings. We also present techniques to remove objects from ewpt mappings for destructive updates.The points-to algorithm was implemented and evaluated on a set of benchmark programs. We demonstrate that ewpt information can significantly improve the precision of dependence analysis. In many cases, the dependence analysis reports no false dependences due to array accesses.

References

1. Rastislav Bodik, Ragiv Gupta, and Vivek Sarkar. ABCD: Eliminating array bounds checks on demand. In ACM Symp. on Programming Language Design and Implementation, June 2000]]
2. C. Chambers, I. Pechtchanski, V. Sarkar, M. Serrano, and H. Srinivasan. Dependence analysis for Java. In Workshop on Languages and Compilers for Parallel Computing, August 1999]]
3. Ben-Chung Cheng and Wen mei Hwu. Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation. In ACM Symp. on Programming Language Design and Implementation, pages 57--69, June 2000]]
4. Jong-Deok Choi, Michael Burke, and Paul Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In ACM Symp. on Principles of Programming Languages, pages 232--245, 1993]]
5. Albert Cohen, Peng Wu, and David Padua. Pointer analysis for monotonic container traversals. Technical Report CSRD 1586, University of Illinois at Urbana-Champaign, January 2001]]
6. Alain Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In ACM Symp. on Programming Language Design and Implementation, June 1994]]
7. A. Diwan, K.S. McKinley, and E.B. Moss. Type-based alias analysis. In ACM Symp. on Programming Language Design and Implementation, June 1998]]
8. Rakesh Ghiya and Laurie J. Hendren. Connection analysis: A practical interprocedural heap analysis for C. In Workshop on Languages and Compilers for Parallel Computing. Springer-Verlag, 1995]]
9. Rakesh Ghiya and Laurie J. Hendren. Putting pointer analysis to work. In ACM Symp. on Principles of Programming Languages, January 1998]]
10. Laurie J. Hendren and Alexandru Nicolau. Parallelizing programs with recursive data structures. In IEEE Trans. on Parallel and Distributed Computing, January 1990]]
11. Joseph Hummel, Laurie~J. Hendren, and Alex Nicolau. A general data dependence test for dynamic, pointer-based data structures. In ACM Symp. on Programming Language Design and Implementation, June 1994]]
12. Joseph Hummel, Laurie~J. Hendren, and Alex Nicolau. A language for conveying the alising properties of dynamic, pointer-based data structures. In Inthernational Parallel Processing Symposium, pages 208--216, April 1994]]
13. J. Larus and P. Hilfinger. Detecting conflicts between structure accesses. In ACM Symp. on Programming Language Design and Implementation, Atlanta, GA, June 1988]]
14. J. E. Moreira, S. P. Midkiff, and M. Gupta. From flop to megaflops: Java for technical computing. ACM Trans. on Programming Languages and Systems, 22(2):265--295, March 2000]]
15. William Pugh. The Omega test: A fast and practical integer programming algorithm for dependence analysis. In Supercomputing, 1991]]
16. Radu Rugina and Martin Rinart. Symbolic bound analysis of pointers, array indices and accessed memory regions. In PLDI'2000. ACM, 2000]]
17. M. Sagiv, T. Reps, and R. Wilhelm. Solving shape analysis problems in languages with destructive updating. In ACM Symp. on Principles of Programming Languages, January 1996]]
18. B. Steensgaard. Points-to analysis in almost linear time. In ACM Symp. on Principles of Programming Languages, January 1996]]
19. R. Wilson and M. Lam. Efficient context-sensitive pointer analysis for C programs. In ACM Symp. on Programming Language Design and Implementation, June 1995]]
20. Peng Wu. Analyses of pointers, induction variables, and container objects for dependence testing. Technical Report UIUCDCS-R-2001-2209, University of Illinois at Urbana-Champaign, May 2001. Ph.D Thesis]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers