diff options
| author | Cliff Click <cliffc@acm.org> | 2025-04-24 14:38:36 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-08 16:52:27 -0700 |
| commit | 53308013c3f2bad224208805df0f54416067b8be (patch) | |
| tree | efd01b4f23d18bc40c9d4001fb399ce3567b180b /src/test | |
| parent | 43316b84a9cc0b7ac03a4d85fa4f4dff0f26ccd5 (diff) | |
| download | Simple-53308013c3f2bad224208805df0f54416067b8be.tar.gz Simple-53308013c3f2bad224208805df0f54416067b8be.zip | |
Chapter 21: Instruction Encoding and ELF
Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com>
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: tejasae-afk <tejasae-afk@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Tejas Attarde <201814263+tejasae-afk@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Diffstat (limited to 'src/test')
52 files changed, 2232 insertions, 447 deletions
diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index c23bb301..aa6fada0 100644 --- a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -1,71 +1,42 @@ package com.seaofnodes.simple; +import com.seaofnodes.isa.eval.EvalRisc5; + +import com.seaofnodes.isa.eval.EvalArm64; + import com.seaofnodes.simple.codegen.CodeGen; -import java.nio.charset.StandardCharsets; +import com.seaofnodes.simple.node.cpus.arm.arm; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; -import static com.seaofnodes.simple.Main.PORTS; 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(";"); - } + @Test public void testBrainFuck() throws IOException { + String brain_fuck = "Hello World!\n"; + TestC.run("brain_fuck", brain_fuck, 40); - String src = encoded + """ + EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 146, false); + int trap = R5.step(100000); + assertEquals(0,trap); + int ptr = (int)R5.regs[riscv.A0]; + assertEquals(brain_fuck.length(),R5.ld4s(ptr)); + for( int i=0; i<brain_fuck.length(); i++ ) + assertEquals(brain_fuck.charAt(i), R5.ld1z(ptr+4+i)); -int d = 0; -u8[] !output = new u8[0]; -u8[] !data = new u8[100]; + EvalArm64 A5 = TestArm64.build("brain_fuck", 0, 34, false); + int trap_arm = A5.step(100000); + assertEquals(0,trap_arm); + assertEquals(0,trap); + int ptr_arm = (int)A5.regs[arm.X0]; + assertEquals(brain_fuck.length(),A5.ld4s(ptr_arm)); -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; -"""; - Chapter20Test.testCPU(src,"x86_64_v2", "SystemV",28,null); - Chapter20Test.testCPU(src,"riscv" , "SystemV",18,null); - Chapter20Test.testCPU(src,"arm" , "SystemV",12,null); - //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); + for( int i=0; i<brain_fuck.length(); i++ ) + assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr_arm+4+i)); } + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 70cc6121..6ff4ac95 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -100,7 +100,7 @@ else return a; """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Region,2,3),Phi(Region,4,5));", code.print()); + assertEquals("return Phi(Region,3,5,2,4);", code.print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 24d12921..b6bc2bf3 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -145,7 +145,7 @@ else return a; """); code.parse().opto(); - assertEquals("return Phi(Region,3,Phi(Region,4,5));", code.print()); + assertEquals("return Phi(Region,3,5,4);", code.print()); } @Test @@ -258,7 +258,7 @@ if( arg ) { return a+b+c; """); code.parse().opto(); - assertEquals("return (Phi(Region,Phi(Region,2,3),0)+Phi(Region,3,1));", code.print()); + assertEquals("return Phi(Region,6,1,5);", code.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 7e90d484..09669cc7 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -23,7 +23,7 @@ while(arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add),Add);", code.print()); + assertEquals("return Phi(Region,(Phi(Loop,arg,Add)+1),Add,Phi_arg);", code.print()); assertTrue(code.ctrl() instanceof RegionNode); Assert.assertEquals( "5", Eval2.eval(code, 1)); Assert.assertEquals("10", Eval2.eval(code, 6)); @@ -46,7 +46,7 @@ while(arg < 10) { return a; """); code.parse().opto(); - assertEquals("return Phi(Loop,1,Phi(Region,Phi_a,(Phi_a+1)));", code.print()); + assertEquals("return Phi(Loop,1,Phi(Region,Phi_a,(Phi_a+1),Phi_a));", code.print()); assertTrue(code.ctrl() instanceof CProjNode); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 4abc9117..0b4ad8ec 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -35,7 +35,7 @@ while( arg ) { return head.next.i; """); try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 975946da..66e12e42 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -291,7 +291,7 @@ else { } """); code.parse().opto().typeCheck().GCM(); - assertEquals("return Phi(Region,9,Top,Top,Top,Top);", code.print()); + assertEquals("return 9;", code.print()); } @@ -323,7 +323,7 @@ while( prime <= arg ) { return primeCount; """); code.parse().opto(); - assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi(Region,(Phi_primeCount+1),Phi_primeCount))));", code.print()); + assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi_primeCount,(Phi_primeCount+1))));", code.print()); assertEquals("0", Eval2.eval(code, 1)); // No primes 1 or below assertEquals("1", Eval2.eval(code, 2)); // 2 assertEquals("2", Eval2.eval(code, 3)); // 2, 3 diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 6a22ff97..cb92277f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -1,6 +1,9 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -129,7 +132,7 @@ else { return rez; """); code.parse().opto(); - assertEquals("return Phi(Region,1.2,Phi(Region,2.3,.y));", code.print()); + assertEquals("return Phi(Region,1.2,.y,2.3);", code.print()); assertEquals("3.14", Eval2.eval(code, 0)); assertEquals("1.2", Eval2.eval(code, 1)); } @@ -154,7 +157,7 @@ if( iss[arg] ) rez = iss[arg][2].y; return rez;"""); code.parse().opto().typeCheck(); - assertEquals("return Phi(Region,Phi(Region,.y,1.2),1.2);", code.print()); + assertEquals("return Phi(Region,1.2,1.2,.y);", code.print()); assertEquals("3.14", Eval2.eval(code, 0)); try { Eval2.eval(code, 10); fail(); } // Fails AIOOBE in Eval2, no range checks catch( Exception e ) { assertEquals("Index 10 out of bounds for length 2",e.getMessage()); } @@ -212,44 +215,12 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 } @Test - public void sieveOEratosthenes() { - CodeGen code = new CodeGen( -""" -int[] !ary = new int[arg], !primes = new int[arg]; -int nprimes = 0, p=2; -// Find primes while p^2 < arg -while( p*p < arg ) { - // skip marked non-primes - while( ary[p]==1 ) p = p + 1; - // p is now a prime - primes[nprimes] = p; nprimes = nprimes + 1; - // Mark out the rest non-primes - int i = p + p; - while( i < ary# ) { - ary[i] = 1; - i = i + p; - } - p = p + 1; -} -// Now just collect the remaining primes, no more marking -while( p < arg ) { - if( ary[p] == 0 ) { - primes[nprimes] = p; nprimes = nprimes + 1; - } - p = p + 1; -} -// Copy/shrink the result array -int[] !rez = new int[nprimes]; -int j = 0; -while( j < nprimes ) { - rez[j] = primes[j]; - j = j + 1; -} -return rez; -"""); + public void sieveOEratosthenes() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/sieve.smp")); + CodeGen code = new CodeGen(src+"return sieve(arg);"); code.parse().opto(); - assertEquals("return [int];", code.print()); - assertEquals("int[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20)); + assertEquals("return [u32];", code.print()); + assertEquals("u32[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20)); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index da619ed3..e8f6e0bd 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -370,7 +370,7 @@ var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Region,.x,.x),0);", code.print()); + assertEquals("return Phi(Region,.x,0,.x);", code.print()); assertEquals("0", Eval2.eval(code, 0)); assertEquals("1", Eval2.eval(code, 1)); assertEquals("2", Eval2.eval(code, 2)); diff --git a/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/src/test/java/com/seaofnodes/simple/Chapter18Test.java index dafd2f3a..7c0af028 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -3,6 +3,7 @@ import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Ignore; import org.junit.Test; @@ -18,8 +19,7 @@ public class Chapter18Test { "int x=0; while(arg) { if(arg==2) while(1) { x++; } x++; arg--; } return x;" }; for( String src : sources ) { - CodeGen code = new CodeGen(src).parse().opto().typeCheck(); - code._start.buildLoopTree(code._stop); + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.LoopTree); int[] nevers = {0}; code._stop.walk(n -> { if( n instanceof FunNode fun ) @@ -51,26 +51,18 @@ public class Chapter18Test { "val g = { int x -> x ? g(x-1)/305420988+x*305420988 : 1; }; "+ "return f(arg)+g(arg);"; CodeGen code = new CodeGen(src); - code.parse().opto().typeCheck(); - Node con = code._stop.walk(n -> n instanceof ConstantNode && - n._type==TypeInteger.constant(305420988) ? n : null); - assertNotNull(con); - Node[] uses = con._outputs.asAry(); - // Preserve a stacked Cast/Constant chain through scheduling. - Node cast = new CastNode(TypeInteger.BOT,code._start,con); - cast = new CastNode(TypeInteger.BOT,code._start,cast); - for( Node use : uses ) - for( int i=1; i<use.nIns(); i++ ) - if( use.in(i)==con ) use.setDef(i,cast); - code.GCM(); + code.driver(CodeGen.Phase.Schedule,"riscv","SystemV"); var owners = new java.util.IdentityHashMap<CFGNode,Boolean>(); code._stop.walk(n -> { - if( !(n instanceof CastNode) || !(n.in(1) instanceof CastNode) ) return null; + if( !(n instanceof com.seaofnodes.simple.node.cpus.riscv.AddIRISC add) || + !(add.in(1) instanceof com.seaofnodes.simple.node.cpus.riscv.LUI upper) || + ((TypeInteger)upper._con).value()+((add._imm12<<20)>>20)!=305420988 ) + return null; CFGNode fun = n.cfg0(); while( fun!=null && !(fun instanceof FunNode) ) fun = fun.idom(); assertTrue("Constant must belong to a function",fun instanceof FunNode); assertNull("Share one constant chain within each function",owners.put(fun,true)); - // Follow all parts of the constant chain, including shared inputs. + // Follow all parts of a machine constant, including shared inputs. var todo = new java.util.ArrayList<Node>(); var seen = new java.util.IdentityHashMap<Node,Boolean>(); todo.add(n); @@ -130,7 +122,7 @@ public class Chapter18Test { """ return 0; """); - code.parse().opto().typeCheck().GCM().localSched(); + code.driver(Phase.LocalSched); assertEquals("return 0;", code._stop.toString()); assertEquals("0", Eval2.eval(code, 2)); } @@ -177,11 +169,10 @@ return x2; {int -> int}? sq = { int x -> x*x; }; -return sq; """); code.parse().opto(); - assertEquals("Stop[ return { sq}; return (Parm_x(sq,int)*x); ]", code._stop.toString()); - assertEquals("{ int -> int #1}", Eval2.eval(code, 3)); + assertEquals("return (Parm_x(sq,int)*x);", code._stop.toString()); + //assertEquals("{ int -> int #1}", Eval2.eval(code, 3)); } @Test @@ -193,7 +184,7 @@ var sq = { int x -> }; return sq(arg)+sq(3); """); - code.parse().opto().typeCheck().GCM().localSched(); + code.driver(Phase.LocalSched); assertEquals("Stop[ return (#2+#2); return (Parm_x(sq,int)*x); ]", code._stop.toString()); assertEquals("13", Eval2.eval(code, 2)); } @@ -291,7 +282,7 @@ for(;;) { i2i = id(x); } """); - code.parse().opto().typeCheck().GCM().localSched(); + code.driver(Phase.LocalSched); assertEquals("Stop[ return #2; return Parm_i(x,int); ]", code._stop.toString()); assertEquals("3", Eval2.eval(code, 0)); } @@ -307,9 +298,9 @@ for(;;) { arg = x(3); } """); - code.parse().opto().typeCheck().GCM().localSched(); + code.driver(Phase.LocalSched); assertEquals("return Top;", code._stop.toString()); - assertEquals(null, Eval2.eval(code, 0)); + assertNull(Eval2.eval(code,0)); // Infinite loop: i2i remains null. } @@ -332,7 +323,7 @@ ps[0] = new Person; ps[1] = new Person; fcn(ps,1); """); - code.parse().opto().typeCheck().GCM().localSched(); + code.driver(Phase.LocalSched); assertEquals("return 0;", code._stop.toString()); assertEquals("0", Eval2.eval(code, 0)); } @@ -462,7 +453,7 @@ if (arg) i2i = null; if (i2i) return i2i(arg); return f2f(o)(1); """); - code.parse().opto().typeCheck().GCM().localSched(); + code.driver(Phase.LocalSched); assertEquals("Stop[ return Phi(Region,#2,1); return Parm_i(o,int); ]", code._stop.toString()); assertEquals("1", Eval2.eval(code, 2)); } @@ -478,7 +469,7 @@ struct Person { p.coffee_count += 1; return p.coffee_count; """); - code.parse().opto().typeCheck().GCM().localSched(); + code.driver(Phase.LocalSched); assertEquals("return 1;", code._stop.toString()); assertEquals("1", Eval2.eval(code, 2)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 9bd75207..c53a8e11 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -3,12 +3,14 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; import org.junit.Ignore; import org.junit.Test; -import static com.seaofnodes.simple.Main.PORTS; import static org.junit.Assert.*; -import static org.junit.Assert.fail; public class Chapter19Test { @Test public void testPrintingFunctionLookup() { @@ -44,143 +46,108 @@ return 0; @Test - public void testString() { - CodeGen code = new CodeGen( -""" -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)+hashCode(s);"""); - code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("Stop[ return (#2+#2); return Phi(Region,1,0,0,1); return Phi(Region,._hashCode,Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code._stop.toString()); - assertEquals("-4898613127354160978", Eval2.eval(code, 2)); + public void testString() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); + CodeGen code = new CodeGen(src).parse().opto().typeCheck().GCM().localSched(); + assertEquals("Stop[ return Phi(Region,._hashCode,Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); return Phi(Region,1,0,0,1); ]", code._stop.toString()); + //assertEquals("-4898613127354160978", Eval2.eval(code, 2)); } @Test public void testBasic0() { - CodeGen code = new CodeGen("return 0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return 0;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return 0;", code._stop.toString()); } @Test public void testBasic1() { - CodeGen code = new CodeGen("return arg+1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg+1;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (inc,arg);", code._stop.toString()); } @Test public void testBasic2() { - CodeGen code = new CodeGen("return -17;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return -17;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return -17;", code._stop.toString()); } @Test public void testBasic3() { - CodeGen code = new CodeGen("return arg==1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg==1;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (set==,(cmp,arg));", code._stop.toString()); } @Test public void testBasic4() { - CodeGen code = new CodeGen("return arg<<1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg<<1;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (shli,arg);", code._stop.toString()); } @Test public void testBasic5() { - CodeGen code = new CodeGen("return arg >> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg >> 1;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (sari,arg);", code._stop.toString()); } @Test public void testBasic6() { - CodeGen code = new CodeGen("return arg >>> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg >>> 1;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (shri,arg);", code._stop.toString()); } @Test public void testBasic7() { - CodeGen code = new CodeGen("return arg / 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg / 2;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (div,arg,2);", code._stop.toString()); } @Test public void testBasic8() { - CodeGen code = new CodeGen("return arg * 6;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg * 6;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (muli,arg);", code._stop.toString()); } @Test public void testBasic9() { - CodeGen code = new CodeGen("return arg & 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg & 2;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (andi,arg);", code._stop.toString()); } @Test public void testBasic10() { - CodeGen code = new CodeGen("return arg | 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg | 2;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (ori,arg);", code._stop.toString()); } @Test public void testBasic11() { - CodeGen code = new CodeGen("return arg ^ 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg ^ 2;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (xori,arg);", code._stop.toString()); } @Test public void testBasic12() { - CodeGen code = new CodeGen("return arg + 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (addf,(i2f8,arg),2.0f);", code._stop.toString()); + CodeGen code = new CodeGen("return arg + 2.0;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); + assertEquals("return (addf,(cvtf,arg),2.0f);", code._stop.toString()); } @Test public void testBasic13() { - CodeGen code = new CodeGen("return arg - 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (subf,(i2f8,arg),2.0f);", code._stop.toString()); + CodeGen code = new CodeGen("return arg - 2.0;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); + assertEquals("return (subf,(cvtf,arg),2.0f);", code._stop.toString()); } @Test public void testBasic14() { - CodeGen code = new CodeGen("return arg * 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (mulf,(i2f8,arg),2.0f);", code._stop.toString()); + CodeGen code = new CodeGen("return arg * 2.0;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); + assertEquals("return (mulf,(cvtf,arg),2.0f);", code._stop.toString()); } @Test public void testBasic15() { - CodeGen code = new CodeGen("return arg / 2.0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (mulf,(i2f8,arg),0.5f);", code._stop.toString()); + CodeGen code = new CodeGen("return arg / 2.0;").driver(Phase.LocalSched,"x86_64_v2", "SystemV"); + assertEquals("return (mulf,(cvtf,arg),0.5f);", code._stop.toString()); } @Test @@ -189,7 +156,7 @@ hashCode(s)+hashCode(s);"""); """ int arg1 = arg + 1; return arg1 / arg;"""); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (div,(inc,arg),arg);", code._stop.toString()); } @@ -200,18 +167,18 @@ return arg1 / arg;"""); int arg1 = arg + 1; return arg1 * arg; """); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (mul,(inc,arg),arg);", code._stop.toString()); } @Test public void testToFloat() { CodeGen code = new CodeGen(""" - int a = arg; - return a + 2.0; - """ - ).parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (addf,(i2f8,arg),2.0f);", code._stop.toString()); +int a = arg; +return a + 2.0; +""" + ).driver(Phase.LocalSched,"x86_64_v2", "SystemV"); + assertEquals("return (addf,(cvtf,arg),2.0f);", code._stop.toString()); } @Test @@ -225,7 +192,7 @@ else { a = arg-3; } return a;"""); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return Phi(Region,(addi,arg),(addi,arg));", code.print()); } @@ -240,7 +207,7 @@ if( arg==1 ) else a=b+1; return a+b;"""); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (add,(add,Phi(Region,(shli,arg),arg),arg),Phi(Region,4,5));", code.print()); } @@ -252,7 +219,7 @@ int sum=0; for( int i=0; i<arg; i++ ) sum += i; return sum;"""); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return Phi(Loop,0,(add,Phi_sum,Phi(Loop,0,(inc,Phi_i))));", code.print()); } @@ -262,42 +229,42 @@ return sum;"""); """ struct S { int a; !S? !c; }; return new S;"""); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return S;", code.print()); } @Test public void testLea1() { CodeGen code = new CodeGen("int x = arg/3; return arg+x+7;"); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (lea,arg,(div,arg,3));", code.print()); } @Test public void testLea2() { CodeGen code = new CodeGen("int x = arg/3; return arg+x*4+7;"); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (lea,arg,(div,arg,3));", code.print()); } @Test public void testLea3() { CodeGen code = new CodeGen("int x = arg/3; return x*4+arg;"); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return (lea,arg,(div,arg,3));", code.print()); } @Test public void testAlloc2() { CodeGen code = new CodeGen("int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return .[];", code.print()); } @Test public void testAlloc3() { CodeGen code = new CodeGen("int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1]+3;"); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return .[];", code.print()); } @@ -314,7 +281,7 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return .[];", code.print()); } @@ -329,7 +296,7 @@ for( int i=0; i<A#; i++ ) for( int i=0; i<A#; i++ ) B[i] += A[i]; """); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return 0;", code.print()); } @@ -342,60 +309,25 @@ for( int i=0; i<A#; i++ ) A[i]++; return A[1]; """); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return .[];", code.print()); } @Test - public void testNewton() { - CodeGen code = new CodeGen( -""" -// 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); -"""); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return Phi(Loop,(i2f8,arg),(mulf,(addf,(divf,i2f8,Phi_guess),Phi_guess),0.5f));", code.print()); + public void testNewton() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) + + "flt farg = arg; return test_sqrt(farg);"; + CodeGen code = new CodeGen(src).driver(Phase.LocalSched,"x86_64_v2", "SystemV"); + assertEquals("return Phi(Loop,(cvtf,arg),(mulf,(addf,(divf,cvtf,Phi_guess),Phi_guess),0.5f));", code.print()); }; @Test - public void sieveOfEratosthenes() { - CodeGen code = new CodeGen( -""" -var ary = new bool[arg], primes = new int[arg]; -var nprimes=0, p=0; -// Find primes while p^2 < arg -for( p=2; p*p < arg; p++ ) { - // 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; -} -// Now just collect the remaining primes, no more marking -for( ; p < arg; p++ ) - if( !ary[p] ) - primes[nprimes++] = p; -// Copy/shrink the result array -var !rez = new int[nprimes]; -for( int j=0; j<nprimes; j++ ) - rez[j] = primes[j]; -return rez; -"""); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return [int];", code.print()); - //assertEquals("int[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20)); + public void sieveOfEratosthenes() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/sieve.smp")); + CodeGen code = new CodeGen(src).driver(Phase.LocalSched,"x86_64_v2", "SystemV"); + assertEquals("return [u32];", code.print()); + //assertEquals("u32[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20)); } @@ -406,7 +338,7 @@ return rez; val fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(2)*10 + fcn(3); """); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun1,int),x); return (shli,Parm_x($fun2,int)); ]", code.print()); } @@ -417,7 +349,7 @@ return fcn(2)*10 + fcn(3); val sq = { int x -> x*x; }; return sq(arg) + sq(3); """); - code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("Stop[ return (add,#2,#2); return (mul,Parm_x(sq,int),x); ]", code.print()); } @@ -427,7 +359,7 @@ return sq(arg) + sq(3); Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY} ) { var code = new CodeGen(src).parse().opto().typeCheck(); var aliases = memoryPhis(code._stop); - code.instSelect(PORTS,cpu,"SystemV"); + code.loopTree().instSelect(cpu,"SystemV"); assertEquals(aliases,memoryPhis(code._stop)); code.GCM().localSched(); code._stop.walk(n -> { @@ -437,6 +369,7 @@ return sq(arg) + sq(3); assertEquals(2,((TypeTuple)nn._type)._types.length); assertTrue(nn.mem() instanceof MemMergeNode); assertNull(nn.mem().in(1)); // Partial allocation input. + nn.cacheRegs(code); MachNode mach = (MachNode)nn; assertNull(mach.regmap(1)); assertNotNull(mach.regmap(2)); @@ -480,7 +413,7 @@ return sq(arg) + sq(3); int before = p.x + arg; a.x=33; b.x=44; return before; - """).parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2","SystemV").GCM().localSched(); + """).parse().opto().typeCheck().loopTree().instSelect("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); diff --git a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 104be01e..e63fb32e 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -6,18 +6,47 @@ import com.seaofnodes.simple.print.ASMPrinter; import org.junit.Assert; import org.junit.Ignore; import org.junit.Test; -import static com.seaofnodes.simple.Main.PORTS; import static org.junit.Assert.*; public class Chapter20Test { @Test public void testAllocatorTopPhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.topPhi(); } + @Test public void testNeverReturnAllocation() { + String[] sources = { + // A real integer return merged with a synthetic exit. + "if(arg) while(1) {} return arg+1;", + // TOP must not widen a non-null pointer or constrain a float register. + "struct S { int x; }; !S !s=new S; if(arg) while(1) {} return s;", + "if(arg) while(1) {} return 1.5;", + // Several synthetic exits into the same return. + "if(arg==1) while(1) {} if(arg==2) while(1) {} return arg+3;", + // No real return, including a merge of only synthetic exits. + "while(1) { arg+=1; }", + "if(arg) while(1) {} while(1) {}", + // Loop-carried memory and scalar self-conflicts exercise spilling. + "struct S { int x; int y; }; !S !a=new S; if(arg) while(1) { a.x+=arg; a.y+=a.x; } return a.x+a.y;" + }; + for( String target : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : sources ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.RegAlloc,target,"SystemV"); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + assertNotNull(code._stop.walk(n -> { + if( n._type!=com.seaofnodes.simple.type.Type.TOP ) return null; + assertEquals(-1,code._regAlloc.regnum(n)); + for( var use : n.outs() ) + assertFalse(use instanceof com.seaofnodes.simple.node.SplitNode); + return n; + })); + code.encode(); + } + } + @Test public void testAllocatorFixedNeighbor() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.uncoloredFixedNeighbor(); } @Test public void testNarrowStoreMasks() { for( String type : new String[]{"i8","u8","i16","u16"} ) { CodeGen code = new CodeGen("struct S { "+type+" x; }; !S !s=new S; s.x=arg; return 0;") - .parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2","SystemV").GCM().localSched().regAlloc(); + .driver(CodeGen.Phase.RegAlloc,"x86_64_v2","SystemV"); int stores=0; for( var bb : code._cfg ) for( var node : bb.outs() ) @@ -76,10 +105,10 @@ return f(s); static void testCPU(String src, String cpu, String os, int spills, String stop) { CodeGen code = new CodeGen(src); - code.parse().opto().typeCheck().instSelect(PORTS,cpu,os).GCM().localSched().regAlloc().encode(); + code.driver(CodeGen.Phase.RegAlloc,cpu,os); com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); SpillStats.record(code,"Chapter20",cpu,os); - assertEquals("Expect spills: "+cpu,spills,code._regAlloc._spillScaled,Math.max(1,spills>>3)); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop!=null ) assertEquals(stop,code._stop.toString()); } @@ -90,7 +119,9 @@ return f(s); } @Test public void testAlloc0() { - testAllCPUs("return new u8[arg];", 1, "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() { @@ -115,9 +146,9 @@ val sqrt = { int x -> }; return sqrt(arg) + sqrt(arg+2); """; - testTarget(src,"x86_64_v2", "SystemV",26,null); - testTarget(src,"riscv" , "SystemV",19,null); - testTarget(src,"arm" , "SystemV",26,null); + testTarget(src,"x86_64_v2", "SystemV",23,null); + testTarget(src,"riscv" , "SystemV",17,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test @@ -136,15 +167,17 @@ val sqrt = { flt x -> flt farg = arg; return sqrt(farg) + sqrt(farg+2.0); """; - testTarget(src,"x86_64_v2", "SystemV",25,null); - testTarget(src,"riscv" , "SystemV",21,null); + 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];"; - testAllCPUs(src,1,"return .[];"); + testTarget(src,"x86_64_v2","SystemV",4,"return .[];"); + testTarget(src,"riscv","SystemV",8,"return .[];"); + testTarget(src,"arm","SystemV",9,"return .[];"); } @Test @@ -160,9 +193,9 @@ 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",13,"return .[];"); - testTarget(src,"riscv" , "SystemV",1,"return (add,.[],(mul,.[],1000));"); - testTarget(src,"arm" , "SystemV",1,"return (add,.[],(muli,.[]));"); + testTarget(src,"x86_64_v2", "SystemV",7,"return .[];"); + testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); + testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } @Test @@ -203,15 +236,17 @@ s.cs[0] = 67; // C s.cs[1] = 108; // l hashCode(s); """; - testTarget(src,"x86_64_v2", "SystemV",21,null); - testTarget(src,"riscv" , "SystemV", 3,null); - testTarget(src,"arm" , "SystemV", 3,null); + testTarget(src,"x86_64_v2", "SystemV",15,null); + testTarget(src,"riscv" , "SystemV", 10,null); + testTarget(src,"arm" , "SystemV", 10,null); } @Test public void testCast() { String src = "struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1;"; - testAllCPUs(src,0,null); + testTarget(src,"x86_64_v2","SystemV",1,null); + testTarget(src,"riscv","SystemV",2,null); + testTarget(src,"arm","SystemV",2,null); } @Test @@ -248,14 +283,132 @@ return arg; 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",146,null); + testTarget(src,"arm" , "SystemV",34,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",41,null); +//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + } + @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(); + var code = new CodeGen(src).parse().opto().typeCheck().loopTree() + .instSelect(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. diff --git a/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java new file mode 100644 index 00000000..bc300217 --- /dev/null +++ b/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" ,23,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/stringHash.smp")); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV", 3,null); + Chapter21Test.testCPU(src,"arm" , "SystemV", 1,null); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/src/test/java/com/seaofnodes/simple/Chapter21Test.java new file mode 100644 index 00000000..a51ae3bc --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -0,0 +1,532 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.isa.eval.EvalRisc5; + +import com.seaofnodes.isa.eval.EvalArm64; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.cpus.arm.arm; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Ignore; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter21Test { + + @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<ops.length; i++ ) { + EvalArm64 cpu = new EvalArm64(new byte[1<<16],1<<15); + cpu.st4(0,ops[i]); cpu.regs[1]=value; + assertEquals(0,cpu.step(1)); + assertEquals(expected[i],cpu.regs[0]); + } + } + + + @Test public void testReturnedFunctionEncoding() throws IOException { + String src = "if(arg) return {->42;}; return {->43;};"; + CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); + for( int arg : new int[]{0,1} ) { + byte[] image = new byte[1<<16]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalRisc5 cpu = new EvalRisc5(image,1<<15); + cpu._pc = code._encoding._opStart[code.link(code._main)._nid]; + cpu.regs[riscv.A0] = arg; + assertEquals(0,cpu.step(100)); + assertEquals(0,cpu._pc); + cpu._pc = (int)cpu.regs[riscv.A0]; + assertEquals(0,cpu.step(100)); + assertEquals(0,cpu._pc); + assertEquals(arg==0 ? 43 : 42,cpu.regs[riscv.A0]); + } + // Anonymous bodies need code, but no exported ELF name. + new CodeGen(src).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,"build/objs/anonymous.o"); + } + + @Test public void testArmFloatMemory() throws IOException { + for( String type : new String[]{"f32","f64"} ) { + String src = type+"[] !a=new "+type+"[3]; a[arg]=1.25; return a[1];"; + CodeGen code = new CodeGen(src).driver("arm","SystemV",null); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalArm64 cpu = new EvalArm64(image,1<<16); + 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 testNarrowStores() throws IOException { + for( String type : new String[]{"i8","u8","i16","u16"} ) { + String src = "struct S { "+type+" x; }; !S !s = new S; s.x = arg; return 0;"; + CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); + int stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.riscv.StoreRISC st ) { + stores++; + assertEquals("Byte/short stores have no FP encoding",-1,st.regmap(4).nextReg((short)31)); + } + assertEquals(1,stores); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu.regs[riscv.A0] = 0x8765; + assertEquals(0,cpu.step(100)); + assertEquals(type.endsWith("8") ? 0x65 : 0x8765, + type.endsWith("8") ? cpu.ld1z(1<<16) : cpu.ld2z(1<<16)); + code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"x86_64_v2",TestC.CALL_CONVENTION); + stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) { + stores++; + assertEquals("Byte/short stores have no XMM encoding",-1,st.regmap(4).nextReg((short)15)); + } + assertEquals(1,stores); + } + } + + + @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); + } + + 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 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 testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } + @Test public void testCopyForward() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyForward(); } + @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<Integer,Long> 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<mem.length; i++ ) { + int expected = i>=8 && i<16 ? (int)(value >>> (8*(i-8)))&0xFF : 0xA5; + assertEquals("byte "+i,expected,mem[i]&0xFF); + } + assertEquals(value,load.applyAsLong(8)); + } + } + + + @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); + testCPU(src,"riscv" , "SystemV",-1,null); + testCPU(src,"arm" , "SystemV",-1,null); + } + + static void testCPU( String src, String cpu, String os, int spills, String stop ) { + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + SpillStats.record(code,"Chapter21",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + if( stop != null ) + assertEquals(stop, code._stop.toString()); + } + + + @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++;"; + 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() 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", 7,"return (add,.[],(mul,.[],1000));"); + testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); + } + + @Test + public void testAntiDeps1() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/antiDep1.smp")); + testCPU(src,"x86_64_v2", "SystemV", 7,"return mov(mov(S));"); + testCPU(src,"riscv" , "SystemV",10,"return mov(mov(S));"); + testCPU(src,"arm" , "SystemV",10,"return mov(mov(S));"); + } + + @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", 1,null); + } + + @Test public void testStringExport() throws IOException { + TestC.run("stringHash", 9); + } + + @Test public void testLoop2() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/loop2.smp")); + testCPU(src,"x86_64_v2", "Win64" ,0,"return (inc,Phi(Loop,0,inc));"); + testCPU(src,"riscv" , "SystemV",0,"return ( Phi(Loop,0,addi) + #1 );"); + testCPU(src,"arm" , "SystemV",0,"return (inc,Phi(Loop,0,inc));"); + } + + @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) +"""; + TestC.run("newtonFloat",result,34); + + EvalRisc5 R5 = TestRisc5.build("newtonFloat", 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("newtonFloat", 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 { + // 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.run("sieve",sprimes, 185); + + // Evaluate on RISC5 emulator; expect return of an array of primes in + // the simulated heap. + EvalRisc5 R5 = TestRisc5.build("sieve", 100, 92, 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<primes.length; i++ ) + assertEquals(primes[i], R5.ld4s(ary + 4 + i*4)); + + // Evaluate on ARM5 emulator; expect return of an array of primes in + // the simulated heap. + EvalArm64 A5 = TestArm64.build("sieve", 100, 91, false); + int trap_arm = A5.step(10000); + assertEquals(0, trap_arm); + int ary_arm = (int)A5.regs[arm.X0]; + // Memory layout starting at ary(length,pad, prime1, primt2, prime3, prime4) + assertEquals(primes.length, A5.ld4s(ary_arm)); + for( int i = 0; i<primes.length; i++ ) + assertEquals(primes[i], A5.ld4s(ary_arm + 4 + i * 4)); + } + + @Test public void testFibExport() throws IOException { + String fib = "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"; + TestC.run("fib", fib, 24); + + EvalRisc5 R5 = TestRisc5.build("fib", 9, 16, 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", 9, 16, 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 person = "6\n"; + TestC.run("person", person, 0); + + // 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("person", ps, 0, 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("person", ps, 0, 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 arg_count = "191.000000\n"; + TestC.run("arg_count", arg_count, + TestC.CALL_CONVENTION.equals("Win64") ? 32 : 9); + + + EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", 0, 0, 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; + + // a0 is passed in arg + 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; + R5.regs[riscv.A7] = 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("no_stack_arg_count", 0, 0, 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); + } +} diff --git a/src/test/java/com/seaofnodes/simple/Compile.java b/src/test/java/com/seaofnodes/simple/Compile.java new file mode 100644 index 00000000..088055f9 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Compile.java @@ -0,0 +1,65 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.FunNode; +import java.io.IOException; +import java.nio.charset.StandardCharsets; +import java.nio.file.Files; +import java.nio.file.Path; +import java.util.ArrayList; +import org.junit.Ignore; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Compile { + + private static Process run(String simple, String c) throws IOException, InterruptedException { + boolean USE_WSL = System.getProperty("os.name").startsWith("Windows"); + CodeGen code = new CodeGen(simple); + code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched().regAlloc().encode(); + if (c != null) for (var n:code._start._outputs) if (n instanceof FunNode f && f._name.equals("main")) f._name = "simple_main"; + code.exportELF("test.o"); + var params = new ArrayList<String>(); + if (USE_WSL) params.add("wsl.exe"); + params.add("gcc"); + params.add("-o"); + params.add("test"); + if (c != null) { + Files.writeString(Path.of("test.c"), c); + params.add("test.c"); + } + params.add("test.o"); + Process p = Runtime.getRuntime().exec(params.toArray(String[]::new)); + assertEquals(0, p.waitFor()); + return Runtime.getRuntime().exec(USE_WSL ? new String[]{"wsl.exe", "./test"}:new String[]{"./test"}); + } + + @Test + @Ignore + public void testCompile() throws IOException, InterruptedException { + var p = run(""" + val testMy = { flt x -> + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } + }; + """,""" + + #include <stdio.h> + + extern double testMy(double); + + int main(int argc, char** argv) { + printf("%f\\n", testMy(2.0)); + return 0; + } + + """); + assertEquals(0, p.waitFor()); + assertEquals("1.414214\n", new String(p.getInputStream().readAllBytes(), StandardCharsets.UTF_8)); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/Eval2.java b/src/test/java/com/seaofnodes/simple/Eval2.java index 3312ec6b..a855350e 100644 --- a/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/src/test/java/com/seaofnodes/simple/Eval2.java @@ -117,6 +117,7 @@ public abstract class Eval2 { SB trace = null; // new SB(); // TRACE, set to null for off, new SB() for on // Force local scheduling phase if( code._phase.ordinal() < CodeGen.Phase.TypeCheck .ordinal() ) code.typeCheck(); + if( code._phase.ordinal() < CodeGen.Phase.LoopTree .ordinal() ) code.loopTree(); if( code._phase.ordinal() < CodeGen.Phase.Schedule .ordinal() ) code.GCM(); if( code._phase.ordinal() < CodeGen.Phase.LocalSched.ordinal() ) code.localSched(); // Set global, so don't have to pass everywhere @@ -159,6 +160,7 @@ public abstract class Eval2 { switch( prior ) { case StartNode start: F = new Frame(F); break; // Frame for the call to main, as-if Called case CallNode call : BB = call(call); break; + case NeverNode never: BB = never.cproj(0); break; // Synthetic exit is never taken. case IfNode iff : Object p = val(iff.pred()); BB = iff.cproj( p==null || (p instanceof Long x && x==0L) ? 1 : 0); break; case ReturnNode ret : if( clj(ret.rpc()).isStop() ) return exit(ret); else BB = ret(ret); break; case FunNode fun : if( loopCnt++ > timeout ) return null; break; // Timeout diff --git a/src/test/java/com/seaofnodes/simple/Main.java b/src/test/java/com/seaofnodes/simple/Main.java index f3a6784c..589c043b 100644 --- a/src/test/java/com/seaofnodes/simple/Main.java +++ b/src/test/java/com/seaofnodes/simple/Main.java @@ -5,7 +5,6 @@ import java.nio.file.Files; import java.nio.file.Path; public class Main { - public static final String PORTS = "com.seaofnodes.simple.node.cpus"; // Compile and run a simple program public static void main( String[] args ) throws Exception { // First arg is file, 2nd+ args are program args diff --git a/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java new file mode 100644 index 00000000..1ce2cd34 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -0,0 +1,180 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.isa.eval.EvalRisc5; + +import com.seaofnodes.isa.eval.EvalArm64; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.RegAllocTestSupport; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.arm.arm; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Test; +import static org.junit.Assert.*; + +// Execution regressions are separate from the fixed spill-measurement cohorts. +public class MemoryEncodingTest { + @Test public void testLoopLoadSearch() { + String[] sources = { + """ + u8[] !program=new u8[106]; u8[] !out=new u8[0]; + int sum=0; + for(int i=0; i<arg; i++) { + sum+=program#; + if(i==1) out=new u8[i+1]; + else if(i==3) out=new u8[2]; + } + return sum+out#; + """, + // One possibly aliasing arm must reject the unchanged-memory proof. + """ + 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++) { + if(i==2) p.x=30; + else if(i==4) b.x=40; + sum+=a.x; + } + return sum; + """, + // Unchanged memory does not imply an unchanged loop-carried pointer. + """ + struct S { int x; }; !S !a=new S; !S !b=new S; + a.x=10; b.x=20; !S !p=a; int sum=0; + for(int i=0; i<6; i++) { + if(i==2) a.x=30; + sum+=p.x; + p=b; if(i&1) p=a; + } + return sum; + """, + // All arms fold, but their values differ: build a value Phi. + """ + struct S { int x; }; !S !a=new S; a.x=1; int sum=0; + for(int i=0; i<6; i++) { + sum+=a.x; + if(i&1) a.x=2; + else if(i==2) a.x=3; + else a.x=4; + } + return sum; + """ + }; + for( int p=0; p<sources.length; p++ ) { + CodeGen code=new CodeGen(sources[p]).parse().opto(); + if( p==0 ) assertNull(code._stop.walk(n -> + n instanceof LoadNode ld && ld.ptr() instanceof ProjNode ptr && + ptr.in(0) instanceof NewNode nn && + nn.size()._type==com.seaofnodes.simple.type.TypeInteger.constant(110) ? ld : null)); + for( int arg=0; arg<7; arg++ ) { + long expected=switch(p) { + case 0 -> 106*arg+(arg>=2 ? 2 : 0); + case 1 -> (arg&1)==0 ? 140 : 60; + case 2 -> 130; + default -> 16; + }; + assertEquals(Long.toString(expected),Eval2.eval(code,arg)); + } + } + } + + private static final String[] SOURCES = { + Chapter16Test.CONSTRUCTOR_MEMORY, + Chapter18Test.CALL_MEMORY, + Chapter18Test.RECURSIVE_MEMORY, + Chapter18Test.INLINE_MEMORY, + "int[] !a = new int[7]; a[arg]=arg+3; return a[0]+1;", + """ + int[] !a = new int[7]; + for( int i=0; i<7; i++ ) a[i]=i+arg; + for( int i=0; i<6; i++ ) a[i+1]+=a[i]; + return a[6]; + """ + }; + + private static long expected(int program, long arg) { + return switch(program) { + case 0 -> arg==0 ? 111249 : 222351+arg; + case 1 -> arg==0 ? 10101325 : 20202322; + case 2 -> (10*(arg+1)+arg*(arg+1)/2)*100+10+arg; + case 3 -> 400944+arg*10001; + case 4 -> arg==0 ? 4 : 1; + case 5 -> 21+7*arg; + default -> throw new AssertionError(); + }; + } + + @Test public void testEmulatedMemory() throws IOException { + for( String target : new String[]{"riscv","arm"} ) + for( int p=0; p<SOURCES.length; p++ ) { + CodeGen code = new CodeGen(SOURCES[p]).driver(target,"SystemV",null); + RegAllocTestSupport.checkRegisters(code); + int entry=0; + for( var n : code._start._outputs ) + if( n instanceof FunNode fun && "main".equals(fun._name) ) + entry=code._encoding._opStart[fun._nid]; + for( int arg=0; arg<7; arg++ ) { + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + long result; + if( target.equals("riscv") ) { + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu._pc=entry; + cpu.regs[riscv.A0]=arg; + assertEquals(target+" program "+p+" arg "+arg,0,cpu.step(100000)); + result=cpu.regs[riscv.A0]; + } else { + EvalArm64 cpu = new EvalArm64(image,1<<16); + cpu._pc=entry; + cpu.regs[arm.X0]=arg; + assertEquals(target+" program "+p+" arg "+arg,0,cpu.step(100000)); + result=cpu.regs[arm.X0]; + } + assertEquals(target+" program "+p+" arg "+arg,expected(p,arg),result); + } + } + } + + @Test public void testNeverMemory() { + // A varying pointer prevents store sinking: the synthetic exit needs both slices. + for( String target : new String[]{"x86_64_v2","riscv","arm"} ) { + CodeGen code = new CodeGen(""" + struct S { int x; int y; }; + !S !a=new S; !S !b=new S; !S !p=a; + if( arg ) while( 1 ) { p.x+=arg; p.y+=p.x; p=p==a ? b : a; } + return a.x+a.y; + """).driver(CodeGen.Phase.LoopTree); + assertNotNull(code._stop.walk(n -> { + if( n instanceof MemMergeNode mem && + mem.in(0) instanceof CProjNode exit && exit.in(0) instanceof NeverNode ) { + assertTrue(mem.alias(2) instanceof MemPhiNode); + assertTrue(mem.alias(3) instanceof MemPhiNode); + return mem; + } + return null; + })); + code.instSelect(target,"SystemV").GCM().localSched().regAlloc(); + RegAllocTestSupport.checkRegisters(code); + code.encode(); + } + } + + @Test public void testNativeMemory() throws IOException { + Files.createDirectories(Path.of("build/objs")); + for( int p=0; p<SOURCES.length; p++ ) { + String file="build/objs/memory"+p; + StringBuilder c = new StringBuilder("extern long long memory(long long);\nint main() {\n"); + for( int arg=0; arg<7; arg++ ) + c.append("if(memory(").append(arg).append(")!=").append(expected(p,arg)).append("LL) return ").append(arg+1).append(";\n"); + c.append("return 0;\n}\n"); + Files.writeString(Path.of(file+".c"),c); + TestC._run("val memory = { int arg -> "+SOURCES[p]+" };", + TestC.CALL_CONVENTION,"",file+".c",file,"S","",-1); + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/src/test/java/com/seaofnodes/simple/MergeSortTest.java index 31fbe3a4..788bd9c2 100644 --- a/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -1,67 +1,46 @@ package com.seaofnodes.simple; +import com.seaofnodes.isa.eval.EvalRisc5; + import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class MergeSortTest { - @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; -"""; - Chapter20Test.testCPU(src,"x86_64_v2", "SystemV",46,"Stop[ return mov(mov([int])); return 0; ]"); - Chapter20Test.testCPU(src,"riscv" , "SystemV",36,"Stop[ return mov(mov([int])); return 0; ]"); - Chapter20Test.testCPU(src,"arm" , "SystemV",37,"Stop[ return mov(mov([int])); return 0; ]"); -//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + @Test public void testMergeSort0() throws IOException { + 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(); + TestC.run("sort", sprimes, 34); + + + EvalRisc5 R5 = TestRisc5.build("src/test/java/com/seaofnodes/simple/progs", "sort", "merge_sort", 0, 36, false); + // Allocate an array of primes, filled in reverse order + int ps = R5._heap; + R5._heap += (primes.length+1)*8; // 25 primes, and length + R5.st4(ps,primes.length); + for( int i=0; i<primes.length; i++ ) + R5.st8(ps+(primes.length-1-i+1)*8,primes[i]); + // Pass array base when calling `merge_sort` + R5.regs[riscv.A0] = ps; // Array base to be sorted + + int trap = R5.step(100000); + assertEquals(0,trap); + + assertEquals(primes.length,R5.ld4s(ps)); + for( int i=0; i<primes.length; i++ ) + assertEquals(primes[i], R5.ld8(ps+(i+1)*8)); + + // TODO: replace with ARM Eval + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/sort.smp")); + Chapter21Test.testCPU(src,"arm", "SystemV",36,null); } - } diff --git a/src/test/java/com/seaofnodes/simple/Simple.java b/src/test/java/com/seaofnodes/simple/Simple.java new file mode 100644 index 00000000..705b086a --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Simple.java @@ -0,0 +1,287 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.*; + +import java.nio.file.Files; +import java.nio.file.Path; +import java.io.InputStreamReader; +import java.io.BufferedReader; +import java.io.IOException; +import java.util.stream.Collectors; + +public class Simple { + public static final String PORTS = "com.seaofnodes.simple.node.cpus"; + + static final int DUMP_AFTER_PARSE = 1<<0; + static final int DUMP_AFTER_OPTO = 1<<1; + static final int DUMP_AFTER_TYPE_CHECK = 1<<2; + static final int DUMP_AFTER_LOOP_TREE = 1<<3; + static final int DUMP_AFTER_INSTR_SELECT = 1<<4; + static final int DUMP_AFTER_GCM = 1<<5; + static final int DUMP_AFTER_LOCAL_SCHED = 1<<6; + static final int DUMP_AFTER_REG_ALLOC = 1<<7; + static final int DUMP_AFTER_ENCODE = 1<<8; + + static final int DUMP_FINAL = 1<<16; + + static final int DUMP_PASS_NAME = 1<<30; + static final int DUMP_AFTER_ALL = 0xff | DUMP_PASS_NAME; + + static final int DUMP_DISASSEMBLE = 1<<31; + + static String system_cpu = null; + static String system_abi = null; + + static void usage() { + System.out.println( +""" +simple <input-file> [options] [--eval|--run ...] +Options: + --dump - dump final intermediate representation + --dump-after-parse - dump intermediate representation after parse + --dump-after-opto - dump intermediate representation after opto pass + --dump-after-type-check - dump intermediate representation after type check pass + --dump-after-instr-select - dump intermediate representation after instrution selection pass + --dump-after-gcm - dump intermediate representation after GCM pass + --dump-after-local-sched - dump intermediate representation after local scheduling pass + --dump-after-reg-alloc - dump intermediate representation after register allocation pass + --dump-after-encode - dump intermediate representation after encoding pass + --dump-after-all - dump intermediate representation after all passes + -S - dump generated assembler code + --eval ... - evaluate the compiled code in emulator + --run ... - run the compiled code natively + --dump-size - print the size of generated code + --dump-time - print compilation and execution times + --cpu <cpu-name> - use specific CPU (x86_64_v2, riscv, arm) + --abi <abi-name> - use speific ABI variant (SystemV) + --target - print native CPU and ABI + --version + --help +""" +); + System.exit(0); + } + + static void bad_usage() { + System.err.println("ERROR: Invalid usage (use --help)"); + System.exit(1); + } + + static void target() { + if (system_cpu == null || system_abi == null) { + System.err.println("ERROR: Unknown target"); + System.exit(1); + } + System.out.print(system_cpu); + System.out.print("-"); + System.out.println(system_abi); + System.exit(0); + } + + static void dump(CodeGen code, int dump, int pass) { + if ((dump & pass) != 0) { + if ((dump & DUMP_PASS_NAME) != 0) { + System.err.println(switch (pass) { + case DUMP_AFTER_PARSE -> "After Parse:"; + case DUMP_AFTER_OPTO -> "After OPTO:"; + case DUMP_AFTER_TYPE_CHECK -> "After Type Check:"; + case DUMP_AFTER_LOOP_TREE -> "After Loop Tree:"; + case DUMP_AFTER_INSTR_SELECT -> "After Instruction Selection:"; + case DUMP_AFTER_GCM -> "After GCM:"; + case DUMP_AFTER_LOCAL_SCHED -> "After Local Scheduling:"; + case DUMP_AFTER_REG_ALLOC -> "After Register Allocation:"; + case DUMP_AFTER_ENCODE -> "After Instruction Encoding:"; + case DUMP_FINAL -> "Final:"; + default -> throw Utils.TODO(); + }); + } + + System.err.println(IRPrinter.prettyPrint(code._stop, 9999)); + + } + } + + static void print_compilation_times(CodeGen code) { + double t, total = 0; + + total += t = code._tParse / 1e3; + System.out.println(String.format("Parsing Time: %.3f sec", t)); + total += t = code._tOpto / 1e3; + System.out.println(String.format("Optimization Time: %.3f sec", t)); + total += t = code._tTypeCheck / 1e3; + System.out.println(String.format("Type Checking Time: %.3f sec", t)); + total += t = code._tLoopTree / 1e3; + System.out.println(String.format("Loop Tree Time: %.3f sec", t)); + total += t = code._tInsSel / 1e3; + System.out.println(String.format("Instruction Selection Time: %.3f sec", t)); + total += t = code._tGCM / 1e3; + System.out.println(String.format("GCM Time: %.3f sec", t)); + total += t = code._tLocal / 1e3; + System.out.println(String.format("Local Scheduling Time: %.3f sec", t)); + total += t = code._tRegAlloc / 1e3; + System.out.println(String.format("Register Allocation Time: %.3f sec", t)); + total += t = code._tEncode / 1e3; + System.out.println(String.format("Instruction Encoding Time: %.3f sec", t)); + System.out.println(String.format("TOTAL COMPILATION TIME: %.3f sec", total)); + } + + static String getInput() throws IOException { + try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) { + return reader.lines().collect(Collectors.joining("\n")); + } + } + + public static void main(String[] args) throws Exception { + String input_filename = null; + boolean use_stdin = false; + boolean do_eval = false; + boolean do_run = false; + boolean do_codegen = false; + boolean do_print_size = false; + boolean do_print_time = false; + int dump = 0; + int first_arg = 0; + String src = null; + String cpu = null; + String abi = null; + + // TODO: autodetect + system_cpu = "x86_64_v2"; + system_abi = "SystemV"; + + // Parse command line +loop: for (int i = 0; i < args.length; i++) { + String arg = args[i]; + if (arg.charAt(0) == '-') { + switch (arg) { + case "-": use_stdin = true; break; + case "--dump": dump |= DUMP_FINAL; break; + case "--dump-after-parse": dump |= DUMP_AFTER_PARSE; break; + case "--dump-after-opto": dump |= DUMP_AFTER_OPTO; break; + case "--dump-after-type-check": dump |= DUMP_AFTER_TYPE_CHECK; break; + case "--dump-after-loop-tree": dump |= DUMP_AFTER_LOOP_TREE; break; + case "--dump-after-instr-select": dump |= DUMP_AFTER_INSTR_SELECT; break; + case "--dump-after-gcm": dump |= DUMP_AFTER_GCM; break; + case "--dump-after-local-sched": dump |= DUMP_AFTER_LOCAL_SCHED; break; + case "--dump-after-reg-alloc": dump |= DUMP_AFTER_REG_ALLOC; break; + case "--dump-after-encode": dump |= DUMP_AFTER_ENCODE; break; + case "--dump-after-all": dump |= DUMP_AFTER_ALL; break; + case "-S": dump |= DUMP_DISASSEMBLE; break; + case "--eval": do_eval = true; first_arg = i + 1; break loop; + case "--run": do_run = true; first_arg = i + 1; break loop; + case "--dump-size": do_print_size = true; break; + case "--dump-time": do_print_time = true; break; + case "--cpu": if (cpu != null + || i + 1 >= args.length + || args[i + 1].charAt(0) == '-') bad_usage(); + cpu = args[i + 1]; + i++; + break; + case "--abi": if (abi != null + || i + 1 >= args.length + || args[i + 1].charAt(0) == '-') bad_usage(); + abi = args[i + 1]; + i++; + break; + case "--target": target(); + case "--version": throw Utils.TODO(); + case "--help": usage(); + default: bad_usage(); + } + } else { + if (input_filename != null || use_stdin) bad_usage(); + input_filename = arg; + } + } + + if (input_filename == null && !use_stdin) { + System.err.println("ERROR: no input file' (use --help)"); + System.exit(1); + } + + if (do_run || (dump & DUMP_DISASSEMBLE) != 0 || do_print_size) { + if (cpu == null) cpu = system_cpu; + if (abi == null) abi = system_abi; + if (cpu == null || abi == null) { + System.err.println("ERROR: Cannot compile for unknown target"); + System.exit(1); + } + do_codegen = true; + } + + // Read input file + try { + src = use_stdin ? getInput() : Files.readString(Path.of(input_filename)); + } catch(IOException e) { + System.err.println("ERROR: Cannot read input file"); + System.exit(1); + } + + // Compilation pipeline + CodeGen code = new CodeGen(src); + + code.parse(); + dump(code, dump, DUMP_AFTER_PARSE); + + code.opto(); + dump(code, dump, DUMP_AFTER_OPTO); + + code.typeCheck(); + dump(code, dump, DUMP_AFTER_TYPE_CHECK); + + code.loopTree(); + dump(code, dump, DUMP_AFTER_LOOP_TREE); + + if (do_codegen) { + code.instSelect(PORTS, cpu, abi); + dump(code, dump, DUMP_AFTER_INSTR_SELECT); + } + + code.GCM(); + dump(code, dump, DUMP_AFTER_GCM); + + code.localSched(); + dump(code, dump, DUMP_AFTER_LOCAL_SCHED); + + if (do_codegen) { + code.regAlloc(); + dump(code, dump, DUMP_AFTER_REG_ALLOC); + + code.encode(); + dump(code, dump, DUMP_AFTER_ENCODE); + } + + dump(code, dump, DUMP_FINAL); + + if (do_codegen && (dump & DUMP_DISASSEMBLE) != 0) { + System.out.println(code.asm()); + } + + if (do_print_size) { + System.out.println(String.format("Code Size: %d", code._encoding._bits.size())); + } + + if (do_print_time) { + print_compilation_times(code); + } + + if (do_eval) { + // TODO: Support for evaluation of functions with different argument numbers and types + long t = System.currentTimeMillis(); + long arg = (first_arg < args.length) ? Integer.valueOf(args[first_arg]) : 0; + System.out.println(Eval2.eval(code, arg, 100000)); + if (do_print_time) { + System.out.println(String.format("EXECUTION TIME: %.3f sec", + (System.currentTimeMillis() - t) / 1e3)); + } + } else if (do_run) { + if (cpu != system_cpu || abi != system_abi) { + System.err.println("ERROR: cannot run code on not native target"); + System.exit(1); + } + + throw Utils.TODO(); + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/SpillStats.java b/src/test/java/com/seaofnodes/simple/SpillStats.java index 9b03da7b..318a6e33 100644 --- a/src/test/java/com/seaofnodes/simple/SpillStats.java +++ b/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -11,6 +11,7 @@ import org.junit.runner.notification.*; 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; } @@ -25,8 +26,20 @@ public class SpillStats extends RunListener { code._regAlloc._spills+","+code._regAlloc._spillScaled); } + // 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","BrainFuckTest","MergeSortTest"}; + if( args.length==0 ) args = new String[]{"Chapter20Test","Chapter21Test","Chapter21AllocTest","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]); @@ -34,7 +47,8 @@ public class SpillStats extends RunListener { JUnitCore junit = new JUnitCore(); junit.addListener(ACTIVE); Result result = junit.run(tests); - if( !result.wasSuccessful() ) System.out.println("FAILED test run: totals are not a complete comparison."); + boolean passed = result.wasSuccessful() && ACTIVE._qualityFailures==0; + if( !passed ) System.out.println("FAILED test run: totals are not a complete comparison."); System.out.println("cohort,cpu,abi,allocations,splits,scaled"); for( var row : ACTIVE._totals.entrySet() ) { long[] sum = row.getValue(); @@ -42,7 +56,8 @@ public class SpillStats extends RunListener { } 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( !result.wasSuccessful() ) System.exit(1); + if( !passed ) System.exit(1); } } diff --git a/src/test/java/com/seaofnodes/simple/TestArm64.java b/src/test/java/com/seaofnodes/simple/TestArm64.java new file mode 100644 index 00000000..e4bc38a0 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.isa.eval.EvalArm64; + + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.cpus.arm.arm; +import junit.framework.Assert; +import java.nio.file.Files; +import java.nio.file.Path; +import java.io.IOException; + +import static org.junit.Assert.assertEquals; + +// Runs 32-bit ARM code in an emulator + +public class TestArm64 { + public static EvalArm64 build( String file, int arg, int spills, boolean print ) throws IOException { + return build("src/test/java/com/seaofnodes/simple/progs",file, arg, spills, print); + } + + // Compile and run a simple program + public static EvalArm64 build( String dir, String file, int arg, int spills, boolean print ) throws IOException { + // Compile and export Simple + String src = Files.readString(Path.of(dir+"/"+file+".smp")); + CodeGen code = new CodeGen(src).driver("arm", "SystemV",null); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + SpillStats.record(code,"Chapter21","arm","SystemV"); + if( print ) { code.print_as_hex(); System.out.print(code.asm()); } + + // Allocation quality not degraded + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + + // Image + byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) + EvalArm64 ARM = new EvalArm64(image, 1<<16); + // Code at offset 0 + System.arraycopy(code._encoding.bits(), 0, image, 0, code._encoding.bits().length); + // Initial incoming int arg + ARM.regs[arm.X0] = arg; + // malloc memory starts at 64K and goes up + return ARM; + } +} diff --git a/src/test/java/com/seaofnodes/simple/TestC.java b/src/test/java/com/seaofnodes/simple/TestC.java new file mode 100644 index 00000000..b3e21ea7 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/TestC.java @@ -0,0 +1,88 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import java.nio.file.Files; +import java.nio.file.Path; +import java.io.InputStream; +import java.io.IOException; +import static org.junit.Assert.*; + +// Call a C driver program, which calls a Simple-generated .o, and self-checks. +// Expects GCC from the default CLI, compiles C, compiles Simple, links and runs. +public abstract class TestC { + + public static final String OS = System.getProperty("os.name"); + public static final String CPU = System.getProperty("os.arch"); + + public static final String CALL_CONVENTION = OS.startsWith("Windows") ? "Win64" : "SystemV"; + public static final String CPU_PORT = switch( CPU ) { + case "amd64" -> "x86_64_v2"; + default -> throw Utils.TODO("Map Yer CPU Port Here"); + }; + + public static void run( String file, int spills ) throws IOException { run(file,"",spills); } + + public static void run( String file, String expected, int spills ) throws IOException { + run("src/test/java/com/seaofnodes/simple/progs",file,expected,spills); + } + + // Compile and run a simple program + public static void run( String dir, String file, String expected, int spills ) throws IOException { + // Files + String cfile = dir+"/"+file+".c" ; + String sfile = dir+"/"+file+".smp"; + String efile = "build/objs/"+file; + + // Compile and export Simple + String src = Files.readString(Path.of(sfile)); + _run(src,CALL_CONVENTION,"",cfile,efile,"S",expected,spills); + } + + static void _run( String src, String simple_conv, String c_conv, String cfile, String efile, String xtn, String expected, int spills ) throws IOException { + String bin = efile+xtn; + String obj = bin+".o"; + // Compile simple, emit ELF + CodeGen code = new CodeGen(src).driver( CPU_PORT, simple_conv, obj); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + SpillStats.record(code,"Chapter21",CPU_PORT,simple_conv); + + // Compile the C program + var params = new String[] { + //if (USE_WSL) "wsl.exe"; + "gcc", + cfile, + obj, + "-lm", // Picks up 'sqrt' for newtonFloat tests to compare + "-g", + "-o", + bin, + "-D", + "CALL_CONV="+c_conv, + }; + Process gcc = new ProcessBuilder(params).redirectErrorStream(true).start(); + int error; + try { error = gcc.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + String result = new String(gcc.getInputStream().readAllBytes()); + if( error!=0 ) { + System.err.println("gcc error code: "+error); + System.err.println(result); + } + assertEquals( 0, error ); + //assertTrue(result.isEmpty()); // No data in error stream + + // Execute results + Process smp = new ProcessBuilder(bin).redirectErrorStream(true).start(); + try { error = smp.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + result = new String(smp.getInputStream().readAllBytes()); + if( error!=0 ) { + System.err.println("exec error code: "+error); + System.err.println(result); + } + assertEquals( 0, error ); + assertEquals(expected,result); + + // Allocation quality not degraded + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + + } +} diff --git a/src/test/java/com/seaofnodes/simple/TestRisc5.java b/src/test/java/com/seaofnodes/simple/TestRisc5.java new file mode 100644 index 00000000..1289575d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -0,0 +1,51 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.isa.eval.EvalRisc5; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.FunNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import static org.junit.Assert.*; + +// Runs 32-bit R5 code in an emulator +public abstract class TestRisc5 { + + public static EvalRisc5 build( String file, int arg, int spills, boolean print ) throws IOException { + return build("src/test/java/com/seaofnodes/simple/progs",file, null, arg, spills, print); + } + + // Compile and run a simple program + public static EvalRisc5 build( String dir, String file, String main, int arg, int spills, boolean print ) throws IOException { + // Compile and export Simple + String src = Files.readString(Path.of(dir+"/"+file+".smp")); + CodeGen code = new CodeGen(src).driver("riscv", "SystemV",null); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + SpillStats.record(code,"Chapter21","riscv","SystemV"); + if( print ) { code.print_as_hex(); System.out.print(code.asm()); } + + // Allocation quality not degraded + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + + // Image + byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) + EvalRisc5 R5 = new EvalRisc5(image, 1<<16); + // Code at offset 0 + System.arraycopy(code._encoding.bits(), 0, image, 0, code._encoding.bits().length); + // Initial incoming int arg + R5.regs[riscv.A0] = arg; + // malloc memory starts at 64K and goes up + + // Look up starting PC or zero if not given + if( main!=null ) + for( Node use : code._start._outputs ) + if( use instanceof FunNode fun && main.equals(fun._name) ) + R5._pc = code._encoding._opStart[fun._nid]; + + return R5; + } + +} diff --git a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 2966cb00..739eba3b 100644 --- a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; import com.seaofnodes.simple.type.TypeInteger; -import java.io.ByteArrayOutputStream; import static org.junit.Assert.*; // Small scheduled machine graphs isolate register constraints from peepholes. @@ -21,11 +20,11 @@ public class RegAllocTestSupport { @Override public RegMask killmap() { return _kill; } @Override public boolean isClone() { return _clone; } @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); } - @Override public int encoding(ByteArrayOutputStream bytes) { throw new AssertionError(); } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } } private static CodeGen graph() { CodeGen code = new CodeGen(""); - code._mach = new x86_64_v2(); + code._mach = new x86_64_v2(code); code._cfg.add(code._start); return code; } @@ -192,4 +191,71 @@ public class RegAllocTestSupport { assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); } + public static void copyForward() throws Exception { + // Forwarding, fixed operand, two-address tie, intervening clobber, + // another user, and a scheduling-only edge. + for( int kind=0; kind<6; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode copy = code._mach.split("test",(byte)0,null); + copy.setDef(0,code._start); copy.setDef(1,def); + alloc.newLRG(copy)._reg=1; + if( kind==3 ) new Op(null,null,A,false,code._start); + int twoAddress = kind==2 ? 1 : 0; + RegMask mask = kind==1 ? B : kind==5 ? null : new RegMask(3L); + Op use = new Op(null,mask,null,false,code._start,copy) { + @Override public int twoAddress() { return twoAddress; } + }; + if( kind==4 ) new Op(null,B,null,false,code._start,copy); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame("copy case "+kind,kind==0 ? def : copy,use.in(1)); + assertEquals(kind==0 ? 0 : 1,alloc._spills); + } + } + + public static void coalescing() { + // Merge, incompatible masks, interference, capacity, and adjacency remapping. + for( int kind=0; kind<5; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + SplitNode copy = code._mach.split("test",(byte)0,null); + copy.setDef(0,code._start); copy.setDef(1,def); + Op use = new Op(null,new RegMask(3L),null,false,code._start,copy); + LRG from = alloc.newLRG(def), to = alloc.newLRG(copy); + from._mask = kind==1 ? A : new RegMask(3L); + to._mask = kind==1 ? B : new RegMask(3L); + from.machDef(def,false); from.machUse(copy,(short)1,false); + to.machDef(copy,false); to.machUse(use,(short)1,false); + LRG left = new LRG((short)100), right = new LRG((short)101); + if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); } + if( kind>=3 ) { + from.addNeighbor(left); left.addNeighbor(from); + if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); } + else { to.addNeighbor(left); left.addNeighbor(to); } + } + int fcnt=from.nadj(), tcnt=to.nadj(); + assertTrue(Coalesce.coalesce(0,alloc)); + if( kind==0 || kind==4 ) { + assertSame(def,use.in(1)); + assertSame(alloc.lrg(def),alloc.lrg(copy)); + assertSame(use,alloc.lrg(def)._machUse); + assertEquals(1,alloc.lrg(def)._uidx); + if( kind==4 ) { + assertEquals(1,left.nadj()); + assertSame(alloc.lrg(def),left._adj.at(0)); + assertSame(left,alloc.lrg(def)._adj.at(0)); + } + } else { + assertSame(copy,use.in(1)); + assertNotSame(alloc.lrg(def),alloc.lrg(copy)); + assertEquals(fcnt,from.nadj()); + assertEquals(tcnt,to.nadj()); + } + } + } + } diff --git a/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java new file mode 100644 index 00000000..368c243b --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java @@ -0,0 +1,97 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86; +import org.junit.Test; +import static org.junit.Assert.*; + +public class X86EncodingTest { + + @Test + public void testLogicalNotRegisters() { + CodeGen code = new CodeGen("return !arg;") + .driver(CodeGen.Phase.InstSelect, "x86_64_v2", "SystemV"); + var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null); + assertNotNull("Must exercise logical not", not); + int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}}; + // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping + // registers, low-byte registers requiring REX, and extended registers. + String[] expected = { + "4885c00f94c00fb6c0", "4885c90f94c10fb6c9", + "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9", + "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9", + "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff" + }; + for (int i = 0; i < registers.length; i++) { + int dst = registers[i][0], src = registers[i][1]; + var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src); + not.encoding(enc); + assertArrayEquals("Logical not dst=" + dst + ", src=" + src, + java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray()); + } + } + + @Test + public void testLogicalNotExecution() throws java.io.IOException { + var dir = java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"), + "val logicalNot = { int x -> return !x; };"); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """ + #include <limits.h> + extern long long logicalNot(long long); + int main(void) { + long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32}; + for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++) + if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1; + return 0; + } + """); + com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1); + } + @Test + public void testMemoryCompare64Immediate32() { + for (int immediate : new int[]{123456789, -123456789}) { + String src = "int[] !a = new int[2]; a[0] = arg; return a[arg & 1] == " + immediate + ";"; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding, "x86_64_v2", "SystemV"); + var cmp = code._stop.walk(n -> n instanceof CmpMemX86 ? n : null); + assertNotNull("Must exercise a memory comparison", cmp); + var enc = code._encoding; + int start = enc._opStart[cmp._nid]; + + // REX.W, 81 /7, SIB with scale 8, disp8, and a sign-extended imm32. + assertEquals(0x48, enc.read1(start) & 0xF8); + assertEquals(0x81, enc.read1(start + 1)); + assertEquals(0x7C, enc.read1(start + 2)); + assertEquals(0xC0, enc.read1(start + 3) & 0xC0); + assertEquals(8, enc.read1(start + 4)); + assertEquals(immediate, enc.read4(start + 5)); + assertEquals("CMP r/m64 uses four immediate bytes", 9, enc._opLen[cmp._nid]); + + // SETE must immediately follow the CPU's nine-byte CMP instruction. + assertEquals(0x0F, enc.read1(start + 9)); + assertEquals(0x94, enc.read1(start + 10)); + } + } + + /** Exercise instruction encoders with explicit registers, independent of allocator choices. */ + private static class FixedRegisterEncoding extends Encoding { + private final Node _dst, _src; + private final short _dstReg, _srcReg; + + FixedRegisterEncoding(CodeGen code, Node dst, int dstReg, Node src, int srcReg) { + super(code); + _dst = dst; + _src = src; + _dstReg = (short)dstReg; + _srcReg = (short)srcReg; + } + + @Override public short reg(Node n) { + if (n == _dst) return _dstReg; + if (n == _src) return _srcReg; + throw new AssertionError("Unexpected register lookup"); + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 4bfa7628..7ba9272f 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -248,20 +248,20 @@ public class Scheduler { assert data.block != null; assert data.users == 0; - if (data.node instanceof LoadNode l) { + if (data.node instanceof MemOpNode l && l._isLoad) { assert isValid(data); // Handle anti-deps of load nodes. // At this point all anti-dep nodes are scheduled, // but they did not refine the placement // so do that now. - var mem = l.in(1); + var mem = data.node.in(1); for(var out : mem._outputs) { if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { if (p.in(i) == mem) optionalRefinePlacement(data, r.in(i)); } - } else if (!(out instanceof LoadNode)) { + } else if (!(out instanceof MemOpNode ld && ld._isLoad)) { optionalRefinePlacement(data, out); } } @@ -273,11 +273,11 @@ public class Scheduler { for(var in:data.node._inputs) { if (in!=null) update(d(in), data.block); } - if (data.node instanceof StoreNode s) { + if (data.node instanceof MemOpNode s && !s._isLoad) { // 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) od(out).ifPresent(this::decUsers); + for (var out: ((Node)s).in(1)._outputs) { + if (out instanceof MemOpNode ld && ld._isLoad) od(out).ifPresent(this::decUsers); } } } @@ -471,14 +471,14 @@ public class Scheduler { } else { for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false); } - if (node instanceof StoreNode) mem.push(data); + if (node instanceof MemOpNode s && !s._isLoad) mem.push(data); } // Handle store nodes and increase load with an anti-dep to the store. while (!mem.isEmpty()) { var data = mem.pop(); node = data.node; for(var out:node.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); + if (out instanceof MemOpNode ld && ld._isLoad) od(out).ifPresent(d->d.users++); } } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index a2137314..b2be5b5f 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -101,7 +101,7 @@ class FuzzerUtils { System.setErr(NULL_PRINT_STREAM); System.setOut(NULL_PRINT_STREAM); var code = new CodeGen(script, TypeInteger.BOT, workListSeed); - return code.parse().opto().typeCheck().GCM().localSched(); + return code.driver(CodeGen.Phase.LocalSched); } finally { System.setErr(err); System.setOut(out); diff --git a/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp b/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp new file mode 100644 index 00000000..52bfe29b --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp @@ -0,0 +1,11 @@ +// -*- mode: java; -*- +struct S { int f; }; +var v0 = new S; +!S? !v1; +if (arg) v1 = new S; +if (v1) { + v0.f = v1.f; +} else { + v0.f = 2; +} +return v0; diff --git a/src/test/java/com/seaofnodes/simple/progs/arg_count.c b/src/test/java/com/seaofnodes/simple/progs/arg_count.c new file mode 100644 index 00000000..e247e28a --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/arg_count.c @@ -0,0 +1,10 @@ +#include <stdio.h> + +__attribute__ ((CALL_CONV)) +extern double addAll( long long i0, double f1, long long i2, double f3, long long i4, double f5, long long i6, double f7, long long i8, double f9, long long i10, double f11, long long i12, double f13, long long i14, double f15, long long i16, double f17, long long i18, double f19 ); + +int main() { + double result = addAll( 0, 1.1, 2, 3.1, 4, 5.1, 6, 7.1, 8, 9.1, 10, 11.1, 12, 13.1, 14, 15.1, 16, 17.1, 18, 19.1 ); + printf("%f\n", result); + return 0; +} diff --git a/src/test/java/com/seaofnodes/simple/progs/arg_count.smp b/src/test/java/com/seaofnodes/simple/progs/arg_count.smp new file mode 100644 index 00000000..6b6bc0ae --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/arg_count.smp @@ -0,0 +1,6 @@ +// -*- mode: java; -*- +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 ; +}; diff --git a/src/test/java/com/seaofnodes/simple/progs/array1.smp b/src/test/java/com/seaofnodes/simple/progs/array1.smp new file mode 100644 index 00000000..6b10f92c --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/array1.smp @@ -0,0 +1,9 @@ +// -*- mode: java; -*- +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 diff --git a/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c new file mode 100644 index 00000000..127cbe73 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c @@ -0,0 +1,18 @@ +#include <stdio.h> +#include <stdbool.h> + +typedef struct AryInt { + unsigned int len; + unsigned char data[]; +} AryInt; + +__attribute__ ((CALL_CONV)) +extern AryInt* brain_fuck(); + +int main() { + AryInt* ps = brain_fuck(); + + printf("%.*s", ps->len, ps->data); + + return 0; +} diff --git a/src/test/java/com/seaofnodes/simple/progs/brain_fuck.smp b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.smp new file mode 100644 index 00000000..ed90cb84 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.smp @@ -0,0 +1,46 @@ +// -*- mode: java; -*- +val brain_fuck = { -> + u8[] !program = new u8[106];program[0] = 43;program[1] = 43;program[2] = 43;program[3] = 43;program[4] = 43;program[5] = 43;program[6] = 43;program[7] = 43;program[8] = 91;program[9] = 62;program[10] = 43;program[11] = 43;program[12] = 43;program[13] = 43;program[14] = 91;program[15] = 62;program[16] = 43;program[17] = 43;program[18] = 62;program[19] = 43;program[20] = 43;program[21] = 43;program[22] = 62;program[23] = 43;program[24] = 43;program[25] = 43;program[26] = 62;program[27] = 43;program[28] = 60;program[29] = 60;program[30] = 60;program[31] = 60;program[32] = 45;program[33] = 93;program[34] = 62;program[35] = 43;program[36] = 62;program[37] = 43;program[38] = 62;program[39] = 45;program[40] = 62;program[41] = 62;program[42] = 43;program[43] = 91;program[44] = 60;program[45] = 93;program[46] = 60;program[47] = 45;program[48] = 93;program[49] = 62;program[50] = 62;program[51] = 46;program[52] = 62;program[53] = 45;program[54] = 45;program[55] = 45;program[56] = 46;program[57] = 43;program[58] = 43;program[59] = 43;program[60] = 43;program[61] = 43;program[62] = 43;program[63] = 43;program[64] = 46;program[65] = 46;program[66] = 43;program[67] = 43;program[68] = 43;program[69] = 46;program[70] = 62;program[71] = 62;program[72] = 46;program[73] = 60;program[74] = 45;program[75] = 46;program[76] = 60;program[77] = 46;program[78] = 43;program[79] = 43;program[80] = 43;program[81] = 46;program[82] = 45;program[83] = 45;program[84] = 45;program[85] = 45;program[86] = 45;program[87] = 45;program[88] = 46;program[89] = 45;program[90] = 45;program[91] = 45;program[92] = 45;program[93] = 45;program[94] = 45;program[95] = 45;program[96] = 45;program[97] = 46;program[98] = 62;program[99] = 62;program[100] = 43;program[101] = 46;program[102] = 62;program[103] = 43;program[104] = 43;program[105] = 46; + 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; +}; diff --git a/src/test/java/com/seaofnodes/simple/progs/fcn.smp b/src/test/java/com/seaofnodes/simple/progs/fcn.smp deleted file mode 100644 index 43d398b3..00000000 --- a/src/test/java/com/seaofnodes/simple/progs/fcn.smp +++ /dev/null @@ -1,15 +0,0 @@ - -struct Person { - int age; -}; - -val fcn = { !Person?[] ps, int x -> - val tmp = ps[x]; - if( ps[x] ) - ps[x].age++; -}; - -!Person?[] !ps = new !Person?[2]; -ps[0] = new Person; -ps[1] = new Person; -fcn(ps,1); diff --git a/src/test/java/com/seaofnodes/simple/progs/fcn2.smp b/src/test/java/com/seaofnodes/simple/progs/fcn2.smp deleted file mode 100644 index 049132d9..00000000 --- a/src/test/java/com/seaofnodes/simple/progs/fcn2.smp +++ /dev/null @@ -1,5 +0,0 @@ - -val fcn = (arg&1) - ? { int x -> x*x; } - : { int x -> x+x; }; -fcn(arg); diff --git a/src/test/java/com/seaofnodes/simple/progs/fcn3.smp b/src/test/java/com/seaofnodes/simple/progs/fcn3.smp deleted file mode 100644 index 55b74455..00000000 --- a/src/test/java/com/seaofnodes/simple/progs/fcn3.smp +++ /dev/null @@ -1,42 +0,0 @@ - -//val fact = { int n -> n <= 1 ? 1 : fact(n-1)*n; } -struct LL { !LL? !next; int payload; }; - - -struct String { - - val _hashCodeString = { -> - int hash=0; - for( int i=0; i< cs#; i++ ) - hash = hash*31 + cs[i]; - if( !hash ) hash = 123456789; - return hash; - }; - - val equals = { !String s -> - if( self == s ) return true; - if( cs# != s.cs# ) return false; - for( int i=0; i< #; i++ ) - if( [i] != s.cs[i] ) - return false; - return true; - }; - - int _hashCode = hash(); - u8[] cs; -}; - - - -val hashCode= { !String self -> - int hash = self._hashCode - ? self._hashCode - : self._hashCode = _hashCodeString(self); - return hash; -}; - - -String s = new String { cs = new u8[17]; }; -s.cs[0] = 67; // C -s.cs[1] = 108; // l -hashCode(s); diff --git a/src/test/java/com/seaofnodes/simple/progs/fib.c b/src/test/java/com/seaofnodes/simple/progs/fib.c new file mode 100644 index 00000000..263d2f13 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/fib.c @@ -0,0 +1,16 @@ +#include <stdio.h> +#include <stdbool.h> + + +__attribute__ ((CALL_CONV)) +extern int fib(int x); + +int main() { + printf("["); + for (int i = 0; i < 10; i++) { + printf("%d", fib(i)); + if (i < 9) printf(", "); + } + printf("]"); + return 0; +}
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/fib.smp b/src/test/java/com/seaofnodes/simple/progs/fib.smp new file mode 100644 index 00000000..1512541b --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/fib.smp @@ -0,0 +1,11 @@ +// -*- mode: java; -*- +val fib = {int n -> + int f1=1; + int f2=1; + while( n-- > 1 ){ + int temp = f1+f2; + f1=f2; + f2=temp; + } + return f2; +};
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/jig.smp b/src/test/java/com/seaofnodes/simple/progs/jig.smp new file mode 100644 index 00000000..1daeee09 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/jig.smp @@ -0,0 +1,2 @@ +// -*- mode: java; -*- +return 0; diff --git a/src/test/java/com/seaofnodes/simple/progs/loop2.c b/src/test/java/com/seaofnodes/simple/progs/loop2.c new file mode 100644 index 00000000..934f2d89 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/loop2.c @@ -0,0 +1,7 @@ + +__attribute__ ((CALL_CONV)) +extern int loop2(); + +int main() { + return loop2(); +} diff --git a/src/test/java/com/seaofnodes/simple/progs/loop2.smp b/src/test/java/com/seaofnodes/simple/progs/loop2.smp new file mode 100644 index 00000000..01ec827e --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/loop2.smp @@ -0,0 +1,10 @@ +// -*- mode: java; -*- +int i = 0; +while(true) { + i += 1; + if( i==0 ) continue; + if( i==1 ) continue; + if( i==2 ) break; + continue; +} +return i; diff --git a/src/test/java/com/seaofnodes/simple/progs/newtonFloat.c b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.c new file mode 100644 index 00000000..7e7e796d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.c @@ -0,0 +1,16 @@ +#include <stdio.h> +#include <math.h> +#include <stdlib.h> + +extern double test_sqrt(double); + +int main( int argc, char** argv ) { + for( int i=0; i<10; i++ ) { + double d = test_sqrt((double)i), expect = sqrt((double)i); + double delta = fabs(d-expect); + printf("%d %f (%g)\n",i,d,delta); + if( delta > 1e-15 ) + return 1; + } + return 0; +} diff --git a/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp new file mode 100644 index 00000000..be2dffec --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp @@ -0,0 +1,12 @@ +// -*- mode: java; -*- +// Newtons approximation to the square root +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; + } +}; diff --git a/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp b/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp new file mode 100644 index 00000000..20a05445 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp @@ -0,0 +1,6 @@ +// -*- mode: java; -*- +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 -> + return + i0 + f1+ i2+ f3+ i4+ f5+ i6+ f7+ x8 +f9 + + i10+f11+i12+f13+i14+f15; +}; diff --git a/src/test/java/com/seaofnodes/simple/progs/person.c b/src/test/java/com/seaofnodes/simple/progs/person.c new file mode 100644 index 00000000..df95e1ca --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/person.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/src/test/java/com/seaofnodes/simple/progs/person.smp b/src/test/java/com/seaofnodes/simple/progs/person.smp new file mode 100644 index 00000000..b5e6ee90 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/person.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/src/test/java/com/seaofnodes/simple/progs/sieve.c b/src/test/java/com/seaofnodes/simple/progs/sieve.c new file mode 100644 index 00000000..cac4cfa3 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/sieve.c @@ -0,0 +1,19 @@ +#include <stdio.h> +#include <stdbool.h> + +typedef struct AryInt { + unsigned int len; + unsigned int data[]; +} AryInt; + +__attribute__ ((CALL_CONV)) +extern AryInt *sieve(int N); + +int main() { + AryInt* ps = sieve(100); + printf("%d[",ps->len); + for( int i=0; i<ps->len; i++ ) + printf("%d, ",ps->data[i]); + printf("]"); + return 0; +} diff --git a/src/test/java/com/seaofnodes/simple/progs/sieve.smp b/src/test/java/com/seaofnodes/simple/progs/sieve.smp index 0788e6c5..569dbb96 100644 --- a/src/test/java/com/seaofnodes/simple/progs/sieve.smp +++ b/src/test/java/com/seaofnodes/simple/progs/sieve.smp @@ -1,32 +1,31 @@ - -int[] !ary = new int[arg], !primes = new int[arg]; -int nprimes = 0, p=2; -// Find primes while p^2 < arg -while( p*p < arg ) { - // skip marked non-primes - while( ary[p]==1 ) p = p + 1; - // p is now a prime - primes[nprimes] = p; nprimes = nprimes + 1; - // Mark out the rest non-primes - int i = p + p; - while( i < ary# ) { - ary[i] = 1; - i = i + p; - } - p = p + 1; -} -// Now just collect the remaining primes, no more marking -while( p < arg ) { - if( ary[p] == 0 ) { - primes[nprimes] = p; nprimes = nprimes + 1; +// -*- mode: java; -*- +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++; } - p = p + 1; -} -// Copy/shrink the result array -int[] !rez = new int[nprimes]; -int j = 0; -while( j < nprimes ) { - rez[j] = primes[j]; - j = j + 1; -} -return rez; + + // 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; +}; diff --git a/src/test/java/com/seaofnodes/simple/progs/sort.c b/src/test/java/com/seaofnodes/simple/progs/sort.c new file mode 100644 index 00000000..ad76cc7f --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/sort.c @@ -0,0 +1,28 @@ +#include <stdio.h> +#include <stdlib.h> + +// Test wrapper to call `sort.smp` + +typedef struct AryInt { + unsigned int len; + long long data[]; +} AryInt; + +__attribute__ ((CALL_CONV)) +extern AryInt* merge_sort(AryInt*); + + +long long primes[] = { 25, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2 }; + +int main() { + AryInt *as = (AryInt*)primes; + + merge_sort(as); + + printf("%d[",as->len); + for( int i=0; i<as->len; i++ ) + printf("%d, ",as->data[i]); + printf("]"); + + return 0; +}
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/sort.smp b/src/test/java/com/seaofnodes/simple/progs/sort.smp new file mode 100644 index 00000000..ae3f4f23 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/sort.smp @@ -0,0 +1,38 @@ +// -*- mode: java; -*- +// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort + +val merge_sort = { int[] a -> + int[] !b = new int[a#]; + copy_array (a, 0, a#, b); + split_merge(a, 0, a#, 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]; +}; diff --git a/src/test/java/com/seaofnodes/simple/progs/stringHash.c b/src/test/java/com/seaofnodes/simple/progs/stringHash.c new file mode 100644 index 00000000..2c6d0fa9 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/stringHash.c @@ -0,0 +1,30 @@ +#include <stdio.h> +#include <stdbool.h> + +typedef struct ArrayU8 { + unsigned int length; + unsigned char data[]; +} ArrayU8; +typedef struct String { + ArrayU8 * cs; + long long _hashCode; +} String; + + +__attribute__ ((CALL_CONV)) +extern bool equals(String*st1, String*st2); + +int main() { + String test1 = {.cs=(ArrayU8*)"\x04\x00\x00\x00test"}; + String test2 = {.cs=(ArrayU8*)"\x05\x00\x00\x00test1"}; + + if( equals(&test1, &test2) ) { + printf("Expected test1 and test2 unequal"); + return 1; + } + if( !equals(&test2, &test2) ) { + printf("Expected test2 and test2 equal"); + return 1; + } + return 0; +} diff --git a/src/test/java/com/seaofnodes/simple/progs/stringHash.smp b/src/test/java/com/seaofnodes/simple/progs/stringHash.smp new file mode 100644 index 00000000..257f79f9 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/stringHash.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; +}; |