diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/chapter08/08-grammar.md | 98 | ||||
| -rw-r--r-- | docs/chapter08/08-graph1.gv | 107 | ||||
| -rw-r--r-- | docs/chapter08/08-graph1.svg | 359 | ||||
| -rw-r--r-- | docs/chapter08/08-graph2.gv | 103 | ||||
| -rw-r--r-- | docs/chapter08/08-graph2.svg | 332 | ||||
| -rw-r--r-- | docs/chapter08/08-graph3.gv | 111 | ||||
| -rw-r--r-- | docs/chapter08/08-graph3.svg | 386 | ||||
| -rw-r--r-- | docs/chapter08/Makefile | 12 | ||||
| -rw-r--r-- | docs/chapter08/README.md | 296 |
9 files changed, 1804 insertions, 0 deletions
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..87559494 --- /dev/null +++ b/docs/chapter08/README.md @@ -0,0 +1,296 @@ +# Chapter 8: Lazy Phis, Break, Continue, and Evaluator + +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. + +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. + +## 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. |
