From c1d8d90f5246a41e42189ffbfcde017873bf5b72 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 20 Sep 2026 16:23:20 -0700 Subject: Forward-port allocator bug fixes and test support through ch25 Improved spilling --- .../java/com/seaofnodes/simple/Chapter20Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 59 +++++- .../java/com/seaofnodes/simple/Chapter22Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter24Test.java | 4 +- .../test/java/com/seaofnodes/simple/TestArm64.java | 4 +- .../src/test/java/com/seaofnodes/simple/TestC.java | 8 +- .../test/java/com/seaofnodes/simple/TestRisc5.java | 3 +- .../simple/codegen/RegAllocTestSupport.java | 209 +++++++++++++++++++++ 9 files changed, 292 insertions(+), 16 deletions(-) create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java (limited to 'chapter24/src/test/java/com/seaofnodes') diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 760344ec..e668f90d 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/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 java.io.IOException; @@ -24,6 +26,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(); } @@ -38,7 +48,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; @@ -83,7 +93,7 @@ val sqrt = { int x -> int cast_int = arg+2; return sqrt(arg) + sqrt(cast_int); """; - testCPU(src,"x86_64_v2", "Win64" ,55,null); + testCPU(src,"x86_64_v2", "Win64" ,48,null); testCPU(src,"riscv" , "SystemV",19,null); testCPU(src,"arm" , "SystemV",19,null); } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 38029ee8..49c95fb8 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter24/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; @@ -12,6 +13,54 @@ 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 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 testNativeExitStatus() throws IOException { + Path source = Path.of("build/objs/nativeExit.c"); + Files.createDirectories(source.getParent()); + Files.writeString(source,"int main() { return 7; }\n"); + try { + TestC.gcc(source.toString(),null,null,false, + "build/objs/nativeExit"+(TestC.OS.startsWith("Windows") ? ".exe" : "")); + } catch( AssertionError error ) { + assertTrue(error.getMessage(),error.getMessage().contains("Program exit status")); + return; + } + fail("A failing native program must fail the test, even with empty stdout"); + } + @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. @@ -82,7 +131,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 ) @@ -323,11 +372,11 @@ val sieve = { int N -> String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - TestC.run(src, "sieve", null, sprimes, 257); + TestC.run(src, "sieve", null, sprimes, 186); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. - EvalRisc5 R5 = TestRisc5.build("sieve", src, 100, 160, false); + EvalRisc5 R5 = TestRisc5.build("sieve", src, 100, 92, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) @@ -339,7 +388,7 @@ val sieve = { int N -> // Evaluate on ARM5 emulator; expect return of an array of primes in // the simulated heap. - EvalArm64 A5 = TestArm64.build("sieve", src, 100, 160, false); + EvalArm64 A5 = TestArm64.build("sieve", src, 100, 94, false); int trap_arm = A5.step(10000); assertEquals(0, trap_arm); int ary_arm = (int)A5.regs[arm.X0]; @@ -450,7 +499,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.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 42 : 15); + TestC.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", src, 0, 4, false); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 78b9e7a1..fa9036d2 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter24/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.codegen.CodeGen; import java.io.IOException; import java.nio.file.Files; @@ -39,7 +40,7 @@ fib(10); } 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 ) diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 56a672aa..661d4f39 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter24/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.*; @@ -90,7 +92,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 ) diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index a4fb5829..a1dd6eaa 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/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 ) diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java index a1c02ede..d0fdae0c 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -1,5 +1,7 @@ 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; @@ -27,7 +29,7 @@ public class TestArm64 { // Compile and run a simple program public static EvalArm64 build( String dir, String src, String file, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("arm", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java b/chapter24/src/test/java/com/seaofnodes/simple/TestC.java index f1831929..aed9f844 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter24/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; @@ -75,7 +76,7 @@ public abstract class TestC { String obj = bin+".o"; String exe = OS.startsWith("Windows") ? bin+".exe" : bin; // Compile simple, emit ELF - CodeGen code = new CodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); + CodeGen code = new CheckedCodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); String result = gcc(obj, c_conv, cfile, false, exe ); assertEquals(expected,result); @@ -130,10 +131,9 @@ public abstract class TestC { ProcessBuilder smp = new ProcessBuilder(args); if( stdin ) smp.redirectInput(ProcessBuilder.Redirect.INHERIT); Process p = smp.start(); - try { exit = (byte)p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + try { exit = p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } result = new String(p.getInputStream().readAllBytes()); - if( exit!=0 ) - System.err.println("exec exit code: "+exit); + assertEquals("Program exit status",0,exit); return result; } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java index a8f6817e..72a05c61 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter24/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.node.FunNode; import com.seaofnodes.simple.node.Node; @@ -26,7 +27,7 @@ public abstract class TestRisc5 { // Compile and run a simple program public static EvalRisc5 build( String dir, String src, String file, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("riscv", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..b2d14a02 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,209 @@ +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), b = new LRG((short)2); + 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",TypeInteger.BOT,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 src, TypeInteger arg) { super(src,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=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=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()); + } + } + } + +} -- cgit v1.2.3