From 1fd6f46cca3541861d56f3710728d34791beedf8 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 8 Mar 2025 11:01:01 -0800 Subject: chapter 21 encodings first push --- .../java/com/seaofnodes/simple/BrainFuckTest.java | 71 ++ .../java/com/seaofnodes/simple/Chapter01Test.java | 95 +++ .../java/com/seaofnodes/simple/Chapter02Test.java | 61 ++ .../java/com/seaofnodes/simple/Chapter03Test.java | 73 ++ .../java/com/seaofnodes/simple/Chapter04Test.java | 131 ++++ .../java/com/seaofnodes/simple/Chapter05Test.java | 186 +++++ .../java/com/seaofnodes/simple/Chapter06Test.java | 305 ++++++++ .../java/com/seaofnodes/simple/Chapter07Test.java | 222 ++++++ .../java/com/seaofnodes/simple/Chapter08Test.java | 208 +++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 296 +++++++ .../java/com/seaofnodes/simple/Chapter10Test.java | 397 ++++++++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 551 +++++++++++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 61 ++ .../java/com/seaofnodes/simple/Chapter13Test.java | 261 +++++++ .../java/com/seaofnodes/simple/Chapter14Test.java | 226 ++++++ .../java/com/seaofnodes/simple/Chapter15Test.java | 383 +++++++++ .../java/com/seaofnodes/simple/Chapter16Test.java | 261 +++++++ .../java/com/seaofnodes/simple/Chapter17Test.java | 555 +++++++++++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 370 +++++++++ .../java/com/seaofnodes/simple/Chapter19Test.java | 400 ++++++++++ .../java/com/seaofnodes/simple/Chapter20Test.java | 196 +++++ .../java/com/seaofnodes/simple/Chapter21Test.java | 45 ++ .../src/test/java/com/seaofnodes/simple/Eval2.java | 450 +++++++++++ .../java/com/seaofnodes/simple/FuzzerWrap.java | 43 + .../src/test/java/com/seaofnodes/simple/Main.java | 19 + .../java/com/seaofnodes/simple/MergeSortTest.java | 67 ++ .../java/com/seaofnodes/simple/SchedulerTest.java | 74 ++ .../test/java/com/seaofnodes/simple/TypeTest.java | 158 ++++ .../com/seaofnodes/simple/evaluator/Evaluator.java | 383 +++++++++ .../com/seaofnodes/simple/evaluator/Scheduler.java | 606 ++++++++++++++ .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 174 +++++ .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 111 +++ .../java/com/seaofnodes/simple/fuzzer/Reducer.java | 176 +++++ .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 869 +++++++++++++++++++++ .../test/java/com/seaofnodes/simple/progs/fcn.smp | 15 + .../test/java/com/seaofnodes/simple/progs/fcn2.smp | 5 + .../test/java/com/seaofnodes/simple/progs/fcn3.smp | 42 + .../java/com/seaofnodes/simple/progs/sieve.smp | 32 + 38 files changed, 8578 insertions(+) create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter01Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter02Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter03Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter04Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter05Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter06Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter07Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter08Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter11Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter13Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Eval2.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/FuzzerWrap.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/Main.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/SchedulerTest.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/TypeTest.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/fcn.smp create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/fcn2.smp create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/fcn3.smp create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/sieve.smp (limited to 'chapter21/src/test/java') diff --git a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java new file mode 100644 index 00000000..c23bb301 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -0,0 +1,71 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import java.nio.charset.StandardCharsets; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; +import static com.seaofnodes.simple.Main.PORTS; + +public class BrainFuckTest { + + @Test + public void testBrainfuck() { + var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(StandardCharsets.UTF_8); + var encoded = new StringBuilder("u8[] !program = new u8[").append(program.length).append("];"); + for (int i = 0; i < program.length; i++) { + int value = program[i] & 0xFF; + encoded.append("program[").append(i).append("] = ").append(value).append(";"); + } + + String src = encoded + """ + +int d = 0; +u8[] !output = new u8[0]; +u8[] !data = new u8[100]; + +for( int pc = 0; pc < program#; pc++ ) { + var command = program[pc]; + if (command == 62) { + d++; + } else if (command == 60) { + d--; + } else if (command == 43) { + data[d]++; + } else if (command == 45) { + data[d]--; + } else if (command == 46) { + // Output a byte; increase the output array size + var old = output; + output = new u8[output# + 1]; + 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( int d = 1; d > 0; ) { + command = program[++pc]; + if (command == 91) d++; + if (command == 93) d--; + } + } + } else if (command == 93) { + if (data[d]) { + for( int d = 1; d > 0; ) { + command = program[--pc]; + if (command == 93) d++; + if (command == 91) d--; + } + } + } +} +return output; +"""; + Chapter20Test.testCPU(src,"x86_64_v2", "SystemV",28,null); + Chapter20Test.testCPU(src,"riscv" , "SystemV",18,null); + Chapter20Test.testCPU(src,"arm" , "SystemV",12,null); + //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..cddbdfcf --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,95 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + CodeGen code = new CodeGen("return 1;").parse(); + Node expr = code.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(code._start,con.in(0)); + assertEquals(TypeInteger.constant(1), con._type); + } else { + fail(); + } + } + + @Test + public void testZero() { + 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); + } + + @Test + public void testBad1() { + try { + new CodeGen("ret;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'ret'",e.getMessage()); + } + } + + @Test + public void testBad2() { + try { + new CodeGen("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new CodeGen("return - -12;").parse()._stop.print()); + } + + @Test + public void testBad4() { + try { + new CodeGen("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new CodeGen("return -100;").parse()._stop.print()); + } + + @Test + public void testBad6() { + try { + new CodeGen("return100;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'return100'",e.getMessage()); + } + } + + @Test + public void testBad7() { + try { + new CodeGen("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected: }",e.getMessage()); + } + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..631e1487 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + CodeGen code = new CodeGen("return 1+2*3+-5;"); + code.parse(); // No more disable peepholes + assertEquals("return 2;", code.print()); + } + + @Test + public void testAddPeephole() { + CodeGen code = new CodeGen("return 1+2;"); + code.parse(); + assertEquals("return 3;", code.print()); + } + + @Test + public void testSubPeephole() { + CodeGen code = new CodeGen("return 1-2;"); + code.parse(); + assertEquals("return -1;", code.print()); + } + + @Test + public void testMulPeephole() { + CodeGen code = new CodeGen("return 2*3;"); + code.parse(); + assertEquals("return 6;", code.print()); + } + + @Test + public void testDivPeephole() { + CodeGen code = new CodeGen("return 6/3;"); + code.parse(); + assertEquals("return 2;", code.print()); + } + + @Test + public void testMinusPeephole() { + CodeGen code = new CodeGen("return 6/-3;"); + code.parse(); + assertEquals("return -2;", code.print()); + } + + @Test + public void testExample() { + CodeGen code = new CodeGen("return 1+2*3+-5;"); + code.parse(); + assertEquals("return 2;", code.print()); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..c4e4c91e --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + CodeGen code = new CodeGen("int a=1; return a;"); + code.parse(); assertEquals("return 1;", code.print()); + } + + @Test + public void testVarAdd() { + CodeGen code = new CodeGen("int a=1; int b=2; return a+b;"); + code.parse(); + assertEquals("return 3;", code.print()); + } + + @Test + public void testVarScope() { + 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 testVarScopeNoPeephole() { + CodeGen code = new CodeGen("int a=1; int b=2; int !c=0; { int b=3; c=a+b; } return c; "); + code.parse(); // Peepholes always run now + assertEquals("return 4;", code.print()); + } + + @Test + public void testVarDist() { + 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 CodeGen("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testRedeclareVar() { + try { + new CodeGen("int a=1; int b=2; int c=0; int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Redefining name 'b'",e.getMessage()); + } + } + + @Test + public void testBad1() { + try { + 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/chapter21/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..c6199193 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,131 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter04Test { + + @Test + public void testPeephole() { + CodeGen code = new CodeGen("return 1+arg+2; "); + code.parse(); + assertEquals("return (arg+3);", code.print()); + } + + @Test + public void testPeephole2() { + CodeGen code = new CodeGen("return (1+arg)+2;"); + code.parse(); + assertEquals("return (arg+3);", code.print()); + } + + @Test + public void testAdd0() { + CodeGen code = new CodeGen("return 0+arg;"); + code.parse(); + assertEquals("return arg;", code.print()); + } + + @Test + public void testAddAddMul() { + CodeGen code = new CodeGen("return arg+0+arg;"); + code.parse(); + assertEquals("return (arg<<1);", code.print()); + } + + @Test + public void testPeephole3() { + CodeGen code = new CodeGen("return 1+arg+2+arg+3; "); + code.parse(); + assertEquals("return ((arg<<1)+6);", code.print()); + } + + @Test + public void testMul1() { + CodeGen code = new CodeGen("return 1*arg;"); + code.parse(); + assertEquals("return arg;", code.print()); + } + + @Test + public void testVarArg() { + CodeGen code = new CodeGen("return arg; "); + code.parse(); + assertTrue(code.ctrl() instanceof FunNode); + assertTrue(code.expr() instanceof ParmNode); + } + + // Adding functions means `main` does not constant fold the incoming arg value + @Ignore @Test + public void testConstantArg() { + CodeGen code = new CodeGen("return arg; ", TypeInteger.constant(2), 123L).parse(); + assertEquals("return 2;", code.expr().in(1).toString()); + } + + @Test + public void testCompEq() { + CodeGen code = new CodeGen("return 3==3; "); + code.parse(); + assertEquals("return 1;", code.print()); + } + + @Test + public void testCompEq2() { + CodeGen code = new CodeGen("return 3==4; "); + code.parse(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testCompNEq() { + CodeGen code = new CodeGen("return 3!=3; "); + code.parse(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testCompNEq2() { + CodeGen code = new CodeGen("return 3!=4; "); + code.parse(); + assertEquals("return 1;", code.print()); + } + + @Test + public void testBug1() { + 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() { + CodeGen code = new CodeGen("int !a=arg+1; a=a; return a; "); + code.parse(); + assertEquals("return (arg+1);", code.print()); + } + + @Test + public void testBug3() { + try { new CodeGen("inta=1; return a;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Undefined name 'inta'",e.getMessage()); } + } + + @Test + public void testBug4() { + CodeGen code = new CodeGen("return -arg;"); + code.parse(); + assertEquals("return (-arg);", code.print()); + } + + @Test + public void testBug5() { + CodeGen code = new CodeGen("return arg--2;"); + code.parse(); + assertEquals("return (arg--2);", code.print()); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..a584ad5a --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,186 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter05Test { + + @Test + public void testIfStmt() { + CodeGen code = new CodeGen( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; +} +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,(arg+2),(arg-3));", code.print()); + } + + @Test + public void testTest() { + CodeGen code = new CodeGen( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,4,3);", code.print()); + } + + @Test + public void testReturn2() { + CodeGen code = new CodeGen( +""" +if( arg==1 ) + return 3; +else + return 4; +"""); + code.parse(); + assertEquals("return Phi(Region,3,4);", code.print()); + } + + @Test + public void testIfMergeB() { + CodeGen code = new CodeGen( +""" +int a=arg+1; +int b=0; +if( arg==1 ) + b=a; +else + b=a+1; +return a+b;"""); + code.parse().opto(); + assertEquals("return ((arg<<1)+Phi(Region,2,3));", code.print()); + } + + @Test + public void testIfMerge2() { + CodeGen code = new CodeGen( +""" +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b;"""); + code.parse().opto(); + assertEquals("return ((Phi(Region,(arg<<1),arg)+arg)+Phi(Region,4,5));", code.print()); + } + + @Test + public void testMerge3() { + CodeGen code = new CodeGen( +""" +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,Phi(Region,2,3),Phi(Region,4,5));", code.print()); + } + + @Test + public void testMerge4() { + CodeGen code = new CodeGen( +""" +int a=0; +int b=0; +if( arg ) + a=1; +if( arg==0 ) + b=2; +return arg+a+b; +"""); + code.parse().opto(); + assertEquals("return ((arg+Phi(Region,1,0))+Phi(Region,2,0));", code.print()); + } + + @Test + public void testMerge5() { + CodeGen code = new CodeGen( +""" +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a; +"""); + code.parse().opto(); + assertEquals("return (arg==Phi(Region,3,2));", code.print()); + } + + @Test + public void testTrue() { + CodeGen code = new CodeGen("return true;").parse(); + assertEquals("return 1;",code.print()); + } + + @Test + public void testHalfDef() { + try { new CodeGen("if( arg==1 ) int b=2; return b;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Cannot define a 'b' on one arm of an if",e.getMessage()); } + } + + @Test + public void testHalfDef2() { + try { new CodeGen("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Undefined name 'b'",e.getMessage()); } + } + + @Test + public void testRegress1() { + try { new CodeGen("if(arg==2) int a=1; else int b=2; return a;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Cannot define a 'a' on one arm of an if",e.getMessage()); } + } + + + @Test + public void testBadNum() { + try { new CodeGen("return 1-;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); } + } + + @Test + public void testKeyword1() { + try { new CodeGen("int true=0; return true;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Expected an identifier, found 'true'",e.getMessage()); } + } + + @Test + public void testKeyword2() { + try { new CodeGen("int else=arg; if(else) else=2; else else=1; return else;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Expected an identifier, found 'else'",e.getMessage()); } + } + + @Test + public void testKeyword3() { + try { new CodeGen("int a=1; ififif(arg);a=2;return a;").parse(); fail(); } + catch( RuntimeException e ) { assertEquals("Undefined name 'ififif'",e.getMessage()); } + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..24d12921 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,305 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter06Test { + + @Test + public void testPeepholeReturn() { + CodeGen code = new CodeGen(""" +if( true ) return 2; +return 1; +"""); + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertTrue(code.ctrl() instanceof FunNode); + } + + @Test + public void testPeepholeRotate() { + 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 +"""); + code.parse().opto(); + assertEquals("return 1;", code.print()); + } + + @Test + public void testPeepholeCFG() { + CodeGen code = new CodeGen( +""" +int a=1; +if( true ) + a=2; +else + a=3; +return a; +"""); + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertTrue(code.ctrl() instanceof FunNode); + } + + @Test + public void testIfIf() { + CodeGen code = new CodeGen( +""" +int a=1; +if( arg!=1 ) + a=2; +else + a=3; +int b=4; +if( a==2 ) + b=42; +else + b=5; +return b; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,42,5);", code.print()); + } + + @Test + public void testIfArgIf() { + CodeGen code = new CodeGen( +""" +int a=1; +if( 1==1 ) + a=2; +else + a=3; +int b=4; +if( arg==2 ) + b=a; +else + b=5; +return b;"""); + code.parse().opto(); + assertEquals("return Phi(Region,2,5);", code.print()); + } + + @Test + public void testMerge3With2() { + CodeGen code = new CodeGen( +""" +arg=2; +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(2), 123L).parse().opto(); + assertEquals("return 5;", code.print()); + } + + @Test + public void testMerge3With1() { + CodeGen code = new CodeGen( +""" +arg=1; +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(1), 123L).parse().opto(); + assertEquals("return 3;", code.print()); + } + + @Test + public void testMerge3Peephole() { + CodeGen code = new CodeGen( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,3,Phi(Region,4,5));", code.print()); + } + + @Test + public void testMerge3Peephole1() { + CodeGen code = new CodeGen( +""" +arg=1; +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(1), 123L); + code.parse().opto(); + assertEquals("return 3;", code.print()); + } + + @Test + public void testMerge3Peephole3() { + CodeGen code = new CodeGen( +""" +arg=3; +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(3), 123L); + code.parse().opto(); + assertEquals("return 4;", code.print()); + } + + @Test + public void testDemo1NonConst() { + CodeGen code = new CodeGen(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,4,1);", code.print()); + } + + + @Test + public void testDemo1True() { + CodeGen code = new CodeGen( +""" +arg=1; +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(1), 123L); + code.parse().opto(); + assertEquals("return 4;", code.print()); + } + + @Test + public void testDemo1False() { + CodeGen code = new CodeGen( +""" +arg=0; +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(0), 123L); + code.parse().opto(); + assertEquals("return 1;", code.print()); + } + + @Test + public void testDemo2NonConst() { + CodeGen code = new CodeGen(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +"""); + code.parse().opto(); + assertEquals("return (Phi(Region,Phi(Region,2,3),0)+Phi(Region,3,1));", code.print()); + } + + + @Test + public void testDemo2True() { + CodeGen code = new CodeGen( +""" +arg=1; +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(1), 123L); + code.parse().opto(); + assertEquals("return 6;", code.print()); + } + + @Test + public void testDemo2arg2() { + CodeGen code = new CodeGen( +""" +arg=2; +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(2), 123L); + code.parse().opto(); + assertEquals("return 5;", code.print()); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter07Test.java new file mode 100644 index 00000000..88554323 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -0,0 +1,222 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter07Test { + + @Test + public void testExample() { + CodeGen code = new CodeGen( +""" +while(arg < 10) { + arg = arg + 1; +} +return arg; +"""); + code.parse(); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testRegression() { + CodeGen code = new CodeGen( +""" +int a = 1; +if(arg){}else{ + while(a < 10) { + a = a + 1; + } +} +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,1,Phi(Loop,1,(Phi_a+1)));", code.print()); + } + + @Test + public void testWhileNested() { + CodeGen code = new CodeGen( +""" +int sum = 0; +int i = 0; +while(i < arg) { + i = i + 1; + int j = 0; + while( j < arg ) { + sum = sum + j; + j = j + 1; + } +} +return sum; +"""); + 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() { + CodeGen code = new CodeGen( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; +} +return b; +"""); + code.parse(); + assertEquals("return Phi(Loop,2,Phi(Region,Phi_b,4));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhileNestedIfAndInc() { + CodeGen code = new CodeGen( +""" +int a = 1; +int b = 2; +while(a < 10) { + if (a == 2) a = 3; + else b = 4; + b = b + 1; + a = a + 1; +} +return b; +"""); + 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() { + CodeGen code = new CodeGen( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + code.parse(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhilePeep() { + CodeGen code = new CodeGen( +""" +int a = 1; +while(a < 10) { + a = a + 1; + a = a + 2; +} +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhile2() { + CodeGen code = new CodeGen( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + code.parse(); + assertEquals("return Phi(Loop,1,2);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhile2Peep() { + CodeGen code = new CodeGen( +""" +int a = 1; +while(arg) a = 2; +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,1,2);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhile3() { + CodeGen code = new CodeGen( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + code.parse(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhile3Peep() { + CodeGen code = new CodeGen( +""" +int a = 1; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhile4() { + CodeGen code = new CodeGen( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + code.parse(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testWhile4Peep() { + CodeGen code = new CodeGen( +""" +int a = 1; +int b = 2; +while(a < 10) { + int b = a + 1; + a = b + 2; +} +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter08Test.java new file mode 100644 index 00000000..7e90d484 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -0,0 +1,208 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import org.junit.Assert; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter08Test { + + @Test + public void testEx6() { + CodeGen code = new CodeGen( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + break; + if (arg == 6) + break; +} +return arg; + """); + 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() { + CodeGen code = new CodeGen( + """ +int a = 1; +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 7) + continue; + a = a + 1; +} +return a; + """); + 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() { + CodeGen code = new CodeGen( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + break; +} +return arg; + """); + 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() { + CodeGen code = new CodeGen( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 6) + break; +} +return arg; + """); + 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() { + CodeGen code = new CodeGen( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; + if (arg == 6) + continue; +} +return arg; + """); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + + @Test + public void testEx1() { + CodeGen code = new CodeGen( + """ +while(arg < 10) { + arg = arg + 1; + if (arg == 5) + continue; +} +return arg; + """); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); + } + + @Test + public void testRegress1() { + CodeGen code = new CodeGen( + """ +while( arg < 10 ) { + int a = arg+2; + if( a > 4 ) + break; +} +return arg; + """); + code.parse().opto(); + assertEquals("return arg;", code.print()); + } + + @Test + public void testRegress2() { + 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 + public void testBreakOutsideLoop() { + try { + new CodeGen(""" +if(arg <= 10) { + break; + arg = arg + 1; +} +return arg; +""").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("No active loop for a break or continue",e.getMessage()); + } + } + + @Test + public void testRegress3() { + CodeGen code = new CodeGen(""" +while(arg < 10) { + break; +} +return arg; +"""); + code.parse().opto(); + assertEquals("return arg;", code.print()); + } + + @Test + public void testRegress4() { + CodeGen code = new CodeGen(""" +int a = 1; +while(arg < 10) { + a = a + 1; + if (arg > 2) { + int a = 17; + break; + } +} +return a; +"""); + 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() { + CodeGen code = new CodeGen(""" +int a = 1; +while(1) { + a = a + 1; + if (a<10) continue; + break; +} +return a; +"""); + code.parse().opto(); + assertEquals("return (Phi(Loop,1,Add)+1);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode prj && prj._idx==1 ); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java new file mode 100644 index 00000000..401f346f --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -0,0 +1,296 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter09Test { + + @Test + @Ignore + public void testJig() { + CodeGen code = new CodeGen(""" +int v0=0; +arg=0; +while(v0) { + while(1) if(arg*arg*0==0) {} + while(0) {} + arg=1; +} +return 0; + """); + code.parse().opto(); + } + + @Test + public void testGVN1() { + CodeGen code = new CodeGen( + """ +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + """); + code.parse().opto(); + assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + Assert.assertEquals( "2", Eval2.eval(code, 1)); + Assert.assertEquals("23", Eval2.eval(code, 11)); + } + + @Test + public void testGVN2() { + 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() { + CodeGen code = new CodeGen(""" +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+2));", code.print()); + Assert.assertEquals("11", Eval2.eval(code, 1)); + } + + @Test + public void testWorklist2() { + CodeGen code = new CodeGen( + """ +int cond = 0; +int one = 1; +while (arg < 10) { + if (cond) one = 2; + arg = arg + one*3 + 1; +} +return arg; + """); + code.parse().opto(); + assertEquals("return Phi(Loop,arg,(Phi_arg+4));", code.print()); + Assert.assertEquals("13", Eval2.eval(code, 1)); + } + + @Test + public void testWorklist3() { + CodeGen code = new CodeGen( + """ +int v1 = 0; +int v2 = 0; +int v3 = 0; +int v4 = 0; +int v5 = 0; +int v6 = 0; +int v7 = 0; +int v8 = 0; +while (arg) { + if (v1) v2 = 1; + if (v2) v3 = 1; + if (v3) v4 = 1; + if (v4) v5 = 1; + if (v5) v6 = 1; + if (v6) v7 = 1; + if (v7) v8 = 1; + arg = arg + v8 + 1; +} +return arg; + """); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testRegionPeepBug() { + CodeGen code = new CodeGen( + """ +int v0=0; +int v1=0; +while(v1+arg) { + arg=0; + int v2=v0; + while(arg+1) {} + v0=1; + v1=v2; +} + """); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testWhile0() { + CodeGen code = new CodeGen("while(0) continue; if(0) arg=0;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testWhile1() { + CodeGen code = new CodeGen(""" +if(0) while(0) { + int arg=arg; + while(0) {} +} +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + + @Test + public void testPrecedence() { + CodeGen code = new CodeGen("return 3-1+2;"); + code.parse().opto(); + assertEquals("return 4;", code.print()); + } + + @Test + public void testSwap2() { + CodeGen code = new CodeGen("return 1+(1+1);"); + code.parse().opto(); + assertEquals("return 3;", code.print()); + } + + + @Test + public void testFuzz0() { + CodeGen code = new CodeGen(""" +int one = 1; +int a = 0; +int zero = 0; +while(arg) { + a = -(one + a + 2); + arg = arg + 1; + one = one + zero; +} +return a; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(-(Phi_a+3)));", code.print()); + } + + @Test + public void testFuzz1() { + CodeGen code = new CodeGen(""" +while(1) {} +while(arg) break; +while(arg) arg=0; +arg=0; +int v0=0!=0<-0; +return -0+0+0; +"""); + code.parse().opto(); + assertEquals("return Top;", code.print()); + } + + + @Test + public void testFuzz2() { + CodeGen code = new CodeGen("return 0+-0;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testFuzz3() { + 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() { + CodeGen code = new CodeGen(""" +while(1) { + arg=0<=0; + if(1<0) while(arg==-0) arg=arg-arg; +} +"""); + code.parse().opto(); + assertEquals("return Top;", code.print()); + } + + @Test + public void testFuzz5() { + CodeGen code = new CodeGen(""" +{ + int v0=0; + while(1) + int v1=0--0; + while(v0) + break; + while(-v0) { + while(0+0+v0) continue; + break; + } + if(-0!=-0+0+v0) while(0+0+0+0) + break; +} +return 0!=0; +"""); + code.parse().opto(); + assertEquals("return Top;", code.print()); + } + + @Test + public void testFuzz6() { + CodeGen code = new CodeGen( +""" +int v0=0; +while(0==1) while(v0) + v0=1+v0; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testFuzz7() { + CodeGen code = new CodeGen(""" +while(1) {} +int v0=0; +while(v0) + {} +int v1=0; +while(1) + v1=1; +return v1+v0; + """); + code.parse().opto(); + assertEquals("return Top;", code.print()); + } + + @Test + public void testFuzz8() { + CodeGen code = new CodeGen("while(arg) arg = arg - 1; return arg;"); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testMeet() { + Type t1 = Type.TOP; + Type t2 = TypeInteger.TOP; + Assert.assertEquals(TypeInteger.TOP, t1.meet(t2)); + Assert.assertEquals(TypeInteger.TOP, t2.meet(t1)); + t1 = Type.BOTTOM; + t2 = TypeInteger.BOT; + Assert.assertEquals(Type.BOTTOM, t1.meet(t2)); + Assert.assertEquals(Type.BOTTOM, t2.meet(t1)); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java new file mode 100644 index 00000000..1253e4a6 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -0,0 +1,397 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter10Test { + + @Test + public void testFuzzer() { + CodeGen code = new CodeGen( +""" +int a = arg/3; +int b = arg*5; +int x = arg*7; +int y = arg/11; +int p; int g; int h; +if( (arg/13)==0 ) { + p = x + y; + g = x; + h = y; +} else { + p = a + b; + g = a; + h = b; +} +int r = g+h; +return p-r; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testStruct() { + CodeGen code = new CodeGen(""" +struct Bar { + int a; + int b; +}; +struct Foo { + int x; +}; +Foo? foo = null; +Bar !bar = new Bar; +bar.a = 1; +bar.a = 2; +return bar.a; +"""); + code.parse().opto(); + assertEquals("return 2;", code.print()); + } + + @Test + public void testExample() { + CodeGen code = new CodeGen(""" +struct Vector2D { int x; int y; }; +Vector2D !v = new Vector2D; +v.x = 1; +if (arg) + v.y = 2; +else + v.y = 3; +return v; +"""); + code.parse().opto(); + assertEquals("return Vector2D;", code.print()); + } + + @Test + public void testBug() { + CodeGen code = new CodeGen(""" +struct s0 { + int v0; +}; +s0? v1=null; +int v3=v1.zAicm; +"""); + try { code.parse(); fail(); } + catch( Exception e ) { assertEquals("Accessing unknown field 'zAicm' from 'null'",e.getMessage()); } + } + + @Test + public void testBug2() { + CodeGen code = new CodeGen(""" +struct s0 { int v0; }; +arg=0+new s0.0; +"""); + try { code.parse(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test + public void testLoop() { + CodeGen code = new CodeGen(""" +struct Bar { int a; }; +Bar !bar = new Bar; +while (arg) { + bar.a = bar.a + 2; + arg = arg + 1; +} +return bar.a; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(Phi_a+2));", code.print()); + } + + @Test + public void testIf() { + CodeGen code = new CodeGen(""" +struct Bar { int a; }; +Bar !bar = new Bar; +if (arg) bar = null; +bar.a = 1; +return bar.a; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Type null is not of declared type *Bar",e.getMessage()); } + } + + @Test + public void testIf2() { + CodeGen code = new CodeGen(""" +struct Bar { int a; }; +Bar? !bar = null; +if (arg) bar = new Bar; +bar.a = 1; +return bar.a; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'a'",e.getMessage()); } + } + + @Test + public void testIf3() { + CodeGen code = new CodeGen(""" +struct Bar { int a; }; +Bar bar = null; +if (arg) bar = null; +bar.a = 1; +return bar.a; +"""); + try { code.parse(); fail(); } + catch( Exception e ) { assertEquals("Type null is not of declared type *Bar", e.getMessage()); } + } + + @Test + public void testIfOrNull() { + CodeGen code = new CodeGen(""" +struct Bar { int a; }; +Bar? !bar = new Bar; +if (arg) bar = null; +if( bar ) bar.a = 1; +return bar; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,null,Bar);", code.print()); + } + + @Test + public void testIfOrNull2() { + CodeGen code = new CodeGen( +""" +struct Bar { int a; }; +Bar? !bar = new Bar; +if (arg) bar = null; +int rez = 3; +if( !bar ) rez=4; +else bar.a = 1; +return rez; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,4,3);", code.print()); + } + + @Test + public void testWhileWithNullInside() { + CodeGen code = new CodeGen(""" +struct s0 {int v0;}; +s0? !v0 = new s0; +int ret = 0; +while(arg) { + ret = v0.v0; + v0 = null; + arg = arg - 1; +} +return ret; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { + assertEquals("Might be null accessing 'v0'", e.getMessage()); } + } + + @Test + public void testRedeclareStruct() { + CodeGen code = new CodeGen(""" +struct s0 { + int v0; +}; +s0? v1=new s0; +s0? v1; +v1=new s0; +"""); + try { code.parse(); fail(); } + catch( Exception e ) { assertEquals("Redefining name 'v1'", e.getMessage()); } + } + + @Test + public void testIter() { + // Build and use an iterator + CodeGen code = new CodeGen( +""" +struct Iter { + int x; + int len; +}; +Iter !i = new Iter; +i.len = arg; +int sum=0; +while( i.x < i.len ) { + sum = sum + i.x; + i.x = i.x + 1; +} +return sum; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", code.print()); + } + + + @Test + public void test1() { + CodeGen code = new CodeGen(""" +struct s0 {int v0;}; +s0 !ret = new s0; +while(arg) { + s0 !v0 = new s0; + v0.v0 = arg; + arg = arg-1; + if (arg==5) ret=v0; + +} +return ret; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); + } + + @Test + public void test2() { + CodeGen code = new CodeGen(""" +struct s0 {int v0;}; +s0 !ret = new s0; +s0 !v0 = new s0; +while(arg) { + v0.v0 = arg; + arg = arg-1; + if (arg==5) ret=v0; + +} +return ret; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); + } + + + @Test + public void test3() { + CodeGen code = new CodeGen(""" +struct s0 {int v0;}; +s0 !ret = new s0; +while(arg < 10) { + s0 !v0 = new s0; + if (arg == 5) ret=v0; + arg = arg + 1; +} +return ret; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); + } + + @Test + public void testBug3() { + CodeGen code = new CodeGen(""" +struct s0 { int f0; }; +return new s0; +int v0=null.f0; +"""); + try { code.parse(); fail(); } + catch( Exception e ) { assertEquals("Accessing unknown field 'f0' from 'null'",e.getMessage()); } + } + + @Test + public void testBug4() { + CodeGen code = new CodeGen(""" +if(0) { + while(0) if(arg) continue; + int v0=0; + while(1) { + int v2=-arg; + v0=v2; + } +} + """); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testBug5() { + CodeGen code = new CodeGen(""" +struct s0 { + int f0; +}; +if(0) return 0; +else return new s0; +if(new s0.f0) return 0; + """); + code.parse().opto(); + assertEquals("return s0;", code.print()); + } + + @Test + public void testBug6MissedWorklist() { + CodeGen code = new CodeGen(""" +while(0) {} +int v4=0; +while(0=24; + if(7) continue; + kzEl_r7EYz=false; + if(-kzEl_r7EYz+arg<-3) continue; + else { + while(kzEl_r7EYz) continue; + arg=----3; + kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz); + int v2uF_4ba=9; + } + } + } + int pjcp7rv=arg; + { + int m2ya3=--arg-pjcp7rv; + while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) { + m2ya3=m2ya3+-(--0<=false=-pjcp7rv>=arg<=arg); + while(arg<-arg) { + arg=arg+--arg; + { + while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33); + pjcp7rv=11; + int c=pjcp7rv; + if(--107) break; + else break; + } + } + } + pjcp7rv=pjcp7rv; + int aR0Wkua=-pjcp7rv==pjcp7rv; + { + if(-0!=-0) while(-true) break; + else { + while(aR0Wkua) pjcp7rv=-0/pjcp7rv; + pjcp7rv=pjcp7rv; + } + } + } + if(-arg) { + { + int Isdlt0fr91=0!=arg; + while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) { + Isdlt0fr91=Isdlt0fr91+-1!=true; + if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91; + int i=---arg<---arg!=--40; + { + int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0; + while(jVX43Ln4Dm<--(3-3)) { + jVX43Ln4Dm=jVX43Ln4Dm+-0<25; + i=24<--(jVX43Ln4Dm); + } + } + i=(arg!=----false>=7); + int Te=5>-arg; + break; + } + } + arg=arg!=--true/arg; + { + int UX=arg; + while(UX<-3*arg) { + UX=UX+arg/-1; + arg=-3--(-UX- -47=-arg; + if(---12) while(-UX) break; + break; + } + } + continue; + } + if(arg) arg=--0; + else if(1) continue; + int DtTlhjYq=19==arg; + { + arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq); + if(---arg) continue; + else { + int Zsl=40; + while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) { + Zsl=Zsl+arg; + } + } + if((arg)) if(-DtTlhjYq) { + } + else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false; + else { + int lwbF=arg>=0; + while(lwbF<57) { + lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg; + arg=----0+0; + while(49) break; + if(true) DtTlhjYq=-----arg; + DtTlhjYq=0!=-----(0); + } + } + arg=---arg!=DtTlhjYq/--0; + DtTlhjYq=-DtTlhjYq/(--argDtTlhjYq; + else { + } + DtTlhjYq=-0; + { + while((0)<-arg) DtTlhjYq=-DtTlhjYq; + } + if(30/--(arg)>=0) DtTlhjYq=-0>=arg; + else { + int Y2wcIQJ=--DtTlhjYq*---11; + if(arg==arg) { + Y2wcIQJ=-----Y2wcIQJ; + Y2wcIQJ=Y2wcIQJ<7; + if(DtTlhjYq) arg=arg; + else break; + while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3; + } + continue; + } + arg=DtTlhjYq; + arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq; + arg=51+---(-true)!=arg!=----1==-DtTlhjYq; + if(11<=arg) if((arg)+79<32+(-arg)) continue; + else if(true==DtTlhjYq) break; + break; + } +} +if(arg!=62==arg) { + while(---arg) { + { + int bhmDacPM=arg/arg; + while(bhmDacPM1)=-arg+-arg; + break; + } + } + int arg=true; + arg=arg<=arg; + { + int KlC=30; + while(KlC<-2) { + KlC=KlC+-1!=25<=-KlC>KlC>----0; + int Ij=arg>=-arg<=---10; + { + int LAbgurVa2R=-arg!=Ij; + while(LAbgurVa2R<-true) { + LAbgurVa2R=LAbgurVa2R+Ij; + KlC=-LAbgurVa2R; + Ij=42*(-Ij>true); + while(Ij) arg=KlC; + KlC=-----7>-(--KlC<--7)==-LAbgurVa2R; + } + } + int a=Ij<=-KlC; + if(Ij) { + int r1W=a!=-false; + } + else { + arg=56>=Ij; + while(54) break; + arg=8>=-(a<--Ij)/a>=-a-KlC; + } + int Yt_T=KlC; + arg=KlC; + } + } + if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg; + else if(----arg) continue; + if(-arg-arg) { + arg=-(-arg)*--(-3)<(-7==-arg----arg); + { + int arg=arg; + while(arg<-0>arg==-arg-(-arg>1+11)) { + arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg; + } + } + arg=-arg+arg; + arg=--47+-arg<1>arg*(-arg==-arg- -0>3); + arg=(----arg)!=arg+--59; + arg=- -4+arg==-(arg)-arg; + } + else { + while(--true-----true*-25+-18>arg>=-----(-arg)---13) { + arg=-0+--true=--0))<=-0/-arg; + int L=-arg; + int B4mHcrf=---vzXB; + int oZWGdzZl=-o3ypEsewxM; + int K6tQqa1=11; + while(0!=--L) { + int sdZfTM=vzXB*true+K6tQqa1; + while(sdZfTMfalse); + sdZfTM=vzXB; + } + } + L=false; + while(31) B4mHcrf=arg; + oZWGdzZl=-0<--oZWGdzZl<=--2; + if(K6tQqa1>=20<=46) { + if(-1+-L) if(oZWGdzZl) { + int wmhv=-----0; + } + int arg=0; + o3ypEsewxM=---(oZWGdzZl); + return -oZWGdzZl/0; + } + else if(arg) { + int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM; + return -K6tQqa1; + } + else { + if(---0) { + {} + {} + } + return o3ypEsewxM; + } +} +"""); + code.parse().opto().typeCheck().GCM(); + assertEquals("return Phi(Region,9,Top,Top,Top,Top);", code.print()); + } + + + @Test + public void testPrimes() { + CodeGen code = new CodeGen( +""" +if( arg < 2 ) return 0; +int primeCount = 1; +int prime = 3; +while( prime <= arg ) { + int isPrime = 1; + // Check for even case, so the next loop need only check odds + if( (prime/2)*2 == prime ) + continue; + // Check odds up to sqrt of prime + int j = 3; + while( j*j <= prime ) { + if( (prime/j)*j == prime ) { + isPrime = 0; + break; + } + j = j + 2; + } + if( isPrime ) + primeCount = primeCount + 1; + prime = prime + 2; +} +return primeCount; +"""); + 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() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; +"""); + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertEquals("2", Eval2.eval(code, 0)); + assertEquals("2", Eval2.eval(code, 1)); + } + + @Test + public void testAntiDeps2() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v = new S; +v.f = arg; +S !t = new S; +int i = 0; +if (arg) { + if (arg+1) v = t; + i = v.f; +} else { + v.f = 2; +} +return i; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,.f,0);", code.print()); + } + + @Test + public void testAntiDeps3() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v0 = new S; +S? v1; +if (arg) v1 = new S; +if (v1) { + v0.f = v1.f; +} else { + v0.f = 2; +} +return v0; +"""); + code.parse().opto(); + assertEquals("return S;", code.print()); + } + + + @Test + public void testAntiDeps4() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v = new S; +v.f = arg; +S t = new S; +int i = v.f; +if (arg+1) arg= 0; +while (arg) v.f = 2; +return i; +"""); + code.parse().opto(); + assertEquals("return arg;", code.print()); + } + + @Test + public void testAntiDeps5() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v = new S; +while(1) { + while(arg+1) { arg=arg-1; } + if (arg) break; + v.f = 2; +} +return v; +"""); + code.parse().opto(); + assertEquals("return S;", code.print()); + } + + @Test + public void testAntiDeps6() { + CodeGen code = new CodeGen( +""" +struct s { int v; }; +s !ptr=new s; +while( -arg ) + ptr = new s; +while(1) + arg = arg+ptr.v; +"""); + code.parse().opto(); + assertEquals("return Top;", code.print()); + } + + @Test + public void testAntiDeps7() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v = new S; +S t = new S; +int i = v.f; +while (arg) { + v.f = arg; + arg = arg-1; +} +return i; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testAntiDeps8() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v = new S; +S t = new S; +while(arg) { + arg=arg-1; + int f = v.f; + v.f = 2; + if (arg) arg = f; + else v.f = 3; +} +return arg; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testAntiDeps9() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v = new S; +S t = new S; +if (arg) { + v.f=2; + int i=t.f; + v.f=i; +} +return v; +"""); + code.parse().opto(); + assertEquals("return S;", code.print()); + } + + @Test + public void testExample2() { + CodeGen code = new CodeGen( +""" +struct S { int f; }; +S !v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; + """); + code.parse().opto(); + //assertEquals("return new S;", code.print()); + } + + @Test + public void testScheduleUse() { + CodeGen code = new CodeGen( +""" +int v0=0; +while(0>=0) { + u1 v1=0; + v1=v0; + if(v1*0) + v0=-v1; +} +return 0; +"""); + code.parse().opto(); + assertEquals("return Top;", code.print()); + } + + @Test + public void testLoopCarriedDep() { + CodeGen code = new CodeGen( +""" +u32 v0=0; +{ + int v1=0; + while(v1) { + v1=1>>>v0!=0; + v0=v1/0; + } + return v1; +} +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java new file mode 100644 index 00000000..8069ddaa --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -0,0 +1,61 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter12Test { + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testFloat() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testSquareRoot() { + CodeGen code = new CodeGen( +""" +flt guess = arg; +while( 1 ) { + flt next = (arg/guess + guess)/2; + if( next == guess ) break; + guess = next; +} +return guess; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print()); + assertEquals("3.0", Eval2.eval(code, 9)); + assertEquals("1.414213562373095", Eval2.eval(code, 2)); + } + + @Test + public void testFPOps() { + CodeGen code = new CodeGen( +""" +flt x = arg; +return x+1==x; +"""); + code.parse().opto(); + assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter13Test.java new file mode 100644 index 00000000..977595cb --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -0,0 +1,261 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter13Test { + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testLinkedList0() { + CodeGen code = new CodeGen( +""" +struct LLI { LLI? next; int i; }; +LLI? !head = null; +while( arg ) { + LLI !x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +return head.next.i; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + } + + @Test + public void testLinkedList1() { + CodeGen code = new CodeGen( +""" +struct LLI { LLI? next; int i; }; +LLI? !head = null; +while( arg ) { + LLI !x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.i; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,0,1,.i);", code.print()); + assertEquals("2", Eval2.eval(code, 3)); + } + + @Test + public void testCoRecur() { + CodeGen code = new CodeGen( +""" +struct int0 { int i; flt0? f; }; +struct flt0 { flt f; int0? i; }; +int0 !i0 = new int0; +i0.i = 17; +flt0 !f0 = new flt0; +f0.f = 3.14; +i0.f = f0; +f0.i = i0; +return f0.i.f.i.i; +"""); + code.parse().opto(); + assertEquals("return 17;", code.print()); + } + + @Test + public void testNullRef0() { + CodeGen code = new CodeGen( +""" +struct N { N? next; int i; }; +N n = new N; +return n.next; +"""); + code.parse().opto(); + assertEquals("return null;", code.print()); + } + + @Test + public void testNullRef1() { + CodeGen code = new CodeGen( +""" +struct M { int m; }; +struct N { M next; int i; }; +N n = new N { next = new M; }; +return n.next; +"""); + code.parse().opto(); + assertEquals("return (const)M;", code.print()); + } + + @Test + public void testNullRef2() { + CodeGen code = new CodeGen( +""" +struct M { int m; }; +struct N { M next; int i; }; +N n = new N { next = null; } +return n.next; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } + } + + @Test + public void testNullRef3() { + CodeGen code = new CodeGen( +""" +struct N { N? next; int i; }; +N !n = new N; +n.i = 3.14; +return n.i; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Type 3.14 is not of declared type int",e.getMessage()); } + } + + @Test + public void testNullRef4() { + 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() { + 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() { + CodeGen code = new CodeGen( +""" +struct S{}; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @Test + public void testForwardRef0() { + CodeGen code = new CodeGen( +""" +struct S1 { S2? s; }; +return new S2; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } + } + + @Test + public void testForwardRef1() { + CodeGen code = new CodeGen( +""" +struct S1 { S2? s; }; +struct S2 { int x; }; +return new S1.s=new S2; +"""); + code.parse().opto(); + assertEquals("return S2;", code.print()); + } + + @Test + public void testcheckNull() { + CodeGen code = new CodeGen( +""" +struct I {int i;}; +struct P { I? pi; }; +P !p1 = new P; +P !p2 = new P; +p2.pi = new I; +p2.pi.i = 2; +if (arg) p1 = new P; +return p1.pi.i + 1; +"""); + try { 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/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java new file mode 100644 index 00000000..b83516e3 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -0,0 +1,226 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter14Test { + + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testRange() { + CodeGen code = new CodeGen( +""" +int b; +if( arg ) b=1; else b=0; +int c = 99; +if( b < 0 ) c = -1; +if( b > 2 ) c = 1; +return c; +"""); + code.parse().opto(); + assertEquals("return 99;", code.print()); + assertEquals("99", Eval2.eval(code, 0)); + } + + @Test + public void testU8() { + CodeGen code = new CodeGen( +""" +u8 b = 123; +b = b + 456;// Truncate +return b; +"""); + code.parse().opto(); + assertEquals("return 67;", code.print()); + assertEquals("67", Eval2.eval(code, 0)); + } + + + @Test + public void testU8While() { + CodeGen code = new CodeGen( +""" +u8 b = 123; +while( b ) b = b + 456;// Truncate +return b; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testU1() { + CodeGen code = new CodeGen( +""" +bool b = 123; +b = b + 456;// Truncate +u1 c = b; // No more truncate needed +return c; +"""); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + } + + @Test + public void testAnd() { + CodeGen code = new CodeGen( +""" +int b = 123; +b = b+456 & 31; // Precedence +return b; +"""); + code.parse().opto(); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); + } + + @Test + public void testRefLoad() { + CodeGen code = new CodeGen( +""" +struct Foo { u1 b; }; +Foo !f = new Foo; +f.b = 123; +return f.b; +"""); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + } + + @Test + public void testSigned() { + CodeGen code = new CodeGen( +""" +i8 b = 255; // Chopped +return b; // Sign extend +"""); + code.parse().opto(); + assertEquals("return -1;", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); + } + + @Test + public void testI8() { + CodeGen code = new CodeGen( +""" +i8 b = arg; +b = b + 1;// Truncate +return b; +"""); + 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() { + CodeGen code = new CodeGen( +""" +u16 mask = (1<<16)-1; // AND mask +int c = 123456789 & mask; +return c; // +"""); + code.parse().opto(); + assertEquals("return 52501;", code.print()); + assertEquals("52501", Eval2.eval(code, 0)); + } + + @Test + public void testOr() { + CodeGen code = new CodeGen( +""" +return (arg | 123 ^ 456) >>> 1; +"""); + code.parse().opto(); + assertEquals("return (((arg|123)^456)>>>1);", code.print()); + assertEquals("217", Eval2.eval(code, 0)); + } + + @Test + public void testMaskFloat() { + CodeGen code = new CodeGen( +""" +flt f = arg; +arg = f & 1; +return arg; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot '&' flt",e.getMessage()); } + } + + @Test + public void testCloneAnd() { + CodeGen code = new CodeGen(""" +int v0=0; +u32 v1 = 1&(1<>>0) { + while(0) { + u8 v1=0; + v0=0>>>0; + v1=arg; + while(v1+0) {} + } +} +return v0; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @Test + public void testTypes() { + CodeGen code = new CodeGen( +""" +i8 xi8 = 123456789; if( xi8 != 21 ) return -8; +i16 xi16 = 123456789; if( xi16 != -13035 ) return -16; +i32 xi32 = 123456789; if( xi32 != 123456789 ) return -32; +i64 xi64 = 123456789; if( xi64 != 123456789 ) return -64; +int xint = 123456789; if( xint != 123456789 ) return -64; + +u1 ui1 = 123456789; if( ui1 != 1 ) return 1; +u8 ui8 = 123456789; if( ui8 != 21 ) return 8; +u16 ui16 = 123456789; if( ui16 != 52501 ) return 16; +u32 ui32 = 123456789; if( ui32 != 123456789 ) return 32; + +flt fflt = 3.141592653589793; if( fflt != 3.141592653589793 ) return 3; +f64 ff64 = 3.141592653589793; if( ff64 != 3.141592653589793 ) return 3; +f32 ff32 = 3.141592653589793; if( ff32 != 3.1415927410125732) return 5; + +return 0; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java new file mode 100644 index 00000000..7dd0710a --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -0,0 +1,383 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter15Test { + + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testCyclic() { + CodeGen code = new CodeGen( +""" +struct C { C? l; }; +C !c = new C; +c.l = c; +return c; +"""); + code.parse().opto(); + assertEquals("return C;", code.print()); + assertEquals("C{l=$cyclic}", Eval2.eval(code, 0)); + } + + @Test + public void testSafetyCheck() { + CodeGen code = new CodeGen( +""" +u8[] old = new u8[0]; +u8[] !output = new u8[1]; +int i = 0; +while (i < old#) { + output[i] = old[i]; + i = i + 1; +} +output[i] = 1; +return output; +"""); + code.parse().opto(); + assertEquals("return [u8];", code.print()); + assertEquals("\u0001", Eval2.eval(code, 0)); + } + + @Test + public void testBasic1() { + CodeGen code = new CodeGen( +""" +int[] is = new int[2]; +return is[1]; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @Test + public void testBasic2() { + CodeGen code = new CodeGen( +""" +int[] is = new int[2]; +int[] is2 = new int[2]; +return is[1]; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @Test + public void testBasic3() { + CodeGen code = new CodeGen( +""" +int[] !a = new int[2]; +a[0] = 1; +a[1] = 2; +return a[0]; +"""); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + } + + @Test + public void testBasic4() { + CodeGen code = new CodeGen( +""" +struct A { int i; }; +A?[] !a = new A?[2]; +return a; +"""); + code.parse().opto(); + assertEquals("return [*A?];", code.print()); + assertEquals("*A {int !i; }?[ null,null]", Eval2.eval(code, 0)); + } + + @Test + public void testBasic5() { + CodeGen code = new CodeGen( +""" +struct S { int x; flt y; }; +// A new S +S !s = new S; s.x=99; s.y = 3.14; + +// Double-d array of Ss. Fill in one row. +S?[]?[] !iss = new S?[]?[2]; +iss[0] = new S?[7]; +iss[0][2] = s; + +// Now pull out the filled-in value, with null checks +flt rez; +S?[]? is = iss[arg]; +if( !is ) rez = 1.2; +else { + S? i = is[2]; + if( !i ) rez = 2.3; + else rez = i.y; +} +return rez; +"""); + 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() { + CodeGen code = new CodeGen( +""" +struct S { int x; flt y; }; +// A new S +S !s = new S; s.x=99; s.y = 3.14; + +// Double-d array of Ss. Fill in one row. +S?[]?[] !iss = new S?[]?[2]; +iss[0] = new S?[7]; +iss[0][2] = s; + +// Now pull out the filled-in value, with null checks +flt rez = 1.2; +if( iss[arg] ) + if( iss[arg][2] ) + rez = iss[arg][2].y; +return rez;"""); + code.parse().opto().typeCheck(); + assertEquals("return Phi(Region,Phi(Region,.y,1.2),1.2);", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + try { Eval2.eval(code, 10); fail(); } // Fails AIOOBE in Eval2, no range checks + catch( Exception e ) { assertEquals("Index 10 out of bounds for length 2",e.getMessage()); } + } + + @Test + public void testTree() { + CodeGen code = new CodeGen( +""" +// Can we define a forward-reference array? +struct Tree { Tree?[]? _kids; }; +Tree !root = new Tree; +root._kids = new Tree?[2]; // NO BANG SO ARRAY IS OF IMMUTABLE TREES???? +root._kids[0] = new Tree; +return root; +"""); + code.parse().opto(); + assertEquals("return Tree;", code.print()); + assertEquals("Tree{_kids=*Tree?[ Tree{_kids=null},null]}", Eval2.eval(code, 0)); + } + + @Test + public void testNestedStructAddMemProj() { + CodeGen code = new CodeGen( +""" +struct S { int a; int[] b; }; +return 0; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + @Test + public void testRollingSum() { + CodeGen code = new CodeGen( +""" +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +int i=0; +while( i < ary# ) { + ary[i] = i; + i = i+1; +} +// Fill [0,1,3,6,10,...] +i=0; +while( i < ary# - 1 ) { + ary[i+1] = ary[i+1] + ary[i]; + i = i+1; +} +return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 +"""); + code.parse().opto(); + assertEquals("return (.[]+(.[]*1000));", code.print()); + assertEquals("1006", Eval2.eval(code, 4)); + } + + @Test + public void sieveOEratosthenes() { + CodeGen code = new CodeGen( +""" +int[] !ary = new int[arg], !primes = new int[arg]; +int nprimes = 0, p=2; +// Find primes while p^2 < arg +while( p*p < arg ) { + // skip marked non-primes + while( ary[p]==1 ) p = p + 1; + // p is now a prime + primes[nprimes] = p; nprimes = nprimes + 1; + // Mark out the rest non-primes + int i = p + p; + while( i < ary# ) { + ary[i] = 1; + i = i + p; + } + p = p + 1; +} +// Now just collect the remaining primes, no more marking +while( p < arg ) { + if( ary[p] == 0 ) { + primes[nprimes] = p; nprimes = nprimes + 1; + } + p = p + 1; +} +// Copy/shrink the result array +int[] !rez = new int[nprimes]; +int j = 0; +while( j < nprimes ) { + rez[j] = primes[j]; + j = j + 1; +} +return rez; +"""); + code.parse().opto(); + assertEquals("return [int];", code.print()); + assertEquals("int[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20)); + } + + @Test + public void testNewNodeInit() { + CodeGen code = new CodeGen( +""" +struct S {int i; flt f;}; +S !s1 = new S; +S !s2 = new S; +s2.i = 3; +s2.f = 2.0; +if (arg) s1 = new S; +return s1.i + s1.f; +"""); + code.parse().opto(); + assertEquals("return ((flt).i+.f);", code.print()); + assertEquals("0.0", Eval2.eval(code, 0)); + } + + + @Test + public void testBad0() { + CodeGen code = new CodeGen( +""" +return new flt; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Cannot allocate a flt",e.getMessage()); } + } + + @Test + public void testBad1() { + CodeGen code = new CodeGen( +""" +int is = new int[2]; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Type *[int] is not of declared type int",e.getMessage()); } + } + + @Test + public void testBad2() { + CodeGen code = new CodeGen( +""" +int[] is = new int[3.14]; +return is[1]; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Cannot allocate an array with length 3.14",e.getMessage()); } + } + + @Test + public void testBad3() { + CodeGen code = new CodeGen(""" +int[] is = new int[arg]; +return is[1]; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 4)); + try { Eval2.eval(code,-1); fail(); } + catch( NegativeArraySizeException e ) { assertEquals("-1",e.getMessage()); } + // This test will not pass (i.e., failed range-check) until we have range checks. + // Without the range check, the load `is[1]` optimizes against the `new int[]` + // and assumes it loads a zero then folds away, and the Eval2 never sees an OOB load. + //try { Eval2.eval(code,0); fail(); } + //catch( ArrayIndexOutOfBoundsException e ) { assertEquals("Array index 1 out of bounds for array length 0",e.getMessage()); } + } + + @Test + public void testProgress() { + CodeGen code = new CodeGen(""" +i8 v1=0&0; +u8 v2=0; +byte v4=0; +if(0) {} +while(v2<0) { + v4=0-v1; + break; +} +int v5=0&0; +while(v5+(0&0)) { + int v7=0&0; + while(v7) + v4=0>>>v5; + while(v1) + return 0; +} +return v1; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @Test + public void testSharpNot() { + CodeGen code = new CodeGen( +""" +if(0>>0) {} +while(0) {} +u32 v7=0; +int v8=0; +while(0<--1>>>---(v7*0==v8)) {} +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } + + + @Test + public void testProgress2() { + CodeGen code = new CodeGen( +""" +if(1) {} +else { + while(arg>>>0&0>>>0) {} + byte v3=0>>>0; + while(0) {} + int v7=0>>>0; + while(v7<0>>>0) { + while(0+v7<=0) if(1) arg=-12; + if(arg) { + v3=arg+v3+0; + arg=0; + } + } +} +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java new file mode 100644 index 00000000..930624e5 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -0,0 +1,261 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter16Test { + + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + + @Test + public void testMulti0() { + CodeGen code = new CodeGen( +""" +int x, y; +return x+y; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + @Test + public void testMulti1() { + CodeGen code = new CodeGen( +""" +int x=2, y=x+1; +return x+y; +"""); + code.parse().opto(); + assertEquals("return 5;", code.print()); + assertEquals("5", Eval2.eval(code, 0)); + } + +// @Test +// public void testFinal0() { +// CodeGen code = new CodeGen( +//""" +//int !x=2; +//x=3; +//return x; +//"""); +// try { code.parse().opto(); fail(); } +// catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } +// } + + @Test + public void testFinal1() { + CodeGen code = new CodeGen( +""" +int x=2, y=3; +if( arg ) { int x = y; x = x*x; y=x; } // Shadow final x +return y; +"""); + 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 testConstruct0() { + CodeGen code = new CodeGen(""" +struct X { int x=3; }; +X z = new X; +return z.x; +"""); + code.parse().opto(); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); + } + + @Test + public void testConstruct1() { + CodeGen code = new CodeGen(""" +struct X { int !x; }; +X z = new X { x=3; }; +return z.x; +"""); + code.parse().opto(); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); + } + + @Test + public void testConstruct2() { + CodeGen code = new CodeGen(""" +struct X { int x=3; }; +X z = new X { x = 4; }; +return z.x; +"""); + code.parse().opto(); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); + } + + + @Test + public void testStructFinal0() { + CodeGen code = new CodeGen(""" +struct Point { int !x, !y; }; +Point p = new Point { x=3; y=4; }; +return p; +"""); + code.parse().opto(); + assertEquals("return (const)Point;", code.print()); + assertEquals("Point{x=3,y=4}", Eval2.eval(code, 0)); + } + + @Test + public void testStructFinal1() { + CodeGen code = new CodeGen(""" +struct Point { int x=3, y=4; }; +Point p = new Point { x=5; y=6; }; +p.x++; +return p; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal2() { + CodeGen code = new CodeGen(""" +struct Point { int x=3, y=4; }; +Point p = new Point; +p.x++; +return p; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal3() { + CodeGen code = new CodeGen(""" +struct Point { var x; var y; }; +Point p = new Point; +p.x++; +return p; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("'Point' is not fully initialized, field 'x' needs to be set in a constructor",e.getMessage()); } + } + + @Test + public void testStructFinal4() { + CodeGen code = new CodeGen(""" +struct Point { val x=3; val y=4; }; +Point p = new Point; +p.x++; +return p; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal5() { + CodeGen code = new CodeGen(""" +struct Point { var x=3; var y=4; }; +Point !p = new Point; +p.x++; +return p; +"""); + code.parse().opto(); + assertEquals("return Point;", code.print()); + assertEquals("Point{x=4,y=4}", Eval2.eval(code, 0)); + } + + // Same as the Chapter13 test with the same name, but using the new + // constructor syntax + @Test + public void testLinkedList1() { + CodeGen code = new CodeGen( +""" +struct LLI { LLI? next; int i; }; +LLI? !head = null; +while( arg ) { + head = new LLI { next=head; i=arg; }; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( !next ) return 1; +return next.i; +"""); + 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() { + CodeGen code = new CodeGen( +""" +struct LLI { LLI? next; int i; }; +LLI? !head = null; +while( arg ) { + head = new LLI { + next=head; + // Any old code in the constructor + int !tmp=arg; + while( arg > 10 ) { + tmp = tmp + arg; + arg = arg - 1; + } + i=tmp; + }; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( !next ) return 1; +return next.i; +"""); + 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() { + CodeGen code = new CodeGen( +""" +struct Square { + flt !side = arg; + // Newtons approximation to the square root, computed in a constructor. + // The actual allocation will copy in this result as the initial + // value for 'diag'. + flt !diag = arg*arg/2; + while( 1 ) { + flt next = (side/diag + diag)/2; + if( next == diag ) break; + diag = next; + } +}; +return new Square; +"""); + 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)); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java new file mode 100644 index 00000000..6e43dbc8 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -0,0 +1,555 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter17Test { + + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 1; +"""); + code.parse().opto().typeCheck(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + } + + + // --------------------------------------------------------------- + @Test + public void testInc0() { + CodeGen code = new CodeGen(""" +return arg++; +"""); + code.parse().opto(); + assertEquals("return arg;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @Test + public void testInc1() { + CodeGen code = new CodeGen(""" +return arg+++arg++; +"""); + code.parse().opto(); + assertEquals("return ((arg<<1)+1);", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + } + + @Test + public void testInc2() { + CodeGen code = new CodeGen(""" +// -(arg--)-(arg--) +return -arg---arg--; +"""); + code.parse().opto(); + assertEquals("return (-((arg<<1)+-1));", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + } + + @Test + public void testInc3() { + CodeGen code = new CodeGen(""" +int[] !xs = new int[arg]; +xs[0]++; +xs[1]++; +return xs[0]; +"""); + code.parse().opto(); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 2)); + } + + @Test + public void testInc4() { + CodeGen code = new CodeGen(""" +u8[] !xs = new u8[1]; +xs[0]--; +return xs[0]; +"""); + code.parse().opto(); + assertEquals("return 255;", code.print()); + assertEquals("255", Eval2.eval(code, 2)); + } + + @Test + public void testInc5() { + CodeGen code = new CodeGen(""" +struct S { u16 x; }; +S !s = new S; +s.x--; +return s.x; +"""); + code.parse().opto(); + assertEquals("return 65535;", code.print()); + assertEquals("65535", Eval2.eval(code, 2)); + } + + @Test + public void testInc6() { + 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() { + 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() { + 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;"); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Type 2.5f is not of declared type int",e.getMessage()); } + } + + + // --------------------------------------------------------------- + @Test public void testVar0() { + 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() { + 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() { + 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() { + 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() { + 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() { + 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() { + 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() { + 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() { + 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() { + 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() { + CodeGen code = new CodeGen("struct S{int x;}; val 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() { + CodeGen code = new CodeGen(""" +struct Bar { int x; }; +Bar !bar = new Bar; +bar.x = 3; // Ok, bar is mutable + +struct Foo { Bar? !bar; int y; }; +Foo !foo = new Foo { bar = bar; }; +foo.bar = bar; // Ok foo is mutable +foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable + +val xfoo = foo; // Throw away mutability +xfoo.bar.x++; // Error, cannot mutate through xfoo + """); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test public void testVar12() { + CodeGen code = new CodeGen(""" +struct Bar { int x; }; +Bar !bar = new Bar; +bar.x = 3; // Ok, bar is mutable + +struct Foo { Bar? !bar; int y; }; +Foo !foo = new Foo; +foo.bar = bar; // Ok bar is mutable +foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable + +val xfoo = foo; // Throw away mutability +int x4 = xfoo.bar.x; // Ok to read through xfoo, gets 4 +foo.bar.x++; // Bumps to 5 +int x5 = xfoo.bar.x; // Ok to read through xfoo, gets 5 +return x4*10+x5; +"""); + code.parse().opto(); + assertEquals("return 45;", code.print()); + assertEquals("45", Eval2.eval(code, 0)); + } + + @Test + public void testVar13() { + CodeGen code = new CodeGen(""" +int i,i++; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Redefining name 'i'",e.getMessage()); } + } + + + @Test + public void testVar14() { + CodeGen code = new CodeGen(""" +struct B {}; +struct A { B b; }; +A x = new A { + return b; // read before init + b = new B; +}; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Cannot read uninitialized field 'b'",e.getMessage()); } + } + + @Test + public void testVar15() { + 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 { 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() { + CodeGen code = new CodeGen(""" +return arg ? 1 : 2; +"""); + 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() { + CodeGen code = new CodeGen(""" +return arg ? 0 : arg; +"""); + code.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @Test + public void testTrinary2() { + CodeGen code = new CodeGen(""" +struct Bar { int x; }; +var b = arg ? new Bar : null; +return b ? b.x++ + b.x++ : -1; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,((.x<<1)+1),-1);", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + } + + @Test + public void testTrinary3() { + CodeGen code = new CodeGen(""" +struct Bar { int x; }; +var b = arg ? new Bar; +return b ? b.x++ + b.x++ : -1; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,((.x<<1)+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 + 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" +"""); + 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() { + CodeGen code = new CodeGen(""" +flt f=arg?1:1.2; +return f; // missing widening +"""); + 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() { + CodeGen code = new CodeGen(""" +int sum=0; +for( int i=0; i=arg ) break; + sum += i; +} +return sum; +"""); + 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() { + CodeGen code = new CodeGen(""" +int sum=0; +for( int i=0; i 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("{ int -> int #1}", 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().typeCheck().GCM().localSched(); + assertEquals("Stop[ return (#2+#2); return (Parm_x(sq,int)*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 #2; return (Parm_x($fun1,int,3)*x); return (Parm_x($fun2,int,3)<<1); ]", 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().typeCheck(); + assertEquals("Stop[ return #2; return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*#2)); ]", 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 #2; return Parm_i(x,int); ]", 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)); + } + + + @Test + public void testFcn10() { + CodeGen code = new CodeGen( +""" +struct Person { + int age; +}; + +val fcn = { Person?[] ps, int x -> + val tmp = ps[x]; + if( ps[x] ) + ps[x].age++; +}; + +var ps = new Person?[2]; +ps[0] = new Person; +ps[1] = new Person; +fcn(ps,1); +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", 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,#2,#2); return Parm_i(o,int); ]", 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)); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java new file mode 100644 index 00000000..bb7e8716 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -0,0 +1,400 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; +import org.junit.Test; +import static com.seaofnodes.simple.Main.PORTS; +import static org.junit.Assert.*; +import static org.junit.Assert.fail; + +public class Chapter19Test { + + @Test + public void testJig() { + CodeGen code = new CodeGen(""" +return 0; +"""); + code.parse().opto().typeCheck(); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", Eval2.eval(code, 2)); + } + + + @Test + public void testString() { + CodeGen code = new CodeGen( +""" +struct String { + u8[] cs; + int _hashCode; +}; + +val equals = { String self, String s -> + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + if( self.cs ) { + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + } + if( !hash ) hash = 123456789; + return hash; +}; + +String !s = new String { cs = new u8[17]; }; +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s)+hashCode(s);"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("Stop[ return (#2+#2); return Phi(Region,1,0,0,1); return Phi(Region,._hashCode,Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code._stop.toString()); + assertEquals("-4898613127354160978", Eval2.eval(code, 2)); + } + + @Test + public void testBasic0() { + CodeGen code = new CodeGen("return 0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return 0;", code._stop.toString()); + } + + @Test + public void testBasic1() { + CodeGen code = new CodeGen("return arg+1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (inc,arg);", code._stop.toString()); + } + + @Test + public void testBasic2() { + CodeGen code = new CodeGen("return -17;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return -17;", code._stop.toString()); + } + + + @Test + public void testBasic3() { + CodeGen code = new CodeGen("return arg==1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (set==,(cmp,arg));", code._stop.toString()); + } + + @Test + public void testBasic4() { + CodeGen code = new CodeGen("return arg<<1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (shli,arg);", code._stop.toString()); + } + + @Test + public void testBasic5() { + CodeGen code = new CodeGen("return arg >> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (sari,arg);", code._stop.toString()); + } + + @Test + public void testBasic6() { + CodeGen code = new CodeGen("return arg >>> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (shri,arg);", code._stop.toString()); + } + + @Test + public void testBasic7() { + CodeGen code = new CodeGen("return arg / 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (div,arg,2);", code._stop.toString()); + } + + @Test + public void testBasic8() { + CodeGen code = new CodeGen("return arg * 6;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (muli,arg);", code._stop.toString()); + } + + @Test + public void testBasic9() { + CodeGen code = new CodeGen("return arg & 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (andi,arg);", code._stop.toString()); + } + + @Test + public void testBasic10() { + CodeGen code = new CodeGen("return arg | 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (ori,arg);", code._stop.toString()); + } + + @Test + public void testBasic11() { + CodeGen code = new CodeGen("return arg ^ 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (xori,arg);", code._stop.toString()); + } + + @Test + public void testBasic12() { + CodeGen code = new CodeGen("return arg + 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (addf,(i2f8,arg),2.0f);", code._stop.toString()); + } + + @Test + public void testBasic13() { + CodeGen code = new CodeGen("return arg - 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (subf,(i2f8,arg),2.0f);", code._stop.toString()); + } + + @Test + public void testBasic14() { + CodeGen code = new CodeGen("return arg * 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (mulf,(i2f8,arg),2.0f);", code._stop.toString()); + } + + @Test + public void testBasic15() { + CodeGen code = new CodeGen("return arg / 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (mulf,(i2f8,arg),0.5f);", code._stop.toString()); + } + + @Test + public void testBasic16() { + CodeGen code = new CodeGen( +""" +int arg1 = arg + 1; +return arg1 / arg;"""); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (div,(inc,arg),arg);", code._stop.toString()); + } + + @Test + public void testBasic17() { + CodeGen code = new CodeGen( +""" +int arg1 = arg + 1; +return arg1 * arg; +"""); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (mul,(inc,arg),arg);", code._stop.toString()); + } + + @Test + public void testToFloat() { + CodeGen code = new CodeGen(""" + int a = arg; + return a + 2.0; + """ + ).parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (addf,(i2f8,arg),2.0f);", code._stop.toString()); + } + + @Test + public void testIfStmt() { + CodeGen code = new CodeGen( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; +} +return a;"""); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return Phi(Region,(addi,arg),(addi,arg));", code.print()); + } + + @Test + public void testIfMerge2() { + CodeGen code = new CodeGen( +""" +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b;"""); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (add,(add,Phi(Region,(shli,arg),arg),arg),Phi(Region,4,5));", code.print()); + } + + @Test + public void testLoop() { + CodeGen code = new CodeGen( +""" +int sum=0; +for( int i=0; i + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +flt farg = arg; +return sqrt(farg); +"""); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return Phi(Loop,(i2f8,arg),(mulf,(addf,(divf,i2f8,Phi_guess),Phi_guess),0.5f));", code.print()); + }; + + + @Test + public void sieveOfEratosthenes() { + CodeGen code = new CodeGen( +""" +var ary = new bool[arg], primes = new int[arg]; +var nprimes=0, p=0; +// Find primes while p^2 < arg +for( p=2; p*p < arg; p++ ) { + // skip marked non-primes + while( ary[p] ) p++; + // p is now a prime + primes[nprimes++] = p; + // Mark out the rest non-primes + for( int i = p + p; i < ary#; i += p ) + ary[i] = true; +} +// Now just collect the remaining primes, no more marking +for( ; p < arg; p++ ) + if( !ary[p] ) + primes[nprimes++] = p; +// Copy/shrink the result array +var !rez = new int[nprimes]; +for( int j=0; j x*x; } : { int x -> x+x; }; +return fcn(2)*10 + fcn(3); +"""); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun1,int),x); return (shli,Parm_x($fun2,int)); ]", code.print()); + } + + @Test + public void testFcn2() { + CodeGen code = new CodeGen( +""" +val sq = { int x -> x*x; }; +return sq(arg) + sq(3); +"""); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("Stop[ return (add,#2,#2); return (mul,Parm_x(sq,int),x); ]", code.print()); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java new file mode 100644 index 00000000..008f5e0c --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -0,0 +1,196 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.ASMPrinter; +import org.junit.Assert; +import org.junit.Ignore; +import org.junit.Test; +import static com.seaofnodes.simple.Main.PORTS; +import static org.junit.Assert.*; + +public class Chapter20Test { + + @Test + public void testJig() { + CodeGen code = new CodeGen("return 0;"); + code.parse().opto().typeCheck(); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", Eval2.eval(code, 2)); + } + + static void testCPU( String src, String cpu, String os, int spills, String stop ) { + CodeGen code = new CodeGen(src); + code.parse().opto().typeCheck().instSelect(PORTS,cpu,os).GCM().localSched().regAlloc().encode(); + int delta = spills>>3; + if( delta==0 ) delta = 1; + assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + if( stop != null ) + assertEquals(stop, code._stop.toString()); + } + + private static void testAllCPUs( String src, int spills, String stop ) { + testCPU(src,"x86_64_v2", "SystemV",spills,stop); + testCPU(src,"riscv" , "SystemV",spills,stop); + testCPU(src,"arm" , "SystemV",spills,stop); + } + + @Test public void testAlloc0() { + testAllCPUs("return new u8[arg];", 1, "return [u8];"); + } + + @Test public void testBasic1() { + String src = "return arg | 2;"; + testCPU(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); + testCPU(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); + testCPU(src,"arm" , "SystemV",0,"return (ori,arg);"); + } + + @Test + public void testNewtonInteger() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { int x -> + int guess = x; + while( 1 ) { + int next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +return sqrt(arg) + sqrt(arg+2); +"""; + testCPU(src,"x86_64_v2", "SystemV",26,null); + testCPU(src,"riscv" , "SystemV",19,null); + testCPU(src,"arm" , "SystemV",26,null); + } + + @Test + public void testNewtonFloat() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { flt x -> + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +flt farg = arg; +return sqrt(farg) + sqrt(farg+2.0); +"""; + testCPU(src,"x86_64_v2", "SystemV",25,null); + testCPU(src,"riscv" , "SystemV",21,null); + testCPU(src,"arm" , "SystemV",18,null); + } + + @Test + public void testAlloc2() { + String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"; + testAllCPUs(src,1,"return .[];"); + } + + @Test + public void testArray1() { + String src = +""" +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +for( int i=0; i + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + if( self.cs ) { + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + } + if( !hash ) hash = 123456789; + return hash; +}; + +String !s = new String { cs = new u8[17]; }; +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s); +"""; + testCPU(src,"x86_64_v2", "SystemV",18,null); + testCPU(src,"riscv" , "SystemV", 3,null); + testCPU(src,"arm" , "SystemV", 3,null); + } + + @Test + public void testCast() { + String src = "struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1;"; + testAllCPUs(src,0,null); + } + + @Test + public void testFltArg() { + String src = "return {int i, flt f, int j->return i+f+j;};"; + testAllCPUs(src,0,null); + } + + @Test + public void testFlags1() { + String src = """ +bool b1 = arg == 1; +bool b2 = arg == 2; +if (b2) if (b1) return 1; +if (b1) return 2; +return 0; +"""; + testCPU(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); + testCPU(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); + testCPU(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); + } + + @Test + public void testFlags2() { + String src = """ +bool b1 = arg == 1; +while (arg > 0) { + arg--; + if (b1) arg--; +} +return arg; +"""; + testCPU(src,"x86_64_v2", "SystemV",3,null); + testCPU(src,"riscv" , "SystemV",2,null); + testCPU(src,"arm" , "SystemV",2,null); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java new file mode 100644 index 00000000..1f605cc1 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -0,0 +1,45 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.ASMPrinter; +import org.junit.Assert; +import org.junit.Ignore; +import org.junit.Test; +import static com.seaofnodes.simple.Main.PORTS; +import static org.junit.Assert.*; + +public class Chapter21Test { + + @Test + public void testJig() { + CodeGen code = new CodeGen("return 0;"); + code.parse().opto().typeCheck(); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", Eval2.eval(code, 2)); + } + + static void testCPU( String src, String cpu, String os, int spills, String stop ) { + CodeGen code = new CodeGen(src); + code.parse().opto().typeCheck().instSelect(PORTS,cpu,os).GCM().localSched().regAlloc().encode(); + int delta = spills>>3; + if( delta==0 ) delta = 1; + assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + if( stop != null ) + assertEquals(stop, code._stop.toString()); + } + + private static void testAllCPUs( String src, int spills, String stop ) { + testCPU(src,"x86_64_v2", "SystemV",spills,stop); + testCPU(src,"riscv" , "SystemV",spills,stop); + testCPU(src,"arm" , "SystemV",spills,stop); + } + + + @Test public void testBasic1() { + String src = "return arg | 2;"; + testCPU(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); + testCPU(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); + testCPU(src,"arm" , "SystemV",0,"return (ori,arg);"); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java new file mode 100644 index 00000000..ecea97dd --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java @@ -0,0 +1,450 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.print.IRPrinter; +import com.seaofnodes.simple.type.*; +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(CodeGen.CODE._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 -> x(not.in(1)) == 0 ? 1L : 0L; + 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 ToFloatNode toflt-> (double)x(toflt.in(1)); + case XorNode xor -> x(xor.in(1)) ^ x(xor.in(2)); + default -> throw Utils.TODO(); + }; + } + + // 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.in(1)); + 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[1] instanceof TypeMemPtr ) + // Assume a NewNode + yield _print( tt._types[1], x, sb, visit ); + throw Utils.TODO(); + } + case Type tt -> { + if( tt == Type.NIL ) yield sb.p("null"); + throw Utils.TODO(); + } + }; + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter21/src/test/java/com/seaofnodes/simple/FuzzerWrap.java new file mode 100644 index 00000000..d67b2065 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -0,0 +1,43 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.fuzzer.Fuzzer; +import java.util.Random; +import org.junit.Ignore; +import org.junit.Test; +import static org.junit.Assert.assertTrue; + +/** + * To use the fuzzer run the fuzzPeeps methods. + * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line + * via mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps + */ +public class FuzzerWrap { + + @Ignore + @Test + public void fuzzPeeps() { + var fuzzer = new Fuzzer(); + for (int i=0; i<1000000; i++) + fuzzer.fuzzPeeps(i); + assertTrue(fuzzer.noExceptions()); + } + + + @Test + public void fuzzPeepsSmall() { + Random R = new Random(System.currentTimeMillis()); + var fuzzer = new Fuzzer(); + for (int i=0; i<100; i++) + fuzzer.fuzzPeeps( R.nextLong()); + assertTrue(fuzzer.noExceptions()); + } + + @Test + @Ignore + public void fuzzPeepTiming() { + var fuzzer = new Fuzzer(); + int max_nid=0; + for (int i=0; i<1000000; i++) + max_nid = fuzzer.fuzzPeepTiming(i, max_nid); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Main.java b/chapter21/src/test/java/com/seaofnodes/simple/Main.java new file mode 100644 index 00000000..f3a6784c --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Main.java @@ -0,0 +1,19 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import java.nio.file.Files; +import java.nio.file.Path; + +public class Main { + public static final String PORTS = "com.seaofnodes.simple.node.cpus"; + // Compile and run a simple program + public static void main( String[] args ) throws Exception { + // First arg is file, 2nd+ args are program args + String src = Files.readString(Path.of(args[0])); + int arg = Integer.valueOf(args[1]); + CodeGen code = new CodeGen(src); + code.parse().opto().typeCheck().GCM().localSched(); + System.out.println(code._stop); + System.out.println(Eval2.eval(code,arg,100000)); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java new file mode 100644 index 00000000..c83fe089 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -0,0 +1,67 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class MergeSortTest { + + @Test + public void testMergeSort() { + String src = +""" +// 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; +"""; + Chapter20Test.testCPU(src,"x86_64_v2", "SystemV",46,"Stop[ return mov(mov([int])); return 0; ]"); + Chapter20Test.testCPU(src,"riscv" , "SystemV",36,"Stop[ return mov(mov([int])); return 0; ]"); + Chapter20Test.testCPU(src,"arm" , "SystemV",37,"Stop[ return mov(mov([int])); return 0; ]"); +//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter21/src/test/java/com/seaofnodes/simple/SchedulerTest.java new file mode 100644 index 00000000..ca29bf84 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -0,0 +1,74 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Assert; +import org.junit.Ignore; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; + +public class SchedulerTest { + + private static void assertObj(Object obj, String name, Object... fields) { + assertEquals(Evaluator.Obj.class, obj.getClass()); + var o = (Evaluator.Obj)obj; + assertEquals(name, o.struct()._name); + Assert.assertArrayEquals(fields, o.fields()); + } + + @Test + @Ignore + public void testJig() { + CodeGen code = new CodeGen(""" +struct S { + int f; +} +S !v=new S; +v.f = 2; +int i=v.f; +if (arg) v.f=1; +return i; +"""); + code.parse();//.opto(); + var eval = new Evaluator(code._stop); + assertEquals(2L, eval.evaluate(1, 10)); + } + + @Test + public void testStoreInIf() { + CodeGen code = new CodeGen(""" +struct S { + int f; +}; +S !v0=new S; +if(arg) v0.f=1; +return v0; +"""); + 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() { + CodeGen code = new CodeGen(""" +struct S { + int f; +}; +S !v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; +"""); + code.parse().opto(); + var eval = new Evaluator(code._stop); + assertEquals(2L, eval.evaluate(0, 10)); + assertEquals(2L, eval.evaluate(1, 10)); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter21/src/test/java/com/seaofnodes/simple/TypeTest.java new file mode 100644 index 00000000..d94f5b5a --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -0,0 +1,158 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.type.*; +import org.junit.Assert; +import org.junit.Test; +import static org.junit.Assert.assertSame; + +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.makeRO(), s1.glb()); + Assert.assertNotEquals(s1, s1.dual()); + Assert.assertEquals(s1.makeRO(), s1.dual().glb()); + + TypeMem m1 = TypeMem.make(1,TypeNil.NIL); + TypeMem m2 = TypeMem.make(2,TypeInteger.U16); + TypeMem m3 = TypeMem.make(3,TypeFloat.F64); + TypeMem m4 = TypeMem.make(4,TypeInteger.BOT); + + Assert.assertNotEquals(m1, m2); + Assert.assertNotEquals(m2, m3); + Assert.assertNotEquals(m3, m4); + + Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); + 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,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); + Assert.assertEquals(s1, ptr1._obj); + TypeMemPtr ptr2 = TypeMemPtr.make(s2); + Assert.assertEquals(s2, ptr2._obj); + + TypeMemPtr ptr1nil = TypeMemPtr.makeNullable(s1); + Assert.assertEquals(s1, ptr1nil._obj); + 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.makeRO(), ptr1.glb()); + + Assert.assertEquals(ptr1, ptr1.dual().dual()); + Assert.assertEquals(ptr1.glb().makeRO(), ptr1.dual().glb()); + Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT), ptr1.meet(ptr2nil)); + Assert.assertEquals(ptr1.glb(), ptr1.meet(TypeNil.NIL).makeRO()); + + TypeMemPtr TOP = TypeMemPtr.TOP; + 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, ptr1_meet_ptr2); + Type NULL_join_ptr1 = NULL.join(ptr1); + Assert.assertEquals(TypePtr.XNPTR, NULL_join_ptr1); + Type NULL_join_PTR = PTR.join(NULL); + Assert.assertEquals(TypePtr.XNPTR, NULL_join_PTR); + Type ptr1_dual = ptr1.dual(); + Type nullableptr1_dual = ptr1nil.dual(); + } + + // Test theoretical properties. + // This is a symmetric complete bounded (ranked) lattice. + // Also, the meet is commutative and associative. + // The lattice has a dual (symmetric), and join is ~(~x meet ~y). + // See https://en.wikipedia.org/wiki/Lattice_(order). + @Test + public void testLatticeTheory() { + Type[] ts = Type.gather(); + + // Confirm commutative & complete + for( Type t0 : ts ) + for( Type t1 : ts ) { + check_commute (t0,t1); + check_symmetric(t0,t1); + } + + // Confirm associative + for( Type t0 : ts ) + for( Type t1 : ts ) + for( Type t2 : ts ) + assoc(t0,t1,t2); + + // Confirm symmetry. If A isa B, then A.join(C) isa B.join(C) + for( Type t0 : ts ) + for( Type t1 : ts ) + if( t0.isa(t1) ) + for( Type t2 : ts ) { + Type t02 = t0.join(t2); + Type t12 = t1.join(t2); + Type mt = t02.meet(t12); + assertSame(mt,t12); + } + } + + // By design in meet, args are already flipped to order _type, which forces + // symmetry for things with badly ordered _type fields. The question is + // still interesting for other orders. + private static void check_commute( Type t0, Type t1 ) { + if( t0==t1 ) return; + if( t0.is_simple() && !t1.is_simple() ) return; // By design, flipped the only allowed order + Type mta = t0.meet(t1); + Type mtb = t1.meet(t0); // Reverse args and try again + assertSame(mta,mtb); + } + + // A & B = MT + // Expect: ~A & ~MT == ~A + // Expect: ~B & ~MT == ~B + private static void check_symmetric( Type t0, Type t1 ) { + if( t1==t0 ) return; + Type mt = t0.meet(t1); + Type dm = mt.dual(); + Type d0 = t0.dual(); + Type d1 = t1.dual(); + Type ta = dm.meet(d1); + Type tb = dm.meet(d0); + assertSame(ta,d1); + assertSame(tb,d0); + } + + private static void assoc( Type t0, Type t1, Type t2 ) { + Type t01 = t0 .meet(t1 ); + Type t12 = t1 .meet(t2 ); + Type t01_2 = t01.meet(t2 ); + Type t0_12 = t0 .meet(t12); + assertSame(t01_2,t0_12); + } + + // Test cyclic types and meets + @Test + public void testCyclic0() { + Type d0 = TypeStruct.S1.dual(); + Type d1 = d0.dual(); + assertSame(TypeStruct.S1,d1); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java new file mode 100644 index 00000000..a3b87e90 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -0,0 +1,383 @@ +package com.seaofnodes.simple.evaluator; + +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; + +import java.util.*; + +public class Evaluator { + + private static final Object MEMORY = new Object(); + + public record Obj(TypeStruct struct, Object[] fields) { + private void init(IdentityHashMap objs) { + var oid = objs.get(this); + if (oid != null) { + if (oid != 0) objs.put(this, 0); + return; + } + objs.put(this, -1); + for (var obj : fields) { + if (obj instanceof Obj o) o.init(objs); + } + } + private static int p(StringBuilder sb, IdentityHashMap objs, int id, String indentation, String step, String sep, Object obj) { + if (obj instanceof Obj o) return o.p(sb, objs, id, indentation, step, sep); + sb.append(obj); + return id; + } + private int p(StringBuilder sb, IdentityHashMap objs, int id, String indentation, String step, String sep) { + var cid = objs.get(this); + assert cid != null; + if (cid > 0) { + sb.append("obj@").append(cid); + return id; + } + if (struct._name.equals("[u8]")) { + sb.append('"'); + for (int i=struct._fields.length-1; i= 0x20 && n < 0x80) { + if (n == 0x22 || n == 0x5C) sb.append("\\"); + sb.append((char)n); + } else { + sb.append("\\x").append("0123456789abcdef".charAt(n >> 4)).append("0123456789abcdef".charAt(n & 0xF)); + } + } + sb.append('"'); + return id; + } + sb.append("Obj<").append(struct._name).append(">"); + if (cid == 0) { + cid = id++; + objs.put(this, cid); + sb.append("@").append(cid); + } + sb.append("{"); + if (struct._fields.length == 0) { + assert !struct.isAry(); + sb.append("}"); + return id; + } + String nextIndent = indentation + step; + int e = struct._fields.length - 1; + for(int i=0; i e) { + String innerIndent = nextIndent + step; + sb.append(innerIndent); + id = p(sb, objs, id, nextIndent, step, sep, fields[e]); + for (int i = e+1; i < fields.length; i++) { + sb.append(sep).append(innerIndent); + id = p(sb, objs, id, nextIndent, step, sep, fields[i]); + } + sb.append(nextIndent); + } + sb.append("]"); + } else { + id = p(sb, objs, id, nextIndent, step, sep, fields[e]); + } + sb.append(indentation).append("}"); + return id; + } + private StringBuilder p(StringBuilder sb, String indentation, String step, String sep) { + var objs = new IdentityHashMap(); + init(objs); + p(sb, objs, 1, indentation, step, sep); + return sb; + } + @Override + public String toString() { + if (struct._name.equals("[u8]")) { + var sb = new StringBuilder(); + for (int i=struct._fields.length-1; i= 0 ) return idx; + throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name); + } + + public enum Status { + TIMEOUT, + FALLTHROUGH + } + + /** + * Find the start node from some node in the graph or null if there is no start node + */ + private static StartNode findStart(BitSet visit, Node node) { + if (node == null) return null; + if( visit.get(node._nid) ) return null; + visit.set(node._nid); + StartNode start = node instanceof StartNode ? (StartNode) node : null; + for( Node def : node._inputs ) { + var res = findStart(visit,def); + if( res != null ) start = res; + } + for( Node use : node._outputs ) { + var res = findStart(visit,use); + if( res != null ) start = res; + } + return start; + } + + private final Object[] values; + private final ArrayList phiCache = new ArrayList<>(); + private final StartNode start; + private final Scheduler.Block startBlock; + + public Evaluator(Node graph) { + var visited = new BitSet(); + this.start = findStart(visited, graph); + if (this.start == null) { + this.values = null; + this.startBlock = null; + return; + } + this.startBlock = Scheduler.schedule(this.start); + this.values = new Object[visited.length()]; + } + + private long div(DivNode div) { + long in2 = vall(div.in(2)); + return in2 == 0 ? 0 : vall(div.in(1)) / in2; + } + private double div(DivFNode div) { + double in2 = vald(div.in(2)); + return in2 == 0 ? 0 : vald(div.in(1)) / in2; + } + + private static long offToIdx(long off, TypeStruct t) { + off -= t.aryBase(); + int scale = t.aryScale(); + long mask = (1L << scale)-1; + assert (off & mask) == 0; + return off>>scale; + } + + private Object alloc(NewNode alloc) { + TypeStruct type = alloc._ptr._obj; + Object[] body=null; + int num; + if( type.isAry() ) { + long sz = (Long)val(alloc.in(1)); + long n = offToIdx(sz, type); + if( n < 0 ) + throw new NegativeArraySizeException(""+n); + body = new Object[(int)n+1]; // Array body + var elem = type._fields[1]._type; + if (elem instanceof TypeInteger) { + for (int i=0; i 0L; + case TypeFloat tf -> 0; + default -> null; + }; + } + Object[] mems = new Object[type._fields.length+2]; + // mems[0] is control + mems[1] = new Obj(type,body); // the ref + // mems[2+...] are memory aliases + return mems; + } + + private Object load(LoadNode load) { + var from = (Obj)val(load.ptr()); + var off = vall(load.off()); + var idx = getFieldIndex(from.struct, load, (Long)off); + if( idx==from.struct._fields.length-1 && from.struct.isAry() ) { + long len = from.fields.length - from.struct._fields.length + 1; + long i = offToIdx(off, from.struct); + if( i < 0 || i >= len ) + throw new ArrayIndexOutOfBoundsException("Array index out of bounds " + i + " < " + len); + return from.fields[(int)i+from.struct._fields.length-1]; + + } else + return from.fields[idx]; + } + + private Object store(StoreNode store) { + var to = (Obj)val(store.ptr()); + var off = vall(store.off()); + var val = val(store.val()); + var idx = getFieldIndex(to.struct, store, (Long)off); + if( idx==to.struct._fields.length-1 && to.struct.isAry() ) { + long len = to.fields.length - to.struct._fields.length + 1; + long i = offToIdx(off, to.struct); + if( i < 0 || i >= len ) + throw new RuntimeException("Array index out of bounds " + off + " <= " + len); + to.fields[(int)i+to.struct._fields.length-1] = val; + } else + to.fields[idx] = val; + return null; + } + + private static boolean isTrue(Object obj) { + if (obj == null) return false; + if (obj instanceof Number n) return n.longValue() != 0; + return true; + } + + private Object val(Node node) { + return values[node._nid]; + } + + private long vall(Node node) { + var v = val(node); + if (v instanceof Number n) return n.longValue(); + throw new AssertionError("Not a long " + v); + } + private double vald(Node node) { + var v = val(node); + if (v instanceof Number n) return n.doubleValue(); + if( v == null ) return 0; + throw new AssertionError("Not a double " + v); + } + + private Object cons(ConstantNode cons) { + var type = cons.compute(); + if (type instanceof TypeInteger i) return i.isConstant() ? i.value() : Integer.MAX_VALUE; + if (type instanceof TypeFloat i) return i.value(); + return null; + } + + private Object exec(Node node) { + return switch (node) { + case ConstantNode cons -> cons(cons); + case AddNode add -> vall(add.in(1)) + vall(add.in(2)); + case AddFNode add -> vald(add.in(1)) + vald(add.in(2)); + case BoolNode.EQF eq -> vald(eq.in(1)) == vald(eq.in(2)) ? 1L : 0L; + case BoolNode.LEF le -> vald(le.in(1)) <= vald(le.in(2)) ? 1L : 0L; + case BoolNode.LTF lt -> vald(lt.in(1)) < vald(lt.in(2)) ? 1L : 0L; + case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; + case BoolNode.LE le -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L; + case BoolNode.LT lt -> vall(lt.in(1)) < vall(lt.in(2)) ? 1L : 0L; + case DivNode div -> div(div); + case DivFNode div -> div(div); + case MinusNode minus -> -vall(minus.in(1)); + case MinusFNode minus -> -vald(minus.in(1)); + case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2)); + case MulFNode mul -> vald(mul.in(1)) * vald(mul.in(2)); + case NotNode not -> isTrue(val(not.in(1))) ? 0L : 1L; + case SubNode sub -> vall(sub.in(1)) - vall(sub.in(2)); + case SubFNode sub -> vald(sub.in(1)) - vald(sub.in(2)); + case ShlNode shl -> vall(shl.in(1)) << vall(shl.in(2)); + case ShrNode shr -> vall(shr.in(1)) >>> vall(shr.in(2)); + case SarNode sar -> vall(sar.in(1)) >> vall(sar.in(2)); + case AndNode and -> vall(and.in(1)) & vall(and.in(2)); + case OrNode or -> vall(or .in(1)) | vall(or .in(2)); + case XorNode xor -> vall(xor.in(1)) ^ vall(xor.in(2)); + case CastNode cast -> val(cast.in(1)); + case ToFloatNode cast -> (double)vall(cast.in(1)); + case LoadNode load -> load(load); + case StoreNode store -> store(store); + case 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); + }; + } + + /** + * Run the graph until either a return is found or the number of loop iterations are done. + */ + public Object evaluate(long parameter, int loops) { + if (start == null) return Status.TIMEOUT; + var s = new Object[start.compute()._types.length]; + s[1] = MEMORY; + s[2] = parameter; + values[start._nid] = s; + int i=0; + Scheduler.Block block = this.startBlock; + for(;;) { + 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 phi)) break; + var val = region instanceof FunNode fun && "main".equals(fun._name) && ((ParmNode)phi)._idx==2 && exit==1 + ? parameter + : val(phi.in(exit)); + phiCache.add(val); + } + for (i=0; i + *
+ * This scheduler is used for tests and is not the final scheduler. + *
+ *
+ * The scheduler schedules not as late as possible. Since it is just for test cases this is fine. + * A better scheduler will try to place nodes outside of loops. Due to the schedule late strategy + * this scheduler might place initialization code in loops. + *
+ * We schedule late here since memory edges have some implicit information. There can only be one + * memory edge (for a field) at a time. However, before if statements this might split. + * When scheduling early a store might be moved out of the loop but then there are two edges alive. + * The one through the store node and the adjacent one. This is an invalid schedule and instead of + * handling this case a late scheduler does not have this problem as memory edges are combined + * through phi nodes. + *
+ *
+ * A bit about this scheduler. It first discovers all alive nodes and allocates side data for them. + * Then the control flow graph is build. Then, all phis are placed and finally all the remaining nodes + * in an order where a node is placed when all alive uses are placed. Finally, the output is produced. + */ +public class Scheduler { + + /** + * A basic block with a schedule of the containing nodes. + * + * @param nodes The nodes in the final schedule of this block + * @param exit The exit node of this block. + * @param exitId In case the next block is a region this gives the entry id into the region. + * @param next The next blocks. + */ + public record Block(Node[] nodes, Node exit, int exitId, Block[] next) {} + + /** + * Definition of a block in the building process. + */ + private static class BasicBlock { + + /** + * Dominator of this block + */ + final BasicBlock dom; + /** + * Id of this block where a.depth < b.depth means that a is before b or + * both are in different branches. + */ + final int depth; + /** + * Previous blocks + */ + final BasicBlock[] prev; + /** + * Entry to this block + */ + final Node entry; + /** + * Schedules node in reverse order. + */ + final ArrayList reverseSchedule = new ArrayList<>(); + + /** + * Initialize the block. + * @param entry The node that started this block + * @param depth The depth of this node. All previous nodes need to have a lower value. + * @param prev The previous blocks. + */ + BasicBlock(Node entry, int depth, BasicBlock... prev) { + BasicBlock dom = null; + int max = -1; + for(var bb: prev) { + max = Math.max(max, bb.depth); + dom = dom==null?bb:dom(dom, bb); + } + assert depth > max; + this.dom = dom; + this.depth = depth; + this.entry = entry; + this.prev = prev; + } + BasicBlock(Node entry, BasicBlock prev) { + this(entry,prev.depth+1,prev); + } + + } + + /** + * Ancillary data for nodes used during the scheduling process. + */ + private static class NodeData { + + /** + * The node this ancillary data is used for. + */ + final Node node; + + /** + * Number of alive users not yet scheduled. + */ + int users = 1; + + /** + * Block into which the node should be placed so far. + * This will be updated with every placed use. + */ + BasicBlock block; + + /** + * Initialize ancillary data for a node + * @param node The node this ancillary data is associated with. + */ + NodeData(Node node) { + this.node = node; + } + + } + + /** + * Ancillary data for nodes. + */ + private final IdentityHashMap data = new IdentityHashMap<>(); + /** + * List of nodes which can be placed since all users are placed. + */ + private final Stack scheduleQueue = new Stack<>(); + + /** + * Get the ancillary data for an alive node. + * @param node The node for which the ancillary data is requested. + * @return The ancillary data for the node. + */ + NodeData d(Node node) { + return od(node).orElseThrow(AssertionError::new); + } + + /** + * Get the ancillary data for a potentially dead node. + * @param node The node for which the ancillary data is requested. + * @return The ancillary data for the node an alive node or + * Optional.empty() for null or dead nodes. + */ + Optional od(Node node) { + return Optional.ofNullable(data.get(node)); + } + + /** + * Checks a node for validity + * @param data The node to check. + * @return true if all placed inputs are before this node. + */ + private boolean isValid(NodeData data) { + return data.node._inputs.stream() + .map(i->i==null?null:d(i)) + .map(d->d==null||d.users>0?null:d.block) + .allMatch(d->d==null||dom(d, data.block)==d); + } + + /** + * Checks that node is not XCtrl. + * @param node The node to check. + * @return true if the node is not XCtrl. + */ + private static boolean isNotXCtrl(Node node) { + return !(node instanceof ConstantNode c && c.compute() == Type.XCONTROL) && !(node instanceof XCtrlNode); + } + + /** + * Return the dominator of a and b + * @param a Block a + * @param b Block b + * @return The dominator of a and b + */ + private static BasicBlock dom(BasicBlock a, BasicBlock b) { + while (a!=b) { + if (a.depth >= b.depth) a=a.dom; + if (b.depth > a.depth) b=b.dom; + } + return a; + } + + /** + * Return if a is before b. + * @param a Block a + * @param b Block b + * @return true is a is before b. + */ + private static boolean isBefore(BasicBlock a, BasicBlock b) { + while (b.depth > a.depth) { + while (b.dom.depth > a.depth) b = b.dom; + for (int i=0; i{ + // before might be in a different branch. So check this case with isBefore + // and only refine the placement if it is not in a different branch. + if (isBefore(d.block, data.block)) refinePlacement(data, d.block); + }); + } + + /** + * Schedule all nodes not yet scheduled. + */ + private void doSchedule() { + while (!scheduleQueue.isEmpty()) { + var data = scheduleQueue.pop(); + assert !isPinnedNode(data); + + assert data.block != null; + assert data.users == 0; + + if (data.node instanceof LoadNode l) { + assert isValid(data); + // Handle anti-deps of load nodes. + // At this point all anti-dep nodes are scheduled, + // but they did not refine the placement + // so do that now. + var mem = l.in(1); + for(var out : mem._outputs) { + if (out instanceof PhiNode p) { + var r = p.in(0); + for (int i = 1; i < p.nIns(); i++) { + if (p.in(i) == mem) optionalRefinePlacement(data, r.in(i)); + } + } else if (!(out instanceof LoadNode)) { + optionalRefinePlacement(data, out); + } + } + } + + assert isValid(data); + data.block.reverseSchedule.add(data.node); + + for(var in:data.node._inputs) { + if (in!=null) update(d(in), data.block); + } + 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 + assert this.data.values().stream().noneMatch(d->d.block==null); + } + + /** + * Decrement the not-yet-placed users of a block. + * @param data The node for which the users should be decremented. + */ + private void decUsers(NodeData data) { + assert data.users > 0; + if (--data.users == 0) { + assert data.block != null; + assert isValid(data); + + // When all users are gone this node can be scheduled. + scheduleQueue.push(data); + } + } + + /** + * Update the placement of a node + * @param data The node to update + * @param block The block before which the node should happen. + */ + private void update(NodeData data, BasicBlock block) { + assert block != null; + if (data.users == 0) { + assert isPinnedNode(data); + return; + } + refinePlacement(data, block); + decUsers(data); + } + + /** + * Checks if a CFG node is ready to be placed. This is used for regions joining branches. + * @param node The CFG node to check + * @return true if all parents of a CFG node are placed. + */ + private boolean isCFGNodeReady(Node node) { + if (node instanceof LoopNode l) { + assert d(l.in(1)).block != null; + } else if (node instanceof RegionNode r) { + for(int i=1; id.block==null).orElse(false)) return false; + } + } else if (node instanceof XCtrlNode) { + return false; + } else { + assert d(node.in(0)).block != null; + } + return true; + } + + /** + * Schedule all phi nodes. + * @param phiQueue List of all the phi nodes to schedule. + */ + private void schedulePhis(Stack phiQueue) { + while(!phiQueue.empty()) { + var data = phiQueue.pop(); + var phi = (PhiNode) data.node; + var r = phi.in(0); + data.block = d(r).block; + for(int i=1; iupdate(d(in), d.block)); + } + } + } + + /** + * Build the control flow graph. + * @param start The start node. + */ + private void doBuildCTF(StartNode start) { + var queue = new Stack(); + var phiQueue = new Stack(); + queue.push(d(start)); + while (!queue.isEmpty()) { + var data = queue.pop(); + var node = data.node; + assert node instanceof CFGNode; + 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; 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. + // Put them on a list for later scheduling. + for (var out:r._outputs) { + if (out instanceof PhiNode p) { + var d = this.data.get(p); + if (d!=null) { + d.users=0; + phiQueue.push(d); + } + } + } + } + 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)); + } + + // Schedule all phi nodes. + schedulePhis(phiQueue); + } + + /** + * Mark a node alive and create ancillary data for it. + * @param queue List into which this node should be placed if it needs to be visited. + * @param node Node which should be marked alive. + * @param cfg If this node is a CFG node. + */ + private void markAlive(Stack queue, Node node, boolean cfg) { + var nd = od(node).orElse(null); + if (nd != null) { + // Node was already visited, just increase the users. + if (nd.users>0) nd.users++; + return; + } + assert node instanceof CFGNode == cfg; + assert isNotXCtrl(node); + nd = new NodeData(node); + if (cfg) nd.users=0; + data.put(node, nd); + queue.push(nd); + } + + /** + * Mark all alive nodes. + * First all CFG nodes are marked, then all other nodes. + * @param node THe start node. + */ + 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) ) { + 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); + } + // Mark all other nodes. + while (!dataQueue.isEmpty()) { + var data = dataQueue.pop(); + node = data.node; + assert !(node instanceof CFGNode); + if (node instanceof PhiNode phi) { + var r = phi.in(0); + for (int i=1; id.users++); + } + } + } + + /** + * Helper function to append the nodes of a block to an array of nodes + * @param arr The array the nodes of a block should be appended to. + * @param node A potentially separator node + * @param block The block from which the nodes should be appended. + * @return The combined new array. + */ + private static Node[] appendNodes(Node[] arr, Node node, BasicBlock block) { + var idx = arr.length; + arr = Arrays.copyOf(arr, arr.length+block.reverseSchedule.size()+(node==null?0:1)); + if (node != null) arr[idx++] = node; + for(int i=block.reverseSchedule.size()-1;i>=0;i--) { + arr[idx++] = block.reverseSchedule.get(i); + } + return arr; + } + + /** + * Find the CFG output of a node + * @param node The node + * @return The CFG output of the node. + */ + private static CFGNode findSingleCFGOut(Node node) { + if (node instanceof StartNode) { + for(var n:node._outputs) + if (n instanceof FunNode fun && "main".equals(fun._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 cfg) return cfg; + return null; + } + + /** + * Build the final data structure after all the scheduling happened. + * @param start The start node + * @return The final schedule. + */ + private Block build(Node start) { + var blocks = new IdentityHashMap(); + var queue = new Stack(); + queue.push(d(start)); + + // Visit all CFG nodes and create blocks for them. + // This can combine blocks. + while(!queue.isEmpty()) { + var data = queue.pop(); + var first = data.node; + Node prev; + var last = first; + Node[] arr = new Node[0]; + if (first instanceof RegionNode) { + var nodes = new ArrayList(); + for(var out: first._outputs) { + if (out instanceof PhiNode) { + if(od(out).isPresent()) nodes.add(out); + } + } + arr = nodes.toArray(arr); + } + arr = appendNodes(arr, null, data.block); + assert !(first instanceof IfNode); + for(;;) { + prev = last; + last = findSingleCFGOut(last); + if (last == null) break; + if (last instanceof RegionNode) { + if (blocks.get(last) == null && last != first) + queue.push(d(last)); + break; + } + if (last instanceof ReturnNode) break; + if (last instanceof IfNode if_) { + for(var out:if_._outputs) if (out instanceof CFGNode && blocks.get(out) == null) queue.push(d(out)); + break; + } + data = d(last); + arr = appendNodes(arr, data.node, data.block); + } + blocks.put(first, switch(last) { + 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]); + default -> throw new AssertionError("Unexpected block exit node"); + }); + } + // Update the next pointer of all blocks. + for (var block: blocks.values()) { + switch(block.exit) { + case null: break; + case IfNode i: + for(var out:i._outputs) if (out instanceof CProjNode p) block.next[p._idx] = blocks.get(p); + break; + case RegionNode r: + block.next[0] = blocks.get(r); + break; + default: + assert block.exit instanceof ReturnNode; + } + } + // And return the block for the start node. + return blocks.get(start); + } + + /** + * Create a schedule for the program reachable from start. + * @param start The start node + * @return The final schedule. + */ + public static Scheduler.Block schedule(StartNode start) { + var scheduler = new Scheduler(); + scheduler.doMarkAlive(start); + scheduler.doBuildCTF(start); + scheduler.doSchedule(); + return scheduler.build(start); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java new file mode 100644 index 00000000..30a548ad --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -0,0 +1,174 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Eval2; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.Node; +import java.util.ArrayList; +import java.util.Objects; +import java.util.Random; +import java.util.function.Consumer; + +/** + * Implementation of the fuzzer. + * Random testcases are generated using the ScriptGenerator. + * This will generate a script similar to how the parser parses it but instead of parsing it will + * randomly choose a variation the parser would parse and generate it. + * These scripts are the parsed by the parser and all exceptions are caught and filtered + * to only show one occurrence of one problem. This includes script which generate different + * results when the compiled graph with and without peeps is executed. + * To aid debugging scripts that cause errors are then reduced by applying rules and checking + * that the same issue persists. + */ +public class Fuzzer { + + private static final int EVAL_TIMEOUT = 1000; + + /** + * List of exceptions already encountered. + * This is used to filter new exceptions and discard them if they are already found. + */ + private final ArrayList exceptions = new ArrayList<>(); + + /** + * Filter and record an exception in a script. + * @param e The exception caused by the script + * @param script The script causing the exception + * @param reproducer Reproducer which should be used to reproduce the test case. + */ + private void recordException(Throwable e, String script, Consumer reproducer, long seed) { + for (var ex : exceptions) { + if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return; + } + exceptions.add(e); + System.out.println("========== Stack =========="); + e.printStackTrace(System.out); + System.out.println("========== Seed =========="); + System.out.println(seed); + //System.out.println("========== Code ==========="); + //System.out.println(script); + System.out.println("========= Reduced ========="); + System.out.println(Reducer.reduce(script, e, reproducer)); + System.out.println("==========================="); + System.out.flush(); + } + + private static boolean neq(Object a, Object b) { + if (Objects.equals(a, b)) return false; + return true; + } + + /** + * Check that two graphs result in the same output when supplied with a value + * @param e1 Evaluator for the first graph + * @param e2 Evaluator for the second graph + * @param in The input value to both graphs to test for an equal output + */ + private static void checkGraphs(CodeGen code1, CodeGen code2, long in) { + var r1 = Eval2.eval(code1, in, EVAL_TIMEOUT); + var r2 = Eval2.eval(code2, in, EVAL_TIMEOUT); + if( r1 == null || r2 == null ) return; // Timeout test invalid + if( neq(r1, r2) ) + throw new RuntimeException("Different calculations values " + r1 + " vs " + r2); + } + + /** + * Run checks for script. Compile the script with peeps enabled and disabled. + * Check that exceptions raised in the parser by both methods are the same and only happens if the script may be invalid. + * If the script was successfully parsed check that both version behave the same. + * @param script The script to test + * @param valid If the script is definitely valid. If not some exceptions may be suppressed. + */ + private static void runCheck(String script, boolean valid) { + CodeGen code1; + try { + code1 = FuzzerUtils.parse(script, 123); + } catch (RuntimeException e1) { + try { + FuzzerUtils.parse(script, 456); + } catch (RuntimeException e2) { + if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) { + if (!valid || e1.getClass() == Parser.ParseException.class) return; + } else { + e1.addSuppressed(e2); + } + } + throw e1; + } + CodeGen code2 = FuzzerUtils.parse(script, 456); + checkGraphs(code1, code2, 0); + checkGraphs(code1, code2, 1); + checkGraphs(code1, code2, 10); + } + + /** + * Check that the script does not result in exceptions. + * @param script The script to test. + * @param valid If the script is valid or if it might contain syntax errors. + */ + private void check(String script, boolean valid, long seed) { + try { + runCheck(script, valid); + } catch (Throwable e) { + recordException(e, script, s->runCheck(s, valid), seed); + } + } + + /** + * Run one test with the given seed, and check for peephole counts. + * @param seed The seed to use for generating this test case + */ + public int fuzzPeepTiming(long seed, int max_nids) { + var rand = new Random(seed); + var sb = new StringBuilder(); + new ScriptGenerator(rand, sb, true).genProgram(); + try { + var code = new CodeGen(sb.toString()); + + code.parse(); + int nids = code.UID(); + if( nids <= max_nids ) return max_nids; // Smaller, looking for trends as we grow + int parse_peeps= code._iter_cnt; + int parse_nops = code._iter_nop_cnt; + double parse_nop_ratio = (double)parse_nops/parse_peeps; + double parse_peeps_per_node = (double)parse_peeps/nids; + + code.opto(); + int iter_peeps= code._iter_cnt; + int iter_nops = code._iter_nop_cnt; + double iter_nop_ratio = (double)iter_nops/iter_peeps; + double iter_peeps_per_node = (double)iter_peeps/nids; + + System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n", + seed, + parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node, + iter_peeps , iter_nops, iter_nop_ratio, iter_peeps_per_node); + return nids; + } catch (Throwable e) { + // ignore exceptions, let the normal fullPeeps catch and reduce, + // we're interested in valid program optimizations + } + return max_nids; + } + + + /** + * Run one test with the given seed. + * @param seed The seed to use for generating this test case + */ + public void fuzzPeeps(long seed) { + var rand = new Random(seed); + var sb = new StringBuilder(); + var valid = new ScriptGenerator(rand, sb, true).genProgram(); + check(sb.toString(), valid, seed); + } + + + /** + * Check that no exceptions happened. + * @return true if no exception happened + */ + public boolean noExceptions() { + return exceptions.isEmpty(); + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java new file mode 100644 index 00000000..669a1e6a --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -0,0 +1,111 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.OutputStream; +import java.io.PrintStream; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.reflect.Field; +import java.util.BitSet; + +/** + * Some utilities for the fuzzer. + */ +class FuzzerUtils { + + /** + * Get the val of a private field + */ + @SuppressWarnings("unchecked") + public static T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException { + return (T) (obj instanceof Class clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj)); + } + + /** + * Get access to a private field + */ + public static Field getField(Class clz, String name) throws NoSuchFieldException { + var field = clz.getDeclaredField(name); + try { + field.setAccessible(true); + } catch (Throwable e) { + // Intentionally left empty + } + return field; + } + + /** + * Try to rethrow an exception or create a runtime exception and throw it. + */ + public static RuntimeException rethrow(Throwable e) { + if (e instanceof RuntimeException re) return re; + if (e instanceof Error er) throw er; + return new RuntimeException(e); + } + + /** + * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing. + */ + public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream()); + + /** + * Check that the messages are similar. + */ + private static boolean similarMessages(String a, String b) { + if (a == null || b == null) return true; + a = a.replaceAll("'\\w+'", "'normalized'").replaceAll("variable \\w+", "variable normalized"); + b = b.replaceAll("'\\w+'", "'normalized'").replaceAll("variable \\w+", "variable normalized"); + return a.equals(b); + } + + /** + * Check if both stack traces have the same first entry. Empty stack traces can happen with NPE optimization + * and allow the other to be any stack trace. + */ + private static boolean sameStackTraceOrigin(StackTraceElement[] a, StackTraceElement[] b) { + if (a == null || a.length == 0 || b == null || b.length == 0) return true; // One or both stack traces are missing. + return a[0].equals(b[0]); + } + + /** + * Checks if two exceptions are caused by the same problem. + */ + public static boolean isExceptionFromSameCause(Throwable a, Throwable b) { + if (a == null || b == null) return a == b; // Handle the null case + if (a.getClass() != b.getClass()) return false; // Different classes + if (!similarMessages(a.getMessage(), b.getMessage())) return false; // Different messages. Null is allowed as wildcard + var s1 = a.getStackTrace(); + var s2 = b.getStackTrace(); + if (!sameStackTraceOrigin(s1, s2)) return false; // Different stack trace origins + if (!isExceptionFromSameCause(a.getCause(), b.getCause())) return false; // Different causes + var o1 = a.getSuppressed(); + var o2 = b.getSuppressed(); + if (o1 == null || o2 == null || o1.length != o2.length) return o1 == o2; // Different suppression + for (int i=0; i {} + + /** + * Holder for the rewrite rules + */ + private record Replace(Pattern pattern, boolean iterate, Replacer... replacements) { + Replace(Pattern p, Object... replacements) { + this(p, replacements[0] == Boolean.TRUE, Arrays.stream(replacements).filter(o->!(o instanceof Boolean)).map(Replace::from).toArray(Replacer[]::new)); + } + private static Replacer from(Object o) { + if (o instanceof Replacer r) return r; + if (o instanceof Integer i) return (s, m)->s.append(m.group(i)); + if (o instanceof String r) return (s, m)->s.append(r); + throw new IllegalArgumentException(); + } + } + + /** + * List of rewrite rules. + */ + private static final Replace[] REPLACEMENTS = { + new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "0", "1"), + new Replace(Pattern.compile("(?<=\\n|^)[^\\n]+(?=\\n|$)"), true, ""), + new Replace(Pattern.compile("(?<=[+\\-*/<>=(])--"), ""), + new Replace(Pattern.compile("\\b--"), "+"), + new Replace(Pattern.compile("-"), ""), + new Replace(Pattern.compile("\\b\\+-"), "-"), + new Replace(Pattern.compile("(?=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"), + new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)(?:\\n[ \\t]*)?}"), "", "{}", 1), + new Replace(Pattern.compile("(?<=\\n|^)([ \\t]*)\\{\\n(.*?)\\n\\1}", Pattern.DOTALL), 2), + new Replace(Pattern.compile("\\(([^()]+)\\)"), 1), + new Replace(Pattern.compile("\\d+\\+"), ""), + new Replace(Pattern.compile("\\+\\d+"), ""), + new Replace(Pattern.compile("\\n\\n+"), "\n"), + new Replace(Pattern.compile("^\\n+|\\n+$"), ""), + new Replace(Pattern.compile("else *"), ""), + new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""), + new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""), + new Replace(Pattern.compile("\\bstruct \\w+ \\{[^{}]*}"), "") + }; + + /** + * Predicate to test if the reduced script generates the same error. + */ + private final Predicate tester; + + /** + * Create a reducer with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + private Reducer(Predicate tester) { + this.tester = tester; + } + + /** + * Rewrites the script with one rewrite rule. + */ + private String doReplacement(String script, Pattern pattern, Replacer[] replacements) { + var matcher = pattern.matcher(script); + var sb = new StringBuilder(); + var last = 0; + var skip = 0; + outer: + while (matcher.find(last + skip)) { + sb.append(script, last, matcher.start()); + last = matcher.end(); + skip = last == matcher.start() ? 1 : 0; + var pos = sb.length(); + for (var replacement : replacements) { + replacement.accept(sb, matcher); + var tail = sb.length(); + sb.append(script, last, script.length()); + if (tester.test(sb.toString())) { + sb.setLength(tail); + continue outer; + } + sb.setLength(pos); + } + last = matcher.start(); + skip = 1; + } + sb.append(script, last, script.length()); + return sb.toString(); + } + + /** + * Clean up variable names from the random ones generated by the fuzzer. + */ + private String cleanVariables(String script) { + var matcher = Pattern.compile("\\b([0-9a-zA-Z_]+) ([0-9a-zA-Z_]+)").matcher(script); + int[] num = {0, 0}; + while (matcher.find()) { + var type = matcher.group(1); + var var = matcher.group(2); + if (type.equals("new")) continue; + String prefix = "v"; + int t = 0; + if (type.equals("struct")) { + t = 1; + prefix = "s"; + } + if (var.matches(prefix+"\\d+")) continue; + while (script.contains(prefix+num[t])) num[t]++; + var n = script.replaceAll("\\b"+var+"\\b", prefix + num[t]); + if (tester.test(n)) { + script = n; + } + } + return script; + } + + /** + * Run all rewrite rules once. + */ + private String doAllReplacements(String script) { + for (var replace: REPLACEMENTS) { + String old; + do { + old = script; + script = doReplacement(script, replace.pattern, replace.replacements); + } while (replace.iterate && !old.equals(script)); + } + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + public static String reduce(String script, Predicate tester) { + var reducer = new Reducer(tester); + String old; + do { + old = script; + script = reducer.doAllReplacements(script); + script = reducer.cleanVariables(script); + } while (!script.equals(old)); + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a reproducer. + * @param ex The exception originally caused by the script + * @param reproducer Test function which throws an exception which will be checked against ex. + */ + public static String reduce(String script, Throwable ex, Consumer reproducer) { + return reduce(script, s->{ + Throwable nex = null; + try { + reproducer.accept(s); + } catch (Throwable e) { + nex = e; + } + return FuzzerUtils.isExceptionFromSameCause(nex, ex); + }); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java new file mode 100644 index 00000000..f119fa1a --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -0,0 +1,869 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.ScopeNode; +import com.seaofnodes.simple.type.TypeInteger; +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Random; +import java.util.function.Predicate; +import static com.seaofnodes.simple.Parser.KEYWORDS; + + +/** + * Generate a pseudo random script. + * This generator will generate the same script for two random number generators initialized with the same seed. + * To generate valid code it implements the parser but instead of parsing it emits the statements and expressions. + * It is guaranteed to terminate. + */ +public class ScriptGenerator { + + private static final int MAX_STATEMENTS_PER_BLOCK = 5; + private static final int MAX_BINARY_EXPRESSIONS_PER_EXPRESSION = 10; + private static final int MAX_UNARY_EXPRESSIONS_PER_EXPRESSION = 6; + private static final int MAX_NAME_LENGTH = 10; + private static final int MAX_BLOCK_DEPTH = 4; + private static final int MAX_EXPRESSION_DEPTH = 10; + private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10; + + /** + * Number of spaces per indentation + */ + private static final int INDENTATION = 4; + /** + * Valid characters for identifiers. The last 10 are not valid for the first character. + */ + private static final String VAR_CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_0123456789"; + + /** + * Flag for a statement that it does not pass on control flow to the next statement. + */ + private static final int FLAG_STOP = 0x01; + /** + * Flag for a statement that it contains a final if statement without an else branch. + */ + private static final int FLAG_IF_WITHOUT_ELSE = 0x02; + /** + * Binary operators. + */ + private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/", "&", ">>", ">>>", "<<"}; + /** + * Unary operators. + */ + private static final String[] UNARY_OP = {"-"}; + + private static class Type { + final String name; + Type(String name) {this.name=name;} + boolean isa(Type other) { return this == other; } + } + + private static class TypeStruct extends Type { + record Field (String name, Type type, TypeStruct struct) {} + Field[] fields; + final TypeNullable nullable = new TypeNullable(this); + TypeStruct(String name) { + super(name); + } + boolean isa(Type other) { return this == other || other == nullable; } + } + + private static class TypeNullable extends Type { + + final Type base; + + TypeNullable(Type base) { + super(base.name+"?"); + this.base = base; + } + + } + + private static final Type TYPE_FLT = new Type("flt"); + + private static class TypeInt extends Type { + + TypeInt(String name) { + super(name); + } + + @Override + boolean isa(Type other) { + return super.isa(other) || other == TYPE_FLT || other instanceof TypeInt; + } + } + + private static final List INTTYPES = new ArrayList<>(); + + static { + for( var e : Parser.defaultTypes().entrySet() ) { + if( e.getValue() instanceof TypeInteger ) { + INTTYPES.add(new TypeInt(e.getKey())); + } + } + } + + private static final Type TYPE_INT = INTTYPES.stream().filter(t->t.name.equals("int")).findAny().get(); + private static final Type TYPE_BOOL = INTTYPES.stream().filter(t->t.name.equals("bool")).findAny().get(); + + private static class Variable { + final String name; + final Type declared; + final Variable shadowing; + Type type; + boolean shadowed = false; + + Variable(String name, Type type, Variable var) { + this.name = name; + this.declared = type; + this.type = type; + this.shadowing = var; + } + } + + /** + * The random number generator used for random decisions. + */ + private final Random random; + /** + * Indentation depth. + */ + private int indentation = 0; + /** + * Output string builder + */ + private final StringBuilder sb; + /** + * Number of nested loops + */ + private int loopDepth = 0; + /** + * Current scope start in the variables list. + */ + private int currScopeStart = 0; + /** + * The depth of blocks allowed. + */ + private int depth = MAX_BLOCK_DEPTH; + /** + * The depth of expressions allowed. + */ + private int exprDepth = MAX_EXPRESSION_DEPTH; + /** + * Current variables in scope. + */ + private final ArrayList variables = new ArrayList<>(); + /** + * All defined structs. + */ + private final ArrayList structs = new ArrayList<>(); + /** + * All forward declared structs + */ + private final ArrayList forwardStructs = new ArrayList<>(); + /** + * Allow to declare structs. + */ + private boolean allowStructs = true; + /** + * If this needs to generate valid scripts or is also allowed to generate invalid ones. + */ + private boolean generateValid; + /** + * If this script might be invalid. + */ + private boolean maybeInvalid = false; + + + /** + * + * @param random the random number generator. + * @param sb the script will be written to this string builder. + * @param generateValid if the script should be guaranteed valid or if it is allowed to contain bugs. + */ + public ScriptGenerator(Random random, StringBuilder sb, boolean generateValid) { + this.random = random; + this.sb = sb; + this.generateValid = generateValid; + } + + /** + * Random number with log distribution + * @param max The maximum value + * @return A random number in the range [0, max) with higher numbers being more uncommon. + */ + private int randLog(int max) { + max--; + int n = 1<=0; i--) { + if ((num & (1<2) return false; + maybeInvalid = true; + return true; + } + + /** + * Lookup a variable by name + * @param name name of the variable + * @return The index of the variable in variables or -1 + */ + private int lookup(String name) { + for (int i=variables.size()-1; i>=0; i--) { + if (variables.get(i).name.equals(name)) return i; + } + return -1; + } + + /** + * Lookup a variable by name + * @param name name of the variable + * @return THe variable of null if not found + */ + private Variable lookupVar(String name) { + int idx = lookup(name); + return idx == -1 ? null : variables.get(idx); + } + + /** + * Add a variable to the current scope + * @param name The name of the variable + * @param type The declared type of the variable + */ + private void addVariable(String name, Type type) { + var old = lookupVar(name); + variables.add(new Variable(name, type, old)); + if (old != null) old.shadowed = true; + } + + /** + * Pop variables to level to + * @param to Level until which variables should be popped + */ + private void popVariables(int to) { + while (variables.size() > to) { + var v = variables.removeLast(); + if (v.shadowing != null) v.shadowing.shadowed = false; + } + } + + /** + * Get a random visible variable patching pred + * @param pred The predicate the variable needs to match + * @return A random visible variable matching pred or null if no variable mached pred. + */ + private Variable findVisibleVariablesMatching(Predicate pred) { + int num=0; + for (var v:variables) { + if (!v.shadowed && pred.test(v)) num++; + } + if (num == 0) return null; + num = random.nextInt(num); + for (var v:variables) { + if (!v.shadowed && pred.test(v) && num-- == 0) return v; + } + throw new AssertionError(); + } + + /** + * Get a structure by name + * @param name Name of the structure + * @return The structure of null + */ + private TypeStruct getStruct(String name) { + for (var s:structs) { + if (s.name.equals(name)) return s; + } + for (var s:forwardStructs) if (s.name.equals(name)) return s; + return null; + } + + /** + * Generate a variable name. This might be new random name or a name from an outer scope. + * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope. + * @return The variable name. + */ + private String getVarName() { + if (currScopeStart > 0 && random.nextInt(10) > 7) { + // Use a variable outside the current scope. + var v = variables.get(random.nextInt(currScopeStart)); + if (lookup(v.name) < currScopeStart) return v.name; + if (!generateValid) { + maybeInvalid = true; + return v.name; + } + } + // Generate a new random variable name + StringBuilder sb = getRandomName(); + var v = sb.toString(); + if (!generateValid && (KEYWORDS.contains(v) || lookup(v) >= currScopeStart)) { + maybeInvalid = true; + return v; + } + while (KEYWORDS.contains(v) || lookup(v) >= currScopeStart) { + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + v = sb.toString(); + } + return v; + } + + private T randFromList(List list) { + return list.get(random.nextInt(list.size())); + } + + /** + * Get a random structure name + * @return A random structure name + */ + private String getStructName() { + if (!structs.isEmpty() && generateInvalid()) return randFromList(structs).name; + if (!forwardStructs.isEmpty() && generateInvalid()) return randFromList(forwardStructs).name; + + // Generate a new random struct name + StringBuilder sb = getRandomName(); + var v = sb.toString(); + if (!generateValid && (KEYWORDS.contains(v) || getStruct(v) != null)) { + maybeInvalid = true; + return v; + } + while (KEYWORDS.contains(v) || getStruct(v) != null) { + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + v = sb.toString(); + } + return v; + } + + public TypeInt getIntType() { + return randFromList(INTTYPES); + } + + /** + * Get a random type + * @return A random type + */ + private Type getType(boolean allowForward) { + int t = random.nextInt(10); + if( t<5 || structs.isEmpty() ) return getIntType(); + if( t<7 ) return TYPE_FLT; + if (allowForward && random.nextInt(10)==0) { + int i=random.nextInt(forwardStructs.size()+1); + if (i>0) return forwardStructs.get(i-1).nullable; + var name = getStructName(); + var struct = new TypeStruct(name); + forwardStructs.add(struct); + return struct.nullable; + } + TypeStruct struct = randFromList(structs); + if (random.nextBoolean()) return struct.nullable; + return struct; + } + + private Type getType() { + return getType(false); + } + + /** + * Generates a program and writes it into the string builder supplied in the constructor. + * @return If the program is allowed to be invalid returns if something potentially invalid was generated. + */ + public boolean genProgram() { + var oldGenerateValid = generateValid; + if (!generateValid && random.nextBoolean()) generateValid = true; + this.maybeInvalid = false; + addVariable(ScopeNode.ARG0, TYPE_INT); + currScopeStart = variables.size(); + if ((genStatements() & FLAG_STOP) == 0) { + if (generateValid || random.nextInt(10)<7) { + genReturn(); + } else { + this.maybeInvalid = true; + } + } + generateValid = oldGenerateValid; + return !this.maybeInvalid; + } + + /** + * Generate a list of statements. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated + */ + public int genStatements() { + var num = random.nextInt(MAX_STATEMENTS_PER_BLOCK * (depth+1)); + for (int i=0; i allowStructs || generateInvalid() ? genStruct() : genAssignment(); + case 1 -> genBlock(); + case 2 -> genIf(); + case 3 -> genCountedLoop(); + case 4 -> genWhile(); + case 5, 6 -> genDecl(); + case 7, 8, 9 -> genAssignment(); + case 10 -> genNullCheck(); + default -> genExit(); + }; + } + + /** + * Generate a new structure + * @return 0 + */ + public int genStruct() { + int idx = random.nextInt(forwardStructs.size()+10); + TypeStruct struct; + if (idx < 10) { + var name = getStructName(); + struct = new TypeStruct(name); + forwardStructs.add(struct); + } else { + struct = forwardStructs.get(idx-10); + } + var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)]; + sb.append("struct ").append(struct.name).append(" {\n"); + indentation += INDENTATION; + for (int i=0; i { + depth++; + indentation -= INDENTATION; + var ret = genBlock(); + indentation += INDENTATION; + depth--; + yield ret; + } + case 6 -> genIf(); + case 7 -> genCountedLoop(); + case 8 -> genWhile(); + case 9 -> genAssignment(); + case 10 -> genNullCheck(); + default -> genExit(); + }; + depth++; + } + indentation -= INDENTATION; + allowStructs = oldAllowStructs; + return res; + } + + /** + * Generate an exit. This can be return or break and continue when in a loop. + * @return FLAG_STOP + */ + public int genExit() { + if (loopDepth == 0 && generateValid) return genReturn(); + return switch (random.nextInt(7)) { + case 0,1,2 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("continue;"); + yield FLAG_STOP; + } + case 3,4,5 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("break;"); + yield FLAG_STOP; + } + default -> genReturn(); + }; + } + + /** + * Generate a block statement. After a certain depth only empty blocks are generated to ensure termination of the generator. + * @return flag FLAG_STOP for the generated statement + */ + public int genBlock() { + if (depth == 0) { + sb.append("{}"); + return 0; + } + var oldAllowStructs = allowStructs; + var oldCSS = currScopeStart; + allowStructs = false; + currScopeStart = variables.size(); + depth--; + sb.append("{\n"); + indentation += INDENTATION; + var stop = genStatements(); + indentation -= INDENTATION; + printIndentation().append("}"); + popVariables(currScopeStart); + depth++; + currScopeStart = oldCSS; + allowStructs = oldAllowStructs; + return stop & ~FLAG_IF_WITHOUT_ELSE; + } + + /** + * Generate an if statement with an optional else block. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genIf() { + sb.append("if("); + genExpression(TYPE_BOOL, true); + sb.append(") "); + var stop = genStatementBlock(); + if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { + sb.append("\n"); + printIndentation().append("else "); + stop &= genStatementBlock(); + } else { + stop = FLAG_IF_WITHOUT_ELSE; + } + return stop; + } + + /** + * Generate a block with a null check + * if (nullable) { handle_nullable_as_non_nullable; } + */ + public int genNullCheck() { + var v = findVisibleVariablesMatching(va->va.declared instanceof TypeNullable); + if (v == null) return genIf(); + var n = (TypeNullable)v.declared; + boolean negate = random.nextBoolean(); + sb.append("if("); + if (negate) sb.append("!"); + sb.append(v.name).append(")"); + if (!negate) v.type = n.base; + var stop = genStatementBlock(); + v.type = n; + if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { + sb.append("\n"); + printIndentation().append("else "); + if (negate) v.type = n.base; + stop &= genStatementBlock(); + v.type = n; + } else { + stop = FLAG_IF_WITHOUT_ELSE; + } + return stop; + } + + /** + * Generate a while loop. + * @return 0 + */ + public int genWhile() { + sb.append("while("); + genExpression(TYPE_BOOL, true); + sb.append(") "); + loopDepth++; + genStatementBlock(); + loopDepth--; + return 0; + } + + /** + * Generate a counted loop of the form + * + * { + * int varname = start_expr; + * while (varname < end_expr) loop_body; + * } + * + * @return 0 + */ + public int genCountedLoop() { + if (depth == 0) return genWhile(); + var oldCSS = currScopeStart; + currScopeStart = variables.size(); + sb.append("{\n"); + indentation += INDENTATION; + String name = getVarName(); + printIndentation().append("int ").append(name).append("="); + genExpression(TYPE_INT, true); + sb.append(";\n"); + addVariable(name, TYPE_INT); + printIndentation().append("while(").append(name).append("<"); + genExpression(TYPE_INT, true); + sb.append(") {\n"); + indentation += INDENTATION; + depth--; + loopDepth++; + printIndentation().append(name).append("=").append(name).append("+"); + genExpression(TYPE_INT, true); + sb.append(";\n"); + genStatements(); + loopDepth--; + depth++; + indentation -= INDENTATION; + printIndentation().append("}\n"); + indentation -= INDENTATION; + printIndentation().append("}"); + popVariables(currScopeStart); + currScopeStart = oldCSS; + return 0; + } + + /** + * Generate a declaration statement. + * @return 0 + */ + public int genDecl() { + var type = getType(); + var name = getVarName(); + // Always make them mutable + sb.append(generateInvalid() ? getRandomName() : type.name).append(" !").append(name); + if (!(type instanceof TypeNullable) || random.nextBoolean()) { + sb.append("="); + genExpression(type, true); + } + sb.append(";"); + addVariable(name, type); + return 0; + } + + /** + * Generate an assignment statement. + * @return 0 + */ + public int genAssignment() { + Type type; + Type declared; + if (generateInvalid()) { + sb.append(getRandomName()); + type = getType(); + declared = type; + } else { + var v = findVisibleVariablesMatching(va->true); + if (v == null) return genDecl(); + sb.append(v.name); + type = v.type; + declared = v.declared; + } + if (generateInvalid()) { + var name = getRandomName(); + sb.append(".").append(name); + declared = getType(); + } else if (type instanceof TypeStruct s && s.fields.length > 0 && random.nextBoolean()) { + var field = s.fields[random.nextInt(s.fields.length)]; + sb.append(".").append(field.name); + declared = field.type; + } + sb.append("="); + genExpression(declared, true); + sb.append(";"); + return 0; + } + + /** + * Generate a return statement. + * @return FLAG_STOP + */ + public int genReturn() { + var type = getType(); + sb.append("return "); + genExpression(type, true); + sb.append(";"); + return FLAG_STOP; + } + + /** + * Generate a binary expression. + * This method does not care about operator precedence. + */ + public void genExpression(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); + if (!(type instanceof TypeInt) && type != TYPE_FLT) { + genUnary(type, false); + return; + } + var num = randLog(MAX_BINARY_EXPRESSIONS_PER_EXPRESSION); + while(num-->0) { + genUnary(type, false); + sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); + } + genUnary(type, false); + } + + /** + * Generate a unary expression. + */ + public void genUnary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); + if (!(type instanceof TypeInt) && type != TYPE_FLT) { + genSuffix(type, false); + return; + } + var num = randLog(MAX_UNARY_EXPRESSIONS_PER_EXPRESSION); + while(num-->0) { + sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); + } + genSuffix(type, false); + } + + public TypeStruct.Field getField(Type type) { + int n=0; + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) n++; + } + } + if (n==0) return null; + n = random.nextInt(n); + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) if (n--==0) return f; + } + } + throw new AssertionError(); + } + + /** + * Generate + */ + public void genSuffix(Type type, boolean change) { + genSuffixRecursive(type, change, MAX_SUFFIX_RECURSIVE_DEPTH); + } + + public void genSuffixRecursive(Type type, boolean change, int depth) { + if (change && generateInvalid()) type = getType(); + if (depth > 0 && random.nextBoolean()) { + if (generateInvalid()) { + var field = getRandomName(); + var t = getType(); + genSuffixRecursive(t, true, depth-1); + sb.append(".").append(field); + return; + } else { + var field = getField(type); + if (field != null) { + genSuffixRecursive(field.struct, true, depth-1); + sb.append(".").append(field.name); + return; + } + } + } + genPrimary(type, false); + } + + /** + * Generate a primary expression. + */ + public void genPrimary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); + var rand = random.nextInt(10); + if (rand == 0 && exprDepth != 0) { + sb.append("("); + exprDepth--; + genExpression(type, false); + exprDepth++; + sb.append(")"); + } else if (rand < 6) { + genVariable(type); + } else { + genConst(type); + } + } + + /** + * Generate a constant. + */ + public void genConst(Type type) { + if (generateInvalid()) type = getType(); + if (type instanceof TypeInt || (type == TYPE_FLT && random.nextBoolean())) { + var rand = random.nextInt(10); + switch (rand) { + case 0 -> sb.append("true"); + case 1 -> sb.append("false"); + default -> sb.append(random.nextInt(1<<(rand-2))); + } + } else if (type == TYPE_FLT) { + sb.append(random.nextFloat()); + } else if (type instanceof TypeNullable n) { + if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) { + sb.append("null"); + } else { + sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name); + } + } else { + sb.append("new ").append(generateInvalid() ? getRandomName() : type.name); + } + } + + /** + * Generate a variable. If there are none generate a number instead. + * If the program is allowed to be invalid a random name can be generated in some cases. + */ + public void genVariable(Type type) { + if (generateInvalid()) { + sb.append(getRandomName()); + return; + } + if (generateInvalid()) type = getType(); + var t = type; + var v = findVisibleVariablesMatching(va->va.type.isa(t)); + if (v == null) genConst(type); + else sb.append(v.name); + } + +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn.smp new file mode 100644 index 00000000..188e0a9f --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn.smp @@ -0,0 +1,15 @@ + +struct Person { + int age; +}; + +val fcn = { Person?[] ps, int x -> + val tmp = ps[x]; + if( ps[x] ) + ps[x].age++; +}; + +Person?[] !ps = new Person?[2]; +ps[0] = new Person; +ps[1] = new Person; +fcn(ps,1); diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn2.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn2.smp new file mode 100644 index 00000000..049132d9 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn2.smp @@ -0,0 +1,5 @@ + +val fcn = (arg&1) + ? { int x -> x*x; } + : { int x -> x+x; }; +fcn(arg); diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn3.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn3.smp new file mode 100644 index 00000000..a64564f0 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/fcn3.smp @@ -0,0 +1,42 @@ + +//val fact = { int n -> n <= 1 ? 1 : fact(n-1)*n; } +struct LL { LL? next; int payload; }; + + +struct String { + + val _hashCodeString = { -> + int hash=0; + for( int i=0; i< cs#; i++ ) + hash = hash*31 + cs[i]; + if( !hash ) hash = 123456789; + return hash; + }; + + val equals = { String s -> + if( self == s ) return true; + if( cs# != s.cs# ) return false; + for( int i=0; i< #; i++ ) + if( [i] != s.cs[i] ) + return false; + return true; + }; + + int _hashCode = hash(); + u8[] cs; +}; + + + +val hashCode= { String self -> + int hash = self._hashCode + ? self._hashCode + : self._hashCode = _hashCodeString(self); + return hash; +}; + + +String s = new String { cs = new u8[17]; }; +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s); diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/sieve.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/sieve.smp new file mode 100644 index 00000000..0788e6c5 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/sieve.smp @@ -0,0 +1,32 @@ + +int[] !ary = new int[arg], !primes = new int[arg]; +int nprimes = 0, p=2; +// Find primes while p^2 < arg +while( p*p < arg ) { + // skip marked non-primes + while( ary[p]==1 ) p = p + 1; + // p is now a prime + primes[nprimes] = p; nprimes = nprimes + 1; + // Mark out the rest non-primes + int i = p + p; + while( i < ary# ) { + ary[i] = 1; + i = i + p; + } + p = p + 1; +} +// Now just collect the remaining primes, no more marking +while( p < arg ) { + if( ary[p] == 0 ) { + primes[nprimes] = p; nprimes = nprimes + 1; + } + p = p + 1; +} +// Copy/shrink the result array +int[] !rez = new int[nprimes]; +int j = 0; +while( j < nprimes ) { + rez[j] = primes[j]; + j = j + 1; +} +return rez; -- cgit v1.2.3