From 101f482058855c6e1a8a59a9f8fe2191cfb26ac7 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 --- README.md | 2 +- 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 ++++++++++++++ .../com/seaofnodes/simple/GraphVisualizer.java | 116 ++++--- src/main/java/com/seaofnodes/simple/IRPrinter.java | 124 +++++++ src/main/java/com/seaofnodes/simple/Parser.java | 74 +++- .../java/com/seaofnodes/simple/node/AddNode.java | 8 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 8 +- .../com/seaofnodes/simple/node/ConstantNode.java | 6 +- .../java/com/seaofnodes/simple/node/DivNode.java | 8 +- .../java/com/seaofnodes/simple/node/IfNode.java | 10 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 28 ++ .../java/com/seaofnodes/simple/node/MinusNode.java | 6 +- .../java/com/seaofnodes/simple/node/MulNode.java | 8 +- src/main/java/com/seaofnodes/simple/node/Node.java | 61 +++- .../java/com/seaofnodes/simple/node/NotNode.java | 6 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 28 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 5 +- .../com/seaofnodes/simple/node/RegionNode.java | 15 +- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 58 +++- .../java/com/seaofnodes/simple/node/StartNode.java | 5 +- .../java/com/seaofnodes/simple/node/StopNode.java | 8 +- .../java/com/seaofnodes/simple/node/SubNode.java | 8 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 12 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 32 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 234 +++++++++++++ 37 files changed, 2615 insertions(+), 134 deletions(-) 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 create mode 100644 src/main/java/com/seaofnodes/simple/IRPrinter.java create mode 100644 src/main/java/com/seaofnodes/simple/node/LoopNode.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter07Test.java diff --git a/README.md b/README.md index 301d8adf..09265040 100644 --- a/README.md +++ b/README.md @@ -48,7 +48,7 @@ The Simple language is styled after a subset of C or Java. simplifications. * [Chapter 5](docs/chapter05/README.md): `if` statement. CFG construction. * [Chapter 6](docs/chapter06/README.md): Peephole optimization around dead control flow. -* Chapter 7: `while` statement; looping constructs - eager phi approach. +* [Chapter 7](docs/chapter07/README.md): `while` statement; looping constructs - eager phi approach. * Chapter 8: Looping constructs continued, lazy phi creation, `break` and `continue` statements. * Chapter 9: Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * Chapter 10: User defined Struct types. Memory effects: 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 all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter06 {\n"); + sb.append("digraph chapter07 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -36,42 +45,48 @@ public class GraphVisualizer { // nodes much prettier to look at. sb.append("\tconcentrate=\"true\";\n"); + // Force nested scopes to order + sb.append("\tcompound=\"true\";\n"); + // Just the Nodes first, in a cluster no edges nodes(sb, all); // Now the scopes, in a cluster no edges - for (ScopeNode sn: parser._xScopes) - scopes(sb, sn); + for( ScopeNode scope : parser._xScopes ) + scope( sb, scope ); // Walk the Node edges nodeEdges(sb, all); - // Walk the Scope edges - for (ScopeNode sn: parser._xScopes) - scopeEdges(sb, sn); + // Walk the active Scope edges + for( ScopeNode scope : parser._xScopes ) + scopeEdges( sb, scope ); sb.append("}\n"); return sb.toString(); } - - private void nodes(StringBuilder sb, Collection all) { + private void nodesByCluster(StringBuilder sb, boolean doCtrl, Collection all) { + if (!_separateControlCluster && doCtrl) // all nodes in 1 cluster + return; // Just the Nodes first, in a cluster no edges - sb.append("\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name - for( Node n : all ) { - if( n instanceof ProjNode || n instanceof ScopeNode ) + sb.append(doCtrl ? "\tsubgraph cluster_Controls {\n" : "\tsubgraph cluster_Nodes {\n"); // Magic "cluster_" in the subgraph name + for (Node n : all) { + if (n instanceof ProjNode || n instanceof ScopeNode) continue; // Do not emit, rolled into MultiNode or Scope cluster already + if (_separateControlCluster && doCtrl && !n.isCFG()) continue; + if (_separateControlCluster && !doCtrl && n.isCFG()) continue; sb.append("\t\t").append(n.uniqueName()).append(" [ "); String lab = n.glabel(); - if( n instanceof MultiNode ) { + if (n instanceof MultiNode) { // Make a box with the MultiNode on top, and all the projections on the bottom sb.append("shape=plaintext label=<\n"); sb.append("\t\t\t\n"); sb.append("\t\t\t\n"); sb.append("\t\t\t"); boolean doProjTable = false; - for( Node use : n._outputs ) { - if( use instanceof ProjNode proj ) { + for (Node use : n._outputs) { + if (use instanceof ProjNode proj) { if (!doProjTable) { doProjTable = true; sb.append(""); } sb.append(""); } } @@ -94,41 +109,46 @@ public class GraphVisualizer { } else { // control nodes have box shape // other nodes are ellipses, i.e. default shape - if( n.isCFG() ) - sb.append("shape=box style=filled fillcolor=yellow "); - if( n instanceof PhiNode ) - sb.append("style=filled fillcolor=lightyellow "); + if (n.isCFG()) sb.append("shape=box style=filled fillcolor=yellow "); + else if (n instanceof PhiNode) sb.append("style=filled fillcolor=lightyellow "); sb.append("label=\"").append(lab).append("\" "); } sb.append("];\n"); } - - // Force Region & Phis to line up - for( Node n : all ) { - if( n instanceof RegionNode region ) { - sb.append("\t\t{ rank=same; "); - sb.append(region).append(";") ; - for( Node phi : region._outputs ) - if( phi instanceof PhiNode ) - sb.append(phi.uniqueName()).append(";"); - sb.append("}\n"); + if (!_separateControlCluster) { + // Force Region & Phis to line up + for (Node n : all) { + if (n instanceof RegionNode region) { + sb.append("\t\t{ rank=same; "); + sb.append(region).append(";"); + for (Node phi : region._outputs) + if (phi instanceof PhiNode) sb.append(phi.uniqueName()).append(";"); + sb.append("}\n"); + } } } - sb.append("\t}\n"); // End Node cluster } - private void scopes( StringBuilder sb, ScopeNode scopenode) { + private void nodes(StringBuilder sb, Collection all) { + nodesByCluster(sb, true, all); + nodesByCluster(sb, false, all); + } + + // Build a nested scope display, walking the _prev edge + private void scope( StringBuilder sb, ScopeNode scope ) { sb.append("\tnode [shape=plaintext];\n"); - int level=0; - for( HashMap scope : scopenode._scopes ) { - String scopeName = makeScopeName(scopenode, level); + int level=1; + for( int idx = scope._scopes.size()-1; idx>=0; idx-- ) { + var syms = scope._scopes.get(idx); + String scopeName = makeScopeName(scope, level); sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name sb.append("\t\t").append(scopeName).append(" [label=<\n"); sb.append("\t\t\t
").append(lab).append("
").append("\n"); @@ -79,7 +94,7 @@ public class GraphVisualizer { sb.append("\t\t\t\t
").append(proj.glabel()).append("
\n"); // Add the scope level - sb.append("\t\t\t"); - for( String name : scope.keySet() ) + int scopeLevel = scope._scopes.size()-level; + sb.append("\t\t\t"); + for(String name: syms.keySet()) sb.append(""); sb.append("\n"); sb.append("\t\t\t
").append(level).append("
").append(scopeLevel).append("").append(name).append("
>];\n"); @@ -137,7 +157,7 @@ public class GraphVisualizer { // Scope clusters nest, so the graphics shows the nested scopes, so // they are not closed as they are printed; so they just keep nesting. // We close them all at once here. - sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters + sb.append( "\t}\n".repeat( level-1 ) ); // End all Scope clusters } private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } @@ -153,8 +173,8 @@ public class GraphVisualizer { // ScopeNodes are done separately if( n instanceof ConstantNode || n instanceof ProjNode || n instanceof ScopeNode ) continue; - int i=0; - for( Node def : n._inputs ) { + for( int i=0; idef edge from Phi to Region. sb.append('\t').append(n.uniqueName()); @@ -173,21 +193,25 @@ public class GraphVisualizer { // control edges are colored red if( def.isCFG() ) sb.append(" color=red"); + // Backedges do not add a ranking constraint + if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) ) + sb.append(" constraint=false"); sb.append("];\n"); } - i++; } } } // Walk the scope edges - private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) { + private void scopeEdges( StringBuilder sb, ScopeNode scope ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); - int level=0; - for( HashMap scope : scopenode._scopes ) { - String scopeName = makeScopeName(scopenode, level); - for( String name : scope.keySet() ) { - Node def = scopenode.in(scope.get(name)); + int level=1; + for( int i = scope._scopes.size()-1; i>=0; i-- ) { + var syms = scope._scopes.get(i); + String scopeName = makeScopeName(scope, level); + for( String name : syms.keySet() ) { + int idx = syms.get(name); + Node def = scope.in(idx); if( def==null ) continue; sb.append("\t") .append(scopeName).append(":") diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java new file mode 100644 index 00000000..2a6dbefd --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -0,0 +1,124 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.LoopNode; +import com.seaofnodes.simple.node.Node; + +import java.util.ArrayList; +import java.util.BitSet; + +public class IRPrinter { + + // Another bulk pretty-printer. Makes more effort at basic-block grouping. + public static String prettyPrint(Node node, int depth) { + // First, a Breadth First Search at a fixed depth. + BFS bfs = new BFS(node,depth); + // Convert just that set to a post-order + ArrayList rpos = new ArrayList<>(); + BitSet visit = new BitSet(); + for( int i=bfs._lim; i< bfs._bfs.size(); i++ ) + postOrd( bfs._bfs.get(i), rpos, visit, bfs._bs); + // Reverse the post-order walk + StringBuilder sb = new StringBuilder(); + boolean gap=false; + for( int i=rpos.size()-1; i>=0; i-- ) { + Node n = rpos.get(i); + if( n.isCFG() || n.isMultiHead() ) { + if( !gap ) sb.append("\n"); // Blank before multihead + n._printLine(sb); // Print head + while( --i >= 0 ) { + Node t = rpos.get(i); + if( !t.isMultiTail() ) { i++; break; } + t._printLine(sb); + } + sb.append("\n"); // Blank after multitail + gap = true; + } else { + n._printLine( sb ); + gap = false; + } + } + return sb.toString(); + } + + private static void postOrd(Node n, ArrayList rpos, BitSet visit, BitSet bfs) { + if( !bfs.get(n._nid) ) + return; // Not in the BFS visit + if( visit.get(n._nid) ) return; // Already post-order walked + visit.set(n._nid); + // First walk the CFG, then everything + if( n.isCFG() ) { + for( Node use : n._outputs ) + if( use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) + postOrd(use, rpos,visit,bfs); + for( Node use : n._outputs ) + if( use.isCFG() ) + postOrd(use,rpos,visit,bfs); + } + for( Node use : n._outputs ) + postOrd(use, rpos,visit,bfs); + // Post-order + rpos.add(n); + } + + // Breadth-first search, broken out in a class to keep in more independent. + // Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead). + public static class BFS { + // A breadth first search, plus MultiHeads for any MultiTails + public final ArrayList _bfs; + public final BitSet _bs; // Visited members by node id + public final int _depth; // Depth limit + public final int _lim; // From here to _bfs._len can be roots for a reverse search + public BFS( Node base, int d ) { + _depth = d; + _bfs = new ArrayList<>(); + _bs = new BitSet(); + + add(base); // Prime the pump + int idx=0, lim=1; // Limit is where depth counter changes + while( idx < _bfs.size() ) { // Ran out of nodes below depth + Node n = _bfs.get(idx++); + for( Node def : n._inputs ) + if( def!=null && !_bs.get(def._nid) ) + add(def); + if( idx==lim ) { // Depth counter changes at limit + if( --d < 0 ) + break; // Ran out of depth + lim = _bfs.size(); // New depth limit + } + } + // Toss things past the limit except multi-heads + while( idx < _bfs.size() ) { + Node n = _bfs.get(idx); + if( n.isMultiHead() ) idx++; + else del(idx); + } + // Root set is any node with no inputs in the visited set + lim = _bfs.size(); + for( int i=_bfs.size()-1; i>=0; i-- ) + if( !any_visited(_bfs.get(i)) ) + swap( i,--lim); + _lim = lim; + } + void swap( int x, int y ) { + if( x==y ) return; + Node tx = _bfs.get(x); + Node ty = _bfs.get(y); + _bfs.set(x,ty); + _bfs.set(y,tx); + } + void add(Node n) { + _bfs.add(n); + _bs.set(n._nid); + } + void del(int idx) { + Node n = Utils.del(_bfs, idx); + _bs.clear(n._nid); + } + boolean any_visited( Node n ) { + for( Node def : n._inputs ) + if( def!=null && _bs.get(def._nid) ) + return true; + return false; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 1a15efa3..cfb4deb4 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -52,6 +52,7 @@ public class Parser { add("int"); add("return"); add("true"); + add("while"); }}; @@ -134,11 +135,80 @@ public class Parser { else if (matchx("int")) return parseDecl(); else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); + else if (matchx("while")) return parseWhile(); else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";")) return null; // Empty statement else return parseExpressionStatement(); } + /** + * Parses a while statement + * + * 
+     *     while ( expression ) statement
+     *
+ * @return a {@link Node}, never {@code null} + */ + private Node parseWhile() { + require("("); + + // Loop region has two control inputs, the first is the entry + // point, and second is back edge that is set after loop is parsed + // (see end_loop() call below). Note that the absence of back edge is + // used as an indicator to switch off peepholes of the region and + // associated phis; see {@code inProgress()}. + + ctrl(new LoopNode(ctrl()).peephole()); // Note we set back edge to null here + + // At loop head, we clone the current Scope (this includes all + // names in every nesting level within the Scope). + // We create phis eagerly for all the names we find, see dup(). + + // Save the current scope as the loop head + ScopeNode head = _scope.keep(); + // Clone the head Scope to create a new Scope for the body. + // Create phis eagerly as part of cloning + _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis + + // Parse predicate + var pred = require(parseExpression(), ")"); + // IfNode takes current control and predicate + IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + + // Clone the body Scope to create the exit Scope + // which accounts for any side effects in the predicate + // The exit Scope will be the final scope after the loop, + // And its control input is the False branch of the loop predicate + // Note that body Scope is still our current scope + var exit = _scope.dup(); + _xScopes.push(exit); + exit.ctrl(ifF); + + // Parse the true side, which corresponds to loop body + // Our current scope is the body Scope + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + + // The true branch loops back, so whatever is current control (_scope.ctrl) gets + // added to head loop as input. endLoop() updates the head scope, + // and goes through all the phis that were created earlier. For each + // phi, it sets the second input to the corresponding input from the back edge. + // If the phi is redundant, it is replaced by its sole input. + head.endLoop(_scope, exit); + head.unkeep().kill(); + + _xScopes.pop(); // Cleanup + _xScopes.pop(); // Cleanup + + // At exit the false control is the current control, and + // the scope is the exit scope after the exit test. + return (_scope = exit); + } + /** * Parses a statement * @@ -369,7 +439,7 @@ public class Parser { // Require an exact match private void require(String syntax) { require(null, syntax); } - private Node require(Node n, String syntax) { + private N require(N n, String syntax) { if (match(syntax)) return n; throw errorSyntax(syntax); } @@ -378,7 +448,7 @@ public class Parser { return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); } - static RuntimeException error(String errorMessage) { + public static RuntimeException error( String errorMessage ) { return new RuntimeException(errorMessage); } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index b37785f6..8f3e5a98 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; +import java.util.BitSet; + public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -10,9 +12,9 @@ public class AddNode extends Node { @Override public String glabel() { return "+"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("+")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("+"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index a9ec6838..0c32d50d 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + abstract public class BoolNode extends Node { public BoolNode(Node lhs, Node rhs) { @@ -18,9 +20,9 @@ abstract public class BoolNode extends Node { public String glabel() { return op(); } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append(op())); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append(op()), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 23bc4d1a..49bb30ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer @@ -29,10 +31,12 @@ public class ConstantNode extends Node { public String uniqueName() { return "Con_" + _nid; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return _con._print(sb); } + @Override public boolean isMultiTail() { return true; } + @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 519a8c8a..7207fd48 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class DivNode extends Node { public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -11,9 +13,9 @@ public class DivNode extends Node { @Override public String glabel() { return "//"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("/")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("/"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 34846e99..0f414c08 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -4,6 +4,8 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + public class IfNode extends MultiNode { public IfNode(Node ctrl, Node pred) { @@ -14,12 +16,13 @@ public class IfNode extends MultiNode { public String label() { return "If"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("if( "); - return in(1)._print0(sb).append(" )"); + return in(1)._print0(sb, visited).append(" )"); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } public Node ctrl() { return in(0); } public Node pred() { return in(1); } @@ -27,7 +30,8 @@ public class IfNode extends MultiNode { @Override public Type compute() { // If the If node is not reachable then neither is any following Proj - if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER; + if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) + return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java new file mode 100644 index 00000000..81f707ec --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +import java.util.BitSet; + +public class LoopNode extends RegionNode { + + public LoopNode( Node entry ) { super(null,entry,null); } + + Node entry() { return in(1); } + Node back () { return in(2); } + + @Override + public String label() { return "Loop"; } + + @Override + public Type compute() { + return inProgress() ? Type.CONTROL : super.compute(); + } + + @Override + public Node idealize() { + return inProgress() ? null : super.idealize(); + } + + @Override Node idom() { return entry(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 0d59ef25..3d944fd4 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } @@ -11,8 +13,8 @@ public class MinusNode extends Node { @Override public String glabel() { return "-"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(-")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("(-"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 0380c079..2e701a4e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class MulNode extends Node { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @@ -11,9 +13,9 @@ public class MulNode extends Node { @Override public String glabel() { return "*"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(")); - in(2)._print0(sb.append("*")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("*"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 97ba68ab..35b07781 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -98,18 +98,51 @@ public abstract class Node { // tik-tok style; the common _print0 calls the per-Node _print1, which // calls back to _print0; public final String print() { - return _print0(new StringBuilder()).toString(); + return _print0(new StringBuilder(), new BitSet()).toString(); } - // This is the common print: check for DEAD and print "DEAD" else call the - // per-Node print1. - final StringBuilder _print0(StringBuilder sb) { + // This is the common print: check for repeats, check for DEAD and print + // "DEAD" else call the per-Node print1. + final StringBuilder _print0(StringBuilder sb, BitSet visited) { + if (visited.get(_nid)) + return sb.append(label()); + visited.set(_nid); return isDead() ? sb.append(uniqueName()).append(":DEAD") - : _print1(sb); + : _print1(sb, visited); + } + // Every Node implements this; a partial-line recursive print + abstract StringBuilder _print1(StringBuilder sb, BitSet visited); + + + // Print a node on 1 line, columnar aligned, as: + // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE + // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt + public void _printLine(StringBuilder sb ) { + sb.append("%4d %-7.7s ".formatted(_nid,label())); + if( _inputs==null ) { + sb.append("DEAD\n"); + return; + } + for( Node def : _inputs ) + sb.append(def==null ? "____ " : "%4d ".formatted(def._nid)); + for( int i = _inputs.size(); i<3; i++ ) + sb.append(" "); + sb.append(" [[ "); + for( Node use : _outputs ) + sb.append("%4d ".formatted(use._nid)); + int lim = 5 - Math.max(_inputs.size(),3); + for( int i = _outputs.size(); i N keep() { return addUse(null); } // Remove bogus null. public N unkeep() { delUse(null); return (N)this; } + + + // Replace self with nnn in the graph, making 'this' go dead + void subsume( Node nnn ) { + assert nnn!=this; + while( nOuts() > 0 ) { + Node n = _outputs.removeLast(); + int idx = Utils.find(n._inputs, this); + n._inputs.set(idx,nnn); + nnn.addUse(n); + } + kill(); + } + // ------------------------------------------------------------------------ // Graph-based optimizations diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index e3683646..39df410d 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import java.util.BitSet; + public class NotNode extends Node { public NotNode(Node in) { super(null, in); } @@ -11,8 +13,8 @@ public class NotNode extends Node { @Override public String glabel() { return "!"; } @Override - StringBuilder _print1(StringBuilder sb) { - in(1)._print0(sb.append("(!")); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("(!"), visited); return sb.append(")"); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 15088e08..2a4ff52a 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class PhiNode extends Node { final String _label; @@ -13,19 +15,27 @@ public class PhiNode extends Node { @Override public String glabel() { return "φ_"+_label; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { + if( region().inProgress() ) + sb.append("Z"); sb.append("Phi("); - for( Node in : _inputs ) - in._print0(sb).append(","); + for( Node in : _inputs ) { + if (in == null) sb.append("____"); + else in._print0(sb, visited); + sb.append(","); + } sb.setLength(sb.length()-1); sb.append(")"); return sb; } - Node region() { return in(0); } + RegionNode region() { return (RegionNode)in(0); } + @Override public boolean isMultiTail() { return true; } @Override public Type compute() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -34,6 +44,9 @@ public class PhiNode extends Node { @Override public Node idealize() { + if( !(region() instanceof RegionNode r ) || r.inProgress() ) + return null; + // If we have only a single unique input, become it. Node live = singleUniqueInput(); if (live != null) @@ -79,5 +92,10 @@ public class PhiNode extends Node { return live; } - + @Override + boolean allCons() { + if( !(region() instanceof RegionNode r) || r.inProgress() ) + return false; + return super.allCons(); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 85f28037..3c3f73b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; +import java.util.BitSet; + public class ProjNode extends Node { // Which slice of the incoming multi-part value @@ -21,9 +23,10 @@ public class ProjNode extends Node { public String label() { return _label; } @Override - StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index bb7998a3..acaadaf1 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,21 +3,26 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + public class RegionNode extends Node { - public RegionNode(Node... inputs) { super(inputs); } + + public RegionNode(Node... nodes) { super(nodes); } @Override public String label() { return "Region"; } @Override - StringBuilder _print1(StringBuilder sb) { + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(label()).append(_nid); } @Override public boolean isCFG() { return true; } + @Override public boolean isMultiHead() { return true; } @Override public Type compute() { + if( inProgress() ) return Type.CONTROL; Type t = Type.XCONTROL; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -26,6 +31,7 @@ public class RegionNode extends Node { @Override public Node idealize() { + if( inProgress() ) return null; int path = findDeadInput(); if( path != 0 ) { for( Node phi : _outputs ) @@ -72,4 +78,9 @@ public class RegionNode extends Node { _idepth = lhs._idepth+1; return (_idom=lhs); } + + // True if last input is null + public final boolean inProgress() { + return in(nIns()-1) == null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 6130d050..312058b9 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; +import java.util.BitSet; + /** * The Return node has two inputs. The first input is a control node and the * second is the data node that supplies the return value. @@ -24,8 +26,8 @@ public class ReturnNode extends Node { public String label() { return "Return"; } @Override - StringBuilder _print1(StringBuilder sb) { - return expr()._print0(sb.append("return ")).append(";"); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return expr()._print0(sb.append("return "), visited).append(";"); } @Override public boolean isCFG() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index a7a04a42..a4fcbe65 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -33,22 +33,16 @@ public class ScopeNode extends Node { @Override public String label() { return "Scope"; } @Override - StringBuilder _print1(StringBuilder sb) { - sb.append(label()); - for( HashMap scope : _scopes ) { - sb.append("["); - boolean first=true; - for( String name : scope.keySet() ) { - if( !first ) sb.append(", "); - first=false; - sb.append(name).append(":"); - Node n = in(scope.get(name)); - if( n==null ) sb.append("null"); - else n._print0(sb); - } - sb.append("]"); + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("Scope[ "); + String[] names = reverseNames(); + for( int j=0; j * The new Scope is a full-fledged Node with proper use<->def edges. */ - public ScopeNode dup() { + public ScopeNode dup() { return dup(false); } + public ScopeNode dup(boolean loop) { ScopeNode dup = new ScopeNode(); // Our goals are: // 1) duplicate the name bindings of the ScopeNode across all stack levels @@ -147,9 +142,19 @@ public class ScopeNode extends Node { // 3) Ensure that the order of defs is the same to allow easy merging for( HashMap syms : _scopes ) dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i