Chapter 9: Global Value Numbering and Iterative Peepholes

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Hadházy Tamás <helsgithub15@gmail.com>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

11 files changed, 563 insertions, 92 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
index 609dff76..c3cd43c3 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java
@@ -31,7 +31,7 @@ public class Chapter03Test {
 
     @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); ");
+        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);");
         StopNode ret = parser.parse();
         assertEquals("return 8;", ret.print());
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index fa9a5e37..2c869033 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -21,7 +21,7 @@ else {
 }
 
 return a;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
     }
 
@@ -36,7 +36,7 @@ if (arg == 1) {
     c = 4;
 }
 return c;""", TypeInteger.BOT);
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return Phi(Region16,4,3);", ret.toString());
     }
 
@@ -64,7 +64,7 @@ if( arg==1 )
 else
     b=a+1;
 return a+b;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString());
     }
 
@@ -79,7 +79,7 @@ if( arg==1 )
 else
     a=b+1;
 return a+b;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString());
     }
 
@@ -99,7 +99,7 @@ else
     a=5;
 return a;
 """, TypeInteger.BOT);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString());
     }
 
@@ -129,7 +129,7 @@ if( arg==1 )
     a=arg==3;
 }
 return a;""");
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return (arg==Phi(Region16,3,2));", ret.toString());
     }
 
@@ -184,6 +184,7 @@ return a;
         }
     }
 
+
     @Test
     public void testBadNum() {
         try {
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index 00d725bc..054e96e8 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -15,7 +15,7 @@ public class Chapter06Test {
 if( true ) return 2;
 return 1;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 2;", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -29,7 +29,7 @@ if (arg)
     a = 2;
 return (arg < a) < 3;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString());
     }
 
@@ -44,7 +44,7 @@ else
   a=3;
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 2;", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -64,7 +64,7 @@ if( a==2 )
 else
     b=5;
 return b;""", TypeInteger.BOT);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region32,42,5);", stop.toString());
     }
 
@@ -83,8 +83,8 @@ if( arg==2 )
 else
     b=5;
 return b;""", TypeInteger.BOT);
-        StopNode stop = parser.parse();
-        assertEquals("return Phi(Region28,2,5);", stop.toString());
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Region29,2,5);", stop.toString());
     }
 
     @Test
@@ -123,7 +123,7 @@ else
     a=5;
 return a;
 """, TypeInteger.constant(1));
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 3;", stop.toString());
     }
 
@@ -143,8 +143,8 @@ else
     a=5;
 return a;
 """, TypeInteger.BOT);
-        StopNode stop = parser.parse();
-        assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString());
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Region37,3,Phi(Region35,4,5));", stop.toString());
     }
 
     @Test
@@ -163,7 +163,7 @@ else
     a=5;
 return a;
 """, TypeInteger.constant(1));
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 3;", stop.toString());
     }
 
@@ -183,7 +183,7 @@ else
     a=5;
 return a;
 """, TypeInteger.constant(3));
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return 4;", stop.toString());
     }
 
@@ -199,8 +199,8 @@ if( arg ) {
 }
 return a+b;
 """);
-        StopNode ret = parser.parse();
-        assertEquals("return Phi(Region22,4,1);", ret.toString());
+        StopNode ret = parser.parse().iterate();
+        assertEquals("return Phi(Region24,4,1);", ret.toString());
     }
 
 
@@ -216,7 +216,7 @@ if( arg ) {
 }
 return a+b;
 """, TypeInteger.constant(1));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 4;", ret.toString());
     }
 
@@ -232,7 +232,7 @@ if( arg ) {
 }
 return a+b;
 """, TypeInteger.constant(0));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 1;", ret.toString());
     }
 
@@ -250,8 +250,8 @@ if( arg ) {
 }
 return a+b+c;
 """);
-        StopNode ret = parser.parse();
-        assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString());
+        StopNode ret = parser.parse().iterate();
+        assertEquals("return (Phi(Region35,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString());
     }
 
 
@@ -269,7 +269,7 @@ if( arg ) {
 }
 return a+b+c;
 """, TypeInteger.constant(1));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 6;", ret.toString());
     }
 
