Chapter 9 (#66)

* chapter9

* merge fixes to chapter8

* Ch 9 notes

* Ch 9 work

Add a Iterate phase, after parsing.
Add a Worklist with fast dup removal & rand pull.
Add a Node.iter() call which returns progress or null.  Peephole calls it.  Iter() also asserts that Types make monotonic progress.
Intern all types, so we can do a cheap/easy "isa" test.

* GVN

* rename temporarily

* Apply Cliff's worklist changes

* Apply Cliff's GVN changes

* Revert "GVN"

This reverts commit 9dc6db1cac7e40de4a58333cbc3c9c3e7c088e6f.

* Revert "Ch 9 work"

This reverts commit df5b74e6c017a4f237a5d1a550a83b40a7928876.

* Fix 3-1+2

Was computing as 3-(1+2) == 0, not 4 as expected.
Add tests.
Unlock in swap12.

* Missed some cut-n-paste changes

* Break up the test file per-chapter

* Fix keep-alive while looping expressions

Must "hook" LHS prior to calling peepholes

* Ch9 Region optimization

Bug fix, GVN hits 2 inProgress Loops
Bug fix lifetime tracking when parsing dead code
Bug fix debug find call
GraphViz post-iterate

* Readme overhaul

Progress on Ch 9 readme

* Fix bugs hashcode

Was relying on label() hashCode for Phi, Proj; since this is debug-only cannot be relied on.  Proj relies on _idx field, Phi needs a !inProgress check.

* Constant nodes print "#" before con

* Add a farther neighbor check

Peeps that check more than the nearest neighbor register a dependency on the Node that failed them.  Should that Node later change, the peep root is put back on the worklist and revisited.

* Fix addDeps assert

Unwind golden test print, print smarter.
Unlock edges in subsume

* Update README

* shuffle adddeps forward one

its needed again shortly in another test, so just cover it now

* Fix fuzzer bugs

Peep x+(-y) to x-y
Handle TOP inputs; didn't think it could happen before running an optimistic pass, but fuzzer proved me wrong.
Deleting an input can recursively delete the self-node.
When checking the compute() type assert, delay setting _type so the method can just be re-run in the debugger.
Missing addDep in Phi
Parser mis-handling stacked operators like "1+-2" or "1==!=<=<>=>2"
Make Work list deterministic between tests.

* Update fuzzer to run iterate (#62)

* Update fuzzer to run iterate

* Work seed is now reset by reset

* A few more fuzzer tests

Set _type in iter() even later, better debugging.
Handle dead active scopes in visiualizer.
Region ideal honors Loop invariants; finish Region ideal for single input; inProgress check is a little tighter.
Type.isConstant is true strictly for lattice centerline constants.  Clean up TypeInteger.
ideaj warning removal

* Fix all fuzzer bugs

iter() does not call peep(), instead peep() is self-recursive.  This allows Iterate() to call iter(), and not get into arbitrary recursive peep() changes that do not track on the worklist.
Div, Minus, If all monotonic.
Catch a bunch of progress issues.
Robustify IRPrinter and Iterate and Region ideal

* Reducer could run into an infinite loop (#63)

* Write up how the Evaluator works (#64)

* Write up how the Evaluator works

* Some small improvements and a slightly better wrap up.

* Series of fuzzer bugs.

Fix monotonicity for all data nodes.
Generic compute intercept for data nodes, check all inputs for TOP/BOTTOM, and again for IntDataNodes.
Fix general progress bug allow high Types as constants.
Fix progress Region 1-input has obvious idom.
Make shortcut for fuzzer; renames Fuzzer to not have "Test" in the class name.
Fix invert comment in TypeInteger

* All fuzzer tests pass

Turn off expensive assert accidentally turned on
CSE needs to join types.
Add a type join.
Missing dep in Phi

* More README

* Hacking alternative way to fix the type compute

* Node is no longer IntSupplier
Renamed Work to WorkList
Renamed Iterate to IterOptim
Renamed Node.iter() to Node.peepholeOpt()
WorkList expects elements to be of Node

* Add an example of GVN

* Rename the method depsClear to moveDepsToWorklist - to better capture what it actually does.

* Add a second example of GVN benefits

* Fix typo

* Add example of worklist opt

* Prepare to allow alternative post parse worklist opt

* Alternative WorkList opt that has following differences:
1. It does not require dependencies between nodes
2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step.
3. It is simple

* Alternative WorkList opt that has following differences:
1. It does not require dependencies between nodes
2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step.
3. It is simple

* The RPO list was incomplete as it only identified the subgraph accessible from the STOP node.

* Fix iter count

* Add test suggested by Xmilia

* Fix bug where after the region is peeped the phis get consistent number of inputs

* Fix bug where after the region is peeped the phis get consistent number of inputs

* Dump out stats on how many nodes we peepd during the post parse iterative opt.

* Make it easy to switch the IterOpt

* Use deps based worklist by default

* Sharper worklist add

* Copy across Cliff's changes

* Merge changes to Iterate

* Revert failing change

* Update readme

* Add comments / update docs to explain the patterns where we call addDep().

* As before, unconditionally made dep a dependent of region.

* Fix a lot of missing dep issues

Rename IterOptim -> IterPeeps
Some grammar changes in comments & readme

* Bump up fuzzer limits, more testing

Missing dep in idom calc in IfNode.
Missed idom cache clear on Region edit.

* Remove RPO based peeps

O(n^2) behavior

* Minor updates README

* fix compile bug

---------

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>

14 files changed, 2568 insertions, 0 deletions

diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java
new file mode 100644
index 00000000..48cc716f
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java
@@ -0,0 +1,50 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter01Test {
+
+    @Test
+    public void testSimpleProgram() {
+        Parser parser = new Parser("return 1;");
+        StopNode stop = parser.parse();
+        StartNode start = Parser.START;
+        ReturnNode ret = (ReturnNode)stop.in(0);
+        
+        assertTrue(ret.ctrl() instanceof ProjNode);
+        Node expr = ret.expr();
+        if( expr instanceof ConstantNode con ) {
+            assertEquals(start,con.in(0));
+            assertEquals(TypeInteger.constant(1), con._type);
+        } else {
+            fail();
+        }
+    }
+
+    @Test
+    public void testZero() {
+        Parser parser = new Parser("return 0;");
+        parser.parse();
+        StartNode start = Parser.START;
+        for( Node use : start._outputs )
+            if( use instanceof ConstantNode con && con._type instanceof TypeInteger )
+                assertEquals(TypeInteger.constant(0),con._type);
+    }
+
+
+    @Test
+    public void testBad2() {
+        try { 
+            new Parser("return 0123;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage());
+        }
+    }
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java
new file mode 100644
index 00000000..5efd33e7
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java
@@ -0,0 +1,99 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter02Test {
+    
+    @Test
+    public void testParseGrammar() {
+        Parser parser = new Parser("return 1+2*3+-5;");
+        Node._disablePeephole = true; // disable peephole so we can observe full graph
+        StopNode ret = parser.parse();
+        assertEquals("return ((1+(2*3))+(-5));", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(parser));
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testAddPeephole() {
+        Parser parser = new Parser("return 1+2;");
+        StopNode ret = parser.parse();
+        assertEquals("return 3;", ret.print());
+    }
+
+    @Test
+    public void testSubPeephole() {
+        Parser parser = new Parser("return 1-2;");
+        StopNode ret = parser.parse();
+        assertEquals("return -1;", ret.print());
+    }
+
+    @Test
+    public void testMulPeephole() {
+        Parser parser = new Parser("return 2*3;");
+        StopNode ret = parser.parse();
+        assertEquals("return 6;", ret.print());
+    }
+
+    @Test
+    public void testDivPeephole() {
+        Parser parser = new Parser("return 6/3;");
+        StopNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+    }
+
+    @Test
+    public void testMinusPeephole() {
+        Parser parser = new Parser("return 6/-3;");
+        StopNode ret = parser.parse();
+        assertEquals("return -2;", ret.print());
+    }
+
+    @Test
+    public void testExample() {
+        Parser parser = new Parser("return 1+2*3+-5;");
+        StopNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+        GraphVisualizer gv = new GraphVisualizer();
+        System.out.println(gv.generateDotOutput(parser));
+    }
+    
+    @Test
+    public void testBad1() {
+        try { 
+            new Parser("ret").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected =: ",e.getMessage());
+        }
+    }
+    @Test
+    public void testNotBad3() {
+        // this test used to fail in chapter 1
+        assertEquals("return 12;", new Parser("return --12;").parse().print());
+    }
+
+    @Test
+    public void testBad4() {
+        try { 
+            new Parser("return 100").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected ;: ",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testNotBad5() {
+        // this test used to fail in chapter 1
+        assertEquals("return -100;", new Parser("return -100;").parse().print());
+    }
+
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java
new file mode 100644
index 00000000..8a11107d
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -0,0 +1,70 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter03Test {
+    
+    @Test
+    public void testVarDecl() {
+        Parser parser = new Parser("int a=1; return a;");
+        StopNode ret = parser.parse();
+        assertEquals("return 1;", ret.print());
+    }
+
+    @Test
+    public void testVarAdd() {
+        Parser parser = new Parser("int a=1; int b=2; return a+b;");
+        StopNode ret = parser.parse();
+        assertEquals("return 3;", ret.print());
+    }
+
+    @Test
+    public void testVarScope() {
+        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;");
+        StopNode ret = parser.parse();
+        assertEquals("return 4;", ret.print());
+    }
+
+    @Test
+    public void testVarScopeNoPeephole() {
+        Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
+        Node._disablePeephole = true;
+        StopNode ret = parser.parse();
+        Node._disablePeephole = false;
+        assertEquals("return (1+3);", ret.print());
+    }
+
+    @Test
+    public void testVarDist() {
+        Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return 8;", ret.print());
+    }
+
+    @Test
+    public void testSelfAssign() {
+        try { 
+            new Parser("int a=a; return a;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Undefined name 'a'",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testBad6() {
+        try {
+            new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected }: ",e.getMessage());
+        }
+    }
+
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java
new file mode 100644
index 00000000..ffbbe9a8
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java
@@ -0,0 +1,130 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter04Test {
+    
+    @Test
+    public void testPeephole() {
+        Parser parser = new Parser("return 1+arg+2; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
+    }
+
+    @Test
+    public void testPeephole2() {
+        Parser parser = new Parser("return (1+arg)+2;");
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
+    }
+
+    @Test
+    public void testAdd0() {
+        Parser parser = new Parser("return 0+arg;");
+        StopNode ret = parser.parse();
+        assertEquals("return arg;", ret.print());
+    }
+
+    @Test
+    public void testAddAddMul() {
+        Parser parser = new Parser("return arg+0+arg;");
+        StopNode ret = parser.parse();
+        assertEquals("return (arg*2);", ret.print());
+    }
+  
+    @Test
+    public void testPeephole3() {
+        Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return ((arg*2)+6);", ret.print());
+    }
+
+    @Test
+    public void testMul1() {
+        Parser parser = new Parser("return 1*arg;");
+        StopNode ret = parser.parse();
+        assertEquals("return arg;", ret.print());
+    }
+  
+    @Test
+    public void testVarArg() {
+        Parser parser = new Parser("return arg; #showGraph;");
+        StopNode stop = parser.parse();
+        ReturnNode ret = stop.ret();
+        assertTrue(ret.in(0) instanceof ProjNode);
+        assertTrue(ret.in(1) instanceof ProjNode);
+    }
+
+    @Test
+    public void testConstantArg() {
+        Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2));
+        StopNode ret = parser.parse();
+        assertEquals("return 2;", ret.print());
+    }
+
+    @Test
+    public void testCompEq() {
+        Parser parser = new Parser("return 3==3; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return 1;", ret.print());
+    }
+
+    @Test
+    public void testCompEq2() {
+        Parser parser = new Parser("return 3==4; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return 0;", ret.print());
+    }
+
+    @Test
+    public void testCompNEq() {
+        Parser parser = new Parser("return 3!=3; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return 0;", ret.print());
+    }
+
+    @Test
+    public void testCompNEq2() {
+        Parser parser = new Parser("return 3!=4; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return 1;", ret.print());
+    }
+
+    @Test
+    public void testBug1() {
+        Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
+    }
+
+    @Test
+    public void testBug2() {
+        Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;");
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+1);", ret.print());
+    }
+
+    @Test
+    public void testBug3() {
+        try { 
+            new Parser("inta=1; return a;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Undefined name 'inta'",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testBug4() {
+        Parser parser = new Parser("return -arg;");
+        StopNode ret = parser.parse();
+        assertEquals("return (-arg);", ret.print());
+    }
+    
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java
new file mode 100644
index 00000000..6bdc0ef6
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -0,0 +1,225 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter05Test {
+    
+    @Test
+    public void testIfStmt() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+if (arg == 1)
+    a = arg+2;
+else {
+    a = arg-3;
+    #showGraph;
+}
+#showGraph;
+return a;""");
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
+    }
+  
+    @Test
+    public void testTest() {
+        Parser parser = new Parser(
+"""
+int c = 3;
+int b = 2;
+if (arg == 1) {
+    b = 3;
+    c = 4;
+}
+return c;""", TypeInteger.BOT);
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return Phi(Region16,4,3);", ret.toString());
+    }
+    
+    @Test
+    public void testReturn2() {
+        Parser parser = new Parser(
+"""
+if( arg==1 ) 
+    return 3; 
+else 
+    return 4; 
+#showGraph;""", TypeInteger.BOT);
+        StopNode stop = parser.parse();
+        assertEquals("Stop[ return 3; return 4; ]", stop.toString());
+    }
+    
+    @Test
+    public void testIfMergeB() {
+        Parser parser = new Parser(
+"""
+int a=arg+1;
+int b=0;
+if( arg==1 )
+    b=a;
+else
+    b=a+1;
+return a+b;""");
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString());
+    }
+
+    @Test
+    public void testIfMerge2() {
+        Parser parser = new Parser(
+"""
+int a=arg+1;
+int b=arg+2;
+if( arg==1 )
+    b=b+a;
+else
+    a=b+1;
+return a+b;""");
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString());
+    }
+
+    @Test
+    public void testMerge3() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+#showGraph;""", TypeInteger.BOT);
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString());
+    }
+
+    @Test
+    public void testMerge4() {
+        Parser parser = new Parser(
+"""
+int a=0;
+int b=0;
+if( arg )
+    a=1;
+if( arg==0 )
+    b=2;
+return arg+a+b;
+#showGraph;""", TypeInteger.BOT);
+        StopNode stop = parser.parse();
+        assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString());
+    }
+
+    @Test
+    public void testMerge5() {
+        Parser parser = new Parser(
+"""
+int a=arg==2;
+if( arg==1 )
+{
+    a=arg==3;
+}
+return a;""");
+        StopNode ret = parser.parse().iterate();
+        assertEquals("return (arg==Phi(Region16,3,2));", ret.toString());
+    }
+
+    @Test
+    public void testTrue() {
+      StopNode stop = new Parser("return true;").parse();
+      assertEquals("return 1;",stop.toString());
+    }
+    
+    @Test
+    public void testHalfDef() {
+        try { 
+            new Parser("if( arg==1 ) int b=2; return b;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Cannot define a new name on one arm of an if",e.getMessage());
+        }
+    }
+    
+    @Test
+    public void testHalfDef2() {
+        try { 
+            new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Undefined name 'b'",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testRegress1() {
+        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 testBadNum() {
+        try { 
+            new Parser("return 1-;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage());
+        }
+    }
+      
+    @Test
+    public void testKeyword1() {
+        try { 
+            new Parser("int true=0; return true;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Expected an identifier, found 'true'",e.getMessage());
+        }
+    }
+      
+    @Test
+    public void testKeyword2() {
+        try { 
+            new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Expected an identifier, found 'else'",e.getMessage());
+        }
+    }
+
+    @Test
+        public void testKeyword3() {
+        try { 
+            new Parser("int a=1; ififif(arg)inta=2;return a;").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, expected =: (",e.getMessage());
+        }
+    }
+
+    @Test
+    public void testBad7() {
+        try {
+            new Parser("return 1;}").parse();
+            fail();
+        } catch( RuntimeException e ) {
+            assertEquals("Syntax error, unexpected }",e.getMessage());
+        }
+    }
+
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java
new file mode 100644
index 00000000..ba0ea9f6
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -0,0 +1,296 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter06Test {
+
+    @Test
+    public void testPeepholeReturn() {
+        Parser parser = new Parser(
+"""
+if( true ) return 2;
+return 1;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 2;", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testPeepholeRotate() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+if (arg)
+    a = 2;
+return (arg < a) < 3;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString());
+    }
+
+    @Test
+    public void testPeepholeCFG() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( true )
+  a=2;
+else
+  a=3;
+return a;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 2;", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testIfIf() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg!=1 )
+    a=2;
+else
+    a=3;
+int b=4;
+if( a==2 )
+    b=42;
+else
+    b=5;
+return b;""", TypeInteger.BOT);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Region32,42,5);", stop.toString());
+    }
+
+    @Test
+    public void testIfArgIf() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( 1==1 )
+    a=2;
+else
+    a=3;
+int b=4;
+if( arg==2 )
+    b=a;
+else
+    b=5;
+return b;""", TypeInteger.BOT);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Region29,2,5);", stop.toString());
+    }
+
+    @Test
+    public void testMerge3With2() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+#showGraph;""", TypeInteger.constant(2));
+        StopNode stop = parser.parse();
+        assertEquals("return 5;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3With1() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( arg==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(1));
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 3;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.BOT);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Region37,3,Phi(Region35,4,5));", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole1() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(1));
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 3;", stop.toString());
+    }
+
+    @Test
+    public void testMerge3Peephole3() {
+        Parser parser = new Parser(
+"""
+int a=1;
+if( arg==1 )
+    if( 1==2 )
+        a=2;
+    else
+        a=3;
+else if( arg==3 )
+    a=4;
+else
+    a=5;
+return a;
+""", TypeInteger.constant(3));
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 4;", stop.toString());
+    }
+
+    @Test
+    public void testDemo1NonConst() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""");
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return Phi(Region24,4,1);", ret.toString());
+    }
+
+
+    @Test
+    public void testDemo1True() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""", TypeInteger.constant(1));
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return 4;", ret.toString());
+    }
+
+    @Test
+    public void testDemo1False() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+if( arg ) {
+    a = 2;
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b;
+""", TypeInteger.constant(0));
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return 1;", ret.toString());
+    }
+
+    @Test
+    public void testDemo2NonConst() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""");
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return (Phi(Region35,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString());
+    }
+
+
+    @Test
+    public void testDemo2True() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""", TypeInteger.constant(1));
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return 6;", ret.toString());
+    }
+
+    @Test
+    public void testDemo2arg2() {
+        Parser parser = new Parser("""
+int a = 0;
+int b = 1;
+int c = 0;
+if( arg ) {
+    a = 1;
+    if( arg==2 ) { c=2; } else { c=3; }
+    if( arg ) { b = 2; }
+    else b = 3;
+}
+return a+b+c;
+""", TypeInteger.constant(2));
+        StopNode ret = parser.parse().iterate(true);
+        assertEquals("return 5;", ret.toString());
+    }
+    
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java
new file mode 100644
index 00000000..48876598
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -0,0 +1,245 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter07Test {
+
+        
+    @Test
+    public void testExample() {
+        Parser parser = new Parser(
+                """
+                while(arg < 10) {
+                    arg = arg + 1;
+                    #showGraph;
+                }
+                return arg;
+                """);
+        Node._disablePeephole = true;
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testRegression() {
+        Parser parser = new Parser(
+
+"""
+int a = 1;
+if(arg){}else{
+    while(a < 10) {
+        a = a + 1;
+    }
+}
+return a;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString());
+    }
+  
+    @Test
+    public void testWhileNested() {
+        Parser parser = new Parser(
+
+"""
+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;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        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));
+    }
+
+    @Test
+    public void testWhileScope() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+int b = 2;
+while(a < 10) {
+    if (a == 2) a = 3;
+    else b = 4;
+}
+return b;
+""");
+        Node._disablePeephole = true;
+        StopNode stop = parser.parse(true);
+        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));
+    }
+
+    @Test
+    public void testWhileNestedIfAndInc() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+int b = 2;
+while(a < 10) {
+    if (a == 2) a = 3;
+    else b = 4;
+    b = b + 1;
+    a = a + 1;
+}
+return b;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        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));
+    }
+
+
+    @Test
+    public void testWhile() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+while(a < 10) {
+    a = a + 1;
+    a = a + 2;
+}
+return a;
+""");
+        Node._disablePeephole = true;
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testWhilePeep() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+while(a < 10) {
+    a = a + 1;
+    a = a + 2;
+}
+return a;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testWhile2() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+while(arg) a = 2;
+return a;
+""");
+        Node._disablePeephole = true;
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop7,1,2);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+        Node._disablePeephole = false;
+        System.out.println(IRPrinter.prettyPrint(stop,99));
+    }
+
+    @Test
+    public void testWhile2Peep() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+while(arg) a = 2;
+return a;
+""");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop7,1,2);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+        System.out.println(IRPrinter.prettyPrint(stop, 99));
+    }
+
+    @Test
+    public void testWhile3() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+while(a < 10) {
+    int b = a + 1;
+    a = b + 2;
+}
+return a;
+""");
+        Node._disablePeephole = true;
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop7,1,((Phi_a+1)+2));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testWhile3Peep() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+while(a < 10) {
+    int b = a + 1;
+    a = b + 2;
+}
+return a;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testWhile4() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+int b = 2;
+while(a < 10) {
+    int b = a + 1;
+    a = b + 2;
+}
+return a;
+""");
+        Node._disablePeephole = true;
+        StopNode stop = parser.parse(true);
+        assertEquals("return Phi(Loop8,1,((Phi_a+1)+2));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+        Node._disablePeephole = false;
+    }
+
+    @Test
+    public void testWhile4Peep() {
+        Parser parser = new Parser(
+"""
+int a = 1;
+int b = 2;
+while(a < 10) {
+    int b = a + 1;
+    a = b + 2;
+}
+return a;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+}
+        
\ No newline at end of file
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java
new file mode 100644
index 00000000..18371494
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -0,0 +1,211 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter08Test {
+
+    @Test
+    public void testEx6() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        break;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate(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 testEx5() {
+        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().iterate(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 testEx4() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+    @Test
+    public void testEx3() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 6)
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+    }
+
+
+    @Test
+    public void testEx2() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+    if (arg == 6)
+        continue;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+
+    @Test
+    public void testEx1() {
+        Parser parser = new Parser(
+                """
+while(arg < 10) {
+    arg = arg + 1;
+    if (arg == 5)
+        continue;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode);
+    }
+
+    @Test
+    public void testRegress1() {
+        Parser parser = new Parser(
+                """
+while( arg < 10 ) {
+    int a = arg+2;
+    if( a > 4 )
+        break;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return arg;", stop.toString());
+        System.out.println(IRPrinter.prettyPrint(stop,99));
+    }
+
+    @Test
+    public void testRegress2() {
+        Parser parser = new Parser("if(1) return 0;  else while(arg>--arg) arg=arg+1; return 0;");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 0;", stop.toString());
+    }
+    
+    @Test
+    public void testBreakOutsideLoop() {
+        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 testRegress3() {
+        Parser parser = new Parser("""
+while(arg < 10) {
+    break;
+}
+return arg;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return arg;", stop.toString());
+    }
+        
+    @Test
+    public void testRegress4() {
+        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().iterate(true);
+        assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof RegionNode);                   
+    }
+        
+    @Test
+    public void testRegress5() {
+        Parser parser = new Parser("""
+int a = 1;
+while(1) {
+    a = a + 1;
+    if (a<10) continue;
+    break;
+}
+return a;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString());
+        assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 );
+    }
+
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter09Test.java
new file mode 100644
index 00000000..8e198218
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter09Test.java
@@ -0,0 +1,300 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+import org.junit.Assert;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.junit.Ignore;
+
+import static org.junit.Assert.*;
+
+public class Chapter09Test {
+
+    @Test
+    @Ignore
+    public void testJig() {
+        Parser parser = new Parser("""
+int v0=0;
+arg=0;
+while(v0) {
+        while(1) if(arg*arg*0==0) {}
+                while(0) {}
+    arg=1;
+}
+return 0;
+                """);
+        StopNode stop = parser.parse().iterate(true);
+    }
+
+    @Test
+    public void testGVN1() {
+        Parser parser = new Parser(
+                """
+int x = arg + arg;
+if(arg < 10) {
+    return arg + arg;
+}
+else {
+    x = x + 1;
+}
+return x;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString());
+        Assert.assertEquals(2, GraphEvaluator.evaluate(stop, 1));
+        Assert.assertEquals(23, GraphEvaluator.evaluate(stop, 11));
+    }
+
+    @Test
+    public void testGVN2() {
+        Parser parser = new Parser(
+                """
+return arg*arg-arg*arg;
+                """);
+        StopNode stop = parser.parse(true);
+        assertEquals("return 0;", stop.toString());
+        Assert.assertEquals(0, GraphEvaluator.evaluate(stop, 1));
+    }
+
+    @Test
+    public void testWorklist1() {
+        Parser parser = new Parser(
+                """
+int step = 1;
+while (arg < 10) {
+    arg = arg + step + 1;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse(true).iterate(true);
+        assertEquals("return Phi(Loop7,arg,(Phi_arg+2));", stop.toString());
+        Assert.assertEquals(11, GraphEvaluator.evaluate(stop, 1));
+    }
+
+    @Test
+    public void testWorklist2() {
+        Parser parser = new Parser(
+                """
+int cond = 0;
+int one = 1;
+while (arg < 10) {
+    if (cond) one = 2;
+    arg = arg + one*3 + 1;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse(true).iterate(true);
+        assertEquals("return Phi(Loop8,arg,(Phi_arg+4));", stop.toString());
+        Assert.assertEquals(13, GraphEvaluator.evaluate(stop, 1));
+    }
+
+    @Test
+    public void testWorklist3() {
+        Parser parser = new Parser(
+                """
+int v1 = 0;
+int v2 = 0;
+int v3 = 0;
+int v4 = 0;
+int v5 = 0;
+int v6 = 0;
+int v7 = 0;
+int v8 = 0;
+while (arg) {
+    if (v1) v2 = 1;
+    if (v2) v3 = 1;
+    if (v3) v4 = 1;
+    if (v4) v5 = 1;
+    if (v5) v6 = 1;
+    if (v6) v7 = 1;
+    if (v7) v8 = 1;
+    arg = arg + v8 + 1;
+}
+return arg;
+                """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop14,arg,(Phi_arg+1));", stop.toString());
+    }
+
+    @Test
+    public void testRegionPeepBug() {
+        Parser parser = new Parser(
+                """
+int v0=0;
+int v1=0;
+while(v1+arg) {
+    arg=0;
+    int v2=v0;
+    while(arg+1) {}
+    v0=1;
+    v1=v2;
+}
+                """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testWhile0() {
+        Parser parser = new Parser("while(0) continue; if(0) arg=0;");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testWhile1() {
+        Parser parser = new Parser("""
+if(0) while(0) {
+    int arg=arg;
+    while(0) {}
+}                                   
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+
+    @Test
+    public void testPrecedence() {
+        Parser parser = new Parser("return 3-1+2;");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 4;", stop.toString());
+    }
+
+    @Test
+    public void testSwap2() {
+        Parser parser = new Parser("return 1+(1+1);");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 3;", stop.toString());
+    }
+
+    
+    @Test
+    public void testFuzz0() {
+        Parser parser = new Parser("""
+int one = 1;
+int a = 0;
+int zero = 0;
+while(arg) {
+    a = -(one + a + 2);
+    arg = arg + 1;
+    one = one + zero;
+}
+return a;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop9,0,(-(Phi_a+3)));", stop.toString());
+    }
+
+    @Test
+    public void testFuzz1() {
+        Parser parser = new Parser("""
+while(1) {}
+while(arg) break;
+while(arg) arg=0;
+arg=0;
+int v0=0!=0<-0;
+return -0+0+0;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+
+    @Test
+    public void testFuzz2() {
+        Parser parser = new Parser("return 0+-0;");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return 0;", stop.toString());
+    }
+        
+    @Test
+    public void testFuzz3() {
+        Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz4() {
+        Parser parser = new Parser("""
+while(1) {
+    arg=0<=0;
+    if(1<0) while(arg==-0) arg=arg-arg;
+}
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz5() {
+        Parser parser = new Parser("""
+{
+    int v0=0;
+    while(1)
+            int v1=0--0;
+    while(v0)
+        break;
+    while(-v0) {
+        while(0+0+v0) continue;
+        break;
+    }
+    if(-0!=-0+0+v0) while(0+0+0+0)
+                break;
+}
+return 0!=0;
+""");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz6() {
+        Parser parser = new Parser("""
+int v0=0;
+while(0==1) while(v0)
+        v0=1+v0;
+                                   """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz7() {
+        Parser parser = new Parser("""
+while(1) {}
+int v0=0;
+while(v0)
+    {}
+int v1=0;
+while(1)
+        v1=1;
+return v1+v0;
+                                   """);
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz8() {
+        Parser parser = new Parser("while(arg) arg = arg - 1; #showGraph; return arg;");
+        StopNode stop = parser.parse().iterate(true);
+        assertEquals("return Phi(Loop6,arg,(Phi_arg-1));", stop.toString());
+    }
+
+    @Test
+    public void testMeet() {
+        Type t1 = Type.TOP;
+        Type t2 = TypeInteger.TOP;
+        Assert.assertEquals(TypeInteger.TOP, t1.meet(t2));
+        Assert.assertEquals(TypeInteger.TOP, t2.meet(t1));
+        t1 = Type.BOTTOM;
+        t2 = TypeInteger.BOT;
+        Assert.assertEquals(Type.BOTTOM, t1.meet(t2));
+        Assert.assertEquals(Type.BOTTOM, t2.meet(t1));
+    }
+
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter09/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
new file mode 100644
index 00000000..efd76481
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
@@ -0,0 +1,34 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.fuzzer.Fuzzer;
+import org.junit.Test;
+import org.junit.Ignore;
+
+
+import static org.junit.Assert.assertTrue;
+
+/**
+ * To use the fuzzer run the <code>fuzzPeeps</code> methods.
+ * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line
+ * via <code>mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps</code>
+ */
+public class FuzzerWrap {
+
+    @Test
+    public void fuzzPeeps() {
+        var fuzzer = new Fuzzer();
+        for (int i=0; i<1000000; i++)
+            fuzzer.fuzzPeeps(i);
+        assertTrue(fuzzer.noExceptions());
+    }
+
+
+    @Test
+    @Ignore
+    public void fuzzPeepTiming() {
+        var fuzzer = new Fuzzer();
+        int max_nid=0;
+        for (int i=0; i<1000000; i++)
+            max_nid = fuzzer.fuzzPeepTiming(i, max_nid);
+    }
+}
diff --git a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
new file mode 100644
index 00000000..90817d2b
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
@@ -0,0 +1,170 @@
+package com.seaofnodes.simple.fuzzer;

+

+import com.seaofnodes.simple.GraphEvaluator;

+import com.seaofnodes.simple.Parser;

+import com.seaofnodes.simple.node.Node;

+import com.seaofnodes.simple.node.StopNode;

+

+import java.util.ArrayList;

+import java.util.Random;

+import java.util.function.Consumer;

+

+/**

+ * Implementation of the fuzzer.

+ * Random testcases are generated using the ScriptGenerator.

+ * This will generate a script similar to how the parser parses it but instead of parsing it will

+ * randomly choose a variation the parser would parse and generate it.

+ * These scripts are the parsed by the parser and all exceptions are caught and filtered

+ * to only show one occurrence of one problem. This includes script which generate different

+ * results when the compiled graph with and without peeps is executed.

+ * To aid debugging scripts that cause errors are then reduced by applying rules and checking

+ * that the same issue persists.

+ */

+public class Fuzzer {

+

+    private static final int EVAL_TIMEOUT = 1000;

+

+    /**

+     * List of exceptions already encountered.

+     * This is used to filter new exceptions and discard them if they are already found.

+     */

+    private final ArrayList<Throwable> exceptions = new ArrayList<>();

+

+    /**

+     * Filter and record an exception in a script.

+     * @param e The exception caused by the script

+     * @param script The script causing the exception

+     * @param reproducer Reproducer which should be used to reproduce the test case.

+     */

+    private void recordException(Throwable e, String script, Consumer<String> reproducer) {

+        for (var ex : exceptions) {

+            if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return;

+        }

+        exceptions.add(e);

+        System.out.println("========== Stack ==========");

+        e.printStackTrace(System.out);

+        System.out.println("========== Code ===========");

+        System.out.println(script);

+        System.out.println("========= Reduced =========");

+        System.out.println(Reducer.reduce(script, e, reproducer));

+        System.out.println("===========================");

+        System.out.flush();

+    }

+

+    /**

+     * Check that two graphs result in the same output when supplied with a value

+     * @param stop1 Stop node of the first graph

+     * @param stop2 Stop node of the second graph

+     * @param in The input value to both graphs to test for an equal output

+     */

+    private static void checkGraphs(StopNode stop1, StopNode stop2, long in) {

+        var e1 = GraphEvaluator.evaluateWithResult(stop1, in, EVAL_TIMEOUT);

+        var e2 = GraphEvaluator.evaluateWithResult(stop2, in, EVAL_TIMEOUT);

+        if (e1.type() == GraphEvaluator.ResultType.TIMEOUT || e2.type() == GraphEvaluator.ResultType.TIMEOUT) return;

+        if (e1.type() != e2.type())

+            throw new RuntimeException("Different calculations types " + e1.type() + " vs " + e2.type());

+        if (e1.value() != e2.value())

+            throw new RuntimeException("Different calculations values " + e1.value() + " vs " + e2.value());

+    }

+

+    /**

+     * Run checks for script. Compile the script with peeps enabled and disabled.

+     * Check that exceptions raised in the parser by both methods are the same and only happens if the script may be invalid.

+     * If the script was successfully parsed check that both version behave the same.

+     * @param script The script to test

+     * @param valid If the script is definitely valid. If not some exceptions may be suppressed.

+     */

+    private static void runCheck(String script, boolean valid) {

+        StopNode stop1;

+        try {

+            stop1 = FuzzerUtils.parse(script, false);

+        } catch (RuntimeException e1) {

+            try {

+                FuzzerUtils.parse(script, true);

+            } catch (RuntimeException e2) {

+                if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) {

+                    if (!valid || e1.getClass() == RuntimeException.class) return;

+                } else {

+                    e1.addSuppressed(e2);

+                }

+            }

+            throw e1;

+        }

+        var stop2 = FuzzerUtils.parse(script, true);

+        checkGraphs(stop1, stop2, 0);

+        checkGraphs(stop1, stop2, 1);

+        checkGraphs(stop1, stop2, 10);

+    }

+

+    /**

+     * Check that the script does not result in exceptions.

+     * @param script The script to test.

+     * @param valid If the script is valid or if it might contain syntax errors.

+     */

+    private void check(String script, boolean valid) {

+        try {

+            runCheck(script, valid);

+        } catch (Throwable e) {

+            recordException(e, script, s->runCheck(s, valid));

+        }

+    }

+

+    /**

+     * Run one test with the given seed, and check for peephole counts.

+     * @param seed The seed to use for generating this test case

+     */

+    public int fuzzPeepTiming(long seed, int max_nids) {

+        var rand = new Random(seed);

+        var sb = new StringBuilder();

+        new ScriptGenerator(rand, sb, true).genProgram();

+        try {

+            var parser = new Parser(sb.toString());

+            

+            var stop = parser.parse();

+            int parse_peeps= Node.ITER_CNT;

+            int parse_nops = Node.ITER_NOP_CNT;

+            double parse_nop_ratio = (double)parse_nops/parse_peeps;

+            int nids = Node.UID();

+            if( nids <= max_nids ) return max_nids;

+            

+            double parse_peeps_per_node = (double)parse_peeps/nids;

+            

+            stop.iterate();

+            int iter_peeps= Node.ITER_CNT;

+            int iter_nops = Node.ITER_NOP_CNT;

+            double iter_nop_ratio = (double)iter_nops/iter_peeps;

+            double iter_peeps_per_node = (double)iter_peeps/nids;

+

+            System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f  | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n",

+                              seed,

+                              parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node,

+                              iter_peeps , iter_nops, iter_nop_ratio,      iter_peeps_per_node);

+            return nids;

+        } catch (Throwable e) {

+            // ignore exceptions, let the normal fullPeeps catch and reduce,

+            // we're interested in valid program optimizations

+        }

+        return max_nids;

+    }

+

+

+    /**

+     * Run one test with the given seed.

+     * @param seed The seed to use for generating this test case

+     */

+    public void fuzzPeeps(long seed) {

+        var rand = new Random(seed);

+        var sb = new StringBuilder();

+        var valid = new ScriptGenerator(rand, sb, false).genProgram();

+        check(sb.toString(), valid);

+    }

+

+    

+    /**

+     * Check that no exceptions happened.

+     * @return true if no exception happened

+     */

+    public boolean noExceptions() {

+        return exceptions.isEmpty();

+    }

+}

diff --git a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
new file mode 100644
index 00000000..a331e5a0
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
@@ -0,0 +1,138 @@
+package com.seaofnodes.simple.fuzzer;

+

+import com.seaofnodes.simple.IterPeeps;

+import com.seaofnodes.simple.Parser;

+import com.seaofnodes.simple.node.Node;

+import com.seaofnodes.simple.node.StopNode;

+

+import java.io.OutputStream;

+import java.io.PrintStream;

+import java.lang.invoke.MethodHandle;

+import java.lang.invoke.MethodHandles;

+import java.lang.reflect.Field;

+import java.util.BitSet;

+

+/**

+ * Some utilities for the fuzzer.

+ */

+class FuzzerUtils {

+

+    /**

+     * Get the value of a private field

+     */

+    @SuppressWarnings("unchecked")

+    public static <T> T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException {

+        return (T) (obj instanceof Class<?> clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj));

+    }

+

+    /**

+     * Get access to a private field

+     */

+    public static Field getField(Class<?> clz, String name) throws NoSuchFieldException {

+        var field = clz.getDeclaredField(name);

+        try {

+            field.setAccessible(true);

+        } catch (Throwable e) {

+            // Intentionally left empty

+        }

+        return field;

+    }

+

+    /**

+     * Try to rethrow an exception or create a runtime exception and throw it.

+     */

+    public static RuntimeException rethrow(Throwable e) {

+        if (e instanceof RuntimeException re) return re;

+        if (e instanceof Error er) throw er;

+        return new RuntimeException(e);

+    }

+

+    /**

+     * Copy of Node.WVISIST

+     * Used to clear as exceptions might happen in the walk and left this bitset not cleared

+     */

+    private static final BitSet NodeWalkVisit;

+

+    /**

+     * Write access to Iterate.MID_ASSERT

+     * Exception could happen mid assert and left this at true. Used to reset to false prior to parsing.

+     */

+    private static final MethodHandle set_MID_ASSERT;

+

+    /**

+     * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing.

+     */

+    public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream());

+

+    static {

+        try {

+            NodeWalkVisit = getFieldValue(Node.class, "WVISIT");

+            set_MID_ASSERT = MethodHandles.lookup().unreflectSetter(getField( IterPeeps.class, "MID_ASSERT"));

+        } catch (Exception e) {

+            throw new ExceptionInInitializerError(e);

+        }

+    }

+

+    /**

+     * Check that eiter one of the objects is null or that both are equal.

+     */

+    private static boolean equalOrNull(Object a, Object b) {

+        if (a == null || b == null) return true;

+        return a.equals(b);

+    }

+

+    /**

+     * Check if both stack traces have the same first entry. Empty stack traces can happen with NPE optimization

+     * and allow the other to be any stack trace.

+     */

+    private static boolean sameStackTraceOrigin(StackTraceElement[] a, StackTraceElement[] b) {

+        if (a == null || a.length == 0 || b == null || b.length == 0) return true; // One or both stack traces are missing.

+        return a[0].equals(b[0]);

+    }

+

+    /**

+     * Checks if two exceptions are caused by the same problem.

+     */

+    public static boolean isExceptionFromSameCause(Throwable a, Throwable b) {

+        if (a == null || b == null) return a == b; // Handle the null case

+        if (a.getClass() != b.getClass()) return false; // Different classes

+        if (!equalOrNull(a.getMessage(), b.getMessage())) return false; // Different messages. Null is allowed as wildcard

+        var s1 = a.getStackTrace();

+        var s2 = b.getStackTrace();

+        if (!sameStackTraceOrigin(s1, s2)) return false; // Different stack trace origins

+        if (!isExceptionFromSameCause(a.getCause(), b.getCause())) return false; // Different causes

+        var o1 = a.getSuppressed();

+        var o2 = b.getSuppressed();

+        if (o1 == null || o2 == null || o1.length != o2.length) return o1 == o2; // Different suppression

+        for (int i=0; i<o1.length; i++) {

+            if (!isExceptionFromSameCause(o1[i], o2[i])) return false; // Different suppression

+        }

+        return true;

+    }

+

+    /**

+     * Parse script with peepholes enabled or disabled

+     */

+    public static StopNode parse(String script, boolean runPeeps) {

+        var err = System.err;

+        var out = System.out;

+        try {

+            System.setErr(NULL_PRINT_STREAM);

+            System.setOut(NULL_PRINT_STREAM);

+            try {

+                set_MID_ASSERT.invokeExact(false);

+            } catch (Throwable e) {

+                throw rethrow(e);

+            }

+            var parser = new Parser(script);

+            Node._disablePeephole = !runPeeps;

+            var stop = parser.parse();

+            return runPeeps ? stop.iterate() : stop;

+        } finally {

+            NodeWalkVisit.clear();

+            System.setErr(err);

+            System.setOut(out);

+        }

+    }

+

+}

diff --git a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
new file mode 100644
index 00000000..38a4531b
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
@@ -0,0 +1,144 @@
+package com.seaofnodes.simple.fuzzer;

+

+import java.util.function.Consumer;

+import java.util.function.Predicate;

+import java.util.regex.Pattern;

+

+/**

+ * This class is used to reduce test cases created by the fuzzer.

+ * It applies rewrite rules to the test case and checks that the

+ * test still produces the same exception.

+ * This is done in a fixpoint iteration until every rewrite produces

+ * no or a different exception.

+ */

+public class Reducer {

+

+    /**

+     * Holder for the rewrite rules

+     */

+    private record Replace(Pattern p, String r) {}

+

+    /**

+     * List of rewrite rules.

+     */

+    private static final Replace[] REPLACEMENTS = {

+            new Replace(Pattern.compile("(?<=[+\\-*/<>=(])--"), ""),

+            new Replace(Pattern.compile("\\b--"), "+"),

+            new Replace(Pattern.compile("\\b\\+-"), "-"),

+            new Replace(Pattern.compile("\\bfalse\\b"), "0"),

+            new Replace(Pattern.compile("\\btrue\\b"), "1"),

+            new Replace(Pattern.compile("-"), ""),

+            new Replace(Pattern.compile("(?<![+\\-*/<>=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"),

+            new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"),

+            new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"),

+            new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"),

+            new Replace(Pattern.compile("\\b\\w+\\b"), "0"),

+            new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"),

+            new Replace(Pattern.compile("\\d+\\+"), ""),

+            new Replace(Pattern.compile("\\+\\d+"), ""),

+            new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"),

+            new Replace(Pattern.compile("\\n+"), "\n"),

+            new Replace(Pattern.compile("^\\n+|\\n+$"), ""),

+            new Replace(Pattern.compile("else *"), ""),

+            new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""),

+            new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""),

+    };

+

+    /**

+     * Predicate to test if the reduced script generates the same error.

+     */

+    private final Predicate<String> tester;

+

+    /**

+     * Create a reducer with a test function.

+     * @param tester Test function which returns true when the same issue is found in the script.

+     */

+    private Reducer(Predicate<String> tester) {

+        this.tester = tester;

+    }

+

+    /**

+     * Rewrites the script with one rewrite rule.

+     */

+    private String doReplacement(String script, Pattern pattern, String with) {

+        var matcher = pattern.matcher(script);

+        var sb = new StringBuilder();

+        int last = 0;

+        while (matcher.find()) {

+            var pos = sb.length();

+            matcher.appendReplacement(sb, with);

+            var tail = sb.length();

+            matcher.appendTail(sb);

+            if (tester.test(sb.toString())) {

+                sb.setLength(tail);

+            } else {

+                sb.setLength(pos);

+                sb.append(script, last, matcher.end());

+            }

+            last = matcher.end();

+        }

+        matcher.appendTail(sb);

+        return sb.toString();

+    }

+

+    /**

+     * Clean up variable names from the random ones generated by the fuzzer.

+     */

+    private String cleanVariables(String script) {

+        var matcher = Pattern.compile("\\bint ([0-9a-zA-Z_]+)").matcher(script);

+        int num = 0;

+        while (matcher.find()) {

+            var var = matcher.group(1);

+            if (var.matches("v\\d+")) continue;

+            while (script.contains("v"+num)) num++;

+            var n = script.replaceAll("\\b"+var+"\\b", "v" + num);

+            if (tester.test(n)) {

+                script = n;

+            }

+        }

+        return script;

+    }

+

+    /**

+     * Run all rewrite rules once.

+     */

+    private String doAllReplacements(String script) {

+        for (var replace: REPLACEMENTS) {

+            script = doReplacement(script, replace.p, replace.r);

+        }

+        return script;

+    }

+

+    /**

+     * Reduce the script to a minimal version which produces the same problem with a test function.

+     * @param tester Test function which returns true when the same issue is found in the script.

+     */

+    public static String reduce(String script, Predicate<String> tester) {

+        var reducer = new Reducer(tester);

+        String old;

+        do {

+            old = script;

+            script = reducer.doAllReplacements(script);

+            script = reducer.cleanVariables(script);

+        } while (!script.equals(old));

+        return script;

+    }

+

+    /**

+     * Reduce the script to a minimal version which produces the same problem with a reproducer.

+     * @param ex The exception originally caused by the script

+     * @param reproducer Test function which throws an exception which will be checked against ex.

+     */

+    public static String reduce(String script, Throwable ex, Consumer<String> reproducer) {

+        return reduce(script, s->{

+            Throwable nex = null;

+            try {

+                reproducer.accept(s);

+            } catch (Throwable e) {

+                nex = e;

+            }

+            return FuzzerUtils.isExceptionFromSameCause(nex, ex);

+        });

+    }

+

+}

diff --git a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
new file mode 100644
index 00000000..ad0c0a4a
--- /dev/null
+++ b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -0,0 +1,456 @@
+package com.seaofnodes.simple.fuzzer;

+

+import com.seaofnodes.simple.Parser;

+import com.seaofnodes.simple.node.ScopeNode;

+

+import java.util.ArrayList;

+import java.util.HashSet;

+import java.util.Random;

+

+/**

+ * Generate a pseudo random script.

+ * This generator will generate the same script for two random number generators initialized with the same seed.

+ * To generate valid code it implements the parser but instead of parsing it emits the statements and expressions.

+ * It is guaranteed to terminate.

+ */

+public class ScriptGenerator {

+

+    /**

+     * Number of spaces per indentation

+     */

+    private static final int INDENTATION = 4;

+    /**

+     * Valid characters for identifiers. The last 10 are not valid for the first character.

+     */

+    private static final String VAR_CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_0123456789";

+    /**

+     * List of keywords not valid for identifiers.

+     */

+    private static final HashSet<String> KEYWORDS;

+

+    static {

+        try {

+            KEYWORDS = FuzzerUtils.getFieldValue(new Parser(""), "KEYWORDS");

+        } catch (Throwable e) {

+            throw new ExceptionInInitializerError(e);

+        }

+    }

+

+    /**

+     * Flag for a statement that it does not pass on control flow to the next statement.

+     */

+    private static final int FLAG_STOP = 0x01;

+    /**

+     * Flag for a statement that it contains a final if statement without an else branch.

+     */

+    private static final int FLAG_IF_WITHOUT_ELSE = 0x02;

+    /**

+     * Binary operators.

+     */

+    private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"};

+    /**

+     * Unary operators.

+     */

+    private static final String[] UNARY_OP = {"-"};

+

+

+    /**

+     * The random number generator used for random decisions.

+     */

+    private final Random random;

+    /**

+     * Indentation depth.

+     */

+    private int indentation = 0;

+    /**

+     * Output string builder

+     */

+    private final StringBuilder sb;

+    /**

+     * Number of nested loops

+     */

+    private int loopDepth = 0;

+    /**

+     * Current scope start in the variables list.

+     */

+    private int currScopeStart = 0;

+    /**

+     * The depth of blocks allowed.

+     */

+    private int depth = 20;

+    /**

+     * The depth of expressions allowed.

+     */

+    private int exprDepth = 30;

+    /**

+     * Current variables in scope.

+     */

+    private final ArrayList<String> variables = new ArrayList<>();

+    /**

+     * If this needs to generate valid scripts or is also allowed to generate invalid ones.

+     */

+    private final boolean generateValid;

+    /**

+     * If this script might be invalid.

+     */

+    private boolean maybeInvalid = false;

+

+    /**

+     *

+     * @param random the random number generator.

+     * @param sb the script will be written to this string builder.

+     * @param generateValid if the script should be guaranteed valid or if it is allowed to contain bugs.

+     */

+    public ScriptGenerator(Random random, StringBuilder sb, boolean generateValid) {

+        this.random = random;

+        this.sb = sb;

+        this.generateValid = generateValid;

+    }

+

+    /**

+     * Random number with log distribution

+     * @param max The maximum value

+     * @return A random number in the range [0, max) with higher numbers being more uncommon.

+     */

+    private int randLog(int max) {

+        max--;

+        int n = 1<<max;

+        var num = random.nextInt(n);

+        for (int i=max-1; i>=0; i--) {

+            if ((num & (1<<i))!=0) return max-i-1;

+        }

+        return max;

+    }

+

+    /**

+     * Helper function to print indentation.

+     * @return sb for chaining

+     */

+    private StringBuilder printIndentation() {

+        return sb.repeat(' ', indentation);

+    }

+

+    /**

+     * Generate a random name for variables. This might be invalid when it is a keyword.

+     * @return The random name generated

+     */

+    private StringBuilder getRandomName() {

+        int len = random.nextInt(30) + 1;

+        StringBuilder sb = new StringBuilder(len);

+        sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10)));

+        for (int i=1; i<len; i++)

+            sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length())));

+        return sb;

+    }

+

+    /**

+     * Generate a variable name. This might be new random name or a name from an outer scope.

+     * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope.

+     * @return The variable name.

+     */

+    private String getVarName() {

+        if (currScopeStart > 0 && random.nextInt(10) > 7) {

+            // Use a variable outside the current scope.

+            var v = variables.get(random.nextInt(currScopeStart));

+            if (variables.lastIndexOf(v) < currScopeStart) return v;

+            if (!generateValid) {

+                maybeInvalid = true;

+                return v;

+            }

+        }

+        // Generate a new random variable name

+        StringBuilder sb = getRandomName();

+        var v = sb.toString();

+        if (!generateValid && (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart)) {

+            maybeInvalid = true;

+            return v;

+        }

+        while (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart) {

+            sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length())));

+            v = sb.toString();

+        }

+        return v;

+    }

+

+

+

+    /**

+     * Generates a program and writes it into the string builder supplied in the constructor.

+     * @return If the program is allowed to be invalid returns if something potentially invalid was generated.

+     */

+    public boolean genProgram() {

+        this.maybeInvalid = false;

+        variables.add(ScopeNode.ARG0);

+        currScopeStart = variables.size();

+        if ((genStatements() & FLAG_STOP) == 0) {

+            if (generateValid || random.nextInt(10)<7) {

+                genReturn();

+            } else {

+                this.maybeInvalid = true;

+            }

+        }

+        return !this.maybeInvalid;

+    }

+

+    /**

+     * Generate a list of statements.

+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated

+     */

+    public int genStatements() {

+        var num = random.nextInt(10); // (30);

+        for (int i=0; i<num; i++) {

+            printIndentation();

+            var stop = genStatement();

+            sb.append("\n");

+            if ((stop & FLAG_STOP) != 0) return stop;

+        }

+        return 0;

+    }

+

+    /**

+     * Generate a single statement

+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement

+     */

+    public int genStatement() {

+        return switch (random.nextInt(10)) {

+            case 1 -> genBlock();

+            case 2 -> genIf();

+            case 3 -> genWhile();

+            case 4, 5 -> genDecl();

+            case 6, 7, 8 -> genAssignment();

+            default -> genExit();

+        };

+    }

+

+    /**

+     * Generate a statement for if, else and while blocks.

+     * This is special since it disallows declarations and prefers to generate blocks.

+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement

+     */

+    public int genStatementBlock() {

+        indentation += INDENTATION;

+        int res;

+        if (depth == 0) {

+            res = random.nextBoolean() ? genAssignment() : genExit();

+        } else {

+            depth--;

+            res = switch (random.nextInt(10)) {

+                case 1, 2, 3, 4, 5 -> {

+                    depth++;

+                    indentation -= INDENTATION;

+                    var ret = genBlock();

+                    indentation += INDENTATION;

+                    depth--;

+                    yield ret;

+                }

+                case 6 -> genIf();

+                case 7 -> genWhile();

+                case 8 -> genAssignment();

+                default -> genExit();

+            };

+            depth++;

+        }

+        indentation -= INDENTATION;

+        return res;

+    }

+

+    /**

+     * Generate an exit. This can be return or break and continue when in a loop.

+     * @return FLAG_STOP

+     */

+    public int genExit() {

+        if (loopDepth == 0 && generateValid) return genReturn();

+        return switch (random.nextInt(7)) {

+            case 0,1,2 -> {

+                if (loopDepth == 0) maybeInvalid = true;

+                sb.append("continue;");

+                yield FLAG_STOP;

+            }

+            case 3,4,5 -> {

+                if (loopDepth == 0) maybeInvalid = true;

+                sb.append("break;");

+                yield FLAG_STOP;

+            }

+            default -> genReturn();

+        };

+    }

+

+    /**

+     * Generate a block statement. After a certain depth only empty blocks are generated to ensure termination of the generator.

+     * @return flag FLAG_STOP for the generated statement

+     */

+    public int genBlock() {

+        if (depth == 0) {

+            sb.append("{}");

+            return 0;

+        }

+        depth--;

+        int oldCSS = currScopeStart;

+        currScopeStart = variables.size();

+        sb.append("{\n");

+        indentation += INDENTATION;

+        var stop = genStatements();

+        indentation -= INDENTATION;

+        printIndentation().append("}");

+        while (variables.size() > currScopeStart)

+            variables.removeLast();

+        currScopeStart = oldCSS;

+        depth++;

+        return stop & ~FLAG_IF_WITHOUT_ELSE;

+    }

+

+    /**

+     * Generate an if statement with an optional else block.

+     * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement

+     */

+    public int genIf() {

+        sb.append("if(");

+        genExpression();

+        sb.append(") ");

+        var stop = genStatementBlock();

+        if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) {

+            sb.append("\n");

+            printIndentation().append("else ");

+            stop &= genStatementBlock();

+        } else {

+            stop = FLAG_IF_WITHOUT_ELSE;

+        }

+        return stop;

+    }

+

+    /**

+     * Generate a while loop.

+     * @return 0

+     */

+    public int genWhile() {

+        sb.append("while(");

+        genExpression();

+        sb.append(") ");

+        loopDepth++;

+        genStatementBlock();

+        loopDepth--;

+        return 0;

+    }

+

+    /**

+     * Generate a declaration statement.

+     * @return 0

+     */

+    public int genDecl() {

+        String name = getVarName();

+        sb.append("int ").append(name).append("=");

+        genExpression();

+        sb.append(";");

+        variables.add(name);

+        return 0;

+    }

+

+    /**

+     * Generate an assignment statement.

+     * @return 0

+     */

+    public int genAssignment() {

+        if (variables.isEmpty()) return genDecl();

+        genVariable();

+        sb.append("=");

+        genExpression();

+        sb.append(";");

+        return 0;

+    }

+

+    /**

+     * Generate a return statement.

+     * @return FLAG_STOP

+     */

+    public int genReturn() {

+        sb.append("return ");

+        genExpression();

+        sb.append(";");

+        return FLAG_STOP;

+    }

+

+

+    /**

+     * Generate a binary expression.

+     * This method does not care about operator precedence.

+     */

+    public void genExpression() {

+        var num = randLog(10);

+        while(num-->0) {

+            genUnary();

+            sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]);

+        }

+        genUnary();

+    }

+

+    /**

+     * Generate a unary expression.

+     */

+    public void genUnary() {

+        var num = randLog(6);

+        while(num-->0) {

+            sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]);

+        }

+        genPrimary();

+    }

+

+    /**

+     * Generate a primary expression.

+     */

+    public void genPrimary() {

+        switch (random.nextInt(10)) {

+            case 0:

+                sb.append("true");

+                break;

+            case 1:

+                sb.append("false");

+                break;

+            case 2:

+                if (exprDepth == 0) {

+                    // Ensure termination of the generator.

+                    if (random.nextBoolean()) {

+                        genNumber();

+                    } else {

+                        genVariable();

+                    }

+                } else {

+                    sb.append("(");

+                    exprDepth--;

+                    genExpression();

+                    exprDepth++;

+                    sb.append(")");

+                }

+                break;

+            case 3, 4, 5, 6:

+                genNumber();

+                break;

+            default:

+                genVariable();

+        }

+    }

+

+    /**

+     * Generate a number.

+     */

+    public void genNumber() {

+        sb.append(random.nextInt(100));

+    }

+

+    /**

+     * Generate a variable. If there are none generate a number instead.

+     * If the program is allowed to be invalid a random name can be generated in some cases.

+     */

+    public void genVariable() {

+        if (!generateValid && random.nextInt(100)>97) {

+            sb.append(getRandomName());

+            maybeInvalid = true;

+            return;

+        }

+        if (variables.isEmpty()) {

+            genNumber();

+        } else {

+            sb.append(variables.get(random.nextInt(variables.size())));

+        }

+    }

+

+}