Chapter 11: Global Code Motion

Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

1 files changed, 309 insertions, 0 deletions

diff --git a/docs/chapter11/graph2.svg b/docs/chapter11/graph2.svg
new file mode 100644
index 00000000..00f7b594
--- /dev/null
+++ b/docs/chapter11/graph2.svg
@@ -0,0 +1,309 @@
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 2.43.0 (0)
+ -->
+<!-- Title: chapter11 Pages: 1 -->
+<svg width="346pt" height="636pt"
+ viewBox="0.00 0.00 346.00 636.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 632)">
+<title>chapter11</title>
+<polygon fill="white" stroke="transparent" points="-4,4 -4,-632 342,-632 342,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="black" points="8,-8 8,-620 330,-620 330,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="yellow" stroke="transparent" points="137,-583 137,-608 243,-608 243,-583 137,-583"/>
+<polygon fill="none" stroke="black" points="137,-583 137,-608 243,-608 243,-583 137,-583"/>
+<text text-anchor="start" x="171.5" y="-591.8" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="none" stroke="black" points="137,-552 137,-583 243,-583 243,-552 137,-552"/>
+<polygon fill="yellow" stroke="transparent" points="142,-557 142,-578 182,-578 182,-557 142,-557"/>
+<polygon fill="none" stroke="black" points="142,-557 142,-578 182,-578 182,-557 142,-557"/>
+<text text-anchor="start" x="145" y="-563.8" font-family="Times,serif" font-size="14.00">$ctrl</text>
+<polygon fill="none" stroke="black" points="182,-557 182,-578 213,-578 213,-557 182,-557"/>
+<text text-anchor="start" x="185" y="-563.8" font-family="Times,serif" font-size="14.00">arg</text>
+<polygon fill="none" stroke="black" points="213,-557 213,-578 238,-578 238,-557 213,-557"/>
+<text text-anchor="start" x="216" y="-563.8" font-family="Times,serif" font-size="14.00">$2</text>
+</g>
+<!-- Stop3 -->
+<g id="node2" class="node">
+<title>Stop3</title>
+<polygon fill="yellow" stroke="black" points="176,-52 122,-52 122,-16 176,-16 176,-52"/>
+<text text-anchor="middle" x="149" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text>
+</g>
+<!-- Return25 -->
+<g id="node15" class="node">
+<title>Return25</title>
+<polygon fill="yellow" stroke="black" points="182,-124 116,-124 116,-88 182,-88 182,-124"/>
+<text text-anchor="middle" x="149" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text>
+</g>
+<!-- Stop3&#45;&gt;Return25 -->
+<g id="edge1" class="edge">
+<title>Stop3&#45;&gt;Return25</title>
+<path fill="none" stroke="red" d="M149,-52.3C149,-60.02 149,-69.29 149,-77.89"/>
+<polygon fill="red" stroke="red" points="145.5,-77.9 149,-87.9 152.5,-77.9 145.5,-77.9"/>
+<text text-anchor="middle" x="146" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Con_4 -->
+<g id="node3" class="node">
+<title>Con_4</title>
+<ellipse fill="none" stroke="black" cx="121" cy="-422" rx="27" ry="18"/>
+<text text-anchor="middle" x="121" y="-418.3" font-family="Times,serif" font-size="14.00">#0</text>
+</g>
+<!-- new9 -->
+<g id="node4" class="node">
+<title>new9</title>
+<ellipse fill="none" stroke="black" cx="191" cy="-494" rx="38.99" ry="18"/>
+<text text-anchor="middle" x="191" y="-490.3" font-family="Times,serif" font-size="14.00">new S</text>
+</g>
+<!-- new9&#45;&gt;Start2 -->
+<g id="edge2" class="edge">
+<title>new9&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="green" d="M178.53,-511.11C172.27,-520.49 165.49,-533 162.99,-546"/>
+<polygon fill="green" stroke="green" points="159.51,-545.7 162,-556 166.47,-546.4 159.51,-545.7"/>
+<text text-anchor="middle" x="175.53" y="-513.71" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Con_11 -->
+<g id="node5" class="node">
+<title>Con_11</title>
+<ellipse fill="none" stroke="black" cx="275" cy="-494" rx="27" ry="18"/>
+<text text-anchor="middle" x="275" y="-490.3" font-family="Times,serif" font-size="14.00">#2</text>
+</g>
+<!-- Store12 -->
+<g id="node6" class="node">
+<title>Store12</title>
+<ellipse fill="none" stroke="black" cx="217" cy="-422" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="217" y="-418.3" font-family="Times,serif" font-size="14.00">.f =</text>
+</g>
+<!-- Store12&#45;&gt;Start2 -->
+<g id="edge3" class="edge">
+<title>Store12&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M239.72,-432.8C270.79,-446.95 322.54,-473.53 321,-493"/>
+<path fill="none" stroke="red" d="M321,-495C315.6,-563.11 190.37,-496.28 166.07,-538.32"/>
+<polygon fill="red" stroke="red" points="162.72,-537.27 162.68,-547.87 169.32,-539.61 162.72,-537.27"/>
+<text text-anchor="middle" x="242.72" y="-435.4" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Store12&#45;&gt;new9 -->
+<g id="edge5" class="edge">
+<title>Store12&#45;&gt;new9</title>
+<path fill="none" stroke="black" d="M210.84,-439.59C207.84,-447.66 204.16,-457.57 200.79,-466.65"/>
+<polygon fill="black" stroke="black" points="197.5,-465.45 197.3,-476.04 204.06,-467.89 197.5,-465.45"/>
+<text text-anchor="middle" x="207.84" y="-442.19" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Store12&#45;&gt;Con_11 -->
+<g id="edge6" class="edge">
+<title>Store12&#45;&gt;Con_11</title>
+<path fill="none" stroke="black" d="M229.59,-438.19C237.26,-447.45 247.23,-459.48 255.86,-469.91"/>
+<polygon fill="black" stroke="black" points="253.36,-472.37 262.44,-477.84 258.75,-467.91 253.36,-472.37"/>
+<text text-anchor="middle" x="226.59" y="-440.79" font-family="Helvetica,sans-Serif" font-size="8.00">3</text>
+</g>
+<!-- new13 -->
+<g id="node7" class="node">
+<title>new13</title>
+<ellipse fill="none" stroke="black" cx="75" cy="-494" rx="38.99" ry="18"/>
+<text text-anchor="middle" x="75" y="-490.3" font-family="Times,serif" font-size="14.00">new S</text>
+</g>
+<!-- new13&#45;&gt;Start2 -->
+<g id="edge7" class="edge">
+<title>new13&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="green" d="M81.73,-512.06C90.25,-530.86 106.79,-559.28 130.97,-565.69"/>
+<polygon fill="green" stroke="green" points="130.63,-569.17 141,-567 131.54,-562.23 130.63,-569.17"/>
+<text text-anchor="middle" x="78.73" y="-514.66" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Store14 -->
+<g id="node8" class="node">
+<title>Store14</title>
+<ellipse fill="none" stroke="black" cx="74" cy="-336" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="74" y="-332.3" font-family="Times,serif" font-size="14.00">.f =</text>
+</g>
+<!-- Store14&#45;&gt;Start2 -->
+<g id="edge8" class="edge">
+<title>Store14&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M75,-423C81.23,-454.16 104.2,-450.38 123,-476 125.09,-478.85 144.12,-515.97 154.8,-538.72"/>
+<polygon fill="red" stroke="red" points="151.69,-540.34 159.03,-547.99 158.06,-537.44 151.69,-540.34"/>
+<text text-anchor="middle" x="72" y="-416.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Store14&#45;&gt;Con_4 -->
+<g id="edge11" class="edge">
+<title>Store14&#45;&gt;Con_4</title>
+<path fill="none" stroke="black" d="M83.06,-353.2C89.82,-365.28 99.19,-382.02 106.92,-395.84"/>
+<polygon fill="black" stroke="black" points="104.03,-397.84 111.97,-404.85 110.14,-394.42 104.03,-397.84"/>
+<text text-anchor="middle" x="80.06" y="-355.8" font-family="Helvetica,sans-Serif" font-size="8.00">3</text>
+</g>
+<!-- Store14&#45;&gt;Store12 -->
+<g id="edge9" class="edge">
+<title>Store14&#45;&gt;Store12</title>
+<path fill="none" stroke="blue" d="M91.16,-350.58C98.61,-356.24 107.55,-362.71 116,-368 138.6,-382.16 165.37,-396.08 185.67,-406.11"/>
+<polygon fill="blue" stroke="blue" points="184.27,-409.32 194.79,-410.56 187.34,-403.03 184.27,-409.32"/>
+<text text-anchor="middle" x="88.16" y="-353.18" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Store14&#45;&gt;new13 -->
+<g id="edge10" class="edge">
+<title>Store14&#45;&gt;new13</title>
+<path fill="none" stroke="black" d="M72.36,-354.25C71.17,-371.36 70.46,-398.26 75,-421"/>
+<path fill="none" stroke="black" d="M75,-423C77.77,-436.87 78.02,-452.6 77.47,-465.63"/>
+<polygon fill="black" stroke="black" points="73.97,-465.65 76.86,-475.84 80.95,-466.07 73.97,-465.65"/>
+<text text-anchor="middle" x="69.36" y="-356.85" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Load16 -->
+<g id="node9" class="node">
+<title>Load16</title>
+<ellipse fill="none" stroke="black" cx="74" cy="-250" rx="27" ry="18"/>
+<text text-anchor="middle" x="74" y="-246.3" font-family="Times,serif" font-size="14.00">.f</text>
+</g>
+<!-- Load16&#45;&gt;Start2 -->
+<g id="edge12" class="edge">
+<title>Load16&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M60.29,-266C52.02,-276 42.12,-289.86 37,-304 19.23,-353.07 6.22,-373.12 27,-421"/>
+<path fill="none" stroke="red" d="M27,-423C42.75,-459.29 5.97,-478.5 27,-512 52.69,-552.92 76.85,-564.12 118.8,-566.47"/>
+<polygon fill="red" stroke="red" points="118.8,-569.97 128.93,-566.86 119.08,-562.98 118.8,-569.97"/>
+<text text-anchor="middle" x="57.29" y="-268.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Load16&#45;&gt;new9 -->
+<g id="edge14" class="edge">
+<title>Load16&#45;&gt;new9</title>
+<path fill="none" stroke="black" d="M27,-423C37.2,-446.5 102.74,-468.87 147.82,-481.75"/>
+<polygon fill="black" stroke="black" points="147.08,-485.18 157.66,-484.5 148.97,-478.44 147.08,-485.18"/>
+<text text-anchor="middle" x="24" y="-416.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Load16&#45;&gt;Store14 -->
+<g id="edge13" class="edge">
+<title>Load16&#45;&gt;Store14</title>
+<path fill="none" stroke="blue" d="M74,-268.4C74,-279.74 74,-294.77 74,-307.68"/>
+<polygon fill="blue" stroke="blue" points="70.5,-307.9 74,-317.9 77.5,-307.9 70.5,-307.9"/>
+<text text-anchor="middle" x="71" y="-271" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- If17 -->
+<g id="node10" class="node">
+<title>If17</title>
+<polygon fill="yellow" stroke="transparent" points="220,-339 220,-364 314,-364 314,-339 220,-339"/>
+<polygon fill="none" stroke="black" points="220,-339 220,-364 314,-364 314,-339 220,-339"/>
+<text text-anchor="start" x="261.5" y="-347.8" font-family="Times,serif" font-size="14.00">If</text>
+<polygon fill="none" stroke="black" points="220,-308 220,-339 314,-339 314,-308 220,-308"/>
+<polygon fill="yellow" stroke="transparent" points="225,-313 225,-334 265,-334 265,-313 225,-313"/>
+<polygon fill="none" stroke="black" points="225,-313 225,-334 265,-334 265,-313 225,-313"/>
+<text text-anchor="start" x="228" y="-319.8" font-family="Times,serif" font-size="14.00">True</text>
+<polygon fill="yellow" stroke="transparent" points="265,-313 265,-334 309,-334 309,-313 265,-313"/>
+<polygon fill="none" stroke="black" points="265,-313 265,-334 309,-334 309,-313 265,-313"/>
+<text text-anchor="start" x="268" y="-319.8" font-family="Times,serif" font-size="14.00">False</text>
+</g>
+<!-- If17&#45;&gt;Start2 -->
+<g id="edge15" class="edge">
+<title>If17&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M258.27,-368.06C255.35,-385.41 255.35,-406.41 267,-421"/>
+<text text-anchor="middle" x="255.27" y="-370.66" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Con_21 -->
+<g id="node11" class="node">
+<title>Con_21</title>
+<ellipse fill="none" stroke="black" cx="167" cy="-336" rx="27" ry="18"/>
+<text text-anchor="middle" x="167" y="-332.3" font-family="Times,serif" font-size="14.00">#1</text>
+</g>
+<!-- Store22 -->
+<g id="node12" class="node">
+<title>Store22</title>
+<ellipse fill="none" stroke="black" cx="149" cy="-250" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="149" y="-246.3" font-family="Times,serif" font-size="14.00">.f =</text>
+</g>
+<!-- Store22&#45;&gt;Start2 -->
+<g id="edge17" class="edge">
+<title>Store22&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M121,-337C124.72,-350.99 120.62,-357.9 131,-368 171.82,-407.72 207.03,-371.77 254,-404 261.84,-409.38 261.07,-413.57 267,-421"/>
+<path fill="none" stroke="red" d="M267,-423C291.51,-453.71 324.1,-453.83 321,-493"/>
+<text text-anchor="middle" x="118" y="-330.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Store22&#45;&gt;new9 -->
+<g id="edge19" class="edge">
+<title>Store22&#45;&gt;new9</title>
+<path fill="none" stroke="black" d="M138.02,-266.62C127.62,-283.37 114.49,-310.8 121,-335"/>
+<path fill="none" stroke="black" d="M121,-337C124.76,-350.98 124.46,-355.08 131,-368 139.92,-385.61 147.62,-386.63 157,-404 167.83,-424.05 176.84,-448.28 182.87,-466.4"/>
+<polygon fill="black" stroke="black" points="179.57,-467.59 185.98,-476.03 186.23,-465.43 179.57,-467.59"/>
+<text text-anchor="middle" x="135.02" y="-269.22" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Store22&#45;&gt;Store14 -->
+<g id="edge18" class="edge">
+<title>Store22&#45;&gt;Store14</title>
+<path fill="none" stroke="blue" d="M135.59,-266.02C124.07,-278.92 107.3,-297.71 94.16,-312.42"/>
+<polygon fill="blue" stroke="blue" points="91.34,-310.32 87.29,-320.11 96.56,-314.98 91.34,-310.32"/>
+<text text-anchor="middle" x="132.59" y="-268.62" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Store22&#45;&gt;Con_21 -->
+<g id="edge20" class="edge">
+<title>Store22&#45;&gt;Con_21</title>
+<path fill="none" stroke="black" d="M152.64,-268C155.11,-279.5 158.41,-294.93 161.23,-308.08"/>
+<polygon fill="black" stroke="black" points="157.85,-308.98 163.36,-318.03 164.69,-307.52 157.85,-308.98"/>
+<text text-anchor="middle" x="149.64" y="-270.6" font-family="Helvetica,sans-Serif" font-size="8.00">3</text>
+</g>
+<!-- Region23 -->
+<g id="node13" class="node">
+<title>Region23</title>
+<polygon fill="yellow" stroke="black" points="269,-196 203,-196 203,-160 269,-160 269,-196"/>
+<text text-anchor="middle" x="236" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text>
+</g>
+<!-- Region23&#45;&gt;If17 -->
+<g id="edge21" class="edge">
+<title>Region23&#45;&gt;If17:p0</title>
+<path fill="none" stroke="red" d="M237.91,-196.19C240.33,-219.44 244.28,-262.49 244.91,-301.62"/>
+<polygon fill="red" stroke="red" points="241.42,-302.03 245,-312 248.42,-301.97 241.42,-302.03"/>
+<text text-anchor="middle" x="234.91" y="-198.79" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Region23&#45;&gt;If17 -->
+<g id="edge22" class="edge">
+<title>Region23&#45;&gt;If17:p1</title>
+<path fill="none" stroke="red" d="M249.35,-196.26C256.45,-206.22 264.76,-219.26 270,-232 282.41,-262.21 286.24,-273.37 286.89,-301.69"/>
+<polygon fill="red" stroke="red" points="283.4,-302.04 287,-312 290.4,-301.96 283.4,-302.04"/>
+<text text-anchor="middle" x="246.35" y="-198.86" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Phi_224 -->
+<g id="node14" class="node">
+<title>Phi_224</title>
+<ellipse fill="lightyellow" stroke="black" cx="149" cy="-178" rx="33.29" ry="18"/>
+<text text-anchor="middle" x="149" y="-174.3" font-family="Times,serif" font-size="14.00">φ_$2</text>
+</g>
+<!-- Phi_224&#45;&gt;Store14 -->
+<g id="edge25" class="edge">
+<title>Phi_224&#45;&gt;Store14</title>
+<path fill="none" stroke="blue" d="M163.74,-194.16C179.64,-212.44 200.82,-243.72 186,-268 167.78,-297.86 145.73,-285.55 116,-304 110.44,-307.45 104.68,-311.42 99.27,-315.34"/>
+<polygon fill="blue" stroke="blue" points="97.08,-312.61 91.14,-321.38 101.25,-318.23 97.08,-312.61"/>
+<text text-anchor="middle" x="160.74" y="-196.76" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Phi_224&#45;&gt;Store22 -->
+<g id="edge24" class="edge">
+<title>Phi_224&#45;&gt;Store22</title>
+<path fill="none" stroke="blue" d="M149,-196.3C149,-204.02 149,-213.29 149,-221.89"/>
+<polygon fill="blue" stroke="blue" points="145.5,-221.9 149,-231.9 152.5,-221.9 145.5,-221.9"/>
+<text text-anchor="middle" x="146" y="-198.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Phi_224&#45;&gt;Region23 -->
+<g id="edge23" class="edge">
+<title>Phi_224&#45;&gt;Region23</title>
+<path fill="none" stroke="black" stroke-dasharray="1,5" d="M182.3,-178C185.73,-178 189.16,-178 192.58,-178"/>
+<polygon fill="black" stroke="black" points="192.86,-181.5 202.86,-178 192.86,-174.5 192.86,-181.5"/>
+<text text-anchor="middle" x="185.3" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return25&#45;&gt;Load16 -->
+<g id="edge27" class="edge">
+<title>Return25&#45;&gt;Load16</title>
+<path fill="none" stroke="black" d="M133.12,-124.15C124.54,-134.07 114.25,-147.11 107,-160 95.8,-179.9 87.06,-204.34 81.39,-222.56"/>
+<polygon fill="black" stroke="black" points="78.01,-221.66 78.49,-232.24 84.71,-223.67 78.01,-221.66"/>
+<text text-anchor="middle" x="130.12" y="-126.75" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Return25&#45;&gt;Region23 -->
+<g id="edge26" class="edge">
+<title>Return25&#45;&gt;Region23</title>
+<path fill="none" stroke="red" d="M170.51,-124.3C181.46,-133.12 194.95,-143.97 206.82,-153.53"/>
+<polygon fill="red" stroke="red" points="204.76,-156.35 214.74,-159.9 209.14,-150.9 204.76,-156.35"/>
+<text text-anchor="middle" x="167.51" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return25&#45;&gt;Phi_224 -->
+<g id="edge28" class="edge">
+<title>Return25&#45;&gt;Phi_224</title>
+<path fill="none" stroke="blue" d="M149,-124.3C149,-132.02 149,-141.29 149,-149.89"/>
+<polygon fill="blue" stroke="blue" points="145.5,-149.9 149,-159.9 152.5,-149.9 145.5,-149.9"/>
+<text text-anchor="middle" x="146" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+</g>
+</svg>