Trace-basedJust-in-TimeTypeSpecializationforDynamic Languages ∗+ ∗ ∗ ∗ ∗ AndreasGal ,BrendanEich ,MikeShaver ,DavidAnderson ,DavidMandelin , $ ∗ ∗ ∗ ∗ MohammadR.Haghighat ,BlakeKaplan ,GraydonHoare ,BorisZbarsky ,JasonOrendorff , ∗ # # + +# + JesseRuderman ,EdwinSmith ,RickReitmaier ,MichaelBebenita ,MasonChang ,MichaelFranz ∗ MozillaCorporation {gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman}@mozilla.com # AdobeCorporation {edwsmith,rreitmai}@adobe.com $ IntelCorporation {mohammad.r.haghighat}@intel.com + UniversityofCalifornia,Irvine {mbebenit,changm,franz}@uci.edu Abstract and is used for the application logic of browser-based productivity applications such as Google Mail, Google Docs and Zimbra Col- Dynamic languages such as JavaScript are more difficult to com- laboration Suite. In this domain, in order to provide a fluid user pile than statically typed ones. Since no concrete type information experienceandenableanewgenerationofapplications,virtualma- isavailable,traditionalcompilersneedtoemitgenericcodethatcan chinesmustprovidealowstartuptimeandhighperformance. handleallpossibletypecombinationsatruntime.Wepresentanal- Compilers for statically typed languages rely on type informa- ternative compilation technique for dynamically-typed languages tiontogenerateefficientmachinecode.Inadynamicallytypedpro- that identifies frequently executed loop traces at run-time and then gramming language such as JavaScript, the types of expressions generates machine code on the fly that is specialized for the ac- may vary at runtime. This means that the compiler can no longer tual dynamic types occurring on each path through the loop. Our easily transform operations into machine instructions that operate methodprovidescheapinter-proceduraltypespecialization,andan on one specific type. Without exact type information, the compiler elegantandefficientwayofincrementallycompilinglazilydiscov- must emit slower generalized machine code that can deal with all ered alternative paths through nested loops. We have implemented potential type combinations. While compile-time static type infer- a dynamic compiler for JavaScript based on our technique and we ence might be able to gather type information to generate opti- have measured speedups of 10x and more for certain benchmark mized machine code, traditional static analysis is very expensive programs. andhencenotwellsuitedforthehighlyinteractiveenvironmentof Categories and Subject Descriptors D.3.4 [Programming Lan- awebbrowser. guages]:Processors— Incremental compilers, code generation. We present a trace-based compilation technique for dynamic languages that reconciles speed of compilation with excellent per- General Terms Design, Experimentation, Measurement, Perfor- formanceofthegeneratedmachinecode.Oursystemusesamixed- mance. modeexecutionapproach:thesystemstartsrunningJavaScriptina fast-starting bytecode interpreter. As the program runs, the system Keywords JavaScript,just-in-timecompilation,tracetrees. identifies hot (frequently executed) bytecode sequences, records them, and compiles them to fast native code. We call such a se- 1. Introduction quenceofinstructionsa trace. DynamiclanguagessuchasJavaScript,Python,andRuby,arepop- Unlike method-based dynamic compilers, our dynamic com- ularsincetheyareexpressive,accessibletonon-experts,andmake piler operates at the granularity of individual loops. This design deployment as easy as distributing a source file. They are used for 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 for client-side web programming expecthotloopstobemostlytype-stable ,meaningthatthetypesof valuesareinvariant.(12)Forexample,wewouldexpectloopcoun- tersthatstartasintegerstoremainintegersforalliterations.When both of these expectations hold, a trace-based compiler can cover Permission to make digital or hard copies of all or part of this work for personal or theprogramexecutionwithasmallnumberoftype-specialized,ef- classroom use is granted without fee provided that copies are not made or distributed ficientlycompiledtraces. forprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitation Each compiled trace covers one path through the program with on the first page. To copy otherwise, to republish, to post on servers or to redistribute onemappingofvaluestotypes.WhentheVMexecutesacompiled tolists,requirespriorspecificpermissionand/orafee. trace, it cannot guarantee that the same path will be followed PLDI’09, June15–20,2009,Dublin,Ireland. c Copyright 2009ACM978-1-60558-392-1/09/06...$5.00 or that the same types will occur in subsequent loop iterations. 1 for (var i = 2; i < 100; ++i) { Hence,recordingandcompilingatracespeculatesthatthepathand 2 if (!primes[i]) typingwillbeexactlyastheywereduringrecordingforsubsequent 3 continue; iterationsoftheloop. 4 for (var k = i + i; i < 100; k += i) Every compiled trace contains all the guards (checks) required 5 primes[k] = false; to validate the speculation. If one of the guards fails (if control 6 } flow is different, or a value of a different type is generated), the trace exits. If an exit becomes hot, the VM can record a branch tracestartingattheexittocoverthenewpath.Inthisway,theVM Figure 1. Sample program: sieve of Eratosthenes. primes is recordsa trace treecoveringallthehotpathsthroughtheloop. initialized to an array of 100 false values on entry to this 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 VMwoulddetectthatadifferentbranchwastaken.TheVMwould try to record a branch trace, and find that the trace reaches not the Symbol Key Interpret inner loop header, but the outer loop header. At this point, the VM Overhead Bytecodes could continue tracing until it reaches the inner loop header again, Interpreting loop thus tracing the outer loop inside a trace tree for the inner loop. edge cold/blacklisted Native loop/exit Butthisrequirestracingacopyoftheouterloopforeverysideexit and type combination in the inner loop. In essence, this is a form abort Monitor compiled trace recording ready of unintended tail duplication, which can easily overflow the code hot Record Enter cache.Alternatively,theVMcouldsimplystoptracing,andgiveup loop/exit LIR Trace Compiled Trace onevertracingouterloops. finish at We solve the nested loop problem by recording nested trace loop edge with loop header same types trees.Oursystemtracestheinnerloopexactlyasthena¨ıveversion. Compile Execute Thesystem stopsextending theinner treewhenit reachesan outer LIR Trace Compiled Trace loop, but then it starts a new trace at the outer loop header. When theouterloopreachestheinnerloopheader,thesystemtriestocall side exit, side exit to thetracetreefortheinnerloop.Ifthecallsucceeds,theVMrecords no existing trace existing trace Leave the call to the inner tree as part of the outer trace and finishes Compiled Trace the outer trace as normal. In this way, our system can trace any numberofloopsnestedtoanydepthwithoutcausingexcessivetail 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 to a new activ- cross function call boundaries, our techniques also achieve the ef- ity. In the dark box, TM executes JS as compiled traces. In the fectsofinlining.Becausetraceshavenointernalcontrol-flowjoins, lightgrayboxes,TMexecutesJSinthestandardinterpreter.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- maximizetimespentinthedarkestboxandminimizetimespentin timizations that would require interprocedural analysis in a static thewhiteboxes.Thebestcaseisaloopwherethetypesattheloop optimization setting. This makes tracing an attractive and effective edgearethesameasthetypesonentry–thenTMcanstayinnative tooltotypespecializeevencomplexfunctioncall-richcode. codeuntiltheloopisdone. WeimplementedthesetechniquesforanexistingJavaScriptin- terpreter, SpiderMonkey. We call the resulting tracing VM Trace- a set of industry benchmarks. The paper ends with conclusions in Monkey. TraceMonkey supports all the JavaScript features of Spi- Section9andanoutlookonfutureworkispresentedinSection10. derMonkey,witha2x-20xspeedupfortraceableprograms. Thispapermakesthefollowingcontributions: 2. Overview:ExampleTracingRun • Weexplainanalgorithmfordynamicallyformingtracetreesto This section provides an overview of our system by describing coveraprogram,representingnestedloopsasnestedtracetrees. how TraceMonkey executes an example program. The example • Weexplainhowtospeculativelygenerateefficienttype-specialized program,showninFigure1,computesthefirst100primenumbers codefortracesfromdynamiclanguageprograms. withnestedloops.ThenarrativeshouldbereadalongwithFigure2, • which describes the activities TraceMonkey performs and when it We validate our tracing techniques in an implementation based transitionsbetweentheloops. on the SpiderMonkey JavaScript interpreter, achieving 2x-20x TraceMonkey always begins executing a program in the byte- speedupsonmanyprograms. code interpreter. Every loop back edge is a potential trace point. Theremainderofthispaperisorganizedasfollows.Section3is When the interpreter crosses a loop edge, TraceMonkey invokes a general overview of trace tree based compilation we use to cap- the trace monitor, which may decide to record or execute a native ture and compile frequently executed code regions. In Section 4 trace.Atthestartofexecution,therearenocompiledtracesyet,so we describe our approach of covering nested loops using a num- thetracemonitorcountsthenumberoftimeseachloopbackedgeis ber of individual trace trees. In Section 5 we describe our trace- executeduntilaloopbecomeshot,currentlyafter2crossings.Note compilationbasedspeculativetypespecializationapproachweuse thatthewayourloopsarecompiled,theloopedgeiscrossedbefore 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 thefirstiteration. JavaScript is described in Section 6. Related work is discussed in Here is the sequence of events broken down by outer loop Section8.InSection7weevaluateourdynamiccompilerbasedon 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 that the interpreter would do to its data stack. Sometimesthesestorescanbeoptimizedawayasthestacklocationsareliveonlyonexitstotheinterpreter.Finally,theLIRrecordsguards andsideexitstoverifytheassumptionsmadeinthisrecording:thatprimesisanarrayandthatthecalltosetitselementsucceeds. 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 Figure4. x86snippetforsampleprogram.Thisisthex86codecompiledfromtheLIRsnippetinFigure3.MostLIRinstructionscompile to a single x86 instruction. Instructions marked with (*) would be omitted by an idealized compiler that knew that none of the side exits would ever be taken. The 17 instructions generated by the compiler compare favorably with the 100+ instructions that the interpreter would executeforthesamecodesnippet,including4indirectjumps. i=2. This is the first iteration of the outer loop. The loop on interpreter PC and the types of values match those observed when lines 4-5 becomes hot on its second iteration, so TraceMonkey en- trace recording was started. The first trace in our example, T , 45 ters recording mode on line 4. In recording mode, TraceMonkey coverslines4and5.ThistracecanbeenteredifthePCisatline4, recordsthecodealongthetraceinalow-levelcompilerintermedi- iandkareintegers,andprimesisanobject.AftercompilingT , 45 aterepresentationwecall LIR.TheLIRtraceencodesalltheoper- TraceMonkeyreturnstotheinterpreterandloopsbacktoline1. ations performed and the types of all operands. The LIR trace also i=3. Now the loop header at line 1 has become hot, so Trace- encodes guards, which are checks that verify that the control 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, if and only if all guards are passed, the ready has a compiled trace, so TraceMonkey attempts to nest the tracehastherequiredprogramsemantics. innerloopinsidethecurrenttrace.Thefirststepistocalltheinner TraceMonkey stops recording when execution returns to the traceasasubroutine.Thisexecutesthelooponline4tocompletion loop header or exits the loop. In this case, execution returns to the andthenreturnstotherecorder.TraceMonkeyverifiesthatthecall loopheaderonline4. wassuccessfulandthenrecordsthecalltotheinnertraceaspartof 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 fortheouterloop,T . 16 i=4.Onthisiteration,TraceMonkeycallsT .Becausei=4,the A trace records all its intermediate values in a small activation 16 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 originaltrace,sothiscausesT tofailaguardandtakeasideexit. imports local and global variables by unboxing them and copying 16 The exit is not yet hot, so TraceMonkey returns to the interpreter, them to its activation record. Thus, the trace can read and write whichexecutesthecontinuestatement. thesevariableswithsimpleloadsandstoresfromanativeactivation i=5.TraceMonkeycallsT ,whichinturncallsthenestedtrace recording, independently of the boxing mechanism used by the 16 T . T loops back to its own header, starting the next iteration interpreter. When the trace exits, the VM boxes the values from 45 16 withouteverreturningtothemonitor. this native storage location and copies them back to the interpreter i=6.Onthisiteration,thesideexitonline2istakenagain.This structures. time, the side exit becomes hot, so a trace T is recorded that For every control-flow branch in the source program, the 23,1 coversline3andreturnstotheloopheader.Thus,theendofT recordergeneratesconditionalexitLIRinstructions.Theseinstruc- 23,1 jumps directly to the start of T . The side exit is patched so that tions exit from the trace if required control flow is different from 16 onfutureiterations,itjumpsdirectlytoT . what it was at trace recording, ensuring that the trace instructions 23,1 Atthispoint,TraceMonkeyhascompiledenoughtracestocover are run only if they are supposed to. We call these instructions the entire nested loop structure, so the rest of the program runs guard instructions. entirelyasnativecode. Mostofourtracesrepresentloopsandendwiththespecialloop LIR instruction. This is just an unconditional branch to the top of thetrace.Suchtracesreturnonlyviaguards. 3. TraceTrees Now, we describe the key optimizations that are performed as part of recording LIR. All of these optimizations reduce complex In this section, we describe traces, trace trees, and how they are dynamic language constructs to simple typed constructs by spe- formedatruntime.Althoughourtechniquesapplytoanydynamic cializingforthecurrenttrace.Eachoptimizationrequiresguardin- language interpreter, we will describe them assuming a bytecode structions to verify their assumptions about the state and exit the interpretertokeeptheexpositionsimple. traceifnecessary. Typespecialization. 3.1 Traces 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 no type dispatches. A a loop edge and represent a single iteration through the associated typical bytecode interpreter carries tag bits along with each value, loop. andtoperformanyoperation,mustcheckthetagbits,dynamically Similar to an extended basic block, a trace 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 performtheoperation,andthenreapplytags.LIRomitseverything block, a trace can contain join nodes. Since a trace always only excepttheoperationitself. followsonesinglepaththroughtheoriginalprogram,however,join Apotentialproblemisthatsomeoperationscanproducevalues nodes are not recognizable as such in a trace and have a single of unpredictable types. For example, reading a property from an predecessornodelikeregularnodes. object could yield a value of any type, not necessarily the type A typed traceisatraceannotatedwithatypeforeveryvariable observed during recording. The recorder emits guard instructions (includingtemporaries)onthetrace.Atypedtracealsohasanentry that conditionally exit if the operation yields a 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 beforetheyaredefined.Forexample,atracecouldhaveatypemap guarantee that as long as execution is on trace, the types of values (x: int, b: boolean), meaning that the trace may be entered match those of the typed trace. When the VM observes a side exit only if the value of the variablex is of typeint and the value ofb along such a type guard, a new typed trace is recorded originating is of type boolean. The entry type map is much like the signature at the side exit location, capturing the new type of the operation in ofafunction. question. In this paper, we only discuss typed loop traces, and we will Representation specialization: objects. In JavaScript, name refer to them simply as “traces”. The key property of typed loop lookup semantics are complex and potentially expensive because traces is that they can be compiled to efficient machine code using they include features like object inheritance and eval. To evaluate thesametechniquesusedfortypedlanguages. 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 of its 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 or shared 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 foundduringsearch.TraceMonkeycansimplyobservetheresultof offset), integer operators, floating-point operators, function calls, the search process and record the simplest possible LIR to access and conditional exits. Type conversions, such as integer to double, thepropertyvalue.Forexample,thesearchmightfindsthevalueof are represented by function calls. This makes the LIR used by o.xintheprototypeofo,whichusesasharedhash-tablerepresen- TraceMonkey independent of the concrete type system and type tationthatplacesxinslot2ofapropertyvector.Thentherecorded conversion rules of the source language. The LIR operations are cangenerateLIRthatreadso.xwithjusttwoorthreeloads:oneto genericenoughthatthebackendcompilerislanguageindependent. gettheprototype,possiblyonetogetthepropertyvaluevector,and Figure3showsanexampleLIRtrace. one more to get slot 2 from the vector. This is a vast simplification Bytecode interpreters typically represent values in a various and speedup compared to the original interpreter code. Inheritance complex data structures (e.g., hash tables) in a boxed 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 code requires guard instructions that ensure efficient code that eliminates all that complexity, our traces oper- theobjectrepresentationisthesame.InTraceMonkey,objects’rep- ate on unboxed values in simple variables and arrays as much as possible. resentations are assigned an integer key called the object shape. Startingatree.Treetreesalwaysstartatloopheaders,because Thus,theguardisasimpleequalitycheckontheobjectshape. theyareanaturalplacetolookforhotpaths.InTraceMonkey,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 of 64-bit IEEE- bytecode is a loop header iff it is the target of a backward branch. 754 floating-pointer numbers (“doubles”). But many JavaScript TraceMonkey starts a tree when a given loop header has been exe- operators,inparticulararrayaccessesandbitwiseoperators,really cuted a certain number of times (2 in the current implementation). operate on integers, so they first convert the number to an integer, Starting a tree just means starting recording a trace for the current 1 pointandtypemapandmarkingthetraceastherootofatree.Each and then convert any integer result back to a double. Clearly, a treeisassociatedwithaloopheaderandtypemap,sotheremaybe JavaScript VM that wants to be fast must find a way to operate on integersdirectlyandavoidtheseconversions. severaltreesforagivenloopheader. In TraceMonkey, we support two representations for numbers: Closingtheloop.Tracerecordingcanendinseveralways. integers and doubles. The interpreter uses integer representations Ideally, the trace reaches the loop header where it started with asmuchasitcan,switchingforresultsthatcanonlyberepresented the same type map as on entry. This is called a type-stable loop as doubles. When a trace is started, some values may be imported iteration. In this case, the end of the trace can jump right to the and represented as integers. Some operations on integers require beginning, as all the value representations are exactly as needed to guards. For example, adding two integers can produce a value too enter the trace. The jump can even skip the usual code that would largefortheintegerrepresentation. copy out the state at the end of the trace and copy it back in to the Function inlining. LIR traces can cross function boundaries traceactivationrecordtoenteratrace. in either direction, achieving function inlining. Move instructions In certain cases the trace might reach the loop header with a need to be recorded for function entry and exit to copy arguments differenttypemap.Thisscenarioissometimeobservedforthefirst inandreturnvaluesout.Thesemovestatementsarethenoptimized iterationofaloop.Somevariablesinsidetheloopmightinitiallybe away by the compiler using copy propagation. In order to be able undefined,beforetheyaresettoaconcretetypeduringthefirstloop to return to the interpreter, the trace must also generate LIR to 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 to its own loop header since it is type-unstable . entry and exit LIR saves just enough information to allow the Instead, the iteration is terminated with a side exit that will always intepreter call stack to be restored later and is much simpler than fail and return to the interpreter. At the same time a new trace is recorded with the new type map. Every time an additional type- the interpreter’s standard call code. If the function being entered unstabletraceisaddedtoaregion,itsexittypemapiscomparedto is not constant (which in JavaScript includes any call by function the entry map of all existing traces in case they complement each name), the recorder must also emit LIR to guard that the function other. With this approach we are able to cover type-unstable loop isthesame. iterationsaslongtheyeventuallyformastableequilibrium. Guards and side exits. Each optimization described above Finally, the trace might exit the loop before reaching the loop requires one or more guards to verify the assumptions made in header,forexamplebecauseexecutionreachesabreakorreturn doing the optimization. A guard is just a group of LIR instructions statement. In this case, the VM simply ends the trace with an exit that performs a test and conditional exit. The exit branches to a tothetracemonitor. side exit, a small off-trace piece of LIR that returns a pointer to As mentioned previously, we may speculatively chose to rep- a structure that describes the reason for the exit along with the interpreterPCattheexitpointandanyotherdataneededtorestore resent certain Number-typed values as integers on trace. We do so theinterpreter’sstatestructures. 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 to widen the type program state in unpredictable ways, making it difficult for the ofthevariabletoadouble.Asaresult,therecordedtracebecomes tracer to know the current type map in order to continue tracing. inherently type-unstable since it starts with an integer 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 the length of traces. attraceentrywespecializedtheNumber-typedvaluetoaninteger, When any situation occurs that prevents the implementation from assumingthatattheloopedgewewouldagainfindanintegervalue continuingtracerecording,theimplementationabortstracerecord- inthevariable,allowingustoclosetheloop.Toavoidfuturespec- ingandreturnstothetracemonitor. ulative failures involving this variable, and to obtain a type-stable tracewenotethefactthatthevariableinquestionasbeenobserved to sometimes hold non-integer values in an advisory data structure 3.2 TraceTrees whichwecallthe“oracle”. Especially simple loops, namely those where control flow, value When compiling loops, we consult the oracle before specializ- types,valuerepresentations,andinlinedfunctionsareallinvariant, ing values 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 is known 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 tracefromthatpointandpatchesthesideexittojump able, we immediately trigger the recording of a new trace, which directlytothattrace.Inthisway,asingletraceexpandsondemand basedonthenowupdatedoracleinformationwillstartwithadou- toasingle-entry,multiple-exit trace tree. blevalueandthusbecometypestable. This section explains how trace trees are formed during execu- Extending a tree. Side exits lead to different paths through tion. The goal is to form trace trees during execution that cover all the loop, or paths with different types or representations. Thus, to thehotpathsoftheprogram. completelycovertheloop,theVMmustrecordtracesstartingatall side exits. These traces are recorded much like root traces: there is acounterforeachsideexit,andwhenthecounterreachesahotness 1 Arraysareactuallyworsethanthis:iftheindexvalueisanumber,itmust threshold, recording starts. Recording stops exactly as for the root beconvertedfromadoubletoastringforthepropertyaccessoperator,and trace,usingtheloopheaderoftheroottraceasthetargettoreach. thentoanintegerinternallytothearrayimplementation. Our implementation does not extend at all side exits. It extends onlyifthesideexitisforacontrol-flowbranch,andonlyiftheside T Tree
Anchor exitdoesnotleavetheloop.Inparticularwedonotwanttoextend Trunk
Trace a trace tree along a path that leads to an outer loop, because we Trace
Anchor wanttocoversuchpathsinanoutertreethroughtree nesting. Branch
Trace 3.3 Blacklisting Guard Side
Exit Sometimes, a program follows a path that cannot be compiled into a trace, usually because of limitations 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, if a 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 Figure 5. A tree with two traces, a trunk trace and one branch tracingeverytimeweobserveanexceptionbeingthrown. trace.Thetrunktracecontainsaguardtowhichabranchtracewas Asaresult,ifahotloopcontainstracesthatalwaysfail,theVM attached.Thebranchtracecontainaguardthatmayfailandtrigger could potentially run much more slowly than the base interpreter: asideexit.Boththetrunkandthebranchtraceloopbacktothetree theVMrepeatedlyspendstimetryingtorecordtraces,butisnever anchor,whichisthebeginningofthetracetree. able to run any. To avoid this problem, whenever the VM is about tostarttracing,itmusttrytopredictwhetheritwillfinishthetrace. Our prediction algorithm is based on blacklisting traces that Trace
1 Trace
2 Trace
1 Trace
2 havebeentriedandfailed.WhentheVMfailstofinishatracestart- ingatagivenpoint,theVMrecordsthatafailurehasoccurred.The Number Boolean Number Boolean VMalsosetsacountersothatitwillnottrytorecordatracestarting at that point until it is passed a few more times (32 in our imple- mentation). This backoff counter gives temporary conditions that prevent tracing a chance to end. For example, a loop may behave Number Number Boolean Number differentlyduringstartupthanduringitssteady-stateexecution.Af- Closed Linked Linked Linked ter a given number of failures (2 in our implementation), the VM (b) (a) marksthefragmentasblacklisted,whichmeanstheVMwillnever Trace
1 Trace
2 Trace
3 againstartrecordingatthatpoint. After implementing this basic strategy, we observed that for Number Boolean String small loops that get blacklisted, the system can spend a noticeable amountoftimejustfindingtheloopfragmentanddeterminingthat ithasbeenblacklisted.Wenowavoidthatproblembypatchingthe bytecode. We define an extra no-op bytecode that indicates a loop String Number String header. The VM calls into the trace monitor every time the inter- String Linked Linked Closed preter executes a loop header no-op. To blacklist a fragment, we Linked simply replace the loop header no-op with a regular no-op. Thus, (c) theinterpreterwillneveragainevencallintothetracemonitor. Thereisarelatedproblemwehavenotyetsolved,whichoccurs Figure 6. We handle type-unstable loops by allowing traces to whenaloopmeetsalloftheseconditions: compile that cannot loop back to themselves due to a type mis- • TheVMcanformatleastoneroottracefortheloop. match.Assuchtracesaccumulate,weattempttoconnecttheirloop • There is at least one hot side exit for which the VM cannot edgestoformgroupsoftracetreesthatcanexecutewithouthaving completeatrace. to side-exit to the interpreter to cover odd type cases. This is par- ticularlyimportantfornestedtracetreeswhereanoutertreetriesto • Theloopbodyisshort. callaninnertree(orinthiscaseaforestofinnertrees),sinceinner Inthiscase,theVMwillrepeatedlypasstheloopheader,search loopsfrequentlyhaveinitiallyundefinedvalueswhichchangetype for a trace, find it, execute it, and fall back to the interpreter. toaconcretevalueafterthefirstiteration. With a short loop body, the overhead of finding and calling the trace is high, and causes performance to be even slower than the through the inner loop, {i ,i ,i ,α}. The α symbol is used to 2 3 5 basic interpreter. So far, in this situation we have improved the indicatethatthetraceloopsbackthetreeanchor. implementation so that the VM can complete the branch trace. When execution leaves the inner loop, the basic design has two But it is hard to guarantee that this situation will never happen. choices.First,thesystemcanstoptracingandgiveuponcompiling As future work, this situation could be avoided by detecting and the outer loop, clearly an undesirable solution. The other choice is blacklisting loops for which the average trace call executes few to continue tracing, compiling traces for the outer loop inside the bytecodesbeforereturningtotheinterpreter. innerloop’stracetree. For example, the program might exit at i and record a branch 5 4. NestedTraceTreeFormation trace that incorporates the outer loop: {i ,i ,i ,i ,i ,i ,α}. 5 7 1 6 7 1 Figure7showsbasictracetreecompilation(11)appliedtoanested Later, the program might take the other branch at i and then 2 loop where the inner loop contains two paths. Usually, the inner exit, recording another branch trace incorporating the outer loop: loop(withheaderati )becomeshotfirst,andatracetreeisrooted {i ,i ,i ,i ,i ,i ,i ,i ,α}.Thus,theouterloopisrecordedand 2 2 4 5 7 1 6 7 1 at that point. For example, the first recorded trace may be a cycle compiledtwice,andbothcopiesmustberetainedinthetracecache. Outer
Tree t1 i1 i1 t1 Nested
Tree Tree
Call i2 t2 i2 Nested
Tree i3 t2 i6 i3 i4 Exit
Guard i4 t4 i5 i5 Exit
Guard i7 i6 (b) (a) Figure8. Controlflowgraphofaloopwithtwonestedloops(left) and its nested trace tree configuration (right). The outer tree calls Figure7. Controlflowgraphofanestedloopwithanifstatement the two inner nested trace trees and places guards at their side exit inside the inner most loop (a). An inner tree captures the inner locations. loop,andisnestedinsideanoutertreewhich“calls”theinnertree. The inner tree returns to the outer tree once it exits along its loop conditionguard(b). loopisenteredwithmdifferenttypemaps(ongeometricaverage), k then we compileO(m ) copies of the innermost loop. As long as miscloseto1,theresultingtracetreeswillbetractable. Ingeneral,ifloopsarenestedtodepthk,andeachloophasnpaths Animportantdetailisthatthecalltotheinnertracetreemustact k (on geometric average), this na¨ıve strategy yields O(n ) traces, likeafunctioncallsite:itmustreturntothesamepointeverytime. whichcaneasilyfillthetracecache. The goal of nesting is to make inner and outer loops independent; In order to execute programs with nested loops efficiently, a thus when the inner tree is called, it must exit to the same point tracingsystemneedsatechniqueforcoveringthenestedloopswith in the outer tree every time with the same type map. Because we nativecodewithoutexponentialtraceduplication. cannot actually guarantee this property, we must guard on it after the call, and side exit if the property does not hold. A common 4.1 NestingAlgorithm reason for the inner tree not to return to the same point would The key insight is that if each loop is represented by its own trace be if the inner tree took a new side exit for which it had never tree, the code for each loop can be contained only in its own tree, compiled a trace. At this point, the interpreter PC is in the inner andouterlooppathswillnotbeduplicated.Anotherkeyfactisthat tree, so we cannot continue recording or executing the outer tree. wearenottracingarbitrarybytecodesthatmighthaveirreduceable If this happens during recording, we abort the outer trace, to give control flow graphs, but rather bytecodes produced by a compiler theinnertreeachancetofinishgrowing.Afutureexecutionofthe for a language with structured control flow. Thus, given two loop outertreewouldthenbeabletoproperlyfinishandrecordacallto edges, the system can easily determine whether they are nested theinnertree.Ifaninnertreesideexithappensduringexecutionof and which is the inner loop. Using this knowledge, the system can a compiled trace for the outer tree, we simply exit the outer trace compileinnerandouterloopsseparately,andmaketheouterloop’s andstartrecordinganewbranchintheinnertree. traces calltheinnerloop’stracetree. The algorithm for building nested trace trees is as follows. We 4.2 BlacklistingwithNesting start tracing at loop headers exactly as in the basic tracing system. The blacklisting algorithm needs modification to work well with When we exit a loop (detected by comparing the interpreter PC nesting. The problem is that outer loop traces often abort during with the range given by the loop edge), we stop the trace. The startup (because the inner tree is not available or takes a side exit), key step of the algorithm occurs when we are recording a trace which would lead to their being quickly blacklisted by the basic for loop L (R for loop being recorded) and we reach the header R algorithm. ofadifferentloopL (O forotherloop).NotethatL mustbean O O The key observation is that when an outer trace aborts because innerloopofL becausewestopthetracewhenweexitaloop. R the inner tree is not ready, this is probably a temporary condition. • If L has a type-matching compiled trace tree, we call L as O O Thus, we should not count such aborts toward blacklisting as long a nested trace tree. If the call succeeds, then we record the call asweareabletobuildupmoretracesfortheinnertree. in the trace forL . On future executions, the trace forL will R R In our implementation, when an outer tree aborts on the inner calltheinnertracedirectly. tree, we increment the outer tree’s blacklist counter as usual and • If L does not have a type-matching compiled trace tree yet, back off on compiling it. When the inner tree finishes a trace, we O 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 outerloopforabortingpreviously.Wealsoundothebackoffsothat monitor will see the inner loop header, and will immediately theoutertreecanstartimmediatelytryingtocompilethenexttime 2 startrecordingtheinnerloop. wereachit. Ifalltheloopsinanestaretype-stable,thenloopnestingcreates noduplication.Otherwise,ifloopsarenestedtoadepthk,andeach 5. TraceTreeOptimization 2 This section explains how a recorded trace is translated to an Instead of aborting the outer recording, we could principally merely sus- optimized machine code trace. The trace compilation subsystem, pend the recording, but that would require the implementation to be able NANOJIT, is separate from the VM and can be used for other to record several traces simultaneously, complicating the implementation, whilesavingonlyafewiterationsintheinterpreter. applications. Tag JSType Description 5.1 Optimizations xx1 number 31-bitintegerrepresentation Because traces are in SSA form and have no join points or φ- 000 object pointertoJSObjecthandle nodes, certain optimizations are easy to implement. In order to 010 number pointertodoublehandle get good startup performance, the optimizations must run quickly, 100 string pointertoJSStringhandle so we chose a small set of optimizations. We implemented the 110 boolean enumerationfornull,undefined,true,false optimizations as pipelined filters so that they can be turned on and null,or off independently, and yet all run in just two loop passes over the undefined trace:oneforwardandonebackward. Every time the trace recorder emits a LIR instruction, the in- Figure 9. Tagged values in the SpiderMonkey JS interpreter. struction is immediately passed to the first filter in the forward Testing tags, unboxing (extracting the untagged value) and boxing pipeline. Thus, forward filter optimizations are performed as the (creating tagged values) are significant costs. Avoiding these costs trace is recorded. Each filter may pass each instruction to the next isakeybenefitoftracing. filter unchanged, write a different instruction to the next filter, or write no instruction at all. For example, the constant folding filter can replace a multiply instruction like v := mul3,1000 with a 13 constantinstructionv = 3000. heuristic selects v with minimum v . The motivation is that this 13 m Wecurrentlyapplyfourforwardfilters: freesuparegisterforaslongaspossiblegivenasinglespill. If we need to spill a value v at this point, we generate the s • On ISAs without floating-point instructions, a soft-float filter restore code just after the code for the current instruction. The convertsfloating-pointLIRinstructionstosequencesofinteger correspondingspillcodeisgeneratedjustafterthelastpointwhere instructions. v wasused.Theregisterthatwasassignedtov ismarkedfreefor s s • the preceding code, because that register can now be used freely CSE(constantsubexpressionelimination), withoutaffectingthefollowingcode • expression simplification, including constant folding and a few algebraicidentities(e.g.,a−a = 0),and 6. Implementation • source language semantic-specific expression simplification, To demonstrate the effectiveness of our approach, we have im- primarilyalgebraicidentitiesthatallow DOUBLEtobereplaced plemented a trace-based dynamic compiler for the SpiderMonkey with INT. For example, LIR that converts an INT to a DOUBLE JavaScript Virtual Machine (4). SpiderMonkey is the JavaScript andthenbackagainwouldberemovedbythisfilter. VM embedded in Mozilla’s Firefox open-source web browser (2), When trace recording is completed, nanojit runs the backward whichisusedbymorethan200millionusersworld-wide.Thecore optimization filters. These are used for optimizations that require ofSpiderMonkeyisabytecodeinterpreterimplementedinC++. backward program analysis. When running the backward filters, In SpiderMonkey, all JavaScript values are represented by the nanojitreadsoneLIRinstructionatatime,andthereadsarepassed type jsval. A jsval is machine word in which up to the 3 of the throughthepipeline. leastsignificantbitsareatypetag,andtheremainingbitsaredata. Wecurrentlyapplythreebackwardfilters: See Figure 6 for details. All pointers contained in jsvals point to GC-controlledblocksalignedon8-byteboundaries. • Deaddata-stackstoreelimination.TheLIRtraceencodesmany JavaScriptobjectvaluesaremappingsofstring-valuedproperty stores to locations in the interpreter stack. But these values are namestoarbitraryvalues.Theyarerepresentedinoneoftwoways never read back before exiting the trace (by the interpreter or in SpiderMonkey. Most objects are represented by a shared struc- another trace). Thus, stores to the stack that are overwritten turaldescription,calledtheobjectshape,thatmapspropertynames before the next exit are dead. Stores to locations that are off to array indexes using a hash table. The object stores a pointer to thetopoftheinterpreterstackatfutureexitsarealsodead. the shape and the array of its own property values. Objects with • Deadcall-stackstoreelimination.Thisisthesameoptimization large, unique sets of property names store their properties directly as above, except applied to the interpreter’s call stack used for inahashtable. functioncallinlining. The garbage collector is an exact, non-generational, stop-the- worldmark-and-sweepcollector. • Dead code elimination. This eliminates any operation that IntherestofthissectionwediscusskeyareasoftheTraceMon- storestoavaluethatisneverused. keyimplementation. After a LIR instruction is successfully read (“pulled”) from 6.1 CallingCompiledTraces the backward filter pipeline, nanojit’s code generator emits native machineinstruction(s)forit. Compiled traces are stored in a trace cache, indexed by intepreter PC and type map. Traces are compiled so that they may be 5.2 RegisterAllocation called as functions using standard native calling conventions (e.g., We use a simple greedy register allocator that makes a single FASTCALLonx86). backward pass over the trace (it is integrated with the code gen- The interpreter must hit a loop edge and enter the monitor in erator). By the time the allocator has reached an instruction like ordertocallanativetraceforthefirsttime.Themonitorcomputes v = addv ,v , it has already assigned a register tov . Ifv and the current type map, checks the trace cache for a trace for the 3 1 2 3 1 v havenotyetbeenassignedregisters,theallocatorassignsafree currentPCandtypemap,andifitfindsone,executesthetrace. 2 registertoeach.Iftherearenofreeregisters,avalueisselectedfor To execute a trace, the monitor must build a trace activation spilling. We use a class heuristic that selects the “oldest” register- record containing imported local and global variables, temporary carriedvalue(6). stack space, and space for arguments to native calls. The local and TheheuristicconsidersthesetRofvaluesv inregistersimme- global values are then copied from the interpreter state to the trace diately after the current instruction for spilling. Letv be the last activationrecord.Then,thetraceiscalledlikeanormalCfunction m instructionbeforethecurrentwhereeachv isreferredto.Thenthe pointer. When a trace call returns, the monitor restores the interpreter Recording is activated by a pointer swap that sets the inter- state. First, the monitor checks the reason for the trace exit and preter’s dispatch table to call a single “interrupt” routine for ev- applies blacklisting if needed. Then, it pops or synthesizes inter- ery bytecode. The interrupt routine first calls a bytecode-specific preter JavaScript call stack frames as needed. Finally, it copies the recording routine. Then, it turns off recording if necessary (e.g., imported variables back from the trace activation record to the in- the trace ended). Finally, it jumps to the standard interpreter byte- terpreterstate. codeimplementation.Somebytecodeshaveeffectsonthetypemap At least in the current implementation, these steps have a 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- indexargumentisoutofrange).Forthese,wearrangefortheinter- mance. (see also Section 3.3). Our experiments (see Figure 12) preter to call into the recorder again after executing the bytecode. show that for programs we can trace well such transitions hap- Since such hooks are relatively rare, we embed 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 recorderiscurrentlyactive. recording branch traces for hot side exits by aborts, this cost can Whileseparatingtheinterpreterfromtherecorderreducesindi- risetoupto10%oftotalexecutiontime. vidualcodecomplexity,italsorequirescarefulimplementationand extensivetestingtoachievesemanticequivalence. 6.2 TraceStitching In some cases achieving this equivalence is difficult since Spi- derMonkey follows a fat-bytecode design, which was found to be Transitions from a trace to a branch trace at a side exit avoid the beneficialtopureinterpreterperformance. costs of calling traces from the monitor, in a feature called trace In fat-bytecode designs, individual bytecodes can implement stitching. At a side exit, the exiting trace only needs to write live complex processing (e.g., the getprop bytecode, which imple- register-carriedvaluesbacktoitstraceactivationrecord.Inourim- mentsfullJavaScriptpropertyvalueaccess,includingspecialcases plementation, identical type maps yield identical activation record forcachedanddensearrayaccess). layouts, so the trace activation record can be reused immediately Fat bytecodes have two advantages: fewer bytecodes means bythebranchtrace. lowerdispatchcost,andbiggerbytecodeimplementationsgivethe In programs with branchy trace trees with small traces, trace compilermoreopportunitiestooptimizetheinterpreter. stitching has a noticeable cost. Although writing to memory and Fat bytecodes are a problem for TraceMonkey because they then soon reading back would be expected to have a high L1 require the recorder to reimplement the same special case logic cache hit rate, for small traces the increased instruction count has in the same way. Also, the advantages are reduced because (a) a noticeable cost. Also, if the writes and reads are very close dispatch costs are eliminated entirely in compiled traces, (b) the in the dynamic instruction stream, we have found that current traces contain only one special case, not the interpreter’s large x86 processors often incur penalties of 6 cycles or more (e.g., if chunk of code, and (c) TraceMonkey spends less time running the the instructions use different base registers with equal values, the baseinterpreter. processormaynotbeabletodetectthattheaddressesarethesame Onewaywehavemitigatedtheseproblemsisbyimplementing rightaway). certain complex bytecodes in the recorder as sequences of simple The alternate solution is to recompile an entire trace tree, thus bytecodes.Expressingtheoriginalsemanticsthiswayisnottoodif- achieving inter-trace register allocation (10). The disadvantage is ficult,andrecordingsimplebytecodesismucheasier.Thisenables thattreerecompilationtakestimequadraticinthenumberoftraces. ustoretaintheadvantagesoffatbytecodeswhileavoidingsomeof We believe that the cost of recompiling a trace tree every time theirproblemsfortracerecording.Thisisparticularlyeffectivefor a branch is added would be prohibitive. That problem might be fat bytecodes that recurse back into the interpreter, for example to mitigated by recompiling only at certain points, or only for very convert an object into a primitive value by invoking a well-known hot,stabletrees. methodontheobject,sinceitletsusinlinethisfunctioncall. In the future, multicore hardware is expected to be common, It is important to note that we split fat opcodes into thinner op- making background tree recompilation attractive. In a closely re- codesonlyduringrecording.Whenrunningpurelyinterpretatively lated project (13) background recompilation yielded speedups of (i.e.codethathasbeenblacklisted),theinterpreter directly andef- up to 1.25x on benchmarks with many branch traces. We plan to ficientlyexecutesthefatopcodes. applythistechniquetoTraceMonkeyasfuturework. 6.3 TraceRecording 6.4 Preemption ThejobofthetracerecorderistoemitLIRwithidenticalsemantics to the currently running interpreter bytecode trace. A good imple- SpiderMonkey,likemanyVMs,needstopreempttheuserprogram 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- scriptsfromlockingupthehostsystemandtoscheduleGC. manticequivalence. In the interpreter, this had been implemented by setting a “pre- Inourimplementation,theonlydirectmodificationtotheinter- empt now” flag that was checked on every backward jump. This preterisacalltothetracemonitoratloopedges.Inourbenchmark strategycarriedoverintoTraceMonkey:theVMinsertsaguardon results (see Figure 12) the total time spent in the monitor (for all the preemption flag at every loop edge. We measured less than a activities) is usually less than 5%, so we consider the interpreter 1% increase in runtime on most benchmarks for this extra guard. impact requirement met. Incrementing the loop hit counter is ex- Inpractice,thecostisdetectableonlyforprogramswithveryshort pensivebecauseitrequiresustolookuptheloopinthetracecache, 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 hit counter 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 trace monitor for preemptionbecomesveryslow.Theimplementationwasalsovery thatloop(seeSection3.3). complex,especiallytryingtorestartexecutionafterthepreemption. 6.5 CallingExternalFunctions ?>9@AJ.D2.@A:0>#3$4,56# ?>9@AJ.0A:9@AJ.>9@AJ.B<#3$4(56# face(FFI)thatallowsittocallCbuiltinsandhostsystemfunctions ?>9@AJ.1;.?:2/>9;.:<9I;./89-@/#3'4,56# -<>2.B897<>.5:<91#3$4!56# FFIinteractwiththeprogramstatethroughaninterpreterAPI(e.g., -<>2.B897<>.>8H2#3$4$56# to read a property from an argument). There are also certain inter- /9=:>8.?;<$#3(4,56# /9=:>8.7-(#3%4&56# preterbuiltinsthatdonotusetheFFI,butinteractwiththeprogram /9=:>8.<2?#3$4)56# state in the same way, such as the CallIteratorNext function /8A>98FG8E.92/09?@D2#3$4!56# 1@>8:?.A?@2D2.1@>?#3%4*56# used with iterator objects. TraceMonkey must support this FFI in 1@>8:?.1@>E@?2.8:?.1@>?.@A.1=>2#3+4*56# 1@>8:?.&1@>.1@>?.@A.1=>2#3%(4(56# loops. 922?#3!4,56# ing. In particular, external functions may need the call stack or the &-.9<=>929:92># L?J+B:F>*:?7-<#0(1923# mance. =<6>?J+-?7:,A+,5*/#0(1$23# =<6>?J+<:J,F5-*#0(1(23# Call threading, also known as context threading (8), compiles =<6>?J+@:=<:#0(1C23# methods by generating a native call instruction to an interpreter =<6>?J+.:=/&%#0$1C23# 6/J/27+*?:#0%1$23# method for each interpreter bytecode. A call-return pair has been 4:<8+=7/,<6:F+?564#0D1(23# 4:<8+7:6I:F+=-4=#0C1923# showntobeapotentiallymuchmoreefficientdispatchmechanism 4:<8+,56*>,#0%1923# thantheindirectjumpsusedinstandardbytecodeinterpreters. *:B/#0(1!23# dispatchoverhead. .><57=+?=>/B/+.><=#0$1D23# .><57=+.>=/+:?*#0$C1$23# Neithercallthreadingnorinlinethreadingperformtypespecial- .><57=+.><=+>?+.;<57=+).><+.><=+>?+.;/B/#0)1!23# Apple’s SquirrelFish Extreme (5) is a JavaScript implementa- :,,/==+?.5*;#0%1$23# tion based on call threading with selective inline threading. Com- :,,/==+@:??A-,8#0$1$23# :,,/==+.>?:6;+<6//=#0!1923# bined with efficient interpreter engineering, these threading tech- )*+6:;<6:,/#0(1$23# niqueshavegivenSFXexcellentperformanceonthestandardSun- )*+45678#0$1923# )*+,-./#0$1$23# Spiderbenchmarks. !"# $!"# %!"# &!"# '!"# (!!"# 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 This paper described how to run dynamic languages efficiently by speedup vs. interpreter is shown in parentheses next to each test. recording hot traces and generating type-specialized native code. Most programs where the VM spends the majority of its time run- Our technique focuses on aggressively inlined loops, and for each ning native code have a good speedup. Recording and compilation loop, it generates a tree of native code traces representing the costs can be substantial; speeding up those parts of the implemen- paths and value types through the loop observed at run time. We tationwouldimproveSunSpiderperformance. explained how to identify loop nesting relationships and generate 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 to much greater tail duplica- which translates a trace from an intermediate representation to tion. optimizednativecodeintwolinearpasses. YETI, from Zaleski et al. (19) applied Dynamo-style tracing Our experimental results show that in practice loops typically are entered with only a few different combinations of value types to Java in order to achieve inlining, indirect jump elimination, of variables. Thus, a small number of traces per loop is sufficient and other optimizations. Their primary focus was on designing an to run a program efficiently. Our experiments also show that on interpreterthatcouldeasilybegraduallyre-engineeredasatracing programsamenabletotracing,weachievespeedupsof2xto20x. VM. Suganumaetal.(18)describedregion-basedcompilation(RBC), a relative of tracing. A region is an subprogram worth optimizing 10. FutureWork thatcanincludesubsetsofanynumberofmethods.Thus,thecom- Work is underway in a number of areas to further improve the piler has more flexibility and can potentially generate better code, performance of our trace-based JavaScript compiler. We currently buttheprofilingandcompilationsystemsarecorrespondinglymore do not trace across recursive function calls, but plan to add the complex. support for this capability in the near term. We are also exploring Type specialization for dynamic languages. Dynamic lan- adoption of the existing work on tree recompilation in the context guage implementors have long recognized the importance of type of the presented dynamic compiler in order to minimize JIT pause specializationforperformance.Mostpreviousworkhasfocusedon times and obtain the best of both worlds, fast tree stitching as well methodsinsteadoftraces. astheimprovedcodequalityduetotreerecompilation. Chambers et. al (9) pioneered the idea of compiling multiple We also plan on adding support for tracing across regular ex- versions of a procedure specialized for the input types in the lan- pression substitutions using lambda functions, function applica- guage Self. In one implementation, they generated a specialized tions and expression evaluation using eval. All these language methodonlineeachtimeamethodwascalledwithnewinputtypes. constructs are currently executed via interpretation, which limits In another, they used an offline whole-program static analysis to ourperformanceforapplicationsthatusethosefeatures. infer input types and constant receiver types at call sites. Interest- ingly,thetwotechniquesproducednearlythesameperformance. Acknowledgments Salib(17)designedatypeinferencealgorithmforPythonbased ontheCartesianProductAlgorithmandusedtheresultstospecial- Parts of this effort have been sponsored by the National Science izeontypesandtranslatetheprogramtoC++. FoundationundergrantsCNS-0615443andCNS-0627747,aswell 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 MicrosystemsunderProjectNo.07-127. implementationsofJavaScriptandPythonprograms. The U.S. Government is authorized to reproduce and distribute Nativecodegenerationbyinterpreters. The traditional inter- reprintsforGovernmentalpurposesnotwithstandinganycopyright preter design is a virtual machine that directly executes ASTs or annotationthereon.Anyopinions,findings,andconclusionsorrec- machine-code-likebytecodes.Researchershaveshownhowtogen- 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 Machine Dissertation. PhD thesis, University Of California, Irvine, policies or endorsements, either expressed or implied, of the Na- 2006. tionalSciencefoundation(NSF),anyotheragencyoftheU.S.Gov- ernment,oranyofthecompaniesmentionedabove. [11] A. Gal, C. W. Probst, and M. Franz. HotpathVM: An effective JIT compiler for resource-constrained devices. In Proceedings of the International Conference on Virtual Execution Environments, pages References 144–153.ACMPress,2006. [1] LuaJIT roadmap 2008 - http://lua-users.org/lists/lua-l/2008- [12] C. Garrett, J. Dean, D. Grove, and C. Chambers. Measurement and 02/msg00051.html. ApplicationofDynamicReceiverClassDistributions. 1994. [2] Mozilla — Firefox web browser and Thunderbird email client - [13] J. Ha, M. R. Haghighat, S. Cong, and K. S. McKinley. A concurrent http://www.mozilla.com. trace-based just-in-time compiler for javascript. Dept.of Computer [3] SPECJVM98-http://www.spec.org/jvm98/. Sciences,TheUniversityofTexasatAustin,TR-09-06,2009. [4] SpiderMonkey (JavaScript-C) Engine - [14] B.McCloskey. Personalcommunication. http://www.mozilla.org/js/spidermonkey/. [15] I.PiumartaandF.Riccardi. Optimizingdirectthreadedcodebyselec- [5] Surfin’ Safari - Blog Archive - Announcing SquirrelFish Extreme - tive inlining. In Proceedings of the ACM SIGPLAN 1998 conference 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.ACMNewYork,NY,USA,1998. techniques,andtools,2006. [16] A. Rigo. Representation-Based Just-In-time Specialization and the [7] V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent PsycoPrototypeforPython. In PEPM,2004. dynamic optimization system. In Proceedings 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. pages1–12.ACMPress,2000. [18] T. Suganuma, T. Yasue, and T. Nakatani. A Region-Based Compila- [8] M. Berndl, B. Vitale, M. Zaleski, and A. Brown. Context Threading: tion Technique for Dynamic Compilers. ACM Transactions on Pro- a Flexible and Efficient Dispatch Technique for Virtual Machine In- gramming Languages and Systems (TOPLAS),28(1):134–174,2006. terpreters. In Code Generation and Optimization, 2005. CGO 2005. [19] M. Zaleski, A. D. Brown, and K. Stoodley. YETI: A graduallY International Symposium on,pages15–26,2005. Extensible Trace Interpreter. In Proceedings of the International [9] C. Chambers and D. Ungar. Customization: Optimizing Compiler Conference on Virtual Execution Environments, pages 83–93. ACM Technology for SELF, a Dynamically-Typed O bject-Oriented Pro- Press,2007. gramming Language. In Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, pages146–160.ACMNewYork,NY,USA,1989.