diff options
Diffstat (limited to 'chapter23')
23 files changed, 787 insertions, 175 deletions
diff --git a/chapter23/Makefile b/chapter23/Makefile index 55d5e70a..33855ddf 100644 --- a/chapter23/Makefile +++ b/chapter23/Makefile @@ -138,6 +138,12 @@ tests: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag @$(JVM) org.junit.runner.JUnitCore $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap +spill-stats: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag + @[ -d build/objs ] || mkdir -p build/objs + @$(JVM) com.seaofnodes.simple.SpillStats + +.PHONY: spill-stats + fuzzer: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag @echo "fuzzing " $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap diff --git a/chapter23/README.md b/chapter23/README.md index 545a4c4a..4a1118b5 100644 --- a/chapter23/README.md +++ b/chapter23/README.md @@ -1,6 +1,6 @@ # Chapter 23: Methods and Revisiting Types -In this chapter add *methods*, functions defined in structs which take a +In this chapter we add *methods*, functions defined in structs which take a hidden `self` argument and can access the struct fields. Here is an `indexOf` method in a String-like class: @@ -114,7 +114,7 @@ struct List { List *next; Object payload } No sharpening of `Object` to `int` nor `String` because every List object has a payload of `Object` and `Object` MEET `int` is back to `Object`. -It we allow truely cyclic types then in these kinds of places we can discover +If we allow truly cyclic types then in these kinds of places we can discover (or infer) a sharper type: `*List<int> { *List<int> next, int payload }` basically building up *generics* in the optimizer. This is not generics in the language nor type-variables per-se, but it goes a long way towards them. @@ -377,7 +377,7 @@ Type productions. In the end, the new `List` cyclic type is wholly interned - with a R/W version of `List#2` pointing back to the R/W `List#2` and the R/O version `List#12` -pointing back to the same R/W `List#12`. +pointing back to the same R/O `List#12`. @@ -427,33 +427,93 @@ implementation; they are not reified. struct vecInt { u32 !len; // Actual number of elements int[] !buf; // Array of integers. - + // Since "add" is declared with `val` in the original struct definition, // it is a final field and is moved out of here to the class. - - // Method: Add an element to a vector, possibly returning a new larger vector. - val add = { int e -> - if( len >= buf# ) _grow(buf#*2) - buf[len++] = e; - self; - }; - + // Method: Internal: copy buf to a new size - val _grow = { int sz -> - val buf2 = new int[sz]; + val _grow = { int sz -> + var buf2 = new int[sz]; for( int i=0; i<len; i++ ) buf2[i] = buf[i]; - free(buf); // Needs a better Mem Management solution + buf = buf2; + }; + + // Method: Add an element, growing the backing array when needed. + val add = { int e -> + if( len >= buf# ) _grow(buf#*2); + buf[len++] = e; + return self; }; -}; -val primes = new vecInt{}.add(2).add(3).add(5).add(7); +}; +val primes = new vecInt{buf = new int[4];}.add(2).add(3).add(5).add(7).add(11); ``` Here the `val add` field is a *value* field, a constant function value. It is moved out of the basic `vecInt` object into `vecInt`'s *class*, and takes no storage space in `vecInt` objects. The same happens for `_grow`. The size of -a `vecInt` is thus a `u32` word, a pointer to an `int[]` plus -`buf#*sizeof(int)`, plus any padding (probably none here). +a `vecInt` instance is thus its `u32` length and array pointer, plus alignment +padding. The array header and elements occupy a separate allocation. Reclaiming +the old buffer after growth is outside this example. Appending +`return primes.len*100+primes.buf[4];` produces 511 on both RISC-V and ARM. + +## RegAlloc improvements: grouping popular uses + +Chapter 22 improved color preferences and cheap-spill ordering. This chapter +adds a way to split a popular value whose uses demand incompatible registers. +For example, several shifts may need the same count register while another use +needs a different register. Sharing one copy for each compatible group can avoid +inserting a separate copy at every use. + +The allocator applies this to a single-definition live range with an empty +register mask and more than two fixed-register uses. It intersects overlapping +use masks into groups; narrowing a group keeps it compatible with its earlier +users, so one pass suffices. Disjoint masks start separate groups. It snapshots +distinct users before rewiring their inputs, ignores scheduling-only edges, +and counts a call once even when the value supplies several arguments. + +Grouping declines values used by multiple calls, whose register kills tend to +undo the benefit of a shared copy. The usual loop-boundary splitting remains +the fallback, including splitting an existing copy when all uses have the same +loop depth. Cold-first loop splitting is left for Chapter 24; area/cost spill +ranking remains for Chapter 25. + +Run `make spill-stats` in this directory. All rows below use **this chapter's +compiler**, seed 123, and frozen source/target combinations from each cohort. +The Windows run combines x86 SystemV/Win64 and RISC-V/ARM SystemV. Diagnostic +machine graphs are checked separately and do not contribute to the counts. + +| Program cohort | Compilations | Split/move count | Loop-weighted count | +|---|---:|---:|---:| +| Chapter 20 | 39 | 332 | 458 | +| Chapter 21 | 52 | 450 | 989 | +| Chapter 22 | 24 | 67 | 67 | +| Chapter 23 | 30 | 84 | 231 | +| **Total** | **145** | **933** | **1,745** | + +`_spills` counts retained SplitNodes, including register moves; `_spillScaled` +weights them by `8^loopDepth`. These estimate compiler-generated moves, not +runtime memory traffic. The reporter prints individual compilations and sums +by CPU/ABI, and still reports failure when a spill expectation or execution +check fails. + +With grouping disabled and everything else held fixed, this suite produces +**the same 933 moves / 1,745 weighted moves**. The original grouping code also +has those totals. This suite therefore shows no spill improvement from grouping; +the reduced machine-graph regression exercises its compatibility and call rules, +including a null-mask crash in the old implementation. A plausible allocator +heuristic needs measurements on workloads that reach it before claiming a win. + +For the older cohorts alone, Chapter 22's compiler produced 838 moves / 1,496 +weighted moves; this compiler produces 849 / 1,514. That comparison includes +changes outside allocation. In particular, Chapter 20's frozen String input +survives optimization here and costs 16 weighted moves; Chapter 22 eliminated +it at this seed. It would be misleading to attribute that difference to grouping. + +The original 64-bit `person21` and guarded `stringHash21` inputs preserve cohort +21. The revised String input and two encoding tests enabled in this chapter +belong to cohort 23. Keeping these cohorts fixed makes subsequent comparisons +meaningful even as the language and its tests grow. diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index adc198fc..11c9409d 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -289,75 +289,55 @@ public class RegAlloc { return true; } - // Single-def live range with an empty mask. There are many single-reg - // uses. Theory is there's many repeats of the same reg amongst the uses. - // In of splitting once per use, start by splitting into groups based on - // required input register. + // Popular single-def value: share a split among uses with compatible masks. boolean splitEmptyMaskByUse( byte round, LRG lrg ) { Node def = (Node)lrg._machDef; + // Snapshot distinct users: rewriting an input changes def's output list, + // and a call can use the same value in more than one argument. + Ary<Node> uses = new Ary<>(Node.class); + for( Node use : def._outputs ) + if( uses.find(use)==-1 ) uses.push(use); - // Look at each use, and break into non-overlapping register classes. Ary<RegMask> rclass = new Ary<>(RegMask.class); - boolean done=false; int ncalls=0; - while( !done ) { - done = true; - for( Node use : def._outputs ) - if( use instanceof MachNode mach ) { - if( mach instanceof CallNode ) ncalls++; - for( int i=1; i<use.nIns(); i++ ) - if( use.in(i)==def ) - done = putIntoRegClass( rclass, mach.regmap(i) ); - } - } - - // See how many register classes we split into. Generally not - // productive to split like this across calls, which are going to kill - // all registers anyways. - if( rclass._len <= 1 || ncalls > 1 ) return false; + for( Node use : uses ) + if( use instanceof MachNode mach ) { + // Sharing copies across several calls usually loses to their kills. + if( use instanceof CallNode && ++ncalls > 1 ) return false; + for( int i=1; i<use.nIns(); i++ ) + if( use.in(i)==def && mach.regmap(i)!=null ) + putIntoRegClass(rclass,mach.regmap(i)); + } + if( rclass._len <= 1 ) return false; - // Split by class - Ary<Node> ns = new Ary<>(Node.class); for( RegMask rmask : rclass ) { - ns.addAll(def._outputs); Node split = makeSplit(def,"popular",round,lrg,rmask); - split.insertAfter( def ); + split.insertAfter(def); if( split.nIns()>1 ) split.setDef(1,def); - // all uses by class to split - for( int j=0; j < def._outputs._len; j++ ) { - Node use = def._outputs.at(j); - if( use instanceof MachNode mach && use!=split ) { - // Check all use inputs for n, in case there's several - for( int i = 1; i < use.nIns(); i++ ) - // Find a def input, and check register class - if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) { - RegMask m = mach.regmap( i ); - if( m!=null && mach.regmap( i ).overlap( rmask ) ) - // Modify use to use the split version specialized to this rclass - { use.setDefOrdered( i, split ); j--; break; } + for( Node use : uses ) + if( use instanceof MachNode mach ) + for( int i=1; i<use.nIns(); i++ ) { + RegMask mask = mach.regmap(i); + if( use.in(i)==def && mask!=null && mask.overlap(rmask) ) { + assert rmask.and(mask)==rmask; + use.setDefOrdered(i,split); } - } - } - ns.clear(); + } } return true; } - - // Put use into a register class, perhaps adding a class or perhaps - // narrowing a class (and causing a repeat) - private static boolean putIntoRegClass( Ary<RegMask> rclass, RegMask rmask ) { + // Narrowing preserves all earlier users of a class; new classes are disjoint. + // Each use contains its first overlapping class, so one pass suffices. + private static void putIntoRegClass( Ary<RegMask> rclass, RegMask rmask ) { for( int i=0; i<rclass._len; i++ ) { RegMask omask = rclass.at(i); - if( omask.and(rmask) == omask ) return true; // Within the same register class - if( omask.overlap(rmask) ) { + if( !omask.overlap(rmask) ) continue; + if( omask.and(rmask)!=omask ) rclass.set(i,new RegMask(omask.copy().and(rmask))); - return false; // Need go again - } + return; } - // Add a new class, no need to go again rclass.push(rmask); - return true; } // Self conflicts require Phis (or two-address). diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java index 44a417f9..b9e85202 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java @@ -10,13 +10,12 @@ public class FunARM extends FunNode implements MachNode { FunARM(FunNode fun) { super(fun); } @Override public void computeFrameAdjust(CodeGen code, int maxReg) { super.computeFrameAdjust(code,maxReg); - if( _hasCalls ) // If non-leaf, pad to 16b - _frameAdjust = ((_frameAdjust+8) & -16); + _frameAdjust = (_frameAdjust+15) & -16; // Keep SP aligned, including leaf spills. } @Override public void encoding( Encoding enc ) { int sz = _frameAdjust; if( sz == 0 ) return; // Skip if no frame adjust if( sz >= 1L<<12 ) throw Utils.TODO(); - enc.add4(arm.imm_inst(arm.OPI_ADD, -sz&0xFFF, arm.RSP, arm.RSP)); + enc.add4(arm.imm_inst(arm.OPI_SUB, sz, arm.RSP, arm.RSP)); } } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java index 2136ebf5..4597666b 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java @@ -9,7 +9,7 @@ public class RetARM extends ReturnNode implements MachNode { @Override public void encoding( Encoding enc ) { int frameAdjust = ((FunARM)fun())._frameAdjust; if( frameAdjust > 0 ) - enc.add4(arm.imm_inst(arm.OPI_ADD, (frameAdjust*-8)&0xFFF, arm.RSP, arm.RSP)); + enc.add4(arm.imm_inst(arm.OPI_ADD, frameAdjust, arm.RSP, arm.RSP)); enc.add4(arm.ret(arm.OP_RET)); } } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 9dbf724d..716f7cb7 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -317,6 +317,11 @@ public class arm extends Machine { short self = enc.reg(n); short reg1 = enc.reg(n2); + // ADD/SUB encode an unsigned magnitude; switch operation for a negative addend. + if( imm12<0 && (opcode==OPI_ADD || opcode==OPI_SUB) ) { + opcode ^= OPI_ADD ^ OPI_SUB; + imm12 = -imm12; + } int body = imm_inst(opcode, imm12&0xFFF, reg1, self); enc.add4(body); } @@ -427,7 +432,7 @@ public class arm extends Machine { } public static int ret(int opcode) { - return (opcode << 10); + return (opcode << 10) | (X30 << 5); } // FMOV (scalar, immediate) diff --git a/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 1e1a1dc3..bf809d2a 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -32,7 +32,7 @@ public class BrainFuckTest { 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/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 15addc7b..70ddd435 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -5,9 +5,6 @@ import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; -import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; import org.junit.Assert; import org.junit.Ignore; import org.junit.Test; @@ -31,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(); } @@ -52,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 @@ -95,56 +96,109 @@ 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 { - 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);"; - testCPU(src,"x86_64_v2", "SystemV",39,null); - testCPU(src,"riscv" , "SystemV",17,null); - testCPU(src,"arm" , "SystemV",18,null); + public void testNewtonFloat() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { flt x -> + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +flt farg = arg; +return sqrt(farg) + sqrt(farg+2.0); +"""; + 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 { - String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/array1.smp")); - 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));"); + public void testArray1() { + String src = +""" +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 +"""; + 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 = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); - testCPU(src,"x86_64_v2", "SystemV", 9,null); - testCPU(src,"riscv" , "SystemV", 3,null); - testCPU(src,"arm" , "SystemV", 3,null); + public void testString() { + String src = """ +struct String { + u8[] cs; + int _hashCode; +}; + +val equals = { String self, String s -> + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + if( self.cs ) { + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + } + if( !hash ) hash = 123456789; + return hash; +}; + +String !s = new String { cs = new u8[17]; }; +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s); +"""; + 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 @@ -162,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 @@ -177,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/chapter23/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java new file mode 100644 index 00000000..2d0493e5 --- /dev/null +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 9e73a9c0..f84a7237 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -13,6 +13,118 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testArmCallInstructions() { + EvalArm64 cpu = new EvalArm64(new byte[512],256); + for( int delta : new int[]{4,32,-4} ) { + cpu._pc = 128; + for( int i=0; i<32; i++ ) cpu.regs[i]=1000+i; + cpu.st4(128,0x94000000 | ((delta>>2)&0x03FFFFFF)); // BL + assertEquals(0,cpu.step(1)); + assertEquals(128+delta,cpu._pc); + for( int i=0; i<32; i++ ) assertEquals(i==30 ? 132 : 1000+i,cpu.regs[i]); + } + for( int rn : new int[]{9,30} ) + for( boolean call : new boolean[]{false,true} ) { + cpu._pc=4; + cpu.regs[rn]=64; + cpu.st4(4,(call ? 0xD63F0000 : 0xD65F0000) | (rn<<5)); // BLR / RET + assertEquals(0,cpu.step(1)); + assertEquals(64,cpu._pc); + if( call ) assertEquals(8,cpu.regs[30]); + } + } + + @Test public void testArmImmediateArithmetic() { + EvalArm64 cpu = new EvalArm64(new byte[16],16); + // Unsigned imm12, including bit 11 and the optional 12-bit shift. + for( int[] test : new int[][]{{0x91200020,2148},{0xD1200020,-1948}, + {0x91400420,4196},{0xD1400420,-3996}} ) { + cpu._pc=0; cpu.regs[1]=100; + cpu.N=true; cpu.Z=false; cpu.C=true; cpu.V=true; + cpu.st4(0,test[0]); + assertEquals(0,cpu.step(1)); + assertEquals(test[1],cpu.regs[0]); + assertTrue(cpu.N); assertFalse(cpu.Z); assertTrue(cpu.C); assertTrue(cpu.V); + } + } + + @Test public void testArmCallsAndFrames() throws IOException { + String src = """ + val sum = { int n -> + if( n<=0 ) return 1; + return sum(n-1)+n; + }; + val run = { int n -> return sum(n)+sum(n+1); }; + """; + assertTrue("Ordinary calls must survive optimization",checkArmCalls(src,"run",4,27)>0); + } + + @Test public void testArmVectorGrowth() throws IOException { + String src = """ + struct _Vec { + u32 !len; + int[] !buf; + val grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i<len; i++ ) buf2[i]=buf[i]; + buf=buf2; + }; + val add = { int e -> + if( len>=buf# ) grow(buf#*2); + buf[len++]=e; + return self; + }; + }; + val run = { int arg -> + val v = new _Vec{buf=new int[4];}.add(2).add(3).add(5).add(7).add(11); + return v.len*100+v.buf[arg]; + }; + """; + checkArmCalls(src,"run",4,511); + } + + private static int checkArmCalls(String src, String entryName, int arg, int result) throws IOException { + CodeGen code = new CodeGen(src).driver("arm","SystemV",null); + byte[] image = new byte[1<<20]; + System.arraycopy(code._encoding.bits(),0,image,0,code._encoding.bits().length); + EvalArm64 cpu = new EvalArm64(image,1<<16); + boolean entry=false; + int frames=0, calls=0; + for( var bb : code._cfg ) { + if( bb instanceof com.seaofnodes.simple.node.FunNode fun ) { + int off = code._encoding._opStart[fun._nid]; + if( entryName.equals(fun._name) ) { cpu._pc=off; entry=true; } + int frame=fun._frameAdjust; + assertEquals(0,frame&15); + if( frame>0 ) { + frames++; + assertEquals(0xD10003FF | (frame<<10),cpu.ld4s(off)); // SUB SP,SP,#bytes + } + } + if( bb instanceof com.seaofnodes.simple.node.ReturnNode ret ) { + int off=code._encoding._opStart[ret._nid]; + int frame=ret.fun()._frameAdjust; + if( frame>0 ) { + assertEquals(0x910003FF | (frame<<10),cpu.ld4s(off)); // ADD SP,SP,#bytes + off+=4; + } + assertEquals(0xD65F03C0,cpu.ld4s(off)); // RET X30 + } + if( bb instanceof com.seaofnodes.simple.node.cpus.arm.CallARM ) calls++; + } + assertTrue("Must execute the program entry",entry); + assertTrue("Exercise stack frames",frames>0); + for( int i=19; i<=29; i++ ) cpu.regs[i]=1000+i; + cpu.regs[0]=arg; + assertEquals(0,cpu.step(10000)); + assertEquals("Must return to the harness",0,cpu._pc); + assertEquals(result,cpu.regs[0]); + assertEquals(1<<16,cpu.regs[31]); + for( int i=19; i<=29; i++ ) assertEquals(1000+i,cpu.regs[i]); + return calls; + } + + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } @Test public void testNarrowStores() throws IOException { @@ -104,7 +216,8 @@ public class Chapter21Test { } - @Test + // Enabled in Chapter 23; measured there by Chapter23AllocTest. + @Test @Ignore public void testJig() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); testCPU(src,"x86_64_v2", "Win64" ,-1,null); @@ -114,10 +227,8 @@ public class Chapter21Test { 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()); } @@ -131,7 +242,7 @@ public class Chapter21Test { } @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;"); @@ -258,7 +369,7 @@ public class Chapter21Test { @Test public void testPerson() throws IOException { String person = "6\n"; - TestC.run("person", person, 0); + TestC.run("person21", person, 0); // Memory layout starting at PS: int ps = 1<<16; // Person array pointer starts at heap start @@ -269,7 +380,7 @@ public class Chapter21Test { int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; - EvalRisc5 R5 = TestRisc5.build("person", 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); @@ -285,7 +396,7 @@ public class Chapter21Test { assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); - EvalArm64 A5 = TestArm64.build("person", 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); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java index d6f31ff6..a3e9a016 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -13,8 +13,15 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter22Test { + @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;"); + } - @Test + // Enabled in Chapter 23; measured there by Chapter23AllocTest. + @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")); @@ -25,10 +32,8 @@ public class Chapter22Test { 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/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java new file mode 100644 index 00000000..cd8c43cf --- /dev/null +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 4bb8ded0..41f0df6e 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -16,6 +16,8 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter23Test { + @Test public void testPopularUses() { com.seaofnodes.simple.codegen.RegAllocTestSupport.popularUses(); } + @Test public void testDiagnosticTypeAccessors() throws Exception { new CodeGen("return 0;").parse(); var tfp = TypeFunPtr.TEST; @@ -62,7 +64,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()); @@ -93,10 +96,8 @@ var apply = { i64 x, { i64 -> u32 } fcn -> 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/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java index 5a40de8f..54d08e19 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -307,11 +307,11 @@ public class EvalArm64 { break; } - case 0x91: { // add(immediate) + case 0x91, 0xD1: { // ADD/SUB (immediate), unsigned imm12, optional LSL #12 int rn = (ir >> 5) & 0x1F; - int immediate = ir << 10 >> 20; - // only hit it twice - rval = regs[rn] + immediate; + long immediate = (ir >>> 10) & 0xFFF; + if( (ir & (1<<22))!=0 ) immediate <<= 12; + rval = opcode1==0x91 ? regs[rn] + immediate : regs[rn] - immediate; break; } case 0x92: { // and(immediate) @@ -330,6 +330,7 @@ public class EvalArm64 { } case 0x94, 0x95, 0x96, 0x97: { // bl + rdid = -1; // BL writes only X30, not a displacement-selected register. rval = pc + 4; regs[arm.X30] = rval; int imm26 = (ir & 0x03FFFFFF); @@ -573,15 +574,15 @@ public class EvalArm64 { break; } case 0xD6: { - if( (ir & 0xFFFF) != 0 ) throw Utils.TODO(); - if( ((ir>>16) & 0xFF) != 0x5F ) throw Utils.TODO(); // 0x3F is register call + int op = ir & 0xFFFFFC1F; + int rn = (ir >>> 5) & 31; + int target = (int)regs[rn]; // Read before BLR overwrites X30. rdid = -1; - int rn = ir << 22 >> 27; - assert rn == 0; - pc = (int)regs[30]; - // Return to zero breaks simulation - if( pc==0 ) break outer; - pc -= 4; // Undo post-increment + if( op==0xD63F0000 ) regs[arm.X30] = pc+4; // BLR + else if( op!=0xD65F0000 ) { trap = 3; break; } // RET + pc = target; + if( op==0xD65F0000 && pc==0 ) break outer; + pc -= 4; break; } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java index 65eb525c..d1fbd7df 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.cpus.riscv.riscv; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.node.cpus.riscv.riscv; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; @@ -18,7 +18,7 @@ public class MergeSortTest { for( int prime : primes ) sb.p(prime).p(", "); String sprimes = sb.p("]").toString(); - TestC.run("sort", sprimes, 40); + TestC.run("sort", sprimes, 34); EvalRisc5 R5 = TestRisc5.build("src/test/java/com/seaofnodes/simple/progs", "sort", "merge_sort", 0, 36, false); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/SpillStats.java b/chapter23/src/test/java/com/seaofnodes/simple/SpillStats.java new file mode 100644 index 00000000..6af51b33 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -0,0 +1,72 @@ +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()==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","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/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java index 38fd2a85..edce92f3 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -24,12 +24,11 @@ public class TestArm64 { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); 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/chapter23/src/test/java/com/seaofnodes/simple/TestC.java b/chapter23/src/test/java/com/seaofnodes/simple/TestC.java index 6edde562..2e61211a 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestC.java @@ -60,15 +60,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/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java index cb1c95e9..adb256eb 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -22,13 +22,11 @@ public abstract class TestRisc5 { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); 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/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index b2d14a02..ec666653 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -105,6 +105,48 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,new RegAlloc(code))); } + private static class CallOp extends CallNode implements MachNode { + CallOp(Node ctrl, Node def) { super(null,ctrl,null,def,def); } + @Override public RegMask regmap(int i) { return i==2 ? A : i==3 ? B : null; } + @Override public RegMask outregmap() { return null; } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + + public static void popularUses() { + for( int calls=0; calls<=2; calls++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + RegionNode block = new RegionNode(null,code._start,code._start); + Op def = new Op(new RegMask(7L),null,null,false,block); + LRG lrg = alloc.newLRG(def); + lrg._machDef = def; + lrg._mask = new RegMask(0L); + Op ab = new Op(null,new RegMask(3L),null,false,block,def); + Op bc = new Op(null,new RegMask(6L),null,false,block,def); + Op a = new Op(null,A,null,false,block,def,def); + Op b = new Op(null,B,null,false,block,def); + Op dep = new Op(null,null,null,false,block,def); + CallOp call = calls>0 ? new CallOp(block,def) : null; + if( calls==2 ) new CallOp(block,def); + boolean split = alloc.splitEmptyMaskByUse((byte)0,lrg); + assertEquals(calls<2,split); + if( !split ) { assertSame(def,a.in(1)); assertSame(def,b.in(1)); continue; } + // Two shared copies, even with overlapping masks and repeated inputs. + assertTrue(a.in(1) instanceof SplitNode); + assertTrue(b.in(1) instanceof SplitNode); + assertNotSame(a.in(1),b.in(1)); + assertSame(a.in(1),a.in(2)); + assertSame(b.in(1),ab.in(1)); + assertSame(b.in(1),bc.in(1)); + assertSame(def,dep.in(1)); // A scheduling dependency has no register. + assertEquals(3,def.nOuts()); // Two copies and the dependency. + if( call!=null ) { + assertSame(a.in(1),call.in(2)); + assertSame(b.in(1),call.in(3)); + } + } + } + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. public static class CheckedCodeGen extends CodeGen { public CheckedCodeGen(String src) { super(src); } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.c b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.c new file mode 100644 index 00000000..df95e1ca --- /dev/null +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp new file mode 100644 index 00000000..9f0f5bea --- /dev/null +++ b/chapter23/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/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp new file mode 100644 index 00000000..dafa7456 --- /dev/null +++ b/chapter23/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; +}; |