BT
/F41 17.9328 Tf 80.5159 700.6706 Td[(T)74(race-based)-250(J)15(ust-in-T)18(ime)-250(T)74(ype)-250(Specialization)-250(f)25(or)-250(Dynamic)]TJ 183.1901 -19.9253 Td[(Languages)]TJ/F42 10.9589 Tf -143.3836 -35.8655 Td[(Andreas)-250(Gal)]TJ/F26 7.9701 Tf 55.0789 3.9588 Td[(\003)]TJ/F22 7.9701 Tf 4.7323 0 Td[(+)]TJ/F42 10.9589 Tf 7.0846 -3.9588 Td[(,)-250(Brendan)-250(Eich)]TJ/F26 7.9701 Tf 65.4351 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)-250(Mik)10(e)-250(Sha)20(v)15(er)]TJ/F26 7.9701 Tf 61.2928 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)-250(Da)20(vid)-250(Anderson)]TJ/F26 7.9701 Tf 77.3913 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)-250(Da)20(vid)-250(Mandelin)]TJ/F26 7.9701 Tf 76.7884 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)]TJ -393.5134 -12.9514 Td[(Mohammad)-250(R.)-250(Haghighat)]TJ/F22 7.9701 Tf 114.147 3.9588 Td[($)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)-250(Blak)10(e)-250(Kaplan)]TJ/F26 7.9701 Tf 65.3254 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)-250(Graydon)-250(Hoare)]TJ/F26 7.9701 Tf 73.3366 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)-250(Boris)-250(Zbarsk)15(y)]TJ/F26 7.9701 Tf 67.7145 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7324 -3.9588 Td[(,)-250(Jason)-250(Orendorf)25(f)]TJ/F26 7.9701 Tf 76.1089 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)]TJ -445.5607 -12.9514 Td[(Jesse)-250(Ruderman)]TJ/F26 7.9701 Tf 70.9142 3.9588 Td[(\003)]TJ/F42 10.9589 Tf 4.7323 -3.9588 Td[(,)-250(Edwin)-250(Smith)]TJ/F22 7.9701 Tf 63.0241 3.9588 Td[(#)]TJ/F42 10.9589 Tf 7.5551 -3.9588 Td[(,)-250(Rick)-250(Reitmaier)]TJ/F22 7.9701 Tf 72.1414 3.9588 Td[(#)]TJ/F42 10.9589 Tf 7.5551 -3.9588 Td[(,)-250(Michael)-250(Bebenita)]TJ/F22 7.9701 Tf 83.0893 3.9588 Td[(+)]TJ/F42 10.9589 Tf 7.0847 -3.9588 Td[(,)-250(Mason)-250(Chang)]TJ/F22 7.9701 Tf 66.6625 3.9588 Td[(+)-63(#)]TJ/F42 10.9589 Tf 14.6398 -3.9588 Td[(,)-250(Michael)-250(Franz)]TJ/F22 7.9701 Tf 69.0841 3.9588 Td[(+)]TJ/F42 8.9664 Tf -268.5924 -18.9028 Td[(Mozilla)-250(Corporation)]TJ/F32 5.9776 Tf 73.4696 3.809 Td[(\003)]TJ/F31 8.9664 Tf -248.6584 -13.7716 Td[(f)]TJ/F33 8.9664 Tf 4.6077 0 Td[(gal,brendan,shaver,danderson,dmandelin,mrbkap,graydon,bz,jorendorff,jruder)1(man)]TJ/F31 8.9664 Tf 362.4615 0 Td[(g)]TJ/F33 8.9664 Tf 4.6077 0 Td[(@mozilla.com)]TJ/F42 8.9664 Tf -195.5725 -16.1793 Td[(Adobe)-250(Corporation)]TJ/F28 5.9776 Tf 69.48 3.809 Td[(#)]TJ/F31 8.9664 Tf -99.6583 -13.7716 Td[(f)]TJ/F33 8.9664 Tf 4.6077 0 Td[(edwsmith,rreitmai)]TJ/F31 8.9664 Tf 80.024 0 Td[(g)]TJ/F33 8.9664 Tf 4.6077 0 Td[(@adobe.com)]TJ/F42 8.9664 Tf -54.1642 -16.5114 Td[(Intel)-250(Corporation)]TJ/F28 5.9776 Tf 62.0108 3.809 Td[($)]TJ/F31 8.9664 Tf -104.1469 -13.7716 Td[(f)]TJ/F33 8.9664 Tf 4.6077 0 Td[(mohammad.r.haghighat)]TJ/F31 8.9664 Tf 94.1458 0 Td[(g)]TJ/F33 8.9664 Tf 4.6077 0 Td[(@intel.com)]TJ/F42 8.9664 Tf -87.0392 -15.8472 Td[(Uni)25(v)15(ersity)-250(of)-250(California,)-250(Irvine)]TJ/F28 5.9776 Tf 111.7019 3.809 Td[(+)]TJ/F31 8.9664 Tf -125.6703 -13.7716 Td[(f)]TJ/F33 8.9664 Tf 4.6077 0 Td[(mbebenit,changm,franz)]TJ/F31 8.9664 Tf 98.8531 0 Td[(g)]TJ/F33 8.9664 Tf 4.6077 0 Td[(@uci.edu)]TJ/F41 10.9589 Tf -286.2636 -67.746 Td[(Abstract)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(Dynamic)-329(languages)-330(such)-329(as)-329(Ja)20(v)25(aScript)-329(are)-330(more)-329(dif)25(\002cult)-329(to)-330(com-)]TJ 0 -9.9626 Td[(pile)-275(than)-275(statically)-275(typed)-275(ones.)-275(Since)-275(no)-276(concrete)-275(type)-275(information)]TJ 0 -9.9627 Td[(is)-197(a)20(v)25(ailable,)-196(traditional)-197(compilers)-197(need)-196(to)-197(emit)-197(generic)-196(code)-197(that)-197(can)]TJ 0 -9.9626 Td[(handle)-233(all)-234(possible)-233(type)-233(combinations)-234(at)-233(runtime.)-234(W)80(e)-233(present)-233(an)-234(al-)]TJ 0 -9.9626 Td[(ternati)25(v)15(e)-376(compilat)1(ion)-376(technique)-376(for)-375(dynamically-typed)-376(languages)]TJ 0 -9.9627 Td[(that)-269(identi\002es)-270(frequently)-269(e)15(x)15(ecuted)-269(loop)-269(traces)-270(at)-269(run-time)-269(and)-270(then)]TJ 0 -9.9626 Td[(generates)-374(machine)-375(code)-374(on)-374(the)-375(\003y)-374(that)-374(is)-375(specialized)-374(for)-374(the)-375(ac-)]TJ 0 -9.9627 Td[(tual)-331(dynamic)-331(types)-331(occurring)-331(on)-331(each)-331(path)-331(through)-331(the)-331(loop.)-331(Our)]TJ 0 -9.9626 Td[(method)-232(pro)15(vides)-232(cheap)-232(inter)20(-procedural)-232(type)-233(s)1(pecialization,)-233(and)-232(an)]TJ 0 -9.9626 Td[(ele)15(g)5(ant)-238(and)-239(ef)25(\002cient)-238(w)10(ay)-239(of)-238(incrementally)-239(compiling)-238(lazily)-239(disco)15(v-)]TJ 0 -9.9627 Td[(ered)-273(alternati)25(v)15(e)-274(paths)-273(through)-274(nested)-273(loops.)-274(W)80(e)-273(ha)20(v)15(e)-274(implemented)]TJ 0 -9.9626 Td[(a)-283(dynamic)-283(compiler)-283(for)-282(Ja)20(v)25(aScript)-283(based)-283(on)-283(our)-283(technique)-283(and)-283(we)]TJ 0 -9.9627 Td[(ha)20(v)15(e)-350(measured)-351(speedups)-350(of)-351(10x)-350(and)-350(more)-351(for)-350(certain)-351(benchmark)]TJ 0 -9.9626 Td[(programs.)]TJ/F45 8.9664 Tf 0 -15.6041 Td[(Categories)-392(and)-391(Subject)-392(Descriptors)]TJ/F42 8.9664 Tf 142.5488 0 Td[(D.3.4)-392([)]TJ/F46 8.9664 Tf 26.4219 0 Td[(Pr)45(o)10(gr)15(amming)-392(Lan-)]TJ -168.9707 -9.9626 Td[(gua)10(g)10(es)]TJ/F42 8.9664 Tf 25.2223 0 Td[(]:)-250(Processors)-250(\227)]TJ/F46 8.9664 Tf 59.5181 0 Td[(Incr)37(emental)-250(compiler)10(s,)-250(code)-250(g)10(ener)15(ation)]TJ/F42 8.9664 Tf 142.788 0 Td[(.)]TJ/F45 8.9664 Tf -227.5284 -15.6041 Td[(General)-328(T)92(erms)]TJ/F42 8.9664 Tf 64.3755 0 Td[(Design,)-328(Experimentation,)-327(Measurement,)-328(Perfor)20(-)]TJ -64.3755 -9.9627 Td[(mance.)]TJ/F45 8.9664 Tf 0 -15.6041 Td[(K)25(eyw)15(ords)]TJ/F42 8.9664 Tf 44.4728 0 Td[(Ja)20(v)25(aScript,)-250(just-in-time)-250(compilation,)-250(trace)-250(trees.)]TJ/F41 10.9589 Tf -44.4728 -22.5779 Td[(1.)-1000(Intr)18(oduction)]TJ/F46 8.9664 Tf 0 -13.9477 Td[(Dynamic)-222(langua)10(g)10(es)]TJ/F42 8.9664 Tf 73.0244 0 Td[(such)-222(as)-221(Ja)20(v)25(aScript,)-222(Python,)-221(and)-222(Ruby)65(,)-222(are)-221(pop-)]TJ -73.0244 -9.9626 Td[(ular)-258(since)-259(the)15(y)-258(are)-258(e)15(xpressi)25(v)15(e,)-259(ac)1(cessible)-259(to)-258(non-e)15(xperts,)-258(and)-259(mak)10(e)]TJ 0 -9.9627 Td[(deplo)10(yment)-280(as)-280(easy)-279(as)-280(distrib)20(uting)-280(a)-280(source)-279(\002le.)-280(The)15(y)-280(are)-280(used)-280(for)]TJ 0 -9.9626 Td[(small)-365(scripts)-365(as)-365(well)-365(as)-365(for)-365(comple)15(x)-366(applications.)-365(Ja)20(v)25(aScript,)-365(for)]TJ 0 -9.9627 Td[(e)15(xample,)-266(is)-265(the)-266(de)-266(f)10(acto)-266(standard)-265(for)-266(client-side)-266(web)-266(programming)]TJ/F42 6.9738 Tf 0 -41.5565 Td[(Permission)-328(to)-329(mak)10(e)-328(digital)-329(or)-328(hard)-329(copies)-328(of)-328(all)-329(or)-328(part)-329(of)-328(this)-329(w)10(ork)-328(for)-329(personal)-328(or)]TJ 0 -7.9701 Td[(classroom)-277(use)-277(is)-278(granted)-277(without)-277(fee)-277(pro)15(vided)-278(that)-277(copies)-277(are)-277(not)-278(made)-277(or)-277(distrib)20(uted)]TJ 0 -7.9701 Td[(for)-229(pro\002t)-229(or)-229(commercial)-229(adv)25(antage)-229(and)-229(that)-229(copies)-229(bear)-229(this)-229(notice)-229(and)-229(the)-229(full)-229(citation)]TJ 0 -7.9701 Td[(on)-274(the)-274(\002rst)-274(page.)-274(T)80(o)-274(cop)10(y)-274(otherwise,)-274(to)-273(republish,)-274(to)-274(post)-274(on)-274(serv)15(ers)-274(or)-274(to)-274(redistrib)20(ute)]TJ 0 -7.9701 Td[(to)-250(lists,)-250(requires)-250(prior)-250(speci\002c)-250(permission)-250(and/or)-250(a)-250(fee.)]TJ/F48 6.9738 Tf 0 -9.9626 Td[(PLDI'09,)]TJ/F42 6.9738 Tf 33.6277 0 Td[(June)-250(15\22620,)-250(2009,)-250(Dublin,)-250(Ireland.)]TJ -33.6277 -7.9701 Td[(Cop)10(yright)]TJ 32.3825 0.2102 Td[(c)]TJ/F13 6.9738 Tf -2.4231 -0.2102 Td[(\015)]TJ/F42 6.9738 Tf 9.6859 0 Td[(2009)-250(A)40(CM)-250(978-1-60558-392-1/09/06.)-150(.)-150(.)-150($5.00)]TJ/F42 8.9664 Tf 223.3684 377.9455 Td[(and)-268(is)-267(used)-268(for)-267(the)-268(application)-267(logic)-268(of)-267(bro)25(wser)20(-based)-268(producti)25(vity)]TJ 0 -9.9627 Td[(applications)-324(such)-325(as)-324(Google)-325(Mail,)-324(Google)-324(Docs)-325(and)-324(Zimbra)-325(Col-)]TJ 0 -9.9626 Td[(laboration)-375(Suite.)-375(In)-376(this)-375(domain,)-375(in)-375(order)-376(to)-375(pro)15(vide)-375(a)-375(\003uid)-376(user)]TJ 0 -9.9626 Td[(e)15(xperience)-212(and)-212(enable)-212(a)-212(ne)25(w)-212(generation)-212(of)-213(applications,)-212(virtual)-212(ma-)]TJ 0 -9.9627 Td[(chines)-250(must)-250(pro)15(vide)-250(a)-250(lo)25(w)-250(startup)-250(time)-250(and)-250(high)-250(performance.)]TJ 11.9552 -9.9626 Td[(Compilers)-299(for)-299(statically)-299(typed)-299(languages)-299(rely)-299(on)-299(type)-299(informa-)]TJ -11.9552 -9.9627 Td[(tion)-206(to)-206(generate)-206(ef)25(\002cient)-205(machine)-206(code.)-206(In)-206(a)-206(dynamically)-206(typed)-206(pro-)]TJ 0 -9.9626 Td[(gramming)-386(language)-387(such)-386(as)-387(Ja)20(v)25(aScript,)-386(the)-387(types)-386(of)-387(e)15(xpressions)]TJ 0 -9.9626 Td[(may)-323(v)25(ary)-324(at)-323(runtime.)-323(This)-324(means)-323(that)-323(the)-324(compiler)-323(can)-323(no)-324(longer)]TJ 0 -9.9627 Td[(easily)-318(transform)-318(operations)-318(into)-318(machine)-318(instructions)-318(that)-318(operate)]TJ 0 -9.9626 Td[(on)-266(one)-266(speci)1(\002c)-266(type.)-266(W)40(ithout)-266(e)15(xact)-265(type)-266(information,)-266(the)-266(compiler)]TJ 0 -9.9627 Td[(must)-309(emit)-308(slo)25(wer)-309(generalized)-308(machine)-309(code)-308(that)-309(can)-309(deal)-308(with)-309(all)]TJ 0 -9.9626 Td[(potential)-285(type)-285(combinations.)-285(While)-285(compile-time)-285(static)-285(type)-285(infer)20(-)]TJ 0 -9.9626 Td[(ence)-412(might)-412(be)-412(able)-412(to)-412(g)5(ather)-412(type)-413(inf)1(ormation)-413(to)-412(generate)-412(opti-)]TJ 0 -9.9627 Td[(mized)-360(machine)-360(code,)-360(traditional)-360(static)-360(analysis)-360(is)-360(v)15(ery)-360(e)15(xpensi)25(v)15(e)]TJ 0 -9.9626 Td[(and)-253(hence)-253(not)-253(well)-253(s)1(uited)-253(for)-253(the)-253(highly)-253(interacti)25(v)15(e)-253(en)40(vironment)-253(of)]TJ 0 -9.9627 Td[(a)-250(web)-250(bro)25(wser)55(.)]TJ 11.9552 -9.9626 Td[(W)80(e)-409(present)-409(a)-410(trace-based)-409(compilation)-409(technique)-409(for)-409(dynamic)]TJ -11.9552 -9.9626 Td[(languages)-283(that)-283(reconciles)-282(speed)-283(of)-283(compilation)-283(with)-283(e)15(xcellent)-283(per)20(-)]TJ 0 -9.9627 Td[(formance)-211(of)-210(the)-211(generated)-210(machine)-211(code.)-210(Our)-211(system)-211(uses)-210(a)-211(mix)15(ed-)]TJ 0 -9.9626 Td[(mode)-231(e)15(x)15(ecution)-231(approach:)-231(the)-231(system)-231(starts)-231(running)-231(Ja)20(v)25(aScript)-231(in)-231(a)]TJ 0 -9.9627 Td[(f)10(ast-starting)-280(bytecode)-279(interpreter)55(.)-280(As)-279(the)-280(program)-280(runs)1(,)-280(the)-280(system)]TJ 0 -9.9626 Td[(identi\002es)]TJ/F46 8.9664 Tf 36.6853 0 Td[(hot)]TJ/F42 8.9664 Tf 15.4263 0 Td[(\050frequently)-424(e)15(x)15(ecuted\051)-425(bytecode)-424(sequences,)-425(records)]TJ -52.1116 -9.9626 Td[(them,)-368(and)-367(compiles)-368(them)-368(to)-368(f)10(ast)-367(nati)25(v)15(e)-368(code.)-368(W)80(e)-368(c)1(all)-368(such)-368(a)-368(se-)]TJ 0 -9.9627 Td[(quence)-250(of)-250(instructions)-250(a)]TJ/F46 8.9664 Tf 87.6544 0 Td[(tr)15(ace)]TJ/F42 8.9664 Tf 18.2911 0 Td[(.)]TJ -93.9903 -9.9626 Td[(Unlik)10(e)-424(method-based)-423(dynamic)-424(compilers,)-423(our)-424(dynamic)-423(com-)]TJ -11.9552 -9.9627 Td[(piler)-389(operates)-389(at)-389(the)-388(granularity)-389(of)-389(indi)25(vidual)-389(loops.)-389(This)-389(design)]TJ 0 -9.9626 Td[(choice)-391(is)-391(based)-390(on)-391(the)-391(e)15(xpectation)-391(that)-390(programs)-391(spend)-391(most)-391(of)]TJ 0 -9.9626 Td[(their)-318(time)-319(in)-318(hot)-318(loops.)-319(Ev)15(en)-318(in)-319(dynamically)-318(typed)-318(languages,)-319(we)]TJ 0 -9.9627 Td[(e)15(xpect)-221(hot)-222(l)1(oops)-222(to)-221(be)-221(mostly)]TJ/F46 8.9664 Tf 105.9153 0 Td[(type-stable)]TJ/F42 8.9664 Tf 39.3439 0 Td[(,)-221(meaning)-222(t)1(hat)-222(the)-221(types)-221(of)]TJ -145.2592 -9.9626 Td[(v)25(alues)-221(are)-220(in)40(v)25(ariant.)-221(\05012\051)-221(F)15(or)-220(e)15(xample,)-221(we)-221(w)10(ould)-220(e)15(xpect)-221(loop)-221(coun-)]TJ 0 -9.9627 Td[(ters)-253(that)-253(start)-253(as)-254(inte)15(gers)-253(to)-253(remain)-253(inte)15(gers)-253(for)-253(all)-254(iterations.)-253(When)]TJ 0 -9.9626 Td[(both)-318(of)-317(these)-318(e)15(xpectations)-317(hold,)-318(a)-317(trace-based)-318(compiler)-317(can)-318(co)15(v)15(er)]TJ 0 -9.9626 Td[(the)-229(program)-230(e)15(x)15(ecution)-229(with)-229(a)-230(small)-229(number)-229(of)-229(type-specialized,)-230(ef-)]TJ 0 -9.9627 Td[(\002ciently)-250(compiled)-250(traces.)]TJ 11.9552 -9.9626 Td[(Each)-269(compiled)-270(trace)-269(co)15(v)15(ers)-269(one)-270(path)-269(through)-270(the)-269(program)-269(with)]TJ -11.9552 -9.9627 Td[(one)-220(mapping)-220(of)-220(v)25(alues)-220(to)-220(types.)-220(When)-220(the)-221(VM)-220(e)15(x)15(ecutes)-220(a)-220(compiled)]TJ 0 -9.9626 Td[(trace,)-484(it)-483(cannot)-484(guarantee)-483(that)-484(the)-483(same)-484(path)-484(will)-483(be)-484(follo)25(wed)]TJ 0 -9.9626 Td[(or)-420(that)-419(the)-420(same)-420(types)-419(will)-420(occur)-420(in)-419(subsequent)-420(loop)-420(iterations.)]TJ
ET