diff options
27 files changed, 1514 insertions, 16 deletions
diff --git a/README.ja.md b/README.ja.md index 4c71d15f..141963c6 100644 --- a/README.ja.md +++ b/README.ja.md @@ -39,7 +39,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第1章](docs/chapter01/README.ja.md)：整数リテラルを返すスクリプト。引数を受け取らず、整数値を1つ返す空の関数。`return` 文。 * [第2章](docs/chapter02/README.ja.md)：定数を使う加算、減算、乗算、除算などの単純な二項算術演算。ピープホール最適化と単純な定数畳み込み。 -* 第3章：ローカル変数と代入文。右辺での読み取り、SSA、ローカル変数が定数の場合の追加のピープホール最適化。 +* [第3章](docs/chapter03/README.ja.md)：ローカル変数と代入文。右辺での読み取り、SSA、ローカル変数が定数の場合の追加のピープホール最適化。 * 第4章：`arg` という名前の、定数ではない外部入力変数。定数と `arg` を使う二項演算と比較演算。ゼロ以外の値は真とみなします。代数的簡約によるピープホール最適化。 * 第5章：`if` 文。制御フローグラフ（CFG）の構築。 * 第6章：実行されない制御フローに対するピープホール最適化。 @@ -42,7 +42,7 @@ 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](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 +* [Chapter 3](docs/chapter03/README.md): Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. * Chapter 4: A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. diff --git a/docs/chapter03/03-grammar.ja.md b/docs/chapter03/03-grammar.ja.md new file mode 100644 index 00000000..5c79e725 --- /dev/null +++ b/docs/chapter03/03-grammar.ja.md @@ -0,0 +1,75 @@ +# 第3章の文法 + +[English](03-grammar.md) | 日本語 + +この文書は [原文](03-grammar.md) の日本語訳です。 + + +[第3章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter03/03-grammar.md b/docs/chapter03/03-grammar.md new file mode 100644 index 00000000..3ae8463e --- /dev/null +++ b/docs/chapter03/03-grammar.md @@ -0,0 +1,70 @@ +# Grammar for Chapter 3 + +English | [日本語](03-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : additiveExpression + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter03/03-graph1.gv b/docs/chapter03/03-graph1.gv new file mode 100644 index 00000000..7008a44e --- /dev/null +++ b/docs/chapter03/03-graph1.gv @@ -0,0 +1,39 @@ +digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_a">a</TD><TD PORT="Scope1_0_b">b</TD><TD PORT="Scope1_0_c">c</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_b">b</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; + Scope1_1:"Scope1_1_b" -> Con_6; +} diff --git a/docs/chapter03/03-graph1.json b/docs/chapter03/03-graph1.json new file mode 100644 index 00000000..5dce5431 --- /dev/null +++ b/docs/chapter03/03-graph1.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 7, "role": "ASSOC", "label": "0: c"}, {"idx": 3, "def": 6, "role": "ASSOC", "label": "1: b"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "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": 3, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph1.svg b/docs/chapter03/03-graph1.svg new file mode 100644 index 00000000..0ecaffac --- /dev/null +++ b/docs/chapter03/03-graph1.svg @@ -0,0 +1,86 @@ +<svg aria-label="Compiler graph" width="888" height="208" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 888 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="e1i0" d="M236,77 C236,101 696,74 696,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[0] → #3 · ASSOC · 0: a</title></path><path class="edge ASSOC" id="e1i1" d="M388,77 C388,101 744,74 744,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #4 · ASSOC · 0: b</title></path><path class="edge ASSOC" id="e1i2" d="M236,181 C236,205 792,74 792,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #7 · ASSOC · 0: c</title></path><path class="edge ASSOC" id="e1i3" d="M540,77 C540,101 840,74 840,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[3] → #6 · ASSOC · 1: b</title></path><path class="edge ASSOC" id="e3i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e4i0" d="M84,77 C84,101 388,3 388,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e6i0" d="M84,77 C84,101 540,3 540,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #2 · ASSOC</title></path><path class="edge DATA" id="e7i1" d="M236,80 L236,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #3 · DATA</title></path><path class="edge DATA" id="e7i2" d="M540,80 L540,85 Q540,90 535,90 L274,90 Q266,90 266,98 L266,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #6 · 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(672,98)" style="opacity: 1;"><path class="box" d="M4,0H188Q192,0 192,4V52Q192,56 188,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="96" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="96"/><title>#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #7 ASSOC 0: c +[3] → #6 ASSOC 1: b</title><line class="row" x1="0" x2="192" y1="30" y2="30"/><line class="row" x1="48" x2="48" y1="0" y2="30"/><line class="row" x1="96" x2="96" y1="0" y2="30"/><line class="row" x1="144" x2="144" y1="0" y2="30"/><text class="bind" x="24" y="20" text-anchor="middle">0: a</text><text class="bind" x="72" y="20" text-anchor="middle">0: b</text><text class="bind" x="120" y="20" text-anchor="middle">0: c</text><text class="bind" x="168" y="20" text-anchor="middle">1: b</text><circle class="port" cx="24" cy="0" r="3" fill="#536477"/><circle class="port" cx="72" cy="0" r="3" fill="#536477"/><circle class="port" cx="120" cy="0" r="3" fill="#536477"/><circle class="port" cx="168" cy="0" r="3" fill="#536477"/><text class="slot" x="24" y="-7" text-anchor="middle">0</text><text class="slot" x="72" y="-7" text-anchor="middle">1</text><text class="slot" x="120" y="-7" text-anchor="middle">2</text><text class="slot" x="168" y="-7" text-anchor="middle">3</text></g><g class="node" id="n2" data-id="2" 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"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" 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>#1</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #1 +Type not computed + +[0] → #2 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,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"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 #2 +Type not computed + +[0] → #2 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(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>#3</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #3 +Type not computed + +[0] → #2 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(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"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 + +Type not computed + +[0] → — DATA +[1] → #3 DATA +[2] → #6 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><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/chapter03/03-graph2.gv b/docs/chapter03/03-graph2.gv new file mode 100644 index 00000000..cafa7f25 --- /dev/null +++ b/docs/chapter03/03-graph2.gv @@ -0,0 +1,35 @@ +digraph chapter03 { +/* +int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_6 [ label="#3" ]; + Add7 [ label="+" ]; + Return8 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_a">a</TD><TD PORT="Scope1_0_b">b</TD><TD PORT="Scope1_0_c">c</TD></TR> + </TABLE>>]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_6 -> Start2[taillabel=0 style=dotted]; + Add7 -> Con_3[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + Return8 -> Start2[taillabel=0 color=red]; + Return8 -> Add7[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_a" -> Con_3; + Scope1_0:"Scope1_0_b" -> Con_4; + Scope1_0:"Scope1_0_c" -> Add7; +} diff --git a/docs/chapter03/03-graph2.json b/docs/chapter03/03-graph2.json new file mode 100644 index 00000000..80397161 --- /dev/null +++ b/docs/chapter03/03-graph2.json @@ -0,0 +1,18 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 7, "role": "ASSOC", "label": "0: c"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "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": 3, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph2.svg b/docs/chapter03/03-graph2.svg new file mode 100644 index 00000000..3904d87e --- /dev/null +++ b/docs/chapter03/03-graph2.svg @@ -0,0 +1,89 @@ +<svg aria-label="Compiler graph" width="840" height="312" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 840 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="e1i0" d="M236,77 C236,101 696,74 696,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[0] → #3 · ASSOC · 0: a</title></path><path class="edge ASSOC" id="e1i1" d="M388,77 C388,101 744,74 744,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #4 · ASSOC · 0: b</title></path><path class="edge ASSOC" id="e1i2" d="M236,181 C236,205 792,74 792,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #7 · ASSOC · 0: c</title></path><path class="edge ASSOC" id="e3i0" d="M84,181 C84,205 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e4i0" d="M84,181 C84,205 388,3 388,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e6i0" d="M84,181 C84,205 540,3 540,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #2 · ASSOC</title></path><path class="edge DATA" id="e7i1" d="M236,80 L236,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #3 · DATA</title></path><path class="edge DATA" id="e7i2" d="M540,80 L540,85 Q540,90 535,90 L274,90 Q266,90 266,98 L266,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #6 · DATA</title></path><path class="edge CTRL" id="e8i0" d="M84,184 L84,232" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#8[0] → #2 · CTRL</title></path><path class="edge DATA" id="e8i1" 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>#8[1] → #7 · 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(672,98)" style="opacity: 1;"><path class="box" d="M4,0H140Q144,0 144,4V52Q144,56 140,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="72" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="72"/><title>#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #7 ASSOC 0: c</title><line class="row" x1="0" x2="144" y1="30" y2="30"/><line class="row" x1="48" x2="48" y1="0" y2="30"/><line class="row" x1="96" x2="96" y1="0" y2="30"/><text class="bind" x="24" y="20" text-anchor="middle">0: a</text><text class="bind" x="72" y="20" text-anchor="middle">0: b</text><text class="bind" x="120" y="20" text-anchor="middle">0: c</text><circle class="port" cx="24" cy="0" r="3" fill="#536477"/><circle class="port" cx="72" cy="0" r="3" fill="#536477"/><circle class="port" cx="120" cy="0" r="3" fill="#536477"/><text class="slot" x="24" y="-7" text-anchor="middle">0</text><text class="slot" x="72" y="-7" text-anchor="middle">1</text><text class="slot" x="120" y="-7" text-anchor="middle">2</text></g><g class="node" id="n2" data-id="2" 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"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" 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>#1</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #1 +Type not computed + +[0] → #2 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,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"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 #2 +Type not computed + +[0] → #2 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(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>#3</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #3 +Type not computed + +[0] → #2 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(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"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 + +Type not computed + +[0] → — DATA +[1] → #3 DATA +[2] → #6 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="n8" data-id="8" 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"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 Return +Type not computed + +[0] → #2 CTRL +[1] → #7 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/chapter03/03-graph3.gv b/docs/chapter03/03-graph3.gv new file mode 100644 index 00000000..791a7dc1 --- /dev/null +++ b/docs/chapter03/03-graph3.gv @@ -0,0 +1,37 @@ +digraph chapter03 { +/* +int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_3 [ label="#1" ]; + Con_4 [ label="#2" ]; + Con_20 [ label="#8" ]; + Con_5 [ label="#3" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_6 [ label="#4" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_y0">y0</TD><TD PORT="Scope1_0_x0">x0</TD><TD PORT="Scope1_0_y1">y1</TD><TD PORT="Scope1_0_x1">x1</TD></TR> + </TABLE>>]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_3 -> Start2[taillabel=0 style=dotted]; + Con_4 -> Start2[taillabel=0 style=dotted]; + Con_20 -> Start2[taillabel=0 style=dotted]; + Con_5 -> Start2[taillabel=0 style=dotted]; + Return21 -> Start2[taillabel=0 color=red]; + Return21 -> Con_20[taillabel=1]; + Con_6 -> Start2[taillabel=0 style=dotted]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_y0" -> Con_4; + Scope1_0:"Scope1_0_x0" -> Con_3; + Scope1_0:"Scope1_0_y1" -> Con_6; + Scope1_0:"Scope1_0_x1" -> Con_5; +} diff --git a/docs/chapter03/03-graph3.json b/docs/chapter03/03-graph3.json new file mode 100644 index 00000000..a6d6175a --- /dev/null +++ b/docs/chapter03/03-graph3.json @@ -0,0 +1,19 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph3.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 4, "role": "ASSOC", "label": "0: y0"}, {"idx": 1, "def": 3, "role": "ASSOC", "label": "0: x0"}, {"idx": 2, "def": 6, "role": "ASSOC", "label": "0: y1"}, {"idx": 3, "def": 5, "role": "ASSOC", "label": "0: x1"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 5, "label": "#3", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#4", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 20, "label": "#8", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph3.svg b/docs/chapter03/03-graph3.svg new file mode 100644 index 00000000..4c5db5e0 --- /dev/null +++ b/docs/chapter03/03-graph3.svg @@ -0,0 +1,91 @@ +<svg aria-label="Compiler graph" width="1204" height="208" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1204 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="e1i0" d="M388,77 C388,101 1001.5,74 1001.5,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[0] → #4 · ASSOC · 0: y0</title></path><path class="edge ASSOC" id="e1i1" d="M236,77 C236,101 1052.5,74 1052.5,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #3 · ASSOC · 0: x0</title></path><path class="edge ASSOC" id="e1i2" d="M692,77 C692,101 1103.5,74 1103.5,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #6 · ASSOC · 0: y1</title></path><path class="edge ASSOC" id="e1i3" d="M540,77 C540,101 1154.5,74 1154.5,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[3] → #5 · ASSOC · 0: x1</title></path><path class="edge ASSOC" id="e3i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e4i0" d="M84,77 C84,101 388,3 388,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e5i0" d="M84,77 C84,101 540,3 540,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#5[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e6i0" d="M84,77 C84,101 692,3 692,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e20i0" d="M84,77 C84,101 844,3 844,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#20[0] → #2 · ASSOC</title></path><path class="edge CTRL" id="e21i0" d="M84,80 L84,128" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#21[0] → #2 · CTRL</title></path><path class="edge DATA" id="e21i1" d="M844,80 L844,85 Q844,90 839,90 L132,90 Q124,90 124,98 L124,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#21[1] → #20 · 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(976,98)" style="opacity: 1;"><path class="box" d="M4,0H200Q204,0 204,4V52Q204,56 200,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="102" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="102"/><title>#1 Scope +Type not computed + +[0] → #4 ASSOC 0: y0 +[1] → #3 ASSOC 0: x0 +[2] → #6 ASSOC 0: y1 +[3] → #5 ASSOC 0: x1</title><line class="row" x1="0" x2="204" y1="30" y2="30"/><line class="row" x1="51" x2="51" y1="0" y2="30"/><line class="row" x1="102" x2="102" y1="0" y2="30"/><line class="row" x1="153" x2="153" y1="0" y2="30"/><text class="bind" x="25.5" y="20" text-anchor="middle">0: y0</text><text class="bind" x="76.5" y="20" text-anchor="middle">0: x0</text><text class="bind" x="127.5" y="20" text-anchor="middle">0: y1</text><text class="bind" x="178.5" y="20" text-anchor="middle">0: x1</text><circle class="port" cx="25.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="76.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="127.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="178.5" cy="0" r="3" fill="#536477"/><text class="slot" x="25.5" y="-7" text-anchor="middle">0</text><text class="slot" x="76.5" y="-7" text-anchor="middle">1</text><text class="slot" x="127.5" y="-7" text-anchor="middle">2</text><text class="slot" x="178.5" y="-7" text-anchor="middle">3</text></g><g class="node" id="n2" data-id="2" 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"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" 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>#1</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #1 +Type not computed + +[0] → #2 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,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"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 #2 +Type not computed + +[0] → #2 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(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>#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] → #2 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(632,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>#4</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #4 +Type not computed + +[0] → #2 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="n20" data-id="20" transform="translate(784,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>#8</tspan><tspan class="node-id"> #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 #8 +Type not computed + +[0] → #2 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="n21" data-id="21" 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"> #21</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#21 Return +Type not computed + +[0] → #2 CTRL +[1] → #20 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/chapter03/03-graph4.json b/docs/chapter03/03-graph4.json new file mode 100644 index 00000000..b594eee2 --- /dev/null +++ b/docs/chapter03/03-graph4.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph4.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 8, "role": "ASSOC", "label": "0: c"}, {"idx": 3, "def": 6, "role": "ASSOC", "label": "1: b"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 6, "label": "#5", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 8, "label": "#6", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph4.svg b/docs/chapter03/03-graph4.svg new file mode 100644 index 00000000..c773ef9b --- /dev/null +++ b/docs/chapter03/03-graph4.svg @@ -0,0 +1,84 @@ +<svg aria-label="Compiler graph" width="1040" height="178" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1040 178" 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="e1i0" d="M236,77 C236,101 848,74 848,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[0] → #3 · ASSOC · 0: a</title></path><path class="edge ASSOC" id="e1i1" d="M388,77 C388,101 896,74 896,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #4 · ASSOC · 0: b</title></path><path class="edge ASSOC" id="e1i2" d="M692,77 C692,101 944,74 944,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #8 · ASSOC · 0: c</title></path><path class="edge ASSOC" id="e1i3" d="M540,77 C540,101 992,74 992,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[3] → #6 · ASSOC · 1: b</title></path><path class="edge ASSOC" id="e3i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e4i0" d="M84,77 C84,101 388,3 388,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e6i0" d="M84,77 C84,101 540,3 540,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#6[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e8i0" d="M84,77 C84,101 692,3 692,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#8[0] → #2 · ASSOC</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(824,98)" style="opacity: 1;"><path class="box" d="M4,0H188Q192,0 192,4V52Q192,56 188,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="96" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="96"/><title>#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #8 ASSOC 0: c +[3] → #6 ASSOC 1: b</title><line class="row" x1="0" x2="192" y1="30" y2="30"/><line class="row" x1="48" x2="48" y1="0" y2="30"/><line class="row" x1="96" x2="96" y1="0" y2="30"/><line class="row" x1="144" x2="144" y1="0" y2="30"/><text class="bind" x="24" y="20" text-anchor="middle">0: a</text><text class="bind" x="72" y="20" text-anchor="middle">0: b</text><text class="bind" x="120" y="20" text-anchor="middle">0: c</text><text class="bind" x="168" y="20" text-anchor="middle">1: b</text><circle class="port" cx="24" cy="0" r="3" fill="#536477"/><circle class="port" cx="72" cy="0" r="3" fill="#536477"/><circle class="port" cx="120" cy="0" r="3" fill="#536477"/><circle class="port" cx="168" cy="0" r="3" fill="#536477"/><text class="slot" x="24" y="-7" text-anchor="middle">0</text><text class="slot" x="72" y="-7" text-anchor="middle">1</text><text class="slot" x="120" y="-7" text-anchor="middle">2</text><text class="slot" x="168" y="-7" text-anchor="middle">3</text></g><g class="node" id="n2" data-id="2" 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"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" 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>#1</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #1 +Type not computed + +[0] → #2 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,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"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 #2 +Type not computed + +[0] → #2 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(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>#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] → #2 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="n8" data-id="8" transform="translate(632,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>#6</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 #6 +Type not computed + +[0] → #2 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><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/chapter03/03-graph5.json b/docs/chapter03/03-graph5.json new file mode 100644 index 00000000..476ad586 --- /dev/null +++ b/docs/chapter03/03-graph5.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter03/docs/03-graph5.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 3, "role": "ASSOC", "label": "0: a"}, {"idx": 1, "def": 4, "role": "ASSOC", "label": "0: b"}, {"idx": 2, "def": 11, "role": "ASSOC", "label": "0: c"}, {"idx": 3, "def": 9, "role": "ASSOC", "label": "1: e"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 4, "label": "#2", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 9, "label": "#6", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 11, "label": "#7", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "ASSOC", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter03/03-graph5.svg b/docs/chapter03/03-graph5.svg new file mode 100644 index 00000000..a62d03bb --- /dev/null +++ b/docs/chapter03/03-graph5.svg @@ -0,0 +1,84 @@ +<svg aria-label="Compiler graph" width="1040" height="178" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1040 178" 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="e1i0" d="M236,77 C236,101 848,74 848,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[0] → #3 · ASSOC · 0: a</title></path><path class="edge ASSOC" id="e1i1" d="M388,77 C388,101 896,74 896,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #4 · ASSOC · 0: b</title></path><path class="edge ASSOC" id="e1i2" d="M692,77 C692,101 944,74 944,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #11 · ASSOC · 0: c</title></path><path class="edge ASSOC" id="e1i3" d="M540,77 C540,101 992,74 992,98" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[3] → #9 · ASSOC · 1: e</title></path><path class="edge ASSOC" id="e3i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#3[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e4i0" d="M84,77 C84,101 388,3 388,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e9i0" d="M84,77 C84,101 540,3 540,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#9[0] → #2 · ASSOC</title></path><path class="edge ASSOC" id="e11i0" d="M84,77 C84,101 692,3 692,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#11[0] → #2 · ASSOC</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(824,98)" style="opacity: 1;"><path class="box" d="M4,0H188Q192,0 192,4V52Q192,56 188,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="96" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="96"/><title>#1 Scope +Type not computed + +[0] → #3 ASSOC 0: a +[1] → #4 ASSOC 0: b +[2] → #11 ASSOC 0: c +[3] → #9 ASSOC 1: e</title><line class="row" x1="0" x2="192" y1="30" y2="30"/><line class="row" x1="48" x2="48" y1="0" y2="30"/><line class="row" x1="96" x2="96" y1="0" y2="30"/><line class="row" x1="144" x2="144" y1="0" y2="30"/><text class="bind" x="24" y="20" text-anchor="middle">0: a</text><text class="bind" x="72" y="20" text-anchor="middle">0: b</text><text class="bind" x="120" y="20" text-anchor="middle">0: c</text><text class="bind" x="168" y="20" text-anchor="middle">1: e</text><circle class="port" cx="24" cy="0" r="3" fill="#536477"/><circle class="port" cx="72" cy="0" r="3" fill="#536477"/><circle class="port" cx="120" cy="0" r="3" fill="#536477"/><circle class="port" cx="168" cy="0" r="3" fill="#536477"/><text class="slot" x="24" y="-7" text-anchor="middle">0</text><text class="slot" x="72" y="-7" text-anchor="middle">1</text><text class="slot" x="120" y="-7" text-anchor="middle">2</text><text class="slot" x="168" y="-7" text-anchor="middle">3</text></g><g class="node" id="n2" data-id="2" 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"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" 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>#1</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 #1 +Type not computed + +[0] → #2 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,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"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 #2 +Type not computed + +[0] → #2 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="n9" data-id="9" 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>#6</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 #6 +Type not computed + +[0] → #2 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="n11" data-id="11" transform="translate(632,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>#7</tspan><tspan class="node-id"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 #7 +Type not computed + +[0] → #2 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><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/chapter03/Makefile b/docs/chapter03/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter03/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter03/README.ja.md b/docs/chapter03/README.ja.md new file mode 100644 index 00000000..a0fd8546 --- /dev/null +++ b/docs/chapter03/README.ja.md @@ -0,0 +1,167 @@ +# 第3章: 変数宣言 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第2章](../chapter02/README.ja.md) | +[次の章: 第4章](../chapter04/README.ja.md) + +# 目次 + +1. [中間表現の拡張](#中間表現の拡張) +2. [シンボルテーブル](#シンボルテーブル) +3. [ScopeNode](#scopenode) +4. [実例](#実例) +5. [ピープホール最適化の有効化](#ピープホール最適化の有効化) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter03) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter02...linear-chapter03) することもできます。 + +この章では、変数宣言を可能にするために言語の文法を拡張します。これにより、次のように書けます。 + +``` +int a=1; +int b=2; +int c=0; +{ + int b=3; + c=a+b; +} +return c; +``` + +この章の [完全な言語文法](03-grammar.ja.md) はこちらです。 + +## 中間表現の拡張 + +この章では次のノードを導入します。 + +| ノード名 | 種類 | 説明 | 入力 | 値 | +|-----------|--------------|--------------------------------|---------------------------------|-------| +| Scope | シンボルテーブル | グラフ内のスコープを表す | 変数を定義するすべてのノード | なし | + +前の章までのすべてのノードも引き続き使います。 + +## シンボルテーブル + +変数宣言とレキシカルスコープをサポートするため、パーサーにシンボルテーブルを導入します。シンボルテーブルは名前をノードに対応付けます。 + +シンボルテーブルの *スタック* を管理します。新しいレキシカルスコープが作られると、新しいシンボルテーブルをスタックにプッシュします。スコープを抜けると、スタックの最上部にあるシンボルテーブルをポップします。 + +名前を宣言すると、現在のシンボルテーブルに追加されます。名前に代入すると、最も新しいシンボルテーブル内の対応付けが更新されます。名前を参照すると、シンボルテーブル内でその対応付けを検索します。検索はレキシカルな順序で、シンボルテーブルのスタックをさかのぼります。 + +## ScopeNode + +ScopeNode は、レキシカルスコープの実装に使うシンボルテーブルのスタックをカプセル化します。 + +* レキシカルスコープ内の名前が参照するノードは、ScopeNode の入力になります。これにより ScopeNode がそれらの値の利用側となり、そのレキシカルスコープが生きている間、値も生存します。レキシカルスコープが終わると、これらの入力は取り除かれます。ピープホール最適化は死んだノードを削除し、新しいノードは生成直後には実質的に死んでいるため、これは極めて重要です。 +* 分岐を実装する [第5章](../chapter05/README.ja.md) では、分岐点で ScopeNode を複製し、分岐が合流するときにマージします。これにより、それぞれの分岐で名前を独立して更新できます。マージ地点では、異なる値になった名前に Phi ノードが必要です。 +* [第7章](../chapter07/README.ja.md) では、バックエッジからの Phi を扱う追加のロジックを導入します。 +* ScopeNode は、[第4章](../chapter04/README.ja.md) からは制御トークン、[第10章](../chapter10/README.ja.md) からはメモリ全体など、ほかの値の追跡にも使われます。これらには特別な名前の束縛を使い、それぞれの名前を分岐をまたいで追跡し、マージ地点でマージします。 +* [第10章](../chapter10/README.ja.md) では ScopeNode を拡張し、各名前の宣言された型も管理します。 + +実装上、各シンボルテーブルは `HashMap<String,Integer>` で表します。`String` は変数名で、`Integer` は ScopeNode の入力へのインデックスです。名前に対応するノードを取得するには、まずシンボルテーブルを調べ、次に ScopeNode の入力から必要なノードを取得します。シンボルテーブルのスタックは `Stack<HashMap<String,Integer>>` で表します。 + +レキシカルスコープを抜けるときは、そのスコープを表すシンボルテーブルをスタックからポップするだけでなく、対応する入力ノードも取り除きます。変数の式が Scope の対応付けのためだけに存在している場合（たとえば、その変数を使うコードをパーサーが解析する「かもしれない」ために保持していた場合）、この時点で式は死にます。 + +``` + int a=1; + { + int b=a*a*a; + } // When this scope closes and ends, b (and the cube of a) dies + return a; +``` + +可視化では、ScopeNode を独立した紫色の箱で示します。各束縛には、そのレキシカルスコープの階層をラベルとして付けます。シンボルテーブルの各変数から、グラフ内の定義ノードへ向かうエッジを示します。 + +ScopeNode はデータノードでも制御ノードでもありません。シンボルテーブルの管理と名前の検索のための補助機構であり、どこに Phi ノードが必要かを決める重要な役割を果たします。ノードとして表すことで、Sea of Nodes の定義・使用（def-use）アーキテクチャを利用して、スコープ内の値の生存性を維持できます。 + +ScopeNode に出力はありません。 + +## 実例 + +次のコードから得られる出力を示します。 + +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=3; +07 c=a+b; +08 } +09 return c; +``` + +* この例の解析を始めるとき、階層0のシンボルテーブルから始めます。変数 `a`、`b`、`c` をこのテーブルに登録します。 +* 4行目では、入れ子のスコープを開始します。この時点で新しいシンボルテーブルを階層1にプッシュします。 +* 5行目では、変数 `b` を宣言します。`b` を階層1のシンボルテーブルに登録し、2行目の同名の変数を隠します。 +* 7行目では、変数 `c` を更新します。変数の検索では、階層0のシンボルテーブルにある `c` が見つかります。 + +次の模式図は、定数畳み込み前の変数の束縛と算術演算を示します。コンパイラはグラフを構築しながらピープホール最適化を適用するため、この例の実際の結果は `return 4;` です。 + + + +この図は ScopeNode の束縛をスコープの階層とともに示します。`b` の2つの束縛は、異なるレキシカルスコープに属しています。 + +* 8行目で入れ子のスコープを抜けると、階層1のシンボルテーブルをポップします。 +* 9行目では、グラフは次のようになります。 + + + +この時点では、シンボルテーブルが1つだけ存在することがわかります。 + +プログラムの実行中には同じ階層のスコープが複数存在することもあります。ただし、各スコープ階層にはシンボルテーブルを1つしか保持できないため、同時に有効になるのは1つだけです。 + +たとえば、次のようになります。 + +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=5; +06 c=a+b; +08 } +09 { +10 int e=6; +11 c = a+e; +13 } +14 return c; +``` + +ここでは `(04-08)` と `(09-13)` の2つのスコープは同じ階層にあります。 + +```java +public final Stack<HashMap<String, Integer>> _scopes; +``` + +`_scopes` スタックは入れ子のスコープを保持します。インデックス0が最上位の（グローバル）スコープを表し、より大きなインデックスがより深い入れ子のスコープを表します。ポップすると現在のスコープを返し、外側のスコープに移ります。各インデックスと対応するスコープには、直接の1対1の対応があります。 + +最初の入れ子のスコープ（04-08）: + + + +2つ目の入れ子のスコープ（09-13）: + + + +* どちらの場合も、スコープの深さを表すインデックスは1です。 + +## ピープホール最適化の有効化 + +ピープホール最適化を有効にすると、パーサーはすべての式を定数に簡約できます。次の例がその様子をよく示しています。 + +``` +01 int x0=1; +02 int y0=2; +03 int x1=3; +04 int y1=4; +05 return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); +``` + +この例のグラフを次に示します。 + + + +Return ノードのデータ値は定数 `8` です！ 解析が終わって階層0のスコープが取り除かれると、`return 8` だけが残ります。 diff --git a/docs/chapter03/README.md b/docs/chapter03/README.md new file mode 100644 index 00000000..82393094 --- /dev/null +++ b/docs/chapter03/README.md @@ -0,0 +1,193 @@ +# Chapter 3: Variable Declarations + +English | [日本語](README.ja.md) + +[Previous: Chapter 2](../chapter02/README.md) | +[Next: Chapter 4](../chapter04/README.md) + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Symbol Tables](#symbol-tables) +3. [ScopeNode](#scopenode) +4. [Demonstration](#demonstration) +5. [Enabling peephole optimizations](#enabling-peephole-optimizations) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter03) 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-chapter02...linear-chapter03) it to the previous chapter. + +In this chapter we extend the language grammar to allow variable declarations. This allows us to write: + +``` +int a=1; +int b=2; +int c=0; +{ + int b=3; + c=a+b; +} +return c; +``` + +Here is the [complete language grammar](03-grammar.md) for this chapter. + + +## Extensions to Intermediate Representation + +In this chapter we introduce: + +| Node Name | Type | Description | Inputs | Value | +|-----------|--------------|--------------------------------|---------------------------------|-------| +| Scope | Symbol Table | Represents scopes in the graph | All nodes that define variables | None | + +and keep all nodes from prior chapters. + +## Symbol Tables + +To support variable declarations and lexical scopes, we introduce symbol tables +in the parser. A symbol table maps names to nodes. + +We maintain a *stack* of symbol tables. +When a new lexical scope is created we push a new symbol table to the stack; +when scope exits the topmost symbol table is popped from the stack. + +Declaring a name adds it to the current symbol table. If a name is assigned +to, then its mapping in the most recent symbol table is updated. If a name is +accessed, its mapping is looked up in the symbol tables. The lookup goes up +the stack of symbol tables, in lexical order. + +## ScopeNode + +A ScopeNode encapsulates the stack of symbol tables that are used to implement lexical scopes. + +* The nodes referenced by the names in a lexical scope become inputs to the + ScopeNode; this makes ScopeNode a user of these values, thus keeping them + alive while a particular lexical scope is alive. When the lexical scope + ends, those inputs are removed. This is crucial because peepholes will remove + dead Nodes and every new Node is effectively dead at the instant of creation. +* In [Chapter 5](../chapter05/README.md) when we implement branches, the ScopeNode gets duplicated at a branch point and then gets merged when the branch joins. This allows + the names to evolve in each branch independently. At the merge point, names that have diverged require a Phi node. +* In [Chapter 7](../chapter07/README.md) additional logic is deployed for handling Phis from back edges. +* The ScopeNode is used to track some other values such as the Control token starting from [Chapter 4](../chapter04/README.md), and whole memory starting from [Chapter 10](../chapter10/README.md). Special name bindings are used + for these, and each name is tracked across branches and then merged at merge points. +* In [Chapter 10](../chapter10/README.md) the ScopeNode is enhanced to also maintain the declared type for each name. + +From an implementation standpoint, each symbol table is represented as a `HashMap<String,Integer>`, where the `String` is the variable name, and the `Integer` is an index into the inputs of the +ScopeNode. To access the Node associated with a name, first the symbol table is consulted, and then the ScopeNode's inputs to find the required Node. +The stack of symbol tables is represented as `Stack<HashMap<String,Integer>>`. + +When a lexical scope is exited, we not only pop the symbol table representing the +scope from the stack, but also remove the relevant input nodes. If the variable's expression +only exists for the Scope mapping (e.g., "just in case" the Parser parses code +that uses the variable) this is when the expression dies: +``` + int a=1; + { + int b=a*a*a; + } // When this scope closes and ends, b (and the cube of a) dies + return a; +``` + + +In the visualization, we show the ScopeNode in a separate purple box. Each +binding is labelled with its lexical scope level. We show the edge from each +variable in the symbol table to the defining +Node in the graph. + +The ScopeNode is neither a Data Node nor a Control Node; it really is a utility for maintaining symbol tables, name lookups, plays a crucial role in deciding where Phi nodes are required. +Representing it as a Node allows us to leverage the Sea of Nodes def-use architecture to maintain liveness of values in scope. + +A ScopeNode has no outputs. + +## Demonstration + +We show the output from the following code. + +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=3; +07 c=a+b; +08 } +09 return c; +``` + +* When we start parsing the example above, we start with a symbol table (at level 0). +The variables `a`, `b`, and `c` are registered in this table. +* On line 4, we start a nested scope. At this point, a new symbol table is pushed (at level 1). +* On line 5, a variable `b` is declared. `b` is registered in the symbol table at level 1. This then +hides the variable with the same name on line 2. +* On line 7, we update the variable `c`. Variable lookup will find it in the symbol table at level 0. +The schematic below shows the variable bindings and arithmetic before constant +folding. The compiler applies peepholes as it builds the graph, so the actual +result of this example is `return 4;`. + + + +The diagram shows the ScopeNode's bindings with their scope levels. The two +bindings for `b` belong to different lexical scopes. + +* When we exit the nested scope on line 8, the symbol table at level 1 is popped. +* At line 9, our graph looks like this: + + + +As we see, only 1 symbol table is present at this point. + +We can also have multiple scopes at the same level during the execution of the program, +but only one will be active at a time because the symbol table can only hold one symbol table +for each scope level. + +For example: +``` +01 int a=1; +02 int b=2; +03 int c=0; +04 { +05 int b=5; +06 c=a+b; +08 } +09 { +10 int e=6; +11 c = a+e; +13 } +14 return c; +``` +Here both scopes starting from `(04-08)` and `(09-13)` are at the same level: +```java +public final Stack<HashMap<String, Integer>> _scopes; +``` +The `_scopes` stack holds nested scopes, with index 0 representing the highest (global) +scope and deeper indices representing more nested scopes. +Popping returns the current scope and moves to the outer one. +There is a direct one-to-one mapping between each index and its corresponding scope. + +The first nested scope (04-08): + + + +The second nested scope (09-13): + + + + - In both cases the index which represents the depth of the scope is 1. +## Enabling peephole optimizations + +Once we enable peephole optimizations, the parser is able to reduce all the expressions down to a +constant. This is illustrated nicely below. + +``` +01 int x0=1; +02 int y0=2; +03 int x1=3; +04 int y1=4; +05 return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); +``` + +The graph for the example above is displayed below. + + + +The return node has the constant `8` as its data value! When the parsing ends +and the scope at level 0 is removed, only the `return 8` remains. diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index f59b0f25..e6cb84f8 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -5,6 +5,8 @@ import com.seaofnodes.graph.GraphObserver; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import java.util.*; + /** * The Parser converts a Simple source program to the Sea of Nodes intermediate * representation directly in one pass. There is no intermediate Abstract @@ -32,33 +34,73 @@ public class Parser { // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; + /** + * Stack of lexical scopes, each scope is a symbol table that binds + * variable names to Nodes. The top of this stack represents current scope. + */ + public ScopeNode _scope; + + /** + * List of keywords disallowed as identifiers + */ + private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("int"); + add("return"); + }}; + public Parser(String source) { _lexer = new Lexer(source); PARSER = this; Node.reset(); + _scope = new ScopeNode(); START = new StartNode(); } String src() { return new String( _lexer._input ); } public ReturnNode parse() { - var ret = (ReturnNode) parseStatement(); + var ret = (ReturnNode) parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); return ret; } /** + * Parses a block + * + * <pre> + * '{' statements '}' + * </pre> + * Does not parse the opening or closing '{}' + * @return a {@link Node} or {@code null} + */ + private Node parseBlock() { + // Enter a new scope + _scope.push(); + Node n = null; + while (!peek('}') && !_lexer.isEOF()) { + Node n0 = parseStatement(); + if (n0 != null) n = n0; // Empty statements can return null + }; + // Exit scope + _scope.pop(); + return n; + } + + /** * Parses a statement * * <pre> - * returnStatement + * returnStatement | declStatement | blockStatement | expressionStatement * </pre> * @return a {@link Node} or {@code null} */ private Node parseStatement() { - if (matchx("return")) return parseReturn(); - throw errorSyntax("a statement"); + if (matchx("return") ) return parseReturn(); + else if (matchx("int")) return parseDecl(); + else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx(";")) return null; // Empty statement + else return parseExpressionStatement(); } /** @@ -74,6 +116,43 @@ public class Parser { return new ReturnNode(START, expr).peephole(); } + + + /** + * Parses an expression statement + * + * <pre> + * name '=' expression ';' + * </pre> + * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpressionStatement() { + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.update(name, expr)==null ) + throw error("Undefined name '" + name + "'"); + return expr; + } + + /** + * Parses a declStatement + * + * <pre> + * 'int' name = expression ';' + * </pre> + * @return an expression {@link Node}, never {@code null} + */ + private Node parseDecl() { + // Type is 'int' for now + var name = requireId(); + require("="); + var expr = require(parseExpression(), ";"); + if( _scope.define(name,expr) == null ) + throw error("Redefining name '" + name + "'"); + return expr; + } + /** * Parse an expression of the form: * @@ -138,7 +217,11 @@ public class Parser { private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); - throw errorSyntax("integer literal"); + String name = _lexer.matchId(); + if( name == null) throw errorSyntax("an identifier or expression"); + Node n = _scope.lookup(name); + if( n!=null ) return n; + throw error("Undefined name '" + name + "'"); } /** @@ -159,6 +242,15 @@ public class Parser { private boolean match (String syntax) { return _lexer.match (syntax); } // Match must be "exact", not be followed by more id letters private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + // Return true and do NOT skip if 'ch' is next + private boolean peek(char ch) { return _lexer.peek(ch); } + + // Require and return an identifier + private String requireId() { + String id = _lexer.matchId(); + if (id != null && !KEYWORDS.contains(id) ) return id; + throw error("Expected an identifier, found '"+id+"'"); + } // Require an exact match private void require(String syntax) { require(null, syntax); } @@ -256,6 +348,17 @@ public class Parser { return false; } + private boolean peek(char ch) { + skipWhiteSpace(); + return peek()==ch; + } + + // Return an identifier or null + String matchId() { + skipWhiteSpace(); + return isIdStart(peek()) ? parseId() : null; + } + // Used for errors String getAnyNextToken() { if (isEOF()) return ""; diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 3c0c3905..54687b2e 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -83,6 +83,13 @@ public abstract class Node extends BaseNode<Node> { * 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}. + * <p> + + * This method is the normal path for altering a Node, because it does the + * proper default edge maintenance. It also <em>immediately</em> kills + * Nodes that lose their last use; at times care must be taken to avoid + * killing Nodes that are being used without having an output Node. This + * definitely happens in the middle of recursive {@link #peephole} calls. * * @param idx which def to set * @param new_def the new definition @@ -105,6 +112,22 @@ public abstract class Node extends BaseNode<Node> { return new_def; } + /** + * Add a new def to an existing Node. Keep the edges correct by + * adding the corresponding <em>def->use</em> edge. + * + * @param new_def the new definition, appended to the end of existing definitions + * @return new_def for flow coding + */ + Node addDef(Node new_def) { + // Add use->def edge + _inputs.add(new_def); + // If new def is not null, add the corresponding def->use edge + if( new_def != null ) + new_def.addUse(this); + return new_def; + } + // Breaks the edge invariants, used temporarily protected <N extends Node> void addUse(N n) { _outputs.add(n); } @@ -116,16 +139,25 @@ public abstract class Node extends BaseNode<Node> { return _outputs.size() == 0; } + // Shortcut for "popping" n nodes. A "pop" is basically a + // set_def(last,null) followed by lowering the nIns() count. + void popN(int n) { + for( int i=0; i<n; i++ ) { + Node old_def = _inputs.removeLast(); + if( old_def != null && // If it exists and + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + } + } + /** * 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}. + * code elimination. This function is co-recursive with {@link #popN}. */ 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(); + popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead assert isDead(); // Really dead now } @@ -197,4 +229,24 @@ public abstract class Node extends BaseNode<Node> { * Node unique id generator, and is done as part of making a new Parser. */ public static void reset() { UNIQUE_ID = 1; } + + /** + * Debugging utility to find a Node by index + */ + public Node find(int nid) { return _find(new BitSet(),nid); } + private Node _find(BitSet visit, int nid) { + if( _nid==nid ) return this; + if( visit.get(_nid) ) return null; + visit.set(_nid); + for( Node def : _inputs ) + if( def!=null ) { + Node rez = def._find(visit,nid); + if( rez != null ) return rez; + } + for( Node use : _outputs ) { + Node rez = use._find(visit,nid); + if( rez != null ) return rez; + } + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java new file mode 100644 index 00000000..95c25391 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -0,0 +1,130 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; + +import java.util.*; + +/** + * The Scope node is purely a parser helper - it tracks names to nodes with a + * stack of scopes. + * @see <a href="file:../../../../../../../../chapter03/README.md">chapter03/README.md</a> + */ +public class ScopeNode extends Node { + + /** + * A Stack of symbol tables; a symbol table is a map from names to node indices. + */ + public final Stack<HashMap<String, Integer>> _scopes; + + + // A new ScopeNode + public ScopeNode() { + _scopes = new Stack<>(); + _type = Type.BOTTOM; + } + + + @Override public String label() { return "Scope"; } + + @Override + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + p.p(label()); + for( HashMap<String,Integer> scope : _scopes ) { + p.p("["); + boolean first=true; + for( String name : scope.keySet() ) { + if( !first ) p.p(", "); + first=false; + p.p(name).p(":"); + Node n = in(scope.get(name)); + if( n==null ) p.p("null"); + else p.n(n); + } + p.p("]"); + } + return p; + } + + /** + * Recover the names for all variable bindings. + * The result is an array of names that is aligned with the + * inputs to the Node. + * <p> + * This is an expensive operation. + */ + public String[] reverseNames() { + String[] names = new String[nIns()]; + for( HashMap<String,Integer> syms : _scopes ) + for( String name : syms.keySet() ) + names[syms.get(name)] = name; + return names; + } + + @Override public Type compute() { return Type.BOTTOM; } + + @Override public Node idealize() { return null; } + + public void push() { _scopes.push(new HashMap<>()); } + public void pop() { popN(_scopes.pop().size()); } + + /** + * Create a new name in the current scope + */ + public Node define( String name, Node n ) { + HashMap<String,Integer> syms = _scopes.lastElement(); + if( syms.put(name,nIns()) != null ) + return null; // Double define + return addDef(n); + } + /** + * Lookup a name in all scopes starting from most deeply nested. + * <p> + * @param name Name to be looked up + * @see #update(String, Node, int) + */ + public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + /** + * If the name is present in any scope, then redefine else null + * <p> + * @param name Name being redefined + * @param n The node to bind to the name + */ + public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + /** + * Both recursive lookup and update. + * <p> + * A shared implementation allows us to create lazy phis both during + * lookups and updates; the lazy phi creation is part of chapter 8. + * + * @param name Name whose binding is being updated or looked up + * @param n If null, do a lookup, else update binding + * @param nestingLevel The starting nesting level + * @return node being looked up, or the one that was updated + */ + private Node update( String name, Node n, int nestingLevel ) { + if( nestingLevel<0 ) return null; // Missed in all scopes, not found + var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var idx = syms.get(name); + if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope + Node old = in(idx); + // If n is null we are looking up rather than updating, hence return existing value + return n==null ? old : setDef(idx,n); + } + + public Node ctrl() { return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ + public Node ctrl(Node n) { return setDef(0,n); } + +} diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 8f2f31ec..c97aaf55 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,16 +5,21 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** Chapter 2's view of the IR; browser, transport and layout are shared. */ +/** Chapter 3's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { + @Override protected String[] edgeNames(Node n) { + return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; + } + @Override protected Kind kind(Node n) { + if( n instanceof ScopeNode ) return Kind.SCOPE; if( n instanceof StartNode ) return Kind.CTRL; return n.isCFG() ? Kind.CTRL : Kind.DATA; } @Override protected Role role(Node n, int i) { - if( n instanceof ConstantNode ) return Role.ASSOC; + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; if( i == 0 ) return Role.CTRL; return Role.DATA; } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index a17bf796..2dc5d844 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 2's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 3's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; @@ -30,6 +30,7 @@ public class SimpleGraphObserver extends GraphCapture<Node> { _parser = null; _ret = null; } + @Override protected Node scope() { return _parser._scope; } @Override protected void roots(ArrayList<Node> roots) { roots.add(Parser.START); roots.add(_ret); diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 49edfb5b..311ca23b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -40,7 +40,7 @@ public class Chapter01Test { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: ret",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } @@ -82,7 +82,7 @@ public class Chapter01Test { new Parser("return100").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, expected a statement: return100",e.getMessage()); + assertEquals("Syntax error, expected =: ",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..9a7dda5d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,68 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + ReturnNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + ReturnNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); + ReturnNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testRedeclareVar() { + try { + new Parser("int a=1; int b=2; int c=0; int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Redefining name 'b'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} |
