Chapter 9: Global Value Numbering and Iterative Peepholes

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: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.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, 210 insertions, 0 deletions

diff --git a/docs/chapter09/09-graph5.svg b/docs/chapter09/09-graph5.svg
new file mode 100644
index 00000000..9d0698db
--- /dev/null
+++ b/docs/chapter09/09-graph5.svg
@@ -0,0 +1,210 @@
+<?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: chapter09 Pages: 1 -->
+<svg width="338pt" height="492pt"
+ viewBox="0.00 0.00 338.00 492.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 488)">
+<title>chapter09</title>
+<polygon fill="white" stroke="transparent" points="-4,4 -4,-488 334,-488 334,4 -4,4"/>
+<g id="clust1" class="cluster">
+<title>cluster_Nodes</title>
+<polygon fill="none" stroke="black" points="8,-8 8,-476 322,-476 322,-8 8,-8"/>
+</g>
+<!-- Start2 -->
+<g id="node1" class="node">
+<title>Start2</title>
+<polygon fill="yellow" stroke="transparent" points="153,-439 153,-464 234,-464 234,-439 153,-439"/>
+<polygon fill="none" stroke="black" points="153,-439 153,-464 234,-464 234,-439 153,-439"/>
+<text text-anchor="start" x="175" y="-447.8" font-family="Times,serif" font-size="14.00">Start</text>
+<polygon fill="none" stroke="black" points="153,-408 153,-439 234,-439 234,-408 153,-408"/>
+<polygon fill="yellow" stroke="transparent" points="158,-413 158,-434 198,-434 198,-413 158,-413"/>
+<polygon fill="none" stroke="black" points="158,-413 158,-434 198,-434 198,-413 158,-413"/>
+<text text-anchor="start" x="161" y="-419.8" font-family="Times,serif" font-size="14.00">$ctrl</text>
+<polygon fill="none" stroke="black" points="198,-413 198,-434 229,-434 229,-413 198,-413"/>
+<text text-anchor="start" x="201" y="-419.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="271,-52 217,-52 217,-16 271,-16 271,-52"/>
+<text text-anchor="middle" x="244" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text>
+</g>
+<!-- Return21 -->
+<g id="node11" class="node">
+<title>Return21</title>
+<polygon fill="yellow" stroke="black" points="277,-124 211,-124 211,-88 277,-88 277,-124"/>
+<text text-anchor="middle" x="244" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text>
+</g>
+<!-- Stop3&#45;&gt;Return21 -->
+<g id="edge1" class="edge">
+<title>Stop3&#45;&gt;Return21</title>
+<path fill="none" stroke="red" d="M244,-52.3C244,-60.02 244,-69.29 244,-77.89"/>
+<polygon fill="red" stroke="red" points="240.5,-77.9 244,-87.9 247.5,-77.9 240.5,-77.9"/>
+<text text-anchor="middle" x="241" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Con_6 -->
+<g id="node3" class="node">
+<title>Con_6</title>
+<ellipse fill="none" stroke="black" cx="43" cy="-350" rx="27" ry="18"/>
+<text text-anchor="middle" x="43" y="-346.3" font-family="Times,serif" font-size="14.00">#1</text>
+</g>
+<!-- Loop7 -->
+<g id="node4" class="node">
+<title>Loop7</title>
+<polygon fill="yellow" stroke="black" points="142,-368 88,-368 88,-332 142,-332 142,-368"/>
+<text text-anchor="middle" x="115" y="-346.3" font-family="Times,serif" font-size="14.00">Loop</text>
+</g>
+<!-- Loop7&#45;&gt;Start2 -->
+<g id="edge2" class="edge">
+<title>Loop7&#45;&gt;Start2:p0</title>
+<path fill="none" stroke="red" d="M117.35,-368.06C120.75,-386.19 128.75,-413.28 146.69,-420.93"/>
+<polygon fill="red" stroke="red" points="146.51,-424.46 157,-423 147.89,-417.6 146.51,-424.46"/>
+<text text-anchor="middle" x="114.35" y="-370.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- If12 -->
+<g id="node8" class="node">
+<title>If12</title>
+<polygon fill="yellow" stroke="transparent" points="147,-195 147,-220 241,-220 241,-195 147,-195"/>
+<polygon fill="none" stroke="black" points="147,-195 147,-220 241,-220 241,-195 147,-195"/>
+<text text-anchor="start" x="188.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text>
+<polygon fill="none" stroke="black" points="147,-164 147,-195 241,-195 241,-164 147,-164"/>
+<polygon fill="yellow" stroke="transparent" points="152,-169 152,-190 192,-190 192,-169 152,-169"/>
+<polygon fill="none" stroke="black" points="152,-169 152,-190 192,-190 192,-169 152,-169"/>
+<text text-anchor="start" x="155" y="-175.8" font-family="Times,serif" font-size="14.00">True</text>
+<polygon fill="yellow" stroke="transparent" points="192,-169 192,-190 236,-190 236,-169 192,-169"/>
+<polygon fill="none" stroke="black" points="192,-169 192,-190 236,-190 236,-169 192,-169"/>
+<text text-anchor="start" x="195" y="-175.8" font-family="Times,serif" font-size="14.00">False</text>
+</g>
+<!-- Loop7&#45;&gt;If12 -->
+<g id="edge3" class="edge">
+<title>Loop7&#45;&gt;If12:p0</title>
+<path fill="none" stroke="red" d="M142.11,-336.15C145.11,-334.74 148.12,-333.34 151,-332 186,-315.76 209.13,-328.45 230,-296 238.66,-282.54 239,-273.23 230,-260 205.55,-224.03 163.45,-259.97 139,-224 125.26,-203.78 121.98,-186.54 139,-169 146.02,-161.76 158.99,-157.07 166.4,-159.61"/>
+<polygon fill="red" stroke="red" points="163.54,-161.62 172,-168 169.36,-157.74 163.54,-161.62"/>
+<text text-anchor="middle" x="145.11" y="-329.75" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Phi_arg9 -->
+<g id="node5" class="node">
+<title>Phi_arg9</title>
+<ellipse fill="lightyellow" stroke="black" cx="277" cy="-350" rx="37.09" ry="18"/>
+<text text-anchor="middle" x="277" y="-346.3" font-family="Times,serif" font-size="14.00">φ_arg</text>
+</g>
+<!-- Phi_arg9&#45;&gt;Start2 -->
+<g id="edge5" class="edge">
+<title>Phi_arg9&#45;&gt;Start2:p1</title>
+<path fill="none" stroke="black" d="M273.71,-368.06C269.21,-386.44 259.37,-414.03 239.96,-421.23"/>
+<polygon fill="black" stroke="black" points="239.23,-417.81 230,-423 240.46,-424.7 239.23,-417.81"/>
+<text text-anchor="middle" x="270.71" y="-370.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Phi_arg9&#45;&gt;Loop7 -->
+<g id="edge4" class="edge">
+<title>Phi_arg9&#45;&gt;Loop7</title>
+<path fill="none" stroke="black" stroke-dasharray="1,5" d="M258.53,-334.01C248.46,-326.34 235.34,-317.98 222,-314 195.59,-306.13 186,-304.88 160,-314 152.86,-316.5 146.01,-320.67 139.91,-325.3"/>
+<polygon fill="black" stroke="black" points="137.55,-322.71 132.08,-331.78 142.01,-328.1 137.55,-322.71"/>
+<text text-anchor="middle" x="255.53" y="-327.61" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- Add18 -->
+<g id="node10" class="node">
+<title>Add18</title>
+<ellipse fill="none" stroke="black" cx="66" cy="-192" rx="27" ry="18"/>
+<text text-anchor="middle" x="66" y="-188.3" font-family="Times,serif" font-size="14.00">+</text>
+</g>
+<!-- Phi_arg9&#45;&gt;Add18 -->
+<g id="edge6" class="edge">
+<title>Phi_arg9&#45;&gt;Add18</title>
+<path fill="none" stroke="black" d="M249.01,-337.87C243.12,-335.75 236.9,-333.68 231,-332 153.36,-309.94 104.1,-358.47 53,-296 35.4,-274.49 43.72,-241.53 53.12,-218.71"/>
+<polygon fill="black" stroke="black" points="56.43,-219.88 57.28,-209.32 50.03,-217.04 56.43,-219.88"/>
+<text text-anchor="middle" x="246.01" y="-331.47" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- LT10 -->
+<g id="node6" class="node">
+<title>LT10</title>
+<ellipse fill="none" stroke="black" cx="194" cy="-278" rx="27" ry="18"/>
+<text text-anchor="middle" x="194" y="-274.3" font-family="Times,serif" font-size="14.00">&lt;</text>
+</g>
+<!-- LT10&#45;&gt;Phi_arg9 -->
+<g id="edge7" class="edge">
+<title>LT10&#45;&gt;Phi_arg9</title>
+<path fill="none" stroke="black" d="M210.4,-292.83C222.06,-302.66 237.95,-316.07 251.29,-327.31"/>
+<polygon fill="black" stroke="black" points="249.3,-330.22 259.2,-333.99 253.81,-324.86 249.3,-330.22"/>
+<text text-anchor="middle" x="207.4" y="-295.43" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Con_11 -->
+<g id="node7" class="node">
+<title>Con_11</title>
+<ellipse fill="none" stroke="black" cx="191" cy="-350" rx="30.59" ry="18"/>
+<text text-anchor="middle" x="191" y="-346.3" font-family="Times,serif" font-size="14.00">#10</text>
+</g>
+<!-- LT10&#45;&gt;Con_11 -->
+<g id="edge8" class="edge">
+<title>LT10&#45;&gt;Con_11</title>
+<path fill="none" stroke="black" d="M193.26,-296.3C192.93,-304.02 192.53,-313.29 192.16,-321.89"/>
+<polygon fill="black" stroke="black" points="188.66,-321.75 191.73,-331.9 195.66,-322.05 188.66,-321.75"/>
+<text text-anchor="middle" x="190.26" y="-298.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- If12&#45;&gt;Loop7 -->
+<g id="edge9" class="edge">
+<title>If12&#45;&gt;Loop7</title>
+<path fill="none" stroke="red" d="M176.87,-224.21C170.8,-235.44 164,-248.24 158,-260 147.34,-280.9 135.81,-304.85 127.37,-322.64"/>
+<polygon fill="red" stroke="red" points="124.14,-321.29 123.03,-331.83 130.46,-324.29 124.14,-321.29"/>
+<text text-anchor="middle" x="173.87" y="-226.81" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+<!-- If12&#45;&gt;LT10 -->
+<g id="edge10" class="edge">
+<title>If12&#45;&gt;LT10</title>
+<path fill="none" stroke="black" d="M194,-224.28C194,-232.58 194,-241.48 194,-249.56"/>
+<polygon fill="black" stroke="black" points="190.5,-249.6 194,-259.6 197.5,-249.6 190.5,-249.6"/>
+<text text-anchor="middle" x="191" y="-226.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Add16 -->
+<g id="node9" class="node">
+<title>Add16</title>
+<ellipse fill="none" stroke="black" cx="89" cy="-278" rx="27" ry="18"/>
+<text text-anchor="middle" x="89" y="-274.3" font-family="Times,serif" font-size="14.00">+</text>
+</g>
+<!-- Add16&#45;&gt;Con_6 -->
+<g id="edge11" class="edge">
+<title>Add16&#45;&gt;Con_6</title>
+<path fill="none" stroke="black" d="M78.56,-294.88C72.8,-303.66 65.52,-314.74 59.04,-324.58"/>
+<polygon fill="black" stroke="black" points="55.96,-322.9 53.4,-333.18 61.81,-326.74 55.96,-322.9"/>
+<text text-anchor="middle" x="75.56" y="-297.48" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Add16&#45;&gt;Phi_arg9 -->
+<g id="edge12" class="edge">
+<title>Add16&#45;&gt;Phi_arg9</title>
+<path fill="none" stroke="black" d="M112.05,-287.58C143.64,-299.35 200.8,-320.63 238.83,-334.79"/>
+<polygon fill="black" stroke="black" points="237.94,-338.19 248.54,-338.4 240.39,-331.63 237.94,-338.19"/>
+<text text-anchor="middle" x="115.05" y="-290.18" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Add18&#45;&gt;Con_6 -->
+<g id="edge14" class="edge">
+<title>Add18&#45;&gt;Con_6</title>
+<path fill="none" stroke="black" d="M62.31,-210.01C59.48,-223.51 55.62,-242.9 53,-260 49.85,-280.62 47.25,-304.07 45.5,-321.72"/>
+<polygon fill="black" stroke="black" points="41.99,-321.59 44.51,-331.88 48.96,-322.27 41.99,-321.59"/>
+<text text-anchor="middle" x="59.31" y="-212.61" font-family="Helvetica,sans-Serif" font-size="8.00">2</text>
+</g>
+<!-- Add18&#45;&gt;Add16 -->
+<g id="edge13" class="edge">
+<title>Add18&#45;&gt;Add16</title>
+<path fill="none" stroke="black" d="M70.65,-210C73.8,-221.5 78.03,-236.93 81.63,-250.08"/>
+<polygon fill="black" stroke="black" points="78.34,-251.31 84.35,-260.03 85.09,-249.46 78.34,-251.31"/>
+<text text-anchor="middle" x="67.65" y="-212.6" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Return21&#45;&gt;Phi_arg9 -->
+<g id="edge16" class="edge">
+<title>Return21&#45;&gt;Phi_arg9</title>
+<path fill="none" stroke="black" d="M249.23,-124.03C252.22,-134.35 255.79,-147.83 258,-160 268.31,-216.9 273.41,-284.53 275.6,-321.49"/>
+<polygon fill="black" stroke="black" points="272.13,-322.15 276.19,-331.93 279.12,-321.75 272.13,-322.15"/>
+<text text-anchor="middle" x="246.23" y="-126.63" font-family="Helvetica,sans-Serif" font-size="8.00">1</text>
+</g>
+<!-- Return21&#45;&gt;If12 -->
+<g id="edge15" class="edge">
+<title>Return21&#45;&gt;If12:p1</title>
+<path fill="none" stroke="red" d="M230.4,-124.06C224.14,-133.27 217.55,-145.31 215.05,-157.87"/>
+<polygon fill="red" stroke="red" points="211.55,-157.69 214,-168 218.51,-158.41 211.55,-157.69"/>
+<text text-anchor="middle" x="227.4" y="-126.66" font-family="Helvetica,sans-Serif" font-size="8.00">0</text>
+</g>
+</g>
+</svg>