Pattern-Based Peephole Optimizations with Java JIT Tests
Pages 64 - 75
Abstract
We present JOG, a framework that facilitates developing Java JIT peephole optimizations alongside JIT tests. JOG enables developers to write a pattern, in Java itself, that specifies desired code transformations by writing code before and after the optimization, as well as any necessary preconditions. Such patterns can be written in the same way that tests of the optimization are already written in OpenJDK. JOG translates each pattern into C/C++ code that can be integrated as a JIT optimization pass. JOG also generates Java tests for optimizations from patterns. Furthermore, JOG can automatically detect possible shadow relation between a pair of optimizations where the effect of the shadowed optimization is overridden by another. Our evaluation shows that JOG makes it easier to write readable JIT optimizations alongside tests without decreasing the effectiveness of JIT optimizations. We wrote 162 patterns, including 68 existing optimizations in OpenJDK, 92 new optimizations adapted from LLVM, and two new optimizations that we proposed. We opened eight pull requests (PRs) for OpenJDK, including six for new optimizations, one on removing shadowed optimizations, and one for newly generated JIT tests; seven PRs have already been integrated into the master branch of OpenJDK.
References
[1]
Gergö Barany. 2018. Finding Missed Compiler Optimizations by Differential Testing. In International Conference on Compiler Construction. ACM, 82–92. https://doi.org/10.1145/3178372.3179521
[2]
Gilles Barthe, Delphine Demange, and David Pichardie. 2014. Formal Verification of an SSA-Based Middle-End for CompCert. In Programming Language Design and Implementation. Association for Computing Machinery, 4:1–4:35. https://doi.org/10.1145/2579080
[3]
Richard Biener and Prathamesh Kulkarni. 2022. gcc/match.pd at master - gcc-mirror/gcc. https://github.com/gcc-mirror/gcc/blob/dcb4bd0/gcc/match.pd
[4]
Stephen M. Blackburn, Robin Garner, Chris Hoffmann, Asjad M. Khang, Kathryn S. McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z. Guyer, Martin Hirzel, Antony Hosking, Maria Jump, Han Lee, J. Eliot B. Moss, Aashish Phansalkar, Darko Stefanović, Thomas VanDrunen, Daniel von Dincklage, and Ben Wiedermann. 2006. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In International Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM, 169–190. https://doi.org/10.1145/1167473.1167488
[5]
Sebastian Buchwald. 2015. Optgen: A Generator for Local Optimizations. In International Conference on Compiler Construction. Springer, Berlin, Heidelberg. 171–189. https://doi.org/10.1007/978-3-662-46663-6_9
[6]
Raymond P.L. Buse and Westley R. Weimer. 2010. Learning a Metric for Code Readability. IEEE Transactions on Software Engineering, 36, 4 (2010), 546–558. https://doi.org/10.1109/TSE.2009.70
[7]
Nathanaël Courant and Xavier Leroy. 2021. Verified Code Generation for the Polyhedral Model. In Symposium on Principles of Programming Languages. ACM, 40:1–40:24. https://doi.org/10.1145/3434321
[8]
Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, 337–340. https://doi.org/10.1007/978-3-540-78800-3_24
[9]
Bradley Efron and Robert J. Tibshirani. 1994. An Introduction to the Bootstrap. CRC Press. isbn:9781000064988 https://books.google.com/books?id=MWC1DwAAQBAJ
[10]
Philip Ginsbach, Lewis Crawford, and Michael F. P. O’Boyle. 2018. CAnDL: A Domain Specific Language for Compiler Analysis. In International Conference on Compiler Construction. ACM, 151–162. https://doi.org/10.1145/3178372.3179515
[11]
James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, Daniel Smith, and Gavin Bierman. 2021. The Java® Language Specification. https://docs.oracle.com/javase/specs/jls/se17/jls17.pdf
[12]
He Jiang, Zhide Zhou, Zhilei Ren, Jingxuan Zhang, and Xiaochen Li. 2022. CTOS: Compiler Testing for Optimization Sequences of LLVM. IEEE Transactions on Software Engineering, 48, 7 (2022), 2339–2358. https://doi.org/10.1109/TSE.2021.3058671
[13]
Sudipta Kundu, Zachary Tatlock, and Sorin Lerner. 2009. Proving Optimizations Correct Using Parameterized Program Equivalence. In Programming Language Design and Implementation. ACM, 327–337. https://doi.org/10.1145/1542476.1542513
[14]
Sorin Lerner, Todd Millstein, and Craig Chambers. 2003. Automatically Proving the Correctness of Compiler Optimizations. In Programming Language Design and Implementation. ACM, 220–231. https://doi.org/10.1145/781131.781156
[15]
Sorin Lerner, Todd Millstein, Erika Rice, and Craig Chambers. 2005. Automated Soundness Proofs for Dataflow Analyses and Transformations via Local Rules. In Symposium on Principles of Programming Languages. ACM, 364–377. https://doi.org/10.1145/1040305.1040335
[16]
Xavier Leroy. 2009. Formal Verification of a Realistic Compiler. Commun. ACM, 52, 7 (2009), 107–115. https://doi.org/10.1145/1538788.1538814
[17]
LLVM Project. 2022. llvm-project/llvm/lib/Transforms/InstCombine at main - llvm/llvm-project. https://github.com/llvm/llvm-project/tree/b26e44e/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
[18]
LLVM Project. 2023. llvm/llvm-project: The LLVM Project is a collection of modular and reusable compiler and toolchain technologies. Note: the repository does not accept github pull requests at this moment. Please submit your patches at http://reviews.llvm.org. https://github.com/llvm/llvm-project
[19]
Nuno P. Lopes, David Menendez, Santosh Nagarakatte, and John Regehr. 2015. Provably Correct Peephole Optimizations with Alive. In Programming Language Design and Implementation. ACM, 22–32. https://doi.org/10.1145/2737924.2737965
[20]
Nuno P. Lopes and John Regehr. 2018. Future Directions for Optimizing Compilers. https://doi.org/10.48550/ARXIV.1809.02161
[21]
W. M. McKeeman. 1965. Peephole Optimization. Commun. ACM, 8, 7 (1965), 443–444. https://doi.org/10.1145/364995.365000
[22]
David Menendez and Santosh Nagarakatte. 2016. Termination-Checking for LLVM Peephole Optimizations. In International Conference on Software Engineering. ACM, 191–202. https://doi.org/10.1145/2884781.2884809
[23]
David Menendez, Santosh Nagarakatte, and Aarti Gupta. 2016. Alive-FP: Automated Verification of Floating Point Based Peephole Optimizations in LLVM. In Static Analysis. Springer, 317–337. https://doi.org/10.1007/978-3-662-53413-7_16
[24]
Steven S. Muchnick. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers. isbn:9781558603202
[25]
Eric Mullen, Daryl Zuniga, Zachary Tatlock, and Dan Grossman. 2016. Verified Peephole Optimizations for CompCert. In Programming Language Design and Implementation. ACM, 448–461. https://doi.org/10.1145/2908080.2908109
[26]
Naoki Nishida and Sarah Winkler. 2018. Loop Detection by Logically Constrained Term Rewriting. In Verified Software. Theories, Tools, and Experiments. Springer, 309–321. https://doi.org/10.1007/978-3-030-03592-1_18
[27]
Andres Nötzli and Fraser Brown. 2016. LifeJacket: Verifying Precise Floating-Point Optimizations in LLVM. In International Workshop on State Of the Art in Program Analysis. ACM, 24–29. https://doi.org/10.1145/2931021.2931024
[28]
Oracle and/or its affiliates. 2022. jdk/AddINodeIdealizationTests.java at master - openjdk/jdk - GitHub. https://github.com/openjdk/jdk/blob/master/test/hotspot/jtreg/compiler/c2/irTests/AddINodeIdealizationTests.java
[29]
Oracle and/or its affiliates. 2022. jdk/subnode.cpp at b334d96 - openjdk/jdk - GitHub. https://github.com/openjdk/jdk/blob/b334d96/src/hotspot/share/opto/subnode.cpp#L163
[30]
Oracle and/or its affiliates. 2022. jdk/test/hotspot/jtreg/compiler/lib/ir_framework at master - openjdk/jdk - GitHub. https://github.com/openjdk/jdk/tree/master/test/hotspot/jtreg/compiler/lib/ir_framework
[31]
Oracle and/or its affiliates. 2023. 8277882: New subnode ideal optimization: converting "c0 - (x + c1)" into "(c0 - c1) - x" - Pull Request #6441 - openjdk/jdk. https://github.com/openjdk/jdk/pull/6441
[32]
Oracle and/or its affiliates. 2023. 8278114: New addnode ideal optimization: converting "x + x" into "x << 1" - Pull Request #6675 - openjdk/jdk. https://github.com/openjdk/jdk/pull/6675
[33]
Oracle and/or its affiliates. 2023. 8278471: Remove unreached rules in AddNode::IdealIL - Pull Request #6752 - openjdk/jdk. https://github.com/openjdk/jdk/pull/6752
[34]
Oracle and/or its affiliates. 2023. 8279607: Existing optimization "∼x+1" -> x" can be generalized to "∼x+c" -> "(c-1)-x". - Pull Request #6858 - openjdk/jdk. https://github.com/openjdk/jdk/pull/6858
[35]
Oracle and/or its affiliates. 2023. 8281453: New optimization: convert ∼x into -1-x when ∼x is used in an arithmetic expression - Pull Request #7376 - openjdk/jdk. https://github.com/openjdk/jdk/pull/7376
[36]
Oracle and/or its affiliates. 2023. 8281518: New optimization: convert "(x|y)-(x∧y)" into "x&y" - Pull Request #7395 - openjdk/jdk. https://github.com/openjdk/jdk/pull/7395
[37]
Oracle and/or its affiliates. 2023. 8283094: Add Ideal transformation: x + (con - y) -> (x - y) + con - Pull Request #7795 - openjdk/jdk. https://github.com/openjdk/jdk/pull/7795
[38]
Oracle and/or its affiliates. 2023. 8297384: Add IR tests for existing idealizations of arithmetic nodes by CptGit - Pull Request #11049 - openjdk/jdk. https://github.com/openjdk/jdk/pull/11049
[39]
Oracle and/or its affiliates. 2023. jdk/addnode.cpp at b334d96 - openjdk/jdk - GitHub. https://github.com/openjdk/jdk/blob/b334d96/src/hotspot/share/opto/addnode.cpp#L358
[40]
Oracle and/or its affiliates. 2023. jdk/subnode.cpp at b334d96 - openjdk/jdk - GitHub. https://github.com/openjdk/jdk/blob/b334d96/src/hotspot/share/opto/subnode.cpp#L243
[41]
Oracle Corporation and/or its affiliates. 2023. JDK Bug System. https://bugs.openjdk.java.net/browse/JDK-8266601
[42]
Oracle Corporation and/or its affiliates. 2023. openjdk/jdk: JDK main-line development. https://github.com/openjdk/jdk
[43]
Aleksandar Prokopec, Andrea Rosà, David Leopoldseder, Gilles Duboscq, Petr Tůma, Martin Studener, Lubomír Bulej, Yudi Zheng, Alex Villazón, Doug Simon, Thomas Würthinger, and Walter Binder. 2019. Renaissance: Benchmarking Suite for Parallel Applications on the JVM. In Programming Language Design and Implementation. ACM, 31–47. https://doi.org/10.1145/3314221.3314637
[44]
Standard Performance Evaluation Corporation. 2022. SPECjvm2008. https://www.spec.org/jvm2008/
[45]
the GCC Developer Community. 2022. Match and Simplify. https://gcc.gnu.org/onlinedocs/gccint/match-and-simplify.html
[46]
Theodoros Theodoridis, Manuel Rigger, and Zhendong Su. 2022. Finding Missed Optimizations through the Lens of Dead Code Elimination. In International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, 697–709. https://doi.org/10.1145/3503222.3507764
[47]
Sruthi Venkat and Preet Kanwal. 2018. COpt: A High Level Domain-Specific Language to Generate Compiler Optimizers. In International Conference on Advanced Computation and Telecommunication. IEEE, 1–6. https://doi.org/10.1109/ICACAT.2018.8933593
[48]
Deborah L. Whitfield and Mary Lou Soffa. 1997. An Approach for Exploring Code Improving Transformations. ACM Trans. Program. Lang. Syst., 19, 6 (1997), 1053–1084. https://doi.org/10.1145/267959.267960
Index Terms
- Pattern-Based Peephole Optimizations with Java JIT Tests
Recommendations
JOG: Java JIT Peephole Optimizations and Tests from Patterns
ICSE-Companion '24: Proceedings of the 2024 IEEE/ACM 46th International Conference on Software Engineering: Companion ProceedingsWe present JOG, a framework for developing peephole optimizations and accompanying tests for Java compilers. JOG allows developers to write a peephole optimization as a pattern in Java itself. Such a pattern contains code before and after the desired ...
Java bytecode optimizations
COMPCON '97: Proceedings of the 42nd IEEE International Computer ConferenceWe present our results obtained from applying well known optimizations to Java bytecodes. We survey the optimizations implemented thus far, which include peephole optimizations, jump redundancy eliminations, and common subexpression elimination. The ...
Efficient interpreter optimizations for the JVM
PPPJ '13: Proceedings of the 2013 International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and ToolsThe Java virtual machine is a popular target for many language implementers. Due to the unusually poor performance of hosted interpreters, many programming language implementers resort to implementing a custom compiler that emits Java bytecode instead. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
1554 pages
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
ISSTA '23
Sponsor:
ISSTA '23: 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis
July 17 - 21, 2023
WA, Seattle, USA
Acceptance Rates
Overall Acceptance Rate 58 of 213 submissions, 27%
Upcoming Conference
ISSTA '25
- Sponsor:
- sigsoft
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 363Total Downloads
- Downloads (Last 12 months)237
- Downloads (Last 6 weeks)23
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in