From 84a70fd744f83e2d701e15fc3d17109eb59ac707 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Nov 2024 11:01:47 -0800 Subject: Chapter 18: Functions and Calls MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- .../java/com/seaofnodes/simple/BrainFuckTest.java | 21 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 34 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 42 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 29 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 124 +++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 79 +-- .../java/com/seaofnodes/simple/Chapter06Test.java | 116 +++-- .../java/com/seaofnodes/simple/Chapter07Test.java | 100 ++-- .../java/com/seaofnodes/simple/Chapter08Test.java | 87 ++-- .../java/com/seaofnodes/simple/Chapter09Test.java | 135 +++-- .../java/com/seaofnodes/simple/Chapter10Test.java | 207 ++++---- .../java/com/seaofnodes/simple/Chapter11Test.java | 23 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 147 ++++-- .../java/com/seaofnodes/simple/Chapter13Test.java | 103 ++-- .../com/seaofnodes/simple/Chapter14FloatTest.java | 50 +- .../java/com/seaofnodes/simple/Chapter14Test.java | 121 +++-- .../java/com/seaofnodes/simple/Chapter15Test.java | 164 +++--- .../java/com/seaofnodes/simple/Chapter16Test.java | 80 +-- .../java/com/seaofnodes/simple/Chapter17aTest.java | 48 +- .../java/com/seaofnodes/simple/Chapter17bTest.java | 431 ++++++++-------- .../java/com/seaofnodes/simple/Chapter18Test.java | 551 +++++++++++++++++++++ .../seaofnodes/simple/CompoundAssignmentTest.java | 25 +- src/test/java/com/seaofnodes/simple/Eval2.java | 454 +++++++++++++++++ .../java/com/seaofnodes/simple/FuzzerWrap.java | 9 +- .../java/com/seaofnodes/simple/MergeSortTest.java | 65 +++ .../java/com/seaofnodes/simple/MutabilityTest.java | 17 +- .../java/com/seaofnodes/simple/SchedulerTest.java | 18 +- src/test/java/com/seaofnodes/simple/TypeTest.java | 45 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 64 +-- .../com/seaofnodes/simple/evaluator/Scheduler.java | 96 ++-- .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 50 +- .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 11 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 3 +- 33 files changed, 2352 insertions(+), 1197 deletions(-) create mode 100644 src/test/java/com/seaofnodes/simple/Chapter18Test.java create mode 100644 src/test/java/com/seaofnodes/simple/Eval2.java create mode 100644 src/test/java/com/seaofnodes/simple/MergeSortTest.java (limited to 'src/test/java') diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 154b74a2..37ecde1c 100644 --- a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -1,12 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; -import org.junit.Test; -import org.junit.Ignore; - import java.nio.charset.StandardCharsets; - +import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -21,9 +17,10 @@ public class BrainFuckTest { encoded.append("program[").append(i).append("] = ").append(value).append(";"); } - Parser parser = new Parser( + CodeGen code = new CodeGen( encoded + """ -var d = 0; + +int d = 0; u8[] !output = new u8[0]; u8[] !data = new u8[100]; @@ -41,14 +38,14 @@ for( int pc = 0; pc < program#; pc++ ) { // Output a byte; increase the output array size var old = output; output = new u8[output# + 1]; - for( var i = 0; i < old#; i++ ) + for( int i = 0; i < old#; i++ ) output[i] = old[i]; output[old#] = data[d]; // Add the extra byte on the end } else if (command == 44) { data[d] = 42; } else if (command == 91) { if (data[d] == 0) { - for( var d = 1; d > 0; ) { + for( int d = 1; d > 0; ) { command = program[++pc]; if (command == 91) d++; if (command == 93) d--; @@ -56,7 +53,7 @@ for( int pc = 0; pc < program#; pc++ ) { } } else if (command == 93) { if (data[d]) { - for( var d = 1; d > 0; ) { + for( int d = 1; d > 0; ) { command = program[--pc]; if (command == 93) d++; if (command == 91) d--; @@ -66,7 +63,7 @@ for( int pc = 0; pc < program#; pc++ ) { } return output; """); - StopNode stop = parser.parse().iterate(); - assertEquals("Hello World!\n", Evaluator.evaluate(stop, 0, 10000).toString()); + code.parse().opto().typeCheck().GCM(); + assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index f7524c17..934eda76 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -10,15 +10,10 @@ 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 CProjNode); - Node expr = ret.expr(); + CodeGen code = new CodeGen("return 1;").parse(); + Node expr = code.expr(); if( expr instanceof ConstantNode con ) { - assertEquals(start,con.in(0)); + assertEquals(code._start,con.in(0)); assertEquals(TypeInteger.constant(1), con._type); } else { fail(); @@ -27,10 +22,9 @@ public class Chapter01Test { @Test public void testZero() { - Parser parser = new Parser("return 0;"); - parser.parse(); - StartNode start = Parser.START; - for( Node use : start._outputs ) + CodeGen code = new CodeGen("return 0;"); + code.parse(); + for( Node use : code._start._outputs ) if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) assertEquals(TypeInteger.constant(0),con._type); } @@ -38,7 +32,7 @@ public class Chapter01Test { @Test public void testBad1() { try { - new Parser("ret").parse(); + new CodeGen("ret;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Undefined name 'ret'",e.getMessage()); @@ -48,7 +42,7 @@ public class Chapter01Test { @Test public void testBad2() { try { - new Parser("return 0123;").parse(); + new CodeGen("return 0123;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); @@ -58,13 +52,13 @@ public class Chapter01Test { @Test public void testNotBad3() { // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return - -12;").parse().print()); + assertEquals("return 12;", new CodeGen("return - -12;").parse()._stop.print()); } @Test public void testBad4() { try { - new Parser("return 100").parse(); + new CodeGen("return 100").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Syntax error, expected ;: ",e.getMessage()); @@ -74,13 +68,13 @@ public class Chapter01Test { @Test public void testNotBad5() { // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); + assertEquals("return -100;", new CodeGen("return -100;").parse()._stop.print()); } @Test public void testBad6() { try { - new Parser("return100").parse(); + new CodeGen("return100;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Undefined name 'return100'",e.getMessage()); @@ -90,10 +84,10 @@ public class Chapter01Test { @Test public void testBad7() { try { - new Parser("return 1;}").parse(); + new CodeGen("return 1;}").parse(); fail(); } catch( RuntimeException e ) { - assertEquals("Syntax error, unexpected }",e.getMessage()); + assertEquals("Syntax error, unexpected: }",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index a6075b75..8b7a2f66 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -10,51 +10,51 @@ public class Chapter02Test { @Test public void testParseGrammar() { - Parser parser = new Parser("return 1+2*3+-5;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); + CodeGen code = new CodeGen("return 1+2*3+-5;"); + code.parse(); + assertEquals("return 2;", code.print()); } @Test public void testAddPeephole() { - Parser parser = new Parser("return 1+2;"); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.print()); + CodeGen code = new CodeGen("return 1+2;"); + code.parse(); + assertEquals("return 3;", code.print()); } @Test public void testSubPeephole() { - Parser parser = new Parser("return 1-2;"); - StopNode ret = parser.parse(); - assertEquals("return -1;", ret.print()); + CodeGen code = new CodeGen("return 1-2;"); + code.parse(); + assertEquals("return -1;", code.print()); } @Test public void testMulPeephole() { - Parser parser = new Parser("return 2*3;"); - StopNode ret = parser.parse(); - assertEquals("return 6;", ret.print()); + CodeGen code = new CodeGen("return 2*3;"); + code.parse(); + assertEquals("return 6;", code.print()); } @Test public void testDivPeephole() { - Parser parser = new Parser("return 6/3;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); + CodeGen code = new CodeGen("return 6/3;"); + code.parse(); + assertEquals("return 2;", code.print()); } @Test public void testMinusPeephole() { - Parser parser = new Parser("return 6/-3;"); - StopNode ret = parser.parse(); - assertEquals("return -2;", ret.print()); + CodeGen code = new CodeGen("return 6/-3;"); + code.parse(); + assertEquals("return -2;", code.print()); } @Test public void testExample() { - Parser parser = new Parser("return 1+2*3+-5;"); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); + CodeGen code = new CodeGen("return 1+2*3+-5;"); + code.parse(); + assertEquals("return 2;", code.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index f06e5dcf..409e23ed 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -1,7 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -10,36 +8,35 @@ 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()); + CodeGen code = new CodeGen("int a=1; return a;"); + code.parse(); assertEquals("return 1;", code.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()); + CodeGen code = new CodeGen("int a=1; int b=2; return a+b;"); + code.parse(); + assertEquals("return 3;", code.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()); + CodeGen code = new CodeGen("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + code.parse(); + assertEquals("return 4;", code.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); "); - StopNode ret = parser.parse(); - assertEquals("return 8;", ret.print()); + CodeGen code = new CodeGen("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); "); + code.parse(); + assertEquals("return 8;", code.print()); } @Test public void testSelfAssign() { try { - new Parser("int a=a; return a;").parse(); + new CodeGen("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Undefined name 'a'",e.getMessage()); @@ -59,7 +56,7 @@ public class Chapter03Test { @Test public void testBad1() { try { - new Parser("int a=1; int b=2; int !c=0; { int b=3; c=a+b;").parse(); + new CodeGen("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/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 36727a8f..d2260e1f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; +import org.junit.Ignore; import static org.junit.Assert.*; @@ -10,133 +11,130 @@ public class Chapter04Test { @Test public void testPeephole() { - Parser parser = new Parser("return 1+arg+2; "); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); + CodeGen code = new CodeGen("return 1+arg+2; "); + code.parse(); + assertEquals("return (arg+3);", code.print()); } @Test public void testPeephole2() { - Parser parser = new Parser("return (1+arg)+2;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); + CodeGen code = new CodeGen("return (1+arg)+2;"); + code.parse(); + assertEquals("return (arg+3);", code.print()); } @Test public void testAdd0() { - Parser parser = new Parser("return 0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); + CodeGen code = new CodeGen("return 0+arg;"); + code.parse(); + assertEquals("return arg;", code.print()); } @Test public void testAddAddMul() { - Parser parser = new Parser("return arg+0+arg;"); - StopNode ret = parser.parse(); - assertEquals("return (arg*2);", ret.print()); + CodeGen code = new CodeGen("return arg+0+arg;"); + code.parse(); + assertEquals("return (arg*2);", code.print()); } @Test public void testPeephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3; "); - StopNode ret = parser.parse(); - assertEquals("return ((arg*2)+6);", ret.print()); + CodeGen code = new CodeGen("return 1+arg+2+arg+3; "); + code.parse(); + assertEquals("return ((arg*2)+6);", code.print()); } @Test public void testMul1() { - Parser parser = new Parser("return 1*arg;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); + CodeGen code = new CodeGen("return 1*arg;"); + code.parse(); + assertEquals("return arg;", code.print()); } @Test public void testSub0() { - Parser parser = new Parser("return arg-0;"); - StopNode ret = parser.parse(); - assertEquals("return arg;", ret.print()); + CodeGen code = new CodeGen("return arg-0;"); + code.parse(); + assertEquals("return arg;", code.print()); } @Test public void test0Sub() { - Parser parser = new Parser("return 0-arg;"); - StopNode ret = parser.parse(); - assertEquals("return (-arg);", ret.print()); + CodeGen code = new CodeGen("return 0-arg;"); + code.parse(); + assertEquals("return (-arg);", code.print()); } @Test public void testSubNeg() { - Parser parser = new Parser("return 3--arg;"); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); + CodeGen code = new CodeGen("return 3--arg;"); + code.parse(); + assertEquals("return (arg+3);", code.print()); } @Test public void testNegSub() { - Parser parser = new Parser("return -arg-3;"); - StopNode ret = parser.parse(); - assertEquals("return (-(arg+3));", ret.print()); + CodeGen code = new CodeGen("return -arg-3;"); + code.parse(); + assertEquals("return (-(arg+3));", code.print()); } @Test public void testVarArg() { - Parser parser = new Parser("return arg; "); - StopNode stop = parser.parse(); - ReturnNode ret = stop.ret(); - assertTrue(ret.in(0) instanceof CProjNode); - assertTrue(ret.in(1) instanceof ProjNode); - assertEquals(1, ((ProjNode)ret.in(1))._idx); - assertTrue(ret.in(2) instanceof ProjNode); - assertEquals(2, ((ProjNode)ret.in(2))._idx); + CodeGen code = new CodeGen("return arg; "); + code.parse(); + assertTrue(code.ctrl() instanceof FunNode); + assertTrue(code.expr() instanceof ParmNode); } - @Test + // Adding functions means `main` does not constant fold the incoming arg value + @Ignore @Test public void testConstantArg() { - Parser parser = new Parser("return arg; ", TypeInteger.constant(2)); - StopNode ret = parser.parse(); - assertEquals("return 2;", ret.print()); + CodeGen code = new CodeGen("return arg; ", TypeInteger.constant(2)); + code.parse(); + assertEquals("return 2;", code.expr().in(1).toString()); } @Test public void testCompEq() { - Parser parser = new Parser("return 3==3; "); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); + CodeGen code = new CodeGen("return 3==3; "); + code.parse(); + assertEquals("return 1;", code.print()); } @Test public void testCompEq2() { - Parser parser = new Parser("return 3==4; "); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); + CodeGen code = new CodeGen("return 3==4; "); + code.parse(); + assertEquals("return 0;", code.print()); } @Test public void testCompNEq() { - Parser parser = new Parser("return 3!=3; "); - StopNode ret = parser.parse(); - assertEquals("return 0;", ret.print()); + CodeGen code = new CodeGen("return 3!=3; "); + code.parse(); + assertEquals("return 0;", code.print()); } @Test public void testCompNEq2() { - Parser parser = new Parser("return 3!=4; "); - StopNode ret = parser.parse(); - assertEquals("return 1;", ret.print()); + CodeGen code = new CodeGen("return 3!=4; "); + code.parse(); + assertEquals("return 1;", code.print()); } @Test public void testBug1() { - Parser parser = new Parser("int a=arg+1; int !b=a; b=1; return a+2; "); - StopNode ret = parser.parse(); - assertEquals("return (arg+3);", ret.print()); + CodeGen code = new CodeGen("int a=arg+1; int !b=a; b=1; return a+2; "); + code.parse(); + assertEquals("return (arg+3);", code.print()); } @Test public void testBug2() { - Parser parser = new Parser("int !a=arg+1; a=a; return a; "); - StopNode ret = parser.parse(); - assertEquals("return (arg+1);", ret.print()); + CodeGen code = new CodeGen("int !a=arg+1; a=a; return a; "); + code.parse(); + assertEquals("return (arg+1);", code.print()); } @Test @@ -151,9 +149,9 @@ public class Chapter04Test { @Test public void testBug4() { - Parser parser = new Parser("return -arg;"); - StopNode ret = parser.parse(); - assertEquals("return (-arg);", ret.print()); + CodeGen code = new CodeGen("return -arg;"); + code.parse(); + assertEquals("return (-arg);", code.print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 7ea75f49..ff60c695 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -10,7 +9,7 @@ public class Chapter05Test { @Test public void testIfStmt() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; if (arg == 1) @@ -20,13 +19,13 @@ else { } return a; """); - StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region,(arg+2),(arg-3));", ret.toString()); + code.parse().opto(); + assertEquals("return Phi(Region,(arg+2),(arg-3));", code.print()); } @Test public void testTest() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int c = 3; int b = 2; @@ -34,27 +33,28 @@ if (arg == 1) { b = 3; c = 4; } -return c;""", TypeInteger.BOT); - StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region,4,3);", ret.toString()); +return c; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,4,3);", code.print()); } @Test public void testReturn2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ if( arg==1 ) return 3; else return 4; -""", TypeInteger.BOT); - StopNode stop = parser.parse(); - assertEquals("Stop[ return 3; return 4; ]", stop.toString()); +"""); + code.parse(); + assertEquals("return Phi(Region,3,4);", code.print()); } @Test public void testIfMergeB() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=arg+1; int b=0; @@ -63,13 +63,13 @@ if( arg==1 ) else b=a+1; return a+b;"""); - StopNode ret = parser.parse().iterate(); - assertEquals("return ((arg*2)+Phi(Region,2,3));", ret.toString()); + code.parse().opto(); + assertEquals("return ((arg*2)+Phi(Region,2,3));", code.print()); } @Test public void testIfMerge2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=arg+1; int b=arg+2; @@ -78,13 +78,13 @@ if( arg==1 ) else a=b+1; return a+b;"""); - StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + code.parse().opto(); + assertEquals("return ((Phi(Region,(arg*2),arg)+arg)+Phi(Region,4,5));", code.print()); } @Test public void testMerge3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=1; if( arg==1 ) @@ -97,14 +97,14 @@ else if( arg==3 ) else a=5; return a; -""", TypeInteger.BOT); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,Phi(Region,2,3),Phi(Region,4,5));", stop.toString()); +"""); + code.parse().opto(); + assertEquals("return Phi(Region,Phi(Region,2,3),Phi(Region,4,5));", code.print()); } @Test public void testMerge4() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=0; int b=0; @@ -113,28 +113,29 @@ if( arg ) if( arg==0 ) b=2; return arg+a+b; -""", TypeInteger.BOT); - StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region,1,0))+Phi(Region,2,0));", stop.toString()); +"""); + code.parse().opto(); + assertEquals("return ((arg+Phi(Region,1,0))+Phi(Region,2,0));", code.print()); } @Test public void testMerge5() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=arg==2; if( arg==1 ) { a=arg==3; } -return a;"""); - StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region,3,2));", ret.toString()); +return a; +"""); + code.parse().opto(); + assertEquals("return (arg==Phi(Region,3,2));", code.print()); } @Test public void testMergeSameCon() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=arg; if( arg==1 ) @@ -143,23 +144,23 @@ else a=3; return a; """); - StopNode ret = parser.parse(); - assertEquals("return 3;", ret.toString()); + code.parse().opto(); + assertEquals("return 3;", code.print()); } @Test public void testTrue() { StopNode stop = new Parser("return true;").parse(); - assertEquals("return 1;",stop.toString()); + assertEquals("return 1;",stop.ret().print()); } @Test public void testHalfDef() { try { - new Parser("if( arg==1 ) int b=2; return b;").parse(); + new CodeGen("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()); + assertEquals("Cannot define a 'b' on one arm of an if",e.getMessage()); } } @@ -176,10 +177,10 @@ return a; @Test public void testRegress1() { try { - new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + new CodeGen("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()); + assertEquals("Cannot define a 'a' on one arm of an if",e.getMessage()); } } @@ -217,7 +218,7 @@ return a; @Test public void testKeyword3() { try { - new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + new CodeGen("int a=1; ififif(arg);a=2;return a;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Undefined name 'ififif'",e.getMessage()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 50c0580d..2107cdb0 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -10,32 +10,31 @@ public class Chapter06Test { @Test public void testPeepholeReturn() { - Parser parser = new Parser( -""" + CodeGen code = new CodeGen(""" if( true ) return 2; return 1; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertTrue(code.ctrl() instanceof FunNode); } @Test public void testPeepholeRotate() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; if (arg) a = 2; return (arg < a) < 3; // Because (arg < a) is a bool/uint1/[0-1], its always less than 3 """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); + code.parse().opto(); + assertEquals("return 1;", code.print()); } @Test public void testPeepholeCFG() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=1; if( true ) @@ -44,14 +43,14 @@ else a=3; return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 2;", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertTrue(code.ctrl() instanceof FunNode); } @Test public void testIfIf() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=1; if( arg!=1 ) @@ -63,14 +62,15 @@ if( a==2 ) b=42; else b=5; -return b;""", TypeInteger.BOT); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,42,5);", stop.toString()); +return b; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,42,5);", code.print()); } @Test public void testIfArgIf() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=1; if( 1==1 ) @@ -82,15 +82,16 @@ if( arg==2 ) b=a; else b=5; -return b;""", TypeInteger.BOT); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,2,5);", stop.toString()); +return b;"""); + code.parse().opto(); + assertEquals("return Phi(Region,2,5);", code.print()); } @Test public void testMerge3With2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ +arg=2; int a=1; if( arg==1 ) if( arg==2 ) @@ -103,14 +104,15 @@ else a=5; return a; """, TypeInteger.constant(2)); - StopNode stop = parser.parse(); - assertEquals("return 5;", stop.toString()); + code.parse().opto(); + assertEquals("return 5;", code.print()); } @Test public void testMerge3With1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ +arg=1; int a=1; if( arg==1 ) if( arg==2 ) @@ -123,13 +125,13 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3;", stop.toString()); + code.parse().opto(); + assertEquals("return 3;", code.print()); } @Test public void testMerge3Peephole() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a=1; if( arg==1 ) @@ -142,15 +144,16 @@ else if( arg==3 ) else a=5; return a; -""", TypeInteger.BOT); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,3,Phi(Region,4,5));", stop.toString()); +"""); + code.parse().opto(); + assertEquals("return Phi(Region,3,Phi(Region,4,5));", code.print()); } @Test public void testMerge3Peephole1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ +arg=1; int a=1; if( arg==1 ) if( 1==2 ) @@ -163,14 +166,15 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3;", stop.toString()); + code.parse().opto(); + assertEquals("return 3;", code.print()); } @Test public void testMerge3Peephole3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ +arg=3; int a=1; if( arg==1 ) if( 1==2 ) @@ -183,13 +187,13 @@ else a=5; return a; """, TypeInteger.constant(3)); - StopNode stop = parser.parse().iterate(); - assertEquals("return 4;", stop.toString()); + code.parse().opto(); + assertEquals("return 4;", code.print()); } @Test public void testDemo1NonConst() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int a = 0; int b = 1; if( arg ) { @@ -199,14 +203,15 @@ if( arg ) { } return a+b; """); - StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region,4,1);", ret.toString()); + code.parse().opto(); + assertEquals("return Phi(Region,4,1);", code.print()); } @Test public void testDemo1True() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" +arg=1; int a = 0; int b = 1; if( arg ) { @@ -216,13 +221,14 @@ if( arg ) { } return a+b; """, TypeInteger.constant(1)); - StopNode ret = parser.parse().iterate(); - assertEquals("return 4;", ret.toString()); + code.parse().opto(); + assertEquals("return 4;", code.print()); } @Test public void testDemo1False() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" +arg=0; int a = 0; int b = 1; if( arg ) { @@ -232,13 +238,13 @@ if( arg ) { } return a+b; """, TypeInteger.constant(0)); - StopNode ret = parser.parse().iterate(); - assertEquals("return 1;", ret.toString()); + code.parse().opto(); + assertEquals("return 1;", code.print()); } @Test public void testDemo2NonConst() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int a = 0; int b = 1; int c = 0; @@ -250,14 +256,15 @@ if( arg ) { } return a+b+c; """); - StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region,Phi(Region,2,3),0)+Phi(Region,3,1));", ret.toString()); + code.parse().opto(); + assertEquals("return (Phi(Region,Phi(Region,2,3),0)+Phi(Region,3,1));", code.print()); } @Test public void testDemo2True() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" +arg=1; int a = 0; int b = 1; int c = 0; @@ -269,13 +276,14 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(1)); - StopNode ret = parser.parse().iterate(); - assertEquals("return 6;", ret.toString()); + code.parse().opto(); + assertEquals("return 6;", code.print()); } @Test public void testDemo2arg2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" +arg=2; int a = 0; int b = 1; int c = 0; @@ -287,8 +295,8 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(2)); - StopNode ret = parser.parse().iterate(); - assertEquals("return 5;", ret.toString()); + code.parse().opto(); + assertEquals("return 5;", code.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index ad3622c9..6d6a3ce7 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -9,21 +9,21 @@ public class Chapter07Test { @Test public void testExample() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while(arg < 10) { arg = arg + 1; } return arg; """); - StopNode stop = parser.parse(); - assertEquals("return Phi(Loop,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse(); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testRegression() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; if(arg){}else{ @@ -33,13 +33,13 @@ if(arg){}else{ } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1,Phi(Loop,1,(Phi_a+1)));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Region,1,Phi(Loop,1,(Phi_a+1)));", code.print()); } @Test public void testWhileNested() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int sum = 0; int i = 0; @@ -53,13 +53,13 @@ while(i < arg) { } return sum; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,0,Phi(Loop,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Loop,0,Phi(Loop,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", code.print()); } @Test public void testWhileScope() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; int b = 2; @@ -69,14 +69,14 @@ while(a < 10) { } return b; """); - StopNode stop = parser.parse(); - assertEquals("return Phi(Loop,2,Phi(Region,Phi_b,4));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse(); + assertEquals("return Phi(Loop,2,Phi(Region,Phi_b,4));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhileNestedIfAndInc() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; int b = 2; @@ -88,15 +88,15 @@ while(a < 10) { } return b; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,2,(Phi(Region,Phi_b,4)+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,2,(Phi(Region,Phi_b,4)+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhile() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; while(a < 10) { @@ -105,14 +105,14 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhilePeep() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; while(a < 10) { @@ -121,40 +121,40 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhile2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; while(arg) a = 2; return a; """); - StopNode stop = parser.parse(); - assertEquals("return Phi(Loop,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse(); + assertEquals("return Phi(Loop,1,2);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhile2Peep() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; while(arg) a = 2; return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,1,2);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,1,2);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhile3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; while(a < 10) { @@ -163,14 +163,14 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhile3Peep() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; while(a < 10) { @@ -179,14 +179,14 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhile4() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; int b = 2; @@ -196,14 +196,14 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testWhile4Peep() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; int b = 2; @@ -213,9 +213,9 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index bb3bd674..03a2c50a 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/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; @@ -11,7 +12,7 @@ public class Chapter08Test { @Test public void testEx6() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while(arg < 10) { arg = arg + 1; @@ -22,17 +23,17 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,Phi(Region,Phi(Loop,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)); + code.parse().opto(); + assertEquals("return Phi(Region,Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); + Assert.assertEquals( "5", Eval2.eval(code, 1)); + Assert.assertEquals("10", Eval2.eval(code, 6)); } @Test public void testEx5() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = 1; while(arg < 10) { @@ -45,15 +46,15 @@ while(arg < 10) { } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,1,Phi(Region,Phi_a,(Phi_a+1)));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,1,Phi(Region,Phi_a,(Phi_a+1)));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testEx4() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while(arg < 10) { arg = arg + 1; @@ -64,14 +65,14 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof RegionNode); + code.parse().opto(); + assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); } @Test public void testEx3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while(arg < 10) { arg = arg + 1; @@ -80,15 +81,15 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof RegionNode); + code.parse().opto(); + assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); } @Test public void testEx2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while(arg < 10) { arg = arg + 1; @@ -99,15 +100,15 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testEx1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while(arg < 10) { arg = arg + 1; @@ -116,14 +117,14 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,arg,(Phi_arg+1));", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test public void testRegress1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while( arg < 10 ) { int a = arg+2; @@ -132,15 +133,15 @@ while( arg < 10 ) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return arg;", stop.toString()); + code.parse().opto(); + assertEquals("return arg;", code.print()); } @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(); - assertEquals("return 0;", stop.toString()); + CodeGen code = new CodeGen("if(1) return 0; else while(arg>- -arg) arg=arg+1; return 0;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test @@ -161,19 +162,19 @@ return arg; @Test public void testRegress3() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" while(arg < 10) { break; } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return arg;", stop.toString()); + code.parse().opto(); + assertEquals("return arg;", code.print()); } @Test public void testRegress4() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int a = 1; while(arg < 10) { a = a + 1; @@ -184,14 +185,14 @@ while(arg < 10) { } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,Phi(Loop,1,(Phi_a+1)),Add);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof RegionNode); + code.parse().opto(); + assertEquals("return Phi(Region,Phi(Loop,1,(Phi_a+1)),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); } @Test public void testRegress5() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int a = 1; while(1) { a = a + 1; @@ -200,9 +201,9 @@ while(1) { } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); + code.parse().opto(); + assertEquals("return (Phi(Loop,1,Add)+1);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode prj && prj._idx==1 ); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index c31afcd6..b210f7e9 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; @@ -15,7 +14,7 @@ public class Chapter09Test { @Test @Ignore public void testJig() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int v0=0; arg=0; while(v0) { @@ -25,12 +24,12 @@ while(v0) { } return 0; """); - StopNode stop = parser.parse().iterate(); + code.parse().opto(); } @Test public void testGVN1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int x = arg + arg; if(arg < 10) { @@ -41,41 +40,37 @@ else { } return x; """); - StopNode stop = parser.parse(); - assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString()); - Assert.assertEquals(2L, Evaluator.evaluate(stop, 1)); - Assert.assertEquals(23L, Evaluator.evaluate(stop, 11)); + code.parse().opto(); + assertEquals("return Phi(Region,(arg*2),(Mul+1));", code.print()); + Assert.assertEquals( "2", Eval2.eval(code, 1)); + Assert.assertEquals("23", Eval2.eval(code, 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(0L, Evaluator.evaluate(stop, 1)); + CodeGen code = new CodeGen("return arg*arg-arg*arg;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); + Assert.assertEquals("0", Eval2.eval(code, 1, 1)); } @Test public void testWorklist1() { - Parser parser = new Parser( - """ + CodeGen code = new CodeGen(""" int step = 1; while (arg < 10) { arg = arg + step + 1; } return arg; - """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,arg,(Phi_arg+2));", stop.toString()); - Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+2));", code.print()); + Assert.assertEquals("11", Eval2.eval(code, 1)); } @Test public void testWorklist2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int cond = 0; int one = 1; @@ -85,14 +80,14 @@ while (arg < 10) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,arg,(Phi_arg+4));", stop.toString()); - Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+4));", code.print()); + Assert.assertEquals("13", Eval2.eval(code, 1)); } @Test public void testWorklist3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int v1 = 0; int v2 = 0; @@ -114,13 +109,13 @@ while (arg) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testRegionPeepBug() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int v0=0; int v1=0; @@ -132,48 +127,48 @@ while(v1+arg) { v1=v2; } """); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testWhile0() { - Parser parser = new Parser("while(0) continue; if(0) arg=0;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + CodeGen code = new CodeGen("while(0) continue; if(0) arg=0;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testWhile1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" if(0) while(0) { int arg=arg; while(0) {} } """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testPrecedence() { - Parser parser = new Parser("return 3-1+2;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 4;", stop.toString()); + CodeGen code = new CodeGen("return 3-1+2;"); + code.parse().opto(); + assertEquals("return 4;", code.print()); } @Test public void testSwap2() { - Parser parser = new Parser("return 1+(1+1);"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3;", stop.toString()); + CodeGen code = new CodeGen("return 1+(1+1);"); + code.parse().opto(); + assertEquals("return 3;", code.print()); } @Test public void testFuzz0() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int one = 1; int a = 0; int zero = 0; @@ -184,13 +179,13 @@ while(arg) { } return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,0,(-(Phi_a+3)));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(-(Phi_a+3)));", code.print()); } @Test public void testFuzz1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" while(1) {} while(arg) break; while(arg) arg=0; @@ -198,40 +193,40 @@ arg=0; int v0=0!=0<-0; return -0+0+0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test public void testFuzz2() { - Parser parser = new Parser("return 0+-0;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + CodeGen code = new CodeGen("return 0+-0;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testFuzz3() { - Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + CodeGen code = new CodeGen("int v0=0; while(0==69) while(v0) return 0;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testFuzz4() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" while(1) { arg=0<=0; if(1<0) while(arg==-0) arg=arg-arg; } """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test public void testFuzz5() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" { int v0=0; while(1) @@ -247,25 +242,25 @@ while(1) { } return 0!=0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test public void testFuzz6() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int v0=0; while(0==1) while(v0) v0=1+v0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return ~int;", code.print()); } @Test public void testFuzz7() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" while(1) {} int v0=0; while(v0) @@ -275,15 +270,15 @@ while(1) v1=1; return v1+v0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test public void testFuzz8() { - Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + CodeGen code = new CodeGen("while(arg) arg = arg - 1; return arg;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index f634e421..bcae373b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,9 +1,8 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; +import org.junit.Test; import com.seaofnodes.simple.node.*; import java.util.BitSet; -import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -14,9 +13,9 @@ public class Chapter10Test { "if(1) return new S; else return 0;" } ) { String src = "struct S { int x; }; " + body; - var stop = new Parser(src).parse().iterate(); + var code = new CodeGen(src).parse().opto().typeCheck(); org.junit.Assert.assertTrue(body, - stop.ret().expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); + code.expr()._type instanceof com.seaofnodes.simple.type.TypeMemPtr); } } @@ -39,9 +38,9 @@ public class Chapter10Test { "if (!!!p) return -1; return p.x;", "int b = !!p; if (b) return p.x + b - 1; return -1;" } ) { - StopNode stop = new Parser(NULLABLE_POINT_SOURCE+body).parse().iterate(); - assertEquals(body,-1L,com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0)); - assertEquals(body,42L,com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1)); + CodeGen code = new CodeGen(NULLABLE_POINT_SOURCE+body).parse().opto().typeCheck(); + assertEquals(body,"-1",Eval2.eval(code,0)); + assertEquals(body,"42",Eval2.eval(code,1)); } } @@ -54,7 +53,7 @@ public class Chapter10Test { "if (!!p) { int x = p.x; } return p.x;" } ) { try { - new Parser(NULLABLE_POINT_SOURCE+body).parse().iterate(); + new CodeGen(NULLABLE_POINT_SOURCE+body).parse().opto().typeCheck(); fail(body); } catch( RuntimeException e ) { // Known null is rejected during parsing in these chapters. @@ -67,7 +66,7 @@ public class Chapter10Test { @Test public void testFuzzer() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int a = arg/3; int b = arg*5; @@ -86,13 +85,13 @@ if( (arg/13)==0 ) { int r = g+h; return p-r; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testStruct() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int a; int b; @@ -106,13 +105,13 @@ bar.a = 1; bar.a = 2; return bar.a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 2;", stop.toString()); + code.parse().opto(); + assertEquals("return 2;", code.print()); } @Test public void testExample() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Vector2D { int x; int y; }; !Vector2D !v = new Vector2D; v.x = 1; @@ -122,36 +121,36 @@ else v.y = 3; return v; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Vector2D;", stop.toString()); + code.parse().opto(); + assertEquals("return Vector2D;", code.print()); } @Test public void testBug() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 { int v0; }; s0? v1=null; int v3=v1.zAicm; """); - try { parser.parse(); fail(); } + try { code.parse(); fail(); } catch( Exception e ) { assertEquals("Accessing unknown field 'zAicm' from 'null'",e.getMessage()); } } @Test public void testBug2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 { int v0; }; arg=0+new s0.0; """); - try { parser.parse(); fail(); } + try { code.parse(); fail(); } catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } } @Test public void testLoop() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int a; }; !Bar !bar = new Bar; while (arg) { @@ -160,65 +159,65 @@ while (arg) { } return bar.a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,0,(Phi_a+2));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(Phi_a+2));", code.print()); } @Test public void testIf() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int a; }; !Bar !bar = new Bar; if (arg) bar = null; bar.a = 1; return bar.a; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("Type null is not of declared type *Bar",e.getMessage()); } } @Test public void testIf2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int a; }; !Bar? !bar = null; if (arg) bar = new Bar; bar.a = 1; return bar.a; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Might be null accessing 'a'",e.getMessage()); } } @Test public void testIf3() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int a; }; Bar bar = null; if (arg) bar = null; bar.a = 1; return bar.a; """); - try { parser.parse(); fail(); } + try { code.parse(); fail(); } catch( Exception e ) { assertEquals("Type null is not of declared type *Bar", e.getMessage()); } } @Test public void testIfOrNull() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int a; }; !Bar? !bar = new Bar; if (arg) bar = null; if( bar ) bar.a = 1; return bar; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,(*void)Phi(Region,null,Bar),null);", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Region,null,Bar);", code.print()); } @Test public void testIfOrNull2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct Bar { int a; }; !Bar? !bar = new Bar; @@ -228,13 +227,13 @@ if( !bar ) rez=4; else bar.a = 1; return rez; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,4,3);", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Region,4,3);", code.print()); } @Test public void testWhileWithNullInside() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 {int v0;}; !s0? !v0 = new s0; int ret = 0; @@ -245,14 +244,14 @@ while(arg) { } return ret; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Might be null accessing 'v0'", e.getMessage()); } } @Test public void testRedeclareStruct() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 { int v0; }; @@ -260,14 +259,14 @@ s0? v1=new s0; !s0? !v1; v1=new s0; """); - try { parser.parse(); fail(); } + try { code.parse(); fail(); } catch( Exception e ) { assertEquals("Redefining name 'v1'", e.getMessage()); } } @Test public void testIter() { // Build and use an iterator - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct Iter { int x; @@ -282,14 +281,14 @@ while( i.x < i.len ) { } return sum; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", code.print()); } @Test public void test1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 {int v0;}; !s0 !ret = new s0; while(arg) { @@ -301,13 +300,13 @@ while(arg) { } return ret; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); } @Test public void test2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 {int v0;}; !s0 !ret = new s0; !s0 !v0 = new s0; @@ -319,14 +318,14 @@ while(arg) { } return ret; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); } @Test public void test3() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 {int v0;}; !s0 !ret = new s0; while(arg < 10) { @@ -336,41 +335,40 @@ while(arg < 10) { } return ret; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); } @Test public void testBug3() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 { int f0; }; return new s0; int v0=null.f0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return s0;", stop.toString()); - assertEquals("Obj{f0=0}", Evaluator.evaluate(stop, 0).toString()); + try { code.parse(); fail(); } + catch( Exception e ) { assertEquals("Accessing unknown field 'f0' from 'null'",e.getMessage()); } } @Test public void testBug4() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" if(0) { while(0) if(arg) continue; int v0=0; while(1) { - int arg=-arg; - v0=arg; + int v2=-arg; + v0=v2; } } """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testBug5() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct s0 { int f0; }; @@ -378,13 +376,13 @@ if(0) return 0; else return new s0; if(new s0.f0) return 0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return s0;", stop.toString()); + code.parse().opto(); + assertEquals("return s0;", code.print()); } @Test public void testBug6MissedWorklist() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" while(0) {} int v4=0; while(0=2 ? 2 : 0), 11L+2*arg-(arg>=2 ? 2 : 0) - }, obj.fields()); + assertEquals("S{x="+(5L+arg)+",y="+(7L+arg*(arg+1)-(arg>=2 ? 2 : 0))+ + ",z="+(11L+2*arg-(arg>=2 ? 2 : 0))+"}",Eval2.eval(code,arg)); } } @Test public void testMemoryAtEarlyReturns() { - var stop = new Parser(""" + var code = new CodeGen(""" struct S { int x; int y; int z; }; !S !s = new S; s.x = 3; s.y = 5; s.z = 7; if (arg) { s.x = 11; s.z = 13; return s; } s.y = 17; return s; - """).parse().iterate(); + """).parse().opto(); + StopNode stop = code._stop; for (int arg=0; arg<2; arg++) { - var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) - com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); - org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields()); + assertEquals(arg==0 ? "S{x=3,y=17,z=7}" : "S{x=11,y=5,z=13}",Eval2.eval(code,arg)); } } @Test public void testKeepLoadsAtMerge() { - StopNode stop = new Parser(""" + var code = new CodeGen(""" struct S { int x; }; !S !a = new S; !S !b = new S; a.x = arg; b.x = arg+1; @@ -524,28 +520,30 @@ return 0; int v; if (arg>1) v=p.x; else v=q.x; return v; - """).parse().iterate(); + """).parse().opto(); + StopNode stop = code._stop; // The one-step safety check stops at the memory aggregate. assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); - assertEquals(-1L,Evaluator.evaluate(stop,-1)); - assertEquals(1L,Evaluator.evaluate(stop,0)); - assertEquals(3L,Evaluator.evaluate(stop,3)); + assertEquals("-1",Eval2.eval(code,-1)); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("3",Eval2.eval(code,3)); } @Test public void testDropStores() { - StopNode stop = new Parser(""" + var code = new CodeGen(""" struct S { int x; }; !S !s = new S; if (arg) s.x=arg+1; else s.x=arg+2; return s; - """).parse().iterate(); + """).parse().opto(); + StopNode stop = code._stop; assertEquals(1,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]); + assertEquals("S{x=2}",Eval2.eval(code,0)); + assertEquals("S{x=4}",Eval2.eval(code,3)); } @Test public void testKeepReadsBeforeWrites() { - StopNode stop = new Parser(""" + var code = new CodeGen(""" struct S { int x; int y; }; !S !a = new S; !S !b = new S; a.x=arg; b.x=arg+1; @@ -555,11 +553,12 @@ return 0; if (arg>1) { v=p.x; p.x=41; p.y=5; } else { v=q.x; q.x=42; } return v; - """).parse().iterate(); + """).parse().opto(); + StopNode stop = code._stop; assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); - assertEquals(-1L,Evaluator.evaluate(stop,-1)); - assertEquals(1L,Evaluator.evaluate(stop,0)); - assertEquals(3L,Evaluator.evaluate(stop,3)); + assertEquals("-1",Eval2.eval(code,-1)); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("3",Eval2.eval(code,3)); } private static int countMemoryNodes(Node n, Class kind, BitSet seen) { diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java index f0caed02..9fd392d2 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,26 +1,26 @@ 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 Chapter11Test { @Test public void testIndependentField() { - var stop = new Parser(""" + var code = new CodeGen(""" 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(); + """).parse().opto(); + var stop = code._stop; assertEquals("return 42;",stop.toString()); - assertEquals(42L,Evaluator.evaluate(stop,5)); + assertEquals("42",Eval2.eval(code,5)); assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); } @Test public void testParallelMemoryPhis() { - var stop = new Parser(""" + var code = new CodeGen(""" struct S { int x; int y; int z; }; !S !a = new S; !S !b = new S; !S !p = a; if (arg) p = b; @@ -31,7 +31,8 @@ public class Chapter11Test { arg = arg - 1; } return a; - """).parse().iterate(); + """).parse().opto(); + var stop = code._stop; int[] phis = {0}; stop.walk(n -> { // Store sinking can replace field memory Phis with value Phis. @@ -40,26 +41,26 @@ public class Chapter11Test { for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) assertTrue(a=4); // Three fields and the loop counter. - assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4)); } @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 code = new CodeGen(Chapter10Test.NESTED_MEMORY).parse(); 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()); + code.opto(); + assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); } } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 628f6211..a15132d4 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,7 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; @@ -11,18 +9,18 @@ public class Chapter12Test { @Ignore @Test public void testJig() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ return 3.14; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test public void testLinkedList0() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct LLI { !LLI? !next; int i; }; !LLI? !head = null; @@ -35,13 +33,13 @@ while( arg ) { } return head.next.i; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } } @Test public void testLinkedList1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct LLI { !LLI? !next; int i; }; !LLI? !head = null; @@ -57,14 +55,14 @@ 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)); + code.parse().opto(); + assertEquals("return Phi(Region,0,1,.i);", code.print()); + assertEquals("2", Eval2.eval(code, 3)); } @Test public void testCoRecur() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct int0 { int i; !flt0? !f; }; struct flt0 { flt f; !int0? !i; }; @@ -76,122 +74,189 @@ i0.f = f0; f0.i = i0; return f0.i.f.i.i; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 17;", stop.toString()); + code.parse().opto(); + assertEquals("return 17;", code.print()); } @Test public void testNullRef0() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct N { !N? !next; int i; }; N n = new N; return n.next; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return null;", stop.toString()); + code.parse().opto(); + assertEquals("return null;", code.print()); } @Test public void testNullRef1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct M { int m; }; struct N { !M !next; int i; }; N n = new N { next = new M; }; return n.next; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return (const)M;", stop.toString()); + code.parse().opto(); + assertEquals("return (const)M;", code.print()); } @Test public void testNullRef2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct M { int m; }; struct N { !M !next; int i; }; N n = new N { next = null; } return n.next; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } } @Test public void testNullRef3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct N { !N? !next; int i; }; !N !n = new N; n.i = 3.14; return n.i; """); - assertEquals("3",com.seaofnodes.simple.evaluator.Evaluator.evaluate(parser.parse().iterate(),0).toString()); + code.parse().opto(); + assertEquals("3",Eval2.eval(code,0)); } @Test public void testNullRef4() { - Parser parser = new Parser("-null-5/null-5;"); - try { parser.parse().iterate(); fail(); } + CodeGen code = new CodeGen("-null-5/null-5;"); + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } } @Test public void testNullRef5() { - Parser parser = new Parser("return null+42;"); - try { parser.parse().iterate(); fail(); } + CodeGen code = new CodeGen("return null+42;"); + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } } @Test public void testEmpty() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S{}; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testForwardRef0() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S1 { !S2? !s; }; return new S2; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } } @Test public void testForwardRef1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S1 { !S2? !s; }; struct S2 { int x; }; return new S1.s=new S2; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return S2;", stop.toString()); + code.parse().opto(); + assertEquals("return S2;", code.print()); } @Test public void testcheckNull() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct I {int i;}; struct P { !I? !pi; }; !P !p1 = new P; -!P !p2 = 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(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } } + @Test + public void testCoRecur2() { + CodeGen code = new CodeGen( +""" +struct A { !L? !a; !T? !b; !F? !c; }; !A? !a = new A; +struct B { !M? !a; !U? !b; !G? !c; }; !B? !b = new B; +struct C { !N? !a; !V? !b; !H? !c; }; !C? !c = new C; +struct D { !O? !a; !W? !b; !I? !c; }; !D? !d = new D; +struct E { !P? !a; !X? !b; !J? !c; }; !E? !e = new E; +struct F { !Q? !a; !Y? !b; !K? !c; }; !F? !f = new F; +struct G { !R? !a; !Z? !b; !L? !c; }; !G? !g = new G; +struct H { !S? !a; !A? !b; !M? !c; }; !H? !h = new H; +struct I { !T? !a; !B? !b; !N? !c; }; !I? !i = new I; +struct J { !U? !a; !C? !b; !O? !c; }; !J? !j = new J; +struct K { !V? !a; !D? !b; !P? !c; }; !K? !k = new K; +struct L { !W? !a; !E? !b; !Q? !c; }; !L? !l = new L; +struct M { !X? !a; !F? !b; !R? !c; }; !M? !m = new M; +struct N { !Y? !a; !G? !b; !S? !c; }; !N? !n = new N; +struct O { !Z? !a; !H? !b; !T? !c; }; !O? !o = new O; +struct P { !A? !a; !I? !b; !U? !c; }; !P? !p = new P; +struct Q { !B? !a; !J? !b; !V? !c; }; !Q? !q = new Q; +struct R { !C? !a; !K? !b; !W? !c; }; !R? !r = new R; +struct S { !D? !a; !L? !b; !X? !c; }; !S? !s = new S; +struct T { !E? !a; !M? !b; !Y? !c; }; !T? !t = new T; +struct U { !F? !a; !N? !b; !Z? !c; }; !U? !u = new U; +struct V { !G? !a; !O? !b; !A? !c; }; !V? !v = new V; +struct W { !H? !a; !P? !b; !B? !c; }; !W? !w = new W; +struct X { !I? !a; !Q? !b; !C? !c; }; !X? !x = new X; +struct Y { !J? !a; !R? !b; !D? !c; }; !Y? !y = new Y; +struct Z { !K? !a; !S? !b; !E? !c; }; !Z? !z = new Z; + +a.a=l; a.b=t; a.c=f; +b.a=m; b.b=u; b.c=g; +c.a=n; c.b=v; c.c=h; +d.a=o; d.b=w; d.c=i; +e.a=p; e.b=x; e.c=j; +f.a=q; f.b=y; f.c=k; +g.a=r; g.b=z; g.c=l; +h.a=s; h.b=a; h.c=m; +i.a=t; i.b=b; i.c=n; +j.a=u; j.b=c; j.c=o; +k.a=v; k.b=d; k.c=p; +l.a=w; l.b=e; l.c=q; +m.a=x; m.b=f; m.c=r; +n.a=y; n.b=g; n.c=s; +o.a=z; o.b=h; o.c=t; +p.a=a; p.b=i; p.c=u; +q.a=b; q.b=j; q.c=v; +r.a=c; r.b=k; r.c=w; +s.a=d; s.b=l; s.c=x; +t.a=e; t.b=m; t.c=y; +u.a=f; u.b=n; u.c=z; +v.a=g; v.b=o; v.c=a; +w.a=h; w.b=p; w.c=b; +x.a=i; x.b=q; x.c=c; +y.a=j; y.b=r; y.c=d; +z.a=k; z.b=s; z.c=e; + +return a.b.c.a.b.c.a.b.c.a.b.c.a.b.c.a.b.c; + +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return R;", code._stop.toString()); + assertEquals("R{a=C{a=N{a=Y{a=J{a=U{a=F{a=Q{a=B{a=M{a=X{a=I{a=T{a=E{a=P{a=A{a=L{a=W{a=H{a=S{a=D{a=O{a=Z{a=K{a=V{a=G{a=$cyclic,b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic}", Eval2.eval(code, 0)); + } + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 8f64701f..584377e4 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -13,7 +11,7 @@ public class Chapter13Test { // A placeholder test used to rapidly rotate through fuzzer produced issues @Test public void testFuzzer() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ while(---- -arg) { while(-arg) { @@ -292,14 +290,14 @@ else { } } """); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString()); + code.parse().opto().typeCheck().GCM(); + assertEquals("return Phi(Region,9,Top,Top,Top,Top);", code.print()); } @Test public void testPrimes() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ if( arg < 2 ) return 0; int primeCount = 1; @@ -324,19 +322,19 @@ while( prime <= arg ) { } return primeCount; """); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop,1,Phi(Region,Phi_primeCount,Phi(Region,(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 + code.parse().opto(); + assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi(Region,(Phi_primeCount+1),Phi_primeCount))));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); // No primes 1 or below + assertEquals("1", Eval2.eval(code, 2)); // 2 + assertEquals("2", Eval2.eval(code, 3)); // 2, 3 + assertEquals("2", Eval2.eval(code, 4)); // 2, 3 + assertEquals("3", Eval2.eval(code, 5)); // 2, 3, 5 + assertEquals("4", Eval2.eval(code, 10)); // 2, 3, 5, 7 } @Test public void testAntiDeps1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v=new S; @@ -346,15 +344,15 @@ i=v.f; if (arg) v.f=1; return i; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 2;", stop.toString()); - assertEquals(2L, Evaluator.evaluate(stop, 0)); - assertEquals(2L, Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertEquals("2", Eval2.eval(code, 0)); + assertEquals("2", Eval2.eval(code, 1)); } @Test public void testAntiDeps2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v = new S; @@ -369,13 +367,13 @@ if (arg) { } return i; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,.f,0);", stop.toString()); + code.parse().opto(); + assertEquals("return Phi(Region,.f,0);", code.print()); } @Test public void testAntiDeps3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v0 = new S; @@ -388,14 +386,14 @@ if (v1) { } return v0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return S;", stop.toString()); + code.parse().opto(); + assertEquals("return S;", code.print()); } @Test public void testAntiDeps4() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v = new S; @@ -406,13 +404,13 @@ if (arg+1) arg= 0; while (arg) v.f = 2; return i; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return arg;", stop.toString()); + code.parse().opto(); + assertEquals("return arg;", code.print()); } @Test public void testAntiDeps5() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v = new S; @@ -423,13 +421,13 @@ while(1) { } return v; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return S;", stop.toString()); + code.parse().opto(); + assertEquals("return S;", code.print()); } @Test public void testAntiDeps6() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct s { int v; }; !s !ptr=new s; @@ -438,13 +436,13 @@ while( -arg ) while(1) arg = arg+ptr.v; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test public void testAntiDeps7() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v = new S; @@ -456,13 +454,13 @@ while (arg) { } return i; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testAntiDeps8() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v = new S; @@ -476,13 +474,13 @@ while(arg) { } return arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testAntiDeps9() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v = new S; @@ -494,13 +492,13 @@ if (arg) { } return v; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return S;", stop.toString()); + code.parse().opto(); + assertEquals("return S;", code.print()); } @Test public void testExample2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int f; }; !S !v = new S; @@ -513,13 +511,13 @@ while (arg > 0) { } return v; """); - StopNode stop = parser.parse().iterate(); - //assertEquals("return new S;", stop.toString()); + code.parse().opto(); + //assertEquals("return new S;", code.print()); } @Test public void testScheduleUse() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int v0=0; while(0>=0) { @@ -530,13 +528,13 @@ while(0>=0) { } return 0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test public void testLoopCarriedDep() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ u32 v0=0; { @@ -545,10 +543,11 @@ u32 v0=0; v1=1>>>v0!=0; v0=v1/0; } + return v1; } """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index 3d92c9cf..a40b4f04 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -20,18 +20,18 @@ public class Chapter14FloatTest { {"f32 rounded=arg+16777216.0; return rounded;", "1.6777232E7", "1.6777199E7"} }; for( String[] test : tests ) { - var stop = new Parser(test[0]).parse().iterate(); - assertEquals(test[0],test[1],Evaluator.evaluate(stop,17).toString()); - assertEquals(test[0],test[2],Evaluator.evaluate(stop,-17).toString()); + var code = new CodeGen(test[0]).parse().opto().typeCheck(); + assertEquals(test[0],test[1],Eval2.eval(code,17)); + assertEquals(test[0],test[2],Eval2.eval(code,-17)); } } @Test public void testSubZeroFloat() { - var stop = new Parser("flt x = arg; return 0-x;").parse().iterate(); + var code = new CodeGen("flt x = arg; return 0-x;").parse().opto().typeCheck(); // 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()); + assertEquals("0.0", Eval2.eval(code,0)); + assertEquals("-1.0", Eval2.eval(code,1)); } @Test public void testDeadNumericReturns() { @@ -42,8 +42,8 @@ public class Chapter14FloatTest { {"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()); + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(src,test[1],Eval2.eval(code,0)); } } @@ -51,29 +51,29 @@ public class Chapter14FloatTest { @Ignore @Test public void testJig() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ return 3.14; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test public void testFloat() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ return 3.14; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test public void testSquareRoot() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ flt guess = arg; while( 1 ) { @@ -83,21 +83,21 @@ while( 1 ) { } return guess; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,(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)); + code.parse().opto(); + assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0f));", code.print()); + assertEquals("3.0", Eval2.eval(code, 9)); + assertEquals("1.414213562373095", Eval2.eval(code, 2)); } @Test public void testFPOps() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ flt x = arg; return x+1==x; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 27804a5a..789a2113 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Ignore; import org.junit.Test; @@ -13,18 +12,18 @@ public class Chapter14Test { @Ignore @Test public void testJig() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ return 3.14; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test public void testRange() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int b; if( arg ) b=1; else b=0; @@ -33,157 +32,157 @@ if( b < 0 ) c = -1; if( b > 2 ) c = 1; return c; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 99;", stop.toString()); - assertEquals(99L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 99;", code.print()); + assertEquals("99", Eval2.eval(code, 0)); } @Test public void testU8() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ u8 b = 123; b = b + 456;// Truncate return b; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 67;", stop.toString()); - assertEquals(67L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 67;", code.print()); + assertEquals("67", Eval2.eval(code, 0)); } @Test public void testU8While() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ u8 b = 123; while( b ) b = b + 456;// Truncate return b; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testU1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ bool b = 123; b = b + 456;// Truncate u1 c = b; // No more truncate needed return c; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testAnd() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int b = 123; b = b+456 & 31; // Precedence return b; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3;", stop.toString()); - assertEquals(3L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); } @Test public void testRefLoad() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct Foo { u1 b; }; !Foo !f = new Foo; f.b = 123; return f.b; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testSigned() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ i8 b = 255; // Chopped return b; // Sign extend """); - StopNode stop = parser.parse().iterate(); - assertEquals("return -1;", stop.toString()); - assertEquals(-1L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return -1;", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); } @Test public void testI8() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ i8 b = arg; b = b + 1;// Truncate return b; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(-128L, Evaluator.evaluate(stop, 127)); + code.parse().opto(); + assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("-128", Eval2.eval(code, 127)); } @Test public void testMask() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ u16 mask = (1<<16)-1; // AND mask int c = 123456789 & mask; return c; // """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 52501;", stop.toString()); - assertEquals(52501L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 52501;", code.print()); + assertEquals("52501", Eval2.eval(code, 0)); } @Test public void testOr() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ return (arg | 123 ^ 456) >>> 1; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return (((arg|123)^456)>>>1);", stop.toString()); - assertEquals(217L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return (((arg|123)^456)>>>1);", code.print()); + assertEquals("217", Eval2.eval(code, 0)); } @Test public void testMaskFloat() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ flt f = arg; -arg = f & 0; +arg = f & 1; return arg; """); - try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Cannot '&' FltBot",e.getMessage()); } + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot '&' flt",e.getMessage()); } } @Test public void testCloneAnd() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int v0=0; u32 v1 = 1&(1<>>0) { while(0) { @@ -195,14 +194,14 @@ if(0&0>>>0) { } return v0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testTypes() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ i8 xi8 = 123456789; if( xi8 != 21 ) return -8; i16 xi16 = 123456789; if( xi16 != -13035 ) return -16; @@ -221,9 +220,9 @@ f32 ff32 = 3.141592653589793; if( ff32 != 3.1415927410125732) return 5; return 0; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 452a1051..97f695bf 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -1,43 +1,40 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; -import org.junit.Test; import org.junit.Ignore; -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.fail; +import org.junit.Test; +import static org.junit.Assert.*; public class Chapter15Test { @Ignore @Test public void testJig() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ return 3.14; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test public void testCyclic() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct C { !C? !l; }; !C !c = new C; c.l = c; return c; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return C;", stop.toString()); - assertEquals("Obj@1{l=obj@1}", Evaluator.evaluate(stop, 0).toString()); + code.parse().opto(); + assertEquals("return C;", code.print()); + assertEquals("C{l=$cyclic}", Eval2.eval(code, 0)); } @Test public void testSafetyCheck() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ u8[] old = new u8[0]; u8[] !output = new u8[1]; @@ -49,66 +46,66 @@ while (i < old#) { output[i] = 1; return output; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return [u8];", stop.toString()); - assertEquals("\u0001", Evaluator.evaluate(stop, 0).toString()); + code.parse().opto(); + assertEquals("return [u8];", code.print()); + assertEquals("\u0001", Eval2.eval(code, 0)); } @Test public void testBasic1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int[] is = new int[2]; return is[1]; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testBasic2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int[] is = new int[2]; int[] is2 = new int[2]; return is[1]; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testBasic3() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int[] !a = new int[2]; a[0] = 1; a[1] = 2; return a[0]; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testBasic4() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct A { int i; }; !A?[] !a = new !A?[2]; return a; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return [*A?];", stop.toString()); - assertEquals("Obj<[*A?]>{#=2,[]=[null,null]}", Evaluator.evaluate(stop, 0).toString()); + code.parse().opto(); + assertEquals("return [*A?];", code.print()); + assertEquals("*A {int !i; }?[ null,null]", Eval2.eval(code, 0)); } @Test public void testBasic5() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int x; flt y; }; // A new S @@ -130,15 +127,15 @@ else { } return rez; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1.2,Phi(Region,2.3,.y));", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); - assertEquals(1.2 , Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return Phi(Region,1.2,Phi(Region,2.3,.y));", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + assertEquals("1.2", Eval2.eval(code, 1)); } @Test public void testBasic6() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int x; flt y; }; // A new S @@ -156,13 +153,13 @@ if( iss[arg] ) rez = iss[arg][2].y; return rez; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Might be null accessing '[]'",e.getMessage()); } } @Test public void testTree() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ // Can we define a forward-reference array? struct Tree { !Tree?[]? !_kids; }; @@ -171,25 +168,25 @@ root._kids = new !Tree?[2]; // NO BANG SO ARRAY IS OF IMMUTABLE TREES???? root._kids[0] = new Tree; return root; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Tree;", stop.toString()); - assertEquals("Obj{_kids=Obj<[*Tree?]>{#=2,[]=[Obj{_kids=null},null]}}", Evaluator.evaluate(stop, 0).toString()); + code.parse().opto(); + assertEquals("return Tree;", code.print()); + assertEquals("Tree{_kids=*Tree?[ Tree{_kids=null},null]}", Eval2.eval(code, 0)); } @Test public void testNestedStructAddMemProj() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct S { int a; int[] !b; }; return 0; """); - StopNode stop = parser.parse(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testRollingSum() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int[] !ary = new int[arg]; // Fill [0,1,2,3,4,...] @@ -206,14 +203,14 @@ while( i < ary# - 1 ) { } return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """); - StopNode stop = parser.parse().iterate(); - assertEquals("return (.[]+(.[]*1000));", stop.toString()); - assertEquals(1006L, Evaluator.evaluate(stop, 4)); + code.parse().opto(); + assertEquals("return (.[]+(.[]*1000));", code.print()); + assertEquals("1006", Eval2.eval(code, 4)); } @Test public void sieveOEratosthenes() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int[] !ary = new int[arg], !primes = new int[arg]; int nprimes = 0, p=2; @@ -247,19 +244,14 @@ while( j < nprimes ) { } return rez; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return [int];", stop.toString()); - Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(stop, 20); - assertEquals("[int] {int #; int ![]; }",obj.struct().toString()); - long nprimes = (Long)obj.fields()[0]; - long[] primes = new long[]{2,3,5,7,11,13,17,19}; - for( int i=0; i>0) {} while(0) {} @@ -358,14 +350,14 @@ u32 v7=0; int v8=0; while(0<--1>>>---(v7*0==v8)) {} """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test public void testProgress2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ if(1) {} else { @@ -382,7 +374,7 @@ else { } } """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + code.parse().opto(); + assertEquals("return 0;", code.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 996be2a1..fd028d57 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -12,68 +12,68 @@ public class Chapter16Test { @Ignore @Test public void testJig() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ return 3.14; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3.14;", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test public void testMulti0() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int x, y; return x+y; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testMulti1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int x=2, y=x+1; return x+y; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 5;", stop.toString()); - assertEquals(5L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 5;", code.print()); + assertEquals("5", Eval2.eval(code, 0)); } @Test public void testConstruct0() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct X { int x=3; }; X z = new X; return z.x; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3;", stop.toString()); - assertEquals(3L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); } @Test public void testConstruct2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct X { int x=3; }; X z = new X { x = 4; }; return z.x; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 4;", stop.toString()); - assertEquals(4L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @Test public void testLinkedList1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct LLI { !LLI? !next; int i; }; !LLI? !head = null; @@ -86,16 +86,16 @@ LLI? next = head.next; if( !next ) return 1; return next.i; """); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(2L, Evaluator.evaluate(stop, 3)); + code.parse().opto(); + assertEquals("return Phi(Region,0,1,.i);", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + assertEquals("2", Eval2.eval(code, 3)); } @Test public void testLinkedList2() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct LLI { !LLI? !next; int i; }; !LLI? !head = null; @@ -117,16 +117,16 @@ LLI? next = head.next; if( !next ) return 1; return next.i; """); - StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(2L, Evaluator.evaluate(stop, 11)); + code.parse().opto(); + assertEquals("return Phi(Region,0,1,.i);", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + assertEquals("2", Eval2.eval(code, 11)); } @Test public void testSquare() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ struct Square { flt !side = arg; @@ -142,10 +142,10 @@ struct Square { }; return new Square; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Square;", stop.toString()); - assertEquals("Obj{side=3.0,diag=1.7320508075688772}", Evaluator.evaluate(stop, 3).toString()); - assertEquals("Obj{side=4.0,diag=2.0}", Evaluator.evaluate(stop, 4).toString()); + code.parse().opto(); + assertEquals("return Square;", code.print()); + assertEquals("Square{side=3.0,diag=1.7320508075688772}", Eval2.eval(code, 3)); + assertEquals("Square{side=4.0,diag=2.0}", Eval2.eval(code, 4)); } static final String CONSTRUCTOR_MEMORY = """ struct S { int x; int y; }; @@ -166,8 +166,8 @@ return new Square; """; @Test public void testConstructorMemory() { - StopNode stop = new Parser(CONSTRUCTOR_MEMORY).parse().iterate(); - assertEquals(111249L,Evaluator.evaluate(stop,0)); - assertEquals(222352L,Evaluator.evaluate(stop,1)); + var code = new CodeGen(CONSTRUCTOR_MEMORY).parse().opto(); + assertEquals("111249",Eval2.eval(code,0)); + assertEquals("222352",Eval2.eval(code,1)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter17aTest.java b/src/test/java/com/seaofnodes/simple/Chapter17aTest.java index 423eade0..ab92d439 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter17aTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter17aTest.java @@ -10,63 +10,63 @@ public class Chapter17aTest { @Test public void testFinal1() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ int x=2, y=3; if( arg ) { int x = y; x = x*x; y=x; } // Shadow final x return y; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,9,3);", stop.toString()); - assertEquals(3L, Evaluator.evaluate(stop, 0)); - assertEquals(9L, Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return Phi(Region,9,3);", code.print()); + assertEquals("3", Eval2.eval(code, 0)); + assertEquals("9", Eval2.eval(code, 1)); } @Test public void testConstruct1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct X { int ~x; }; X z = new X { x=3; }; return z.x; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 3;", stop.toString()); - assertEquals(3L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); } @Test public void testStructFinal0() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Point { int ~x, ~y; }; Point p = new Point { x=3; y=4; }; return p; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return (const)Point;", stop.toString()); - assertEquals("Obj{x=3,y=4}", Evaluator.evaluate(stop, 0).toString()); + code.parse().opto(); + assertEquals("return (const)Point;", code.print()); + assertEquals("Point{x=3,y=4}", Eval2.eval(code, 0)); } @Test public void testStructFinal1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Point { int x=3, y=4; }; Point p = new Point { x=5; y=6; }; p.x++; return p; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @Test public void testStructFinal2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Point { int x=3, y=4; }; Point p = new Point; p.x++; return p; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @@ -74,34 +74,34 @@ return p; public void testStructFinal3() { for( String fields : new String[] { "var x; var y;", "int[] !x;", "int[] !x;" } ) { String src = "struct Point { "+fields+" }; Point p = new Point; p.x++; return p;"; - try { new Parser(src).parse().iterate(); fail(fields); } + try { new CodeGen(src).parse().opto(); fail(fields); } catch( Exception e ) { assertEquals("'Point' is not fully initialized, field 'x' needs to be set in a constructor",e.getMessage()); } } } @Test public void testStructFinal4() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Point { val x=3; val y=4; }; Point p = new Point; p.x++; return p; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } } @Test public void testStructFinal5() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Point { var x=3; var y=4; }; !Point !p = new Point; p.x++; return p; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Point;", stop.toString()); - assertEquals("Obj{x=4,y=4}", Evaluator.evaluate(stop, 0).toString()); + code.parse().opto(); + assertEquals("return Point;", code.print()); + assertEquals("Point{x=4,y=4}", Eval2.eval(code, 0)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 64b606d3..e83b43af 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -1,241 +1,211 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; -import com.seaofnodes.simple.node.StoreNode; -import org.junit.Test; import org.junit.Ignore; +import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter17bTest { - @Test public void testSinkLoopStores() { - StopNode stop = new Parser(""" - struct Totals { int sum; int visits; }; - val t = new Totals { sum=7; visits=2; }; - val data = new int[4]; - for( int i=0; i { - if( n instanceof StoreNode st && !st._name.equals("[]") ) { - assertEquals(stop.in(0).in(0),st.in(0)); // Both stores at the exit. - stores[0]++; - } - return null; - }); - assertEquals(2,stores[0]); - for( int arg : new int[]{-1,0,1,3,4,5} ) { - long n = Math.max(0,Math.min(arg,4)); - var obj = (Evaluator.Obj)Evaluator.evaluate(stop,arg); - org.junit.Assert.assertArrayEquals(new Object[]{7+n*arg+n*(n-1)/2,2+n},obj.fields()); - } - } - - @Test public void testKeepObservedLoopStore() { - StopNode stop = new Parser(""" - struct S { int x; }; - val a = new S; - val b = new S; - val p = arg ? a : b; - int sum=0; - for( int i=0; i<4; i++ ) { - a.x=i+1; - sum+=p.x; - } - return sum; - """).parse().iterate(); - stop.typeCheck(); - assertEquals(0L,Evaluator.evaluate(stop,0)); - assertEquals(10L,Evaluator.evaluate(stop,1)); - } - @Ignore @Test public void testJig() { - Parser parser = new Parser("return 1;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen( +""" +int i = 0; +i=i=1; +return i; +"""); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } // --------------------------------------------------------------- @Test public void testInc0() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" return arg++; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return arg;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return arg;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testInc1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" return arg+++arg++; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg*2)+1);", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return ((arg*2)+1);", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testInc2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" // -(arg--)-(arg--) return -arg---arg--; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return (-((arg*2)+-1));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return (-((arg*2)+-1));", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testInc3() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int[] !xs = new int[arg]; xs[0]++; xs[1]++; return xs[0]; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 2)); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 2)); } @Test public void testInc4() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" u8[] !xs = new u8[1]; xs[0]--; return xs[0]; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 255;", stop.toString()); - assertEquals(255L, Evaluator.evaluate(stop, 2)); + code.parse().opto(); + assertEquals("return 255;", code.print()); + assertEquals("255", Eval2.eval(code, 2)); } @Test public void testInc5() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct S { u16 x; }; !S !s = new S; s.x--; return s.x; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 65535;", stop.toString()); - assertEquals(65535L, Evaluator.evaluate(stop, 2)); + code.parse().opto(); + assertEquals("return 65535;", code.print()); + assertEquals("65535", Eval2.eval(code, 2)); } @Test public void testInc6() { - Parser parser = new Parser("return --arg;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return (arg+-1);", stop.toString()); - assertEquals(-1L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("return --arg;"); + code.parse().opto(); + assertEquals("return (arg+-1);", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); } @Test public void testInc7() { - Parser parser = new Parser("u8 x=0; return --x;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 255;", stop.toString()); - assertEquals(255L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("u8 x=0; return --x;"); + code.parse().opto(); + assertEquals("return 255;", code.print()); + assertEquals("255", Eval2.eval(code, 0)); } @Test public void testInc8() { - Parser parser = new Parser("int x; x+=2; return x+=3;"); - StopNode stop = parser.parse().iterate(); - assertEquals("return 5;", stop.toString()); - assertEquals(5L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("int x; x+=2; return x+=3;"); + code.parse().opto(); + assertEquals("return 5;", code.print()); + assertEquals("5", Eval2.eval(code, 0)); + } + + @Test + public void testInc9() { + CodeGen code = new CodeGen("flt x = 1.5; x++; return x;"); + code.parse().opto(); + assertEquals("return 2.5f;", code.print()); + assertEquals("2.5", Eval2.eval(code, 0)); + } + + @Test public void testInt10() { + CodeGen code = new CodeGen("flt x = 1.5; x++; int i = x; return i;"); + code.parse().opto(); + assertEquals("2",Eval2.eval(code,0)); } + // --------------------------------------------------------------- @Test public void testVar0() { - Parser parser = new Parser("var d; return d;"); - try { parser.parse().iterate(); fail(); } + CodeGen code = new CodeGen("var d; return d;"); + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("Syntax error, expected =expression: ;",e.getMessage()); } } @Test public void testVar1() { - Parser parser = new Parser("val d; return d;"); - try { parser.parse().iterate(); fail(); } + CodeGen code = new CodeGen("val d; return d;"); + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("Syntax error, expected =expression: ;",e.getMessage()); } } @Test public void testVar2() { - Parser parser = new Parser("int x; x=3; x++; return x; // Ok, no initializer so x is mutable "); - StopNode stop = parser.parse().iterate(); - assertEquals("return 4;", stop.toString()); - assertEquals(4L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("int x; x=3; x++; return x; // Ok, no initializer so x is mutable "); + code.parse().opto(); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @Test public void testVar3() { - Parser parser = new Parser("int x=3; x++; return x; // Ok, primitive so x is mutable despite initializer "); - StopNode stop = parser.parse().iterate(); - assertEquals("return 4;", stop.toString()); - assertEquals(4L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("int x=3; x++; return x; // Ok, primitive so x is mutable despite initializer "); + code.parse().opto(); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @Test public void testVar4() { - Parser parser = new Parser("struct S{int x;}; !S !s; s=new S; s.x++; return s.x; // Ok, no initializer so x is mutable "); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("struct S{int x;}; !S? !s; s=new S; s.x++; return s.x; // Ok, no initializer so x is mutable "); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testVar5() { - Parser parser = new Parser("struct S{int x;}; !S !s; s=new S{x=3;}; s.x++; return s.x; // Ok, no initializer so x is mutable "); - StopNode stop = parser.parse().iterate(); - assertEquals("return 4;", stop.toString()); - assertEquals(4L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("struct S{int x;}; !S? !s; s=new S{x=3;}; s.x++; return s.x; // Ok, no initializer so x is mutable "); + code.parse().opto(); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @Test public void testVar6() { - Parser parser = new Parser("struct S{int x;}; S s=new S; s.x++; return s.x; // Error initializer so x is immutable "); - try { parser.parse().iterate(); fail(); } + CodeGen code = new CodeGen("struct S{int x;}; S s=new S; s.x++; return s.x; // Error initializer so x is immutable "); + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @Test public void testVar7() { - Parser parser = new Parser("struct S{int x;}; S s=new S{x=3;}; s.x++; return s.x; // Error initializer so x is immutable "); - try { parser.parse().iterate(); fail(); } + CodeGen code = new CodeGen("struct S{int x;}; S s=new S{x=3;}; s.x++; return s.x; // Error initializer so x is immutable "); + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @Test public void testVar8() { - Parser parser = new Parser("struct S{int x;}; !S !s=new S; s.x++; return s.x; // Ok, has '!' so s.x is mutable "); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("struct S{int x;}; !S !s=new S; s.x++; return s.x; // Ok, has '!' so s.x is mutable "); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testVar9() { - Parser parser = new Parser("struct S{int x;}; var s=new S; s.x++; return s.x; // Ok, has var so s.x is mutable "); - StopNode stop = parser.parse().iterate(); - assertEquals("return 1;", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + CodeGen code = new CodeGen("struct S{int x;}; var s=new S; s.x++; return s.x; // Ok, has var so s.x is mutable "); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testVar10() { - Parser parser = new Parser("struct S{int x;}; ~S s=new S; s.x++; return s.x; // Error, has val so x is immutable "); - try { parser.parse().iterate(); fail(); } + CodeGen code = new CodeGen("struct S{int x;}; ~S s=new S; s.x++; return s.x; // Error, has val so x is immutable "); + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @Test public void testVar11() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int x; }; !Bar !bar = new Bar; bar.x = 3; // Ok, bar is mutable @@ -248,12 +218,12 @@ foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable ~Foo xfoo = foo; // Throw away mutability xfoo.bar.x++; // Error, cannot mutate through xfoo """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @Test public void testVar12() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int x; }; !Bar !bar = new Bar; bar.x = 3; // Ok, bar is mutable @@ -269,24 +239,24 @@ foo.bar.x++; // Bumps to 5 int x5 = xfoo.bar.x; // Ok to read through xfoo, gets 5 return x4*10+x5; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 45;", stop.toString()); - assertEquals(45L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 45;", code.print()); + assertEquals("45", Eval2.eval(code, 0)); } @Test public void testVar13() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int i,i++; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Redefining name 'i'",e.getMessage()); } } @Test public void testVar14() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct B {}; struct A { !B !b; }; A x = new A { @@ -294,127 +264,171 @@ A x = new A { b = new B; }; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("Cannot read uninitialized field 'b'",e.getMessage()); } } @Test public void testVar15() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct B {}; struct A { !B !b; }; return new A { if (arg) b = new B; // Constructor ends with partial init of b }.b; """); - try { parser.parse().iterate(); fail(); } + try { code.parse().opto(); fail(); } catch( Exception e ) { assertEquals("'A' is not fully initialized, field 'b' needs to be set in a constructor",e.getMessage()); } } + @Test + public void testVar16() { + CodeGen code = new CodeGen( +""" +struct S{}; +val x = 1; +val s = new S{x = 2;}; +return x; +""" +); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } + } + + @Test + public void testVar17() { + CodeGen code = new CodeGen( +""" +struct Person { + bool focused; +}; +val focus = { !Person p -> + p.focused = true; +}; +!Person !me; // !Person !me = new Person; +focus(me); +return me; +""" +); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Syntax error, expected =expression: ;",e.getMessage()); } + } + // --------------------------------------------------------------- @Test public void testTrinary0() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" return arg ? 1 : 2; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1,2);", stop.toString()); - assertEquals(2L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return Phi(Region,1,2);", code.print()); + assertEquals("2", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); } @Test public void testTrinary1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" return arg ? 0 : arg; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testTrinary2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int x; }; var b = arg ? new Bar : null; return b ? b.x++ + b.x++ : -1; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1,-1);", stop.toString()); - assertEquals(-1L, Evaluator.evaluate(stop, 0)); - assertEquals( 1L, Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return Phi(Region,((.x*2)+1),-1);", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); } @Test public void testTrinary3() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1,-1);", stop.toString()); - assertEquals(-1L, Evaluator.evaluate(stop, 0)); - assertEquals( 1L, Evaluator.evaluate(stop, 1)); + code.parse().opto(); + assertEquals("return Phi(Region,((.x*2)+1),-1);", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); } @Test public void testTrinary4() { // This test case will benefit from an unzipping transformation - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct Bar { !Bar? !next; int x; }; var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,Phi(Region,.x,.x),0);", stop.toString()); - assertEquals( 0L, Evaluator.evaluate(stop, 0)); - assertEquals( 1L, Evaluator.evaluate(stop, 1)); - assertEquals( 2L, Evaluator.evaluate(stop, 2)); + code.parse().opto(); + assertEquals("return Phi(Region,Phi(Region,.x,.x),0);", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + assertEquals("2", Eval2.eval(code, 2)); } @Test public void testTrinary5() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" flt f=arg?1:1.2; return f; // missing widening """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1.0,1.2);", stop.toString()); - assertEquals(1.2, Evaluator.evaluate(stop, 0)); + code.parse().opto(); + assertEquals("return Phi(Region,1.0f,1.2);", code.print()); + assertEquals("1.2", Eval2.eval(code, 0)); + } + + + @Test + public void testTrinary6() { + CodeGen code = new CodeGen(""" +struct S{}; +return arg ? 7 : new S; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("No common type amongst int and reference",e.getMessage()); } } // --------------------------------------------------------------- @Test public void testFor0() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int sum=0; for( int i=0; i=arg ) break; @@ -422,41 +436,41 @@ for( int i=0; ; i++ ) { } return sum; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString()); - assertEquals(3L, Evaluator.evaluate(stop, 3)); - assertEquals(45L, Evaluator.evaluate(stop, 10)); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print()); + assertEquals("3", Eval2.eval(code, 3)); + assertEquals("45", Eval2.eval(code, 10)); } @Test public void testFor3() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" int sum=0; for( int i=0; i{f1=null,f2=null}", Evaluator.evaluate(stop).toString()); + code.parse().opto(); + assertEquals("return A;", code.print()); + assertEquals("A{f1=null,f2=null}", Eval2.eval(code,0)); } @Test public void testForward1() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct A{ !B?[]? !nil_array_of_b; !B?[] not_array_of_b = new !B?[0]; }; return new A.not_array_of_b; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return [*B?];", stop.toString()); - assertEquals("Obj<[*B?]>{#=0,[]=[]}", Evaluator.evaluate(stop).toString()); + code.parse().opto(); + assertEquals("return [*B?];", code.print()); + assertEquals("*B?[]", Eval2.eval(code,0)); } // --------------------------------------------------------------- @Test public void testLinkedList2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct LLI { !LLI? !next; int i; }; !LLI? !head = null; while( arg-- ) @@ -505,14 +519,14 @@ for( ; ptr; ptr = ptr.next ) sum += ptr.i; return sum; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop,0,(Phi_sum+.i));", stop.toString()); - assertEquals(45L, Evaluator.evaluate(stop, 10)); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(Phi_sum+.i));", code.print()); + assertEquals("45", Eval2.eval(code, 10)); } @Test public void sieveOfEratosthenes() { - Parser parser = new Parser( + CodeGen code = new CodeGen( """ var ary = new bool[arg], primes = new int[arg]; var nprimes=0, p=0; @@ -536,14 +550,9 @@ for( int j=0; j { + if( n instanceof FunNode fun ) + assertEquals("Function entry is outside its loops",0,fun.loopDepth()); + if( n instanceof ReturnNode ret ) { + assertEquals(ret.fun().loopDepth(),ret.loopDepth()); + assertEquals(ret.fun().loopDepth(),ret.cfg0().loopDepth()); + } + if( n instanceof LoopNode loop && !(loop instanceof StartNode) && + loop.back() instanceof CProjNode back && back.in(0) instanceof NeverNode never ) { + nevers[0]++; + assertSame(loop,never.loop()); + assertSame(loop,back.loop()); + CProjNode exit = never.cproj(1-back._idx); + CFGNode fun = loop; + while( !(fun instanceof FunNode) ) fun=fun.idom(); + assertSame(fun.loop(),exit.loop()); + assertEquals(fun.loopDepth(),exit.loopDepth()); + assertTrue(loop.loopDepth()>fun.loopDepth()); + } + return null; + }); + assertTrue("Exercise a synthetic exit",nevers[0]>0); + } + } + + @Test public void testFunctionLocalConstantChains() { + String src = "val f = { int x -> x ? f(x-1)*305420988+x/305420988 : 1; }; "+ + "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ + "return f(arg)+g(arg);"; + CodeGen code = new CodeGen(src); + code.parse().opto().typeCheck(); + Node con = code._stop.walk(n -> n instanceof ConstantNode && + n._type==TypeInteger.constant(305420988) ? n : null); + assertNotNull(con); + Node[] uses = con._outputs.asAry(); + // Preserve a stacked Cast/Constant chain through scheduling. + Node cast = new CastNode(TypeInteger.BOT,code._start,con); + cast = new CastNode(TypeInteger.BOT,code._start,cast); + for( Node use : uses ) + for( int i=1; i(); + code._stop.walk(n -> { + if( !(n instanceof CastNode) || !(n.in(1) instanceof CastNode) ) return null; + CFGNode fun = n.cfg0(); + while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); + assertTrue("Constant must belong to a function",fun instanceof FunNode); + assertNull("Share one constant chain within each function",owners.put(fun,true)); + // Follow all parts of the constant chain, including shared inputs. + var todo = new java.util.ArrayList(); + var seen = new java.util.IdentityHashMap(); + todo.add(n); + for( int j=0; j=2); + } + + @Test public void testReachableMixedReturns() { + for( String[] test : new String[][] { + {"if(arg) return 7; else return 2.5;", "No common type amongst int and f64"}, + {"struct S { int x; }; if(arg) return new S; else return 0;", + "No common type amongst int and reference"} + } ) { + try { + new CodeGen(test[0]).parse().opto().typeCheck(); + fail("Expected incompatible return types: " + test[0]); + } catch( Parser.ParseException e ) { + assertEquals(test[1],e.getMessage()); + } + } + } + + + @Test public void testPrintingForwardReferenceScope() throws Exception { + new CodeGen("return 0;").parse(); + var declared = TypeMemPtr.make(TypeStruct.makeFRef("PrintForward")); + var scope = new ScopeNode(); + scope.define("ptr",declared,false,new ConstantNode(TypeInteger.ZERO),null); + Parser.TYPES.put("PrintForward",TypeMemPtr.make(TypeStruct.make("PrintForward"))); + var field = Var.class.getDeclaredField("_type"); + field.setAccessible(true); + var v = scope._vars.get(0); + org.junit.Assert.assertSame(declared,field.get(v)); + scope.toString(); + org.junit.Assert.assertSame(declared,field.get(v)); + } + + + @Ignore + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 0; +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", Eval2.eval(code, 2)); + } + + @Test + public void testPhiParalleAssign() { + CodeGen code = new CodeGen( +""" +int a = 1; +int b = 2; +while(arg--) { + int t = a; + a = b; + b = t; +} +return a; +"""); + code.parse().opto().typeCheck().GCM(); + assertEquals("return Phi(Loop,1,Phi(Loop,2,Phi_a));", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("2", Eval2.eval(code, 1)); + assertEquals("1", Eval2.eval(code, 2)); + assertEquals("2", Eval2.eval(code, 3)); + } + + + // --------------------------------------------------------------- + @Test + public void testType0() { + CodeGen code = new CodeGen( +""" +{int -> int}? x2 = null; // null function ptr +return x2; +"""); + code.parse().opto(); + assertEquals("return null;", code._stop.toString()); + assertEquals("null", Eval2.eval(code, 0 ) ); + } + + @Test + public void testFcn0() { + CodeGen code = new CodeGen( +""" +{int -> int}? sq = { int x -> + x*x; +}; +return sq; +"""); + code.parse().opto(); + assertEquals("Stop[ return { sq}; return (Parm_x(sq,int)*x); ]", code._stop.toString()); + assertEquals("{ sq}", Eval2.eval(code, 3)); + } + + @Test + public void testFcn1() { + CodeGen code = new CodeGen( +""" +var sq = { int x -> + x*x; +}; +return sq(arg)+sq(3); +"""); + code.parse().opto(); + assertEquals("Stop[ return (sq( 3)+sq( arg)); return (Parm_x(sq,int,3,arg)*x); ]", code._stop.toString()); + assertEquals("13", Eval2.eval(code, 2)); + } + + // Function scope test + @Test + public void testFcn2() { + CodeGen code = new CodeGen( +""" +int cnt=1; +return { -> cnt; }; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Variable 'cnt' is out of function scope and must be a final constant",e.getMessage()); } + } + + // Function scope test + @Test + public void testFcn3() { + CodeGen code = new CodeGen( +""" +val cnt=2; +return { -> cnt; }(); +"""); + code.parse().opto(); + assertEquals("return 2;", code._stop.toString()); + assertEquals("2", Eval2.eval(code, 0)); + } + + // Function variables + @Test + public void testFcn4() { + CodeGen code = new CodeGen( +""" +var fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; +return fcn(3); +"""); + code.parse().opto(); + assertEquals("Stop[ return Phi(Region,{ int -> int #1},{ int -> int #2})( 3); return (Parm_x($fun,int,3)*x); return (Parm_x($fun,int,3)*2); ]", code._stop.toString()); + assertEquals("6", Eval2.eval(code, 0)); + assertEquals("9", Eval2.eval(code, 1)); + } + + // Recursive factorial test + @Test + public void testFcn5() { + CodeGen code = new CodeGen("val fact = { int x -> x <= 1 ? 1 : x*fact(x-1); }; return fact(arg);"); + code.parse().opto(); + assertEquals("Stop[ return fact( arg); return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*fact( Sub))); ]", code._stop.toString()); + assertEquals( "1", Eval2.eval(code, 0)); + assertEquals( "1", Eval2.eval(code, 1)); + assertEquals( "2", Eval2.eval(code, 2)); + assertEquals( "6", Eval2.eval(code, 3)); + assertEquals("24", Eval2.eval(code, 4)); + } + + @Test + public void testFcn6() { + CodeGen code = new CodeGen( +""" +struct S { int i; }; +val newS = { int x -> return new S { i=x; }; }; +return newS(1).i; +"""); + code.parse().opto().typeCheck().GCM(); + assertEquals("return 1;", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 0)); + } + + // Double forward reference + @Test + public void testFcn7() { + CodeGen code = new CodeGen( +""" +if( arg ? f : g ) return 1; +val f = {->1;}; +val g = {->2;}; +return 2; +"""); + code.parse().opto().typeCheck().GCM(); + assertEquals("Stop[ return 1; return 1; return 2; ]", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 0)); + } + + @Test + public void testFcn8() { + CodeGen code = new CodeGen( +""" +{int -> int}? !i2i = null; +var id = {{int->int} f-> return f;}; +for(;;) { + if (i2i) return i2i(arg); + var x = {int i-> return i;}; + arg = x(3); + i2i = id(x); +} +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("Stop[ return x( Phi(Loop,arg,x( 3))); return Parm_i(x,int,3,Phi_arg); ]", code._stop.toString()); + assertEquals("3", Eval2.eval(code, 0)); + } + + + @Test + public void testFcn9() { + CodeGen code = new CodeGen( +""" +{int -> int}? !i2i = null; +for(;;) { + if (i2i) return i2i(arg); + var x = {int i-> return i;}; + arg = x(3); +} +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return Top;", code._stop.toString()); + assertEquals(null, Eval2.eval(code, 0)); + } + + // Function break + @Test + public void testErr1() { + CodeGen code = new CodeGen( +""" +for(;;) { + val f = { -> + break; + }; + f(); + return 2; +} +return 1; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("No active loop for a break or continue",e.getMessage()); } + } + + // Calling and inlining a null function + @Test + public void testErr2() { + CodeGen code = new CodeGen( +""" +{int -> int}? !i2i = { int i -> return i; }; +for(;;) { + if (i2i(2) == arg) break; + i2i = null; +} +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Might be null calling { int -> int #1}?",e.getMessage()); } + } + + + @Test + public void testErr3() { + CodeGen code = new CodeGen( +""" +val f = { int i, int j -> return i+j; }; +return f(); +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Expecting 2 arguments, but found 0",e.getMessage()); } + } + + + @Test + public void testErr4() { + CodeGen code = new CodeGen( +""" +struct S { + {int} f = { -> x(); return 0; }; // Do not let fref x be a field +}; +val x = { -> return 1; }; +!S? !s = null; +for(;;) { + if (s) return s.x; +} +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Accessing unknown field 'x' from '*S'",e.getMessage()); } + } + + @Test + public void testErr5() { + CodeGen code = new CodeGen( +""" +val g = { -> + g(); +}; +return 0; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("No defined return type",e.getMessage()); } + } + + + // Mutual recursion. Fails without SCCP to lift the recursive return types. + @Ignore @Test + public void testFcnMutRec() { + CodeGen code = new CodeGen( +""" +val is_even = { int x -> x ? is_odd (x-1) : true ; }; +val is_odd = { int x -> x ? is_even(x-1) : false; }; +return is_even(arg); +"""); + code.parse().opto(); + assertEquals("Stop[ return is_even( arg); return Phi(Region,Phi(Region,is_even( ((Parm_x(is_even,int,arg,Sub)-1)-1)),0),1); ]", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("0", Eval2.eval(code, 1)); + assertEquals("1", Eval2.eval(code, 2)); + assertEquals("0", Eval2.eval(code, 3)); + } + + // Forward ref to 'x' means that + @Ignore @Test + public void testForwardRef1() { + CodeGen code = new CodeGen( +""" +struct S { + { int } f = { -> return x(); }; +}; +val x = { -> return 1; }; +!S? !s = null; +for(;;) { + if (s) return s.f; +} +"""); + code.parse().opto().typeCheck().GCM(); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", Eval2.eval(code, 0)); + } + + // Inline hidden called more than once + @Test + public void testInline() { + CodeGen code = new CodeGen( +""" +{int->int}?! i2i = {int i->return i;}; +{{int->int}->{int->int}}! f2f = {{int->int} f->return f;}; +val o = i2i; +if (arg) i2i = null; +if (i2i) return i2i(arg); +return f2f(o)(1); +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("Stop[ return Phi(Region,o( arg),o( 1)); return Parm_i(o,int,arg,1); ]", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 2)); + } + + @Test + public void testOperField() { + CodeGen code = new CodeGen( +""" +struct Person { + int coffee_count; +}; +!Person !p = new Person; +p.coffee_count += 1; +return p.coffee_count; +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return 1;", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 2)); + } + + static final String CALL_MEMORY = """ + struct S { int x; int y; }; + val bump = { !S !s, int d -> int old=s.x; s.x=old+d; return old; }; + !S !a = new S { x=10; y=7; }; + !S !b = new S { x=20; y=9; }; + !S !p=a; if (arg) p=b; + int before=p.x; + int old=bump(p,3); + int after=p.x; + bump(a,5); + return before*1000000+old*10000+after*100+a.x+a.y; + """; + + @Test public void testCallMemory() { + var code = new CodeGen(CALL_MEMORY).parse().opto(); + int[] calls={0}; + code._stop.walk(n -> { if(n instanceof CallNode) calls[0]++; return null; }); + assertEquals(2,calls[0]); // Keep real calls so this checks scheduling across them. + assertEquals("10101325",Eval2.eval(code,0)); + assertEquals("20202322",Eval2.eval(code,1)); + code._stop.walk(n -> { + if(n instanceof CallNode call) { + assertEquals(5,call.nIns()); // No scheduling edges may become extra arguments. + assertTrue(call.fptr()._type instanceof TypeFunPtr); + } + return null; + }); + } + + static final String RECURSIVE_MEMORY = """ + struct S { int x; }; + val rec = { !S !s, int n -> + if (n==0) return s.x; + int before=s.x; + s.x=before+1; + return before+rec(s,n-1); + }; + !S !s=new S { x=10; }; + int value=rec(s,arg); + return value*100+s.x; + """; + + @Test public void testRecursiveMemory() { + var code = new CodeGen(RECURSIVE_MEMORY).parse().opto(); + for(int n=0; n<7; n++) + assertEquals(Long.toString((10L*(n+1)+n*(n+1)/2)*100+10+n),Eval2.eval(code,n)); + } + + static final String INLINE_MEMORY = """ + struct S { int x; int y; }; + val make = { !S s -> + S t = new S { x=s.x+1; y=3; }; + s.y=9; + return t; + }; + !S !a = new S { x=arg+40; y=7; }; + S t=make(a); + return a.x*10000+a.y*100+t.x+t.y; + """; + + @Test public void testInlineAllocationMemory() { + var code = new CodeGen(INLINE_MEMORY).parse().opto(); + assertNull(code._stop.walk(n -> n instanceof CallNode ? n : null)); + assertEquals("400944",Eval2.eval(code,0)); + assertEquals("420946",Eval2.eval(code,2)); + } +} diff --git a/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java b/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java index 0fa4283b..860827d7 100644 --- a/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java +++ b/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; + import org.junit.Test; import static org.junit.Assert.*; @@ -64,14 +64,31 @@ public class CompoundAssignmentTest { check(src, 0, 0); fail("Accepted invalid assignment: " + src); } catch (RuntimeException e) { - assertEquals("Must report a language error", RuntimeException.class, e.getClass()); + assertTrue("Must report a language error: " + e, e instanceof Parser.ParseException); assertNotNull(e.getMessage()); assertFalse("Must report a language error: " + e, e.getMessage().contains("Not yet implemented")); } } + @Test public void testFields() { + for (String op : OPS) { + long expected = apply(op, -8, 3); + check("struct S { int x; }; !S !s=new S; s.x=arg; int r=(s.x " + + op + " 3); return s.x*10+r;", -8, expected*11); + } + } + + @Test public void testArrayAddressAndRhsOnce() { + for (String op : OPS) { + long expected = apply(op, 5, 1); + check("int[] !a=new int[2]; a[0]=arg; int i=0; int count=0; " + + "int r=(a[i++] " + op + " (count=count+1)); " + + "return i*1000+count*100+a[0]*10+r;", 5, 1100+expected*11); + } + } + private static void check(String src, long arg, long expected) { - var stop = new Parser(src).parse().iterate(); - assertEquals(src, Long.valueOf(expected), Evaluator.evaluate(stop, arg)); + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(src, Long.toString(expected), Eval2.eval(code, arg)); } } diff --git a/src/test/java/com/seaofnodes/simple/Eval2.java b/src/test/java/com/seaofnodes/simple/Eval2.java new file mode 100644 index 00000000..3f337e86 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Eval2.java @@ -0,0 +1,454 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; +import java.util.*; + +public abstract class Eval2 { + + // A mapping from Node ID to evaluation data Object. + // Data Objsts are a boxed Long or Double; or an Object[] of fields, which + // themselves are just more Objects. + private static class Frame { + private static int UID=1; + + private final IdentityHashMap _data; + private Frame _prior; // Prior frame in this sequence, means when making a new frame we can find old stuff + private int _refcnt; // TODO: Use this in a sentence (free/recycle unused stack frames) + final int _uid = UID++; // Debugging aid + Frame(Frame prior) { + _prior = prior; + if( prior!=null ) prior._refcnt++; + _data = new IdentityHashMap<>(); + _refcnt = 1; + } + + // Dec ref count + void dec() { + assert _refcnt>0; + if( --_refcnt == 0 ) { + Frame prior = _prior; + _prior = null; + _data.clear(); + // TODO: FREE LIST? + if( prior!=null ) + prior.dec(); + } + } + + // Put a mapping from Node->Object + Node put(Node n, Object d) { + assert d!=null; + return put0(n,d); + } + // Put a mapping from Node->Object? + Node put0(Node n, Object d) { + assert _refcnt>0; + _data.put(n,d); + return n; + } + // Get a mapped Node, perhaps using the prior stack frame crawl + Object get(Node n) { + assert _refcnt>0; + Object d = _data.get(n); + return d != null ? d + : _prior == null ? null + : _prior.get(n); + } + + // Short debugging print + public String p() { + return "#"+_uid + (_prior==null ? "" : " >> " + _prior.p()); + } + // Long debugging print + @Override public String toString() { + String s = ""; + if( _prior != null ) s+= _prior+" << "; + s += "#"+_uid+"[ "; + for( Node n : _data.keySet() ) + s += n + ":" + _data.get(n) + ","; + s += "]"; + + return s; + } + } + + // Classic Closure; an environment (stack of frames) and an execution point + private static class Closure { + // Where to return too; either a CallEnd or a Function + final CFGNode _cc; + + // Stack frame at the execution point. Includes Closures which + // recursively include other stack frames + private Frame _frame; + + Closure(CFGNode cc, Frame frame) { + _cc = cc; // One of Fun, CallEnd or Stop (null) + _frame = frame; + assert _frame._refcnt >=0; + _frame._refcnt++; + } + + FunNode fun() { return (FunNode)_cc; } + CallEndNode cend() { return (CallEndNode)_cc; } + boolean isStop() { return _cc instanceof StopNode; } // or Stop + + // + void pushFrame() { + _frame = new Frame(_frame); + _frame._refcnt++; + } + + @Override public String toString() { + return _cc.toString(); + } + } + + // CodeGen has the linker tables + public static CodeGen CODE; + + // Current active Frame, to avoid having to pass it everywhere + public static Frame F; + + public static String eval( CodeGen code, long arg ) { return eval(code,arg,1000); } + public static String eval( CodeGen code, long arg, int timeout ) { + SB trace = null; // new SB(); // TRACE, set to null for off, new SB() for on + // Force local scheduling phase + if( code._phase.ordinal() < CodeGen.Phase.TypeCheck .ordinal() ) code.typeCheck(); + if( code._phase.ordinal() < CodeGen.Phase.Schedule .ordinal() ) code.GCM(); + if( code._phase.ordinal() < CodeGen.Phase.LocalSched.ordinal() ) code.localSched(); + // Set global, so don't have to pass everywhere + CODE = code; + + // Timer for when we run too long. Ticks once per backedge or function call + int loopCnt = 0; + + // Current value for each Node; boxed Long or Double; or an Object[] of + // fields, which themselves are just more Objects. + F = new Frame(null); + + // Start at the START + CFGNode BB = code._start, prior = null; + // Return from main hits Stop + F.put(BB,new Closure(code._stop,F)); + + + // ------------ + // Evaluate until exit or timeout. Each outer loop step computes + // all data nodes under some new Control. + while( true ) { + assert BB!=null; + traceCtrl(BB,trace); + if( trace!=null ) System.out.println(F.p()); + + // Parallel assign Phis + int i = BB instanceof RegionNode r + ? parallelAssignPhis(r,prior,arg,trace) + : 0; + + // Compute the data nodes until BB control + for( ; i < BB.nOuts(); i++ ) + if( !(BB.out(i) instanceof CFGNode) ) + step(BB.out(i), trace); + + // Find the next control target + prior = BB; + BB = BB.uctrl(); // Next unique control target + switch( prior ) { + case StartNode start: F = new Frame(F); break; // Frame for the call to main, as-if Called + case CallNode call : BB = call(call); break; + case IfNode iff : Object p = val(iff.pred()); BB = iff.cproj( p==null || (p instanceof Long x && x==0L) ? 1 : 0); break; + case ReturnNode ret : if( clj(ret.rpc()).isStop() ) return exit(ret); else BB = ret(ret); break; + case FunNode fun : if( loopCnt++ > timeout ) return null; break; // Timeout + case LoopNode loop : if( loopCnt++ > timeout ) return null; break; // Timeout + case CallEndNode cend: break; + case CProjNode cproj: break; + case RegionNode r : break; + default: throw Utils.TODO(); + } + assert !BB.isDead(); + } + } + + + // Phi cache; size is limited to number of Phis at a merge point + private static final Object[] PHICACHE = new Object[256]; + static int parallelAssignPhis(RegionNode r, CFGNode prior, long arg, SB trace) { + + // Compute input path on Phis for this Region + int path = r._inputs.find( prior ); + // Parameters read from prior frame, Phis from local frame + Frame frame = (r instanceof FunNode ? F._prior : F); + boolean isMain = r instanceof FunNode fun && fun.sig().isa(TypeFunPtr.MAIN); + + // Parallel assign Phis. First parallel read and cache + int i; + for( i = 0; i < r.nOuts(); i++ ) { + if( !(r.out(i) instanceof PhiNode phi) ) break; + if( isMain && phi instanceof ParmNode parm && parm._idx==2 ) + PHICACHE[i] = arg; // Reading the initial arguments to main() + else { + Node n = phi instanceof ParmNode parm + // RPC reads the Call directly; + // Parms may not be linked, so read call args directly + ? (parm._idx==0 ? prior : prior.in(parm._idx)) + // Phis read from path input + : phi.in(path); + PHICACHE[i] = frame.get(n); + } + } + // Parallel assign; might assign before read, so read from cache + for( int j=0; j < i; j++ ) + traceData(F.put0(r.out(j),PHICACHE[j]),trace); + // Return point in basic block past last Phi + return i; + } + + + // Make a call. + private static CFGNode call( CallNode call ) { + // Set up the Return PC and return frame (which is just the current frame). + // Really making a Continuation, but it's just a Closure + Closure cont = new Closure(call.cend(),F); + // Set the return continuation into the current frame RPC + F.put(call, cont ); + // Next Frame to use + F = new Frame(F); + // Target function and environment + return CODE.link(tfp(call.fptr())); + } + + private static CFGNode ret( ReturnNode ret ) { + // Fetch return expression value and continuation from current frame + Object rez = val(ret.expr()); + Closure cont = clj(ret.rpc()); + // Lower Frame reference count; might delete frame + F.dec(); // Lower ref count + // Install replacement Frame; set return result over the CallEnd + F = cont._frame; + F.put0(cont._cc,rez); // Set return value into CallEnd + return cont._cc; // Return CallEnd as the new control + } + + private static String exit( ReturnNode ret ) { + return prettyPrint(ret.expr()._type,val(ret.expr())); + } + + // Take a worklist step: one data op from the current Control is updated. + private static void step(Node n, SB trace) { + if( n instanceof PhiNode ) return; + // Compute new value + F.put0(n,compute(n)); + traceData(n,trace); + // Also do any following projections, which are not in the local schedule otherwise + if( n instanceof MultiNode ) + for( Node use : n._outputs ) + step(use,trace); + } + + // From here down shamelessly copied from Evaluator, written by @Xmilia + private static Object compute( Node n ) { + return switch( n ) { + case AddFNode adf -> d(adf.in(1)) + d(adf.in(2)); + case AddNode add -> x(add.in(1)) + x(add.in(2)); + case AndNode and -> x(and.in(1)) & x(and.in(2)); + case BoolNode.EQF eqf -> d(eqf.in(1)) == d(eqf.in(2)) ? 1L : 0L; + case BoolNode.LEF lef -> d(lef.in(1)) <= d(lef.in(2)) ? 1L : 0L; + case BoolNode.LTF ltf -> d(ltf.in(1)) < d(ltf.in(2)) ? 1L : 0L; + case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; // Bool EQ supports pointers, nil, and integers + case BoolNode.LE le -> x(le .in(1)) <= x(le .in(2)) ? 1L : 0L; + case BoolNode.LT lt -> x(lt .in(1)) < x(lt .in(2)) ? 1L : 0L; + case CastNode cast -> val(cast.in(1)); + case ConstantNode con -> con(con._con); + case DivFNode dvf -> d(dvf.in(2))==0 ? 0D : d(dvf.in(1)) / d(dvf.in(2)); + case DivNode div -> x(div.in(2))==0 ? 0L : x(div.in(1)) / x(div.in(2)); + case LoadNode ld -> load(ld); + case MinusFNode mnf -> - d(mnf.in(1)); + case MinusNode sub -> - x(sub.in(1)); + case MulFNode mlf -> d(mlf.in(1)) * d(mlf.in(2)); + case MulNode mul -> x(mul.in(1)) * x(mul.in(2)); + case NewNode alloc-> alloc(alloc); + case NotNode not -> not(not); + case OrNode or -> x(or .in(1)) | x(or .in(2)); + case ProjNode proj -> proj._type instanceof TypeMem ? "$mem" : val(proj.in(0)); + case ReadOnlyNode read -> val(read.in(1)); + case SarNode sar -> x(sar.in(1)) >> x(sar.in(2)); + case MemMergeNode merge-> "$mem"; + case ShlNode shl -> x(shl.in(1)) << x(shl.in(2)); + case ShrNode shr -> x(shr.in(1)) >>>x(shr.in(2)); + case StoreNode st -> store(st); + case SubNode sub -> x(sub.in(1)) - x(sub.in(2)); + case SubFNode sbf -> d(sbf.in(1)) - d(sbf.in(2)); + case RoundF32Node rnd -> (double)(float)d(rnd.in(1)); + case ToIntegerNode cvt -> (long)d(cvt.in(1)); + case ToFloatNode toflt-> (double)x(toflt.in(1)); + case XorNode xor -> x(xor.in(1)) ^ x(xor.in(2)); + default -> throw Utils.TODO(); + }; + } + + private static Object not( NotNode not ) { + Object n = val(not.in(1)); + return ( n==null || (n instanceof Double D && D==0.0) || n instanceof Long L && L==0 ) + ? 1L : 0L; + } + + // Fetch without unboxing, searching up-Frame + static Object val( Node n ) { return F.get(n); } + // Fetch and unbox as primitive long + static long x( Node n ) { Object d = F.get(n); return d==null ? 0 : (Long) F.get(n); } + // Fetch and unbox as primitive double + static double d( Node n ) { Object d = F.get(n); return d==null ? 0 : (Double)F.get(n); } + // Fetch and unbox a function constant + static TypeFunPtr tfp(Node n) { return (TypeFunPtr)F.get(n); } + // Fetch and unbox a closure + static Closure clj(Node n) { return (Closure)F.get(n); } + + // Java box ints and floats. Other things can just be null or some informative string + private static Object con( Type t ) { + return switch ( t ) { + case TypeInteger i -> i.isConstant() ? (Long )i.value() : "INT"; + case TypeFloat f -> f.isConstant() ? (Double)f.value() : "FLT"; + case TypeMemPtr tmp -> tmp; + case TypeFunPtr tfp -> tfp; + case TypeMem mem -> "MEM"; + default -> null; + }; + } + + // Convert array size to array element count + private static int offToIdx( long off, TypeStruct t) { + off -= t.aryBase(); + int scale = t.aryScale(); + long mask = (1L << scale)-1; + assert (off & mask) == 0; + return (int)(off>>scale); + } + + // Builds and returns a pointer Object + private static Object alloc(NewNode alloc) { + TypeStruct type = alloc._ptr._obj; + if( type.isAry() ) { + long sz = (Long)val(alloc.size()); + long x = offToIdx(sz, type); + int n = (int)x; + if( n!=x || n<0 ) + throw new NegativeArraySizeException(""+n); + Object[] ary = new Object[n]; // Array body + var elem = type._fields[1]._type; + if (elem instanceof TypeInteger) { + Arrays.fill( ary, 0L ); + } else if (elem instanceof TypeFloat) { + Arrays.fill( ary, 0D ); + } else { + assert elem instanceof TypeMemPtr || elem instanceof TypeFunPtr; + } + return ary; + } + + int num = type._fields.length; + Object[] ptr = new Object[num]; + for( int i=0; i VISIT = new IdentityHashMap<>(); + + + static void traceCtrl( CFGNode BB, SB sb ) { + if( sb==null ) return; + IRPrinter.printLine(BB,sb.p("--- ")); + System.out.print(sb); + sb.clear(); + } + static void traceData( Node n, SB sb ) { + if( sb==null ) return; + IRPrinter.printLine(n,sb).unchar(); + _print( n._type, F.get(n), sb.p('\t'), VISIT ); + System.out.println(sb); + sb.clear(); + VISIT.clear(); + } + + // Use type to print x as a string. Uses a new VISIT table so the debugger + // doesn't try to reuse VISIT if stopping mid-print. The trace code reuses + // VISIT endlessly for some minor speed hope + static String prettyPrint( Type t, Object x ) { return _print(t,x,new SB(), new IdentityHashMap<>()).toString(); } + static SB _print( Type t, Object x, SB sb, IdentityHashMap visit ) { + if( x instanceof String s ) return sb.p(s); + if( x == null ) return sb.p("null"); + return switch( t ) { + case TypeInteger i -> sb.p( (Long)x); + case TypeFloat f -> sb.p((Double)x); + case TypeMemPtr tmp -> { + if( visit.containsKey(x) ) yield sb.p("$cyclic"); + visit.put(x,x); + // Since never can close the type cycle, without cyclic types, have + // to handle FRefs even here + if( tmp.isFRef() ) + tmp = tmp.makeFrom(((TypeMemPtr)Parser.TYPES.get(tmp._obj._name))._obj); + + Object[] xs = (Object[])x; // Array of fields + if( tmp._obj.isAry() ) { + Type elem = tmp._obj._fields[1]._type; + if( elem == TypeInteger.U8 ) { + // Shortcut u8[] as a String + for( Object o : xs ) + sb.p((char)(long)(Long)o); + } else { + // Array of elements + elem.print(sb).p("[ "); + for( Object o : xs ) + _print( elem, o, sb, visit ).p( "," ); + sb.unchar().p("]"); + } + } else { + sb.p(tmp._obj._name).p("{"); + Field[] flds = tmp._obj._fields; + for( int i=0; i sb.p(x.toString()); + case TypeRPC rpc -> sb.p(x.toString()); + case TypeMem mem -> sb.p("$mem"); + case TypeTuple tt -> { + if( tt._types.length>1 && tt._types[0] instanceof TypeMemPtr ) + // Assume a NewNode + yield _print( tt._types[0], x, sb, visit ); + throw Utils.TODO(); + } + case Type tt -> { + if( tt == Type.NIL ) yield sb.p("null"); + throw Utils.TODO(); + } + }; + } +} diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 2c98f405..143828e6 100644 --- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -7,9 +7,10 @@ import org.junit.Test; import static org.junit.Assert.assertTrue; /** - * Normal tests run chapter-local regression seeds. Open failures and exploratory - * fuzzing are opt-in (run directly in the IDE or temporarily remove Ignore). - * Seeds depend on this chapter's generator; do not copy them between chapters. + * Normal tests run only this chapter's fixed regression seeds. Open failures + * and exploratory fuzzing are opt-in: run their methods directly in the IDE, + * or temporarily remove the relevant Ignore annotation when investigating. + * Seeds belong to this chapter's generator; do not copy them between chapters. */ public class FuzzerWrap { @@ -43,7 +44,7 @@ public class FuzzerWrap { Random R = new Random(System.currentTimeMillis()); var fuzzer = new Fuzzer(); for (int i=0; i<100; i++) - fuzzer.fuzzPeeps(R.nextLong()); + fuzzer.fuzzPeeps( R.nextLong()); assertTrue(fuzzer.noExceptions()); } diff --git a/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/src/test/java/com/seaofnodes/simple/MergeSortTest.java new file mode 100644 index 00000000..a352530f --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -0,0 +1,65 @@ +package com.seaofnodes.simple; + +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class MergeSortTest { + + @Test + public void testMergeSort() { + CodeGen code = new CodeGen( +""" +// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort + +val merge_sort = { int[] !a, int[] !b, int n -> + copy_array(a, 0, n, b); + split_merge(a, 0, n, b); +}; + +val split_merge = { int[] !b, int begin, int end, int[] a -> + if (end - begin <= 1) + return 0; + int middle = (end + begin) / 2; + split_merge(a, begin, middle, b); + split_merge(a, middle, end, b); + merge(b, begin, middle, end, a); + return 0; +}; + +val merge = { int[] !b, int begin, int middle, int end, int[] a -> + int i = begin, j = middle; + + for (int k = begin; k < end; k++) { + // && and || + bool cond = false; + if (i < middle) { + if (j >= end) cond = true; + else if (a[i] <= a[j]) cond = true; + } + if (cond) b[k] = a[i++]; + else b[k] = a[j++]; + } +}; + +val copy_array = { int[] !a, int begin, int end, int[] b -> + for (int k = begin; k < end; k++) + b[k] = a[k]; +}; + +int[] !a = new int[arg]; +int[] !b = new int[a#]; + +for (int i = 0; i < a#; i++) + a[i] = a# - i; + +merge_sort(a, b, a#); + +return a; +"""); + code.parse().opto(); + assertEquals("Stop[ return [int]; return 0; ]", code._stop.toString()); + assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/MutabilityTest.java b/src/test/java/com/seaofnodes/simple/MutabilityTest.java index 8f99a059..0861424f 100644 --- a/src/test/java/com/seaofnodes/simple/MutabilityTest.java +++ b/src/test/java/com/seaofnodes/simple/MutabilityTest.java @@ -5,16 +5,16 @@ import static org.junit.Assert.*; public class MutabilityTest { private static void ok(String src, String result) { - var stop = new Parser(src).parse().iterate(); - assertEquals(result,com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0).toString()); + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(result,Eval2.eval(code,0)); } private static void bad(String src) { try { - new Parser(src).parse().iterate(); + new CodeGen(src).parse().opto().typeCheck(); } catch( RuntimeException expected ) { String msg = expected.getMessage(); assertTrue("Expected a permission error, got: "+expected, - msg!=null && (msg.contains("final") || msg.contains("not of declared type") || msg.contains("Cannot store"))); + msg!=null && (msg.contains("final") || msg.contains("not of declared type") || msg.contains("Cannot store") || msg.contains("Argument #"))); return; } fail("Accepted forbidden write: "+src); @@ -43,6 +43,15 @@ public class MutabilityTest { bad("struct P { int x; }; P p=new P; var q=p; q.x=7; return 0;"); } + @Test public void testParameterPermissions() { + ok("struct P { int x; }; val f={ !P p -> p.x=7; return p.x; }; return f(new P);", "7"); + ok("val f={ int ~x -> return x; }; return f(7);", "7"); + bad("val f={ int ~x -> x=7; return x; }; return f(3);"); + bad("struct P { int x; }; val f={ P p -> p.x=7; return p.x; }; return f(new P);"); + bad("struct P { int x; }; val f={ !P p -> p.x=7; return p.x; }; P p=new P; return f(p);"); + bad("struct P { int x; }; val f={ P?[] a -> return a#; }; !P?[] a=new !P?[1]; return f(a);"); + } + @Test public void testConstructorScope() { ok("struct P { int ~x; }; P p=new P{if(arg) x=3; else x=7;}; return p.x;", "7"); bad("int ~outer=1; struct P { int x; }; P p=new P{outer=7;}; return outer;"); diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java index d8a22fd3..d29166a7 100644 --- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -20,7 +20,7 @@ public class SchedulerTest { @Test @Ignore public void testJig() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct S { int f; } @@ -30,14 +30,14 @@ int i=v.f; if (arg) v.f=1; return i; """); - StopNode stop = parser.parse();//.iterate(); - var eval = new Evaluator(stop); + code.parse();//.opto(); + var eval = new Evaluator(code._stop); assertEquals(2L, eval.evaluate(1, 10)); } @Test public void testStoreInIf() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct S { int f; }; @@ -45,15 +45,15 @@ struct S { if(arg) v0.f=1; return v0; """); - StopNode stop = parser.parse().iterate(); - var eval = new Evaluator(stop); + code.parse().opto(); + var eval = new Evaluator(code._stop); assertObj(eval.evaluate(0, 10), "S", 0L); assertObj(eval.evaluate(1, 10), "S", 1L); } @Test public void testStoreInIf2() { - Parser parser = new Parser(""" + CodeGen code = new CodeGen(""" struct S { int f; }; @@ -64,8 +64,8 @@ i=v.f; if (arg) v.f=1; return i; """); - StopNode stop = parser.parse().iterate(); - var eval = new Evaluator(stop); + code.parse().opto(); + var eval = new Evaluator(code._stop); assertEquals(2L, eval.evaluate(0, 10)); assertEquals(2L, eval.evaluate(1, 10)); } diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index 3fac1641..dee033bc 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.type.*; import org.junit.Assert; -import org.junit.Ignore; import org.junit.Test; -import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertSame; public class TypeTest { @@ -12,19 +10,23 @@ public class TypeTest { // Test basic properties and GLB @Test public void testTypeAdHoc() { + Assert.assertEquals( Type.BOTTOM, TypeInteger.TRUE.meet(TypeNil.NIL) ); + Assert.assertEquals( Type.BOTTOM, TypeInteger.TOP.meet(TypeNil.NIL) ); + + TypeStruct s1 = TypeStruct.make("s1", new Field[]{ Field.make("a", TypeInteger.BOT,-1, false), Field.make("b", TypeInteger.BOT,-2, false) }); TypeStruct s2 = TypeStruct.make("s2", new Field[]{ Field.make("a", TypeInteger.BOT,-3, false), Field.make("b", TypeInteger.BOT,-4, false) }); - Assert.assertEquals(s1, s1.glb()); + Assert.assertEquals(s1.makeRO(), s1.glb()); Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1.makeRO(), s1.dual().glb()); - TypeMem m1 = TypeMem.make(1,TypeInteger.ZERO); + TypeMem m1 = TypeMem.make(1,TypeNil.NIL); TypeMem m2 = TypeMem.make(2,TypeInteger.U16); - TypeMem m3 = TypeMem.make(3,TypeFloat.BOT); + TypeMem m3 = TypeMem.make(3,TypeFloat.F64); TypeMem m4 = TypeMem.make(4,TypeInteger.BOT); Assert.assertNotEquals(m1, m2); @@ -32,12 +34,12 @@ public class TypeTest { Assert.assertNotEquals(m3, m4); Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); - Assert.assertEquals(TypeMem.make(-1,TypeInteger.U16), m1.meet(m2)); - Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); + Assert.assertEquals(TypeMem .BOT, m1.meet(m2)); + Assert.assertEquals(TypeMem.make(0,Type.BOTTOM), m1.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(TypeMem.make(1,TypeInteger.BOT), m1.glb()); - Assert.assertEquals(TypeMem.make(1,TypeInteger.ZERO), m1.dual()); + Assert.assertEquals(TypeMem.make(1,Type.BOTTOM), m1.glb()); + Assert.assertEquals(TypeMem.make(1,Type.XNIL), m1.dual()); Assert.assertEquals(m4.dual(), m4.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); @@ -45,34 +47,34 @@ public class TypeTest { TypeMemPtr ptr2 = TypeMemPtr.make(s2); Assert.assertEquals(s2, ptr2._obj); - TypeMemPtr ptr1nil = TypeMemPtr.make(s1, true); + TypeMemPtr ptr1nil = TypeMemPtr.makeNullable(s1); Assert.assertEquals(s1, ptr1nil._obj); - Assert.assertTrue(ptr1nil._nil); - Assert.assertFalse(ptr1nil._obj==null); - TypeMemPtr ptr2nil = TypeMemPtr.make(s2, true); + Assert.assertTrue( ptr1nil.nullable() ); + Assert.assertNotNull( ptr1nil._obj ); + TypeMemPtr ptr2nil = TypeMemPtr.makeNullable( s2); Assert.assertEquals(s2, ptr2nil._obj); Assert.assertNotEquals(ptr1, ptr2); Assert.assertNotEquals(ptr1, ptr1.glb()); - Assert.assertEquals(ptr1nil.withAccess(true), ptr1.glb()); + Assert.assertEquals(ptr1nil.makeFrom(s1.glb()).makeRO(), ptr1.glb()); Assert.assertEquals(ptr1, ptr1.dual().dual()); Assert.assertEquals(ptr1.glb().makeFrom(s1.dual().glb()), ptr1.dual().glb()); - Assert.assertEquals(TypeMemPtr.make(TypeStruct.BOT,true).withAccess(false), ptr1.meet(ptr2nil)); - Assert.assertEquals(ptr1nil, ptr1.meet(TypeMemPtr.NULLPTR)); + Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT).withAccess(false), ptr1.meet(ptr2nil)); + Assert.assertEquals(ptr1nil, ptr1.meet(TypeNil.NIL)); TypeMemPtr TOP = TypeMemPtr.TOP; - TypeMemPtr BOT = TypeMemPtr.make(TypeStruct.BOT,true ); - TypeMemPtr PTR = TypeMemPtr.make(TypeStruct.BOT,false); - TypeMemPtr NULL = TypeMemPtr.NULLPTR; + TypeMemPtr BOT = TypeMemPtr.makeNullable(TypeStruct.BOT); + TypeMemPtr PTR = TypeMemPtr.make(TypeStruct.BOT); + Type NULL = TypeNil.NIL; Type PTR_meet_NULL = NULL.meet(PTR); Assert.assertEquals(BOT, PTR_meet_NULL); Type ptr1_meet_ptr2 = ptr1.meet(ptr2); Assert.assertEquals(PTR.withAccess(false), ptr1_meet_ptr2); Type NULL_join_ptr1 = NULL.join(ptr1); - Assert.assertEquals(TOP, NULL_join_ptr1); + Assert.assertEquals(TypePtr.XNPTR, NULL_join_ptr1); Type NULL_join_PTR = PTR.join(NULL); - Assert.assertEquals(TOP, NULL_join_PTR); + Assert.assertEquals(TypePtr.XNPTR, NULL_join_PTR); Type ptr1_dual = ptr1.dual(); Type nullableptr1_dual = ptr1nil.dual(); } @@ -153,5 +155,4 @@ public class TypeTest { assertSame(TypeStruct.S1,d1); } - } diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 0721402f..7dbc551e 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -4,8 +4,6 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.lang.invoke.MethodHandle; -import java.lang.invoke.MethodHandles; import java.util.*; public class Evaluator { @@ -207,7 +205,8 @@ public class Evaluator { for (int i=0; i (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 MemMergeNode mem -> null; case ReadOnlyNode ro -> val(ro.in(1)); + case CallNode call -> Utils.TODO(); // should not reach here, go the IfNode route default -> throw new AssertionError("Unexpected node " + node); }; } @@ -326,31 +326,33 @@ public class Evaluator { for(; i 0 && region.nIns() > exit; - block = block.next()[0]; - assert block != null; - for (; i < block.nodes().length; i++) { - if (!(block.nodes()[i] instanceof PhiNode)) break; - phiCache.add(val(block.nodes()[i].in(exit))); - } - for (i=0; i 0 && region.nIns() > exit; + block = block.next()[0]; + assert block != null; + for (; i < block.nodes().length; i++) { + if (!(block.nodes()[i] instanceof PhiNode phi)) break; + var val = region instanceof FunNode fun && "main".equals(fun.sig()._name) && ((ParmNode)phi)._idx==2 && exit==1 + ? parameter + : val(phi.in(exit)); + phiCache.add(val); + } + for (i=0; i> readers = new HashMap<>(); - /** * A basic block with a schedule of the containing nodes. * @@ -89,6 +87,9 @@ public class Scheduler { this.entry = entry; this.prev = prev; } + BasicBlock(Node entry, BasicBlock prev) { + this(entry,prev.depth+1,prev); + } } @@ -254,7 +255,7 @@ public class Scheduler { // but they did not refine the placement // so do that now. var mem = l.in(1); - for(var out : l.antiDeps()) { + for(var out : mem._outputs) { if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -272,9 +273,13 @@ public class Scheduler { for(var in:data.node._inputs) { if (in!=null) update(d(in), data.block); } - var loads = readers.get(data.node); - if (loads != null) - for (var load : loads) decUsers(load); + if (data.node instanceof StoreNode s) { + // Store nodes have anti-deps to load nodes. + // So decrease the uses of these loads when the store is placed. + for (var out: s.in(1)._outputs) { + if (out instanceof LoadNode) od(out).ifPresent(this::decUsers); + } + } } // Now all nodes should be placed and have a block assigned @@ -356,35 +361,29 @@ public class Scheduler { var queue = new Stack(); var phiQueue = new Stack(); queue.push(d(start)); - int depth = 0; while (!queue.isEmpty()) { var data = queue.pop(); var node = data.node; assert node instanceof CFGNode; - BasicBlock block; - switch (node) { - case StartNode s: - block = new BasicBlock(s, depth++); - break; - case LoopNode l: - block = new BasicBlock(l, depth++, d(l.in(1)).block); - break; - case RegionNode r: + BasicBlock block = switch (node) { + case StartNode s -> new BasicBlock(s, 0); + case LoopNode l -> new BasicBlock(l, d(l.in(1)).block); + case RegionNode r -> { var prev = new ArrayList(); + int depth = 0; for(int i=1; iprev.add(d.block)); + if( !od(r.in(i)).isPresent() ) continue; + BasicBlock bb = d(r.in(i)).block; + prev.add(bb); + depth = Math.max(depth,bb.depth); } - block = new BasicBlock(r, depth++, prev.toArray(BasicBlock[]::new)); - break; - case IfNode i: - block = d(i.in(0)).block; - break; - case ReturnNode r: - block = d(r.in(0)).block; - break; - default: - block = new BasicBlock(node, depth++, d(node.in(0)).block); + yield new BasicBlock(r, depth+1, prev.toArray(BasicBlock[]::new)); } + case IfNode i -> d(i.in(0)).block; + case ReturnNode ret -> d(ret .in(0)).block; + case CallNode call -> throw Utils.TODO(); + default -> new BasicBlock(node, d(node.in(0)).block); + }; data.block = block; if (node instanceof RegionNode r) { // Regions might have phis which need to be scheduled. @@ -399,10 +398,17 @@ public class Scheduler { } } } - if (!(node instanceof ReturnNode)) + if( node instanceof FunNode fun ) { + // Cannot find CFG user from fun via a naive search, because always find + // Return but Return is not always the one CFG user. + CFGNode n = fun.uctrl(); + assert isCFGNodeReady(n) && d(n).block==null; + queue.push(d(n)); + } else if( !(node instanceof ReturnNode) ) { for (Node n : node._outputs) if(n instanceof CFGNode && 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)); } @@ -440,13 +446,14 @@ public class Scheduler { private void doMarkAlive(Node node) { var cfgQueue = new Stack(); var dataQueue = new Stack(); + var mem = new Stack(); markAlive(cfgQueue, node, true); // Mark all CFG nodes. while (!cfgQueue.isEmpty()) { var data = cfgQueue.pop(); node = data.node; assert node instanceof CFGNode; - if (!(node instanceof ReturnNode)) { + if (!(node instanceof ReturnNode) ) { for (var out : node._outputs) if (out!=null && out instanceof CFGNode && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } for (var in : node._inputs) if(in!=null && !(in instanceof CFGNode) && isNotXCtrl(in)) markAlive(dataQueue, in, false); @@ -464,16 +471,16 @@ public class Scheduler { } else { for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false); } + if (node instanceof StoreNode) mem.push(data); + } + // Handle store nodes and increase load with an anti-dep to the store. + while (!mem.isEmpty()) { + var data = mem.pop(); + node = data.node; + for(var out:node.in(1)._outputs) { + if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); + } } - // Writes, including New behind an aggregate, schedule before their - // anti-dependent reads in this reverse scheduling pass. - for (var load : data.values()) - if (load.node instanceof LoadNode l) - for (var use : l.antiDeps()) - if ((use instanceof StoreNode || use instanceof NewNode) && data.containsKey(use)) { - load.users++; - readers.computeIfAbsent(use,k->new ArrayList<>()).add(load); - } } /** @@ -496,15 +503,18 @@ public class Scheduler { /** * Find the CFG output of a node * @param node The node - * @return THe CFG output of the node. + * @return The CFG output of the node. */ - private static Node findSingleCFGOut(Node node) { + private static CFGNode 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 FunNode fun && "main".equals(fun.sig()._name) ) + return fun; return null; } + if( node instanceof FunNode fun ) return fun.uctrl(); assert node._outputs.stream().filter(x -> x instanceof CFGNode).limit(2).count()<=1; - for(var n:node._outputs) if(n instanceof CFGNode) return n; + for(var n:node._outputs) if(n instanceof CFGNode cfg) return cfg; return null; } @@ -558,7 +568,7 @@ public class Scheduler { case null -> new Block(arr, null, -1, new Block[0]); case IfNode i -> new Block(arr, i, -1, new Block[2]); case RegionNode r -> new Block(arr, r, r._inputs.find(prev), new Block[1]); - case ReturnNode r -> new Block(arr, r, -1, new Block[0]); + case ReturnNode r -> new Block(arr, r , -1, new Block[0]); default -> throw new AssertionError("Unexpected block exit node"); }); } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 7dcb88e5..a5634e82 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,10 +1,9 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.Eval2; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.StopNode; - import java.util.ArrayList; import java.util.Objects; import java.util.Random; @@ -46,8 +45,8 @@ public class Fuzzer { e.printStackTrace(System.out); System.out.println("========== Seed =========="); System.out.println(seed); - System.out.println("========== Code ==========="); - System.out.println(script); + //System.out.println("========== Code ==========="); + //System.out.println(script); System.out.println("========= Reduced ========="); System.out.println(Reducer.reduce(script, e, reproducer)); System.out.println("==========================="); @@ -56,13 +55,6 @@ public class Fuzzer { private static boolean neq(Object a, Object b) { if (Objects.equals(a, b)) return false; - if (a instanceof Evaluator.Obj ea && b instanceof Evaluator.Obj eb) { - if (ea.struct() != eb.struct()) return true; - for(int i=0;i