1 0 0 1 93.9255 581.3979 cm
 q 0.35 0 0 0.35 0 0 cm
q
1 0 0 1 0 0 cm
/Im4 Do
Q
 Q
1 0 0 1 -39.9255 -11.2877 cm
q
[]0 d
0 J
0.3288 w
0 0.1644 m
239.1034 0.1644 l
S
Q
1 0 0 1 -54 -570.1102 cm
BT
/F41 8.9664 Tf 54 559.9474 Td[(Figur)18(e)-249(7.)]TJ/F42 8.9664 Tf 38.6815 0 Td[(Control)-249(\003o)25(w)-249(graph)-249(of)-249(a)-249(nested)-249(loop)-249(with)-250(an)-249(if)-249(statement)]TJ -38.6815 -9.9627 Td[(inside)-412(the)-412(inner)-412(most)-412(loop)-412(\050a\051.)-412(An)-412(inner)-413(tre)1(e)-413(captures)-412(the)-412(inner)]TJ 0 -9.9626 Td[(loop,)-241(and)-241(is)-242(nested)-241(inside)-241(an)-241(outer)-242(tree)-241(which)-241(\223calls\224)-241(the)-241(inner)-242(tree.)]TJ 0 -9.9626 Td[(The)-305(inner)-305(tree)-305(returns)-305(to)-304(the)-305(outer)-305(tree)-305(once)-305(it)-305(e)15(xits)-305(along)-305(its)-305(loop)]TJ 0 -9.9627 Td[(condition)-250(guard)-250(\050b\051.)]TJ 0 -28.6839 Td[(In)-225(general,)-226(if)-225(loops)-225(are)-226(nes)1(ted)-226(to)-225(depth)]TJ/F29 8.9664 Tf 137.9245 0 Td[(k)]TJ/F42 8.9664 Tf 5.0609 0 Td[(,)-225(and)-226(each)-225(loop)-225(has)]TJ/F29 8.9664 Tf 69.6109 0 Td[(n)]TJ/F42 8.9664 Tf 7.5793 0 Td[(paths)]TJ -220.1756 -10.3994 Td[(\050on)-402(geometric)-403(a)20(v)15(erage\051,)-402(this)-403(na)]TJ 116.2073 0.0448 Td[(\250)]TJ 0.2466 -0.0448 Td[(\021v)15(e)-402(strate)15(gy)-403(yields)]TJ/F29 8.9664 Tf 71.322 0 Td[(O)]TJ/F27 8.9664 Tf 7.2682 0 Td[(\050)]TJ/F29 8.9664 Tf 3.5838 0 Td[(n)]TJ/F30 5.9776 Tf 5.559 3.809 Td[(k)]TJ/F27 8.9664 Tf 4.5731 -3.809 Td[(\051)]TJ/F42 8.9664 Tf 7.1926 0 Td[(traces,)]TJ -215.9526 -9.9626 Td[(which)-250(can)-250(easily)-250(\002ll)-250(the)-250(trace)-250(cache.)]TJ 11.9552 -9.9627 Td[(In)-406(order)-406(to)-405(e)15(x)14(e)1(cute)-406(programs)-406(with)-406(nested)-406(loops)-406(ef)25(\002cientl)1(y)64(,)-405(a)]TJ -11.9552 -9.9626 Td[(tracing)-215(system)-214(needs)-215(a)-214(technique)-215(for)-214(co)15(v)15(ering)-215(the)-215(nested)-214(loops)-215(with)]TJ 0 -9.9627 Td[(nati)25(v)15(e)-250(code)-250(without)-250(e)15(xponential)-250(trace)-250(duplication.)]TJ/F41 8.9664 Tf 0 -18.3527 Td[(4.1)-1000(Nesting)-250(Algorithm)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(The)-286(k)10(e)15(y)-286(insight)-287(is)-286(that)-286(if)-286(each)-286(loop)-287(is)-286(represented)-286(by)-286(its)-286(o)25(wn)-287(trace)]TJ 0 -9.9626 Td[(tree,)-297(the)-298(code)-297(for)-297(each)-297(loop)-298(can)-297(be)-297(contained)-298(only)-297(in)-297(its)-297(o)25(wn)-298(tree,)]TJ 0 -9.9627 Td[(and)-228(outer)-227(loop)-228(paths)-228(will)-228(not)-227(be)-228(duplicated.)-228(Another)-228(k)10(e)15(y)-227(f)10(act)-228(is)-228(that)]TJ 0 -9.9626 Td[(we)-239(are)-240(not)-239(tracing)-239(arbitrary)-240(bytec)1(odes)-240(that)-239(might)-239(ha)20(v)15(e)-240(irreduceable)]TJ 0 -9.9626 Td[(control)-317(\003o)25(w)-318(graphs,)-317(b)20(ut)-317(rather)-318(byt)1(ecodes)-318(produced)-317(by)-317(a)-318(compiler)]TJ 0 -9.9627 Td[(for)-320(a)-320(language)-320(with)-319(structured)-320(control)-320(\003o)25(w)65(.)-320(Thus,)-320(gi)25(v)15(en)-320(tw)10(o)-320(loop)]TJ 0 -9.9626 Td[(edges,)-413(the)-413(system)-413(can)-412(easily)-413(determine)-413(whether)-413(the)15(y)-413(are)-413(nested)]TJ 0 -9.9627 Td[(and)-270(which)-270(is)-270(the)-271(inner)-270(loop.)-270(Using)-270(this)-270(kno)25(wledge,)-270(the)-271(system)-270(can)]TJ 0 -9.9626 Td[(compile)-216(inner)-217(and)-216(outer)-216(loops)-216(separately)65(,)-217(and)-216(mak)10(e)-216(the)-216(outer)-217(loop')55(s)]TJ 0 -9.9626 Td[(traces)]TJ/F46 8.9664 Tf 23.1508 0 Td[(call)]TJ/F42 8.9664 Tf 15.6998 0 Td[(the)-250(inner)-250(loop')55(s)-250(trace)-250(tree.)]TJ -26.8954 -9.9627 Td[(The)-299(algorithm)-299(for)-299(b)20(uilding)-299(nested)-299(trace)-299(trees)-299(is)-299(as)-299(follo)25(ws.)-299(W)80(e)]TJ -11.9552 -9.9626 Td[(start)-277(tracing)-277(at)-277(loop)-277(headers)-277(e)15(xactly)-277(as)-277(in)-278(the)-277(basic)-277(tracing)-277(system.)]TJ 0 -9.9627 Td[(When)-385(we)-386(e)15(xit)-385(a)-386(loop)-385(\050detected)-385(by)-386(comparing)-385(the)-385(interpreter)-386(PC)]TJ 0 -9.9626 Td[(with)-416(the)-416(range)-415(gi)25(v)15(en)-416(by)-416(the)-416(loop)-416(edge\051,)-415(we)-416(stop)-416(the)-416(trace.)-416(The)]TJ 0 -9.9626 Td[(k)10(e)15(y)-392(step)-392(of)-392(the)-392(algorithm)-391(occurs)-392(when)-392(we)-392(are)-392(recording)-392(a)-392(trace)]TJ 0 -9.9627 Td[(for)-298(loop)]TJ/F29 8.9664 Tf 31.7379 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9963 Td[(R)]TJ/F42 8.9664 Tf 8.7027 0.9963 Td[(\050)]TJ/F29 8.9664 Tf 2.9858 0 Td[(R)]TJ/F42 8.9664 Tf 9.7062 0 Td[(for)-298(loop)-298(being)-297(recorded\051)-298(and)-298(we)-298(reach)-298(the)-298(header)]TJ -59.4034 -9.9626 Td[(of)-242(a)-243(dif)25(ferent)-242(loop)]TJ/F29 8.9664 Tf 66.7304 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9963 Td[(O)]TJ/F42 8.9664 Tf 8.4482 0.9963 Td[(\050)]TJ/F29 8.9664 Tf 2.9858 0 Td[(O)]TJ/F42 8.9664 Tf 9.4411 0 Td[(for)-242(other)-243(loop\051.)-242(Note)-242(that)]TJ/F29 8.9664 Tf 91.7943 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9963 Td[(O)]TJ/F42 8.9664 Tf 8.4482 0.9963 Td[(must)-242(be)-243(an)]TJ -200.3898 -9.9626 Td[(inner)-250(loop)-250(of)]TJ/F29 8.9664 Tf 48.5616 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9963 Td[(R)]TJ/F42 8.9664 Tf 8.2738 0.9963 Td[(because)-250(we)-250(stop)-250(the)-250(trace)-250(when)-250(we)-250(e)15(xit)-250(a)-250(loop.)]TJ/F26 7.9701 Tf -57.876 -14.2558 Td[(\017)]TJ/F42 8.9664 Tf 7.7212 -0.8982 Td[(If)]TJ/F29 8.9664 Tf 8.6997 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9962 Td[(O)]TJ/F42 8.9664 Tf 9.0035 0.9962 Td[(has)-304(a)-305(type-)1(matching)-305(compiled)-304(trace)-304(tree,)-304(we)-305(call)]TJ/F29 8.9664 Tf 179.4346 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9962 Td[(O)]TJ/F42 8.9664 Tf 9.0035 0.9962 Td[(as)]TJ -218.6831 -9.9626 Td[(a)-274(nested)-274(trace)-274(tree.)-274(If)-274(the)-274(call)-274(succeeds,)-273(then)-274(we)-274(record)-274(the)-274(call)]TJ 0 -9.9626 Td[(in)-260(the)-261(trace)-260(for)]TJ/F29 8.9664 Tf 55.1491 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9963 Td[(R)]TJ/F42 8.9664 Tf 6.0322 0.9963 Td[(.)-260(On)-261(future)-260(e)15(x)15(ecutions,)-261(the)-260(trace)-260(for)]TJ/F29 8.9664 Tf 130.1102 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9963 Td[(R)]TJ/F42 8.9664 Tf 8.3673 0.9963 Td[(will)]TJ -212.2006 -9.9626 Td[(call)-250(the)-250(inner)-250(trace)-250(directly)65(.)]TJ/F26 7.9701 Tf -7.7211 -13.0495 Td[(\017)]TJ/F42 8.9664 Tf 7.7211 -0.8982 Td[(If)]TJ/F29 8.9664 Tf 8.9629 0 Td[(L)]TJ/F30 5.9776 Tf 6.2709 -0.9963 Td[(O)]TJ/F42 8.9664 Tf 9.2667 0.9963 Td[(does)-334(not)-333(ha)20(v)15(e)-334(a)-333(type-matching)-334(compiled)-334(trace)-333(tree)-334(yet,)]TJ -24.5005 -9.9626 Td[(we)-386(ha)20(v)15(e)-385(to)-386(obtain)-385(it)-386(before)-385(we)-386(are)-385(able)-386(to)-385(proceed.)-386(In)-385(order)]TJ 0 -9.9627 Td[(to)-319(do)-318(this,)-319(we)-318(simply)-319(abort)-318(recording)-319(the)-319(\002rst)-318(trace.)-319(The)-318(trace)]TJ 0 -9.9626 Td[(monitor)-366(will)-366(see)-365(the)-366(inner)-366(loop)-366(header)40(,)-366(and)-366(wi)1(ll)-366(immediately)]TJ 0 -10.3249 Td[(start)-250(recording)-250(the)-250(inner)-250(loop.)]TJ/F42 5.9776 Tf 108.5728 3.809 Td[(2)]TJ/F42 8.9664 Tf -109.569 -18.9629 Td[(If)-202(all)-202(the)-201(loops)-202(in)-202(a)-202(nest)-202(are)-201(type-stable,)-202(then)-202(loop)-202(nesting)-201(creates)]TJ -11.9552 -9.9627 Td[(no)-206(duplication.)-205(Otherwise,)-206(if)-206(loops)-205(are)-206(nested)-206(to)-205(a)-206(depth)]TJ/F29 8.9664 Tf 198.7384 0 Td[(k)]TJ/F42 8.9664 Tf 5.0609 0 Td[(,)-206(and)-205(each)]TJ
ET
1 0 0 1 54 104.3088 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 -104.3088 cm
BT
/F42 5.9776 Tf 54 98.1552 Td[(2)]TJ/F42 7.9701 Tf 4.4832 -2.8128 Td[(Instead)-292(of)-291(aborting)-292(the)-291(outer)-292(recording,)-291(we)-292(could)-291(principally)-292(merely)-292(sus-)]TJ -4.4832 -8.9664 Td[(pend)-344(the)-344(recording,)-344(b)20(ut)-344(that)-344(w)10(ould)-344(require)-344(the)-344(implementation)-344(to)-344(be)-344(able)]TJ 0 -8.9663 Td[(to)-333(record)-333(se)25(v)15(eral)-333(traces)-333(simultaneously)65(,)-333(complicating)-333(the)-333(implementation,)]TJ 0 -8.9664 Td[(while)-250(sa)20(ving)-250(only)-250(a)-250(fe)25(w)-250(iterations)-250(in)-250(the)-250(interpreter)55(.)]TJ
ET
1 0 0 1 382.7675 600.193 cm
 q 0.33005 0 0 0.33005 0 0 cm
