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> --- README.md | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 1 - chapter08/README.md | 250 ++++++++++++- 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 +- .../java/com/seaofnodes/simple/GraphEvaluator.java | 175 ++++++++++ .../main/java/com/seaofnodes/simple/Parser.java | 94 +++-- .../java/com/seaofnodes/simple/node/LoopNode.java | 16 +- .../main/java/com/seaofnodes/simple/node/Node.java | 11 +- .../com/seaofnodes/simple/node/RegionNode.java | 10 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 37 +- .../java/com/seaofnodes/simple/Chapter08Test.java | 213 +++++++++++- 18 files changed, 2140 insertions(+), 82 deletions(-) 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 create mode 100644 chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java diff --git a/README.md b/README.md index 3424c5d9..113a1d39 100644 --- a/README.md +++ b/README.md @@ -35,7 +35,7 @@ The simple language will be a small subset of C. * [Chapter 5](chapter05/README.md): `if` statement. CFG construction. * [Chapter 6](chapter06/README.md): Peephole optimization around dead control flow. * [Chapter 7](chapter07/README.md): `while` statement. Looping construct - eager phi approach. -* Chapter 8: Looping construct continued, lazy phi creation, `break` and `continue` statements. +* [Chapter 8](chapter08/README.md): Looping construct continued, lazy phi creation, `break` and `continue` statements. * Chapter 9: Global Value Numbering. * Chapter 10: Functions and calls. * Chapter 11: Boolean operators `&&`, `||` and `!` including short circuit. diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 3b793758..7113f5c4 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; -import java.util.Collection; import java.util.BitSet; public class RegionNode extends Node { diff --git a/chapter08/README.md b/chapter08/README.md index ddfde17f..402d487a 100644 --- a/chapter08/README.md +++ b/chapter08/README.md @@ -1,3 +1,251 @@ # Chapter 8 -In this chapter we move from eager to lazy phi creation in loops. +In this chapter: + +* We move from eager to lazy `Phi` creation in loops. +* We add support for `break` and `continue` statements. +* We implement a Sea of Nodes Graph Evaluator. + +Here is the [complete language grammar](docs/08-grammar.md) for this chapter. + +## Lazy Phi Creation + +In [chapter 7](../chapter07/README.md), we created `PhiNode`s for all variables +in the loop head eagerly. This approach creates some unnecessary Phis but the +redundant Phis get cleaned up later. + +In this chapter we add support for creating the `PhiNode`s lazily. + +The main complication with creating `PhiNode`s lazily is that when we create a +Phi, it must be created in the innermost loop head scope where it would have +been created had we done it eagerly. Since scopes get duped in `if` and +`while` statements, we cannot just create Phis in the current scope. + +It turns out that the easiest way to create the `PhiNode`s lazily is to hook +them up to name lookup. But how do we know that a Phi must be created when we +access a name? We need a way to flag that a particular name mapping must be +converted to a `PhiNode` on lookup. + +We do this as follows: + +* In `ScopeNode.dup()`, if the Scope is being duplicated for a loop head, then + instead of setting the name's definition to the original node, we set it to + the Scope itself. This acts like a sentinel. + + ```java + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + dup.addDef(loop ? this : in(i)); + ``` + +* Subsequently, when a lookup accesses a name, we notice that the def is set to + the Scope node, and we create a `PhiNode` at this point. The relevant + implementation is in `ScopeNode.update()`. + + ```java + if( old instanceof ScopeNode loop ) { + // Lazy Phi! + old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? loop.in(idx) + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have insert a Phi in every loop nest. + : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + setDef(idx,old); + } + ``` + +* When we merge scopes, we ensure lazy `PhiNode` creation at the correct inner + scope level by invoking lookup by name instead of directly accessing the + defs. + + ```java + if( in(i) != that.in(i) ) // No need for redundant Phis + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + ``` + +* Finally, in `ScopeNode.endLoop()` we clean up any leftover sentinels, replacing the sentinel with the input from loop head. + + ```java + for( int i=1; i than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + ``` + +* The continue scope becomes the base scope for the subsequent `continue` + statement, thus forming a stack of continue scopes/regions. +* After the loop is done, if we find that a continue scope was created within + the loop, we must merge the current scope into the continue scope, and make + the continue scope the active scope. + + ```java + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + ``` + +## `break` Statement + +Implementing `break` is simpler than `continue`, because the exit scope is +created before we parse the loop body, and this becomes the initial `break` +scope. When we see `break`, we merge the current scope, after pruning any +nested lexical scopes, to the current break scope, and the resulting new scope +becomes the active break scope. + +## Parser Considerations + +Since a `continue` or `break` targets the immediate surrounding `while` loop, +we maintain a stack of the `continue` and `break` scopes. This is done by +saving the previous `continue` or `break` scope before parsing a `while` loop +and restoring afterward. + +## Examples + +### Example 1 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; +``` + +![Graph1](./docs/08-graph1.svg) + + +### Example 2 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; +``` + +![Graph1](./docs/08-graph2.svg) + +### Example 3 + +```java +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; +``` + +![Graph1](./docs/08-graph3.svg) + + +## Sea of Nodes Graph Evaluator + +TODO \ No newline at end of file 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 + diff --git a/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java new file mode 100644 index 00000000..cbd6f1f9 --- /dev/null +++ b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -0,0 +1,175 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.Arrays; +import java.util.BitSet; +import java.util.HashMap; + +public class GraphEvaluator { + + /** + * Find the start node from some node in the graph or null if there is no start node + */ + private static StartNode findStart(BitSet visit, Node node) { + if (node == null) return null; + if (node instanceof StartNode start) return start; + if( visit.get(node._nid) ) return null; + visit.set(node._nid); + for( Node def : node._inputs ) { + var res = findStart(visit,def); + if( res != null ) return res; + } + for( Node use : node._outputs ) { + var res = findStart(visit,use); + if( res != null ) return res; + } + return null; + } + + /** + * Find the control output from a control node + */ + private static Node findControl(Node control) { + for( Node use : control._outputs ) { + if (use.isCFG()) return use; + } + return null; + } + + /** + * Find the projection for a node + */ + private static ProjNode findProjection(Node node, int idx) { + for( Node use : node._outputs ) { + if (use instanceof ProjNode proj && proj._idx == idx) return proj; + } + return null; + } + + private static RuntimeException timeout() { + return new RuntimeException("Timeout"); + } + + /** + * Cache values for phi and parameter projection nodes. + */ + private final HashMap cacheValues = new HashMap<>(); + /** + * Cache for loop phis as they can depend on itself or other loop phis + */ + private long[] loopPhiCache = new long[16]; + + private GraphEvaluator() { + } + + private long div(DivNode div) { + long in2 = getValue(div.in(2)); + return in2 == 0 ? 0 : getValue(div.in(1)) / in2; + } + + /** + * Calculate the value of a node + */ + private long getValue(Node node) { + var cache = cacheValues.get(node); + if (cache != null) return cache; + return switch (node) { + case ConstantNode cons -> ((TypeInteger)cons.compute()).value(); + case AddNode add -> getValue(add.in(1)) + getValue(add.in(2)); + case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0; + case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0; + case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0; + case DivNode div -> div(div); + case MinusNode minus -> -getValue(minus.in(1)); + case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2)); + case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0; + case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2)); + default -> throw Utils.TODO("Unexpected node " + node); + }; + } + + /** + * Special case of latchPhis when phis can depend on phis of the same region. + */ + private void latchLoopPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + int i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2); + loopPhiCache[i++] = value; + } + } + i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]); + } + } + + /** + * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region. + */ + private void latchPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + cacheValues.put(phi, value); + } + } + } + + /** + * Run the graph until either a return is found or the number of loop iterations are done. + */ + private long evaluate(StartNode start, long parameter, int loops) { + var parameter1 = findProjection(start, 1); + if (parameter1 != null) cacheValues.put(parameter1, parameter); + Node control = findProjection(start, 0); + Node prev = start; + while (control != null) { + Node next; + switch (control) { + case RegionNode region -> { + if (region instanceof LoopNode && region.in(1) != prev) { + if (loops--<=0) throw timeout(); + latchLoopPhis(region, prev); + } else { + latchPhis(region, prev); + } + next = findControl(region); + } + case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1); + case ReturnNode ret -> { + return getValue(ret.in(1)); + } + case ProjNode ignored -> next = findControl(control); + default -> throw Utils.TODO("Unexpected control node " + control); + } + prev = control; + control = next; + } + return 0; + } + + public static long evaluate(Node graph) { + return evaluate(graph, 0); + } + + public static long evaluate(Node graph, long parameter) { + return evaluate(graph, parameter, 1000); + } + + public static long evaluate(Node graph, long parameter, int loops) { + var start = findStart(new BitSet(), graph); + if (start == null) throw timeout(); + var evaluator = new GraphEvaluator(); + return evaluator.evaluate(start, parameter, loops); + } + +} diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java index 41803f24..45332396 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java @@ -13,7 +13,6 @@ import java.util.*; * This is a simple recursive descent parser. All lexical analysis is done here as well. */ public class Parser { - public static boolean LAZY = false; /** * A Global Static, unique to each compilation. This is a public, so we @@ -47,6 +46,8 @@ public class Parser { * List of keywords disallowed as identifiers */ private final HashSet KEYWORDS = new HashSet<>(){{ + add("break"); + add("continue"); add("else"); add("false"); add("if"); @@ -63,10 +64,14 @@ public class Parser { */ public final Stack _xScopes = new Stack<>(); + ScopeNode _continueScope; + ScopeNode _breakScope; + public Parser(String source, TypeInteger arg) { Node.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); + _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); STOP = new StopNode(); } @@ -137,6 +142,8 @@ public class Parser { else if (match ("{" )) return require(parseBlock(),"}"); else if (matchx("if" )) return parseIf(); else if (matchx("while")) return parseWhile(); + else if (matchx("break")) return parseBreak(); + else if (matchx("continue")) return parseContinue(); else if (matchx("#showGraph")) return require(showGraph(),";"); else return parseExpressionStatement(); } @@ -150,65 +157,104 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseWhile() { + + var savedContinueScope = _continueScope; + var savedBreakScope = _breakScope; + 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. + // associated phis; see {@code inProgress()}. - ctrl(new LoopNode(ctrl(),null).peephole()); // Note we set back edge to null here + 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 = _xScopes.push(_scope).keep(); + ScopeNode head = _scope.keep(); // Clone the head Scope to create a new Scope for the body. // Create phis eagerly as part of cloning - _scope = _scope.dup(true); // The true argument triggers creating phis + _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(); + 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); + // Clone the body Scope to create the break/exit Scope which accounts for any + // side effects in the predicate. The break/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. + ctrl(ifF); + _xScopes.push(_breakScope = _scope.dup()); + // No continues yet + _continueScope = null; + // 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. + // Merge the loop bottom into other continue statements + if (_continueScope != null) { + _continueScope = jumpTo(_continueScope); + _scope.kill(); + _scope = _continueScope; + } + + // The true branch loops back, so whatever is current _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. + var exit = _breakScope; head.endLoop(_scope, exit); head.unkeep().kill(); _xScopes.pop(); // Cleanup _xScopes.pop(); // Cleanup + _continueScope = savedContinueScope; + _breakScope = savedBreakScope; + // At exit the false control is the current control, and // the scope is the exit scope after the exit test. - return (_scope = exit); + return _scope = exit; } + private ScopeNode jumpTo(ScopeNode toScope) { + ScopeNode cur = _scope.dup(); + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill current scope + // Prune nested lexical scopes that have depth > than the loop head + // We use _breakScope as a proxy for the loop head scope to obtain the depth + while( cur._scopes.size() > _breakScope._scopes.size() ) + cur.pop(); + // If this is a continue then first time the target is null + // So we just use the pruned current scope as the base for the + // continue + if (toScope == null) + return cur; + // toScope is either the break scope, or a scope that was created here + assert toScope._scopes.size() <= _breakScope._scopes.size(); + toScope.mergeScopes(cur); + return toScope; + } + + private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); } + + private Node parseBreak () { checkLoopActive(); return ( _breakScope = require(jumpTo( _breakScope ),";")); } + private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); } + /** * Parses a statement * @@ -339,10 +385,10 @@ public class Parser { var lhs = parseAddition(); if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); - if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); - if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); + if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); return lhs; } @@ -439,7 +485,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); } @@ -448,7 +494,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/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java index eaf19199..0ed32464 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -6,7 +6,7 @@ import java.util.BitSet; public class LoopNode extends RegionNode { - public LoopNode( Node entry, Node back) { super(null,entry,back); } + public LoopNode( Node entry ) { super(null,entry,null); } Node entry() { return in(1); } Node back () { return in(2); } @@ -14,22 +14,10 @@ public class LoopNode extends RegionNode { @Override public String label() { return "Loop"; } - @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append("Loop").append(_nid); - } - - @Override - public Type compute() { - return inProgress() ? Type.CONTROL : super.compute(); - } - @Override public Node idealize() { return inProgress() ? null : super.idealize(); } - @Override Node idom() { return entry(); } - - @Override public boolean inProgress() { return back()==null; } + @Override Node idom() { return entry(); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java index 4cd1b3d2..52d4c1e4 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java @@ -153,8 +153,6 @@ public abstract class Node { public int nIns() { return _inputs.size(); } - public Node out(int i) { return _outputs.get(i); } - public int nOuts() { return _outputs.size(); } public boolean isUnused() { return nOuts() == 0; } @@ -229,11 +227,11 @@ public abstract class Node { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { Utils.del(_outputs, Utils.find(_outputs, use)); - return _outputs.size() == 0; + return _outputs.isEmpty(); } // Shortcut for "popping" n nodes. A "pop" is basically a - // set_def(last,null) followed by lowering the nIns() count. + // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { for( int i=0; i(syms)); dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i 4 ) + break; +} +return arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return arg;", stop.toString()); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + @Test + public void testChapter8BreakOutsideLoop() { + try { + new Parser(""" +if(arg <= 10) { + break; + arg = arg + 1; +} +return arg; +""").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("No active loop for a break or continue",e.getMessage()); + } + } + + @Test + public void testChapter8Regress3() { + Parser parser = new Parser(""" +while(arg < 10) { + break; +} +return arg; +"""); + StopNode stop = parser.parse(true); + assertEquals("return arg;", stop.toString()); + } + + @Test + public void testChapter8Regress4() { + Parser parser = new Parser(""" +int a = 1; +while(arg < 10) { + a = a + 1; + if (arg > 2) { + int a = 17; + break; + } +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testChapter8Regress5() { + Parser parser = new Parser(""" +int a = 1; +while(1) { + a = a + 1; + if (a<10) continue; + break; +} +return a; +"""); + StopNode stop = parser.parse(true); + assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + @Test public void testChapter7Example() { Parser parser = new Parser( @@ -39,7 +231,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } @Test @@ -60,7 +252,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,0,Phi(Loop21,Phi_sum,(Phi(Loop,0,(Phi_j+1))+Phi_sum)));", stop.toString()); + assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); System.out.println(IRPrinter.prettyPrint(stop,99)); } @@ -78,7 +270,7 @@ return b; """); Node._disablePeephole = true; StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,Phi(Region27,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop8,2,Phi(Region26,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); Node._disablePeephole = false; System.out.println(IRPrinter.prettyPrint(stop,99)); @@ -99,7 +291,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(true); - assertEquals("return Phi(Loop8,2,(Phi(Region27,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); System.out.println(IRPrinter.prettyPrint(stop,99)); } @@ -674,7 +866,18 @@ return a;"""); assertEquals("Undefined name 'b'",e.getMessage()); } } + + @Test + public void testChapter5Regress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + @Test public void testChapter5BadNum() { try { @@ -957,7 +1160,7 @@ return a;"""); parser.parse(); StartNode start = Parser.START; for( Node use : start._outputs ) - if( use instanceof ConstantNode con ) + if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) assertEquals(TypeInteger.constant(0),con._type); } -- cgit v1.2.3