From a6d709139ca5cfd647ec23b9f7cfc96aeea3e1eb 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: tannal Co-authored-by: hadha 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 | 92 +++++ README.md | 2 +- docs/chapter06/06-grammar.md | 83 ++++ docs/chapter06/06-graph1-post.gv | 29 ++ docs/chapter06/06-graph1-post.svg | 67 +++ docs/chapter06/06-graph1-pre.gv | 52 +++ docs/chapter06/06-graph1-pre.svg | 160 ++++++++ docs/chapter06/06-graph2-post.gv | 33 ++ docs/chapter06/06-graph2-post.svg | 67 +++ docs/chapter06/06-graph2-pre.gv | 55 +++ docs/chapter06/06-graph2-pre.svg | 154 +++++++ 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.svg | 150 +++++++ docs/chapter06/06-graph3-nonconst.gv | 86 ++++ docs/chapter06/06-graph3-nonconst.svg | 290 +++++++++++++ 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 | 12 + docs/chapter06/README.md | 200 +++++++++ docs/chapter06/lattice.gv | 97 +++++ docs/chapter06/lattice.svg | 319 ++++++++++++++ .../com/seaofnodes/simple/GraphVisualizer.java | 21 +- src/main/java/com/seaofnodes/simple/Parser.java | 3 +- .../java/com/seaofnodes/simple/node/AddNode.java | 67 ++- .../java/com/seaofnodes/simple/node/BoolNode.java | 6 + .../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 | 31 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 28 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 2 + .../com/seaofnodes/simple/node/RegionNode.java | 50 ++- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 5 + .../java/com/seaofnodes/simple/node/StopNode.java | 5 + 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/Chapter02Test.java | 4 - .../java/com/seaofnodes/simple/Chapter03Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 20 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 18 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 294 +++++++++++++ 51 files changed, 3552 insertions(+), 83 deletions(-) create mode 100644 Makefile 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.svg create mode 100644 docs/chapter06/06-graph1-pre.gv 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.svg create mode 100644 docs/chapter06/06-graph2-pre.gv 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.svg create mode 100644 docs/chapter06/06-graph3-nonconst.gv 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 new file mode 100644 index 00000000..56f69e12 --- /dev/null +++ b/Makefile @@ -0,0 +1,92 @@ +SHELL := /bin/bash +.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)) +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 + @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) diff --git a/README.md b/README.md index 7d663c9c..832dfaf2 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..4cf1cac6 --- /dev/null +++ b/docs/chapter06/06-grammar.md @@ -0,0 +1,83 @@ +# Grammar for Chapter 6 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | metaStatement + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + +metaStatement + : '#showGraph' ';' + ; + +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.svg b/docs/chapter06/06-graph1-post.svg new file mode 100644 index 00000000..faabcd8c --- /dev/null +++ b/docs/chapter06/06-graph1-post.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return13 + +Return + + + +Stop3->Return13 + + +0 + + + +Con_12 + +#2 + + + +Return13->Start2:p0 + + +0 + + + +Return13->Con_12 + + +1 + + + 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.svg b/docs/chapter06/06-graph1-pre.svg new file mode 100644 index 00000000..f80edcfc --- /dev/null +++ b/docs/chapter06/06-graph1-pre.svg @@ -0,0 +1,160 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return12 + +Return + + + +Stop3->Return12 + + +0 + + + +Return16 + +Return + + + +Stop3->Return16 + + +1 + + + +Con_6 + +#1 + + + +If7 + + +If + + + +True + + +False + + + +If7->Start2:p0 + + +0 + + + +If7->Con_6 + + +1 + + + +Con_11 + +#2 + + + +Return12->If7:p0 + + +0 + + + +Return12->Con_11 + + +1 + + + +Con_13 + +#~CONTROL + + + +Region14 + +Region + + + +Region14->If7:p1 + + +2 + + + +Region14->Con_13 + + +1 + + + +Con_15 + +#1 + + + +Return16->Region14 + + +0 + + + +Return16->Con_15 + + +1 + + + 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.svg b/docs/chapter06/06-graph2-post.svg new file mode 100644 index 00000000..269eb15c --- /dev/null +++ b/docs/chapter06/06-graph2-post.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Return17 + +Return + + + +Start2 + + +Start + + + +$ctrl + + + +Return17->Start2:p0 + + +0 + + + +Con_13 + +#2 + + + +Return17->Con_13 + + +1 + + + +Stop3 + +Stop + + + +Stop3->Return17 + + +0 + + + 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.svg b/docs/chapter06/06-graph2-pre.svg new file mode 100644 index 00000000..e9a4dd55 --- /dev/null +++ b/docs/chapter06/06-graph2-pre.svg @@ -0,0 +1,154 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Return16 + +Return + + + +Region14 + +Region + + + +Return16->Region14 + + +0 + + + +Phi_a15 + +φ_a + + + +Return16->Phi_a15 + + +1 + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Stop3->Return16 + + +0 + + + +Con_7 + +#1 + + + +If8 + + +If + + + +True + + +False + + + +If8->Start2:p0 + + +0 + + + +If8->Con_7 + + +1 + + + +Con_12 + +#2 + + + +Con_13 + +#3 + + + +Region14->If8:p0 + + +1 + + + +Region14->If8:p1 + + +2 + + + +Phi_a15->Con_12 + + +1 + + + +Phi_a15->Con_13 + + +2 + + + +Phi_a15->Region14 + + +0 + + + 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.svg b/docs/chapter06/06-graph3-nonconst-peephole.svg new file mode 100644 index 00000000..c312ffc5 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.svg @@ -0,0 +1,150 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return31 + +Return + + + +Stop3->Return31 + + +0 + + + +Region22 + +Region + + + +If8 + + +If + + + +True + + +False + + + +Region22->If8:p0 + + +1 + + + +Region22->If8:p1 + + +2 + + + +If8->Start2:p0 + + +0 + + + +If8->Start2:p1 + + +1 + + + +Con_27 + +#4 + + + +Con_29 + +#1 + + + +Phi_ab30 + +φ_ab + + + +Phi_ab30->Region22 + + +0 + + + +Phi_ab30->Con_27 + + +1 + + + +Phi_ab30->Con_29 + + +2 + + + +Return31->Region22 + + +0 + + + +Return31->Phi_ab30 + + +1 + + + 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.svg b/docs/chapter06/06-graph3-nonconst.svg new file mode 100644 index 00000000..dee852e4 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.svg @@ -0,0 +1,290 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return25 + +Return + + + +Stop3->Return25 + + +0 + + + +Con_6 + +#0 + + + +Con_7 + +#1 + + + +If8 + + +If + + + +True + + +False + + + +If8->Start2:p0 + + +0 + + + +If8->Start2:p1 + + +1 + + + +Con_12 + +#2 + + + +If13 + + +If + + + +True + + +False + + + +If13->Start2:p1 + + +1 + + + +If13->If8:p0 + + +0 + + + +Con_17 + +#2 + + + +Con_18 + +#3 + + + +Region19 + +Region + + + +Region19->If13:p0 + + +1 + + + +Region19->If13:p1 + + +2 + + + +Phi_b20 + +φ_b + + + +Phi_b20->Con_17 + + +1 + + + +Phi_b20->Con_18 + + +2 + + + +Phi_b20->Region19 + + +0 + + + +Region21 + +Region + + + +Region21->If8:p1 + + +2 + + + +Region21->Region19 + + +1 + + + +Phi_a22 + +φ_a + + + +Phi_a22->Con_6 + + +2 + + + +Phi_a22->Con_12 + + +1 + + + +Phi_a22->Region21 + + +0 + + + +Phi_b23 + +φ_b + + + +Phi_b23->Con_7 + + +2 + + + +Phi_b23->Phi_b20 + + +1 + + + +Phi_b23->Region21 + + +0 + + + +Add24 + ++ + + + +Add24->Phi_a22 + + +2 + + + +Add24->Phi_b23 + + +1 + + + +Return25->Region21 + + +0 + + + +Return25->Add24 + + +1 + + + 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..12659b8f --- /dev/null +++ b/docs/chapter06/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/chapter06/README.md b/docs/chapter06/README.md new file mode 100644 index 00000000..a5151586 --- /dev/null +++ b/docs/chapter06/README.md @@ -0,0 +1,200 @@ +# Chapter 6: Peepholes for If + +# 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 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 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 the 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 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`'s [override 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/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index c35a4e32..b30dd450 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -17,7 +17,7 @@ public class GraphVisualizer { // nodes in the graph. Collection all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter05 {\n"); + sb.append("digraph chapter06 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -207,29 +207,24 @@ public class GraphVisualizer { * Finds all nodes in the graph. */ private Collection findAll(Parser parser) { - final StartNode start = Parser.START; final HashMap all = new HashMap<>(); - for( Node n : start._outputs ) + for( Node n : Parser.START._outputs ) + walk(all, n); + for( Node n : parser._scope._inputs ) walk(all, n); - // Scan symbol tables - for( HashMap scope : parser._scope._scopes ) - for (Integer i : scope.values()) - walk(all, parser._scope.in(i)); return all.values(); } /** * Walk a subgraph and populate distinct nodes in the all list. */ - private void walk(HashMap all, Node n) { + private void walk(HashMap all, Node n) { if(n == null ) return; if (all.get(n._nid) != null) return; // Been there, done that all.put(n._nid, n); for (Node c : n._inputs) - if (c != null) - walk(all, c); - for (Node c : n._outputs) - if (c != null) - walk(all, c); + walk(all, c); + for( Node c : n._outputs ) + walk(all, c); } } diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 80674d59..1a15efa3 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -155,6 +155,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 @@ -198,7 +199,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 081c9276..b37785f6 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -63,7 +63,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 spline_cmp(lhs,rhs) ? swap12() : null; + // Rotate; look for (add (phi cons) con/(phi cons)) + return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true); // Now we only see (add add non) @@ -72,23 +73,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 + * See {@link ...} + */ + int _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; @@ -151,6 +161,17 @@ public abstract class Node { 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. @@ -358,6 +379,14 @@ public abstract class Node { return true; } + // Return the immediate dominator of this Node and compute dom tree depth. + Node idom() { + Node idom = in(0); + if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth + if( _idepth==0 ) _idepth = idom._idepth+1; + return idom; + } + // 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 374e1183..15088e08 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -26,14 +26,18 @@ public class PhiNode extends Node { @Override public Type compute() { - return Type.BOTTOM; + Type t = Type.TOP; + for (int i = 1; i < nIns(); i++) + t = t.meet(in(i)._type); + return t; } @Override public Node idealize() { - // Remove a "junk" Phi: Phi(x,x) is just x - if( same_inputs() ) - return in(1); + // If we have only a single unique input, become it. + Node live = singleUniqueInput(); + if (live != null) + return live; // Pull "down" a common data op. One less op in the world. One more // Phi, but Phis do not make code. @@ -63,11 +67,17 @@ public class PhiNode extends Node { return true; } - private boolean same_inputs() { - for( int i=2; i= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + if( lhs==null ) return null; + _idepth = lhs._idepth+1; + return (_idom=lhs); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c9d6c9c8..6130d050 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -36,5 +36,9 @@ public class ReturnNode extends Node { } @Override - public Node idealize() { return null; } + public Node idealize() { + if( ctrl()._type==Type.XCONTROL ) + return ctrl(); + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 32045fbc..a7a04a42 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -162,14 +162,14 @@ public class ScopeNode extends Node { * @return A new node representing the merge point */ public Node mergeScopes(ScopeNode that) { - RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); + RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); String[] ns = reverseNames(); // Note that we skip i==0, which is bound to '$ctrl' for (int i = 1; i < nIns(); i++) if( in(i) != that.in(i) ) // No need for redundant Phis setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); that.kill(); // Kill merged scope - return r; + return r.unkeep().peephole(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 022e276d..c5a45876 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -35,4 +35,9 @@ public class StartNode extends MultiNode { @Override public Node idealize() { return null; } + + // No immediate dominator, and idepth==0 + @Override + Node idom() { return null; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index a30256f9..01574dc7 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -36,6 +36,11 @@ public class StopNode extends Node { @Override public Node idealize() { + int len = nIns(); + for( int i=0; i