From b50645a6b0ecdd9b41f947c172795c41d952874b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 11 Nov 2023 23:17:22 +0000 Subject: Chapter 6: Peepholes for If MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Yichen Yan Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Tamas Hadhazy Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher --- Makefile | 101 ++++- README.md | 2 +- docs/chapter06/06-grammar.md | 79 ++++ docs/chapter06/06-graph1-post.gv | 29 ++ docs/chapter06/06-graph1-post.json | 16 + docs/chapter06/06-graph1-post.svg | 80 ++++ docs/chapter06/06-graph1-pre.gv | 52 +++ docs/chapter06/06-graph1-pre.json | 24 ++ docs/chapter06/06-graph1-pre.svg | 111 +++++ docs/chapter06/06-graph2-post.gv | 33 ++ docs/chapter06/06-graph2-post.json | 16 + docs/chapter06/06-graph2-post.svg | 80 ++++ docs/chapter06/06-graph2-pre.gv | 55 +++ docs/chapter06/06-graph2-pre.json | 24 ++ docs/chapter06/06-graph2-pre.svg | 108 +++++ docs/chapter06/06-graph3-false.gv | 35 ++ docs/chapter06/06-graph3-false.svg | 67 +++ docs/chapter06/06-graph3-nonconst-peephole.gv | 56 +++ docs/chapter06/06-graph3-nonconst-peephole.json | 24 ++ docs/chapter06/06-graph3-nonconst-peephole.svg | 109 +++++ docs/chapter06/06-graph3-nonconst.gv | 86 ++++ docs/chapter06/06-graph3-nonconst.json | 35 ++ docs/chapter06/06-graph3-nonconst.svg | 150 +++++++ docs/chapter06/06-graph3-true.gv | 35 ++ docs/chapter06/06-graph3-true.svg | 67 +++ docs/chapter06/06-graph4-arg2.gv | 37 ++ docs/chapter06/06-graph4-arg2.svg | 67 +++ docs/chapter06/06-graph4-nonconst.gv | 122 ++++++ docs/chapter06/06-graph4-nonconst.svg | 456 +++++++++++++++++++++ docs/chapter06/06-graph4-true.gv | 37 ++ docs/chapter06/06-graph4-true.svg | 67 +++ docs/chapter06/Makefile | 1 + docs/chapter06/README.md | 203 +++++++++ docs/chapter06/lattice.gv | 97 +++++ docs/chapter06/lattice.svg | 319 ++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 3 +- .../java/com/seaofnodes/simple/node/AddNode.java | 67 ++- .../java/com/seaofnodes/simple/node/BoolNode.java | 7 + .../java/com/seaofnodes/simple/node/IfNode.java | 20 +- .../java/com/seaofnodes/simple/node/MulNode.java | 6 + src/main/java/com/seaofnodes/simple/node/Node.java | 47 ++- .../java/com/seaofnodes/simple/node/PhiNode.java | 27 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 2 + .../com/seaofnodes/simple/node/RegionNode.java | 49 ++- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 6 + .../java/com/seaofnodes/simple/node/StopNode.java | 5 + .../simple/print/SimpleGraphAdapter.java | 2 +- .../simple/print/SimpleGraphObserver.java | 2 +- src/main/java/com/seaofnodes/simple/type/Type.java | 37 +- .../com/seaofnodes/simple/type/TypeInteger.java | 2 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 8 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 294 +++++++++++++ 54 files changed, 3426 insertions(+), 48 deletions(-) create mode 100644 docs/chapter06/06-grammar.md create mode 100644 docs/chapter06/06-graph1-post.gv create mode 100644 docs/chapter06/06-graph1-post.json create mode 100644 docs/chapter06/06-graph1-post.svg create mode 100644 docs/chapter06/06-graph1-pre.gv create mode 100644 docs/chapter06/06-graph1-pre.json create mode 100644 docs/chapter06/06-graph1-pre.svg create mode 100644 docs/chapter06/06-graph2-post.gv create mode 100644 docs/chapter06/06-graph2-post.json create mode 100644 docs/chapter06/06-graph2-post.svg create mode 100644 docs/chapter06/06-graph2-pre.gv create mode 100644 docs/chapter06/06-graph2-pre.json create mode 100644 docs/chapter06/06-graph2-pre.svg create mode 100644 docs/chapter06/06-graph3-false.gv create mode 100644 docs/chapter06/06-graph3-false.svg create mode 100644 docs/chapter06/06-graph3-nonconst-peephole.gv create mode 100644 docs/chapter06/06-graph3-nonconst-peephole.json create mode 100644 docs/chapter06/06-graph3-nonconst-peephole.svg create mode 100644 docs/chapter06/06-graph3-nonconst.gv create mode 100644 docs/chapter06/06-graph3-nonconst.json create mode 100644 docs/chapter06/06-graph3-nonconst.svg create mode 100644 docs/chapter06/06-graph3-true.gv create mode 100644 docs/chapter06/06-graph3-true.svg create mode 100644 docs/chapter06/06-graph4-arg2.gv create mode 100644 docs/chapter06/06-graph4-arg2.svg create mode 100644 docs/chapter06/06-graph4-nonconst.gv create mode 100644 docs/chapter06/06-graph4-nonconst.svg create mode 100644 docs/chapter06/06-graph4-true.gv create mode 100644 docs/chapter06/06-graph4-true.svg create mode 100644 docs/chapter06/Makefile create mode 100644 docs/chapter06/README.md create mode 100644 docs/chapter06/lattice.gv create mode 100644 docs/chapter06/lattice.svg create mode 100644 src/test/java/com/seaofnodes/simple/Chapter06Test.java diff --git a/Makefile b/Makefile index 67307a26..9afabcaf 100644 --- a/Makefile +++ b/Makefile @@ -1 +1,100 @@ -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.%,$(test_javas)) +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) + +# Compile just the out-of-date files +$(main_classes): build/classes/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) + $(JVM) org.junit.runner.JUnitCore $(test_cp) + +.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)) + +.PHONY: build +build: $(main_classes) diff --git a/README.md b/README.md index fec20e09..78899ccb 100644 --- a/README.md +++ b/README.md @@ -47,7 +47,7 @@ The Simple language is styled after a subset of C or Java. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. * [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. -* Chapter 6: Peephole optimization around dead control flow. +* [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow. * Chapter 7: `while` statement; looping constructs - eager phi approach. * Chapter 8: Looping constructs continued, lazy phi creation, `break` and `continue` statements. * Chapter 9: Global Value Numbering. Iterative peepholes to fixpoint. Worklists. diff --git a/docs/chapter06/06-grammar.md b/docs/chapter06/06-grammar.md new file mode 100644 index 00000000..9ed7b160 --- /dev/null +++ b/docs/chapter06/06-grammar.md @@ -0,0 +1,79 @@ +# Grammar for Chapter 6 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter06/06-graph1-post.gv b/docs/chapter06/06-graph1-post.gv new file mode 100644 index 00000000..31480991 --- /dev/null +++ b/docs/chapter06/06-graph1-post.gv @@ -0,0 +1,29 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_12 [ label="#2" ]; + Return13 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return13[taillabel=0 color=red]; + Return13 -> Start2:p0[taillabel=0 color=red]; + Return13 -> Con_12[taillabel=1]; +} diff --git a/docs/chapter06/06-graph1-post.json b/docs/chapter06/06-graph1-post.json new file mode 100644 index 00000000..325d473a --- /dev/null +++ b/docs/chapter06/06-graph1-post.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph1-post.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": null}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph1-post.svg b/docs/chapter06/06-graph1-post.svg new file mode 100644 index 00000000..7c58b6c3 --- /dev/null +++ b/docs/chapter06/06-graph1-post.svg @@ -0,0 +1,80 @@ +#3[0] → #13 · CTRL#13[0] → #1 · CTRL#13[1] → #12 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #13 CTRL0#2  #12#12 #2 +Type not computed + +Return  #13#13 Return +Type not computed + +[0] → #1 CTRL +[1] → #12 DATA01 diff --git a/docs/chapter06/06-graph1-pre.gv b/docs/chapter06/06-graph1-pre.gv new file mode 100644 index 00000000..2bfdd23d --- /dev/null +++ b/docs/chapter06/06-graph1-pre.gv @@ -0,0 +1,52 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#1" ]; + If7 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_11 [ label="#2" ]; + Return12 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_13 [ label="#~CONTROL" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Con_15 [ label="#1" ]; + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region14;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return12[taillabel=0 color=red]; + Stop3 -> Return16[taillabel=1 color=red]; + If7 -> Start2:p0[taillabel=0 color=red]; + If7 -> Con_6[taillabel=1]; + Return12 -> If7:p0[taillabel=0 color=red]; + Return12 -> Con_11[taillabel=1]; + Region14 -> Con_13[taillabel=1]; + Region14 -> If7:p1[taillabel=2 color=red]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Con_15[taillabel=1]; +} diff --git a/docs/chapter06/06-graph1-pre.json b/docs/chapter06/06-graph1-pre.json new file mode 100644 index 00000000..18615f2c --- /dev/null +++ b/docs/chapter06/06-graph1-pre.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph1-pre.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 16, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}], "proj": {"par": 7, "idx": 0}}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}], "proj": {"par": 7, "idx": 1}}, + {"id": 6, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "#~CONTROL", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 15, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph1-pre.svg b/docs/chapter06/06-graph1-pre.svg new file mode 100644 index 00000000..693ddba6 --- /dev/null +++ b/docs/chapter06/06-graph1-pre.svg @@ -0,0 +1,111 @@ +#3[0] → #12 · CTRL#3[1] → #16 · CTRL#7[0] → #1 · CTRL#7[1] → #6 · DATA#12[0] → #4 · CTRL#12[1] → #11 · DATA#14[1] → #13 · DATA#14[2] → #5 · CTRL#16[0] → #14 · CTRL#16[1] → #15 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #12 CTRL +[1] → #16 CTRL01True  #4/0#4 True +Projection 0 of #7 +Type not computed + +[0] → #7 CTRLFalse  #5/1#5 False +Projection 1 of #7 +Type not computed + +[0] → #7 CTRL#1  #6#6 #1 +Type not computed + +If  #7#7 If +Type not computed + +[0] → #1 CTRL +[1] → #6 DATA01#2  #11#11 #2 +Type not computed + +Return  #12#12 Return +Type not computed + +[0] → #4 CTRL +[1] → #11 DATA01#~CONTROL  #13#13 #~CONTROL +Type not computed + +Region  #14#14 Region +Type not computed + +[0] → — DATA +[1] → #13 DATA +[2] → #5 CTRL012#1  #15#15 #1 +Type not computed + +Return  #16#16 Return +Type not computed + +[0] → #14 CTRL +[1] → #15 DATA01 diff --git a/docs/chapter06/06-graph2-post.gv b/docs/chapter06/06-graph2-post.gv new file mode 100644 index 00000000..61ae2ca1 --- /dev/null +++ b/docs/chapter06/06-graph2-post.gv @@ -0,0 +1,33 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_13 [ label="#2" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return17 -> Start2:p0[taillabel=0 color=red]; + Return17 -> Con_13[taillabel=1]; + Stop3 -> Return17[taillabel=0 color=red]; +} diff --git a/docs/chapter06/06-graph2-post.json b/docs/chapter06/06-graph2-post.json new file mode 100644 index 00000000..31be64c2 --- /dev/null +++ b/docs/chapter06/06-graph2-post.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph2-post.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": null}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph2-post.svg b/docs/chapter06/06-graph2-post.svg new file mode 100644 index 00000000..a87af3ec --- /dev/null +++ b/docs/chapter06/06-graph2-post.svg @@ -0,0 +1,80 @@ +#3[0] → #17 · CTRL#17[0] → #1 · CTRL#17[1] → #13 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #17 CTRL0#2  #13#13 #2 +Type not computed + +Return  #17#17 Return +Type not computed + +[0] → #1 CTRL +[1] → #13 DATA01 diff --git a/docs/chapter06/06-graph2-pre.gv b/docs/chapter06/06-graph2-pre.gv new file mode 100644 index 00000000..d183b4c4 --- /dev/null +++ b/docs/chapter06/06-graph2-pre.gv @@ -0,0 +1,55 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="#1" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_12 [ label="#2" ]; + Con_13 [ label="#3" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a15 [ style=filled fillcolor=lightyellow label="φ_a" ]; + { rank=same; Region14;Phi_a15;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Phi_a15[taillabel=1]; + Stop3 -> Return16[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Con_7[taillabel=1]; + Region14 -> If8:p0[taillabel=1 color=red]; + Region14 -> If8:p1[taillabel=2 color=red]; + Phi_a15 -> Region14 [style=dotted taillabel=0]; + Phi_a15 -> Con_12[taillabel=1]; + Phi_a15 -> Con_13[taillabel=2]; +} diff --git a/docs/chapter06/06-graph2-pre.json b/docs/chapter06/06-graph2-pre.json new file mode 100644 index 00000000..fd187946 --- /dev/null +++ b/docs/chapter06/06-graph2-pre.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph2-pre.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "CTRL", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 15, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 14, "role": "ASSOC", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [4, 5, 8, 14, 15]} + ] +} diff --git a/docs/chapter06/06-graph2-pre.svg b/docs/chapter06/06-graph2-pre.svg new file mode 100644 index 00000000..f787b4dc --- /dev/null +++ b/docs/chapter06/06-graph2-pre.svg @@ -0,0 +1,108 @@ +#3[0] → #16 · CTRL#8[0] → #1 · CTRL#8[1] → #7 · DATA#14[1] → #4 · CTRL#14[2] → #5 · CTRL#15[1] → #12 · DATA#15[2] → #13 · DATA#16[0] → #14 · CTRL#16[1] → #15 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #16 CTRL0True  #4/0#4 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRLFalse  #5/1#5 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRL#1  #7#7 #1 +Type not computed + +If  #8#8 If +Type not computed + +[0] → #1 CTRL +[1] → #7 DATA01#2  #12#12 #2 +Type not computed + +#3  #13#13 #3 +Type not computed + +Region  #14#14 Region +Type not computed + +[0] → — DATA +[1] → #4 CTRL +[2] → #5 CTRL012φ_a  #15#15 φ_a +Type not computed + +[0] → #14 ASSOC +[1] → #12 DATA +[2] → #13 DATA[0] → #14012Return  #16#16 Return +Type not computed + +[0] → #14 CTRL +[1] → #15 DATA01If  #8If · 5 nodes−Fold region diff --git a/docs/chapter06/06-graph3-false.gv b/docs/chapter06/06-graph3-false.gv new file mode 100644 index 00000000..28f741fa --- /dev/null +++ b/docs/chapter06/06-graph3-false.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_30 [ label="#1" ]; + Return31 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return31[taillabel=0 color=red]; + Return31 -> Start2:p0[taillabel=0 color=red]; + Return31 -> Con_30[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-false.svg b/docs/chapter06/06-graph3-false.svg new file mode 100644 index 00000000..49b04f09 --- /dev/null +++ b/docs/chapter06/06-graph3-false.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return31 + +Return + + + +Stop3->Return31 + + +0 + + + +Con_30 + +#1 + + + +Return31->Start2:p0 + + +0 + + + +Return31->Con_30 + + +1 + + + diff --git a/docs/chapter06/06-graph3-nonconst-peephole.gv b/docs/chapter06/06-graph3-nonconst-peephole.gv new file mode 100644 index 00000000..f8e3e5fa --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.gv @@ -0,0 +1,56 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_27 [ label="#4" ]; + Con_29 [ label="#1" ]; + Phi_ab30 [ style=filled fillcolor=lightyellow label="φ_ab" ]; + Return31 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region22;Phi_ab30;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return31[taillabel=0 color=red]; + Region22 -> If8:p0[taillabel=1 color=red]; + Region22 -> If8:p1[taillabel=2 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Start2:p1[taillabel=1]; + Phi_ab30 -> Region22 [style=dotted taillabel=0]; + Phi_ab30 -> Con_27[taillabel=1]; + Phi_ab30 -> Con_29[taillabel=2]; + Return31 -> Region22[taillabel=0 color=red]; + Return31 -> Phi_ab30[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-nonconst-peephole.json b/docs/chapter06/06-graph3-nonconst-peephole.json new file mode 100644 index 00000000..7f1f183c --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph3-nonconst-peephole.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 31, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 6, "role": "CTRL", "label": null}], "proj": null}, + {"id": 27, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 29, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 30, "label": "φ_ab", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 22, "role": "ASSOC", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}, {"idx": 2, "def": 29, "role": "DATA", "label": null}], "proj": null}, + {"id": 31, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 22, "role": "CTRL", "label": null}, {"idx": 1, "def": 30, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [5, 6, 8, 22, 30]} + ] +} diff --git a/docs/chapter06/06-graph3-nonconst-peephole.svg b/docs/chapter06/06-graph3-nonconst-peephole.svg new file mode 100644 index 00000000..a60d66f9 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.svg @@ -0,0 +1,109 @@ +#3[0] → #31 · CTRL#8[0] → #1 · CTRL#8[1] → #4 · DATA#22[1] → #5 · CTRL#22[2] → #6 · CTRL#30[1] → #27 · DATA#30[2] → #29 · DATA#31[0] → #22 · CTRL#31[1] → #30 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #31 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRLFalse  #6/1#6 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRLIf  #8#8 If +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA01Region  #22#22 Region +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #6 CTRL012#4  #27#27 #4 +Type not computed + +#1  #29#29 #1 +Type not computed + +φ_ab  #30#30 φ_ab +Type not computed + +[0] → #22 ASSOC +[1] → #27 DATA +[2] → #29 DATA[0] → #22012Return  #31#31 Return +Type not computed + +[0] → #22 CTRL +[1] → #30 DATA01If  #8If · 5 nodes−Fold region diff --git a/docs/chapter06/06-graph3-nonconst.gv b/docs/chapter06/06-graph3-nonconst.gv new file mode 100644 index 00000000..7cd4e8e2 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.gv @@ -0,0 +1,86 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#0" ]; + Con_7 [ label="#1" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_12 [ label="#2" ]; + If13 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_17 [ label="#2" ]; + Con_18 [ label="#3" ]; + Region19 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b20 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region21 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a22 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b23 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Add24 [ label="+" ]; + Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region19;Phi_b20;} + { rank=same; Region21;Phi_b23;Phi_a22;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return25[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Start2:p1[taillabel=1]; + If13 -> If8:p0[taillabel=0 color=red]; + If13 -> Start2:p1[taillabel=1]; + Region19 -> If13:p0[taillabel=1 color=red]; + Region19 -> If13:p1[taillabel=2 color=red]; + Phi_b20 -> Region19 [style=dotted taillabel=0]; + Phi_b20 -> Con_17[taillabel=1]; + Phi_b20 -> Con_18[taillabel=2]; + Region21 -> Region19[taillabel=1 color=red]; + Region21 -> If8:p1[taillabel=2 color=red]; + Phi_a22 -> Region21 [style=dotted taillabel=0]; + Phi_a22 -> Con_12[taillabel=1]; + Phi_a22 -> Con_6[taillabel=2]; + Phi_b23 -> Region21 [style=dotted taillabel=0]; + Phi_b23 -> Phi_b20[taillabel=1]; + Phi_b23 -> Con_7[taillabel=2]; + Add24 -> Phi_b23[taillabel=1]; + Add24 -> Phi_a22[taillabel=2]; + Return25 -> Region21[taillabel=0 color=red]; + Return25 -> Add24[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-nonconst.json b/docs/chapter06/06-graph3-nonconst.json new file mode 100644 index 00000000..77bb6d2c --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.json @@ -0,0 +1,35 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph3-nonconst.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": {"par": 13, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": {"par": 13, "idx": 1}}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 19, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "CTRL", "label": null}, {"idx": 2, "def": 11, "role": "CTRL", "label": null}], "proj": null}, + {"id": 20, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 19, "role": "ASSOC", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 19, "role": "CTRL", "label": null}, {"idx": 2, "def": 9, "role": "CTRL", "label": null}], "proj": null}, + {"id": 22, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}, {"idx": 1, "def": 24, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [5, 8, 9, 21, 22, 23, 24]}, + {"id": 13, "par": 8, "nodes": [10, 11, 13, 19, 20]} + ] +} diff --git a/docs/chapter06/06-graph3-nonconst.svg b/docs/chapter06/06-graph3-nonconst.svg new file mode 100644 index 00000000..2e4ec0fc --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.svg @@ -0,0 +1,150 @@ +#3[0] → #25 · CTRL#8[0] → #1 · CTRL#8[1] → #4 · DATA#13[0] → #5 · CTRL#13[1] → #4 · DATA#19[1] → #10 · CTRL#19[2] → #11 · CTRL#20[1] → #17 · DATA#20[2] → #18 · DATA#21[1] → #19 · CTRL#21[2] → #9 · CTRL#22[1] → #12 · DATA#22[2] → #6 · DATA#23[1] → #20 · DATA#23[2] → #7 · DATA#24[1] → #23 · DATA#24[2] → #22 · DATA#25[0] → #21 · CTRL#25[1] → #24 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #25 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRL#0  #6#6 #0 +Type not computed + +#1  #7#7 #1 +Type not computed + +If  #8#8 If +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA01False  #9/1#9 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRLTrue  #10/0#10 True +Projection 0 of #13 +Type not computed + +[0] → #13 CTRLFalse  #11/1#11 False +Projection 1 of #13 +Type not computed + +[0] → #13 CTRL#2  #12#12 #2 +Type not computed + +If  #13#13 If +Type not computed + +[0] → #5 CTRL +[1] → #4 DATA01#2  #17#17 #2 +Type not computed + +#3  #18#18 #3 +Type not computed + +Region  #19#19 Region +Type not computed + +[0] → — DATA +[1] → #10 CTRL +[2] → #11 CTRL012φ_b  #20#20 φ_b +Type not computed + +[0] → #19 ASSOC +[1] → #17 DATA +[2] → #18 DATA[0] → #19012Region  #21#21 Region +Type not computed + +[0] → — DATA +[1] → #19 CTRL +[2] → #9 CTRL012φ_a  #22#22 φ_a +Type not computed + +[0] → #21 ASSOC +[1] → #12 DATA +[2] → #6 DATA[0] → #21012φ_b  #23#23 φ_b +Type not computed + +[0] → #21 ASSOC +[1] → #20 DATA +[2] → #7 DATA[0] → #21012+  #24#24 + +Type not computed + +[0] → — DATA +[1] → #23 DATA +[2] → #22 DATA012Return  #25#25 Return +Type not computed + +[0] → #21 CTRL +[1] → #24 DATA01If  #8If · 12 nodes−Fold regionIf  #13If · 5 nodes−Fold region diff --git a/docs/chapter06/06-graph3-true.gv b/docs/chapter06/06-graph3-true.gv new file mode 100644 index 00000000..9739169c --- /dev/null +++ b/docs/chapter06/06-graph3-true.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_28 [ label="#4" ]; + Return29 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return29[taillabel=0 color=red]; + Return29 -> Start2:p0[taillabel=0 color=red]; + Return29 -> Con_28[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-true.svg b/docs/chapter06/06-graph3-true.svg new file mode 100644 index 00000000..7e573cc6 --- /dev/null +++ b/docs/chapter06/06-graph3-true.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return29 + +Return + + + +Stop3->Return29 + + +0 + + + +Con_28 + +#4 + + + +Return29->Start2:p0 + + +0 + + + +Return29->Con_28 + + +1 + + + diff --git a/docs/chapter06/06-graph4-arg2.gv b/docs/chapter06/06-graph4-arg2.gv new file mode 100644 index 00000000..7d6913e2 --- /dev/null +++ b/docs/chapter06/06-graph4-arg2.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_44 [ label="#5" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-arg2.svg b/docs/chapter06/06-graph4-arg2.svg new file mode 100644 index 00000000..8ec80be4 --- /dev/null +++ b/docs/chapter06/06-graph4-arg2.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return45 + +Return + + + +Stop3->Return45 + + +0 + + + +Con_44 + +#5 + + + +Return45->Start2:p0 + + +0 + + + +Return45->Con_44 + + +1 + + + diff --git a/docs/chapter06/06-graph4-nonconst.gv b/docs/chapter06/06-graph4-nonconst.gv new file mode 100644 index 00000000..b8899b48 --- /dev/null +++ b/docs/chapter06/06-graph4-nonconst.gv @@ -0,0 +1,122 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#0" ]; + Con_7 [ label="#1" ]; + Con_8 [ label="#0" ]; + If9 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_13 [ label="#1" ]; + Con_14 [ label="#2" ]; + EQNode15 [ label="==" ]; + If16 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_20 [ label="#2" ]; + Con_21 [ label="#3" ]; + Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_c23 [ style=filled fillcolor=lightyellow label="φ_c" ]; + If24 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_28 [ label="#2" ]; + Con_29 [ label="#3" ]; + Region30 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b31 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a33 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b34 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Phi_c35 [ style=filled fillcolor=lightyellow label="φ_c" ]; + Add36 [ label="+" ]; + Add37 [ label="+" ]; + Return38 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region22;Phi_c23;} + { rank=same; Region30;Phi_b31;} + { rank=same; Region32;Phi_c35;Phi_a33;Phi_b34;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return38[taillabel=0 color=red]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> Start2:p1[taillabel=1]; + EQNode15 -> Start2:p1[taillabel=1]; + EQNode15 -> Con_14[taillabel=2]; + If16 -> If9:p0[taillabel=0 color=red]; + If16 -> EQNode15[taillabel=1]; + Region22 -> If16:p0[taillabel=1 color=red]; + Region22 -> If16:p1[taillabel=2 color=red]; + Phi_c23 -> Region22 [style=dotted taillabel=0]; + Phi_c23 -> Con_20[taillabel=1]; + Phi_c23 -> Con_21[taillabel=2]; + If24 -> Region22[taillabel=0 color=red]; + If24 -> Start2:p1[taillabel=1]; + Region30 -> If24:p0[taillabel=1 color=red]; + Region30 -> If24:p1[taillabel=2 color=red]; + Phi_b31 -> Region30 [style=dotted taillabel=0]; + Phi_b31 -> Con_28[taillabel=1]; + Phi_b31 -> Con_29[taillabel=2]; + Region32 -> Region30[taillabel=1 color=red]; + Region32 -> If9:p1[taillabel=2 color=red]; + Phi_a33 -> Region32 [style=dotted taillabel=0]; + Phi_a33 -> Con_13[taillabel=1]; + Phi_a33 -> Con_6[taillabel=2]; + Phi_b34 -> Region32 [style=dotted taillabel=0]; + Phi_b34 -> Phi_b31[taillabel=1]; + Phi_b34 -> Con_7[taillabel=2]; + Phi_c35 -> Region32 [style=dotted taillabel=0]; + Phi_c35 -> Phi_c23[taillabel=1]; + Phi_c35 -> Con_8[taillabel=2]; + Add36 -> Phi_c35[taillabel=1]; + Add36 -> Phi_b34[taillabel=2]; + Add37 -> Add36[taillabel=1]; + Add37 -> Phi_a33[taillabel=2]; + Return38 -> Region32[taillabel=0 color=red]; + Return38 -> Add37[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-nonconst.svg b/docs/chapter06/06-graph4-nonconst.svg new file mode 100644 index 00000000..d38c3636 --- /dev/null +++ b/docs/chapter06/06-graph4-nonconst.svg @@ -0,0 +1,456 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return38 + +Return + + + +Stop3->Return38 + + +0 + + + +Con_6 + +#0 + + + +Con_7 + +#1 + + + +Con_8 + +#0 + + + +If9 + + +If + + + +True + + +False + + + +If9->Start2:p0 + + +0 + + + +If9->Start2:p1 + + +1 + + + +Con_13 + +#1 + + + +Con_14 + +#2 + + + +EQNode15 + +== + + + +EQNode15->Start2:p1 + + +1 + + + +EQNode15->Con_14 + + +2 + + + +If16 + + +If + + + +True + + +False + + + +If16->If9:p0 + + +0 + + + +If16->EQNode15 + + +1 + + + +Con_20 + +#2 + + + +Con_21 + +#3 + + + +Region22 + +Region + + + +Region22->If16:p0 + + +1 + + + +Region22->If16:p1 + + +2 + + + +Phi_c23 + +φ_c + + + +Phi_c23->Con_20 + + +1 + + + +Phi_c23->Con_21 + + +2 + + + +Phi_c23->Region22 + + +0 + + + +If24 + + +If + + + +True + + +False + + + +If24->Start2:p1 + + +1 + + + +If24->Region22 + + +0 + + + +Con_28 + +#2 + + + +Con_29 + +#3 + + + +Region30 + +Region + + + +Region30->If24:p0 + + +1 + + + +Region30->If24:p1 + + +2 + + + +Phi_b31 + +φ_b + + + +Phi_b31->Con_28 + + +1 + + + +Phi_b31->Con_29 + + +2 + + + +Phi_b31->Region30 + + +0 + + + +Region32 + +Region + + + +Region32->If9:p1 + + +2 + + + +Region32->Region30 + + +1 + + + +Phi_a33 + +φ_a + + + +Phi_a33->Con_6 + + +2 + + + +Phi_a33->Con_13 + + +1 + + + +Phi_a33->Region32 + + +0 + + + +Phi_b34 + +φ_b + + + +Phi_b34->Con_7 + + +2 + + + +Phi_b34->Phi_b31 + + +1 + + + +Phi_b34->Region32 + + +0 + + + +Phi_c35 + +φ_c + + + +Phi_c35->Con_8 + + +2 + + + +Phi_c35->Phi_c23 + + +1 + + + +Phi_c35->Region32 + + +0 + + + +Add36 + ++ + + + +Add36->Phi_b34 + + +2 + + + +Add36->Phi_c35 + + +1 + + + +Add37 + ++ + + + +Add37->Phi_a33 + + +2 + + + +Add37->Add36 + + +1 + + + +Return38->Region32 + + +0 + + + +Return38->Add37 + + +1 + + + diff --git a/docs/chapter06/06-graph4-true.gv b/docs/chapter06/06-graph4-true.gv new file mode 100644 index 00000000..6e48ee7d --- /dev/null +++ b/docs/chapter06/06-graph4-true.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_44 [ label="#6" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-true.svg b/docs/chapter06/06-graph4-true.svg new file mode 100644 index 00000000..a533ea21 --- /dev/null +++ b/docs/chapter06/06-graph4-true.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return45 + +Return + + + +Stop3->Return45 + + +0 + + + +Con_44 + +#6 + + + +Return45->Start2:p0 + + +0 + + + +Return45->Con_44 + + +1 + + + diff --git a/docs/chapter06/Makefile b/docs/chapter06/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter06/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter06/README.md b/docs/chapter06/README.md new file mode 100644 index 00000000..0f3ef945 --- /dev/null +++ b/docs/chapter06/README.md @@ -0,0 +1,203 @@ +# Chapter 6: Peepholes for If + +[Previous: Chapter 5](../chapter05/README.md) | +[Next: Chapter 7](../chapter07/README.md) + +# Table of Contents + +1. [Type System Revision](#type-system-revision) +2. [Peephole of `if`](#peephole-of-if) +3. [`Region` and `Phi`](#region-and-phi) +4. [Discussion](#discussion) +5. [Expanding Peephole Beyond Constant Expressions](#expanding-peephole-beyond-constant-expressions) +6. [Dominators](#dominators) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter06) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter05...linear-chapter06) it to the previous chapter. + +In this chapter we do not add new language features. Our goal is to add peephole optimization to `if` statements. + + +## Type System Revision + +We now need to extend the type system to introduce another lattice structure, in addition to the Integer sub-lattice. +As before we denote "Top" by T and "Bottom" by ⊥. + +* "Ctrl" represents a live control, whereas "~Ctrl" represents a dead control. +* "INT" refers to an integer value, note that integer values have their own sub-lattice. + +| | ⊥ | Ctrl | ~Ctrl | T | INT | +|-------|---|------|-------|-------|-----| +| T | ⊥ | Ctrl | ~Ctrl | T | INT | +| Ctrl | ⊥ | Ctrl | Ctrl | Ctrl | ⊥ | +| ~Ctrl | ⊥ | Ctrl | ~Ctrl | ~Ctrl | ⊥ | +| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | + +* "Top" meets any type is that type, +* "Bottom" meets any type is "Bottom", +* "Top", "Bottom", "Ctrl", "~Ctrl" are classed as simple types, +* "Ctrl" meets "~Ctrl" is "Ctrl" +* Unless covered above, a simple type meets non-simple results in "Bottom" + +The entire revised Lattice is shown below: + +![Lattice](./lattice.svg) + + +## Peephole of `if` + +* Our general strategy is to continue parsing the entire `if` statement even if we know that one branch is dead. +* This approach creates dead nodes which get cleaned up by dead code + elimination. The benefits are that we do not introduce special logic during + parsing, the normal graph building machinery takes care of cleaning up dead + nodes. +* When we peephole an `If` node we test if the predicate is a constant. If so, + then one branch or the other is dead, depending on if the constant is `0` or not. +* When we add the `Proj` nodes, in this scenario, we already know one of the projections is dead. The peephole of the + relevant `Proj` node replaces the `Proj` with a `Constant` of type "~Ctrl" indicating dead control. +* At this point our dead code elimination would kill the `If` node since it has no uses + - but we cannot do that because we need to continue the parse. The + important observation is that *we __can__ kill the `If` node after __both__ + the `Proj` nodes have been created*, because any subsequent control flow can + only see the `Proj` nodes. +* To ensure this, we add a dummy user to `If` before creating the first `Proj` and remove it immediately after, allowing the + second `Proj` to trigger a dead code elimination of the `If`. +* The live `Proj` gets replaced by the parent of `If`, whereas the dead `Proj` gets replaced by "~Ctrl". +* The parsing then continues as normal. +* The other changes are when we reach the merge point with a dead control. +* Again keeping with our strategy we merge as normal, including creating `Phi` nodes. +* The `Region` may have one of its inputs as "~Ctrl". This will be seen + by the `Phi` which then optimizes itself. If the `Phi` has just one live + input, the `Phi` peephole replaces itself with the remaining input. +* Finally, at the end, when the `Region` node is peepholed, we see that it has only one live input and no Phi uses + and can be replaced with its one live input. + +## `Region` and `Phi` + +One of the invariants we maintain is that for each control input to a +`Region` every `Phi` has a 1-to-1 relationship with a data input. Thus, if a +`Region` loses a control input, every `Phi`'s corresponding data input must be +deleted. Conversely, we cannot collapse a Region until it has no dependent +`Phi`s. + +When processing `If` we do not remove control inputs to a `Region`, instead the +dead control input is simply set to `Constant(~Ctrl)`. The peephole logic in +a `Phi` notices this and replaces itself with the live input. + +## Discussion + +With the changes above, our peephole optimization is able to fold dead code when +an `if` statement has a condition that evaluates to `true` or `false` at compile time. + +Let's look at a simple example below: + +```java +if( true ) return 2; +return 1; +``` + +Before peephole: + +![Graph1-Pre](./06-graph1-pre.svg) + +After peephole: + +![Graph1-Post](./06-graph1-post.svg) + +Another example: + +```java +int a=1; +if( true ) + a=2; +else + a=3; +return a; +``` + +Before peephole: + +![Graph2-Pre](./06-graph2-pre.svg) + +After peephole: + +![Graph2-Post](./06-graph2-post.svg) + +## Expanding Peephole Beyond Constant Expressions + +While our peephole of the `CFG` collapses dead code when the expression is +a compile-time constant, it does not do as well as it could with the following example: + +```java +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +``` + +In this example, `arg` is defined externally, and we have to assume it is not a constant. +However, the code repeats the `if( arg )` condition in the inner `if` statement. +We know that if the outer `if( arg )` is true, then the *inner `if` must also evaluate to true*. + +Our peephole at present cannot see this: + +![Graph3-NonConst](./06-graph3-nonconst.svg) + +What we would like is for our peephole to see that the inner `if` is fully determined by the +outer `if` and thus, the code can be simplified as follows: + +```java +int a = 0; +int b = 1; +if ( arg ) { + a = 2; + b = 2; +} +return a+b; +``` + +That is, the final outcome is either `4` if `arg` happens to be true, or `1` if `arg` happens to be false. + +## Dominators + +The key to implementing this peephole is the observation that the inner `if` is completely determined by the +outer `if`. In compiler parlance, we say that the outer `if` dominates the inner `if`. + +There is a generic way to determine this type of domination; it involves constructing a dominator +tree. For details of how to do this, please refer to the paper `A Simple, Fast Dominance Algorithm`.[^1] + +However, constructing a dominator tree is an expensive operation; one that we would not like to +do in the middle of parsing. Fortunately, since we do not have loops yet, we do not +have back edges in our control flow graph. Our control flow graph is essentially hierarchical, tree like. +Thus, a simple form of dominator identification is possible. + +The main idea is that we can assign a `depth` to each control node, this represents the node's depth +in the hierarchy. We can compute this depth incrementally as we need to. The nodes that are deeper in the hierarchy +have a greater depth than the ones above. + +Secondly we know that for our control nodes, except for `Region`s, there is only one incoming control edge, +which means that most control nodes have a single immediate dominating control node. `Region` nodes are different +as they can have one or more control edges; but, we know that for `if` statements, a `Region` node has exactly two +control inputs, one from each branch of the `if`. To find the immediate dominator of a `Region` node in the +limited scenario of an `if`, we can follow the immediate dominator of each branch until we find the common ancestor +node that dominates both the branches. + +If this ancestor node is also an `if` and its predicate is the same as the current `if`, then we know that +the outcome of the present `if` is fully determined. + +The code that does this check is in the [`compute` method of the `if`](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java#L38-L45). + +The `idom` method in `Node` provides a default implementation of the depth based immediate dominator calculation. +`Region` [overrides this](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java#L57-L74) to implement the more complex search described above. + +It turns out that to simplify the example above, we need a [further peephole in our `Add` node](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java#L64-L67). + +With all these changes, the outcome of the peephole is just what we would like to see! + +![Graph3-NonConst-Peephole](./06-graph3-nonconst-peephole.svg) + +[^1]: Cooper, K. D. Cooper, Harvey, T. J., and Kennedy, K. (2001). + A Simple, Fast Dominance Algorithm. diff --git a/docs/chapter06/lattice.gv b/docs/chapter06/lattice.gv new file mode 100644 index 00000000..e5cc59be --- /dev/null +++ b/docs/chapter06/lattice.gv @@ -0,0 +1,97 @@ +digraph Lattice { + // Define nodes + splines=false; + node [shape=circle, style=filled, fillcolor=lightblue]; + nodesep=0.6; + + TOP [label=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<⊤:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<⊥:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> 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; XCTRL; INT_TOP; TUPLE_TOP} + {rank=same; + INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; + } + {rank=same; CTRL; INT_BOT, TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter06/lattice.svg b/docs/chapter06/lattice.svg new file mode 100644 index 00000000..86371c93 --- /dev/null +++ b/docs/chapter06/lattice.svg @@ -0,0 +1,319 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +⊤ +:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥ +:ctrl + + + +XCTRL->CTRL + + + + + +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/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 359d0175..b9fbf26f 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -161,6 +161,7 @@ public class Parser { IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); // Setup projection nodes Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); Node ifF = new ProjNode(ifNode, 1, "False").peephole(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current @@ -204,7 +205,7 @@ public class Parser { private Node parseReturn() { var expr = require(parseExpression(), ";"); Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole()); - ctrl(null); // Kill control + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control return ret; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 367cb2c0..22c36746 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -57,7 +57,8 @@ public class AddNode extends Node { // 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; + // Rotate; look for (add (phi cons) con/(phi cons)) + return spine_cmp(lhs,rhs) ? swap12() : phiCon(this,true); // Now we only see (add add non) @@ -66,23 +67,12 @@ public class AddNode extends Node { if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); - if( lhs.in(2) instanceof PhiNode phi && phi.allCons() && - // Do we have ((x + (phi cons)) + con) ? - // Do we have ((x + (phi cons)) + (phi cons)) ? - // Push constant up through the phi: x + (phi con0+con0 con1+con1...) - - // Note that this is the exact reverse of Phi pulling a common op - // down to reduce total op-count. We don't get in an endless push- - // up push-down peephole cycle because the constants all fold first. - (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) { - Node[] ns = new Node[phi.nIns()]; - ns[0] = phi.in(0); - // Push constant up through the phi: x + (phi con0+con0 con1+con1...) - for( int i=1; i 2 ) { + // Only valid to rotate constants if both are same associative ops + if( lhs.getClass() != op.getClass() ) return null; + lphi = pcon(lhs.in(2)); // Will rotate with the Phi push + } + if( lphi==null ) return null; + + // RHS is a constant or a Phi of constants + if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null ) + return null; + + // If both are Phis, must be same Region + if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) ) + return null; + + // Note that this is the exact reverse of Phi pulling a common op down + // to reduce total op-count. We don't get in an endless push-up + // push-down peephole cycle because the constants all fold first. + Node[] ns = new Node[lphi.nIns()]; + ns[0] = lphi.in(0); + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + for( int i=1; i { */ public Type _type; + /** + * Immediate dominator tree depth, used to approximate a real IDOM during + * parsing where we do not have the whole program, and also peepholes + * change the CFG incrementally. + *

