From 81e464bab1193e0d4b973503ee1da1c9700a66a6 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 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Thalia Archibald Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamas Hadhazy Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Hadházy Tamás Co-authored-by: Dibyendu Majumdar Co-authored-by: Darrick Wiebe Co-authored-by: Claude Opus 5 --- Makefile | 8 +- README.ja.md | 2 +- README.md | 2 +- docs/chapter09/09-graph1.gv | 67 +++++ docs/chapter09/09-graph1.json | 23 ++ docs/chapter09/09-graph1.svg | 110 +++++++ docs/chapter09/09-graph2.gv | 63 ++++ docs/chapter09/09-graph2.json | 21 ++ docs/chapter09/09-graph2.svg | 102 +++++++ docs/chapter09/09-graph3.gv | 37 +++ docs/chapter09/09-graph3.json | 17 ++ docs/chapter09/09-graph3.svg | 89 ++++++ docs/chapter09/09-graph4.gv | 29 ++ docs/chapter09/09-graph4.json | 13 + docs/chapter09/09-graph4.svg | 70 +++++ docs/chapter09/09-graph5.gv | 63 ++++ docs/chapter09/09-graph5.json | 18 ++ docs/chapter09/09-graph5.svg | 92 ++++++ docs/chapter09/09-graph6.gv | 60 ++++ docs/chapter09/09-graph6.json | 17 ++ docs/chapter09/09-graph6.svg | 87 ++++++ docs/chapter09/Makefile | 1 + docs/chapter09/README.ja.md | 190 ++++++++++++ docs/chapter09/README.md | 314 ++++++++++++++++++++ .../java/com/seaofnodes/simple/GraphEvaluator.java | 2 +- src/main/java/com/seaofnodes/simple/IterPeeps.java | 208 ++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 70 +++-- .../java/com/seaofnodes/simple/node/AddNode.java | 53 ++-- .../java/com/seaofnodes/simple/node/BoolNode.java | 9 +- .../com/seaofnodes/simple/node/ConstantNode.java | 16 +- .../java/com/seaofnodes/simple/node/DivNode.java | 9 +- .../java/com/seaofnodes/simple/node/IfNode.java | 29 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulNode.java | 9 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 7 + src/main/java/com/seaofnodes/simple/node/Node.java | 264 +++++++++++++---- .../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 | 55 ++-- .../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 | 10 +- .../java/com/seaofnodes/simple/node/SubNode.java | 9 +- .../simple/print/SimpleGraphAdapter.java | 2 +- .../simple/print/SimpleGraphObserver.java | 5 +- 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/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 | 320 +++++++++++++++++++++ .../java/com/seaofnodes/simple/FuzzerWrap.java | 13 +- .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 94 +++++- .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 91 +++++- .../java/com/seaofnodes/simple/fuzzer/Reducer.java | 2 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 32 +-- 61 files changed, 2860 insertions(+), 298 deletions(-) create mode 100644 docs/chapter09/09-graph1.gv create mode 100644 docs/chapter09/09-graph1.json create mode 100644 docs/chapter09/09-graph1.svg create mode 100644 docs/chapter09/09-graph2.gv create mode 100644 docs/chapter09/09-graph2.json create mode 100644 docs/chapter09/09-graph2.svg create mode 100644 docs/chapter09/09-graph3.gv create mode 100644 docs/chapter09/09-graph3.json create mode 100644 docs/chapter09/09-graph3.svg create mode 100644 docs/chapter09/09-graph4.gv create mode 100644 docs/chapter09/09-graph4.json create mode 100644 docs/chapter09/09-graph4.svg create mode 100644 docs/chapter09/09-graph5.gv create mode 100644 docs/chapter09/09-graph5.json create mode 100644 docs/chapter09/09-graph5.svg create mode 100644 docs/chapter09/09-graph6.gv create mode 100644 docs/chapter09/09-graph6.json create mode 100644 docs/chapter09/09-graph6.svg create mode 100644 docs/chapter09/Makefile create mode 100644 docs/chapter09/README.ja.md 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 5ededbc3..1874a5b5 100644 --- a/Makefile +++ b/Makefile @@ -69,7 +69,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) com.seaofnodes.simple.FuzzerWrap + @echo "testing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore $(test_cp) com.seaofnodes.simple.FuzzerWrap + +fuzzer: $(default_targets) + @echo "testing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap + .PHONY: clean clean: diff --git a/README.ja.md b/README.ja.md index 584d4bcf..0cdd98c2 100644 --- a/README.ja.md +++ b/README.ja.md @@ -45,7 +45,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第6章](docs/chapter06/README.ja.md)：実行されない制御フローに対するピープホール最適化。 * [第7章](docs/chapter07/README.ja.md)：`while` 文。ループ構造と先行的な Phi の導入。 * [第8章](docs/chapter08/README.ja.md)：ループ構造の続き。必要時の Phi の生成、`break` 文と `continue` 文。 -* 第9章：大域的値番号付け。不動点に達するまでのピープホール最適化の反復。ワークリスト。 +* [第9章](docs/chapter09/README.ja.md)：大域的値番号付け。不動点に達するまでのピープホール最適化の反復。ワークリスト。 * 第10章：ユーザー定義の構造体、ポインタ、null 解析。SSA で表す単一のメモリ値。ロード、ストア、実行可能な評価器。 * 第11章：同値類によるエイリアス解析。`MemMerge`、`MemPhi`、`BulkMemPhi` による必要時のメモリ分割。 * 第12章：参照フィールド、前方参照、再帰的な構造体。 diff --git a/README.md b/README.md index a637e3a4..85489ce0 100644 --- a/README.md +++ b/README.md @@ -52,7 +52,7 @@ The Simple language is 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 constructs - eager phi approach. * [Chapter 8](docs/chapter08/README.md): Looping constructs 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 structs, pointers and null analysis. One memory value in SSA. Loads, stores, and an executable evaluator. * Chapter 11: Equivalence class aliasing. Lazy memory 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.json b/docs/chapter09/09-graph1.json new file mode 100644 index 00000000..8dfdee0a --- /dev/null +++ b/docs/chapter09/09-graph1.json @@ -0,0 +1,23 @@ +{ + "ver": 1, + "comp": "chapter09/docs/09-graph1.svg", + "step": 1, + "roots": [18, 24], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 7, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 18, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 21, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 20, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 21, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter09/09-graph1.svg b/docs/chapter09/09-graph1.svg new file mode 100644 index 00000000..1b53a14a --- /dev/null +++ b/docs/chapter09/09-graph1.svg @@ -0,0 +1,110 @@ +#8[1] → #4 · DATA#8[2] → #7 · DATA#17[1] → #4 · DATA#17[2] → #16 · DATA#18[0] → #5 · CTRL#18[1] → #17 · DATA#21[1] → #8 · DATA#21[2] → #20 · DATA#24[0] → #6 · CTRL#24[1] → #21 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #0 +Type not computed + +False  #6/1#6 False +Projection 1 of #0 +Type not computed + +2  #7#7 2 +Type not computed + +*  #8#8 * +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #7 DATA0122  #16#16 2 +Type not computed + +*  #17#17 * +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #16 DATA012Return  #18#18 Return +Type not computed + +[0] → #5 CTRL +[1] → #17 DATA011  #20#20 1 +Type not computed + ++  #21#21 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #20 DATA012Return  #24#24 Return +Type not computed + +[0] → #6 CTRL +[1] → #21 DATA01 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.json b/docs/chapter09/09-graph2.json new file mode 100644 index 00000000..7b48931f --- /dev/null +++ b/docs/chapter09/09-graph2.json @@ -0,0 +1,21 @@ +{ + "ver": 1, + "comp": "chapter09/docs/09-graph2.svg", + "step": 1, + "roots": [18, 24], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [], "proj": {"par": 0, "idx": 1}}, + {"id": 7, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 18, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}, {"idx": 2, "def": 21, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 24, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter09/09-graph2.svg b/docs/chapter09/09-graph2.svg new file mode 100644 index 00000000..59ef5de1 --- /dev/null +++ b/docs/chapter09/09-graph2.svg @@ -0,0 +1,102 @@ +#8[1] → #4 · DATA#8[2] → #7 · DATA#18[0] → #5 · CTRL#18[1] → #8 · DATA#20[1] → #8 · DATA#20[2] → #21 · DATA#24[0] → #6 · CTRL#24[1] → #20 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #0 +Type not computed + +False  #6/1#6 False +Projection 1 of #0 +Type not computed + +#2  #7#7 #2 +Type not computed + +*  #8#8 * +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #7 DATA012Return  #18#18 Return +Type not computed + +[0] → #5 CTRL +[1] → #8 DATA01+  #20#20 + +Type not computed + +[0] → — DATA +[1] → #8 DATA +[2] → #21 DATA012#1  #21#21 #1 +Type not computed + +Return  #24#24 Return +Type not computed + +[0] → #6 CTRL +[1] → #20 DATA01 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.json b/docs/chapter09/09-graph3.json new file mode 100644 index 00000000..abdb81b6 --- /dev/null +++ b/docs/chapter09/09-graph3.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter09/docs/09-graph3.svg", + "step": 1, + "roots": [9], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 6, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 7, "label": "*", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 8, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter09/09-graph3.svg b/docs/chapter09/09-graph3.svg new file mode 100644 index 00000000..da89b9b9 --- /dev/null +++ b/docs/chapter09/09-graph3.svg @@ -0,0 +1,89 @@ +#6[1] → #4 · DATA#6[2] → #4 · DATA#7[1] → #4 · DATA#7[2] → #4 · DATA#8[1] → #6 · DATA#8[2] → #7 · DATA#9[1] → #8 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA*  #6#6 * +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #4 DATA012*  #7#7 * +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #4 DATA012-  #8#8 - +Type not computed + +[0] → — DATA +[1] → #6 DATA +[2] → #7 DATA012Return  #9#9 Return +Type not computed + +[0] → — CTRL +[1] → #8 DATA01 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.json b/docs/chapter09/09-graph4.json new file mode 100644 index 00000000..1282e87e --- /dev/null +++ b/docs/chapter09/09-graph4.json @@ -0,0 +1,13 @@ +{ + "ver": 1, + "comp": "chapter09/docs/09-graph4.svg", + "step": 1, + "roots": [10], + "scope": 0, + "nodes": [ + {"id": 9, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 10, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter09/09-graph4.svg b/docs/chapter09/09-graph4.svg new file mode 100644 index 00000000..3c49a48a --- /dev/null +++ b/docs/chapter09/09-graph4.svg @@ -0,0 +1,70 @@ +#10[1] → #9 · DATA#0  #9#9 #0 +Type not computed + +Return  #10#10 Return +Type not computed + +[0] → — CTRL +[1] → #9 DATA01 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.json b/docs/chapter09/09-graph5.json new file mode 100644 index 00000000..ff52950d --- /dev/null +++ b/docs/chapter09/09-graph5.json @@ -0,0 +1,18 @@ +{ + "ver": 1, + "comp": "chapter09/docs/09-graph5.svg", + "step": 1, + "roots": [21], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 6, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 9, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null, "backedge": true}], "proj": null}, + {"id": 16, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 18, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 16, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter09/09-graph5.svg b/docs/chapter09/09-graph5.svg new file mode 100644 index 00000000..bbaf2227 --- /dev/null +++ b/docs/chapter09/09-graph5.svg @@ -0,0 +1,92 @@ +#9[1] → #4 · DATA#9[2] → #18 · DATA#16[1] → #6 · DATA#16[2] → #9 · DATA#18[1] → #16 · DATA#18[2] → #6 · DATA#21[1] → #9 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA#1  #6#6 #1 +Type not computed + +φ_arg  #9#9 φ_arg +Type not computed + +[0] → — ASSOC +[1] → #4 DATA +[2] → #18 DATA012+  #16#16 + +Type not computed + +[0] → — DATA +[1] → #6 DATA +[2] → #9 DATA012+  #18#18 + +Type not computed + +[0] → — DATA +[1] → #16 DATA +[2] → #6 DATA012Return  #21#21 Return +Type not computed + +[0] → — CTRL +[1] → #9 DATA01 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.json b/docs/chapter09/09-graph6.json new file mode 100644 index 00000000..5b511bd1 --- /dev/null +++ b/docs/chapter09/09-graph6.json @@ -0,0 +1,17 @@ +{ + "ver": 1, + "comp": "chapter09/docs/09-graph6.svg", + "step": 1, + "roots": [21], + "scope": 0, + "nodes": [ + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 9, "label": "φ_arg", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 25, "role": "DATA", "label": null, "backedge": true}], "proj": null}, + {"id": 21, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 25, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}, {"idx": 2, "def": 24, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter09/09-graph6.svg b/docs/chapter09/09-graph6.svg new file mode 100644 index 00000000..b573d88a --- /dev/null +++ b/docs/chapter09/09-graph6.svg @@ -0,0 +1,87 @@ +#9[1] → #4 · DATA#9[2] → #25 · DATA#21[1] → #9 · DATA#25[1] → #9 · DATA#25[2] → #24 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATAφ_arg  #9#9 φ_arg +Type not computed + +[0] → — ASSOC +[1] → #4 DATA +[2] → #25 DATA012Return  #21#21 Return +Type not computed + +[0] → — CTRL +[1] → #9 DATA01#2  #24#24 #2 +Type not computed + ++  #25#25 + +Type not computed + +[0] → — DATA +[1] → #9 DATA +[2] → #24 DATA012 diff --git a/docs/chapter09/Makefile b/docs/chapter09/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter09/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter09/README.ja.md b/docs/chapter09/README.ja.md new file mode 100644 index 00000000..79da0150 --- /dev/null +++ b/docs/chapter09/README.ja.md @@ -0,0 +1,190 @@ +# 第9章: 大域的値番号付けと反復的なピープホール最適化 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第8章](../chapter08/README.ja.md) | +[次の章: 第10章](../chapter10/README.ja.md) + +文法は[第8章](../chapter08/08-grammar.ja.md)から変わりません。 + +# 目次 + +1. [ピープホール最適化の基盤づくり](#ピープホール最適化の基盤づくり) +2. [大域的値番号付け](#大域的値番号付け) +3. [解析後の反復的なピープホール最適化](#解析後の反復的なピープホール最適化) +4. [遠くの隣接ノード](#遠くの隣接ノード) +5. [今後の課題](#今後の課題) +6. [GVN による共通部分式](#gvn-による共通部分式) + - [例1](#例1) + - [例2](#例2) +7. [解析後の反復最適化](#解析後の反復最適化) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter09) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter08...linear-chapter09) することもできます。 + +この章では次のことを行います。 + +* 大域的値番号付け（共通部分式除去）を追加します。 +* 解析後にピープホール最適化を不動点まで反復する最適化を追加します。 + +この章に言語の変更はなく、最適化だけを追加します。 + +## ピープホール最適化の基盤づくり + +第9章の目標は、ピープホール最適化を「仕上げる」ことです。これ以上ピープホール最適化が登場しないという意味ではありません。むしろ、今後もたくさん登場します。ここで作るのは、それらを整理し、安全で扱いやすく実装し、不動点に到達するまで適用するための基盤です。 + +本当の目標は、新しいピープホール最適化を恐れずに追加できるようにすることです。間違っていれば、すぐにアサーションで失敗します。正しければ、新しい最適化はほかのすべての最適化と一緒に動き、お互いに効果を高め合います。 + +## 大域的値番号付け + +大域的値番号付け（GVN）は、従来のハッシュテーブルを使い、ノードのオペコードと入力からハッシュを計算します。2つのノードが同じ入力に同じ処理を行うなら、結果も同じなので、共有できます。 + +* Node にグローバルな静的ハッシュテーブル `GVN` を追加します。 +* `Node.equals` を追加します。2つのノードは、同じ入力に対し同じオペコード、すなわち同じ Java クラスを持つ場合に等価です。 +* ノードのオペコード（代用としてノード名の文字列）と入力に基づく `hashCode` を追加します。 +* `ConstantNode` などいくつかのノードでは、追加の固有情報が必要です。定数17と99は同じではありませんが、どちらも同じ `ConstantNode` クラスとラベルを持ちます。`eq` と `hash` は、この追加情報を確認（またはハッシュ化）します。 + +ここでは意図的に *値の等価性* を使っていることに注意してください。Simple の多くの箇所では *参照の等価性* を使います。たとえば、ノードとエッジの管理は値の等価性ではなく参照の等価性で行い、`Utils.find()` も参照で検索します。Simple プロジェクト全体で、ノードを検索するときは、それが *値の等価性* か *参照の等価性* かに注意してください。常に明示されているわけではありませんが、文脈から明らかであるはずです。 + +グラフは頻繁に編集するため、ノードの入力が変わることがあります。それによってハッシュも変わるので、GVN テーブル内で見つからなくなります。たとえば、次の `Add` を `Con` に置き換える場合です。 + + (Mul (Add 4 8) x) // Fold the constant + (Mul 12 x) // The `Mul` changes hash and inputs + +対策として、エッジを変更するときにはノードが `GVN` テーブルに存在していないことを要求します。何らかの「エッジのロック」が必要です。「エッジがロックされている」なら、エッジの変更前にまずノードを `GVN` から取り除く必要があります。 + +* `_hash` フィールドを、キャッシュされたハッシュコードとエッジのロックの両方に使います。0ならノードはロックされておらず、`GVN` にもありません。0以外ならノードの「エッジがロックされており」、`GVN` に存在します。 +* `hashCode` 関数はキャッシュされたハッシュがあれば使い、偶然ハッシュが0になることは許しません。 +* エッジを変更する前にノードを `GVN` から取り除く `unlock()` を追加します。ノードのエッジを操作するすべての呼び出しの前に挿入します。エッジを変更するすべてのコード経路は、すでにノードを再度ピープホール最適化することを保証しているため、その再訪時にノードを `GVN` テーブルへ再挿入します。 + +この新しい `GVN` テーブルは、`peepholeOpt()`（および `peephole()`）で、ピープホール最適化するすべてのノードについて共通部分式を探すために使います。ノードのハッシュが0なら、以前の同一ノードとの一致を探します。見つかれば、その以前のノードを使い、現在のノードはデッドコード除去で削除します。見つからなければ、現在のノードを「代表インスタンス」として `GVN` に挿入します。ノードのハッシュがすでに0以外なら、それが「代表インスタンス」だとわかるので、`GVN` を検索する必要はありません。 + +この最適化全体は、`iter()` の十数行と、共有の `equals`、`hashCode`（コメントを含めてさらに約50行）で実現できます。 + +不変条件の1つは、ピープホール最適化の実行中に型が単調に上がることです。GVN はこれを一時的に破る場合があります。2つの等価なノードのうち、一方の `_type` はすでに引き上げられ、もう一方はまだかもしれません。どちらを残すかによって、「より低い」`_type` のノードを選ぶ可能性があります。この「低い」は、型の束における意味です。両方の型が正しい必要があり、両ノードの `compute()` は同じ型を返さなければなりません。その型は JOIN に等しい必要があります。対策は、2つのノードの型について（MEET ではなく）JOIN を計算することです。 + +## 解析後の反復的なピープホール最適化 + +解析後の `IterPeeps` は、ピープホール最適化を不動点、すなわち適用できる最適化がなくなるまで反復します。ピープホール最適化がコードサイズを増やすことはまれ（まったくない？）なので、これは線形時間になるはずです。グラフは何らかの尺度、通常はサイズについて単調に小さくなるはずです。MulNode やロード/ストアノードの数などが減り、より「高価な」ノードを安価なノードに置き換える場合もあります。 + +理論上、ワークリストの処理は単純です。次の項目を取って処理します。グラフが変わったら、隣接ノードをワークリストに入れます。この手順を、ワークリストが空になるまで繰り返します。 + +扱う必要のある主な問題は次のとおりです。 + +* ノードには利用側があります。あるノード群を別のものに置き換えるには、さらにグラフを組み替える必要があります。高度に難しいわけではありませんが、細かな扱いが面倒です。少数のグラフ操作ユーティリティと、ピープホール最適化の間ではグラフが安定し正しいという強い不変条件が役に立ちます。ここでは、従来の安定したノードのユーティリティを基に、`Node.subsume` が操作の大部分を行います。 +* ノードの変更は、グラフの「近傍」も変えます。隣接ノードにもピープホール最適化を適用できるか確認し、その先にも同様に続ける必要があります。ピープホール最適化やグラフ更新の後では、ノードの利用側と定義側をワークリストに入れます。 +* 強い不変条件は、すべてのノードについて、ワークリスト上にあるか、適用できるピープホール最適化がないか、のどちらかであることです。確認は簡単ですが、高コストです。通常の「不動点までのピープホール最適化の反復」は基本的に線形時間ですが、この確認は各最適化ステップで線形時間なので、全体では二次時間になります。便利なアサーションですが、アルゴリズム全体が安定したら無効にし、新しく追加したピープホール最適化が誤動作するときに再び有効にできます。このコードは `IterPeeps.iterate` の `assert progressOnList(stop);` として有効になっています。 + +## 遠くの隣接ノード + +一部のピープホール最適化では、「近傍」は直接の利用側や定義側より遠くまで及びます。そのため、より長距離の関係を扱う方法が必要です。たとえば、ある最適化が「this -> A -> B -> C」を調べ、自身を「D」に置き換えようとしても、「B」の何らかの判定で失敗する場合があります。「B」が更新されたら、「this」を再訪し、ピープホール最適化を再確認したいはずです。そこで、「B」に「this」の依存関係を記録します。「B」の更新時に、依存リスト（「this」）を「処理待ち」リストへ追加します。 + +遠くの隣接ノードの確認の例が `AddNode` にあります。`(Add (Add x 2) 1)` という重なった定数を探し、`(Add x 3)` にしたいとします。調べた結果、代わりに `(Add (Phi (Add x 2) self) 1)` が見つかったとします。`Phi` は `Add` ではないため、当然この確認はそこで打ち切られます。しかし、`(Phi y self)` は一意な入力を1つしか持たず、いずれそれ自体が `y` にピープホール最適化されます。そうなれば、重なった `Add` の最適化を適用できます。そこで、失敗した Add の最適化は `phi.addDep(Add)` を呼び、`Phi` への依存を登録します。実際に後で `Phi` が最適化されたら、その依存ノード（たとえば `Add`）を `IterPeeps` のワークリストへ戻し、重なった Add の最適化を再試行します。 + +一般的な規則は次のとおりです。 + +* **ピープホール最適化のパターンが遠くのノードを調べるなら、依存リストに登録しなければなりません！** +* `node.in(1).in(2)` を `node.in(1).in(2).addDep(node)` にします。 + +この章では、次のパターンでこれを使います。 + +* 一部の最適化は `Phi` の入力と関係します。直接の場合も間接の場合もあり、たとえば `(Add Add( (Phi x) 2 ) 1)` です。`Phi` の入力がすべて `Constant` なら最適化を進められるため、そのノードを `Phi` の入力の依存側にします。また、`Phi` の Region の依存側にもします。`Node.allCons()` と `PhiNode.allCons()` を参照してください。 +* `(Add (Add x 1) 2)` のパターンでは、`x` が定数になれば処理が進むため、外側の `Add` を `x` の依存側として追加します。`AddNode.idealize()` を参照してください。 +* `Phi` の型を計算するとき、対応する Region の該当する制御が生きていれば、`Phi` を Region の制御入力の依存側として追加します。その制御が死ねば、`Phi` にピープホール最適化を適用できるからです。`PhiNode.compute()` と `PhiNode.singleUniqueInput()` を参照してください。 + +変更点: + +* Node に `ArrayList _deps` フィールドを追加します。初期値は null です。 +* 一部のピープホール最適化（上記参照）は、遠くのノードの確認に失敗したら `distant.addDep(this)` を呼び、依存を追加します。`addDep` は `_deps` を作り、各種の重複した追加を除外します。 +* `IterPeeps` のループは、変更を見つけたら、依存側もすべてワークリストへ移します。 + +# 例 + +## GVN による共通部分式 + +これらの図は値の依存関係に焦点を当てています。通常の制御フローは省略しています。最初の例では、小さな True/False の射影で2つの Return を区別します。空の制御スロットは、コンパイラの入力の欠如ではなく、省略した文脈を表す場合があります。 + +### 例1 + +GVN がどのように共通部分式を見つけるかを示す小さな例です。 + +```java +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; +``` + +GVN を使う前には、次のグラフになります。`arg+arg` を `arg*2` に変換していることに注目してください。 + +![グラフ1](./09-graph1.svg) + +GVN を追加すると、次のようになります。`arg*2` の式が2回現れる代わりに、再利用されるようになったことに注目してください。 + +![グラフ2](./09-graph2.svg) + +### 例2 + +共通の式を再利用できると、さらに最適化が可能になります。単純な例を示します。 + +```java +return arg*arg-arg*arg; +``` + +GVN がなければ、ピープホール最適化は減算の両辺が同じ値だと認識できません。 + +![グラフ3](./09-graph3.svg) + +* 各乗算（*）ノードは、`arg` に向かうエッジを2本持ちます。 +* 入力スロットのラベルが、同じ定義を使うこの2つの使用を区別します。 + +GVN があれば、ピープホール最適化はよりよい結果を得られます。 + +![グラフ4](./09-graph4.svg) + +## 解析後の反復最適化 + +ワークリストに基づく解析後の最適化は、解析中にはできなかった最適化を可能にします。たとえば、次のコードです。 + +```java +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; +``` + +`while` ループの解析中には、`step` が定数で、変化しないことはまだわかりません。そのため、解析後の最適化がなければ次のようになります。 + +両方の図で、ループの判定と制御のバックエッジは省略しています。Phi のデータのバックエッジは残しているため、繰り返される加算とその置き換えを比較しやすくなっています。その入力1は入口の値、入力2は次の反復の値です。 + +![グラフ5](./09-graph5.svg) + +解析後のワークリストに基づく最適化を有効にすると、次のようになります。グラフのループ本体内に `arg+2` が現れたことに注目してください。 + +![グラフ6](./09-graph6.svg) + +## 今後の課題 + +後の章で扱いたい問題がさらにあります。 + +* 順序を考えずにピープホール最適化を実行すると、いくつかの欠点があります。 + - 死んでいるものや、もうすぐ死ぬものを最適化してから削除する場合があります。無駄な処理です。 + - 死んだ無限ループは、ピープホール最適化の無限の循環を引き起こすことがよくあります。死んだループの「根元」を処理すれば、全体を畳み込めるのに、そこに到達できません。 + - 一部の最適化はグラフを直接小さくします。ほかの最適化はサイズを保ったまま別のものを減らします（たとえば2倍の Mul を Shift に置き換える場合）。さらに、簡約する前に一時的にグラフを大きくしようとする最適化も出てくるかもしれません。 +* したがって、まずグラフを直接小さくする最適化（デッドコード除去など）を行い、次に別のものを減らす最適化を行い、最後にそれ以外を行うことには利点があります。これはソートされたワークリストを意味しますが、順序の種類はごく限られるため、基数ソートだけで十分です。ピープホール最適化を、たとえば次のような分類に分ける必要があります。 + - 「厳密に小さくする」もの。 + - 「ノード数は同じだが、たとえば `Mul` を `Shift` に置き換える」もの。 + - 自由度を増やすもの（エッジの迂回）。 + - 「後で小さくなるため、今は大きくする」もの（インライン化はこの分類です）。 +* リストのどちらかの端から常に取り出すのを避ける利点もあります。一方または他方の端から処理すると、多くの最適化パターンが二次時間になるかもしれません。何かを変更してリストに戻すと、それがすぐに再び取り出されるためです。つまり、同じ最適化を繰り返すループに陥り、たとえば左側に連なる加算木を、少しずつ右側に連なる加算木に移すことになります。擬似ランダムな取り出しは、ランダム化によって悪い最適化パターンを避けます。 +* なぜ `IterPeeps` は、`addDeps` の仕組みを備えたワークリストを使う代わりに、全ノードを1回か2回走査するだけではないのでしょうか。定義側を利用側より先に訪問する順序（たとえば逆後順）で巡回することさえできます。 + + ループがなければ、そのような1回の走査で局所的なピープホール最適化をすべて見つけられます。実際、パーサーはすでにこれを行っています。しかし、ループやさらに遠くのケースでの機会は見つけられません。ループ周辺の最適化を得るには、再訪が必要です。各回 O(N) のコストで O(N) 回の走査を必要とするケースは簡単に作れ、アルゴリズムはすぐに二次時間になります。 + + `addDeps` の解法は、ピープホール最適化を書く際のコストをいくらか増やす代わりに、この二次時間のコストを避けます。 diff --git a/docs/chapter09/README.md b/docs/chapter09/README.md new file mode 100644 index 00000000..338df612 --- /dev/null +++ b/docs/chapter09/README.md @@ -0,0 +1,314 @@ +# Chapter 9: Global Value Numbering and Iterative Peepholes + +English | [日本語](README.ja.md) + +[Previous: Chapter 8](../chapter08/README.md) | +[Next: Chapter 10](../chapter10/README.md) + +The grammar is unchanged from [Chapter 8](../chapter08/08-grammar.md). + +# Table of Contents + +1. [Engineering Peepholes](#engineering-peepholes) +2. [Global Value Numbering](#global-value-numbering) +3. [Post-Parse Iterative Peepholes](#post-parse-iterative-peepholes) +4. [Distant Neighbors](#distant-neighbors) +5. [Future Work](#future-work) +6. [Common SubExpressions via GVN](#common-subexpressions-via-gvn) + - [Example 1](#example-1) + - [Example 2](#example-2) +7. [Post Parse Iterative Optimizations](#post-parse-iterative-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. + +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. + + +## 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 equal 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. + +Note the intentional *value* equality here. In many places in Simple we use +*reference* equality - e.g. node/edge maintenance is via reference equality, not +value equality, so e.g. the `Utils.find()` call finds via reference. Throughout the Simple project whenever a Node lookup is happening, beware if it's via +*value* or *reference* equality; this is not always explicitly called out but +should be obvious from context. + + +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 an `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. It's 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 neighbors need to + be checked to see if THEY can also peephole, and so on. After any peephole + or graph update we put a Node's 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. It's 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 it's 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 dependencies (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 an `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. + + + +# Examples + +## Common SubExpressions via GVN + +These diagrams focus on value dependencies. Routine control flow is omitted; +small True/False projections distinguish the two Returns in the first example. +Empty control slots can stand for omitted context, not missing compiler inputs. + +### 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 the 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`. +- The input-slot labels distinguish these two uses of the same definition. + +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 the following: + +The loop test and control backedge are omitted in both diagrams. The Phi's +data backedge remains, making the repeated additions and their replacement +easy to compare; its input 1 is the entry value and input 2 the next iteration. + +![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) + + +## Future Work + +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 keep 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 e.g. left-spine add-tree into a + right-spine add-tree. A pseudo-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 absence 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. 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/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java new file mode 100644 index 00000000..41fc6916 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -0,0 +1,208 @@ +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) { + 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 + var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(n); + Node x = n.peepholeOpt(); + if( x != null ) { + if( x.isDead() ) { + if( obs != null ) obs.after(n, x, true); + 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( obs != null ) obs.after(n, x, true); + } + + 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 d7055f48..3c1eab96 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -78,11 +78,12 @@ public class Parser { public Parser(String source, TypeInteger arg) { PARSER = this; 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) { @@ -115,7 +116,6 @@ public class Parser { return STOP; } - /** * Parses a block * @@ -191,11 +191,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 @@ -209,7 +208,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 @@ -253,7 +252,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; } @@ -275,11 +274,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(); @@ -288,12 +286,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 + ifF.unkeep(); // fScope already owns the false control if (matchx("else")) { parseStatement(); fScope = _scope; @@ -383,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; } @@ -401,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; } @@ -417,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 4a587953..c299e805 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -14,11 +14,14 @@ public class AddNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()+i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } @@ -27,12 +30,8 @@ public class AddNode extends Node { 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 ) @@ -48,6 +47,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) ? @@ -59,7 +62,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 spine_cmp(lhs,rhs) ? swap12() : phiCon(this,true); + return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true); // Now we only see (add add non) @@ -70,7 +73,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()); @@ -84,7 +91,7 @@ public class AddNode extends Node { // Do we rotate (x + y) + z // into (x + z) + y ? - if( spine_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; @@ -97,16 +104,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 @@ -127,8 +134,15 @@ 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-spine nodes and decide what order they should be in. @@ -136,12 +150,15 @@ public class AddNode extends Node { // 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 spine_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 e363bf75..a6b8bfc7 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -23,11 +23,14 @@ abstract public class BoolNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); - return i0.meet(i1); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 19166ec6..cf2465e3 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -9,7 +9,7 @@ import com.seaofnodes.simple.type.Type; /** * 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 @@ -44,4 +44,18 @@ 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; } + @Override int idepth() { return 0; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 4c3c2feb..d7244ace 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -14,13 +14,16 @@ public class DivNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return i1.value() == 0 ? TypeInteger.ZERO : TypeInteger.constant(i0.value()/i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 41b5ffd7..1c3d2c85 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -28,27 +28,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 fb51777e..0934c37f 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -16,7 +16,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 TypeInteger.BOT; + return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 2d0fa95b..5592c52d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -14,11 +14,14 @@ public class MulNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()*i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } 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 46d5b843..3c1ed0ab 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -5,10 +5,12 @@ import com.seaofnodes.print.BaseNode; import com.seaofnodes.simple.Parser; 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. @@ -58,6 +60,7 @@ public abstract class Node extends BaseNode { * 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) { super(UNIQUE_ID++); // allocate unique dense ID @@ -88,11 +91,10 @@ public abstract class Node extends BaseNode { * @return Input node or null */ public Node in(int i) { return _inputs.get(i); } + public Node out(int i) { return _outputs.get(i); } public int nIns() { return _inputs.size(); } - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } @@ -113,9 +115,10 @@ public abstract class Node extends BaseNode { * @param new_def the new definition * @return new_def for flow coding */ - Node setDef(int idx, Node new_def ) { + public Node setDef(int idx, Node new_def ) { + unlock(); Node old_def = in(idx); - if( old_def == new_def ) return this; // No change + if( old_def == new_def ) return new_def; // No change // If new def is not null, add the corresponding def->use 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. @@ -132,13 +135,17 @@ public abstract class Node extends BaseNode { // 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; } /** @@ -149,6 +156,7 @@ public abstract class Node extends BaseNode { * @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 @@ -171,6 +179,7 @@ public abstract class Node extends BaseNode { // 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; i { /** * Kill a Node with no uses, 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 } @@ -201,10 +218,11 @@ public abstract class Node extends BaseNode { public N unkeep() { delUse(null); return (N)this; } // 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); @@ -215,6 +233,19 @@ public abstract class Node extends BaseNode { // ------------------------------------------------------------------------ // Graph-based optimizations + /** + * Try to peephole at this node and return a better replacement Node. + * Always returns some not-null Node (often this). + */ + public final Node peephole() { + var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.before(this); + Node n = peepholeOpt(); + Node rez = n == null ? this : deadCodeElim(n.peephole()); + if( obs != null ) obs.after(this, n == null ? null : rez, false); + return rez; + } + /** * Try to peephole at this node and return a better replacement Node if * possible. We compute a {@link Type} and then check and replace: @@ -228,36 +259,45 @@ public abstract class Node extends BaseNode { * {@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() { - var obs = Parser.PARSER == null ? null : Parser.PARSER._obs; - if( obs != null ) obs.before(this); - Type old = _type; - Node n = peepholeOpt(); - Node rez = n == null ? this : n; - if( obs != null ) obs.after(this, n == null && old == _type ? null : rez, false); - return rez; - } - - private Node peepholeOpt() { + public final Node peepholeOpt( ) { + ITER_CNT++; // Compute initial or improved Type - Type type = _type = compute(); + 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 null; // 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. @@ -287,13 +327,25 @@ public abstract class Node extends BaseNode { * 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 @@ -333,31 +385,126 @@ public abstract class Node extends BaseNode { * 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; + public int nDeps() { return _deps == null ? 0 : _deps.size(); } + public Node dep(int idx) { return _deps.get(idx); } + + /** + * 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; + var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs; + if( obs != null ) obs.dep(this, dep); + 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 { */ public static void reset() { UNIQUE_ID = 1; + GVN.clear(); + ITER_CNT = ITER_NOP_CNT = 0; + } + + // Utility to walk the entire graph applying a function; return the first + // not-null result. + private static final BitSet WVISIT = new BitSet(); + final public 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 538016bd..8077f108 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -16,7 +16,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 TypeInteger.BOT; + return in(1)._type==Type.TOP ? TypeInteger.TOP : TypeInteger.BOT; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 14622140..fe6231fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -15,30 +15,36 @@ public class PhiNode extends Node { @Override protected ExprPrinter _print1(ExprPrinter p) { - if( region().inProgress() ) + if( !(region() instanceof RegionNode r) || r.inProgress() ) p.p("Z"); p.p("Phi("); for( Node in : _inputs ) p.n(in).p(","); return p.unchar(',').close(); } - 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(); @@ -77,11 +83,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 9f4cad7a..bc09c623 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -35,7 +35,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 31585ef4..f34d78e1 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -213,6 +214,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 56689503..c2fcaba5 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -19,7 +19,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 aa655f63..d79194d8 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -3,11 +3,16 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.IterPeeps; public class StopNode extends Node { - public StopNode(Node... inputs) { - super(inputs); + + public final String _src; + + public StopNode(String src) { + super(); + _src = src; } @Override @@ -51,4 +56,5 @@ public class StopNode extends Node { return addDef(node); } + public StopNode iterate() { return IterPeeps.iterate(this); } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index bf938504..6fa87a07 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -14,15 +14,18 @@ public class SubNode extends Node { @Override public Type compute() { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1==Type.TOP || t1==TypeInteger.TOP || + t2==Type.TOP || t2==TypeInteger.TOP ) + return TypeInteger.TOP; // Sub of same is 0 if( in(1)==in(2) ) return TypeInteger.ZERO; - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); - return i0.meet(i1); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index a9acba10..64b78766 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -5,7 +5,7 @@ import com.seaofnodes.graph.GraphSnapshot.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; -/** Chapter 8's view of the IR; browser, transport and layout are shared. */ +/** Chapter 9's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { @Override protected String[] edgeNames(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 0c3f4ce8..2c6c90ca 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 8's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 9's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; @@ -22,6 +22,9 @@ public class SimpleGraphObserver extends GraphCapture { _phase = "Parse"; _ret = _parser.parse(); phase(_phase); + _phase = "Iter"; + com.seaofnodes.simple.IterPeeps.iterate(_parser.STOP); + phase(_phase); } @Override protected String phase() { return _phase; } @Override protected int pos() { return "Parse".equals(_phase) ? _parser.pos() : -1; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index d66fb3e7..daaa8af6 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 a9f6ee1c..ab9dbcff 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 39d8f72b..a2a6a095 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/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 609dff76..c3cd43c3 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -31,7 +31,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 fa9a5e37..2c869033 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()); } @@ -184,6 +184,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 00d725bc..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(); + 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..8103b903 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -0,0 +1,320 @@ +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 testSccp() { + Parser parser = new Parser( +""" +int x = 1; +int cnt = 5; +while (cnt) { + cnt = cnt - 1; + if (x == 0) { + x = x + 1; + } +} +return x; +""" + ); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop8,1,Phi(Region26,(Phi_x+1),Phi_x));", 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 33434b6c..019140ad 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; @@ -33,9 +33,18 @@ public class FuzzerWrap { @Ignore public void fuzzPeepsLarge() { 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 ef73fa4b..c3444093 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; @@ -13,8 +15,8 @@ import java.util.function.Consumer; * This will generate a script similar to how the parser parses it but instead of parsing it will * randomly choose a variation the parser would parse and generate it. * These scripts are the parsed by the parser and all exceptions are caught and filtered - * to only show one occurrence of one problem. Generated graphs are evaluated - * to detect compiler/evaluator failures; this chapter has no differential oracle. + * to only show one occurrence of one problem. This includes script which generate different + * results when graphs optimized with different worklist seeds are executed. * To aid debugging scripts that cause errors are then reduced by applying rules and checking * that the same issue persists. */ @@ -49,17 +51,49 @@ public class Fuzzer { System.out.flush(); } - /** Compile and evaluate generated programs with normal peepholes. */ + /** + * Check that two graphs result in the same output when supplied with a value + * @param stop1 Stop node of the first graph + * @param stop2 Stop node of the second graph + * @param in The input value to both graphs to test for an equal output + */ + private static void checkGraphs(StopNode stop1, StopNode stop2, long in) { + var e1 = GraphEvaluator.evaluateWithResult(stop1, in, EVAL_TIMEOUT); + var e2 = GraphEvaluator.evaluateWithResult(stop2, in, EVAL_TIMEOUT); + if (e1.type() == GraphEvaluator.ResultType.TIMEOUT || e2.type() == GraphEvaluator.ResultType.TIMEOUT) return; + if (e1.type() != e2.type()) + throw new RuntimeException("Different calculations types " + e1.type() + " vs " + e2.type()); + if (e1.value() != e2.value()) + throw new RuntimeException("Different calculations values " + e1.value() + " vs " + e2.value()); + } + + /** + * Run checks for script. Compile the script with two different optimizer worklist seeds. + * Check that exceptions raised in the parser by both methods are the same and only happens if the script may be invalid. + * If the script was successfully parsed check that both version behave the same. + * @param script The script to test + * @param valid If the script is definitely valid. If not some exceptions may be suppressed. + */ private static void runCheck(String script, boolean valid) { - StopNode stop; + StopNode stop1; try { - stop = FuzzerUtils.parse(script); - } catch (RuntimeException e) { - if (!valid || e.getClass() == RuntimeException.class) return; - throw e; + stop1 = FuzzerUtils.parse(script, 123); + } catch (RuntimeException e1) { + try { + FuzzerUtils.parse(script, 456); + } catch (RuntimeException e2) { + if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) { + if (!valid || e1.getClass() == RuntimeException.class) return; + } else { + e1.addSuppressed(e2); + } + } + throw e1; } - for (int input : new int[] {0, 1, 10}) - GraphEvaluator.evaluateWithResult(stop, input, EVAL_TIMEOUT); + var stop2 = FuzzerUtils.parse(script, 456); + checkGraphs(stop1, stop2, 0); + checkGraphs(stop1, stop2, 1); + checkGraphs(stop1, stop2, 10); } /** @@ -75,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 @@ -86,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 0e83861d..6488297b 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,14 +1,80 @@ 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; + private static final java.util.Random WorkRandom; + + /** + * 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"); + WorkRandom = getFieldValue(getFieldValue(IterPeeps.class, "WORK"), "_R"); + 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. */ @@ -47,11 +113,28 @@ class FuzzerUtils { } /** - * Parse script with normal peephole optimization + * Parse and optimize using the given worklist seed */ - public static StopNode parse(String script) { - var parser = new Parser(script); - return parser.parse(); + public static StopNode parse(String script, long workListSeed) { + 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); + WorkRandom.setSeed(workListSeed); + var stop = parser.parse(); + return stop.iterate(); + } 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