BT
/F42 8.9664 Tf 54 712.0299 Td[(Hence,)-209(recording)-209(and)-209(compiling)-209(a)-209(trace)]TJ/F46 8.9664 Tf 141.4609 0 Td[(speculates)]TJ/F42 8.9664 Tf 39.2273 0 Td[(that)-209(the)-209(path)-209(and)]TJ -180.6882 -9.9627 Td[(typing)-220(will)-220(be)-221(e)15(xac)1(tly)-221(as)-220(the)15(y)-220(were)-220(during)-220(recording)-221(for)-220(subsequent)]TJ 0 -9.9626 Td[(iterations)-250(of)-250(the)-250(loop.)]TJ 11.9552 -9.9626 Td[(Ev)15(ery)-285(compiled)-285(trace)-285(contains)-285(all)-285(the)]TJ/F46 8.9664 Tf 137.2149 0 Td[(guar)37(ds)]TJ/F42 8.9664 Tf 27.1327 0 Td[(\050checks\051)-285(required)]TJ -176.3028 -9.9627 Td[(to)-400(v)25(alidate)-400(the)-400(speculation.)-400(If)-400(one)-400(of)-400(the)-401(guards)-400(f)10(ails)-400(\050if)-400(control)]TJ 0 -9.9626 Td[(\003o)25(w)-365(is)-366(dif)25(ferent,)-365(or)-366(a)-365(v)25(alue)-365(of)-366(a)-365(dif)25(ferent)-366(type)-365(is)-365(generated\051,)-366(the)]TJ 0 -9.9627 Td[(trace)-371(e)15(xits.)-372(If)-371(an)-371(e)15(xit)-372(becomes)-371(hot,)-371(the)-372(V)1(M)-372(can)-371(record)-371(a)]TJ/F46 8.9664 Tf 213.9706 0 Td[(br)15(anc)15(h)]TJ -213.9706 -9.9626 Td[(tr)15(ace)]TJ/F42 8.9664 Tf 20.4956 0 Td[(starting)-246(at)-246(the)-245(e)15(xit)-246(to)-246(co)15(v)15(er)-246(the)-246(ne)25(w)-246(path.)-246(In)-245(this)-246(w)10(ay)65(,)-246(the)-246(VM)]TJ -20.4956 -9.9626 Td[(records)-250(a)]TJ/F46 8.9664 Tf 34.852 0 Td[(tr)15(ace)-250(tr)37(ee)]TJ/F42 8.9664 Tf 36.385 0 Td[(co)15(v)15(ering)-250(all)-250(the)-250(hot)-250(paths)-250(through)-250(the)-250(loop.)]TJ -59.2818 -9.9627 Td[(Nested)-361(loops)-361(can)-361(be)-362(dif)25(\002cult)-361(to)-361(optimize)-361(for)-361(tracing)-361(VMs.)-361(In)]TJ -11.9552 -9.9626 Td[(a)-355(na)]TJ 15.3806 0.0448 Td[(\250)]TJ 0.2466 -0.0448 Td[(\021v)15(e)-355(implementation,)-355(inner)-355(loops)-354(w)10(ould)-355(become)-355(hot)-355(\002rst,)-355(and)]TJ -15.6272 -9.9627 Td[(the)-346(VM)-346(w)10(ould)-346(start)-346(tracing)-346(there.)-346(When)-346(the)-346(inner)-347(loop)-346(e)15(xits,)-346(the)]TJ 0 -9.9626 Td[(VM)-226(w)10(ould)-226(detect)-226(that)-227(a)-226(dif)25(ferent)-226(branch)-226(w)10(as)-226(tak)10(en.)-226(The)-227(VM)-226(w)10(ould)]TJ 0 -9.9626 Td[(try)-285(to)-285(record)-284(a)-285(branch)-285(trace,)-285(and)-285(\002nd)-285(that)-284(the)-285(trace)-285(reaches)-285(not)-285(the)]TJ 0 -9.9627 Td[(inner)-267(loop)-267(header)40(,)-266(b)20(ut)-267(the)-267(outer)-267(loop)-267(header)55(.)-266(At)-267(this)-267(point,)-267(the)-267(VM)]TJ 0 -9.9626 Td[(could)-270(continue)-271(tracing)-270(until)-271(it)-270(reaches)-271(the)-270(inner)-271(loop)-270(header)-271(ag)5(ain,)]TJ 0 -9.9627 Td[(thus)-368(tracing)-369(the)-368(outer)-369(loop)-368(inside)-369(a)-368(trace)-369(tree)-368(for)-369(the)-368(inner)-369(loop.)]TJ 0 -9.9626 Td[(But)-236(this)-236(requires)-236(tracing)-236(a)-237(cop)10(y)-236(of)-236(the)-236(outer)-236(loop)-236(for)-236(e)25(v)15(ery)-237(side)-236(e)15(xit)]TJ 0 -9.9626 Td[(and)-315(type)-315(combination)-315(in)-315(the)-315(inner)-315(loop.)-315(In)-315(essence,)-316(t)1(his)-316(is)-315(a)-315(form)]TJ 0 -9.9627 Td[(of)-287(unintended)-288(tail)-287(duplication,)-288(which)-287(can)-287(easily)-288(o)15(v)15(er\003o)25(w)-287(the)-288(code)]TJ 0 -9.9626 Td[(cache.)-212(Alternati)25(v)15(ely)65(,)-212(the)-212(VM)-212(could)-212(simply)-212(stop)-212(tracing,)-212(and)-213(gi)25(v)15(e)-212(up)]TJ 0 -9.9627 Td[(on)-250(e)25(v)15(er)-250(tracing)-250(outer)-250(loops.)]TJ 11.9552 -9.9626 Td[(W)80(e)-402(solv)15(e)-401(the)-402(nested)-401(loop)-402(problem)-402(by)-401(recording)]TJ/F46 8.9664 Tf 182.3472 0 Td[(nested)-402(tr)15(ace)]TJ -194.3024 -9.9626 Td[(tr)37(ees)]TJ/F42 8.9664 Tf 17.0985 0 Td[(.)-230(Our)-230(system)-230(traces)-231(the)-230(inner)-230(loop)-230(e)15(xactly)-230(as)-230(the)-231(na)]TJ 180.3682 0.0448 Td[(\250)]TJ 0.2466 -0.0448 Td[(\021v)15(e)-230(v)15(ersion.)]TJ -197.7133 -9.9627 Td[(The)-259(system)-260(stops)-259(e)15(xtending)-260(the)-259(inner)-260(tree)-259(when)-259(it)-260(reaches)-259(an)-260(outer)]TJ 0 -9.9626 Td[(loop,)-303(b)20(ut)-303(then)-303(it)-303(starts)-303(a)-303(ne)25(w)-303(trace)-303(at)-303(the)-303(outer)-303(loop)-303(header)55(.)-303(When)]TJ 0 -9.9626 Td[(the)-228(outer)-229(loop)-228(reaches)-228(the)-229(inner)-228(loop)-228(header)40(,)-228(the)-229(system)-228(tries)-228(to)-229(call)]TJ 0 -9.9627 Td[(the)-202(trac)1(e)-202(tree)-202(for)-201(the)-202(inner)-201(loop.)-202(If)-201(the)-202(call)-201(succeeds,)-202(the)-201(VM)-202(records)]TJ 0 -9.9626 Td[(the)-424(cal)1(l)-424(to)-424(the)-423(inner)-424(tree)-423(as)-424(part)-423(of)-424(the)-423(outer)-424(trace)-423(and)-424(\002nishes)]TJ 0 -9.9627 Td[(the)-378(outer)-379(trace)-378(as)-379(normal.)-378(In)-378(this)-379(w)10(ay)65(,)-378(our)-379(system)-378(can)-378(trace)-379(an)15(y)]TJ 0 -9.9626 Td[(number)-246(of)-246(loops)-247(nested)-246(to)-246(an)15(y)-246(depth)-246(without)-246(causing)-247(e)15(xcessi)25(v)15(e)-246(tail)]TJ 0 -9.9626 Td[(duplication.)]TJ 11.9552 -9.9627 Td[(These)-355(techniques)-355(allo)25(w)-355(a)-356(VM)-355(to)-355(dynamically)-355(translate)-355(a)-355(pro-)]TJ -11.9552 -9.9626 Td[(gram)-425(to)-424(nested,)-425(type-specialized)-425(trace)-425(trees.)-424(Because)-425(traces)-425(can)]TJ 0 -9.9627 Td[(cross)-292(function)-292(call)-293(boundaries,)-292(our)-292(techniques)-292(also)-292(achie)25(v)15(e)-292(the)-293(ef-)]TJ 0 -9.9626 Td[(fects)-211(of)-211(inlining.)-211(Because)-210(traces)-211(ha)20(v)15(e)-211(no)-211(internal)-211(control-\003o)25(w)-211(joins,)]TJ 0 -9.9626 Td[(the)15(y)-383(can)-383(be)-383(optimized)-383(in)-383(linear)-383(time)-383(by)-383(a)-383(simple)-383(compiler)-383(\05010\051.)]TJ 0 -9.9627 Td[(Thus,)-383(our)-384(tracing)-383(VM)-384(ef)25(\002ciently)-383(performs)-384(the)-383(same)-384(kind)-383(of)-384(op-)]TJ 0 -9.9626 Td[(timizations)-342(that)-342(w)10(ould)-342(require)-342(interprocedural)-342(analysis)-342(in)-342(a)-342(static)]TJ 0 -9.9627 Td[(optimization)-261(setting.)-262(This)-261(mak)10(es)-262(tracing)-261(an)-262(attracti)25(v)15(e)-261(and)-262(ef)25(fecti)25(v)15(e)]TJ 0 -9.9626 Td[(tool)-250(to)-250(type)-250(specialize)-250(e)25(v)15(en)-250(comple)15(x)-250(function)-250(call-rich)-250(code.)]TJ 11.9552 -9.9626 Td[(W)80(e)-247(implemented)-247(these)-247(techniques)-248(for)-247(an)-247(e)15(xisting)-247(Ja)20(v)25(aScript)-247(in-)]TJ -11.9552 -9.9627 Td[(terpreter)40(,)-313(SpiderMonk)10(e)15(y)65(.)-314(W)80(e)-313(call)-314(the)-313(resulting)-314(tracing)-313(VM)]TJ/F46 8.9664 Tf 215.8268 0 Td[(T)55(r)15(ace-)]TJ -215.8268 -9.9626 Td[(Monk)10(e)30(y)]TJ/F42 8.9664 Tf 28.0198 0 Td[(.)-293(T)35(raceMonk)10(e)15(y)-293(supports)-294(all)-293(the)-293(Ja)20(v)25(aScript)-293(features)-293(of)-294(Spi-)]TJ -28.0198 -9.9627 Td[(derMonk)10(e)15(y)65(,)-250(with)-250(a)-250(2x-20x)-250(speedup)-250(for)-250(traceable)-250(programs.)]TJ 11.9552 -9.9626 Td[(This)-250(paper)-250(mak)10(es)-250(the)-250(follo)25(wing)-250(contrib)20(utions:)]TJ/F26 7.9701 Tf -6.7249 -18.0308 Td[(\017)]TJ/F42 8.9664 Tf 7.7211 -0.8982 Td[(W)80(e)-246(e)15(xplain)-245(an)-246(algorithm)-246(for)-246(dynam)1(ically)-246(forming)-246(trace)-246(trees)-245(to)]TJ 0 -9.9626 Td[(co)15(v)15(er)-202(a)-201(program,)-202(representing)-202(nested)-201(loops)-202(as)-202(nested)-202(trace)-201(trees.)]TJ/F26 7.9701 Tf -7.7211 -13.0495 Td[(\017)]TJ/F42 8.9664 Tf 7.7211 -0.8982 Td[(W)80(e)-190(e)15(xplain)-190(ho)25(w)-190(to)-190(speculati)25(v)15(ely)-190(generate)-190(ef)25(\002cient)-190(type-specialized)]TJ 0 -9.9626 Td[(code)-250(for)-250(traces)-250(from)-250(dynamic)-250(language)-250(programs.)]TJ/F26 7.9701 Tf -7.7211 -13.0495 Td[(\017)]TJ/F42 8.9664 Tf 7.7211 -0.8982 Td[(W)80(e)-264(v)25(alidate)-263(our)-264(tracing)-264(techniques)-263(in)-264(an)-264(implementation)-263(based)]TJ 0 -9.9626 Td[(on)-315(the)-315(SpiderMonk)10(e)15(y)-315(Ja)20(v)25(aScript)-315(int)1(erpreter)40(,)-315(achie)25(ving)-315(2x-20x)]TJ 0 -9.9627 Td[(speedups)-250(on)-250(man)15(y)-250(programs.)]TJ -0.9963 -18.929 Td[(The)-219(remainder)-220(of)-219(this)-220(paper)-219(is)-219(or)18(g)5(anized)-220(as)-219(follo)25(ws.)-220(Section)-219(3)-219(is)]TJ -11.9551 -9.9626 Td[(a)-299(general)-298(o)15(v)15(ervie)25(w)-299(of)-299(trace)-299(t)1(ree)-299(based)-299(compilation)-299(we)-298(use)-299(to)-299(cap-)]TJ 0 -9.9627 Td[(ture)-379(and)-379(compile)-379(frequently)-379(e)15(x)15(ecuted)-379(code)-379(re)15(gions.)-380(In)-379(Section)-379(4)]TJ 0 -9.9626 Td[(we)-342(describe)-343(our)-342(approach)-343(of)-342(co)15(v)15(ering)-343(nested)-342(loops)-343(using)-342(a)-343(num-)]TJ 0 -9.9627 Td[(ber)-364(of)-364(indi)25(vidual)-364(trace)-364(trees.)-364(In)-364(Section)-364(5)-364(we)-365(describe)-364(our)-364(trace-)]TJ 0 -9.9626 Td[(compilation)-253(ba)1(sed)-253(speculati)25(v)15(e)-253(type)-252(specialization)-253(approach)-252(we)-253(use)]TJ 0 -9.9626 Td[(to)-292(generate)-293(ef)25(\002cient)-292(machine)-293(code)-292(from)-293(recorded)-292(bytecode)-293(traces.)]TJ 0 -9.9627 Td[(Our)-366(implementation)-365(of)-366(a)-366(dynamic)-365(type-specializing)-366(compiler)-366(for)]TJ 0 -9.9626 Td[(Ja)20(v)25(aScript)-314(is)-314(described)-314(in)-314(Section)-314(6.)-314(Related)-314(w)10(ork)-315(is)-314(discussed)-314(in)]TJ 0 -9.9627 Td[(Section)-230(8.)-229(In)-230(Section)-230(7)-230(we)-229(e)25(v)25(aluate)-230(our)-230(dynamic)-229(compiler)-230(based)-230(on)]TJ/F33 8.9664 Tf 263.0137 645.33 Td[(1)-525(for)-525(\050var)-525(i)-525(=)-525(2;)-525(i)-525(<)-525(100;)-525(++i\051)-525({)]TJ 0 -9.9626 Td[(2)-1575(if)-525(\050!primes[i]\051)]TJ 0 -9.9626 Td[(3)-2625(continue;)]TJ 0 -9.9627 Td[(4)-1575(for)-525(\050var)-525(k)-525(=)-525(i)-525(+)-525(i;)-525(i)-525(<)-525(100;)-525(k)-525(+=)-525(i\051)]TJ 0 -9.9626 Td[(5)-2625(primes[k])-525(=)-525(false;)]TJ 0 -9.9627 Td[(6)-525(})]TJ
ET
1 0 0 1 317.0137 651.9253 cm
q
[]0 d
0 J
0.3288 w
0 0.1644 m
239.1034 0.1644 l
S
Q
1 0 0 1 -317.0137 -651.9253 cm
BT
/F41 8.9664 Tf 317.0137 641.7624 Td[(Figur)18(e)-408(1.)-500(Sample)-408(pr)18(ogram:)-409(sie)15(v)10(e)-408(of)-408(Eratosthenes.)]TJ/F33 8.9664 Tf 201.2185 0 Td[(primes)]TJ/F42 8.9664 Tf 31.9045 0 Td[(is)]TJ -233.123 -9.9626 Td[(initialized)-353(to)-353(an)-353(array)-353(of)-353(100)]TJ/F33 8.9664 Tf 109.635 0 Td[(false)]TJ/F42 8.9664 Tf 26.7022 0 Td[(v)25(alues)-353(on)-353(entry)-353(to)-353(this)-353(code)]TJ -136.3372 -9.9627 Td[(snippet.)]TJ
ET
1 0 0 1 317.0137 414.7685 cm
 q 0.43082 0 0 0.43082 0 0 cm
