Tracing just-in-time compilation

<h2 id="overview">Overview</h2>
<p>Just-in-time compilation is a technique to increase execution speed of programs by compiling parts of a program to <a href="/facts/Machine_code/bgdQ1Fxf">machine code</a> 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 <a href="/facts/Loop_(computing)/2XTDfErC">loops</a> of the program ("hot loops") and subsequent loop iterations often take similar paths. <a href="/facts/Virtual_machines/BLevU3sx">Virtual machines</a> 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.
</p>
<h2 id="technical-details">Technical details</h2>
<p>A tracing JIT compiler goes through various phases at runtime. First, <a href="/facts/Profiling_(computer_programming)/JbSlDHPP">profiling</a> information for loops is collected. After a hot loop has been identified, a special <a href="/facts/Tracing_(software)/36dskvN5">tracing</a> 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. When this loop is executed again, the compiled trace is called instead of the program counterpart.
</p><p>These steps are explained in detail in the following:
</p>
<h3>Profiling phase</h3>
<p>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.
</p>
<h3>Tracing phase</h3>
<p>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 a <a href="/facts/Trace_tree/qCnpjsDq">trace tree</a>, often in an <a href="/facts/Intermediate_representation/s0qRrbfh">intermediate representation</a> (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.
</p><p>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 <a href="/facts/Guard_(computer_science)/QsmS63NU">guard</a> 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.
</p><p>Since tracing is done during execution, the trace can be made to contain <a href="/facts/Runtime_(program_lifecycle_phase)/lCxKsrzB">runtime information</a> (e.g. <a href="/facts/Run-time_type_information/z08ojlmN">type information</a>). This information can later be used in the optimization phase to increase code efficiency.
</p>
<h3>Optimization and code-generation phase</h3>
<p>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 <a href="/facts/Common_subexpression_elimination/hlCW19QS">common-subexpression elimination</a>, <a href="/facts/Dead_code_elimination/waQRsajr">dead code elimination</a>, <a href="/facts/Register_allocation/rB1vkhxU">register allocation</a>, <a href="/facts/Loop-invariant_code_motion/9jBNoTdm">invariant-code motion</a>, <a href="/facts/Constant_folding/1NmVLgm1">constant folding</a>, and <a href="/facts/Escape_analysis/DzEFMdLX">escape analysis</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p><p>After the optimization, the trace is turned into machine code. Similarly to optimization, this is easy due to the linear nature of traces.
</p>
<h3>Execution</h3>
<p>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.
</p>
<h2 id="history">History</h2>
<p>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.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> It was observed that compiled code could be derived from an interpreter at run-time by simply storing the actions performed during interpretation.
</p><p>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".<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> 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.
</p><p>Dynamo was later extended to <a href="/facts/DynamoRIO/vEdB2UPb">DynamoRIO</a>. 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".<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p><p>In 2006, HotpathVM, the first tracing JIT compiler for a high-level language was developed.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> This VM was capable of dynamically identifying frequently executed bytecode instructions, which are traced and then compiled to machine code using <a href="/facts/Static_single_assignment/HnDHfx6I">static single assignment</a> (SSA) construction. The motivation for HotpathVM was to have an efficient JVM for resource constrained mobile devices.
</p><p>Another example of a tracing JIT is <a href="/facts/SpiderMonkey_(JavaScript_engine)/YosPe1Bv">TraceMonkey</a>, one of <a href="/facts/Mozilla/FevL9Itn">Mozilla</a>’s JavaScript implementations for <a href="/facts/Firefox/xez2zv8H">Firefox</a> (2009).<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> 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.
</p><p>Another project that utilizes tracing JITs is <a href="/facts/PyPy/r7l3Dbey">PyPy</a>. 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.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p><p>Tracing JITs have also been explored by <a href="/facts/Microsoft/nGIDDXdx">Microsoft</a> in the SPUR project for their <a href="/facts/Common_Intermediate_Language/sBIaMXyW">Common Intermediate Language</a> (CIL). SPUR is a generic tracer for CIL, which can also be used to trace through a JavaScript implementation.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a>
</p>
<h2 id="example-of-a-trace">Example of a trace</h2>
<p>Consider the following Python program that computes a sum of squares of successive whole numbers until that sum exceeds 100000:
</p>
def square(x):
    return x * x

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

<p>A trace for this program could look something like this:
</p>
 loopstart(i1, y1)
 i2 = int_mul(i1, i1)		# i*i
 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)

<p>Note how the function call to square is inlined into the trace and how the if statement is turned into a guard_false.
</p>
<h2 id="see-also">See also</h2>
<ul>
<li>Computer programming portal</li></ul>
<ul><li><a href="/facts/Code_generation_(compiler)/6Ce9gjPs">Code generation</a></li>
<li><a href="/facts/Dalvik_(software)/n7tnxaPt">Dalvik</a></li>
<li><a href="/facts/HotSpot_(virtual_machine)/m6vjRXvm">HotSpot</a></li>
<li><a href="/facts/Interpreter_(computing)/JB85fbyb">Interpreter</a></li>
<li><a href="/facts/Profile-guided_optimization/u9ej9s76">Profile-guided optimization</a></li>
<li><a href="/facts/RPython/r7l3Dbey">RPython</a></li>
<li><a href="/facts/Semantic_dictionary_encoding/T2WRRR4E">Semantic dictionary encoding</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://luajit.org/luajit.html">Official website of LuaJIT</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>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. <a href="https://www3.hhu.de/stups/downloads/pdf/BoCuFiLePeRi2011.pdf" target="_blank">https://www3.hhu.de/stups/downloads/pdf/BoCuFiLePeRi2011.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>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. <a href="978-0-8240-4414-5" target="_blank">978-0-8240-4414-5</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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. <a href="978-1-58113-199-4" target="_blank">978-1-58113-199-4</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>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. <a href="978-1-58113-655-5" target="_blank">978-1-58113-655-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>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. <a href="978-1-59593-332-4" target="_blank">978-1-59593-332-4</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>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. <a href="978-1-60558-392-1" target="_blank">978-1-60558-392-1</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>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. <a href="978-1-60558-541-3" target="_blank">978-1-60558-541-3</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>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. <a href="978-1-4503-0203-6" target="_blank">978-1-4503-0203-6</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
</ol>

Tracing just-in-time compilation open-in-new

Tracing just-in-time compilation