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 --- README.ja.md | 2 +- README.md | 2 +- 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 +++++++++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 74 +++++- .../java/com/seaofnodes/simple/node/AddNode.java | 1 + .../java/com/seaofnodes/simple/node/BoolNode.java | 1 + .../com/seaofnodes/simple/node/ConstantNode.java | 3 + .../java/com/seaofnodes/simple/node/DivNode.java | 1 + .../java/com/seaofnodes/simple/node/IfNode.java | 5 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 30 +++ .../java/com/seaofnodes/simple/node/MinusNode.java | 1 + .../java/com/seaofnodes/simple/node/MulNode.java | 1 + src/main/java/com/seaofnodes/simple/node/Node.java | 19 ++ .../java/com/seaofnodes/simple/node/NotNode.java | 1 + .../java/com/seaofnodes/simple/node/PhiNode.java | 21 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 2 + .../com/seaofnodes/simple/node/RegionNode.java | 12 +- .../com/seaofnodes/simple/node/ReturnNode.java | 1 + .../java/com/seaofnodes/simple/node/ScopeNode.java | 55 +++-- .../java/com/seaofnodes/simple/node/StartNode.java | 2 + .../java/com/seaofnodes/simple/node/StopNode.java | 1 + .../java/com/seaofnodes/simple/node/SubNode.java | 1 + .../simple/print/SimpleGraphAdapter.java | 3 +- .../simple/print/SimpleGraphObserver.java | 2 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 222 ++++++++++++++++++ 42 files changed, 2170 insertions(+), 30 deletions(-) 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 create mode 100644 src/main/java/com/seaofnodes/simple/node/LoopNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter07Test.java diff --git a/README.ja.md b/README.ja.md index 081544fe..c1b587ef 100644 --- a/README.ja.md +++ b/README.ja.md @@ -43,7 +43,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第4章](docs/chapter04/README.ja.md)：`arg` という名前の、定数ではない外部入力変数。定数と `arg` を使う二項演算と比較演算。ゼロ以外の値は真とみなします。代数的簡約によるピープホール最適化。 * [第5章](docs/chapter05/README.ja.md)：`if` 文。制御フローグラフ（CFG）の構築。 * [第6章](docs/chapter06/README.ja.md)：実行されない制御フローに対するピープホール最適化。 -* 第7章：`while` 文。ループ構造と先行的な Phi の導入。 +* [第7章](docs/chapter07/README.ja.md)：`while` 文。ループ構造と先行的な Phi の導入。 * 第8章：ループ構造の続き。必要時の Phi の生成、`break` 文と `continue` 文。 * 第9章：大域的値番号付け。不動点に達するまでのピープホール最適化の反復。ワークリスト。 * 第10章：ユーザー定義の構造体、ポインタ、null 解析。SSA で表す単一のメモリ値。ロード、ストア、実行可能な評価器。 diff --git a/README.md b/README.md index 67bf6c0c..19ee1891 100644 --- a/README.md +++ b/README.md @@ -50,7 +50,7 @@ The Simple language is styled after a subset of C or Java. simplifications. * [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. * [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow. -* Chapter 7: `while` statement; looping constructs - eager phi approach. +* [Chapter 7](docs/chapter07/README.md): `while` statement; looping constructs - eager phi approach. * Chapter 8: Looping constructs continued, lazy phi creation, `break` and `continue` statements. * Chapter 9: Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * Chapter 10: User defined structs, pointers and null 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 + * while ( expression ) statement + * + * @return a {@link Node}, never {@code null} + */ + private Node parseWhile() { + require("("); + + // Loop region has two control inputs, the first is the entry + // point, and second is back edge that is set after loop is parsed + // (see end_loop() call below). Note that the absence of back edge is + // used as an indicator to switch off peepholes of the region and + // associated phis; see {@code inProgress()}. + + ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here + + // At loop head, we clone the current Scope (this includes all + // names in every nesting level within the Scope). + // We create phis eagerly for all the names we find, see dup(). + + // Save the current scope as the loop head + ScopeNode head = _scope.keep(); + // Clone the head Scope to create a new Scope for the body. + // Create phis eagerly as part of cloning + _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis + + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + + // Clone the body Scope to create the exit Scope + // which accounts for any side effects in the predicate + // The exit Scope will be the final scope after the loop, + // And its control input is the False branch of the loop predicate + // Note that body Scope is still our current scope + var exit = _scope.dup(); + _xScopes.push(exit); + exit.ctrl(ifF); + + // Parse the true side, which corresponds to loop body + // Our current scope is the body Scope + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + + // The true branch loops back, so whatever is current control (_scope.ctrl) gets + // added to head loop as input. endLoop() updates the head scope, + // and goes through all the phis that were created earlier. For each + // phi, it sets the second input to the corresponding input from the back edge. + // If the phi is redundant, it is replaced by its sole input. + head.endLoop(_scope, exit); + head.unkeep().kill(); + + _xScopes.pop(); // Cleanup + _xScopes.pop(); // Cleanup + + // At exit the false control is the current control, and + // the scope is the exit scope after the exit test. + return (_scope = exit); + } + /** * Parses a statement * @@ -368,7 +438,7 @@ public class Parser { // Require an exact match private void require(String syntax) { require(null, syntax); } - private Node require(Node n, String syntax) { + private N require(N n, String syntax) { if (match(syntax)) return n; throw errorSyntax(syntax); } @@ -377,7 +447,7 @@ public class Parser { return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); } - static RuntimeException error(String errorMessage) { + public static RuntimeException error( String errorMessage ) { return new RuntimeException(errorMessage); } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 22c36746..5ee742f7 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; + public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 3a5e1a8f..e363bf75 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + abstract public class BoolNode extends Node { public BoolNode(Node lhs, Node rhs) { diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 5efe29b7..19166ec6 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; + /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer @@ -36,6 +37,8 @@ public class ConstantNode extends Node { return p.p(_con); } + @Override public boolean isMultiTail() { return true; } + @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index f6b4e03e..4c3c2feb 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class DivNode extends Node { public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 05c1c844..52d7e31e 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; + public class IfNode extends MultiNode { public IfNode(Node ctrl, Node pred) { @@ -17,6 +18,7 @@ public class IfNode extends MultiNode { @Override protected String format() { return "if( %1 )"; } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } public Node pred() { return in(1); } @@ -24,7 +26,8 @@ public class IfNode extends MultiNode { @Override public Type compute() { // If the If node is not reachable then neither is any following Proj - if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER; + if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) + return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java new file mode 100644 index 00000000..e4ef68a3 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.BitSet; + +public class LoopNode extends RegionNode { + + public LoopNode( Node entry ) { super(null,entry,null); } + + Node entry() { return in(1); } + Node back () { return in(2); } + + @Override + public String label() { return "Loop"; } + + @Override + public Type compute() { + return inProgress() ? Type.CONTROL : super.compute(); + } + + @Override + public Node idealize() { + return inProgress() ? null : super.idealize(); + } + + @Override int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(entry().idepth()+1); } + + @Override Node idom() { return entry(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index bb5f155d..fb51777e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index d7c65b26..2d0fa95b 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class MulNode extends Node { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 23f15ebe..1430cdac 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -71,6 +71,12 @@ public abstract class Node extends BaseNode { // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); + public boolean isMultiHead() { return false; } + public boolean isMultiTail() { return false; } + + // ------------------------------------------------------------------------ + // Graph Node & Edge manipulation + @Override public String typeName() { return _type==null ? null : _type.toString(); } /** @@ -190,6 +196,19 @@ public abstract class Node extends BaseNode { public N keep() { addUse(null); return (N)this; } // Remove bogus null. public N unkeep() { delUse(null); return (N)this; } + + // Replace self with nnn in the graph, making 'this' go dead + void subsume( Node nnn ) { + assert nnn!=this; + while( nOuts() > 0 ) { + Node n = _outputs.removeLast(); + int idx = Utils.find(n._inputs, this); + n._inputs.set(idx,nnn); + nnn.addUse(n); + } + kill(); + } + // ------------------------------------------------------------------------ // Graph-based optimizations diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index a9781ce1..538016bd 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; + public class NotNode extends Node { public NotNode(Node in) { super(null, in); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6acb5535..64cd3dd7 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; + public class PhiNode extends Node { final String _label; @@ -14,16 +15,20 @@ public class PhiNode extends Node { @Override protected ExprPrinter _print1(ExprPrinter p) { + if( region().inProgress() ) + p.p("Z"); p.p("Phi("); - for( Node in : _inputs ) - p.n(in).p(","); + for( Node in : _inputs ) p.n(in).p(","); return p.unchar(',').close(); } - Node region() { return in(0); } + RegionNode region() { return (RegionNode)in(0); } + @Override public boolean isMultiTail() { return true; } @Override public Type compute() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -32,6 +37,9 @@ public class PhiNode extends Node { @Override public Node idealize() { + if( !(region() instanceof RegionNode r ) || r.inProgress() ) + return null; + // If we have only a single unique input, become it. Node live = singleUniqueInput(); if (live != null) @@ -77,5 +85,10 @@ public class PhiNode extends Node { return live; } - + @Override + boolean allCons() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return false; + return super.allCons(); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index e313d31b..605c73bd 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; + public class ProjNode extends Node { // Which slice of the incoming multi-part value @@ -26,6 +27,7 @@ public class ProjNode extends Node { protected ExprPrinter _print1(ExprPrinter p) { return p.p(_label); } @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index cbd51743..e0dd45d7 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -5,8 +5,10 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; + public class RegionNode extends Node { - public RegionNode(Node... inputs) { super(inputs); } + + public RegionNode(Node... nodes) { super(nodes); } @Override public String label() { return "Region"; } @@ -16,9 +18,11 @@ public class RegionNode extends Node { } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } @Override public Type compute() { + if( inProgress() ) return Type.CONTROL; Type t = Type.XCONTROL; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -27,6 +31,7 @@ public class RegionNode extends Node { @Override public Node idealize() { + if( inProgress() ) return null; int path = findDeadInput(); if( path != 0 ) { for( Node phi : _outputs ) @@ -72,4 +77,9 @@ public class RegionNode extends Node { lca = in(i).domLCA(lca); return lca; } + + // True if last input is null + public final boolean inProgress() { + return in(nIns()-1) == null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index b8bc8859..9f4cad7a 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; + /** * The Return node has two inputs. The first input is a control node and the * second is the data node that supplies the return value. diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 86f4778e..bd6b0d8c 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -36,21 +36,14 @@ public class ScopeNode extends Node { @Override protected ExprPrinter _print1(ExprPrinter p) { - p.p(label()); - for( HashMap scope : _scopes ) { - p.p("["); - boolean first=true; - for( String name : scope.keySet() ) { - if( !first ) p.p(", "); - first=false; - p.p(name).p(":"); - Node n = in(scope.get(name)); - if( n==null ) p.p("null"); - else p.n(n); - } - p.p("]"); + p.p("Scope[ "); + String[] names = reverseNames(); + for( int j=0; j * The new Scope is a full-fledged Node with proper use<->def edges. */ - public ScopeNode dup() { + public ScopeNode dup() { return dup(false); } + public ScopeNode dup(boolean loop) { ScopeNode dup = new ScopeNode(); // Our goals are: // 1) duplicate the name bindings of the ScopeNode across all stack levels @@ -149,9 +143,19 @@ public class ScopeNode extends Node { // 3) Ensure that the order of defs is the same to allow easy merging for( HashMap syms : _scopes ) dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i { @Override protected String[] edgeNames(Node n) { @@ -17,6 +17,7 @@ public class SimpleGraphAdapter extends GraphAdapter { if( n instanceof StopNode ) return Kind.STOP; if( n instanceof ScopeNode ) return Kind.SCOPE; if( n instanceof StartNode ) return Kind.CTRL; + if( n instanceof LoopNode ) return Kind.LOOP; if( n instanceof RegionNode ) return Kind.REGION; if( n instanceof PhiNode ) return Kind.PHI; return n.isCFG() ? Kind.CTRL : Kind.DATA; diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index ea9a705e..1835f53f 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 6's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 7's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index c3cd43c3..12201ca0 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -45,7 +45,7 @@ public class Chapter03Test { assertEquals("Undefined name 'a'",e.getMessage()); } } - + @Test public void testRedeclareVar() { try { diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java new file mode 100644 index 00000000..fb8dbcca --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -0,0 +1,222 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter07Test { + + @Test + public void testExample() { + Parser parser = new Parser( + """ + while(arg < 10) { + arg = arg + 1; + } + return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testRegression() { + Parser parser = new Parser( +""" +int a = 1; +if(arg){}else{ + while(a < 10) { + a = a + 1; + } +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + } + + @Test + public void testWhileNested() { + Parser parser = new Parser( +""" +int sum = 0; +int i = 0; +while(i < arg) { + i = i + 1; + int j = 0; + while( j < arg ) { + sum = sum + j; + j = j + 1; + } +} +return sum; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,0,Phi(Loop21,Phi_sum,(Phi(Loop,0,(Phi_j+1))+Phi_sum)));", stop.toString()); + } + + @Test + public void testWhileScope() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; +} +return b; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhileNestedIfAndInc() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; + b = b + 1; + a = a + 1; +} +return b; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testWhile() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhilePeep() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile2() { + Parser parser = new Parser( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile2Peep() { + Parser parser = new Parser( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile3() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile3Peep() { + Parser parser = new Parser( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile4() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testWhile4Peep() { + Parser parser = new Parser( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + +} -- cgit v1.2.3