Tracing just-in-time compilation is a technique used by
virtual machines
In computing, a virtual machine (VM) is the virtualization/emulation of a computer system. Virtual machines are based on computer architectures and provide functionality of a physical computer. Their implementations may involve specialized hardw ...
to
optimize the execution of a program at
runtime. This is done by recording a linear sequence of frequently executed operations,
compiling
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
them to
native
Native may refer to:
People
* Jus soli, citizenship by right of birth
* Indigenous peoples, peoples with a set of specific rights based on their historical ties to a particular territory
** Native Americans (disambiguation)
In arts and entert ...
machine code
In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very ...
and executing them. This is opposed to traditional
just-in-time (JIT) compilers that work on a per-method basis.
Overview
Just-in-time compilation is a technique to increase execution speed of programs by compiling parts of a program to
machine code
In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very ...
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
In computing, a virtual machine (VM) is the virtualization/emulation of a computer system. Virtual machines are based on computer architectures and provide functionality of a physical computer. Their implementations may involve specialized hardw ...
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.
Technical details
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
Tracing may refer to:
Computer graphics
* Image tracing, digital image processing to convert raster graphics into vector graphics
* Path tracing, a method of rendering images of three-dimensional scenes such that the global illumination is faithf ...
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:
Profiling phase
The goal of profiling is to identify hot loops. This is often done by counting the number of iterations for every loop. After the count of a loop exceeds a certain threshold, the loop is considered to be hot, and tracing phase is entered.
Tracing phase
In the tracing phase the execution of the loop proceeds normally, but in addition every executed operation is recorded into a trace. The recorded operations are typically stored in
trace tree
Trace may refer to:
Arts and entertainment Music
* ''Trace'' (Son Volt album), 1995
* ''Trace'' (Died Pretty album), 1993
* Trace (band), a Dutch progressive rock band
* ''The Trace'' (album)
Other uses in arts and entertainment
* ''Trace'' ...
, often in an
intermediate representation
An intermediate representation (IR) is the data structure or code used internally by a compiler or virtual machine to represent source code. An IR is designed to be conducive to further processing, such as optimization and translation. A "good" ...
(IR). Tracing follows function calls, which leads to them being inlined into the trace. Tracing continues until the loop reaches its end and jumps back to the start.
Since the trace is recorded by following one concrete execution path of the loop, later executions of that trace can diverge from that path. To identify the places where that can happen, special
guard
Guard or guards may refer to:
Professional occupations
* Bodyguard, who protects an individual from personal assault
* Crossing guard, who stops traffic so pedestrians can cross the street
* Lifeguard, who rescues people from drowning
* Prison ...
instructions are inserted into the trace. One example for such a place are if statements. The guard is a quick check to determine whether the original condition is still true. If a guard fails, the execution of the trace is aborted.
Since tracing is done during execution, the trace can be made to contain
runtime information (e.g.
type information). This information can later be used in the optimization phase to increase code efficiency.
Optimization and code-generation phase
Traces are easy to optimize, since they represent only one execution path, which means that no control flow exists and needs no handling. Typical optimizations include
constant-subexpression elimination,
dead code elimination
In compiler theory, dead-code elimination (also known as DCE, dead-code removal, dead-code stripping, or dead-code strip) is a compiler optimization to remove code which does not affect the program results. Removing such code has several benefits: ...
,
register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocation' ...
,
invariant-code motion,
constant folding, and
escape analysis
In compiler optimization, escape analysis is a method for determining the dynamic scope of pointers where in the program a pointer can be accessed. It is related to pointer analysis and shape analysis.
When a variable (or an object) is allocate ...
.
After the optimization, the trace is turned into machine code. Similarly to optimization, this is easy due to the linear nature of traces.
Execution
After the trace has been compiled to machine code, it can be executed in subsequent iterations of the loop. Trace execution continues until a guard fails.
History
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.
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".
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
DynamoRIO is a BSD licensed dynamic binary instrumentation framework for the development of dynamic program analysis tools. DynamoRIO targets user space applications under the Android, Linux, and Windows operating systems running on the AArch32 ...
. 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".
In 2006, HotpathVM, the first tracing JIT compiler for a high-level language was developed.
This VM was capable of dynamically identifying frequently executed bytecode instructions, which are traced and then compiled to machine code using
static single assignment In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing var ...
(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
SpiderMonkey is the first JavaScript engine, written by Brendan Eich at Netscape Communications, later released as open source and currently maintained by the Mozilla Foundation. It is used in the Firefox web browser.
History
Eich "wrote J ...
, one of
Mozilla
Mozilla (stylized as moz://a) is a free software community founded in 1998 by members of Netscape. The Mozilla community uses, develops, spreads and supports Mozilla products, thereby promoting exclusively free software and open standards, wi ...
’s JavaScript implementations for
Firefox
Mozilla Firefox, or simply Firefox, is a free and open-source web browser developed by the Mozilla Foundation and its subsidiary, the Mozilla Corporation. It uses the Gecko rendering engine to display web pages, which implements current and ...
(2009).
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
PyPy () is an implementation of the Python programming language. PyPy often runs faster than the standard implementation CPython because PyPy uses a just-in-time compiler. Most Python code runs well on PyPy except for code that depends on CPytho ...
. 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.
Tracing JITs have also been explored by
Microsoft
Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washing ...
in the SPUR project for their
Common Intermediate Language
Common Intermediate Language (CIL), formerly called Microsoft Intermediate Language (MSIL) or Intermediate Language (IL), is the intermediate language binary instruction set defined within the Common Language Infrastructure (CLI) specification. ...
(CIL). SPUR is a generic tracer for CIL, which can also be used to trace through a JavaScript implementation.
Example of a trace
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
.
See also
*
Code generation
*
Dalvik
*
HotSpot
*
Interpreter
*
Profile-guided optimization
Profile-guided optimization (PGO, sometimes pronounced as ''pogo''), also known as profile-directed feedback (PDF), and feedback-directed optimization (FDO) is a compiler optimization technique in computer programming that uses profiling to impr ...
*
RPython
PyPy () is an implementation of the Python programming language. PyPy often runs faster than the standard implementation CPython because PyPy uses a just-in-time compiler. Most Python code runs well on PyPy except for code that depends on CPytho ...
*
Semantic dictionary encoding
References
{{Reflist, 40em
External links
Official website of LuaJIT
Compiler construction
Software optimization
Articles with example Python (programming language) code