diff options
Diffstat (limited to 'chapter25/src/test/java/com')
9 files changed, 243 insertions, 10 deletions
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 20619c1b..647b253e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; @@ -23,6 +25,14 @@ return f(s); } + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } + @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } + @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } + @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } + @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } + @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } + @Test public void testPrintingRegisters() throws Exception { com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); } @@ -37,7 +47,7 @@ return f(s); } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src); + CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; @@ -102,7 +112,7 @@ val _test_sqrt_noInline = { flt x -> }; flt farg = arg; return _test_sqrt_noInline(farg) + _test_sqrt_noInline(farg+2.0); """; - testCPU(src,"x86_64_v2", "SystemV",48,null); + testCPU(src,"x86_64_v2", "SystemV",40,null); testCPU(src,"riscv" , "SystemV",17,null); testCPU(src,"arm" , "SystemV",18,null); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index e8a9e700..e194829a 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -9,6 +10,8 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } + @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. @@ -79,7 +82,7 @@ return new _s0.v1; } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) @@ -447,7 +450,7 @@ val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, i """; String arg_count = "191.000000\n"; - TestC.runC(src, "arg_count", arg_count, TestC.CALL_CONVENTION.equals("win64") ? 31 : 15); + TestC.runC(src, "arg_count", arg_count, TestC.CALL_CONVENTION.equals("win64") ? 35 : 15); EvalRisc5 R5 = TestRisc5.build( src, "addAll", 0, 4, false); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 96e7fce7..fde523cf 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -37,7 +38,7 @@ return new s0.v1; } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 0e6398ee..923395bf 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -1,4 +1,6 @@ package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -47,7 +49,7 @@ public class Chapter23Test { static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 1307d2ce..0abdfb3e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -1,4 +1,6 @@ package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -37,7 +39,7 @@ public class Chapter24Test { } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java index 14864d64..d2c6cde4 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -14,7 +15,7 @@ public class TestArm64 { public static EvalArm64 build( String main, String src, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("arm", "SystemV",true,false); + CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",true,false); // Allocation quality not degraded int delta = spills>>3; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java index 55c62c37..e0ee701a 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; @@ -118,7 +119,7 @@ public abstract class TestC { String obj = pathBase+".o"; String exe = pathBase+(OS.startsWith("Windows") ? ".exe" : ""); // Compile simple, emit ELF - CodeGen code = new CodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT); + CodeGen code = new CheckedCodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT); code.driver( CPU_PORT, simple_conv, false, cfile==null ); linkExe(obj, c_conv, cfile, linkObjs(externPaths), exe); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java index 658909ca..1de5e3bc 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.node.FunNode; @@ -14,7 +15,7 @@ public abstract class TestRisc5 { public static EvalRisc5 build( String src, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("riscv", "SystemV",true,false); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",true,false); // Allocation quality not degraded int delta = spills>>3; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..5e1b276e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,212 @@ +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 static org.junit.Assert.*; + +// Small scheduled machine graphs isolate register constraints from peepholes. +public class RegAllocTestSupport { + private static final RegMask A = new RegMask(0), B = new RegMask(1); + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + final boolean _clone; + Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT; + } + @Override public String op() { return "testOp"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @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 void encoding(Encoding enc) { throw new AssertionError(); } + } + private static CodeGen graph() { + CodeGen code = new CodeGen(""); + code._mach = new x86_64_v2(code); + code._cfg.add(code._start); + return code; + } + + public static void masks() { + for( int reg : new int[]{0,63,64,65,127} ) { + RegMask mask = new RegMask(reg); + assertEquals(reg,mask.firstReg()); + assertEquals(1,mask.size()); + } + assertEquals(-1,new RegMask(0L).firstReg()); + assertFalse(new RegMask(0L).size1()); + RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1); + assertEquals(64,boundary.nextReg((short)63)); + assertEquals(127,boundary.nextReg((short)64)); + assertEquals(-1,boundary.nextReg((short)127)); + } + + public static void union() { + CodeGen code = graph(); + Op use = new Op(null,B,null,false,code._start); + LRG a = new LRG((short)1,null), b = new LRG((short)2,null); + a._mask = new RegMask(3L); + b._mask = new RegMask(6L); + b.machUse(use,(short)2,true); + LRG both = a.union(b); + assertNotNull(both._mask); + assertEquals(1,both._mask.firstReg()); + assertEquals(1,both._mask.size()); + assertSame(use,both._machUse); + assertEquals(2,both._uidx); + } + + public static void killWithoutResult() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,A,false,code._start); // Clobbers A, produces no value. + new Op(null,A,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + } + + public static void nullUseMask() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,null,false,code._start,def); // Scheduling dependency only. + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertTrue(IFG.build(0,alloc)); + } + + public static void cloneRegisterClass() { + for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) { + CodeGen code = graph(); + Op def = new Op(A,null,null,true,code._start); + Op use = new Op(null,required,null,false,code._start,def); + Op use2 = new Op(null,required,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses. + assertEquals(0,alloc.regnum(def)); + assertTrue(required.test(alloc.regnum(use.in(1)))); + assertTrue(required.test(alloc.regnum(use2.in(1)))); + assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void commutativePhi() { + CodeGen code = graph(); + Op a = new Op(A,null,null,false,code._start); + Op b = new Op(A,null,null,false,code._start); + Op add = new Op(A,A,null,false,code._start,a,b) { + @Override public boolean commutes() { return true; } + }; + RegionNode region = new RegionNode(null,code._start,code._start); + new PhiNode("sum",region,add,a); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,new RegAlloc(code))); + } + + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. + public static class CheckedCodeGen extends CodeGen { + public CheckedCodeGen(String src) { super(src); } + public CheckedCodeGen(String modDir, String buildDir, com.seaofnodes.simple.util.Ary<String> externPaths, + String srcName, String src, long seed, boolean reset, TypeInteger arg) { + super(modDir,buildDir,externPaths,srcName,src,seed,reset,arg); + } + @Override public CodeGen regAlloc() { + super.regAlloc(); + checkRegisters(this); + return this; + } + } + + public static void checkRegisters(CodeGen code) { + assertTrue(code._regAlloc.verifyFunctionLocalEdges()); + for( CFGNode bb : code._cfg ) + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach ) { + if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n))); + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i)))); + if( mach.twoAddress()!=0 ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress()))); + } + if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + } + } + + public static void copyClobber() throws Exception { + for( boolean killed : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def,null)._reg=0; + SplitNode hi = code._mach.split(null,"test",(byte)0); + hi.setDef(0,code._start); hi.setDef(1,def); + alloc.newLRG(hi,null)._reg=1; + new Op(null,null,killed ? A : null,false,code._start); + SplitNode lo = code._mach.split(null,"test",(byte)0); + lo.setDef(0,code._start); lo.setDef(1,hi); + alloc.newLRG(lo,null)._reg=0; + Op use = new Op(null,A,null,false,code._start,lo); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame(killed ? lo : def,use.in(1)); + } + CodeGen pre = graph(); + RegAlloc uncolored = new RegAlloc(pre); + Op def0 = new Op(A,null,null,false,pre._start); + uncolored.newLRG(def0,null)._mask=A; + Op fixed = new Op(A,null,null,false,pre._start); + uncolored.newLRG(fixed,null)._mask=A; + SplitNode copy = pre._mach.split(null,"test",(byte)0); + copy.setDef(0,pre._start); copy.setDef(1,def0); + assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); + } + + 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(null,"test",(byte)0); + 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,null), to = alloc.newLRG(copy,null); + 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,null), right = new LRG((short)101,null); + 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()); + } + } + } + +} |