diff options
Diffstat (limited to 'chapter23/src/test')
17 files changed, 663 insertions, 101 deletions
diff --git a/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 1e1a1dc3..bf809d2a 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -32,7 +32,7 @@ public class BrainFuckTest { assertEquals(brain_fuck.length(),A5.ld4s(ptr_arm)); for( int i=0; i<brain_fuck.length(); i++ ) - assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr+4+i)); + assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr_arm+4+i)); } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 15addc7b..70ddd435 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -5,9 +5,6 @@ import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; -import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; import org.junit.Assert; import org.junit.Ignore; import org.junit.Test; @@ -31,6 +28,8 @@ return f(s); } + @org.junit.Rule public final org.junit.rules.ErrorCollector _errors = new org.junit.rules.ErrorCollector(); + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } @@ -52,34 +51,36 @@ return f(s); assertEquals("0", Eval2.eval(code, 2)); } - static void testCPU( String src, String cpu, String os, int spills, String stop ) { + // Collect differences so every target runs; JUnit still fails the test. + private void testTarget(String src, String cpu, String os, int spills, String stop) { + _errors.checkSucceeds(() -> { testCPU(src,cpu,os,spills,stop); return null; }); + } + + static void testCPU(String src, String cpu, String os, int spills, String stop) { CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); - if( stop != null ) - assertEquals(stop, code._stop.toString()); + SpillStats.record(code,"Chapter20",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + 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); + private void testAllCPUs( String src, int spills, String stop ) { + testTarget(src,"x86_64_v2", "SystemV",spills,stop); + testTarget(src,"riscv" , "SystemV",spills,stop); + testTarget(src,"arm" , "SystemV",spills,stop); } @Test public void testAlloc0() { - testCPU("return new u8[arg];","x86_64_v2", "SystemV",3,"return []u8;"); - testCPU("return new u8[arg];","riscv" , "SystemV",5,"return []u8;"); - testCPU("return new u8[arg];","arm" , "SystemV",5,"return []u8;"); + testTarget("return new u8[arg];","x86_64_v2","SystemV",4,"return []u8;"); + testTarget("return new u8[arg];","riscv","SystemV",5,"return []u8;"); + testTarget("return new u8[arg];","arm","SystemV",5,"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);"); + testTarget(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); + testTarget(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); + testTarget(src,"arm" , "SystemV",0,"return (ori,arg);"); } @Test @@ -95,56 +96,109 @@ val sqrt = { int x -> guess = next; } }; -int cast_int = arg+2; -return sqrt(arg) + sqrt(cast_int); +return sqrt(arg) + sqrt(arg+2); """; - testCPU(src,"x86_64_v2", "Win64" ,48,null); - testCPU(src,"riscv" , "SystemV",19,null); - testCPU(src,"arm" , "SystemV",19,null); + testTarget(src,"x86_64_v2", "SystemV",48,null); + testTarget(src,"riscv" , "SystemV",17,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test - public void testNewtonFloat() throws IOException { - String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) - + "flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0);"; - testCPU(src,"x86_64_v2", "SystemV",39,null); - testCPU(src,"riscv" , "SystemV",17,null); - testCPU(src,"arm" , "SystemV",18,null); + 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); +"""; + testTarget(src,"x86_64_v2", "SystemV",23,null); + testTarget(src,"riscv" , "SystemV",18,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test public void testAlloc2() { String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"; - testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); - testCPU(src,"riscv" , "SystemV", 6,"return .[];"); - testCPU(src,"arm" , "SystemV", 6,"return .[];"); + testTarget(src,"x86_64_v2","SystemV",3,"return .[];"); + testTarget(src,"riscv","SystemV",6,"return .[];"); + testTarget(src,"arm","SystemV",6,"return .[];"); } - - @Test - public void testArray1() throws IOException { - String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/array1.smp")); - testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); - testCPU(src,"riscv" , "SystemV", 8,"return (add,.[],(mul,.[],1000));"); - testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); + public void testArray1() { + String src = +""" +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +for( int i=0; i<ary#; i++ ) + ary[i] = i; +// Fill [0,1,3,6,10,...] +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",9,"return .[];"); + testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); + testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } - @Test - public void testString() throws IOException { - String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); - testCPU(src,"x86_64_v2", "SystemV", 9,null); - testCPU(src,"riscv" , "SystemV", 3,null); - testCPU(src,"arm" , "SystemV", 3,null); + public void testString() { + String src = """ +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); +"""; + testTarget(src,"x86_64_v2", "SystemV",9,null); + testTarget(src,"riscv" , "SystemV",4,null); + testTarget(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;"; - testCPU(src,"x86_64_v2", "SystemV",2,null); - testCPU(src,"riscv" , "SystemV",2,null); - testCPU(src,"arm" , "SystemV",2,null); + testTarget(src,"x86_64_v2","SystemV",1,null); + testTarget(src,"riscv","SystemV",2,null); + testTarget(src,"arm","SystemV",2,null); } @Test @@ -162,9 +216,9 @@ 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);"); + testTarget(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); } @Test @@ -177,8 +231,126 @@ while (arg > 0) { } return arg; """; - testCPU(src,"x86_64_v2", "SystemV",3,null); - testCPU(src,"riscv" , "SystemV",2,null); - testCPU(src,"arm" , "SystemV",2,null); + testTarget(src,"x86_64_v2", "SystemV",3,null); + testTarget(src,"riscv" , "SystemV",2,null); + testTarget(src,"arm" , "SystemV",2,null); } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @Test + public void testBrainfuck() { + var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(java.nio.charset.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; +"""; + testTarget(src,"x86_64_v2", "SystemV",40,null); + testTarget(src,"riscv" , "SystemV",28,null); + testTarget(src,"arm" , "SystemV",28,null); + //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); + } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @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; +"""; + testTarget(src,"x86_64_v2", "SystemV",52,null); + testTarget(src,"riscv" , "SystemV",44,null); + testTarget(src,"arm" , "SystemV",44,null); +//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + } + } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java new file mode 100644 index 00000000..2d0493e5 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java @@ -0,0 +1,55 @@ +package com.seaofnodes.simple; + +import java.io.IOException; +import java.nio.file.*; +import org.junit.Test; + +// Revised Chapter 20 examples introduced with native encoding. +public class Chapter21AllocTest { + @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); +"""; + Chapter21Test.testCPU(src,"x86_64_v2", "Win64" ,48,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV",19,null); + Chapter21Test.testCPU(src,"arm" , "SystemV",19,null); + } + + @Test + public void testNewtonFloat() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) + + "flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0);"; + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",39,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV",17,null); + Chapter21Test.testCPU(src,"arm" , "SystemV",18,null); + } + + @Test + public void testArray1() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/array1.smp")); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); + Chapter21Test.testCPU(src,"riscv" , "SystemV", 8,"return (add,.[],(mul,.[],1000));"); + Chapter21Test.testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); + } + + + @Test + public void testString() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash21.smp")); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV", 3,null); + Chapter21Test.testCPU(src,"arm" , "SystemV", 3,null); + } + +} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 9e73a9c0..f84a7237 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -13,6 +13,118 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testArmCallInstructions() { + EvalArm64 cpu = new EvalArm64(new byte[512],256); + for( int delta : new int[]{4,32,-4} ) { + cpu._pc = 128; + for( int i=0; i<32; i++ ) cpu.regs[i]=1000+i; + cpu.st4(128,0x94000000 | ((delta>>2)&0x03FFFFFF)); // BL + assertEquals(0,cpu.step(1)); + assertEquals(128+delta,cpu._pc); + for( int i=0; i<32; i++ ) assertEquals(i==30 ? 132 : 1000+i,cpu.regs[i]); + } + for( int rn : new int[]{9,30} ) + for( boolean call : new boolean[]{false,true} ) { + cpu._pc=4; + cpu.regs[rn]=64; + cpu.st4(4,(call ? 0xD63F0000 : 0xD65F0000) | (rn<<5)); // BLR / RET + assertEquals(0,cpu.step(1)); + assertEquals(64,cpu._pc); + if( call ) assertEquals(8,cpu.regs[30]); + } + } + + @Test public void testArmImmediateArithmetic() { + EvalArm64 cpu = new EvalArm64(new byte[16],16); + // Unsigned imm12, including bit 11 and the optional 12-bit shift. + for( int[] test : new int[][]{{0x91200020,2148},{0xD1200020,-1948}, + {0x91400420,4196},{0xD1400420,-3996}} ) { + cpu._pc=0; cpu.regs[1]=100; + cpu.N=true; cpu.Z=false; cpu.C=true; cpu.V=true; + cpu.st4(0,test[0]); + assertEquals(0,cpu.step(1)); + assertEquals(test[1],cpu.regs[0]); + assertTrue(cpu.N); assertFalse(cpu.Z); assertTrue(cpu.C); assertTrue(cpu.V); + } + } + + @Test public void testArmCallsAndFrames() throws IOException { + String src = """ + val sum = { int n -> + if( n<=0 ) return 1; + return sum(n-1)+n; + }; + val run = { int n -> return sum(n)+sum(n+1); }; + """; + assertTrue("Ordinary calls must survive optimization",checkArmCalls(src,"run",4,27)>0); + } + + @Test public void testArmVectorGrowth() throws IOException { + String src = """ + struct _Vec { + u32 !len; + int[] !buf; + val grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i<len; i++ ) buf2[i]=buf[i]; + buf=buf2; + }; + val add = { int e -> + if( len>=buf# ) grow(buf#*2); + buf[len++]=e; + return self; + }; + }; + val run = { int arg -> + val v = new _Vec{buf=new int[4];}.add(2).add(3).add(5).add(7).add(11); + return v.len*100+v.buf[arg]; + }; + """; + checkArmCalls(src,"run",4,511); + } + + private static int checkArmCalls(String src, String entryName, int arg, int result) throws IOException { + CodeGen code = new CodeGen(src).driver("arm","SystemV",null); + byte[] image = new byte[1<<20]; + System.arraycopy(code._encoding.bits(),0,image,0,code._encoding.bits().length); + EvalArm64 cpu = new EvalArm64(image,1<<16); + boolean entry=false; + int frames=0, calls=0; + for( var bb : code._cfg ) { + if( bb instanceof com.seaofnodes.simple.node.FunNode fun ) { + int off = code._encoding._opStart[fun._nid]; + if( entryName.equals(fun._name) ) { cpu._pc=off; entry=true; } + int frame=fun._frameAdjust; + assertEquals(0,frame&15); + if( frame>0 ) { + frames++; + assertEquals(0xD10003FF | (frame<<10),cpu.ld4s(off)); // SUB SP,SP,#bytes + } + } + if( bb instanceof com.seaofnodes.simple.node.ReturnNode ret ) { + int off=code._encoding._opStart[ret._nid]; + int frame=ret.fun()._frameAdjust; + if( frame>0 ) { + assertEquals(0x910003FF | (frame<<10),cpu.ld4s(off)); // ADD SP,SP,#bytes + off+=4; + } + assertEquals(0xD65F03C0,cpu.ld4s(off)); // RET X30 + } + if( bb instanceof com.seaofnodes.simple.node.cpus.arm.CallARM ) calls++; + } + assertTrue("Must execute the program entry",entry); + assertTrue("Exercise stack frames",frames>0); + for( int i=19; i<=29; i++ ) cpu.regs[i]=1000+i; + cpu.regs[0]=arg; + assertEquals(0,cpu.step(10000)); + assertEquals("Must return to the harness",0,cpu._pc); + assertEquals(result,cpu.regs[0]); + assertEquals(1<<16,cpu.regs[31]); + for( int i=19; i<=29; i++ ) assertEquals(1000+i,cpu.regs[i]); + return calls; + } + + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } @Test public void testNarrowStores() throws IOException { @@ -104,7 +216,8 @@ public class Chapter21Test { } - @Test + // Enabled in Chapter 23; measured there by Chapter23AllocTest. + @Test @Ignore public void testJig() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); testCPU(src,"x86_64_v2", "Win64" ,-1,null); @@ -114,10 +227,8 @@ public class Chapter21Test { static void testCPU( String src, String cpu, String os, int spills, String stop ) { CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.record(code,"Chapter21",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); } @@ -131,7 +242,7 @@ public class Chapter21Test { } @Test public void testInfinite() { - String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + String src = "struct S { int i; }; S !s = new S; while(1) s.i++;"; testCPU(src,"x86_64_v2", "SystemV",0,"return Top;"); testCPU(src,"riscv" , "SystemV",2,"return Top;"); testCPU(src,"arm" , "SystemV",2,"return Top;"); @@ -258,7 +369,7 @@ public class Chapter21Test { @Test public void testPerson() throws IOException { String person = "6\n"; - TestC.run("person", person, 0); + TestC.run("person21", person, 0); // Memory layout starting at PS: int ps = 1<<16; // Person array pointer starts at heap start @@ -269,7 +380,7 @@ public class Chapter21Test { int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; - EvalRisc5 R5 = TestRisc5.build("person", ps, 0, false); + EvalRisc5 R5 = TestRisc5.build("person21", ps, 0, false); R5.regs[riscv.A1] = 1; // Index 1 R5.st8(ps,3); // Length R5.st8(ps+1*8,p0); @@ -285,7 +396,7 @@ public class Chapter21Test { assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); - EvalArm64 A5 = TestArm64.build("person", ps, 0, false); + EvalArm64 A5 = TestArm64.build("person21", ps, 0, false); A5.regs[arm.X1] = 1; // Index 1 A5.st8(ps, 3); A5.st8(ps+1*8,p0); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java index d6f31ff6..a3e9a016 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -13,8 +13,15 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter22Test { + @Test public void testInfiniteReturn() { + String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + testCPU(src,"x86_64_v2","SystemV",0,"return Top;"); + testCPU(src,"riscv","SystemV",2,"return Top;"); + testCPU(src,"arm","SystemV",2,"return Top;"); + } - @Test + // Enabled in Chapter 23; measured there by Chapter23AllocTest. + @Test @Ignore public void testJig() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); //String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); @@ -25,10 +32,8 @@ public class Chapter22Test { static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.record(code,"Chapter22",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); return code; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java new file mode 100644 index 00000000..cd8c43cf --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java @@ -0,0 +1,34 @@ +package com.seaofnodes.simple; + +import java.io.IOException; +import java.nio.file.*; +import org.junit.Test; + +// Revised or newly enabled allocation examples in Chapter 23. +public class Chapter23AllocTest { + @Test + public void testString() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); + Chapter23Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); + Chapter23Test.testCPU(src,"riscv" , "SystemV", 3,null); + Chapter23Test.testCPU(src,"arm" , "SystemV", 3,null); + } + + @Test + public void testJig21() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); + Chapter23Test.testCPU(src,"x86_64_v2", "Win64" ,-1,null); + Chapter23Test.testCPU(src,"riscv" , "SystemV",-1,null); + Chapter23Test.testCPU(src,"arm" , "SystemV",-1,null); + } + + @Test + public void testJig22() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); + //String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); + Chapter23Test.testCPU(src,"x86_64_v2", "Win64" ,-1,null); + Chapter23Test.testCPU(src,"riscv" , "SystemV",-1,null); + Chapter23Test.testCPU(src,"arm" , "SystemV",-1,null); + } + +} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 4bb8ded0..41f0df6e 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -16,6 +16,8 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter23Test { + @Test public void testPopularUses() { com.seaofnodes.simple.codegen.RegAllocTestSupport.popularUses(); } + @Test public void testDiagnosticTypeAccessors() throws Exception { new CodeGen("return 0;").parse(); var tfp = TypeFunPtr.TEST; @@ -62,7 +64,8 @@ public class Chapter23Test { } private static void checkOrRhsLoop(String src) throws IOException { - CodeGen code = new CodeGen(src).driver("riscv", "SystemV", null); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV", null); + SpillStats.record(code,"Chapter23","riscv","SystemV"); for (int arg : new int[]{0, 1, 2, 3}) { byte[] image = new byte[1 << 20]; System.arraycopy(code._encoding.bits(), 0, image, 0, code._encoding._bits.size()); @@ -93,10 +96,8 @@ var apply = { i64 x, { i64 -> u32 } fcn -> static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.record(code,"Chapter23",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); return code; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java index 5a40de8f..54d08e19 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -307,11 +307,11 @@ public class EvalArm64 { break; } - case 0x91: { // add(immediate) + case 0x91, 0xD1: { // ADD/SUB (immediate), unsigned imm12, optional LSL #12 int rn = (ir >> 5) & 0x1F; - int immediate = ir << 10 >> 20; - // only hit it twice - rval = regs[rn] + immediate; + long immediate = (ir >>> 10) & 0xFFF; + if( (ir & (1<<22))!=0 ) immediate <<= 12; + rval = opcode1==0x91 ? regs[rn] + immediate : regs[rn] - immediate; break; } case 0x92: { // and(immediate) @@ -330,6 +330,7 @@ public class EvalArm64 { } case 0x94, 0x95, 0x96, 0x97: { // bl + rdid = -1; // BL writes only X30, not a displacement-selected register. rval = pc + 4; regs[arm.X30] = rval; int imm26 = (ir & 0x03FFFFFF); @@ -573,15 +574,15 @@ public class EvalArm64 { break; } case 0xD6: { - if( (ir & 0xFFFF) != 0 ) throw Utils.TODO(); - if( ((ir>>16) & 0xFF) != 0x5F ) throw Utils.TODO(); // 0x3F is register call + int op = ir & 0xFFFFFC1F; + int rn = (ir >>> 5) & 31; + int target = (int)regs[rn]; // Read before BLR overwrites X30. rdid = -1; - int rn = ir << 22 >> 27; - assert rn == 0; - pc = (int)regs[30]; - // Return to zero breaks simulation - if( pc==0 ) break outer; - pc -= 4; // Undo post-increment + if( op==0xD63F0000 ) regs[arm.X30] = pc+4; // BLR + else if( op!=0xD65F0000 ) { trap = 3; break; } // RET + pc = target; + if( op==0xD65F0000 && pc==0 ) break outer; + pc -= 4; break; } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java index 65eb525c..d1fbd7df 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.cpus.riscv.riscv; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.node.cpus.riscv.riscv; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; @@ -18,7 +18,7 @@ public class MergeSortTest { for( int prime : primes ) sb.p(prime).p(", "); String sprimes = sb.p("]").toString(); - TestC.run("sort", sprimes, 40); + TestC.run("sort", sprimes, 34); EvalRisc5 R5 = TestRisc5.build("src/test/java/com/seaofnodes/simple/progs", "sort", "merge_sort", 0, 36, false); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/SpillStats.java b/chapter23/src/test/java/com/seaofnodes/simple/SpillStats.java new file mode 100644 index 00000000..6af51b33 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -0,0 +1,72 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import java.util.Map; +import java.util.TreeMap; +import org.junit.runner.*; +import org.junit.runner.notification.*; + +// Run existing tests and sum actual allocations, including ones without goldens. +// Helpers call record after allocation; ordinary JUnit runs collect nothing. +public class SpillStats extends RunListener { + private static SpillStats ACTIVE; + private Description _test; + private int _qualityFailures; + private final Map<String,long[]> _totals = new TreeMap<>(); + + @Override public void testStarted(Description test) { _test = test; } + public static void record(CodeGen code, String cohort, String cpu, String abi) { + if( ACTIVE==null ) return; + String test = ACTIVE._test.getTestClass().getSimpleName()+"."+ACTIVE._test.getMethodName(); + for( String key : new String[]{cohort+","+cpu+","+abi,cohort+",ALL,ALL"} ) { + long[] sum = ACTIVE._totals.computeIfAbsent(key,k -> new long[3]); + sum[0]++; sum[1] += code._regAlloc._spills; sum[2] += code._regAlloc._spillScaled; + } + System.out.println("allocation,"+cohort+","+test+","+cpu+","+abi+","+ + code._regAlloc._spills+","+code._regAlloc._spillScaled); + } + + // The same native helpers serve old and new program cohorts. + public static void recordNative(CodeGen code, String cpu, String abi) { + String cohort = ACTIVE!=null && ACTIVE._test.getTestClass()==Chapter23Test.class + ? "Chapter23" : ACTIVE!=null && ACTIVE._test.getTestClass()==Chapter22Test.class + ? "Chapter22" : "Chapter21"; + record(code,cohort,cpu,abi); + } + + // Keep running every CPU and native result check when measuring quality. + // A changed golden still makes spill-stats fail at the end. + public static void checkSpills(int expected, int actual) { + if( expected==-1 ) return; + try { org.junit.Assert.assertEquals("Expect spills:",expected,actual,Math.max(1,expected>>3)); } + catch( AssertionError error ) { + if( ACTIVE==null ) throw error; + ACTIVE._qualityFailures++; + System.err.println(ACTIVE._test+": "+error.getMessage()); + } + } + + public static void main(String[] args) throws ClassNotFoundException { + if( args.length==0 ) args = new String[]{"Chapter20Test","Chapter21Test","Chapter21AllocTest","Chapter22Test","Chapter23Test","Chapter23AllocTest","BrainFuckTest","MergeSortTest"}; + Class<?>[] tests = new Class<?>[args.length]; + for( int i=0; i<args.length; i++ ) + tests[i] = Class.forName("com.seaofnodes.simple."+args[i]); + ACTIVE = new SpillStats(); + JUnitCore junit = new JUnitCore(); + junit.addListener(ACTIVE); + Result result = junit.run(tests); + boolean passed = result.wasSuccessful() && ACTIVE._qualityFailures==0; + if( !result.wasSuccessful() ) System.out.println("FAILED test run: totals are not a complete comparison."); + else if( !passed ) System.out.println("Spill expectations differ; allocation and runtime checks passed."); + System.out.println("cohort,cpu,abi,allocations,splits,scaled"); + for( var row : ACTIVE._totals.entrySet() ) { + long[] sum = row.getValue(); + System.out.println(row.getKey()+","+sum[0]+","+sum[1]+","+sum[2]); + } + for( Failure failure : result.getFailures() ) System.err.println(failure.getTrace()); + System.out.println("Tests: "+result.getRunCount()+", failures: "+result.getFailureCount()); + System.out.println("Spill golden failures: "+ACTIVE._qualityFailures); + ACTIVE = null; + if( !passed ) System.exit(1); + } +} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java index 38fd2a85..edce92f3 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -24,12 +24,11 @@ public class TestArm64 { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null); + SpillStats.recordNative(code,"arm","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded - int delta = spills>>3; - if( delta == 0 ) delta =1; - if( spills != -1 ) assertEquals("Expect spills:", spills, code._regAlloc._spillScaled, delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); // Image byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) diff --git a/chapter23/src/test/java/com/seaofnodes/simple/TestC.java b/chapter23/src/test/java/com/seaofnodes/simple/TestC.java index 6edde562..2e61211a 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestC.java @@ -60,15 +60,13 @@ public abstract class TestC { String exe = OS.startsWith("Windows") ? bin+".exe" : bin; // Compile simple, emit ELF CodeGen code = new CheckedCodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); + SpillStats.recordNative(code,CPU_PORT,simple_conv); String result = gcc(obj, c_conv, cfile, false, exe ); assertEquals(expected,result); // Allocation quality not degraded - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); } public static String gcc( String obj, String c_conv, String cfile, boolean stdin, String... args ) throws IOException { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java index cb1c95e9..adb256eb 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -22,13 +22,11 @@ public abstract class TestRisc5 { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null); + SpillStats.recordNative(code,"riscv","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); // Image byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) diff --git a/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index b2d14a02..ec666653 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -105,6 +105,48 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,new RegAlloc(code))); } + private static class CallOp extends CallNode implements MachNode { + CallOp(Node ctrl, Node def) { super(null,ctrl,null,def,def); } + @Override public RegMask regmap(int i) { return i==2 ? A : i==3 ? B : null; } + @Override public RegMask outregmap() { return null; } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + + public static void popularUses() { + for( int calls=0; calls<=2; calls++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + RegionNode block = new RegionNode(null,code._start,code._start); + Op def = new Op(new RegMask(7L),null,null,false,block); + LRG lrg = alloc.newLRG(def); + lrg._machDef = def; + lrg._mask = new RegMask(0L); + Op ab = new Op(null,new RegMask(3L),null,false,block,def); + Op bc = new Op(null,new RegMask(6L),null,false,block,def); + Op a = new Op(null,A,null,false,block,def,def); + Op b = new Op(null,B,null,false,block,def); + Op dep = new Op(null,null,null,false,block,def); + CallOp call = calls>0 ? new CallOp(block,def) : null; + if( calls==2 ) new CallOp(block,def); + boolean split = alloc.splitEmptyMaskByUse((byte)0,lrg); + assertEquals(calls<2,split); + if( !split ) { assertSame(def,a.in(1)); assertSame(def,b.in(1)); continue; } + // Two shared copies, even with overlapping masks and repeated inputs. + assertTrue(a.in(1) instanceof SplitNode); + assertTrue(b.in(1) instanceof SplitNode); + assertNotSame(a.in(1),b.in(1)); + assertSame(a.in(1),a.in(2)); + assertSame(b.in(1),ab.in(1)); + assertSame(b.in(1),bc.in(1)); + assertSame(def,dep.in(1)); // A scheduling dependency has no register. + assertEquals(3,def.nOuts()); // Two copies and the dependency. + if( call!=null ) { + assertSame(a.in(1),call.in(2)); + assertSame(b.in(1),call.in(3)); + } + } + } + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. public static class CheckedCodeGen extends CodeGen { public CheckedCodeGen(String src) { super(src); } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.c b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.c new file mode 100644 index 00000000..df95e1ca --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.c @@ -0,0 +1,34 @@ +#include <stdio.h> +#include <stdbool.h> +#include <stdlib.h> + +typedef struct Person { + int age; +} Person; + +typedef struct PersonArray { + unsigned int length; + int pad; + Person* data[]; +} PersonArray; + +__attribute__ ((CALL_CONV)) +extern void fcn(PersonArray* people, int index); + +int main() { + Person base[5] = {{25},{1},{18},{45},{60}}; + unsigned char buf[8+8*5]; + PersonArray* people_array = (PersonArray*)buf; + people_array->length=5; + for (int i=0; i<people_array->length; i++) people_array->data[i] = &base[i]; + + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + + printf("%d\n", people_array->data[1]->age); // expected: 6 + + return 0; +}
\ No newline at end of file diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp new file mode 100644 index 00000000..9f0f5bea --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp @@ -0,0 +1,9 @@ +// -*-java-*- +struct Person { + int age; +}; + +val fcn = { Person?[] ps, int x -> + if( ps[x] ) + ps[x].age++; +};
\ No newline at end of file diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp new file mode 100644 index 00000000..dafa7456 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp @@ -0,0 +1,31 @@ +// -*- mode: java; -*- +struct String { + u8[] cs; + int _hashCode; +}; + +// Compare two Strings +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; +}; + +// Return the String hashCode (cached, and never 0) +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; +}; |