From b9cc14c18586ad244e562648da7b361de3a19e3e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 20 Oct 2023 15:21:08 -0700 Subject: Chapter 4: External Argument and Comparisons MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Tamas Hadhazy Co-authored-by: Hels15 Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher --- Makefile | 106 ++++- README.md | 2 +- appendix/dce.md | 166 ++++++++ docs/chapter04/04-arg1.svg | 84 ++++ docs/chapter04/04-arg2.svg | 80 ++++ docs/chapter04/04-dce1.svg | 100 +++++ docs/chapter04/04-dce2.svg | 59 +++ docs/chapter04/04-dce3.svg | 116 ++++++ docs/chapter04/04-grammar.md | 72 ++++ docs/chapter04/04-post-peephole.gv | 43 ++ docs/chapter04/04-post-peephole.svg | 108 +++++ docs/chapter04/04-pre-peephole.gv | 47 +++ docs/chapter04/04-pre-peephole.svg | 134 +++++++ docs/chapter04/Makefile | 12 + docs/chapter04/README.md | 434 +++++++++++++++++++++ docs/chapter04/lattice.gv | 97 +++++ docs/chapter04/lattice.svg | 305 +++++++++++++++ docs/chapter04/projnode.png | Bin 0 -> 6061 bytes src/main/java/com/seaofnodes/simple/Parser.java | 66 +++- .../java/com/seaofnodes/simple/node/AddNode.java | 66 +++- .../java/com/seaofnodes/simple/node/BoolNode.java | 49 +++ .../com/seaofnodes/simple/node/ConstantNode.java | 3 +- .../java/com/seaofnodes/simple/node/DivNode.java | 10 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulNode.java | 21 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 7 + src/main/java/com/seaofnodes/simple/node/Node.java | 116 +++++- .../java/com/seaofnodes/simple/node/NotNode.java | 26 ++ .../java/com/seaofnodes/simple/node/ProjNode.java | 40 ++ .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 18 +- .../java/com/seaofnodes/simple/node/StartNode.java | 11 +- .../java/com/seaofnodes/simple/node/SubNode.java | 30 +- .../simple/print/SimpleGraphAdapter.java | 28 +- .../simple/print/SimpleGraphObserver.java | 10 +- src/main/java/com/seaofnodes/simple/type/Type.java | 20 +- .../com/seaofnodes/simple/type/TypeInteger.java | 44 ++- .../java/com/seaofnodes/simple/type/TypeTuple.java | 26 ++ .../java/com/seaofnodes/simple/Chapter01Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 1 + .../java/com/seaofnodes/simple/Chapter04Test.java | 161 ++++++++ 41 files changed, 2628 insertions(+), 96 deletions(-) create mode 100644 appendix/dce.md create mode 100644 docs/chapter04/04-arg1.svg create mode 100644 docs/chapter04/04-arg2.svg create mode 100644 docs/chapter04/04-dce1.svg create mode 100644 docs/chapter04/04-dce2.svg create mode 100644 docs/chapter04/04-dce3.svg create mode 100644 docs/chapter04/04-grammar.md create mode 100644 docs/chapter04/04-post-peephole.gv create mode 100644 docs/chapter04/04-post-peephole.svg create mode 100644 docs/chapter04/04-pre-peephole.gv create mode 100644 docs/chapter04/04-pre-peephole.svg create mode 100644 docs/chapter04/Makefile create mode 100644 docs/chapter04/README.md create mode 100644 docs/chapter04/lattice.gv create mode 100644 docs/chapter04/lattice.svg create mode 100644 docs/chapter04/projnode.png create mode 100644 src/main/java/com/seaofnodes/simple/node/BoolNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MultiNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/NotNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ProjNode.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeTuple.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter04Test.java diff --git a/Makefile b/Makefile index 67307a26..060e0cfd 100644 --- a/Makefile +++ b/Makefile @@ -1 +1,105 @@ -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)) +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) + @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)) diff --git a/README.md b/README.md index 7966f04b..c11da0ff 100644 --- a/README.md +++ b/README.md @@ -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..ad5be2d0 --- /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 idealize call). + +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): + +![Graph2](../docs/04-dce1.svg) + +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. + +*A constant node pointing to "Start"(ignored by the graph visualizer) but still maintains a connection:* + +![Graph3](../docs/04-dce2.svg) + +## 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: +![Graph3](../docs/04-dce3.svg) + +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.svg b/docs/chapter04/04-arg1.svg new file mode 100644 index 00000000..cf4599c5 --- /dev/null +++ b/docs/chapter04/04-arg1.svg @@ -0,0 +1,84 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + + +Start + + + +$ctrl + + + +Con_5 + +2 + + + +Return6 + +Return + + + +Return6->Start2:p0 + + +0 + + + +Return6->Con_5 + + +1 + + + +Scope1_0 + + +0 + +$ctrl + +arg + + + +Scope1_0:Scope1_0_arg->Con_5 + + + + + +Scope1_1 + + +1 + + + \ No newline at end of file diff --git a/docs/chapter04/04-arg2.svg b/docs/chapter04/04-arg2.svg new file mode 100644 index 00000000..2b3b47a3 --- /dev/null +++ b/docs/chapter04/04-arg2.svg @@ -0,0 +1,80 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Return5 + +Return + + + +Return5->Start2:p0 + + +0 + + + +Return5->Start2:p1 + + +1 + + + +Scope1_0 + + +0 + +$ctrl + +arg + + + +Scope1_0:Scope1_0_arg->Start2:p1 + + + + + +Scope1_1 + + +1 + + + \ No newline at end of file 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 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Con_5 + +12 + + + +Con_6 + +1 + + + +Return7 + +Return + + + +Return7->Start2:p0 + + +0 + + + +Return7->Con_6 + + +1 + + + +Scope1_0 + + +0 + +$ctrl + +arg + + + +Scope1_0:Scope1_0_arg->Start2:p1 + + + + + +Scope1_1 + + +1 + +a + + + +Scope1_1:Scope1_1_a->Con_5 + + + + + \ 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 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Con_6 + +1 + + + +Con_6->Start2 + + +0 + + + +Return7 + +Return + + + +Return7->Start2:p0 + + +0 + + + +Return7->Con_6 + + +1 + + + \ 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 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Con_5 + +2 + + + +Con_6 + +1 + + + +Add7 + ++ + + + +Add7->Con_5 + + +1 + + + +Add7->Con_6 + + +2 + + + +Con_8 + +3 + + + +Con_9 + +3 + + + +Add10 + ++ + + + +Add10->Con_8 + + +1 + + + +Add10->Con_9 + + +2 + + + +Con_11 + +6 + + + +Return12 + +Return + + + +Return12->Start2:p0 + + +0 + + + +Return12->Con_11 + + +1 + + + \ 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=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + 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=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1
>]; + } + } + 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.svg b/docs/chapter04/04-post-peephole.svg new file mode 100644 index 00000000..550c16ef --- /dev/null +++ b/docs/chapter04/04-post-peephole.svg @@ -0,0 +1,108 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Con_10 + +#3 + + + +Add11 + ++ + + + +Add11->Start2:p1 + + +1 + + + +Add11->Con_10 + + +2 + + + +Return12 + +Return + + + +Return12->Start2:p0 + + +0 + + + +Return12->Add11 + + +1 + + + +Scope1_0 + + +0 + +$ctrl + +arg + + + +Scope1_0:Scope1_0_arg->Start2:p1 + + + + + +Scope1_1 + + +1 + + + 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=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + 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=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1
>]; + } + } + 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.svg b/docs/chapter04/04-pre-peephole.svg new file mode 100644 index 00000000..9ec38d27 --- /dev/null +++ b/docs/chapter04/04-pre-peephole.svg @@ -0,0 +1,134 @@ + + + + + + +chapter04 + + +cluster_Nodes + + + +cluster_Scope1_0 + + + +cluster_Scope1_1 + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Con_5 + +#1 + + + +Con_6 + +#2 + + + +Add7 + ++ + + + +Add7->Start2:p1 + + +1 + + + +Add7->Con_6 + + +2 + + + +Add8 + ++ + + + +Add8->Con_5 + + +1 + + + +Add8->Add7 + + +2 + + + +Return9 + +Return + + + +Return9->Start2:p0 + + +0 + + + +Return9->Add8 + + +1 + + + +Scope1_0 + + +0 + +$ctrl + +arg + + + +Scope1_0:Scope1_0_arg->Start2:p1 + + + + + +Scope1_1 + + +1 + + + diff --git a/docs/chapter04/Makefile b/docs/chapter04/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter04/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter04/README.md b/docs/chapter04/README.md new file mode 100644 index 00000000..7891431e --- /dev/null +++ b/docs/chapter04/README.md @@ -0,0 +1,434 @@ +# Chapter 4: External Argument and Comparisons + +# Table of Contents + +1. [Extensions to Intermediate Representation](#extensions-to-intermediate-representation) +2. [Projection Nodes](#projection-nodes) +3. [Visualisation](#visualisation) +5. [Initial values](#initial-values) +6. [When Is Control Not-Null?](#when-is-control-not-null) +5. [Note Regarding Visualizations](#note-regarding-visualizations) +6. [Changes to Type System](#changes-to-type-system) +7. [Tuple Types](#tuple-types) +8. [$ctrl name binding](#ctrl-name-binding) +9. [More Peephole Optimizations](#more-peephole-optimizations) +10. [Peephole Walkthrough](#peephole-walkthrough) +11. [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 following features: + +* The program receives a single argument named `arg` of integer type from 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()`. + +Below is our list of Nodes from [Chapter 3](../chapter03/README.md): + +| Node Name | Type | Description | Inputs | Value | +|-----------|--------------|------------------------------------|------------------------------------------------------------------|------------------------------| +| Return | Control | End of function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | +| Add | Data | Add two values | Two data nodes, values are added, order not important | Result of the add operation | +| Sub | Data | Subtract a value from another | Two data nodes, values are subtracted, order matters | Result of the subtract | +| Mul | Data | Multiply two values | Two data nodes, values are multiplied, order not important | Result of the multiply | +| Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | +| Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | +| Scope | Symbol Table | Represents scopes in the graph | All nodes that define variables | None | + +## 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 + +![ProjNode](./projnode.png) + +In the visual above, the projection nodes have been tagged by the names +associated with the outputs of the Start node. Both MultiNode 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: + +![ProjNode](./04-arg1.svg) + +- `$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: + +![ArgNode](./04-arg2.svg) + + +#### 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 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 convenient to deal with a Types' 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: + +![Lattice](./lattice.svg) + + +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 a `IntBot` integer type. +When we start optimizing loops, we will start seeing `IntTop` values. + + +### Tuple Types + +Tuple types need a little more explaination: 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 a 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. + +This introduces the idea that the control flow subgraph is a Petri net model.[^1] +The control token moves virtually from node to node as execution proceeds. The +initial control token is in Start, it then moves via the Proj node to Return. +In later chapters we will see how the token moves across branches. + + +## 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: + +![Graph1](./04-pre-peephole.svg) + +We need to perform some algebraic simplifications to enable 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. + +![Graph1](./04-post-peephole.svg) + +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 | Multiple of 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 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 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. + +[^1]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 131. 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=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + CTRL [label="ctrl", fillcolor=yellow, shape=oval]; + + TOP -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥: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=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
tuple
type
...
type
+ >]; + + + 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 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +CTRL + +ctrl + + + +TOP->CTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL->BOT + + + + + +INT_MIN + +-n + + + +INT_TOP->INT_MIN + + + + + +INT_MINDOTS + +... + + + +INT_TOP->INT_MINDOTS + + + + + +INT_MINUS + +-1 + + + +INT_TOP->INT_MINUS + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_PLUS + +1 + + + +INT_TOP->INT_PLUS + + + + + +INT_MAXDOTS + +... + + + +INT_TOP->INT_MAXDOTS + + + + + +INT_MAX + ++n + + + +INT_TOP->INT_MAX + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +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 + + + + + +TUPLE1 + + + +tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/docs/chapter04/projnode.png b/docs/chapter04/projnode.png new file mode 100644 index 00000000..bf7493f2 Binary files /dev/null and b/docs/chapter04/projnode.png differ 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 _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 _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. * * 
      *     '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:
      *
      * 
