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 --- 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 +++++++++++ 19 files changed, 1412 insertions(+) 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 (limited to 'docs') 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 + + + + + -- cgit v1.2.3