diff options
| author | Cliff Click <cliffc@acm.org> | 2026-09-20 17:46:47 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-09-20 17:46:47 -0700 |
| commit | 1e527b16b28f31b08cbb36b7b1bf2d689487a989 (patch) | |
| tree | eca664e141e3dd6e7091573befc1eb16d4a09bc8 | |
| parent | 6a5d13d459e40d242bea43f87a4717ad4fcf9e48 (diff) | |
| download | Simple-1e527b16b28f31b08cbb36b7b1bf2d689487a989.tar.gz Simple-1e527b16b28f31b08cbb36b7b1bf2d689487a989.zip | |
Split self-conflict phis once at a loop head
if this works, saves a copy-per-loop. If it fails, next round split as normal
33 files changed, 942 insertions, 183 deletions
diff --git a/chapter24/Makefile b/chapter24/Makefile index 55d5e70a..ec672d7f 100644 --- a/chapter24/Makefile +++ b/chapter24/Makefile @@ -178,3 +178,9 @@ lib/hamcrest-core-1.3.jar: tags: $(main_javas) $(test_javas) @rm -f TAGS @$(CTAGS) -e --recurse=yes --extra=+q --fields=+fksaiS $(SRC) $(TST) + +spill-stats: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag + @[ -d build/objs ] || mkdir -p build/objs + @$(JVM) com.seaofnodes.simple.SpillStats + +.PHONY: spill-stats diff --git a/chapter24/README.md b/chapter24/README.md index 3774c80a..93f54a0d 100644 --- a/chapter24/README.md +++ b/chapter24/README.md @@ -158,23 +158,24 @@ those found by the peephole rules; we can then run the peephole rules on nodes with improved types, to see if unrelated peepholes can fire - such as newly discovered constants replacing computations with ConstantNodes. -Example: +The following is SSA pseudocode; `phi` denotes a merge, not Simple syntax. -```java +```text int x0 = 1; // x0 = 1 while( rand ) { x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT) x2 = 2 - x1; // x2 = BOT = 2 - BOT } -return x2 +return x1 ``` -Without SCCP, this small program cannot remove the computation of `x` and hence -the loop either. A glance at the program tells us `x` must always be a `1` but +Without SCCP, this small program cannot fold the computation of `x`. +A glance at the program tells us `x` must always be a `1` but the bottom-up (pessimistic) approach decides that since x1 is BOT, x2 must be BOT so x1 must be BOT. We need the optimistic approach to break the stalemate, and just *assume* x1 is `1`, and then we can discover that x2 is -also a `1`. +also a `1`. Folding the value does not prove the loop terminates or make +its condition and side effects removable. The algorithm progresses from left to right and stops when no more changes @@ -194,9 +195,9 @@ Since our control flow is in the same graph as our data flow (that's the major point of Sea-of-Nodes!), we need not do anything special and our algorithm is *conditional* already. Again an example is interesting: -Example: +Again using SSA pseudocode: -```java +```text int x0 = 1; // x0 = 1 while( rand ) { x1 = phi(x0,x4); // x1 = BOT = phi(1,BOT) @@ -205,7 +206,7 @@ while( rand ) { else x3 = 99; // x3 = 99 x4 = phi(x2,x3); // x4 = BOT = phi(BOT,99) } -return x4 +return x1 ``` Again the algorithm progresses from left to right, although this time not all @@ -259,7 +260,7 @@ Such edges make up a [Call Graph](https://en.wikipedia.org/wiki/Call_graph). We extend the normal SCCP algorithm to observe when a `Call`s function pointer input changes - when it picks up new function targets. There are only a finite number so we represent them exactly with *function indices* as described in an -early chapter. (Separate compilation adds a special index for the infinite +earlier chapter. (Separate compilation adds a special index for the infinite unknown functions that are called outside this compilation unit). Once we observe a new *fidx* at a `Call`, we *link* the `Call` with the `Fun`, @@ -277,3 +278,57 @@ Other than discovering a few new edges as the algorithm proceeds, the core algorithm is unchanged. We are guaranteed to terminate with a fixed point solution, and may discover e.g. certain call parameters are constants (or e.g. not-null) on all calling paths. + + +## RegAlloc improvements: try cold loop splits first + +A loop Phi and its backedge can belong to one live range even though their +values must coexist at some instruction. This self-conflict requires splitting +the range. Chapter 23 split the Phi's definition and incoming values right away. +This chapter first leaves the hot definition/backedge alone and tries the +outside-loop copies. If coloring succeeds, it avoids moves on every iteration. +Other conflicts, including two-address operations, keep their existing handling. + +The allocator remembers which Phis have had this chance. If the same Phi +self-conflicts again, the next attempt uses the ordinary aggressive splitting. +The record uses Phi identity because live ranges are rebuilt each round. It +also covers a backedge-only conflict where the first attempt inserts no copy: +that attempt must still consume the one permitted delay. A regression checks +both the cheaper first attempt and the mandatory fallback. + +Run `make spill-stats`. All rows use **Chapter 24's compiler**, optimizer seed +123, and the same source/target combinations as the earlier cohort tables. +These Windows results combine x86 SystemV/Win64 and RISC-V/ARM SystemV. + +| Program cohort | Compilations | Split/move count | Loop-weighted count | +|---|---:|---:|---:| +| Chapter 20 | 39 | 331 | 457 | +| Chapter 21 | 52 | 436 | 975 | +| Chapter 22 | 24 | 67 | 67 | +| Chapter 23 | 30 | 66 | 115 | +| Chapter 24 | 67 | 432 | 1,342 | +| **Total** | **212** | **1,332** | **2,956** | + +`_spills` counts retained SplitNodes, including register moves. `_spillScaled` +weights those moves by `8^loopDepth`; it is a cost estimate, not measured memory +traffic. Diagnostic machine graphs contribute no allocations to this table. +The reporter checks allocation legality and native/emulated results even when +spill expectations differ, and exits unsuccessfully for either kind of failure. + +With only the cold-first rule disabled, the same compiler and programs produce +**1,338 moves / 2,962 weighted moves**. The rule saves six of each. A RISC-V +MergeSort case adds one move, offset by improvements in other MergeSort cases, +Sieve, and an ARM loop case. Aggregate measurements justify accepting that +local regression; the improvement here is modest, not universal. + +On cohorts 20-23 alone, Chapter 23 produced 933 / 1,745; Chapter 24 produces +900 / 1,614. Only six of each reduction comes from this allocator change. The +rest comes from other compiler changes, including SCCP; comparing chapters +alone would overstate the heuristic's benefit. + +The older cohorts retain the 64-bit Person, guarded String, and smaller emulator +argument list. Revised Jig, BubbleSort, Newton, and stack-argument inputs belong +to cohort 24 alongside this chapter's existing tests. The frozen String workload +also exposed a missing null check in the inlining dominator walk; that correctness +fix is included on both sides of the heuristic comparison. Area/cost spill +ranking remains for Chapter 25. diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 6f6cf7a8..4bf4ac35 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -59,6 +59,9 @@ public class RegAlloc { // ----------------------- // Live ranges with self-conflicts or no allowed registers private final IdentityHashMap<LRG,String> _failed = new IdentityHashMap<>(); + // Loop Phis get one chance to color after only cold self-conflict splits. + // If the same Phi self-conflicts again, split its hot def/backedge also. + private final IdentityHashMap<PhiNode,String> _deferredLoopSelf = new IdentityHashMap<>(); void fail( LRG lrg ) { assert lrg.leader(); _failed.put(lrg,""); @@ -348,6 +351,19 @@ public class RegAlloc { Node[] conflicts = lrg._selfConflicts.keySet().toArray(new Node[0]); Arrays.sort(conflicts, (x,y) -> x._nid - y._nid ); + // First encounter with a loop Phi: try only cold splits this round. + // Remember the Phi across rounds so a persistent self-conflict forces + // the hot def/backedge splits on the next encounter. + IdentityHashMap<PhiNode,String> deferred = new IdentityHashMap<>(); + for( Node def : conflicts ) { + if( def instanceof PhiNode phi && phi.region() instanceof LoopNode ) + deferLoopSelf(phi,deferred); + for( Node use : def._outputs ) + if( use instanceof PhiNode phi && phi.region() instanceof LoopNode && + phi._inputs.find(def)==2 ) + deferLoopSelf(phi,deferred); + } + // For all conflicts for( Node def : conflicts ) { assert lrg(def)==lrg; // Might be conflict use-side @@ -356,6 +372,7 @@ public class RegAlloc { for( int i=0; i<def._outputs._len; i++ ) { Node use = def.out(i); if( (use instanceof PhiNode phi && + !(deferred.containsKey(phi) && phi.region() instanceof LoopNode && phi._inputs.find(def)==2) && !(phi.region() instanceof LoopNode loop && phi.in(2)==def && def.cfg0().idepth() > loop.idepth() ) ) || (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) ) insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg ); @@ -364,10 +381,12 @@ public class RegAlloc { // Phi slot 1 (and not all inputs), because Phis extend the live range. // TODO: split before all inputs (except the last; at least 1 split here must be extra) if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) { - SplitNode split = makeSplit("def/self",round,lrg); - insertAfterAndReplace(split,def,false); - if( split.nOuts()==0 ) - split.killOrdered(); + if( !deferred.containsKey(phi) ) { + SplitNode split = makeSplit("def/self",round,lrg); + insertAfterAndReplace(split,def,false); + if( split.nOuts()==0 ) + split.killOrdered(); + } insertBefore(phi,1,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range @@ -377,6 +396,13 @@ public class RegAlloc { return true; } + private void deferLoopSelf(PhiNode phi, IdentityHashMap<PhiNode,String> deferred) { + if( !_deferredLoopSelf.containsKey(phi) ) { + _deferredLoopSelf.put(phi,""); + deferred.put(phi,""); + } + } + // Generic: split around the outermost loop with non-split def/uses. This // covers both self-conflicts (once we split deep enough) and register diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index a7e50c39..9cf6c641 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -82,8 +82,9 @@ public class CallEndNode extends CFGNode implements MultiNode { // Disallow self-recursive inlining (loop unrolling by another name). // Disallow if still folding other things, as it makes other // dependency checks carry long chains of half-folded calls. + // Dead control may end the walk before an enclosing function. CFGNode idom = call; - while( true ) { + while( idom!=null ) { idom = idom.idom(); if( idom instanceof FunNode ) break; if( idom instanceof CallEndNode cend && cend._folding ) break; @@ -107,7 +108,7 @@ public class CallEndNode extends CFGNode implements MultiNode { // Bump the global version number invalidating them en-masse. CodeGen.CODE.invalidateIDepthCaches(); return this; - } else { + } else if( idom!=null ) { addDep(idom); } } else { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index de6c5a6b..43758f8b 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -79,7 +79,7 @@ val brain_fuck = { -> assertEquals(brain_fuck.length(),A5.ld4s(ptr_arm)); for( int i=0; i<brain_fuck.length(); i++ ) - assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr+4+i)); + assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr_arm+4+i)); } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index e668f90d..70ddd435 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -4,7 +4,9 @@ import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; -import java.io.IOException; +import com.seaofnodes.simple.print.ASMPrinter; +import org.junit.Assert; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -26,6 +28,8 @@ return f(s); } + @org.junit.Rule public final org.junit.rules.ErrorCollector _errors = new org.junit.rules.ErrorCollector(); + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } @@ -47,34 +51,36 @@ return f(s); assertEquals("0", Eval2.eval(code, 2)); } - static void testCPU( String src, String cpu, String os, int spills, String stop ) { + // Collect differences so every target runs; JUnit still fails the test. + private void testTarget(String src, String cpu, String os, int spills, String stop) { + _errors.checkSucceeds(() -> { testCPU(src,cpu,os,spills,stop); return null; }); + } + + static void testCPU(String src, String cpu, String os, int spills, String stop) { CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); - if( stop != null ) - assertEquals(stop, code._stop.toString()); + SpillStats.record(code,"Chapter20",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + if( stop!=null ) assertEquals(stop,code._stop.toString()); } - private static void testAllCPUs( String src, int spills, String stop ) { - testCPU(src,"x86_64_v2", "SystemV",spills,stop); - testCPU(src,"riscv" , "SystemV",spills,stop); - testCPU(src,"arm" , "SystemV",spills,stop); + private void testAllCPUs( String src, int spills, String stop ) { + testTarget(src,"x86_64_v2", "SystemV",spills,stop); + testTarget(src,"riscv" , "SystemV",spills,stop); + testTarget(src,"arm" , "SystemV",spills,stop); } @Test public void testAlloc0() { - testCPU("return new u8[arg];","x86_64_v2", "SystemV",3,"return []u8;"); - testCPU("return new u8[arg];","riscv" , "SystemV",5,"return []u8;"); - testCPU("return new u8[arg];","arm" , "SystemV",5,"return []u8;"); + testTarget("return new u8[arg];","x86_64_v2","SystemV",4,"return []u8;"); + testTarget("return new u8[arg];","riscv","SystemV",5,"return []u8;"); + testTarget("return new u8[arg];","arm","SystemV",5,"return []u8;"); } @Test public void testBasic1() { String src = "return arg | 2;"; - testCPU(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); - testCPU(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); - testCPU(src,"arm" , "SystemV",0,"return (ori,arg);"); + testTarget(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); + testTarget(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); + testTarget(src,"arm" , "SystemV",0,"return (ori,arg);"); } @Test @@ -90,47 +96,44 @@ val sqrt = { int x -> guess = next; } }; -int cast_int = arg+2; -return sqrt(arg) + sqrt(cast_int); +return sqrt(arg) + sqrt(arg+2); """; - testCPU(src,"x86_64_v2", "Win64" ,48,null); - testCPU(src,"riscv" , "SystemV",19,null); - testCPU(src,"arm" , "SystemV",19,null); + testTarget(src,"x86_64_v2", "SystemV",48,null); + testTarget(src,"riscv" , "SystemV",17,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test - public void testNewtonFloat() throws IOException { + public void testNewtonFloat() { String src = """ -val test_sqrt = { flt x -> - flt epsilon = 1e-15; +// Newtons approximation to the square root +val sqrt = { flt x -> 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; + if( next == guess ) return guess; guess = next; } }; -flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0); +flt farg = arg; +return sqrt(farg) + sqrt(farg+2.0); """; - testCPU(src,"x86_64_v2", "SystemV",39,null); - testCPU(src,"riscv" , "SystemV",17,null); - testCPU(src,"arm" , "SystemV",18,null); + testTarget(src,"x86_64_v2", "SystemV",23,null); + testTarget(src,"riscv" , "SystemV",18,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test public void testAlloc2() { String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"; - testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); - testCPU(src,"riscv" , "SystemV", 6,"return .[];"); - testCPU(src,"arm" , "SystemV", 6,"return .[];"); + testTarget(src,"x86_64_v2","SystemV",3,"return .[];"); + testTarget(src,"riscv","SystemV",6,"return .[];"); + testTarget(src,"arm","SystemV",6,"return .[];"); } - - @Test - public void testArray1() throws IOException { + public void testArray1() { String src = """ int[] !ary = new int[arg]; @@ -142,22 +145,19 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; - testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); - testCPU(src,"riscv" , "SystemV", 8,"return (add,.[],(mul,.[],1000));"); - testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); + testTarget(src,"x86_64_v2", "SystemV",9,"return .[];"); + testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); + testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } - @Test - public void testString() throws IOException { - String src = -""" + public void testString() { + String src = """ 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; @@ -167,7 +167,6 @@ val equals = { String self, String s -> return true; }; -// Return the String hashCode (cached, and never 0) val hashCode = { String self -> self._hashCode ? self._hashCode @@ -176,23 +175,30 @@ val hashCode = { String self -> val _hashCodeString = { String self -> int hash=0; - for( int i=0; i< self.cs#; i++ ) - hash = hash*31 + self.cs[i]; + 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 { cs = new u8[17]; }; +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s); """; - testCPU(src,"x86_64_v2", "SystemV", 9,null); - testCPU(src,"riscv" , "SystemV", 3,null); - testCPU(src,"arm" , "SystemV", 3,null); + testTarget(src,"x86_64_v2", "SystemV",9,null); + testTarget(src,"riscv" , "SystemV",4,null); + testTarget(src,"arm" , "SystemV",3,null); } @Test public void testCast() { String src = "struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1;"; - testCPU(src,"x86_64_v2", "SystemV",2,null); - testCPU(src,"riscv" , "SystemV",2,null); - testCPU(src,"arm" , "SystemV",2,null); + testTarget(src,"x86_64_v2","SystemV",1,null); + testTarget(src,"riscv","SystemV",2,null); + testTarget(src,"arm","SystemV",2,null); } @Test @@ -210,9 +216,9 @@ if (b2) if (b1) return 1; if (b1) return 2; return 0; """; - testCPU(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); - testCPU(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); - testCPU(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); } @Test @@ -225,8 +231,126 @@ while (arg > 0) { } return arg; """; - testCPU(src,"x86_64_v2", "SystemV",3,null); - testCPU(src,"riscv" , "SystemV",2,null); - testCPU(src,"arm" , "SystemV",2,null); + testTarget(src,"x86_64_v2", "SystemV",3,null); + testTarget(src,"riscv" , "SystemV",2,null); + testTarget(src,"arm" , "SystemV",2,null); + } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @Test + public void testBrainfuck() { + var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(java.nio.charset.StandardCharsets.UTF_8); + var encoded = new StringBuilder("u8[] !program = new u8[").append(program.length).append("];"); + for (int i = 0; i < program.length; i++) { + int value = program[i] & 0xFF; + encoded.append("program[").append(i).append("] = ").append(value).append(";"); + } + + String src = encoded + """ + +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; +"""; + testTarget(src,"x86_64_v2", "SystemV",40,null); + testTarget(src,"riscv" , "SystemV",28,null); + testTarget(src,"arm" , "SystemV",28,null); + //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @Test + public void testMergeSort() { + String src = +""" +// 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; +"""; + testTarget(src,"x86_64_v2", "SystemV",52,null); + testTarget(src,"riscv" , "SystemV",44,null); + testTarget(src,"arm" , "SystemV",44,null); +//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + } + } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java new file mode 100644 index 00000000..2d0493e5 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java @@ -0,0 +1,55 @@ +package com.seaofnodes.simple; + +import java.io.IOException; +import java.nio.file.*; +import org.junit.Test; + +// Revised Chapter 20 examples introduced with native encoding. +public class Chapter21AllocTest { + @Test + public void testNewtonInteger() { + String src = +""" +// 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); +"""; + Chapter21Test.testCPU(src,"x86_64_v2", "Win64" ,48,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV",19,null); + Chapter21Test.testCPU(src,"arm" , "SystemV",19,null); + } + + @Test + public void testNewtonFloat() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) + + "flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0);"; + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",39,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV",17,null); + Chapter21Test.testCPU(src,"arm" , "SystemV",18,null); + } + + @Test + public void testArray1() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/array1.smp")); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); + Chapter21Test.testCPU(src,"riscv" , "SystemV", 8,"return (add,.[],(mul,.[],1000));"); + Chapter21Test.testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); + } + + + @Test + public void testString() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash21.smp")); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV", 3,null); + Chapter21Test.testCPU(src,"arm" , "SystemV", 3,null); + } + +} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 3910b7a5..7b22389e 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -216,27 +216,10 @@ public class Chapter21Test { } - @Test + // Frozen Jig runs in Chapter23AllocTest; the revised input is in Chapter24AllocTest. + @Test @Ignore public void testJig() throws IOException { - String src = -""" -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; -"""; + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); testCPU(src,"x86_64_v2", "Win64" ,-1,null); testCPU(src,"riscv" , "SystemV",-1,null); testCPU(src,"arm" , "SystemV",-1,null); @@ -244,10 +227,8 @@ return new s0.v1; static void testCPU( String src, String cpu, String os, int spills, String stop ) { CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.record(code,"Chapter21",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); } @@ -261,7 +242,7 @@ return new s0.v1; } @Test public void testInfinite() { - String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + String src = "struct S { int i; }; S !s = new S; while(1) s.i++;"; testCPU(src,"x86_64_v2", "SystemV",0,"return Top;"); testCPU(src,"riscv" , "SystemV",2,"return Top;"); testCPU(src,"arm" , "SystemV",2,"return Top;"); @@ -542,19 +523,8 @@ val fib = {int n -> } @Test public void testPerson() throws IOException { - String src = - """ - struct Person { - i32 age; - }; - - val fcn = { Person?[] ps, int x -> - if( ps[x] ) - ps[x].age++; - }; - """; String person = "6\n"; - TestC.run(src, "person", null, person, 0); + TestC.run("person21", person, 0); // Memory layout starting at PS: int ps = 1<<16; // Person array pointer starts at heap start @@ -565,7 +535,7 @@ val fib = {int n -> int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; - EvalRisc5 R5 = TestRisc5.build("person", src, ps, 0, false); + EvalRisc5 R5 = TestRisc5.build("person21", ps, 0, false); R5.regs[riscv.A1] = 1; // Index 1 R5.st8(ps,3); // Length R5.st8(ps+1*8,p0); @@ -581,7 +551,7 @@ val fib = {int n -> assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); - EvalArm64 A5 = TestArm64.build("person", src, ps, 0, false); + EvalArm64 A5 = TestArm64.build("person21", ps, 0, false); A5.regs[arm.X1] = 1; // Index 1 A5.st8(ps, 3); A5.st8(ps+1*8,p0); @@ -601,19 +571,12 @@ val fib = {int n -> @Test public void testArgCount() throws IOException { // Test passes more args than registers in Sys5, which is far far more // than what Win64 allows - so Win64 gets a lot more spills here. - String src = -""" -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 ; -}; -"""; String arg_count = "191.000000\n"; + TestC.run("arg_count", arg_count, + TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); - TestC.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); - EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", src, 0, 4, false); + EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", 0, 0, false); // Todo: handle stack(imaginary stack in emulator) // pass in float arguments @@ -643,7 +606,7 @@ val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, i assertEquals(22.8, result, 0.00001); // arm - EvalArm64 A5 = TestArm64.build("no_stack_arg_count", src, 0, 4, false); + EvalArm64 A5 = TestArm64.build("no_stack_arg_count", 0, 0, false); A5.fregs[arm.D0 - arm.D_OFFSET] = 1.1; A5.fregs[arm.D1 - arm.D_OFFSET] = 1.1; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java index fa9036d2..7c2f4f69 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -13,27 +13,19 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter22Test { - - @Test - public void testJig() throws IOException { - String src = -""" -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; + @Test public void testInfiniteReturn() { + String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + testCPU(src,"x86_64_v2","SystemV",0,"return Top;"); + testCPU(src,"riscv","SystemV",2,"return Top;"); + testCPU(src,"arm","SystemV",2,"return Top;"); } - return f2; -}; -fib(10); -"""; + + // Frozen Jig runs in Chapter23AllocTest; the revised input is in Chapter24AllocTest. + @Test @Ignore + public void testJig() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); + //String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); testCPU(src,"x86_64_v2", "Win64" ,-1,null); testCPU(src,"riscv" , "SystemV",-1,null); testCPU(src,"arm" , "SystemV",-1,null); @@ -41,10 +33,8 @@ fib(10); static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.record(code,"Chapter22",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); return code; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java new file mode 100644 index 00000000..cd8c43cf --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java @@ -0,0 +1,34 @@ +package com.seaofnodes.simple; + +import java.io.IOException; +import java.nio.file.*; +import org.junit.Test; + +// Revised or newly enabled allocation examples in Chapter 23. +public class Chapter23AllocTest { + @Test + public void testString() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); + Chapter23Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); + Chapter23Test.testCPU(src,"riscv" , "SystemV", 3,null); + Chapter23Test.testCPU(src,"arm" , "SystemV", 3,null); + } + + @Test + public void testJig21() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); + Chapter23Test.testCPU(src,"x86_64_v2", "Win64" ,-1,null); + Chapter23Test.testCPU(src,"riscv" , "SystemV",-1,null); + Chapter23Test.testCPU(src,"arm" , "SystemV",-1,null); + } + + @Test + public void testJig22() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); + //String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); + Chapter23Test.testCPU(src,"x86_64_v2", "Win64" ,-1,null); + Chapter23Test.testCPU(src,"riscv" , "SystemV",-1,null); + Chapter23Test.testCPU(src,"arm" , "SystemV",-1,null); + } + +} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 23c88613..118607c9 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -69,7 +69,8 @@ public class Chapter23Test { } private static void checkOrRhsLoop(String src) throws IOException { - CodeGen code = new CodeGen(src).driver("riscv", "SystemV", null); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV", null); + SpillStats.record(code,"Chapter23","riscv","SystemV"); for (int arg : new int[]{0, 1, 2, 3}) { byte[] image = new byte[1 << 20]; System.arraycopy(code._encoding.bits(), 0, image, 0, code._encoding._bits.size()); @@ -85,20 +86,19 @@ public class Chapter23Test { @Test public void testJig() throws IOException { - //String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); - String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); - testCPU(src,"x86_64_v2", "Win64" ,-1,null); - testCPU(src,"riscv" , "SystemV",-1,null); - testCPU(src,"arm" , "SystemV",-1,null); + String src = +""" +var apply = { i64 x, { i64 -> u32 } fcn -> + return fcn(x); +} +"""; } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.record(code,"Chapter23",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); return code; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java new file mode 100644 index 00000000..1631705b --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java @@ -0,0 +1,163 @@ +package com.seaofnodes.simple; + +import java.io.IOException; +import java.nio.file.*; +import com.seaofnodes.simple.node.cpus.arm.arm; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import org.junit.Test; +import static org.junit.Assert.*; + +// Revised inherited programs belong to the chapter which changed their inputs. +public class Chapter24AllocTest { + @Test + public void testNewtonInteger() { + String src = +""" +// 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); +"""; + Chapter24Test.testCPU(src,"x86_64_v2", "Win64" ,48,null); + Chapter24Test.testCPU(src,"riscv" , "SystemV",19,null); + Chapter24Test.testCPU(src,"arm" , "SystemV",19,null); + } + + @Test + public void testJig21() throws IOException { + String src = +""" +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; +"""; + Chapter24Test.testCPU(src,"x86_64_v2", "Win64" ,-1,null); + Chapter24Test.testCPU(src,"riscv" , "SystemV",-1,null); + Chapter24Test.testCPU(src,"arm" , "SystemV",-1,null); + } + + @Test public void testStackArguments() throws IOException { + // Test passes more args than registers in Sys5, which is far far more + // than what Win64 allows - so Win64 gets a lot more spills here. + String src = +""" +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 ; +}; +"""; + String arg_count = "191.000000\n"; + + TestC.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); + + EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", src, 0, 4, false); + + // Todo: handle stack(imaginary stack in emulator) + // pass in float arguments + R5.fregs[riscv.FA0 - riscv.F_OFFSET] = 1.1; + R5.fregs[riscv.FA1 - riscv.F_OFFSET] = 1.1; + R5.fregs[riscv.FA2 - riscv.F_OFFSET] = 1.1; + R5.fregs[riscv.FA3 - riscv.F_OFFSET] = 1.1; + R5.fregs[riscv.FA4 - riscv.F_OFFSET] = 1.1; + R5.fregs[riscv.FA5 - riscv.F_OFFSET] = 1.1; + R5.fregs[riscv.FA6 - riscv.F_OFFSET] = 1.1; + R5.fregs[riscv.FA7 - riscv.F_OFFSET] = 1.1; + + // a0 is passed in arg + R5.regs[riscv.A1] = 2; + R5.regs[riscv.A2] = 2; + R5.regs[riscv.A3] = 2; + R5.regs[riscv.A4] = 2; + R5.regs[riscv.A5] = 2; + R5.regs[riscv.A6] = 2; + R5.regs[riscv.A7] = 2; + + int trap = R5.step(100); + assertEquals(0,trap); + + double result = R5.fregs[riscv.FA0 - riscv.F_OFFSET]; + + assertEquals(22.8, result, 0.00001); + + // arm + EvalArm64 A5 = TestArm64.build("no_stack_arg_count", src, 0, 4, false); + + A5.fregs[arm.D0 - arm.D_OFFSET] = 1.1; + A5.fregs[arm.D1 - arm.D_OFFSET] = 1.1; + A5.fregs[arm.D2 - arm.D_OFFSET] = 1.1; + A5.fregs[arm.D3 - arm.D_OFFSET] = 1.1; + A5.fregs[arm.D4 - arm.D_OFFSET] = 1.1; + A5.fregs[arm.D5 - arm.D_OFFSET] = 1.1; + A5.fregs[arm.D6 - arm.D_OFFSET] = 1.1; + A5.fregs[arm.D7 - arm.D_OFFSET] = 1.1; + + A5.regs[arm.X1] = 2; + A5.regs[arm.X2] = 2; + A5.regs[arm.X3] = 2; + A5.regs[arm.X4] = 2; + A5.regs[arm.X5] = 2; + A5.regs[arm.X6] = 2; + A5.regs[arm.X7] = 2; + + int trap_arm = A5.step(100); + assertEquals(0,trap_arm); + + double result1 = A5.fregs[arm.D0 - arm.D_OFFSET]; + assertEquals(22.8, result1, 0.00001); + } + + @Test + public void testJig22() throws IOException { + String src = +""" +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); +"""; + Chapter24Test.testCPU(src,"x86_64_v2", "Win64" ,-1,null); + Chapter24Test.testCPU(src,"riscv" , "SystemV",-1,null); + Chapter24Test.testCPU(src,"arm" , "SystemV",-1,null); + } + + @Test + public void testBubbleSort() throws IOException { + //String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); + String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); + Chapter24Test.testCPU(src,"x86_64_v2", "Win64" ,-1,null); + Chapter24Test.testCPU(src,"riscv" , "SystemV",-1,null); + Chapter24Test.testCPU(src,"arm" , "SystemV",-1,null); + } +} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index a1dd6eaa..93c778c8 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -12,6 +12,8 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter24Test { + @Test public void testColdLoopSelfConflict() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coldLoopSelfConflict(); } + @Test public void testPrintingDeadFunction() throws Exception { var code = new CodeGen("return 0;").parse(); var tfp = TypeFunPtr.TEST; @@ -40,10 +42,8 @@ public class Chapter24Test { static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.record(code,"Chapter24",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); return code; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java index 9c7c1360..19a1facf 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -57,7 +57,7 @@ public class MergeSortTest { for( int prime : primes ) sb.p(prime).p(", "); String sprimes = sb.p("]").toString(); - TestC.run(src, "sort", null, sprimes, 40); + TestC.run(src, "sort", null, sprimes, 34); EvalRisc5 R5 = TestRisc5.build("src/test/java/com/seaofnodes/simple/progs",src, "sort", "merge_sort", 0, 36, false); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/SpillStats.java b/chapter24/src/test/java/com/seaofnodes/simple/SpillStats.java new file mode 100644 index 00000000..ad044a52 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import java.util.Map; +import java.util.TreeMap; +import org.junit.runner.*; +import org.junit.runner.notification.*; + +// Run existing tests and sum actual allocations, including ones without goldens. +// Helpers call record after allocation; ordinary JUnit runs collect nothing. +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; } + public static void record(CodeGen code, String cohort, String cpu, String abi) { + if( ACTIVE==null ) return; + String test = ACTIVE._test.getTestClass().getSimpleName()+"."+ACTIVE._test.getMethodName(); + for( String key : new String[]{cohort+","+cpu+","+abi,cohort+",ALL,ALL"} ) { + long[] sum = ACTIVE._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); + } + + // The same native helpers serve old and new program cohorts. + public static void recordNative(CodeGen code, String cpu, String abi) { + String cohort = ACTIVE!=null && (ACTIVE._test.getTestClass()==Chapter24Test.class || ACTIVE._test.getTestClass()==Chapter24AllocTest.class) + ? "Chapter24" : ACTIVE!=null && ACTIVE._test.getTestClass()==Chapter23Test.class + ? "Chapter23" : ACTIVE!=null && ACTIVE._test.getTestClass()==Chapter22Test.class + ? "Chapter22" : "Chapter21"; + record(code,cohort,cpu,abi); + } + + // Keep running every CPU and native result check when measuring quality. + // A changed golden still makes spill-stats fail at the end. + public static void checkSpills(int expected, int actual) { + if( expected==-1 ) 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 ClassNotFoundException { + if( args.length==0 ) args = new String[]{"Chapter20Test","Chapter21Test","Chapter21AllocTest","Chapter22Test","Chapter23Test","Chapter23AllocTest","Chapter24Test","Chapter24AllocTest","BrainFuckTest","MergeSortTest"}; + Class<?>[] tests = new Class<?>[args.length]; + for( int i=0; i<args.length; i++ ) + tests[i] = Class.forName("com.seaofnodes.simple."+args[i]); + ACTIVE = new SpillStats(); + JUnitCore junit = new JUnitCore(); + junit.addListener(ACTIVE); + Result result = junit.run(tests); + boolean passed = result.wasSuccessful() && ACTIVE._qualityFailures==0; + if( !result.wasSuccessful() ) System.out.println("FAILED test run: totals are not a complete comparison."); + else if( !passed ) System.out.println("Spill expectations differ; allocation and runtime checks passed."); + 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]); + } + for( Failure failure : result.getFailures() ) System.err.println(failure.getTrace()); + System.out.println("Tests: "+result.getRunCount()+", failures: "+result.getFailureCount()); + System.out.println("Spill golden failures: "+ACTIVE._qualityFailures); + ACTIVE = null; + if( !passed ) System.exit(1); + } +} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java index d0fdae0c..02b15171 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -30,12 +30,11 @@ public class TestArm64 { public static EvalArm64 build( String dir, String src, String file, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null); + SpillStats.recordNative(code,"arm","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded - int delta = spills>>3; - if( delta == 0 ) delta =1; - if( spills != -1 ) assertEquals("Expect spills:", spills, code._regAlloc._spillScaled, delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); // Image byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java b/chapter24/src/test/java/com/seaofnodes/simple/TestC.java index aed9f844..3b3aabc0 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TestC.java @@ -77,15 +77,13 @@ public abstract class TestC { String exe = OS.startsWith("Windows") ? bin+".exe" : bin; // Compile simple, emit ELF CodeGen code = new CheckedCodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); + SpillStats.recordNative(code,CPU_PORT,simple_conv); String result = gcc(obj, c_conv, cfile, false, exe ); assertEquals(expected,result); // Allocation quality not degraded - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); } public static String gcc( String obj, String c_conv, String cfile, boolean stdin, String... args ) throws IOException { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java index 72a05c61..ceba3157 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -28,13 +28,11 @@ public abstract class TestRisc5 { public static EvalRisc5 build( String dir, String src, String file, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null); + SpillStats.recordNative(code,"riscv","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); // Image byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) 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 ec666653..20da40fd 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -206,6 +206,33 @@ public class RegAllocTestSupport { assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); } + public static void coldLoopSelfConflict() { + for( boolean phiConflict : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op init = new Op(A,null,null,false,code._start); + LoopNode loop = new LoopNode(null,code._start); + PhiNode phi = new PhiNode("loop",TypeInteger.BOT,loop,init,null); + Op back = new Op(A,A,null,false,loop,phi); + phi.setDef(2,back); + Op use = new Op(null,A,null,false,loop,phi); + loop.setDef(2,loop); + LRG lrg = alloc.newLRG(phi); + lrg._mask = A; + alloc.union(lrg,init); alloc.union(lrg,back); + lrg.selfConflict(back); + if( phiConflict ) lrg.selfConflict(phi); + assertTrue(alloc.splitSelfConflict((byte)0,lrg)); + assertSame(phi,use.in(1)); // First try leaves the hot definition alone. + assertSame(back,phi.in(2)); + if( phiConflict ) assertTrue(phi.in(1) instanceof SplitNode); + // Even if the first attempt made no graph change, retry must split. + assertTrue(alloc.splitSelfConflict((byte)1,lrg)); + assertTrue(phi.in(2) instanceof SplitNode); + if( phiConflict ) assertTrue(use.in(1) instanceof SplitNode); + } + } + public static void coalescing() { // Merge, incompatible masks, interference, capacity, and adjacency remapping. for( int kind=0; kind<5; kind++ ) { diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/arg_count.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/arg_count.smp new file mode 100644 index 00000000..6b6bc0ae --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/arg_count.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/chapter24/src/test/java/com/seaofnodes/simple/progs/array1.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/array1.smp new file mode 100644 index 00000000..6b10f92c --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/array1.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/chapter24/src/test/java/com/seaofnodes/simple/progs/jig.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/jig.smp new file mode 100644 index 00000000..f7a5d202 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/jig.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/chapter24/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp new file mode 100644 index 00000000..be2dffec --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp @@ -0,0 +1,12 @@ +// -*- 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; + } +}; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp new file mode 100644 index 00000000..20a05445 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.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/chapter24/src/test/java/com/seaofnodes/simple/progs/person21.c b/chapter24/src/test/java/com/seaofnodes/simple/progs/person21.c new file mode 100644 index 00000000..df95e1ca --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/person21.c @@ -0,0 +1,34 @@ +#include <stdio.h> +#include <stdbool.h> +#include <stdlib.h> + +typedef struct Person { + int age; +} Person; + +typedef struct PersonArray { + unsigned int length; + int pad; + Person* data[]; +} PersonArray; + +__attribute__ ((CALL_CONV)) +extern void fcn(PersonArray* people, int index); + +int main() { + Person base[5] = {{25},{1},{18},{45},{60}}; + unsigned char buf[8+8*5]; + PersonArray* people_array = (PersonArray*)buf; + people_array->length=5; + for (int i=0; i<people_array->length; i++) people_array->data[i] = &base[i]; + + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + + printf("%d\n", people_array->data[1]->age); // expected: 6 + + return 0; +}
\ No newline at end of file diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/person21.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/person21.smp new file mode 100644 index 00000000..9f0f5bea --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/person21.smp @@ -0,0 +1,9 @@ +// -*-java-*- +struct Person { + int age; +}; + +val fcn = { Person?[] ps, int x -> + if( ps[x] ) + ps[x].age++; +};
\ No newline at end of file diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash.smp new file mode 100644 index 00000000..3fa2174c --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash.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/chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp new file mode 100644 index 00000000..dafa7456 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash21.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/BrainFuckTest.java b/chapter25/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index a42ebc24..f3da1592 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -77,7 +77,7 @@ val brain_fuck = { -> assertEquals(brain_fuck.length(),A5.ld4s(ptr_arm)); for( int i=0; i<brain_fuck.length(); i++ ) - assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr+4+i)); + assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr_arm+4+i)); } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 0abdfb3e..a94f36f2 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -12,6 +12,8 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter24Test { + @Test public void testColdLoopSelfConflict() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coldLoopSelfConflict(); } + @Test public void testPrintingDeadFunction() throws Exception { var code = new CodeGen("return 0;").parse(); var tfp = TypeFunPtr.TEST; 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 a92859d4..038d6882 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -209,6 +209,34 @@ public class RegAllocTestSupport { assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); } + public static void coldLoopSelfConflict() { + for( boolean phiConflict : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op init = new Op(A,null,null,false,code._start); + LoopNode loop = new LoopNode(null,null,code._start); + PhiNode phi = new PhiNode("loop",loop,init,null); + phi._type = TypeInteger.BOT; + Op back = new Op(A,A,null,false,loop,phi); + phi.setDef(2,back); + Op use = new Op(null,A,null,false,loop,phi); + loop.setDef(2,loop); + LRG lrg = alloc.newLRG(phi,null); + lrg._mask = A; + alloc.union(lrg,init); alloc.union(lrg,back); + lrg.selfConflict(back); + if( phiConflict ) lrg.selfConflict(phi); + assertTrue(alloc.splitSelfConflict((byte)0,lrg)); + assertSame(phi,use.in(1)); // First try leaves the hot definition alone. + assertSame(back,phi.in(2)); + if( phiConflict ) assertTrue(phi.in(1) instanceof SplitNode); + // Even if the first attempt made no graph change, retry must split. + assertTrue(alloc.splitSelfConflict((byte)1,lrg)); + assertTrue(phi.in(2) instanceof SplitNode); + if( phiConflict ) assertTrue(use.in(1) instanceof SplitNode); + } + } + public static void coalescing() { // Merge, incompatible masks, interference, capacity, and adjacency remapping. for( int kind=0; kind<5; kind++ ) { diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 94b9b1f3..7096156f 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -124,7 +124,7 @@ 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 23, with 24 next. | +| 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. | @@ -133,7 +133,7 @@ Chapter 25 suite, including `make -j 4 tests`. ## Register allocation: correctness first, staged improvements -Review on 2026-09-20. The staged plan follows; Chapters 20-23 +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, @@ -223,7 +223,7 @@ to add persistent deferral state to the first allocator chapter. 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-23 have now been implemented; stop for Cliff's review before 24. +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 @@ -269,6 +269,59 @@ 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 diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 24a57c02..4be72a96 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -155,9 +155,9 @@ lessons rather than duplicating that history. 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-23 are now implemented; common correctness + 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 24. Chapter 21's shortened README links the retained encoding reference. + Resume the quality/cohort/README review at 25. Chapter 21's shortened README links the retained encoding reference. - 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 @@ -176,6 +176,17 @@ lessons rather than duplicating that history. tests belong to 23. Grouping on/off gives identical 933 raw / 1,745 weighted moves here; report the zero gain rather than implying every heuristic helps this suite. The earlier-cohort increase includes changed optimizer behavior. +- Chapter 24 gives loop-Phi self-conflicts one cold-only splitting attempt; + remember Phi identity across rebuilt LRGs and force the ordinary fallback on + the next conflict. A backedge-only attempt can make no graph change and must + still consume that allowance. The same regression runs in 24 and 25. +- Chapter 24 preserves cohorts 20-23 and adds 67 allocations for cohort 24. + Distinguish moved inline sources from changed programs: keep the old 64-bit + Person and small emulator argument list, and attribute revised inputs to 24. + Cold-first splitting saves only 6 raw / 6 weighted moves here; the much larger + cross-chapter reduction includes optimizer changes. Its frozen String program + also found a lost null guard in the inlining dominator walk; keep that fix on + both sides when measuring the allocator heuristic. - 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 |
