Automatic generation of optimised virtual machine interpreters

Abstract

Virtual Machines (VMs) are commonly used as execution platforms for many modern high-level languages. Two important examples are the Java VM, intended for running Java applications, and Microsoft's Common Language Runtime (CLR), intended for executing .NET applications compiled from C#/VB.NET . Typical VMs are implemented as either interpreters or Just-In-Time compilers. Interpreters are slower but have several advantages such as reliability, portability and memory efficiency that make them ideal for certain types of application. This thesis concentrates on various optimisations to improve the performance of VM interpreters. We show how it is possible to select and apply broadly useful optimisations, and even more importantly, show how these optimisations can be implemented in a automatic and portable manner. In order to facilitate this work we develop an interpreter generation tool, Tiger which provides extensive support for these optimisations. Details of this tool are presented, along with a discussion of how it supports a number of optimisations. A new optimised, portable JVM called Fastcore is constructed using Tiger, and then evaluated. The applied optimisations such as faster dispatch methods, constant inlining, conditional loading of operands and faster method dispatch are detailed along with their cumulative effect (an average speedup of 1.31) over an equivalent unoptimised JVM interpreter. Remaining optimisations are then classified into two broad categories; static instruction enhancement and dynamic instruction enhancement. Static instruction enhancements are comprised of instruction replication, instruction concatenation (superinstructions) and instruction specialisation. We show how these optimisations can improve the performance of our optimised interpreter by a speedup of up to 2.1 when the interpreter is being optimised for a broad range of programs, and up to 3.35 when the interpreter is being customised for a particular program. Dynamic instruction enhancements are comprised of dynamic instruction replication, along with a number of methods for creating dynamic superinstructions. The effects of these dynamic optimisations are examined in comparison to each other and against the static optimisations previously presented. These more generic dynamic optimisations improve performance by a speedup of up to 2.76 for a broad range of programs. Extensive results using hardware performance counters are presented for all of these optimisations. Some surprising results are encountered, which are highlighted and explained. These results give greater insight into the behaviour of VM interpreters and help the construction of simpler, faster, more maintainable VM interpreters.