Trace-basedJust-in-TimeTypeSpecializationforDynamic Languages AndreasGal  +
,BrendanEich 
,MikeShaver 
,DavidAnderson 
,DavidMandelin 
, MohammadR.Haghighat $
,BlakeKaplan 
,GraydonHoare 
,BorisZbarsky 
,JasonOrendorff 
, JesseRuderman 
,EdwinSmith #
,RickReitmaier #
,MichaelBebenita +
,MasonChang +# ,MichaelFranz + MozillaCorporation  f gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruderman g @mozilla.com AdobeCorporation # f edwsmith,rreitmai g @adobe.com IntelCorporation $ f mohammad.r.haghighat g @intel.com UniversityofCalifornia,Irvine + f mbebenit,changm,franz g @uci.edu Abstract
Dynamic languages such as JavaScript are more difcult to com-
pile than statically typed ones. Since no concrete type information
isavailable,traditionalcompilersneedtoemitgenericcodethatcan
handleallpossibletypecombinationsatruntime.Wepresentanal-
ternative compilation technique for dynamically-typed languages
that identies frequently executed loop traces at run-time and then
generates machine code on the y that is specialized for the ac-
tual dynamic types occurring on each path through the loop. Our
methodprovidescheapinter-proceduraltypespecialization,andan
elegantandefcientwayofincrementallycompilinglazilydiscov-
ered alternative paths through nested loops. We have implemented
a dynamic compiler for JavaScript based on our technique and we
have measured speedups of 10x and more for certain benchmark
programs.
Categories and Subject Descriptors D.3.4 [ Programming Lan- guages ]:Processors— Incrementalcompilers,codegeneration . General Terms Design, Experimentation, Measurement, Perfor- mance.
Keywords JavaScript,just-in-timecompilation,tracetrees.
1. Introduction
Dynamiclanguages suchasJavaScript,Python,andRuby,arepop- ular since they are expressive, accessible to non-experts, and make
deployment as easy as distributing a source le. They are used for
small scripts as well as for complex applications. JavaScript, for
example, is the de facto standard for client-side web programming
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
forprotorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitation
on the rst page. To copy otherwise, to republish, to post on servers or to redistribute
tolists,requirespriorspecicpermissionand/orafee.
PLDI'09, June15–20,2009,Dublin,Ireland. Copyright c 
2009ACM978-1-60558-392-1/09/06...$5.00 and is used for the application logic of browser-based productivity
applications such as Google Mail, Google Docs and Zimbra Col-
laboration Suite. In this domain, in order to provide a uid user
experienceandenableanewgenerationofapplications,virtualma-
chinesmustprovidealowstartuptimeandhighperformance.
Compilers for statically typed languages rely on type informa-
tiontogenerateefcientmachinecode.Inadynamicallytypedpro-
gramming language such as JavaScript, the types of expressions
may vary at runtime. This means that the compiler can no longer
easily transform operations into machine instructions that operate
on one specic type. Without exact type information, the compiler
must emit slower generalized machine code that can deal with all
potential type combinations. While compile-time static type infer-
ence might be able to gather type information to generate opti-
mized machine code, traditional static analysis is very expensive
and hence not well suited for the highly interactive environment of
awebbrowser.
We present a trace-based compilation technique for dynamic
languages that reconciles speed of compilation with excellent per-
formanceofthegeneratedmachinecode.Oursystemusesamixed-
modeexecutionapproach:thesystemstartsrunningJavaScriptina
fast-starting bytecode interpreter. As the program runs, the system
identies hot (frequently executed) bytecode sequences, records them, and compiles them to fast native code. We call such a se-
quenceofinstructionsa trace . Unlike method-based dynamic compilers, our dynamic com-
piler operates at the granularity of individual loops. This design
choice is based on the expectation that programs spend most of
their time in hot loops. Even in dynamically typed languages, we
expecthotloopstobemostly type-stable ,meaningthatthetypesof valuesareinvariant.(12)Forexample,wewouldexpectloopcoun-
ters that start as integers to remain integers for all iterations. When
both of these expectations hold, a trace-based compiler can cover
theprogramexecutionwithasmallnumberoftype-specialized,ef-
cientlycompiledtraces.
Each compiled trace covers one path through the program with
onemappingofvaluestotypes.WhentheVMexecutesacompiled
trace, it cannot guarantee that the same path will be followed
or that the same types will occur in subsequent loop iterations.
Hence,recordingandcompilingatrace speculates thatthepathand typingwillbeexactlyastheywereduringrecordingforsubsequent
iterationsoftheloop.
Every compiled trace contains all the guards (checks) required to validate the speculation. If one of the guards fails (if control
ow 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 trace startingattheexittocoverthenewpath.Inthisway,theVM recordsa tracetree coveringallthehotpathsthroughtheloop. Nested loops can be difcult to optimize for tracing VMs. In
a na ¨ ve implementation, inner loops would become hot rst, and
the VM would start tracing there. When the inner loop exits, the
VMwoulddetectthatadifferentbranchwastaken.TheVMwould
try to record a branch trace, and nd that the trace reaches not the
inner loop header, but the outer loop header. At this point, the VM
could continue tracing until it reaches the inner loop header again,
thus tracing the outer loop inside a trace tree for the inner loop.
Butthisrequirestracingacopyoftheouterloopforeverysideexit
and type combination in the inner loop. In essence, this is a form
of unintended tail duplication, which can easily overow the code
cache.Alternatively,theVMcouldsimplystoptracing,andgiveup
onevertracingouterloops.
We solve the nested loop problem by recording nested trace trees .Oursystemtracestheinnerloopexactlyasthena ¨ veversion. The system stops extending the inner tree when it reaches an outer
loop, but then it starts a new trace at the outer loop header. When
theouterloopreachestheinnerloopheader,thesystemtriestocall
thetracetreefortheinnerloop.Ifthecallsucceeds,theVMrecords
the call to the inner tree as part of the outer trace and nishes
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-
gram to nested, type-specialized trace trees. Because traces can
cross function call boundaries, our techniques also achieve the ef-
fectsofinlining.Becausetraceshavenointernalcontrol-owjoins,
they can be optimized in linear time by a simple compiler (10).
Thus, our tracing VM efciently performs the same kind of op-
timizations that would require interprocedural analysis in a static
optimization setting. This makes tracing an attractive and effective
tooltotypespecializeevencomplexfunctioncall-richcode.
WeimplementedthesetechniquesforanexistingJavaScriptin-
terpreter, SpiderMonkey. We call the resulting tracing VM Trace- Monkey . TraceMonkey supports all the JavaScript features of Spi- derMonkey,witha2x-20xspeedupfortraceableprograms.
Thispapermakesthefollowingcontributions:
 Weexplainanalgorithmfordynamicallyformingtracetreesto
coveraprogram,representingnestedloopsasnestedtracetrees.
 Weexplainhowtospeculativelygenerateefcienttype-specialized
codefortracesfromdynamiclanguageprograms.
 We validate our tracing techniques in an implementation based
on the SpiderMonkey JavaScript interpreter, achieving 2x-20x
speedupsonmanyprograms.
Theremainderofthispaperisorganizedasfollows.Section3is
a general overview of trace tree based compilation we use to cap-
ture and compile frequently executed code regions. In Section 4
we describe our approach of covering nested loops using a num-
ber of individual trace trees. In Section 5 we describe our trace-
compilation based speculative type specialization approach we use
to generate efcient machine code from recorded bytecode traces.
Our implementation of a dynamic type-specializing compiler for
JavaScript is described in Section 6. Related work is discussed in
Section8.InSection7weevaluateourdynamiccompilerbasedon 1 for (var i = 2; i < 100; ++i) {
2 if (!primes[i])
3 continue;
4 for (var k = i + i; i < 100; k += i)
5 primes[k] = false;
6 }
Figure 1. Sample program: sieve of Eratosthenes. primes is initialized to an array of 100 false values on entry to this code snippet.
Figure 2. State machine describing the major activities of Trace- Monkey and the conditions that cause transitions to a new activ-
ity. In the dark box, TM executes JS as compiled traces. In the
lightgrayboxes,TMexecutesJSinthestandardinterpreter.White
boxes are overhead. Thus, to maximize performance, we need to
maximizetimespentinthedarkestboxandminimizetimespentin
thewhiteboxes.Thebestcaseisaloopwherethetypesattheloop
edgearethesameasthetypesonentry–thenTMcanstayinnative
codeuntiltheloopisdone.
a set of industry benchmarks. The paper ends with conclusions in
Section9andanoutlookonfutureworkispresentedinSection10.
2. Overview:ExampleTracingRun
This section provides an overview of our system by describing
how TraceMonkey executes an example program. The example
program,showninFigure1,computestherst100primenumbers
withnestedloops.ThenarrativeshouldbereadalongwithFigure2,
which describes the activities TraceMonkey performs and when it
transitionsbetweentheloops.
TraceMonkey always begins executing a program in the byte-
code interpreter. Every loop back edge is a potential trace point.
When the interpreter crosses a loop edge, TraceMonkey invokes
the trace monitor , which may decide to record or execute a native trace.Atthestartofexecution,therearenocompiledtracesyet,so
thetracemonitorcountsthenumberoftimeseachloopbackedgeis
executeduntilaloopbecomes hot ,currentlyafter2crossings.Note thatthewayourloopsarecompiled,theloopedgeiscrossedbefore
entering the loop, so the second crossing occurs immediately after
therstiteration.
Here is the sequence of events broken down by outer loop
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.
Sometimes these stores can be optimized away as the stack locations are live only on exits to the interpreter. Finally, the LIR records guards
andsideexitstoverifytheassumptionsmadeinthisrecording:that primes isanarrayandthatthecalltosetitselementsucceeds. 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 rst iteration of the outer loop. The loop on lines 4-5 becomes hot on its second iteration, so TraceMonkey en-
ters recording mode on line 4. In recording mode, TraceMonkey
records the code along the trace in a low-level compiler intermedi-
ate representation we call LIR . The LIR trace encodes all the oper- ations performed and the types of all operands. The LIR trace also
encodes guards , which are checks that verify that the control ow and types are identical to those observed during trace recording.
Thus, on later executions, if and only if all guards are passed, the
tracehastherequiredprogramsemantics.
TraceMonkey stops recording when execution returns to the
loop header or exits the loop. In this case, execution returns to the
loopheaderonline4.
After recording is nished, TraceMonkey compiles the trace to
native code using the recorded type information for optimization.
The result is a native code fragment that can be entered if the interpreter PC and the types of values match those observed when
trace recording was started. The rst trace in our example, T 45 , coverslines4and5.ThistracecanbeenteredifthePCisatline4,
i and k areintegers,and primes isanobject.Aftercompiling T 45 , TraceMonkeyreturnstotheinterpreterandloopsbacktoline1.
i=3. Now the loop header at line 1 has become hot, so Trace- Monkey starts recording. When recording reaches line 4, Trace-
Monkey observes that it has reached an inner loop header that al-
ready has a compiled trace, so TraceMonkey attempts to nest the
inner loop inside the current trace. The rst step is to call the inner
traceasasubroutine.Thisexecutesthelooponline4tocompletion
and then returns to the recorder. TraceMonkey veries that the call
wassuccessfulandthenrecordsthecalltotheinnertraceaspartof
the current trace. Recording continues until execution reaches line
1, and at which point TraceMonkey nishes and compiles a trace
fortheouterloop, T 16 .
i=4. Onthisiteration,TraceMonkeycalls T 16 .Because i=4 ,the if statement on line 2 is taken. This branch was not taken in the
originaltrace,sothiscauses T 16 tofailaguardandtakeasideexit. The exit is not yet hot, so TraceMonkey returns to the interpreter,
whichexecutesthecontinuestatement.
i=5. TraceMonkeycalls T 16 ,whichinturncallsthenestedtrace T 45 . T 16 loops back to its own header, starting the next iteration withouteverreturningtothemonitor.
i=6. Onthisiteration,thesideexitonline2istakenagain.This time, the side exit becomes hot, so a trace T 23 ; 1 is recorded that covers line 3 and returns to the loop header. Thus, the end of T 23 ; 1 jumps directly to the start of T 16 . The side exit is patched so that onfutureiterations,itjumpsdirectlyto T 23 ; 1 . Atthispoint,TraceMonkeyhascompiledenoughtracestocover
the entire nested loop structure, so the rest of the program runs
entirelyasnativecode.
3. TraceTrees
In this section, we describe traces, trace trees, and how they are
formedatruntime.Althoughourtechniquesapplytoanydynamic
language interpreter, we will describe them assuming a bytecode
interpretertokeeptheexpositionsimple.
3.1 Traces
A trace is simply a program path, which may cross function call boundaries. TraceMonkey focuses on loop traces , that originate at a loop edge and represent a single iteration through the associated
loop.
Similar to an extended basic block, a trace is only entered at
the top, but may have many exits. In contrast to an extended basic
block, a trace can contain join nodes. Since a trace always only
followsonesinglepaththroughtheoriginalprogram,however,join
nodes are not recognizable as such in a trace and have a single
predecessornodelikeregularnodes.
A typedtrace isatraceannotatedwithatypeforeveryvariable (includingtemporaries)onthetrace.Atypedtracealsohasanentry
type map giving the required types for variables used on the trace beforetheyaredened.Forexample,atracecouldhaveatypemap
(x: int, b: boolean) , meaning that the trace may be entered only if the value of the variable x is of type int and the value of b is of type boolean . The entry type map is much like the signature ofafunction.
In this paper, we only discuss typed loop traces, and we will
refer to them simply as “traces”. The key property of typed loop
traces is that they can be compiled to efcient machine code using
thesametechniquesusedfortypedlanguages.
In TraceMonkey, traces are recorded in trace-avored SSA LIR (low-level intermediate representation). In trace-avored SSA (or
TSSA), phi nodes appear only at the entry point, which is reached
both on entry and via loop edges. The important LIR primitives
are constant values, memory loads and stores (by address and
offset), integer operators, oating-point operators, function calls,
and conditional exits. Type conversions, such as integer to double,
are represented by function calls. This makes the LIR used by
TraceMonkey independent of the concrete type system and type
conversion rules of the source language. The LIR operations are
genericenoughthatthebackendcompilerislanguageindependent.
Figure3showsanexampleLIRtrace.
Bytecode interpreters typically represent values in a various
complex data structures (e.g., hash tables) in a boxed format (i.e.,
with attached type tag bits). Since a trace is intended to represent
efcient code that eliminates all that complexity, our traces oper-
ate on unboxed values in simple variables and arrays as much as
possible. A trace records all its intermediate values in a small activation
record area. To make variable accesses fast on trace, the trace also
imports local and global variables by unboxing them and copying
them to its activation record. Thus, the trace can read and write
thesevariableswithsimpleloadsandstoresfromanativeactivation
recording, independently of the boxing mechanism used by the
interpreter. When the trace exits, the VM boxes the values from
this native storage location and copies them back to the interpreter
structures.
For every control-ow branch in the source program, the
recordergeneratesconditionalexitLIRinstructions.Theseinstruc-
tions exit from the trace if required control ow is different from
what it was at trace recording, ensuring that the trace instructions
are run only if they are supposed to. We call these instructions
guard instructions.
Mostofourtracesrepresentloopsandendwiththespecial loop LIR instruction. This is just an unconditional branch to the top of
thetrace.Suchtracesreturnonlyviaguards.
Now, we describe the key optimizations that are performed as
part of recording LIR. All of these optimizations reduce complex
dynamic language constructs to simple typed constructs by spe-
cializingforthecurrenttrace.Eachoptimizationrequiresguardin-
structions to verify their assumptions about the state and exit the
traceifnecessary.
Typespecialization.
All LIR primitives apply to operands of specic types. Thus,
LIR traces are necessarily type-specialized, and a compiler can
easily produce a translation that requires no type dispatches. A
typical bytecode interpreter carries tag bits along with each value,
andtoperformanyoperation,mustcheckthetagbits,dynamically
dispatch, mask out the tag bits to recover the untagged value,
performtheoperation,andthenreapplytags.LIRomitseverything
excepttheoperationitself.
Apotentialproblemisthatsomeoperationscanproducevalues
of unpredictable types. For example, reading a property from an
object could yield a value of any type, not necessarily the type
observed during recording. The recorder emits guard instructions
that conditionally exit if the operation yields a value of a different
type from that seen during recording. These guard instructions
guarantee that as long as execution is on trace, the types of values
match those of the typed trace. When the VM observes a side exit
along such a type guard, a new typed trace is recorded originating
at the side exit location, capturing the new type of the operation in
question.
Representation specialization: objects. In JavaScript, name lookup semantics are complex and potentially expensive because
they include features like object inheritance and eval . To evaluate an object property read expression like o.x , the interpreter must search the property map of o and all of its prototypes and parents. Property maps can be implemented with different data structures
(e.g., per-object hash tables or shared hash tables), so the search
process also must dispatch on the representation of each object
foundduringsearch.TraceMonkeycansimplyobservetheresultof
the search process and record the simplest possible LIR to access
thepropertyvalue.Forexample,thesearchmightndsthevalueof
o.x intheprototypeof o ,whichusesasharedhash-tablerepresen- tationthatplaces x inslot2ofapropertyvector.Thentherecorded cangenerateLIRthatreads o.x withjusttwoorthreeloads:oneto gettheprototype,possiblyonetogetthepropertyvaluevector,and
one more to get slot 2 from the vector. This is a vast simplication
and speedup compared to the original interpreter code. Inheritance
relationships and object representations can change during execu-
tion, so the simplied code requires guard instructions that ensure
theobjectrepresentationisthesame.InTraceMonkey,objects'rep-
resentations are assigned an integer key called the object shape . Thus,theguardisasimpleequalitycheckontheobjectshape.
Representation specialization: numbers. JavaScript has no integer type, only a Number type that is the set of 64-bit IEEE-
754 oating-pointer numbers (“doubles”). But many JavaScript
operators, in particular array accesses and bitwise operators, really
operate on integers, so they rst convert the number to an integer,
and then convert any integer result back to a double. 1
Clearly, a JavaScript VM that wants to be fast must nd a way to operate on
integersdirectlyandavoidtheseconversions.
In TraceMonkey, we support two representations for numbers:
integers and doubles. The interpreter uses integer representations
asmuchasitcan,switchingforresultsthatcanonlyberepresented
as doubles. When a trace is started, some values may be imported
and represented as integers. Some operations on integers require
guards. For example, adding two integers can produce a value too
largefortheintegerrepresentation.
Function inlining. LIR traces can cross function boundaries in either direction, achieving function inlining. Move instructions
need to be recorded for function entry and exit to copy arguments
inandreturnvaluesout.Thesemovestatementsarethenoptimized
away by the compiler using copy propagation. In order to be able
to return to the interpreter, the trace must also generate LIR to
record that a call frame has been entered and exited. The frame
entry and exit LIR saves just enough information to allow the
intepreter call stack to be restored later and is much simpler than
the interpreter's standard call code. If the function being entered
is not constant (which in JavaScript includes any call by function
name), the recorder must also emit LIR to guard that the function
isthesame.
Guards and side exits. Each optimization described above requires one or more guards to verify the assumptions made in
doing the optimization. A guard is just a group of LIR instructions
that performs a test and conditional exit. The exit branches to a
side exit , a small off-trace piece of LIR that returns a pointer to a structure that describes the reason for the exit along with the
interpreterPCattheexitpointandanyotherdataneededtorestore
theinterpreter'sstatestructures.
Aborts. Some constructs are difcult to record in LIR traces. For example, eval or calls to external functions can change the program state in unpredictable ways, making it difcult for the
tracer to know the current type map in order to continue tracing.
A tracing implementation can also have any number of other limi-
tations, e.g.,a small-memory device may limit the length of traces.
When any situation occurs that prevents the implementation from
continuingtracerecording,theimplementation aborts tracerecord- ingandreturnstothetracemonitor.
3.2 TraceTrees
Especially simple loops, namely those where control ow, value
types,valuerepresentations,andinlinedfunctionsareallinvariant,
can be represented by a single trace. But most loops have at least
some variation, and so the program will take side exits from the
main trace. When a side exit becomes hot, TraceMonkey starts a
new branch trace from that point and patches the side exit to jump directlytothattrace.Inthisway,asingletraceexpandsondemand
toasingle-entry,multiple-exit tracetree . This section explains how trace trees are formed during execu-
tion. The goal is to form trace trees during execution that cover all
thehotpathsoftheprogram.
1
Arraysareactuallyworsethanthis:iftheindexvalueisanumber,itmust
beconvertedfromadoubletoastringforthepropertyaccessoperator,and
thentoanintegerinternallytothearrayimplementation. Startingatree. Treetreesalwaysstartatloopheaders,because theyareanaturalplacetolookforhotpaths.InTraceMonkey,loop
headers are easy to detect–the bytecode compiler ensures that a
bytecode is a loop header iff it is the target of a backward branch.
TraceMonkey starts a tree when a given loop header has been exe-
cuted a certain number of times (2 in the current implementation).
Starting a tree just means starting recording a trace for the current
pointandtypemapandmarkingthetraceastherootofatree.Each
treeisassociatedwithaloopheaderandtypemap,sotheremaybe
severaltreesforagivenloopheader.
Closingtheloop. Tracerecordingcanendinseveralways. Ideally, the trace reaches the loop header where it started with
the same type map as on entry. This is called a type-stable loop iteration. In this case, the end of the trace can jump right to the
beginning, as all the value representations are exactly as needed to
enter the trace. The jump can even skip the usual code that would
copy out the state at the end of the trace and copy it back in to the
traceactivationrecordtoenteratrace.
In certain cases the trace might reach the loop header with a
differenttypemap.Thisscenarioissometimeobservedfortherst
iterationofaloop.Somevariablesinsidetheloopmightinitiallybe
undened ,beforetheyaresettoaconcretetypeduringtherstloop iteration. When recording such an iteration, the recorder cannot
link the trace back to its own loop header since it is type-unstable . Instead, the iteration is terminated with a side exit that will always
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-
unstabletraceisaddedtoaregion,itsexittypemapiscomparedto
the entry map of all existing traces in case they complement each
other. With this approach we are able to cover type-unstable loop
iterationsaslongtheyeventuallyformastableequilibrium.
Finally, the trace might exit the loop before reaching the loop
header,forexamplebecauseexecutionreachesa break or return statement. In this case, the VM simply ends the trace with an exit
tothetracemonitor.
As mentioned previously, we may speculatively chose to rep-
resent certain Number-typed values as integers on trace. We do so
when we observe that Number-typed variables contain an integer
value at trace entry. If during trace recording the variable is unex-
pectedly assigned a non-integer value, we have to widen the type
of the variable to a double. As a result, the recorded trace becomes
inherently type-unstable since it starts with an integer value but
ends with a double value. This represents a mis-speculation, since
attraceentrywespecializedtheNumber-typedvaluetoaninteger,
assumingthatattheloopedgewewouldagainndanintegervalue
in the variable, allowing us to close the loop. To avoid future spec-
ulative failures involving this variable, and to obtain a type-stable
tracewenotethefactthatthevariableinquestionasbeenobserved
to sometimes hold non-integer values in an advisory data structure
whichwecallthe“oracle”.
When compiling loops, we consult the oracle before specializ-
ing values to integers. Speculation towards integers is performed
only if no adverse information is known to the oracle about that
particular variable. Whenever we accidentally compile a loop that
is type-unstable due to mis-speculation of a Number-typed vari-
able, we immediately trigger the recording of a new trace, which
based on the now updated oracle information will start with a dou-
blevalueandthusbecometypestable.
Extending a tree. Side exits lead to different paths through the loop, or paths with different types or representations. Thus, to
completelycovertheloop,theVMmustrecordtracesstartingatall
side exits. These traces are recorded much like root traces: there is
acounterforeachsideexit,andwhenthecounterreachesahotness
threshold, recording starts. Recording stops exactly as for the root
trace,usingtheloopheaderoftheroottraceasthetargettoreach.
Our implementation does not extend at all side exits. It extends
onlyifthesideexitisforacontrol-owbranch,andonlyiftheside
exit does not leave the loop. In particular we do not want to extend
a trace tree along a path that leads to an outer loop, because we
wanttocoversuchpathsinanoutertreethroughtree nesting . 3.3 Blacklisting
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
tracingeverytimeweobserveanexceptionbeingthrown.
Asaresult,ifahotloopcontainstracesthatalwaysfail,theVM
could potentially run much more slowly than the base interpreter:
the VM repeatedly spends time trying to record traces, but is never
able to run any. To avoid this problem, whenever the VM is about
tostarttracing,itmusttrytopredictwhetheritwillnishthetrace.
Our prediction algorithm is based on blacklisting traces that havebeentriedandfailed.WhentheVMfailstonishatracestart-
ingatagivenpoint,theVMrecordsthatafailurehasoccurred.The
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
differentlyduringstartupthanduringitssteady-stateexecution.Af-
ter a given number of failures (2 in our implementation), the VM
marksthefragmentasblacklisted,whichmeanstheVMwillnever
againstartrecordingatthatpoint.
After implementing this basic strategy, we observed that for
small loops that get blacklisted, the system can spend a noticeable
amountoftimejustndingtheloopfragmentanddeterminingthat
ithasbeenblacklisted.Wenowavoidthatproblembypatchingthe
bytecode. We dene an extra no-op bytecode that indicates a loop
header. The VM calls into the trace monitor every time the inter-
preter executes a loop header no-op. To blacklist a fragment, we
simply replace the loop header no-op with a regular no-op. Thus,
theinterpreterwillneveragainevencallintothetracemonitor.
Thereisarelatedproblemwehavenotyetsolved,whichoccurs
whenaloopmeetsalloftheseconditions:
 TheVMcanformatleastoneroottracefortheloop.
 There is at least one hot side exit for which the VM cannot
completeatrace.
 Theloopbodyisshort.
Inthiscase,theVMwillrepeatedlypasstheloopheader,search
for a trace, nd it, execute it, and fall back to the interpreter.
With a short loop body, the overhead of nding and calling the
trace is high, and causes performance to be even slower than the
basic interpreter. So far, in this situation we have improved the
implementation so that the VM can complete the branch trace.
But it is hard to guarantee that this situation will never happen.
As future work, this situation could be avoided by detecting and
blacklisting loops for which the average trace call executes few
bytecodesbeforereturningtotheinterpreter.
4. NestedTraceTreeFormation
Figure7showsbasictracetreecompilation(11)appliedtoanested
loop where the inner loop contains two paths. Usually, the inner
loop(withheaderat i 2 )becomeshotrst,andatracetreeisrooted at that point. For example, the rst recorded trace may be a cycle
Figure 5. A tree with two traces, a trunk trace and one branch trace.Thetrunktracecontainsaguardtowhichabranchtracewas
attached.Thebranchtracecontainaguardthatmayfailandtrigger
asideexit.Boththetrunkandthebranchtraceloopbacktothetree
anchor,whichisthebeginningofthetracetree.
Figure 6. We handle type-unstable loops by allowing traces to compile that cannot loop back to themselves due to a type mis-
match.Assuchtracesaccumulate,weattempttoconnecttheirloop
edgestoformgroupsoftracetreesthatcanexecutewithouthaving
to side-exit to the interpreter to cover odd type cases. This is par-
ticularlyimportantfornestedtracetreeswhereanoutertreetriesto
callaninnertree(orinthiscaseaforestofinnertrees),sinceinner
loopsfrequentlyhaveinitiallyundenedvalueswhichchangetype
toaconcretevalueaftertherstiteration.
through the inner loop, f i 2 ;i 3 ;i 5 ;g . The symbol is used to indicatethatthetraceloopsbackthetreeanchor.
When execution leaves the inner loop, the basic design has two
choices.First,thesystemcanstoptracingandgiveuponcompiling
the outer loop, clearly an undesirable solution. The other choice is
to continue tracing, compiling traces for the outer loop inside the
innerloop'stracetree.
For example, the program might exit at i 5 and record a branch trace that incorporates the outer loop: f i 5 ;i 7 ;i 1 ;i 6 ;i 7 ;i 1 ;g . Later, the program might take the other branch at i 2 and then exit, recording another branch trace incorporating the outer loop:
f i 2 ;i 4 ;i 5 ;i 7 ;i 1 ;i 6 ;i 7 ;i 1 ;g .Thus,theouterloopisrecordedand compiledtwice,andbothcopiesmustberetainedinthetracecache.
Figure7. Controlowgraphofanestedloopwithanifstatement inside the inner most loop (a). An inner tree captures the inner
loop,andisnestedinsideanoutertreewhich“calls”theinnertree.
The inner tree returns to the outer tree once it exits along its loop
conditionguard(b).
Ingeneral,ifloopsarenestedtodepth k ,andeachloophas n paths (on geometric average), this na ¨ ve strategy yields O ( n k
) traces, whichcaneasilyllthetracecache.
In order to execute programs with nested loops efciently, a
tracingsystemneedsatechniqueforcoveringthenestedloopswith
nativecodewithoutexponentialtraceduplication.
4.1 NestingAlgorithm
The key insight is that if each loop is represented by its own trace
tree, the code for each loop can be contained only in its own tree,
andouterlooppathswillnotbeduplicated.Anotherkeyfactisthat
wearenottracingarbitrarybytecodesthatmighthaveirreduceable
control ow graphs, but rather bytecodes produced by a compiler
for a language with structured control ow. Thus, given two loop
edges, the system can easily determine whether they are nested
and which is the inner loop. Using this knowledge, the system can
compileinnerandouterloopsseparately,andmaketheouterloop's
traces call theinnerloop'stracetree. The algorithm for building nested trace trees is as follows. We
start tracing at loop headers exactly as in the basic tracing system.
When we exit a loop (detected by comparing the interpreter PC
with the range given by the loop edge), we stop the trace. The
key step of the algorithm occurs when we are recording a trace
for loop L R ( R for loop being recorded) and we reach the header ofadifferentloop L O ( O forotherloop).Notethat L O mustbean innerloopof L R becausewestopthetracewhenweexitaloop.  If L O has a type-matching compiled trace tree, we call L O as a nested trace tree. If the call succeeds, then we record the call
in the trace for L R . On future executions, the trace for L R will calltheinnertracedirectly.
 If L O does not have a type-matching compiled trace tree yet, we have to obtain it before we are able to proceed. In order
to do this, we simply abort recording the rst trace. The trace
monitor will see the inner loop header, and will immediately
startrecordingtheinnerloop. 2 Ifalltheloopsinanestaretype-stable,thenloopnestingcreates
noduplication.Otherwise,ifloopsarenestedtoadepth k ,andeach
2
Instead of aborting the outer recording, we could principally merely sus-
pend the recording, but that would require the implementation to be able
to record several traces simultaneously, complicating the implementation,
whilesavingonlyafewiterationsintheinterpreter.
Figure8. Controlowgraphofaloopwithtwonestedloops(left) and its nested trace tree conguration (right). The outer tree calls
the two inner nested trace trees and places guards at their side exit
locations.
loopisenteredwith m differenttypemaps(ongeometricaverage), then we compile O ( m k
) copies of the innermost loop. As long as m iscloseto1,theresultingtracetreeswillbetractable.
Animportantdetailisthatthecalltotheinnertracetreemustact
likeafunctioncallsite:itmustreturntothesamepointeverytime.
The goal of nesting is to make inner and outer loops independent;
thus when the inner tree is called, it must exit to the same point
in the outer tree every time with the same type map. Because we
cannot actually guarantee this property, we must guard on it after
the call, and side exit if the property does not hold. A common
reason for the inner tree not to return to the same point would
be if the inner tree took a new side exit for which it had never
compiled a trace. At this point, the interpreter PC is in the inner
tree, so we cannot continue recording or executing the outer tree.
If this happens during recording, we abort the outer trace, to give
the inner tree a chance to nish growing. A future execution of the
outertreewouldthenbeabletoproperlynishandrecordacallto
theinnertree.Ifaninnertreesideexithappensduringexecutionof
a compiled trace for the outer tree, we simply exit the outer trace
andstartrecordinganewbranchintheinnertree.
4.2 BlacklistingwithNesting
The blacklisting algorithm needs modication to work well with
nesting. The problem is that outer loop traces often abort during
startup (because the inner tree is not available or takes a side exit),
which would lead to their being quickly blacklisted by the basic
algorithm.
The key observation is that when an outer trace aborts because
the inner tree is not ready, this is probably a temporary condition.
Thus, we should not count such aborts toward blacklisting as long
asweareabletobuildupmoretracesfortheinnertree.
In our implementation, when an outer tree aborts on the inner
tree, we increment the outer tree's blacklist counter as usual and
back off on compiling it. When the inner tree nishes a trace, we
decrement the blacklist counter on the outer loop, “forgiving” the
outerloopforabortingpreviously.Wealsoundothebackoffsothat
theoutertreecanstartimmediatelytryingtocompilethenexttime
wereachit.
5. TraceTreeOptimization
This section explains how a recorded trace is translated to an
optimized machine code trace. The trace compilation subsystem,
NANOJIT , is separate from the VM and can be used for other applications.
5.1 Optimizations
Because traces are in SSA form and have no join points or  - nodes, certain optimizations are easy to implement. In order to
get good startup performance, the optimizations must run quickly,
so we chose a small set of optimizations. We implemented the
optimizations as pipelined lters so that they can be turned on and
off independently, and yet all run in just two loop passes over the
trace:oneforwardandonebackward.
Every time the trace recorder emits a LIR instruction, the in-
struction is immediately passed to the rst lter in the forward
pipeline. Thus, forward lter optimizations are performed as the
trace is recorded. Each lter may pass each instruction to the next
lter unchanged, write a different instruction to the next lter, or
write no instruction at all. For example, the constant folding lter
can replace a multiply instruction like v 13 := mul 3 ; 1000 with a constantinstruction v 13 = 3000 . Wecurrentlyapplyfourforwardlters:
 On ISAs without oating-point instructions, a soft-oat lter
convertsoating-pointLIRinstructionstosequencesofinteger
instructions.
 CSE(constantsubexpressionelimination),
 expression simplication, including constant folding and a few
algebraicidentities(e.g., a  a = 0 ),and  source language semantic-specic expression simplication,
primarilyalgebraicidentitiesthatallow DOUBLE tobereplaced with INT . For example, LIR that converts an INT to a DOUBLE andthenbackagainwouldberemovedbythislter.
When trace recording is completed, nanojit runs the backward
optimization lters. These are used for optimizations that require
backward program analysis. When running the backward lters,
nanojitreadsoneLIRinstructionatatime,andthereadsarepassed
throughthepipeline.
Wecurrentlyapplythreebackwardlters:
 Deaddata-stackstoreelimination.TheLIRtraceencodesmany
stores to locations in the interpreter stack. But these values are
never read back before exiting the trace (by the interpreter or
another trace). Thus, stores to the stack that are overwritten
before the next exit are dead. Stores to locations that are off
thetopoftheinterpreterstackatfutureexitsarealsodead.
 Deadcall-stackstoreelimination.Thisisthesameoptimization
as above, except applied to the interpreter's call stack used for
functioncallinlining.
 Dead code elimination. This eliminates any operation that
storestoavaluethatisneverused.
After a LIR instruction is successfully read (“pulled”) from
the backward lter pipeline, nanojit's code generator emits native
machineinstruction(s)forit.
5.2 RegisterAllocation
We use a simple greedy register allocator that makes a single
backward pass over the trace (it is integrated with the code gen-
erator). By the time the allocator has reached an instruction like
v 3 = add v 1 ;v 2 , it has already assigned a register to v 3 . If v 1 and v 2 have not yet been assigned registers, the allocator assigns a free
registertoeach.Iftherearenofreeregisters,avalueisselectedfor
spilling. We use a class heuristic that selects the “oldest” register-
carriedvalue(6).
The heuristic considers the set R of values v in registers imme- diately after the current instruction for spilling. Let v m be the last instruction before the current where each v is referred to. Then the Tag
JSType
Description
xx1
number
31-bitintegerrepresentation 000
object
pointertoJSObjecthandle 010
number
pointertodoublehandle 100
string
pointertoJSStringhandle 110
boolean
enumerationfornull,undened,true,false
null,or
undened
Figure 9. Tagged values in the SpiderMonkey JS interpreter.
Testing tags, unboxing (extracting the untagged value) and boxing
(creating tagged values) are signicant costs. Avoiding these costs
isakeybenetoftracing.
heuristic selects v with minimum v m . The motivation is that this freesuparegisterforaslongaspossiblegivenasinglespill.
If we need to spill a value v s at this point, we generate the restore code just after the code for the current instruction. The
correspondingspillcodeisgeneratedjustafterthelastpointwhere
v s wasused.Theregisterthatwasassignedto v s ismarkedfreefor the preceding code, because that register can now be used freely
withoutaffectingthefollowingcode
6. Implementation
To demonstrate the effectiveness of our approach, we have im-
plemented a trace-based dynamic compiler for the SpiderMonkey
JavaScript Virtual Machine (4). SpiderMonkey is the JavaScript
VM embedded in Mozilla's Firefox open-source web browser (2),
whichisusedbymorethan200millionusersworld-wide.Thecore
ofSpiderMonkeyisabytecodeinterpreterimplementedinC++.
In SpiderMonkey, all JavaScript values are represented by the
type jsval . A jsval is machine word in which up to the 3 of the least signicant bits are a type tag, and the remaining bits are data.
See Figure 6 for details. All pointers contained in jsvals point to GC-controlledblocksalignedon8-byteboundaries.
JavaScript object valuesaremappingsofstring-valuedproperty namestoarbitraryvalues.Theyarerepresentedinoneoftwoways
in SpiderMonkey. Most objects are represented by a shared struc-
turaldescription,calledthe objectshape ,thatmapspropertynames to array indexes using a hash table. The object stores a pointer to
the shape and the array of its own property values. Objects with
large, unique sets of property names store their properties directly
inahashtable.
The garbage collector is an exact, non-generational, stop-the-
worldmark-and-sweepcollector.
IntherestofthissectionwediscusskeyareasoftheTraceMon-
keyimplementation.
6.1 CallingCompiledTraces
Compiled traces are stored in a trace cache , indexed by intepreter PC and type map. Traces are compiled so that they may be
called as functions using standard native calling conventions (e.g.,
FASTCALL onx86). The interpreter must hit a loop edge and enter the monitor in
order to call a native trace for the rst time. The monitor computes
the current type map, checks the trace cache for a trace for the
currentPCandtypemap,andifitndsone,executesthetrace.
To execute a trace, the monitor must build a trace activation
record containing imported local and global variables, temporary
stack space, and space for arguments to native calls. The local and
global values are then copied from the interpreter state to the trace
activationrecord.Then,thetraceiscalledlikeanormalCfunction
pointer.
When a trace call returns, the monitor restores the interpreter
state. First, the monitor checks the reason for the trace exit and
applies blacklisting if needed. Then, it pops or synthesizes inter-
preter JavaScript call stack frames as needed. Finally, it copies the
imported variables back from the trace activation record to the in-
terpreterstate.
At least in the current implementation, these steps have a non-
negligible runtime cost, so minimizing the number of interpreter-
to-trace and trace-to-interpreter transitions is essential for perfor-
mance. (see also Section 3.3). Our experiments (see Figure 12)
show that for programs we can trace well such transitions hap-
pen infrequently and hence do not contribute signicantly to total
runtime. In a few programs, where the system is prevented from
recording branch traces for hot side exits by aborts, this cost can
risetoupto10%oftotalexecutiontime.
6.2 TraceStitching
Transitions from a trace to a branch trace at a side exit avoid the
costs of calling traces from the monitor, in a feature called trace stitching . At a side exit, the exiting trace only needs to write live register-carriedvaluesbacktoitstraceactivationrecord.Inourim-
plementation, identical type maps yield identical activation record
layouts, so the trace activation record can be reused immediately
bythebranchtrace.
In programs with branchy trace trees with small traces, trace
stitching has a noticeable cost. Although writing to memory and
then soon reading back would be expected to have a high L1
cache hit rate, for small traces the increased instruction count has
a noticeable cost. Also, if the writes and reads are very close
in the dynamic instruction stream, we have found that current
x86 processors often incur penalties of 6 cycles or more (e.g., if
the instructions use different base registers with equal values, the
processor maynot beable todetect thatthe addresses arethe same
rightaway).
The alternate solution is to recompile an entire trace tree, thus
achieving inter-trace register allocation (10). The disadvantage is
thattreerecompilationtakestimequadraticinthenumberoftraces.
We believe that the cost of recompiling a trace tree every time
a branch is added would be prohibitive. That problem might be
mitigated by recompiling only at certain points, or only for very
hot,stabletrees.
In the future, multicore hardware is expected to be common,
making background tree recompilation attractive. In a closely re-
lated project (13) background recompilation yielded speedups of
up to 1.25x on benchmarks with many branch traces. We plan to
applythistechniquetoTraceMonkeyasfuturework.
6.3 TraceRecording
ThejobofthetracerecorderistoemitLIRwithidenticalsemantics
to the currently running interpreter bytecode trace. A good imple-
mentation should have low impact on non-tracing interpreter per-
formance and a convenient way for implementers to maintain se-
manticequivalence.
Inourimplementation,theonlydirectmodicationtotheinter-
preterisacalltothetracemonitoratloopedges.Inourbenchmark
results (see Figure 12) the total time spent in the monitor (for all
activities) is usually less than 5%, so we consider the interpreter
impact requirement met. Incrementing the loop hit counter is ex-
pensivebecauseitrequiresustolookuptheloopinthetracecache,
but we have tuned our loops to become hot and trace very quickly
(on the second iteration). The hit counter implementation could be
improved, which might give us a small increase in overall perfor-
mance, as well as more exibility with tuning hotness thresholds.
Once a loop is blacklisted we never call into the trace monitor for
thatloop(seeSection3.3). Recording is activated by a pointer swap that sets the inter-
preter's dispatch table to call a single “interrupt” routine for ev-
ery bytecode. The interrupt routine rst calls a bytecode-specic
recording routine. Then, it turns off recording if necessary (e.g.,
the trace ended). Finally, it jumps to the standard interpreter byte-
codeimplementation.Somebytecodeshaveeffectsonthetypemap
that cannot be predicted before executing the bytecode (e.g., call-
ing String.charCodeAt , which returns an integer or NaN if the indexargumentisoutofrange).Forthese,wearrangefortheinter-
preter to call into the recorder again after executing the bytecode.
Since such hooks are relatively rare, we embed them directly into
the interpreter, with an additional runtime check to see whether a
recorderiscurrentlyactive.
Whileseparatingtheinterpreterfromtherecorderreducesindi-
vidualcodecomplexity,italsorequirescarefulimplementationand
extensivetestingtoachievesemanticequivalence.
In some cases achieving this equivalence is difcult since Spi-
derMonkey follows a fat-bytecode design, which was found to be benecialtopureinterpreterperformance.
In fat-bytecode designs, individual bytecodes can implement
complex processing (e.g., the getprop bytecode, which imple- mentsfullJavaScriptpropertyvalueaccess,includingspecialcases
forcachedanddensearrayaccess).
Fat bytecodes have two advantages: fewer bytecodes means
lower dispatch cost, and bigger bytecode implementations give the
compilermoreopportunitiestooptimizetheinterpreter.
Fat bytecodes are a problem for TraceMonkey because they
require the recorder to reimplement the same special case logic
in the same way. Also, the advantages are reduced because (a)
dispatch costs are eliminated entirely in compiled traces, (b) the
traces contain only one special case, not the interpreter's large
chunk of code, and (c) TraceMonkey spends less time running the
baseinterpreter.
Onewaywehavemitigatedtheseproblemsisbyimplementing
certain complex bytecodes in the recorder as sequences of simple
bytecodes.Expressingtheoriginalsemanticsthiswayisnottoodif-
cult,andrecordingsimplebytecodesismucheasier.Thisenables
ustoretaintheadvantagesoffatbytecodeswhileavoidingsomeof
their problems for trace recording. This is particularly effective for
fat bytecodes that recurse back into the interpreter, for example to
convert an object into a primitive value by invoking a well-known
methodontheobject,sinceitletsusinlinethisfunctioncall.
It is important to note that we split fat opcodes into thinner op-
codes only during recording. When running purely interpretatively
(i.e. code that has been blacklisted), the interpreter directly and ef-
cientlyexecutesthefatopcodes.
6.4 Preemption
SpiderMonkey,likemanyVMs,needstopreempttheuserprogram
periodically. The main reasons are to prevent innitely looping
scriptsfromlockingupthehostsystemandtoscheduleGC.
In the interpreter, this had been implemented by setting a “pre-
empt now” ag that was checked on every backward jump. This
strategycarriedoverintoTraceMonkey:theVMinsertsaguardon
the preemption ag at every loop edge. We measured less than a
1% increase in runtime on most benchmarks for this extra guard.
Inpractice,thecostisdetectableonlyforprogramswithveryshort
loops.
We tested and rejected a solution that avoided the guards by
compiling the loop edge as an unconditional jump, and patching
the jump target to an exit routine when preemption is required.
This solution can make the normal case slightly faster, but then
preemption becomes very slow. The implementation was also very
complex,especiallytryingtorestartexecutionafterthepreemption.
6.5 CallingExternalFunctions
Like most interpreters, SpiderMonkey has a foreign function inter-
face(FFI)thatallowsittocallCbuiltinsandhostsystemfunctions
(e.g., web browser control and DOM access). The FFI has a stan-
dardsignatureforJS-callablefunctions,thekeyargumentofwhich
is an array of boxed values. External functions called through the
FFIinteractwiththeprogramstatethroughaninterpreterAPI(e.g.,
to read a property from an argument). There are also certain inter-
preterbuiltinsthatdonotusetheFFI,butinteractwiththeprogram
state in the same way, such as the CallIteratorNext function used with iterator objects. TraceMonkey must support this FFI in
ordertospeedupcodethatinteractswiththehostsysteminsidehot
loops.
CallingexternalfunctionsfromTraceMonkeyispotentiallydif-
cult because traces do not update the interpreter state until exit-
ing. In particular, external functions may need the call stack or the
globalvariables,buttheymaybeoutofdate.
For the out-of-date call stack problem, we refactored some of
the interpreter API implementation functions to re-materialize the
interpretercallstackondemand.
We developed a C++ static analysis and annotated some inter-
preter functions in order to verify that the call stack is refreshed
at any point it needs to be used. In order to access the call stack,
a function must be annotated as either F ORCES S TACK or R E - QUIRES S TACK .Theseannotationsarealsorequiredinordertocall R EQUIRES S TACK functions,whicharepresumedtoaccessthecall stack transitively. F ORCES S TACK is a trusted annotation, applied toonly5functions,thatmeansthefunctionrefreshesthecallstack.
R EQUIRES S TACK is an untrusted annotation that means the func- tionmayonlybecalledifthecallstackhasalreadybeenrefreshed.
Similarly, we detect when host functions attempt to directly
readorwriteglobalvariables,andforcethecurrentlyrunningtrace
to side exit. This is necessary since we cache and unbox global
variablesintotheactivationrecordduringtraceexecution.
Since both call-stack access and global variable access are
rarelyperformedbyhostfunctions,performanceisnotsignicantly
affectedbythesesafetymechanisms.
Anotherproblemisthatexternalfunctionscanreentertheinter-
preter by calling scripts, which in turn again might want to access
thecallstackorglobalvariables.Toaddressthisproblem,wemade
theVMsetaagwhenevertheinterpreterisreenteredwhileacom-
piledtraceisrunning.
Everycalltoanexternalfunctionthenchecksthisagandexits
thetraceimmediatelyafterreturningfromtheexternalfunctioncall
if it is set. There are many external functions that seldom or never
reenter, and they can be called without problem, and will cause
traceexitonlyifnecessary.
The FFI's boxed value array requirement has a performance
cost, so we dened a new FFI that allows C functions to be an-
notated with their argument types so that the tracer can call them
directly,withoutunnecessaryargumentconversions.
Currently, we do not support calling native property get and set
override functions or DOM functions directly from trace. Support
isplannedfuturework.
6.6 Correctness
During development, we had access to existing JavaScript test
suites, but most of them were not designed with tracing VMs in
mindandcontainedfewloops.
One tool that helped us greatly was Mozilla's JavaScript fuzz
tester, JSFUNFUZZ , which generates random JavaScript programs by nesting random language elements. We modied JSFUNFUZZ to generate loops, and also to test more heavily certain constructs
wesuspectedwouldrevealawsinourimplementation.Forexam-
ple,wesuspectedbugsinTraceMonkey'shandlingoftype-unstable
Figure 11. Fraction of dynamic bytecodes executed by inter-
preter and on native traces. The speedup vs. interpreter is shown in parentheses next to each test. The fraction of bytecodes exe-
cuted while recording is too small to see in this gure, except
for crypto-md5 , where fully 3% of bytecodes are executed while recording. In most of the tests, almost all the bytecodes are exe-
cuted by compiled traces. Three of the benchmarks are not traced
atallandrunintheinterpreter.
loops and heavily branching code, and a specialized fuzz tester in-
deedrevealedseveralregressionswhichwesubsequentlycorrected.
7. Evaluation
We evaluated our JavaScript tracing implementation using Sun-
Spider, the industry standard JavaScript benchmark suite. SunSpi-
der consists of 26 short-running (less than 250ms, average 26ms)
JavaScript programs. This is in stark contrast to benchmark suites
such as SpecJVM98 (3) used to evaluate desktop and server Java
VMs. Many programs in those benchmarks use large data sets and
executeforminutes.TheSunSpiderprogramscarryoutavarietyof
tasks,primarily3drendering,bit-bashing,cryptographicencoding,
mathkernels,andstringprocessing.
All experiments were performed on a MacBook Pro with 2.2
GHzCore2processorand2GBRAMrunningMacOS10.5.
Benchmark results. The main question is whether programs runfasterwithtracing.Forthis,weranthestandardSunSpidertest
driver, which starts a JavaScript interpreter, loads and runs each
program once for warmup, then loads and runs each program 10
times and reports the average time taken by each. We ran 4 differ-
ent congurations for comparison: (a) SpiderMonkey, the baseline
interpreter, (b) TraceMonkey, (d) SquirrelFish Extreme (SFX), the
call-threaded JavaScript interpreter used in Apple's WebKit, and
(e)V8,themethod-compilingJavaScriptVMfromGoogle.
Figure10showstherelativespeedupsachievedbytracing,SFX,
and V8 against the baseline (SpiderMonkey). Tracing achieves the
best speedups in integer-heavy benchmarks, up to the 25x speedup
on bitops-bitwise-and . TraceMonkey is the fastest VM on 9 of the 26 benchmarks
( 3d-morph , bitops-3bit-bits-in-byte , bitops-bitwise- and , crypto-sha1 , math-cordic , math-partial-sums , math- spectral-norm , string-base64 , string-validate-input ).
Figure 10. Speedup vs. a baseline JavaScript interpreter (SpiderMonkey) for our trace-based JIT compiler, Apple's SquirrelFish Extreme inlinethreadinginterpreterandGoogle'sV8JScompiler.Oursystemgeneratesparticularlyefcientcodeforprogramsthatbenetmostfrom
type specialization, which includes SunSpider Benchmark programs that perform bit manipulation. We type-specialize the code in question
to use integer arithmetic, which substantially improves performance. For one of the benchmark programs we execute 25 times faster than
theSpiderMonkey interpreter, andalmost5 timesfasterthanV8 andSFX.For alargenumberof benchmarksallthreeVMs producesimilar
results.Weperformworstonbenchmarkprogramsthatwedonottraceandinsteadfallbackontotheinterpreter.Thisincludestherecursive
benchmarks access-binary-trees and control-flow-recursive ,forwhichwecurrentlydon'tgenerateanynativecode. In particular, the bitops benchmarks are short programs that per- form many bitwise operations, so TraceMonkey can cover the en-
tireprogramwith1or2tracesthatoperateonintegers.TraceMon-
key runs all the other programs in this set almost entirely as native
code.
regexp-dna is dominated by regular expression matching, which isimplemented inall 3VMs bya specialregular expression
compiler. Thus, performance on this benchmark has little relation
tothetracecompilationapproachdiscussedinthispaper.
TraceMonkey's smaller speedups on the other benchmarks can
beattributedtoafewspeciccauses:
 The implementation does not currently trace recursion, so
TraceMonkey achieves a small speedup or no speedup on
benchmarks that use recursion extensively: 3d-cube , 3d- raytrace , access-binary-trees , string-tagcloud , and controlflow-recursive .  The implementation does not currently trace eval and some other functions implemented in C. Because date-format- tofte and date-format-xparb use such functions in their mainloops,wedonottracethem.
 The implementation does not currently trace through regular
expression replace operations. The replace function can be passed a function object used to compute the replacement text.
Our implementation currently does not trace functions called
asreplacefunctions.Theruntimeof string-unpack-code is dominatedbysucha replace call.  Two programs trace well, but have a long compilation time.
access-nbody formsalargenumberoftraces(81). crypto-md5 forms one very long trace. We expect to improve performance
on this programs by improving the compilation speed of nano-
jit.
 Some programs trace very well, and speed up compared to
the interpreter, but are not as fast as SFX and/or V8, namely
bitops-bits-in-byte , bitops-nsieve-bits , access- fannkuch , access-nsieve , and crypto-aes . The reason is not clear, but all of these programs have nested loops with
small bodies, so we suspect that the implementation has a rela-
tivelyhighcostforcallingnestedtraces. string-fasta traces well,butitsruntimeisdominatedbystringprocessingbuiltins,
which are unaffected by tracing and seem to be less efcient in
SpiderMonkeythaninthetwootherVMs.
Detailedperformancemetrics. InFigure11weshowthefrac- tion of instructions interpreted and the fraction of instructions exe-
cutedasnativecode.Thisgureshowsthatformanyprograms,we
areabletoexecutealmostallthecodenatively.
Figure 12 breaks down the total execution time into four activ-
ities: interpreting bytecodes while not recording, recording traces
(including time taken to interpret the recorded trace), compiling
tracestonativecode,andexecutingnativecodetraces.
These detailed metrics allow us to estimate parameters for a
simple model of tracing performance. These estimates should be
considered very rough, as the values observed on the individual
benchmarks have large standard deviations (on the order of the
Loops Trees Traces Aborts Flushes Trees/Loop Traces/Tree Traces/Loop Speedup
3d-cube 25 27 29 3 0 1.1 1.1 1.2 2.20x
3d-morph 5 8 8 2 0 1.6 1.0 1.6 2.86x
3d-raytrace 10 25 100 10 1 2.5 4.0 10.0 1.18x
access-binary-trees 0 0 0 5 0 - - - 0.93x
access-fannkuch 10 34 57 24 0 3.4 1.7 5.7 2.20x
access-nbody 8 16 18 5 0 2.0 1.1 2.3 4.19x
access-nsieve 3 6 8 3 0 2.0 1.3 2.7 3.05x
bitops-3bit-bits-in-byte 2 2 2 0 0 1.0 1.0 1.0 25.47x
bitops-bits-in-byte 3 3 4 1 0 1.0 1.3 1.3 8.67x
bitops-bitwise-and 1 1 1 0 0 1.0 1.0 1.0 25.20x
bitops-nsieve-bits 3 3 5 0 0 1.0 1.7 1.7 2.75x
controlow-recursive 0 0 0 1 0 - - - 0.98x
crypto-aes 50 72 78 19 0 1.4 1.1 1.6 1.64x
crypto-md5 4 4 5 0 0 1.0 1.3 1.3 2.30x
crypto-sha1 5 5 10 0 0 1.0 2.0 2.0 5.95x
date-format-tofte 3 3 4 7 0 1.0 1.3 1.3 1.07x
date-format-xparb 3 3 11 3 0 1.0 3.7 3.7 0.98x
math-cordic 2 4 5 1 0 2.0 1.3 2.5 4.92x
math-partial-sums 2 4 4 1 0 2.0 1.0 2.0 5.90x
math-spectral-norm 15 20 20 0 0 1.3 1.0 1.3 7.12x
regexp-dna 2 2 2 0 0 1.0 1.0 1.0 4.21x
string-base64 3 5 7 0 0 1.7 1.4 2.3 2.53x
string-fasta 5 11 15 6 0 2.2 1.4 3.0 1.49x
string-tagcloud 3 6 6 5 0 2.0 1.0 2.0 1.09x
string-unpack-code 4 4 37 0 0 1.0 9.3 9.3 1.20x
string-validate-input 6 10 13 1 0 1.7 1.3 2.2 1.86x
Figure13. DetailedtracerecordingstatisticsfortheSunSpiderbenchmarkset. mean). We exclude regexp-dna from the following calculations, becausemostofitstimeisspentintheregularexpressionmatcher,
which has much different performance characteristics from the
other programs. (Note that this only makes a difference of about
10% in the results.) Dividing the total execution time in processor
clock cycles by the number of bytecodes executed in the base
interpreter shows that on average, a bytecode executes in about
35 cycles. Native traces take about 9 cycles per bytecode, a 3.9x
speedupovertheinterpreter.
Using similar computations, we nd that trace recording takes
about 3800 cycles per bytecode, and compilation 3150 cycles per
bytecode. Hence, during recording and compiling the VM runs at
1/200 the speed of the interpreter. Because it costs 6950 cycles to
compile a bytecode, and we save 26 cycles each time that code is
runnatively,webreakevenafterrunningatrace270times.
The other VMs we compared with achieve an overall speedup
of 3.0x relative to our baseline interpreter. Our estimated native
code speedup of 3.9x is signicantly better. This suggests that
ourcompilationtechniquescangeneratemoreefcientnativecode
thananyothercurrentJavaScriptVM.
Theseestimatesalsoindicatethatourstartupperformancecould
be substantially better if we improved the speed of trace recording
and compilation. The estimated 200x slowdown for recording and
compilationisveryrough,andmaybeinuencedbystartupfactors
in the interpreter (e.g., caches that have not warmed up yet during
recording). One observation supporting this conjecture is that in
thetracer,interpretedbytecodestakeabout180cyclestorun.Still,
recording and compilation are clearly both expensive, and a better
implementation, possibly including redesign of the LIR abstract
syntaxorencoding,wouldimprovestartupperformance.
Our performance results conrm that type specialization using
trace trees substantially improves performance. We are able to
outperform the fastest available JavaScript compiler (V8) and the fastest available JavaScript inline threaded interpreter (SFX) on 9
of26benchmarks.
8. RelatedWork
Trace optimization for dynamic languages. The closest area of related work is on applying trace optimization to type-specialize
dynamic languages. Existing work shares the idea of generating
type-specialized code speculatively with guards along interpreter
traces.
To our knowledge, Rigo's Psyco (16) is the only published
type-specializing trace compiler for a dynamic language (Python).
Psycodoesnotattempttoidentifyhotloopsorinlinefunctioncalls.
Instead,Psycotransformsloopstomutualrecursionbeforerunning
andtracesalloperations.
Pall's LuaJIT is a Lua VM in development that uses trace com-
pilationideas.(1).TherearenopublicationsonLuaJITbutthecre-
ator has told us that LuaJIT has a similar design to our system, but
will use a less aggressive type speculation (e.g., using a oating-
point representation for all number values) and does not generate
nestedtracesfornestedloops.
General trace optimization. General trace optimization has a longer history that has treated mostly native code and typed
languages like Java. Thus, these systems have focused less on type
specializationandmoreonotheroptimizations.
Dynamo (7) by Bala et al, introduced native code tracing as a
replacement for prole-guided optimization (PGO). A major goal
was to perform PGO online so that the prole was specic to
the current execution. Dynamo used loop headers as candidate hot
traces,butdidnottrytocreatelooptracesspecically.
Trace trees were originally proposed by Gal et al. (11) in the
context of Java, a statically typed language. Their trace trees ac-
tually inlined parts of outer loops within the inner loops (because
Figure 12. Fraction of time spent on major VM activities. The speedup vs. interpreter is shown in parentheses next to each test.
Most programs where the VM spends the majority of its time run-
ning native code have a good speedup. Recording and compilation
costs can be substantial; speeding up those parts of the implemen-
tationwouldimproveSunSpiderperformance.
inner loops become hot rst), leading to much greater tail duplica-
tion.
YETI, from Zaleski et al. (19) applied Dynamo-style tracing
to Java in order to achieve inlining, indirect jump elimination,
and other optimizations. Their primary focus was on designing an
interpreterthatcouldeasilybegraduallyre-engineeredasatracing
VM.
Suganumaetal.(18)describedregion-basedcompilation(RBC),
a relative of tracing. A region is an subprogram worth optimizing
thatcanincludesubsetsofanynumberofmethods.Thus,thecom-
piler has more exibility and can potentially generate better code,
buttheprolingandcompilationsystemsarecorrespondinglymore
complex.
Type specialization for dynamic languages. Dynamic lan- guage implementors have long recognized the importance of type
specializationforperformance.Mostpreviousworkhasfocusedon
methodsinsteadoftraces.
Chambers et. al (9) pioneered the idea of compiling multiple
versions of a procedure specialized for the input types in the lan-
guage Self. In one implementation, they generated a specialized
methodonlineeachtimeamethodwascalledwithnewinputtypes.
In another, they used an ofine whole-program static analysis to
infer input types and constant receiver types at call sites. Interest-
ingly,thetwotechniquesproducednearlythesameperformance.
Salib(17)designedatypeinferencealgorithmforPythonbased
ontheCartesianProductAlgorithmandusedtheresultstospecial-
izeontypesandtranslatetheprogramtoC++.
McCloskey (14) has work in progress based on a language-
independent type inference that is used to generate efcient C
implementationsofJavaScriptandPythonprograms.
Native code generation by interpreters. The traditional inter- preter design is a virtual machine that directly executes ASTs or
machine-code-likebytecodes.Researchershaveshownhowtogen- erate native code with nearly the same structure but better perfor-
mance.
Call threading, also known as context threading (8), compiles
methods by generating a native call instruction to an interpreter
method for each interpreter bytecode. A call-return pair has been
showntobeapotentiallymuchmoreefcientdispatchmechanism
thantheindirectjumpsusedinstandardbytecodeinterpreters.
Inline threading (15) copies chunks of interpreter native code
which implement the required bytecodes into a native code cache,
thusactingasasimpleper-methodJITcompilerthateliminatesthe
dispatchoverhead.
Neithercallthreadingnorinlinethreadingperformtypespecial-
ization.
Apple's SquirrelFish Extreme (5) is a JavaScript implementa-
tion based on call threading with selective inline threading. Com-
bined with efcient interpreter engineering, these threading tech-
niqueshavegivenSFXexcellentperformanceonthestandardSun-
Spiderbenchmarks.
Google's V8 is a JavaScript implementation primarily based
on inline threading, with call threading only for very complex
operations.
9. Conclusions
This paper described how to run dynamic languages efciently by
recording hot traces and generating type-specialized native code.
Our technique focuses on aggressively inlined loops, and for each
loop, it generates a tree of native code traces representing the
paths and value types through the loop observed at run time. We
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,
which translates a trace from an intermediate representation to
optimizednativecodeintwolinearpasses.
Our experimental results show that in practice loops typically
are entered with only a few different combinations of value types
of variables. Thus, a small number of traces per loop is sufcient
to run a program efciently. Our experiments also show that on
programsamenabletotracing,weachievespeedupsof2xto20x.
10. FutureWork
Work is underway in a number of areas to further improve the
performance of our trace-based JavaScript compiler. We currently
do not trace across recursive function calls, but plan to add the
support for this capability in the near term. We are also exploring
adoption of the existing work on tree recompilation in the context
of the presented dynamic compiler in order to minimize JIT pause
times and obtain the best of both worlds, fast tree stitching as well
astheimprovedcodequalityduetotreerecompilation.
We also plan on adding support for tracing across regular ex-
pression substitutions using lambda functions, function applica-
tions and expression evaluation using eval . All these language constructs are currently executed via interpretation, which limits
ourperformanceforapplicationsthatusethosefeatures.
Acknowledgments
Parts of this effort have been sponsored by the National Science
FoundationundergrantsCNS-0615443andCNS-0627747,aswell
as by the California MICRO Program and industrial sponsor Sun
MicrosystemsunderProjectNo.07-127.
The U.S. Government is authorized to reproduce and distribute
reprintsfor Governmentalpurposes notwithstandingany copyright
annotationthereon.Anyopinions,ndings,andconclusionsorrec-
ommendations expressed here are those of the author and should
not be interpreted as necessarily representing the ofcial views,
policies or endorsements, either expressed or implied, of the Na-
tionalSciencefoundation(NSF),anyotheragencyoftheU.S.Gov-
ernment,oranyofthecompaniesmentionedabove.
References
[1] LuaJIT roadmap 2008 - http://lua-users.org/lists/lua-l/2008-
02/msg00051.html.
[2] Mozilla — Firefox web browser and Thunderbird email client -
http://www.mozilla.com.
[3] SPECJVM98-http://www.spec.org/jvm98/.
[4] SpiderMonkey (JavaScript-C) Engine -
http://www.mozilla.org/js/spidermonkey/.
[5] Surn' Safari - Blog Archive - Announcing SquirrelFish Extreme -
http://webkit.org/blog/214/introducing-squirrelsh-extreme/.
[6] A. Aho, R. Sethi, J. Ullman, and M. Lam. Compilers: Principles,
techniques,andtools,2006.
[7] V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent
dynamic optimization system. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation , pages1–12.ACMPress,2000.
[8] M. Berndl, B. Vitale, M. Zaleski, and A. Brown. Context Threading:
a Flexible and Efcient Dispatch Technique for Virtual Machine In-
terpreters. In Code Generation and Optimization, 2005. CGO 2005. InternationalSymposiumon ,pages15–26,2005. [9] C. Chambers and D. Ungar. Customization: Optimizing Compiler
Technology for SELF, a Dynamically-Typed O bject-Oriented Pro-
gramming Language. In Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation , pages146–160.ACMNewYork,NY,USA,1989. [10] A. Gal. Efcient Bytecode Verication and Compilation in a Virtual Machine Dissertation . PhD thesis, University Of California, Irvine, 2006.
[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 144–153.ACMPress,2006.
[12] C. Garrett, J. Dean, D. Grove, and C. Chambers. Measurement and
ApplicationofDynamicReceiverClassDistributions. 1994.
[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
Sciences,TheUniversityofTexasatAustin,TR-09-06,2009.
[14] B.McCloskey. Personalcommunication.
[15] I.PiumartaandF.Riccardi. Optimizingdirectthreadedcodebyselec-
tive inlining. In Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation , pages 291– 300.ACMNewYork,NY,USA,1998.
[16] A. Rigo. Representation-Based Just-In-time Specialization and the
PsycoPrototypeforPython. In PEPM ,2004. [17] M. Salib. Starkiller: A Static Type Inferencer and Compiler for
Python. In Master'sThesis ,2004. [18] T. Suganuma, T. Yasue, and T. Nakatani. A Region-Based Compila-
tion Technique for Dynamic Compilers. ACM Transactions on Pro- grammingLanguagesandSystems(TOPLAS) ,28(1):134–174,2006. [19] M. Zaleski, A. D. Brown, and K. Stoodley. YETI: A graduallY
Extensible Trace Interpreter. In Proceedings of the International Conference on Virtual Execution Environments , pages 83–93. ACM Press,2007.