diff options
131 files changed, 2135 insertions, 1127 deletions
diff --git a/chapter20/README.md b/chapter20/README.md index e050a812..e463831a 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -505,21 +505,20 @@ checks, not additional program benchmarks. | Program-test cohort | Allocator chapter | Compilations | Split moves | Loop-weighted moves | |---|---:|---:|---:|---:| -| Chapter 20 | 20 | 39 | 236 | 355 | +| Chapter 20 | 20 | 39 | 238 | 357 | `_spills` counts surviving split moves, including register-to-register copies; it does not count only stack stores. `_spillScaled` weights each move by `8^loopDepth`, a rough cost estimate rather than measured execution frequency. -The weighted subtotals are 152 for x86-64, 101 for RISC-V, and 102 for ARM. +The weighted subtotals are 154 for x86-64, 101 for RISC-V, and 102 for ARM. ### Comments on the measurements -Before the correctness fixes, this same cohort had 235 moves and a weighted -count of 354. The corrected baseline is one higher in each measure: x86-64's -weighted count rises by two, ARM's by one, while RISC-V's falls by two. This is -a small correctness cost, not a claimed quality improvement. Individual cases -move more: the x86 array example rises from three to five, while its integer -Newton example stays at 23. Looking at just one example would be misleading. +Before the correctness fixes, this cohort had 235 moves / 354 weighted moves. +The final corrected baseline costs three more of each. The final narrow x86 +store-mask backport accounts for two of those moves: an integer byte/short store +cannot consume an XMM register. This is a correctness cost, not a quality gain. +The fixed-neighbor color-bias correction changes no counts in this cohort. Later chapters will add one quality technique at a time and end with this kind of table: Chapter 21 will measure both the Chapter 20 and Chapter 21 program diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java index acfec53f..71a96d94 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -494,7 +494,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/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index dee4afd4..f65fe054 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter20/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 x86_64_v2.MEM_MASK; // value in GPR or XMM + if( i==4 ) return _sz >= '4' ? x86_64_v2.MEM_MASK : x86_64_v2.RMASK; // Narrow stores need GPRs throw Utils.TODO(); } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 00a8407f..71a4bc36 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -10,6 +10,23 @@ import static com.seaofnodes.simple.Main.PORTS; 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;") + .parse().opto().typeCheck().instSelect(PORTS,"x86_64_v2","SystemV").GCM().localSched().regAlloc(); + 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; }; diff --git a/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index bb1d49bf..1b3963c5 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -30,6 +30,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); 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); diff --git a/chapter22/README.md b/chapter22/README.md index bcb286d0..229c78d9 100644 --- a/chapter22/README.md +++ b/chapter22/README.md @@ -221,8 +221,8 @@ confused with comparing entire compiler chapters: lowering also changes. For example, the frozen Chapter 20 String input has no explicit return, and Chapter 22's default-return handling eliminates that workload at the default seed. -The full suite passes 416 tests plus the fuzzer; the statistics runner passes -55 selected tests. Routine backend comparisons use a fixed optimizer seed: +The full suite and statistics runner pass. Routine backend comparisons use a +fixed optimizer seed: shuffling optimizer worklists should normalize to essentially the same graph, so repeating allocation on those graphs adds little coverage. Use seed variation when investigating optimizer normalization or worklist-order failures. diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 1268db6a..c73f1035 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -522,7 +522,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/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index 44c13321..65ca3603 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java index 6d8344a2..bec0acc5 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java +++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java index 688d8731..0ce6197b 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java +++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index b619899a..578901c1 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter22/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/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 337d58ea..1765512a 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -11,6 +11,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; }; diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 85e92bd8..b27e16fd 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -12,6 +12,38 @@ 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 testArmCallInstructions() { EvalArm64 cpu = new EvalArm64(new byte[512],256); for( int delta : new int[]{4,32,-4} ) { diff --git a/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java index b9c5e415..c6151340 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -480,7 +480,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); } @@ -519,7 +519,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; @@ -528,7 +528,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; } @@ -682,7 +682,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); } @@ -710,7 +710,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; @@ -720,7 +720,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; @@ -729,7 +729,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/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 85de8b36..e4643ee6 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter22/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); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java index bc14aadd..ecff9aac 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -522,7 +522,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/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index 1e5d2094..8967d654 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node.cpus.arm; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.LoadNode; import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.util.SB; // Load memory addressing on ARM @@ -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/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java index e877931d..01066f47 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java @@ -44,7 +44,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 } @@ -53,6 +53,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/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java index 91385ac9..4fd8ac79 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node.cpus.arm; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StoreNode; -import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.util.SB; // Store memory addressing on ARM @@ -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/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 716f7cb7..db179754 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 70ddd435..044ad4ed 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -11,6 +11,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; }; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index f84a7237..3be634d1 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -13,6 +13,38 @@ 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 testArmCallInstructions() { EvalArm64 cpu = new EvalArm64(new byte[512],256); for( int delta : new int[]{4,32,-4} ) { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java index 54d08e19..46827235 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -481,7 +481,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); } @@ -520,7 +520,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; @@ -529,7 +529,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; } @@ -683,7 +683,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); } @@ -711,7 +711,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; @@ -721,7 +721,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; @@ -730,7 +730,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/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index ec666653..f0830f1b 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter23/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); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java index bc14aadd..ecff9aac 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -522,7 +522,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/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index 1e5d2094..8967d654 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node.cpus.arm; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.LoadNode; import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.util.SB; // Load memory addressing on ARM @@ -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/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java index e877931d..01066f47 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java @@ -44,7 +44,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 } @@ -53,6 +53,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/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java index 91385ac9..4fd8ac79 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node.cpus.arm; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StoreNode; -import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.util.SB; // Store memory addressing on ARM @@ -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/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 9a6b3530..74dc70d4 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter24/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/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 70ddd435..044ad4ed 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -11,6 +11,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; }; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 7b22389e..afa99d31 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -13,6 +13,38 @@ 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 testArmCallInstructions() { EvalArm64 cpu = new EvalArm64(new byte[512],256); for( int delta : new int[]{4,32,-4} ) { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java index 5557de3c..5dc56ef7 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -488,7 +488,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); } @@ -527,7 +527,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; @@ -536,7 +536,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; } @@ -690,7 +690,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); } @@ -718,7 +718,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; @@ -728,7 +728,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; @@ -737,7 +737,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/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 20da40fd..c0a26d60 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter24/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); diff --git a/chapter25/Makefile b/chapter25/Makefile index 9cacde76..fa743535 100644 --- a/chapter25/Makefile +++ b/chapter25/Makefile @@ -242,3 +242,9 @@ tags: TAGS TAGS: $(main_javas) $(test_javas) @rm -f TAGS @$(CTAGS) -e --recurse=yes --fields=+fksaiS $(SRC) $(TST) + +# Frozen earlier allocation cohorts, followed by Chapter 25's native tests. +spill-stats: $(CLZDIR)/test/.ttag $(TEST_SYS) $(RELEASE_SYS) $(RELEASE_CRT) + @$(JVM) com.seaofnodes.simple.SpillStats + +.PHONY: spill-stats diff --git a/chapter25/README.md b/chapter25/README.md index 971c4746..b6a7ded5 100644 --- a/chapter25/README.md +++ b/chapter25/README.md @@ -122,3 +122,66 @@ the environment; the Makefile currently defaults to x86-64/win64. Compiler changes can invalidate both serialized IR and native code in `sys.o`. Rebuild it before interpreting linked-program test results. A source-only subset is not equivalent to this chapter's full `make tests`. + +## RegAlloc improvements: live-range area and split cost + +Chapter 24 tried cold copies before splitting a loop Phi's hot edges. This +chapter also estimates how much scheduled code a spill frees from register +pressure, divided by the estimated cost of the new copies. Callee-save ranges +cover a whole function. Cloneable constants can be rebuilt nearer their uses. +Copies inside loops cost more: the estimate weights them by `8^loopDepth`. +These are inexpensive approximations, especially for values with many uses. + +The other Chapter 25 conflict-handling rules remain here: direct splitting of +several fixed-register uses and deeper splits for some multi-definition ranges. +Their size thresholds are heuristics, not general invariants to backport to the +first allocator. Shared legality fixes still start in the earliest affected +chapter. The final audit corrected fixed-neighbor color bias in 20-25, narrow +store masks in 20-21, and ARM register-bank/float-memory encoding in 21-25. + +Run `make spill-stats`. Each row uses **Chapter 25's compiler**. The first five +rows preserve the earlier 212 program/target entries, adapted to this chapter's +syntax and library organization; the [fixture notes](src/test/java/com/seaofnodes/simple/spill/README.md) +list those adaptations and the measurement limits. They use optimizer seed 123. +The last row includes nine allocations from `Chapter25Test` at its existing +seeds plus a fresh system-library compilation at the driver's seed 456. Reusing +`sys.o` must not make that substantial workload disappear from the measurements. +These results are from Windows x86-64; earlier cohorts also include RISC-V/ARM +SystemV and x86 SystemV. The reporter prints per-target totals as well. + +| Program cohort | Compilations | Split/move count | Loop-weighted count | +|---|---:|---:|---:| +| Chapter 20 | 39 | 381 | 612 | +| Chapter 21 | 52 | 464 | 1,185 | +| Chapter 22 | 24 | 103 | 131 | +| Chapter 23 | 30 | 122 | 346 | +| Chapter 24 | 67 | 744 | 1,479 | +| Chapter 25 | 10 | 783 | 1,826 | +| **Total** | **222** | **2,597** | **5,579** | + +`_spills` counts retained SplitNodes, including register-to-register moves; +`_spillScaled` applies the loop weight. Neither measures just memory traffic. +The old cohorts are allocation replays with register-legality checks, not reruns +of their native harnesses. `Chapter25Test` still runs its native/result checks. +Use `make -j 4 tests` for the full chapter, including inherited emulator tests. + +### Comments on the measurements + +There is no uniform improvement to claim. Substituting Chapter 24's ranking +while keeping the rest of this compiler unchanged saves five moves on the 221 +client compilations (2,206 / 4,719 versus 2,211 / 4,724), but fails to allocate +the system library within eight rounds. It is therefore an incomplete comparison, +not a lower valid whole-suite total. The existing area/cost ranking is retained; +the round limit and correctness checks are unchanged. The system library itself +contributes 386 moves / 855 weighted moves. + +A trial that favored all multi-use cloneable constants saved one move against +the earlier ranking on those clients, but also failed the fresh library build. +It was rejected. This is why both aggregate statistics and complete compilation +and execution checks matter; a favorable subtotal cannot justify a change. + +The earlier-cohort total rises from Chapter 24's 1,332 / 2,956 to 1,814 / 3,753. +Chapter 25 adds class initializers, module ownership, different escape analysis, +and syntax/library adaptations. These are different machine graphs; the increase +cannot be attributed to allocator quality alone. Compare a heuristic within one +compiler and fixed corpus before drawing conclusions from the chapter tables. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 8d09b58c..8649b68c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -556,7 +556,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/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java index f8c9bfef..827db545 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node.cpus.arm; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.LoadNode; import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.util.SB; // Load memory addressing on ARM @@ -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 _con == TypeFloat.F32 ? arm.OPF_LOAD_IMM_32 - : _con == TypeFloat.F64 ? arm.OPF_LOAD_IMM_64 - : OP_LOADS[_con.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[_con.log_size()], this, size()); + ldst_encode(enc, OP_LOADS[Integer.numberOfTrailingZeros(size())], OP_LOAD_RS[_con.log_size()], this, size()); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)).p(","); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java index 25402018..53a0f8cf 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java @@ -46,7 +46,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 } @@ -55,6 +55,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/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java index b11a2c89..36b6bcdb 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node.cpus.arm; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StoreNode; -import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.util.SB; // Store memory addressing on ARM @@ -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 val()!=null && val()._type instanceof TypeFloat - ? (_bytes==4 ? arm.OPF_STORE_IMM_32 : arm.OPF_STORE_IMM_64) - : OP_STORES[Integer.numberOfTrailingZeros(_bytes)]; - } 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[Integer.numberOfTrailingZeros(_bytes)], val(), size()); + ldst_encode(enc, OP_STORES[Integer.numberOfTrailingZeros(size())], OP_STORE_RS[Integer.numberOfTrailingZeros(_bytes)], val(), size()); } @Override public void asm(CodeGen code, SB sb) { asm_address(code,sb).p(","); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 510d5e78..d4e10404 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter25/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/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 647b253e..a9f7dde7 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -8,6 +8,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 && st._name.equals("x") ) { + stores++; + assertEquals(-1,st.regmap(4).nextReg((short)15)); + } + assertTrue(stores>0); + } + } + @Test public void testInlinedReturnValue() { String src = """ struct S { int x; }; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 10d52ea7..c7677345 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -10,6 +10,34 @@ 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];"; + EvalArm64 cpu = TestArm64.build("probe","val probe={ int arg -> "+src+" };",1,-1,false); + 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 testArmCallInstructions() { EvalArm64 cpu = new EvalArm64(new byte[512],256); for( int delta : new int[]{4,32,-4} ) { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index b96ae836..0ac55a9e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.ElfReader; import com.seaofnodes.simple.codegen.ParseAll; import com.seaofnodes.simple.type.TypeInteger; @@ -282,7 +283,7 @@ int v0=0^0; String base = "helloWorldNoInline"; String expected = "Hello, World!\n"; String prog = "return sys.io.p_noInline(\""+expected+"\") - "+expected.length()+";"; - CodeGen code = new CodeGen(null,"build/objs",new Ary<>(new String[]{SYS_BLDDIR}), + CodeGen code = new CheckedCodeGen(null,"build/objs",new Ary<>(new String[]{SYS_BLDDIR}), base,prog,123L,true,TypeInteger.BOT); code.driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,true); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter25/src/test/java/com/seaofnodes/simple/EvalArm64.java index aa128b72..e8121927 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -483,7 +483,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); } @@ -522,7 +522,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; @@ -531,7 +531,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; } @@ -685,7 +685,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); } @@ -713,7 +713,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; @@ -723,7 +723,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; @@ -732,7 +732,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/chapter25/src/test/java/com/seaofnodes/simple/SpillStats.java b/chapter25/src/test/java/com/seaofnodes/simple/SpillStats.java new file mode 100644 index 00000000..d43f1a36 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -0,0 +1,92 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; +import com.seaofnodes.simple.type.TypeInteger; +import java.nio.file.*; +import java.util.Map; +import java.util.TreeMap; +import org.junit.runner.*; +import org.junit.runner.notification.*; + +// Earlier cohorts freeze source/target membership; Chapter 25 retains native checks. +public class SpillStats extends RunListener { + private static SpillStats ACTIVE; + private Description _test; + private int _qualityFailures; + private final Map<String,long[]> _totals = new TreeMap<>(); + + @Override public void testStarted(Description test) { _test = test; } + @Override public void testFinished(Description test) { _test = null; } + + public static void record25(CodeGen code) { + if( ACTIVE==null || ACTIVE._test==null || ACTIVE._test.getTestClass()!=Chapter25Test.class ) return; + ACTIVE.record(code,"Chapter25",ACTIVE._test.getMethodName(),code._mach.getClass().getSimpleName(),code._callingConv); + } + + private void record(CodeGen code, String cohort, String test, String cpu, String abi) { + for( String key : new String[]{cohort+","+cpu+","+abi,cohort+",ALL,ALL"} ) { + long[] sum = _totals.computeIfAbsent(key,k -> new long[3]); + sum[0]++; sum[1] += code._regAlloc._spills; sum[2] += code._regAlloc._spillScaled; + } + System.out.println("allocation,"+cohort+","+test+","+cpu+","+abi+","+ + code._regAlloc._spills+","+code._regAlloc._spillScaled); + } + + // Keep native result checks running during a quality comparison. + public static void checkSpills(int expected, int actual) { + if( expected==-1 || CodeGen.iterSeedOverridden() ) return; + try { org.junit.Assert.assertEquals("Expect spills:",expected,actual,Math.max(1,expected>>3)); } + catch( AssertionError error ) { + if( ACTIVE==null ) throw error; + ACTIVE._qualityFailures++; + System.err.println(ACTIVE._test+": "+error.getMessage()); + } + } + + public static void main(String[] args) throws Exception { + ACTIVE = new SpillStats(); + Path dir = Path.of("src/test/java/com/seaofnodes/simple/spill"); + int failures=0, attempts=0; + for( String line : Files.readAllLines(dir.resolve("cohorts.tsv")) ) { + if( line.startsWith("#") || line.isBlank() ) continue; + attempts++; + String[] row = line.split("\t"); + try { + String src = Files.readString(dir.resolve(row[5])); + CodeGen code = new CheckedCodeGen(null,null,null,null,src,123L,true,TypeInteger.BOT) + .driver(CodeGen.Phase.RegAlloc,row[2],row[3]); + ACTIVE.record(code,row[0],row[1],row[2],row[3]); + } catch( Throwable error ) { + failures++; + System.err.println(line); + error.printStackTrace(); + } + } + // Include the library's allocation even when make's sys.o is up to date. + try { + CodeGen code = new CheckedCodeGen("src/main/smp","build/spill-sys",null,"sys", + Files.readString(Path.of("src/main/smp/sys.smp")),456L,true,TypeInteger.BOT) + .driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION); + ACTIVE.record(code,"Chapter25","sys",TestC.CPU_PORT,TestC.CALL_CONVENTION); + } catch( Throwable error ) { + failures++; + error.printStackTrace(); + } + JUnitCore junit = new JUnitCore(); + junit.addListener(ACTIVE); + Result result = junit.run(Chapter25Test.class); + for( Failure failure : result.getFailures() ) System.err.println(failure.getTrace()); + failures += result.getFailureCount(); + if( failures!=0 ) System.out.println("FAILED: totals are not a complete comparison."); + System.out.println("cohort,cpu,abi,allocations,splits,scaled"); + for( var row : ACTIVE._totals.entrySet() ) { + long[] sum = row.getValue(); + System.out.println(row.getKey()+","+sum[0]+","+sum[1]+","+sum[2]); + } + System.out.println("Historical allocations: "+attempts+"; native tests: "+result.getRunCount()+"; failures: "+failures+"; spill golden failures: "+ACTIVE._qualityFailures); + failures += ACTIVE._qualityFailures; + ACTIVE = null; + if( failures!=0 ) System.exit(1); + } +}
\ No newline at end of file diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java index e0ee701a..44291196 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java @@ -125,10 +125,7 @@ public abstract class TestC { linkExe(obj, c_conv, cfile, linkObjs(externPaths), exe); // Allocation quality not degraded - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 && !CodeGen.iterSeedOverridden() ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); return exe; } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 038d6882..6c6b9ad5 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter25/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,null); + LRG neighbor = new LRG((short)99,null); + 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); @@ -157,6 +170,7 @@ public class RegAllocTestSupport { @Override public CodeGen regAlloc() { super.regAlloc(); checkRegisters(this); + com.seaofnodes.simple.SpillStats.record25(this); return this; } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/BrainFuckTest-testBrainFuck.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/BrainFuckTest-testBrainFuck.smp new file mode 100644 index 00000000..71af2b7a --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/BrainFuckTest-testBrainFuck.smp @@ -0,0 +1,46 @@ +// -*- mode: java; -*- +val brain_fuck = { -> + var !program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."; + int d = 0; + u8[] !output = new u8[0]; + u8[] !data = new u8[100]; + + for( int pc = 0; pc < program#; pc++ ) { + var command = program[pc]; + if (command == 62) { + d++; + } else if (command == 60) { + d--; + } else if (command == 43) { + data[d]++; + } else if (command == 45) { + data[d]--; + } else if (command == 46) { + // Output a byte; increase the output array size + var old = output; + output = new u8[output# + 1]; + for( int i = 0; i < old#; i++ ) + output[i] = old[i]; + output[old#] = data[d]; // Add the extra byte on the end + } else if (command == 44) { + data[d] = 42; + } else if (command == 91) { + if (data[d] == 0) { + for( int d = 1; d > 0; ) { + command = program[++pc]; + if (command == 91) d++; + if (command == 93) d--; + } + } + } else if (command == 93) { + if (data[d]) { + for( int d = 1; d > 0; ) { + command = program[--pc]; + if (command == 93) d++; + if (command == 91) d--; + } + } + } + } + return output; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testAlloc0.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testAlloc0.smp new file mode 100644 index 00000000..d85e39e5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testAlloc0.smp @@ -0,0 +1 @@ +return new u8[arg]; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testAlloc2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testAlloc2.smp new file mode 100644 index 00000000..864bcdc8 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testAlloc2.smp @@ -0,0 +1 @@ +int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1]; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testArray1.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testArray1.smp new file mode 100644 index 00000000..7f3bd007 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testArray1.smp @@ -0,0 +1,8 @@ +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +for( int i=0; i<ary#; i++ ) + ary[i] = i; +// Fill [0,1,3,6,10,...] +for( int i=0; i<ary#-1; i++ ) + ary[i+1] += ary[i]; +return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testBasic1.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testBasic1.smp new file mode 100644 index 00000000..671e5b74 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testBasic1.smp @@ -0,0 +1 @@ +return arg | 2; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testBrainfuck.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testBrainfuck.smp new file mode 100644 index 00000000..4e5ab81d --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testBrainfuck.smp @@ -0,0 +1,43 @@ +u8[] !program = new u8[106];program[0] = 43;program[1] = 43;program[2] = 43;program[3] = 43;program[4] = 43;program[5] = 43;program[6] = 43;program[7] = 43;program[8] = 91;program[9] = 62;program[10] = 43;program[11] = 43;program[12] = 43;program[13] = 43;program[14] = 91;program[15] = 62;program[16] = 43;program[17] = 43;program[18] = 62;program[19] = 43;program[20] = 43;program[21] = 43;program[22] = 62;program[23] = 43;program[24] = 43;program[25] = 43;program[26] = 62;program[27] = 43;program[28] = 60;program[29] = 60;program[30] = 60;program[31] = 60;program[32] = 45;program[33] = 93;program[34] = 62;program[35] = 43;program[36] = 62;program[37] = 43;program[38] = 62;program[39] = 45;program[40] = 62;program[41] = 62;program[42] = 43;program[43] = 91;program[44] = 60;program[45] = 93;program[46] = 60;program[47] = 45;program[48] = 93;program[49] = 62;program[50] = 62;program[51] = 46;program[52] = 62;program[53] = 45;program[54] = 45;program[55] = 45;program[56] = 46;program[57] = 43;program[58] = 43;program[59] = 43;program[60] = 43;program[61] = 43;program[62] = 43;program[63] = 43;program[64] = 46;program[65] = 46;program[66] = 43;program[67] = 43;program[68] = 43;program[69] = 46;program[70] = 62;program[71] = 62;program[72] = 46;program[73] = 60;program[74] = 45;program[75] = 46;program[76] = 60;program[77] = 46;program[78] = 43;program[79] = 43;program[80] = 43;program[81] = 46;program[82] = 45;program[83] = 45;program[84] = 45;program[85] = 45;program[86] = 45;program[87] = 45;program[88] = 46;program[89] = 45;program[90] = 45;program[91] = 45;program[92] = 45;program[93] = 45;program[94] = 45;program[95] = 45;program[96] = 45;program[97] = 46;program[98] = 62;program[99] = 62;program[100] = 43;program[101] = 46;program[102] = 62;program[103] = 43;program[104] = 43;program[105] = 46; +int d = 0; +u8[] !output = new u8[0]; +u8[] !data = new u8[100]; + +for( int pc = 0; pc < program#; pc++ ) { + var command = program[pc]; + if (command == 62) { + d++; + } else if (command == 60) { + d--; + } else if (command == 43) { + data[d]++; + } else if (command == 45) { + data[d]--; + } else if (command == 46) { + // Output a byte; increase the output array size + var old = output; + output = new u8[output# + 1]; + for( int i = 0; i < old#; i++ ) + output[i] = old[i]; + output[old#] = data[d]; // Add the extra byte on the end + } else if (command == 44) { + data[d] = 42; + } else if (command == 91) { + if (data[d] == 0) { + for( int d = 1; d > 0; ) { + command = program[++pc]; + if (command == 91) d++; + if (command == 93) d--; + } + } + } else if (command == 93) { + if (data[d]) { + for( int d = 1; d > 0; ) { + command = program[--pc]; + if (command == 93) d++; + if (command == 91) d--; + } + } + } +} +return output; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testCast.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testCast.smp new file mode 100644 index 00000000..19c36ebb --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testCast.smp @@ -0,0 +1 @@ +struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFlags1.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFlags1.smp new file mode 100644 index 00000000..f630e959 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFlags1.smp @@ -0,0 +1,5 @@ +bool b1 = arg == 1; +bool b2 = arg == 2; +if (b2) if (b1) return 1; +if (b1) return 2; +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFlags2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFlags2.smp new file mode 100644 index 00000000..70bfc226 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFlags2.smp @@ -0,0 +1,6 @@ +bool b1 = arg == 1; +while (arg > 0) { + arg--; + if (b1) arg--; +} +return arg; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFltArg.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFltArg.smp new file mode 100644 index 00000000..caa11f12 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testFltArg.smp @@ -0,0 +1 @@ +return {int i, flt f, int j->return i+f+j;}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testMergeSort.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testMergeSort.smp new file mode 100644 index 00000000..eddf1799 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testMergeSort.smp @@ -0,0 +1,46 @@ +// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort + +val merge_sort = { int[] a, int[] b, int n -> + copy_array(a, 0, n, b); + split_merge(a, 0, n, b); +}; + +val split_merge = { int[] b, int begin, int end, int[] a -> + if (end - begin <= 1) + return 0; + int middle = (end + begin) / 2; + split_merge(a, begin, middle, b); + split_merge(a, middle, end, b); + merge(b, begin, middle, end, a); + return 0; +}; + +val merge = { int[] b, int begin, int middle, int end, int[] a -> + int i = begin, j = middle; + + for (int k = begin; k < end; k++) { + // && and || + bool cond = false; + if (i < middle) { + if (j >= end) cond = true; + else if (a[i] <= a[j]) cond = true; + } + if (cond) b[k] = a[i++]; + else b[k] = a[j++]; + } +}; + +val copy_array = { int[] a, int begin, int end, int[] b -> + for (int k = begin; k < end; k++) + b[k] = a[k]; +}; + +int[] !a = new int[arg]; +int[] !b = new int[a#]; + +for (int i = 0; i < a#; i++) + a[i] = a# - i; + +merge_sort(a, b, a#); + +return a; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonFloat.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonFloat.smp new file mode 100644 index 00000000..7fa66a33 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonFloat.smp @@ -0,0 +1,11 @@ +// Newtons approximation to the square root +val sqrt = { flt x -> + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +flt farg = arg; +return sqrt(farg) + sqrt(farg+2.0); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonInteger.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonInteger.smp new file mode 100644 index 00000000..b97da1f3 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonInteger.smp @@ -0,0 +1,10 @@ +// Newtons approximation to the square root +val sqrt = { int x -> + int guess = x; + while( 1 ) { + int next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +return sqrt(arg) + sqrt(arg+2); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testString.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testString.smp new file mode 100644 index 00000000..8c56636f --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testString.smp @@ -0,0 +1,35 @@ +struct String { + u8[] cs; + new String={ u8[] b -> cs=b; }; + int _hashCode; +}; + +val equals = { String self, String s -> + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + if( self.cs ) { + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + } + if( !hash ) hash = 123456789; + return hash; +}; + +String !s = new String(new u8[17]); +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testArray1.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testArray1.smp new file mode 100644 index 00000000..6b10f92c --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testArray1.smp @@ -0,0 +1,9 @@ +// -*- mode: java; -*- +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +for( int i=0; i<ary#; i++ ) + ary[i] = i; +// Fill [0,1,3,6,10,...] +for( int i=0; i<ary#-1; i++ ) + ary[i+1] += ary[i]; +return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testNewtonFloat.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testNewtonFloat.smp new file mode 100644 index 00000000..2b1acfbe --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testNewtonFloat.smp @@ -0,0 +1,13 @@ +// -*- mode: java; -*- +// Newtons approximation to the square root +val test_sqrt = { flt x -> + flt epsilon = 1e-15; + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( guess-epsilon <= next & next <= guess+epsilon ) return guess; + //if( guess==next ) return guess; + guess = next; + } +}; +flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testString.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testString.smp new file mode 100644 index 00000000..dafa7456 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testString.smp @@ -0,0 +1,31 @@ +// -*- mode: java; -*- +struct String { + u8[] cs; + int _hashCode; +}; + +// Compare two Strings +val equals = { String self, String s -> + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +// Return the String hashCode (cached, and never 0) +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + if( self.cs ) + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + if( !hash ) hash = 123456789; + return hash; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testAntiDeps1.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testAntiDeps1.smp new file mode 100644 index 00000000..baf77c92 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testAntiDeps1.smp @@ -0,0 +1,10 @@ +struct S { int f; }; +var v0 = new S; +S? v1; +if (arg) v1 = new S; +if (v1) { + v0.f = v1.f; +} else { + v0.f = 2; +} +return v0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testArgCount-2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testArgCount-2.smp new file mode 100644 index 00000000..20a05445 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testArgCount-2.smp @@ -0,0 +1,6 @@ +// -*- mode: java; -*- +val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, int x8, flt f9, int i10, flt f11, int i12, flt f13, int i14, flt f15 -> + return + i0 + f1+ i2+ f3+ i4+ f5+ i6+ f7+ x8 +f9 + + i10+f11+i12+f13+i14+f15; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testArgCount.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testArgCount.smp new file mode 100644 index 00000000..6b6bc0ae --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testArgCount.smp @@ -0,0 +1,6 @@ +// -*- mode: java; -*- +val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, int x8, flt f9, int i10, flt f11, int i12, flt f13, int i14, flt f15, int x16, flt f17 int x18, flt f19 -> + return + i0 + f1+ i2+ f3+ i4+ f5+ i6+ f7+ x8 +f9 + + i10+f11+i12+f13+i14+f15+x16+f17+x18+f19 ; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testFibExport.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testFibExport.smp new file mode 100644 index 00000000..149872a7 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testFibExport.smp @@ -0,0 +1,10 @@ +val fib = {int n -> + int f1=1; + int f2=1; + while( n-- > 1 ){ + int temp = f1+f2; + f1=f2; + f2=temp; + } + return f2; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testInfinite.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testInfinite.smp new file mode 100644 index 00000000..1e4557d3 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testInfinite.smp @@ -0,0 +1 @@ +struct S { int i; }; S !s = new S; while(1) s.i++; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testLoop2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testLoop2.smp new file mode 100644 index 00000000..cc54f790 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testLoop2.smp @@ -0,0 +1,9 @@ +int i = 0; +while(true) { + i += 1; + if( i==0 ) continue; + if( i==1 ) continue; + if( i==2 ) break; + continue; +} +return i; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testNewtonExport.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testNewtonExport.smp new file mode 100644 index 00000000..2786558e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testNewtonExport.smp @@ -0,0 +1,10 @@ +val test_sqrt = { flt x -> + flt epsilon = 1e-15; + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( guess-epsilon <= next & next <= guess+epsilon ) return guess; + //if( guess==next ) return guess; + guess = next; + } +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testPerson.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testPerson.smp new file mode 100644 index 00000000..06c2861e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testPerson.smp @@ -0,0 +1,9 @@ +// -*-java-*- +struct Person { + int age; +}; + +val fcn = { Person?[] ps, int x -> + if( ps[x] ) + ps[x].age++; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testSieve.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testSieve.smp new file mode 100644 index 00000000..beb0b3ad --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testSieve.smp @@ -0,0 +1,30 @@ +val sieve = { int N -> + // The main Sieve array + bool[] !ary = new bool[N]; + // The primes less than N + u32[] !primes = new u32[N>>1]; + // Number of primes so far, searching at index p + int nprimes = 0, p=2; + // Find primes while p^2 < N + while( p*p < N ) { + // skip marked non-primes + while( ary[p] ) p++; + // p is now a prime + primes[nprimes++] = p; + // Mark out the rest non-primes + for( int i = p + p; i < ary#; i+= p ) + ary[i] = true; + p++; + } + + // Now just collect the remaining primes, no more marking + for( ; p < N; p++ ) + if( !ary[p] ) + primes[nprimes++] = p; + + // Copy/shrink the result array + u32[] !rez = new u32[nprimes]; + for( int j=0; j < nprimes; j++ ) + rez[j] = primes[j]; + return rez; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testStringExport.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testStringExport.smp new file mode 100644 index 00000000..6cc28315 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21Test-testStringExport.smp @@ -0,0 +1,29 @@ +struct String { + u8[] cs; + int _hashCode; +}; + +// Compare two Strings +val equals = { String self, String s -> + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +// Return the String hashCode (cached, and never 0) +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + if( !hash ) hash = 123456789; + return hash; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testHelloWorld.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testHelloWorld.smp new file mode 100644 index 00000000..1bcac36d --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testHelloWorld.smp @@ -0,0 +1,4 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +_p("Hello, World!"); +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testInfiniteReturn.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testInfiniteReturn.smp new file mode 100644 index 00000000..523fc6f9 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testInfiniteReturn.smp @@ -0,0 +1 @@ +struct S { int i; }; S !s = new S; while(1) s.i++; return s.i; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testPerson.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testPerson.smp new file mode 100644 index 00000000..a3cafc9a --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testPerson.smp @@ -0,0 +1,8 @@ +struct Person { + i32 age; +}; + +val fcn = { Person?[] ps, int x -> + if( ps[x] ) + ps[x].age++; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail.smp new file mode 100644 index 00000000..2d431705 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail.smp @@ -0,0 +1,4 @@ +struct Person { i32 age;}; +Person !p = new Person; +p.age = (arg<<17)>>17; +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail2.smp new file mode 100644 index 00000000..01e070c8 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail2.smp @@ -0,0 +1,5 @@ + + struct Person { i32 age;}; + Person !p = new Person; + p.age = (arg<<48)>>48; + return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextSuccess.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextSuccess.smp new file mode 100644 index 00000000..6d11a431 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextSuccess.smp @@ -0,0 +1,5 @@ +// Should fold away sign extend +struct Person { i8 age;}; +Person !p = new Person; +p.age = (arg<<48)>>48; +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testJig21.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testJig21.smp new file mode 100644 index 00000000..f7a5d202 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testJig21.smp @@ -0,0 +1,16 @@ +// -*- mode: java; -*- +val fib = {int n -> + int temp=0; + int f1=1; + int f2=1; + int i=n; + while( i>1 ){ + temp = f1+f2; + f1=f2; + f2=temp; + i=i-1; + } + return f2; +}; + +fib(10); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testString.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testString.smp new file mode 100644 index 00000000..3fa2174c --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testString.smp @@ -0,0 +1,30 @@ +// -*- mode: java; -*- +struct String { + u8[] cs; + int _hashCode; +}; + +// Compare two Strings +val equals = { String self, String s -> + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +// Return the String hashCode (cached, and never 0) +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + if( !hash ) hash = 123456789; + return hash; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAnd.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAnd.smp new file mode 100644 index 00000000..da85ef0e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAnd.smp @@ -0,0 +1,11 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +int a = 1; +int b = 1; + +if(a && b) { + _p("And"); +} else { + _p("Or"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAndPtr.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAndPtr.smp new file mode 100644 index 00000000..5d300ede --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testAndPtr.smp @@ -0,0 +1,12 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +struct S { S? fld; new S={ S? f -> fld=f; }; }; + +val ptr = arg == 1 ? null : new S(arg==1 ? null : new S(null)); +if( ptr && ptr.fld ) { + _p("true"); +} else { + _p("false"); +} + +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testCondSideEffAnd.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testCondSideEffAnd.smp new file mode 100644 index 00000000..1a6b5cf3 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testCondSideEffAnd.smp @@ -0,0 +1,17 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +int a = 1; +int b = 1; + +int x=1; +int y=1; +int z=0; + +int g = x++ && y++ && z++; + +if(x == 2 && y == 2 && z == 1 && g == 0) { + _p("Effected"); +} else { + _p("Not effected"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testCondSideEffOr.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testCondSideEffOr.smp new file mode 100644 index 00000000..f2bb16c5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testCondSideEffOr.smp @@ -0,0 +1,24 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +int a = 1; +int b = 1; + +int x = -1; +int y=1; +int z= -1; + +int g = x++ || y++ || z++; + +int switch = 0; +if(x == 4 || y == 4 || z == 4) { + switch = -1; +} else { + switch = 1; +} +int cd = 1; +if((x == 0 && y == 1 && z==-1) && switch && g) { + _p("Effected"); +} else { + _p("Not effected"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFRefFields.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFRefFields.smp new file mode 100644 index 00000000..8eb86522 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFRefFields.smp @@ -0,0 +1,20 @@ +// A hypothetical scanner class +struct Scan { + int !x; + u8[~] buf; + new Scan={ u8[~] b -> buf=b; }; + // Skip whitespace + val skip = { -> + while( buf[x] <= ' ' ) + x++; + }; + // Peek a character; if matched consume it, else false. + val peek = { u8 c -> + skip(); + if( buf[x] != c ) return false; + x++; + return true; + }; +}; +Scan !s = new Scan(" q"); +return s.peek('q'); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFuncCall.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFuncCall.smp new file mode 100644 index 00000000..b522a811 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testFuncCall.smp @@ -0,0 +1,16 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +// -*- mode: java; -*- +int a = 1; +int b = 1; + +var sq = { int x -> + x*x; +}; + +if(a && sq(0)) { + _p("And"); +} else { + _p("Or"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testMethod.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testMethod.smp new file mode 100644 index 00000000..3ba33216 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testMethod.smp @@ -0,0 +1,17 @@ +// A hypothetical scanner class +struct Scan { + int !x; + u8[~] buf; + new Scan={ u8[~] b -> buf=b; }; + // Skip whitespace + val skip = { -> + while( buf[x] <= ' ' ) + x++; + }; + val require = { u8 ch -> + skip(); + buf[x++]==ch; + }; +}; +Scan !s = new Scan(" [1,2]"); +return s.require('['); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOr.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOr.smp new file mode 100644 index 00000000..dbab1ae5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOr.smp @@ -0,0 +1,13 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +int a = 1; +int b = 0; + +if(a++ || b++ ) { + if(b == 0 && a == 2) { + _p("Or"); + } +} else{ + _p("And"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopLocal.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopLocal.smp new file mode 100644 index 00000000..a4c8a9f5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopLocal.smp @@ -0,0 +1,10 @@ +struct S { int f; }; +int x=0; +int result=arg&1; +if(!result) { + S !s=new S; + while(x<3) x++; + s.f=++x; + result=!!s.f; +} +return x*10+result; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopMemory.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopMemory.smp new file mode 100644 index 00000000..775b92b5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23Test-testOrRhsLoopMemory.smp @@ -0,0 +1,11 @@ +struct S { int f; }; +S !s=new S; +int result=arg&1; +if(!result) { + S !t=new S; + while(s.f<3) s.f++; + s.f++; + t.f=s.f; + result=!!t.f; +} +return s.f*10+result; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testBubbleSort.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testBubbleSort.smp new file mode 100644 index 00000000..a61ca332 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testBubbleSort.smp @@ -0,0 +1,217 @@ + + i32 errno = "C"; + // fd buf len -> len + { i32 i64 u32 -> u32 } write = "C"; + // fd buf len -> len + { i32 i64 u32 -> u32 } read = "C"; + // status + { i32 -> i32 } _exit = "C"; + // addr len prot flags fd off -> void* + { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; + // mmap flags + i32 PROT_EXEC = 4; + i32 PROT_READ = 1; + i32 PROT_WRITE= 2; + i32 PROT_NONE = 0; + i32 MAP_PRIVATE = 2; + i32 MAP_ANON = 32; + + val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> + for( int i=0; i<len; i++ ) + dst[i+doff] = src[i+soff]; + return dst; + }; + struct aryu8 { + u32 !len = 0; + u8[] !buf; + new aryu8={ u8[] b -> buf=b; }; + // Grow as needed + val _grow = { int len2 -> + if( len+len2 < buf# ) return self; + int newlen = buf# * 2; + while( len+len2 >= newlen ) newlen *= 2; + u8[] !buf2 = new u8[newlen]; + copy(buf2,0,buf,0,buf#); + buf = buf2; + self; + }; + + // Add a character to aryu8 + val add = { u8 c -> + _grow(1).buf[len++] = c; + self; + }; + + // Add a plain array to the aryu8 + val addAry = { u8[~] ary -> + _grow(ary#); + copy(buf,len,ary,0,ary#); + len += ary#; + self; + }; + + // Remove x chars from the tail. + val undo = { int x -> + len = len >= x ? len-x : 0; + self; + }; + + // Print ASCII number into aryu8 + val num = { i64 x -> + if( !x ) { add('0'); return self; } + if( x < 0 ) { add('-'); x = -x; } + i64 ten = 1, log = 0; + while( ten <= x ) { ten *= 10; log++; } + for( int i=0; i<log; i++ ) { + ten /= 10; + i64 q = x/ten; + u8 digit = q+'0'; + add(digit); + x -= q*ten; + } + self; + }; + + // Write to fd, returns the number of bytes written (len). + val write = { i32 fd -> i64 ptr = buf; write(fd,ptr,len); }; + }; +struct Scan { + int !x; + u8[~] buf; + new Scan={ u8[~] b -> buf=b; }; + + // Skip whitespace + val skip = { -> + while( buf[x] <= ' ' ) + x++; + return self; + }; + + // True if find required character, and skip it; else False. + val match = { u8 c -> + skip(); + if( buf[x] != c ) return false; + x++; + return true; + }; + + // Parse a simple number + val number = { -> + skip(); + bool neg = match('-'); + i64 n = 0; + while( '0' <= buf[x] & buf[x] <= '9' ) + n = n*10 + (buf[x++] - '0'); + return neg ? -n : n; + }; + }; +struct aryi64 { + u32 !len = 0; + i64[] !buf; + new aryi64={ i64[] b -> buf=b; }; + // Grow as needed + val _grow = { int len2 -> + if( len+len2 < buf# ) return self; + int newlen = buf# * 2; + while( len+len2 >= newlen ) newlen *= 2; + i64[] !buf2 = new i64[newlen]; + for( int i=0; i<buf#; i++ ) + buf2[i] = buf[i]; + buf = buf2; + self; + }; + + // Add a i64 to aryu8 + val add = { i64 c -> + _grow(1).buf[len++] = c; + self; + }; + + // Write to aryu8 + val str = { -> + // TODO: clunky default constructor syntax + var str = new aryu8(new u8[1]).add('['); + for( int i=0; i<len; i++ ) + str.num(buf[i]).add(',').add(' '); + str.undo(2).add(']'); + }; + }; + val parseAryI64 = { u8[~] str -> + Scan !s = new Scan(str); + if( !s.match('[') ) return null; + // Array of parsed results + var nums = new aryi64(new i64[1]); + // Parse a list of numbers + if( !s.match(']') ) { // Handle the empty list + // Parse "123, " until a something else + while( s.x < s.buf# ) { + nums.add(s.number()); + if( !s.match(',') ) + break; + }; + if( !s.match(']') ) return null; // Close the list + } + return nums; + }; + + + // Print string to stdout + val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + return write(1,ptr,str#); + }; + + // Return stdin as a u8[] + val stdin = { -> + var buf = new u8[8*1024]; + i64 ptr = buf; + int len = 0; + while( true ) { + int rez = read(0,ptr,buf#); + if( rez < 0 ) _exit(errno); + len += rez; + if( rez < buf# ) + break; + _exit(-2); // Need to implement + } + // Compress + var dst = new u8[len]; + return copy(dst,0,buf,0,len); + }; + // -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + +val sort = { aryi64 nums -> + var done = false; + while( !done ) { + done = true; + for( var i = 0; i < nums.len-1; i++ ) + if( nums.buf[i] > nums.buf[i+1] ) { + int tmp = nums.buf[i]; + nums.buf[i] = nums.buf[i+1]; + nums.buf[i+1] = tmp; // Swap + done = false; + } + } +}; + +// Read from stdin a line of the form "[ 4, 3, 2, 1]" and print it sorted. +val main = { -> + // Parse array of numbers from stdin + var nums = parseAryI64( stdin() ); + if( !nums ) { + p("stdin must look like [4, 3, 2, 1]"); + return 1; + } + + // Bubble sort array of integers + sort(nums); + + // Print a list of numbers to stdout + nums.str().write(1); + return 0; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig21.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig21.smp new file mode 100644 index 00000000..f09915a1 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig21.smp @@ -0,0 +1,16 @@ +struct s0 { + bool v1; + i16 v2; + int v3; + i8 v4; + byte v5; +}; +while(new s0.v3) + while(new s0.v5<<new s0.v4) {} +if(0) { + if(0) { + flt !P5ZUD4=new s0.v2; + } + while(0) {} +} +return new s0.v1; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig22.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig22.smp new file mode 100644 index 00000000..df605c94 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig22.smp @@ -0,0 +1,15 @@ +val fib = {int n -> + int temp=0; + int f1=1; + int f2=1; + int i=n; + while( i>1 ){ + temp = f1+f2; + f1=f2; + f2=temp; + i=i-1; + } + return f2; +}; + +fib(10); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testNewtonInteger.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testNewtonInteger.smp new file mode 100644 index 00000000..0423585b --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testNewtonInteger.smp @@ -0,0 +1,11 @@ +// Newtons approximation to the square root +val sqrt = { int x -> + int guess = x; + while( 1 ) { + int next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +int cast_int = arg+2; +return sqrt(arg) + sqrt(cast_int); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testStackArguments.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testStackArguments.smp new file mode 100644 index 00000000..b7d52dc5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testStackArguments.smp @@ -0,0 +1,5 @@ +val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, int x8, flt f9, int i10, flt f11, int i12, flt f13, int i14, flt f15, int x16, flt f17 int x18, flt f19 -> + return + i0 + f1+ i2+ f3+ i4+ f5+ i6+ f7+ x8 +f9 + + i10+f11+i12+f13+i14+f15+x16+f17+x18+f19 ; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testJig.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testJig.smp new file mode 100644 index 00000000..5c9d3aa5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testJig.smp @@ -0,0 +1 @@ +int v0=0; v0 = arg && 0== 0 !=0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack1.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack1.smp new file mode 100644 index 00000000..ded92426 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack1.smp @@ -0,0 +1,10 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +int something_specific = 11; + +if (10 < something_specific < 20) { + _p("In Range"); +} else { + _p("Out of Range"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack10-2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack10-2.smp new file mode 100644 index 00000000..d9fb38d5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack10-2.smp @@ -0,0 +1 @@ +return (0 < 1) == (1>0); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack10.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack10.smp new file mode 100644 index 00000000..f92e5b00 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack10.smp @@ -0,0 +1,3 @@ +var stack10 = { int x -> + (x < 1) == (1>x); +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack11-2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack11-2.smp new file mode 100644 index 00000000..b5aac70b --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack11-2.smp @@ -0,0 +1 @@ +return 0 < arg < arg+1 < 4; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack11.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack11.smp new file mode 100644 index 00000000..f50e3512 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack11.smp @@ -0,0 +1,3 @@ +var stack11 = { int x -> + 0 < x < x+1 < 4; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack12-2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack12-2.smp new file mode 100644 index 00000000..575d1b4e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack12-2.smp @@ -0,0 +1 @@ +return 0 != arg != 2; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack12.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack12.smp new file mode 100644 index 00000000..b4f36c2e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack12.smp @@ -0,0 +1,3 @@ +var stack12 = { int x -> + 0 != x != 2; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack13-2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack13-2.smp new file mode 100644 index 00000000..9bde9687 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack13-2.smp @@ -0,0 +1 @@ +return 0 == arg == 1; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack13.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack13.smp new file mode 100644 index 00000000..ae7b38a3 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack13.smp @@ -0,0 +1,3 @@ +var stack13 = { int x -> + 0 == x == 1; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack2.smp new file mode 100644 index 00000000..5590c42f --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack2.smp @@ -0,0 +1,10 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +int score = 75; + +if (60 <= score < 90) { + _p("In Range"); +} else { +_p("Out of range"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack3.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack3.smp new file mode 100644 index 00000000..6a3db406 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack3.smp @@ -0,0 +1,11 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +var sq = { int x -> + x*x; +}; + +int score = 5; + +val str = (sq(2) <= score < sq(3)) ? "In Range" : "Out of range"; +_p(str); +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack4.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack4.smp new file mode 100644 index 00000000..47623b30 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack4.smp @@ -0,0 +1,10 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +int something_specific = 9; + +if (10 < something_specific < 20) { + _p("In Range"); +} else { + _p("Out of Range"); +} +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack5.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack5.smp new file mode 100644 index 00000000..e4660752 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack5.smp @@ -0,0 +1,15 @@ +{i32 i64 u32 -> u32} write="C"; +val _p={u8[~] str -> i64 ptr=str; return write(1,ptr,str#);}; +var sq = { int x -> + x*x; +}; + +int score = 5; + +if (sq(2) <= score < sq(3)) { +_p("In Range"); +} else { +_p("Out of range"); +} + +return 0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack9-2.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack9-2.smp new file mode 100644 index 00000000..f54558f5 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack9-2.smp @@ -0,0 +1 @@ +return (0 < 1) == 1; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack9.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack9.smp new file mode 100644 index 00000000..15979be6 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testStack9.smp @@ -0,0 +1,3 @@ +var stack9 = { int x -> + (x < 1) == 1; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/MergeSortTest-testMergeSort0.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/MergeSortTest-testMergeSort0.smp new file mode 100644 index 00000000..e6478eeb --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/MergeSortTest-testMergeSort0.smp @@ -0,0 +1,35 @@ + val merge_sort = { int[] a -> + int[] !b = new int[a#]; + copy_array (a, 0, a#, b); + split_merge(a, 0, a#, b); + }; + + val split_merge = { int[] b, int begin, int end, int[] a -> + if (end - begin <= 1) + return 0; + int middle = (end + begin) / 2; + split_merge(a, begin, middle, b); + split_merge(a, middle, end, b); + merge(b, begin, middle, end, a); + return 0; + }; + + val merge = { int[] b, int begin, int middle, int end, int[] a -> + int i = begin, j = middle; + + for (int k = begin; k < end; k++) { + // && and || + bool cond = false; + if (i < middle) { + if (j >= end) cond = true; + else if (a[i] <= a[j]) cond = true; + } + if (cond) b[k] = a[i++]; + else b[k] = a[j++]; + } + }; + + val copy_array = { int[] a, int begin, int end, int[] b -> + for (int k = begin; k < end; k++) + b[k] = a[k]; + }; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md b/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md new file mode 100644 index 00000000..fae44126 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md @@ -0,0 +1,40 @@ +# Historical allocation cohorts + +`cohorts.tsv` freezes the 212 compilation entries measured by Chapter 24's +`SpillStats`: 39, 52, 24, 30, and 67 entries for cohorts 20-24. The source files +are deduplicated by contents and named for their first referring test. The +manifest preserves test identity, target, ABI, and the original stopping phase. +`Win64` becomes `win64`, the Chapter 25 ABI spelling. Argument type is i64 and +the replay seed is 123 throughout. + +These inputs were captured from the Chapter 24 tests before this final audit's +new correctness regressions. They are a stable comparison corpus; changing one +requires explaining the resulting break in comparability. Synthetic allocator +and instruction regressions do not contribute allocations to these cohorts. + +Chapter 25 cannot parse all earlier sources unchanged. Adaptations are explicit: + +- String, Scan, and linked S constructors replace `new S { field=...; }` with + declared constructors and arguments. The explicit-receiver scanner functions + become instance methods, preserving their operations. +- The two short-circuit RHS initializer loops become equivalent guarded blocks, + preserving allocation, side effects, and the final result. +- Simple I/O cases include the old `write` binding and print helper directly. + Bubble Sort includes the old library bodies, with namespace prefixes flattened, + explicit constructors, and mutable replacement buffers. This retains the old + workload instead of substituting Chapter 25's substantially revised example. +- Other source texts, including both original Newton float variants, are retained. + +All entries replay **through RegAlloc**, checking scheduled register constraints. +The historical phase column is provenance, not a promise to run those old native +harnesses in Chapter 25. In particular, the adapted Bubble Sort still exposes a +pre-existing ARM extern-data encoding limitation (`i32 errno="C"; return 0;` is +sufficient to reproduce it). Allocation succeeds; ARM encoding does not. That +separate failure remains in the backport queue. Do not count this corpus as +historical runtime coverage. + +`SpillStats` then compiles the current system library through encoding at seed +456, and runs Chapter25Test with its existing seeds and native checks. Together +these form cohort 25. A library or test failure makes the report fail; partial +totals cannot establish an improvement. The ordinary full chapter suite remains +the execution validation for the current compiler. diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/cohorts.tsv b/chapter25/src/test/java/com/seaofnodes/simple/spill/cohorts.tsv new file mode 100644 index 00000000..e1643e39 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/cohorts.tsv @@ -0,0 +1,213 @@ +# cohort test cpu abi original phase source +Chapter20 Chapter20Test.testMergeSort x86_64_v2 SystemV RegAlloc Chapter20Test-testMergeSort.smp +Chapter20 Chapter20Test.testMergeSort riscv SystemV RegAlloc Chapter20Test-testMergeSort.smp +Chapter20 Chapter20Test.testMergeSort arm SystemV RegAlloc Chapter20Test-testMergeSort.smp +Chapter20 Chapter20Test.testNewtonInteger x86_64_v2 SystemV RegAlloc Chapter20Test-testNewtonInteger.smp +Chapter20 Chapter20Test.testNewtonInteger riscv SystemV RegAlloc Chapter20Test-testNewtonInteger.smp +Chapter20 Chapter20Test.testNewtonInteger arm SystemV RegAlloc Chapter20Test-testNewtonInteger.smp +Chapter20 Chapter20Test.testCast x86_64_v2 SystemV RegAlloc Chapter20Test-testCast.smp +Chapter20 Chapter20Test.testCast riscv SystemV RegAlloc Chapter20Test-testCast.smp +Chapter20 Chapter20Test.testCast arm SystemV RegAlloc Chapter20Test-testCast.smp +Chapter20 Chapter20Test.testNewtonFloat x86_64_v2 SystemV RegAlloc Chapter20Test-testNewtonFloat.smp +Chapter20 Chapter20Test.testNewtonFloat riscv SystemV RegAlloc Chapter20Test-testNewtonFloat.smp +Chapter20 Chapter20Test.testNewtonFloat arm SystemV RegAlloc Chapter20Test-testNewtonFloat.smp +Chapter20 Chapter20Test.testBrainfuck x86_64_v2 SystemV RegAlloc Chapter20Test-testBrainfuck.smp +Chapter20 Chapter20Test.testBrainfuck riscv SystemV RegAlloc Chapter20Test-testBrainfuck.smp +Chapter20 Chapter20Test.testBrainfuck arm SystemV RegAlloc Chapter20Test-testBrainfuck.smp +Chapter20 Chapter20Test.testAlloc0 x86_64_v2 SystemV RegAlloc Chapter20Test-testAlloc0.smp +Chapter20 Chapter20Test.testAlloc0 riscv SystemV RegAlloc Chapter20Test-testAlloc0.smp +Chapter20 Chapter20Test.testAlloc0 arm SystemV RegAlloc Chapter20Test-testAlloc0.smp +Chapter20 Chapter20Test.testAlloc2 x86_64_v2 SystemV RegAlloc Chapter20Test-testAlloc2.smp +Chapter20 Chapter20Test.testAlloc2 riscv SystemV RegAlloc Chapter20Test-testAlloc2.smp +Chapter20 Chapter20Test.testAlloc2 arm SystemV RegAlloc Chapter20Test-testAlloc2.smp +Chapter20 Chapter20Test.testArray1 x86_64_v2 SystemV RegAlloc Chapter20Test-testArray1.smp +Chapter20 Chapter20Test.testArray1 riscv SystemV RegAlloc Chapter20Test-testArray1.smp +Chapter20 Chapter20Test.testArray1 arm SystemV RegAlloc Chapter20Test-testArray1.smp +Chapter20 Chapter20Test.testBasic1 x86_64_v2 SystemV RegAlloc Chapter20Test-testBasic1.smp +Chapter20 Chapter20Test.testBasic1 riscv SystemV RegAlloc Chapter20Test-testBasic1.smp +Chapter20 Chapter20Test.testBasic1 arm SystemV RegAlloc Chapter20Test-testBasic1.smp +Chapter20 Chapter20Test.testFlags1 x86_64_v2 SystemV RegAlloc Chapter20Test-testFlags1.smp +Chapter20 Chapter20Test.testFlags1 riscv SystemV RegAlloc Chapter20Test-testFlags1.smp +Chapter20 Chapter20Test.testFlags1 arm SystemV RegAlloc Chapter20Test-testFlags1.smp +Chapter20 Chapter20Test.testFlags2 x86_64_v2 SystemV RegAlloc Chapter20Test-testFlags2.smp +Chapter20 Chapter20Test.testFlags2 riscv SystemV RegAlloc Chapter20Test-testFlags2.smp +Chapter20 Chapter20Test.testFlags2 arm SystemV RegAlloc Chapter20Test-testFlags2.smp +Chapter20 Chapter20Test.testFltArg x86_64_v2 SystemV RegAlloc Chapter20Test-testFltArg.smp +Chapter20 Chapter20Test.testFltArg riscv SystemV RegAlloc Chapter20Test-testFltArg.smp +Chapter20 Chapter20Test.testFltArg arm SystemV RegAlloc Chapter20Test-testFltArg.smp +Chapter20 Chapter20Test.testString x86_64_v2 SystemV RegAlloc Chapter20Test-testString.smp +Chapter20 Chapter20Test.testString riscv SystemV RegAlloc Chapter20Test-testString.smp +Chapter20 Chapter20Test.testString arm SystemV RegAlloc Chapter20Test-testString.smp +Chapter21 Chapter21Test.testFibExport x86_64_v2 win64 Export Chapter21Test-testFibExport.smp +Chapter21 Chapter21Test.testFibExport riscv SystemV Export Chapter21Test-testFibExport.smp +Chapter21 Chapter21Test.testFibExport arm SystemV Export Chapter21Test-testFibExport.smp +Chapter21 Chapter21Test.testAntiDeps1 x86_64_v2 SystemV Encoding Chapter21Test-testAntiDeps1.smp +Chapter21 Chapter21Test.testAntiDeps1 riscv SystemV Encoding Chapter21Test-testAntiDeps1.smp +Chapter21 Chapter21Test.testAntiDeps1 arm SystemV Encoding Chapter21Test-testAntiDeps1.smp +Chapter21 Chapter21Test.testLoop2 x86_64_v2 win64 Encoding Chapter21Test-testLoop2.smp +Chapter21 Chapter21Test.testLoop2 riscv SystemV Encoding Chapter21Test-testLoop2.smp +Chapter21 Chapter21Test.testLoop2 arm SystemV Encoding Chapter21Test-testLoop2.smp +Chapter21 Chapter21Test.testSieve x86_64_v2 win64 Export Chapter21Test-testSieve.smp +Chapter21 Chapter21Test.testSieve riscv SystemV Export Chapter21Test-testSieve.smp +Chapter21 Chapter21Test.testSieve arm SystemV Export Chapter21Test-testSieve.smp +Chapter21 Chapter21Test.testArgCount x86_64_v2 win64 Export Chapter21Test-testArgCount.smp +Chapter21 Chapter21Test.testArgCount riscv SystemV Export Chapter21Test-testArgCount-2.smp +Chapter21 Chapter21Test.testArgCount arm SystemV Export Chapter21Test-testArgCount-2.smp +Chapter21 Chapter21Test.testStringExport x86_64_v2 win64 Export Chapter21Test-testStringExport.smp +Chapter21 Chapter21Test.testInfinite x86_64_v2 SystemV Encoding Chapter21Test-testInfinite.smp +Chapter21 Chapter21Test.testInfinite riscv SystemV Encoding Chapter21Test-testInfinite.smp +Chapter21 Chapter21Test.testInfinite arm SystemV Encoding Chapter21Test-testInfinite.smp +Chapter21 Chapter21Test.testArray1 x86_64_v2 SystemV Encoding Chapter20Test-testArray1.smp +Chapter21 Chapter21Test.testArray1 riscv SystemV Encoding Chapter20Test-testArray1.smp +Chapter21 Chapter21Test.testArray1 arm SystemV Encoding Chapter20Test-testArray1.smp +Chapter21 Chapter21Test.testBasic1 x86_64_v2 SystemV Encoding Chapter20Test-testBasic1.smp +Chapter21 Chapter21Test.testBasic1 riscv SystemV Encoding Chapter20Test-testBasic1.smp +Chapter21 Chapter21Test.testBasic1 arm SystemV Encoding Chapter20Test-testBasic1.smp +Chapter21 Chapter21Test.testNewtonExport x86_64_v2 win64 Export Chapter21Test-testNewtonExport.smp +Chapter21 Chapter21Test.testNewtonExport riscv SystemV Export Chapter21Test-testNewtonExport.smp +Chapter21 Chapter21Test.testNewtonExport arm SystemV Export Chapter21Test-testNewtonExport.smp +Chapter21 Chapter21Test.testPerson x86_64_v2 win64 Export Chapter21Test-testPerson.smp +Chapter21 Chapter21Test.testPerson riscv SystemV Export Chapter21Test-testPerson.smp +Chapter21 Chapter21Test.testPerson arm SystemV Export Chapter21Test-testPerson.smp +Chapter21 Chapter21Test.testString x86_64_v2 SystemV Encoding Chapter21Test-testStringExport.smp +Chapter21 Chapter21Test.testString riscv SystemV Encoding Chapter21Test-testStringExport.smp +Chapter21 Chapter21Test.testString arm SystemV Encoding Chapter21Test-testStringExport.smp +Chapter21 Chapter21AllocTest.testNewtonInteger x86_64_v2 win64 Encoding Chapter20Test-testNewtonInteger.smp +Chapter21 Chapter21AllocTest.testNewtonInteger riscv SystemV Encoding Chapter20Test-testNewtonInteger.smp +Chapter21 Chapter21AllocTest.testNewtonInteger arm SystemV Encoding Chapter20Test-testNewtonInteger.smp +Chapter21 Chapter21AllocTest.testNewtonFloat x86_64_v2 SystemV Encoding Chapter21AllocTest-testNewtonFloat.smp +Chapter21 Chapter21AllocTest.testNewtonFloat riscv SystemV Encoding Chapter21AllocTest-testNewtonFloat.smp +Chapter21 Chapter21AllocTest.testNewtonFloat arm SystemV Encoding Chapter21AllocTest-testNewtonFloat.smp +Chapter21 Chapter21AllocTest.testArray1 x86_64_v2 SystemV Encoding Chapter21AllocTest-testArray1.smp +Chapter21 Chapter21AllocTest.testArray1 riscv SystemV Encoding Chapter21AllocTest-testArray1.smp +Chapter21 Chapter21AllocTest.testArray1 arm SystemV Encoding Chapter21AllocTest-testArray1.smp +Chapter21 Chapter21AllocTest.testString x86_64_v2 SystemV Encoding Chapter21AllocTest-testString.smp +Chapter21 Chapter21AllocTest.testString riscv SystemV Encoding Chapter21AllocTest-testString.smp +Chapter21 Chapter21AllocTest.testString arm SystemV Encoding Chapter21AllocTest-testString.smp +Chapter22 Chapter22Test.testSextFail x86_64_v2 win64 Encoding Chapter22Test-testSextFail.smp +Chapter22 Chapter22Test.testSextFail riscv SystemV Encoding Chapter22Test-testSextFail.smp +Chapter22 Chapter22Test.testSextFail arm SystemV Encoding Chapter22Test-testSextFail.smp +Chapter22 Chapter22Test.testSextFail riscv SystemV Export Chapter22Test-testSextFail.smp +Chapter22 Chapter22Test.testSextFail arm SystemV Export Chapter22Test-testSextFail.smp +Chapter22 Chapter22Test.testSextSuccess riscv SystemV Export Chapter22Test-testSextSuccess.smp +Chapter22 Chapter22Test.testSextSuccess arm SystemV Export Chapter22Test-testSextSuccess.smp +Chapter22 Chapter22Test.testSextSuccess x86_64_v2 win64 Encoding Chapter22Test-testSextSuccess.smp +Chapter22 Chapter22Test.testSextSuccess riscv SystemV Encoding Chapter22Test-testSextSuccess.smp +Chapter22 Chapter22Test.testSextSuccess arm SystemV Encoding Chapter22Test-testSextSuccess.smp +Chapter22 Chapter22Test.testInfiniteReturn x86_64_v2 SystemV Encoding Chapter22Test-testInfiniteReturn.smp +Chapter22 Chapter22Test.testInfiniteReturn riscv SystemV Encoding Chapter22Test-testInfiniteReturn.smp +Chapter22 Chapter22Test.testInfiniteReturn arm SystemV Encoding Chapter22Test-testInfiniteReturn.smp +Chapter22 Chapter22Test.testSextFail2 riscv SystemV Export Chapter22Test-testSextFail2.smp +Chapter22 Chapter22Test.testSextFail2 arm SystemV Export Chapter22Test-testSextFail2.smp +Chapter22 Chapter22Test.testSextFail2 x86_64_v2 win64 Encoding Chapter22Test-testSextFail2.smp +Chapter22 Chapter22Test.testSextFail2 riscv SystemV Encoding Chapter22Test-testSextFail2.smp +Chapter22 Chapter22Test.testSextFail2 arm SystemV Encoding Chapter22Test-testSextFail2.smp +Chapter22 Chapter22Test.testPerson x86_64_v2 win64 Export Chapter22Test-testPerson.smp +Chapter22 Chapter22Test.testPerson riscv SystemV Export Chapter22Test-testPerson.smp +Chapter22 Chapter22Test.testPerson arm SystemV Export Chapter22Test-testPerson.smp +Chapter22 Chapter22Test.testHelloWorld x86_64_v2 win64 Export Chapter22Test-testHelloWorld.smp +Chapter22 Chapter22Test.testHelloWorld riscv SystemV Export Chapter22Test-testHelloWorld.smp +Chapter22 Chapter22Test.testHelloWorld arm SystemV Export Chapter22Test-testHelloWorld.smp +Chapter23 Chapter23Test.testAnd x86_64_v2 win64 Export Chapter23Test-testAnd.smp +Chapter23 Chapter23Test.testAnd riscv SystemV Export Chapter23Test-testAnd.smp +Chapter23 Chapter23Test.testAnd arm SystemV Export Chapter23Test-testAnd.smp +Chapter23 Chapter23Test.testOr x86_64_v2 win64 Export Chapter23Test-testOr.smp +Chapter23 Chapter23Test.testOr riscv SystemV Export Chapter23Test-testOr.smp +Chapter23 Chapter23Test.testOr arm SystemV Export Chapter23Test-testOr.smp +Chapter23 Chapter23Test.testCondSideEffAnd x86_64_v2 win64 Export Chapter23Test-testCondSideEffAnd.smp +Chapter23 Chapter23Test.testCondSideEffAnd riscv SystemV Export Chapter23Test-testCondSideEffAnd.smp +Chapter23 Chapter23Test.testCondSideEffAnd arm SystemV Export Chapter23Test-testCondSideEffAnd.smp +Chapter23 Chapter23Test.testFRefFields x86_64_v2 win64 Encoding Chapter23Test-testFRefFields.smp +Chapter23 Chapter23Test.testAndPtr riscv SystemV Export Chapter23Test-testAndPtr.smp +Chapter23 Chapter23Test.testAndPtr arm SystemV Export Chapter23Test-testAndPtr.smp +Chapter23 Chapter23Test.testOrRhsLoopLocal riscv SystemV Export Chapter23Test-testOrRhsLoopLocal.smp +Chapter23 Chapter23Test.testMethod x86_64_v2 win64 Encoding Chapter23Test-testMethod.smp +Chapter23 Chapter23Test.testOrRhsLoopMemory riscv SystemV Export Chapter23Test-testOrRhsLoopMemory.smp +Chapter23 Chapter23Test.testCondSideEffOr x86_64_v2 win64 Export Chapter23Test-testCondSideEffOr.smp +Chapter23 Chapter23Test.testCondSideEffOr riscv SystemV Export Chapter23Test-testCondSideEffOr.smp +Chapter23 Chapter23Test.testCondSideEffOr arm SystemV Export Chapter23Test-testCondSideEffOr.smp +Chapter23 Chapter23Test.testFuncCall x86_64_v2 win64 Export Chapter23Test-testFuncCall.smp +Chapter23 Chapter23Test.testFuncCall riscv SystemV Export Chapter23Test-testFuncCall.smp +Chapter23 Chapter23Test.testFuncCall arm SystemV Export Chapter23Test-testFuncCall.smp +Chapter23 Chapter23AllocTest.testJig21 x86_64_v2 win64 Encoding Chapter23AllocTest-testJig21.smp +Chapter23 Chapter23AllocTest.testJig21 riscv SystemV Encoding Chapter23AllocTest-testJig21.smp +Chapter23 Chapter23AllocTest.testJig21 arm SystemV Encoding Chapter23AllocTest-testJig21.smp +Chapter23 Chapter23AllocTest.testJig22 x86_64_v2 win64 Encoding Chapter23AllocTest-testJig21.smp +Chapter23 Chapter23AllocTest.testJig22 riscv SystemV Encoding Chapter23AllocTest-testJig21.smp +Chapter23 Chapter23AllocTest.testJig22 arm SystemV Encoding Chapter23AllocTest-testJig21.smp +Chapter23 Chapter23AllocTest.testString x86_64_v2 SystemV Encoding Chapter23AllocTest-testString.smp +Chapter23 Chapter23AllocTest.testString riscv SystemV Encoding Chapter23AllocTest-testString.smp +Chapter23 Chapter23AllocTest.testString arm SystemV Encoding Chapter23AllocTest-testString.smp +Chapter24 Chapter24Test.testAnd x86_64_v2 win64 Export Chapter23Test-testAnd.smp +Chapter24 Chapter24Test.testAnd riscv SystemV Export Chapter23Test-testAnd.smp +Chapter24 Chapter24Test.testAnd arm SystemV Export Chapter23Test-testAnd.smp +Chapter24 Chapter24Test.testJig x86_64_v2 win64 Encoding Chapter24Test-testJig.smp +Chapter24 Chapter24Test.testJig riscv SystemV Encoding Chapter24Test-testJig.smp +Chapter24 Chapter24Test.testJig arm SystemV Encoding Chapter24Test-testJig.smp +Chapter24 Chapter24Test.testOr x86_64_v2 win64 Export Chapter23Test-testOr.smp +Chapter24 Chapter24Test.testOr riscv SystemV Export Chapter23Test-testOr.smp +Chapter24 Chapter24Test.testOr arm SystemV Export Chapter23Test-testOr.smp +Chapter24 Chapter24Test.testCondSideEffAnd x86_64_v2 win64 Export Chapter23Test-testCondSideEffAnd.smp +Chapter24 Chapter24Test.testCondSideEffAnd riscv SystemV Export Chapter23Test-testCondSideEffAnd.smp +Chapter24 Chapter24Test.testCondSideEffAnd arm SystemV Export Chapter23Test-testCondSideEffAnd.smp +Chapter24 Chapter24Test.testFRefFields x86_64_v2 win64 Encoding Chapter23Test-testFRefFields.smp +Chapter24 Chapter24Test.testAndPtr riscv SystemV Export Chapter23Test-testAndPtr.smp +Chapter24 Chapter24Test.testAndPtr arm SystemV Export Chapter23Test-testAndPtr.smp +Chapter24 Chapter24Test.testMethod x86_64_v2 win64 Encoding Chapter23Test-testMethod.smp +Chapter24 Chapter24Test.testStack1 x86_64_v2 win64 Export Chapter24Test-testStack1.smp +Chapter24 Chapter24Test.testStack1 riscv SystemV Export Chapter24Test-testStack1.smp +Chapter24 Chapter24Test.testStack1 arm SystemV Export Chapter24Test-testStack1.smp +Chapter24 Chapter24Test.testStack2 x86_64_v2 win64 Export Chapter24Test-testStack2.smp +Chapter24 Chapter24Test.testStack2 riscv SystemV Export Chapter24Test-testStack2.smp +Chapter24 Chapter24Test.testStack2 arm SystemV Export Chapter24Test-testStack2.smp +Chapter24 Chapter24Test.testStack3 x86_64_v2 win64 Export Chapter24Test-testStack3.smp +Chapter24 Chapter24Test.testStack3 riscv SystemV Export Chapter24Test-testStack3.smp +Chapter24 Chapter24Test.testStack3 arm SystemV Export Chapter24Test-testStack3.smp +Chapter24 Chapter24Test.testStack4 x86_64_v2 win64 Export Chapter24Test-testStack4.smp +Chapter24 Chapter24Test.testStack4 riscv SystemV Export Chapter24Test-testStack4.smp +Chapter24 Chapter24Test.testStack4 arm SystemV Export Chapter24Test-testStack4.smp +Chapter24 Chapter24Test.testStack5 x86_64_v2 win64 Export Chapter24Test-testStack5.smp +Chapter24 Chapter24Test.testStack5 riscv SystemV Export Chapter24Test-testStack5.smp +Chapter24 Chapter24Test.testStack5 arm SystemV Export Chapter24Test-testStack5.smp +Chapter24 Chapter24Test.testStack9 x86_64_v2 win64 Export Chapter24Test-testStack9.smp +Chapter24 Chapter24Test.testStack9 riscv SystemV Export Chapter24Test-testStack9-2.smp +Chapter24 Chapter24Test.testStack9 arm SystemV Export Chapter24Test-testStack9-2.smp +Chapter24 Chapter24Test.testCondSideEffOr x86_64_v2 win64 Export Chapter23Test-testCondSideEffOr.smp +Chapter24 Chapter24Test.testCondSideEffOr riscv SystemV Export Chapter23Test-testCondSideEffOr.smp +Chapter24 Chapter24Test.testCondSideEffOr arm SystemV Export Chapter23Test-testCondSideEffOr.smp +Chapter24 Chapter24Test.testStack10 x86_64_v2 win64 Export Chapter24Test-testStack10.smp +Chapter24 Chapter24Test.testStack10 riscv SystemV Export Chapter24Test-testStack10-2.smp +Chapter24 Chapter24Test.testStack10 arm SystemV Export Chapter24Test-testStack10-2.smp +Chapter24 Chapter24Test.testStack11 x86_64_v2 win64 Export Chapter24Test-testStack11.smp +Chapter24 Chapter24Test.testStack11 riscv SystemV Export Chapter24Test-testStack11-2.smp +Chapter24 Chapter24Test.testStack11 arm SystemV Export Chapter24Test-testStack11-2.smp +Chapter24 Chapter24Test.testStack12 x86_64_v2 win64 Export Chapter24Test-testStack12.smp +Chapter24 Chapter24Test.testStack12 riscv SystemV Export Chapter24Test-testStack12-2.smp +Chapter24 Chapter24Test.testStack12 arm SystemV Export Chapter24Test-testStack12-2.smp +Chapter24 Chapter24Test.testStack13 x86_64_v2 win64 Export Chapter24Test-testStack13.smp +Chapter24 Chapter24Test.testStack13 riscv SystemV Export Chapter24Test-testStack13-2.smp +Chapter24 Chapter24Test.testStack13 arm SystemV Export Chapter24Test-testStack13-2.smp +Chapter24 Chapter24Test.testFuncCall x86_64_v2 win64 Export Chapter23Test-testFuncCall.smp +Chapter24 Chapter24Test.testFuncCall riscv SystemV Export Chapter23Test-testFuncCall.smp +Chapter24 Chapter24Test.testFuncCall arm SystemV Export Chapter23Test-testFuncCall.smp +Chapter24 Chapter24AllocTest.testNewtonInteger x86_64_v2 win64 Encoding Chapter24AllocTest-testNewtonInteger.smp +Chapter24 Chapter24AllocTest.testNewtonInteger riscv SystemV Encoding Chapter24AllocTest-testNewtonInteger.smp +Chapter24 Chapter24AllocTest.testNewtonInteger arm SystemV Encoding Chapter24AllocTest-testNewtonInteger.smp +Chapter24 Chapter24AllocTest.testJig21 x86_64_v2 win64 Encoding Chapter24AllocTest-testJig21.smp +Chapter24 Chapter24AllocTest.testJig21 riscv SystemV Encoding Chapter24AllocTest-testJig21.smp +Chapter24 Chapter24AllocTest.testJig21 arm SystemV Encoding Chapter24AllocTest-testJig21.smp +Chapter24 Chapter24AllocTest.testJig22 x86_64_v2 win64 Encoding Chapter24AllocTest-testJig22.smp +Chapter24 Chapter24AllocTest.testJig22 riscv SystemV Encoding Chapter24AllocTest-testJig22.smp +Chapter24 Chapter24AllocTest.testJig22 arm SystemV Encoding Chapter24AllocTest-testJig22.smp +Chapter24 Chapter24AllocTest.testStackArguments x86_64_v2 win64 Export Chapter24AllocTest-testStackArguments.smp +Chapter24 Chapter24AllocTest.testStackArguments riscv SystemV Export Chapter24AllocTest-testStackArguments.smp +Chapter24 Chapter24AllocTest.testStackArguments arm SystemV Export Chapter24AllocTest-testStackArguments.smp +Chapter24 Chapter24AllocTest.testBubbleSort x86_64_v2 win64 Encoding Chapter24AllocTest-testBubbleSort.smp +Chapter24 Chapter24AllocTest.testBubbleSort riscv SystemV Encoding Chapter24AllocTest-testBubbleSort.smp +Chapter24 Chapter24AllocTest.testBubbleSort arm SystemV Encoding Chapter24AllocTest-testBubbleSort.smp +Chapter21 BrainFuckTest.testBrainFuck x86_64_v2 win64 Export BrainFuckTest-testBrainFuck.smp +Chapter21 BrainFuckTest.testBrainFuck riscv SystemV Export BrainFuckTest-testBrainFuck.smp +Chapter21 BrainFuckTest.testBrainFuck arm SystemV Export BrainFuckTest-testBrainFuck.smp +Chapter21 MergeSortTest.testMergeSort0 x86_64_v2 win64 Export MergeSortTest-testMergeSort0.smp +Chapter21 MergeSortTest.testMergeSort0 riscv SystemV Export MergeSortTest-testMergeSort0.smp +Chapter21 MergeSortTest.testMergeSort0 arm SystemV Encoding MergeSortTest-testMergeSort0.smp diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 7096156f..150afe20 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -1,75 +1,80 @@ # Chapter backport review -This is a queue of pending work. Remove completed corrections from the queue. Independent -corrections should start in the earliest affected chapter and propagate through -every later affected snapshot. A regression in Chapter 25's `Chapter21Test` -does not test the compiler in the `chapter21` directory. - -For now, keep building SSA with incomplete types in Chapter 25. Moving that -architecture earlier, or splitting Chapter 25, is deferred while small changes -establish the review workflow. No renumbering is committed. - -Keep each correction's reduced failure, smallest patch, and test results together -for review. - -## Follow-ups exposed by the Chapter 22 allocator review - -- **Narrow-store register masks:** fixed locally in 22-24, with - `Chapter21Test.testNarrowStores`. Bring the x86 restriction to 20-21, - and the RISC-V restriction to 21; 19's masks and 20's RISC-V mask are - already general-register-only, and 25 already has both fixes. Byte/short stores - cannot consume XMM/FPR values. The old x86 `_sz >= 2` compares a character to - an integer and always accepts XMM; the intended threshold is `'4'`. RISC-V - previously accepted its full memory mask for every width. With Chapter 21's - bias in 22, `testSextSuccess` emitted an invalid FP byte store on RISC-V and - asserted in `StoreX86.encVal` on x86. Preserve cohort data when backporting: - correcting a mask can substantially change spill counts even without tuning. -- **FunPtrNode backport: defer until register allocation work is complete.** The - minimal reproducer is `return {->42;};`; `return sys.io.p;` fails for the same - reason. Both fail on x86, RISC-V, and ARM at the default seed 123. The first - iterative Opto pass preserves the target. The subsequent pruning loop in - `CodeGen.opto` equates no linked calls with no callers for anonymous and `sys.` - functions, clears their unknown-caller Start edge, and deletes their bodies. - Their function-address ConstantNodes have no edge to keep the bodies alive. - The returned pointer survives while its Return disappears from Stop. - - Instruction selection resets NIDs and never selects the deleted function, so - the linker still maps its pointer to an ideal FunNode. In the reduced anonymous - case that node is 256; the x86 machine graph has UID 19. `Encoding.relo` accepts - the stale target and `patchLocalRelocations` indexes `_opStart[256]`. Enlarging - the array would merely hide a missing function body and produce a wrong address. - - `val f = {->42;}; return f;` retains the named function and encodes on all three - targets. An isolated build that excludes anonymous functions from pruning also - encodes both anonymous reproductions, confirming the cause; it does not fix - escaped `sys.` addresses. Cliff's chosen direction is to investigate backporting - Chapter 25's `FunPtrNode`, whose edge to the function Return keeps the function - body alive. This supersedes the proposed address-reference scan. Leave both - examples as documented known failures while finishing the allocator chapters; - do not fold this reachability change into that work. - - After register allocation, find the earliest applicable chapter and carry the - function-pointer representation and its retention rules together: pointer - creation, Opto's unknown-caller pruning, instruction selection, global constant - cloning, and relocation must agree on the retained function. Adapt these to - each chapter without importing unrelated Chapter 25 module/escape machinery. - Validate a returned pointer by calling it, and cover library pointers and - genuinely unused helpers. Chapter 21 lacks this pruning pass and also treats a constant-only - default main differently, so its old encoding-only coverage was not equivalent. - Diagnostic logs are in `chapter22/build/funptr-review`; the reduced sources and - causal trace above are the durable reproduction. -- **String without an explicit return in 22:** use the unchanged source in - `Chapter20Test.testString`, with the same driver and seeds 0-29. All three CPUs - fail before allocation, in loop-tree construction or GCM (missing loop owner, - dead CallEnd, or a FunNode cast to LoopNode, depending on seed). The original - snapshot reproduces the same 90 failures; seed 123 folds the work away. Reduce - this around Chapter 22's default-return/dead-call handling before changing a - central reachability invariant. Do not count a different seed or added return - as fixing this input. +This is a queue of pending work. Completed corrections leave the queue; the +[validation summary](#validation-record) records their scope. Detailed old logs +are disposable build artifacts. Reusable rules live in +[the AI notes](../skills/chapter25-codex-notes.md). + +Introduce independent fixes in the earliest applicable chapter and propagate +them through every affected snapshot. Testing Chapter 25's inherited tests does +not validate the compilers in the earlier chapter directories. Keep building +SSA with incomplete types in Chapter 25 for now; moving that architecture or +renumbering chapters is deferred. + +## Pending corrections + +- **B10: preserve integer widening in `nonZero`, Chapter 24.** Still missing: + `[0,255]` and `[-255,0]` with widening levels 1-3 become level zero. Chapter 25 + passes `_widen` to `make`; 24 does not. Widening first appears in 24, so 15-23's + older `nonZero` needs no patch. The previous audit established the type-level + discrepancy, not a loop-failure reproducer. Source: `51f1f8f4`. +- **FunPtrNode lifetime backport, now next after the allocator review.** + `return {->42;};` and `return sys.io.p;` fail during relocation in Chapter 22 + on all three targets at seed 123. Opto's name-based pruning equates no linked + calls with no callers and deletes anonymous/library function bodies. A plain + function-address ConstantNode keeps the pointer, but has no edge to keep the + Return alive. Instruction selection resets NIDs; the linker retains an ideal + target and `patchLocalRelocations` indexes outside the machine graph. + + Backport Chapter 25's FunPtrNode/Return retention rules together with pointer + creation, unknown-caller pruning, instruction selection, constant cloning, and + relocation. Determine the earliest applicable home; 21 lacks this pruning + pass. `val f={->42;}; return f;` surviving is not a fix for anonymous/library + addresses. Do not enlarge relocation arrays or add an interim address scan. + Validate returned pointers by calling them, including library pointers, while + still deleting genuinely unused helpers. Keep module/escape machinery in 25. +- **Chapter 22 String without an explicit return.** The unchanged source in + `Chapter20Test.testString` fails before allocation in loop-tree construction + or GCM at the historically tested seeds 0-29, on all targets. The original + snapshot has the same failures; seed 123 folds the work away. Reduce default + return/dead-call handling. A new return or a different seed is not a fix; + this historical sweep is not a reason to sweep routine backend tests. +- **Chapter 25 null-dereference diagnostic.** This setup was accepted despite + dereferencing null on the taken arm; investigate separately from B13: + + ```java + struct Point { int x; new Point={int v -> x=v;}; }; + Point?[] !points=new Point?[2]; points[arg]=new Point(42); + Point? p=points[1]; + if(p==null) return p.x; return -1; + ``` + +- **Chapter 18 fuzzer seed `973358943756616234`.** Remains in + `OPEN_FAILING_SEEDS`. The reduction below exposes nullable field lookup with + peepholes disabled and, historically, a mixed-return error with them enabled. + B11 fixes the latter reduced diagnostic; neither it nor Chapter 19's change + from an off/on oracle to worklist-seed comparison proves the full seed fixed. + + ```java + struct s0 { u8 v1; }; + s0? !UmPOLQK=null; + if(0) while(0&UmPOLQK.v1) {} + if(UmPOLQK.v1) {} + return new s0; + while(0) {} + ``` + +- **Chapter 25 ARM extern data.** `i32 errno="C"; return 0;`, compiled through + Encoding with ARM/SystemV, reaches `arm.load_str_imm` with register -1 for the + extern-data value stored by `<clinit>`. Both the saved original and final + compiler reproduce it. This is an extern-data lowering/encoding issue, not + the repaired float-store allocation conflict. The historical Bubble Sort + replay allocates successfully but also exposes this failure if ARM encoding + is requested. Do not describe its allocation statistics as runtime coverage. ## AOT class initialization: larger independent work -Proposed on 2026-09-19; deferred behind the smaller BXX cleanup above. This is +Proposed on 2026-09-19; deferred behind the smaller queue above. This is a substantial, self-contained Chapter 25 change, not an entangled backport. Earlier chapter applicability has not been established. @@ -124,896 +129,125 @@ Chapter 25 suite, including `make -j 4 tests`. | Group | Eventual home | Why not in the small queue yet | |---|---|---| -| Register allocation and spilling | 20 onward | Shared corrections/support now carried through 25; staged allocator/cohort/README reviews are complete through 24, with 25 next. | | Conditional Store and array Load control | Memory/arrays chapters | Reproduce under the earlier alias model before extracting fixes from the new memory implementation. | | SCCP dependencies, function revival, reachability | 24; some foundations may fit 18 | Separate old-IR corrections from new Guard/Escape/BulkMemPhi and external-caller machinery. | | TypeScalar, numeric modes, guards, symbolic fields, open/forward types | Revisit earlier homes later | A connected incomplete-types architecture, including phase ordering and errors. | | BulkMemPhi/MemPhi, private constructor memory, allocation helpers | Revisit memory / constructors / methods | Move invariants and regressions together. | | Serialization, global identity remapping, module escape summaries | Separate compilation | Remain with modules. | -## Register allocation: correctness first, staged improvements +## Register allocation: completed chapter progression -Review on 2026-09-20. The staged plan follows; Chapters 20-24 -have since been implemented and validated as recorded below. Shared corrections -and test support have also been carried through 24-25; their quality/cohort/README -reviews remain pending. Compared RegAlloc, BuildLRG, IFG, -LRG, Coalesce, RegMask, and split support across 20-25, with the original fix -commits. Allocation starts in 20; 19 has instruction selection/register masks -but no coloring allocator. Most changes are in 20->21 and 24->25. The 22->23 -allocator changes are imports/API cleanup; 23->24 has no allocator changes. +The allocator review is complete through Chapter 25. Each README ends with the +introduced technique, measured program cohorts, and commentary. `make spill-stats` +reports actual retained moves, per target and cohort, with assertions enabled. -Cliff's direction: correctness fixes belong at the earliest applicable chapter; -quality improvements should accumulate gradually. Debugging/printing/support -can start in 20. Judge spill changes across a fixed suite, allowing a local -increase when compensated elsewhere. Do not copy the entire Chapter 25 allocator -into 20, and do not classify a whole historical commit by its title. - -### Correctness work to extract - -| Work | Current evidence / source | Earliest intended home | +| Chapter | Additional technique | Final cohort sizes | |---|---|---| -| Register-mask and LRG bookkeeping | Original 20: `RegMask(int)` assigns `bit=64` instead of subtracting 64, and empty `firstReg()` returns 128. `LRG._union` replaces `_machUse` without its `_uidx`, and can retain null from an immutable mask intersection. Fixed in 21; see `7e1deb4c`, `8d6de0e1`. | 20 | -| BuildLRG/IFG instruction contracts | 21 checks null use masks, avoids revisiting CFG projections, processes kills even without an output LRG, and distinguishes an instruction's fixed output from a range narrowed elsewhere. The 25 commutative-input fallback uses `mach.outregmap()` rather than a possibly nonexistent LRG. | 20, after reduced graph/source regressions | -| Self-conflicts and effective splits | 21 visits extending uses before rewriting definitions, permits needed backedge splits, checks intervening clobbers/self-conflicts before reusing splits, and avoids immediately folding away capacity splits. `35057d50`, `cc32b0cf`, and `880329e6` explicitly address failed progress. | 20; preserve Phi parallel-assignment semantics | -| Legal rematerialization | 22 checks a clone's output mask against the use mask before choosing a clone over a move. Otherwise repeated cloning can preserve the original hard conflict. The 25 kill handling chooses the live cloneable value to split rather than the killing instruction (`c05d7df4`). | 20; isolate correctness from ranking cloneable spill candidates | -| Empty-mask split bookkeeping | 25 saves the original def use-count before inserting a split, checks for a missing sample use, and skips null traversal roots. | 20 where the affected helper/path exists | -| Persistent multi-def/fixed-register conflicts | 25 directly splits single-register uses and sometimes splits the deep side of a loop (`c05d7df4`). Its `_ns._len > 5` and related thresholds mix progress with tuning. | Reduce a no-progress case in 20, then extract the smallest sufficient rule; do not transplant thresholds as a proven invariant | -| Encoding and stack ABI support | Correct frame sizing, incoming/outgoing stack arguments, and stack-to-stack move encoding are required once native emission exists (`7e1deb4c`). | 21, where encoding is introduced; retain CPU/ABI distinctions | - -Each correctness packet needs a failure demonstrated against the destination's -old implementation, then allocation completion and legal register use. From -21, also execute native/emulated results. An eight-round cutoff failure is a -correctness failure, not permission to increase the cutoff. Some entries above -are established historical fixes; applicability of the larger 25 changes to -older graphs still needs reproduction. - -### Proposed quality progression - -| Chapter | Additional quality technique | -|---|---| -| 20 | Keep the existing basic coloring, biased coloring, rematerialization, and loop-boundary splitting, corrected for legality/progress. | -| 21 | Conservative copy coalescing, already introduced here. Keep its mask/adjacency correctness fixes with it. | -| 22 | Stronger color preferences: follow loop backedges for bias, improve copy-chain searches, and refine cheap-spill ordering for callee saves/cloneables. | -| 23 | Group popular single-def values by their uses' required register classes instead of splitting each use. Include safe use-list mutation and call-crossing restrictions when introduced. | -| 24 | Try cold splits first for loop-Phi self-conflicts, with a remembered one-attempt limit and aggressive fallback. The delay is optional; its fallback is mandatory. | -| 25 | Rank recovered live-range area against loop-scaled split cost (`a03bc567`), plus any further measured tuning. | - -This progression would move some heuristics currently bundled into 21 later; -it is not just a forward copy. Keep each introduced technique in subsequent -chapters and update the chapter prose with it. Chapter 20's README already -discusses popular-value grouping and coalescing beyond its current code, so -that prose needs realignment too. The one-attempt loop-Phi delay from -`a03bc567` is a quality feature with its own progress safeguard, not a reason -to add persistent deferral state to the first allocator chapter. - -### Support and measurement - -- Start deterministic split ordering, null-safe split printing, useful LRG/mask - diagnostics, and an optional function-local-edge verifier in 20. Preserve the - existing side-effect-free `_` printer accessors. Actual stack offsets require - the frame layout introduced in 21; module-specific exceptions stay in 25. -- Record actual `_spills` and `_spillScaled` for each compilation, keyed by test, - CPU, ABI, and fixed seed. Both count retained SplitNodes; `_spillScaled` weights - each by `8^loopDepth`. These are move/split metrics, not solely memory traffic. -- Use one fixed optimizer seed for routine backend validation. Seeds shuffle - IterPeeps/Opto worklists, whose output should normalize modulo NIDs and equivalent - operand orderings; similar post-Opto graphs give little additional allocation, - scheduling, or encoding coverage. Reserve seed sweeps for optimizer/worklist - investigations or demonstrated order-sensitive failures. Inspect post-Opto - differences before multiplying backend runs. Prefer varied programs, register - constraints, targets/ABIs, and execution checks for allocator coverage. -- Compare total scaled counts as the existing quality measure, and report raw - totals plus the largest local changes. Report per CPU/ABI as well as the whole - suite so a regression on one target is visible. Include compilations without - a current golden spill assertion; do not exclude failures or disable checks - to obtain an aggregate. Freeze test membership and seeds for each comparison. -- Compare before/after within each chapter. For tutorial progression, also use - the common program/target subset: totals from different suites or changed IR - are not a controlled allocator comparison. -- Existing helpers assert individual spill goldens (often with tolerance). - Review those local changes against the measured aggregate before updating - expectations. Correctness tests must assert completion/results independently - of the heuristic's exact spill count. -- `splitBypass` originally scanned from `j-1` with `idx++` throughout 20-25, - reaching its own destination and rejecting nonadjacent bypasses. Corrected - through 25 with intervening kill-mask checks and a regression. - Pre-color copy reuse also checks fixed-register definitions before they have - an assigned `_reg`. Chapter 25 is not a complete correctness reference. - -Suggested execution order: support/measurement, small mask/LRG correctness -fixes, constrained-register and self-conflict regressions/fixes, then one -quality technique at a time. Run each affected snapshot's full suite at each -accepted boundary. Chapters 20-24 have now been implemented; stop for Cliff's review before 25. -Review each chapter's README along the way. Chapter 21's encoding discussion -has been shortened, with the bit-level notes retained as a separate reference. End each README with its -RegAlloc improvement, measured cohort table, and commentary; the Chapter 25 -table must have rows for cohorts 20-25 using the Chapter 25 compiler. +| 20 | Basic coloring, rematerialization and loop splitting, with shared legality/progress fixes | 39 | +| 21 | Conservative copy coalescing | 39, 52 | +| 22 | Stronger copy-chain/backedge bias and cheap-spill ordering | 39, 52, 24 | +| 23 | Group popular single-def uses by compatible register classes | 39, 52, 24, 30 | +| 24 | One cold-only attempt for loop-Phi self-conflicts, then mandatory fallback | 39, 52, 24, 30, 67 | +| 25 | Existing area/cost ranking and later conflict strategies | 39, 52, 24, 30, 67, 10 | + +Shared corrections include RegMask/LRG bookkeeping, null use masks, kills without +an output LRG, self-conflict splitting, compatible rematerialization, clobber-aware +copy reuse/bypass, deterministic ordering, and side-effect-free diagnostics. The +final audit adds the missing narrow x86 masks in 20-21 and RISC-V mask in 21; +fixed-neighbor color bias in 20-25; and ARM memory register-bank selection, +float opcodes, and matching emulator fixes in 21-25. + +Chapter 25's additional fixed-use/deep-side splitting thresholds remain there. +The def-use-count snapshot and null-use guard support its extra split branch; +20-24 do not have that branch. Earlier kill handling subtracts killed registers; +25 can choose to split cloneables earlier. No independent earlier-chapter +correctness failure was established for these strategy differences. They are +not uncompleted promises to copy the complete allocator backwards. Compilation- +unit ownership and void/metadata handling also stay with the later representation. + +The final ARM failure was substantive: the original Newton float programs reached +the allocation round limit because a float store demanded a GPR; the deeper loop +split kept cutting the wrong portion of the range. Permitting the supported FP +registers removes that conflict. Encoding must then use the allocated register +bank, with five-bit register numbers, for both immediate and indexed loads/stores. +The emulator must preserve floating bits and scale double offsets by eight. + +Chapter 25 freezes the 212 earlier compilation entries in +[documented source fixtures](../chapter25/src/test/java/com/seaofnodes/simple/spill/README.md). +Constructor/library adaptations change IR, so this is a program-cohort comparison, +not identical machine graphs. Those rows replay allocation and legality checks; +current Chapter25Test native checks and a fresh system-library encoding contribute +ten more allocations. Total: **2,597 moves / 5,579 loop-weighted moves** over 222 +compilations. Chapter 25's area/cost implementation is retained. Substituting the +earlier ranking saves five moves on the clients but fails a fresh `sys` allocation +at the eight-round limit; a failed library cannot be omitted from the comparison. + +The earlier tables are refreshed where the final mask fixes changed them: +Chapter 20 is 238 / 357; Chapter 21 is 840 / 1,456. Coalescing on/off now saves +230 / 433 moves in Chapter 21 with identical legality fixes. Chapters 22-24's +aggregate values are unchanged. Full details and comparison limits belong in +the individual READMEs rather than a second evolving set of tables here. ## Review and test protocol -1. Run the destination's unmodified `make tests`. Record baseline failures and - resolve them before accepting a compiler backport into that chapter. -2. Add a deterministic regression proving the old failure. Prefer tiny source - programs; use encoding checks when register placement is the property at issue. -3. Apply the smallest correction; run the focused regression and full chapter - `make tests`. Stop for Cliff's review before the next trial fix. -4. Propagate the accepted fix and regression through every affected later - snapshot. Run each snapshot's full `make tests`, not just 25's inherited tests. -5. Run TypeTest for lattice changes and rebuild system objects when compiler - changes invalidate their IR/native code. Force a full Java rebuild when shared - APIs or constants change: older Makefiles do not track all Java dependencies. - Do not weaken checks or drop tests. -6. Report chapters, commands, and results for review; remove completed items from - this queue. Keep unrelated dirty changes; - do not push without explicit approval. - -The top-level runner supports all 25 chapters: - -```sh -make lib # dependencies, before tests on a fresh checkout -make tests -make -k tests # visit all chapters; failures still fail the command -make tests CHAPTERS="chapter21 chapter22" -make tags release CHAPTERS="chapter01 chapter24 chapter25" -``` - -Runs are sequential, and child failures propagate. `make tag` aliases `tags`. -Java, GNU make, bash, ctags (for tags), and the existing native test tools must -be on PATH. Early release targets package classes into jars; they do not imply -standalone executable compiler drivers. Older Makefiles discover jars when make -starts, so run `make lib` separately before `make tests`. +1. Establish the destination baseline. Reproduce a real failure with a small + source or constrained machine graph before classifying a change as a bug fix. +2. Apply the smallest correction, propagate it to all affected snapshots, and + run each snapshot's focused checks and full `make tests`. Respect the current + user-authorized review boundary; do not push without explicit instructions. +3. Force Java rebuilds when older Makefiles miss dependencies. Rebuild `sys.o` + after compiler changes; include a fresh library compilation in allocator + measurements rather than relying on an up-to-date object. +4. Keep legality/progress/runtime checks separate from spill expectations. + Eight-round exhaustion is a failure; neither increasing the cutoff nor + changing a golden proves it fixed. Preserve test membership, targets/ABIs, + and fixed seeds. Do not sweep optimizer seeds for routine backend validation. +5. Report aggregate and local changes. Use same-compiler heuristic comparisons; + changed frontend/lowering graphs are not allocator-only measurements. +6. Keep edited text LF-only, preserve unrelated changes, and run `git diff --check`. + +The top-level runner accepts explicit chapter lists, e.g. +`make -k tests CHAPTERS="chapter20 chapter21"`. Tests in 25 alone are insufficient. ## Validation record -Historical results below are dated evidence, not a substitute for a fresh -baseline. Logs live in ignored build directories and may no longer exist. -Reusable implementation lessons are in `skills/chapter25-codex-notes.md`. - -### Chapter 24 allocator: ready for review, 2026-09-20 - -Introduced Chapter 25's cold-first loop-Phi self-conflict splitting in 24. -Remember each deferred Phi across rebuilt live ranges; a second conflict uses -ordinary aggressive splitting. The graph regression covers both a Phi conflict -and a backedge-only conflict where the first attempt makes no graph change. -It fails with the saved allocator and with a deliberately disabled fallback, -and passes in 24 and 25 (where this strategy was already present). - -Kept cohorts 20-23 at 39 / 52 / 24 / 30 allocations, including the earlier -64-bit Person, guarded String, and smaller emulator argument list. Chapter 24's -revised Jig, BubbleSort, Newton, and stack-argument cases move to Chapter24AllocTest; -its own existing tests add the rest of cohort 24. Native/emulator helpers retain -24's inline-source APIs. Restored the ARM BrainFuck check's own result pointer in 24-25. - -The frozen Chapter20Test.testString exposes a pre-existing CallEndNode.idealize -NPE on all three targets, before allocation. Chapter 24's new dominator loop -lost 23's null termination check. Restored that check and avoid adding a null -dependency when no enclosing function is found; 25 uses a different inliner. -The unchanged String test fails against the original snapshot and passes after -this local correction. Both sides of the allocator comparison include the fix. - -| Cohort, using Chapter 24 | Allocations | Raw splits | Weighted splits | -|---|---:|---:|---:| -| 20 | 39 | 331 | 457 | -| 21 | 52 | 436 | 975 | -| 22 | 24 | 67 | 67 | -| 23 | 30 | 66 | 115 | -| 24 | 67 | 432 | 1,342 | -| **Total** | **212** | **1,332** | **2,956** | - -With only cold-first splitting absent, totals are 1,338 / 2,962: six fewer moves -and six fewer weighted moves. Per-target raw/weighted totals are ARM 430 / 710, -RISC-V 451 / 745, x86 SystemV 152 / 285, and x86 Win64 299 / 1,216. The respective -savings are 2 / 2, 1 / 1, 1 / 1, and 2 / 2. RISC-V cohort-20 MergeSort adds one; -other MergeSort cases, Sieve, and ARM testFlags2 offset it. Native MergeSort's -weighted expectation becomes 34 (observed 35 without this heuristic), replacing -the older loose 40 expectation. No allocation or execution failure was hidden. - -On cohorts 20-23 alone, 23's 933 / 1,745 becomes 900 / 1,614. Of that change, -only 6 / 6 is the new allocator rule; other compiler changes account for 27 / 125. -Reviewed the README, labelled its SSA examples as pseudocode, corrected which -Phi is available at loop exit, and avoided implying a constant value proves a -loop removable. It ends with the cold-first explanation, cohort table, and -controlled comparison. Area/cost ranking and Chapter 25's cohort review remain. - -Validation: the original 24 suite passed 456 + 1 fuzzer. Final `make -j 4 tests` -passes 470 + 1; `make spill-stats` passes 106 tests / 212 allocations, including -runtime, register/ownership, and quality checks. The forwarded regression passes -25's full 465 tests across six groups. Snapshots, comparisons, and negative -controls are in `chapter24/build/regalloc-review`; 25's full log is in its -`build/regalloc-review/full.log`. Edited files use LF endings. - -### ARM calls and stack frames: corrected in 21-25, 2026-09-20 - -The Chapter 23 README vector example exposed ordinary BL corrupting an argument -register in the emulator and RetARM subtracting eight times the frame size. -FunARM also emitted ADD with a wrapped negative immediate, masked by the -emulator's signed decoding; RET omitted its X30 operand. Corrected the encoder -and emulator together in 21-25, the first chapters with actual ARM encoding. -Frames use SUB/ADD with byte counts and 16-byte alignment, including leaf spills. -Negative arithmetic immediates switch ADD/SUB rather than wrapping. BL writes -only X30; RET/BLR use their encoded register (read before overwriting X30). -Chapter 21's older decoder already avoided BL writeback, but did not execute RET. - -Instruction regressions and recursive calls check actual return values, emitted -frame/RET words, preserved registers, stack restoration, and bounded completion. -The vector-growth regression starts at 23, where struct methods arrive, and uses -25's explicit constructor syntax there. All regressions fail against the saved -pre-fix compiler/emulator. The original README example now returns 511 on ARM, -matching RISC-V, and restores SP. Full `make -j 4 tests` passes in 21 (404 + 1 -fuzzer), 22 (419 + 1), 23 (441 + 1), 24 (456 + 1), and 25 (464 across six groups). -Spill reports retain the same allocation counts and raw/weighted totals: -21: 91 allocations, 884 / 1,794; 22: 115, 838 / 1,496; 23: 145, 933 / 1,745. -Logs and saved pre-fix classes are under each chapter's `build/arm-call-review`. - -### Chapter 23 allocator: ready for review, 2026-09-20 - -The prior batch already supplied shared correctness/support through 25. This -pass keeps Chapter 22's color bias/cheap-spill ordering and introduces popular-use -grouping: a single-definition empty-mask range with more than two fixed-register -uses may share copies by compatible register class. Existing same-depth split -fallback remains; cold-first splitting and area/cost ranking remain for 24/25. - -Simplified grouping to one pass. Intersecting a class preserves compatibility -with all earlier users of that class; new classes are disjoint, so rescanning -is unnecessary. Snapshot distinct users before rewiring, skip null register -masks, and count each call once even if it uses the value in several slots. -Values used by multiple calls still fall back to ordinary splitting. The old -code throws a null-mask NPE in the new reduced graph regression. Its corrected -version checks shared copies, overlapping masks, repeated input edges, preserved -scheduling dependencies, and one-call/two-call handling. Carried this same fix -and regression through 24-25 to avoid repeating its review in later chapters. - -Added `make spill-stats` with frozen cohorts 20-23. Keep `person21`, and preserve -21's guarded String file as `stringHash21`; 23's simplified String and two newly -enabled Jig encoding tests live in Chapter23AllocTest. Cohort 23 also includes -its two executed RISC-V short-circuit regressions. The reporter defers quality -failures while still executing remaining targets/results, and exits nonzero. -Restored the inherited ARM BrainFuck check to use the ARM result pointer. - -| Cohort, using Chapter 23 | Allocations | Raw splits | Weighted splits | -|---|---:|---:|---:| -| 20 | 39 | 332 | 458 | -| 21 | 52 | 450 | 989 | -| 22 | 24 | 67 | 67 | -| 23 | 30 | 84 | 231 | -| **Total** | **145** | **933** | **1,745** | - -The saved original compiler, corrected grouping, and a controlled ablation -which disables only the grouping dispatch all produce these same totals. -There is **no demonstrated spill improvement** from grouping on this suite. -By target the totals are ARM 303 raw / 464 weighted, RISC-V 324 / 499, -x86 SystemV 153 / 286, and x86 Win64 153 / 496. The new machine-graph regression -covers behavior that the program suite does not distinguish; it is excluded -from the original-compiler measurement and contributes no allocation statistics. - -Across the earlier cohorts, Chapter 22's 838 / 1,496 becomes 849 / 1,514 here. -These are different compilers, not an allocator-only comparison: the frozen -Chapter 20 String source survives optimization in 23 (9 + 4 + 3 weighted moves) -where 22 folded it away. Its goldens are updated accordingly. Array type printing -also changes `[u8]` to `[]u8`; only its rendered expectation changes. - -The original Chapter 23 full suite passed 428 + 1 fuzzer. Final `make -j 4 tests` -passes 437 + 1; `make spill-stats` passes 72 tests / 145 allocations, including -quality, ownership, register, native, and emulator checks. The forwarded grouping -fix passes full 24 (452 + 1) and 25 (460 across six groups) suites. Original -snapshots, controlled ablation, and detailed logs are under -`chapter23/build/regalloc-review`; later chapter logs are in `build/grouping-review`. - -Reviewed the README's type discussion and vector example, corrected buffer -installation/mutability/initialization and object-versus-array storage, and ended -it with the grouping explanation, cohort table, and the unchanged ablation -result. Its ARM execution failure is corrected in the call/frame record above. -FunPtrNode reachability work remains deferred until the allocator reviews finish. - -### Shared allocator fixes/support: forwarded through 25, 2026-09-20 - -At Cliff's request, carried the common Chapter 22 corrections into 23-25 in -this review batch, avoiding repeated chapter-by-chapter review of the same -changes. Preserved each later allocator's existing grouping, split-delay, and -area/cost choices; the staged quality/cohort/README reviews still resume at 23. - -The shared packet includes bounded register-mask iteration and nonempty -single-bit tests; commutative BuildLRG output fallback/null masks; resultless -kill handling; fixed-register clone progress; null sample/traversal guards; -and backward copy bypass with kill masks and uncolored fixed definitions. -Chapters 23-24 also receive the corrected clone adjacency/multiple-use test, -narrow-store masks, and native process exit-status assertions. Chapter 25 -already has the store/exit-status fixes and retains its module-aware verifier. - -Forwarded all eight RegAllocTestSupport diagnostic groups and Chapter20Test/ -Chapter21Test hooks. Generic allocation, encoding, native, and emulator helpers -use CheckedCodeGen, whose regAlloc override checks function ownership, register -masks, two-address constraints, and Phis immediately after allocation. Encoding -adds untyped branches and rewrites tail calls, so running these checks afterward -is too late: even Call.regmap may consult CFG.fun. This test-only hook preserves -25's driver serialization/import-unlink ordering. Chapter 22 uses the same hook. - -Unmodified destination baselines passed. Against their saved main classes, -five diagnostic groups fail in 23/24 (masks, resultless kills, clone progress, -commutative Phi fallback, copy clobbers), and three fail in 25 (masks, clone -progress, copy clobbers). All eight pass in all three corrected destinations. -Final `make -j 4 tests` passes 23: 428 + 1 fuzzer, 24: 451 + 1 fuzzer, -and 25: 459 tests across all six groups (8 + 386 + 34 + 18 + 1 + 12). -Chapter 22 still passes 416 + 1 fuzzer; its separate `make spill-stats` passes -55 tests / 115 allocations with the unchanged 838 raw / 1,496 weighted total. - -For this common-fix comparison, froze each destination's existing local program -suite and default seed. Included its Chapter20-24 allocator/native cases as -applicable, BrainFuck, and MergeSort; excluded diagnostic graphs/new regressions. -These are within-chapter before/after comparisons, not the historical cohort -rows needed for the later README reviews. In particular, 25's module suite is -covered by the full tests, not included in these spill sums. - -| Compiler / same local suite | Allocations | Raw before | Raw after | Weighted before | Weighted after | -|---|---:|---:|---:|---:|---:| -| 23 | 119 | 629 | 614 | 1,511 | 1,279 | -| 24 | 174 | 968 | 953 | 2,620 | 2,381 | -| 25 | 146 | 660 | 656 | 1,255 | 1,244 | - -| Compiler | ARM weighted | RISC-V weighted | x86 SystemV weighted | x86 Win64 weighted | -|---|---:|---:|---:|---:| -| 23 | 413 -> 343 | 417 -> 345 | 95 -> 95 | 586 -> 496 | -| 24 | 643 -> 573 | 647 -> 575 | 95 -> 95 | 1,235 -> 1,138 | -| 25 | 348 -> 347 | 346 -> 343 | 123 -> 114 | 438 -> 440 | - -Changed goldens only after measuring the aggregate: in 23/24, NewtonInteger -Win64 55 -> 48, Sieve Win64 257 -> 186 / RISC-V 160 -> 92 / ARM 160 -> 94, -and arg_count Win64 42 -> 32. In 25, NewtonFloat SystemV 48 -> 40 and arg_count -Win64 31 -> 35. That local increase is accepted against the overall reduction. -All measured cases now complete their legality, quality, native/emulator checks: -53 tests in 23, 77 in 24, and 67 in 25. Logs, original classes, and disposable -measurement sources are under each chapter's `build/forward-regalloc`. -The separate FunPtrNode reachability backport remains deferred as requested. - -### Inlined return typing and ARM emulator: corrected, 2026-09-20 - -The ARM seed-9 String failure was an optimizer bug: inlining can delete a FunNode -while its Return still carries live control, memory, and data. ReturnNode.compute -mistook the deleted entry for an unreachable return and supplied Top to its -caller. Chapter 20 introduced direct use of the linked Return's type, exposing -this stale guard. Removed it in 20-21, matching the existing 22-25 implementation. -Chapter 19 does not read that linked return type and passes the reduced probe. - -Reduced source: `struct S { int x; }; val f={ S s -> s.x=g(); }; -val g={ -> 123; }; S !s=new S; return f(s);`. The old 20 compiler returns null -instead of 123 at seed 58; 21 fails at seed 8. The regression checks interpreted -results across seeds 0-63 in Chapter20Test in every snapshot 20-25. - -Execution then exposed missing register-register SUB decoding in EvalArm64. -Added the unshifted SUB form already emitted by Simple in 21-25. The matching -Chapter21Test checks positive/negative results, 64-bit overflow, and preserved -flags; it traps with the old emulator. The original String source at seed 9 now -encodes and executes on both ARM and RISC-V, producing the independently computed -hash `-2449306563677080489`. All 1,170 encoding/register checks pass over the frozen -13-program cohort, three targets, and seeds 0-29. - -Fresh baselines passed before edits. Full suites after correction: 20: 376+1; -21: 401+1; 22: 399+1; 23: 418+1; 24: 441+1; 25's six groups: -8, 378, 34, 18, 1, 12. Spill totals are unchanged: Chapter 20 remains 236 splits / -355 weighted; Chapter 21's two cohorts remain 401/653 and 483/1,141. These regressions -are excluded from spill measurements. Logs/reducers are in each affected chapter's -ignored `build/arm-top`; the earlier chapter-by-chapter allocator review gate remains. - -### Chapter 22 allocator: ready for review, 2026-09-20 - -Carried forward the corrected Chapter 21 allocator and its diagnostic checks, -retaining native frame/call support (`CallEndMach` in 22). Five inherited -regressions fail against the original 22 classes: mask iteration/empty masks, -resultless register kills, fixed-register clone progress, commutative Phi fallback, -and copy bypass across clobbers. All eight diagnostic groups pass now. - -Chapter 22 keeps the stronger copy-chain and loop-backedge color bias, and cheap -cloneable/callee-save spill ordering. Cloneable candidates must have samples; -coalescing can leave either absent. The adjacent-use test now compares -`defIndex+1 < useIndex`, not `defIndex < useIndex+1`, and treats multiple uses -explicitly. Popular-use grouping is removed for introduction in 23; cold loop -split deferral and area/cost ranking remain for 24 and 25. - -The native test helper had lost its exit-status assertion. Restored checking of -its full integer exit code; `testNativeExitStatus` proves an empty-output program -returning 7 fails. `testNarrowStores` first failed against the old RISC-V mask, -then against the old x86 mask; both now reject FP registers for byte/short stores, -and signed/unsigned RISC-V byte/short writes execute with the expected bytes. -These restrictions already exist in 25; remaining destinations are queued above. - -Preserved cohorts 20 and 21 rather than silently accepting changed inputs: -`person21` holds the original 64-bit age example, and `testInfiniteReturn` belongs -to 22 while the old loop remains in 21. Cohort 22 includes its new allocation -programs and repeated encoding/emulator compilations; diagnostic tests stay out. - -| Cohort, all using Chapter 22 | Compilations | Original splits | Current splits | Original weighted | Current weighted | -|---|---:|---:|---:|---:|---:| -| Chapter 20 | 39 | 322 | 324 | 448 | 443 | -| Chapter 21 | 52 | 465 | 447 | 1,221 | 986 | -| Chapter 22 | 24 | 67 | 67 | 67 | 67 | -| **Total** | **115** | **854** | **838** | **1,736** | **1,496** | - -The original full suite passed 399 tests plus the fuzzer. Its frozen-cohort run -completed all 115 allocations and execution checks, with 15 differences from -Chapter 21's spill expectations. The final `make -j 4 tests` passes 416 tests plus -the fuzzer; `make spill-stats` passes 55 tests, 115 allocations, and all quality, -register-legality, function-ownership, native, and emulator checks. Sources and -expectations were force-recompiled before checking. The README ends with the -cohort table and explains the metrics; its FFI examples now match `sys.smp`. - -A controlled ablation substitutes only Chapter 21's IFG bias/ordering, keeping -all other code and the new narrow-store restrictions fixed. It completes all -115 allocations and runtime checks: 885 splits / 1,543 weighted, versus 838 / -1,496 with the new preferences, a 47 weighted move (3.0%) improvement. The scratch -ablation expects 42 instead of 41 bytes for the x86 narrow-store example because -its chosen registers need an extra REX byte; runtime and mask checks remain on. -Quality differences are reported with nonzero exit status, not suppressed. - -| Target/ABI, all cohorts | Compilations | Chapter 21 preferences, weighted | Chapter 22 preferences, weighted | -|---|---:|---:|---:| -| x86 SystemV | 22 | 267 | 268 | -| x86 Win64 | 15 | 414 | 415 | -| RISC-V SystemV | 39 | 437 | 407 | -| ARM SystemV | 39 | 425 | 406 | - -Against the controlled ablation, BrainFuck saves 14 on RISC-V and 6 on ARM in -both cohorts; ARM `testAlloc2` saves 4. Several MergeSort variants and RISC-V Sieve -increase by one. Against the original mixed snapshot, Sieve saves 72 weighted -moves on each target and Win64 argCount saves 10. This shows why individual spill -goldens are reviewed against the aggregate rather than requiring every case to -improve. Chapter totals also reflect lowering: the frozen String example has no -explicit return and folds away at seed 123 in 22. - -The supplementary 13-program, three-target, 30-seed encoding sweep completes -990 of 1,170 compilations with register checks. The remaining 180 fail on String -(before allocation) and FltArg (relocation); the original classes reproduce all -180 and additionally fail five allocator diagnostic groups per seed. No new -program failures were introduced by the allocator work. The two source-level -failures are queued above, not hidden by changing inputs, seeds, or expectations. -Cliff clarified after this run that optimizer seed variation is not productive -routine allocator coverage: normalized post-Opto graphs should produce similar -backend work. Retain these historical reproductions, but use fixed-seed backend -validation going forward; seed variation belongs to optimizer investigations. -Stop for Cliff's review before starting Chapter 23. - -### Chapter 21 allocator: ready for review, 2026-09-20 - -Carries the Chapter 20 legality/progress/support fixes into 21 while retaining -native frame/ABI handling and conservative coalescing. Stronger color bias, -clone/callee-save ranking, and popular-use grouping are deferred to the planned -later chapters. The existing loop-entry-tail treatment remains; removing it -increased weighted counts in a controlled trial. Coalescing's mask, interference, -capacity rollback, and adjacency-remapping checks pass. Five inherited regression -cases fail against the original compiler and pass now: mask iteration/empty masks, -resultless kills, incompatible clone/use classes (round limit), commutative Phi -uses, and copy cleanup across clobbers. The other two inherited cases already pass. - -`make -j 4 tests`: original 385 + 1; corrected 399 + 1 at the allocator boundary (401 + 1 after the return/emulator -corrections above), after forced rebuilds, -including native x86/Win64 and RISC-V/ARM emulator checks. All 1,170 allocation -and register-constraint checks pass for the 13 frozen Chapter 20 inputs, three -CPUs, and seeds 0-29. The subsequent encoding sweep also passes after the return-typing correction -recorded above; the original ARM seed-9 failure is resolved. -Native harnesses now retain full process exit codes, and ARM BrainFuck checks its -own result pointer. `make spill-stats` passes all 45 selected tests (43 at the allocator boundary) and records -91 compilations; spill-golden mismatches are deferred during reporting so they do -not suppress later targets/runtime checks, but still make the command fail. - -| Cohort, all using Chapter 21 | Compilations | Original splits | Current splits | Original weighted | Current weighted | -|---|---:|---:|---:|---:|---:| -| Chapter 20, three SystemV targets | 39 | 340 | 401 | 445 | 653 | -| Chapter 21, fixed Windows native/emulator suite | 52 | 454 | 483 | 1,175 | 1,141 | -| Total | 91 | 794 | 884 | 1,620 | 1,794 | - -Same corrected compiler without coalescing: 1,074 splits / 1,921 weighted; with -coalescing: 884 / 1,794, saving 190 / 127. Relative to the original combined -heuristics, staging costs 174 weighted moves (+10.7%). RISC-V BrainFuck is the -largest regression; sieve improves on all three targets. Do not claim an overall -quality improvement over the original snapshot. Chapter-to-chapter raw totals -also reflect changed lowering and native ABI obligations, not just coalescing. - -Frozen Chapter 20 sources (including original BrainFuck/MergeSort) now reside in -Chapter20Test. The four revised source/ABI cases formerly there are preserved in -Chapter21AllocTest and counted in 21; its native BrainFuck/MergeSort variants also -belong to 21. No diagnostic graphs count toward quality totals. The README now -summarizes encoding/ELF, links the retained encoding reference, and ends with -coalescing, both cohort rows, and the controlled comparison. Logs and isolated -baseline/ablation sources are under `chapter21/build/regalloc-review` (ignored). -The allocator changes remain confined to Chapter 21; the subsequent return/emulator -correction is recorded separately above. Chapter 22 allocator work is recorded below the review heading. - -### Chapter 20 allocator: ready for review, 2026-09-20 - -Implemented only in 20, per Cliff's chapter-by-chapter review gate. Corrected -high-word/empty register masks and boundary iteration, LRG mask merging/use-slot -bookkeeping, null register-mask dependencies, commutative outputs used by Phis, -CFG projection visitation, and kills from instructions without output LRGs. -Splits now preserve progress through self-conflicts/backedges and intervening -clobbers. Rematerialization must satisfy the use mask; fixed-register clones -with flexible uses go through use-side splitting instead of a no-op simple -split. Copy cleanup scans backward and respects both fixed definitions and kill -masks. Removed the unused `splitEmptyMask` path and its `_killed` bookkeeping. - -Support includes deterministic failed-range ordering, null-safe split printing, -a function-local-edge diagnostic, and `make spill-stats`. The program tests also -check assigned register masks, two-address constraints, and Phi agreement. -Seven small machine-graph/mask regressions fail against the saved original -implementation and pass after correction, including a round-limit failure for -incompatible clone/use register classes. These are separate from the quality -corpus; they do not supply extra zero-spill examples to improve a total. - -The complete program cohort includes Chapter20Test's 11 examples plus BrainFuck -and MergeSort on all three SystemV targets: 39 compilations, default seed 123. -The fresh original baseline passes 368 tests plus the fuzzer regression. After -forced rebuilds, `make -j 4 tests` passes 375 plus 1. The 11 ordinary examples -also pass 990 compilations across seeds 0-29 and three CPUs, with the current -register/ownership checks enabled. Native execution begins in Chapter 21. - -| SystemV target | Compilations | Original splits | Corrected splits | Original weighted | Corrected weighted | -|---|---:|---:|---:|---:|---:| -| x86-64 | 13 | 80 | 82 | 150 | 152 | -| RISC-V | 13 | 82 | 80 | 103 | 101 | -| ARM | 13 | 73 | 74 | 101 | 102 | -| Total | 39 | 235 | 236 | 354 | 355 | - -This is a one-move correctness cost, not a quality win. Adjusted three local -weighted goldens after reviewing the full aggregate: x86 array 3->5, x86 String -18->21, ARM String 3->5 (the original actual ARM count was 2 within tolerance). -All assertions remain active. The stats runner emits per-compilation data and -fails on any JUnit failure; the Chapter20Test collector allows all three target -checks to run before reporting golden differences. The README preserves Cliff's -new introduction, removes premature coalescing/popular-use-grouping claims, -and ends with the measured baseline and discussion of statistical comparison. -No advanced coalescing, color-bias, grouping, cold-first, or area/cost heuristic -was imported. Logs and the original-code snapshots are under -`chapter20/build/regalloc-review/`. Chapters 21-25 are unchanged. - -### TypeFunPtr normalization: complete locally, 2026-09-20 - -Backported the trailing-default normalization from `7f3b8856` to 23-24, where -open/closed function argument tails first appear. Their complete `make` factory -trims trailing BOTTOM arguments for open signatures and TOP arguments for closed -signatures before interning; the existing meet uses that factory too. Raw cyclic -allocation stays unchanged. Earlier chapters use fixed TypeTuple signatures. -Chapter 25 already normalizes with scalar BOT/TOP and retains its implementation. - -Added only `gather` cases in 23-25: open/closed signatures, repeated trailing -defaults, all-default signatures, and defaults before a real argument. No new -test methods or files. The expanded existing lattice-law tests also passed -before the 23-24 fix; these cases extend coverage rather than prove an old law -failure. The other changes in `7f3b8856` concern Chapter 25's TypeMem final flags -and XInt sets, already fixed there; neither representation exists earlier. - -Fresh baselines and forced-rebuild validation passed `make -j 4 tests` in -23 (416 + 1), 24 (439 + 1), and 25 (449 total), with assertions enabled. -Focused TypeTest runs also passed all six tests in each chapter. Edited files -are LF-only and `git diff --check` passes. Logs: -`chapter25/build/tfp-normalization/{baseline,repro,validate}.log`. - -### Scheduling without isPinned: complete locally, 2026-09-20 - -Removed `isPinned()` and all overrides in 11-25. Early scheduling walks inputs, -then assigns a block only when input 0 is null. Existing control and Phi/Proj -bindings stay intact. For ordinary values, that control is an earliest-placement -bound, not a prohibition on sinking during late scheduling. - -Chapters 11-14 also used the predicate for late placement; GCM now preserves -those cases explicitly (Proj, New, Parser.ZERO, and Cast from 13), alongside its -existing CFG/Phi handling. From 15, late scheduling already handles its fixed -CFG/Phi/Proj cases structurally. - -The preceding GCM suites supplied the passing baseline. After forced Java -rebuilds, every full snapshot suite in 11-25 passed `make -j 4 tests`, with -assertions enabled and unchanged expectations/counts (449 total in 25). Existing -constant-chain, guard, loop, allocation, native, and emulator tests all pass. -No remaining `isPinned` declaration or call exists in the chapter sources. -Edited files retain LF endings; `git diff --check` passes. -Logs: `chapter25/build/pinned-review/{chapter25,backports}.log`. - -### GCM and global constant cloning: unified locally, 2026-09-20 - -GCM starts in 11; functions make constant ownership relevant in 18. Chapters -11-25 now share the early definitions-first / late uses-first worklist strategy, -including Region/Loop Phi discovery, waiting-load wakeups, and LCA over every -matching Phi input. Anti-dependence marks moved from CFGNode into a temporary -GCM array. Removed the obsolete fixed-register placement heuristic in 21-24. - -Chapters 18-25 clone entire global constant-building graphs with one identity -map per function, reusing shared subgraphs within that function. Originals stay -intact until all rewrites finish. `Node.copyEmpty()` supplies exact-class clones -with fresh IDs and empty edges, avoiding incompatible machine `copy()` contracts. -Removed 25's redundant instruction-selection pinning to the old ideal Start. - -Necessary chapter differences remain explicit: 18-19's linked Parm inputs -belong to their callers; from 20, unlinked Parms belong to the callee. In 11-20, -the evaluator independently reschedules nodes, so anti-dependencies retain the -full store placement range. Trying the later single-block rule fails the existing -`SchedulerTest.testStoreInIf2`. Alias/tuple memory representations stay local to -their chapters; 25 retains its compilation-unit ownership check. - -The new Chapter18Test regression in every snapshot 18-25 exercises two surviving -recursive functions, repeated uses, registered edges, and function-local chains: -stacked Cast/Constant nodes in 18-20 and RISC LUI/AddI expansions in 21-25. It -fails against isolated original GCM classes in 18 and 20, and passes afterward. -Original 21 and 25 already pass the machine-chain case; those changes simplify -and unify the implementation rather than correcting that particular case. - -Changed ordering exposed 21's existing empty-block layout bug: entering a nested -loop was mistaken for a backedge, producing a bad native Sieve branch. Backported -22's same-loop-tree check; native and emulated Sieve pass. Updated 21's tighter -scaled spill expectations: stringHash RISC 5->3 and ARM 6->3; BrainFuck RISC -44->28. BrainFuck executes on both emulators; a separate direct-entry RISC -hashCode probe verifies both initial hashing and the cached result. - -Validation: unmodified full baselines passed in 11-25. After forced Java rebuilds, -all full chapter targets pass with assertions and `make -j 4 tests`: ordinary -counts in 11-24 are 166, 169, 184, 204, 215, 233, 285, 316, 358, 368, 385, 397, -416, and 439, plus the separately invoked fuzzer wrappers where applicable. -Chapter 25 passes 449 tests across its groups. All edited files use LF endings. -Logs: `chapter25/build/gcm-review/{baseline,before-test,focus-all,final,final25}.log`; -`final.log` covers successful 11-24 runs and `final25.log` the final 25 rebuild/run. - -Independent follow-up: a direct-entry ARM emulator probe of 21's exported -`hashCode` traps with code 3 under both original and updated GCM. It uses the -existing stringHash.smp library, a String containing the u8 array "test", and a -zero cached hash; the cause is not diagnosed. Do not claim the green suite or -lower spill count validates this extra case. Scratch reproducer: `StringProof.java` -in the same review directory; the RISC equivalent returns/caches 3556498. - -### Dominator caches: unified locally, 2026-09-19 - -Real dominator searches begin in 6. The original Region pointer cache in 6-9 -returned the old, still-live dominator after its predecessors were rewired. -Regions now recompute through the shared depth-based `domLCA` walk in 6-25, -including one, two, or more predecessors. Existing dependency direction and -24-25's dead-predecessor filtering are preserved. - -Per review, 6-17 use a char depth with no version. Chapters 18-25 use separate -char depth/version fields, checked before depth narrowing and global version -increments. Added the invalidation hook to 18-20's inlining; 21-25 already had -it. Region, Loop and Stop all validate their caches, and folding functions use -their caller-side depth. CFG copy constructors preserve both fields, as do -ordinary clones. Packed versions in 21-24 failed after 100 invalidations; -25's packed depth overflowed at 2148. Both limits are now 65535, with explicit -overflow assertions. - -Development checks covered rewiring, depth overflow, actual inlining with warmed -caches, repeated invalidation, copy preservation, and version overflow. At -Cliff's request, the dedicated dominator helpers/tests and their Makefile -accommodations were subsequently removed as unnecessary for this bookkeeping. -Existing printer regressions still check that both cache fields stay unchanged. - -Baseline full targets passed in 6-24. After full Java rebuilds, all affected -snapshot suites passed with assertions enabled. Chapter 25 initially passed -`make tests` and `make -j 4 tests` in a scratch copy with a pre-existing stray -`v` removed from Node.java. After Cliff authorized removing that typo from the -live tree, its Java sources and system object rebuilt and `make -j 4 tests` -passed there too (451 tests, exit status zero). - -Logs: `chapter25/build/dominator-review/{baseline,fixed,later,final18-24,chapter25-scratch,chapter25-final,chapter25-live}.log`. -Reusable cache rules are in the skills notes. - -### B11: optimized return-type checking backported locally, 2026-09-19 - -The false mixed-return rejection begins in Chapter 18, where function returns -first merge through one Return/return-value Phi. `ReturnNode.err()` now checks -`expr()._type`, as in Chapter 19. The parse-time `mt` meet could retain a type -from an unreachable return forever. Removed that aggregate from 18-24; it was -already unused in 19-24 and absent in 25. Parsed kind flags remain only for -formatting diagnostics. Chapter 24's additional TOP check is preserved. - -Earlier snapshots were checked with reduced syntax. Struct/reference returns -appear in 10; floating-point returns in 12. Chapters 10-17 already accept the -dead reference/int examples, and 12-17 accept the dead float/int examples. -They retain separate Return nodes and do not require one common type across -reachable returns. The B11 false rejection therefore has no earlier compiler -patch; introducing common-return-type checking there would be separate work. - -`Chapter10Test.testDeadReferenceReturn` starts in 10 and is copied through 25; -`Chapter12Test.testDeadNumericReturns` starts in 12 and is copied through 25. -They cover both constant If arms and unreachable returns after an unconditional -return; numeric cases also verify execution results. Both tests failed in 18 -before the correction with `No common type amongst ...`. -`Chapter18Test.testReachableMixedReturns` in 18-25 still rejects reachable -int/float and int/reference alternatives, using each chapter's diagnostic. - -Unmodified baseline targets passed in 9-25. Final full `make tests` targets -passed with assertions enabled in every changed snapshot, 10-25; Chapter 25 -passed 448 tests. Its reference test selects the entry function explicitly, -because constructors add other Returns to the same compilation unit. -Logs: `chapter25/build/b11-review/{probe,probe-later,baseline,red,fixed,chapter25-fixed}.log`. - -### B12: immediate multiply destination corrected locally, 2026-09-19 - -The x86 backend has distinct integer register (`MulX86`, 0F AF), integer -immediate (`MulIX86`, 69/6B), and floating-point (`MulFX86`, MULSD) encoders. -Chapter 21 incorrectly routed immediate multiply through `ImmX86`, which -encodes an opcode extension in ModRM.reg. IMUL needs the destination there, -including its high bit in REX.R. Chapter 20 has no executable encoder yet; -22-25 already have a dedicated immediate multiply encoder. - -Chapter 21 now uses that dedicated encoder while preserving its -`twoAddress() == 1` allocation contract. Other `ImmX86` subclasses are unchanged. -For `rcx *= 11`, the regression failed with ModRM C1 instead of C9; the fix emits -`48 6b c9 0b`. For `r9 *= 11`, it emits `4d 6b c9 0b`. - -`Chapter21Test.testX86MultiplySameRegister` is carried through 21-25. It forces -rax/rcx/r9/r15 and positive/negative imm8/imm32 values, independently of allocator -choices, and checks register fields, opcode, immediate, length, and each -chapter's allocation contract. Existing distinct-register checks remain in -22-24. Unmodified baselines and final full `make tests` targets passed in all -five snapshots, with assertions enabled; Chapter 25 passed 446 tests. -Logs: `chapter25/build/b12-review/{baseline,red,fixed}.log`. - -### Issue #251: dead-node printing corrected locally, 2026-09-19 - -[Issue #251](https://github.com/SeaOfNodes/Simple/issues/251) identifies dead-node -checks against a null `_inputs` array. Constructors and clones allocate the -array; `kill()` empties it without setting it to null. Line printers now use -`isDead()` throughout 7-25, including both columnar and LLVM formats in 10-17. -Chapter 25's whole-program printer uses the same predicate to omit dead -functions and nodes. Its bounds-safe input accessor simply checks the input -count. Printing does not prune the linker. - -`Chapter07Test.testDeadNodePrinting` in every snapshot 7-25 checks retained input -storage, the `DEAD` marker, and live inputless nodes. Chapter 25 also tests -omitting a dead function while preserving its linker entry. The regressions -fail against isolated original printers in 7, 10, 18, and 25. Full `make tests` -passed with assertions enabled in every affected snapshot, including 447 tests -in 25. The initial Chapter 17 test assumed an inputless Start; its setup was -corrected for that chapter's representation and its full target rerun. -Logs: `chapter25/build/issue251-review/{original,fixed,chapter17-fixed}.log`. - -### Issue #247: emulator 64-bit stores corrected locally, 2026-09-19 - -[Issue #247](https://github.com/SeaOfNodes/Simple/issues/247) identifies `st8` -writing the upper half with `st2`. The identical bug exists in EvalRisc5 and -EvalArm64 in every snapshot 21-25, starting with their introduction. Both now -use `st4` for the upper half, writing all eight bytes rather than leaving the -upper two unchanged. - -`Chapter21Test.testRisc64BitStore` and `testArm64BitStore` are carried through -21-25. They check individual little-endian bytes independently of the load -helper, round trips, positive/negative/extreme values, overwriting with zero, -and untouched neighboring memory. All ten cases failed before the correction -at the first unwritten byte (0xA5 instead of 0x23). - -Full `make tests` passed with assertions enabled in each snapshot 21-25, -including 445 tests in Chapter 25. Log: -`chapter25/build/issue247-review/fixed.log`. - -### B10 audit: still pending in Chapter 24, 2026-09-19 - -The fix is present in Chapter 25 (introduced with commit `51f1f8f4`), but has -not reached Chapter 24. Integer `nonZero` appears in 15; `_widen` first appears -in 24, so earlier snapshots do not need this backport. - -An assertions-enabled probe of the current compiled snapshots tested `[0,255]` -and `[-255,0]` at widening levels 0-3. Chapter 24 resets all six nonzero widening -levels to zero; Chapter 25 preserves all of them. Both pass refinement (`isa`), -idempotence, double-dual, singleton normalization, and zero-input checks. This -establishes the missing type-level backport; it is not a loop-failure reproducer. -Probe: `chapter25/build/b10-review/B10Probe.java`. No compiler correction was -made during this audit; B10 remains in the pending queue above. - -### B09: complete locally, 2026-09-19 - -Audited `Node.p(depth)`, recursive printing, labels, scope/graph viewers, and -assembly helpers. Corrections follow the first affected representation: - -- 11-24: scheduled IR display uses local `_idepth` state; 11-14 also use - identity maps to avoid setting Node hashes/GVN locks. -- 18-24: memory display reads raw lazy aliases instead of creating Phis; - scope display uses `Var._type` without resolving forward references. - 25's stale alias-based memory display reads its actual bulk-memory input. -- 19-23: printers use ordinary `link` and tolerate missing targets. Per Cliff's - review, type interning is allowed: the proposed non-interning linker scan and - `sameTarget` helper were removed. 24-25 use `CodeGen._link` to preserve dead - entries, including through 25's `funcName`; optimizing `link` still cleans up. -- 20-25: register display uses `_lrg` without compressing chains or rewriting - node mappings. Function predicates use the existing leaf `_isConstant` from - 23; integer size/value accessors also avoid entering shared recursion state. -- 21-25: pool display uses identity bookkeeping and recorded alignment, plus - recorded struct size from 22 and section choice in 25. Printers do not ask - Types for layouts, even when an answer might already be cached. Layout is - separate from type identity and may eventually move out of TypeStruct. - -Regressions cover graph caches/edges, lazy Phis, unresolved declarations, stale -linker entries, register chains, leaf type accessors, and forbidden layout queries. -Isolated original Chapter 18 classes fail the lazy-memory and forward-reference -tests; original printers also reproduce cache mutation, register compression, -shared-scratch assertions, and dead-linker pruning. Tests permit type interning. - -Every affected compiler snapshot (11-25) passed its full `make tests` target with -assertions enabled after the review adjustment, including 443 tests in 25. -The constant-pool regression rejects size/alignment queries even if they would -return cached answers. Log: `chapter25/build/b09-review/revised.log`. -Durable rules are in the skills notes. - -### B13 / issue #246: complete, 2026-09-19 - -Cliff reports the correction pushed. Nested negation in `p != null` / `!!p` -now discovers the underlying pointer guard in every snapshot 10-25, retaining -each chapter's guard representation. Chapters 23-24 also decompose short-circuit -Phis with availability checks; Eval2 in 18-24 now handles pointer/null Not. - -`Chapter10Test.testNullGuards` failed before the backport in 10-24 and passes -afterward; `testNullGuardErrors` checks rejected uses. Both tests live in every -snapshot 10-25. `testShortCircuitGuardScheduling` covers RHS-only call results -in 23-25; Chapter 25 also rotates optimizer seeds. Full `make tests` passed in -each directory 10-25. Ordinary test counts were 149, 164, 166, 181, 201, 212, -230, 282, 309, 350, 359, 374, 386, 403, 425 in 10-24; Chapter 25 passed 428 -total. No assertions or existing expectations were weakened. -Logs: `chapter25/build/issue246-review/`, particularly -`chapters18-24-fixed.log` and `chapters23-25-final.log`. - -Independent findings retained for follow-up: - -- B14's cyclic-equality failure remained reproducible despite green B13 - suites; it is corrected separately below. -- A pre-existing Chapter 25 diagnostic concern remains outside B13: with the - issue's nullable array setup, `if (p == null) return p.x; return -1;` was - accepted despite dereferencing null on the taken arm. Original setup: - `struct Point { int x; new Point = { int v -> x = v; }; };` - `Point?[] !points = new Point?[2]; points[arg] = new Point(42);` - `Point? p = points[1];`. This needs separate investigation. - -### B14: complete locally, 2026-09-19 - -Added the existing Chapter 25 leaf type-kind check to `Type.cycle_eq` in 23-24. -Cyclic structural equality first appears in 23. Inspection of 9-22 found the -older interned-child identity representation with kind checks in `Type.equals`; -the equivalent BOTTOM/float-struct meet probe passes in 22 without a correction. -No earlier compiler change is needed for B14. - -`TypeTest.testCyclicLeafKinds` in 23-25 interns same-named structs with `x` -typed BOTTOM, 1.0, and 2.0, then meets the latter two. Before the correction it -throws ClassCastException through `TypeFloat.eq` in 23 and 24; 25 passes. -Afterward all three pass, checking F32 field type, canonical interning, -commutativity, absorption by the BOTTOM-field struct, and the dual/join result. - -Validation with assertions enabled (Windows/Cygwin, JDK 21.0.4): - -- Unmodified baseline: `make -k tests CHAPTERS="chapter22 chapter23 chapter24 chapter25"` - passed each full target. -- After a full Java rebuild of 23-24, the focused regression and full TypeTest - passed in 23-25 (6 TypeTest cases in each). -- `make -k tests CHAPTERS="chapter23 chapter24 chapter25"` passed: 404 and 426 - ordinary tests plus their fuzzer wrappers in 23 and 24; 429 total in 25 - (365 raw0, 32 raw1, 8 standalone, 16 system, 1 fuzzer, 7 remaining). - -Logs: `chapter25/build/b14-review/{baseline,before-fix,fixed}.log`. - -### Build and fuzzer baseline, 2026-09-17 - -Windows/Cygwin, OpenJDK 22.0.2: all 25 chapters passed `tags` and `release`. -Build setup supplied missing early targets and corrected argument-list writes -in 22-24; no compiler behavior was backported. Chapter 22 initially failed -TypeTest with a TypeConAry/TypeRPC cast error, then passed a forced rebuild -(369 ordinary tests plus fuzzer), consistent with stale classes. - -The initial all-chapter test baseline failed Chapter 18's random fuzzer on -seed `973358943756616234`. At Cliff's request, wrappers in 8-24 now follow -25's explicit seed-list structure, and 8-15 invoke their wrappers from -`make tests`. Exploratory fuzzing is opt-in. All 25 full chapter targets -passed after these harness changes; 8-15 passed again after wrapper invocation -was added. Logs: `build/review/seed-lists-all-tests.log` and -`seed-lists-08-15-tests.log`. - -**The Chapter 18 compiler failure remains open.** Its seed is in -`OPEN_FAILING_SEEDS`, and explicitly running it still failed. Regression lists -started empty, so green default wrappers added no fuzz regression coverage. -Reduced input: - -```java -struct s0 { u8 v1; }; -s0? !UmPOLQK=null; -if(0) while(0&UmPOLQK.v1) {} -if(UmPOLQK.v1) {} -return new s0; -while(0) {} -``` - -This exposes two distinct concerns: nullable field lookup can fail during -parsing with peepholes disabled; with peepholes enabled it reaches a -mixed-return error. B11 isolates the latter further to -`struct S { u8 x; }; return new S; return 0;`, rejected in 18 and accepted in -19. Chapter 19 also changes the fuzzer comparison from peepholes off/on to -two optimizer worklist seeds. Neither that harness change nor B11 alone proves -the original seed fixed. Keep it open until the full seed passes. -Log: `build/review/chapter18-open-seed.log` (intentional failure). +This is a condensed completion record, not a list of current suite counts for +old revisions. Earlier detailed traces are in Git history; durable invariants +have been consolidated into the [AI notes](../skills/chapter25-codex-notes.md). +Unresolved reproductions have been promoted to the pending queue above. + +| Completed work | Scope and evidence retained | +|---|---| +| B14 cyclic leaf-kind equality | 23-24 backport; 25 already correct. Cyclic equality starts in 23. `TypeTest.testCyclicLeafKinds` fails before the fix; earlier interned-child equality already checks kinds. Full affected suites passed. | +| B13 / #246 null guards | Nested Not/null guard discovery from 10; short-circuit Phi availability in 23-24. Regression and full suites in 10-25 passed. Separate null-dereference diagnostic remains queued. | +| B09 and #251 debug printing | Side-effect-free print/accessor paths from their first applicable chapters; `_` diagnostic naming, type interning allowed, layouts forbidden. Dead nodes use `isDead()`, not null `_inputs`, from 7. Original-printer negative checks and full affected suites passed. | +| #247 emulator stores | Full eight-byte writes in ARM/RISC-V emulators, 21-25. Independent byte-pattern/overwrite regressions failed before the fix; all affected suites passed. | +| B12 x86 immediate multiply | Dedicated destination-register encoder in 21; 22-25 already had it. Low/extended-register encoding regressions and full 21-25 suites passed. | +| B11 optimized return checking | Remove parse-time meet in 18-24; 18 checks the optimized result type. Earlier separate Returns already accept dead mixed-type exits. Regressions start in 10/12; full 10-25 suites passed. | +| Dominator caches | Shared searches from 6; char depth in 6-17, separate char depth/version from 18, checked overflow and preserved clone fields. Inlining invalidation in 18-20. Full affected suites passed; dedicated bookkeeping helpers/tests were removed at Cliff's request. | +| GCM, constant cloning, isPinned removal | Shared scheduling from 11, per-function cloning of stacked constants from 18; preserve chapter-specific anti-dependencies and linked Parm ownership. Full 11-25 suites passed. Keep clone-based copyEmpty and non-final graph fields per review. | +| TypeFunPtr normalization | Trailing-default normalization in 23-24; 25 already correct. Only gather cases added; lattice laws and full 23-25 suites passed. Other `7f3b8856` representations remain in 25. | +| Inlining Return types and ARM execution | Live return expressions outlast a deleted inline entry (20-25); ARM register SUB, call instructions, frame byte counts/alignment, and vector growth (21-25 as applicable). Reduced negative cases and full affected suites passed. The earlier standalone ARM String/hash failure is resolved. | +| Native test reliability | Full process exit status, stdout plus successful execution, and distinct concurrent HelloWorld artifact names. Crashes no longer pass merely because output matches or an exit status narrows to zero. | +| Allocator progression 20-25 | Fixed cohorts, legality checks, native/emulated execution from 21, and same-compiler comparisons. Final results below. | +| Build/fuzzer harness baseline | All 25 chapter targets passed after build setup and explicit seed lists. Empty default lists were not exploratory fuzz coverage; the Chapter 18 open seed remains queued. | + +Final allocator audit, 2026-09-20, Windows/Cygwin with assertions: + +| Snapshot | Full suite | Spill report | +|---|---|---| +| 20 | 378 tests + fuzzer | 39 compilations, 238 / 357 | +| 21 | 408 tests + fuzzer | 91 compilations, 840 / 1,456 | +| 22 | 422 tests + fuzzer | 115 compilations, 838 / 1,496 | +| 23 | 444 tests + fuzzer | 145 compilations, 933 / 1,745 | +| 24 | 473 tests + fuzzer | 212 compilations, 1,332 / 2,956 | +| 25 | 468 tests across parallel groups, including fuzzer | 222 compilations, 2,597 / 5,579 | + +All full suites and final spill reports passed. The Chapter 25 run rebuilt +`sys.o`. Negative checks against saved original classes reproduce fixed-neighbor +bias, narrow-store masks, and ARM floating-memory encoding failures. The original +Newton ARM allocation also failed before the fix. The Chapter 21 coalescing-off +comparison passes all allocation/runtime checks but reports nine changed spill +goldens, intentionally exiting nonzero. The Chapter 25 earlier-ranking ablation +fails fresh library allocation, so its client-only totals are explicitly partial. +Logs and saved original classes: `chapter{20..25}/build/regalloc-final/`. diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 4be72a96..04bdcce2 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -6,8 +6,8 @@ the implementation. `WIP-HANDOFF.md` and `parser-simplification-plan.md` retain the detailed history; portions of their old branch/status reports are stale after the Chapter 25 squash. For cross-chapter work, read [the backport queue and validation record](../docs/chapter-backports.md). -It owns pending items and detailed reproductions; these notes capture reusable -lessons rather than duplicating that history. +It owns pending reproductions and a condensed completion record; these notes +capture reusable lessons. Detailed superseded validation history remains in Git. ## Collaboration preferences @@ -44,7 +44,8 @@ lessons rather than duplicating that history. affected directories explicitly listed. Establish the destination baseline before changing it; older Makefiles may need a forced rebuild after API changes. - Keep unrelated discoveries separate in `docs/chapter-backports.md`. Completed - fixes leave the pending queue; preserve their validation history. A green suite + fixes leave the pending queue; retain a concise validation summary and move + unresolved discoveries out of the history into the actual queue. A green suite after changing graph/test order does not prove an intermittent failure fixed. - Store disposable probes/logs under an appropriate ignored build directory. Preserve durable reproducers in tests or the review record, not only scratch @@ -153,11 +154,9 @@ lessons rather than duplicating that history. the JUnit listener labels individual cases and sums CPU/ABI and cohort totals. Assertions stay enabled and failures propagate. Do not silently change cohort membership, seeds, or targets when comparing chapters. -- Chapter 20's corrected baseline costs one extra weighted move (354->355 over - 39 compilations); document this as a correctness cost. Advanced quality - heuristics remain staged. Chapters 20-24 are now implemented; common correctness - fixes and diagnostic hooks have also been forwarded through 25 at Cliff's request. - Resume the quality/cohort/README review at 25. Chapter 21's shortened README links the retained encoding reference. +- The staged review is complete through 25. Keep 21's shortened README and its + separate encoding reference. The final narrow-store mask fixes changed the + measured totals for 20 and 21; use the current READMEs, not older review counts. - Chapter 21 changed several inherited inputs/ABIs. Its Chapter20Test now freezes all 13 original programs; Chapter21AllocTest retains the four revised cases, counted with the native variants as cohort 21. On Windows the cohorts are @@ -190,8 +189,8 @@ lessons rather than duplicating that history. - Validate the instruction masks independently of the chosen register: a broad mask can hide behind favorable color bias. Byte/short x86 and RISC-V stores must exclude floating-point registers. Size fields such as `_sz` may hold a - printable character: compare to `'4'`, not integer `2`. Chapters 22-24 now carry - 25's store restrictions; x86 20-21 and RISC-V 21 remain queued. + printable character: compare to `'4'`, not integer `2`. The narrow-store + restrictions are now present from x86 20 and RISC-V 21 onward. - The historical Chapter 22 seed sweep exposed failures outside allocation; it is not a template for routine allocator validation. Chapter 22's frozen String source fails before allocation and its returned @@ -200,8 +199,8 @@ lessons rather than duplicating that history. Do not replace the seed or add a return merely to make the sweep green. - Use an ablation in the same compiler to measure each staged heuristic. Native ABI/lowering changes make the Chapter 20 and 21 totals different even with the - same sources. In 21, coalescing saves 127 weighted moves, but deferring later - heuristics costs 174 against the old combined snapshot; disclose both. + same sources. Include the same legality fixes on both sides. Mask corrections + can substantially change coalescing results; refresh old tables and commentary. - Chapter 21's spill reporter defers quality-golden failures until reporting ends, so all target/runtime checks still run. The command must still exit nonzero. Keep full native process exit codes and check each emulator's own result memory. @@ -236,8 +235,32 @@ lessons rather than duplicating that history. each chapter's quality heuristics and historical cohort/README review staged. Compare each destination's unchanged local suite before/after for such a batch; do not present those unequal local suites as the chapter progression table. -- The staged plan and historical fix inventory are in - `docs/chapter-backports.md`; its review is not evidence of completed backports. +- Chapter 25's spill corpus preserves the earlier 212 source/target entries, + with documented constructor, receiver, library and mutability adaptations. + These are allocation/legality replays, not historical runtime harnesses. Its + own cohort includes current Chapter25Test allocations and a fresh library + encoding. See `chapter25/src/test/java/com/seaofnodes/simple/spill/README.md`. + Do not silently use current inherited tests as though their sources were frozen. +- Rebuild and measure the system library even if sys.o is up to date. In the + final 25 review, the older ranking and a multi-use-clone preference looked + better on clients but exhausted allocation rounds on fresh sys compilation. + Both trials were rejected. Keep the existing area/cost ranking; client-only + totals do not prove whole-suite improvement. The driver uses seed 456, old + cohort replay uses 123, and current test helpers normally use 126. +- ARM load/store opcodes must follow the allocated register bank, not the + source Type. Emit the SIMD bit for both addressing modes, normalize D0-D31 + to register numbers 0-31, and permit FP registers only at supported widths. + A GPR-only float-store mask made 25's old Newton programs repeatedly split + the wrong side of a loop. The paired fixes start in 21's executable backend. + Emulator FP memory operations must preserve bits and scale double offsets + by eight. Use independent instruction words as well as compiler round trips. +- Fixed-neighbor bias must clear the computed register, including a neighbor's + sole allowed register before it is colored; `_reg` can still be -1. The shared + correction and regression start in 20. A passing corpus can miss this path. +- Chapter 25's extra multi-def/fixed-use thresholds and kill/rematerialization + choices remain local strategies. Earlier splitEmptyMaskSimple lacks the extra + branch that needs 25's original-def-use-count snapshot. Do not label a textual + difference a missing correctness fix without establishing the affected path. ## Null guards: B13 / issue #246 lessons |