Tracing just-in-time compilation

Just-in-time compilation is a technique to increase execution speed of programs by compiling parts of a program to machine code at runtime. One way to categorize different JIT compilers is by their compilation scope. Whereas method-based JIT compilers translate one method at a time to machine code, tracing JITs use frequently executed loops as their unit of compilation. Tracing JITs are based on the assumptions that programs spend most of their time in some loops of the program ("hot loops") and subsequent loop iterations often take similar paths. Virtual machines that have a tracing JIT are often mixed-mode execution environments, meaning that they have either an interpreter or a method compiler in addition to the tracing JIT.

A tracing JIT compiler goes through various phases at runtime. First, profiling information for loops is collected. After a hot loop has been identified, a special tracing phase is entered, which records all executed operations of that loop. This sequence of operations is called a trace. The trace is then optimized and compiled to machine code (trace). When this loop is executed again, the compiled trace is called instead of the program counterpart.

These steps are explained in detail in the following:

Whereas the idea of JITs reaches back to the 1960s, tracing JITs have become used more often only recently. The first mention of an idea that is similar to today's idea of tracing JITs was in 1970.[2] It was observed that compiled code could be derived from an interpreter at run-time by simply storing the actions performed during interpretation.

The first implementation of tracing is Dynamo, "a software dynamic optimization system that is capable of transparently improving the performance of a native instruction stream as it executes on the processor".[3] To do this, the native instruction stream is interpreted until a "hot" instruction sequence is found. For this sequence an optimized version is generated, cached and executed.

Dynamo was later extended to DynamoRIO. One DynamoRIO-based project was a framework for interpreter construction that combines tracing and partial evaluation. It was used to "dynamically remove interpreter overhead from language implementations".[4]

In 2006, HotpathVM, the first tracing JIT compiler for a high-level language was developed.[5] This VM was capable of dynamically identifying frequently executed bytecode instructions, which are traced and then compiled to machine code using static single assignment (SSA) construction. The motivation for HotpathVM was to have an efficient JVM for resource constrained mobile devices.

Another example of a tracing JIT is TraceMonkey, one of Mozilla’s JavaScript implementations for Firefox (2009).[6] TraceMonkey compiles frequently executed loop traces in the dynamic language JavaScript at run-time and specializes the generated code for the actual dynamic types occurring on each path.

Another project that utilizes tracing JITs is PyPy. It enables the use of tracing JITs for language implementations that were written with PyPy's translation toolchain, thus improving the performance of any program that is executed using that interpreter. This is possible by tracing the interpreter itself, instead of the program that is executed by the interpreter.[7]

Tracing JITs have also been explored by Microsoft in the SPUR project for their Common Intermediate Language (CIL). SPUR is a generic tracer for CIL, which can also be used to trace through a JavaScript implementation.[8]

Consider the following Python program that computes a sum of squares of successive whole numbers until that sum exceeds 100000:

def square(x):
    return x * x

i = 0
y = 0
while True:
    y += square(i)
    if y > 100000:
        break
    i = i + 1

A trace for this program could look something like this:

 loopstart(i1, y1)
 i2 = int_mul(i1, i1)		# x*x
 y2 = int_add(y1, i2)		# y += i*i
 b1 = int_gt(y2, 100000)
 guard_false(b1)
 i3 = int_add(i1, 1)		# i = i+1
 jump(i3, y2)

Note how the function call to square is inlined into the trace and how the if statement is turned into a guard_false.

• Code generation
• Dalvik
• HotSpot
• Interpreter
• Profile-guided optimization
• RPython
• Semantic dictionary encoding

• Official website of LuaJIT