From b6d5e06a2099749e867d3068aec9d555ab2fe693 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 11 Nov 2023 23:17:22 +0000 Subject: Chapter 6: Peepholes for If MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Yichen Yan Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Tamas Hadhazy Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki --- docs/chapter06/06-graph1-post.gv | 29 ++ docs/chapter06/06-graph1-post.json | 16 + docs/chapter06/06-graph1-post.svg | 80 +++++ docs/chapter06/06-graph1-pre.gv | 52 +++ docs/chapter06/06-graph1-pre.json | 24 ++ docs/chapter06/06-graph1-pre.svg | 111 ++++++ docs/chapter06/06-graph2-post.gv | 33 ++ docs/chapter06/06-graph2-post.json | 16 + docs/chapter06/06-graph2-post.svg | 80 +++++ docs/chapter06/06-graph2-pre.gv | 55 +++ docs/chapter06/06-graph2-pre.json | 24 ++ docs/chapter06/06-graph2-pre.svg | 108 ++++++ docs/chapter06/06-graph3-false.gv | 35 ++ docs/chapter06/06-graph3-false.svg | 67 ++++ docs/chapter06/06-graph3-nonconst-peephole.gv | 56 +++ docs/chapter06/06-graph3-nonconst-peephole.json | 24 ++ docs/chapter06/06-graph3-nonconst-peephole.svg | 109 ++++++ docs/chapter06/06-graph3-nonconst.gv | 86 +++++ docs/chapter06/06-graph3-nonconst.json | 35 ++ docs/chapter06/06-graph3-nonconst.svg | 150 ++++++++ docs/chapter06/06-graph3-true.gv | 35 ++ docs/chapter06/06-graph3-true.svg | 67 ++++ docs/chapter06/06-graph4-arg2.gv | 37 ++ docs/chapter06/06-graph4-arg2.svg | 67 ++++ docs/chapter06/06-graph4-nonconst.gv | 122 +++++++ docs/chapter06/06-graph4-nonconst.svg | 456 ++++++++++++++++++++++++ docs/chapter06/06-graph4-true.gv | 37 ++ docs/chapter06/06-graph4-true.svg | 67 ++++ docs/chapter06/Makefile | 1 + docs/chapter06/README.ja.md | 168 +++++++++ docs/chapter06/README.md | 207 +++++++++++ docs/chapter06/lattice.gv | 97 +++++ docs/chapter06/lattice.svg | 319 +++++++++++++++++ 33 files changed, 2870 insertions(+) create mode 100644 docs/chapter06/06-graph1-post.gv create mode 100644 docs/chapter06/06-graph1-post.json create mode 100644 docs/chapter06/06-graph1-post.svg create mode 100644 docs/chapter06/06-graph1-pre.gv create mode 100644 docs/chapter06/06-graph1-pre.json create mode 100644 docs/chapter06/06-graph1-pre.svg create mode 100644 docs/chapter06/06-graph2-post.gv create mode 100644 docs/chapter06/06-graph2-post.json create mode 100644 docs/chapter06/06-graph2-post.svg create mode 100644 docs/chapter06/06-graph2-pre.gv create mode 100644 docs/chapter06/06-graph2-pre.json create mode 100644 docs/chapter06/06-graph2-pre.svg create mode 100644 docs/chapter06/06-graph3-false.gv create mode 100644 docs/chapter06/06-graph3-false.svg create mode 100644 docs/chapter06/06-graph3-nonconst-peephole.gv create mode 100644 docs/chapter06/06-graph3-nonconst-peephole.json create mode 100644 docs/chapter06/06-graph3-nonconst-peephole.svg create mode 100644 docs/chapter06/06-graph3-nonconst.gv create mode 100644 docs/chapter06/06-graph3-nonconst.json create mode 100644 docs/chapter06/06-graph3-nonconst.svg create mode 100644 docs/chapter06/06-graph3-true.gv create mode 100644 docs/chapter06/06-graph3-true.svg create mode 100644 docs/chapter06/06-graph4-arg2.gv create mode 100644 docs/chapter06/06-graph4-arg2.svg create mode 100644 docs/chapter06/06-graph4-nonconst.gv create mode 100644 docs/chapter06/06-graph4-nonconst.svg create mode 100644 docs/chapter06/06-graph4-true.gv create mode 100644 docs/chapter06/06-graph4-true.svg create mode 100644 docs/chapter06/Makefile create mode 100644 docs/chapter06/README.ja.md create mode 100644 docs/chapter06/README.md create mode 100644 docs/chapter06/lattice.gv create mode 100644 docs/chapter06/lattice.svg (limited to 'docs/chapter06') diff --git a/docs/chapter06/06-graph1-post.gv b/docs/chapter06/06-graph1-post.gv new file mode 100644 index 00000000..31480991 --- /dev/null +++ b/docs/chapter06/06-graph1-post.gv @@ -0,0 +1,29 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_12 [ label="#2" ]; + Return13 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return13[taillabel=0 color=red]; + Return13 -> Start2:p0[taillabel=0 color=red]; + Return13 -> Con_12[taillabel=1]; +} diff --git a/docs/chapter06/06-graph1-post.json b/docs/chapter06/06-graph1-post.json new file mode 100644 index 00000000..325d473a --- /dev/null +++ b/docs/chapter06/06-graph1-post.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph1-post.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": null}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph1-post.svg b/docs/chapter06/06-graph1-post.svg new file mode 100644 index 00000000..7c58b6c3 --- /dev/null +++ b/docs/chapter06/06-graph1-post.svg @@ -0,0 +1,80 @@ +#3[0] → #13 · CTRL#13[0] → #1 · CTRL#13[1] → #12 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #13 CTRL0#2  #12#12 #2 +Type not computed + +Return  #13#13 Return +Type not computed + +[0] → #1 CTRL +[1] → #12 DATA01 diff --git a/docs/chapter06/06-graph1-pre.gv b/docs/chapter06/06-graph1-pre.gv new file mode 100644 index 00000000..2bfdd23d --- /dev/null +++ b/docs/chapter06/06-graph1-pre.gv @@ -0,0 +1,52 @@ +digraph chapter06 { +/* +if( true ) return 2; +return 1; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#1" ]; + If7 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_11 [ label="#2" ]; + Return12 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_13 [ label="#~CONTROL" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Con_15 [ label="#1" ]; + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region14;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return12[taillabel=0 color=red]; + Stop3 -> Return16[taillabel=1 color=red]; + If7 -> Start2:p0[taillabel=0 color=red]; + If7 -> Con_6[taillabel=1]; + Return12 -> If7:p0[taillabel=0 color=red]; + Return12 -> Con_11[taillabel=1]; + Region14 -> Con_13[taillabel=1]; + Region14 -> If7:p1[taillabel=2 color=red]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Con_15[taillabel=1]; +} diff --git a/docs/chapter06/06-graph1-pre.json b/docs/chapter06/06-graph1-pre.json new file mode 100644 index 00000000..18615f2c --- /dev/null +++ b/docs/chapter06/06-graph1-pre.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph1-pre.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 12, "role": "CTRL", "label": null}, {"idx": 1, "def": 16, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}], "proj": {"par": 7, "idx": 0}}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 7, "role": "CTRL", "label": null}], "proj": {"par": 7, "idx": 1}}, + {"id": 6, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 11, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 12, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 11, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "#~CONTROL", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 15, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph1-pre.svg b/docs/chapter06/06-graph1-pre.svg new file mode 100644 index 00000000..693ddba6 --- /dev/null +++ b/docs/chapter06/06-graph1-pre.svg @@ -0,0 +1,111 @@ +#3[0] → #12 · CTRL#3[1] → #16 · CTRL#7[0] → #1 · CTRL#7[1] → #6 · DATA#12[0] → #4 · CTRL#12[1] → #11 · DATA#14[1] → #13 · DATA#14[2] → #5 · CTRL#16[0] → #14 · CTRL#16[1] → #15 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #12 CTRL +[1] → #16 CTRL01True  #4/0#4 True +Projection 0 of #7 +Type not computed + +[0] → #7 CTRLFalse  #5/1#5 False +Projection 1 of #7 +Type not computed + +[0] → #7 CTRL#1  #6#6 #1 +Type not computed + +If  #7#7 If +Type not computed + +[0] → #1 CTRL +[1] → #6 DATA01#2  #11#11 #2 +Type not computed + +Return  #12#12 Return +Type not computed + +[0] → #4 CTRL +[1] → #11 DATA01#~CONTROL  #13#13 #~CONTROL +Type not computed + +Region  #14#14 Region +Type not computed + +[0] → — DATA +[1] → #13 DATA +[2] → #5 CTRL012#1  #15#15 #1 +Type not computed + +Return  #16#16 Return +Type not computed + +[0] → #14 CTRL +[1] → #15 DATA01 diff --git a/docs/chapter06/06-graph2-post.gv b/docs/chapter06/06-graph2-post.gv new file mode 100644 index 00000000..61ae2ca1 --- /dev/null +++ b/docs/chapter06/06-graph2-post.gv @@ -0,0 +1,33 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_13 [ label="#2" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return17 -> Start2:p0[taillabel=0 color=red]; + Return17 -> Con_13[taillabel=1]; + Stop3 -> Return17[taillabel=0 color=red]; +} diff --git a/docs/chapter06/06-graph2-post.json b/docs/chapter06/06-graph2-post.json new file mode 100644 index 00000000..31be64c2 --- /dev/null +++ b/docs/chapter06/06-graph2-post.json @@ -0,0 +1,16 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph2-post.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}], "proj": null}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 13, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter06/06-graph2-post.svg b/docs/chapter06/06-graph2-post.svg new file mode 100644 index 00000000..a87af3ec --- /dev/null +++ b/docs/chapter06/06-graph2-post.svg @@ -0,0 +1,80 @@ +#3[0] → #17 · CTRL#17[0] → #1 · CTRL#17[1] → #13 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #17 CTRL0#2  #13#13 #2 +Type not computed + +Return  #17#17 Return +Type not computed + +[0] → #1 CTRL +[1] → #13 DATA01 diff --git a/docs/chapter06/06-graph2-pre.gv b/docs/chapter06/06-graph2-pre.gv new file mode 100644 index 00000000..d183b4c4 --- /dev/null +++ b/docs/chapter06/06-graph2-pre.gv @@ -0,0 +1,55 @@ +digraph chapter06 { +/* +int a=1; +if( true ) + a=2; +else + a=3; +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Return16 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="#1" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_12 [ label="#2" ]; + Con_13 [ label="#3" ]; + Region14 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a15 [ style=filled fillcolor=lightyellow label="φ_a" ]; + { rank=same; Region14;Phi_a15;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Return16 -> Region14[taillabel=0 color=red]; + Return16 -> Phi_a15[taillabel=1]; + Stop3 -> Return16[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Con_7[taillabel=1]; + Region14 -> If8:p0[taillabel=1 color=red]; + Region14 -> If8:p1[taillabel=2 color=red]; + Phi_a15 -> Region14 [style=dotted taillabel=0]; + Phi_a15 -> Con_12[taillabel=1]; + Phi_a15 -> Con_13[taillabel=2]; +} diff --git a/docs/chapter06/06-graph2-pre.json b/docs/chapter06/06-graph2-pre.json new file mode 100644 index 00000000..fd187946 --- /dev/null +++ b/docs/chapter06/06-graph2-pre.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph2-pre.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 16, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 5, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 4, "role": "CTRL", "label": null}, {"idx": 2, "def": 5, "role": "CTRL", "label": null}], "proj": null}, + {"id": 15, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 14, "role": "ASSOC", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 14, "role": "CTRL", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [4, 5, 8, 14, 15]} + ] +} diff --git a/docs/chapter06/06-graph2-pre.svg b/docs/chapter06/06-graph2-pre.svg new file mode 100644 index 00000000..f787b4dc --- /dev/null +++ b/docs/chapter06/06-graph2-pre.svg @@ -0,0 +1,108 @@ +#3[0] → #16 · CTRL#8[0] → #1 · CTRL#8[1] → #7 · DATA#14[1] → #4 · CTRL#14[2] → #5 · CTRL#15[1] → #12 · DATA#15[2] → #13 · DATA#16[0] → #14 · CTRL#16[1] → #15 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #16 CTRL0True  #4/0#4 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRLFalse  #5/1#5 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRL#1  #7#7 #1 +Type not computed + +If  #8#8 If +Type not computed + +[0] → #1 CTRL +[1] → #7 DATA01#2  #12#12 #2 +Type not computed + +#3  #13#13 #3 +Type not computed + +Region  #14#14 Region +Type not computed + +[0] → — DATA +[1] → #4 CTRL +[2] → #5 CTRL012φ_a  #15#15 φ_a +Type not computed + +[0] → #14 ASSOC +[1] → #12 DATA +[2] → #13 DATA[0] → #14012Return  #16#16 Return +Type not computed + +[0] → #14 CTRL +[1] → #15 DATA01If  #8If · 5 nodes−Fold region diff --git a/docs/chapter06/06-graph3-false.gv b/docs/chapter06/06-graph3-false.gv new file mode 100644 index 00000000..28f741fa --- /dev/null +++ b/docs/chapter06/06-graph3-false.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_30 [ label="#1" ]; + Return31 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return31[taillabel=0 color=red]; + Return31 -> Start2:p0[taillabel=0 color=red]; + Return31 -> Con_30[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-false.svg b/docs/chapter06/06-graph3-false.svg new file mode 100644 index 00000000..49b04f09 --- /dev/null +++ b/docs/chapter06/06-graph3-false.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return31 + +Return + + + +Stop3->Return31 + + +0 + + + +Con_30 + +#1 + + + +Return31->Start2:p0 + + +0 + + + +Return31->Con_30 + + +1 + + + diff --git a/docs/chapter06/06-graph3-nonconst-peephole.gv b/docs/chapter06/06-graph3-nonconst-peephole.gv new file mode 100644 index 00000000..f8e3e5fa --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.gv @@ -0,0 +1,56 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_27 [ label="#4" ]; + Con_29 [ label="#1" ]; + Phi_ab30 [ style=filled fillcolor=lightyellow label="φ_ab" ]; + Return31 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region22;Phi_ab30;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return31[taillabel=0 color=red]; + Region22 -> If8:p0[taillabel=1 color=red]; + Region22 -> If8:p1[taillabel=2 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Start2:p1[taillabel=1]; + Phi_ab30 -> Region22 [style=dotted taillabel=0]; + Phi_ab30 -> Con_27[taillabel=1]; + Phi_ab30 -> Con_29[taillabel=2]; + Return31 -> Region22[taillabel=0 color=red]; + Return31 -> Phi_ab30[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-nonconst-peephole.json b/docs/chapter06/06-graph3-nonconst-peephole.json new file mode 100644 index 00000000..7f1f183c --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.json @@ -0,0 +1,24 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph3-nonconst-peephole.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 31, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 22, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "CTRL", "label": null}, {"idx": 2, "def": 6, "role": "CTRL", "label": null}], "proj": null}, + {"id": 27, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 29, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 30, "label": "φ_ab", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 22, "role": "ASSOC", "label": null}, {"idx": 1, "def": 27, "role": "DATA", "label": null}, {"idx": 2, "def": 29, "role": "DATA", "label": null}], "proj": null}, + {"id": 31, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 22, "role": "CTRL", "label": null}, {"idx": 1, "def": 30, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [5, 6, 8, 22, 30]} + ] +} diff --git a/docs/chapter06/06-graph3-nonconst-peephole.svg b/docs/chapter06/06-graph3-nonconst-peephole.svg new file mode 100644 index 00000000..a60d66f9 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst-peephole.svg @@ -0,0 +1,109 @@ +#3[0] → #31 · CTRL#8[0] → #1 · CTRL#8[1] → #4 · DATA#22[1] → #5 · CTRL#22[2] → #6 · CTRL#30[1] → #27 · DATA#30[2] → #29 · DATA#31[0] → #22 · CTRL#31[1] → #30 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #31 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRLFalse  #6/1#6 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRLIf  #8#8 If +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA01Region  #22#22 Region +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #6 CTRL012#4  #27#27 #4 +Type not computed + +#1  #29#29 #1 +Type not computed + +φ_ab  #30#30 φ_ab +Type not computed + +[0] → #22 ASSOC +[1] → #27 DATA +[2] → #29 DATA[0] → #22012Return  #31#31 Return +Type not computed + +[0] → #22 CTRL +[1] → #30 DATA01If  #8If · 5 nodes−Fold region diff --git a/docs/chapter06/06-graph3-nonconst.gv b/docs/chapter06/06-graph3-nonconst.gv new file mode 100644 index 00000000..7cd4e8e2 --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.gv @@ -0,0 +1,86 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#0" ]; + Con_7 [ label="#1" ]; + If8 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_12 [ label="#2" ]; + If13 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_17 [ label="#2" ]; + Con_18 [ label="#3" ]; + Region19 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b20 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region21 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a22 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b23 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Add24 [ label="+" ]; + Return25 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region19;Phi_b20;} + { rank=same; Region21;Phi_b23;Phi_a22;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return25[taillabel=0 color=red]; + If8 -> Start2:p0[taillabel=0 color=red]; + If8 -> Start2:p1[taillabel=1]; + If13 -> If8:p0[taillabel=0 color=red]; + If13 -> Start2:p1[taillabel=1]; + Region19 -> If13:p0[taillabel=1 color=red]; + Region19 -> If13:p1[taillabel=2 color=red]; + Phi_b20 -> Region19 [style=dotted taillabel=0]; + Phi_b20 -> Con_17[taillabel=1]; + Phi_b20 -> Con_18[taillabel=2]; + Region21 -> Region19[taillabel=1 color=red]; + Region21 -> If8:p1[taillabel=2 color=red]; + Phi_a22 -> Region21 [style=dotted taillabel=0]; + Phi_a22 -> Con_12[taillabel=1]; + Phi_a22 -> Con_6[taillabel=2]; + Phi_b23 -> Region21 [style=dotted taillabel=0]; + Phi_b23 -> Phi_b20[taillabel=1]; + Phi_b23 -> Con_7[taillabel=2]; + Add24 -> Phi_b23[taillabel=1]; + Add24 -> Phi_a22[taillabel=2]; + Return25 -> Region21[taillabel=0 color=red]; + Return25 -> Add24[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-nonconst.json b/docs/chapter06/06-graph3-nonconst.json new file mode 100644 index 00000000..77bb6d2c --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.json @@ -0,0 +1,35 @@ +{ + "ver": 1, + "comp": "chapter06/docs/06-graph3-nonconst.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": null}, + {"id": 4, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 5, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 0}}, + {"id": 6, "label": "#0", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 7, "label": "#1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 8, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 8, "role": "CTRL", "label": null}], "proj": {"par": 8, "idx": 1}}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": {"par": 13, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 13, "role": "CTRL", "label": null}], "proj": {"par": 13, "idx": 1}}, + {"id": 12, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 13, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 18, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 19, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "CTRL", "label": null}, {"idx": 2, "def": 11, "role": "CTRL", "label": null}], "proj": null}, + {"id": 20, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 19, "role": "ASSOC", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}, {"idx": 2, "def": 18, "role": "DATA", "label": null}], "proj": null}, + {"id": 21, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 19, "role": "CTRL", "label": null}, {"idx": 2, "def": 9, "role": "CTRL", "label": null}], "proj": null}, + {"id": 22, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 12, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 21, "role": "ASSOC", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 24, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 23, "role": "DATA", "label": null}, {"idx": 2, "def": 22, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 21, "role": "CTRL", "label": null}, {"idx": 1, "def": 24, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 8, "par": 0, "nodes": [5, 8, 9, 21, 22, 23, 24]}, + {"id": 13, "par": 8, "nodes": [10, 11, 13, 19, 20]} + ] +} diff --git a/docs/chapter06/06-graph3-nonconst.svg b/docs/chapter06/06-graph3-nonconst.svg new file mode 100644 index 00000000..2e4ec0fc --- /dev/null +++ b/docs/chapter06/06-graph3-nonconst.svg @@ -0,0 +1,150 @@ +#3[0] → #25 · CTRL#8[0] → #1 · CTRL#8[1] → #4 · DATA#13[0] → #5 · CTRL#13[1] → #4 · DATA#19[1] → #10 · CTRL#19[2] → #11 · CTRL#20[1] → #17 · DATA#20[2] → #18 · DATA#21[1] → #19 · CTRL#21[2] → #9 · CTRL#22[1] → #12 · DATA#22[2] → #6 · DATA#23[1] → #20 · DATA#23[2] → #7 · DATA#24[1] → #23 · DATA#24[2] → #22 · DATA#25[0] → #21 · CTRL#25[1] → #24 · DATA$ctrl  #1/0#1 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLStart  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #25 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #8 +Type not computed + +[0] → #8 CTRL#0  #6#6 #0 +Type not computed + +#1  #7#7 #1 +Type not computed + +If  #8#8 If +Type not computed + +[0] → #1 CTRL +[1] → #4 DATA01False  #9/1#9 False +Projection 1 of #8 +Type not computed + +[0] → #8 CTRLTrue  #10/0#10 True +Projection 0 of #13 +Type not computed + +[0] → #13 CTRLFalse  #11/1#11 False +Projection 1 of #13 +Type not computed + +[0] → #13 CTRL#2  #12#12 #2 +Type not computed + +If  #13#13 If +Type not computed + +[0] → #5 CTRL +[1] → #4 DATA01#2  #17#17 #2 +Type not computed + +#3  #18#18 #3 +Type not computed + +Region  #19#19 Region +Type not computed + +[0] → — DATA +[1] → #10 CTRL +[2] → #11 CTRL012φ_b  #20#20 φ_b +Type not computed + +[0] → #19 ASSOC +[1] → #17 DATA +[2] → #18 DATA[0] → #19012Region  #21#21 Region +Type not computed + +[0] → — DATA +[1] → #19 CTRL +[2] → #9 CTRL012φ_a  #22#22 φ_a +Type not computed + +[0] → #21 ASSOC +[1] → #12 DATA +[2] → #6 DATA[0] → #21012φ_b  #23#23 φ_b +Type not computed + +[0] → #21 ASSOC +[1] → #20 DATA +[2] → #7 DATA[0] → #21012+  #24#24 + +Type not computed + +[0] → — DATA +[1] → #23 DATA +[2] → #22 DATA012Return  #25#25 Return +Type not computed + +[0] → #21 CTRL +[1] → #24 DATA01If  #8If · 12 nodes−Fold regionIf  #13If · 5 nodes−Fold region diff --git a/docs/chapter06/06-graph3-true.gv b/docs/chapter06/06-graph3-true.gv new file mode 100644 index 00000000..9739169c --- /dev/null +++ b/docs/chapter06/06-graph3-true.gv @@ -0,0 +1,35 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_28 [ label="#4" ]; + Return29 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return29[taillabel=0 color=red]; + Return29 -> Start2:p0[taillabel=0 color=red]; + Return29 -> Con_28[taillabel=1]; +} diff --git a/docs/chapter06/06-graph3-true.svg b/docs/chapter06/06-graph3-true.svg new file mode 100644 index 00000000..7e573cc6 --- /dev/null +++ b/docs/chapter06/06-graph3-true.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return29 + +Return + + + +Stop3->Return29 + + +0 + + + +Con_28 + +#4 + + + +Return29->Start2:p0 + + +0 + + + +Return29->Con_28 + + +1 + + + diff --git a/docs/chapter06/06-graph4-arg2.gv b/docs/chapter06/06-graph4-arg2.gv new file mode 100644 index 00000000..7d6913e2 --- /dev/null +++ b/docs/chapter06/06-graph4-arg2.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_44 [ label="#5" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-arg2.svg b/docs/chapter06/06-graph4-arg2.svg new file mode 100644 index 00000000..8ec80be4 --- /dev/null +++ b/docs/chapter06/06-graph4-arg2.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return45 + +Return + + + +Stop3->Return45 + + +0 + + + +Con_44 + +#5 + + + +Return45->Start2:p0 + + +0 + + + +Return45->Con_44 + + +1 + + + diff --git a/docs/chapter06/06-graph4-nonconst.gv b/docs/chapter06/06-graph4-nonconst.gv new file mode 100644 index 00000000..b8899b48 --- /dev/null +++ b/docs/chapter06/06-graph4-nonconst.gv @@ -0,0 +1,122 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_6 [ label="#0" ]; + Con_7 [ label="#1" ]; + Con_8 [ label="#0" ]; + If9 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_13 [ label="#1" ]; + Con_14 [ label="#2" ]; + EQNode15 [ label="==" ]; + If16 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_20 [ label="#2" ]; + Con_21 [ label="#3" ]; + Region22 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_c23 [ style=filled fillcolor=lightyellow label="φ_c" ]; + If24 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_28 [ label="#2" ]; + Con_29 [ label="#3" ]; + Region30 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_b31 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Region32 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a33 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b34 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Phi_c35 [ style=filled fillcolor=lightyellow label="φ_c" ]; + Add36 [ label="+" ]; + Add37 [ label="+" ]; + Return38 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region22;Phi_c23;} + { rank=same; Region30;Phi_b31;} + { rank=same; Region32;Phi_c35;Phi_a33;Phi_b34;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return38[taillabel=0 color=red]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> Start2:p1[taillabel=1]; + EQNode15 -> Start2:p1[taillabel=1]; + EQNode15 -> Con_14[taillabel=2]; + If16 -> If9:p0[taillabel=0 color=red]; + If16 -> EQNode15[taillabel=1]; + Region22 -> If16:p0[taillabel=1 color=red]; + Region22 -> If16:p1[taillabel=2 color=red]; + Phi_c23 -> Region22 [style=dotted taillabel=0]; + Phi_c23 -> Con_20[taillabel=1]; + Phi_c23 -> Con_21[taillabel=2]; + If24 -> Region22[taillabel=0 color=red]; + If24 -> Start2:p1[taillabel=1]; + Region30 -> If24:p0[taillabel=1 color=red]; + Region30 -> If24:p1[taillabel=2 color=red]; + Phi_b31 -> Region30 [style=dotted taillabel=0]; + Phi_b31 -> Con_28[taillabel=1]; + Phi_b31 -> Con_29[taillabel=2]; + Region32 -> Region30[taillabel=1 color=red]; + Region32 -> If9:p1[taillabel=2 color=red]; + Phi_a33 -> Region32 [style=dotted taillabel=0]; + Phi_a33 -> Con_13[taillabel=1]; + Phi_a33 -> Con_6[taillabel=2]; + Phi_b34 -> Region32 [style=dotted taillabel=0]; + Phi_b34 -> Phi_b31[taillabel=1]; + Phi_b34 -> Con_7[taillabel=2]; + Phi_c35 -> Region32 [style=dotted taillabel=0]; + Phi_c35 -> Phi_c23[taillabel=1]; + Phi_c35 -> Con_8[taillabel=2]; + Add36 -> Phi_c35[taillabel=1]; + Add36 -> Phi_b34[taillabel=2]; + Add37 -> Add36[taillabel=1]; + Add37 -> Phi_a33[taillabel=2]; + Return38 -> Region32[taillabel=0 color=red]; + Return38 -> Add37[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-nonconst.svg b/docs/chapter06/06-graph4-nonconst.svg new file mode 100644 index 00000000..d38c3636 --- /dev/null +++ b/docs/chapter06/06-graph4-nonconst.svg @@ -0,0 +1,456 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return38 + +Return + + + +Stop3->Return38 + + +0 + + + +Con_6 + +#0 + + + +Con_7 + +#1 + + + +Con_8 + +#0 + + + +If9 + + +If + + + +True + + +False + + + +If9->Start2:p0 + + +0 + + + +If9->Start2:p1 + + +1 + + + +Con_13 + +#1 + + + +Con_14 + +#2 + + + +EQNode15 + +== + + + +EQNode15->Start2:p1 + + +1 + + + +EQNode15->Con_14 + + +2 + + + +If16 + + +If + + + +True + + +False + + + +If16->If9:p0 + + +0 + + + +If16->EQNode15 + + +1 + + + +Con_20 + +#2 + + + +Con_21 + +#3 + + + +Region22 + +Region + + + +Region22->If16:p0 + + +1 + + + +Region22->If16:p1 + + +2 + + + +Phi_c23 + +φ_c + + + +Phi_c23->Con_20 + + +1 + + + +Phi_c23->Con_21 + + +2 + + + +Phi_c23->Region22 + + +0 + + + +If24 + + +If + + + +True + + +False + + + +If24->Start2:p1 + + +1 + + + +If24->Region22 + + +0 + + + +Con_28 + +#2 + + + +Con_29 + +#3 + + + +Region30 + +Region + + + +Region30->If24:p0 + + +1 + + + +Region30->If24:p1 + + +2 + + + +Phi_b31 + +φ_b + + + +Phi_b31->Con_28 + + +1 + + + +Phi_b31->Con_29 + + +2 + + + +Phi_b31->Region30 + + +0 + + + +Region32 + +Region + + + +Region32->If9:p1 + + +2 + + + +Region32->Region30 + + +1 + + + +Phi_a33 + +φ_a + + + +Phi_a33->Con_6 + + +2 + + + +Phi_a33->Con_13 + + +1 + + + +Phi_a33->Region32 + + +0 + + + +Phi_b34 + +φ_b + + + +Phi_b34->Con_7 + + +2 + + + +Phi_b34->Phi_b31 + + +1 + + + +Phi_b34->Region32 + + +0 + + + +Phi_c35 + +φ_c + + + +Phi_c35->Con_8 + + +2 + + + +Phi_c35->Phi_c23 + + +1 + + + +Phi_c35->Region32 + + +0 + + + +Add36 + ++ + + + +Add36->Phi_b34 + + +2 + + + +Add36->Phi_c35 + + +1 + + + +Add37 + ++ + + + +Add37->Phi_a33 + + +2 + + + +Add37->Add36 + + +1 + + + +Return38->Region32 + + +0 + + + +Return38->Add37 + + +1 + + + diff --git a/docs/chapter06/06-graph4-true.gv b/docs/chapter06/06-graph4-true.gv new file mode 100644 index 00000000..6e48ee7d --- /dev/null +++ b/docs/chapter06/06-graph4-true.gv @@ -0,0 +1,37 @@ +digraph chapter06 { +/* +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrl
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_44 [ label="#6" ]; + Return45 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return45[taillabel=0 color=red]; + Return45 -> Start2:p0[taillabel=0 color=red]; + Return45 -> Con_44[taillabel=1]; +} diff --git a/docs/chapter06/06-graph4-true.svg b/docs/chapter06/06-graph4-true.svg new file mode 100644 index 00000000..a533ea21 --- /dev/null +++ b/docs/chapter06/06-graph4-true.svg @@ -0,0 +1,67 @@ + + + + + + +chapter06 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return45 + +Return + + + +Stop3->Return45 + + +0 + + + +Con_44 + +#6 + + + +Return45->Start2:p0 + + +0 + + + +Return45->Con_44 + + +1 + + + diff --git a/docs/chapter06/Makefile b/docs/chapter06/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter06/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter06/README.ja.md b/docs/chapter06/README.ja.md new file mode 100644 index 00000000..bf2766eb --- /dev/null +++ b/docs/chapter06/README.ja.md @@ -0,0 +1,168 @@ +# 第6章: If のピープホール最適化 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第5章](../chapter05/README.ja.md) | +[次の章: 第7章](../chapter07/README.ja.md) + +文法は[第5章](../chapter05/05-grammar.ja.md)から変わりません。 + +# 目次 + +1. [型システムの改訂](#型システムの改訂) +2. [`if` のピープホール最適化](#if-のピープホール最適化) +3. [`Region` と `Phi`](#region-と-phi) +4. [考察](#考察) +5. [定数式以外へのピープホール最適化の拡張](#定数式以外へのピープホール最適化の拡張) +6. [支配ノード](#支配ノード) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter06) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter05...linear-chapter06) することもできます。 + +この章では新しい言語機能は追加しません。目標は、`if` 文にピープホール最適化を追加することです。 + +## 型システムの改訂 + +整数の部分束に加えて、別の束構造を導入するよう型システムを拡張する必要があります。これまでと同じく、「トップ」を T、「ボトム」を ⊥ と表記します。 + +* 「Ctrl」は生きた制御を、「~Ctrl」は死んだ制御を表します。 +* 「INT」は整数値を表します。整数値は独自の部分束を持つことに注意してください。 + +| | ⊥ | Ctrl | ~Ctrl | T | INT | +|-------|---|------|-------|-------|-----| +| T | ⊥ | Ctrl | ~Ctrl | T | INT | +| Ctrl | ⊥ | Ctrl | Ctrl | Ctrl | ⊥ | +| ~Ctrl | ⊥ | Ctrl | ~Ctrl | ~Ctrl | ⊥ | +| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | + +* 「トップ」と任意の型の meet は、その型です。 +* 「ボトム」と任意の型の meet は、「ボトム」です。 +* 「トップ」「ボトム」「Ctrl」「~Ctrl」は単純型に分類します。 +* 「Ctrl」と「~Ctrl」の meet は「Ctrl」です。 +* 上記で扱っていない場合、単純型と非単純型の meet の結果は「ボトム」です。 + +改訂した束の全体を次に示します。 + +![束](./lattice.svg) + +## `if` のピープホール最適化 + +* 基本方針は、一方の分岐が死んでいるとわかっていても、`if` 文全体の解析を続けることです。 +* この方法では死んだノードを作り、デッドコード除去で片付けます。解析時に特別なロジックを導入せず、通常のグラフ構築の仕組みで死んだノードを片付けられるという利点があります。 +* `If` ノードをピープホール最適化するとき、条件が定数かどうかを調べます。定数なら、それが `0` かどうかによって、どちらか一方の分岐が死にます。 +* この場合、`Proj` ノードを追加する時点で一方の射影が死んでいるとわかっています。その `Proj` ノードのピープホール最適化では、`Proj` を、死んだ制御を示す「~Ctrl」型の `Constant` に置き換えます。 +* この時点では `If` ノードに利用側がないため、デッドコード除去はそれを削除しようとします。しかし解析を続ける必要があるので、まだ削除できません。重要なのは、*両方の `Proj` ノードを作った後なら `If` ノードを削除できる* ということです。その後の制御フローから見えるのは `Proj` ノードだけだからです。 +* これを保証するため、最初の `Proj` を作る前に `If` にダミーの利用側を追加し、作成直後に取り除きます。こうして2つ目の `Proj` が `If` のデッドコード除去を引き起こせるようにします。 +* 生きた `Proj` は `If` の親に、死んだ `Proj` は「~Ctrl」に置き換えます。 +* その後、解析は通常どおり続きます。 +* ほかに変わるのは、死んだ制御を伴ってマージ地点に到達したときです。 +* 同じ方針に従い、`Phi` ノードの作成も含めて通常どおりマージします。 +* `Region` の入力の1つが「~Ctrl」になっている場合があります。`Phi` はこれを見て自身を最適化します。生きた入力が1つだけなら、`Phi` のピープホール最適化は自身を残りの入力に置き換えます。 +* 最後に `Region` ノードをピープホール最適化するとき、生きた入力が1つしかなく、Phi の利用側もないとわかれば、その1つの生きた入力に置き換えられます。 + +## `Region` と `Phi` + +維持する不変条件の1つは、`Region` の各制御入力が、すべての `Phi` のデータ入力と1対1に対応することです。したがって、`Region` が制御入力を失ったら、各 `Phi` の対応するデータ入力も削除しなければなりません。逆に、依存する `Phi` がなくなるまでは Region を簡約できません。 + +`If` を処理するときは `Region` の制御入力を取り除かず、死んだ制御入力に単に `Constant(~Ctrl)` を設定します。`Phi` のピープホールロジックはそれに気付き、自身を生きた入力に置き換えます。 + +## 考察 + +上記の変更により、`if` 文の条件がコンパイル時に `true` または `false` に評価される場合、ピープホール最適化でデッドコードを畳み込めるようになります。 + +次の単純な例を見てみましょう。 + +```java +if( true ) return 2; +return 1; +``` + +ピープホール最適化前: + +![グラフ1・最適化前](./06-graph1-pre.svg) + +ピープホール最適化後: + +![グラフ1・最適化後](./06-graph1-post.svg) + +別の例: + +```java +int a=1; +if( true ) + a=2; +else + a=3; +return a; +``` + +ピープホール最適化前: + +![グラフ2・最適化前](./06-graph2-pre.svg) + +ピープホール最適化後: + +![グラフ2・最適化後](./06-graph2-post.svg) + +## 定数式以外へのピープホール最適化の拡張 + +`CFG` のピープホール最適化は、式がコンパイル時の定数ならデッドコードを簡約します。しかし、次の例では可能な最適化を十分に行えていません。 + +```java +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +``` + +この例では `arg` が外部で定義されるため、定数ではないと仮定しなければなりません。ただし、内側の `if` 文で `if( arg )` という条件を繰り返しています。外側の `if( arg )` が true なら、*内側の `if` も必ず true に評価される* とわかります。 + +現在のピープホール最適化には、これが見えません。 + +![グラフ3・非定数](./06-graph3-nonconst.svg) + +ピープホール最適化に、内側の `if` が外側の `if` によって完全に決定されると認識させ、コードを次のように簡単にしたいのです。 + +```java +int a = 0; +int b = 1; +if ( arg ) { + a = 2; + b = 2; +} +return a+b; +``` + +つまり、最終結果は、`arg` が true なら `4`、false なら `1` です。 + +## 支配ノード + +このピープホール最適化を実装する鍵は、内側の `if` が外側の `if` によって完全に決定されるという観察です。コンパイラの用語では、外側の `if` が内側の `if` を支配するといいます。 + +この種の支配関係を判定する一般的な方法は、支配木（dominator tree）を構築することです。その詳細は論文 `A Simple, Fast Dominance Algorithm` を参照してください。[^1] + +ただし、支配木の構築は高コストで、解析の途中では行いたくありません。幸い、まだループがないので、制御フローグラフにバックエッジもありません。制御フローグラフは本質的に階層的で、木のような形です。そのため、単純な方法で支配ノードを特定できます。 + +基本的な考えは、各制御ノードに、階層内での深さを表す `depth` を付けることです。必要に応じて、この深さを漸進的に計算できます。階層の深い位置にあるノードは、上にあるノードより大きな深さを持ちます。 + +次に、`Region` 以外の制御ノードには入ってくる制御エッジが1つしかないので、ほとんどの制御ノードには直接支配ノード（immediate dominator）が1つだけあるとわかります。`Region` ノードは制御エッジを1本以上持ちうるため異なります。ただし `if` 文の場合、`Region` ノードは `if` の各分岐から1つずつ、ちょうど2つの制御入力を持ちます。この `if` に限った状況で `Region` ノードの直接支配ノードを見つけるには、各分岐の直接支配ノードをたどり、両方の分岐を支配する共通の祖先ノードを見つけます。 + +この祖先ノードも `if` で、条件が現在の `if` と同じなら、現在の `if` の結果は完全に決定されるとわかります。 + +この確認を行うコードは、[`If` の `compute` メソッド](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java#L38-L45) にあります。 + +`Node` の `idom` メソッドは、深さに基づく直接支配ノードの計算のデフォルト実装を提供します。`Region` は [これをオーバーライド](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java#L57-L74) し、上記のより複雑な探索を実装します。 + +上の例を簡約するには、[`Add` ノードにさらにピープホール最適化を追加](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java#L64-L67) する必要もあるとわかります。 + +これらすべての変更によって、ピープホール最適化の結果は望んでいたとおりになります！ + +![グラフ3・非定数のピープホール最適化](./06-graph3-nonconst-peephole.svg) + +[^1]: Cooper, K. D. Cooper, Harvey, T. J., and Kennedy, K. (2001). + A Simple, Fast Dominance Algorithm. diff --git a/docs/chapter06/README.md b/docs/chapter06/README.md new file mode 100644 index 00000000..74c28116 --- /dev/null +++ b/docs/chapter06/README.md @@ -0,0 +1,207 @@ +# Chapter 6: Peepholes for If + +English | [日本語](README.ja.md) + +[Previous: Chapter 5](../chapter05/README.md) | +[Next: Chapter 7](../chapter07/README.md) + +The grammar is unchanged from [Chapter 5](../chapter05/05-grammar.md). + +# Table of Contents + +1. [Type System Revision](#type-system-revision) +2. [Peephole of `if`](#peephole-of-if) +3. [`Region` and `Phi`](#region-and-phi) +4. [Discussion](#discussion) +5. [Expanding Peephole Beyond Constant Expressions](#expanding-peephole-beyond-constant-expressions) +6. [Dominators](#dominators) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter06) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter05...linear-chapter06) it to the previous chapter. + +In this chapter we do not add new language features. Our goal is to add peephole optimization to `if` statements. + + +## Type System Revision + +We now need to extend the type system to introduce another lattice structure, in addition to the Integer sub-lattice. +As before we denote "Top" by T and "Bottom" by ⊥. + +* "Ctrl" represents a live control, whereas "~Ctrl" represents a dead control. +* "INT" refers to an integer value, note that integer values have their own sub-lattice. + +| | ⊥ | Ctrl | ~Ctrl | T | INT | +|-------|---|------|-------|-------|-----| +| T | ⊥ | Ctrl | ~Ctrl | T | INT | +| Ctrl | ⊥ | Ctrl | Ctrl | Ctrl | ⊥ | +| ~Ctrl | ⊥ | Ctrl | ~Ctrl | ~Ctrl | ⊥ | +| ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | ⊥ | + +* "Top" meets any type is that type, +* "Bottom" meets any type is "Bottom", +* "Top", "Bottom", "Ctrl", "~Ctrl" are classed as simple types, +* "Ctrl" meets "~Ctrl" is "Ctrl" +* Unless covered above, a simple type meets non-simple results in "Bottom" + +The entire revised Lattice is shown below: + +![Lattice](./lattice.svg) + + +## Peephole of `if` + +* Our general strategy is to continue parsing the entire `if` statement even if we know that one branch is dead. +* This approach creates dead nodes which get cleaned up by dead code + elimination. The benefits are that we do not introduce special logic during + parsing, the normal graph building machinery takes care of cleaning up dead + nodes. +* When we peephole an `If` node we test if the predicate is a constant. If so, + then one branch or the other is dead, depending on if the constant is `0` or not. +* When we add the `Proj` nodes, in this scenario, we already know one of the projections is dead. The peephole of the + relevant `Proj` node replaces the `Proj` with a `Constant` of type "~Ctrl" indicating dead control. +* At this point our dead code elimination would kill the `If` node since it has no uses + - but we cannot do that because we need to continue the parse. The + important observation is that *we __can__ kill the `If` node after __both__ + the `Proj` nodes have been created*, because any subsequent control flow can + only see the `Proj` nodes. +* To ensure this, we add a dummy user to `If` before creating the first `Proj` and remove it immediately after, allowing the + second `Proj` to trigger a dead code elimination of the `If`. +* The live `Proj` gets replaced by the parent of `If`, whereas the dead `Proj` gets replaced by "~Ctrl". +* The parsing then continues as normal. +* The other changes are when we reach the merge point with a dead control. +* Again keeping with our strategy we merge as normal, including creating `Phi` nodes. +* The `Region` may have one of its inputs as "~Ctrl". This will be seen + by the `Phi` which then optimizes itself. If the `Phi` has just one live + input, the `Phi` peephole replaces itself with the remaining input. +* Finally, at the end, when the `Region` node is peepholed, we see that it has only one live input and no Phi uses + and can be replaced with its one live input. + +## `Region` and `Phi` + +One of the invariants we maintain is that for each control input to a +`Region` every `Phi` has a 1-to-1 relationship with a data input. Thus, if a +`Region` loses a control input, every `Phi`'s corresponding data input must be +deleted. Conversely, we cannot collapse a Region until it has no dependent +`Phi`s. + +When processing `If` we do not remove control inputs to a `Region`, instead the +dead control input is simply set to `Constant(~Ctrl)`. The peephole logic in +a `Phi` notices this and replaces itself with the live input. + +## Discussion + +With the changes above, our peephole optimization is able to fold dead code when +an `if` statement has a condition that evaluates to `true` or `false` at compile time. + +Let's look at a simple example below: + +```java +if( true ) return 2; +return 1; +``` + +Before peephole: + +![Graph1-Pre](./06-graph1-pre.svg) + +After peephole: + +![Graph1-Post](./06-graph1-post.svg) + +Another example: + +```java +int a=1; +if( true ) + a=2; +else + a=3; +return a; +``` + +Before peephole: + +![Graph2-Pre](./06-graph2-pre.svg) + +After peephole: + +![Graph2-Post](./06-graph2-post.svg) + +## Expanding Peephole Beyond Constant Expressions + +While our peephole of the `CFG` collapses dead code when the expression is +a compile-time constant, it does not do as well as it could with the following example: + +```java +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +``` + +In this example, `arg` is defined externally, and we have to assume it is not a constant. +However, the code repeats the `if( arg )` condition in the inner `if` statement. +We know that if the outer `if( arg )` is true, then the *inner `if` must also evaluate to true*. + +Our peephole at present cannot see this: + +![Graph3-NonConst](./06-graph3-nonconst.svg) + +What we would like is for our peephole to see that the inner `if` is fully determined by the +outer `if` and thus, the code can be simplified as follows: + +```java +int a = 0; +int b = 1; +if ( arg ) { + a = 2; + b = 2; +} +return a+b; +``` + +That is, the final outcome is either `4` if `arg` happens to be true, or `1` if `arg` happens to be false. + +## Dominators + +The key to implementing this peephole is the observation that the inner `if` is completely determined by the +outer `if`. In compiler parlance, we say that the outer `if` dominates the inner `if`. + +There is a generic way to determine this type of domination; it involves constructing a dominator +tree. For details of how to do this, please refer to the paper `A Simple, Fast Dominance Algorithm`.[^1] + +However, constructing a dominator tree is an expensive operation; one that we would not like to +do in the middle of parsing. Fortunately, since we do not have loops yet, we do not +have back edges in our control flow graph. Our control flow graph is essentially hierarchical, tree like. +Thus, a simple form of dominator identification is possible. + +The main idea is that we can assign a `depth` to each control node, this represents the node's depth +in the hierarchy. We can compute this depth incrementally as we need to. The nodes that are deeper in the hierarchy +have a greater depth than the ones above. + +Secondly we know that for our control nodes, except for `Region`s, there is only one incoming control edge, +which means that most control nodes have a single immediate dominating control node. `Region` nodes are different +as they can have one or more control edges; but, we know that for `if` statements, a `Region` node has exactly two +control inputs, one from each branch of the `if`. To find the immediate dominator of a `Region` node in the +limited scenario of an `if`, we can follow the immediate dominator of each branch until we find the common ancestor +node that dominates both the branches. + +If this ancestor node is also an `if` and its predicate is the same as the current `if`, then we know that +the outcome of the present `if` is fully determined. + +The code that does this check is in the [`compute` method of the `if`](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java#L38-L45). + +The `idom` method in `Node` provides a default implementation of the depth based immediate dominator calculation. +`Region` [overrides this](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java#L57-L74) to implement the more complex search described above. + +It turns out that to simplify the example above, we need a [further peephole in our `Add` node](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java#L64-L67). + +With all these changes, the outcome of the peephole is just what we would like to see! + +![Graph3-NonConst-Peephole](./06-graph3-nonconst-peephole.svg) + +[^1]: Cooper, K. D. Cooper, Harvey, T. J., and Kennedy, K. (2001). + A Simple, Fast Dominance Algorithm. diff --git a/docs/chapter06/lattice.gv b/docs/chapter06/lattice.gv new file mode 100644 index 00000000..e5cc59be --- /dev/null +++ b/docs/chapter06/lattice.gv @@ -0,0 +1,97 @@ +digraph Lattice { + // Define nodes + splines=false; + node [shape=circle, style=filled, fillcolor=lightblue]; + nodesep=0.6; + + TOP [label=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<⊤:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<⊥:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + TOP -> INT_TOP; + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + INT_BOT -> BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
tuple
type
...
type
+ >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // Additional customization + {rank=same; TOP} + {rank=same; XCTRL; INT_TOP; TUPLE_TOP} + {rank=same; + INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; + } + {rank=same; CTRL; INT_BOT, TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter06/lattice.svg b/docs/chapter06/lattice.svg new file mode 100644 index 00000000..86371c93 --- /dev/null +++ b/docs/chapter06/lattice.svg @@ -0,0 +1,319 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +⊤ +:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥ +:ctrl + + + +XCTRL->CTRL + + + + + +CTRL->BOT + + + + + +INT_MIN + +-n + + + +INT_TOP->INT_MIN + + + + + +INT_MINDOTS + +... + + + +INT_TOP->INT_MINDOTS + + + + + +INT_MINUS + +-1 + + + +INT_TOP->INT_MINUS + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_PLUS + +1 + + + +INT_TOP->INT_PLUS + + + + + +INT_MAXDOTS + +... + + + +INT_TOP->INT_MAXDOTS + + + + + +INT_MAX + ++n + + + +INT_TOP->INT_MAX + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +INT_MIN->INT_BOT + + + + + + +INT_MINDOTS->INT_BOT + + + + + + +INT_MINUS->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_PLUS->INT_BOT + + + + + + +INT_MAXDOTS->INT_BOT + + + + + + +INT_MAX->INT_BOT + + + + + +TUPLE1 + + + +tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + -- cgit v1.2.3