Side-effect analysis with fast escape filter
Authors: 
Binxian Tao, Ju Qian, Xiaoyu ZhouAuthors Info & Claims
Pages 15 - 20
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
- Side-effect analysis with fast escape filter
Recommendations
Fast and precise points-to analysis
Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, ...
Parameterized object sensitivity for points-to analysis for Java
The goal of points-to analysis for Java is to determine the set of objects pointed to by a reference variable or a reference object field. We present object sensitivity, a new form of context sensitivity for flow-insensitive points-to analysis for Java. ...
Interprocedural side-effect analysis for incomplete object-oriented software modules
We introduce a new approach to computing interprocedural modification side effects for part of an object-oriented program (e.g., components, libraries or client modules). Our approach consists of first performing a whole-program points-to analysis to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2012
58 pages
ISBN:9781450314909
DOI:10.1145/2259051
- Conference Chairs:
- Eric Bodden,
- Laurie Hendren,
- Patrick Lam,
- Elena Sherman
Copyright © 2012 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 June 2012
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
PLDI '12
Sponsor:
PLDI '12: ACM SIGPLAN Conference on Programming Language Design and Implementation
June 14, 2012
Beijing, China
Acceptance Rates
Overall Acceptance Rate 11 of 11 submissions, 100%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 160Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in