Trace-based Just-in-Time Type Specialization for DynamicLanguagesAndreas Gal∗+, Brendan Eich∗, Mike Shaver∗, David Anderson∗, David Mandelin∗,Mohammad R. Haghighat$, Blake Kaplan∗, Graydon Hoare∗, Boris Zbarsky∗, Jason Orendorff∗,Jesse Ruderman∗, Edwin Smith#, Rick Reitmaier#, Michael Bebenita+, Mason Chang+#, Michael Franz+Mozilla Corporation∗{gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman}@mozilla.comAdobe Corporation#{edwsmith,rreitmai}@adobe.comIntel Corporation${mohammad.r.haghighat}@intel.comUniversity of California, Irvine+{mbebenit,changm,franz}@uci.eduAbstractDynamic languages such as JavaScript are more difficult to com-pile than statically typed ones. Since no concrete type informationis available, traditional compilers need to emit generic code that canhandle all possible type combinations at runtime. We present an al-ternative compilation technique for dynamically-typed languagesthat identifies frequently executed loop traces at run-time and thengenerates machine code on the fly that is specialized for the ac-tual dynamic types occurring on each path through the loop. Ourmethod provides cheap inter-procedural type specialization, and anelegant and efficient way of incrementally compiling lazily discov-ered alternative paths through nested loops. We have implementeda dynamic compiler for JavaScript based on our technique and wehave measured speedups of 10x and more for certain benchmarkprograms.Categories and Subject DescriptorsD.3.4 [Programming Lan-guages]: Processors —Incremental compilers, code generation.General TermsDesign, Experimentation, Measurement, Perfor-mance.KeywordsJavaScript, just-in-time compilation, trace trees.1. IntroductionDynamic languagessuch as JavaScript, Python, and Ruby, are pop-ular since they are expressive, accessible to non-experts, and makedeployment as easy as distributing a source file. They are used forsmall scripts as well as for complex applications. JavaScript, forexample, is the de facto standard for client-side web programmingPermission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a fee.PLDI’09,June 15–20, 2009, Dublin, Ireland.Copyrightc©2009 ACM 978-1-60558-392-1/09/06. . . $5.00and is used for the application logic of browser-based productivityapplications such as Google Mail, Google Docs and Zimbra Col-laboration Suite. In this domain, in order to provide a fluid userexperience and enable a new generation of applications, virtual ma-chines must provide a low startup time and high performance.Compilers for statically typed languages rely on type informa-tion to generate efficient machine code. In a dynamically typed pro-gramming language such as JavaScript, the types of expressionsmay vary at runtime. This means that the compiler can no longereasily transform operations into machine instructions that operateon one specific type. Without exact type information, the compilermust emit slower generalized machine code that can deal with allpotential type combinations. While compile-time static type infer-ence might be able to gather type information to generate opti-mized machine code, traditional static analysis is very expensiveand hence not well suited for the highly interactive environment ofa web browser.We present a trace-based compilation technique for dynamiclanguages that reconciles speed of compilation with excellent per-formance of the generated machine code. Our system uses a mixed-mode execution approach: the system starts running JavaScript in afast-starting bytecode interpreter. As the program runs, the systemidentifieshot(frequently executed) bytecode sequences, recordsthem, and compiles them to fast native code. We call such a se-quence of instructions atrace.Unlike method-based dynamic compilers, our dynamic com-piler operates at the granularity of individual loops. This designchoice is based on the expectation that programs spend most oftheir time in hot loops. Even in dynamically typed languages, weexpect hot loops to be mostlytype-stable, meaning that the types ofvalues are invariant. (12) For example, we would expect loop coun-ters that start as integers to remain integers for all iterations. Whenboth of these expectations hold, a trace-based compiler can coverthe program execution with a small number of type-specialized, ef-ficiently compiled traces.Each compiled trace covers one path through the program withone mapping of values to types. When the VM executes a compiledtrace, it cannot guarantee that the same path will be followedor that the same types will occur in subsequent loop iterations.
Hence, recording and compiling a tracespeculatesthat the path andtyping will be exactly as they were during recording for subsequentiterations of the loop.Every compiled trace contains all theguards(checks) requiredto validate the speculation. If one of the guards fails (if controlflow is different, or a value of a different type is generated), thetrace exits. If an exit becomes hot, the VM can record abranchtracestarting at the exit to cover the new path. In this way, the VMrecords atrace treecovering all the hot paths through the loop.Nested loops can be difficult to optimize for tracing VMs. Ina na ̈ıve implementation, inner loops would become hot first, andthe VM would start tracing there. When the inner loop exits, theVM would detect that a different branch was taken. The VM wouldtry to record a branch trace, and find that the trace reaches not theinner loop header, but the outer loop header. At this point, the VMcould continue tracing until it reaches the inner loop header again,thus tracing the outer loop inside a trace tree for the inner loop.But this requires tracing a copy of the outer loop for every side exitand type combination in the inner loop. In essence, this is a formof unintended tail duplication, which can easily overflow the codecache. Alternatively, the VM could simply stop tracing, and give upon ever tracing outer loops.We solve the nested loop problem by recordingnested tracetrees. Our system traces the inner loop exactly as the na ̈ıve version.The system stops extending the inner tree when it reaches an outerloop, but then it starts a new trace at the outer loop header. Whenthe outer loop reaches the inner loop header, the system tries to callthe trace tree for the inner loop. If the call succeeds, the VM recordsthe call to the inner tree as part of the outer trace and finishesthe outer trace as normal. In this way, our system can trace anynumber of loops nested to any depth without causing excessive tailduplication.These techniques allow a VM to dynamically translate a pro-gram to nested, type-specialized trace trees. Because traces cancross function call boundaries, our techniques also achieve the ef-fects of inlining. Because traces have no internal control-flow joins,they can be optimized in linear time by a simple compiler (10).Thus, our tracing VM efficiently performs the same kind of op-timizations that would require interprocedural analysis in a staticoptimization setting. This makes tracing an attractive and effectivetool to type specialize even complex function call-rich code.We implemented these techniques for an existing JavaScript in-terpreter, SpiderMonkey. We call the resulting tracing VMTrace-Monkey. TraceMonkey supports all the JavaScript features of Spi-derMonkey, with a 2x-20x speedup for traceable programs.This paper makes the following contributions:•We explain an algorithm for dynamically forming trace trees tocover a program, representing nested loops as nested trace trees.•We explain how to speculatively generate efficient type-specializedcode for traces from dynamic language programs.•We validate our tracing techniques in an implementation basedon the SpiderMonkey JavaScript interpreter, achieving 2x-20xspeedups on many programs.The remainder of this paper is organized as follows. Section 3 isa general overview of trace tree based compilation we use to cap-ture and compile frequently executed code regions. In Section 4we describe our approach of covering nested loops using a num-ber of individual trace trees. In Section 5 we describe our trace-compilation based speculative type specialization approach we useto generate efficient machine code from recorded bytecode traces.Our implementation of a dynamic type-specializing compiler forJavaScript is described in Section 6. Related work is discussed inSection 8. In Section 7 we evaluate our dynamic compiler based on1 for (var i = 2; i < 100; ++i) {2 if (!primes[i])3 continue;4 for (var k = i + i; i < 100; k += i)5 primes[k] = false;6 }Figure 1. Sample program: sieve of Eratosthenes.primesisinitialized to an array of 100falsevalues on entry to this codesnippet.InterpretBytecodesMonitorRecordLIR TraceExecuteCompiled TraceEnterCompiled TraceCompileLIR TraceLeaveCompiled Traceloop edgehotloop/exitabort recordingfinish at loop headercold/blacklistedloop/exitcompiled trace readyloop edge with same typesside exit to existing traceside exit,no existing traceOverheadInterpretingNativeSymbol KeyFigure 2.State machine describing the major activities of Trace-Monkey and the conditions that cause transitions to a new activ-ity. In the dark box, TM executes JS as compiled traces. In thelight gray boxes, TM executes JS in the standard interpreter. Whiteboxes are overhead. Thus, to maximize performance, we need tomaximize time spent in the darkest box and minimize time spent inthe white boxes. The best case is a loop where the types at the loopedge are the same as the types on entry–then TM can stay in nativecode until the loop is done.a set of industry benchmarks. The paper ends with conclusions inSection 9 and an outlook on future work is presented in Section 10.2. Overview: Example Tracing RunThis section provides an overview of our system by describinghow TraceMonkey executes an example program. The exampleprogram, shown in Figure 1, computes the first 100 prime numberswith nested loops. The narrative should be read along with Figure 2,which describes the activities TraceMonkey performs and when ittransitions between the loops.TraceMonkey always begins executing a program in the byte-code interpreter. Every loop back edge is a potential trace point.When the interpreter crosses a loop edge, TraceMonkey invokesthetrace monitor, which may decide to record or execute a nativetrace. At the start of execution, there are no compiled traces yet, sothe trace monitor counts the number of times each loop back edge isexecuted until a loop becomeshot, currently after 2 crossings. Notethat the way our loops are compiled, the loop edge is crossed beforeentering the loop, so the second crossing occurs immediately afterthe first iteration.Here is the sequence of events broken down by outer loopiteration:
v0 := ld state[748] // load primes from the trace activation recordst sp[0], v0 // store primes to interpreter stackv1 := ld state[764] // load k from the trace activation recordv2 := i2f(v1) // convert k from int to doublest sp[8], v1 // store k to interpreter stackst sp[16], 0 // store false to interpreter stackv3 := ld v0[4] // load class word for primesv4 := and v3, -4 // mask out object class tag for primesv5 := eq v4, Array // test whether primes is an arrayxf v5 // side exit if v5 is falsev6 := js_Array_set(v0, v2, false) // call function to set array elementv7 := eq v6, 0 // test return value from callxt v7 // side exit if js_Array_set returns false.Figure 3. LIR snippet for sample program.This is the LIR recorded for line 5 of the sample program in Figure 1. The LIR encodesthe semantics in SSA form using temporary variables. The LIR also encodes all the stores that the interpreter would do to its data stack.Sometimes these stores can be optimized away as the stack locations are live only on exits to the interpreter. Finally, the LIR records guardsand side exits to verify the assumptions made in this recording: thatprimesis an array and that the call to set its element succeeds.mov edx, ebx(748) // load primes from the trace activation recordmov edi(0), edx // (*) store primes to interpreter stackmov esi, ebx(764) // load k from the trace activation recordmov edi(8), esi // (*) store k to interpreter stackmov edi(16), 0 // (*) store false to interpreter stackmov eax, edx(4) // (*) load object class word for primesand eax, -4 // (*) mask out object class tag for primescmp eax, Array // (*) test whether primes is an arrayjne side_exit_1 // (*) side exit if primes is not an arraysub esp, 8 // bump stack for call alignment conventionpush false // push last argument for callpush esi // push first argument for callcall js_Array_set // call function to set array elementadd esp, 8 // clean up extra stack spacemov ecx, ebx // (*) created by register allocatortest eax, eax // (*) test return value of js_Array_setje side_exit_2 // (*) side exit if call failed...side_exit_1:mov ecx, ebp(-4) // restore ecxmov esp, ebp // restore espjmp epilog // jump to ret statementFigure 4. x86 snippet for sample program.This is the x86 code compiled from the LIR snippet in Figure 3. Most LIR instructions compileto a single x86 instruction. Instructions marked with(*)would be omitted by an idealized compiler that knew that none of the side exitswould ever be taken. The 17 instructions generated by the compiler compare favorably with the 100+ instructions that the interpreter wouldexecute for the same code snippet, including 4 indirect jumps.i=2.This is the first iteration of the outer loop. The loop onlines 4-5 becomes hot on its second iteration, so TraceMonkey en-ters recording mode on line 4. In recording mode, TraceMonkeyrecords the code along the trace in a low-level compiler intermedi-ate representation we callLIR. The LIR trace encodes all the oper-ations performed and the types of all operands. The LIR trace alsoencodesguards, which are checks that verify that the control flowand types are identical to those observed during trace recording.Thus, on later executions, if and only if all guards are passed, thetrace has the required program semantics.TraceMonkey stops recording when execution returns to theloop header or exits the loop. In this case, execution returns to theloop header on line 4.After recording is finished, TraceMonkey compiles the trace tonative code using the recorded type information for optimization.The result is a native code fragment that can be entered if theinterpreter PC and the types of values match those observed whentrace recording was started. The first trace in our example,T45,covers lines 4 and 5. This trace can be entered if the PC is at line 4,iandkare integers, andprimesis an object. After compilingT45,TraceMonkey returns to the interpreter and loops back to line 1.i=3.Now the loop header at line 1 has become hot, so Trace-Monkey starts recording. When recording reaches line 4, Trace-Monkey observes that it has reached an inner loop header that al-ready has a compiled trace, so TraceMonkey attempts to nest theinner loop inside the current trace. The first step is to call the innertrace as a subroutine. This executes the loop on line 4 to completionand then returns to the recorder. TraceMonkey verifies that the callwas successful and then records the call to the inner trace as part ofthe current trace. Recording continues until execution reaches line1, and at which point TraceMonkey finishes and compiles a tracefor the outer loop,T16.
i=4.On this iteration, TraceMonkey callsT16. Becausei=4, theifstatement on line 2 is taken. This branch was not taken in theoriginal trace, so this causesT16to fail a guard and take a side exit.The exit is not yet hot, so TraceMonkey returns to the interpreter,which executes the continue statement.i=5.TraceMonkey callsT16, which in turn calls the nested traceT45.T16loops back to its own header, starting the next iterationwithout ever returning to the monitor.i=6.On this iteration, the side exit on line 2 is taken again. Thistime, the side exit becomes hot, so a traceT23,1is recorded thatcovers line 3 and returns to the loop header. Thus, the end ofT23,1jumps directly to the start ofT16. The side exit is patched so thaton future iterations, it jumps directly toT23,1.At this point, TraceMonkey has compiled enough traces to coverthe entire nested loop structure, so the rest of the program runsentirely as native code.3. Trace TreesIn this section, we describe traces, trace trees, and how they areformed at run time. Although our techniques apply to any dynamiclanguage interpreter, we will describe them assuming a bytecodeinterpreter to keep the exposition simple.3.1 TracesAtraceis simply a program path, which may cross function callboundaries. TraceMonkey focuses onloop traces, that originate ata loop edge and represent a single iteration through the associatedloop.Similar to an extended basic block, a trace is only entered atthe top, but may have many exits. In contrast to an extended basicblock, a trace can contain join nodes. Since a trace always onlyfollows one single path through the original program, however, joinnodes are not recognizable as such in a trace and have a singlepredecessor node like regular nodes.Atyped traceis a trace annotated with a type for every variable(including temporaries) on the trace. A typed trace also has an entrytype mapgiving the required types for variables used on the tracebefore they are defined. For example, a trace could have a type map(x: int, b: boolean), meaning that the trace may be enteredonly if the value of the variablexis of typeintand the value ofbis of typeboolean. The entry type map is much like the signatureof a function.In this paper, we only discuss typed loop traces, and we willrefer to them simply as “traces”. The key property of typed looptraces is that they can be compiled to efficient machine code usingthe same techniques used for typed languages.In TraceMonkey, traces are recorded in trace-flavored SSALIR(low-level intermediate representation). In trace-flavored SSA (orTSSA), phi nodes appear only at the entry point, which is reachedboth on entry and via loop edges. The important LIR primitivesare constant values, memory loads and stores (by address andoffset), integer operators, floating-point operators, function calls,and conditional exits. Type conversions, such as integer to double,are represented by function calls. This makes the LIR used byTraceMonkey independent of the concrete type system and typeconversion rules of the source language. The LIR operations aregeneric enough that the backend compiler is language independent.Figure 3 shows an example LIR trace.Bytecode interpreters typically represent values in a variouscomplex data structures (e.g., hash tables) in a boxed format (i.e.,with attached type tag bits). Since a trace is intended to representefficient code that eliminates all that complexity, our traces oper-ate on unboxed values in simple variables and arrays as much aspossible.A trace records all its intermediate values in a small activationrecord area. To make variable accesses fast on trace, the trace alsoimports local and global variables by unboxing them and copyingthem to its activation record. Thus, the trace can read and writethese variables with simple loads and stores from a native activationrecording, independently of the boxing mechanism used by theinterpreter. When the trace exits, the VM boxes the values fromthis native storage location and copies them back to the interpreterstructures.For every control-flow branch in the source program, therecorder generates conditional exit LIR instructions. These instruc-tions exit from the trace if required control flow is different fromwhat it was at trace recording, ensuring that the trace instructionsare run only if they are supposed to. We call these instructionsguardinstructions.Most of our traces represent loops and end with the specialloopLIR instruction. This is just an unconditional branch to the top ofthe trace. Such traces return only via guards.Now, we describe the key optimizations that are performed aspart of recording LIR. All of these optimizations reduce complexdynamic language constructs to simple typed constructs by spe-cializing for the current trace. Each optimization requires guard in-structions to verify their assumptions about the state and exit thetrace if necessary.Type specialization.All LIR primitives apply to operands of specific types. Thus,LIR traces are necessarily type-specialized, and a compiler caneasily produce a translation that requires no type dispatches. Atypical bytecode interpreter carries tag bits along with each value,and to perform any operation, must check the tag bits, dynamicallydispatch, mask out the tag bits to recover the untagged value,perform the operation, and then reapply tags. LIR omits everythingexcept the operation itself.A potential problem is that some operations can produce valuesof unpredictable types. For example, reading a property from anobject could yield a value of any type, not necessarily the typeobserved during recording. The recorder emits guard instructionsthat conditionally exit if the operation yields a value of a differenttype from that seen during recording. These guard instructionsguarantee that as long as execution is on trace, the types of valuesmatch those of the typed trace. When the VM observes a side exitalong such a type guard, a new typed trace is recorded originatingat the side exit location, capturing the new type of the operation inquestion.Representation specialization: objects.In JavaScript, namelookup semantics are complex and potentially expensive becausethey include features like object inheritance andeval. To evaluatean object property read expression likeo.x, the interpreter mustsearch the property map ofoand all of its prototypes and parents.Property maps can be implemented with different data structures(e.g., per-object hash tables or shared hash tables), so the searchprocess also must dispatch on the representation of each objectfound during search. TraceMonkey can simply observe the result ofthe search process and record the simplest possible LIR to accessthe property value. For example, the search might finds the value ofo.xin the prototype ofo, which uses a shared hash-table represen-tation that placesxin slot 2 of a property vector. Then the recordedcan generate LIR that readso.xwith just two or three loads: one toget the prototype, possibly one to get the property value vector, andone more to get slot 2 from the vector. This is a vast simplificationand speedup compared to the original interpreter code. Inheritancerelationships and object representations can change during execu-tion, so the simplified code requires guard instructions that ensurethe object representation is the same. In TraceMonkey, objects’ rep-
