Automatic Generation of Interpreter for Multilingual Virtual Machine
Abstract
The article says about existing implementations of interpreter generators and proposes an approach for generating interpreters in assembly for several architectures by describing a set of instructions (BISA - Bytecode Instruction Set Architecture) of a multilingual stack virtual machine (VM - Virtual Machine) with an interpreter, compiler and garbage collector. Each instruction from BISA has a unique BISA handler. For each BISA handler, there are a specified number that defines its position, a frequency of usage of the corresponding instruction in the set of target applications (STA), and a set of pseudo-language instructions that characterizes the logic of handling the corresponding BISA instruction by the virtual machine. STA consists of applications designed to be run on the given virtual machine. An interpreter is a sequential set of BISA handlers. According to the approach chosen by the author, to obtain interpreters in assembly using BISA, it is necessary to do three consecutive steps. During the first step, the BISA handlers are converted into an intermediate representation of the interpreter. In the second step, machine-independent optimizations of the intermediate code of the interpreter are performed. At the third step, the intermediate representation of the interpreter is converted into representations of the selected architectures and machine-dependent optimizations are performed. A C ++ tool was developed that implements a simplified, non-optimized version of the given approach for two instructions. An experimental study was carried out, during which the proposed generator was compared with the clang ++ compiler in terms of the number of generated instructions of the target machine for each BISA processor. Experimental research has shown that the selected approaches are equivalent, even when using a simplified algorithm for generating interpreters. In the longer run, it is planned to optimize the proposed approach, which will allow surpassing the known approaches in performance.
References
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
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.
