From c25a2ddace2e275a11d260a04069f82d587ba9e9 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 20 Oct 2023 15:21:08 -0700 Subject: Chapter 4: External Argument and Comparisons MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Tamas Hadhazy Co-authored-by: Hels15 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: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Jun Kawasaki --- docs/chapter04/04-arg1.json | 16 ++ docs/chapter04/04-arg1.svg | 81 +++++++ docs/chapter04/04-arg2.json | 16 ++ docs/chapter04/04-arg2.svg | 82 +++++++ docs/chapter04/04-dce1.svg | 100 +++++++++ docs/chapter04/04-dce2.svg | 59 +++++ docs/chapter04/04-dce3.svg | 116 ++++++++++ docs/chapter04/04-grammar.ja.md | 79 +++++++ docs/chapter04/04-grammar.md | 74 ++++++ docs/chapter04/04-post-peephole.gv | 43 ++++ docs/chapter04/04-post-peephole.json | 18 ++ docs/chapter04/04-post-peephole.svg | 90 ++++++++ docs/chapter04/04-pre-peephole.gv | 47 ++++ docs/chapter04/04-pre-peephole.json | 20 ++ docs/chapter04/04-pre-peephole.svg | 98 ++++++++ docs/chapter04/Makefile | 1 + docs/chapter04/README.ja.md | 342 ++++++++++++++++++++++++++++ docs/chapter04/README.md | 421 +++++++++++++++++++++++++++++++++++ docs/chapter04/appendix/dce.ja.md | 185 +++++++++++++++ docs/chapter04/appendix/dce.md | 168 ++++++++++++++ docs/chapter04/lattice.gv | 97 ++++++++ docs/chapter04/lattice.svg | 305 +++++++++++++++++++++++++ docs/chapter04/projnode.json | 14 ++ docs/chapter04/projnode.png | Bin 0 -> 6061 bytes docs/chapter04/projnode.svg | 74 ++++++ 25 files changed, 2546 insertions(+) create mode 100644 docs/chapter04/04-arg1.json create mode 100644 docs/chapter04/04-arg1.svg create mode 100644 docs/chapter04/04-arg2.json create mode 100644 docs/chapter04/04-arg2.svg create mode 100644 docs/chapter04/04-dce1.svg create mode 100644 docs/chapter04/04-dce2.svg create mode 100644 docs/chapter04/04-dce3.svg create mode 100644 docs/chapter04/04-grammar.ja.md create mode 100644 docs/chapter04/04-grammar.md create mode 100644 docs/chapter04/04-post-peephole.gv create mode 100644 docs/chapter04/04-post-peephole.json create mode 100644 docs/chapter04/04-post-peephole.svg create mode 100644 docs/chapter04/04-pre-peephole.gv create mode 100644 docs/chapter04/04-pre-peephole.json create mode 100644 docs/chapter04/04-pre-peephole.svg create mode 100644 docs/chapter04/Makefile create mode 100644 docs/chapter04/README.ja.md create mode 100644 docs/chapter04/README.md create mode 100644 docs/chapter04/appendix/dce.ja.md create mode 100644 docs/chapter04/appendix/dce.md create mode 100644 docs/chapter04/lattice.gv create mode 100644 docs/chapter04/lattice.svg create mode 100644 docs/chapter04/projnode.json create mode 100644 docs/chapter04/projnode.png create mode 100644 docs/chapter04/projnode.svg (limited to 'docs') diff --git a/docs/chapter04/04-arg1.json b/docs/chapter04/04-arg1.json new file mode 100644 index 00000000..b16dc51b --- /dev/null +++ b/docs/chapter04/04-arg1.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-arg1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 5, "role": "ASSOC", "label": "0: arg"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 5, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-arg1.svg b/docs/chapter04/04-arg1.svg new file mode 100644 index 00000000..b726b91f --- /dev/null +++ b/docs/chapter04/04-arg1.svg @@ -0,0 +1,81 @@ +#1[1] → #5 · ASSOC · 0: arg#6[0] → #4 · CTRL#6[1] → #5 · DATAScope  #1#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #5 ASSOC 0: arg0: $ctrl0: arg01Start  #2#2 Start +Type not computed + +$ctrl  #4/0#4 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL2  #5#5 2 +Type not computed + +Return  #6#6 Return +Type not computed + +[0] → #4 CTRL +[1] → #5 DATA01 diff --git a/docs/chapter04/04-arg2.json b/docs/chapter04/04-arg2.json new file mode 100644 index 00000000..5d2d7fde --- /dev/null +++ b/docs/chapter04/04-arg2.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-arg2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 6, "role": "ASSOC", "label": "0: arg"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 5, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 6, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-arg2.svg b/docs/chapter04/04-arg2.svg new file mode 100644 index 00000000..6083ae9b --- /dev/null +++ b/docs/chapter04/04-arg2.svg @@ -0,0 +1,82 @@ +#1[1] → #6 · ASSOC · 0: arg#5[0] → #4 · CTRL#5[1] → #6 · DATAScope  #1#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #6 ASSOC 0: arg0: $ctrl0: arg01Start  #2#2 Start +Type not computed + +$ctrl  #4/0#4 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLReturn  #5#5 Return +Type not computed + +[0] → #4 CTRL +[1] → #6 DATA01arg  #6/1#6 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA diff --git a/docs/chapter04/04-dce1.svg b/docs/chapter04/04-dce1.svg new file mode 100644 index 00000000..c63a85f7 --- /dev/null +++ b/docs/chapter04/04-dce1.svg @@ -0,0 +1,100 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Con_5 + +12 + + + +Con_6 + +1 + + + +Return7 + +Return + + + +Return7->Start2:p0 + + +0 + + + +Return7->Con_6 + + +1 + + + +Scope1_0 + + +0 + +$ctrl + +arg + + + +Scope1_0:Scope1_0_arg->Start2:p1 + + + + + +Scope1_1 + + +1 + +a + + + +Scope1_1:Scope1_1_a->Con_5 + + + + + \ No newline at end of file diff --git a/docs/chapter04/04-dce2.svg b/docs/chapter04/04-dce2.svg new file mode 100644 index 00000000..e3719bcc --- /dev/null +++ b/docs/chapter04/04-dce2.svg @@ -0,0 +1,59 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Con_6 + +1 + + + +Con_6->Start2 + + +0 + + + +Return7 + +Return + + + +Return7->Start2:p0 + + +0 + + + +Return7->Con_6 + + +1 + + + \ No newline at end of file diff --git a/docs/chapter04/04-dce3.svg b/docs/chapter04/04-dce3.svg new file mode 100644 index 00000000..86fa6f0d --- /dev/null +++ b/docs/chapter04/04-dce3.svg @@ -0,0 +1,116 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Con_5 + +2 + + + +Con_6 + +1 + + + +Add7 + ++ + + + +Add7->Con_5 + + +1 + + + +Add7->Con_6 + + +2 + + + +Con_8 + +3 + + + +Con_9 + +3 + + + +Add10 + ++ + + + +Add10->Con_8 + + +1 + + + +Add10->Con_9 + + +2 + + + +Con_11 + +6 + + + +Return12 + +Return + + + +Return12->Start2:p0 + + +0 + + + +Return12->Con_11 + + +1 + + + \ No newline at end of file diff --git a/docs/chapter04/04-grammar.ja.md b/docs/chapter04/04-grammar.ja.md new file mode 100644 index 00000000..029718a4 --- /dev/null +++ b/docs/chapter04/04-grammar.ja.md @@ -0,0 +1,79 @@ +# 第4章の文法 + +[English](04-grammar.md) | 日本語 + +この文書は [原文](04-grammar.md) の日本語訳です。 + + +[第4章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +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 + | '(' 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/chapter04/04-grammar.md b/docs/chapter04/04-grammar.md new file mode 100644 index 00000000..bd01c305 --- /dev/null +++ b/docs/chapter04/04-grammar.md @@ -0,0 +1,74 @@ +# Grammar for Chapter 4 + +English | [日本語](04-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +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 + | '(' 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/chapter04/04-post-peephole.gv b/docs/chapter04/04-post-peephole.gv new file mode 100644 index 00000000..b893874f --- /dev/null +++ b/docs/chapter04/04-post-peephole.gv @@ -0,0 +1,43 @@ +digraph chapter04 { +/* +return 1+arg+2; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Con_10 [ label="#3" ]; + Add11 [ label="+" ]; + Return12 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Add11 -> Start2:p1[taillabel=1]; + Add11 -> Con_10[taillabel=2]; + Return12 -> Start2:p0[taillabel=0; color=red]; + Return12 -> Add11[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; +} diff --git a/docs/chapter04/04-post-peephole.json b/docs/chapter04/04-post-peephole.json new file mode 100644 index 00000000..4890ca67 --- /dev/null +++ b/docs/chapter04/04-post-peephole.json @@ -0,0 +1,18 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-post-peephole.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 5, "role": "ASSOC", "label": "0: arg"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 5, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 10, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 11, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 10, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-post-peephole.svg b/docs/chapter04/04-post-peephole.svg new file mode 100644 index 00000000..d03218d6 --- /dev/null +++ b/docs/chapter04/04-post-peephole.svg @@ -0,0 +1,90 @@ +#1[1] → #5 · ASSOC · 0: arg#11[1] → #5 · DATA#11[2] → #10 · DATA#12[0] → #4 · CTRL#12[1] → #11 · DATAScope  #1#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #5 ASSOC 0: arg0: $ctrl0: arg01Start  #2#2 Start +Type not computed + +$ctrl  #4/0#4 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLarg  #5/1#5 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA#3  #10#10 #3 +Type not computed + ++  #11#11 + +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #10 DATA012Return  #12#12 Return +Type not computed + +[0] → #4 CTRL +[1] → #11 DATA01 diff --git a/docs/chapter04/04-pre-peephole.gv b/docs/chapter04/04-pre-peephole.gv new file mode 100644 index 00000000..d0d7cb0c --- /dev/null +++ b/docs/chapter04/04-pre-peephole.gv @@ -0,0 +1,47 @@ +digraph chapter04 { +/* +return 1+arg+2; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Con_5 [ label="#1" ]; + Con_6 [ label="#2" ]; + Add7 [ label="+" ]; + Add8 [ label="+" ]; + Return9 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Add7 -> Start2:p1[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + Add8 -> Con_5[taillabel=1]; + Add8 -> Add7[taillabel=2]; + Return9 -> Start2:p0[taillabel=0; color=red]; + Return9 -> Add8[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; +} diff --git a/docs/chapter04/04-pre-peephole.json b/docs/chapter04/04-pre-peephole.json new file mode 100644 index 00000000..839c16e7 --- /dev/null +++ b/docs/chapter04/04-pre-peephole.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-pre-peephole.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 10, "role": "ASSOC", "label": "0: arg"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 5, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-pre-peephole.svg b/docs/chapter04/04-pre-peephole.svg new file mode 100644 index 00000000..813a48dd --- /dev/null +++ b/docs/chapter04/04-pre-peephole.svg @@ -0,0 +1,98 @@ +#1[1] → #10 · ASSOC · 0: arg#7[1] → #10 · DATA#7[2] → #6 · DATA#8[1] → #5 · DATA#8[2] → #7 · DATA#9[0] → #4 · CTRL#9[1] → #8 · DATAScope  #1#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #10 ASSOC 0: arg0: $ctrl0: arg01Start  #2#2 Start +Type not computed + +$ctrl  #4/0#4 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL#1  #5#5 #1 +Type not computed + +#2  #6#6 #2 +Type not computed + ++  #7#7 + +Type not computed + +[0] → — DATA +[1] → #10 DATA +[2] → #6 DATA012+  #8#8 + +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #7 DATA012Return  #9#9 Return +Type not computed + +[0] → #4 CTRL +[1] → #8 DATA01arg  #10/1#10 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA diff --git a/docs/chapter04/Makefile b/docs/chapter04/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter04/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter04/README.ja.md b/docs/chapter04/README.ja.md new file mode 100644 index 00000000..f7773ef4 --- /dev/null +++ b/docs/chapter04/README.ja.md @@ -0,0 +1,342 @@ +# 第4章: 外部からの引数と比較 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第3章](../chapter03/README.ja.md) | +[次の章: 第5章](../chapter05/README.ja.md) + +# 目次 + +1. [中間表現の拡張](#中間表現の拡張) +2. [射影ノード](#射影ノード) +3. [可視化](#可視化) +4. [初期値](#初期値) +5. [制御が null でないのはいつか](#制御が-null-でないのはいつか) +6. [可視化についての注記](#可視化についての注記) +7. [型システムの変更](#型システムの変更) +8. [タプル型](#タプル型) +9. [$ctrl の名前の束縛](#ctrl-の名前の束縛) +10. [ピープホール最適化の追加](#ピープホール最適化の追加) +11. [ピープホール最適化の処理を追う](#ピープホール最適化の処理を追う) +12. [デッドコード除去（DCE）](#デッドコード除去dce) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter04) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter03...linear-chapter04) することもできます。 + +この章では、言語の文法を拡張して次の機能を追加します。 + +* プログラムは、外部環境から整数型の引数 `arg` を1つ受け取ります。 +* 式で比較演算子をサポートします。 +* 現在入ってくる制御ノードに対し、スコープを考慮する名前の束縛 `$ctrl` を導入します。これにより Return は Start に固定的につながるのではなく、スコープ内の `$ctrl` の束縛を追跡します。 + +この章の [完全な言語文法](04-grammar.ja.md) はこちらです。 + +## 中間表現の拡張 + +この章では、新しいノードを追加し、既存のノードの一部を変更します。変更するノードと新しいノードは次のとおりです。 + +| ノード名 | 種類 | 説明 | 入力 | 値 | +|-----------|----------------|------------------------------------------------|-----------------------|----------------------------------------------------------------------------| +| MultiNode | 抽象クラス | 結果がタプルであるノード | | タプル | +| Start | 制御 | 関数の開始点。今回から MultiNode になる | | 制御トークンと `arg` データノードを含むタプル | +| Proj | データ / 制御 | MultiNode から値を取り出す射影ノード | MultiNode とインデックス | 入力 MultiNode のインデックス位置から取り出した値 | +| Bool | データ | 比較演算子の結果を表す | 2つのデータノード | 比較結果を整数値で表す。1=true、0=false | +| Not | データ | 論理否定 | 1つのデータノード | 0を1に、1を0に変換する | + +> `Proj` は制御スロットを射影するとき、すなわち `Start` の `Proj#0` のときに制御ノードです。それ以外の射影はすべてデータノードです。`ProjNode.isCFG()` を参照してください。 + +前の章までのほかのすべてのノードも引き続き使います。 + +## 射影ノード + +複数の値を返すノードから、特定のタプル要素を取り出す射影ノードを追加します。各射影ノードは、入力ノードから取り出すフィールドのインデックスを持ちます。射影ノードによって、ラベル付きの使用・定義（use-def）エッジを単純なノード参照として管理できます。 + +図では、射影ノードを、接続先ノードの内側にある長方形の箱として示します。 + +### 可視化 + +![Start と、その制御および引数の射影](./projnode.svg) + +この図では、Start ノードの出力に対応する名前を射影ノードのラベルにしています。制御を含む MultiNode と制御ノードは、どちらも黄色です。`$ctrl` と `arg` は StartNode（`START`）の出力（利用側）であり、唯一の入力としてスロット0に MultiNode を持ちます。`label` に意味上の役割はなく、デバッグ出力で使います。 + +```java +public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); +``` + +```java +_scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); +_scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); +``` + +これらの射影ノードは、`START` MultiNode から `CTRL` と `ARG0` の型を取り出します。MultiNode は型を TypeTuple として保持します。 + +```java +public StartNode(Type[] args) { + super(); + _args = new TypeTuple(args); +``` + +型の取り出しには `_idx` を使います。 + +```java +return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; +``` + +### 初期値 + +引数は常に与えられ、デフォルトは `TypeInteger.BOT` です。個々のテストでは、引数を指定して `new Parser` を呼ぶことで、ほかの整数値を渡すことができますし、実際にそうしています。 + +```java +Parser parser = new Parser("return arg; ", TypeInteger.constant(2)); +``` + +グラフは次のようになります。 + +![ProjNode](./04-arg1.svg) + +* `$ctrl` と `arg` はどちらも最外側のシンボルテーブル、レキシカルな深さ0で定義されます。 +* 深さ1には空のグローバルスコープのシンボルテーブルを作ります。将来、ここでグローバル変数を定義します。 +* return の後では制御が死ぬため、スコープの `$ctrl` の線はありません。明示的に null を設定すると `setDef` が呼ばれてノードが削除されます（削除されたノードはプログラムの一部ではなく、可視化にも現れません）。 + +``` + ctrl(null); // Kill control +``` + +* `arg` は定数なので、`arg` 射影ノードはクラスタに含まれません。もともと `arg` は ProjNode により定義されていましたが、ピープホール最適化の呼び出しで計算された型が定数となるため、ProjNode を ConstantNode に置き換えます。 + +```java +public final Node peephole( ) { + Type type = _type = compute(); + /* type = {TypeInteger@1527} "2" */ + + // ProjNode is not a constant unlike its type. + if (!(this instanceof ConstantNode) && type.isConstant()) + /* Create Constant(2) */ + return deadCodeElim(new ConstantNode(type).peephole()); + + /* won't get called */ + ... +``` + +引数を渡さなければ、`TypeInteger.BOT` になります。 + +```java + Parser parser = new Parser("return arg; "); + ... + +public Parser(String source) { + this(source, TypeInteger.BOT); +} + +``` + +これが定数ではないことは明らかです。 + +```java +public final static TypeInteger BOT = new TypeInteger(false, 1); + /* _is_con = false */ +``` + +そのため、`arg` 射影ノードはクラスタ内に残ります。 + +![ArgNode](./04-arg2.svg) + +#### 制御が null でないのはいつか + +後の章では、`$ctrl` は `If` や `Region`（さらに `Loop`）などのほかの制御ノードを指すようになります。現時点ではほかの制御フローがないため、`Return` の後には必ず null を設定します。 + +#### 可視化についての注記 + +この章以降は、定数から Start ノードへのエッジを省略します。主な目的は図の混雑を減らし、グラフのより重要な部分に読者の注意を向けることです。 + +## 型システムの変更 + +[第2章](../chapter02/README.ja.md) で型システムを導入しました。 + +ノードには型を付けています。この型の注釈には2つの目的があります。 + +* そのノードで許される演算の集合を定義すること。 +* そのノードが取りうる値の集合を定義すること。 + +[第2章](../chapter02/README.ja.md) では、特定のノードにおいて型に対応する値の集合を、[束](https://en.wikipedia.org/wiki/Lattice_(order)) として便利に表せることを述べました。 + +型そのものは Java の `Type` クラスとそのサブタイプで識別します。型の実装では、型の内部構造を扱う便利な方法として Java のクラスを使っています。ただし、Java のクラスと束の中での型の位置に関連はありません。 + +この章では、型の階層を次のように拡張します。 + +``` +Type (Enhanced - now has Control, and a global Top and Bottom) ++-- TypeInteger (Enhanced - now has Top and Bottom types) ++-- TypeTuple (New - represents multi-valued result) +``` + +拡張した束は次のようになります。 + +![束](./lattice.svg) + +この章では、`arg` という名前のプログラム入力変数を導入します。この変数についてわかるのは、何らかの整数値だということだけで、定数かどうかはわかりません。 + +定数でない整数値を扱うため、`TypeInteger` を拡張し、これまでの定数値に加えて整数型 `IntTop` と `IntBot` も表せるようにします。 + +整数値が定数の場合と定数でない場合を持つようになったため、束に *meet* 演算子を導入する必要があります。`meet` 演算子は、整数値を組み合わせたときの結果の型を決める規則を表します。束の図では、`meet` を取る2つの要素から始めて、矢印を下向きにたどり、最初に合流する地点を見つけます。 + +| | IntBot | Con1 | Con2 | IntTop | +|--------|--------|--------|--------|--------| +| IntBot | IntBot | IntBot | IntBot | IntBot | +| Con1 | IntBot | Con1 | IntBot | Con1 | +| IntTop | IntBot | Con1 | Con2 | IntTop | + +この表の `Con1` と `Con2` は2つの異なる整数値を表し、次の規則を説明するためのものです。 + +* `IntTop` と任意の整数定数の `meet` は、その定数です。 +* `IntBot` と任意の整数値の `meet` は `IntBot` です。 +* 任意の整数とそれ自身の `meet` は、その整数です。 +* 互いに異なる2つの整数定数の `meet` は `IntBot` です。 + +現時点では、整数値を持つノードはすべて、定数か `IntBot` 整数型のどちらかです。ループの最適化を始めると、`IntTop` の値も現れるようになります。 + +### タプル型 + +タプル型にはもう少し説明が必要です。型を固定数まとめたもので、文字どおり `Type[]` です。タプルは、ほかの点では互いに無関係な型の集まりを表し、`MultiNode` から得られます。`ProjNode` は、タプルから適切な `Type` 配列要素を取り出します。StartNode は今回から、制御と `arg` の型からなる2要素の `TypeTuple`、`[ctrl, TypeInteger.INTBOT]` を生成します。 + +タプルに対する束の `meet` 演算子は、要素ごとに適用します。各配列要素で再帰的に `meet` を呼び出します。異なるサイズのタプルを組み合わせるのはコンパイラ内部エラーであり、その場合 `meet` はボトムを使います。 + +## `$ctrl` の名前の束縛 + +前の章までは、Start から Return への制御入力エッジを固定していました。この章では、そのような固定エッジを使いません。代わりに `$ctrl` という名前で、現在のスコープ内の制御ノードを追跡します。したがって、先行する制御ノードへのエッジを作る必要があるときは、現在のスコープでこの名前を検索するだけです。 + +## ピープホール最適化の追加 + +定数でない整数値を扱えるようになったので、代数式を並べ替えて定数畳み込みを可能にする追加の最適化を行えます。たとえば、次の式です。 + +``` +return 1 + arg + 2; +``` + +ここではコンパイラに `arg+3` を出力してほしいのですが、現状では次のようになります。 + +![グラフ1](./04-pre-peephole.svg) + +よりよい結果を得るには、代数的な簡約が必要です。たとえば、式を次のように並べ替えます。 + +``` +arg + (1 + 2) +``` + +これで定数畳み込みが可能になり、最終的な結果は次のようになります。式を正規形にすることで、よく使われるアドレス計算の定数を畳み込み、代数的な恒等式を取り除き、全般的にコードを簡単にします。 + +![グラフ1](./04-post-peephole.svg) + +この章で導入するピープホール最適化を次に示します。後の章ではさらに追加します。 + +| 変更前 | 変更後 | 説明 | +|-----------------------|-----------------------|------------------------------------------------| +| (arg + 0 ) | arg | 0の加算の恒等式 | +| (arg - 0 ) | arg | 0の減算の恒等式 | +| (arg * 1 ) | arg | 1の乗算の恒等式 | +| (con + arg) | (arg + con) | 畳み込みを促すため定数を右に移す | +| (con * arg) | (arg * con) | 畳み込みを促すため定数を右に移す | +| (con1 + (arg + con2)) | (arg + (con1 + con2)) | 畳み込みを促すため定数を右に移す | +| ((arg1 + con) + arg2) | ((arg1 + arg2) + con) | 畳み込みを促すため定数を右に移す | +| (arg + arg) | (arg * 2) | 積の和の形式 | +| (arg - arg) | 0 | 同じ値の減算は0 | +| (0 - arg) | (-arg) | 0からの減算は符号反転 | +| (arg1 - (-arg2)) | (arg1 + arg2) | 符号反転した値の減算は加算 | +| ((-arg1) - arg2) | -(arg1 + arg2) | 符号反転した値からの減算は和の符号反転 | +| (con / 1) | con | 1による除算 | +| (arg == arg) | 1 | 同じ値の比較 | +| (arg != arg) | 0 | 同じ値の比較 | +| (arg < arg) | 0 | 同じ値の比較 | +| (arg > arg) | 0 | 同じ値の比較 | +| (arg <= arg) | 1 | 同じ値の比較 | +| (arg >= arg) | 1 | 同じ値の比較 | + +## ピープホール最適化の処理を追う + +この章で導入するピープホール最適化は、すべて局所的です。解析中に新しいノードを作ったとき、そのノードがまだどこからも使われていない段階で実行します。 + +たとえば、単項式を解析してその式のノードを作ると、新しく作った `MinusNode` に対して `peephole()` を呼び出します。 + +```java +private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); +} +``` + +もう1つの例として、この章で導入した比較演算子の解析を示します。 + +```java +private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); + return lhs; +} +``` + +`peephole()` は基底の `Node` クラスで実装しているため、`Node` のすべてのサブクラスが共有します。 + +```java +public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress +} +``` + +ピープホールメソッドは次の処理を行います。 + +* ノードの型を計算します。 +* 型が定数で、ノードが ConstantNode でなければ、ConstantNode に置き換え、新しい定数に対してピープホール最適化を再帰的に呼び出します。 +* そうでなければ、`idealize()` を呼び、ノードによりよい置き換えを求めます。「よりよい置き換え」とは、`(1+2)` を `3` に、`1+(x+2)` を `(x+(1+2))` にするようなものです。 +* `idealize()` の処理内容を決めるのは、各 Node サブタイプの責任です。よりよい置き換えがあれば、ノードは `null` ではない値を返します。 +* `null` ではない値が返ったら何かが変わったので、もう一度 `peephole()` を呼び、その後、（置き換えられて死んだ）`this` ノードにデッドコード除去を行います。 + +`peephole()` は、次に示す `deadCodeElim()` を呼び出します。 + +## デッドコード除去（DCE） + +グラフの編集時に、ノードの利用側が1つから0になるたびに `kill` を呼びます。ピープホール最適化による置き換えや、スコープを抜けるときによく起こります。この再帰的な `kill` は、ほかの多くのコンパイラでいうデッドコード除去に相当します。ここでは、それを非常に細かな単位で呼び出します。パーサーが作った多くのノードは、次の字句を解析するより前に削除されます。 + +詳しくは、デッドコード除去の [付録](appendix/dce.ja.md#付録) を読んでください。 + +名前が示唆するとおり、`deadCodeElim` 関数は `kill` の薄いラッパーです。利用側が一時的に1から0になるだけのノードを早まって削除しないよう、`peepholeOpt` が使います。 + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` + +ノード `m` にダミーの利用側を一時的に追加していることに注目してください。`m` は新しい置き換え先であり、生きているとわかっていますが、まだグラフにつないでいないため、利用側がありません。ダミーの利用側を加えることで、死んだと誤認されて削除されるのを防ぎます。 diff --git a/docs/chapter04/README.md b/docs/chapter04/README.md new file mode 100644 index 00000000..cfa969d0 --- /dev/null +++ b/docs/chapter04/README.md @@ -0,0 +1,421 @@ +# Chapter 4: External Argument and Comparisons + +English | [日本語](README.ja.md) + +[Previous: Chapter 3](../chapter03/README.md) | +[Next: Chapter 5](../chapter05/README.md) + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Projection Nodes](#projection-nodes) +3. [Visualisation](#visualisation) +4. [Initial values](#initial-values) +5. [When Is Control Not-Null?](#when-is-control-not-null) +6. [Note Regarding Visualizations](#note-regarding-visualizations) +7. [Changes to Type System](#changes-to-type-system) +8. [Tuple Types](#tuple-types) +9. [$ctrl name binding](#ctrl-name-binding) +10. [More Peephole Optimizations](#more-peephole-optimizations) +11. [Peephole Walkthrough](#peephole-walkthrough) +12. [Dead Code Elimination(DCE)](#dead-code-eliminationdce) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter04) 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-chapter03...linear-chapter04) it to the previous chapter. + + +In this chapter we extend the language grammar with the following features: + +* The program receives a single argument named `arg` of integer type from the external environment. +* Expressions support comparison operators. +* We introduce a scope sensitive name binding `$ctrl` for the current incoming + control node. Thus, our Return is no longer hard-wired to Start, instead it + tracks the in scope `$ctrl` binding. + +Here is the [complete language grammar](04-grammar.md) for this chapter. + + + +## Extensions to Intermediate Representation + +In this chapter we add some new nodes and revise some existing nodes. +Following are revised or new nodes + +| Node Name | Type | Description | Inputs | Value | +|-----------|----------------|------------------------------------------------|-----------------------|----------------------------------------------------------------------------| +| MultiNode | Abstract class | A node that has a tuple result | | A tuple | +| Start | Control | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | +| Proj | Data / Control | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | +| Bool | Data | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | +| Not | Data | Logical not | One data node | Result converts 0 to 1 and vice versa | + +> A `Proj` is a control node when it projects the control slot: `Proj#0` off `Start`. +> Every other projection is a data node. See `ProjNode.isCFG()`. + +We keep all other nodes from prior chapters. + + +## Projection Nodes + +We add projection nodes that are used to extract a specific tuple member from a multi-valued node. +Each projection node contains an index of the field to extract from its input node. +Projection nodes allow us to maintain labeled use-def edges as simple Node references. + +In the visuals, projection nodes are shown as rectangular boxes inside the node to which they are attached. + +### Visualisation + +![Start and its control and argument projections](./projnode.svg) + +In the visual above, the projection nodes have been tagged by the names +associated with the outputs of the Start node. Both MultiNodes that contain +Control and Control nodes are yellow. `$ctrl` and `arg` are outputs (users) of +StartNode(`START`) and have their MultiNode as their only input in slot 0. The +`label` has no semantics and is used during debug printing. + +```java +public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); +``` + +```java +_scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); +_scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); +``` + +These projection nodes are going to extract the types for `CTRL` and `ARG0` from the `START` MultiNode. +The MultiNode holds the types as a TypeTuple: + +```java +public StartNode(Type[] args) { + super(); + _args = new TypeTuple(args); +``` + +Extracting the types is based on the `_idx`: +```java +return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; +``` + +### Initial values + +An argument is always provided, and defaults to `TypeInteger.BOT`. Individual +tests can (and do) pass in other integer values by calling `new Parser` with +an argument: + +```java +Parser parser = new Parser("return arg; ", TypeInteger.constant(2)); +``` + +The graph: + +![ProjNode](./04-arg1.svg) + +- `$ctrl` and `arg` are both defined in the outermost symbol table, at lexical depth 0. +- There is an empty global-scope symbol table created at depth 1; in the future + global variables will be defined here. +- There is no line for the scope `$ctrl` because control is dead after the + return. It is manually set to null, which calls `setDef` to kill the node + (and killed nodes are not part of the program and not visualized). + +``` + ctrl(null); // Kill control +``` + +- The `arg` projection node is not included in the cluster because arg is a + constant. The `arg` was originally defined by a ProjNode; but when peephole + is called the computed type is a constant, and the ProjNode gets replaced + with a ConstantNode: + +```java +public final Node peephole( ) { + Type type = _type = compute(); + /* type = {TypeInteger@1527} "2" */ + + // ProjNode is not a constant unlike its type. + if (!(this instanceof ConstantNode) && type.isConstant()) + /* Create Constant(2) */ + return deadCodeElim(new ConstantNode(type).peephole()); + + /* won't get called */ + ... +``` + +If you don't pass an argument you get `TypeInteger.BOT` + +```java + Parser parser = new Parser("return arg; "); + ... + +public Parser(String source) { + this(source, TypeInteger.BOT); +} + +``` + +We clearly see this is not a constant: + +```java +public final static TypeInteger BOT = new TypeInteger(false, 1); + /* _is_con = false */ +``` + +So the `arg` projection node remains in the cluster: + +![ArgNode](./04-arg2.svg) + + +#### When Is Control Not-Null? + +In later chapters, `$ctrl` will point to other control nodes, such as +`If` and `Region` (and `Loop`), but for now with no other control flow it always gets set to null after a `Return`. + +#### Note Regarding Visualizations + +From this chapter onwards we omit the edges from Constants to Start node, mainly to reduce +clutter and help draw the reader's attention to the more important aspects of the graph. + + + +## Changes to Type System + +In [Chapter 2](../chapter02/README.md) we introduced the Type System. + +We have annotated Nodes with Types and the Type annotation serves two purposes: + +* It defines the set of operations allowed on the Node, and +* it defines the set of values the Node takes on. + +We mentioned in [Chapter 2](../chapter02/README.md) that the set of values +associated with a Type at a specific Node can be conveniently represented as a +[lattice](https://en.wikipedia.org/wiki/Lattice_(order)). + +The type itself is identified by the Java class `Type` and subtypes. The type +implementation uses Java classes as a convenient way to deal with a Type's internal +structure - but the Java classes have no relation to a Type's place in the +lattice. + +In this chapter we extend the Type hierarchy as follows: + +``` +Type (Enhanced - now has Control, and a global Top and Bottom) ++-- TypeInteger (Enhanced - now has Top and Bottom types) ++-- TypeTuple (New - represents multi-valued result) +``` + +Our enhanced Lattice looks like this: + +![Lattice](./lattice.svg) + + +In this chapter we introduce the possibility of a program input variable named +`arg`; all we know about this variable is that it is some integer value, but we +do not know whether it is a constant or not. + +To support the requirements for non-constant integer values, we enhance +`TypeInteger` to allow it to represent `IntTop` and `IntBot` integer types in +addition to the earlier constant value. + +Now that integer values may be constants or non-constants, we need to introduce +the *meet* operator over our lattice. The `meet` operator describes rules that +define the resulting type when we combine integer values. In the lattice +diagram you can start from the two elements being `meet` and follow the +two arrows down the graph to the first point they meet. + +| | IntBot | Con1 | Con2 | IntTop | +|--------|--------|--------|--------|--------| +| IntBot | IntBot | IntBot | IntBot | IntBot | +| Con1 | IntBot | Con1 | IntBot | Con1 | +| IntTop | IntBot | Con1 | Con2 | IntTop | + +In the table above `Con1` and `Con2` represent two distinct integer values, and serve to explain the rules below. + +* The `meet` of `IntTop` with any integer constant is that constant. +* The `meet` of `IntBot` with any integer value is `IntBot`. +* The `meet` of any integer with itself is that integer. +* The `meet` of two unrelated integer constants is `IntBot`. + +Currently, all our integer valued nodes are either a constant or an `IntBot` integer type. +When we start optimizing loops, we will start seeing `IntTop` values. + + +### Tuple Types + +Tuple types need a little more explanation: they are a fixed-size grouping of +types; literally a `Type[]`. Tuples represent a collection of otherwise +unrelated types, and come from `MultiNode`s. `ProjNode`s will take the +appropriate `Type` array element out of a Tuple. The `StartNode` now produces +a 2-element `TypeTuple` with control and the type of `arg`: `[ctrl, TypeInteger.INTBOT]` + +The lattice `meet` operator on Tuples is done element by element; each array +element recursively calls `meet`. Tuples of mixed sizes are an internal +compiler error, and the `meet` uses Bottom for them. + + +## `$ctrl` name binding + +In previous chapters, we had a hard coded control input edge from Start to +Return. In this chapter we no longer have such a hard-wired edge. Instead, we +track the current in-scope control node via the name `$ctrl`. This means that +when we need to create an edge to the predecessor control node, we simply look +up this name in the current scope. + + +## More Peephole Optimizations + +Now that we have non-constant integer values, we can do additional +optimizations, rearranging algebraic expressions to enable constant +folding. For example: + +``` +return 1 + arg + 2; +``` + +We would expect the compiler to output `arg+3` here, but as it stands what we get is: + +![Graph1](./04-pre-peephole.svg) + +We need to perform some algebraic simplifications to enable a better outcome. For +example, we need to rearrange the expression as follows: + +``` +arg + (1 + 2) +``` + +This then enables constant folding and the final outcome is shown below. By +canonicalizing expressions we fold common addressing math constants, remove +algebraic identities and generally simplify the code. + +![Graph1](./04-post-peephole.svg) + +Here is a list of peepholes introduced in this Chapter, more will be introduced in later chapters: + +| Before | After | Description | +|-----------------------|-----------------------|------------------------------------------------| +| (arg + 0 ) | arg | Add of zero identity | +| (arg - 0 ) | arg | Sub of zero identity | +| (arg * 1 ) | arg | Multiply by one identity | +| (con + arg) | (arg + con) | Move constants to right, to encourage folding | +| (con * arg) | (arg * con) | Move constants to right, to encourage folding | +| (con1 + (arg + con2)) | (arg + (con1 + con2)) | Move constants to right, to encourage folding | +| ((arg1 + con) + arg2) | ((arg1 + arg2) + con) | Move constants to right, to encourage folding | +| (arg + arg) | (arg * 2) | Sum-of-products form | +| (arg - arg) | 0 | Sub of same is 0 +| (0 - arg) | (-arg) | Sub from 0 is negation +| (arg1 - (-arg2)) | (arg1 + arg2) | Sub of negation is add +| ((-arg1) - arg2) | -(arg1 + arg2) | Sub from negation is negation of sum +| (con / 1) | con | Division by one +| (arg == arg) | 1 | Compare of same +| (arg != arg) | 0 | Compare of same +| (arg < arg) | 0 | Compare of same +| (arg > arg) | 0 | Compare of same +| (arg <= arg) | 1 | Compare of same +| (arg >= arg) | 1 | Compare of same + + +## Peephole Walkthrough + +The peephole optimizations introduced in this chapter are all local. They are triggered during parsing +as new nodes are created, before the newly created node has any uses. + +For example, when we parse a unary expression, and create a Node for the parsed expression, +`peephole()` is invoked on the newly created `MinusNode`: + +```java +private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); +} +``` + +As another example, here is the parsing of comparison operators, also introduced in this chapter: + +```java +private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); + return lhs; +} +``` + +The implementation of `peephole()` is in the main `Node` class, and is thus shared +by all subclasses of `Node`. + +```java +public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress +} +``` + +The peephole method does the following: + +- Compute a Type for the node. +- If the Type is a Constant and the node is not a ConstantNode, replace with a + ConstantNode, recursively invoking peephole on the new constant. +- Otherwise, ask the Node for a better replacement via a call to `idealize()`. + The "better replacement" is things like `(1+2)` becomes `3` and `1+(x+2)` + becomes `(x+(1+2))`. +- Each Node subtype is responsible for deciding what the `idealize()` step + should do. If there is a better replacement then the node returns a non + `null` value. +- If we see a non `null` value, something changed, so we invoke `peephole()` + again and then also run dead code elimination on the (now dead and replaced) + `this` node. + +`peephole()` calls `deadCodeElim()` which is shown below. + + +## Dead Code Elimination(DCE) + +We call `kill` every time a Node makes the 1-user-to-0-users transition during +graph editing. This commonly happens when replacing via peeps and exiting +scopes. This recursive `kill` amounts to Dead Code Elimination in many other +compilers; here we call it in a very fine-grained way. Many Nodes will be +created by the parser, only to be killed before the very next lexeme is parsed. + +For more information please read the [appendix section](appendix/dce.md#appendix) on dead code elimination. + +The suggestively called `deadCodeElim` function is a thin wrapper over `kill` +used by `peepholeOpt` to avoid prematurely killing a Node which only briefly +makes the 1->0 users transition. + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` + +Note the temporary add of a bogus user to the Node `m`. The reason this is +done is that we know `m` is the new replacement and is alive, but since it is +not yet hooked into the graph, it has no users yet. By adding a bogus user we +prevent it being mistaken for dead and being killed. diff --git a/docs/chapter04/appendix/dce.ja.md b/docs/chapter04/appendix/dce.ja.md new file mode 100644 index 00000000..ab22b00e --- /dev/null +++ b/docs/chapter04/appendix/dce.ja.md @@ -0,0 +1,185 @@ +# 付録 + +[English](dce.md) | 日本語 + +この文書は [原文](dce.md) の日本語訳です。 + +## デッドコード除去（DCE） + +デッドコード除去は、死んだ（使われていない）ノードを取り除く処理です。 + +この章には、2種類のデッドコード除去があります。 + +* スコープをポップするときに、使われていないノードを削除する。 +* よりよい置き換えを見つけた後（`idealize()` の呼び出し後）に、古いノードを削除する。 + +どちらの方法もノードを再帰的に削除します。ただし、最初のケースは `peephole` を呼ぶかどうかにかかわらず発生します。 + +### スコープをポップするときに使われていないノードを削除する + +出力（利用側）のないノードは、使われていません。 + +### 例1 + + ``` + int a = 12; // the only output it has is the scope itself + return 1; + ``` + +`a` が使われていないことは明らかです。これから得られる、DCE なしのグラフは次のとおりです。 + +![グラフ2](../04-dce1.svg) + +`a` を削除するため、スコープのポップ時に次の方法を導入します。 + + ```java + var ret = (ReturnNode) parseBlock(); + _scope.pop(); + ``` + +現時点ではプログラムの終わりは return に固定されており、解析を終えたらスコープをポップします。ポップ前のスコープの状態は次のとおりです。 + + ``` + _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" + 1 = {ProjNode@1528} "arg" + 2 = {ConstantNode@1529} "12" + _inputs = {ArrayList@1523} size = 3 + ``` + +`a` の出力: + + ``` + _outputs = {ArrayList@1544} size = 1 + 0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" + ``` + +`a` の唯一の出力はスコープ自身であることに注目してください。`a` を導入するとき、スコープの入力に追加するとともに、スコープを `a` の出力に追加します（使用・定義の連鎖を思い出してください）。 + +`a` は戻り値ではないため、使われておらず、削除できます。 + +`_scope.pop`: + +```java +public void pop() { popN(_scopes.pop().size()); } +``` + +`_scope.popN`（使われていないノードを *再帰的に* 削除する処理）: + +```java +void popN(int n) { + for (int i = 0; i < n; i++) { + Node old_def = _inputs.removeLast(); // start from the back + if (old_def != null && // If it exists and + old_def.delUse(this)) { // If we removed the last use, the old def is now dead + old_def.kill(); // Kill the old def + } + } +} +``` + +まず、スコープの入力をループでたどります（スコープもほかと同じノードであり、スコープのシンボルが入力であることを *思い出してください*）。`removeLast` が返すノードが null でなく、`old_def` の唯一の利用側が現在のノードなら、削除できます。 + +`old_def.delUse(this)` は、`old_def` の出力から *this* を削除します。 + +```java +protected boolean delUse( Node use ) { + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.isEmpty(); + } +``` + +`use` の削除後に `_outputs` が空になれば true を返します。`old_def.kill()` は再帰的な削除処理を開始します。 + +`old_def.kill()`: + +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes + _type=null; // Flag as dead + assert isDead(); // Really dead now + } +``` + +再び `popN` を呼びます。目的は、`a` を解放した結果、同様に削除できるノードを探すことです。`a` の唯一の入力は、値12の定数ノードです。ほかのノードと同様に、`ConstantNode` も最初の入力として制御ノード（`Start`）を取ります。`ConstantNode` の入力から `Start` ノードを取り除いたら、 + +``` +Node old_def = _inputs.removeLast(); +``` + +`Start` の出力から `ConstantNode`（`this`）も取り除けます。 + +``` +old_def.delUse(this) +``` + +### 例2 + +``` +int a = 12; +int b = a + 1; +return 1; +``` + +* 現在のスコープで `popN` を呼びます。 +* `b = a + 1;` に利用側がないとわかるので、削除できます。 +* kill 関数では再び `popN` を呼べますが、今回は `b = a + 1;` の入力を対象にします（再帰的な削除を始めます）。 +* 末尾から削除処理を始め、まず「1」を調べます。これには `AddNode` 以外の出力がありません。`this = AddNode` なので、`delUse` を呼ぶと「1」が死んだ状態になります。 +* 「1」を削除し、1つの入力（制御ノード）に対して `popN` を呼べます。 +* 次に「a」を調べます。この時点ではスコープと `AddNode` の2つの利用側があります。`this = AddNode` なので、出力から `AddNode` を取り除きますが、まだスコープが利用側として残るため、ここでは削除できません。 +* `a = 12` に進みます。「a」の利用側は1つ（スコープ）だけで、`this = scope` なので、容易に削除できます。 +* 前と同じように「a」の入力をたどり、制御ノードの出力からそれらを削除します。 + +![グラフ3](../04-dce2.svg) + +## よりよい置き換えを見つけた後に古いノードを削除する + +次のコードを考えます。 + +``` +return (2+1)+3; +``` + +`idealize` の呼び出し後に DCE を行わなければ、次のようになります。 + +![グラフ3](../04-dce3.svg) + +式 (2 + 1) + 3 に対して、より最適な置き換え値（6）を見つけた後、その値を保持する定数ノードを作りました。しかし、元の式を取り除かなかったため、構造内に不要なノードが残っています。 + +これを直すため、使われていないノードを削除する `deadCodeElim` の呼び出しを追加します。 + +```java +public final Node peephole( ) { + ... + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + ... + + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + ... +} +``` + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` diff --git a/docs/chapter04/appendix/dce.md b/docs/chapter04/appendix/dce.md new file mode 100644 index 00000000..2f55e792 --- /dev/null +++ b/docs/chapter04/appendix/dce.md @@ -0,0 +1,168 @@ +# Appendix + +English | [日本語](dce.ja.md) +## Dead Code Elimination(DCE) +Dead Code Elimination is the process or removing nodes that are dead(unused). + +There are two kinds of dead code eliminations present in this chapter. +- Delete unused nodes when popping the scope. +- Delete old nodes after finding a better replacement (after calling `idealize()`). + +Both of the methods mentioned above delete the nodes recursively. However, the +first case happens regardless of whether `peephole` is called or not. + +### Delete unused nodes when popping the scope + +A node is unused if it has no outputs(users). + +### Example 1: + ``` + int a = 12; // the only output it has is the scope itself + return 1; + ``` +We clearly see `a` is unused. +This gives us the following graph(without DCE): + +![Graph2](../04-dce1.svg) + +To remove `a` we introduce the following technique when popping the scope. + + ```java + var ret = (ReturnNode) parseBlock(); + _scope.pop(); + ``` +As of now the end of the program is hard-wired to return, after finishing parsing we pop the scope. +The state of the scope before popping it: + ``` + _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" + 1 = {ProjNode@1528} "arg" + 2 = {ConstantNode@1529} "12" + _inputs = {ArrayList@1523} size = 3 + ``` +The output(s) of `a` + ``` + _outputs = {ArrayList@1544} size = 1 + 0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" + ``` +Notice how the only output of `a`is the scope itself. When `a` is introduced, it is added to the +inputs of the scope, and the scope is added to the outputs of `a`(recall use-def chains). + +Since `a` is not being returned - it is unused and can be killed. + +`_scope.pop`: +```java +public void pop() { popN(_scopes.pop().size()); } +``` +`_scope.popN`(responsible for killing the unused nodes *recursively*): +```java +void popN(int n) { + for (int i = 0; i < n; i++) { + Node old_def = _inputs.removeLast(); // start from the back + if (old_def != null && // If it exists and + old_def.delUse(this)) { // If we removed the last use, the old def is now dead + old_def.kill(); // Kill the old def + } + } +} +``` +First, we start off by looping through the inputs of the scope(*remember*: scope is just a node like any other, the symbols of the scope are the inputs). +If the node returned by `removeLast` is not null, and if the only user of `old_def` is the current Node then we can delete it. + +`old_def.delUse(this)` - delete *this* from `old_def`'s outputs. +```java +protected boolean delUse( Node use ) { + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.isEmpty(); + } +``` +Returns true if `_outputs` becomes empty after deleting `use`. +`old_def.kill()` starts the killing process recursively. + +`old_def.kill()` +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes + _type=null; // Flag as dead + assert isDead(); // Really dead now + } +``` +`popN` is called again, our goal is to look for nodes that might also get deleted once `a` is freed. +The only input `a` has is the constant node with value 12. As every other node a `ConstantNode` takes in the control node first(`Start`), once we +drop the `Start` node from the inputs of `ConstantNode`: +``` +Node old_def = _inputs.removeLast(); +``` +we can also get rid of `ConstantNode`(`this`) from the outputs of `Start`: +``` +old_def.delUse(this) +``` +### Example 2: +``` +int a = 12; +int b = a + 1; +return 1; +``` +- Call `popN` on current scope. +- Realize that `b = a + 1;` has no uses - so we can kill it. +- In the kill function we can call `popN` but this time with the inputs of `b = a + 1;`(start killing them recursively) +- We start the killing process from the back and examine "1" first. This has no output other than the `AddNode`. Since `this = AddNode` calling `delUse` will mark "1" as dead. +- We now can kill "1" and call the `popN` function with one input(the control node). +- Now we examine "a" which has 2 uses at this point, the scope and `AddNode`. Since `this = AddNode` we will remove `AddNode` from its outputs, it will still have the scope as a user - so we can't delete it just yet. +- We move onto`a = 12`, since "a" has only one user left(the scope) and `this = scope` it can get killed easily. +- Same as before, we go through the inputs of "a" and will delete them from the outputs of the control node. + +![Graph3](../04-dce2.svg) + +## Delete old nodes after finding a better replacement + +Consider the following code: +``` +return (2+1)+3; +``` +Without DCE after the `idealize` call we would end up with: +![Graph3](../04-dce3.svg) + +After identifying a more optimal replacement value (6) for the expression (2 + 1) + 3, +we created a constant node to store this value. +However, we did not remove the original expression, +resulting in dangling nodes in our structure. + +To fix this, we introduce an extra `deadCodeElim` call that is responsible for deleting unused nodes. + + +```java +public final Node peephole( ) { + ... + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + ... + + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + ... +} +``` + +```java +// m is the new Node, self is the old. +// Return 'm', which may have zero uses but is alive nonetheless. +// If self has zero uses (and is not 'm'), {@link #kill} self. +private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.addUse(null); // Add bogus null use to keep m alive + kill(); // Kill self because replacing with 'm' + m.delUse(null); // Remove bogus null. + } + return m; +} +``` \ No newline at end of file diff --git a/docs/chapter04/lattice.gv b/docs/chapter04/lattice.gv new file mode 100644 index 00000000..6efef107 --- /dev/null +++ b/docs/chapter04/lattice.gv @@ -0,0 +1,97 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.6; + + TOP [label=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + CTRL [label="ctrl", fillcolor=yellow, shape=oval]; + + TOP -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + TOP -> INT_TOP; + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + INT_BOT -> BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
tuple
type
...
type
+ >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // Additional customization + {rank=same; TOP} + {rank=same; INT_TOP; TUPLE_TOP} + {rank=same; + CTRL; + INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; + } + {rank=same; INT_BOT, TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter04/lattice.svg b/docs/chapter04/lattice.svg new file mode 100644 index 00000000..35cb9296 --- /dev/null +++ b/docs/chapter04/lattice.svg @@ -0,0 +1,305 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +CTRL + +ctrl + + + +TOP->CTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL->BOT + + + + + +INT_MIN + +-n + + + +INT_TOP->INT_MIN + + + + + +INT_MINDOTS + +... + + + +INT_TOP->INT_MINDOTS + + + + + +INT_MINUS + +-1 + + + +INT_TOP->INT_MINUS + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_PLUS + +1 + + + +INT_TOP->INT_PLUS + + + + + +INT_MAXDOTS + +... + + + +INT_TOP->INT_MAXDOTS + + + + + +INT_MAX + ++n + + + +INT_TOP->INT_MAX + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +INT_MIN->INT_BOT + + + + + + +INT_MINDOTS->INT_BOT + + + + + + +INT_MINUS->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_PLUS->INT_BOT + + + + + + +INT_MAXDOTS->INT_BOT + + + + + + +INT_MAX->INT_BOT + + + + + +TUPLE1 + + + +tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/docs/chapter04/projnode.json b/docs/chapter04/projnode.json new file mode 100644 index 00000000..3d4d20cf --- /dev/null +++ b/docs/chapter04/projnode.json @@ -0,0 +1,14 @@ +{ + "ver": 1, + "comp": "chapter04/docs/projnode.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/projnode.png b/docs/chapter04/projnode.png new file mode 100644 index 00000000..bf7493f2 Binary files /dev/null and b/docs/chapter04/projnode.png differ diff --git a/docs/chapter04/projnode.svg b/docs/chapter04/projnode.svg new file mode 100644 index 00000000..b1291cdb --- /dev/null +++ b/docs/chapter04/projnode.svg @@ -0,0 +1,74 @@ +Start  #2#2 Start +Type not computed + +$ctrl  #4/0#4 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLarg  #6/1#6 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA -- cgit v1.2.3