From f4d0e1583b9ae0237422640d8ee7eea5ce8aad6f 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 Co-authored-by: Jun Kawasaki --- docs/chapter07/07-grammar.ja.md | 91 +++++++++++++++ docs/chapter07/07-grammar.md | 86 ++++++++++++++ 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.ja.md | 229 ++++++++++++++++++++++++++++++++++++ docs/chapter07/README.md | 250 ++++++++++++++++++++++++++++++++++++++++ 17 files changed, 1735 insertions(+) create mode 100644 docs/chapter07/07-grammar.ja.md 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.ja.md create mode 100644 docs/chapter07/README.md (limited to 'docs/chapter07') diff --git a/docs/chapter07/07-grammar.ja.md b/docs/chapter07/07-grammar.ja.md new file mode 100644 index 00000000..a49e31e5 --- /dev/null +++ b/docs/chapter07/07-grammar.ja.md @@ -0,0 +1,91 @@ +# 第7章の文法 + +[English](07-grammar.md) | 日本語 + +この文書は [原文](07-grammar.md) の日本語訳です。 + + +[第7章に戻る](README.ja.md) + +```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-grammar.md b/docs/chapter07/07-grammar.md new file mode 100644 index 00000000..c09f499c --- /dev/null +++ b/docs/chapter07/07-grammar.md @@ -0,0 +1,86 @@ +# Grammar for Chapter 7 + +English | [日本語](07-grammar.ja.md) + +```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.ja.md b/docs/chapter07/README.ja.md new file mode 100644 index 00000000..67d59c1b --- /dev/null +++ b/docs/chapter07/README.ja.md @@ -0,0 +1,229 @@ +# 第7章: While 文 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第6章](../chapter06/README.ja.md) | +[次の章: 第8章](../chapter08/README.ja.md) + +# 目次 + +1. [バックエッジの扱い](#バックエッジの扱い) +2. [新しいノード型](#新しいノード型) +3. [詳細な手順](#詳細な手順) +4. [可視化](#可視化) +5. [入れ子のループ](#入れ子のループ) +6. [If を内包するループ](#if-を内包するループ) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter07) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter06...linear-chapter07) することもできます。 + +この章では `while` 文を導入します。 + +この章の [完全な言語文法](07-grammar.ja.md) はこちらです。 + +## バックエッジの扱い + +ループ構造によって生じる難しさは、反復時に変数がループ本体へ戻ってくることです。たとえば、次のコードです。 + +```java +while(arg < 10) { + arg = arg + 1; +} +return arg; +``` + +変数 `arg` にはループ本体内で新しい値が代入され、その値がループ本体へ戻ります。 + +一般に、ループ構造を次のように書き換えます。 + +```java +loop_head: +if( !(arg < 10) ) + goto loop_exit; +arg = arg + 1; +goto loop_head; + +loop_exit: +``` + +これは説明のためのもので、この言語にはラベルや `goto` 文はありません。 + +SSA[^1] の観点では、`arg` が戻ってくるため、先頭に `phi` ノードが必要です。概念的には、次のような結果にしたいのです。 + +```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: +``` + +`arg2` の phi が `arg3` を参照することに注目してください。`while` ループの条件を解析する時点では、`arg3` はまだわかりません。常に SSA 形式である Sea of Nodes グラフを正しく構築するために解決すべき問題の核心は、ここにあります。 + +[第5章](../chapter05/README.ja.md) を思い出してください。`if` 文の解析では、`if` の条件を過ぎるときにシンボルテーブルを複製します。後で2組のシンボルテーブルを `Region` でマージし、`if` 文の2つの分岐内で定義が変わったすべての名前に phi を作ります。`if` 文の場合、マージする定義がすでにわかっているマージ地点で phi を作ります。 + +ループ構造に対する基本的な考えは、ループ本体内でどの名前が再定義されるかわからないため、ループの `if` 条件に入る *前に*、シンボルテーブル内のすべての名前に対して積極的に phi を作ることです。ループが終わると、さかのぼって不要な phi を削除します。これを「eager phi（先行生成する phi）」方式と呼びます。[^2] + +[第8章](../chapter08/README.ja.md) では、名前の再定義に遭遇したときだけ phi を作る「lazy phi（遅延生成する phi）」方式を実装します。 + +## 新しいノード型 + +ノードの一覧は [第5章](../chapter05/README.ja.md) と同じですが、必要な追加ロジックの一部をより適切にカプセル化するため、`Region` のサブタイプ `Loop` を作ります。Loop と Phi のピープホール最適化では、バックエッジが必要な書き換えを、ループ本体の解析が完了するまで延期します。ほかのノードは通常どおり最適化を続けます。 + +## 詳細な手順 + +1. まず、`Region` の新しいサブクラス `Loop` を作ります。`Loop` は2つの制御入力を取ります。最初は入口、すなわち `$ctrl` の現在の束縛です。2つ目（`null`）は、ループ解析後に設定するバックエッジのためのプレースホルダーです。バックエッジの欠如は、Loop と対応する Phi が未完成であることを示します。そのため、それらのピープホール最適化は、各書き換えに必要な入力がそろうまで待ちます。 + + ```java + ctrl(new LoopNode(ctrl(),null).peephole()); + ``` + + 新しく作った Region が現在の制御になります。 + +2. 現在の Scope ノードを複製します。スコープ内のすべての階層のシンボルを複製し、`$ctrl` の束縛を除くすべてのシンボルに phi を作ります。 + + ```java + // Make a new Scope for the body. + _scope = _scope.dup(true); + ``` + + `dup` の呼び出しに引数 `true` を渡すことに注目してください。これが phi の作成を引き起こします。`dup()` メソッドで phi を作るコードを次に示します。 + + ```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. 現在のスコープをもう一度複製します。これはループ終了後に生き続ける出口スコープなので、出口スコープの `$ctrl` を `False` 射影に設定します。出口スコープは、ループの条件式の副作用も取り込みます。 + + ```java + // The exit scope, accounting for any side effects in the predicate + var exit = _scope.dup(); + exit.ctrl(ifF); + ``` + +5. 制御を `True` 射影に設定し、ループ本体を解析します。 + + ```java + // Parse the true side, which corresponds to loop body + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + ``` + +6. ループ本体の解析後、先ほど作ったすべての phi に戻って処理します。 + + ```java + // The true branch loops back, so whatever is current control gets + // added to head loop as input + head.endLoop(_scope, exit); + ``` + + `endLoop` メソッドは、ループ Region の2つ目の制御をバックエッジの制御に設定します。続いてすべての phi をたどり、それぞれの2つ目のデータ入力をループ本体の対応する項目に設定します。使われなかった phi はピープホール最適化され、元の入力に置き換わります。 + + ```java + Node ctrl = ctrl(); + ctrl.set_def(2,back.ctrl()); + 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