Pointer analysis of multithreaded Java programs

ABSTRACT

This paper presents a context-sensitive and path-sensitive, intra-thread and inter-thread solution to combined pointer analysis, escape analysis and data dependence analysis of multithreaded Java programs which uses a sparse representation. We build and maintain a complete Static Single Assignment (SSA) form even for fields variables. We show how to compute inter-thread dependencies for multithreaded programs with structured fork-join constructs, open-ended threads, recursively generated threads, monitors, and wait-notify synchronization. We have implemented our algorithm in a slicer for Java programs. Our experimental results show that a sparse representation improves the analysis time and strong updates on field variables improves the precision.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: 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
• 3: 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
• 4: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 5: Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.36-45, June 21-25, 1993, Albuquerque, New Mexico, United States
• 6: Rakesh Ghiya , Laurie J. Hendren, Connection analysis: a practical interprocedural heap analysis for C, International Journal of Parallel Programming, v.24 n.6, p.547-578, Dec. 1996
• 7: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 8: 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]
• 9: Mangala Gowri Nanda , S. Ramesh, Slicing concurrent programs, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.180-190, August 21-24, 2000, Portland, Oregon, United States
• 10: Diego Novillo , Ronald C. Unrau , Jonathan Schaeffer, Concurrent SSA Form in the Presence of Mutual Exclusion, Proceedings of the 1998 International Conference on Parallel Processing, p.356, August 10-14, 1998
• 11: 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
• 12: 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
• 13: 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
• 14: 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
• 15: 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

Keywords:
SSA, multithreaded pointer analysis, path-sensitive