q
1 0 0 1 0 0 cm
/Im5 Do
Q
 Q
1 0 0 1 -65.7538 -11.2877 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 -588.9053 cm
BT
/F41 8.9664 Tf 317.0137 578.7425 Td[(Figur)18(e)-225(8.)]TJ/F42 8.9664 Tf 38.463 0 Td[(Control)-225(\003o)25(w)-224(graph)-225(of)-225(a)-225(loop)-224(with)-225(tw)10(o)-225(nested)-224(loops)-225(\050left\051)]TJ -38.463 -9.9627 Td[(and)-320(its)-320(nested)-320(trace)-320(tree)-320(con\002guration)-320(\050right\051.)-320(The)-321(outer)-320(tree)-320(calls)]TJ 0 -9.9626 Td[(the)-271(tw)10(o)-271(inner)-271(nested)-272(trace)-271(trees)-271(and)-271(places)-271(guards)-271(at)-271(their)-272(side)-271(e)15(xit)]TJ 0 -9.9626 Td[(locations.)]TJ 0 -33.3876 Td[(loop)-236(is)-235(entered)-236(with)]TJ/F29 8.9664 Tf 72.7002 0 Td[(m)]TJ/F42 8.9664 Tf 10.2308 0 Td[(dif)25(ferent)-236(t)1(ype)-236(maps)-236(\050on)-235(geometric)-236(a)20(v)15(erage\051,)]TJ -82.931 -10.3994 Td[(then)-288(we)-289(compile)]TJ/F29 8.9664 Tf 62.5392 0 Td[(O)]TJ/F27 8.9664 Tf 7.2682 0 Td[(\050)]TJ/F29 8.9664 Tf 3.5838 0 Td[(m)]TJ/F30 5.9776 Tf 8.1188 3.809 Td[(k)]TJ/F27 8.9664 Tf 4.5731 -3.809 Td[(\051)]TJ/F42 8.9664 Tf 6.1689 0 Td[(copies)-288(of)-289(the)-288(innermost)-288(loop.)-288(As)-289(long)-288(as)]TJ/F29 8.9664 Tf -92.252 -9.9626 Td[(m)]TJ/F42 8.9664 Tf 10.3604 0 Td[(is)-250(close)-250(to)-250(1,)-250(the)-250(resulting)-250(trace)-250(trees)-250(will)-250(be)-250(tractable.)]TJ 1.5948 -9.9627 Td[(An)-197(important)-197(detail)-197(is)-196(that)-197(the)-197(call)-197(to)-197(the)-197(inner)-197(trace)-197(tree)-196(must)-197(act)]TJ -11.9552 -9.9626 Td[(lik)10(e)-237(a)-237(function)-237(call)-237(site:)-236(it)-237(must)-237(return)-237(to)-237(the)-237(same)-237(point)-237(e)25(v)15(ery)-237(time.)]TJ 0 -9.9626 Td[(The)-289(goal)-289(of)-289(nesting)-289(is)-289(to)-289(mak)10(e)-289(inner)-290(and)-289(outer)-289(loops)-289(independent;)]TJ 0 -9.9627 Td[(thus)-358(when)-358(the)-358(inner)-359(tree)-358(is)-358(called,)-358(it)-358(must)-358(e)15(xit)-358(to)-358(the)-359(same)-358(point)]TJ 0 -9.9626 Td[(in)-326(the)-325(outer)-326(tree)-325(e)25(v)15(ery)-326(time)-325(with)-326(the)-325(same)-326(type)-326(map.)-325(Because)-326(we)]TJ 0 -9.9627 Td[(cannot)-315(actually)-316(guarantee)-315(this)-315(property)65(,)-316(we)-315(must)-316(guard)-315(on)-315(it)-316(after)]TJ 0 -9.9626 Td[(the)-386(call,)-385(and)-386(side)-386(e)15(xit)-386(if)-385(the)-386(property)-386(does)-386(not)-385(hold.)-386(A)-386(common)]TJ 0 -9.9626 Td[(reason)-422(for)-423(the)-422(inner)-423(tree)-422(not)-423(to)-422(return)-423(to)-422(the)-423(same)-422(point)-423(w)10(ould)]TJ 0 -9.9627 Td[(be)-399(if)-399(the)-399(inner)-399(tree)-399(took)-399(a)-399(ne)25(w)-399(side)-399(e)15(xit)-399(for)-399(which)-399(it)-399(had)-399(ne)25(v)15(er)]TJ 0 -9.9626 Td[(compiled)-352(a)-352(trace.)-352(At)-352(this)-352(point,)-352(the)-352(interpreter)-352(PC)-352(is)-353(in)-352(the)-352(inner)]TJ 0 -9.9627 Td[(tree,)-320(so)-321(we)-320(cannot)-320(continue)-321(recording)-320(or)-321(e)15(x)15(ecuting)-320(the)-320(outer)-321(tree.)]TJ 0 -9.9626 Td[(If)-312(this)-312(happens)-313(during)-312(recording,)-312(we)-312(abort)-313(the)-312(outer)-312(trace,)-312(to)-313(gi)25(v)15(e)]TJ 0 -9.9626 Td[(the)-257(inner)-258(tree)-257(a)-258(chance)-257(to)-257(\002nish)-258(gro)25(wing.)-257(A)-258(fut)1(ure)-258(e)15(x)15(ecution)-257(of)-258(the)]TJ 0 -9.9627 Td[(outer)-249(tree)-249(w)10(ould)-249(then)-249(be)-249(able)-249(to)-249(properly)-249(\002nish)-249(and)-250(rec)1(ord)-250(a)-249(call)-249(to)]TJ 0 -9.9626 Td[(the)-233(inner)-234(tree.)-233(If)-234(an)-233(inner)-234(tree)-233(side)-234(e)15(xit)-233(happens)-234(during)-233(e)15(x)15(ecution)-234(of)]TJ 0 -9.9627 Td[(a)-314(compiled)-315(trace)-314(for)-314(the)-315(outer)-314(tree,)-314(we)-314(simply)-315(e)15(xit)-314(the)-314(outer)-315(trace)]TJ 0 -9.9626 Td[(and)-250(start)-250(recording)-250(a)-250(ne)25(w)-250(branch)-250(in)-250(the)-250(inner)-250(tree.)]TJ/F41 8.9664 Tf 0 -21.6236 Td[(4.2)-1000(Blacklisting)-250(with)-250(Nesting)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(The)-362(blacklisting)-363(algorithm)-362(needs)-363(modi\002cation)-362(to)-363(w)10(ork)-362(well)-363(with)]TJ 0 -9.9626 Td[(nesting.)-359(The)-358(problem)-359(is)-359(that)-358(outer)-359(loop)-359(traces)-358(often)-359(abort)-359(during)]TJ 0 -9.9627 Td[(startup)-263(\050because)-264(the)-263(inner)-263(tree)-264(is)-263(not)-263(a)20(v)25(ailable)-263(or)-264(tak)10(es)-263(a)-263(side)-264(e)15(xit\051,)]TJ 0 -9.9626 Td[(which)-362(w)10(ould)-363(lead)-362(to)-363(t)1(heir)-363(being)-362(quickly)-363(blacklisted)-362(by)-362(the)-363(basic)]TJ 0 -9.9626 Td[(algorithm.)]TJ 11.9552 -9.9627 Td[(The)-283(k)10(e)15(y)-284(observ)25(ation)-283(is)-284(that)-283(when)-284(an)-283(outer)-284(tr)1(ace)-284(aborts)-283(because)]TJ -11.9552 -9.9626 Td[(the)-299(inner)-299(tree)-299(is)-300(not)-299(ready)65(,)-299(this)-299(is)-299(probably)-299(a)-300(temporary)-299(condition.)]TJ 0 -9.9627 Td[(Thus,)-279(we)-278(should)-279(not)-279(count)-278(such)-279(aborts)-279(to)25(w)10(ard)-278(blacklisting)-279(as)-279(long)]TJ 0 -9.9626 Td[(as)-250(we)-250(are)-250(able)-250(to)-250(b)20(uild)-250(up)-250(more)-250(traces)-250(for)-250(the)-250(inner)-250(tree.)]TJ 11.9552 -9.9626 Td[(In)-325(our)-326(implementation,)-325(when)-326(an)-325(outer)-326(tree)-325(aborts)-325(on)-326(the)-325(inner)]TJ -11.9552 -9.9627 Td[(tree,)-353(we)-354(increment)-353(the)-353(outer)-354(tree')55(s)-353(blacklist)-354(counter)-353(as)-353(usual)-354(and)]TJ 0 -9.9626 Td[(back)-313(of)25(f)-312(on)-313(compiling)-313(it.)-313(When)-312(the)-313(inner)-313(tree)-313(\002nis)1(hes)-313(a)-313(trace,)-313(we)]TJ 0 -9.9627 Td[(decrement)-311(the)-311(blacklist)-311(count)1(er)-311(on)-311(the)-311(outer)-311(loop,)-311(\223for)18(gi)25(ving\224)-311(the)]TJ 0 -9.9626 Td[(outer)-219(loop)-218(for)-219(aborting)-218(pre)25(viously)65(.)-219(W)80(e)-218(also)-219(undo)-218(the)-219(back)10(of)25(f)-218(so)-219(that)]TJ 0 -9.9626 Td[(the)-244(outer)-244(tree)-244(can)-244(start)-244(immediately)-244(trying)-244(to)-244(compile)-245(the)-244(ne)15(xt)-244(time)]TJ 0 -9.9627 Td[(we)-250(reach)-250(it.)]TJ/F41 10.9589 Tf 0 -28.4503 Td[(5.)-1000(T)74(race)-250(T)74(r)18(ee)-250(Optimization)]TJ/F42 8.9664 Tf 0 -13.9477 Td[(This)-488(section)-488(e)15(xplains)-488(ho)25(w)-487(a)-488(recorded)-488(trace)-488(is)-488(translated)-488(to)-488(an)]TJ 0 -9.9626 Td[(optimized)-358(machine)-358(code)-357(trace.)-358(The)-358(trace)-358(compilation)-358(subsystem,)]TJ/F42 7.1731 Tf 0.2242 -9.9627 Td[(N)-28(A)-62(N)-61(O)-62(J)-62(I)-62(T)]TJ/F42 8.9664 Tf 32.915 0 Td[(,)-470(is)-470(separate)-470(from)-470(the)-470(VM)-470(and)-470(can)-470(be)-471(used)-470(for)-470(other)]TJ -33.1392 -9.9626 Td[(applications.)]TJ
ET