@@ -287,7 +287,7 @@ if( arg ) {
 }
 return a+b+c;
 """, TypeInteger.constant(2));
-        StopNode ret = parser.parse();
+        StopNode ret = parser.parse().iterate();
         assertEquals("return 5;", ret.toString());
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
index 26b5c17d..109ee830 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java
@@ -34,7 +34,7 @@ if(arg){}else{
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString());
     }
 
@@ -54,7 +54,7 @@ while(i < arg) {
 }
 return sum;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString());
     }
 
@@ -89,7 +89,7 @@ while(a < 10) {
 }
 return b;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -122,7 +122,7 @@ while(a < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -148,7 +148,7 @@ int a = 1;
 while(arg) a = 2;
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,2);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -180,7 +180,7 @@ while(a < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -214,7 +214,7 @@ while(a < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 5d9d1545..cea6dd0f 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -4,22 +4,12 @@ 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
-    @Ignore
-    public void testJig() {
-        Parser parser = new Parser("""
-// Insert test case here
-""");
-        StopNode stop = parser.parse();
-    }
-
-    @Test
     public void testEx6() {
         Parser parser = new Parser(
                 """
@@ -32,7 +22,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         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));
@@ -55,7 +45,7 @@ while(arg < 10) {
 }
 return a;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -74,7 +64,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
@@ -90,7 +80,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
@@ -109,7 +99,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -126,7 +116,7 @@ while(arg < 10) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof ProjNode);
     }
@@ -142,15 +132,15 @@ while( arg < 10 ) {
 }
 return arg;
                 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return arg;", stop.toString());
     }
 
     @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();
-        assertEquals("Stop[ return 0; return 0; ]", stop.toString());
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 0;", stop.toString());
     }
 
     @Test
@@ -177,7 +167,7 @@ while(arg < 10) {
 }
 return arg;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return arg;", stop.toString());
     }
 
