Задача автоматической генерации peephole-оптимизаций
обзор подходов, решение проблемы оптимального расширения архитектуры набора managed инструкций
Аннотация
В данной статье рассматривается проблема автоматической генерации peephole-оптимизаций статического оптимизатора байт-кода виртуальной машины (ВМ) применительно к задаче усовершенствования архитектуры набора инструкций (ISA) ВМ.
Peephole-оптимизация является одним из этапов работы оптимизирующего компилятора, применяющаяся к коду исходной входной программы в промежуточном представлении (IR или LLIR) и заключающаяся в поиске последовательностей инструкций, совпадающих с известными шаблономи, и замене их на более короткие или более быстрые семантически эквивалентные наборы. Существующие подходы peephole-оптимизаций предполагают наличие некоторого ограниченного набора шаблонов или функций, которые закодированы вручную, полагаясь при этом на глубокие знания инженеров соответствующего IR и структуры выходных программ данного компилятора. Также для различных IR необходимо заново кодировать аналогичные peephole-оптимизации, что влечет дополнительные денежные и временные расходы.
Альтернативным подходом является супероптимизация, заключающаяся в автоматической генерации шаблонов и правил их сопоставления. Среди основных частей супероптимизатора присутствуют алгоритм поиска, функция затрат и верификатор эквивалентности.
В статье реализован и протестирован метод решения более специализированной подзадачи, заключающейся в поиске и подсчете наиболее частых шаблонов инструкций, которые в дальнейшем могут быть заменены на одну новую инструкцию для оптимизации времени выполнения и/или размера байт-кода и быть проанализированы программистом для получения информации о специфике исходных данных. Данный алгоритм может быть использован как инструмент проектирования managed ISA.
Литература
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
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
