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: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

1 files changed, 316 insertions, 0 deletions

diff --git a/docs/chapter11/graph3.svg b/docs/chapter11/graph3.svg
new file mode 100644
index 00000000..e017c4af
--- /dev/null
+++ b/docs/chapter11/graph3.svg
@@ -0,0 +1,316 @@
+<?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="708pt"
+ viewBox="0.00 0.00 346.00 708.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 704)">
+<title>chapter11</title>
+<polygon fill="white" stroke="transparent" points="-4,4 -4,-704 342,-704 342,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="black" points="8,-8 8,-692 330,-692 330,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="yellow" stroke="transparent" points="137,-655 137,-680 243,-680 243,-655 137,-655"/>
+<polygon fill="none" stroke="black" points="137,-655 137,-680 243,-680 243,-655 137,-655"/>
+<text text-anchor="start" x="171.5" y="-663.8" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="none" stroke="black" points="137,-624 137,-655 243,-655 243,-624 137,-624"/>
+<polygon fill="yellow" stroke="transparent" points="142,-629 142,-650 182,-650 182,-629 142,-629"/>
+<polygon fill="none" stroke="black" points="142,-629 142,-650 182,-650 182,-629 142,-629"/>
+<text text-anchor="start" x="145" y="-635.8" font-family="Times,serif" font-size="14.00">$ctrl</text>
+<polygon fill="none" stroke="black" points="182,-629 182,-650 213,-650 213,-629 182,-629"/>
+<text text-anchor="start" x="185" y="-635.8" font-family="Times,serif" font-size="14.00">arg</text>
+<polygon fill="none" stroke="black" points="213,-629 213,-650 238,-650 238,-629 213,-629"/>
+<text text-anchor="start" x="216" y="-635.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="186,-52 132,-52 132,-16 186,-16 186,-52"/>
+<text text-anchor="middle" x="159" 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="192,-124 126,-124 126,-88 192,-88 192,-124"/>
+<text text-anchor="middle" x="159" 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="M159,-52.3C159,-60.02 159,-69.29 159,-77.89"/>
+<polygon fill="red" stroke="red" points="155.5,-77.9 159,-87.9 162.5,-77.9 155.5,-77.9"/>
+<text text-anchor="middle" x="156" 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="87" cy="-494" rx="27" ry="18"/>
+<text text-anchor="middle" x="87" y="-490.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="-566" rx="38.99" ry="18"/>
+<text text-anchor="middle" x="191" y="-562.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,-583.11C172.27,-592.49 165.49,-605 162.99,-618"/>
+<polygon fill="green" stroke="green" points="159.51,-617.7 162,-628 166.47,-618.4 159.51,-617.7"/>
+<text text-anchor="middle" x="175.53" y="-585.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="-566" rx="27" ry="18"/>
+<text text-anchor="middle" x="275" y="-562.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="256" cy="-494" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="256" y="-490.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="M278.09,-505.5C299.78,-517.5 328.59,-538.88 321,-565"/>
+<path fill="none" stroke="red" d="M321,-567C301.92,-632.61 187.71,-567.79 165.68,-610.25"/>
+<polygon fill="red" stroke="red" points="162.32,-609.27 162.62,-619.86 168.99,-611.39 162.32,-609.27"/>
+<text text-anchor="middle" x="281.09" y="-508.1" 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="M242.22,-509.85C233.66,-519.06 222.49,-531.09 212.76,-541.57"/>
+<polygon fill="black" stroke="black" points="209.91,-539.49 205.67,-549.2 215.04,-544.26 209.91,-539.49"/>
+<text text-anchor="middle" x="239.22" y="-512.45" 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="M260.6,-511.95C262.75,-519.86 265.35,-529.46 267.76,-538.31"/>
+<polygon fill="black" stroke="black" points="264.45,-539.48 270.44,-548.21 271.2,-537.64 264.45,-539.48"/>
+<text text-anchor="middle" x="257.6" y="-514.55" 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="-566" rx="38.99" ry="18"/>
+<text text-anchor="middle" x="75" y="-562.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,-584.06C90.25,-602.86 106.79,-631.28 130.97,-637.69"/>
+<polygon fill="green" stroke="green" points="130.63,-641.17 141,-639 131.54,-634.23 130.63,-641.17"/>
+<text text-anchor="middle" x="78.73" y="-586.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="133" cy="-422" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="133" y="-418.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="M133,-495C125.43,-534.08 132.78,-545.53 143,-584 146.42,-596.87 152.99,-602.52 157.44,-610.16"/>
+<polygon fill="red" stroke="red" points="154.26,-611.64 161.18,-619.66 160.77,-609.07 154.26,-611.64"/>
+<text text-anchor="middle" x="130" y="-488.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="M122.56,-438.88C116.8,-447.66 109.52,-458.74 103.04,-468.58"/>
+<polygon fill="black" stroke="black" points="99.96,-466.9 97.4,-477.18 105.81,-470.74 99.96,-466.9"/>
+<text text-anchor="middle" x="119.56" y="-441.48" 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="M153.31,-434.56C173.34,-445.96 204.16,-463.5 226.81,-476.39"/>
+<polygon fill="blue" stroke="blue" points="225.24,-479.52 235.66,-481.42 228.7,-473.44 225.24,-479.52"/>
+<text text-anchor="middle" x="150.31" y="-437.16" 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="M134.81,-440.15C135.88,-454.43 136.45,-475.22 133,-493"/>
+<path fill="none" stroke="black" d="M133,-495C129.28,-514.17 115.61,-531.16 102.48,-543.6"/>
+<polygon fill="black" stroke="black" points="100.01,-541.11 94.89,-550.38 104.68,-546.33 100.01,-541.11"/>
+<text text-anchor="middle" x="131.81" y="-442.75" 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="53" cy="-336" rx="27" ry="18"/>
+<text text-anchor="middle" x="53" y="-332.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="M47.25,-353.59C38.09,-382.82 22.94,-444.94 41,-493"/>
+<path fill="none" stroke="red" d="M41,-495C50.66,-517.36 30.14,-523.84 27,-548 24.94,-563.87 18.49,-570.45 27,-584 52.69,-624.92 76.85,-636.12 118.8,-638.47"/>
+<polygon fill="red" stroke="red" points="118.8,-641.97 128.93,-638.86 119.08,-634.98 118.8,-641.97"/>
+<text text-anchor="middle" x="44.25" y="-356.19" 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="M41,-495C44.08,-503.21 44.3,-506.35 51,-512 66.3,-524.9 113.87,-541.46 149.33,-552.61"/>
+<polygon fill="black" stroke="black" points="148.39,-555.98 158.98,-555.6 150.47,-549.3 148.39,-555.98"/>
+<text text-anchor="middle" x="38" y="-488.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="M66.93,-351.63C79.36,-364.68 97.74,-383.97 111.95,-398.9"/>
+<polygon fill="blue" stroke="blue" points="109.53,-401.43 118.96,-406.25 114.59,-396.6 109.53,-401.43"/>
+<text text-anchor="middle" x="63.93" y="-354.23" 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="218,-339 218,-364 312,-364 312,-339 218,-339"/>
+<polygon fill="none" stroke="black" points="218,-339 218,-364 312,-364 312,-339 218,-339"/>
+<text text-anchor="start" x="259.5" y="-347.8" font-family="Times,serif" font-size="14.00">If</text>
+<polygon fill="none" stroke="black" points="218,-308 218,-339 312,-339 312,-308 218,-308"/>
+<polygon fill="yellow" stroke="transparent" points="223,-313 223,-334 263,-334 263,-313 223,-313"/>
+<polygon fill="none" stroke="black" points="223,-313 223,-334 263,-334 263,-313 223,-313"/>
+<text text-anchor="start" x="226" y="-319.8" font-family="Times,serif" font-size="14.00">True</text>
+<polygon fill="yellow" stroke="transparent" points="263,-313 263,-334 307,-334 307,-313 263,-313"/>
+<polygon fill="none" stroke="black" points="263,-313 263,-334 307,-334 307,-313 263,-313"/>
+<text text-anchor="start" x="266" 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="M283.07,-368.2C306.27,-412.32 341.25,-495.33 321,-565"/>
+<text text-anchor="middle" x="280.07" y="-370.8" 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="125" cy="-336" rx="27" ry="18"/>
+<text text-anchor="middle" x="125" 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="159" cy="-250" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="159" y="-246.3" font-family="Times,serif" font-size="14.00">.f =</text>
+</g>
+<!-- Store22&#45;&gt;new9 -->
+<g id="edge19" class="edge">
+<title>Store22&#45;&gt;new9</title>
+<path fill="none" stroke="black" d="M191,-337C192.12,-409.45 191.64,-494.88 191.27,-537.67"/>
+<polygon fill="black" stroke="black" points="187.77,-537.81 191.18,-547.84 194.77,-537.87 187.77,-537.81"/>
+<text text-anchor="middle" x="188" y="-330.6" 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="M168.96,-267.05C178.21,-283.46 190.61,-310.03 191,-335"/>
+<path fill="none" stroke="blue" d="M191,-337C191.39,-361.97 173.77,-384.91 157.85,-400.48"/>
+<polygon fill="blue" stroke="blue" points="155.22,-398.15 150.26,-407.51 159.98,-403.28 155.22,-398.15"/>
+<text text-anchor="middle" x="165.96" y="-269.65" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Store22&#45;&gt;Load16 -->
+<g id="edge21" class="edge">
+<title>Store22&#45;&gt;Load16</title>
+<path fill="none" stroke="black" d="M141.22,-263.98C126.92,-274.53 106.43,-289.92 89,-304 84.86,-307.35 80.51,-310.98 76.33,-314.54"/>
+<polygon fill="black" stroke="black" points="73.89,-312.03 68.59,-321.2 78.45,-317.33 73.89,-312.03"/>
+<text text-anchor="middle" x="138.22" y="-266.58" font-family="Helvetica,sans-Serif" font-size="8.00">4</text>
+</g>
+<!-- Store22&#45;&gt;If17 -->
+<g id="edge17" class="edge">
+<title>Store22&#45;&gt;If17:p0</title>
+<path fill="none" stroke="red" d="M170.65,-266.62C182.83,-282.67 201.77,-306.77 213.47,-317.51"/>
+<polygon fill="red" stroke="red" points="211.7,-320.53 222,-323 215.49,-314.64 211.7,-320.53"/>
+<text text-anchor="middle" x="173.65" y="-269.22" font-family="Helvetica,sans-Serif" font-size="8.00">0</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.28,-267.6C147.49,-279.45 140.94,-295.62 135.46,-309.15"/>
+<polygon fill="black" stroke="black" points="132.21,-307.86 131.7,-318.44 138.7,-310.48 132.21,-307.86"/>
+<text text-anchor="middle" x="149.28" y="-270.2" 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="276,-196 210,-196 210,-160 276,-160 276,-196"/>
+<text text-anchor="middle" x="243" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text>
+</g>
+<!-- Region23&#45;&gt;If17 -->
+<g id="edge22" class="edge">
+<title>Region23&#45;&gt;If17:p0</title>
+<path fill="none" stroke="red" d="M243,-196.22C243,-219.49 243,-262.58 243,-301.64"/>
+<polygon fill="red" stroke="red" points="239.5,-302 243,-312 246.5,-302 239.5,-302"/>
+<text text-anchor="middle" x="240" y="-198.82" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Region23&#45;&gt;If17 -->
+<g id="edge23" class="edge">
+<title>Region23&#45;&gt;If17:p1</title>
+<path fill="none" stroke="red" d="M252.84,-196.18C258.29,-206.33 264.79,-219.58 269,-232 279.46,-262.85 284.04,-273.57 284.86,-301.73"/>
+<polygon fill="red" stroke="red" points="281.37,-302.05 285,-312 288.37,-301.95 281.37,-302.05"/>
+<text text-anchor="middle" x="249.84" y="-198.78" 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="159" cy="-178" rx="33.29" ry="18"/>
+<text text-anchor="middle" x="159" y="-174.3" font-family="Times,serif" font-size="14.00">φ_$2</text>
+</g>
+<!-- Phi_224&#45;&gt;Store14 -->
+<g id="edge26" class="edge">
+<title>Phi_224&#45;&gt;Store14</title>
+<path fill="none" stroke="blue" d="M173.5,-194.31C181.86,-204.22 191.56,-217.87 196,-232 200.8,-247.26 198.68,-252.23 196,-268 192.06,-291.21 170.41,-346.42 161,-368 156.97,-377.25 151.97,-387.09 147.32,-395.75"/>
+<polygon fill="blue" stroke="blue" points="144.21,-394.15 142.48,-404.6 150.35,-397.51 144.21,-394.15"/>
+<text text-anchor="middle" x="170.5" y="-196.91" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Phi_224&#45;&gt;Store22 -->
+<g id="edge25" class="edge">
+<title>Phi_224&#45;&gt;Store22</title>
+<path fill="none" stroke="blue" d="M159,-196.3C159,-204.02 159,-213.29 159,-221.89"/>
+<polygon fill="blue" stroke="blue" points="155.5,-221.9 159,-231.9 162.5,-221.9 155.5,-221.9"/>
+<text text-anchor="middle" x="156" y="-198.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Phi_224&#45;&gt;Region23 -->
+<g id="edge24" class="edge">
+<title>Phi_224&#45;&gt;Region23</title>
+<path fill="none" stroke="black" stroke-dasharray="1,5" d="M192.47,-178C194.91,-178 197.35,-178 199.8,-178"/>
+<polygon fill="black" stroke="black" points="199.84,-181.5 209.84,-178 199.84,-174.5 199.84,-181.5"/>
+<text text-anchor="middle" x="195.47" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return25&#45;&gt;Load16 -->
+<g id="edge28" class="edge">
+<title>Return25&#45;&gt;Load16</title>
+<path fill="none" stroke="black" d="M143.1,-124.14C134.51,-134.05 124.23,-147.09 117,-160 89.5,-209.12 69.82,-272.31 60.03,-307.76"/>
+<polygon fill="black" stroke="black" points="56.54,-307.25 57.31,-317.82 63.3,-309.08 56.54,-307.25"/>
+<text text-anchor="middle" x="140.1" y="-126.74" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Return25&#45;&gt;Region23 -->
+<g id="edge27" class="edge">
+<title>Return25&#45;&gt;Region23</title>
+<path fill="none" stroke="red" d="M179.76,-124.3C190.24,-133.03 203.11,-143.76 214.5,-153.25"/>
+<polygon fill="red" stroke="red" points="212.55,-156.18 222.47,-159.9 217.03,-150.81 212.55,-156.18"/>
+<text text-anchor="middle" x="176.76" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return25&#45;&gt;Phi_224 -->
+<g id="edge29" class="edge">
+<title>Return25&#45;&gt;Phi_224</title>
+<path fill="none" stroke="blue" d="M159,-124.3C159,-132.02 159,-141.29 159,-149.89"/>
+<polygon fill="blue" stroke="blue" points="155.5,-149.9 159,-159.9 162.5,-149.9 155.5,-149.9"/>
+<text text-anchor="middle" x="156" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+</g>
+</svg>