diff options
| author | Cliff Click <cliffc@acm.org> | 2023-12-03 23:23:04 +0000 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-04-24 14:38:36 -0700 |
| commit | f9353c3765efd4c0e862b35c7beada89799e16f7 (patch) | |
| tree | 59c8f1bf75c2f62f2207c722be9f7157f84036b7 | |
| parent | 277f7510ceced76f6e5fc2d7d2331c6842a54d7b (diff) | |
| download | Simple-f9353c3765efd4c0e862b35c7beada89799e16f7.tar.gz Simple-f9353c3765efd4c0e862b35c7beada89799e16f7.zip | |
Chapter 8: Lazy Phis, Break, Continue, and Evaluator
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
33 files changed, 3193 insertions, 64 deletions
@@ -36,7 +36,7 @@ main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java) test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) -test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(test_javas)) +test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) classes = $(main_classes) $(test_classes) # All the libraries libs = $(wildcard lib/*jar) @@ -49,7 +49,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. * [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: Looping constructs continued, lazy phi creation, `break` and `continue` statements. +* [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 10: User defined Struct types. Memory effects: general memory edges in SSA. Equivalence class aliasing. Null pointer diff --git a/docs/chapter08/08-grammar.md b/docs/chapter08/08-grammar.md new file mode 100644 index 00000000..4c61bfd7 --- /dev/null +++ b/docs/chapter08/08-grammar.md @@ -0,0 +1,98 @@ +# Grammar for Chapter 8 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + | metaStatement + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter08/08-graph1.gv b/docs/chapter08/08-graph1.gv new file mode 100644 index 00000000..604ee0fe --- /dev/null +++ b/docs/chapter08/08-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +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" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + 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_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ 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_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ 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>> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg35 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Region39 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return40 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;Phi_arg35;} + { rank=same; Region39;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return40[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region39[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If11:p1[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Phi_arg35 -> Region34 [style=dotted taillabel=0]; + Phi_arg35 -> Phi_arg8[taillabel=1]; + Phi_arg35 -> Add16[taillabel=2 constraint=false]; + Region39 -> If19:p0[taillabel=1 color=red]; + Region39 -> If28:p1[taillabel=2 color=red]; + Return40 -> Region34[taillabel=0 color=red]; + Return40 -> Phi_arg35[taillabel=1]; +} diff --git a/docs/chapter08/08-graph1.svg b/docs/chapter08/08-graph1.svg new file mode 100644 index 00000000..0f23a746 --- /dev/null +++ b/docs/chapter08/08-graph1.svg @@ -0,0 +1,359 @@ +<?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="334pt" height="764pt" + viewBox="0.00 0.00 334.00 764.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 760)"> +<title>chapter08</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-760 330,-760 330,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-748 318,-748 318,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="80,-711 80,-736 161,-736 161,-711 80,-711"/> +<polygon fill="none" stroke="black" points="80,-711 80,-736 161,-736 161,-711 80,-711"/> +<text text-anchor="start" x="102" y="-719.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="80,-680 80,-711 161,-711 161,-680 80,-680"/> +<polygon fill="yellow" stroke="transparent" points="85,-685 85,-706 125,-706 125,-685 85,-685"/> +<polygon fill="none" stroke="black" points="85,-685 85,-706 125,-706 125,-685 85,-685"/> +<text text-anchor="start" x="88" y="-691.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="125,-685 125,-706 156,-706 156,-685 125,-685"/> +<text text-anchor="start" x="128" y="-691.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="130,-52 76,-52 76,-16 130,-16 130,-52"/> +<text text-anchor="middle" x="103" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return40 --> +<g id="node19" class="node"> +<title>Return40</title> +<polygon fill="yellow" stroke="black" points="136,-124 70,-124 70,-88 136,-88 136,-124"/> +<text text-anchor="middle" x="103" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return40 --> +<g id="edge1" class="edge"> +<title>Stop3->Return40</title> +<path fill="none" stroke="red" d="M103,-52.3C103,-60.02 103,-69.29 103,-77.89"/> +<polygon fill="red" stroke="red" points="99.5,-77.9 103,-87.9 106.5,-77.9 99.5,-77.9"/> +<text text-anchor="middle" x="100" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop6 --> +<g id="node3" class="node"> +<title>Loop6</title> +<polygon fill="yellow" stroke="black" points="70,-640 16,-640 16,-604 70,-604 70,-640"/> +<text text-anchor="middle" x="43" y="-618.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop6->Start2 --> +<g id="edge2" class="edge"> +<title>Loop6->Start2:p0</title> +<path fill="none" stroke="red" d="M45.16,-640.06C48.35,-658.19 56.02,-685.28 73.77,-692.93"/> +<polygon fill="red" stroke="red" points="73.5,-696.44 84,-695 74.89,-689.58 73.5,-696.44"/> +<text text-anchor="middle" x="42.16" y="-642.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region39 --> +<g id="node18" class="node"> +<title>Region39</title> +<polygon fill="yellow" stroke="black" points="268,-196 202,-196 202,-160 268,-160 268,-196"/> +<text text-anchor="middle" x="235" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Loop6->Region39 --> +<g id="edge3" class="edge"> +<title>Loop6->Region39</title> +<path fill="none" stroke="red" d="M34.42,-603.81C18.87,-570.32 -10.82,-494.13 7,-432 35.9,-331.24 54.86,-302.97 132,-232 141.73,-223.05 168.66,-209.3 192.54,-198.05"/> +<polygon fill="red" stroke="red" points="194.25,-201.11 201.84,-193.72 191.3,-194.77 194.25,-201.11"/> +<text text-anchor="middle" x="31.42" y="-597.41" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg8 --> +<g id="node4" class="node"> +<title>Phi_arg8</title> +<ellipse fill="lightyellow" stroke="black" cx="197" cy="-622" rx="37.09" ry="18"/> +<text text-anchor="middle" x="197" y="-618.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg8->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg8->Start2:p1</title> +<path fill="none" stroke="black" d="M195.04,-640.06C192.05,-658.19 184.71,-685.28 167.15,-692.93"/> +<polygon fill="black" stroke="black" points="166.1,-689.57 157,-695 167.5,-696.43 166.1,-689.57"/> +<text text-anchor="middle" x="192.04" y="-642.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8->Loop6 --> +<g id="edge4" class="edge"> +<title>Phi_arg8->Loop6</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M178.53,-606.01C168.46,-598.34 155.34,-589.98 142,-586 119,-579.14 110.65,-578.06 88,-586 80.86,-588.5 74.01,-592.67 67.91,-597.3"/> +<polygon fill="black" stroke="black" points="65.55,-594.71 60.08,-603.78 70.01,-600.1 65.55,-594.71"/> +<text text-anchor="middle" x="175.53" y="-599.61" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add16 --> +<g id="node9" class="node"> +<title>Add16</title> +<ellipse fill="none" stroke="black" cx="197" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="197" y="-546.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Con_9 --> +<g id="node5" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="115" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-618.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="99" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="99" y="-546.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg8 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg8</title> +<path fill="none" stroke="black" d="M116.97,-563.84C131.47,-574.19 152.11,-588.94 168.8,-600.86"/> +<polygon fill="black" stroke="black" points="166.94,-603.83 177.12,-606.8 171.01,-598.14 166.94,-603.83"/> +<text text-anchor="middle" x="113.97" y="-566.44" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT10->Con_9 --> +<g id="edge8" class="edge"> +<title>LT10->Con_9</title> +<path fill="none" stroke="black" d="M102.87,-567.95C104.65,-575.74 106.81,-585.18 108.81,-593.92"/> +<polygon fill="black" stroke="black" points="105.41,-594.76 111.05,-603.72 112.24,-593.2 105.41,-594.76"/> +<text text-anchor="middle" x="99.87" y="-570.55" 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="24,-467 24,-492 118,-492 118,-467 24,-467"/> +<polygon fill="none" stroke="black" points="24,-467 24,-492 118,-492 118,-467 24,-467"/> +<text text-anchor="start" x="65.5" y="-475.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-436 24,-467 118,-467 118,-436 24,-436"/> +<polygon fill="yellow" stroke="transparent" points="29,-441 29,-462 69,-462 69,-441 29,-441"/> +<polygon fill="none" stroke="black" points="29,-441 29,-462 69,-462 69,-441 29,-441"/> +<text text-anchor="start" x="32" y="-447.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-441 69,-462 113,-462 113,-441 69,-441"/> +<polygon fill="none" stroke="black" points="69,-441 69,-462 113,-462 113,-441 69,-441"/> +<text text-anchor="start" x="72" y="-447.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Loop6 --> +<g id="edge9" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M65.4,-496.19C60.27,-524.77 52.76,-566.64 47.87,-593.86"/> +<polygon fill="red" stroke="red" points="44.4,-593.4 46.08,-603.86 51.29,-594.63 44.4,-593.4"/> +<text text-anchor="middle" x="62.4" y="-498.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT10 --> +<g id="edge10" class="edge"> +<title>If11->LT10</title> +<path fill="none" stroke="black" d="M81.43,-496.28C84.3,-504.9 87.39,-514.17 90.16,-522.49"/> +<polygon fill="black" stroke="black" points="86.87,-523.69 93.36,-532.07 93.51,-521.48 86.87,-523.69"/> +<text text-anchor="middle" x="78.43" y="-498.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node8" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="279" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="279" y="-618.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add16->Phi_arg8 --> +<g id="edge11" class="edge"> +<title>Add16->Phi_arg8</title> +<path fill="none" stroke="black" d="M197,-578.33C197,-583.31 197,-588.51 197,-593.49"/> +<polygon fill="black" stroke="black" points="200.5,-578.3 197,-568.3 193.5,-578.3 200.5,-578.3"/> +<polygon fill="black" stroke="black" points="193.5,-593.9 197,-603.9 200.5,-593.9 193.5,-593.9"/> +<text text-anchor="middle" x="194" y="-570.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add16->Con_15 --> +<g id="edge12" class="edge"> +<title>Add16->Con_15</title> +<path fill="none" stroke="black" d="M213.2,-564.83C225.18,-575.06 241.69,-589.15 255.18,-600.66"/> +<polygon fill="black" stroke="black" points="253.23,-603.61 263.11,-607.44 257.78,-598.28 253.23,-603.61"/> +<text text-anchor="middle" x="210.2" y="-567.43" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_17 --> +<g id="node10" class="node"> +<title>Con_17</title> +<ellipse fill="none" stroke="black" cx="269" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="269" y="-546.3" font-family="Times,serif" font-size="14.00">5</text> +</g> +<!-- EQ18 --> +<g id="node11" class="node"> +<title>EQ18</title> +<ellipse fill="none" stroke="black" cx="211" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="211" y="-460.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ18->Add16 --> +<g id="edge13" class="edge"> +<title>EQ18->Add16</title> +<path fill="none" stroke="black" d="M208.17,-482C206.25,-493.5 203.68,-508.93 201.49,-522.08"/> +<polygon fill="black" stroke="black" points="198.02,-521.59 199.83,-532.03 204.93,-522.74 198.02,-521.59"/> +<text text-anchor="middle" x="205.17" y="-484.6" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ18->Con_17 --> +<g id="edge14" class="edge"> +<title>EQ18->Con_17</title> +<path fill="none" stroke="black" d="M221.91,-480.8C230.5,-493.24 242.61,-510.78 252.4,-524.95"/> +<polygon fill="black" stroke="black" points="249.58,-527.03 258.14,-533.27 255.34,-523.05 249.58,-527.03"/> +<text text-anchor="middle" x="218.91" y="-483.4" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If19 --> +<g id="node12" class="node"> +<title>If19</title> +<polygon fill="yellow" stroke="transparent" points="116,-367 116,-392 210,-392 210,-367 116,-367"/> +<polygon fill="none" stroke="black" points="116,-367 116,-392 210,-392 210,-367 116,-367"/> +<text text-anchor="start" x="157.5" y="-375.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="116,-336 116,-367 210,-367 210,-336 116,-336"/> +<polygon fill="yellow" stroke="transparent" points="121,-341 121,-362 161,-362 161,-341 121,-341"/> +<polygon fill="none" stroke="black" points="121,-341 121,-362 161,-362 161,-341 121,-341"/> +<text text-anchor="start" x="124" y="-347.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="161,-341 161,-362 205,-362 205,-341 161,-341"/> +<polygon fill="none" stroke="black" points="161,-341 161,-362 205,-362 205,-341 161,-341"/> +<text text-anchor="start" x="164" y="-347.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If19->If11 --> +<g id="edge15" class="edge"> +<title>If19->If11:p0</title> +<path fill="none" stroke="red" d="M107.67,-379.11C81.91,-388.94 55.7,-404.9 50.1,-429.95"/> +<polygon fill="red" stroke="red" points="46.61,-429.68 49,-440 53.56,-430.44 46.61,-429.68"/> +<text text-anchor="middle" x="104.67" y="-372.71" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If19->EQ18 --> +<g id="edge16" class="edge"> +<title>If19->EQ18</title> +<path fill="none" stroke="black" d="M178.19,-396.01C184.75,-409.41 192.34,-424.91 198.57,-437.61"/> +<polygon fill="black" stroke="black" points="195.48,-439.27 203.02,-446.71 201.76,-436.19 195.48,-439.27"/> +<text text-anchor="middle" x="175.19" y="-398.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_26 --> +<g id="node13" class="node"> +<title>Con_26</title> +<ellipse fill="none" stroke="black" cx="283" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="283" y="-460.3" font-family="Times,serif" font-size="14.00">6</text> +</g> +<!-- EQ27 --> +<g id="node14" class="node"> +<title>EQ27</title> +<ellipse fill="none" stroke="black" cx="263" cy="-364" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-360.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ27->Add16 --> +<g id="edge17" class="edge"> +<title>EQ27->Add16</title> +<path fill="none" stroke="black" d="M247.53,-378.95C241.28,-384.42 233.92,-390.65 227,-396 204.76,-413.19 191.76,-409.43 175,-432 166.37,-443.62 168.75,-449.02 165,-463"/> +<path fill="none" stroke="black" d="M165,-465C159.41,-485.86 169.21,-508.71 179.4,-525.31"/> +<polygon fill="black" stroke="black" points="176.59,-527.4 185,-533.83 182.43,-523.55 176.59,-527.4"/> +<text text-anchor="middle" x="244.53" y="-381.55" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ27->Con_26 --> +<g id="edge18" class="edge"> +<title>EQ27->Con_26</title> +<path fill="none" stroke="black" d="M266.48,-382.07C269.52,-396.97 273.99,-418.83 277.51,-436.08"/> +<polygon fill="black" stroke="black" points="274.13,-437.03 279.56,-446.13 280.99,-435.63 274.13,-437.03"/> +<text text-anchor="middle" x="263.48" y="-384.67" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If28 --> +<g id="node15" class="node"> +<title>If28</title> +<polygon fill="yellow" stroke="transparent" points="168,-267 168,-292 262,-292 262,-267 168,-267"/> +<polygon fill="none" stroke="black" points="168,-267 168,-292 262,-292 262,-267 168,-267"/> +<text text-anchor="start" x="209.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="168,-236 168,-267 262,-267 262,-236 168,-236"/> +<polygon fill="yellow" stroke="transparent" points="173,-241 173,-262 213,-262 213,-241 173,-241"/> +<polygon fill="none" stroke="black" points="173,-241 173,-262 213,-262 213,-241 173,-241"/> +<text text-anchor="start" x="176" y="-247.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="213,-241 213,-262 257,-262 257,-241 213,-241"/> +<polygon fill="none" stroke="black" points="213,-241 213,-262 257,-262 257,-241 213,-241"/> +<text text-anchor="start" x="216" y="-247.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If28->If19 --> +<g id="edge19" class="edge"> +<title>If28->If19:p1</title> +<path fill="none" stroke="red" d="M195.1,-296.25C190.01,-306.42 185.49,-318.16 183.75,-330.03"/> +<polygon fill="red" stroke="red" points="180.26,-329.76 183,-340 187.24,-330.29 180.26,-329.76"/> +<text text-anchor="middle" x="192.1" y="-298.85" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If28->EQ27 --> +<g id="edge20" class="edge"> +<title>If28->EQ27</title> +<path fill="none" stroke="black" d="M230.19,-296.01C236.75,-309.41 244.34,-324.91 250.57,-337.61"/> +<polygon fill="black" stroke="black" points="247.48,-339.27 255.02,-346.71 253.76,-336.19 247.48,-339.27"/> +<text text-anchor="middle" x="227.19" y="-298.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34 --> +<g id="node16" class="node"> +<title>Region34</title> +<polygon fill="yellow" stroke="black" points="92,-196 26,-196 26,-160 92,-160 92,-196"/> +<text text-anchor="middle" x="59" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region34->If11 --> +<g id="edge21" class="edge"> +<title>Region34->If11:p1</title> +<path fill="none" stroke="red" d="M60.73,-196.19C64.47,-232.93 73.83,-321.8 84,-396 86.16,-411.79 89.38,-417.84 90.55,-429.91"/> +<polygon fill="red" stroke="red" points="87.06,-430.17 91,-440 94.05,-429.85 87.06,-430.17"/> +<text text-anchor="middle" x="57.73" y="-198.79" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34->If28 --> +<g id="edge22" class="edge"> +<title>Region34->If28:p0</title> +<path fill="none" stroke="red" d="M73.55,-196.06C91.73,-215.52 124.92,-245.31 161.58,-250.28"/> +<polygon fill="red" stroke="red" points="161.78,-253.81 172,-251 162.26,-246.82 161.78,-253.81"/> +<text text-anchor="middle" x="70.55" y="-198.66" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg35 --> +<g id="node17" class="node"> +<title>Phi_arg35</title> +<ellipse fill="lightyellow" stroke="black" cx="147" cy="-178" rx="37.09" ry="18"/> +<text text-anchor="middle" x="147" y="-174.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg35->Phi_arg8 --> +<g id="edge24" class="edge"> +<title>Phi_arg35->Phi_arg8</title> +<path fill="none" stroke="black" d="M136.87,-195.37C115.38,-232.36 69.47,-324.71 99,-396 107.66,-416.91 124.41,-412 135,-432 163.81,-486.38 137.45,-511.15 161,-568 165.15,-578.02 171.36,-588.09 177.46,-596.73"/> +<polygon fill="black" stroke="black" points="174.69,-598.87 183.44,-604.83 180.32,-594.71 174.69,-598.87"/> +<text text-anchor="middle" x="133.87" y="-197.97" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg35->Add16 --> +<g id="edge25" class="edge"> +<title>Phi_arg35->Add16</title> +<path fill="none" stroke="black" d="M175.64,-189.71C213.39,-203.94 275.5,-227.79 279,-232 307.96,-266.86 294.53,-286.9 299,-332 301.8,-360.31 316.08,-373.26 299,-396 264.54,-441.89 216.17,-392.02 175,-432 164.61,-442.08 168.75,-449.02 165,-463"/> +<text text-anchor="middle" x="172.64" y="-192.31" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg35->Region34 --> +<g id="edge23" class="edge"> +<title>Phi_arg35->Region34</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M109.85,-178C107.39,-178 104.93,-178 102.47,-178"/> +<polygon fill="black" stroke="black" points="102.34,-174.5 92.34,-178 102.34,-181.5 102.34,-174.5"/> +<text text-anchor="middle" x="106.85" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Region39->If19 --> +<g id="edge26" class="edge"> +<title>Region39->If19:p0</title> +<path fill="none" stroke="red" d="M201.88,-195.94C181.14,-207.25 157.22,-221.86 151,-232 127.62,-270.12 139.01,-288.97 140.78,-329.99"/> +<polygon fill="red" stroke="red" points="137.28,-330.08 141,-340 144.28,-329.93 137.28,-330.08"/> +<text text-anchor="middle" x="198.88" y="-189.54" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region39->If28 --> +<g id="edge27" class="edge"> +<title>Region39->If28:p1</title> +<path fill="none" stroke="red" d="M235,-196.09C235,-205.55 235,-217.77 235,-229.69"/> +<polygon fill="red" stroke="red" points="231.5,-230 235,-240 238.5,-230 231.5,-230"/> +<text text-anchor="middle" x="232" y="-198.69" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return40->Region34 --> +<g id="edge28" class="edge"> +<title>Return40->Region34</title> +<path fill="none" stroke="red" d="M92.12,-124.3C87.01,-132.44 80.8,-142.31 75.16,-151.3"/> +<polygon fill="red" stroke="red" points="72.11,-149.57 69.75,-159.9 78.04,-153.29 72.11,-149.57"/> +<text text-anchor="middle" x="89.12" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return40->Phi_arg35 --> +<g id="edge29" class="edge"> +<title>Return40->Phi_arg35</title> +<path fill="none" stroke="black" d="M113.88,-124.3C119.07,-132.56 125.38,-142.61 131.1,-151.7"/> +<polygon fill="black" stroke="black" points="128.27,-153.77 136.55,-160.38 134.19,-150.05 128.27,-153.77"/> +<text text-anchor="middle" x="110.88" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter08/08-graph2.gv b/docs/chapter08/08-graph2.gv new file mode 100644 index 00000000..2fa82523 --- /dev/null +++ b/docs/chapter08/08-graph2.gv @@ -0,0 +1,103 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +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" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + 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_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ 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_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ 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>> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Region38 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;} + { rank=same; Region38;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region38[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If19:p0[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Region38 -> Region34[taillabel=1 color=red]; + Region38 -> If28:p1[taillabel=2 color=red]; + Return39 -> If11:p1[taillabel=0 color=red]; + Return39 -> Phi_arg8[taillabel=1]; +} diff --git a/docs/chapter08/08-graph2.svg b/docs/chapter08/08-graph2.svg new file mode 100644 index 00000000..1f497470 --- /dev/null +++ b/docs/chapter08/08-graph2.svg @@ -0,0 +1,332 @@ +<?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="334pt" height="692pt" + viewBox="0.00 0.00 334.00 692.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 688)"> +<title>chapter08</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-688 330,-688 330,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-676 318,-676 318,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="81,-639 81,-664 162,-664 162,-639 81,-639"/> +<polygon fill="none" stroke="black" points="81,-639 81,-664 162,-664 162,-639 81,-639"/> +<text text-anchor="start" x="103" y="-647.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="81,-608 81,-639 162,-639 162,-608 81,-608"/> +<polygon fill="yellow" stroke="transparent" points="86,-613 86,-634 126,-634 126,-613 86,-613"/> +<polygon fill="none" stroke="black" points="86,-613 86,-634 126,-634 126,-613 86,-613"/> +<text text-anchor="start" x="89" y="-619.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="126,-613 126,-634 157,-634 157,-613 126,-613"/> +<text text-anchor="start" x="129" y="-619.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="174,-210 120,-210 120,-174 174,-174 174,-210"/> +<text text-anchor="middle" x="147" y="-188.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return39 --> +<g id="node18" class="node"> +<title>Return39</title> +<polygon fill="yellow" stroke="black" points="228,-310 162,-310 162,-274 228,-274 228,-310"/> +<text text-anchor="middle" x="195" y="-288.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return39 --> +<g id="edge1" class="edge"> +<title>Stop3->Return39</title> +<path fill="none" stroke="red" d="M155.36,-210.07C162.75,-225.15 173.64,-247.39 182.14,-264.74"/> +<polygon fill="red" stroke="red" points="179.03,-266.36 186.57,-273.8 185.32,-263.28 179.03,-266.36"/> +<text text-anchor="middle" x="152.36" y="-212.67" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop6 --> +<g id="node3" class="node"> +<title>Loop6</title> +<polygon fill="yellow" stroke="black" points="72,-568 18,-568 18,-532 72,-532 72,-568"/> +<text text-anchor="middle" x="45" y="-546.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop6->Start2 --> +<g id="edge2" class="edge"> +<title>Loop6->Start2:p0</title> +<path fill="none" stroke="red" d="M46.96,-568.06C49.95,-586.19 57.29,-613.28 74.85,-620.93"/> +<polygon fill="red" stroke="red" points="74.5,-624.43 85,-623 75.9,-617.57 74.5,-624.43"/> +<text text-anchor="middle" x="43.96" y="-570.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region38 --> +<g id="node17" class="node"> +<title>Region38</title> +<polygon fill="yellow" stroke="black" points="274,-52 208,-52 208,-16 274,-16 274,-52"/> +<text text-anchor="middle" x="241" y="-30.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Loop6->Region38 --> +<g id="edge3" class="edge"> +<title>Loop6->Region38</title> +<path fill="none" stroke="red" d="M38.06,-531.98C28.81,-508.26 12.9,-463.71 7,-424 -3.78,-351.47 4.18,-330.31 25,-260 38.69,-213.78 36.96,-197.7 67,-160 103.26,-114.48 160.19,-77.91 198.98,-56.36"/> +<polygon fill="red" stroke="red" points="200.84,-59.33 207.94,-51.46 197.49,-53.18 200.84,-59.33"/> +<text text-anchor="middle" x="35.06" y="-525.58" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg8 --> +<g id="node4" class="node"> +<title>Phi_arg8</title> +<ellipse fill="lightyellow" stroke="black" cx="199" cy="-550" rx="37.09" ry="18"/> +<text text-anchor="middle" x="199" y="-546.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg8->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg8->Start2:p1</title> +<path fill="none" stroke="black" d="M196.84,-568.06C193.65,-586.19 185.98,-613.28 168.23,-620.93"/> +<polygon fill="black" stroke="black" points="167.11,-617.58 158,-623 168.5,-624.44 167.11,-617.58"/> +<text text-anchor="middle" x="193.84" y="-570.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8->Loop6 --> +<g id="edge4" class="edge"> +<title>Phi_arg8->Loop6</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M180.53,-534.01C170.46,-526.34 157.34,-517.98 144,-514 121,-507.14 112.65,-506.06 90,-514 82.86,-516.5 76.01,-520.67 69.91,-525.3"/> +<polygon fill="black" stroke="black" points="67.55,-522.71 62.08,-531.78 72.01,-528.1 67.55,-522.71"/> +<text text-anchor="middle" x="177.53" y="-527.61" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add16 --> +<g id="node9" class="node"> +<title>Add16</title> +<ellipse fill="none" stroke="black" cx="271" cy="-478" rx="27" ry="18"/> +<text text-anchor="middle" x="271" y="-474.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Con_9 --> +<g id="node5" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="117" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="117" y="-546.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="99" cy="-478" rx="27" ry="18"/> +<text text-anchor="middle" x="99" y="-474.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg8 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg8</title> +<path fill="none" stroke="black" d="M116.88,-491.51C131.61,-501.83 152.8,-516.66 169.97,-528.68"/> +<polygon fill="black" stroke="black" points="168.32,-531.8 178.52,-534.66 172.33,-526.06 168.32,-531.8"/> +<text text-anchor="middle" x="113.88" y="-494.11" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT10->Con_9 --> +<g id="edge8" class="edge"> +<title>LT10->Con_9</title> +<path fill="none" stroke="black" d="M103.36,-495.95C105.39,-503.86 107.86,-513.46 110.14,-522.31"/> +<polygon fill="black" stroke="black" points="106.8,-523.4 112.68,-532.21 113.58,-521.65 106.8,-523.4"/> +<text text-anchor="middle" x="100.36" y="-498.55" 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="24,-395 24,-420 118,-420 118,-395 24,-395"/> +<polygon fill="none" stroke="black" points="24,-395 24,-420 118,-420 118,-395 24,-395"/> +<text text-anchor="start" x="65.5" y="-403.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="24,-364 24,-395 118,-395 118,-364 24,-364"/> +<polygon fill="yellow" stroke="transparent" points="29,-369 29,-390 69,-390 69,-369 29,-369"/> +<polygon fill="none" stroke="black" points="29,-369 29,-390 69,-390 69,-369 29,-369"/> +<text text-anchor="start" x="32" y="-375.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="69,-369 69,-390 113,-390 113,-369 69,-369"/> +<polygon fill="none" stroke="black" points="69,-369 69,-390 113,-390 113,-369 69,-369"/> +<text text-anchor="start" x="72" y="-375.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Loop6 --> +<g id="edge9" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M65.8,-424.19C61.04,-452.77 54.06,-494.64 49.52,-521.86"/> +<polygon fill="red" stroke="red" points="46.05,-521.42 47.86,-531.86 52.95,-522.57 46.05,-521.42"/> +<text text-anchor="middle" x="62.8" y="-426.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT10 --> +<g id="edge10" class="edge"> +<title>If11->LT10</title> +<path fill="none" stroke="black" d="M81.43,-424.28C84.3,-432.9 87.39,-442.17 90.16,-450.49"/> +<polygon fill="black" stroke="black" points="86.87,-451.69 93.36,-460.07 93.51,-449.48 86.87,-451.69"/> +<text text-anchor="middle" x="78.43" y="-426.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node8" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="281" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="281" y="-546.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add16->Phi_arg8 --> +<g id="edge11" class="edge"> +<title>Add16->Phi_arg8</title> +<path fill="none" stroke="black" d="M249.16,-500.23C240.6,-508.56 230.75,-518.13 222.07,-526.57"/> +<polygon fill="black" stroke="black" points="251.7,-502.65 256.43,-493.17 246.82,-497.63 251.7,-502.65"/> +<polygon fill="black" stroke="black" points="219.53,-524.16 214.8,-533.64 224.41,-529.18 219.53,-524.16"/> +<text text-anchor="middle" x="253.43" y="-495.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add16->Con_15 --> +<g id="edge12" class="edge"> +<title>Add16->Con_15</title> +<path fill="none" stroke="black" d="M273.42,-495.95C274.52,-503.65 275.85,-512.97 277.09,-521.64"/> +<polygon fill="black" stroke="black" points="273.65,-522.32 278.53,-531.72 280.58,-521.33 273.65,-522.32"/> +<text text-anchor="middle" x="270.42" y="-498.55" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_17 --> +<g id="node10" class="node"> +<title>Con_17</title> +<ellipse fill="none" stroke="black" cx="171" cy="-478" rx="27" ry="18"/> +<text text-anchor="middle" x="171" y="-474.3" font-family="Times,serif" font-size="14.00">5</text> +</g> +<!-- EQ18 --> +<g id="node11" class="node"> +<title>EQ18</title> +<ellipse fill="none" stroke="black" cx="171" cy="-392" rx="27" ry="18"/> +<text text-anchor="middle" x="171" y="-388.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ18->Add16 --> +<g id="edge13" class="edge"> +<title>EQ18->Add16</title> +<path fill="none" stroke="black" d="M187.07,-406.5C203.23,-420.07 228.34,-441.16 246.89,-456.75"/> +<polygon fill="black" stroke="black" points="244.73,-459.51 254.64,-463.26 249.24,-454.15 244.73,-459.51"/> +<text text-anchor="middle" x="184.07" y="-409.1" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ18->Con_17 --> +<g id="edge14" class="edge"> +<title>EQ18->Con_17</title> +<path fill="none" stroke="black" d="M171,-410.4C171,-421.74 171,-436.77 171,-449.68"/> +<polygon fill="black" stroke="black" points="167.5,-449.9 171,-459.9 174.5,-449.9 167.5,-449.9"/> +<text text-anchor="middle" x="168" y="-413" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If19 --> +<g id="node12" class="node"> +<title>If19</title> +<polygon fill="yellow" stroke="transparent" points="42,-295 42,-320 136,-320 136,-295 42,-295"/> +<polygon fill="none" stroke="black" points="42,-295 42,-320 136,-320 136,-295 42,-295"/> +<text text-anchor="start" x="83.5" y="-303.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="42,-264 42,-295 136,-295 136,-264 42,-264"/> +<polygon fill="yellow" stroke="transparent" points="47,-269 47,-290 87,-290 87,-269 47,-269"/> +<polygon fill="none" stroke="black" points="47,-269 47,-290 87,-290 87,-269 47,-269"/> +<text text-anchor="start" x="50" y="-275.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="87,-269 87,-290 131,-290 131,-269 87,-269"/> +<polygon fill="none" stroke="black" points="87,-269 87,-290 131,-290 131,-269 87,-269"/> +<text text-anchor="start" x="90" y="-275.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If19->If11 --> +<g id="edge15" class="edge"> +<title>If19->If11:p0</title> +<path fill="none" stroke="red" d="M63.67,-324.33C57.47,-334.31 52,-345.89 49.91,-357.87"/> +<polygon fill="red" stroke="red" points="46.41,-357.73 49,-368 53.38,-358.35 46.41,-357.73"/> +<text text-anchor="middle" x="60.67" y="-326.93" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If19->EQ18 --> +<g id="edge16" class="edge"> +<title>If19->EQ18</title> +<path fill="none" stroke="black" d="M114.95,-324.01C126.8,-338.18 140.6,-354.67 151.55,-367.75"/> +<polygon fill="black" stroke="black" points="149.18,-370.37 158.28,-375.8 154.54,-365.88 149.18,-370.37"/> +<text text-anchor="middle" x="111.95" y="-326.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_26 --> +<g id="node13" class="node"> +<title>Con_26</title> +<ellipse fill="none" stroke="black" cx="263" cy="-392" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-388.3" font-family="Times,serif" font-size="14.00">6</text> +</g> +<!-- EQ27 --> +<g id="node14" class="node"> +<title>EQ27</title> +<ellipse fill="none" stroke="black" cx="273" cy="-292" rx="27" ry="18"/> +<text text-anchor="middle" x="273" y="-288.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ27->Add16 --> +<g id="edge17" class="edge"> +<title>EQ27->Add16</title> +<path fill="none" stroke="black" d="M281.29,-309.29C287.55,-322.56 295.62,-341.97 299,-360 304.23,-387.96 305.84,-396.39 299,-424 296.57,-433.79 291.97,-443.77 287.18,-452.38"/> +<polygon fill="black" stroke="black" points="284.09,-450.74 282.02,-461.13 290.12,-454.3 284.09,-450.74"/> +<text text-anchor="middle" x="278.29" y="-311.89" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ27->Con_26 --> +<g id="edge18" class="edge"> +<title>EQ27->Con_26</title> +<path fill="none" stroke="black" d="M271.26,-310.07C269.75,-324.88 267.53,-346.57 265.78,-363.77"/> +<polygon fill="black" stroke="black" points="262.29,-363.49 264.76,-373.8 269.25,-364.2 262.29,-363.49"/> +<text text-anchor="middle" x="268.26" y="-312.67" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If28 --> +<g id="node15" class="node"> +<title>If28</title> +<polygon fill="yellow" stroke="transparent" points="200,-195 200,-220 294,-220 294,-195 200,-195"/> +<polygon fill="none" stroke="black" points="200,-195 200,-220 294,-220 294,-195 200,-195"/> +<text text-anchor="start" x="241.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="200,-164 200,-195 294,-195 294,-164 200,-164"/> +<polygon fill="yellow" stroke="transparent" points="205,-169 205,-190 245,-190 245,-169 205,-169"/> +<polygon fill="none" stroke="black" points="205,-169 205,-190 245,-190 245,-169 205,-169"/> +<text text-anchor="start" x="208" y="-175.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="245,-169 245,-190 289,-190 289,-169 245,-169"/> +<polygon fill="none" stroke="black" points="245,-169 245,-190 289,-190 289,-169 245,-169"/> +<text text-anchor="start" x="248" y="-175.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If28->If19 --> +<g id="edge19" class="edge"> +<title>If28->If19:p1</title> +<path fill="none" stroke="red" d="M200.79,-224.33C185.31,-235.25 168.15,-247.82 153,-260 146.72,-265.05 145.03,-271.43 141.32,-275.36"/> +<polygon fill="red" stroke="red" points="140.04,-272.1 132,-279 142.59,-278.62 140.04,-272.1"/> +<text text-anchor="middle" x="197.79" y="-226.93" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If28->EQ27 --> +<g id="edge20" class="edge"> +<title>If28->EQ27</title> +<path fill="none" stroke="black" d="M255.23,-224.01C258.67,-236.98 262.63,-251.9 265.93,-264.36"/> +<polygon fill="black" stroke="black" points="262.58,-265.39 268.53,-274.15 269.35,-263.59 262.58,-265.39"/> +<text text-anchor="middle" x="252.23" y="-226.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34 --> +<g id="node16" class="node"> +<title>Region34</title> +<polygon fill="yellow" stroke="black" points="248,-124 182,-124 182,-88 248,-88 248,-124"/> +<text text-anchor="middle" x="215" y="-102.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region34->If19 --> +<g id="edge21" class="edge"> +<title>Region34->If19:p0</title> +<path fill="none" stroke="red" d="M181.63,-117.1C159.08,-125.42 130.06,-139.26 111,-160 78.33,-195.56 68.34,-213.61 67.13,-257.83"/> +<polygon fill="red" stroke="red" points="63.63,-257.96 67,-268 70.63,-258.05 63.63,-257.96"/> +<text text-anchor="middle" x="178.63" y="-110.7" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region34->If28 --> +<g id="edge22" class="edge"> +<title>Region34->If28:p0</title> +<path fill="none" stroke="red" d="M219.36,-124.23C221.44,-133.63 223.68,-145.75 224.58,-157.66"/> +<polygon fill="red" stroke="red" points="221.1,-158.15 225,-168 228.09,-157.87 221.1,-158.15"/> +<text text-anchor="middle" x="216.36" y="-126.83" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region38->If28 --> +<g id="edge24" class="edge"> +<title>Region38->If28:p1</title> +<path fill="none" stroke="red" d="M247.09,-52.47C250.45,-62.71 254.45,-75.96 257,-88 263.67,-119.49 266.43,-130.05 266.92,-157.85"/> +<polygon fill="red" stroke="red" points="263.42,-158.03 267,-168 270.42,-157.97 263.42,-158.03"/> +<text text-anchor="middle" x="244.09" y="-55.07" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region38->Region34 --> +<g id="edge23" class="edge"> +<title>Region38->Region34</title> +<path fill="none" stroke="red" d="M234.57,-52.3C231.64,-60.19 228.11,-69.7 224.86,-78.45"/> +<polygon fill="red" stroke="red" points="221.55,-77.3 221.35,-87.9 228.12,-79.74 221.55,-77.3"/> +<text text-anchor="middle" x="231.57" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return39->Phi_arg8 --> +<g id="edge26" class="edge"> +<title>Return39->Phi_arg8</title> +<path fill="none" stroke="black" d="M198.96,-310.24C201.84,-323.7 205.48,-342.93 207,-360 212.35,-420.21 211.52,-435.73 207,-496 206.36,-504.48 205.16,-513.66 203.88,-521.96"/> +<polygon fill="black" stroke="black" points="200.42,-521.45 202.25,-531.89 207.32,-522.59 200.42,-521.45"/> +<text text-anchor="middle" x="195.96" y="-312.84" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return39->If11 --> +<g id="edge25" class="edge"> +<title>Return39->If11:p1</title> +<path fill="none" stroke="red" d="M179.78,-310.4C162.83,-329.64 136.01,-359.63 122.28,-372.63"/> +<polygon fill="red" stroke="red" points="119.79,-370.13 114,-379 124.06,-375.68 119.79,-370.13"/> +<text text-anchor="middle" x="176.78" y="-313" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +</g> +</svg> diff --git a/docs/chapter08/08-graph3.gv b/docs/chapter08/08-graph3.gv new file mode 100644 index 00000000..72ac10a8 --- /dev/null +++ b/docs/chapter08/08-graph3.gv @@ -0,0 +1,111 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +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" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + 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_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ 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>> + ]; + Region25 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg26 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_28 [ label="6" ]; + EQ29 [ label="==" ]; + If30 [ 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>> + ]; + Region36 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg37 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region25;Phi_arg26;} + { rank=same; Region36;Phi_arg37;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> If30:p1[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + Region25 -> If11:p1[taillabel=1 color=red]; + Region25 -> If19:p0[taillabel=2 color=red]; + Phi_arg26 -> Region25 [style=dotted taillabel=0]; + Phi_arg26 -> Phi_arg8[taillabel=1]; + Phi_arg26 -> Add16[taillabel=2 constraint=false]; + EQ29 -> Add16[taillabel=1]; + EQ29 -> Con_28[taillabel=2]; + If30 -> If19:p1[taillabel=0 color=red]; + If30 -> EQ29[taillabel=1]; + Region36 -> Region25[taillabel=1 color=red]; + Region36 -> If30:p0[taillabel=2 color=red]; + Phi_arg37 -> Region36 [style=dotted taillabel=0]; + Phi_arg37 -> Phi_arg26[taillabel=1]; + Phi_arg37 -> Add16[taillabel=2 constraint=false]; + Return39 -> Region36[taillabel=0 color=red]; + Return39 -> Phi_arg37[taillabel=1]; +}
\ No newline at end of file diff --git a/docs/chapter08/08-graph3.svg b/docs/chapter08/08-graph3.svg new file mode 100644 index 00000000..12aafcc5 --- /dev/null +++ b/docs/chapter08/08-graph3.svg @@ -0,0 +1,386 @@ +<?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="396pt" height="764pt" + viewBox="0.00 0.00 395.85 764.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 760)"> +<title>chapter08</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-760 391.85,-760 391.85,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-748 378,-748 378,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="44,-711 44,-736 125,-736 125,-711 44,-711"/> +<polygon fill="none" stroke="black" points="44,-711 44,-736 125,-736 125,-711 44,-711"/> +<text text-anchor="start" x="66" y="-719.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="44,-680 44,-711 125,-711 125,-680 44,-680"/> +<polygon fill="yellow" stroke="transparent" points="49,-685 49,-706 89,-706 89,-685 49,-685"/> +<polygon fill="none" stroke="black" points="49,-685 49,-706 89,-706 89,-685 49,-685"/> +<text text-anchor="start" x="52" y="-691.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="89,-685 89,-706 120,-706 120,-685 89,-685"/> +<text text-anchor="start" x="92" y="-691.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="144,-52 90,-52 90,-16 144,-16 144,-52"/> +<text text-anchor="middle" x="117" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return39 --> +<g id="node20" class="node"> +<title>Return39</title> +<polygon fill="yellow" stroke="black" points="150,-124 84,-124 84,-88 150,-88 150,-124"/> +<text text-anchor="middle" x="117" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return39 --> +<g id="edge1" class="edge"> +<title>Stop3->Return39</title> +<path fill="none" stroke="red" d="M117,-52.3C117,-60.02 117,-69.29 117,-77.89"/> +<polygon fill="red" stroke="red" points="113.5,-77.9 117,-87.9 120.5,-77.9 113.5,-77.9"/> +<text text-anchor="middle" x="114" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Loop6 --> +<g id="node3" class="node"> +<title>Loop6</title> +<polygon fill="yellow" stroke="black" points="70,-640 16,-640 16,-604 70,-604 70,-640"/> +<text text-anchor="middle" x="43" y="-618.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop6->Start2 --> +<g id="edge2" class="edge"> +<title>Loop6->Start2:p0</title> +<path fill="none" stroke="red" d="M54.63,-640.06C60.09,-649.38 65.88,-661.53 68.08,-673.99"/> +<polygon fill="red" stroke="red" points="64.6,-674.36 69,-684 71.57,-673.72 64.6,-674.36"/> +<text text-anchor="middle" x="51.63" y="-642.66" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If30 --> +<g id="node17" class="node"> +<title>If30</title> +<polygon fill="yellow" stroke="transparent" points="220,-267 220,-292 314,-292 314,-267 220,-267"/> +<polygon fill="none" stroke="black" points="220,-267 220,-292 314,-292 314,-267 220,-267"/> +<text text-anchor="start" x="261.5" y="-275.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="220,-236 220,-267 314,-267 314,-236 220,-236"/> +<polygon fill="yellow" stroke="transparent" points="225,-241 225,-262 265,-262 265,-241 225,-241"/> +<polygon fill="none" stroke="black" points="225,-241 225,-262 265,-262 265,-241 225,-241"/> +<text text-anchor="start" x="228" y="-247.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="265,-241 265,-262 309,-262 309,-241 265,-241"/> +<polygon fill="none" stroke="black" points="265,-241 265,-262 309,-262 309,-241 265,-241"/> +<text text-anchor="start" x="268" y="-247.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- Loop6->If30 --> +<g id="edge3" class="edge"> +<title>Loop6->If30:p1</title> +<path fill="none" stroke="red" d="M70.26,-607.38C73.18,-606.15 76.13,-604.99 79,-604 147.07,-580.48 188.31,-621.07 237,-568 257.49,-545.67 264.72,-456.58 247,-432 217.42,-390.95 168.58,-437.05 139,-396 122.37,-372.92 120.93,-353.97 139,-332 191.65,-267.98 269.35,-360.02 322,-296 337.53,-277.12 339.04,-258.53 322,-241 314.29,-233.07 299.85,-228.04 292.15,-231.39"/> +<polygon fill="red" stroke="red" points="289.13,-229.62 287,-240 295.14,-233.22 289.13,-229.62"/> +<text text-anchor="middle" x="73.26" y="-600.98" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg8 --> +<g id="node4" class="node"> +<title>Phi_arg8</title> +<ellipse fill="lightyellow" stroke="black" cx="125" cy="-622" rx="37.09" ry="18"/> +<text text-anchor="middle" x="125" y="-618.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg8->Start2 --> +<g id="edge5" class="edge"> +<title>Phi_arg8->Start2:p1</title> +<path fill="none" stroke="black" d="M116.4,-639.61C112.12,-649.08 107.5,-661.53 105.74,-674.02"/> +<polygon fill="black" stroke="black" points="102.25,-673.77 105,-684 109.23,-674.29 102.25,-673.77"/> +<text text-anchor="middle" x="113.4" y="-642.21" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8->Loop6 --> +<g id="edge4" class="edge"> +<title>Phi_arg8->Loop6</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M87.77,-622C85.3,-622 82.84,-622 80.37,-622"/> +<polygon fill="black" stroke="black" points="80.23,-618.5 70.23,-622 80.23,-625.5 80.23,-618.5"/> +<text text-anchor="middle" x="84.77" y="-615.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add16 --> +<g id="node9" class="node"> +<title>Add16</title> +<ellipse fill="none" stroke="black" cx="293" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="293" y="-546.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Con_9 --> +<g id="node5" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="207" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-618.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="125" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="125" y="-546.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg8 --> +<g id="edge7" class="edge"> +<title>LT10->Phi_arg8</title> +<path fill="none" stroke="black" d="M125,-568.3C125,-576.02 125,-585.29 125,-593.89"/> +<polygon fill="black" stroke="black" points="121.5,-593.9 125,-603.9 128.5,-593.9 121.5,-593.9"/> +<text text-anchor="middle" x="122" y="-570.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT10->Con_9 --> +<g id="edge8" class="edge"> +<title>LT10->Con_9</title> +<path fill="none" stroke="black" d="M141.2,-564.83C153.18,-575.06 169.69,-589.15 183.18,-600.66"/> +<polygon fill="black" stroke="black" points="181.23,-603.61 191.11,-607.44 185.78,-598.28 181.23,-603.61"/> +<text text-anchor="middle" x="138.2" y="-567.43" 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="44,-467 44,-492 138,-492 138,-467 44,-467"/> +<polygon fill="none" stroke="black" points="44,-467 44,-492 138,-492 138,-467 44,-467"/> +<text text-anchor="start" x="85.5" y="-475.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="44,-436 44,-467 138,-467 138,-436 44,-436"/> +<polygon fill="yellow" stroke="transparent" points="49,-441 49,-462 89,-462 89,-441 49,-441"/> +<polygon fill="none" stroke="black" points="49,-441 49,-462 89,-462 89,-441 49,-441"/> +<text text-anchor="start" x="52" y="-447.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="89,-441 89,-462 133,-462 133,-441 89,-441"/> +<polygon fill="none" stroke="black" points="89,-441 89,-462 133,-462 133,-441 89,-441"/> +<text text-anchor="start" x="92" y="-447.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Loop6 --> +<g id="edge9" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M81.4,-496.19C72.57,-524.89 59.61,-567.01 51.24,-594.22"/> +<polygon fill="red" stroke="red" points="47.87,-593.27 48.27,-603.86 54.56,-595.33 47.87,-593.27"/> +<text text-anchor="middle" x="78.4" y="-498.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT10 --> +<g id="edge10" class="edge"> +<title>If11->LT10</title> +<path fill="none" stroke="black" d="M103.66,-496.28C107.24,-505.13 111.1,-514.66 114.54,-523.15"/> +<polygon fill="black" stroke="black" points="111.34,-524.59 118.34,-532.54 117.83,-521.96 111.34,-524.59"/> +<text text-anchor="middle" x="100.66" y="-498.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node8" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="293" cy="-622" rx="27" ry="18"/> +<text text-anchor="middle" x="293" y="-618.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add16->Phi_arg8 --> +<g id="edge11" class="edge"> +<title>Add16->Phi_arg8</title> +<path fill="none" stroke="black" d="M261.07,-564.31C232.75,-576.1 191.39,-593.34 161.72,-605.7"/> +<polygon fill="black" stroke="black" points="262.81,-567.37 270.69,-560.3 260.11,-560.91 262.81,-567.37"/> +<polygon fill="black" stroke="black" points="160.02,-602.62 152.13,-609.69 162.71,-609.08 160.02,-602.62"/> +<text text-anchor="middle" x="267.69" y="-562.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add16->Con_15 --> +<g id="edge12" class="edge"> +<title>Add16->Con_15</title> +<path fill="none" stroke="black" d="M293,-568.3C293,-576.02 293,-585.29 293,-593.89"/> +<polygon fill="black" stroke="black" points="289.5,-593.9 293,-603.9 296.5,-593.9 289.5,-593.9"/> +<text text-anchor="middle" x="290" y="-570.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_17 --> +<g id="node10" class="node"> +<title>Con_17</title> +<ellipse fill="none" stroke="black" cx="201" cy="-550" rx="27" ry="18"/> +<text text-anchor="middle" x="201" y="-546.3" font-family="Times,serif" font-size="14.00">5</text> +</g> +<!-- EQ18 --> +<g id="node11" class="node"> +<title>EQ18</title> +<ellipse fill="none" stroke="black" cx="211" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="211" y="-460.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ18->Add16 --> +<g id="edge13" class="edge"> +<title>EQ18->Add16</title> +<path fill="none" stroke="black" d="M225.28,-479.63C238.1,-492.76 257.09,-512.21 271.7,-527.18"/> +<polygon fill="black" stroke="black" points="269.39,-529.83 278.88,-534.54 274.4,-524.94 269.39,-529.83"/> +<text text-anchor="middle" x="222.28" y="-482.23" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ18->Con_17 --> +<g id="edge14" class="edge"> +<title>EQ18->Con_17</title> +<path fill="none" stroke="black" d="M208.98,-482C207.61,-493.5 205.77,-508.93 204.2,-522.08"/> +<polygon fill="black" stroke="black" points="200.73,-521.68 203.02,-532.03 207.68,-522.51 200.73,-521.68"/> +<text text-anchor="middle" x="205.98" y="-484.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If19 --> +<g id="node12" class="node"> +<title>If19</title> +<polygon fill="yellow" stroke="transparent" points="156,-367 156,-392 250,-392 250,-367 156,-367"/> +<polygon fill="none" stroke="black" points="156,-367 156,-392 250,-392 250,-367 156,-367"/> +<text text-anchor="start" x="197.5" y="-375.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="156,-336 156,-367 250,-367 250,-336 156,-336"/> +<polygon fill="yellow" stroke="transparent" points="161,-341 161,-362 201,-362 201,-341 161,-341"/> +<polygon fill="none" stroke="black" points="161,-341 161,-362 201,-362 201,-341 161,-341"/> +<text text-anchor="start" x="164" y="-347.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="201,-341 201,-362 245,-362 245,-341 201,-341"/> +<polygon fill="none" stroke="black" points="201,-341 201,-362 245,-362 245,-341 201,-341"/> +<text text-anchor="start" x="204" y="-347.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If19->If11 --> +<g id="edge15" class="edge"> +<title>If19->If11:p0</title> +<path fill="none" stroke="red" d="M147.72,-384.8C116.87,-397.31 82.59,-414.16 72.17,-430.48"/> +<polygon fill="red" stroke="red" points="68.84,-429.41 69,-440 75.48,-431.62 68.84,-429.41"/> +<text text-anchor="middle" x="144.72" y="-378.4" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If19->EQ18 --> +<g id="edge16" class="edge"> +<title>If19->EQ18</title> +<path fill="none" stroke="black" d="M205.53,-396.01C206.57,-408.76 207.77,-423.4 208.77,-435.73"/> +<polygon fill="black" stroke="black" points="205.3,-436.19 209.6,-445.87 212.28,-435.62 205.3,-436.19"/> +<text text-anchor="middle" x="202.53" y="-398.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region25 --> +<g id="node13" class="node"> +<title>Region25</title> +<polygon fill="yellow" stroke="black" points="194,-282 128,-282 128,-246 194,-246 194,-282"/> +<text text-anchor="middle" x="161" y="-260.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region25->If11 --> +<g id="edge17" class="edge"> +<title>Region25->If11:p1</title> +<path fill="none" stroke="red" d="M149.15,-282.07C140.7,-295.13 129.84,-313.92 124,-332 110.25,-374.59 110.82,-389.45 110.98,-429.78"/> +<polygon fill="red" stroke="red" points="107.48,-430.01 111,-440 114.48,-429.99 107.48,-430.01"/> +<text text-anchor="middle" x="146.15" y="-284.67" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region25->If19 --> +<g id="edge18" class="edge"> +<title>Region25->If19:p0</title> +<path fill="none" stroke="red" d="M168.33,-282.23C173.11,-294.76 178.75,-312.49 180.47,-329.86"/> +<polygon fill="red" stroke="red" points="176.99,-330.19 181,-340 183.98,-329.83 176.99,-330.19"/> +<text text-anchor="middle" x="165.33" y="-284.83" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg26 --> +<g id="node14" class="node"> +<title>Phi_arg26</title> +<ellipse fill="lightyellow" stroke="black" cx="73" cy="-264" rx="37.09" ry="18"/> +<text text-anchor="middle" x="73" y="-260.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg26->Phi_arg8 --> +<g id="edge20" class="edge"> +<title>Phi_arg26->Phi_arg8</title> +<path fill="none" stroke="black" d="M63.83,-281.65C43.83,-320.21 0.18,-418.31 27,-496 41.37,-537.63 75.96,-575.97 99.94,-598.92"/> +<polygon fill="black" stroke="black" points="97.62,-601.54 107.31,-605.82 102.4,-596.43 97.62,-601.54"/> +<text text-anchor="middle" x="60.83" y="-284.25" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg26->Add16 --> +<g id="edge21" class="edge"> +<title>Phi_arg26->Add16</title> +<path fill="none" stroke="black" d="M91.19,-280C99.25,-285.9 109.13,-292.16 119,-296 169.26,-315.55 323.81,-291.14 359,-332 470,-460.89 226.92,-368.94 175,-432 156.92,-453.96 159.55,-472.12 175,-496 184.72,-511.01 228.01,-527.86 259.35,-538.45"/> +<polygon fill="black" stroke="black" points="258.45,-541.84 269.04,-541.65 260.65,-535.19 258.45,-541.84"/> +<text text-anchor="middle" x="88.19" y="-282.6" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg26->Region25 --> +<g id="edge19" class="edge"> +<title>Phi_arg26->Region25</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M110.12,-264C112.58,-264 115.04,-264 117.5,-264"/> +<polygon fill="black" stroke="black" points="117.61,-267.5 127.61,-264 117.61,-260.5 117.61,-267.5"/> +<text text-anchor="middle" x="113.12" y="-257.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_28 --> +<g id="node15" class="node"> +<title>Con_28</title> +<ellipse fill="none" stroke="black" cx="343" cy="-464" rx="27" ry="18"/> +<text text-anchor="middle" x="343" y="-460.3" font-family="Times,serif" font-size="14.00">6</text> +</g> +<!-- EQ29 --> +<g id="node16" class="node"> +<title>EQ29</title> +<ellipse fill="none" stroke="black" cx="323" cy="-364" rx="27" ry="18"/> +<text text-anchor="middle" x="323" y="-360.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ29->Add16 --> +<g id="edge22" class="edge"> +<title>EQ29->Add16</title> +<path fill="none" stroke="black" d="M318.38,-381.96C314.84,-395.44 310.07,-414.81 307,-432 301.54,-462.56 297.63,-498.01 295.36,-521.8"/> +<polygon fill="black" stroke="black" points="291.86,-521.58 294.43,-531.86 298.83,-522.22 291.86,-521.58"/> +<text text-anchor="middle" x="315.38" y="-384.56" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ29->Con_28 --> +<g id="edge23" class="edge"> +<title>EQ29->Con_28</title> +<path fill="none" stroke="black" d="M326.48,-382.07C329.52,-396.97 333.99,-418.83 337.51,-436.08"/> +<polygon fill="black" stroke="black" points="334.13,-437.03 339.56,-446.13 340.99,-435.63 334.13,-437.03"/> +<text text-anchor="middle" x="323.48" y="-384.67" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If30->If19 --> +<g id="edge24" class="edge"> +<title>If30->If19:p1</title> +<path fill="none" stroke="red" d="M238.89,-296.32C232.15,-306.21 226.24,-317.72 223.98,-329.78"/> +<polygon fill="red" stroke="red" points="220.47,-329.71 223,-340 227.44,-330.38 220.47,-329.71"/> +<text text-anchor="middle" x="235.89" y="-298.92" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If30->EQ29 --> +<g id="edge25" class="edge"> +<title>If30->EQ29</title> +<path fill="none" stroke="black" d="M284.72,-296.01C292.51,-309.64 301.52,-325.42 308.85,-338.24"/> +<polygon fill="black" stroke="black" points="305.85,-340.04 313.85,-346.98 311.92,-336.56 305.85,-340.04"/> +<text text-anchor="middle" x="281.72" y="-298.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region36 --> +<g id="node18" class="node"> +<title>Region36</title> +<polygon fill="yellow" stroke="black" points="194,-196 128,-196 128,-160 194,-160 194,-196"/> +<text text-anchor="middle" x="161" y="-174.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region36->Region25 --> +<g id="edge26" class="edge"> +<title>Region36->Region25</title> +<path fill="none" stroke="red" d="M161,-196.4C161,-207.74 161,-222.77 161,-235.68"/> +<polygon fill="red" stroke="red" points="157.5,-235.9 161,-245.9 164.5,-235.9 157.5,-235.9"/> +<text text-anchor="middle" x="158" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region36->If30 --> +<g id="edge27" class="edge"> +<title>Region36->If30:p0</title> +<path fill="none" stroke="red" d="M174.84,-196.06C187.5,-211.53 205.8,-233.52 216.25,-244.39"/> +<polygon fill="red" stroke="red" points="214.12,-247.18 224,-251 218.66,-241.85 214.12,-247.18"/> +<text text-anchor="middle" x="171.84" y="-198.66" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg37 --> +<g id="node19" class="node"> +<title>Phi_arg37</title> +<ellipse fill="lightyellow" stroke="black" cx="73" cy="-178" rx="37.09" ry="18"/> +<text text-anchor="middle" x="73" y="-174.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg37->Add16 --> +<g id="edge30" class="edge"> +<title>Phi_arg37->Add16</title> +<path fill="none" stroke="black" d="M54.57,-194.1C44.32,-203.73 32.54,-217.16 27,-232 17.05,-258.65 8.44,-274.45 27,-296 97.38,-377.73 191.87,-254.61 267,-332 280.01,-345.4 288.39,-466.53 291.56,-521.77"/> +<polygon fill="black" stroke="black" points="288.07,-522.09 292.13,-531.88 295.06,-521.7 288.07,-522.09"/> +<text text-anchor="middle" x="51.57" y="-196.7" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_arg37->Phi_arg26 --> +<g id="edge29" class="edge"> +<title>Phi_arg37->Phi_arg26</title> +<path fill="none" stroke="black" d="M73,-196.4C73,-207.74 73,-222.77 73,-235.68"/> +<polygon fill="black" stroke="black" points="69.5,-235.9 73,-245.9 76.5,-235.9 69.5,-235.9"/> +<text text-anchor="middle" x="70" y="-199" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg37->Region36 --> +<g id="edge28" class="edge"> +<title>Phi_arg37->Region36</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M110.12,-178C112.58,-178 115.04,-178 117.5,-178"/> +<polygon fill="black" stroke="black" points="117.61,-181.5 127.61,-178 117.61,-174.5 117.61,-181.5"/> +<text text-anchor="middle" x="113.12" y="-171.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return39->Region36 --> +<g id="edge31" class="edge"> +<title>Return39->Region36</title> +<path fill="none" stroke="red" d="M127.88,-124.3C132.99,-132.44 139.2,-142.31 144.84,-151.3"/> +<polygon fill="red" stroke="red" points="141.96,-153.29 150.25,-159.9 147.89,-149.57 141.96,-153.29"/> +<text text-anchor="middle" x="124.88" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return39->Phi_arg37 --> +<g id="edge32" class="edge"> +<title>Return39->Phi_arg37</title> +<path fill="none" stroke="black" d="M106.12,-124.3C100.93,-132.56 94.62,-142.61 88.9,-151.7"/> +<polygon fill="black" stroke="black" points="85.81,-150.05 83.45,-160.38 91.73,-153.77 85.81,-150.05"/> +<text text-anchor="middle" x="103.12" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter08/Makefile b/docs/chapter08/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter08/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/chapter08/README.md b/docs/chapter08/README.md new file mode 100644 index 00000000..85340e17 --- /dev/null +++ b/docs/chapter08/README.md @@ -0,0 +1,312 @@ +# Chapter 8: Lazy Phis, Break, Continue, and Evaluator + +# Table of Contents + +1. [Lazy Phi Creation](#lazy-phi-creation) +2. [Continue statement](#continue-statement) +3. [Break statement](#break-statement) +4. [Parser Considerations ](#parser-considerations) +5. [Identification of Basic Blocks in SoN graph](#identification-of-basic-blocks-in-son-graph) +6. [Examples](#examples) + -[Example 1](#example-1) + -[Example 2](#example-2) + -[Example 3](#example-3) + +7. [Sea of Nodes Graph Evaluator](#sea-of-nodes-graph-evaluator) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter08) 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-chapter07...linear-chapter08) it to the previous chapter. + + +In this chapter: + +* We move from eager to lazy `Phi` creation in loops. +* We add support for `break` and `continue` statements. +* We implement a Sea of Nodes Graph Evaluator. + +Here is the [complete language grammar](08-grammar.md) for this chapter. + + +## Lazy Phi Creation + +In [chapter 7](../chapter07/README.md), we created `PhiNode`s for all variables +in the loop head eagerly. This approach creates some unnecessary Phis but the +redundant Phis get cleaned up later. + +In this chapter we add support for creating the `PhiNode`s lazily. + +The main complication with creating `PhiNode`s lazily is that when we create a +Phi, it must be created in the innermost loop head scope where it would have +been created had we done it eagerly. Since scopes get duped in `if` and +`while` statements, we cannot just create Phis in the current scope. + +It turns out that the easiest way to create the `PhiNode`s lazily is to hook +them up to name lookup. But how do we know that a Phi must be created when we +access a name? We need a way to flag that a particular name mapping must be +converted to a `PhiNode` on lookup. + +We do this as follows: + +* In `ScopeNode.dup()`, if the Scope is being duplicated for a loop head, then + instead of setting the name's definition to the original node, we set it to + the Scope itself. This acts like a sentinel. + + ```java + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); + ``` + +* Subsequently, when a lookup accesses a name, we notice that the def is set to + the Scope node, and we create a `PhiNode` at this point. The relevant + implementation is in `ScopeNode.update()`. + + ```java + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have insert a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + ``` + +* When we merge scopes, we ensure lazy `PhiNode` creation at the correct inner + scope level by invoking lookup by name instead of directly accessing the + defs. + + ```java + if( in(i) != that.in(i) ) // No need for redundant Phis + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + ``` + +* Finally, in `ScopeNode.endLoop()` we clean up any leftover sentinels, replacing the sentinel with the input from loop head. + + ```java + for( int i=1; i<nIns(); i++ ) { + if( back.in(i) != this ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.setDef(2,back.in(i)); + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) + phi.subsume(in); + } + if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also + exit.setDef(i,in(i)); + } + ``` + +## `continue` Statement + +In chapter7, we had a single backedge from the loop's end flowing back to the +loop head. + +With the addition of a `continue` statement, we can have multiple backedges +flowing back to the loop head. + +We have several ways of implementing these backedges. + +1. The traditional way would be to let each backedge from `continue` merge into + the loop head. Phis would require as many inputs as there are edges. The + downside is now are Loops are not simply nested. This makes it difficult to + do many kinds of peephole-based loop optimizations, such as "partially + rolling" the loop to allow more loop invariants to get hoisted. +2. An alternative is collect all `continue`s at a single merge point (`Region`) + and then create a single backedge flowing from the continue `Region` to the + loop head. +3. A third approach is to create a stack of continue `Region`s rather than a + single continue `Region`. This has the benefit of keeping our Phis simple + with just two inputs as they are now, whereas the other approaches require + Phis with more than 2 inputs. On the other hand we end up with as many + continue `Region`s as there are `continue` statements, and corresponding + Phis that are stacked. + +In this chapter we adopt option 3 as it is the simplest implementation on top +of our basic `while` loop architecture. We also experimented with +option 2. For readers who would like to see this alternative solution, we +provide a separate branch with such an implementation. + +The implementation requires some careful handling of scopes. This is because +we would like to only generate `PhiNode/RegionNode`s for continues if necessary. + +In our [basic loop architecture](../chapter07/README.md), by the time we get to +the loop backedge, we have already exited all nested blocks/scopes, we just +need to stitch together the current scope+ctrl into the Loop scope+ctrl and +create `PhiNode`s as needed. + +A `continue` however, can occur inside nested scopes (such as nested `if` +statement). Since we want to lazily create the continue `Region`, the first +time we see a `continue`, we need to dupe the head scope and merge the current +scope into it to generate a continue Scope and `Region`. Subsequently, when we +see another `continue`, we need to construct a new `Region` and merge the +previous continue Scope with the current Scope. + +The implementation is a variation of above. + +* The first `continue` triggers a dupe of the current scope; we prune any + nested lexical scopes deeper than the head scope, removing any name bindings + that were not visible in the head scope. This is essentially ensuring that + we "exit" any nested scopes. + + We set the continue scope initially to null. + + ```java + // No continues yet + _continueScope = null; + ``` + When we parse continue, the first time `_continueScope` is null. + + ```java + private Node parseContinue() { return (_continueScope = require(jumpTo( _continueScope ),";")); } + + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + 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); + return toScope; + } + ``` + +* The continue scope becomes the base scope for the subsequent `continue` + statement, thus forming a stack of continue scopes/regions. +* After the loop is done, if we find that a continue scope was created within + the loop, we must merge the current scope into the continue scope, and make + the continue scope the active scope. + + ```java + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + ``` + +## `break` Statement + +Implementing `break` is simpler than `continue`, because the exit scope is +created before we parse the loop body, and this becomes the initial `break` +scope. When we see `break`, we merge the current scope, after pruning any +nested lexical scopes, to the current break scope, and the resulting new scope +becomes the active break scope. + +## Parser Considerations + +Since a `continue` or `break` targets the immediate surrounding `while` loop, +we maintain a stack of the `continue` and `break` scopes. This is done by +saving the previous `continue` or `break` scope before parsing a `while` loop +and restoring afterward. + +## Examples + +### Example 1 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; +``` + + + + +### Example 2 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; +``` + + + +### Example 3 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; +``` + + + + +## Sea of Nodes Graph Evaluator + +The evaluator directly evaluates the given graph by walking forward through the control flow from the program start until it either encounters a Return node or it passes the maximum loop count. + +When called, the evaluator sets itself up by first traversing the graph to find the Start node. Then, if a program uses the special `arg` parameter, the passed-in parameter value will be bound to the node that represents it. + +With that brief setup done, the control projection from the Start node is traversed and the program can begin "execution". + +At this point, control flow is at the first region of the program, but it is treated just the same as any other region. There are two things that must be done at each region. First, resolve all phis to a specific value; and second to determine where control flow will continue to. + +It may seem like more than that should be done, but by resolving phi nodes, any logic that is specific to the control flow path for the given will be resolved. Any other work will eventually be resolved later on as-needed. This is sufficient for the program to run! + +Finding the next place control flow will move to after a region is straightforward because any region only has a single control node that uses it. So we search for that node in the Region's users. + +Once we have that node, our behavior depends on what type of control flow node we've landed on. There are only 3 options: `RegionNode`, `IfNode`, and `ReturnNode`. If it is another `RegionNode`, we do the same again. If it's a `ReturnNode`, we can resolve the returned expression and return the program's value. Finally, for an `IfNode`, we must first resolve the test expression so that we can choose the false (projection 0) or true (projection 1) branch. Whichever projection from the `IfNode` is chosen, we step through that projection on to the control node (a `RegionNode`) that uses it. + +We talk about resolving nodes above, but what does that mean? A node will either have a value (for instance a constant), will already be resolved with the resolved value cached, or it will operate on nodes that it uses, which must be resolved. Once a node's inputs are resolved, its operation may be performed on them. For instance, an `AddNode`'s value will be the sum of its two inputs. Once the value is resolved, the resolved value is returned. + +With that, a simple non-looping program can be evaluated. + +Looping is almost functional with that, too, with only a couple of small extra details. Whenever control moves through a `LoopNode`, the evaluator checks that it hasn't run out of loop iterations. If it has, a timeout RuntimeException will be thrown. + +Finally, while calculating the value of `PhiNode`s in the loop region, we must be careful to compute all of their new values before we update any of their cached values. That's because as a loop iterates, we must ensure that all `PhiNode` values are consistently the value from the same point in time. Once all of the new values are calculated, we can update the cache for all of them at once. To illustrate this, consider the following code: + +```java +t = 0; +while(arg < 10) { + t = arg; + arg = arg + 1; +} +return t; +``` + +In this code, the two statements within the loop may be evaluated in either order by the graph, so we must ensure that the new value `arg` is not cached before the value of `t` can be set to the previous value of `arg`. + +This approach to evaluation is useful for testing because it allows a program to be executed without worrying about instruction selection, register allocation or code generation. It can execute on any valid Sea of Nodes graph, as well, so execution results of unoptimized code can be checked against the results of optimized code! This fact lends itself to some interesting automated / regression testing ideas. For instance, the result of execution could be checked after every optimization step, possibly helping isolate some types of errors. + +``` java +arg=arg+arg; +arg=arg+arg; +... +arg=arg+arg; +return arg; +``` + +On the other hand, this engine is not designed to be particularly fast! Because not all expressions are cached, it's possible to construct programs like the preceeding one which have exponential runtime. diff --git a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java new file mode 100644 index 00000000..f5694a78 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -0,0 +1,181 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.Arrays; +import java.util.BitSet; +import java.util.HashMap; + +public class GraphEvaluator { + + public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT } + + public record Result(ResultType type, long value) {} + + /** + * Find the start node from some node in the graph or null if there is no start node + */ + private static StartNode findStart(BitSet visit, Node node) { + if (node == null) return null; + if (node instanceof StartNode start) return start; + if( visit.get(node._nid) ) return null; + visit.set(node._nid); + for( Node def : node._inputs ) { + var res = findStart(visit,def); + if( res != null ) return res; + } + for( Node use : node._outputs ) { + var res = findStart(visit,use); + if( res != null ) return res; + } + return null; + } + + /** + * Find the control output from a control node + */ + private static Node findControl(Node control) { + for( Node use : control._outputs ) { + if (use.isCFG()) return use; + } + return null; + } + + /** + * Find the projection for a node + */ + private static ProjNode findProjection(Node node, int idx) { + for( Node use : node._outputs ) { + if (use instanceof ProjNode proj && proj._idx == idx) return proj; + } + return null; + } + + /** + * Cache values for phi and parameter projection nodes. + */ + private final HashMap<Node, Long> cacheValues = new HashMap<>(); + /** + * Cache for loop phis as they can depend on itself or other loop phis + */ + private long[] loopPhiCache = new long[16]; + + private GraphEvaluator() { + } + + private long div(DivNode div) { + long in2 = getValue(div.in(2)); + return in2 == 0 ? 0 : getValue(div.in(1)) / in2; + } + + /** + * Calculate the value of a node + */ + private long getValue(Node node) { + var cache = cacheValues.get(node); + if (cache != null) return cache; + return switch (node) { + case ConstantNode cons -> ((TypeInteger)cons.compute()).value(); + case AddNode add -> getValue(add.in(1)) + getValue(add.in(2)); + case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0; + case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0; + case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0; + case DivNode div -> div(div); + case MinusNode minus -> -getValue(minus.in(1)); + case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2)); + case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0; + case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2)); + default -> throw Utils.TODO("Unexpected node " + node); + }; + } + + /** + * Special case of latchPhis when phis can depend on phis of the same region. + */ + private void latchLoopPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + int i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2); + loopPhiCache[i++] = value; + } + } + i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]); + } + } + + /** + * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region. + */ + private void latchPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + cacheValues.put(phi, value); + } + } + } + + /** + * Run the graph until either a return is found or the number of loop iterations are done. + */ + private Result evaluate(StartNode start, long parameter, int loops) { + var parameter1 = findProjection(start, 1); + if (parameter1 != null) cacheValues.put(parameter1, parameter); + Node control = findProjection(start, 0); + Node prev = start; + while (control != null) { + Node next; + switch (control) { + case RegionNode region -> { + if (region instanceof LoopNode && region.in(1) != prev) { + if (loops--<=0) return new Result(ResultType.TIMEOUT, 0); + latchLoopPhis(region, prev); + } else { + latchPhis(region, prev); + } + next = findControl(region); + } + case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1); + case ReturnNode ret -> { + return new Result(ResultType.VALUE, getValue(ret.in(1))); + } + case ProjNode ignored -> next = findControl(control); + default -> throw Utils.TODO("Unexpected control node " + control); + } + prev = control; + control = next; + } + return new Result(ResultType.FALLTHROUGH, 0); + } + + public static long evaluate(Node graph) { + return evaluate(graph, 0); + } + + public static long evaluate(Node graph, long parameter) { + return evaluate(graph, parameter, 1000); + } + + 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"); + return res.value; + } + + public static Result evaluateWithResult(Node graph, long parameter, int loops) { + var start = findStart(new BitSet(), graph); + if (start == null) return new Result(ResultType.TIMEOUT, 0); + var evaluator = new GraphEvaluator(); + return evaluator.evaluate(start, parameter, loops); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 07f1af21..d75e5bea 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -26,7 +26,7 @@ public class GraphVisualizer { // nodes in the graph. Collection<Node> all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter07 {\n"); + sb.append("digraph chapter08 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -212,6 +212,8 @@ public class GraphVisualizer { for( String name : syms.keySet() ) { int idx = syms.get(name); Node def = scope.in(idx); + while( def instanceof ScopeNode lazy ) + def = lazy.in(idx); if( def==null ) continue; sb.append("\t") .append(scopeName).append(":") diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index cfb4deb4..69796828 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -46,6 +46,8 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("break"); + add("continue"); add("else"); add("false"); add("if"); @@ -62,10 +64,14 @@ public class Parser { */ public final Stack<ScopeNode> _xScopes = new Stack<>(); + ScopeNode _continueScope; + ScopeNode _breakScope; + public Parser(String source, TypeInteger arg) { Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); + _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); STOP = new StopNode(); } @@ -136,6 +142,8 @@ public class Parser { else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); else if (matchx("while")) return parseWhile(); + else if (matchx("break")) return parseBreak(); + else if (matchx("continue")) return parseContinue(); else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); @@ -150,6 +158,10 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseWhile() { + + var savedContinueScope = _continueScope; + var savedBreakScope = _breakScope; + require("("); // Loop region has two control inputs, the first is the entry @@ -179,36 +191,71 @@ public class Parser { ifNode.unkeep(); Node ifF = new ProjNode(ifNode, 1, "False").peephole(); - // Clone the body Scope to create the exit Scope - // which accounts for any side effects in the predicate - // The exit Scope will be the final scope after the loop, - // And its control input is the False branch of the loop predicate - // Note that body Scope is still our current scope - var exit = _scope.dup(); - _xScopes.push(exit); - exit.ctrl(ifF); + // 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 + // scope after the loop, and its control input is the False branch of + // the loop predicate. Note that body Scope is still our current scope. + ctrl(ifF); + _xScopes.push(_breakScope = _scope.dup()); + + // No continues yet + _continueScope = null; // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body - // The true branch loops back, so whatever is current control (_scope.ctrl) gets - // added to head loop as input. endLoop() updates the head scope, - // and goes through all the phis that were created earlier. For each - // phi, it sets the second input to the corresponding input from the back edge. - // If the phi is redundant, it is replaced by its sole input. + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + + // The true branch loops back, so whatever is current _scope.ctrl gets + // added to head loop as input. endLoop() updates the head scope, and + // goes through all the phis that were created earlier. For each phi, + // it sets the second input to the corresponding input from the back + // edge. If the phi is redundant, it is replaced by its sole input. + var exit = _breakScope; head.endLoop(_scope, exit); head.unkeep().kill(); _xScopes.pop(); // Cleanup _xScopes.pop(); // Cleanup + _continueScope = savedContinueScope; + _breakScope = savedBreakScope; + // At exit the false control is the current control, and // the scope is the exit scope after the exit test. - return (_scope = exit); + return _scope = exit; + } + + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + 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); + return toScope; } + private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); } + + private Node parseBreak () { checkLoopActive(); return ( _breakScope = require(jumpTo( _breakScope ),";")); } + private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); } + /** * Parses a statement * diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 8f3e5a98..84a368fd 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -70,6 +70,11 @@ public class AddNode extends Node { // Now we only see (add add non) + // Dead data cycle; comes about from dead infinite loops. Do nothing, + // the loop will peep as dead after a bit. + if( lhs.in(1) == lhs ) + return null; + // Do we have (x + con1) + con2? // Replace with (x + (con1+con2) which then fold the constants if( lhs.in(2)._type.isConstant() && t2.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 0f414c08..23a8fafc 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -46,7 +46,7 @@ public class IfNode extends MultiNode { 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) - : null; // Repeated test not dominated on one side + : dom._type; // Repeated test not dominated on one side return TypeTuple.IF_BOTH; } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 81f707ec..c192bc20 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -16,7 +16,8 @@ public class LoopNode extends RegionNode { @Override public Type compute() { - return inProgress() ? Type.CONTROL : super.compute(); + if( inProgress() ) return Type.CONTROL; + return entry()._type; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 35b07781..2d6d5ad5 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; @@ -100,6 +101,7 @@ public abstract class Node { public final String print() { return _print0(new StringBuilder(), new BitSet()).toString(); } + // 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) { @@ -138,6 +140,8 @@ public abstract class Node { sb.append("\n"); } + public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } + public boolean isMultiHead() { return false; } public boolean isMultiTail() { return false; } @@ -153,8 +157,6 @@ public abstract class Node { public int nIns() { return _inputs.size(); } - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } @@ -443,7 +445,10 @@ public abstract class Node { * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; } + public static void reset() { + UNIQUE_ID = 1; + _disablePeephole=false; + } /** * Debugging utility to find a Node by index diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 2a4ff52a..c7b5b357 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -85,10 +85,13 @@ public class PhiNode extends Node { */ private Node singleUniqueInput() { Node live = null; - for( int i=1; i<nIns(); i++ ) + 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( live == null || live == in(i) ) live = in(i); else return null; + } return live; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index acaadaf1..453d028f 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import java.util.Collection; import java.util.BitSet; public class RegionNode extends Node { diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index a4fcbe65..e5d03d93 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -39,6 +39,10 @@ public class ScopeNode extends Node { for( int j=0; j<nIns(); j++ ) { sb.append(names[j]).append(":"); Node n = in(j); + while( n instanceof ScopeNode loop ) { + sb.append("Lazy_"); + n = loop.in(j); + } n._print0(sb, visited).append(" "); } sb.setLength(sb.length()-1); @@ -107,8 +111,18 @@ public class ScopeNode extends Node { var idx = syms.get(name); if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope Node old = in(idx); - // If n is null we are looking up rather than updating, hence return existing value - return n==null ? old : setDef(idx,n); + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have insert a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer } public Node ctrl() { return in(0); } @@ -131,6 +145,11 @@ public class ScopeNode extends Node { * tables), nor deep (would dup the Scope, the HashMap tables, but then * also the program Nodes). * <p> + * If the {@code loop} flag is set, the edges are filled in as the original + * Scope, as a indication of Lazy Phis at loop heads. The goal here is to + * not make Phis at loop heads for variables which are never touched in the + * loop body. + * <p> * The new Scope is a full-fledged Node with proper use<->def edges. */ public ScopeNode dup() { return dup(false); } @@ -144,17 +163,10 @@ public class ScopeNode extends Node { dup._scopes.push(new HashMap<>(syms)); dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i<nIns(); i++ ) { - if ( !loop ) { dup.addDef(in(i)); } - else { - String[] names = reverseNames(); // Get the variable names - // Create a phi node with second input as null - to be filled in - // by endLoop() below - dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole()); - // Ensure our node has the same phi in case we created one - setDef(i, dup.in(i)); - } - } + for( int i=1; i<nIns(); i++ ) + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); return dup; } @@ -172,7 +184,9 @@ public class ScopeNode extends Node { // Note that we skip i==0, which is bound to '$ctrl' for (int i = 1; i < nIns(); i++) if( in(i) != that.in(i) ) // No need for redundant Phis - setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope return r.unkeep().peephole(); } @@ -184,14 +198,26 @@ public class ScopeNode extends Node { assert ctrl instanceof LoopNode loop && loop.inProgress(); ctrl.setDef(2,back.ctrl()); for( int i=1; i<nIns(); i++ ) { - PhiNode phi = (PhiNode)in(i); - assert phi.region()==ctrl && phi.in(2)==null; - phi.setDef(2,back.in(i)); - // Do an eager useless-phi removal - Node in = phi.peephole(); - if( in != phi ) - phi.subsume(in); + if( back.in(i) != this ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.setDef(2,back.in(i)); + } + if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also + exit.setDef(i,in(i)); } back.kill(); // Loop backedge is dead + // Now one-time do a useless-phi removal + for( int i=1; i<nIns(); i++ ) { + if( in(i) instanceof PhiNode phi ) { + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) { + phi.subsume(in); + setDef(i,in); // Set the update back into Scope + } + } + } + } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 547c36f8..13b42f96 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -31,7 +31,7 @@ public class Chapter01Test { parser.parse(); StartNode start = Parser.START; for( Node use : start._outputs ) - if( use instanceof ConstantNode con ) + if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) assertEquals(TypeInteger.constant(0),con._type); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 1e67cef5..64ff153e 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 testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c; "); Node._disablePeephole = true; StopNode ret = parser.parse(); Node._disablePeephole = false; @@ -40,7 +40,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()); } @@ -54,7 +54,7 @@ public class Chapter03Test { assertEquals("Undefined name 'a'",e.getMessage()); } } - + @Test public void testRedeclareVar() { try { diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 98878ca6..2e2abb25 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -10,7 +10,7 @@ public class Chapter04Test { @Test public void testPeephole() { - Parser parser = new Parser("return 1+arg+2;"); + Parser parser = new Parser("return 1+arg+2; "); StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @@ -38,7 +38,7 @@ public class Chapter04Test { @Test public void testPeephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3;"); + Parser parser = new Parser("return 1+arg+2+arg+3; "); StopNode ret = parser.parse(); assertEquals("return ((arg*2)+6);", ret.print()); } @@ -52,7 +52,7 @@ public class Chapter04Test { @Test public void testVarArg() { - Parser parser = new Parser("return arg;"); + Parser parser = new Parser("return arg; "); StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof ProjNode); @@ -61,49 +61,49 @@ public class Chapter04Test { @Test public void testConstantArg() { - Parser parser = new Parser("return arg;", TypeInteger.constant(2)); + Parser parser = new Parser("return arg; ", TypeInteger.constant(2)); StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testCompEq() { - Parser parser = new Parser("return 3==3;"); + Parser parser = new Parser("return 3==3; "); StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testCompEq2() { - Parser parser = new Parser("return 3==4;"); + Parser parser = new Parser("return 3==4; "); StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq() { - Parser parser = new Parser("return 3!=3;"); + Parser parser = new Parser("return 3!=3; "); StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq2() { - Parser parser = new Parser("return 3!=4;"); + Parser parser = new Parser("return 3!=4; "); StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testBug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;"); + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; "); StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testBug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a;"); + Parser parser = new Parser("int a=arg+1; a=a; return a; "); StopNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 5bb67817..68d379a1 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -17,7 +17,9 @@ if (arg == 1) a = arg+2; else { a = arg-3; + } + return a;"""); StopNode ret = parser.parse(); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 00d725bc..b858b83e 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -29,7 +29,7 @@ if (arg) a = 2; return (arg < a) < 3; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse(false); assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 189fcf66..d691672e 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -37,7 +37,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } @Test @@ -57,7 +57,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,0,Phi(Loop21,Phi_sum,(Phi(Loop,0,(Phi_j+1))+Phi_sum)));", stop.toString()); + assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -74,7 +74,7 @@ return b; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); Node._disablePeephole = false; } @@ -94,7 +94,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -156,7 +156,7 @@ int a = 1; while(arg) a = 2; return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse(false); assertEquals("return Phi(Loop7,1,2);", 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 new file mode 100644 index 00000000..5d9d1545 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -0,0 +1,218 @@ +package com.seaofnodes.simple; + +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( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + 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)); + Assert.assertEquals(10, GraphEvaluator.evaluate(stop, 6)); + } + + + @Test + public void testEx5() { + Parser parser = new Parser( + """ +int a = 1; +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 7) + continue; + a = a + 1; +} +return a; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testEx4() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testEx3() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + + @Test + public void testEx2() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testEx1() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testRegress1() { + Parser parser = new Parser( + """ +while( arg < 10 ) { + int a = arg+2; + if( a > 4 ) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + 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()); + } + + @Test + public void testBreakOutsideLoop() { + try { + new Parser(""" +if(arg <= 10) { + break; + arg = arg + 1; +} +return arg; +""").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("No active loop for a break or continue",e.getMessage()); + } + } + + @Test + public void testRegress3() { + Parser parser = new Parser(""" +while(arg < 10) { + break; +} +return arg; +"""); + StopNode stop = parser.parse(); + assertEquals("return arg;", stop.toString()); + } + + @Test + public void testRegress4() { + Parser parser = new Parser(""" +int a = 1; +while(arg < 10) { + a = a + 1; + if (arg > 2) { + int a = 17; + break; + } +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testRegress5() { + Parser parser = new Parser(""" +int a = 1; +while(1) { + a = a + 1; + if (a<10) continue; + break; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java new file mode 100644 index 00000000..82a6a472 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.fuzzer.Fuzzer; +import org.junit.Ignore; +import org.junit.Test; + + +import static org.junit.Assert.assertTrue; + +/** + * To use the fuzzer run the <code>fuzzPeeps</code> methods. + * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line + * via <code>mvn clean test -Dtest=com.seaofnodes.simple.FuzzerWrap#fuzzPeeps</code> + */ +public class FuzzerWrap { + + @Test + @Ignore + public void fuzzPeeps() { + var fuzzer = new Fuzzer(); + for (int i=0; i<100000; i++) + fuzzer.fuzzPeeps(i); + assertTrue(fuzzer.noExceptions()); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java new file mode 100644 index 00000000..5fcd8764 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -0,0 +1,128 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.GraphEvaluator; +import com.seaofnodes.simple.node.StopNode; + +import java.util.ArrayList; +import java.util.Random; +import java.util.function.Consumer; + +/** + * Implementation of the fuzzer. + * Random testcases are generated using the ScriptGenerator. + * 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. This includes script which generate different + * results when the compiled graph with and without peeps is executed. + * To aid debugging scripts that cause errors are then reduced by applying rules and checking + * that the same issue persists. + */ +public class Fuzzer { + + private static final int EVAL_TIMEOUT = 1000; + + /** + * List of exceptions already encountered. + * This is used to filter new exceptions and discard them if they are already found. + */ + private final ArrayList<Throwable> exceptions = new ArrayList<>(); + + /** + * Filter and record an exception in a script. + * @param e The exception caused by the script + * @param script The script causing the exception + * @param reproducer Reproducer which should be used to reproduce the test case. + */ + private void recordException(Throwable e, String script, Consumer<String> reproducer) { + for (var ex : exceptions) { + if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return; + } + exceptions.add(e); + System.out.println("========== Stack =========="); + e.printStackTrace(System.out); + System.out.println("========== Code ==========="); + System.out.println(script); + System.out.println("========= Reduced ========="); + System.out.println(Reducer.reduce(script, e, reproducer)); + System.out.println("==========================="); + System.out.flush(); + } + + /** + * 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 peeps enabled and disabled. + * 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 stop1; + try { + stop1 = FuzzerUtils.parse(script, false); + } catch (RuntimeException e1) { + try { + FuzzerUtils.parse(script, true); + } catch (RuntimeException e2) { + if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) { + if (!valid || e1.getClass() == RuntimeException.class) return; + } else { + e1.addSuppressed(e2); + } + } + throw e1; + } + var stop2 = FuzzerUtils.parse(script, true); + checkGraphs(stop1, stop2, 0); + checkGraphs(stop1, stop2, 1); + checkGraphs(stop1, stop2, 10); + } + + /** + * Check that the script does not result in exceptions. + * @param script The script to test. + * @param valid If the script is valid or if it might contain syntax errors. + */ + private void check(String script, boolean valid) { + try { + runCheck(script, valid); + } catch (Throwable e) { + recordException(e, script, s->runCheck(s, valid)); + } + } + + /** + * Run one test with the given seed. + * @param seed The seed to use for generating this test case + */ + public void fuzzPeeps(long seed) { + var rand = new Random(seed); + var sb = new StringBuilder(); + var valid = new ScriptGenerator(rand, sb, false).genProgram(); + check(sb.toString(), valid); + } + + /** + * Check that no exceptions happened. + * @return true if no exception happened + */ + public boolean noExceptions() { + return exceptions.isEmpty(); + } +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java new file mode 100644 index 00000000..37a57e11 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -0,0 +1,58 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; + +/** + * Some utilities for the fuzzer. + */ +class FuzzerUtils { + + /** + * Check that eiter one of the objects is null or that both are equal. + */ + private static boolean equalOrNull(Object a, Object b) { + if (a == null || b == null) return true; + return a.equals(b); + } + + /** + * Check if both stack traces have the same first entry. Empty stack traces can happen with NPE optimization + * and allow the other to be any stack trace. + */ + private static boolean sameStackTraceOrigin(StackTraceElement[] a, StackTraceElement[] b) { + if (a == null || a.length == 0 || b == null || b.length == 0) return true; // One or both stack traces are missing. + return a[0].equals(b[0]); + } + + /** + * Checks if two exceptions are caused by the same problem. + */ + public static boolean isExceptionFromSameCause(Throwable a, Throwable b) { + if (a == null || b == null) return a == b; // Handle the null case + if (a.getClass() != b.getClass()) return false; // Different classes + if (!equalOrNull(a.getMessage(), b.getMessage())) return false; // Different messages. Null is allowed as wildcard + var s1 = a.getStackTrace(); + var s2 = b.getStackTrace(); + if (!sameStackTraceOrigin(s1, s2)) return false; // Different stack trace origins + if (!isExceptionFromSameCause(a.getCause(), b.getCause())) return false; // Different causes + var o1 = a.getSuppressed(); + var o2 = b.getSuppressed(); + if (o1 == null || o2 == null || o1.length != o2.length) return o1 == o2; // Different suppression + for (int i=0; i<o1.length; i++) { + if (!isExceptionFromSameCause(o1[i], o2[i])) return false; // Different suppression + } + return true; + } + + /** + * Parse script with peepholes enabled or disabled + */ + public static StopNode parse(String script, boolean runPeeps) { + var parser = new Parser(script); + Node._disablePeephole = !runPeeps; + return parser.parse(); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java new file mode 100644 index 00000000..b7fc18ec --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java @@ -0,0 +1,144 @@ +package com.seaofnodes.simple.fuzzer; + +import java.util.function.Consumer; +import java.util.function.Predicate; +import java.util.regex.Pattern; + +/** + * This class is used to reduce test cases created by the fuzzer. + * It applies rewrite rules to the test case and checks that the + * test still produces the same exception. + * This is done in a fixpoint iteration until every rewrite produces + * no or a different exception. + */ +public class Reducer { + + /** + * Holder for the rewrite rules + */ + private record Replace(Pattern p, String r) {} + + /** + * List of rewrite rules. + */ + private static final Replace[] REPLACEMENTS = { + new Replace(Pattern.compile("(?<=[+\\-*/<>=(])--"), ""), + new Replace(Pattern.compile("\\b--"), "+"), + new Replace(Pattern.compile("\\b\\+-"), "-"), + new Replace(Pattern.compile("\\bfalse\\b"), "0"), + new Replace(Pattern.compile("\\btrue\\b"), "1"), + new Replace(Pattern.compile("-"), ""), + new Replace(Pattern.compile("(?<![+\\-*/<>=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"), + 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("\\d+\\+"), ""), + new Replace(Pattern.compile("\\+\\d+"), ""), + new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), + new Replace(Pattern.compile("\\n+"), "\n"), + new Replace(Pattern.compile("^\\n+|\\n+$"), ""), + new Replace(Pattern.compile("else *"), ""), + new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""), + new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""), + }; + + /** + * Predicate to test if the reduced script generates the same error. + */ + private final Predicate<String> tester; + + /** + * Create a reducer with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + private Reducer(Predicate<String> tester) { + this.tester = tester; + } + + /** + * Rewrites the script with one rewrite rule. + */ + private String doReplacement(String script, Pattern pattern, String with) { + var matcher = pattern.matcher(script); + var sb = new StringBuilder(); + int last = 0; + while (matcher.find()) { + var pos = sb.length(); + matcher.appendReplacement(sb, with); + var tail = sb.length(); + matcher.appendTail(sb); + if (tester.test(sb.toString())) { + sb.setLength(tail); + } else { + sb.setLength(pos); + sb.append(script, last, matcher.end()); + } + last = matcher.end(); + } + matcher.appendTail(sb); + return sb.toString(); + } + + /** + * Clean up variable names from the random ones generated by the fuzzer. + */ + private String cleanVariables(String script) { + var matcher = Pattern.compile("\\bint ([0-9a-zA-Z_]+)").matcher(script); + int num = 0; + while (matcher.find()) { + var var = matcher.group(1); + if (var.matches("v\\d+")) continue; + while (script.contains("v"+num)) num++; + var n = script.replaceAll("\\b"+var+"\\b", "v" + num); + if (tester.test(n)) { + script = n; + } + } + return script; + } + + /** + * Run all rewrite rules once. + */ + private String doAllReplacements(String script) { + for (var replace: REPLACEMENTS) { + script = doReplacement(script, replace.p, replace.r); + } + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + public static String reduce(String script, Predicate<String> tester) { + var reducer = new Reducer(tester); + String old; + do { + old = script; + script = reducer.doAllReplacements(script); + script = reducer.cleanVariables(script); + } while (!script.equals(old)); + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a reproducer. + * @param ex The exception originally caused by the script + * @param reproducer Test function which throws an exception which will be checked against ex. + */ + public static String reduce(String script, Throwable ex, Consumer<String> reproducer) { + return reduce(script, s->{ + Throwable nex = null; + try { + reproducer.accept(s); + } catch (Throwable e) { + nex = e; + } + return FuzzerUtils.isExceptionFromSameCause(nex, ex); + }); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java new file mode 100644 index 00000000..148c2319 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -0,0 +1,462 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.ScopeNode; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.Random; + +/** + * Generate a pseudo random script. + * This generator will generate the same script for two random number generators initialized with the same seed. + * To generate valid code it implements the parser but instead of parsing it emits the statements and expressions. + * It is guaranteed to terminate. + */ +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; + /** + * Valid characters for identifiers. The last 10 are not valid for the first character. + */ + private static final String VAR_CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_0123456789"; + /** + * List of keywords not valid for identifiers. + */ + private static final HashSet<String> KEYWORDS = getKeywords(); + + /** + * Flag for a statement that it does not pass on control flow to the next statement. + */ + private static final int FLAG_STOP = 0x01; + /** + * Flag for a statement that it contains a final if statement without an else branch. + */ + private static final int FLAG_IF_WITHOUT_ELSE = 0x02; + /** + * Binary operators. + */ + private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"}; + /** + * Unary operators. + */ + private static final String[] UNARY_OP = {"-"}; + + + /** + * The random number generator used for random decisions. + */ + private final Random random; + /** + * Indentation depth. + */ + private int indentation = 0; + /** + * Output string builder + */ + private final StringBuilder sb; + /** + * Number of nested loops + */ + private int loopDepth = 0; + /** + * Current scope start in the variables list. + */ + private int currScopeStart = 0; + /** + * The depth of blocks allowed. + */ + private int depth = 7; + /** + * The depth of expressions allowed. + */ + private int exprDepth = 3; + /** + * Current variables in scope. + */ + private final ArrayList<String> variables = new ArrayList<>(); + /** + * If this needs to generate valid scripts or is also allowed to generate invalid ones. + */ + private final boolean generateValid; + /** + * If this script might be invalid. + */ + private boolean maybeInvalid = false; + + /** + * + * @param random the random number generator. + * @param sb the script will be written to this string builder. + * @param generateValid if the script should be guaranteed valid or if it is allowed to contain bugs. + */ + public ScriptGenerator(Random random, StringBuilder sb, boolean generateValid) { + this.random = random; + this.sb = sb; + this.generateValid = generateValid; + } + + /** + * Random number with log distribution + * @param max The maximum value + * @return A random number in the range [0, max) with higher numbers being more uncommon. + */ + private int randLog(int max) { + max--; + int n = 1<<max; + var num = random.nextInt(n); + for (int i=max-1; i>=0; i--) { + if ((num & (1<<i))!=0) return max-i-1; + } + return max; + } + + /** + * Helper function to print indentation. + * @return sb for chaining + */ + private StringBuilder printIndentation() { + return sb.repeat(' ', indentation); + } + + /** + * Generate a random name for variables. This might be invalid when it is a keyword. + * @return The random name generated + */ + private StringBuilder getRandomName() { + int len = random.nextInt(10) + 1; + StringBuilder sb = new StringBuilder(len); + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10))); + for (int i=1; i<len; i++) + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + return sb; + } + + /** + * Generate a variable name. This might be new random name or a name from an outer scope. + * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope. + * @return The variable name. + */ + private String getVarName() { + if (currScopeStart > 0 && random.nextInt(10) > 7) { + // Use a variable outside the current scope. + var v = variables.get(random.nextInt(currScopeStart)); + if (variables.lastIndexOf(v) < currScopeStart) return v; + if (!generateValid) { + maybeInvalid = true; + return v; + } + } + // Generate a new random variable name + StringBuilder sb = getRandomName(); + var v = sb.toString(); + if (!generateValid && (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart)) { + maybeInvalid = true; + return v; + } + while (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart) { + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + v = sb.toString(); + } + return v; + } + + + + /** + * Generates a program and writes it into the string builder supplied in the constructor. + * @return If the program is allowed to be invalid returns if something potentially invalid was generated. + */ + public boolean genProgram() { + this.maybeInvalid = false; + variables.add(ScopeNode.ARG0); + currScopeStart = variables.size(); + if ((genStatements() & FLAG_STOP) == 0) { + if (generateValid || random.nextInt(10)<7) { + genReturn(); + } else { + this.maybeInvalid = true; + } + } + return !this.maybeInvalid; + } + + /** + * Generate a list of statements. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated + */ + public int genStatements() { + var num = random.nextInt(10); + for (int i=0; i<num; i++) { + printIndentation(); + var stop = genStatement(); + sb.append("\n"); + if ((stop & FLAG_STOP) != 0) return stop; + } + return 0; + } + + /** + * Generate a single statement + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genStatement() { + return switch (random.nextInt(10)) { + case 1 -> genBlock(); + case 2 -> genIf(); + case 3 -> genWhile(); + case 4, 5 -> genDecl(); + case 6, 7, 8 -> genAssignment(); + default -> genExit(); + }; + } + + /** + * Generate a statement for if, else and while blocks. + * This is special since it disallows declarations and prefers to generate blocks. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genStatementBlock() { + indentation += INDENTATION; + int res; + if (depth == 0) { + res = random.nextBoolean() ? genAssignment() : genExit(); + } else { + depth--; + res = switch (random.nextInt(10)) { + case 1, 2, 3, 4, 5 -> { + depth++; + indentation -= INDENTATION; + var ret = genBlock(); + indentation += INDENTATION; + depth--; + yield ret; + } + case 6 -> genIf(); + case 7 -> genWhile(); + case 8 -> genAssignment(); + default -> genExit(); + }; + depth++; + } + indentation -= INDENTATION; + return res; + } + + /** + * Generate an exit. This can be return or break and continue when in a loop. + * @return FLAG_STOP + */ + public int genExit() { + if (loopDepth == 0 && generateValid) return genReturn(); + return switch (random.nextInt(7)) { + case 0,1,2 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("continue;"); + yield FLAG_STOP; + } + case 3,4,5 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("break;"); + yield FLAG_STOP; + } + default -> genReturn(); + }; + } + + /** + * Generate a block statement. After a certain depth only empty blocks are generated to ensure termination of the generator. + * @return flag FLAG_STOP for the generated statement + */ + public int genBlock() { + if (depth == 0) { + sb.append("{}"); + return 0; + } + depth--; + int oldCSS = currScopeStart; + currScopeStart = variables.size(); + sb.append("{\n"); + indentation += INDENTATION; + var stop = genStatements(); + indentation -= INDENTATION; + printIndentation().append("}"); + while (variables.size() > currScopeStart) + variables.removeLast(); + currScopeStart = oldCSS; + depth++; + return stop & ~FLAG_IF_WITHOUT_ELSE; + } + + /** + * Generate an if statement with an optional else block. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genIf() { + sb.append("if("); + genExpression(); + sb.append(") "); + var stop = genStatementBlock(); + if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { + sb.append("\n"); + printIndentation().append("else "); + stop &= genStatementBlock(); + } else { + stop = FLAG_IF_WITHOUT_ELSE; + } + return stop; + } + + /** + * Generate a while loop. + * @return 0 + */ + public int genWhile() { + sb.append("while("); + genExpression(); + sb.append(") "); + loopDepth++; + genStatementBlock(); + loopDepth--; + return 0; + } + + /** + * Generate a declaration statement. + * @return 0 + */ + public int genDecl() { + String name = getVarName(); + sb.append("int ").append(name).append("="); + genExpression(); + sb.append(";"); + variables.add(name); + return 0; + } + + /** + * Generate an assignment statement. + * @return 0 + */ + public int genAssignment() { + if (variables.isEmpty()) return genDecl(); + genVariable(); + sb.append("="); + genExpression(); + sb.append(";"); + return 0; + } + + /** + * Generate a return statement. + * @return FLAG_STOP + */ + public int genReturn() { + sb.append("return "); + genExpression(); + sb.append(";"); + return FLAG_STOP; + } + + + /** + * Generate a binary expression. + * This method does not care about operator precedence. + */ + public void genExpression() { + var num = randLog(10); + while(num-->0) { + genUnary(); + sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); + } + genUnary(); + } + + /** + * Generate a unary expression. + */ + public void genUnary() { + var num = randLog(6); + while(num-->0) { + sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); + } + genPrimary(); + } + + /** + * Generate a primary expression. + */ + public void genPrimary() { + switch (random.nextInt(10)) { + case 0: + sb.append("true"); + break; + case 1: + sb.append("false"); + break; + case 2: + if (exprDepth == 0) { + // Ensure termination of the generator. + if (random.nextBoolean()) { + genNumber(); + } else { + genVariable(); + } + } else { + sb.append("("); + exprDepth--; + genExpression(); + exprDepth++; + sb.append(")"); + } + break; + case 3, 4, 5, 6: + genNumber(); + break; + default: + genVariable(); + } + } + + /** + * Generate a number. + */ + public void genNumber() { + sb.append(random.nextInt(100)); + } + + /** + * Generate a variable. If there are none generate a number instead. + * If the program is allowed to be invalid a random name can be generated in some cases. + */ + public void genVariable() { + if (!generateValid && random.nextInt(100)>97) { + sb.append(getRandomName()); + maybeInvalid = true; + return; + } + if (variables.isEmpty()) { + genNumber(); + } else { + sb.append(variables.get(random.nextInt(variables.size()))); + } + } + +} |
