Chapter 9: Global Value Numbering and Iterative Peepholeslinear-chapter09

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>

1 files changed, 222 insertions, 0 deletions

diff --git a/docs/chapter09/09-graph1.svg b/docs/chapter09/09-graph1.svg
new file mode 100644
index 00000000..fce8d53c
--- /dev/null
+++ b/docs/chapter09/09-graph1.svg
@@ -0,0 +1,222 @@
+<?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: chapter08 Pages: 1 -->
+<svg width="350pt" height="420pt"
+ viewBox="0.00 0.00 350.00 420.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 416)">
+<title>chapter08</title>
+<polygon fill="white" stroke="transparent" points="-4,4 -4,-416 346,-416 346,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="black" points="8,-8 8,-404 334,-404 334,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="yellow" stroke="transparent" points="56,-367 56,-392 137,-392 137,-367 56,-367"/>
+<polygon fill="none" stroke="black" points="56,-367 56,-392 137,-392 137,-367 56,-367"/>
+<text text-anchor="start" x="78" y="-375.8" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="none" stroke="black" points="56,-336 56,-367 137,-367 137,-336 56,-336"/>
+<polygon fill="yellow" stroke="transparent" points="61,-341 61,-362 101,-362 101,-341 61,-341"/>
+<polygon fill="none" stroke="black" points="61,-341 61,-362 101,-362 101,-341 61,-341"/>
+<text text-anchor="start" x="64" y="-347.8" font-family="Times,serif" font-size="14.00">$ctrl</text>
+<polygon fill="none" stroke="black" points="101,-341 101,-362 132,-362 132,-341 101,-341"/>
+<text text-anchor="start" x="104" y="-347.8" font-family="Times,serif" font-size="14.00">arg</text>
+</g>
+<!-- Stop3 -->
+<g id="node2" class="node">
+<title>Stop3</title>
+<polygon fill="yellow" stroke="black" points="175,-52 121,-52 121,-16 175,-16 175,-52"/>
+<text text-anchor="middle" x="148" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text>
+</g>
+<!-- Return18 -->
+<g id="node10" class="node">
+<title>Return18</title>
+<polygon fill="yellow" stroke="black" points="139,-124 73,-124 73,-88 139,-88 139,-124"/>
+<text text-anchor="middle" x="106" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text>
+</g>
+<!-- Stop3&#45;&gt;Return18 -->
+<g id="edge1" class="edge">
+<title>Stop3&#45;&gt;Return18</title>
+<path fill="none" stroke="red" d="M137.62,-52.3C132.74,-60.44 126.81,-70.31 121.42,-79.3"/>
+<polygon fill="red" stroke="red" points="118.41,-77.52 116.26,-87.9 124.41,-81.12 118.41,-77.52"/>
+<text text-anchor="middle" x="134.62" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return24 -->
+<g id="node13" class="node">
+<title>Return24</title>
+<polygon fill="yellow" stroke="black" points="223,-124 157,-124 157,-88 223,-88 223,-124"/>
+<text text-anchor="middle" x="190" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text>
+</g>
+<!-- Stop3&#45;&gt;Return24 -->
+<g id="edge2" class="edge">
+<title>Stop3&#45;&gt;Return24</title>
+<path fill="none" stroke="red" d="M158.38,-52.3C163.26,-60.44 169.19,-70.31 174.58,-79.3"/>
+<polygon fill="red" stroke="red" points="171.59,-81.12 179.74,-87.9 177.59,-77.52 171.59,-81.12"/>
+<text text-anchor="middle" x="155.38" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Con_7 -->
+<g id="node3" class="node">
+<title>Con_7</title>
+<ellipse fill="none" stroke="black" cx="262" cy="-364" rx="27" ry="18"/>
+<text text-anchor="middle" x="262" y="-360.3" font-family="Times,serif" font-size="14.00">2</text>
+</g>
+<!-- Mul8 -->
+<g id="node4" class="node">
+<title>Mul8</title>
+<ellipse fill="none" stroke="black" cx="227" cy="-278" rx="27" ry="18"/>
+<text text-anchor="middle" x="227" y="-274.3" font-family="Times,serif" font-size="14.00">*</text>
+</g>
+<!-- Mul8&#45;&gt;Start2 -->
+<g id="edge3" class="edge">
+<title>Mul8&#45;&gt;Start2:p1</title>
+<path fill="none" stroke="black" d="M208.6,-291.54C193.58,-301.96 172,-317.39 154,-332 147.74,-337.08 146.05,-343.45 142.33,-347.37"/>
+<polygon fill="black" stroke="black" points="141.05,-344.11 133,-351 143.59,-350.64 141.05,-344.11"/>
+<text text-anchor="middle" x="205.6" y="-294.14" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Mul8&#45;&gt;Con_7 -->
+<g id="edge4" class="edge">
+<title>Mul8&#45;&gt;Con_7</title>
+<path fill="none" stroke="black" d="M233.91,-295.6C238.85,-307.45 245.59,-323.62 251.23,-337.15"/>
+<polygon fill="black" stroke="black" points="248.02,-338.55 255.1,-346.44 254.48,-335.86 248.02,-338.55"/>
+<text text-anchor="middle" x="230.91" y="-298.2" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Con_9 -->
+<g id="node5" class="node">
+<title>Con_9</title>
+<ellipse fill="none" stroke="black" cx="190" cy="-364" rx="27" ry="18"/>
+<text text-anchor="middle" x="190" y="-360.3" font-family="Times,serif" font-size="14.00">10</text>
+</g>
+<!-- LT10 -->
+<g id="node6" class="node">
+<title>LT10</title>
+<ellipse fill="none" stroke="black" cx="155" cy="-278" rx="27" ry="18"/>
+<text text-anchor="middle" x="155" y="-274.3" font-family="Times,serif" font-size="14.00">&lt;</text>
+</g>
+<!-- LT10&#45;&gt;Start2 -->
+<g id="edge5" class="edge">
+<title>LT10&#45;&gt;Start2:p1</title>
+<path fill="none" stroke="black" d="M139.98,-293.02C131.35,-302.35 121.57,-315.51 118.21,-329.88"/>
+<polygon fill="black" stroke="black" points="114.71,-329.65 117,-340 121.66,-330.49 114.71,-329.65"/>
+<text text-anchor="middle" x="136.98" y="-295.62" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- LT10&#45;&gt;Con_9 -->
+<g id="edge6" class="edge">
+<title>LT10&#45;&gt;Con_9</title>
+<path fill="none" stroke="black" d="M161.91,-295.6C166.85,-307.45 173.59,-323.62 179.23,-337.15"/>
+<polygon fill="black" stroke="black" points="176.02,-338.55 183.1,-346.44 182.48,-335.86 176.02,-338.55"/>
+<text text-anchor="middle" x="158.91" y="-298.2" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- If11 -->
+<g id="node7" class="node">
+<title>If11</title>
+<polygon fill="yellow" stroke="transparent" points="102,-195 102,-220 196,-220 196,-195 102,-195"/>
+<polygon fill="none" stroke="black" points="102,-195 102,-220 196,-220 196,-195 102,-195"/>
+<text text-anchor="start" x="143.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text>
+<polygon fill="none" stroke="black" points="102,-164 102,-195 196,-195 196,-164 102,-164"/>
+<polygon fill="yellow" stroke="transparent" points="107,-169 107,-190 147,-190 147,-169 107,-169"/>
+<polygon fill="none" stroke="black" points="107,-169 107,-190 147,-190 147,-169 107,-169"/>
+<text text-anchor="start" x="110" y="-175.8" font-family="Times,serif" font-size="14.00">True</text>
+<polygon fill="yellow" stroke="transparent" points="147,-169 147,-190 191,-190 191,-169 147,-169"/>
+<polygon fill="none" stroke="black" points="147,-169 147,-190 191,-190 191,-169 147,-169"/>
+<text text-anchor="start" x="150" y="-175.8" font-family="Times,serif" font-size="14.00">False</text>
+</g>
+<!-- If11&#45;&gt;Start2 -->
+<g id="edge7" class="edge">
+<title>If11&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M133.74,-224.23C117.53,-257.6 93.05,-308.62 84.28,-330.23"/>
+<polygon fill="red" stroke="red" points="80.86,-329.41 81,-340 87.5,-331.63 80.86,-329.41"/>
+<text text-anchor="middle" x="130.74" y="-226.83" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- If11&#45;&gt;LT10 -->
+<g id="edge8" class="edge">
+<title>If11&#45;&gt;LT10</title>
+<path fill="none" stroke="black" d="M151.23,-224.28C151.83,-232.58 152.46,-241.48 153.04,-249.56"/>
+<polygon fill="black" stroke="black" points="149.55,-249.87 153.76,-259.6 156.54,-249.37 149.55,-249.87"/>
+<text text-anchor="middle" x="148.23" y="-226.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Con_16 -->
+<g id="node8" class="node">
+<title>Con_16</title>
+<ellipse fill="none" stroke="black" cx="43" cy="-278" rx="27" ry="18"/>
+<text text-anchor="middle" x="43" y="-274.3" font-family="Times,serif" font-size="14.00">2</text>
+</g>
+<!-- Mul17 -->
+<g id="node9" class="node">
+<title>Mul17</title>
+<ellipse fill="none" stroke="black" cx="49" cy="-192" rx="27" ry="18"/>
+<text text-anchor="middle" x="49" y="-188.3" font-family="Times,serif" font-size="14.00">*</text>
+</g>
+<!-- Mul17&#45;&gt;Start2 -->
+<g id="edge9" class="edge">
+<title>Mul17&#45;&gt;Start2:p1</title>
+<path fill="none" stroke="black" d="M58.46,-208.9C75.17,-237.54 108.83,-297.79 115.74,-329.91"/>
+<polygon fill="black" stroke="black" points="112.29,-330.51 117,-340 119.24,-329.64 112.29,-330.51"/>
+<text text-anchor="middle" x="55.46" y="-211.5" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Mul17&#45;&gt;Con_16 -->
+<g id="edge10" class="edge">
+<title>Mul17&#45;&gt;Con_16</title>
+<path fill="none" stroke="black" d="M47.79,-210C46.98,-221.31 45.9,-236.42 44.97,-249.43"/>
+<polygon fill="black" stroke="black" points="41.45,-249.51 44.23,-259.74 48.44,-250.01 41.45,-249.51"/>
+<text text-anchor="middle" x="44.79" y="-212.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Return18&#45;&gt;If11 -->
+<g id="edge11" class="edge">
+<title>Return18&#45;&gt;If11:p0</title>
+<path fill="none" stroke="red" d="M115.27,-124.08C119.67,-133.41 124.35,-145.54 126.19,-157.76"/>
+<polygon fill="red" stroke="red" points="122.72,-158.31 127,-168 129.7,-157.76 122.72,-158.31"/>
+<text text-anchor="middle" x="112.27" y="-126.68" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return18&#45;&gt;Mul17 -->
+<g id="edge12" class="edge">
+<title>Return18&#45;&gt;Mul17</title>
+<path fill="none" stroke="black" d="M94.19,-124.4C85.84,-136.7 74.55,-153.35 65.34,-166.92"/>
+<polygon fill="black" stroke="black" points="62.36,-165.08 59.64,-175.32 68.15,-169.01 62.36,-165.08"/>
+<text text-anchor="middle" x="91.19" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Con_20 -->
+<g id="node11" class="node">
+<title>Con_20</title>
+<ellipse fill="none" stroke="black" cx="299" cy="-278" rx="27" ry="18"/>
+<text text-anchor="middle" x="299" y="-274.3" font-family="Times,serif" font-size="14.00">1</text>
+</g>
+<!-- Add21 -->
+<g id="node12" class="node">
+<title>Add21</title>
+<ellipse fill="none" stroke="black" cx="249" cy="-192" rx="27" ry="18"/>
+<text text-anchor="middle" x="249" y="-188.3" font-family="Times,serif" font-size="14.00">+</text>
+</g>
+<!-- Add21&#45;&gt;Mul8 -->
+<g id="edge13" class="edge">
+<title>Add21&#45;&gt;Mul8</title>
+<path fill="none" stroke="black" d="M244.55,-210C241.54,-221.5 237.49,-236.93 234.05,-250.08"/>
+<polygon fill="black" stroke="black" points="230.59,-249.47 231.45,-260.03 237.36,-251.24 230.59,-249.47"/>
+<text text-anchor="middle" x="241.55" y="-212.6" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Add21&#45;&gt;Con_20 -->
+<g id="edge14" class="edge">
+<title>Add21&#45;&gt;Con_20</title>
+<path fill="none" stroke="black" d="M258.64,-209.2C265.9,-221.4 275.99,-238.34 284.26,-252.24"/>
+<polygon fill="black" stroke="black" points="281.27,-254.05 289.39,-260.85 287.28,-250.47 281.27,-254.05"/>
+<text text-anchor="middle" x="255.64" y="-211.8" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Return24&#45;&gt;If11 -->
+<g id="edge15" class="edge">
+<title>Return24&#45;&gt;If11:p1</title>
+<path fill="none" stroke="red" d="M180.73,-124.08C176.33,-133.41 171.65,-145.54 169.81,-157.76"/>
+<polygon fill="red" stroke="red" points="166.3,-157.76 169,-168 173.28,-158.31 166.3,-157.76"/>
+<text text-anchor="middle" x="177.73" y="-126.68" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Return24&#45;&gt;Add21 -->
+<g id="edge16" class="edge">
+<title>Return24&#45;&gt;Add21</title>
+<path fill="none" stroke="black" d="M202.22,-124.4C210.86,-136.7 222.55,-153.35 232.09,-166.92"/>
+<polygon fill="black" stroke="black" points="229.37,-169.15 237.98,-175.32 235.1,-165.12 229.37,-169.15"/>
+<text text-anchor="middle" x="199.22" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+</g>
+</svg>