From 277f7510ceced76f6e5fc2d7d2331c6842a54d7b Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sun, 3 Dec 2023 23:23:04 +0000 Subject: Chapter 7: While Statement MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Cliff Click Co-authored-by: Thalia Archibald Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher --- docs/chapter07/07-grammar.md | 88 ++++++++++ docs/chapter07/07-graph1.gv | 107 +++++++++++++ docs/chapter07/07-graph1.svg | 268 +++++++++++++++++++++++++++++++ docs/chapter07/07-graph2.gv | 62 +++++++ docs/chapter07/07-graph2.svg | 184 +++++++++++++++++++++ docs/chapter07/07-graph3.gv | 108 +++++++++++++ docs/chapter07/07-graph3.svg | 373 +++++++++++++++++++++++++++++++++++++++++++ docs/chapter07/07-graph4.gv | 96 +++++++++++ docs/chapter07/07-graph4.svg | 329 ++++++++++++++++++++++++++++++++++++++ docs/chapter07/Makefile | 12 ++ docs/chapter07/README.md | 244 ++++++++++++++++++++++++++++ 11 files changed, 1871 insertions(+) create mode 100644 docs/chapter07/07-grammar.md create mode 100644 docs/chapter07/07-graph1.gv create mode 100644 docs/chapter07/07-graph1.svg create mode 100644 docs/chapter07/07-graph2.gv create mode 100644 docs/chapter07/07-graph2.svg create mode 100644 docs/chapter07/07-graph3.gv create mode 100644 docs/chapter07/07-graph3.svg create mode 100644 docs/chapter07/07-graph4.gv create mode 100644 docs/chapter07/07-graph4.svg create mode 100644 docs/chapter07/Makefile create mode 100644 docs/chapter07/README.md (limited to 'docs/chapter07') diff --git a/docs/chapter07/07-grammar.md b/docs/chapter07/07-grammar.md new file mode 100644 index 00000000..29a730b6 --- /dev/null +++ b/docs/chapter07/07-grammar.md @@ -0,0 +1,88 @@ +# Grammar for Chapter 6 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | metaStatement + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + +metaStatement + : '#showGraph' ';' + ; + +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/chapter07/07-graph1.gv b/docs/chapter07/07-graph1.gv new file mode 100644 index 00000000..ba806a28 --- /dev/null +++ b/docs/chapter07/07-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter07 { +/* +while(arg < 10) { + arg = arg + 1; + #showGraph; +} +return arg; + +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + compound="true"; + subgraph cluster_Nodes { + Start2 [ shape=plaintext label=< + + + +
Start
+ + +
$ctrlarg
+
> + ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + { rank=same; Loop6;Phi_arg8;} + } + node [shape=plaintext]; + subgraph cluster_Scope7_1 { + Scope7_1 [label=< + + +
2
>]; + subgraph cluster_Scope7_2 { + Scope7_2 [label=< + + +
1
>]; + subgraph cluster_Scope7_3 { + Scope7_3 [label=< + + +
0$ctrlarg
>]; + } + } + } + node [shape=plaintext]; + subgraph cluster_Scope1_1 { + Scope1_1 [label=< + + +
1
>]; + subgraph cluster_Scope1_2 { + Scope1_2 [label=< + + +
0$ctrlarg
>]; + } + } + node [shape=plaintext]; + subgraph cluster_Scope14_1 { + Scope14_1 [label=< + + +
1
>]; + subgraph cluster_Scope14_2 { + Scope14_2 [label=< + + +
0$ctrlarg
>]; + } + } + edge [ fontname=Helvetica, fontsize=8 ]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + edge [style=dashed color=cornflowerblue]; + Scope7_3:"Scope7_3_$ctrl" -> If11:p0; + Scope7_3:"Scope7_3_arg" -> Add16; + edge [style=dashed color=cornflowerblue]; + Scope1_2:"Scope1_2_$ctrl" -> Loop6; + Scope1_2:"Scope1_2_arg" -> Phi_arg8; + edge [style=dashed color=cornflowerblue]; + Scope14_2:"Scope14_2_$ctrl" -> If11:p1; + Scope14_2:"Scope14_2_arg" -> Phi_arg8; +} diff --git a/docs/chapter07/07-graph1.svg b/docs/chapter07/07-graph1.svg new file mode 100644 index 00000000..94248cfb --- /dev/null +++ b/docs/chapter07/07-graph1.svg @@ -0,0 +1,268 @@ + + + + + + +chapter07 + + +cluster_Nodes + + + +cluster_Scope7_1 + + + +cluster_Scope7_2 + + + +cluster_Scope7_3 + + + +cluster_Scope1_1 + + + +cluster_Scope1_2 + + + +cluster_Scope14_1 + + + +cluster_Scope14_2 + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Loop6 + +Loop + + + +Loop6->Start2:p0 + + +1 + + + +Phi_arg8 + +φ_arg + + + +Phi_arg8->Start2:p1 + + +1 + + + +Phi_arg8->Loop6 + + +0 + + + +Con_9 + +10 + + + +LT10 + +< + + + +LT10->Phi_arg8 + + +1 + + + +LT10->Con_9 + + +2 + + + +If11 + + +If + + + +True + + +False + + + +If11->Loop6 + + +0 + + + +If11->LT10 + + +1 + + + +Con_15 + +1 + + + +Add16 + ++ + + + +Add16->Phi_arg8 + + +1 + + + +Add16->Con_15 + + +2 + + + +Scope7_1 + + +2 + + + +Scope7_2 + + +1 + + + +Scope7_3 + + +0 + +$ctrl + +arg + + + +Scope7_3:Scope7_3_$ctrl->If11:p0 + + + + + +Scope7_3:Scope7_3_arg->Add16 + + + + + +Scope1_1 + + +1 + + + +Scope1_2 + + +0 + +$ctrl + +arg + + + +Scope1_2:Scope1_2_$ctrl->Loop6 + + + + + +Scope1_2:Scope1_2_arg->Phi_arg8 + + + + + +Scope14_1 + + +1 + + + +Scope14_2 + + +0 + +$ctrl + +arg + + + +Scope14_2:Scope14_2_arg->Phi_arg8 + + + + + +Scope14_2:Scope14_2_$ctrl->If11:p1 + + + + + diff --git a/docs/chapter07/07-graph2.gv b/docs/chapter07/07-graph2.gv new file mode 100644 index 00000000..f4cfcb45 --- /dev/null +++ b/docs/chapter07/07-graph2.gv @@ -0,0 +1,62 @@ +digraph chapter07 { +/* +while(arg < 10) { + arg = arg + 1; + #showGraph; +} +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" ]; + Loop6 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_arg8 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_9 [ label="10" ]; + LT10 [ label="<" ]; + If11 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_15 [ label="1" ]; + Add16 [ label="+" ]; + Return17 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + } + node [shape=plaintext]; + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return17[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> If11:p0[taillabel=2 color=red constraint=false]; + Phi_arg8 -> Loop6 [style=dotted taillabel=0]; + Phi_arg8 -> Start2:p1[taillabel=1]; + Phi_arg8 -> Add16[taillabel=2 constraint=false]; + LT10 -> Phi_arg8[taillabel=1]; + LT10 -> Con_9[taillabel=2]; + If11 -> Loop6[taillabel=0 color=red]; + If11 -> LT10[taillabel=1]; + Add16 -> Phi_arg8[taillabel=1]; + Add16 -> Con_15[taillabel=2]; + Return17 -> If11:p1[taillabel=0 color=red]; + Return17 -> Phi_arg8[taillabel=1]; + edge [style=dashed color=cornflowerblue]; +} \ No newline at end of file diff --git a/docs/chapter07/07-graph2.svg b/docs/chapter07/07-graph2.svg new file mode 100644 index 00000000..1fec9556 --- /dev/null +++ b/docs/chapter07/07-graph2.svg @@ -0,0 +1,184 @@ + + + + + + +chapter07 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return17 + +Return + + + +Stop3->Return17 + + +0 + + + +Loop6 + +Loop + + + +Loop6->Start2:p0 + + +1 + + + +If11 + + +If + + + +True + + +False + + + +Loop6->If11:p0 + + +2 + + + +Phi_arg8 + +φ_arg + + + +Phi_arg8->Start2:p1 + + +1 + + + +Phi_arg8->Loop6 + + +0 + + + +Add16 + ++ + + + +Con_9 + +10 + + + +LT10 + +< + + + +LT10->Phi_arg8 + + +1 + + + +LT10->Con_9 + + +2 + + + +If11->Loop6 + + +0 + + + +If11->LT10 + + +1 + + + +Con_15 + +1 + + + +Add16->Phi_arg8 + + + +1 + + + +Add16->Con_15 + + +2 + + + +Return17->Phi_arg8 + + +1 + + + +Return17->If11:p1 + + +0 + + + diff --git a/docs/chapter07/07-graph3.gv b/docs/chapter07/07-graph3.gv new file mode 100644 index 00000000..4482100b --- /dev/null +++ b/docs/chapter07/07-graph3.gv @@ -0,0 +1,108 @@ +digraph chapter07 { +/* +int sum = 0; +int i = 0; +while(i < arg) { + i = i + 1; + int j = 0; + while( j < arg ) { + sum = sum + j; + j = j + 1; + } +} +return sum; + +*/ + 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="0" ]; + Con_7 [ label="0" ]; + Loop8 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_sum11 [ style=filled fillcolor=lightyellow label="φ_sum" ]; + Phi_i12 [ style=filled fillcolor=lightyellow label="φ_i" ]; + LT13 [ label="<" ]; + If14 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_18 [ label="1" ]; + Add19 [ label="+" ]; + Con_20 [ label="0" ]; + Loop21 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_sum24 [ style=filled fillcolor=lightyellow label="φ_sum" ]; + Phi_j26 [ style=filled fillcolor=lightyellow label="φ_j" ]; + LT27 [ label="<" ]; + If28 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Add32 [ label="+" ]; + Con_33 [ label="1" ]; + Add34 [ label="+" ]; + Return35 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop8;Phi_sum11;Phi_i12;} + { rank=same; Loop21;Phi_sum24;Phi_j26;} + } + node [shape=plaintext]; + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return35[taillabel=0 color=red]; + Loop8 -> Start2:p0[taillabel=1 color=red]; + Loop8 -> If28:p1[taillabel=2 color=red constraint=false]; + Phi_sum11 -> Loop8 [style=dotted taillabel=0]; + Phi_sum11 -> Con_6[taillabel=1]; + Phi_sum11 -> Phi_sum24[taillabel=2 constraint=false]; + Phi_i12 -> Loop8 [style=dotted taillabel=0]; + Phi_i12 -> Con_7[taillabel=1]; + Phi_i12 -> Add19[taillabel=2 constraint=false]; + LT13 -> Phi_i12[taillabel=1]; + LT13 -> Start2:p1[taillabel=2]; + If14 -> Loop8[taillabel=0 color=red]; + If14 -> LT13[taillabel=1]; + Add19 -> Phi_i12[taillabel=1]; + Add19 -> Con_18[taillabel=2]; + Loop21 -> If14:p0[taillabel=1 color=red]; + Loop21 -> If28:p0[taillabel=2 color=red constraint=false]; + Phi_sum24 -> Loop21 [style=dotted taillabel=0]; + Phi_sum24 -> Phi_sum11[taillabel=1]; + Phi_sum24 -> Add32[taillabel=2 constraint=false]; + Phi_j26 -> Loop21 [style=dotted taillabel=0]; + Phi_j26 -> Con_20[taillabel=1]; + Phi_j26 -> Add34[taillabel=2 constraint=false]; + LT27 -> Phi_j26[taillabel=1]; + LT27 -> Start2:p1[taillabel=2]; + If28 -> Loop21[taillabel=0 color=red]; + If28 -> LT27[taillabel=1]; + Add32 -> Phi_j26[taillabel=1]; + Add32 -> Phi_sum24[taillabel=2]; + Add34 -> Phi_j26[taillabel=1]; + Add34 -> Con_33[taillabel=2]; + Return35 -> If14:p1[taillabel=0 color=red]; + Return35 -> Phi_sum11[taillabel=1]; + edge [style=dashed color=cornflowerblue]; +} \ No newline at end of file diff --git a/docs/chapter07/07-graph3.svg b/docs/chapter07/07-graph3.svg new file mode 100644 index 00000000..a9a0e8d0 --- /dev/null +++ b/docs/chapter07/07-graph3.svg @@ -0,0 +1,373 @@ + + + + + + +chapter07 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return35 + +Return + + + +Stop3->Return35 + + +0 + + + +Con_6 + +0 + + + +Con_7 + +0 + + + +Loop8 + +Loop + + + +Loop8->Start2:p0 + + +1 + + + +If28 + + +If + + + +True + + +False + + + +Loop8->If28:p1 + + +2 + + + +Phi_sum11 + +φ_sum + + + +Phi_sum11->Con_6 + + +1 + + + +Phi_sum11->Loop8 + + +0 + + + +Phi_sum24 + +φ_sum + + + +Phi_i12 + +φ_i + + + +Phi_i12->Con_7 + + +1 + + + +Phi_i12->Loop8 + + +0 + + + +Add19 + ++ + + + +LT13 + +< + + + +LT13->Start2:p1 + + +2 + + + +LT13->Phi_i12 + + +1 + + + +If14 + + +If + + + +True + + +False + + + +If14->Loop8 + + +0 + + + +If14->LT13 + + +1 + + + +Con_18 + +1 + + + +Add19->Phi_i12 + + + +1 + + + +Add19->Con_18 + + +2 + + + +Con_20 + +0 + + + +Loop21 + +Loop + + + +Loop21->If14:p0 + + +1 + + + +Loop21->If28:p0 + + +2 + + + +Phi_sum24->Phi_sum11 + + + +1 + + + +Phi_sum24->Loop21 + + +0 + + + +Add32 + ++ + + + +Phi_j26 + +φ_j + + + +Phi_j26->Con_20 + + +1 + + + +Phi_j26->Loop21 + + +0 + + + +Add34 + ++ + + + +LT27 + +< + + + +LT27->Start2:p1 + + +2 + + + +LT27->Phi_j26 + + +1 + + + +If28->Loop21 + + +0 + + + +If28->LT27 + + +1 + + + +Add32->Phi_sum24 + + + +2 + + + +Add32->Phi_j26 + + +1 + + + +Con_33 + +1 + + + +Add34->Phi_j26 + + + +1 + + + +Add34->Con_33 + + +2 + + + +Return35->Phi_sum11 + + +1 + + + +Return35->If14:p1 + + +0 + + + diff --git a/docs/chapter07/07-graph4.gv b/docs/chapter07/07-graph4.gv new file mode 100644 index 00000000..24ace3da --- /dev/null +++ b/docs/chapter07/07-graph4.gv @@ -0,0 +1,96 @@ +digraph chapter07 { +/* +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; +} +return b; + +*/ + 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_6 [ label="1" ]; + Con_7 [ label="2" ]; + Loop8 [ shape=box style=filled fillcolor=yellow label="Loop" ]; + Phi_a11 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b12 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Con_13 [ label="10" ]; + LT14 [ label="<" ]; + If15 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_19 [ label="2" ]; + EQ20 [ label="==" ]; + If21 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_25 [ label="3" ]; + Con_26 [ label="4" ]; + Region27 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_a28 [ style=filled fillcolor=lightyellow label="φ_a" ]; + Phi_b29 [ style=filled fillcolor=lightyellow label="φ_b" ]; + Return30 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop8;Phi_a11;Phi_b12;} + { rank=same; Region27;Phi_b29;Phi_a28;} + } + node [shape=plaintext]; + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return30[taillabel=0 color=red]; + Loop8 -> Start2:p0[taillabel=1 color=red]; + Loop8 -> Region27[taillabel=2 color=red constraint=false]; + Phi_a11 -> Loop8 [style=dotted taillabel=0]; + Phi_a11 -> Con_6[taillabel=1]; + Phi_a11 -> Phi_a28[taillabel=2 constraint=false]; + Phi_b12 -> Loop8 [style=dotted taillabel=0]; + Phi_b12 -> Con_7[taillabel=1]; + Phi_b12 -> Phi_b29[taillabel=2 constraint=false]; + LT14 -> Phi_a11[taillabel=1]; + LT14 -> Con_13[taillabel=2]; + If15 -> Loop8[taillabel=0 color=red]; + If15 -> LT14[taillabel=1]; + EQ20 -> Phi_a11[taillabel=1]; + EQ20 -> Con_19[taillabel=2]; + If21 -> If15:p0[taillabel=0 color=red]; + If21 -> EQ20[taillabel=1]; + Region27 -> If21:p0[taillabel=1 color=red]; + Region27 -> If21:p1[taillabel=2 color=red]; + Phi_a28 -> Region27 [style=dotted taillabel=0]; + Phi_a28 -> Con_25[taillabel=1]; + Phi_a28 -> Phi_a11[taillabel=2 constraint=false]; + Phi_b29 -> Region27 [style=dotted taillabel=0]; + Phi_b29 -> Phi_b12[taillabel=1]; + Phi_b29 -> Con_26[taillabel=2 constraint=false]; + Return30 -> If15:p1[taillabel=0 color=red]; + Return30 -> Phi_b12[taillabel=1]; + edge [style=dashed color=cornflowerblue]; +} diff --git a/docs/chapter07/07-graph4.svg b/docs/chapter07/07-graph4.svg new file mode 100644 index 00000000..cf42453d --- /dev/null +++ b/docs/chapter07/07-graph4.svg @@ -0,0 +1,329 @@ + + + + + + +chapter07 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + + + +Stop3 + +Stop + + + +Return30 + +Return + + + +Stop3->Return30 + + +0 + + + +Con_6 + +1 + + + +Con_7 + +2 + + + +Loop8 + +Loop + + + +Loop8->Start2:p0 + + +1 + + + +Region27 + +Region + + + +Loop8->Region27 + + +2 + + + +Phi_a11 + +φ_a + + + +Phi_a11->Con_6 + + +1 + + + +Phi_a11->Loop8 + + +0 + + + +Phi_a28 + +φ_a + + + +Phi_b12 + +φ_b + + + +Phi_b12->Con_7 + + +1 + + + +Phi_b12->Loop8 + + +0 + + + +Phi_b29 + +φ_b + + + +Con_13 + +10 + + + +LT14 + +< + + + +LT14->Phi_a11 + + +1 + + + +LT14->Con_13 + + +2 + + + +If15 + + +If + + + +True + + +False + + + +If15->Loop8 + + +0 + + + +If15->LT14 + + +1 + + + +Con_19 + +2 + + + +EQ20 + +== + + + +EQ20->Phi_a11 + + +1 + + + +EQ20->Con_19 + + +2 + + + +If21 + + +If + + + +True + + +False + + + +If21->If15:p0 + + +0 + + + +If21->EQ20 + + +1 + + + +Con_25 + +3 + + + +Con_26 + +4 + + + +Region27->If21:p0 + + +1 + + + +Region27->If21:p1 + + +2 + + + +Phi_a28->Phi_a11 + + + +2 + + + +Phi_a28->Con_25 + + +1 + + + +Phi_a28->Region27 + + +0 + + + +Phi_b29->Phi_b12 + + + +1 + + + +Phi_b29->Con_26 + + +2 + + + +Phi_b29->Region27 + + +0 + + + +Return30->Phi_b12 + + +1 + + + +Return30->If15:p1 + + +0 + + + diff --git a/docs/chapter07/Makefile b/docs/chapter07/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter07/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter07/README.md b/docs/chapter07/README.md new file mode 100644 index 00000000..19dbcfe0 --- /dev/null +++ b/docs/chapter07/README.md @@ -0,0 +1,244 @@ +# Chapter 7: While Statement + +# Table of Contents + +1. [Dealing With Back Edges](#dealing-with-back-edges) +2. [New Node Types](#new-node-types) +3. [Detailed Steps](#detailed-steps) +4. [Visualization](#visualization) +5. [Nested Loops](#nested-loops) +5. [Loop With Nested If](#loop-with-nested-if) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter07) 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-chapter06...linear-chapter07) it to the previous chapter. + + +In this chapter we introduce the `while` statement. + +Here is the [complete language grammar](07-grammar.md) for this chapter. + + +## Dealing With Back Edges + +The complication introduced by looping constructs is that variables flow back into the body of the loop on iteration. +For example: + +```java +while(arg < 10) { + arg = arg + 1; +} +return arg; +``` + +The variable `arg` is assigned a new value inside the body of the loop, and this then flows back into the body of the loop. + +In general, we will rewrite the looping construct as follows: + +```java +loop_head: +if( !(arg < 10) ) + goto loop_exit; +arg = arg + 1; +goto loop_head; + +loop_exit: +``` + +Above is for illustration only, we do not have labels and `goto` statements in the language. + +From an SSA[^1] point of view, since `arg` flows back, it requires a `phi` node at the head. Conceptually we would like the outcome to be: + +```java +// arg1 represents incoming arg +// +loop_head: +arg2 = phi(arg1, arg3); +if( !(arg2 < 10) ) + goto loop_exit; +arg3 = arg2 + 1; +goto loop_head; + +loop_exit: +``` + +Notice that the phi for `arg2` refers to `arg3`, which is not known at the time we parse the `while` loop predicate. This is the crux of the problem that we need +to solve in order to successfully construct the Sea of Nodes graph, which is always in SSA form. + +Recall from [Chapter 5](../chapter05/README.md) that when parsing `if` statements, we clone the symbol tables as we go past the `if` predicate. +Later we merge the two sets of symbol tables at a `Region` - creating phis for all names that encountered a change in definition within the two +branches of the `if` statement. In the case of the `if` statement, the phis are created at the merge point when we already know the definitions +that are being merged. + +The essential idea for loop constructs is to eagerly create phis for all names in the symbol tables *before* we enter the loop's `if` condition, +since we do not know which names will be redefined inside the body of the loop. When the loop terminates, we go back and remove unnecessary +phis. We call this approach the "eager phi" approach.[^2] + +In [Chapter 8](../chapter08) we will implement a "lazy phi" approach that creates phis only when we encounter redefinition of a name. + +## New Node Types + +Our list of nodes remains the same as in [Chapter 5](../chapter05/README.md), however, we create a subtype of `Region` named `Loop` to better +encapsulate some of the additional logic required. A key aspect of this is to temporarily disable peepholes of the `Region` and any phis +created until we complete parsing the loop body. This is because our phis are not fully constructed until the loop end. + +## Detailed Steps + +1. We start by creating a new subclass of `Region`, the `Loop`. The `Loop` gets two control inputs, + the first is the entry point, i.e. the current binding to `$ctrl`, and second (`null`) is a placeholder for the back edge that is + set after loop is parsed. The absence of a back edge is used as an indicator to switch off peepholes of the region and + associated phis. + + ```java + ctrl(new LoopNode(ctrl(),null).peephole()); + ``` + + The newly created region becomes the current control. + +2. We duplicate the current Scope node. This involves duplicating all the symbols at + every level with the scope, and creating phis for every symbol except the `$ctrl` binding. + + ```java + // Make a new Scope for the body. + _scope = _scope.dup(true); + ``` + + Note that the `dup` call is given an argument `true`. This triggers creating phis. The code + that creates the phis in the `dup()` method is shown below. + + ```java + // boolean loop=true if this is a loop region + + String[] names = reverseNames(); // Get the variable names + dup.add_def(ctrl()); // Control input is just copied + for( int i=1; ikeep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + ``` + +4. We make another clone of the current scope. This will be the exit scope that will live after the loop ends, + therefore `$ctrl` in the exit scope is set to the `False` projection. + The exit scope captures any side effects of the loop's predicate. + + ```java + // The exit scope, accounting for any side effects in the predicate + var exit = _scope.dup(); + exit.ctrl(ifF); + ``` + +5. We now set the control to the `True` projection and parse the loop body. + + ```java + // Parse the true side, which corresponds to loop body + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + ``` + +6. After the loop body is parsed, we go back and process all the phis we created earlier. + + ```java + // The true branch loops back, so whatever is current control gets + // added to head loop as input + head.endLoop(_scope, exit); + ``` + + The `endLoop` method sets the second control of the loop region to the control from the back edge. + It then goes through all the phis and sets the second data input on the phi to the corresponding entry + from the loop body; phis that were not used are peepholed and get replaced by the original input. + + ```java + Node ctrl = ctrl(); + ctrl.set_def(2,back.ctrl()); + for( int i=1; i