-     *     expr : additiveExpr
+     *     expr : compareExpr
      * 

      * @return an expression {@link Node}, never {@code null}
      */
-    private Node parseExpression() { return parseAddition(); }
+    private Node parseExpression() { return parseComparison(); }
+
+    /**
+     * Parse an expression of the form:
+     *
+     * 
+     *     expr : additiveExpr op additiveExpr
+     * 

+     * @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 814b99b8..0291a900 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -21,14 +21,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..143a6fde
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -0,0 +1,49 @@
+package com.seaofnodes.simple.node;
+
+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
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("("));
+        in(2)._print0(sb.append(op()));
+        return sb.append(")");
+    }
+
+    @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 43a22426..85277d82 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -23,7 +23,7 @@ public class ConstantNode extends Node {
     }
 
     @Override
-    public String label() { return "#"+_con; }
+    public String label() { return ""+_con; }
 
     @Override
     public String uniqueName() { return "Con_" + _nid; }
@@ -38,5 +38,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 fc893e27..bffa4b44 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -23,10 +23,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 b83c41a5..ad6e513a 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -18,7 +18,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 b2b2f9c0..60103b8b 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -21,10 +21,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 3fa0fd1e..fdde869b 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,10 +1,8 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Parser;
-
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
-
 import java.util.*;
 
 /**
@@ -79,14 +77,7 @@ public abstract class Node {
     // line (because this is what a debugger typically displays by default) and
     // has to be robust with broken graph/nodes.
     @Override
-    public final String toString() {
-        // TODO: The print evolves in later chapters.  For now, a simple
-        // recursive print does well.  Later with control flow and later still
-        // with loops, we need some serious algorithm work to get a decent
-        // print.  So you should consider the "print" to always be a work-in-
-        // progress as we march through the chapters.
-        return print();
-    }
+    public final String toString() {  return print(); }
 
     // This is a *deep* print.  This version will fail on cycles, which we will
     // correct later when we can parse programs with loops.  We print with a
@@ -123,8 +114,6 @@ public abstract class Node {
 
     public boolean isCFG() { return false; }
 
-
-
     /**
      * Change a def into a Node.  Keeps the edges correct, by removing
      * the corresponding use->def edge.  This may make the original
@@ -182,11 +171,11 @@ public abstract class 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 keep() { addUse(null); return (N)this; }
+    // Remove bogus null.
+    public  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:
@@ -218,7 +216,11 @@ public abstract class Node {
      * 
  • in a future chapter we will look for a
      * Common Subexpression
      * to eliminate.
    • 
-     * 
  • we ask the Node for a better replacement (again, none enabled in this chapter)
    • 
+     * 
  • 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. 
    • 
      * 
      */
     public final Node peephole() {
@@ -236,19 +238,36 @@ public abstract class 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
@@ -268,8 +287,65 @@ public abstract class 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:
+     * 
       ary[idx+1]
    
+     * might turn into Sea-of-Nodes IR:
+     * 
       (ary+12)+((idx+1) * 4)
    
+     * This expression can then be idealized into:
+     * 
       ary + ((idx*4) + (12 + (1*4)))
    
+     * And more folding:
+     * 
       ary + ((idx<<2) + 16)
    
+     * And during code-gen:
+     * 
       MOV4 Rary,Ridx,16 // or some such hardware-specific notation 
    
+     * 
    
+     * {@link #idealize} has a very specific calling convention:
+     * 
      
+     * 
    • If NO change is made, return {@code null}
+     * 
    • If ANY change is made, return not-null; this can be {@code this}
+     * 
    • The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it.
+     * 
    • Any NEW nodes that are not directly returned DO call {@link #peephole}.
+     * 
    
+     * 
    
+     * Examples:
+     * 
+     * 
+     * 
+     * 
+     * 
+     * 
        before              after     return comment  
    {@code (x+5)    }{@code   (x+5)  }{@code null  }No change
    {@code (5+x)    }{@code   (x+5)  }{@code this  }Swapped arguments
    {@code ((x+1)+2)}{@code (x+(1+2))}{@code (x+_) }Returns 2 new Nodes
    
+     *
+     * 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.
+     * 
    
+     * Since idealize calls peephole and peephole calls idealize, you must be
+     * careful that all idealizations are monotonic: 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..6a56ff64
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -0,0 +1,26 @@
+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
+    StringBuilder _print1(StringBuilder sb) {
+        in(1)._print0(sb.append("(!"));
+        return sb.append(")");
+    }
+
+    @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..2f49fe91
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -0,0 +1,40 @@
+package com.seaofnodes.simple.node;
+
+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
+    StringBuilder _print1(StringBuilder sb) { return sb.append(_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 7fa470f8..c9d6c9c8 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -32,7 +32,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 379ef033..8ffeac64 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -7,12 +7,18 @@ import java.util.*;
 /**
  * The Scope node is purely a parser helper - it tracks names to nodes with a
  * stack of scopes.
- * @see chapter03/README.md
  */
 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> _scopes;
 
@@ -49,7 +55,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.
-     * 
    
+     *
      * This is an expensive operation.
      */
     public String[] reverseNames() {
@@ -78,21 +84,21 @@ public class ScopeNode extends Node {
     }
     /**
      * Lookup a name in all scopes starting from most deeply nested.
-     * 
    
+     *
      * @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
-     * 
    
+     *
      * @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.
-     * 
    
+     *
      * 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 99e240ad..022e276d 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 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
@@ -9,10 +10,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
@@ -26,7 +31,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 1d2ddaa0..c831a798 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -17,15 +17,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 a615741d..a0ad7be0 100644
--- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
+++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.node.Node;
 import java.util.ArrayList;
 
-/** 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 {
     @Override protected boolean dead(Node n) { return n.isDead(); }
     @Override protected int id(Node n) { return n._nid; }
@@ -17,31 +17,23 @@ public class SimpleGraphAdapter extends GraphAdapter {
     @Override protected Node out(Node n, int idx) { return n.out(idx); }
 
     private ArrayList edges(Node n) {
-        var edges = new ArrayList();
         String[] names = n instanceof ScopeNode scope && n.nIns() != 0 ? scope.reverseNames() : null;
+        var edges = new ArrayList();
         for( int i = 0; i < n.nIns(); i++ ) {
-            String name = names == null || i >= names.length ? null : names[i];
-            edges.add(new Edge(i, ref(n.in(i)), role(n, i), name));
+            Role role = n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC
+                : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA)
+                : i == 0 ? Role.CTRL : Role.DATA;
+            edges.add(new Edge(i, ref(n.in(i)), role, names == null ? null : names[i]));
         }
         return edges;
     }
 
     @Override protected GraphSnapshot.Node desc(Node n) {
-        Projection proj = null;
+        Projection proj = n instanceof ProjNode p
+            ? new Projection(n.nIns() == 0 ? 0 : ref(n.in(0)), p._idx) : null;
+        Kind kind = n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA;
         String label = n.label();
         return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label,
-                                      n._type == null ? null : n._type.toString(), kind(n), edges(n), proj);
-    }
-
-    private 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;
-    }
-
-    private 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;
+                                      n._type == null ? null : n._type.toString(), kind, edges(n), proj);
     }
 }
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 {
     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 {
     @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 7ea17bfb..1e50bdda 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -24,17 +24,29 @@ 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; }
 
     public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+
+    public Type meet(Type other) { return Type.BOTTOM; }
+
+    @Override
+    public final String toString() {
+        return print(new StringBuilder()).toString();
+    }
 }
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());
+    }
+}
-- 
cgit v1.2.3