Tracing just-in-time compilation

Last updated

Tracing just-in-time compilation is a technique used by virtual machines to optimize the execution of a program at runtime. This is done by recording a linear sequence of frequently executed operations, compiling them to native machine code and executing them. This is opposed to traditional just-in-time (JIT) compilers that work on a per-method basis.

Contents

Overview

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.

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 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, often in an intermediate representation (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 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, register allocation, invariant-code motion, constant folding, and escape analysis. [1]

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. [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[ citation needed ] 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]

Example of a trace

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

defsquare(x):returnx*xi=0y=0whileTrue:y+=square(i)ify>100000:breaki=i+1

A trace for this program could look something like this:

loopstart(i1,y1)i2=int_mul(i1,i1)# i*iy2=int_add(y1,i2)# y += i*ib1=int_gt(y2,100000)guard_false(b1)i3=int_add(i1,1)# i = i+1jump(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

Related Research Articles

In computing, a compiler is a computer program that translates computer code written in one programming language into another language. The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a low-level programming language to create an executable program.

<span class="mw-page-title-main">Java virtual machine</span> Virtual machine that runs Java programs

A Java virtual machine (JVM) is a virtual machine that enables a computer to run Java programs as well as programs written in other languages that are also compiled to Java bytecode. The JVM is detailed by a specification that formally describes what is required in a JVM implementation. Having a specification ensures interoperability of Java programs across different implementations so that program authors using the Java Development Kit (JDK) need not worry about idiosyncrasies of the underlying hardware platform.

In computing, a virtual machine (VM) is the virtualization or emulation of a computer system. Virtual machines are based on computer architectures and provide the functionality of a physical computer. Their implementations may involve specialized hardware, software, or a combination of the two. Virtual machines differ and are organized by their function, shown here:

<span class="mw-page-title-main">Interpreter (computing)</span> Program that executes source code without a separate compilation step

In computer science, an interpreter is a computer program that directly executes instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program. An interpreter generally uses one of the following strategies for program execution:

  1. Parse the source code and perform its behavior directly;
  2. Translate source code into some efficient intermediate representation or object code and immediately execute that;
  3. Explicitly execute stored precompiled bytecode made by a compiler and matched with the interpreter Virtual Machine.

Bytecode is a form of instruction set designed for efficient execution by a software interpreter. Unlike human-readable source code, bytecodes are compact numeric codes, constants, and references that encode the result of compiler parsing and performing semantic analysis of things like type, scope, and nesting depths of program objects.

In computing, just-in-time (JIT) compilation is compilation during execution of a program rather than before execution. This may consist of source code translation but is more commonly bytecode translation to machine code, which is then executed directly. A system implementing a JIT compiler typically continuously analyses the code being executed and identifies parts of the code where the speedup gained from compilation or recompilation would outweigh the overhead of compiling that code.

In compiler design, static single assignment form is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing variables in the original IR are split into versions, new variables typically indicated by the original name with a subscript in textbooks, so that every definition gets its own version. In SSA form, use-def chains are explicit and each contains a single element.

In software engineering, profiling is a form of dynamic program analysis that measures, for example, the space (memory) or time complexity of a program, the usage of particular instructions, or the frequency and duration of function calls. Most commonly, profiling information serves to aid program optimization, and more specifically, performance engineering.

<span class="mw-page-title-main">PyPy</span> Alternative implementation of the Python programming language

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 CPython extensions, which either does not work or incurs some overhead when run in PyPy. Internally, PyPy uses a technique known as meta-tracing, which transforms an interpreter into a tracing just-in-time compiler. Since interpreters are usually easier to write than compilers, but run slower, this technique can make it easier to produce efficient implementations of programming languages. PyPy's meta-tracing toolchain is called RPython.

In computer programming, a programming language implementation is a system for executing computer programs. There are two general approaches to programming language implementation:

Thread Level Speculation (TLS), also known as Speculative Multithreading, or Speculative Parallelization, is a technique to speculatively execute a section of computer code that is anticipated to be executed later in parallel with the normal execution on a separate independent thread. Such a speculative thread may need to make assumptions about the values of input variables. If these prove to be invalid, then the portions of the speculative thread that rely on these input variables will need to be discarded and squashed. If the assumptions are correct the program can complete in a shorter time provided the thread was able to be scheduled efficiently.

In computer science, ahead-of-time compilation is the act of compiling an (often) higher-level programming language into an (often) lower-level language before execution of a program, usually at build-time, to reduce the amount of work needed to be performed at run time.

Dalvik is a discontinued process virtual machine (VM) in the Android operating system that executes applications written for Android. Dalvik was an integral part of the Android software stack in the Android versions 4.4 "KitKat" and earlier, which were commonly used on mobile devices such as mobile phones and tablet computers, and more in some devices such as smart TVs and wearables. Dalvik is open-source software, originally written by Dan Bornstein, who named it after the fishing village of Dalvík in Eyjafjörður, Iceland.

Profile-guided optimization, also known as profile-directed feedback (PDF), and feedback-directed optimization (FDO) is a compiler optimization technique in computer programming that uses profiling to improve program runtime performance.

A trace tree is a data structure that is used in the runtime compilation of programming code. Trace trees are used in tracing just-in-time compilation where tracing is used during code execution to look for hot spots before compilation. When those hot spots are entered again the compiled code is run instead. Each statement executed is traced, including within other function calls, and the entire execution path is compiled. This is different from compiling individual functions. More information can be gained allowing better compiler optimizations, including the removal of some function call overhead. The interpreter is called to continue whenever compiled code makes calls to code outside the compilation contexts.

<span class="mw-page-title-main">LuaJIT</span> Just-in-time compiler for the Lua programming language

LuaJIT is a tracing just-in-time compiler for the Lua programming language. Mike Pall, a primary maintainer of the project had resigned in 2015, resorting only to occasional patching to the future 2.1 version.

<span class="mw-page-title-main">GraalVM</span>

GraalVM is a Java Development Kit (JDK), written in Java. The open-source distribution of GraalVM is based on OpenJDK, and the enterprise distribution is based on Oracle JDK. As well as just-in-time (JIT) compilation, GraalVM can compile a Java application ahead-of-time so that it starts instantly, provides peak performance with no warmup, and uses fewer resources. It provides additional programming languages and execution modes. The first production-ready release, GraalVM 19.0, was distributed in May 2019. The most recent release is GraalVM for JDK 21, made available in September 2023.

HipHop Virtual Machine (HHVM) is an open-source virtual machine based on just-in-time (JIT) compilation that serves as an execution engine for the Hack programming language. By using the principle of JIT compilation, Hack code is first transformed into intermediate HipHop bytecode (HHBC), which is then dynamically translated into x86-64 machine code, optimized, and natively executed. This contrasts with PHP's usual interpreted execution, in which the Zend Engine transforms PHP source code into opcodes that serve as a form of bytecode, and executes the opcodes directly on the Zend Engine's virtual CPU.

Android Runtime (ART) is an application runtime environment used by the Android operating system. Replacing Dalvik, the process virtual machine originally used by Android, ART performs the translation of the application's bytecode into native instructions that are later executed by the device's runtime environment.

A high-level language computer architecture (HLLCA) is a computer architecture designed to be targeted by a specific high-level programming language (HLL), rather than the architecture being dictated by hardware considerations. It is accordingly also termed language-directed computer design, coined in McKeeman (1967) and primarily used in the 1960s and 1970s. HLLCAs were popular in the 1960s and 1970s, but largely disappeared in the 1980s. This followed the dramatic failure of the Intel 432 (1981) and the emergence of optimizing compilers and reduced instruction set computer (RISC) architectures and RISC-like complex instruction set computer (CISC) architectures, and the later development of just-in-time compilation (JIT) for HLLs. A detailed survey and critique can be found in Ditzel & Patterson (1980).

References

  1. Bolz, Carl Friedrich; Cuni, Antonio; FijaBkowski, Maciej; Leuschel, Michael; Pedroni, Samuele; Rigo, Armin (January 2011). "Allocation Removal by Partial Evaluation in a Tracing JIT" (PDF). Proceedings of the 20th ACM SIGPLAN workshop on Partial evaluation and program manipulation. PEPM '11. pp. 43–52. doi:10.1145/1929501.1929508. S2CID   15871223 . Retrieved 2020-12-13.
  2. Mitchell, James G. (June 29, 1970). The Design and Construction of Flexible and Efficient Interactive Programming Systems (PhD). Carnegie Mellon University. ISBN   978-0-8240-4414-5. LCCN   79050563. OCLC   633313022. S2CID   36249021. Docket AAI7104538. Retrieved 2020-12-13.
  3. Bala, Vasanth; Duesterwald, Evelyn; Banerjia, Sanjeev (May 2000). "Dynamo: A Transparent Dynamic Optimization System" (PDF). Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation. PLDI '00. pp. 1–12. doi:10.1145/349299.349303. ISBN   978-1-58113-199-4. S2CID   53223267 . Retrieved 2020-12-13.
  4. Sullivan, Gregory T.; Bruening, Derek L.; Baron, Iris; Garnett, Timothy; Amarasinghe, Saman (June 2003). "Dynamic Native Optimization of Interpreters" (PDF). Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators. IVME '03. pp. 50–57. CiteSeerX   10.1.1.14.9819 . doi:10.1145/858570.858576. ISBN   978-1-58113-655-5. S2CID   509405 . Retrieved 2020-12-13.
  5. Gal, Andreas; Probst, Christian W.; Franz, Michael (June 2006). "HotpathVM: An Effective JIT Compiler for Resource-constrained Devices" (PDF). Proceedings of the 2nd international conference on Virtual execution environments. VEE '06. pp. 144–153. doi:10.1145/1134760.1134780. ISBN   978-1-59593-332-4. S2CID   17846788. QID   56580114 . Retrieved 2020-12-13.
  6. Gal, Andreas; Orendorff, Jason; Ruderman, Jesse; Smith, Edwin W.; Reitmaier, Rick; Bebenita, Michael; Chang, Mason; Franz, Michael; Eich, Brendan; Shaver, Mike; Anderson, David; Mandelin, David; Haghighat, Mohammad R.; Kaplan, Blake; Hoare, Graydon; Zbarsky, Boris (June 2009). "Trace-based Just-in-Time Type Specialization for Dynamic Languages" (PDF). Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '09. pp. 465–478. doi:10.1145/1542476.1542528. ISBN   978-1-60558-392-1. S2CID   207172806 . Retrieved 2020-12-13.
  7. Bolz, Carl Friedrich; Cuni, Antonio; Fijalkowski, Maciej; Rigo, Armin (July 2009). "Tracing the Meta-Level: PyPy's Tracing JIT Compiler" (PDF). Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems. ICOOOLPS '09. pp. 18–25. doi:10.1145/1565824.1565827. ISBN   978-1-60558-541-3. S2CID   7478596 . Retrieved 2020-12-13.
  8. Bebenita, Michael; Brandner, Florian; Fahndrich, Manuel; Logozzo, Francesco; Schulte, Wolfram; Tillmann, Nikolai; Venter, Herman (October 2010). "SPUR: A Trace-Based JIT Compiler for CIL" (PDF). Proceedings of the ACM international conference on Object oriented programming systems languages and applications. OOPSLA '10. pp. 708–725. doi:10.1145/1869459.1869517. ISBN   978-1-4503-0203-6. S2CID   3395746 . Retrieved 2020-12-13.