Автоматическая генерация интерпретатора для многоязыковой виртуальной машины
Аннотация
В данной статье проведено исследование существующих реализаций генераторов интерпретаторов и предложен подход к генерации интерпретаторов на ассемблере для нескольких архитектур по описанию множества инструкций (BISA – Bytecode Instruction Set Architecture) многоязыковой регистровой виртуальной машины (VM – Virtual Machine) с интерпретатором, компилятором и сборщиком мусора.
Каждой инструкции из BISA однозначно соответствует обработчик BISA. Для каждого обработчика BISA задан номер, определяющий положение обработчика, частота использования соответствующей инструкции в множестве целевых приложений (МЦП), и набор инструкций псевдоязыка, характеризующий логику обработки соответствующей инструкции BISA виртуальной машиной. МЦП состоит из приложений, предназначенных для запуска на рассматриваемой виртуальной машине. Интерпретатор представляет собой последовательный набор обработчиков BISA.
Согласно выбранному автором подходу, для получения интерпретаторов на ассемблере по BISA необходимо выполнить три последовательных шага. На первом шаге осуществляется преобразование обработчиков BISA в промежуточное представление интерпретатора. На втором шаге проводятся машинно-независимые оптимизации промежуточного кода интерпретатора. На третьем шаге выполняются машинно-зависимые оптимизации и преобразование промежуточного представления интерпретатора в представления выбранных архитектур.
Было разработано инструментальное средство на языке C++, реализующее упрощенный, не включающий оптимизации, вариант предложенного подхода для двух инструкций. Проведено экспериментальное исследование, в ходе которого предложенный генератор сравнивался с компилятором clang++ по количеству генерируемых инструкций целевой машины для каждого обработчика BISA. Экспериментальное исследование показало, что выбранные подходы эквивалентны, даже при использовании упрощенного алгоритма генерации интерпретаторов. В перспективе планируется оптимизировать предложенный подход, что позволит превзойти по производительности известные подходы.
Литература
2. Marques I.L., Ronan J., Rosa N.S. TinyReef: a register-based virtual machine for Wireless Sensor Networks. SENSORS. IEEE Computer Society; 2009. p. 1423-1426. (In Eng.) doi: https://doi.org/10.1109/ICSENS.2009.5398437
3. Goldberg R.P. Architecture of virtual machines. Proceedings of the workshop on virtual computer systems. Association for Computing Machinery, New York, NY, USA; 1973. p. 74-112. (In Eng.) doi: https://doi.org/10.1145/800122.803950
4. Craig I.D. Virtual Machines. Springer, London; 2006. 269 p. (In Eng.) doi: https://doi.org/10.1007/978-1-84628-246-1
5. Gregg D., et al. The case for virtual register machines. Science of Computer Programming. 2005; 57(3): 319-338. (In Eng.) doi: https://doi.org/10.1016/j.scico.2004.08.005
6. Mugridge W.B., Hamer J., Hosking J.G. Multi-methods in a statically-typed programming language. In: America P. (eds.) ECOOP'91 European Conference on Object-Oriented Programming. ECOOP 1991. Lecture Notes in Computer Science. Vol. 512. Springer, Berlin, Heidelberg; 1991. p. 307-324. (In Eng.) doi: https://doi.org/10.1007/BFb0057029
7. Abadi M., Cardelli L., Pierce B., Plotkin G. Dynamic typing in a statically typed language. ACM Transactions on Programming Languages and Systems. 1991; 13(2):237-268. (In Eng.) doi: https://doi.org/10.1145/103135.103138
8. Tratt L. Chapter 5 Dynamically Typed Languages. Advances in Computers. 2009; 77:149-184. (In Eng.) doi: https://doi.org/10.1016/S0065-2458(09)01205-4
9. Nierstrasz O., Bergel A., Denker M., Ducasse S., Gälli M., Wuyts R. On the Revival of Dynamic Languages. In: Gschwind, T., Aßmann, U., Nierstrasz, O. (eds) Software Composition. SC 2005. Lecture Notes in Computer Science. Vol. 3628. Springer, Berlin, Heidelberg; 2005. p. 1-13. (In Eng.) doi: https://doi.org/10.1007/11550679_1
10. Hickman G.D. An overview of virtual machine (VM) technology and its implementation in IT student labs at Utah Valley State College. Journal of Computing Sciences in Colleges. 2008; 23(6):203-212. (In Eng.) doi: https://doi.org/10.5555/1352383.1352419
11. Cheng P., Blelloch G.E. A parallel, real-time garbage collector. Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation (PLDI'01). Association for Computing Machinery, New York, NY, USA; 2001. p. 125-136. (In Eng.) doi: https://doi.org/10.1145/378795.37882
12. Sasada K. YARV: yet another RubyVM: innovating the ruby interpreter. Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (OOPSLA'05). Association for Computing Machinery, New York, NY, USA; 2005. p. 158-159. (In Eng.) doi: https://doi.org/10.1145/1094855.1094912
13. Hofstee H.P. Power efficient processor architecture and the Cell processor. 11th International Symposium on High-Performance Computer Architecture. IEEE Computer Society; 2005. p. 258-262. (In Eng.) doi: https://doi.org/10.1109/HPCA.2005.26
14. Burd T.D., Brodersen R.W. Processor design for portable systems. Journal of VLSI signal processing systems for signal, image and video technology. 1996; 13(2):203-221. (In Eng.) doi: https://doi.org/10.1007/BF01130406
15. Würthinger T., Wimmer C., Humer C., Wöß A., Stadler L., Seaton C., Duboscq G., Simon D., Grimmer M. Practical partial evaluation for high-performance dynamic language runtimes. 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. 662-676. (In Eng.) doi: https://doi.org/10.1145/3062341.3062381
16. Kuck D.J., Kuhn R.H., Padua D.A., Leasure B., Wolfe M. Dependence graphs and compiler optimizations. Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL'81). Association for Computing Machinery, New York, NY, USA; 1981. p. 207-218. (In Eng.) doi: https://doi.org/10.1145/567532.567555
17. McKeeman W.M. Peephole optimization. Communications of the ACM. 1965; 8(7):443-444. (In Eng.) doi: https://doi.org/10.1145/364995.365000
18. Dubach C., Cavazos J., Franke B., Fursin G., O'Boyle M.F.P., Temam O. Fast compiler optimisation evaluation using code-feature based performance prediction. Proceedings of the 4th international conference on Computing frontiers (CF '07). Association for Computing Machinery, New York, NY, USA; 2007. p. 131-142. (In Eng.) doi: https://doi.org/10.1145/1242531.1242553
19. McCandless J., Gregg D. Optimizing interpreters by tuning opcode orderings on virtual machines for modern architectures: or: how I learned to stop worrying and love hill climbing. Proceedings of the 9th International Conference on Principles and Practice of Programming in Java (PPPJ '11). Association for Computing Machinery, New York, NY, USA; 2011. p. 161-170. (In Eng.) doi: https://doi.org/10.1145/2093157.2093183
20. Henriques P.R., et al. Automatic Generation of Language-based Tools. Electronic Notes in Theoretical Computer Science. 2002; 65(3):77-96. (In Eng.) doi: https://doi.org/10.1016/S1571-0661(04)80428-6
21. Vergu V., Visser E. Specializing a meta-interpreter: JIT compilation of Dynsem specifications on the Graal VM. Proceedings of the 15th International Conference on Managed Languages & Runtimes (ManLang '18). Association for Computing Machinery, New York, NY, USA; 2018. Article number: 16. p. 1-14. (In Eng.) doi: https://doi.org/10.1145/3237009.3237018
22. Steensgaard-Madsen J. A Generator for Composition Interpreters. In: Bosch J., Mitchell S. (eds.) Object-Oriented Technologys. ECOOP 1997. Lecture Notes in Computer Science. Vol. 1357. Springer, Berlin, Heidelberg; 1998. p. 369-373. (In Eng.) doi: https://doi.org/10.1007/3-540-69687-3_75
23. Rubio M.S., Civera G.L., Herraiz J.J.M. Automatic Generation Of Virtual Machines For Security Training. IEEE Latin America Transactions. 2016; 14(6):2795-2800. (In Eng.) doi: https://doi.org/10.1109/TLA.2016.7555257
24. Aguzzi G., Cesarini F., Pinzani R., Soda G., Sprugnoli R. Towards an Automatic Generation of Interpreters. In: Brauer, W. (eds) GI Gesellschaft für Informatik e. V. Lecture Notes in Computer Science. Vol. 1. Springer, Berlin, Heidelberg; 1973. p. 94-103. (In Eng.) doi: https://doi.org/10.1007/978-3-662-41148-3_9
25. Leduc M., et al. Automatic generation of Truffle-based interpreters for Domain-Specific Languages. The Journal of Object Technology. 2020; 19(2):1-21. (In Eng.) doi: https://doi.org/10.5381/jot.2020.19.2.a1
26. Ertl M.A., Gregg D.,Krall A., Paysan B. Vmgen – a generator of efficient virtual machine interpreters. Software: Practice and Experience. 2002; 32(3):265-294. (In Eng.) doi: https://doi.org/10.1002/spe.434
27. Gregg D., Ertl M.A. A Language and Tool for Generating Efficient Virtual Machine Interpreters. In: Lengauer C., Batory D., Consel C., Odersky M. (eds.) Domain-Specific Program Generation. Lecture Notes in Computer Science. Vol. 3016. Springer, Berlin, Heidelberg; 2004. p. 196-215. (In Eng.) doi: https://doi.org/10.1007/978-3-540-25935-0_12
28. Lim J., Reps T. TSL: A System for Generating Abstract Interpreters and its Application to Machine-Code Analysis. ACM Transactions on Programming Languages and Systems. 2013; 35(1):4. (In Eng.) doi: https://doi.org/10.1145/2450136.2450139
Это произведение доступно по лицензии 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.
