Side-effect analysis with fast escape filter

ABSTRACT

Side-effect analysis is a fundamental static analysis used to determine the memory locations modified or used by each program entity. For the programs with pointers, the analysis can be very imprecise. To improve the precision of side-effect analysis, many approaches design more elaborate background pointer analyses in order to obtain smaller side-effect sets, but very few approaches consider to achieve better precisions by refining the side-effect analysis algorithms themselves. To address the problem, this paper presents a new side-effect analysis approach that uses Gay and Steensgaard's fast escape analysis to filter superfluous side-effects. The approach does not need to modify the background pointer analysis and can filter side-effects in the intraprocedural level and the interprocedural level. The experimental results show that it can effectively improve the analysis precision within a short extra time.

References

1. Ashes suite collection. http://www.sable.mcgill.ca/software.
2. SPEC JVM2008 benchmarks. http://www.spec.org/jvm2008/.
3. M. Q. Beers, C. H. Stork, and M. Franz. Efficiently Verifiable Escape Analysis. In European Conference on Object-Oriented Programming (ECOOP), 2004, LNCS, Vol. 3086/2004, pp. 60--81.
4. S. M. Blackburn, R. Garner, and C. Hoffman et al. The DaCapo benchmarks: Java benchmarking development and analysis. In ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications, 2006.
5. B. Blanchet. Escape analysis for object oriented languages: application to Java. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 1999.
6. J. Bogda and U. Hölzle. Removing unnecessary synchronization in Java. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 1999, pp. 35--46.
7. S. Cherem and R Rugina. A practical escape and effect analysis for building lightweight method summaries. In International Conference on Compiler Construction, 2007.
8. J.-D. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midkiff. Escape analysis for Java. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 1999, pp. 1--19.
9. L. R. Clausen. A java bytecode optimizer using side-effect analysis. Concurrency: Practice and Experience, 9(11): 1031--1045, 1997.
10. C. Click. Global code motion/global value numbering. In Proccedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 1995.
11. K. D. Cooper and K. Kennedy. Interprocedural side-effect analysis in linear time. In Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI), 1988, pp. 57--66.
12. M. Edvinsson, J. Lundberg, W. Lowe. Parallel reachability and escape analyses. In 10th IEEE International Workshop on Source Code Analysis and Manipulation (SCAM), pp. 125--134, 2010.
13. A. Flexeder, M. Petter and H. Seidl. Side-effect analysis of assembly code. In 18th International Symposium on Static Analysis (SAS), 2011.
14. D. Gay and B. Steensgaard. Fast escape analysis and stack allocation for object-based programs. In Proceedings of the 9th International Conference on Compiler Construction, 2000, pp. 82--93.
15. M. Hind. Pointer analysis: Haven't we solved this problem yet? In ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, 2001.
16. A. Le, O. Lhoták, and L. Hendren. Using inter-procedural side-effect information in jit optimizations. In International Conference on Compiler Construction, 2005.
17. K. Lee, X. Fang, and S. P. Midkiff. Practical escape analyses: how good are they? In Proceedings of the 3rd International Conference on Virtual Execution Environments (VEE), pp. 180--190, 2007.
18. O. Lhoták and L. Hendren. Scaling java points-to analysis using spark. In International Conference on Compiler Construction, 2003.
19. A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to analysis for java. ACM Trans. on Software Engineering and Methodology, 14(1):1--41, 2005.
20. M. Naik. Effective Static race detection for Java. PhD thesis, Stanford University, 2008.
21. N. Nystrom, M. R. Clarkson, and A. C. Myers. Polyglot:An extensible compiler framework for java. In International Conference on Compiler Construction, 2003.
22. J. Qian, B. Xu, and H. Min. Interstatement must aliases for data dependence analysis of heap locations. In ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, 2007.
23. J. Qian, Y. Zhou, B. Xu. Improving Side-Effect Analysis with Lazy Access Path Resolving. In 9th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM), 2009, pp. 35--44.
24. C. Razafimahefa. A study of side-effect analyses for java. Master's thesis, McGill University, Dec. 1999.
25. A. Rountev. Precise identification of side-effect-free methods in java. In Proceedings of the 20th International Conference on Software Maintenance, 2004.
26. B. G. Ryder, W. Landi, P. Stocks, S. Zhang, and R. Altucher. A schema for interprocedural modification side-effect analysis with pointer aliasing. ACM Transaction on Programming Languages and System, 23(2):105--186, 2001.
27. A. Sălcianu and M. Rinard. Purity and side effect analysis for java programs. In International Conference on Verification Model Checking, and Abstract Interpretation, 2005.
28. R. Vallée-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Cot. Soot -- a java optimization framework. In IBM Centre for Advanced Studies Conference (CASCON), 1999.
29. J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Proceedings of the 14th ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), 1999, pp. 187--206.
30. J. Xue, P. H. Nguyen, and J. Potter. Interprocedural side-effect analysis for incomplete object-oriented software modules. Journal of Systems and Software, 80(1):92--105, 2007.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers