From a65faba96e78f1d366abb9fafbdefc3e1d4927c9 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 23 Sep 2024 14:42:23 -0700 Subject: Redo address math Loads and Stores take a field offset instead of a field name; the name remains for debugging. NewNode takes a size and produces a pre-initialized chunk of memory with updated memory aliases for all fields. Field picks up an alias; TypeStruct loses one. TypeArray is a subclass of TypeStruct for now. TypeMem tracks a conservative value for its alias. TypeStruct computes field layouts. Now ProjNodes can have non-CFG input 0 - NewNode does, but so would a combined ModRem op from a divide, or a CAS producing both a success boolean and the old value. This impacts all the schedulers (IRPrinter, GCM, Scheduler) which previously believe slot 0 only held control nows, or could be modified to a control now. Aliases are now computed in the Parser instead of Start; Parser gets new Field math. --- .../java/com/seaofnodes/simple/Chapter10Test.java | 22 ++++++++-------- .../java/com/seaofnodes/simple/Chapter11Test.java | 16 +++++++----- .../java/com/seaofnodes/simple/Chapter13Test.java | 6 ++--- .../java/com/seaofnodes/simple/Chapter15Test.java | 10 ++++++++ .../java/com/seaofnodes/simple/SchedulerTest.java | 2 +- .../test/java/com/seaofnodes/simple/TypeTest.java | 30 +++++++++++----------- .../com/seaofnodes/simple/evaluator/Evaluator.java | 21 +++++++++------ .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 4 +-- 8 files changed, 65 insertions(+), 46 deletions(-) (limited to 'chapter15/src/test/java') diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 65bd1170..f1b791fb 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -65,9 +65,9 @@ else v.y = 3; return v; """); - StopNode stop = parser.parse(true).iterate(true); + StopNode stop = parser.parse(false).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return new Vector2D;", stop.toString()); + assertEquals("return Vector2D;", stop.toString()); } @Test @@ -105,7 +105,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop13,0,(Phi_a+2));", stop.toString()); } @Test @@ -157,7 +157,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Region31,(*void)Phi(Region19,null,new Bar),null);", stop.toString()); + assertEquals("return Phi(Region33,(*void)Phi(Region20,null,Bar),null);", stop.toString()); } @Test @@ -173,7 +173,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Region37,4,3);", stop.toString()); + assertEquals("return Phi(Region39,4,3);", stop.toString()); } @Test @@ -227,7 +227,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(true); - assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop18,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -249,7 +249,7 @@ return ret; """); StopNode stop = parser.parse(true).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop13,s0,Phi(Region37,s0,Phi_ret));", stop.toString()); } @Test @@ -268,7 +268,7 @@ return ret; """); StopNode stop = parser.parse(true).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop17,s0,Phi(Region38,s0,Phi_ret));", stop.toString()); } @@ -286,7 +286,7 @@ return ret; """); StopNode stop = parser.parse(true).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return Phi(Loop12,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop13,s0,Phi(Region35,s0,Phi_ret));", stop.toString()); } @Test @@ -330,7 +330,7 @@ else return new s0; if(new s0.f0) return 0; """); StopNode stop = parser.parse(true).iterate(true); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } @Test @@ -358,7 +358,7 @@ s0 v1 = v0; return v1; """); StopNode stop = parser.parse().iterate(true); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 3b9cac7d..9f5119f5 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -347,6 +347,8 @@ return i; """); StopNode stop = parser.parse(false).iterate(true); assertEquals("return .f;", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 0)); + assertEquals(2L, Evaluator.evaluate(stop, 1)); } @Test @@ -355,6 +357,7 @@ return i; """ struct S { int f; } S v = new S; +v.f = arg; S t = new S; int i = 0; if (arg) { @@ -366,7 +369,7 @@ if (arg) { return i; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Region34,.f,0);", stop.toString()); + assertEquals("return Phi(Region40,.f,0);", stop.toString()); } @Test @@ -385,7 +388,7 @@ if (v1) { return v0; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @@ -395,6 +398,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; @@ -419,7 +423,7 @@ while(1) { return v; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @Test @@ -452,7 +456,7 @@ while (arg) { return i; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return .f;", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -472,7 +476,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return Phi(Loop15,arg,Phi(Region37,.f,0));", stop.toString()); + assertEquals("return Phi(Loop17,arg,Phi(Region42,.f,0));", stop.toString()); } @Test @@ -490,7 +494,7 @@ if (arg) { return v; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @Test diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java index f9aa3016..97e6808e 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -35,7 +35,7 @@ while( arg ) { return head.next.i; """); try { parser.parse(true).iterate(true); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } } @Test @@ -101,7 +101,7 @@ n.next = new N; return n.next; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return new N;", stop.toString()); + assertEquals("return N;", stop.toString()); } @Test @@ -161,6 +161,6 @@ struct S2 { int x; } return new S1.s=new S2; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return new S1;", stop.toString()); + assertEquals("return S2;", stop.toString()); } } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 550c3165..f884f18d 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -33,4 +33,14 @@ return is[1]; assertEquals(0L, Evaluator.evaluate(stop, 0)); } + @Test + public void testBad0() { + Parser parser = new Parser( +""" +return new flt; +"""); + try { parser.parse(false).iterate(false); fail(); } + catch( Exception e ) { assertEquals("Cannot allocate a FltBot",e.getMessage()); } + } + } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java index e5961815..6f65f834 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -48,7 +48,7 @@ return v0; """); StopNode stop = parser.parse(false).iterate(true); var eval = new Evaluator(stop); - assertObj(eval.evaluate(0, 10), "S", 0L); + assertObj(eval.evaluate(0, 10), "S", new Object[1]); assertObj(eval.evaluate(1, 10), "S", 1L); } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java index 9e8a1418..cb45a0d7 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -13,32 +13,32 @@ public class TypeTest { @Test public void testTypeAdHoc() { TypeStruct s1 = TypeStruct.make("s1", new Field[]{ - Field.make("a", TypeInteger.BOT), - Field.make("b", TypeInteger.BOT) }); + Field.make("a",-1, TypeInteger.BOT), + Field.make("b",-2, TypeInteger.BOT) }); TypeStruct s2 = TypeStruct.make("s2", new Field[]{ - Field.make("a", TypeInteger.BOT), - Field.make("b", TypeInteger.BOT) }); + Field.make("a",-3, TypeInteger.BOT), + Field.make("b",-4, TypeInteger.BOT) }); Assert.assertEquals(s1, s1.glb()); Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); - TypeMem m1 = TypeMem.make(1); - TypeMem m2 = TypeMem.make(2); - TypeMem m3 = TypeMem.make(3); - TypeMem m4 = TypeMem.make(4); + TypeMem m1 = TypeMem.make(1,TypeInteger.ZERO); + TypeMem m2 = TypeMem.make(2,TypeInteger.U16); + TypeMem m3 = TypeMem.make(3,TypeFloat.BOT); + 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(-1,TypeInteger.U16), m1.meet(m2)); Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(m1, m1.glb()); - Assert.assertEquals(TypeMem.make(1), m1.dual()); - Assert.assertEquals(m1.dual(), m1.glb().dual()); + Assert.assertEquals(TypeMem.make(1,TypeInteger.BOT), m1.glb()); + Assert.assertEquals(TypeMem.make(1,TypeInteger.ZERO), m1.dual()); + Assert.assertEquals(m4.dual(), m4.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); @@ -58,12 +58,12 @@ public class TypeTest { Assert.assertEquals(ptr1, ptr1.dual().dual()); Assert.assertEquals(ptr1.glb(), ptr1.dual().glb()); - Assert.assertEquals(TypeMemPtr.BOT, ptr1.meet(ptr2nil)); + Assert.assertEquals(TypeMemPtr.make(TypeStruct.BOT,true), ptr1.meet(ptr2nil)); Assert.assertEquals(ptr1.glb(), ptr1.meet(TypeMemPtr.NULLPTR)); TypeMemPtr TOP = TypeMemPtr.TOP; - TypeMemPtr BOT = TypeMemPtr.BOT; - TypeMemPtr PTR = TypeMemPtr.VOIDPTR; + TypeMemPtr BOT = TypeMemPtr.make(TypeStruct.BOT,true ); + TypeMemPtr PTR = TypeMemPtr.make(TypeStruct.BOT,false); TypeMemPtr NULL = TypeMemPtr.NULLPTR; Type PTR_meet_NULL = NULL.meet(PTR); Assert.assertEquals(BOT, PTR_meet_NULL); diff --git a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 31a14c05..b897af7d 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -26,7 +26,7 @@ public class Evaluator { } } - private static int getFieldIndex(TypeStruct struct, MemOpNode memop) { + private static int getFieldIndex(TypeStruct struct, MemOpNode memop, long off) { int idx = struct.find(memop._name); if( idx >= 0 ) return idx; throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name); @@ -83,20 +83,25 @@ public class Evaluator { } private Object alloc(NewNode alloc) { - var type = ((TypeMemPtr)alloc.compute())._obj; - return new Obj(type, new Object[type._fields.length]); + TypeTuple tt = alloc.compute(); + TypeStruct type = ((TypeMemPtr)tt._types[1])._obj; + Object[] mems = new Object[type._fields.length+2]; + mems[1] = new Obj(type,new Object[type._fields.length]); + return mems; } private Object load(LoadNode load) { - var from = (Obj)val(load.in(2)); - var idx = getFieldIndex(from.struct, load); + var from = (Obj)val(load.ptr()); + var off = val(load.off()); + var idx = getFieldIndex(from.struct, load, (Long)off); 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); + var to = (Obj)val(store.ptr()); + var off = val(store.off()); + var val = val(store.val()); + var idx = getFieldIndex(to.struct, store, (Long)off); to.fields[idx] = val; return null; } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index ec6e7816..324dd42d 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter15/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,7 +109,7 @@ public class ScriptGenerator { static { new Parser("", TypeInteger.BOT); - for(var e:Parser.TYPES.entrySet()) { + for(var e : Parser.TYPES.entrySet() ) { if (e.getValue() instanceof TypeInteger) { INTTYPES.add(new TypeInt(e.getKey())); } -- cgit v1.2.3