BT
/F41 8.9664 Tf 65.9552 712.0299 Td[(i=4.)]TJ/F42 8.9664 Tf 16.3253 0 Td[(On)-223(this)-222(iteration,)-223(T)35(raceMonk)10(e)15(y)-223(calls)]TJ/F29 8.9664 Tf 132.214 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9963 Td[(16)]TJ/F42 8.9664 Tf 7.804 0.9963 Td[(.)-223(Because)]TJ/F33 8.9664 Tf 36.1115 0 Td[(i=4)]TJ/F42 8.9664 Tf 14.1219 0 Td[(,)-223(the)]TJ/F33 8.9664 Tf -223.9079 -9.9627 Td[(if)]TJ/F42 8.9664 Tf 12.3342 0 Td[(statement)-326(on)-325(line)-326(2)-325(is)-326(tak)10(en.)-326(This)-325(branch)-326(w)10(as)-325(not)-326(tak)10(en)-325(in)-326(the)]TJ -12.3342 -9.9626 Td[(original)-231(trace,)-231(so)-232(this)-231(causes)]TJ/F29 8.9664 Tf 102.2519 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9962 Td[(16)]TJ/F42 8.9664 Tf 9.8771 0.9962 Td[(to)-231(f)10(ail)-231(a)-232(guard)-231(and)-231(tak)10(e)-231(a)-231(side)-232(e)15(xit.)]TJ -117.505 -9.9626 Td[(The)-304(e)15(xit)-304(is)-303(not)-304(yet)-304(hot,)-304(so)-304(T)35(raceMonk)10(e)15(y)-303(returns)-304(to)-304(the)-304(interpreter)40(,)]TJ 0 -9.9627 Td[(which)-250(e)15(x)15(ecutes)-250(the)-250(continue)-250(statement.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(i=5.)]TJ/F42 8.9664 Tf 16.3435 0 Td[(T)35(raceMonk)10(e)15(y)-225(calls)]TJ/F29 8.9664 Tf 70.2197 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9963 Td[(16)]TJ/F42 8.9664 Tf 7.804 0.9963 Td[(,)-225(which)-225(in)-224(turn)-225(calls)-225(the)-224(nested)-225(trace)]TJ/F29 8.9664 Tf -111.6984 -9.9627 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9962 Td[(45)]TJ/F42 8.9664 Tf 7.804 0.9962 Td[(.)]TJ/F29 8.9664 Tf 5.3921 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9962 Td[(16)]TJ/F42 8.9664 Tf 10.9544 0.9962 Td[(loops)-351(back)-352(to)-351(its)-351(o)25(wn)-352(header)40(,)-351(starting)-351(the)-352(ne)15(xt)-351(iteration)]TJ -34.9025 -9.9626 Td[(without)-250(e)25(v)15(er)-250(returning)-250(to)-250(the)-250(monitor)55(.)]TJ/F41 8.9664 Tf 11.9552 -9.9626 Td[(i=6.)]TJ/F42 8.9664 Tf 16.5046 0 Td[(On)-243(this)-242(iteration,)-243(the)-243(side)-243(e)15(xit)-242(on)-243(line)-243(2)-242(is)-243(tak)10(en)-243(ag)5(ain.)-243(This)]TJ -28.4598 -9.9627 Td[(time,)-352(the)-352(side)-352(e)15(xit)-351(becomes)-352(hot,)-352(so)-352(a)-352(trace)]TJ/F29 8.9664 Tf 159.7422 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9962 Td[(23)]TJ/F30 5.9776 Tf 7.3058 0 Td[(;)]TJ/F28 5.9776 Tf 2.2693 0 Td[(1)]TJ/F42 8.9664 Tf 7.3061 0.9962 Td[(is)-352(recorded)-352(that)]TJ -181.9994 -9.9626 Td[(co)15(v)15(ers)-258(line)-257(3)-258(and)-257(returns)-258(to)-257(the)-258(loop)-257(header)55(.)-258(Thus,)-258(the)-257(end)-258(of)]TJ/F29 8.9664 Tf 220.0013 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9963 Td[(23)]TJ/F30 5.9776 Tf 7.3058 0 Td[(;)]TJ/F28 5.9776 Tf 2.2692 0 Td[(1)]TJ/F42 8.9664 Tf -234.9523 -8.9664 Td[(jumps)-313(directly)-314(to)-313(the)-314(start)-313(of)]TJ/F29 8.9664 Tf 107.0194 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9962 Td[(16)]TJ/F42 8.9664 Tf 7.8039 0.9962 Td[(.)-313(The)-314(side)-313(e)15(xit)-314(is)-313(patched)-314(so)-313(that)]TJ -120.1993 -9.9626 Td[(on)-250(future)-250(iterations,)-250(it)-250(jumps)-250(directly)-250(to)]TJ/F29 8.9664 Tf 142.9581 0 Td[(T)]TJ/F28 5.9776 Tf 5.376 -0.9962 Td[(23)]TJ/F30 5.9776 Tf 7.3058 0 Td[(;)]TJ/F28 5.9776 Tf 2.2692 0 Td[(1)]TJ/F42 8.9664 Tf 4.1511 0.9962 Td[(.)]TJ -150.105 -9.9626 Td[(At)-193(this)-192(point,)-193(T)35(raceMonk)10(e)15(y)-192(has)-193(compiled)-193(enough)-192(traces)-193(to)-192(co)15(v)15(er)]TJ -11.9552 -9.9627 Td[(the)-397(entire)-397(nested)-397(loop)-397(st)1(ructure,)-397(so)-397(the)-397(rest)-397(of)-397(the)-397(program)-397(runs)]TJ 0 -9.9626 Td[(entirely)-250(as)-250(nati)25(v)15(e)-250(code.)]TJ/F41 10.9589 Tf 0 -27.0984 Td[(3.)-1000(T)74(race)-250(T)74(r)18(ees)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(In)-371(this)-370(section,)-371(we)-370(describe)-371(traces,)-370(trace)-371(trees,)-370(and)-371(ho)25(w)-370(the)15(y)-371(are)]TJ 0 -9.9626 Td[(formed)-243(at)-244(run)-243(time.)-244(Although)-243(our)-244(techniques)-243(apply)-244(to)-243(an)15(y)-244(dynamic)]TJ 0 -9.9627 Td[(language)-349(interpreter)40(,)-350(we)-349(will)-350(describe)-349(them)-350(assuming)-349(a)-350(bytecode)]TJ 0 -9.9626 Td[(interpreter)-250(to)-250(k)10(eep)-250(the)-250(e)15(xposition)-250(simple.)]TJ/F41 8.9664 Tf 0 -20.7223 Td[(3.1)-1000(T)74(races)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(A)]TJ/F46 8.9664 Tf 9.4995 0 Td[(tr)15(ace)]TJ/F42 8.9664 Tf 21.3178 0 Td[(is)-338(sim)1(ply)-338(a)-338(program)-337(path,)-338(which)-337(may)-338(cross)-337(function)-338(call)]TJ -30.8173 -9.9626 Td[(boundaries.)-281(T)35(raceMonk)10(e)15(y)-281(focuses)-280(on)]TJ/F46 8.9664 Tf 137.2694 0 Td[(loop)-281(tr)15(aces)]TJ/F42 8.9664 Tf 40.2395 0 Td[(,)-281(that)-281(originate)-281(at)]TJ -177.5089 -9.9627 Td[(a)-284(loop)-284(edge)-284(and)-284(represent)-283(a)-284(single)-284(iteration)-284(through)-284(the)-284(associated)]TJ 0 -9.9626 Td[(loop.)]TJ 11.9552 -9.9627 Td[(Similar)-368(to)-368(an)-368(e)15(xtended)-368(basic)-368(block,)-368(a)-368(trace)-368(is)-367(only)-368(entered)-368(at)]TJ -11.9552 -9.9626 Td[(the)-282(top,)-282(b)20(ut)-281(may)-282(ha)20(v)15(e)-282(man)15(y)-282(e)15(xits.)-282(In)-281(contrast)-282(to)-282(an)-282(e)15(xtended)-282(basic)]TJ 0 -9.9626 Td[(block,)-381(a)-381(trace)-381(can)-382(contain)-381(join)-381(nodes.)-381(Since)-381(a)-381(trace)-382(al)10(w)10(ays)-381(only)]TJ 0 -9.9627 Td[(follo)25(ws)-212(one)-213(single)-212(path)-212(through)-212(the)-213(original)-212(program,)-212(ho)25(we)25(v)15(er)40(,)-213(join)]TJ 0 -9.9626 Td[(nodes)-397(are)-397(not)-397(recognizable)-397(as)-397(such)-397(in)-397(a)-397(trace)-397(and)-398(ha)20(v)15(e)-397(a)-397(single)]TJ 0 -9.9627 Td[(predecessor)-250(node)-250(lik)10(e)-250(re)15(gular)-250(nodes.)]TJ 11.9552 -9.9626 Td[(A)]TJ/F46 8.9664 Tf 8.6978 0 Td[(typed)-248(tr)15(ace)]TJ/F42 8.9664 Tf 42.1603 0 Td[(is)-248(a)-248(trace)-248(annotated)-248(with)-248(a)-248(type)-248(for)-248(e)25(v)15(ery)-248(v)25(ariable)]TJ -62.8133 -9.9626 Td[(\050including)-205(temporaries\051)-205(on)-205(the)-206(trace.)-205(A)-205(typed)-205(trace)-205(also)-205(has)-206(an)-205(entry)]TJ/F46 8.9664 Tf 0 -9.9627 Td[(type)-303(map)]TJ/F42 8.9664 Tf 35.813 0 Td[(gi)25(ving)-303(the)-303(required)-303(types)-303(for)-303(v)25(ariables)-303(used)-303(on)-303(the)-304(trace)]TJ -35.813 -9.9626 Td[(before)-220(the)15(y)-221(are)-220(de\002ned.)-220(F)15(or)-221(e)15(xample,)-220(a)-220(trace)-220(could)-221(ha)20(v)15(e)-220(a)-220(type)-221(map)]TJ/F33 8.9664 Tf 0 -9.9627 Td[(\050x:)-525(int,)-525(b:)-525(boolean\051)]TJ/F42 8.9664 Tf 94.1459 0 Td[(,)-314(meaning)-314(that)-314(the)-314(trace)-315(may)-314(be)-314(entered)]TJ -94.1459 -9.9626 Td[(only)-261(if)-261(the)-261(v)25(alue)-261(of)-261(the)-261(v)25(ariable)]TJ/F33 8.9664 Tf 115.0411 0 Td[(x)]TJ/F42 8.9664 Tf 7.048 0 Td[(is)-261(of)-261(type)]TJ/F33 8.9664 Tf 35.9115 0 Td[(int)]TJ/F42 8.9664 Tf 16.4626 0 Td[(and)-261(the)-261(v)25(alue)-261(of)]TJ/F33 8.9664 Tf 59.9329 0 Td[(b)]TJ/F42 8.9664 Tf -234.3961 -9.9626 Td[(is)-267(of)-266(type)]TJ/F33 8.9664 Tf 36.06 0 Td[(boolean)]TJ/F42 8.9664 Tf 32.9511 0 Td[(.)-267(The)-266(entry)-267(type)-266(map)-267(is)-266(much)-267(lik)10(e)-266(the)-267(signature)]TJ -69.0111 -9.9627 Td[(of)-250(a)-250(function.)]TJ 11.9552 -9.9626 Td[(In)-368(this)-367(paper)40(,)-368(we)-367(only)-368(discuss)-367(typed)-368(loop)-368(traces,)-367(and)-368(we)-367(will)]TJ -11.9552 -9.9627 Td[(refer)-344(to)-343(them)-344(simply)-344(as)-343(\223traces\224.)-344(The)-344(k)10(e)15(y)-344(property)-343(of)-344(typed)-344(loop)]TJ 0 -9.9626 Td[(traces)-267(is)-266(that)-267(the)15(y)-267(can)-267(be)-266(compiled)-267(to)-267(ef)25(\002cient)-266(machine)-267(code)-267(using)]TJ 0 -9.9626 Td[(the)-250(same)-250(techniques)-250(used)-250(for)-250(typed)-250(languages.)]TJ 11.9552 -9.9627 Td[(In)-261(T)35(raceMonk)10(e)15(y)65(,)-262(traces)-261(are)-261(recorded)-261(in)-262(trace-\003a)20(v)20(ored)-261(SSA)]TJ/F46 8.9664 Tf 213.6987 0 Td[(LIR)]TJ/F42 8.9664 Tf -225.6539 -9.9626 Td[(\050lo)25(w-le)25(v)15(el)-338(intermediate)-338(representation\051.)-338(In)-338(trace-\003a)20(v)20(ored)-339(SSA)-338(\050or)]TJ 0 -9.9627 Td[(TSSA\051,)-278(phi)-278(nodes)-278(appear)-279(only)-278(at)-278(the)-278(entry)-278(point,)-278(which)-279(is)-278(reached)]TJ 0 -9.9626 Td[(both)-379(on)-379(entry)-380(and)-379(via)-379(loop)-379(edges.)-379(The)-380(im)1(portant)-380(LIR)-379(primiti)25(v)15(es)]TJ 0 -9.9626 Td[(are)-482(constant)-481(v)25(alues,)-482(memory)-482(loads)-482(and)-481(stores)-482(\050by)-482(address)-482(and)]TJ 0 -9.9627 Td[(of)25(fset\051,)-378(inte)15(ger)-378(operators,)-377(\003oating-point)-378(operators,)-378(function)-378(calls,)]TJ 0 -9.9626 Td[(and)-275(conditional)-275(e)15(xits.)-275(T)80(ype)-274(con)40(v)15(ersions,)-275(such)-275(as)-275(inte)15(ger)-275(to)-275(double,)]TJ 0 -9.9627 Td[(are)-443(represented)-443(by)-444(function)-443(calls.)-443(This)-443(mak)10(es)-443(the)-443(LIR)-443(used)-444(by)]TJ 0 -9.9626 Td[(T)35(raceMonk)10(e)15(y)-390(independent)-390(of)-391(the)-390(concrete)-390(type)-390(system)-390(and)-391(type)]TJ 0 -9.9626 Td[(con)40(v)15(ersion)-368(rules)-368(of)-368(the)-368(source)-368(language.)-368(The)-368(LIR)-368(operations)-368(are)]TJ 0 -9.9627 Td[(generic)-221(enough)-220(that)-221(the)-221(back)10(end)-221(compiler)-220(is)-221(language)-221(independent.)]TJ 0 -9.9626 Td[(Figure)-250(3)-250(sho)25(ws)-250(an)-250(e)15(xample)-250(LIR)-250(trace.)]TJ 11.9552 -9.9627 Td[(Bytecode)-452(interpreters)-453(typically)-452(represent)-452(v)25(alues)-453(in)-452(a)-452(v)25(arious)]TJ -11.9552 -9.9626 Td[(comple)15(x)-304(data)-303(structures)-304(\050e.g.,)-303(hash)-304(tables\051)-303(in)-304(a)-304(box)15(ed)-303(format)-304(\050i.e.,)]TJ 0 -9.9626 Td[(with)-311(attached)-311(type)-311(tag)-311(bits\051.)-311(Since)-311(a)-311(trace)-312(i)1(s)-312(intended)-311(to)-311(represent)]TJ 0 -9.9627 Td[(ef)25(\002cient)-332(code)-333(that)-332(eliminates)-332(all)-332(that)-333(comple)15(xity)65(,)-332(our)-332(traces)-333(oper)20(-)]TJ 0 -9.9626 Td[(ate)-340(on)-339(unbox)15(ed)-340(v)25(alues)-340(in)-340(simpl)1(e)-340(v)25(ariables)-340(and)-340(arrays)-339(as)-340(much)-340(as)]TJ 0 -9.9627 Td[(possible.)]TJ 274.9689 643.5866 Td[(A)-297(trace)-297(records)-297(a)1(ll)-297(its)-297(intermediate)-297(v)25(alues)-297(in)-297(a)-297(small)-296(acti)25(v)25(ation)]TJ -11.9552 -9.9627 Td[(record)-275(area.)-275(T)80(o)-275(mak)10(e)-275(v)25(ariable)-275(accesses)-275(f)10(ast)-275(on)-275(trace,)-275(the)-275(trace)-275(also)]TJ 0 -9.9626 Td[(imports)-300(local)-301(and)-300(global)-301(v)25(ariables)-300(by)-300(unboxing)-301(them)-300(and)-301(cop)10(ying)]TJ 0 -9.9626 Td[(them)-384(to)-384(its)-384(acti)25(v)25(ation)-383(record.)-384(Thus,)-384(the)-384(trace)-384(can)-384(read)-384(and)-384(write)]TJ 0 -9.9627 Td[(these)-201(v)25(ariables)-201(wit)1(h)-201(simple)-201(loads)-201(and)-201(stores)-200(from)-201(a)-201(nati)25(v)15(e)-201(acti)25(v)25(ation)]TJ 0 -9.9626 Td[(recording,)-434(independently)-435(of)-434(the)-435(boxing)-434(mechanism)-435(used)-434(by)-435(the)]TJ 0 -9.9627 Td[(interpreter)55(.)-378(When)-379(the)-378(trace)-378(e)15(xits,)-378(the)-379(VM)-378(box)15(es)-378(the)-378(v)25(alues)-379(from)]TJ 0 -9.9626 Td[(this)-266(nati)25(v)15(e)-265(storage)-266(location)-265(and)-266(copies)-265(them)-266(back)-266(to)-265(the)-266(interpreter)]TJ 0 -9.9626 Td[(structures.)]TJ 11.9552 -9.9627 Td[(F)15(or)-584(e)25(v)15(ery)-583(control-\003o)25(w)-584(branch)-583(in)-584(the)-583(source)-584(program,)-583(the)]TJ -11.9552 -9.9626 Td[(recorder)-229(generates)-229(conditional)-229(e)15(xit)-229(LIR)-230(inst)1(ructions.)-230(These)-229(instruc-)]TJ 0 -9.9627 Td[(tions)-325(e)15(xit)-324(from)-325(the)-324(trace)-325(if)-324(required)-325(control)-324(\003o)25(w)-325(is)-324(dif)25(ferent)-325(from)]TJ 0 -9.9626 Td[(what)-310(it)-310(w)10(as)-310(at)-310(trac)1(e)-310(recording,)-310(ensuring)-310(that)-310(the)-310(trace)-310(instructions)]TJ 0 -9.9626 Td[(are)-416(run)-415(only)-416(if)-415(the)15(y)-416(are)-416(supposed)-415(to.)-416(W)80(e)-416(call)-415(these)-416(instructions)]TJ/F46 8.9664 Tf 0 -9.9627 Td[(guar)37(d)]TJ/F42 8.9664 Tf 23.5724 0 Td[(instructions.)]TJ -11.6172 -9.9626 Td[(Most)-198(of)-199(our)-198(traces)-199(represent)-198(loops)-198(and)-199(end)-198(with)-199(the)-198(special)]TJ/F33 8.9664 Tf 208.319 0 Td[(loop)]TJ/F42 8.9664 Tf -220.2742 -9.9627 Td[(LIR)-306(instruction.)-305(This)-306(is)-305(just)-306(an)-306(unconditional)-305(branch)-306(to)-305(the)-306(top)-306(of)]TJ 0 -9.9626 Td[(the)-250(trace.)-250(Such)-250(traces)-250(return)-250(only)-250(via)-250(guards.)]TJ 11.9552 -9.9626 Td[(No)25(w)65(,)-325(we)-325(describe)-325(the)-326(k)10(e)15(y)-325(optimizations)-325(that)-325(are)-325(performed)-325(as)]TJ -11.9552 -9.9627 Td[(part)-320(of)-320(recording)-320(LIR.)-320(All)-320(of)-321(thes)1(e)-321(optimizations)-320(reduce)-320(comple)15(x)]TJ 0 -9.9626 Td[(dynamic)-396(language)-396(constructs)-397(to)-396(simple)-396(typed)-396(constructs)-396(by)-397(spe-)]TJ 0 -9.9627 Td[(cializing)-238(for)-239(the)-238(current)-239(trace.)-238(Each)-238(optimization)-239(requires)-238(guard)-239(in-)]TJ 0 -9.9626 Td[(structions)-342(to)-342(v)15(erify)-342(their)-342(assumptions)-342(about)-342(the)-342(state)-343(a)1(nd)-343(e)15(xit)-342(the)]TJ 0 -9.9626 Td[(trace)-250(if)-250(necessary)65(.)]TJ/F41 8.9664 Tf 11.9552 -9.9627 Td[(T)74(ype)-250(specialization.)]TJ/F42 8.9664 Tf 0 -9.9626 Td[(All)-369(LIR)-369(primiti)26(v)14(e)1(s)-369(apply)-369(to)-369(operands)-369(of)-369(speci\002c)-369(type)1(s.)-369(Thus,)]TJ -11.9552 -9.9627 Td[(LIR)-435(traces)-435(are)-435(necessarily)-435(type-specialized,)-435(and)-435(a)-436(compiler)-435(can)]TJ 0 -9.9626 Td[(easily)-430(produc)1(e)-430(a)-430(translation)-429(that)-430(requires)-429(no)-430(type)-429(dispatches.)-430(A)]TJ 0 -9.9626 Td[(typical)-291(byt)1(ecode)-291(interpreter)-291(carri)1(es)-291(tag)-291(bits)-290(along)-291(with)-290(each)-291(v)25(alue,)]TJ 0 -9.9627 Td[(and)-241(to)-241(perform)-240(an)15(y)-241(operation,)-241(must)-241(check)-240(the)-241(tag)-241(bits,)-241(dynamically)]TJ 0 -9.9626 Td[(dispatch,)-478(mask)-478(out)-478(the)-478(tag)-478(bits)-478(to)-478(reco)15(v)15(er)-479(the)-478(untagged)-478(v)25(alue,)]TJ 0 -9.9627 Td[(perform)-233(the)-234(operation,)-233(and)-233(then)-234(reappl)1(y)-234(tags.)-233(LIR)-233(omits)-234(e)25(v)15(erything)]TJ 0 -9.9626 Td[(e)15(xcept)-250(the)-250(operation)-250(itself.)]TJ 11.9552 -9.9626 Td[(A)-244(potential)-244(problem)-244(is)-244(that)-244(some)-244(operations)-243(can)-244(produce)-244(v)25(alues)]TJ -11.9552 -9.9627 Td[(of)-368(unpredictable)-368(types.)-369(F)15(or)-368(e)15(xample,)-368(reading)-368(a)-368(property)-368(from)-369(an)]TJ 0 -9.9626 Td[(object)-411(could)-410(yield)-411(a)-410(v)25(alue)-411(of)-411(an)15(y)-410(type,)-411(not)-411(ne)1(cessarily)-411(the)-411(type)]TJ 0 -9.9627 Td[(observ)15(ed)-340(during)-341(rec)1(ording.)-341(The)-340(recorder)-340(emits)-340(guard)-341(instructions)]TJ 0 -9.9626 Td[(that)-284(conditionally)-284(e)15(xit)-284(if)-284(the)-284(operation)-284(yields)-284(a)-284(v)25(alue)-285(of)-284(a)-284(dif)25(ferent)]TJ 0 -9.9626 Td[(type)-462(from)-463(that)-462(seen)-462(during)-463(recording.)-462(These)-462(guard)-463(instructions)]TJ 0 -9.9627 Td[(guarantee)-285(that)-285(as)-285(long)-286(as)-285(e)15(x)15(ecution)-285(is)-285(on)-285(trace,)-285(the)-285(types)-286(of)-285(v)25(alues)]TJ 0 -9.9626 Td[(match)-283(those)-283(of)-283(the)-283(typed)-283(trace.)-283(When)-283(the)-283(VM)-283(observ)15(es)-284(a)-283(side)-283(e)15(xit)]TJ 0 -9.9627 Td[(along)-283(such)-283(a)-283(type)-284(guard,)-283(a)-283(ne)25(w)-283(typed)-283(trace)-283(is)-284(recorded)-283(originating)]TJ 0 -9.9626 Td[(at)-265(the)-265(side)-266(e)15(xit)-265(location,)-265(capturing)-265(the)-266(ne)25(w)-265(type)-265(of)-265(the)-265(operation)-266(in)]TJ 0 -9.9626 Td[(question.)]TJ/F41 8.9664 Tf 11.9552 -9.9627 Td[(Repr)18(esentation)-424(specialization:)-425(objects.)]TJ/F42 8.9664 Tf 153.4538 0 Td[(In)-425(Ja)20(v)25(aS)1(cript,)-425(name)]TJ -165.409 -9.9626 Td[(lookup)-352(semantics)-352(are)-352(comple)15(x)-352(and)-352(potentially)-352(e)15(xpensi)25(v)15(e)-352(because)]TJ 0 -9.9627 Td[(the)15(y)-263(include)-263(features)-263(lik)10(e)-263(object)-263(inheritance)-263(and)]TJ/F33 8.9664 Tf 174.6448 0 Td[(eval)]TJ/F42 8.9664 Tf 18.8292 0 Td[(.)-263(T)80(o)-263(e)25(v)25(aluate)]TJ -193.474 -9.9626 Td[(an)-362(object)-363(property)-362(read)-362(e)15(xpression)-363(li)1(k)10(e)]TJ/F33 8.9664 Tf 147.2531 0 Td[(o.x)]TJ/F42 8.9664 Tf 14.1219 0 Td[(,)-362(the)-363(interpreter)-362(must)]TJ -161.375 -9.9626 Td[(search)-283(the)-283(property)-283(map)-283(of)]TJ/F33 8.9664 Tf 99.8342 0 Td[(o)]TJ/F42 8.9664 Tf 7.2455 0 Td[(and)-283(all)-283(of)-283(its)-283(prototypes)-283(and)-283(parents.)]TJ -107.0797 -9.9627 Td[(Property)-351(maps)-351(can)-351(be)-351(implemented)-351(with)-351(dif)25(ferent)-351(data)-351(structures)]TJ 0 -9.9626 Td[(\050e.g.,)-358(per)20(-object)-359(hash)-358(tables)-358(or)-358(shared)-359(hash)-358(tables\051,)-358(so)-358(the)-359(search)]TJ 0 -9.9627 Td[(process)-420(also)-421(must)-420(dispatch)-420(on)-421(t)1(he)-421(representation)-420(of)-420(each)-421(object)]TJ 0 -9.9626 Td[(found)-210(during)-209(search.)-210(T)35(raceMonk)10(e)15(y)-210(can)-209(simply)-210(observ)15(e)-209(the)-210(result)-210(of)]TJ 0 -9.9626 Td[(the)-312(search)-311(process)-312(and)-312(record)-311(the)-312(simplest)-312(possible)-311(LIR)-312(to)-312(access)]TJ 0 -9.9627 Td[(the)-220(property)-220(v)25(alue.)-219(F)15(or)-220(e)15(xample,)-220(the)-220(search)-220(might)-219(\002nds)-220(the)-220(v)25(alue)-220(of)]TJ/F33 8.9664 Tf 0 -9.9626 Td[(o.x)]TJ/F42 8.9664 Tf 16.242 0 Td[(in)-236(the)-237(prototype)-236(of)]TJ/F33 8.9664 Tf 68.2496 0 Td[(o)]TJ/F42 8.9664 Tf 4.7073 0 Td[(,)-236(which)-237(uses)-236(a)-237(shared)-236(hash-table)-237(represen-)]TJ -89.1989 -9.9627 Td[(tation)-232(that)-233(places)]TJ/F33 8.9664 Tf 62.5359 0 Td[(x)]TJ/F42 8.9664 Tf 6.7923 0 Td[(in)-233(sl)1(ot)-233(2)-233(of)-232(a)-233(property)-232(v)15(ector)55(.)-233(Then)-232(the)-233(recorded)]TJ -69.3282 -9.9626 Td[(can)-226(generate)-226(LIR)-226(that)-226(reads)]TJ/F33 8.9664 Tf 99.7654 0 Td[(o.x)]TJ/F42 8.9664 Tf 16.1497 0 Td[(with)-226(just)-226(tw)10(o)-226(or)-227(three)-226(loads:)-226(one)-226(to)]TJ -115.9151 -9.9626 Td[(get)-225(the)-225(prototype,)-224(possibly)-225(one)-225(to)-225(get)-225(the)-224(property)-225(v)25(alue)-225(v)15(ector)40(,)-225(and)]TJ 0 -9.9627 Td[(one)-262(more)-261(to)-262(get)-262(slot)-261(2)-262(from)-262(the)-261(v)15(ector)55(.)-262(This)-262(is)-261(a)-262(v)25(ast)-262(simpli\002cation)]TJ 0 -9.9626 Td[(and)-261(speedup)-262(compared)-261(to)-261(the)-262(original)-261(interpreter)-261(code.)-262(Inheritance)]TJ 0 -9.9627 Td[(relationships)-307(and)-307(object)-306(representations)-307(can)-307(change)-307(during)-307(e)15(x)15(ecu-)]TJ 0 -9.9626 Td[(tion,)-287(so)-288(the)-287(simpli\002ed)-287(code)-288(require)1(s)-288(guard)-287(instructions)-287(that)-288(ensure)]TJ 0 -9.9626 Td[(the)-200(object)-200(representation)-200(is)-199(the)-200(same.)-200(In)-200(T)35(raceMonk)10(e)15(y)65(,)-200(objects')-200(rep-)]TJ
ET