@@ -194,7 +184,7 @@ while(arg < 10) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
@@ -210,9 +200,9 @@ while(1) {
 }
 return a;
 """);
-        StopNode stop = parser.parse();
+        StopNode stop = parser.parse().iterate();
         assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString());
-        assertTrue(stop.ret().ctrl() instanceof RegionNode);
+        assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 );
     }
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
new file mode 100644
index 00000000..8103b903
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java
@@ -0,0 +1,320 @@
+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();
+    }
+
+    @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();
+        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();
+        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().iterate();
+        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().iterate();
+        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();
+        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();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testSccp() {
+        Parser parser = new Parser(
+"""
+int x = 1;
+int cnt = 5;
+while (cnt) {
+  cnt = cnt - 1;
+  if (x == 0) {
+    x = x + 1;
+  }
+}
+return x;
+"""
+        );
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return Phi(Loop8,1,Phi(Region26,(Phi_x+1),Phi_x));", stop.toString());
+
+    }
+
+    @Test
+    public void testWhile0() {
+        Parser parser = new Parser("while(0) continue; if(0) arg=0;");
+        StopNode stop = parser.parse().iterate();
+        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();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+
+    @Test
+    public void testPrecedence() {
+        Parser parser = new Parser("return 3-1+2;");
+        StopNode stop = parser.parse().iterate();
+        assertEquals("return 4;", stop.toString());
+    }
+
+    @Test
+    public void testSwap2() {
+        Parser parser = new Parser("return 1+(1+1);");
+        StopNode stop = parser.parse().iterate();
+        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();
+        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();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+
+    @Test
+    public void testFuzz2() {
+        Parser parser = new Parser("return 0+-0;");
+        StopNode stop = parser.parse().iterate();
+        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();
+        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();
+        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();
+        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();
+        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();
+        assertEquals("Stop[ ]", stop.toString());
+    }
+
+    @Test
+    public void testFuzz8() {
+        Parser parser = new Parser("while(arg) arg = arg - 1;  return arg;");
+        StopNode stop = parser.parse().iterate();
+        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/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
index 33434b6c..019140ad 100644
--- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
+++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java
@@ -1,8 +1,8 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.fuzzer.Fuzzer;
-import org.junit.Ignore;
 import org.junit.Test;
+import org.junit.Ignore;
 
 
 import static org.junit.Assert.assertTrue;
@@ -33,9 +33,18 @@ public class FuzzerWrap {
     @Ignore
     public void fuzzPeepsLarge() {
         var fuzzer = new Fuzzer();
-        for (int i=0; i<100000; i++)
+        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/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
index ef73fa4b..c3444093 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java
@@ -1,6 +1,8 @@
 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;
@@ -13,8 +15,8 @@ import java.util.function.Consumer;
  * 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. Generated graphs are evaluated
- * to detect compiler/evaluator failures; this chapter has no differential oracle.
+ * to only show one occurrence of one problem. This includes script which generate different
+ * results when graphs optimized with different worklist seeds are executed.
  * To aid debugging scripts that cause errors are then reduced by applying rules and checking
  * that the same issue persists.
  */
@@ -49,17 +51,49 @@ public class Fuzzer {
         System.out.flush();
     }
 
-    /** Compile and evaluate generated programs with normal peepholes. */
+    /**
+     * 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 two different optimizer worklist seeds.
+     * 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 stop;
+        StopNode stop1;
         try {
-            stop = FuzzerUtils.parse(script);
-        } catch (RuntimeException e) {
-            if (!valid || e.getClass() == RuntimeException.class) return;
-            throw e;
+            stop1 = FuzzerUtils.parse(script, 123);
+        } catch (RuntimeException e1) {
+            try {
+                FuzzerUtils.parse(script, 456);
+            } catch (RuntimeException e2) {
+                if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) {
+                    if (!valid || e1.getClass() == RuntimeException.class) return;
+                } else {
+                    e1.addSuppressed(e2);
+                }
+            }
+            throw e1;
         }
-        for (int input : new int[] {0, 1, 10})
-            GraphEvaluator.evaluateWithResult(stop, input, EVAL_TIMEOUT);
+        var stop2 = FuzzerUtils.parse(script, 456);
+        checkGraphs(stop1, stop2, 0);
+        checkGraphs(stop1, stop2, 1);
+        checkGraphs(stop1, stop2, 10);
     }
 
     /**
@@ -76,6 +110,45 @@ public class Fuzzer {
     }
 
     /**
+     * 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
      */
@@ -86,6 +159,7 @@ public class Fuzzer {
         check(sb.toString(), valid);
     }
 
+
     /**
      * Check that no exceptions happened.
      * @return true if no exception happened
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
index 0e83861d..6488297b 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java
@@ -1,15 +1,81 @@
 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;
+    private static final java.util.Random WorkRandom;
+
+    /**
+     * 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");
+            WorkRandom = getFieldValue(getFieldValue(IterPeeps.class, "WORK"), "_R");
+            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) {
@@ -47,11 +113,28 @@ class FuzzerUtils {
     }
 
     /**
-     * Parse script with normal peephole optimization
+     * Parse and optimize using the given worklist seed
      */
-    public static StopNode parse(String script) {
-        var parser = new Parser(script);
-        return parser.parse();
+    public static StopNode parse(String script, long workListSeed) {
+        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);
+            WorkRandom.setSeed(workListSeed);
+            var stop = parser.parse();
+            return stop.iterate();
+        } finally {
+            NodeWalkVisit.clear();
+            System.setErr(err);
+            System.setOut(out);
+        }
     }
 
 }
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
index b7fc18ec..2ef0a3fd 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java
@@ -32,8 +32,8 @@ public class Reducer {
             new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"),
             new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"),
             new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"),
-            new Replace(Pattern.compile("\\b\\w+\\b"), "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"),
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index 148c2319..ad98f7e2 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -16,20 +16,6 @@ import java.util.Random;
 public class ScriptGenerator {
 
     /**
-     * Get the list of keywords from the parser.
-     */
-    @SuppressWarnings("unchecked")
-    private static HashSet<String> getKeywords() {
-        try {
-            var field = Parser.class.getDeclaredField("KEYWORDS");
-            field.setAccessible(true);
-            return (HashSet<String>) field.get(new Parser(""));
-        } catch (Throwable e) {
-            throw new ExceptionInInitializerError(e);
-        }
-    }
-
-    /**
      * Number of spaces per indentation
      */
     private static final int INDENTATION = 4;
@@ -40,7 +26,15 @@ public class ScriptGenerator {
     /**
      * List of keywords not valid for identifiers.
      */
-    private static final HashSet<String> KEYWORDS = getKeywords();
+    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.
@@ -83,11 +77,11 @@ public class ScriptGenerator {
     /**
      * The depth of blocks allowed.
      */
-    private int depth = 7;
+    private int depth = 20;
     /**
      * The depth of expressions allowed.
      */
-    private int exprDepth = 3;
+    private int exprDepth = 30;
     /**
      * Current variables in scope.
      */
@@ -141,7 +135,7 @@ public class ScriptGenerator {
      * @return The random name generated
      */
     private StringBuilder getRandomName() {
-        int len = random.nextInt(10) + 1;
+        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++)
@@ -203,7 +197,7 @@ public class ScriptGenerator {
      * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated
      */
     public int genStatements() {
-        var num = random.nextInt(10);
+        var num = random.nextInt(10); // (30);
         for (int i=0; i<num; i++) {
             printIndentation();
             var stop = genStatement();