diff options
Diffstat (limited to 'chapter20/src/test')
8 files changed, 365 insertions, 13 deletions
diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 14cf6e01..7da1354f 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; +import com.seaofnodes.simple.node.*; +import java.util.BitSet; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -450,4 +452,121 @@ return 0; assertEquals("return 0;", code.print()); } + @Test public void testReadBeforeStores() { + var code = new CodeGen(""" + struct S { int x; int y; }; + 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; + a.y = 55; b.y = 66; + a.x = 33; b.x = 44; + return before*100 + p.x; + """).parse().opto(); + StopNode stop = code._stop; + assertEquals("1133",Eval2.eval(code,0)); + assertEquals("2244",Eval2.eval(code,1)); + } + + static final String NESTED_MEMORY = """ + struct S { int x; int y; int z; }; + S !s = new S; + s.x = 5; s.y = 7; s.z = 11; + while (arg > 0) { + s.x = s.x + 1; + int j = 3; + while (j > 0) { + j = j - 1; + if (j == 1) continue; + s.y = s.y + arg; + if (arg == 2) break; + s.z = s.z + 1; + } + arg = arg - 1; + } + return s; + """; + + @Test public void testMemoryAcrossNestedLoops() { + var code = new CodeGen(NESTED_MEMORY).parse().opto(); + StopNode stop = code._stop; + for (int arg=0; arg<7; arg++) { + assertEquals("S{x="+(5L+arg)+",y="+(7L+arg*(arg+1)-(arg>=2 ? 2 : 0))+ + ",z="+(11L+2*arg-(arg>=2 ? 2 : 0))+"}",Eval2.eval(code,arg)); + } + } + + @Test public void testMemoryAtEarlyReturns() { + var code = new CodeGen(""" + struct S { int x; int y; int z; }; + S !s = new S; + s.x = 3; s.y = 5; s.z = 7; + if (arg) { s.x = 11; s.z = 13; return s; } + s.y = 17; + return s; + """).parse().opto(); + StopNode stop = code._stop; + for (int arg=0; arg<2; arg++) { + assertEquals(arg==0 ? "S{x=3,y=17,z=7}" : "S{x=11,y=5,z=13}",Eval2.eval(code,arg)); + } + } + + @Test public void testKeepLoadsAtMerge() { + var code = new CodeGen(""" + struct S { int x; }; + S !a = new S; S !b = new S; + a.x = arg; b.x = arg+1; + S !p = a; S !q = b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) v=p.x; else v=q.x; + return v; + """).parse().opto(); + StopNode stop = code._stop; + // The one-step safety check stops at the memory aggregate. + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals("-1",Eval2.eval(code,-1)); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("3",Eval2.eval(code,3)); + } + + @Test public void testDropStores() { + var code = new CodeGen(""" + struct S { int x; }; + S !s = new S; + if (arg) s.x=arg+1; else s.x=arg+2; + return s; + """).parse().opto(); + StopNode stop = code._stop; + assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + assertEquals("S{x=2}",Eval2.eval(code,0)); + assertEquals("S{x=4}",Eval2.eval(code,3)); + } + + @Test public void testKeepReadsBeforeWrites() { + var code = new CodeGen(""" + struct S { int x; int y; }; + S !a = new S; S !b = new S; + a.x=arg; b.x=arg+1; + S !p=a; S !q=b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) { v=p.x; p.x=41; p.y=5; } + else { v=q.x; q.x=42; } + return v; + """).parse().opto(); + StopNode stop = code._stop; + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals("-1",Eval2.eval(code,-1)); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("3",Eval2.eval(code,3)); + } + + private static int countMemoryNodes(Node n, Class<?> kind, BitSet seen) { + if (n==null || seen.get(n._nid)) return 0; + seen.set(n._nid); + int cnt=kind.isInstance(n) ? 1 : 0; + for (Node def : n._inputs) cnt+=countMemoryNodes(def,kind,seen); + return cnt; + } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..5d78ae06 --- /dev/null +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter10bTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter10bTest { + @Test public void testIndependentField() { + var code = new CodeGen(""" + struct S { int x; int y; }; + S !s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().opto(); + var stop = code._stop; + assertEquals("return 42;",stop.toString()); + assertEquals("42",Eval2.eval(code,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var code = new CodeGen(""" + struct S { int x; int y; int z; }; + S !a = new S; S !b = new S; + S !p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().opto(); + var stop = code._stop; + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a<m.nIns() && m.in(a)!=null); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode)); + return null; + }); + assertTrue(phis[0]>=3); + assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4)); + } + + @Test public void testLateSliceWorklist() { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var code = new CodeGen(Chapter10Test.NESTED_MEMORY,com.seaofnodes.simple.type.TypeInteger.BOT,seed).parse(); + code.opto(); + assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); + } + } +} diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 5899763f..571a0d54 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -255,4 +255,27 @@ return new Square; assertEquals("Square{side=3.0,diag=1.7320508075688772}", Eval2.eval(code, 3)); assertEquals("Square{side=4.0,diag=2.0}", Eval2.eval(code, 4)); } + static final String CONSTRUCTOR_MEMORY = """ + struct S { int x; int y; }; + struct T { int z=arg+40; }; + T !t = new T; + S !a = new S { x=11; y=7; }; + S !b = new S { x=22; y=9; }; + S !p=a; + if (arg) p=b; + int before=p.x; + S !c = new S { + x=p.x+1; + { int i=0; while (i<2) { p.y=p.y+1; i=i+1; } } + y=p.y; + }; + p.x=33; + return before*10000+c.x*100+c.y+t.z; + """; + + @Test public void testConstructorMemory() { + var code = new CodeGen(CONSTRUCTOR_MEMORY).parse().opto(); + assertEquals("111249",Eval2.eval(code,0)); + assertEquals("222352",Eval2.eval(code,1)); + } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java index ddf4a263..b9ca9cd3 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -446,4 +446,70 @@ return p.coffee_count; assertEquals("1", Eval2.eval(code, 2)); } + static final String CALL_MEMORY = """ + struct S { int x; int y; }; + val bump = { S s, int d -> int old=s.x; s.x=old+d; return old; }; + S !a = new S { x=10; y=7; }; + S !b = new S { x=20; y=9; }; + S !p=a; if (arg) p=b; + int before=p.x; + int old=bump(p,3); + int after=p.x; + bump(a,5); + return before*1000000+old*10000+after*100+a.x+a.y; + """; + + @Test public void testCallMemory() { + var code = new CodeGen(CALL_MEMORY).parse().opto(); + int[] calls={0}; + code._stop.walk(n -> { if(n instanceof CallNode) calls[0]++; return null; }); + assertEquals(2,calls[0]); // Keep real calls so this checks scheduling across them. + assertEquals("10101325",Eval2.eval(code,0)); + assertEquals("20202322",Eval2.eval(code,1)); + code._stop.walk(n -> { + if(n instanceof CallNode call) { + assertEquals(5,call.nIns()); // No scheduling edges may become extra arguments. + assertTrue(call.fptr()._type instanceof TypeFunPtr); + } + return null; + }); + } + + static final String RECURSIVE_MEMORY = """ + struct S { int x; }; + val rec = { S s, int n -> + if (n==0) return s.x; + int before=s.x; + s.x=before+1; + return before+rec(s,n-1); + }; + S !s=new S { x=10; }; + int value=rec(s,arg); + return value*100+s.x; + """; + + @Test public void testRecursiveMemory() { + var code = new CodeGen(RECURSIVE_MEMORY).parse().opto(); + for(int n=0; n<7; n++) + assertEquals(Long.toString((10L*(n+1)+n*(n+1)/2)*100+10+n),Eval2.eval(code,n)); + } + + static final String INLINE_MEMORY = """ + struct S { int x; int y; }; + val make = { S s -> + S t = new S { x=s.x+1; y=3; }; + s.y=9; + return t; + }; + S !a = new S { x=arg+40; y=7; }; + S t=make(a); + return a.x*10000+a.y*100+t.x+t.y; + """; + + @Test public void testInlineAllocationMemory() { + var code = new CodeGen(INLINE_MEMORY).parse().opto(); + assertNull(code._stop.walk(n -> n instanceof CallNode ? n : null)); + assertEquals("400944",Eval2.eval(code,0)); + assertEquals("420946",Eval2.eval(code,2)); + } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 95fbe3f5..a7321c96 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -419,4 +419,71 @@ 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()); } + + @Test public void testSelectedMemory() { + for( String cpu : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY, + Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY} ) { + var code = new CodeGen(src).parse().opto().typeCheck(); + var aliases = memoryPhis(code._stop); + code.instSelect(PORTS,cpu,"SystemV"); + assertEquals(aliases,memoryPhis(code._stop)); + code.GCM().localSched(); + code._stop.walk(n -> { + if( !(n instanceof CFGNode) && !(n instanceof ProjNode) ) + assertTrue(n.in(0) instanceof CFGNode); + if( n instanceof NewNode nn ) { + assertEquals(2,((TypeTuple)nn._type)._types.length); + assertTrue(nn.mem() instanceof MemMergeNode); + assertNull(nn.mem().in(1)); // Partial allocation input. + MachNode mach = (MachNode)nn; + assertNull(mach.regmap(1)); + assertNotNull(mach.regmap(2)); + assertNotNull(mach.outregmap(0)); + assertNull(mach.outregmap(1)); + } + if( n instanceof CallNode call ) { + assertEquals(4,call.nIns()); // ctrl, memory, two args; direct target is embedded. + } + return null; + }); + } + } + + private static java.util.ArrayList<String> memoryPhis(Node stop) { + var phis = new java.util.ArrayList<String>(); + stop.walk(n -> { + if( n instanceof MemPhiNode phi ) phis.add("alias:"+phi._alias); + if( n instanceof BulkMemPhiNode phi ) phis.add("bulk:"+phi._aliases); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode)); + return null; + }); + java.util.Collections.sort(phis); + return phis; + } + + @Test public void testFoldedReadBeforeWrites() { + var code = new CodeGen(""" + struct S { int x; }; + S !a = new S { x=11; }; S !b = new S { x=22; }; + S !p = a; if( arg ) p = b; + int before = p.x + arg; + a.x=33; b.x=44; + return before; + """).parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2","SystemV").GCM().localSched(); + var read = (MemOpNode)code._stop.walk(n -> + n instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.AddMemX86 ? n : null); + assertNotNull(read); + int writes = 0; + for( Node use : read.antiDeps() ) + if( use instanceof MemOpNode st && st.isMem() ) { + assertSame(read.cfg0(),st.cfg0()); + assertTrue(st._inputs.find(read)>=0); + assertTrue(read.cfg0()._outputs.find(read)<st.cfg0()._outputs.find(st)); + assertNull(((MachNode)st).regmap(st._inputs.find(read))); + writes++; + } + assertEquals(1,writes); // The next Store follows this first clobber through memory. + } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 71a4bc36..7cdcd739 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -157,7 +157,7 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; - testTarget(src,"x86_64_v2", "SystemV",5,"return .[];"); + testTarget(src,"x86_64_v2", "SystemV",13,"return .[];"); testTarget(src,"riscv" , "SystemV",1,"return (add,.[],(mul,.[],1000));"); testTarget(src,"arm" , "SystemV",1,"return (add,.[],(muli,.[]));"); } @@ -202,7 +202,7 @@ hashCode(s); """; testTarget(src,"x86_64_v2", "SystemV",21,null); testTarget(src,"riscv" , "SystemV", 3,null); - testTarget(src,"arm" , "SystemV", 5,null); + testTarget(src,"arm" , "SystemV", 3,null); } @Test @@ -245,4 +245,25 @@ return arg; testTarget(src,"riscv" , "SystemV",2,null); testTarget(src,"arm" , "SystemV",2,null); } + + @Test public void testMemoryAllocation() { + for( String cpu : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY, + Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY, + "int[] !a = new int[3]; a[arg]=arg; return a[0]+1;"} ) { + var code = new CodeGen(src).parse().opto().typeCheck() + .instSelect(PORTS,cpu,"SystemV").GCM().localSched().regAlloc(); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + code._stop.walk(n -> { + // Whole memory, precise Phis, and memory projections need no register. + if( n._type instanceof com.seaofnodes.simple.type.TypeMem ) + assertEquals(-1,code._regAlloc.regnum(n)); + if( n instanceof com.seaofnodes.simple.node.NewNode nn ) { + assertTrue(code._regAlloc.regnum(nn.proj(0))>=0); + assertEquals(-1,code._regAlloc.regnum(nn.proj(1))); + } + return null; + }); + } + } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter20/src/test/java/com/seaofnodes/simple/Eval2.java index 3e1954aa..b55607df 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Eval2.java @@ -329,7 +329,7 @@ public abstract class Eval2 { private static Object alloc(NewNode alloc) { TypeStruct type = alloc._ptr._obj; if( type.isAry() ) { - long sz = (Long)val(alloc.in(1)); + long sz = (Long)val(alloc.size()); long x = offToIdx(sz, type); int n = (int)x; if( n!=x || n<0 ) @@ -442,9 +442,9 @@ public abstract class Eval2 { 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 ) + if( tt._types.length>1 && tt._types[0] instanceof TypeMemPtr ) // Assume a NewNode - yield _print( tt._types[1], x, sb, visit ); + yield _print( tt._types[0], x, sb, visit ); throw Utils.TODO(); } case Type tt -> { diff --git a/chapter20/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter20/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index a3b87e90..3f023bb2 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -185,7 +185,7 @@ public class Evaluator { Object[] body=null; int num; if( type.isAry() ) { - long sz = (Long)val(alloc.in(1)); + long sz = (Long)val(alloc.size()); long n = offToIdx(sz, type); if( n < 0 ) throw new NegativeArraySizeException(""+n); @@ -199,21 +199,17 @@ public class Evaluator { assert elem instanceof TypeMemPtr; } // Length value - body[0] = vall(alloc.in(2+2)); + body[0] = n; } else { body = new Object[num = type._fields.length]; for( int i=0; i<num; i++ ) body[i] = switch( alloc._ptr._obj._fields[i]._type ) { case TypeInteger ti -> 0L; - case TypeFloat tf -> 0; + case TypeFloat tf -> 0D; 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; + return new Object[]{new Obj(type,body),null}; } private Object load(LoadNode load) { |