diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-07 19:10:51 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-07 19:10:51 -0700 |
| commit | 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc (patch) | |
| tree | c297b19a448bc3e0780437122646183240437a30 /chapter25 | |
| parent | aaec6f8136df6f7020bfc05f79ff5273adf73de1 (diff) | |
| download | Simple-2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc.tar.gz Simple-2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc.zip | |
Towrds getting RA spill counts comparable
Ignore JIGs. Get test suites more conical, so reg alloc spill counts are comparable
Diffstat (limited to 'chapter25')
36 files changed, 184 insertions, 180 deletions
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. + +<!-- spill-matrix:start --> +| 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 | +<!-- spill-matrix:end --> + + +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; i<len; i++ ) { + Node n = TINYBODY[i]; + addDep(n); + if( n==ret ) continue; + if( n instanceof ParmNode parm && parm.region()!=fun ) return false; + if( n!=fun && !(n instanceof ParmNode) && + !(n instanceof StoreNode) && !(n instanceof MemMergeNode) ) + return false; // Something unexpected + if( n.nOuts()>TINYBODY.length ) return false; // Too big + for( Node use : n._outputs ) { + if( use==null ) continue; + int j=0; + while( j<len && TINYBODY[j]!=use ) j++; + if( j<len ) continue; // Already in TINYBODY + if( len==TINYBODY.length ) { addDep(use); return false; } // Too big + TINYBODY[len++] = use; // Add to worklist + } + } + return true; + } + public void doInline() { assert _inline > 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(".<init>"); } + // Allocation factories and instance initializers carry extra memory boilerplate. + public int inlineLimit() { + return isInstance() || (_name!=null && _name.endsWith(".<new>")) ? 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<Node,Node> 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<<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 deleted file mode 100644 index df605c94..00000000 --- a/chapter25/src/test/java/com/seaofnodes/simple/spill/Chapter24AllocTest-testJig22.smp +++ /dev/null @@ -1,15 +0,0 @@ -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 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 |
