Constructing trace trees for Scheme
Instead of compiling an entire program upfront, a JIT compiler only compiles parts of the code that are frequently executed, avoiding unnecessary compilation and at the same time opening up opportunities for a number of new optimisations.
Different approaches for JIT compilation exist. A traditional method-level JIT compiler will compile frequently called methods. A tracing JIT however will compile specific code paths, and does so across intervening method calls, loops, and conditionals [4, 5].
A tracing JIT starts out by monitoring the interpretation of a program to find loops. Thus, it tries to determine jumps in the control flow that target already executed code. When the same jump has been taken a number of times, the JIT starts recording the activity of the interpreter into a trace. Whenever a jump is encountered to the same target that initiated the tracing, the JIT will compile the obtained trace and associate the resulting native code with that jump target. From then on, whenever the interpreter reaches a jump target for which a native trace is available, it will execute that trace instead of continuing regular interpretation.
While the basic operations of a tracing JIT compiler are fairly straightforward to comprehend, the devil is in the details. Since a trace represents a snapshot of program execution at a particular point in time, it inevitably has certain assumptions attached to it that need to be guarded when re-executing that trace. Therefore it is possible that trace execution is prevented, or even aborted while in progress, due to failing guard conditions installed during recording.
The goal of this thesis is to develop a trace management system that enables the JIT compiler to detect when traces start overlapping each other. Since these traces often share important similarities, it might be beneficial to unify them, both to minimise memory overhead and to increase JIT start-up performance. However, care must be taken when merging traces, because each trace might have been optimised under different assumptions and (partial) recompilation of the traces may therefore be required. The trace management system will therefore need to carefully compare the expected performance gains achieved by unifying traces with the overhead produced by merging them.
Some research has already been conducted in this area [1, 2, 3], but it remains unclear under which circumstances it is preferable to merge traces. Additionally, most of this research has been conducted in the context of imperative languages with explicit loop-constructs. It remains to be seen how this research could be transposed to functional-like languages such as Scheme.
As a testbed for this research, the student can make use of STRAF, a Scala framework for running trace-based JIT compilers that was recently developed at the Software Languages Lab. Using STRAF, we have constructed a trace-based JIT compiler for a Scheme-like language.
[1] M. Bebenita, et al. Trace-based compilation in execution environments without interpreters. In Proceedings of the 8th International Conference on the Principles and Practice of Programming in Java. 2010.
[2] M. Bebenita, et al. SPUR: a trace-based JIT compiler for CIL. Sigplan Not, 45(10). ACM, 2010.
[3] A. Gal, and M. Franz. Incremental dynamic code generation with trace trees. Technical Report ICS-TR-06-16, Donald Bren School of Information and Computer Science, University of California, Irvine, 2006.
[4] A. Gal, C. W. Probst, and M. Franz. HotpathVM: An effective JIT compiler for resource-constrained devices. In Proceedings of the 2nd international conference on Virtual execution environments, 2006.
[5] C. Häubl, and H. Mössenböck. Trace-based compilation for the Java HotSpot virtual machine. In Proceedings of the 9th International Conference on Principles and Practice of Programming in Java, 2011.