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 +- .../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 +++++++++++++++++++++ 8 files changed, 289 insertions(+), 15 deletions(-) create mode 100644 chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java (limited to 'chapter23/src/test/java') diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 8ce02220..15addc7b 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/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 com.seaofnodes.simple.print.ASMPrinter; @@ -29,6 +31,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(); } @@ -43,7 +53,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; @@ -88,7 +98,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/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index db8e398a..9e73a9c0 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/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. @@ -64,7 +113,7 @@ public class Chapter21Test { } 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 ) @@ -163,11 +212,11 @@ public class Chapter21Test { 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, 257); + TestC.run("sieve",sprimes, 186); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. - EvalRisc5 R5 = TestRisc5.build("sieve", 100, 160, false); + EvalRisc5 R5 = TestRisc5.build("sieve", 100, 92, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) @@ -179,7 +228,7 @@ public class Chapter21Test { // Evaluate on ARM5 emulator; expect return of an array of primes in // the simulated heap. - EvalArm64 A5 = TestArm64.build("sieve", 100, 160, false); + EvalArm64 A5 = TestArm64.build("sieve", 100, 94, false); int trap_arm = A5.step(10000); assertEquals(0, trap_arm); int ary_arm = (int)A5.regs[arm.X0]; @@ -258,7 +307,7 @@ public class Chapter21Test { // 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") ? 42 : 15); + TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", 0, 0, false); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java index f6410b6a..d6f31ff6 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter23/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; @@ -23,7 +24,7 @@ public class Chapter22Test { } 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/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 45acc62a..4bb8ded0 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter23/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 @@ var apply = { i64 x, { i64 -> u32 } fcn -> } 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/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java index 5d7d1361..38fd2a85 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter23/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; @@ -21,7 +23,7 @@ public class TestArm64 { 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); + 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/chapter23/src/test/java/com/seaofnodes/simple/TestC.java b/chapter23/src/test/java/com/seaofnodes/simple/TestC.java index dbe9f02f..6edde562 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter23/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; @@ -58,7 +59,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); @@ -113,10 +114,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/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java index 041ed833..cb1c95e9 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter23/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; @@ -20,7 +21,7 @@ public abstract class TestRisc5 { 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); + 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/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..b2d14a02 --- /dev/null +++ b/chapter23/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