From 40b33cb6f8b8dc4d8551c3b522e7c5682a44540a Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 20 Sep 2026 22:38:58 -0700 Subject: Final reg-alloc across chapters cleanup --- chapter21/README.md | 41 +++++++------- .../java/com/seaofnodes/simple/codegen/IFG.java | 2 +- .../seaofnodes/simple/node/cpus/arm/LoadARM.java | 10 +--- .../seaofnodes/simple/node/cpus/arm/MemOpARM.java | 11 +++- .../seaofnodes/simple/node/cpus/arm/StoreARM.java | 8 +-- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 2 +- .../simple/node/cpus/riscv/StoreRISC.java | 2 +- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 2 +- .../java/com/seaofnodes/simple/BrainFuckTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 19 ++++++- .../java/com/seaofnodes/simple/Chapter21Test.java | 65 ++++++++++++++++++++++ .../test/java/com/seaofnodes/simple/EvalArm64.java | 14 ++--- .../simple/codegen/RegAllocTestSupport.java | 13 +++++ 13 files changed, 140 insertions(+), 51 deletions(-) (limited to 'chapter21') diff --git a/chapter21/README.md b/chapter21/README.md index cd3a46ae..21f2febf 100644 --- a/chapter21/README.md +++ b/chapter21/README.md @@ -112,9 +112,9 @@ by `8^loopDepth`. | Test cohort | Allocations | Splits | Loop-weighted splits | |---|---:|---:|---:| -| Chapter 20 | 39 | 401 | 653 | -| Chapter 21 | 52 | 483 | 1,141 | -| Total | 91 | 884 | 1,794 | +| Chapter 20 | 39 | 379 | 484 | +| Chapter 21 | 52 | 461 | 972 | +| Total | 91 | 840 | 1,456 | The Chapter 20 row freezes all 13 original inputs, including BrainFuck and MergeSort, on three SystemV targets. They live in `Chapter20Test`. The revised @@ -126,23 +126,20 @@ row; compare the same host and targets. | Controlled comparison, same 91 compilations | Splits | Loop-weighted splits | |---|---:|---:| -| Current compiler with coalescing disabled | 1,074 | 1,921 | -| Current compiler with coalescing | 884 | 1,794 | -| Original Chapter 21 snapshot, including later heuristics | 794 | 1,620 | - -The controlled run disables only the `Coalesce.coalesce` call in `graphColor`; -allocation, register-constraint, and runtime checks still pass. Its different -spill goldens are reported as failures, as intended for this experiment. - -Coalescing saves 190 moves (17.7%) and 127 weighted moves (6.6%) against the same -corrected compiler without coalescing. It is not uniformly beneficial; use the -summed measurements to judge the change. - -Deferring the later heuristics has a visible cost against the old snapshot: -weighted totals rise by 174 (10.7%). RISC-V BrainFuck rises from 28 to 211 in the -native case, while sieve improves from 257 to 178 on x86/Win64, 160 to 89 on -RISC-V, and 160 to 93 on ARM. These are reported costs of the staged tutorial, -not evidence that the simplified allocator beats the original combined one. -Chapter 20's 355 weighted splits also cannot be read as a coalescing baseline: +| Current compiler with coalescing disabled | 1,070 | 1,889 | +| Current compiler with coalescing | 840 | 1,456 | + +The controlled run disables only `Coalesce.coalesce` in `graphColor`. Allocation, +register constraints, and runtime checks pass in both runs. The disabled run +reports nine changed spill goldens and exits unsuccessfully, as intended. +Coalescing saves 230 moves (21.5%) and 433 weighted moves (22.9%). Local increases +can still occur; the aggregate, rather than one example, judges the tradeoff. + +The final audit backported narrow x86/RISC-V store masks and corrected ARM +register-bank selection and floating-point memory operations. Restricting byte +stores to legal registers lowers RISC-V BrainFuck from 211 to 42 weighted moves +in each of its two cohorts, reducing the previous table by 44 raw / 338 weighted +moves. These correctness fixes are included on both sides of the comparison. +Earlier measurements made with the broader masks are historical, not the current +baseline. Chapter 20's 357 weighted moves are not a coalescing baseline either: Chapter 21 changes machine lowering and implements native ABI obligations. -The controlled comparison above holds those changes fixed. diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 2912e179..546844b0 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -507,7 +507,7 @@ abstract public class IFG { if( reg == -1 && alrg._mask.size1() ) reg = alrg._mask.firstReg(); if( reg != -1 ) { - mask.clr(alrg._reg); + mask.clr(reg); if( mask.size1() ) return mask.firstReg(); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index 44c13321..65ca3603 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -4,7 +4,6 @@ import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.LoadNode; import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.type.TypeFloat; // Load memory addressing on ARM // Support imm, reg(direct), or reg+off(indirect) addressing @@ -17,20 +16,15 @@ public class LoadARM extends MemOpARM { super(ld, base, idx, off, 0); } @Override public String op() { return "ld"+_sz; } - @Override public RegMask outregmap() { return arm.MEM_MASK; } + @Override public RegMask outregmap() { return size() >= 4 ? arm.MEM_MASK : arm.RMASK; } private static final int[] OP_LOADS = new int[]{ arm.OP_LOAD_IMM_8, arm.OP_LOAD_IMM_16, arm.OP_LOAD_IMM_32, arm.OP_LOAD_IMM_64, }; - private int imm_op() { - return _declaredType == TypeFloat.F32 ? arm.OPF_LOAD_IMM_32 - : _declaredType == TypeFloat.F64 ? arm.OPF_LOAD_IMM_64 - : OP_LOADS[_declaredType.log_size()]; - } private static final int[] OP_LOAD_RS = new int[]{ arm.OP_LOAD_R_8 , arm.OP_LOAD_R_16 , arm.OP_LOAD_R_32 , arm.OP_LOAD_R_64, }; // ldr(immediate - unsigned offset) | ldr(register) @Override public void encoding( Encoding enc ) { - ldst_encode(enc, imm_op(), OP_LOAD_RS[_declaredType.log_size()], this, size()); + ldst_encode(enc, OP_LOADS[Integer.numberOfTrailingZeros(size())], OP_LOAD_RS[_declaredType.log_size()], this, size()); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)).p(","); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java index 6d8344a2..bec0acc5 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java @@ -45,7 +45,7 @@ public abstract class MemOpARM extends MemOpNode implements MachNode { if( i==1 ) return null; // memory if( i==2 ) return arm.RMASK; // ptr/base if( i==3 ) return arm.RMASK; // off/index - if( i==4 ) return arm.RMASK; // value + if( i==4 ) return size() >= 4 ? arm.MEM_MASK : arm.RMASK; // value return null; // Anti-dependence } @@ -54,6 +54,15 @@ public abstract class MemOpARM extends MemOpNode implements MachNode { short ptr = enc.reg(ptr()); short off = enc.reg(off()); short val = enc.reg(xval); + // The allocated register selects integer vs SIMD/FP encoding, even for + // bitwise copies. ARM numbers each register bank from zero in the opcode. + boolean fp = val >= arm.D0; + assert !fp || size >= 4; + if( fp ) { + opcode_imm |= 1<<4; + opcode_reg |= 1<<5; + val -= arm.D0; + } int body = off() == null ? arm.load_str_imm(opcode_imm, _off, ptr, val, size) : arm.indr_adr(opcode_reg, off, arm.STORE_LOAD_OPTION.SXTX, 0, ptr, val); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java index 688d8731..0ce6197b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java @@ -4,7 +4,6 @@ import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.StoreNode; import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.type.TypeFloat; // Store memory addressing on ARM // Support imm, reg(direct), or reg+off(indirect) addressing @@ -24,16 +23,11 @@ public class StoreARM extends MemOpARM { @Override public RegMask outregmap() { return null; } private static final int[] OP_STORES = new int[]{ arm.OP_STORE_IMM_8, arm.OP_STORE_IMM_16, arm.OP_STORE_IMM_32, arm.OP_STORE_IMM_64, }; - private int imm_op() { - return _declaredType == TypeFloat.F32 ? arm.OPF_STORE_IMM_32 - : _declaredType == TypeFloat.F64 ? arm.OPF_STORE_IMM_64 - : OP_STORES[_declaredType.log_size()]; - } private static final int[] OP_STORE_RS = new int[]{ arm.OP_STORE_R_8, arm.OP_STORE_R_16, arm.OP_STORE_R_32, arm.OP_STORE_R_64, }; @Override public void encoding( Encoding enc ) { - ldst_encode(enc, imm_op(), OP_STORE_RS[_declaredType.log_size()], val(), size()); + ldst_encode(enc, OP_STORES[Integer.numberOfTrailingZeros(size())], OP_STORE_RS[_declaredType.log_size()], val(), size()); } @Override public void asm(CodeGen code, SB sb) { asm_address(code,sb).p(","); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 9ba63b22..533f2d7b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -169,7 +169,7 @@ public class arm extends Machine { public static int OPF_STORE_R_64 = 0b11111100001; public static int OPF_STORE_R_32 = 0b10111100001; - public static int OPF_STORE_IMM_32 = 0b1111110100; + public static int OPF_STORE_IMM_32 = 0b1011110100; public static int OPF_STORE_IMM_64 = 0b1111110100; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java index 7305c4d9..55f9d33b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -26,7 +26,7 @@ public class StoreRISC extends MemOpRISC { if( i==1 ) return null; // mem if( i==2 ) return riscv.RMASK; // ptr // 2 - index - if( i==4 ) return riscv.MEM_MASK; // Wide mask to store GPR and FPR + if( i==4 ) return _sz >= '4' ? riscv.MEM_MASK : riscv.RMASK; // No byte/short FP stores return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 97586d87..9f80b1f5 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -66,7 +66,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base in GPR if( i==3 ) return x86_64_v2.RMASK; // index in GPR - if( i==4 ) return _sz >= 2 + if( i==4 ) return _sz >= '4' ? x86_64_v2.MEM_MASK // value in GPR or XMM : x86_64_v2.RMASK; // Bytes and shorts in GPR only return null; // Anti-dependence diff --git a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 7912929b..610969e7 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -16,7 +16,7 @@ public class BrainFuckTest { String brain_fuck = "Hello World!\n"; TestC.run("brain_fuck", brain_fuck, 40); - EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 211, false); + EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 42, false); int trap = R5.step(100000); assertEquals(0,trap); int ptr = (int)R5.regs[riscv.A0]; diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 4685e4d5..0691d4a2 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -9,6 +9,23 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter20Test { + @Test public void testAllocatorFixedNeighbor() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.uncoloredFixedNeighbor(); } + + @Test public void testNarrowStoreMasks() { + for( String type : new String[]{"i8","u8","i16","u16"} ) { + CodeGen code = new CodeGen("struct S { "+type+" x; }; S !s=new S; s.x=arg; return 0;") + .driver(CodeGen.Phase.RegAlloc,"x86_64_v2","SystemV"); + int 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(-1,st.regmap(4).nextReg((short)15)); + } + assertEquals(1,stores); + } + } + @Test public void testInlinedReturnValue() { String src = """ struct S { int x; }; @@ -289,7 +306,7 @@ for( int pc = 0; pc < program#; pc++ ) { return output; """; testTarget(src,"x86_64_v2", "SystemV",40,null); - testTarget(src,"riscv" , "SystemV",211,null); + testTarget(src,"riscv" , "SystemV",42,null); testTarget(src,"arm" , "SystemV",34,null); //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 5e86d21c..729bdc97 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -11,6 +11,71 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testArmFloatMemory() throws IOException { + for( String type : new String[]{"f32","f64"} ) { + String src = type+"[] !a=new "+type+"[3]; a[arg]=1.25; return a[1];"; + CodeGen code = new CodeGen(src).driver("arm","SystemV",null); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalArm64 cpu = new EvalArm64(image,1<<16); + cpu.regs[arm.X0]=1; + assertEquals(0,cpu.step(1000)); + assertEquals(1.25,cpu.fregs[0],0); + } + // Independently exercise both SIMD widths and addressing modes. Keep + // the GPR value different so accidentally reading that bank is visible. + for( boolean wide : new boolean[]{false,true} ) + for( boolean indexed : new boolean[]{false,true} ) { + EvalArm64 cpu = new EvalArm64(new byte[512],256); + cpu.regs[1]=128; cpu.regs[2]=16; cpu.regs[3]=99; + cpu.fregs[3]=-13.25; + int store = (wide ? 0xFD000000 : 0xBD000000) | ((16/(wide?8:4))<<10) | (1<<5) | 3; + if( indexed ) store=(wide ? 0xFC226823 : 0xBC226823); // STR D3/S3,[X1,X2] + cpu.st4(0,store); + cpu.st4(4,store | (1<<22)); // LDR to the same SIMD register. + assertEquals(0,cpu.step(1)); + assertEquals(-13.25,wide ? cpu.ld8f(144) : cpu.ld4f(144),0); + cpu.fregs[3]=0; + assertEquals(0,cpu.step(1)); + assertEquals(-13.25,cpu.fregs[3],0); + } + } + + + @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 testArmCallInstructions() { EvalArm64 cpu = new EvalArm64(new byte[512],256); for( int delta : new int[]{4,32,-4} ) { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java index 66772060..75525133 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -404,7 +404,7 @@ public class EvalArm64 { switch(opc) { case 0x1: { if(opcode1 == arm.OPF_STORE_R_64) { - st8((int)regs[rn] + (int)regs[rm], (int)regs[rdid]); + st8((int)regs[rn] + (int)regs[rm], Double.doubleToRawLongBits(fregs[rdid])); }else { trap = (2+1); } @@ -439,7 +439,7 @@ public class EvalArm64 { switch(opc) { case 0x1: { if(opcode1 == arm.OPF_STORE_R_32) { - st4((int)regs[rn] + (int)regs[rm], (int)regs[rdid]); + st4((int)regs[rn] + (int)regs[rm], Float.floatToRawIntBits((float)fregs[rdid])); }else { trap = (2+1); } @@ -478,7 +478,7 @@ public class EvalArm64 { case 0x0: { // store if(opcode1 == arm.OPF_STORE_IMM_32) { - st4((int)rval, (int)regs[rdid]); + st4((int)rval, Float.floatToRawIntBits((float)fregs[rdid])); } else trap = (2+1); rdid = -1; @@ -487,7 +487,7 @@ public class EvalArm64 { case 0x1: { // LDR (immediate) if(opcode1 == arm.OPF_LOAD_IMM_32) { - frval = ld4s((int)rval); + frval = ld4f((int)rval); } else trap = (2+1); break; } @@ -500,7 +500,7 @@ public class EvalArm64 { int base = ir >> 5 & 0x1F; int imm = (ir >> 10) & 0xFFF; - imm *= 4; + imm *= 8; is_f = true; rval = regs[base] + imm; int opc = (ir >> 22) & 0x3; @@ -510,7 +510,7 @@ public class EvalArm64 { case 0x0: { // store if(opcode1 == arm.OPF_STORE_IMM_64) { - st8((int)rval, regs[rdid]); + st8((int)rval, Double.doubleToRawLongBits(fregs[rdid])); } else trap = (2+1); rdid = -1; @@ -519,7 +519,7 @@ public class EvalArm64 { case 0x1: { // LDR (immediate) if(opcode1 == arm.OPF_LOAD_IMM_64) { - frval = ld8((int)rval); + frval = ld8f((int)rval); } else trap = (2+1); break; } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 8c8f0f98..abc2ae82 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -29,6 +29,19 @@ public class RegAllocTestSupport { return code; } + public static void uncoloredFixedNeighbor() throws Exception { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + LRG lrg = alloc.newLRG(def); + LRG neighbor = new LRG((short)99); + neighbor._mask = A; + lrg.addNeighbor(neighbor); // Uncolored, but its only possible color is A. + var bias = IFG.class.getDeclaredMethod("biasColorNeighbors",RegAlloc.class,Node.class,RegMask.class); + bias.setAccessible(true); + assertEquals((short)1,bias.invoke(null,alloc,def,new RegMaskRW(3L,0L))); + } + public static void masks() { for( int reg : new int[]{0,63,64,65,127} ) { RegMask mask = new RegMask(reg); -- cgit v1.2.3