diff options
Diffstat (limited to 'chapter20')
11 files changed, 365 insertions, 105 deletions
diff --git a/chapter20/Makefile b/chapter20/Makefile index c5d8fa71..9e33ae91 100644 --- a/chapter20/Makefile +++ b/chapter20/Makefile @@ -71,6 +71,10 @@ tests: $(default_targets) @$(JVM) org.junit.runner.JUnitCore $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap +# Report measured spill totals while retaining the tests' assertions. +spill-stats: $(default_targets) + @$(JVM) com.seaofnodes.simple.SpillStats + fuzzer: $(default_targets) @echo "fuzzing " $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap @@ -89,7 +93,7 @@ view: $(main_classes) @echo "viewing " @$(JVM) com.seaofnodes.simple.print.JSViewer -.PHONY: clean +.PHONY: clean spill-stats clean: rm -rf build rm -f TAGS diff --git a/chapter20/README.md b/chapter20/README.md index ab1d9ca4..e050a812 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -34,6 +34,9 @@ bugs linger until we can actually run the code. This means that other chapters have updates and bug-fixes to the work being described here. +Specific to the register allocator, we will be gradually adding improvements to +it, chapter by chapter for quite a few chapters. Register allocators generally +end with a large number of heuristics which we will add slowly. You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter19...linear-chapter20) it to the previous chapter. @@ -218,11 +221,7 @@ The rest of the fields are dedicated to various spilling heuristics: - `_1regDefCnt` `_1regUseCnt` - Count of defs and uses which are pinned to a single register. These typically require a hard-split just before (use) or after (def) to free up the register choices. -- `_killed` - LRG lost all registers due to an op killing its available - registers; commonly happens to LRGs which span a `Call` and generally - requires splitting some callee-save live range (spilling a callee-save - register) and move the LRG into the now available register. - + ## Live Ranges and Conflicts @@ -400,7 +399,8 @@ This set of splits is fairly aggressive... but test cases requiring a split in each of the listed locations are including in Chapter 20's test cases. We cannot even attempt a color while we have self conflicts, so its important to break up these live ranges quickly. This tends to over-split and the allocator -leans on Biased Coloring and Coalescing to remove some of the extras. +leans on Biased Coloring and the final copy cleanup to remove some of the +extras. Conservative coalescing will be introduced in a later chapter. ### Split Hard Conflict @@ -414,12 +414,15 @@ For simple hard-conflicts (a single def and single use), we have the exact def and use kept in the Live Range itself. We split once after the def and once before the use (and only on sides with restricted registers). -Another common case is popular constants (e.g. 0): a single def with many uses, -and some of the uses require certain registers. Instead of splitting the -popular constant everywhere, we first split it into "register classes" and see -if we can remove the hard conflict with fewer spills. - For more complex cases we use the capacity spilling/loop-nest technique. +Cloneable values can be recreated near their uses, but only when the clone's +output register class can satisfy that use. Otherwise we need a move. A fixed +register constant with flexible uses must also split at its uses; doing nothing +at its definition would repeat the same hard conflict forever. + +Popular constants (e.g. 0) often have many uses requiring different registers. +Grouping these uses into register classes can save moves, but we defer that +heuristic to a later chapter. ### Split By Loop Nest @@ -468,4 +471,60 @@ useless splits (and track the rest for "scoring" our allocation). We'll also bypass some split-after-splits, which can remove some redundant copying. The registers remain available in the `RegAlloc` object via `alloc.regnum( Node n )` -and will be used by a following instruction encoding pass.
\ No newline at end of file +and will be used by a following instruction encoding pass. + + +## RegAlloc improvements: correctness and a measured baseline + +This chapter starts with a small allocator. Hard conflicts must actually be +broken: a split cannot be skipped just because another copy is in the same +block, nor folded away when that would restore the conflict. Loop backedges +need the same care, especially when Phis represent parallel assignments. +Register kills apply even to instructions with no output value. Finally, +removing a redundant copy requires a backward scan for intervening definitions +and register kills. These are correctness rules, independent of spill quality. + +We sort failed live ranges before splitting so changes in identity-map order do +not decide the allocation. The allocator also has null-safe split printing and +an optional function-local-edge diagnostic. The tests check register masks, +two-address operands, and Phi register agreement; tiny machine graphs exercise +hard conflicts independently of optimizer choices. Native execution comes with +encoding in Chapter 21. + +### Spill-count summed across tests + +Run `make spill-stats` to execute the tests and print each compilation's counts, +CPU/ABI subtotals, and the total below. Assertions remain enabled, and a failing +test makes the command fail. The optimizer's default seed is 123. + +The Chapter 20 program cohort is all 11 source examples in `Chapter20Test`, plus +`BrainFuckTest.testBrainfuck` and `MergeSortTest.testMergeSort`, on x86-64, +RISC-V, and ARM using SystemV: 13 programs and 39 compilations, including the +zero-spill cases. The synthetic allocator regression graphs are correctness +checks, not additional program benchmarks. + +| Program-test cohort | Allocator chapter | Compilations | Split moves | Loop-weighted moves | +|---|---:|---:|---:|---:| +| Chapter 20 | 20 | 39 | 236 | 355 | + +`_spills` counts surviving split moves, including register-to-register copies; +it does not count only stack stores. `_spillScaled` weights each move by +`8^loopDepth`, a rough cost estimate rather than measured execution frequency. +The weighted subtotals are 152 for x86-64, 101 for RISC-V, and 102 for ARM. + +### Comments on the measurements + +Before the correctness fixes, this same cohort had 235 moves and a weighted +count of 354. The corrected baseline is one higher in each measure: x86-64's +weighted count rises by two, ARM's by one, while RISC-V's falls by two. This is +a small correctness cost, not a claimed quality improvement. Individual cases +move more: the x86 array example rises from three to five, while its integer +Newton example stays at 23. Looking at just one example would be misleading. + +Later chapters will add one quality technique at a time and end with this kind +of table: Chapter 21 will measure both the Chapter 20 and Chapter 21 program +cohorts using its allocator, and Chapter 25 will have rows for cohorts 20-25. +Keep the program/target membership and seeds fixed when comparing a row between +chapters, and separate changes in the optimizer or instruction selection from +changes in allocation. A local regression may be worthwhile when the total +improves; an allocation failure or illegal register assignment never is. diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index 88b49863..2bd64c50 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -41,8 +41,8 @@ abstract public class BuildLRG { int uidx = n.out(0)._inputs.find(n); RegMask mask1 = n.in (1) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(1))._mask; RegMask mask2 = n.in (2) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(2))._mask; - RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): alloc.lrg(n )._mask; - if( !mask1.overlap(masko) && mask2.overlap(masko) ) + RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): mach.outregmap(); + if( masko!=null && !mask1.overlap(masko) && mask2.overlap(masko) ) n.swap12(); } @@ -56,7 +56,7 @@ abstract public class BuildLRG { LRG lrg2 = alloc.lrg(n.in(i)); if( lrg2 != null ) { // Anti-dep or other, no LRG RegMask use_mask = mach.regmap(i); - if( !lrg2.machUse(mach,(short)i,use_mask.size1()).and(use_mask) ) + if( use_mask!=null && !lrg2.machUse(mach,(short)i,use_mask.size1()).and(use_mask) ) alloc.fail(lrg2); // Empty register mask, must split } } @@ -64,7 +64,7 @@ abstract public class BuildLRG { } // MultiNodes have projections which set registers - if( n instanceof MultiNode ) + if( n instanceof MultiNode && !(n instanceof CFGNode) ) for( Node proj : n.outs() ) if( proj instanceof MachNode ) defLRG(alloc,proj); diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 1f3186ff..acfec53f 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -127,16 +127,11 @@ abstract public class IFG { if( n instanceof PhiNode ) return; - // A copy does not define a new value, and the src and dst can use the - // same register. Remove the input from TMP/liveout set before - // interfering. - //if( n instanceof MachNode m && m.isSplit() ) - // TMP.remove(alloc.lrg(n.in(1))); // Kill spill-use + // Instructions can clobber registers without defining an LRG. + if( n instanceof MachNode m ) kills(alloc,m); // Interfere n with all live if( lrg!=null ) { - if( n instanceof MachNode m ) - kills(alloc,m); // Interfere n with all live for( LRG tlrg : TMP.keySet() ) { assert tlrg.leader(); @@ -148,9 +143,9 @@ abstract public class IFG { // last tlrg register at some point, either tlrg or lrg // must fail. If *n* (a subset of lrg) needs the single // last tlrg register then only tlrg must fail. - if( lrg.size1() && !tlrg.clr(lrg._mask.firstReg()) ) - alloc.fail(tlrg); - else addIFG(lrg,tlrg); // Add interference + if( ((MachNode)n).outregmap().size1() ) { + if( !tlrg.clr(lrg._mask.firstReg()) ) alloc.fail(tlrg); + } else addIFG(lrg,tlrg); // Add interference } } @@ -171,7 +166,7 @@ abstract public class IFG { // Look for a must-use single register conflicting with some other must-def. if( n instanceof MachNode m ) { RegMask ni_mask = m.regmap(i); - if( ni_mask.size1() ) { // Must-use single register + if( ni_mask!=null && ni_mask.size1() ) { // Must-use single register // Search all current live for( LRG tlrg : TMP.keySet() ) { assert tlrg.leader(); @@ -204,15 +199,7 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - // Disallow clone-ables from killing registers. Just fail - // them and re-clone closer to target... so no kill. - // Special case for Intel XOR used to zero. - if( m.isClone() ) - alloc.fail(alloc.lrg((Node)m)); - else if( !tlrg.sub(killMask) ) { - tlrg._killed = true; // Failed by a kill-mask - alloc.fail(tlrg); - } + if( !tlrg.sub(killMask) ) alloc.fail(tlrg); } } } @@ -234,7 +221,7 @@ abstract public class IFG { private static void mergeLiveOut( RegAlloc alloc, CFGNode priorbb, int i ) { CFGNode bb = priorbb.cfg(i); if( bb == null ) return; // Start has no prior - if( !bb.blockHead() ) bb = bb.cfg0(); + while( !bb.blockHead() ) bb = bb.cfg0(); //if( i==0 && !(bb instanceof StartNode) ) bb = bb.cfg0(); assert bb.blockHead(); diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java index 394c4a01..5803cad8 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java @@ -42,11 +42,6 @@ public class LRG { public MachNode _machDef, _machUse; short _uidx; // _machUse input - // Mask set to empty via a kill-mask. This is usually a capacity kill, - // which means we need to split and spill into memory - which means even if - // the def-side has many registers, it MUST spill. - boolean _killed; - // Some splits used in biased coloring MachConcreteNode _splitDef, _splitUse; @@ -130,9 +125,12 @@ public class LRG { if( _machUse==null ) { _machUse = lrg._machUse; + _uidx = lrg._uidx; } else if( lrg._machUse!=null ) { - if( _1regUseCnt==0 ) + if( _1regUseCnt==0 ) { _machUse = lrg._machUse; + _uidx = lrg._uidx; + } else if( _machUse==lrg._machUse ) _1regUseCnt--; } @@ -143,7 +141,8 @@ public class LRG { _splitUse = deepSplit(_splitUse,lrg._splitUse); // Fold together masks - _mask = _mask.and(lrg._mask); + RegMask mask = _mask.and(lrg._mask); + _mask = mask==null ? _mask.copy().and(lrg._mask) : mask; return this; } diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index f28805b5..5227c11e 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -28,7 +28,7 @@ public class RegMask { public RegMask(int bit) { if( bit < 64 ) _bits0 = 1L<<bit; - else _bits1 = 1L<<(bit=64); + else _bits1 = 1L<<(bit-64); } public RegMask(long bits ) { _bits0 = bits; } public RegMask(long bits0, long bits1 ) { _bits0 = bits0; _bits1 = bits1; } @@ -65,21 +65,18 @@ public class RegMask { public short firstReg() { + if( isEmpty() ) return -1; return (short)(_bits0 != 0 ? Long.numberOfTrailingZeros(_bits0) : Long.numberOfTrailingZeros(_bits1)+64); } public short nextReg(short reg) { - if( reg<64 ) { - long bits0 = _bits0 >> (reg+1); - if( bits0!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits0)); - reg=64; + if( reg < 63 ) { + long bits0 = _bits0 & (-1L << (reg+1)); + if( bits0!=0 ) return (short)Long.numberOfTrailingZeros(bits0); } - long bits1 = _bits1 >> (reg-64+1); - if( bits1!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits1)); - return -1; + long bits1 = reg < 64 ? _bits1 : reg < 127 ? _bits1 & (-1L << (reg-63)) : 0; + return bits1==0 ? -1 : (short)(64+Long.numberOfTrailingZeros(bits1)); } boolean isEmpty() { return _bits0==0 && _bits1==0; } @@ -96,8 +93,8 @@ public class RegMask { // Has exactly 1 bit set public boolean size1() { - return ((_bits0 & -_bits0)==_bits0 && _bits1==0) || - ((_bits1 & -_bits1)==_bits1 && _bits0==0); + return !isEmpty() && (((_bits0 & -_bits0)==_bits0 && _bits1==0) || + ((_bits1 & -_bits1)==_bits1 && _bits0==0)); } // Cardinality diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java index 55ffe378..f7cb1672 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java @@ -297,9 +297,8 @@ public abstract class Node implements Cloneable { kill(); } - // Replace uses of `def` with `this`, and insert `this` immediately after - // `def` in the basic block. - public void insertAfter( Node def, boolean must ) { + // insert `this` immediately after `def` in the same basic block. + public void insertAfter( Node def ) { CFGNode cfg = def.cfg0(); int i = cfg._outputs.find(def)+1; if( cfg instanceof CallEndNode ) { @@ -312,19 +311,6 @@ public abstract class Node implements Cloneable { while( cfg.out(i) instanceof PhiNode || cfg.out(i) instanceof CalleeSaveNode ) i++; cfg._outputs.insert(this,i); _inputs.set(0,cfg); - for( int j=def.nOuts()-1; j>=0; j-- ) { - // Can we avoid a split of a split? 'this' split is used by - // another split in the same block. - if( !must && def.out(j) instanceof SplitNode split && def.out(j).cfg0()==cfg && - !split._kind.contains("self") ) - continue; - Node use = def._outputs.del(j); - use.unlock(); - int idx = use._inputs.find(def); - use._inputs.set(idx,this); - addUse(use); - } - if( nIns()>1 ) setDef(1,def); } // Insert this in front of use.in(uidx) with this, and insert this @@ -358,6 +344,13 @@ public abstract class Node implements Cloneable { setDef(idx,def); } + public void killOrdered() { + CFGNode cfg = cfg0(); + cfg._outputs.remove(cfg._outputs.find(this)); + _inputs.set(0,null); + kill(); + } + public void removeSplit() { CFGNode cfg = cfg0(); cfg._outputs.remove(cfg._outputs.find(this)); diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java index 22cb9bb9..37d1a63d 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java @@ -11,7 +11,10 @@ public abstract class SplitNode extends MachConcreteNode { public SplitNode(String kind, byte round, Node[] nodes) { super(nodes); _kind = kind; _round = round; } @Override public String op() { return "mov"; } @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { - return in(1)._print0(sb.append("mov("),visited).append(")"); + sb.append("mov("); + if( in(1)==null ) sb.append("---"); + else in(1)._print0(sb,visited); + return sb.append(")"); } @Override public Type compute() { return in(0)._type; } @Override public Node idealize() { return null; } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 0657e9ad..8e9b0272 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -10,6 +10,15 @@ import static com.seaofnodes.simple.Main.PORTS; import static org.junit.Assert.*; public class Chapter20Test { + @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(); } + @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } + @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } + @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } + @Test public void testPrintingRegisters() throws Exception { com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); } @@ -23,20 +32,24 @@ public class Chapter20Test { 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 CodeGen(src); code.parse().opto().typeCheck().instSelect(PORTS,cpu,os).GCM().localSched().regAlloc().encode(); - int delta = spills>>3; - if( delta==0 ) delta = 1; - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); - if( stop != null ) - assertEquals(stop, code._stop.toString()); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + SpillStats.record(code,"Chapter20",cpu,os); + assertEquals("Expect spills: "+cpu,spills,code._regAlloc._spillScaled,Math.max(1,spills>>3)); + 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() { @@ -45,9 +58,9 @@ public class Chapter20Test { @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 @@ -65,9 +78,9 @@ val sqrt = { int x -> }; return sqrt(arg) + sqrt(arg+2); """; - testCPU(src,"x86_64_v2", "SystemV",26,null); - testCPU(src,"riscv" , "SystemV",19,null); - testCPU(src,"arm" , "SystemV",26,null); + testTarget(src,"x86_64_v2", "SystemV",26,null); + testTarget(src,"riscv" , "SystemV",19,null); + testTarget(src,"arm" , "SystemV",26,null); } @Test @@ -86,9 +99,9 @@ val sqrt = { flt x -> flt farg = arg; return sqrt(farg) + sqrt(farg+2.0); """; - testCPU(src,"x86_64_v2", "SystemV",25,null); - testCPU(src,"riscv" , "SystemV",21,null); - testCPU(src,"arm" , "SystemV",18,null); + testTarget(src,"x86_64_v2", "SystemV",25,null); + testTarget(src,"riscv" , "SystemV",21,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test @@ -110,9 +123,9 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; - testCPU(src,"x86_64_v2", "SystemV",3,"return .[];"); - testCPU(src,"riscv" , "SystemV",1,"return (add,.[],(mul,.[],1000));"); - testCPU(src,"arm" , "SystemV",1,"return (add,.[],(muli,.[]));"); + testTarget(src,"x86_64_v2", "SystemV",5,"return .[];"); + testTarget(src,"riscv" , "SystemV",1,"return (add,.[],(mul,.[],1000));"); + testTarget(src,"arm" , "SystemV",1,"return (add,.[],(muli,.[]));"); } @Test @@ -153,9 +166,9 @@ s.cs[0] = 67; // C s.cs[1] = 108; // l hashCode(s); """; - testCPU(src,"x86_64_v2", "SystemV",18,null); - testCPU(src,"riscv" , "SystemV", 3,null); - testCPU(src,"arm" , "SystemV", 3,null); + testTarget(src,"x86_64_v2", "SystemV",21,null); + testTarget(src,"riscv" , "SystemV", 3,null); + testTarget(src,"arm" , "SystemV", 5,null); } @Test @@ -179,9 +192,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 @@ -194,8 +207,8 @@ 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); } } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/SpillStats.java b/chapter20/src/test/java/com/seaofnodes/simple/SpillStats.java new file mode 100644 index 00000000..9b03da7b --- /dev/null +++ b/chapter20/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -0,0 +1,48 @@ +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 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); + } + + public static void main(String[] args) throws ClassNotFoundException { + if( args.length==0 ) args = new String[]{"Chapter20Test","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); + if( !result.wasSuccessful() ) System.out.println("FAILED test run: totals are not a complete comparison."); + 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()); + ACTIVE = null; + if( !result.wasSuccessful() ) System.exit(1); + } +} diff --git a/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..bb1d49bf --- /dev/null +++ b/chapter20/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,157 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; +import static org.junit.Assert.*; + +// Small scheduled machine graphs isolate register constraints from peepholes. +public class RegAllocTestSupport { + private static final RegMask A = new RegMask(0), B = new RegMask(1); + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + final boolean _clone; + Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT; + } + @Override public String op() { return "testOp"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @Override public RegMask killmap() { return _kill; } + @Override public boolean isClone() { return _clone; } + @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); } + @Override public int encoding(ByteArrayOutputStream bytes) { throw new AssertionError(); } + } + private static CodeGen graph() { + CodeGen code = new CodeGen(""); + code._mach = new x86_64_v2(); + code._cfg.add(code._start); + return code; + } + + public static void masks() { + for( int reg : new int[]{0,63,64,65,127} ) { + RegMask mask = new RegMask(reg); + assertEquals(reg,mask.firstReg()); + assertEquals(1,mask.size()); + } + assertEquals(-1,new RegMask(0L).firstReg()); + assertFalse(new RegMask(0L).size1()); + RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1); + assertEquals(64,boundary.nextReg((short)63)); + assertEquals(127,boundary.nextReg((short)64)); + assertEquals(-1,boundary.nextReg((short)127)); + } + + public static void union() { + CodeGen code = graph(); + Op use = new Op(null,B,null,false,code._start); + LRG a = new LRG((short)1), b = new LRG((short)2); + a._mask = new RegMask(3L); + b._mask = new RegMask(6L); + b.machUse(use,(short)2,true); + LRG both = a.union(b); + assertNotNull(both._mask); + assertEquals(1,both._mask.firstReg()); + assertEquals(1,both._mask.size()); + assertSame(use,both._machUse); + assertEquals(2,both._uidx); + } + + public static void killWithoutResult() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,A,false,code._start); // Clobbers A, produces no value. + new Op(null,A,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + } + + public static void nullUseMask() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,null,false,code._start,def); // Scheduling dependency only. + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertTrue(IFG.build(0,alloc)); + } + + public static void cloneRegisterClass() { + for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) { + CodeGen code = graph(); + Op def = new Op(A,null,null,true,code._start); + Op use = new Op(null,required,null,false,code._start,def); + Op use2 = new Op(null,required,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses. + assertEquals(0,alloc.regnum(def)); + assertTrue(required.test(alloc.regnum(use.in(1)))); + assertTrue(required.test(alloc.regnum(use2.in(1)))); + assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void commutativePhi() { + CodeGen code = graph(); + Op a = new Op(A,null,null,false,code._start); + Op b = new Op(A,null,null,false,code._start); + Op add = new Op(A,A,null,false,code._start,a,b) { + @Override public boolean commutes() { return true; } + }; + RegionNode region = new RegionNode(null,code._start,code._start); + new PhiNode("sum",TypeInteger.BOT,region,add,a); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,new RegAlloc(code))); + } + + public static void checkRegisters(CodeGen code) { + assertTrue(code._regAlloc.verifyFunctionLocalEdges()); + for( CFGNode bb : code._cfg ) + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach ) { + if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n))); + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i)))); + if( mach.twoAddress()!=0 ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress()))); + } + if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + } + } + + public static void copyClobber() throws Exception { + for( boolean killed : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode hi = code._mach.split("test",(byte)0,null); + hi.setDef(0,code._start); hi.setDef(1,def); + alloc.newLRG(hi)._reg=1; + new Op(null,null,killed ? A : null,false,code._start); + SplitNode lo = code._mach.split("test",(byte)0,null); + lo.setDef(0,code._start); lo.setDef(1,hi); + alloc.newLRG(lo)._reg=0; + Op use = new Op(null,A,null,false,code._start,lo); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame(killed ? lo : def,use.in(1)); + } + CodeGen pre = graph(); + RegAlloc uncolored = new RegAlloc(pre); + Op def0 = new Op(A,null,null,false,pre._start); + uncolored.newLRG(def0)._mask=A; + Op fixed = new Op(A,null,null,false,pre._start); + uncolored.newLRG(fixed)._mask=A; + SplitNode copy = pre._mach.split("test",(byte)0,null); + copy.setDef(0,pre._start); copy.setDef(1,def0); + assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); + } + +} |