diff options
| author | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2023-12-03 23:23:04 +0000 |
|---|---|---|
| committer | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2026-08-10 11:11:18 -0700 |
| commit | 43d3ee3722dc08d87f787cd6eae75cc0359af621 (patch) | |
| tree | b85dec25dafde51957d17d849f7e6e3426a32d9c | |
| parent | bacc96cb93d078034390be678f8b986149d540ee (diff) | |
| download | Simple-43d3ee3722dc08d87f787cd6eae75cc0359af621.tar.gz Simple-43d3ee3722dc08d87f787cd6eae75cc0359af621.zip | |
Chapter 7: While Statement
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
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>
37 files changed, 2615 insertions, 134 deletions
@@ -48,7 +48,7 @@ The Simple language is styled after a subset of C or Java. simplifications. * [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. * [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow. -* Chapter 7: `while` statement; looping constructs - eager phi approach. +* [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 9: Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * Chapter 10: User defined Struct types. Memory effects: diff --git a/docs/chapter07/07-grammar.md b/docs/chapter07/07-grammar.md new file mode 100644 index 00000000..29a730b6 --- /dev/null +++ b/docs/chapter07/07-grammar.md @@ -0,0 +1,88 @@ +# Grammar for Chapter 6 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | metaStatement + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +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/chapter07/07-graph1.gv b/docs/chapter07/07-graph1.gv new file mode 100644 index 00000000..ba806a28 --- /dev/null +++ b/docs/chapter07/07-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter07 { +/* +while(arg < 10) { + arg = arg + 1; + #showGraph; +} +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>> + ]; + 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="+" ]; + { rank=same; Loop6;Phi_arg8;} + } + node [shape=plaintext]; + subgraph cluster_Scope7_1 { + Scope7_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">2</TD></TR> + </TABLE>>]; + subgraph cluster_Scope7_2 { + Scope7_2 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD></TR> + </TABLE>>]; + subgraph cluster_Scope7_3 { + Scope7_3 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope7_3_$ctrl">$ctrl</TD><TD PORT="Scope7_3_arg">arg</TD></TR> + </TABLE>>]; + } + } + } + node [shape=plaintext]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_2 { + Scope1_2 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_2_$ctrl">$ctrl</TD><TD PORT="Scope1_2_arg">arg</TD></TR> + </TABLE>>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope14_1 { + Scope14_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD></TR> + </TABLE>>]; + subgraph cluster_Scope14_2 { + Scope14_2 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope14_2_$ctrl">$ctrl</TD><TD PORT="Scope14_2_arg">arg</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + 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]; + edge [style=dashed color=cornflowerblue]; + Scope7_3:"Scope7_3_$ctrl" -> If11:p0; + Scope7_3:"Scope7_3_arg" -> Add16; + edge [style=dashed color=cornflowerblue]; + Scope1_2:"Scope1_2_$ctrl" -> Loop6; + Scope1_2:"Scope1_2_arg" -> Phi_arg8; + edge [style=dashed color=cornflowerblue]; + Scope14_2:"Scope14_2_$ctrl" -> If11:p1; + Scope14_2:"Scope14_2_arg" -> Phi_arg8; +} diff --git a/docs/chapter07/07-graph1.svg b/docs/chapter07/07-graph1.svg new file mode 100644 index 00000000..94248cfb --- /dev/null +++ b/docs/chapter07/07-graph1.svg @@ -0,0 +1,268 @@ +<?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: chapter07 Pages: 1 --> +<svg width="726pt" height="440pt" + viewBox="0.00 0.00 726.00 440.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 436)"> +<title>chapter07</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-436 722,-436 722,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="196,-100 196,-424 502,-424 502,-100 196,-100"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope7_1</title> +<polygon fill="none" stroke="black" points="8,-8 8,-92 288,-92 288,-8 8,-8"/> +</g> +<g id="clust4" class="cluster"> +<title>cluster_Scope7_2</title> +<polygon fill="none" stroke="black" points="80,-16 80,-84 280,-84 280,-16 80,-16"/> +</g> +<g id="clust5" class="cluster"> +<title>cluster_Scope7_3</title> +<polygon fill="none" stroke="black" points="152,-24 152,-76 272,-76 272,-24 152,-24"/> +</g> +<g id="clust6" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="black" points="510,-192 510,-260 710,-260 710,-192 510,-192"/> +</g> +<g id="clust7" class="cluster"> +<title>cluster_Scope1_2</title> +<polygon fill="none" stroke="black" points="582,-200 582,-252 702,-252 702,-200 582,-200"/> +</g> +<g id="clust8" class="cluster"> +<title>cluster_Scope14_1</title> +<polygon fill="none" stroke="black" points="296,-16 296,-84 496,-84 496,-16 296,-16"/> +</g> +<g id="clust9" class="cluster"> +<title>cluster_Scope14_2</title> +<polygon fill="none" stroke="black" points="368,-24 368,-76 488,-76 488,-24 368,-24"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="365,-387 365,-412 446,-412 446,-387 365,-387"/> +<polygon fill="none" stroke="black" points="365,-387 365,-412 446,-412 446,-387 365,-387"/> +<text text-anchor="start" x="387" y="-395.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="365,-356 365,-387 446,-387 446,-356 365,-356"/> +<polygon fill="yellow" stroke="transparent" points="370,-361 370,-382 410,-382 410,-361 370,-361"/> +<polygon fill="none" stroke="black" points="370,-361 370,-382 410,-382 410,-361 370,-361"/> +<text text-anchor="start" x="373" y="-367.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="410,-361 410,-382 441,-382 441,-361 410,-361"/> +<text text-anchor="start" x="413" y="-367.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Loop6 --> +<g id="node2" class="node"> +<title>Loop6</title> +<polygon fill="yellow" stroke="black" points="494,-316 440,-316 440,-280 494,-280 494,-316"/> +<text text-anchor="middle" x="467" y="-294.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop6->Start2 --> +<g id="edge1" class="edge"> +<title>Loop6->Start2:p0</title> +<path fill="none" stroke="red" d="M439.64,-314.34C422.52,-324.68 402.19,-338.54 393.85,-350.32"/> +<polygon fill="red" stroke="red" points="390.45,-349.41 390,-360 396.95,-352 390.45,-349.41"/> +<text text-anchor="middle" x="436.64" y="-307.94" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8 --> +<g id="node3" class="node"> +<title>Phi_arg8</title> +<ellipse fill="lightyellow" stroke="black" cx="385" cy="-298" rx="37.09" ry="18"/> +<text text-anchor="middle" x="385" y="-294.3" font-family="Times,serif" font-size="14.00">φ_arg</text> +</g> +<!-- Phi_arg8->Start2 --> +<g id="edge3" class="edge"> +<title>Phi_arg8->Start2:p1</title> +<path fill="none" stroke="black" d="M402.63,-314.22C411.57,-323.35 421.25,-335.86 424.7,-349.71"/> +<polygon fill="black" stroke="black" points="421.27,-350.52 426,-360 428.22,-349.64 421.27,-350.52"/> +<text text-anchor="middle" x="399.63" y="-316.82" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_arg8->Loop6 --> +<g id="edge2" class="edge"> +<title>Phi_arg8->Loop6</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M422.16,-298C424.62,-298 427.08,-298 429.55,-298"/> +<polygon fill="black" stroke="black" points="429.67,-301.5 439.67,-298 429.67,-294.5 429.67,-301.5"/> +<text text-anchor="middle" x="425.16" y="-291.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_9 --> +<g id="node4" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="black" cx="303" cy="-298" rx="27" ry="18"/> +<text text-anchor="middle" x="303" y="-294.3" font-family="Times,serif" font-size="14.00">10</text> +</g> +<!-- LT10 --> +<g id="node5" class="node"> +<title>LT10</title> +<ellipse fill="none" stroke="black" cx="374" cy="-226" rx="27" ry="18"/> +<text text-anchor="middle" x="374" y="-222.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT10->Phi_arg8 --> +<g id="edge4" class="edge"> +<title>LT10->Phi_arg8</title> +<path fill="none" stroke="black" d="M376.66,-243.95C377.87,-251.65 379.34,-260.97 380.7,-269.64"/> +<polygon fill="black" stroke="black" points="377.28,-270.39 382.29,-279.72 384.19,-269.3 377.28,-270.39"/> +<text text-anchor="middle" x="373.66" y="-246.55" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT10->Con_9 --> +<g id="edge5" class="edge"> +<title>LT10->Con_9</title> +<path fill="none" stroke="black" d="M359.29,-241.5C349.39,-251.27 336.16,-264.31 325.01,-275.3"/> +<polygon fill="black" stroke="black" points="322.36,-273 317.69,-282.51 327.27,-277.99 322.36,-273"/> +<text text-anchor="middle" x="356.29" y="-244.1" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If11 --> +<g id="node6" class="node"> +<title>If11</title> +<polygon fill="yellow" stroke="transparent" points="327,-143 327,-168 421,-168 421,-143 327,-143"/> +<polygon fill="none" stroke="black" points="327,-143 327,-168 421,-168 421,-143 327,-143"/> +<text text-anchor="start" x="368.5" y="-151.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="327,-112 327,-143 421,-143 421,-112 327,-112"/> +<polygon fill="yellow" stroke="transparent" points="332,-117 332,-138 372,-138 372,-117 332,-117"/> +<polygon fill="none" stroke="black" points="332,-117 332,-138 372,-138 372,-117 332,-117"/> +<text text-anchor="start" x="335" y="-123.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="372,-117 372,-138 416,-138 416,-117 372,-117"/> +<polygon fill="none" stroke="black" points="372,-117 372,-138 416,-138 416,-117 372,-117"/> +<text text-anchor="start" x="375" y="-123.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If11->Loop6 --> +<g id="edge6" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M396.87,-172.17C401.36,-178.63 405.94,-185.46 410,-192 426.23,-218.13 442.79,-249.22 453.84,-270.75"/> +<polygon fill="red" stroke="red" points="450.85,-272.6 458.51,-279.92 457.09,-269.42 450.85,-272.6"/> +<text text-anchor="middle" x="393.87" y="-174.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If11->LT10 --> +<g id="edge7" class="edge"> +<title>If11->LT10</title> +<path fill="none" stroke="black" d="M374,-172.28C374,-180.58 374,-189.48 374,-197.56"/> +<polygon fill="black" stroke="black" points="370.5,-197.6 374,-207.6 377.5,-197.6 370.5,-197.6"/> +<text text-anchor="middle" x="371" y="-174.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_15 --> +<g id="node7" class="node"> +<title>Con_15</title> +<ellipse fill="none" stroke="black" cx="231" cy="-298" rx="27" ry="18"/> +<text text-anchor="middle" x="231" y="-294.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add16 --> +<g id="node8" class="node"> +<title>Add16</title> +<ellipse fill="none" stroke="black" cx="241" cy="-226" rx="27" ry="18"/> +<text text-anchor="middle" x="241" y="-222.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add16->Phi_arg8 --> +<g id="edge8" class="edge"> +<title>Add16->Phi_arg8</title> +<path fill="none" stroke="black" d="M262.25,-237.33C285.48,-248.62 323.06,-266.89 350.53,-280.24"/> +<polygon fill="black" stroke="black" points="349.26,-283.52 359.78,-284.74 352.32,-277.22 349.26,-283.52"/> +<text text-anchor="middle" x="265.25" y="-239.93" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add16->Con_15 --> +<g id="edge9" class="edge"> +<title>Add16->Con_15</title> +<path fill="none" stroke="black" d="M238.58,-243.95C237.48,-251.65 236.15,-260.97 234.91,-269.64"/> +<polygon fill="black" stroke="black" points="231.42,-269.33 233.47,-279.72 238.35,-270.32 231.42,-269.33"/> +<text text-anchor="middle" x="235.58" y="-246.55" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Scope7_1 --> +<g id="node9" class="node"> +<title>Scope7_1</title> +<polygon fill="cyan" stroke="transparent" points="35,-39 35,-60 51,-60 51,-39 35,-39"/> +<polygon fill="none" stroke="black" points="35,-39 35,-60 51,-60 51,-39 35,-39"/> +<text text-anchor="start" x="38" y="-45.8" font-family="Times,serif" font-size="14.00">2</text> +</g> +<!-- Scope7_2 --> +<g id="node10" class="node"> +<title>Scope7_2</title> +<polygon fill="cyan" stroke="transparent" points="107,-39 107,-60 123,-60 123,-39 107,-39"/> +<polygon fill="none" stroke="black" points="107,-39 107,-60 123,-60 123,-39 107,-39"/> +<text text-anchor="start" x="110" y="-45.8" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Scope7_3 --> +<g id="node11" class="node"> +<title>Scope7_3</title> +<polygon fill="cyan" stroke="transparent" points="169,-39 169,-60 185,-60 185,-39 169,-39"/> +<polygon fill="none" stroke="black" points="169,-39 169,-60 185,-60 185,-39 169,-39"/> +<text text-anchor="start" x="172" y="-45.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="185,-39 185,-60 225,-60 225,-39 185,-39"/> +<text text-anchor="start" x="188" y="-45.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="225,-39 225,-60 256,-60 256,-39 225,-39"/> +<text text-anchor="start" x="228" y="-45.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope7_3->If11 --> +<g id="edge10" class="edge"> +<title>Scope7_3:Scope7_3_$ctrl->If11:p0</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M205,-61C205,-74.83 289.37,-114.99 321.05,-124.81"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="320.48,-128.27 331,-127 321.98,-121.43 320.48,-128.27"/> +</g> +<!-- Scope7_3->Add16 --> +<g id="edge11" class="edge"> +<title>Scope7_3:Scope7_3_arg->Add16</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M241,-61C241,-109.09 241,-165.12 241,-197.67"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="237.5,-197.76 241,-207.76 244.5,-197.76 237.5,-197.76"/> +</g> +<!-- Scope1_1 --> +<g id="node12" class="node"> +<title>Scope1_1</title> +<polygon fill="cyan" stroke="transparent" points="537,-215 537,-236 553,-236 553,-215 537,-215"/> +<polygon fill="none" stroke="black" points="537,-215 537,-236 553,-236 553,-215 537,-215"/> +<text text-anchor="start" x="540" y="-221.8" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Scope1_2 --> +<g id="node13" class="node"> +<title>Scope1_2</title> +<polygon fill="cyan" stroke="transparent" points="599,-215 599,-236 615,-236 615,-215 599,-215"/> +<polygon fill="none" stroke="black" points="599,-215 599,-236 615,-236 615,-215 599,-215"/> +<text text-anchor="start" x="602" y="-221.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="615,-215 615,-236 655,-236 655,-215 615,-215"/> +<text text-anchor="start" x="618" y="-221.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="655,-215 655,-236 686,-236 686,-215 655,-215"/> +<text text-anchor="start" x="658" y="-221.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope1_2->Loop6 --> +<g id="edge12" class="edge"> +<title>Scope1_2:Scope1_2_$ctrl->Loop6</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M635,-237C635,-264.54 553.92,-282.77 504.41,-291.34"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="503.65,-287.92 494.37,-293.02 504.81,-294.82 503.65,-287.92"/> +</g> +<!-- Scope1_2->Phi_arg8 --> +<g id="edge13" class="edge"> +<title>Scope1_2:Scope1_2_arg->Phi_arg8</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M671,-237C671,-275.71 624.96,-252.41 587,-260 518.46,-273.71 498.88,-263.33 431,-280 428.04,-280.73 425,-281.58 421.97,-282.52"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="420.79,-279.23 412.41,-285.72 423.01,-285.86 420.79,-279.23"/> +</g> +<!-- Scope14_1 --> +<g id="node14" class="node"> +<title>Scope14_1</title> +<polygon fill="cyan" stroke="transparent" points="323,-39 323,-60 339,-60 339,-39 323,-39"/> +<polygon fill="none" stroke="black" points="323,-39 323,-60 339,-60 339,-39 323,-39"/> +<text text-anchor="start" x="326" y="-45.8" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Scope14_2 --> +<g id="node15" class="node"> +<title>Scope14_2</title> +<polygon fill="cyan" stroke="transparent" points="385,-39 385,-60 401,-60 401,-39 385,-39"/> +<polygon fill="none" stroke="black" points="385,-39 385,-60 401,-60 401,-39 385,-39"/> +<text text-anchor="start" x="388" y="-45.8" font-family="Times,serif" font-size="14.00">0</text> +<polygon fill="none" stroke="black" points="401,-39 401,-60 441,-60 441,-39 401,-39"/> +<text text-anchor="start" x="404" y="-45.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="441,-39 441,-60 472,-60 472,-39 441,-39"/> +<text text-anchor="start" x="444" y="-45.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Scope14_2->Phi_arg8 --> +<g id="edge15" class="edge"> +<title>Scope14_2:Scope14_2_arg->Phi_arg8</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M457,-61C457,-151.88 449.62,-178.21 410,-260 408.01,-264.11 405.61,-268.3 403.09,-272.3"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="400.15,-270.4 397.51,-280.67 405.97,-274.28 400.15,-270.4"/> +</g> +<!-- Scope14_2->If11 --> +<g id="edge14" class="edge"> +<title>Scope14_2:Scope14_2_$ctrl->If11:p1</title> +<path fill="none" stroke="cornflowerblue" stroke-dasharray="5,2" d="M421,-61C421,-84.4 401.06,-88.09 395.45,-105.95"/> +<polygon fill="cornflowerblue" stroke="cornflowerblue" points="391.97,-105.6 394,-116 398.89,-106.6 391.97,-105.6"/> +</g> +</g> +</svg> diff --git a/docs/chapter07/07-graph2.gv b/docs/chapter07/07-graph2.gv new file mode 100644 index 00000000..f4cfcb45 --- /dev/null +++ b/docs/chapter07/07-graph2.gv @@ -0,0 +1,62 @@ +digraph chapter07 { +/* +while(arg < 10) { + arg = arg + 1; + #showGraph; +} +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="+" ]; + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + } + node [shape=plaintext]; + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return17[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> If11:p0[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]; + Return17 -> If11:p1[taillabel=0 color=red]; + Return17 -> Phi_arg8[taillabel=1]; + edge [style=dashed color=cornflowerblue]; +}
\ No newline at end of file diff --git a/docs/chapter07/07-graph2.svg b/docs/chapter07/07-graph2.svg new file mode 100644 index 00000000..1fec9556 --- /dev/null +++ b/docs/chapter07/07-graph2.svg @@ -0,0 +1,184 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter07 Pages: 1 --> +<svg width="330pt" height="492pt" + viewBox="0.00 0.00 330.00 492.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 488)"> +<title>chapter07</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-488 326,-488 326,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-476 314,-476 314,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="141,-439 141,-464 222,-464 222,-439 141,-439"/> +<polygon fill="none" stroke="black" points="141,-439 141,-464 222,-464 222,-439 141,-439"/> +<text text-anchor="start" x="163" y="-447.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="141,-408 141,-439 222,-439 222,-408 141,-408"/> +<polygon fill="yellow" stroke="transparent" points="146,-413 146,-434 186,-434 186,-413 146,-413"/> +<polygon fill="none" stroke="black" points="146,-413 146,-434 186,-434 186,-413 146,-413"/> +<text text-anchor="start" x="149" y="-419.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="186,-413 186,-434 217,-434 217,-413 186,-413"/> +<text text-anchor="start" x="189" y="-419.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="153,-52 99,-52 99,-16 153,-16 153,-52"/> +<text text-anchor="middle" x="126" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return17 --> +<g id="node10" class="node"> +<title>Return17</title> +<polygon fill="yellow" stroke="black" points="159,-124 93,-124 93,-88 159,-88 159,-124"/> +<text text-anchor="middle" x="126" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return17 --> +<g id="edge1" class="edge"> +<title>Stop3->Return17</title> +<path fill="none" stroke="red" d="M126,-52.3C126,-60.02 126,-69.29 126,-77.89"/> +<polygon fill="red" stroke="red" points="122.5,-77.9 126,-87.9 129.5,-77.9 122.5,-77.9"/> +<text text-anchor="middle" x="123" 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="306,-368 252,-368 252,-332 306,-332 306,-368"/> +<text text-anchor="middle" x="279" y="-346.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="M251.93,-364.13C226.34,-376.71 189.56,-395.24 173.73,-405.41"/> +<polygon fill="red" stroke="red" points="171.34,-402.85 166,-412 175.88,-408.18 171.34,-402.85"/> +<text text-anchor="middle" x="248.93" y="-357.73" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If11 --> +<g id="node7" class="node"> +<title>If11</title> +<polygon fill="yellow" stroke="transparent" points="32,-195 32,-220 126,-220 126,-195 32,-195"/> +<polygon fill="none" stroke="black" points="32,-195 32,-220 126,-220 126,-195 32,-195"/> +<text text-anchor="start" x="73.5" y="-203.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="32,-164 32,-195 126,-195 126,-164 32,-164"/> +<polygon fill="yellow" stroke="transparent" points="37,-169 37,-190 77,-190 77,-169 37,-169"/> +<polygon fill="none" stroke="black" points="37,-169 37,-190 77,-190 77,-169 37,-169"/> +<text text-anchor="start" x="40" y="-175.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="77,-169 77,-190 121,-190 121,-169 77,-169"/> +<polygon fill="none" stroke="black" points="77,-169 77,-190 121,-190 121,-169 77,-169"/> +<text text-anchor="start" x="80" y="-175.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- Loop6->If11 --> +<g id="edge3" class="edge"> +<title>Loop6->If11:p0</title> +<path fill="none" stroke="red" d="M251.78,-335.24C248.86,-334.04 245.9,-332.93 243,-332 156.98,-304.48 103.76,-362.82 43,-296 18.41,-268.96 14.64,-203.69 27.49,-184.44"/> +<polygon fill="red" stroke="red" points="29.46,-187.33 36,-179 25.69,-181.43 29.46,-187.33"/> +<text text-anchor="middle" x="248.78" y="-328.84" 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="-350" rx="37.09" ry="18"/> +<text text-anchor="middle" x="125" y="-346.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="M154.55,-360.93C173.21,-369 194.84,-382.27 200.56,-401.87"/> +<polygon fill="black" stroke="black" points="197.12,-402.59 202,-412 204.05,-401.61 197.12,-402.59"/> +<text text-anchor="middle" x="151.55" y="-363.53" 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="M143.47,-334.01C153.54,-326.34 166.66,-317.98 180,-314 203,-307.14 211.35,-306.06 234,-314 241.14,-316.5 247.99,-320.67 254.09,-325.3"/> +<polygon fill="black" stroke="black" points="251.99,-328.1 261.92,-331.78 256.45,-322.71 251.99,-328.1"/> +<text text-anchor="middle" x="140.47" y="-327.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="203" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="203" y="-274.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="43" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-346.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="79" cy="-278" rx="27" ry="18"/> +<text text-anchor="middle" x="79" y="-274.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="M89.44,-294.88C95.12,-303.53 102.28,-314.42 108.68,-324.17"/> +<polygon fill="black" stroke="black" points="105.87,-326.26 114.28,-332.69 111.72,-322.41 105.87,-326.26"/> +<text text-anchor="middle" x="86.44" y="-297.48" 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="M70.65,-295.24C66.29,-303.72 60.85,-314.29 55.96,-323.8"/> +<polygon fill="black" stroke="black" points="52.77,-322.36 51.3,-332.85 58.99,-325.56 52.77,-322.36"/> +<text text-anchor="middle" x="67.65" y="-297.84" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If11->Loop6 --> +<g id="edge9" class="edge"> +<title>If11->Loop6</title> +<path fill="none" stroke="red" d="M134.07,-205.07C167.93,-214.93 210.21,-231.94 239,-260 256.28,-276.84 266.71,-302.48 272.57,-321.93"/> +<polygon fill="red" stroke="red" points="269.24,-323.03 275.3,-331.72 275.98,-321.15 269.24,-323.03"/> +<text text-anchor="middle" x="137.07" y="-198.67" 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="M79,-224.28C79,-232.58 79,-241.48 79,-249.56"/> +<polygon fill="black" stroke="black" points="75.5,-249.6 79,-259.6 82.5,-249.6 75.5,-249.6"/> +<text text-anchor="middle" x="76" y="-226.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="207" cy="-350" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-346.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="M180.01,-299.63C170.41,-308.25 159.23,-318.28 149.47,-327.04"/> +<polygon fill="black" stroke="black" points="182.48,-302.11 187.59,-292.83 177.81,-296.9 182.48,-302.11"/> +<polygon fill="black" stroke="black" points="147.11,-324.46 142,-333.74 151.78,-329.67 147.11,-324.46"/> +<text text-anchor="middle" x="184.59" y="-295.43" 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="M203.99,-296.3C204.43,-304.02 204.96,-313.29 205.45,-321.89"/> +<polygon fill="black" stroke="black" points="201.96,-322.11 206.02,-331.9 208.95,-321.71 201.96,-322.11"/> +<text text-anchor="middle" x="200.99" y="-298.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return17->Phi_arg8 --> +<g id="edge14" class="edge"> +<title>Return17->Phi_arg8</title> +<path fill="none" stroke="black" d="M133.07,-124.33C136.84,-134.53 141.09,-147.78 143,-160 151.97,-217.35 140.08,-285.24 131.79,-322.03"/> +<polygon fill="black" stroke="black" points="128.33,-321.44 129.46,-331.97 135.14,-323.03 128.33,-321.44"/> +<text text-anchor="middle" x="130.07" y="-126.93" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return17->If11 --> +<g id="edge13" class="edge"> +<title>Return17->If11:p1</title> +<path fill="none" stroke="red" d="M113.92,-124C108.25,-133.3 102.24,-145.44 99.95,-157.94"/> +<polygon fill="red" stroke="red" points="96.46,-157.71 99,-168 103.43,-158.38 96.46,-157.71"/> +<text text-anchor="middle" x="110.92" y="-126.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +</g> +</svg> diff --git a/docs/chapter07/07-graph3.gv b/docs/chapter07/07-graph3.gv new file mode 100644 index 00000000..4482100b --- /dev/null +++ b/docs/chapter07/07-graph3.gv @@ -0,0 +1,108 @@ +digraph chapter07 { +/* +int sum = 0; +int i = 0; +while(i < arg) { + i = i + 1; + int j = 0; + while( j < arg ) { + sum = sum + j; + j = j + 1; + } +} +return sum; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="0" ]; + Con_7 [ label="0" ]; + Loop8 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_sum11 [ style=filled fillcolor=lightyellow label="φ_sum" ]; + Phi_i12 [ style=filled fillcolor=lightyellow label="φ_i" ]; + LT13 [ label="<" ]; + If14 [ 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_18 [ label="1" ]; + Add19 [ label="+" ]; + Con_20 [ label="0" ]; + Loop21 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_sum24 [ style=filled fillcolor=lightyellow label="φ_sum" ]; + Phi_j26 [ style=filled fillcolor=lightyellow label="φ_j" ]; + LT27 [ 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>> + ]; + Add32 [ label="+" ]; + Con_33 [ label="1" ]; + Add34 [ label="+" ]; + Return35 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop8;Phi_sum11;Phi_i12;} + { rank=same; Loop21;Phi_sum24;Phi_j26;} + } + node [shape=plaintext]; + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return35[taillabel=0 color=red]; + Loop8 -> Start2:p0[taillabel=1 color=red]; + Loop8 -> If28:p1[taillabel=2 color=red constraint=false]; + Phi_sum11 -> Loop8 [style=dotted taillabel=0]; + Phi_sum11 -> Con_6[taillabel=1]; + Phi_sum11 -> Phi_sum24[taillabel=2 constraint=false]; + Phi_i12 -> Loop8 [style=dotted taillabel=0]; + Phi_i12 -> Con_7[taillabel=1]; + Phi_i12 -> Add19[taillabel=2 constraint=false]; + LT13 -> Phi_i12[taillabel=1]; + LT13 -> Start2:p1[taillabel=2]; + If14 -> Loop8[taillabel=0 color=red]; + If14 -> LT13[taillabel=1]; + Add19 -> Phi_i12[taillabel=1]; + Add19 -> Con_18[taillabel=2]; + Loop21 -> If14:p0[taillabel=1 color=red]; + Loop21 -> If28:p0[taillabel=2 color=red constraint=false]; + Phi_sum24 -> Loop21 [style=dotted taillabel=0]; + Phi_sum24 -> Phi_sum11[taillabel=1]; + Phi_sum24 -> Add32[taillabel=2 constraint=false]; + Phi_j26 -> Loop21 [style=dotted taillabel=0]; + Phi_j26 -> Con_20[taillabel=1]; + Phi_j26 -> Add34[taillabel=2 constraint=false]; + LT27 -> Phi_j26[taillabel=1]; + LT27 -> Start2:p1[taillabel=2]; + If28 -> Loop21[taillabel=0 color=red]; + If28 -> LT27[taillabel=1]; + Add32 -> Phi_j26[taillabel=1]; + Add32 -> Phi_sum24[taillabel=2]; + Add34 -> Phi_j26[taillabel=1]; + Add34 -> Con_33[taillabel=2]; + Return35 -> If14:p1[taillabel=0 color=red]; + Return35 -> Phi_sum11[taillabel=1]; + edge [style=dashed color=cornflowerblue]; +}
\ No newline at end of file diff --git a/docs/chapter07/07-graph3.svg b/docs/chapter07/07-graph3.svg new file mode 100644 index 00000000..a9a0e8d0 --- /dev/null +++ b/docs/chapter07/07-graph3.svg @@ -0,0 +1,373 @@ +<?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: chapter07 Pages: 1 --> +<svg width="462pt" height="592pt" + viewBox="0.00 0.00 462.00 592.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 588)"> +<title>chapter07</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-588 458,-588 458,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-576 446,-576 446,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="148,-539 148,-564 229,-564 229,-539 148,-539"/> +<polygon fill="none" stroke="black" points="148,-539 148,-564 229,-564 229,-539 148,-539"/> +<text text-anchor="start" x="170" y="-547.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="148,-508 148,-539 229,-539 229,-508 148,-508"/> +<polygon fill="yellow" stroke="transparent" points="153,-513 153,-534 193,-534 193,-513 153,-513"/> +<polygon fill="none" stroke="black" points="153,-513 153,-534 193,-534 193,-513 153,-513"/> +<text text-anchor="start" x="156" y="-519.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="193,-513 193,-534 224,-534 224,-513 193,-513"/> +<text text-anchor="start" x="196" y="-519.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="432,-152 378,-152 378,-116 432,-116 432,-152"/> +<text text-anchor="middle" x="405" y="-130.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return35 --> +<g id="node21" class="node"> +<title>Return35</title> +<polygon fill="yellow" stroke="black" points="438,-224 372,-224 372,-188 438,-188 438,-224"/> +<text text-anchor="middle" x="405" y="-202.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return35 --> +<g id="edge1" class="edge"> +<title>Stop3->Return35</title> +<path fill="none" stroke="red" d="M405,-152.3C405,-160.02 405,-169.29 405,-177.89"/> +<polygon fill="red" stroke="red" points="401.5,-177.9 405,-187.9 408.5,-177.9 401.5,-177.9"/> +<text text-anchor="middle" x="402" y="-154.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="94" cy="-536" rx="27" ry="18"/> +<text text-anchor="middle" x="94" y="-532.3" font-family="Times,serif" font-size="14.00">0</text> +</g> +<!-- Con_7 --> +<g id="node4" class="node"> +<title>Con_7</title> +<ellipse fill="none" stroke="black" cx="282" cy="-536" rx="27" ry="18"/> +<text text-anchor="middle" x="282" y="-532.3" font-family="Times,serif" font-size="14.00">0</text> +</g> +<!-- Loop8 --> +<g id="node5" class="node"> +<title>Loop8</title> +<polygon fill="yellow" stroke="black" points="426,-468 372,-468 372,-432 426,-432 426,-468"/> +<text text-anchor="middle" x="399" y="-446.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop8->Start2 --> +<g id="edge2" class="edge"> +<title>Loop8->Start2:p0</title> +<path fill="none" stroke="red" d="M371.74,-464.61C368.82,-465.84 365.87,-467 363,-468 325.58,-481 197.82,-470.79 176.14,-502.03"/> +<polygon fill="red" stroke="red" points="172.67,-501.41 173,-512 179.34,-503.51 172.67,-501.41"/> +<text text-anchor="middle" x="368.74" y="-458.21" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If28 --> +<g id="node17" class="node"> +<title>If28</title> +<polygon fill="yellow" stroke="transparent" points="142,-51 142,-76 236,-76 236,-51 142,-51"/> +<polygon fill="none" stroke="black" points="142,-51 142,-76 236,-76 236,-51 142,-51"/> +<text text-anchor="start" x="183.5" y="-59.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="142,-20 142,-51 236,-51 236,-20 142,-20"/> +<polygon fill="yellow" stroke="transparent" points="147,-25 147,-46 187,-46 187,-25 147,-25"/> +<polygon fill="none" stroke="black" points="147,-25 147,-46 187,-46 187,-25 147,-25"/> +<text text-anchor="start" x="150" y="-31.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="187,-25 187,-46 231,-46 231,-25 187,-25"/> +<polygon fill="none" stroke="black" points="187,-25 187,-46 231,-46 231,-25 187,-25"/> +<text text-anchor="start" x="190" y="-31.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- Loop8->If28 --> +<g id="edge3" class="edge"> +<title>Loop8->If28:p1</title> +<path fill="none" stroke="red" d="M371.72,-435.44C368.81,-434.2 365.86,-433.02 363,-432 300.87,-409.81 259.6,-448 219,-396 176.78,-341.93 243.11,-308.12 292,-260 311.77,-240.54 330.24,-248.63 343,-224 350.36,-209.79 353.65,-199.94 343,-188 248.88,-82.54 121.12,-257.46 27,-152 16.35,-140.06 16.65,-128.2 27,-116 90.22,-41.43 180.78,-154.57 244,-80 259.81,-61.35 261.04,-42.53 244,-25 236.29,-17.07 221.85,-12.04 214.15,-15.39"/> +<polygon fill="red" stroke="red" points="211.13,-13.62 209,-24 217.14,-17.22 211.13,-13.62"/> +<text text-anchor="middle" x="368.72" y="-429.04" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_sum11 --> +<g id="node6" class="node"> +<title>Phi_sum11</title> +<ellipse fill="lightyellow" stroke="black" cx="149" cy="-450" rx="40.89" ry="18"/> +<text text-anchor="middle" x="149" y="-446.3" font-family="Times,serif" font-size="14.00">φ_sum</text> +</g> +<!-- Phi_sum11->Con_6 --> +<g id="edge5" class="edge"> +<title>Phi_sum11->Con_6</title> +<path fill="none" stroke="black" d="M138.13,-467.6C130.07,-479.91 118.95,-496.89 109.89,-510.73"/> +<polygon fill="black" stroke="black" points="106.84,-509.01 104.29,-519.29 112.69,-512.84 106.84,-509.01"/> +<text text-anchor="middle" x="135.13" y="-470.2" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_sum11->Loop8 --> +<g id="edge4" class="edge"> +<title>Phi_sum11->Loop8</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M173.66,-435.44C188.78,-427.38 208.85,-418.16 228,-414 282.73,-402.12 301.16,-395.46 354,-414 361.14,-416.5 367.99,-420.67 374.09,-425.3"/> +<polygon fill="black" stroke="black" points="371.99,-428.1 381.92,-431.78 376.45,-422.71 371.99,-428.1"/> +<text text-anchor="middle" x="170.66" y="-429.04" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Phi_sum24 --> +<g id="node14" class="node"> +<title>Phi_sum24</title> +<ellipse fill="lightyellow" stroke="black" cx="149" cy="-206" rx="40.89" ry="18"/> +<text text-anchor="middle" x="149" y="-202.3" font-family="Times,serif" font-size="14.00">φ_sum</text> +</g> +<!-- Phi_i12 --> +<g id="node7" class="node"> +<title>Phi_i12</title> +<ellipse fill="lightyellow" stroke="black" cx="255" cy="-450" rx="27" ry="18"/> +<text text-anchor="middle" x="255" y="-446.3" font-family="Times,serif" font-size="14.00">φ_i</text> +</g> +<!-- Phi_i12->Con_7 --> +<g id="edge8" class="edge"> +<title>Phi_i12->Con_7</title> +<path fill="none" stroke="black" d="M260.46,-468C264.22,-479.69 269.28,-495.44 273.56,-508.73"/> +<polygon fill="black" stroke="black" points="270.24,-509.86 276.64,-518.31 276.91,-507.72 270.24,-509.86"/> +<text text-anchor="middle" x="257.46" y="-470.6" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_i12->Loop8 --> +<g id="edge7" class="edge"> +<title>Phi_i12->Loop8</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M269.22,-434.43C277.37,-426.68 288.29,-418.11 300,-414 322.65,-406.06 331.35,-406.06 354,-414 361.14,-416.5 367.99,-420.67 374.09,-425.3"/> +<polygon fill="black" stroke="black" points="371.99,-428.1 381.92,-431.78 376.45,-422.71 371.99,-428.1"/> +<text text-anchor="middle" x="266.22" y="-428.03" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add19 --> +<g id="node11" class="node"> +<title>Add19</title> +<ellipse fill="none" stroke="black" cx="327" cy="-378" rx="27" ry="18"/> +<text text-anchor="middle" x="327" y="-374.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- LT13 --> +<g id="node8" class="node"> +<title>LT13</title> +<ellipse fill="none" stroke="black" cx="255" cy="-378" rx="27" ry="18"/> +<text text-anchor="middle" x="255" y="-374.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT13->Start2 --> +<g id="edge11" class="edge"> +<title>LT13->Start2:p1</title> +<path fill="none" stroke="black" d="M241.85,-394.14C233.87,-404.19 224.26,-418.05 219,-432 207.64,-462.12 208.62,-473.77 208.94,-501.81"/> +<polygon fill="black" stroke="black" points="205.44,-502.02 209,-512 212.44,-501.98 205.44,-502.02"/> +<text text-anchor="middle" x="238.85" y="-396.74" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- LT13->Phi_i12 --> +<g id="edge10" class="edge"> +<title>LT13->Phi_i12</title> +<path fill="none" stroke="black" d="M255,-396.3C255,-404.02 255,-413.29 255,-421.89"/> +<polygon fill="black" stroke="black" points="251.5,-421.9 255,-431.9 258.5,-421.9 251.5,-421.9"/> +<text text-anchor="middle" x="252" y="-398.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If14 --> +<g id="node9" class="node"> +<title>If14</title> +<polygon fill="yellow" stroke="transparent" points="309,-295 309,-320 403,-320 403,-295 309,-295"/> +<polygon fill="none" stroke="black" points="309,-295 309,-320 403,-320 403,-295 309,-295"/> +<text text-anchor="start" x="350.5" y="-303.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="309,-264 309,-295 403,-295 403,-264 309,-264"/> +<polygon fill="yellow" stroke="transparent" points="314,-269 314,-290 354,-290 354,-269 314,-269"/> +<polygon fill="none" stroke="black" points="314,-269 314,-290 354,-290 354,-269 314,-269"/> +<text text-anchor="start" x="317" y="-275.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="354,-269 354,-290 398,-290 398,-269 354,-269"/> +<polygon fill="none" stroke="black" points="354,-269 354,-290 398,-290 398,-269 354,-269"/> +<text text-anchor="start" x="357" y="-275.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If14->Loop8 --> +<g id="edge12" class="edge"> +<title>If14->Loop8</title> +<path fill="none" stroke="red" d="M364.6,-324.19C372.47,-352.77 384.02,-394.64 391.52,-421.86"/> +<polygon fill="red" stroke="red" points="388.24,-423.15 394.27,-431.86 394.99,-421.29 388.24,-423.15"/> +<text text-anchor="middle" x="361.6" y="-326.79" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If14->LT13 --> +<g id="edge13" class="edge"> +<title>If14->LT13</title> +<path fill="none" stroke="black" d="M318.68,-324.04C305.44,-335.05 290.9,-347.14 279.06,-356.99"/> +<polygon fill="black" stroke="black" points="276.79,-354.32 271.34,-363.41 281.27,-359.7 276.79,-354.32"/> +<text text-anchor="middle" x="315.68" y="-326.64" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_18 --> +<g id="node10" class="node"> +<title>Con_18</title> +<ellipse fill="none" stroke="black" cx="327" cy="-450" rx="27" ry="18"/> +<text text-anchor="middle" x="327" y="-446.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add19->Phi_i12 --> +<g id="edge14" class="edge"> +<title>Add19->Phi_i12</title> +<path fill="none" stroke="black" d="M304.96,-400.43C296.13,-409.01 285.99,-418.87 277.15,-427.46"/> +<polygon fill="black" stroke="black" points="307.7,-402.65 312.43,-393.17 302.82,-397.63 307.7,-402.65"/> +<polygon fill="black" stroke="black" points="274.53,-425.13 269.8,-434.62 279.41,-430.15 274.53,-425.13"/> +<text text-anchor="middle" x="309.43" y="-395.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add19->Con_18 --> +<g id="edge15" class="edge"> +<title>Add19->Con_18</title> +<path fill="none" stroke="black" d="M327,-396.3C327,-404.02 327,-413.29 327,-421.89"/> +<polygon fill="black" stroke="black" points="323.5,-421.9 327,-431.9 330.5,-421.9 323.5,-421.9"/> +<text text-anchor="middle" x="324" y="-398.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Con_20 --> +<g id="node12" class="node"> +<title>Con_20</title> +<ellipse fill="none" stroke="black" cx="63" cy="-292" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-288.3" font-family="Times,serif" font-size="14.00">0</text> +</g> +<!-- Loop21 --> +<g id="node13" class="node"> +<title>Loop21</title> +<polygon fill="yellow" stroke="black" points="334,-224 280,-224 280,-188 334,-188 334,-224"/> +<text text-anchor="middle" x="307" y="-202.3" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop21->If14 --> +<g id="edge16" class="edge"> +<title>Loop21->If14:p0</title> +<path fill="none" stroke="red" d="M319.08,-224C324.75,-233.3 330.76,-245.44 333.05,-257.94"/> +<polygon fill="red" stroke="red" points="329.57,-258.38 334,-268 336.54,-257.71 329.57,-258.38"/> +<text text-anchor="middle" x="316.08" y="-226.6" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Loop21->If28 --> +<g id="edge17" class="edge"> +<title>Loop21->If28:p0</title> +<path fill="none" stroke="red" d="M279.81,-191.15C276.88,-189.96 273.91,-188.88 271,-188 218.54,-172.13 62.82,-193.49 27,-152 -19.29,-98.38 63.73,-40.46 135.9,-35.36"/> +<polygon fill="red" stroke="red" points="136.13,-38.86 146,-35 135.88,-31.86 136.13,-38.86"/> +<text text-anchor="middle" x="276.81" y="-184.75" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_sum24->Phi_sum11 --> +<g id="edge19" class="edge"> +<title>Phi_sum24->Phi_sum11</title> +<path fill="none" stroke="black" d="M149,-234.1C149,-280.5 149,-374.66 149,-421.4"/> +<polygon fill="black" stroke="black" points="152.5,-234.02 149,-224.02 145.5,-234.02 152.5,-234.02"/> +<polygon fill="black" stroke="black" points="145.5,-421.68 149,-431.68 152.5,-421.68 145.5,-421.68"/> +<text text-anchor="middle" x="146" y="-226.62" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_sum24->Loop21 --> +<g id="edge18" class="edge"> +<title>Phi_sum24->Loop21</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M168.72,-190.18C179.62,-182.46 193.79,-173.99 208,-170 231.11,-163.51 239.35,-162.06 262,-170 269.14,-172.5 275.99,-176.67 282.09,-181.3"/> +<polygon fill="black" stroke="black" points="279.99,-184.1 289.92,-187.78 284.45,-178.71 279.99,-184.1"/> +<text text-anchor="middle" x="165.72" y="-183.78" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add32 --> +<g id="node18" class="node"> +<title>Add32</title> +<ellipse fill="none" stroke="black" cx="142" cy="-134" rx="27" ry="18"/> +<text text-anchor="middle" x="142" y="-130.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Phi_j26 --> +<g id="node15" class="node"> +<title>Phi_j26</title> +<ellipse fill="lightyellow" stroke="black" cx="63" cy="-206" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-202.3" font-family="Times,serif" font-size="14.00">φ_j</text> +</g> +<!-- Phi_j26->Con_20 --> +<g id="edge22" class="edge"> +<title>Phi_j26->Con_20</title> +<path fill="none" stroke="black" d="M63,-224.4C63,-235.74 63,-250.77 63,-263.68"/> +<polygon fill="black" stroke="black" points="59.5,-263.9 63,-273.9 66.5,-263.9 59.5,-263.9"/> +<text text-anchor="middle" x="60" y="-227" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_j26->Loop21 --> +<g id="edge21" class="edge"> +<title>Phi_j26->Loop21</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M77.22,-190.43C85.37,-182.68 96.29,-174.11 108,-170 172.59,-147.34 197.41,-147.34 262,-170 269.14,-172.5 275.99,-176.67 282.09,-181.3"/> +<polygon fill="black" stroke="black" points="279.99,-184.1 289.92,-187.78 284.45,-178.71 279.99,-184.1"/> +<text text-anchor="middle" x="74.22" y="-184.03" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add34 --> +<g id="node20" class="node"> +<title>Add34</title> +<ellipse fill="none" stroke="black" cx="225" cy="-134" rx="27" ry="18"/> +<text text-anchor="middle" x="225" y="-130.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- LT27 --> +<g id="node16" class="node"> +<title>LT27</title> +<ellipse fill="none" stroke="black" cx="63" cy="-134" rx="27" ry="18"/> +<text text-anchor="middle" x="63" y="-130.3" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT27->Start2 --> +<g id="edge25" class="edge"> +<title>LT27->Start2:p1</title> +<path fill="none" stroke="black" d="M49.72,-150.09C41.69,-160.12 32.07,-173.98 27,-188 11.37,-231.26 17,-245.01 17,-291 17,-291 17,-291 17,-379 17,-432.79 54.71,-437.48 99,-468 139.14,-495.66 199.24,-464.69 207.94,-501.72"/> +<polygon fill="black" stroke="black" points="204.49,-502.41 209,-512 211.45,-501.69 204.49,-502.41"/> +<text text-anchor="middle" x="46.72" y="-152.69" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- LT27->Phi_j26 --> +<g id="edge24" class="edge"> +<title>LT27->Phi_j26</title> +<path fill="none" stroke="black" d="M63,-152.3C63,-160.02 63,-169.29 63,-177.89"/> +<polygon fill="black" stroke="black" points="59.5,-177.9 63,-187.9 66.5,-177.9 59.5,-177.9"/> +<text text-anchor="middle" x="60" y="-154.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If28->Loop21 --> +<g id="edge26" class="edge"> +<title>If28->Loop21</title> +<path fill="none" stroke="red" d="M227.35,-80.17C239.01,-90.79 251.3,-103.21 261,-116 275.71,-135.38 288.07,-160.15 296.27,-178.63"/> +<polygon fill="red" stroke="red" points="293.1,-180.12 300.27,-187.92 299.53,-177.35 293.1,-180.12"/> +<text text-anchor="middle" x="224.35" y="-82.77" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If28->LT27 --> +<g id="edge27" class="edge"> +<title>If28->LT27</title> +<path fill="none" stroke="black" d="M142.44,-80.04C124.74,-91.84 105.18,-104.88 89.9,-115.07"/> +<polygon fill="black" stroke="black" points="87.82,-112.24 81.44,-120.7 91.71,-118.07 87.82,-112.24"/> +<text text-anchor="middle" x="139.44" y="-82.64" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add32->Phi_sum24 --> +<g id="edge29" class="edge"> +<title>Add32->Phi_sum24</title> +<path fill="none" stroke="black" d="M144.73,-162.33C145.24,-167.45 145.78,-172.79 146.29,-177.9"/> +<polygon fill="black" stroke="black" points="148.21,-161.91 143.73,-152.3 141.24,-162.6 148.21,-161.91"/> +<polygon fill="black" stroke="black" points="142.81,-178.29 147.29,-187.9 149.78,-177.6 142.81,-178.29"/> +<text text-anchor="middle" x="140.73" y="-154.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Add32->Phi_j26 --> +<g id="edge28" class="edge"> +<title>Add32->Phi_j26</title> +<path fill="none" stroke="black" d="M126.39,-148.83C114.92,-158.99 99.15,-172.97 86.21,-184.44"/> +<polygon fill="black" stroke="black" points="83.74,-181.95 78.58,-191.2 88.38,-187.19 83.74,-181.95"/> +<text text-anchor="middle" x="123.39" y="-151.43" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_33 --> +<g id="node19" class="node"> +<title>Con_33</title> +<ellipse fill="none" stroke="black" cx="235" cy="-206" rx="27" ry="18"/> +<text text-anchor="middle" x="235" y="-202.3" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Add34->Phi_j26 --> +<g id="edge30" class="edge"> +<title>Add34->Phi_j26</title> +<path fill="none" stroke="black" d="M193.01,-148.01C167.45,-158.51 130.76,-173.83 99,-188 97.2,-188.8 95.36,-189.64 93.5,-190.49"/> +<polygon fill="black" stroke="black" points="194.64,-151.12 202.57,-144.09 191.99,-144.65 194.64,-151.12"/> +<polygon fill="black" stroke="black" points="91.85,-187.39 84.25,-194.78 94.79,-193.74 91.85,-187.39"/> +<text text-anchor="middle" x="199.57" y="-146.69" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add34->Con_33 --> +<g id="edge31" class="edge"> +<title>Add34->Con_33</title> +<path fill="none" stroke="black" d="M227.42,-151.95C228.52,-159.65 229.85,-168.97 231.09,-177.64"/> +<polygon fill="black" stroke="black" points="227.65,-178.32 232.53,-187.72 234.58,-177.33 227.65,-178.32"/> +<text text-anchor="middle" x="224.42" y="-154.55" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Return35->Phi_sum11 --> +<g id="edge33" class="edge"> +<title>Return35->Phi_sum11</title> +<path fill="none" stroke="black" d="M371.93,-220.42C343.47,-232.34 305.01,-249.46 292,-260 233.39,-307.47 185.4,-383.86 162.87,-423.42"/> +<polygon fill="black" stroke="black" points="159.79,-421.75 157.95,-432.19 165.89,-425.18 159.79,-421.75"/> +<text text-anchor="middle" x="368.93" y="-214.02" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return35->If14 --> +<g id="edge32" class="edge"> +<title>Return35->If14:p1</title> +<path fill="none" stroke="red" d="M391.86,-224.13C385.8,-233.37 379.43,-245.41 377.01,-257.92"/> +<polygon fill="red" stroke="red" points="373.52,-257.7 376,-268 380.48,-258.4 373.52,-257.7"/> +<text text-anchor="middle" x="388.86" y="-226.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +</g> +</svg> diff --git a/docs/chapter07/07-graph4.gv b/docs/chapter07/07-graph4.gv new file mode 100644 index 00000000..24ace3da --- /dev/null +++ b/docs/chapter07/07-graph4.gv @@ -0,0 +1,96 @@ +digraph chapter07 { +/* +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; +} +return b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="1" ]; + Con_7 [ label="2" ]; + Loop8 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_a11 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b12 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Con_13 [ label="10" ]; + LT14 [ label="<" ]; + If15 [ 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_19 [ label="2" ]; + EQ20 [ label="==" ]; + If21 [ 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_25 [ label="3" ]; + Con_26 [ label="4" ]; + Region27 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a28 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b29 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Return30 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop8;Phi_a11;Phi_b12;} + { rank=same; Region27;Phi_b29;Phi_a28;} + } + node [shape=plaintext]; + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return30[taillabel=0 color=red]; + Loop8 -> Start2:p0[taillabel=1 color=red]; + Loop8 -> Region27[taillabel=2 color=red constraint=false]; + Phi_a11 -> Loop8 [style=dotted taillabel=0]; + Phi_a11 -> Con_6[taillabel=1]; + Phi_a11 -> Phi_a28[taillabel=2 constraint=false]; + Phi_b12 -> Loop8 [style=dotted taillabel=0]; + Phi_b12 -> Con_7[taillabel=1]; + Phi_b12 -> Phi_b29[taillabel=2 constraint=false]; + LT14 -> Phi_a11[taillabel=1]; + LT14 -> Con_13[taillabel=2]; + If15 -> Loop8[taillabel=0 color=red]; + If15 -> LT14[taillabel=1]; + EQ20 -> Phi_a11[taillabel=1]; + EQ20 -> Con_19[taillabel=2]; + If21 -> If15:p0[taillabel=0 color=red]; + If21 -> EQ20[taillabel=1]; + Region27 -> If21:p0[taillabel=1 color=red]; + Region27 -> If21:p1[taillabel=2 color=red]; + Phi_a28 -> Region27 [style=dotted taillabel=0]; + Phi_a28 -> Con_25[taillabel=1]; + Phi_a28 -> Phi_a11[taillabel=2 constraint=false]; + Phi_b29 -> Region27 [style=dotted taillabel=0]; + Phi_b29 -> Phi_b12[taillabel=1]; + Phi_b29 -> Con_26[taillabel=2 constraint=false]; + Return30 -> If15:p1[taillabel=0 color=red]; + Return30 -> Phi_b12[taillabel=1]; + edge [style=dashed color=cornflowerblue]; +} diff --git a/docs/chapter07/07-graph4.svg b/docs/chapter07/07-graph4.svg new file mode 100644 index 00000000..cf42453d --- /dev/null +++ b/docs/chapter07/07-graph4.svg @@ -0,0 +1,329 @@ +<?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: chapter07 Pages: 1 --> +<svg width="394pt" height="545pt" + viewBox="0.00 0.00 394.00 545.35" 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 541.35)"> +<title>chapter07</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-541.35 390,-541.35 390,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-33.35 8,-529.35 378,-529.35 378,-33.35 8,-33.35"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="312,-492.35 312,-517.35 362,-517.35 362,-492.35 312,-492.35"/> +<polygon fill="none" stroke="black" points="312,-492.35 312,-517.35 362,-517.35 362,-492.35 312,-492.35"/> +<text text-anchor="start" x="318.5" y="-501.15" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="312,-461.35 312,-492.35 362,-492.35 362,-461.35 312,-461.35"/> +<polygon fill="yellow" stroke="transparent" points="317,-466.35 317,-487.35 357,-487.35 357,-466.35 317,-466.35"/> +<polygon fill="none" stroke="black" points="317,-466.35 317,-487.35 357,-487.35 357,-466.35 317,-466.35"/> +<text text-anchor="start" x="320" y="-473.15" font-family="Times,serif" font-size="14.00">$ctrl</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="370,-77.35 316,-77.35 316,-41.35 370,-41.35 370,-77.35"/> +<text text-anchor="middle" x="343" y="-55.65" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return30 --> +<g id="node19" class="node"> +<title>Return30</title> +<polygon fill="yellow" stroke="black" points="370,-163.35 304,-163.35 304,-127.35 370,-127.35 370,-163.35"/> +<text text-anchor="middle" x="337" y="-141.65" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return30 --> +<g id="edge1" class="edge"> +<title>Stop3->Return30</title> +<path fill="none" stroke="red" d="M341.76,-77.75C340.95,-89.09 339.87,-104.12 338.95,-117.03"/> +<polygon fill="red" stroke="red" points="335.44,-117.03 338.22,-127.25 342.42,-117.53 335.44,-117.03"/> +<text text-anchor="middle" x="338.76" y="-80.35" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="196" cy="-489.35" rx="27" ry="18"/> +<text text-anchor="middle" x="196" y="-485.65" font-family="Times,serif" font-size="14.00">1</text> +</g> +<!-- Con_7 --> +<g id="node4" class="node"> +<title>Con_7</title> +<ellipse fill="none" stroke="black" cx="124" cy="-489.35" rx="27" ry="18"/> +<text text-anchor="middle" x="124" y="-485.65" font-family="Times,serif" font-size="14.00">2</text> +</g> +<!-- Loop8 --> +<g id="node5" class="node"> +<title>Loop8</title> +<polygon fill="yellow" stroke="black" points="367,-421.35 313,-421.35 313,-385.35 367,-385.35 367,-421.35"/> +<text text-anchor="middle" x="340" y="-399.65" font-family="Times,serif" font-size="14.00">Loop</text> +</g> +<!-- Loop8->Start2 --> +<g id="edge2" class="edge"> +<title>Loop8->Start2:p0</title> +<path fill="none" stroke="red" d="M338.71,-421.43C338.08,-430.88 337.4,-443.1 337.13,-455.02"/> +<polygon fill="red" stroke="red" points="333.62,-455.3 337,-465.35 340.62,-455.39 333.62,-455.3"/> +<text text-anchor="middle" x="335.71" y="-424.03" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region27 --> +<g id="node16" class="node"> +<title>Region27</title> +<polygon fill="yellow" stroke="black" points="298,-77.35 232,-77.35 232,-41.35 298,-41.35 298,-77.35"/> +<text text-anchor="middle" x="265" y="-55.65" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Loop8->Region27 --> +<g id="edge3" class="edge"> +<title>Loop8->Region27</title> +<path fill="none" stroke="red" d="M312.6,-389.27C286.36,-376.62 248.79,-358.1 235,-349.35 191.17,-321.51 165.74,-324.02 143,-277.35 130.54,-251.78 139.66,-241.59 143,-213.35 145.69,-190.65 153.07,-131.47 167,-113.35 174.64,-103.41 199.67,-89.94 222.53,-79.07"/> +<polygon fill="red" stroke="red" points="224.22,-82.15 231.8,-74.74 221.25,-75.8 224.22,-82.15"/> +<text text-anchor="middle" x="309.6" y="-382.87" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a11 --> +<g id="node6" class="node"> +<title>Phi_a11</title> +<ellipse fill="lightyellow" stroke="black" cx="196" cy="-403.35" rx="27" ry="18"/> +<text text-anchor="middle" x="196" y="-399.65" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a11->Con_6 --> +<g id="edge5" class="edge"> +<title>Phi_a11->Con_6</title> +<path fill="none" stroke="black" d="M196,-421.75C196,-433.09 196,-448.12 196,-461.03"/> +<polygon fill="black" stroke="black" points="192.5,-461.25 196,-471.25 199.5,-461.25 192.5,-461.25"/> +<text text-anchor="middle" x="193" y="-424.35" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a11->Loop8 --> +<g id="edge4" class="edge"> +<title>Phi_a11->Loop8</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M210.22,-387.78C218.37,-380.03 229.29,-371.45 241,-367.35 263.65,-359.4 272.35,-359.4 295,-367.35 302.14,-369.85 308.99,-374.02 315.09,-378.65"/> +<polygon fill="black" stroke="black" points="312.99,-381.44 322.92,-385.13 317.45,-376.05 312.99,-381.44"/> +<text text-anchor="middle" x="207.22" y="-381.38" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Phi_a28 --> +<g id="node17" class="node"> +<title>Phi_a28</title> +<ellipse fill="lightyellow" stroke="black" cx="187" cy="-59.35" rx="27" ry="18"/> +<text text-anchor="middle" x="187" y="-55.65" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_b12 --> +<g id="node7" class="node"> +<title>Phi_b12</title> +<ellipse fill="lightyellow" stroke="black" cx="124" cy="-403.35" rx="27.1" ry="18"/> +<text text-anchor="middle" x="124" y="-399.65" font-family="Times,serif" font-size="14.00">φ_b</text> +</g> +<!-- Phi_b12->Con_7 --> +<g id="edge8" class="edge"> +<title>Phi_b12->Con_7</title> +<path fill="none" stroke="black" d="M124,-421.75C124,-433.09 124,-448.12 124,-461.03"/> +<polygon fill="black" stroke="black" points="120.5,-461.25 124,-471.25 127.5,-461.25 120.5,-461.25"/> +<text text-anchor="middle" x="121" y="-424.35" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_b12->Loop8 --> +<g id="edge7" class="edge"> +<title>Phi_b12->Loop8</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M138.22,-387.78C146.37,-380.03 157.29,-371.45 169,-367.35 221.84,-348.81 242.16,-348.81 295,-367.35 302.14,-369.85 308.99,-374.02 315.09,-378.65"/> +<polygon fill="black" stroke="black" points="312.99,-381.44 322.92,-385.13 317.45,-376.05 312.99,-381.44"/> +<text text-anchor="middle" x="135.22" y="-381.38" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Phi_b29 --> +<g id="node18" class="node"> +<title>Phi_b29</title> +<ellipse fill="lightyellow" stroke="black" cx="43" cy="-59.35" rx="27.1" ry="18"/> +<text text-anchor="middle" x="43" y="-55.65" font-family="Times,serif" font-size="14.00">φ_b</text> +</g> +<!-- Con_13 --> +<g id="node8" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="268" cy="-403.35" rx="27" ry="18"/> +<text text-anchor="middle" x="268" y="-399.65" font-family="Times,serif" font-size="14.00">10</text> +</g> +<!-- LT14 --> +<g id="node9" class="node"> +<title>LT14</title> +<ellipse fill="none" stroke="black" cx="271" cy="-331.35" rx="27" ry="18"/> +<text text-anchor="middle" x="271" y="-327.65" font-family="Times,serif" font-size="14.00"><</text> +</g> +<!-- LT14->Phi_a11 --> +<g id="edge10" class="edge"> +<title>LT14->Phi_a11</title> +<path fill="none" stroke="black" d="M255.82,-346.51C245.15,-356.47 230.68,-369.98 218.65,-381.21"/> +<polygon fill="black" stroke="black" points="216.08,-378.82 211.15,-388.2 220.85,-383.94 216.08,-378.82"/> +<text text-anchor="middle" x="252.82" y="-349.11" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- LT14->Con_13 --> +<g id="edge11" class="edge"> +<title>LT14->Con_13</title> +<path fill="none" stroke="black" d="M270.26,-349.65C269.93,-357.36 269.53,-366.63 269.16,-375.23"/> +<polygon fill="black" stroke="black" points="265.66,-375.1 268.73,-385.24 272.66,-375.4 265.66,-375.1"/> +<text text-anchor="middle" x="267.26" y="-352.25" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If15 --> +<g id="node10" class="node"> +<title>If15</title> +<polygon fill="yellow" stroke="transparent" points="260,-248.35 260,-273.35 354,-273.35 354,-248.35 260,-248.35"/> +<polygon fill="none" stroke="black" points="260,-248.35 260,-273.35 354,-273.35 354,-248.35 260,-248.35"/> +<text text-anchor="start" x="301.5" y="-257.15" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="260,-217.35 260,-248.35 354,-248.35 354,-217.35 260,-217.35"/> +<polygon fill="yellow" stroke="transparent" points="265,-222.35 265,-243.35 305,-243.35 305,-222.35 265,-222.35"/> +<polygon fill="none" stroke="black" points="265,-222.35 265,-243.35 305,-243.35 305,-222.35 265,-222.35"/> +<text text-anchor="start" x="268" y="-229.15" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="305,-222.35 305,-243.35 349,-243.35 349,-222.35 305,-222.35"/> +<polygon fill="none" stroke="black" points="305,-222.35 305,-243.35 349,-243.35 349,-222.35 305,-222.35"/> +<text text-anchor="start" x="308" y="-229.15" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If15->Loop8 --> +<g id="edge12" class="edge"> +<title>If15->Loop8</title> +<path fill="none" stroke="red" d="M314.79,-277.64C317.5,-288.87 320.49,-301.65 323,-313.35 327.43,-333.98 331.89,-357.43 335.12,-375.08"/> +<polygon fill="red" stroke="red" points="331.74,-376.02 336.97,-385.24 338.63,-374.77 331.74,-376.02"/> +<text text-anchor="middle" x="311.79" y="-280.24" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If15->LT14 --> +<g id="edge13" class="edge"> +<title>If15->LT14</title> +<path fill="none" stroke="black" d="M293.59,-277.62C289.8,-286.48 285.72,-296.01 282.08,-304.5"/> +<polygon fill="black" stroke="black" points="278.78,-303.32 278.05,-313.89 285.21,-306.08 278.78,-303.32"/> +<text text-anchor="middle" x="290.59" y="-280.22" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_19 --> +<g id="node11" class="node"> +<title>Con_19</title> +<ellipse fill="none" stroke="black" cx="130" cy="-331.35" rx="27" ry="18"/> +<text text-anchor="middle" x="130" y="-327.65" font-family="Times,serif" font-size="14.00">2</text> +</g> +<!-- EQ20 --> +<g id="node12" class="node"> +<title>EQ20</title> +<ellipse fill="none" stroke="black" cx="179" cy="-245.35" rx="27" ry="18"/> +<text text-anchor="middle" x="179" y="-241.65" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQ20->Phi_a11 --> +<g id="edge14" class="edge"> +<title>EQ20->Phi_a11</title> +<path fill="none" stroke="black" d="M180.85,-263.34C183.79,-290.3 189.54,-343.11 193.05,-375.31"/> +<polygon fill="black" stroke="black" points="189.59,-375.81 194.15,-385.38 196.55,-375.06 189.59,-375.81"/> +<text text-anchor="middle" x="177.85" y="-265.94" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQ20->Con_19 --> +<g id="edge15" class="edge"> +<title>EQ20->Con_19</title> +<path fill="none" stroke="black" d="M169.55,-262.54C162.5,-274.63 152.74,-291.37 144.67,-305.19"/> +<polygon fill="black" stroke="black" points="141.43,-303.8 139.42,-314.2 147.48,-307.33 141.43,-303.8"/> +<text text-anchor="middle" x="166.55" y="-265.14" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If21 --> +<g id="node13" class="node"> +<title>If21</title> +<polygon fill="yellow" stroke="transparent" points="184,-148.35 184,-173.35 278,-173.35 278,-148.35 184,-148.35"/> +<polygon fill="none" stroke="black" points="184,-148.35 184,-173.35 278,-173.35 278,-148.35 184,-148.35"/> +<text text-anchor="start" x="225.5" y="-157.15" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="184,-117.35 184,-148.35 278,-148.35 278,-117.35 184,-117.35"/> +<polygon fill="yellow" stroke="transparent" points="189,-122.35 189,-143.35 229,-143.35 229,-122.35 189,-122.35"/> +<polygon fill="none" stroke="black" points="189,-122.35 189,-143.35 229,-143.35 229,-122.35 189,-122.35"/> +<text text-anchor="start" x="192" y="-129.15" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="229,-122.35 229,-143.35 273,-143.35 273,-122.35 229,-122.35"/> +<polygon fill="none" stroke="black" points="229,-122.35 229,-143.35 273,-143.35 273,-122.35 229,-122.35"/> +<text text-anchor="start" x="232" y="-129.15" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If21->If15 --> +<g id="edge16" class="edge"> +<title>If21->If15:p0</title> +<path fill="none" stroke="red" d="M266.11,-177.35C274.25,-187.13 281.31,-198.68 283.92,-211.16"/> +<polygon fill="red" stroke="red" points="280.47,-211.77 285,-221.35 287.43,-211.03 280.47,-211.77"/> +<text text-anchor="middle" x="263.11" y="-179.95" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If21->EQ20 --> +<g id="edge17" class="edge"> +<title>If21->EQ20</title> +<path fill="none" stroke="black" d="M214.55,-177.35C207.43,-190.76 199.21,-206.25 192.47,-218.96"/> +<polygon fill="black" stroke="black" points="189.24,-217.58 187.65,-228.05 195.42,-220.86 189.24,-217.58"/> +<text text-anchor="middle" x="211.55" y="-179.95" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_25 --> +<g id="node14" class="node"> +<title>Con_25</title> +<ellipse fill="none" stroke="black" cx="111" cy="-145.35" rx="27" ry="18"/> +<text text-anchor="middle" x="111" y="-141.65" font-family="Times,serif" font-size="14.00">3</text> +</g> +<!-- Con_26 --> +<g id="node15" class="node"> +<title>Con_26</title> +<ellipse fill="none" stroke="black" cx="115" cy="-59.35" rx="27" ry="18"/> +<text text-anchor="middle" x="115" y="-55.65" font-family="Times,serif" font-size="14.00">4</text> +</g> +<!-- Region27->If21 --> +<g id="edge18" class="edge"> +<title>Region27->If21:p0</title> +<path fill="none" stroke="red" d="M236.34,-77.55C225.26,-86.1 214.31,-97.52 210.45,-111.09"/> +<polygon fill="red" stroke="red" points="206.94,-110.95 209,-121.35 213.87,-111.94 206.94,-110.95"/> +<text text-anchor="middle" x="233.34" y="-80.15" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region27->If21 --> +<g id="edge19" class="edge"> +<title>Region27->If21:p1</title> +<path fill="none" stroke="red" d="M258.9,-77.46C255.95,-86.91 252.79,-99.16 251.55,-111.27"/> +<polygon fill="red" stroke="red" points="248.05,-111.17 251,-121.35 255.04,-111.55 248.05,-111.17"/> +<text text-anchor="middle" x="255.9" y="-80.06" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a28->Phi_a11 --> +<g id="edge22" class="edge"> +<title>Phi_a28->Phi_a11</title> +<path fill="none" stroke="black" d="M156.38,-74.81C123.24,-90.46 75.08,-113.23 75,-113.35 59.78,-137.38 66.63,-150.16 75,-177.35 90.81,-228.71 98.49,-247.23 143,-277.35 204.81,-319.16 260.23,-255.2 307,-313.35 317.03,-325.81 315.54,-335.81 307,-349.35 306.7,-349.82 259.29,-372.35 226.54,-387.88"/> +<polygon fill="black" stroke="black" points="158.14,-77.85 165.69,-70.41 155.15,-71.52 158.14,-77.85"/> +<polygon fill="black" stroke="black" points="224.86,-384.81 217.32,-392.25 227.86,-391.13 224.86,-384.81"/> +<text text-anchor="middle" x="162.69" y="-73.01" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a28->Con_25 --> +<g id="edge21" class="edge"> +<title>Phi_a28->Con_25</title> +<path fill="none" stroke="black" d="M173.41,-75.36C161.74,-88.26 144.74,-107.05 131.43,-121.77"/> +<polygon fill="black" stroke="black" points="128.58,-119.7 124.47,-129.46 133.77,-124.39 128.58,-119.7"/> +<text text-anchor="middle" x="170.41" y="-77.96" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a28->Region27 --> +<g id="edge20" class="edge"> +<title>Phi_a28->Region27</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M214.12,-59.35C216.58,-59.35 219.04,-59.35 221.5,-59.35"/> +<polygon fill="black" stroke="black" points="221.61,-62.85 231.61,-59.35 221.61,-55.85 221.61,-62.85"/> +<text text-anchor="middle" x="217.12" y="-52.95" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Phi_b29->Phi_b12 --> +<g id="edge24" class="edge"> +<title>Phi_b29->Phi_b12</title> +<path fill="none" stroke="black" d="M44.59,-87.64C48.34,-139.92 60.11,-257.16 94,-349.35 97.54,-358.97 102.7,-368.9 107.74,-377.53"/> +<polygon fill="black" stroke="black" points="48.07,-87.25 43.91,-77.51 41.09,-87.72 48.07,-87.25"/> +<polygon fill="black" stroke="black" points="104.9,-379.59 113.09,-386.31 110.88,-375.95 104.9,-379.59"/> +<text text-anchor="middle" x="40.91" y="-80.11" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_b29->Con_26 --> +<g id="edge25" class="edge"> +<title>Phi_b29->Con_26</title> +<path fill="none" stroke="black" d="M70.56,-59.35C73,-59.35 75.44,-59.35 77.89,-59.35"/> +<polygon fill="black" stroke="black" points="77.92,-62.85 87.92,-59.35 77.92,-55.85 77.92,-62.85"/> +<text text-anchor="middle" x="73.56" y="-52.95" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_b29->Region27 --> +<g id="edge23" class="edge"> +<title>Phi_b29->Region27</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M54.68,-42.66C62.75,-32.67 74.44,-20.87 88,-15.35 139.86,5.79 161.51,4.17 214,-15.35 224.63,-19.3 234.53,-26.57 242.72,-34.08"/> +<polygon fill="black" stroke="black" points="240.44,-36.75 250.02,-41.26 245.34,-31.75 240.44,-36.75"/> +<text text-anchor="middle" x="51.68" y="-36.26" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return30->Phi_b12 --> +<g id="edge27" class="edge"> +<title>Return30->Phi_b12</title> +<path fill="none" stroke="black" d="M313.98,-163.53C307.84,-168.06 301.19,-172.92 295,-177.35 272.13,-193.69 260.87,-191.65 243,-213.35 223.27,-237.31 230.02,-250.17 215,-277.35 196.27,-311.22 188.92,-318.16 166,-349.35 158.65,-359.34 150.22,-370.11 142.84,-379.32"/> +<polygon fill="black" stroke="black" points="139.98,-377.29 136.43,-387.27 145.43,-381.68 139.98,-377.29"/> +<text text-anchor="middle" x="310.98" y="-166.13" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return30->If15 --> +<g id="edge26" class="edge"> +<title>Return30->If15:p1</title> +<path fill="none" stroke="red" d="M333.39,-163.54C331,-176.2 328.14,-194.14 327.27,-211.34"/> +<polygon fill="red" stroke="red" points="323.77,-211.26 327,-221.35 330.76,-211.44 323.77,-211.26"/> +<text text-anchor="middle" x="330.39" y="-166.14" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +</g> +</svg> diff --git a/docs/chapter07/Makefile b/docs/chapter07/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter07/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/chapter07/README.md b/docs/chapter07/README.md new file mode 100644 index 00000000..19dbcfe0 --- /dev/null +++ b/docs/chapter07/README.md @@ -0,0 +1,244 @@ +# Chapter 7: While Statement + +# Table of Contents + +1. [Dealing With Back Edges](#dealing-with-back-edges) +2. [New Node Types](#new-node-types) +3. [Detailed Steps](#detailed-steps) +4. [Visualization](#visualization) +5. [Nested Loops](#nested-loops) +5. [Loop With Nested If](#loop-with-nested-if) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter07) 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-chapter06...linear-chapter07) it to the previous chapter. + + +In this chapter we introduce the `while` statement. + +Here is the [complete language grammar](07-grammar.md) for this chapter. + + +## Dealing With Back Edges + +The complication introduced by looping constructs is that variables flow back into the body of the loop on iteration. +For example: + +```java +while(arg < 10) { + arg = arg + 1; +} +return arg; +``` + +The variable `arg` is assigned a new value inside the body of the loop, and this then flows back into the body of the loop. + +In general, we will rewrite the looping construct as follows: + +```java +loop_head: +if( !(arg < 10) ) + goto loop_exit; +arg = arg + 1; +goto loop_head; + +loop_exit: +``` + +Above is for illustration only, we do not have labels and `goto` statements in the language. + +From an SSA[^1] point of view, since `arg` flows back, it requires a `phi` node at the head. Conceptually we would like the outcome to be: + +```java +// arg1 represents incoming arg +// +loop_head: +arg2 = phi(arg1, arg3); +if( !(arg2 < 10) ) + goto loop_exit; +arg3 = arg2 + 1; +goto loop_head; + +loop_exit: +``` + +Notice that the phi for `arg2` refers to `arg3`, which is not known at the time we parse the `while` loop predicate. This is the crux of the problem that we need +to solve in order to successfully construct the Sea of Nodes graph, which is always in SSA form. + +Recall from [Chapter 5](../chapter05/README.md) that when parsing `if` statements, we clone the symbol tables as we go past the `if` predicate. +Later we merge the two sets of symbol tables at a `Region` - creating phis for all names that encountered a change in definition within the two +branches of the `if` statement. In the case of the `if` statement, the phis are created at the merge point when we already know the definitions +that are being merged. + +The essential idea for loop constructs is to eagerly create phis for all names in the symbol tables *before* we enter the loop's `if` condition, +since we do not know which names will be redefined inside the body of the loop. When the loop terminates, we go back and remove unnecessary +phis. We call this approach the "eager phi" approach.[^2] + +In [Chapter 8](../chapter08) we will implement a "lazy phi" approach that creates phis only when we encounter redefinition of a name. + +## New Node Types + +Our list of nodes remains the same as in [Chapter 5](../chapter05/README.md), however, we create a subtype of `Region` named `Loop` to better +encapsulate some of the additional logic required. A key aspect of this is to temporarily disable peepholes of the `Region` and any phis +created until we complete parsing the loop body. This is because our phis are not fully constructed until the loop end. + +## Detailed Steps + +1. We start by creating a new subclass of `Region`, the `Loop`. The `Loop` gets two control inputs, + the first is the entry point, i.e. the current binding to `$ctrl`, and second (`null`) is a placeholder for the back edge that is + set after loop is parsed. The absence of a back edge is used as an indicator to switch off peepholes of the region and + associated phis. + + ```java + ctrl(new LoopNode(ctrl(),null).peephole()); + ``` + + The newly created region becomes the current control. + +2. We duplicate the current Scope node. This involves duplicating all the symbols at + every level with the scope, and creating phis for every symbol except the `$ctrl` binding. + + ```java + // Make a new Scope for the body. + _scope = _scope.dup(true); + ``` + + Note that the `dup` call is given an argument `true`. This triggers creating phis. The code + that creates the phis in the `dup()` method is shown below. + + ```java + // boolean loop=true if this is a loop region + + String[] names = reverseNames(); // Get the variable names + dup.add_def(ctrl()); // Control input is just copied + for( int i=1; i<nIns(); i++ ) { + if ( !loop ) { dup.add_def(in(i)); } + else { + // Loop region + // Create a phi node with second input as null - to be filled in + // by endLoop() below + dup.add_def(new PhiNode(names[i], ctrl(), in(i), null).peephole()); + // Ensure our node has the same phi in case we created one + set_def(i, dup.in(i)); + } + } + ``` + + Inside the `else` block both the duplicated scope and the original scope get the same phi node. + +3. Next we set up the `if` condition, very much like we do with regular ifs. + + ```java + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + ``` + +4. We make another clone of the current scope. This will be the exit scope that will live after the loop ends, + therefore `$ctrl` in the exit scope is set to the `False` projection. + The exit scope captures any side effects of the loop's predicate. + + ```java + // The exit scope, accounting for any side effects in the predicate + var exit = _scope.dup(); + exit.ctrl(ifF); + ``` + +5. We now set the control to the `True` projection and parse the loop body. + + ```java + // Parse the true side, which corresponds to loop body + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + ``` + +6. After the loop body is parsed, we go back and process all the phis we created earlier. + + ```java + // The true branch loops back, so whatever is current control gets + // added to head loop as input + head.endLoop(_scope, exit); + ``` + + The `endLoop` method sets the second control of the loop region to the control from the back edge. + It then goes through all the phis and sets the second data input on the phi to the corresponding entry + from the loop body; phis that were not used are peepholed and get replaced by the original input. + + ```java + Node ctrl = ctrl(); + ctrl.set_def(2,back.ctrl()); + for( int i=1; i<nIns(); i++ ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.set_def(2,back.in(i)); + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) + phi.subsume(in); + } + ``` + +7. Finally, both the original scope (head) we started with, and the duplicate created for the body are killed. + At exit the false control is the current control (step 4), and exit scope is set as the current scope. + + ```java + // At exit the false control is the current control, and + // the scope is the exit scope after the exit test. + return (_scope = exit); + ``` + +### Visualization + +The example quoted above is shown below at an intermediate state: + + + +* Three Scopes are shown, reading clockwise, the loop head, exit and the body. + +The final graph looks like this: + + + +## More Complex Examples + +### Nested Loops + +```java +int sum = 0; +int i = 0; +while(i < arg) { + i = i + 1; + int j = 0; + while( j < arg ) { + sum = sum + j; + j = j + 1; + } +} +return sum; +``` + + + +### Loop With Nested If + +```java +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; +} +return b; +``` + + + + +[^1]: Cytron, R. et al (1991). + Efficiently computing static single assignment form and the control dependence graph, in ACM Transactions on Programming Languages and Systems, 13(4):451-490, 1991. + +[^2]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 103. diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index b30dd450..07f1af21 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -11,13 +11,22 @@ import java.util.*; */ public class GraphVisualizer { + /** + * If set to true we put the control nodes in a separate cluster from + * data nodes. + */ + boolean _separateControlCluster = false; + + public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; } + public GraphVisualizer() { this(false); } + public String generateDotOutput(Parser parser) { // Since the graph has cycles, we need to create a flat list of all the // nodes in the graph. Collection<Node> all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter06 {\n"); + sb.append("digraph chapter07 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -36,42 +45,48 @@ public class GraphVisualizer { // nodes much prettier to look at. sb.append("\tconcentrate=\"true\";\n"); + // Force nested scopes to order + sb.append("\tcompound=\"true\";\n"); + // Just the Nodes first, in a cluster no edges nodes(sb, all); // Now the scopes, in a cluster no edges - for (ScopeNode sn: parser._xScopes) - scopes(sb, sn); + for( ScopeNode scope : parser._xScopes ) + scope( sb, scope ); // Walk the Node edges nodeEdges(sb, all); - // Walk the Scope edges - for (ScopeNode sn: parser._xScopes) - scopeEdges(sb, sn); + // Walk the active Scope edges + for( ScopeNode scope : parser._xScopes ) + scopeEdges( sb, scope ); sb.append("}\n"); return sb.toString(); } - - private void nodes(StringBuilder sb, Collection<Node> all) { + private void nodesByCluster(StringBuilder sb, boolean doCtrl, Collection<Node> all) { + if (!_separateControlCluster && doCtrl) // all nodes in 1 cluster + return; // Just the Nodes first, in a cluster no edges - sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name - for( Node n : all ) { - if( n instanceof ProjNode || n instanceof ScopeNode ) + sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name + for (Node n : all) { + if (n instanceof ProjNode || n instanceof ScopeNode) continue; // Do not emit, rolled into MultiNode or Scope cluster already + if (_separateControlCluster && doCtrl && !n.isCFG()) continue; + if (_separateControlCluster && !doCtrl && n.isCFG()) continue; sb.append("\t\t").append(n.uniqueName()).append(" [ "); String lab = n.glabel(); - if( n instanceof MultiNode ) { + if (n instanceof MultiNode) { // Make a box with the MultiNode on top, and all the projections on the bottom sb.append("shape=plaintext label=<\n"); sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\">\n"); sb.append("\t\t\t<TR><TD BGCOLOR=\"yellow\">").append(lab).append("</TD></TR>\n"); sb.append("\t\t\t<TR>"); boolean doProjTable = false; - for( Node use : n._outputs ) { - if( use instanceof ProjNode proj ) { + for (Node use : n._outputs) { + if (use instanceof ProjNode proj) { if (!doProjTable) { doProjTable = true; sb.append("<TD>").append("\n"); @@ -79,7 +94,7 @@ public class GraphVisualizer { sb.append("\t\t\t\t<TR>"); } sb.append("<TD PORT=\"p").append(proj._idx).append("\""); - if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\""); + if (proj.isCFG()) sb.append(" BGCOLOR=\"yellow\""); sb.append(">").append(proj.glabel()).append("</TD>"); } } @@ -94,41 +109,46 @@ public class GraphVisualizer { } else { // control nodes have box shape // other nodes are ellipses, i.e. default shape - if( n.isCFG() ) - sb.append("shape=box style=filled fillcolor=yellow "); - if( n instanceof PhiNode ) - sb.append("style=filled fillcolor=lightyellow "); + if (n.isCFG()) sb.append("shape=box style=filled fillcolor=yellow "); + else if (n instanceof PhiNode) sb.append("style=filled fillcolor=lightyellow "); sb.append("label=\"").append(lab).append("\" "); } sb.append("];\n"); } - - // Force Region & Phis to line up - for( Node n : all ) { - if( n instanceof RegionNode region ) { - sb.append("\t\t{ rank=same; "); - sb.append(region).append(";") ; - for( Node phi : region._outputs ) - if( phi instanceof PhiNode ) - sb.append(phi.uniqueName()).append(";"); - sb.append("}\n"); + if (!_separateControlCluster) { + // Force Region & Phis to line up + for (Node n : all) { + if (n instanceof RegionNode region) { + sb.append("\t\t{ rank=same; "); + sb.append(region).append(";"); + for (Node phi : region._outputs) + if (phi instanceof PhiNode) sb.append(phi.uniqueName()).append(";"); + sb.append("}\n"); + } } } - sb.append("\t}\n"); // End Node cluster } - private void scopes( StringBuilder sb, ScopeNode scopenode) { + private void nodes(StringBuilder sb, Collection<Node> all) { + nodesByCluster(sb, true, all); + nodesByCluster(sb, false, all); + } + + // Build a nested scope display, walking the _prev edge + private void scope( StringBuilder sb, ScopeNode scope ) { sb.append("\tnode [shape=plaintext];\n"); - int level=0; - for( HashMap<String,Integer> scope : scopenode._scopes ) { - String scopeName = makeScopeName(scopenode, level); + int level=1; + for( int idx = scope._scopes.size()-1; idx>=0; idx-- ) { + var syms = scope._scopes.get(idx); + String scopeName = makeScopeName(scope, level); sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name sb.append("\t\t").append(scopeName).append(" [label=<\n"); sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); // Add the scope level - sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(level).append("</TD>"); - for( String name : scope.keySet() ) + int scopeLevel = scope._scopes.size()-level; + sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>"); + for(String name: syms.keySet()) sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); sb.append("</TR>\n"); sb.append("\t\t\t</TABLE>>];\n"); @@ -137,7 +157,7 @@ public class GraphVisualizer { // Scope clusters nest, so the graphics shows the nested scopes, so // they are not closed as they are printed; so they just keep nesting. // We close them all at once here. - sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters + sb.append( "\t}\n".repeat( level-1 ) ); // End all Scope clusters } private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } @@ -153,8 +173,8 @@ public class GraphVisualizer { // ScopeNodes are done separately if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode ) continue; - int i=0; - for( Node def : n._inputs ) { + for( int i=0; i<n.nIns(); i++ ) { + Node def = n.in(i); if( n instanceof PhiNode && def instanceof RegionNode ) { // Draw a dotted use->def edge from Phi to Region. sb.append('\t').append(n.uniqueName()); @@ -173,21 +193,25 @@ public class GraphVisualizer { // control edges are colored red if( def.isCFG() ) sb.append(" color=red"); + // Backedges do not add a ranking constraint + if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) ) + sb.append(" constraint=false"); sb.append("];\n"); } - i++; } } } // Walk the scope edges - private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { + private void scopeEdges( StringBuilder sb, ScopeNode scope ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); - int level=0; - for( HashMap<String,Integer> scope : scopenode._scopes ) { - String scopeName = makeScopeName(scopenode, level); - for( String name : scope.keySet() ) { - Node def = scopenode.in(scope.get(name)); + int level=1; + for( int i = scope._scopes.size()-1; i>=0; i-- ) { + var syms = scope._scopes.get(i); + String scopeName = makeScopeName(scope, level); + for( String name : syms.keySet() ) { + int idx = syms.get(name); + Node def = scope.in(idx); if( def==null ) continue; sb.append("\t") .append(scopeName).append(":") diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java new file mode 100644 index 00000000..2a6dbefd --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -0,0 +1,124 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.LoopNode; +import com.seaofnodes.simple.node.Node; + +import java.util.ArrayList; +import java.util.BitSet; + +public class IRPrinter { + + // Another bulk pretty-printer. Makes more effort at basic-block grouping. + public static String prettyPrint(Node node, int depth) { + // First, a Breadth First Search at a fixed depth. + BFS bfs = new BFS(node,depth); + // Convert just that set to a post-order + ArrayList<Node> rpos = new ArrayList<>(); + BitSet visit = new BitSet(); + for( int i=bfs._lim; i< bfs._bfs.size(); i++ ) + postOrd( bfs._bfs.get(i), rpos, visit, bfs._bs); + // Reverse the post-order walk + StringBuilder sb = new StringBuilder(); + boolean gap=false; + for( int i=rpos.size()-1; i>=0; i-- ) { + Node n = rpos.get(i); + if( n.isCFG() || n.isMultiHead() ) { + if( !gap ) sb.append("\n"); // Blank before multihead + n._printLine(sb); // Print head + while( --i >= 0 ) { + Node t = rpos.get(i); + if( !t.isMultiTail() ) { i++; break; } + t._printLine(sb); + } + sb.append("\n"); // Blank after multitail + gap = true; + } else { + n._printLine( sb ); + gap = false; + } + } + return sb.toString(); + } + + private static void postOrd(Node n, ArrayList<Node> rpos, BitSet visit, BitSet bfs) { + if( !bfs.get(n._nid) ) + return; // Not in the BFS visit + if( visit.get(n._nid) ) return; // Already post-order walked + visit.set(n._nid); + // First walk the CFG, then everything + if( n.isCFG() ) { + for( Node use : n._outputs ) + if( use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) + postOrd(use, rpos,visit,bfs); + for( Node use : n._outputs ) + if( use.isCFG() ) + postOrd(use,rpos,visit,bfs); + } + for( Node use : n._outputs ) + postOrd(use, rpos,visit,bfs); + // Post-order + rpos.add(n); + } + + // Breadth-first search, broken out in a class to keep in more independent. + // Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead). + public static class BFS { + // A breadth first search, plus MultiHeads for any MultiTails + public final ArrayList<Node> _bfs; + public final BitSet _bs; // Visited members by node id + public final int _depth; // Depth limit + public final int _lim; // From here to _bfs._len can be roots for a reverse search + public BFS( Node base, int d ) { + _depth = d; + _bfs = new ArrayList<>(); + _bs = new BitSet(); + + add(base); // Prime the pump + int idx=0, lim=1; // Limit is where depth counter changes + while( idx < _bfs.size() ) { // Ran out of nodes below depth + Node n = _bfs.get(idx++); + for( Node def : n._inputs ) + if( def!=null && !_bs.get(def._nid) ) + add(def); + if( idx==lim ) { // Depth counter changes at limit + if( --d < 0 ) + break; // Ran out of depth + lim = _bfs.size(); // New depth limit + } + } + // Toss things past the limit except multi-heads + while( idx < _bfs.size() ) { + Node n = _bfs.get(idx); + if( n.isMultiHead() ) idx++; + else del(idx); + } + // Root set is any node with no inputs in the visited set + lim = _bfs.size(); + for( int i=_bfs.size()-1; i>=0; i-- ) + if( !any_visited(_bfs.get(i)) ) + swap( i,--lim); + _lim = lim; + } + void swap( int x, int y ) { + if( x==y ) return; + Node tx = _bfs.get(x); + Node ty = _bfs.get(y); + _bfs.set(x,ty); + _bfs.set(y,tx); + } + void add(Node n) { + _bfs.add(n); + _bs.set(n._nid); + } + void del(int idx) { + Node n = Utils.del(_bfs, idx); + _bs.clear(n._nid); + } + boolean any_visited( Node n ) { + for( Node def : n._inputs ) + if( def!=null && _bs.get(def._nid) ) + return true; + return false; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 1a15efa3..cfb4deb4 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -52,6 +52,7 @@ public class Parser { add("int"); add("return"); add("true"); + add("while"); }}; @@ -134,12 +135,81 @@ public class Parser { else if (matchx("int")) return parseDecl(); else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); + else if (matchx("while")) return parseWhile(); else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } /** + * Parses a while statement + * + * <pre> + * while ( expression ) statement + * </pre> + * @return a {@link Node}, never {@code null} + */ + private Node parseWhile() { + require("("); + + // Loop region has two control inputs, the first is the entry + // point, and second is back edge that is set after loop is parsed + // (see end_loop() call below). Note that the absence of back edge is + // used as an indicator to switch off peepholes of the region and + // associated phis; see {@code inProgress()}. + + ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here + + // At loop head, we clone the current Scope (this includes all + // names in every nesting level within the Scope). + // We create phis eagerly for all the names we find, see dup(). + + // Save the current scope as the loop head + ScopeNode head = _scope.keep(); + // Clone the head Scope to create a new Scope for the body. + // Create phis eagerly as part of cloning + _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis + + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + 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); + + // 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. + head.endLoop(_scope, exit); + head.unkeep().kill(); + + _xScopes.pop(); // Cleanup + _xScopes.pop(); // Cleanup + + // At exit the false control is the current control, and + // the scope is the exit scope after the exit test. + return (_scope = exit); + } + + /** * Parses a statement * * <pre> @@ -369,7 +439,7 @@ public class Parser { // Require an exact match private void require(String syntax) { require(null, syntax); } - private Node require(Node n, String syntax) { + private <N extends Node> N require(N n, String syntax) { if (match(syntax)) return n; throw errorSyntax(syntax); } @@ -378,7 +448,7 @@ public class Parser { return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); } - static RuntimeException error(String errorMessage) { + public static RuntimeException error( String errorMessage ) { return new RuntimeException(errorMessage); } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index b37785f6..8f3e5a98 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; +import java.util.BitSet; + public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -10,9 +12,9 @@ public class AddNode extends Node { @Override public String glabel() { return "+"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("+")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("+"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index a9ec6838..0c32d50d 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + abstract public class BoolNode extends Node { public BoolNode(Node lhs, Node rhs) { @@ -18,9 +20,9 @@ abstract public class BoolNode extends Node { public String glabel() { return op(); } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append(op())); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append(op()), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 85277d82..b7ec8292 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer @@ -29,10 +31,12 @@ public class ConstantNode extends Node { public String uniqueName() { return "Con_" + _nid; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return _con.print(sb); } + @Override public boolean isMultiTail() { return true; } + @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 519a8c8a..7207fd48 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class DivNode extends Node { public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -11,9 +13,9 @@ public class DivNode extends Node { @Override public String glabel() { return "//"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("/")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("/"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 34846e99..0f414c08 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -4,6 +4,8 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + public class IfNode extends MultiNode { public IfNode(Node ctrl, Node pred) { @@ -14,12 +16,13 @@ public class IfNode extends MultiNode { public String label() { return "If"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("if( "); - return in(1)._print0(sb).append(" )"); + return in(1)._print0(sb, visited).append(" )"); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } public Node pred() { return in(1); } @@ -27,7 +30,8 @@ public class IfNode extends MultiNode { @Override public Type compute() { // If the If node is not reachable then neither is any following Proj - if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER; + if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) + return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java new file mode 100644 index 00000000..81f707ec --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.BitSet; + +public class LoopNode extends RegionNode { + + public LoopNode( Node entry ) { super(null,entry,null); } + + Node entry() { return in(1); } + Node back () { return in(2); } + + @Override + public String label() { return "Loop"; } + + @Override + public Type compute() { + return inProgress() ? Type.CONTROL : super.compute(); + } + + @Override + public Node idealize() { + return inProgress() ? null : super.idealize(); + } + + @Override Node idom() { return entry(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 0d59ef25..3d944fd4 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } @@ -11,8 +13,8 @@ public class MinusNode extends Node { @Override public String glabel() { return "-"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(-")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("(-"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 0380c079..2e701a4e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class MulNode extends Node { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -11,9 +13,9 @@ public class MulNode extends Node { @Override public String glabel() { return "*"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("*")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("*"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 39e8ff8d..5759a065 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -98,18 +98,51 @@ public abstract class Node { // tik-tok style; the common _print0 calls the per-Node _print1, which // calls back to _print0; public final String print() { - return _print0(new StringBuilder()).toString(); + return _print0(new StringBuilder(), new BitSet()).toString(); } - // This is the common print: check for DEAD and print "DEAD" else call the - // per-Node print1. - final StringBuilder _print0(StringBuilder sb) { + // This is the common print: check for repeats, check for DEAD and print + // "DEAD" else call the per-Node print1. + final StringBuilder _print0(StringBuilder sb, BitSet visited) { + if (visited.get(_nid)) + return sb.append(label()); + visited.set(_nid); return isDead() ? sb.append(uniqueName()).append(":DEAD") - : _print1(sb); + : _print1(sb, visited); + } + // Every Node implements this; a partial-line recursive print + abstract StringBuilder _print1(StringBuilder sb, BitSet visited); + + + // Print a node on 1 line, columnar aligned, as: + // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE + // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt + public void _printLine(StringBuilder sb ) { + sb.append("%4d %-7.7s ".formatted(_nid,label())); + if( _inputs==null ) { + sb.append("DEAD\n"); + return; + } + for( Node def : _inputs ) + sb.append(def==null ? "____ " : "%4d ".formatted(def._nid)); + for( int i = _inputs.size(); i<3; i++ ) + sb.append(" "); + sb.append(" [[ "); + for( Node use : _outputs ) + sb.append("%4d ".formatted(use._nid)); + int lim = 5 - Math.max(_inputs.size(),3); + for( int i = _outputs.size(); i<lim; i++ ) + sb.append(" "); + sb.append(" ]] "); + if( _type!= null ) _type.print(sb); + sb.append("\n"); } - // Every Node implements this. - abstract StringBuilder _print1(StringBuilder sb); + public boolean isMultiHead() { return false; } + public boolean isMultiTail() { return false; } + + // ------------------------------------------------------------------------ + // Graph Node & Edge manipulation /** * Gets the ith input node @@ -230,6 +263,20 @@ public abstract class Node { public <N extends Node> N keep() { addUse(null); return (N)this; } // Remove bogus null. public <N extends Node> N unkeep() { delUse(null); return (N)this; } + + + // Replace self with nnn in the graph, making 'this' go dead + void subsume( Node nnn ) { + assert nnn!=this; + while( nOuts() > 0 ) { + Node n = _outputs.removeLast(); + int idx = Utils.find(n._inputs, this); + n._inputs.set(idx,nnn); + nnn.addUse(n); + } + kill(); + } + // ------------------------------------------------------------------------ // Graph-based optimizations diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index e3683646..39df410d 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class NotNode extends Node { public NotNode(Node in) { super(null, in); } @@ -11,8 +13,8 @@ public class NotNode extends Node { @Override public String glabel() { return "!"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(!")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("(!"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 15088e08..2a4ff52a 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class PhiNode extends Node { final String _label; @@ -13,19 +15,27 @@ public class PhiNode extends Node { @Override public String glabel() { return "φ_"+_label; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( region().inProgress() ) + sb.append("Z"); sb.append("Phi("); - for( Node in : _inputs ) - in._print0(sb).append(","); + for( Node in : _inputs ) { + if (in == null) sb.append("____"); + else in._print0(sb, visited); + sb.append(","); + } sb.setLength(sb.length()-1); sb.append(")"); return sb; } - Node region() { return in(0); } + RegionNode region() { return (RegionNode)in(0); } + @Override public boolean isMultiTail() { return true; } @Override public Type compute() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -34,6 +44,9 @@ public class PhiNode extends Node { @Override public Node idealize() { + if( !(region() instanceof RegionNode r ) || r.inProgress() ) + return null; + // If we have only a single unique input, become it. Node live = singleUniqueInput(); if (live != null) @@ -79,5 +92,10 @@ public class PhiNode extends Node { return live; } - + @Override + boolean allCons() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return false; + return super.allCons(); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 85f28037..3c3f73b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + public class ProjNode extends Node { // Which slice of the incoming multi-part value @@ -21,9 +23,10 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index bb7998a3..acaadaf1 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,21 +3,26 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class RegionNode extends Node { - public RegionNode(Node... inputs) { super(inputs); } + + public RegionNode(Node... nodes) { super(nodes); } @Override public String label() { return "Region"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(label()).append(_nid); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } @Override public Type compute() { + if( inProgress() ) return Type.CONTROL; Type t = Type.XCONTROL; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -26,6 +31,7 @@ public class RegionNode extends Node { @Override public Node idealize() { + if( inProgress() ) return null; int path = findDeadInput(); if( path != 0 ) { for( Node phi : _outputs ) @@ -72,4 +78,9 @@ public class RegionNode extends Node { _idepth = lhs._idepth+1; return (_idom=lhs); } + + // True if last input is null + public final boolean inProgress() { + return in(nIns()-1) == null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 6130d050..312058b9 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; +import java.util.BitSet; + /** * The Return node has two inputs. The first input is a control node and the * second is the data node that supplies the return value. @@ -24,8 +26,8 @@ public class ReturnNode extends Node { public String label() { return "Return"; } @Override - StringBuilder _print1(StringBuilder sb) { - return expr()._print0(sb.append("return ")).append(";"); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return expr()._print0(sb.append("return "), visited).append(";"); } @Override public boolean isCFG() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index a7a04a42..a4fcbe65 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -33,22 +33,16 @@ public class ScopeNode extends Node { @Override public String label() { return "Scope"; } @Override - StringBuilder _print1(StringBuilder sb) { - sb.append(label()); - for( HashMap<String,Integer> scope : _scopes ) { - sb.append("["); - boolean first=true; - for( String name : scope.keySet() ) { - if( !first ) sb.append(", "); - first=false; - sb.append(name).append(":"); - Node n = in(scope.get(name)); - if( n==null ) sb.append("null"); - else n._print0(sb); - } - sb.append("]"); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("Scope[ "); + String[] names = reverseNames(); + for( int j=0; j<nIns(); j++ ) { + sb.append(names[j]).append(":"); + Node n = in(j); + n._print0(sb, visited).append(" "); } - return sb; + sb.setLength(sb.length()-1); + return sb.append("]"); } /** @@ -139,7 +133,8 @@ public class ScopeNode extends Node { * <p> * The new Scope is a full-fledged Node with proper use<->def edges. */ - public ScopeNode dup() { + public ScopeNode dup() { return dup(false); } + public ScopeNode dup(boolean loop) { ScopeNode dup = new ScopeNode(); // Our goals are: // 1) duplicate the name bindings of the ScopeNode across all stack levels @@ -147,9 +142,19 @@ public class ScopeNode extends Node { // 3) Ensure that the order of defs is the same to allow easy merging for( HashMap<String,Integer> syms : _scopes ) dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i<nIns(); i++ ) - dup.addDef(in(i)); + 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)); + } + } return dup; } @@ -172,4 +177,21 @@ public class ScopeNode extends Node { return r.unkeep().peephole(); } + // Merge the backedge scope into this loop head scope + // We set the second input to the phi from the back edge (i.e. loop body) + public void endLoop(ScopeNode back, ScopeNode exit ) { + Node ctrl = ctrl(); + 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); + } + back.kill(); // Loop backedge is dead + } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index c5a45876..01f1485a 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + /** * The Start node represents the start of the function. For now, we do not * have any inputs to Start because our function does not yet accept @@ -24,11 +26,12 @@ public class StartNode extends MultiNode { public String label() { return "Start"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(label()); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } @Override public TypeTuple compute() { return _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 01574dc7..417790d9 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class StopNode extends Node { public StopNode(Node... inputs) { super(inputs); @@ -13,11 +15,11 @@ public class StopNode extends Node { } @Override - StringBuilder _print1(StringBuilder sb) { - if( ret()!=null ) return ret()._print0(sb); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( ret()!=null ) return ret()._print0(sb, visited); sb.append("Stop[ "); for( Node ret : _inputs ) - ret._print0(sb).append(" "); + ret._print0(sb, visited).append(" "); return sb.append("]"); } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 475b3790..af66b950 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class SubNode extends Node { public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -11,9 +13,9 @@ public class SubNode extends Node { @Override public String glabel() { return "-"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("-")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("-"), visited); return sb.append(")"); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 10b67f5f..1e67cef5 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -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/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 134a8be2..5bb67817 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -19,7 +19,7 @@ else { a = arg-3; } return a;"""); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } @@ -34,7 +34,7 @@ if (arg == 1) { c = 4; } return c;""", TypeInteger.BOT); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return Phi(Region16,4,3);", ret.toString()); } @@ -62,7 +62,7 @@ if( arg==1 ) else b=a+1; return a+b;"""); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); } @@ -77,8 +77,8 @@ if( arg==1 ) else a=b+1; return a+b;"""); - StopNode ret = parser.parse(false); - assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString()); + StopNode ret = parser.parse(); + assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test @@ -127,7 +127,7 @@ if( arg==1 ) a=arg==3; } return a;"""); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 44b49d73..00d725bc 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -15,7 +15,7 @@ public class Chapter06Test { if( true ) return 2; return 1; """); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return 2;", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -29,7 +29,7 @@ if (arg) a = 2; return (arg < a) < 3; """); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); } @@ -44,7 +44,7 @@ else a=3; return a; """); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return 2;", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -64,7 +64,7 @@ if( a==2 ) else b=5; return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return Phi(Region32,42,5);", stop.toString()); } @@ -83,7 +83,7 @@ if( arg==2 ) else b=5; return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return Phi(Region28,2,5);", stop.toString()); } @@ -123,7 +123,7 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return 3;", stop.toString()); } @@ -143,7 +143,7 @@ else a=5; return a; """, TypeInteger.BOT); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); } @@ -163,7 +163,7 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return 3;", stop.toString()); } @@ -183,7 +183,7 @@ else a=5; return a; """, TypeInteger.constant(3)); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse(); assertEquals("return 4;", stop.toString()); } @@ -199,7 +199,7 @@ if( arg ) { } return a+b; """); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return Phi(Region22,4,1);", ret.toString()); } @@ -216,7 +216,7 @@ if( arg ) { } return a+b; """, TypeInteger.constant(1)); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return 4;", ret.toString()); } @@ -232,7 +232,7 @@ if( arg ) { } return a+b; """, TypeInteger.constant(0)); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.toString()); } @@ -250,8 +250,8 @@ if( arg ) { } return a+b+c; """); - StopNode ret = parser.parse(false); - assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region33,3,1));", ret.toString()); + StopNode ret = parser.parse(); + assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); } @@ -269,7 +269,7 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(1)); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return 6;", ret.toString()); } @@ -287,7 +287,7 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(2)); - StopNode ret = parser.parse(false); + StopNode ret = parser.parse(); assertEquals("return 5;", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java new file mode 100644 index 00000000..189fcf66 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -0,0 +1,234 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter07Test { + + @Test + public void testExample() { + Parser parser = new Parser( + """ + while(arg < 10) { + arg = arg + 1; + } + return arg; + """); + Node._disablePeephole = true; + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testRegression() { + Parser parser = new Parser( +""" +int a = 1; +if(arg){}else{ + while(a < 10) { + a = a + 1; + } +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + } + + @Test + public void testWhileNested() { + Parser parser = new Parser( +""" +int sum = 0; +int i = 0; +while(i < arg) { + i = i + 1; + int j = 0; + while( j < arg ) { + sum = sum + j; + j = j + 1; + } +} +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()); + } + + @Test + public void testWhileScope() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; +} +return b; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhileNestedIfAndInc() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; + b = b + 1; + a = a + 1; +} +return b; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testWhile() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhilePeep() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile2() { + Parser parser = new Parser( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhile2Peep() { + Parser parser = new Parser( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile3() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhile3Peep() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile4() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + Node._disablePeephole = true; + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,1,((Phi_a+1)+2));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + Node._disablePeephole = false; + } + + @Test + public void testWhile4Peep() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + +} |
