From 1e527b16b28f31b08cbb36b7b1bf2d689487a989 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 20 Sep 2026 17:46:47 -0700 Subject: 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 --- chapter24/Makefile | 6 + chapter24/README.md | 75 ++++++- .../com/seaofnodes/simple/codegen/RegAlloc.java | 34 ++- .../com/seaofnodes/simple/node/CallEndNode.java | 5 +- .../java/com/seaofnodes/simple/BrainFuckTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 246 ++++++++++++++++----- .../com/seaofnodes/simple/Chapter21AllocTest.java | 55 +++++ .../java/com/seaofnodes/simple/Chapter21Test.java | 63 ++---- .../java/com/seaofnodes/simple/Chapter22Test.java | 36 ++- .../com/seaofnodes/simple/Chapter23AllocTest.java | 34 +++ .../java/com/seaofnodes/simple/Chapter23Test.java | 20 +- .../com/seaofnodes/simple/Chapter24AllocTest.java | 163 ++++++++++++++ .../java/com/seaofnodes/simple/Chapter24Test.java | 8 +- .../java/com/seaofnodes/simple/MergeSortTest.java | 2 +- .../java/com/seaofnodes/simple/SpillStats.java | 73 ++++++ .../test/java/com/seaofnodes/simple/TestArm64.java | 5 +- .../src/test/java/com/seaofnodes/simple/TestC.java | 6 +- .../test/java/com/seaofnodes/simple/TestRisc5.java | 6 +- .../simple/codegen/RegAllocTestSupport.java | 27 +++ .../java/com/seaofnodes/simple/progs/arg_count.smp | 6 + .../java/com/seaofnodes/simple/progs/array1.smp | 9 + .../test/java/com/seaofnodes/simple/progs/jig.smp | 16 ++ .../com/seaofnodes/simple/progs/newtonFloat.smp | 12 + .../seaofnodes/simple/progs/no_stack_arg_count.smp | 6 + .../java/com/seaofnodes/simple/progs/person21.c | 34 +++ .../java/com/seaofnodes/simple/progs/person21.smp | 9 + .../com/seaofnodes/simple/progs/stringHash.smp | 30 +++ .../com/seaofnodes/simple/progs/stringHash21.smp | 31 +++ .../java/com/seaofnodes/simple/BrainFuckTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter24Test.java | 2 + .../simple/codegen/RegAllocTestSupport.java | 28 +++ docs/chapter-backports.md | 59 ++++- skills/chapter25-codex-notes.md | 15 +- 33 files changed, 942 insertions(+), 183 deletions(-) create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/SpillStats.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/arg_count.smp create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/array1.smp create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/jig.smp create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/person21.c create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/person21.smp create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash.smp create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp 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 _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 _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 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 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 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 { 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 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<>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< + 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 _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>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 + 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 +#include +#include + +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; ilength; 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; i355 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 -- cgit v1.2.3