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 <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>

1 files changed, 208 insertions, 5 deletions

diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 6baa8215..16f7e324 100644
--- a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
 import org.junit.Test;
 
 import static org.junit.Assert.*;
@@ -9,6 +10,197 @@ import static org.junit.Assert.*;
 public class Chapter08Test {
 
     @Test
+    public void testChapter8Ex6() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        break;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+        Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1));
+        Assert.assertEquals(10, GraphEvaluator.evaluate(stop, 6));
+    }
+
+
+    @Test
+    public void testChapter8Ex5() {
+        Parser parser = new Parser(
+                """
+int a = 1;
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 7)
+        continue;
+    a = a + 1;
+}
+return a;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+        System.out.println(IRPrinter.prettyPrint(stop,99));
+    }
+
+
+    @Test
+    public void testChapter8Ex4() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+    @Test
+    public void testChapter8Ex3() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+
+    @Test
+    public void testChapter8Ex2() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 6)
+        continue;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+
+    @Test
+    public void testChapter8Ex1() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testChapter8Regress1() {
+        Parser parser = new Parser(
+                """
+while( arg < 10 ) {
+    int a = arg+2;
+    if( a > 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);
     }