Correctness of Partial Escape Analysis for Multithreading Optimization
Article No.: 9, Pages 1 - 6
Abstract
Compilers often use escape analysis to elide locking operations on thread-local data. Similarly, dynamic race detectors may use escape analysis to elide race checks on thread-local data. In this paper, we study the correctness of these two related optimizations when using a partial escape analysis, which identifies objects that are currently thread-local but that may later become thread-shared.
We show that lock elision based on partial escape analysis is unsound for the Java memory model. We also show that race check elision based on a partial escape analysis weakens the precision of dynamic race detectors. Finally, we prove that race check elision based on a partial escape analysis is sound with respect to this weakened, but still useful, notion of precision.
References
[1]
Sarita V. Adve and Kourosh Gharachorloo. 1996. Shared Memory Consistency Models: A Tutorial. IEEE Computer 29, 12 (1996), 66--76.
[2]
Bruno Blanchet. 1999. Escape Analysis for Object-Oriented Languages: Application to Java. In OOPSLA. 20--34.
[3]
Hans-Juergen Boehm and Sarita V. Adve. 2008. Foundations of the C++ concurrency memory model. In PLDI. 68--78.
[4]
Jong-Deok Choi, Manish Gupta, Mauricio J. Serrano, Vugranam C. Sreedhar, and Samuel P. Midkiff. 1999. Escape Analysis for Java. In OOPSLA. 1--19.
[5]
Jong-Deok Choi, Manish Gupta, Mauricio J. Serrano, Vugranam C. Sreedhar, and Samuel P. Midkiff. 2003. Stack allocation and synchronization optimizations for Java using escape analysis. ACM Trans. Program. Lang. Syst. 25, 6 (2003), 876--910.
[6]
Mark Christiaens and Koen De Bosschere. 2001. TRaDe: A Topological Approach to On-the-Fly Race Detection in Java Programs. In Proceedings of the 1st Java Virtual Machine Research and Technology Symposium, April 23-24, 2001, Monterey, CA, USA. 105--116.
[7]
Steve Dever, Steve Goldman, and Kenneth Russell. 2006. New Compiler Optimizations in the Java HotSpotffl Virtual Machine. In JavaOne Conference.
[8]
Pietro Ferrara. 2008. Static Analysis Via Abstract Interpretation of the Happens-Before Memory Model. In TAP. 116--133.
[9]
David Gay and Bjarne Steensgaard. 2000. Fast Escape Analysis and Stack Allocation for Object-Based Programs. In Compiler Construction, 9th International Conference. 82--93.
[10]
Emma Harrington and Stephen N Freund. 2014. Using Escape Analysis in Dynamic Data Race Detection. Williams College Technical Report CSTR 201401 (2014).
[11]
Jeremy Manson, William Pugh, and Sarita V. Adve. 2005. The Java memory model. In POPL. 378--391.
[12]
Mayur Naik, Alex Aiken, and John Whaley. 2006. Effective static race detection for Java. In PLDI. 308--319.
[13]
Hiroyasu Nishiyama. 2004. Detecting Data Races Using Dynamic Escape Analysis Based on Read Barrier. In Proceedings of the 3rd Virtual Machine Research and Technology Symposium. 127--138.
[14]
Michael Paleczny, Christopher A. Vick, and Cliff Click. 2001. The Java HotSpot Server Compiler. In Proceedings of the 1st Java Virtual Machine Research and Technology Symposium, April 23-24, 2001, Monterey, CA, USA.
[15]
Alexandru Salcianu and Martin C. Rinard. 2001. Pointer and escape analysis for multithreaded programs. In PPOPP. 12--23.
[16]
Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas E. Anderson. 1997. Eraser: A Dynamic Data Race Detector for Multithreaded Programs. ACM Trans. Comput. Syst. 15, 4 (1997), 391--411.
[17]
Jaroslav Sevcík and David Aspinall. 2008. On Validity of Program Transformations in the Java Memory Model. In ECOOP. 27--51.
[18]
Ajeet Shankar, Matthew Arnold, and Rastislav Bodík. 2008. Jolt: lightweight dynamic analysis and removal of object churn. In OOPSLA. 127--142.
[19]
Lukas Stadler, Thomas Würthinger, and Hanspeter Mössenböck. 2014. Partial escape analysis and scalar replacement for Java. In Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization. ACM, 165.
[20]
Christoph von Praun and Thomas R. Gross. 2001. Object Race Detection. In OOPSLA. 70--82.
[21]
Jan Wen Voung, Ranjit Jhala, and Sorin Lerner. 2007. RELAY: static race detection on millions of lines of code. In SIGSOFT. 205--214.
[22]
John Whaley and Martin C. Rinard. 1999. Compositional Pointer and Escape Analysis for Java Programs. In OOPSLA. 187--206.
Index Terms
- Correctness of Partial Escape Analysis for Multithreading Optimization
Recommendations
Inlining-Benefit Prediction with Interprocedural Partial Escape Analysis
VMIL 2022: Proceedings of the 14th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate LanguagesInlining is the primary facilitating mechanism for intraprocedural Partial Escape Analysis (PEA), which allows for the removal of object allocations on a branch-by-branch basis and is critical for performance in object-oriented languages. Prior work ...
Partial Escape Analysis and Scalar Replacement for Java
CGO '14: Proceedings of Annual IEEE/ACM International Symposium on Code Generation and OptimizationEscape Analysis allows a compiler to determine whether an object is accessible outside the allocating method or thread. This information is used to perform optimizations such as Scalar Replacement, Stack Allocation and Lock Elision, allowing modern ...
Side-effect analysis with fast escape filter
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysisSide-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, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2017
49 pages
ISBN:9781450350983
DOI:10.1145/3103111
Copyright © 2017 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 the author(s) 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].
In-Cooperation
- SIGPLAN: ACM Special Interest Group on Programming Languages
- AITO: Assoc Internationale por les Technologies Objects
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 June 2017
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ECOOP '17
Acceptance Rates
FTFJP'17 Paper Acceptance Rate 10 of 12 submissions, 83%;
Overall Acceptance Rate 51 of 75 submissions, 68%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 67Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Nov 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