MEA2: A Lightweight Field-Sensitive Escape Analysis with Points-to Calculation for Golang
Article No.: 319, Pages 1362 - 1389
Abstract
Escape analysis plays a crucial role in garbage-collected languages as it enables the allocation of non-escaping variables on the stack by identifying the dynamic lifetimes of objects and pointers. This helps in reducing heap allocations and alleviating garbage collection pressure. However, Go, as a garbage-collected language, employs a fast yet conservative escape analysis, which is field-insensitive and omits point-to-set calculation to expedite compilation. This results in more variables being allocated on the heap. Empirical statistics reveal that field access and indirect memory access are prevalent in real-world Go programs, suggesting potential opportunities for escape analysis to enhance program performance. In this paper, we propose MEA2, an escape analysis framework atop GoLLVM (an LLVM-based Go compiler), which combines field sensitivity and points-to analysis. Moreover, a novel generic function summary representation is designed to facilitate fast inter-procedural analysis. We evaluated it by using MEA2 to perform stack allocation in 12 wildly-use open-source projects. The results show that, compared to Go’s escape analysis, MEA2 can reduce heap allocation sites by 7.9
References
[1]
Mina Andrawos and Martin Helmich. 2017. Cloud Native Programming with Golang: Develop microservice-based high performance web apps for the cloud with Go. Packt Publishing Ltd.
[2]
George Balatsouras and Yannis Smaragdakis. 2016. Structure-Sensitive Points-To Analysis for C and C++. In Static Analysis, Xavier Rival (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 84–104. isbn:978-3-662-53413-7
[3]
Mohamad Barbar, Yulei Sui, and Shiping Chen. 2021. Object Versioning for Flow-Sensitive Pointer Analysis. In 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO). 222–235. https://doi.org/10.1109/CGO51591.2021.9370334
[4]
Matthew Q. Beers, Christian H. Stork, and Michael Franz. 2004. Efficiently Verifiable Escape Analysis. In ECOOP 2004 – Object-Oriented Programming, Martin Odersky (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 75–95. isbn:978-3-540-24851-4
[5]
Bruno Blanchet. 1998. Escape Analysis: Correctness Proof, Implementation and Experimental Results. In [25th]POPLACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’98). Association for Computing Machinery, New York, NY, USA. 25–37. isbn:0897919793 https://doi.org/10.1145/268946.268949
[6]
Bruno Blanchet. 1999. Escape Analysis for Object-Oriented Languages: Application to Java. In [14th]OOPSLAACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’99). Association for Computing Machinery, New York, NY, USA. 20–34. isbn:1581132387 https://doi.org/10.1145/320384.320387
[7]
Jinbao Chen, Yu Zhang, Qingwei Li, and Boyao Ding. 2024. DBI-Go: Dynamic Binary Instrumentation for Pinpointing Illegal Memory References in Go Binaries. Journal of Software, 35, 6 (2024), 0–0.
[8]
Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. 1999. Escape Analysis for Java. In [14th]OOPSLAACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’99). Association for Computing Machinery, New York, NY, USA. 1–19. isbn:1581132387 https://doi.org/10.1145/320384.320386
[9]
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), nov, 876–910. issn:0164-0925 https://doi.org/10.1145/945885.945892
[10]
danscalesr. 2022. proposal: arena: new package providing memory arenas. https://github.com/golang/go/issues/51317
[11]
Alain Deutsch. 1997. On the Complexity of Escape Analysis. In [24th]POPLACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’97). Association for Computing Machinery, New York, NY, USA. 358–371. isbn:0897918533 https://doi.org/10.1145/263699.263750
[12]
David Gay and Bjarne Steensgaard. 2000. Fast Escape Analysis and Stack Allocation for Object-Based Programs. In Compiler Construction, David A. Watt (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 82–93. isbn:978-3-540-46423-5
[13]
Ben Hardekopf and Calvin Lin. 2009. Semi-Sparse Flow-Sensitive Pointer Analysis. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’09). Association for Computing Machinery, New York, NY, USA. 226–238. isbn:9781605583792 https://doi.org/10.1145/1480881.1480911
[14]
Ben Hardekopf and Calvin Lin. 2011. Flow-Sensitive Pointer Analysis for Millions of Lines of Code. In International Symposium on Code Generation and Optimization (CGO 2011). 289–298. https://doi.org/10.1109/CGO.2011.5764696
[15]
https://github.com/JX-Zhang98 2021. Gollvm: Some existing defects.
[16]
Thomas Kotzmann and Hanspeter Mössenböck. 2005. Escape Analysis in the Context of Dynamic Compilation and Deoptimization. In Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments (VEE ’05). Association for Computing Machinery, New York, NY, USA. 111–120. isbn:1595930477 https://doi.org/10.1145/1064979.1064996
[17]
Thomas Kotzmann and Hanspeter Mossenbock. 2007. Run-Time Support for Optimizations Based on Escape Analysis. In International Symposium on Code Generation and Optimization (CGO’07). 49–60. https://doi.org/10.1109/CGO.2007.34
[18]
Clemens Lang and Isabella Stilkerich. 2020. Design and Implementation of an Escape Analysis in the Context of Safety-Critical Embedded Systems. ACM Trans. Embed. Comput. Syst., 19, 1 (2020), Article 6, feb, 20 pages. issn:1539-9087 https://doi.org/10.1145/3372133
[19]
Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the International Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization (CGO ’04). IEEE Computer Society, USA. 75. isbn:0769521029
[20]
Kyungwoo Lee and Samuel P. Midkiff. 2006. A Two-Phase Escape Analysis for Parallel Java Programs. In [15th]PACTInternational Conference on Parallel Architectures and Compilation Techniques (PACT ’06). Association for Computing Machinery, New York, NY, USA. 53–62. isbn:159593264X https://doi.org/10.1145/1152154.1152166
[21]
Yuxiang Lei and Yulei Sui. 2019. Fast and Precise Handling of Positive Weight Cycles for Field-Sensitive Pointer Analysis. In Static Analysis, Bor-Yuh Evan Chang (Ed.). Springer International Publishing, Cham. 27–47. isbn:978-3-030-32304-2
[22]
Ondrej Lhoták and Kwok-Chiang Andrew Chung. 2011. Points-to Analysis with Efficient Strong Updates. In [38th]POPLAnnual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’11). Association for Computing Machinery, New York, NY, USA. 3–16. isbn:9781450304900 https://doi.org/10.1145/1926385.1926389
[23]
Lian Li, Cristina Cifuentes, and Nathan Keynes. 2011. Boosting the Performance of Flow-Sensitive Points-to Analysis using Value Flow. In [13th]ESEC/FSEACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering (ESEC/FSE ’11). Association for Computing Machinery, New York, NY, USA. 343–353. isbn:9781450304436 https://doi.org/10.1145/2025113.2025160
[24]
Than McIntosh. 2018. gollvm - Git at Google. https://go.googlesource.com/gollvm/ Online; accessed 20-Sept-2018
[25]
Young Gil Park and Benjamin Goldberg. 1991. Reference escape analysis: optimizing reference counting based on the lifetime of references. SIGPLAN Not., 26, 9 (1991), may, 178–189. issn:0362-1340 https://doi.org/10.1145/115866.115883
[26]
Young Gil Park and Benjamin Goldberg. 1992. Escape Analysis on Lists. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation (PLDI ’92). Association for Computing Machinery, New York, NY, USA. 116–127. isbn:0897914759 https://doi.org/10.1145/143095.143125
[27]
David J. Pearce, Paul H.J. Kelly, and Chris Hankin. 2007. Efficient Field-Sensitive Pointer Analysis of C. ACM Trans. Program. Lang. Syst., 30, 1 (2007), nov, 4–es. issn:0164-0925 https://doi.org/10.1145/1290520.1290524
[28]
Prakash Prabhu and Priti Shankar. 2008. Field Flow Sensitive Pointer and Escape Analysis for Java Using Heap Array SSA. In Static Analysis, María Alpuente and Germán Vidal (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 110–127. isbn:978-3-540-69166-2
[29]
G. Salagnac, S. Yovine, and D. Garbervetsky. 2005. Fast Escape Analysis for Region-based Memory Management. Electronic Notes in Theoretical Computer Science, 131 (2005), 99–110. issn:1571-0661 https://doi.org/10.1016/j.entcs.2005.01.026 Proceedings of the First International Workshop on Abstract Interpretation of Object-oriented Languages (AIOOL 2005)
[30]
Alexandru Salcianu and Martin Rinard. 2001. Pointer and Escape Analysis for Multithreaded Programs. In Proceedings of the Eighth ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming (PPoPP ’01). Association for Computing Machinery, New York, NY, USA. 12–23. isbn:1581133464 https://doi.org/10.1145/379539.379553
[31]
Paul Menage Sanjay Ghemawat. 2007. TCMalloc: Thread-Caching Malloc. http://goog-perftools.sourceforge.net/doc/tcmalloc.html
[32]
Lukas Stadler, Thomas Würthinger, and Hanspeter Mössenböck. 2018. Partial Escape Analysis and Scalar Replacement for Java. In Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO ’14). Association for Computing Machinery, New York, NY, USA. 165–174. isbn:9781450326704 https://doi.org/10.1145/2544137.2544157
[33]
Isabella Stilkerich, Clemens Lang, Christoph Erhardt, Christian Bay, and Michael Stilkerich. 2017. The Perfect Getaway: Using Escape Analysis in Embedded Real-Time Systems. ACM Trans. Embed. Comput. Syst., 16, 4 (2017), Article 99, may, 30 pages. issn:1539-9087 https://doi.org/10.1145/3035542
[34]
Isabella Stilkerich, Clemens Lang, Christoph Erhardt, and Michael Stilkerich. 2015. A Practical Getaway: Applications of Escape Analysis in Embedded Real-Time Systems. In Proceedings of the 16th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2015 CD-ROM (LCTES’15). Association for Computing Machinery, New York, NY, USA. Article 4, 11 pages. isbn:9781450332576 https://doi.org/10.1145/2670529.2754961
[35]
Yulei Sui and Jingling Xue. 2016. SVF: Interprocedural Static Value-Flow Analysis in LLVM. In Proceedings of the 25th International Conference on Compiler Construction (CC 2016). Association for Computing Machinery, New York, NY, USA. 265–266. isbn:9781450342414 https://doi.org/10.1145/2892208.2892235
[36]
Ian Lance Taylor. 2014. A Go frontend. https://github.com/golang/gofrontend
[37]
Ian Lance Taylor. 2022. Definitions for the Go runtime functions. https://github.com/golang/gofrontend/blob/master/go/runtime.def
[38]
Isabella Thomm, Michael Stilkerich, Christian Wawersich, and Wolfgang Schröder-Preikschat. 2010. KESO: an Open-Source Multi-JVM for Deeply Embedded Systems. In [8th]JTRESInternational Workshop on Java Technologies for Real-Time and Embedded Systems (JTRES ’10). Association for Computing Machinery, New York, NY, USA. 109–119. isbn:9781450301220 https://doi.org/10.1145/1850771.1850788
[39]
Dmitry Vyukov. 2015. Go Escape Analysis Flaws. https://docs.google.com/document/d/1CxgUBPlx9iJzkz9JWkb6tIpTe5q32QDmz8l0BouG0Cw/edit
[40]
Cong Wang, Mingrui Zhang, Yu Jiang, Huafeng Zhang, Zhenchang Xing, and Ming Gu. 2020. Escape from Escape Analysis of Golang. In Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP ’20). Association for Computing Machinery, New York, NY, USA. 142–151. isbn:9781450371230 https://doi.org/10.1145/3377813.3381368
[41]
John Whaley and Martin Rinard. 1999. Compositional Pointer and Escape Analysis for Java Programs. In [14th]OOPSLAACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’99). Association for Computing Machinery, New York, NY, USA. 187–206. isbn:1581132387 https://doi.org/10.1145/320384.320400
Index Terms
- MEA2: A Lightweight Field-Sensitive Escape Analysis with Points-to Calculation for Golang
Recommendations
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, ...
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, ...
Practical escape analyses: how good are they?
VEE '07: Proceedings of the 3rd international conference on Virtual execution environmentsA key analysis developed for the compilation of parallel programs is thread escape analysis (hereafter referred to as escape analysis), which determines what objects are accessed in more than one thread, and which references within a program are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2024
2691 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 October 2024
Published in PACMPL Volume 8, Issue OOPSLA2
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Natural Science Foundation of China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 167Total Downloads
- Downloads (Last 12 months)167
- Downloads (Last 6 weeks)151
Reflects downloads up to 25 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