Generalization of Just-in-Time Trace Compilation for Java

Java source code is compiled to machine-independent bytecodes that are interpreted by a virtual machine. At run time, modern Java VMs use a just-in-time compiler (JIT compiler) to compile the most frequently executed methods to machine code while other methods continue to run in the interpreter. This leads to a good trade-off between execution speed and compilation overhead. As a further step in the same direction, Gal et al. recently proposed to make the unit of compilation even smaller, i.e. to compile only certain paths through frequently executing loops while the rest of the program is interpreted. This is called trace compilation. It further reduces compilation times, allows for simpler and more aggressive optimizations, and makes compilers simple enough to run on resource-constrained devices. Currently, trace compilation is restricted to paths through loops. We believe that this does not exploit its full potential. There are also paths outside of loops which are executed frequently enough to justify their compilation to machine code. In other words, the concept of trace compilation needs to be generalized. The research goals of our project are therefore (1) to generalize the concept of the trace compilation by allowing traces to start and end anywhere in a program and by using techniques to split, merge, and glue traces together, (2) to abolish methods as execution units in compiled code and to replace them by traces that call each other using appropriate trace calling conventions, and (3) to investigate how traditional optimization techniques can be adapted and simplified for trace compilation. We plan to integrate trace compilation into the Java HotSpot VM of Sun Microsystems, which is available from the open-source project OpenJDK. It is one of the fastest Java VMs available, so the resulting implementation will show whether trace compilation can compete or even outperform traditional compilation approaches. In this case, our project could lead to a paradigm change in just-in-time compilation.

Java is a modern and widely used programming language that allows the development of programs which run on a large variety of computersfrom mobile phones to enterprise servers. In order to achieve platform independence, Java programs are usually interpreted by a virtual machine. The downside to this is that interpretation is slow. Thus, virtual machines try to compile the most frequently executed program paths into efficient machine code. This is called just-in-time compilation or JIT compilation.We use a variant of JIT compilation in which we measure the execution frequencies of individual program paths (so-called traces) and compile the most frequently executed traces to machine code. This is called trace compilation. Since there are usually just a few frequent paths in any program their compilation tends to be fast. Fast compilation, however, leads to fast overall run times, because compilation happens at run time.In contrast to traditional trace compilers we do not only compile traces within loops but also traces that are outside of loops if they are frequent enough. In our approach, a path can also extend across several methods. As a special result of our research we developed a new context-sensitive technique for inlining paths from sub-methods into calling methods.Measurements have shown that our simple trace-based compiler generates code which is more efficient than the code generated by simple traditional JIT compilers. In some benchmarks our compiler even outperformed one of today's best Java JIT compilers while needing less than 10% of its compilation time.