diff options
| author | Cliff Click <cliffc@acm.org> | 2023-11-11 23:17:22 +0000 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-04 13:30:41 -0700 |
| commit | b50645a6b0ecdd9b41f947c172795c41d952874b (patch) | |
| tree | 112f7586bf804f65a4a9aba6918092ee074876ee /docs/chapter06 | |
| parent | 0f0ca9396a68b78362ce1ee59e6dc11d6910d56c (diff) | |
| download | Simple-b50645a6b0ecdd9b41f947c172795c41d952874b.tar.gz Simple-b50645a6b0ecdd9b41f947c172795c41d952874b.zip | |
Chapter 6: Peepholes for If
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Diffstat (limited to 'docs/chapter06')
33 files changed, 2777 insertions, 0 deletions
diff --git a/docs/chapter06/06-grammar.md b/docs/chapter06/06-grammar.md new file mode 100644 index 00000000..9ed7b160 --- /dev/null +++ b/docs/chapter06/06-grammar.md @@ -0,0 +1,79 @@ +# Grammar for Chapter 6 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter06/06-graph1-post.gv b/docs/chapter06/06-graph1-post.gv new file mode 100644 index 00000000..31480991 --- /dev/null +++ b/docs/chapter06/06-graph1-post.gv @@ -0,0 +1,29 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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_12 [ label="#2" ]; + Return13 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return13[taillabel=0 color=red]; + Return13 -> Start2:p0[taillabel=0 color=red]; + Return13 -> Con_12[taillabel=1]; +} diff --git a/docs/chapter06/06-graph1-post.json b/docs/chapter06/06-graph1-post.json new file mode 100644 index 00000000..325d473a --- /dev/null +++ b/docs/chapter06/06-graph1-post.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph1-post.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": null}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph1-post.svg b/docs/chapter06/06-graph1-post.svg new file mode 100644 index 00000000..7c58b6c3 --- /dev/null +++ b/docs/chapter06/06-graph1-post.svg @@ -0,0 +1,80 @@ +<svg aria-label="Compiler graph" width="326" height="320" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 326 320" 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 CTRL" id="e3i0" d="M104,219 C104,243 163,246 163,270" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #13 · CTRL</title></path><path class="edge CTRL" id="e13i0" d="M84,118 L84,166" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#13[0] → #1 · CTRL</title></path><path class="edge DATA" id="e13i1" d="M242,118 L242,123 Q242,128 237,128 L132,128 Q124,128 124,136 L124,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#13[1] → #12 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(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="n3" data-id="3" transform="translate(127,270)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #13 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n12" data-id="12" transform="translate(182,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"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 #2 +Type not computed + +</title></g><g class="node" id="n13" data-id="13" transform="translate(44,172)" 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"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 Return +Type not computed + +[0] → #1 CTRL +[1] → #12 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/chapter06/06-graph1-pre.gv b/docs/chapter06/06-graph1-pre.gv new file mode 100644 index 00000000..2bfdd23d --- /dev/null +++ b/docs/chapter06/06-graph1-pre.gv @@ -0,0 +1,52 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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_6 [ label="#1" ]; + If7 [ 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_11 [ label="#2" ]; + Return12 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_13 [ label="#~CONTROL" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Con_15 [ label="#1" ]; + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region14;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return12[taillabel=0 color=red]; + Stop3 -> Return16[taillabel=1 color=red]; + If7 -> Start2:p0[taillabel=0 color=red]; + If7 -> Con_6[taillabel=1]; + Return12 -> If7:p0[taillabel=0 color=red]; + Return12 -> Con_11[taillabel=1]; + Region14 -> Con_13[taillabel=1]; + Region14 -> If7:p1[taillabel=2 color=red]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Con_15[taillabel=1]; +} diff --git a/docs/chapter06/06-graph1-pre.json b/docs/chapter06/06-graph1-pre.json new file mode 100644 index 00000000..18615f2c --- /dev/null +++ b/docs/chapter06/06-graph1-pre.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph1-pre.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 16, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}], "proj": {"par": 7, "idx": 0}}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}], "proj": {"par": 7, "idx": 1}}, + {"id": 6, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "#~CONTROL", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 15, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph1-pre.svg b/docs/chapter06/06-graph1-pre.svg new file mode 100644 index 00000000..693ddba6 --- /dev/null +++ b/docs/chapter06/06-graph1-pre.svg @@ -0,0 +1,111 @@ +<svg aria-label="Compiler graph" width="598" height="572" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 598 572" 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 CTRL" id="e3i0" d="M256,367 C256,391 287,498 287,522" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #12 · CTRL</title></path><path class="edge CTRL" id="e3i1" d="M124,471 C124,495 311,498 311,522" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[1] → #16 · CTRL</title></path><path class="edge CTRL" id="e7i0" d="M256,118 L256,166" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#7[0] → #1 · CTRL</title></path><path class="edge DATA" id="e7i1" d="M414,118 L414,123 Q414,128 409,128 L344,128 Q336,128 336,136 L336,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #6 · DATA</title></path><path class="edge CTRL" id="e12i0" d="M236,266 L236,314" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#12[0] → #4 · CTRL</title></path><path class="edge DATA" id="e12i1" d="M514,266 L514,278 Q514,286 506,286 L284,286 Q276,286 276,294 L276,314" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#12[1] → #11 · DATA</title></path><path class="edge DATA" id="e14i1" d="M84,266 L84,271 Q84,276 89,276 L96,276 Q104,276 104,284 L104,314" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[1] → #13 · DATA</title></path><path class="edge CTRL" id="e14i2" d="M356,266 L356,271 Q356,276 351,276 L142,276 Q134,276 134,284 L134,314" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#14[2] → #5 · CTRL</title></path><path class="edge CTRL" id="e16i0" d="M104,370 L104,418" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#16[0] → #14 · CTRL</title></path><path class="edge DATA" id="e16i1" d="M408,370 L408,375 Q408,380 403,380 L152,380 Q144,380 144,388 L144,418" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #15 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(196,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(196,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="n3" data-id="3" transform="translate(263,522)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #12 CTRL +[1] → #16 CTRL</title><circle class="port" cx="24" cy="0" r="3" fill="#536477"/><circle class="port" cx="48" cy="0" r="3" fill="#536477"/><text class="slot" x="24" y="-7" text-anchor="middle">0</text><text class="slot" x="48" y="-7" text-anchor="middle">1</text></g><g class="node" id="n4" data-id="4" transform="translate(176,216)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #4/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 True +Projection 0 of #7 +Type not computed + +[0] → #7 CTRL</title></g><g class="node" id="n5" data-id="5" transform="translate(296,216)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #5/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 False +Projection 1 of #7 +Type not computed + +[0] → #7 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(354,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #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="n7" data-id="7" transform="translate(176,172)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#7 If +Type not computed + +[0] → #1 CTRL +[1] → #6 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n11" data-id="11" transform="translate(454,216)" 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"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 #2 +Type not computed + +</title></g><g class="node" id="n12" data-id="12" transform="translate(196,320)" 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"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 Return +Type not computed + +[0] → #4 CTRL +[1] → #11 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="n13" data-id="13" transform="translate(24,216)" 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>#~CONTROL</tspan><tspan class="node-id"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 #~CONTROL +Type not computed + +</title></g><g class="node" id="n14" data-id="14" transform="translate(44,320)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 Region +Type not computed + +[0] → — DATA +[1] → #13 DATA +[2] → #5 CTRL</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n15" data-id="15" transform="translate(348,320)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 #1 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" transform="translate(64,424)" 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"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 Return +Type not computed + +[0] → #14 CTRL +[1] → #15 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/chapter06/06-graph2-post.gv b/docs/chapter06/06-graph2-post.gv new file mode 100644 index 00000000..61ae2ca1 --- /dev/null +++ b/docs/chapter06/06-graph2-post.gv @@ -0,0 +1,33 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + 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_13 [ label="#2" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return17 -> Start2:p0[taillabel=0 color=red]; + Return17 -> Con_13[taillabel=1]; + Stop3 -> Return17[taillabel=0 color=red]; +} diff --git a/docs/chapter06/06-graph2-post.json b/docs/chapter06/06-graph2-post.json new file mode 100644 index 00000000..31be64c2 --- /dev/null +++ b/docs/chapter06/06-graph2-post.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph2-post.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": null}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph2-post.svg b/docs/chapter06/06-graph2-post.svg new file mode 100644 index 00000000..a87af3ec --- /dev/null +++ b/docs/chapter06/06-graph2-post.svg @@ -0,0 +1,80 @@ +<svg aria-label="Compiler graph" width="326" height="320" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 326 320" 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 CTRL" id="e3i0" d="M104,219 C104,243 163,246 163,270" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #17 · CTRL</title></path><path class="edge CTRL" id="e17i0" d="M84,118 L84,166" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#17[0] → #1 · CTRL</title></path><path class="edge DATA" id="e17i1" d="M242,118 L242,123 Q242,128 237,128 L132,128 Q124,128 124,136 L124,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[1] → #13 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(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="n3" data-id="3" transform="translate(127,270)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #17 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n13" data-id="13" transform="translate(182,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"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 #2 +Type not computed + +</title></g><g class="node" id="n17" data-id="17" transform="translate(44,172)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 Return +Type not computed + +[0] → #1 CTRL +[1] → #13 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter06/06-graph2-pre.gv b/docs/chapter06/06-graph2-pre.gv new file mode 100644 index 00000000..d183b4c4 --- /dev/null +++ b/docs/chapter06/06-graph2-pre.gv @@ -0,0 +1,55 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + 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_7 [ label="#1" ]; + If8 [ 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_12 [ label="#2" ]; + Con_13 [ label="#3" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a15 [ style=filled fillcolor=lightyellow label="φ_a" ]; + { rank=same; Region14;Phi_a15;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Phi_a15[taillabel=1]; + Stop3 -> Return16[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Con_7[taillabel=1]; + Region14 -> If8:p0[taillabel=1 color=red]; + Region14 -> If8:p1[taillabel=2 color=red]; + Phi_a15 -> Region14 [style=dotted taillabel=0]; + Phi_a15 -> Con_12[taillabel=1]; + Phi_a15 -> Con_13[taillabel=2]; +} diff --git a/docs/chapter06/06-graph2-pre.json b/docs/chapter06/06-graph2-pre.json new file mode 100644 index 00000000..fd187946 --- /dev/null +++ b/docs/chapter06/06-graph2-pre.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph2-pre.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "CTRL", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 15, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 14, "role": "ASSOC", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [4, 5, 8, 14, 15]} + ] +} diff --git a/docs/chapter06/06-graph2-pre.svg b/docs/chapter06/06-graph2-pre.svg new file mode 100644 index 00000000..f787b4dc --- /dev/null +++ b/docs/chapter06/06-graph2-pre.svg @@ -0,0 +1,108 @@ +<svg aria-label="Compiler graph" width="662" height="628" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 662 628" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"><g class="region" transform="translate(24,171)"><rect class="region-box" rx="8" width="360" height="250" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M180,527 C180,551 331,554 331,578" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #16 · CTRL</title></path><path class="edge CTRL" id="e8i0" d="M116,118 L116,205" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#8[0] → #1 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M274,118 L274,123 Q274,128 269,128 L204,128 Q196,128 196,136 L196,205" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #7 · DATA</title></path><path class="edge CTRL" id="e14i1" d="M96,305 L96,310 Q96,315 101,315 L152,315 Q160,315 160,323 L160,353" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#14[1] → #4 · CTRL</title></path><path class="edge CTRL" id="e14i2" d="M216,305 L216,310 Q216,315 211,315 L198,315 Q190,315 190,323 L190,353" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#14[2] → #5 · CTRL</title></path><path class="edge DATA" id="e15i1" d="M426,118 L426,123 Q426,128 421,128 L300,128 Q292,128 292,136 L292,353" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[1] → #12 · DATA</title></path><path class="edge DATA" id="e15i2" d="M578,118 L578,130 Q578,138 570,138 L340,138 Q332,138 332,146 L332,353" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[2] → #13 · DATA</title></path><path class="edge CTRL" id="e16i0" d="M160,409 L160,474" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#16[0] → #14 · CTRL</title></path><path class="edge DATA" id="e16i1" d="M312,409 L312,428 Q312,436 304,436 L208,436 Q200,436 200,444 L200,474" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #15 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(56,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(56,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="n3" data-id="3" transform="translate(295,578)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #16 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(36,255)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #4/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRL</title></g><g class="node" id="n5" data-id="5" transform="translate(156,255)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #5/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRL</title></g><g class="node" id="n7" data-id="7" transform="translate(214,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 #1 +Type not computed + +</title></g><g class="node" id="n8" data-id="8" transform="translate(36,211)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#8 If +Type not computed + +[0] → #1 CTRL +[1] → #7 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n12" data-id="12" transform="translate(366,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"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 #2 +Type not computed + +</title></g><g class="node" id="n13" data-id="13" transform="translate(518,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>#3</tspan><tspan class="node-id"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#13 #3 +Type not computed + +</title></g><g class="node" id="n14" data-id="14" transform="translate(100,359)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 Region +Type not computed + +[0] → — DATA +[1] → #4 CTRL +[2] → #5 CTRL</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n15" data-id="15" transform="translate(252,359)" 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>φ_a</tspan><tspan class="node-id"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 φ_a +Type not computed + +[0] → #14 ASSOC +[1] → #12 DATA +[2] → #13 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #14</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n16" data-id="16" transform="translate(120,480)" 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"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 Return +Type not computed + +[0] → #14 CTRL +[1] → #15 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"><g class="region-head" transform="translate(24,171)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #8</tspan></text><title>If · 5 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #8"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g></g><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter06/06-graph3-false.gv b/docs/chapter06/06-graph3-false.gv new file mode 100644 index 00000000..28f741fa --- /dev/null +++ b/docs/chapter06/06-graph3-false.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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_30 [ label="#1" ]; + Return31 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return31[taillabel=0 color=red]; + Return31 -> Start2:p0[taillabel=0 color=red]; + Return31 -> Con_30[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-false.svg b/docs/chapter06/06-graph3-false.svg new file mode 100644 index 00000000..49b04f09 --- /dev/null +++ b/docs/chapter06/06-graph3-false.svg @@ -0,0 +1,67 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter06 Pages: 1 --> +<svg width="178pt" height="248pt" + viewBox="0.00 0.00 178.00 248.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 244)"> +<title>chapter06</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 174,-244 174,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-232 162,-232 162,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<polygon fill="none" stroke="black" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<text text-anchor="start" x="30.5" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="24,-164 24,-195 74,-195 74,-164 24,-164"/> +<polygon fill="yellow" stroke="transparent" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<polygon fill="none" stroke="black" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<text text-anchor="start" x="32" y="-175.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="112,-52 58,-52 58,-16 112,-16 112,-52"/> +<text text-anchor="middle" x="85" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return31 --> +<g id="node4" class="node"> +<title>Return31</title> +<polygon fill="yellow" stroke="black" points="118,-124 52,-124 52,-88 118,-88 118,-124"/> +<text text-anchor="middle" x="85" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return31 --> +<g id="edge1" class="edge"> +<title>Stop3->Return31</title> +<path fill="none" stroke="red" d="M85,-52.3C85,-60.02 85,-69.29 85,-77.89"/> +<polygon fill="red" stroke="red" points="81.5,-77.9 85,-87.9 88.5,-77.9 81.5,-77.9"/> +<text text-anchor="middle" x="82" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_30 --> +<g id="node3" class="node"> +<title>Con_30</title> +<ellipse fill="none" stroke="black" cx="127" cy="-192" rx="27" ry="18"/> +<text text-anchor="middle" x="127" y="-188.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Return31->Start2 --> +<g id="edge2" class="edge"> +<title>Return31->Start2:p0</title> +<path fill="none" stroke="red" d="M68.26,-124.13C60.77,-133.26 52.99,-145.23 50.13,-158.06"/> +<polygon fill="red" stroke="red" points="46.66,-157.67 49,-168 53.61,-158.46 46.66,-157.67"/> +<text text-anchor="middle" x="65.26" y="-126.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return31->Con_30 --> +<g id="edge3" class="edge"> +<title>Return31->Con_30</title> +<path fill="none" stroke="black" d="M93.7,-124.4C99.66,-136.31 107.65,-152.3 114.31,-165.62"/> +<polygon fill="black" stroke="black" points="111.28,-167.38 118.88,-174.76 117.54,-164.25 111.28,-167.38"/> +<text text-anchor="middle" x="90.7" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter06/06-graph3-nonconst-peephole.gv b/docs/chapter06/06-graph3-nonconst-peephole.gv new file mode 100644 index 00000000..f8e3e5fa --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.gv @@ -0,0 +1,56 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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" ]; + Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; + If8 [ 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_27 [ label="#4" ]; + Con_29 [ label="#1" ]; + Phi_ab30 [ style=filled fillcolor=lightyellow label="φ_ab" ]; + Return31 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region22;Phi_ab30;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return31[taillabel=0 color=red]; + Region22 -> If8:p0[taillabel=1 color=red]; + Region22 -> If8:p1[taillabel=2 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Start2:p1[taillabel=1]; + Phi_ab30 -> Region22 [style=dotted taillabel=0]; + Phi_ab30 -> Con_27[taillabel=1]; + Phi_ab30 -> Con_29[taillabel=2]; + Return31 -> Region22[taillabel=0 color=red]; + Return31 -> Phi_ab30[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-nonconst-peephole.json b/docs/chapter06/06-graph3-nonconst-peephole.json new file mode 100644 index 00000000..7f1f183c --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph3-nonconst-peephole.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 31, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 6, "role": "CTRL", "label": null}], "proj": null}, + {"id": 27, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 29, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 30, "label": "φ_ab", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 22, "role": "ASSOC", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}, {"idx": 2, "def": 29, "role": "DATA", "label": null}], "proj": null}, + {"id": 31, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 22, "role": "CTRL", "label": null}, {"idx": 1, "def": 30, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [5, 6, 8, 22, 30]} + ] +} diff --git a/docs/chapter06/06-graph3-nonconst-peephole.svg b/docs/chapter06/06-graph3-nonconst-peephole.svg new file mode 100644 index 00000000..a60d66f9 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.svg @@ -0,0 +1,109 @@ +<svg aria-label="Compiler graph" width="630" height="628" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 630 628" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"><g class="region" transform="translate(24,171)"><rect class="region-box" rx="8" width="360" height="250" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M180,527 C180,551 315,554 315,578" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #31 · CTRL</title></path><path class="edge CTRL" id="e8i0" d="M116,118 L116,205" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#8[0] → #1 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M236,118 L236,123 Q236,128 231,128 L204,128 Q196,128 196,136 L196,205" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge CTRL" id="e22i1" d="M96,305 L96,310 Q96,315 101,315 L152,315 Q160,315 160,323 L160,353" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#22[1] → #5 · CTRL</title></path><path class="edge CTRL" id="e22i2" d="M216,305 L216,310 Q216,315 211,315 L198,315 Q190,315 190,323 L190,353" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#22[2] → #6 · CTRL</title></path><path class="edge DATA" id="e30i1" d="M394,118 L394,123 Q394,128 389,128 L300,128 Q292,128 292,136 L292,353" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#30[1] → #27 · DATA</title></path><path class="edge DATA" id="e30i2" d="M546,118 L546,130 Q546,138 538,138 L340,138 Q332,138 332,146 L332,353" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#30[2] → #29 · DATA</title></path><path class="edge CTRL" id="e31i0" d="M160,409 L160,474" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#31[0] → #22 · CTRL</title></path><path class="edge DATA" id="e31i1" d="M312,409 L312,428 Q312,436 304,436 L208,436 Q200,436 200,444 L200,474" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#31[1] → #30 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(56,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(56,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(279,578)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #31 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(176,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(36,255)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(156,255)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #6/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRL</title></g><g class="node" id="n8" data-id="8" transform="translate(36,211)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#8 If +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n22" data-id="22" transform="translate(100,359)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #22</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#22 Region +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #6 CTRL</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n27" data-id="27" transform="translate(334,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>#4</tspan><tspan class="node-id"> #27</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#27 #4 +Type not computed + +</title></g><g class="node" id="n29" data-id="29" transform="translate(486,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #29</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#29 #1 +Type not computed + +</title></g><g class="node" id="n30" data-id="30" transform="translate(252,359)" 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>φ_ab</tspan><tspan class="node-id"> #30</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#30 φ_ab +Type not computed + +[0] → #22 ASSOC +[1] → #27 DATA +[2] → #29 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #22</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n31" data-id="31" transform="translate(120,480)" 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"> #31</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#31 Return +Type not computed + +[0] → #22 CTRL +[1] → #30 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"><g class="region-head" transform="translate(24,171)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #8</tspan></text><title>If · 5 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #8"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g></g><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter06/06-graph3-nonconst.gv b/docs/chapter06/06-graph3-nonconst.gv new file mode 100644 index 00000000..7cd4e8e2 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.gv @@ -0,0 +1,86 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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="#0" ]; + Con_7 [ label="#1" ]; + If8 [ 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_12 [ label="#2" ]; + If13 [ 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_17 [ label="#2" ]; + Con_18 [ label="#3" ]; + Region19 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b20 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region21 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a22 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b23 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Add24 [ label="+" ]; + Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region19;Phi_b20;} + { rank=same; Region21;Phi_b23;Phi_a22;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return25[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Start2:p1[taillabel=1]; + If13 -> If8:p0[taillabel=0 color=red]; + If13 -> Start2:p1[taillabel=1]; + Region19 -> If13:p0[taillabel=1 color=red]; + Region19 -> If13:p1[taillabel=2 color=red]; + Phi_b20 -> Region19 [style=dotted taillabel=0]; + Phi_b20 -> Con_17[taillabel=1]; + Phi_b20 -> Con_18[taillabel=2]; + Region21 -> Region19[taillabel=1 color=red]; + Region21 -> If8:p1[taillabel=2 color=red]; + Phi_a22 -> Region21 [style=dotted taillabel=0]; + Phi_a22 -> Con_12[taillabel=1]; + Phi_a22 -> Con_6[taillabel=2]; + Phi_b23 -> Region21 [style=dotted taillabel=0]; + Phi_b23 -> Phi_b20[taillabel=1]; + Phi_b23 -> Con_7[taillabel=2]; + Add24 -> Phi_b23[taillabel=1]; + Add24 -> Phi_a22[taillabel=2]; + Return25 -> Region21[taillabel=0 color=red]; + Return25 -> Add24[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-nonconst.json b/docs/chapter06/06-graph3-nonconst.json new file mode 100644 index 00000000..77bb6d2c --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.json @@ -0,0 +1,35 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph3-nonconst.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": {"par": 13, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": {"par": 13, "idx": 1}}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 19, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "CTRL", "label": null}, {"idx": 2, "def": 11, "role": "CTRL", "label": null}], "proj": null}, + {"id": 20, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 19, "role": "ASSOC", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 19, "role": "CTRL", "label": null}, {"idx": 2, "def": 9, "role": "CTRL", "label": null}], "proj": null}, + {"id": 22, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}, {"idx": 1, "def": 24, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [5, 8, 9, 21, 22, 23, 24]}, + {"id": 13, "par": 8, "nodes": [10, 11, 13, 19, 20]} + ] +} diff --git a/docs/chapter06/06-graph3-nonconst.svg b/docs/chapter06/06-graph3-nonconst.svg new file mode 100644 index 00000000..2e4ec0fc --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.svg @@ -0,0 +1,150 @@ +<svg aria-label="Compiler graph" width="1086" height="1042" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1086 1042" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"><g class="region" transform="translate(24,171)"><rect class="region-box" rx="8" width="608" height="664" fill="#f2f7ef"/></g><g class="region" transform="translate(227,358)"><rect class="region-box" rx="8" width="360" height="250" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M206,941 C206,965 543,968 543,992" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #25 · CTRL</title></path><path class="edge CTRL" id="e8i0" d="M116,118 L116,205" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#8[0] → #1 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M236,118 L236,130 Q236,138 228,138 L204,138 Q196,138 196,146 L196,205" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge CTRL" id="e13i0" d="M96,305 L96,310 Q96,315 101,315 L311,315 Q319,315 319,323 L319,392" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#13[0] → #5 · CTRL</title></path><path class="edge DATA" id="e13i1" d="M236,118 L236,130 Q236,138 244,138 L391,138 Q399,138 399,146 L399,392" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#13[1] → #4 · DATA</title></path><path class="edge CTRL" id="e19i1" d="M299,492 L299,497 Q299,502 304,502 L355,502 Q363,502 363,510 L363,540" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#19[1] → #10 · CTRL</title></path><path class="edge CTRL" id="e19i2" d="M419,492 L419,497 Q419,502 414,502 L401,502 Q393,502 393,510 L393,540" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#19[2] → #11 · CTRL</title></path><path class="edge DATA" id="e20i1" d="M394,118 L394,123 Q394,128 399,128 L487,128 Q495,128 495,136 L495,540" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[1] → #17 · DATA</title></path><path class="edge DATA" id="e20i2" d="M546,118 L546,123 Q546,128 541,128 L540.5,128 Q535,128 535,133.5 L535,540" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[2] → #18 · DATA</title></path><path class="edge CTRL" id="e21i1" d="M363,596 L363,615 Q363,623 355,623 L194,623 Q186,623 186,631 L186,663" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#21[1] → #19 · CTRL</title></path><path class="edge CTRL" id="e21i2" d="M216,305 L216,663" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#21[2] → #9 · CTRL</title></path><path class="edge DATA" id="e22i1" d="M698,118 L698,123 Q698,128 693,128 L605,128 Q597,128 597,136 L597,625 Q597,633 589,633 L326,633 Q318,633 318,641 L318,663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#22[1] → #12 · DATA</title></path><path class="edge DATA" id="e22i2" d="M850,118 L850,130 Q850,138 842,138 L616,138 Q608,138 608,146 L608,635 Q608,643 600,643 L366,643 Q358,643 358,651 L358,663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#22[2] → #6 · DATA</title></path><path class="edge DATA" id="e23i1" d="M515,596 L515,615 Q515,623 507,623 L478,623 Q470,623 470,631 L470,663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#23[1] → #20 · DATA</title></path><path class="edge DATA" id="e23i2" d="M1002,118 L1002,140 Q1002,148 994,148 L627,148 Q619,148 619,156 L619,645 Q619,653 611,653 L515,653 Q510,653 510,658 L510,663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#23[2] → #7 · DATA</title></path><path class="edge DATA" id="e24i1" d="M490,719 L490,724 Q490,729 485,729 L316,729 Q308,729 308,737 L308,767" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#24[1] → #23 · DATA</title></path><path class="edge DATA" id="e24i2" d="M338,719 L338,767" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#24[2] → #22 · DATA</title></path><path class="edge CTRL" id="e25i0" d="M186,719 L186,888" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#25[0] → #21 · CTRL</title></path><path class="edge DATA" id="e25i1" d="M308,823 L308,842 Q308,850 300,850 L234,850 Q226,850 226,858 L226,888" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#25[1] → #24 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(56,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(56,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(507,992)" style="opacity: 1;"><path class="box" d="M0,0H72V26H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="36" y="17"><tspan>Stop</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="36"/><title>#3 Stop +Type not computed + +[0] → #25 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(176,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(36,255)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(790,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>#0</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #0 +Type not computed + +</title></g><g class="node" id="n7" data-id="7" transform="translate(942,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 #1 +Type not computed + +</title></g><g class="node" id="n8" data-id="8" transform="translate(36,211)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#8 If +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n9" data-id="9" transform="translate(156,255)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #9/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRL</title></g><g class="node" id="n10" data-id="10" transform="translate(239,442)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #10/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 True +Projection 0 of #13 +Type not computed + +[0] → #13 CTRL</title></g><g class="node" id="n11" data-id="11" transform="translate(359,442)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>False</tspan><tspan class="node-id"> #11/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 False +Projection 1 of #13 +Type not computed + +[0] → #13 CTRL</title></g><g class="node" id="n12" data-id="12" transform="translate(638,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"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 #2 +Type not computed + +</title></g><g class="node" id="n13" data-id="13" transform="translate(239,398)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>If</tspan><tspan class="node-id"> #13</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#13 If +Type not computed + +[0] → #5 CTRL +[1] → #4 DATA</title><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><circle class="port" cx="160" cy="-3" r="3" fill="#536477"/><text class="slot" x="80" y="-10" text-anchor="middle">0</text><text class="slot" x="160" y="-10" text-anchor="middle">1</text></g><g class="node" id="n17" data-id="17" transform="translate(334,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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 #2 +Type not computed + +</title></g><g class="node" id="n18" data-id="18" transform="translate(486,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>#3</tspan><tspan class="node-id"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 #3 +Type not computed + +</title></g><g class="node" id="n19" data-id="19" transform="translate(303,546)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 Region +Type not computed + +[0] → — DATA +[1] → #10 CTRL +[2] → #11 CTRL</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n20" data-id="20" transform="translate(455,546)" 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>φ_b</tspan><tspan class="node-id"> #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 φ_b +Type not computed + +[0] → #19 ASSOC +[1] → #17 DATA +[2] → #18 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #19</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n21" data-id="21" transform="translate(126,669)" style="opacity: 1;"><path class="box" d="M12,0H108L120,44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Region</tspan><tspan class="node-id"> #21</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#21 Region +Type not computed + +[0] → — DATA +[1] → #19 CTRL +[2] → #9 CTRL</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n22" data-id="22" transform="translate(278,669)" 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>φ_a</tspan><tspan class="node-id"> #22</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#22 φ_a +Type not computed + +[0] → #21 ASSOC +[1] → #12 DATA +[2] → #6 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #21</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n23" data-id="23" transform="translate(430,669)" 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>φ_b</tspan><tspan class="node-id"> #23</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#23 φ_b +Type not computed + +[0] → #21 ASSOC +[1] → #20 DATA +[2] → #7 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #21</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n24" data-id="24" transform="translate(248,773)" 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"> #24</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#24 + +Type not computed + +[0] → — DATA +[1] → #23 DATA +[2] → #22 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="n25" data-id="25" transform="translate(146,894)" 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"> #25</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#25 Return +Type not computed + +[0] → #21 CTRL +[1] → #24 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"><g class="region-head" transform="translate(24,171)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #8</tspan></text><title>If · 12 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #8"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g><g class="region-head" transform="translate(227,358)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #13</tspan></text><title>If · 5 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #13"><rect width="16" height="16" rx="2"/><text x="8" y="12" text-anchor="middle">−</text><title>Fold region</title></g></g></g><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter06/06-graph3-true.gv b/docs/chapter06/06-graph3-true.gv new file mode 100644 index 00000000..9739169c --- /dev/null +++ b/docs/chapter06/06-graph3-true.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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_28 [ label="#4" ]; + Return29 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return29[taillabel=0 color=red]; + Return29 -> Start2:p0[taillabel=0 color=red]; + Return29 -> Con_28[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-true.svg b/docs/chapter06/06-graph3-true.svg new file mode 100644 index 00000000..7e573cc6 --- /dev/null +++ b/docs/chapter06/06-graph3-true.svg @@ -0,0 +1,67 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter06 Pages: 1 --> +<svg width="178pt" height="248pt" + viewBox="0.00 0.00 178.00 248.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 244)"> +<title>chapter06</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 174,-244 174,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-232 162,-232 162,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<polygon fill="none" stroke="black" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<text text-anchor="start" x="30.5" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="24,-164 24,-195 74,-195 74,-164 24,-164"/> +<polygon fill="yellow" stroke="transparent" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<polygon fill="none" stroke="black" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<text text-anchor="start" x="32" y="-175.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="112,-52 58,-52 58,-16 112,-16 112,-52"/> +<text text-anchor="middle" x="85" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return29 --> +<g id="node4" class="node"> +<title>Return29</title> +<polygon fill="yellow" stroke="black" points="118,-124 52,-124 52,-88 118,-88 118,-124"/> +<text text-anchor="middle" x="85" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return29 --> +<g id="edge1" class="edge"> +<title>Stop3->Return29</title> +<path fill="none" stroke="red" d="M85,-52.3C85,-60.02 85,-69.29 85,-77.89"/> +<polygon fill="red" stroke="red" points="81.5,-77.9 85,-87.9 88.5,-77.9 81.5,-77.9"/> +<text text-anchor="middle" x="82" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_28 --> +<g id="node3" class="node"> +<title>Con_28</title> +<ellipse fill="none" stroke="black" cx="127" cy="-192" rx="27" ry="18"/> +<text text-anchor="middle" x="127" y="-188.3" font-family="Times,serif" font-size="14.00">#4</text> +</g> +<!-- Return29->Start2 --> +<g id="edge2" class="edge"> +<title>Return29->Start2:p0</title> +<path fill="none" stroke="red" d="M68.26,-124.13C60.77,-133.26 52.99,-145.23 50.13,-158.06"/> +<polygon fill="red" stroke="red" points="46.66,-157.67 49,-168 53.61,-158.46 46.66,-157.67"/> +<text text-anchor="middle" x="65.26" y="-126.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return29->Con_28 --> +<g id="edge3" class="edge"> +<title>Return29->Con_28</title> +<path fill="none" stroke="black" d="M93.7,-124.4C99.66,-136.31 107.65,-152.3 114.31,-165.62"/> +<polygon fill="black" stroke="black" points="111.28,-167.38 118.88,-174.76 117.54,-164.25 111.28,-167.38"/> +<text text-anchor="middle" x="90.7" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter06/06-graph4-arg2.gv b/docs/chapter06/06-graph4-arg2.gv new file mode 100644 index 00000000..7d6913e2 --- /dev/null +++ b/docs/chapter06/06-graph4-arg2.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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_44 [ label="#5" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-arg2.svg b/docs/chapter06/06-graph4-arg2.svg new file mode 100644 index 00000000..8ec80be4 --- /dev/null +++ b/docs/chapter06/06-graph4-arg2.svg @@ -0,0 +1,67 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter06 Pages: 1 --> +<svg width="178pt" height="248pt" + viewBox="0.00 0.00 178.00 248.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 244)"> +<title>chapter06</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 174,-244 174,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-232 162,-232 162,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<polygon fill="none" stroke="black" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<text text-anchor="start" x="30.5" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="24,-164 24,-195 74,-195 74,-164 24,-164"/> +<polygon fill="yellow" stroke="transparent" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<polygon fill="none" stroke="black" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<text text-anchor="start" x="32" y="-175.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="112,-52 58,-52 58,-16 112,-16 112,-52"/> +<text text-anchor="middle" x="85" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return45 --> +<g id="node4" class="node"> +<title>Return45</title> +<polygon fill="yellow" stroke="black" points="118,-124 52,-124 52,-88 118,-88 118,-124"/> +<text text-anchor="middle" x="85" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return45 --> +<g id="edge1" class="edge"> +<title>Stop3->Return45</title> +<path fill="none" stroke="red" d="M85,-52.3C85,-60.02 85,-69.29 85,-77.89"/> +<polygon fill="red" stroke="red" points="81.5,-77.9 85,-87.9 88.5,-77.9 81.5,-77.9"/> +<text text-anchor="middle" x="82" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_44 --> +<g id="node3" class="node"> +<title>Con_44</title> +<ellipse fill="none" stroke="black" cx="127" cy="-192" rx="27" ry="18"/> +<text text-anchor="middle" x="127" y="-188.3" font-family="Times,serif" font-size="14.00">#5</text> +</g> +<!-- Return45->Start2 --> +<g id="edge2" class="edge"> +<title>Return45->Start2:p0</title> +<path fill="none" stroke="red" d="M68.26,-124.13C60.77,-133.26 52.99,-145.23 50.13,-158.06"/> +<polygon fill="red" stroke="red" points="46.66,-157.67 49,-168 53.61,-158.46 46.66,-157.67"/> +<text text-anchor="middle" x="65.26" y="-126.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return45->Con_44 --> +<g id="edge3" class="edge"> +<title>Return45->Con_44</title> +<path fill="none" stroke="black" d="M93.7,-124.4C99.66,-136.31 107.65,-152.3 114.31,-165.62"/> +<polygon fill="black" stroke="black" points="111.28,-167.38 118.88,-174.76 117.54,-164.25 111.28,-167.38"/> +<text text-anchor="middle" x="90.7" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter06/06-graph4-nonconst.gv b/docs/chapter06/06-graph4-nonconst.gv new file mode 100644 index 00000000..b8899b48 --- /dev/null +++ b/docs/chapter06/06-graph4-nonconst.gv @@ -0,0 +1,122 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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="#0" ]; + Con_7 [ label="#1" ]; + Con_8 [ label="#0" ]; + If9 [ 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_13 [ label="#1" ]; + Con_14 [ label="#2" ]; + EQNode15 [ label="==" ]; + If16 [ 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_20 [ label="#2" ]; + Con_21 [ label="#3" ]; + Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_c23 [ style=filled fillcolor=lightyellow label="φ_c" ]; + If24 [ 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_28 [ label="#2" ]; + Con_29 [ label="#3" ]; + Region30 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b31 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a33 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b34 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Phi_c35 [ style=filled fillcolor=lightyellow label="φ_c" ]; + Add36 [ label="+" ]; + Add37 [ label="+" ]; + Return38 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region22;Phi_c23;} + { rank=same; Region30;Phi_b31;} + { rank=same; Region32;Phi_c35;Phi_a33;Phi_b34;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return38[taillabel=0 color=red]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> Start2:p1[taillabel=1]; + EQNode15 -> Start2:p1[taillabel=1]; + EQNode15 -> Con_14[taillabel=2]; + If16 -> If9:p0[taillabel=0 color=red]; + If16 -> EQNode15[taillabel=1]; + Region22 -> If16:p0[taillabel=1 color=red]; + Region22 -> If16:p1[taillabel=2 color=red]; + Phi_c23 -> Region22 [style=dotted taillabel=0]; + Phi_c23 -> Con_20[taillabel=1]; + Phi_c23 -> Con_21[taillabel=2]; + If24 -> Region22[taillabel=0 color=red]; + If24 -> Start2:p1[taillabel=1]; + Region30 -> If24:p0[taillabel=1 color=red]; + Region30 -> If24:p1[taillabel=2 color=red]; + Phi_b31 -> Region30 [style=dotted taillabel=0]; + Phi_b31 -> Con_28[taillabel=1]; + Phi_b31 -> Con_29[taillabel=2]; + Region32 -> Region30[taillabel=1 color=red]; + Region32 -> If9:p1[taillabel=2 color=red]; + Phi_a33 -> Region32 [style=dotted taillabel=0]; + Phi_a33 -> Con_13[taillabel=1]; + Phi_a33 -> Con_6[taillabel=2]; + Phi_b34 -> Region32 [style=dotted taillabel=0]; + Phi_b34 -> Phi_b31[taillabel=1]; + Phi_b34 -> Con_7[taillabel=2]; + Phi_c35 -> Region32 [style=dotted taillabel=0]; + Phi_c35 -> Phi_c23[taillabel=1]; + Phi_c35 -> Con_8[taillabel=2]; + Add36 -> Phi_c35[taillabel=1]; + Add36 -> Phi_b34[taillabel=2]; + Add37 -> Add36[taillabel=1]; + Add37 -> Phi_a33[taillabel=2]; + Return38 -> Region32[taillabel=0 color=red]; + Return38 -> Add37[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-nonconst.svg b/docs/chapter06/06-graph4-nonconst.svg new file mode 100644 index 00000000..d38c3636 --- /dev/null +++ b/docs/chapter06/06-graph4-nonconst.svg @@ -0,0 +1,456 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter06 Pages: 1 --> +<svg width="506pt" height="908pt" + viewBox="0.00 0.00 506.00 908.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 904)"> +<title>chapter06</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-904 502,-904 502,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-892 490,-892 490,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="266,-855 266,-880 347,-880 347,-855 266,-855"/> +<polygon fill="none" stroke="black" points="266,-855 266,-880 347,-880 347,-855 266,-855"/> +<text text-anchor="start" x="288" y="-863.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="266,-824 266,-855 347,-855 347,-824 266,-824"/> +<polygon fill="yellow" stroke="transparent" points="271,-829 271,-850 311,-850 311,-829 271,-829"/> +<polygon fill="none" stroke="black" points="271,-829 271,-850 311,-850 311,-829 271,-829"/> +<text text-anchor="start" x="274" y="-835.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +<polygon fill="none" stroke="black" points="311,-829 311,-850 342,-850 342,-829 311,-829"/> +<text text-anchor="start" x="314" y="-835.8" font-family="Times,serif" font-size="14.00">arg</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="329,-52 275,-52 275,-16 329,-16 329,-52"/> +<text text-anchor="middle" x="302" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return38 --> +<g id="node26" class="node"> +<title>Return38</title> +<polygon fill="yellow" stroke="black" points="335,-124 269,-124 269,-88 335,-88 335,-124"/> +<text text-anchor="middle" x="302" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return38 --> +<g id="edge1" class="edge"> +<title>Stop3->Return38</title> +<path fill="none" stroke="red" d="M302,-52.3C302,-60.02 302,-69.29 302,-77.89"/> +<polygon fill="red" stroke="red" points="298.5,-77.9 302,-87.9 305.5,-77.9 298.5,-77.9"/> +<text text-anchor="middle" x="299" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="black" cx="351" cy="-394" rx="27" ry="18"/> +<text text-anchor="middle" x="351" y="-390.3" font-family="Times,serif" font-size="14.00">#0</text> +</g> +<!-- Con_7 --> +<g id="node4" class="node"> +<title>Con_7</title> +<ellipse fill="none" stroke="black" cx="207" cy="-394" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-390.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Con_8 --> +<g id="node5" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="black" cx="43" cy="-394" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-390.3" font-family="Times,serif" font-size="14.00">#0</text> +</g> +<!-- If9 --> +<g id="node6" class="node"> +<title>If9</title> +<polygon fill="yellow" stroke="transparent" points="232,-755 232,-780 326,-780 326,-755 232,-755"/> +<polygon fill="none" stroke="black" points="232,-755 232,-780 326,-780 326,-755 232,-755"/> +<text text-anchor="start" x="273.5" y="-763.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="232,-724 232,-755 326,-755 326,-724 232,-724"/> +<polygon fill="yellow" stroke="transparent" points="237,-729 237,-750 277,-750 277,-729 237,-729"/> +<polygon fill="none" stroke="black" points="237,-729 237,-750 277,-750 277,-729 237,-729"/> +<text text-anchor="start" x="240" y="-735.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="277,-729 277,-750 321,-750 321,-729 277,-729"/> +<polygon fill="none" stroke="black" points="277,-729 277,-750 321,-750 321,-729 277,-729"/> +<text text-anchor="start" x="280" y="-735.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If9->Start2 --> +<g id="edge2" class="edge"> +<title>If9->Start2:p0</title> +<path fill="none" stroke="red" d="M286.26,-784.2C288.21,-794.57 289.98,-806.42 290.68,-817.97"/> +<polygon fill="red" stroke="red" points="287.18,-818.12 291,-828 294.18,-817.89 287.18,-818.12"/> +<text text-anchor="middle" x="283.26" y="-786.8" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If9->Start2 --> +<g id="edge3" class="edge"> +<title>If9->Start2:p1</title> +<path fill="none" stroke="black" d="M309.94,-784.28C317.27,-794.18 323.65,-805.76 326.02,-818.03"/> +<polygon fill="black" stroke="black" points="322.54,-818.39 327,-828 329.51,-817.71 322.54,-818.39"/> +<text text-anchor="middle" x="306.94" y="-786.88" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_13 --> +<g id="node7" class="node"> +<title>Con_13</title> +<ellipse fill="none" stroke="black" cx="279" cy="-394" rx="27" ry="18"/> +<text text-anchor="middle" x="279" y="-390.3" font-family="Times,serif" font-size="14.00">#1</text> +</g> +<!-- Con_14 --> +<g id="node8" class="node"> +<title>Con_14</title> +<ellipse fill="none" stroke="black" cx="413" cy="-852" rx="27" ry="18"/> +<text text-anchor="middle" x="413" y="-848.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- EQNode15 --> +<g id="node9" class="node"> +<title>EQNode15</title> +<ellipse fill="none" stroke="black" cx="413" cy="-752" rx="27" ry="18"/> +<text text-anchor="middle" x="413" y="-748.3" font-family="Times,serif" font-size="14.00">==</text> +</g> +<!-- EQNode15->Start2 --> +<g id="edge4" class="edge"> +<title>EQNode15->Start2:p1</title> +<path fill="none" stroke="black" d="M403.94,-769.18C391.81,-790 369.82,-824.8 352.53,-835.66"/> +<polygon fill="black" stroke="black" points="351.28,-832.39 343,-839 353.59,-838.99 351.28,-832.39"/> +<text text-anchor="middle" x="400.94" y="-771.78" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- EQNode15->Con_14 --> +<g id="edge5" class="edge"> +<title>EQNode15->Con_14</title> +<path fill="none" stroke="black" d="M413,-770.07C413,-784.88 413,-806.57 413,-823.77"/> +<polygon fill="black" stroke="black" points="409.5,-823.8 413,-833.8 416.5,-823.8 409.5,-823.8"/> +<text text-anchor="middle" x="410" y="-772.67" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- If16 --> +<g id="node10" class="node"> +<title>If16</title> +<polygon fill="yellow" stroke="transparent" points="380,-655 380,-680 474,-680 474,-655 380,-655"/> +<polygon fill="none" stroke="black" points="380,-655 380,-680 474,-680 474,-655 380,-655"/> +<text text-anchor="start" x="421.5" y="-663.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="380,-624 380,-655 474,-655 474,-624 380,-624"/> +<polygon fill="yellow" stroke="transparent" points="385,-629 385,-650 425,-650 425,-629 385,-629"/> +<polygon fill="none" stroke="black" points="385,-629 385,-650 425,-650 425,-629 385,-629"/> +<text text-anchor="start" x="388" y="-635.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="425,-629 425,-650 469,-650 469,-629 425,-629"/> +<polygon fill="none" stroke="black" points="425,-629 425,-650 469,-650 469,-629 425,-629"/> +<text text-anchor="start" x="428" y="-635.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If16->If9 --> +<g id="edge6" class="edge"> +<title>If16->If9:p0</title> +<path fill="none" stroke="red" d="M371.81,-671.79C331.47,-686.19 280.89,-705.86 263.34,-719.58"/> +<polygon fill="red" stroke="red" points="260.22,-717.91 257,-728 265.81,-722.12 260.22,-717.91"/> +<text text-anchor="middle" x="368.81" y="-665.39" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If16->EQNode15 --> +<g id="edge7" class="edge"> +<title>If16->EQNode15</title> +<path fill="none" stroke="black" d="M422.57,-684.01C420.75,-696.76 418.66,-711.4 416.9,-723.73"/> +<polygon fill="black" stroke="black" points="413.4,-723.48 415.45,-733.87 420.33,-724.47 413.4,-723.48"/> +<text text-anchor="middle" x="419.57" y="-686.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Con_20 --> +<g id="node11" class="node"> +<title>Con_20</title> +<ellipse fill="none" stroke="black" cx="134" cy="-652" rx="27" ry="18"/> +<text text-anchor="middle" x="134" y="-648.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Con_21 --> +<g id="node12" class="node"> +<title>Con_21</title> +<ellipse fill="none" stroke="black" cx="206" cy="-652" rx="27" ry="18"/> +<text text-anchor="middle" x="206" y="-648.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Region22 --> +<g id="node13" class="node"> +<title>Region22</title> +<polygon fill="yellow" stroke="black" points="446,-584 380,-584 380,-548 446,-548 446,-584"/> +<text text-anchor="middle" x="413" y="-562.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region22->If16 --> +<g id="edge8" class="edge"> +<title>Region22->If16:p0</title> +<path fill="none" stroke="red" d="M409.56,-584.01C407.87,-593.54 406.04,-605.9 405.32,-617.98"/> +<polygon fill="red" stroke="red" points="401.82,-617.89 405,-628 408.81,-618.12 401.82,-617.89"/> +<text text-anchor="middle" x="406.56" y="-586.61" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region22->If16 --> +<g id="edge9" class="edge"> +<title>Region22->If16:p1</title> +<path fill="none" stroke="red" d="M428.61,-584.03C435.66,-593.13 443.03,-605.06 445.83,-617.72"/> +<polygon fill="red" stroke="red" points="442.39,-618.46 447,-628 449.35,-617.67 442.39,-618.46"/> +<text text-anchor="middle" x="425.61" y="-586.63" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_c23 --> +<g id="node14" class="node"> +<title>Phi_c23</title> +<ellipse fill="lightyellow" stroke="black" cx="170" cy="-566" rx="27" ry="18"/> +<text text-anchor="middle" x="170" y="-562.3" font-family="Times,serif" font-size="14.00">φ_c</text> +</g> +<!-- Phi_c23->Con_20 --> +<g id="edge11" class="edge"> +<title>Phi_c23->Con_20</title> +<path fill="none" stroke="black" d="M162.89,-583.6C157.81,-595.45 150.88,-611.62 145.08,-625.15"/> +<polygon fill="black" stroke="black" points="141.82,-623.87 141.1,-634.44 148.25,-626.63 141.82,-623.87"/> +<text text-anchor="middle" x="159.89" y="-586.2" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_c23->Con_21 --> +<g id="edge12" class="edge"> +<title>Phi_c23->Con_21</title> +<path fill="none" stroke="black" d="M177.11,-583.6C182.19,-595.45 189.12,-611.62 194.92,-625.15"/> +<polygon fill="black" stroke="black" points="191.75,-626.63 198.9,-634.44 198.18,-623.87 191.75,-626.63"/> +<text text-anchor="middle" x="174.11" y="-586.2" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_c23->Region22 --> +<g id="edge10" class="edge"> +<title>Phi_c23->Region22</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M197.05,-566C254.48,-566 311.91,-566 369.34,-566"/> +<polygon fill="black" stroke="black" points="369.68,-569.5 379.68,-566 369.68,-562.5 369.68,-569.5"/> +<text text-anchor="middle" x="200.05" y="-559.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- If24 --> +<g id="node15" class="node"> +<title>If24</title> +<polygon fill="yellow" stroke="transparent" points="375,-483 375,-508 469,-508 469,-483 375,-483"/> +<polygon fill="none" stroke="black" points="375,-483 375,-508 469,-508 469,-483 375,-483"/> +<text text-anchor="start" x="416.5" y="-491.8" font-family="Times,serif" font-size="14.00">If</text> +<polygon fill="none" stroke="black" points="375,-452 375,-483 469,-483 469,-452 375,-452"/> +<polygon fill="yellow" stroke="transparent" points="380,-457 380,-478 420,-478 420,-457 380,-457"/> +<polygon fill="none" stroke="black" points="380,-457 380,-478 420,-478 420,-457 380,-457"/> +<text text-anchor="start" x="383" y="-463.8" font-family="Times,serif" font-size="14.00">True</text> +<polygon fill="yellow" stroke="transparent" points="420,-457 420,-478 464,-478 464,-457 420,-457"/> +<polygon fill="none" stroke="black" points="420,-457 420,-478 464,-478 464,-457 420,-457"/> +<text text-anchor="start" x="423" y="-463.8" font-family="Times,serif" font-size="14.00">False</text> +</g> +<!-- If24->Start2 --> +<g id="edge14" class="edge"> +<title>If24->Start2:p1</title> +<path fill="none" stroke="black" d="M392.77,-512.23C384.4,-522.84 376.15,-535.26 371,-548 331.39,-645.92 367.43,-681.24 343,-784 339.09,-800.45 330.97,-805.48 328.06,-817.95"/> +<polygon fill="black" stroke="black" points="324.57,-817.69 327,-828 331.53,-818.42 324.57,-817.69"/> +<text text-anchor="middle" x="389.77" y="-514.83" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- If24->Region22 --> +<g id="edge13" class="edge"> +<title>If24->Region22</title> +<path fill="none" stroke="red" d="M418.65,-512.28C417.76,-520.58 416.81,-529.48 415.94,-537.56"/> +<polygon fill="red" stroke="red" points="412.45,-537.28 414.86,-547.6 419.41,-538.02 412.45,-537.28"/> +<text text-anchor="middle" x="415.65" y="-514.88" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_28 --> +<g id="node16" class="node"> +<title>Con_28</title> +<ellipse fill="none" stroke="black" cx="135" cy="-480" rx="27" ry="18"/> +<text text-anchor="middle" x="135" y="-476.3" font-family="Times,serif" font-size="14.00">#2</text> +</g> +<!-- Con_29 --> +<g id="node17" class="node"> +<title>Con_29</title> +<ellipse fill="none" stroke="black" cx="207" cy="-480" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-476.3" font-family="Times,serif" font-size="14.00">#3</text> +</g> +<!-- Region30 --> +<g id="node18" class="node"> +<title>Region30</title> +<polygon fill="yellow" stroke="black" points="482,-412 416,-412 416,-376 482,-376 482,-412"/> +<text text-anchor="middle" x="449" y="-390.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region30->If24 --> +<g id="edge15" class="edge"> +<title>Region30->If24:p0</title> +<path fill="none" stroke="red" d="M424.79,-412.2C414.85,-420.99 404.86,-432.65 401.33,-446"/> +<polygon fill="red" stroke="red" points="397.85,-445.63 400,-456 404.79,-446.55 397.85,-445.63"/> +<text text-anchor="middle" x="421.79" y="-414.8" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Region30->If24 --> +<g id="edge16" class="edge"> +<title>Region30->If24:p1</title> +<path fill="none" stroke="red" d="M445.99,-412.03C444.51,-421.56 442.91,-433.93 442.28,-446"/> +<polygon fill="red" stroke="red" points="438.78,-445.91 442,-456 445.78,-446.1 438.78,-445.91"/> +<text text-anchor="middle" x="442.99" y="-414.63" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_b31 --> +<g id="node19" class="node"> +<title>Phi_b31</title> +<ellipse fill="lightyellow" stroke="black" cx="135" cy="-394" rx="27.1" ry="18"/> +<text text-anchor="middle" x="135" y="-390.3" font-family="Times,serif" font-size="14.00">φ_b</text> +</g> +<!-- Phi_b31->Con_28 --> +<g id="edge18" class="edge"> +<title>Phi_b31->Con_28</title> +<path fill="none" stroke="black" d="M135,-412.4C135,-423.74 135,-438.77 135,-451.68"/> +<polygon fill="black" stroke="black" points="131.5,-451.9 135,-461.9 138.5,-451.9 131.5,-451.9"/> +<text text-anchor="middle" x="132" y="-415" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_b31->Con_29 --> +<g id="edge19" class="edge"> +<title>Phi_b31->Con_29</title> +<path fill="none" stroke="black" d="M147.87,-410.02C158.93,-422.92 175.04,-441.71 187.65,-456.42"/> +<polygon fill="black" stroke="black" points="185.07,-458.8 194.24,-464.11 190.39,-454.24 185.07,-458.8"/> +<text text-anchor="middle" x="144.87" y="-412.62" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_b31->Region30 --> +<g id="edge17" class="edge"> +<title>Phi_b31->Region30</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M149.22,-378.43C157.37,-370.68 168.29,-362.11 180,-358 224.67,-342.33 347.58,-344.66 393,-358 401.94,-360.63 410.81,-365.17 418.76,-370.16"/> +<polygon fill="black" stroke="black" points="417.05,-373.23 427.3,-375.91 420.96,-367.43 417.05,-373.23"/> +<text text-anchor="middle" x="146.22" y="-372.03" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Region32 --> +<g id="node20" class="node"> +<title>Region32</title> +<polygon fill="yellow" stroke="black" points="390,-340 324,-340 324,-304 390,-304 390,-340"/> +<text text-anchor="middle" x="357" y="-318.3" font-family="Times,serif" font-size="14.00">Region</text> +</g> +<!-- Region32->If9 --> +<g id="edge21" class="edge"> +<title>Region32->If9:p1</title> +<path fill="none" stroke="red" d="M369.73,-340.15C376.29,-350.08 383.61,-363.12 387,-376 391.08,-391.47 392.32,-396.91 387,-412 380.17,-431.38 366.81,-429.44 358,-448 304.99,-559.76 299.28,-598.69 299.01,-717.76"/> +<polygon fill="red" stroke="red" points="295.51,-718 299,-728 302.51,-718 295.51,-718"/> +<text text-anchor="middle" x="366.73" y="-342.75" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Region32->Region30 --> +<g id="edge20" class="edge"> +<title>Region32->Region30</title> +<path fill="none" stroke="red" d="M379.74,-340.3C391.44,-349.2 405.86,-360.18 418.51,-369.8"/> +<polygon fill="red" stroke="red" points="416.44,-372.63 426.52,-375.9 420.68,-367.06 416.44,-372.63"/> +<text text-anchor="middle" x="376.74" y="-342.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a33 --> +<g id="node21" class="node"> +<title>Phi_a33</title> +<ellipse fill="lightyellow" stroke="black" cx="279" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="279" y="-318.3" font-family="Times,serif" font-size="14.00">φ_a</text> +</g> +<!-- Phi_a33->Con_6 --> +<g id="edge24" class="edge"> +<title>Phi_a33->Con_6</title> +<path fill="none" stroke="black" d="M293.57,-337.17C303.75,-347.06 317.52,-360.45 329.03,-371.64"/> +<polygon fill="black" stroke="black" points="326.59,-374.15 336.2,-378.62 331.47,-369.13 326.59,-374.15"/> +<text text-anchor="middle" x="290.57" y="-339.77" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_a33->Con_13 --> +<g id="edge23" class="edge"> +<title>Phi_a33->Con_13</title> +<path fill="none" stroke="black" d="M279,-340.3C279,-348.02 279,-357.29 279,-365.89"/> +<polygon fill="black" stroke="black" points="275.5,-365.9 279,-375.9 282.5,-365.9 275.5,-365.9"/> +<text text-anchor="middle" x="276" y="-342.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_a33->Region32 --> +<g id="edge22" class="edge"> +<title>Phi_a33->Region32</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M306.12,-322C308.58,-322 311.04,-322 313.5,-322"/> +<polygon fill="black" stroke="black" points="313.61,-325.5 323.61,-322 313.61,-318.5 313.61,-325.5"/> +<text text-anchor="middle" x="309.12" y="-315.6" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Phi_b34 --> +<g id="node22" class="node"> +<title>Phi_b34</title> +<ellipse fill="lightyellow" stroke="black" cx="207" cy="-322" rx="27.1" ry="18"/> +<text text-anchor="middle" x="207" y="-318.3" font-family="Times,serif" font-size="14.00">φ_b</text> +</g> +<!-- Phi_b34->Con_7 --> +<g id="edge27" class="edge"> +<title>Phi_b34->Con_7</title> +<path fill="none" stroke="black" d="M207,-340.3C207,-348.02 207,-357.29 207,-365.89"/> +<polygon fill="black" stroke="black" points="203.5,-365.9 207,-375.9 210.5,-365.9 203.5,-365.9"/> +<text text-anchor="middle" x="204" y="-342.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_b34->Phi_b31 --> +<g id="edge26" class="edge"> +<title>Phi_b34->Phi_b31</title> +<path fill="none" stroke="black" d="M192.08,-337.5C182.04,-347.27 168.62,-360.31 157.32,-371.3"/> +<polygon fill="black" stroke="black" points="154.63,-369.03 149.9,-378.51 159.51,-374.05 154.63,-369.03"/> +<text text-anchor="middle" x="189.08" y="-340.1" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_b34->Region32 --> +<g id="edge25" class="edge"> +<title>Phi_b34->Region32</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M221.22,-306.43C229.37,-298.68 240.29,-290.11 252,-286 274.65,-278.06 283.12,-278.74 306,-286 313.99,-288.54 321.81,-292.83 328.83,-297.58"/> +<polygon fill="black" stroke="black" points="327.11,-300.66 337.24,-303.75 331.25,-295.01 327.11,-300.66"/> +<text text-anchor="middle" x="218.22" y="-300.03" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Phi_c35 --> +<g id="node23" class="node"> +<title>Phi_c35</title> +<ellipse fill="lightyellow" stroke="black" cx="112" cy="-322" rx="27" ry="18"/> +<text text-anchor="middle" x="112" y="-318.3" font-family="Times,serif" font-size="14.00">φ_c</text> +</g> +<!-- Phi_c35->Con_8 --> +<g id="edge30" class="edge"> +<title>Phi_c35->Con_8</title> +<path fill="none" stroke="black" d="M97.7,-337.5C88.08,-347.27 75.22,-360.31 64.39,-371.3"/> +<polygon fill="black" stroke="black" points="61.81,-368.94 57.28,-378.51 66.79,-373.85 61.81,-368.94"/> +<text text-anchor="middle" x="94.7" y="-340.1" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Phi_c35->Phi_c23 --> +<g id="edge29" class="edge"> +<title>Phi_c35->Phi_c23</title> +<path fill="none" stroke="black" d="M105.53,-339.52C93.19,-373.79 70.03,-454.23 99,-512 107.39,-528.74 123.86,-541.54 138.82,-550.37"/> +<polygon fill="black" stroke="black" points="137.41,-553.59 147.86,-555.35 140.79,-547.46 137.41,-553.59"/> +<text text-anchor="middle" x="102.53" y="-342.12" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Phi_c35->Region32 --> +<g id="edge28" class="edge"> +<title>Phi_c35->Region32</title> +<path fill="none" stroke="black" stroke-dasharray="1,5" d="M130.62,-308.94C143.75,-300.56 162.11,-290.44 180,-286 234.35,-272.5 252.62,-269.06 306,-286 313.99,-288.54 321.81,-292.83 328.83,-297.58"/> +<polygon fill="black" stroke="black" points="327.11,-300.66 337.24,-303.75 331.25,-295.01 327.11,-300.66"/> +<text text-anchor="middle" x="127.62" y="-302.54" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Add36 --> +<g id="node24" class="node"> +<title>Add36</title> +<ellipse fill="none" stroke="black" cx="207" cy="-250" rx="27" ry="18"/> +<text text-anchor="middle" x="207" y="-246.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add36->Phi_b34 --> +<g id="edge32" class="edge"> +<title>Add36->Phi_b34</title> +<path fill="none" stroke="black" d="M207,-268.3C207,-276.02 207,-285.29 207,-293.89"/> +<polygon fill="black" stroke="black" points="203.5,-293.9 207,-303.9 210.5,-293.9 203.5,-293.9"/> +<text text-anchor="middle" x="204" y="-270.9" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Add36->Phi_c35 --> +<g id="edge31" class="edge"> +<title>Add36->Phi_c35</title> +<path fill="none" stroke="black" d="M189.58,-263.84C175.07,-274.53 154.21,-289.9 137.77,-302.01"/> +<polygon fill="black" stroke="black" points="135.61,-299.26 129.64,-308.01 139.76,-304.89 135.61,-299.26"/> +<text text-anchor="middle" x="186.58" y="-266.44" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Add37 --> +<g id="node25" class="node"> +<title>Add37</title> +<ellipse fill="none" stroke="black" cx="279" cy="-178" rx="27" ry="18"/> +<text text-anchor="middle" x="279" y="-174.3" font-family="Times,serif" font-size="14.00">+</text> +</g> +<!-- Add37->Phi_a33 --> +<g id="edge34" class="edge"> +<title>Add37->Phi_a33</title> +<path fill="none" stroke="black" d="M279,-196.13C279,-220.33 279,-264.79 279,-293.61"/> +<polygon fill="black" stroke="black" points="275.5,-293.81 279,-303.81 282.5,-293.81 275.5,-293.81"/> +<text text-anchor="middle" x="276" y="-198.73" font-family="Helvetica,sans-Serif" font-size="8.00">2</text> +</g> +<!-- Add37->Add36 --> +<g id="edge33" class="edge"> +<title>Add37->Add36</title> +<path fill="none" stroke="black" d="M264.43,-193.17C254.25,-203.06 240.48,-216.45 228.97,-227.64"/> +<polygon fill="black" stroke="black" points="226.53,-225.13 221.8,-234.62 231.41,-230.15 226.53,-225.13"/> +<text text-anchor="middle" x="261.43" y="-195.77" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +<!-- Return38->Region32 --> +<g id="edge35" class="edge"> +<title>Return38->Region32</title> +<path fill="none" stroke="red" d="M306.41,-124.15C315.94,-161.25 338.54,-249.19 350.03,-293.9"/> +<polygon fill="red" stroke="red" points="346.69,-294.95 352.57,-303.77 353.47,-293.21 346.69,-294.95"/> +<text text-anchor="middle" x="303.41" y="-126.75" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return38->Add37 --> +<g id="edge36" class="edge"> +<title>Return38->Add37</title> +<path fill="none" stroke="black" d="M296.31,-124.3C293.75,-132.1 290.67,-141.49 287.82,-150.17"/> +<polygon fill="black" stroke="black" points="284.42,-149.3 284.62,-159.9 291.07,-151.49 284.42,-149.3"/> +<text text-anchor="middle" x="293.31" y="-126.9" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter06/06-graph4-true.gv b/docs/chapter06/06-graph4-true.gv new file mode 100644 index 00000000..6e48ee7d --- /dev/null +++ b/docs/chapter06/06-graph4-true.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="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_44 [ label="#6" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-true.svg b/docs/chapter06/06-graph4-true.svg new file mode 100644 index 00000000..a533ea21 --- /dev/null +++ b/docs/chapter06/06-graph4-true.svg @@ -0,0 +1,67 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.43.0 (0) + --> +<!-- Title: chapter06 Pages: 1 --> +<svg width="178pt" height="248pt" + viewBox="0.00 0.00 178.00 248.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 244)"> +<title>chapter06</title> +<polygon fill="white" stroke="transparent" points="-4,4 -4,-244 174,-244 174,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="black" points="8,-8 8,-232 162,-232 162,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="yellow" stroke="transparent" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<polygon fill="none" stroke="black" points="24,-195 24,-220 74,-220 74,-195 24,-195"/> +<text text-anchor="start" x="30.5" y="-203.8" font-family="Times,serif" font-size="14.00">Start</text> +<polygon fill="none" stroke="black" points="24,-164 24,-195 74,-195 74,-164 24,-164"/> +<polygon fill="yellow" stroke="transparent" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<polygon fill="none" stroke="black" points="29,-169 29,-190 69,-190 69,-169 29,-169"/> +<text text-anchor="start" x="32" y="-175.8" font-family="Times,serif" font-size="14.00">$ctrl</text> +</g> +<!-- Stop3 --> +<g id="node2" class="node"> +<title>Stop3</title> +<polygon fill="yellow" stroke="black" points="112,-52 58,-52 58,-16 112,-16 112,-52"/> +<text text-anchor="middle" x="85" y="-30.3" font-family="Times,serif" font-size="14.00">Stop</text> +</g> +<!-- Return45 --> +<g id="node4" class="node"> +<title>Return45</title> +<polygon fill="yellow" stroke="black" points="118,-124 52,-124 52,-88 118,-88 118,-124"/> +<text text-anchor="middle" x="85" y="-102.3" font-family="Times,serif" font-size="14.00">Return</text> +</g> +<!-- Stop3->Return45 --> +<g id="edge1" class="edge"> +<title>Stop3->Return45</title> +<path fill="none" stroke="red" d="M85,-52.3C85,-60.02 85,-69.29 85,-77.89"/> +<polygon fill="red" stroke="red" points="81.5,-77.9 85,-87.9 88.5,-77.9 81.5,-77.9"/> +<text text-anchor="middle" x="82" y="-54.9" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Con_44 --> +<g id="node3" class="node"> +<title>Con_44</title> +<ellipse fill="none" stroke="black" cx="127" cy="-192" rx="27" ry="18"/> +<text text-anchor="middle" x="127" y="-188.3" font-family="Times,serif" font-size="14.00">#6</text> +</g> +<!-- Return45->Start2 --> +<g id="edge2" class="edge"> +<title>Return45->Start2:p0</title> +<path fill="none" stroke="red" d="M68.26,-124.13C60.77,-133.26 52.99,-145.23 50.13,-158.06"/> +<polygon fill="red" stroke="red" points="46.66,-157.67 49,-168 53.61,-158.46 46.66,-157.67"/> +<text text-anchor="middle" x="65.26" y="-126.73" font-family="Helvetica,sans-Serif" font-size="8.00">0</text> +</g> +<!-- Return45->Con_44 --> +<g id="edge3" class="edge"> +<title>Return45->Con_44</title> +<path fill="none" stroke="black" d="M93.7,-124.4C99.66,-136.31 107.65,-152.3 114.31,-165.62"/> +<polygon fill="black" stroke="black" points="111.28,-167.38 118.88,-174.76 117.54,-164.25 111.28,-167.38"/> +<text text-anchor="middle" x="90.7" y="-127" font-family="Helvetica,sans-Serif" font-size="8.00">1</text> +</g> +</g> +</svg> diff --git a/docs/chapter06/Makefile b/docs/chapter06/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter06/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter06/README.md b/docs/chapter06/README.md new file mode 100644 index 00000000..0f3ef945 --- /dev/null +++ b/docs/chapter06/README.md @@ -0,0 +1,203 @@ +# Chapter 6: Peepholes for If + +[Previous: Chapter 5](../chapter05/README.md) | +[Next: Chapter 7](../chapter07/README.md) + +# Table of Contents + +1. [Type System Revision](#type-system-revision) +2. [Peephole of `if`](#peephole-of-if) +3. [`Region` and `Phi`](#region-and-phi) +4. [Discussion](#discussion) +5. [Expanding Peephole Beyond Constant Expressions](#expanding-peephole-beyond-constant-expressions) +6. [Dominators](#dominators) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter06) 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-chapter05...linear-chapter06) it to the previous chapter. + +In this chapter we do not add new language features. Our goal is to add peephole optimization to `if` statements. + + +## Type System Revision + +We now need to extend the type system to introduce another lattice structure, in addition to the Integer sub-lattice. +As before we denote "Top" by T and "Bottom" by ⊥. + +* "Ctrl" represents a live control, whereas "~Ctrl" represents a dead control. +* "INT" refers to an integer value, note that integer values have their own sub-lattice. + +| | ⊥ | Ctrl | ~Ctrl | T | INT | +|-------|---|------|-------|-------|-----| +| T | ⊥ | Ctrl | ~Ctrl | T | INT | +| Ctrl | ⊥ | Ctrl | Ctrl | Ctrl | ⊥ | +| ~Ctrl | ⊥ | Ctrl | ~Ctrl | ~Ctrl | ⊥ | +| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | + +* "Top" meets any type is that type, +* "Bottom" meets any type is "Bottom", +* "Top", "Bottom", "Ctrl", "~Ctrl" are classed as simple types, +* "Ctrl" meets "~Ctrl" is "Ctrl" +* Unless covered above, a simple type meets non-simple results in "Bottom" + +The entire revised Lattice is shown below: + + + + +## Peephole of `if` + +* Our general strategy is to continue parsing the entire `if` statement even if we know that one branch is dead. +* This approach creates dead nodes which get cleaned up by dead code + elimination. The benefits are that we do not introduce special logic during + parsing, the normal graph building machinery takes care of cleaning up dead + nodes. +* When we peephole an `If` node we test if the predicate is a constant. If so, + then one branch or the other is dead, depending on if the constant is `0` or not. +* When we add the `Proj` nodes, in this scenario, we already know one of the projections is dead. The peephole of the + relevant `Proj` node replaces the `Proj` with a `Constant` of type "~Ctrl" indicating dead control. +* At this point our dead code elimination would kill the `If` node since it has no uses + - but we cannot do that because we need to continue the parse. The + important observation is that *we __can__ kill the `If` node after __both__ + the `Proj` nodes have been created*, because any subsequent control flow can + only see the `Proj` nodes. +* To ensure this, we add a dummy user to `If` before creating the first `Proj` and remove it immediately after, allowing the + second `Proj` to trigger a dead code elimination of the `If`. +* The live `Proj` gets replaced by the parent of `If`, whereas the dead `Proj` gets replaced by "~Ctrl". +* The parsing then continues as normal. +* The other changes are when we reach the merge point with a dead control. +* Again keeping with our strategy we merge as normal, including creating `Phi` nodes. +* The `Region` may have one of its inputs as "~Ctrl". This will be seen + by the `Phi` which then optimizes itself. If the `Phi` has just one live + input, the `Phi` peephole replaces itself with the remaining input. +* Finally, at the end, when the `Region` node is peepholed, we see that it has only one live input and no Phi uses + and can be replaced with its one live input. + +## `Region` and `Phi` + +One of the invariants we maintain is that for each control input to a +`Region` every `Phi` has a 1-to-1 relationship with a data input. Thus, if a +`Region` loses a control input, every `Phi`'s corresponding data input must be +deleted. Conversely, we cannot collapse a Region until it has no dependent +`Phi`s. + +When processing `If` we do not remove control inputs to a `Region`, instead the +dead control input is simply set to `Constant(~Ctrl)`. The peephole logic in +a `Phi` notices this and replaces itself with the live input. + +## Discussion + +With the changes above, our peephole optimization is able to fold dead code when +an `if` statement has a condition that evaluates to `true` or `false` at compile time. + +Let's look at a simple example below: + +```java +if( true ) return 2; +return 1; +``` + +Before peephole: + + + +After peephole: + + + +Another example: + +```java +int a=1; +if( true ) + a=2; +else + a=3; +return a; +``` + +Before peephole: + + + +After peephole: + + + +## Expanding Peephole Beyond Constant Expressions + +While our peephole of the `CFG` collapses dead code when the expression is +a compile-time constant, it does not do as well as it could with the following example: + +```java +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +``` + +In this example, `arg` is defined externally, and we have to assume it is not a constant. +However, the code repeats the `if( arg )` condition in the inner `if` statement. +We know that if the outer `if( arg )` is true, then the *inner `if` must also evaluate to true*. + +Our peephole at present cannot see this: + + + +What we would like is for our peephole to see that the inner `if` is fully determined by the +outer `if` and thus, the code can be simplified as follows: + +```java +int a = 0; +int b = 1; +if ( arg ) { + a = 2; + b = 2; +} +return a+b; +``` + +That is, the final outcome is either `4` if `arg` happens to be true, or `1` if `arg` happens to be false. + +## Dominators + +The key to implementing this peephole is the observation that the inner `if` is completely determined by the +outer `if`. In compiler parlance, we say that the outer `if` dominates the inner `if`. + +There is a generic way to determine this type of domination; it involves constructing a dominator +tree. For details of how to do this, please refer to the paper `A Simple, Fast Dominance Algorithm`.[^1] + +However, constructing a dominator tree is an expensive operation; one that we would not like to +do in the middle of parsing. Fortunately, since we do not have loops yet, we do not +have back edges in our control flow graph. Our control flow graph is essentially hierarchical, tree like. +Thus, a simple form of dominator identification is possible. + +The main idea is that we can assign a `depth` to each control node, this represents the node's depth +in the hierarchy. We can compute this depth incrementally as we need to. The nodes that are deeper in the hierarchy +have a greater depth than the ones above. + +Secondly we know that for our control nodes, except for `Region`s, there is only one incoming control edge, +which means that most control nodes have a single immediate dominating control node. `Region` nodes are different +as they can have one or more control edges; but, we know that for `if` statements, a `Region` node has exactly two +control inputs, one from each branch of the `if`. To find the immediate dominator of a `Region` node in the +limited scenario of an `if`, we can follow the immediate dominator of each branch until we find the common ancestor +node that dominates both the branches. + +If this ancestor node is also an `if` and its predicate is the same as the current `if`, then we know that +the outcome of the present `if` is fully determined. + +The code that does this check is in the [`compute` method of the `if`](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java#L38-L45). + +The `idom` method in `Node` provides a default implementation of the depth based immediate dominator calculation. +`Region` [overrides this](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java#L57-L74) to implement the more complex search described above. + +It turns out that to simplify the example above, we need a [further peephole in our `Add` node](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java#L64-L67). + +With all these changes, the outcome of the peephole is just what we would like to see! + + + +[^1]: Cooper, K. D. Cooper, Harvey, T. J., and Kennedy, K. (2001). + A Simple, Fast Dominance Algorithm. diff --git a/docs/chapter06/lattice.gv b/docs/chapter06/lattice.gv new file mode 100644 index 00000000..e5cc59be --- /dev/null +++ b/docs/chapter06/lattice.gv @@ -0,0 +1,97 @@ +digraph Lattice { + // Define nodes + splines=false; + node [shape=circle, style=filled, fillcolor=lightblue]; + nodesep=0.6; + + TOP [label=<<B>⊤</B >>, fillcolor=black, fontcolor=white]; + BOT [label=<<B>⊥</B>>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<<B>⊤</B >:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<<B>⊥</B>:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + TOP -> INT_TOP; + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + INT_BOT -> BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<<B>⊤</B >:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<<B>⊥</B>:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLE2 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLEN [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">...</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // Additional customization + {rank=same; TOP} + {rank=same; XCTRL; INT_TOP; TUPLE_TOP} + {rank=same; + INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; + } + {rank=same; CTRL; INT_BOT, TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter06/lattice.svg b/docs/chapter06/lattice.svg new file mode 100644 index 00000000..86371c93 --- /dev/null +++ b/docs/chapter06/lattice.svg @@ -0,0 +1,319 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="855pt" height="406pt"
+ viewBox="0.00 0.00 854.60 406.50" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 402.5)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-402.5 850.6,-402.5 850.6,4 -4,4"/>
+<!-- TOP -->
+<g id="node1" class="node">
+<title>TOP</title>
+<ellipse fill="black" stroke="black" cx="276.6" cy="-377.37" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="268.72" y="-372.95" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+</g>
+<!-- XCTRL -->
+<g id="node3" class="node">
+<title>XCTRL</title>
+<ellipse fill="yellow" stroke="black" cx="49.6" cy="-302.25" rx="36.51" ry="18"/>
+<text text-anchor="start" x="30.85" y="-298.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="46.6" y="-298.2" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- TOP->XCTRL -->
+<g id="edge1" class="edge">
+<title>TOP->XCTRL</title>
+<path fill="none" stroke="black" d="M256.45,-369.88C219.31,-357.92 139.36,-332.16 90.45,-316.41"/>
+<polygon fill="black" stroke="black" points="91.65,-313.12 81.06,-313.38 89.51,-319.78 91.65,-313.12"/>
+</g>
+<!-- INT_TOP -->
+<g id="node5" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-302.25" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-298.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="275.47" y="-298.2" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- TOP->INT_TOP -->
+<g id="edge4" class="edge">
+<title>TOP->INT_TOP</title>
+<path fill="none" stroke="black" d="M276.6,-356C276.6,-348.51 276.6,-339.87 276.6,-331.79"/>
+<polygon fill="black" stroke="black" points="280.1,-332.05 276.6,-322.05 273.1,-332.05 280.1,-332.05"/>
+</g>
+<!-- TUPLE_TOP -->
+<g id="node14" class="node">
+<title>TUPLE_TOP</title>
+<ellipse fill="pink" stroke="black" cx="673.6" cy="-302.25" rx="42.65" ry="18"/>
+<text text-anchor="start" x="650.35" y="-298.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="666.1" y="-298.2" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TOP->TUPLE_TOP -->
+<g id="edge26" class="edge">
+<title>TOP->TUPLE_TOP</title>
+<path fill="none" stroke="black" d="M297.66,-372.49C358.57,-361.27 536.1,-328.57 623.62,-312.45"/>
+<polygon fill="black" stroke="black" points="624.16,-315.91 633.36,-310.66 622.89,-309.03 624.16,-315.91"/>
+</g>
+<!-- BOT -->
+<g id="node2" class="node">
+<title>BOT</title>
+<ellipse fill="black" stroke="black" cx="276.6" cy="-21.12" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="268.72" y="-16.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+</g>
+<!-- CTRL -->
+<g id="node4" class="node">
+<title>CTRL</title>
+<ellipse fill="yellow" stroke="black" cx="49.6" cy="-96.25" rx="36.51" ry="18"/>
+<text text-anchor="start" x="30.85" y="-92.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="46.6" y="-92.2" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text>
+</g>
+<!-- XCTRL->CTRL -->
+<g id="edge2" class="edge">
+<title>XCTRL->CTRL</title>
+<path fill="none" stroke="black" d="M49.6,-283.97C49.6,-248.31 49.6,-169.19 49.6,-125.93"/>
+<polygon fill="black" stroke="black" points="53.1,-126 49.6,-116 46.1,-126 53.1,-126"/>
+</g>
+<!-- CTRL->BOT -->
+<g id="edge3" class="edge">
+<title>CTRL->BOT</title>
+<path fill="none" stroke="black" d="M79.74,-85.54C122.92,-71.63 201.96,-46.17 245.6,-32.11"/>
+<polygon fill="black" stroke="black" points="246.52,-35.49 254.96,-29.09 244.37,-28.83 246.52,-35.49"/>
+</g>
+<!-- INT_MIN -->
+<g id="node7" class="node">
+<title>INT_MIN</title>
+<ellipse fill="lightblue" stroke="black" cx="18.6" cy="-199.25" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="18.6" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">-n</text>
+</g>
+<!-- INT_TOP->INT_MIN -->
+<g id="edge5" class="edge">
+<title>INT_TOP->INT_MIN</title>
+<path fill="none" stroke="black" d="M249.96,-290.82C200.87,-271.6 96.58,-230.78 46.53,-211.18"/>
+<polygon fill="black" stroke="black" points="47.87,-207.95 37.29,-207.56 45.32,-214.47 47.87,-207.95"/>
+</g>
+<!-- INT_MINDOTS -->
+<g id="node8" class="node">
+<title>INT_MINDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="107.6" cy="-199.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="107.6" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MINDOTS -->
+<g id="edge6" class="edge">
+<title>INT_TOP->INT_MINDOTS</title>
+<path fill="none" stroke="black" d="M254.85,-288.25C224.79,-270.29 170.48,-237.83 136.88,-217.75"/>
+<polygon fill="black" stroke="black" points="138.84,-214.85 128.46,-212.72 135.25,-220.85 138.84,-214.85"/>
+</g>
+<!-- INT_MINUS -->
+<g id="node9" class="node">
+<title>INT_MINUS</title>
+<ellipse fill="lightblue" stroke="black" cx="196.6" cy="-199.25" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="196.6" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">-1</text>
+</g>
+<!-- INT_TOP->INT_MINUS -->
+<g id="edge7" class="edge">
+<title>INT_TOP->INT_MINUS</title>
+<path fill="none" stroke="black" d="M264.1,-285.47C250.86,-268.76 229.85,-242.23 214.78,-223.21"/>
+<polygon fill="black" stroke="black" points="217.61,-221.14 208.66,-215.48 212.12,-225.49 217.61,-221.14"/>
+</g>
+<!-- INT_ZERO -->
+<g id="node10" class="node">
+<title>INT_ZERO</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-199.25" rx="18" ry="18"/>
+<text text-anchor="middle" x="276.6" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_TOP->INT_ZERO -->
+<g id="edge8" class="edge">
+<title>INT_TOP->INT_ZERO</title>
+<path fill="none" stroke="black" d="M276.6,-284.12C276.6,-269.02 276.6,-246.74 276.6,-228.93"/>
+<polygon fill="black" stroke="black" points="280.1,-228.98 276.6,-218.98 273.1,-228.98 280.1,-228.98"/>
+</g>
+<!-- INT_PLUS -->
+<g id="node11" class="node">
+<title>INT_PLUS</title>
+<ellipse fill="lightblue" stroke="black" cx="355.6" cy="-199.25" rx="18" ry="18"/>
+<text text-anchor="middle" x="355.6" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">1</text>
+</g>
+<!-- INT_TOP->INT_PLUS -->
+<g id="edge9" class="edge">
+<title>INT_TOP->INT_PLUS</title>
+<path fill="none" stroke="black" d="M288.94,-285.47C302.08,-268.67 323,-241.93 337.89,-222.88"/>
+<polygon fill="black" stroke="black" points="340.52,-225.2 343.93,-215.17 335.01,-220.89 340.52,-225.2"/>
+</g>
+<!-- INT_MAXDOTS -->
+<g id="node12" class="node">
+<title>INT_MAXDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="443.6" cy="-199.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="443.6" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MAXDOTS -->
+<g id="edge10" class="edge">
+<title>INT_TOP->INT_MAXDOTS</title>
+<path fill="none" stroke="black" d="M298.43,-288.04C328.15,-270.07 381.44,-237.84 414.52,-217.83"/>
+<polygon fill="black" stroke="black" points="416.05,-221 422.8,-212.83 412.43,-215.01 416.05,-221"/>
+</g>
+<!-- INT_MAX -->
+<g id="node13" class="node">
+<title>INT_MAX</title>
+<ellipse fill="lightblue" stroke="black" cx="534.6" cy="-199.25" rx="21.15" ry="21.15"/>
+<text text-anchor="middle" x="534.6" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">+n</text>
+</g>
+<!-- INT_TOP->INT_MAX -->
+<g id="edge11" class="edge">
+<title>INT_TOP->INT_MAX</title>
+<path fill="none" stroke="black" d="M303.23,-290.82C351.59,-271.89 453.51,-231.99 504.38,-212.08"/>
+<polygon fill="black" stroke="black" points="505.55,-215.38 513.59,-208.47 503,-208.86 505.55,-215.38"/>
+</g>
+<!-- INT_BOT -->
+<g id="node6" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-96.25" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-92.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="275.47" y="-92.2" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_BOT->BOT -->
+<g id="edge19" class="edge">
+<title>INT_BOT->BOT</title>
+<path fill="none" stroke="black" d="M276.6,-77.92C276.6,-70.74 276.6,-62.18 276.6,-53.95"/>
+<polygon fill="black" stroke="black" points="280.1,-54.22 276.6,-44.22 273.1,-54.22 280.1,-54.22"/>
+</g>
+<!-- INT_MIN->INT_BOT -->
+<g id="edge12" class="edge">
+<title>INT_MIN->INT_BOT</title>
+<path fill="none" stroke="black" d="M35.92,-191.46C77.34,-175.25 182.81,-133.96 239.39,-111.81"/>
+<polygon fill="black" stroke="black" points="240.58,-115.11 248.62,-108.2 238.03,-108.59 240.58,-115.11"/>
+</g>
+<!-- INT_MIN->INT_MINDOTS -->
+<!-- INT_MINDOTS->INT_BOT -->
+<g id="edge13" class="edge">
+<title>INT_MINDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M127.31,-186.46C156.24,-169.18 210.48,-136.76 245,-116.13"/>
+<polygon fill="black" stroke="black" points="246.52,-119.3 253.3,-111.17 242.93,-113.29 246.52,-119.3"/>
+</g>
+<!-- INT_MINDOTS->INT_MINUS -->
+<!-- INT_MINUS->INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_MINUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M207.72,-184.2C220.41,-168.18 241.41,-141.67 256.89,-122.13"/>
+<polygon fill="black" stroke="black" points="259.58,-124.37 263.05,-114.35 254.09,-120.02 259.58,-124.37"/>
+</g>
+<!-- INT_MINUS->INT_ZERO -->
+<!-- INT_ZERO->INT_BOT -->
+<g id="edge15" class="edge">
+<title>INT_ZERO->INT_BOT</title>
+<path fill="none" stroke="black" d="M276.6,-181.12C276.6,-166.02 276.6,-143.74 276.6,-125.93"/>
+<polygon fill="black" stroke="black" points="280.1,-125.98 276.6,-115.98 273.1,-125.98 280.1,-125.98"/>
+</g>
+<!-- INT_ZERO->INT_PLUS -->
+<!-- INT_PLUS->INT_BOT -->
+<g id="edge16" class="edge">
+<title>INT_PLUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M344.94,-184.63C332.49,-168.71 311.63,-142.04 296.23,-122.35"/>
+<polygon fill="black" stroke="black" points="299.01,-120.23 290.1,-114.51 293.5,-124.54 299.01,-120.23"/>
+</g>
+<!-- INT_PLUS->INT_MAXDOTS -->
+<!-- INT_MAXDOTS->INT_BOT -->
+<g id="edge17" class="edge">
+<title>INT_MAXDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M424.11,-186.46C395.53,-169.18 341.93,-136.76 307.82,-116.13"/>
+<polygon fill="black" stroke="black" points="309.99,-113.35 299.62,-111.17 306.37,-119.34 309.99,-113.35"/>
+</g>
+<!-- INT_MAXDOTS->INT_MAX -->
+<!-- INT_MAX->INT_BOT -->
+<g id="edge18" class="edge">
+<title>INT_MAX->INT_BOT</title>
+<path fill="none" stroke="black" d="M515.2,-190.66C472.47,-173.93 369.55,-133.64 313.87,-111.84"/>
+<polygon fill="black" stroke="black" points="315.4,-108.68 304.81,-108.29 312.84,-115.2 315.4,-108.68"/>
+</g>
+<!-- TUPLE1 -->
+<g id="node16" class="node">
+<title>TUPLE1</title>
+<polygon fill="none" stroke="none" points="652.6,-225.75 598.6,-225.75 598.6,-172.75 652.6,-172.75 652.6,-225.75"/>
+<polygon fill="pink" stroke="none" points="609.1,-199.25 609.1,-221.75 642.1,-221.75 642.1,-199.25 609.1,-199.25"/>
+<polygon fill="none" stroke="black" points="609.1,-199.25 609.1,-221.75 642.1,-221.75 642.1,-199.25 609.1,-199.25"/>
+<text text-anchor="start" x="612.1" y="-205.45" font-family="Times New Roman,serif" font-size="14.00">tuple</text>
+<polygon fill="black" stroke="none" points="609.1,-176.75 609.1,-199.25 642.1,-199.25 642.1,-176.75 609.1,-176.75"/>
+<polygon fill="none" stroke="black" points="609.1,-176.75 609.1,-199.25 642.1,-199.25 642.1,-176.75 609.1,-176.75"/>
+<text text-anchor="start" x="613.97" y="-182.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLE1 -->
+<g id="edge27" class="edge">
+<title>TUPLE_TOP->TUPLE1</title>
+<path fill="none" stroke="black" d="M665.45,-284.12C659.18,-270.91 650.28,-252.2 642.49,-235.8"/>
+<polygon fill="black" stroke="black" points="645.67,-234.33 638.22,-226.8 639.35,-237.34 645.67,-234.33"/>
+</g>
+<!-- TUPLE2 -->
+<g id="node17" class="node">
+<title>TUPLE2</title>
+<polygon fill="none" stroke="none" points="749.6,-237 695.6,-237 695.6,-161.5 749.6,-161.5 749.6,-237"/>
+<polygon fill="pink" stroke="none" points="706.1,-210.5 706.1,-233 739.1,-233 739.1,-210.5 706.1,-210.5"/>
+<polygon fill="none" stroke="black" points="706.1,-210.5 706.1,-233 739.1,-233 739.1,-210.5 706.1,-210.5"/>
+<text text-anchor="start" x="709.1" y="-216.7" font-family="Times New Roman,serif" font-size="14.00">tuple</text>
+<polygon fill="black" stroke="none" points="706.1,-188 706.1,-210.5 739.1,-210.5 739.1,-188 706.1,-188"/>
+<polygon fill="none" stroke="black" points="706.1,-188 706.1,-210.5 739.1,-210.5 739.1,-188 706.1,-188"/>
+<text text-anchor="start" x="710.97" y="-194.2" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="706.1,-165.5 706.1,-188 739.1,-188 739.1,-165.5 706.1,-165.5"/>
+<polygon fill="none" stroke="black" points="706.1,-165.5 706.1,-188 739.1,-188 739.1,-165.5 706.1,-165.5"/>
+<text text-anchor="start" x="710.97" y="-171.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLE2 -->
+<g id="edge28" class="edge">
+<title>TUPLE_TOP->TUPLE2</title>
+<path fill="none" stroke="black" d="M681.91,-284.12C686.91,-273.8 693.55,-260.12 700.01,-246.81"/>
+<polygon fill="black" stroke="black" points="703,-248.65 704.22,-238.13 696.7,-245.6 703,-248.65"/>
+</g>
+<!-- TUPLEN -->
+<g id="node18" class="node">
+<title>TUPLEN</title>
+<polygon fill="none" stroke="none" points="846.6,-248.25 792.6,-248.25 792.6,-150.25 846.6,-150.25 846.6,-248.25"/>
+<polygon fill="pink" stroke="none" points="803.1,-221.75 803.1,-244.25 836.1,-244.25 836.1,-221.75 803.1,-221.75"/>
+<polygon fill="none" stroke="black" points="803.1,-221.75 803.1,-244.25 836.1,-244.25 836.1,-221.75 803.1,-221.75"/>
+<text text-anchor="start" x="806.1" y="-227.95" font-family="Times New Roman,serif" font-size="14.00">tuple</text>
+<polygon fill="black" stroke="none" points="803.1,-199.25 803.1,-221.75 836.1,-221.75 836.1,-199.25 803.1,-199.25"/>
+<polygon fill="none" stroke="black" points="803.1,-199.25 803.1,-221.75 836.1,-221.75 836.1,-199.25 803.1,-199.25"/>
+<text text-anchor="start" x="807.97" y="-205.45" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="803.1,-176.75 803.1,-199.25 836.1,-199.25 836.1,-176.75 803.1,-176.75"/>
+<polygon fill="none" stroke="black" points="803.1,-176.75 803.1,-199.25 836.1,-199.25 836.1,-176.75 803.1,-176.75"/>
+<text text-anchor="start" x="813.97" y="-182.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+<polygon fill="black" stroke="none" points="803.1,-154.25 803.1,-176.75 836.1,-176.75 836.1,-154.25 803.1,-154.25"/>
+<polygon fill="none" stroke="black" points="803.1,-154.25 803.1,-176.75 836.1,-176.75 836.1,-154.25 803.1,-154.25"/>
+<text text-anchor="start" x="807.97" y="-160.45" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLEN -->
+<g id="edge29" class="edge">
+<title>TUPLE_TOP->TUPLEN</title>
+<path fill="none" stroke="black" d="M695.14,-286.35C718.34,-270.29 755.65,-244.48 783.38,-225.3"/>
+<polygon fill="black" stroke="black" points="785.27,-228.25 791.51,-219.68 781.29,-222.49 785.27,-228.25"/>
+</g>
+<!-- TUPLE_BOT -->
+<g id="node15" class="node">
+<title>TUPLE_BOT</title>
+<ellipse fill="pink" stroke="black" cx="673.6" cy="-96.25" rx="42.65" ry="18"/>
+<text text-anchor="start" x="650.35" y="-92.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="666.1" y="-92.2" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TUPLE_BOT->BOT -->
+<g id="edge33" class="edge">
+<title>TUPLE_BOT->BOT</title>
+<path fill="none" stroke="black" d="M635.17,-88.17C557.01,-73.77 380.82,-41.32 308.5,-28"/>
+<polygon fill="black" stroke="black" points="309.38,-24.6 298.91,-26.23 308.11,-31.49 309.38,-24.6"/>
+</g>
+<!-- TUPLE1->TUPLE_BOT -->
+<g id="edge30" class="edge">
+<title>TUPLE1->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M637.71,-172.76C644.73,-158 653.56,-139.41 660.7,-124.38"/>
+<polygon fill="black" stroke="black" points="663.78,-126.06 664.91,-115.53 657.45,-123.06 663.78,-126.06"/>
+</g>
+<!-- TUPLE2->TUPLE_BOT -->
+<g id="edge31" class="edge">
+<title>TUPLE2->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M704.77,-161.5C698.84,-149.27 692.34,-135.89 686.82,-124.51"/>
+<polygon fill="black" stroke="black" points="690.05,-123.15 682.54,-115.69 683.76,-126.21 690.05,-123.15"/>
+</g>
+<!-- TUPLEN->TUPLE_BOT -->
+<g id="edge32" class="edge">
+<title>TUPLEN->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M792.82,-179.72C767.85,-162.45 730.64,-136.71 704.44,-118.58"/>
+<polygon fill="black" stroke="black" points="706.45,-115.72 696.23,-112.91 702.46,-121.47 706.45,-115.72"/>
+</g>
+</g>
+</svg>
|
