From 4369fd94247acf5fef5ebff0ac644671bf165e42 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 12 Sep 2024 11:13:31 -0700 Subject: Chapter 15: Arrays MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: XmiliaH Co-authored-by: Thalia Archibald Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- .../java/com/seaofnodes/simple/BrainFuckTest.java | 80 ++++ .../java/com/seaofnodes/simple/Chapter06Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 28 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 29 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 37 +- .../com/seaofnodes/simple/Chapter14FloatTest.java | 11 - .../java/com/seaofnodes/simple/Chapter14Test.java | 127 +------ .../java/com/seaofnodes/simple/Chapter15Test.java | 416 +++++++++++++++++++++ src/test/java/com/seaofnodes/simple/TypeTest.java | 30 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 184 ++++++++- .../com/seaofnodes/simple/evaluator/Scheduler.java | 71 ++-- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 6 +- 12 files changed, 744 insertions(+), 277 deletions(-) create mode 100644 src/test/java/com/seaofnodes/simple/BrainFuckTest.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter15Test.java (limited to 'src/test/java') diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java new file mode 100644 index 00000000..29ef8732 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -0,0 +1,80 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import org.junit.Ignore; + +import java.nio.charset.StandardCharsets; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +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(";"); + } + + Parser parser = new Parser( + encoded + """ +int pc = 0; +int d = 0; +u8[] data = new u8[100]; +u8[] output = new u8[0]; + +while (pc < program#) { + int command = program[pc]; + if (command == 62) { + d = d + 1; + } else if (command == 60) { + d = d - 1; + } else if (command == 43) { + data[d] = data[d] + 1; + } else if (command == 45) { + data[d] = data[d] - 1; + } else if (command == 46) { + u8[] old = output; + output = new u8[output# + 1]; + int i = 0; + while (i < old#) { + output[i] = old[i]; + i = i + 1; + } + output[i] = data[d]; + } else if (command == 44) { + data[d] = 42; + } else if (command == 91) { + if (data[d] == 0) { + int d = 1; + while (d > 0) { + pc = pc + 1; + command = program[pc]; + if (command == 91) d = d + 1; + if (command == 93) d = d - 1; + } + } + } else if (command == 93) { + if (data[d] != 0) { + int d = 1; + while (d > 0) { + pc = pc - 1; + command = program[pc]; + if (command == 93) d = d + 1; + if (command == 91) d = d - 1; + } + } + } + pc = pc + 1; +} +return output; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Hello World!\n", Evaluator.evaluate(stop, 0, 10000).toString()); + } +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index c5664c9d..d2c46df5 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,42,5);", stop.toString()); + assertEquals("return Phi(Region40,42,5);", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6649c0b0..a5e3a9e0 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -28,10 +28,11 @@ public class Chapter10Test { // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ struct Point { int x; }; + Point?[] points = new Point?[2]; Point point = new Point; point.x = 42; - Point? p = null; - if (arg) p = point; + points[arg] = point; + Point? p = points[1]; """; @Test @@ -54,7 +55,7 @@ public class Chapter10Test { for( String body : new String[] { "return p.x;", "if (p == null) return p.x; return -1;", - "if (!!point) return p.x; return -1;", + "if (!!points) return p.x; return -1;", "if (!!p) { int x = p.x; } return p.x;" } ) { try { @@ -127,7 +128,7 @@ else return v; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new Vector2D;", stop.toString()); + assertEquals("return Vector2D;", stop.toString()); } @Test @@ -165,7 +166,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop15,0,(Phi_a+2));", stop.toString()); } @Test @@ -217,7 +218,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region33,(*void)Phi(Region20,null,new Bar),null);", stop.toString()); + assertEquals("return Phi(Region36,(*void)Phi(Region22,null,Bar),null);", stop.toString()); } @Test @@ -233,7 +234,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region39,4,3);", stop.toString()); + assertEquals("return Phi(Region42,4,3);", stop.toString()); } @Test @@ -308,7 +309,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,new s0,Phi(Region37,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,s0,Phi(Region42,s0,Phi_ret));", stop.toString()); } @Test @@ -326,7 +327,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop17,new s0,Phi(Region38,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop21,s0,Phi(Region43,s0,Phi_ret));", stop.toString()); } @@ -343,7 +344,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop15,s0,Phi(Region39,s0,Phi_ret));", stop.toString()); } @Test @@ -387,7 +388,7 @@ else return new s0; if(new s0.f0) return 0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } @Test @@ -415,7 +416,7 @@ s0 v1 = v0; return v1; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } @@ -547,8 +548,7 @@ return 0; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().iterate(); - // These chapters still bind struct Stores to branch control. - assertEquals(3,countMemoryNodes(stop,StoreNode.class,new BitSet())); + assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index cbe5c523..ae6ebc9e 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -2,14 +2,10 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; -import com.seaofnodes.simple.type.TypeStruct; -import com.seaofnodes.simple.type.TypeMemPtr; import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; -import static org.junit.Assert.assertNull; -import static org.junit.Assert.assertSame; public class Chapter12Test { @Ignore @@ -106,7 +102,7 @@ n.next = new N; return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new N;", stop.toString()); + assertEquals("return N;", stop.toString()); } @Test @@ -178,7 +174,7 @@ struct S2 { int x; } return new S1.s=new S2; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new S1;", stop.toString()); + assertEquals("return S2;", stop.toString()); } @Test @@ -198,25 +194,4 @@ return p1.pi.i + 1; catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } } - - @Test - public void testShallowRecursiveType() { - new Parser("struct LLI { LLI? next; int i; } return 0;").parse().iterate(); - TypeStruct l1 = (TypeStruct)Parser.TYPES.get("LLI"); - TypeStruct l0 = ((TypeMemPtr)l1._fields[0]._type)._obj; - assertEquals("LLI", l0._name); - assertNull(l0._fields); - assertEquals(2, l1._fields.length); - assertSame(l0, l1.meet(l0)); - assertSame(l0, l0.dual()); - assertSame(l0, l0.glb()); - } - - @Test - public void testUnusedForwardReference() { - StopNode stop = new Parser("struct Holder { Missing? ref; } Holder h = new Holder; return h.ref;") - .parse().iterate(); - assertEquals("return null;", stop.toString()); - assertNull(((TypeStruct)Parser.TYPES.get("Missing"))._fields); - } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 34d71d9b..3373a1aa 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -347,7 +347,9 @@ if (arg) v.f=1; return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); + assertEquals("return 2;", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 0)); + assertEquals(2L, Evaluator.evaluate(stop, 1)); } @Test @@ -356,6 +358,7 @@ return i; """ struct S { int f; } S v = new S; +v.f = arg; S t = new S; int i = 0; if (arg) { @@ -367,7 +370,7 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region37,.f,0);", stop.toString()); + assertEquals("return Phi(Region46,.f,0);", stop.toString()); } @Test @@ -386,7 +389,7 @@ if (v1) { return v0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @@ -396,6 +399,7 @@ return v0; """ struct S { int f; } S v = new S; +v.f = arg; S t = new S; int i = v.f; if (arg+1) arg= 0; @@ -403,7 +407,7 @@ while (arg) v.f = 2; return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); + assertEquals("return arg;", stop.toString()); } @Test @@ -420,7 +424,7 @@ while(1) { return v; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @Test @@ -453,7 +457,7 @@ while (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -473,7 +477,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop17,arg,Phi(Region41,.f,0));", stop.toString()); + assertEquals("return Phi(Loop21,arg,Phi(Region48,.f,0));", stop.toString()); } @Test @@ -491,7 +495,7 @@ if (arg) { return v; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @Test @@ -512,21 +516,4 @@ return v; StopNode stop = parser.parse().iterate(); //assertEquals("return new S;", stop.toString()); } - - @Test - public void testSplit() { - Parser parser = new Parser( - """ -struct S { int f; } -S s = new S; -if( arg==0 ) s.f = 1; -else if (arg == 1) s.f = 1; -return s.f; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,1,Phi(Region38,1,0));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index f79b758d..c42b0154 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -100,15 +100,4 @@ return x+1==x; assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 1)); } - @Test - public void testReferenceFieldConvertsFloat() { - Parser parser = new Parser( -""" -struct N { N next; int i; } -N n = new N; -n.i = 3.14; -return n.i; -"""); - assertEquals("3",com.seaofnodes.simple.evaluator.Evaluator.evaluate(parser.parse().iterate(),0).toString()); - } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 968054bd..cafa2d8f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -127,7 +127,8 @@ return b; """); StopNode stop = parser.parse().iterate(); assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + assertEquals(-128L, Evaluator.evaluate(stop, 127)); } @Test @@ -143,35 +144,6 @@ return c; // assertEquals(52501L, Evaluator.evaluate(stop, 0)); } - @Test - public void testWrapMinus() { - Parser parser = new Parser( -""" -int MAX = 9223372036854775807; //0x7FFFFFFFFFFFFFFF; -int i = (arg&MAX) + -MAX + -1; // Basically (e0) + Long.MIN_VALUE -int j = -i; // Negating Long.MIN_VALUE wraps, cannot constant fold -if (arg) j = 1; -return j; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region29,1,(-((arg&9223372036854775807)+-9223372036854775808)));", stop.toString()); - assertEquals(-9223372036854775808L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - } - - @Test - public void testWrapShr() { - Parser parser = new Parser( -""" -return (arg >>> 1)==0; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return (!(arg>>>1));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - } - @Test public void testOr() { Parser parser = new Parser( @@ -195,101 +167,6 @@ return arg; catch( Exception e ) { assertEquals("Cannot '&' FltBot",e.getMessage()); } } - @Test - public void testLoadBug() { - Parser parser = new Parser( -""" -struct A { int i; } -struct B { int i; } -A a = new A; -A t1 = new A; -B b = new B; -B t2 = new B; -int i; -if (arg) i = a.i; -else i = b.i; -return i; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,.i,.i);", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); - } - - @Test - public void testBug2() { - Parser parser = new Parser( -""" -int z = 0; -while (1) { - int j; - if (arg&3) { - j = arg >> 2; - } else { - j = (arg >> 3)+z; - } - return j+1; -} -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg>>Phi(Region33,2,3))+1);", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(2L, Evaluator.evaluate(stop, 7)); - assertEquals(2L, Evaluator.evaluate(stop, 8)); - } - - @Test - public void testBug3() { - Parser parser = new Parser( -""" -flt f = arg; -bool b; -if (arg&3) b = f == 1.0; -else b = f == 2.0; -if (arg&5) b = arg == 1; -return b; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,(arg==1),((flt)arg==Phi(Region24,1.0,2.0)));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - assertEquals(0L, Evaluator.evaluate(stop, 3)); - } - - @Test - public void testBug4() { - Parser parser = new Parser( -""" -int i; -if (arg&7) i=3; -else i=2; -return (arg == i) == 1; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region19,3,2));", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); - assertEquals(0L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - assertEquals(1L, Evaluator.evaluate(stop, 3)); - } - - @Test - public void testBug5() { - Parser parser = new Parser( -""" -int d = -1; -while (1) { - int i = (arg & 7) + (9223372036854775807 - 7); - if (arg & 1) i = ((arg&3) + (9223372036854775807 - 3)) & d; - return i + -1; -} -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Region44,((arg&3)+9223372036854775804),((arg&7)+9223372036854775800))+-1);", stop.toString()); - assertEquals(0x7FFFFFFFFFFFFFF7L, Evaluator.evaluate(stop, 0)); - assertEquals(0x7FFFFFFFFFFFFFFCL, Evaluator.evaluate(stop, 1)); - } - @Test public void testTypes() { Parser parser = new Parser( diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java new file mode 100644 index 00000000..d0e02eeb --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -0,0 +1,416 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import org.junit.Ignore; + +import java.nio.charset.StandardCharsets; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter15Test { + + @Test public void testPartialAllocationMemory() { + StopNode stop = new Parser(""" + struct Other { int a; int b; int c; } + struct S { int x; flt y; S? next; } + Other other = new Other; + other.c = 7; + S a = new S; + a.x = arg; + a.y = 1.5; + S b = new S; + // S's aliases are global identities, not tuple or input positions. + // Bypass b's zeroing for a, preserving the unrelated Other slice. + return a.x + a.y + b.x + b.y + other.c; + """).parse().iterate(); + assertEquals(8.5, Evaluator.evaluate(stop,0)); + assertEquals(12.5, Evaluator.evaluate(stop,4)); + + stop = new Parser(""" + struct S { int x; flt y; S? next; } + S a = new S; S b = new S; + S p = a; if (arg) p = b; + // The memory result carries distinct int, float and pointer facts. + if (p.next != null) return 99; + return p.x + p.y; + """).parse().iterate(); + assertEquals("return 0.0;",stop.toString()); + assertEquals(0.0,Evaluator.evaluate(stop,1)); + } + + @Test public void testReadAcrossAllocation() { + StopNode stop = new Parser(""" + struct S { int x; } + S a = new S; S b = new S; + a.x = 11; b.x = 22; + S p = a; if (arg) p = b; + int before = p.x; + S c = new S; + a.x = 33; b.x = 44; + // The partial input to c must not hide the read/write ordering. + // p can alias either object, so node inequality cannot bypass New. + return before*100 + p.x + c.x; + """).parse().iterate(); + assertEquals(1133L,Evaluator.evaluate(stop,0)); + assertEquals(2244L,Evaluator.evaluate(stop,1)); + } + + @Test public void testAllocationInLoop() { + StopNode stop = new Parser(""" + struct S { int x; flt y; S? next; } + S old = new S; old.x = 7; + S last = old; + while (arg > 0) { + S fresh = new S; + fresh.x = last.x + 1; + fresh.next = last; + last = fresh; + arg = arg - 1; + } + return old.x*100 + last.x; + """).parse().iterate(); + assertEquals(707L,Evaluator.evaluate(stop,0)); + assertEquals(712L,Evaluator.evaluate(stop,5)); + } + + @Ignore + @Test + public void testJig() { + Parser parser = new Parser(""" +return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testLifetime() { + Parser parser = new Parser(""" +u8[] b = new u8[5]; +if (arg) { + b[0] = b[0] + 1; +} else { + b[1] = b[1] * 2; +} +return b[0] + b[1]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region72,1,0);", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 1)); + } + + @Test + public void testCyclic() { + Parser parser = new Parser( +""" +struct C { + C? l; +} +C c = new C; +c.l = c; +return c; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return C;", stop.toString()); + assertEquals("Obj@1{l=obj@1}", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testSafetyCheck() { + Parser parser = new Parser( +""" +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; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return u8[];", stop.toString()); + assertEquals("\u0001", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testBasic1() { + Parser parser = new Parser( +""" +int[] is = new int[2]; +return is[1]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testBasic2() { + Parser parser = new Parser( +""" +int[] is = new int[2]; +int[] is2 = new int[2]; +return is[1]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testBasic3() { + Parser parser = new Parser( +""" +int[] a = new int[2]; +a[0] = 1; +a[1] = 2; +return a[0]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testBasic4() { + Parser parser = new Parser( +""" +struct A { int i; } +A?[] a = new A?[2]; +return a; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return *A?[];", stop.toString()); + assertEquals("Obj<*A?[]>{#=2,[]=[null,null]}", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testBasic5() { + Parser parser = new Parser( +""" +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; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region122,1.2,Phi(Region119,2.3,.y));", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Ignore + @Test + public void testBasic6() { + Parser parser = new Parser( +""" +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; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region122,Phi(Region118,.y,1.2),1.2);", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testTree() { + Parser parser = new Parser( +""" +// Can we define a forward-reference array? +struct Tree { Tree?[] _kids; } +Tree root = new Tree; +root._kids = new Tree?[2]; +root._kids[0] = new Tree; +return root; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Tree;", stop.toString()); + assertEquals("Obj{_kids=Obj<*Tree?[]>{#=2,[]=[Obj{_kids=null},null]}}", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testNestedStructAddMemProj() { + Parser parser = new Parser( +""" +struct S { + int a; + int[] b; +} +return 0; +"""); + StopNode stop = parser.parse(); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testRollingSum() { + Parser parser = new Parser( +""" +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 +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (.[]+(.[]*1000));", stop.toString()); + assertEquals(1006L, Evaluator.evaluate(stop, 4)); + } + + @Test + public void sieveOEratosthenes() { + Parser parser = new Parser( +""" +int[] ary = new int[arg]; +int[] primes = new int[arg]; +int nprimes = 0; +// Find primes +int j=2; +while( j*j < arg ) { + while( ary[j]==1 ) j = j + 1; + // j is now a prime + primes[nprimes] = j; nprimes = nprimes + 1; + // Mark out the rest non-primes + int i = j + j; + while( i < ary# ) { + ary[i] = 1; + i = i + j; + } + j = j + 1; +} +// Now just collect the remaining primes +while( j < arg ) { + if( ary[j] == 0 ) { + primes[nprimes] = j; nprimes = nprimes + 1; + } + j = j + 1; +} +// Shrink the result array to size +int[] rez = new int[nprimes]; +j = 0; +while( j < nprimes ) { + rez[j] = primes[j]; + j = j + 1; +} + +return rez; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return int[];", stop.toString()); + Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(stop, 20); + assertEquals("int[] {\n # :int;\n [] :int;\n}",obj.struct().toString()); + long nprimes = (Long)obj.fields()[0]; + long[] primes = new long[]{2,3,5,7,11,13,17,19}; + for( int i=0; i 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() { - var sb = new StringBuilder(); - sb.append("Obj<").append(struct._name).append("> {"); - for(int i=0; i= 0 ) return idx; throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name); @@ -82,22 +174,78 @@ public class Evaluator { 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) { - var type = ((TypeMemPtr)alloc.compute())._obj; - return new Obj(type, new Object[type._fields.length]); + TypeStruct type = alloc._ptr._obj; + Object[] body=null; + int num; + if( type.isAry() ) { + long sz = (Long)val(alloc.size()); + long n = offToIdx(sz, type); + if( n < 0 ) + throw new NegativeArraySizeException(""+n); + body = new Object[(int)n+1]; // Array body + var c = type._fields[type._fields.length-1]._type; + if (c instanceof TypeInteger) { + for (int 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.in(2)); - var val = val(store.in(3)); - var idx = getFieldIndex(to.struct, store); - to.fields[idx] = val; + 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; } diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index d16f4300..125f2f5e 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -31,6 +31,8 @@ import java.util.*; */ public class Scheduler { + private final HashMap> readers = new HashMap<>(); + /** * A basic block with a schedule of the containing nodes. * @@ -155,7 +157,10 @@ public class Scheduler { * @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); + 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); } /** @@ -204,7 +209,7 @@ public class Scheduler { * @return true if node is placed during the control flow graph build. */ private static boolean isPinnedNode(NodeData data) { - return data.node.isCFG() || data.node instanceof PhiNode; + return data.node instanceof CFGNode || data.node instanceof PhiNode; } /** @@ -249,13 +254,7 @@ public class Scheduler { // but they did not refine the placement // so do that now. var mem = l.in(1); - for(var out : mem._outputs) { - // Aggregates describe partitions; they do not overwrite - // memory. Only users of this alias constrain the load. - if (out instanceof MemMergeNode || out instanceof ReturnNode) continue; - if (out instanceof StoreNode s && s._alias != l._alias) continue; - if (out instanceof MemPhiNode p && p._alias != l._alias) continue; - if (out instanceof BulkMemPhiNode p && p.isSplit(l._alias)) continue; + for(var out : l.antiDeps()) { if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -273,13 +272,9 @@ public class Scheduler { 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 l && l._alias==s._alias) od(out).ifPresent(this::decUsers); - } - } + var loads = readers.get(data.node); + if (loads != null) + for (var load : loads) decUsers(load); } // Now all nodes should be placed and have a block assigned @@ -365,7 +360,7 @@ public class Scheduler { while (!queue.isEmpty()) { var data = queue.pop(); var node = data.node; - assert node.isCFG(); + assert node instanceof CFGNode; BasicBlock block; switch (node) { case StartNode s: @@ -405,7 +400,9 @@ public class Scheduler { } } if (!(node instanceof ReturnNode)) - for (Node n:node._outputs) if (n!=null && n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + for (Node n : node._outputs) + if(n 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)); } @@ -427,7 +424,7 @@ public class Scheduler { if (nd.users>0) nd.users++; return; } - assert node.isCFG() == cfg; + assert node instanceof CFGNode == cfg; assert isNotXCtrl(node); nd = new NodeData(node); if (cfg) nd.users=0; @@ -443,42 +440,40 @@ public class Scheduler { private void doMarkAlive(Node node) { var cfgQueue = new Stack(); var dataQueue = new Stack(); - var mem = new Stack(); markAlive(cfgQueue, node, true); // Mark all CFG nodes. while (!cfgQueue.isEmpty()) { var data = cfgQueue.pop(); node = data.node; - assert node.isCFG(); + assert node instanceof CFGNode; if (!(node instanceof ReturnNode)) { - for (var out : node._outputs) if (out!=null && out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); + for (var out : node._outputs) if (out!=null && out instanceof CFGNode && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } - for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false); + 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.isCFG(); + assert !(node instanceof CFGNode); if (node instanceof PhiNode phi) { var r = phi.in(0); for (int i=1; id.users++); + for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false); } } + // Writes, including New behind an aggregate, schedule before their + // anti-dependent reads in this reverse scheduling pass. + for (var load : data.values()) + if (load.node instanceof LoadNode l) + for (var use : l.antiDeps()) + if ((use instanceof StoreNode || use instanceof NewNode) && data.containsKey(use)) { + load.users++; + readers.computeIfAbsent(use,k->new ArrayList<>()).add(load); + } } /** @@ -508,8 +503,8 @@ public class Scheduler { for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p; return null; } - assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1; - for(var n:node._outputs) if(n.isCFG()) return n; + assert node._outputs.stream().filter(x -> x instanceof CFGNode).limit(2).count()<=1; + for(var n:node._outputs) if(n instanceof CFGNode) return n; return null; } @@ -553,7 +548,7 @@ public class Scheduler { } if (last instanceof ReturnNode) break; if (last instanceof IfNode if_) { - for(var out:if_._outputs) if (out.isCFG() && blocks.get(out) == null) queue.push(d(out)); + for(var out:if_._outputs) if (out instanceof CFGNode && blocks.get(out) == null) queue.push(d(out)); break; } data = d(last); diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index ec6e7816..7cd854bf 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -25,7 +25,7 @@ public class ScriptGenerator { 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 */ @@ -109,8 +109,8 @@ public class ScriptGenerator { static { new Parser("", TypeInteger.BOT); - for(var e:Parser.TYPES.entrySet()) { - if (e.getValue() instanceof TypeInteger) { + for( var e : Parser.TYPES.entrySet() ) { + if( e.getValue() instanceof TypeInteger ) { INTTYPES.add(new TypeInt(e.getKey())); } } -- cgit v1.2.3