From 628620ce49255f1b80dceee8ef3fa3e6945a0cce 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: Hadházy Tamás Co-authored-by: Dibyendu Majumdar Co-authored-by: Darrick Wiebe Co-authored-by: Claude Opus 5 --- docs/chapter09/09-grammar.md | 94 +++++++++++++ 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.md | 310 ++++++++++++++++++++++++++++++++++++++++++ 21 files changed, 1383 insertions(+) create mode 100644 docs/chapter09/09-grammar.md 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.md (limited to 'docs') diff --git a/docs/chapter09/09-grammar.md b/docs/chapter09/09-grammar.md new file mode 100644 index 00000000..00f93e04 --- /dev/null +++ b/docs/chapter09/09-grammar.md @@ -0,0 +1,94 @@ +# Grammar for Chapter 8 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +declStatement + : 'int' IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | primaryExpression + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | '(' expression ')' + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter09/09-graph1.gv b/docs/chapter09/09-graph1.gv new file mode 100644 index 00000000..e6d1851a --- /dev/null +++ b/docs/chapter09/09-graph1.gv @@ -0,0 +1,67 @@ +digraph chapter08 { +/* +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Stop3 [ shape=box style=filled fillcolor=yellow label="Stop" ]; + Con_7 [ label="2" ]; + Mul8 [ label="*" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_16 [ label="2" ]; + Mul17 [ label="*" ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Con_20 [ label="1" ]; + Add21 [ label="+" ]; + Return24 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + Stop3 -> Return24[taillabel=1 color=red]; + Mul8 -> Start2:p1[taillabel=1]; + Mul8 -> Con_7[taillabel=2]; + LT10 -> Start2:p1[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Start2:p0[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Mul17 -> Start2:p1[taillabel=1]; + Mul17 -> Con_16[taillabel=2]; + Return18 -> If11:p0[taillabel=0 color=red]; + Return18 -> Mul17[taillabel=1]; + Add21 -> Mul8[taillabel=1]; + Add21 -> Con_20[taillabel=2]; + Return24 -> If11:p1[taillabel=0 color=red]; + Return24 -> Add21[taillabel=1]; +} diff --git a/docs/chapter09/09-graph1.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.md b/docs/chapter09/README.md new file mode 100644 index 00000000..c327b20d --- /dev/null +++ b/docs/chapter09/README.md @@ -0,0 +1,310 @@ +# Chapter 9: Global Value Numbering and Iterative Peepholes + +[Previous: Chapter 8](../chapter08/README.md) | +[Next: Chapter 10](../chapter10/README.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. [Other Concerns](#other-concerns) +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