From 4968424d5aceefcf5ab6af1c6c0f7d23b9cbfadf Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Sep 2023 17:43:36 +0100 Subject: Chapter 2: Arithmetic 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: Yichen Yan Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: hadha Co-authored-by: RobertObkircher Co-authored-by: Jun Kawasaki --- README.ja.md | 2 +- README.md | 2 +- docs/chapter02/02-demonstration-peephole.json | 14 + docs/chapter02/02-demonstration-peephole.svg | 73 ++++++ .../02-demonstration-pre-peephole-nokill.json | 17 ++ .../02-demonstration-pre-peephole-nokill.svg | 84 ++++++ docs/chapter02/02-demonstration-pre-peephole.json | 16 ++ docs/chapter02/02-demonstration-pre-peephole.svg | 81 ++++++ docs/chapter02/02-grammar.ja.md | 47 ++++ docs/chapter02/02-grammar.md | 42 +++ docs/chapter02/02-post-peephole-ex1.gv | 17 ++ docs/chapter02/02-post-peephole-ex1.json | 14 + docs/chapter02/02-post-peephole-ex1.svg | 73 ++++++ docs/chapter02/02-pre-peephole-ex1.gv | 34 +++ docs/chapter02/02-pre-peephole-ex1.json | 21 ++ docs/chapter02/02-pre-peephole-ex1.svg | 101 +++++++ docs/chapter02/Makefile | 1 + docs/chapter02/README.ja.md | 288 ++++++++++++++++++++ docs/chapter02/README.md | 290 +++++++++++++++++++++ docs/chapter02/lattice.gv | 40 +++ docs/chapter02/lattice.svg | 159 +++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 81 +++++- src/main/java/com/seaofnodes/simple/Utils.java | 39 +++ .../java/com/seaofnodes/simple/node/AddNode.java | 30 +++ .../com/seaofnodes/simple/node/ConstantNode.java | 30 ++- .../java/com/seaofnodes/simple/node/DivNode.java | 28 ++ .../java/com/seaofnodes/simple/node/MinusNode.java | 23 ++ .../java/com/seaofnodes/simple/node/MulNode.java | 26 ++ src/main/java/com/seaofnodes/simple/node/Node.java | 131 +++++++++- .../com/seaofnodes/simple/node/ReturnNode.java | 19 ++ .../java/com/seaofnodes/simple/node/StartNode.java | 24 +- .../java/com/seaofnodes/simple/node/SubNode.java | 27 ++ .../simple/print/SimpleGraphAdapter.java | 2 +- .../simple/print/SimpleGraphObserver.java | 4 +- src/main/java/com/seaofnodes/simple/type/Type.java | 45 ++++ .../com/seaofnodes/simple/type/TypeInteger.java | 41 +++ .../java/com/seaofnodes/simple/Chapter01Test.java | 26 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 60 +++++ 38 files changed, 2007 insertions(+), 45 deletions(-) create mode 100644 docs/chapter02/02-demonstration-peephole.json create mode 100644 docs/chapter02/02-demonstration-peephole.svg create mode 100644 docs/chapter02/02-demonstration-pre-peephole-nokill.json create mode 100644 docs/chapter02/02-demonstration-pre-peephole-nokill.svg create mode 100644 docs/chapter02/02-demonstration-pre-peephole.json create mode 100644 docs/chapter02/02-demonstration-pre-peephole.svg create mode 100644 docs/chapter02/02-grammar.ja.md create mode 100644 docs/chapter02/02-grammar.md create mode 100644 docs/chapter02/02-post-peephole-ex1.gv create mode 100644 docs/chapter02/02-post-peephole-ex1.json create mode 100644 docs/chapter02/02-post-peephole-ex1.svg create mode 100644 docs/chapter02/02-pre-peephole-ex1.gv create mode 100644 docs/chapter02/02-pre-peephole-ex1.json create mode 100644 docs/chapter02/02-pre-peephole-ex1.svg create mode 100644 docs/chapter02/Makefile create mode 100644 docs/chapter02/README.ja.md create mode 100644 docs/chapter02/README.md create mode 100644 docs/chapter02/lattice.gv create mode 100644 docs/chapter02/lattice.svg create mode 100644 src/main/java/com/seaofnodes/simple/Utils.java create mode 100644 src/main/java/com/seaofnodes/simple/node/AddNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/DivNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MinusNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MulNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/SubNode.java create mode 100644 src/main/java/com/seaofnodes/simple/type/Type.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeInteger.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter02Test.java diff --git a/README.ja.md b/README.ja.md index 678af6e3..4c71d15f 100644 --- a/README.ja.md +++ b/README.ja.md @@ -38,7 +38,7 @@ JIT コンパイルも視野に入れています。 Simple 言語のスタイルは、C または Java のサブセットに倣っています。 * [第1章](docs/chapter01/README.ja.md)：整数リテラルを返すスクリプト。引数を受け取らず、整数値を1つ返す空の関数。`return` 文。 -* 第2章：定数を使う加算、減算、乗算、除算などの単純な二項算術演算。ピープホール最適化と単純な定数畳み込み。 +* [第2章](docs/chapter02/README.ja.md)：定数を使う加算、減算、乗算、除算などの単純な二項算術演算。ピープホール最適化と単純な定数畳み込み。 * 第3章：ローカル変数と代入文。右辺での読み取り、SSA、ローカル変数が定数の場合の追加のピープホール最適化。 * 第4章：`arg` という名前の、定数ではない外部入力変数。定数と `arg` を使う二項演算と比較演算。ゼロ以外の値は真とみなします。代数的簡約によるピープホール最適化。 * 第5章：`if` 文。制御フローグラフ（CFG）の構築。 diff --git a/README.md b/README.md index 147dbb94..b3bc31d8 100644 --- a/README.md +++ b/README.md @@ -40,7 +40,7 @@ intermediate representation. The Simple language is styled after a subset of C or Java. * [Chapter 1](docs/chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement. -* Chapter 2: Simple binary arithmetic such as addition, subtraction, multiplication, division +* [Chapter 2](docs/chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding. * Chapter 3: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. diff --git a/docs/chapter02/02-demonstration-peephole.json b/docs/chapter02/02-demonstration-peephole.json new file mode 100644 index 00000000..f78a058e --- /dev/null +++ b/docs/chapter02/02-demonstration-peephole.json @@ -0,0 +1,14 @@ +{ + "ver": 1, + "comp": "chapter02/docs/02-demonstration-peephole.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 5, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter02/02-demonstration-peephole.svg b/docs/chapter02/02-demonstration-peephole.svg new file mode 100644 index 00000000..6742dc47 --- /dev/null +++ b/docs/chapter02/02-demonstration-peephole.svg @@ -0,0 +1,73 @@ +#5[0] → #1 · ASSOC#6[0] → #1 · CTRL#6[1] → #5 · DATAStart  #1#1 Start +Type not computed + +#3  #5#5 #3 +Type not computed + +[0] → #1 ASSOC0Return  #6#6 Return +Type not computed + +[0] → #1 CTRL +[1] → #5 DATA01 diff --git a/docs/chapter02/02-demonstration-pre-peephole-nokill.json b/docs/chapter02/02-demonstration-pre-peephole-nokill.json new file mode 100644 index 00000000..6a952f88 --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole-nokill.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter02/docs/02-demonstration-pre-peephole-nokill.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 3, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 2, "role": "DATA", "label": null}, {"idx": 2, "def": 3, "role": "DATA", "label": null}], "proj": null}, + {"id": 5, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter02/02-demonstration-pre-peephole-nokill.svg b/docs/chapter02/02-demonstration-pre-peephole-nokill.svg new file mode 100644 index 00000000..f581be2c --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole-nokill.svg @@ -0,0 +1,84 @@ +#2[0] → #1 · ASSOC#3[0] → #1 · ASSOC#4[1] → #2 · DATA#4[2] → #3 · DATA#5[0] → #1 · ASSOC#6[0] → #1 · CTRL#6[1] → #5 · DATAStart  #1#1 Start +Type not computed + +#1  #2#2 #1 +Type not computed + +[0] → #1 ASSOC0#2  #3#3 #2 +Type not computed + +[0] → #1 ASSOC0+  #4#4 + +Type not computed + +[0] → — DATA +[1] → #2 DATA +[2] → #3 DATA012#3  #5#5 #3 +Type not computed + +[0] → #1 ASSOC0Return  #6#6 Return +Type not computed + +[0] → #1 CTRL +[1] → #5 DATA01 diff --git a/docs/chapter02/02-demonstration-pre-peephole.json b/docs/chapter02/02-demonstration-pre-peephole.json new file mode 100644 index 00000000..b29cf6dd --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter02/docs/02-demonstration-pre-peephole.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 3, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 2, "role": "DATA", "label": null}, {"idx": 2, "def": 3, "role": "DATA", "label": null}], "proj": null}, + {"id": 5, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter02/02-demonstration-pre-peephole.svg b/docs/chapter02/02-demonstration-pre-peephole.svg new file mode 100644 index 00000000..a8319f8b --- /dev/null +++ b/docs/chapter02/02-demonstration-pre-peephole.svg @@ -0,0 +1,81 @@ +#2[0] → #1 · ASSOC#3[0] → #1 · ASSOC#4[1] → #2 · DATA#4[2] → #3 · DATA#5[0] → #1 · CTRL#5[1] → #4 · DATAStart  #1#1 Start +Type not computed + +#1  #2#2 #1 +Type not computed + +[0] → #1 ASSOC0#2  #3#3 #2 +Type not computed + +[0] → #1 ASSOC0+  #4#4 + +Type not computed + +[0] → — DATA +[1] → #2 DATA +[2] → #3 DATA012Return  #5#5 Return +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA01 diff --git a/docs/chapter02/02-grammar.ja.md b/docs/chapter02/02-grammar.ja.md new file mode 100644 index 00000000..5fbf930a --- /dev/null +++ b/docs/chapter02/02-grammar.ja.md @@ -0,0 +1,47 @@ +# 第2章の文法 + +[English](02-grammar.md) | 日本語 + +この文書は [第2章の文法定義](02-grammar.md) の日本語版です。 +文法定義そのものは原文と同一です。 + +[第2章：算術演算に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement EOF + ; + +statement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; +``` diff --git a/docs/chapter02/02-grammar.md b/docs/chapter02/02-grammar.md new file mode 100644 index 00000000..994a398a --- /dev/null +++ b/docs/chapter02/02-grammar.md @@ -0,0 +1,42 @@ +# Grammar for Chapter 2 + +English | [日本語](02-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement EOF + ; + +statement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; +``` diff --git a/docs/chapter02/02-post-peephole-ex1.gv b/docs/chapter02/02-post-peephole-ex1.gv new file mode 100644 index 00000000..6c2b23ae --- /dev/null +++ b/docs/chapter02/02-post-peephole-ex1.gv @@ -0,0 +1,17 @@ +digraph chapter02 { +/* +return 1+2*3+-5; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_13 [ label="#2" ]; + Return14 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_13 -> Start1[taillabel=0 style=dotted]; + Return14 -> Start1[taillabel=0 color=red]; + Return14 -> Con_13[taillabel=1]; +} diff --git a/docs/chapter02/02-post-peephole-ex1.json b/docs/chapter02/02-post-peephole-ex1.json new file mode 100644 index 00000000..e9c6d1eb --- /dev/null +++ b/docs/chapter02/02-post-peephole-ex1.json @@ -0,0 +1,14 @@ +{ + "ver": 1, + "comp": "chapter02/docs/02-post-peephole-ex1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 14, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter02/02-post-peephole-ex1.svg b/docs/chapter02/02-post-peephole-ex1.svg new file mode 100644 index 00000000..2f9fc49d --- /dev/null +++ b/docs/chapter02/02-post-peephole-ex1.svg @@ -0,0 +1,73 @@ +#13[0] → #1 · ASSOC#14[0] → #1 · CTRL#14[1] → #13 · DATAStart  #1#1 Start +Type not computed + +#2  #13#13 #2 +Type not computed + +[0] → #1 ASSOC0Return  #14#14 Return +Type not computed + +[0] → #1 CTRL +[1] → #13 DATA01 diff --git a/docs/chapter02/02-pre-peephole-ex1.gv b/docs/chapter02/02-pre-peephole-ex1.gv new file mode 100644 index 00000000..411de5ee --- /dev/null +++ b/docs/chapter02/02-pre-peephole-ex1.gv @@ -0,0 +1,34 @@ +digraph chapter02 { +/* +return 1+2*3+-5; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_2 [ label="#1" ]; + Con_3 [ label="#2" ]; + Con_4 [ label="#3" ]; + Mul5 [ label="*" ]; + Con_6 [ label="#5" ]; + Minus7 [ label="-" ]; + Add8 [ label="+" ]; + Add9 [ label="+" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_2 -> Start1[taillabel=0 style=dotted]; + Con_3 -> Start1[taillabel=0 style=dotted]; + Con_4 -> Start1[taillabel=0 style=dotted]; + Mul5 -> Con_3[taillabel=1]; + Mul5 -> Con_4[taillabel=2]; + Con_6 -> Start1[taillabel=0 style=dotted]; + Minus7 -> Con_6[taillabel=1]; + Add8 -> Mul5[taillabel=1]; + Add8 -> Minus7[taillabel=2]; + Add9 -> Con_2[taillabel=1]; + Add9 -> Add8[taillabel=2]; + Return10 -> Start1[taillabel=0 color=red]; + Return10 -> Add9[taillabel=1]; +} diff --git a/docs/chapter02/02-pre-peephole-ex1.json b/docs/chapter02/02-pre-peephole-ex1.json new file mode 100644 index 00000000..012bd814 --- /dev/null +++ b/docs/chapter02/02-pre-peephole-ex1.json @@ -0,0 +1,21 @@ +{ + "ver": 1, + "comp": "chapter02/docs/02-pre-peephole-ex1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 3, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 5, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 3, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 6, "label": "#5", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 7, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "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": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 2, "role": "DATA", "label": null}, {"idx": 2, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter02/02-pre-peephole-ex1.svg b/docs/chapter02/02-pre-peephole-ex1.svg new file mode 100644 index 00000000..0217cdd0 --- /dev/null +++ b/docs/chapter02/02-pre-peephole-ex1.svg @@ -0,0 +1,101 @@ +#2[0] → #1 · ASSOC#3[0] → #1 · ASSOC#4[0] → #1 · ASSOC#5[1] → #3 · DATA#5[2] → #4 · DATA#6[0] → #1 · ASSOC#7[1] → #6 · DATA#8[1] → #5 · DATA#8[2] → #7 · DATA#9[1] → #2 · DATA#9[2] → #8 · DATA#10[0] → #1 · CTRL#10[1] → #9 · DATAStart  #1#1 Start +Type not computed + +#1  #2#2 #1 +Type not computed + +[0] → #1 ASSOC0#2  #3#3 #2 +Type not computed + +[0] → #1 ASSOC0#3  #4#4 #3 +Type not computed + +[0] → #1 ASSOC0*  #5#5 * +Type not computed + +[0] → — DATA +[1] → #3 DATA +[2] → #4 DATA012#5  #6#6 #5 +Type not computed + +[0] → #1 ASSOC0-  #7#7 - +Type not computed + +[0] → — DATA +[1] → #6 DATA01+  #8#8 + +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #7 DATA012+  #9#9 + +Type not computed + +[0] → — DATA +[1] → #2 DATA +[2] → #8 DATA012Return  #10#10 Return +Type not computed + +[0] → #1 CTRL +[1] → #9 DATA01 diff --git a/docs/chapter02/Makefile b/docs/chapter02/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter02/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter02/README.ja.md b/docs/chapter02/README.ja.md new file mode 100644 index 00000000..f25b2f4f --- /dev/null +++ b/docs/chapter02/README.ja.md @@ -0,0 +1,288 @@ +# 第2章：算術演算 + +[English](README.md) | 日本語 + +この文書は [Chapter 2: Arithmetic](README.md) の日本語訳です。 + +[前の章：第1章](../chapter01/README.ja.md) | +[次の章：第3章](../chapter03/README.ja.md) + +# 目次 + +1. [中間表現の拡張](#中間表現の拡張) +2. [ピープホール最適化](#ピープホール最適化) +3. [定数畳み込みと定数伝播](#定数畳み込みと定数伝播) +4. [ピープホール最適化前のノード](#ピープホール最適化前のノード) +5. [ピープホール最適化後](#ピープホール最適化後) +6. [実例](#実例) +7. [実装上の注意](#実装上の注意) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git の変更履歴をたどって +[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter02)を読むことも、 +前の章との[差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter01...linear-chapter02)を見ることもできます。 + +この章では言語の文法を拡張し、加算、減算、乗算、除算、単項マイナスといった算術演算を扱えるようにします。 +これにより、次のような文を書けるようになります。 + +``` +return 1 + 2 * 3 + -5; +``` + +この章の[言語の文法全体](02-grammar.ja.md)はこちらです。 + +## 中間表現の拡張 + +次のノード型を追加して、ノードの種類を増やします。 + +| ノード名 | 種類 | 説明 | 入力 | 値 | +|----------|------|------|------|----| +| Add | データ | 2つの値を加算する | 2つのデータノード。値を加算する。順序は問わない | 加算の結果 | +| Sub | データ | ある値から別の値を減算する | 2つのデータノード。値を減算する。順序が重要 | 減算の結果 | +| Mul | データ | 2つの値を乗算する | 2つのデータノード。値を乗算する。順序は問わない | 乗算の結果 | +| Div | データ | ある値を別の値で除算する | 2つのデータノード。値を除算する。順序が重要 | 除算の結果 | +| Minus | データ | 値の符号を反転する | 1つのデータノード。値の符号を反転する | 単項マイナスの結果 | + +[第1章](../chapter01/README.ja.md)のノードである Start、Return、Constant は引き続き使います。 + +## ピープホール最適化 + +グラフ内のノードには、ピープホール最適化を適用できます。 +グラフの小さな部分を「のぞき穴（peephole）」から見るように調べ、 +特定のパターンが見つかれば、その部分のグラフを書き換えます。 + +構文解析中は、こうしたピープホール最適化の条件を調べて適用することが特に簡単です。 +解析したばかりの構文から作られたノードには、まだそれを使うノードがないため、 +「書き換え」の手間がかからないからです。グラフに組み込む前に、その場でノードを置き換えるだけです。 + +この置き換えによって、置き換え前のノードの入力のうち、使われなくなったものを*削除（kill）*できる場合があります。 +つまり、構文解析中に小規模なデッドコード除去を行うことになります。 + +たとえば、すでに定数 `1` と定数 `2` を解析したとします。 +続いて `Add(1,2)` を解析すると、定数の計算に対するピープホール規則が Add を定数 `3` に置き換えます。 +この時点で、使われなくなった `Add` も*削除*します。 +その結果、使われなくなった定数 `1` と `2` も再帰的に*削除*できる場合があります。 + +## 定数畳み込みと定数伝播 + +この章と次の章では、ピープホール最適化の中でも定数畳み込みと定数伝播に注目します。 +[第4章](../chapter04/README.ja.md)までは定数以外の値が登場しないため、 +ここで主に示すのは定数畳み込みです。ただし、第4章への準備として、 +この段階でコンパイラにいくつかの考え方を導入します。 + +プログラムのさまざまな箇所で、ノードの値が定数かどうかをコンパイラが把握していると便利です。 +その情報を使うと、次のような最適化を行えます。 + +* コンパイル時に式を評価し、その式を定数に置き換える。 + この考え方はさまざまな形に拡張でき、[部分評価（Partial Evaluation）](https://en.wikipedia.org/wiki/Partial_evaluation)と呼ばれます。 +* 条件分岐で常に同じ側の分岐が選ばれる場合などに、実行されず不要になったコード領域を特定する + （[第6章](../chapter06/README.ja.md)）。 +* ポインタが null でないと分かっている場合に、null チェックを省略する + （[第10章](../chapter10/README.ja.md)）。 +* 配列の添字が範囲内にあると分かっている場合に、範囲チェックを省略する。 +* ノードが取り得る値の集合について詳しく分かれば、さらに多くの最適化が可能になる。 + +これらを実現するには、ノードが実行時にどのような値を取り得るのかを表す方法が必要です。 +これを型（Type）と呼び、ノードに型を付与します。 + +型の付与には、2つの目的があります。 + +* ノードに対して許される操作の集合を定義する。 +* ノードが取り得る値の集合を定義する。 + +型そのものは Java のクラスで表します。Java のクラスを使うと、型の構造を簡単に表せます。 +すべての型は `Type` クラスのサブタイプです。現時点では、型の階層は次のものだけです。 + +``` +Type ++-- TypeInteger +``` + +あるノードの型に対応する値の集合は、[束（lattice）](https://en.wikipedia.org/wiki/Lattice_(order))を使うと +扱いやすくなります。ここで使う束は次の構造を持ちます。 + +![束](./lattice.svg) + +この束の要素は、次の3種類に分かれます。 + +* 最上位の要素は「トップ（top）」で、⊤ と表します。 + ⊤ を付与することは、そのノードの値がコンパイル時定数かもしれないし、そうでないかもしれないことを意味します。 +* 中間の要素はすべて定数です。 +* 最下位の要素は「ボトム（bottom）」で、⊥ と表します。 + ⊥ を付与することは、そのノードの値がコンパイル時定数では**ない**と分かっていることを意味します。 + +ピープホール最適化の不変条件の1つは、ノードの型が常に束の*上方向*（「トップ」の方向）に移動することです。 +ピープホール最適化は*悲観的*で、より良い状態を証明できるまでは最悪の状態を仮定します。 +後の章で扱う*楽観的*な最適化では、すべてのノードをトップから始め、 +楽観的な仮定が誤りだと分かるにつれて、型を束の下方向に移動させます。 + +束はコンパイラに行わせたい主要な最適化の中核になることが多いため、 +後の章ではこの束を拡張する方法を探ります。 + +すべてのノードに `_type` フィールドを追加し、現時点で計算された最も精度の高い `Type` を格納します。 +このフィールドは、最適化処理の実行時間を線形に保つために必要です。 +また、後の章で楽観的な定数伝播 +（[疎な条件付き定数伝播（Sparse Conditional Constant Propagation）](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation)）を行う際にも必要になります。 + +`Start` と `Return` にも `_type` フィールドを追加し、後にはすべての制御ノードに追加します。 +Sea of Nodes は制御とデータを区別しないからです。 +どちらのノードにも同じようにピープホール最適化が適用されます。 +これについては[第4章](../chapter04/README.ja.md)と[第5章](../chapter05/README.ja.md)から説明します。 + +束には、「meet（交わり）」や「join（結び）」という演算子とその規則など、ほかにも重要な性質があります。 +これらは[第4章](../chapter04/README.ja.md)と[第10章](../chapter10/README.ja.md)で説明します。 + +## ピープホール最適化前のノード + +次の模式図は、ピープホール最適化による畳み込み前の演算を示しています。 +パーサーは各ノードを構築した時点で最適化するので、この中間グラフ全体が保持されるわけではありません。 + +```java +return 1 + 2 * 3 + -5; +``` + +![ピープホール最適化前のグラフ](./02-pre-peephole-ex1.svg) + +* 制御ノードは、背景が薄い黄色の長方形で示しています。 +* 制御エッジは赤色です。 +* Constant から Start へのエッジは、本当の制御エッジではないため、灰色の破線で示しています。 +* 各エッジには、そのノードの入力リスト内での位置をラベルとして付けています。 + +## ピープホール最適化後 + +![ピープホール最適化後のグラフ](./02-post-peephole-ex1.svg) + +## 実例 + +最適化の動作を示すために、次のコードを考えます。 + +``` +return 1+2; +``` + +これは次のように解析されます。 + +```java + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); +``` + +AddNode ノードの `peephole` が呼ばれると、まず `compute` 関数を呼び出します。 + +```java + public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); +``` + +```java + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()+i1.value()); + } + return Type.BOTTOM; + } +``` + +この例では、両方のオペランド（`1` と `2`）が定数であり、その型は `TypeInteger` のインスタンスです。 +`compute` は型を返します。両方のオペランドが定数だと分かっているので、 +式の結果を計算する定数伝播・定数畳み込みを行い、`1+2` を `3` に置き換えられます。 + +`TypeInteger` クラスは `Type` を継承していますが、その型で確認された値を格納するフィールドも持っています。 + +```java + private final long _con; +``` + +AddNode は次の構造を持ちます。 + +![AddNode の構造](./02-demonstration-pre-peephole.svg) + +両方のオペランドの値が分かっているので、それらを加算し、 +元のノードを、式の結果だけを保持する定数ノードに置き換えられます。 + +そのためには、ノードについて計算した型がすでに定数である一方、 +ノード自体はまだ定数ノードのインスタンスではないことを検出する必要があります。 + +これは次のように判定できます。 + +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { + .... +} +``` + +定数畳み込みの際に、定数を表す型を返していることに注目してください。 + +```java +return TypeInteger.constant(i0.value()+i1.value()); +``` + +定数ノードは次のように作成できます。 + +```java +return new ConstantNode(type).peephole(); +``` + +これによって、ピープホールのアルゴリズムが再帰的に呼び出されます。 +結果は次のようになります。 + +![定数ノードを追加したグラフ](./02-demonstration-pre-peephole-nokill.svg) + +定数値 `3` を保持する定数ノードが追加されたことに注目してください。 +残っている加算ノードは使われていないので、削除できます。 + +先に `kill` 関数を呼び出すことができます。 + +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type).peephole(); +``` + +これによって、取り残された加算ノードを削除します。 + +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i⊤: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]; + + 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_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // Additional customization + {rank=same; INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; } +} diff --git a/docs/chapter02/lattice.svg b/docs/chapter02/lattice.svg new file mode 100644 index 00000000..b11d57aa --- /dev/null +++ b/docs/chapter02/lattice.svg @@ -0,0 +1,159 @@ + + + + + + +Lattice + + + +INT_TOP + +⊤ +:int + + + +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_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 + + + + + diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index c2ea3734..f59b0f25 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,6 +1,9 @@ package com.seaofnodes.simple; +import com.seaofnodes.graph.GraphObserver; + import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; /** * The Parser converts a Simple source program to the Sea of Nodes intermediate @@ -11,6 +14,9 @@ import com.seaofnodes.simple.node.*; */ public class Parser { + // Current compilation context; the observer belongs to the parser. + public static Parser PARSER; + public GraphObserver _obs; public int pos() { return _lexer._position; } @@ -29,10 +35,13 @@ public class Parser { public Parser(String source) { _lexer = new Lexer(source); + PARSER = this; Node.reset(); START = new StartNode(); } + String src() { return new String( _lexer._input ); } + public ReturnNode parse() { var ret = (ReturnNode) parseStatement(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -60,20 +69,61 @@ public class Parser { * * @return an expression {@link Node}, never {@code null} */ - private ReturnNode parseReturn() { + private Node parseReturn() { var expr = require(parseExpression(), ";"); - return new ReturnNode(START, expr); + return new ReturnNode(START, expr).peephole(); } /** * Parse an expression of the form: * * 
-     *     expr : primaryExpr
+     *     expr : additiveExpr
      *
* @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { + private Node parseExpression() { return parseAddition(); } + + /** + * Parse an additive expression + * + * 
+     *     additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)*
+     *
+ * @return an add expression {@link Node}, never {@code null} + */ + private Node parseAddition() { + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); + if (match("-")) return new SubNode(lhs, parseAddition()).peephole(); + return lhs; + } + + /** + * Parse an multiplicativeExpr expression + * + * 
+     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     *
+ * @return a multiply expression {@link Node}, never {@code null} + */ + private Node parseMultiplication() { + var lhs = parseUnary(); + if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); + if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); + return lhs; + } + + /** + * Parse a unary minus expression. + * + * 
+     *     unaryExpr : ('-') unaryExpr | primaryExpr
+     *
+ * @return a unary expression {@link Node}, never {@code null} + */ + private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); return parsePrimary(); } @@ -81,14 +131,14 @@ public class Parser { * Parse a primary expression: * * 
-     *     primaryExpr : integerLiteral
+     *     primaryExpr : integerLiteral | Identifier | '(' expression ')'
      *
+ * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - _lexer.skipWhiteSpace(); - if (_lexer.isNumber()) - return parseIntegerLiteral(); - throw error("Syntax error, expected integer literal"); + if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( match("(") ) return require(parseExpression(), ")"); + throw errorSyntax("integer literal"); } /** @@ -99,7 +149,7 @@ public class Parser { * */ private ConstantNode parseIntegerLiteral() { - return new ConstantNode(_lexer.parseNumber()); + return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } ////////////////////////////////// @@ -149,6 +199,12 @@ public class Parser { _input = buf; } + // Very handy in the debugger, shows the unparsed program + @Override + public String toString() { + return new String(_input, _position, _input.length - _position); + } + // True if at EOF private boolean isEOF() { return _position >= _input.length; @@ -212,11 +268,11 @@ public class Parser { boolean isNumber() {return isNumber(peek());} boolean isNumber(char ch) {return Character.isDigit(ch);} - private long parseNumber() { + private Type parseNumber() { String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); - return Long.parseLong(snum); + return TypeInteger.constant(Long.parseLong(snum)); } private String parseNumberString() { int start = _position; @@ -249,5 +305,4 @@ public class Parser { return new String(_input, start, 1); } } - } diff --git a/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..45f15327 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/Utils.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple; + +import java.util.ArrayList; + +public class Utils { + public static RuntimeException TODO() { return TODO("Not yet implemented"); } + public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } + + /** + * Fast, constant-time, element removal. Does not preserve order + * + * @param array ArrayList to modify + * @param i element to be removed + * @return element removed + */ + public static E del(ArrayList array, int i) { + if ( i >= 0 && i < array.size() ) { + E tmp = array.get(i); + E last = array.removeLast(); + if (i < array.size()) array.set(i, last); + return tmp; + } + return null; + } + + /** + * Search a list for an element by reference + * + * @param ary List to search in + * @param x Object to be searched + * @return >= 0 on success, -1 on failure + */ + public static int find( ArrayList ary, E x ) { + for( int i=0; i _print1(ExprPrinter p) { + return p.p(_con); } + + @Override + public Type compute() { return _con; } + + @Override + public Node idealize() { return null; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java new file mode 100644 index 00000000..d1a554bc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -0,0 +1,28 @@ +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); } + + @Override public String label() { return "Div"; } + + @Override protected String format() { return "(%1/%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return i1.value() == 0 + ? TypeInteger.ZERO + : TypeInteger.constant(i0.value()/i1.value()); + } + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java new file mode 100644 index 00000000..11769935 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -0,0 +1,23 @@ +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); } + + @Override public String label() { return "Minus"; } + + @Override protected String format() { return "(-%1)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0) + return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java new file mode 100644 index 00000000..abae6925 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -0,0 +1,26 @@ +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); } + + @Override public String label() { return "Mul"; } + + @Override protected String format() { return "(%1*%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()*i1.value()); + } + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index ed88e86e..3c0c3905 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -2,6 +2,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.BaseNode; +import com.seaofnodes.simple.Parser; + +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.Type; + import java.util.*; /** @@ -31,6 +36,12 @@ public abstract class Node extends BaseNode { */ public final ArrayList _outputs; + /** + * Current computed type for this Node. This value changes as the graph + * changes and more knowledge is gained about the program. + */ + public Type _type; + /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multi-threaded, this field will have to move into a TLS. @@ -45,9 +56,14 @@ public abstract class Node extends BaseNode { _outputs = new ArrayList<>(); for( Node n : _inputs ) if( n != null ) - n._outputs.add( this ); + n.addUse( this ); } + // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" + public abstract String label(); + + @Override public String typeName() { return _type==null ? null : _type.toString(); } + /** * Gets the ith input node * @param i Offset of the input node @@ -63,6 +79,119 @@ public abstract class Node extends BaseNode { public boolean isUnused() { return nOuts() == 0; } + /** + * Change a def into a Node. Keeps the edges correct, by removing + * the corresponding use->def edge. This may make the original + * def go dead. This function is co-recursive with {@link #kill}. + * + * @param idx which def to set + * @param new_def the new definition + * @return new_def for flow coding + */ + Node setDef(int idx, Node new_def ) { + Node old_def = in(idx); + if( old_def == new_def ) return this; // No change + // If new def is not null, add the corresponding def->use edge + // This needs to happen before removing the old node's def->use edge as + // the new_def might get killed if the old node kills it recursively. + if( new_def != null ) + new_def.addUse(this); + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + // Set the new_def over the old (killed) edge + _inputs.set(idx,new_def); + // Return self for easy flow-coding + return new_def; + } + + // Breaks the edge invariants, used temporarily + protected void addUse(N n) { _outputs.add(n); } + + // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place. + // Return true if the output list is empty afterward. + // Error is 'use' does not exist; ok for 'use' to be null. + protected boolean delUse( Node use ) { + Utils.del(_outputs, Utils.find(_outputs, use)); + return _outputs.size() == 0; + } + + /** + * Kill a Node with no uses, by setting all of its defs + * to null. This may recursively kill more Nodes and is basically dead + * code elimination. This function is co-recursive with {@link #setDef}. + */ + public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i + *
  • if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}
    • + *
  • in a future chapter we will look for a + * Common Subexpression + * to eliminate.
    • + *
  • we ask the Node for a better replacement (again, none enabled in this chapter)
    • + * + */ + public final Node peephole() { + var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(this); + Type old = _type; + Node n = peepholeOpt(); + Node rez = n == null ? this : n; + if( obs != null ) obs.after(this, n == null && old == _type ? null : rez, false); + return rez; + } + + private Node peepholeOpt() { + // 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()) { + kill(); // Kill `this` because replacing with a Constant + return new ConstantNode(type).peephole(); + } + + // Future chapter: Global Value Numbering goes here + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) return n; + + return null; // No progress + } + + /** + * This function needs to be + * Monotonic + * as it is part of a Monotone Analysis Framework. + * See for example this set of slides. + *

    + * For Chapter 2, all our Types are really integer constants, and so all + * the needed properties are trivially true, and we can ignore the high + * theory. Much later on, this will become important and allow us to do + * many fancy complex optimizations trivially... because theory. + *

    + * compute() needs to be stand-alone, and cannot recursively call compute + * on its inputs programs are cyclic (have loops!) and this will just + * infinitely recurse until stack overflow. Instead, compute typically + * computes a new type from the {@link #_type} field of its inputs. + */ + public abstract Type compute(); + + public abstract Node idealize(); + /** * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 85bbc83f..b48682ca 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,5 +1,9 @@ package com.seaofnodes.simple.node; +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. @@ -18,6 +22,21 @@ public class ReturnNode extends Node { public Node ctrl() { return in(0); } public Node expr() { return in(1); } + @Override + public String label() { return "Return"; } + + @Override + protected ExprPrinter _print1(ExprPrinter p) { + return p.p("return ").n(expr()).p(";"); + } + @Override public boolean isCFG() { return true; } + @Override + public Type compute() { + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 04bd6bb4..12f35736 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,9 +1,15 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; + /** - * The Start node represents the start of the function. For now, we do not have any inputs to Start because our function does not - * yet accept parameters. When we add parameters the value of Start will be a tuple, and will require Projections to extract the values. - * We discuss this in detail in Chapter 9: Functions and Calls. + * The Start node represents the start of the function. For now, we do not + * have any inputs to Start because our function does not yet accept + * parameters. When we add parameters the value of Start will be a tuple, and + * will require Projections to extract the values. We discuss this in detail + * in Chapter 9: Functions and Calls. */ public class StartNode extends Node { @@ -11,6 +17,18 @@ public class StartNode extends Node { super(); } + @Override + public String label() { return "Start"; } + + @Override protected ExprPrinter _print1(ExprPrinter p) { + return p.p(label()); + } + @Override public boolean isCFG() { return true; } + @Override + public Type compute() { return Type.BOTTOM; } + + @Override + public Node idealize() { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java new file mode 100644 index 00000000..88106018 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -0,0 +1,27 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class SubNode extends Node { + public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Sub"; } + + @Override protected String format() { return "(%1-%2)"; } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()-i1.value()); + } + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } + +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 20ee6aed..8f2f31ec 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** Chapter 1's view of the IR; browser, transport and layout are shared. */ +/** Chapter 2's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { @Override protected Kind kind(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 1c78e4dd..a17bf796 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 1's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 2's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; @@ -18,6 +18,7 @@ public class SimpleGraphObserver extends GraphCapture { } @Override protected void compile(String src) { _parser = new Parser(src); + _parser._obs = this; _phase = "Parse"; _ret = _parser.parse(); phase(_phase); @@ -25,6 +26,7 @@ public class SimpleGraphObserver extends GraphCapture { @Override protected String phase() { return _phase; } @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } @Override protected void detach() { + if( _parser != null ) _parser._obs = null; _parser = null; _ret = null; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java new file mode 100644 index 00000000..b98ce6de --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -0,0 +1,45 @@ +package com.seaofnodes.simple.type; + + +/** + * These types are part of a Monotone Analysis Framework, + * @see see for example this set of slides. + *

    + * The types form a lattice; @see a symmetric complete bounded (ranked) lattice. + *

    + * This wild lattice theory will be needed later to allow us to easily beef up + * the analysis and optimization of the Simple compiler... but we don't need it + * now, just know that it is coming along in a later Chapter. + *

    g + * One of the fun things here is that while the theory is deep and subtle, the + * actual implementation is darn near trivial and is generally really obvious + * what we're doing with it. Right now, it's just simple integer math to do + * simple constant folding e.g. 1+2 == 3 stuff. + */ + +public class Type { + + // ---------------------------------------------------------- + // Simple types are implemented fully here. "Simple" means: the code and + // type hierarchy are simple, not that the Type is conceptually simple. + static final byte TBOT = 0; // Bottom (ALL) + static final byte TTOP = 1; // Top (ANY) + static final byte TSIMPLE = 2; // End of the Simple Types + static final byte TINT = 3; // All Integers; see TypeInteger + public final byte _type; + + public boolean is_simple() { return _type < TSIMPLE; } + private static final String[] STRS = new String[]{"Bot","Top"}; + protected Type(byte type) { _type = type; } + + public static final Type BOTTOM = new Type( TBOT ); // ALL + + public boolean isConstant() { return _type == TTOP; } + + @Override + public String toString() { + return print(new StringBuilder()).toString(); + } + + public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} +} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java new file mode 100644 index 00000000..e0324da5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple.type; + +/** + * Integer Type + */ +public class TypeInteger extends Type { + + public final static TypeInteger ZERO= new TypeInteger(0); + + /** + * The constant value observed for this type + */ + private final long _con; + + public TypeInteger(long con) { + super(TINT); + _con = con; + } + + public static TypeInteger constant(long con) { return new TypeInteger(con); } + + @Override + public String toString() { + return print(new StringBuilder()).toString(); + } + + @Override + public StringBuilder print(StringBuilder sb) { return sb.append(_con); } + + @Override + public boolean isConstant() { return true; } + + public long value() { return _con; } + + @Override + public boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof TypeInteger i) ) return false; + return _con==i._con; + } +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index a91aabb1..49edfb5b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -17,7 +18,7 @@ public class Chapter01Test { Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); - assertEquals(1, con._value); + assertEquals(TypeInteger.constant(1), con._type); } else { fail(); } @@ -30,7 +31,7 @@ public class Chapter01Test { StartNode start = Parser.START; for( Node use : start._outputs ) if( use instanceof ConstantNode con ) - assertEquals(0,con._value); + assertEquals(TypeInteger.constant(0),con._type); } @Test @@ -54,13 +55,9 @@ public class Chapter01Test { } @Test - public void testBad3() { - try { - new Parser("return --12;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected integer literal",e.getMessage()); - } + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); } @Test @@ -73,15 +70,10 @@ public class Chapter01Test { } } - // Negative numbers require unary operator support that is not in scope @Test - public void testBad5() { - try { - new Parser("return -100;").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected integer literal",e.getMessage()); - } + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..6c816a23 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,60 @@ +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 Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + ReturnNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + ReturnNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + Parser parser = new Parser("return 1+2*3+-5;"); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + +} -- cgit v1.2.3