+ * See {@link ...} + */ + char _idepth; + /** * A private Global Static mutable counter, for unique node id generation. - * To make the compiler multi-threaded, this field will have to move into a TLS. + * To make the compiler multithreaded, this field will have to move into a TLS. * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; @@ -110,6 +121,17 @@ public abstract class Node extends BaseNode { return new_def; } + // Remove the numbered input, compressing the inputs in-place. This + // shuffles the order deterministically - which is suitable for Region and + // Phi, but not for every Node. + void delDef(int idx) { + Node old_def = in(idx); + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + Utils.del(_inputs, idx); + } + /** * Add a new def to an existing Node. Keep the edges correct by * adding the corresponding def->use edge. @@ -317,6 +339,29 @@ public abstract class Node extends BaseNode { return true; } + // Return the immediate dominator of this Node and compute dom tree depth. + Node idom() { return in(0); } + + // Find the lowest common ancestor in the current dominator tree. + Node domLCA(Node rhs) { + if( rhs==null ) return this; + Node lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; + } + // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index da3917c7..6acb5535 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -24,17 +24,18 @@ public class PhiNode extends Node { @Override public Type compute() { - Type t = in(1)._type; - for( int i=2; i { @Override protected String[] edgeNames(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index a7604165..ea9a705e 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 5's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 6's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 6b9130ba..d66fb3e7 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -25,25 +25,50 @@ public class Type { static final byte TBOT = 0; // Bottom (ALL) static final byte TTOP = 1; // Top (ANY) 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 + static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) + static final byte TSIMPLE = 4; // End of the Simple Types + static final byte TINT = 5; // All Integers; see TypeInteger + static final byte TTUPLE = 6; // 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","Ctrl"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl"}; protected Type(byte type) { _type = type; } 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 static final Type XCONTROL = new Type( TXCTRL ); // ~Ctrl - public boolean isConstant() { return _type == TTOP; } + public boolean isConstant() { return _type == TTOP || _type == TXCTRL; } public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} - public Type meet(Type other) { return BOTTOM; } + public final Type meet(Type t) { + // Shortcut for the self case + if( t == this ) return this; + // Same-type is always safe in the subclasses + if( _type==t._type ) return xmeet(t); + // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this". + if( is_simple() ) return this.xmeet(t ); + if( t.is_simple() ) return t .xmeet(this); + return BOTTOM; // Mixing 2 unrelated types + } + + // Compute meet right now. Overridden in subclasses. + // Handle cases where 'this.is_simple()' and unequal to 't'. + // Subclassed xmeet calls can assert that '!t.is_simple()'. + protected Type xmeet(Type t) { + assert is_simple(); // Should be overridden in subclass + // ANY meet anything is thing; thing meet ALL is ALL + if( _type==TBOT || t._type==TTOP ) return this; + if( _type==TTOP || t._type==TBOT ) return t; + // 'this' is {TCTRL,TXCTRL} + if( !t.is_simple() ) return BOTTOM; + // 't' is {TCTRL,TXCTRL} + return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; + } @Override public final String toString() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index cbaff45f..a9f6ee1c 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -41,7 +41,7 @@ public class TypeInteger extends Type { public long value() { return _con; } @Override - public Type meet(Type other) { + public Type xmeet(Type other) { if( this==other ) return this; if (!(other instanceof TypeInteger i)) return super.meet(other); // BOT wins diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index da701865..39d8f72b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -10,7 +10,7 @@ public class TypeTuple extends Type { } @Override - public Type meet(Type other) { + public Type xmeet(Type other) { throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); } @@ -24,5 +24,9 @@ public class TypeTuple extends Type { return sb; } - public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL}); + public static final TypeTuple IF_BOTH = new TypeTuple(new Type[]{Type.CONTROL, Type.CONTROL}); + public static final TypeTuple IF_NEITHER = new TypeTuple(new Type[]{Type.XCONTROL,Type.XCONTROL}); + public static final TypeTuple IF_TRUE = new TypeTuple(new Type[]{Type.CONTROL, Type.XCONTROL}); + public static final TypeTuple IF_FALSE = new TypeTuple(new Type[]{Type.XCONTROL,Type.CONTROL}); + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..00d725bc --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,294 @@ +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 Chapter06Test { + + @Test + public void testPeepholeReturn() { + Parser parser = new Parser( +""" +if( true ) return 2; +return 1; +"""); + StopNode stop = parser.parse(); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testPeepholeRotate() { + Parser parser = new Parser( +""" +int a = 1; +if (arg) + a = 2; +return (arg < a) < 3; +"""); + StopNode stop = parser.parse(); + assertEquals("return ((arg