pdf2htmlEX/demo/demo4.page

<div class="pd w0 h0"><div id="pf4" class="pf" data-page-no="4"><div class="pc pc4"><div class="t m0 x34 h5 y5b ff1 fs3 fc0 sc0 ls0 ws0">i=4.<span class="_ _5"> </span><span class="ff2">On<span class="_ _5"> </span>this<span class="_ _7"> </span>iteration,<span class="_ _5"> </span>T<span class="_ _2"></span>raceMonkey<span class="_ _7"> </span>calls<span class="_ _5"> </span><span class="fff">T</span></span></div><div class="t m0 x57 h8 y10b ff8 fs4 fc0 sc0 ls0 ws0">16</div><div class="t m0 x58 h5 y5b ff2 fs3 fc0 sc0 ls0 ws0">.<span class="_ _5"> </span>Because<span class="_ _5"> </span><span class="ff7">i=4<span class="_ _2"></span><span class="ff2">,<span class="_ _5"> </span>the</span></span></div><div class="t m0 x2f h5 y5c ff7 fs3 fc0 sc0 ls0 ws0">if<span class="_ _3"> </span><span class="ff2">statement<span class="_ _6"> </span>on<span class="_ _3"> </span>line<span class="_ _6"> </span>2<span class="_ _3"> </span>is<span class="_ _3"> </span>taken.<span class="_ _6"> </span>This<span class="_ _3"> </span>branch<span class="_ _3"> </span>was<span class="_ _6"> </span>not<span class="_ _3"> </span>taken<span class="_ _3"> </span>in<span class="_ _6"> </span>the</span></div><div class="t m0 x2f h5 y5d ff2 fs3 fc0 sc0 ls0 ws0">original<span class="_ _5"> </span>trace,<span class="_ _5"> </span>so<span class="_ _5"> </span>this<span class="_ _5"> </span>causes<span class="_ _5"> </span><span class="fff">T</span></div><div class="t m0 x59 h8 y10c ff8 fs4 fc0 sc0 ls0 ws0">16</div><div class="t m0 x5a h5 y5d ff2 fs3 fc0 sc0 ls0 ws0">to<span class="_ _5"> </span>fail<span class="_ _5"> </span>a<span class="_ _5"> </span>guard<span class="_ _7"> </span>and<span class="_ _5"> </span>take<span class="_ _5"> </span>a<span class="_ _5"> </span>side<span class="_ _5"> </span>e<span class="_ _2"></span>xit.</div><div class="t m0 x2f h5 y5e ff2 fs3 fc0 sc0 ls0 ws0">The<span class="_ _3"> </span>exit<span class="_ _3"> </span>is<span class="_ _3"> </span>not<span class="_ _3"> </span>yet<span class="_ _3"> </span>hot,<span class="_ _3"> </span>so<span class="_ _3"> </span>T<span class="_ _2"></span>raceMonk<span class="_ _2"></span>ey<span class="_ _3"> </span>returns<span class="_ _3"> </span>to<span class="_ _3"> </span>the<span class="_ _3"> </span>interpreter<span class="_ _b"></span>,</div><div class="t m0 x2f h5 y5f ff2 fs3 fc0 sc0 ls0 ws0">which<span class="_ _5"> </span>executes<span class="_ _5"> </span>the<span class="_ _5"> </span>continue<span class="_ _5"> </span>statement.</div><div class="t m0 x34 h5 y60 ff1 fs3 fc0 sc0 ls0 ws0">i=5.<span class="_ _5"> </span><span class="ff2">T<span class="_ _2"></span>raceMonk<span class="_ _2"></span>ey<span class="_ _5"> </span>calls<span class="_ _7"> </span><span class="fff">T</span></span></div><div class="t m0 x5b h8 y10d ff8 fs4 fc0 sc0 ls0 ws0">16</div><div class="t m0 x5c h5 y60 ff2 fs3 fc0 sc0 ls0 ws0">,<span class="_ _5"> </span>which<span class="_ _5"> </span>in<span class="_ _7"> </span>turn<span class="_ _5"> </span>calls<span class="_ _5"> </span>the<span class="_ _5"> </span>nested<span class="_ _5"> </span>trace</div><div class="t m0 x2f h5 y61 fff fs3 fc0 sc0 ls0 ws0">T</div><div class="t m0 x36 h8 y10e ff8 fs4 fc0 sc0 ls0 ws0">45</div><div class="t m0 x37 h5 y61 ff2 fs3 fc0 sc0 ls0 ws0">.<span class="_ _6"> </span><span class="fff">T</span></div><div class="t m0 x5d h8 y10e ff8 fs4 fc0 sc0 ls0 ws0">16</div><div class="t m0 x38 h5 y61 ff2 fs3 fc0 sc0 ls0 ws0">loops<span class="_ _6"> </span>back<span class="_ _6"> </span>to<span class="_ _6"> </span>its<span class="_ _6"> </span>o<span class="_ _2"></span>wn<span class="_ _6"> </span>header<span class="_ _2"></span>,<span class="_ _6"> </span>starting<span class="_ _3"> </span>the<span class="_ _6"> </span>next<span class="_ _6"> </span>iteration</div><div class="t m0 x2f h5 y62 ff2 fs3 fc0 sc0 ls0 ws0">without<span class="_ _5"> </span>ev<span class="_ _2"></span>er<span class="_ _5"> </span>returning<span class="_ _5"> </span>to<span class="_ _3"> </span>the<span class="_ _5"> </span>monitor<span class="_ _b"></span>.</div><div class="t m0 x34 h5 y63 ff1 fs3 fc0 sc0 ls0 ws0">i=6.<span class="_ _5"> </span><span class="ff2">On<span class="_ _5"> </span>this<span class="_ _5"> </span>iteration,<span class="_ _5"> </span>the<span class="_ _5"> </span>side<span class="_ _5"> </span>exit<span class="_ _5"> </span>on<span class="_ _5"> </span>line<span class="_ _5"> </span>2<span class="_ _5"> </span>is<span class="_ _5"> </span>taken<span class="_ _5"> </span>again.<span class="_ _5"> </span>This</span></div><div class="t m0 x2f h5 y7 ff2 fs3 fc0 sc0 ls0 ws0">time,<span class="_ _6"> </span>the<span class="_ _6"> </span>side<span class="_ _6"> </span>exit<span class="_ _3"> </span>becomes<span class="_ _6"> </span>hot,<span class="_ _6"> </span>so<span class="_ _6"> </span>a<span class="_ _6"> </span>trace<span class="_ _6"> </span><span class="fff">T</span></div><div class="t m0 x57 h8 ya4 ff8 fs4 fc0 sc0 ls0 ws0">23<span class="ff10">,</span>1</div><div class="t m0 x28 h5 y7 ff2 fs3 fc0 sc0 ls0 ws0">is<span class="_ _6"> </span>recorded<span class="_ _6"> </span>that</div><div class="t m0 x2f h5 y64 ff2 fs3 fc0 sc0 ls0 ws0">cov<span class="_ _2"></span>ers<span class="_ _5"> </span>line<span class="_ _3"> </span>3<span class="_ _5"> </span>and<span class="_ _5"> </span>returns<span class="_ _5"> </span>to<span class="_ _3"> </span>the<span class="_ _5"> </span>loop<span class="_ _5"> </span>header<span class="_ _2"></span>.<span class="_ _5"> </span>Thus,<span class="_ _5"> </span>the<span class="_ _3"> </span>end<span class="_ _5"> </span>of<span class="_ _5"> </span><span class="fff">T</span></div><div class="t m0 x5e h8 y10f ff8 fs4 fc0 sc0 ls0 ws0">23<span class="ff10">,</span>1</div><div class="t m0 x2f h5 y66 ff2 fs3 fc0 sc0 ls0 ws0">jumps<span class="_ _3"> </span>directly<span class="_ _3"> </span>to<span class="_ _3"> </span>the<span class="_ _6"> </span>start<span class="_ _3"> </span>of<span class="_ _3"> </span><span class="fff">T</span></div><div class="t m0 x5f h8 y110 ff8 fs4 fc0 sc0 ls0 ws0">16</div><div class="t m0 x60 h5 y66 ff2 fs3 fc0 sc0 ls0 ws0">.<span class="_ _3"> </span>The<span class="_ _3"> </span>side<span class="_ _3"> </span>exit<span class="_ _3"> </span>is<span class="_ _3"> </span>patched<span class="_ _6"> </span>so<span class="_ _3"> </span>that</div><div class="t m0 x2f h5 y67 ff2 fs3 fc0 sc0 ls0 ws0">on<span class="_ _5"> </span>future<span class="_ _5"> </span>iterations,<span class="_ _3"> </span>it<span class="_ _5"> </span>jumps<span class="_ _5"> </span>directly<span class="_ _5"> </span>to<span class="_ _5"> </span><span class="fff">T</span></div><div class="t m0 x61 h8 y111 ff8 fs4 fc0 sc0 ls0 ws0">23<span class="ff10">,</span>1</div><div class="t m0 x62 h5 y67 ff2 fs3 fc0 sc0 ls0 ws0">.</div><div class="t m0 x34 h5 y68 ff2 fs3 fc0 sc0 ls0 ws0">At<span class="_ _7"> </span>this<span class="_ _5"> </span>point,<span class="_ _7"> </span>T<span class="_ _2"></span>raceMonke<span class="_ _2"></span>y<span class="_ _7"> </span>has<span class="_ _5"> </span>compiled<span class="_ _7"> </span>enough<span class="_ _5"> </span>traces<span class="_ _7"> </span>to<span class="_ _7"> </span>cover</div><div class="t m0 x2f h5 y69 ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _8"> </span>entire<span class="_ _8"> </span>nested<span class="_ _d"> </span>loop<span class="_ _6"> </span>structure,<span class="_ _d"> </span>so<span class="_ _6"> </span>the<span class="_ _d"> </span>rest<span class="_ _8"> </span>of<span class="_ _8"> </span>the<span class="_ _8"> </span>program<span class="_ _8"> </span>runs</div><div class="t m0 x2f h5 y6a ff2 fs3 fc0 sc0 ls0 ws0">entirely<span class="_ _5"> </span>as<span class="_ _5"> </span>native<span class="_ _5"> </span>code.</div><div class="t m0 x2f h9 y112 ff1 fs1 fc0 sc0 ls0 ws0">3.<span class="_ _a"> </span>T<span class="_ _b"></span>race<span class="_ _3"> </span>T<span class="_ _b"></span>rees</div><div class="t m0 x2f h5 y113 ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _6"> </span>this<span class="_ _8"> </span>section,<span class="_ _6"> </span>we<span class="_ _8"> </span>describe<span class="_ _6"> </span>traces,<span class="_ _8"> </span>trace<span class="_ _6"> </span>trees,<span class="_ _8"> </span>and<span class="_ _6"> </span>how<span class="_ _6"> </span>they<span class="_ _6"> </span>are</div><div class="t m0 x2f h5 y114 ff2 fs3 fc0 sc0 ls0 ws0">formed<span class="_ _5"> </span>at<span class="_ _5"> </span>run<span class="_ _5"> </span>time.<span class="_ _5"> </span>Although<span class="_ _5"> </span>our<span class="_ _5"> </span>techniques<span class="_ _5"> </span>apply<span class="_ _3"> </span>to<span class="_ _5"> </span>an<span class="_ _2"></span>y<span class="_ _5"> </span>dynamic</div><div class="t m0 x2f h5 y115 ff2 fs3 fc0 sc0 ls0 ws0">language<span class="_ _6"> </span>interpreter<span class="_ _2"></span>,<span class="_ _6"> </span>we<span class="_ _3"> </span>will<span class="_ _6"> </span>describe<span class="_ _6"> </span>them<span class="_ _6"> </span>assuming<span class="_ _6"> </span>a<span class="_ _6"> </span>bytecode</div><div class="t m0 x2f h5 y116 ff2 fs3 fc0 sc0 ls0 ws0">interpreter<span class="_ _5"> </span>to<span class="_ _5"> </span>keep<span class="_ _5"> </span>the<span class="_ _3"> </span>e<span class="_ _2"></span>xposition<span class="_ _5"> </span>simple.</div><div class="t m0 x2f hc y117 ff1 fs3 fc0 sc0 ls0 ws0">3.1<span class="_ _9"> </span>T<span class="_ _b"></span>races</div><div class="t m0 x2f h5 y118 ff2 fs3 fc0 sc0 ls0 ws0">A<span class="_ _6"> </span><span class="ffa">tr<span class="_ _2"></span>ace<span class="_ _6"> </span><span class="ff2">is<span class="_ _3"> </span>simply<span class="_ _6"> </span>a<span class="_ _6"> </span>program<span class="_ _3"> </span>path,<span class="_ _6"> </span>which<span class="_ _6"> </span>may<span class="_ _3"> </span>cross<span class="_ _6"> </span>function<span class="_ _6"> </span>call</span></span></div><div class="t m0 x2f h5 y119 ff2 fs3 fc0 sc0 ls0 ws0">boundaries.<span class="_ _3"> </span>T<span class="_ _2"></span>raceMonk<span class="_ _2"></span>ey<span class="_ _5"> </span>focuses<span class="_ _3"> </span>on<span class="_ _3"> </span><span class="ffa">loop<span class="_ _5"> </span>traces</span>,<span class="_ _3"> </span>that<span class="_ _5"> </span>originate<span class="_ _3"> </span>at</div><div class="t m0 x2f h5 y11a ff2 fs3 fc0 sc0 ls0 ws0">a<span class="_ _3"> </span>loop<span class="_ _5"> </span>edge<span class="_ _3"> </span>and<span class="_ _3"> </span>represent<span class="_ _5"> </span>a<span class="_ _3"> </span>single<span class="_ _3"> </span>iteration<span class="_ _5"> </span>through<span class="_ _3"> </span>the<span class="_ _3"> </span>associated</div><div class="t m0 x2f h5 y11b ff2 fs3 fc0 sc0 ls0 ws0">loop.</div><div class="t m0 x34 h5 y11c ff2 fs3 fc0 sc0 ls0 ws0">Similar<span class="_ _6"> </span>to<span class="_ _8"> </span>an<span class="_ _6"> </span>extended<span class="_ _6"> </span>basic<span class="_ _6"> </span>block,<span class="_ _8"> </span>a<span class="_ _6"> </span>trace<span class="_ _8"> </span>is<span class="_ _6"> </span>only<span class="_ _6"> </span>entered<span class="_ _8"> </span>at</div><div class="t m0 x2f h5 y11d ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _3"> </span>top,<span class="_ _5"> </span>but<span class="_ _3"> </span>may<span class="_ _5"> </span>have<span class="_ _5"> </span>many<span class="_ _3"> </span>e<span class="_ _2"></span>xits.<span class="_ _3"> </span>In<span class="_ _5"> </span>contrast<span class="_ _3"> </span>to<span class="_ _3"> </span>an<span class="_ _5"> </span>extended<span class="_ _3"> </span>basic</div><div class="t m0 x2f h5 y11e ff2 fs3 fc0 sc0 ls0 ws0">block,<span class="_ _6"> </span>a<span class="_ _8"> </span>trace<span class="_ _8"> </span>can<span class="_ _8"> </span>contain<span class="_ _8"> </span>join<span class="_ _8"> </span>nodes.<span class="_ _6"> </span>Since<span class="_ _8"> </span>a<span class="_ _8"> </span>trace<span class="_ _8"> </span>always<span class="_ _6"> </span>only</div><div class="t m0 x2f h5 y11f ff2 fs3 fc0 sc0 ls0 ws0">follows<span class="_ _7"> </span>one<span class="_ _5"> </span>single<span class="_ _5"> </span>path<span class="_ _7"> </span>through<span class="_ _5"> </span>the<span class="_ _7"> </span>original<span class="_ _5"> </span>program,<span class="_ _5"> </span>ho<span class="_ _2"></span>we<span class="_ _2"></span>v<span class="_ _2"></span>er<span class="_ _2"></span>,<span class="_ _5"> </span>join</div><div class="t m0 x2f h5 y120 ff2 fs3 fc0 sc0 ls0 ws0">nodes<span class="_ _8"> </span>are<span class="_ _8"> </span>not<span class="_ _d"> </span>recognizable<span class="_ _6"> </span>as<span class="_ _d"> </span>such<span class="_ _6"> </span>in<span class="_ _d"> </span>a<span class="_ _8"> </span>trace<span class="_ _8"> </span>and<span class="_ _8"> </span>have<span class="_ _6"> </span>a<span class="_ _d"> </span>single</div><div class="t m0 x2f h5 y121 ff2 fs3 fc0 sc0 ls0 ws0">predecessor<span class="_ _5"> </span>node<span class="_ _5"> </span>like<span class="_ _5"> </span>regular<span class="_ _5"> </span>nodes.</div><div class="t m0 x34 h5 y122 ff2 fs3 fc0 sc0 ls0 ws0">A<span class="_ _5"> </span><span class="ffa">typed<span class="_ _5"> </span>trace<span class="_ _5"> </span></span>is<span class="_ _5"> </span>a<span class="_ _5"> </span>trace<span class="_ _3"> </span>annotated<span class="_ _5"> </span>with<span class="_ _5"> </span>a<span class="_ _5"> </span>type<span class="_ _5"> </span>for<span class="_ _5"> </span>ev<span class="_ _2"></span>ery<span class="_ _5"> </span>variable</div><div class="t m0 x2f h5 y123 ff2 fs3 fc0 sc0 ls0 ws0">(including<span class="_ _5"> </span>temporaries)<span class="_ _7"> </span>on<span class="_ _5"> </span>the<span class="_ _7"> </span>trace.<span class="_ _5"> </span>A<span class="_ _7"> </span>typed<span class="_ _5"> </span>trace<span class="_ _7"> </span>also<span class="_ _5"> </span>has<span class="_ _7"> </span>an<span class="_ _5"> </span>entry</div><div class="t m0 x2f h5 y124 ffa fs3 fc0 sc0 ls0 ws0">type<span class="_ _3"> </span>map<span class="_ _3"> </span><span class="ff2">gi<span class="_ _2"></span>ving<span class="_ _3"> </span>the<span class="_ _3"> </span>required<span class="_ _3"> </span>types<span class="_ _3"> </span>for<span class="_ _3"> </span>v<span class="_ _2"></span>ariables<span class="_ _3"> </span>used<span class="_ _3"> </span>on<span class="_ _3"> </span>the<span class="_ _3"> </span>trace</span></div><div class="t m0 x2f h5 y125 ff2 fs3 fc0 sc0 ls0 ws0">before<span class="_ _5"> </span>the<span class="_ _2"></span>y<span class="_ _5"> </span>are<span class="_ _5"> </span>defined.<span class="_ _7"> </span>For<span class="_ _5"> </span>e<span class="_ _2"></span>xample,<span class="_ _5"> </span>a<span class="_ _7"> </span>trace<span class="_ _5"> </span>could<span class="_ _5"> </span>ha<span class="_ _2"></span>ve<span class="_ _5"> </span>a<span class="_ _7"> </span>type<span class="_ _5"> </span>map</div><div class="t m0 x2f h5 y126 ff7 fs3 fc0 sc0 ls0 ws0">(x:<span class="_ _1"> </span>int,<span class="_ _e"> </span>b:<span class="_ _1"> </span>boolean)<span class="ff2">,<span class="_ _6"> </span>meaning<span class="_ _3"> </span>that<span class="_ _3"> </span>the<span class="_ _3"> </span>trace<span class="_ _3"> </span>may<span class="_ _6"> </span>be<span class="_ _3"> </span>entered</span></div><div class="t m0 x2f h5 y127 ff2 fs3 fc0 sc0 ls0 ws0">only<span class="_ _5"> </span>if<span class="_ _3"> </span>the<span class="_ _5"> </span>value<span class="_ _5"> </span>of<span class="_ _5"> </span>the<span class="_ _3"> </span>v<span class="_ _2"></span>ariable<span class="_ _5"> </span><span class="ff7">x<span class="_ _5"> </span></span>is<span class="_ _3"> </span>of<span class="_ _5"> </span>type<span class="_ _5"> </span><span class="ff7">int<span class="_ _3"> </span></span>and<span class="_ _5"> </span>the<span class="_ _5"> </span>value<span class="_ _5"> </span>of<span class="_ _3"> </span><span class="ff7">b</span></div><div class="t m0 x2f h5 y128 ff2 fs3 fc0 sc0 ls0 ws0">is<span class="_ _5"> </span>of<span class="_ _3"> </span>type<span class="_ _5"> </span><span class="ff7">boolean</span>.<span class="_ _3"> </span>The<span class="_ _5"> </span>entry<span class="_ _3"> </span>type<span class="_ _5"> </span>map<span class="_ _5"> </span>is<span class="_ _3"> </span>much<span class="_ _5"> </span>like<span class="_ _5"> </span>the<span class="_ _3"> </span>signature</div><div class="t m0 x2f h5 y129 ff2 fs3 fc0 sc0 ls0 ws0">of<span class="_ _5"> </span>a<span class="_ _5"> </span>function.</div><div class="t m0 x34 h5 y12a ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _6"> </span>this<span class="_ _8"> </span>paper<span class="_ _2"></span>,<span class="_ _6"> </span>we<span class="_ _6"> </span>only<span class="_ _6"> </span>discuss<span class="_ _8"> </span>typed<span class="_ _6"> </span>loop<span class="_ _8"> </span>traces,<span class="_ _6"> </span>and<span class="_ _8"> </span>we<span class="_ _6"> </span>will</div><div class="t m0 x2f h5 y12b ff2 fs3 fc0 sc0 ls0 ws0">refer<span class="_ _6"> </span>to<span class="_ _6"> </span>them<span class="_ _3"> </span>simply<span class="_ _6"> </span>as<span class="_ _6"> </span>“traces”.<span class="_ _6"> </span>The<span class="_ _3"> </span>key<span class="_ _6"> </span>property<span class="_ _6"> </span>of<span class="_ _3"> </span>typed<span class="_ _6"> </span>loop</div><div class="t m0 x2f h5 y12c ff2 fs3 fc0 sc0 ls0 ws0">traces<span class="_ _5"> </span>is<span class="_ _3"> </span>that<span class="_ _5"> </span>they<span class="_ _5"> </span>can<span class="_ _3"> </span>be<span class="_ _5"> </span>compiled<span class="_ _3"> </span>to<span class="_ _5"> </span>efficient<span class="_ _5"> </span>machine<span class="_ _3"> </span>code<span class="_ _5"> </span>using</div><div class="t m0 x2f h5 y12d ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _5"> </span>same<span class="_ _5"> </span>techniques<span class="_ _3"> </span>used<span class="_ _5"> </span>for<span class="_ _5"> </span>typed<span class="_ _5"> </span>languages.</div><div class="t m0 x34 h5 ycc ff2 fs3 fc0 sc0 ls0 ws0">In<span class="_ _5"> </span>TraceMonke<span class="_ _2"></span>y<span class="_ _b"></span>,<span class="_ _3"> </span>traces<span class="_ _5"> </span>are<span class="_ _5"> </span>recorded<span class="_ _3"> </span>in<span class="_ _5"> </span>trace-flav<span class="_ _2"></span>ored<span class="_ _5"> </span>SSA<span class="_ _3"> </span><span class="ffa">LIR</span></div><div class="t m0 x2f h5 ycd ff2 fs3 fc0 sc0 ls0 ws0">(low-le<span class="_ _2"></span>v<span class="_ _2"></span>el<span class="_ _3"> </span>intermediate<span class="_ _6"> </span>representation).<span class="_ _6"> </span>In<span class="_ _6"> </span>trace-fla<span class="_ _2"></span>v<span class="_ _2"></span>ored<span class="_ _6"> </span>SSA<span class="_ _3"> </span>(or</div><div class="t m0 x2f h5 yce ff2 fs3 fc0 sc0 ls0 ws0">TSSA),<span class="_ _3"> </span>phi<span class="_ _5"> </span>nodes<span class="_ _3"> </span>appear<span class="_ _5"> </span>only<span class="_ _3"> </span>at<span class="_ _3"> </span>the<span class="_ _5"> </span>entry<span class="_ _3"> </span>point,<span class="_ _5"> </span>which<span class="_ _3"> </span>is<span class="_ _5"> </span>reached</div><div class="t m0 x2f h5 ycf ff2 fs3 fc0 sc0 ls0 ws0">both<span class="_ _6"> </span>on<span class="_ _8"> </span>entry<span class="_ _8"> </span>and<span class="_ _8"> </span>via<span class="_ _6"> </span>loop<span class="_ _8"> </span>edges.<span class="_ _8"> </span>The<span class="_ _8"> </span>important<span class="_ _6"> </span>LIR<span class="_ _8"> </span>primitives</div><div class="t m0 x2f h5 y12e ff2 fs3 fc0 sc0 ls0 ws0">are<span class="_ _1"> </span>constant<span class="_ _d"> </span>values,<span class="_ _1"> </span>memory<span class="_ _1"> </span>loads<span class="_ _d"> </span>and<span class="_ _1"> </span>stores<span class="_ _1"> </span>(by<span class="_ _d"> </span>address<span class="_ _1"> </span>and</div><div class="t m0 x2f h5 yd1 ff2 fs3 fc0 sc0 ls0 ws0">offset),<span class="_ _6"> </span>integer<span class="_ _6"> </span>operators,<span class="_ _8"> </span>floating-point<span class="_ _6"> </span>operators,<span class="_ _8"> </span>function<span class="_ _8"> </span>calls,</div><div class="t m0 x2f h5 yd2 ff2 fs3 fc0 sc0 ls0 ws0">and<span class="_ _3"> </span>conditional<span class="_ _5"> </span>exits.<span class="_ _5"> </span>T<span class="_ _2"></span>ype<span class="_ _5"> </span>con<span class="_ _2"></span>versions,<span class="_ _5"> </span>such<span class="_ _3"> </span>as<span class="_ _5"> </span>integer<span class="_ _3"> </span>to<span class="_ _5"> </span>double,</div><div class="t m0 x2f h5 yd3 ff2 fs3 fc0 sc0 ls0 ws0">are<span class="_ _d"> </span>represented<span class="_ _d"> </span>by<span class="_ _d"> </span>function<span class="_ _d"> </span>calls.<span class="_ _1"> </span>This<span class="_ _8"> </span>makes<span class="_ _d"> </span>the<span class="_ _1"> </span>LIR<span class="_ _8"> </span>used<span class="_ _1"> </span>by</div><div class="t m0 x2f h5 y94 ff2 fs3 fc0 sc0 ls0 ws0">T<span class="_ _2"></span>raceMonke<span class="_ _2"></span>y<span class="_ _8"> </span>independent<span class="_ _8"> </span>of<span class="_ _8"> </span>the<span class="_ _8"> </span>concrete<span class="_ _8"> </span>type<span class="_ _8"> </span>system<span class="_ _8"> </span>and<span class="_ _8"> </span>type</div><div class="t m0 x2f h5 y95 ff2 fs3 fc0 sc0 ls0 ws0">con<span class="_ _2"></span>version<span class="_ _6"> </span>rules<span class="_ _6"> </span>of<span class="_ _6"> </span>the<span class="_ _8"> </span>source<span class="_ _6"> </span>language.<span class="_ _8"> </span>The<span class="_ _6"> </span>LIR<span class="_ _6"> </span>operations<span class="_ _8"> </span>are</div><div class="t m0 x2f h5 y96 ff2 fs3 fc0 sc0 ls0 ws0">generic<span class="_ _5"> </span>enough<span class="_ _5"> </span>that<span class="_ _7"> </span>the<span class="_ _5"> </span>backend<span class="_ _5"> </span>compiler<span class="_ _7"> </span>is<span class="_ _5"> </span>language<span class="_ _5"> </span>independent.</div><div class="t m0 x2f h5 y97 ff2 fs3 fc0 sc0 ls0 ws0">Figure<span class="_ _5"> </span>3<span class="_ _5"> </span>shows<span class="_ _5"> </span>an<span class="_ _5"> </span>example<span class="_ _5"> </span>LIR<span class="_ _5"> </span>trace.</div><div class="t m0 x34 h5 y98 ff2 fs3 fc0 sc0 ls0 ws0">Bytecode<span class="_ _d"> </span>interpreters<span class="_ _1"> </span>typically<span class="_ _d"> </span>represent<span class="_ _d"> </span>values<span class="_ _d"> </span>in<span class="_ _d"> </span>a<span class="_ _d"> </span>various</div><div class="t m0 x2f h5 y99 ff2 fs3 fc0 sc0 ls0 ws0">complex<span class="_ _3"> </span>data<span class="_ _3"> </span>structures<span class="_ _3"> </span>(e.g.,<span class="_ _3"> </span>hash<span class="_ _3"> </span>tables)<span class="_ _3"> </span>in<span class="_ _3"> </span>a<span class="_ _3"> </span>box<span class="_ _2"></span>ed<span class="_ _3"> </span>format<span class="_ _3"> </span>(i.e.,</div><div class="t m0 x2f h5 y9a ff2 fs3 fc0 sc0 ls0 ws0">with<span class="_ _3"> </span>attached<span class="_ _3"> </span>type<span class="_ _3"> </span>tag<span class="_ _3"> </span>bits).<span class="_ _3"> </span>Since<span class="_ _6"> </span>a<span class="_ _3"> </span>trace<span class="_ _3"> </span>is<span class="_ _3"> </span>intended<span class="_ _3"> </span>to<span class="_ _3"> </span>represent</div><div class="t m0 x2f h5 y9b ff2 fs3 fc0 sc0 ls0 ws0">efficient<span class="_ _3"> </span>code<span class="_ _6"> </span>that<span class="_ _3"> </span>eliminates<span class="_ _6"> </span>all<span class="_ _3"> </span>that<span class="_ _6"> </span>complexity<span class="_ _b"></span>,<span class="_ _6"> </span>our<span class="_ _3"> </span>traces<span class="_ _6"> </span>oper-</div><div class="t m0 x2f h5 y9c ff2 fs3 fc0 sc0 ls0 ws0">ate<span class="_ _6"> </span>on<span class="_ _3"> </span>unboxed<span class="_ _6"> </span>v<span class="_ _2"></span>alues<span class="_ _6"> </span>in<span class="_ _3"> </span>simple<span class="_ _6"> </span>variables<span class="_ _3"> </span>and<span class="_ _6"> </span>arrays<span class="_ _6"> </span>as<span class="_ _3"> </span>much<span class="_ _6"> </span>as</div><div class="t m0 x2f h5 y9d ff2 fs3 fc0 sc0 ls0 ws0">possible.</div><div class="t m0 x33 h5 y5b ff2 fs3 fc0 sc0 ls0 ws0">A<span class="_ _3"> </span>trace<span class="_ _3"> </span>records<span class="_ _3"> </span>all<span class="_ _3"> </span>its<span class="_ _5"> </span>intermediate<span class="_ _3"> </span>values<span class="_ _3"> </span>in<span class="_ _3"> </span>a<span class="_ _3"> </span>small<span class="_ _5"> </span>activ<span class="_ _2"></span>ation</div><div class="t m0 x32 h5 y5c ff2 fs3 fc0 sc0 ls0 ws0">record<span class="_ _3"> </span>area.<span class="_ _5"> </span>T<span class="_ _b"></span>o<span class="_ _3"> </span>make<span class="_ _5"> </span>variable<span class="_ _5"> </span>accesses<span class="_ _3"> </span>fast<span class="_ _5"> </span>on<span class="_ _3"> </span>trace,<span class="_ _5"> </span>the<span class="_ _3"> </span>trace<span class="_ _3"> </span>also</div><div class="t m0 x32 h5 y5d ff2 fs3 fc0 sc0 ls0 ws0">imports<span class="_ _3"> </span>local<span class="_ _3"> </span>and<span class="_ _3"> </span>global<span class="_ _3"> </span>v<span class="_ _2"></span>ariables<span class="_ _3"> </span>by<span class="_ _3"> </span>unboxing<span class="_ _3"> </span>them<span class="_ _3"> </span>and<span class="_ _5"> </span>copying</div><div class="t m0 x32 h5 y5e ff2 fs3 fc0 sc0 ls0 ws0">them<span class="_ _8"> </span>to<span class="_ _6"> </span>its<span class="_ _8"> </span>activation<span class="_ _6"> </span>record.<span class="_ _8"> </span>Thus,<span class="_ _8"> </span>the<span class="_ _6"> </span>trace<span class="_ _8"> </span>can<span class="_ _8"> </span>read<span class="_ _8"> </span>and<span class="_ _8"> </span>write</div><div class="t m0 x32 h5 y5f ff2 fs3 fc0 sc0 ls0 ws0">these<span class="_ _5"> </span>v<span class="_ _2"></span>ariables<span class="_ _7"> </span>with<span class="_ _5"> </span>simple<span class="_ _7"> </span>loads<span class="_ _7"> </span>and<span class="_ _5"> </span>stores<span class="_ _7"> </span>from<span class="_ _5"> </span>a<span class="_ _7"> </span>nativ<span class="_ _2"></span>e<span class="_ _5"> </span>acti<span class="_ _2"></span>v<span class="_ _2"></span>ation</div><div class="t m0 x32 h5 y60 ff2 fs3 fc0 sc0 ls0 ws0">recording,<span class="_ _d"> </span>independently<span class="_ _d"> </span>of<span class="_ _d"> </span>the<span class="_ _d"> </span>boxing<span class="_ _d"> </span>mechanism<span class="_ _d"> </span>used<span class="_ _d"> </span>by<span class="_ _d"> </span>the</div><div class="t m0 x32 h5 y61 ff2 fs3 fc0 sc0 ls0 ws0">interpreter<span class="_ _2"></span>.<span class="_ _6"> </span>When<span class="_ _6"> </span>the<span class="_ _8"> </span>trace<span class="_ _8"> </span>exits,<span class="_ _6"> </span>the<span class="_ _8"> </span>VM<span class="_ _8"> </span>boxes<span class="_ _6"> </span>the<span class="_ _8"> </span>values<span class="_ _6"> </span>from</div><div class="t m0 x32 h5 y62 ff2 fs3 fc0 sc0 ls0 ws0">this<span class="_ _5"> </span>native<span class="_ _5"> </span>storage<span class="_ _3"> </span>location<span class="_ _5"> </span>and<span class="_ _5"> </span>copies<span class="_ _3"> </span>them<span class="_ _5"> </span>back<span class="_ _3"> </span>to<span class="_ _5"> </span>the<span class="_ _5"> </span>interpreter</div><div class="t m0 x32 h5 y63 ff2 fs3 fc0 sc0 ls0 ws0">structures.</div><div class="t m0 x33 h5 y7 ff2 fs3 fc0 sc0 ls0 ws0">For<span class="_ _e"> </span>every<span class="_ _e"> </span>control-flow<span class="_ _e"> </span>branch<span class="_ _1b"> </span>in<span class="_ _1b"> </span>the<span class="_ _e"> </span>source<span class="_ _1b"> </span>program,<span class="_ _e"> </span>the</div><div class="t m0 x32 h5 y64 ff2 fs3 fc0 sc0 ls0 ws0">recorder<span class="_ _5"> </span>generates<span class="_ _5"> </span>conditional<span class="_ _5"> </span>e<span class="_ _2"></span>xit<span class="_ _5"> </span>LIR<span class="_ _5"> </span>inst<span class="_ _2"></span>ructions.<span class="_ _5"> </span>These<span class="_ _5"> </span>instruc-</div><div class="t m0 x32 h5 y66 ff2 fs3 fc0 sc0 ls0 ws0">tions<span class="_ _3"> </span>exit<span class="_ _3"> </span>from<span class="_ _6"> </span>the<span class="_ _3"> </span>trace<span class="_ _6"> </span>if<span class="_ _3"> </span>required<span class="_ _3"> </span>control<span class="_ _6"> </span>flo<span class="_ _2"></span>w<span class="_ _3"> </span>is<span class="_ _6"> </span>dif<span class="_ _2"></span>ferent<span class="_ _3"> </span>from</div><div class="t m0 x32 h5 y67 ff2 fs3 fc0 sc0 ls0 ws0">what<span class="_ _3"> </span>it<span class="_ _3"> </span>was<span class="_ _3"> </span>at<span class="_ _3"> </span>trace<span class="_ _3"> </span>recording,<span class="_ _3"> </span>ensuring<span class="_ _3"> </span>that<span class="_ _3"> </span>the<span class="_ _6"> </span>trace<span class="_ _3"> </span>instructions</div><div class="t m0 x32 h5 y68 ff2 fs3 fc0 sc0 ls0 ws0">are<span class="_ _d"> </span>run<span class="_ _8"> </span>only<span class="_ _d"> </span>if<span class="_ _8"> </span>they<span class="_ _8"> </span>are<span class="_ _d"> </span>supposed<span class="_ _d"> </span>to.<span class="_ _8"> </span>W<span class="_ _2"></span>e<span class="_ _6"> </span>call<span class="_ _d"> </span>these<span class="_ _d"> </span>instructions</div><div class="t m0 x32 h5 y69 ffa fs3 fc0 sc0 ls0 ws0">guar<span class="_ _2"></span>d<span class="_ _3"> </span><span class="ff2">instructions.</span></div><div class="t m0 x33 h5 y6a ff2 fs3 fc0 sc0 ls0 ws0">Most<span class="_ _5"> </span>of<span class="_ _7"> </span>our<span class="_ _7"> </span>traces<span class="_ _5"> </span>represent<span class="_ _7"> </span>loops<span class="_ _5"> </span>and<span class="_ _7"> </span>end<span class="_ _7"> </span>with<span class="_ _5"> </span>the<span class="_ _7"> </span>special<span class="_ _5"> </span><span class="ff7">loop</span></div><div class="t m0 x32 h5 y6b ff2 fs3 fc0 sc0 ls0 ws0">LIR<span class="_ _3"> </span>instruction.<span class="_ _3"> </span>This<span class="_ _3"> </span>is<span class="_ _3"> </span>just<span class="_ _3"> </span>an<span class="_ _3"> </span>unconditional<span class="_ _3"> </span>branch<span class="_ _3"> </span>to<span class="_ _3"> </span>the<span class="_ _3"> </span>top<span class="_ _3"> </span>of</div><div class="t m0 x32 h5 y6c ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _5"> </span>trace.<span class="_ _5"> </span>Such<span class="_ _3"> </span>traces<span class="_ _5"> </span>return<span class="_ _5"> </span>only<span class="_ _5"> </span>via<span class="_ _5"> </span>guards.</div><div class="t m0 x33 h5 y6d ff2 fs3 fc0 sc0 ls0 ws0">Now<span class="_ _b"></span>,<span class="_ _3"> </span>we<span class="_ _6"> </span>describe<span class="_ _3"> </span>the<span class="_ _6"> </span>ke<span class="_ _2"></span>y<span class="_ _3"> </span>optimizations<span class="_ _6"> </span>that<span class="_ _3"> </span>are<span class="_ _3"> </span>performed<span class="_ _6"> </span>as</div><div class="t m0 x32 h5 y6e ff2 fs3 fc0 sc0 ls0 ws0">part<span class="_ _3"> </span>of<span class="_ _6"> </span>recording<span class="_ _3"> </span>LIR.<span class="_ _3"> </span>All<span class="_ _3"> </span>of<span class="_ _6"> </span>these<span class="_ _3"> </span>optimizations<span class="_ _3"> </span>reduce<span class="_ _6"> </span>complex</div><div class="t m0 x32 h5 y6f ff2 fs3 fc0 sc0 ls0 ws0">dynamic<span class="_ _8"> </span>language<span class="_ _8"> </span>constructs<span class="_ _8"> </span>to<span class="_ _d"> </span>simple<span class="_ _8"> </span>typed<span class="_ _8"> </span>constructs<span class="_ _8"> </span>by<span class="_ _8"> </span>spe-</div><div class="t m0 x32 h5 y70 ff2 fs3 fc0 sc0 ls0 ws0">cializing<span class="_ _5"> </span>for<span class="_ _5"> </span>the<span class="_ _5"> </span>current<span class="_ _5"> </span>trace.<span class="_ _5"> </span>Each<span class="_ _5"> </span>optimization<span class="_ _5"> </span>requires<span class="_ _5"> </span>guard<span class="_ _5"> </span>in-</div><div class="t m0 x32 h5 y71 ff2 fs3 fc0 sc0 ls0 ws0">structions<span class="_ _6"> </span>to<span class="_ _3"> </span>verify<span class="_ _6"> </span>their<span class="_ _6"> </span>assumptions<span class="_ _3"> </span>about<span class="_ _6"> </span>the<span class="_ _6"> </span>state<span class="_ _6"> </span>and<span class="_ _3"> </span>exit<span class="_ _6"> </span>the</div><div class="t m0 x32 h5 y72 ff2 fs3 fc0 sc0 ls0 ws0">trace<span class="_ _5"> </span>if<span class="_ _5"> </span>necessary<span class="_ _2"></span>.</div><div class="t m0 x33 hc y74 ff1 fs3 fc0 sc0 ls0 ws0">T<span class="_ _b"></span>ype<span class="_ _3"> </span>specialization.</div><div class="t m0 x33 h5 y75 ff2 fs3 fc0 sc0 ls0 ws0">All<span class="_ _6"> </span>LIR<span class="_ _8"> </span>primiti<span class="_ _2"></span>ves<span class="_ _6"> </span>apply<span class="_ _6"> </span>to<span class="_ _8"> </span>operands<span class="_ _6"> </span>of<span class="_ _8"> </span>specific<span class="_ _6"> </span>types.<span class="_ _6"> </span>Thus,</div><div class="t m0 x32 h5 y76 ff2 fs3 fc0 sc0 ls0 ws0">LIR<span class="_ _d"> </span>traces<span class="_ _d"> </span>are<span class="_ _d"> </span>necessarily<span class="_ _d"> </span>type-specialized,<span class="_ _d"> </span>and<span class="_ _d"> </span>a<span class="_ _d"> </span>compiler<span class="_ _d"> </span>can</div><div class="t m0 x32 h5 y77 ff2 fs3 fc0 sc0 ls0 ws0">easily<span class="_ _d"> </span>produce<span class="_ _d"> </span>a<span class="_ _d"> </span>translation<span class="_ _8"> </span>that<span class="_ _d"> </span>requires<span class="_ _d"> </span>no<span class="_ _d"> </span>type<span class="_ _d"> </span>dispatches.<span class="_ _d"> </span>A</div><div class="t m0 x32 h5 y78 ff2 fs3 fc0 sc0 ls0 ws0">typical<span class="_ _3"> </span>bytecode<span class="_ _3"> </span>interpreter<span class="_ _5"> </span>carries<span class="_ _3"> </span>tag<span class="_ _3"> </span>bits<span class="_ _3"> </span>along<span class="_ _5"> </span>with<span class="_ _3"> </span>each<span class="_ _3"> </span>v<span class="_ _2"></span>alue,</div><div class="t m0 x32 h5 y79 ff2 fs3 fc0 sc0 ls0 ws0">and<span class="_ _5"> </span>to<span class="_ _5"> </span>perform<span class="_ _5"> </span>any<span class="_ _5"> </span>operation,<span class="_ _5"> </span>must<span class="_ _5"> </span>check<span class="_ _5"> </span>the<span class="_ _5"> </span>tag<span class="_ _5"> </span>bits,<span class="_ _5"> </span>dynamically</div><div class="t m0 x32 h5 y7a ff2 fs3 fc0 sc0 ls0 ws0">dispatch,<span class="_ _1"> </span>mask<span class="_ _d"> </span>out<span class="_ _1"> </span>the<span class="_ _1"> </span>tag<span class="_ _d"> </span>bits<span class="_ _1"> </span>to<span class="_ _1"> </span>reco<span class="_ _2"></span>ver<span class="_ _d"> </span>the<span class="_ _1"> </span>untagged<span class="_ _1"> </span>v<span class="_ _2"></span>alue,</div><div class="t m0 x32 h5 y7b ff2 fs3 fc0 sc0 ls0 ws0">perform<span class="_ _5"> </span>the<span class="_ _5"> </span>operation,<span class="_ _5"> </span>and<span class="_ _5"> </span>then<span class="_ _5"> </span>reappl<span class="_ _2"></span>y<span class="_ _5"> </span>tags.<span class="_ _5"> </span>LIR<span class="_ _5"> </span>omits<span class="_ _5"> </span>e<span class="_ _2"></span>v<span class="_ _2"></span>erything</div><div class="t m0 x32 h5 y7c ff2 fs3 fc0 sc0 ls0 ws0">except<span class="_ _5"> </span>the<span class="_ _5"> </span>operation<span class="_ _5"> </span>itself.</div><div class="t m0 x33 h5 y7d ff2 fs3 fc0 sc0 ls0 ws0">A<span class="_ _5"> </span>potential<span class="_ _5"> </span>problem<span class="_ _5"> </span>is<span class="_ _5"> </span>that<span class="_ _5"> </span>some<span class="_ _5"> </span>operations<span class="_ _5"> </span>can<span class="_ _3"> </span>produce<span class="_ _5"> </span>v<span class="_ _2"></span>alues</div><div class="t m0 x32 h5 y7e ff2 fs3 fc0 sc0 ls0 ws0">of<span class="_ _6"> </span>unpredictable<span class="_ _8"> </span>types.<span class="_ _6"> </span>For<span class="_ _6"> </span>example,<span class="_ _6"> </span>reading<span class="_ _6"> </span>a<span class="_ _8"> </span>property<span class="_ _6"> </span>from<span class="_ _8"> </span>an</div><div class="t m0 x32 h5 y7f ff2 fs3 fc0 sc0 ls0 ws0">object<span class="_ _8"> </span>could<span class="_ _d"> </span>yield<span class="_ _8"> </span>a<span class="_ _d"> </span>v<span class="_ _2"></span>alue<span class="_ _8"> </span>of<span class="_ _d"> </span>any<span class="_ _8"> </span>type,<span class="_ _d"> </span>not<span class="_ _8"> </span>necessarily<span class="_ _8"> </span>the<span class="_ _d"> </span>type</div><div class="t m0 x32 h5 y80 ff2 fs3 fc0 sc0 ls0 ws0">observed<span class="_ _3"> </span>during<span class="_ _6"> </span>recording.<span class="_ _6"> </span>The<span class="_ _6"> </span>recorder<span class="_ _3"> </span>emits<span class="_ _6"> </span>guard<span class="_ _6"> </span>instructions</div><div class="t m0 x32 h5 y81 ff2 fs3 fc0 sc0 ls0 ws0">that<span class="_ _3"> </span>conditionally<span class="_ _5"> </span>exit<span class="_ _3"> </span>if<span class="_ _3"> </span>the<span class="_ _5"> </span>operation<span class="_ _3"> </span>yields<span class="_ _3"> </span>a<span class="_ _5"> </span>value<span class="_ _3"> </span>of<span class="_ _5"> </span>a<span class="_ _3"> </span>dif<span class="_ _2"></span>ferent</div><div class="t m0 x32 h5 y82 ff2 fs3 fc0 sc0 ls0 ws0">type<span class="_ _d"> </span>from<span class="_ _1"> </span>that<span class="_ _d"> </span>seen<span class="_ _1"> </span>during<span class="_ _d"> </span>recording.<span class="_ _1"> </span>These<span class="_ _d"> </span>guard<span class="_ _d"> </span>instructions</div><div class="t m0 x32 h5 y83 ff2 fs3 fc0 sc0 ls0 ws0">guarantee<span class="_ _3"> </span>that<span class="_ _5"> </span>as<span class="_ _3"> </span>long<span class="_ _3"> </span>as<span class="_ _3"> </span>e<span class="_ _2"></span>x<span class="_ _2"></span>ecution<span class="_ _3"> </span>is<span class="_ _5"> </span>on<span class="_ _3"> </span>trace,<span class="_ _3"> </span>the<span class="_ _5"> </span>types<span class="_ _3"> </span>of<span class="_ _3"> </span>v<span class="_ _2"></span>alues</div><div class="t m0 x32 h5 y84 ff2 fs3 fc0 sc0 ls0 ws0">match<span class="_ _3"> </span>those<span class="_ _5"> </span>of<span class="_ _3"> </span>the<span class="_ _3"> </span>typed<span class="_ _5"> </span>trace.<span class="_ _3"> </span>When<span class="_ _3"> </span>the<span class="_ _5"> </span>VM<span class="_ _3"> </span>observes<span class="_ _5"> </span>a<span class="_ _3"> </span>side<span class="_ _3"> </span>e<span class="_ _2"></span>xit</div><div class="t m0 x32 h5 y85 ff2 fs3 fc0 sc0 ls0 ws0">along<span class="_ _3"> </span>such<span class="_ _5"> </span>a<span class="_ _3"> </span>type<span class="_ _3"> </span>guard,<span class="_ _5"> </span>a<span class="_ _3"> </span>ne<span class="_ _2"></span>w<span class="_ _3"> </span>typed<span class="_ _5"> </span>trace<span class="_ _3"> </span>is<span class="_ _3"> </span>recorded<span class="_ _5"> </span>originating</div><div class="t m0 x32 h5 y86 ff2 fs3 fc0 sc0 ls0 ws0">at<span class="_ _5"> </span>the<span class="_ _3"> </span>side<span class="_ _5"> </span>exit<span class="_ _5"> </span>location,<span class="_ _3"> </span>capturing<span class="_ _5"> </span>the<span class="_ _3"> </span>ne<span class="_ _2"></span>w<span class="_ _5"> </span>type<span class="_ _5"> </span>of<span class="_ _3"> </span>the<span class="_ _5"> </span>operation<span class="_ _3"> </span>in</div><div class="t m0 x32 h5 y87 ff2 fs3 fc0 sc0 ls0 ws0">question.</div><div class="t m0 x33 h5 y88 ff1 fs3 fc0 sc0 ls0 ws0">Representation<span class="_ _8"> </span>specialization:<span class="_ _d"> </span>objects.<span class="_ _d"> </span><span class="ff2">In<span class="_ _d"> </span>Ja<span class="_ _2"></span>v<span class="_ _2"></span>aScript,<span class="_ _d"> </span>name</span></div><div class="t m0 x32 h5 y89 ff2 fs3 fc0 sc0 ls0 ws0">lookup<span class="_ _6"> </span>semantics<span class="_ _6"> </span>are<span class="_ _6"> </span>complex<span class="_ _3"> </span>and<span class="_ _6"> </span>potentially<span class="_ _6"> </span>expensiv<span class="_ _2"></span>e<span class="_ _6"> </span>because</div><div class="t m0 x32 h5 y12f ff2 fs3 fc0 sc0 ls0 ws0">they<span class="_ _5"> </span>include<span class="_ _3"> </span>features<span class="_ _5"> </span>like<span class="_ _5"> </span>object<span class="_ _5"> </span>inheritance<span class="_ _3"> </span>and<span class="_ _5"> </span><span class="ff7">eval</span>.<span class="_ _5"> </span>T<span class="_ _2"></span>o<span class="_ _5"> </span>ev<span class="_ _2"></span>aluate</div><div class="t m0 x32 h5 y130 ff2 fs3 fc0 sc0 ls0 ws0">an<span class="_ _6"> </span>object<span class="_ _6"> </span>property<span class="_ _6"> </span>read<span class="_ _8"> </span>expression<span class="_ _6"> </span>like<span class="_ _6"> </span><span class="ff7">o.x</span>,<span class="_ _6"> </span>the<span class="_ _6"> </span>interpreter<span class="_ _6"> </span>must</div><div class="t m0 x32 h5 y131 ff2 fs3 fc0 sc0 ls0 ws0">search<span class="_ _3"> </span>the<span class="_ _5"> </span>property<span class="_ _3"> </span>map<span class="_ _3"> </span>of<span class="_ _5"> </span><span class="ff7">o<span class="_ _3"> </span></span>and<span class="_ _3"> </span>all<span class="_ _5"> </span>of<span class="_ _3"> </span>its<span class="_ _3"> </span>prototypes<span class="_ _5"> </span>and<span class="_ _3"> </span>parents.</div><div class="t m0 x32 h5 y132 ff2 fs3 fc0 sc0 ls0 ws0">Property<span class="_ _6"> </span>maps<span class="_ _6"> </span>can<span class="_ _6"> </span>be<span class="_ _6"> </span>implemented<span class="_ _6"> </span>with<span class="_ _6"> </span>dif<span class="_ _2"></span>ferent<span class="_ _6"> </span>data<span class="_ _6"> </span>structures</div><div class="t m0 x32 h5 y133 ff2 fs3 fc0 sc0 ls0 ws0">(e.g.,<span class="_ _6"> </span>per-object<span class="_ _6"> </span>hash<span class="_ _6"> </span>tables<span class="_ _6"> </span>or<span class="_ _6"> </span>shared<span class="_ _6"> </span>hash<span class="_ _6"> </span>tables),<span class="_ _6"> </span>so<span class="_ _6"> </span>the<span class="_ _8"> </span>search</div><div class="t m0 x32 h5 y134 ff2 fs3 fc0 sc0 ls0 ws0">process<span class="_ _d"> </span>also<span class="_ _8"> </span>must<span class="_ _d"> </span>dispatch<span class="_ _d"> </span>on<span class="_ _8"> </span>the<span class="_ _d"> </span>representation<span class="_ _d"> </span>of<span class="_ _8"> </span>each<span class="_ _d"> </span>object</div><div class="t m0 x32 h5 y135 ff2 fs3 fc0 sc0 ls0 ws0">found<span class="_ _5"> </span>during<span class="_ _7"> </span>search.<span class="_ _5"> </span>T<span class="_ _2"></span>raceMonk<span class="_ _2"></span>ey<span class="_ _7"> </span>can<span class="_ _5"> </span>simply<span class="_ _5"> </span>observ<span class="_ _2"></span>e<span class="_ _7"> </span>the<span class="_ _5"> </span>result<span class="_ _5"> </span>of</div><div class="t m0 x32 h5 y136 ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _3"> </span>search<span class="_ _3"> </span>process<span class="_ _3"> </span>and<span class="_ _3"> </span>record<span class="_ _6"> </span>the<span class="_ _3"> </span>simplest<span class="_ _3"> </span>possible<span class="_ _3"> </span>LIR<span class="_ _3"> </span>to<span class="_ _3"> </span>access</div><div class="t m0 x32 h5 y137 ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _5"> </span>property<span class="_ _5"> </span>v<span class="_ _2"></span>alue.<span class="_ _7"> </span>For<span class="_ _5"> </span>e<span class="_ _2"></span>xample,<span class="_ _5"> </span>the<span class="_ _5"> </span>search<span class="_ _7"> </span>might<span class="_ _5"> </span>finds<span class="_ _5"> </span>the<span class="_ _7"> </span>value<span class="_ _5"> </span>of</div><div class="t m0 x32 h5 y138 ff7 fs3 fc0 sc0 ls0 ws0">o.x<span class="_ _5"> </span><span class="ff2">in<span class="_ _5"> </span>the<span class="_ _5"> </span>prototype<span class="_ _5"> </span>of<span class="_ _5"> </span></span>o<span class="ff2">,<span class="_ _5"> </span>which<span class="_ _5"> </span>uses<span class="_ _5"> </span>a<span class="_ _5"> </span>shared<span class="_ _5"> </span>hash-table<span class="_ _5"> </span>represen-</span></div><div class="t m0 x32 h5 y139 ff2 fs3 fc0 sc0 ls0 ws0">tation<span class="_ _5"> </span>that<span class="_ _5"> </span>places<span class="_ _5"> </span><span class="ff7">x<span class="_ _5"> </span></span>in<span class="_ _5"> </span>sl<span class="_ _2"></span>ot<span class="_ _5"> </span>2<span class="_ _5"> </span>of<span class="_ _5"> </span>a<span class="_ _5"> </span>property<span class="_ _7"> </span>vector<span class="_ _2"></span>.<span class="_ _5"> </span>Then<span class="_ _5"> </span>the<span class="_ _5"> </span>recorded</div><div class="t m0 x32 h5 y13a ff2 fs3 fc0 sc0 ls0 ws0">can<span class="_ _5"> </span>generate<span class="_ _5"> </span>LIR<span class="_ _5"> </span>that<span class="_ _7"> </span>reads<span class="_ _5"> </span><span class="ff7">o.x<span class="_ _5"> </span></span>with<span class="_ _5"> </span>just<span class="_ _5"> </span>tw<span class="_ _2"></span>o<span class="_ _5"> </span>or<span class="_ _7"> </span>three<span class="_ _5"> </span>loads:<span class="_ _5"> </span>one<span class="_ _5"> </span>to</div><div class="t m0 x32 h5 y13b ff2 fs3 fc0 sc0 ls0 ws0">get<span class="_ _5"> </span>the<span class="_ _5"> </span>prototype,<span class="_ _7"> </span>possibly<span class="_ _5"> </span>one<span class="_ _5"> </span>to<span class="_ _5"> </span>get<span class="_ _5"> </span>the<span class="_ _7"> </span>property<span class="_ _5"> </span>value<span class="_ _5"> </span>v<span class="_ _2"></span>ector<span class="_ _2"></span>,<span class="_ _5"> </span>and</div><div class="t m0 x32 h5 y13c ff2 fs3 fc0 sc0 ls0 ws0">one<span class="_ _5"> </span>more<span class="_ _3"> </span>to<span class="_ _5"> </span>get<span class="_ _5"> </span>slot<span class="_ _3"> </span>2<span class="_ _5"> </span>from<span class="_ _5"> </span>the<span class="_ _3"> </span>v<span class="_ _2"></span>ector<span class="_ _2"></span>.<span class="_ _5"> </span>This<span class="_ _5"> </span>is<span class="_ _3"> </span>a<span class="_ _5"> </span>v<span class="_ _2"></span>ast<span class="_ _5"> </span>simplification</div><div class="t m0 x32 h5 y13d ff2 fs3 fc0 sc0 ls0 ws0">and<span class="_ _5"> </span>speedup<span class="_ _3"> </span>compared<span class="_ _5"> </span>to<span class="_ _5"> </span>the<span class="_ _3"> </span>original<span class="_ _5"> </span>interpreter<span class="_ _5"> </span>code.<span class="_ _3"> </span>Inheritance</div><div class="t m0 x32 h5 y13e ff2 fs3 fc0 sc0 ls0 ws0">relationships<span class="_ _3"> </span>and<span class="_ _3"> </span>object<span class="_ _3"> </span>representations<span class="_ _3"> </span>can<span class="_ _3"> </span>change<span class="_ _3"> </span>during<span class="_ _3"> </span>execu-</div><div class="t m0 x32 h5 y13f ff2 fs3 fc0 sc0 ls0 ws0">tion,<span class="_ _3"> </span>so<span class="_ _3"> </span>the<span class="_ _5"> </span>simplified<span class="_ _3"> </span>code<span class="_ _3"> </span>requires<span class="_ _5"> </span>guard<span class="_ _3"> </span>instructions<span class="_ _3"> </span>that<span class="_ _3"> </span>ensure</div><div class="t m0 x32 h5 y140 ff2 fs3 fc0 sc0 ls0 ws0">the<span class="_ _5"> </span>object<span class="_ _7"> </span>representation<span class="_ _7"> </span>is<span class="_ _5"> </span>the<span class="_ _7"> </span>same.<span class="_ _5"> </span>In<span class="_ _7"> </span>T<span class="_ _2"></span>raceMonkey<span class="_ _b"></span>,<span class="_ _5"> </span>objects’<span class="_ _7"> </span>rep-</div></div><div class="pi" data-data='{"ctm":[1.673203,0.000000,0.000000,1.673203,0.000000,0.000000]}'></div></div></div>