Trace-basedJust-in-TimeTypeSpecializationforDynamicLanguagesAndreasGal∗+,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.comAdobeCorporation#{edwsmith,rreitmai}@adobe.comIntelCorporation${mohammad.r.haghighat}@intel.comUniversityofCalifornia,Irvine+{mbebenit,changm,franz}@uci.eduAbstractDynamiclanguagessuchasJavaScriptaremoredifficulttocom-pilethanstaticallytypedones.Sincenoconcretetypeinformationisavailable,traditionalcompilersneedtoemitgenericcodethatcanhandleallpossibletypecombinationsatruntime.Wepresentanal-ternativecompilationtechniquefordynamically-typedlanguagesthatidentifiesfrequentlyexecutedlooptracesatrun-timeandthengeneratesmachinecodeontheflythatisspecializedfortheac-tualdynamictypesoccurringoneachpaththroughtheloop.Ourmethodprovidescheapinter-proceduraltypespecialization,andanelegantandefficientwayofincrementallycompilinglazilydiscov-eredalternativepathsthroughnestedloops.WehaveimplementedadynamiccompilerforJavaScriptbasedonourtechniqueandwehavemeasuredspeedupsof10xandmoreforcertainbenchmarkprograms.CategoriesandSubjectDescriptorsD.3.4[ProgrammingLan-guages]:Processors—Incrementalcompilers,codegeneration.GeneralTermsDesign,Experimentation,Measurement,Perfor-mance.KeywordsJavaScript,just-in-timecompilation,tracetrees.1.IntroductionDynamiclanguagessuchasJavaScript,Python,andRuby,arepop-ularsincetheyareexpressive,accessibletonon-experts,andmakedeploymentaseasyasdistributingasourcefile.Theyareusedforsmallscriptsaswellasforcomplexapplications.JavaScript,forexample,isthedefactostandardforclient-sidewebprogrammingPermissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.PLDI’09,June15–20,2009,Dublin,Ireland.Copyrightc(cid:13)2009ACM978-1-60558-392-1/09/06...$5.00andisusedfortheapplicationlogicofbrowser-basedproductivityapplicationssuchasGoogleMail,GoogleDocsandZimbraCol-laborationSuite.Inthisdomain,inordertoprovideafluiduserexperienceandenableanewgenerationofapplications,virtualma-chinesmustprovidealowstartuptimeandhighperformance.Compilersforstaticallytypedlanguagesrelyontypeinforma-tiontogenerateefficientmachinecode.Inadynamicallytypedpro-gramminglanguagesuchasJavaScript,thetypesofexpressionsmayvaryatruntime.Thismeansthatthecompilercannolongereasilytransformoperationsintomachineinstructionsthatoperateononespecifictype.Withoutexacttypeinformation,thecompilermustemitslowergeneralizedmachinecodethatcandealwithallpotentialtypecombinations.Whilecompile-timestatictypeinfer-encemightbeabletogathertypeinformationtogenerateopti-mizedmachinecode,traditionalstaticanalysisisveryexpensiveandhencenotwellsuitedforthehighlyinteractiveenvironmentofawebbrowser.Wepresentatrace-basedcompilationtechniquefordynamiclanguagesthatreconcilesspeedofcompilationwithexcellentper-formanceofthegeneratedmachinecode.Oursystemusesamixed-modeexecutionapproach:thesystemstartsrunningJavaScriptinafast-startingbytecodeinterpreter.Astheprogramruns,thesystemidentifieshot(frequentlyexecuted)bytecodesequences,recordsthem,andcompilesthemtofastnativecode.Wecallsuchase-quenceofinstructionsatrace.Unlikemethod-baseddynamiccompilers,ourdynamiccom-pileroperatesatthegranularityofindividualloops.Thisdesignchoiceisbasedontheexpectationthatprogramsspendmostoftheirtimeinhotloops.Evenindynamicallytypedlanguages,weexpecthotloopstobemostlytype-stable,meaningthatthetypesofvaluesareinvariant.(12)Forexample,wewouldexpectloopcoun-tersthatstartasintegerstoremainintegersforalliterations.Whenbothoftheseexpectationshold,atrace-basedcompilercancovertheprogramexecutionwithasmallnumberoftype-specialized,ef-ficientlycompiledtraces.Eachcompiledtracecoversonepaththroughtheprogramwithonemappingofvaluestotypes.WhentheVMexecutesacompiledtrace,itcannotguaranteethatthesamepathwillbefollowedorthatthesametypeswilloccurinsubsequentloopiterations.Hence,recordingandcompilingatracespeculatesthatthepathandtypingwillbeexactlyastheywereduringrecordingforsubsequentiterationsoftheloop.Everycompiledtracecontainsalltheguards(checks)requiredtovalidatethespeculation.Ifoneoftheguardsfails(ifcontrolflowisdifferent,oravalueofadifferenttypeisgenerated),thetraceexits.Ifanexitbecomeshot,theVMcanrecordabranchtracestartingattheexittocoverthenewpath.Inthisway,theVMrecordsatracetreecoveringallthehotpathsthroughtheloop.NestedloopscanbedifficulttooptimizefortracingVMs.Inana¨ıveimplementation,innerloopswouldbecomehotfirst,andtheVMwouldstarttracingthere.Whentheinnerloopexits,theVMwoulddetectthatadifferentbranchwastaken.TheVMwouldtrytorecordabranchtrace,andfindthatthetracereachesnottheinnerloopheader,buttheouterloopheader.Atthispoint,theVMcouldcontinuetracinguntilitreachestheinnerloopheaderagain,thustracingtheouterloopinsideatracetreefortheinnerloop.Butthisrequirestracingacopyoftheouterloopforeverysideexitandtypecombinationintheinnerloop.Inessence,thisisaformofunintendedtailduplication,whichcaneasilyoverflowthecodecache.Alternatively,theVMcouldsimplystoptracing,andgiveuponevertracingouterloops.Wesolvethenestedloopproblembyrecordingnestedtracetrees.Oursystemtracestheinnerloopexactlyasthena¨ıveversion.Thesystemstopsextendingtheinnertreewhenitreachesanouterloop,butthenitstartsanewtraceattheouterloopheader.Whentheouterloopreachestheinnerloopheader,thesystemtriestocallthetracetreefortheinnerloop.Ifthecallsucceeds,theVMrecordsthecalltotheinnertreeaspartoftheoutertraceandfinishestheoutertraceasnormal.Inthisway,oursystemcantraceanynumberofloopsnestedtoanydepthwithoutcausingexcessivetailduplication.ThesetechniquesallowaVMtodynamicallytranslateapro-gramtonested,type-specializedtracetrees.Becausetracescancrossfunctioncallboundaries,ourtechniquesalsoachievetheef-fectsofinlining.Becausetraceshavenointernalcontrol-flowjoins,theycanbeoptimizedinlineartimebyasimplecompiler(10).Thus,ourtracingVMefficientlyperformsthesamekindofop-timizationsthatwouldrequireinterproceduralanalysisinastaticoptimizationsetting.Thismakestracinganattractiveandeffectivetooltotypespecializeevencomplexfunctioncall-richcode.WeimplementedthesetechniquesforanexistingJavaScriptin-terpreter,SpiderMonkey.WecalltheresultingtracingVMTrace-Monkey.TraceMonkeysupportsalltheJavaScriptfeaturesofSpi-derMonkey,witha2x-20xspeedupfortraceableprograms.Thispapermakesthefollowingcontributions:•Weexplainanalgorithmfordynamicallyformingtracetreestocoveraprogram,representingnestedloopsasnestedtracetrees.•Weexplainhowtospeculativelygenerateefficienttype-specializedcodefortracesfromdynamiclanguageprograms.•WevalidateourtracingtechniquesinanimplementationbasedontheSpiderMonkeyJavaScriptinterpreter,achieving2x-20xspeedupsonmanyprograms.Theremainderofthispaperisorganizedasfollows.Section3isageneraloverviewoftracetreebasedcompilationweusetocap-tureandcompilefrequentlyexecutedcoderegions.InSection4wedescribeourapproachofcoveringnestedloopsusinganum-berofindividualtracetrees.InSection5wedescribeourtrace-compilationbasedspeculativetypespecializationapproachweusetogenerateefficientmachinecodefromrecordedbytecodetraces.Ourimplementationofadynamictype-specializingcompilerforJavaScriptisdescribedinSection6.RelatedworkisdiscussedinSection8.InSection7weevaluateourdynamiccompilerbasedon1for(vari=2;i<100;++i){2if(!primes[i])3continue;4for(vark=i+i;i<100;k+=i)5primes[k]=false;6}Figure1.Sampleprogram:sieveofEratosthenes.primesisinitializedtoanarrayof100falsevaluesonentrytothiscodesnippet.Interpret BytecodesMonitor RecordLIR TraceExecute Compiled TraceEnter Compiled TraceCompileLIR TraceLeave Compiled Traceloop edgehotloop/exitabort recordingfinish at loop headercold/blacklistedloop/exitcompiled trace readyloop edge with same typesside exit to existing traceside exit,no existing traceOverhead InterpretingNativeSymbol KeyFigure2.StatemachinedescribingthemajoractivitiesofTrace-Monkeyandtheconditionsthatcausetransitionstoanewactiv-ity.Inthedarkbox,TMexecutesJSascompiledtraces.Inthelightgrayboxes,TMexecutesJSinthestandardinterpreter.Whiteboxesareoverhead.Thus,tomaximizeperformance,weneedtomaximizetimespentinthedarkestboxandminimizetimespentinthewhiteboxes.Thebestcaseisaloopwherethetypesattheloopedgearethesameasthetypesonentry–thenTMcanstayinnativecodeuntiltheloopisdone.asetofindustrybenchmarks.ThepaperendswithconclusionsinSection9andanoutlookonfutureworkispresentedinSection10.2.Overview:ExampleTracingRunThissectionprovidesanoverviewofoursystembydescribinghowTraceMonkeyexecutesanexampleprogram.Theexampleprogram,showninFigure1,computesthefirst100primenumberswithnestedloops.ThenarrativeshouldbereadalongwithFigure2,whichdescribestheactivitiesTraceMonkeyperformsandwhenittransitionsbetweentheloops.TraceMonkeyalwaysbeginsexecutingaprograminthebyte-codeinterpreter.Everyloopbackedgeisapotentialtracepoint.Whentheinterpretercrossesaloopedge,TraceMonkeyinvokesthetracemonitor,whichmaydecidetorecordorexecuteanativetrace.Atthestartofexecution,therearenocompiledtracesyet,sothetracemonitorcountsthenumberoftimeseachloopbackedgeisexecuteduntilaloopbecomeshot,currentlyafter2crossings.Notethatthewayourloopsarecompiled,theloopedgeiscrossedbeforeenteringtheloop,sothesecondcrossingoccursimmediatelyafterthefirstiteration.Hereisthesequenceofeventsbrokendownbyouterloopiteration:v0:=ldstate[748]//loadprimesfromthetraceactivationrecordstsp[0],v0//storeprimestointerpreterstackv1:=ldstate[764]//loadkfromthetraceactivationrecordv2:=i2f(v1)//convertkfrominttodoublestsp[8],v1//storektointerpreterstackstsp[16],0//storefalsetointerpreterstackv3:=ldv0[4]//loadclasswordforprimesv4:=andv3,-4//maskoutobjectclasstagforprimesv5:=eqv4,Array//testwhetherprimesisanarrayxfv5//sideexitifv5isfalsev6:=js_Array_set(v0,v2,false)//callfunctiontosetarrayelementv7:=eqv6,0//testreturnvaluefromcallxtv7//sideexitifjs_Array_setreturnsfalse.Figure3.LIRsnippetforsampleprogram.ThisistheLIRrecordedforline5ofthesampleprograminFigure1.TheLIRencodesthesemanticsinSSAformusingtemporaryvariables.TheLIRalsoencodesallthestoresthattheinterpreterwoulddotoitsdatastack.Sometimesthesestorescanbeoptimizedawayasthestacklocationsareliveonlyonexitstotheinterpreter.Finally,theLIRrecordsguardsandsideexitstoverifytheassumptionsmadeinthisrecording:thatprimesisanarrayandthatthecalltosetitselementsucceeds.movedx,ebx(748)//loadprimesfromthetraceactivationrecordmovedi(0),edx//(*)storeprimestointerpreterstackmovesi,ebx(764)//loadkfromthetraceactivationrecordmovedi(8),esi//(*)storektointerpreterstackmovedi(16),0//(*)storefalsetointerpreterstackmoveax,edx(4)//(*)loadobjectclasswordforprimesandeax,-4//(*)maskoutobjectclasstagforprimescmpeax,Array//(*)testwhetherprimesisanarrayjneside_exit_1//(*)sideexitifprimesisnotanarraysubesp,8//bumpstackforcallalignmentconventionpushfalse//pushlastargumentforcallpushesi//pushfirstargumentforcallcalljs_Array_set//callfunctiontosetarrayelementaddesp,8//cleanupextrastackspacemovecx,ebx//(*)createdbyregisterallocatortesteax,eax//(*)testreturnvalueofjs_Array_setjeside_exit_2//(*)sideexitifcallfailed...side_exit_1:movecx,ebp(-4)//restoreecxmovesp,ebp//restoreespjmpepilog//jumptoretstatementFigure4.x86snippetforsampleprogram.Thisisthex86codecompiledfromtheLIRsnippetinFigure3.MostLIRinstructionscompiletoasinglex86instruction.Instructionsmarkedwith(*)wouldbeomittedbyanidealizedcompilerthatknewthatnoneofthesideexitswouldeverbetaken.The17instructionsgeneratedbythecompilercomparefavorablywiththe100+instructionsthattheinterpreterwouldexecuteforthesamecodesnippet,including4indirectjumps.i=2.Thisisthefirstiterationoftheouterloop.Thelooponlines4-5becomeshotonitsseconditeration,soTraceMonkeyen-tersrecordingmodeonline4.Inrecordingmode,TraceMonkeyrecordsthecodealongthetraceinalow-levelcompilerintermedi-aterepresentationwecallLIR.TheLIRtraceencodesalltheoper-ationsperformedandthetypesofalloperands.TheLIRtracealsoencodesguards,whicharechecksthatverifythatthecontrolflowandtypesareidenticaltothoseobservedduringtracerecording.Thus,onlaterexecutions,ifandonlyifallguardsarepassed,thetracehastherequiredprogramsemantics.TraceMonkeystopsrecordingwhenexecutionreturnstotheloopheaderorexitstheloop.Inthiscase,executionreturnstotheloopheaderonline4.Afterrecordingisfinished,TraceMonkeycompilesthetracetonativecodeusingtherecordedtypeinformationforoptimization.TheresultisanativecodefragmentthatcanbeenterediftheinterpreterPCandthetypesofvaluesmatchthoseobservedwhentracerecordingwasstarted.Thefirsttraceinourexample,T45,coverslines4and5.ThistracecanbeenteredifthePCisatline4,iandkareintegers,andprimesisanobject.AftercompilingT45,TraceMonkeyreturnstotheinterpreterandloopsbacktoline1.i=3.Nowtheloopheaderatline1hasbecomehot,soTrace-Monkeystartsrecording.Whenrecordingreachesline4,Trace-Monkeyobservesthatithasreachedaninnerloopheaderthatal-readyhasacompiledtrace,soTraceMonkeyattemptstonesttheinnerloopinsidethecurrenttrace.Thefirststepistocalltheinnertraceasasubroutine.Thisexecutesthelooponline4tocompletionandthenreturnstotherecorder.TraceMonkeyverifiesthatthecallwassuccessfulandthenrecordsthecalltotheinnertraceaspartofthecurrenttrace.Recordingcontinuesuntilexecutionreachesline1,andatwhichpointTraceMonkeyfinishesandcompilesatracefortheouterloop,T16.i=4.Onthisiteration,TraceMonkeycallsT16.Becausei=4,theifstatementonline2istaken.Thisbranchwasnottakenintheoriginaltrace,sothiscausesT16tofailaguardandtakeasideexit.Theexitisnotyethot,soTraceMonkeyreturnstotheinterpreter,whichexecutesthecontinuestatement.i=5.TraceMonkeycallsT16,whichinturncallsthenestedtraceT45.T16loopsbacktoitsownheader,startingthenextiterationwithouteverreturningtothemonitor.i=6.Onthisiteration,thesideexitonline2istakenagain.Thistime,thesideexitbecomeshot,soatraceT23,1isrecordedthatcoversline3andreturnstotheloopheader.Thus,theendofT23,1jumpsdirectlytothestartofT16.Thesideexitispatchedsothatonfutureiterations,itjumpsdirectlytoT23,1.Atthispoint,TraceMonkeyhascompiledenoughtracestocovertheentirenestedloopstructure,sotherestoftheprogramrunsentirelyasnativecode.3.TraceTreesInthissection,wedescribetraces,tracetrees,andhowtheyareformedatruntime.Althoughourtechniquesapplytoanydynamiclanguageinterpreter,wewilldescribethemassumingabytecodeinterpretertokeeptheexpositionsimple.3.1TracesAtraceissimplyaprogrampath,whichmaycrossfunctioncallboundaries.TraceMonkeyfocusesonlooptraces,thatoriginateataloopedgeandrepresentasingleiterationthroughtheassociatedloop.Similartoanextendedbasicblock,atraceisonlyenteredatthetop,butmayhavemanyexits.Incontrasttoanextendedbasicblock,atracecancontainjoinnodes.Sinceatracealwaysonlyfollowsonesinglepaththroughtheoriginalprogram,however,joinnodesarenotrecognizableassuchinatraceandhaveasinglepredecessornodelikeregularnodes.Atypedtraceisatraceannotatedwithatypeforeveryvariable(includingtemporaries)onthetrace.Atypedtracealsohasanentrytypemapgivingtherequiredtypesforvariablesusedonthetracebeforetheyaredefined.Forexample,atracecouldhaveatypemap(x:int,b:boolean),meaningthatthetracemaybeenteredonlyifthevalueofthevariablexisoftypeintandthevalueofbisoftypeboolean.Theentrytypemapismuchlikethesignatureofafunction.Inthispaper,weonlydiscusstypedlooptraces,andwewillrefertothemsimplyas“traces”.Thekeypropertyoftypedlooptracesisthattheycanbecompiledtoefficientmachinecodeusingthesametechniquesusedfortypedlanguages.InTraceMonkey,tracesarerecordedintrace-flavoredSSALIR(low-levelintermediaterepresentation).Intrace-flavoredSSA(orTSSA),phinodesappearonlyattheentrypoint,whichisreachedbothonentryandvialoopedges.TheimportantLIRprimitivesareconstantvalues,memoryloadsandstores(byaddressandoffset),integeroperators,floating-pointoperators,functioncalls,andconditionalexits.Typeconversions,suchasintegertodouble,arerepresentedbyfunctioncalls.ThismakestheLIRusedbyTraceMonkeyindependentoftheconcretetypesystemandtypeconversionrulesofthesourcelanguage.TheLIRoperationsaregenericenoughthatthebackendcompilerislanguageindependent.Figure3showsanexampleLIRtrace.Bytecodeinterpreterstypicallyrepresentvaluesinavariouscomplexdatastructures(e.g.,hashtables)inaboxedformat(i.e.,withattachedtypetagbits).Sinceatraceisintendedtorepresentefficientcodethateliminatesallthatcomplexity,ourtracesoper-ateonunboxedvaluesinsimplevariablesandarraysasmuchaspossible.Atracerecordsallitsintermediatevaluesinasmallactivationrecordarea.Tomakevariableaccessesfastontrace,thetracealsoimportslocalandglobalvariablesbyunboxingthemandcopyingthemtoitsactivationrecord.Thus,thetracecanreadandwritethesevariableswithsimpleloadsandstoresfromanativeactivationrecording,independentlyoftheboxingmechanismusedbytheinterpreter.Whenthetraceexits,theVMboxesthevaluesfromthisnativestoragelocationandcopiesthembacktotheinterpreterstructures.Foreverycontrol-flowbranchinthesourceprogram,therecordergeneratesconditionalexitLIRinstructions.Theseinstruc-tionsexitfromthetraceifrequiredcontrolflowisdifferentfromwhatitwasattracerecording,ensuringthatthetraceinstructionsarerunonlyiftheyaresupposedto.Wecalltheseinstructionsguardinstructions.MostofourtracesrepresentloopsandendwiththespecialloopLIRinstruction.Thisisjustanunconditionalbranchtothetopofthetrace.Suchtracesreturnonlyviaguards.Now,wedescribethekeyoptimizationsthatareperformedaspartofrecordingLIR.Alloftheseoptimizationsreducecomplexdynamiclanguageconstructstosimpletypedconstructsbyspe-cializingforthecurrenttrace.Eachoptimizationrequiresguardin-structionstoverifytheirassumptionsaboutthestateandexitthetraceifnecessary.Typespecialization.AllLIRprimitivesapplytooperandsofspecifictypes.Thus,LIRtracesarenecessarilytype-specialized,andacompilercaneasilyproduceatranslationthatrequiresnotypedispatches.Atypicalbytecodeinterpretercarriestagbitsalongwitheachvalue,andtoperformanyoperation,mustcheckthetagbits,dynamicallydispatch,maskoutthetagbitstorecovertheuntaggedvalue,performtheoperation,andthenreapplytags.LIRomitseverythingexcepttheoperationitself.Apotentialproblemisthatsomeoperationscanproducevaluesofunpredictabletypes.Forexample,readingapropertyfromanobjectcouldyieldavalueofanytype,notnecessarilythetypeobservedduringrecording.Therecorderemitsguardinstructionsthatconditionallyexitiftheoperationyieldsavalueofadifferenttypefromthatseenduringrecording.Theseguardinstructionsguaranteethataslongasexecutionisontrace,thetypesofvaluesmatchthoseofthetypedtrace.WhentheVMobservesasideexitalongsuchatypeguard,anewtypedtraceisrecordedoriginatingatthesideexitlocation,capturingthenewtypeoftheoperationinquestion.Representationspecialization:objects.InJavaScript,namelookupsemanticsarecomplexandpotentiallyexpensivebecausetheyincludefeatureslikeobjectinheritanceandeval.Toevaluateanobjectpropertyreadexpressionlikeo.x,theinterpretermustsearchthepropertymapofoandallofitsprototypesandparents.Propertymapscanbeimplementedwithdifferentdatastructures(e.g.,per-objecthashtablesorsharedhashtables),sothesearchprocessalsomustdispatchontherepresentationofeachobjectfoundduringsearch.TraceMonkeycansimplyobservetheresultofthesearchprocessandrecordthesimplestpossibleLIRtoaccessthepropertyvalue.Forexample,thesearchmightfindsthevalueofo.xintheprototypeofo,whichusesasharedhash-tablerepresen-tationthatplacesxinslot2ofapropertyvector.ThentherecordedcangenerateLIRthatreadso.xwithjusttwoorthreeloads:onetogettheprototype,possiblyonetogetthepropertyvaluevector,andonemoretogetslot2fromthevector.Thisisavastsimplificationandspeedupcomparedtotheoriginalinterpretercode.Inheritancerelationshipsandobjectrepresentationscanchangeduringexecu-tion,sothesimplifiedcoderequiresguardinstructionsthatensuretheobjectrepresentationisthesame.InTraceMonkey,objects’rep-resentationsareassignedanintegerkeycalledtheobjectshape.Thus,theguardisasimpleequalitycheckontheobjectshape.Representationspecialization:numbers.JavaScripthasnointegertype,onlyaNumbertypethatisthesetof64-bitIEEE-754floating-pointernumbers(“doubles”).ButmanyJavaScriptoperators,inparticulararrayaccessesandbitwiseoperators,reallyoperateonintegers,sotheyfirstconvertthenumbertoaninteger,andthenconvertanyintegerresultbacktoadouble.1Clearly,aJavaScriptVMthatwantstobefastmustfindawaytooperateonintegersdirectlyandavoidtheseconversions.InTraceMonkey,wesupporttworepresentationsfornumbers:integersanddoubles.Theinterpreterusesintegerrepresentationsasmuchasitcan,switchingforresultsthatcanonlyberepresentedasdoubles.Whenatraceisstarted,somevaluesmaybeimportedandrepresentedasintegers.Someoperationsonintegersrequireguards.Forexample,addingtwointegerscanproduceavaluetoolargefortheintegerrepresentation.Functioninlining.LIRtracescancrossfunctionboundariesineitherdirection,achievingfunctioninlining.Moveinstructionsneedtoberecordedforfunctionentryandexittocopyargumentsinandreturnvaluesout.Thesemovestatementsarethenoptimizedawaybythecompilerusingcopypropagation.Inordertobeabletoreturntotheinterpreter,thetracemustalsogenerateLIRtorecordthatacallframehasbeenenteredandexited.TheframeentryandexitLIRsavesjustenoughinformationtoallowtheintepretercallstacktoberestoredlaterandismuchsimplerthantheinterpreter’sstandardcallcode.Ifthefunctionbeingenteredisnotconstant(whichinJavaScriptincludesanycallbyfunctionname),therecordermustalsoemitLIRtoguardthatthefunctionisthesame.Guardsandsideexits.Eachoptimizationdescribedaboverequiresoneormoreguardstoverifytheassumptionsmadeindoingtheoptimization.AguardisjustagroupofLIRinstructionsthatperformsatestandconditionalexit.Theexitbranchestoasideexit,asmalloff-tracepieceofLIRthatreturnsapointertoastructurethatdescribesthereasonfortheexitalongwiththeinterpreterPCattheexitpointandanyotherdataneededtorestoretheinterpreter’sstatestructures.Aborts.SomeconstructsaredifficulttorecordinLIRtraces.Forexample,evalorcallstoexternalfunctionscanchangetheprogramstateinunpredictableways,makingitdifficultforthetracertoknowthecurrenttypemapinordertocontinuetracing.Atracingimplementationcanalsohaveanynumberofotherlimi-tations,e.g.,asmall-memorydevicemaylimitthelengthoftraces.Whenanysituationoccursthatpreventstheimplementationfromcontinuingtracerecording,theimplementationabortstracerecord-ingandreturnstothetracemonitor.3.2TraceTreesEspeciallysimpleloops,namelythosewherecontrolflow,valuetypes,valuerepresentations,andinlinedfunctionsareallinvariant,canberepresentedbyasingletrace.Butmostloopshaveatleastsomevariation,andsotheprogramwilltakesideexitsfromthemaintrace.Whenasideexitbecomeshot,TraceMonkeystartsanewbranchtracefromthatpointandpatchesthesideexittojumpdirectlytothattrace.Inthisway,asingletraceexpandsondemandtoasingle-entry,multiple-exittracetree.Thissectionexplainshowtracetreesareformedduringexecu-tion.Thegoalistoformtracetreesduringexecutionthatcoverallthehotpathsoftheprogram.1Arraysareactuallyworsethanthis:iftheindexvalueisanumber,itmustbeconvertedfromadoubletoastringforthepropertyaccessoperator,andthentoanintegerinternallytothearrayimplementation.Startingatree.Treetreesalwaysstartatloopheaders,becausetheyareanaturalplacetolookforhotpaths.InTraceMonkey,loopheadersareeasytodetect–thebytecodecompilerensuresthatabytecodeisaloopheaderiffitisthetargetofabackwardbranch.TraceMonkeystartsatreewhenagivenloopheaderhasbeenexe-cutedacertainnumberoftimes(2inthecurrentimplementation).Startingatreejustmeansstartingrecordingatraceforthecurrentpointandtypemapandmarkingthetraceastherootofatree.Eachtreeisassociatedwithaloopheaderandtypemap,sotheremaybeseveraltreesforagivenloopheader.Closingtheloop.Tracerecordingcanendinseveralways.Ideally,thetracereachestheloopheaderwhereitstartedwiththesametypemapasonentry.Thisiscalledatype-stableloopiteration.Inthiscase,theendofthetracecanjumprighttothebeginning,asallthevaluerepresentationsareexactlyasneededtoenterthetrace.Thejumpcanevenskiptheusualcodethatwouldcopyoutthestateattheendofthetraceandcopyitbackintothetraceactivationrecordtoenteratrace.Incertaincasesthetracemightreachtheloopheaderwithadifferenttypemap.Thisscenarioissometimeobservedforthefirstiterationofaloop.Somevariablesinsidetheloopmightinitiallybeundefined,beforetheyaresettoaconcretetypeduringthefirstloopiteration.Whenrecordingsuchaniteration,therecordercannotlinkthetracebacktoitsownloopheadersinceitistype-unstable.Instead,theiterationisterminatedwithasideexitthatwillalwaysfailandreturntotheinterpreter.Atthesametimeanewtraceisrecordedwiththenewtypemap.Everytimeanadditionaltype-unstabletraceisaddedtoaregion,itsexittypemapiscomparedtotheentrymapofallexistingtracesincasetheycomplementeachother.Withthisapproachweareabletocovertype-unstableloopiterationsaslongtheyeventuallyformastableequilibrium.Finally,thetracemightexittheloopbeforereachingtheloopheader,forexamplebecauseexecutionreachesabreakorreturnstatement.Inthiscase,theVMsimplyendsthetracewithanexittothetracemonitor.Asmentionedpreviously,wemayspeculativelychosetorep-resentcertainNumber-typedvaluesasintegersontrace.WedosowhenweobservethatNumber-typedvariablescontainanintegervalueattraceentry.Ifduringtracerecordingthevariableisunex-pectedlyassignedanon-integervalue,wehavetowidenthetypeofthevariabletoadouble.Asaresult,therecordedtracebecomesinherentlytype-unstablesinceitstartswithanintegervaluebutendswithadoublevalue.Thisrepresentsamis-speculation,sinceattraceentrywespecializedtheNumber-typedvaluetoaninteger,assumingthatattheloopedgewewouldagainfindanintegervalueinthevariable,allowingustoclosetheloop.Toavoidfuturespec-ulativefailuresinvolvingthisvariable,andtoobtainatype-stabletracewenotethefactthatthevariableinquestionasbeenobservedtosometimesholdnon-integervaluesinanadvisorydatastructurewhichwecallthe“oracle”.Whencompilingloops,weconsulttheoraclebeforespecializ-ingvaluestointegers.Speculationtowardsintegersisperformedonlyifnoadverseinformationisknowntotheoracleaboutthatparticularvariable.Wheneverweaccidentallycompilealoopthatistype-unstableduetomis-speculationofaNumber-typedvari-able,weimmediatelytriggertherecordingofanewtrace,whichbasedonthenowupdatedoracleinformationwillstartwithadou-blevalueandthusbecometypestable.Extendingatree.Sideexitsleadtodifferentpathsthroughtheloop,orpathswithdifferenttypesorrepresentations.Thus,tocompletelycovertheloop,theVMmustrecordtracesstartingatallsideexits.Thesetracesarerecordedmuchlikeroottraces:thereisacounterforeachsideexit,andwhenthecounterreachesahotnessthreshold,recordingstarts.Recordingstopsexactlyasfortheroottrace,usingtheloopheaderoftheroottraceasthetargettoreach.Ourimplementationdoesnotextendatallsideexits.Itextendsonlyifthesideexitisforacontrol-flowbranch,andonlyifthesideexitdoesnotleavetheloop.Inparticularwedonotwanttoextendatracetreealongapaththatleadstoanouterloop,becausewewanttocoversuchpathsinanoutertreethroughtreenesting.3.3BlacklistingSometimes,aprogramfollowsapaththatcannotbecompiledintoatrace,usuallybecauseoflimitationsintheimplementation.TraceMonkeydoesnotcurrentlysupportrecordingthrowingandcatchingofarbitraryexceptions.Thisdesigntradeoffwaschosen,becauseexceptionsareusuallyrareinJavaScript.However,ifaprogramoptstouseexceptionsintensively,wewouldsuddenlyincurapunishingruntimeoverheadifwerepeatedlytrytorecordatraceforthispathandrepeatedlyfailtodoso,sinceweaborttracingeverytimeweobserveanexceptionbeingthrown.Asaresult,ifahotloopcontainstracesthatalwaysfail,theVMcouldpotentiallyrunmuchmoreslowlythanthebaseinterpreter:theVMrepeatedlyspendstimetryingtorecordtraces,butisneverabletorunany.Toavoidthisproblem,whenevertheVMisabouttostarttracing,itmusttrytopredictwhetheritwillfinishthetrace.Ourpredictionalgorithmisbasedonblacklistingtracesthathavebeentriedandfailed.WhentheVMfailstofinishatracestart-ingatagivenpoint,theVMrecordsthatafailurehasoccurred.TheVMalsosetsacountersothatitwillnottrytorecordatracestartingatthatpointuntilitispassedafewmoretimes(32inourimple-mentation).Thisbackoffcountergivestemporaryconditionsthatpreventtracingachancetoend.Forexample,aloopmaybehavedifferentlyduringstartupthanduringitssteady-stateexecution.Af-teragivennumberoffailures(2inourimplementation),theVMmarksthefragmentasblacklisted,whichmeanstheVMwillneveragainstartrecordingatthatpoint.Afterimplementingthisbasicstrategy,weobservedthatforsmallloopsthatgetblacklisted,thesystemcanspendanoticeableamountoftimejustfindingtheloopfragmentanddeterminingthatithasbeenblacklisted.Wenowavoidthatproblembypatchingthebytecode.Wedefineanextrano-opbytecodethatindicatesaloopheader.TheVMcallsintothetracemonitoreverytimetheinter-preterexecutesaloopheaderno-op.Toblacklistafragment,wesimplyreplacetheloopheaderno-opwitharegularno-op.Thus,theinterpreterwillneveragainevencallintothetracemonitor.Thereisarelatedproblemwehavenotyetsolved,whichoccurswhenaloopmeetsalloftheseconditions:•TheVMcanformatleastoneroottracefortheloop.•ThereisatleastonehotsideexitforwhichtheVMcannotcompleteatrace.•Theloopbodyisshort.Inthiscase,theVMwillrepeatedlypasstheloopheader,searchforatrace,findit,executeit,andfallbacktotheinterpreter.Withashortloopbody,theoverheadoffindingandcallingthetraceishigh,andcausesperformancetobeevenslowerthanthebasicinterpreter.Sofar,inthissituationwehaveimprovedtheimplementationsothattheVMcancompletethebranchtrace.Butitishardtoguaranteethatthissituationwillneverhappen.Asfuturework,thissituationcouldbeavoidedbydetectingandblacklistingloopsforwhichtheaveragetracecallexecutesfewbytecodesbeforereturningtotheinterpreter.4.NestedTraceTreeFormationFigure7showsbasictracetreecompilation(11)appliedtoanestedloopwheretheinnerloopcontainstwopaths.Usually,theinnerloop(withheaderati2)becomeshotfirst,andatracetreeisrootedatthatpoint.Forexample,thefirstrecordedtracemaybeacycleTTrunk
TraceTree
AnchorTrace
AnchorBranch
TraceGuardSide
ExitFigure5.Atreewithtwotraces,atrunktraceandonebranchtrace.Thetrunktracecontainsaguardtowhichabranchtracewasattached.Thebranchtracecontainaguardthatmayfailandtriggerasideexit.Boththetrunkandthebranchtraceloopbacktothetreeanchor,whichisthebeginningofthetracetree.Trace
2Trace
1Trace
2Trace
1ClosedLinkedLinkedLinkedNumberNumberStringStringStringStringBooleanTrace
2Trace
1Trace
3LinkedLinkedLinkedClosedNumberNumberNumberBooleanNumberBooleanNumberBoolean(a)(b)(c)Figure6.Wehandletype-unstableloopsbyallowingtracestocompilethatcannotloopbacktothemselvesduetoatypemis-match.Assuchtracesaccumulate,weattempttoconnecttheirloopedgestoformgroupsoftracetreesthatcanexecutewithouthavingtoside-exittotheinterpretertocoveroddtypecases.Thisispar-ticularlyimportantfornestedtracetreeswhereanoutertreetriestocallaninnertree(orinthiscaseaforestofinnertrees),sinceinnerloopsfrequentlyhaveinitiallyundefinedvalueswhichchangetypetoaconcretevalueafterthefirstiteration.throughtheinnerloop,{i2,i3,i5,α}.Theαsymbolisusedtoindicatethatthetraceloopsbackthetreeanchor.Whenexecutionleavestheinnerloop,thebasicdesignhastwochoices.First,thesystemcanstoptracingandgiveuponcompilingtheouterloop,clearlyanundesirablesolution.Theotherchoiceistocontinuetracing,compilingtracesfortheouterloopinsidetheinnerloop’stracetree.Forexample,theprogrammightexitati5andrecordabranchtracethatincorporatestheouterloop:{i5,i7,i1,i6,i7,i1,α}.Later,theprogrammighttaketheotherbranchati2andthenexit,recordinganotherbranchtraceincorporatingtheouterloop:{i2,i4,i5,i7,i1,i6,i7,i1,α}.Thus,theouterloopisrecordedandcompiledtwice,andbothcopiesmustberetainedinthetracecache.i2i3i4i5i1i6i7t1t2Tree
CallOuter
TreeNested
TreeExit
Guard(a)(b)Figure7.Controlflowgraphofanestedloopwithanifstatementinsidetheinnermostloop(a).Aninnertreecapturestheinnerloop,andisnestedinsideanoutertreewhich“calls”theinnertree.Theinnertreereturnstotheoutertreeonceitexitsalongitsloopconditionguard(b).Ingeneral,ifloopsarenestedtodepthk,andeachloophasnpaths(ongeometricaverage),thisna¨ıvestrategyyieldsO(nk)traces,whichcaneasilyfillthetracecache.Inordertoexecuteprogramswithnestedloopsefficiently,atracingsystemneedsatechniqueforcoveringthenestedloopswithnativecodewithoutexponentialtraceduplication.4.1NestingAlgorithmThekeyinsightisthatifeachloopisrepresentedbyitsowntracetree,thecodeforeachloopcanbecontainedonlyinitsowntree,andouterlooppathswillnotbeduplicated.Anotherkeyfactisthatwearenottracingarbitrarybytecodesthatmighthaveirreduceablecontrolflowgraphs,butratherbytecodesproducedbyacompilerforalanguagewithstructuredcontrolflow.Thus,giventwoloopedges,thesystemcaneasilydeterminewhethertheyarenestedandwhichistheinnerloop.Usingthisknowledge,thesystemcancompileinnerandouterloopsseparately,andmaketheouterloop’stracescalltheinnerloop’stracetree.Thealgorithmforbuildingnestedtracetreesisasfollows.Westarttracingatloopheadersexactlyasinthebasictracingsystem.Whenweexitaloop(detectedbycomparingtheinterpreterPCwiththerangegivenbytheloopedge),westopthetrace.ThekeystepofthealgorithmoccurswhenwearerecordingatraceforloopLR(Rforloopbeingrecorded)andwereachtheheaderofadifferentloopLO(Oforotherloop).NotethatLOmustbeaninnerloopofLRbecausewestopthetracewhenweexitaloop.•IfLOhasatype-matchingcompiledtracetree,wecallLOasanestedtracetree.Ifthecallsucceeds,thenwerecordthecallinthetraceforLR.Onfutureexecutions,thetraceforLRwillcalltheinnertracedirectly.•IfLOdoesnothaveatype-matchingcompiledtracetreeyet,wehavetoobtainitbeforeweareabletoproceed.Inordertodothis,wesimplyabortrecordingthefirsttrace.Thetracemonitorwillseetheinnerloopheader,andwillimmediatelystartrecordingtheinnerloop.2Ifalltheloopsinanestaretype-stable,thenloopnestingcreatesnoduplication.Otherwise,ifloopsarenestedtoadepthk,andeach2Insteadofabortingtheouterrecording,wecouldprincipallymerelysus-pendtherecording,butthatwouldrequiretheimplementationtobeabletorecordseveraltracessimultaneously,complicatingtheimplementation,whilesavingonlyafewiterationsintheinterpreter.i2i3i1i6i4i5t2t1t4Exit
GuardNested
TreeFigure8.Controlflowgraphofaloopwithtwonestedloops(left)anditsnestedtracetreeconfiguration(right).Theoutertreecallsthetwoinnernestedtracetreesandplacesguardsattheirsideexitlocations.loopisenteredwithmdifferenttypemaps(ongeometricaverage),thenwecompileO(mk)copiesoftheinnermostloop.Aslongasmiscloseto1,theresultingtracetreeswillbetractable.Animportantdetailisthatthecalltotheinnertracetreemustactlikeafunctioncallsite:itmustreturntothesamepointeverytime.Thegoalofnestingistomakeinnerandouterloopsindependent;thuswhentheinnertreeiscalled,itmustexittothesamepointintheoutertreeeverytimewiththesametypemap.Becausewecannotactuallyguaranteethisproperty,wemustguardonitafterthecall,andsideexitifthepropertydoesnothold.Acommonreasonfortheinnertreenottoreturntothesamepointwouldbeiftheinnertreetookanewsideexitforwhichithadnevercompiledatrace.Atthispoint,theinterpreterPCisintheinnertree,sowecannotcontinuerecordingorexecutingtheoutertree.Ifthishappensduringrecording,weaborttheoutertrace,togivetheinnertreeachancetofinishgrowing.Afutureexecutionoftheoutertreewouldthenbeabletoproperlyfinishandrecordacalltotheinnertree.Ifaninnertreesideexithappensduringexecutionofacompiledtracefortheoutertree,wesimplyexittheoutertraceandstartrecordinganewbranchintheinnertree.4.2BlacklistingwithNestingTheblacklistingalgorithmneedsmodificationtoworkwellwithnesting.Theproblemisthatouterlooptracesoftenabortduringstartup(becausetheinnertreeisnotavailableortakesasideexit),whichwouldleadtotheirbeingquicklyblacklistedbythebasicalgorithm.Thekeyobservationisthatwhenanoutertraceabortsbecausetheinnertreeisnotready,thisisprobablyatemporarycondition.Thus,weshouldnotcountsuchabortstowardblacklistingaslongasweareabletobuildupmoretracesfortheinnertree.Inourimplementation,whenanoutertreeabortsontheinnertree,weincrementtheoutertree’sblacklistcounterasusualandbackoffoncompilingit.Whentheinnertreefinishesatrace,wedecrementtheblacklistcounterontheouterloop,“forgiving”theouterloopforabortingpreviously.Wealsoundothebackoffsothattheoutertreecanstartimmediatelytryingtocompilethenexttimewereachit.5.TraceTreeOptimizationThissectionexplainshowarecordedtraceistranslatedtoanoptimizedmachinecodetrace.Thetracecompilationsubsystem,NANOJIT,isseparatefromtheVMandcanbeusedforotherapplications.5.1OptimizationsBecausetracesareinSSAformandhavenojoinpointsorφ-nodes,certainoptimizationsareeasytoimplement.Inordertogetgoodstartupperformance,theoptimizationsmustrunquickly,sowechoseasmallsetofoptimizations.Weimplementedtheoptimizationsaspipelinedfilterssothattheycanbeturnedonandoffindependently,andyetallruninjusttwolooppassesoverthetrace:oneforwardandonebackward.EverytimethetracerecorderemitsaLIRinstruction,thein-structionisimmediatelypassedtothefirstfilterintheforwardpipeline.Thus,forwardfilteroptimizationsareperformedasthetraceisrecorded.Eachfiltermaypasseachinstructiontothenextfilterunchanged,writeadifferentinstructiontothenextfilter,orwritenoinstructionatall.Forexample,theconstantfoldingfiltercanreplaceamultiplyinstructionlikev13:=mul3,1000withaconstantinstructionv13=3000.Wecurrentlyapplyfourforwardfilters:•OnISAswithoutfloating-pointinstructions,asoft-floatfilterconvertsfloating-pointLIRinstructionstosequencesofintegerinstructions.•CSE(constantsubexpressionelimination),•expressionsimplification,includingconstantfoldingandafewalgebraicidentities(e.g.,a−a=0),and•sourcelanguagesemantic-specificexpressionsimplification,primarilyalgebraicidentitiesthatallowDOUBLEtobereplacedwithINT.Forexample,LIRthatconvertsanINTtoaDOUBLEandthenbackagainwouldberemovedbythisfilter.Whentracerecordingiscompleted,nanojitrunsthebackwardoptimizationfilters.Theseareusedforoptimizationsthatrequirebackwardprogramanalysis.Whenrunningthebackwardfilters,nanojitreadsoneLIRinstructionatatime,andthereadsarepassedthroughthepipeline.Wecurrentlyapplythreebackwardfilters:•Deaddata-stackstoreelimination.TheLIRtraceencodesmanystorestolocationsintheinterpreterstack.Butthesevaluesareneverreadbackbeforeexitingthetrace(bytheinterpreteroranothertrace).Thus,storestothestackthatareoverwrittenbeforethenextexitaredead.Storestolocationsthatareoffthetopoftheinterpreterstackatfutureexitsarealsodead.•Deadcall-stackstoreelimination.Thisisthesameoptimizationasabove,exceptappliedtotheinterpreter’scallstackusedforfunctioncallinlining.•Deadcodeelimination.Thiseliminatesanyoperationthatstorestoavaluethatisneverused.AfteraLIRinstructionissuccessfullyread(“pulled”)fromthebackwardfilterpipeline,nanojit’scodegeneratoremitsnativemachineinstruction(s)forit.5.2RegisterAllocationWeuseasimplegreedyregisterallocatorthatmakesasinglebackwardpassoverthetrace(itisintegratedwiththecodegen-erator).Bythetimetheallocatorhasreachedaninstructionlikev3=addv1,v2,ithasalreadyassignedaregistertov3.Ifv1andv2havenotyetbeenassignedregisters,theallocatorassignsafreeregistertoeach.Iftherearenofreeregisters,avalueisselectedforspilling.Weuseaclassheuristicthatselectsthe“oldest”register-carriedvalue(6).TheheuristicconsidersthesetRofvaluesvinregistersimme-diatelyafterthecurrentinstructionforspilling.Letvmbethelastinstructionbeforethecurrentwhereeachvisreferredto.ThentheTagJSTypeDescriptionxx1number31-bitintegerrepresentation000objectpointertoJSObjecthandle010numberpointertodoublehandle100stringpointertoJSStringhandle110booleanenumerationfornull,undefined,true,falsenull,orundefinedFigure9.TaggedvaluesintheSpiderMonkeyJSinterpreter.Testingtags,unboxing(extractingtheuntaggedvalue)andboxing(creatingtaggedvalues)aresignificantcosts.Avoidingthesecostsisakeybenefitoftracing.heuristicselectsvwithminimumvm.Themotivationisthatthisfreesuparegisterforaslongaspossiblegivenasinglespill.Ifweneedtospillavaluevsatthispoint,wegeneratetherestorecodejustafterthecodeforthecurrentinstruction.Thecorrespondingspillcodeisgeneratedjustafterthelastpointwherevswasused.Theregisterthatwasassignedtovsismarkedfreefortheprecedingcode,becausethatregistercannowbeusedfreelywithoutaffectingthefollowingcode6.ImplementationTodemonstratetheeffectivenessofourapproach,wehaveim-plementedatrace-baseddynamiccompilerfortheSpiderMonkeyJavaScriptVirtualMachine(4).SpiderMonkeyistheJavaScriptVMembeddedinMozilla’sFirefoxopen-sourcewebbrowser(2),whichisusedbymorethan200millionusersworld-wide.ThecoreofSpiderMonkeyisabytecodeinterpreterimplementedinC++.InSpiderMonkey,allJavaScriptvaluesarerepresentedbythetypejsval.Ajsvalismachinewordinwhichuptothe3oftheleastsignificantbitsareatypetag,andtheremainingbitsaredata.SeeFigure6fordetails.AllpointerscontainedinjsvalspointtoGC-controlledblocksalignedon8-byteboundaries.JavaScriptobjectvaluesaremappingsofstring-valuedpropertynamestoarbitraryvalues.TheyarerepresentedinoneoftwowaysinSpiderMonkey.Mostobjectsarerepresentedbyasharedstruc-turaldescription,calledtheobjectshape,thatmapspropertynamestoarrayindexesusingahashtable.Theobjectstoresapointertotheshapeandthearrayofitsownpropertyvalues.Objectswithlarge,uniquesetsofpropertynamesstoretheirpropertiesdirectlyinahashtable.Thegarbagecollectorisanexact,non-generational,stop-the-worldmark-and-sweepcollector.IntherestofthissectionwediscusskeyareasoftheTraceMon-keyimplementation.6.1CallingCompiledTracesCompiledtracesarestoredinatracecache,indexedbyintepreterPCandtypemap.Tracesarecompiledsothattheymaybecalledasfunctionsusingstandardnativecallingconventions(e.g.,FASTCALLonx86).Theinterpretermusthitaloopedgeandenterthemonitorinordertocallanativetraceforthefirsttime.Themonitorcomputesthecurrenttypemap,checksthetracecacheforatraceforthecurrentPCandtypemap,andifitfindsone,executesthetrace.Toexecuteatrace,themonitormustbuildatraceactivationrecordcontainingimportedlocalandglobalvariables,temporarystackspace,andspaceforargumentstonativecalls.Thelocalandglobalvaluesarethencopiedfromtheinterpreterstatetothetraceactivationrecord.Then,thetraceiscalledlikeanormalCfunctionpointer.Whenatracecallreturns,themonitorrestorestheinterpreterstate.First,themonitorchecksthereasonforthetraceexitandappliesblacklistingifneeded.Then,itpopsorsynthesizesinter-preterJavaScriptcallstackframesasneeded.Finally,itcopiestheimportedvariablesbackfromthetraceactivationrecordtothein-terpreterstate.Atleastinthecurrentimplementation,thesestepshaveanon-negligibleruntimecost,sominimizingthenumberofinterpreter-to-traceandtrace-to-interpretertransitionsisessentialforperfor-mance.(seealsoSection3.3).Ourexperiments(seeFigure12)showthatforprogramswecantracewellsuchtransitionshap-peninfrequentlyandhencedonotcontributesignificantlytototalruntime.Inafewprograms,wherethesystemispreventedfromrecordingbranchtracesforhotsideexitsbyaborts,thiscostcanrisetoupto10%oftotalexecutiontime.6.2TraceStitchingTransitionsfromatracetoabranchtraceatasideexitavoidthecostsofcallingtracesfromthemonitor,inafeaturecalledtracestitching.Atasideexit,theexitingtraceonlyneedstowriteliveregister-carriedvaluesbacktoitstraceactivationrecord.Inourim-plementation,identicaltypemapsyieldidenticalactivationrecordlayouts,sothetraceactivationrecordcanbereusedimmediatelybythebranchtrace.Inprogramswithbranchytracetreeswithsmalltraces,tracestitchinghasanoticeablecost.AlthoughwritingtomemoryandthensoonreadingbackwouldbeexpectedtohaveahighL1cachehitrate,forsmalltracestheincreasedinstructioncounthasanoticeablecost.Also,ifthewritesandreadsareverycloseinthedynamicinstructionstream,wehavefoundthatcurrentx86processorsoftenincurpenaltiesof6cyclesormore(e.g.,iftheinstructionsusedifferentbaseregisterswithequalvalues,theprocessormaynotbeabletodetectthattheaddressesarethesamerightaway).Thealternatesolutionistorecompileanentiretracetree,thusachievinginter-traceregisterallocation(10).Thedisadvantageisthattreerecompilationtakestimequadraticinthenumberoftraces.Webelievethatthecostofrecompilingatracetreeeverytimeabranchisaddedwouldbeprohibitive.Thatproblemmightbemitigatedbyrecompilingonlyatcertainpoints,oronlyforveryhot,stabletrees.Inthefuture,multicorehardwareisexpectedtobecommon,makingbackgroundtreerecompilationattractive.Inacloselyre-latedproject(13)backgroundrecompilationyieldedspeedupsofupto1.25xonbenchmarkswithmanybranchtraces.WeplantoapplythistechniquetoTraceMonkeyasfuturework.6.3TraceRecordingThejobofthetracerecorderistoemitLIRwithidenticalsemanticstothecurrentlyrunninginterpreterbytecodetrace.Agoodimple-mentationshouldhavelowimpactonnon-tracinginterpreterper-formanceandaconvenientwayforimplementerstomaintainse-manticequivalence.Inourimplementation,theonlydirectmodificationtotheinter-preterisacalltothetracemonitoratloopedges.Inourbenchmarkresults(seeFigure12)thetotaltimespentinthemonitor(forallactivities)isusuallylessthan5%,soweconsidertheinterpreterimpactrequirementmet.Incrementingtheloophitcounterisex-pensivebecauseitrequiresustolookuptheloopinthetracecache,butwehavetunedourloopstobecomehotandtraceveryquickly(ontheseconditeration).Thehitcounterimplementationcouldbeimproved,whichmightgiveusasmallincreaseinoverallperfor-mance,aswellasmoreflexibilitywithtuninghotnessthresholds.Oncealoopisblacklistedwenevercallintothetracemonitorforthatloop(seeSection3.3).Recordingisactivatedbyapointerswapthatsetstheinter-preter’sdispatchtabletocallasingle“interrupt”routineforev-erybytecode.Theinterruptroutinefirstcallsabytecode-specificrecordingroutine.Then,itturnsoffrecordingifnecessary(e.g.,thetraceended).Finally,itjumpstothestandardinterpreterbyte-codeimplementation.Somebytecodeshaveeffectsonthetypemapthatcannotbepredictedbeforeexecutingthebytecode(e.g.,call-ingString.charCodeAt,whichreturnsanintegerorNaNiftheindexargumentisoutofrange).Forthese,wearrangefortheinter-pretertocallintotherecorderagainafterexecutingthebytecode.Sincesuchhooksarerelativelyrare,weembedthemdirectlyintotheinterpreter,withanadditionalruntimechecktoseewhetherarecorderiscurrentlyactive.Whileseparatingtheinterpreterfromtherecorderreducesindi-vidualcodecomplexity,italsorequirescarefulimplementationandextensivetestingtoachievesemanticequivalence.InsomecasesachievingthisequivalenceisdifficultsinceSpi-derMonkeyfollowsafat-bytecodedesign,whichwasfoundtobebeneficialtopureinterpreterperformance.Infat-bytecodedesigns,individualbytecodescanimplementcomplexprocessing(e.g.,thegetpropbytecode,whichimple-mentsfullJavaScriptpropertyvalueaccess,includingspecialcasesforcachedanddensearrayaccess).Fatbytecodeshavetwoadvantages:fewerbytecodesmeanslowerdispatchcost,andbiggerbytecodeimplementationsgivethecompilermoreopportunitiestooptimizetheinterpreter.FatbytecodesareaproblemforTraceMonkeybecausetheyrequiretherecordertoreimplementthesamespecialcaselogicinthesameway.Also,theadvantagesarereducedbecause(a)dispatchcostsareeliminatedentirelyincompiledtraces,(b)thetracescontainonlyonespecialcase,nottheinterpreter’slargechunkofcode,and(c)TraceMonkeyspendslesstimerunningthebaseinterpreter.Onewaywehavemitigatedtheseproblemsisbyimplementingcertaincomplexbytecodesintherecorderassequencesofsimplebytecodes.Expressingtheoriginalsemanticsthiswayisnottoodif-ficult,andrecordingsimplebytecodesismucheasier.Thisenablesustoretaintheadvantagesoffatbytecodeswhileavoidingsomeoftheirproblemsfortracerecording.Thisisparticularlyeffectiveforfatbytecodesthatrecursebackintotheinterpreter,forexampletoconvertanobjectintoaprimitivevaluebyinvokingawell-knownmethodontheobject,sinceitletsusinlinethisfunctioncall.Itisimportanttonotethatwesplitfatopcodesintothinnerop-codesonlyduringrecording.Whenrunningpurelyinterpretatively(i.e.codethathasbeenblacklisted),theinterpreterdirectlyandef-ficientlyexecutesthefatopcodes.6.4PreemptionSpiderMonkey,likemanyVMs,needstopreempttheuserprogramperiodically.ThemainreasonsaretopreventinfinitelyloopingscriptsfromlockingupthehostsystemandtoscheduleGC.Intheinterpreter,thishadbeenimplementedbysettinga“pre-emptnow”flagthatwascheckedoneverybackwardjump.ThisstrategycarriedoverintoTraceMonkey:theVMinsertsaguardonthepreemptionflagateveryloopedge.Wemeasuredlessthana1%increaseinruntimeonmostbenchmarksforthisextraguard.Inpractice,thecostisdetectableonlyforprogramswithveryshortloops.Wetestedandrejectedasolutionthatavoidedtheguardsbycompilingtheloopedgeasanunconditionaljump,andpatchingthejumptargettoanexitroutinewhenpreemptionisrequired.Thissolutioncanmakethenormalcaseslightlyfaster,butthenpreemptionbecomesveryslow.Theimplementationwasalsoverycomplex,especiallytryingtorestartexecutionafterthepreemption.6.5CallingExternalFunctionsLikemostinterpreters,SpiderMonkeyhasaforeignfunctioninter-face(FFI)thatallowsittocallCbuiltinsandhostsystemfunctions(e.g.,webbrowsercontrolandDOMaccess).TheFFIhasastan-dardsignatureforJS-callablefunctions,thekeyargumentofwhichisanarrayofboxedvalues.ExternalfunctionscalledthroughtheFFIinteractwiththeprogramstatethroughaninterpreterAPI(e.g.,toreadapropertyfromanargument).Therearealsocertaininter-preterbuiltinsthatdonotusetheFFI,butinteractwiththeprogramstateinthesameway,suchastheCallIteratorNextfunctionusedwithiteratorobjects.TraceMonkeymustsupportthisFFIinordertospeedupcodethatinteractswiththehostsysteminsidehotloops.CallingexternalfunctionsfromTraceMonkeyispotentiallydif-ficultbecausetracesdonotupdatetheinterpreterstateuntilexit-ing.Inparticular,externalfunctionsmayneedthecallstackortheglobalvariables,buttheymaybeoutofdate.Fortheout-of-datecallstackproblem,werefactoredsomeoftheinterpreterAPIimplementationfunctionstore-materializetheinterpretercallstackondemand.WedevelopedaC++staticanalysisandannotatedsomeinter-preterfunctionsinordertoverifythatthecallstackisrefreshedatanypointitneedstobeused.Inordertoaccessthecallstack,afunctionmustbeannotatedaseitherFORCESSTACKorRE-QUIRESSTACK.TheseannotationsarealsorequiredinordertocallREQUIRESSTACKfunctions,whicharepresumedtoaccessthecallstacktransitively.FORCESSTACKisatrustedannotation,appliedtoonly5functions,thatmeansthefunctionrefreshesthecallstack.REQUIRESSTACKisanuntrustedannotationthatmeansthefunc-tionmayonlybecalledifthecallstackhasalreadybeenrefreshed.Similarly,wedetectwhenhostfunctionsattempttodirectlyreadorwriteglobalvariables,andforcethecurrentlyrunningtracetosideexit.Thisisnecessarysincewecacheandunboxglobalvariablesintotheactivationrecordduringtraceexecution.Sincebothcall-stackaccessandglobalvariableaccessarerarelyperformedbyhostfunctions,performanceisnotsignificantlyaffectedbythesesafetymechanisms.Anotherproblemisthatexternalfunctionscanreentertheinter-preterbycallingscripts,whichinturnagainmightwanttoaccessthecallstackorglobalvariables.Toaddressthisproblem,wemadetheVMsetaflagwhenevertheinterpreterisreenteredwhileacom-piledtraceisrunning.Everycalltoanexternalfunctionthenchecksthisflagandexitsthetraceimmediatelyafterreturningfromtheexternalfunctioncallifitisset.Therearemanyexternalfunctionsthatseldomorneverreenter,andtheycanbecalledwithoutproblem,andwillcausetraceexitonlyifnecessary.TheFFI’sboxedvaluearrayrequirementhasaperformancecost,sowedefinedanewFFIthatallowsCfunctionstobean-notatedwiththeirargumenttypessothatthetracercancallthemdirectly,withoutunnecessaryargumentconversions.Currently,wedonotsupportcallingnativepropertygetandsetoverridefunctionsorDOMfunctionsdirectlyfromtrace.Supportisplannedfuturework.6.6CorrectnessDuringdevelopment,wehadaccesstoexistingJavaScripttestsuites,butmostofthemwerenotdesignedwithtracingVMsinmindandcontainedfewloops.OnetoolthathelpedusgreatlywasMozilla’sJavaScriptfuzztester,JSFUNFUZZ,whichgeneratesrandomJavaScriptprogramsbynestingrandomlanguageelements.WemodifiedJSFUNFUZZtogenerateloops,andalsototestmoreheavilycertainconstructswesuspectedwouldrevealflawsinourimplementation.Forexam-ple,wesuspectedbugsinTraceMonkey’shandlingoftype-unstable!"#$!"#%!"#&!"#'!"#(!"#)!"#*!"#+!"#,!"#$!!"#&-./012#3%4%56#&-.789:;#3%4,56#&-.9<=>9</2#3$4%56#<//2??.1@A<9=.>922?#3!4,56#<//2??.B<AAC0/;#3%4%56#<//2??.A18-=#3'4%56#<//2??.A?@2D2#3&4!56#1@>8:?.&1@>.1@>?.@A.1=>2#3%(4(56#1@>8:?.1@>?.@A.1=>2#3+4*56#1@>8:?.1@>E@?2.<A-#3%(4%56#1@>8:?.A?@2D2.1@>?#3%4*56#/8A>98FG8E.92/09?@D2#3$4!56#/9=:>8.<2?#3$4)56#/9=:>8.7-(#3%4&56#/9=:>8.?;<$#3(4,56#-<>2.B897<>.>8H2#3$4$56#-<>2.B897<>.5:<91#3$4!56#7<>;./89-@/#3'4,56#7<>;.:<9I<F.?07?#3(4,56#7<>;.?:2/>9<F.A897#3*4$56#92J25:.-A<#3'4%56#?>9@AJ.1<?2)'#3%4(56#?>9@AJ.B<?><#3$4(56#?>9@AJ.><J/F80-#3$4$56#?>9@AJ.0A:</C./8-2#3$4%56#?>9@AJ.D<F@-<>2.@A:0>#3$4,56#KA>29:92>#L<ID2#Figure11.Fractionofdynamicbytecodesexecutedbyinter-preterandonnativetraces.Thespeedupvs.interpreterisshowninparenthesesnexttoeachtest.Thefractionofbytecodesexe-cutedwhilerecordingistoosmalltoseeinthisfigure,exceptforcrypto-md5,wherefully3%ofbytecodesareexecutedwhilerecording.Inmostofthetests,almostallthebytecodesareexe-cutedbycompiledtraces.Threeofthebenchmarksarenottracedatallandrunintheinterpreter.loopsandheavilybranchingcode,andaspecializedfuzztesterin-deedrevealedseveralregressionswhichwesubsequentlycorrected.7.EvaluationWeevaluatedourJavaScripttracingimplementationusingSun-Spider,theindustrystandardJavaScriptbenchmarksuite.SunSpi-derconsistsof26short-running(lessthan250ms,average26ms)JavaScriptprograms.ThisisinstarkcontrasttobenchmarksuitessuchasSpecJVM98(3)usedtoevaluatedesktopandserverJavaVMs.Manyprogramsinthosebenchmarksuselargedatasetsandexecuteforminutes.TheSunSpiderprogramscarryoutavarietyoftasks,primarily3drendering,bit-bashing,cryptographicencoding,mathkernels,andstringprocessing.AllexperimentswereperformedonaMacBookProwith2.2GHzCore2processorand2GBRAMrunningMacOS10.5.Benchmarkresults.Themainquestioniswhetherprogramsrunfasterwithtracing.Forthis,weranthestandardSunSpidertestdriver,whichstartsaJavaScriptinterpreter,loadsandrunseachprogramonceforwarmup,thenloadsandrunseachprogram10timesandreportstheaveragetimetakenbyeach.Weran4differ-entconfigurationsforcomparison:(a)SpiderMonkey,thebaselineinterpreter,(b)TraceMonkey,(d)SquirrelFishExtreme(SFX),thecall-threadedJavaScriptinterpreterusedinApple’sWebKit,and(e)V8,themethod-compilingJavaScriptVMfromGoogle.Figure10showstherelativespeedupsachievedbytracing,SFX,andV8againstthebaseline(SpiderMonkey).Tracingachievesthebestspeedupsininteger-heavybenchmarks,uptothe25xspeeduponbitops-bitwise-and.TraceMonkeyisthefastestVMon9ofthe26benchmarks(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).!"#"$!"$#"%!"%#"&'()*+,"-./"01"Figure10.Speedupvs.abaselineJavaScriptinterpreter(SpiderMonkey)forourtrace-basedJITcompiler,Apple’sSquirrelFishExtremeinlinethreadinginterpreterandGoogle’sV8JScompiler.Oursystemgeneratesparticularlyefficientcodeforprogramsthatbenefitmostfromtypespecialization,whichincludesSunSpiderBenchmarkprogramsthatperformbitmanipulation.Wetype-specializethecodeinquestiontouseintegerarithmetic,whichsubstantiallyimprovesperformance.Foroneofthebenchmarkprogramsweexecute25timesfasterthantheSpiderMonkeyinterpreter,andalmost5timesfasterthanV8andSFX.ForalargenumberofbenchmarksallthreeVMsproducesimilarresults.Weperformworstonbenchmarkprogramsthatwedonottraceandinsteadfallbackontotheinterpreter.Thisincludestherecursivebenchmarksaccess-binary-treesandcontrol-flow-recursive,forwhichwecurrentlydon’tgenerateanynativecode.Inparticular,thebitopsbenchmarksareshortprogramsthatper-formmanybitwiseoperations,soTraceMonkeycancovertheen-tireprogramwith1or2tracesthatoperateonintegers.TraceMon-keyrunsalltheotherprogramsinthissetalmostentirelyasnativecode.regexp-dnaisdominatedbyregularexpressionmatching,whichisimplementedinall3VMsbyaspecialregularexpressioncompiler.Thus,performanceonthisbenchmarkhaslittlerelationtothetracecompilationapproachdiscussedinthispaper.TraceMonkey’ssmallerspeedupsontheotherbenchmarkscanbeattributedtoafewspecificcauses:•Theimplementationdoesnotcurrentlytracerecursion,soTraceMonkeyachievesasmallspeedupornospeeduponbenchmarksthatuserecursionextensively:3d-cube,3d-raytrace,access-binary-trees,string-tagcloud,andcontrolflow-recursive.•TheimplementationdoesnotcurrentlytraceevalandsomeotherfunctionsimplementedinC.Becausedate-format-tofteanddate-format-xparbusesuchfunctionsintheirmainloops,wedonottracethem.•Theimplementationdoesnotcurrentlytracethroughregularexpressionreplaceoperations.Thereplacefunctioncanbepassedafunctionobjectusedtocomputethereplacementtext.Ourimplementationcurrentlydoesnottracefunctionscalledasreplacefunctions.Theruntimeofstring-unpack-codeisdominatedbysuchareplacecall.•Twoprogramstracewell,buthavealongcompilationtime.access-nbodyformsalargenumberoftraces(81).crypto-md5formsoneverylongtrace.Weexpecttoimproveperformanceonthisprogramsbyimprovingthecompilationspeedofnano-jit.•Someprogramstraceverywell,andspeedupcomparedtotheinterpreter,butarenotasfastasSFXand/orV8,namelybitops-bits-in-byte,bitops-nsieve-bits,access-fannkuch,access-nsieve,andcrypto-aes.Thereasonisnotclear,butalloftheseprogramshavenestedloopswithsmallbodies,sowesuspectthattheimplementationhasarela-tivelyhighcostforcallingnestedtraces.string-fastatraceswell,butitsruntimeisdominatedbystringprocessingbuiltins,whichareunaffectedbytracingandseemtobelessefficientinSpiderMonkeythaninthetwootherVMs.Detailedperformancemetrics.InFigure11weshowthefrac-tionofinstructionsinterpretedandthefractionofinstructionsexe-cutedasnativecode.Thisfigureshowsthatformanyprograms,weareabletoexecutealmostallthecodenatively.Figure12breaksdownthetotalexecutiontimeintofouractiv-ities:interpretingbytecodeswhilenotrecording,recordingtraces(includingtimetakentointerprettherecordedtrace),compilingtracestonativecode,andexecutingnativecodetraces.Thesedetailedmetricsallowustoestimateparametersforasimplemodeloftracingperformance.Theseestimatesshouldbeconsideredveryrough,asthevaluesobservedontheindividualbenchmarkshavelargestandarddeviations(ontheorderoftheLoopsTreesTracesAbortsFlushesTrees/LoopTraces/TreeTraces/LoopSpeedup3d-cube252729301.11.11.22.20x3d-morph588201.61.01.62.86x3d-raytrace10251001012.54.010.01.18xaccess-binary-trees00050---0.93xaccess-fannkuch1034572403.41.75.72.20xaccess-nbody81618502.01.12.34.19xaccess-nsieve368302.01.32.73.05xbitops-3bit-bits-in-byte222001.01.01.025.47xbitops-bits-in-byte334101.01.31.38.67xbitops-bitwise-and111001.01.01.025.20xbitops-nsieve-bits335001.01.71.72.75xcontrolflow-recursive00010---0.98xcrypto-aes5072781901.41.11.61.64xcrypto-md5445001.01.31.32.30xcrypto-sha15510001.02.02.05.95xdate-format-tofte334701.01.31.31.07xdate-format-xparb3311301.03.73.70.98xmath-cordic245102.01.32.54.92xmath-partial-sums244102.01.02.05.90xmath-spectral-norm152020001.31.01.37.12xregexp-dna222001.01.01.04.21xstring-base64357001.71.42.32.53xstring-fasta51115602.21.43.01.49xstring-tagcloud366502.01.02.01.09xstring-unpack-code4437001.09.39.31.20xstring-validate-input61013101.71.32.21.86xFigure13.DetailedtracerecordingstatisticsfortheSunSpiderbenchmarkset.mean).Weexcluderegexp-dnafromthefollowingcalculations,becausemostofitstimeisspentintheregularexpressionmatcher,whichhasmuchdifferentperformancecharacteristicsfromtheotherprograms.(Notethatthisonlymakesadifferenceofabout10%intheresults.)Dividingthetotalexecutiontimeinprocessorclockcyclesbythenumberofbytecodesexecutedinthebaseinterpretershowsthatonaverage,abytecodeexecutesinabout35cycles.Nativetracestakeabout9cyclesperbytecode,a3.9xspeedupovertheinterpreter.Usingsimilarcomputations,wefindthattracerecordingtakesabout3800cyclesperbytecode,andcompilation3150cyclesperbytecode.Hence,duringrecordingandcompilingtheVMrunsat1/200thespeedoftheinterpreter.Becauseitcosts6950cyclestocompileabytecode,andwesave26cycleseachtimethatcodeisrunnatively,webreakevenafterrunningatrace270times.TheotherVMswecomparedwithachieveanoverallspeedupof3.0xrelativetoourbaselineinterpreter.Ourestimatednativecodespeedupof3.9xissignificantlybetter.ThissuggeststhatourcompilationtechniquescangeneratemoreefficientnativecodethananyothercurrentJavaScriptVM.Theseestimatesalsoindicatethatourstartupperformancecouldbesubstantiallybetterifweimprovedthespeedoftracerecordingandcompilation.Theestimated200xslowdownforrecordingandcompilationisveryrough,andmaybeinfluencedbystartupfactorsintheinterpreter(e.g.,cachesthathavenotwarmedupyetduringrecording).Oneobservationsupportingthisconjectureisthatinthetracer,interpretedbytecodestakeabout180cyclestorun.Still,recordingandcompilationareclearlybothexpensive,andabetterimplementation,possiblyincludingredesignoftheLIRabstractsyntaxorencoding,wouldimprovestartupperformance.Ourperformanceresultsconfirmthattypespecializationusingtracetreessubstantiallyimprovesperformance.WeareabletooutperformthefastestavailableJavaScriptcompiler(V8)andthefastestavailableJavaScriptinlinethreadedinterpreter(SFX)on9of26benchmarks.8.RelatedWorkTraceoptimizationfordynamiclanguages.Theclosestareaofrelatedworkisonapplyingtraceoptimizationtotype-specializedynamiclanguages.Existingworksharestheideaofgeneratingtype-specializedcodespeculativelywithguardsalonginterpretertraces.Toourknowledge,Rigo’sPsyco(16)istheonlypublishedtype-specializingtracecompilerforadynamiclanguage(Python).Psycodoesnotattempttoidentifyhotloopsorinlinefunctioncalls.Instead,Psycotransformsloopstomutualrecursionbeforerunningandtracesalloperations.Pall’sLuaJITisaLuaVMindevelopmentthatusestracecom-pilationideas.(1).TherearenopublicationsonLuaJITbutthecre-atorhastoldusthatLuaJIThasasimilardesigntooursystem,butwillusealessaggressivetypespeculation(e.g.,usingafloating-pointrepresentationforallnumbervalues)anddoesnotgeneratenestedtracesfornestedloops.Generaltraceoptimization.GeneraltraceoptimizationhasalongerhistorythathastreatedmostlynativecodeandtypedlanguageslikeJava.Thus,thesesystemshavefocusedlessontypespecializationandmoreonotheroptimizations.Dynamo(7)byBalaetal,introducednativecodetracingasareplacementforprofile-guidedoptimization(PGO).AmajorgoalwastoperformPGOonlinesothattheprofilewasspecifictothecurrentexecution.Dynamousedloopheadersascandidatehottraces,butdidnottrytocreatelooptracesspecifically.TracetreeswereoriginallyproposedbyGaletal.(11)inthecontextofJava,astaticallytypedlanguage.Theirtracetreesac-tuallyinlinedpartsofouterloopswithintheinnerloops(because!"#$!"#%!"#&!"#'!"#(!!"#)*+,-./#0$1$23#)*+45678#0$1923#)*+6:;<6:,/#0(1$23#:,,/==+.>?:6;+<6//=#0!1923#:,,/==+@:??A-,8#0$1$23#:,,/==+?.5*;#0%1$23#:,,/==+?=>/B/#0)1!23#.><57=+).><+.><=+>?+.;</#0$C1C23#.><57=+.><=+>?+.;</#0'1D23#.><57=+.><E>=/+:?*#0$C1$23#.><57=+?=>/B/+.><=#0$1D23#,5?<65FG5E+6/,-6=>B/#0(1!23#,6;7<5+:/=#0(1&23#,6;7<5+4*C#0$1)23#,6;7<5+=8:(#0C1923#*:</+@564:<+<5H/#0(1(23#*:</+@564:<+27:6.#0(1!23#4:<8+,56*>,#0%1923#4:<8+7:6I:F+=-4=#0C1923#4:<8+=7/,<6:F+?564#0D1(23#6/J/27+*?:#0%1$23#=<6>?J+.:=/&%#0$1C23#=<6>?J+@:=<:#0(1C23#=<6>?J+<:J,F5-*#0(1(23#=<6>?J+-?7:,A+,5*/#0(1$23#=<6>?J+B:F>*:</+>?7-<#0(1923#K?</676/<#L5?><56#M/,56*#N547>F/#N:FF#O6:,/#M-?#O6:,/#Figure12.FractionoftimespentonmajorVMactivities.Thespeedupvs.interpreterisshowninparenthesesnexttoeachtest.MostprogramswheretheVMspendsthemajorityofitstimerun-ningnativecodehaveagoodspeedup.Recordingandcompilationcostscanbesubstantial;speedingupthosepartsoftheimplemen-tationwouldimproveSunSpiderperformance.innerloopsbecomehotfirst),leadingtomuchgreatertailduplica-tion.YETI,fromZaleskietal.(19)appliedDynamo-styletracingtoJavainordertoachieveinlining,indirectjumpelimination,andotheroptimizations.Theirprimaryfocuswasondesigninganinterpreterthatcouldeasilybegraduallyre-engineeredasatracingVM.Suganumaetal.(18)describedregion-basedcompilation(RBC),arelativeoftracing.Aregionisansubprogramworthoptimizingthatcanincludesubsetsofanynumberofmethods.Thus,thecom-pilerhasmoreflexibilityandcanpotentiallygeneratebettercode,buttheprofilingandcompilationsystemsarecorrespondinglymorecomplex.Typespecializationfordynamiclanguages.Dynamiclan-guageimplementorshavelongrecognizedtheimportanceoftypespecializationforperformance.Mostpreviousworkhasfocusedonmethodsinsteadoftraces.Chamberset.al(9)pioneeredtheideaofcompilingmultipleversionsofaprocedurespecializedfortheinputtypesinthelan-guageSelf.Inoneimplementation,theygeneratedaspecializedmethodonlineeachtimeamethodwascalledwithnewinputtypes.Inanother,theyusedanofflinewhole-programstaticanalysistoinferinputtypesandconstantreceivertypesatcallsites.Interest-ingly,thetwotechniquesproducednearlythesameperformance.Salib(17)designedatypeinferencealgorithmforPythonbasedontheCartesianProductAlgorithmandusedtheresultstospecial-izeontypesandtranslatetheprogramtoC++.McCloskey(14)hasworkinprogressbasedonalanguage-independenttypeinferencethatisusedtogenerateefficientCimplementationsofJavaScriptandPythonprograms.Nativecodegenerationbyinterpreters.Thetraditionalinter-preterdesignisavirtualmachinethatdirectlyexecutesASTsormachine-code-likebytecodes.Researchershaveshownhowtogen-eratenativecodewithnearlythesamestructurebutbetterperfor-mance.Callthreading,alsoknownascontextthreading(8),compilesmethodsbygeneratinganativecallinstructiontoaninterpretermethodforeachinterpreterbytecode.Acall-returnpairhasbeenshowntobeapotentiallymuchmoreefficientdispatchmechanismthantheindirectjumpsusedinstandardbytecodeinterpreters.Inlinethreading(15)copieschunksofinterpreternativecodewhichimplementtherequiredbytecodesintoanativecodecache,thusactingasasimpleper-methodJITcompilerthateliminatesthedispatchoverhead.Neithercallthreadingnorinlinethreadingperformtypespecial-ization.Apple’sSquirrelFishExtreme(5)isaJavaScriptimplementa-tionbasedoncallthreadingwithselectiveinlinethreading.Com-binedwithefficientinterpreterengineering,thesethreadingtech-niqueshavegivenSFXexcellentperformanceonthestandardSun-Spiderbenchmarks.Google’sV8isaJavaScriptimplementationprimarilybasedoninlinethreading,withcallthreadingonlyforverycomplexoperations.9.ConclusionsThispaperdescribedhowtorundynamiclanguagesefficientlybyrecordinghottracesandgeneratingtype-specializednativecode.Ourtechniquefocusesonaggressivelyinlinedloops,andforeachloop,itgeneratesatreeofnativecodetracesrepresentingthepathsandvaluetypesthroughtheloopobservedatruntime.Weexplainedhowtoidentifyloopnestingrelationshipsandgeneratenestedtracesinordertoavoidexcessivecodeduplicationduetothemanypathsthroughaloopnest.Wedescribedourtypespecializationalgorithm.Wealsodescribedourtracecompiler,whichtranslatesatracefromanintermediaterepresentationtooptimizednativecodeintwolinearpasses.Ourexperimentalresultsshowthatinpracticeloopstypicallyareenteredwithonlyafewdifferentcombinationsofvaluetypesofvariables.Thus,asmallnumberoftracesperloopissufficienttorunaprogramefficiently.Ourexperimentsalsoshowthatonprogramsamenabletotracing,weachievespeedupsof2xto20x.10.FutureWorkWorkisunderwayinanumberofareastofurtherimprovetheperformanceofourtrace-basedJavaScriptcompiler.Wecurrentlydonottraceacrossrecursivefunctioncalls,butplantoaddthesupportforthiscapabilityinthenearterm.WearealsoexploringadoptionoftheexistingworkontreerecompilationinthecontextofthepresenteddynamiccompilerinordertominimizeJITpausetimesandobtainthebestofbothworlds,fasttreestitchingaswellastheimprovedcodequalityduetotreerecompilation.Wealsoplanonaddingsupportfortracingacrossregularex-pressionsubstitutionsusinglambdafunctions,functionapplica-tionsandexpressionevaluationusingeval.Alltheselanguageconstructsarecurrentlyexecutedviainterpretation,whichlimitsourperformanceforapplicationsthatusethosefeatures.AcknowledgmentsPartsofthisefforthavebeensponsoredbytheNationalScienceFoundationundergrantsCNS-0615443andCNS-0627747,aswellasbytheCaliforniaMICROProgramandindustrialsponsorSunMicrosystemsunderProjectNo.07-127.TheU.S.GovernmentisauthorizedtoreproduceanddistributereprintsforGovernmentalpurposesnotwithstandinganycopyrightannotationthereon.Anyopinions,findings,andconclusionsorrec-ommendationsexpressedherearethoseoftheauthorandshouldnotbeinterpretedasnecessarilyrepresentingtheofficialviews,policiesorendorsements,eitherexpressedorimplied,oftheNa-tionalSciencefoundation(NSF),anyotheragencyoftheU.S.Gov-ernment,oranyofthecompaniesmentionedabove.References[1]LuaJITroadmap2008-http://lua-users.org/lists/lua-l/2008-02/msg00051.html.[2]Mozilla—FirefoxwebbrowserandThunderbirdemailclient-http://www.mozilla.com.[3]SPECJVM98-http://www.spec.org/jvm98/.[4]SpiderMonkey(JavaScript-C)Engine-http://www.mozilla.org/js/spidermonkey/.[5]Surfin’Safari-BlogArchive-AnnouncingSquirrelFishExtreme-http://webkit.org/blog/214/introducing-squirrelfish-extreme/.[6]A.Aho,R.Sethi,J.Ullman,andM.Lam.Compilers:Principles,techniques,andtools,2006.[7]V.Bala,E.Duesterwald,andS.Banerjia.Dynamo:Atransparentdynamicoptimizationsystem.InProceedingsoftheACMSIGPLANConferenceonProgrammingLanguageDesignandImplementation,pages1–12.ACMPress,2000.[8]M.Berndl,B.Vitale,M.Zaleski,andA.Brown.ContextThreading:aFlexibleandEfficientDispatchTechniqueforVirtualMachineIn-terpreters.InCodeGenerationandOptimization,2005.CGO2005.InternationalSymposiumon,pages15–26,2005.[9]C.ChambersandD.Ungar.Customization:OptimizingCompilerTechnologyforSELF,aDynamically-TypedObject-OrientedPro-grammingLanguage.InProceedingsoftheACMSIGPLAN1989ConferenceonProgrammingLanguageDesignandImplementation,pages146–160.ACMNewYork,NY,USA,1989.[10]A.Gal.EfficientBytecodeVerificationandCompilationinaVirtualMachineDissertation.PhDthesis,UniversityOfCalifornia,Irvine,2006.[11]A.Gal,C.W.Probst,andM.Franz.HotpathVM:AneffectiveJITcompilerforresource-constraineddevices.InProceedingsoftheInternationalConferenceonVirtualExecutionEnvironments,pages144–153.ACMPress,2006.[12]C.Garrett,J.Dean,D.Grove,andC.Chambers.MeasurementandApplicationofDynamicReceiverClassDistributions.1994.[13]J.Ha,M.R.Haghighat,S.Cong,andK.S.McKinley.Aconcurrenttrace-basedjust-in-timecompilerforjavascript.Dept.ofComputerSciences,TheUniversityofTexasatAustin,TR-09-06,2009.[14]B.McCloskey.Personalcommunication.[15]I.PiumartaandF.Riccardi.Optimizingdirectthreadedcodebyselec-tiveinlining.InProceedingsoftheACMSIGPLAN1998conferenceonProgramminglanguagedesignandimplementation,pages291–300.ACMNewYork,NY,USA,1998.[16]A.Rigo.Representation-BasedJust-In-timeSpecializationandthePsycoPrototypeforPython.InPEPM,2004.[17]M.Salib.Starkiller:AStaticTypeInferencerandCompilerforPython.InMaster’sThesis,2004.[18]T.Suganuma,T.Yasue,andT.Nakatani.ARegion-BasedCompila-tionTechniqueforDynamicCompilers.ACMTransactionsonPro-grammingLanguagesandSystems(TOPLAS),28(1):134–174,2006.[19]M.Zaleski,A.D.Brown,andK.Stoodley.YETI:AgraduallYExtensibleTraceInterpreter.InProceedingsoftheInternationalConferenceonVirtualExecutionEnvironments,pages83–93.ACMPress,2007.