From 67ee27bfb29036efe7b154f633817aa152182684 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 3 Dec 2023 23:23:04 +0000 Subject: Chapter 8: Lazy Phis, Break, Continue, and Evaluator MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Thalia Archibald Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@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 Co-authored-by: Darrick Wiebe --- docs/chapter08/08-grammar.ja.md | 101 +++++++++++++ docs/chapter08/08-grammar.md | 96 ++++++++++++ docs/chapter08/08-graph1.gv | 107 +++++++++++++ docs/chapter08/08-graph1.json | 39 +++++ docs/chapter08/08-graph1.svg | 174 +++++++++++++++++++++ docs/chapter08/08-graph2.gv | 103 +++++++++++++ docs/chapter08/08-graph2.json | 39 +++++ docs/chapter08/08-graph2.svg | 169 +++++++++++++++++++++ docs/chapter08/08-graph3.gv | 111 ++++++++++++++ docs/chapter08/08-graph3.json | 40 +++++ docs/chapter08/08-graph3.svg | 179 ++++++++++++++++++++++ docs/chapter08/Makefile | 1 + docs/chapter08/README.ja.md | 264 ++++++++++++++++++++++++++++++++ docs/chapter08/README.md | 327 ++++++++++++++++++++++++++++++++++++++++ 14 files changed, 1750 insertions(+) create mode 100644 docs/chapter08/08-grammar.ja.md create mode 100644 docs/chapter08/08-grammar.md create mode 100644 docs/chapter08/08-graph1.gv create mode 100644 docs/chapter08/08-graph1.json create mode 100644 docs/chapter08/08-graph1.svg create mode 100644 docs/chapter08/08-graph2.gv create mode 100644 docs/chapter08/08-graph2.json create mode 100644 docs/chapter08/08-graph2.svg create mode 100644 docs/chapter08/08-graph3.gv create mode 100644 docs/chapter08/08-graph3.json create mode 100644 docs/chapter08/08-graph3.svg create mode 100644 docs/chapter08/Makefile create mode 100644 docs/chapter08/README.ja.md create mode 100644 docs/chapter08/README.md (limited to 'docs/chapter08') diff --git a/docs/chapter08/08-grammar.ja.md b/docs/chapter08/08-grammar.ja.md new file mode 100644 index 00000000..d88eb1c1 --- /dev/null +++ b/docs/chapter08/08-grammar.ja.md @@ -0,0 +1,101 @@ +# 第8章の文法 + +[English](08-grammar.md) | 日本語 + +この文書は [原文](08-grammar.md) の日本語訳です。 + + +[第8章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +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/chapter08/08-grammar.md b/docs/chapter08/08-grammar.md new file mode 100644 index 00000000..0c1d05da --- /dev/null +++ b/docs/chapter08/08-grammar.md @@ -0,0 +1,96 @@ +# Grammar for Chapter 8 + +English | [日本語](08-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +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/chapter08/08-graph1.gv b/docs/chapter08/08-graph1.gv new file mode 100644 index 00000000..604ee0fe --- /dev/null +++ b/docs/chapter08/08-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
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="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg35 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Region39 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return40 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;Phi_arg35;} + { rank=same; Region39;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return40[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region39[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If11:p1[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Phi_arg35 -> Region34 [style=dotted taillabel=0]; + Phi_arg35 -> Phi_arg8[taillabel=1]; + Phi_arg35 -> Add16[taillabel=2 constraint=false]; + Region39 -> If19:p0[taillabel=1 color=red]; + Region39 -> If28:p1[taillabel=2 color=red]; + Return40 -> Region34[taillabel=0 color=red]; + Return40 -> Phi_arg35[taillabel=1]; +} diff --git a/docs/chapter08/08-graph1.json b/docs/chapter08/08-graph1.json new file mode 100644 index 00000000..130a79bd --- /dev/null +++ b/docs/chapter08/08-graph1.json @@ -0,0 +1,39 @@ +{ + "ver": 1, + "comp": "chapter08/docs/08-graph1.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": 40, "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": 39, "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": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 0}}, + {"id": 13, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 1}}, + {"id": 14, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "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": "5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 1}}, + {"id": 26, "label": "6", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 27, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 26, "role": "DATA", "label": null}], "proj": null}, + {"id": 28, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}], "proj": null}, + {"id": 34, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 7, "role": "CTRL", "label": null}, {"idx": 2, "def": 14, "role": "CTRL", "label": null}], "proj": null}, + {"id": 35, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 34, "role": "ASSOC", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 39, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "CTRL", "label": null}, {"idx": 2, "def": 20, "role": "CTRL", "label": null}], "proj": null}, + {"id": 40, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 34, "role": "CTRL", "label": null}, {"idx": 1, "def": 35, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 6, "par": 0, "nodes": [5, 6, 7, 8, 10, 11, 12, 13, 14, 18, 19, 20, 27, 28, 39]} + ] +} diff --git a/docs/chapter08/08-graph1.svg b/docs/chapter08/08-graph1.svg new file mode 100644 index 00000000..c398607a --- /dev/null +++ b/docs/chapter08/08-graph1.svg @@ -0,0 +1,174 @@ +#3[0] → #40 · CTRL#6[1] → #1 · CTRL#6[2] → #39 · 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#18[1] → #16 · DATA#18[2] → #17 · DATA#19[0] → #5 · CTRL#19[1] → #18 · DATA#27[1] → #16 · DATA#27[2] → #26 · DATA#28[0] → #13 · CTRL#28[1] → #27 · DATA#34[1] → #7 · CTRL#34[2] → #14 · CTRL#35[1] → #8 · DATA#35[2] → #16 · DATA#39[1] → #12 · CTRL#39[2] → #20 · CTRL#40[0] → #34 · CTRL#40[1] → #35 · 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] → #40 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] → #39 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 DATA01True  #12/0#12 True +Projection 0 of #19 +Type not computed + +[0] → #19 CTRLFalse  #13/1#13 False +Projection 1 of #19 +Type not computed + +[0] → #19 CTRLTrue  #14/0#14 True +Projection 0 of #28 +Type not computed + +[0] → #28 CTRL1  #15#15 1 +Type not computed + ++  #16#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 DATA0125  #17#17 5 +Type not computed + +==  #18#18 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #17 DATA012If  #19#19 If +Type not computed + +[0] → #5 CTRL +[1] → #18 DATA01False  #20/1#20 False +Projection 1 of #28 +Type not computed + +[0] → #28 CTRL6  #26#26 6 +Type not computed + +==  #27#27 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #26 DATA012If  #28#28 If +Type not computed + +[0] → #13 CTRL +[1] → #27 DATA01Region  #34#34 Region +Type not computed + +[0] → — DATA +[1] → #7 CTRL +[2] → #14 CTRL012φ_arg  #35#35 φ_arg +Type not computed + +[0] → #34 ASSOC +[1] → #8 DATA +[2] → #16 DATA[0] → #34012Region  #39#39 Region +Type not computed + +[0] → — DATA +[1] → #12 CTRL +[2] → #20 CTRL012Return  #40#40 Return +Type not computed + +[0] → #34 CTRL +[1] → #35 DATA01Loop  #6Loop · 15 nodes−Fold region diff --git a/docs/chapter08/08-graph2.gv b/docs/chapter08/08-graph2.gv new file mode 100644 index 00000000..2fa82523 --- /dev/null +++ b/docs/chapter08/08-graph2.gv @@ -0,0 +1,103 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
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="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Region38 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;} + { rank=same; Region38;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region38[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If19:p0[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Region38 -> Region34[taillabel=1 color=red]; + Region38 -> If28:p1[taillabel=2 color=red]; + Return39 -> If11:p1[taillabel=0 color=red]; + Return39 -> Phi_arg8[taillabel=1]; +} diff --git a/docs/chapter08/08-graph2.json b/docs/chapter08/08-graph2.json new file mode 100644 index 00000000..6f25aaad --- /dev/null +++ b/docs/chapter08/08-graph2.json @@ -0,0 +1,39 @@ +{ + "ver": 1, + "comp": "chapter08/docs/08-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": 39, "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": 38, "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": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 0}}, + {"id": 13, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 1}}, + {"id": 14, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "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": "5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 1}}, + {"id": 26, "label": "6", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 27, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 26, "role": "DATA", "label": null}], "proj": null}, + {"id": 28, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}], "proj": null}, + {"id": 34, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "CTRL", "label": null}, {"idx": 2, "def": 14, "role": "CTRL", "label": null}], "proj": null}, + {"id": 38, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 34, "role": "CTRL", "label": null}, {"idx": 2, "def": 20, "role": "CTRL", "label": null}], "proj": null}, + {"id": 39, "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]}, + {"id": 19, "par": 6, "nodes": [12, 13, 14, 18, 19, 20, 27, 28, 34, 38]} + ] +} diff --git a/docs/chapter08/08-graph2.svg b/docs/chapter08/08-graph2.svg new file mode 100644 index 00000000..e3d62fb9 --- /dev/null +++ b/docs/chapter08/08-graph2.svg @@ -0,0 +1,169 @@ +#3[0] → #39 · CTRL#6[1] → #1 · CTRL#6[2] → #38 · 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#18[1] → #16 · DATA#18[2] → #17 · DATA#19[0] → #5 · CTRL#19[1] → #18 · DATA#27[1] → #16 · DATA#27[2] → #26 · DATA#28[0] → #13 · CTRL#28[1] → #27 · DATA#34[1] → #12 · CTRL#34[2] → #14 · CTRL#38[1] → #34 · CTRL#38[2] → #20 · CTRL#39[0] → #7 · CTRL#39[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] → #39 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] → #38 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 DATA01True  #12/0#12 True +Projection 0 of #19 +Type not computed + +[0] → #19 CTRLFalse  #13/1#13 False +Projection 1 of #19 +Type not computed + +[0] → #19 CTRLTrue  #14/0#14 True +Projection 0 of #28 +Type not computed + +[0] → #28 CTRL1  #15#15 1 +Type not computed + ++  #16#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 DATA0125  #17#17 5 +Type not computed + +==  #18#18 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #17 DATA012If  #19#19 If +Type not computed + +[0] → #5 CTRL +[1] → #18 DATA01False  #20/1#20 False +Projection 1 of #28 +Type not computed + +[0] → #28 CTRL6  #26#26 6 +Type not computed + +==  #27#27 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #26 DATA012If  #28#28 If +Type not computed + +[0] → #13 CTRL +[1] → #27 DATA01Region  #34#34 Region +Type not computed + +[0] → — DATA +[1] → #12 CTRL +[2] → #14 CTRL012Region  #38#38 Region +Type not computed + +[0] → — DATA +[1] → #34 CTRL +[2] → #20 CTRL012Return  #39#39 Return +Type not computed + +[0] → #7 CTRL +[1] → #8 DATA01Loop  #6Loop · 17 nodes−Fold regionIf  #19If · 10 nodes−Fold region diff --git a/docs/chapter08/08-graph3.gv b/docs/chapter08/08-graph3.gv new file mode 100644 index 00000000..72ac10a8 --- /dev/null +++ b/docs/chapter08/08-graph3.gv @@ -0,0 +1,111 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
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="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region25 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg26 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_28 [ label="6" ]; + EQ29 [ label="==" ]; + If30 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region36 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg37 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region25;Phi_arg26;} + { rank=same; Region36;Phi_arg37;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> If30:p1[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + Region25 -> If11:p1[taillabel=1 color=red]; + Region25 -> If19:p0[taillabel=2 color=red]; + Phi_arg26 -> Region25 [style=dotted taillabel=0]; + Phi_arg26 -> Phi_arg8[taillabel=1]; + Phi_arg26 -> Add16[taillabel=2 constraint=false]; + EQ29 -> Add16[taillabel=1]; + EQ29 -> Con_28[taillabel=2]; + If30 -> If19:p1[taillabel=0 color=red]; + If30 -> EQ29[taillabel=1]; + Region36 -> Region25[taillabel=1 color=red]; + Region36 -> If30:p0[taillabel=2 color=red]; + Phi_arg37 -> Region36 [style=dotted taillabel=0]; + Phi_arg37 -> Phi_arg26[taillabel=1]; + Phi_arg37 -> Add16[taillabel=2 constraint=false]; + Return39 -> Region36[taillabel=0 color=red]; + Return39 -> Phi_arg37[taillabel=1]; +} \ No newline at end of file diff --git a/docs/chapter08/08-graph3.json b/docs/chapter08/08-graph3.json new file mode 100644 index 00000000..a795c51d --- /dev/null +++ b/docs/chapter08/08-graph3.json @@ -0,0 +1,40 @@ +{ + "ver": 1, + "comp": "chapter08/docs/08-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": 39, "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": 20, "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": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 0}}, + {"id": 13, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 1}}, + {"id": 14, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 30, "role": "CTRL", "label": null}], "proj": {"par": 30, "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": "5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 30, "role": "CTRL", "label": null}], "proj": {"par": 30, "idx": 1}}, + {"id": 25, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 7, "role": "CTRL", "label": null}, {"idx": 2, "def": 12, "role": "CTRL", "label": null}], "proj": null}, + {"id": 26, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 25, "role": "ASSOC", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 28, "label": "6", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 29, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 28, "role": "DATA", "label": null}], "proj": null}, + {"id": 30, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}, {"idx": 1, "def": 29, "role": "DATA", "label": null}], "proj": null}, + {"id": 36, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 25, "role": "CTRL", "label": null}, {"idx": 2, "def": 14, "role": "CTRL", "label": null}], "proj": null}, + {"id": 37, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 36, "role": "ASSOC", "label": null}, {"idx": 1, "def": 26, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 39, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 36, "role": "CTRL", "label": null}, {"idx": 1, "def": 37, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 6, "par": 0, "nodes": [5, 6, 7, 8, 10, 11, 12, 13, 14, 18, 19, 20, 29, 30]} + ] +} diff --git a/docs/chapter08/08-graph3.svg b/docs/chapter08/08-graph3.svg new file mode 100644 index 00000000..62517032 --- /dev/null +++ b/docs/chapter08/08-graph3.svg @@ -0,0 +1,179 @@ +#3[0] → #39 · CTRL#6[1] → #1 · CTRL#6[2] → #20 · 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#18[1] → #16 · DATA#18[2] → #17 · DATA#19[0] → #5 · CTRL#19[1] → #18 · DATA#25[1] → #7 · CTRL#25[2] → #12 · CTRL#26[1] → #8 · DATA#26[2] → #16 · DATA#29[1] → #16 · DATA#29[2] → #28 · DATA#30[0] → #13 · CTRL#30[1] → #29 · DATA#36[1] → #25 · CTRL#36[2] → #14 · CTRL#37[1] → #26 · DATA#37[2] → #16 · DATA#39[0] → #36 · CTRL#39[1] → #37 · 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] → #39 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] → #20 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 DATA01True  #12/0#12 True +Projection 0 of #19 +Type not computed + +[0] → #19 CTRLFalse  #13/1#13 False +Projection 1 of #19 +Type not computed + +[0] → #19 CTRLTrue  #14/0#14 True +Projection 0 of #30 +Type not computed + +[0] → #30 CTRL1  #15#15 1 +Type not computed + ++  #16#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 DATA0125  #17#17 5 +Type not computed + +==  #18#18 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #17 DATA012If  #19#19 If +Type not computed + +[0] → #5 CTRL +[1] → #18 DATA01False  #20/1#20 False +Projection 1 of #30 +Type not computed + +[0] → #30 CTRLRegion  #25#25 Region +Type not computed + +[0] → — DATA +[1] → #7 CTRL +[2] → #12 CTRL012φ_arg  #26#26 φ_arg +Type not computed + +[0] → #25 ASSOC +[1] → #8 DATA +[2] → #16 DATA[0] → #250126  #28#28 6 +Type not computed + +==  #29#29 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #28 DATA012If  #30#30 If +Type not computed + +[0] → #13 CTRL +[1] → #29 DATA01Region  #36#36 Region +Type not computed + +[0] → — DATA +[1] → #25 CTRL +[2] → #14 CTRL012φ_arg  #37#37 φ_arg +Type not computed + +[0] → #36 ASSOC +[1] → #26 DATA +[2] → #16 DATA[0] → #36012Return  #39#39 Return +Type not computed + +[0] → #36 CTRL +[1] → #37 DATA01Loop  #6Loop · 14 nodes−Fold region diff --git a/docs/chapter08/Makefile b/docs/chapter08/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter08/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter08/README.ja.md b/docs/chapter08/README.ja.md new file mode 100644 index 00000000..cbe61a3b --- /dev/null +++ b/docs/chapter08/README.ja.md @@ -0,0 +1,264 @@ +# 第8章: 遅延生成する Phi、Break、Continue、評価器 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第7章](../chapter07/README.ja.md) | +[次の章: 第9章](../chapter09/README.ja.md) + +# 目次 + +1. [Phi の遅延生成](#phi-の遅延生成) +2. [`continue` 文](#continue-文) +3. [`break` 文](#break-文) +4. [パーサーでの考慮事項](#パーサーでの考慮事項) +5. [例](#例) + - [例1](#例1) + - [例2](#例2) + - [例3](#例3) +6. [Sea of Nodes グラフ評価器](#sea-of-nodes-グラフ評価器) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter08) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter07...linear-chapter08) することもできます。 + +この章では次のことを行います。 + +* ループ内の `Phi` の作成を、先行生成から遅延生成へ移します。 +* `break` 文と `continue` 文のサポートを追加します。 +* Sea of Nodes グラフ評価器を実装します。 + +この章の [完全な言語文法](08-grammar.ja.md) はこちらです。 + +## Phi の遅延生成 + +[第7章](../chapter07/README.ja.md) では、ループ先頭にすべての変数の `PhiNode` を先行して作成しました。この方法では不要な Phi も作りますが、冗長な Phi は後で削除されます。 + +この章では、`PhiNode` の遅延生成をサポートします。 + +`PhiNode` を遅延生成する際の主な難しさは、Phi を作るとき、先行生成していた場合に作られるはずだった最も内側のループ先頭のスコープで作らなければならないことです。`if` 文と `while` 文ではスコープを複製するため、単に現在のスコープに Phi を作るわけにはいきません。 + +`PhiNode` を遅延生成する最も簡単な方法は、名前の検索にその処理を組み込むことだとわかります。しかし、名前を参照するとき、Phi を作る必要があるとどう判断するのでしょうか。特定の名前の対応付けを、検索時に `PhiNode` に変換すべきだと示す仕組みが必要です。 + +次のように実現します。 + +* `ScopeNode.dup()` で、ループ先頭のために Scope を複製する場合、名前の定義を元のノードに設定する代わりに、Scope 自身に設定します。これが番兵（sentinel）として機能します。 + + ```java + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); + ``` + +* その後、検索で名前にアクセスするとき、定義が Scope ノードを指していることを検出し、その時点で `PhiNode` を作ります。対応する実装は `ScopeNode.update()` にあります。 + + ```java + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have inserted a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + ``` + +* スコープをマージするときは、定義に直接アクセスする代わりに名前で検索し、正しい内側のスコープ階層で遅延生成する `PhiNode` が作られるようにします。 + + ```java + if( in(i) != that.in(i) ) // No need for redundant Phis + // If we are in lazy phi mode we need to do a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + ``` + +* 最後に `ScopeNode.endLoop()` で残った番兵を片付け、ループ先頭からの入力に置き換えます。 + + ```java + for( int i=1; i than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + ``` + +* continue スコープは、後続の `continue` 文の基準となるスコープになり、こうして continue スコープと Region のスタックを形成します。 +* ループが終わった後、ループ内で continue スコープを作っていたなら、現在のスコープを continue スコープへマージし、その continue スコープを有効なスコープにする必要があります。 + + ```java + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + ``` + +## `break` 文 + +`break` の実装は `continue` より簡単です。ループ本体の解析前に出口スコープを作っており、これが初期の `break` スコープになります。`break` に遭遇したら、入れ子のレキシカルスコープを切り詰めた後、現在のスコープを現在の break スコープにマージします。その結果の新しいスコープが、有効な break スコープになります。 + +## パーサーでの考慮事項 + +`continue` や `break` の対象は、それを直接囲む `while` ループです。そのため、`continue` と `break` のスコープのスタックを管理します。`while` ループの解析前にそれまでの `continue` や `break` のスコープを保存し、解析後に復元することで実現します。 + +## 例 + +### 例1 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; +``` + +![グラフ1](./08-graph1.svg) + +### 例2 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; +``` + +![グラフ1](./08-graph2.svg) + +### 例3 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; +``` + +![グラフ1](./08-graph3.svg) + +## Sea of Nodes グラフ評価器 + +評価器は、プログラムの開始点から制御フローを前向きにたどり、Return ノードに到達するか、最大ループ回数を超えるまで、与えられたグラフを直接評価します。 + +評価器は呼び出されると、最初にグラフを走査して Start ノードを見つけ、準備を行います。プログラムが特別なパラメーター `arg` を使っている場合、渡されたパラメーター値を、そのパラメーターを表すノードに束縛します。 + +この簡単な準備が済むと、Start ノードからの制御の射影をたどり、プログラムの「実行」を始められます。 + +この時点で制御フローはプログラムの最初の Region にありますが、ほかの Region とまったく同じように扱います。各 Region で行うべき処理は2つあります。まずすべての phi を具体的な値に解決し、次に制御フローの次の行き先を決めます。 + +もっと処理が必要に思えるかもしれません。しかし phi ノードを解決すれば、その Region の制御フロー経路に固有のロジックはすべて解決されます。それ以外の処理は、後で必要に応じて解決されます。プログラムの実行には、これで十分です！ + +Region の後の制御フローの行き先は簡単に見つけられます。Region を使う制御ノードは1つだけだからです。そのため、Region の利用側の中からそのノードを探します。 + +そのノードを見つけたら、到達した制御フローノードの種類によって動作を変えます。可能性は `RegionNode`、`IfNode`、`ReturnNode` の3つだけです。別の `RegionNode` なら、同じ処理を繰り返します。`ReturnNode` なら、戻り値の式を解決してプログラムの値を返せます。最後に `IfNode` の場合、まず判定式を解決し、true（射影0）または false（射影1）の分岐を選択します。`IfNode` のどちらの射影を選んでも、その射影を通って、それを使う制御ノード（`RegionNode`）に進みます。 + +上ではノードを「解決する」と述べましたが、それは何を意味するのでしょうか。ノードは、値を持つ（たとえば定数）か、すでに解決されて値がキャッシュされているか、あるいは自身が使うノードに対して演算を行います。最後の場合、その入力ノードを解決する必要があります。入力が解決されたら、それらに対してノードの演算を行えます。たとえば `AddNode` の値は、2つの入力の和です。値を解決したら、その値を返します。 + +これで、ループのない単純なプログラムを評価できます。 + +ループもほぼこのままで動作し、少しだけ追加の処理が必要です。制御が `LoopNode` を通るたびに、評価器はループの反復回数を使い切っていないか確認します。使い切っていたら、タイムアウトを示す RuntimeException を投げます。 + +最後に、ループ Region の `PhiNode` の値を計算するときは、どのキャッシュ値も更新する前に、すべての新しい値を計算するよう注意が必要です。ループの反復では、すべての `PhiNode` の値が同じ時点の値になるようにしなければならないからです。新しい値をすべて計算し終えたら、それらのキャッシュを一度に更新できます。これを説明するため、次のコードを考えます。 + +```java +int t = 0; +while(arg < 10) { + t = arg; + arg = arg + 1; +} +return t; +``` + +このコードでは、グラフはループ内の2つの文をどちらの順序でも評価できるため、`t` に以前の `arg` の値を設定する前に、`arg` の新しい値をキャッシュしないようにする必要があります。 + +この評価方法は、命令選択、レジスタ割り当て、コード生成を気にせずプログラムを実行できるため、テストに便利です。通常のピープホール最適化で生成したグラフを実行します。後の章では、異なるワークリストの順序で最適化したグラフを評価器で比較し、結果の不一致を検出できます。この章のファザーは、生成したプログラムについて、コンパイラと評価器の失敗をチェックします。 + +``` java +arg=arg+arg; +arg=arg+arg; +... +arg=arg+arg; +return arg; +``` + +一方、このエンジンは特に高速になるようには設計していません！ すべての式をキャッシュするわけではないため、直前の例のように実行時間が指数的になるプログラムを作ることができます。 + +[^1]: 方法2も試しました。この別の解法を見たい読者のため、その実装を持つ別のブランチを用意しています。 diff --git a/docs/chapter08/README.md b/docs/chapter08/README.md new file mode 100644 index 00000000..d4f8cab6 --- /dev/null +++ b/docs/chapter08/README.md @@ -0,0 +1,327 @@ +# Chapter 8: Lazy Phis, Break, Continue, and Evaluator + +English | [日本語](README.ja.md) + +[Previous: Chapter 7](../chapter07/README.md) | +[Next: Chapter 9](../chapter09/README.md) + +# Table of Contents + +1. [Lazy Phi Creation](#lazy-phi-creation) +2. [Continue statement](#continue-statement) +3. [Break statement](#break-statement) +4. [Parser Considerations](#parser-considerations) +5. [Examples](#examples) + - [Example 1](#example-1) + - [Example 2](#example-2) + - [Example 3](#example-3) + +6. [Sea of Nodes Graph Evaluator](#sea-of-nodes-graph-evaluator) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter08) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter07...linear-chapter08) it to the previous chapter. + + +In this chapter: + +* We move from eager to lazy `Phi` creation in loops. +* We add support for `break` and `continue` statements. +* We implement a Sea of Nodes Graph Evaluator. + +Here is the [complete language grammar](08-grammar.md) for this chapter. + + +## Lazy Phi Creation + +In [chapter 7](../chapter07/README.md), we created `PhiNode`s for all variables +in the loop head eagerly. This approach creates some unnecessary Phis but the +redundant Phis get cleaned up later. + +In this chapter we add support for creating the `PhiNode`s lazily. + +The main complication with creating `PhiNode`s lazily is that when we create a +Phi, it must be created in the innermost loop head scope where it would have +been created had we done it eagerly. Since scopes get duped in `if` and +`while` statements, we cannot just create Phis in the current scope. + +It turns out that the easiest way to create the `PhiNode`s lazily is to hook +them up to name lookup. But how do we know that a Phi must be created when we +access a name? We need a way to flag that a particular name mapping must be +converted to a `PhiNode` on lookup. + +We do this as follows: + +* In `ScopeNode.dup()`, if the Scope is being duplicated for a loop head, then + instead of setting the name's definition to the original node, we set it to + the Scope itself. This acts like a sentinel. + + ```java + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); + ``` + +* Subsequently, when a lookup accesses a name, we notice that the def is set to + the Scope node, and we create a `PhiNode` at this point. The relevant + implementation is in `ScopeNode.update()`. + + ```java + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have inserted a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + ``` + +* When we merge scopes, we ensure lazy `PhiNode` creation at the correct inner + scope level by invoking lookup by name instead of directly accessing the + defs. + + ```java + if( in(i) != that.in(i) ) // No need for redundant Phis + // If we are in lazy phi mode we need to do a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + ``` + +* Finally, in `ScopeNode.endLoop()` we clean up any leftover sentinels, replacing the sentinel with the input from loop head. + + ```java + for( int i=1; i than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + ``` + +* The continue scope becomes the base scope for the subsequent `continue` + statement, thus forming a stack of continue scopes/regions. +* After the loop is done, if we find that a continue scope was created within + the loop, we must merge the current scope into the continue scope, and make + the continue scope the active scope. + + ```java + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + ``` + +## `break` Statement + +Implementing `break` is simpler than `continue`, because the exit scope is +created before we parse the loop body, and this becomes the initial `break` +scope. When we see `break`, we merge the current scope, after pruning any +nested lexical scopes, to the current break scope, and the resulting new scope +becomes the active break scope. + +## Parser Considerations + +Since a `continue` or `break` targets the immediate surrounding `while` loop, +we maintain a stack of the `continue` and `break` scopes. This is done by +saving the previous `continue` or `break` scope before parsing a `while` loop +and restoring afterward. + +## Examples + +### Example 1 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; +``` + +![Graph1](./08-graph1.svg) + + +### Example 2 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; +``` + +![Graph1](./08-graph2.svg) + +### Example 3 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; +``` + +![Graph1](./08-graph3.svg) + + +## Sea of Nodes Graph Evaluator + +The evaluator directly evaluates the given graph by walking forward through the control flow from the program start until it either encounters a Return node or it passes the maximum loop count. + +When called, the evaluator sets itself up by first traversing the graph to find the Start node. Then, if a program uses the special `arg` parameter, the passed-in parameter value will be bound to the node that represents it. + +With that brief setup done, the control projection from the Start node is traversed and the program can begin "execution". + +At this point, control flow is at the first region of the program, but it is treated just the same as any other region. There are two things that must be done at each region. First, resolve all phis to a specific value; and second to determine where control flow will continue to. + +It may seem like more than that should be done, but by resolving phi nodes, any logic that is specific to the control flow path for the given region will be resolved. Any other work will eventually be resolved later on as-needed. This is sufficient for the program to run! + +Finding the next place control flow will move to after a region is straightforward because any region only has a single control node that uses it. So we search for that node in the Region's users. + +Once we have that node, our behavior depends on what type of control flow node we've landed on. There are only 3 options: `RegionNode`, `IfNode`, and `ReturnNode`. If it is another `RegionNode`, we do the same again. If it's a `ReturnNode`, we can resolve the returned expression and return the program's value. Finally, for an `IfNode`, we must first resolve the test expression so that we can choose the true (projection 0) or false (projection 1) branch. Whichever projection from the `IfNode` is chosen, we step through that projection on to the control node (a `RegionNode`) that uses it. + +We talk about resolving nodes above, but what does that mean? A node will either have a value (for instance a constant), will already be resolved with the resolved value cached, or it will operate on nodes that it uses, which must be resolved. Once a node's inputs are resolved, its operation may be performed on them. For instance, an `AddNode`'s value will be the sum of its two inputs. Once the value is resolved, the resolved value is returned. + +With that, a simple non-looping program can be evaluated. + +Looping is almost functional with that, too, with only a couple of small extra details. Whenever control moves through a `LoopNode`, the evaluator checks that it hasn't run out of loop iterations. If it has, a timeout RuntimeException will be thrown. + +Finally, while calculating the value of `PhiNode`s in the loop region, we must be careful to compute all of their new values before we update any of their cached values. That's because as a loop iterates, we must ensure that all `PhiNode` values are consistently the value from the same point in time. Once all of the new values are calculated, we can update the cache for all of them at once. To illustrate this, consider the following code: + +```java +int t = 0; +while(arg < 10) { + t = arg; + arg = arg + 1; +} +return t; +``` + +In this code, the two statements within the loop may be evaluated in either +order by the graph, so we must ensure that the new value `arg` is not cached +before the value of `t` can be set to the previous value of `arg`. + +This approach to evaluation is useful for testing because it allows a program +to be executed without worrying about instruction selection, register +allocation or code generation. It executes the graph produced with normal +peephole optimization. In later chapters, the evaluator can compare graphs +optimized with different worklist orders to detect inconsistent results. This +chapter's fuzzer checks generated programs for compiler and evaluator failures. + +``` java +arg=arg+arg; +arg=arg+arg; +... +arg=arg+arg; +return arg; +``` + +On the other hand, this engine is not designed to be particularly fast! Because +not all expressions are cached, it's possible to construct programs like the +preceding one which have exponential runtime. + + +[^1]: We also experimented with option 2. For readers who would like to see this +alternative solution, we provide a separate branch with such an implementation. \ No newline at end of file -- cgit v1.2.3