package com.seaofnodes.simple; import com.seaofnodes.isa.eval.EvalRisc5; import com.seaofnodes.isa.eval.EvalArm64; import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; import com.seaofnodes.simple.util.SB; import java.io.IOException; import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { @Test public void testFloatToInteger() throws IOException { String src = "val float_to_int={ flt x -> int i=x; return i; };"+ "val float_to_u8={ flt x -> u8 i=x; return i; };"; TestC.runC(src,"floatToInteger","",-1); for( double x : new double[]{0.0,-0.0,6.92,-6.92,255.75,-257.75, 0x1p63,Math.nextDown(0x1p63),-0x1p63,Math.nextDown(-0x1p63), Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NaN} ) { for( String name : new String[]{"float_to_int","float_to_u8"} ) { long expected = name.equals("float_to_u8") ? ((long)x)&255 : (long)x; EvalRisc5 r = TestRisc5.build(src,name,0,-1,false); r.fregs[riscv.FA0-riscv.F_OFFSET]=x; assertEquals(0,r.step(1000)); assertEquals(name+"("+x+")",expected,r.regs[riscv.A0]); EvalArm64 a = TestArm64.build(name,src,0,-1,false); a.fregs[arm.D0-arm.D_OFFSET]=x; assertEquals(0,a.step(1000)); assertEquals(name+"("+x+")",expected,a.regs[arm.X0]); } } } @Test public void testReadBeforeConditionalStore() { var code = new CodeGen(""" struct S { int x; }; !S !a=new S; !S !b=new S; a.x=10; b.x=20; !S !p=a; if(arg&1) p=b; int sum=0; for(int i=0; i<6; i++) { sum+=a.x; if(i==2) p.x=30; else if(i==4) b.x=40; } return sum; """).parse().opto(); // The i==2 read still sees 10: three reads of 10, then three of 30. assertEquals("120",Eval2.eval(code,0)); assertEquals("60",Eval2.eval(code,1)); } @Test public void testArmBitfieldExtracts() { // Independent SXT/UXT instruction words, plus ASR, LSR and LSL aliases. int[] ops = {0x93401c20,0xd3401c20,0x93403c20,0xd3403c20, 0x93407c20,0xd3407c20,0x9344fc20,0xd344fc20,0xd37cec20}; long value = 0xa5a5a5a580008080L; long[] expected = {(byte)value,value&255,(short)value,value&65535, (int)value,value&0xffffffffL,value>>4,value>>>4,value<<4}; for( int i=0; i "+src+" };",1,-1,false); cpu.regs[arm.X0]=1; assertEquals(0,cpu.step(1000)); assertEquals(1.25,cpu.fregs[0],0); } // Independently exercise both SIMD widths and addressing modes. Keep // the GPR value different so accidentally reading that bank is visible. for( boolean wide : new boolean[]{false,true} ) for( boolean indexed : new boolean[]{false,true} ) { EvalArm64 cpu = new EvalArm64(new byte[512],256); cpu.regs[1]=128; cpu.regs[2]=16; cpu.regs[3]=99; cpu.fregs[3]=-13.25; int store = (wide ? 0xFD000000 : 0xBD000000) | ((16/(wide?8:4))<<10) | (1<<5) | 3; if( indexed ) store=(wide ? 0xFC226823 : 0xBC226823); // STR D3/S3,[X1,X2] cpu.st4(0,store); cpu.st4(4,store | (1<<22)); // LDR to the same SIMD register. assertEquals(0,cpu.step(1)); assertEquals(-13.25,wide ? cpu.ld8f(144) : cpu.ld4f(144),0); cpu.fregs[3]=0; assertEquals(0,cpu.step(1)); assertEquals(-13.25,cpu.fregs[3],0); } } @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; new _Vec = { int[] initial -> buf=initial; }; val grow = { int sz -> var buf2 = new int[sz]; for( int i=0; i if( len>=buf# ) grow(buf#*2); buf[len++]=e; return self; }; }; val run = { int arg -> val v = new _Vec(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",true,false); 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); 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); 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 testCopyForward() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyForward(); } @Test public void testArmSubtractRegisters() { EvalArm64 cpu = new EvalArm64(new byte[16],16); cpu.st4(0,0xCB020020); // SUB X0,X1,X2, no shift or flag update. for( long[] pair : new long[][]{{7,3},{3,7},{Long.MIN_VALUE,1},{1L<<40,3}} ) { cpu._pc = 0; cpu.regs[1] = pair[0]; cpu.regs[2] = pair[1]; cpu.N=true; cpu.Z=false; cpu.C=true; cpu.V=true; assertEquals(0,cpu.step(1)); assertEquals(pair[0]-pair[1],cpu.regs[0]); assertTrue(cpu.N); assertFalse(cpu.Z); assertTrue(cpu.C); assertTrue(cpu.V); } } @Test public void testRisc64BitStore() { byte[] mem = new byte[24]; EvalRisc5 cpu = new EvalRisc5(mem,mem.length); check64BitStore(mem,cpu::st8,cpu::ld8); } @Test public void testArm64BitStore() { byte[] mem = new byte[24]; EvalArm64 cpu = new EvalArm64(mem,mem.length); check64BitStore(mem,cpu::st8,cpu::ld8); } // Check bytes independently of ld8, including overwrite and adjacent memory. private static void check64BitStore(byte[] mem, java.util.function.BiConsumer store, java.util.function.IntToLongFunction load) { java.util.Arrays.fill(mem,(byte)0xA5); for( long value : new long[]{0x0123456789ABCDEFL,0xFEDCBA9876543210L, -1L,0L,Long.MIN_VALUE,Long.MAX_VALUE} ) { store.accept(8,value); for( int i=0; i=8 && i<16 ? (int)(value >>> (8*(i-8)))&0xFF : 0xA5; assertEquals("byte "+i,expected,mem[i]&0xFF); } assertEquals(value,load.applyAsLong(8)); } } @Ignore @Test public void testJig() throws IOException { String src = """ struct _s0 { bool v1; i16 v2; int v3; i8 v4; byte v5; }; while(new _s0.v3) while(new _s0.v5<>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); if( stop != null ) assertEquals(stop, code.print()); } @Test public void testBasic1() { String src = "return arg | 2;"; testCPU(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); testCPU(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); testCPU(src,"arm" , "SystemV",0,"return (ori,arg);"); } @Test public void testInfinite() { 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",0,"return Top;"); testCPU(src,"arm" , "SystemV",0,"return Top;"); } @Test public void testArray1() { String src = """ int[] !ary = new int[arg]; // Fill [0,1,2,3,4,...] for( int i=0; i cs=data; }; }; // 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; for( int i=0; i< self.cs#; i++ ) hash = hash*31 + self.cs[i]; if( !hash ) hash = 123456789; return hash; }; """; testCPU(src,"x86_64_v2", "SystemV",21,null); testCPU(src,"riscv" , "SystemV",8,null); testCPU(src,"arm" , "SystemV",8,null); } @Test public void testStringExport() throws IOException { String src = """ struct String { u8[] !cs; int _hashCode; new String = { u8[] data -> cs=data; }; }; // 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; for( int i=0; i< self.cs#; i++ ) hash = hash*31 + self.cs[i]; if( !hash ) hash = 123456789; return hash; }; """; TestC.runC(src, "stringHash", "",21); } @Test public void testLoop2() { String src = """ int i = 0; while(true) { i += 1; if( i==0 ) continue; if( i==1 ) continue; if( i==2 ) break; continue; } return i; """; testCPU(src,"x86_64_v2", "win64" ,0,"return (!=0)(inc,Phi(Loop,0,Phi(Region,(!=0),(!=0),0)));"); testCPU(src,"riscv" , "SystemV",0,"return (!=0)( Phi(Loop,0,Phi(Region,(!=0),(!=0),0)) + #1 );"); testCPU(src,"arm" , "SystemV",0,"return (!=0)(inc,Phi(Loop,0,Phi(Region,(!=0),(!=0),0)));"); } @Test public void testNewtonExport() throws IOException { String result = """ 0 0.000000 (0) 1 1.000000 (0) 2 1.414214 (2.22045e-16) 3 1.732051 (0) 4 2.000000 (0) 5 2.236068 (0) 6 2.449490 (0) 7 2.645751 (0) 8 2.828427 (4.44089e-16) 9 3.000000 (0) """; String src = """ val test_sqrt = { flt x -> flt epsilon = 1e-15; flt guess = x; while( 1 ) { flt next = (x/guess + guess)/2; if( guess-epsilon <= next & next <= guess+epsilon ) return guess; //if( guess==next ) return guess; guess = next; } }; """; TestC.runC(src, "newtonFloat", result, TestC.CALL_CONVENTION.equals("win64") ? 42 : 34); EvalRisc5 R5 = TestRisc5.build( src, "test_sqrt", 0, 10, false); R5.fregs[riscv.FA0 - riscv.F_OFFSET] = 3.0; int trap_r5 = R5.step(1000); assertEquals(0,trap_r5); // Return register A0 holds fib(8)==55 assertEquals(1.732051,R5.fregs[riscv.FA0 - riscv.F_OFFSET], 0.00001); // arm EvalArm64 A5 = TestArm64.build("test_sqrt", src,0, 10, false); A5.fregs[arm.D0 - arm.D_OFFSET] = 3.0; int trap_arm = A5.step(1000); assertEquals(0,trap_arm); assertEquals(1.732051, A5.fregs[arm.D0 - arm.D_OFFSET], 0.00001); } @Test public void testSieve() throws IOException { String src = """ val sieve = { int N -> // The main Sieve array bool[] !ary = new bool[N]; // The primes less than N u32[] !primes = new u32[N>>1]; // Number of primes so far, searching at index p int nprimes = 0, p=2; // Find primes while p^2 < N while( p*p < N ) { // skip marked non-primes while( ary[p] ) p++; // p is now a prime primes[nprimes++] = p; // Mark out the rest non-primes for( int i = p + p; i < ary#; i+= p ) ary[i] = true; p++; } // Now just collect the remaining primes, no more marking for( ; p < N; p++ ) if( !ary[p] ) primes[nprimes++] = p; // Copy/shrink the result array u32[] !rez = new u32[nprimes]; for( int j=0; j < nprimes; j++ ) rez[j] = primes[j]; return rez; }; """; // The primes int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, }; SB sb = new SB().p(primes.length).p("["); for( int prime : primes ) sb.p(prime).p(", "); String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C TestC.runC(src, "sieve", sprimes, 186); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. EvalRisc5 R5 = TestRisc5.build( src, "sieve", 100, 90, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) int ary = (int)R5.regs[riscv.A0]; // Memory layout starting at ary(length,pad, prime1, primt2, prime3, prime4) assertEquals(primes.length, R5.ld4s(ary)); for( int i=0; i int f1=1; int f2=1; while( n-- > 1 ){ int temp = f1+f2; f1=f2; f2=temp; } return f2; }; """; String fib = "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"; TestC.runC(src, "fib", fib, 24); EvalRisc5 R5 = TestRisc5.build( src, "fib", 9, 17, false); int trap = R5.step(100); assertEquals(0,trap); // Return register A0 holds fib(8)==55 assertEquals(55,R5.regs[riscv.A0]); // arm EvalArm64 A5 = TestArm64.build("fib", src, 9, 17, false); int trap_arm = A5.step(100); assertEquals(0,trap_arm); // Return register X0 holds fib(8)==55 assertEquals(55, A5.regs[arm.X0]); } @Test public void testPerson() throws IOException { String src = """ struct Person { i32 age; }; val fcn = { !Person?[] !ps, int x -> if( ps[x] ) ps[x].age++; }; """; String person = "6\n"; TestC.run(src, "person1", null, TestC.CALL_CONVENTION, "", TestC.C_DRIVERS_DIR+"person.c", person, 2); // Memory layout starting at PS: int ps = 1<<16; // Person array pointer starts at heap start // Person[3] = { len,pad,P0,P1,P2 }; // sizeof = 4*8 // P0 = { age } // sizeof=8 int p0 = ps+4*8+0*8; // P1 = { age } // sizeof=8 int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; EvalRisc5 R5 = TestRisc5.build( src, "fcn", ps, 2, false); R5.regs[riscv.A1] = 1; // Index 1 R5.st8(ps,3); // Length R5.st8(ps+1*8,p0); R5.st8(ps+2*8,p1); R5.st8(ps+3*8,p2); R5.st8(p0, 5); // age= 5 R5.st8(p1,17); // age=17 R5.st8(p2,60); // age=60 int trap = R5.step(100); assertEquals(0,trap); assertEquals( 5+0,R5.ld8(p0)); assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); EvalArm64 A5 = TestArm64.build("fcn", src, ps, 2, false); A5.regs[arm.X1] = 1; // Index 1 A5.st8(ps, 3); A5.st8(ps+1*8,p0); A5.st8(ps+2*8,p1); A5.st8(ps+3*8,p2); A5.st8(p0, 5); // age= 5 A5.st8(p1,17); // age=17 A5.st8(p2,60); // age=60 int trap_arm = A5.step(100); assertEquals(0,trap_arm); assertEquals( 5+0, A5.ld8(p0)); assertEquals(17+1, A5.ld8(p1)); assertEquals(60+0, A5.ld8(p2)); } @Test public void testArgCount() throws IOException { // Test passes more args than registers in Sys5, which is far, far more // than what win64 allows - so win64 gets a lot more spills here. String src = """ val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, int x8, flt f9, int i10, flt f11, int i12, flt f13, int i14, flt f15, int x16, flt f17 int x18, flt f19 -> return i0 + f1+ i2+ f3+ i4+ f5+ i6+ f7+ x8 +f9 + i10+f11+i12+f13+i14+f15+x16+f17+x18+f19 ; }; """; String arg_count = "191.000000\n"; TestC.runC(src, "arg_count", arg_count, TestC.CALL_CONVENTION.equals("win64") ? 35 : 9); EvalRisc5 R5 = TestRisc5.build( src, "addAll", 0, 4, false); // Todo: handle stack(imaginary stack in emulator) // pass in float arguments R5.fregs[riscv.FA0 - riscv.F_OFFSET] = 1.1; R5.fregs[riscv.FA1 - riscv.F_OFFSET] = 1.1; R5.fregs[riscv.FA2 - riscv.F_OFFSET] = 1.1; R5.fregs[riscv.FA3 - riscv.F_OFFSET] = 1.1; R5.fregs[riscv.FA4 - riscv.F_OFFSET] = 1.1; R5.fregs[riscv.FA5 - riscv.F_OFFSET] = 1.1; R5.fregs[riscv.FA6 - riscv.F_OFFSET] = 1.1; R5.fregs[riscv.FA7 - riscv.F_OFFSET] = 1.1; R5.regs[riscv.A0] = 2; R5.regs[riscv.A1] = 2; R5.regs[riscv.A2] = 2; R5.regs[riscv.A3] = 2; R5.regs[riscv.A4] = 2; R5.regs[riscv.A5] = 2; R5.regs[riscv.A6] = 2; int trap = R5.step(100); assertEquals(0,trap); double result = R5.fregs[riscv.FA0 - riscv.F_OFFSET]; assertEquals(22.8, result, 0.00001); // arm EvalArm64 A5 = TestArm64.build("addAll", src, 0, 4, false); A5.fregs[arm.D0 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D1 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D2 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D3 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D4 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D5 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D6 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D7 - arm.D_OFFSET] = 1.1; A5.regs[arm.X1] = 2; A5.regs[arm.X2] = 2; A5.regs[arm.X3] = 2; A5.regs[arm.X4] = 2; A5.regs[arm.X5] = 2; A5.regs[arm.X6] = 2; A5.regs[arm.X7] = 2; int trap_arm = A5.step(100); assertEquals(0,trap_arm); double result1 = A5.fregs[arm.D0 - arm.D_OFFSET]; assertEquals(22.8, result1, 0.00001); } }