q
1 0 0 1 0 0 cm
/Im1 Do
Q
 Q
1 0 0 1 0 -11.2876 cm
q
[]0 d
0 J
0.3288 w
0 0.1644 m
239.1034 0.1644 l
S
Q
1 0 0 1 -317.0137 -403.4809 cm
BT
/F41 8.9664 Tf 317.0137 393.318 Td[(Figur)18(e)-312(2.)]TJ/F42 8.9664 Tf 39.2501 0 Td[(State)-312(machine)-313(describing)-312(the)-313(major)-312(acti)25(vities)-313(of)-312(T)35(race-)]TJ -39.2501 -9.9626 Td[(Monk)10(e)15(y)-352(and)-353(the)-352(conditions)-352(that)-352(cause)-353(transitions)-352(to)-352(a)-352(ne)25(w)-353(acti)25(v-)]TJ 0 -9.9627 Td[(ity)65(.)-400(In)-399(the)-400(dark)-399(box,)-400(TM)-399(e)15(x)15(ecutes)-399(JS)-400(as)-399(compiled)-400(traces.)-399(In)-400(the)]TJ 0 -9.9626 Td[(light)-244(gray)-244(box)15(es,)-243(TM)-244(e)15(x)15(ecutes)-244(JS)-244(in)-243(the)-244(standard)-244(interpreter)55(.)-244(White)]TJ 0 -9.9627 Td[(box)15(es)-348(are)-349(o)15(v)15(erhead.)-348(Thus,)-349(to)-348(maximize)-348(performance,)-349(we)-348(need)-349(to)]TJ 0 -9.9626 Td[(maximize)-233(time)-234(spent)-233(in)-233(the)-234(dark)10(est)-233(box)-233(and)-234(minimize)-233(time)-233(spent)-234(in)]TJ 0 -9.9626 Td[(the)-241(white)-242(box)15(es.)-241(The)-242(best)-241(case)-242(is)-241(a)-242(loop)-241(where)-242(the)-241(types)-242(at)-241(the)-242(loop)]TJ 0 -9.9627 Td[(edge)-243(are)-243(the)-242(same)-243(as)-243(the)-243(types)-243(on)-243(entry\226then)-242(TM)-243(can)-243(stay)-243(in)-243(nati)25(v)15(e)]TJ 0 -9.9626 Td[(code)-250(until)-250(the)-250(loop)-250(is)-250(done.)]TJ 0 -28.4956 Td[(a)-303(set)-303(of)-304(industry)-303(benchmarks.)-303(The)-303(paper)-303(ends)-303(with)-304(conclusions)-303(in)]TJ 0 -9.9626 Td[(Section)-230(9)-230(and)-231(an)-230(outlook)-230(on)-230(future)-231(w)10(ork)-230(is)-230(presented)-230(in)-230(Section)-231(10.)]TJ/F41 10.9589 Tf 0 -23.4028 Td[(2.)-1000(Ov)10(er)10(view:)-250(Example)-250(T)74(racing)-250(Run)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(This)-434(section)-434(pro)15(vides)-434(an)-434(o)15(v)15(ervie)25(w)-434(of)-434(our)-435(system)-434(by)-434(describing)]TJ 0 -9.9626 Td[(ho)25(w)-446(T)35(raceMonk)10(e)15(y)-447(e)15(x)15(ecutes)-446(an)-447(e)15(xample)-446(program.)-446(The)-447(e)15(xample)]TJ 0 -9.9627 Td[(program,)-242(sho)25(wn)-241(in)-242(Figure)-241(1,)-242(computes)-241(the)-242(\002rst)-242(100)-241(prime)-242(numbers)]TJ 0 -9.9626 Td[(with)-196(nested)-196(loops.)-196(The)-196(narra)1(ti)25(v)15(e)-196(should)-196(be)-196(read)-196(along)-196(with)-196(Figure)-196(2,)]TJ 0 -9.9627 Td[(which)-296(describes)-296(the)-296(acti)25(vities)-296(T)35(raceMonk)10(e)15(y)-296(performs)-296(and)-297(when)-296(it)]TJ 0 -9.9626 Td[(transitions)-250(between)-250(the)-250(loops.)]TJ 11.9552 -9.9626 Td[(T)35(raceMonk)10(e)15(y)-336(al)10(w)10(ays)-336(be)15(gins)-335(e)15(x)15(ecuting)-336(a)-336(program)-336(in)-336(the)-335(byte-)]TJ -11.9552 -9.9627 Td[(code)-363(interpreter)55(.)-363(Ev)15(ery)-363(loop)-364(back)-363(edge)-363(is)-363(a)-363(potential)-364(tra)1(ce)-364(point.)]TJ 0 -9.9626 Td[(When)-382(the)-381(interpreter)-382(crosses)-382(a)-382(loop)-381(edge,)-382(T)35(raceMonk)10(e)15(y)-382(in)40(v)20(ok)10(es)]TJ 0 -9.9627 Td[(the)]TJ/F46 8.9664 Tf 13.5447 0 Td[(tr)15(ace)-289(monitor)]TJ/F42 8.9664 Tf 49.2753 0 Td[(,)-289(which)-288(may)-289(decide)-288(to)-289(record)-289(or)-288(e)15(x)15(ecute)-289(a)-289(nat)1(i)25(v)15(e)]TJ -62.82 -9.9626 Td[(trace.)-246(At)-246(the)-246(start)-247(of)-246(e)15(x)15(ecution,)-246(there)-246(are)-246(no)-246(compiled)-246(traces)-247(yet,)-246(so)]TJ 0 -9.9626 Td[(the)-199(trace)-200(monitor)-199(counts)-200(the)-199(number)-200(of)-199(times)-200(each)-199(loop)-200(back)-199(edge)-200(is)]TJ 0 -9.9627 Td[(e)15(x)15(ecuted)-220(until)-220(a)-221(loop)-220(becomes)]TJ/F46 8.9664 Tf 109.2092 0 Td[(hot)]TJ/F42 8.9664 Tf 11.4589 0 Td[(,)-220(currently)-220(after)-221(2)-220(crossings.)-220(Note)]TJ -120.6681 -9.9626 Td[(that)-207(the)-208(w)10(ay)-207(our)-207(loops)-208(are)-207(compiled,)-207(the)-207(loop)-208(edge)-207(is)-207(crossed)-208(before)]TJ 0 -9.9627 Td[(entering)-275(the)-275(loop,)-276(so)-275(the)-275(second)-275(crossing)-275(occurs)-276(immediat)1(ely)-276(after)]TJ 0 -9.9626 Td[(the)-250(\002rst)-250(iteration.)]TJ 11.9552 -9.9626 Td[(Here)-469(is)-469(the)-469(sequence)-470(of)-469(e)25(v)15(ents)-469(brok)10(en)-469(do)25(wn)-469(by)-469(outer)-469(loop)]TJ -11.9552 -9.9627 Td[(iteration:)]TJ
ET