The Task of Automatic Generation of Peephole-Optimizations
Approaches Overview, Solution of the Optimal Expansion of Managed Instructions Set Architecture
Abstract
This article discusses the problem of automatic generation of peephole-optimization of the static bytecode optimizer of a virtual machine (VM) concerning the task of improving the instruction set architecture (ISA) of the VM.
Peephole optimization is one of the stages of the optimizing compiler. It applies to the code of the original input program in an intermediate representation (IR or LLIR) and resides in finding sequences of instructions that match known templates and replacing them with shorter or faster semantically equivalent sequences. The current peephole optimization approaches assume some limited set of templates or functions that are manually encoded while relying on the engineers' in-depth knowledge of the corresponding IR and the structure of the compiler output programs. Also, for various IRs you must re-encode similar peephole optimizations, which entails additional monetary and time costs.
An alternative approach is superoptimization, which consists of the automatic generation of templates and their matching rules. Among the main parts of the superoptimizer there are the search algorithm, the cost function, and the equivalence verifier.
In the article algorithm for solving a more specialized subtask was implemented and tested. It consists in finding and counting the most frequent instruction templates, which can later be replaced with one new instruction to optimize execution time and/or bytecode size or be analyzed by a programmer to investigate the weaknesses of the existing ISA and obtain information about the specifics of the source data.
References
2. Tanenbaum A.S., Van Staveren H., Stevenson J.W. Using Peephole Optimization on Intermediate Code. ACM Transactions on Programming Languages and Systems. 1982; 4(1):21-36. (In Eng.) DOI: https://doi.org/10.1145/357153.357155
3. McKeeman W.M. Peephole optimization. Communications of the ACM. 1965; 8(7):443-444. (In Eng.) DOI: https://doi.org/10.1145/364995.365000
4. Lopes N.P., Regehr J. Future Directions for Optimizing Compilers. arXiv:1809.02161. 2018. (In Eng.) DOI: https://doi.org/10.48550/arXiv.1809.02161
5. Bhatt C.H., Bhadka H.B. Peephole Optimization Technique for analysis and review of Compile Design and Construction. IOSR Journal of Computer Engineering (IOSR-JCE). 2013; 9(4):80-86. (In Eng.) DOI: https://doi.org/10.9790/0661-0948086
6. Lamb D.A. Construction of a peephole optimizer. Software: Practice and Experience. 1981; 11(6):639-647. (In Eng.) DOI: https://doi.org/10.1002/spe.4380110608
7. Massalin H. Superoptimizer: a look at the smallest program. ACM SIGARCH Computer Architecture News. 1987; 15(5):122-126. (In Eng.) DOI: https://doi.org/10.1145/36206.36194
8. Sasnauskas R., et al. Souper: A Synthesizing Superoptimizer. arXiv:1711.04422. 201 8. (In Eng.) DOI: https://doi.org/10.48550/arXiv.1711.04422
9. Davidson J.W., Fraser C.W. The design and application of a retargetable peephole optimizer. ACM Transactions on Programming Languages and Systems. 1980; 2(2):191-202. (In Eng.) DOI: https://doi.org/10.1145/357094.357098
10. Fraser C.W. A compact, machine-independent peephole optimizer. Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages (POPL '79). Association for Computing Machinery, New York, NY, USA; 1979. p. 1-6. (In Eng.) DOI: https://doi.org/10.1145/567752.567753
11. Chakraborty P. Fifty years of peephole optimization. Current Science. 2015; 108(12):2186-2190. Available at: https://www.jstor.org/stable/24905654 (accessed 03.08.2021). (In Eng.)
12. Hickey J., Nogin A. Formal compiler construction in a logical framework. Higher-Order and Symbolic Computation. 2006; 19(2-3):197-230. (In Eng.) DOI: https://doi.org/10.1007/s10990-006-8746-6
13. Heberle A., Gaul T., Goerigk W., Goos G., Zimmermann W. Construction of Verified Compiler Front-Ends with Program-Checking. In: Ed. by D. Bjøner, M. Broy, A.V. Zamulin. Perspectives of System Informatics. PSI 1999. Lecture Notes in Computer Science. 2000; 1755:481 -492. Springer, Berlin, Heidelberg. (In Eng.) DOI: https://doi.org/10.1007/3-540-46562-6_43
14. Davidson J.W., Fraser C.W. Automatic generation of peephole optimizations. Proceedings of the 1984 SIGPLAN symposium on Compiler construction (SIGPLAN '84). Association for Computing Machinery, New York, NY, USA; 1984. p. 111-116. (In Eng.) DOI: https://doi.org/10.1145/502874.502885
15. Granlund T., Kenner R. Eliminating branches using a superoptimizer and the GNU C compiler. ACM SIGPLAN Notices. 1992; 27(7):341-352. (In Eng.) DOI: https://doi.org/10.1145/143103.143146
16. Leidel J., Kabrick R., Donofrio D. Toward an Automated Hardware Pipelining LLVM Pass Infrastructure. 2021 IEEE/ACM 7th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC). IEEE Press, St. Louis, MO, USA; 2021. p. 39-49. (In Eng.) DOI: https://doi.org/10.1109/LLVMHPC54804.2021.00010
17. Davidson J.W., Fraser C.W. Automatic generation of peephole optimizations. ACM SIGPLAN Notices. 2004; 39(4):104-111. (In Eng.) DOI: https://doi.org/10.1145/989393.989407
18. Menendez D., Nagarakatte S. Alive-Infer: data-driven precondition inference for peephole optimizations in LLVM. Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2017). Association for Computing Machinery, New York, NY, USA; 2017. p. 49-63. (In Eng.) DOI: https://doi.org/10.1145/3062341.3062372
19. Lopes N.P., Menendez D., Nagarakatte S., Regehr J. Practical verification of peephole optimizations with Alive. Communications of the ACM. 2018; 61(2):84-91. (In Eng.) DOI: https://doi.org/10.1145/3166064
20. Gulwani S., Jha S., Tiwari A., Venkatesan R. Synthesis of loop-free programs. ACM SIGPLAN Notices. 2011; 46(6):62-73. (In Eng.) DOI: https://doi.org/10.1145/1993498.1993506
21. Cadar C., Dunbar D., Engler D. KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. Proceedings of the 8th USENIX conference on Operating systems design and implementation (OSDI'08). USENIX Association, USA; 2008. p. 209-224. Available at: https://www.usenix.org/legacy/events/osdi08/tech/full_papers/cadar/cadar.pdf (accessed 03.08.2021). (In Eng.)
22. Luk C.-K., et al. Pin: building customized program analysis tools with dynamic instrumentation. ACM SIGPLAN Notices. 2005; 40(6):190-200. (In Eng.) DOI: https://doi.org/10.1145/1064978.1065034
23. Schkufza E., Sharma R., Aiken A. Stochastic superoptimization. ACM SIGARCH Computer Architecture News. 2013; 41(1):305-316. (In Eng.) DOI: https://doi.org/10.1145/2451116.2451150
24. Bansal S., Aiken A. Automatic generation of peephole superoptimizers. ACM SIGARCH Computer Architecture News. 2006; 34(5):394-403. (In Eng.) DOI: https://doi.org/10.1145/1168857.1168906
25. Buchwald S. OPTGEN: A Generator for Local Optimizations. In: Ed. by B. Franke. Compiler Construction. CC 2015. Lecture Notes in Computer Science. 2015; 9031:171-189. Springer, Berlin, Heidelberg. (In Eng.) DOI: https://doi.org/10.1007/978-3-662-46663-6_9
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
