From 22df891893d30e9906d0b14fc3ae5d8e67d500b2 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 3 Oct 2026 14:03:48 -0700 Subject: Chapter renumber, and split ch 17 Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14]. Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly. THe new immutable syntax is pushed through all later chapters --- .../java/com/seaofnodes/simple/Chapter01Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 12 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 48 +- .../java/com/seaofnodes/simple/Chapter08Test.java | 25 +- .../java/com/seaofnodes/simple/Chapter09Test.java | 26 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 21 +- .../java/com/seaofnodes/simple/Chapter10bTest.java | 64 --- .../java/com/seaofnodes/simple/Chapter11Test.java | 578 ++------------------- .../java/com/seaofnodes/simple/Chapter12Test.java | 199 +++++-- .../java/com/seaofnodes/simple/FuzzerWrap.java | 2 +- .../test/java/com/seaofnodes/simple/TypeTest.java | 4 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 27 +- .../com/seaofnodes/simple/evaluator/Scheduler.java | 14 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 84 +-- 16 files changed, 349 insertions(+), 773 deletions(-) delete mode 100644 chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java (limited to 'chapter12/src/test') diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java index c10dc510..89882b2f 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -15,7 +15,7 @@ public class Chapter01Test { StartNode start = Parser.START; ReturnNode ret = (ReturnNode)stop.in(0); - assertTrue(ret.ctrl() instanceof CProjNode); + assertTrue(ret.ctrl() instanceof ProjNode); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { assertEquals(start,con.in(0)); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 14d31245..edc62f50 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -83,7 +83,7 @@ public class Chapter04Test { Parser parser = new Parser("return arg; "); StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof CProjNode); + assertTrue(ret.in(0) instanceof ProjNode); assertTrue(ret.in(1) instanceof ProjNode); assertEquals(1, ((ProjNode)ret.in(1))._idx); assertTrue(ret.in(2) instanceof ProjNode); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 7beeb4d9..97cd9940 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -22,7 +22,7 @@ else { return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region21,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region19,(arg+2),(arg-3));", ret.toString()); } @Test @@ -37,7 +37,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region19,4,3);", ret.toString()); + assertEquals("return Phi(Region18,4,3);", ret.toString()); } @Test @@ -65,7 +65,7 @@ else b=a+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((arg*2)+Phi(Region24,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region22,2,3));", ret.toString()); } @Test @@ -80,7 +80,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region35,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region33,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test @@ -100,7 +100,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region39,Phi(Region25,2,3),Phi(Region37,4,5));", stop.toString()); + assertEquals("return Phi(Region37,Phi(Region23,2,3),Phi(Region35,4,5));", stop.toString()); } @Test @@ -116,7 +116,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region31,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region32,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region19,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region18,3,2));", ret.toString()); } @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java index df0f2848..9af11b68 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -17,7 +17,7 @@ return 1; """); StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -46,7 +46,7 @@ return a; """); StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region40,42,5);", stop.toString()); + assertEquals("return Phi(Region38,42,5);", stop.toString()); } @Test @@ -84,7 +84,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region33,2,5);", stop.toString()); + assertEquals("return Phi(Region31,2,5);", stop.toString()); } @Test @@ -144,7 +144,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region44,3,Phi(Region42,4,5));", stop.toString()); + assertEquals("return Phi(Region42,3,Phi(Region40,4,5));", stop.toString()); } @Test @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region39,Phi(Region26,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region39,Phi(Region24,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 222982e7..ff0ca599 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -18,8 +18,8 @@ public class Chapter07Test { return arg; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -35,7 +35,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region27,1,Phi(Loop16,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region25,1,Phi(Loop14,1,(Phi_a+1)));", stop.toString()); } @Test @@ -55,7 +55,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,0,Phi(Loop23,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + assertEquals("return Phi(Loop9,0,Phi(Loop21,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -71,8 +71,8 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,2,Phi(Region30,Phi_b,4));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,2,Phi(Region28,Phi_b,4));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -90,8 +90,8 @@ while(a < 10) { return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,2,(Phi(Region30,Phi_b,4)+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,2,(Phi(Region28,Phi_b,4)+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -107,8 +107,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -123,8 +123,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -136,8 +136,8 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -149,8 +149,8 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,2);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -165,8 +165,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -181,8 +181,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -198,8 +198,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -215,8 +215,8 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop9,1,(Phi_a+3));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 8c644977..02c3a301 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; @@ -23,7 +24,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region37,Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region38,Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); @@ -46,8 +47,8 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop8,1,Phi(Region45,Phi_a,(Phi_a+1)));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -65,7 +66,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region36,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -81,7 +82,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region26,Phi(Loop7,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -100,8 +101,8 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -117,8 +118,8 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop7,arg,(Phi_arg+1));", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); } @Test @@ -185,7 +186,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region30,Phi(Loop10,1,(Phi_a+1)),Add);", stop.toString()); + assertEquals("return Phi(Region29,Phi(Loop8,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -201,8 +202,8 @@ while(1) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop10,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); + assertEquals("return (Phi(Loop8,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 49ee75a2..b1fdc459 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -5,6 +5,7 @@ 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; @@ -69,7 +70,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+2));", stop.toString()); + assertEquals("return Phi(Loop8,arg,(Phi_arg+2));", stop.toString()); Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); } @@ -86,7 +87,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,arg,(Phi_arg+4));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+4));", stop.toString()); Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); } @@ -115,7 +116,7 @@ while (arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop17,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop15,arg,(Phi_arg+1));", stop.toString()); } @Test @@ -133,7 +134,7 @@ while(v1+arg) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -185,7 +186,7 @@ while(arg) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,(-(Phi_a+3)));", stop.toString()); + assertEquals("return Phi(Loop10,0,(-(Phi_a+3)));", stop.toString()); } @Test @@ -199,7 +200,7 @@ int v0=0!=0<-0; return -0+0+0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @@ -226,7 +227,7 @@ while(1) { } """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test @@ -248,17 +249,16 @@ while(1) { return 0!=0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ ]", stop.toString()); } @Test public void testFuzz6() { - Parser parser = new Parser( -""" + Parser parser = new Parser(""" int v0=0; while(0==1) while(v0) v0=1+v0; -"""); + """); StopNode stop = parser.parse().iterate(); assertEquals("return 0;", stop.toString()); } @@ -276,14 +276,14 @@ while(1) return v1+v0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + 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(Loop9,arg,(Phi_arg-1));", stop.toString()); + assertEquals("return Phi(Loop7,arg,(Phi_arg-1));", stop.toString()); } @Test diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 38aceb84..55574c13 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -169,7 +169,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString()); } @Test @@ -221,7 +221,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region17,null,new Bar);", stop.toString()); + assertEquals("return Phi(Region31,(*void)Phi(Region18,null,new Bar),null);", stop.toString()); } @Test @@ -237,7 +237,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,4,3);", stop.toString()); + assertEquals("return Phi(Region37,4,3);", stop.toString()); } @Test @@ -254,8 +254,7 @@ while(arg) { return ret; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { - assertEquals("Might be null accessing 'v0'", e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing 'v0'", e.getMessage()); } } @Test @@ -307,12 +306,11 @@ while(arg) { v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; - } return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); } @Test @@ -329,7 +327,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,new s0,Phi(Region36,new s0,Phi_ret));", stop.toString()); } @@ -346,7 +344,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop11,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString()); } @Test @@ -464,6 +462,7 @@ return 0; assertEquals("return 0;", stop.toString()); } + @Test public void testReadBeforeStores() { var stop = new Parser(""" struct S { int x; int y; } @@ -550,8 +549,8 @@ return 0; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - // These chapters still bind struct Stores to branch control. - assertEquals(3,countMemoryNodes(stop,StoreNode.class,new BitSet())); + // The initializing slice also remains live as the aggregate default. + assertEquals(2,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java deleted file mode 100644 index 6f094cfb..00000000 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter10bTest.java +++ /dev/null @@ -1,64 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.evaluator.Evaluator; -import org.junit.Test; -import static org.junit.Assert.*; - -public class Chapter10bTest { - @Test public void testIndependentField() { - var stop = new Parser(""" - struct S { int x; int y; } - S s = new S; - s.x = 42; - while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } - return s.x; - """).parse().iterate(); - assertEquals("return 42;",stop.toString()); - assertEquals(42L,Evaluator.evaluate(stop,5)); - assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); - } - - @Test public void testParallelMemoryPhis() { - var stop = new Parser(""" - struct S { int x; int y; int z; } - S a = new S; S b = new S; - S p = a; if (arg) p = b; - while (arg > 0) { - a.x = p.x + arg; - a.y = p.y + 2; - a.z = p.z + 3; - arg = arg - 1; - } - return a; - """).parse().iterate(); - int[] phis = {0}; - stop.walk(n -> { - if (n instanceof MemPhiNode) phis[0]++; - if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) - for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) - assertTrue(a=3); - assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); - } - - @Test public void testLateSliceWorklist() throws ReflectiveOperationException { - // Seed 97 exposed a store selecting a bulk predecessor without queuing - // it. Keep both the worklist assertion and the final heap check. - for (int seed : new int[]{0,97,123,456}) { - var parser = new Parser(Chapter10Test.NESTED_MEMORY); - var field = IterPeeps.class.getDeclaredField("WORK"); - field.setAccessible(true); - Object work = field.get(null); - field = work.getClass().getDeclaredField("_R"); - field.setAccessible(true); - ((java.util.Random)field.get(work)).setSeed(seed); - var stop = parser.parse().iterate(); - assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); - } - } -} diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 0e492591..5f92c9c1 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,532 +1,64 @@ package com.seaofnodes.simple; - +import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; - - -import static org.junit.Assert.assertEquals; +import static org.junit.Assert.*; public class Chapter11Test { - - // A placeholder test used to rapidly rotate through fuzzer produced issues - @Test - public void testFuzzer() { - Parser parser = new Parser( -""" -while(-----arg) { - while(-arg) { - while(-----arg*---0) { - int N=--false==false<--arg; - while(N<-4==N) { - N=N+N; - } - } - { - int kzEl_r7EYz=3*----0!=-arg<(37*--97!=0/arg==arg)<=-(--arg!=0); - while(kzEl_r7EYz<---1) { - kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24; - if(7) continue; - kzEl_r7EYz=false; - if(-kzEl_r7EYz+arg<-3) continue; - else { - while(kzEl_r7EYz) continue; - arg=----3; - kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz); - int v2uF_4ba=9; - } - } - } - int pjcp7rv=arg; - { - int m2ya3=--arg-pjcp7rv; - while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) { - m2ya3=m2ya3+-(--0<=false=-pjcp7rv>=arg<=arg); - while(arg<-arg) { - arg=arg+--arg; - { - while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33); - pjcp7rv=11; - int c=pjcp7rv; - if(--107) break; - else break; - } - } - } - pjcp7rv=pjcp7rv; - int aR0Wkua=-pjcp7rv==pjcp7rv; - { - if(-0!=-0) while(-true) break; - else { - while(aR0Wkua) pjcp7rv=-0/pjcp7rv; - pjcp7rv=pjcp7rv; - } - } - } - if(-arg) { - { - int Isdlt0fr91=0!=arg; - while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) { - Isdlt0fr91=Isdlt0fr91+-1!=true; - if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91; - int i=---arg<---arg!=--40; - { - int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0; - while(jVX43Ln4Dm<--(3-3)) { - jVX43Ln4Dm=jVX43Ln4Dm+-0<25; - i=24<--(jVX43Ln4Dm); - } - } - i=(arg!=----false>=7); - int Te=5>-arg; - break; - } - } - arg=arg!=--true/arg; - { - int UX=arg; - while(UX<-3*arg) { - UX=UX+arg/-1; - arg=-3--(-UX--47=-arg; - if(---12) while(-UX) break; - break; - } - } - continue; - } - if(arg) arg=--0; - else if(1) continue; - int DtTlhjYq=19==arg; - { - arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq); - if(---arg) continue; - else { - int Zsl=40; - while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) { - Zsl=Zsl+arg; - } - } - if((arg)) if(-DtTlhjYq) { - } - else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false; - else { - int lwbF=arg>=0; - while(lwbF<57) { - lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg; - arg=----0+0; - while(49) break; - if(true) DtTlhjYq=-----arg; - DtTlhjYq=0!=-----(0); - } - } - arg=---arg!=DtTlhjYq/--0; - DtTlhjYq=-DtTlhjYq/(--argDtTlhjYq; - else { - } - DtTlhjYq=-0; - { - while((0)<-arg) DtTlhjYq=-DtTlhjYq; - } - if(30/--(arg)>=0) DtTlhjYq=-0>=arg; - else { - int Y2wcIQJ=--DtTlhjYq*---11; - if(arg==arg) { - Y2wcIQJ=-----Y2wcIQJ; - Y2wcIQJ=Y2wcIQJ<7; - if(DtTlhjYq) arg=arg; - else break; - while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3; - } - continue; - } - arg=DtTlhjYq; - arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq; - arg=51+---(-true)!=arg!=----1==-DtTlhjYq; - if(11<=arg) if((arg)+79<32+(-arg)) continue; - else if(true==DtTlhjYq) break; - break; - } -} -if(arg!=62==arg) { - while(---arg) { - { - int bhmDacPM=arg/arg; - while(bhmDacPM1)=-arg+-arg; - break; - } - } - int arg=true; - arg=arg<=arg; - { - int KlC=30; - while(KlC<-2) { - KlC=KlC+-1!=25<=-KlC>KlC>----0; - int Ij=arg>=-arg<=---10; - { - int LAbgurVa2R=-arg!=Ij; - while(LAbgurVa2R<-true) { - LAbgurVa2R=LAbgurVa2R+Ij; - KlC=-LAbgurVa2R; - Ij=42*(-Ij>true); - while(Ij) arg=KlC; - KlC=-----7>-(--KlC<--7)==-LAbgurVa2R; - } - } - int a=Ij<=-KlC; - if(Ij) { - int r1W=a!=-false; - } - else { - arg=56>=Ij; - while(54) break; - arg=8>=-(a<--Ij)/a>=-a-KlC; - } - int Yt_T=KlC; - arg=KlC; - } + @Test public void testIndependentField() { + var stop = new Parser(""" + struct S { int x; int y; } + S s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().iterate(); + assertEquals("return 42;",stop.toString()); + assertEquals(42L,Evaluator.evaluate(stop,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var stop = new Parser(""" + struct S { int x; int y; int z; } + S a = new S; S b = new S; + S p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().iterate(); + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a=3); + assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + + @Test public void testLateSliceWorklist() throws ReflectiveOperationException { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var parser = new Parser(Chapter10Test.NESTED_MEMORY); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + var stop = parser.parse().iterate(); + assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); } - if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg; - else if(----arg) continue; - if(-arg-arg) { - arg=-(-arg)*--(-3)<(-7==-arg----arg); - { - int arg=arg; - while(arg<-0>arg==-arg-(-arg>1+11)) { - arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg; - } - } - arg=-arg+arg; - arg=--47+-arg<1>arg*(-arg==-arg--0>3); - arg=(----arg)!=arg+--59; - arg=--4+arg==-(arg)-arg; - } - else { - while(--true-----true*-25+-18>arg>=-----(-arg)---13) { - arg=-0+--true=--0))<=-0/-arg; - int L=-arg; - int B4mHcrf=---vzXB; - int oZWGdzZl=-o3ypEsewxM; - int K6tQqa1=11; - while(0!=--L) { - int sdZfTM=vzXB*true+K6tQqa1; - while(sdZfTMfalse); - sdZfTM=vzXB; - } - } - L=false; - while(31) B4mHcrf=arg; - oZWGdzZl=-0<--oZWGdzZl<=--2; - if(K6tQqa1>=20<=46) { - if(-1+-L) if(oZWGdzZl) { - int wmhv=-----0; - } - int arg=0; - o3ypEsewxM=---(oZWGdzZl); - return -oZWGdzZl/0; - } - else if(arg) { - int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM; - return -K6tQqa1; - } - else { - if(---0) { - {} - {} - } - return o3ypEsewxM; - } -} -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString()); - } - - - @Test - public void testPrimes() { - Parser parser = new Parser( -""" -if( arg < 2 ) return 0; -int primeCount = 1; -int prime = 3; -while( prime <= arg ) { - int isPrime = 1; - // Check for even case, so the next loop need only check odds - if( (prime/2)*2 == prime ) - continue; - // Check odds up to sqrt of prime - int j = 3; - while( j*j <= prime ) { - if( (prime/j)*j == prime ) { - isPrime = 0; - break; - } - j = j + 2; - } - if( isPrime ) - primeCount = primeCount + 1; - prime = prime + 2; -} -return primeCount; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop20,1,Phi(Region82,Phi_primeCount,Phi(Region77,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below - assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2 - assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3 - assertEquals(2L, Evaluator.evaluate(stop, 4)); // 2, 3 - assertEquals(3L, Evaluator.evaluate(stop, 5)); // 2, 3, 5 - assertEquals(4L, Evaluator.evaluate(stop, 10)); // 2, 3, 5, 7 - } - - @Test - public void testAntiDeps1() { - Parser parser = new Parser( -""" -struct S { int f; } -S v=new S; -v.f = 2; -int i=new S.f; -i=v.f; -if (arg) v.f=1; -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps2() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = 0; -if (arg) { - if (arg+1) v = t; - i = v.f; -} else { - v.f = 2; -} -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,.f,0);", stop.toString()); - } - - @Test - public void testAntiDeps3() { - Parser parser = new Parser( -""" -struct S { int f; } -S v0 = new S; -S? v1; -if (arg) v1 = new S; -if (v1) { - v0.f = v1.f; -} else { - v0.f = 2; -} -return v0; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - - @Test - public void testAntiDeps4() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = v.f; -if (arg+1) arg= 0; -while (arg) v.f = 2; -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps5() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -while(1) { - while(arg+1) { arg=arg-1; } - if (arg) break; - v.f = 2; -} -return v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - @Test - public void testAntiDeps6() { - Parser parser = new Parser( -""" -struct s { int v; } -s ptr=new s; -while( -arg ) - ptr = new s; -while(1) - arg = arg+ptr.v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); - } - - @Test - public void testAntiDeps7() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -int i = v.f; -while (arg) { - v.f = arg; - arg = arg-1; -} -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); - } - - @Test - public void testAntiDeps8() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -while(arg) { - arg=arg-1; - int f = v.f; - v.f = 2; - if (arg) arg = f; - else v.f = 3; -} -return arg; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,arg,Phi(Region39,.f,0));", stop.toString()); - } - - @Test - public void testAntiDeps9() { - Parser parser = new Parser( -""" -struct S { int f; } -S v = new S; -S t = new S; -if (arg) { - v.f=2; - int i=t.f; - v.f=i; -} -return v; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); - } - - @Test - public void testExample2() { - Parser parser = new Parser( - """ -struct S { int f; } -S v = new S; -int i = arg; -while (arg > 0) { - int j = i/3; - if (arg == 5) - v.f = j; - arg = arg - 1; -} -return v; - """); - StopNode stop = parser.parse().iterate(); - //assertEquals("return new S;", stop.toString()); - } - - @Test - public void testSplit() { - Parser parser = new Parser( - """ -struct S { int f; } -S s = new S; -if( arg==0 ) s.f = 1; -else if (arg == 1) s.f = 1; -return s.f; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region41,1,Phi(Region36,1,0));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java index e577c8c3..0d4f3c97 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -2,84 +2,199 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.type.TypeMemPtr; +import org.junit.Ignore; import org.junit.Test; - - import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertSame; public class Chapter12Test { - @Test public void testSubZeroFloat() { - var stop = new Parser("flt x = arg; return 0-x;").parse().iterate(); - // Compare strings so +0.0 and -0.0 remain distinct. - assertEquals("0.0", Evaluator.evaluate(stop,0).toString()); - assertEquals("-1.0", Evaluator.evaluate(stop,1).toString()); + + @Test + public void testLinkedList0() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; } +LLI? head = null; +while( arg ) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +return head.next.i; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } } - @Test public void testDeadNumericReturns() { - for( String[] test : new String[][] { - {"if(1) return 7; else return 2.5;", "7"}, - {"if(0) return 7; else return 2.5;", "2.5"}, - {"return 7; return 2.5;", "7"}, - {"return 2.5; return 7;", "2.5"} - } ) { - String src = test[0]; - var stop = new Parser(src).parse().iterate(); - assertEquals(src,test[1],com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); - } + @Test + public void testLinkedList1() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; } +LLI? head = null; +while( arg ) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 3)); } + @Test + public void testCoRecur() { + Parser parser = new Parser( +""" +struct Left { int i; Right? f; } +struct Right { int f; Left? i; } +Left left = new Left; +left.i = 17; +Right right = new Right; +right.f = 314; +left.f = right; +right.i = left; +return right.i.f.i.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 17;", stop.toString()); + } @Test - public void testJig() { + public void testNullReright() { Parser parser = new Parser( """ -return 3.14; +struct N { N next; int i; } +N n = new N; +return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + assertEquals("return null;", stop.toString()); } @Test - public void testFloat() { + public void testNullRef1() { Parser parser = new Parser( """ -return 3.14; +struct N { N next; int i; } +N n = new N; +n.next = new N; +return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + assertEquals("return new N;", stop.toString()); } @Test - public void testSquareRoot() { + public void testNullRef2() { Parser parser = new Parser( """ -flt guess = arg; -while( 1 ) { - flt next = (arg/guess + guess)/2; - if( next == guess ) break; - guess = next; -} -return guess; +struct N { N next; int i; } +N n = new N; +n.next = null; +return n.next; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); } + } + + + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + + @Test + public void testEmpty() { + Parser parser = new Parser( +""" +struct S{}; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); - assertEquals(3.0, Evaluator.evaluate(stop, 9)); - assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2)); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testForwardReright() { + Parser parser = new Parser( +""" +struct S1 { S2 s; } +return new S2; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } } @Test - public void testFPOps() { + public void testForwardRef1() { Parser parser = new Parser( """ -flt x = arg; -return x+1==x; +struct S1 { S2? s; } +struct S2 { int x; } +return new S1.s=new S2; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 1)); + assertEquals("return new S1;", stop.toString()); } + @Test + public void testcheckNull() { + Parser parser = new Parser( +""" +struct I {int i;} +struct P {I pi;} +P p1 = new P; +P p2 = new P; +p2.pi = new I; +p2.pi.i = 2; +if (arg) p1 = new P; +return p1.pi.i + 1; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + } + + + @Test + public void testShallowRecursiveType() { + new Parser("struct LLI { LLI? next; int i; } return 0;").parse().iterate(); + TypeStruct l1 = (TypeStruct)Parser.TYPES.get("LLI"); + TypeStruct l0 = ((TypeMemPtr)l1._fields[0]._type)._obj; + assertEquals("LLI", l0._name); + assertNull(l0._fields); + assertEquals(2, l1._fields.length); + assertSame(l0, l1.meet(l0)); + assertSame(l0, l0.dual()); + assertSame(l0, l0.glb()); + } + + @Test + public void testUnusedForwardReference() { + StopNode stop = new Parser("struct Holder { Missing? ref; } Holder h = new Holder; return h.ref;") + .parse().iterate(); + assertEquals("return null;", stop.toString()); + assertNull(((TypeStruct)Parser.TYPES.get("Missing"))._fields); + } } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 52c2a014..019140ad 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -29,8 +29,8 @@ public class FuzzerWrap { fuzzer.fuzzPeepsRegression(seed); } - @Ignore @Test + @Ignore public void fuzzPeepsLarge() { var fuzzer = new Fuzzer(); for (int i=0; i<1000000; i++) diff --git a/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java index f9c580cc..298fc6f8 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -36,9 +36,9 @@ public class TypeTest { Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(TypeMem.BOT, m1.glb()); + Assert.assertEquals(m1, m1.glb()); Assert.assertEquals(m1, m1.dual()); - Assert.assertEquals(TypeMem.TOP, m1.glb().dual()); + Assert.assertEquals(m1, m1.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 40a2f78d..ac7c5e09 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -2,7 +2,10 @@ package com.seaofnodes.simple.evaluator; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.type.Field; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMemPtr; +import com.seaofnodes.simple.type.TypeStruct; import java.lang.invoke.MethodHandle; import java.lang.invoke.MethodHandles; @@ -77,10 +80,6 @@ public class Evaluator { long in2 = vall(div.in(2)); return in2 == 0 ? 0 : vall(div.in(1)) / in2; } - private double div(DivFNode div) { - double in2 = vald(div.in(2)); - return in2 == 0 ? 0 : vald(div.in(1)) / in2; - } private Object alloc(NewNode alloc) { var type = ((TypeMemPtr)alloc.compute())._obj; @@ -116,16 +115,10 @@ public class Evaluator { if (v instanceof Number n) return n.longValue(); throw new AssertionError("Not a long " + v); } - private double vald(Node node) { - var v = val(node); - if (v instanceof Number n) return n.doubleValue(); - throw new AssertionError("Not a double " + v); - } private Object cons(ConstantNode cons) { var type = cons.compute(); if (type instanceof TypeInteger i) return i.value(); - if (type instanceof TypeFloat i) return i.value(); assert type instanceof TypeMemPtr; return null; } @@ -134,30 +127,20 @@ public class Evaluator { return switch (node) { case ConstantNode cons -> cons(cons); case AddNode add -> vall(add.in(1)) + vall(add.in(2)); - case AddFNode add -> vald(add.in(1)) + vald(add.in(2)); - case BoolNode.EQF eq -> vald(eq.in(1)) == vald(eq.in(2)) ? 1L : 0L; - case BoolNode.LEF le -> vald(le.in(1)) <= vald(le.in(2)) ? 1L : 0L; - case BoolNode.LTF lt -> vald(lt.in(1)) < vald(lt.in(2)) ? 1L : 0L; case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; case BoolNode.LE le -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L; case BoolNode.LT lt -> vall(lt.in(1)) < vall(lt.in(2)) ? 1L : 0L; case DivNode div -> div(div); - case DivFNode div -> div(div); case MinusNode minus -> -vall(minus.in(1)); - case MinusFNode minus -> -vald(minus.in(1)); case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2)); - case MulFNode mul -> vald(mul.in(1)) * vald(mul.in(2)); case NotNode not -> isTrue(val(not.in(1))) ? 0L : 1L; case SubNode sub -> vall(sub.in(1)) - vall(sub.in(2)); - case SubFNode sub -> vald(sub.in(1)) - vald(sub.in(2)); case CastNode cast -> val(cast.in(1)); - case ToFloatNode cast -> (double)vall(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); - case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; - case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; + case ProjNode proj -> ((Object[])val(proj.ctrl()))[proj._idx]; default -> throw new AssertionError("Unexpected node " + node); }; } diff --git a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index d16f4300..48ac0562 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -164,7 +164,7 @@ public class Scheduler { * @return true if the node is not XCtrl. */ private static boolean isNotXCtrl(Node node) { - return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL) && !(node instanceof XCtrlNode); + return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL); } /** @@ -215,7 +215,7 @@ public class Scheduler { private void refinePlacement(NodeData data, BasicBlock block) { assert !isPinnedNode(data); data.block = data.block == null ? block : dom(data.block, block); - assert isValid(data); + assert isValid(data) : data.node.uniqueName()+" at "+data.block.entry.uniqueName(); } /** @@ -328,8 +328,6 @@ public class Scheduler { for(int i=1; id.block==null).orElse(false)) return false; } - } else if (node instanceof XCtrlNode) { - return false; } else { assert d(node.in(0)).block != null; } @@ -405,7 +403,7 @@ public class Scheduler { } } if (!(node instanceof ReturnNode)) - for (Node n:node._outputs) if (n!=null && n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + for (Node n:node._outputs) if (n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); var b = block; for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b)); } @@ -451,7 +449,7 @@ public class Scheduler { node = data.node; assert node.isCFG(); if (!(node instanceof ReturnNode)) { - for (var out : node._outputs) if (out!=null && out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); + for (var out : node._outputs) if (out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false); } @@ -505,7 +503,7 @@ public class Scheduler { */ private static Node findSingleCFGOut(Node node) { if (node instanceof StartNode) { - for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p; + for(var n:node._outputs) if (n instanceof ProjNode p && p._idx==0) return p; return null; } assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1; @@ -572,7 +570,7 @@ public class Scheduler { switch(block.exit) { case null: break; case IfNode i: - for(var out:i._outputs) if (out instanceof CProjNode p) block.next[p._idx] = blocks.get(p); + for(var out:i._outputs) if (out instanceof ProjNode p) block.next[p._idx] = blocks.get(p); break; case RegionNode r: block.next[0] = blocks.get(r); diff --git a/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index b8437b50..14baadba 100644 --- a/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter12/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -3,9 +3,7 @@ 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; +import java.util.*; import java.util.function.Predicate; /** @@ -70,11 +68,10 @@ public class ScriptGenerator { private static class TypeStruct extends Type { record Field (String name, Type type, TypeStruct struct) {} - final Field[] fields; + Field[] fields; final TypeNullable nullable = new TypeNullable(this); - TypeStruct(String name, Field[] fields) { + TypeStruct(String name) { super(name); - this.fields = fields; } boolean isa(Type other) { return this == other || other == nullable; } } @@ -90,21 +87,7 @@ public class ScriptGenerator { } - private static final Type TYPE_FLT = new Type("flt"); - - private static class TypeInt extends Type { - - TypeInt() { - super("int"); - } - - @Override - boolean isa(Type other) { - return super.isa(other) || other == TYPE_FLT; - } - } - - private static final Type TYPE_INT = new TypeInt(); + private static final Type TYPE_INT = new Type("int"); private static class Variable { @@ -158,6 +141,10 @@ public class ScriptGenerator { * All defined structs. */ private final ArrayList structs = new ArrayList<>(); + /** + * All forward declared structs + */ + private final ArrayList forwardStructs = new ArrayList<>(); /** * Allow to declare structs. */ @@ -301,6 +288,7 @@ public class ScriptGenerator { for (var s:structs) { if (s.name.equals(name)) return s; } + for (var s:forwardStructs) if (s.name.equals(name)) return s; return null; } @@ -333,12 +321,18 @@ public class ScriptGenerator { return v; } + private T randFromList(List list) { + return list.get(random.nextInt(list.size())); + } + /** * Get a random structure name * @return A random structure name */ private String getStructName() { - if (!structs.isEmpty() && generateInvalid()) return structs.get(random.nextInt(structs.size())).name; + if (!structs.isEmpty() && generateInvalid()) return randFromList(structs).name; + if (!forwardStructs.isEmpty() && generateInvalid()) return randFromList(forwardStructs).name; + // Generate a new random struct name StringBuilder sb = getRandomName(); var v = sb.toString(); @@ -357,16 +351,26 @@ public class ScriptGenerator { * Get a random type * @return A random type */ - private Type getType() { + private Type getType(boolean allowForward) { int t = random.nextInt(10); if( t<5 || structs.isEmpty() ) return TYPE_INT; - if( t<7 ) return TYPE_FLT; - var idx = random.nextInt(structs.size()); - TypeStruct struct = structs.get(idx); + if (allowForward && random.nextInt(10)==0) { + int i=random.nextInt(forwardStructs.size()+1); + if (i>0) return forwardStructs.get(i-1).nullable; + var name = getStructName(); + var struct = new TypeStruct(name); + forwardStructs.add(struct); + return struct.nullable; + } + TypeStruct struct = randFromList(structs); if (random.nextBoolean()) return struct.nullable; return struct; } + private Type getType() { + return getType(false); + } + /** * 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. @@ -426,19 +430,28 @@ public class ScriptGenerator { * @return 0 */ public int genStruct() { - var name = getStructName(); + int idx = random.nextInt(forwardStructs.size()+10); + TypeStruct struct; + if (idx < 10) { + var name = getStructName(); + struct = new TypeStruct(name); + forwardStructs.add(struct); + } else { + struct = forwardStructs.get(idx-10); + } var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)]; - var struct = new TypeStruct(name, fields); - sb.append("struct ").append(name).append(" {\n"); + sb.append("struct ").append(struct.name).append(" {\n"); indentation += INDENTATION; for (int i=0; i sb.append("true"); case 1 -> sb.append("false"); default -> sb.append(random.nextInt(1<<(rand-2))); } - } else if (type == TYPE_FLT) { - sb.append(random.nextFloat()); + } else if (type instanceof TypeNullable n) { - if (random.nextBoolean()) { + if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) { sb.append("null"); } else { sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name); -- cgit v1.2.3