From 892deaa10d8d2bae0e839bb42e4c2ce830eaff39 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 7 Feb 2025 09:12:14 -0800 Subject: Chapter 20: Graph Coloring Register Allocation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: RobertObkircher --- .../java/com/seaofnodes/simple/BrainFuckTest.java | 14 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 1 + .../java/com/seaofnodes/simple/Chapter02Test.java | 1 + .../java/com/seaofnodes/simple/Chapter03Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 1 + .../java/com/seaofnodes/simple/Chapter05Test.java | 1 + .../java/com/seaofnodes/simple/Chapter06Test.java | 1 + .../java/com/seaofnodes/simple/Chapter07Test.java | 1 + .../java/com/seaofnodes/simple/Chapter08Test.java | 1 + .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 1 + .../java/com/seaofnodes/simple/Chapter11Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 1 + .../java/com/seaofnodes/simple/Chapter14Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 13 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 1 + .../java/com/seaofnodes/simple/Chapter17Test.java | 7 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 13 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 121 +++++-------- .../java/com/seaofnodes/simple/Chapter20Test.java | 196 +++++++++++++++++++++ src/test/java/com/seaofnodes/simple/Eval2.java | 4 +- src/test/java/com/seaofnodes/simple/Main.java | 2 + .../java/com/seaofnodes/simple/MergeSortTest.java | 12 +- .../java/com/seaofnodes/simple/SchedulerTest.java | 1 + .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 2 +- .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 2 +- 27 files changed, 299 insertions(+), 114 deletions(-) create mode 100644 src/test/java/com/seaofnodes/simple/Chapter20Test.java (limited to 'src/test/java') diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 8f09cb3d..c23bb301 100644 --- a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -1,10 +1,11 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.codegen.CodeGen; import java.nio.charset.StandardCharsets; 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 { @@ -17,8 +18,7 @@ public class BrainFuckTest { encoded.append("program[").append(i).append("] = ").append(value).append(";"); } - CodeGen code = new CodeGen( - encoded + """ + String src = encoded + """ int d = 0; u8[] !output = new u8[0]; @@ -62,8 +62,10 @@ for( int pc = 0; pc < program#; pc++ ) { } } return output; - """); - code.parse().opto().typeCheck()/*.instSelect("x86_64_v2", "SystemV")*/.GCM().localSched(); - assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); +"""; + 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)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 934eda76..cddbdfcf 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index d8607c32..631e1487 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 4f9b2490..c4e4c91e 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; - import static org.junit.Assert.*; public class Chapter03Test { diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index d09b1748..c6199193 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 86ec4136..a584ad5a 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 117531f0..24d12921 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 6d6a3ce7..88554323 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 350df18b..7e90d484 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import org.junit.Assert; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 10f4a78b..401f346f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 02029b3f..1253e4a6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 0b24bd5d..c2b9a86d 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,8 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; - - import static org.junit.Assert.assertEquals; public class Chapter11Test { diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 21df8205..8069ddaa 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,8 +1,7 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.StopNode; -import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -43,7 +42,7 @@ while( 1 ) { return guess; """); code.parse().opto(); - assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0f));", code.print()); + assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print()); assertEquals("3.0", Eval2.eval(code, 9)); assertEquals("1.414213562373095", Eval2.eval(code, 2)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 005a3dd4..977595cb 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 17708c37..b83516e3 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; - import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -174,7 +174,7 @@ while(v1) break; return v1; """); code.parse().opto(); - assertEquals("return Phi(Loop,(((1< return sq(arg)+sq(3); """); code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("Stop[ return (sq( 3)+sq( arg)); return (Parm_x(sq,int,3,arg)*x); ]", code._stop.toString()); + assertEquals("Stop[ return (#2+#2); return (Parm_x(sq,int)*x); ]", code._stop.toString()); assertEquals("13", Eval2.eval(code, 2)); } @@ -115,7 +116,7 @@ var fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(3); """); code.parse().opto(); - assertEquals("Stop[ return Phi(Region,{ int -> int #1},{ int -> int #2})( 3); return (Parm_x($fun,int,3)*x); return (Parm_x($fun,int,3)<<1); ]", code._stop.toString()); + assertEquals("Stop[ return #2; return (Parm_x($fun1,int,3)*x); return (Parm_x($fun2,int,3)<<1); ]", code._stop.toString()); assertEquals("6", Eval2.eval(code, 0)); assertEquals("9", Eval2.eval(code, 1)); } @@ -125,7 +126,7 @@ return fcn(3); public void testFcn5() { CodeGen code = new CodeGen("val fact = { int x -> x <= 1 ? 1 : x*fact(x-1); }; return fact(arg);"); code.parse().opto().typeCheck(); - assertEquals("Stop[ return fact( arg); return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*fact( Sub))); ]", code._stop.toString()); + assertEquals("Stop[ return #2; return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*#2)); ]", code._stop.toString()); assertEquals( "1", Eval2.eval(code, 0)); assertEquals( "1", Eval2.eval(code, 1)); assertEquals( "2", Eval2.eval(code, 2)); @@ -175,7 +176,7 @@ for(;;) { } """); code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("Stop[ return x( Phi(Loop,arg,x( 3))); return Parm_i(x,int,3,Phi_arg); ]", code._stop.toString()); + assertEquals("Stop[ return #2; return Parm_i(x,int); ]", code._stop.toString()); assertEquals("3", Eval2.eval(code, 0)); } @@ -346,7 +347,7 @@ if (i2i) return i2i(arg); return f2f(o)(1); """); code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("Stop[ return Phi(Region,o( arg),o( 1)); return Parm_i(o,int,arg,1); ]", code._stop.toString()); + assertEquals("Stop[ return Phi(Region,#2,#2); return Parm_i(o,int); ]", 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 990c4c32..bb7e8716 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -1,9 +1,11 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; +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; -import org.junit.Ignore; public class Chapter19Test { @@ -55,107 +57,107 @@ val _hashCodeString = { String self -> String !s = new String { cs = new u8[17]; }; s.cs[0] = 67; // C s.cs[1] = 108; // l -hashCode(s);"""); +hashCode(s)+hashCode(s);"""); code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("Stop[ return Phi(Region,123456789,Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return Phi(Region,1,0,0,1); ]", code._stop.toString()); - assertEquals("-2449306563677080489", Eval2.eval(code, 2)); + 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)); } @Test public void testBasic0() { - CodeGen code = new CodeGen("return 0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return 0;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return 0;", code._stop.toString()); } @Test public void testBasic1() { - CodeGen code = new CodeGen("return arg+1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg+1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (inc,arg);", code._stop.toString()); } @Test public void testBasic2() { - CodeGen code = new CodeGen("return -17;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return -17;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return -17;", code._stop.toString()); } @Test public void testBasic3() { - CodeGen code = new CodeGen("return arg==1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg==1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (set==,(cmp,arg));", code._stop.toString()); } @Test public void testBasic4() { - CodeGen code = new CodeGen("return arg<<1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg<<1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (shli,arg);", code._stop.toString()); } @Test public void testBasic5() { - CodeGen code = new CodeGen("return arg >> 1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg >> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (sari,arg);", code._stop.toString()); } @Test public void testBasic6() { - CodeGen code = new CodeGen("return arg >>> 1;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg >>> 1;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (shri,arg);", code._stop.toString()); } @Test public void testBasic7() { - CodeGen code = new CodeGen("return arg / 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg / 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (div,arg,2);", code._stop.toString()); } @Test public void testBasic8() { - CodeGen code = new CodeGen("return arg * 6;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg * 6;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (muli,arg);", code._stop.toString()); } @Test public void testBasic9() { - CodeGen code = new CodeGen("return arg & 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg & 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (andi,arg);", code._stop.toString()); } @Test public void testBasic10() { - CodeGen code = new CodeGen("return arg | 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg | 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (ori,arg);", code._stop.toString()); } @Test public void testBasic11() { - CodeGen code = new CodeGen("return arg ^ 2;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + CodeGen code = new CodeGen("return arg ^ 2;").parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (xori,arg);", code._stop.toString()); } @Test public void testBasic12() { - CodeGen code = new CodeGen("return arg + 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + 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()); } @Test public void testBasic13() { - CodeGen code = new CodeGen("return arg - 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + 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()); } @Test public void testBasic14() { - CodeGen code = new CodeGen("return arg * 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + 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()); } @Test public void testBasic15() { - CodeGen code = new CodeGen("return arg / 2.0;").parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (divf,(i2f8,arg),2.0f);", code._stop.toString()); + 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()); } @Test @@ -164,7 +166,7 @@ hashCode(s);"""); """ int arg1 = arg + 1; return arg1 / arg;"""); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (div,(inc,arg),arg);", code._stop.toString()); } @@ -175,50 +177,17 @@ return arg1 / arg;"""); int arg1 = arg + 1; return arg1 * arg; """); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (mul,(inc,arg),arg);", code._stop.toString()); } - @Test - public void testBasic18() { - CodeGen code = new CodeGen( - """ - int arg1 = arg + 1; - return arg1 << arg; - """); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (shl,(inc,arg),arg);", code._stop.toString()); - } - - @Test - public void testBasic19() { - CodeGen code = new CodeGen( - """ - int arg1 = arg + 1; - return arg1 >> arg; - """); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (sar,(inc,arg),arg);", code._stop.toString()); - } - - @Test - public void testBasic20() { - CodeGen code = new CodeGen( - """ - int arg1 = arg + 1; - return arg1 >>> arg; - """); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return (shr,(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("x86_64_v2", "SystemV").GCM().localSched(); + ).parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (addf,(i2f8,arg),2.0f);", code._stop.toString()); } @@ -233,7 +202,7 @@ else { a = arg-3; } return a;"""); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return Phi(Region,(addi,arg),(addi,arg));", code.print()); } @@ -248,7 +217,7 @@ if( arg==1 ) else a=b+1; return a+b;"""); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); assertEquals("return (add,(add,Phi(Region,(shli,arg),arg),arg),Phi(Region,4,5));", code.print()); } @@ -260,7 +229,7 @@ int sum=0; for( int i=0; i flt farg = arg; return sqrt(farg); """); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("return Phi(Loop,(i2f8,arg),(divf,(addf,(divf,i2f8,Phi_guess),Phi_guess),2.0f));", code.print()); + 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()); }; @@ -401,7 +370,7 @@ for( int j=0; j x*x; } : { int x -> x+x; }; return fcn(2)*10 + fcn(3); """); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("Stop[ return (add,Phi(Region,{ int -> int #1},{ int -> int #2})( 3),(muli,Phi_( 2))); return (mul,Parm_x($fun,int,3,2),x); return (shli,Parm_x($fun,int,3,2)); ]", code.print()); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun1,int),x); return (shli,Parm_x($fun2,int)); ]", code.print()); } @Test @@ -425,7 +394,7 @@ return fcn(2)*10 + fcn(3); val sq = { int x -> x*x; }; return sq(arg) + sq(3); """); - code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); - assertEquals("Stop[ return (add,sq(),sq()); return (mul,Parm_x(sq,int,3,arg),x); ]", code.print()); + code.parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("Stop[ return (add,#2,#2); return (mul,Parm_x(sq,int),x); ]", code.print()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/src/test/java/com/seaofnodes/simple/Chapter20Test.java new file mode 100644 index 00000000..008f5e0c --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -0,0 +1,196 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +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 testJig() { + CodeGen code = new CodeGen("return 0;"); + code.parse().opto().typeCheck(); + assertEquals("return 0;", code._stop.toString()); + assertEquals("0", Eval2.eval(code, 2)); + } + + 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(); + int delta = spills>>3; + if( delta==0 ) delta = 1; + assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + if( stop != null ) + assertEquals(stop, code._stop.toString()); + } + + private static void testAllCPUs( String src, int spills, String stop ) { + testCPU(src,"x86_64_v2", "SystemV",spills,stop); + testCPU(src,"riscv" , "SystemV",spills,stop); + testCPU(src,"arm" , "SystemV",spills,stop); + } + + @Test public void testAlloc0() { + testAllCPUs("return new u8[arg];", 1, "return [u8];"); + } + + @Test public void testBasic1() { + String src = "return arg | 2;"; + testCPU(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); + testCPU(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); + testCPU(src,"arm" , "SystemV",0,"return (ori,arg);"); + } + + @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); +"""; + testCPU(src,"x86_64_v2", "SystemV",26,null); + testCPU(src,"riscv" , "SystemV",19,null); + testCPU(src,"arm" , "SystemV",26,null); + } + + @Test + public void testNewtonFloat() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { flt x -> + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +flt farg = arg; +return sqrt(farg) + sqrt(farg+2.0); +"""; + testCPU(src,"x86_64_v2", "SystemV",25,null); + testCPU(src,"riscv" , "SystemV",21,null); + testCPU(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 .[];"); + } + + @Test + public void testArray1() { + String src = +""" +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +for( int i=0; i + 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); +"""; + testCPU(src,"x86_64_v2", "SystemV",18,null); + testCPU(src,"riscv" , "SystemV", 3,null); + testCPU(src,"arm" , "SystemV", 3,null); + } + + @Test + public void testCast() { + String src = "struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1;"; + testAllCPUs(src,0,null); + } + + @Test + public void testFltArg() { + String src = "return {int i, flt f, int j->return i+f+j;};"; + testAllCPUs(src,0,null); + } + + @Test + public void testFlags1() { + String src = """ +bool b1 = arg == 1; +bool b2 = arg == 2; +if (b2) if (b1) return 1; +if (b1) return 2; +return 0; +"""; + testCPU(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); + testCPU(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); + testCPU(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); + } + + @Test + public void testFlags2() { + String src = """ +bool b1 = arg == 1; +while (arg > 0) { + arg--; + if (b1) arg--; +} +return arg; +"""; + testCPU(src,"x86_64_v2", "SystemV",3,null); + testCPU(src,"riscv" , "SystemV",2,null); + testCPU(src,"arm" , "SystemV",2,null); + } +} diff --git a/src/test/java/com/seaofnodes/simple/Eval2.java b/src/test/java/com/seaofnodes/simple/Eval2.java index 6ae8427c..ecea97dd 100644 --- a/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/src/test/java/com/seaofnodes/simple/Eval2.java @@ -1,7 +1,9 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.print.IRPrinter; +import com.seaofnodes.simple.type.*; import java.util.*; public abstract class Eval2 { diff --git a/src/test/java/com/seaofnodes/simple/Main.java b/src/test/java/com/seaofnodes/simple/Main.java index 523bd306..f3a6784c 100644 --- a/src/test/java/com/seaofnodes/simple/Main.java +++ b/src/test/java/com/seaofnodes/simple/Main.java @@ -1,9 +1,11 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; 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/MergeSortTest.java b/src/test/java/com/seaofnodes/simple/MergeSortTest.java index d48449d5..c83fe089 100644 --- a/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -8,7 +9,7 @@ public class MergeSortTest { @Test public void testMergeSort() { - CodeGen code = new CodeGen( + String src = """ // based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort @@ -56,10 +57,11 @@ for (int i = 0; i < a#; i++) merge_sort(a, b, a#); return a; -"""); - code.parse().opto(); - assertEquals("Stop[ return [int]; return 0; ]", code._stop.toString()); - assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); +"""; + 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)); } } diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java index d50c302a..ca29bf84 100644 --- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Assert; diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index f7e0c4ad..30a548ad 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -2,7 +2,7 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Eval2; -import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.util.Objects; diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index 0781ad67..669a1e6a 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.fuzzer; -import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import com.seaofnodes.simple.type.TypeInteger; -- cgit v1.2.3