diff options
55 files changed, 3105 insertions, 302 deletions
@@ -68,7 +68,13 @@ $(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" tests: $(default_targets) - $(JVM) org.junit.runner.JUnitCore $(test_cp) com.seaofnodes.simple.FuzzerWrap + @echo "testing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore $(test_cp) com.seaofnodes.simple.FuzzerWrap + +fuzzer: $(default_targets) + @echo "testing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap + .PHONY: clean clean: @@ -50,7 +50,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow. * [Chapter 7](docs/chapter07/README.md): `while` statement; looping constructs - eager phi approach. * [Chapter 8](docs/chapter08/README.md): Looping constructs continued, lazy phi creation, `break` and `continue` statements. -* Chapter 9: Global Value Numbering. Iterative peepholes to fixpoint. Worklists. +* [Chapter 9](docs/chapter09/README.md): Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * Chapter 10a: User defined structs, pointers and null analysis. One memory value in SSA. Loads, stores, and an executable evaluator. * Chapter 10b: Equivalence class aliasing. Lazy memory diff --git a/docs/chapter09/09-grammar.md b/docs/chapter09/09-grammar.md new file mode 100644 index 00000000..00f93e04 --- /dev/null +++ b/docs/chapter09/09-grammar.md @@ -0,0 +1,94 @@ +# Grammar for Chapter 8 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +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: + + diff --git a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java index f5694a78..9fc51c8e 100644 --- a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java +++ b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -167,7 +167,7 @@ public class GraphEvaluator { public static long evaluate(Node graph, long parameter, int loops) { var res = evaluateWithResult(graph, parameter, loops); - if (res.type==ResultType.TIMEOUT) throw new RuntimeException("Timeout"); + if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout"); return res.value; } diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index 2a6dbefd..c06ac9d0 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -48,14 +48,15 @@ public class IRPrinter { // First walk the CFG, then everything if( n.isCFG() ) { for( Node use : n._outputs ) - if( use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) + if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) postOrd(use, rpos,visit,bfs); for( Node use : n._outputs ) - if( use.isCFG() ) + if( use!=null && use.isCFG() ) postOrd(use,rpos,visit,bfs); } for( Node use : n._outputs ) - postOrd(use, rpos,visit,bfs); + if( use != null ) + postOrd(use, rpos,visit,bfs); // Post-order rpos.add(n); } diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java new file mode 100644 index 00000000..41fc6916 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -0,0 +1,208 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.BitSet; +import java.util.Random; + +/** + * The IterOptim runs after parsing. It iterates the peepholes to a fixed point + * so that 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: + * + * <ul> + * <li>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.</li> + * + * <li>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.</li> + * + * <li>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 `IterOptim.iterate` as `assert + * progressOnList(stop);`</li> + * </ul> + */ +public abstract class IterPeeps { + + private static final WorkList<Node> WORK = new WorkList<>(); + + public static <N extends Node> N add( N n ) { + return (N)WORK.push(n); + } + + public static void addAll( ArrayList<Node> ary ) { + WORK.addAll(ary); + } + + /** + * Iterate peepholes to a fixed point + */ + public static StopNode iterate(StopNode stop) { + assert progressOnList(stop); + int cnt=0; + + Node n; + while( (n=WORK.pop()) != null ) { + if( n.isDead() ) continue; + cnt++; // Useful for debugging, searching which peephole broke things + var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(n); + Node x = n.peepholeOpt(); + if( x != null ) { + if( x.isDead() ) { + if( obs != null ) obs.after(n, x, true); + continue; + } + // peepholeOpt can return brand-new nodes, needing an initial type set + if( x._type==null ) x.setType(x.compute()); + // Changes require neighbors onto the worklist + if( x != n || !(x instanceof ConstantNode) ) { + // All outputs of n (changing node) not x (prior existing node). + for( Node z : n._outputs ) WORK.push(z); + // Everybody gets a free "go again" in case they didn't get + // made in their final form. + WORK.push(x); + // If the result is not self, revisit all inputs (because + // there's a new user), and replace in the graph. + if( x != n ) { + for( Node z : n. _inputs ) WORK.push(z); + n.subsume(x); + } + } + // If there are distant neighbors, move to worklist + n.moveDepsToWorklist(); + assert progressOnList(stop); // Very expensive assert + } + if( obs != null ) obs.after(n, x, true); + } + + return stop; + } + + // Visit ALL nodes and confirm the invariant: + // Either you are on the WORK worklist OR running `iter()` makes no progress. + + // This invariant ensures that no progress is missed, i.e., when the + // worklist is empty we have indeed done all that can be done. To help + // with debugging, the {@code assert} is broken out in a place where it is easy to + // stop if a change is found. + + // Also, the normal usage of `iter()` may attempt peepholes with distance + // neighbors and these should fail, but will then try to add dependencies + // {@link #Node.addDep} which is a side effect in an assert. The {@link + // #midAssert} is used to stop this side effect. + private static boolean MID_ASSERT; + public static boolean midAssert() { return MID_ASSERT; } + private static boolean progressOnList(Node stop) { + MID_ASSERT = true; + int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT; + Node changed = stop.walk( n -> { + if( WORK.on(n) ) return null; + Node m = n.peepholeOpt(); + if( m==null ) return null; + System.err.println("BREAK HERE FOR BUG"); + return m; + }); + Node.ITER_CNT = old_cnt; Node.ITER_NOP_CNT = old_nop; + MID_ASSERT = false; + return changed==null; + } + + public static void reset() { + WORK.clear(); + } + + /** + * Classic WorkList, with a fast add/remove, dup removal, random pull. + * The Node's nid is used to check membership in the worklist. + */ + public static class WorkList<E extends Node> { + + private Node[] _es; + private int _len; + private final BitSet _on; // Bit set if Node._nid is on WorkList + private final Random _R; // For randomizing pull from the WorkList + private final long _seed; + + /* Useful stat - how many nodes are processed in the post parse iterative opt */ + private long _totalWork = 0; + + WorkList() { this(123); } + WorkList(long seed) { + _es = new Node[1]; + _len=0; + _on = new BitSet(); + _seed = seed; + _R = new Random(); + _R.setSeed(_seed); + } + + /** + * Pushes a Node on the WorkList, ensuring no duplicates + * If Node is null it will not be added. + */ + public E push( E x ) { + if( x==null ) return null; + int idx = x._nid; + if( !_on.get(idx) ) { + _on.set(idx); + if( _len==_es.length ) + _es = Arrays.copyOf(_es,_len<<1); + _es[_len++] = x; + _totalWork++; + } + return x; + } + + public void addAll( ArrayList<E> ary ) { + for( E n : ary ) + push(n); + } + + /** + * True if Node is on the WorkList + */ + boolean on( E x ) { return _on.get(x._nid); } + + /** + * Removes a random Node from the WorkList; null if WorkList is empty + */ + E pop() { + if( _len == 0 ) return null; + int idx = _R.nextInt(_len); + E x = (E)_es[idx]; + _es[idx] = _es[--_len]; // Compress array + _on.clear(x._nid); + return x; + } + + public void clear() { + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index d7055f48..3c1eab96 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -78,11 +78,12 @@ public class Parser { public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); + IterPeeps.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); - STOP = new StopNode(); + STOP = new StopNode(source); } public Parser(String source) { @@ -115,7 +116,6 @@ public class Parser { return STOP; } - /** * Parses a block * @@ -191,11 +191,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole(); // Clone the body Scope to create the break/exit Scope which accounts for any // side effects in the predicate. The break/exit Scope will be the final @@ -209,7 +208,7 @@ public class Parser { // Parse the true side, which corresponds to loop body // Our current scope is the body Scope - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body // Merge the loop bottom into other continue statements @@ -253,7 +252,7 @@ public class Parser { return cur; // toScope is either the break scope, or a scope that was created here assert toScope._scopes.size() <= _breakScope._scopes.size(); - toScope.mergeScopes(cur); + toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -275,11 +274,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current int ndefs = _scope.nIns(); @@ -288,12 +286,13 @@ public class Parser { _xScopes.push(fScope); // For graph visualization we need all scopes // Parse the true side - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection parseStatement(); // Parse true-side ScopeNode tScope = _scope; // Parse the false side _scope = fScope; // Restore scope, then parse else block if any + ifF.unkeep(); // fScope already owns the false control if (matchx("else")) { parseStatement(); fScope = _scope; @@ -383,12 +382,23 @@ public class Parser { */ private Node parseComparison() { var lhs = parseAddition(); - if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); - if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); - if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); - if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); - if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); - if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + while( true ) { + int idx=0; boolean negate=false; + // Test for any local nodes made, and "keep" lhs during peepholes + if( false ) ; + else if( match("==") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); } + else if( match("!=") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); negate=true; } + else if( match("<=") ) { idx=2; lhs = new BoolNode.LE(lhs, null); } + else if( match("<" ) ) { idx=2; lhs = new BoolNode.LT(lhs, null); } + else if( match(">=") ) { idx=1; lhs = new BoolNode.LE(null, lhs); } + else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); } + else break; + // Peepholes can fire, but lhs is already "hooked", kept alive + lhs.setDef(idx,parseAddition()); + lhs = lhs.peephole(); + if( negate ) // Extra negate for != + lhs = new NotNode(lhs).peephole(); + } return lhs; } @@ -401,9 +411,15 @@ public class Parser { * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { - var lhs = parseMultiplication(); - if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); - if (match("-")) return new SubNode(lhs, parseAddition()).peephole(); + Node lhs = parseMultiplication(); + while( true ) { + if( false ) ; + else if( match("+") ) lhs = new AddNode(lhs,null); + else if( match("-") ) lhs = new SubNode(lhs,null); + else break; + lhs.setDef(2,parseMultiplication()); + lhs = lhs.peephole(); + } return lhs; } @@ -417,8 +433,14 @@ public class Parser { */ private Node parseMultiplication() { var lhs = parseUnary(); - if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); - if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); + while( true ) { + if( false ) ; + else if( match("*") ) lhs = new MulNode(lhs,null); + else if( match("/") ) lhs = new DivNode(lhs,null); + else break; + lhs.setDef(2,parseUnary()); + lhs = lhs.peephole(); + } return lhs; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index fa3a6169..b57b305f 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -19,11 +19,14 @@ public class AddNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()+i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } @@ -32,12 +35,8 @@ public class AddNode extends Node { public Node idealize () { Node lhs = in(1); Node rhs = in(2); - Type t1 = lhs._type; Type t2 = rhs._type; - // Already handled by peephole constant folding - assert !(t1.isConstant() && t2.isConstant()); - // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) if( t2 instanceof TypeInteger i && i.value()==0 ) @@ -53,6 +52,10 @@ public class AddNode extends Node { if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) return swap12(); + // x+(-y) becomes x-y + if( rhs instanceof MinusNode minus ) + return new SubNode(lhs,minus.in(1)); + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) // Do we have x + (y + z) ? @@ -64,7 +67,7 @@ public class AddNode extends Node { // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) if( !(lhs instanceof AddNode) ) // Rotate; look for (add (phi cons) con/(phi cons)) - return spine_cmp(lhs,rhs) ? swap12() : phiCon(this,true); + return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true); // Now we only see (add add non) @@ -75,7 +78,11 @@ public class AddNode extends Node { // Do we have (x + con1) + con2? // Replace with (x + (con1+con2) which then fold the constants - if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + // lhs.in(2) is con1 here + // If lhs.in(2) is not a constant, we add ourselves as a dependency + // because if it later became a constant then we could make this + // transformation. + if( lhs.in(2).addDep(this)._type.isConstant() && rhs._type.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); @@ -89,7 +96,7 @@ public class AddNode extends Node { // Do we rotate (x + y) + z // into (x + z) + y ? - if( spine_cmp(lhs.in(2),rhs) ) + if( spine_cmp(lhs.in(2),rhs,this) ) return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); return null; @@ -102,16 +109,16 @@ public class AddNode extends Node { Node lhs = op.in(1); Node rhs = op.in(2); // LHS is either a Phi of constants, or another op with Phi of constants - PhiNode lphi = pcon(lhs); + PhiNode lphi = pcon(lhs,op); if( rotate && lphi==null && lhs.nIns() > 2 ) { // Only valid to rotate constants if both are same associative ops if( lhs.getClass() != op.getClass() ) return null; - lphi = pcon(lhs.in(2)); // Will rotate with the Phi push + lphi = pcon(lhs.in(2),op); // Will rotate with the Phi push } if( lphi==null ) return null; // RHS is a constant or a Phi of constants - if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null ) + if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==null ) return null; // If both are Phis, must be same Region @@ -132,8 +139,15 @@ public class AddNode extends Node { return lhs==lphi ? phi : op.copy(lhs.in(1),phi); } - static PhiNode pcon(Node op) { - return op instanceof PhiNode phi && phi.allCons() ? phi : null; + /** + * Tests if the op is a phi and has all constant inputs. + * If not, returns null. + * If op is a phi, but its inputs are not all constants, then dep is added as + * a dependency to the phi's non-const input, because if later the input turn into a constant + * dep can make progress. + */ + static PhiNode pcon(Node op, Node dep) { + return op instanceof PhiNode phi && phi.allCons(dep) ? phi : null; } // Compare two off-spine nodes and decide what order they should be in. @@ -141,12 +155,15 @@ public class AddNode extends Node { // Generally constants always go right, then Phi-of-constants, then muls, then others. // Ties with in a category sort by node ID. // TRUE if swapping hi and lo. - static boolean spine_cmp( Node hi, Node lo ) { + static boolean spine_cmp( Node hi, Node lo, Node dep ) { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; - if( lo instanceof PhiNode && lo.allCons() ) return false; - if( hi instanceof PhiNode && hi.allCons() ) return true ; + if( lo instanceof PhiNode lphi && lphi.region()._type==Type.XCONTROL ) return false; + if( hi instanceof PhiNode hphi && hphi.region()._type==Type.XCONTROL ) return false; + + if( lo instanceof PhiNode && lo.allCons(dep) ) return false; + if( hi instanceof PhiNode && hi.allCons(dep) ) return true ; if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index f5bbc9ad..08ff3789 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -25,11 +25,14 @@ abstract public class BoolNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); - return i0.meet(i1); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index b7ec8292..8fd955e9 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -8,7 +8,7 @@ import java.util.BitSet; /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer - * value. As we add other types of constants, we will refactor how we represent + * value. As we add other types of constants, we will refactor how we represent * Constants. * <p> * Constants have no semantic inputs. However, we set Start as an input to @@ -25,7 +25,7 @@ public class ConstantNode extends Node { } @Override - public String label() { return ""+_con; } + public String label() { return "#"+_con; } @Override public String uniqueName() { return "Con_" + _nid; } @@ -42,4 +42,18 @@ public class ConstantNode extends Node { @Override public Node idealize() { return null; } + + @Override + boolean eq(Node n) { + ConstantNode con = (ConstantNode)n; // Contract + return _con==con._con; + } + + @Override + int hash() { return _con.hashCode(); } + + // Dead control is its own idom root + Node idom() { return null; } + @Override int idepth() { return 0; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index f71a32db..6cee90ad 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -19,13 +19,16 @@ public class DivNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return i1.value() == 0 ? TypeInteger.ZERO : TypeInteger.constant(i0.value()/i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 23a8fafc..460dce51 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -32,27 +32,30 @@ public class IfNode extends MultiNode { // If the If node is not reachable then neither is any following Proj if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) return TypeTuple.IF_NEITHER; + Node pred = pred(); + Type t = pred._type; + // High types mean NEITHER side is reachable. + // Wait until the type falls to decide which way to go. + if( t == Type.TOP || t == TypeInteger.TOP ) + return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable - if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { - if (ti.value() == 0) return TypeTuple.IF_FALSE; - else return TypeTuple.IF_TRUE; - } - - // Hunt up the immediate dominator tree. If we find an identical if - // test on either the true or false branch, then this test matches. - for( Node dom = idom(), prior=this; dom!=null; prior=dom, dom = dom.idom() ) - if( dom instanceof IfNode iff && iff.pred()==pred() ) - return prior instanceof ProjNode proj - // Repeated test, dominated on one side. Test result is the same. - ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) - : dom._type; // Repeated test not dominated on one side + if (t instanceof TypeInteger ti && ti.isConstant()) + return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; } @Override public Node idealize() { + // Hunt up the immediate dominator tree. If we find an identical if + // test on either the true or false branch, that side wins. + if( !pred()._type.isHighOrConst() ) + for( Node dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) + if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) { + setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); + return this; + } return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 9d3d3f5d..5b055089 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -20,7 +20,7 @@ public class MinusNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0) return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return TypeInteger.BOT; + return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 4884ee18..97721ce3 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -19,11 +19,14 @@ public class MulNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()*i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 7ba1aa19..2743bd19 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -4,4 +4,11 @@ public abstract class MultiNode extends Node { public MultiNode(Node... inputs) { super(inputs); } + // Find a projection by index + ProjNode proj( int idx ) { + for( Node out : _outputs ) + if( out instanceof ProjNode prj && prj._idx==idx ) + return prj; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index ffb868cb..a0ec0289 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -3,10 +3,12 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IRPrinter; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; +import java.util.function.Function; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -65,6 +67,7 @@ public abstract class Node { * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; + public static int UID() { return UNIQUE_ID; } protected Node(Node... inputs) { _nid = UNIQUE_ID++; // allocate unique dense ID @@ -103,7 +106,7 @@ public abstract class Node { // This is the common print: check for repeats, check for DEAD and print // "DEAD" else call the per-Node print1. final StringBuilder _print0(StringBuilder sb, BitSet visited) { - if (visited.get(_nid)) + if (visited.get(_nid) && !(this instanceof ConstantNode) ) return sb.append(label()); visited.set(_nid); return isDead() @@ -129,7 +132,7 @@ public abstract class Node { sb.append(" "); sb.append(" [[ "); for( Node use : _outputs ) - sb.append("%4d ".formatted(use._nid)); + sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); int lim = 5 - Math.max(_inputs.size(),3); for( int i = _outputs.size(); i<lim; i++ ) sb.append(" "); @@ -152,6 +155,7 @@ public abstract class Node { * @return Input node or null */ public Node in(int i) { return _inputs.get(i); } + public Node out(int i) { return _outputs.get(i); } public int nIns() { return _inputs.size(); } @@ -177,9 +181,10 @@ public abstract class Node { * @param new_def the new definition * @return new_def for flow coding */ - Node setDef(int idx, Node new_def ) { + public Node setDef(int idx, Node new_def ) { + unlock(); Node old_def = in(idx); - if( old_def == new_def ) return this; // No change + if( old_def == new_def ) return new_def; // No change // If new def is not null, add the corresponding def->use edge // This needs to happen before removing the old node's def->use edge as // the new_def might get killed if the old node kills it recursively. @@ -196,13 +201,17 @@ public abstract class Node { // Remove the numbered input, compressing the inputs in-place. This // shuffles the order deterministically - which is suitable for Region and - // Phi, but not for every Node. - void delDef(int idx) { + // Phi, but not for every Node. If the def goes dead, it is recursively + // killed, which may include 'this' Node. + Node delDef(int idx) { + unlock(); Node old_def = in(idx); if( old_def != null && // If the old def exists, remove a def->use edge old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def + old_def.moveDepsToWorklist(); Utils.del(_inputs, idx); + return this; } /** @@ -213,6 +222,7 @@ public abstract class Node { * @return new_def for flow coding */ Node addDef(Node new_def) { + unlock(); // Add use->def edge _inputs.add(new_def); // If new def is not null, add the corresponding def->use edge @@ -235,6 +245,7 @@ public abstract class Node { // Shortcut for "popping" n nodes. A "pop" is basically a // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { + unlock(); for( int i=0; i<n; i++ ) { Node old_def = _inputs.removeLast(); if( old_def != null && // If it exists and @@ -245,13 +256,21 @@ public abstract class Node { /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> - * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #popN}. + * to null. This may recursively kill more Nodes, and is basically dead + * code elimination. */ public void kill( ) { + unlock(); assert isUnused(); // Has no uses, so it is dead - popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead + while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes + Node old_def = _inputs.removeLast(); + if( old_def != null ) { + IterPeeps.add(old_def);// Revisit neighbor because removed use + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + } + } assert isDead(); // Really dead now } @@ -266,10 +285,11 @@ public abstract class Node { // Replace self with nnn in the graph, making 'this' go dead - void subsume( Node nnn ) { + public void subsume( Node nnn ) { assert nnn!=this; while( nOuts() > 0 ) { Node n = _outputs.removeLast(); + n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); nnn.addUse(n); @@ -281,6 +301,19 @@ public abstract class Node { // Graph-based optimizations /** + * Try to peephole at this node and return a better replacement Node. + * Always returns some not-null Node (often this). + */ + public final Node peephole() { + var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(this); + Node n = peepholeOpt(); + Node rez = n == null ? this : deadCodeElim(n.peephole()); + if( obs != null ) obs.after(this, n == null ? null : rez, false); + return rez; + } + + /** * Try to peephole at this node and return a better replacement Node if * possible. We compute a {@link Type} and then check and replace: * <ul> @@ -293,36 +326,45 @@ public abstract class Node { * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing * math constants, remove algebraic identities and generally simplify the * code. </li> + * + * Unlike peephole above, this explicitly returns null for no-change, or not-null + * for a better replacement (which can be this). * </ul> */ - public final Node peephole() { - var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; - if( obs != null ) obs.before(this); - Type old = _type; - Node n = peepholeOpt(); - Node rez = n == null ? this : n; - if( obs != null ) obs.after(this, n == null && old == _type ? null : rez, false); - return rez; - } - - private Node peepholeOpt() { + public final Node peepholeOpt( ) { + ITER_CNT++; // Compute initial or improved Type - Type type = _type = compute(); + Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if (!(this instanceof ConstantNode) && type.isConstant()) - return deadCodeElim(new ConstantNode(type).peephole()); - - // Future chapter: Global Value Numbering goes here + if (!(this instanceof ConstantNode) && _type.isHighOrConst() ) + return new ConstantNode(_type).peepholeOpt(); + + // Global Value Numbering + if( _hash==0 ) { + Node n = GVN.get(this); // Will set _hash as a side effect + if( n==null ) + GVN.put(this,this); // Put in table now + else { + // Because of random worklist ordering, the two equal nodes + // might have different types. Because of monotonicity, both + // types are valid. To preserve monotonicity, the resulting + // shared Node has to have the best of both types. + n.setType(n._type.join(_type)); + _hash = 0; // Clear, since it never went in the table + return deadCodeElim(n);// Return previous; does Common Subexpression Elimination + } + } // Ask each node for a better replacement Node n = idealize(); if( n != null ) // Something changed - // Recursively optimize - return deadCodeElim(n.peephole()); + return n; // Report progress - return null; // No progress - } + if( old==_type ) ITER_NOP_CNT++; + return old==_type ? null : this; // Report progress + } + public static int ITER_CNT, ITER_NOP_CNT; // m is the new Node, self is the old. // Return 'm', which may have zero uses but is alive nonetheless. @@ -352,13 +394,26 @@ public abstract class Node { * theory. Much later on, this will become important and allow us to do * many fancy complex optimizations trivially... because theory. * <p> - * compute() needs to be stand-alone, and cannot recursively call compute - * on its inputs programs are cyclic (have loops!) and this will just + * {@link #compute()} needs to be stand-alone, and cannot recursively call compute + * on its inputs, because programs are cyclic (have loops!) and this will just * infinitely recurse until stack overflow. Instead, compute typically * computes a new type from the {@link #_type} field of its inputs. */ public abstract Type compute(); + // Set the type. Assert monotonic progress. + // If changing, add users to worklist. + public Type setType(Type type) { + Type old = _type; + assert old==null || type.isa(old); // Since _type not set, can just re-run this in assert in the debugger + if( old == type ) return old; + _type = type; // Set _type late for easier assert debugging + IterPeeps.addAll(_outputs); + moveDepsToWorklist(); + return old; + } + + /** * This function rewrites the current Node into a more "idealized" form. * This is the bulk of our peephole rewrite rules, and we use this to @@ -398,32 +453,131 @@ public abstract class Node { * call peephole. * <p> * Since idealize calls peephole and peephole calls idealize, you must be - * careful that all idealizations are <em>monotonic</em>: all transforms remove - * some feature, so that the set of available transforms always shrinks. - * If you don't, you risk an infinite peephole loop! + * careful that all idealizations are <em>monotonic</em>: all transforms + * remove some feature, so that the set of available transforms always + * shrinks. If you don't, you risk an infinite peephole loop! * * @return Either a new or changed node, or null for no changes. */ public abstract Node idealize(); + // Some of the peephole rules get complex, and search further afield than + // just the nearest neighbor. These peepholes can fail the pattern match + // on a node some distance away, and if that node ever changes we should + // retry the peephole. Track a set of Nodes dependent on `this`, and + // revisit them if `this` changes. + ArrayList<Node> _deps; + public int nDeps() { return _deps == null ? 0 : _deps.size(); } + public Node dep(int idx) { return _deps.get(idx); } + + /** + * Add a node to the list o dependencies. Only add it if its not + * an input or output of this node, that is, it is at least one step + * away. The node being added must benefit from this node being peepholed. + */ + Node addDep( Node dep ) { + // Running peepholes during the big assert cannot have side effects + // like adding dependencies. + if( IterPeeps.midAssert() ) return this; + var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.dep(this, dep); + if( _deps==null ) _deps = new ArrayList<>(); + if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list + if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors + if( Utils.find(_outputs,dep)!= -1 ) return this; + _deps.add(dep); + return this; + } + + // Move the dependents onto a worklist, and clear for future dependents. + public void moveDepsToWorklist( ) { + if( _deps==null ) return; + IterPeeps.addAll(_deps); + _deps.clear(); + } + + + // Global Value Numbering. Hash over opcode and inputs; hits in this table + // are structurally equal. + public static final HashMap<Node,Node> GVN = new HashMap<>(); + + // Two nodes are equal if they have the same inputs and the same "opcode" + // which means the same Java class, plus same internal parts. + @Override public final boolean equals( Object o ) { + if( o==this ) return true; + if( o.getClass() != getClass() ) return false; + Node n = (Node)o; + int len = _inputs.size(); + if( len != n._inputs.size() ) return false; + for( int i=0; i<len; i++ ) + if( in(i) != n.in(i) ) + return false; + return eq(n); + } + // Subclasses add extra checks (such as ConstantNodes have same constant), + // and can assume "this!=n" and has the same Java class. + boolean eq( Node n ) { return true; } + + + // Cached hash. If zero, then not computed AND this Node is NOT in the GVN + // table - and can have its edges hacked (which will change his hash + // anyway). If Non-Zero then this Node is IN the GVN table, or is being + // probed to see if it can be inserted. His edges are "locked", because + // hacking his edges will change his hash. + int _hash; + + // If the _hash is set, then the Node is in the GVN table; remove it. + void unlock() { + if( _hash==0 ) return; + Node old = GVN.remove(this); // Pull from table + assert old==this; + _hash=0; // Out of table now + } + + + // Hash of opcode and inputs + @Override public final int hashCode() { + if( _hash != 0 ) return _hash; + int hash = hash(); + for( Node n : _inputs ) + if( n != null ) + hash = hash ^ (hash<<17) ^ (hash>>13) ^ n._nid; + if( hash==0 ) hash = 0xDEADBEEF; // Bad hash, so use some junky thing + return (_hash=hash); + } + // Subclasses add extra hash info (such as ConstantNodes constant) + int hash() { return 0; } + + // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. Node swap12() { + unlock(); // Hash is order dependent Node tmp = in(1); _inputs.set(1,in(2)); _inputs.set(2,tmp); return this; } - // does this node contain all constants? - // Ignores in(0), as is usually control. - boolean allCons() { + /** + * Does this node contain all constants? + * Ignores in(0), as is usually control. + * In an input is not a constant, we add dep as + * a dependency to it, because dep can make progress + * if the input becomes a constant later. + * It is sufficient for one of the non-const + * inputs to have the dependency so we don't bother + * checking the rest. + */ + boolean allCons(Node dep) { for( int i=1; i<nIns(); i++ ) - if( !(in(i)._type.isConstant()) ) + if( !(in(i)._type.isConstant()) ) { + in(i).addDep(dep); // If in(i) becomes a constant later, will trigger some peephole return false; + } return true; } @@ -462,25 +616,35 @@ public abstract class Node { */ public static void reset() { UNIQUE_ID = 1; + GVN.clear(); + ITER_CNT = ITER_NOP_CNT = 0; + } + + + // Utility to walk the entire graph applying a function; return the first + // not-null result. + private static final BitSet WVISIT = new BitSet(); + final public <E> E walk( Function<Node,E> pred ) { + assert WVISIT.isEmpty(); + E rez = _walk(pred); + WVISIT.clear(); + return rez; + } + + private <E> E _walk( Function<Node,E> pred ) { + if( WVISIT.get(_nid) ) return null; // Been there, done that + WVISIT.set(_nid); + E x = pred.apply(this); + if( x != null ) return x; + for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; + for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; + return null; } /** * Debugging utility to find a Node by index */ - public Node find(int nid) { return _find(new BitSet(),nid); } - private Node _find(BitSet visit, int nid) { - if( _nid==nid ) return this; - if( visit.get(_nid) ) return null; - visit.set(_nid); - for( Node def : _inputs ) - if( def!=null ) { - Node rez = def._find(visit,nid); - if( rez != null ) return rez; - } - for( Node use : _outputs ) { - Node rez = use._find(visit,nid); - if( rez != null ) return rez; - } - return null; + public Node find(int nid) { + return walk( n -> n._nid==nid ? n : null ); } } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index 4c0be167..a9a69c59 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -20,7 +20,7 @@ public class NotNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; - return TypeInteger.BOT; + return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 7eeed394..13c9423d 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -14,7 +14,7 @@ public class PhiNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( region().inProgress() ) + if( !(region() instanceof RegionNode r) || r.inProgress() ) sb.append("Z"); sb.append("Phi("); for( Node in : _inputs ) { @@ -27,23 +27,29 @@ public class PhiNode extends Node { return sb; } - RegionNode region() { return (RegionNode)in(0); } + Node region() { return in(0); } @Override public boolean isMultiTail() { return true; } @Override public Type compute() { - if( !(region() instanceof RegionNode r) || r.inProgress() ) - return Type.BOTTOM; + if( !(region() instanceof RegionNode r) ) + return region()._type==Type.XCONTROL ? Type.TOP : _type; + if( r.inProgress() ) return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) - t = t.meet(in(i)._type); + // If the region's control input is live, add this as a dependency + // to the control because we can be peeped should it become dead. + if( r.in(i).addDep(this)._type != Type.XCONTROL && in(i) != this ) + t = t.meet(in(i)._type); return t; } @Override public Node idealize() { - if( !(region() instanceof RegionNode r ) || r.inProgress() ) - return null; + if( !(region() instanceof RegionNode r ) ) + return in(1); // Input has collapse to e.g. starting control. + if( r.inProgress() || r.nIns()<=1 ) + return null; // Input is in-progress // If we have only a single unique input, become it. Node live = singleUniqueInput(); @@ -82,11 +88,13 @@ public class PhiNode extends Node { * If only single unique input, return it */ private Node singleUniqueInput() { + if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL ) + return null; // Dead entry loops just ignore and let the loop collapse Node live = null; for( int i=1; i<nIns(); i++ ) { - if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL ) - return null; // Dead entry loops just ignore and let the loop collapse - if( region().in(i)._type != Type.XCONTROL && in(i) != this ) + // If the region's control input is live, add this as a dependency + // to the control because we can be peeped should it become dead. + if( region().in(i).addDep(this)._type != Type.XCONTROL && in(i) != this ) if( live == null || live == in(i) ) live = in(i); else return null; } @@ -94,9 +102,22 @@ public class PhiNode extends Node { } @Override - boolean allCons() { - if( !(region() instanceof RegionNode r) || r.inProgress() ) - return false; - return super.allCons(); + boolean allCons(Node dep) { + if( !(region() instanceof RegionNode r) ) return false; + // When the region completes (is no longer in progress) the Phi can + // become a "all constants" Phi, and the "dep" might make progress. + addDep(dep); + if( r.inProgress() ) return false; + return super.allCons(dep); + } + + // True if last input is null + public final boolean inProgress() { + return in(nIns()-1) == null; + } + + // Never equal if inProgress + @Override boolean eq( Node n ) { + return !inProgress(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 3c3f73b8..0ed9441d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -7,7 +7,7 @@ import java.util.BitSet; public class ProjNode extends Node { - // Which slice of the incoming multi-part value + // Which slice of the incoming multipart value public final int _idx; // Debugging label @@ -32,7 +32,7 @@ public class ProjNode extends Node { @Override public Type compute() { - Type t = ctrl()._type; + Type t = in(0)._type; return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } @@ -42,4 +42,10 @@ public class ProjNode extends Node { return ctrl().in(0); // We become our input control return null; } + + @Override + boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; } + + @Override + int hash() { return _idx; } } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 756b4e24..71bef275 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,9 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; -import java.util.Collection; +import java.util.ArrayList; +import java.util.Arrays; import java.util.BitSet; public class RegionNode extends Node { @@ -34,22 +36,29 @@ public class RegionNode extends Node { public Node idealize() { if( inProgress() ) return null; int path = findDeadInput(); - if( path != 0 ) { - for( Node phi : _outputs ) - if( phi instanceof PhiNode ) - phi.delDef(path); - delDef(path); - - // If down to a single input, become that input - but also make all - // Phis an identity on *their* single input. - if( nIns()==2 ) { - for( Node phi : _outputs ) - if( phi instanceof PhiNode ) - // Currently does not happen, because no loops - throw Utils.TODO(); - return in(1); + if( path != 0 && + // Do not delete the entry path of a loop (ok to remove the back + // edge and make the loop a single-entry Region which folds away + // the Loop). Folding the entry path confused the loop structure, + // moving the backedge to the entry point. + !(this instanceof LoopNode loop && loop.entry()==in(path)) ) { + // Cannot use the obvious output iterator here, because a Phi + // deleting an input might recursively delete *itself*. This + // shuffles the output array, and we might miss iterating an + // unrelated Phi. So on rare occasions we repeat the loop to get + // all the Phis. + int nouts = 0; + while( nouts != nOuts() ) { + nouts = nOuts(); + for( int i=0; i<nOuts(); i++ ) + if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) + phi.delDef(path); } - return this; + return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); + } + // If down to a single input, become that input + if( nIns()==2 && !hasPhi() ) { + return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own } return null; } @@ -61,6 +70,13 @@ public class RegionNode extends Node { return 0; // All inputs alive } + private boolean hasPhi() { + for( Node phi : _outputs ) + if( phi instanceof PhiNode ) + return true; + return false; + } + // Immediate dominator of Region is a little more complicated. @Override int idepth() { if( _idepth!=0 ) return _idepth; @@ -81,6 +97,11 @@ public class RegionNode extends Node { // True if last input is null public final boolean inProgress() { - return in(nIns()-1) == null; + return nIns()>1 && in(nIns()-1) == null; + } + + // Never equal if inProgress + @Override boolean eq( Node n ) { + return !inProgress(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 312058b9..922a3649 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -34,7 +34,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return new TypeTuple(ctrl()._type,expr()._type); + return TypeTuple.make(ctrl()._type,expr()._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index e5d03d93..3abea54d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -212,6 +213,8 @@ public class ScopeNode extends Node { if( in(i) instanceof PhiNode phi ) { // Do an eager useless-phi removal Node in = phi.peephole(); + IterPeeps.addAll(phi._outputs); + phi.moveDepsToWorklist(); if( in != phi ) { phi.subsume(in); setDef(i,in); // Set the update back into Scope diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index bab0f18c..1e3559ce 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -18,7 +18,7 @@ public class StartNode extends MultiNode { public StartNode(Type[] args) { super(); - _args = new TypeTuple(args); + _args = TypeTuple.make(args); _type = _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 417790d9..6ed80df4 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,12 +1,17 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.IterPeeps; import java.util.BitSet; public class StopNode extends Node { - public StopNode(Node... inputs) { - super(inputs); + + public final String _src; + + public StopNode(String src) { + super(); + _src = src; } @Override @@ -50,4 +55,5 @@ public class StopNode extends Node { return addDef(node); } + public StopNode iterate() { return IterPeeps.iterate(this); } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 421e659b..eeec5e1d 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -19,15 +19,18 @@ public class SubNode extends Node { @Override public Type compute() { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; // Sub of same is 0 if( in(1)==in(2) ) return TypeInteger.ZERO; - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 3c4dd7dd..df46cc6b 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -7,14 +7,16 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import java.util.ArrayList; -/** Chapter 8's view of the IR; browser, transport and layout are shared. */ +/** Chapter 9's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected boolean dead(Node n) { return n.isDead(); } @Override protected int id(Node n) { return n._nid; } @Override protected int nIns(Node n) { return n.nIns(); } @Override protected Node in(Node n, int idx) { return n.in(idx); } @Override protected int nOuts(Node n) { return n.nOuts(); } - @Override protected Node out(Node n, int idx) { return n._outputs.get(idx); } + @Override protected Node out(Node n, int idx) { return n.out(idx); } + @Override protected int nDeps(Node n) { return n.nDeps(); } + @Override protected Node dep(Node n, int idx) { return n.dep(idx); } private ArrayList<Edge> edges(Node n) { var edges = new ArrayList<Edge>(); diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 0c3f4ce8..2c6c90ca 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 8's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 9's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; @@ -22,6 +22,9 @@ public class SimpleGraphObserver extends GraphCapture<Node> { _phase = "Parse"; _ret = _parser.parse(); phase(_phase); + _phase = "Iter"; + com.seaofnodes.simple.IterPeeps.iterate(_parser.STOP); + phase(_phase); } @Override protected String phase() { return _phase; } @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index d66fb3e7..daaa8af6 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -1,5 +1,8 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.Utils; + +import java.util.HashMap; /** * These types are part of a Monotone Analysis Framework, @@ -18,6 +21,7 @@ package com.seaofnodes.simple.type; */ public class Type { + static final HashMap<Type,Type> INTERN = new HashMap<>(); // ---------------------------------------------------------- // Simple types are implemented fully here. "Simple" means: the code and @@ -36,15 +40,53 @@ public class Type { private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl"}; protected Type(byte type) { _type = type; } - public static final Type BOTTOM = new Type( TBOT ); // ALL - public static final Type TOP = new Type( TTOP ); // ANY - public static final Type CONTROL = new Type( TCTRL ); // Ctrl - public static final Type XCONTROL = new Type( TXCTRL ); // ~Ctrl + public static final Type BOTTOM = new Type( TBOT ).intern(); // ALL + public static final Type TOP = new Type( TTOP ).intern(); // ANY + public static final Type CONTROL = new Type( TCTRL ).intern(); // Ctrl + public static final Type XCONTROL = new Type( TXCTRL ).intern(); // ~Ctrl + + // Is high or on the lattice centerline. + public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; } - public boolean isConstant() { return _type == TTOP || _type == TXCTRL; } + // Strict constant values, things on the lattice centerline. + // Excludes both high and low values + public boolean isConstant() { return false; } public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} + // ---------------------------------------------------------- + + // Factory method which interns "this" + protected <T extends Type> T intern() { + T nnn = (T)INTERN.get(this); + if( nnn==null ) + INTERN.put(nnn=(T)this,this); + return nnn; + } + + private int _hash; // Hash cache; not-zero when set. + @Override + public final int hashCode() { + if( _hash!=0 ) return _hash; + _hash = hash(); + if( _hash==0 ) _hash = 0xDEADBEEF; // Bad hash from subclass; use some junk thing + return _hash; + } + // Override in subclasses + int hash() { return _type; } + + @Override + public final boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof Type t)) return false; + if( _type != t._type ) return false; + return eq(t); + } + // Overridden in subclasses; subclass can assume "this!=t" and java classes are same + boolean eq(Type t) { return true; } + + + // ---------------------------------------------------------- public final Type meet(Type t) { // Shortcut for the self case if( t == this ) return this; @@ -53,7 +95,7 @@ public class Type { // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this". if( is_simple() ) return this.xmeet(t ); if( t.is_simple() ) return t .xmeet(this); - return BOTTOM; // Mixing 2 unrelated types + return xmeet(t); // Mixing 2 unrelated types } // Compute meet right now. Overridden in subclasses. @@ -70,6 +112,28 @@ public class Type { return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; } + // True if this "isa" t; e.g. 17 isa TypeInteger.BOT + public boolean isa( Type t ) { return meet(t)==t; } + + // ---------------------------------------------------------- + // Our lattice is defined with a MEET and a DUAL. + // JOIN is dual of meet of both duals. + public final Type join(Type t) { + if( this==t ) return this; + return dual().meet(t.dual()).dual(); + } + + public Type dual() { + return switch( _type ) { + case TBOT -> TOP; + case TTOP -> BOTTOM; + case TCTRL -> XCONTROL; + case TXCTRL -> CONTROL; + default -> throw Utils.TODO(); // Should not reach here + }; + } + + // ---------------------------------------------------------- @Override public final String toString() { return print(new StringBuilder()).toString(); diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index a9f6ee1c..ab9dbcff 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -5,59 +5,70 @@ package com.seaofnodes.simple.type; */ public class TypeInteger extends Type { - public final static TypeInteger TOP = new TypeInteger(false, 0); - public final static TypeInteger BOT = new TypeInteger(false, 1); - public final static TypeInteger ZERO= new TypeInteger(true, 0); + public final static TypeInteger TOP = make(false, 0); + public final static TypeInteger BOT = make(false, 1); + public final static TypeInteger ZERO= make(true , 0); - private final boolean _is_con; + public final boolean _is_con; /** * The constant value or - * if not constant then 0=bottom, 1=top. + * if not constant then 1=bottom, 0=top. */ - private final long _con; + public final long _con; - public TypeInteger(boolean is_con, long con) { + private TypeInteger(boolean is_con, long con) { super(TINT); _is_con = is_con; _con = con; } + public static TypeInteger make(boolean is_con, long con) { + return new TypeInteger(is_con,con).intern(); + } - public static TypeInteger constant(long con) { return new TypeInteger(true, con); } - - public boolean isTop() { return !_is_con && _con==0; } - public boolean isBot() { return !_is_con && _con==1; } + public static TypeInteger constant(long con) { return make(true, con); } @Override public StringBuilder print(StringBuilder sb) { - if (isTop()) return sb.append("IntTop"); - if (isBot()) return sb.append("IntBot"); + if( this==TOP ) return sb.append("IntTop"); + if( this==BOT ) return sb.append("IntBot"); return sb.append(_con); } @Override + public boolean isHighOrConst() { return _is_con || _con==0; } + + @Override public boolean isConstant() { return _is_con; } public long value() { return _con; } @Override public Type xmeet(Type other) { - if( this==other ) return this; - if (!(other instanceof TypeInteger i)) return super.meet(other); + // Invariant from caller: 'this' != 'other' and same class (TypeInteger) + TypeInteger i = (TypeInteger)other; // Contract // BOT wins - if ( isBot() ) return this; - if ( i.isBot() ) return i ; + if ( this==BOT ) return this; + if ( i ==BOT ) return i ; // TOP loses - if ( i.isTop() ) return this; - if ( isTop() ) return i ; - assert isConstant() && i.isConstant(); - return _con==i._con ? this : TypeInteger.BOT; + if ( i ==TOP ) return this; + if ( this==TOP ) return i ; + // Since both are constants, and are never equals (contract) unequals + // constants fall to bottom + return BOT; } @Override - public boolean equals( Object o ) { - if( o==this ) return true; - if( !(o instanceof TypeInteger i) ) return false; + public Type dual() { + if( isConstant() ) return this; // Constants are a self-dual + return _con==0 ? BOT : TOP; + } + + @Override + int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); } + @Override + public boolean eq( Type t ) { + TypeInteger i = (TypeInteger)t; // Contract return _con==i._con && _is_con==i._is_con; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 39d8f72b..a2a6a095 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -4,14 +4,24 @@ public class TypeTuple extends Type { public final Type[] _types; - public TypeTuple(Type... _types) { - super(TTUPLE); - this._types = _types; - } + private TypeTuple(Type[] types) { super(TTUPLE); _types = types; } + public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); } @Override public Type xmeet(Type other) { - throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); + TypeTuple tt = (TypeTuple)other; // contract from xmeet + assert _types.length == tt._types.length; + Type[] ts = new Type[_types.length]; + for( int i=0; i<_types.length; i++ ) + ts[i] = _types[i].meet(tt._types[i]); + return make(ts); + } + + @Override public Type dual() { + Type[] ts = new Type[_types.length]; + for( int i=0; i<_types.length; i++ ) + ts[i] = _types[i].dual(); + return make(ts); } @Override @@ -24,9 +34,27 @@ public class TypeTuple extends Type { return sb; } - public static final TypeTuple IF_BOTH = new TypeTuple(new Type[]{Type.CONTROL, Type.CONTROL}); - public static final TypeTuple IF_NEITHER = new TypeTuple(new Type[]{Type.XCONTROL,Type.XCONTROL}); - public static final TypeTuple IF_TRUE = new TypeTuple(new Type[]{Type.CONTROL, Type.XCONTROL}); - public static final TypeTuple IF_FALSE = new TypeTuple(new Type[]{Type.XCONTROL,Type.CONTROL}); + public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL}); + public static final TypeTuple IF_NEITHER = make(new Type[]{Type.XCONTROL,Type.XCONTROL}); + public static final TypeTuple IF_TRUE = make(new Type[]{Type. CONTROL,Type.XCONTROL}); + public static final TypeTuple IF_FALSE = make(new Type[]{Type.XCONTROL,Type. CONTROL}); + + @Override + int hash() { + int sum = 0; + for( Type type : _types ) sum ^= type.hashCode(); + return sum; + } + + @Override + boolean eq( Type t ) { + TypeTuple tt = (TypeTuple)t; // Contract + if( _types.length != tt._types.length ) return false; + for( int i=0; i<_types.length; i++ ) + if( _types[i]!=tt._types[i] ) + return false; + return true; + } + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 609dff76..c3cd43c3 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -31,7 +31,7 @@ public class Chapter03Test { @Test public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); "); + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 68d379a1..6ad3af15 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -21,7 +21,7 @@ else { } return a;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } @@ -36,7 +36,7 @@ if (arg == 1) { c = 4; } return c;""", TypeInteger.BOT); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return Phi(Region16,4,3);", ret.toString()); } @@ -64,7 +64,7 @@ if( arg==1 ) else b=a+1; return a+b;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); } @@ -79,7 +79,7 @@ if( arg==1 ) else a=b+1; return a+b;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @@ -99,7 +99,7 @@ else a=5; return a; """, TypeInteger.BOT); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); } @@ -129,7 +129,7 @@ if( arg==1 ) a=arg==3; } return a;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); } @@ -169,6 +169,7 @@ return a;"""); } } + @Test public void testBadNum() { try { diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 00d725bc..054e96e8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -15,7 +15,7 @@ public class Chapter06Test { if( true ) return 2; return 1; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -29,7 +29,7 @@ if (arg) a = 2; return (arg < a) < 3; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); } @@ -44,7 +44,7 @@ else a=3; return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -64,7 +64,7 @@ if( a==2 ) else b=5; return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region32,42,5);", stop.toString()); } @@ -83,8 +83,8 @@ if( arg==2 ) else b=5; return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(); - assertEquals("return Phi(Region28,2,5);", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region29,2,5);", stop.toString()); } @Test @@ -123,7 +123,7 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 3;", stop.toString()); } @@ -143,8 +143,8 @@ else a=5; return a; """, TypeInteger.BOT); - StopNode stop = parser.parse(); - assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region37,3,Phi(Region35,4,5));", stop.toString()); } @Test @@ -163,7 +163,7 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 3;", stop.toString()); } @@ -183,7 +183,7 @@ else a=5; return a; """, TypeInteger.constant(3)); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 4;", stop.toString()); } @@ -199,8 +199,8 @@ if( arg ) { } return a+b; """); - StopNode ret = parser.parse(); - assertEquals("return Phi(Region22,4,1);", ret.toString()); + StopNode ret = parser.parse().iterate(); + assertEquals("return Phi(Region24,4,1);", ret.toString()); } @@ -216,7 +216,7 @@ if( arg ) { } return a+b; """, TypeInteger.constant(1)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 4;", ret.toString()); } @@ -232,7 +232,7 @@ if( arg ) { } return a+b; """, TypeInteger.constant(0)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 1;", ret.toString()); } @@ -250,8 +250,8 @@ if( arg ) { } return a+b+c; """); - StopNode ret = parser.parse(); - assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); + StopNode ret = parser.parse().iterate(); + assertEquals("return (Phi(Region35,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); } @@ -269,7 +269,7 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(1)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 6;", ret.toString()); } @@ -287,7 +287,7 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(2)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 5;", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 26b5c17d..109ee830 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -34,7 +34,7 @@ if(arg){}else{ } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } @@ -54,7 +54,7 @@ while(i < arg) { } return sum; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @@ -89,7 +89,7 @@ while(a < 10) { } return b; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -122,7 +122,7 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -148,7 +148,7 @@ int a = 1; while(arg) a = 2; return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -180,7 +180,7 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -214,7 +214,7 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 5d9d1545..cea6dd0f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -4,22 +4,12 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter08Test { @Test - @Ignore - public void testJig() { - Parser parser = new Parser(""" -// Insert test case here -"""); - StopNode stop = parser.parse(); - } - - @Test public void testEx6() { Parser parser = new Parser( """ @@ -32,7 +22,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1)); @@ -55,7 +45,7 @@ while(arg < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -74,7 +64,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -90,7 +80,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -109,7 +99,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -126,7 +116,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -142,15 +132,15 @@ while( arg < 10 ) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return arg;", stop.toString()); } @Test public void testRegress2() { Parser parser = new Parser("if(1) return 0; else while(arg>--arg) arg=arg+1; return 0;"); - StopNode stop = parser.parse(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); } @Test @@ -177,7 +167,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return arg;", stop.toString()); } @@ -194,7 +184,7 @@ while(arg < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -210,9 +200,9 @@ while(1) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof RegionNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java new file mode 100644 index 00000000..8103b903 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -0,0 +1,320 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.BeforeClass; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter09Test { + + @Test + @Ignore + public void testJig() { + Parser parser = new Parser(""" +int v0=0; +arg=0; +while(v0) { + while(1) if(arg*arg*0==0) {} + while(0) {} + arg=1; +} +return 0; + """); + StopNode stop = parser.parse().iterate(); + } + + @Test + public void testGVN1() { + Parser parser = new Parser( + """ +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + """); + StopNode stop = parser.parse(); + assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString()); + Assert.assertEquals(2, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(23, GraphEvaluator.evaluate(stop, 11)); + } + + @Test + public void testGVN2() { + Parser parser = new Parser( + """ +return arg*arg-arg*arg; + """); + StopNode stop = parser.parse(); + assertEquals("return 0;", stop.toString()); + Assert.assertEquals(0, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist1() { + Parser parser = new Parser( + """ +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop7,arg,(Phi_arg+2));", stop.toString()); + Assert.assertEquals(11, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist2() { + Parser parser = new Parser( + """ +int cond = 0; +int one = 1; +while (arg < 10) { + if (cond) one = 2; + arg = arg + one*3 + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop8,arg,(Phi_arg+4));", stop.toString()); + Assert.assertEquals(13, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist3() { + Parser parser = new Parser( + """ +int v1 = 0; +int v2 = 0; +int v3 = 0; +int v4 = 0; +int v5 = 0; +int v6 = 0; +int v7 = 0; +int v8 = 0; +while (arg) { + if (v1) v2 = 1; + if (v2) v3 = 1; + if (v3) v4 = 1; + if (v4) v5 = 1; + if (v5) v6 = 1; + if (v6) v7 = 1; + if (v7) v8 = 1; + arg = arg + v8 + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop14,arg,(Phi_arg+1));", stop.toString()); + } + + @Test + public void testRegionPeepBug() { + Parser parser = new Parser( + """ +int v0=0; +int v1=0; +while(v1+arg) { + arg=0; + int v2=v0; + while(arg+1) {} + v0=1; + v1=v2; +} + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testSccp() { + Parser parser = new Parser( +""" +int x = 1; +int cnt = 5; +while (cnt) { + cnt = cnt - 1; + if (x == 0) { + x = x + 1; + } +} +return x; +""" + ); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop8,1,Phi(Region26,(Phi_x+1),Phi_x));", stop.toString()); + + } + + @Test + public void testWhile0() { + Parser parser = new Parser("while(0) continue; if(0) arg=0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testWhile1() { + Parser parser = new Parser(""" +if(0) while(0) { + int arg=arg; + while(0) {} +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testPrecedence() { + Parser parser = new Parser("return 3-1+2;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + } + + @Test + public void testSwap2() { + Parser parser = new Parser("return 1+(1+1);"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3;", stop.toString()); + } + + + @Test + public void testFuzz0() { + Parser parser = new Parser(""" +int one = 1; +int a = 0; +int zero = 0; +while(arg) { + a = -(one + a + 2); + arg = arg + 1; + one = one + zero; +} +return a; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop9,0,(-(Phi_a+3)));", stop.toString()); + } + + @Test + public void testFuzz1() { + Parser parser = new Parser(""" +while(1) {} +while(arg) break; +while(arg) arg=0; +arg=0; +int v0=0!=0<-0; +return -0+0+0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testFuzz2() { + Parser parser = new Parser("return 0+-0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testFuzz3() { + Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz4() { + Parser parser = new Parser(""" +while(1) { + arg=0<=0; + if(1<0) while(arg==-0) arg=arg-arg; +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz5() { + Parser parser = new Parser(""" +{ + int v0=0; + while(1) + int v1=0--0; + while(v0) + break; + while(-v0) { + while(0+0+v0) continue; + break; + } + if(-0!=-0+0+v0) while(0+0+0+0) + break; +} +return 0!=0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz6() { + Parser parser = new Parser(""" +int v0=0; +while(0==1) while(v0) + v0=1+v0; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz7() { + Parser parser = new Parser(""" +while(1) {} +int v0=0; +while(v0) + {} +int v1=0; +while(1) + v1=1; +return v1+v0; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz8() { + Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop6,arg,(Phi_arg-1));", stop.toString()); + } + + @Test + public void testMeet() { + Type t1 = Type.TOP; + Type t2 = TypeInteger.TOP; + Assert.assertEquals(TypeInteger.TOP, t1.meet(t2)); + Assert.assertEquals(TypeInteger.TOP, t2.meet(t1)); + t1 = Type.BOTTOM; + t2 = TypeInteger.BOT; + Assert.assertEquals(Type.BOTTOM, t1.meet(t2)); + Assert.assertEquals(Type.BOTTOM, t2.meet(t1)); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 33434b6c..019140ad 100644 --- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.fuzzer.Fuzzer; -import org.junit.Ignore; import org.junit.Test; +import org.junit.Ignore; import static org.junit.Assert.assertTrue; @@ -33,9 +33,18 @@ public class FuzzerWrap { @Ignore public void fuzzPeepsLarge() { var fuzzer = new Fuzzer(); - for (int i=0; i<100000; i++) + for (int i=0; i<1000000; i++) fuzzer.fuzzPeeps(i); assertTrue(fuzzer.noExceptions()); } + + @Test + @Ignore + public void fuzzPeepTiming() { + var fuzzer = new Fuzzer(); + int max_nid=0; + for (int i=0; i<1000000; i++) + max_nid = fuzzer.fuzzPeepTiming(i, max_nid); + } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index ef73fa4b..c3444093 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.GraphEvaluator; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import java.util.ArrayList; @@ -13,8 +15,8 @@ import java.util.function.Consumer; * This will generate a script similar to how the parser parses it but instead of parsing it will * randomly choose a variation the parser would parse and generate it. * These scripts are the parsed by the parser and all exceptions are caught and filtered - * to only show one occurrence of one problem. Generated graphs are evaluated - * to detect compiler/evaluator failures; this chapter has no differential oracle. + * to only show one occurrence of one problem. This includes script which generate different + * results when graphs optimized with different worklist seeds are executed. * To aid debugging scripts that cause errors are then reduced by applying rules and checking * that the same issue persists. */ @@ -49,17 +51,49 @@ public class Fuzzer { System.out.flush(); } - /** Compile and evaluate generated programs with normal peepholes. */ + /** + * Check that two graphs result in the same output when supplied with a value + * @param stop1 Stop node of the first graph + * @param stop2 Stop node of the second graph + * @param in The input value to both graphs to test for an equal output + */ + private static void checkGraphs(StopNode stop1, StopNode stop2, long in) { + var e1 = GraphEvaluator.evaluateWithResult(stop1, in, EVAL_TIMEOUT); + var e2 = GraphEvaluator.evaluateWithResult(stop2, in, EVAL_TIMEOUT); + if (e1.type() == GraphEvaluator.ResultType.TIMEOUT || e2.type() == GraphEvaluator.ResultType.TIMEOUT) return; + if (e1.type() != e2.type()) + throw new RuntimeException("Different calculations types " + e1.type() + " vs " + e2.type()); + if (e1.value() != e2.value()) + throw new RuntimeException("Different calculations values " + e1.value() + " vs " + e2.value()); + } + + /** + * Run checks for script. Compile the script with two different optimizer worklist seeds. + * Check that exceptions raised in the parser by both methods are the same and only happens if the script may be invalid. + * If the script was successfully parsed check that both version behave the same. + * @param script The script to test + * @param valid If the script is definitely valid. If not some exceptions may be suppressed. + */ private static void runCheck(String script, boolean valid) { - StopNode stop; + StopNode stop1; try { - stop = FuzzerUtils.parse(script); - } catch (RuntimeException e) { - if (!valid || e.getClass() == RuntimeException.class) return; - throw e; + stop1 = FuzzerUtils.parse(script, 123); + } catch (RuntimeException e1) { + try { + FuzzerUtils.parse(script, 456); + } catch (RuntimeException e2) { + if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) { + if (!valid || e1.getClass() == RuntimeException.class) return; + } else { + e1.addSuppressed(e2); + } + } + throw e1; } - for (int input : new int[] {0, 1, 10}) - GraphEvaluator.evaluateWithResult(stop, input, EVAL_TIMEOUT); + var stop2 = FuzzerUtils.parse(script, 456); + checkGraphs(stop1, stop2, 0); + checkGraphs(stop1, stop2, 1); + checkGraphs(stop1, stop2, 10); } /** @@ -76,6 +110,45 @@ public class Fuzzer { } /** + * Run one test with the given seed, and check for peephole counts. + * @param seed The seed to use for generating this test case + */ + public int fuzzPeepTiming(long seed, int max_nids) { + var rand = new Random(seed); + var sb = new StringBuilder(); + new ScriptGenerator(rand, sb, true).genProgram(); + try { + var parser = new Parser(sb.toString()); + + var stop = parser.parse(); + int parse_peeps= Node.ITER_CNT; + int parse_nops = Node.ITER_NOP_CNT; + double parse_nop_ratio = (double)parse_nops/parse_peeps; + int nids = Node.UID(); + if( nids <= max_nids ) return max_nids; + + double parse_peeps_per_node = (double)parse_peeps/nids; + + stop.iterate(); + int iter_peeps= Node.ITER_CNT; + int iter_nops = Node.ITER_NOP_CNT; + double iter_nop_ratio = (double)iter_nops/iter_peeps; + double iter_peeps_per_node = (double)iter_peeps/nids; + + System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n", + seed, + parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node, + iter_peeps , iter_nops, iter_nop_ratio, iter_peeps_per_node); + return nids; + } catch (Throwable e) { + // ignore exceptions, let the normal fullPeeps catch and reduce, + // we're interested in valid program optimizations + } + return max_nids; + } + + + /** * Run one test with the given seed. * @param seed The seed to use for generating this test case */ @@ -86,6 +159,7 @@ public class Fuzzer { check(sb.toString(), valid); } + /** * Check that no exceptions happened. * @return true if no exception happened diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index 0e83861d..6488297b 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,15 +1,81 @@ package com.seaofnodes.simple.fuzzer; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; +import java.io.OutputStream; +import java.io.PrintStream; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.reflect.Field; +import java.util.BitSet; + /** * Some utilities for the fuzzer. */ class FuzzerUtils { /** + * Get the value of a private field + */ + @SuppressWarnings("unchecked") + public static <T> T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException { + return (T) (obj instanceof Class<?> clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj)); + } + + /** + * Get access to a private field + */ + public static Field getField(Class<?> clz, String name) throws NoSuchFieldException { + var field = clz.getDeclaredField(name); + try { + field.setAccessible(true); + } catch (Throwable e) { + // Intentionally left empty + } + return field; + } + + /** + * Try to rethrow an exception or create a runtime exception and throw it. + */ + public static RuntimeException rethrow(Throwable e) { + if (e instanceof RuntimeException re) return re; + if (e instanceof Error er) throw er; + return new RuntimeException(e); + } + + /** + * Copy of Node.WVISIST + * Used to clear as exceptions might happen in the walk and left this bitset not cleared + */ + private static final BitSet NodeWalkVisit; + private static final java.util.Random WorkRandom; + + /** + * Write access to Iterate.MID_ASSERT + * Exception could happen mid assert and left this at true. Used to reset to false prior to parsing. + */ + private static final MethodHandle set_MID_ASSERT; + + /** + * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing. + */ + public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream()); + + static { + try { + NodeWalkVisit = getFieldValue(Node.class, "WVISIT"); + WorkRandom = getFieldValue(getFieldValue(IterPeeps.class, "WORK"), "_R"); + set_MID_ASSERT = MethodHandles.lookup().unreflectSetter(getField( IterPeeps.class, "MID_ASSERT")); + } catch (Exception e) { + throw new ExceptionInInitializerError(e); + } + } + + /** * Check that eiter one of the objects is null or that both are equal. */ private static boolean equalOrNull(Object a, Object b) { @@ -47,11 +113,28 @@ class FuzzerUtils { } /** - * Parse script with normal peephole optimization + * Parse and optimize using the given worklist seed */ - public static StopNode parse(String script) { - var parser = new Parser(script); - return parser.parse(); + public static StopNode parse(String script, long workListSeed) { + var err = System.err; + var out = System.out; + try { + System.setErr(NULL_PRINT_STREAM); + System.setOut(NULL_PRINT_STREAM); + try { + set_MID_ASSERT.invokeExact(false); + } catch (Throwable e) { + throw rethrow(e); + } + var parser = new Parser(script); + WorkRandom.setSeed(workListSeed); + var stop = parser.parse(); + return stop.iterate(); + } finally { + NodeWalkVisit.clear(); + System.setErr(err); + System.setOut(out); + } } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java index b7fc18ec..2ef0a3fd 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java @@ -32,8 +32,8 @@ public class Reducer { new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"), new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"), new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"), - new Replace(Pattern.compile("\\b\\w+\\b"), "1"), new Replace(Pattern.compile("\\b\\w+\\b"), "0"), + new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"), new Replace(Pattern.compile("\\d+\\+"), ""), new Replace(Pattern.compile("\\+\\d+"), ""), new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 148c2319..ad98f7e2 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -16,20 +16,6 @@ import java.util.Random; public class ScriptGenerator { /** - * Get the list of keywords from the parser. - */ - @SuppressWarnings("unchecked") - private static HashSet<String> getKeywords() { - try { - var field = Parser.class.getDeclaredField("KEYWORDS"); - field.setAccessible(true); - return (HashSet<String>) field.get(new Parser("")); - } catch (Throwable e) { - throw new ExceptionInInitializerError(e); - } - } - - /** * Number of spaces per indentation */ private static final int INDENTATION = 4; @@ -40,7 +26,15 @@ public class ScriptGenerator { /** * List of keywords not valid for identifiers. */ - private static final HashSet<String> KEYWORDS = getKeywords(); + private static final HashSet<String> KEYWORDS; + + static { + try { + KEYWORDS = FuzzerUtils.getFieldValue(new Parser(""), "KEYWORDS"); + } catch (Throwable e) { + throw new ExceptionInInitializerError(e); + } + } /** * Flag for a statement that it does not pass on control flow to the next statement. @@ -83,11 +77,11 @@ public class ScriptGenerator { /** * The depth of blocks allowed. */ - private int depth = 7; + private int depth = 20; /** * The depth of expressions allowed. */ - private int exprDepth = 3; + private int exprDepth = 30; /** * Current variables in scope. */ @@ -141,7 +135,7 @@ public class ScriptGenerator { * @return The random name generated */ private StringBuilder getRandomName() { - int len = random.nextInt(10) + 1; + int len = random.nextInt(30) + 1; StringBuilder sb = new StringBuilder(len); sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10))); for (int i=1; i<len; i++) @@ -203,7 +197,7 @@ public class ScriptGenerator { * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated */ public int genStatements() { - var num = random.nextInt(10); + var num = random.nextInt(10); // (30); for (int i=0; i<num; i++) { printIndentation(); var stop = genStatement(); |
