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: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

1 files changed, 285 insertions, 0 deletions

diff --git a/docs/chapter11/graph1.svg b/docs/chapter11/graph1.svg
new file mode 100644
index 00000000..592db961
--- /dev/null
+++ b/docs/chapter11/graph1.svg
@@ -0,0 +1,285 @@
+<?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="336pt" height="636pt"
+ viewBox="0.00 0.00 336.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 332,-632 332,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="black" points="8,-8 8,-620 320,-620 320,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="yellow" stroke="transparent" points="198,-583 198,-608 304,-608 304,-583 198,-583"/>
+<polygon fill="none" stroke="black" points="198,-583 198,-608 304,-608 304,-583 198,-583"/>
+<text text-anchor="start" x="232.5" y="-591.8" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="none" stroke="black" points="198,-552 198,-583 304,-583 304,-552 198,-552"/>
+<polygon fill="yellow" stroke="transparent" points="203,-557 203,-578 243,-578 243,-557 203,-557"/>
+<polygon fill="none" stroke="black" points="203,-557 203,-578 243,-578 243,-557 203,-557"/>
+<text text-anchor="start" x="206" y="-563.8" font-family="Times,serif" font-size="14.00">$ctrl</text>
+<polygon fill="none" stroke="black" points="243,-557 243,-578 274,-578 274,-557 243,-557"/>
+<text text-anchor="start" x="246" y="-563.8" font-family="Times,serif" font-size="14.00">arg</text>
+<polygon fill="none" stroke="black" points="274,-557 274,-578 299,-578 299,-557 274,-557"/>
+<text text-anchor="start" x="277" 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="210,-52 156,-52 156,-16 210,-16 210,-52"/>
+<text text-anchor="middle" x="183" 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="216,-124 150,-124 150,-88 216,-88 216,-124"/>
+<text text-anchor="middle" x="183" 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="M183,-52.3C183,-60.02 183,-69.29 183,-77.89"/>
+<polygon fill="red" stroke="red" points="179.5,-77.9 183,-87.9 186.5,-77.9 179.5,-77.9"/>
+<text text-anchor="middle" x="180" 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="137" cy="-422" rx="27" ry="18"/>
+<text text-anchor="middle" x="137" 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="151" cy="-494" rx="38.99" ry="18"/>
+<text text-anchor="middle" x="151" 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="M155.04,-512.06C160.38,-530.53 171.62,-558.28 191.99,-565.33"/>
+<polygon fill="green" stroke="green" points="191.56,-568.8 202,-567 192.71,-561.9 191.56,-568.8"/>
+<text text-anchor="middle" x="152.04" y="-514.66" 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="255" cy="-494" rx="27" ry="18"/>
+<text text-anchor="middle" x="255" 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="230" cy="-422" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="230" 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:p2</title>
+<path fill="none" stroke="blue" d="M222.43,-439.51C215.04,-458.25 206.57,-489.16 219,-512 234.25,-540.04 275.92,-524.64 285.17,-545.89"/>
+<polygon fill="blue" stroke="blue" points="281.77,-546.79 287,-556 288.66,-545.54 281.77,-546.79"/>
+<text text-anchor="middle" x="219.43" y="-442.11" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Store12&#45;&gt;new9 -->
+<g id="edge4" class="edge">
+<title>Store12&#45;&gt;new9</title>
+<path fill="none" stroke="black" d="M214.01,-437.17C203.14,-446.8 188.53,-459.75 176.11,-470.75"/>
+<polygon fill="black" stroke="black" points="173.5,-468.39 168.33,-477.64 178.14,-473.63 173.5,-468.39"/>
+<text text-anchor="middle" x="211.01" y="-439.77" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Store12&#45;&gt;Con_11 -->
+<g id="edge5" class="edge">
+<title>Store12&#45;&gt;Con_11</title>
+<path fill="none" stroke="black" d="M236.05,-439.95C238.91,-447.94 242.38,-457.67 245.57,-466.6"/>
+<polygon fill="black" stroke="black" points="242.34,-467.97 249,-476.21 248.94,-465.62 242.34,-467.97"/>
+<text text-anchor="middle" x="233.05" y="-442.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="55" cy="-494" rx="38.99" ry="18"/>
+<text text-anchor="middle" x="55" y="-490.3" font-family="Times,serif" font-size="14.00">new S</text>
+</g>
+<!-- new13&#45;&gt;Start2 -->
+<g id="edge6" class="edge">
+<title>new13&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="green" d="M72.65,-510.27C97.21,-530 144.07,-562.34 191.81,-566.54"/>
+<polygon fill="green" stroke="green" points="191.85,-570.05 202,-567 192.17,-563.06 191.85,-570.05"/>
+<text text-anchor="middle" x="69.65" y="-512.87" 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="136" cy="-336" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="136" y="-332.3" font-family="Times,serif" font-size="14.00">.f =</text>
+</g>
+<!-- Store14&#45;&gt;Con_4 -->
+<g id="edge9" class="edge">
+<title>Store14&#45;&gt;Con_4</title>
+<path fill="none" stroke="black" d="M136.21,-354.4C136.34,-365.74 136.52,-380.77 136.67,-393.68"/>
+<polygon fill="black" stroke="black" points="133.18,-393.95 136.8,-403.9 140.18,-393.86 133.18,-393.95"/>
+<text text-anchor="middle" x="133.21" y="-357" font-family="Helvetica,sans-Serif" font-size="8.00">3</text>
+</g>
+<!-- Store14&#45;&gt;Store12 -->
+<g id="edge7" class="edge">
+<title>Store14&#45;&gt;Store12</title>
+<path fill="none" stroke="blue" d="M151.95,-351.25C166.89,-364.6 189.42,-384.73 206.44,-399.94"/>
+<polygon fill="blue" stroke="blue" points="204.5,-402.91 214.29,-406.96 209.17,-397.69 204.5,-402.91"/>
+<text text-anchor="middle" x="148.95" y="-353.85" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Store14&#45;&gt;new13 -->
+<g id="edge8" class="edge">
+<title>Store14&#45;&gt;new13</title>
+<path fill="none" stroke="black" d="M127.49,-353.24C120.39,-366.8 110.02,-386.65 101,-404 89.97,-425.23 77.52,-449.33 68.35,-467.1"/>
+<polygon fill="black" stroke="black" points="65.1,-465.77 63.63,-476.26 71.32,-468.97 65.1,-465.77"/>
+<text text-anchor="middle" x="124.49" y="-355.84" 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="183" cy="-250" rx="27" ry="18"/>
+<text text-anchor="middle" x="183" y="-246.3" font-family="Times,serif" font-size="14.00">.f</text>
+</g>
+<!-- Load16&#45;&gt;new9 -->
+<g id="edge11" class="edge">
+<title>Load16&#45;&gt;new9</title>
+<path fill="none" stroke="black" d="M184.02,-268.21C185.58,-301.74 187.07,-378 173,-440 170.94,-449.08 167.45,-458.59 163.85,-467.01"/>
+<polygon fill="black" stroke="black" points="160.59,-465.75 159.66,-476.3 166.96,-468.63 160.59,-465.75"/>
+<text text-anchor="middle" x="181.02" y="-270.81" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Load16&#45;&gt;Store14 -->
+<g id="edge10" class="edge">
+<title>Load16&#45;&gt;Store14</title>
+<path fill="none" stroke="blue" d="M173.94,-267.2C167.18,-279.28 157.81,-296.02 150.08,-309.84"/>
+<polygon fill="blue" stroke="blue" points="146.86,-308.42 145.03,-318.85 152.97,-311.84 146.86,-308.42"/>
+<text text-anchor="middle" x="170.94" y="-269.8" 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="210,-339 210,-364 304,-364 304,-339 210,-339"/>
+<polygon fill="none" stroke="black" points="210,-339 210,-364 304,-364 304,-339 210,-339"/>
+<text text-anchor="start" x="251.5" y="-347.8" font-family="Times,serif" font-size="14.00">If</text>
+<polygon fill="none" stroke="black" points="210,-308 210,-339 304,-339 304,-308 210,-308"/>
+<polygon fill="yellow" stroke="transparent" points="215,-313 215,-334 255,-334 255,-313 215,-313"/>
+<polygon fill="none" stroke="black" points="215,-313 215,-334 255,-334 255,-313 215,-313"/>
+<text text-anchor="start" x="218" y="-319.8" font-family="Times,serif" font-size="14.00">True</text>
+<polygon fill="yellow" stroke="transparent" points="255,-313 255,-334 299,-334 299,-313 255,-313"/>
+<polygon fill="none" stroke="black" points="255,-313 255,-334 299,-334 299,-313 255,-313"/>
+<text text-anchor="start" x="258" y="-319.8" font-family="Times,serif" font-size="14.00">False</text>
+</g>
+<!-- If17&#45;&gt;Start2 -->
+<g id="edge12" class="edge">
+<title>If17&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M274.94,-368.3C293.31,-404.87 315.92,-466.19 291,-512 275.75,-540.04 234.08,-524.64 224.83,-545.89"/>
+<polygon fill="red" stroke="red" points="221.34,-545.54 223,-556 228.23,-546.79 221.34,-545.54"/>
+<text text-anchor="middle" x="271.94" y="-370.9" 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="43" cy="-336" rx="27" ry="18"/>
+<text text-anchor="middle" x="43" 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="99" cy="-250" rx="27.9" ry="18"/>
+<text text-anchor="middle" x="99" y="-246.3" font-family="Times,serif" font-size="14.00">.f =</text>
+</g>
+<!-- Store22&#45;&gt;new9 -->
+<g id="edge15" class="edge">
+<title>Store22&#45;&gt;new9</title>
+<path fill="none" stroke="black" d="M95.12,-268.01C88.19,-302.16 76.55,-380.87 101,-440 105.95,-451.96 114.93,-462.83 123.93,-471.57"/>
+<polygon fill="black" stroke="black" points="121.66,-474.24 131.41,-478.38 126.37,-469.06 121.66,-474.24"/>
+<text text-anchor="middle" x="92.12" y="-270.61" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Store22&#45;&gt;Store14 -->
+<g id="edge14" class="edge">
+<title>Store22&#45;&gt;Store14</title>
+<path fill="none" stroke="blue" d="M106.31,-267.6C111.53,-279.45 118.65,-295.62 124.61,-309.15"/>
+<polygon fill="blue" stroke="blue" points="121.47,-310.7 128.71,-318.44 127.88,-307.88 121.47,-310.7"/>
+<text text-anchor="middle" x="103.31" y="-270.2" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Store22&#45;&gt;Con_21 -->
+<g id="edge16" class="edge">
+<title>Store22&#45;&gt;Con_21</title>
+<path fill="none" stroke="black" d="M88.47,-266.8C80.25,-279.12 68.7,-296.45 59.3,-310.55"/>
+<polygon fill="black" stroke="black" points="56.12,-309.01 53.49,-319.27 61.95,-312.89 56.12,-309.01"/>
+<text text-anchor="middle" x="85.47" y="-269.4" 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="268,-196 202,-196 202,-160 268,-160 268,-196"/>
+<text text-anchor="middle" x="235" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text>
+</g>
+<!-- Region23&#45;&gt;If17 -->
+<g id="edge17" class="edge">
+<title>Region23&#45;&gt;If17:p0</title>
+<path fill="none" stroke="red" d="M235,-196.22C235,-219.49 235,-262.58 235,-301.64"/>
+<polygon fill="red" stroke="red" points="231.5,-302 235,-312 238.5,-302 231.5,-302"/>
+<text text-anchor="middle" x="232" y="-198.82" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Region23&#45;&gt;If17 -->
+<g id="edge18" class="edge">
+<title>Region23&#45;&gt;If17:p1</title>
+<path fill="none" stroke="red" d="M244.11,-196.1C255.5,-218.96 273.84,-261.33 276.64,-301.77"/>
+<polygon fill="red" stroke="red" points="273.15,-302.13 277,-312 280.14,-301.88 273.15,-302.13"/>
+<text text-anchor="middle" x="241.11" y="-198.7" 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="131" cy="-178" rx="33.29" ry="18"/>
+<text text-anchor="middle" x="131" y="-174.3" font-family="Times,serif" font-size="14.00">φ_$2</text>
+</g>
+<!-- Phi_224&#45;&gt;Store14 -->
+<g id="edge21" class="edge">
+<title>Phi_224&#45;&gt;Store14</title>
+<path fill="none" stroke="blue" d="M159.11,-187.55C179.74,-195.47 206.28,-209.49 219,-232 237.92,-265.48 196.57,-299.24 165.7,-318.58"/>
+<polygon fill="blue" stroke="blue" points="163.69,-315.71 156.94,-323.87 167.31,-321.7 163.69,-315.71"/>
+<text text-anchor="middle" x="162.11" y="-190.15" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Phi_224&#45;&gt;Store22 -->
+<g id="edge20" class="edge">
+<title>Phi_224&#45;&gt;Store22</title>
+<path fill="none" stroke="blue" d="M123.42,-195.59C119.63,-203.87 114.97,-214.08 110.73,-223.34"/>
+<polygon fill="blue" stroke="blue" points="107.5,-221.98 106.53,-232.53 113.87,-224.89 107.5,-221.98"/>
+<text text-anchor="middle" x="120.42" y="-198.19" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Phi_224&#45;&gt;Region23 -->
+<g id="edge19" class="edge">
+<title>Phi_224&#45;&gt;Region23</title>
+<path fill="none" stroke="black" stroke-dasharray="1,5" d="M164.31,-178C173.41,-178 182.5,-178 191.6,-178"/>
+<polygon fill="black" stroke="black" points="191.87,-181.5 201.87,-178 191.87,-174.5 191.87,-181.5"/>
+<text text-anchor="middle" x="167.31" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return25&#45;&gt;Load16 -->
+<g id="edge23" class="edge">
+<title>Return25&#45;&gt;Load16</title>
+<path fill="none" stroke="black" d="M183,-124.13C183,-148.33 183,-192.79 183,-221.61"/>
+<polygon fill="black" stroke="black" points="179.5,-221.81 183,-231.81 186.5,-221.81 179.5,-221.81"/>
+<text text-anchor="middle" x="180" y="-126.73" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Return25&#45;&gt;Region23 -->
+<g id="edge22" class="edge">
+<title>Return25&#45;&gt;Region23</title>
+<path fill="none" stroke="red" d="M195.85,-124.3C202.03,-132.61 209.54,-142.72 216.32,-151.86"/>
+<polygon fill="red" stroke="red" points="213.52,-153.96 222.29,-159.9 219.14,-149.78 213.52,-153.96"/>
+<text text-anchor="middle" x="192.85" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return25&#45;&gt;Phi_224 -->
+<g id="edge24" class="edge">
+<title>Return25&#45;&gt;Phi_224</title>
+<path fill="none" stroke="blue" d="M170.15,-124.3C163.79,-132.86 156.01,-143.33 149.07,-152.67"/>
+<polygon fill="blue" stroke="blue" points="146.15,-150.74 142.99,-160.86 151.77,-154.92 146.15,-150.74"/>
+<text text-anchor="middle" x="167.15" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+</g>
+</svg>