summaryrefslogtreecommitdiff
path: root/docs/chapter09
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2024-03-03 17:55:47 +0000
committerCliff Click <cliffc@acm.org>2026-10-08 16:52:27 -0700
commit81e464bab1193e0d4b973503ee1da1c9700a66a6 (patch)
treec1acdb04e7810f93bca6a9d81f0225d4ed3f287a /docs/chapter09
parent67ee27bfb29036efe7b154f633817aa152182684 (diff)
downloadSimple-81e464bab1193e0d4b973503ee1da1c9700a66a6.tar.gz
Simple-81e464bab1193e0d4b973503ee1da1c9700a66a6.zip
Chapter 9: Global Value Numbering and Iterative Peepholes
Co-authored-by: Thalia Archibald <thalia@archibald.dev> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.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: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com> Co-authored-by: Symious <14933944+symious@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: Hadházy Tamás <helsgithub15@gmail.com> Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk> Co-authored-by: Darrick Wiebe <darrickw@untether.ai> Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Diffstat (limited to 'docs/chapter09')
-rw-r--r--docs/chapter09/09-graph1.gv67
-rw-r--r--docs/chapter09/09-graph1.json23
-rw-r--r--docs/chapter09/09-graph1.svg110
-rw-r--r--docs/chapter09/09-graph2.gv63
-rw-r--r--docs/chapter09/09-graph2.json21
-rw-r--r--docs/chapter09/09-graph2.svg102
-rw-r--r--docs/chapter09/09-graph3.gv37
-rw-r--r--docs/chapter09/09-graph3.json17
-rw-r--r--docs/chapter09/09-graph3.svg89
-rw-r--r--docs/chapter09/09-graph4.gv29
-rw-r--r--docs/chapter09/09-graph4.json13
-rw-r--r--docs/chapter09/09-graph4.svg70
-rw-r--r--docs/chapter09/09-graph5.gv63
-rw-r--r--docs/chapter09/09-graph5.json18
-rw-r--r--docs/chapter09/09-graph5.svg92
-rw-r--r--docs/chapter09/09-graph6.gv60
-rw-r--r--docs/chapter09/09-graph6.json17
-rw-r--r--docs/chapter09/09-graph6.svg87
-rw-r--r--docs/chapter09/Makefile1
-rw-r--r--docs/chapter09/README.ja.md190
-rw-r--r--docs/chapter09/README.md314
21 files changed, 1483 insertions, 0 deletions
diff --git a/docs/chapter09/09-graph1.gv b/docs/chapter09/09-graph1.gv
new file mode 100644
index 00000000..e6d1851a
--- /dev/null
+++ b/docs/chapter09/09-graph1.gv
@@ -0,0 +1,67 @@
+digraph chapter08 {
+/*
+int x = arg + arg;
+if(arg < 10) {
+ return arg + arg;
+}
+else {
+ x = x + 1;
+}
+return x;
+
+*/
+ 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" ];
+ Con_7 [ label="2" ];
+ Mul8 [ label="*" ];
+ 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_16 [ label="2" ];
+ Mul17 [ label="*" ];
+ Return18 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ Con_20 [ label="1" ];
+ Add21 [ label="+" ];
+ Return24 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ }
+ edge [ fontname=Helvetica, fontsize=8 ];
+ Stop3 -> Return18[taillabel=0 color=red];
+ Stop3 -> Return24[taillabel=1 color=red];
+ Mul8 -> Start2:p1[taillabel=1];
+ Mul8 -> Con_7[taillabel=2];
+ LT10 -> Start2:p1[taillabel=1];
+ LT10 -> Con_9[taillabel=2];
+ If11 -> Start2:p0[taillabel=0 color=red];
+ If11 -> LT10[taillabel=1];
+ Mul17 -> Start2:p1[taillabel=1];
+ Mul17 -> Con_16[taillabel=2];
+ Return18 -> If11:p0[taillabel=0 color=red];
+ Return18 -> Mul17[taillabel=1];
+ Add21 -> Mul8[taillabel=1];
+ Add21 -> Con_20[taillabel=2];
+ Return24 -> If11:p1[taillabel=0 color=red];
+ Return24 -> Add21[taillabel=1];
+}
diff --git a/docs/chapter09/09-graph1.json b/docs/chapter09/09-graph1.json
new file mode 100644
index 00000000..8dfdee0a
--- /dev/null
+++ b/docs/chapter09/09-graph1.json
@@ -0,0 +1,23 @@
+{
+ "ver": 1,
+ "comp": "chapter09/docs/09-graph1.svg",
+ "step": 1,
+ "roots": [18, 24],
+ "scope": 0,
+ "nodes": [
+ {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "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": [], "proj": {"par": 0, "idx": 0}},
+ {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}},
+ {"id": 7, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 8, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null},
+ {"id": 16, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 17, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null},
+ {"id": 18, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}], "proj": null},
+ {"id": 20, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 21, "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": 20, "role": "DATA", "label": null}], "proj": null},
+ {"id": 24, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 21, "role": "DATA", "label": null}], "proj": null}
+ ],
+ "groups": [
+ ]
+}
diff --git a/docs/chapter09/09-graph1.svg b/docs/chapter09/09-graph1.svg
new file mode 100644
index 00000000..1b53a14a
--- /dev/null
+++ b/docs/chapter09/09-graph1.svg
@@ -0,0 +1,110 @@
+<svg aria-label="Compiler graph" width="587" height="454" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 587 454" style="font-family: sans-serif;"><style>
+ html, body { height:100%; margin:0; font-family:sans-serif; }
+ .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; }
+ .source { padding:8px; border-bottom:1px solid #ccc; }
+ #program { width:min(600px,80vw); vertical-align:middle; }
+ #status { margin-top:4px; }
+ #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; }
+ #elk { width:100%; height:100%; }
+ #graph svg { display:block; }
+ .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; }
+ .hint { color:#616c78; }
+ .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; }
+ .edge { fill:none; stroke-width:1.5; }
+ .edge.CTRL { stroke-width:2; }
+ .edge.ASSOC { stroke-dasharray:4 4; }
+ .edge.PARSER { stroke-dasharray:5 4; }
+ .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; }
+ .edge.selected { stroke-width:3.5; }
+ .edge.bundle { stroke-width:4; }
+ .edge.bundle.selected { stroke-width:6; }
+ .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; }
+ .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; }
+ .node { cursor:pointer; }
+ .box { stroke:#758191; stroke-width:1; }
+ .node.held .box { stroke-dasharray:5 3; }
+ .node.near .box { stroke:#c18221; stroke-width:2; }
+ .node.focus .box { stroke:#9c4900; stroke-width:3; }
+ .node.selected .box { stroke:#1569b9; stroke-width:3; }
+ .node.folded .box { stroke-width:4; }
+ .node.folding .box { fill:#f4ccd7; }
+ .fold-tag { font-size:9px; font-weight:700; fill:#963751; }
+ .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; }
+ .node.peep-edit .box { stroke:#9c4900; stroke-width:3; }
+ .node.error .box { stroke:#b42318; stroke-width:4; }
+ #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; }
+ .peep-ghosts { pointer-events:none; }
+ .region-box { stroke:#9da9b8; stroke-width:1.5; }
+ .fold-btn { cursor:pointer; }
+ .fold-btn rect { fill:white; stroke:#596674; }
+ .fold-btn text { font-size:14px; fill:#152330; }
+ .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; }
+ .shortcut { cursor:pointer; }
+ .shortcut path { fill:none; stroke-width:1.5; }
+ .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; }
+ .shortcut text { font-size:11px; fill:#783030; }
+ .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; }
+ .label { font-size:12px; fill:#152330; font-weight:600; }
+ .node-id { font-size:10px; fill:#596674; font-weight:400; }
+ .type { font-size:11px; fill:#455768; }
+ .port { stroke:#536477; stroke-width:1; }
+ .row { stroke:#b6afcf; stroke-width:1; }
+ .bind { font-size:12px; fill:#152330; }
+ .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; }
+ #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px;
+ max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere;
+ background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; }
+ .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; }
+ .button { color:white; background:black; font-size:20px; min-width:30px; }
+ .button:disabled { background:grey; }
+ .count { font-size:20px; min-width:35px; text-align:center; }
+ #N { width:6ch; }
+ #scrub { width:clamp(120px,35vw,600px); }
+ </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e8i1" d="M193,118 L193,130 Q193,138 201,138 L337,138 Q345,138 345,146 L345,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge DATA" id="e8i2" d="M503,118 L503,123 Q503,128 498,128 L383,128 Q375,128 375,136 L375,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge DATA" id="e17i1" d="M193,118 L193,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[1] → #4 · DATA</title></path><path class="edge DATA" id="e17i2" d="M351,118 L351,123 Q351,128 346,128 L231,128 Q223,128 223,136 L223,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[2] → #16 · DATA</title></path><path class="edge CTRL" id="e18i0" d="M64,222 L64,270" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#18[0] → #5 · CTRL</title></path><path class="edge DATA" id="e18i1" d="M193,222 L193,227 Q193,232 188,232 L112,232 Q104,232 104,240 L104,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #17 · DATA</title></path><path class="edge DATA" id="e21i1" d="M345,222 L345,230 Q345,232 347,232 L347,232 Q349,232 349,234 L349,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#21[1] → #8 · DATA</title></path><path class="edge DATA" id="e21i2" d="M497,222 L497,227 Q497,232 492,232 L387,232 Q379,232 379,240 L379,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#21[2] → #20 · DATA</title></path><path class="edge CTRL" id="e24i0" d="M217,326 L217,374" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#24[0] → #6 · CTRL</title></path><path class="edge DATA" id="e24i1" d="M349,326 L349,331 Q349,336 344,336 L265,336 Q257,336 257,344 L257,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#24[1] → #21 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(133,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id">  #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start
+Type not computed
+
+</title></g><g class="node" id="n4" data-id="4" transform="translate(133,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(26,190)" style="opacity: 1;"><path class="box" d="M0,0H75V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="37.5" y="17"><tspan>True</tspan><tspan class="node-id">  #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="37.5"/><title>#5 True
+Projection 0 of #0
+Type not computed
+
+</title></g><g class="node" id="n6" data-id="6" transform="translate(176,294)" style="opacity: 1;"><path class="box" d="M0,0H81V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="40.5" y="17"><tspan>False</tspan><tspan class="node-id">  #6/1</tspan></text><text class="type" text-anchor="middle" y="35" x="40.5"/><title>#6 False
+Projection 1 of #0
+Type not computed
+
+</title></g><g class="node" id="n7" data-id="7" transform="translate(443,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>2</tspan><tspan class="node-id">  #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 2
+Type not computed
+
+</title></g><g class="node" id="n8" data-id="8" transform="translate(285,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>*</tspan><tspan class="node-id">  #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 *
+Type not computed
+
+[0] → — DATA
+[1] → #4 DATA
+[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n16" data-id="16" transform="translate(291,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>2</tspan><tspan class="node-id">  #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 2
+Type not computed
+
+</title></g><g class="node" id="n17" data-id="17" transform="translate(133,172)" 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">  #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 *
+Type not computed
+
+[0] → — DATA
+[1] → #4 DATA
+[2] → #16 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="n18" data-id="18" transform="translate(24,276)" 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">  #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 Return
+Type not computed
+
+[0] → #5 CTRL
+[1] → #17 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 class="node" id="n20" data-id="20" transform="translate(437,172)" 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">  #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 1
+Type not computed
+
+</title></g><g class="node" id="n21" data-id="21" transform="translate(289,276)" 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">  #21</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#21 +
+Type not computed
+
+[0] → — DATA
+[1] → #8 DATA
+[2] → #20 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="n24" data-id="24" transform="translate(177,380)" 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">  #24</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#24 Return
+Type not computed
+
+[0] → #6 CTRL
+[1] → #21 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg>
diff --git a/docs/chapter09/09-graph2.gv b/docs/chapter09/09-graph2.gv
new file mode 100644
index 00000000..1a1f7a29
--- /dev/null
+++ b/docs/chapter09/09-graph2.gv
@@ -0,0 +1,63 @@
+digraph chapter09 {
+/*
+int x = arg + arg;
+if(arg < 10) {
+ return arg + arg;
+}
+else {
+ x = x + 1;
+}
+return x;
+
+*/
+ 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" ];
+ Con_7 [ label="#2" ];
+ Mul8 [ label="*" ];
+ LT9 [ label="<" ];
+ Con_10 [ label="#10" ];
+ 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>>
+ ];
+ Return18 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ Add20 [ label="+" ];
+ Con_21 [ label="#1" ];
+ Return24 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ }
+ edge [ fontname=Helvetica, fontsize=8 ];
+ Stop3 -> Return18[taillabel=0 color=red];
+ Stop3 -> Return24[taillabel=1 color=red];
+ Mul8 -> Start2:p1[taillabel=1];
+ Mul8 -> Con_7[taillabel=2];
+ LT9 -> Start2:p1[taillabel=1];
+ LT9 -> Con_10[taillabel=2];
+ If11 -> Start2:p0[taillabel=0 color=red];
+ If11 -> LT9[taillabel=1];
+ Return18 -> If11:p0[taillabel=0 color=red];
+ Return18 -> Mul8[taillabel=1];
+ Add20 -> Mul8[taillabel=1];
+ Add20 -> Con_21[taillabel=2];
+ Return24 -> If11:p1[taillabel=0 color=red];
+ Return24 -> Add20[taillabel=1];
+}
diff --git a/docs/chapter09/09-graph2.json b/docs/chapter09/09-graph2.json
new file mode 100644
index 00000000..7b48931f
--- /dev/null
+++ b/docs/chapter09/09-graph2.json
@@ -0,0 +1,21 @@
+{
+ "ver": 1,
+ "comp": "chapter09/docs/09-graph2.svg",
+ "step": 1,
+ "roots": [18, 24],
+ "scope": 0,
+ "nodes": [
+ {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "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": [], "proj": {"par": 0, "idx": 0}},
+ {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}},
+ {"id": 7, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 8, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null},
+ {"id": 18, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null},
+ {"id": 20, "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": 21, "role": "DATA", "label": null}], "proj": null},
+ {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 24, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}], "proj": null}
+ ],
+ "groups": [
+ ]
+}
diff --git a/docs/chapter09/09-graph2.svg b/docs/chapter09/09-graph2.svg
new file mode 100644
index 00000000..59ef5de1
--- /dev/null
+++ b/docs/chapter09/09-graph2.svg
@@ -0,0 +1,102 @@
+<svg aria-label="Compiler graph" width="548" height="454" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 548 454" style="font-family: sans-serif;"><style>
+ html, body { height:100%; margin:0; font-family:sans-serif; }
+ .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; }
+ .source { padding:8px; border-bottom:1px solid #ccc; }
+ #program { width:min(600px,80vw); vertical-align:middle; }
+ #status { margin-top:4px; }
+ #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; }
+ #elk { width:100%; height:100%; }
+ #graph svg { display:block; }
+ .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; }
+ .hint { color:#616c78; }
+ .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; }
+ .edge { fill:none; stroke-width:1.5; }
+ .edge.CTRL { stroke-width:2; }
+ .edge.ASSOC { stroke-dasharray:4 4; }
+ .edge.PARSER { stroke-dasharray:5 4; }
+ .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; }
+ .edge.selected { stroke-width:3.5; }
+ .edge.bundle { stroke-width:4; }
+ .edge.bundle.selected { stroke-width:6; }
+ .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; }
+ .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; }
+ .node { cursor:pointer; }
+ .box { stroke:#758191; stroke-width:1; }
+ .node.held .box { stroke-dasharray:5 3; }
+ .node.near .box { stroke:#c18221; stroke-width:2; }
+ .node.focus .box { stroke:#9c4900; stroke-width:3; }
+ .node.selected .box { stroke:#1569b9; stroke-width:3; }
+ .node.folded .box { stroke-width:4; }
+ .node.folding .box { fill:#f4ccd7; }
+ .fold-tag { font-size:9px; font-weight:700; fill:#963751; }
+ .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; }
+ .node.peep-edit .box { stroke:#9c4900; stroke-width:3; }
+ .node.error .box { stroke:#b42318; stroke-width:4; }
+ #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; }
+ .peep-ghosts { pointer-events:none; }
+ .region-box { stroke:#9da9b8; stroke-width:1.5; }
+ .fold-btn { cursor:pointer; }
+ .fold-btn rect { fill:white; stroke:#596674; }
+ .fold-btn text { font-size:14px; fill:#152330; }
+ .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; }
+ .shortcut { cursor:pointer; }
+ .shortcut path { fill:none; stroke-width:1.5; }
+ .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; }
+ .shortcut text { font-size:11px; fill:#783030; }
+ .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; }
+ .label { font-size:12px; fill:#152330; font-weight:600; }
+ .node-id { font-size:10px; fill:#596674; font-weight:400; }
+ .type { font-size:11px; fill:#455768; }
+ .port { stroke:#536477; stroke-width:1; }
+ .row { stroke:#b6afcf; stroke-width:1; }
+ .bind { font-size:12px; fill:#152330; }
+ .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; }
+ #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px;
+ max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere;
+ background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; }
+ .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; }
+ .button { color:white; background:black; font-size:20px; min-width:30px; }
+ .button:disabled { background:grey; }
+ .count { font-size:20px; min-width:35px; text-align:center; }
+ #N { width:6ch; }
+ #scrub { width:clamp(120px,35vw,600px); }
+ </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e8i1" d="M306,118 L306,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge DATA" id="e8i2" d="M464,118 L464,123 Q464,128 459,128 L344,128 Q336,128 336,136 L336,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge CTRL" id="e18i0" d="M177,222 L177,270" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#18[0] → #5 · CTRL</title></path><path class="edge DATA" id="e18i1" d="M306,222 L306,227 Q306,232 301,232 L225,232 Q217,232 217,240 L217,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #8 · DATA</title></path><path class="edge DATA" id="e20i1" d="M306,222 L306,227 Q306,232 311,232 L341,232 Q349,232 349,240 L349,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[1] → #8 · DATA</title></path><path class="edge DATA" id="e20i2" d="M458,222 L458,227 Q458,232 453,232 L387,232 Q379,232 379,240 L379,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[2] → #21 · DATA</title></path><path class="edge CTRL" id="e24i0" d="M65,326 L65,374" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#24[0] → #6 · CTRL</title></path><path class="edge DATA" id="e24i1" d="M349,326 L349,331 Q349,336 344,336 L113,336 Q105,336 105,344 L105,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#24[1] → #20 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(246,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id">  #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start
+Type not computed
+
+</title></g><g class="node" id="n4" data-id="4" transform="translate(246,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(139,190)" style="opacity: 1;"><path class="box" d="M0,0H75V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="37.5" y="17"><tspan>True</tspan><tspan class="node-id">  #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="37.5"/><title>#5 True
+Projection 0 of #0
+Type not computed
+
+</title></g><g class="node" id="n6" data-id="6" transform="translate(24,294)" style="opacity: 1;"><path class="box" d="M0,0H81V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="40.5" y="17"><tspan>False</tspan><tspan class="node-id">  #6/1</tspan></text><text class="type" text-anchor="middle" y="35" x="40.5"/><title>#6 False
+Projection 1 of #0
+Type not computed
+
+</title></g><g class="node" id="n7" data-id="7" transform="translate(404,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>#2</tspan><tspan class="node-id">  #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 #2
+Type not computed
+
+</title></g><g class="node" id="n8" data-id="8" transform="translate(246,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>*</tspan><tspan class="node-id">  #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 *
+Type not computed
+
+[0] → — DATA
+[1] → #4 DATA
+[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n18" data-id="18" transform="translate(137,276)" 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">  #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 Return
+Type not computed
+
+[0] → #5 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 class="node" id="n20" data-id="20" transform="translate(289,276)" 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">  #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 +
+Type not computed
+
+[0] → — DATA
+[1] → #8 DATA
+[2] → #21 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="n21" data-id="21" transform="translate(398,172)" 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">  #21</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#21 #1
+Type not computed
+
+</title></g><g class="node" id="n24" data-id="24" transform="translate(25,380)" 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">  #24</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#24 Return
+Type not computed
+
+[0] → #6 CTRL
+[1] → #20 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg>
diff --git a/docs/chapter09/09-graph3.gv b/docs/chapter09/09-graph3.gv
new file mode 100644
index 00000000..37bb1c53
--- /dev/null
+++ b/docs/chapter09/09-graph3.gv
@@ -0,0 +1,37 @@
+digraph chapter08 {
+/*
+return arg*arg-arg*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" ];
+ Mul6 [ label="*" ];
+ Mul7 [ label="*" ];
+ Sub8 [ label="-" ];
+ Return9 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ }
+ edge [ fontname=Helvetica, fontsize=8 ];
+ Stop3 -> Return9[taillabel=0 color=red];
+ Mul6 -> Start2:p1[taillabel=1];
+ Mul6 -> Start2:p1[taillabel=2];
+ Mul7 -> Start2:p1[taillabel=1];
+ Mul7 -> Start2:p1[taillabel=2];
+ Sub8 -> Mul6[taillabel=1];
+ Sub8 -> Mul7[taillabel=2];
+ Return9 -> Start2:p0[taillabel=0 color=red];
+ Return9 -> Sub8[taillabel=1];
+}
diff --git a/docs/chapter09/09-graph3.json b/docs/chapter09/09-graph3.json
new file mode 100644
index 00000000..abdb81b6
--- /dev/null
+++ b/docs/chapter09/09-graph3.json
@@ -0,0 +1,17 @@
+{
+ "ver": 1,
+ "comp": "chapter09/docs/09-graph3.svg",
+ "step": 1,
+ "roots": [9],
+ "scope": 0,
+ "nodes": [
+ {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "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": 6, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null},
+ {"id": 7, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null},
+ {"id": 8, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null},
+ {"id": 9, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}
+ ],
+ "groups": [
+ ]
+}
diff --git a/docs/chapter09/09-graph3.svg b/docs/chapter09/09-graph3.svg
new file mode 100644
index 00000000..da89b9b9
--- /dev/null
+++ b/docs/chapter09/09-graph3.svg
@@ -0,0 +1,89 @@
+<svg aria-label="Compiler graph" width="340" height="454" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 340 454" style="font-family: sans-serif;"><style>
+ html, body { height:100%; margin:0; font-family:sans-serif; }
+ .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; }
+ .source { padding:8px; border-bottom:1px solid #ccc; }
+ #program { width:min(600px,80vw); vertical-align:middle; }
+ #status { margin-top:4px; }
+ #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; }
+ #elk { width:100%; height:100%; }
+ #graph svg { display:block; }
+ .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; }
+ .hint { color:#616c78; }
+ .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; }
+ .edge { fill:none; stroke-width:1.5; }
+ .edge.CTRL { stroke-width:2; }
+ .edge.ASSOC { stroke-dasharray:4 4; }
+ .edge.PARSER { stroke-dasharray:5 4; }
+ .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; }
+ .edge.selected { stroke-width:3.5; }
+ .edge.bundle { stroke-width:4; }
+ .edge.bundle.selected { stroke-width:6; }
+ .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; }
+ .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; }
+ .node { cursor:pointer; }
+ .box { stroke:#758191; stroke-width:1; }
+ .node.held .box { stroke-dasharray:5 3; }
+ .node.near .box { stroke:#c18221; stroke-width:2; }
+ .node.focus .box { stroke:#9c4900; stroke-width:3; }
+ .node.selected .box { stroke:#1569b9; stroke-width:3; }
+ .node.folded .box { stroke-width:4; }
+ .node.folding .box { fill:#f4ccd7; }
+ .fold-tag { font-size:9px; font-weight:700; fill:#963751; }
+ .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; }
+ .node.peep-edit .box { stroke:#9c4900; stroke-width:3; }
+ .node.error .box { stroke:#b42318; stroke-width:4; }
+ #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; }
+ .peep-ghosts { pointer-events:none; }
+ .region-box { stroke:#9da9b8; stroke-width:1.5; }
+ .fold-btn { cursor:pointer; }
+ .fold-btn rect { fill:white; stroke:#596674; }
+ .fold-btn text { font-size:14px; fill:#152330; }
+ .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; }
+ .shortcut { cursor:pointer; }
+ .shortcut path { fill:none; stroke-width:1.5; }
+ .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; }
+ .shortcut text { font-size:11px; fill:#783030; }
+ .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; }
+ .label { font-size:12px; fill:#152330; font-weight:600; }
+ .node-id { font-size:10px; fill:#596674; font-weight:400; }
+ .type { font-size:11px; fill:#455768; }
+ .port { stroke:#536477; stroke-width:1; }
+ .row { stroke:#b6afcf; stroke-width:1; }
+ .bind { font-size:12px; fill:#152330; }
+ .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; }
+ #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px;
+ max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere;
+ background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; }
+ .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; }
+ .button { color:white; background:black; font-size:20px; min-width:30px; }
+ .button:disabled { background:grey; }
+ .count { font-size:20px; min-width:35px; text-align:center; }
+ #N { width:6ch; }
+ #scrub { width:clamp(120px,35vw,600px); }
+ </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e6i1" d="M134,118 L134,123 Q134,128 129,128 L112,128 Q104,128 104,136 L104,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#6[1] → #4 · DATA</title></path><path class="edge DATA" id="e6i2" d="M134,118 L134,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#6[2] → #4 · DATA</title></path><path class="edge DATA" id="e7i1" d="M134,118 L134,123 Q134,128 139,128 L248,128 Q256,128 256,136 L256,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #4 · DATA</title></path><path class="edge DATA" id="e7i2" d="M134,118 L134,123 Q134,128 139,128 L278,128 Q286,128 286,136 L286,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #4 · DATA</title></path><path class="edge DATA" id="e8i1" d="M104,222 L104,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #6 · DATA</title></path><path class="edge DATA" id="e8i2" d="M256,222 L256,227 Q256,232 251,232 L142,232 Q134,232 134,240 L134,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge DATA" id="e9i1" d="M104,326 L104,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #8 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(74,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id">  #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start
+Type not computed
+
+</title></g><g class="node" id="n4" data-id="4" transform="translate(74,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="n6" data-id="6" transform="translate(44,172)" 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">  #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 *
+Type not computed
+
+[0] → — DATA
+[1] → #4 DATA
+[2] → #4 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n7" data-id="7" transform="translate(196,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>*</tspan><tspan class="node-id">  #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 *
+Type not computed
+
+[0] → — DATA
+[1] → #4 DATA
+[2] → #4 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n8" data-id="8" transform="translate(44,276)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>-</tspan><tspan class="node-id">  #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 -
+Type not computed
+
+[0] → — DATA
+[1] → #6 DATA
+[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(24,380)" 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">  #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 Return
+Type not computed
+
+[0] → — CTRL
+[1] → #8 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg>
diff --git a/docs/chapter09/09-graph4.gv b/docs/chapter09/09-graph4.gv
new file mode 100644
index 00000000..8886f73a
--- /dev/null
+++ b/docs/chapter09/09-graph4.gv
@@ -0,0 +1,29 @@
+digraph chapter09 {
+/*
+return arg*arg-arg*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></TR>
+ </TABLE>
+ </TD></TR>
+ </TABLE>>
+ ];
+ Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ];
+ Con_9 [ label="#0" ];
+ Return10 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ }
+ edge [ fontname=Helvetica, fontsize=8 ];
+ Stop3 -> Return10[taillabel=0 color=red];
+ Return10 -> Start2:p0[taillabel=0 color=red];
+ Return10 -> Con_9[taillabel=1];
+}
diff --git a/docs/chapter09/09-graph4.json b/docs/chapter09/09-graph4.json
new file mode 100644
index 00000000..1282e87e
--- /dev/null
+++ b/docs/chapter09/09-graph4.json
@@ -0,0 +1,13 @@
+{
+ "ver": 1,
+ "comp": "chapter09/docs/09-graph4.svg",
+ "step": 1,
+ "roots": [10],
+ "scope": 0,
+ "nodes": [
+ {"id": 9, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null}
+ ],
+ "groups": [
+ ]
+}
diff --git a/docs/chapter09/09-graph4.svg b/docs/chapter09/09-graph4.svg
new file mode 100644
index 00000000..3c49a48a
--- /dev/null
+++ b/docs/chapter09/09-graph4.svg
@@ -0,0 +1,70 @@
+<svg aria-label="Compiler graph" width="188" height="202" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 188 202" style="font-family: sans-serif;"><style>
+ html, body { height:100%; margin:0; font-family:sans-serif; }
+ .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; }
+ .source { padding:8px; border-bottom:1px solid #ccc; }
+ #program { width:min(600px,80vw); vertical-align:middle; }
+ #status { margin-top:4px; }
+ #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; }
+ #elk { width:100%; height:100%; }
+ #graph svg { display:block; }
+ .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; }
+ .hint { color:#616c78; }
+ .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; }
+ .edge { fill:none; stroke-width:1.5; }
+ .edge.CTRL { stroke-width:2; }
+ .edge.ASSOC { stroke-dasharray:4 4; }
+ .edge.PARSER { stroke-dasharray:5 4; }
+ .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; }
+ .edge.selected { stroke-width:3.5; }
+ .edge.bundle { stroke-width:4; }
+ .edge.bundle.selected { stroke-width:6; }
+ .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; }
+ .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; }
+ .node { cursor:pointer; }
+ .box { stroke:#758191; stroke-width:1; }
+ .node.held .box { stroke-dasharray:5 3; }
+ .node.near .box { stroke:#c18221; stroke-width:2; }
+ .node.focus .box { stroke:#9c4900; stroke-width:3; }
+ .node.selected .box { stroke:#1569b9; stroke-width:3; }
+ .node.folded .box { stroke-width:4; }
+ .node.folding .box { fill:#f4ccd7; }
+ .fold-tag { font-size:9px; font-weight:700; fill:#963751; }
+ .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; }
+ .node.peep-edit .box { stroke:#9c4900; stroke-width:3; }
+ .node.error .box { stroke:#b42318; stroke-width:4; }
+ #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; }
+ .peep-ghosts { pointer-events:none; }
+ .region-box { stroke:#9da9b8; stroke-width:1.5; }
+ .fold-btn { cursor:pointer; }
+ .fold-btn rect { fill:white; stroke:#596674; }
+ .fold-btn text { font-size:14px; fill:#152330; }
+ .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; }
+ .shortcut { cursor:pointer; }
+ .shortcut path { fill:none; stroke-width:1.5; }
+ .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; }
+ .shortcut text { font-size:11px; fill:#783030; }
+ .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; }
+ .label { font-size:12px; fill:#152330; font-weight:600; }
+ .node-id { font-size:10px; fill:#596674; font-weight:400; }
+ .type { font-size:11px; fill:#455768; }
+ .port { stroke:#536477; stroke-width:1; }
+ .row { stroke:#b6afcf; stroke-width:1; }
+ .bind { font-size:12px; fill:#152330; }
+ .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; }
+ #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px;
+ max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere;
+ background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; }
+ .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; }
+ .button { color:white; background:black; font-size:20px; min-width:30px; }
+ .button:disabled { background:grey; }
+ .count { font-size:20px; min-width:35px; text-align:center; }
+ #N { width:6ch; }
+ #scrub { width:clamp(120px,35vw,600px); }
+ </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e10i1" d="M104,74 L104,122" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[1] → #9 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n9" data-id="9" transform="translate(44,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>#0</tspan><tspan class="node-id">  #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 #0
+Type not computed
+
+</title></g><g class="node" id="n10" data-id="10" transform="translate(24,128)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id">  #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 Return
+Type not computed
+
+[0] → — CTRL
+[1] → #9 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg>
diff --git a/docs/chapter09/09-graph5.gv b/docs/chapter09/09-graph5.gv
new file mode 100644
index 00000000..72274239
--- /dev/null
+++ b/docs/chapter09/09-graph5.gv
@@ -0,0 +1,63 @@
+digraph chapter09 {
+/*
+int step = 1;
+while (arg < 10) {
+ arg = arg + step + 1;
+}
+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" ];
+ Con_6 [ label="#1" ];
+ Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ];
+ Phi_arg9 [ style=filled fillcolor=lightyellow label="&phi;_arg" ];
+ LT10 [ label="<" ];
+ Con_11 [ label="#10" ];
+ If12 [ 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>>
+ ];
+ Add16 [ label="+" ];
+ Add18 [ label="+" ];
+ Return21 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ { rank=same; Loop7;Phi_arg9;}
+ }
+ edge [ fontname=Helvetica, fontsize=8 ];
+ Stop3 -> Return21[taillabel=0 color=red];
+ Loop7 -> Start2:p0[taillabel=1 color=red];
+ Loop7 -> If12:p0[taillabel=2 color=red constraint=false];
+ Phi_arg9 -> Loop7 [style=dotted taillabel=0];
+ Phi_arg9 -> Start2:p1[taillabel=1];
+ Phi_arg9 -> Add18[taillabel=2 constraint=false];
+ LT10 -> Phi_arg9[taillabel=1];
+ LT10 -> Con_11[taillabel=2];
+ If12 -> Loop7[taillabel=0 color=red];
+ If12 -> LT10[taillabel=1];
+ Add16 -> Con_6[taillabel=1];
+ Add16 -> Phi_arg9[taillabel=2];
+ Add18 -> Add16[taillabel=1];
+ Add18 -> Con_6[taillabel=2];
+ Return21 -> If12:p1[taillabel=0 color=red];
+ Return21 -> Phi_arg9[taillabel=1];
+}
diff --git a/docs/chapter09/09-graph5.json b/docs/chapter09/09-graph5.json
new file mode 100644
index 00000000..ff52950d
--- /dev/null
+++ b/docs/chapter09/09-graph5.json
@@ -0,0 +1,18 @@
+{
+ "ver": 1,
+ "comp": "chapter09/docs/09-graph5.svg",
+ "step": 1,
+ "roots": [21],
+ "scope": 0,
+ "nodes": [
+ {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "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": 6, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 9, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null, "backedge": true}], "proj": null},
+ {"id": 16, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "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": 6, "role": "DATA", "label": null}], "proj": null},
+ {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null}
+ ],
+ "groups": [
+ ]
+}
diff --git a/docs/chapter09/09-graph5.svg b/docs/chapter09/09-graph5.svg
new file mode 100644
index 00000000..bbaf2227
--- /dev/null
+++ b/docs/chapter09/09-graph5.svg
@@ -0,0 +1,92 @@
+<svg aria-label="Compiler graph" width="402" height="464" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 402 464" style="font-family: sans-serif;"><style>
+ html, body { height:100%; margin:0; font-family:sans-serif; }
+ .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; }
+ .source { padding:8px; border-bottom:1px solid #ccc; }
+ #program { width:min(600px,80vw); vertical-align:middle; }
+ #status { margin-top:4px; }
+ #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; }
+ #elk { width:100%; height:100%; }
+ #graph svg { display:block; }
+ .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; }
+ .hint { color:#616c78; }
+ .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; }
+ .edge { fill:none; stroke-width:1.5; }
+ .edge.CTRL { stroke-width:2; }
+ .edge.ASSOC { stroke-dasharray:4 4; }
+ .edge.PARSER { stroke-dasharray:5 4; }
+ .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; }
+ .edge.selected { stroke-width:3.5; }
+ .edge.bundle { stroke-width:4; }
+ .edge.bundle.selected { stroke-width:6; }
+ .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; }
+ .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; }
+ .node { cursor:pointer; }
+ .box { stroke:#758191; stroke-width:1; }
+ .node.held .box { stroke-dasharray:5 3; }
+ .node.near .box { stroke:#c18221; stroke-width:2; }
+ .node.focus .box { stroke:#9c4900; stroke-width:3; }
+ .node.selected .box { stroke:#1569b9; stroke-width:3; }
+ .node.folded .box { stroke-width:4; }
+ .node.folding .box { fill:#f4ccd7; }
+ .fold-tag { font-size:9px; font-weight:700; fill:#963751; }
+ .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; }
+ .node.peep-edit .box { stroke:#9c4900; stroke-width:3; }
+ .node.error .box { stroke:#b42318; stroke-width:4; }
+ #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; }
+ .peep-ghosts { pointer-events:none; }
+ .region-box { stroke:#9da9b8; stroke-width:1.5; }
+ .fold-btn { cursor:pointer; }
+ .fold-btn rect { fill:white; stroke:#596674; }
+ .fold-btn text { font-size:14px; fill:#152330; }
+ .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; }
+ .shortcut { cursor:pointer; }
+ .shortcut path { fill:none; stroke-width:1.5; }
+ .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; }
+ .shortcut text { font-size:11px; fill:#783030; }
+ .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; }
+ .label { font-size:12px; fill:#152330; font-weight:600; }
+ .node-id { font-size:10px; fill:#596674; font-weight:400; }
+ .type { font-size:11px; fill:#455768; }
+ .port { stroke:#536477; stroke-width:1; }
+ .row { stroke:#b6afcf; stroke-width:1; }
+ .bind { font-size:12px; fill:#152330; }
+ .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; }
+ #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px;
+ max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere;
+ background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; }
+ .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; }
+ .button { color:white; background:black; font-size:20px; min-width:30px; }
+ .button:disabled { background:grey; }
+ .count { font-size:20px; min-width:35px; text-align:center; }
+ #N { width:6ch; }
+ #scrub { width:clamp(120px,35vw,600px); }
+ </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e9i1" d="M287,118 L287,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #4 · DATA</title></path><path class="edge DATA" id="e9i2" d="M155,430 L155,435 Q155,440 160,440 L369,440 Q377,440 377,432 L377,136 Q377,128 369,128 L335,128 Q327,128 327,136 L327,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[2] → #18 · DATA</title></path><path class="edge DATA" id="e16i1" d="M84,222 L84,227 Q84,232 89,232 L147,232 Q155,232 155,240 L155,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #6 · DATA</title></path><path class="edge DATA" id="e16i2" d="M307,222 L307,227 Q307,232 302,232 L193,232 Q185,232 185,240 L185,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[2] → #9 · DATA</title></path><path class="edge DATA" id="e18i1" d="M155,326 L155,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #16 · DATA</title></path><path class="edge DATA" id="e18i2" d="M84,222 L84,328 Q84,336 92,336 L177,336 Q185,336 185,344 L185,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #6 · DATA</title></path><path class="edge DATA" id="e21i1" d="M307,222 L307,227 Q307,232 312,232 L319,232 Q327,232 327,240 L327,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#21[1] → #9 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(227,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id">  #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start
+Type not computed
+
+</title></g><g class="node" id="n4" data-id="4" transform="translate(227,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="n6" data-id="6" transform="translate(24,172)" 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">  #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #1
+Type not computed
+
+</title></g><g class="node" id="n9" data-id="9" transform="translate(247,172)" 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">  #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 φ_arg
+Type not computed
+
+[0] → — ASSOC
+[1] → #4 DATA
+[2] → #18 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><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="0" y="-10" 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="n16" data-id="16" transform="translate(95,276)" 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] → #6 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="n18" data-id="18" transform="translate(95,380)" 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] → #6 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n21" data-id="21" transform="translate(247,276)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id">  #21</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#21 Return
+Type not computed
+
+[0] → — CTRL
+[1] → #9 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg>
diff --git a/docs/chapter09/09-graph6.gv b/docs/chapter09/09-graph6.gv
new file mode 100644
index 00000000..56dc6ada
--- /dev/null
+++ b/docs/chapter09/09-graph6.gv
@@ -0,0 +1,60 @@
+digraph chapter09 {
+/*
+int step = 1;
+while (arg < 10) {
+ arg = arg + step + 1;
+}
+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" ];
+ Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ];
+ Phi_arg9 [ style=filled fillcolor=lightyellow label="&phi;_arg" ];
+ LT10 [ label="<" ];
+ Con_11 [ label="#10" ];
+ If12 [ 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>>
+ ];
+ Return21 [ shape=box style=filled fillcolor=yellow label="Return" ];
+ Con_24 [ label="#2" ];
+ Add25 [ label="+" ];
+ { rank=same; Loop7;Phi_arg9;}
+ }
+ edge [ fontname=Helvetica, fontsize=8 ];
+ Stop3 -> Return21[taillabel=0 color=red];
+ Loop7 -> Start2:p0[taillabel=1 color=red];
+ Loop7 -> If12:p0[taillabel=2 color=red constraint=false];
+ Phi_arg9 -> Loop7 [style=dotted taillabel=0];
+ Phi_arg9 -> Start2:p1[taillabel=1];
+ Phi_arg9 -> Add25[taillabel=2 constraint=false];
+ LT10 -> Phi_arg9[taillabel=1];
+ LT10 -> Con_11[taillabel=2];
+ If12 -> Loop7[taillabel=0 color=red];
+ If12 -> LT10[taillabel=1];
+ Return21 -> If12:p1[taillabel=0 color=red];
+ Return21 -> Phi_arg9[taillabel=1];
+ Add25 -> Phi_arg9[taillabel=1];
+ Add25 -> Con_24[taillabel=2];
+}
diff --git a/docs/chapter09/09-graph6.json b/docs/chapter09/09-graph6.json
new file mode 100644
index 00000000..5b511bd1
--- /dev/null
+++ b/docs/chapter09/09-graph6.json
@@ -0,0 +1,17 @@
+{
+ "ver": 1,
+ "comp": "chapter09/docs/09-graph6.svg",
+ "step": 1,
+ "roots": [21],
+ "scope": 0,
+ "nodes": [
+ {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "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": 9, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 25, "role": "DATA", "label": null, "backedge": true}], "proj": null},
+ {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null},
+ {"id": 24, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null},
+ {"id": 25, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null}
+ ],
+ "groups": [
+ ]
+}
diff --git a/docs/chapter09/09-graph6.svg b/docs/chapter09/09-graph6.svg
new file mode 100644
index 00000000..b573d88a
--- /dev/null
+++ b/docs/chapter09/09-graph6.svg
@@ -0,0 +1,87 @@
+<svg aria-label="Compiler graph" width="350" height="360" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 350 360" style="font-family: sans-serif;"><style>
+ html, body { height:100%; margin:0; font-family:sans-serif; }
+ .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; }
+ .source { padding:8px; border-bottom:1px solid #ccc; }
+ #program { width:min(600px,80vw); vertical-align:middle; }
+ #status { margin-top:4px; }
+ #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; }
+ #elk { width:100%; height:100%; }
+ #graph svg { display:block; }
+ .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; }
+ .hint { color:#616c78; }
+ .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; }
+ .edge { fill:none; stroke-width:1.5; }
+ .edge.CTRL { stroke-width:2; }
+ .edge.ASSOC { stroke-dasharray:4 4; }
+ .edge.PARSER { stroke-dasharray:5 4; }
+ .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; }
+ .edge.selected { stroke-width:3.5; }
+ .edge.bundle { stroke-width:4; }
+ .edge.bundle.selected { stroke-width:6; }
+ .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; }
+ .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; }
+ .node { cursor:pointer; }
+ .box { stroke:#758191; stroke-width:1; }
+ .node.held .box { stroke-dasharray:5 3; }
+ .node.near .box { stroke:#c18221; stroke-width:2; }
+ .node.focus .box { stroke:#9c4900; stroke-width:3; }
+ .node.selected .box { stroke:#1569b9; stroke-width:3; }
+ .node.folded .box { stroke-width:4; }
+ .node.folding .box { fill:#f4ccd7; }
+ .fold-tag { font-size:9px; font-weight:700; fill:#963751; }
+ .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; }
+ .node.peep-edit .box { stroke:#9c4900; stroke-width:3; }
+ .node.error .box { stroke:#b42318; stroke-width:4; }
+ #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; }
+ .peep-ghosts { pointer-events:none; }
+ .region-box { stroke:#9da9b8; stroke-width:1.5; }
+ .fold-btn { cursor:pointer; }
+ .fold-btn rect { fill:white; stroke:#596674; }
+ .fold-btn text { font-size:14px; fill:#152330; }
+ .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; }
+ .shortcut { cursor:pointer; }
+ .shortcut path { fill:none; stroke-width:1.5; }
+ .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; }
+ .shortcut text { font-size:11px; fill:#783030; }
+ .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; }
+ .label { font-size:12px; fill:#152330; font-weight:600; }
+ .node-id { font-size:10px; fill:#596674; font-weight:400; }
+ .type { font-size:11px; fill:#455768; }
+ .port { stroke:#536477; stroke-width:1; }
+ .row { stroke:#b6afcf; stroke-width:1; }
+ .bind { font-size:12px; fill:#152330; }
+ .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; }
+ #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px;
+ max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere;
+ background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; }
+ .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; }
+ .button { color:white; background:black; font-size:20px; min-width:30px; }
+ .button:disabled { background:grey; }
+ .count { font-size:20px; min-width:35px; text-align:center; }
+ #N { width:6ch; }
+ #scrub { width:clamp(120px,35vw,600px); }
+ </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e9i1" d="M84,118 L84,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #4 · DATA</title></path><path class="edge DATA" id="e9i2" d="M236,326 L236,331 Q236,336 241,336 L318,336 Q326,336 326,328 L326,136 Q326,128 318,128 L132,128 Q124,128 124,136 L124,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[2] → #25 · DATA</title></path><path class="edge DATA" id="e21i1" d="M104,222 L104,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#21[1] → #9 · DATA</title></path><path class="edge DATA" id="e25i1" d="M104,222 L104,227 Q104,232 109,232 L228,232 Q236,232 236,240 L236,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#25[1] → #9 · DATA</title></path><path class="edge DATA" id="e25i2" d="M256,222 L256,227 Q256,232 261,232 L261,232 Q266,232 266,237 L266,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#25[2] → #24 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(24,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id">  #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start
+Type not computed
+
+</title></g><g class="node" id="n4" data-id="4" transform="translate(24,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="n9" data-id="9" transform="translate(44,172)" 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">  #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 φ_arg
+Type not computed
+
+[0] → — ASSOC
+[1] → #4 DATA
+[2] → #25 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><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="0" y="-10" 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="n21" data-id="21" transform="translate(24,276)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id">  #21</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#21 Return
+Type not computed
+
+[0] → — CTRL
+[1] → #9 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g><g class="node" id="n24" data-id="24" transform="translate(196,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id">  #24</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#24 #2
+Type not computed
+
+</title></g><g class="node" id="n25" data-id="25" transform="translate(176,276)" 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">  #25</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#25 +
+Type not computed
+
+[0] → — DATA
+[1] → #9 DATA
+[2] → #24 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg>
diff --git a/docs/chapter09/Makefile b/docs/chapter09/Makefile
new file mode 100644
index 00000000..6fa0f057
--- /dev/null
+++ b/docs/chapter09/Makefile
@@ -0,0 +1 @@
+include ../../graph/docs.mk
diff --git a/docs/chapter09/README.ja.md b/docs/chapter09/README.ja.md
new file mode 100644
index 00000000..79da0150
--- /dev/null
+++ b/docs/chapter09/README.ja.md
@@ -0,0 +1,190 @@
+# 第9章: 大域的値番号付けと反復的なピープホール最適化
+
+[English](README.md) | 日本語
+
+この文書は [原文](README.md) の日本語訳です。
+
+[前の章: 第8章](../chapter08/README.ja.md) |
+[次の章: 第10章](../chapter10/README.ja.md)
+
+文法は[第8章](../chapter08/08-grammar.ja.md)から変わりません。
+
+# 目次
+
+1. [ピープホール最適化の基盤づくり](#ピープホール最適化の基盤づくり)
+2. [大域的値番号付け](#大域的値番号付け)
+3. [解析後の反復的なピープホール最適化](#解析後の反復的なピープホール最適化)
+4. [遠くの隣接ノード](#遠くの隣接ノード)
+5. [今後の課題](#今後の課題)
+6. [GVN による共通部分式](#gvn-による共通部分式)
+ - [例1](#例1)
+ - [例2](#例2)
+7. [解析後の反復最適化](#解析後の反復最適化)
+
+[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter09) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter08...linear-chapter09) することもできます。
+
+この章では次のことを行います。
+
+* 大域的値番号付け（共通部分式除去）を追加します。
+* 解析後にピープホール最適化を不動点まで反復する最適化を追加します。
+
+この章に言語の変更はなく、最適化だけを追加します。
+
+## ピープホール最適化の基盤づくり
+
+第9章の目標は、ピープホール最適化を「仕上げる」ことです。これ以上ピープホール最適化が登場しないという意味ではありません。むしろ、今後もたくさん登場します。ここで作るのは、それらを整理し、安全で扱いやすく実装し、不動点に到達するまで適用するための基盤です。
+
+本当の目標は、新しいピープホール最適化を恐れずに追加できるようにすることです。間違っていれば、すぐにアサーションで失敗します。正しければ、新しい最適化はほかのすべての最適化と一緒に動き、お互いに効果を高め合います。
+
+## 大域的値番号付け
+
+大域的値番号付け（GVN）は、従来のハッシュテーブルを使い、ノードのオペコードと入力からハッシュを計算します。2つのノードが同じ入力に同じ処理を行うなら、結果も同じなので、共有できます。
+
+* Node にグローバルな静的ハッシュテーブル `GVN` を追加します。
+* `Node.equals` を追加します。2つのノードは、同じ入力に対し同じオペコード、すなわち同じ Java クラスを持つ場合に等価です。
+* ノードのオペコード（代用としてノード名の文字列）と入力に基づく `hashCode` を追加します。
+* `ConstantNode` などいくつかのノードでは、追加の固有情報が必要です。定数17と99は同じではありませんが、どちらも同じ `ConstantNode` クラスとラベルを持ちます。`eq` と `hash` は、この追加情報を確認（またはハッシュ化）します。
+
+ここでは意図的に *値の等価性* を使っていることに注意してください。Simple の多くの箇所では *参照の等価性* を使います。たとえば、ノードとエッジの管理は値の等価性ではなく参照の等価性で行い、`Utils.find()` も参照で検索します。Simple プロジェクト全体で、ノードを検索するときは、それが *値の等価性* か *参照の等価性* かに注意してください。常に明示されているわけではありませんが、文脈から明らかであるはずです。
+
+グラフは頻繁に編集するため、ノードの入力が変わることがあります。それによってハッシュも変わるので、GVN テーブル内で見つからなくなります。たとえば、次の `Add` を `Con` に置き換える場合です。
+
+ (Mul (Add 4 8) x) // Fold the constant
+ (Mul 12 x) // The `Mul` changes hash and inputs
+
+対策として、エッジを変更するときにはノードが `GVN` テーブルに存在していないことを要求します。何らかの「エッジのロック」が必要です。「エッジがロックされている」なら、エッジの変更前にまずノードを `GVN` から取り除く必要があります。
+
+* `_hash` フィールドを、キャッシュされたハッシュコードとエッジのロックの両方に使います。0ならノードはロックされておらず、`GVN` にもありません。0以外ならノードの「エッジがロックされており」、`GVN` に存在します。
+* `hashCode` 関数はキャッシュされたハッシュがあれば使い、偶然ハッシュが0になることは許しません。
+* エッジを変更する前にノードを `GVN` から取り除く `unlock()` を追加します。ノードのエッジを操作するすべての呼び出しの前に挿入します。エッジを変更するすべてのコード経路は、すでにノードを再度ピープホール最適化することを保証しているため、その再訪時にノードを `GVN` テーブルへ再挿入します。
+
+この新しい `GVN` テーブルは、`peepholeOpt()`（および `peephole()`）で、ピープホール最適化するすべてのノードについて共通部分式を探すために使います。ノードのハッシュが0なら、以前の同一ノードとの一致を探します。見つかれば、その以前のノードを使い、現在のノードはデッドコード除去で削除します。見つからなければ、現在のノードを「代表インスタンス」として `GVN` に挿入します。ノードのハッシュがすでに0以外なら、それが「代表インスタンス」だとわかるので、`GVN` を検索する必要はありません。
+
+この最適化全体は、`iter()` の十数行と、共有の `equals`、`hashCode`（コメントを含めてさらに約50行）で実現できます。
+
+不変条件の1つは、ピープホール最適化の実行中に型が単調に上がることです。GVN はこれを一時的に破る場合があります。2つの等価なノードのうち、一方の `_type` はすでに引き上げられ、もう一方はまだかもしれません。どちらを残すかによって、「より低い」`_type` のノードを選ぶ可能性があります。この「低い」は、型の束における意味です。両方の型が正しい必要があり、両ノードの `compute()` は同じ型を返さなければなりません。その型は JOIN に等しい必要があります。対策は、2つのノードの型について（MEET ではなく）JOIN を計算することです。
+
+## 解析後の反復的なピープホール最適化
+
+解析後の `IterPeeps` は、ピープホール最適化を不動点、すなわち適用できる最適化がなくなるまで反復します。ピープホール最適化がコードサイズを増やすことはまれ（まったくない？）なので、これは線形時間になるはずです。グラフは何らかの尺度、通常はサイズについて単調に小さくなるはずです。MulNode やロード/ストアノードの数などが減り、より「高価な」ノードを安価なノードに置き換える場合もあります。
+
+理論上、ワークリストの処理は単純です。次の項目を取って処理します。グラフが変わったら、隣接ノードをワークリストに入れます。この手順を、ワークリストが空になるまで繰り返します。
+
+扱う必要のある主な問題は次のとおりです。
+
+* ノードには利用側があります。あるノード群を別のものに置き換えるには、さらにグラフを組み替える必要があります。高度に難しいわけではありませんが、細かな扱いが面倒です。少数のグラフ操作ユーティリティと、ピープホール最適化の間ではグラフが安定し正しいという強い不変条件が役に立ちます。ここでは、従来の安定したノードのユーティリティを基に、`Node.subsume` が操作の大部分を行います。
+* ノードの変更は、グラフの「近傍」も変えます。隣接ノードにもピープホール最適化を適用できるか確認し、その先にも同様に続ける必要があります。ピープホール最適化やグラフ更新の後では、ノードの利用側と定義側をワークリストに入れます。
+* 強い不変条件は、すべてのノードについて、ワークリスト上にあるか、適用できるピープホール最適化がないか、のどちらかであることです。確認は簡単ですが、高コストです。通常の「不動点までのピープホール最適化の反復」は基本的に線形時間ですが、この確認は各最適化ステップで線形時間なので、全体では二次時間になります。便利なアサーションですが、アルゴリズム全体が安定したら無効にし、新しく追加したピープホール最適化が誤動作するときに再び有効にできます。このコードは `IterPeeps.iterate` の `assert progressOnList(stop);` として有効になっています。
+
+## 遠くの隣接ノード
+
+一部のピープホール最適化では、「近傍」は直接の利用側や定義側より遠くまで及びます。そのため、より長距離の関係を扱う方法が必要です。たとえば、ある最適化が「this -> A -> B -> C」を調べ、自身を「D」に置き換えようとしても、「B」の何らかの判定で失敗する場合があります。「B」が更新されたら、「this」を再訪し、ピープホール最適化を再確認したいはずです。そこで、「B」に「this」の依存関係を記録します。「B」の更新時に、依存リスト（「this」）を「処理待ち」リストへ追加します。
+
+遠くの隣接ノードの確認の例が `AddNode` にあります。`(Add (Add x 2) 1)` という重なった定数を探し、`(Add x 3)` にしたいとします。調べた結果、代わりに `(Add (Phi (Add x 2) self) 1)` が見つかったとします。`Phi` は `Add` ではないため、当然この確認はそこで打ち切られます。しかし、`(Phi y self)` は一意な入力を1つしか持たず、いずれそれ自体が `y` にピープホール最適化されます。そうなれば、重なった `Add` の最適化を適用できます。そこで、失敗した Add の最適化は `phi.addDep(Add)` を呼び、`Phi` への依存を登録します。実際に後で `Phi` が最適化されたら、その依存ノード（たとえば `Add`）を `IterPeeps` のワークリストへ戻し、重なった Add の最適化を再試行します。
+
+一般的な規則は次のとおりです。
+
+* **ピープホール最適化のパターンが遠くのノードを調べるなら、依存リストに登録しなければなりません！**
+* `node.in(1).in(2)` を `node.in(1).in(2).addDep(node)` にします。
+
+この章では、次のパターンでこれを使います。
+
+* 一部の最適化は `Phi` の入力と関係します。直接の場合も間接の場合もあり、たとえば `(Add Add( (Phi x) 2 ) 1)` です。`Phi` の入力がすべて `Constant` なら最適化を進められるため、そのノードを `Phi` の入力の依存側にします。また、`Phi` の Region の依存側にもします。`Node.allCons()` と `PhiNode.allCons()` を参照してください。
+* `(Add (Add x 1) 2)` のパターンでは、`x` が定数になれば処理が進むため、外側の `Add` を `x` の依存側として追加します。`AddNode.idealize()` を参照してください。
+* `Phi` の型を計算するとき、対応する Region の該当する制御が生きていれば、`Phi` を Region の制御入力の依存側として追加します。その制御が死ねば、`Phi` にピープホール最適化を適用できるからです。`PhiNode.compute()` と `PhiNode.singleUniqueInput()` を参照してください。
+
+変更点:
+
+* Node に `ArrayList<Node> _deps` フィールドを追加します。初期値は null です。
+* 一部のピープホール最適化（上記参照）は、遠くのノードの確認に失敗したら `distant.addDep(this)` を呼び、依存を追加します。`addDep` は `_deps` を作り、各種の重複した追加を除外します。
+* `IterPeeps` のループは、変更を見つけたら、依存側もすべてワークリストへ移します。
+
+# 例
+
+## GVN による共通部分式
+
+これらの図は値の依存関係に焦点を当てています。通常の制御フローは省略しています。最初の例では、小さな True/False の射影で2つの Return を区別します。空の制御スロットは、コンパイラの入力の欠如ではなく、省略した文脈を表す場合があります。
+
+### 例1
+
+GVN がどのように共通部分式を見つけるかを示す小さな例です。
+
+```java
+int x = arg + arg;
+if(arg < 10) {
+ return arg + arg;
+}
+else {
+ x = x + 1;
+}
+return x;
+```
+
+GVN を使う前には、次のグラフになります。`arg+arg` を `arg*2` に変換していることに注目してください。
+
+![グラフ1](./09-graph1.svg)
+
+GVN を追加すると、次のようになります。`arg*2` の式が2回現れる代わりに、再利用されるようになったことに注目してください。
+
+![グラフ2](./09-graph2.svg)
+
+### 例2
+
+共通の式を再利用できると、さらに最適化が可能になります。単純な例を示します。
+
+```java
+return arg*arg-arg*arg;
+```
+
+GVN がなければ、ピープホール最適化は減算の両辺が同じ値だと認識できません。
+
+![グラフ3](./09-graph3.svg)
+
+* 各乗算（*）ノードは、`arg` に向かうエッジを2本持ちます。
+* 入力スロットのラベルが、同じ定義を使うこの2つの使用を区別します。
+
+GVN があれば、ピープホール最適化はよりよい結果を得られます。
+
+![グラフ4](./09-graph4.svg)
+
+## 解析後の反復最適化
+
+ワークリストに基づく解析後の最適化は、解析中にはできなかった最適化を可能にします。たとえば、次のコードです。
+
+```java
+int step = 1;
+while (arg < 10) {
+ arg = arg + step + 1;
+}
+return arg;
+```
+
+`while` ループの解析中には、`step` が定数で、変化しないことはまだわかりません。そのため、解析後の最適化がなければ次のようになります。
+
+両方の図で、ループの判定と制御のバックエッジは省略しています。Phi のデータのバックエッジは残しているため、繰り返される加算とその置き換えを比較しやすくなっています。その入力1は入口の値、入力2は次の反復の値です。
+
+![グラフ5](./09-graph5.svg)
+
+解析後のワークリストに基づく最適化を有効にすると、次のようになります。グラフのループ本体内に `arg+2` が現れたことに注目してください。
+
+![グラフ6](./09-graph6.svg)
+
+## 今後の課題
+
+後の章で扱いたい問題がさらにあります。
+
+* 順序を考えずにピープホール最適化を実行すると、いくつかの欠点があります。
+ - 死んでいるものや、もうすぐ死ぬものを最適化してから削除する場合があります。無駄な処理です。
+ - 死んだ無限ループは、ピープホール最適化の無限の循環を引き起こすことがよくあります。死んだループの「根元」を処理すれば、全体を畳み込めるのに、そこに到達できません。
+ - 一部の最適化はグラフを直接小さくします。ほかの最適化はサイズを保ったまま別のものを減らします（たとえば2倍の Mul を Shift に置き換える場合）。さらに、簡約する前に一時的にグラフを大きくしようとする最適化も出てくるかもしれません。
+* したがって、まずグラフを直接小さくする最適化（デッドコード除去など）を行い、次に別のものを減らす最適化を行い、最後にそれ以外を行うことには利点があります。これはソートされたワークリストを意味しますが、順序の種類はごく限られるため、基数ソートだけで十分です。ピープホール最適化を、たとえば次のような分類に分ける必要があります。
+ - 「厳密に小さくする」もの。
+ - 「ノード数は同じだが、たとえば `Mul` を `Shift` に置き換える」もの。
+ - 自由度を増やすもの（エッジの迂回）。
+ - 「後で小さくなるため、今は大きくする」もの（インライン化はこの分類です）。
+* リストのどちらかの端から常に取り出すのを避ける利点もあります。一方または他方の端から処理すると、多くの最適化パターンが二次時間になるかもしれません。何かを変更してリストに戻すと、それがすぐに再び取り出されるためです。つまり、同じ最適化を繰り返すループに陥り、たとえば左側に連なる加算木を、少しずつ右側に連なる加算木に移すことになります。擬似ランダムな取り出しは、ランダム化によって悪い最適化パターンを避けます。
+* なぜ `IterPeeps` は、`addDeps` の仕組みを備えたワークリストを使う代わりに、全ノードを1回か2回走査するだけではないのでしょうか。定義側を利用側より先に訪問する順序（たとえば逆後順）で巡回することさえできます。
+
+ ループがなければ、そのような1回の走査で局所的なピープホール最適化をすべて見つけられます。実際、パーサーはすでにこれを行っています。しかし、ループやさらに遠くのケースでの機会は見つけられません。ループ周辺の最適化を得るには、再訪が必要です。各回 O(N) のコストで O(N) 回の走査を必要とするケースは簡単に作れ、アルゴリズムはすぐに二次時間になります。
+
+ `addDeps` の解法は、ピープホール最適化を書く際のコストをいくらか増やす代わりに、この二次時間のコストを避けます。
diff --git a/docs/chapter09/README.md b/docs/chapter09/README.md
new file mode 100644
index 00000000..338df612
--- /dev/null
+++ b/docs/chapter09/README.md
@@ -0,0 +1,314 @@
+# Chapter 9: Global Value Numbering and Iterative Peepholes
+
+English | [日本語](README.ja.md)
+
+[Previous: Chapter 8](../chapter08/README.md) |
+[Next: Chapter 10](../chapter10/README.md)
+
+The grammar is unchanged from [Chapter 8](../chapter08/08-grammar.md).
+
+# Table of Contents
+
+1. [Engineering Peepholes](#engineering-peepholes)
+2. [Global Value Numbering](#global-value-numbering)
+3. [Post-Parse Iterative Peepholes](#post-parse-iterative-peepholes)
+4. [Distant Neighbors](#distant-neighbors)
+5. [Future Work](#future-work)
+6. [Common SubExpressions via GVN](#common-subexpressions-via-gvn)
+ - [Example 1](#example-1)
+ - [Example 2](#example-2)
+7. [Post Parse Iterative Optimizations](#post-parse-iterative-optimizations)
+
+You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter09) 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-chapter08...linear-chapter09) it to the previous chapter.
+
+In this chapter:
+
+* We add Global Value Numbering (Common Subexpression Elimination)
+* We add a post-parse iterate-peepholes-to-fixed-point optimization
+
+No language changes in this chapter, just adding optimizations.
+
+
+## Engineering Peepholes
+
+The goal for Ch 9 is to "finish out" the Peepholes. Not that no more peeps will
+appear, on the contrary lots will - but this is the infrastructure to organize
+them, engineer them safe and sane; to apply them until a fixed point is reached.
+
+Really the goal here is to be fearless about adding a new peephole; if you got
+it wrong you'll assert pretty fast. If you got it right, that new peep will
+just run alongside all the others and they will all mutually benefit each other.
+
+
+## Global Value Numbering
+
+Global Value Numbering works via a classic hash table, hashing on a Node's
+opcode and inputs. If two Nodes do the same function on the same inputs, they
+get the same result - and can be shared.
+
+* We add a global static hash table `GVN` in Node.
+* We add a `Node.equals` call. Two Nodes are equal if they have the same
+ opcode - same Java class - on the same inputs.
+* We add a `hashCode` on the Node opcode (proxy: Node string name) and inputs.
+* `ConstantNode` and a few others need some extra custom bits here: the
+ constant 17 is not the same as 99, but both are the same `ConstantNode` class
+ and label. The `eq` and `hash` calls check (or hash) these extra bits.
+
+Note the intentional *value* equality here. In many places in Simple we use
+*reference* equality - e.g. node/edge maintenance is via reference equality, not
+value equality, so e.g. the `Utils.find()` call finds via reference. Throughout the Simple project whenever a Node lookup is happening, beware if it's via
+*value* or *reference* equality; this is not always explicitly called out but
+should be obvious from context.
+
+
+Since we edit the graph a lot, Nodes can have their inputs change which changes
+their hash which means they can't be found in the GVN table. E.g. we swap out
+the `Add` for a `Con` in:
+
+ (Mul (Add 4 8) x) // Fold the constant
+ (Mul 12 x) // The `Mul` changes hash and inputs
+
+The fix for this is to require Nodes NOT be in the `GVN` table when their edges
+modify; they need some sort of "edge lock". If "edges are locked", we need to
+remove the Node from `GVN` first, before modifying the edges.
+
+* We use the `_hash` field as both a cached hash code and as the edge lock. If
+ zero the Node is unlocked and NOT in `GVN`. If non-zero, the Node is
+ "edge-locked" and IS in `GVN`.
+* The `hashCode` function uses the cached hash if available and disallows an
+ accidental zero hash.
+* We add an `unlock()` call to remove a Node from `GVN` before any edge is
+ changed. This is inserted in front of all calls which hack Node edges. All
+ edge modify code paths already ensure the Node is re-peepholed, and during
+ this revisit the Node will get re-inserted in the `GVN` table.
+
+This new `GVN` table is used in `peepholeOpt()` (and `peephole()`) to look for common
+subexpressions on every peephole'd Node. If the Node has a zero hash, we look
+for a hit against some previous identical Node. If found, we use the prior
+Node and dead-code-eliminate this one. If not found, we insert this Node
+into `GVN` as the "golden instance". If a Node already has a non-zero hash
+we know it IS the "golden instance" and do not need to look in `GVN`.
+
+This entire optimization takes about a dozen lines in `iter()`, plus the common
+shared `equals` and `hashCode` (about 50 more lines counting comments).
+
+One of our invariants is that Types monotonically increase while running
+peepholes. GVN can break this briefly: of the two equivalent Nodes one has
+already had its `_type` lifted but not the other. Depending on which of the
+two Nodes is kept, we might choose the Node with the "lower" `_type`. This is
+"lower" in the Type lattice sense. Both types must be correct, and a
+`compute()` call on both nodes must produce the same Type, which must be equal
+to the JOIN. A fix is to compute a JOIN (not a MEET) over the two Nodes' types.
+
+
+## Post-Parse Iterative Peepholes
+
+The post-Parse `IterPeeps` iterates the peepholes to a fixed point - so
+no more peepholes apply. This should be linear because peepholes rarely
+(never?) increase code size. The graph should monotonically reduce in some
+dimension, which is usually size. It might also reduce in e.g. number of
+MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper
+ones.
+
+The theoretical overall worklist is mindless just grabbing the next thing and
+doing it. If the graph changes, put the neighbors on the worklist. Lather,
+Rinse, Repeat until the worklist runs dry.
+
+The main issues we have to deal with:
+
+* Nodes have uses; replacing some set of Nodes with another requires more graph
+ reworking. Not rocket science, but it can be fiddly. It's helpful to have a
+ small set of graph munging utilities, and the strong invariant that the graph
+ is stable and correct between peepholes. In our case `Node.subsume` does
+ most of the munging, building on our prior stable Node utilities.
+
+* Changing a Node also changes the graph "neighborhood". The neighbors need to
+ be checked to see if THEY can also peephole, and so on. After any peephole
+ or graph update we put a Node's uses and defs on the worklist.
+
+* Our strong invariant is that for all Nodes, either they are on the worklist
+ OR no peephole applies. This invariant is easy to check, although expensive.
+ Basically the normal "iterate peepholes to a fixed point" is linear, and this
+ check is linear at each peephole step... so quadratic overall. It's a useful
+ assert, but one we can disable once the overall algorithm is stable - and
+ then turn it back on again when some new set of peepholes is misbehaving.
+ The code for this is turned on in `IterPeeps.iterate` as `assert
+ progressOnList(stop);`
+
+
+## Distant Neighbors
+
+For some peepholes the "neighborhood" is farther away than just the immediate
+uses or defs, and for these we need a longer range plan. E.g. some peephole
+inspects "this -> A -> B -> C" and will swap itself for "D"; however it fails
+some test at "B". Should "B" ever update we want to revisit "this" and recheck
+his peepholes. So we will need to record a dependence of "this" in "B".
+Updating "B" throws the dependent list ("this") onto the "todo" list.
+
+An example of a distant neighbor check is in `AddNode`, where we check for
+stacked constants: `(Add (Add x 2) 1)` and we'd like `(Add x 3)` instead.
+Suppose we're doing this check and we find instead `(Add (Phi (Add x 2) self)
+1)` The check naturally bails out at the `Phi` since it's not an `Add`, but the
+`(Phi y self)` only has one unique input, and will itself peephole to `y`
+eventually. When it does, our stacked `Add` peephole can apply. So the
+failing Add peephole calls `phi.addDep(Add)` and registers a dependency on the
+`Phi`. If the `Phi` indeed later optimizes, we add its dependencies (e.g. the
+`Add`) back on our `IterPeeps` worklist and retry the stacked Add peephole.
+
+The general rule is:
+* **If a peephole pattern inspects a remote node, it must go on the dependency list!**
+* `node.in(1).in(2)` becomes `node.in(1).in(2).addDep(node)`
+
+
+In this chapter we trigger on following patterns
+
+* Some peeps interact with `Phi` inputs; this can be direct or indirect,
+ e.g. `(Add Add( (Phi x) 2 ) 1)`. The peep can progress if all of the `Phi`'s
+ inputs are `Constant`'s. Thus, we make the node a dependent on the `Phi`'s
+ input. We also make the node a dependent of the `Phi`'s region. See
+ `Node.allCons()` and `PhiNode.allCons()`.
+* The pattern `(Add (Add x 1) 2)` adds the outer `Add` as dependency of `x`
+ because `x` becoming a constant would enable progress. See
+ `AddNode.idealize()`
+* When computing a `Phi`'s type, if we observe that the associated region's
+ corresponding control is live, we add the `Phi` as a dependent of the
+ region's control input, because if that control goes dead, it would allow the
+ `Phi` to undergo peephole. See `PhiNode.compute()` and
+ `PhiNode.singleUniqueInput()`.
+
+Changes:
+
+* We add an `ArrayList<Node> _deps` field to Node; initially null.
+* Some peepholes (see above) add dependencies if they fail a remote check, by calling
+ `distant.addDep(this)`. The `addDep` call creates `_deps` and
+ filters for various kinds of duplicate adds.
+* The `IterPeeps` loop, when it finds a change, also moves all the
+ dependents onto the worklist.
+
+
+
+# Examples
+
+## Common SubExpressions via GVN
+
+These diagrams focus on value dependencies. Routine control flow is omitted;
+small True/False projections distinguish the two Returns in the first example.
+Empty control slots can stand for omitted context, not missing compiler inputs.
+
+### Example 1
+
+Here is a small example that illustrates how GVN enables finding common sub-expressions.
+
+```java
+int x = arg + arg;
+if(arg < 10) {
+ return arg + arg;
+}
+else {
+ x = x + 1;
+}
+return x;
+```
+
+Prior to GVN, this would result in the following graph. Note that the `arg+arg` is translated to `arg*2`.
+
+![Graph1](./09-graph1.svg)
+
+Adding GVN, we get below. Note how the `arg*2` expression is now reused rather than appearing twice.
+
+![Graph2](./09-graph2.svg)
+
+### Example 2
+
+Being able to reuse common expressions, enables additional optimizations. Here is a simple example:
+
+```java
+return arg*arg-arg*arg;
+```
+
+Without GVN the peepholes cannot see that both sides of the subtraction have the same value.
+
+![Graph3](./09-graph3.svg)
+
+- Each multiplication(*) node has two edges going to `arg`.
+- The input-slot labels distinguish these two uses of the same definition.
+
+With GVN, the peepholes can do a better job:
+
+![Graph4](./09-graph4.svg)
+
+## Post Parse Iterative Optimizations
+
+The worklist based post parse optimization enables certain optimizations that are not available
+during parsing. For example:
+
+```java
+int step = 1;
+while (arg < 10) {
+ arg = arg + step + 1;
+}
+return arg;
+```
+
+While parsing the `while` loop it is not yet known that `step` is a constant and will not change. Therefore,
+without the post parse optimization we get the following:
+
+The loop test and control backedge are omitted in both diagrams. The Phi's
+data backedge remains, making the repeated additions and their replacement
+easy to compare; its input 1 is the entry value and input 2 the next iteration.
+
+![Graph5](./09-graph5.svg)
+
+Enabling the post parse worklist based optimization yields below. Notice that now the graph shows `arg+2` inside the
+loop body:
+
+![Graph6](./09-graph6.svg)
+
+
+## Future Work
+
+There are more issues we will want to deal with in a later Chapter:
+
+* Blindly running peepholes in any order has some drawbacks:
+
+ - Dead and dying stuff might get peepholes done... and then die. Wasted work.
+ - Dead infinite loops often lead to infinite peephole cycles... if only we
+ would get around to working on the "base" of the dead loop it would fold
+ up.
+ - Some peepholes naturally reduce the graph directly; while some keep its
+ size the same but reduce other things (e.g. swapping a Mul-by-2 with a
+ Shift), and we might end up with a few which try to grow the graph briefly
+ before collapsing.
+
+* All this means is there's some benefit to running peepholes that reduce the
+ graph directly (e.g. Dead Code Eliminate), before running peeps that reduce
+ other things, before running all other peeps. This implies a sorted
+ worklist, but the count of unique orders is really limited - a radix sort is
+ all that is needed. We'll have to break up the peepholes into some
+ categories like
+ - "strictly reducing" vs
+ - "same Nodes but swapping e.g. `Mul` for `Shift`, vs
+ - getting more freedom (edge bypass), vs
+ - "grow now because shrink later" (inlining lands in this camp).
+
+* Also there's a benefit to not always grabbing from either end of the list -
+ many peep patterns might go quadratic if approached from one end or another,
+ because they modify something then push it back onto the list where it
+ immediately gets pulled again. I.e., you end up spinning in a loop repeating
+ the same peeps while slowly migrating e.g. left-spine add-tree into a
+ right-spine add-tree. A pseudo-random pull uses randomization to defeat bad
+ peep patterns.
+
+* Why isn't `IterPeeps` just passing over all of the Nodes once or twice,
+ instead of using a worklist with the `addDeps` mechanism? We could even
+ visit them in a defs-before-uses order (e.g. Reverse Post Order).
+
+ In the absence of loops exactly one such pass will find all local peepholes,
+ and indeed the Parser already does this. However, this will fail to find
+ opportunities at loops and farther remote cases - and to get those peepholes
+ around loops will require another visit. It is easy to construct a case
+ requiring O(N) passes, each of cost O(N) and the algorithm quickly goes
+ quadratic.
+
+ The `addDeps` solution avoids this quadratic cost, in exchange for some more
+ costs in writing peepholes.
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-15 12:26:57 +0000