From 4e18ea024240e20592d459caf383acdbda5e2e9e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 3 Dec 2023 23:23:04 +0000 Subject: Chapter 7: While Statement MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher --- docs/chapter07/07-grammar.md | 84 ++++++++++++++ docs/chapter07/07-graph1.gv | 107 ++++++++++++++++++ docs/chapter07/07-graph1.json | 27 +++++ docs/chapter07/07-graph1.svg | 122 +++++++++++++++++++++ docs/chapter07/07-graph2.gv | 62 +++++++++++ docs/chapter07/07-graph2.json | 26 +++++ docs/chapter07/07-graph2.svg | 119 ++++++++++++++++++++ docs/chapter07/07-graph3.gv | 108 ++++++++++++++++++ docs/chapter07/07-graph3.json | 40 +++++++ docs/chapter07/07-graph3.svg | 175 +++++++++++++++++++++++++++++ docs/chapter07/07-graph4.gv | 96 ++++++++++++++++ docs/chapter07/07-graph4.json | 37 +++++++ docs/chapter07/07-graph4.svg | 159 +++++++++++++++++++++++++++ docs/chapter07/Makefile | 1 + docs/chapter07/README.md | 248 ++++++++++++++++++++++++++++++++++++++++++ 15 files changed, 1411 insertions(+) create mode 100644 docs/chapter07/07-grammar.md create mode 100644 docs/chapter07/07-graph1.gv create mode 100644 docs/chapter07/07-graph1.json create mode 100644 docs/chapter07/07-graph1.svg create mode 100644 docs/chapter07/07-graph2.gv create mode 100644 docs/chapter07/07-graph2.json create mode 100644 docs/chapter07/07-graph2.svg create mode 100644 docs/chapter07/07-graph3.gv create mode 100644 docs/chapter07/07-graph3.json create mode 100644 docs/chapter07/07-graph3.svg create mode 100644 docs/chapter07/07-graph4.gv create mode 100644 docs/chapter07/07-graph4.json create mode 100644 docs/chapter07/07-graph4.svg create mode 100644 docs/chapter07/Makefile create mode 100644 docs/chapter07/README.md (limited to 'docs/chapter07') diff --git a/docs/chapter07/07-grammar.md b/docs/chapter07/07-grammar.md new file mode 100644 index 00000000..21c5ad0a --- /dev/null +++ b/docs/chapter07/07-grammar.md @@ -0,0 +1,84 @@ +# Grammar for Chapter 6 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter07/07-graph1.gv b/docs/chapter07/07-graph1.gv new file mode 100644 index 00000000..5957a931 --- /dev/null +++ b/docs/chapter07/07-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter07 { +/* +while(arg < 10) { + arg = arg + 1; + +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + 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=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + { rank=same; Loop6;Phi_arg8;} + } + node [shape=plaintext]; + subgraph cluster_Scope7_1 { + Scope7_1 [label=< + + +
2
>]; + subgraph cluster_Scope7_2 { + Scope7_2 [label=< + + +
1
>]; + subgraph cluster_Scope7_3 { + Scope7_3 [label=< + + +
0$ctrlarg
>]; + } + } + } + node [shape=plaintext]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1
>]; + subgraph cluster_Scope1_2 { + Scope1_2 [label=< + + +
0$ctrlarg
>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope14_1 { + Scope14_1 [label=< + + +
1
>]; + subgraph cluster_Scope14_2 { + Scope14_2 [label=< + + +
0$ctrlarg
>]; + } + } + 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.json b/docs/chapter07/07-graph1.json new file mode 100644 index 00000000..0f2c6c4d --- /dev/null +++ b/docs/chapter07/07-graph1.json @@ -0,0 +1,27 @@ +{ + "ver": 1, + "comp": "chapter07/docs/07-graph1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 18, "role": "ASSOC", "label": "3: $ctrl"}, {"idx": 1, "def": 16, "role": "ASSOC", "label": "3: arg"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 5, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 6, "role": "ASSOC", "label": "2: $ctrl"}, {"idx": 1, "def": 8, "role": "ASSOC", "label": "2: arg"}], "proj": null}, + {"id": 6, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 14, "role": "CTRL", "label": null}], "proj": null}, + {"id": 8, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 6, "role": "ASSOC", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "10", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 10, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 19, "role": "ASSOC", "label": "2: $ctrl"}, {"idx": 1, "def": 8, "role": "ASSOC", "label": "2: arg"}], "proj": null}, + {"id": 14, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 15, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 18, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 0}}, + {"id": 19, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 1}} + ], + "groups": [ + {"id": 6, "par": 0, "nodes": [6, 8]} + ] +} diff --git a/docs/chapter07/07-graph1.svg b/docs/chapter07/07-graph1.svg new file mode 100644 index 00000000..d5de1351 --- /dev/null +++ b/docs/chapter07/07-graph1.svg @@ -0,0 +1,122 @@ +#1[0] → #18 · ASSOC · 3: $ctrl#1[1] → #16 · ASSOC · 3: arg#5[0] → #6 · ASSOC · 2: $ctrl#5[1] → #8 · ASSOC · 2: arg#6[1] → #14 · CTRL#8[1] → #17 · DATA#10[1] → #8 · DATA#10[2] → #9 · DATA#11[0] → #6 · CTRL#11[1] → #10 · DATA#12[0] → #19 · ASSOC · 2: $ctrl#12[1] → #8 · ASSOC · 2: arg#16[1] → #8 · DATA#16[2] → #15 · DATAScope  #1#1 Scope +Type not computed + +[0] → #18 ASSOC 3: $ctrl +[1] → #16 ASSOC 3: arg3: $ctrl3: arg01Start  #2#2 Start +Type not computed + +Scope  #5#5 Scope +Type not computed + +[0] → #6 ASSOC 2: $ctrl +[1] → #8 ASSOC 2: arg2: $ctrl2: arg01Loop  #6#6 Loop +Type not computed + +[0] → — DATA +[1] → #14 CTRL01φ_arg  #8#8 φ_arg +Type not computed + +[0] → #6 ASSOC +[1] → #17 DATA[0] → #60110  #9#9 10 +Type not computed + +<  #10#10 < +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #9 DATA012If  #11#11 If +Type not computed + +[0] → #6 CTRL +[1] → #10 DATA01Scope  #12#12 Scope +Type not computed + +[0] → #19 ASSOC 2: $ctrl +[1] → #8 ASSOC 2: arg2: $ctrl2: arg01$ctrl  #14/0#14 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL1  #15#15 1 +Type not computed + ++  #16#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 DATA012arg  #17/1#17 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #18/0#18 True +Projection 0 of #11 +Type not computed + +[0] → #11 CTRLFalse  #19/1#19 False +Projection 1 of #11 +Type not computed + +[0] → #11 CTRLLoop  #6Loop · 2 nodes−Fold region diff --git a/docs/chapter07/07-graph2.gv b/docs/chapter07/07-graph2.gv new file mode 100644 index 00000000..4ff5ff35 --- /dev/null +++ b/docs/chapter07/07-graph2.gv @@ -0,0 +1,62 @@ +digraph chapter07 { +/* +while(arg < 10) { + arg = arg + 1; + +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + 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=< + + + +
If
+ + +
TrueFalse
+
> + ]; + 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.json b/docs/chapter07/07-graph2.json new file mode 100644 index 00000000..cc0e6d6c --- /dev/null +++ b/docs/chapter07/07-graph2.json @@ -0,0 +1,26 @@ +{ + "ver": 1, + "comp": "chapter07/docs/07-graph2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 0}}, + {"id": 6, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 7, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 1}}, + {"id": 8, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 6, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "10", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 10, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 6, "par": 0, "nodes": [5, 6, 7, 8, 10, 11, 16]} + ] +} diff --git a/docs/chapter07/07-graph2.svg b/docs/chapter07/07-graph2.svg new file mode 100644 index 00000000..d2488859 --- /dev/null +++ b/docs/chapter07/07-graph2.svg @@ -0,0 +1,119 @@ +#3[0] → #17 · CTRL#6[1] → #1 · CTRL#6[2] → #5 · CTRL#8[1] → #4 · DATA#8[2] → #16 · DATA#10[1] → #8 · DATA#10[2] → #9 · DATA#11[0] → #6 · CTRL#11[1] → #10 · DATA#16[1] → #8 · DATA#16[2] → #15 · DATA#17[0] → #7 · CTRL#17[1] → #8 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #17 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #11 +Type not computed + +[0] → #11 CTRLLoop  #6#6 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #5 CTRL012False  #7/1#7 False +Projection 1 of #11 +Type not computed + +[0] → #11 CTRLφ_arg  #8#8 φ_arg +Type not computed + +[0] → #6 ASSOC +[1] → #4 DATA +[2] → #16 DATA[0] → #601210  #9#9 10 +Type not computed + +<  #10#10 < +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #9 DATA012If  #11#11 If +Type not computed + +[0] → #6 CTRL +[1] → #10 DATA011  #15#15 1 +Type not computed + ++  #16#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 DATA012Return  #17#17 Return +Type not computed + +[0] → #7 CTRL +[1] → #8 DATA01Loop  #6Loop · 7 nodes−Fold region 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=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + 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=< + + + +
If
+ + +
TrueFalse
+
> + ]; + 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=< + + + +
If
+ + +
TrueFalse
+
> + ]; + 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.json b/docs/chapter07/07-graph3.json new file mode 100644 index 00000000..26dbc457 --- /dev/null +++ b/docs/chapter07/07-graph3.json @@ -0,0 +1,40 @@ +{ + "ver": 1, + "comp": "chapter07/docs/07-graph3.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 35, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}], "proj": {"par": 14, "idx": 0}}, + {"id": 6, "label": "0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 15, "role": "CTRL", "label": null}], "proj": null}, + {"id": 9, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}], "proj": {"par": 14, "idx": 1}}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 0}}, + {"id": 11, "label": "φ_sum", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 8, "role": "ASSOC", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "φ_i", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 8, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 19, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 1}}, + {"id": 18, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 19, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 21, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, + {"id": 24, "label": "φ_sum", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}, {"idx": 2, "def": 32, "role": "DATA", "label": null}], "proj": null}, + {"id": 26, "label": "φ_j", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}, {"idx": 2, "def": 34, "role": "DATA", "label": null}], "proj": null}, + {"id": 27, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 26, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 28, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}], "proj": null}, + {"id": 32, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 26, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}, + {"id": 33, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 34, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 26, "role": "DATA", "label": null}, {"idx": 2, "def": 33, "role": "DATA", "label": null}], "proj": null}, + {"id": 35, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [5, 8, 9, 11, 12, 13, 14, 19]}, + {"id": 21, "par": 8, "nodes": [10, 15, 21, 24, 26, 27, 28, 32, 34]} + ] +} diff --git a/docs/chapter07/07-graph3.svg b/docs/chapter07/07-graph3.svg new file mode 100644 index 00000000..e8ca3ba5 --- /dev/null +++ b/docs/chapter07/07-graph3.svg @@ -0,0 +1,175 @@ +#3[0] → #35 · CTRL#8[1] → #1 · CTRL#8[2] → #15 · CTRL#11[1] → #6 · DATA#11[2] → #24 · DATA#12[1] → #7 · DATA#12[2] → #19 · DATA#13[1] → #12 · DATA#13[2] → #4 · DATA#14[0] → #8 · CTRL#14[1] → #13 · DATA#19[1] → #12 · DATA#19[2] → #18 · DATA#21[1] → #5 · CTRL#21[2] → #10 · CTRL#24[1] → #11 · DATA#24[2] → #32 · DATA#26[1] → #20 · DATA#26[2] → #34 · DATA#27[1] → #26 · DATA#27[2] → #4 · DATA#28[0] → #21 · CTRL#28[1] → #27 · DATA#32[1] → #26 · DATA#32[2] → #24 · DATA#34[1] → #26 · DATA#34[2] → #33 · DATA#35[0] → #9 · CTRL#35[1] → #11 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #35 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #14 +Type not computed + +[0] → #14 CTRL0  #6#6 0 +Type not computed + +0  #7#7 0 +Type not computed + +Loop  #8#8 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #15 CTRL012False  #9/1#9 False +Projection 1 of #14 +Type not computed + +[0] → #14 CTRLTrue  #10/0#10 True +Projection 0 of #28 +Type not computed + +[0] → #28 CTRLφ_sum  #11#11 φ_sum +Type not computed + +[0] → #8 ASSOC +[1] → #6 DATA +[2] → #24 DATA[0] → #8012φ_i  #12#12 φ_i +Type not computed + +[0] → #8 ASSOC +[1] → #7 DATA +[2] → #19 DATA[0] → #8012<  #13#13 < +Type not computed + +[0] → — DATA +[1] → #12 DATA +[2] → #4 DATA012If  #14#14 If +Type not computed + +[0] → #8 CTRL +[1] → #13 DATA01False  #15/1#15 False +Projection 1 of #28 +Type not computed + +[0] → #28 CTRL1  #18#18 1 +Type not computed + ++  #19#19 + +Type not computed + +[0] → — DATA +[1] → #12 DATA +[2] → #18 DATA0120  #20#20 0 +Type not computed + +Loop  #21#21 Loop +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #10 CTRL012φ_sum  #24#24 φ_sum +Type not computed + +[0] → #21 ASSOC +[1] → #11 DATA +[2] → #32 DATA[0] → #21012φ_j  #26#26 φ_j +Type not computed + +[0] → #21 ASSOC +[1] → #20 DATA +[2] → #34 DATA[0] → #21012<  #27#27 < +Type not computed + +[0] → — DATA +[1] → #26 DATA +[2] → #4 DATA012If  #28#28 If +Type not computed + +[0] → #21 CTRL +[1] → #27 DATA01+  #32#32 + +Type not computed + +[0] → — DATA +[1] → #26 DATA +[2] → #24 DATA0121  #33#33 1 +Type not computed + ++  #34#34 + +Type not computed + +[0] → — DATA +[1] → #26 DATA +[2] → #33 DATA012Return  #35#35 Return +Type not computed + +[0] → #9 CTRL +[1] → #11 DATA01Loop  #8Loop · 17 nodes−Fold regionLoop  #21Loop · 9 nodes−Fold region 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=< + + + +
Start
+ + +
$ctrl
+
> + ]; + 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=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_19 [ label="2" ]; + EQ20 [ label="==" ]; + If21 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + 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.json b/docs/chapter07/07-graph4.json new file mode 100644 index 00000000..a9848505 --- /dev/null +++ b/docs/chapter07/07-graph4.json @@ -0,0 +1,37 @@ +{ + "ver": 1, + "comp": "chapter07/docs/07-graph4.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 30, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}], "proj": {"par": 15, "idx": 0}}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}], "proj": {"par": 15, "idx": 1}}, + {"id": 6, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 27, "role": "CTRL", "label": null}], "proj": null}, + {"id": 9, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}], "proj": {"par": 21, "idx": 0}}, + {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}], "proj": {"par": 21, "idx": 1}}, + {"id": 11, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 8, "role": "ASSOC", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 28, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 8, "role": "ASSOC", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}, {"idx": 2, "def": 29, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "10", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 20, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}, {"idx": 2, "def": 19, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 26, "label": "4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 27, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 9, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, + {"id": 28, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 27, "role": "ASSOC", "label": null}, {"idx": 1, "def": 25, "role": "DATA", "label": null}, {"idx": 2, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 29, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 27, "role": "ASSOC", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 26, "role": "DATA", "label": null}], "proj": null}, + {"id": 30, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [4, 5, 8, 11, 12, 14, 15]}, + {"id": 21, "par": 8, "nodes": [9, 10, 20, 21, 27, 28, 29]} + ] +} diff --git a/docs/chapter07/07-graph4.svg b/docs/chapter07/07-graph4.svg new file mode 100644 index 00000000..09cea0b4 --- /dev/null +++ b/docs/chapter07/07-graph4.svg @@ -0,0 +1,159 @@ +#3[0] → #30 · CTRL#8[1] → #1 · CTRL#8[2] → #27 · CTRL#11[1] → #6 · DATA#11[2] → #28 · DATA#12[1] → #7 · DATA#12[2] → #29 · DATA#14[1] → #11 · DATA#14[2] → #13 · DATA#15[0] → #8 · CTRL#15[1] → #14 · DATA#20[1] → #11 · DATA#20[2] → #19 · DATA#21[0] → #4 · CTRL#21[1] → #20 · DATA#27[1] → #9 · CTRL#27[2] → #10 · CTRL#28[1] → #25 · DATA#28[2] → #11 · DATA#29[1] → #12 · DATA#29[2] → #26 · DATA#30[0] → #5 · CTRL#30[1] → #12 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #30 CTRL0True  #4/0#4 True +Projection 0 of #15 +Type not computed + +[0] → #15 CTRLFalse  #5/1#5 False +Projection 1 of #15 +Type not computed + +[0] → #15 CTRL1  #6#6 1 +Type not computed + +2  #7#7 2 +Type not computed + +Loop  #8#8 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #27 CTRL012True  #9/0#9 True +Projection 0 of #21 +Type not computed + +[0] → #21 CTRLFalse  #10/1#10 False +Projection 1 of #21 +Type not computed + +[0] → #21 CTRLφ_a  #11#11 φ_a +Type not computed + +[0] → #8 ASSOC +[1] → #6 DATA +[2] → #28 DATA[0] → #8012φ_b  #12#12 φ_b +Type not computed + +[0] → #8 ASSOC +[1] → #7 DATA +[2] → #29 DATA[0] → #801210  #13#13 10 +Type not computed + +<  #14#14 < +Type not computed + +[0] → — DATA +[1] → #11 DATA +[2] → #13 DATA012If  #15#15 If +Type not computed + +[0] → #8 CTRL +[1] → #14 DATA012  #19#19 2 +Type not computed + +==  #20#20 == +Type not computed + +[0] → — DATA +[1] → #11 DATA +[2] → #19 DATA012If  #21#21 If +Type not computed + +[0] → #4 CTRL +[1] → #20 DATA013  #25#25 3 +Type not computed + +4  #26#26 4 +Type not computed + +Region  #27#27 Region +Type not computed + +[0] → — DATA +[1] → #9 CTRL +[2] → #10 CTRL012φ_a  #28#28 φ_a +Type not computed + +[0] → #27 ASSOC +[1] → #25 DATA +[2] → #11 DATA[0] → #27012φ_b  #29#29 φ_b +Type not computed + +[0] → #27 ASSOC +[1] → #12 DATA +[2] → #26 DATA[0] → #27012Return  #30#30 Return +Type not computed + +[0] → #5 CTRL +[1] → #12 DATA01Loop  #8Loop · 14 nodes−Fold regionIf  #21If · 7 nodes−Fold region diff --git a/docs/chapter07/Makefile b/docs/chapter07/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter07/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter07/README.md b/docs/chapter07/README.md new file mode 100644 index 00000000..4527707e --- /dev/null +++ b/docs/chapter07/README.md @@ -0,0 +1,248 @@ +# Chapter 7: While Statement + +[Previous: Chapter 6](../chapter06/README.md) | +[Next: Chapter 8](../chapter08/README.md) + +# 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) +6. [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. Loop and Phi peepholes defer rewrites that need the back edge +until we complete parsing the loop body. Other nodes continue to optimize normally. + +## 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 the loop is parsed. A missing back edge marks the Loop and associated Phis as incomplete, + so their peepholes wait for the inputs needed by each rewrite. + + ```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 within 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; ikeep().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