BT
/F42 8.9664 Tf 54 712.0299 Td[(resentations)-385(are)-384(assigned)-385(an)-385(inte)15(ger)-385(k)10(e)15(y)-384(called)-385(the)]TJ/F46 8.9664 Tf 190.5798 0 Td[(object)-385(shape)]TJ/F42 8.9664 Tf 46.282 0 Td[(.)]TJ -236.8618 -9.9627 Td[(Thus,)-250(the)-250(guard)-250(is)-250(a)-250(simple)-250(equality)-250(check)-250(on)-250(the)-250(object)-250(shape.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(Repr)18(esentation)-452(specialization:)-452(numbers.)]TJ/F42 8.9664 Tf 161.1756 0 Td[(Ja)20(v)25(aScript)-452(has)-452(no)]TJ -173.1308 -9.9626 Td[(inte)15(ger)-374(type,)-374(only)-375(a)-374(Number)-374(type)-374(that)-375(is)-374(the)-374(set)-374(of)-374(64-bit)-375(IEEE-)]TJ 0 -9.9627 Td[(754)-469(\003oating-pointer)-469(numbers)-468(\050\223doubles\224\051.)-469(But)-469(man)15(y)-469(Ja)20(v)25(aScript)]TJ 0 -9.9626 Td[(operators,)-258(in)-258(particular)-258(array)-258(accesses)-258(and)-258(bitwise)-258(operators,)-258(really)]TJ 0 -9.9627 Td[(operate)-296(on)-296(inte)15(gers,)-296(so)-296(the)15(y)-296(\002rst)-296(con)40(v)15(ert)-296(the)-296(number)-296(to)-296(an)-296(inte)15(ger)40(,)]TJ 0 -10.3249 Td[(and)-373(then)-372(con)40(v)15(ert)-373(an)15(y)-373(inte)15(ger)-373(result)-372(back)-373(to)-373(a)-372(double.)]TJ/F42 5.9776 Tf 196.896 3.809 Td[(1)]TJ/F42 8.9664 Tf 6.8289 -3.809 Td[(Clearly)65(,)-373(a)]TJ -203.7249 -9.9626 Td[(Ja)20(v)25(aScript)-279(VM)-280(that)-279(w)10(ants)-280(to)-280(be)-279(f)10(ast)-280(must)-279(\002nd)-280(a)-279(w)10(ay)-280(to)-279(operate)-280(on)]TJ 0 -9.9627 Td[(inte)15(gers)-250(directly)-250(and)-250(a)20(v)20(oid)-250(these)-250(con)40(v)15(ersions.)]TJ 11.9552 -9.9626 Td[(In)-310(T)35(raceMonk)10(e)15(y)65(,)-310(we)-309(support)-310(tw)10(o)-310(representations)-310(for)-309(numbers:)]TJ -11.9552 -9.9627 Td[(inte)15(gers)-350(and)-351(doubles.)-350(The)-351(interpreter)-350(uses)-350(inte)15(ger)-351(representations)]TJ 0 -9.9626 Td[(as)-225(much)-225(as)-225(it)-225(can,)-225(switching)-225(for)-225(results)-225(that)-225(can)-225(only)-225(be)-225(represented)]TJ 0 -9.9626 Td[(as)-291(doubles.)-290(When)-291(a)-290(trace)-291(is)-291(started,)-290(some)-291(v)25(alues)-290(may)-291(be)-291(imported)]TJ 0 -9.9627 Td[(and)-369(represented)-369(as)-369(inte)15(gers.)-369(Some)-369(operations)-370(on)-369(inte)15(gers)-369(require)]TJ 0 -9.9626 Td[(guards.)-292(F)15(or)-292(e)15(xample,)-292(adding)-291(tw)10(o)-292(inte)15(gers)-292(can)-292(produce)-292(a)-292(v)25(alue)-292(too)]TJ 0 -9.9627 Td[(lar)18(ge)-250(for)-250(the)-250(inte)15(ger)-250(representation.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(Function)-411(inlining)15(.)]TJ/F42 8.9664 Tf 73.2653 0 Td[(LIR)-411(traces)-411(can)-411(cross)-411(function)-411(boundaries)]TJ -85.2205 -9.9626 Td[(in)-326(either)-325(direction,)-326(achie)25(ving)-325(function)-326(inlining.)-325(Mo)15(v)15(e)-326(instructions)]TJ 0 -9.9627 Td[(need)-292(to)-293(be)-292(recorded)-292(for)-293(function)-292(entry)-292(and)-293(e)15(xit)-292(to)-292(cop)10(y)-293(ar)18(guments)]TJ 0 -9.9626 Td[(in)-225(and)-226(return)-225(v)25(alues)-226(out)1(.)-226(These)-225(mo)15(v)15(e)-226(statements)-225(are)-225(then)-226(optimized)]TJ 0 -9.9627 Td[(a)15(w)10(ay)-305(by)-304(the)-305(compiler)-304(using)-305(cop)10(y)-305(propag)5(ation.)-304(In)-305(order)-304(to)-305(be)-305(able)]TJ 0 -9.9626 Td[(to)-421(return)-421(to)-420(the)-421(interpreter)40(,)-421(the)-421(trace)-421(must)-420(also)-421(generate)-421(LIR)-421(to)]TJ 0 -9.9626 Td[(record)-384(that)-383(a)-384(call)-383(frame)-384(has)-383(been)-384(entered)-383(and)-384(e)15(xited.)-383(The)-384(frame)]TJ 0 -9.9627 Td[(entry)-463(and)-464(e)15(xit)-463(LIR)-463(sa)20(v)15(es)-463(just)-464(enough)-463(information)-463(to)-463(allo)25(w)-464(the)]TJ 0 -9.9626 Td[(intepreter)-324(call)-323(stack)-324(to)-324(be)-323(restored)-324(later)-324(and)-324(is)-323(much)-324(simpler)-324(than)]TJ 0 -9.9627 Td[(the)-362(interpreter')55(s)-362(standard)-362(call)-361(code.)-362(If)-362(the)-362(function)-362(being)-362(entered)]TJ 0 -9.9626 Td[(is)-317(not)-318(constant)-317(\050which)-317(in)-318(Ja)20(v)25(aScript)-317(includes)-318(an)15(y)-317(call)-317(by)-318(function)]TJ 0 -9.9626 Td[(name\051,)-301(the)-301(recorder)-301(must)-301(also)-300(emit)-301(LIR)-301(to)-301(guard)-301(that)-301(the)-301(function)]TJ 0 -9.9627 Td[(is)-250(the)-250(same.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(Guards)-485(and)-484(side)-485(exits.)]TJ/F42 8.9664 Tf 95.3529 0 Td[(Each)-485(optimization)-484(described)-485(abo)15(v)15(e)]TJ -107.3081 -9.9627 Td[(requires)-419(one)-418(or)-419(more)-418(guards)-419(to)-418(v)15(erify)-419(the)-419(assumptions)-418(made)-419(in)]TJ 0 -9.9626 Td[(doing)-260(the)-260(optimization.)-260(A)-261(guard)-260(is)-260(just)-260(a)-260(group)-260(of)-261(LIR)-260(instructions)]TJ 0 -9.9626 Td[(that)-384(performs)-385(a)-384(test)-385(and)-384(conditional)-385(e)15(xit.)-384(The)-384(e)15(xit)-385(branches)-384(to)-385(a)]TJ/F46 8.9664 Tf 0 -9.9627 Td[(side)-372(e)20(xit)]TJ/F42 8.9664 Tf 30.551 0 Td[(,)-372(a)-373(small)-372(of)25(f-trace)-372(piece)-373(of)-372(LIR)-372(that)-372(returns)-373(a)-372(pointer)-372(to)]TJ -30.551 -9.9626 Td[(a)-416(structure)-416(that)-416(describes)-416(the)-416(reason)-416(for)-416(the)-416(e)15(xit)-416(along)-416(with)-416(the)]TJ 0 -9.9627 Td[(interpreter)-239(PC)-239(at)-239(the)-239(e)15(xit)-239(point)-239(and)-239(an)15(y)-239(other)-240(dat)1(a)-240(needed)-239(to)-239(restore)]TJ 0 -9.9626 Td[(the)-250(interpreter')55(s)-250(state)-250(structures.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(Aborts.)]TJ/F42 8.9664 Tf 31.7673 0 Td[(Some)-349(constructs)-349(are)-349(dif)25(\002cult)-349(to)-349(record)-349(in)-349(LIR)-348(traces.)]TJ -43.7225 -9.9627 Td[(F)15(or)-376(e)15(xample,)]TJ/F33 8.9664 Tf 51.5401 0 Td[(eval)]TJ/F42 8.9664 Tf 22.1969 0 Td[(or)-376(calls)-375(to)-376(e)15(xternal)-375(functions)-376(can)-375(change)-376(the)]TJ -73.737 -9.9626 Td[(program)-427(state)-427(in)-427(unpredictable)-427(w)10(ays,)-427(making)-427(it)-428(dif)25(\002c)1(ult)-428(for)-427(the)]TJ 0 -9.9627 Td[(tracer)-344(to)-343(kno)25(w)-344(the)-344(current)-343(type)-344(map)-344(in)-344(order)-343(to)-344(continue)-344(tracing.)]TJ 0 -9.9626 Td[(A)-272(tracing)-272(implementation)-272(can)-272(also)-272(ha)20(v)15(e)-272(an)15(y)-272(number)-273(of)-272(other)-272(limi-)]TJ 0 -9.9626 Td[(tations,)-272(e.g.,a)-271(small-memory)-272(de)25(vice)-271(may)-272(limit)-272(the)-271(length)-272(of)-272(traces.)]TJ 0 -9.9627 Td[(When)-313(an)15(y)-313(situation)-313(occurs)-312(that)-313(pre)25(v)15(ents)-313(the)-313(implementation)-313(from)]TJ 0 -9.9626 Td[(continuing)-211(trace)-211(recording,)-211(the)-211(implementation)]TJ/F46 8.9664 Tf 169.0923 0 Td[(aborts)]TJ/F42 8.9664 Tf 24.8109 0 Td[(trace)-211(record-)]TJ -193.9032 -9.9627 Td[(ing)-250(and)-250(returns)-250(to)-250(the)-250(trace)-250(monitor)55(.)]TJ/F41 8.9664 Tf 0 -24.4515 Td[(3.2)-1000(T)74(race)-250(T)74(r)18(ees)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(Especially)-376(simple)-376(loops,)-375(namely)-376(those)-376(where)-376(control)-376(\003o)25(w)65(,)-376(v)25(alue)]TJ 0 -9.9626 Td[(types,)-244(v)25(alue)-245(representations,)-244(and)-245(inlined)-244(functions)-245(are)-244(all)-245(in)40(v)25(ariant,)]TJ 0 -9.9626 Td[(can)-311(be)-311(represented)-312(by)-311(a)-311(single)-311(trace.)-312(But)-311(most)-311(loops)-311(ha)20(v)15(e)-311(at)-312(least)]TJ 0 -9.9627 Td[(some)-361(v)25(ariation,)-361(and)-361(so)-361(the)-360(program)-361(will)-361(tak)10(e)-361(side)-361(e)15(xits)-361(from)-361(the)]TJ 0 -9.9626 Td[(main)-341(trace.)-342(When)-341(a)-342(side)-341(e)15(xit)-342(becomes)-341(hot,)-342(T)35(raceMonk)10(e)15(y)-341(starts)-342(a)]TJ 0 -9.9627 Td[(ne)25(w)]TJ/F46 8.9664 Tf 17.021 0 Td[(br)15(anc)15(h)-257(tr)15(ace)]TJ/F42 8.9664 Tf 48.0385 0 Td[(from)-257(that)-258(point)-257(and)-257(patches)-258(the)-257(side)-257(e)15(xit)-257(to)-258(jump)]TJ -65.0595 -9.9626 Td[(directly)-235(to)-235(that)-234(trace.)-235(In)-235(this)-235(w)10(ay)65(,)-235(a)-234(single)-235(trace)-235(e)15(xpands)-235(on)-235(demand)]TJ 0 -9.9626 Td[(to)-250(a)-250(single-entry)65(,)-250(multiple-e)15(xit)]TJ/F46 8.9664 Tf 110.6079 0 Td[(tr)15(ace)-250(tr)37(ee)]TJ/F42 8.9664 Tf 34.1434 0 Td[(.)]TJ -132.7961 -9.9627 Td[(This)-280(section)-280(e)15(xplains)-280(ho)25(w)-281(trace)-280(trees)-280(are)-280(formed)-280(during)-280(e)15(x)15(ecu-)]TJ -11.9552 -9.9626 Td[(tion.)-267(The)-267(goal)-267(is)-267(to)-267(form)-267(trace)-267(trees)-267(during)-267(e)15(x)15(ecution)-267(that)-267(co)15(v)15(er)-267(all)]TJ 0 -9.9627 Td[(the)-250(hot)-250(paths)-250(of)-250(the)-250(program.)]TJ
ET
1 0 0 1 54 95.3424 cm
q
[]0 d
0 J
0.3288 w
0 0.1644 m
119.5517 0.1644 l
S
Q
1 0 0 1 -54 -95.3424 cm
BT
/F42 5.9776 Tf 54 89.1889 Td[(1)]TJ/F42 7.9701 Tf 4.4832 -2.8128 Td[(Arrays)-246(are)-247(actually)-246(w)10(orse)-246(than)-247(this:)-246(if)-246(the)-247(inde)15(x)-246(v)25(alue)-246(is)-247(a)-246(number)40(,)-246(it)-247(must)]TJ -4.4832 -8.9664 Td[(be)-249(con)40(v)15(erted)-250(from)-249(a)-250(double)-249(to)-249(a)-250(string)-249(for)-250(the)-249(property)-249(access)-250(operator)40(,)-249(and)]TJ 0 -8.9664 Td[(then)-250(to)-250(an)-250(inte)15(ger)-250(internally)-250(to)-250(the)-250(array)-250(implementation.)]TJ/F41 8.9664 Tf 274.9689 643.5866 Td[(Starting)-230(a)-231(tr)18(ee.)]TJ/F42 8.9664 Tf 59.0707 0 Td[(T)35(ree)-230(trees)-231(al)10(w)10(ays)-230(start)-230(at)-231(loop)-230(headers,)-230(because)]TJ -71.0259 -9.9627 Td[(the)15(y)-225(are)-225(a)-225(natural)-226(place)-225(to)-225(look)-225(for)-225(hot)-225(paths.)-225(In)-226(T)35(raceMonk)10(e)15(y)65(,)-225(loop)]TJ 0 -9.9626 Td[(headers)-402(are)-402(easy)-402(to)-402(detect\226the)-402(bytecode)-402(compiler)-403(ensur)1(es)-403(that)-402(a)]TJ 0 -9.9627 Td[(bytecode)-289(is)-289(a)-288(loop)-289(header)-289(if)25(f)-289(it)-289(is)-289(the)-288(tar)18(get)-289(of)-289(a)-289(backw)10(ard)-289(branch.)]TJ 0 -9.9626 Td[(T)35(raceMonk)10(e)15(y)-265(starts)-265(a)-265(tree)-266(when)-265(a)-265(gi)25(v)15(en)-265(loop)-265(header)-265(has)-266(bee)1(n)-266(e)15(x)15(e-)]TJ 0 -9.9626 Td[(cuted)-275(a)-276(certain)-275(number)-276(of)-275(times)-276(\0502)-275(in)-276(the)-275(current)-276(implementation\051.)]TJ 0 -9.9627 Td[(Starting)-283(a)-284(tree)-283(just)-284(means)-283(starting)-284(recordi)1(ng)-284(a)-283(trace)-284(for)-283(the)-284(current)]TJ 0 -9.9626 Td[(point)-221(and)-220(type)-221(map)-221(and)-220(marking)-221(the)-221(trace)-221(as)-220(the)-221(root)-221(of)-220(a)-221(tree.)-221(Each)]TJ 0 -9.9627 Td[(tree)-233(is)-234(associated)-233(with)-233(a)-234(loop)-233(header)-233(and)-234(type)-233(map,)-234(so)-233(there)-233(may)-234(be)]TJ 0 -9.9626 Td[(se)25(v)15(eral)-250(trees)-250(for)-250(a)-250(gi)25(v)15(en)-250(loop)-250(header)55(.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(Closing)-250(the)-250(loop.)]TJ/F42 8.9664 Tf 66.2608 0 Td[(T)35(race)-250(recording)-250(can)-250(end)-250(in)-250(se)25(v)15(eral)-250(w)10(ays.)]TJ -66.2608 -9.9627 Td[(Ideally)65(,)-310(the)-310(trace)-310(reaches)-310(the)-310(loop)-310(header)-310(where)-310(it)-310(started)-310(with)]TJ -11.9552 -9.9626 Td[(the)-369(same)-369(type)-369(map)-370(as)-369(on)-369(entry)65(.)-369(This)-369(is)-369(called)-369(a)]TJ/F46 8.9664 Tf 180.5073 0 Td[(type-stable)]TJ/F42 8.9664 Tf 42.654 0 Td[(loop)]TJ -223.1613 -9.9627 Td[(iteration.)-372(In)-372(this)-372(case,)-372(the)-373(end)-372(of)-372(the)-372(trace)-372(can)-372(jump)-372(right)-373(to)-372(the)]TJ 0 -9.9626 Td[(be)15(ginning,)-264(as)-265(all)-264(the)-265(v)25(alue)-264(representations)-265(are)-264(e)15(xactly)-265(as)-264(needed)-265(to)]TJ 0 -9.9626 Td[(enter)-294(the)-294(trace.)-294(The)-294(jump)-294(can)-294(e)25(v)15(en)-294(skip)-294(the)-294(usual)-294(code)-294(that)-294(w)10(ould)]TJ 0 -9.9627 Td[(cop)10(y)-276(out)-276(the)-276(state)-275(at)-276(the)-276(end)-276(of)-276(the)-276(trace)-276(and)-275(cop)10(y)-276(it)-276(back)-276(in)-276(to)-276(the)]TJ 0 -9.9626 Td[(trace)-250(acti)25(v)25(ation)-250(record)-250(to)-250(enter)-250(a)-250(trace.)]TJ 11.9552 -9.9627 Td[(In)-374(certain)-375(cases)-374(the)-375(trace)-374(might)-374(reach)-375(the)-374(loop)-375(header)-374(with)-374(a)]TJ -11.9552 -9.9626 Td[(dif)25(ferent)-235(type)-235(map.)-235(This)-235(scenario)-235(is)-235(sometime)-235(observ)15(ed)-235(for)-235(the)-235(\002rst)]TJ 0 -9.9626 Td[(iteration)-217(of)-217(a)-217(loop.)-217(Some)-217(v)25(ariables)-217(inside)-217(the)-217(loop)-217(might)-217(initially)-217(be)]TJ/F46 8.9664 Tf 0 -9.9627 Td[(unde\002ned)]TJ/F42 8.9664 Tf 34.8612 0 Td[(,)-203(before)-203(the)15(y)-203(are)-204(set)-203(to)-203(a)-203(concrete)-203(type)-203(during)-203(the)-204(\002rst)-203(loop)]TJ -34.8612 -9.9626 Td[(iteration.)-411(When)-410(recording)-411(such)-410(an)-411(iteration,)-411(t)1(he)-411(recorder)-411(cannot)]TJ 0 -9.9627 Td[(link)-273(the)-273(trace)-274(back)-273(to)-273(its)-273(o)25(wn)-274(loop)-273(header)-273(since)-273(it)-273(is)]TJ/F46 8.9664 Tf 188.5515 0 Td[(type-unstable)]TJ/F42 8.9664 Tf 48.3103 0 Td[(.)]TJ -236.8618 -9.9626 Td[(Instead,)-264(the)-263(iteration)-264(is)-263(terminated)-264(with)-263(a)-264(side)-263(e)15(xit)-264(that)-263(will)-264(al)10(w)10(ays)]TJ 0 -9.9626 Td[(f)10(ail)-339(and)-338(return)-339(to)-338(the)-339(interpreter)55(.)-339(At)-338(the)-339(same)-338(time)-339(a)-339(ne)25(w)-338(trace)-339(is)]TJ 0 -9.9627 Td[(recorded)-368(with)-369(the)-368(ne)25(w)-368(type)-369(map.)-368(Ev)15(ery)-369(time)-368(an)-368(additional)-369(type-)]TJ 0 -9.9626 Td[(unstable)-235(trace)-236(is)-236(adde)1(d)-236(to)-236(a)-235(re)15(gion,)-236(its)-235(e)15(xit)-236(type)-235(map)-236(is)-235(compared)-236(to)]TJ 0 -9.9627 Td[(the)-306(entry)-307(m)1(ap)-307(of)-306(all)-306(e)15(xisting)-306(traces)-307(in)-306(case)-306(the)15(y)-306(complement)-307(each)]TJ 0 -9.9626 Td[(other)55(.)-316(W)40(ith)-316(this)-316(approach)-315(we)-316(are)-316(able)-316(to)-316(co)15(v)15(er)-316(type-unstable)-316(loop)]TJ 0 -9.9626 Td[(iterations)-250(as)-250(long)-250(the)15(y)-250(e)25(v)15(entually)-250(form)-250(a)-250(stable)-250(equilibrium.)]TJ 11.9552 -9.9627 Td[(Finally)65(,)-333(the)-334(trace)-333(might)-333(e)15(xit)-334(the)-333(loop)-333(before)-334(reaching)-333(the)-333(loop)]TJ -11.9552 -9.9626 Td[(header)40(,)-242(for)-242(e)15(xample)-243(because)-242(e)15(x)15(ecution)-242(reaches)-242(a)]TJ/F33 8.9664 Tf 175.5107 0 Td[(break)]TJ/F42 8.9664 Tf 25.7082 0 Td[(or)]TJ/F33 8.9664 Tf 9.6407 0 Td[(return)]TJ/F42 8.9664 Tf -210.8596 -9.9627 Td[(statement.)-298(In)-298(this)-297(case,)-298(the)-298(VM)-298(simply)-298(ends)-297(the)-298(trace)-298(with)-298(an)-298(e)15(xit)]TJ 0 -9.9626 Td[(to)-250(the)-250(trace)-250(monitor)55(.)]TJ 11.9552 -9.9626 Td[(As)-354(mentioned)-353(pre)25(viously)65(,)-354(we)-353(may)-354(speculati)25(v)15(ely)-353(chose)-354(to)-353(rep-)]TJ -11.9552 -9.9627 Td[(resent)-284(certain)-284(Number)20(-typed)-284(v)25(alues)-285(as)-284(inte)15(gers)-284(on)-284(trace.)-284(W)80(e)-284(do)-285(so)]TJ 0 -9.9626 Td[(when)-337(we)-336(observ)15(e)-337(that)-336(Number)20(-typed)-337(v)25(ariables)-337(c)1(ontain)-337(an)-337(inte)15(ger)]TJ 0 -9.9627 Td[(v)25(alue)-293(at)-293(trace)-293(entry)65(.)-293(If)-292(during)-293(trace)-293(recording)-293(the)-293(v)25(ariable)-293(is)-293(une)15(x-)]TJ 0 -9.9626 Td[(pectedly)-322(assigned)-322(a)-322(non-inte)15(ger)-322(v)25(alue,)-322(we)-322(ha)20(v)15(e)-322(to)-322(widen)-322(the)-322(type)]TJ 0 -9.9626 Td[(of)-253(the)-252(v)25(ariable)-253(to)-253(a)-253(double.)-252(As)-253(a)-253(result,)-253(the)-252(recorded)-253(trace)-253(becomes)]TJ 0 -9.9627 Td[(inherently)-402(type-unstable)-402(since)-402(it)-402(starts)-402(with)-402(an)-403(i)1(nte)15(ger)-403(v)25(alue)-402(b)20(ut)]TJ 0 -9.9626 Td[(ends)-287(with)-287(a)-288(double)-287(v)25(alue.)-287(This)-287(represents)-287(a)-288(mis-speculat)1(ion,)-288(since)]TJ 0 -9.9627 Td[(at)-247(trace)-247(entry)-247(we)-246(specialized)-247(the)-247(Number)20(-typed)-247(v)25(alue)-247(to)-247(an)-247(inte)15(ger)40(,)]TJ 0 -9.9626 Td[(assuming)-213(that)-213(at)-214(the)-213(loop)-213(edge)-213(we)-214(w)10(ould)-213(ag)5(ain)-213(\002nd)-213(an)-213(inte)15(ger)-214(v)25(alue)]TJ 0 -9.9626 Td[(in)-255(the)-255(v)25(ariable,)-256(allo)25(wing)-255(us)-255(to)-255(close)-256(the)-255(loop.)-255(T)80(o)-255(a)20(v)20(oid)-255(future)-256(spec-)]TJ 0 -9.9627 Td[(ulati)25(v)15(e)-309(f)10(ai)1(lures)-309(in)40(v)20(olving)-309(this)-308(v)25(ariable,)-309(and)-308(to)-309(obtain)-308(a)-309(type-stable)]TJ 0 -9.9626 Td[(trace)-227(we)-227(note)-227(the)-227(f)10(act)-227(that)-227(the)-227(v)25(ariable)-227(in)-227(question)-227(as)-227(been)-227(observ)15(ed)]TJ 0 -9.9627 Td[(to)-264(sometimes)-264(hold)-264(non-inte)15(ger)-264(v)25(alues)-264(in)-264(an)-265(advisory)-264(data)-264(structure)]TJ 0 -9.9626 Td[(which)-250(we)-250(call)-250(the)-250(\223oracle\224.)]TJ 11.9552 -9.9626 Td[(When)-296(compiling)-296(loops,)-295(we)-296(consult)-296(the)-296(oracle)-296(before)-295(specializ-)]TJ -11.9552 -9.9627 Td[(ing)-355(v)25(alues)-356(to)-355(inte)15(gers.)-356(Speculation)-355(to)25(w)10(ards)-356(inte)15(gers)-355(is)-356(performed)]TJ 0 -9.9626 Td[(only)-363(if)-362(no)-363(adv)15(erse)-362(information)-363(is)-362(kno)25(wn)-363(to)-362(the)-363(oracle)-362(about)-363(that)]TJ 0 -9.9627 Td[(particular)-297(v)25(ariable.)-297(Whene)25(v)15(er)-298(we)-297(accidentally)-297(compile)-297(a)-297(loop)-298(that)]TJ 0 -9.9626 Td[(is)-388(type-unstable)-388(due)-388(to)-388(mis-speculation)-388(of)-388(a)-389(Number)20(-typed)-388(v)25(ari-)]TJ 0 -9.9626 Td[(able,)-331(we)-331(immediately)-331(trigger)-331(the)-331(recording)-331(of)-331(a)-331(ne)25(w)-331(trace,)-331(which)]TJ 0 -9.9627 Td[(based)-255(on)-255(the)-255(no)25(w)-256(updated)-255(oracle)-255(information)-255(will)-255(start)-255(with)-255(a)-256(dou-)]TJ 0 -9.9626 Td[(ble)-250(v)25(alue)-250(and)-250(thus)-250(become)-250(type)-250(stable.)]TJ/F41 8.9664 Tf 11.9552 -9.9627 Td[(Extending)-423(a)-424(tr)18(ee.)]TJ/F42 8.9664 Tf 72.2432 0 Td[(Side)-423(e)15(xits)-424(lead)-423(to)-424(di)1(f)25(ferent)-424(paths)-423(through)]TJ -84.1984 -9.9626 Td[(the)-300(loop,)-300(or)-300(paths)-300(with)-300(dif)25(ferent)-300(types)-300(or)-301(representations)1(.)-301(Thus,)-300(to)]TJ 0 -9.9626 Td[(completely)-218(co)15(v)15(er)-218(the)-217(loop,)-218(the)-218(VM)-218(must)-218(record)-217(traces)-218(starting)-218(at)-218(all)]TJ 0 -9.9627 Td[(side)-263(e)15(xits.)-263(These)-263(traces)-263(are)-263(recorded)-263(much)-263(lik)10(e)-264(root)-263(traces:)-263(there)-263(is)]TJ 0 -9.9626 Td[(a)-217(counter)-217(for)-218(each)-217(side)-217(e)15(xit,)-217(and)-218(when)-217(the)-217(counter)-217(reaches)-217(a)-218(hotness)]TJ 0 -9.9627 Td[(threshold,)-286(recording)-286(starts.)-286(Recording)-286(stops)-286(e)15(xactly)-286(as)-286(for)-287(the)-286(root)]TJ 0 -9.9626 Td[(trace,)-250(using)-250(the)-250(loop)-250(header)-250(of)-250(the)-250(root)-250(trace)-250(as)-250(the)-250(tar)18(get)-250(to)-250(reach.)]TJ
ET