diff options
| author | Cliff Click <cliffc@acm.org> | 2023-12-03 23:23:04 +0000 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-08 16:52:27 -0700 |
| commit | 67ee27bfb29036efe7b154f633817aa152182684 (patch) | |
| tree | 89e8b5d5413ff19721328f9f2fef87704d1223f3 | |
| parent | f4d0e1583b9ae0237422640d8ee7eea5ce8aad6f (diff) | |
| download | Simple-67ee27bfb29036efe7b154f633817aa152182684.tar.gz Simple-67ee27bfb29036efe7b154f633817aa152182684.zip | |
Chapter 8: Lazy Phis, Break, Continue, and Evaluator
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
40 files changed, 3146 insertions, 62 deletions
@@ -39,7 +39,7 @@ main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) include $(firstword $(wildcard ../graph/graph.mk graph/graph.mk)) include $(firstword $(wildcard ../print/print.mk print/print.mk)) test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) -test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(test_javas)) +test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) classes = $(main_classes) $(test_classes) # All the libraries libs = $(wildcard lib/*jar) @@ -69,7 +69,7 @@ $(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" tests: $(default_targets) - $(JVM) org.junit.runner.JUnitCore $(test_cp) + $(JVM) org.junit.runner.JUnitCore $(test_cp) com.seaofnodes.simple.FuzzerWrap .PHONY: clean clean: diff --git a/README.ja.md b/README.ja.md index c1b587ef..584d4bcf 100644 --- a/README.ja.md +++ b/README.ja.md @@ -44,7 +44,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第5章](docs/chapter05/README.ja.md)：`if` 文。制御フローグラフ（CFG）の構築。 * [第6章](docs/chapter06/README.ja.md)：実行されない制御フローに対するピープホール最適化。 * [第7章](docs/chapter07/README.ja.md)：`while` 文。ループ構造と先行的な Phi の導入。 -* 第8章：ループ構造の続き。必要時の Phi の生成、`break` 文と `continue` 文。 +* [第8章](docs/chapter08/README.ja.md)：ループ構造の続き。必要時の Phi の生成、`break` 文と `continue` 文。 * 第9章：大域的値番号付け。不動点に達するまでのピープホール最適化の反復。ワークリスト。 * 第10章：ユーザー定義の構造体、ポインタ、null 解析。SSA で表す単一のメモリ値。ロード、ストア、実行可能な評価器。 * 第11章：同値類によるエイリアス解析。`MemMerge`、`MemPhi`、`BulkMemPhi` による必要時のメモリ分割。 @@ -51,7 +51,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. * [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow. * [Chapter 7](docs/chapter07/README.md): `while` statement; looping constructs - eager phi approach. -* Chapter 8: Looping constructs continued, lazy phi creation, `break` and `continue` statements. +* [Chapter 8](docs/chapter08/README.md): Looping constructs continued, lazy phi creation, `break` and `continue` statements. * Chapter 9: Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * Chapter 10: User defined structs, pointers and null analysis. One memory value in SSA. Loads, stores, and an executable evaluator. diff --git a/docs/chapter08/08-grammar.ja.md b/docs/chapter08/08-grammar.ja.md new file mode 100644 index 00000000..d88eb1c1 --- /dev/null +++ b/docs/chapter08/08-grammar.ja.md @@ -0,0 +1,101 @@ +# 第8章の文法 + +[English](08-grammar.md) | 日本語 + +この文書は [原文](08-grammar.md) の日本語訳です。 + + +[第8章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' 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/chapter08/08-grammar.md b/docs/chapter08/08-grammar.md new file mode 100644 index 00000000..0c1d05da --- /dev/null +++ b/docs/chapter08/08-grammar.md @@ -0,0 +1,96 @@ +# Grammar for Chapter 8 + +English | [日本語](08-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' 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/chapter08/08-graph1.gv b/docs/chapter08/08-graph1.gv new file mode 100644 index 00000000..604ee0fe --- /dev/null +++ b/docs/chapter08/08-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg35 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Region39 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return40 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;Phi_arg35;} + { rank=same; Region39;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return40[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region39[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If11:p1[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Phi_arg35 -> Region34 [style=dotted taillabel=0]; + Phi_arg35 -> Phi_arg8[taillabel=1]; + Phi_arg35 -> Add16[taillabel=2 constraint=false]; + Region39 -> If19:p0[taillabel=1 color=red]; + Region39 -> If28:p1[taillabel=2 color=red]; + Return40 -> Region34[taillabel=0 color=red]; + Return40 -> Phi_arg35[taillabel=1]; +} diff --git a/docs/chapter08/08-graph1.json b/docs/chapter08/08-graph1.json new file mode 100644 index 00000000..130a79bd --- /dev/null +++ b/docs/chapter08/08-graph1.json @@ -0,0 +1,39 @@ +{ + "ver": 1, + "comp": "chapter08/docs/08-graph1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 40, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 0}}, + {"id": 6, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 39, "role": "CTRL", "label": null}], "proj": null}, + {"id": 7, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 1}}, + {"id": 8, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 6, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "10", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 10, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 0}}, + {"id": 13, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 1}}, + {"id": 14, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 0}}, + {"id": 15, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 1}}, + {"id": 26, "label": "6", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 27, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 26, "role": "DATA", "label": null}], "proj": null}, + {"id": 28, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}], "proj": null}, + {"id": 34, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 7, "role": "CTRL", "label": null}, {"idx": 2, "def": 14, "role": "CTRL", "label": null}], "proj": null}, + {"id": 35, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 34, "role": "ASSOC", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 39, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "CTRL", "label": null}, {"idx": 2, "def": 20, "role": "CTRL", "label": null}], "proj": null}, + {"id": 40, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 34, "role": "CTRL", "label": null}, {"idx": 1, "def": 35, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 6, "par": 0, "nodes": [5, 6, 7, 8, 10, 11, 12, 13, 14, 18, 19, 20, 27, 28, 39]} + ] +} diff --git a/docs/chapter08/08-graph1.svg b/docs/chapter08/08-graph1.svg new file mode 100644 index 00000000..c398607a --- /dev/null +++ b/docs/chapter08/08-graph1.svg @@ -0,0 +1,174 @@ +<svg aria-label="Compiler graph" width="966" height="1390" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 966 1390" 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;"><g class="region" transform="translate(34,269)"><rect class="region-box" rx="8" width="667" height="810" fill="#f1f6fc"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M409,1289 C409,1313 483,1316 483,1340" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #40 · CTRL</title></path><path class="edge CTRL" id="e6i1" d="M148,216 L148,339" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[1] → #1 · CTRL</title></path><path class="edge CTRL" id="e6i2" d="M319,1044 L319,1049 Q319,1054 324,1054 L681,1054 Q689,1054 689,1046 L689,330 Q689,322 681,322 L186,322 Q178,322 178,330 L178,342" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[2] → #39 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M268,216 L268,221 Q268,226 273,226 L274,226 Q280,226 280,232 L280,339" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge DATA" id="e8i2" d="M578,200.33333333333331 L578,205.33333333333331 Q578,210.33333333333331 583,210.33333333333331 L658.1666666666666,210.33333333333331 Q662,210.33333333333331 662,214.16666666666666 L662,214.16666666666666 Q662,218 665.8333333333334,218 L671,218 Q679,218 679,226 L679,322 Q679,330 671,330 L326,330 Q320,330 320,336 L320,342" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #16 · DATA</title></path><path class="edge DATA" id="e10i1" d="M300,395 L300,400 Q300,405 305,405 L332,405 Q340,405 340,413 L340,443" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[1] → #8 · DATA</title></path><path class="edge DATA" id="e10i2" d="M426,216 L426,221 Q426,226 421,226 L378,226 Q370,226 370,234 L370,443" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[2] → #9 · DATA</title></path><path class="edge CTRL" id="e11i0" d="M148,395 L148,547" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#11[0] → #6 · CTRL</title></path><path class="edge DATA" id="e11i1" d="M340,499 L340,504 Q340,509 335,509 L236,509 Q228,509 228,517 L228,547" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[1] → #10 · DATA</title></path><path class="edge DATA" id="e16i1" d="M300,395 L300,400 Q300,405 295,405 L167,405 Q159,405 159,413 L159,501 Q159,509 151,509 L65,509 Q57,509 57,517 L57,1096 Q57,1104 49,1104 L32,1104 Q24,1104 24,1096 L24,92 Q24,84 32,84 L570,84 Q578,84 578,92 L578,147.33333333333331" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #8 · DATA</title></path><path class="edge DATA" id="e16i2" d="M608,74 L608,147.33333333333331" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[2] → #15 · DATA</title></path><path class="edge DATA" id="e18i1" d="M578,203.33333333333331 L578,238 Q578,246 570,246 L535,246 Q527,246 527,254 L527,561.6666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #16 · DATA</title></path><path class="edge DATA" id="e18i2" d="M730,216 L730,221 Q730,226 725,226 L616,226 Q608,226 608,234 L608,501 Q608,509 600,509 L565,509 Q557,509 557,517 L557,561.6666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #17 · DATA</title></path><path class="edge CTRL" id="e19i0" d="M128,647 L128,652 Q128,657 133,657 L331,657 Q339,657 339,665 L339,695" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#19[0] → #5 · CTRL</title></path><path class="edge DATA" id="e19i1" d="M527,617.6666666666666 L527,649 Q527,657 519,657 L427,657 Q419,657 419,665 L419,695" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[1] → #18 · DATA</title></path><path class="edge DATA" id="e27i1" d="M578,203.33333333333331 L578,238 Q578,246 586,246 L589,246 Q597,246 597,254 L597,709.6666666666667" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#27[1] → #16 · DATA</title></path><path class="edge DATA" id="e27i2" d="M882,216 L882,228 Q882,236 874,236 L635,236 Q627,236 627,244 L627,709.6666666666667" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#27[2] → #26 · DATA</title></path><path class="edge CTRL" id="e28i0" d="M439,795 L439,843" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#28[0] → #13 · CTRL</title></path><path class="edge DATA" id="e28i1" d="M597,765.6666666666667 L597,797 Q597,805 589,805 L527,805 Q519,805 519,813 L519,843" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#28[1] → #27 · DATA</title></path><path class="edge CTRL" id="e34i1" d="M248,647 L248,1086 Q248,1094 256,1094 L381,1094 Q389,1094 389,1102 L389,1132" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#34[1] → #7 · CTRL</title></path><path class="edge CTRL" id="e34i2" d="M419,943 L419,1132" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#34[2] → #14 · CTRL</title></path><path class="edge DATA" id="e35i1" d="M300,395 L300,400 Q300,405 295,405 L167,405 Q159,405 159,413 L159,501 Q159,509 151,509 L65,509 Q57,509 57,517 L57,1096 Q57,1104 65,1104 L513,1104 Q521,1104 521,1112 L521,1132" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#35[1] → #8 · DATA</title></path><path class="edge DATA" id="e35i2" d="M578,203.33333333333331 L578,238 Q578,246 586,246 L703,246 Q711,246 711,254 L711,1086 Q711,1094 703,1094 L569,1094 Q561,1094 561,1102 L561,1132" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#35[2] → #16 · DATA</title></path><path class="edge CTRL" id="e39i1" d="M319,795 L319,991" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#39[1] → #12 · CTRL</title></path><path class="edge CTRL" id="e39i2" d="M539,943 L539,948 Q539,953 534,953 L357,953 Q349,953 349,961 L349,991" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#39[2] → #20 · CTRL</title></path><path class="edge CTRL" id="e40i0" d="M389,1188 L389,1236" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#40[0] → #34 · CTRL</title></path><path class="edge DATA" id="e40i1" d="M541,1188 L541,1193 Q541,1198 536,1198 L437,1198 Q429,1198 429,1206 L429,1236" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#40[1] → #35 · 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(88,166)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(88,122)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(447,1340)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #40 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(208,166)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(68,597)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 True +Projection 0 of #11 +Type not computed + +[0] → #11 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(88,345)" style="opacity: 1;"><path class="box" d="M20,0H100Q120,0 120,20V24Q120,44 100,44H20Q0,44 0,24V20Q0,0 20,0Z" fill="#ffe0ab"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Loop</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #39 CTRL</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="n7" data-id="7" transform="translate(188,597)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #7/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 False +Projection 1 of #11 +Type not computed + +[0] → #11 CTRL</title></g><g class="node" id="n8" data-id="8" transform="translate(240,345)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>φ_arg</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 φ_arg +Type not computed + +[0] → #6 ASSOC +[1] → #4 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #6</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(366,166)" 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>10</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 10 +Type not computed + +</title></g><g class="node" id="n10" data-id="10" transform="translate(280,449)" 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"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 < +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #9 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="n11" data-id="11" transform="translate(68,553)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#11 If +Type not computed + +[0] → #6 CTRL +[1] → #10 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n12" data-id="12" transform="translate(259,745)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #12/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 True +Projection 0 of #19 +Type not computed + +[0] → #19 CTRL</title></g><g class="node" id="n13" data-id="13" transform="translate(379,745)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #13/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 False +Projection 1 of #19 +Type not computed + +[0] → #19 CTRL</title></g><g class="node" id="n14" data-id="14" transform="translate(359,893)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #14/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 True +Projection 0 of #28 +Type not computed + +[0] → #28 CTRL</title></g><g class="node" id="n15" data-id="15" transform="translate(548,24)" 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"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 1 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" transform="translate(518,153.33333333333331)" 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"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 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="n17" data-id="17" transform="translate(670,166)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 5 +Type not computed + +</title></g><g class="node" id="n18" data-id="18" transform="translate(467,567.6666666666666)" 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"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #17 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="n19" data-id="19" transform="translate(259,701)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#19 If +Type not computed + +[0] → #5 CTRL +[1] → #18 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n20" data-id="20" transform="translate(479,893)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #20/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 False +Projection 1 of #28 +Type not computed + +[0] → #28 CTRL</title></g><g class="node" id="n26" data-id="26" transform="translate(822,166)" 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"> #26</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#26 6 +Type not computed + +</title></g><g class="node" id="n27" data-id="27" transform="translate(537,715.6666666666667)" 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"> #27</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#27 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #26 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="n28" data-id="28" transform="translate(359,849)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #28</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#28 If +Type not computed + +[0] → #13 CTRL +[1] → #27 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n34" data-id="34" transform="translate(329,1138)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #34</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#34 Region +Type not computed + +[0] → — DATA +[1] → #7 CTRL +[2] → #14 CTRL</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="n35" data-id="35" transform="translate(481,1138)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>φ_arg</tspan><tspan class="node-id"> #35</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#35 φ_arg +Type not computed + +[0] → #34 ASSOC +[1] → #8 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #34</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n39" data-id="39" transform="translate(259,997)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #39</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#39 Region +Type not computed + +[0] → — DATA +[1] → #12 CTRL +[2] → #20 CTRL</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="n40" data-id="40" transform="translate(349,1242)" 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"> #40</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#40 Return +Type not computed + +[0] → #34 CTRL +[1] → #35 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="region-head" transform="translate(34,269)"><text class="label" x="26" y="17"><tspan>Loop</tspan><tspan class="node-id"> #6</tspan></text><title>Loop · 15 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #6"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g></g><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter08/08-graph2.gv b/docs/chapter08/08-graph2.gv new file mode 100644 index 00000000..2fa82523 --- /dev/null +++ b/docs/chapter08/08-graph2.gv @@ -0,0 +1,103 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Region38 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;} + { rank=same; Region38;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region38[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If19:p0[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Region38 -> Region34[taillabel=1 color=red]; + Region38 -> If28:p1[taillabel=2 color=red]; + Return39 -> If11:p1[taillabel=0 color=red]; + Return39 -> Phi_arg8[taillabel=1]; +} diff --git a/docs/chapter08/08-graph2.json b/docs/chapter08/08-graph2.json new file mode 100644 index 00000000..6f25aaad --- /dev/null +++ b/docs/chapter08/08-graph2.json @@ -0,0 +1,39 @@ +{ + "ver": 1, + "comp": "chapter08/docs/08-graph2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 39, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 0}}, + {"id": 6, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 38, "role": "CTRL", "label": null}], "proj": null}, + {"id": 7, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 1}}, + {"id": 8, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 6, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "10", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 10, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 0}}, + {"id": 13, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 1}}, + {"id": 14, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 0}}, + {"id": 15, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 28, "role": "CTRL", "label": null}], "proj": {"par": 28, "idx": 1}}, + {"id": 26, "label": "6", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 27, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 26, "role": "DATA", "label": null}], "proj": null}, + {"id": 28, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}], "proj": null}, + {"id": 34, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "CTRL", "label": null}, {"idx": 2, "def": 14, "role": "CTRL", "label": null}], "proj": null}, + {"id": 38, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 34, "role": "CTRL", "label": null}, {"idx": 2, "def": 20, "role": "CTRL", "label": null}], "proj": null}, + {"id": 39, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 6, "par": 0, "nodes": [5, 6, 7, 8, 10, 11, 16]}, + {"id": 19, "par": 6, "nodes": [12, 13, 14, 18, 19, 20, 27, 28, 34, 38]} + ] +} diff --git a/docs/chapter08/08-graph2.svg b/docs/chapter08/08-graph2.svg new file mode 100644 index 00000000..e3d62fb9 --- /dev/null +++ b/docs/chapter08/08-graph2.svg @@ -0,0 +1,169 @@ +<svg aria-label="Compiler graph" width="902" height="1452" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 902 1452" 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;"><g class="region" transform="translate(133,171)"><rect class="region-box" rx="8" width="691" height="1074" fill="#f1f6fc"/></g><g class="region" transform="translate(347,602)"><rect class="region-box" rx="8" width="422" height="606" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M356,1351 C356,1375 451,1378 451,1402" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #39 · CTRL</title></path><path class="edge CTRL" id="e6i1" d="M236,118 L236,241" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[1] → #1 · CTRL</title></path><path class="edge CTRL" id="e6i2" d="M580,1193 L580,1198 Q580,1203 585,1203 L804,1203 Q812,1203 812,1195 L812,232 Q812,224 804,224 L274,224 Q266,224 266,232 L266,244" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[2] → #38 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M356,118 L356,123 Q356,128 361,128 L362,128 Q368,128 368,134 L368,241" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge DATA" id="e8i2" d="M519,398 L519,403 Q519,408 524,408 L794,408 Q802,408 802,400 L802,240 Q802,232 794,232 L414,232 Q408,232 408,238 L408,244" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #16 · DATA</title></path><path class="edge DATA" id="e10i1" d="M388,297 L388,302 Q388,307 383,307 L324,307 Q316,307 316,315 L316,345" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[1] → #8 · DATA</title></path><path class="edge DATA" id="e10i2" d="M84,118 L84,123 Q84,128 89,128 L157,128 Q165,128 165,136 L165,309 Q165,317 173,317 L338,317 Q346,317 346,325 L346,345" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[2] → #9 · DATA</title></path><path class="edge CTRL" id="e11i0" d="M236,297 L236,449" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#11[0] → #6 · CTRL</title></path><path class="edge DATA" id="e11i1" d="M316,401 L316,449" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[1] → #10 · DATA</title></path><path class="edge DATA" id="e16i1" d="M388,297 L388,302 Q388,307 393,307 L511,307 Q519,307 519,315 L519,345" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #8 · DATA</title></path><path class="edge DATA" id="e16i2" d="M514,118 L514,123 Q514,128 519,128 L541,128 Q549,128 549,136 L549,345" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[2] → #15 · DATA</title></path><path class="edge DATA" id="e18i1" d="M519,401 L519,636" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #16 · DATA</title></path><path class="edge DATA" id="e18i2" d="M666,118 L666,123 Q666,128 661,128 L607,128 Q599,128 599,136 L599,413 Q599,421 591,421 L557,421 Q549,421 549,429 L549,636" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #17 · DATA</title></path><path class="edge CTRL" id="e19i0" d="M216,549 L216,554 Q216,559 221,559 L431,559 Q439,559 439,567 L439,740" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#19[0] → #5 · CTRL</title></path><path class="edge DATA" id="e19i1" d="M519,692 L519,740" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[1] → #18 · DATA</title></path><path class="edge DATA" id="e27i1" d="M519,401 L519,406 Q519,411 524,411 L689,411 Q697,411 697,419 L697,754.6666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#27[1] → #16 · DATA</title></path><path class="edge DATA" id="e27i2" d="M818,118 L818,123 Q818,128 813,128 L735,128 Q727,128 727,136 L727,754.6666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#27[2] → #26 · DATA</title></path><path class="edge CTRL" id="e28i0" d="M539,840 L539,845 Q539,850 534,850 L518,850 Q510,850 510,858 L510,888" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#28[0] → #13 · CTRL</title></path><path class="edge DATA" id="e28i1" d="M697,810.6666666666666 L697,842 Q697,850 689,850 L598,850 Q590,850 590,858 L590,888" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#28[1] → #27 · DATA</title></path><path class="edge CTRL" id="e34i1" d="M419,840 L419,990 Q419,998 427,998 L452,998 Q460,998 460,1006 L460,1036" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#34[1] → #12 · CTRL</title></path><path class="edge CTRL" id="e34i2" d="M490,988 L490,1036" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#34[2] → #14 · CTRL</title></path><path class="edge CTRL" id="e38i1" d="M460,1092 L460,1097 Q460,1102 465,1102 L572,1102 Q580,1102 580,1110 L580,1140" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#38[1] → #34 · CTRL</title></path><path class="edge CTRL" id="e38i2" d="M610,988 L610,1140" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#38[2] → #20 · CTRL</title></path><path class="edge CTRL" id="e39i0" d="M336,549 L336,1298" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#39[0] → #7 · CTRL</title></path><path class="edge DATA" id="e39i1" d="M388,297 L388,302 Q388,307 393,307 L771,307 Q779,307 779,315 L779,1252 Q779,1260 771,1260 L384,1260 Q376,1260 376,1268 L376,1298" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#39[1] → #8 · 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(176,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(415,1402)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #39 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(296,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(156,499)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 True +Projection 0 of #11 +Type not computed + +[0] → #11 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(176,247)" style="opacity: 1;"><path class="box" d="M20,0H100Q120,0 120,20V24Q120,44 100,44H20Q0,44 0,24V20Q0,0 20,0Z" fill="#ffe0ab"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Loop</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #38 CTRL</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="n7" data-id="7" transform="translate(276,499)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #7/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 False +Projection 1 of #11 +Type not computed + +[0] → #11 CTRL</title></g><g class="node" id="n8" data-id="8" transform="translate(328,247)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>φ_arg</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 φ_arg +Type not computed + +[0] → #6 ASSOC +[1] → #4 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #6</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(24,68)" 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>10</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 10 +Type not computed + +</title></g><g class="node" id="n10" data-id="10" transform="translate(256,351)" 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"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 < +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #9 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="n11" data-id="11" transform="translate(156,455)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#11 If +Type not computed + +[0] → #6 CTRL +[1] → #10 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n12" data-id="12" transform="translate(359,790)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #12/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 True +Projection 0 of #19 +Type not computed + +[0] → #19 CTRL</title></g><g class="node" id="n13" data-id="13" transform="translate(479,790)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #13/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 False +Projection 1 of #19 +Type not computed + +[0] → #19 CTRL</title></g><g class="node" id="n14" data-id="14" transform="translate(430,938)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #14/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 True +Projection 0 of #28 +Type not computed + +[0] → #28 CTRL</title></g><g class="node" id="n15" data-id="15" transform="translate(454,68)" 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"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 1 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" transform="translate(459,351)" 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"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 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="n17" data-id="17" transform="translate(606,68)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 5 +Type not computed + +</title></g><g class="node" id="n18" data-id="18" transform="translate(459,642)" 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"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #17 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="n19" data-id="19" transform="translate(359,746)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#19 If +Type not computed + +[0] → #5 CTRL +[1] → #18 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n20" data-id="20" transform="translate(550,938)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #20/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 False +Projection 1 of #28 +Type not computed + +[0] → #28 CTRL</title></g><g class="node" id="n26" data-id="26" transform="translate(758,68)" 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"> #26</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#26 6 +Type not computed + +</title></g><g class="node" id="n27" data-id="27" transform="translate(637,760.6666666666666)" 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"> #27</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#27 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #26 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="n28" data-id="28" transform="translate(430,894)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #28</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#28 If +Type not computed + +[0] → #13 CTRL +[1] → #27 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n34" data-id="34" transform="translate(400,1042)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #34</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#34 Region +Type not computed + +[0] → — DATA +[1] → #12 CTRL +[2] → #14 CTRL</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="n38" data-id="38" transform="translate(520,1146)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #38</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#38 Region +Type not computed + +[0] → — DATA +[1] → #34 CTRL +[2] → #20 CTRL</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="n39" data-id="39" transform="translate(296,1304)" 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"> #39</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#39 Return +Type not computed + +[0] → #7 CTRL +[1] → #8 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="region-head" transform="translate(133,171)"><text class="label" x="26" y="17"><tspan>Loop</tspan><tspan class="node-id"> #6</tspan></text><title>Loop · 17 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #6"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g><g class="region-head" transform="translate(347,602)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #19</tspan></text><title>If · 10 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #19"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g></g><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter08/08-graph3.gv b/docs/chapter08/08-graph3.gv new file mode 100644 index 00000000..72ac10a8 --- /dev/null +++ b/docs/chapter08/08-graph3.gv @@ -0,0 +1,111 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">Start</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">$ctrl</TD><TD PORT="p1">arg</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region25 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg26 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_28 [ label="6" ]; + EQ29 [ label="==" ]; + If30 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Region36 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg37 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region25;Phi_arg26;} + { rank=same; Region36;Phi_arg37;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> If30:p1[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + Region25 -> If11:p1[taillabel=1 color=red]; + Region25 -> If19:p0[taillabel=2 color=red]; + Phi_arg26 -> Region25 [style=dotted taillabel=0]; + Phi_arg26 -> Phi_arg8[taillabel=1]; + Phi_arg26 -> Add16[taillabel=2 constraint=false]; + EQ29 -> Add16[taillabel=1]; + EQ29 -> Con_28[taillabel=2]; + If30 -> If19:p1[taillabel=0 color=red]; + If30 -> EQ29[taillabel=1]; + Region36 -> Region25[taillabel=1 color=red]; + Region36 -> If30:p0[taillabel=2 color=red]; + Phi_arg37 -> Region36 [style=dotted taillabel=0]; + Phi_arg37 -> Phi_arg26[taillabel=1]; + Phi_arg37 -> Add16[taillabel=2 constraint=false]; + Return39 -> Region36[taillabel=0 color=red]; + Return39 -> Phi_arg37[taillabel=1]; +}
\ No newline at end of file diff --git a/docs/chapter08/08-graph3.json b/docs/chapter08/08-graph3.json new file mode 100644 index 00000000..a795c51d --- /dev/null +++ b/docs/chapter08/08-graph3.json @@ -0,0 +1,40 @@ +{ + "ver": 1, + "comp": "chapter08/docs/08-graph3.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 39, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 0}}, + {"id": 6, "label": "Loop", "type": null, "kind": "LOOP", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 1, "role": "CTRL", "label": null}, {"idx": 2, "def": 20, "role": "CTRL", "label": null}], "proj": null}, + {"id": 7, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}], "proj": {"par": 11, "idx": 1}}, + {"id": 8, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 6, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "10", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 10, "label": "<", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 0}}, + {"id": 13, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 19, "role": "CTRL", "label": null}], "proj": {"par": 19, "idx": 1}}, + {"id": 14, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 30, "role": "CTRL", "label": null}], "proj": {"par": 30, "idx": 0}}, + {"id": 15, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 30, "role": "CTRL", "label": null}], "proj": {"par": 30, "idx": 1}}, + {"id": 25, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 7, "role": "CTRL", "label": null}, {"idx": 2, "def": 12, "role": "CTRL", "label": null}], "proj": null}, + {"id": 26, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 25, "role": "ASSOC", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 28, "label": "6", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 29, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 28, "role": "DATA", "label": null}], "proj": null}, + {"id": 30, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}, {"idx": 1, "def": 29, "role": "DATA", "label": null}], "proj": null}, + {"id": 36, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 25, "role": "CTRL", "label": null}, {"idx": 2, "def": 14, "role": "CTRL", "label": null}], "proj": null}, + {"id": 37, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 36, "role": "ASSOC", "label": null}, {"idx": 1, "def": 26, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 39, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 36, "role": "CTRL", "label": null}, {"idx": 1, "def": 37, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 6, "par": 0, "nodes": [5, 6, 7, 8, 10, 11, 12, 13, 14, 18, 19, 20, 29, 30]} + ] +} diff --git a/docs/chapter08/08-graph3.svg b/docs/chapter08/08-graph3.svg new file mode 100644 index 00000000..62517032 --- /dev/null +++ b/docs/chapter08/08-graph3.svg @@ -0,0 +1,179 @@ +<svg aria-label="Compiler graph" width="955" height="1390" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 955 1390" 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;"><g class="region" transform="translate(34,269)"><rect class="region-box" rx="8" width="667" height="706" fill="#f1f6fc"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M449,1289 C449,1313 477.5,1316 477.5,1340" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #39 · CTRL</title></path><path class="edge CTRL" id="e6i1" d="M137,216 L137,339" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[1] → #1 · CTRL</title></path><path class="edge CTRL" id="e6i2" d="M539,940 L539,945 Q539,950 544,950 L681,950 Q689,950 689,942 L689,330 Q689,322 681,322 L175,322 Q167,322 167,330 L167,342" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[2] → #20 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M257,216 L257,221 Q257,226 262,226 L263,226 Q269,226 269,232 L269,339" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge DATA" id="e8i2" d="M567,200.33333333333331 L567,205.33333333333331 Q567,210.33333333333331 572,210.33333333333331 L647.1666666666666,210.33333333333331 Q651,210.33333333333331 651,214.16666666666666 L651,214.16666666666666 Q651,218 654.8333333333334,218 L671,218 Q679,218 679,226 L679,322 Q679,330 671,330 L315,330 Q309,330 309,336 L309,342" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #16 · DATA</title></path><path class="edge DATA" id="e10i1" d="M289,395 L289,443" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[1] → #8 · DATA</title></path><path class="edge DATA" id="e10i2" d="M415,216 L415,221 Q415,226 410,226 L367,226 Q359,226 359,234 L359,397 Q359,405 351,405 L327,405 Q319,405 319,413 L319,443" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[2] → #9 · DATA</title></path><path class="edge CTRL" id="e11i0" d="M137,395 L137,547" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#11[0] → #6 · CTRL</title></path><path class="edge DATA" id="e11i1" d="M289,499 L289,504 Q289,509 284,509 L225,509 Q217,509 217,517 L217,547" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[1] → #10 · DATA</title></path><path class="edge DATA" id="e16i1" d="M289,395 L289,400 Q289,405 284,405 L54,405 Q46,405 46,413 L46,992 Q46,1000 38,1000 L32,1000 Q24,1000 24,992 L24,92 Q24,84 32,84 L559,84 Q567,84 567,92 L567,147.33333333333331" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #8 · DATA</title></path><path class="edge DATA" id="e16i2" d="M597,74 L597,147.33333333333331" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[2] → #15 · DATA</title></path><path class="edge DATA" id="e18i1" d="M567,203.33333333333331 L567,238 Q567,246 559,246 L427,246 Q419,246 419,254 L419,561.6666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #16 · DATA</title></path><path class="edge DATA" id="e18i2" d="M719,216 L719,221 Q719,226 714,226 L457,226 Q449,226 449,234 L449,561.6666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #17 · DATA</title></path><path class="edge CTRL" id="e19i0" d="M117,647 L117,659 Q117,667 125,667 L331,667 Q339,667 339,675 L339,695" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#19[0] → #5 · CTRL</title></path><path class="edge DATA" id="e19i1" d="M419,617.6666666666666 L419,695" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[1] → #18 · DATA</title></path><path class="edge CTRL" id="e25i1" d="M237,647 L237,1028" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#25[1] → #7 · CTRL</title></path><path class="edge CTRL" id="e25i2" d="M319,795 L319,982 Q319,990 311,990 L275,990 Q267,990 267,998 L267,1028" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#25[2] → #12 · CTRL</title></path><path class="edge DATA" id="e26i1" d="M289,395 L289,400 Q289,405 284,405 L54,405 Q46,405 46,413 L46,992 Q46,1000 54,1000 L361,1000 Q369,1000 369,1008 L369,1028" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#26[1] → #8 · DATA</title></path><path class="edge DATA" id="e26i2" d="M567,203.33333333333331 L567,238 Q567,246 575,246 L703,246 Q711,246 711,254 L711,982 Q711,990 703,990 L417,990 Q409,990 409,998 L409,1028" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#26[2] → #16 · DATA</title></path><path class="edge DATA" id="e29i1" d="M567,203.33333333333331 L567,238 Q567,246 575,246 L589,246 Q597,246 597,254 L597,709.6666666666667" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#29[1] → #16 · DATA</title></path><path class="edge DATA" id="e29i2" d="M871,216 L871,228 Q871,236 863,236 L635,236 Q627,236 627,244 L627,709.6666666666667" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#29[2] → #28 · DATA</title></path><path class="edge CTRL" id="e30i0" d="M439,795 L439,843" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#30[0] → #13 · CTRL</title></path><path class="edge DATA" id="e30i1" d="M597,765.6666666666667 L597,797 Q597,805 589,805 L527,805 Q519,805 519,813 L519,843" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#30[1] → #29 · DATA</title></path><path class="edge CTRL" id="e36i1" d="M237,1084 L237,1096 Q237,1104 245,1104 L421,1104 Q429,1104 429,1112 L429,1132" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#36[1] → #25 · CTRL</title></path><path class="edge CTRL" id="e36i2" d="M419,943 L419,992 Q419,1000 427,1000 L451,1000 Q459,1000 459,1008 L459,1132" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#36[2] → #14 · CTRL</title></path><path class="edge DATA" id="e37i1" d="M389,1084 L389,1089 Q389,1094 394,1094 L553,1094 Q561,1094 561,1102 L561,1132" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#37[1] → #26 · DATA</title></path><path class="edge DATA" id="e37i2" d="M567,203.33333333333331 L567,238 Q567,246 575,246 L703,246 Q711,246 711,254 L711,982 Q711,990 703,990 L609,990 Q601,990 601,998 L601,1132" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#37[2] → #16 · DATA</title></path><path class="edge CTRL" id="e39i0" d="M429,1188 L429,1236" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#39[0] → #36 · CTRL</title></path><path class="edge DATA" id="e39i1" d="M581,1188 L581,1193 Q581,1198 576,1198 L477,1198 Q469,1198 469,1206 L469,1236" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#39[1] → #37 · 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(77,166)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(77,122)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(441.5,1340)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #39 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(197,166)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(57,597)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 True +Projection 0 of #11 +Type not computed + +[0] → #11 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(77,345)" style="opacity: 1;"><path class="box" d="M20,0H100Q120,0 120,20V24Q120,44 100,44H20Q0,44 0,24V20Q0,0 20,0Z" fill="#ffe0ab"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Loop</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 Loop +Type not computed + +[0] → — DATA +[1] → #1 CTRL +[2] → #20 CTRL</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="n7" data-id="7" transform="translate(177,597)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #7/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 False +Projection 1 of #11 +Type not computed + +[0] → #11 CTRL</title></g><g class="node" id="n8" data-id="8" transform="translate(229,345)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>φ_arg</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 φ_arg +Type not computed + +[0] → #6 ASSOC +[1] → #4 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #6</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(355,166)" 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>10</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 10 +Type not computed + +</title></g><g class="node" id="n10" data-id="10" transform="translate(229,449)" 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"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 < +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #9 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="n11" data-id="11" transform="translate(57,553)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#11 If +Type not computed + +[0] → #6 CTRL +[1] → #10 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n12" data-id="12" transform="translate(259,745)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #12/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 True +Projection 0 of #19 +Type not computed + +[0] → #19 CTRL</title></g><g class="node" id="n13" data-id="13" transform="translate(379,745)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #13/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 False +Projection 1 of #19 +Type not computed + +[0] → #19 CTRL</title></g><g class="node" id="n14" data-id="14" transform="translate(359,893)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #14/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 True +Projection 0 of #30 +Type not computed + +[0] → #30 CTRL</title></g><g class="node" id="n15" data-id="15" transform="translate(537,24)" 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"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 1 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" transform="translate(507,153.33333333333331)" 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"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #15 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="n17" data-id="17" transform="translate(659,166)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 5 +Type not computed + +</title></g><g class="node" id="n18" data-id="18" transform="translate(359,567.6666666666666)" 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"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #17 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="n19" data-id="19" transform="translate(259,701)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#19 If +Type not computed + +[0] → #5 CTRL +[1] → #18 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n20" data-id="20" transform="translate(479,893)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #20/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 False +Projection 1 of #30 +Type not computed + +[0] → #30 CTRL</title></g><g class="node" id="n25" data-id="25" transform="translate(177,1034)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #25</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#25 Region +Type not computed + +[0] → — DATA +[1] → #7 CTRL +[2] → #12 CTRL</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="n26" data-id="26" transform="translate(329,1034)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>φ_arg</tspan><tspan class="node-id"> #26</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#26 φ_arg +Type not computed + +[0] → #25 ASSOC +[1] → #8 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #25</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n28" data-id="28" transform="translate(811,166)" 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"> #28</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#28 6 +Type not computed + +</title></g><g class="node" id="n29" data-id="29" transform="translate(537,715.6666666666667)" 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"> #29</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#29 == +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #28 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="n30" data-id="30" transform="translate(359,849)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #30</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#30 If +Type not computed + +[0] → #13 CTRL +[1] → #29 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n36" data-id="36" transform="translate(369,1138)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #36</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#36 Region +Type not computed + +[0] → — DATA +[1] → #25 CTRL +[2] → #14 CTRL</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="n37" data-id="37" transform="translate(521,1138)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>φ_arg</tspan><tspan class="node-id"> #37</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#37 φ_arg +Type not computed + +[0] → #36 ASSOC +[1] → #26 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #36</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n39" data-id="39" transform="translate(389,1242)" 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"> #39</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#39 Return +Type not computed + +[0] → #36 CTRL +[1] → #37 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="region-head" transform="translate(34,269)"><text class="label" x="26" y="17"><tspan>Loop</tspan><tspan class="node-id"> #6</tspan></text><title>Loop · 14 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #6"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g></g><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter08/Makefile b/docs/chapter08/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter08/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter08/README.ja.md b/docs/chapter08/README.ja.md new file mode 100644 index 00000000..cbe61a3b --- /dev/null +++ b/docs/chapter08/README.ja.md @@ -0,0 +1,264 @@ +# 第8章: 遅延生成する Phi、Break、Continue、評価器 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第7章](../chapter07/README.ja.md) | +[次の章: 第9章](../chapter09/README.ja.md) + +# 目次 + +1. [Phi の遅延生成](#phi-の遅延生成) +2. [`continue` 文](#continue-文) +3. [`break` 文](#break-文) +4. [パーサーでの考慮事項](#パーサーでの考慮事項) +5. [例](#例) + - [例1](#例1) + - [例2](#例2) + - [例3](#例3) +6. [Sea of Nodes グラフ評価器](#sea-of-nodes-グラフ評価器) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter08) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter07...linear-chapter08) することもできます。 + +この章では次のことを行います。 + +* ループ内の `Phi` の作成を、先行生成から遅延生成へ移します。 +* `break` 文と `continue` 文のサポートを追加します。 +* Sea of Nodes グラフ評価器を実装します。 + +この章の [完全な言語文法](08-grammar.ja.md) はこちらです。 + +## Phi の遅延生成 + +[第7章](../chapter07/README.ja.md) では、ループ先頭にすべての変数の `PhiNode` を先行して作成しました。この方法では不要な Phi も作りますが、冗長な Phi は後で削除されます。 + +この章では、`PhiNode` の遅延生成をサポートします。 + +`PhiNode` を遅延生成する際の主な難しさは、Phi を作るとき、先行生成していた場合に作られるはずだった最も内側のループ先頭のスコープで作らなければならないことです。`if` 文と `while` 文ではスコープを複製するため、単に現在のスコープに Phi を作るわけにはいきません。 + +`PhiNode` を遅延生成する最も簡単な方法は、名前の検索にその処理を組み込むことだとわかります。しかし、名前を参照するとき、Phi を作る必要があるとどう判断するのでしょうか。特定の名前の対応付けを、検索時に `PhiNode` に変換すべきだと示す仕組みが必要です。 + +次のように実現します。 + +* `ScopeNode.dup()` で、ループ先頭のために Scope を複製する場合、名前の定義を元のノードに設定する代わりに、Scope 自身に設定します。これが番兵（sentinel）として機能します。 + + ```java + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); + ``` + +* その後、検索で名前にアクセスするとき、定義が Scope ノードを指していることを検出し、その時点で `PhiNode` を作ります。対応する実装は `ScopeNode.update()` にあります。 + + ```java + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have inserted a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + ``` + +* スコープをマージするときは、定義に直接アクセスする代わりに名前で検索し、正しい内側のスコープ階層で遅延生成する `PhiNode` が作られるようにします。 + + ```java + if( in(i) != that.in(i) ) // No need for redundant Phis + // If we are in lazy phi mode we need to do a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + ``` + +* 最後に `ScopeNode.endLoop()` で残った番兵を片付け、ループ先頭からの入力に置き換えます。 + + ```java + for( int i=1; i<nIns(); i++ ) { + if( back.in(i) != this ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.setDef(2,back.in(i)); + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) + phi.subsume(in); + } + if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also + exit.setDef(i,in(i)); + } + ``` + +## `continue` 文 + +第7章では、ループ末尾から先頭に戻るバックエッジは1本だけでした。 + +`continue` 文の追加により、ループ先頭に戻るバックエッジが複数になることがあります。 + +このバックエッジの実装には、いくつかの方法があります。 + +1. 従来の方法では、各 `continue` のバックエッジをループ先頭にマージします。Phi はエッジの数だけ入力を必要とします。欠点は、Loop が単純な入れ子構造ではなくなることです。これにより、より多くのループ不変式を外に持ち上げるためにループを「部分的に巻き戻す」など、多くの種類のピープホールによるループ最適化が難しくなります。 +2. 別の方法は、すべての `continue` を1つのマージ地点（`Region`）に集め、continue の `Region` からループ先頭へ流れるバックエッジを1本作ることです。 +3. 3つ目の方法は、continue の `Region` を1つ作る代わりに、そのスタックを作ることです。この方法では、Phi を現在と同じ2入力の単純な形に保てる利点があります。ほかの方法では Phi に3つ以上の入力が必要です。一方、`continue` 文と同じ数の continue `Region` と、それに対応する積み重なった Phi ができることになります。 + +この章では、基本的な `while` ループのアーキテクチャに最も簡単に実装できる方法3を採用します。[^1] + +実装ではスコープを慎重に扱う必要があります。`continue` 用の `PhiNode/RegionNode` を必要な場合だけ生成したいからです。 + +[基本的なループのアーキテクチャ](../chapter07/README.ja.md) では、ループのバックエッジに到達した時点ですべての入れ子のブロックやスコープを抜けています。現在のスコープと制御を Loop のスコープと制御につなぎ、必要に応じて `PhiNode` を作れば十分です。 + +しかし、`continue` は入れ子のスコープ（入れ子の `if` 文など）の中にも現れます。continue の `Region` を遅延生成したいので、最初に `continue` に遭遇したら、先頭スコープを複製し、現在のスコープをそこへマージして、continue の Scope と `Region` を生成する必要があります。その後、別の `continue` に遭遇したら、新しい `Region` を作り、それまでの continue Scope と現在の Scope をマージします。 + +実装は、上記の方法の変形です。 + +* 最初の `continue` によって現在のスコープを複製します。先頭スコープより深い入れ子のレキシカルスコープを切り詰め、先頭スコープでは見えなかった名前の束縛を取り除きます。これは本質的に、入れ子のスコープを「抜ける」ことを保証しています。 + + continue スコープの初期値を null にします。 + + ```java + // No continues yet + _continueScope = null; + ``` + + continue を解析するとき、最初は `_continueScope` が null です。 + + ```java + private Node parseContinue() { return (_continueScope = require(jumpTo( _continueScope ),";")); } + + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + ``` + +* continue スコープは、後続の `continue` 文の基準となるスコープになり、こうして continue スコープと Region のスタックを形成します。 +* ループが終わった後、ループ内で continue スコープを作っていたなら、現在のスコープを continue スコープへマージし、その continue スコープを有効なスコープにする必要があります。 + + ```java + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + ``` + +## `break` 文 + +`break` の実装は `continue` より簡単です。ループ本体の解析前に出口スコープを作っており、これが初期の `break` スコープになります。`break` に遭遇したら、入れ子のレキシカルスコープを切り詰めた後、現在のスコープを現在の break スコープにマージします。その結果の新しいスコープが、有効な break スコープになります。 + +## パーサーでの考慮事項 + +`continue` や `break` の対象は、それを直接囲む `while` ループです。そのため、`continue` と `break` のスコープのスタックを管理します。`while` ループの解析前にそれまでの `continue` や `break` のスコープを保存し、解析後に復元することで実現します。 + +## 例 + +### 例1 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; +``` + + + +### 例2 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; +``` + + + +### 例3 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; +``` + + + +## Sea of Nodes グラフ評価器 + +評価器は、プログラムの開始点から制御フローを前向きにたどり、Return ノードに到達するか、最大ループ回数を超えるまで、与えられたグラフを直接評価します。 + +評価器は呼び出されると、最初にグラフを走査して Start ノードを見つけ、準備を行います。プログラムが特別なパラメーター `arg` を使っている場合、渡されたパラメーター値を、そのパラメーターを表すノードに束縛します。 + +この簡単な準備が済むと、Start ノードからの制御の射影をたどり、プログラムの「実行」を始められます。 + +この時点で制御フローはプログラムの最初の Region にありますが、ほかの Region とまったく同じように扱います。各 Region で行うべき処理は2つあります。まずすべての phi を具体的な値に解決し、次に制御フローの次の行き先を決めます。 + +もっと処理が必要に思えるかもしれません。しかし phi ノードを解決すれば、その Region の制御フロー経路に固有のロジックはすべて解決されます。それ以外の処理は、後で必要に応じて解決されます。プログラムの実行には、これで十分です！ + +Region の後の制御フローの行き先は簡単に見つけられます。Region を使う制御ノードは1つだけだからです。そのため、Region の利用側の中からそのノードを探します。 + +そのノードを見つけたら、到達した制御フローノードの種類によって動作を変えます。可能性は `RegionNode`、`IfNode`、`ReturnNode` の3つだけです。別の `RegionNode` なら、同じ処理を繰り返します。`ReturnNode` なら、戻り値の式を解決してプログラムの値を返せます。最後に `IfNode` の場合、まず判定式を解決し、true（射影0）または false（射影1）の分岐を選択します。`IfNode` のどちらの射影を選んでも、その射影を通って、それを使う制御ノード（`RegionNode`）に進みます。 + +上ではノードを「解決する」と述べましたが、それは何を意味するのでしょうか。ノードは、値を持つ（たとえば定数）か、すでに解決されて値がキャッシュされているか、あるいは自身が使うノードに対して演算を行います。最後の場合、その入力ノードを解決する必要があります。入力が解決されたら、それらに対してノードの演算を行えます。たとえば `AddNode` の値は、2つの入力の和です。値を解決したら、その値を返します。 + +これで、ループのない単純なプログラムを評価できます。 + +ループもほぼこのままで動作し、少しだけ追加の処理が必要です。制御が `LoopNode` を通るたびに、評価器はループの反復回数を使い切っていないか確認します。使い切っていたら、タイムアウトを示す RuntimeException を投げます。 + +最後に、ループ Region の `PhiNode` の値を計算するときは、どのキャッシュ値も更新する前に、すべての新しい値を計算するよう注意が必要です。ループの反復では、すべての `PhiNode` の値が同じ時点の値になるようにしなければならないからです。新しい値をすべて計算し終えたら、それらのキャッシュを一度に更新できます。これを説明するため、次のコードを考えます。 + +```java +int t = 0; +while(arg < 10) { + t = arg; + arg = arg + 1; +} +return t; +``` + +このコードでは、グラフはループ内の2つの文をどちらの順序でも評価できるため、`t` に以前の `arg` の値を設定する前に、`arg` の新しい値をキャッシュしないようにする必要があります。 + +この評価方法は、命令選択、レジスタ割り当て、コード生成を気にせずプログラムを実行できるため、テストに便利です。通常のピープホール最適化で生成したグラフを実行します。後の章では、異なるワークリストの順序で最適化したグラフを評価器で比較し、結果の不一致を検出できます。この章のファザーは、生成したプログラムについて、コンパイラと評価器の失敗をチェックします。 + +``` java +arg=arg+arg; +arg=arg+arg; +... +arg=arg+arg; +return arg; +``` + +一方、このエンジンは特に高速になるようには設計していません！ すべての式をキャッシュするわけではないため、直前の例のように実行時間が指数的になるプログラムを作ることができます。 + +[^1]: 方法2も試しました。この別の解法を見たい読者のため、その実装を持つ別のブランチを用意しています。 diff --git a/docs/chapter08/README.md b/docs/chapter08/README.md new file mode 100644 index 00000000..d4f8cab6 --- /dev/null +++ b/docs/chapter08/README.md @@ -0,0 +1,327 @@ +# Chapter 8: Lazy Phis, Break, Continue, and Evaluator + +English | [日本語](README.ja.md) + +[Previous: Chapter 7](../chapter07/README.md) | +[Next: Chapter 9](../chapter09/README.md) + +# Table of Contents + +1. [Lazy Phi Creation](#lazy-phi-creation) +2. [Continue statement](#continue-statement) +3. [Break statement](#break-statement) +4. [Parser Considerations](#parser-considerations) +5. [Examples](#examples) + - [Example 1](#example-1) + - [Example 2](#example-2) + - [Example 3](#example-3) + +6. [Sea of Nodes Graph Evaluator](#sea-of-nodes-graph-evaluator) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter08) 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-chapter07...linear-chapter08) it to the previous chapter. + + +In this chapter: + +* We move from eager to lazy `Phi` creation in loops. +* We add support for `break` and `continue` statements. +* We implement a Sea of Nodes Graph Evaluator. + +Here is the [complete language grammar](08-grammar.md) for this chapter. + + +## Lazy Phi Creation + +In [chapter 7](../chapter07/README.md), we created `PhiNode`s for all variables +in the loop head eagerly. This approach creates some unnecessary Phis but the +redundant Phis get cleaned up later. + +In this chapter we add support for creating the `PhiNode`s lazily. + +The main complication with creating `PhiNode`s lazily is that when we create a +Phi, it must be created in the innermost loop head scope where it would have +been created had we done it eagerly. Since scopes get duped in `if` and +`while` statements, we cannot just create Phis in the current scope. + +It turns out that the easiest way to create the `PhiNode`s lazily is to hook +them up to name lookup. But how do we know that a Phi must be created when we +access a name? We need a way to flag that a particular name mapping must be +converted to a `PhiNode` on lookup. + +We do this as follows: + +* In `ScopeNode.dup()`, if the Scope is being duplicated for a loop head, then + instead of setting the name's definition to the original node, we set it to + the Scope itself. This acts like a sentinel. + + ```java + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); + ``` + +* Subsequently, when a lookup accesses a name, we notice that the def is set to + the Scope node, and we create a `PhiNode` at this point. The relevant + implementation is in `ScopeNode.update()`. + + ```java + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have inserted a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + ``` + +* When we merge scopes, we ensure lazy `PhiNode` creation at the correct inner + scope level by invoking lookup by name instead of directly accessing the + defs. + + ```java + if( in(i) != that.in(i) ) // No need for redundant Phis + // If we are in lazy phi mode we need to do a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + ``` + +* Finally, in `ScopeNode.endLoop()` we clean up any leftover sentinels, replacing the sentinel with the input from loop head. + + ```java + for( int i=1; i<nIns(); i++ ) { + if( back.in(i) != this ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.setDef(2,back.in(i)); + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) + phi.subsume(in); + } + if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also + exit.setDef(i,in(i)); + } + ``` + +## `continue` Statement + +In Chapter 7, we had a single backedge from the loop's end flowing back to the +loop head. + +With the addition of a `continue` statement, we can have multiple backedges +flowing back to the loop head. + +We have several ways of implementing these backedges. + +1. The traditional way would be to let each backedge from `continue` merge into + the loop head. Phis would require as many inputs as there are edges. The + downside is now our Loops are not simply nested. This makes it difficult to + do many kinds of peephole-based loop optimizations, such as "partially + rolling" the loop to allow more loop invariants to get hoisted. +2. An alternative is to collect all `continue`s at a single merge point (`Region`) + and then create a single backedge flowing from the continue `Region` to the + loop head. +3. A third approach is to create a stack of continue `Region`s rather than a + single continue `Region`. This has the benefit of keeping our Phis simple + with just two inputs as they are now, whereas the other approaches require + Phis with more than 2 inputs. On the other hand we end up with as many + continue `Region`s as there are `continue` statements, and corresponding + Phis that are stacked. + +In this chapter we adopt option 3 as it is the simplest implementation on top +of our basic `while` loop architecture.[^1] + +The implementation requires some careful handling of scopes. This is because +we would like to only generate `PhiNode/RegionNode`s for `continues` if necessary. + +In our [basic loop architecture](../chapter07/README.md), by the time we get to +the loop backedge, we have already exited all nested blocks/scopes, we just +need to stitch together the current scope+ctrl into the Loop scope+ctrl and +create `PhiNode`s as needed. + +A `continue` however, can occur inside nested scopes (such as nested `if` +statement). Since we want to lazily create the continue `Region`, the first +time we see a `continue`, we need to dupe the head scope and merge the current +scope into it to generate a continue Scope and `Region`. Subsequently, when we +see another `continue`, we need to construct a new `Region` and merge the +previous continue Scope with the current Scope. + +The implementation is a variation of the above. + +* The first `continue` triggers a dupe of the current scope; we prune any + nested lexical scopes deeper than the head scope, removing any name bindings + that were not visible in the head scope. This is essentially ensuring that + we "exit" any nested scopes. + + We set the continue scope initially to null. + + ```java + // No continues yet + _continueScope = null; + ``` + When we parse continue, the first time `_continueScope` is null. + + ```java + private Node parseContinue() { return (_continueScope = require(jumpTo( _continueScope ),";")); } + + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + ``` + +* The continue scope becomes the base scope for the subsequent `continue` + statement, thus forming a stack of continue scopes/regions. +* After the loop is done, if we find that a continue scope was created within + the loop, we must merge the current scope into the continue scope, and make + the continue scope the active scope. + + ```java + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + ``` + +## `break` Statement + +Implementing `break` is simpler than `continue`, because the exit scope is +created before we parse the loop body, and this becomes the initial `break` +scope. When we see `break`, we merge the current scope, after pruning any +nested lexical scopes, to the current break scope, and the resulting new scope +becomes the active break scope. + +## Parser Considerations + +Since a `continue` or `break` targets the immediate surrounding `while` loop, +we maintain a stack of the `continue` and `break` scopes. This is done by +saving the previous `continue` or `break` scope before parsing a `while` loop +and restoring afterward. + +## Examples + +### Example 1 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; +``` + + + + +### Example 2 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; +``` + + + +### Example 3 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; +``` + + + + +## Sea of Nodes Graph Evaluator + +The evaluator directly evaluates the given graph by walking forward through the control flow from the program start until it either encounters a Return node or it passes the maximum loop count. + +When called, the evaluator sets itself up by first traversing the graph to find the Start node. Then, if a program uses the special `arg` parameter, the passed-in parameter value will be bound to the node that represents it. + +With that brief setup done, the control projection from the Start node is traversed and the program can begin "execution". + +At this point, control flow is at the first region of the program, but it is treated just the same as any other region. There are two things that must be done at each region. First, resolve all phis to a specific value; and second to determine where control flow will continue to. + +It may seem like more than that should be done, but by resolving phi nodes, any logic that is specific to the control flow path for the given region will be resolved. Any other work will eventually be resolved later on as-needed. This is sufficient for the program to run! + +Finding the next place control flow will move to after a region is straightforward because any region only has a single control node that uses it. So we search for that node in the Region's users. + +Once we have that node, our behavior depends on what type of control flow node we've landed on. There are only 3 options: `RegionNode`, `IfNode`, and `ReturnNode`. If it is another `RegionNode`, we do the same again. If it's a `ReturnNode`, we can resolve the returned expression and return the program's value. Finally, for an `IfNode`, we must first resolve the test expression so that we can choose the true (projection 0) or false (projection 1) branch. Whichever projection from the `IfNode` is chosen, we step through that projection on to the control node (a `RegionNode`) that uses it. + +We talk about resolving nodes above, but what does that mean? A node will either have a value (for instance a constant), will already be resolved with the resolved value cached, or it will operate on nodes that it uses, which must be resolved. Once a node's inputs are resolved, its operation may be performed on them. For instance, an `AddNode`'s value will be the sum of its two inputs. Once the value is resolved, the resolved value is returned. + +With that, a simple non-looping program can be evaluated. + +Looping is almost functional with that, too, with only a couple of small extra details. Whenever control moves through a `LoopNode`, the evaluator checks that it hasn't run out of loop iterations. If it has, a timeout RuntimeException will be thrown. + +Finally, while calculating the value of `PhiNode`s in the loop region, we must be careful to compute all of their new values before we update any of their cached values. That's because as a loop iterates, we must ensure that all `PhiNode` values are consistently the value from the same point in time. Once all of the new values are calculated, we can update the cache for all of them at once. To illustrate this, consider the following code: + +```java +int t = 0; +while(arg < 10) { + t = arg; + arg = arg + 1; +} +return t; +``` + +In this code, the two statements within the loop may be evaluated in either +order by the graph, so we must ensure that the new value `arg` is not cached +before the value of `t` can be set to the previous value of `arg`. + +This approach to evaluation is useful for testing because it allows a program +to be executed without worrying about instruction selection, register +allocation or code generation. It executes the graph produced with normal +peephole optimization. In later chapters, the evaluator can compare graphs +optimized with different worklist orders to detect inconsistent results. This +chapter's fuzzer checks generated programs for compiler and evaluator failures. + +``` java +arg=arg+arg; +arg=arg+arg; +... +arg=arg+arg; +return arg; +``` + +On the other hand, this engine is not designed to be particularly fast! Because +not all expressions are cached, it's possible to construct programs like the +preceding one which have exponential runtime. + + +[^1]: We also experimented with option 2. For readers who would like to see this +alternative solution, we provide a separate branch with such an implementation.
\ No newline at end of file diff --git a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java new file mode 100644 index 00000000..f5694a78 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -0,0 +1,181 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.Arrays; +import java.util.BitSet; +import java.util.HashMap; + +public class GraphEvaluator { + + public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT } + + public record Result(ResultType type, long value) {} + + /** + * Find the start node from some node in the graph or null if there is no start node + */ + private static StartNode findStart(BitSet visit, Node node) { + if (node == null) return null; + if (node instanceof StartNode start) return start; + if( visit.get(node._nid) ) return null; + visit.set(node._nid); + for( Node def : node._inputs ) { + var res = findStart(visit,def); + if( res != null ) return res; + } + for( Node use : node._outputs ) { + var res = findStart(visit,use); + if( res != null ) return res; + } + return null; + } + + /** + * Find the control output from a control node + */ + private static Node findControl(Node control) { + for( Node use : control._outputs ) { + if (use.isCFG()) return use; + } + return null; + } + + /** + * Find the projection for a node + */ + private static ProjNode findProjection(Node node, int idx) { + for( Node use : node._outputs ) { + if (use instanceof ProjNode proj && proj._idx == idx) return proj; + } + return null; + } + + /** + * Cache values for phi and parameter projection nodes. + */ + private final HashMap<Node, Long> cacheValues = new HashMap<>(); + /** + * Cache for loop phis as they can depend on itself or other loop phis + */ + private long[] loopPhiCache = new long[16]; + + private GraphEvaluator() { + } + + private long div(DivNode div) { + long in2 = getValue(div.in(2)); + return in2 == 0 ? 0 : getValue(div.in(1)) / in2; + } + + /** + * Calculate the value of a node + */ + private long getValue(Node node) { + var cache = cacheValues.get(node); + if (cache != null) return cache; + return switch (node) { + case ConstantNode cons -> ((TypeInteger)cons.compute()).value(); + case AddNode add -> getValue(add.in(1)) + getValue(add.in(2)); + case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0; + case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0; + case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0; + case DivNode div -> div(div); + case MinusNode minus -> -getValue(minus.in(1)); + case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2)); + case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0; + case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2)); + default -> throw Utils.TODO("Unexpected node " + node); + }; + } + + /** + * Special case of latchPhis when phis can depend on phis of the same region. + */ + private void latchLoopPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + int i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2); + loopPhiCache[i++] = value; + } + } + i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]); + } + } + + /** + * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region. + */ + private void latchPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + cacheValues.put(phi, value); + } + } + } + + /** + * Run the graph until either a return is found or the number of loop iterations are done. + */ + private Result evaluate(StartNode start, long parameter, int loops) { + var parameter1 = findProjection(start, 1); + if (parameter1 != null) cacheValues.put(parameter1, parameter); + Node control = findProjection(start, 0); + Node prev = start; + while (control != null) { + Node next; + switch (control) { + case RegionNode region -> { + if (region instanceof LoopNode && region.in(1) != prev) { + if (loops--<=0) return new Result(ResultType.TIMEOUT, 0); + latchLoopPhis(region, prev); + } else { + latchPhis(region, prev); + } + next = findControl(region); + } + case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1); + case ReturnNode ret -> { + return new Result(ResultType.VALUE, getValue(ret.in(1))); + } + case ProjNode ignored -> next = findControl(control); + default -> throw Utils.TODO("Unexpected control node " + control); + } + prev = control; + control = next; + } + return new Result(ResultType.FALLTHROUGH, 0); + } + + public static long evaluate(Node graph) { + return evaluate(graph, 0); + } + + public static long evaluate(Node graph, long parameter) { + return evaluate(graph, parameter, 1000); + } + + public static long evaluate(Node graph, long parameter, int loops) { + var res = evaluateWithResult(graph, parameter, loops); + if (res.type==ResultType.TIMEOUT) throw new RuntimeException("Timeout"); + return res.value; + } + + public static Result evaluateWithResult(Node graph, long parameter, int loops) { + var start = findStart(new BitSet(), graph); + if (start == null) return new Result(ResultType.TIMEOUT, 0); + var evaluator = new GraphEvaluator(); + return evaluator.evaluate(start, parameter, loops); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java new file mode 100644 index 00000000..2e40ff74 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.print.IRAdapter; +import com.seaofnodes.simple.node.*; + +/** This chapter's read-only IR facts and the familiar debugger entry points. */ +public final class IRPrinter extends IRAdapter<Node> { + private static final com.seaofnodes.print.IRPrinter<Node> PRINT = + new com.seaofnodes.print.IRPrinter<>(new IRPrinter()); + @Override public String type(Node n) { return n._type==null ? "" : n._type.toString(); } + @Override public int inputColumns() { return 3; } + @Override public Kind kind(Node n) { + if( n instanceof StartNode ) return Kind.START; + if( n instanceof StopNode ) return Kind.STOP; + if( n instanceof LoopNode ) return Kind.LOOP; + if( n instanceof RegionNode ) return Kind.REGION; + if( n instanceof PhiNode ) return Kind.PHI; + if( n instanceof ReturnNode ) return Kind.RETURN; + if( n instanceof ConstantNode ) return Kind.CONSTANT; + if( n instanceof ProjNode ) return n.isCFG() ? Kind.CPROJ : Kind.PROJ; + if( n.isCFG() ) return Kind.CTRL; + if( n instanceof MultiNode ) return Kind.MULTI; + return Kind.DATA; + } + @Override public int index(Node n) { + if( n instanceof ProjNode p ) return p._idx; + return n._nid; + } + + public static String prettyPrint(Node n, int depth) { return PRINT.prettyPrint(n,depth); } +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 2e043538..d7055f48 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -54,6 +54,8 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("break"); + add("continue"); add("else"); add("false"); add("if"); @@ -70,11 +72,15 @@ public class Parser { */ public final Stack<ScopeNode> _xScopes = new Stack<>(); + ScopeNode _continueScope; + ScopeNode _breakScope; + public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); + _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); STOP = new StopNode(); } @@ -143,6 +149,8 @@ public class Parser { else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); else if (matchx("while")) return parseWhile(); + else if (matchx("break")) return parseBreak(); + else if (matchx("continue")) return parseContinue(); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } @@ -156,6 +164,10 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseWhile() { + + var savedContinueScope = _continueScope; + var savedBreakScope = _breakScope; + require("("); // Loop region has two control inputs, the first is the entry @@ -185,36 +197,71 @@ public class Parser { ifNode.unkeep(); Node ifF = new ProjNode(ifNode, 1, "False").peephole(); - // Clone the body Scope to create the exit Scope - // which accounts for any side effects in the predicate - // The exit Scope will be the final scope after the loop, - // And its control input is the False branch of the loop predicate - // Note that body Scope is still our current scope - var exit = _scope.dup(); - _xScopes.push(exit); - exit.ctrl(ifF); + // Clone the body Scope to create the break/exit Scope which accounts for any + // side effects in the predicate. The break/exit Scope will be the final + // scope after the loop, and its control input is the False branch of + // the loop predicate. Note that body Scope is still our current scope. + ctrl(ifF); + _xScopes.push(_breakScope = _scope.dup()); + + // No continues yet + _continueScope = null; // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body - // The true branch loops back, so whatever is current control (_scope.ctrl) gets - // added to head loop as input. endLoop() updates the head scope, - // and goes through all the phis that were created earlier. For each - // phi, it sets the second input to the corresponding input from the back edge. - // If the phi is redundant, it is replaced by its sole input. + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + + // The true branch loops back, so whatever is current _scope.ctrl gets + // added to head loop as input. endLoop() updates the head scope, and + // goes through all the phis that were created earlier. For each phi, + // it sets the second input to the corresponding input from the back + // edge. If the phi is redundant, it is replaced by its sole input. + var exit = _breakScope; head.endLoop(_scope, exit); head.unkeep().kill(); _xScopes.pop(); // Cleanup _xScopes.pop(); // Cleanup + _continueScope = savedContinueScope; + _breakScope = savedBreakScope; + // At exit the false control is the current control, and // the scope is the exit scope after the exit test. - return (_scope = exit); + return _scope = exit; + } + + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; } + private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); } + + private Node parseBreak () { checkLoopActive(); return ( _breakScope = require(jumpTo( _breakScope ),";")); } + private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); } + /** * Parses a statement * diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 5ee742f7..4a587953 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -63,6 +63,11 @@ public class AddNode extends Node { // Now we only see (add add non) + // Dead data cycle; comes about from dead infinite loops. Do nothing, + // the loop will peep as dead after a bit. + if( lhs.in(1) == lhs ) + return null; + // Do we have (x + con1) + con2? // Replace with (x + (con1+con2) which then fold the constants if( lhs.in(2)._type.isConstant() && t2.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 52d7e31e..41b5ffd7 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -42,7 +42,7 @@ public class IfNode extends MultiNode { return prior instanceof ProjNode proj // Repeated test, dominated on one side. Test result is the same. ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) - : null; // Repeated test not dominated on one side + : dom._type; // Repeated test not dominated on one side return TypeTuple.IF_BOTH; } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index e4ef68a3..fa9d871e 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -16,7 +16,8 @@ public class LoopNode extends RegionNode { @Override public Type compute() { - return inProgress() ? Type.CONTROL : super.compute(); + if( inProgress() ) return Type.CONTROL; + return entry()._type; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 1430cdac..46d5b843 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.BaseNode; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; @@ -71,6 +72,8 @@ public abstract class Node extends BaseNode<Node> { // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" public abstract String label(); + public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } + public boolean isMultiHead() { return false; } public boolean isMultiTail() { return false; } @@ -390,7 +393,9 @@ public abstract class Node extends BaseNode<Node> { * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. */ - public static void reset() { UNIQUE_ID = 1; } + public static void reset() { + UNIQUE_ID = 1; + } /** * Debugging utility to find a Node by index diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 64cd3dd7..14622140 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -78,10 +78,13 @@ public class PhiNode extends Node { */ private Node singleUniqueInput() { Node live = null; - for( int i=1; i<nIns(); i++ ) + for( int i=1; i<nIns(); i++ ) { + if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL ) + return null; // Dead entry loops just ignore and let the loop collapse if( region().in(i)._type != Type.XCONTROL && in(i) != this ) if( live == null || live == in(i) ) live = in(i); else return null; + } return live; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index e0dd45d7..b4dc3f58 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import java.util.Collection; public class RegionNode extends Node { diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index bd6b0d8c..31585ef4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -41,6 +41,10 @@ public class ScopeNode extends Node { for( int j=0; j<nIns(); j++ ) { p.p(names[j]).p(":"); Node n = in(j); + while( n instanceof ScopeNode loop ) { + p.p("Lazy_"); + n = loop.in(j); + } p.n(n).p(" "); } return p.unchar(' ').p("]"); @@ -108,8 +112,18 @@ public class ScopeNode extends Node { 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); + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have insert a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer } public Node ctrl() { return in(0); } @@ -132,6 +146,11 @@ public class ScopeNode extends Node { * tables), nor deep (would dup the Scope, the HashMap tables, but then * also the program Nodes). * <p> + * If the {@code loop} flag is set, the edges are filled in as the original + * Scope, as a indication of Lazy Phis at loop heads. The goal here is to + * not make Phis at loop heads for variables which are never touched in the + * loop body. + * <p> * The new Scope is a full-fledged Node with proper use<->def edges. */ public ScopeNode dup() { return dup(false); } @@ -145,17 +164,10 @@ public class ScopeNode extends Node { dup._scopes.push(new HashMap<>(syms)); dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i<nIns(); i++ ) { - if ( !loop ) { dup.addDef(in(i)); } - else { - String[] names = reverseNames(); // Get the variable names - // Create a phi node with second input as null - to be filled in - // by endLoop() below - dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole()); - // Ensure our node has the same phi in case we created one - setDef(i, dup.in(i)); - } - } + for( int i=1; i<nIns(); i++ ) + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); return dup; } @@ -173,7 +185,9 @@ public class ScopeNode extends Node { // Note that we skip i==0, which is bound to '$ctrl' for (int i = 1; i < nIns(); i++) if( in(i) != that.in(i) ) // No need for redundant Phis - setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope return r.unkeep().peephole(); } @@ -185,14 +199,26 @@ public class ScopeNode extends Node { assert ctrl instanceof LoopNode loop && loop.inProgress(); ctrl.setDef(2,back.ctrl()); for( int i=1; i<nIns(); i++ ) { - PhiNode phi = (PhiNode)in(i); - assert phi.region()==ctrl && phi.in(2)==null; - phi.setDef(2,back.in(i)); - // Do an eager useless-phi removal - Node in = phi.peephole(); - if( in != phi ) - phi.subsume(in); + if( back.in(i) != this ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==ctrl && phi.in(2)==null; + phi.setDef(2,back.in(i)); + } + if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also + exit.setDef(i,in(i)); } back.kill(); // Loop backedge is dead + // Now one-time do a useless-phi removal + for( int i=1; i<nIns(); i++ ) { + if( in(i) instanceof PhiNode phi ) { + // Do an eager useless-phi removal + Node in = phi.peephole(); + if( in != phi ) { + phi.subsume(in); + setDef(i,in); // Set the update back into Scope + } + } + } + } } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index c5ab1c60..a9acba10 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** Chapter 7's view of the IR; browser, transport and layout are shared. */ +/** Chapter 8's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String[] edgeNames(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 1835f53f..0c3f4ce8 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 7's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 8's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 547c36f8..13b42f96 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -31,7 +31,7 @@ public class Chapter01Test { parser.parse(); StartNode start = Parser.START; for( Node use : start._outputs ) - if( use instanceof ConstantNode con ) + if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) assertEquals(TypeInteger.constant(0),con._type); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 12201ca0..609dff76 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -31,7 +31,7 @@ public class Chapter03Test { @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);"); + 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); "); StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } @@ -45,7 +45,7 @@ public class Chapter03Test { assertEquals("Undefined name 'a'",e.getMessage()); } } - + @Test public void testRedeclareVar() { try { diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index e5840622..f1603cc4 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -10,7 +10,7 @@ public class Chapter04Test { @Test public void testPeephole() { - Parser parser = new Parser("return 1+arg+2;"); + Parser parser = new Parser("return 1+arg+2; "); StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @@ -38,7 +38,7 @@ public class Chapter04Test { @Test public void testPeephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3;"); + Parser parser = new Parser("return 1+arg+2+arg+3; "); StopNode ret = parser.parse(); assertEquals("return ((arg*2)+6);", ret.print()); } @@ -80,7 +80,7 @@ public class Chapter04Test { @Test public void testVarArg() { - Parser parser = new Parser("return arg;"); + Parser parser = new Parser("return arg; "); StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof ProjNode); @@ -89,49 +89,49 @@ public class Chapter04Test { @Test public void testConstantArg() { - Parser parser = new Parser("return arg;", TypeInteger.constant(2)); + Parser parser = new Parser("return arg; ", TypeInteger.constant(2)); StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testCompEq() { - Parser parser = new Parser("return 3==3;"); + Parser parser = new Parser("return 3==3; "); StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testCompEq2() { - Parser parser = new Parser("return 3==4;"); + Parser parser = new Parser("return 3==4; "); StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq() { - Parser parser = new Parser("return 3!=3;"); + Parser parser = new Parser("return 3!=3; "); StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq2() { - Parser parser = new Parser("return 3!=4;"); + Parser parser = new Parser("return 3!=4; "); StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testBug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;"); + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; "); StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testBug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a;"); + Parser parser = new Parser("int a=arg+1; a=a; return a; "); StopNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index d6c91a4a..fa9a5e37 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -17,7 +17,9 @@ if (arg == 1) a = arg+2; else { a = arg-3; + } + return a;"""); StopNode ret = parser.parse(); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index fb8dbcca..26b5c17d 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -35,7 +35,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } @Test @@ -55,7 +55,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,0,Phi(Loop21,Phi_sum,(Phi(Loop,0,(Phi_j+1))+Phi_sum)));", stop.toString()); + assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -71,7 +71,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -90,7 +90,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java new file mode 100644 index 00000000..5d9d1545 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -0,0 +1,218 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter08Test { + + @Test + @Ignore + public void testJig() { + Parser parser = new Parser(""" +// Insert test case here +"""); + StopNode stop = parser.parse(); + } + + @Test + public void testEx6() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(10, GraphEvaluator.evaluate(stop, 6)); + } + + + @Test + public void testEx5() { + Parser parser = new Parser( + """ +int a = 1; +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 7) + continue; + a = a + 1; +} +return a; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testEx4() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testEx3() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 6) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + + @Test + public void testEx2() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + + @Test + public void testEx1() { + Parser parser = new Parser( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testRegress1() { + Parser parser = new Parser( + """ +while( arg < 10 ) { + int a = arg+2; + if( a > 4 ) + break; +} +return arg; + """); + StopNode stop = parser.parse(); + assertEquals("return arg;", stop.toString()); + } + + @Test + public void testRegress2() { + Parser parser = new Parser("if(1) return 0; else while(arg>--arg) arg=arg+1; return 0;"); + StopNode stop = parser.parse(); + assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + } + + @Test + public void testBreakOutsideLoop() { + try { + new Parser(""" +if(arg <= 10) { + break; + arg = arg + 1; +} +return arg; +""").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("No active loop for a break or continue",e.getMessage()); + } + } + + @Test + public void testRegress3() { + Parser parser = new Parser(""" +while(arg < 10) { + break; +} +return arg; +"""); + StopNode stop = parser.parse(); + assertEquals("return arg;", stop.toString()); + } + + @Test + public void testRegress4() { + Parser parser = new Parser(""" +int a = 1; +while(arg < 10) { + a = a + 1; + if (arg > 2) { + int a = 17; + break; + } +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testRegress5() { + Parser parser = new Parser(""" +int a = 1; +while(1) { + a = a + 1; + if (a<10) continue; + break; +} +return a; +"""); + StopNode stop = parser.parse(); + assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java new file mode 100644 index 00000000..33434b6c --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -0,0 +1,41 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.fuzzer.Fuzzer; +import org.junit.Ignore; +import org.junit.Test; + + +import static org.junit.Assert.assertTrue; + +/** + * Normal tests run chapter-local regression seeds. Open failures and exploratory + * fuzzing are opt-in (run directly in the IDE or temporarily remove Ignore). + * Seeds depend on this chapter's generator; do not copy them between chapters. + */ +public class FuzzerWrap { + + private static final long[] REGRESSION_SEEDS = { + }; + + private static final long[] OPEN_FAILING_SEEDS = { + }; + + @Test public void fuzzPeepsRegression () { fuzzPeepsSeeds(REGRESSION_SEEDS); } + @Test @Ignore public void fuzzPeepsOpenFailures() { fuzzPeepsSeeds(OPEN_FAILING_SEEDS); } + + private static void fuzzPeepsSeeds(long... seeds) { + var fuzzer = new Fuzzer(); + for (long seed : seeds) + fuzzer.fuzzPeepsRegression(seed); + } + + @Test + @Ignore + public void fuzzPeepsLarge() { + var fuzzer = new Fuzzer(); + for (int i=0; i<100000; i++) + fuzzer.fuzzPeeps(i); + assertTrue(fuzzer.noExceptions()); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java new file mode 100644 index 00000000..ef73fa4b --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -0,0 +1,110 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.GraphEvaluator; +import com.seaofnodes.simple.node.StopNode; + +import java.util.ArrayList; +import java.util.Random; +import java.util.function.Consumer; + +/** + * Implementation of the fuzzer. + * Random testcases are generated using the ScriptGenerator. + * This will generate a script similar to how the parser parses it but instead of parsing it will + * randomly choose a variation the parser would parse and generate it. + * These scripts are the parsed by the parser and all exceptions are caught and filtered + * to only show one occurrence of one problem. Generated graphs are evaluated + * to detect compiler/evaluator failures; this chapter has no differential oracle. + * To aid debugging scripts that cause errors are then reduced by applying rules and checking + * that the same issue persists. + */ +public class Fuzzer { + + private static final int EVAL_TIMEOUT = 1000; + + /** + * List of exceptions already encountered. + * This is used to filter new exceptions and discard them if they are already found. + */ + private final ArrayList<Throwable> exceptions = new ArrayList<>(); + + /** + * Filter and record an exception in a script. + * @param e The exception caused by the script + * @param script The script causing the exception + * @param reproducer Reproducer which should be used to reproduce the test case. + */ + private void recordException(Throwable e, String script, Consumer<String> reproducer) { + for (var ex : exceptions) { + if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return; + } + exceptions.add(e); + System.out.println("========== Stack =========="); + e.printStackTrace(System.out); + System.out.println("========== Code ==========="); + System.out.println(script); + System.out.println("========= Reduced ========="); + System.out.println(Reducer.reduce(script, e, reproducer)); + System.out.println("==========================="); + System.out.flush(); + } + + /** Compile and evaluate generated programs with normal peepholes. */ + private static void runCheck(String script, boolean valid) { + StopNode stop; + try { + stop = FuzzerUtils.parse(script); + } catch (RuntimeException e) { + if (!valid || e.getClass() == RuntimeException.class) return; + throw e; + } + for (int input : new int[] {0, 1, 10}) + GraphEvaluator.evaluateWithResult(stop, input, EVAL_TIMEOUT); + } + + /** + * Check that the script does not result in exceptions. + * @param script The script to test. + * @param valid If the script is valid or if it might contain syntax errors. + */ + private void check(String script, boolean valid) { + try { + runCheck(script, valid); + } catch (Throwable e) { + recordException(e, script, s->runCheck(s, valid)); + } + } + + /** + * Run one test with the given seed. + * @param seed The seed to use for generating this test case + */ + public void fuzzPeeps(long seed) { + var rand = new Random(seed); + var sb = new StringBuilder(); + var valid = new ScriptGenerator(rand, sb, false).genProgram(); + check(sb.toString(), valid); + } + + /** + * Check that no exceptions happened. + * @return true if no exception happened + */ + public boolean noExceptions() { + return exceptions.isEmpty(); + } + + /** Run a fixed chapter-local seed without reducing or swallowing failures. */ + public void fuzzPeepsRegression(long seed) { + var rand = new Random(seed); + var sb = new StringBuilder(); + var valid = new ScriptGenerator(rand, sb, false).genProgram(); + try { + runCheck(sb.toString(), valid); + } catch (Throwable e) { + AssertionError ae = new AssertionError("Fuzzer regression seed failed: " + seed); + ae.initCause(e); + throw ae; + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java new file mode 100644 index 00000000..0e83861d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -0,0 +1,57 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; + +/** + * Some utilities for the fuzzer. + */ +class FuzzerUtils { + + /** + * Check that eiter one of the objects is null or that both are equal. + */ + private static boolean equalOrNull(Object a, Object b) { + if (a == null || b == null) return true; + return a.equals(b); + } + + /** + * Check if both stack traces have the same first entry. Empty stack traces can happen with NPE optimization + * and allow the other to be any stack trace. + */ + private static boolean sameStackTraceOrigin(StackTraceElement[] a, StackTraceElement[] b) { + if (a == null || a.length == 0 || b == null || b.length == 0) return true; // One or both stack traces are missing. + return a[0].equals(b[0]); + } + + /** + * Checks if two exceptions are caused by the same problem. + */ + public static boolean isExceptionFromSameCause(Throwable a, Throwable b) { + if (a == null || b == null) return a == b; // Handle the null case + if (a.getClass() != b.getClass()) return false; // Different classes + if (!equalOrNull(a.getMessage(), b.getMessage())) return false; // Different messages. Null is allowed as wildcard + var s1 = a.getStackTrace(); + var s2 = b.getStackTrace(); + if (!sameStackTraceOrigin(s1, s2)) return false; // Different stack trace origins + if (!isExceptionFromSameCause(a.getCause(), b.getCause())) return false; // Different causes + var o1 = a.getSuppressed(); + var o2 = b.getSuppressed(); + if (o1 == null || o2 == null || o1.length != o2.length) return o1 == o2; // Different suppression + for (int i=0; i<o1.length; i++) { + if (!isExceptionFromSameCause(o1[i], o2[i])) return false; // Different suppression + } + return true; + } + + /** + * Parse script with normal peephole optimization + */ + public static StopNode parse(String script) { + var parser = new Parser(script); + return parser.parse(); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java new file mode 100644 index 00000000..b7fc18ec --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java @@ -0,0 +1,144 @@ +package com.seaofnodes.simple.fuzzer; + +import java.util.function.Consumer; +import java.util.function.Predicate; +import java.util.regex.Pattern; + +/** + * This class is used to reduce test cases created by the fuzzer. + * It applies rewrite rules to the test case and checks that the + * test still produces the same exception. + * This is done in a fixpoint iteration until every rewrite produces + * no or a different exception. + */ +public class Reducer { + + /** + * Holder for the rewrite rules + */ + private record Replace(Pattern p, String r) {} + + /** + * List of rewrite rules. + */ + private static final Replace[] REPLACEMENTS = { + new Replace(Pattern.compile("(?<=[+\\-*/<>=(])--"), ""), + new Replace(Pattern.compile("\\b--"), "+"), + new Replace(Pattern.compile("\\b\\+-"), "-"), + new Replace(Pattern.compile("\\bfalse\\b"), "0"), + new Replace(Pattern.compile("\\btrue\\b"), "1"), + new Replace(Pattern.compile("-"), ""), + new Replace(Pattern.compile("(?<![+\\-*/<>=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"), + new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"), + new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"), + new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"), + new Replace(Pattern.compile("\\b\\w+\\b"), "1"), + new Replace(Pattern.compile("\\b\\w+\\b"), "0"), + new Replace(Pattern.compile("\\d+\\+"), ""), + new Replace(Pattern.compile("\\+\\d+"), ""), + new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), + new Replace(Pattern.compile("\\n+"), "\n"), + new Replace(Pattern.compile("^\\n+|\\n+$"), ""), + new Replace(Pattern.compile("else *"), ""), + new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""), + new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""), + }; + + /** + * Predicate to test if the reduced script generates the same error. + */ + private final Predicate<String> tester; + + /** + * Create a reducer with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + private Reducer(Predicate<String> tester) { + this.tester = tester; + } + + /** + * Rewrites the script with one rewrite rule. + */ + private String doReplacement(String script, Pattern pattern, String with) { + var matcher = pattern.matcher(script); + var sb = new StringBuilder(); + int last = 0; + while (matcher.find()) { + var pos = sb.length(); + matcher.appendReplacement(sb, with); + var tail = sb.length(); + matcher.appendTail(sb); + if (tester.test(sb.toString())) { + sb.setLength(tail); + } else { + sb.setLength(pos); + sb.append(script, last, matcher.end()); + } + last = matcher.end(); + } + matcher.appendTail(sb); + return sb.toString(); + } + + /** + * Clean up variable names from the random ones generated by the fuzzer. + */ + private String cleanVariables(String script) { + var matcher = Pattern.compile("\\bint ([0-9a-zA-Z_]+)").matcher(script); + int num = 0; + while (matcher.find()) { + var var = matcher.group(1); + if (var.matches("v\\d+")) continue; + while (script.contains("v"+num)) num++; + var n = script.replaceAll("\\b"+var+"\\b", "v" + num); + if (tester.test(n)) { + script = n; + } + } + return script; + } + + /** + * Run all rewrite rules once. + */ + private String doAllReplacements(String script) { + for (var replace: REPLACEMENTS) { + script = doReplacement(script, replace.p, replace.r); + } + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + public static String reduce(String script, Predicate<String> tester) { + var reducer = new Reducer(tester); + String old; + do { + old = script; + script = reducer.doAllReplacements(script); + script = reducer.cleanVariables(script); + } while (!script.equals(old)); + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a reproducer. + * @param ex The exception originally caused by the script + * @param reproducer Test function which throws an exception which will be checked against ex. + */ + public static String reduce(String script, Throwable ex, Consumer<String> reproducer) { + return reduce(script, s->{ + Throwable nex = null; + try { + reproducer.accept(s); + } catch (Throwable e) { + nex = e; + } + return FuzzerUtils.isExceptionFromSameCause(nex, ex); + }); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java new file mode 100644 index 00000000..148c2319 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -0,0 +1,462 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.ScopeNode; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.Random; + +/** + * Generate a pseudo random script. + * This generator will generate the same script for two random number generators initialized with the same seed. + * To generate valid code it implements the parser but instead of parsing it emits the statements and expressions. + * It is guaranteed to terminate. + */ +public class ScriptGenerator { + + /** + * Get the list of keywords from the parser. + */ + @SuppressWarnings("unchecked") + private static HashSet<String> getKeywords() { + try { + var field = Parser.class.getDeclaredField("KEYWORDS"); + field.setAccessible(true); + return (HashSet<String>) field.get(new Parser("")); + } catch (Throwable e) { + throw new ExceptionInInitializerError(e); + } + } + + /** + * Number of spaces per indentation + */ + private static final int INDENTATION = 4; + /** + * Valid characters for identifiers. The last 10 are not valid for the first character. + */ + private static final String VAR_CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_0123456789"; + /** + * List of keywords not valid for identifiers. + */ + private static final HashSet<String> KEYWORDS = getKeywords(); + + /** + * Flag for a statement that it does not pass on control flow to the next statement. + */ + private static final int FLAG_STOP = 0x01; + /** + * Flag for a statement that it contains a final if statement without an else branch. + */ + private static final int FLAG_IF_WITHOUT_ELSE = 0x02; + /** + * Binary operators. + */ + private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"}; + /** + * Unary operators. + */ + private static final String[] UNARY_OP = {"-"}; + + + /** + * The random number generator used for random decisions. + */ + private final Random random; + /** + * Indentation depth. + */ + private int indentation = 0; + /** + * Output string builder + */ + private final StringBuilder sb; + /** + * Number of nested loops + */ + private int loopDepth = 0; + /** + * Current scope start in the variables list. + */ + private int currScopeStart = 0; + /** + * The depth of blocks allowed. + */ + private int depth = 7; + /** + * The depth of expressions allowed. + */ + private int exprDepth = 3; + /** + * Current variables in scope. + */ + private final ArrayList<String> variables = new ArrayList<>(); + /** + * If this needs to generate valid scripts or is also allowed to generate invalid ones. + */ + private final boolean generateValid; + /** + * If this script might be invalid. + */ + private boolean maybeInvalid = false; + + /** + * + * @param random the random number generator. + * @param sb the script will be written to this string builder. + * @param generateValid if the script should be guaranteed valid or if it is allowed to contain bugs. + */ + public ScriptGenerator(Random random, StringBuilder sb, boolean generateValid) { + this.random = random; + this.sb = sb; + this.generateValid = generateValid; + } + + /** + * Random number with log distribution + * @param max The maximum value + * @return A random number in the range [0, max) with higher numbers being more uncommon. + */ + private int randLog(int max) { + max--; + int n = 1<<max; + var num = random.nextInt(n); + for (int i=max-1; i>=0; i--) { + if ((num & (1<<i))!=0) return max-i-1; + } + return max; + } + + /** + * Helper function to print indentation. + * @return sb for chaining + */ + private StringBuilder printIndentation() { + return sb.repeat(' ', indentation); + } + + /** + * Generate a random name for variables. This might be invalid when it is a keyword. + * @return The random name generated + */ + private StringBuilder getRandomName() { + int len = random.nextInt(10) + 1; + StringBuilder sb = new StringBuilder(len); + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10))); + for (int i=1; i<len; i++) + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + return sb; + } + + /** + * Generate a variable name. This might be new random name or a name from an outer scope. + * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope. + * @return The variable name. + */ + private String getVarName() { + if (currScopeStart > 0 && random.nextInt(10) > 7) { + // Use a variable outside the current scope. + var v = variables.get(random.nextInt(currScopeStart)); + if (variables.lastIndexOf(v) < currScopeStart) return v; + if (!generateValid) { + maybeInvalid = true; + return v; + } + } + // Generate a new random variable name + StringBuilder sb = getRandomName(); + var v = sb.toString(); + if (!generateValid && (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart)) { + maybeInvalid = true; + return v; + } + while (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart) { + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + v = sb.toString(); + } + return v; + } + + + + /** + * Generates a program and writes it into the string builder supplied in the constructor. + * @return If the program is allowed to be invalid returns if something potentially invalid was generated. + */ + public boolean genProgram() { + this.maybeInvalid = false; + variables.add(ScopeNode.ARG0); + currScopeStart = variables.size(); + if ((genStatements() & FLAG_STOP) == 0) { + if (generateValid || random.nextInt(10)<7) { + genReturn(); + } else { + this.maybeInvalid = true; + } + } + return !this.maybeInvalid; + } + + /** + * Generate a list of statements. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated + */ + public int genStatements() { + var num = random.nextInt(10); + for (int i=0; i<num; i++) { + printIndentation(); + var stop = genStatement(); + sb.append("\n"); + if ((stop & FLAG_STOP) != 0) return stop; + } + return 0; + } + + /** + * Generate a single statement + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genStatement() { + return switch (random.nextInt(10)) { + case 1 -> genBlock(); + case 2 -> genIf(); + case 3 -> genWhile(); + case 4, 5 -> genDecl(); + case 6, 7, 8 -> genAssignment(); + default -> genExit(); + }; + } + + /** + * Generate a statement for if, else and while blocks. + * This is special since it disallows declarations and prefers to generate blocks. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genStatementBlock() { + indentation += INDENTATION; + int res; + if (depth == 0) { + res = random.nextBoolean() ? genAssignment() : genExit(); + } else { + depth--; + res = switch (random.nextInt(10)) { + case 1, 2, 3, 4, 5 -> { + depth++; + indentation -= INDENTATION; + var ret = genBlock(); + indentation += INDENTATION; + depth--; + yield ret; + } + case 6 -> genIf(); + case 7 -> genWhile(); + case 8 -> genAssignment(); + default -> genExit(); + }; + depth++; + } + indentation -= INDENTATION; + return res; + } + + /** + * Generate an exit. This can be return or break and continue when in a loop. + * @return FLAG_STOP + */ + public int genExit() { + if (loopDepth == 0 && generateValid) return genReturn(); + return switch (random.nextInt(7)) { + case 0,1,2 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("continue;"); + yield FLAG_STOP; + } + case 3,4,5 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("break;"); + yield FLAG_STOP; + } + default -> genReturn(); + }; + } + + /** + * Generate a block statement. After a certain depth only empty blocks are generated to ensure termination of the generator. + * @return flag FLAG_STOP for the generated statement + */ + public int genBlock() { + if (depth == 0) { + sb.append("{}"); + return 0; + } + depth--; + int oldCSS = currScopeStart; + currScopeStart = variables.size(); + sb.append("{\n"); + indentation += INDENTATION; + var stop = genStatements(); + indentation -= INDENTATION; + printIndentation().append("}"); + while (variables.size() > currScopeStart) + variables.removeLast(); + currScopeStart = oldCSS; + depth++; + return stop & ~FLAG_IF_WITHOUT_ELSE; + } + + /** + * Generate an if statement with an optional else block. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genIf() { + sb.append("if("); + genExpression(); + sb.append(") "); + var stop = genStatementBlock(); + if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { + sb.append("\n"); + printIndentation().append("else "); + stop &= genStatementBlock(); + } else { + stop = FLAG_IF_WITHOUT_ELSE; + } + return stop; + } + + /** + * Generate a while loop. + * @return 0 + */ + public int genWhile() { + sb.append("while("); + genExpression(); + sb.append(") "); + loopDepth++; + genStatementBlock(); + loopDepth--; + return 0; + } + + /** + * Generate a declaration statement. + * @return 0 + */ + public int genDecl() { + String name = getVarName(); + sb.append("int ").append(name).append("="); + genExpression(); + sb.append(";"); + variables.add(name); + return 0; + } + + /** + * Generate an assignment statement. + * @return 0 + */ + public int genAssignment() { + if (variables.isEmpty()) return genDecl(); + genVariable(); + sb.append("="); + genExpression(); + sb.append(";"); + return 0; + } + + /** + * Generate a return statement. + * @return FLAG_STOP + */ + public int genReturn() { + sb.append("return "); + genExpression(); + sb.append(";"); + return FLAG_STOP; + } + + + /** + * Generate a binary expression. + * This method does not care about operator precedence. + */ + public void genExpression() { + var num = randLog(10); + while(num-->0) { + genUnary(); + sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); + } + genUnary(); + } + + /** + * Generate a unary expression. + */ + public void genUnary() { + var num = randLog(6); + while(num-->0) { + sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); + } + genPrimary(); + } + + /** + * Generate a primary expression. + */ + public void genPrimary() { + switch (random.nextInt(10)) { + case 0: + sb.append("true"); + break; + case 1: + sb.append("false"); + break; + case 2: + if (exprDepth == 0) { + // Ensure termination of the generator. + if (random.nextBoolean()) { + genNumber(); + } else { + genVariable(); + } + } else { + sb.append("("); + exprDepth--; + genExpression(); + exprDepth++; + sb.append(")"); + } + break; + case 3, 4, 5, 6: + genNumber(); + break; + default: + genVariable(); + } + } + + /** + * Generate a number. + */ + public void genNumber() { + sb.append(random.nextInt(100)); + } + + /** + * Generate a variable. If there are none generate a number instead. + * If the program is allowed to be invalid a random name can be generated in some cases. + */ + public void genVariable() { + if (!generateValid && random.nextInt(100)>97) { + sb.append(getRandomName()); + maybeInvalid = true; + return; + } + if (variables.isEmpty()) { + genNumber(); + } else { + sb.append(variables.get(random.nextInt(variables.size()))); + } + } + +} |
