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 --- 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 ++++++++++++++++++++++++++++++++++++++++++ 21 files changed, 1483 insertions(+) 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 (limited to 'docs') 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. -- cgit v1.2.3