From 6a5d13d459e40d242bea43f87a4717ad4fcf9e48 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 20 Sep 2026 17:27:00 -0700 Subject: Popular use grouping for RegAlloc Fix arm BL encodings; ADD/SUB with reversed sign. --- .../java/com/seaofnodes/simple/Chapter21Test.java | 112 +++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter23Test.java | 2 + .../test/java/com/seaofnodes/simple/EvalArm64.java | 25 ++--- .../simple/codegen/RegAllocTestSupport.java | 42 ++++++++ 4 files changed, 169 insertions(+), 12 deletions(-) (limited to 'chapter24/src/test') diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 49c95fb8..3910b7a5 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -13,6 +13,118 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @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); + } + + @Test public void testArmVectorGrowth() throws IOException { + String src = """ + struct _Vec { + u32 !len; + int[] !buf; + val grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i + if( len>=buf# ) grow(buf#*2); + buf[len++]=e; + return self; + }; + }; + val run = { int arg -> + val v = new _Vec{buf=new int[4];}.add(2).add(3).add(5).add(7).add(11); + return v.len*100+v.buf[arg]; + }; + """; + checkArmCalls(src,"run",4,511); + } + + 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 testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } @Test public void testNarrowStores() throws IOException { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 661d4f39..23c88613 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -16,6 +16,8 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter23Test { + @Test public void testPopularUses() { com.seaofnodes.simple.codegen.RegAllocTestSupport.popularUses(); } + @Test public void testDiagnosticTypeAccessors() throws Exception { new CodeGen("return 0;").parse(); var tfp = TypeFunPtr.TEST; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java index ad1fb785..5557de3c 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -306,11 +306,11 @@ public class EvalArm64 { break; } - case 0x91: { // add(immediate) + case 0x91, 0xD1: { // ADD/SUB (immediate), unsigned imm12, optional LSL #12 int rn = (ir >> 5) & 0x1F; - int immediate = ir << 10 >> 20; - // only hit it twice - rval = regs[rn] + immediate; + long immediate = (ir >>> 10) & 0xFFF; + if( (ir & (1<<22))!=0 ) immediate <<= 12; + rval = opcode1==0x91 ? regs[rn] + immediate : regs[rn] - immediate; break; } case 0x92: { // and(immediate) @@ -329,6 +329,7 @@ public class EvalArm64 { } case 0x94, 0x95, 0x96, 0x97: { // bl + rdid = -1; // BL writes only X30, not a displacement-selected register. rval = pc + 4; regs[arm.X30] = rval; int imm26 = (ir & 0x03FFFFFF); @@ -580,15 +581,15 @@ public class EvalArm64 { break; } case 0xD6: { - if( (ir & 0xFFFF) != 0 ) throw Utils.TODO(); - if( ((ir>>16) & 0xFF) != 0x5F ) throw Utils.TODO(); // 0x3F is register call + int op = ir & 0xFFFFFC1F; + int rn = (ir >>> 5) & 31; + int target = (int)regs[rn]; // Read before BLR overwrites X30. rdid = -1; - int rn = ir << 22 >> 27; - assert rn == 0; - pc = (int)regs[30]; - // Return to zero breaks simulation - if( pc==0 ) break outer; - pc -= 4; // Undo post-increment + if( op==0xD63F0000 ) regs[arm.X30] = pc+4; // BLR + else if( op!=0xD65F0000 ) { trap = 3; break; } // RET + pc = target; + if( op==0xD65F0000 && pc==0 ) break outer; + pc -= 4; break; } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index b2d14a02..ec666653 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -105,6 +105,48 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,new RegAlloc(code))); } + private static class CallOp extends CallNode implements MachNode { + CallOp(Node ctrl, Node def) { super(null,ctrl,null,def,def); } + @Override public RegMask regmap(int i) { return i==2 ? A : i==3 ? B : null; } + @Override public RegMask outregmap() { return null; } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + + public static void popularUses() { + for( int calls=0; calls<=2; calls++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + RegionNode block = new RegionNode(null,code._start,code._start); + Op def = new Op(new RegMask(7L),null,null,false,block); + LRG lrg = alloc.newLRG(def); + lrg._machDef = def; + lrg._mask = new RegMask(0L); + Op ab = new Op(null,new RegMask(3L),null,false,block,def); + Op bc = new Op(null,new RegMask(6L),null,false,block,def); + Op a = new Op(null,A,null,false,block,def,def); + Op b = new Op(null,B,null,false,block,def); + Op dep = new Op(null,null,null,false,block,def); + CallOp call = calls>0 ? new CallOp(block,def) : null; + if( calls==2 ) new CallOp(block,def); + boolean split = alloc.splitEmptyMaskByUse((byte)0,lrg); + assertEquals(calls<2,split); + if( !split ) { assertSame(def,a.in(1)); assertSame(def,b.in(1)); continue; } + // Two shared copies, even with overlapping masks and repeated inputs. + assertTrue(a.in(1) instanceof SplitNode); + assertTrue(b.in(1) instanceof SplitNode); + assertNotSame(a.in(1),b.in(1)); + assertSame(a.in(1),a.in(2)); + assertSame(b.in(1),ab.in(1)); + assertSame(b.in(1),bc.in(1)); + assertSame(def,dep.in(1)); // A scheduling dependency has no register. + assertEquals(3,def.nOuts()); // Two copies and the dependency. + if( call!=null ) { + assertSame(a.in(1),call.in(2)); + assertSame(b.in(1),call.in(3)); + } + } + } + // 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); } -- cgit v1.2.3