From 8a543b86312eb5c7c175fe06b861c3462e0d2884 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 3 Mar 2024 17:55:47 +0000 Subject: Chapter 9: Global Value Numbering and Iterative Peepholes Co-authored-by: Thalia Archibald Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamas Hadhazy Co-authored-by: Robert Obkircher Co-authored-by: Dibyendu Majumdar Co-authored-by: Darrick Wiebe --- Makefile | 8 +- README.md | 2 +- docs/chapter09/09-grammar.md | 98 +++++++ docs/chapter09/09-graph1.gv | 67 +++++ docs/chapter09/09-graph1.svg | 222 +++++++++++++++ docs/chapter09/09-graph2.gv | 63 +++++ docs/chapter09/09-graph2.svg | 196 ++++++++++++++ docs/chapter09/09-graph3.gv | 37 +++ docs/chapter09/09-graph3.svg | 109 ++++++++ docs/chapter09/09-graph4.gv | 29 ++ docs/chapter09/09-graph4.svg | 67 +++++ docs/chapter09/09-graph5.gv | 63 +++++ docs/chapter09/09-graph5.svg | 210 +++++++++++++++ docs/chapter09/09-graph6.gv | 60 +++++ docs/chapter09/09-graph6.svg | 184 +++++++++++++ docs/chapter09/Makefile | 12 + docs/chapter09/README.md | 278 +++++++++++++++++++ .../java/com/seaofnodes/simple/GraphEvaluator.java | 2 +- .../com/seaofnodes/simple/GraphVisualizer.java | 30 ++- src/main/java/com/seaofnodes/simple/IRPrinter.java | 7 +- src/main/java/com/seaofnodes/simple/IterPeeps.java | 204 ++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 75 ++++-- .../java/com/seaofnodes/simple/node/AddNode.java | 51 ++-- .../java/com/seaofnodes/simple/node/BoolNode.java | 3 +- .../com/seaofnodes/simple/node/ConstantNode.java | 17 +- .../java/com/seaofnodes/simple/node/DivNode.java | 3 +- .../java/com/seaofnodes/simple/node/IfNode.java | 29 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulNode.java | 3 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 7 + src/main/java/com/seaofnodes/simple/node/Node.java | 261 ++++++++++++++---- .../java/com/seaofnodes/simple/node/NotNode.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 49 +++- .../java/com/seaofnodes/simple/node/ProjNode.java | 10 +- .../com/seaofnodes/simple/node/RegionNode.java | 68 +++-- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 3 + .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 11 +- .../java/com/seaofnodes/simple/node/SubNode.java | 3 +- src/main/java/com/seaofnodes/simple/type/Type.java | 76 +++++- .../com/seaofnodes/simple/type/TypeInteger.java | 59 ++-- .../java/com/seaofnodes/simple/type/TypeTuple.java | 46 +++- .../java/com/seaofnodes/simple/Chapter02Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 13 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 38 +-- .../java/com/seaofnodes/simple/Chapter07Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter08Test.java | 36 +-- .../java/com/seaofnodes/simple/Chapter09Test.java | 300 +++++++++++++++++++++ .../java/com/seaofnodes/simple/FuzzerWrap.java | 13 +- .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 42 +++ .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 86 +++++- .../java/com/seaofnodes/simple/fuzzer/Reducer.java | 2 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 32 +-- 55 files changed, 3013 insertions(+), 297 deletions(-) create mode 100644 docs/chapter09/09-grammar.md create mode 100644 docs/chapter09/09-graph1.gv create mode 100644 docs/chapter09/09-graph1.svg create mode 100644 docs/chapter09/09-graph2.gv create mode 100644 docs/chapter09/09-graph2.svg create mode 100644 docs/chapter09/09-graph3.gv create mode 100644 docs/chapter09/09-graph3.svg create mode 100644 docs/chapter09/09-graph4.gv create mode 100644 docs/chapter09/09-graph4.svg create mode 100644 docs/chapter09/09-graph5.gv create mode 100644 docs/chapter09/09-graph5.svg create mode 100644 docs/chapter09/09-graph6.gv create mode 100644 docs/chapter09/09-graph6.svg create mode 100644 docs/chapter09/Makefile create mode 100644 docs/chapter09/README.md create mode 100644 src/main/java/com/seaofnodes/simple/IterPeeps.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter09Test.java diff --git a/Makefile b/Makefile index 3c271042..b5c21b38 100644 --- a/Makefile +++ b/Makefile @@ -66,7 +66,13 @@ $(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" tests: $(default_targets) - $(JVM) org.junit.runner.JUnitCore $(test_cp) + @echo "testing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore $(test_cp) + +fuzzer: $(default_targets) + @echo "testing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap + .PHONY: clean clean: diff --git a/README.md b/README.md index 6eaff6e6..2d670b17 100644 --- a/README.md +++ b/README.md @@ -46,7 +46,7 @@ The Simple language will be styled after a subset of C or Java * [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow. * [Chapter 7](docs/chapter07/README.md): `while` statement. Looping construct - eager phi approach. * [Chapter 8](docs/chapter08/README.md): Looping construct continued, lazy phi creation, `break` and `continue` statements. -* Chapter 9: Global Value Numbering. Iterative peepholes to fixpoint. Worklists. +* [Chapter 9](docs/chapter09/README.md): Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * Chapter 10: User defined Struct types. Memory effects: general memory edges in SSA. Equivalence class aliasing. Null pointer analysis. Peephole optimization around load-after-store/store-after-store. * Chapter 11: Global Code Motion - Scheduling. * Chapter 12: Float type. diff --git a/docs/chapter09/09-grammar.md b/docs/chapter09/09-grammar.md new file mode 100644 index 00000000..4c61bfd7 --- /dev/null +++ b/docs/chapter09/09-grammar.md @@ -0,0 +1,98 @@ +# Grammar for Chapter 8 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + | metaStatement + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +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/chapter09/09-graph1.gv b/docs/chapter09/09-graph1.gv new file mode 100644 index 00000000..e6d1851a --- /dev/null +++ b/docs/chapter09/09-graph1.gv @@ -0,0 +1,67 @@ +digraph chapter08 { +/* +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="2" ]; + Mul8 [ label="*" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_16 [ label="2" ]; + Mul17 [ label="*" ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_20 [ label="1" ]; + Add21 [ label="+" ]; + Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + Stop3 -> Return24[taillabel=1 color=red]; + Mul8 -> Start2:p1[taillabel=1]; + Mul8 -> Con_7[taillabel=2]; + LT10 -> Start2:p1[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Start2:p0[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Mul17 -> Start2:p1[taillabel=1]; + Mul17 -> Con_16[taillabel=2]; + Return18 -> If11:p0[taillabel=0 color=red]; + Return18 -> Mul17[taillabel=1]; + Add21 -> Mul8[taillabel=1]; + Add21 -> Con_20[taillabel=2]; + Return24 -> If11:p1[taillabel=0 color=red]; + Return24 -> Add21[taillabel=1]; +} diff --git a/docs/chapter09/09-graph1.svg b/docs/chapter09/09-graph1.svg new file mode 100644 index 00000000..fce8d53c --- /dev/null +++ b/docs/chapter09/09-graph1.svg @@ -0,0 +1,222 @@ + + + + + + +chapter08 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return18 + +Return + + + +Stop3->Return18 + + +0 + + + +Return24 + +Return + + + +Stop3->Return24 + + +1 + + + +Con_7 + +2 + + + +Mul8 + +* + + + +Mul8->Start2:p1 + + +1 + + + +Mul8->Con_7 + + +2 + + + +Con_9 + +10 + + + +LT10 + +< + + + +LT10->Start2:p1 + + +1 + + + +LT10->Con_9 + + +2 + + + +If11 + + +If + + + +True + + +False + + + +If11->Start2:p0 + + +0 + + + +If11->LT10 + + +1 + + + +Con_16 + +2 + + + +Mul17 + +* + + + +Mul17->Start2:p1 + + +1 + + + +Mul17->Con_16 + + +2 + + + +Return18->If11:p0 + + +0 + + + +Return18->Mul17 + + +1 + + + +Con_20 + +1 + + + +Add21 + ++ + + + +Add21->Mul8 + + +1 + + + +Add21->Con_20 + + +2 + + + +Return24->If11:p1 + + +0 + + + +Return24->Add21 + + +1 + + + diff --git a/docs/chapter09/09-graph2.gv b/docs/chapter09/09-graph2.gv new file mode 100644 index 00000000..1a1f7a29 --- /dev/null +++ b/docs/chapter09/09-graph2.gv @@ -0,0 +1,63 @@ +digraph chapter09 { +/* +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="#2" ]; + Mul8 [ label="*" ]; + LT9 [ label="<" ]; + Con_10 [ label="#10" ]; + If11 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Add20 [ label="+" ]; + Con_21 [ label="#1" ]; + Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + Stop3 -> Return24[taillabel=1 color=red]; + Mul8 -> Start2:p1[taillabel=1]; + Mul8 -> Con_7[taillabel=2]; + LT9 -> Start2:p1[taillabel=1]; + LT9 -> Con_10[taillabel=2]; + If11 -> Start2:p0[taillabel=0 color=red]; + If11 -> LT9[taillabel=1]; + Return18 -> If11:p0[taillabel=0 color=red]; + Return18 -> Mul8[taillabel=1]; + Add20 -> Mul8[taillabel=1]; + Add20 -> Con_21[taillabel=2]; + Return24 -> If11:p1[taillabel=0 color=red]; + Return24 -> Add20[taillabel=1]; +} diff --git a/docs/chapter09/09-graph2.svg b/docs/chapter09/09-graph2.svg new file mode 100644 index 00000000..111ec172 --- /dev/null +++ b/docs/chapter09/09-graph2.svg @@ -0,0 +1,196 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return18 + +Return + + + +Stop3->Return18 + + +0 + + + +Return24 + +Return + + + +Stop3->Return24 + + +1 + + + +Con_7 + +#2 + + + +Mul8 + +* + + + +Mul8->Start2:p1 + + +1 + + + +Mul8->Con_7 + + +2 + + + +LT9 + +< + + + +LT9->Start2:p1 + + +1 + + + +Con_10 + +#10 + + + +LT9->Con_10 + + +2 + + + +If11 + + +If + + + +True + + +False + + + +If11->Start2:p0 + + +0 + + + +If11->LT9 + + +1 + + + +Return18->Mul8 + + +1 + + + +Return18->If11:p0 + + +0 + + + +Add20 + ++ + + + +Add20->Mul8 + + +1 + + + +Con_21 + +#1 + + + +Add20->Con_21 + + +2 + + + +Return24->If11:p1 + + +0 + + + +Return24->Add20 + + +1 + + + diff --git a/docs/chapter09/09-graph3.gv b/docs/chapter09/09-graph3.gv new file mode 100644 index 00000000..37bb1c53 --- /dev/null +++ b/docs/chapter09/09-graph3.gv @@ -0,0 +1,37 @@ +digraph chapter08 { +/* +return arg*arg-arg*arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Mul6 [ label="*" ]; + Mul7 [ label="*" ]; + Sub8 [ label="-" ]; + Return9 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return9[taillabel=0 color=red]; + Mul6 -> Start2:p1[taillabel=1]; + Mul6 -> Start2:p1[taillabel=2]; + Mul7 -> Start2:p1[taillabel=1]; + Mul7 -> Start2:p1[taillabel=2]; + Sub8 -> Mul6[taillabel=1]; + Sub8 -> Mul7[taillabel=2]; + Return9 -> Start2:p0[taillabel=0 color=red]; + Return9 -> Sub8[taillabel=1]; +} diff --git a/docs/chapter09/09-graph3.svg b/docs/chapter09/09-graph3.svg new file mode 100644 index 00000000..f26c96e8 --- /dev/null +++ b/docs/chapter09/09-graph3.svg @@ -0,0 +1,109 @@ + + + + + + +chapter08 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return9 + +Return + + + +Stop3->Return9 + + +0 + + + +Mul6 + +* + + + +Mul6->Start2:p1 + + +1 + + + +Mul7 + +* + + + +Mul7->Start2:p1 + + +1 + + + +Sub8 + +- + + + +Sub8->Mul6 + + +1 + + + +Sub8->Mul7 + + +2 + + + +Return9->Start2:p0 + + +0 + + + +Return9->Sub8 + + +1 + + + diff --git a/docs/chapter09/09-graph4.gv b/docs/chapter09/09-graph4.gv new file mode 100644 index 00000000..8886f73a --- /dev/null +++ b/docs/chapter09/09-graph4.gv @@ -0,0 +1,29 @@ +digraph chapter09 { +/* +return arg*arg-arg*arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_9 [ label="#0" ]; + Return10 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return10[taillabel=0 color=red]; + Return10 -> Start2:p0[taillabel=0 color=red]; + Return10 -> Con_9[taillabel=1]; +} diff --git a/docs/chapter09/09-graph4.svg b/docs/chapter09/09-graph4.svg new file mode 100644 index 00000000..4eef5414 --- /dev/null +++ b/docs/chapter09/09-graph4.svg @@ -0,0 +1,67 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return10 + +Return + + + +Stop3->Return10 + + +0 + + + +Con_9 + +#0 + + + +Return10->Start2:p0 + + +0 + + + +Return10->Con_9 + + +1 + + + diff --git a/docs/chapter09/09-graph5.gv b/docs/chapter09/09-graph5.gv new file mode 100644 index 00000000..72274239 --- /dev/null +++ b/docs/chapter09/09-graph5.gv @@ -0,0 +1,63 @@ +digraph chapter09 { +/* +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#1" ]; + Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg9 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT10 [ label="<" ]; + Con_11 [ label="#10" ]; + If12 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Add16 [ label="+" ]; + Add18 [ label="+" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop7;Phi_arg9;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + Loop7 -> Start2:p0[taillabel=1 color=red]; + Loop7 -> If12:p0[taillabel=2 color=red constraint=false]; + Phi_arg9 -> Loop7 [style=dotted taillabel=0]; + Phi_arg9 -> Start2:p1[taillabel=1]; + Phi_arg9 -> Add18[taillabel=2 constraint=false]; + LT10 -> Phi_arg9[taillabel=1]; + LT10 -> Con_11[taillabel=2]; + If12 -> Loop7[taillabel=0 color=red]; + If12 -> LT10[taillabel=1]; + Add16 -> Con_6[taillabel=1]; + Add16 -> Phi_arg9[taillabel=2]; + Add18 -> Add16[taillabel=1]; + Add18 -> Con_6[taillabel=2]; + Return21 -> If12:p1[taillabel=0 color=red]; + Return21 -> Phi_arg9[taillabel=1]; +} diff --git a/docs/chapter09/09-graph5.svg b/docs/chapter09/09-graph5.svg new file mode 100644 index 00000000..9d0698db --- /dev/null +++ b/docs/chapter09/09-graph5.svg @@ -0,0 +1,210 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return21 + +Return + + + +Stop3->Return21 + + +0 + + + +Con_6 + +#1 + + + +Loop7 + +Loop + + + +Loop7->Start2:p0 + + +1 + + + +If12 + + +If + + + +True + + +False + + + +Loop7->If12:p0 + + +2 + + + +Phi_arg9 + +φ_arg + + + +Phi_arg9->Start2:p1 + + +1 + + + +Phi_arg9->Loop7 + + +0 + + + +Add18 + ++ + + + +Phi_arg9->Add18 + + +2 + + + +LT10 + +< + + + +LT10->Phi_arg9 + + +1 + + + +Con_11 + +#10 + + + +LT10->Con_11 + + +2 + + + +If12->Loop7 + + +0 + + + +If12->LT10 + + +1 + + + +Add16 + ++ + + + +Add16->Con_6 + + +1 + + + +Add16->Phi_arg9 + + +2 + + + +Add18->Con_6 + + +2 + + + +Add18->Add16 + + +1 + + + +Return21->Phi_arg9 + + +1 + + + +Return21->If12:p1 + + +0 + + + diff --git a/docs/chapter09/09-graph6.gv b/docs/chapter09/09-graph6.gv new file mode 100644 index 00000000..56dc6ada --- /dev/null +++ b/docs/chapter09/09-graph6.gv @@ -0,0 +1,60 @@ +digraph chapter09 { +/* +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Loop7 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg9 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + LT10 [ label="<" ]; + Con_11 [ label="#10" ]; + If12 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_24 [ label="#2" ]; + Add25 [ label="+" ]; + { rank=same; Loop7;Phi_arg9;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + Loop7 -> Start2:p0[taillabel=1 color=red]; + Loop7 -> If12:p0[taillabel=2 color=red constraint=false]; + Phi_arg9 -> Loop7 [style=dotted taillabel=0]; + Phi_arg9 -> Start2:p1[taillabel=1]; + Phi_arg9 -> Add25[taillabel=2 constraint=false]; + LT10 -> Phi_arg9[taillabel=1]; + LT10 -> Con_11[taillabel=2]; + If12 -> Loop7[taillabel=0 color=red]; + If12 -> LT10[taillabel=1]; + Return21 -> If12:p1[taillabel=0 color=red]; + Return21 -> Phi_arg9[taillabel=1]; + Add25 -> Phi_arg9[taillabel=1]; + Add25 -> Con_24[taillabel=2]; +} diff --git a/docs/chapter09/09-graph6.svg b/docs/chapter09/09-graph6.svg new file mode 100644 index 00000000..36c70099 --- /dev/null +++ b/docs/chapter09/09-graph6.svg @@ -0,0 +1,184 @@ + + + + + + +chapter09 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return21 + +Return + + + +Stop3->Return21 + + +0 + + + +Loop7 + +Loop + + + +Loop7->Start2:p0 + + +1 + + + +If12 + + +If + + + +True + + +False + + + +Loop7->If12:p0 + + +2 + + + +Phi_arg9 + +φ_arg + + + +Phi_arg9->Start2:p1 + + +1 + + + +Phi_arg9->Loop7 + + +0 + + + +Add25 + ++ + + + +LT10 + +< + + + +LT10->Phi_arg9 + + +1 + + + +Con_11 + +#10 + + + +LT10->Con_11 + + +2 + + + +If12->Loop7 + + +0 + + + +If12->LT10 + + +1 + + + +Return21->Phi_arg9 + + +1 + + + +Return21->If12:p1 + + +0 + + + +Con_24 + +#2 + + + +Add25->Phi_arg9 + + + +1 + + + +Add25->Con_24 + + +2 + + + diff --git a/docs/chapter09/Makefile b/docs/chapter09/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter09/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/chapter09/README.md b/docs/chapter09/README.md new file mode 100644 index 00000000..f0c18cbe --- /dev/null +++ b/docs/chapter09/README.md @@ -0,0 +1,278 @@ +# Chapter 9: Global Value Numbering and Iterative Peepholes + +In this chapter: + +* We add Global Value Numbering (Common Subexpression Elimination) +* We add a post-parse iterate-peepholes-to-fixed-point optimization + +No language changes in this chapter, just adding optimizations. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter09) 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-chapter08...linear-chapter09) it to the previous chapter. + +## Engineering Peepholes + +The goal for Ch 9 is to "finish out" the Peepholes. Not that no more peeps will +appear, on the contrary lots will - but this is the infrastructure to organize +them, engineer them safe and sane; to apply them until a fixed point is reached. + +Really the goal here is to be fearless about adding a new peephole; if you got +it wrong you'll assert pretty fast. If you got it right, that new peep will +just run alongside all the others and they will all mutually benefit each other. + + +## Global Value Numbering + +Global Value Numbering works via a classic hash table, hashing on a Node's +opcode and inputs. If two Nodes do the same function on the same inputs, they +get the same result - and can be shared. + +* We add a global static hash table `GVN` in Node. +* We add a `Node.equals` call. Two Nodes are equals if they have the same + opcode - same Java class - on the same inputs. +* We add a `hashCode` on the Node opcode (proxy: Node string name) and inputs. +* `ConstantNode` and a few others need some extra custom bits here: the + constant 17 is not the same as 99, but both are the same `ConstantNode` class + and label. The `eq` and `hash` calls check (or hash) these extra bits. + +Since we edit the graph a lot, Nodes can have their inputs change which changes +their hash which means they can't be found in the GVN table. E.g. we swap out +the `Add` for a `Con` in: + + (Mul (Add 4 8) x) // Fold the constant + (Mul 12 x) // The `Mul` changes hash and inputs + +The fix for this is to require Nodes NOT be in the `GVN` table when their edges +modify; they need some sort of "edge lock". If "edges are locked", we need to +remove the Node from `GVN` first, before modifying the edges. + +* We use the `_hash` field as both a cached hash code and as the edge lock. If + zero the Node is unlocked and NOT in `GVN`. If non-zero, the Node is + "edge-locked" and IS in `GVN`. +* The `hashCode` function uses the cached hash if available and disallows an + accidental zero hash. +* We add a `unlock()` call to remove a Node from `GVN` before any edge is + changed. This is inserted in front of all calls which hack Node edges. All + edge modify code paths already ensure the Node is re-peepholed, and during + this revisit the Node will get re-inserted in the `GVN` table. + +This new `GVN` table is used in `peepholeOpt()` (and `peephole()`) to look for common +subexpressions on every peephole'd Node. If the Node has a zero hash, we look +for a hit against some previous identical Node. If found, we use the prior +Node and dead-code-eliminate this one. If not found, we insert this Node +into `GVN` as the "golden instance". If a Node already has a non-zero hash +we know it IS the "golden instance" and do not need to look in `GVN`. + +This entire optimization takes about a dozen lines in `iter()`, plus the common +shared `equals` and `hashCode` (about 50 more lines counting comments). + +One of our invariants is that Types monotonically increase while running +peepholes. GVN can break this briefly: of the two equivalent Nodes one has +already had its `_type` lifted but not the other. Depending on which of the +two Nodes is kept, we might choose the Node with the "lower" `_type`. This is +"lower" in the Type lattice sense. Both types must be correct, and a +`compute()` call on both nodes must produce the same Type, which must be equal +to the JOIN. A fix is to compute a JOIN (not a MEET) over the two Nodes' types. + + +## Post-Parse Iterative Peepholes + +The post-Parse `IterPeeps` iterates the peepholes to a fixed point - so +no more peepholes apply. This should be linear because peepholes rarely +(never?) increase code size. The graph should monotonically reduce in some +dimension, which is usually size. It might also reduce in e.g. number of +MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper +ones. + +The theoretical overall worklist is mindless just grabbing the next thing and +doing it. If the graph changes, put the neighbors on the worklist. Lather, +Rinse, Repeat until the worklist runs dry. + +The main issues we have to deal with: + +* Nodes have uses; replacing some set of Nodes with another requires more graph + reworking. Not rocket science, but it can be fiddly. Its helpful to have a + small set of graph munging utilities, and the strong invariant that the graph + is stable and correct between peepholes. In our case `Node.subsume` does + most of the munging, building on our prior stable Node utilities. + +* Changing a Node also changes the graph "neighborhood". The neigbors need to + be checked to see if THEY can also peephole, and so on. After any peephole + or graph update we put a Nodes uses and defs on the worklist. + +* Our strong invariant is that for all Nodes, either they are on the worklist + OR no peephole applies. This invariant is easy to check, although expensive. + Basically the normal "iterate peepholes to a fixed point" is linear, and this + check is linear at each peephole step... so quadratic overall. Its a useful + assert, but one we can disable once the overall algorithm is stable - and + then turn it back on again when some new set of peepholes is misbehaving. + The code for this is turned on in `IterPeeps.iterate` as `assert + progressOnList(stop);` + + +## Distant Neighbors + +For some peepholes the "neighborhood" is farther away than just the immediate +uses or defs, and for these we need a longer range plan. E.g. some peephole +inspects "this -> A -> B -> C" and will swap itself for "D"; however it fails +some test at "B". Should "B" ever update we want to revisit "this" and recheck +his peepholes. So we will need to record a dependence of "this" in "B". +Updating "B" throws the dependent list ("this") onto the "todo" list. + +An example of a distant neighbor check is in `AddNode`, where we check for +stacked constants: `(Add (Add x 2) 1)` and we'd like `(Add x 3)` instead. +Suppose we're doing this check and we find instead `(Add (Phi (Add x 2) self) +1)` The check naturally bails out at the `Phi` since its not an `Add`, but the +`(Phi y self)` only has one unique input, and will itself peephole to `y` +eventually. When it does, our stacked `Add` peephole can apply. So the +failing Add peephole calls `phi.addDep(Add)` and registers a dependency on the +`Phi`. If the `Phi` indeed later optimizes, we add its depencencies (e.g. the +`Add`) back on our `IterPeeps` worklist and retry the stacked Add peephole. + +The general rule is: +* **If a peephole pattern inspects a remote node, it must go on the dependency list!** +* `node.in(1).in(2)` becomes `node.in(1).in(2).addDep(node)` + + +In this chapter we trigger on following patterns + +* Some peeps interact with `Phi` inputs; this can be direct or indirect, + e.g. `(Add Add( (Phi x) 2 ) 1)`. The peep can progress if all of the `Phi`'s + inputs are `Constant`'s. Thus, we make the node a dependent on the `Phi`'s + input. We also make the node a dependent of the `Phi`'s region. See + `Node.allCons()` and `PhiNode.allCons()`. +* The pattern `(Add (Add x 1) 2)` adds the outer `Add` as dependency of `x` + because `x` becoming a constant would enable progress. See + `AddNode.idealize()` +* When computing a `Phi`'s type, if we observe that the associated region's + corresponding control is live, we add the `Phi` as a dependent of the + region's control input, because if that control goes dead, it would allow the + `Phi` to undergo peephole. See `PhiNode.compute()` and + `PhiNode.singleUniqueInput()`. + +Changes: + +* We add a `ArrayList _deps` field to Node; initially null. +* Some peepholes (see above) add dependencies if they fail a remote check, by calling + `distant.addDep(this)`. The `addDep` call creates `_deps` and + filters for various kinds of duplicate adds. +* The `IterPeeps` loop, when it finds a change, also moves all the + dependents onto the worklist. + + +## Other Concerns + +There are more issues we will want to deal with in a later Chapter: + +* Blindly running peepholes in any order has some drawbacks: + + - Dead and dying stuff might get peepholes done... and then die. Wasted work. + - Dead infinite loops often lead to infinite peephole cycles... if only we + would get around to working on the "base" of the dead loop it would fold + up. + - Some peepholes naturally reduce the graph directly; while some keeps its + size the same but reduce other things (e.g. swapping a Mul-by-2 with a + Shift), and we might end up with a few which try to grow the graph briefly + before collapsing. + +* All this means is there's some benefit to running peepholes that reduce the + graph directly (e.g. Dead Code Eliminate), before running peeps that reduce + other things, before running all other peeps. This implies a sorted + worklist, but the count of unique orders is really limited - a radix sort is + all that is needed. We'll have to break up the peepholes into some + categories like + - "strictly reducing" vs + - "same Nodes but swapping e.g. `Mul` for `Shift`, vs + - getting more freedom (edge bypass), vs + - "grow now because shrink later" (inlining lands in this camp). + +* Also there's a benefit to not always grabbing from either end of the list - + many peep patterns might go quadratic if approached from one end or another, + because they modify something then push it back onto the list where it + immediately gets pulled again. I.e., you end up spinning in a loop repeating + the same peeps while slowly migrating a e.g. left-spine add-tree into a + right-spine add-tree. A psuedo-random pull uses randomization to defeat bad + peep patterns. + +* Why isn't `IterPeeps` just passing over all of the Nodes once or twice, + instead of using a worklist with the `addDeps` mechanism? We could even + visit them in a defs-before-uses order (e.g. Reverse Post Order). + + In the absense of loops exactly one such pass will find all local peepholes, + and indeed the Parser already does this. However, this will fail to find + opportunities at loops and farther remote cases - and to get those peepholes + around loops will require another visit. It is easy to construct a case + requiring O(N) passes, each of cost O(N) and the algorithm quickly goes + quadratic. + + The `addDeps` solution avoids this quadratic cost, in exchange for some more + costs in writing peepholes. + + +# Examples + +## Common SubExpressions via GVN + +### Example 1 + +Here is a small example that illustrates how GVN enables finding common sub-expressions. + +```java +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; +``` + +Prior to GVN, this would result in following graph. Note that the `arg+arg` is translated to `arg*2`. + +![Graph1](./09-graph1.svg) + +Adding GVN, we get below. Note how the `arg*2` expression is now reused rather than appearing twice. + +![Graph2](./09-graph2.svg) + +### Example 2 + +Being able to reuse common expressions, enables additional optimizations. Here is a simple example: + +```java +return arg*arg-arg*arg; +``` + +Without GVN the peepholes cannot see that both sides of the subtraction have the same value. + +![Graph3](./09-graph3.svg) + +- Each multiplication(*) node has two edges going to `arg`. +- In the example above, we fused them to make the graph more readable. + +With GVN, the peepholes can do a better job: + +![Graph4](./09-graph4.svg) + +## Post Parse Iterative Optimizations + +The worklist based post parse optimization enables certain optimizations that are not available +during parsing. For example: + +```java +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; +``` + +While parsing the `while` loop it is not yet known that `step` is a constant and will not change. Therefore, +without the post parse optimization we get following: + +![Graph5](./09-graph5.svg) + +Enabling the post parse worklist based optimization yields below. Notice that now the graph shows `arg+2` inside the +loop body: + +![Graph6](./09-graph6.svg) diff --git a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java index f5694a78..9fc51c8e 100644 --- a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java +++ b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -167,7 +167,7 @@ public class GraphEvaluator { public static long evaluate(Node graph, long parameter, int loops) { var res = evaluateWithResult(graph, parameter, loops); - if (res.type==ResultType.TIMEOUT) throw new RuntimeException("Timeout"); + if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout"); return res.value; } diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index d75e5bea..b4d64d4c 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -20,15 +20,16 @@ public class GraphVisualizer { public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; } public GraphVisualizer() { this(false); } - public String generateDotOutput(Parser parser) { + public String generateDotOutput(Parser parse) { return generateDotOutput(parse.STOP,parse._scope,parse._xScopes); } + public String generateDotOutput(StopNode stop, Node scope, Stack xScopes) { // Since the graph has cycles, we need to create a flat list of all the // nodes in the graph. - Collection all = findAll(parser); + Collection all = findAll(stop, scope); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter08 {\n"); + sb.append("digraph chapter09 {\n"); sb.append("/*\n"); - sb.append(parser.src()); + sb.append(stop._src); sb.append("\n*/\n"); // To keep the Scopes below the graph and pointing up into the graph we @@ -52,15 +53,19 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - for( ScopeNode scope : parser._xScopes ) - scope( sb, scope ); + if( xScopes != null ) + for( ScopeNode xscope : xScopes ) + if( !xscope.isDead() ) + scope( sb, xscope ); // Walk the Node edges nodeEdges(sb, all); // Walk the active Scope edges - for( ScopeNode scope : parser._xScopes ) - scopeEdges( sb, scope ); + if( xScopes != null ) + for( ScopeNode xscope : xScopes ) + if( !xscope.isDead() ) + scopeEdges( sb, xscope ); sb.append("}\n"); return sb.toString(); @@ -232,12 +237,13 @@ public class GraphVisualizer { /** * Finds all nodes in the graph. */ - private Collection findAll(Parser parser) { + private Collection findAll(Node stop, Node scope) { final HashMap all = new HashMap<>(); - for( Node n : Parser.START._outputs ) - walk(all, n); - for( Node n : parser._scope._inputs ) + for( Node n : stop._inputs ) walk(all, n); + if( scope != null ) + for( Node n : scope._inputs ) + walk(all, n); return all.values(); } diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index 2a6dbefd..c06ac9d0 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -48,14 +48,15 @@ public class IRPrinter { // First walk the CFG, then everything if( n.isCFG() ) { for( Node use : n._outputs ) - if( use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) + if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) postOrd(use, rpos,visit,bfs); for( Node use : n._outputs ) - if( use.isCFG() ) + if( use!=null && use.isCFG() ) postOrd(use,rpos,visit,bfs); } for( Node use : n._outputs ) - postOrd(use, rpos,visit,bfs); + if( use != null ) + postOrd(use, rpos,visit,bfs); // Post-order rpos.add(n); } diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java new file mode 100644 index 00000000..6dafd95f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -0,0 +1,204 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.BitSet; +import java.util.Random; + +/** + * The IterOptim runs after parsing. It iterates the peepholes to a fixed point + * so that no more peepholes apply. This should be linear because peepholes rarely + * (never?) increase code size. The graph should monotonically reduce in some + * dimension, which is usually size. It might also reduce in e.g. number of + * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper + * ones. + * + * The theoretical overall worklist is mindless just grabbing the next thing and + * doing it. If the graph changes, put the neighbors on the worklist. Lather, + * Rinse, Repeat until the worklist runs dry. + * + * The main issues we have to deal with: + * + *
    + *
  • Nodes have uses; replacing some set of Nodes with another requires more graph + * reworking. Not rocket science, but it can be fiddly. Its helpful to have a + * small set of graph munging utilities, and the strong invariant that the graph + * is stable and correct between peepholes. In our case `Node.subsume` does + * most of the munging, building on our prior stable Node utilities.
    • + * + *
  • Changing a Node also changes the graph "neighborhood". The neigbors need to + * be checked to see if THEY can also peephole, and so on. After any peephole + * or graph update we put a Nodes uses and defs on the worklist.
    • + * + *
  • Our strong invariant is that for all Nodes, either they are on the worklist + * OR no peephole applies. This invariant is easy to check, although expensive. + * Basically the normal "iterate peepholes to a fixed point" is linear, and this + * check is linear at each peephole step... so quadratic overall. Its a useful + * assert, but one we can disable once the overall algorithm is stable - and + * then turn it back on again when some new set of peepholes is misbehaving. + * The code for this is turned on in `IterOptim.iterate` as `assert + * progressOnList(stop);`
    • + *
+ */ +public abstract class IterPeeps { + + private static final WorkList WORK = new WorkList<>(); + + public static N add( N n ) { + return (N)WORK.push(n); + } + + public static void addAll( ArrayList ary ) { + WORK.addAll(ary); + } + + /** + * Iterate peepholes to a fixed point + */ + public static StopNode iterate(StopNode stop, boolean show) { + assert progressOnList(stop); + int cnt=0; + + Node n; + while( (n=WORK.pop()) != null ) { + if( n.isDead() ) continue; + cnt++; // Useful for debugging, searching which peephole broke things + Node x = n.peepholeOpt(); + if( x != null ) { + if( x.isDead() ) continue; + // peepholeOpt can return brand-new nodes, needing an initial type set + if( x._type==null ) x.setType(x.compute()); + // Changes require neighbors onto the worklist + if( x != n || !(x instanceof ConstantNode) ) { + // All outputs of n (changing node) not x (prior existing node). + for( Node z : n._outputs ) WORK.push(z); + // Everybody gets a free "go again" in case they didn't get + // made in their final form. + WORK.push(x); + // If the result is not self, revisit all inputs (because + // there's a new user), and replace in the graph. + if( x != n ) { + for( Node z : n. _inputs ) WORK.push(z); + n.subsume(x); + } + } + // If there are distant neighbors, move to worklist + n.moveDepsToWorklist(); + assert progressOnList(stop); // Very expensive assert + } + } + + if( show ) + System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null)); + return stop; + } + + // Visit ALL nodes and confirm the invariant: + // Either you are on the WORK worklist OR running `iter()` makes no progress. + + // This invariant ensures that no progress is missed, i.e., when the + // worklist is empty we have indeed done all that can be done. To help + // with debugging, the {@code assert} is broken out in a place where it is easy to + // stop if a change is found. + + // Also, the normal usage of `iter()` may attempt peepholes with distance + // neighbors and these should fail, but will then try to add dependencies + // {@link #Node.addDep} which is a side effect in an assert. The {@link + // #midAssert} is used to stop this side effect. + private static boolean MID_ASSERT; + public static boolean midAssert() { return MID_ASSERT; } + private static boolean progressOnList(Node stop) { + MID_ASSERT = true; + int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT; + Node changed = stop.walk( n -> { + if( WORK.on(n) ) return null; + Node m = n.peepholeOpt(); + if( m==null ) return null; + System.err.println("BREAK HERE FOR BUG"); + return m; + }); + Node.ITER_CNT = old_cnt; Node.ITER_NOP_CNT = old_nop; + MID_ASSERT = false; + return changed==null; + } + + public static void reset() { + WORK.clear(); + } + + /** + * Classic WorkList, with a fast add/remove, dup removal, random pull. + * The Node's nid is used to check membership in the worklist. + */ + public static class WorkList { + + private Node[] _es; + private int _len; + private final BitSet _on; // Bit set if Node._nid is on WorkList + private final Random _R; // For randomizing pull from the WorkList + private final long _seed; + + /* Useful stat - how many nodes are processed in the post parse iterative opt */ + private long _totalWork = 0; + + WorkList() { this(123); } + WorkList(long seed) { + _es = new Node[1]; + _len=0; + _on = new BitSet(); + _seed = seed; + _R = new Random(); + _R.setSeed(_seed); + } + + /** + * Pushes a Node on the WorkList, ensuring no duplicates + * If Node is null it will not be added. + */ + public E push( E x ) { + if( x==null ) return null; + int idx = x._nid; + if( !_on.get(idx) ) { + _on.set(idx); + if( _len==_es.length ) + _es = Arrays.copyOf(_es,_len<<1); + _es[_len++] = x; + _totalWork++; + } + return x; + } + + public void addAll( ArrayList ary ) { + for( E n : ary ) + push(n); + } + + /** + * True if Node is on the WorkList + */ + boolean on( E x ) { return _on.get(x._nid); } + + /** + * Removes a random Node from the WorkList; null if WorkList is empty + */ + E pop() { + if( _len == 0 ) return null; + int idx = _R.nextInt(_len); + E x = (E)_es[idx]; + _es[idx] = _es[--_len]; // Compress array + _on.clear(x._nid); + return x; + } + + public void clear() { + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 69796828..aabdf63a 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -69,11 +69,12 @@ public class Parser { public Parser(String source, TypeInteger arg) { Node.reset(); + IterPeeps.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); - STOP = new StopNode(); + STOP = new StopNode(source); } public Parser(String source) { @@ -108,7 +109,6 @@ public class Parser { return STOP; } - /** * Parses a block * @@ -185,11 +185,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole(); // Clone the body Scope to create the break/exit Scope which accounts for any // side effects in the predicate. The break/exit Scope will be the final @@ -203,7 +202,7 @@ public class Parser { // Parse the true side, which corresponds to loop body // Our current scope is the body Scope - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body // Merge the loop bottom into other continue statements @@ -247,7 +246,7 @@ public class Parser { return cur; // toScope is either the break scope, or a scope that was created here assert toScope._scopes.size() <= _breakScope._scopes.size(); - toScope.mergeScopes(cur); + toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -269,11 +268,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current int ndefs = _scope.nIns(); @@ -281,13 +279,13 @@ public class Parser { _xScopes.push(fScope); // For graph visualization we need all scopes // Parse the true side - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection parseStatement(); // Parse true-side ScopeNode tScope = _scope; // Parse the false side _scope = fScope; // Restore scope, then parse else block if any - ctrl(ifF); // Ctrl token is now set to ifFalse projection + ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection if (matchx("else")) { parseStatement(); fScope = _scope; @@ -324,8 +322,8 @@ public class Parser { * Dumps out the node graph * @return {@code null} */ - private Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(this)); + Node showGraph() { + System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes)); return null; } @@ -384,12 +382,23 @@ public class Parser { */ private Node parseComparison() { var lhs = parseAddition(); - if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); - if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); - if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); - if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); - if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); - if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + while( true ) { + int idx=0; boolean negate=false; + // Test for any local nodes made, and "keep" lhs during peepholes + if( false ) ; + else if( match("==") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); } + else if( match("!=") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); negate=true; } + else if( match("<=") ) { idx=2; lhs = new BoolNode.LE(lhs, null); } + else if( match("<" ) ) { idx=2; lhs = new BoolNode.LT(lhs, null); } + else if( match(">=") ) { idx=1; lhs = new BoolNode.LE(null, lhs); } + else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); } + else break; + // Peepholes can fire, but lhs is already "hooked", kept alive + lhs.setDef(idx,parseAddition()); + lhs = lhs.peephole(); + if( negate ) // Extra negate for != + lhs = new NotNode(lhs).peephole(); + } return lhs; } @@ -402,9 +411,15 @@ public class Parser { * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { - var lhs = parseMultiplication(); - if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); - if (match("-")) return new SubNode(lhs, parseAddition()).peephole(); + Node lhs = parseMultiplication(); + while( true ) { + if( false ) ; + else if( match("+") ) lhs = new AddNode(lhs,null); + else if( match("-") ) lhs = new SubNode(lhs,null); + else break; + lhs.setDef(2,parseMultiplication()); + lhs = lhs.peephole(); + } return lhs; } @@ -418,8 +433,14 @@ public class Parser { */ private Node parseMultiplication() { var lhs = parseUnary(); - if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); - if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); + while( true ) { + if( false ) ; + else if( match("*") ) lhs = new MulNode(lhs,null); + else if( match("/") ) lhs = new DivNode(lhs,null); + else break; + lhs.setDef(2,parseUnary()); + lhs = lhs.peephole(); + } return lhs; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 84a368fd..4e30bb55 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -25,21 +25,16 @@ public class AddNode extends Node { in(2)._type instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()+i1.value()); - return i0.meet(i1); } - return Type.BOTTOM; + return in(1)._type.meet(in(2)._type); } @Override public Node idealize () { Node lhs = in(1); Node rhs = in(2); - Type t1 = lhs._type; Type t2 = rhs._type; - // Already handled by peephole constant folding - assert !(t1.isConstant() && t2.isConstant()); - // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) if( t2 instanceof TypeInteger i && i.value()==0 ) @@ -55,6 +50,10 @@ public class AddNode extends Node { if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) return swap12(); + // x+(-y) becomes x-y + if( rhs instanceof MinusNode minus ) + return new SubNode(lhs,minus.in(1)); + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) // Do we have x + (y + z) ? @@ -66,7 +65,7 @@ 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) ) // Rotate; look for (add (phi cons) con/(phi cons)) - return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true); + return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true); // Now we only see (add add non) @@ -77,7 +76,11 @@ public class AddNode extends Node { // Do we have (x + con1) + con2? // Replace with (x + (con1+con2) which then fold the constants - if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + // lhs.in(2) is con1 here + // If lhs.in(2) is not a constant, we add ourselves as a dependency + // because if it later became a constant then we could make this + // transformation. + if( lhs.in(2).addDep(this)._type.isConstant() && rhs._type.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); @@ -87,11 +90,11 @@ public class AddNode extends Node { Node phicon = phiCon(this,true); if( phicon!=null ) return phicon; - // Now we sort along the spline via rotates, to gather similar things together. + // Now we sort along the spine via rotates, to gather similar things together. // Do we rotate (x + y) + z // into (x + z) + y ? - if( spline_cmp(lhs.in(2),rhs) ) + if( spine_cmp(lhs.in(2),rhs,this) ) return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); return null; @@ -104,16 +107,16 @@ public class AddNode extends Node { Node lhs = op.in(1); Node rhs = op.in(2); // LHS is either a Phi of constants, or another op with Phi of constants - PhiNode lphi = pcon(lhs); + PhiNode lphi = pcon(lhs,op); if( rotate && lphi==null && lhs.nIns() > 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 + lphi = pcon(lhs.in(2),op); // 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 ) + if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==null ) return null; // If both are Phis, must be same Region @@ -134,21 +137,31 @@ public class AddNode extends Node { return lhs==lphi ? phi : op.copy(lhs.in(1),phi); } - static PhiNode pcon(Node op) { - return op instanceof PhiNode phi && phi.allCons() ? phi : null; + /** + * Tests if the op is a phi and has all constant inputs. + * If not, returns null. + * If op is a phi, but its inputs are not all constants, then dep is added as + * a dependency to the phi's non-const input, because if later the input turn into a constant + * dep can make progress. + */ + static PhiNode pcon(Node op, Node dep) { + return op instanceof PhiNode phi && phi.allCons(dep) ? phi : null; } - // Compare two off-spline nodes and decide what order they should be in. + // Compare two off-spine nodes and decide what order they should be in. // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? // Generally constants always go right, then Phi-of-constants, then muls, then others. // Ties with in a category sort by node ID. // TRUE if swapping hi and lo. - static boolean spline_cmp( Node hi, Node lo ) { + static boolean spine_cmp( Node hi, Node lo, Node dep ) { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; - if( lo instanceof PhiNode && lo.allCons() ) return false; - if( hi instanceof PhiNode && hi.allCons() ) return true ; + if( lo instanceof PhiNode lphi && lphi.region()._type==Type.XCONTROL ) return false; + if( hi instanceof PhiNode hphi && hphi.region()._type==Type.XCONTROL ) return false; + + if( lo instanceof PhiNode && lo.allCons(dep) ) return false; + if( hi instanceof PhiNode && hi.allCons(dep) ) return true ; if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 0c32d50d..d3fcec95 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -32,9 +32,8 @@ abstract public class BoolNode extends Node { in(2)._type instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); - return i0.meet(i1); } - return Type.BOTTOM; + return in(1)._type.meet(in(2)._type); } abstract boolean doOp(long lhs, long rhs); diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 13006bfb..9e45198c 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -8,7 +8,7 @@ import java.util.BitSet; /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer - * value. As we add other types of constants, we will refactor how we represent + * value. As we add other types of constants, we will refactor how we represent * Constants. *

* Constants have no semantic inputs. However, we set Start as an input to @@ -25,7 +25,7 @@ public class ConstantNode extends Node { } @Override - public String label() { return ""+_con; } + public String label() { return "#"+_con; } @Override public String uniqueName() { return "Con_" + _nid; } @@ -42,4 +42,17 @@ public class ConstantNode extends Node { @Override public Node idealize() { return null; } + + @Override + boolean eq(Node n) { + ConstantNode con = (ConstantNode)n; // Contract + return _con==con._con; + } + + @Override + int hash() { return _con.hashCode(); } + + // Dead control is its own idom root + Node idom() { return null; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 7207fd48..08ce70b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -27,9 +27,8 @@ public class DivNode extends Node { return i1.value() == 0 ? TypeInteger.ZERO : TypeInteger.constant(i0.value()/i1.value()); - return i0.meet(i1); } - return Type.BOTTOM; + return in(1)._type.meet(in(2)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 23a8fafc..460dce51 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -32,27 +32,30 @@ public class IfNode extends MultiNode { // If the If node is not reachable then neither is any following Proj if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) return TypeTuple.IF_NEITHER; + Node pred = pred(); + Type t = pred._type; + // High types mean NEITHER side is reachable. + // Wait until the type falls to decide which way to go. + if( t == Type.TOP || t == TypeInteger.TOP ) + return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable - if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { - if (ti.value() == 0) return TypeTuple.IF_FALSE; - else return TypeTuple.IF_TRUE; - } - - // Hunt up the immediate dominator tree. If we find an identical if - // test on either the true or false branch, then this test matches. - for( Node dom = idom(), prior=this; dom!=null; prior=dom, dom = dom.idom() ) - if( dom instanceof IfNode iff && iff.pred()==pred() ) - return prior instanceof ProjNode proj - // Repeated test, dominated on one side. Test result is the same. - ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) - : dom._type; // Repeated test not dominated on one side + if (t instanceof TypeInteger ti && ti.isConstant()) + return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; } @Override public Node idealize() { + // Hunt up the immediate dominator tree. If we find an identical if + // test on either the true or false branch, that side wins. + if( !pred()._type.isHighOrConst() ) + for( Node dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) + if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) { + setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); + return this; + } return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 3d944fd4..dd092c9e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -22,7 +22,7 @@ public class MinusNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0) return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return Type.BOTTOM; + return TypeInteger.TOP.meet(in(1)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 2e701a4e..7e9f88a2 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -25,9 +25,8 @@ public class MulNode extends Node { in(2)._type instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()*i1.value()); - return i0.meet(i1); } - return Type.BOTTOM; + return in(1)._type.meet(in(2)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 7ba1aa19..2743bd19 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -4,4 +4,11 @@ public abstract class MultiNode extends Node { public MultiNode(Node... inputs) { super(inputs); } + // Find a projection by index + ProjNode proj( int idx ) { + for( Node out : _outputs ) + if( out instanceof ProjNode prj && prj._idx==idx ) + return prj; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 2d6d5ad5..5eb9c076 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,10 +1,12 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IRPrinter; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; +import java.util.function.Function; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -63,6 +65,7 @@ public abstract class Node { * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; + public static int UID() { return UNIQUE_ID; } protected Node(Node... inputs) { _nid = UNIQUE_ID++; // allocate unique dense ID @@ -105,7 +108,7 @@ public abstract class Node { // This is the common print: check for repeats, check for DEAD and print // "DEAD" else call the per-Node print1. final StringBuilder _print0(StringBuilder sb, BitSet visited) { - if (visited.get(_nid)) + if (visited.get(_nid) && !(this instanceof ConstantNode) ) return sb.append(label()); visited.set(_nid); return isDead() @@ -131,7 +134,7 @@ public abstract class Node { sb.append(" "); sb.append(" [[ "); for( Node use : _outputs ) - sb.append("%4d ".formatted(use._nid)); + sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); int lim = 5 - Math.max(_inputs.size(),3); for( int i = _outputs.size(); iuse edge // This needs to happen before removing the old node's def->use edge as // the new_def might get killed if the old node kills it recursively. @@ -198,13 +203,17 @@ public abstract class Node { // 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) { + // Phi, but not for every Node. If the def goes dead, it is recursively + // killed, which may include 'this' Node. + Node delDef(int idx) { + unlock(); 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 + old_def.moveDepsToWorklist(); Utils.del(_inputs, idx); + return this; } /** @@ -215,6 +224,7 @@ public abstract class Node { * @return new_def for flow coding */ Node addDef(Node new_def) { + unlock(); // Add use->def edge _inputs.add(new_def); // If new def is not null, add the corresponding def->use edge @@ -237,6 +247,7 @@ public abstract class Node { // Shortcut for "popping" n nodes. A "pop" is basically a // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { + unlock(); for( int i=0; iuses, by setting all of its defs - * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #popN}. + * to null. This may recursively kill more Nodes, and is basically dead + * code elimination. */ public void kill( ) { + unlock(); assert isUnused(); // Has no uses, so it is dead - popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead + while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes + Node old_def = _inputs.removeLast(); + if( old_def != null ) { + IterPeeps.add(old_def);// Revisit neighbor because removed use + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + } + } assert isDead(); // Really dead now } // Mostly used for asserts and printing. - boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + public boolean isDead() { return isUnused() && nIns()==0 && _type==null; } // Shortcuts to stop DCE mid-parse // Add bogus null use to keep node alive @@ -268,10 +287,11 @@ public abstract class Node { // Replace self with nnn in the graph, making 'this' go dead - void subsume( Node nnn ) { + public void subsume( Node nnn ) { assert nnn!=this; while( nOuts() > 0 ) { Node n = _outputs.removeLast(); + n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); nnn.addUse(n); @@ -288,6 +308,19 @@ public abstract class Node { */ public static boolean _disablePeephole = false; + /** + * Try to peephole at this node and return a better replacement Node. + * Always returns some not-null Node (often this). + */ + public final Node peephole( ) { + if (_disablePeephole) { + _type = compute(); + return this; // Peephole optimizations turned off + } + Node n = peepholeOpt(); + return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress + } + /** * Try to peephole at this node and return a better replacement Node if * possible. We compute a {@link Type} and then check and replace: @@ -301,29 +334,45 @@ public abstract class Node { * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing * math constants, remove algebraic identities and generally simplify the * code. + * + * Unlike peephole above, this explicitly returns null for no-change, or not-null + * for a better replacement (which can be this). * */ - public final Node peephole( ) { + public final Node peepholeOpt( ) { + ITER_CNT++; // Compute initial or improved Type - Type type = _type = compute(); - - if (_disablePeephole) - return this; // Peephole optimizations turned off + Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if (!(this instanceof ConstantNode) && type.isConstant()) - return deadCodeElim(new ConstantNode(type).peephole()); - - // Future chapter: Global Value Numbering goes here + if (!(this instanceof ConstantNode) && _type.isHighOrConst() ) + return new ConstantNode(_type).peepholeOpt(); + + // Global Value Numbering + if( _hash==0 ) { + Node n = GVN.get(this); // Will set _hash as a side effect + if( n==null ) + GVN.put(this,this); // Put in table now + else { + // Because of random worklist ordering, the two equal nodes + // might have different types. Because of monotonicity, both + // types are valid. To preserve monotonicity, the resulting + // shared Node has to have the best of both types. + n.setType(n._type.join(_type)); + _hash = 0; // Clear, since it never went in the table + return deadCodeElim(n);// Return previous; does Common Subexpression Elimination + } + } // Ask each node for a better replacement Node n = idealize(); if( n != null ) // Something changed - // Recursively optimize - return deadCodeElim(n.peephole()); + return n; // Report progress - return this; // No progress + if( old==_type ) ITER_NOP_CNT++; + return old==_type ? null : this; // Report progress } + public static int ITER_CNT, ITER_NOP_CNT; // m is the new Node, self is the old. // Return 'm', which may have zero uses but is alive nonetheless. @@ -353,13 +402,26 @@ public abstract class Node { * theory. Much later on, this will become important and allow us to do * many fancy complex optimizations trivially... because theory. *

- * compute() needs to be stand-alone, and cannot recursively call compute - * on its inputs programs are cyclic (have loops!) and this will just + * {@link #compute()} needs to be stand-alone, and cannot recursively call compute + * on its inputs, because programs are cyclic (have loops!) and this will just * infinitely recurse until stack overflow. Instead, compute typically * computes a new type from the {@link #_type} field of its inputs. */ public abstract Type compute(); + // Set the type. Assert monotonic progress. + // If changing, add users to worklist. + public Type setType(Type type) { + Type old = _type; + assert old==null || type.isa(old); // Since _type not set, can just re-run this in assert in the debugger + if( old == type ) return old; + _type = type; // Set _type late for easier assert debugging + IterPeeps.addAll(_outputs); + moveDepsToWorklist(); + return old; + } + + /** * This function rewrites the current Node into a more "idealized" form. * This is the bulk of our peephole rewrite rules, and we use this to @@ -399,32 +461,127 @@ public abstract class Node { * call peephole. *

* Since idealize calls peephole and peephole calls idealize, you must be - * careful that all idealizations are monotonic: all transforms remove - * some feature, so that the set of available transforms always shrinks. - * If you don't, you risk an infinite peephole loop! + * careful that all idealizations are monotonic: all transforms + * remove some feature, so that the set of available transforms always + * shrinks. If you don't, you risk an infinite peephole loop! * * @return Either a new or changed node, or null for no changes. */ public abstract Node idealize(); + // Some of the peephole rules get complex, and search further afield than + // just the nearest neighbor. These peepholes can fail the pattern match + // on a node some distance away, and if that node ever changes we should + // retry the peephole. Track a set of Nodes dependent on `this`, and + // revisit them if `this` changes. + ArrayList _deps; + + /** + * Add a node to the list o dependencies. Only add it if its not + * an input or output of this node, that is, it is at least one step + * away. The node being added must benefit from this node being peepholed. + */ + Node addDep( Node dep ) { + // Running peepholes during the big assert cannot have side effects + // like adding dependencies. + if( IterPeeps.midAssert() ) return this; + if( _deps==null ) _deps = new ArrayList<>(); + if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list + if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors + if( Utils.find(_outputs,dep)!= -1 ) return this; + _deps.add(dep); + return this; + } + + // Move the dependents onto a worklist, and clear for future dependents. + public void moveDepsToWorklist( ) { + if( _deps==null ) return; + IterPeeps.addAll(_deps); + _deps.clear(); + } + + + // Global Value Numbering. Hash over opcode and inputs; hits in this table + // are structurally equal. + public static final HashMap GVN = new HashMap<>(); + + // Two nodes are equal if they have the same inputs and the same "opcode" + // which means the same Java class, plus same internal parts. + @Override public final boolean equals( Object o ) { + if( o==this ) return true; + if( o.getClass() != getClass() ) return false; + Node n = (Node)o; + int len = _inputs.size(); + if( len != n._inputs.size() ) return false; + for( int i=0; i>13) ^ n._nid; + if( hash==0 ) hash = 0xDEADBEEF; // Bad hash, so use some junky thing + return (_hash=hash); + } + // Subclasses add extra hash info (such as ConstantNodes constant) + int hash() { return 0; } + + // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. Node swap12() { + unlock(); // Hash is order dependent Node tmp = in(1); _inputs.set(1,in(2)); _inputs.set(2,tmp); return this; } - // does this node contain all constants? - // Ignores in(0), as is usually control. - boolean allCons() { + /** + * Does this node contain all constants? + * Ignores in(0), as is usually control. + * In an input is not a constant, we add dep as + * a dependency to it, because dep can make progress + * if the input becomes a constant later. + * It is sufficient for one of the non-const + * inputs to have the dependency so we don't bother + * checking the rest. + */ + boolean allCons(Node dep) { for( int i=1; i E walk( Function pred ) { + assert WVISIT.isEmpty(); + E rez = _walk(pred); + WVISIT.clear(); + return rez; + } + + private E _walk( Function pred ) { + if( WVISIT.get(_nid) ) return null; // Been there, done that + WVISIT.set(_nid); + E x = pred.apply(this); + if( x != null ) return x; + for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; + for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; + return null; } /** * Debugging utility to find a Node by index */ - public Node find(int nid) { return _find(new BitSet(),nid); } - private Node _find(BitSet visit, int nid) { - if( _nid==nid ) return this; - if( visit.get(_nid) ) return null; - visit.set(_nid); - for( Node def : _inputs ) - if( def!=null ) { - Node rez = def._find(visit,nid); - if( rez != null ) return rez; - } - for( Node use : _outputs ) { - Node rez = use._find(visit,nid); - if( rez != null ) return rez; - } - return null; + public Node find(int nid) { + return walk( n -> n._nid==nid ? n : null ); } } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index 39df410d..7a520fec 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -22,7 +22,7 @@ public class NotNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; - return Type.BOTTOM; + return TypeInteger.TOP.meet(in(1)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index c7b5b357..ec4c6ad3 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -16,7 +16,7 @@ public class PhiNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( region().inProgress() ) + if( !(region() instanceof RegionNode r) || r.inProgress() ) sb.append("Z"); sb.append("Phi("); for( Node in : _inputs ) { @@ -29,23 +29,29 @@ public class PhiNode extends Node { return sb; } - RegionNode region() { return (RegionNode)in(0); } + Node region() { return in(0); } @Override public boolean isMultiTail() { return true; } @Override public Type compute() { - if( !(region() instanceof RegionNode r) || r.inProgress() ) - return Type.BOTTOM; + if( !(region() instanceof RegionNode r) ) + return region()._type==Type.XCONTROL ? Type.TOP : _type; + if( r.inProgress() ) return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) - t = t.meet(in(i)._type); + // If the region's control input is live, add this as a dependency + // to the control because we can be peeped should it become dead. + if( r.in(i).addDep(this)._type != Type.XCONTROL && in(i) != this ) + t = t.meet(in(i)._type); return t; } @Override public Node idealize() { - if( !(region() instanceof RegionNode r ) || r.inProgress() ) - return null; + if( !(region() instanceof RegionNode r ) ) + return in(1); // Input has collapse to e.g. starting control. + if( r.inProgress() || r.nIns()<=1 ) + return null; // Input is in-progress // If we have only a single unique input, become it. Node live = singleUniqueInput(); @@ -84,11 +90,13 @@ public class PhiNode extends Node { * If only single unique input, return it */ private Node singleUniqueInput() { + if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL ) + return null; // Dead entry loops just ignore and let the loop collapse Node live = null; for( int i=1; i1 && in(nIns()-1) == null; + } + + // Never equal if inProgress + @Override boolean eq( Node n ) { + return !inProgress(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 312058b9..922a3649 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -34,7 +34,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return new TypeTuple(ctrl()._type,expr()._type); + return TypeTuple.make(ctrl()._type,expr()._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index e5d03d93..3abea54d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -212,6 +213,8 @@ public class ScopeNode extends Node { if( in(i) instanceof PhiNode phi ) { // Do an eager useless-phi removal Node in = phi.peephole(); + IterPeeps.addAll(phi._outputs); + phi.moveDepsToWorklist(); if( in != phi ) { phi.subsume(in); setDef(i,in); // Set the update back into Scope diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 01f1485a..e399138b 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -18,7 +18,7 @@ public class StartNode extends MultiNode { public StartNode(Type[] args) { super(); - _args = new TypeTuple(args); + _args = TypeTuple.make(args); _type = _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 417790d9..602feffc 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,12 +1,17 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.IterPeeps; import java.util.BitSet; public class StopNode extends Node { - public StopNode(Node... inputs) { - super(inputs); + + public final String _src; + + public StopNode(String src) { + super(); + _src = src; } @Override @@ -50,4 +55,6 @@ public class StopNode extends Node { return addDef(node); } + public StopNode iterate( ) { return IterPeeps.iterate(this,false); } + public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ); } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index af66b950..f661be14 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -29,9 +29,8 @@ public class SubNode extends Node { in(2)._type instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); - return i0.meet(i1); } - return Type.BOTTOM; + return in(1)._type.meet(in(2)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 2f0e6171..d0265e83 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -1,5 +1,8 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.Utils; + +import java.util.HashMap; /** * These types are part of a Monotone Analysis Framework, @@ -18,6 +21,7 @@ package com.seaofnodes.simple.type; */ public class Type { + static final HashMap INTERN = new HashMap<>(); // ---------------------------------------------------------- // Simple types are implemented fully here. "Simple" means: the code and @@ -36,15 +40,53 @@ public class Type { 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 static final Type BOTTOM = new Type( TBOT ).intern(); // ALL + public static final Type TOP = new Type( TTOP ).intern(); // ANY + public static final Type CONTROL = new Type( TCTRL ).intern(); // Ctrl + public static final Type XCONTROL = new Type( TXCTRL ).intern(); // ~Ctrl + + // Is high or on the lattice centerline. + public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; } - public boolean isConstant() { return _type == TTOP || _type == TXCTRL; } + // Strict constant values, things on the lattice centerline. + // Excludes both high and low values + public boolean isConstant() { return false; } public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} + // ---------------------------------------------------------- + + // Factory method which interns "this" + protected T intern() { + T nnn = (T)INTERN.get(this); + if( nnn==null ) + INTERN.put(nnn=(T)this,this); + return nnn; + } + + private int _hash; // Hash cache; not-zero when set. + @Override + public final int hashCode() { + if( _hash!=0 ) return _hash; + _hash = hash(); + if( _hash==0 ) _hash = 0xDEADBEEF; // Bad hash from subclass; use some junk thing + return _hash; + } + // Override in subclasses + int hash() { return _type; } + + @Override + public final boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof Type t)) return false; + if( _type != t._type ) return false; + return eq(t); + } + // Overridden in subclasses; subclass can assume "this!=t" and java classes are same + boolean eq(Type t) { return true; } + + + // ---------------------------------------------------------- public final Type meet(Type t) { // Shortcut for the self case if( t == this ) return this; @@ -53,7 +95,7 @@ public class Type { // 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 + return xmeet(t); // Mixing 2 unrelated types } // Compute meet right now. Overridden in subclasses. @@ -70,6 +112,28 @@ public class Type { return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; } + // True if this "isa" t; e.g. 17 isa TypeInteger.BOT + public boolean isa( Type t ) { return meet(t)==t; } + + // ---------------------------------------------------------- + // Our lattice is defined with a MEET and a DUAL. + // JOIN is dual of meet of both duals. + public final Type join(Type t) { + if( this==t ) return this; + return dual().meet(t.dual()).dual(); + } + + public Type dual() { + return switch( _type ) { + case TBOT -> TOP; + case TTOP -> BOTTOM; + case TCTRL -> XCONTROL; + case TXCTRL -> CONTROL; + default -> throw Utils.TODO(); // Should not reach here + }; + } + + // ---------------------------------------------------------- @Override public final String toString() { return _print(new StringBuilder()).toString(); diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index b30e21d8..ba045603 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -5,36 +5,39 @@ package com.seaofnodes.simple.type; */ public class TypeInteger extends Type { - public final static TypeInteger TOP = new TypeInteger(false, 0); - public final static TypeInteger BOT = new TypeInteger(false, 1); - public final static TypeInteger ZERO= new TypeInteger(true, 0); + public final static TypeInteger TOP = make(false, 0); + public final static TypeInteger BOT = make(false, 1); + public final static TypeInteger ZERO= make(true , 0); - private final boolean _is_con; + public final boolean _is_con; /** * The constant value or - * if not constant then 0=bottom, 1=top. + * if not constant then 1=bottom, 0=top. */ - private final long _con; + public final long _con; - public TypeInteger(boolean is_con, long con) { + private TypeInteger(boolean is_con, long con) { super(TINT); _is_con = is_con; _con = con; } + public static TypeInteger make(boolean is_con, long con) { + return new TypeInteger(is_con,con).intern(); + } - public static TypeInteger constant(long con) { return new TypeInteger(true, con); } - - public boolean isTop() { return !_is_con && _con==0; } - public boolean isBot() { return !_is_con && _con==1; } + public static TypeInteger constant(long con) { return make(true, con); } @Override public StringBuilder _print(StringBuilder sb) { - if (isTop()) return sb.append("IntTop"); - if (isBot()) return sb.append("IntBot"); + if( this==TOP ) return sb.append("IntTop"); + if( this==BOT ) return sb.append("IntBot"); return sb.append(_con); } + @Override + public boolean isHighOrConst() { return _is_con || _con==0; } + @Override public boolean isConstant() { return _is_con; } @@ -42,22 +45,30 @@ public class TypeInteger extends Type { @Override public Type xmeet(Type other) { - if( this==other ) return this; - if (!(other instanceof TypeInteger i)) return super.meet(other); + // Invariant from caller: 'this' != 'other' and same class (TypeInteger) + TypeInteger i = (TypeInteger)other; // Contract // BOT wins - if ( isBot() ) return this; - if ( i.isBot() ) return i ; + if ( this==BOT ) return this; + if ( i ==BOT ) return i ; // TOP loses - if ( i.isTop() ) return this; - if ( isTop() ) return i ; - assert isConstant() && i.isConstant(); - return _con==i._con ? this : TypeInteger.BOT; + if ( i ==TOP ) return this; + if ( this==TOP ) return i ; + // Since both are constants, and are never equals (contract) unequals + // constants fall to bottom + return BOT; } @Override - public boolean equals( Object o ) { - if( o==this ) return true; - if( !(o instanceof TypeInteger i) ) return false; + public Type dual() { + if( isConstant() ) return this; // Constants are a self-dual + return _con==0 ? BOT : TOP; + } + + @Override + int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); } + @Override + public boolean eq( Type t ) { + TypeInteger i = (TypeInteger)t; // Contract return _con==i._con && _is_con==i._is_con; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 0f8b95bd..e82ea00b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -4,14 +4,24 @@ public class TypeTuple extends Type { public final Type[] _types; - public TypeTuple(Type... _types) { - super(TTUPLE); - this._types = _types; - } + private TypeTuple(Type[] types) { super(TTUPLE); _types = types; } + public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); } @Override public Type xmeet(Type other) { - throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); + TypeTuple tt = (TypeTuple)other; // contract from xmeet + assert _types.length == tt._types.length; + Type[] ts = new Type[_types.length]; + for( int i=0; i<_types.length; i++ ) + ts[i] = _types[i].meet(tt._types[i]); + return make(ts); + } + + @Override public Type dual() { + Type[] ts = new Type[_types.length]; + for( int i=0; i<_types.length; i++ ) + ts[i] = _types[i].dual(); + return make(ts); } @Override @@ -24,9 +34,27 @@ public class TypeTuple extends Type { return sb; } - 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}); + public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL}); + public static final TypeTuple IF_NEITHER = make(new Type[]{Type.XCONTROL,Type.XCONTROL}); + public static final TypeTuple IF_TRUE = make(new Type[]{Type. CONTROL,Type.XCONTROL}); + public static final TypeTuple IF_FALSE = make(new Type[]{Type.XCONTROL,Type. CONTROL}); + + @Override + int hash() { + int sum = 0; + for( Type type : _types ) sum ^= type.hashCode(); + return sum; + } + + @Override + boolean eq( Type t ) { + TypeTuple tt = (TypeTuple)t; // Contract + if( _types.length != tt._types.length ) return false; + for( int i=0; i<_types.length; i++ ) + if( _types[i]!=tt._types[i] ) + return false; + return true; + } + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 47cee096..75ee0b70 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -13,7 +13,7 @@ public class Chapter02Test { Parser parser = new Parser("return 1+2*3+-5;"); Node._disablePeephole = true; // disable peephole so we can observe full graph StopNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); + assertEquals("return ((1+(2*3))+(-5));", ret.print()); Node._disablePeephole = false; } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index c76df903..a243beb1 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -40,7 +40,7 @@ public class Chapter03Test { @Test public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); "); + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 68d379a1..6ad3af15 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -21,7 +21,7 @@ else { } return a;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } @@ -36,7 +36,7 @@ if (arg == 1) { c = 4; } return c;""", TypeInteger.BOT); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return Phi(Region16,4,3);", ret.toString()); } @@ -64,7 +64,7 @@ if( arg==1 ) else b=a+1; return a+b;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); } @@ -79,7 +79,7 @@ if( arg==1 ) else a=b+1; return a+b;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @@ -99,7 +99,7 @@ else a=5; return a; """, TypeInteger.BOT); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); } @@ -129,7 +129,7 @@ if( arg==1 ) a=arg==3; } return a;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); } @@ -169,6 +169,7 @@ return a;"""); } } + @Test public void testBadNum() { try { diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index b858b83e..054e96e8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -15,7 +15,7 @@ public class Chapter06Test { if( true ) return 2; return 1; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -29,7 +29,7 @@ if (arg) a = 2; return (arg < a) < 3; """); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse().iterate(); assertEquals("return ((arg--arg) arg=arg+1; return 0;"); - StopNode stop = parser.parse(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); } @Test @@ -177,7 +167,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return arg;", stop.toString()); } @@ -194,7 +184,7 @@ while(arg < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -210,9 +200,9 @@ while(1) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof RegionNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java new file mode 100644 index 00000000..5567299a --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -0,0 +1,300 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.BeforeClass; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter09Test { + + @Test + @Ignore + public void testJig() { + Parser parser = new Parser(""" +int v0=0; +arg=0; +while(v0) { + while(1) if(arg*arg*0==0) {} + while(0) {} + arg=1; +} +return 0; + """); + StopNode stop = parser.parse().iterate(); + } + + @Test + public void testGVN1() { + Parser parser = new Parser( + """ +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + """); + StopNode stop = parser.parse(); + assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString()); + Assert.assertEquals(2, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(23, GraphEvaluator.evaluate(stop, 11)); + } + + @Test + public void testGVN2() { + Parser parser = new Parser( + """ +return arg*arg-arg*arg; + """); + StopNode stop = parser.parse(); + assertEquals("return 0;", stop.toString()); + Assert.assertEquals(0, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist1() { + Parser parser = new Parser( + """ +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop7,arg,(Phi_arg+2));", stop.toString()); + Assert.assertEquals(11, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist2() { + Parser parser = new Parser( + """ +int cond = 0; +int one = 1; +while (arg < 10) { + if (cond) one = 2; + arg = arg + one*3 + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop8,arg,(Phi_arg+4));", stop.toString()); + Assert.assertEquals(13, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist3() { + Parser parser = new Parser( + """ +int v1 = 0; +int v2 = 0; +int v3 = 0; +int v4 = 0; +int v5 = 0; +int v6 = 0; +int v7 = 0; +int v8 = 0; +while (arg) { + if (v1) v2 = 1; + if (v2) v3 = 1; + if (v3) v4 = 1; + if (v4) v5 = 1; + if (v5) v6 = 1; + if (v6) v7 = 1; + if (v7) v8 = 1; + arg = arg + v8 + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop14,arg,(Phi_arg+1));", stop.toString()); + } + + @Test + public void testRegionPeepBug() { + Parser parser = new Parser( + """ +int v0=0; +int v1=0; +while(v1+arg) { + arg=0; + int v2=v0; + while(arg+1) {} + v0=1; + v1=v2; +} + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testWhile0() { + Parser parser = new Parser("while(0) continue; if(0) arg=0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testWhile1() { + Parser parser = new Parser(""" +if(0) while(0) { + int arg=arg; + while(0) {} +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testPrecedence() { + Parser parser = new Parser("return 3-1+2;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + } + + @Test + public void testSwap2() { + Parser parser = new Parser("return 1+(1+1);"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3;", stop.toString()); + } + + + @Test + public void testFuzz0() { + Parser parser = new Parser(""" +int one = 1; +int a = 0; +int zero = 0; +while(arg) { + a = -(one + a + 2); + arg = arg + 1; + one = one + zero; +} +return a; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop9,0,(-(Phi_a+3)));", stop.toString()); + } + + @Test + public void testFuzz1() { + Parser parser = new Parser(""" +while(1) {} +while(arg) break; +while(arg) arg=0; +arg=0; +int v0=0!=0<-0; +return -0+0+0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testFuzz2() { + Parser parser = new Parser("return 0+-0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testFuzz3() { + Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz4() { + Parser parser = new Parser(""" +while(1) { + arg=0<=0; + if(1<0) while(arg==-0) arg=arg-arg; +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz5() { + Parser parser = new Parser(""" +{ + int v0=0; + while(1) + int v1=0--0; + while(v0) + break; + while(-v0) { + while(0+0+v0) continue; + break; + } + if(-0!=-0+0+v0) while(0+0+0+0) + break; +} +return 0!=0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz6() { + Parser parser = new Parser(""" +int v0=0; +while(0==1) while(v0) + v0=1+v0; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz7() { + Parser parser = new Parser(""" +while(1) {} +int v0=0; +while(v0) + {} +int v1=0; +while(1) + v1=1; +return v1+v0; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz8() { + Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop6,arg,(Phi_arg-1));", stop.toString()); + } + + @Test + public void testMeet() { + Type t1 = Type.TOP; + Type t2 = TypeInteger.TOP; + Assert.assertEquals(TypeInteger.TOP, t1.meet(t2)); + Assert.assertEquals(TypeInteger.TOP, t2.meet(t1)); + t1 = Type.BOTTOM; + t2 = TypeInteger.BOT; + Assert.assertEquals(Type.BOTTOM, t1.meet(t2)); + Assert.assertEquals(Type.BOTTOM, t2.meet(t1)); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 82a6a472..bb3bec1c 100644 --- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.fuzzer.Fuzzer; -import org.junit.Ignore; import org.junit.Test; +import org.junit.Ignore; import static org.junit.Assert.assertTrue; @@ -18,9 +18,18 @@ public class FuzzerWrap { @Ignore public void fuzzPeeps() { var fuzzer = new Fuzzer(); - for (int i=0; i<100000; i++) + for (int i=0; i<1000000; i++) fuzzer.fuzzPeeps(i); assertTrue(fuzzer.noExceptions()); } + + @Test + @Ignore + public void fuzzPeepTiming() { + var fuzzer = new Fuzzer(); + int max_nid=0; + for (int i=0; i<1000000; i++) + max_nid = fuzzer.fuzzPeepTiming(i, max_nid); + } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 5fcd8764..936fb41e 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.GraphEvaluator; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import java.util.ArrayList; @@ -107,6 +109,45 @@ public class Fuzzer { } } + /** + * Run one test with the given seed, and check for peephole counts. + * @param seed The seed to use for generating this test case + */ + public int fuzzPeepTiming(long seed, int max_nids) { + var rand = new Random(seed); + var sb = new StringBuilder(); + new ScriptGenerator(rand, sb, true).genProgram(); + try { + var parser = new Parser(sb.toString()); + + var stop = parser.parse(); + int parse_peeps= Node.ITER_CNT; + int parse_nops = Node.ITER_NOP_CNT; + double parse_nop_ratio = (double)parse_nops/parse_peeps; + int nids = Node.UID(); + if( nids <= max_nids ) return max_nids; + + double parse_peeps_per_node = (double)parse_peeps/nids; + + stop.iterate(); + int iter_peeps= Node.ITER_CNT; + int iter_nops = Node.ITER_NOP_CNT; + double iter_nop_ratio = (double)iter_nops/iter_peeps; + double iter_peeps_per_node = (double)iter_peeps/nids; + + System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n", + seed, + parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node, + iter_peeps , iter_nops, iter_nop_ratio, iter_peeps_per_node); + return nids; + } catch (Throwable e) { + // ignore exceptions, let the normal fullPeeps catch and reduce, + // we're interested in valid program optimizations + } + return max_nids; + } + + /** * Run one test with the given seed. * @param seed The seed to use for generating this test case @@ -118,6 +159,7 @@ public class Fuzzer { check(sb.toString(), valid); } + /** * Check that no exceptions happened. * @return true if no exception happened diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index 37a57e11..f13a51e1 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,14 +1,78 @@ package com.seaofnodes.simple.fuzzer; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; +import java.io.OutputStream; +import java.io.PrintStream; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.reflect.Field; +import java.util.BitSet; + /** * Some utilities for the fuzzer. */ class FuzzerUtils { + /** + * Get the value of a private field + */ + @SuppressWarnings("unchecked") + public static T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException { + return (T) (obj instanceof Class clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj)); + } + + /** + * Get access to a private field + */ + public static Field getField(Class clz, String name) throws NoSuchFieldException { + var field = clz.getDeclaredField(name); + try { + field.setAccessible(true); + } catch (Throwable e) { + // Intentionally left empty + } + return field; + } + + /** + * Try to rethrow an exception or create a runtime exception and throw it. + */ + public static RuntimeException rethrow(Throwable e) { + if (e instanceof RuntimeException re) return re; + if (e instanceof Error er) throw er; + return new RuntimeException(e); + } + + /** + * Copy of Node.WVISIST + * Used to clear as exceptions might happen in the walk and left this bitset not cleared + */ + private static final BitSet NodeWalkVisit; + + /** + * Write access to Iterate.MID_ASSERT + * Exception could happen mid assert and left this at true. Used to reset to false prior to parsing. + */ + private static final MethodHandle set_MID_ASSERT; + + /** + * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing. + */ + public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream()); + + static { + try { + NodeWalkVisit = getFieldValue(Node.class, "WVISIT"); + set_MID_ASSERT = MethodHandles.lookup().unreflectSetter(getField( IterPeeps.class, "MID_ASSERT")); + } catch (Exception e) { + throw new ExceptionInInitializerError(e); + } + } + /** * Check that eiter one of the objects is null or that both are equal. */ @@ -50,9 +114,25 @@ class FuzzerUtils { * Parse script with peepholes enabled or disabled */ public static StopNode parse(String script, boolean runPeeps) { - var parser = new Parser(script); - Node._disablePeephole = !runPeeps; - return parser.parse(); + var err = System.err; + var out = System.out; + try { + System.setErr(NULL_PRINT_STREAM); + System.setOut(NULL_PRINT_STREAM); + try { + set_MID_ASSERT.invokeExact(false); + } catch (Throwable e) { + throw rethrow(e); + } + var parser = new Parser(script); + Node._disablePeephole = !runPeeps; + var stop = parser.parse(); + return runPeeps ? stop.iterate() : stop; + } finally { + NodeWalkVisit.clear(); + System.setErr(err); + System.setOut(out); + } } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java index b7fc18ec..2ef0a3fd 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java @@ -32,8 +32,8 @@ public class Reducer { new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"), new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"), new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"), - new Replace(Pattern.compile("\\b\\w+\\b"), "1"), new Replace(Pattern.compile("\\b\\w+\\b"), "0"), + new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"), new Replace(Pattern.compile("\\d+\\+"), ""), new Replace(Pattern.compile("\\+\\d+"), ""), new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 148c2319..ad98f7e2 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -15,20 +15,6 @@ import java.util.Random; */ public class ScriptGenerator { - /** - * Get the list of keywords from the parser. - */ - @SuppressWarnings("unchecked") - private static HashSet getKeywords() { - try { - var field = Parser.class.getDeclaredField("KEYWORDS"); - field.setAccessible(true); - return (HashSet) field.get(new Parser("")); - } catch (Throwable e) { - throw new ExceptionInInitializerError(e); - } - } - /** * Number of spaces per indentation */ @@ -40,7 +26,15 @@ public class ScriptGenerator { /** * List of keywords not valid for identifiers. */ - private static final HashSet KEYWORDS = getKeywords(); + private static final HashSet KEYWORDS; + + static { + try { + KEYWORDS = FuzzerUtils.getFieldValue(new Parser(""), "KEYWORDS"); + } catch (Throwable e) { + throw new ExceptionInInitializerError(e); + } + } /** * Flag for a statement that it does not pass on control flow to the next statement. @@ -83,11 +77,11 @@ public class ScriptGenerator { /** * The depth of blocks allowed. */ - private int depth = 7; + private int depth = 20; /** * The depth of expressions allowed. */ - private int exprDepth = 3; + private int exprDepth = 30; /** * Current variables in scope. */ @@ -141,7 +135,7 @@ public class ScriptGenerator { * @return The random name generated */ private StringBuilder getRandomName() { - int len = random.nextInt(10) + 1; + int len = random.nextInt(30) + 1; StringBuilder sb = new StringBuilder(len); sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10))); for (int i=1; i