From f5ad15e3699c0d07ab2b06865f3a8ae209d021d0 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 27 Oct 2023 20:35:04 +0100 Subject: Chapter 5: If Statement, Phi, and Region MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Yichen Yan Co-authored-by: Thalia Archibald Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamas Hadhazy 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: RobertObkircher Co-authored-by: Jun Kawasaki Co-authored-by: David Rubin <87927264+Rexicon226@users.noreply.github.com> --- docs/chapter05/05-grammar.ja.md | 86 ++++++++ docs/chapter05/05-grammar.md | 81 ++++++++ docs/chapter05/05-graph1.gv | 88 +++++++++ docs/chapter05/05-graph1.json | 25 +++ docs/chapter05/05-graph1.svg | 120 +++++++++++ docs/chapter05/05-graph2.gv | 78 ++++++++ docs/chapter05/05-graph2.json | 27 +++ docs/chapter05/05-graph2.svg | 125 ++++++++++++ docs/chapter05/05-graph3.gv | 66 +++++++ docs/chapter05/05-graph3.json | 28 +++ docs/chapter05/05-graph3.svg | 127 ++++++++++++ docs/chapter05/05-graph4.gv | 63 ++++++ docs/chapter05/05-graph4.json | 19 ++ docs/chapter05/05-graph4.svg | 95 +++++++++ docs/chapter05/05-graph5.gv | 60 ++++++ docs/chapter05/05-graph5.json | 18 ++ docs/chapter05/05-graph5.svg | 90 +++++++++ docs/chapter05/05-graph6.gv | 58 ++++++ docs/chapter05/05-graph6.json | 15 ++ docs/chapter05/05-graph6.svg | 78 ++++++++ docs/chapter05/05-graph7.gv | 72 +++++++ docs/chapter05/05-graph7.json | 22 +++ docs/chapter05/05-graph7.svg | 108 ++++++++++ docs/chapter05/05-graph8.gv | 129 ++++++++++++ docs/chapter05/05-graph8.json | 45 +++++ docs/chapter05/05-graph8.svg | 188 ++++++++++++++++++ docs/chapter05/05-graph9.json | 26 +++ docs/chapter05/05-graph9.svg | 117 +++++++++++ docs/chapter05/Makefile | 1 + docs/chapter05/README.ja.md | 345 ++++++++++++++++++++++++++++++++ docs/chapter05/README.md | 426 ++++++++++++++++++++++++++++++++++++++++ 31 files changed, 2826 insertions(+) create mode 100644 docs/chapter05/05-grammar.ja.md create mode 100644 docs/chapter05/05-grammar.md create mode 100644 docs/chapter05/05-graph1.gv create mode 100644 docs/chapter05/05-graph1.json create mode 100644 docs/chapter05/05-graph1.svg create mode 100644 docs/chapter05/05-graph2.gv create mode 100644 docs/chapter05/05-graph2.json create mode 100644 docs/chapter05/05-graph2.svg create mode 100644 docs/chapter05/05-graph3.gv create mode 100644 docs/chapter05/05-graph3.json create mode 100644 docs/chapter05/05-graph3.svg create mode 100644 docs/chapter05/05-graph4.gv create mode 100644 docs/chapter05/05-graph4.json create mode 100644 docs/chapter05/05-graph4.svg create mode 100644 docs/chapter05/05-graph5.gv create mode 100644 docs/chapter05/05-graph5.json create mode 100644 docs/chapter05/05-graph5.svg create mode 100644 docs/chapter05/05-graph6.gv create mode 100644 docs/chapter05/05-graph6.json create mode 100644 docs/chapter05/05-graph6.svg create mode 100644 docs/chapter05/05-graph7.gv create mode 100644 docs/chapter05/05-graph7.json create mode 100644 docs/chapter05/05-graph7.svg create mode 100644 docs/chapter05/05-graph8.gv create mode 100644 docs/chapter05/05-graph8.json create mode 100644 docs/chapter05/05-graph8.svg create mode 100644 docs/chapter05/05-graph9.json create mode 100644 docs/chapter05/05-graph9.svg create mode 100644 docs/chapter05/Makefile create mode 100644 docs/chapter05/README.ja.md create mode 100644 docs/chapter05/README.md (limited to 'docs') diff --git a/docs/chapter05/05-grammar.ja.md b/docs/chapter05/05-grammar.ja.md new file mode 100644 index 00000000..65b293f9 --- /dev/null +++ b/docs/chapter05/05-grammar.ja.md @@ -0,0 +1,86 @@ +# 第5章の文法 + +[English](05-grammar.md) | 日本語 + +この文書は [原文](05-grammar.md) の日本語訳です。 + + +[第5章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + ; + +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/chapter05/05-grammar.md b/docs/chapter05/05-grammar.md new file mode 100644 index 00000000..2be5a8a5 --- /dev/null +++ b/docs/chapter05/05-grammar.md @@ -0,0 +1,81 @@ +# Grammar for Chapter 5 + +English | [日本語](05-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + ; + +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/chapter05/05-graph1.gv b/docs/chapter05/05-graph1.gv new file mode 100644 index 00000000..b5cf8370 --- /dev/null +++ b/docs/chapter05/05-graph1.gv @@ -0,0 +1,88 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + +} + +return a; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1a
>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope12_0 { + Scope12_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope12_1 { + Scope12_1 [label=< + + +
1a
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0; color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_$ctrl" -> If9:p0; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Add14; + edge [style=dashed color=cornflowerblue]; + Scope12_0:"Scope12_0_$ctrl" -> If9:p1; + Scope12_0:"Scope12_0_arg" -> Start2:p1; + Scope12_1:"Scope12_1_a" -> Sub16; +} diff --git a/docs/chapter05/05-graph1.json b/docs/chapter05/05-graph1.json new file mode 100644 index 00000000..a2b4a7bd --- /dev/null +++ b/docs/chapter05/05-graph1.json @@ -0,0 +1,25 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph1.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 11, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 10, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 14, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 12, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 10, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 16, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 6, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 7, "label": "#1", "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": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 6, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 11, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 12, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 10, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph1.svg b/docs/chapter05/05-graph1.svg new file mode 100644 index 00000000..0a75532a --- /dev/null +++ b/docs/chapter05/05-graph1.svg @@ -0,0 +1,120 @@ +#1[0] → #11 · ASSOC · 0: $ctrl#1[1] → #10 · ASSOC · 0: arg#1[2] → #14 · ASSOC · 1: a#4[0] → #12 · ASSOC · 0: $ctrl#4[1] → #10 · ASSOC · 0: arg#4[2] → #16 · ASSOC · 1: a#8[1] → #10 · DATA#8[2] → #7 · DATA#9[0] → #6 · CTRL#9[1] → #8 · DATA#14[1] → #10 · DATA#14[2] → #13 · DATA#16[1] → #10 · DATA#16[2] → #15 · DATAScope  #1#1 Scope +Type not computed + +[0] → #11 ASSOC 0: $ctrl +[1] → #10 ASSOC 0: arg +[2] → #14 ASSOC 1: a0: $ctrl0: arg1: a012Start  #2#2 Start +Type not computed + +Scope  #4#4 Scope +Type not computed + +[0] → #12 ASSOC 0: $ctrl +[1] → #10 ASSOC 0: arg +[2] → #16 ASSOC 1: a0: $ctrl0: arg1: a012$ctrl  #6/0#6 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRL#1  #7#7 #1 +Type not computed + +==  #8#8 == +Type not computed + +[0] → — DATA +[1] → #10 DATA +[2] → #7 DATA012If  #9#9 If +Type not computed + +[0] → #6 CTRL +[1] → #8 DATA01arg  #10/1#10 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #11/0#11 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRLFalse  #12/1#12 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRL#2  #13#13 #2 +Type not computed + ++  #14#14 + +Type not computed + +[0] → — DATA +[1] → #10 DATA +[2] → #13 DATA012#3  #15#15 #3 +Type not computed + +-  #16#16 - +Type not computed + +[0] → — DATA +[1] → #10 DATA +[2] → #15 DATA012 diff --git a/docs/chapter05/05-graph2.gv b/docs/chapter05/05-graph2.gv new file mode 100644 index 00000000..a560bc49 --- /dev/null +++ b/docs/chapter05/05-graph2.gv @@ -0,0 +1,78 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + +} + +return a; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Con_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + Region17 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a18 [ style=filled fillcolor=lightyellow label="φ_a" ]; + { rank=same; Region17;Phi_a18;} + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1a
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + Region17 -> If9:p0[taillabel=1 color=red]; + Region17 -> If9:p1[taillabel=2 color=red]; + Phi_a18 -> Region17 [style=dotted taillabel=0]; + Phi_a18 -> Add14[taillabel=1]; + Phi_a18 -> Sub16[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_$ctrl" -> Region17; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Phi_a18; +} diff --git a/docs/chapter05/05-graph2.json b/docs/chapter05/05-graph2.json new file mode 100644 index 00000000..5980da2b --- /dev/null +++ b/docs/chapter05/05-graph2.json @@ -0,0 +1,27 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph2.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 5, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 18, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 4, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 5, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 6, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 7, "label": "#1", "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": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 4, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "-", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 5, "role": "DATA", "label": null}, {"idx": 2, "def": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 6, "role": "CTRL", "label": null}, {"idx": 2, "def": 10, "role": "CTRL", "label": null}], "proj": null}, + {"id": 18, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [6, 8, 9, 10, 14, 16, 17, 18]} + ] +} diff --git a/docs/chapter05/05-graph2.svg b/docs/chapter05/05-graph2.svg new file mode 100644 index 00000000..f073e342 --- /dev/null +++ b/docs/chapter05/05-graph2.svg @@ -0,0 +1,125 @@ +#1[0] → #17 · ASSOC · 0: $ctrl#1[1] → #5 · ASSOC · 0: arg#1[2] → #18 · ASSOC · 1: a#8[1] → #5 · DATA#8[2] → #7 · DATA#9[0] → #4 · CTRL#9[1] → #8 · DATA#14[1] → #5 · DATA#14[2] → #13 · DATA#16[1] → #5 · DATA#16[2] → #15 · DATA#17[1] → #6 · CTRL#17[2] → #10 · CTRL#18[1] → #14 · DATA#18[2] → #16 · DATAScope  #1#1 Scope +Type not computed + +[0] → #17 ASSOC 0: $ctrl +[1] → #5 ASSOC 0: arg +[2] → #18 ASSOC 1: a0: $ctrl0: arg1: a012Start  #2#2 Start +Type not computed + +$ctrl  #4/0#4 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLarg  #5/1#5 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #6/0#6 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRL#1  #7#7 #1 +Type not computed + +==  #8#8 == +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #7 DATA012If  #9#9 If +Type not computed + +[0] → #4 CTRL +[1] → #8 DATA01False  #10/1#10 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRL#2  #13#13 #2 +Type not computed + ++  #14#14 + +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #13 DATA012#3  #15#15 #3 +Type not computed + +-  #16#16 - +Type not computed + +[0] → — DATA +[1] → #5 DATA +[2] → #15 DATA012Region  #17#17 Region +Type not computed + +[0] → — DATA +[1] → #6 CTRL +[2] → #10 CTRL012φ_a  #18#18 φ_a +Type not computed + +[0] → #17 ASSOC +[1] → #14 DATA +[2] → #16 DATA[0] → #17012If  #9If · 8 nodes−Fold region diff --git a/docs/chapter05/05-graph3.gv b/docs/chapter05/05-graph3.gv new file mode 100644 index 00000000..688c5ca9 --- /dev/null +++ b/docs/chapter05/05-graph3.gv @@ -0,0 +1,66 @@ +digraph chapter05 { +/* +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + +} + +return a; +*/ + 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_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_13 [ label="#2" ]; + Add14 [ label="+" ]; + Con_15 [ label="#3" ]; + Sub16 [ label="-" ]; + Region17 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a18 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region17;Phi_a18;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + Add14 -> Start2:p1[taillabel=1]; + Add14 -> Con_13[taillabel=2]; + Sub16 -> Start2:p1[taillabel=1]; + Sub16 -> Con_15[taillabel=2]; + Region17 -> If9:p0[taillabel=1 color=red]; + Region17 -> If9:p1[taillabel=2 color=red]; + Phi_a18 -> Region17 [style=dotted taillabel=0]; + Phi_a18 -> Add14[taillabel=1]; + Phi_a18 -> Sub16[taillabel=2]; + Return19 -> Region17[taillabel=0 color=red]; + Return19 -> Phi_a18[taillabel=1]; +} diff --git a/docs/chapter05/05-graph3.json b/docs/chapter05/05-graph3.json new file mode 100644 index 00000000..16d74821 --- /dev/null +++ b/docs/chapter05/05-graph3.json @@ -0,0 +1,28 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph3.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": 19, "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": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 7, "label": "#1", "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": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "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": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "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": 15, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "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": 18, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [5, 6, 8, 9, 14, 16, 17, 18]} + ] +} diff --git a/docs/chapter05/05-graph3.svg b/docs/chapter05/05-graph3.svg new file mode 100644 index 00000000..5a8b5706 --- /dev/null +++ b/docs/chapter05/05-graph3.svg @@ -0,0 +1,127 @@ +#3[0] → #19 · CTRL#8[1] → #4 · DATA#8[2] → #7 · DATA#9[0] → #1 · CTRL#9[1] → #8 · DATA#14[1] → #4 · DATA#14[2] → #13 · DATA#16[1] → #4 · DATA#16[2] → #15 · DATA#17[1] → #5 · CTRL#17[2] → #6 · CTRL#18[1] → #14 · DATA#18[2] → #16 · DATA#19[0] → #17 · CTRL#19[1] → #18 · 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] → #19 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRLFalse  #6/1#6 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRL#1  #7#7 #1 +Type not computed + +==  #8#8 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #7 DATA012If  #9#9 If +Type not computed + +[0] → #1 CTRL +[1] → #8 DATA01#2  #13#13 #2 +Type not computed + ++  #14#14 + +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #13 DATA012#3  #15#15 #3 +Type not computed + +-  #16#16 - +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #15 DATA012Region  #17#17 Region +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #6 CTRL012φ_a  #18#18 φ_a +Type not computed + +[0] → #17 ASSOC +[1] → #14 DATA +[2] → #16 DATA[0] → #17012Return  #19#19 Return +Type not computed + +[0] → #17 CTRL +[1] → #18 DATA01If  #9If · 8 nodes−Fold region diff --git a/docs/chapter05/05-graph4.gv b/docs/chapter05/05-graph4.gv new file mode 100644 index 00000000..88120b4a --- /dev/null +++ b/docs/chapter05/05-graph4.gv @@ -0,0 +1,63 @@ +digraph chapter05 { +/* +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +*/ + 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="#2" ]; + EQNode7 [ label="==" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_14 [ label="#3" ]; + EQNode15 [ label="==" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a17 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return18 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_a17;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return18[taillabel=0 color=red]; + EQNode7 -> Start2:p1[taillabel=1]; + EQNode7 -> Con_6[taillabel=2]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + EQNode15 -> Start2:p1[taillabel=1]; + EQNode15 -> Con_14[taillabel=2]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_a17 -> Region16 [style=dotted taillabel=0]; + Phi_a17 -> EQNode15[taillabel=1]; + Phi_a17 -> EQNode7[taillabel=2]; + Return18 -> Region16[taillabel=0 color=red]; + Return18 -> Phi_a17[taillabel=1]; +} diff --git a/docs/chapter05/05-graph4.json b/docs/chapter05/05-graph4.json new file mode 100644 index 00000000..a23b54f7 --- /dev/null +++ b/docs/chapter05/05-graph4.json @@ -0,0 +1,19 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph4.svg", + "step": 1, + "roots": [18], + "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": "#2", "type": null, "kind": "DATA", "edges": [], "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": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 15, "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": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 17, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 15, "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": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph4.svg b/docs/chapter05/05-graph4.svg new file mode 100644 index 00000000..45a3d3f3 --- /dev/null +++ b/docs/chapter05/05-graph4.svg @@ -0,0 +1,95 @@ +#7[1] → #4 · DATA#7[2] → #6 · DATA#15[1] → #4 · DATA#15[2] → #14 · DATA#17[1] → #15 · DATA#17[2] → #7 · DATA#18[1] → #17 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA#2  #6#6 #2 +Type not computed + +==  #7#7 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #6 DATA012#3  #14#14 #3 +Type not computed + +==  #15#15 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #14 DATA012φ_a  #17#17 φ_a +Type not computed + +[0] → — ASSOC +[1] → #15 DATA +[2] → #7 DATA012Return  #18#18 Return +Type not computed + +[0] → — CTRL +[1] → #17 DATA01 diff --git a/docs/chapter05/05-graph5.gv b/docs/chapter05/05-graph5.gv new file mode 100644 index 00000000..b03e90b5 --- /dev/null +++ b/docs/chapter05/05-graph5.gv @@ -0,0 +1,60 @@ +digraph chapter05 { +/* +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +*/ + 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="#2" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_14 [ label="#3" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a19 [ style=filled fillcolor=lightyellow label="φ_a" ]; + EQNode20 [ label="==" ]; + Return21 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_a19;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return21[taillabel=0 color=red]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_a19 -> Region16 [style=dotted taillabel=0]; + Phi_a19 -> Con_14[taillabel=1]; + Phi_a19 -> Con_6[taillabel=2]; + EQNode20 -> Start2:p1[taillabel=1]; + EQNode20 -> Phi_a19[taillabel=2]; + Return21 -> Region16[taillabel=0 color=red]; + Return21 -> EQNode20[taillabel=1]; +} diff --git a/docs/chapter05/05-graph5.json b/docs/chapter05/05-graph5.json new file mode 100644 index 00000000..3bce2865 --- /dev/null +++ b/docs/chapter05/05-graph5.json @@ -0,0 +1,18 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-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": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 19, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "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": 4, "role": "DATA", "label": null}, {"idx": 2, "def": 19, "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": 20, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph5.svg b/docs/chapter05/05-graph5.svg new file mode 100644 index 00000000..df1144a9 --- /dev/null +++ b/docs/chapter05/05-graph5.svg @@ -0,0 +1,90 @@ +#19[1] → #14 · DATA#19[2] → #6 · DATA#20[1] → #4 · DATA#20[2] → #19 · DATA#21[1] → #20 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA#2  #6#6 #2 +Type not computed + +#3  #14#14 #3 +Type not computed + +φ_a  #19#19 φ_a +Type not computed + +[0] → — ASSOC +[1] → #14 DATA +[2] → #6 DATA012==  #20#20 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #19 DATA012Return  #21#21 Return +Type not computed + +[0] → — CTRL +[1] → #20 DATA01 diff --git a/docs/chapter05/05-graph6.gv b/docs/chapter05/05-graph6.gv new file mode 100644 index 00000000..1ad7b94a --- /dev/null +++ b/docs/chapter05/05-graph6.gv @@ -0,0 +1,58 @@ +digraph chapter05 { +/* +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return 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="#3" ]; + Con_8 [ label="#1" ]; + EQNode9 [ label="==" ]; + If10 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_15 [ label="#4" ]; + Region16 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_c17 [ style=filled fillcolor=lightyellow label="φ_c" ]; + Return19 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region16;Phi_c17;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return19[taillabel=0 color=red]; + EQNode9 -> Start2:p1[taillabel=1]; + EQNode9 -> Con_8[taillabel=2]; + If10 -> Start2:p0[taillabel=0 color=red]; + If10 -> EQNode9[taillabel=1]; + Region16 -> If10:p0[taillabel=1 color=red]; + Region16 -> If10:p1[taillabel=2 color=red]; + Phi_c17 -> Region16 [style=dotted taillabel=0]; + Phi_c17 -> Con_15[taillabel=1]; + Phi_c17 -> Con_6[taillabel=2]; + Return19 -> Region16[taillabel=0 color=red]; + Return19 -> Phi_c17[taillabel=1]; +} diff --git a/docs/chapter05/05-graph6.json b/docs/chapter05/05-graph6.json new file mode 100644 index 00000000..536b320c --- /dev/null +++ b/docs/chapter05/05-graph6.json @@ -0,0 +1,15 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph6.svg", + "step": 1, + "roots": [19], + "scope": 0, + "nodes": [ + {"id": 6, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 15, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "label": "φ_c", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 15, "role": "DATA", "label": null}, {"idx": 2, "def": 6, "role": "DATA", "label": null}], "proj": null}, + {"id": 19, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 17, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph6.svg b/docs/chapter05/05-graph6.svg new file mode 100644 index 00000000..f58a541f --- /dev/null +++ b/docs/chapter05/05-graph6.svg @@ -0,0 +1,78 @@ +#17[1] → #15 · DATA#17[2] → #6 · DATA#19[1] → #17 · DATA#3  #6#6 #3 +Type not computed + +#4  #15#15 #4 +Type not computed + +φ_c  #17#17 φ_c +Type not computed + +[0] → — ASSOC +[1] → #15 DATA +[2] → #6 DATA012Return  #19#19 Return +Type not computed + +[0] → — CTRL +[1] → #17 DATA01 diff --git a/docs/chapter05/05-graph7.gv b/docs/chapter05/05-graph7.gv new file mode 100644 index 00000000..3abd6455 --- /dev/null +++ b/docs/chapter05/05-graph7.gv @@ -0,0 +1,72 @@ +digraph chapter05 { +/* +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +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" ]; + Phi_b37 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Con_10 [ label="#1" ]; + Add42 [ label="+" ]; + EQNode11 [ label="==" ]; + If12 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_46 [ label="#4" ]; + Con_48 [ label="#5" ]; + Phi_ab49 [ style=filled fillcolor=lightyellow label="φ_ab" ]; + Add50 [ label="+" ]; + Con_19 [ label="#2" ]; + Return51 [ shape=box style=filled fillcolor=yellow label="Return" ]; + Mul20 [ label="*" ]; + Region31 [ shape=box style=filled fillcolor=yellow label="Region" ]; + { rank=same; Region31;Phi_b37;Phi_ab49;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return51[taillabel=0 color=red]; + Phi_b37 -> Region31 [style=dotted taillabel=0]; + Phi_b37 -> Mul20[taillabel=1]; + Phi_b37 -> Start2:p1[taillabel=2]; + Add42 -> Phi_b37[taillabel=1]; + Add42 -> Start2:p1[taillabel=2]; + EQNode11 -> Start2:p1[taillabel=1]; + EQNode11 -> Con_10[taillabel=2]; + If12 -> Start2:p0[taillabel=0 color=red]; + If12 -> EQNode11[taillabel=1]; + Phi_ab49 -> Region31 [style=dotted taillabel=0]; + Phi_ab49 -> Con_46[taillabel=1]; + Phi_ab49 -> Con_48[taillabel=2]; + Add50 -> Add42[taillabel=1]; + Add50 -> Phi_ab49[taillabel=2]; + Return51 -> Region31[taillabel=0 color=red]; + Return51 -> Add50[taillabel=1]; + Mul20 -> Start2:p1[taillabel=1]; + Mul20 -> Con_19[taillabel=2]; + Region31 -> If12:p0[taillabel=1 color=red]; + Region31 -> If12:p1[taillabel=2 color=red]; +} diff --git a/docs/chapter05/05-graph7.json b/docs/chapter05/05-graph7.json new file mode 100644 index 00000000..2f4b4336 --- /dev/null +++ b/docs/chapter05/05-graph7.json @@ -0,0 +1,22 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph7.svg", + "step": 1, + "roots": [51], + "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": 19, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 20, "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": 19, "role": "DATA", "label": null}], "proj": null}, + {"id": 37, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 20, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 42, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 37, "role": "DATA", "label": null}, {"idx": 2, "def": 4, "role": "DATA", "label": null}], "proj": null}, + {"id": 46, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 48, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 49, "label": "φ_ab", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": null}, {"idx": 1, "def": 46, "role": "DATA", "label": null}, {"idx": 2, "def": 48, "role": "DATA", "label": null}], "proj": null}, + {"id": 50, "label": "+", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 42, "role": "DATA", "label": null}, {"idx": 2, "def": 49, "role": "DATA", "label": null}], "proj": null}, + {"id": 51, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 0, "role": "CTRL", "label": null}, {"idx": 1, "def": 50, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter05/05-graph7.svg b/docs/chapter05/05-graph7.svg new file mode 100644 index 00000000..b121e1b9 --- /dev/null +++ b/docs/chapter05/05-graph7.svg @@ -0,0 +1,108 @@ +#20[1] → #4 · DATA#20[2] → #19 · DATA#37[1] → #20 · DATA#37[2] → #4 · DATA#42[1] → #37 · DATA#42[2] → #4 · DATA#49[1] → #46 · DATA#49[2] → #48 · DATA#50[1] → #42 · DATA#50[2] → #49 · DATA#51[1] → #50 · DATAStart  #2#2 Start +Type not computed + +arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA#2  #19#19 #2 +Type not computed + +*  #20#20 * +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #19 DATA012φ_b  #37#37 φ_b +Type not computed + +[0] → — ASSOC +[1] → #20 DATA +[2] → #4 DATA012+  #42#42 + +Type not computed + +[0] → — DATA +[1] → #37 DATA +[2] → #4 DATA012#4  #46#46 #4 +Type not computed + +#5  #48#48 #5 +Type not computed + +φ_ab  #49#49 φ_ab +Type not computed + +[0] → — ASSOC +[1] → #46 DATA +[2] → #48 DATA012+  #50#50 + +Type not computed + +[0] → — DATA +[1] → #42 DATA +[2] → #49 DATA012Return  #51#51 Return +Type not computed + +[0] → — CTRL +[1] → #50 DATA01 diff --git a/docs/chapter05/05-graph8.gv b/docs/chapter05/05-graph8.gv new file mode 100644 index 00000000..8f28207c --- /dev/null +++ b/docs/chapter05/05-graph8.gv @@ -0,0 +1,129 @@ +digraph chapter05 { +/* +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; + +*/ + 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_7 [ label="#1" ]; + EQNode8 [ label="==" ]; + If9 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_13 [ label="#2" ]; + EQNode14 [ label="==" ]; + If15 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_19 [ label="#2" ]; + Con_20 [ label="#3" ]; + Region21 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a22 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Con_23 [ label="#3" ]; + EQNode24 [ label="==" ]; + If25 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_29 [ label="#4" ]; + Con_30 [ label="#5" ]; + Region31 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a32 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Region33 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a34 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Return35 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Region21;Phi_a22;} + { rank=same; Region31;Phi_a32;} + { rank=same; Region33;Phi_a34;} + } + node [shape=plaintext]; + subgraph cluster_Scope1_0 { + Scope1_0 [label=< + + +
0$ctrlarg
>]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1a
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return35[taillabel=0 color=red]; + EQNode8 -> Start2:p1[taillabel=1]; + EQNode8 -> Con_7[taillabel=2]; + If9 -> Start2:p0[taillabel=0 color=red]; + If9 -> EQNode8[taillabel=1]; + EQNode14 -> Start2:p1[taillabel=1]; + EQNode14 -> Con_13[taillabel=2]; + If15 -> If9:p0[taillabel=0 color=red]; + If15 -> EQNode14[taillabel=1]; + Region21 -> If15:p0[taillabel=1 color=red]; + Region21 -> If15:p1[taillabel=2 color=red]; + Phi_a22 -> Region21 [style=dotted taillabel=0]; + Phi_a22 -> Con_19[taillabel=1]; + Phi_a22 -> Con_20[taillabel=2]; + EQNode24 -> Start2:p1[taillabel=1]; + EQNode24 -> Con_23[taillabel=2]; + If25 -> If9:p1[taillabel=0 color=red]; + If25 -> EQNode24[taillabel=1]; + Region31 -> If25:p0[taillabel=1 color=red]; + Region31 -> If25:p1[taillabel=2 color=red]; + Phi_a32 -> Region31 [style=dotted taillabel=0]; + Phi_a32 -> Con_29[taillabel=1]; + Phi_a32 -> Con_30[taillabel=2]; + Region33 -> Region21[taillabel=1 color=red]; + Region33 -> Region31[taillabel=2 color=red]; + Phi_a34 -> Region33 [style=dotted taillabel=0]; + Phi_a34 -> Phi_a22[taillabel=1]; + Phi_a34 -> Phi_a32[taillabel=2]; + Return35 -> Region33[taillabel=0 color=red]; + Return35 -> Phi_a34[taillabel=1]; + edge [style=dashed color=cornflowerblue]; + Scope1_0:"Scope1_0_arg" -> Start2:p1; + Scope1_1:"Scope1_1_a" -> Phi_a34; +} diff --git a/docs/chapter05/05-graph8.json b/docs/chapter05/05-graph8.json new file mode 100644 index 00000000..887d1e8a --- /dev/null +++ b/docs/chapter05/05-graph8.json @@ -0,0 +1,45 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph8.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Scope", "type": null, "kind": "SCOPE", "edges": [{"idx": 0, "def": 0, "role": "ASSOC", "label": "0: $ctrl"}, {"idx": 1, "def": 6, "role": "ASSOC", "label": "0: arg"}, {"idx": 2, "def": 34, "role": "ASSOC", "label": "1: a"}], "proj": null}, + {"id": 2, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 3, "label": "Stop", "type": null, "kind": "STOP", "edges": [{"idx": 0, "def": 35, "role": "CTRL", "label": null}], "proj": null}, + {"id": 5, "label": "$ctrl", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 2, "role": "CTRL", "label": null}], "proj": {"par": 2, "idx": 0}}, + {"id": 6, "label": "arg", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": {"par": 2, "idx": 1}}, + {"id": 7, "label": "#1", "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": 6, "role": "DATA", "label": null}, {"idx": 2, "def": 7, "role": "DATA", "label": null}], "proj": null}, + {"id": 9, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 5, "role": "CTRL", "label": null}, {"idx": 1, "def": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 0}}, + {"id": 11, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 9, "role": "CTRL", "label": null}], "proj": {"par": 9, "idx": 1}}, + {"id": 12, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}], "proj": {"par": 15, "idx": 0}}, + {"id": 13, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 14, "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": 13, "role": "DATA", "label": null}], "proj": null}, + {"id": 15, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 10, "role": "CTRL", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}], "proj": null}, + {"id": 16, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 15, "role": "CTRL", "label": null}], "proj": {"par": 15, "idx": 1}}, + {"id": 17, "label": "True", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 0}}, + {"id": 18, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 25, "role": "CTRL", "label": null}], "proj": {"par": 25, "idx": 1}}, + {"id": 19, "label": "#2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 20, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 21, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 12, "role": "CTRL", "label": null}, {"idx": 2, "def": 16, "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": 19, "role": "DATA", "label": null}, {"idx": 2, "def": 20, "role": "DATA", "label": null}], "proj": null}, + {"id": 23, "label": "#3", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 24, "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": 23, "role": "DATA", "label": null}], "proj": null}, + {"id": 25, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 11, "role": "CTRL", "label": null}, {"idx": 1, "def": 24, "role": "DATA", "label": null}], "proj": null}, + {"id": 29, "label": "#4", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 30, "label": "#5", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 31, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 17, "role": "CTRL", "label": null}, {"idx": 2, "def": 18, "role": "CTRL", "label": null}], "proj": null}, + {"id": 32, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 31, "role": "ASSOC", "label": null}, {"idx": 1, "def": 29, "role": "DATA", "label": null}, {"idx": 2, "def": 30, "role": "DATA", "label": null}], "proj": null}, + {"id": 33, "label": "Region", "type": null, "kind": "REGION", "edges": [{"idx": 0, "def": 0, "role": "DATA", "label": null}, {"idx": 1, "def": 21, "role": "CTRL", "label": null}, {"idx": 2, "def": 31, "role": "CTRL", "label": null}], "proj": null}, + {"id": 34, "label": "φ_a", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 33, "role": "ASSOC", "label": null}, {"idx": 1, "def": 22, "role": "DATA", "label": null}, {"idx": 2, "def": 32, "role": "DATA", "label": null}], "proj": null}, + {"id": 35, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 33, "role": "CTRL", "label": null}, {"idx": 1, "def": 34, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 9, "par": 0, "nodes": [8, 9, 10, 11, 33, 34]}, + {"id": 15, "par": 9, "nodes": [12, 14, 15, 16, 21, 22]}, + {"id": 25, "par": 9, "nodes": [17, 18, 24, 25, 31, 32]} + ] +} diff --git a/docs/chapter05/05-graph8.svg b/docs/chapter05/05-graph8.svg new file mode 100644 index 00000000..b1b4da5c --- /dev/null +++ b/docs/chapter05/05-graph8.svg @@ -0,0 +1,188 @@ +#1[1] → #6 · ASSOC · 0: arg#1[2] → #34 · ASSOC · 1: a#3[0] → #35 · CTRL#8[1] → #6 · DATA#8[2] → #7 · DATA#9[0] → #5 · CTRL#9[1] → #8 · DATA#14[1] → #6 · DATA#14[2] → #13 · DATA#15[0] → #10 · CTRL#15[1] → #14 · DATA#21[1] → #12 · CTRL#21[2] → #16 · CTRL#22[1] → #19 · DATA#22[2] → #20 · DATA#24[1] → #6 · DATA#24[2] → #23 · DATA#25[0] → #11 · CTRL#25[1] → #24 · DATA#31[1] → #17 · CTRL#31[2] → #18 · CTRL#32[1] → #29 · DATA#32[2] → #30 · DATA#33[1] → #21 · CTRL#33[2] → #31 · CTRL#34[1] → #22 · DATA#34[2] → #32 · DATA#35[0] → #33 · CTRL#35[1] → #34 · DATAScope  #1#1 Scope +Type not computed + +[0] → — ASSOC 0: $ctrl +[1] → #6 ASSOC 0: arg +[2] → #34 ASSOC 1: a0: $ctrl0: arg1: a012Start  #2#2 Start +Type not computed + +Stop  #3#3 Stop +Type not computed + +[0] → #35 CTRL0$ctrl  #5/0#5 $ctrl +Projection 0 of #2 +Type not computed + +[0] → #2 CTRLarg  #6/1#6 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATA#1  #7#7 #1 +Type not computed + +==  #8#8 == +Type not computed + +[0] → — DATA +[1] → #6 DATA +[2] → #7 DATA012If  #9#9 If +Type not computed + +[0] → #5 CTRL +[1] → #8 DATA01True  #10/0#10 True +Projection 0 of #9 +Type not computed + +[0] → #9 CTRLFalse  #11/1#11 False +Projection 1 of #9 +Type not computed + +[0] → #9 CTRLTrue  #12/0#12 True +Projection 0 of #15 +Type not computed + +[0] → #15 CTRL#2  #13#13 #2 +Type not computed + +==  #14#14 == +Type not computed + +[0] → — DATA +[1] → #6 DATA +[2] → #13 DATA012If  #15#15 If +Type not computed + +[0] → #10 CTRL +[1] → #14 DATA01False  #16/1#16 False +Projection 1 of #15 +Type not computed + +[0] → #15 CTRLTrue  #17/0#17 True +Projection 0 of #25 +Type not computed + +[0] → #25 CTRLFalse  #18/1#18 False +Projection 1 of #25 +Type not computed + +[0] → #25 CTRL#2  #19#19 #2 +Type not computed + +#3  #20#20 #3 +Type not computed + +Region  #21#21 Region +Type not computed + +[0] → — DATA +[1] → #12 CTRL +[2] → #16 CTRL012φ_a  #22#22 φ_a +Type not computed + +[0] → #21 ASSOC +[1] → #19 DATA +[2] → #20 DATA[0] → #21012#3  #23#23 #3 +Type not computed + +==  #24#24 == +Type not computed + +[0] → — DATA +[1] → #6 DATA +[2] → #23 DATA012If  #25#25 If +Type not computed + +[0] → #11 CTRL +[1] → #24 DATA01#4  #29#29 #4 +Type not computed + +#5  #30#30 #5 +Type not computed + +Region  #31#31 Region +Type not computed + +[0] → — DATA +[1] → #17 CTRL +[2] → #18 CTRL012φ_a  #32#32 φ_a +Type not computed + +[0] → #31 ASSOC +[1] → #29 DATA +[2] → #30 DATA[0] → #31012Region  #33#33 Region +Type not computed + +[0] → — DATA +[1] → #21 CTRL +[2] → #31 CTRL012φ_a  #34#34 φ_a +Type not computed + +[0] → #33 ASSOC +[1] → #22 DATA +[2] → #32 DATA[0] → #33012Return  #35#35 Return +Type not computed + +[0] → #33 CTRL +[1] → #34 DATA01If  #9If · 18 nodes−Fold regionIf  #15If · 6 nodes−Fold regionIf  #25If · 6 nodes−Fold region diff --git a/docs/chapter05/05-graph9.json b/docs/chapter05/05-graph9.json new file mode 100644 index 00000000..deb1b540 --- /dev/null +++ b/docs/chapter05/05-graph9.json @@ -0,0 +1,26 @@ +{ + "ver": 1, + "comp": "chapter05/docs/05-graph9.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": 20, "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": 10, "role": "CTRL", "label": null}], "proj": {"par": 10, "idx": 0}}, + {"id": 6, "label": "False", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 10, "role": "CTRL", "label": null}], "proj": {"par": 10, "idx": 1}}, + {"id": 8, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 9, "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": 8, "role": "DATA", "label": null}], "proj": null}, + {"id": 10, "label": "If", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 9, "role": "DATA", "label": null}], "proj": null}, + {"id": 14, "label": "2", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 16, "label": "1", "type": null, "kind": "DATA", "edges": [], "proj": null}, + {"id": 17, "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": 18, "label": "φ_b", "type": null, "kind": "PHI", "edges": [{"idx": 0, "def": 17, "role": "ASSOC", "label": null}, {"idx": 1, "def": 14, "role": "DATA", "label": null}, {"idx": 2, "def": 16, "role": "DATA", "label": null}], "proj": null}, + {"id": 20, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 17, "role": "CTRL", "label": null}, {"idx": 1, "def": 18, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + {"id": 10, "par": 0, "nodes": [5, 6, 9, 10, 17, 18]} + ] +} diff --git a/docs/chapter05/05-graph9.svg b/docs/chapter05/05-graph9.svg new file mode 100644 index 00000000..d0f62b69 --- /dev/null +++ b/docs/chapter05/05-graph9.svg @@ -0,0 +1,117 @@ +#3[0] → #20 · CTRL#9[1] → #4 · DATA#9[2] → #8 · DATA#10[0] → #1 · CTRL#10[1] → #9 · DATA#17[1] → #5 · CTRL#17[2] → #6 · CTRL#18[1] → #14 · DATA#18[2] → #16 · DATA#20[0] → #17 · CTRL#20[1] → #18 · 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] → #20 CTRL0arg  #4/1#4 arg +Projection 1 of #2 +Type not computed + +[0] → #2 DATATrue  #5/0#5 True +Projection 0 of #10 +Type not computed + +[0] → #10 CTRLFalse  #6/1#6 False +Projection 1 of #10 +Type not computed + +[0] → #10 CTRL1  #8#8 1 +Type not computed + +==  #9#9 == +Type not computed + +[0] → — DATA +[1] → #4 DATA +[2] → #8 DATA012If  #10#10 If +Type not computed + +[0] → #1 CTRL +[1] → #9 DATA012  #14#14 2 +Type not computed + +1  #16#16 1 +Type not computed + +Region  #17#17 Region +Type not computed + +[0] → — DATA +[1] → #5 CTRL +[2] → #6 CTRL012φ_b  #18#18 φ_b +Type not computed + +[0] → #17 ASSOC +[1] → #14 DATA +[2] → #16 DATA[0] → #17012Return  #20#20 Return +Type not computed + +[0] → #17 CTRL +[1] → #18 DATA01If  #10If · 6 nodes−Fold region diff --git a/docs/chapter05/Makefile b/docs/chapter05/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter05/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter05/README.ja.md b/docs/chapter05/README.ja.md new file mode 100644 index 00000000..08f82e6a --- /dev/null +++ b/docs/chapter05/README.ja.md @@ -0,0 +1,345 @@ +# 第5章: If 文、Phi、Region + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第4章](../chapter04/README.ja.md) | +[次の章: 第6章](../chapter06/README.ja.md) + +# 目次 + +1. [新しいノード](#新しいノード) +2. [`IfNode`](#ifnode) +3. [`PhiNode`](#phinode) +4. [`RegionNode`](#regionnode) +5. [固定されたデータノード](#グラフ内のすべてのデータノードに制御エッジを結び付けるわけではない) +6. [`Stop` ノード](#stop-ノード) +7. [`if` 文の解析](#if-文の解析) +8. [ScopeNode に対する操作](#scopenode-に対する操作) +9. [ScopeNode の複製](#scopenode-の複製) +10. [2つの ScopeNode のマージ](#2つの-scopenode-のマージ) +11. [例1](#例1) +12. [マージ前](#マージ前) +13. [マージ後](#マージ後) +14. [最後に](#最後に) +15. [例2](#例2) +16. [例3](#例3) +17. [Phi を通して加算を押し上げる](#phi-を通して加算を押し上げる) +18. [さらにいくつかの例](#さらにいくつかの例) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git のリビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter05) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter04...linear-chapter05) することもできます。 + +この章では、言語の文法を拡張して次の機能を追加します。 + +* `if` 文を導入します。 +* 制御フローの分岐とマージをサポートするため、新しいノード `Region` と `Phi` を導入します。 +* 戻り地点が複数になりうるため、終端を表す `Stop` ノードも導入します。 + +この章の [完全な言語文法](05-grammar.ja.md) はこちらです。 + +## 新しいノード + +この章では、次の新しいノードを導入します。 + +| ノード名 | 種類 | 章 | 説明 | 入力 | 値 | +|-----------|---------|---------|----------------------------------------------------|------------------------------------------------|----------------------------------------------------| +| If | 制御 | 5 | 分岐の判定。`MultiNode` のサブタイプ | 制御ノードと条件式のデータノード | true 用と false 用の2つの値のタプル | +| Region | 制御 | 5 | 複数の制御フローのマージ地点 | マージする制御フローそれぞれの入力 | マージされた制御 | +| Phi | データ | 5 | 制御フローに応じて値を選択する phi 関数 | Region と各制御経路のデータノード | 通過した制御フローの経路に依存する | +| Stop | 制御 | 5 | プログラムの終端 | 関数のすべての Return ノード | なし | + +前の章までのすべてのノードも引き続き使います。 + +#### `IfNode` + +`If` ノードは制御とデータ（条件式）の両方を入力とし、true と false の `Proj` ノードが表す2つの制御フローのどちらかに、制御トークンを振り分けます。 + +#### `PhiNode` + +`Phi` はデータと制御の両方を読み取り、データ値を出力します。`Phi` の制御入力は `Region` ノードを指します。`Phi` のデータ入力は、その `Region` の制御入力それぞれに1つずつ対応します。`Phi` が計算する結果は、データとそれに対応する制御入力の両方に依存します。`Region` の制御入力は同時には最大1つしか有効にならず、`Phi` はその入力に対応するデータ値を通します。[^1] + +型は、データ入力の型の meet です。異なる2つの整数定数をマージすると `TypeInteger.BOT` になります。値は不明でも、整数であることは変わりません。整数の算術演算も同様に、畳み込めない場合は整数の結果型を保持します。 + +#### `RegionNode` + +この Sea of Nodes には制御フローグラフが埋め込まれています。通常の CFG と同じように、2つの基本ブロックが1つへ流れ込むマージ地点があります。`Region` ノードは、先行する各制御（ブロック）の制御を入力として受け取り、マージされた制御を出力します。[^2] + +`Return` と `If` は、どちらもスロット0に制御を取ります。`PhiNode` は、データ値をいつマージするか判断するために対応する `RegionNode` が必要なので、やはりスロット0を設定し、スロット1以降にデータ値を置きます。`RegionNode` の制御入力は `PhiNode` と対応を保つため、制御入力をスロット1以降に置きます。 + +#### グラフ内のすべてのデータノードに制御エッジを結び付けるわけではない + +通常の命令が所属する基本ブロックを追跡したければ、制御入力（常にスロット0）に制御を生成するノードを設定します。通常はこれを追跡する必要も、追跡したい理由もないので、多くのデータ演算では制御を `null` にします。そのようなデータ演算の正しさは、残りのデータ依存関係だけで決まります。その演算と、それに依存するノード、それが依存するノードは、ほとんど制御構造のないノードの「海」に存在します。 + +ノードの「海」は最適化に便利ですが、CFG のような従来の中間表現ではありません。グラフを逐次的な順序に並べ、制御依存関係を復元する方法が必要です。[第13章](../chapter13/README.ja.md) では、単純な大域的コード移動（Global Code Motion）[^3] アルゴリズムによってこれを行います。 + +#### `Stop` ノード + +`StopNode` の入力は `ReturnNode` だけです。プログラムの終端を示します。 + +## `if` 文の解析 + +`if` 文を解析すると、その地点で制御フローが分岐します。`if` 文の各部分で更新される名前を追跡し、最後にマージする必要があります。実装は *Combining Analyses, Combining Optimizations* の説明に従います。[^4] + +処理は次のとおりです。 + +1. 現在の制御トークン、すなわち `$ctrl` に対応付けられたノードと、`if` の条件式を入力として `IfNode` を作ります。 +2. `True` 分岐用（`ifT` と呼びます）と `False` 分岐用（`ifF` と呼びます）の2つの `ProjNode` を追加します。これらは `IfNode` のタプルの結果から値を取り出します。 +3. 現在の `ScopeNode` を複製します。複製した `ScopeNode` は、元と同じシンボルテーブルすべてと、同じエッジを持ちます。 +4. 制御トークンを `True` 射影ノード `ifT` に設定し、`if` 文の true 側の分岐を解析します。 +5. 複製した `ScopeNode` を現在のスコープにします。 +6. 制御トークンを `False` 射影ノード `ifF` に設定し、`else` 文があれば解析します。 +7. この時点で2つの `ScopeNode` があります。元のスコープは `True` 分岐で更新されている可能性があり、複製は `False` 分岐で更新されている可能性があります。 +8. マージ地点を表す `Region` ノードを作ります。 +9. 2つの `ScopeNode` を *マージ* します。束縛が異なる名前に `Phi` ノードを作ります。`Phi` ノードは、制御入力として `Region` ノードを、データ入力として各 `ScopeNode` からの2つのデータノードを取ります。名前の束縛を更新して `Phi` ノードを指すようにします。 +10. 最後に、制御トークンを `Region` ノードに設定し、複製した `ScopeNode` を破棄します。 + +実装は [`Parser` の `parseIf` メソッド](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/Parser.java#L149-L185) にあります。 + +## ScopeNode に対する操作 + +上で説明したように、ScopeNode を複製し、後でマージします。実装には、確認しておく価値のある細かな点があります。 + +### ScopeNode の複製 + +ScopeNode を複製するコードを以下で示します。 + +目標は次のとおりです。 + +1. スタックのすべての階層にわたって名前の束縛を複製する。 +2. 新しい ScopeNode を、束縛されたすべてのノードの利用側にする。 +3. マージを容易にするため、複製内の定義の順序が元と同じになるようにする。 + +実装は [`scopeNode.dup()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L142-L154) を参照してください。 + +### 2つの ScopeNode のマージ + +マージ地点では2つの ScopeNode をマージします。目標は次のとおりです。 + +1. 2つのノード間で束縛が変わった名前をマージする。そのような名前ごとに、元の2つのデータノードを参照する Phi ノードを作る。 +2. マージされた制御フローを表す新しい Region ノードを作る。Phi は、この Region ノードを最初の入力に持つ。 +3. マージが完了したら、複製した `ScopeNode` をエッジとともに破棄する。 + +マージのロジックでは、2つの ScopeNode が入力リスト内で束縛されたノードを同じ順序で保持していることを利用します。これは ScopeNode の複製時に保証しています。名前の最も内側の出現に対応する束縛しか変更できませんが、入力リスト内のすべてのノードを走査し、束縛が変わっていないものを単に無視します。 + +実装は [`ScopeNode.mergeScopes()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L164-L173) を参照してください。 + +## 例1 + +次のコード片のグラフを示します。 + +```java +int a = 1; +if (arg == 1) + a = arg+2; +else + a = arg-3; +return a; +``` + +### マージ前 + +次の図は、`if` 文の2つの分岐を `Region` ノードでマージする直前のグラフです。 + +![グラフ1](./05-graph1.svg) + +グラフに2つの `ScopeNode` があることに注目してください。一方の `$ctrl` は `True` 射影を、もう一方の `$ctrl` は `False` 射影を指します。変数 `a` は `True` 分岐では `Add` ノードに、`False` 分岐では `Sub` ノードに束縛されています。そのため、2つのスコープをマージするときに `a` に `Phi` ノードが必要です。 + +### マージ後 + +次の図は、`Region` ノードを作り、`a` の2つの定義を `Phi` ノードでマージした後のグラフです。 + +![グラフ2](./05-graph2.svg) + +複製した `ScopeNode` はもう一方にマージされ、破棄されました。両方のスコープで `a` の定義が異なっていたので、`Phi` ノードを作り、`a` はそれを参照するようになりました。`Phi` ノードの入力は `Region` ノード、`True` 分岐の `Add` ノード、`False` 分岐の `Sub` ノードです。`arg` には代入されておらず、両スコープで値が同じなので、`arg` に `Phi` は不要です。 + +### 最後に + +`return` 文を解析し処理した後のグラフを示します。 + +![グラフ3](./05-graph3.svg) + +## 例2 + +次のコード片を考えます。 + +```java +int b = 0; +int c = 0; +if (arg == 1) { + b = 2; + c = 1; +} +else { + b = 1; +} +return b; +``` + +`b` の値は、制御フローがどの経路を通ったかに依存します。これを解決するため、Φ（Phi）関数を挿入します。 + +``` +b = Phi(Region,2, 1); // values vary +c = Phi(Region,1, 0); // values vary, but dead +``` + +`c` の `Phi` は、`c` が定義されたスコープが死ぬときに死にます。これはマージ時ではなく、`return` の後に起こります。`return` が `b` を使うため、`b` は生き続けます。 + +if 文の解析を進める前に、スコープを複製します。 + +```java +ScopeNode fScope = _scope.dup(); +/* Scope[$ctrl:$ctrl, arg:arg][b:0, c:0]*/ +``` + +続いて、if 文の最初の分岐を解析します。 + +```java +// Parse the true side +ctrl(ifT); // set ctrl token to ifTrue projection +parseStatement(); // Parse true-side +ScopeNode tScope = _scope; + +/* Scope[$ctrl:True, arg:arg][b:2, c:1]*/ +``` + +この分岐では、シンボルテーブルに存在する両方のシンボルを変更し、新しい値を設定したことに注目してください。ここで、スコープを最初の状態（`ifT` が行った変更を含まない状態）に戻します。 + +```java +_scope = fScope; +``` + +続いて、if 文の2つ目の分岐を解析します。 + +```java +if (matchx("else")) { + parseStatement(); + fScope = _scope; + + /* Scope[$ctrl:False, arg:arg][b:1, c:0]*/ +} +``` + +両方の分岐が `b` を変更しましたが、`c` を変更したのは true 側だけです。分岐の各部分もレキシカルスコープなので、現在の（外側の）スコープに新しいシンボルを導入することはできません。そのため、名前の束縛の順序は変わりません。最初の制御ノードを除いてループし、同じ名前の束縛に対応するノードを比較します。異なる場合は、この違いを表す phi ノードを作ります。 + +```java + /* in(i); 2 */ + /* that.in(i); 1 */ + if( in(i) != that.in(i) ) // No need for redundant Phis + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); +``` + +![グラフ8](./05-graph9.svg) + +## 例3 + +Phi は、次の例が示すピープホール最適化を実装しています。 + +```java +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +``` + +次の2つの図は値の書き換えに焦点を当てています。変わらない `if` と Region は省略しています。Phi の入力1は true 側、入力2は false 側です。コンパイラのグラフでは、Phi は引き続き同じ Region を使います。 + +ピープホール最適化前: + +![グラフ4](./05-graph4.svg) + +ピープホール最適化後: + +![グラフ5](./05-graph5.svg) + +共通の演算子を外へ引き出し、Phi ノードをオペランドだけに適用しました。`==` の第2オペランドだけが変わり、第1オペランド（`arg`）は同じままであることに注目してください。実装は [`PhiNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/PhiNode.java) にあります。 + +全体を通じて `r` が同じ Region を表すとすると、グラフの記法では次のようになります。 + +```text +Phi(r, a+b, c+d) -> Phi(r, a, c) + Phi(r, b, d) +``` + +これを、Phi を通して **演算を下へ引き下げる** と呼びます。共通の演算を、流入する経路からマージ後に移します。新しい各 Phi は、同じ経路から対応するオペランドを選びます。上の `arg` のようにオペランドが共有されていれば、その Phi はそのオペランドに簡約されます。 + +## Phi を通して加算を押し上げる + +逆方向に移すと定数畳み込みの機会が現れることがあります。たとえば、次のコードです。 + +```java +int x = 1; +if( arg ) x = 2; +return (arg+x)+3; +``` + +マージによって `x` は定数の Phi になります。`x` 自体は定数ではありませんが、取りうる値それぞれへの3の加算はコンパイル時に計算できます。加算のピープホール最適化は式の結合を変え、流入する経路へ **加算を上に押し上げます**。 + +```text +(arg + Phi(r, 2, 1)) + 3 + -> arg + Phi(r, 2+3, 1+3) + -> arg + Phi(r, 5, 4) +``` + +この実装は、`(x + Phi(constants)) + constant` の形に対する [`AddNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/AddNode.java) として、ここで初めて登場します。最後のオペランドが別の定数の Phi でも構いません。ただし、対応する各分岐が同じ経路を表すよう、両方の Phi は **同じ Region** を使わなければなりません。 + +なぜすべての演算を Phi の向こうへ押し上げないのでしょうか。それでは流入する経路間で処理が重複し、引き下げるピープホール最適化がすぐに元に戻す可能性があります。2つの書き換えを繰り返すと、いつまでも終わりません。ここでは、結果の Phi を作る **前に** 新しい加算がすべて定数に畳み込まれます。その Phi が下へ引き戻せる新しい加算は残らず、実行時の加算が1つ消えます。畳み込めることという条件が、この最適化の利点と、逆向きの書き換えの組が停止する理由の両方を与えます。 + +## さらにいくつかの例 + +次の2つの単純な `if` の例でも、結果の値を強調するために制御フローを省略しています。Phi の入力は、上と同じ true/false の順序を保ちます。 + +```java +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c; +``` + +![グラフ6](./05-graph6.svg) + +```java +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b; +``` + +![グラフ7](./05-graph7.svg) + +入れ子の分岐では、各 Phi に流入する経路を明確にするため、制御経路と Region を示します。 + +```java +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +``` + +![グラフ8](./05-graph8.svg) + +[^1]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 132. + +[^2]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 129. + +[^3]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 86. + +[^4]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 102-103. diff --git a/docs/chapter05/README.md b/docs/chapter05/README.md new file mode 100644 index 00000000..84f9c7bd --- /dev/null +++ b/docs/chapter05/README.md @@ -0,0 +1,426 @@ +# Chapter 5: If Statement, Phi, and Region + +English | [日本語](README.ja.md) + +[Previous: Chapter 4](../chapter04/README.md) | +[Next: Chapter 6](../chapter06/README.md) + +# Table of Contents + +1. [New Nodes](#new-nodes) +2. [`IfNode`](#ifnode) +3. [`PhiNode`](#phinode) +4. [`RegionNode`](#regionnode) +5. [Pinned data nodes](#we-do-not-associate-a-control-edge-on-every-data-node-in-the-graph) +6. [`Stop` Nodes](#stop-nodes) +7. [Parsing an `if` Statement](#parsing-an-if-statement) +8. [Operations on ScopeNodes](#operations-on-scopenodes) +9. [Duplicating a ScopeNode](#duplicating-a-scopenode) +10. [Merging two ScopeNodes](#merging-two-scopenodes) +11. [Example 1](#example-1) +12. [Before Merging](#before-merging) +13. [After Merging](#after-merging) +14. [Finally](#finally) +15. [Example 2](#example-2) +16. [Example 3](#example-3) +17. [Pushing addition up through a Phi](#pushing-addition-up-through-a-phi) +18. [More Examples](#more-examples) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter05) 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-chapter04...linear-chapter05) it to the previous chapter. + +In this chapter we extend the language grammar with the following features: + +* We introduce the `if` statement. +* To support splitting of control flow and merging, we introduce new nodes: `Region` and `Phi`. +* Since we can now have multiple return points, we also introduce the `Stop` node as the termination. + +Here is the [complete language grammar](05-grammar.md) for this chapter. + +## New Nodes + +The following new nodes are introduced in this chapter: + +| Node Name | Type | Chapter | Description | Inputs | Value | +|-----------|---------|---------|----------------------------------------------------|------------------------------------------------|----------------------------------------------------| +| If | Control | 5 | A branching test, sub type of `MultiNode` | A control node and a data predicate node | A tuple of two values: one for true, one for false | +| Region | Control | 5 | A merge point for multiple control flows | An input for each control flow that is merging | Merged control | +| Phi | Data | 5 | A phi function picks a value based on control flow | A Region, and data nodes for each control path | Depends on control flow path taken | +| Stop | Control | 5 | Termination of the program | All return nodes of the function | None | + +and keep all nodes from prior chapters. + +#### `IfNode` + +`If` node takes in both control and data (predicate expression) and routes the +control token to one of the two control flows, represented by true and false +`Proj` nodes. + +#### `PhiNode` + +A `Phi` reads in both data and control, and outputs a data value. The control +input to the `Phi` points to a `Region` node. The data inputs to the `Phi` are +one for each of the control inputs to that `Region`. The result computed by a +`Phi` depends both on the data and the matching control input. At most one +control input to the `Region` can be active at a time, and the `Phi` passes +through the data value from the matching input.[^1] + +Its type is the meet of its data-input types. Two different integer constants +merge to `TypeInteger.BOT`: the value is unknown, but it is still an integer. +Integer arithmetic likewise retains an integer result type when it cannot fold. + +#### `RegionNode` + +In this Sea of Nodes, there is an embedded Control Flow Graph - and like a +normal CFG there are merge points where two basic blocks flow into one. The +`Region` node takes control from each predecessor control (block) as input and +produces a merged control as an output.[^2] + +Both `Return` and `If` take control in slot 0. `PhiNode`s need their +corresponding `RegionNode` to know when to merge data values, so again slot 0 +is set, and data values show up in slots 1 and onward. `RegionNode`s keep +their control inputs in sync with `PhiNode`s, so again their control inputs show up +in slots 1 and onward. + +#### We do not associate a control edge on every data node in the graph + +If we want to track the basic block a normal instruction is in, we will set the +control input (always slot 0) to some control-producing Node. Typically we do +not need to (nor want to) track this - so control is `null` for most data ops. +The correctness of such a data op is solely determined by the remaining data +dependencies. It, and the Nodes that depend on it or on which it depends, +exists in a “sea” of Nodes, with little control structure. + +The “sea” of Nodes is useful for optimization, but does not represent any +traditional intermediate representation such as a CFG. We need a way to +serialize the graph and get back the control dependences. We do this with a +simple Global Code Motion [^3] algorithm in [Chapter 13](../chapter13/README.md). + +#### `Stop` Nodes +`StopNode`s only have `ReturnNode` inputs. They mark the program termination. + + + +## Parsing an `if` Statement + +When we parse an `if` statement, the control flow splits at that point. We +must track the names being updated in each part of the `if` statement, and then +merge them at the end. The implementation follows the description in *Combining Analyses, Combining Optimizations*[^4]. + +This involves the following: + +1. We create an `IfNode` with the current control token, i.e. the node mapped to + `$ctrl`, and the `if` predicate expression as inputs. +2. We add two `ProjNodes` - one for the `True` branch (call it `ifT`), and the + other for the `False` branch (call it `ifF`) - these extract values from the + tuple result of the `IfNode`. +3. We duplicate the current `ScopeNode`. The duplicated `ScopeNode` contains + all the same symbol tables as the original, and has the same edges. +4. We set the control token to the `True` projection node `ifT`, and parse the true + branch of the `if` statement. +5. We set the duplicated `ScopeNode` as the current one. +6. The control token is set to the `False` projection node `ifF`, and if there is an + `else` statement we parse it. +7. At this point we have two `ScopeNode`s; the original one, potentially updated + by the `True` branch, and the duplicate one, potentially updated by the + `False` branch. +8. We create a `Region` node to represent a merge point. +9. We *merge* the two `ScopeNode`s. We create `Phi` nodes for any names whose + bindings differ. The `Phi` nodes take the `Region` node as the control input + and the two data nodes from each of the `ScopeNode`s. The name binding is + updated to point to the `Phi` node. +10. Finally, we set the `Region` node as the control token, and discard the duplicated `ScopeNode`. + +Implementation is in [`parseIf` method in `Parser`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/Parser.java#L149-L185). + +## Operations on ScopeNodes + +As explained above, we duplicate ScopeNodes and merge them at a later point. There are some +subtleties in how this is implemented that are worth going over. + +### Duplicating a ScopeNode + +Below is the code for duplicating a ScopeNode. + +Our goals are: +1) Duplicate the name bindings across all stack levels +2) Make the new ScopeNode a user of all the bound nodes +3) Ensure that the order of defs in the duplicate is the same to allow easy merging + +For implementation [see `scopeNode.dup()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L142-L154) + +### Merging two ScopeNodes + +At the merge point we merge two ScopeNodes. The goals are: + +1) Merge names whose bindings have changed between the two nodes. For each such name, a Phi node is created, referencing the two original data nodes. +2) A new Region node is created representing the merged control flow. The phis have this region node as the first input. +3) After the merge is completed, the duplicate `ScopeNode` is discarded along with its edges. + +The merging logic takes advantage of the fact that the two ScopeNodes have the bound nodes in the same order in the list of inputs. This was ensured during duplicating the ScopeNode. +Although only the innermost occurrence of a name can have its binding changed, we scan all the nodes in our input list, and simply ignore ones where the binding has not changed. + +For implementation [see `ScopeNode.mergeScopes()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L164-L173) + + +## Example #1 + +We show the graph for the following code snippet: +```java +int a = 1; +if (arg == 1) + a = arg+2; +else + a = arg-3; +return a; +``` + +### Before Merging + +The following shows the graph just before we merge the two branches of the `if` statement in a `Region` node. + +![Graph1](./05-graph1.svg) + +Note the two `ScopeNode`s in the graph. +One has its `$ctrl` pointing to the `True` projection, while the other has `$ctrl` pointing to `False` projection. +The variable `a` is bound to the `Add` node in the `True` branch, whereas it is bound to the `Sub` node in the `False` branch. +Thus `a` will need a `Phi` node when merging the two scopes. + +### After Merging + +Below is the graph after we created a `Region` node and merged the two definitions of `a` in a `Phi` node. + +![Graph2](./05-graph2.svg) + +The duplicate `ScopeNode` has been discarded and was merged into the other one. +Since `a` had two different definitions in both scopes a `Phi` node was created +and is now referenced from `a`. The `Phi` node's inputs are the `Region` node +and the `Add` node from the `True` branch, and `Sub` node from the `False` +branch. The `arg` variable did not get assigned; both scopes agree on the +value so `arg` does not get a `Phi`. + +### Finally + +Here is the graph after the `return` statement was parsed and processed. + +![Graph3](./05-graph3.svg) + + + +## Example #2 + +Consider the following code snippet: +```java +int b = 0; +int c = 0; +if (arg == 1) { + b = 2; + c = 1; +} +else { + b = 1; +} +return b; +``` + +The value of `b` depends on which path the control flow took. +To resolve this, a Φ (Phi) function is inserted. + +``` +b = Phi(Region,2, 1); // values vary +c = Phi(Region,1, 0); // values vary, but dead +``` + +The `Phi` for `c` will die when the scope where `c` is defined dies. This does +not happen when merging but after the `return`. `return` is using `b` so `b` +stays alive. + +Before we go ahead and parse down the if statement we duplicate the scope: +```java +ScopeNode fScope = _scope.dup(); +/* Scope[$ctrl:$ctrl, arg:arg][b:0, c:0]*/ +``` + +We then will proceed and parse down the first branch of the if statement: +```java +// Parse the true side +ctrl(ifT); // set ctrl token to ifTrue projection +parseStatement(); // Parse true-side +ScopeNode tScope = _scope; + +/* Scope[$ctrl:True, arg:arg][b:2, c:1]*/ +``` + +Notice, this branch modified and set a new value for both symbols currently existing in the symbol table. +Now, we set the scope back to where we started (without the modifications that `ifT` made) + +```java +_scope = fScope; +``` + +We then will proceed and parse down the second branch of the if statement: +```java +if (matchx("else")) { + parseStatement(); + fScope = _scope; + + /* Scope[$ctrl:False, arg:arg][b:1, c:0]*/ +} +``` + +The two branches modified `b`; only the true branch modified `c`. Since the branch arms are also +lexical scopes, they cannot introduce new symbols in the current (outer) scope. +This means that the order of the name bindings stayed the same. Excluding the +first control node, we loop through and compare the nodes corresponding to the +same name binding to see if the nodes are different, if so we create a phi node +representing this conflict: + +```java + /* in(i); 2 */ + /* that.in(i); 1 */ + if( in(i) != that.in(i) ) // No need for redundant Phis + setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); +``` + +![Graph8](./05-graph9.svg) + + + +## Example #3 + +Phis implement a peephole illustrated in the example: + +```java +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +``` + +The next two diagrams focus on the value rewrite. The unchanged `if` and +Region are omitted; Phi input 1 is the true arm and input 2 the false arm. +The Phis still use the same Region in the compiler's graph. + +Pre-peephole we have: + +![Graph4](./05-graph4.svg) + +Post-peephole: + +![Graph5](./05-graph5.svg) + +The common operator was pulled out and the Phi node only got applied to the +operands. Notice how only the second operand of the `==` changes, the first +one stays the same (`arg`). The implementation is in +[`PhiNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/PhiNode.java). + +In graph notation, with `r` denoting the same Region throughout: + +```text +Phi(r, a+b, c+d) -> Phi(r, a, c) + Phi(r, b, d) +``` + +We call this **pulling the operation down** through the Phi: the common +operation moves from the incoming paths to after their merge. Each new Phi +selects the corresponding operand from the same path. If an operand is shared, +as `arg` is above, its Phi collapses to that operand. + + +## Pushing addition up through a Phi + +The opposite direction can expose constant folding. For example: + +```java +int x = 1; +if( arg ) x = 2; +return (arg+x)+3; +``` + +The merge gives `x` a Phi of constants. Although `x` itself is not constant, +adding 3 to each possible value is a compile-time calculation. The addition +peephole reassociates the expression and **pushes the addition up** onto the +incoming paths: + +```text +(arg + Phi(r, 2, 1)) + 3 + -> arg + Phi(r, 2+3, 1+3) + -> arg + Phi(r, 5, 4) +``` + +The implementation first appears here in +[`AddNode.idealize()`](../../src/main/java/com/seaofnodes/simple/node/AddNode.java), +for the shape `(x + Phi(constants)) + constant`. The final operand can also +be another Phi of constants, but both Phis must use the **same Region** so +their corresponding arms describe the same path. + +Why not push every operation through a Phi? That would duplicate work across +the incoming paths, and the pull-down peephole could immediately undo it. +Repeatedly applying the two rewrites would never finish. Here every new +addition folds to a constant **before** we build the result Phi. There are no +new additions left for that Phi to pull back down, and one runtime addition +has disappeared. The folding requirement supplies both the benefit and the +reason this pair of opposing rewrites terminates. + + +## More examples + +The next two simple `if` examples also omit control flow to highlight the +resulting values. Their Phi inputs retain the true/false order above. + +```java +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c; +``` + +![Graph6](./05-graph6.svg) + +```java +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b; +``` + +![Graph7](./05-graph7.svg) + +For nested branches, the control paths and Regions are shown so each Phi's +incoming paths remain clear: + +```java +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +``` + +![Graph8](./05-graph8.svg) + + + +[^1]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 132. + +[^2]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 129. + +[^3]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 86. + +[^4]: Click, C. (1995). + Combining Analyses, Combining Optimizations, 102-103. -- cgit v1.2.3