diff options
| author | Cliff Click <cliffc@acm.org> | 2023-09-26 17:43:36 +0100 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-08 16:52:27 -0700 |
| commit | 4968424d5aceefcf5ab6af1c6c0f7d23b9cbfadf (patch) | |
| tree | 89003accfbac76326d23d104d3dfadfe879001b5 | |
| parent | 4947515d6133ddbd0489c395024f4c1ddf7a499c (diff) | |
| download | Simple-4968424d5aceefcf5ab6af1c6c0f7d23b9cbfadf.tar.gz Simple-4968424d5aceefcf5ab6af1c6c0f7d23b9cbfadf.zip | |
Chapter 2: Arithmetic
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
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 <helsgithub15@gmail.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
38 files changed, 2007 insertions, 45 deletions
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）の構築。 @@ -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 @@ +<svg aria-label="Compiler graph" width="320" height="208" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 208" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e5i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#5[0] → #1 · ASSOC</title></path><path class="edge CTRL" id="e6i0" d="M84,80 L84,128" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[0] → #1 · CTRL</title></path><path class="edge DATA" id="e6i1" d="M236,80 L236,85 Q236,90 231,90 L132,90 Q124,90 124,98 L124,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#6[1] → #5 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,30)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n5" data-id="5" transform="translate(176,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 #3 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(44,134)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 Return +Type not computed + +[0] → #1 CTRL +[1] → #5 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="624" height="208" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 624 208" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e2i0" d="M84,77 C84,101 388,3 388,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#2[0] → #1 · ASSOC</title></path><path class="edge ASSOC" id="e3i0" d="M84,77 C84,101 540,3 540,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #1 · ASSOC</title></path><path class="edge DATA" id="e4i1" d="M388,80 L388,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#4[1] → #2 · DATA</title></path><path class="edge DATA" id="e4i2" d="M540,80 L540,85 Q540,90 535,90 L426,90 Q418,90 418,98 L418,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#4[2] → #3 · DATA</title></path><path class="edge ASSOC" id="e5i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#5[0] → #1 · ASSOC</title></path><path class="edge CTRL" id="e6i0" d="M84,80 L84,128" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[0] → #1 · CTRL</title></path><path class="edge DATA" id="e6i1" d="M236,80 L236,85 Q236,90 231,90 L132,90 Q124,90 124,98 L124,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#6[1] → #5 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,30)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n2" data-id="2" transform="translate(328,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 #1 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n3" data-id="3" transform="translate(480,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #2 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(328,134)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>+</tspan><tspan class="node-id"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 + +Type not computed + +[0] → — DATA +[1] → #2 DATA +[2] → #3 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n5" data-id="5" transform="translate(176,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 #3 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n6" data-id="6" transform="translate(44,134)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 Return +Type not computed + +[0] → #1 CTRL +[1] → #5 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="350" height="312" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 350 312" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e2i0" d="M84,181 C84,205 114,3 114,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#2[0] → #1 · ASSOC</title></path><path class="edge ASSOC" id="e3i0" d="M84,181 C84,205 266,3 266,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #1 · ASSOC</title></path><path class="edge DATA" id="e4i1" d="M114,80 L114,85 Q114,90 119,90 L228,90 Q236,90 236,98 L236,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#4[1] → #2 · DATA</title></path><path class="edge DATA" id="e4i2" d="M266,80 L266,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#4[2] → #3 · DATA</title></path><path class="edge CTRL" id="e5i0" d="M84,184 L84,232" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#5[0] → #1 · CTRL</title></path><path class="edge DATA" id="e5i1" d="M236,184 L236,189 Q236,194 231,194 L132,194 Q124,194 124,202 L124,232" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#5[1] → #4 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,134)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n2" data-id="2" transform="translate(54,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 #1 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n3" data-id="3" transform="translate(206,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #2 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(176,134)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>+</tspan><tspan class="node-id"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 + +Type not computed + +[0] → — DATA +[1] → #2 DATA +[2] → #3 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n5" data-id="5" transform="translate(44,238)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 Return +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="320" height="208" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 208" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e13i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#13[0] → #1 · ASSOC</title></path><path class="edge CTRL" id="e14i0" d="M84,80 L84,128" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#14[0] → #1 · CTRL</title></path><path class="edge DATA" id="e14i1" d="M236,80 L236,85 Q236,90 231,90 L132,90 Q124,90 124,98 L124,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[1] → #13 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,30)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n13" data-id="13" transform="translate(176,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 #2 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n14" data-id="14" transform="translate(44,134)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 Return +Type not computed + +[0] → #1 CTRL +[1] → #13 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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 @@ +<svg aria-label="Compiler graph" width="472" height="520" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 472 520" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e2i0" d="M146,389 C146,413 176,211 176,235" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#2[0] → #1 · ASSOC</title></path><path class="edge ASSOC" id="e3i0" d="M146,389 C146,413 84,3 84,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #1 · ASSOC</title></path><path class="edge ASSOC" id="e4i0" d="M146,389 C146,413 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[0] → #1 · ASSOC</title></path><path class="edge DATA" id="e5i1" d="M84,80 L84,85 Q84,90 89,90 L198,90 Q206,90 206,98 L206,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#5[1] → #3 · DATA</title></path><path class="edge DATA" id="e5i2" d="M236,80 L236,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#5[2] → #4 · DATA</title></path><path class="edge ASSOC" id="e6i0" d="M146,389 C146,413 388,3 388,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #1 · ASSOC</title></path><path class="edge DATA" id="e7i1" d="M388,80 L388,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #6 · DATA</title></path><path class="edge DATA" id="e8i1" d="M206,184 L206,189 Q206,194 211,194 L320,194 Q328,194 328,202 L328,232" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #5 · DATA</title></path><path class="edge DATA" id="e8i2" d="M368,184 L368,189 Q368,194 363,194 L363,194 Q358,194 358,199 L358,232" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge DATA" id="e9i1" d="M176,288 L176,293 Q176,298 181,298 L290,298 Q298,298 298,306 L298,336" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #2 · DATA</title></path><path class="edge DATA" id="e9i2" d="M328,288 L328,336" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[2] → #8 · DATA</title></path><path class="edge CTRL" id="e10i0" d="M146,392 L146,440" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#10[0] → #1 · CTRL</title></path><path class="edge DATA" id="e10i1" d="M298,392 L298,397 Q298,402 293,402 L194,402 Q186,402 186,410 L186,440" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[1] → #9 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(86,342)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n2" data-id="2" transform="translate(116,238)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 #1 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n3" data-id="3" transform="translate(24,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #2 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(176,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 #3 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n5" data-id="5" transform="translate(146,134)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>*</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 * +Type not computed + +[0] → — DATA +[1] → #3 DATA +[2] → #4 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n6" data-id="6" transform="translate(328,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#5</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #5 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n7" data-id="7" transform="translate(308,134)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>-</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 - +Type not computed + +[0] → — DATA +[1] → #6 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g><g class="node" id="n8" data-id="8" transform="translate(268,238)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>+</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 + +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(238,342)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>+</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 + +Type not computed + +[0] → — DATA +[1] → #2 DATA +[2] → #8 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n10" data-id="10" transform="translate(106,446)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 Return +Type not computed + +[0] → #1 CTRL +[1] → #9 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> 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))を使うと +扱いやすくなります。ここで使う束は次の構造を持ちます。 + + + +この束の要素は、次の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; +``` + + + +* 制御ノードは、背景が薄い黄色の長方形で示しています。 +* 制御エッジは赤色です。 +* Constant から Start へのエッジは、本当の制御エッジではないため、灰色の破線で示しています。 +* 各エッジには、そのノードの入力リスト内での位置をラベルとして付けています。 + +## ピープホール最適化後 + + + +## 実例 + +最適化の動作を示すために、次のコードを考えます。 + +``` +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 は次の構造を持ちます。 + + + +両方のオペランドの値が分かっているので、それらを加算し、 +元のノードを、式の結果だけを保持する定数ノードに置き換えられます。 + +そのためには、ノードについて計算した型がすでに定数である一方、 +ノード自体はまだ定数ノードのインスタンスではないことを検出する必要があります。 + +これは次のように判定できます。 + +```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(); +``` + +これによって、ピープホールのアルゴリズムが再帰的に呼び出されます。 +結果は次のようになります。 + + + +定数値 `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<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + + _inputs.clear(); + _type=null; // Flag as dead + assert isDead(); // Really dead now +} +``` + +`isUnused` は、現在のノードに出力（このノードを使うノード）がないことを確認します。 +この例では、return 文が加算式を使うため、通常なら出力が1つあるはずです。 +しかし、最適化は Return ノードを作る前に行われるので、 +この時点では加算ノードを使うノードはありません。 + +したがって、そのノードを問題なく削除できます。 + +```java +for(int i=0; i<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + +_inputs.clear(); +_type=null; +``` + +最終的に、次のようになります。 + + + +## 実装上の注意 + +### *値*の等価性と*参照*の等価性 + +Simple の大部分では、ノードの検索（`find()` の呼び出し）に*参照*の等価性を使います。 +これが圧倒的に多いケースです。[第9章](../chapter09/README.ja.md)で初めて*値*の等価性を導入します。 +どちらの場合も、値の等価性と参照の等価性のどちらを使うかは意図的に選んでいます。 +「どちらか適当に選ぶ」ことが正しいケースは*決して*ありません。 +迷ったら文脈を確認してください。値の等価性を使うのは*大域的値番号付け（Global Value Numbering）*だけです。 +それ以外では、参照の等価性を意味しています。 diff --git a/docs/chapter02/README.md b/docs/chapter02/README.md new file mode 100644 index 00000000..585fe5ba --- /dev/null +++ b/docs/chapter02/README.md @@ -0,0 +1,290 @@ +# Chapter 2: Arithmetic + +English | [日本語](README.ja.md) + +[Previous: Chapter 1](../chapter01/README.md) | +[Next: Chapter 3](../chapter03/README.md) + + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Peephole Optimizations](#peephole-optimizations) +3. [Constant Folding and Constant Propagation](#constant-folding-and-constant-propagation) +4. [Nodes Pre Peephole Optimization](#nodes-pre-peephole-optimization) +5. [Post-peephole](#post-peephole) +6. [Demonstration](#demonstration) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter02) 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-chapter01...linear-chapter02) it to the previous chapter. + + +In this chapter we extend the language grammar to include arithmetic operations such as addition, subtraction, +multiplication, division, and unary minus. This allows us to write statements such as: + +``` +return 1 + 2 * 3 + -5; +``` + +Here is the [complete language grammar](02-grammar.md) for this chapter. + +## Extensions to Intermediate Representation + +We extend the set of nodes by adding the following additional node types: + +| Node Name | Type | Description | Inputs | Value | +|-----------|------|-------------------------------|------------------------------------------------------------|-----------------------------| +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | + + +We keep from [Chapter 1](../chapter01/README.md) the following nodes: Start, Return, Constant. + + +## Peephole Optimizations + +Nodes in the graph can be peephole-optimized. The graph is viewed through a +"peephole", a small chunk of graph, and if a certain pattern is detected we +locally rewrite the graph. + +During parsing, these peephole optimizations are particularly easy to check and +apply: there are no uses (yet) of a just-created Node from a just-parsed piece +of syntax, so there's no effort to the "rewrite" part of the program. We just +replace in-place before installing Nodes into the graph. + +This replacement might allow us to *kill* the unused inputs from the replaced +Node, basically doing a modest Dead Code Elimination during parsing. + +E.g. Suppose we already parsed out a constant `1`, and a constant `2`; then when we +parse an `Add(1,2)`, the peephole rule for constant math replaces the Add with a +constant `3`. At this point, we also *kill* the unused `Add`, which recursively +may *kill* the unused constants `1` and `2`. + + + +## Constant Folding and Constant Propagation + +In this chapter and the next we focus on a particular peephole optimization: +constant folding and constant propagation. Since we do not have non-constant values +until [Chapter 4](../chapter04/README.md), the main feature we demonstrate now is constant folding. +However, we introduce some additional ideas into the compiler at this stage, to +set the scene for Chapter 4. + +It is useful for the compiler to know at various points of the program whether +a node's value is a constant. The compiler can use this knowledge to perform various +optimizations such as: + +* Evaluate expressions at compile time and replace an expression with a + constant. This idea can be extended in a number of ways and is called + [Partial Evaluation](https://en.wikipedia.org/wiki/Partial_evaluation). +* The compiler may be able to identify regions of code that are dead and no + longer needed, such as when a conditional branch always takes one of the + branches ([Chapter 6](../chapter06/README.md)). +* Pointers may be known to be not-null, and a null check can be skipped ([Chapter 10](../chapter10/README.md)). +* Array indices may be known to be in-range, and a range check can be skipped. +* Many additional optimizations are possible when the compiler learns more + about the possible set of Node values. + +In order to achieve this, we need a way to talk about what kinds of values a Node can take +on at runtime - we call these Types, and we annotate Nodes with Types. + +The Type annotation serves two purposes: + +* it defines the set of operations allowed on the Node +* it defines the set of values the Node takes on + +The Type itself is represented as a Java class; the Java classes provide a +convenient way to represent the Type's structure; all types are subtypes of the +class `Type`. For now, we only have the following hierarchy of types: + +``` +Type ++-- TypeInteger +``` + +It turns out that the set of values associated with a Type at a specific Node +can be conveniently represented as a *lattice* +[wiki/Lattice_(order)](https://en.wikipedia.org/wiki/Lattice_(order)). Our lattice has the following structure: + + + +Our lattice elements can be one of three types: + +* The highest element is "top", denoted by ⊤; assigning ⊤ means that the Node's + value may or may not be a compile time constant. +* All elements in the middle are constants. +* The lowest is "bottom", denoted by ⊥; assigning ⊥ means that we know that the + Node's value is **not** a compile time constant. + +An invariant of peephole optimizations is that the type of a Node always moves +*up* the lattice (towards "top"); peepholes are *pessimistic* assuming the worst +until they can prove better. A later *optimistic* optimization will start all +Nodes at top and move Types down the lattice as eager assumptions are +proven wrong. + +In later chapters we will explore extending this lattice, as it frequently +forms the heart of core optimizations we want our compiler to do. + +We add a `_type` field to every Node, to store its current computed best +`Type`. We need the field to keep the optimizer runtime linear, and later when +doing an optimistic version of constant propagation (called [Sparse Conditional +Constant Propagation](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation)). + +We add a `_type` field even to `Start` and `Return`, and later to all control +Nodes - because the Sea of Nodes does not distinguish between control and data. +Both nodes are equally peepholed and optimized, and this will be covered +starting in [Chapter 4](../chapter04/README.md) and [Chapter +5](../chapter05/README.md). + + +There are other important properties of the Lattice that we discuss in [Chapter +4](../chapter04/README.md) and [Chapter 10](../chapter10/README.md), such as the "meet" and "join" operators and their rules. + + +## Nodes Pre Peephole Optimization + +The following schematic shows the operations before peephole folding. The parser +optimizes each node as it is built; it does not retain this entire intermediate graph: + +```java +return 1 + 2 * 3 + -5; +``` + + + +* Control nodes appear as rectangular boxes with pale yellow backgrounds +* Control edges are in red +* The edges from Constants to Start are shown as dashed gray lines as these are not true control edges +* We label each edge with its position in the node's list of inputs. + + +## Post-peephole + + + + +## Demonstration +To demonstrate how the optimisation works, let's consider the following code: +``` +return 1+2; +``` +This is parsed as: +```java + var lhs = parseMultiplication(); + if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); +``` +When the peephole is called on the AddNode node it first calls the compute function: +```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; + } +``` +In our case both of the operands(`1`, `2`) are constants, and instances of +`TypeInteger`. +Since `compute` returns a type, and we know that both of our operands are constants, we can do +constant propagation/folding where we compute the result of the expression so that instead of having `1+2` we can +have `3`. + +The `TypeInteger` class inherits from `Type` but also has a field that stores the value observed for that type. +```java + private final long _con; +``` + +AddNode has the layout: + + + +Since we already know the value of both of the operands, we can just add them together and replace the +old node with a constant node that just holds the result of the expression. + +To do this - we have to recognize this happens when the type computed for the node is already a constant, but the node +is still not an instance of constant node. + +This can be captured by: +```java +// Replace constant computations from non-constants with a constant node +if (!(this instanceof ConstantNode) && type.isConstant()) { + .... +} +``` +Note how we return a constant type when doing constant folding +```java +return TypeInteger.constant(i0.value()+i1.value()); +``` +We can create a constant node in the following way: +```java +return new ConstantNode(type).peephole(); +``` +This recursively calls the peephole algorithm. +Now, we end up with this: + + + +Notice how we added the constant node holding a constant value of `3`. +The remaining add node is unused and can be killed. + +We can call the kill function first: +```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(); +``` +This is responsible for deleting the dangling add node. + +```java +public void kill( ) { + assert isUnused(); // Has no uses, so it is dead + for( int i=0; i<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + + _inputs.clear(); + _type=null; // Flag as dead + assert isDead(); // Really dead now +} +``` + +`isUnused` - This makes sure the current node has no outputs. +Ideally, in our case there would be one output as the return statement is +using the add expression. +However, the optimisation happens before even creating the return node, which means that at this point +there are no users of the add node. + +We can now freely go ahead and delete the node. + +```java +for(int i=0; i<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + +_inputs.clear(); +_type=null; +``` + +We finally end up with this: + + + + +## Implementation Notes + +### *Value* equality vs *Reference* equality + +In much of Simple, Nodes are looked up (`find()` calls) via *reference* +equality. This is by far the most common case. In [Chapter +9](../chapter09/README.md) we introduce *value* equality for the first time. +In both cases the choice of value-vs-reference equality is intentional: it is +*never* correct to "just pick one or the other kind of equality". When in +doubt check the context: only *Global Value Numbering* uses value equality; +everywhere else we mean reference equality. diff --git a/docs/chapter02/lattice.gv b/docs/chapter02/lattice.gv new file mode 100644 index 00000000..fe8df136 --- /dev/null +++ b/docs/chapter02/lattice.gv @@ -0,0 +1,40 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.6; + + // ---------------------- + // Integers + INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<<B>⊥</B>: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 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="564pt" height="194pt"
+ viewBox="0.00 0.00 563.75 194.31" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 190.31)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-190.31 559.75,-190.31 559.75,4 -4,4"/>
+<!-- INT_TOP -->
+<g id="node1" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-168.31" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-164.26" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="275.47" y="-164.26" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_MIN -->
+<g id="node3" class="node">
+<title>INT_MIN</title>
+<ellipse fill="lightblue" stroke="black" cx="18.6" cy="-93.15" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="18.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">-n</text>
+</g>
+<!-- INT_TOP->INT_MIN -->
+<g id="edge1" class="edge">
+<title>INT_TOP->INT_MIN</title>
+<path fill="none" stroke="black" d="M247,-158.92C197.13,-144.78 96.96,-116.37 47.53,-102.36"/>
+<polygon fill="black" stroke="black" points="48.71,-99.06 38.13,-99.69 46.8,-105.79 48.71,-99.06"/>
+</g>
+<!-- INT_MINDOTS -->
+<g id="node4" class="node">
+<title>INT_MINDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="107.6" cy="-93.15" rx="27" ry="18"/>
+<text text-anchor="middle" x="107.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MINDOTS -->
+<g id="edge2" class="edge">
+<title>INT_TOP->INT_MINDOTS</title>
+<path fill="none" stroke="black" d="M250.93,-156.2C221.31,-143.38 172.55,-122.27 140.26,-108.29"/>
+<polygon fill="black" stroke="black" points="141.94,-105.21 131.38,-104.45 139.16,-111.63 141.94,-105.21"/>
+</g>
+<!-- INT_MINUS -->
+<g id="node5" class="node">
+<title>INT_MINUS</title>
+<ellipse fill="lightblue" stroke="black" cx="196.6" cy="-93.15" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="196.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">-1</text>
+</g>
+<!-- INT_TOP->INT_MINUS -->
+<g id="edge3" class="edge">
+<title>INT_TOP->INT_MINUS</title>
+<path fill="none" stroke="black" d="M260.02,-152.15C247.97,-141.13 231.55,-126.11 218.43,-114.12"/>
+<polygon fill="black" stroke="black" points="220.83,-111.57 211.09,-107.41 216.11,-116.74 220.83,-111.57"/>
+</g>
+<!-- INT_ZERO -->
+<g id="node6" class="node">
+<title>INT_ZERO</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-93.15" rx="18" ry="18"/>
+<text text-anchor="middle" x="276.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_TOP->INT_ZERO -->
+<g id="edge4" class="edge">
+<title>INT_TOP->INT_ZERO</title>
+<path fill="none" stroke="black" d="M276.6,-149.97C276.6,-141.92 276.6,-132.14 276.6,-123.02"/>
+<polygon fill="black" stroke="black" points="280.1,-123.13 276.6,-113.13 273.1,-123.13 280.1,-123.13"/>
+</g>
+<!-- INT_PLUS -->
+<g id="node7" class="node">
+<title>INT_PLUS</title>
+<ellipse fill="lightblue" stroke="black" cx="355.6" cy="-93.15" rx="18" ry="18"/>
+<text text-anchor="middle" x="355.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">1</text>
+</g>
+<!-- INT_TOP->INT_PLUS -->
+<g id="edge5" class="edge">
+<title>INT_TOP->INT_PLUS</title>
+<path fill="none" stroke="black" d="M292.96,-152.15C305.01,-141 321.48,-125.74 334.51,-113.68"/>
+<polygon fill="black" stroke="black" points="336.82,-116.31 341.78,-106.95 332.06,-111.18 336.82,-116.31"/>
+</g>
+<!-- INT_MAXDOTS -->
+<g id="node8" class="node">
+<title>INT_MAXDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="443.6" cy="-93.15" rx="27" ry="18"/>
+<text text-anchor="middle" x="443.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MAXDOTS -->
+<g id="edge6" class="edge">
+<title>INT_TOP->INT_MAXDOTS</title>
+<path fill="none" stroke="black" d="M302.32,-156.04C331.46,-143.28 379,-122.45 410.79,-108.53"/>
+<polygon fill="black" stroke="black" points="412.17,-111.74 419.93,-104.52 409.36,-105.33 412.17,-111.74"/>
+</g>
+<!-- INT_MAX -->
+<g id="node9" class="node">
+<title>INT_MAX</title>
+<ellipse fill="lightblue" stroke="black" cx="534.6" cy="-93.15" rx="21.15" ry="21.15"/>
+<text text-anchor="middle" x="534.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">+n</text>
+</g>
+<!-- INT_TOP->INT_MAX -->
+<g id="edge7" class="edge">
+<title>INT_TOP->INT_MAX</title>
+<path fill="none" stroke="black" d="M306.19,-158.92C355.31,-144.99 453.21,-117.23 503.38,-103.01"/>
+<polygon fill="black" stroke="black" points="504.07,-106.45 512.73,-100.35 502.16,-99.71 504.07,-106.45"/>
+</g>
+<!-- INT_BOT -->
+<g id="node2" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-18" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-13.95" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="275.47" y="-13.95" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_MIN->INT_BOT -->
+<g id="edge8" class="edge">
+<title>INT_MIN->INT_BOT</title>
+<path fill="none" stroke="black" d="M36.33,-87.13C77.31,-75.51 179.45,-46.55 236.48,-30.38"/>
+<polygon fill="black" stroke="black" points="237.13,-33.83 245.79,-27.73 235.22,-27.09 237.13,-33.83"/>
+</g>
+<!-- INT_MIN->INT_MINDOTS -->
+<!-- INT_MINDOTS->INT_BOT -->
+<g id="edge9" class="edge">
+<title>INT_MINDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M129.69,-82.59C157.87,-70.39 206.96,-49.14 240.58,-34.59"/>
+<polygon fill="black" stroke="black" points="241.73,-37.91 249.51,-30.72 238.95,-31.48 241.73,-37.91"/>
+</g>
+<!-- INT_MINDOTS->INT_MINUS -->
+<!-- INT_MINUS->INT_BOT -->
+<g id="edge10" class="edge">
+<title>INT_MINUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M210.17,-79.75C221.61,-69.28 238.28,-54.04 252.06,-41.44"/>
+<polygon fill="black" stroke="black" points="254.05,-44.36 259.07,-35.03 249.33,-39.19 254.05,-44.36"/>
+</g>
+<!-- INT_MINUS->INT_ZERO -->
+<!-- INT_ZERO->INT_BOT -->
+<g id="edge11" class="edge">
+<title>INT_ZERO->INT_BOT</title>
+<path fill="none" stroke="black" d="M276.6,-74.82C276.6,-66.77 276.6,-56.98 276.6,-47.86"/>
+<polygon fill="black" stroke="black" points="280.1,-47.98 276.6,-37.98 273.1,-47.98 280.1,-47.98"/>
+</g>
+<!-- INT_ZERO->INT_PLUS -->
+<!-- INT_PLUS->INT_BOT -->
+<g id="edge12" class="edge">
+<title>INT_PLUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M342.55,-80.07C331.3,-69.66 314.75,-54.33 301.04,-41.64"/>
+<polygon fill="black" stroke="black" points="303.78,-39.4 294.06,-35.17 299.02,-44.53 303.78,-39.4"/>
+</g>
+<!-- INT_PLUS->INT_MAXDOTS -->
+<!-- INT_MAXDOTS->INT_BOT -->
+<g id="edge13" class="edge">
+<title>INT_MAXDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M421.42,-82.44C393.56,-70.24 345.4,-49.14 312.32,-34.65"/>
+<polygon fill="black" stroke="black" points="314.1,-31.61 303.54,-30.8 311.29,-38.02 314.1,-31.61"/>
+</g>
+<!-- INT_MAXDOTS->INT_MAX -->
+<!-- INT_MAX->INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_MAX->INT_BOT</title>
+<path fill="none" stroke="black" d="M514.35,-86.41C471.9,-74.38 372.87,-46.3 316.93,-30.44"/>
+<polygon fill="black" stroke="black" points="318.05,-27.12 307.47,-27.76 316.14,-33.85 318.05,-27.12"/>
+</g>
+</g>
+</svg>
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<Node> _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 { * </pre> * @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: * * <pre> - * expr : primaryExpr + * expr : additiveExpr * </pre> * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { + private Node parseExpression() { return parseAddition(); } + + /** + * Parse an additive expression + * + * <pre> + * additiveExpr : multiplicativeExpr (('+' | '-') multiplicativeExpr)* + * </pre> + * @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 + * + * <pre> + * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)* + * </pre> + * @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. + * + * <pre> + * unaryExpr : ('-') unaryExpr | primaryExpr + * </pre> + * @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: * * <pre> - * primaryExpr : integerLiteral + * primaryExpr : integerLiteral | Identifier | '(' expression ')' * </pre> + * @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 { * </pre> */ 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> E del(ArrayList<E> 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 <E> int find( ArrayList<E> ary, E x ) { + for( int i=0; i<ary.size(); i++ ) + if( ary.get(i)==x ) + return i; + return -1; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java new file mode 100644 index 00000000..94aa4fbb --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.*; + +public class AddNode extends Node { + public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "Add"; } + + @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 () { + // TODO: add of 0, and many other peepholes added in Chaper04 + return null; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 01d9cbe1..cc1db452 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -1,6 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.print.ExprPrinter; + import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; /** * A Constant node represents a constant value. At present, the only constants @@ -15,15 +18,28 @@ import com.seaofnodes.simple.Parser; * The Constant's value is the value stored in it. */ public class ConstantNode extends Node { + final Type _con; + public ConstantNode( Type type ) { + super(Parser.START); + _con = type; + } - @Override public String label() { return "Con"; } - @Override protected String format() { return Long.toString(_value); } - @Override protected String repeatName() { return null; } + @Override protected String repeatName() { + return _con==null || _con.toString().length()<=32 ? null : uniqueName(); + } - public final long _value; + @Override + public String label() { return "Con"; } - public ConstantNode(long value) { - super(Parser.START); - _value = value; + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> 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.*; /** @@ -32,6 +37,12 @@ public abstract class Node extends BaseNode<Node> { public final ArrayList<Node> _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. * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. @@ -45,9 +56,14 @@ public abstract class Node extends BaseNode<Node> { _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 @@ -64,6 +80,119 @@ public abstract class Node extends BaseNode<Node> { public boolean isUnused() { return nOuts() == 0; } /** + * Change a <em>def</em> into a Node. Keeps the edges correct, by removing + * the corresponding <em>use->def</em> edge. This may make the original + * <em>def</em> 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 <N extends Node> 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 <em>uses</em>, by setting all of its <em>defs</em> + * 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<nIns(); i++ ) + setDef(i,null); // Set all inputs to null, recursively killing unused Nodes + _inputs.clear(); + _type=null; // Flag as dead + assert isDead(); // Really dead now + } + + // Mostly used for asserts and printing. + public boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + /** + * Try to peephole at this node and return a better replacement Node if + * possible. We compute a {@link Type} and then check and replace: + * <ul> + * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li> + * <li>in a future chapter we will look for a + * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> + * to eliminate.</li> + * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li> + * </ul> + */ + 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 + * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> + * as it is part of a Monotone Analysis Framework. + * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>. + * <p> + * 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. + * <p> + * 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<Node> _print1(ExprPrinter<Node> 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<Node> _print1(ExprPrinter<Node> 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<Node> { @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<Node> { private Parser _parser; private Node _ret; @@ -18,6 +18,7 @@ public class SimpleGraphObserver extends GraphCapture<Node> { } @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<Node> { @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 <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>. + * <p> + * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a> + * <p> + * 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. + * <p>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()); + } + +} |
