From 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 7 Oct 2026 19:10:51 -0700 Subject: Towrds getting RA spill counts comparable Ignore JIGs. Get test suites more conical, so reg alloc spill counts are comparable --- chapter25/README.md | 104 +++++++-------------- .../java/com/seaofnodes/simple/codegen/IFG.java | 7 ++ .../com/seaofnodes/simple/node/CallEndNode.java | 43 ++++++++- .../java/com/seaofnodes/simple/node/FunNode.java | 7 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 2 + .../com/seaofnodes/simple/Chapter14FloatTest.java | 2 + .../java/com/seaofnodes/simple/Chapter14Test.java | 2 + .../java/com/seaofnodes/simple/Chapter15Test.java | 1 + .../java/com/seaofnodes/simple/Chapter16Test.java | 2 + .../java/com/seaofnodes/simple/Chapter17bTest.java | 2 + .../java/com/seaofnodes/simple/Chapter18Test.java | 1 + .../java/com/seaofnodes/simple/Chapter19Test.java | 2 + .../java/com/seaofnodes/simple/Chapter20Test.java | 2 + .../java/com/seaofnodes/simple/Chapter21Test.java | 2 + .../java/com/seaofnodes/simple/Chapter22Test.java | 1 + .../java/com/seaofnodes/simple/Chapter24Test.java | 2 + .../java/com/seaofnodes/simple/Chapter25Test.java | 4 +- .../src/test/java/com/seaofnodes/simple/TestC.java | 7 +- .../simple/spill/Chapter20Test-testCast.smp | 2 +- .../simple/spill/Chapter20Test-testMergeSort.smp | 20 ++-- .../simple/spill/Chapter20Test-testNewtonFloat.smp | 4 +- .../spill/Chapter20Test-testNewtonInteger.smp | 4 +- .../simple/spill/Chapter20Test-testString.smp | 14 +-- .../spill/Chapter21AllocTest-testNewtonFloat.smp | 4 +- .../spill/Chapter22Test-testInfiniteReturn.smp | 2 +- .../spill/Chapter22Test-testNarrowCReturns.smp | 12 +++ .../simple/spill/Chapter22Test-testSextFail.smp | 4 +- .../simple/spill/Chapter22Test-testSextFail2.smp | 4 +- .../simple/spill/Chapter22Test-testSextSuccess.smp | 4 +- .../simple/spill/Chapter23AllocTest-testJig21.smp | 16 ---- .../simple/spill/Chapter24AllocTest-testJig21.smp | 16 ---- .../simple/spill/Chapter24AllocTest-testJig22.smp | 15 --- .../spill/Chapter24AllocTest-testNewtonInteger.smp | 4 +- .../simple/spill/Chapter24Test-testJig.smp | 1 - .../java/com/seaofnodes/simple/spill/README.md | 28 +++++- .../java/com/seaofnodes/simple/spill/cohorts.tsv | 17 +--- 36 files changed, 184 insertions(+), 180 deletions(-) create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testNarrowCReturns.smp delete mode 100644 chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testJig21.smp delete mode 100644 chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig21.smp delete mode 100644 chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig22.smp delete mode 100644 chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testJig.smp (limited to 'chapter25') diff --git a/chapter25/README.md b/chapter25/README.md index bfe48809..ec8a8ea8 100644 --- a/chapter25/README.md +++ b/chapter25/README.md @@ -170,77 +170,41 @@ 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 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. +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. - -Chapter 21's adjacent-copy forwarding carries forward here as well: a copy -used only by the next instruction is removed when the operand accepts its -source register and is not tied to the instruction's result. - -The table below is the complete 2026-10-02 replay, after repairing three saved -String sources with explicit constructors for their required `cs` field. -All 212 historical entries now pass. This establishes a new baseline after the -fixture adaptations and recent compiler corrections; it is not an allocator-only -comparison with the earlier audit. The [backport record](../docs/chapter-backports.md) -retains the older partial comparisons. - -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 thirteen recorded 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 | 375 | 606 | -| Chapter 21 | 52 | 479 | 1,172 | -| Chapter 22 | 24 | 103 | 103 | -| Chapter 23 | 30 | 129 | 353 | -| Chapter 24 | 67 | 696 | 1,410 | -| Chapter 25 | 14 | 786 | 1,815 | -| **Total** | **226** | **2,568** | **5,459** | - -`_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. All 23 `Chapter25Test` tests pass, including their -native/result checks, with no spill-golden failures. -Use `make -j 4 tests` for the full chapter, including inherited emulator tests. - -### Comments on the measurements - -The earlier allocator audit found no uniform improvement. Substituting Chapter -24's ranking while keeping the rest of that compiler unchanged saved five moves on the 221 -client compilations (2,206 / 4,719 versus 2,211 / 4,724), but failed 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 -contributed 386 moves / 855 weighted moves in that audit; the current replay -measures 373 / 828. - -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. - -In that earlier audit, the historical-cohort total rose from Chapter 24's -1,332 / 2,956 to Chapter 25's 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. +A single-use function address in the same block gets priority for +rematerialization when it is separated from its use. Moving that address +calculation next to the use adds no instruction and avoids preserving a +callee-save register merely to hold the constant. Adjacent uses and multi-use +addresses retain the area/cost ranking. + +Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each +cell is the sum of `_spillScaled`: retained split moves, including register +copies, weighted by loopDepth. Lower is better. **# tests counts +compilations** (program/CPU/ABI cases), including zero-spill cases, rather than +JUnit methods. The count and membership of each row stay fixed across columns. + + +| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | Ch 23 | Ch 24 | Ch 25 | +|---|---:|---:|---:|---:|---:|---:|---:| +| Ch 20 | 39 | 360 | 576 | 430 | 442 | 441 | 491 | +| Ch 21 | 52 | | 1,072 | 960 | 961 | 948 | 1,077 | +| Ch 22 | 26 | | | 63 | 63 | 63 | 71 | +| Ch 23 | 24 | | | | 103 | 103 | 152 | +| Ch 24 | 58 | | | | | 1,387 | 1,503 | +| Ch 25 | 14 | | | | | | 1,862 | + + + +Chapter25 introduces several features, which when run on the older tests +generate a lot more code, which in turn generates more spills. + +Class initialization, inlining, escape analysis, and library adaptations +all change the graphs. To help with this, we adjust the inlining +heursitics to try and get all the boilerplate to inline and optimize. + 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 6145910c..bcdb14bf 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -457,6 +457,13 @@ abstract public class IFG { int area = cfg != use.cfg0() ? functionArea(lrg._fun,alloc) : cfg._outputs.find(use)-cfg._outputs.find(def)-1; + // A single-use function address can move next to its use without + // adding an instruction. Prefer that to saving a callee-save + // register just to hold the address. Stay in the same block and + // require a gap so the clone makes progress. + if( def instanceof FunPtrNode && !lrg._multiUse && + cfg == use.cfg0() && area > 0 ) + return 1000000; if( area > 0 ) return areaScore(area,loopCost(use)); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 162f9c24..35180fea 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -179,10 +179,12 @@ public class CallEndNode extends CFGNode implements MultiNode { { addDep(fptr); return -1; } // Encouraged inlining because small size and constructor. - int maxSize = fun._name!=null && fun.isInit() && !fun.isClz() ? 200 : 100; - if( fun._approxUIDs >= maxSize ) - return -2; // Try later (if shrinking helps) - if( fun.body().cardinality() >= maxSize ) + int maxSize = fun.inlineLimit(); + // A large parse can leave only a tiny initializer. Recognize that + // without repeatedly walking the whole body while it shrinks. + if( fun._approxUIDs >= maxSize ) { + if( !smallBody(fun) ) return -1; + } else if( fun.body().cardinality() >= maxSize ) return -1; // Try later (if cleanup makes the real body small enough) // Can be cloned but not trivial @@ -192,6 +194,39 @@ public class CallEndNode extends CFGNode implements MultiNode { return 1; } + // Bounded, conservative recognition of straight-line initializer boilerplate. + // Walk uses from the entry and stop at Return, never following callers or + // constant inputs. This also avoids scanning sparse MemMerge input arrays. + // Watch only this small prefix, including an unsupported node that may fold. + private static final Node[] TINYBODY = new Node[15]; // Tiny worklist + private boolean smallBody(FunNode fun) { + ReturnNode ret = fun.ret(); + for( Node in : ret._inputs ) + if( in!=null ) addDep(in); + if( ret.ctrl()!=fun ) return false; + TINYBODY[0] = fun; + int len=1; + for( int i=0; iTINYBODY.length ) return false; // Too big + for( Node use : n._outputs ) { + if( use==null ) continue; + int j=0; + while( j 0; // Only called when possible to inline diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java index 29e9900a..b74f9e6b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -221,6 +221,11 @@ public class FunNode extends RegionNode { public static boolean isInit(String name ) { return name!=null && name.endsWith("init>"); } public static boolean isInstance(String name ) { return name!=null && name.endsWith("."); } + // Allocation factories and instance initializers carry extra memory boilerplate. + public int inlineLimit() { + return isInstance() || (_name!=null && _name.endsWith(".")) ? 200 : 100; + } + // Function is public (callable from Start directly). public boolean isPublic( ) { // Never true for anonymous functions @@ -316,7 +321,7 @@ public class FunNode extends RegionNode { FunNode copyBody() { // Build the function body BitSet BitSet body = body(); - assert body.cardinality() < 100; + assert body.cardinality() < inlineLimit(); // Walk the body, cloning IdentityHashMap map = new IdentityHashMap<>(); BitSet visit = CodeGen.CODE.visit(); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java index f1ff2e14..07cd3831 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,11 +1,13 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter12Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index 80f70ff8..c1354e34 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; @@ -45,6 +46,7 @@ public class Chapter14FloatTest { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter14Test.java index f0ad6c2d..086bb824 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -2,12 +2,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter14Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 85dc7b47..f363847a 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,7 @@ import static org.junit.Assert.*; public class Chapter15Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 23ec549d..91e5cd38 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -1,12 +1,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter16Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 62d0b261..b6768d6f 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -1,12 +1,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter17bTest { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java index adc05f6f..82f99fc0 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -115,6 +115,7 @@ public class Chapter18Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 8cd5137c..cb7d492f 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -6,6 +6,7 @@ import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.codegen.CodeGen.Phase; import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -30,6 +31,7 @@ public class Chapter19Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen(""" diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 262b8604..40e9172e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -87,6 +88,7 @@ return f(s); } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen("return 0;"); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index ba71d1dd..8010e245 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -10,6 +10,7 @@ import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; import com.seaofnodes.simple.util.SB; import java.io.IOException; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -257,6 +258,7 @@ public class Chapter21Test { } + @Ignore @Test public void testJig() throws IOException { String src = diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java index ed678334..e8c080fd 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -96,6 +96,7 @@ public class Chapter22Test { } + @Ignore @Test public void testJig() throws IOException { String src = """ diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 05dfe1c2..ef65c6d9 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -12,6 +12,7 @@ import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; import java.io.IOException; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -36,6 +37,7 @@ public class Chapter24Test { } + @Ignore @Test public void testJig() throws IOException { String src = "int v0=0; v0 = arg && 0== 0 !=0;"; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index dce70897..354c6ec2 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -372,11 +372,11 @@ public class Chapter25Test { String obj = "build/objs/"+base+".o"; String exe = "build/objs/"+base+(TestC.OS.startsWith("Windows") ? ".exe" : ""); - String syms = TestC.exec(10,"nm",obj); + String syms = TestC.exec(TestC.TEST_TIMEOUT_SECONDS,"nm",obj); assertTrue(syms, syms.contains(" U sys.io.p_noInline")); TestC.linkExe(obj,null,null,new Ary<>(new String[]{SYS_FILE.toString()}),exe); - String rez = TestC.exec(10,exe); + String rez = TestC.exec(TestC.TEST_TIMEOUT_SECONDS,exe); assertEquals(expected,rez); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java index 5e32c8c6..64518b0d 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java @@ -16,6 +16,7 @@ import static org.junit.Assert.*; // Call a C driver program, which calls a Simple-generated .o, and self-checks. // Expects GCC from the default CLI, compiles C, compiles Simple, links and runs. public abstract class TestC { + public static final int TEST_TIMEOUT_SECONDS = 60; public static final String OS = System.getProperty("os.name"); public static final String CPU = System.getProperty("os.arch"); @@ -187,7 +188,7 @@ public abstract class TestC { } // Run GCC to link (optionally compile C driver code) - exec(10,params.asAry()); + exec(TEST_TIMEOUT_SECONDS,params.asAry()); } public static String exec( String... args ) throws IOException { @@ -229,9 +230,11 @@ public abstract class TestC { if( stdin==null ) p.getOutputStream().close(); if( seconds>0 && !p.waitFor(seconds,TimeUnit.SECONDS) ) { + String process = "pid="+p.pid()+", cpu="+ + p.info().totalCpuDuration().map(Object::toString).orElse("unknown"); p.destroyForcibly(); boolean stopped = p.waitFor(5,TimeUnit.SECONDS); - throw new IOException(String.join(" ",args)+"\ntimed out after "+seconds+" seconds"+ + throw new IOException(String.join(" ",args)+"\ntimed out after "+seconds+" seconds ("+process+")"+ (stopped ? "" : "; process did not terminate")+ "\nstdout:\n"+Files.readString(stdoutFile)+ "\nstderr:\n"+Files.readString(stderrFile)); 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 index 19c36ebb..d1368767 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testCast.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testCast.smp @@ -1 +1 @@ -struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -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-testMergeSort.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testMergeSort.smp index eddf1799..417eba72 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testMergeSort.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testMergeSort.smp @@ -1,21 +1,21 @@ // 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 _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 -> +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); + _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 -> +val _merge = { int[] b, int begin, int middle, int end, int[] a -> int i = begin, j = middle; for (int k = begin; k < end; k++) { @@ -30,7 +30,7 @@ val merge = { int[] b, int begin, int middle, int end, int[] a -> } }; -val copy_array = { int[] a, int begin, int end, int[] b -> +val _copy_array = { int[] a, int begin, int end, int[] b -> for (int k = begin; k < end; k++) b[k] = a[k]; }; @@ -41,6 +41,6 @@ int[] !b = new int[a#]; for (int i = 0; i < a#; i++) a[i] = a# - i; -merge_sort(a, b, a#); +_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 index 7fa66a33..fd76478f 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonFloat.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonFloat.smp @@ -1,5 +1,5 @@ // Newtons approximation to the square root -val sqrt = { flt x -> +val _sqrt = { flt x -> flt guess = x; while( 1 ) { flt next = (x/guess + guess)/2; @@ -8,4 +8,4 @@ val sqrt = { flt x -> } }; flt farg = arg; -return sqrt(farg) + sqrt(farg+2.0); +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 index b97da1f3..8912dcd9 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonInteger.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testNewtonInteger.smp @@ -1,5 +1,5 @@ // Newtons approximation to the square root -val sqrt = { int x -> +val _sqrt = { int x -> int guess = x; while( 1 ) { int next = (x/guess + guess)/2; @@ -7,4 +7,4 @@ val sqrt = { int x -> guess = next; } }; -return sqrt(arg) + sqrt(arg+2); +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 index f66ad621..951cdc32 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testString.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter20Test-testString.smp @@ -1,10 +1,10 @@ -struct String { +struct _String { u8[] cs; - new String={ u8[] b -> cs=b; }; + new _String={ u8[] b -> cs=b; }; int _hashCode; }; -val equals = { !String !self, !String s -> +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++ ) @@ -13,13 +13,13 @@ val equals = { !String !self, !String s -> return true; }; -val hashCode = { !String self -> +val _hashCode = { !_String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { !String self -> +val _hashCodeString = { !_String self -> int hash=0; if( self.cs ) { for( int i=0; i< self.cs#; i++ ) @@ -29,7 +29,7 @@ val _hashCodeString = { !String self -> return hash; }; -!String !s = new String(new u8[17]); +!_String !s = new _String(new u8[17]); s.cs[0] = 67; // C s.cs[1] = 108; // l -hashCode(s); +_hashCode(s); 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 index 2b1acfbe..58449f9c 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testNewtonFloat.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter21AllocTest-testNewtonFloat.smp @@ -1,6 +1,6 @@ // -*- mode: java; -*- // Newtons approximation to the square root -val test_sqrt = { flt x -> +val _test_sqrt = { flt x -> flt epsilon = 1e-15; flt guess = x; while( 1 ) { @@ -10,4 +10,4 @@ val test_sqrt = { flt x -> guess = next; } }; -flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0); +flt farg = arg; return _test_sqrt(farg) + _test_sqrt(farg+2.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 index f9866025..cc549808 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testInfiniteReturn.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testInfiniteReturn.smp @@ -1 +1 @@ -struct S { int i; }; !S !s = new S; while(1) s.i++; return s.i; +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-testNarrowCReturns.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testNarrowCReturns.smp new file mode 100644 index 00000000..21293a7a --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testNarrowCReturns.smp @@ -0,0 +1,12 @@ +{i8} c_i8="C"; {u8} c_u8="C"; +{i16} c_i16="C"; {u16} c_u16="C"; +{i32} c_i32="C"; {u32} c_u32="C"; +{int} c_i64="C"; +val test_i8={->return c_i8();}; +val test_u8={->return c_u8();}; +val test_i16={->return c_i16();}; +val test_u16={->return c_u16();}; +val test_i32={->return c_i32();}; +val test_u32={->return c_u32();}; +val test_i64={->return c_i64();}; +val test_cmp={->return c_i32()==-1;}; 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 index 9558bca4..ec9c6d50 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail.smp @@ -1,4 +1,4 @@ -struct Person { i32 age;}; -!Person !p = new Person; +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 index d3a27319..d5264aa2 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail2.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextFail2.smp @@ -1,5 +1,5 @@ - struct Person { i32 age;}; - !Person !p = new Person; + 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 index fdf4a7e9..c4398a89 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextSuccess.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter22Test-testSextSuccess.smp @@ -1,5 +1,5 @@ // Should fold away sign extend -struct Person { i8 age;}; -!Person !p = new Person; +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 deleted file mode 100644 index f7a5d202..00000000 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter23AllocTest-testJig21.smp +++ /dev/null @@ -1,16 +0,0 @@ -// -*- 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/Chapter24AllocTest-testJig21.smp b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig21.smp deleted file mode 100644 index f09915a1..00000000 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig21.smp +++ /dev/null @@ -1,16 +0,0 @@ -struct s0 { - bool v1; - i16 v2; - int v3; - i8 v4; - byte v5; -}; -while(new s0.v3) - while(new s0.v5< - 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 index 0423585b..572e4ad7 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testNewtonInteger.smp +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testNewtonInteger.smp @@ -1,5 +1,5 @@ // Newtons approximation to the square root -val sqrt = { int x -> +val _sqrt = { int x -> int guess = x; while( 1 ) { int next = (x/guess + guess)/2; @@ -8,4 +8,4 @@ val sqrt = { int x -> } }; int cast_int = arg+2; -return sqrt(arg) + sqrt(cast_int); +return _sqrt(arg) + _sqrt(cast_int); 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 deleted file mode 100644 index 5c9d3aa5..00000000 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24Test-testJig.smp +++ /dev/null @@ -1 +0,0 @@ -int v0=0; v0 = arg && 0== 0 !=0; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md b/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md index 3a064486..08371ae9 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/README.md @@ -2,15 +2,23 @@ English | [日本語](README.ja.md) -`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 +`cohorts.tsv` freezes 199 compilation entries matching Chapter 24's +`SpillStats`: 39, 52, 26, 24, and 58 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 +The original 212 entries were captured from the Chapter 24 tests before the +allocator audit's new correctness regressions. The 2026-10-07 refresh adds +Chapter22Test.testNarrowCReturns on x86 SystemV and Win64, matching the two +entries already measured in Chapters 22-24. The source is unchanged; only the +manifest's ABI spelling changes. The [cross-chapter matrix](../../../../../../../../docs/regalloc-spills.md) +checks matching test/CPU/ABI membership, including repeated compilations. +The same refresh removes all 15 Jig entries: six from cohort 23 and nine from +cohort 24. Jig methods are ignored scratch pads for debugging, not regression +tests or allocation benchmarks. Their frozen source copies were removed too. +These inputs 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. @@ -32,7 +40,17 @@ Chapter 25 cannot parse all earlier sources unchanged. Adaptations are explicit: 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. +- Local implementation names are private in eleven fixtures: the four Newton + variants that call their helper from the top level, Chapter 20's MergeSort, + String and Cast programs, and Chapter 22's three sign-extension programs and + InfiniteReturn. Their helpers/classes acquire an underscore prefix; operations, + inputs and final results are unchanged. This avoids exporting implementation + functions and allocation factories solely because Chapter 25 treats top-level + declarations as module members. Export/API fixtures, including NewtonExport, + StringExport, Person and the C-return wrappers, retain their public names. + These visibility adaptations change the generated workload and are recorded + separately from the allocator improvement in the cross-chapter comparison. +- Other source texts 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 diff --git a/chapter25/src/test/java/com/seaofnodes/simple/spill/cohorts.tsv b/chapter25/src/test/java/com/seaofnodes/simple/spill/cohorts.tsv index e1643e39..83b19d2a 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/cohorts.tsv +++ b/chapter25/src/test/java/com/seaofnodes/simple/spill/cohorts.tsv @@ -129,21 +129,12 @@ Chapter23 Chapter23Test.testCondSideEffOr arm SystemV Export Chapter23Test-testC 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 @@ -193,12 +184,6 @@ Chapter24 Chapter24Test.testFuncCall arm SystemV Export Chapter23Test-testFuncCa 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 @@ -211,3 +196,5 @@ Chapter21 BrainFuckTest.testBrainFuck arm SystemV Export BrainFuckTest-testBrain 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 +Chapter22 Chapter22Test.testNarrowCReturns x86_64_v2 SystemV Export Chapter22Test-testNarrowCReturns.smp +Chapter22 Chapter22Test.testNarrowCReturns x86_64_v2 win64 Export Chapter22Test-testNarrowCReturns.smp -- cgit v1.2.3