diff options
| author | Cliff Click <cliffc@acm.org> | 2024-03-03 17:55:47 +0000 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-04-24 14:38:36 -0700 |
| commit | 489e86d923d7bc80cec353e08169b5bbeb9e0c00 (patch) | |
| tree | 786b44c77f704c0b4f2c5068c1ba408dbba1e2e6 /docs | |
| parent | f9353c3765efd4c0e862b35c7beada89799e16f7 (diff) | |
| download | Simple-489e86d923d7bc80cec353e08169b5bbeb9e0c00.tar.gz Simple-489e86d923d7bc80cec353e08169b5bbeb9e0c00.zip | |
Chapter 9: Global Value Numbering and Iterative Peepholes
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
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: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: RobertObkircher <robert.obkircher@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>
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/chapter09/09-grammar.md | 98 | ||||
| -rw-r--r-- | docs/chapter09/09-graph1.gv | 67 | ||||
| -rw-r--r-- | docs/chapter09/09-graph1.svg | 222 | ||||
| -rw-r--r-- | docs/chapter09/09-graph2.gv | 63 | ||||
| -rw-r--r-- | docs/chapter09/09-graph2.svg | 196 | ||||
| -rw-r--r-- | docs/chapter09/09-graph3.gv | 37 | ||||
| -rw-r--r-- | docs/chapter09/09-graph3.svg | 109 | ||||
| -rw-r--r-- | docs/chapter09/09-graph4.gv | 29 | ||||
| -rw-r--r-- | docs/chapter09/09-graph4.svg | 67 | ||||
| -rw-r--r-- | docs/chapter09/09-graph5.gv | 63 | ||||
| -rw-r--r-- | docs/chapter09/09-graph5.svg | 210 | ||||
| -rw-r--r-- | docs/chapter09/09-graph6.gv | 60 | ||||
| -rw-r--r-- | docs/chapter09/09-graph6.svg | 184 | ||||
| -rw-r--r-- | docs/chapter09/Makefile | 12 | ||||
| -rw-r--r-- | docs/chapter09/README.md | 300 |
15 files changed, 1717 insertions, 0 deletions
diff --git a/docs/chapter09/09-grammar.md b/docs/chapter09/09-grammar.md new file mode 100644 index 00000000..4c61bfd7 --- /dev/null +++ b/docs/chapter09/09-grammar.md @@ -0,0 +1,98 @@ +# Grammar for Chapter 8 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + | metaStatement + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter09/09-graph1.gv b/docs/chapter09/09-graph1.gv new file mode 100644 index 00000000..e6d1851a --- /dev/null +++ b/docs/chapter09/09-graph1.gv @@ -0,0 +1,67 @@ +digraph chapter08 { +/* +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="2" ]; + Mul8 [ label="*" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_16 [ label="2" ]; + Mul17 [ label="*" ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_20 [ label="1" ]; + Add21 [ label="+" ]; + Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + Stop3 -> Return24[taillabel=1 color=red]; + Mul8 -> Start2:p1[taillabel=1]; + Mul8 -> Con_7[taillabel=2]; + LT10 -> Start2:p1[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Start2:p0[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Mul17 -> Start2:p1[taillabel=1]; + Mul17 -> Con_16[taillabel=2]; + Return18 -> If11:p0[taillabel=0 color=red]; + Return18 -> Mul17[taillabel=1]; + Add21 -> Mul8[taillabel=1]; + Add21 -> Con_20[taillabel=2]; + Return24 -> If11:p1[taillabel=0 color=red]; + Return24 -> Add21[taillabel=1]; +} 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->Return18 --> +<g id="edge1" class="edge"> +<title>Stop3->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->Return24 --> +<g id="edge2" class="edge"> +<title>Stop3->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->Start2 --> +<g id="edge3" class="edge"> +<title>Mul8->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->Con_7 --> +<g id="edge4" class="edge"> +<title>Mul8->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"><</text> +</g> +<!-- LT10->Start2 --> +<g id="edge5" class="edge"> +<title>LT10->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->Con_9 --> +<g id="edge6" class="edge"> +<title>LT10->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->Start2 --> +<g id="edge7" class="edge"> +<title>If11->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->LT10 --> +<g id="edge8" class="edge"> +<title>If11->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->Start2 --> +<g id="edge9" class="edge"> +<title>Mul17->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->Con_16 --> +<g id="edge10" class="edge"> +<title>Mul17->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->If11 --> +<g id="edge11" class="edge"> +<title>Return18->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->Mul17 --> +<g id="edge12" class="edge"> +<title>Return18->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->Mul8 --> +<g id="edge13" class="edge"> +<title>Add21->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->Con_20 --> +<g id="edge14" class="edge"> +<title>Add21->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->If11 --> +<g id="edge15" class="edge"> +<title>Return24->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->Add21 --> +<g id="edge16" class="edge"> +<title>Return24->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> diff --git a/docs/chapter09/09-graph2.gv b/docs/chapter09/09-graph2.gv new file mode 100644 index 00000000..1a1f7a29 --- /dev/null +++ b/docs/chapter09/09-graph2.gv @@ -0,0 +1,63 @@ +digraph chapter09 { +/* +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="#2" ]; + Mul8 [ label="*" ]; + LT9 [ label="<" ]; + Con_10 [ label="#10" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Add20 [ label="+" ]; + Con_21 [ label="#1" ]; + Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + Stop3 -> Return24[taillabel=1 color=red]; + Mul8 -> Start2:p1[taillabel=1]; + Mul8 -> Con_7[taillabel=2]; + LT9 -> Start2:p1[taillabel=1]; + LT9 -> Con_10[taillabel=2]; + If11 -> Start2:p0[taillabel=0 color=red]; + If11 -> LT9[taillabel=1]; + Return18 -> If11:p0[taillabel=0 color=red]; + Return18 -> Mul8[taillabel=1]; + Add20 -> Mul8[taillabel=1]; + Add20 -> Con_21[taillabel=2]; + Return24 -> If11:p1[taillabel=0 color=red]; + Return24 -> Add20[taillabel=1]; +} diff --git a/docs/chapter09/09-graph2.svg b/docs/chapter09/09-graph2.svg new file mode 100644 index 00000000..111ec172 --- /dev/null +++ b/docs/chapter09/09-graph2.svg @@ -0,0 +1,196 @@ +<?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="289pt" height="420pt" + viewBox="0.00 0.00 289.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>chapter09</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-416 285,-416 285,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-404 273,-404 273,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="97,-367 97,-392 178,-392 178,-367 97,-367"/> +<polygon fill="none" stroke="black" points="97,-367 97,-392 178,-392 178,-367 97,-367"/> +<text text-anchor="start" x="119" y="-375.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="97,-336 97,-367 178,-367 178,-336 97,-336"/> +<polygon fill="yellow" stroke="transparent" points="102,-341 102,-362 142,-362 142,-341 102,-341"/> +<polygon fill="none" stroke="black" points="102,-341 102,-362 142,-362 142,-341 102,-341"/> +<text text-anchor="start" x="105" y="-347.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="142,-341 142,-362 173,-362 173,-341 142,-341"/> +<text text-anchor="start" x="145" 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="164,-52 110,-52 110,-16 164,-16 164,-52"/> +<text text-anchor="middle" x="137" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return18 --> +<g id="node8" class="node"> +<title>Return18</title> +<polygon fill="yellow" stroke="black" points="128,-124 62,-124 62,-88 128,-88 128,-124"/> +<text text-anchor="middle" x="95" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return18 --> +<g id="edge1" class="edge"> +<title>Stop3->Return18</title> +<path fill="none" stroke="red" d="M126.62,-52.3C121.74,-60.44 115.81,-70.31 110.42,-79.3"/> +<polygon fill="red" stroke="red" points="107.41,-77.52 105.26,-87.9 113.41,-81.12 107.41,-77.52"/> +<text text-anchor="middle" x="123.62" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return24 --> +<g id="node11" class="node"> +<title>Return24</title> +<polygon fill="yellow" stroke="black" points="212,-124 146,-124 146,-88 212,-88 212,-124"/> +<text text-anchor="middle" x="179" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return24 --> +<g id="edge2" class="edge"> +<title>Stop3->Return24</title> +<path fill="none" stroke="red" d="M147.38,-52.3C152.26,-60.44 158.19,-70.31 163.58,-79.3"/> +<polygon fill="red" stroke="red" points="160.59,-81.12 168.74,-87.9 166.59,-77.52 160.59,-81.12"/> +<text text-anchor="middle" x="144.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="43" cy="-364" rx="27" ry="18"/> +<text text-anchor="middle" x="43" 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="94" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="94" y="-274.3" font-family="Times,serif" font-size="14.00">*</text> +</g> +<!-- Mul8->Start2 --> +<g id="edge3" class="edge"> +<title>Mul8->Start2:p1</title> +<path fill="none" stroke="black" d="M116.03,-288.88C131.86,-297.42 151.32,-311.35 156.62,-330.09"/> +<polygon fill="black" stroke="black" points="153.15,-330.58 158,-340 160.08,-329.61 153.15,-330.58"/> +<text text-anchor="middle" x="119.03" y="-291.48" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Mul8->Con_7 --> +<g id="edge4" class="edge"> +<title>Mul8->Con_7</title> +<path fill="none" stroke="black" d="M84.17,-295.2C76.71,-307.48 66.34,-324.56 57.87,-338.51"/> +<polygon fill="black" stroke="black" points="54.83,-336.77 52.63,-347.14 60.81,-340.41 54.83,-336.77"/> +<text text-anchor="middle" x="81.17" y="-297.8" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- LT9 --> +<g id="node5" class="node"> +<title>LT9</title> +<ellipse fill="none" stroke="black" cx="166" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="166" y="-274.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT9->Start2 --> +<g id="edge5" class="edge"> +<title>LT9->Start2:p1</title> +<path fill="none" stroke="black" d="M162.56,-296.01C160.87,-305.54 159.04,-317.9 158.32,-329.98"/> +<polygon fill="black" stroke="black" points="154.82,-329.89 158,-340 161.81,-330.12 154.82,-329.89"/> +<text text-anchor="middle" x="159.56" y="-298.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_10 --> +<g id="node6" class="node"> +<title>Con_10</title> +<ellipse fill="none" stroke="black" cx="234" cy="-364" rx="30.59" ry="18"/> +<text text-anchor="middle" x="234" y="-360.3" font-family="Times,serif" font-size="14.00">#10</text> +</g> +<!-- LT9->Con_10 --> +<g id="edge6" class="edge"> +<title>LT9->Con_10</title> +<path fill="none" stroke="black" d="M178.47,-294.41C188.66,-307 203.24,-325 214.9,-339.41"/> +<polygon fill="black" stroke="black" points="212.36,-341.84 221.38,-347.41 217.8,-337.43 212.36,-341.84"/> +<text text-anchor="middle" x="175.47" y="-297.01" 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="91,-195 91,-220 185,-220 185,-195 91,-195"/> +<polygon fill="none" stroke="black" points="91,-195 91,-220 185,-220 185,-195 91,-195"/> +<text text-anchor="start" x="132.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="91,-164 91,-195 185,-195 185,-164 91,-164"/> +<polygon fill="yellow" stroke="transparent" points="96,-169 96,-190 136,-190 136,-169 96,-169"/> +<polygon fill="none" stroke="black" points="96,-169 96,-190 136,-190 136,-169 96,-169"/> +<text text-anchor="start" x="99" y="-175.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="136,-169 136,-190 180,-190 180,-169 136,-169"/> +<polygon fill="none" stroke="black" points="136,-169 136,-190 180,-190 180,-169 136,-169"/> +<text text-anchor="start" x="139" y="-175.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Start2 --> +<g id="edge7" class="edge"> +<title>If11->Start2:p0</title> +<path fill="none" stroke="red" d="M87.32,-224.07C75.52,-233.97 64.51,-246.05 58,-260 51.23,-274.5 52.79,-280.87 58,-296 59.97,-301.73 80.37,-332.08 92.9,-345.08"/> +<polygon fill="red" stroke="red" points="90.86,-347.92 101,-351 94.99,-342.27 90.86,-347.92"/> +<text text-anchor="middle" x="84.32" y="-226.67" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT9 --> +<g id="edge8" class="edge"> +<title>If11->LT9</title> +<path fill="none" stroke="black" d="M148.43,-224.28C151.3,-232.9 154.39,-242.17 157.16,-250.49"/> +<polygon fill="black" stroke="black" points="153.87,-251.69 160.36,-260.07 160.51,-249.48 153.87,-251.69"/> +<text text-anchor="middle" x="145.43" y="-226.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return18->Mul8 --> +<g id="edge10" class="edge"> +<title>Return18->Mul8</title> +<path fill="none" stroke="black" d="M86.28,-124.17C81.63,-134.31 76.38,-147.56 74,-160 68.67,-187.94 68.9,-196.02 74,-224 75.67,-233.18 78.85,-242.83 82.19,-251.35"/> +<polygon fill="black" stroke="black" points="79.03,-252.85 86.11,-260.73 85.49,-250.15 79.03,-252.85"/> +<text text-anchor="middle" x="83.28" y="-126.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return18->If11 --> +<g id="edge9" class="edge"> +<title>Return18->If11:p0</title> +<path fill="none" stroke="red" d="M104.27,-124.08C108.67,-133.41 113.35,-145.54 115.19,-157.76"/> +<polygon fill="red" stroke="red" points="111.72,-158.31 116,-168 118.7,-157.76 111.72,-158.31"/> +<text text-anchor="middle" x="101.27" y="-126.68" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add20 --> +<g id="node9" class="node"> +<title>Add20</title> +<ellipse fill="none" stroke="black" cx="238" cy="-192" rx="27" ry="18"/> +<text text-anchor="middle" x="238" y="-188.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add20->Mul8 --> +<g id="edge11" class="edge"> +<title>Add20->Mul8</title> +<path fill="none" stroke="black" d="M223.27,-207.18C217,-212.81 209.43,-219.09 202,-224 194.96,-228.65 153.81,-248.53 124.4,-262.57"/> +<polygon fill="black" stroke="black" points="122.84,-259.44 115.32,-266.9 125.85,-265.75 122.84,-259.44"/> +<text text-anchor="middle" x="220.27" y="-209.78" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_21 --> +<g id="node10" class="node"> +<title>Con_21</title> +<ellipse fill="none" stroke="black" cx="238" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="238" y="-274.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Add20->Con_21 --> +<g id="edge12" class="edge"> +<title>Add20->Con_21</title> +<path fill="none" stroke="black" d="M238,-210.4C238,-221.74 238,-236.77 238,-249.68"/> +<polygon fill="black" stroke="black" points="234.5,-249.9 238,-259.9 241.5,-249.9 234.5,-249.9"/> +<text text-anchor="middle" x="235" y="-213" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return24->If11 --> +<g id="edge13" class="edge"> +<title>Return24->If11:p1</title> +<path fill="none" stroke="red" d="M169.73,-124.08C165.33,-133.41 160.65,-145.54 158.81,-157.76"/> +<polygon fill="red" stroke="red" points="155.3,-157.76 158,-168 162.28,-158.31 155.3,-157.76"/> +<text text-anchor="middle" x="166.73" y="-126.68" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return24->Add20 --> +<g id="edge14" class="edge"> +<title>Return24->Add20</title> +<path fill="none" stroke="black" d="M191.22,-124.4C199.86,-136.7 211.55,-153.35 221.09,-166.92"/> +<polygon fill="black" stroke="black" points="218.37,-169.15 226.98,-175.32 224.1,-165.12 218.37,-169.15"/> +<text text-anchor="middle" x="188.22" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter09/09-graph3.gv b/docs/chapter09/09-graph3.gv new file mode 100644 index 00000000..37bb1c53 --- /dev/null +++ b/docs/chapter09/09-graph3.gv @@ -0,0 +1,37 @@ +digraph chapter08 { +/* +return arg*arg-arg*arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Mul6 [ label="*" ]; + Mul7 [ label="*" ]; + Sub8 [ label="-" ]; + Return9 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return9[taillabel=0 color=red]; + Mul6 -> Start2:p1[taillabel=1]; + Mul6 -> Start2:p1[taillabel=2]; + Mul7 -> Start2:p1[taillabel=1]; + Mul7 -> Start2:p1[taillabel=2]; + Sub8 -> Mul6[taillabel=1]; + Sub8 -> Mul7[taillabel=2]; + Return9 -> Start2:p0[taillabel=0 color=red]; + Return9 -> Sub8[taillabel=1]; +} diff --git a/docs/chapter09/09-graph3.svg b/docs/chapter09/09-graph3.svg new file mode 100644 index 00000000..f26c96e8 --- /dev/null +++ b/docs/chapter09/09-graph3.svg @@ -0,0 +1,109 @@ +<?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="186pt" height="392pt" + viewBox="0.00 0.00 186.00 392.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 388)"> +<title>chapter08</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-388 182,-388 182,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-376 170,-376 170,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="24,-339 24,-364 105,-364 105,-339 24,-339"/> +<polygon fill="none" stroke="black" points="24,-339 24,-364 105,-364 105,-339 24,-339"/> +<text text-anchor="start" x="46" y="-347.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="24,-308 24,-339 105,-339 105,-308 24,-308"/> +<polygon fill="yellow" stroke="transparent" points="29,-313 29,-334 69,-334 69,-313 29,-313"/> +<polygon fill="none" stroke="black" points="29,-313 29,-334 69,-334 69,-313 29,-313"/> +<text text-anchor="start" x="32" y="-319.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="69,-313 69,-334 100,-334 100,-313 69,-313"/> +<text text-anchor="start" x="72" y="-319.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="83,-52 29,-52 29,-16 83,-16 83,-52"/> +<text text-anchor="middle" x="56" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return9 --> +<g id="node6" class="node"> +<title>Return9</title> +<polygon fill="yellow" stroke="black" points="89,-124 23,-124 23,-88 89,-88 89,-124"/> +<text text-anchor="middle" x="56" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return9 --> +<g id="edge1" class="edge"> +<title>Stop3->Return9</title> +<path fill="none" stroke="red" d="M56,-52.3C56,-60.02 56,-69.29 56,-77.89"/> +<polygon fill="red" stroke="red" points="52.5,-77.9 56,-87.9 59.5,-77.9 52.5,-77.9"/> +<text text-anchor="middle" x="53" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Mul6 --> +<g id="node3" class="node"> +<title>Mul6</title> +<ellipse fill="none" stroke="black" cx="63" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-246.3" font-family="Times,serif" font-size="14.00">*</text> +</g> +<!-- Mul6->Start2 --> +<g id="edge2" class="edge"> +<title>Mul6->Start2:p1</title> +<path fill="none" stroke="black" d="M72.2,-267.01C76.96,-276.47 82.18,-289.06 84.17,-301.8"/> +<polygon fill="black" stroke="black" points="80.7,-302.32 85,-312 87.67,-301.75 80.7,-302.32"/> +<text text-anchor="middle" x="69.2" y="-269.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Mul7 --> +<g id="node4" class="node"> +<title>Mul7</title> +<ellipse fill="none" stroke="black" cx="135" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-246.3" font-family="Times,serif" font-size="14.00">*</text> +</g> +<!-- Mul7->Start2 --> +<g id="edge4" class="edge"> +<title>Mul7->Start2:p1</title> +<path fill="none" stroke="black" d="M116.38,-263.15C104.61,-272.17 90.81,-285.67 86.42,-301.7"/> +<polygon fill="black" stroke="black" points="82.9,-301.62 85,-312 89.83,-302.57 82.9,-301.62"/> +<text text-anchor="middle" x="113.38" y="-265.75" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Sub8 --> +<g id="node5" class="node"> +<title>Sub8</title> +<ellipse fill="none" stroke="black" cx="63" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-174.3" font-family="Times,serif" font-size="14.00">-</text> +</g> +<!-- Sub8->Mul6 --> +<g id="edge6" class="edge"> +<title>Sub8->Mul6</title> +<path fill="none" stroke="black" d="M63,-196.3C63,-204.02 63,-213.29 63,-221.89"/> +<polygon fill="black" stroke="black" points="59.5,-221.9 63,-231.9 66.5,-221.9 59.5,-221.9"/> +<text text-anchor="middle" x="60" y="-198.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Sub8->Mul7 --> +<g id="edge7" class="edge"> +<title>Sub8->Mul7</title> +<path fill="none" stroke="black" d="M77.57,-193.17C87.75,-203.06 101.52,-216.45 113.03,-227.64"/> +<polygon fill="black" stroke="black" points="110.59,-230.15 120.2,-234.62 115.47,-225.13 110.59,-230.15"/> +<text text-anchor="middle" x="74.57" y="-195.77" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return9->Start2 --> +<g id="edge8" class="edge"> +<title>Return9->Start2:p0</title> +<path fill="none" stroke="red" d="M43.69,-124.22C37.35,-134.16 30.27,-147.2 27,-160 15.11,-206.5 15.97,-221.28 27,-268 31.12,-285.46 43.28,-289.17 47.52,-302.01"/> +<polygon fill="red" stroke="red" points="44.08,-302.62 49,-312 51,-301.6 44.08,-302.62"/> +<text text-anchor="middle" x="40.69" y="-126.82" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return9->Sub8 --> +<g id="edge9" class="edge"> +<title>Return9->Sub8</title> +<path fill="none" stroke="black" d="M57.73,-124.3C58.5,-132.02 59.43,-141.29 60.29,-149.89"/> +<polygon fill="black" stroke="black" points="56.81,-150.29 61.29,-159.9 63.78,-149.6 56.81,-150.29"/> +<text text-anchor="middle" x="54.73" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter09/09-graph4.gv b/docs/chapter09/09-graph4.gv new file mode 100644 index 00000000..8886f73a --- /dev/null +++ b/docs/chapter09/09-graph4.gv @@ -0,0 +1,29 @@ +digraph chapter09 { +/* +return arg*arg-arg*arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_9 [ label="#0" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return10[taillabel=0 color=red]; + Return10 -> Start2:p0[taillabel=0 color=red]; + Return10 -> Con_9[taillabel=1]; +} diff --git a/docs/chapter09/09-graph4.svg b/docs/chapter09/09-graph4.svg new file mode 100644 index 00000000..4eef5414 --- /dev/null +++ b/docs/chapter09/09-graph4.svg @@ -0,0 +1,67 @@ +<?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="178pt" height="248pt" + viewBox="0.00 0.00 178.00 248.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 244)"> +<title>chapter09</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 174,-244 174,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-232 162,-232 162,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<polygon fill="none" stroke="black" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<text text-anchor="start" x="30.5" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="24,-164 24,-195 74,-195 74,-164 24,-164"/> +<polygon fill="yellow" stroke="transparent" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<polygon fill="none" stroke="black" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<text text-anchor="start" x="32" y="-175.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="112,-52 58,-52 58,-16 112,-16 112,-52"/> +<text text-anchor="middle" x="85" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return10 --> +<g id="node4" class="node"> +<title>Return10</title> +<polygon fill="yellow" stroke="black" points="118,-124 52,-124 52,-88 118,-88 118,-124"/> +<text text-anchor="middle" x="85" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return10 --> +<g id="edge1" class="edge"> +<title>Stop3->Return10</title> +<path fill="none" stroke="red" d="M85,-52.3C85,-60.02 85,-69.29 85,-77.89"/> +<polygon fill="red" stroke="red" points="81.5,-77.9 85,-87.9 88.5,-77.9 81.5,-77.9"/> +<text text-anchor="middle" x="82" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_9 --> +<g id="node3" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="127" cy="-192" rx="27" ry="18"/> +<text text-anchor="middle" x="127" y="-188.3" font-family="Times,serif" font-size="14.00">#0</text> +</g> +<!-- Return10->Start2 --> +<g id="edge2" class="edge"> +<title>Return10->Start2:p0</title> +<path fill="none" stroke="red" d="M68.26,-124.13C60.77,-133.26 52.99,-145.23 50.13,-158.06"/> +<polygon fill="red" stroke="red" points="46.66,-157.67 49,-168 53.61,-158.46 46.66,-157.67"/> +<text text-anchor="middle" x="65.26" y="-126.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return10->Con_9 --> +<g id="edge3" class="edge"> +<title>Return10->Con_9</title> +<path fill="none" stroke="black" d="M93.7,-124.4C99.66,-136.31 107.65,-152.3 114.31,-165.62"/> +<polygon fill="black" stroke="black" points="111.28,-167.38 118.88,-174.76 117.54,-164.25 111.28,-167.38"/> +<text text-anchor="middle" x="90.7" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter09/09-graph5.gv b/docs/chapter09/09-graph5.gv new file mode 100644 index 00000000..72274239 --- /dev/null +++ b/docs/chapter09/09-graph5.gv @@ -0,0 +1,63 @@ +digraph chapter09 { +/* +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#1" ]; + Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg9 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT10 [ label="<" ]; + Con_11 [ label="#10" ]; + If12 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Add16 [ label="+" ]; + Add18 [ label="+" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop7;Phi_arg9;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + Loop7 -> Start2:p0[taillabel=1 color=red]; + Loop7 -> If12:p0[taillabel=2 color=red constraint=false]; + Phi_arg9 -> Loop7 [style=dotted taillabel=0]; + Phi_arg9 -> Start2:p1[taillabel=1]; + Phi_arg9 -> Add18[taillabel=2 constraint=false]; + LT10 -> Phi_arg9[taillabel=1]; + LT10 -> Con_11[taillabel=2]; + If12 -> Loop7[taillabel=0 color=red]; + If12 -> LT10[taillabel=1]; + Add16 -> Con_6[taillabel=1]; + Add16 -> Phi_arg9[taillabel=2]; + Add18 -> Add16[taillabel=1]; + Add18 -> Con_6[taillabel=2]; + Return21 -> If12:p1[taillabel=0 color=red]; + Return21 -> Phi_arg9[taillabel=1]; +} 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->Return21 --> +<g id="edge1" class="edge"> +<title>Stop3->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->Start2 --> +<g id="edge2" class="edge"> +<title>Loop7->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->If12 --> +<g id="edge3" class="edge"> +<title>Loop7->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->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg9->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->Loop7 --> +<g id="edge4" class="edge"> +<title>Phi_arg9->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->Add18 --> +<g id="edge6" class="edge"> +<title>Phi_arg9->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"><</text> +</g> +<!-- LT10->Phi_arg9 --> +<g id="edge7" class="edge"> +<title>LT10->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->Con_11 --> +<g id="edge8" class="edge"> +<title>LT10->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->Loop7 --> +<g id="edge9" class="edge"> +<title>If12->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->LT10 --> +<g id="edge10" class="edge"> +<title>If12->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->Con_6 --> +<g id="edge11" class="edge"> +<title>Add16->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->Phi_arg9 --> +<g id="edge12" class="edge"> +<title>Add16->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->Con_6 --> +<g id="edge14" class="edge"> +<title>Add18->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->Add16 --> +<g id="edge13" class="edge"> +<title>Add18->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->Phi_arg9 --> +<g id="edge16" class="edge"> +<title>Return21->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->If12 --> +<g id="edge15" class="edge"> +<title>Return21->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> diff --git a/docs/chapter09/09-graph6.gv b/docs/chapter09/09-graph6.gv new file mode 100644 index 00000000..56dc6ada --- /dev/null +++ b/docs/chapter09/09-graph6.gv @@ -0,0 +1,60 @@ +digraph chapter09 { +/* +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg9 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT10 [ label="<" ]; + Con_11 [ label="#10" ]; + If12 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_24 [ label="#2" ]; + Add25 [ label="+" ]; + { rank=same; Loop7;Phi_arg9;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + Loop7 -> Start2:p0[taillabel=1 color=red]; + Loop7 -> If12:p0[taillabel=2 color=red constraint=false]; + Phi_arg9 -> Loop7 [style=dotted taillabel=0]; + Phi_arg9 -> Start2:p1[taillabel=1]; + Phi_arg9 -> Add25[taillabel=2 constraint=false]; + LT10 -> Phi_arg9[taillabel=1]; + LT10 -> Con_11[taillabel=2]; + If12 -> Loop7[taillabel=0 color=red]; + If12 -> LT10[taillabel=1]; + Return21 -> If12:p1[taillabel=0 color=red]; + Return21 -> Phi_arg9[taillabel=1]; + Add25 -> Phi_arg9[taillabel=1]; + Add25 -> Con_24[taillabel=2]; +} diff --git a/docs/chapter09/09-graph6.svg b/docs/chapter09/09-graph6.svg new file mode 100644 index 00000000..36c70099 --- /dev/null +++ b/docs/chapter09/09-graph6.svg @@ -0,0 +1,184 @@ +<?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="149,-439 149,-464 230,-464 230,-439 149,-439"/> +<polygon fill="none" stroke="black" points="149,-439 149,-464 230,-464 230,-439 149,-439"/> +<text text-anchor="start" x="171" y="-447.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="149,-408 149,-439 230,-439 230,-408 149,-408"/> +<polygon fill="yellow" stroke="transparent" points="154,-413 154,-434 194,-434 194,-413 154,-413"/> +<polygon fill="none" stroke="black" points="154,-413 154,-434 194,-434 194,-413 154,-413"/> +<text text-anchor="start" x="157" y="-419.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="194,-413 194,-434 225,-434 225,-413 194,-413"/> +<text text-anchor="start" x="197" 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="157,-52 103,-52 103,-16 157,-16 157,-52"/> +<text text-anchor="middle" x="130" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return21 --> +<g id="node8" class="node"> +<title>Return21</title> +<polygon fill="yellow" stroke="black" points="163,-124 97,-124 97,-88 163,-88 163,-124"/> +<text text-anchor="middle" x="130" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return21 --> +<g id="edge1" class="edge"> +<title>Stop3->Return21</title> +<path fill="none" stroke="red" d="M130,-52.3C130,-60.02 130,-69.29 130,-77.89"/> +<polygon fill="red" stroke="red" points="126.5,-77.9 130,-87.9 133.5,-77.9 126.5,-77.9"/> +<text text-anchor="middle" x="127" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop7 --> +<g id="node3" class="node"> +<title>Loop7</title> +<polygon fill="yellow" stroke="black" points="314,-368 260,-368 260,-332 314,-332 314,-368"/> +<text text-anchor="middle" x="287" y="-346.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop7->Start2 --> +<g id="edge2" class="edge"> +<title>Loop7->Start2:p0</title> +<path fill="none" stroke="red" d="M259.93,-364.13C234.34,-376.71 197.56,-395.24 181.73,-405.41"/> +<polygon fill="red" stroke="red" points="179.34,-402.85 174,-412 183.88,-408.18 179.34,-402.85"/> +<text text-anchor="middle" x="256.93" y="-357.73" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If12 --> +<g id="node7" class="node"> +<title>If12</title> +<polygon fill="yellow" stroke="transparent" points="36,-195 36,-220 130,-220 130,-195 36,-195"/> +<polygon fill="none" stroke="black" points="36,-195 36,-220 130,-220 130,-195 36,-195"/> +<text text-anchor="start" x="77.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="36,-164 36,-195 130,-195 130,-164 36,-164"/> +<polygon fill="yellow" stroke="transparent" points="41,-169 41,-190 81,-190 81,-169 41,-169"/> +<polygon fill="none" stroke="black" points="41,-169 41,-190 81,-190 81,-169 41,-169"/> +<text text-anchor="start" x="44" y="-175.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="81,-169 81,-190 125,-190 125,-169 81,-169"/> +<polygon fill="none" stroke="black" points="81,-169 81,-190 125,-190 125,-169 81,-169"/> +<text text-anchor="start" x="84" y="-175.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- Loop7->If12 --> +<g id="edge3" class="edge"> +<title>Loop7->If12:p0</title> +<path fill="none" stroke="red" d="M259.79,-335.23C256.86,-334.03 253.9,-332.92 251,-332 163.26,-304.1 109.06,-364.01 47,-296 22.33,-268.96 18.57,-203.69 31.46,-184.44"/> +<polygon fill="red" stroke="red" points="33.44,-187.32 40,-179 29.68,-181.42 33.44,-187.32"/> +<text text-anchor="middle" x="256.79" y="-328.83" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg9 --> +<g id="node4" class="node"> +<title>Phi_arg9</title> +<ellipse fill="lightyellow" stroke="black" cx="133" cy="-350" rx="37.09" ry="18"/> +<text text-anchor="middle" x="133" y="-346.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg9->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg9->Start2:p1</title> +<path fill="none" stroke="black" d="M162.55,-360.93C181.21,-369 202.84,-382.27 208.56,-401.87"/> +<polygon fill="black" stroke="black" points="205.12,-402.59 210,-412 212.05,-401.61 205.12,-402.59"/> +<text text-anchor="middle" x="159.55" y="-363.53" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg9->Loop7 --> +<g id="edge4" class="edge"> +<title>Phi_arg9->Loop7</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M151.47,-334.01C161.54,-326.34 174.66,-317.98 188,-314 211,-307.14 219.35,-306.06 242,-314 249.14,-316.5 255.99,-320.67 262.09,-325.3"/> +<polygon fill="black" stroke="black" points="259.99,-328.1 269.92,-331.78 264.45,-322.71 259.99,-328.1"/> +<text text-anchor="middle" x="148.47" y="-327.61" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add25 --> +<g id="node10" class="node"> +<title>Add25</title> +<ellipse fill="none" stroke="black" cx="209" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="209" y="-274.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- LT10 --> +<g id="node5" class="node"> +<title>LT10</title> +<ellipse fill="none" stroke="black" cx="83" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="83" y="-274.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg9 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg9</title> +<path fill="none" stroke="black" d="M94.1,-294.54C100.33,-303.26 108.25,-314.35 115.31,-324.24"/> +<polygon fill="black" stroke="black" points="112.58,-326.43 121.24,-332.53 118.27,-322.36 112.58,-326.43"/> +<text text-anchor="middle" x="91.1" y="-297.14" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_11 --> +<g id="node6" class="node"> +<title>Con_11</title> +<ellipse fill="none" stroke="black" cx="47" cy="-350" rx="30.59" ry="18"/> +<text text-anchor="middle" x="47" y="-346.3" font-family="Times,serif" font-size="14.00">#10</text> +</g> +<!-- LT10->Con_11 --> +<g id="edge8" class="edge"> +<title>LT10->Con_11</title> +<path fill="none" stroke="black" d="M74.65,-295.24C70.35,-303.6 65.01,-313.98 60.17,-323.39"/> +<polygon fill="black" stroke="black" points="57.02,-321.87 55.55,-332.37 63.24,-325.07 57.02,-321.87"/> +<text text-anchor="middle" x="71.65" y="-297.84" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If12->Loop7 --> +<g id="edge9" class="edge"> +<title>If12->Loop7</title> +<path fill="none" stroke="red" d="M138.19,-204.98C172.47,-214.83 215.47,-231.87 245,-260 262.62,-276.78 273.63,-302.43 279.94,-321.89"/> +<polygon fill="red" stroke="red" points="276.66,-323.13 282.89,-331.7 283.36,-321.11 276.66,-323.13"/> +<text text-anchor="middle" x="141.19" y="-198.58" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If12->LT10 --> +<g id="edge10" class="edge"> +<title>If12->LT10</title> +<path fill="none" stroke="black" d="M83,-224.28C83,-232.58 83,-241.48 83,-249.56"/> +<polygon fill="black" stroke="black" points="79.5,-249.6 83,-259.6 86.5,-249.6 79.5,-249.6"/> +<text text-anchor="middle" x="80" y="-226.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return21->Phi_arg9 --> +<g id="edge12" class="edge"> +<title>Return21->Phi_arg9</title> +<path fill="none" stroke="black" d="M137.07,-124.33C140.84,-134.53 145.09,-147.78 147,-160 155.96,-217.25 145.96,-285.18 138.86,-322"/> +<polygon fill="black" stroke="black" points="135.39,-321.46 136.86,-331.95 142.26,-322.84 135.39,-321.46"/> +<text text-anchor="middle" x="134.07" y="-126.93" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return21->If12 --> +<g id="edge11" class="edge"> +<title>Return21->If12:p1</title> +<path fill="none" stroke="red" d="M117.92,-124C112.25,-133.3 106.24,-145.44 103.95,-157.94"/> +<polygon fill="red" stroke="red" points="100.46,-157.71 103,-168 107.43,-158.38 100.46,-157.71"/> +<text text-anchor="middle" x="114.92" y="-126.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_24 --> +<g id="node9" class="node"> +<title>Con_24</title> +<ellipse fill="none" stroke="black" cx="215" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="215" y="-346.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Add25->Phi_arg9 --> +<g id="edge13" class="edge"> +<title>Add25->Phi_arg9</title> +<path fill="none" stroke="black" d="M185.95,-300.23C176.82,-308.64 166.31,-318.32 157.07,-326.83"/> +<polygon fill="black" stroke="black" points="188.64,-302.51 193.62,-293.17 183.89,-297.37 188.64,-302.51"/> +<polygon fill="black" stroke="black" points="154.66,-324.29 149.68,-333.64 159.4,-329.44 154.66,-324.29"/> +<text text-anchor="middle" x="190.62" y="-295.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add25->Con_24 --> +<g id="edge14" class="edge"> +<title>Add25->Con_24</title> +<path fill="none" stroke="black" d="M210.48,-296.3C211.14,-304.02 211.94,-313.29 212.68,-321.89"/> +<polygon fill="black" stroke="black" points="209.19,-322.23 213.53,-331.9 216.17,-321.63 209.19,-322.23"/> +<text text-anchor="middle" x="207.48" y="-298.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +</g> +</svg> diff --git a/docs/chapter09/Makefile b/docs/chapter09/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter09/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter09/README.md b/docs/chapter09/README.md new file mode 100644 index 00000000..fd03277c --- /dev/null +++ b/docs/chapter09/README.md @@ -0,0 +1,300 @@ +# Chapter 9: Global Value Numbering and Iterative Peepholes + +# Table of Contents + +1. [Engineering Peepholes](#engineering-peepholes) +2. [Global Value Numbering](#global-value-numbering) +3. [Post-Parse Iterative Peepholes](#post-parse-iterative-peepholes) +4. [Distant Neighbors](#distant-neighbors) +5. [Identification of Basic Blocks in SoN graph](#identification-of-basic-blocks-in-son-graph) +6. [Other Concerns](#other-concerns) +7. [Common SubExpressions via GVN](#common-subexpressions-via-gvn) + - [Example 1](#example-1) + - [Example 2](#example-2) +8. [Post Parse Iterative Optimizations](#post-parse-iterative-optimizations) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter09) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter08...linear-chapter09) it to the previous chapter. + +In this chapter: + +* We add Global Value Numbering (Common Subexpression Elimination) +* We add a post-parse iterate-peepholes-to-fixed-point optimization + +No language changes in this chapter, just adding optimizations. + + +## Engineering Peepholes + +The goal for Ch 9 is to "finish out" the Peepholes. Not that no more peeps will +appear, on the contrary lots will - but this is the infrastructure to organize +them, engineer them safe and sane; to apply them until a fixed point is reached. + +Really the goal here is to be fearless about adding a new peephole; if you got +it wrong you'll assert pretty fast. If you got it right, that new peep will +just run alongside all the others and they will all mutually benefit each other. + + +## Global Value Numbering + +Global Value Numbering works via a classic hash table, hashing on a Node's +opcode and inputs. If two Nodes do the same function on the same inputs, they +get the same result - and can be shared. + +* We add a global static hash table `GVN` in Node. +* We add a `Node.equals` call. Two Nodes are equals if they have the same + opcode - same Java class - on the same inputs. +* We add a `hashCode` on the Node opcode (proxy: Node string name) and inputs. +* `ConstantNode` and a few others need some extra custom bits here: the + constant 17 is not the same as 99, but both are the same `ConstantNode` class + and label. The `eq` and `hash` calls check (or hash) these extra bits. + +Note the intentional *value* equality here. In many places in Simple we use +*reference* equality - e.g. node/edge maintenance is via reference equality, not +value equality, so e.g. the `Utils.find()` call finds via reference. Through +out the Simple project whenever a Node lookup is happening, beware if its via +*value* or *reference* equality; this is not always explicitly called out but +should be obvious from context. + + +Since we edit the graph a lot, Nodes can have their inputs change which changes +their hash which means they can't be found in the GVN table. E.g. we swap out +the `Add` for a `Con` in: + + (Mul (Add 4 8) x) // Fold the constant + (Mul 12 x) // The `Mul` changes hash and inputs + +The fix for this is to require Nodes NOT be in the `GVN` table when their edges +modify; they need some sort of "edge lock". If "edges are locked", we need to +remove the Node from `GVN` first, before modifying the edges. + +* We use the `_hash` field as both a cached hash code and as the edge lock. If + zero the Node is unlocked and NOT in `GVN`. If non-zero, the Node is + "edge-locked" and IS in `GVN`. +* The `hashCode` function uses the cached hash if available and disallows an + accidental zero hash. +* We add a `unlock()` call to remove a Node from `GVN` before any edge is + changed. This is inserted in front of all calls which hack Node edges. All + edge modify code paths already ensure the Node is re-peepholed, and during + this revisit the Node will get re-inserted in the `GVN` table. + +This new `GVN` table is used in `peepholeOpt()` (and `peephole()`) to look for common +subexpressions on every peephole'd Node. If the Node has a zero hash, we look +for a hit against some previous identical Node. If found, we use the prior +Node and dead-code-eliminate this one. If not found, we insert this Node +into `GVN` as the "golden instance". If a Node already has a non-zero hash +we know it IS the "golden instance" and do not need to look in `GVN`. + +This entire optimization takes about a dozen lines in `iter()`, plus the common +shared `equals` and `hashCode` (about 50 more lines counting comments). + +One of our invariants is that Types monotonically increase while running +peepholes. GVN can break this briefly: of the two equivalent Nodes one has +already had its `_type` lifted but not the other. Depending on which of the +two Nodes is kept, we might choose the Node with the "lower" `_type`. This is +"lower" in the Type lattice sense. Both types must be correct, and a +`compute()` call on both nodes must produce the same Type, which must be equal +to the JOIN. A fix is to compute a JOIN (not a MEET) over the two Nodes' types. + + +## Post-Parse Iterative Peepholes + +The post-Parse `IterPeeps` iterates the peepholes to a fixed point - so +no more peepholes apply. This should be linear because peepholes rarely +(never?) increase code size. The graph should monotonically reduce in some +dimension, which is usually size. It might also reduce in e.g. number of +MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper +ones. + +The theoretical overall worklist is mindless just grabbing the next thing and +doing it. If the graph changes, put the neighbors on the worklist. Lather, +Rinse, Repeat until the worklist runs dry. + +The main issues we have to deal with: + +* Nodes have uses; replacing some set of Nodes with another requires more graph + reworking. Not rocket science, but it can be fiddly. Its helpful to have a + small set of graph munging utilities, and the strong invariant that the graph + is stable and correct between peepholes. In our case `Node.subsume` does + most of the munging, building on our prior stable Node utilities. + +* Changing a Node also changes the graph "neighborhood". The neigbors need to + be checked to see if THEY can also peephole, and so on. After any peephole + or graph update we put a Nodes uses and defs on the worklist. + +* Our strong invariant is that for all Nodes, either they are on the worklist + OR no peephole applies. This invariant is easy to check, although expensive. + Basically the normal "iterate peepholes to a fixed point" is linear, and this + check is linear at each peephole step... so quadratic overall. Its a useful + assert, but one we can disable once the overall algorithm is stable - and + then turn it back on again when some new set of peepholes is misbehaving. + The code for this is turned on in `IterPeeps.iterate` as `assert + progressOnList(stop);` + + +## Distant Neighbors + +For some peepholes the "neighborhood" is farther away than just the immediate +uses or defs, and for these we need a longer range plan. E.g. some peephole +inspects "this -> A -> B -> C" and will swap itself for "D"; however it fails +some test at "B". Should "B" ever update we want to revisit "this" and recheck +his peepholes. So we will need to record a dependence of "this" in "B". +Updating "B" throws the dependent list ("this") onto the "todo" list. + +An example of a distant neighbor check is in `AddNode`, where we check for +stacked constants: `(Add (Add x 2) 1)` and we'd like `(Add x 3)` instead. +Suppose we're doing this check and we find instead `(Add (Phi (Add x 2) self) +1)` The check naturally bails out at the `Phi` since its not an `Add`, but the +`(Phi y self)` only has one unique input, and will itself peephole to `y` +eventually. When it does, our stacked `Add` peephole can apply. So the +failing Add peephole calls `phi.addDep(Add)` and registers a dependency on the +`Phi`. If the `Phi` indeed later optimizes, we add its depencencies (e.g. the +`Add`) back on our `IterPeeps` worklist and retry the stacked Add peephole. + +The general rule is: +* **If a peephole pattern inspects a remote node, it must go on the dependency list!** +* `node.in(1).in(2)` becomes `node.in(1).in(2).addDep(node)` + + +In this chapter we trigger on following patterns + +* Some peeps interact with `Phi` inputs; this can be direct or indirect, + e.g. `(Add Add( (Phi x) 2 ) 1)`. The peep can progress if all of the `Phi`'s + inputs are `Constant`'s. Thus, we make the node a dependent on the `Phi`'s + input. We also make the node a dependent of the `Phi`'s region. See + `Node.allCons()` and `PhiNode.allCons()`. +* The pattern `(Add (Add x 1) 2)` adds the outer `Add` as dependency of `x` + because `x` becoming a constant would enable progress. See + `AddNode.idealize()` +* When computing a `Phi`'s type, if we observe that the associated region's + corresponding control is live, we add the `Phi` as a dependent of the + region's control input, because if that control goes dead, it would allow the + `Phi` to undergo peephole. See `PhiNode.compute()` and + `PhiNode.singleUniqueInput()`. + +Changes: + +* We add a `ArrayList<Node> _deps` field to Node; initially null. +* Some peepholes (see above) add dependencies if they fail a remote check, by calling + `distant.addDep(this)`. The `addDep` call creates `_deps` and + filters for various kinds of duplicate adds. +* The `IterPeeps` loop, when it finds a change, also moves all the + dependents onto the worklist. + + +## Other Concerns + +There are more issues we will want to deal with in a later Chapter: + +* Blindly running peepholes in any order has some drawbacks: + + - Dead and dying stuff might get peepholes done... and then die. Wasted work. + - Dead infinite loops often lead to infinite peephole cycles... if only we + would get around to working on the "base" of the dead loop it would fold + up. + - Some peepholes naturally reduce the graph directly; while some keeps its + size the same but reduce other things (e.g. swapping a Mul-by-2 with a + Shift), and we might end up with a few which try to grow the graph briefly + before collapsing. + +* All this means is there's some benefit to running peepholes that reduce the + graph directly (e.g. Dead Code Eliminate), before running peeps that reduce + other things, before running all other peeps. This implies a sorted + worklist, but the count of unique orders is really limited - a radix sort is + all that is needed. We'll have to break up the peepholes into some + categories like + - "strictly reducing" vs + - "same Nodes but swapping e.g. `Mul` for `Shift`, vs + - getting more freedom (edge bypass), vs + - "grow now because shrink later" (inlining lands in this camp). + +* Also there's a benefit to not always grabbing from either end of the list - + many peep patterns might go quadratic if approached from one end or another, + because they modify something then push it back onto the list where it + immediately gets pulled again. I.e., you end up spinning in a loop repeating + the same peeps while slowly migrating a e.g. left-spine add-tree into a + right-spine add-tree. A psuedo-random pull uses randomization to defeat bad + peep patterns. + +* Why isn't `IterPeeps` just passing over all of the Nodes once or twice, + instead of using a worklist with the `addDeps` mechanism? We could even + visit them in a defs-before-uses order (e.g. Reverse Post Order). + + In the absense of loops exactly one such pass will find all local peepholes, + and indeed the Parser already does this. However, this will fail to find + opportunities at loops and farther remote cases - and to get those peepholes + around loops will require another visit. It is easy to construct a case + requiring O(N) passes, each of cost O(N) and the algorithm quickly goes + quadratic. + + The `addDeps` solution avoids this quadratic cost, in exchange for some more + costs in writing peepholes. + + +# Examples + +## Common SubExpressions via GVN + +### Example 1 + +Here is a small example that illustrates how GVN enables finding common sub-expressions. + +```java +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; +``` + +Prior to GVN, this would result in following graph. Note that the `arg+arg` is translated to `arg*2`. + + + +Adding GVN, we get below. Note how the `arg*2` expression is now reused rather than appearing twice. + + + +### Example 2 + +Being able to reuse common expressions, enables additional optimizations. Here is a simple example: + +```java +return arg*arg-arg*arg; +``` + +Without GVN the peepholes cannot see that both sides of the subtraction have the same value. + + + +- Each multiplication(*) node has two edges going to `arg`. +- In the example above, we fused them to make the graph more readable. + +With GVN, the peepholes can do a better job: + + + +## Post Parse Iterative Optimizations + +The worklist based post parse optimization enables certain optimizations that are not available +during parsing. For example: + +```java +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; +``` + +While parsing the `while` loop it is not yet known that `step` is a constant and will not change. Therefore, +without the post parse optimization we get following: + + + +Enabling the post parse worklist based optimization yields below. Notice that now the graph shows `arg+2` inside the +loop body: + + |
