diff options
| author | Cliff Click <cliffc@acm.org> | 2023-10-27 20:35:04 +0100 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-04 13:30:41 -0700 |
| commit | 0f0ca9396a68b78362ce1ee59e6dc11d6910d56c (patch) | |
| tree | 601c8da8618e55b7b08cba9dac80b78de532ec34 | |
| parent | 26c9ce808557ed4c7f6c2c84d9e8f8cd7ebced49 (diff) | |
| download | Simple-0f0ca9396a68b78362ce1ee59e6dc11d6910d56c.tar.gz Simple-0f0ca9396a68b78362ce1ee59e6dc11d6910d56c.zip | |
Chapter 5: If Statement, Phi, and Region
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: David Rubin <87927264+Rexicon226@users.noreply.github.com>
54 files changed, 3049 insertions, 345 deletions
@@ -1,106 +1 @@ -SHELL := /bin/bash -# Shared packaging target; included after chapter source variables below. -.DELETE_ON_ERROR: - -# for printing variable values -# usage: make print-VARIABLE -# > VARIABLE = value_of_variable -print-% : ; @echo $* = $($*) - -# literal space -space := $() $() - -# Decide OS-specific questions -# jar-file seperator -ifeq ($(OS),Windows_NT) - SEP = ; -else - SEP = : -endif -# Find a reasonable ctags. -CTAGS = $(shell which ctags) -# Hack for MacOS: /usr/bin/ctags is unfriendly, so look for ctags from brew -ifeq ($(UNAME),Darwin) - CTAGS = $(shell brew list ctags 2> /dev/null | grep bin/ctags) -endif - -# Fun Args to javac. Mostly limit to java8 source definitions, and fairly -# aggressive lint warnings. -JAVAC_ARGS = -g - -# Source code -SIMPLE := com/seaofnodes/simple -SRC := src/main/java -TST := src/test/java -CLZDIR:= build/classes -main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java) -test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) -main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) -include $(firstword $(wildcard ../graph/graph.mk graph/graph.mk)) -include $(firstword $(wildcard ../print/print.mk print/print.mk)) -test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) -test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) -classes = $(main_classes) $(test_classes) -# All the libraries -libs = $(wildcard lib/*jar) -jars = $(subst $(space),$(SEP),$(libs)) - - -default_targets := $(main_classes) $(test_classes) -# Optionally add ctags to the default target if a reasonable one was found. -ifneq ($(CTAGS),) -default_targets += tags -endif - -default: $(default_targets) - -.PHONY: build -build: $(main_classes) - -# Compile just the out-of-date files -$(main_classes): $(CLZDIR)/main/%class: $(SRC)/%java $(graph_javas) $(print_javas) - @echo "compiling " $@ " because " $? - @[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main - @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas) - -$(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) - @echo "compiling " $@ " because " $? - @[ -d $(CLZDIR)/test ] || mkdir -p $(CLZDIR)/test - @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test $(test_javas) - -# Base launch line for JVM tests -JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" - -tests: $(default_targets) - @echo "testing " $(test_cp) - @$(JVM) org.junit.runner.JUnitCore $(test_cp) - -fuzzer: $(default_targets) - @echo "fuzzing " $(test_cp) - @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap - - -.PHONY: clean -clean: - rm -rf build - rm -f TAGS - (find . -name "*~" -exec rm {} \; 2>/dev/null; exit 0) - -# Download libs from maven -lib: lib/junit-4.12.jar lib/hamcrest-core-1.3.jar - -# Jars -lib/junit-4.12.jar: - @[ -d lib ] || mkdir -p lib - @(cd lib; wget https://repo1.maven.org/maven2/junit/junit/4.12/junit-4.12.jar) - -lib/hamcrest-core-1.3.jar: - @[ -d lib ] || mkdir -p lib - @(cd lib; wget https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar) - -# Build emacs tags (part of a tasty emacs ide experience) -tags: $(main_javas) $(test_javas) - @rm -f TAGS - @$(CTAGS) -e --recurse=yes --extra=+q --fields=+fksaiS $(SRC) $(TST) - -include $(firstword $(wildcard ../build-support/chapter-release.mk build-support/chapter-release.mk)) +include $(firstword $(wildcard ../build-support/early-chapter.mk build-support/early-chapter.mk)) @@ -46,7 +46,7 @@ The Simple language is styled after a subset of C or Java. named `arg`. Binary and Comparison operators involving constants and `arg`. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. -* Chapter 5: `if` statement. CFG construction. +* [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. * Chapter 6: Peephole optimization around dead control flow. * Chapter 7: `while` statement; looping constructs - eager phi approach. * Chapter 8: Looping constructs continued, lazy phi creation, `break` and `continue` statements. diff --git a/appendix/dce.md b/appendix/dce.md deleted file mode 100644 index 1f9dfa7a..00000000 --- a/appendix/dce.md +++ /dev/null @@ -1,166 +0,0 @@ -# Appendix -## Dead Code Elimination(DCE) -Dead Code Elimination is the process or removing nodes that are dead(unused). - -There are two kinds of dead code eliminations present in this chapter. -- Delete unused nodes when popping the scope. -- Delete old nodes after finding a better replacement (after calling `idealize()`). - -Both of the methods mentioned above delete the nodes recursively. However, the -first case happens regardless of whether `peephole` is called or not. - -### Delete unused nodes when popping the scope - -A node is unused if it has no outputs(users). - -### Example 1: - ``` - int a = 12; // the only output it has is the scope itself - return 1; - ``` -We clearly see `a` is unused. -This gives us the following graph(without DCE): - - - -To remove `a` we introduce the following technique when popping the scope. - - ```java - var ret = (ReturnNode) parseBlock(); - _scope.pop(); - ``` -As of now the end of the program is hard-wired to return, after finishing parsing we pop the scope. -The state of the scope before popping it: - ``` - _scope = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" - 1 = {ProjNode@1528} "arg" - 2 = {ConstantNode@1529} "12" - _inputs = {ArrayList@1523} size = 3 - ``` -The output(s) of `a` - ``` - _outputs = {ArrayList@1544} size = 1 - 0 = {ScopeNode@1422} "Scope[$ctrl:null, arg:arg][a:12]" - ``` -Notice how the only output of `a`is the scope itself. When `a` is introduced, it is added to the -inputs of the scope, and the scope is added to the outputs of `a`(recall use-def chains). - -Since `a` is not being returned - it is unused and can be killed. - -`_scope.pop`: -```java -public void pop() { popN(_scopes.pop().size()); } -``` -`_scope.popN`(responsible for killing the unused nodes *recursively*): -```java -void popN(int n) { - for (int i = 0; i < n; i++) { - Node old_def = _inputs.removeLast(); // start from the back - if (old_def != null && // If it exists and - old_def.delUse(this)) { // If we removed the last use, the old def is now dead - old_def.kill(); // Kill the old def - } - } -} -``` -First, we start off by looping through the inputs of the scope(*remember*: scope is just a node like any other, the symbols of the scope are the inputs). -If the node returned by `removeLast` is not null, and if the only user of `old_def` is the current Node then we can delete it. - -`old_def.delUse(this)` - delete *this* from `old_def`'s outputs. -```java -protected boolean delUse( Node use ) { - Utils.del(_outputs, Utils.find(_outputs, use)); - return _outputs.isEmpty(); - } -``` -Returns true if `_outputs` becomes empty after deleting `use`. -`old_def.kill()` starts the killing process recursively. - -`old_def.kill()` -```java -public void kill( ) { - assert isUnused(); // Has no uses, so it is dead - popN(nIns()); // Set all inputs to null, recursively killing unused Nodes - _type=null; // Flag as dead - assert isDead(); // Really dead now - } -``` -`popN` is called again, our goal is to look for nodes that might also get deleted once `a` is freed. -The only input `a` has is the constant node with value 12. As every other node a `ConstantNode` takes in the control node first(`Start`), once we -drop the `Start` node from the inputs of `ConstantNode`: -``` -Node old_def = _inputs.removeLast(); -``` -we can also get rid of `ConstantNode`(`this`) from the outputs of `Start`: -``` -old_def.delUse(this) -``` -### Example 2: -``` -int a = 12; -int b = a + 1; -return 1; -``` -- Call `popN` on current scope. -- Realize that `b = a + 1;` has no uses - so we can kill it. -- In the kill function we can call `popN` but this time with the inputs of `b = a + 1;`(start killing them recursively) -- We start the killing process from the back and examine "1" first. This has no output other than the `AddNode`. Since `this = AddNode` calling `delUse` will mark "1" as dead. -- We now can kill "1" and call the `popN` function with one input(the control node). -- Now we examine "a" which has 2 uses at this point, the scope and `AddNode`. Since `this = AddNode` we will remove `AddNode` from its outputs, it will still have the scope as a user - so we can't delete it just yet. -- We move onto`a = 12`, since "a" has only one user left(the scope) and `this = scope` it can get killed easily. -- Same as before, we go through the inputs of "a" and will delete them from the outputs of the control node. - - - -## Delete old nodes after finding a better replacement - -Consider the following code: -``` -return (2+1)+3; -``` -Without DCE after the `idealize` call we would end up with: - - -After identifying a more optimal replacement value (6) for the expression (2 + 1) + 3, -we created a constant node to store this value. -However, we did not remove the original expression, -resulting in dangling nodes in our structure. - -To fix this, we introduce an extra `deadCodeElim` call that is responsible for deleting unused nodes. - - -```java -public final Node peephole( ) { - ... - if (!(this instanceof ConstantNode) && type.isConstant()) - return new deadCodeElim(ConstantNode(type).peephole()); - - ... - - Node n = idealize(); - if( n != null ) // Something changed - // Recursively optimize - return deadCodeElim(n.peephole()); - - ... -} -``` - -```java -// m is the new Node, self is the old. -// Return 'm', which may have zero uses but is alive nonetheless. -// If self has zero uses (and is not 'm'), {@link #kill} self. -private Node deadCodeElim(Node m) { - // If self is going dead and not being returned here (Nodes returned - // from peephole commonly have no uses (yet)), then kill self. - if( m != this && isUnused() ) { - // Killing self - and since self recursively kills self's inputs we - // might end up killing 'm', which we are returning as a live Node. - // So we add a bogus extra null output edge to stop kill(). - m.addUse(null); // Add bogus null use to keep m alive - kill(); // Kill self because replacing with 'm' - m.delUse(null); // Remove bogus null. - } - return m; -} -```
\ No newline at end of file diff --git a/docs/chapter05/05-grammar.md b/docs/chapter05/05-grammar.md new file mode 100644 index 00000000..8eba1581 --- /dev/null +++ b/docs/chapter05/05-grammar.md @@ -0,0 +1,79 @@ +# Grammar for Chapter 1 + +```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/chapter05/05-graph1.gv b/docs/chapter05/05-graph1.gv new file mode 100644 index 00000000..b5cf8370 --- /dev/null +++ b/docs/chapter05/05-graph1.gv @@ -0,0 +1,88 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + +} + +return a; + +*/ + 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>> + ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + 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="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_a">a</TD></TR> + </TABLE>>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope12_0 { + Scope12_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope12_0_$ctrl">$ctrl</TD><TD PORT="Scope12_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope12_1 { + Scope12_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope12_1_a">a</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0; color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_$ctrl" -> If9:p0; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Add14; + edge [style=dashed color=cornflowerblue]; + Scope12_0:"Scope12_0_$ctrl" -> If9:p1; + Scope12_0:"Scope12_0_arg" -> Start2:p1; + Scope12_1:"Scope12_1_a" -> Sub16; +} diff --git a/docs/chapter05/05-graph1.json b/docs/chapter05/05-graph1.json new file mode 100644 index 00000000..a2b4a7bd --- /dev/null +++ b/docs/chapter05/05-graph1.json @@ -0,0 +1,25 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 10, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 14, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 12, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 10, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 16, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 6, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 11, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph1.svg b/docs/chapter05/05-graph1.svg new file mode 100644 index 00000000..0a75532a --- /dev/null +++ b/docs/chapter05/05-graph1.svg @@ -0,0 +1,120 @@ +<svg aria-label="Compiler graph" width="1006" height="548" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1006 548" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e1i0" d="M84,367 C84,391 848.5,364 848.5,388" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[0] → #11 · ASSOC · 0: $ctrl</title></path><path class="edge ASSOC" id="e1i1" d="M224,115 C224,139 906.5,364 906.5,388" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #10 · ASSOC · 0: arg</title></path><path class="edge ASSOC" id="e1i2" d="M376,219 C376,243 958,364 958,388" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #14 · ASSOC · 1: a</title></path><path class="edge ASSOC" id="e4i0" d="M204,367 C204,391 848.5,444 848.5,468" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[0] → #12 · ASSOC · 0: $ctrl</title></path><path class="edge ASSOC" id="e4i1" d="M224,115 C224,139 906.5,444 906.5,468" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[1] → #10 · ASSOC · 0: arg</title></path><path class="edge ASSOC" id="e4i2" d="M528,219 C528,243 958,444 958,468" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#4[2] → #16 · ASSOC · 1: a</title></path><path class="edge DATA" id="e8i1" d="M224,118 L224,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #10 · DATA</title></path><path class="edge DATA" id="e8i2" d="M382,118 L382,123 Q382,128 377,128 L262,128 Q254,128 254,136 L254,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge CTRL" id="e9i0" d="M104,118 L104,270" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#9[0] → #6 · CTRL</title></path><path class="edge DATA" id="e9i1" d="M224,222 L224,227 Q224,232 219,232 L192,232 Q184,232 184,240 L184,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #8 · DATA</title></path><path class="edge DATA" id="e14i1" d="M224,118 L224,130 Q224,138 232,138 L368,138 Q376,138 376,146 L376,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[1] → #10 · DATA</title></path><path class="edge DATA" id="e14i2" d="M534,118 L534,123 Q534,128 529,128 L414,128 Q406,128 406,136 L406,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[2] → #13 · DATA</title></path><path class="edge DATA" id="e16i1" d="M224,118 L224,130 Q224,138 232,138 L520,138 Q528,138 528,146 L528,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #10 · DATA</title></path><path class="edge DATA" id="e16i2" d="M686,118 L686,123 Q686,128 681,128 L566,128 Q558,128 558,136 L558,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[2] → #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(818,388)" style="opacity: 1;"><path class="box" d="M4,0H160Q164,0 164,4V52Q164,56 160,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="82" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="82"/><title>#1 Scope +Type not computed + +[0] → #11 ASSOC 0: $ctrl +[1] → #10 ASSOC 0: arg +[2] → #14 ASSOC 1: a</title><line class="row" x1="0" x2="164" y1="30" y2="30"/><line class="row" x1="61" x2="61" y1="0" y2="30"/><line class="row" x1="116" x2="116" y1="0" y2="30"/><text class="bind" x="30.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="88.5" y="20" text-anchor="middle">0: arg</text><text class="bind" x="140" y="20" text-anchor="middle">1: a</text><circle class="port" cx="30.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="88.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="140" cy="0" r="3" fill="#536477"/><text class="slot" x="30.5" y="-7" text-anchor="middle">0</text><text class="slot" x="88.5" y="-7" text-anchor="middle">1</text><text class="slot" x="140" y="-7" text-anchor="middle">2</text></g><g class="node" id="n2" data-id="2" transform="translate(44,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="n4" data-id="4" transform="translate(818,468)" style="opacity: 1;"><path class="box" d="M4,0H160Q164,0 164,4V52Q164,56 160,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="82" y="48"><tspan>Scope</tspan><tspan class="node-id"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="82"/><title>#4 Scope +Type not computed + +[0] → #12 ASSOC 0: $ctrl +[1] → #10 ASSOC 0: arg +[2] → #16 ASSOC 1: a</title><line class="row" x1="0" x2="164" y1="30" y2="30"/><line class="row" x1="61" x2="61" y1="0" y2="30"/><line class="row" x1="116" x2="116" y1="0" y2="30"/><text class="bind" x="30.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="88.5" y="20" text-anchor="middle">0: arg</text><text class="bind" x="140" y="20" text-anchor="middle">1: a</text><circle class="port" cx="30.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="88.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="140" cy="0" r="3" fill="#536477"/><text class="slot" x="30.5" y="-7" text-anchor="middle">0</text><text class="slot" x="88.5" y="-7" text-anchor="middle">1</text><text class="slot" x="140" y="-7" text-anchor="middle">2</text></g><g class="node" id="n6" data-id="6" transform="translate(44,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"> #6/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n7" data-id="7" transform="translate(322,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(164,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 == +Type not computed + +[0] → — DATA +[1] → #10 DATA +[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(24,276)" 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"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#9 If +Type not computed + +[0] → #6 CTRL +[1] → #8 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="n10" data-id="10" transform="translate(164,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"> #10/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n11" data-id="11" transform="translate(24,320)" 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"> #11/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n12" data-id="12" transform="translate(144,320)" 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"> #12/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n13" data-id="13" transform="translate(474,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="n14" data-id="14" transform="translate(316,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>+</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 + +Type not computed + +[0] → — DATA +[1] → #10 DATA +[2] → #13 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="n15" data-id="15" transform="translate(626,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"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 #3 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" transform="translate(468,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>-</tspan><tspan class="node-id"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 - +Type not computed + +[0] → — DATA +[1] → #10 DATA +[2] → #15 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g></g><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/chapter05/05-graph2.gv b/docs/chapter05/05-graph2.gv new file mode 100644 index 00000000..a560bc49 --- /dev/null +++ b/docs/chapter05/05-graph2.gv @@ -0,0 +1,78 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + +} + +return a; +*/ + 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>> + ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + 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="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + Region17 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a18 [ style=filled fillcolor=lightyellow label="φ_a" ]; + { rank=same; Region17;Phi_a18;} + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_a">a</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + Region17 -> If9:p0[taillabel=1 color=red]; + Region17 -> If9:p1[taillabel=2 color=red]; + Phi_a18 -> Region17 [style=dotted taillabel=0]; + Phi_a18 -> Add14[taillabel=1]; + Phi_a18 -> Sub16[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_$ctrl" -> Region17; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Phi_a18; +} diff --git a/docs/chapter05/05-graph2.json b/docs/chapter05/05-graph2.json new file mode 100644 index 00000000..5980da2b --- /dev/null +++ b/docs/chapter05/05-graph2.json @@ -0,0 +1,27 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 5, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 18, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 5, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 6, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, + {"id": 18, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [6, 8, 9, 10, 14, 16, 17, 18]} + ] +} diff --git a/docs/chapter05/05-graph2.svg b/docs/chapter05/05-graph2.svg new file mode 100644 index 00000000..f073e342 --- /dev/null +++ b/docs/chapter05/05-graph2.svg @@ -0,0 +1,125 @@ +<svg aria-label="Compiler graph" width="996" height="631" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 996 631" 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(144,171)"><rect class="region-box" rx="8" width="574" height="374" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e1i0" d="M306,530 C306,554 838.5,527 838.5,551" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[0] → #17 · ASSOC · 0: $ctrl</title></path><path class="edge ASSOC" id="e1i1" d="M356,115 C356,139 896.5,527 896.5,551" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #5 · ASSOC · 0: arg</title></path><path class="edge ASSOC" id="e1i2" d="M458,530 C458,554 948,527 948,551" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #18 · ASSOC · 1: a</title></path><path class="edge DATA" id="e8i1" d="M356,118 L356,123 Q356,128 351,128 L315,128 Q307,128 307,136 L307,225" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #5 · DATA</title></path><path class="edge DATA" id="e8i2" d="M84,118 L84,123 Q84,128 89,128 L218,128 Q226,128 226,136 L226,207 Q226,215 234,215 L332,215 Q337,215 337,220 L337,225" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge CTRL" id="e9i0" d="M236,118 L236,329" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#9[0] → #4 · CTRL</title></path><path class="edge DATA" id="e9i1" d="M307,281 L307,286.5 Q307,291 311.5,291 L311.5,291 Q316,291 316,295.5 L316,329" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #8 · DATA</title></path><path class="edge DATA" id="e14i1" d="M356,118 L356,123 Q356,128 361,128 L486,128 Q494,128 494,136 L494,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[1] → #5 · DATA</title></path><path class="edge DATA" id="e14i2" d="M524,118 L524,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[2] → #13 · DATA</title></path><path class="edge DATA" id="e16i1" d="M356,118 L356,123 Q356,128 361,128 L505,128 Q513,128 513,136 L513,283 Q513,291 521,291 L638,291 Q646,291 646,299 L646,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #5 · DATA</title></path><path class="edge DATA" id="e16i2" d="M676,118 L676,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[2] → #15 · DATA</title></path><path class="edge CTRL" id="e17i1" d="M216,429 L216,434 Q216,439 221,439 L298,439 Q306,439 306,447 L306,477" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#17[1] → #6 · CTRL</title></path><path class="edge CTRL" id="e17i2" d="M336,429 L336,477" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#17[2] → #10 · CTRL</title></path><path class="edge DATA" id="e18i1" d="M494,399.66666666666663 L494,431 Q494,439 486,439 L446,439 Q438,439 438,447 L438,477" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #14 · DATA</title></path><path class="edge DATA" id="e18i2" d="M646,399.66666666666663 L646,441 Q646,449 638,449 L486,449 Q478,449 478,457 L478,477" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #16 · 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(808,551)" style="opacity: 1;"><path class="box" d="M4,0H160Q164,0 164,4V52Q164,56 160,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="82" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="82"/><title>#1 Scope +Type not computed + +[0] → #17 ASSOC 0: $ctrl +[1] → #5 ASSOC 0: arg +[2] → #18 ASSOC 1: a</title><line class="row" x1="0" x2="164" y1="30" y2="30"/><line class="row" x1="61" x2="61" y1="0" y2="30"/><line class="row" x1="116" x2="116" y1="0" y2="30"/><text class="bind" x="30.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="88.5" y="20" text-anchor="middle">0: arg</text><text class="bind" x="140" y="20" text-anchor="middle">1: a</text><circle class="port" cx="30.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="88.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="140" cy="0" r="3" fill="#536477"/><text class="slot" x="30.5" y="-7" text-anchor="middle">0</text><text class="slot" x="88.5" y="-7" text-anchor="middle">1</text><text class="slot" x="140" y="-7" text-anchor="middle">2</text></g><g class="node" id="n2" data-id="2" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n4" data-id="4" transform="translate(176,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #4/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n5" data-id="5" transform="translate(296,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #5/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n6" data-id="6" transform="translate(156,379)" 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"> #6/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n7" data-id="7" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#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(247,231)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 == +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(156,335)" 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"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#9 If +Type not computed + +[0] → #4 CTRL +[1] → #8 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="n10" data-id="10" transform="translate(276,379)" 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"> #10/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n13" data-id="13" transform="translate(464,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="n14" data-id="14" transform="translate(434,349.66666666666663)" 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"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 + +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #13 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="n15" data-id="15" transform="translate(616,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"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 #3 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" transform="translate(586,349.66666666666663)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>-</tspan><tspan class="node-id"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 - +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #15 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n17" data-id="17" transform="translate(246,483)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 Region +Type not computed + +[0] → — DATA +[1] → #6 CTRL +[2] → #10 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="n18" data-id="18" transform="translate(398,483)" 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"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 φ_a +Type not computed + +[0] → #17 ASSOC +[1] → #14 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #17</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><g class="region-heads" style="opacity: 1;"><g class="region-head" transform="translate(144,171)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #9</tspan></text><title>If · 8 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #9"><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/chapter05/05-graph3.gv b/docs/chapter05/05-graph3.gv new file mode 100644 index 00000000..688c5ca9 --- /dev/null +++ b/docs/chapter05/05-graph3.gv @@ -0,0 +1,66 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + +} + +return a; +*/ + 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_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + 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="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + Region17 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a18 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region17;Phi_a18;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + Region17 -> If9:p0[taillabel=1 color=red]; + Region17 -> If9:p1[taillabel=2 color=red]; + Phi_a18 -> Region17 [style=dotted taillabel=0]; + Phi_a18 -> Add14[taillabel=1]; + Phi_a18 -> Sub16[taillabel=2]; + Return19 -> Region17[taillabel=0 color=red]; + Return19 -> Phi_a18[taillabel=1]; +} diff --git a/docs/chapter05/05-graph3.json b/docs/chapter05/05-graph3.json new file mode 100644 index 00000000..16d74821 --- /dev/null +++ b/docs/chapter05/05-graph3.json @@ -0,0 +1,28 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph3.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 19, "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": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "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": 18, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [5, 6, 8, 9, 14, 16, 17, 18]} + ] +} diff --git a/docs/chapter05/05-graph3.svg b/docs/chapter05/05-graph3.svg new file mode 100644 index 00000000..5a8b5706 --- /dev/null +++ b/docs/chapter05/05-graph3.svg @@ -0,0 +1,127 @@ +<svg aria-label="Compiler graph" width="760" height="752" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 760 752" 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(144,171)"><rect class="region-box" rx="8" width="574" height="374" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M326,651 C326,675 380,678 380,702" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #19 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M356,118 L356,123 Q356,128 351,128 L315,128 Q307,128 307,136 L307,225" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #4 · DATA</title></path><path class="edge DATA" id="e8i2" d="M84,118 L84,123 Q84,128 89,128 L218,128 Q226,128 226,136 L226,207 Q226,215 234,215 L332,215 Q337,215 337,220 L337,225" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge CTRL" id="e9i0" d="M236,118 L236,329" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#9[0] → #1 · CTRL</title></path><path class="edge DATA" id="e9i1" d="M307,281 L307,286.5 Q307,291 311.5,291 L311.5,291 Q316,291 316,295.5 L316,329" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #8 · DATA</title></path><path class="edge DATA" id="e14i1" d="M356,118 L356,123 Q356,128 361,128 L486,128 Q494,128 494,136 L494,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[1] → #4 · DATA</title></path><path class="edge DATA" id="e14i2" d="M524,118 L524,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[2] → #13 · DATA</title></path><path class="edge DATA" id="e16i1" d="M356,118 L356,123 Q356,128 361,128 L505,128 Q513,128 513,136 L513,283 Q513,291 521,291 L638,291 Q646,291 646,299 L646,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[1] → #4 · DATA</title></path><path class="edge DATA" id="e16i2" d="M676,118 L676,343.66666666666663" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#16[2] → #15 · DATA</title></path><path class="edge CTRL" id="e17i1" d="M216,429 L216,434 Q216,439 221,439 L298,439 Q306,439 306,447 L306,477" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#17[1] → #5 · CTRL</title></path><path class="edge CTRL" id="e17i2" d="M336,429 L336,477" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#17[2] → #6 · CTRL</title></path><path class="edge DATA" id="e18i1" d="M494,399.66666666666663 L494,431 Q494,439 486,439 L446,439 Q438,439 438,447 L438,477" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #14 · DATA</title></path><path class="edge DATA" id="e18i2" d="M646,399.66666666666663 L646,441 Q646,449 638,449 L486,449 Q478,449 478,457 L478,477" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #16 · DATA</title></path><path class="edge CTRL" id="e19i0" d="M306,533 L306,598" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#19[0] → #17 · CTRL</title></path><path class="edge DATA" id="e19i1" d="M458,533 L458,552 Q458,560 450,560 L354,560 Q346,560 346,568 L346,598" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[1] → #18 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(176,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #1/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n2" data-id="2" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(344,702)" 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] → #19 CTRL</title><circle class="port" cx="36" cy="0" r="3" fill="#536477"/><text class="slot" x="36" y="-7" text-anchor="middle">0</text></g><g class="node" id="n4" data-id="4" transform="translate(296,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n5" data-id="5" transform="translate(156,379)" 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 #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(276,379)" 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 #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n7" data-id="7" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#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(247,231)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(156,335)" 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"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#9 If +Type not computed + +[0] → #1 CTRL +[1] → #8 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="n13" data-id="13" transform="translate(464,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="n14" data-id="14" transform="translate(434,349.66666666666663)" 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"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 + +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #13 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="n15" data-id="15" transform="translate(616,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"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 #3 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" transform="translate(586,349.66666666666663)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>-</tspan><tspan class="node-id"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 - +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #15 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n17" data-id="17" transform="translate(246,483)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 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="n18" data-id="18" transform="translate(398,483)" 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"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 φ_a +Type not computed + +[0] → #17 ASSOC +[1] → #14 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #17</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="n19" data-id="19" transform="translate(266,604)" 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"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 Return +Type not computed + +[0] → #17 CTRL +[1] → #18 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(144,171)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #9</tspan></text><title>If · 8 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #9"><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/chapter05/05-graph4.gv b/docs/chapter05/05-graph4.gv new file mode 100644 index 00000000..88120b4a --- /dev/null +++ b/docs/chapter05/05-graph4.gv @@ -0,0 +1,63 @@ +digraph chapter05 { +/* +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +*/ + 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="#2" ]; + EQNode7 [ label="==" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ 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_14 [ label="#3" ]; + EQNode15 [ label="==" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a17 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_a17;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + EQNode7 -> Start2:p1[taillabel=1]; + EQNode7 -> Con_6[taillabel=2]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + EQNode15 -> Start2:p1[taillabel=1]; + EQNode15 -> Con_14[taillabel=2]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_a17 -> Region16 [style=dotted taillabel=0]; + Phi_a17 -> EQNode15[taillabel=1]; + Phi_a17 -> EQNode7[taillabel=2]; + Return18 -> Region16[taillabel=0 color=red]; + Return18 -> Phi_a17[taillabel=1]; +} diff --git a/docs/chapter05/05-graph4.json b/docs/chapter05/05-graph4.json new file mode 100644 index 00000000..a23b54f7 --- /dev/null +++ b/docs/chapter05/05-graph4.json @@ -0,0 +1,19 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph4.svg", + "step": 1, + "roots": [18], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 6, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 15, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 18, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph4.svg b/docs/chapter05/05-graph4.svg new file mode 100644 index 00000000..45a3d3f3 --- /dev/null +++ b/docs/chapter05/05-graph4.svg @@ -0,0 +1,95 @@ +<svg aria-label="Compiler graph" width="478" height="454" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 478 454" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e7i1" d="M84,118 L84,130 Q84,138 92,138 L228,138 Q236,138 236,146 L236,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #4 · DATA</title></path><path class="edge DATA" id="e7i2" d="M394,118 L394,123 Q394,128 389,128 L274,128 Q266,128 266,136 L266,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #6 · DATA</title></path><path class="edge DATA" id="e15i1" d="M84,118 L84,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[1] → #4 · DATA</title></path><path class="edge DATA" id="e15i2" d="M242,118 L242,123 Q242,128 237,128 L122,128 Q114,128 114,136 L114,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[2] → #14 · DATA</title></path><path class="edge DATA" id="e17i1" d="M84,222 L84,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[1] → #15 · DATA</title></path><path class="edge DATA" id="e17i2" d="M236,222 L236,227 Q236,232 231,232 L132,232 Q124,232 124,240 L124,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[2] → #7 · DATA</title></path><path class="edge DATA" id="e18i1" d="M104,326 L104,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #17 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(24,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n4" data-id="4" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n6" data-id="6" 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"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #2 +Type not computed + +</title></g><g class="node" id="n7" data-id="7" transform="translate(176,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#7 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #6 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n14" data-id="14" 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>#3</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 #3 +Type not computed + +</title></g><g class="node" id="n15" data-id="15" transform="translate(24,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #14 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n17" data-id="17" transform="translate(44,276)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 φ_a +Type not computed + +[0] → — ASSOC +[1] → #15 DATA +[2] → #7 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n18" data-id="18" transform="translate(24,380)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 Return +Type not computed + +[0] → — CTRL +[1] → #17 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter05/05-graph5.gv b/docs/chapter05/05-graph5.gv new file mode 100644 index 00000000..b03e90b5 --- /dev/null +++ b/docs/chapter05/05-graph5.gv @@ -0,0 +1,60 @@ +digraph chapter05 { +/* +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +*/ + 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="#2" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ 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_14 [ label="#3" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a19 [ style=filled fillcolor=lightyellow label="φ_a" ]; + EQNode20 [ label="==" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_a19;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_a19 -> Region16 [style=dotted taillabel=0]; + Phi_a19 -> Con_14[taillabel=1]; + Phi_a19 -> Con_6[taillabel=2]; + EQNode20 -> Start2:p1[taillabel=1]; + EQNode20 -> Phi_a19[taillabel=2]; + Return21 -> Region16[taillabel=0 color=red]; + Return21 -> EQNode20[taillabel=1]; +} diff --git a/docs/chapter05/05-graph5.json b/docs/chapter05/05-graph5.json new file mode 100644 index 00000000..3bce2865 --- /dev/null +++ b/docs/chapter05/05-graph5.json @@ -0,0 +1,18 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph5.svg", + "step": 1, + "roots": [21], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 6, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 19, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 19, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph5.svg b/docs/chapter05/05-graph5.svg new file mode 100644 index 00000000..df1144a9 --- /dev/null +++ b/docs/chapter05/05-graph5.svg @@ -0,0 +1,90 @@ +<svg aria-label="Compiler graph" width="369" height="448" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 369 448" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e19i1" d="M133,74 L133,79 Q133,84 138,84 L237,84 Q245,84 245,92 L245,134.66666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[1] → #14 · DATA</title></path><path class="edge DATA" id="e19i2" d="M285,74 L285,134.66666666666666" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[2] → #6 · DATA</title></path><path class="edge DATA" id="e20i1" d="M104,216 L104,264" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[1] → #4 · DATA</title></path><path class="edge DATA" id="e20i2" d="M265,190.66666666666666 L265,218 Q265,226 257,226 L142,226 Q134,226 134,234 L134,264" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[2] → #19 · DATA</title></path><path class="edge DATA" id="e21i1" d="M104,320 L104,368" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#21[1] → #20 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(44,122)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n4" data-id="4" transform="translate(44,166)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #4/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n6" data-id="6" transform="translate(225,24)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #2 +Type not computed + +</title></g><g class="node" id="n14" data-id="14" transform="translate(73,24)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 #3 +Type not computed + +</title></g><g class="node" id="n19" data-id="19" transform="translate(205,140.66666666666666)" 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"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 φ_a +Type not computed + +[0] → — ASSOC +[1] → #14 DATA +[2] → #6 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n20" data-id="20" transform="translate(44,270)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #19 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n21" data-id="21" transform="translate(24,374)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #21</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#21 Return +Type not computed + +[0] → — CTRL +[1] → #20 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter05/05-graph6.gv b/docs/chapter05/05-graph6.gv new file mode 100644 index 00000000..1ad7b94a --- /dev/null +++ b/docs/chapter05/05-graph6.gv @@ -0,0 +1,58 @@ +digraph chapter05 { +/* +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return 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="#3" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_15 [ label="#4" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_c17 [ style=filled fillcolor=lightyellow label="φ_c" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_c17;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_c17 -> Region16 [style=dotted taillabel=0]; + Phi_c17 -> Con_15[taillabel=1]; + Phi_c17 -> Con_6[taillabel=2]; + Return19 -> Region16[taillabel=0 color=red]; + Return19 -> Phi_c17[taillabel=1]; +} diff --git a/docs/chapter05/05-graph6.json b/docs/chapter05/05-graph6.json new file mode 100644 index 00000000..536b320c --- /dev/null +++ b/docs/chapter05/05-graph6.json @@ -0,0 +1,15 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph6.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 6, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 15, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "label": "φ_c", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph6.svg b/docs/chapter05/05-graph6.svg new file mode 100644 index 00000000..f58a541f --- /dev/null +++ b/docs/chapter05/05-graph6.svg @@ -0,0 +1,78 @@ +<svg aria-label="Compiler graph" width="320" height="306" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 306" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e17i1" d="M84,74 L84,122" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[1] → #15 · DATA</title></path><path class="edge DATA" id="e17i2" d="M236,74 L236,79 Q236,84 231,84 L132,84 Q124,84 124,92 L124,122" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#17[2] → #6 · DATA</title></path><path class="edge DATA" id="e19i1" d="M104,178 L104,226" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#19[1] → #17 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n6" data-id="6" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 #3 +Type not computed + +</title></g><g class="node" id="n15" data-id="15" transform="translate(24,24)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#4</tspan><tspan class="node-id"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#15 #4 +Type not computed + +</title></g><g class="node" id="n17" data-id="17" transform="translate(44,128)" 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>φ_c</tspan><tspan class="node-id"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 φ_c +Type not computed + +[0] → — ASSOC +[1] → #15 DATA +[2] → #6 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n19" data-id="19" transform="translate(24,232)" 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"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 Return +Type not computed + +[0] → — CTRL +[1] → #17 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter05/05-graph7.gv b/docs/chapter05/05-graph7.gv new file mode 100644 index 00000000..3abd6455 --- /dev/null +++ b/docs/chapter05/05-graph7.gv @@ -0,0 +1,72 @@ +digraph chapter05 { +/* +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +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" ]; + Phi_b37 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Con_10 [ label="#1" ]; + Add42 [ label="+" ]; + EQNode11 [ label="==" ]; + If12 [ shape=plaintext label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0" CELLPADDING="4"> + <TR><TD BGCOLOR="yellow">If</TD></TR> + <TR><TD> + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD PORT="p0" BGCOLOR="yellow">True</TD><TD PORT="p1" BGCOLOR="yellow">False</TD></TR> + </TABLE> + </TD></TR> + </TABLE>> + ]; + Con_46 [ label="#4" ]; + Con_48 [ label="#5" ]; + Phi_ab49 [ style=filled fillcolor=lightyellow label="φ_ab" ]; + Add50 [ label="+" ]; + Con_19 [ label="#2" ]; + Return51 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Mul20 [ label="*" ]; + Region31 [ shape=box style=filled fillcolor=yellow label="Region" ]; + { rank=same; Region31;Phi_b37;Phi_ab49;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return51[taillabel=0 color=red]; + Phi_b37 -> Region31 [style=dotted taillabel=0]; + Phi_b37 -> Mul20[taillabel=1]; + Phi_b37 -> Start2:p1[taillabel=2]; + Add42 -> Phi_b37[taillabel=1]; + Add42 -> Start2:p1[taillabel=2]; + EQNode11 -> Start2:p1[taillabel=1]; + EQNode11 -> Con_10[taillabel=2]; + If12 -> Start2:p0[taillabel=0 color=red]; + If12 -> EQNode11[taillabel=1]; + Phi_ab49 -> Region31 [style=dotted taillabel=0]; + Phi_ab49 -> Con_46[taillabel=1]; + Phi_ab49 -> Con_48[taillabel=2]; + Add50 -> Add42[taillabel=1]; + Add50 -> Phi_ab49[taillabel=2]; + Return51 -> Region31[taillabel=0 color=red]; + Return51 -> Add50[taillabel=1]; + Mul20 -> Start2:p1[taillabel=1]; + Mul20 -> Con_19[taillabel=2]; + Region31 -> If12:p0[taillabel=1 color=red]; + Region31 -> If12:p1[taillabel=2 color=red]; +} diff --git a/docs/chapter05/05-graph7.json b/docs/chapter05/05-graph7.json new file mode 100644 index 00000000..2f4b4336 --- /dev/null +++ b/docs/chapter05/05-graph7.json @@ -0,0 +1,22 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph7.svg", + "step": 1, + "roots": [51], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 19, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 20, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 19, "role": "DATA", "label": null}], "proj": null}, + {"id": 37, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 42, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 37, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 46, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 48, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 49, "label": "φ_ab", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 46, "role": "DATA", "label": null}, {"idx": 2, "def": 48, "role": "DATA", "label": null}], "proj": null}, + {"id": 50, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 42, "role": "DATA", "label": null}, {"idx": 2, "def": 49, "role": "DATA", "label": null}], "proj": null}, + {"id": 51, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 50, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph7.svg b/docs/chapter05/05-graph7.svg new file mode 100644 index 00000000..b121e1b9 --- /dev/null +++ b/docs/chapter05/05-graph7.svg @@ -0,0 +1,108 @@ +<svg aria-label="Compiler graph" width="577" height="662" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 577 662" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e20i1" d="M236,118 L236,123 Q236,128 231,128 L154,128 Q146,128 146,136 L146,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[1] → #4 · DATA</title></path><path class="edge DATA" id="e20i2" d="M84,118 L84,130 Q84,138 92,138 L168,138 Q176,138 176,146 L176,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[2] → #19 · DATA</title></path><path class="edge DATA" id="e37i1" d="M146,222 L146,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#37[1] → #20 · DATA</title></path><path class="edge DATA" id="e37i2" d="M236,118 L236,224 Q236,232 228,232 L194,232 Q186,232 186,240 L186,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#37[2] → #4 · DATA</title></path><path class="edge DATA" id="e42i1" d="M166,326 L166,331 Q166,336 171,336 L198,336 Q206,336 206,344 L206,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#42[1] → #37 · DATA</title></path><path class="edge DATA" id="e42i2" d="M236,118 L236,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#42[2] → #4 · DATA</title></path><path class="edge DATA" id="e49i1" d="M341,326 L341,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#49[1] → #46 · DATA</title></path><path class="edge DATA" id="e49i2" d="M493,326 L493,331 Q493,336 488,336 L389,336 Q381,336 381,344 L381,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#49[2] → #48 · DATA</title></path><path class="edge DATA" id="e50i1" d="M206,430 L206,478" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#50[1] → #42 · DATA</title></path><path class="edge DATA" id="e50i2" d="M361,430 L361,435 Q361,440 356,440 L244,440 Q236,440 236,448 L236,478" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#50[2] → #49 · DATA</title></path><path class="edge DATA" id="e51i1" d="M206,534 L206,582" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#51[1] → #50 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n2" data-id="2" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n4" data-id="4" transform="translate(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="n19" data-id="19" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 #2 +Type not computed + +</title></g><g class="node" id="n20" data-id="20" transform="translate(86,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>*</tspan><tspan class="node-id"> #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 * +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #19 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="n37" data-id="37" transform="translate(106,276)" 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"> #37</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#37 φ_b +Type not computed + +[0] → — ASSOC +[1] → #20 DATA +[2] → #4 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n42" data-id="42" transform="translate(146,380)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>+</tspan><tspan class="node-id"> #42</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#42 + +Type not computed + +[0] → — DATA +[1] → #37 DATA +[2] → #4 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n46" data-id="46" transform="translate(281,276)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#4</tspan><tspan class="node-id"> #46</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#46 #4 +Type not computed + +</title></g><g class="node" id="n48" data-id="48" transform="translate(433,276)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#5</tspan><tspan class="node-id"> #48</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#48 #5 +Type not computed + +</title></g><g class="node" id="n49" data-id="49" transform="translate(301,380)" 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"> #49</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#49 φ_ab +Type not computed + +[0] → — ASSOC +[1] → #46 DATA +[2] → #48 DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n50" data-id="50" transform="translate(146,484)" 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"> #50</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#50 + +Type not computed + +[0] → — DATA +[1] → #42 DATA +[2] → #49 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="n51" data-id="51" transform="translate(126,588)" 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"> #51</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#51 Return +Type not computed + +[0] → — CTRL +[1] → #50 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="white"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter05/05-graph8.gv b/docs/chapter05/05-graph8.gv new file mode 100644 index 00000000..8f28207c --- /dev/null +++ b/docs/chapter05/05-graph8.gv @@ -0,0 +1,129 @@ +digraph chapter05 { +/* +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; + +*/ + 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_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + 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="#2" ]; + EQNode14 [ label="==" ]; + If15 [ 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_19 [ label="#2" ]; + Con_20 [ label="#3" ]; + Region21 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a22 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Con_23 [ label="#3" ]; + EQNode24 [ label="==" ]; + If25 [ 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_29 [ label="#4" ]; + Con_30 [ label="#5" ]; + Region31 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a32 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Region33 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a34 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return35 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region21;Phi_a22;} + { rank=same; Region31;Phi_a32;} + { rank=same; Region33;Phi_a34;} + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$ctrl">$ctrl</TD><TD PORT="Scope1_0_arg">arg</TD></TR> + </TABLE>>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">1</TD><TD PORT="Scope1_1_a">a</TD></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return35[taillabel=0 color=red]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + EQNode14 -> Start2:p1[taillabel=1]; + EQNode14 -> Con_13[taillabel=2]; + If15 -> If9:p0[taillabel=0 color=red]; + If15 -> EQNode14[taillabel=1]; + Region21 -> If15:p0[taillabel=1 color=red]; + Region21 -> If15:p1[taillabel=2 color=red]; + Phi_a22 -> Region21 [style=dotted taillabel=0]; + Phi_a22 -> Con_19[taillabel=1]; + Phi_a22 -> Con_20[taillabel=2]; + EQNode24 -> Start2:p1[taillabel=1]; + EQNode24 -> Con_23[taillabel=2]; + If25 -> If9:p1[taillabel=0 color=red]; + If25 -> EQNode24[taillabel=1]; + Region31 -> If25:p0[taillabel=1 color=red]; + Region31 -> If25:p1[taillabel=2 color=red]; + Phi_a32 -> Region31 [style=dotted taillabel=0]; + Phi_a32 -> Con_29[taillabel=1]; + Phi_a32 -> Con_30[taillabel=2]; + Region33 -> Region21[taillabel=1 color=red]; + Region33 -> Region31[taillabel=2 color=red]; + Phi_a34 -> Region33 [style=dotted taillabel=0]; + Phi_a34 -> Phi_a22[taillabel=1]; + Phi_a34 -> Phi_a32[taillabel=2]; + Return35 -> Region33[taillabel=0 color=red]; + Return35 -> Phi_a34[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Phi_a34; +} diff --git a/docs/chapter05/05-graph8.json b/docs/chapter05/05-graph8.json new file mode 100644 index 00000000..887d1e8a --- /dev/null +++ b/docs/chapter05/05-graph8.json @@ -0,0 +1,45 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph8.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 6, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 34, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 35, "role": "CTRL", "label": null}], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}], "proj": {"par": 15, "idx": 0}}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 10, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}], "proj": {"par": 15, "idx": 1}}, + {"id": 17, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, + {"id": 18, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, + {"id": 19, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 20, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 21, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "CTRL", "label": null}, {"idx": 2, "def": 16, "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": 19, "role": "DATA", "label": null}, {"idx": 2, "def": 20, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 24, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 23, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 24, "role": "DATA", "label": null}], "proj": null}, + {"id": 29, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 30, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 31, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 17, "role": "CTRL", "label": null}, {"idx": 2, "def": 18, "role": "CTRL", "label": null}], "proj": null}, + {"id": 32, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 31, "role": "ASSOC", "label": null}, {"idx": 1, "def": 29, "role": "DATA", "label": null}, {"idx": 2, "def": 30, "role": "DATA", "label": null}], "proj": null}, + {"id": 33, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 21, "role": "CTRL", "label": null}, {"idx": 2, "def": 31, "role": "CTRL", "label": null}], "proj": null}, + {"id": 34, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 33, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "DATA", "label": null}, {"idx": 2, "def": 32, "role": "DATA", "label": null}], "proj": null}, + {"id": 35, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 33, "role": "CTRL", "label": null}, {"idx": 1, "def": 34, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [8, 9, 10, 11, 33, 34]}, + {"id": 15, "par": 9, "nodes": [12, 14, 15, 16, 21, 22]}, + {"id": 25, "par": 9, "nodes": [17, 18, 24, 25, 31, 32]} + ] +} diff --git a/docs/chapter05/05-graph8.svg b/docs/chapter05/05-graph8.svg new file mode 100644 index 00000000..b1b4da5c --- /dev/null +++ b/docs/chapter05/05-graph8.svg @@ -0,0 +1,188 @@ +<svg aria-label="Compiler graph" width="1594" height="1208" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 1594 1208" 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(61,193)"><rect class="region-box" rx="8" width="826" height="808" fill="#f2f7ef"/></g><g class="region" transform="translate(73,506)"><rect class="region-box" rx="8" width="410" height="374" fill="#f2f7ef"/></g><g class="region" transform="translate(515,511.7142857142857)"><rect class="region-box" rx="8" width="360" height="354" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e1i1" d="M356,115 C356,139 1494.5,0 1494.5,24" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #6 · ASSOC · 0: arg</title></path><path class="edge ASSOC" id="e1i2" d="M431,986 C431,1010 1546,0 1546,24" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[2] → #34 · ASSOC · 1: a</title></path><path class="edge CTRL" id="e3i0" d="M299,1107 C299,1131 797,1134 797,1158" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #35 · CTRL</title></path><path class="edge DATA" id="e8i1" d="M356,118 L356,123 Q356,128 351,128 L349,128 Q342,128 342,135 L342,247" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #6 · DATA</title></path><path class="edge DATA" id="e8i2" d="M514,118 L514,123 Q514,128 509,128 L430,128 Q422,128 422,136 L422,229 Q422,237 414,237 L377,237 Q372,237 372,242 L372,247" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge CTRL" id="e9i0" d="M236,118 L236,351" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#9[0] → #5 · CTRL</title></path><path class="edge DATA" id="e9i1" d="M342,303 L342,308 Q342,313 337,313 L324,313 Q316,313 316,321 L316,351" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #8 · DATA</title></path><path class="edge DATA" id="e14i1" d="M356,118 L356,123 Q356,128 351,128 L255,128 Q247,128 247,136 L247,305 Q247,313 239,313 L153,313 Q145,313 145,321 L145,560" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[1] → #6 · DATA</title></path><path class="edge DATA" id="e14i2" d="M84,118 L84,123 Q84,128 89,128 L126,128 Q134,128 134,136 L134,460.5 Q134,461 134.5,461 L134.5,461 Q135,461 135,461.5 L135,542 Q135,550 143,550 L170,550 Q175,550 175,555 L175,560" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#14[2] → #13 · DATA</title></path><path class="edge CTRL" id="e15i0" d="M216,451 L216,460.5 Q216,461 215.5,461 L215.5,461 Q215,461 215,461.5 L215,664" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#15[0] → #10 · CTRL</title></path><path class="edge DATA" id="e15i1" d="M145,616 L145,621 Q145,626 150,626 L287,626 Q295,626 295,634 L295,664" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#15[1] → #14 · DATA</title></path><path class="edge CTRL" id="e21i1" d="M195,764 L195,769 Q195,774 200,774 L251,774 Q259,774 259,782 L259,812" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#21[1] → #12 · CTRL</title></path><path class="edge CTRL" id="e21i2" d="M315,764 L315,769 Q315,774 310,774 L297,774 Q289,774 289,782 L289,812" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#21[2] → #16 · CTRL</title></path><path class="edge DATA" id="e22i1" d="M666,118 L666,130 Q666,138 658,138 L440,138 Q432,138 432,146 L432,463 Q432,471 424,471 L399,471 Q391,471 391,479 L391,812" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#22[1] → #19 · DATA</title></path><path class="edge DATA" id="e22i2" d="M818,118 L818,140 Q818,148 810,148 L451,148 Q443,148 443,156 L443,475 Q443,481 437,481 L437,481 Q431,481 431,487 L431,812" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#22[2] → #20 · DATA</title></path><path class="edge DATA" id="e24i1" d="M356,118 L356,123 Q356,128 361,128 L404,128 Q412,128 412,136 L412,453 Q412,461 420,461 L679,461 Q687,461 687,469 L687,545.7142857142858" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#24[1] → #6 · DATA</title></path><path class="edge DATA" id="e24i2" d="M970,118 L970,150 Q970,158 962,158 L725,158 Q717,158 717,166 L717,545.7142857142858" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#24[2] → #23 · DATA</title></path><path class="edge CTRL" id="e25i0" d="M336,451 L336,483 Q336,491 344,491 L599,491 Q607,491 607,499 L607,649.7142857142858" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#25[0] → #11 · CTRL</title></path><path class="edge DATA" id="e25i1" d="M687,601.7142857142858 L687,649.7142857142858" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#25[1] → #24 · DATA</title></path><path class="edge CTRL" id="e31i1" d="M587,749.7142857142858 L587,754.7142857142858 Q587,759.7142857142858 592,759.7142857142858 L643,759.7142857142858 Q651,759.7142857142858 651,767.7142857142858 L651,797.7142857142858" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#31[1] → #17 · CTRL</title></path><path class="edge CTRL" id="e31i2" d="M707,749.7142857142858 L707,754.7142857142858 Q707,759.7142857142858 702,759.7142857142858 L689,759.7142857142858 Q681,759.7142857142858 681,767.7142857142858 L681,797.7142857142858" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#31[2] → #18 · CTRL</title></path><path class="edge DATA" id="e32i1" d="M1122,118 L1122,160 Q1122,168 1114,168 L791,168 Q783,168 783,176 L783,797.7142857142858" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#32[1] → #29 · DATA</title></path><path class="edge DATA" id="e32i2" d="M1274,118 L1274,170 Q1274,178 1266,178 L831,178 Q823,178 823,186 L823,797.7142857142858" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#32[2] → #30 · DATA</title></path><path class="edge CTRL" id="e33i1" d="M259,868 L259,887 Q259,895 267,895 L271,895 Q279,895 279,903 L279,933" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#33[1] → #21 · CTRL</title></path><path class="edge CTRL" id="e33i2" d="M651,853.7142857142858 L651,887 Q651,895 643,895 L317,895 Q309,895 309,903 L309,933" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#33[2] → #31 · CTRL</title></path><path class="edge DATA" id="e34i1" d="M411,868 L411,933" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#34[1] → #22 · DATA</title></path><path class="edge DATA" id="e34i2" d="M803,853.7142857142858 L803,897 Q803,905 795,905 L459,905 Q451,905 451,913 L451,933" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#34[2] → #32 · DATA</title></path><path class="edge CTRL" id="e35i0" d="M279,989 L279,1054" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#35[0] → #33 · CTRL</title></path><path class="edge DATA" id="e35i1" d="M431,989 L431,1008 Q431,1016 423,1016 L327,1016 Q319,1016 319,1024 L319,1054" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#35[1] → #34 · 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(1406,24)" style="opacity: 1;"><path class="box" d="M4,0H160Q164,0 164,4V52Q164,56 160,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="82" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="82"/><title>#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #6 ASSOC 0: arg +[2] → #34 ASSOC 1: a</title><line class="row" x1="0" x2="164" y1="30" y2="30"/><line class="row" x1="61" x2="61" y1="0" y2="30"/><line class="row" x1="116" x2="116" y1="0" y2="30"/><text class="bind" x="30.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="88.5" y="20" text-anchor="middle">0: arg</text><text class="bind" x="140" y="20" text-anchor="middle">1: a</text><circle class="port" cx="30.5" cy="0" r="3" fill="white"/><circle class="port" cx="88.5" cy="0" r="3" fill="#536477"/><circle class="port" cx="140" cy="0" r="3" fill="#536477"/><text class="slot" x="30.5" y="-7" text-anchor="middle">0</text><text class="slot" x="88.5" y="-7" text-anchor="middle">1</text><text class="slot" x="140" y="-7" text-anchor="middle">2</text></g><g class="node" id="n2" data-id="2" transform="translate(176,24)" style="opacity: 1;"><path class="box" d="M0,0H240V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="120" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n3" data-id="3" transform="translate(761,1158)" 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] → #35 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="n5" data-id="5" transform="translate(176,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #5/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(296,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>arg</tspan><tspan class="node-id"> #6/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA</title></g><g class="node" id="n7" data-id="7" transform="translate(454,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #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(282,253)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 == +Type not computed + +[0] → — DATA +[1] → #6 DATA +[2] → #7 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(156,357)" 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"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#9 If +Type not computed + +[0] → #5 CTRL +[1] → #8 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="n10" data-id="10" transform="translate(156,401)" 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 #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n11" data-id="11" transform="translate(276,401)" 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 #9 +Type not computed + +[0] → #9 CTRL</title></g><g class="node" id="n12" data-id="12" transform="translate(135,714)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>True</tspan><tspan class="node-id"> #12/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 True +Projection 0 of #15 +Type not computed + +[0] → #15 CTRL</title></g><g class="node" id="n13" data-id="13" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#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="n14" data-id="14" transform="translate(85,566)" 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"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 == +Type not computed + +[0] → — DATA +[1] → #6 DATA +[2] → #13 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="n15" data-id="15" transform="translate(135,670)" 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"> #15</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#15 If +Type not computed + +[0] → #10 CTRL +[1] → #14 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="n16" data-id="16" transform="translate(255,714)" 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"> #16/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 False +Projection 1 of #15 +Type not computed + +[0] → #15 CTRL</title></g><g class="node" id="n17" data-id="17" transform="translate(527,699.7142857142858)" 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"> #17/0</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 True +Projection 0 of #25 +Type not computed + +[0] → #25 CTRL</title></g><g class="node" id="n18" data-id="18" transform="translate(647,699.7142857142858)" 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"> #18/1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 False +Projection 1 of #25 +Type not computed + +[0] → #25 CTRL</title></g><g class="node" id="n19" data-id="19" transform="translate(606,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#2</tspan><tspan class="node-id"> #19</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#19 #2 +Type not computed + +</title></g><g class="node" id="n20" data-id="20" transform="translate(758,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#3</tspan><tspan class="node-id"> #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 #3 +Type not computed + +</title></g><g class="node" id="n21" data-id="21" transform="translate(199,818)" 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] → #12 CTRL +[2] → #16 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(351,818)" 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] → #19 DATA +[2] → #20 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(910,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"> #23</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#23 #3 +Type not computed + +</title></g><g class="node" id="n24" data-id="24" transform="translate(627,551.7142857142858)" 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] → #6 DATA +[2] → #23 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(527,655.7142857142858)" 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"> #25</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#25 If +Type not computed + +[0] → #11 CTRL +[1] → #24 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="n29" data-id="29" transform="translate(1062,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"> #29</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#29 #4 +Type not computed + +</title></g><g class="node" id="n30" data-id="30" transform="translate(1214,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#5</tspan><tspan class="node-id"> #30</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#30 #5 +Type not computed + +</title></g><g class="node" id="n31" data-id="31" transform="translate(591,803.7142857142858)" 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"> #31</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#31 Region +Type not computed + +[0] → — DATA +[1] → #17 CTRL +[2] → #18 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="n32" data-id="32" transform="translate(743,803.7142857142858)" 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"> #32</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#32 φ_a +Type not computed + +[0] → #31 ASSOC +[1] → #29 DATA +[2] → #30 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] → #31</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="n33" data-id="33" transform="translate(219,939)" 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"> #33</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#33 Region +Type not computed + +[0] → — DATA +[1] → #21 CTRL +[2] → #31 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="n34" data-id="34" transform="translate(371,939)" 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"> #34</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#34 φ_a +Type not computed + +[0] → #33 ASSOC +[1] → #22 DATA +[2] → #32 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] → #33</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="n35" data-id="35" transform="translate(239,1060)" 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"> #35</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#35 Return +Type not computed + +[0] → #33 CTRL +[1] → #34 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(61,193)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #9</tspan></text><title>If · 18 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #9"><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(73,506)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #15</tspan></text><title>If · 6 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #15"><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(515,511.7142857142857)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #25</tspan></text><title>If · 6 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #25"><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/chapter05/05-graph9.json b/docs/chapter05/05-graph9.json new file mode 100644 index 00000000..deb1b540 --- /dev/null +++ b/docs/chapter05/05-graph9.json @@ -0,0 +1,26 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph9.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": 20, "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": 10, "role": "CTRL", "label": null}], "proj": {"par": 10, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 10, "role": "CTRL", "label": null}], "proj": {"par": 10, "idx": 1}}, + {"id": 8, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 9, "label": "==", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "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": 18, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 10, "par": 0, "nodes": [5, 6, 9, 10, 17, 18]} + ] +} diff --git a/docs/chapter05/05-graph9.svg b/docs/chapter05/05-graph9.svg new file mode 100644 index 00000000..d0f62b69 --- /dev/null +++ b/docs/chapter05/05-graph9.svg @@ -0,0 +1,117 @@ +<svg aria-label="Compiler graph" width="782" height="734" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 782 734" 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,173)"><rect class="region-box" rx="8" width="360" height="354" fill="#f2f7ef"/></g></g><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge CTRL" id="e3i0" d="M180,633 C180,657 391,660 391,684" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #20 · CTRL</title></path><path class="edge DATA" id="e9i1" d="M236,118 L236,123 Q236,128 231,128 L204,128 Q196,128 196,136 L196,207" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #4 · DATA</title></path><path class="edge DATA" id="e9i2" d="M394,118 L394,130 Q394,138 386,138 L234,138 Q226,138 226,146 L226,207" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[2] → #8 · DATA</title></path><path class="edge CTRL" id="e10i0" d="M116,118 L116,311" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#10[0] → #1 · CTRL</title></path><path class="edge DATA" id="e10i1" d="M196,263 L196,311" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[1] → #9 · DATA</title></path><path class="edge CTRL" id="e17i1" d="M96,411 L96,416 Q96,421 101,421 L152,421 Q160,421 160,429 L160,459" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#17[1] → #5 · CTRL</title></path><path class="edge CTRL" id="e17i2" d="M216,411 L216,416 Q216,421 211,421 L198,421 Q190,421 190,429 L190,459" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#17[2] → #6 · CTRL</title></path><path class="edge DATA" id="e18i1" d="M546,118 L546,140 Q546,148 538,148 L300,148 Q292,148 292,156 L292,459" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[1] → #14 · DATA</title></path><path class="edge DATA" id="e18i2" d="M698,118 L698,150 Q698,158 690,158 L340,158 Q332,158 332,166 L332,459" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#18[2] → #16 · DATA</title></path><path class="edge CTRL" id="e20i0" d="M160,515 L160,580" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#20[0] → #17 · CTRL</title></path><path class="edge DATA" id="e20i1" d="M312,515 L312,534 Q312,542 304,542 L208,542 Q200,542 200,550 L200,580" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#20[1] → #18 · 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(355,684)" 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] → #20 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,361)" 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 #10 +Type not computed + +[0] → #10 CTRL</title></g><g class="node" id="n6" data-id="6" transform="translate(156,361)" 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 #10 +Type not computed + +[0] → #10 CTRL</title></g><g class="node" id="n8" data-id="8" 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>1</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#8 1 +Type not computed + +</title></g><g class="node" id="n9" data-id="9" transform="translate(136,213)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>==</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #8 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n10" data-id="10" transform="translate(36,317)" 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"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="120"/><title>#10 If +Type not computed + +[0] → #1 CTRL +[1] → #9 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="n14" data-id="14" 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>2</tspan><tspan class="node-id"> #14</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#14 2 +Type not computed + +</title></g><g class="node" id="n16" data-id="16" 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>1</tspan><tspan class="node-id"> #16</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#16 1 +Type not computed + +</title></g><g class="node" id="n17" data-id="17" transform="translate(100,465)" 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"> #17</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#17 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="n18" data-id="18" transform="translate(252,465)" 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"> #18</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#18 φ_b +Type not computed + +[0] → #17 ASSOC +[1] → #14 DATA +[2] → #16 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #17</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="n20" data-id="20" transform="translate(120,586)" 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"> #20</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#20 Return +Type not computed + +[0] → #17 CTRL +[1] → #18 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,173)"><text class="label" x="26" y="17"><tspan>If</tspan><tspan class="node-id"> #10</tspan></text><title>If · 6 nodes</title><g class="fold-btn" role="button" tabindex="0" transform="translate(4,4)" aria-label="Fold region #10"><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/chapter05/Makefile b/docs/chapter05/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter05/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter05/README.md b/docs/chapter05/README.md new file mode 100644 index 00000000..6f690922 --- /dev/null +++ b/docs/chapter05/README.md @@ -0,0 +1,425 @@ +# Chapter 5: If Statement, Phi, and Region + +[Previous: Chapter 4](../chapter04/README.md) | +[Next: Chapter 6](../chapter06/README.md) + +# Table of Contents + +1. [Recap](#recap) +2. [New Nodes](#new-nodes) +3. [`IfNode`](#ifnode) +4. [`PhiNode`](#phinode) +5. [`RegionNode`](#regionnode) +6. [Pinned data nodes](#we-do-not-associate-a-control-edge-on-every-data-node-in-the-graph) +7. [`Stop` Nodes](#stop-nodes) +8. [Parsing an `if` Statement](#parsing-an-if-statement) +9. [Operations on ScopeNodes](#operations-on-scopenodes) +10. [Duplicating a ScopeNode](#duplicating-a-scopenode) +11. [Merging two ScopeNodes](#merging-two-scopenodes) +12. [Example 1](#example-1) +13. [Before Merging](#before-merging) +14. [After Merging](#after-merging) +15. [Finally](#finally) +16. [Example 2](#example-2) +17. [Example 3](#example-3) +18. [Pushing addition up through a Phi](#pushing-addition-up-through-a-phi) +19. [More Examples](#more-examples) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter05) 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-chapter04...linear-chapter05) it to the previous chapter. + +In this chapter we extend the language grammar with the following features: + +* We introduce the `if` statement. +* To support splitting of control flow and merging, we introduce new nodes: `Region` and `Phi`. +* Since we can now have multiple return points, we also introduce the `Stop` node as the termination. + +Here is the [complete language grammar](05-grammar.md) for this chapter. + +## New Nodes + +The following new nodes are introduced in this chapter: + +| Node Name | Type | Chapter | Description | Inputs | Value | +|-----------|---------|---------|----------------------------------------------------|------------------------------------------------|----------------------------------------------------| +| If | Control | 5 | A branching test, sub type of `MultiNode` | A control node and a data predicate node | A tuple of two values: one for true, one for false | +| Region | Control | 5 | A merge point for multiple control flows | An input for each control flow that is merging | Merged control | +| Phi | Data | 5 | A phi function picks a value based on control flow | A Region, and data nodes for each control path | Depends on control flow path taken | +| Stop | Control | 5 | Termination of the program | All return nodes of the function | None | + +and keep all nodes from prior chapters. + +#### `IfNode` + +`If` node takes in both control and data (predicate expression) and routes the +control token to one of the two control flows, represented by true and false +`Proj` nodes. + +#### `PhiNode` + +A `Phi` reads in both data and control, and outputs a data value. The control +input to the `Phi` points to a `Region` node. The data inputs to the `Phi` are +one for each of the control inputs to that `Region`. The result computed by a +`Phi` depends both on the data and the matching control input. At most one +control input to the `Region` can be active at a time, and the `Phi` passes +through the data value from the matching input.[^1] + +Its type is the meet of its data-input types. Two different integer constants +merge to `TypeInteger.BOT`: the value is unknown, but it is still an integer. +Integer arithmetic likewise retains an integer result type when it cannot fold. + +#### `RegionNode` + +In this Sea of Nodes, there is an embedded Control Flow Graph - and like a +normal CFG there are merge points where two basic blocks flow into one. The +`Region` node takes control from each predecessor control (block) as input and +produces a merged control as an output.[^2] + +Both `Return` and `If` take control in slot 0. `PhiNode`s need their +corresponding `RegionNode` to know when to merge data values, so again slot 0 +is set, and data values show up in slots 1 and onward. `RegionNode`s keep +their control inputs in sync with `PhiNode`s, so again their control inputs show up +in slots 1 and onward. + +#### We do not associate a control edge on every data node in the graph + +If we want to track the basic block a normal instruction is in, we will set the +control input (always slot 0) to some control-producing Node. Typically we do +not need to (nor want to) track this - so control is `null` for most data ops. +The correctness of such a data op is solely determined by the remaining data +dependencies. It, and the Nodes that depend on it or on which it depends, +exists in a “sea” of Nodes, with little control structure. + +The “sea” of Nodes is useful for optimization, but does not represent any +traditional intermediate representation such as a CFG. We need a way to +serialize the graph and get back the control dependences. We do this with a +simple Global Code Motion [^3] algorithm in [Chapter 13](../chapter13/README.md). + +#### `Stop` Nodes +`StopNode`s only have `ReturnNode` inputs. They mark the program termination. + + + +## Parsing an `if` Statement + +When we parse an `if` statement, the control flow splits at that point. We +must track the names being updated in each part of the `if` statement, and then +merge them at the end. The implementation follows the description in *Combining Analyses, Combining Optimizations*[^4]. + +This involves the following: + +1. We create an `IfNode` with the current control token, i.e. the node mapped to + `$ctrl`, and the `if` predicate expression as inputs. +2. We add two `ProjNodes` - one for the `True` branch (call it `ifT`), and the + other for the `False` branch (call it `ifF`) - these extract values from the + tuple result of the `IfNode`. +3. We duplicate the current `ScopeNode`. The duplicated `ScopeNode` contains + all the same symbol tables as the original, and has the same edges. +4. We set the control token to the `True` projection node `ifT`, and parse the true + branch of the `if` statement. +5. We set the duplicated `ScopeNode` as the current one. +6. The control token is set to the `False` projection node `ifF`, and if there is an + `else` statement we parse it. +7. At this point we have two `ScopeNode`s; the original one, potentially updated + by the `True` branch, and the duplicate one, potentially updated by the + `False` branch. +8. We create a `Region` node to represent a merge point. +9. We *merge* the two `ScopeNode`s. We create `Phi` nodes for any names whose + bindings differ. The `Phi` nodes take the `Region` node as the control input + and the two data nodes from each of the `ScopeNode`s. The name binding is + updated to point to the `Phi` node. +10. Finally, we set the `Region` node as the control token, and discard the duplicated `ScopeNode`. + +Implementation is in [`parseIf` method in `Parser`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/Parser.java#L149-L185). + +## Operations on ScopeNodes + +As explained above, we duplicate ScopeNodes and merge them at a later point. There are some +subtleties in how this is implemented that are worth going over. + +### Duplicating a ScopeNode + +Below is the code for duplicating a ScopeNode. + +Our goals are: +1) Duplicate the name bindings across all stack levels +2) Make the new ScopeNode a user of all the bound nodes +3) Ensure that the order of defs in the duplicate is the same to allow easy merging + +For implementation [see `scopeNode.dup()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L142-L154) + +### Merging two ScopeNodes + +At the merge point we merge two ScopeNodes. The goals are: + +1) Merge names whose bindings have changed between the two nodes. For each such name, a Phi node is created, referencing the two original data nodes. +2) A new Region node is created representing the merged control flow. The phis have this region node as the first input. +3) After the merge is completed, the duplicate `ScopeNode` is discarded along with its edges. + +The merging logic takes advantage of the fact that the two ScopeNodes have the bound nodes in the same order in the list of inputs. This was ensured during duplicating the ScopeNode. +Although only the innermost occurrence of a name can have its binding changed, we scan all the nodes in our input list, and simply ignore ones where the binding has not changed. + +For implementation [see `ScopeNode.mergeScopes()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L164-L173) + + +## Example #1 + +We show the graph for the following code snippet: +```java +int a = 1; +if (arg == 1) + a = arg+2; +else + a = arg-3; +return a; +``` + +### Before Merging + +The following shows the graph just before we merge the two branches of the `if` statement in a `Region` node. + + + +Note the two `ScopeNode`s in the graph. +One has its `$ctrl` pointing to the `True` projection, while the other has `$ctrl` pointing to `False` projection. +The variable `a` is bound to the `Add` node in the `True` branch, whereas it is bound to the `Sub` node in the `False` branch. +Thus `a` will need a `Phi` node when merging the two scopes. + +### After Merging + +Below is the graph after we created a `Region` node and merged the two definitions of `a` in a `Phi` node. + + + +The duplicate `ScopeNode` has been discarded and was merged into the other one. +Since `a` had two different definitions in both scopes a `Phi` node was created +and is now referenced from `a`. The `Phi` node's inputs are the `Region` node +and the `Add` node from the `True` branch, and `Sub` node from the `False` +branch. The `arg` variable did not get assigned; both scopes agree on the +value so `arg` does not get a `Phi`. + +### Finally + +Here is the graph after the `return` statement was parsed and processed. + + + + + +## Example #2 + +Consider the following code snippet: +```java +int b = 0; +int c = 0; +if (arg == 1) { + b = 2; + c = 1; +} +else { + b = 1; +} +return b; +``` + +The value of `b` depends on which path the control flow took. +To resolve this, a Φ (Phi) function is inserted. + +``` +b = Phi(Region,2, 1); // values vary +c = Phi(Region,1, 0); // values vary, but dead +``` + +The `Phi` for `c` will die when the scope where `c` is defined dies. This does +not happen when merging but after the `return`. `return` is using `b` so `b` +stays alive. + +Before we go ahead and parse down the if statement we duplicate the scope: +```java +ScopeNode fScope = _scope.dup(); +/* Scope[$ctrl:$ctrl, arg:arg][b:0, c:0]*/ +``` + +We then will proceed and parse down the first branch of the if statement: +```java +// Parse the true side +ctrl(ifT); // set ctrl token to ifTrue projection +parseStatement(); // Parse true-side +ScopeNode tScope = _scope; + +/* Scope[$ctrl:True, arg:arg][b:2, c:1]*/ +``` + +Notice, this branch modified and set a new value for both symbols currently existing in the symbol table. +Now, we set the scope back to where we started (without the modifications that `ifT` made) + +```java +_scope = fScope; +``` + +We then will proceed and parse down the second branch of the if statement: +```java +if (matchx("else")) { + parseStatement(); + fScope = _scope; + + /* Scope[$ctrl:False, arg:arg][b:1, c:0]*/ +} +``` + +The two branches modified `b`; only the true branch modified `c`. Since the branch arms are also +lexical scopes, they cannot introduce new symbols in the current (outer) scope. +This means that the order of the name bindings stayed the same. Excluding the +first control node, we loop through and compare the nodes corresponding to the +same name binding to see if the nodes are different, if so we create a phi node +representing this conflict: + +```java + /* in(i); 2 */ + /* that.in(i); 1 */ + if( in(i) != that.in(i) ) // No need for redundant Phis + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); +``` + + + + + +## Example #3 + +Phis implement a peephole illustrated in the example: + +```java +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +``` + +The next two diagrams focus on the value rewrite. The unchanged `if` and +Region are omitted; Phi input 1 is the true arm and input 2 the false arm. +The Phis still use the same Region in the compiler's graph. + +Pre-peephole we have: + + + +Post-peephole: + + + +The common operator was pulled out and the Phi node only got applied to the +operands. Notice how only the second operand of the `==` changes, the first +one stays the same (`arg`). The implementation is in +[`PhiNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/PhiNode.java). + +In graph notation, with `r` denoting the same Region throughout: + +```text +Phi(r, a+b, c+d) -> Phi(r, a, c) + Phi(r, b, d) +``` + +We call this **pulling the operation down** through the Phi: the common +operation moves from the incoming paths to after their merge. Each new Phi +selects the corresponding operand from the same path. If an operand is shared, +as `arg` is above, its Phi collapses to that operand. + + +## Pushing addition up through a Phi + +The opposite direction can expose constant folding. For example: + +```java +int x = 1; +if( arg ) x = 2; +return (arg+x)+3; +``` + +The merge gives `x` a Phi of constants. Although `x` itself is not constant, +adding 3 to each possible value is a compile-time calculation. The addition +peephole reassociates the expression and **pushes the addition up** onto the +incoming paths: + +```text +(arg + Phi(r, 2, 1)) + 3 + -> arg + Phi(r, 2+3, 1+3) + -> arg + Phi(r, 5, 4) +``` + +The implementation first appears here in +[`AddNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/AddNode.java), +for the shape `(x + Phi(constants)) + constant`. The final operand can also +be another Phi of constants, but both Phis must use the **same Region** so +their corresponding arms describe the same path. + +Why not push every operation through a Phi? That would duplicate work across +the incoming paths, and the pull-down peephole could immediately undo it. +Repeatedly applying the two rewrites would never finish. Here every new +addition folds to a constant **before** we build the result Phi. There are no +new additions left for that Phi to pull back down, and one runtime addition +has disappeared. The folding requirement supplies both the benefit and the +reason this pair of opposing rewrites terminates. + + +## More examples + +The next two simple `if` examples also omit control flow to highlight the +resulting values. Their Phi inputs retain the true/false order above. + +```java +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c; +``` + + + +```java +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b; +``` + + + +For nested branches, the control paths and Regions are shown so each Phi's +incoming paths remain clear: + +```java +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +``` + + + + + +[^1]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 132. + +[^2]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 129. + +[^3]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 86. + +[^4]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 102-103. diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 487afee9..359d0175 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.graph.GraphObserver; + import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -15,6 +16,11 @@ import java.util.*; */ public class Parser { + // Current compilation context; the observer belongs to the parser. + public static Parser PARSER; + public GraphObserver<Node> _obs; + public int pos() { return _lexer._position; } + /** * A Global Static, unique to each compilation. This is a public, so we @@ -24,17 +30,23 @@ public class Parser { * To make the compiler multithreaded, this field will have to move into a TLS. */ public static StartNode START; - // Current compilation context, like START; the observer belongs to the parser. - public static Parser PARSER; - public GraphObserver<Node> _obs; - public int pos() { return _lexer._position; } + + public StopNode STOP; // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** - * A ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds + * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time + * there is one current ScopeNode. The reason the current ScopeNode can change is to do with how + * we handle branching. See {@link #parseIf()}. + * <p> + * Each ScopeNode contains a stack of lexical scopes, each scope is a symbol table that binds * variable names to Nodes. The top of this stack represents current scope. + * <p> + * We keep a list of all ScopeNodes so that we can show them in graphs. + * @see #parseIf() + * @see #_xScopes */ public ScopeNode _scope; @@ -42,18 +54,28 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("else"); + add("false"); + add("if"); add("int"); add("return"); + add("true"); }}; + /** + * We clone ScopeNodes when control flows branch; it is useful to have + * a list of all active ScopeNodes for purposes of visualization of the SoN graph + */ + public final Stack<ScopeNode> _xScopes = new Stack<>(); + public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); START = new StartNode(new Type[]{ Type.CONTROL, arg }); - START.peephole(); + STOP = new StopNode(); } public Parser(String source) { @@ -72,17 +94,21 @@ public class Parser { private Node ctrl(Node n) { return _scope.ctrl(n); } - public ReturnNode parse() { + public StopNode parse() { + _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); _scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); _scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); - var ret = (ReturnNode) parseBlock(); + parseBlock(); _scope.pop(); + _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); - return ret; + STOP.peephole(); + return STOP; } + /** * Parses a block * @@ -95,21 +121,18 @@ public class Parser { private Node parseBlock() { // Enter a new scope _scope.push(); - Node n = null; - while (!peek('}') && !_lexer.isEOF()) { - Node n0 = parseStatement(); - if (n0 != null) n = n0; // Empty statements can return null - }; + while (!peek('}') && !_lexer.isEOF()) + parseStatement(); // Exit scope _scope.pop(); - return n; + return null; } /** * Parses a statement * * <pre> - * returnStatement | declStatement | blockStatement | expressionStatement + * returnStatement | declStatement | blockStatement | ifStatement | expressionStatement * </pre> * @return a {@link Node} or {@code null} */ @@ -117,11 +140,59 @@ public class Parser { if (matchx("return") ) return parseReturn(); else if (matchx("int")) return parseDecl(); else if (match ("{" )) return require(parseBlock(),"}"); + else if (matchx("if" )) return parseIf(); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } /** + * Parses a statement + * + * <pre> + * if ( expression ) statement [else statement] + * </pre> + * @return a {@link Node}, never {@code null} + */ + private Node parseIf() { + require("("); + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + // In if true branch, the ifT proj node becomes the ctrl + // But first clone the scope and set it as current + int ndefs = _scope.nIns(); + ScopeNode fScope = _scope.dup(); // Duplicate current scope + fScope.ctrl(ifF); // The pending arm already starts at False + _xScopes.push(fScope); // For graph visualization we need all scopes + + // Parse the true side + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse true-side + ScopeNode tScope = _scope; + + // Parse the false side + _scope = fScope; // Restore scope, then parse else block if any + if (matchx("else")) { + parseStatement(); + fScope = _scope; + } + + if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) + throw error("Cannot define a new name on one arm of an if"); + + // Merge results + _scope = tScope; + _xScopes.pop(); // Discard pushed from graph display + + return ctrl(tScope.mergeScopes(fScope)); + } + + + /** * Parses a return statement; "return" already parsed. * The $ctrl edge is killed. * @@ -132,7 +203,7 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - Node ret = new ReturnNode(ctrl(), expr).peephole(); + Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole()); ctrl(null); // Kill control return ret; } @@ -250,13 +321,15 @@ public class Parser { * Parse a primary expression: * * <pre> - * primaryExpr : integerLiteral | Identifier | '(' expression ')' + * primaryExpr : integerLiteral | Identifier | true | false | '(' expression ')' * </pre> * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber() ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); + if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); + if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole(); String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); Node n = _scope.lookup(name); diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 2fa4514e..367cb2c0 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -66,6 +66,24 @@ public class AddNode extends Node { if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + if( lhs.in(2) instanceof PhiNode phi && phi.allCons() && + // Do we have ((x + (phi cons)) + con) ? + // Do we have ((x + (phi cons)) + (phi cons)) ? + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + + // Note that this is the exact reverse of Phi pulling a common op + // down to reduce total op-count. We don't get in an endless push- + // up push-down peephole cycle because the constants all fold first. + (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) { + Node[] ns = new Node[phi.nIns()]; + ns[0] = phi.in(0); + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + for( int i=1; i<ns.length; i++ ) + ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole(); + String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : ""); + return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole()); + } + // Now we sort along the spine via rotates, to gather similar things together. // Do we rotate (x + y) + z @@ -78,15 +96,22 @@ public class AddNode extends Node { // Compare two off-spine nodes and decide what order they should be in. // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? - // Generally constants always go right, then others. + // Generally constants always go right, then Phi-of-constants, then muls, then others. // Ties with in a category sort by node ID. // TRUE if swapping hi and lo. static boolean spine_cmp( Node hi, Node lo ) { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; + if( lo instanceof PhiNode && lo.allCons() ) return false; + if( hi instanceof PhiNode && hi.allCons() ) return true ; + + if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; + if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; + // Same category of "others" return lo._nid > hi._nid; } + @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 4c79fa0b..aaf261d5 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -42,7 +42,7 @@ abstract public class BoolNode extends Node { return null; } - public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } } - public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } } - public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } } + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } } + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } } } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 08dea003..f6b4e03e 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -31,4 +31,6 @@ public class DivNode extends Node { return in(1); return null; } + + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java new file mode 100644 index 00000000..3b644bec --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeTuple; + +public class IfNode extends MultiNode { + + public IfNode(Node ctrl, Node pred) { + super(ctrl, pred); + } + + @Override + public String label() { return "If"; } + + @Override protected String format() { return "if( %1 )"; } + + @Override public boolean isCFG() { return true; } + + public Node ctrl() { return in(0); } + public Node pred() { return in(1); } + + @Override + public Type compute() { + return TypeTuple.IF; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index e866cf24..a881bd96 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -40,4 +40,5 @@ public class MulNode extends Node { return null; } + @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index bd72c8e4..72469ad2 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -213,7 +213,7 @@ public abstract class Node extends BaseNode<Node> { return deadCodeElim(n.peephole()); return null; // No progress - } + } // m is the new Node, self is the old. // Return 'm', which may have zero uses but is alive nonetheless. @@ -308,6 +308,20 @@ public abstract class Node extends BaseNode<Node> { return this; } + // does this node contain all constants? + // Ignores in(0), as is usually control. + boolean allCons() { + for( int i=1; i<nIns(); i++ ) + if( !(in(i)._type.isConstant()) ) + return false; + return true; + } + + // Make a shallow copy (same class) of this Node, with given inputs and + // empty outputs and a new Node ID. The original inputs are ignored. + // Does not need to be implemented in isCFG() nodes. + Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + /** * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java new file mode 100644 index 00000000..da3917c7 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -0,0 +1,74 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; + +public class PhiNode extends Node { + + final String _label; + + public PhiNode(String label, Node... inputs) { super(inputs); _label = label; } + + @Override public String label() { return "Phi_"+_label; } + + @Override + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + p.p("Phi("); + for( Node in : _inputs ) + p.n(in).p(","); + return p.unchar(',').close(); + } + + Node region() { return in(0); } + + @Override + public Type compute() { + Type t = in(1)._type; + for( int i=2; i<nIns(); i++ ) + t = t.meet(in(i)._type); + return t; + } + + @Override + public Node idealize() { + // Remove a "junk" Phi: Phi(x,x) is just x + if( same_inputs() ) + return in(1); + + // Pull "down" a common data op. One less op in the world. One more + // Phi, but Phis do not make code. + // Phi(op(A,B),op(Q,R),op(X,Y)) becomes + // op(Phi(A,Q,X), Phi(B,R,Y)). + Node op = in(1); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node[] lhss = new Node[nIns()]; + Node[] rhss = new Node[nIns()]; + lhss[0] = rhss[0] = in(0); // Set Region + for( int i=1; i<nIns(); i++ ) { + lhss[i] = in(i).in(1); + rhss[i] = in(i).in(2); + } + Node phi_lhs = new PhiNode(_label,lhss).peephole(); + Node phi_rhs = new PhiNode(_label,rhss).peephole(); + return op.copy(phi_lhs,phi_rhs); + } + + return null; + } + + private boolean same_op() { + for( int i=2; i<nIns(); i++ ) + if( in(1).getClass() != in(i).getClass() ) + return false; + return true; + } + + private boolean same_inputs() { + for( int i=2; i<nIns(); i++ ) + if( in(1) != in(i) ) + return false; + return true; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 063f9edc..8917fbd4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -25,7 +25,7 @@ public class ProjNode extends Node { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); } - @Override public boolean isCFG() { return _idx==0; } + @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java new file mode 100644 index 00000000..e29254ad --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; + +public class RegionNode extends Node { + public RegionNode(Node... inputs) { super(inputs); } + + @Override + public String label() { return "Region"; } + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.p(label()).p(_nid); + } + + @Override public boolean isCFG() { return true; } + + @Override + public Type compute() { + return Type.CONTROL; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 6ffa8939..90b97bae 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -133,4 +133,45 @@ public class ScopeNode extends Node { */ public Node ctrl(Node n) { return setDef(0,n); } + /** + * Duplicate a ScopeNode; including all levels, up to Nodes. So this is + * neither shallow (would dup the Scope but not the internal HashMap + * tables), nor deep (would dup the Scope, the HashMap tables, but then + * also the program Nodes). + * <p> + * The new Scope is a full-fledged Node with proper use<->def edges. + */ + public ScopeNode dup() { + ScopeNode dup = new ScopeNode(); + // Our goals are: + // 1) duplicate the name bindings of the ScopeNode across all stack levels + // 2) Make the new ScopeNode a user of all the nodes bound + // 3) Ensure that the order of defs is the same to allow easy merging + for( HashMap<String,Integer> syms : _scopes ) + dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied + for( int i=1; i<nIns(); i++ ) + dup.addDef(in(i)); + return dup; + } + + /** + * Merges the names whose node bindings differ, by creating Phi node for such names + * The names could occur at all stack levels, but a given name can only differ in the + * innermost stack level where the name is bound. + * + * @param that The ScopeNode to be merged into this + * @return A new node representing the merge point + */ + public Node mergeScopes(ScopeNode that) { + RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); + String[] ns = reverseNames(); + // Note that we skip i==0, which is bound to '$ctrl' + for (int i = 1; i < nIns(); i++) + if( in(i) != that.in(i) ) // No need for redundant Phis + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); + that.kill(); // Kill merged scope + return r; + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java new file mode 100644 index 00000000..9ae0acb4 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -0,0 +1,48 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; + +public class StopNode extends Node { + public StopNode(Node... inputs) { + super(inputs); + } + + @Override + public String label() { + return "Stop"; + } + + @Override + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + if( ret()!=null ) return p.n(ret()); + p.p("Stop[ "); + for( Node ret : _inputs ) + p.n(ret).p(" "); + return p.p("]"); + } + + @Override public boolean isCFG() { return true; } + + // If a single Return, return it. + // Otherwise, null because ambiguous. + public ReturnNode ret() { + return nIns()==1 ? (ReturnNode)in(0) : null; + } + + @Override + public Type compute() { + return Type.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } + + public Node addReturn(Node node) { + return addDef(node); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 43e684a1..7a6e1a4b 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -50,4 +50,5 @@ public class SubNode extends Node { return null; } + @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index b68012dc..930d5376 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** Chapter 4's view of the IR; no knowledge of browser, transport or layout. */ +/** Chapter 5's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String[] edgeNames(Node n) { @@ -13,10 +13,21 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { } @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; } - @Override protected Kind kind(Node n) { return n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA; } + @Override protected Kind kind(Node n) { + if( n instanceof StopNode ) return Kind.STOP; + if( n instanceof ScopeNode ) return Kind.SCOPE; + if( n instanceof StartNode ) return Kind.CTRL; + if( n instanceof RegionNode ) return Kind.REGION; + if( n instanceof PhiNode ) return Kind.PHI; + return n.isCFG() ? Kind.CTRL : Kind.DATA; + } + @Override protected Role role(Node n, int i) { - return n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC - : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA) - : i==0 ? Role.CTRL : Role.DATA; + if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; + if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : Role.DATA; + if( n instanceof ProjNode ) return n.isCFG() ? Role.CTRL : Role.DATA; + if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; + if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; + return Role.DATA; } } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index d655ed4a..a7604165 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,10 +7,11 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 4 needs only a parser; it has no worklist or distant dependencies. */ +/** Chapter 5's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; + private String _phase; public SimpleGraphObserver() { super(new SimpleGraphAdapter()); } public static void main(String[] args) throws IOException { GraphViewer.run(new SimpleGraphObserver()); @@ -18,11 +19,12 @@ public class SimpleGraphObserver extends GraphCapture<Node> { @Override protected void compile(String src) { _parser = new Parser(src); _parser._obs = this; + _phase = "Parse"; _ret = _parser.parse(); - phase("Parse"); + phase(_phase); } - @Override protected String phase() { return "Parse"; } - @Override protected int pos() { return _parser.pos(); } + @Override protected String phase() { return _phase; } + @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } @Override protected void detach() { if( _parser != null ) _parser._obs = null; _parser = null; @@ -31,6 +33,8 @@ public class SimpleGraphObserver extends GraphCapture<Node> { @Override protected Node scope() { return _parser._scope; } @Override protected void roots(ArrayList<Node> roots) { roots.add(Parser.START); + roots.add(_parser.STOP); + roots.addAll(_parser._xScopes); roots.add(_ret); } } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 466fb739..6b9130ba 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -41,13 +41,12 @@ public class Type { public boolean isConstant() { return _type == TTOP; } + public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} + + public Type meet(Type other) { return BOTTOM; } + @Override public final String toString() { return print(new StringBuilder()).toString(); } - - public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} - - public Type meet(Type other) { return Type.BOTTOM; } - } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 52befa38..da701865 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -16,11 +16,13 @@ public class TypeTuple extends Type { @Override public StringBuilder print(StringBuilder sb) { - sb.append("[ "); + sb.append("["); for( Type t : _types ) t.print(sb).append(","); sb.setLength(sb.length()-1); sb.append("]"); return sb; } + + public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL}); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 3d568337..547c36f8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -11,8 +11,9 @@ public class Chapter01Test { @Test public void testSimpleProgram() { Parser parser = new Parser("return 1;"); - ReturnNode ret = parser.parse(); + StopNode stop = parser.parse(); StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 6c816a23..a6075b75 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -11,49 +11,49 @@ public class Chapter02Test { @Test public void testParseGrammar() { Parser parser = new Parser("return 1+2*3+-5;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testAddPeephole() { Parser parser = new Parser("return 1+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 3;", ret.print()); } @Test public void testSubPeephole() { Parser parser = new Parser("return 1-2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return -1;", ret.print()); } @Test public void testMulPeephole() { Parser parser = new Parser("return 2*3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 6;", ret.print()); } @Test public void testDivPeephole() { Parser parser = new Parser("return 6/3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testMinusPeephole() { Parser parser = new Parser("return 6/-3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return -2;", ret.print()); } @Test public void testExample() { Parser parser = new Parser("return 1+2*3+-5;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 46b1ca33..c3cd43c3 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -11,28 +11,28 @@ public class Chapter03Test { @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testVarAdd() { Parser parser = new Parser("int a=1; int b=2; return a+b;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 3;", ret.print()); } @Test public void testVarScope() { Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 4;", ret.print()); } @Test public void testVarDist() { Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 195afbb7..e5840622 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -11,77 +11,78 @@ public class Chapter04Test { @Test public void testPeephole() { Parser parser = new Parser("return 1+arg+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testPeephole2() { Parser parser = new Parser("return (1+arg)+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testAdd0() { Parser parser = new Parser("return 0+arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void testAddAddMul() { Parser parser = new Parser("return arg+0+arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg*2);", ret.print()); } @Test public void testPeephole3() { Parser parser = new Parser("return 1+arg+2+arg+3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return ((arg*2)+6);", ret.print()); } @Test public void testMul1() { Parser parser = new Parser("return 1*arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void testSub0() { Parser parser = new Parser("return arg-0;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } @Test public void test0Sub() { Parser parser = new Parser("return 0-arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } @Test public void testSubNeg() { Parser parser = new Parser("return 3--arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testNegSub() { Parser parser = new Parser("return -arg-3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (-(arg+3));", ret.print()); } @Test public void testVarArg() { - Parser parser = new Parser("return arg;", TypeInteger.BOT); - ReturnNode ret = parser.parse(); + Parser parser = new Parser("return arg;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof ProjNode); assertTrue(ret.in(1) instanceof ProjNode); } @@ -89,49 +90,49 @@ public class Chapter04Test { @Test public void testConstantArg() { Parser parser = new Parser("return arg;", TypeInteger.constant(2)); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testCompEq() { Parser parser = new Parser("return 3==3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testCompEq2() { Parser parser = new Parser("return 3==4;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq() { Parser parser = new Parser("return 3!=3;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq2() { Parser parser = new Parser("return 3!=4;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testBug1() { Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testBug2() { Parser parser = new Parser("int a=arg+1; a=a; return a;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } @@ -148,14 +149,14 @@ public class Chapter04Test { @Test public void testBug4() { Parser parser = new Parser("return -arg;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } @Test public void testBug5() { Parser parser = new Parser("return arg--2;"); - ReturnNode ret = parser.parse(); + StopNode ret = parser.parse(); assertEquals("return (arg--2);", ret.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..d6c91a4a --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,225 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter05Test { + + @Test + public void testIfStmt() { + Parser parser = new Parser( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; +} +return a;"""); + StopNode ret = parser.parse(); + assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); + } + + @Test + public void testTest() { + Parser parser = new Parser( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c;""", TypeInteger.BOT); + StopNode ret = parser.parse(); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testReturn2() { + Parser parser = new Parser( +""" +if( arg==1 ) + return 3; +else + return 4; +""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("Stop[ return 3; return 4; ]", stop.toString()); + } + + @Test + public void testIfMergeB() { + Parser parser = new Parser( +""" +int a=arg+1; +int b=0; +if( arg==1 ) + b=a; +else + b=a+1; +return a+b;"""); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); + } + + @Test + public void testIfMerge2() { + Parser parser = new Parser( +""" +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b;"""); + StopNode ret = parser.parse(); + assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + } + + @Test + public void testMerge3() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); + } + + @Test + public void testMerge4() { + Parser parser = new Parser( +""" +int a=0; +int b=0; +if( arg ) + a=1; +if( arg==0 ) + b=2; +return arg+a+b; +""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString()); + } + + @Test + public void testMerge5() { + Parser parser = new Parser( +""" +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a;"""); + StopNode ret = parser.parse(); + assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); + } + + @Test + public void testMergeSameCon() { + Parser parser = new Parser( +""" +int a=arg; +if( arg==1 ) + a=3; +else + a=3; +return a; +"""); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.toString()); + } + + @Test + public void testTrue() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } + + @Test + public void testHalfDef() { + try { + new Parser("if( arg==1 ) int b=2; return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testHalfDef2() { + try { + new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'b'",e.getMessage()); + } + } + + @Test + public void testRegress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testBadNum() { + try { + new Parser("return 1-;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); + } + } + + @Test + public void testKeyword1() { + try { + new Parser("int true=0; return true;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'true'",e.getMessage()); + } + } + + @Test + public void testKeyword2() { + try { + new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'else'",e.getMessage()); + } + } + + @Test + public void testKeyword3() { + try { + new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected =: (",e.getMessage()); + } + } + +} |
