Trace-based Just-in-Time Type Specialization for Dynamic Languages Andreas 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.com Adobe Corporation # {edwsmith,rreitmai}@adobe.com Intel Corporation$ {mohammad.r.haghighat}@intel.com University of California, Irvine+ {mbebenit,changm,franz}@uci.edu Abstract and is used for the application logic of browser-based productivity Dynamic languages such as JavaScript are more difficult to com- applications such as Google Mail, Google Docs and Zimbra Col- pile than statically typed ones. Since no concrete type information laboration Suite. In thisdomain, in order to provide a fluiduser is available, traditional compilers needto emit generic code that canexperience and enable a newgeneration of applications, virtual ma- handle all possible type combinations at runtime. We present an al- chines must provide a low startup timeand highperformance. ternative compilation technique for dynamically-typed languages Compilers for statically typed languages rely on type informa- that identifies frequently executed loop traces at run-time and then tion togenerate efficient machine code. In a dynamically typed pro- generates machine code on the fly that is specialized for the ac- gramming language such as JavaScript, the types of expressions tual dynamic types occurring on each path through the loop. Our may vary at runtime. This means that the compiler can no longer method provides cheap inter-procedural type specialization, and an easily transform operations into machine instructions that operate elegant and efficient way of incrementally compiling lazily discov- on one specific type. Without exact type information, the compiler ered alternative paths through nested loops. We have implemented must emit slower generalized machine code that can deal with all a dynamic compiler for JavaScript based on our technique and we potential type combinations. While compile-time static type infer- have measured speedups of 10x and more for certain benchmark ence might be able to gather type information to generate opti- programs. mized machine code, traditional static analysis is very expensive and hence not well suited for the highly interactive environment of Categories and Subject Descriptors D.3.4 [Programming Lan- a web browser. guages]: Processors — Incremental compilers, code generation. We present a trace-based compilation technique for dynamic General Terms Design, Experimentation, Measurement, Perfor- languages that reconciles speed ofcompilation with excellent per- mance. formance of the generated machine code. Our system uses a mixed- mode execution approach: the system starts running JavaScript in a Keywords JavaScript, just-in-time compilation, trace trees. fast-starting bytecode interpreter. As the program runs,the system identifies hot (frequently executed) bytecode sequences, records 1. Introduction them, and compiles them to fast native code. We call such ase- quence of instructions atrace. Dynamic languages such as JavaScript, Python, and Ruby, are pop- Unlike method-based dynamic compilers, our dynamic com- ular since they are expressive, accessible to non-experts, and make piler operates atthe granularity of individual loops. This design deployment as easy as distributing a source file. They are usedfor choice is based on the expectation that programs spend most of small scripts as well as for complex applications. JavaScript, for their time in hot loops. Even in dynamically typed languages, we example, is the de facto standard forclient-side webprogramming expect hot loops to be mostly type-stable, meaning that the types of values are invariant. (12) Forexample, wewould expect loop coun- ters that start as integers to remain integers for all iterations.When both of these expectations hold, a trace-based compiler cancover Permission tomake digital or hardcopies of all or part ofthis workfor personal or theprogram execution with asmall number oftype-specialized classroom use is granted withoutfee provided that copies are not made or distributed ficiently compiled traces.for profit or commercial advant on the first page. To copy otherwise, to republish, to post on servers orto redistribute Eachcompiled trace covers one path through theprogra to lists, requires prior specific permission and/or a fee. one mapping of values to types. When the VM executes a compiled PLDI’09, June 15–20, 2009, Dublin, Ireland. trace, it cannot guarantee that the same path will be followed Copyright © c 2009 ACM978-1-60558-392-1/09/06...$5.00 or that the same types will occur in subsequent loop iterations. Hence, recording and compiling a trace speculates thatthe pathand 1 for (var i = 2; i < 100; ++i) { typing will be exactly asthey were during recording for subsequent 2 if (!primes[i]) iterations of the loop. 3 continue; Every compiled trace contains all the guards (checks) required 4 for (var k = i + i; i < 100; k += i) to validate the speculation. Ifone of the guards fails (if control 5 primes[k] = false; flow is different, or a value of adifferent type is generated), the 6 } trace exits. If an exit becomes hot, the VM can record a branch trace starting at the exit to coverthe new path.In this way, the VM Figure 1. Sample program: sieve of Eratosthenes. primes is records a trace tree covering allthe hotpaths through the loop. initialized to an array of100 false values on entry tothis code Nested loops can be difficult to optimize for tracing VMs. In snippet. a naıve implementation, inner loops would become hot first, and the VM would start tracing there. When the inner loop exits, the VM would detect that a different branch was taken. TheVM would try to record a branch trace, and find that the tracereaches not the Symbol Key inner loop header, but the outer loop header. At this point,the VM Interpret Bytecodes Overhead could continue tracing until it reaches the innerloop header again, thus tracing the outer loop inside a trace tree for the innerloop. loop Interpreting edge cold/blacklisted But this requires tracing a copy of the outerloop for every side exit loop/exit Native and type combination in the inner loop. Inessence, this is aform abort Monitor compiled trace of unintended tail duplication, which can easily overflow thecode recording ready cache. Alternatively, the VM could simply stop tracing, and give up Record hot LIR Trace loop/exit Enter on ever tracing outer loops. Compiled Trace We solve the nested loop problem by recording nested trace finish at loop header loop edge with trees. Our system traces the inner loop exactly as thenaıve version. same types The system stops extending the inner tree when it reaches an outer Compile Execute loop, but then it starts a new trace at the outerloop header. When LIR Trace Compiled Trace the outer loop reaches the inner loop header, the system tries to call the trace tree for theinner loop. If thecall succeeds, the VM records side exit, side exit to no existin the call to the inner tree as part ofthe outer trace and finishes Leave the outer trace as normal. In this way, our system can trace any Compiled Trace number of loops nested to any depth without causing excessive tail duplication. These techniques allow a VM to dynamically translate a pro- Figure 2. State machine describing the major activities of Trace- gram to nested, type-specialized trace trees. Because traces can Monkey and the conditions that cause transitions toa new activ- cross function call boundaries, our techniques alsoachieve the ef- ity. In the dark box, TM executes JS as compiled traces. Inthe fects of inlining. Because traces haveno internal control-flow joins, light gray boxes, TM executes JS inthe standard interpreter. White they can be optimized in linear time by a simple compiler (10). boxes are overhead. Thus, to maximize performance, we need to Thus, our tracing VM efficiently performs the same kind of op- maximize time spent in the darkest box and minimize time spent in timizations that would require interprocedural analysis in astatic the white boxes. The best case is aloop where the typesat the loop optimization setting. This makes tracing an attractive and effective edge are thesame asthe types on entry–then TM canstay in native tool to type specialize even complex function call-rich code. code until the loop isdone. We implemented these techniques for an existing JavaScript in- terpreter, SpiderMonkey. We call the resulting tracing VMTrace- Monkey. TraceMonkey supports all the JavaScript features ofSpi- a set of industry benchmarks. The paper ends with conclusions in derMonkey, with a 2x-20x speedup for traceable programs. Section 9 and an outlook on future work is presented in Section 10. This paper makes the following contributions: 2. Overview: Example Tracing Run • We explain an algorithm for dynamically forming trace trees to cover a program, representing nested loops as nested tracetrees. This section provides an overview of our system by describing how TraceMonkey executes an example program. The example • We explain how to speculatively generate efficient type-specialized program, shown in Figure 1, computes the first 100 prime numbers code for traces from dynamic language programs. with nested loops. The narrative should be readalong withFigure 2, • We validate our tracing techniques inan implementation based which describes the activities TraceMonkey performs and when it on the SpiderMonkey JavaScript interpreter, achieving 2x-20x transitions between the loops. speedups on many programs. TraceMonkey always begins executing a program in the byte- code interpreter. Every loop back edge is apotential trace point. The remainder of this paper isorganized asfollows. Section 3 is When the interpreter crosses aloop edge, TraceMonkey invokes a general overview of trace tree based compilation weuse tocap- the trace monitor, which may decide to record orexecute a native ture and compile frequently executed code regions. In Section 4 trace. At the start of execution, thereare no compiled tracesyet, so we describe our approach of covering nested loops using anum- the trace monitor counts the number of times eachloop backedge is ber of individual trace trees. InSection 5 we describe our trace- executed until aloop becomes hot, currently after 2 crossings. Note compilation based speculative type specialization approach we use that the way our loops are compiled, theloop edge is crossed before to generate efficient machine code from recorded bytecode traces. entering the loop, so the second crossing occurs immediately after Our implementation of a dynamic type-specializing compiler for the first iteration. JavaScript is described in Section 6.Related work isdiscussed in Here is the sequence of events broken down by outer loop Section 8. In Section 7we evaluate our dynamic compiler based on iteration: v0 := ld state[748] // load primes from the trace activation record st sp[0], v0 // store primes to interpreter stack v1 := ld state[764] // load k from the trace activation record v2 := i2f(v1) // convert k from int to double st sp[8], v1 // store k to interpreter stack st sp[16], 0 // store false to interpreter stack v3 := ld v0[4] // load class word for primes v4 := and v3, -4 // mask out object class tag for primes v5 := eq v4, Array // test whether primes is an array xf v5 // side exit if v5 is false v6 := js_Array_set(v0, v2, false) // call function to set array element v7 := eq v6, 0 // test return value from call xt 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 encodes the semantics in SSA form using temporary variables. The LIR also encodes all the stores thatthe interpreter woulddo to itsdata stack. Sometimes these stores can be optimized away as the stack locations are live only on exits tothe interpreter. Finally, the LIR records guard and side exits to verify theassumptions made inthis recording: that primes is an array and thatthecall to set its elementsucceeds. mov edx, ebx(748) // load primes from the trace activation record mov edi(0), edx // (*) store primes to interpreter stack mov esi, ebx(764) // load k from the trace activation record mov edi(8), esi // (*) store k to interpreter stack mov edi(16), 0 // (*) store false to interpreter stack mov eax, edx(4) // (*) load object class word for primes and eax, -4 // (*) mask out object class tag for primes cmp eax, Array // (*) test whether primes is an array jne side_exit_1 // (*) side exit if primes is not an array sub esp, 8 // bump stack for call alignment convention push false // push last argument for call push esi // push first argument for call call js_Array_set // call function to set array element add esp, 8 // clean up extra stack space mov ecx, ebx // (*) created by register allocator test eax, eax // (*) test return value of js_Array_set je side_exit_2 // (*) side exit if call failed ... side_exit_1: mov ecx, ebp(-4) // restore ecx mov esp, ebp // restore esp jmp epilog // jump to ret statement Figure 4. x86 snippet for sample program. This is the x86 code compiled from theLIR snippet in Figure 3. Most LIR instructions compile to a single x86 instruction. Instructions marked with(*) would beomitted byan idealized compiler thatknew that none of the side exits would ever be taken. The 17 instructions generated by thecompiler compare favorably withthe 100+ instructions that the interpreter would execute for the same code snippet, including 4 indirect jumps. i=2. This is the first iteration ofthe outer loop. The loop on interpreter PC and the types ofvalues match those observed when lines 4-5 becomes hot on its second iteration, so TraceMonkey en- trace recording was started. The first trace inour example, T45, ters recording mode on line 4. In recording mode, TraceMonkey covers lines 4and 5. This trace can be entered if thePC is at line4, records the code along the trace in a low-level compiler intermedi- iand k are integers, andprimes isan object. After compiling T45, ate representation we call LIR. The LIR trace encodes all the oper- TraceMonkey returns to the interpreter and loopsback to line 1. ations performed and the types of all operands. TheLIR trace also i=3. Now the loop header at line 1has become hot, so Trace- encodes guards, which are checks that verify that thecontrol flow Monkey starts recording. When recording reaches line 4, Trace- and types are identical to those observed during trace recording. Monkey observes that it has reached an inner loop header that al- Thus, on later executions, ifand only ifall guards arepassed, the ready has a compiled trace, so TraceMonkey attempts to nest the trace has the required program semantics. inner loop inside the current trace. The first step isto call theinner TraceMonkey stops recording when execution returns to the trace as asubroutine. This executes theloop on line4 to completion loop header or exits the loop. Inthis case, execution returns to the and then returns to the recorder. TraceMonkey verifies that thecall loop header on line 4. was successful and then records the call to the inner trace as part of After recording is finished, TraceMonkey compiles the trace to the current trace. Recording continues until execution reaches line native code using the recorded type information for optimization. 1, and at which point TraceMonkey finishes and compiles a trace The result is a native code fragment that can be entered if the for the outer loop, T16. i=4. On this iteration, TraceMonkey calls T16.Because i=4, the A trace records all its intermediate values in a smallactivation if statement on line 2 is taken. This branch was not taken in the record area. To make variable accesses fast on trace, the trace also original trace, sothis causes T16to faila guard and take a sideexit. imports local andglobal variables by unboxing themand copying The exit is not yet hot, soTraceMonkey returns to the interpreter, them to its activation record. Thus, thetrace canread and write which executes the continue statement. these variables with simple loads andstores from a native activation i=5. TraceMonkey calls T16, which in turn calls the nested trace recording, independently ofthe boxing mechanism used by the T45. T16 loops back to its own header, starting the next iteration interpreter. When the trace exits, theVM boxes the values from without ever returning to the monitor. this native storage location andcopies them back to the interpreter i=6. On this iteration, theside exiton line2 is takenagain. This structures. time, the side exit becomes hot, so atrace T23,1 isrecorded that For every control-flow branch in the source program, the covers line 3 and returns tothe loop header. Thus, the end of T23,1 recorder generates conditional exit LIR instructions. These instruc- jumps directly to the start ofT16. The side exit is patched so that tions exit from thetrace if required control flow is different from on future iterations, it jumps directly to T23,1. what it was at trace recording, ensuring that the traceinstructions At this point, TraceMonkey has compiled enough traces to cover are run only if they are supposed to. We call these instructions the entire nested loop structure, sothe rest ofthe program runs guard instructions. entirely as native code. Most of our traces represent loops andend with the special loop LIR instruction. This is just an unconditional branch to the top of the trace. Such traces return only via guards. 3. Trace Trees Now, we describe the key optimizations that are performed as In this section, we describe traces, trace trees, and how theyare part of recording LIR. All of these optimizations reduce complex formed at run time. Although our techniques apply to anydynamic dynamic language constructs to simple typed constructs by spe- language interpreter, we will describe them assuming abytecode cializing for the current trace. Eachoptimization requires guard in- interpreter to keep the exposition simple. structions to verify their assumptions about thestate andexit the trace if necessary. 3.1 Traces Type specialization. All LIR primitives apply to operands of specific types. Thus, A trace is simply a program path, which may cross function call LIR traces are necessarily type-specialized, and a compiler can boundaries. TraceMonkey focuses on loop traces, that originate at easily produce a translation that requires notype dispatches. A a loop edge and represent asingle iteration through theassociated typical bytecode interpreter carries tag bits alongwith each value, loop. and to perform any operation, must check the tagbits, dynamically Similar to an extended basic block, atrace is only entered at dispatch, mask out the tag bits to recover the untagged value, the top, but may have many exits. In contrast to an extended basic perform the operation, and then reapply tags.LIR omits everything block, a trace can contain join nodes. Since atrace always only except the operation itself. follows one single path through the original program, however, join A potential problem is that some operations canproduce values nodes are not recognizable as such in a trace and have asingle of unpredictable types. For example, reading aproperty from an predecessor node like regular nodes. object could yield a value of any type, not necessarily the type A typed trace is atrace annotated with a type for every variable observed during recording. The recorder emits guard instructions (including temporaries) on the trace. A typed tracealso has anentry that conditionally exitif the operation yieldsa value of a different type map giving the required types for variables used on the trace type from that seen during recording. These guard instructions before they are defined. For example, a trace could havea typemap guarantee that as long as execution is on trace, the types of values(x: in only if the value of the variable x isoftype intand thevalue of b along such a type guard, anew typed trace isrecorded originating is of type boolean. The entry type map is much like the signature at the side exit location, capturing the new type of theoperation in of a function. question. In this paper, we only discuss typed loop traces, and wewill Representation specialization: objects. In JavaScript, name refer to them simply as “traces”. The key property oftyped loop lookup semantics are complex and potentially expensive because traces is that they can becompiled toefficient machine code using they include features like object inheritance and eval.To evaluate the same techniques used for typed languages. an object property read expression like o.x, the interpreter must In TraceMonkey, traces are recorded in trace-flavored SSA LIR search the property map of o and all ofits prototypes and parents. (low-level intermediate representation). In trace-flavored SSA(or Property maps can be implemented with different data structures TSSA), phi nodes appear only at the entry point, which is reached (e.g., per-object hash tables orshared hash tables), so the search both on entry and via loop edges. The important LIR primitives process also must dispatch on the representation of each object are constant values, memory loads and stores (by address and found during search. TraceMonkey can simply observe the result of offset), integer operators, floating-point operators, function calls, the search process andrecord thesimplest possible LIR to access and conditional exits. Type conversions, such as integer to double, the property value. For example, the search might finds the value of are represented by function calls. This makes the LIR used by o.x in the prototype of o,which uses a shared hash-table represen- TraceMonkey independent of the concrete type system and type tation that places x in slot2 of aproperty vector. Then the recorded conversion rules of the source language. The LIR operations are can generate LIR that reads o.x with just twoor three loads: one to generic enough that the backend compiler islanguage independent. get the prototype, possibly one to get the property value vector, and Figure 3 shows an example LIR trace. one more to get slot 2from the vector. This is avast simplification Bytecode interpreters typically represent values ina various and speedup compared to the original interpreter code. Inheritance complex data structures (e.g., hash tables) in aboxed format (i.e., relationships and object representations can change during execu- with attached type tag bits). Since a trace is intended to represent tion, so the simplified coderequires guard instructions that ensure efficient code that eliminates all that complexity, our traces oper- the object representation is thesame. In TraceMonkey, objects’ rep- ate on unboxed values in simple variables and arrays asmuch as possible. resentations are assigned an integer key called the object shape. Starting a tree. Tree trees always start at loop headers, because Thus, the guard is asimple equality check onthe object shape. they are a natural place to look for hot paths.In TraceMonkey, loop Representation specialization: numbers. JavaScript has no headers are easy to detect–the bytecode compiler ensures that a integer type, only a Number type that is the set of64-bit IEEE- bytecode is a loop header iff it is the targetof a backward branch. 754 floating-pointer numbers (“doubles”). But many JavaScript TraceMonkey starts a tree when a given loop header has been exe- operators, in particular array accesses and bitwise operators, really cuted a certain number of times(2 in thecurrent implementation). operate on integers, so they first convert the number to an integer, Starting a tree justmeans starting recording a trace for the current and then convert any integer result back to adouble.1 Clearly, a point and type map and marking the trace as theroot of atree. Each JavaScript VM that wants to be fast must find away to operate on tree is associated with a loop header and typemap, so theremay be integers directly and avoid these conversions. several trees for a given loop header. In TraceMonkey, we support two representations for numbers: Closing the loop. Trace recording can end inseveral ways. integers and doubles. The interpreter uses integer representations Ideally, the trace reaches theloop header where it started with as much as it can, switching forresults thatcan onlybe represented the same type map as on entry. This is called a type-stable loop as doubles. When a trace is started, some values may beimported iteration. In this case, theend ofthe trace can jump right to the and represented as integers. Some operations on integers require beginning, as all the value representations are exactly as neededto guards. For example, adding two integers can produce a value too enter the trace. The jump can even skip the usual code thatwould large for the integer representation. copy out the state at the end of thetrace and copyit backin to the Function inlining. LIR traces can cross function boundaries trace activation record toenter a trace. in either direction, achieving function inlining. Moveinstructions In certain cases the trace might reach the loop header with a need to be recorded for function entry and exit to copyarguments different type map. This scenario is sometime observed for the first in and return values out. These move statements are thenoptimized iteration of aloop. Some variables inside the loop mightinitially be away by the compiler using copy propagation. In order tobe able undefined, before they are set to a concrete type duringthe first loop to return to the interpreter, the trace must also generate LIRto iteration. When recording such an iteration, the recorder cannot record that a call frame has been entered and exited. The frame link the trace back toits own loop header since it istype-unstable. entry and exit LIR saves just enough information to allow the Instead, the iteration is terminated witha side exit that will always intepreter call stack tobe restored later andis much simpler than fail and return to the interpreter. At the sametime a newtrace is the interpreter’s standard call code. If the function beingentered recorded with the new type map. Every time an additional type- is not constant (which in JavaScript includes anycall by function unstable trace is added toa region, its exit type map is compared to name), the recorder must also emit LIR to guard that thefunction the entry map of all existing traces in casethey complement each is the same. other. With this approach we are able tocover type-unstable loop Guards and side exits. Each optimization described above iterations as long they eventually form a stable equilibrium. requires one or more guards to verify the assumptions made in Finally, the trace might exit theloop before reaching theloop doing the optimization. A guard isjust a group of LIRinstructions header, for example because execution reaches a break or return that performs a test and conditional exit. The exit branches to a statement. In this case, the VM simply ends the trace withan exit side exit, a small off-trace piece of LIR that returns a pointer to to the trace monitor. a structure that describes the reason for the exit along with the As mentioned previously, we may speculatively chose to rep- interpreter PC at the exit point and any otherdata needed to restore resent certain Number-typed values as integers on trace. We do so the interpreter’s state structures. when we observe that Number-typed variables contain an integer Aborts. Some constructs are difficult to record in LIR traces. value at trace entry. If during trace recording the variable is unex- For example, eval or calls to external functions can change the pectedly assigned a non-integer value, we have towiden the type program state in unpredictable ways, making it difficult for the of the variable to a double. As a result, the recorded trace becomes tracer to know the current type map in order to continue tracing. inherently type-unstable since itstarts with aninteger value but A tracing implementation can also have any number of other limi- ends with a double value. This represents a mis-speculation, since tations, e.g.,a small-memory device may limit thelength of traces. at trace entry wespecialized theNumber-typed value to an integer, When any situation occurs that prevents the implementation from assuming that at the loop edge wewould again find aninteger value continuing trace recording, the implementation aborts tracerecord- in the variable, allowing us to closethe loop.To avoidfuture spec- ing and returns to the trace monitor. ulative failures involving this variable, and to obtaina type-stable trace we note the fact that the variable in question as been observed 3.2 Trace Trees to sometimes hold non-integer values inan advisory data structure which we call the “oracle”. Especially simple loops, namely those where control flow, value When compiling loops, we consult the oracle before specializ- types, value representations, and inlined functions are allinvariant, ingvalues to integers. Speculation towards integers is performed can be represented by a single trace. But most loops have at least only if no adverse information isknown to the oracle about that some variation, and so the program will take side exits from the particular variable. Whenever we accidentally compile a loop that main trace. When a side exit becomes hot, TraceMonkey starts a is type-unstable due to mis-speculation of a Number-typed vari- new branch trace from that point and patches the side exitto jump able, we immediately trigger the recording ofa new trace, which directly to that trace. In this way, asingle trace expandson demand based on the now updated oracle information willstart with adou- to a single-entry, multiple-exit trace tree. ble value and thus become type stable. This section explains how trace trees areformed during execu- Extending a tree. Side exits lead to different paths through tion. The goal is to form trace trees during execution that cover allthe loop, or paths withdifferent typesor representations. Thus, to the hot paths of the program. completely cover the loop, the VM must record traces starting at all side exits. These traces arerecorded much like root traces: there is a counter for each side exit, and when the counter reaches a hotness1Array be converted from a double to astring for theproperty access operator, and trace, using the loop headerof the root trace as the target to re then to an integer internally to the arrayimplementation. Our implementation does not extend at all side exits. It extends only if the side exit is for acontrol-flow branch, and only ifthe side T exit does not leave the loop. In particular we donot wantto extend Tree
Anchor a trace tree along a path that leads toan outer loop, because we Trunk
Trace want to cover such paths in an outer tree through tree nesting. Trace
Anchor Branch
Trace 3.3 Blacklisting Guard Sometimes, a program follows a path that cannot be compiled Side
Exit into a trace, usually because oflimitations in the implementation. TraceMonkey does not currently support recording throwing and catching of arbitrary exceptions. This design trade off was chosen, because exceptions are usually rare in JavaScript. However, ifa program opts to use exceptions intensively, we would suddenly incur a punishing runtime overhead if we repeatedly try to record a trace for this path and repeatedly fail to do so, since we abort tracing every time we observe an exception being thrown. Figure 5. A tree with two traces, a trunk trace and one branch As a result, ifa hot loop contains traces that alwaysfail, the VMtrace. The trunk trace contains a guardto whicha branch trace was could potentially run much more slowly than the base interpreter: attached. The branch trace contain a guard thatmay failand trigger the VM repeatedly spends time trying to record traces, but is never aside exit. Both thetrunk andthe branch traceloop backto the tree able to run any. To avoid this problem, whenever theVM is about anchor, which is the beginning ofthe trace tree. to start tracing, it must try to predict whetherit will finish thetrace. Our prediction algorithm is based on blacklisting traces that have been tried and failed. When the VM fails to finish a trace start- Trace
1 Trace
2 Trace
1 Trace
2 ing at a given point, theVM records that a failure has occurred. The Number Boolean Number Boolean VM also sets a counter so that it will not try to record a trace starting at that point until itis passed a fewmore times (32 in ourimple- mentation). This backoff counter gives temporary conditions that prevent tracing a chance to end. For example, a loop may behave Number Number Boolean Number differently during startup than during its steady-state execution. Af- ter a given number of failures (2in our implementation), theVM Closed Linked Linked Linked (a) (b) marks the fragment as blacklisted, which means the VM will never again start recording atthat point. Trace
1 Trace
2 Trace
3 After implementing this basic strategy, we observed that for small loops that get blacklisted, thesystem canspend a noticeable Number Boolean String amount of time just finding the loop fragment and determining that it has been blacklisted. Wenow avoid that problem bypatching the bytecode. We define an extra no-op bytecode that indicates a loop Number String String header. The VM calls into the trace monitor every time the inter- String preter executes a loop header no-op. To blacklist a fragment, we Linked Linked ClosedLinked simply replace the loop header no-op with aregular no-op. Thus, (c) the interpreter will never again even callinto the trace monitor. There is a related problem we have not yetsolved, which occurs when a loop meets all of these conditions: Figure 6. We handle type-unstable loops by allowing traces to compile that cannot loop back to themselves due to a type mis- • The VM can form at least one root trace for theloop. match. As such traces accumulate, we attempt to connect their loop • There is at least one hot side exit for which the VM cannot edges to form groups of trace trees thatcan execute without having complete a trace. to side-exit to the interpreter to cover odd type cases.This is par- • The loop body is short. ticularly important for nested trace treeswhere an outertree tries to call an inner tree (orin this casea forest of inner trees), since inner In this case, the VM will repeatedly passthe loopheader, search loops frequently have initially undefined values which change type for a trace, find it, execute it, and fall back tothe interpreter. to a concrete value after thefirst iteration. With a short loop body, the overhead of finding and calling the trace is high, and causes performance to be even slower than the basic interpreter. So far, inthis situation we have improved the through the inner loop, {i2, i3, i5,α}. The αsymbol is used to implementation so that the VM can complete the branch trace. indicate that the trace loops back the tree anchor. But it is hard to guarantee that this situation willnever happen. When execution leaves the inner loop, the basic design has two As future work, this situation could be avoided by detecting and choices. First, the system canstop tracing and give up on compiling blacklisting loops for which the average trace call executes few the outer loop, clearly anundesirable solution. The other choice is bytecodes before returning to the interpreter. to continue tracing, compiling traces forthe outer loop inside the inner loop’s trace tree. 4. Nested Trace Tree Formation For example, the program might exit at i5 and record a branch trace that incorporates the outer loop: {i5, i7, i1,i6, i7, i1, α}. Figure 7 shows basic trace tree compilation (11)applied to a nested Later, the program might take the other branch at i2 and then loop where the inner loop contains two paths. Usually, the inner exit, recording another branch trace incorporating theouter loop: loop (with header at i2) becomes hot first, anda trace tree is rooted {i2, i4,i5, i7, i1, i6,i7, i1, α}. Thus,the outer loopis recorded and at that point. For example, the first recorded trace maybe a cycle compiled twice, and both copies must beretained in the tracecache. i Outer
Tree1t1 i1 t1 Nested
Tree Tree
Call i2 i2 t2 Nested
Tree i3 i t26i3i4 Exit
Guard i4 t4 i5 i5 i Exit
Guard7 i6 (a) (b) Figure 8. Control flow graph of a loop with two nested loops (left) and its nested trace tree configuration (right). The outertree calls Figure 7. Control flow graph of a nested loop with anif statement the two inner nested trace trees andplaces guards at theirside exit inside the inner most loop (a). An inner tree captures the inner locations. loop, and is nested inside anouter tree which “calls” the inner tree. The inner tree returns to the outer tree once it exits along its loop condition guard (b). loop is entered with mdifferent type maps (on geometric average), then we compile O(m k) copies of the innermost loop. As long as In general, if loops are nested to depthk, and each loop has n paths mis close to1, theresulting trace treeswill be tractable. (on geometric average), this naıve strategy yields O(nk) traces, An important detail isthat thecall to the innertrace tree must act which can easily fill the trace cache. like a function call site: it must returnto the same point every time. In order to execute programs with nested loops efficiently, a The goal of nesting is to make inner and outer loops independent; tracing system needs atechnique for covering thenested loops with thus when the inner tree is called, it must exitto thesame point native code without exponential trace duplication. in the outer tree every time with the same type map. Because we cannot actually guarantee this property, wemust guard onit after 4.1 Nesting Algorithm the call, and side exit ifthe property does not hold. A common reason for the inner tree not to return tothe same point would The key insight is that ifeach loop is represented by its own trace be if the inner tree took a new side exitfor which it hadnever tree, the code for each loop can becontained only inits own tree, compiled a trace. At this point, the interpreter PC is inthe inner and outer loop paths will not beduplicated. Another keyfact is that tree, sowe cannot continue recording or executing the outer tree. we are not tracing arbitrary bytecodes thatmight have irreduceable If this happens during recording, weabort theouter trace, to give control flow graphs, but rather bytecodes produced by acompiler the inner tree achance to finish growing. A future execution of the for a language with structured control flow. Thus, given two loop outer tree would then be able toproperly finish andrecord a callto edges, the system can easily determine whether they are nested the inner tree. Ifan inner treeside exit happens duringexecution of and which is the inner loop. Using this knowledge, thesystem can a compiled trace for the outer tree, wesimply exit theouter trace compile inner and outer loops separately, andmake theouter loop’s and start recording anew branch in the inner tree. traces call the inner loop’s trace tree. The algorithm for building nested trace trees is as follows. We start tracing at loop headers exactly as in the basic tracingsystem. 4.2 Blacklisting with Nesting When we exit a loop (detected by comparing the interpreter PC The blacklisting algorithm needs modification to work well with with the range given by the loop edge), we stop the trace. The nesting. The problem is that outer loop traces often abort during key step of the algorithm occurs when we are recording a trace startup (because the inner tree is not available or takes aside exit), for loop LR (R for loop being recorded) and we reach the header which would lead to their being quickly blacklisted bythe basic of a different loop LO (O for other loop). Note that LO mustbe an algorithm. inner loop of LR because we stop the trace when we exit a loop. The key observation is that when an outer trace aborts because • the inner tree is not ready, thisis probably a temporary condition. If LO has a type-matching compiled trace tree, we call LO as Thus, we should not count such aborts toward blacklisting as long a nested trace tree. Ifthe call succeeds, thenwe record the call as we are able to build up moretraces for the inner tree. in the trace for LR. On future executions, the tracefor LR will In our implementation, when an outer tree aborts onthe inner call the inner trace directly. tree, we increment the outer tree’s blacklist counter as usualand • If LO does not have a type-matching compiled trace tree yet, back off on compiling it. When the inner tree finishes a trace, we we have to obtain it before we are able to proceed. In order decrement the blacklist counter on the outer loop, “forgiving” the to do this, we simply abort recording the first trace. The trace outer loop for aborting previously. We also undo the backoff so that monitor will see the inner loop header, and will immediately the outer tree can start immediately trying to compile the next time start recording the inner loop. 2 we reach it. If all the loops in a nestare type-stable, then loop nesting creates no duplication. Otherwise, ifloops arenested to adepth k, and each 5. Trace Tree Optimization 2Instead of aborting theouter recording, we could principally merely sus- This sectionexplains how arecorded traceis translated to an pend the recording, but thatwould require the implementation to be able optimized machine codetrace. The tracecompilation subsystem, to record several traces simultaneously, complicating the implementation, NANOJIT, is separate from the VM and can be usedfor other while saving only a fewiterations in the interpreter. applications. 5.1 Optimizations Tag JS Type Description Because traces are in SSA form and have no join points or φ- xx1 number 31-bit integer representation nodes, certain optimizations are easy to implement. In order to 000 object pointer to JSObject handle get good startup performance, the optimizations must run quickly, 010 number pointer to double handle so we chose a small set of optimizations. We implemented the 100 string pointer to JSString handle optimizations as pipelined filters sothat they canbe turned on and 110 boolean enumeration for null, undefined, true, false off independently, and yet all run in justtwo loop passes overthe null, or trace: one forward and one backward. undefined Every time the trace recorder emits aLIR instruction, the in- Figure 9. Tagged values in the SpiderMonkey JS interpreter. struction is immediately passed to the first filter inthe forward Testing tags, unboxing (extracting theuntagged value) andboxing pipeline. Thus, forward filter optimizations are performed asthe (creating tagged values) are significant costs. Avoiding thesecosts trace is recorded. Each filter may pass each instruction to the next is a key benefit of tracing. filter unchanged, write a different instruction to the next filter,or write no instruction at all. Forexample, theconstant folding filter can replace a multiply instruction like v13:= mul3, 1000 with a constant instruction v13 =3000. heuristic selects vwith minimum vm. The motivation is that this We currently apply four forward filters: frees up a register foras long as possible givena single spill. If we need to spill a value vs at this point, wegenerate the • On ISAs without floating-point instructions, a soft-float filter restore code just after the code for the current instruction. The converts floating-point LIR instructions tosequences ofinteger corresponding spill code isgenerated just after the last point where instructions. vs was used. The register that was assigned to vs ismarked free for • CSE (constant subexpression elimination), the preceding code, because that register can now beused freely • expression simplification, including constant folding anda few without affecting the following code algebraic identities (e.g., a −a= 0), and • source language semantic-specific expression simplification, 6. Implementation primarily algebraic identities thatallow DOUBLE tobe replaced To demonstrate the effectiveness of our approach, we have im- with INT. For example, LIR that converts an INT toa DOUBLE plemented a trace-based dynamic compiler for the SpiderMonkey and then back again would be removed by this filter. JavaScript Virtual Machine (4). SpiderMonkey is the JavaScript VM embedded in Mozilla’s Firefox open-source web browser (2), When trace recording is completed, nanojit runs the backward which is used by more than 200 million users world-wide. Thecore optimization filters. These are used for optimizations thatrequire of SpiderMonkey is a bytecode interpreter implemented inC++. backward program analysis. When running the backward filters, In SpiderMonkey, all JavaScript values are represented bythe nanojit reads one LIR instruction at atime, and the readsare passed type jsval. A jsval is machine word in which up tothe 3 ofthe through the pipeline. least significant bits area type tag,and the remaining bits are data. We currently apply three backward filters: See Figure 6 for details. Allpointers contained in jsvals point to • Dead data-stack store elimination. The LIR trace encodes many GC-controlled blocks aligned on 8-byte boundaries. stores to locations in the interpreter stack. But these values are JavaScript object values aremappings ofstring-valued property never read back before exiting the trace (by the interpreter or names to arbitrary values. They arerepresented in one of two ways another trace). Thus, stores to the stack that are overwritten in SpiderMonkey. Most objects are represented by ashared struc- before the next exit are dead. Stores tolocations that areoff tural description, called the object shape, that maps property names the top of the interpreter stack at future exits are alsodead. to array indexes using ahash table. The object stores a pointer to the shape and the array of its own property values. Objects with • Dead call-stack store elimination. This is the same optimization large, unique sets of property names storetheir properties directly as above, except applied to the interpreter’s call stack used for ina hash table. function call inlining. The garbage collector is an exact, non-generational, stop-the- • Dead code elimination. This eliminates any operation that world mark-and-sweep collector. stores to a value that is never used. In the rest ofthis section we discuss key areasof the TraceMon- key implementation. After a LIR instruction is successfully read (“pulled”) from the backward filter pipeline, nanojit’s code generator emits native 6.1 Calling Compiled Traces machine instruction(s) for it. Compiled traces are stored in atrace cache, indexed byintepreter PC and type map. Traces are compiled so that they may be 5.2 Register Allocation called as functions using standard native calling conventions (e.g., We use a simple greedy register allocator that makes a single FASTCALL on x86). backward pass over the trace (it is integrated with thecode gen- The interpreter must hit aloop edge and enter the monitor in erator). By the time the allocator has reached aninstruction like order to call anative trace forthe firsttime. The monitor computes v3 = add v1 , v2, it has already assigned a register to v3.If v1 and the current type map, checks thetrace cache fora trace forthe v2 have not yet been assigned registers, the allocator assigns a free current PC andtype map, andif it findsone, executes the trace. register to each. Ifthere areno free registers, a valueisselected for To execute a trace, the monitor must build atrace activation spilling. We use a class heuristic thatselects the “oldest” register- record containing imported local and global variables, temporary carried value (6). stack space, and space for arguments tonative calls. The localand The heuristic considers the set R of values v inregisters imme- global values are then copied from theinterpreter stateto the trace diately after the current instruction for spilling. Let vmbe the last activation record. Then,the trace is called like a normal Cfunction instruction before the current where each v isreferred to. Then the pointer. When a trace call returns, the monitor restores theinterpreter Recording is activated by a pointer swap that sets the inter- state. First, the monitor checks the reason forthe trace exit and preter’s dispatch table tocall a single “interrupt” routine for ev- applies blacklisting if needed. Then, it pops or synthesizes inter- ery bytecode. The interrupt routine firstcalls a bytecode-specific preter JavaScript call stack frames as needed. Finally, it copies therecording routine. Then, it turnsoff recording if necessary (e.g., imported variables back from the trace activation record to the in- the trace ended). Finally, it jumpsto the standard interpreter byte- terpreter state. code implementation. Some bytecodes have effects onthe type map At least in the current implementation, these steps havea non- that cannot be predicted before executing the bytecode (e.g., call- negligible runtime cost, so minimizing the number of interpreter- ing String.charCodeAt, which returns an integer or NaN if the to-trace and trace-to-interpreter transitions is essential for perfor- index argument is out ofrange). For these, we arrange for the inter- mance. (see also Section 3.3). Our experiments (see Figure 12) preter to call into the recorder again afterexecuting the bytecode. show that for programs we can trace well such transitions hap- Since such hooks are relatively rare, weembed them directly into pen infrequently and hence do not contribute significantly to total the interpreter, with an additional runtime check to see whether a runtime. In a few programs, where the system is prevented from recorder is currently active. recording branch traces for hot side exits byaborts, thiscost can While separating the interpreter from therecorder reduces indi- rise to up to 10% of total execution time. vidual code complexity, italso requires careful implementation and extensive testing to achieve semantic equivalence. 6.2 Trace Stitching In some cases achieving this equivalence isdifficult since Spi- Transitions from a trace to abranch trace ata side exit avoid the derMonkey follows a fat-bytecode design, which was found to be costs of calling traces from the monitor, in a feature called trace beneficial topure interpreter performance. stitching. At a side exit, theexiting trace onlyneeds to write live In fat-bytecode designs, individual bytecodes can implement register-carried values back to its traceactivation record.In our im-complex processing (e.g., thegetprop bytecode, which imple- plementation, identical type maps yield identical activation record ments full JavaScript property valueaccess, including specialcases layouts, so the trace activation record canbe reused immediately for cached and dense array access). by the branch trace. Fat bytecodes have two advantages: fewer bytecodes means In programs with branchy trace trees with small traces, trace lower dispatch cost, and bigger bytecode implementations give the stitching has a noticeable cost. Although writing to memory and compiler more opportunities to optimize the interpreter. then soon reading back would be expected to have a high L1 Fat bytecodes are a problem for TraceMonkey because they cache hit rate, for small traces theincreased instruction counthas require the recorder to reimplement the same special case logic a noticeable cost. Also, if the writes and reads are very close in the same way. Also, the advantages are reduced because (a) in the dynamic instruction stream, we have found that current dispatch costs are eliminated entirely incompiled traces, (b)the x86 processors often incur penalties of 6cycles or more (e.g., if traces contain only one special case, not the interpreter’s large the instructions use different base registers with equalvalues, the chunk of code, and (c) TraceMonkey spends less time running the processor may not be able to detect that the addresses are the same base interpreter. right away). One way we have mitigated these problems is by implementing The alternate solution is torecompile an entire trace tree,thus certain complex bytecodes in the recorder as sequences of simple achieving inter-trace register allocation (10). The disadvantage is bytecodes. Expressing theoriginal semantics this way isnot too dif- that tree recompilation takes time quadratic in thenumber of traces. ficult, andrecording simple bytecodes is mucheasier. This enables We believe that the cost of recompiling a trace tree every time us to retain the advantages of fat bytecodes whileavoiding someof a branch is added would be prohibitive. That problem might be their problems for trace recording. This is particularly effective for mitigated by recompiling only at certain points, oronly for very fat bytecodes that recurse back into theinterpreter, for example to hot, stable trees. convert an object into aprimitive value byinvoking a well-known In the future, multicore hardware is expected tobe common, method on the object, since itlets us inline this function call. making background tree recompilation attractive. Ina closely re- It is important tonote that wesplit fatopcodes into thinner op- lated project (13) background recompilation yielded speedups of codes only during recording. When running purely interpretatively up to 1.25x on benchmarks with many branch traces. We plan to (i.e. code that has been blacklisted), the interpreter directly and ef- apply this technique to TraceMonkey as future work. ficiently executes the fat opcodes. 6.3 Trace Recording The job of the trace recorder is to emit LIR with identical semantics 6.4 Preemption to the currently running interpreter bytecode trace. A goodimple- SpiderMonkey, like many VMs, needs to preempt the user program mentation should have low impact on non-tracing interpreter per- periodically. The main reasons are to prevent infinitely looping formance and a convenient way for implementers to maintain se- scripts from locking up the host system andto schedule GC. mantic equivalence. In the interpreter, this hadbeen implemented bysetting a “pre- In our implementation, the only direct modification to the inter- empt now” flag that was checked on every backward jump. This preter is acall tothe trace monitor at loopedges. In our benchmark strategy carried over into TraceMonkey: theVM inserts a guard on results (see Figure 12) the total time spent in the monitor (for all the preemption flag atevery loop edge. Wemeasured less than a activities) is usually less than 5%,so we consider theinterpreter 1% increase in runtime on most benchmarks for this extra guard. impact requirement met. Incrementing the loop hit counter isex- In practice, the cost is detectable only for programs with very short pensive because it requires usto look up the loopin the trace cache, loops. but we have tuned our loops to become hot and trace very quickly We tested and rejected a solution that avoided the guards by (on the second iteration). The hitcounter implementation could be compiling the loop edge as an unconditional jump, and patching improved, which might give us a small increase in overall perfor- the jump target to an exit routine when preemption is required. mance, as well as more flexibility with tuning hotness thresholds. This solution can make the normal case slightly faster, but then Once a loop is blacklisted we never call into the tracemonitor for preemption becomes very slow. The implementation was also very that loop (see Section 3.3). complex, especially trying torestart execution afterthe preemption. 6.5 Calling External Functions ?>9@AJ.D2.@A:0>#3$4,56# Like most interpreters, SpiderMonkey has aforeign function inter- ?>9@AJ.0A:9@AJ.>9@AJ.B<#3$4(56# (e.g., web browser control and DOM access). The FFI has astan- ?>9@AJ.1;.?:2/>9;.:<9I;./89-@/#3'4,56# FFI interact with the program state through an interpreter API (e.g., -<>2.B897<>.5:<91#3$4!56# to read a property from an argument). There are also certain inter- -<>2.B897<>.>8H2#3$4$56# /9=:>8.?;<$#3(4,56# preter builtins that donot usethe FFI, but interact with the program /9=:>8.7-(#3%4&56# state in the same way, such as the CallIteratorNext function /9=:>8.<2?#3$4)56# /8A>98FG8E.92/09?@D2#3$4!56# used with iterator objects. TraceMonkey must support this FFI in 1@>8:?.A?@2D2.1@>?#3%4*56# order to speed up code that interacts withthe host system insidehot 1@>8:?.1@>E@?2.8:?.1@>?.@A.1=>2#3+4*56# loops. 1@>8:?.&1@>.1@>?.@A.1=>2#3%(4(56# 922?#3!4,56#ing.Inparticular,externalfunctionsmayneedthe global variables, but they may beout ofdate. &-.789:;#3%4,56# &-./012#3%4%56#Fortheout-of-datecallstackproblem,werefactoredsomeo the interpreter API implementation functions tore-materialize the !"# $!"# %!"# &!"# '!"# (!"# )!"# *!"#+!"# ,!"# $!!"# interpreter call stack ondemand. KA>29:92># L?J+B =<6>?J+-?7:,A+,5*/#0(1$23# mance. =<6>?J+<:J,F5-*#0(1(23# Call threading, also known as context threading (8), compiles =<6>?J+@: =<6>?J+.:=/&%#0$1C23# methods by generating a native call instruction toan interpreter 6/J/27+*?:#0%1$23# method for each interpreter bytecode. Acall-return pair hasbeen4:<8+=7/,<6 4:<8+7:6I:F+=-4=#0C1923# shown to be a potentially much more efficient dispatch mechanism 4:<8+,56*>,#0%1923# than the indirect jumps used instandard bytecode interpreters.*:B/#0(1!23# dispatch overhead. .><57=+?=>/B/+.><=#0$1D23# .><57=+.>=/+:?*#0$C1$23# Neither call threading nor inline threading perform type special- .><57 :,,/==+?=>/B/#0)1!23# Apple’s SquirrelFish Extreme (5) is aJavaScript implementa- :,,/==+?.5*;#0%1$23# :,,/==+@:??A-,8#0$1$23# tion based on call threading with selective inline threading. Com- :,,/==+.>?:6;+<6//=#0!1923# bined with efficient interpreter engineering, these threading tech- )*+6:;< )*+45678#0$1923# niques have given SFX excellent performance on the standard Sun- )*+,-./#0$1$23# Spider benchmarks. !"# $!"# %!"# &!"# '!"# (!!"# Google’s V8 is a JavaScript implementation primarily based on inline threading, with call threading only for very complex K?<56# M/,56*# N547>F/# N:FF#O6:,/# M-?#O6:,/# operations. 9. Conclusions Figure 12. Fraction of time spent on major VM activities. The speedup vs. interpreter is shown in parentheses next to each test. This paper described how to run dynamic languages efficiently by Most programs where the VM spends the majority of its time run- recording hot traces and generating type-specialized native code. ning native code have a good speedup. Recording and compilation Our technique focuses on aggressively inlined loops, andfor each costs can be substantial; speeding upthose parts of the implemen- loop, it generates a tree of native code traces representing the tation would improve SunSpider performance. paths and value types through the loop observed at run time. We explained how to identify loop nesting relationships andgenerate nested traces in order to avoid excessive code duplication due to the many paths through a loop nest. We described our type specialization algorithm. We also described our trace compiler, inner loops become hot first), leading tomuch greater tailduplica- which translates a trace from an intermediate representation to tion. optimized native code in two linear passes. YETI, from Zaleski et al. (19) applied Dynamo-style tracing Our experimental results show that in practice loops typically to Java in order to achieve inlining, indirect jump elimination, are entered with only a few different combinations of value types and other optimizations. Their primary focus was ondesigning an of variables. Thus, asmall number of traces per loop is sufficient interpreter that could easily be gradually re-engineered as a tracing to runa program efficiently. Ourexperiments also show that on VM. programs amenable to tracing, we achieve speedups of2x to20x. Suganuma et al. (18) described region-based compilation (RBC), a relative of tracing. A region is an subprogram worth optimizing 10. Future Work that can include subsets ofany number of methods. Thus, thecom- piler has more flexibility and can potentially generate better code, Work is underway in a number of areas to further improve the but the profiling and compilation systems arecorrespondingly more performance of our trace-based JavaScript compiler. Wecurrently complex. do not trace across recursive function calls, butplan toadd the Type specialization for dynamic languages. Dynamic lan- support for this capability in thenear term. We arealso exploring guage implementors have long recognized the importance of type adoption of the existing work on tree recompilation in the context specialization for performance. Most previous work hasfocused on of the presented dynamic compiler in order tominimize JIT pause methods instead of traces. times and obtain the best ofboth worlds, fast treestitching as well Chambers et. al (9) pioneered the idea of compiling multiple as the improved code quality due totree recompilation. versions of a procedure specialized for the input types in the lan- We also plan on adding support for tracing across regular ex- guage Self. In one implementation, they generated a specialized pression substitutions using lambda functions, function applica- method online each time a method was called with new input types. tions and expression evaluation using eval. All these language In another, they used an offline whole-program static analysis to constructs are currently executed via interpretation, which limits infer input types and constant receiver types at call sites. Interest- our performance for applications that usethose features. ingly, the two techniques produced nearly thesame performance. Salib (17) designed atype inference algorithm forPython based Acknowledgments on the Cartesian Product Algorithm and used the results to special- Parts of this effort havebeen sponsored by theNational Science ize on types and translate the program to C++. Foundation under grants CNS-0615443 and CNS-0627747, as well McCloskey (14) has work in progress based on a language- as by the California MICRO Program and industrial sponsor Sun independent type inference that is used to generate efficient C Microsystems under Project No. 07-127. implementations of JavaScript and Python programs. The U.S. Government is authorized to reproduce and distribute Native code generation by interpreters. The traditional inter- reprints for Governmental purposes notwithstanding any copyright preter design is a virtual machine that directly executes ASTs or annotation thereon. Any opinions, findings, and conclusions or rec- machine-code-like bytecodes. Researchers have shown how to gen- ommendations expressed here are those of the author and should not be interpreted as necessarily representing the official views, [10] A. Gal. Efficient Bytecode Verification and Compilation in a Virtual policies or endorsements, either expressed orimplied, ofthe Na- Machine Dissertation. PhD thesis, University Of California, Irvine, tional Science foundation (NSF), any other agency of the U.S. Gov- 2006. ernment, or any of the companies mentioned above. [11] A. Gal, C. W. Probst, andM. Franz. HotpathVM: An effective JIT compiler for resource-constrained devices. In Proceedings of the References International Conference onVirtual Execution Environments, pages 144–153. ACM Press, 2006. [1] LuaJIT roadmap 2008 - http://lua-users.org/lists/lua-l/2008- 02/msg00051.html. [12] C. Garrett, J. Dean, D. Grove, and C.Chambers. Measurement and Application of Dynamic Receiver Class Distributions. 1994. [2] Mozilla — Firefox web browser and Thunderbird email client - http://www.mozilla.com. [13] J. Ha, M. R.Haghighat, S. Cong, and K. S.McKinley. A concurrent trace-based just-in-time compiler for javascript. Dept.of Computer [3] SPECJVM98 - http://www.spec.org/jvm98/. Sciences, The University of Texas at Austin,TR-09-06, 2009. [4] SpiderMonkey (JavaScript-C) Engine - [14] B. McCloskey. Personal communication. http://www.mozilla.org/js/spidermonkey/. [15] I. Piumarta and F. Riccardi. Optimizing direct threaded code by selec [5] Surfin’ Safari - Blog Archive - Announcing SquirrelFish Extreme- tive inlining. In Proceedings of theACM SIGPLAN 1998conference http://webkit.org/blog/214/introducing-squirrelfish-extreme/. on Programming language design and implementation, pages 291– [6] A. Aho, R. Sethi, J.Ullman, and M.Lam. Compilers: Principles, 300. ACM New York, NY, USA, 1998. techniques, and tools, 2006. [16] A. Rigo. Representation-Based Just-In-time Specialization and the [7] V. Bala, E. Duesterwald, andS. Banerjia. Dynamo: A transparent Psyco Prototype for Python. In PEPM, 2004. dynamic optimization system. InProceedings of the ACM SIGPLAN [17] M. Salib. Starkiller: A Static Type Inferencer and Compiler for Conference on Programming Language Design and Implementation, Python. In Master’s Thesis, 2004. pages 1–12. ACM Press, 2000. [18] T. Suganuma, T. Yasue, andT. Nakatani. A Region-Based Compila-[8]M.Be International Symposium on, pages 15–26, 2005. [19] M. Zaleski, A. D. Brown, and K. Stoodley. YETI: AgraduallY Extensible Trace Interpreter. In Proceedings of the International[9]C. Conference on Programming Language Design and Implementation, pages 146–160. ACM New York, NY, USA, 1989.