diff options
47 files changed, 2695 insertions, 79 deletions
@@ -1 +1,106 @@ -include $(firstword $(wildcard ../build-support/early-chapter.mk build-support/early-chapter.mk)) +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)) @@ -42,7 +42,7 @@ The Simple language is styled after a subset of C or Java. with constants. Peephole optimization / simple constant folding. * [Chapter 3](docs/chapter03/README.md): Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. -* Chapter 4: A non-constant external variable input +* [Chapter 4](docs/chapter04/README.md): A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. diff --git a/appendix/dce.md b/appendix/dce.md new file mode 100644 index 00000000..1f9dfa7a --- /dev/null +++ b/appendix/dce.md @@ -0,0 +1,166 @@ +# 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/chapter04/04-arg1.json b/docs/chapter04/04-arg1.json new file mode 100644 index 00000000..b16dc51b --- /dev/null +++ b/docs/chapter04/04-arg1.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-arg1.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": 5, "role": "ASSOC", "label": "0: arg"}], "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": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 6, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-arg1.svg b/docs/chapter04/04-arg1.svg new file mode 100644 index 00000000..b726b91f --- /dev/null +++ b/docs/chapter04/04-arg1.svg @@ -0,0 +1,81 @@ +<svg aria-label="Compiler graph" width="518" height="246" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 518 246" 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="e1i1" d="M242,115 C242,139 465.5,0 465.5,24" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #5 · ASSOC · 0: arg</title></path><path class="edge CTRL" id="e6i0" d="M84,118 L84,166" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#6[0] → #4 · CTRL</title></path><path class="edge DATA" id="e6i1" d="M242,118 L242,123 Q242,128 237,128 L132,128 Q124,128 124,136 L124,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#6[1] → #5 · 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(374,24)" style="opacity: 1;"><path class="box" d="M4,0H116Q120,0 120,4V52Q120,56 116,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="60" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #5 ASSOC 0: arg</title><line class="row" x1="0" x2="120" y1="30" y2="30"/><line class="row" x1="63" x2="63" y1="0" y2="30"/><text class="bind" x="31.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="91.5" y="20" text-anchor="middle">0: arg</text><circle class="port" cx="31.5" cy="0" r="3" fill="white"/><circle class="port" cx="91.5" cy="0" r="3" fill="#536477"/><text class="slot" x="31.5" y="-7" text-anchor="middle">0</text><text class="slot" x="91.5" y="-7" text-anchor="middle">1</text></g><g class="node" id="n2" data-id="2" transform="translate(24,24)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 Start +Type not computed + +</title></g><g class="node" id="n4" data-id="4" transform="translate(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #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(182,68)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>2</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 2 +Type not computed + +</title></g><g class="node" id="n6" data-id="6" transform="translate(44,172)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#6 Return +Type not computed + +[0] → #4 CTRL +[1] → #5 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter04/04-arg2.json b/docs/chapter04/04-arg2.json new file mode 100644 index 00000000..5d2d7fde --- /dev/null +++ b/docs/chapter04/04-arg2.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-arg2.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"}], "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": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 6, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-arg2.svg b/docs/chapter04/04-arg2.svg new file mode 100644 index 00000000..6083ae9b --- /dev/null +++ b/docs/chapter04/04-arg2.svg @@ -0,0 +1,82 @@ +<svg aria-label="Compiler graph" width="486" height="246" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 486 246" 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="e1i1" d="M204,115 C204,139 433.5,0 433.5,24" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #6 · ASSOC · 0: arg</title></path><path class="edge CTRL" id="e5i0" d="M84,118 L84,166" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#5[0] → #4 · CTRL</title></path><path class="edge DATA" id="e5i1" d="M204,118 L204,123 Q204,128 199,128 L132,128 Q124,128 124,136 L124,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#5[1] → #6 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(342,24)" style="opacity: 1;"><path class="box" d="M4,0H116Q120,0 120,4V52Q120,56 116,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="60" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #6 ASSOC 0: arg</title><line class="row" x1="0" x2="120" y1="30" y2="30"/><line class="row" x1="63" x2="63" y1="0" y2="30"/><text class="bind" x="31.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="91.5" y="20" text-anchor="middle">0: arg</text><circle class="port" cx="31.5" cy="0" r="3" fill="white"/><circle class="port" cx="91.5" cy="0" r="3" fill="#536477"/><text class="slot" x="31.5" y="-7" text-anchor="middle">0</text><text class="slot" x="91.5" y="-7" text-anchor="middle">1</text></g><g class="node" id="n2" data-id="2" transform="translate(24,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(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #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(44,172)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 Return +Type not computed + +[0] → #4 CTRL +[1] → #6 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g><g class="node" id="n6" data-id="6" transform="translate(144,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><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/chapter04/04-dce1.svg b/docs/chapter04/04-dce1.svg new file mode 100644 index 00000000..c63a85f7 --- /dev/null +++ b/docs/chapter04/04-dce1.svg @@ -0,0 +1,100 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.40.1 (20161225.0304) + --> +<!-- Title: chapter04 Pages: 1 --> +<svg width="204pt" height="258pt" viewBox="0.00 0.00 204.00 258.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 254)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-254 200,-254 200,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="19,-88 19,-242 187,-242 187,-88 19,-88"/> +</g> +<g id="clust2" class="cluster"> +<title>cluster_Scope1_0</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-76 188,-76 188,-8 8,-8"/> +</g> +<g id="clust3" class="cluster"> +<title>cluster_Scope1_1</title> +<polygon fill="none" stroke="#000000" points="110,-16 110,-68 180,-68 180,-16 110,-16"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="35,-204 35,-230 99,-230 99,-204 35,-204"/> +<polygon fill="none" stroke="#000000" points="35,-204 35,-230 99,-230 99,-204 35,-204"/> +<text text-anchor="start" x="53.7805" y="-212.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="35,-172 35,-204 99,-204 99,-172 35,-172"/> +<polygon fill="#ffff00" stroke="transparent" points="40,-177 40,-199 71,-199 71,-177 40,-177"/> +<polygon fill="none" stroke="#000000" points="40,-177 40,-199 71,-199 71,-177 40,-177"/> +<text text-anchor="start" x="42.6718" y="-183.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="71,-177 71,-199 94,-199 94,-177 71,-177"/> +<text text-anchor="start" x="73.5624" y="-183.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="#000000" cx="152" cy="-114" rx="27" ry="18"/> +<text text-anchor="middle" x="152" y="-109.8" font-family="Times,serif" font-size="14.00" fill="#000000">12</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="152" cy="-201" rx="27" ry="18"/> +<text text-anchor="middle" x="152" y="-196.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Return7 --> +<g id="node4" class="node"> +<title>Return7</title> +<polygon fill="#ffff00" stroke="#000000" points="107.1025,-132 52.8975,-132 52.8975,-96 107.1025,-96 107.1025,-132"/> +<text text-anchor="middle" x="80" y="-109.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return7->Start2 --> +<g id="edge1" class="edge"> +<title>Return7->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M68.6703,-132.0016C63.4509,-141.64 57.957,-154.1206 55.8715,-166.8193"/> +<polygon fill="#ff0000" stroke="#ff0000" points="52.3657,-166.7379 55,-177 59.3402,-167.335 52.3657,-166.7379"/> +<text text-anchor="middle" x="66.4467" y="-134.4016" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7->Con_6 --> +<g id="edge2" class="edge"> +<title>Return7->Con_6</title> +<path fill="none" stroke="#000000" d="M94.9184,-132.0265C105.7302,-145.0906 120.4588,-162.8877 132.2466,-177.1313"/> +<polygon fill="#000000" stroke="#000000" points="129.7233,-179.572 138.7954,-185.0444 135.1161,-175.109 129.7233,-179.572"/> +<text text-anchor="middle" x="92.6948" y="-134.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Scope1_0 --> +<g id="node5" class="node"> +<title>Scope1_0</title> +<polygon fill="#00ffff" stroke="transparent" points="25,-31 25,-53 38,-53 38,-31 25,-31"/> +<polygon fill="none" stroke="#000000" points="25,-31 25,-53 38,-53 38,-31 25,-31"/> +<text text-anchor="start" x="28" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">0</text> +<polygon fill="none" stroke="#000000" points="38,-31 38,-53 69,-53 69,-31 38,-31"/> +<text text-anchor="start" x="40.6718" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +<polygon fill="none" stroke="#000000" points="69,-31 69,-53 92,-53 92,-31 69,-31"/> +<text text-anchor="start" x="71.5624" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">arg</text> +</g> +<!-- Scope1_0->Start2 --> +<g id="edge3" class="edge"> +<title>Scope1_0:Scope1_0_arg->Start2:p1</title> +<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M81,-53C81,-75.6361 52.952,-67.2092 44,-88 36.2663,-105.9613 37.1652,-113.6777 44,-132 51.8047,-152.9223 74.2036,-151.7329 81.0127,-166.7479"/> +<polygon fill="#6495ed" stroke="#6495ed" points="77.6609,-167.8488 83,-177 84.533,-166.5167 77.6609,-167.8488"/> +</g> +<!-- Scope1_1 --> +<g id="node6" class="node"> +<title>Scope1_1</title> +<polygon fill="#00ffff" stroke="transparent" points="133,-31 133,-53 146,-53 146,-31 133,-31"/> +<polygon fill="none" stroke="#000000" points="133,-31 133,-53 146,-53 146,-31 133,-31"/> +<text text-anchor="start" x="136" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +<polygon fill="none" stroke="#000000" points="146,-31 146,-53 158,-53 158,-31 146,-31"/> +<text text-anchor="start" x="148.8927" y="-37.4" font-family="Times,serif" font-size="14.00" fill="#000000">a</text> +</g> +<!-- Scope1_1->Con_5 --> +<g id="edge4" class="edge"> +<title>Scope1_1:Scope1_1_a->Con_5</title> +<path fill="none" stroke="#6495ed" stroke-dasharray="5,2" d="M152,-53C152,-63.6896 152,-75.4328 152,-85.737"/> +<polygon fill="#6495ed" stroke="#6495ed" points="148.5001,-85.8496 152,-95.8497 155.5001,-85.8497 148.5001,-85.8496"/> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-dce2.svg b/docs/chapter04/04-dce2.svg new file mode 100644 index 00000000..e3719bcc --- /dev/null +++ b/docs/chapter04/04-dce2.svg @@ -0,0 +1,59 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.40.1 (20161225.0304) + --> +<!-- Title: chapter04 Pages: 1 --> +<svg width="114pt" height="250pt" viewBox="0.00 0.00 114.00 250.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 246)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-246 110,-246 110,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-234 98,-234 98,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="33,-196 33,-222 74,-222 74,-196 33,-196"/> +<polygon fill="none" stroke="#000000" points="33,-196 33,-222 74,-222 74,-196 33,-196"/> +<text text-anchor="start" x="40.2805" y="-204.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="33,-164 33,-196 74,-196 74,-164 33,-164"/> +<polygon fill="#ffff00" stroke="transparent" points="38,-169 38,-191 69,-191 69,-169 38,-169"/> +<polygon fill="none" stroke="#000000" points="38,-169 38,-191 69,-191 69,-169 38,-169"/> +<text text-anchor="start" x="40.6718" y="-175.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +</g> +<!-- Con_6 --> +<g id="node2" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="43" cy="-106" rx="27" ry="18"/> +<text text-anchor="middle" x="43" y="-101.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Con_6->Start2 --> +<g id="edge1" class="edge"> +<title>Con_6->Start2</title> +<path fill="none" stroke="#ff0000" d="M45.072,-124.0265C45.9366,-131.5481 46.9815,-140.6387 48.0249,-149.7167"/> +<polygon fill="#ff0000" stroke="#ff0000" points="44.5736,-150.3415 49.1927,-159.8764 51.5278,-149.5421 44.5736,-150.3415"/> +<text text-anchor="middle" x="42.8484" y="-126.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7 --> +<g id="node3" class="node"> +<title>Return7</title> +<polygon fill="#ffff00" stroke="#000000" points="80.1025,-52 25.8975,-52 25.8975,-16 80.1025,-16 80.1025,-52"/> +<text text-anchor="middle" x="53" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return7->Start2 --> +<g id="edge2" class="edge"> +<title>Return7->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M64.3196,-52.2322C69.9396,-62.3585 76.1294,-75.4211 79,-88 82.5597,-103.599 83.0135,-108.5115 79,-124 74.2474,-142.3411 60.2215,-145.475 55.5405,-159.004"/> +<polygon fill="#ff0000" stroke="#ff0000" points="52.0641,-158.5835 54,-169 58.9824,-159.6498 52.0641,-158.5835"/> +<text text-anchor="middle" x="62.096" y="-54.6322" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return7->Con_6 --> +<g id="edge3" class="edge"> +<title>Return7->Con_6</title> +<path fill="none" stroke="#000000" d="M50.4766,-52.1686C49.4071,-59.869 48.1353,-69.0257 46.9468,-77.5834"/> +<polygon fill="#000000" stroke="#000000" points="43.4664,-77.2003 45.5574,-87.5867 50.3999,-78.1633 43.4664,-77.2003"/> +<text text-anchor="middle" x="48.253" y="-54.5686" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-dce3.svg b/docs/chapter04/04-dce3.svg new file mode 100644 index 00000000..86fa6f0d --- /dev/null +++ b/docs/chapter04/04-dce3.svg @@ -0,0 +1,116 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 2.40.1 (20161225.0304) + --> +<!-- Title: chapter04 Pages: 1 --> +<svg width="458pt" height="178pt" viewBox="0.00 0.00 458.00 178.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 174)"> +<title>chapter04</title> +<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-174 454,-174 454,4 -4,4"/> +<g id="clust1" class="cluster"> +<title>cluster_Nodes</title> +<polygon fill="none" stroke="#000000" points="8,-8 8,-162 442,-162 442,-8 8,-8"/> +</g> +<!-- Start2 --> +<g id="node1" class="node"> +<title>Start2</title> +<polygon fill="#ffff00" stroke="transparent" points="25,-124 25,-150 66,-150 66,-124 25,-124"/> +<polygon fill="none" stroke="#000000" points="25,-124 25,-150 66,-150 66,-124 25,-124"/> +<text text-anchor="start" x="32.2805" y="-132.4" font-family="Times,serif" font-size="14.00" fill="#000000">Start</text> +<polygon fill="none" stroke="#000000" points="25,-92 25,-124 66,-124 66,-92 25,-92"/> +<polygon fill="#ffff00" stroke="transparent" points="30,-97 30,-119 61,-119 61,-97 30,-97"/> +<polygon fill="none" stroke="#000000" points="30,-97 30,-119 61,-119 61,-97 30,-97"/> +<text text-anchor="start" x="32.6718" y="-103.4" font-family="Times,serif" font-size="14.00" fill="#000000">$ctrl</text> +</g> +<!-- Con_5 --> +<g id="node2" class="node"> +<title>Con_5</title> +<ellipse fill="none" stroke="#000000" cx="335" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="335" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">2</text> +</g> +<!-- Con_6 --> +<g id="node3" class="node"> +<title>Con_6</title> +<ellipse fill="none" stroke="#000000" cx="407" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="407" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">1</text> +</g> +<!-- Add7 --> +<g id="node4" class="node"> +<title>Add7</title> +<ellipse fill="none" stroke="#000000" cx="371" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="371" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add7->Con_5 --> +<g id="edge1" class="edge"> +<title>Add7->Con_5</title> +<path fill="none" stroke="#000000" d="M363.7149,-51.6057C358.6889,-63.7518 351.9107,-80.1326 346.2018,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="342.8638,-92.842 342.2743,-103.4204 349.3319,-95.5185 342.8638,-92.842"/> +<text text-anchor="middle" x="361.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add7->Con_6 --> +<g id="edge2" class="edge"> +<title>Add7->Con_6</title> +<path fill="none" stroke="#000000" d="M378.2851,-51.6057C383.3111,-63.7518 390.0893,-80.1326 395.7982,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="392.6681,-95.5185 399.7257,-103.4204 399.1362,-92.842 392.6681,-95.5185"/> +<text text-anchor="middle" x="376.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Con_8 --> +<g id="node5" class="node"> +<title>Con_8</title> +<ellipse fill="none" stroke="#000000" cx="191" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="191" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text> +</g> +<!-- Con_9 --> +<g id="node6" class="node"> +<title>Con_9</title> +<ellipse fill="none" stroke="#000000" cx="263" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="263" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">3</text> +</g> +<!-- Add10 --> +<g id="node7" class="node"> +<title>Add10</title> +<ellipse fill="none" stroke="#000000" cx="227" cy="-34" rx="27" ry="18"/> +<text text-anchor="middle" x="227" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">+</text> +</g> +<!-- Add10->Con_8 --> +<g id="edge3" class="edge"> +<title>Add10->Con_8</title> +<path fill="none" stroke="#000000" d="M219.7149,-51.6057C214.6889,-63.7518 207.9107,-80.1326 202.2018,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="198.8638,-92.842 198.2743,-103.4204 205.3319,-95.5185 198.8638,-92.842"/> +<text text-anchor="middle" x="217.4913" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +<!-- Add10->Con_9 --> +<g id="edge4" class="edge"> +<title>Add10->Con_9</title> +<path fill="none" stroke="#000000" d="M234.2851,-51.6057C239.3111,-63.7518 246.0893,-80.1326 251.7982,-93.9289"/> +<polygon fill="#000000" stroke="#000000" points="248.6681,-95.5185 255.7257,-103.4204 255.1362,-92.842 248.6681,-95.5185"/> +<text text-anchor="middle" x="232.0615" y="-54.0057" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">2</text> +</g> +<!-- Con_11 --> +<g id="node8" class="node"> +<title>Con_11</title> +<ellipse fill="none" stroke="#000000" cx="119" cy="-121" rx="27" ry="18"/> +<text text-anchor="middle" x="119" y="-116.8" font-family="Times,serif" font-size="14.00" fill="#000000">6</text> +</g> +<!-- Return12 --> +<g id="node9" class="node"> +<title>Return12</title> +<polygon fill="#ffff00" stroke="#000000" points="109.1025,-52 54.8975,-52 54.8975,-16 109.1025,-16 109.1025,-52"/> +<text text-anchor="middle" x="82" y="-29.8" font-family="Times,serif" font-size="14.00" fill="#000000">Return</text> +</g> +<!-- Return12->Start2 --> +<g id="edge5" class="edge"> +<title>Return12->Start2:p0</title> +<path fill="none" stroke="#ff0000" d="M65.0542,-52.052C57.6135,-61.4899 49.9318,-73.7894 47.1181,-86.8747"/> +<polygon fill="#ff0000" stroke="#ff0000" points="43.6189,-86.6762 46,-97 50.5766,-87.4446 43.6189,-86.6762"/> +<text text-anchor="middle" x="62.8306" y="-54.452" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">0</text> +</g> +<!-- Return12->Con_11 --> +<g id="edge6" class="edge"> +<title>Return12->Con_11</title> +<path fill="none" stroke="#000000" d="M89.6664,-52.0265C94.8444,-64.2017 101.7707,-80.4878 107.5926,-94.1772"/> +<polygon fill="#000000" stroke="#000000" points="104.4613,-95.7577 111.5959,-103.5903 110.903,-93.0181 104.4613,-95.7577"/> +<text text-anchor="middle" x="87.4428" y="-54.4265" font-family="Helvetica,sans-Serif" font-size="8.00" fill="#000000">1</text> +</g> +</g> +</svg>
\ No newline at end of file diff --git a/docs/chapter04/04-grammar.md b/docs/chapter04/04-grammar.md new file mode 100644 index 00000000..0600679e --- /dev/null +++ b/docs/chapter04/04-grammar.md @@ -0,0 +1,72 @@ +# Grammar for Chapter 1 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + ; + + +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 + | '(' 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/chapter04/04-post-peephole.gv b/docs/chapter04/04-post-peephole.gv new file mode 100644 index 00000000..b893874f --- /dev/null +++ b/docs/chapter04/04-post-peephole.gv @@ -0,0 +1,43 @@ +digraph chapter04 { +/* +return 1+arg+2; +*/ + 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_10 [ label="#3" ]; + Add11 [ label="+" ]; + Return12 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$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></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Add11 -> Start2:p1[taillabel=1]; + Add11 -> Con_10[taillabel=2]; + Return12 -> Start2:p0[taillabel=0; color=red]; + Return12 -> Add11[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; +} diff --git a/docs/chapter04/04-post-peephole.json b/docs/chapter04/04-post-peephole.json new file mode 100644 index 00000000..4890ca67 --- /dev/null +++ b/docs/chapter04/04-post-peephole.json @@ -0,0 +1,18 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-post-peephole.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": 5, "role": "ASSOC", "label": "0: arg"}], "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": 10, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 11, "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": 10, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-post-peephole.svg b/docs/chapter04/04-post-peephole.svg new file mode 100644 index 00000000..d03218d6 --- /dev/null +++ b/docs/chapter04/04-post-peephole.svg @@ -0,0 +1,90 @@ +<svg aria-label="Compiler graph" width="638" height="350" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 638 350" 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="e1i1" d="M204,115 C204,139 585.5,0 585.5,24" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #5 · ASSOC · 0: arg</title></path><path class="edge DATA" id="e11i1" d="M204,118 L204,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[1] → #5 · DATA</title></path><path class="edge DATA" id="e11i2" d="M362,118 L362,123 Q362,128 357,128 L242,128 Q234,128 234,136 L234,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#11[2] → #10 · DATA</title></path><path class="edge CTRL" id="e12i0" d="M84,118 L84,270" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#12[0] → #4 · CTRL</title></path><path class="edge DATA" id="e12i1" d="M204,222 L204,227 Q204,232 199,232 L132,232 Q124,232 124,240 L124,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#12[1] → #11 · 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(494,24)" style="opacity: 1;"><path class="box" d="M4,0H116Q120,0 120,4V52Q120,56 116,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="60" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #5 ASSOC 0: arg</title><line class="row" x1="0" x2="120" y1="30" y2="30"/><line class="row" x1="63" x2="63" y1="0" y2="30"/><text class="bind" x="31.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="91.5" y="20" text-anchor="middle">0: arg</text><circle class="port" cx="31.5" cy="0" r="3" fill="white"/><circle class="port" cx="91.5" cy="0" r="3" fill="#536477"/><text class="slot" x="31.5" y="-7" text-anchor="middle">0</text><text class="slot" x="91.5" y="-7" text-anchor="middle">1</text></g><g class="node" id="n2" data-id="2" transform="translate(24,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(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #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(144,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="n10" data-id="10" transform="translate(302,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"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 #3 +Type not computed + +</title></g><g class="node" id="n11" data-id="11" transform="translate(144,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"> #11</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#11 + +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #10 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="n12" data-id="12" transform="translate(44,276)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 Return +Type not computed + +[0] → #4 CTRL +[1] → #11 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><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/chapter04/04-pre-peephole.gv b/docs/chapter04/04-pre-peephole.gv new file mode 100644 index 00000000..d0d7cb0c --- /dev/null +++ b/docs/chapter04/04-pre-peephole.gv @@ -0,0 +1,47 @@ +digraph chapter04 { +/* +return 1+arg+2; +*/ + 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_5 [ label="#1" ]; + Con_6 [ label="#2" ]; + Add7 [ label="+" ]; + Add8 [ label="+" ]; + Return9 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="cyan">0</TD><TD PORT="Scope1_0_$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></TR> + </TABLE>>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Add7 -> Start2:p1[taillabel=1]; + Add7 -> Con_6[taillabel=2]; + Add8 -> Con_5[taillabel=1]; + Add8 -> Add7[taillabel=2]; + Return9 -> Start2:p0[taillabel=0; color=red]; + Return9 -> Add8[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; +} diff --git a/docs/chapter04/04-pre-peephole.json b/docs/chapter04/04-pre-peephole.json new file mode 100644 index 00000000..839c16e7 --- /dev/null +++ b/docs/chapter04/04-pre-peephole.json @@ -0,0 +1,20 @@ +{ + "ver": 1, + "comp": "chapter04/docs/04-pre-peephole.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": 10, "role": "ASSOC", "label": "0: arg"}], "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": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"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": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "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}} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/04-pre-peephole.svg b/docs/chapter04/04-pre-peephole.svg new file mode 100644 index 00000000..813a48dd --- /dev/null +++ b/docs/chapter04/04-pre-peephole.svg @@ -0,0 +1,98 @@ +<svg aria-label="Compiler graph" width="638" height="454" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 638 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 ASSOC" id="e1i1" d="M204,115 C204,139 585.5,0 585.5,24" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#1[1] → #10 · ASSOC · 0: arg</title></path><path class="edge DATA" id="e7i1" d="M204,118 L204,123 Q204,128 209,128 L299,128 Q307,128 307,136 L307,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #10 · DATA</title></path><path class="edge DATA" id="e7i2" d="M362,118 L362,123 Q362,128 357,128 L345,128 Q337,128 337,136 L337,166" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #6 · DATA</title></path><path class="edge DATA" id="e8i1" d="M155,222 L155,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #5 · DATA</title></path><path class="edge DATA" id="e8i2" d="M307,222 L307,227 Q307,232 302,232 L193,232 Q185,232 185,240 L185,270" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #7 · DATA</title></path><path class="edge CTRL" id="e9i0" d="M84,118 L84,374" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#9[0] → #4 · CTRL</title></path><path class="edge DATA" id="e9i1" d="M155,326 L155,331 Q155,336 150,336 L132,336 Q124,336 124,344 L124,374" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[1] → #8 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(494,24)" style="opacity: 1;"><path class="box" d="M4,0H116Q120,0 120,4V52Q120,56 116,56H4Q0,56 0,52V4Q0,0 4,0Z" fill="#e5e0ff"/><text class="label" text-anchor="middle" x="60" y="48"><tspan>Scope</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #10 ASSOC 0: arg</title><line class="row" x1="0" x2="120" y1="30" y2="30"/><line class="row" x1="63" x2="63" y1="0" y2="30"/><text class="bind" x="31.5" y="20" text-anchor="middle">0: $ctrl</text><text class="bind" x="91.5" y="20" text-anchor="middle">0: arg</text><circle class="port" cx="31.5" cy="0" r="3" fill="white"/><circle class="port" cx="91.5" cy="0" r="3" fill="#536477"/><text class="slot" x="31.5" y="-7" text-anchor="middle">0</text><text class="slot" x="91.5" y="-7" text-anchor="middle">1</text></g><g class="node" id="n2" data-id="2" transform="translate(24,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(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #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(95,172)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 #1 +Type not computed + +</title></g><g class="node" id="n6" data-id="6" transform="translate(302,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(247,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] → #10 DATA +[2] → #6 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n8" data-id="8" transform="translate(95,276)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>+</tspan><tspan class="node-id"> #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(44,380)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 Return +Type not computed + +[0] → #4 CTRL +[1] → #8 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g><g class="node" id="n10" data-id="10" transform="translate(144,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><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/chapter04/Makefile b/docs/chapter04/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter04/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter04/README.md b/docs/chapter04/README.md new file mode 100644 index 00000000..837941b2 --- /dev/null +++ b/docs/chapter04/README.md @@ -0,0 +1,419 @@ +# Chapter 4: External Argument and Comparisons + +[Previous: Chapter 3](../chapter03/README.md) | +[Next: Chapter 5](../chapter05/README.md) + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Projection Nodes](#projection-nodes) +3. [Visualisation](#visualisation) +4. [Initial values](#initial-values) +5. [When Is Control Not-Null?](#when-is-control-not-null) +6. [Note Regarding Visualizations](#note-regarding-visualizations) +7. [Changes to Type System](#changes-to-type-system) +8. [Tuple Types](#tuple-types) +9. [$ctrl name binding](#ctrl-name-binding) +10. [More Peephole Optimizations](#more-peephole-optimizations) +11. [Peephole Walkthrough](#peephole-walkthrough) +12. [Dead Code Elimination(DCE)](#dead-code-eliminationdce) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter04) 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-chapter03...linear-chapter04) it to the previous chapter. + + +In this chapter we extend the language grammar with the following features: + +* The program receives a single argument named `arg` of integer type from the external environment. +* Expressions support comparison operators. +* We introduce a scope sensitive name binding `$ctrl` for the current incoming + control node. Thus, our Return is no longer hard-wired to Start, instead it + tracks the in scope `$ctrl` binding. + +Here is the [complete language grammar](04-grammar.md) for this chapter. + + + +## Extensions to Intermediate Representation + +In this chapter we add some new nodes and revise some existing nodes. +Following are revised or new nodes + +| Node Name | Type | Description | Inputs | Value | +|-----------|----------------|------------------------------------------------|-----------------------|----------------------------------------------------------------------------| +| MultiNode | Abstract class | A node that has a tuple result | | A tuple | +| Start | Control | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node | +| Proj | Data / Control | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index | +| Bool | Data | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false | +| Not | Data | Logical not | One data node | Result converts 0 to 1 and vice versa | + +> A `Proj` is a control node when it projects the control slot: `Proj#0` off `Start`. +> Every other projection is a data node. See `ProjNode.isCFG()`. + +We keep all other nodes from prior chapters. + + +## Projection Nodes + +We add projection nodes that are used to extract a specific tuple member from a multi-valued node. +Each projection node contains an index of the field to extract from its input node. +Projection nodes allow us to maintain labeled use-def edges as simple Node references. + +In the visuals, projection nodes are shown as rectangular boxes inside the node to which they are attached. + +### Visualisation + + + +In the visual above, the projection nodes have been tagged by the names +associated with the outputs of the Start node. Both MultiNodes that contain +Control and Control nodes are yellow. `$ctrl` and `arg` are outputs (users) of +StartNode(`START`) and have their MultiNode as their only input in slot 0. The +`label` has no semantics and is used during debug printing. + +```java +public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); +``` + +```java +_scope.define(ScopeNode.CTRL, new ProjNode(START, 0, ScopeNode.CTRL).peephole()); +_scope.define(ScopeNode.ARG0, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); +``` + +These projection nodes are going to extract the types for `CTRL` and `ARG0` from the `START` MultiNode. +The MultiNode holds the types as a TypeTuple: + +```java +public StartNode(Type[] args) { + super(); + _args = new TypeTuple(args); +``` + +Extracting the types is based on the `_idx`: +```java +return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; +``` + +### Initial values + +An argument is always provided, and defaults to `TypeInteger.BOT`. Individual +tests can (and do) pass in other integer values by calling `new Parser` with +an argument: + +```java +Parser parser = new Parser("return arg; ", TypeInteger.constant(2)); +``` + +The graph: + + + +- `$ctrl` and `arg` are both defined in the outermost symbol table, at lexical depth 0. +- There is an empty global-scope symbol table created at depth 1; in the future + global variables will be defined here. +- There is no line for the scope `$ctrl` because control is dead after the + return. It is manually set to null, which calls `setDef` to kill the node + (and killed nodes are not part of the program and not visualized). + +``` + ctrl(null); // Kill control +``` + +- The `arg` projection node is not included in the cluster because arg is a + constant. The `arg` was originally defined by a ProjNode; but when peephole + is called the computed type is a constant, and the ProjNode gets replaced + with a ConstantNode: + +```java +public final Node peephole( ) { + Type type = _type = compute(); + /* type = {TypeInteger@1527} "2" */ + + // ProjNode is not a constant unlike its type. + if (!(this instanceof ConstantNode) && type.isConstant()) + /* Create Constant(2) */ + return deadCodeElim(new ConstantNode(type).peephole()); + + /* won't get called */ + ... +``` + +If you don't pass an argument you get `TypeInteger.BOT` + +```java + Parser parser = new Parser("return arg; "); + ... + +public Parser(String source) { + this(source, TypeInteger.BOT); +} + +``` + +We clearly see this is not a constant: + +```java +public final static TypeInteger BOT = new TypeInteger(false, 1); + /* _is_con = false */ +``` + +So the `arg` projection node remains in the cluster: + + + + +#### When Is Control Not-Null? + +In later chapters, `$ctrl` will point to other control nodes, such as +`If` and `Region` (and `Loop`), but for now with no other control flow it always gets set to null after a `Return`. + +#### Note Regarding Visualizations + +From this chapter onwards we omit the edges from Constants to Start node, mainly to reduce +clutter and help draw the reader's attention to the more important aspects of the graph. + + + +## Changes to Type System + +In [Chapter 2](../chapter02/README.md) we introduced the Type System. + +We have annotated Nodes with Types and the Type annotation serves two purposes: + +* It defines the set of operations allowed on the Node, and +* it defines the set of values the Node takes on. + +We mentioned in [Chapter 2](../chapter02/README.md) that the set of values +associated with a Type at a specific Node can be conveniently represented as a +[lattice](https://en.wikipedia.org/wiki/Lattice_(order)). + +The type itself is identified by the Java class `Type` and subtypes. The type +implementation uses Java classes as a convenient way to deal with a Type's internal +structure - but the Java classes have no relation to a Type's place in the +lattice. + +In this chapter we extend the Type hierarchy as follows: + +``` +Type (Enhanced - now has Control, and a global Top and Bottom) ++-- TypeInteger (Enhanced - now has Top and Bottom types) ++-- TypeTuple (New - represents multi-valued result) +``` + +Our enhanced Lattice looks like this: + + + + +In this chapter we introduce the possibility of a program input variable named +`arg`; all we know about this variable is that it is some integer value, but we +do not know whether it is a constant or not. + +To support the requirements for non-constant integer values, we enhance +`TypeInteger` to allow it to represent `IntTop` and `IntBot` integer types in +addition to the earlier constant value. + +Now that integer values may be constants or non-constants, we need to introduce +the *meet* operator over our lattice. The `meet` operator describes rules that +define the resulting type when we combine integer values. In the lattice +diagram you can start from the two elements being `meet` and follow the +two arrows down the graph to the first point they meet. + +| | IntBot | Con1 | Con2 | IntTop | +|--------|--------|--------|--------|--------| +| IntBot | IntBot | IntBot | IntBot | IntBot | +| Con1 | IntBot | Con1 | IntBot | Con1 | +| IntTop | IntBot | Con1 | Con2 | IntTop | + +In the table above `Con1` and `Con2` represent two distinct integer values, and serve to explain the rules below. + +* The `meet` of `IntTop` with any integer constant is that constant. +* The `meet` of `IntBot` with any integer value is `IntBot`. +* The `meet` of any integer with itself is that integer. +* The `meet` of two unrelated integer constants is `IntBot`. + +Currently, all our integer valued nodes are either a constant or an `IntBot` integer type. +When we start optimizing loops, we will start seeing `IntTop` values. + + +### Tuple Types + +Tuple types need a little more explanation: they are a fixed-size grouping of +types; literally a `Type[]`. Tuples represent a collection of otherwise +unrelated types, and come from `MultiNode`s. `ProjNode`s will take the +appropriate `Type` array element out of a Tuple. The `StartNode` now produces +a 2-element `TypeTuple` with control and the type of `arg`: `[ctrl, TypeInteger.INTBOT]` + +The lattice `meet` operator on Tuples is done element by element; each array +element recursively calls `meet`. Tuples of mixed sizes are an internal +compiler error, and the `meet` uses Bottom for them. + + +## `$ctrl` name binding + +In previous chapters, we had a hard coded control input edge from Start to +Return. In this chapter we no longer have such a hard-wired edge. Instead, we +track the current in-scope control node via the name `$ctrl`. This means that +when we need to create an edge to the predecessor control node, we simply look +up this name in the current scope. + + +## More Peephole Optimizations + +Now that we have non-constant integer values, we can do additional +optimizations, rearranging algebraic expressions to enable constant +folding. For example: + +``` +return 1 + arg + 2; +``` + +We would expect the compiler to output `arg+3` here, but as it stands what we get is: + + + +We need to perform some algebraic simplifications to enable a better outcome. For +example, we need to rearrange the expression as follows: + +``` +arg + (1 + 2) +``` + +This then enables constant folding and the final outcome is shown below. By +canonicalizing expressions we fold common addressing math constants, remove +algebraic identities and generally simplify the code. + + + +Here is a list of peepholes introduced in this Chapter, more will be introduced in later chapters: + +| Before | After | Description | +|-----------------------|-----------------------|------------------------------------------------| +| (arg + 0 ) | arg | Add of zero identity | +| (arg - 0 ) | arg | Sub of zero identity | +| (arg * 1 ) | arg | Multiply by one identity | +| (con + arg) | (arg + con) | Move constants to right, to encourage folding | +| (con * arg) | (arg * con) | Move constants to right, to encourage folding | +| (con1 + (arg + con2)) | (arg + (con1 + con2)) | Move constants to right, to encourage folding | +| ((arg1 + con) + arg2) | ((arg1 + arg2) + con) | Move constants to right, to encourage folding | +| (arg + arg) | (arg * 2) | Sum-of-products form | +| (arg - arg) | 0 | Sub of same is 0 +| (0 - arg) | (-arg) | Sub from 0 is negation +| (arg1 - (-arg2)) | (arg1 + arg2) | Sub of negation is add +| ((-arg1) - arg2) | -(arg1 + arg2) | Sub from negation is negation of sum +| (con / 1) | con | Division by one +| (arg == arg) | 1 | Compare of same +| (arg != arg) | 0 | Compare of same +| (arg < arg) | 0 | Compare of same +| (arg > arg) | 0 | Compare of same +| (arg <= arg) | 1 | Compare of same +| (arg >= arg) | 1 | Compare of same + + +## Peephole Walkthrough + +The peephole optimizations introduced in this chapter are all local. They are triggered during parsing +as new nodes are created, before the newly created node has any uses. + +For example, when we parse a unary expression, and create a Node for the parsed expression, +`peephole()` is invoked on the newly created `MinusNode`: + +```java +private Node parseUnary() { + if (match("-")) return new MinusNode(parseUnary()).peephole(); + return parsePrimary(); +} +``` + +As another example, here is the parsing of comparison operators, also introduced in this chapter: + +```java +private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQNode(lhs, parseComparison()).peephole(); + if (match("!=")) return new BoolNode.NENode(lhs, parseComparison()).peephole(); + if (match("<=")) return new BoolNode.LENode(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LTNode(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.GENode(lhs, parseComparison()).peephole(); + if (match(">" )) return new BoolNode.GTNode(lhs, parseComparison()).peephole(); + return lhs; +} +``` + +The implementation of `peephole()` is in the main `Node` class, and is thus shared +by all subclasses of `Node`. + +```java +public final Node peephole( ) { + // Compute initial or improved Type + Type type = _type = compute(); + + // Replace constant computations from non-constants with a constant node + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); + + // Ask each node for a better replacement + Node n = idealize(); + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); + + return this; // No progress +} +``` + +The peephole method does the following: + +- Compute a Type for the node. +- If the Type is a Constant and the node is not a ConstantNode, replace with a + ConstantNode, recursively invoking peephole on the new constant. +- Otherwise, ask the Node for a better replacement via a call to `idealize()`. + The "better replacement" is things like `(1+2)` becomes `3` and `1+(x+2)` + becomes `(x+(1+2))`. +- Each Node subtype is responsible for deciding what the `idealize()` step + should do. If there is a better replacement then the node returns a non + `null` value. +- If we see a non `null` value, something changed, so we invoke `peephole()` + again and then also run dead code elimination on the (now dead and replaced) + `this` node. + +`peephole()` calls `deadCodeElim()` which is shown below. + + +## Dead Code Elimination(DCE) + +We call `kill` every time a Node makes the 1-user-to-0-users transition during +graph editing. This commonly happens when replacing via peeps and exiting +scopes. This recursive `kill` amounts to Dead Code Elimination in many other +compilers; here we call it in a very fine-grained way. Many Nodes will be +created by the parser, only to be killed before the very next lexeme is parsed. + +For more information please read the [appendix section](appendix/dce.md#appendix) on dead code elimination. + +The suggestively called `deadCodeElim` function is a thin wrapper over `kill` +used by `peepholeOpt` to avoid prematurely killing a Node which only briefly +makes the 1->0 users transition. + +```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; +} +``` + +Note the temporary add of a bogus user to the Node `m`. The reason this is +done is that we know `m` is the new replacement and is alive, but since it is +not yet hooked into the graph, it has no users yet. By adding a bogus user we +prevent it being mistaken for dead and being killed. diff --git a/docs/chapter04/lattice.gv b/docs/chapter04/lattice.gv new file mode 100644 index 00000000..6efef107 --- /dev/null +++ b/docs/chapter04/lattice.gv @@ -0,0 +1,97 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.6; + + TOP [label=<<B>⊤</B >>, fillcolor=black, fontcolor=white]; + BOT [label=<<B>⊥</B>>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + CTRL [label="ctrl", fillcolor=yellow, shape=oval]; + + TOP -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + TOP -> INT_TOP; + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + INT_BOT -> BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<<B>⊤</B >:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<<B>⊥</B>:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLE2 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLEN [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">...</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // Additional customization + {rank=same; TOP} + {rank=same; INT_TOP; TUPLE_TOP} + {rank=same; + CTRL; + INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; + } + {rank=same; INT_BOT, TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter04/lattice.svg b/docs/chapter04/lattice.svg new file mode 100644 index 00000000..35cb9296 --- /dev/null +++ b/docs/chapter04/lattice.svg @@ -0,0 +1,305 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="952pt" height="406pt"
+ viewBox="0.00 0.00 952.00 406.50" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 402.5)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-402.5 948,-402.5 948,4 -4,4"/>
+<!-- TOP -->
+<g id="node1" class="node">
+<title>TOP</title>
+<ellipse fill="black" stroke="black" cx="374" cy="-377.37" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="366.12" y="-372.95" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text>
+</g>
+<!-- CTRL -->
+<g id="node3" class="node">
+<title>CTRL</title>
+<ellipse fill="yellow" stroke="black" cx="27" cy="-199.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="27" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">ctrl</text>
+</g>
+<!-- TOP->CTRL -->
+<g id="edge1" class="edge">
+<title>TOP->CTRL</title>
+<path fill="none" stroke="black" d="M354.85,-367.54C297.95,-338.34 129.51,-251.87 58.81,-215.58"/>
+<polygon fill="black" stroke="black" points="60.56,-212.54 50.07,-211.09 57.36,-218.77 60.56,-212.54"/>
+</g>
+<!-- INT_TOP -->
+<g id="node4" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="374" cy="-302.25" rx="33.95" ry="18"/>
+<text text-anchor="start" x="357.12" y="-298.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="372.88" y="-298.2" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- TOP->INT_TOP -->
+<g id="edge3" class="edge">
+<title>TOP->INT_TOP</title>
+<path fill="none" stroke="black" d="M374,-356C374,-348.51 374,-339.87 374,-331.79"/>
+<polygon fill="black" stroke="black" points="377.5,-332.05 374,-322.05 370.5,-332.05 377.5,-332.05"/>
+</g>
+<!-- TUPLE_TOP -->
+<g id="node13" class="node">
+<title>TUPLE_TOP</title>
+<ellipse fill="pink" stroke="black" cx="771" cy="-302.25" rx="42.65" ry="18"/>
+<text text-anchor="start" x="747.75" y="-298.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="763.5" y="-298.2" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TOP->TUPLE_TOP -->
+<g id="edge25" class="edge">
+<title>TOP->TUPLE_TOP</title>
+<path fill="none" stroke="black" d="M395.06,-372.49C455.97,-361.27 633.5,-328.57 721.03,-312.45"/>
+<polygon fill="black" stroke="black" points="721.57,-315.91 730.77,-310.66 720.3,-309.03 721.57,-315.91"/>
+</g>
+<!-- BOT -->
+<g id="node2" class="node">
+<title>BOT</title>
+<ellipse fill="black" stroke="black" cx="374" cy="-21.12" rx="21.12" ry="21.12"/>
+<text text-anchor="start" x="366.12" y="-16.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text>
+</g>
+<!-- CTRL->BOT -->
+<g id="edge2" class="edge">
+<title>CTRL->BOT</title>
+<path fill="none" stroke="black" d="M48.71,-188.11C108.7,-157.31 276.83,-71 344.87,-36.08"/>
+<polygon fill="black" stroke="black" points="346.26,-39.3 353.55,-31.62 343.06,-33.07 346.26,-39.3"/>
+</g>
+<!-- INT_MIN -->
+<g id="node6" class="node">
+<title>INT_MIN</title>
+<ellipse fill="lightblue" stroke="black" cx="116" cy="-199.25" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="116" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">-n</text>
+</g>
+<!-- INT_TOP->INT_MIN -->
+<g id="edge4" class="edge">
+<title>INT_TOP->INT_MIN</title>
+<path fill="none" stroke="black" d="M347.36,-290.82C298.27,-271.6 193.98,-230.78 143.94,-211.18"/>
+<polygon fill="black" stroke="black" points="145.28,-207.95 134.69,-207.56 142.73,-214.47 145.28,-207.95"/>
+</g>
+<!-- INT_MINDOTS -->
+<g id="node7" class="node">
+<title>INT_MINDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="205" cy="-199.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="205" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MINDOTS -->
+<g id="edge5" class="edge">
+<title>INT_TOP->INT_MINDOTS</title>
+<path fill="none" stroke="black" d="M352.25,-288.25C322.2,-270.29 267.88,-237.83 234.28,-217.75"/>
+<polygon fill="black" stroke="black" points="236.25,-214.85 225.87,-212.72 232.66,-220.85 236.25,-214.85"/>
+</g>
+<!-- INT_MINUS -->
+<g id="node8" class="node">
+<title>INT_MINUS</title>
+<ellipse fill="lightblue" stroke="black" cx="294" cy="-199.25" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="294" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">-1</text>
+</g>
+<!-- INT_TOP->INT_MINUS -->
+<g id="edge6" class="edge">
+<title>INT_TOP->INT_MINUS</title>
+<path fill="none" stroke="black" d="M361.5,-285.47C348.27,-268.76 327.25,-242.23 312.18,-223.21"/>
+<polygon fill="black" stroke="black" points="315.02,-221.14 306.06,-215.48 309.53,-225.49 315.02,-221.14"/>
+</g>
+<!-- INT_ZERO -->
+<g id="node9" class="node">
+<title>INT_ZERO</title>
+<ellipse fill="lightblue" stroke="black" cx="374" cy="-199.25" rx="18" ry="18"/>
+<text text-anchor="middle" x="374" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_TOP->INT_ZERO -->
+<g id="edge7" class="edge">
+<title>INT_TOP->INT_ZERO</title>
+<path fill="none" stroke="black" d="M374,-284.12C374,-269.02 374,-246.74 374,-228.93"/>
+<polygon fill="black" stroke="black" points="377.5,-228.98 374,-218.98 370.5,-228.98 377.5,-228.98"/>
+</g>
+<!-- INT_PLUS -->
+<g id="node10" class="node">
+<title>INT_PLUS</title>
+<ellipse fill="lightblue" stroke="black" cx="453" cy="-199.25" rx="18" ry="18"/>
+<text text-anchor="middle" x="453" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">1</text>
+</g>
+<!-- INT_TOP->INT_PLUS -->
+<g id="edge8" class="edge">
+<title>INT_TOP->INT_PLUS</title>
+<path fill="none" stroke="black" d="M386.34,-285.47C399.49,-268.67 420.4,-241.93 435.3,-222.88"/>
+<polygon fill="black" stroke="black" points="437.93,-225.2 441.33,-215.17 432.41,-220.89 437.93,-225.2"/>
+</g>
+<!-- INT_MAXDOTS -->
+<g id="node11" class="node">
+<title>INT_MAXDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="541" cy="-199.25" rx="27" ry="18"/>
+<text text-anchor="middle" x="541" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MAXDOTS -->
+<g id="edge9" class="edge">
+<title>INT_TOP->INT_MAXDOTS</title>
+<path fill="none" stroke="black" d="M395.83,-288.04C425.56,-270.07 478.84,-237.84 511.93,-217.83"/>
+<polygon fill="black" stroke="black" points="513.46,-221 520.2,-212.83 509.84,-215.01 513.46,-221"/>
+</g>
+<!-- INT_MAX -->
+<g id="node12" class="node">
+<title>INT_MAX</title>
+<ellipse fill="lightblue" stroke="black" cx="632" cy="-199.25" rx="21.15" ry="21.15"/>
+<text text-anchor="middle" x="632" y="-194.2" font-family="Times New Roman,serif" font-size="14.00">+n</text>
+</g>
+<!-- INT_TOP->INT_MAX -->
+<g id="edge10" class="edge">
+<title>INT_TOP->INT_MAX</title>
+<path fill="none" stroke="black" d="M400.64,-290.82C449,-271.89 550.91,-231.99 601.78,-212.08"/>
+<polygon fill="black" stroke="black" points="602.96,-215.38 610.99,-208.47 600.41,-208.86 602.96,-215.38"/>
+</g>
+<!-- INT_BOT -->
+<g id="node5" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="374" cy="-96.25" rx="33.95" ry="18"/>
+<text text-anchor="start" x="357.12" y="-92.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="372.88" y="-92.2" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_BOT->BOT -->
+<g id="edge18" class="edge">
+<title>INT_BOT->BOT</title>
+<path fill="none" stroke="black" d="M374,-77.92C374,-70.74 374,-62.18 374,-53.95"/>
+<polygon fill="black" stroke="black" points="377.5,-54.22 374,-44.22 370.5,-54.22 377.5,-54.22"/>
+</g>
+<!-- INT_MIN->INT_BOT -->
+<g id="edge11" class="edge">
+<title>INT_MIN->INT_BOT</title>
+<path fill="none" stroke="black" d="M133.33,-191.46C174.74,-175.25 280.22,-133.96 336.8,-111.81"/>
+<polygon fill="black" stroke="black" points="337.98,-115.11 346.02,-108.2 335.43,-108.59 337.98,-115.11"/>
+</g>
+<!-- INT_MIN->INT_MINDOTS -->
+<!-- INT_MINDOTS->INT_BOT -->
+<g id="edge12" class="edge">
+<title>INT_MINDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M224.72,-186.46C253.64,-169.18 307.88,-136.76 342.4,-116.13"/>
+<polygon fill="black" stroke="black" points="343.92,-119.3 350.71,-111.17 340.33,-113.29 343.92,-119.3"/>
+</g>
+<!-- INT_MINDOTS->INT_MINUS -->
+<!-- INT_MINUS->INT_BOT -->
+<g id="edge13" class="edge">
+<title>INT_MINUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M305.12,-184.2C317.82,-168.18 338.81,-141.67 354.29,-122.13"/>
+<polygon fill="black" stroke="black" points="356.98,-124.37 360.45,-114.35 351.5,-120.02 356.98,-124.37"/>
+</g>
+<!-- INT_MINUS->INT_ZERO -->
+<!-- INT_ZERO->INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_ZERO->INT_BOT</title>
+<path fill="none" stroke="black" d="M374,-181.12C374,-166.02 374,-143.74 374,-125.93"/>
+<polygon fill="black" stroke="black" points="377.5,-125.98 374,-115.98 370.5,-125.98 377.5,-125.98"/>
+</g>
+<!-- INT_ZERO->INT_PLUS -->
+<!-- INT_PLUS->INT_BOT -->
+<g id="edge15" class="edge">
+<title>INT_PLUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M442.35,-184.63C429.9,-168.71 409.04,-142.04 393.63,-122.35"/>
+<polygon fill="black" stroke="black" points="396.42,-120.23 387.5,-114.51 390.9,-124.54 396.42,-120.23"/>
+</g>
+<!-- INT_PLUS->INT_MAXDOTS -->
+<!-- INT_MAXDOTS->INT_BOT -->
+<g id="edge16" class="edge">
+<title>INT_MAXDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M521.52,-186.46C492.93,-169.18 439.34,-136.76 405.22,-116.13"/>
+<polygon fill="black" stroke="black" points="407.39,-113.35 397.03,-111.17 403.77,-119.34 407.39,-113.35"/>
+</g>
+<!-- INT_MAXDOTS->INT_MAX -->
+<!-- INT_MAX->INT_BOT -->
+<g id="edge17" class="edge">
+<title>INT_MAX->INT_BOT</title>
+<path fill="none" stroke="black" d="M612.61,-190.66C569.87,-173.93 466.96,-133.64 411.28,-111.84"/>
+<polygon fill="black" stroke="black" points="412.8,-108.68 402.21,-108.29 410.25,-115.2 412.8,-108.68"/>
+</g>
+<!-- TUPLE1 -->
+<g id="node15" class="node">
+<title>TUPLE1</title>
+<polygon fill="none" stroke="none" points="750,-225.75 696,-225.75 696,-172.75 750,-172.75 750,-225.75"/>
+<polygon fill="pink" stroke="none" points="706.5,-199.25 706.5,-221.75 739.5,-221.75 739.5,-199.25 706.5,-199.25"/>
+<polygon fill="none" stroke="black" points="706.5,-199.25 706.5,-221.75 739.5,-221.75 739.5,-199.25 706.5,-199.25"/>
+<text text-anchor="start" x="709.5" y="-205.45" font-family="Times New Roman,serif" font-size="14.00">tuple</text>
+<polygon fill="black" stroke="none" points="706.5,-176.75 706.5,-199.25 739.5,-199.25 739.5,-176.75 706.5,-176.75"/>
+<polygon fill="none" stroke="black" points="706.5,-176.75 706.5,-199.25 739.5,-199.25 739.5,-176.75 706.5,-176.75"/>
+<text text-anchor="start" x="711.38" y="-182.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLE1 -->
+<g id="edge26" class="edge">
+<title>TUPLE_TOP->TUPLE1</title>
+<path fill="none" stroke="black" d="M762.86,-284.12C756.58,-270.91 747.69,-252.2 739.89,-235.8"/>
+<polygon fill="black" stroke="black" points="743.07,-234.33 735.62,-226.8 736.75,-237.34 743.07,-234.33"/>
+</g>
+<!-- TUPLE2 -->
+<g id="node16" class="node">
+<title>TUPLE2</title>
+<polygon fill="none" stroke="none" points="847,-237 793,-237 793,-161.5 847,-161.5 847,-237"/>
+<polygon fill="pink" stroke="none" points="803.5,-210.5 803.5,-233 836.5,-233 836.5,-210.5 803.5,-210.5"/>
+<polygon fill="none" stroke="black" points="803.5,-210.5 803.5,-233 836.5,-233 836.5,-210.5 803.5,-210.5"/>
+<text text-anchor="start" x="806.5" y="-216.7" font-family="Times New Roman,serif" font-size="14.00">tuple</text>
+<polygon fill="black" stroke="none" points="803.5,-188 803.5,-210.5 836.5,-210.5 836.5,-188 803.5,-188"/>
+<polygon fill="none" stroke="black" points="803.5,-188 803.5,-210.5 836.5,-210.5 836.5,-188 803.5,-188"/>
+<text text-anchor="start" x="808.38" y="-194.2" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="803.5,-165.5 803.5,-188 836.5,-188 836.5,-165.5 803.5,-165.5"/>
+<polygon fill="none" stroke="black" points="803.5,-165.5 803.5,-188 836.5,-188 836.5,-165.5 803.5,-165.5"/>
+<text text-anchor="start" x="808.38" y="-171.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLE2 -->
+<g id="edge27" class="edge">
+<title>TUPLE_TOP->TUPLE2</title>
+<path fill="none" stroke="black" d="M779.31,-284.12C784.32,-273.8 790.95,-260.12 797.41,-246.81"/>
+<polygon fill="black" stroke="black" points="800.41,-248.65 801.62,-238.13 794.11,-245.6 800.41,-248.65"/>
+</g>
+<!-- TUPLEN -->
+<g id="node17" class="node">
+<title>TUPLEN</title>
+<polygon fill="none" stroke="none" points="944,-248.25 890,-248.25 890,-150.25 944,-150.25 944,-248.25"/>
+<polygon fill="pink" stroke="none" points="900.5,-221.75 900.5,-244.25 933.5,-244.25 933.5,-221.75 900.5,-221.75"/>
+<polygon fill="none" stroke="black" points="900.5,-221.75 900.5,-244.25 933.5,-244.25 933.5,-221.75 900.5,-221.75"/>
+<text text-anchor="start" x="903.5" y="-227.95" font-family="Times New Roman,serif" font-size="14.00">tuple</text>
+<polygon fill="black" stroke="none" points="900.5,-199.25 900.5,-221.75 933.5,-221.75 933.5,-199.25 900.5,-199.25"/>
+<polygon fill="none" stroke="black" points="900.5,-199.25 900.5,-221.75 933.5,-221.75 933.5,-199.25 900.5,-199.25"/>
+<text text-anchor="start" x="905.38" y="-205.45" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+<polygon fill="black" stroke="none" points="900.5,-176.75 900.5,-199.25 933.5,-199.25 933.5,-176.75 900.5,-176.75"/>
+<polygon fill="none" stroke="black" points="900.5,-176.75 900.5,-199.25 933.5,-199.25 933.5,-176.75 900.5,-176.75"/>
+<text text-anchor="start" x="911.38" y="-182.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text>
+<polygon fill="black" stroke="none" points="900.5,-154.25 900.5,-176.75 933.5,-176.75 933.5,-154.25 900.5,-154.25"/>
+<polygon fill="none" stroke="black" points="900.5,-154.25 900.5,-176.75 933.5,-176.75 933.5,-154.25 900.5,-154.25"/>
+<text text-anchor="start" x="905.38" y="-160.45" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text>
+</g>
+<!-- TUPLE_TOP->TUPLEN -->
+<g id="edge28" class="edge">
+<title>TUPLE_TOP->TUPLEN</title>
+<path fill="none" stroke="black" d="M792.54,-286.35C815.75,-270.29 853.06,-244.48 880.79,-225.3"/>
+<polygon fill="black" stroke="black" points="882.68,-228.25 888.91,-219.68 878.7,-222.49 882.68,-228.25"/>
+</g>
+<!-- TUPLE_BOT -->
+<g id="node14" class="node">
+<title>TUPLE_BOT</title>
+<ellipse fill="pink" stroke="black" cx="771" cy="-96.25" rx="42.65" ry="18"/>
+<text text-anchor="start" x="747.75" y="-92.2" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="763.5" y="-92.2" font-family="Times New Roman,serif" font-size="14.00">:tuple</text>
+</g>
+<!-- TUPLE_BOT->BOT -->
+<g id="edge32" class="edge">
+<title>TUPLE_BOT->BOT</title>
+<path fill="none" stroke="black" d="M732.57,-88.17C654.42,-73.77 478.23,-41.32 405.9,-28"/>
+<polygon fill="black" stroke="black" points="406.78,-24.6 396.31,-26.23 405.51,-31.49 406.78,-24.6"/>
+</g>
+<!-- TUPLE1->TUPLE_BOT -->
+<g id="edge29" class="edge">
+<title>TUPLE1->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M735.11,-172.76C742.13,-158 750.96,-139.41 758.11,-124.38"/>
+<polygon fill="black" stroke="black" points="761.18,-126.06 762.31,-115.53 754.86,-123.06 761.18,-126.06"/>
+</g>
+<!-- TUPLE2->TUPLE_BOT -->
+<g id="edge30" class="edge">
+<title>TUPLE2->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M802.17,-161.5C796.24,-149.27 789.75,-135.89 784.23,-124.51"/>
+<polygon fill="black" stroke="black" points="787.46,-123.15 779.94,-115.69 781.16,-126.21 787.46,-123.15"/>
+</g>
+<!-- TUPLEN->TUPLE_BOT -->
+<g id="edge31" class="edge">
+<title>TUPLEN->TUPLE_BOT</title>
+<path fill="none" stroke="black" d="M890.22,-179.72C865.26,-162.45 828.04,-136.71 801.84,-118.58"/>
+<polygon fill="black" stroke="black" points="803.85,-115.72 793.64,-112.91 799.87,-121.47 803.85,-115.72"/>
+</g>
+</g>
+</svg>
diff --git a/docs/chapter04/projnode.json b/docs/chapter04/projnode.json new file mode 100644 index 00000000..3d4d20cf --- /dev/null +++ b/docs/chapter04/projnode.json @@ -0,0 +1,14 @@ +{ + "ver": 1, + "comp": "chapter04/docs/projnode.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"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": 6, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}} + ], + "groups": [ + ] +} diff --git a/docs/chapter04/projnode.png b/docs/chapter04/projnode.png Binary files differnew file mode 100644 index 00000000..bf7493f2 --- /dev/null +++ b/docs/chapter04/projnode.png diff --git a/docs/chapter04/projnode.svg b/docs/chapter04/projnode.svg new file mode 100644 index 00000000..b1291cdb --- /dev/null +++ b/docs/chapter04/projnode.svg @@ -0,0 +1,74 @@ +<svg aria-label="Compiler graph" width="294" height="142" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 294 142" 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"/><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,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(24,68)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>$ctrl</tspan><tspan class="node-id"> #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="n6" data-id="6" transform="translate(144,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><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/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index e6cb84f8..487afee9 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.graph.GraphObserver; - import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -16,11 +15,6 @@ 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 @@ -30,12 +24,16 @@ 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; } // The Lexer. Thin wrapper over a byte[] buffer with a cursor. private final Lexer _lexer; /** - * Stack of lexical scopes, each scope is a symbol table that binds + * A 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. */ public ScopeNode _scope; @@ -49,18 +47,38 @@ public class Parser { }}; - public Parser(String source) { - _lexer = new Lexer(source); + public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); + _lexer = new Lexer(source); _scope = new ScopeNode(); - START = new StartNode(); + START = new StartNode(new Type[]{ Type.CONTROL, arg }); + START.peephole(); } + public Parser(String source) { + this(source, TypeInteger.BOT); + } + + @Override + public String toString() { return _lexer.toString(); } + String src() { return new String( _lexer._input ); } + // Debugging utility to find a Node by index + public static Node find(int nid) { return START.find(nid); } + + private Node ctrl() { return _scope.ctrl(); } + + private Node ctrl(Node n) { return _scope.ctrl(n); } + public ReturnNode parse() { + // 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(); + _scope.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); return ret; } @@ -105,6 +123,7 @@ public class Parser { /** * Parses a return statement; "return" already parsed. + * The $ctrl edge is killed. * * <pre> * 'return' expr ; @@ -113,7 +132,9 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseExpression(), ";"); - return new ReturnNode(START, expr).peephole(); + Node ret = new ReturnNode(ctrl(), expr).peephole(); + ctrl(null); // Kill control + return ret; } @@ -157,11 +178,30 @@ public class Parser { * Parse an expression of the form: * * <pre> - * expr : additiveExpr + * expr : compareExpr * </pre> * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { return parseAddition(); } + private Node parseExpression() { return parseComparison(); } + + /** + * Parse an expression of the form: + * + * <pre> + * expr : additiveExpr op additiveExpr + * </pre> + * @return an comparator expression {@link Node}, never {@code null} + */ + private Node parseComparison() { + var lhs = parseAddition(); + if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); + if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); + if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); + if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); + if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); + if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + return lhs; + } /** * Parse an additive expression diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 94aa4fbb..2fa4514e 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -17,14 +17,76 @@ public class AddNode extends Node { in(2)._type instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()+i1.value()); + return i0.meet(i1); } - return Type.BOTTOM; + return TypeInteger.BOT; } @Override public Node idealize () { - // TODO: add of 0, and many other peepholes added in Chaper04 + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Already handled by peephole constant folding + assert !(t1.isConstant() && t2.isConstant()); + + // Add of 0. We do not check for (0+x) because this will already + // canonicalize to (x+0) + if( t2 instanceof TypeInteger i && i.value()==0 ) + return lhs; + + // Add of same to a multiply by 2 + if( lhs==rhs ) + return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + + // Goal: a left-spine set of adds, with constants on the rhs (which then fold). + + // Move non-adds to RHS + if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) + return swap12(); + + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) + + // Do we have x + (y + z) ? + // Swap to (x + y) + z + // Rotate (add add add) to remove the add on RHS + if( rhs instanceof AddNode add ) + return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + + // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) + if( !(lhs instanceof AddNode) ) + return spine_cmp(lhs,rhs) ? swap12() : null; + + // Now we only see (add add non) + + // Do we have (x + con1) + con2? + // Replace with (x + (con1+con2) which then fold the constants + if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + + // Now we sort along the spine via rotates, to gather similar things together. + + // Do we rotate (x + y) + z + // into (x + z) + y ? + if( spine_cmp(lhs.in(2),rhs) ) + return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); + return null; } + // 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. + // 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 ; + + // Same category of "others" + return lo._nid > hi._nid; + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java new file mode 100644 index 00000000..4c79fa0b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -0,0 +1,48 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +abstract public class BoolNode extends Node { + + public BoolNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + abstract String op(); // String opcode name + + @Override + public String label() { return getClass().getSimpleName(); } + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.open().n(in(1)).p(op()).n(in(2)).close(); + } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); + return i0.meet(i1); + } + return TypeInteger.BOT; + } + + abstract boolean doOp(long lhs, long rhs); + + @Override + public Node idealize() { + // Compare of same + if( in(1)==in(2) ) + return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0)); + + 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; } } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index cc1db452..5efe29b7 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -41,5 +41,4 @@ public class ConstantNode extends Node { @Override public Node idealize() { return null; } - } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index d1a554bc..08dea003 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -19,10 +19,16 @@ public class DivNode extends Node { return i1.value() == 0 ? TypeInteger.ZERO : TypeInteger.constant(i0.value()/i1.value()); + return i0.meet(i1); } - return Type.BOTTOM; + return TypeInteger.BOT; } @Override - public Node idealize() { return null; } + public Node idealize() { + // Div of 1. + if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 ) + return in(1); + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 11769935..bb5f155d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -15,7 +15,7 @@ public class MinusNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0) return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return Type.BOTTOM; + return TypeInteger.BOT; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index abae6925..e866cf24 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -17,10 +17,27 @@ public class MulNode extends Node { in(2)._type instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()*i1.value()); + return i0.meet(i1); } - return Type.BOTTOM; + return TypeInteger.BOT; } @Override - public Node idealize() { return null; } + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java new file mode 100644 index 00000000..7ba1aa19 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -0,0 +1,7 @@ +package com.seaofnodes.simple.node; + +public abstract class MultiNode extends Node { + + public MultiNode(Node... inputs) { super(inputs); } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 54687b2e..bd72c8e4 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -3,10 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.BaseNode; import com.seaofnodes.simple.Parser; - import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; - import java.util.*; /** @@ -136,11 +134,11 @@ public abstract class Node extends BaseNode<Node> { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { Utils.del(_outputs, Utils.find(_outputs, use)); - return _outputs.size() == 0; + return _outputs.isEmpty(); } // Shortcut for "popping" n nodes. A "pop" is basically a - // set_def(last,null) followed by lowering the nIns() count. + // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { for( int i=0; i<n; i++ ) { Node old_def = _inputs.removeLast(); @@ -164,6 +162,15 @@ public abstract class Node extends BaseNode<Node> { // Mostly used for asserts and printing. public boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + + // Shortcuts to stop DCE mid-parse + // Add bogus null use to keep node alive + public <N extends Node> N keep() { addUse(null); return (N)this; } + // Remove bogus null. + public <N extends Node> N unkeep() { delUse(null); return (N)this; } + // ------------------------------------------------------------------------ + // Graph-based optimizations + /** * Try to peephole at this node and return a better replacement Node if * possible. We compute a {@link Type} and then check and replace: @@ -172,7 +179,11 @@ public abstract class Node extends BaseNode<Node> { * <li>in a future chapter we will look for a * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> * to eliminate.</li> - * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li> + * <li>we ask the Node for a better replacement. The "better replacement" + * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes + * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing + * math constants, remove algebraic identities and generally simplify the + * code. </li> * </ul> */ public final Node peephole() { @@ -190,19 +201,36 @@ public abstract class Node extends BaseNode<Node> { Type type = _type = compute(); // Replace constant computations from non-constants with a constant node - if (!(this instanceof ConstantNode) && type.isConstant()) { - kill(); // Kill `this` because replacing with a Constant - return new ConstantNode(type).peephole(); - } + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); // Future chapter: Global Value Numbering goes here // Ask each node for a better replacement Node n = idealize(); - if( n != null ) return n; + if( n != null ) // Something changed + // Recursively optimize + 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. + // 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.keep(); // Keep m alive + kill(); // Kill self because replacing with 'm' + m.unkeep(); // Okay to peephole m } + return m; + } /** * This function needs to be @@ -222,8 +250,64 @@ public abstract class Node extends BaseNode<Node> { */ public abstract Type compute(); + /** + * This function rewrites the current Node into a more "idealized" form. + * This is the bulk of our peephole rewrite rules, and we use this to + * e.g. turn arbitrary collections of adds and multiplies with mixed + * constants into a normal form that's easy for hardware to implement. + * Example: An array addressing expression: + * <pre> ary[idx+1]</pre> + * might turn into Sea-of-Nodes IR: + * <pre> (ary+12)+((idx+1) * 4)</pre> + * This expression can then be idealized into: + * <pre> ary + ((idx*4) + (12 + (1*4)))</pre> + * And more folding: + * <pre> ary + ((idx<<2) + 16)</pre> + * And during code-gen: + * <pre> MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre> + * <p> + * {@link #idealize} has a very specific calling convention: + * <ul> + * <li>If NO change is made, return {@code null} + * <li>If ANY change is made, return not-null; this can be {@code this} + * <li>The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it. + * <li>Any NEW nodes that are not directly returned DO call {@link #peephole}. + * </ul> + * <p> + * Examples: + * <table border="3"> + * <tr><th> before </th><th> after </th><th>return </th><th>comment </th></tr> + * <tr><td>{@code (x+5) }</td><td>{@code (x+5) }</td><td>{@code null }</td><td>No change</td></tr> + * <tr><td>{@code (5+x) }</td><td>{@code (x+5) }</td><td>{@code this }</td><td>Swapped arguments</td></tr> + * <tr><td>{@code ((x+1)+2)}</td><td>{@code (x+(1+2))}</td><td>{@code (x+_) }</td><td>Returns 2 new Nodes</td></tr> + * </table> + * + * The last entry deserves more discussion. The new Node {@code (1+2)} + * created in {@link #idealize} calls {@link #peephole} (which then folds + * into a constant). The other new Node {@code (x+3)} does not call + * peephole, because it is returned and peephole itself will recursively + * call peephole. + * <p> + * Since idealize calls peephole and peephole calls idealize, you must be + * careful that all idealizations are <em>monotonic</em>: all transforms remove + * some feature, so that the set of available transforms always shrinks. + * If you don't, you risk an infinite peephole loop! + * + * @return Either a new or changed node, or null for no changes. + */ public abstract Node idealize(); + // ------------------------------------------------------------------------ + // Peephole utilities + + // Swap inputs without letting either input go dead during the swap. + Node swap12() { + Node tmp = in(1); + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + /** * 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/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java new file mode 100644 index 00000000..a9781ce1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class NotNode extends Node { + public NotNode(Node in) { super(null, in); } + + @Override public String label() { return "Not"; } + + @Override protected String format() { return "(!%1)"; } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 ) + return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; + return TypeInteger.BOT; + } + + @Override + public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java new file mode 100644 index 00000000..063f9edc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeTuple; + +public class ProjNode extends Node { + + // Which slice of the incoming multi-part value + public final int _idx; + + // Debugging label + public final String _label; + + public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); + _idx = idx; + _label = label; + } + + @Override + public String label() { return _label; } + + @Override + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(_label); } + + @Override public boolean isCFG() { return _idx==0; } + + public MultiNode ctrl() { return (MultiNode)in(0); } + + @Override + public Type compute() { + Type t = ctrl()._type; + return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index b48682ca..c5dc532d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -34,7 +34,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return Type.BOTTOM; + return new TypeTuple(ctrl()._type,expr()._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 95c25391..6ffa8939 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -9,12 +9,18 @@ import java.util.*; /** * The Scope node is purely a parser helper - it tracks names to nodes with a * stack of scopes. - * @see <a href="file:../../../../../../../../chapter03/README.md">chapter03/README.md</a> */ public class ScopeNode extends Node { /** - * A Stack of symbol tables; a symbol table is a map from names to node indices. + * The control is a name that binds to the currently active control + * node in the graph + */ + public static final String CTRL = "$ctrl"; + public static final String ARG0 = "arg"; + + /** + * Names for every input edge */ public final Stack<HashMap<String, Integer>> _scopes; @@ -51,7 +57,7 @@ public class ScopeNode extends Node { * Recover the names for all variable bindings. * The result is an array of names that is aligned with the * inputs to the Node. - * <p> + * * This is an expensive operation. */ public String[] reverseNames() { @@ -80,21 +86,21 @@ public class ScopeNode extends Node { } /** * Lookup a name in all scopes starting from most deeply nested. - * <p> + * * @param name Name to be looked up * @see #update(String, Node, int) */ public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } /** * If the name is present in any scope, then redefine else null - * <p> + * * @param name Name being redefined * @param n The node to bind to the name */ public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } /** * Both recursive lookup and update. - * <p> + * * A shared implementation allows us to create lazy phis both during * lookups and updates; the lazy phi creation is part of chapter 8. * diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 12f35736..c9f53abd 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeTuple; /** * The Start node represents the start of the function. For now, we do not @@ -11,10 +12,14 @@ import com.seaofnodes.simple.type.Type; * will require Projections to extract the values. We discuss this in detail * in Chapter 9: Functions and Calls. */ -public class StartNode extends Node { +public class StartNode extends MultiNode { - public StartNode(/*arguments go here*/) { + final TypeTuple _args; + + public StartNode(Type[] args) { super(); + _args = new TypeTuple(args); + _type = _args; } @Override @@ -27,7 +32,7 @@ public class StartNode extends Node { @Override public boolean isCFG() { return true; } @Override - public Type compute() { return Type.BOTTOM; } + public TypeTuple compute() { return _args; } @Override public Node idealize() { return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 88106018..43e684a1 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -13,15 +13,41 @@ public class SubNode extends Node { @Override public Type compute() { + // Sub of same is 0 + if( in(1)==in(2) ) + return TypeInteger.ZERO; + if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); + return i0.meet(i1); } - return Type.BOTTOM; + return TypeInteger.BOT; } @Override - public Node idealize() { return null; } + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Keep invalid operands for type checking. + if( t1 instanceof TypeInteger x && t2 instanceof TypeInteger y ) { + if( y.isConstant() && y.value()==0 ) return lhs; + if( x.isConstant() && x.value()==0 ) return new MinusNode(rhs); + } + + // x - (-y) is x+y + if( rhs instanceof MinusNode minus ) + return new AddNode(lhs,minus.in(1)); + + // (-x) - y is -(x+y) + if( lhs instanceof MinusNode minus ) + return new MinusNode(new AddNode(minus.in(1),rhs).peephole()); + + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index c97aaf55..b68012dc 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,22 +5,18 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** Chapter 3's view of the IR; browser, transport and layout are shared. */ +/** Chapter 4's view of the IR; no knowledge of browser, transport or layout. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String[] edgeNames(Node n) { return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; } + @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : -1; } - @Override protected Kind kind(Node n) { - if( n instanceof ScopeNode ) return Kind.SCOPE; - if( n instanceof StartNode ) return Kind.CTRL; - return n.isCFG() ? Kind.CTRL : Kind.DATA; - } - + @Override protected Kind kind(Node n) { return n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA; } @Override protected Role role(Node n, int i) { - if( n instanceof ScopeNode || n instanceof ConstantNode ) return Role.ASSOC; - if( i == 0 ) return Role.CTRL; - return Role.DATA; + return n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC + : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA) + : i==0 ? Role.CTRL : 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 2dc5d844..d655ed4a 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,11 +7,10 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 3's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 4 needs only a parser; it has no worklist or distant dependencies. */ 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()); @@ -19,12 +18,11 @@ 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(_phase); + phase("Parse"); } - @Override protected String phase() { return _phase; } - @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } + @Override protected String phase() { return "Parse"; } + @Override protected int pos() { return _parser.pos(); } @Override protected void detach() { if( _parser != null ) _parser._obs = null; _parser = null; diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index b98ce6de..466fb739 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -24,22 +24,30 @@ public class Type { // type hierarchy are simple, not that the Type is conceptually simple. static final byte TBOT = 0; // Bottom (ALL) static final byte TTOP = 1; // Top (ANY) - static final byte TSIMPLE = 2; // End of the Simple Types - static final byte TINT = 3; // All Integers; see TypeInteger + static final byte TCTRL = 2; // Ctrl flow bottom + static final byte TSIMPLE = 3; // End of the Simple Types + static final byte TINT = 4; // All Integers; see TypeInteger + static final byte TTUPLE = 5; // Tuples; finite collections of unrelated Types, kept in parallel + public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"Bot","Top"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl"}; protected Type(byte type) { _type = type; } - public static final Type BOTTOM = new Type( TBOT ); // ALL + public static final Type BOTTOM = new Type( TBOT ); // ALL + public static final Type TOP = new Type( TTOP ); // ANY + public static final Type CONTROL = new Type( TCTRL ); // Ctrl public boolean isConstant() { return _type == TTOP; } @Override - public String toString() { - return print(new StringBuilder()).toString(); + 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/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index e0324da5..cbaff45f 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -5,37 +5,59 @@ package com.seaofnodes.simple.type; */ public class TypeInteger extends Type { - public final static TypeInteger ZERO= new TypeInteger(0); + public final static TypeInteger TOP = new TypeInteger(false, 0); + public final static TypeInteger BOT = new TypeInteger(false, 1); + public final static TypeInteger ZERO= new TypeInteger(true, 0); + + private final boolean _is_con; /** - * The constant value observed for this type + * The constant value or + * if not constant then 0=bottom, 1=top. */ private final long _con; - public TypeInteger(long con) { + public TypeInteger(boolean is_con, long con) { super(TINT); + _is_con = is_con; _con = con; } - public static TypeInteger constant(long con) { return new TypeInteger(con); } + public static TypeInteger constant(long con) { return new TypeInteger(true, con); } - @Override - public String toString() { - return print(new StringBuilder()).toString(); - } + public boolean isTop() { return !_is_con && _con==0; } + public boolean isBot() { return !_is_con && _con==1; } @Override - public StringBuilder print(StringBuilder sb) { return sb.append(_con); } + public StringBuilder print(StringBuilder sb) { + if (isTop()) return sb.append("IntTop"); + if (isBot()) return sb.append("IntBot"); + return sb.append(_con); + } @Override - public boolean isConstant() { return true; } + public boolean isConstant() { return _is_con; } public long value() { return _con; } @Override + public Type meet(Type other) { + if( this==other ) return this; + if (!(other instanceof TypeInteger i)) return super.meet(other); + // BOT wins + if ( isBot() ) return this; + if ( i.isBot() ) return i ; + // TOP loses + if ( i.isTop() ) return this; + if ( isTop() ) return i ; + assert isConstant() && i.isConstant(); + return _con==i._con ? this : TypeInteger.BOT; + } + + @Override public boolean equals( Object o ) { if( o==this ) return true; if( !(o instanceof TypeInteger i) ) return false; - return _con==i._con; + return _con==i._con && _is_con==i._is_con; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java new file mode 100644 index 00000000..52befa38 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.type; + +public class TypeTuple extends Type { + + public final Type[] _types; + + public TypeTuple(Type... _types) { + super(TTUPLE); + this._types = _types; + } + + @Override + public Type meet(Type other) { + throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); + } + + @Override + public StringBuilder print(StringBuilder sb) { + sb.append("[ "); + for( Type t : _types ) + t.print(sb).append(","); + sb.setLength(sb.length()-1); + sb.append("]"); + return sb; + } +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 311ca23b..3d568337 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -14,7 +14,7 @@ public class Chapter01Test { ReturnNode ret = parser.parse(); StartNode start = Parser.START; - assertEquals(start, ret.ctrl()); + assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 9a7dda5d..46b1ca33 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..195afbb7 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,161 @@ +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 Chapter04Test { + + @Test + public void testPeephole() { + Parser parser = new Parser("return 1+arg+2;"); + ReturnNode 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(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testAdd0() { + Parser parser = new Parser("return 0+arg;"); + ReturnNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testAddAddMul() { + Parser parser = new Parser("return arg+0+arg;"); + ReturnNode 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(); + assertEquals("return ((arg*2)+6);", ret.print()); + } + + @Test + public void testMul1() { + Parser parser = new Parser("return 1*arg;"); + ReturnNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testSub0() { + Parser parser = new Parser("return arg-0;"); + ReturnNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void test0Sub() { + Parser parser = new Parser("return 0-arg;"); + ReturnNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + + @Test + public void testSubNeg() { + Parser parser = new Parser("return 3--arg;"); + ReturnNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testNegSub() { + Parser parser = new Parser("return -arg-3;"); + ReturnNode 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(); + assertTrue(ret.in(0) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + } + + @Test + public void testConstantArg() { + Parser parser = new Parser("return arg;", TypeInteger.constant(2)); + ReturnNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testCompEq() { + Parser parser = new Parser("return 3==3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testCompEq2() { + Parser parser = new Parser("return 3==4;"); + ReturnNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq() { + Parser parser = new Parser("return 3!=3;"); + ReturnNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq2() { + Parser parser = new Parser("return 3!=4;"); + ReturnNode 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(); + 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(); + assertEquals("return (arg+1);", ret.print()); + } + + @Test + public void testBug3() { + try { + new Parser("inta=1; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'inta'",e.getMessage()); + } + } + + @Test + public void testBug4() { + Parser parser = new Parser("return -arg;"); + ReturnNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + + @Test + public void testBug5() { + Parser parser = new Parser("return arg--2;"); + ReturnNode ret = parser.parse(); + assertEquals("return (arg--2);", ret.print()); + } +} |
