From 399bb146cc0bb0c548cd0b50e51fb9aa29a7900c Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Mon, 15 Jan 2024 00:13:44 +0000 Subject: Implement break and continue (#55) * #52 Update chapter8 to align with chapter7 * #52 Update chapter8 to align with chapter7 * #52 Fix spacing * #51 get started on break and continue * #51 get started on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * break & continue scopes are made lazily, and merged into as discovered Drop ContBreak. Drop ScopeNode.addScope. Add a simple mergeScopes. Simplify Region.inProgress; drop from child classes, use in Region. Add a ConstantNode.XCONTROL shortcut. * Fix some regressions * Error on dead code after break/continue * A more robust dead-def check * Fix for dead loop-back path * Fix scope shadowing bug with continue/break Turn on LAZY phis by default; fix minor golden test results * Fix a case with both break & continue * #51 more on break and continue * #51 more on break and continue * #51 more on break and continue * #51 fix erroneous push of scope * #51 fix import * #51 update test expected results * #51 Start Chapter8 writeup * #51 Start Chapter8 writeup * #51 _scope needs killing after continue * Add graph evaluator (#56) * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 wip writeup * #51 update code comments / add assertion * #51 revert assertion * #51 evaluate graph to verify test outcome * #51 add code snippets * #51 add examples * Cleanup README Comment for usefullness of true Loops. Try to distiguish `PhiNode` as the programming construct from `phi` as the mathematically SSA notation. Flow long lines. Remove LAZY flag, set as `true`. Fold up true tests. * minor comment * #51 Check _breakScope is not null when parsing break or continue to detect use outside of loop * #51 in parseComparison we need to move the op= version above the op version, since at this time using <= and >= does not work since they are parsed as > and < with a preceeding = which causes an error * #51 Update main README to link to chapter 8 * Remove useless test --------- Co-authored-by: Cliff Click Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> --- chapter08/docs/08-grammar.md | 10 ++ chapter08/docs/08-graph1.gv | 107 ++++++++++++ chapter08/docs/08-graph1.svg | 359 ++++++++++++++++++++++++++++++++++++++ chapter08/docs/08-graph2.gv | 103 +++++++++++ chapter08/docs/08-graph2.svg | 332 +++++++++++++++++++++++++++++++++++ chapter08/docs/08-graph3.gv | 111 ++++++++++++ chapter08/docs/08-graph3.svg | 386 +++++++++++++++++++++++++++++++++++++++++ chapter08/docs/build-graphs.sh | 5 +- 8 files changed, 1412 insertions(+), 1 deletion(-) create mode 100644 chapter08/docs/08-graph1.gv create mode 100644 chapter08/docs/08-graph1.svg create mode 100644 chapter08/docs/08-graph2.gv create mode 100644 chapter08/docs/08-graph2.svg create mode 100644 chapter08/docs/08-graph3.gv create mode 100644 chapter08/docs/08-graph3.svg (limited to 'chapter08/docs') diff --git a/chapter08/docs/08-grammar.md b/chapter08/docs/08-grammar.md index cee33030..c603f335 100644 --- a/chapter08/docs/08-grammar.md +++ b/chapter08/docs/08-grammar.md @@ -14,6 +14,8 @@ statement | expressionStatement | ifStatement | whileStatement + | breakStatement + | continueStatment | metaStatement ; @@ -21,6 +23,14 @@ whileStatement : 'while' '(' expression ')' statement ; +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; diff --git a/chapter08/docs/08-graph1.gv b/chapter08/docs/08-graph1.gv new file mode 100644 index 00000000..604ee0fe --- /dev/null +++ b/chapter08/docs/08-graph1.gv @@ -0,0 +1,107 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +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="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg35 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Region39 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return40 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;Phi_arg35;} + { rank=same; Region39;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return40[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region39[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]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If11:p1[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Phi_arg35 -> Region34 [style=dotted taillabel=0]; + Phi_arg35 -> Phi_arg8[taillabel=1]; + Phi_arg35 -> Add16[taillabel=2 constraint=false]; + Region39 -> If19:p0[taillabel=1 color=red]; + Region39 -> If28:p1[taillabel=2 color=red]; + Return40 -> Region34[taillabel=0 color=red]; + Return40 -> Phi_arg35[taillabel=1]; +} diff --git a/chapter08/docs/08-graph1.svg b/chapter08/docs/08-graph1.svg new file mode 100644 index 00000000..0f23a746 --- /dev/null +++ b/chapter08/docs/08-graph1.svg @@ -0,0 +1,359 @@ + + + + + + +chapter08 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return40 + +Return + + + +Stop3->Return40 + + +0 + + + +Loop6 + +Loop + + + +Loop6->Start2:p0 + + +1 + + + +Region39 + +Region + + + +Loop6->Region39 + + +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 + + +If + + + +True + + +False + + + +If11->Loop6 + + +0 + + + +If11->LT10 + + +1 + + + +Con_15 + +1 + + + +Add16->Phi_arg8 + + + +1 + + + +Add16->Con_15 + + +2 + + + +Con_17 + +5 + + + +EQ18 + +== + + + +EQ18->Add16 + + +1 + + + +EQ18->Con_17 + + +2 + + + +If19 + + +If + + + +True + + +False + + + +If19->If11:p0 + + +0 + + + +If19->EQ18 + + +1 + + + +Con_26 + +6 + + + +EQ27 + +== + + + +EQ27->Add16 + + + +1 + + + +EQ27->Con_26 + + +2 + + + +If28 + + +If + + + +True + + +False + + + +If28->If19:p1 + + +0 + + + +If28->EQ27 + + +1 + + + +Region34 + +Region + + + +Region34->If11:p1 + + +1 + + + +Region34->If28:p0 + + +2 + + + +Phi_arg35 + +φ_arg + + + +Phi_arg35->Phi_arg8 + + +1 + + + +Phi_arg35->Add16 + +2 + + + +Phi_arg35->Region34 + + +0 + + + +Region39->If19:p0 + + +1 + + + +Region39->If28:p1 + + +2 + + + +Return40->Region34 + + +0 + + + +Return40->Phi_arg35 + + +1 + + + diff --git a/chapter08/docs/08-graph2.gv b/chapter08/docs/08-graph2.gv new file mode 100644 index 00000000..2fa82523 --- /dev/null +++ b/chapter08/docs/08-graph2.gv @@ -0,0 +1,103 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +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="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Con_26 [ label="6" ]; + EQ27 [ label="==" ]; + If28 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region34 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Region38 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region34;} + { rank=same; Region38;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> Region38[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]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + EQ27 -> Add16[taillabel=1]; + EQ27 -> Con_26[taillabel=2]; + If28 -> If19:p1[taillabel=0 color=red]; + If28 -> EQ27[taillabel=1]; + Region34 -> If19:p0[taillabel=1 color=red]; + Region34 -> If28:p0[taillabel=2 color=red]; + Region38 -> Region34[taillabel=1 color=red]; + Region38 -> If28:p1[taillabel=2 color=red]; + Return39 -> If11:p1[taillabel=0 color=red]; + Return39 -> Phi_arg8[taillabel=1]; +} diff --git a/chapter08/docs/08-graph2.svg b/chapter08/docs/08-graph2.svg new file mode 100644 index 00000000..1f497470 --- /dev/null +++ b/chapter08/docs/08-graph2.svg @@ -0,0 +1,332 @@ + + + + + + +chapter08 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return39 + +Return + + + +Stop3->Return39 + + +0 + + + +Loop6 + +Loop + + + +Loop6->Start2:p0 + + +1 + + + +Region38 + +Region + + + +Loop6->Region38 + + +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 + + +If + + + +True + + +False + + + +If11->Loop6 + + +0 + + + +If11->LT10 + + +1 + + + +Con_15 + +1 + + + +Add16->Phi_arg8 + + + +1 + + + +Add16->Con_15 + + +2 + + + +Con_17 + +5 + + + +EQ18 + +== + + + +EQ18->Add16 + + +1 + + + +EQ18->Con_17 + + +2 + + + +If19 + + +If + + + +True + + +False + + + +If19->If11:p0 + + +0 + + + +If19->EQ18 + + +1 + + + +Con_26 + +6 + + + +EQ27 + +== + + + +EQ27->Add16 + + +1 + + + +EQ27->Con_26 + + +2 + + + +If28 + + +If + + + +True + + +False + + + +If28->If19:p1 + + +0 + + + +If28->EQ27 + + +1 + + + +Region34 + +Region + + + +Region34->If19:p0 + + +1 + + + +Region34->If28:p0 + + +2 + + + +Region38->If28:p1 + + +2 + + + +Region38->Region34 + + +1 + + + +Return39->Phi_arg8 + + +1 + + + +Return39->If11:p1 + + +0 + + + diff --git a/chapter08/docs/08-graph3.gv b/chapter08/docs/08-graph3.gv new file mode 100644 index 00000000..72ac10a8 --- /dev/null +++ b/chapter08/docs/08-graph3.gv @@ -0,0 +1,111 @@ +digraph chapter08 { +/* +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +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="+" ]; + Con_17 [ label="5" ]; + EQ18 [ label="==" ]; + If19 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region25 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg26 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Con_28 [ label="6" ]; + EQ29 [ label="==" ]; + If30 [ shape=plaintext label=< + + + +
If
+ + +
TrueFalse
+
> + ]; + Region36 [ shape=box style=filled fillcolor=yellow label="Region" ]; + Phi_arg37 [ style=filled fillcolor=lightyellow label="φ_arg" ]; + Return39 [ shape=box style=filled fillcolor=yellow label="Return" ]; + { rank=same; Loop6;Phi_arg8;} + { rank=same; Region25;Phi_arg26;} + { rank=same; Region36;Phi_arg37;} + } + edge [ fontname=Helvetica, fontsize=8 ]; + Stop3 -> Return39[taillabel=0 color=red]; + Loop6 -> Start2:p0[taillabel=1 color=red]; + Loop6 -> If30:p1[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]; + EQ18 -> Add16[taillabel=1]; + EQ18 -> Con_17[taillabel=2]; + If19 -> If11:p0[taillabel=0 color=red]; + If19 -> EQ18[taillabel=1]; + Region25 -> If11:p1[taillabel=1 color=red]; + Region25 -> If19:p0[taillabel=2 color=red]; + Phi_arg26 -> Region25 [style=dotted taillabel=0]; + Phi_arg26 -> Phi_arg8[taillabel=1]; + Phi_arg26 -> Add16[taillabel=2 constraint=false]; + EQ29 -> Add16[taillabel=1]; + EQ29 -> Con_28[taillabel=2]; + If30 -> If19:p1[taillabel=0 color=red]; + If30 -> EQ29[taillabel=1]; + Region36 -> Region25[taillabel=1 color=red]; + Region36 -> If30:p0[taillabel=2 color=red]; + Phi_arg37 -> Region36 [style=dotted taillabel=0]; + Phi_arg37 -> Phi_arg26[taillabel=1]; + Phi_arg37 -> Add16[taillabel=2 constraint=false]; + Return39 -> Region36[taillabel=0 color=red]; + Return39 -> Phi_arg37[taillabel=1]; +} \ No newline at end of file diff --git a/chapter08/docs/08-graph3.svg b/chapter08/docs/08-graph3.svg new file mode 100644 index 00000000..12aafcc5 --- /dev/null +++ b/chapter08/docs/08-graph3.svg @@ -0,0 +1,386 @@ + + + + + + +chapter08 + + +cluster_Nodes + + + + +Start2 + + +Start + + + +$ctrl + +arg + + + +Stop3 + +Stop + + + +Return39 + +Return + + + +Stop3->Return39 + + +0 + + + +Loop6 + +Loop + + + +Loop6->Start2:p0 + + +1 + + + +If30 + + +If + + + +True + + +False + + + +Loop6->If30:p1 + + +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 + + +If + + + +True + + +False + + + +If11->Loop6 + + +0 + + + +If11->LT10 + + +1 + + + +Con_15 + +1 + + + +Add16->Phi_arg8 + + + +1 + + + +Add16->Con_15 + + +2 + + + +Con_17 + +5 + + + +EQ18 + +== + + + +EQ18->Add16 + + +1 + + + +EQ18->Con_17 + + +2 + + + +If19 + + +If + + + +True + + +False + + + +If19->If11:p0 + + +0 + + + +If19->EQ18 + + +1 + + + +Region25 + +Region + + + +Region25->If11:p1 + + +1 + + + +Region25->If19:p0 + + +2 + + + +Phi_arg26 + +φ_arg + + + +Phi_arg26->Phi_arg8 + + +1 + + + +Phi_arg26->Add16 + + +2 + + + +Phi_arg26->Region25 + + +0 + + + +Con_28 + +6 + + + +EQ29 + +== + + + +EQ29->Add16 + + +1 + + + +EQ29->Con_28 + + +2 + + + +If30->If19:p1 + + +0 + + + +If30->EQ29 + + +1 + + + +Region36 + +Region + + + +Region36->Region25 + + +1 + + + +Region36->If30:p0 + + +2 + + + +Phi_arg37 + +φ_arg + + + +Phi_arg37->Add16 + + +2 + + + +Phi_arg37->Phi_arg26 + + +1 + + + +Phi_arg37->Region36 + + +0 + + + +Return39->Region36 + + +0 + + + +Return39->Phi_arg37 + + +1 + + + diff --git a/chapter08/docs/build-graphs.sh b/chapter08/docs/build-graphs.sh index 73c39624..f660790b 100644 --- a/chapter08/docs/build-graphs.sh +++ b/chapter08/docs/build-graphs.sh @@ -1,3 +1,6 @@ -dot -Tsvg 07-graph1.gv > 07-graph1.svg +dot -Tsvg 08-graph1.gv > 08-graph1.svg +dot -Tsvg 08-graph2.gv > 08-graph2.svg +dot -Tsvg 08-graph3.gv > 08-graph3.svg + -- cgit v1.2.3