diff options
| author | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2023-12-03 23:23:04 +0000 |
|---|---|---|
| committer | Dibyendu Majumdar <mobile@majumdar.org.uk> | 2025-01-09 12:19:55 -0800 |
| commit | 1394f508523111e2a51d7d7737d99893e2af228b (patch) | |
| tree | ffac1e06aa07151f239a6f2f4983ff9da4a4aac4 /docs | |
| parent | 7cdc3a61a6ed9dc6d68d731d1d2777d18ddaba27 (diff) | |
| download | Simple-1394f508523111e2a51d7d7737d99893e2af228b.tar.gz Simple-1394f508523111e2a51d7d7737d99893e2af228b.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: Robert Obkircher <robert.obkircher@gmail.com>
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/chapter07/07-grammar.md | 88 | ||||
| -rw-r--r-- | docs/chapter07/07-graph1.gv | 107 | ||||
| -rw-r--r-- | docs/chapter07/07-graph1.svg | 268 | ||||
| -rw-r--r-- | docs/chapter07/07-graph2.gv | 62 | ||||
| -rw-r--r-- | docs/chapter07/07-graph2.svg | 184 | ||||
| -rw-r--r-- | docs/chapter07/07-graph3.gv | 108 | ||||
| -rw-r--r-- | docs/chapter07/07-graph3.svg | 373 | ||||
| -rw-r--r-- | docs/chapter07/07-graph4.gv | 96 | ||||
| -rw-r--r-- | docs/chapter07/07-graph4.svg | 329 | ||||
| -rw-r--r-- | docs/chapter07/Makefile | 12 | ||||
| -rw-r--r-- | docs/chapter07/README.md | 233 |
11 files changed, 1860 insertions, 0 deletions
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..203e5314 --- /dev/null +++ b/docs/chapter07/README.md @@ -0,0 +1,233 @@ +# Chapter 7: While Statement + +In this chapter we introduce the `while` statement. + +Here is the [complete language grammar](07-grammar.md) for this chapter. + +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. + +## 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. |
