diff options
13 files changed, 537 insertions, 106 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)); + } + +} diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 74a181f8..c5a7841d 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -69,13 +69,103 @@ Chapter 25 suite, including `make -j 4 tests`. | Group | Eventual home | Why not in the small queue yet | |---|---|---| -| Register allocation and spilling | 20 onward | Need constrained-register/spill regressions; changed golden spill counts are insufficient evidence. | +| Register allocation and spilling | 20 onward | Chapter 20 correction/support pass complete locally; review before Chapter 21. Staged quality work remains below. | | Conditional Store and array Load control | Memory/arrays chapters | Reproduce under the earlier alias model before extracting fixes from the new memory implementation. | | SCCP dependencies, function revival, reachability | 24; some foundations may fit 18 | Separate old-IR corrections from new Guard/Escape/BulkMemPhi and external-caller machinery. | | TypeScalar, numeric modes, guards, symbolic fields, open/forward types | Revisit earlier homes later | A connected incomplete-types architecture, including phase ordering and errors. | | BulkMemPhi/MemPhi, private constructor memory, allocation helpers | Revisit memory / constructors / methods | Move invariants and regressions together. | | Serialization, global identity remapping, module escape summaries | Separate compilation | Remain with modules. | +## Register allocation: correctness first, staged improvements + +Review on 2026-09-20. The staged plan follows; Chapter 20 +has since been implemented and validated as recorded below. Later snapshots +remain pending. Compared RegAlloc, BuildLRG, IFG, +LRG, Coalesce, RegMask, and split support across 20-25, with the original fix +commits. Allocation starts in 20; 19 has instruction selection/register masks +but no coloring allocator. Most changes are in 20->21 and 24->25. The 22->23 +allocator changes are imports/API cleanup; 23->24 has no allocator changes. + +Cliff's direction: correctness fixes belong at the earliest applicable chapter; +quality improvements should accumulate gradually. Debugging/printing/support +can start in 20. Judge spill changes across a fixed suite, allowing a local +increase when compensated elsewhere. Do not copy the entire Chapter 25 allocator +into 20, and do not classify a whole historical commit by its title. + +### Correctness work to extract + +| Work | Current evidence / source | Earliest intended home | +|---|---|---| +| Register-mask and LRG bookkeeping | Original 20: `RegMask(int)` assigns `bit=64` instead of subtracting 64, and empty `firstReg()` returns 128. `LRG._union` replaces `_machUse` without its `_uidx`, and can retain null from an immutable mask intersection. Fixed in 21; see `7e1deb4c`, `8d6de0e1`. | 20 | +| BuildLRG/IFG instruction contracts | 21 checks null use masks, avoids revisiting CFG projections, processes kills even without an output LRG, and distinguishes an instruction's fixed output from a range narrowed elsewhere. The 25 commutative-input fallback uses `mach.outregmap()` rather than a possibly nonexistent LRG. | 20, after reduced graph/source regressions | +| Self-conflicts and effective splits | 21 visits extending uses before rewriting definitions, permits needed backedge splits, checks intervening clobbers/self-conflicts before reusing splits, and avoids immediately folding away capacity splits. `35057d50`, `cc32b0cf`, and `880329e6` explicitly address failed progress. | 20; preserve Phi parallel-assignment semantics | +| Legal rematerialization | 22 checks a clone's output mask against the use mask before choosing a clone over a move. Otherwise repeated cloning can preserve the original hard conflict. The 25 kill handling chooses the live cloneable value to split rather than the killing instruction (`c05d7df4`). | 20; isolate correctness from ranking cloneable spill candidates | +| Empty-mask split bookkeeping | 25 saves the original def use-count before inserting a split, checks for a missing sample use, and skips null traversal roots. | 20 where the affected helper/path exists | +| Persistent multi-def/fixed-register conflicts | 25 directly splits single-register uses and sometimes splits the deep side of a loop (`c05d7df4`). Its `_ns._len > 5` and related thresholds mix progress with tuning. | Reduce a no-progress case in 20, then extract the smallest sufficient rule; do not transplant thresholds as a proven invariant | +| Encoding and stack ABI support | Correct frame sizing, incoming/outgoing stack arguments, and stack-to-stack move encoding are required once native emission exists (`7e1deb4c`). | 21, where encoding is introduced; retain CPU/ABI distinctions | + +Each correctness packet needs a failure demonstrated against the destination's +old implementation, then allocation completion and legal register use. From +21, also execute native/emulated results. An eight-round cutoff failure is a +correctness failure, not permission to increase the cutoff. Some entries above +are established historical fixes; applicability of the larger 25 changes to +older graphs still needs reproduction. + +### Proposed quality progression + +| Chapter | Additional quality technique | +|---|---| +| 20 | Keep the existing basic coloring, biased coloring, rematerialization, and loop-boundary splitting, corrected for legality/progress. | +| 21 | Conservative copy coalescing, already introduced here. Keep its mask/adjacency correctness fixes with it. | +| 22 | Stronger color preferences: follow loop backedges for bias, improve copy-chain searches, and refine cheap-spill ordering for callee saves/cloneables. | +| 23 | Group popular single-def values by their uses' required register classes instead of splitting each use. Include safe use-list mutation and call-crossing restrictions when introduced. | +| 24 | Try cold splits first for loop-Phi self-conflicts, with a remembered one-attempt limit and aggressive fallback. The delay is optional; its fallback is mandatory. | +| 25 | Rank recovered live-range area against loop-scaled split cost (`a03bc567`), plus any further measured tuning. | + +This progression would move some heuristics currently bundled into 21 later; +it is not just a forward copy. Keep each introduced technique in subsequent +chapters and update the chapter prose with it. Chapter 20's README already +discusses popular-value grouping and coalescing beyond its current code, so +that prose needs realignment too. The one-attempt loop-Phi delay from +`a03bc567` is a quality feature with its own progress safeguard, not a reason +to add persistent deferral state to the first allocator chapter. + +### Support and measurement + +- Start deterministic split ordering, null-safe split printing, useful LRG/mask + diagnostics, and an optional function-local-edge verifier in 20. Preserve the + existing side-effect-free `_` printer accessors. Actual stack offsets require + the frame layout introduced in 21; module-specific exceptions stay in 25. +- Record actual `_spills` and `_spillScaled` for each compilation, keyed by test, + CPU, ABI, and fixed seed. Both count retained SplitNodes; `_spillScaled` weights + each by `8^loopDepth`. These are move/split metrics, not solely memory traffic. +- Compare total scaled counts as the existing quality measure, and report raw + totals plus the largest local changes. Report per CPU/ABI as well as the whole + suite so a regression on one target is visible. Include compilations without + a current golden spill assertion; do not exclude failures or disable checks + to obtain an aggregate. Freeze test membership and seeds for each comparison. +- Compare before/after within each chapter. For tutorial progression, also use + the common program/target subset: totals from different suites or changed IR + are not a controlled allocator comparison. +- Existing helpers assert individual spill goldens (often with tolerance). + Review those local changes against the measured aggregate before updating + expectations. Correctness tests must assert completion/results independently + of the heuristic's exact spill count. +- `splitBypass` originally scanned from `j-1` with `idx++` throughout 20-25, + reaching its own destination and rejecting nonadjacent bypasses. Corrected + in 20 with intervening kill-mask checks and a regression; 21-25 remain pending. + Pre-color copy reuse also checks fixed-register definitions before they have + an assigned `_reg`. Chapter 25 is not a complete correctness reference. + +Suggested execution order: support/measurement, small mask/LRG correctness +fixes, constrained-register and self-conflict regressions/fixes, then one +quality technique at a time. Run each affected snapshot's full suite at each +accepted boundary. Chapter 20 has now been implemented; do not proceed to 21 until Cliff reviews it. +Review each chapter's README along the way. Chapter 21's encoding discussion +should be shortened when that chapter is reached. End each README with its +RegAlloc improvement, measured cohort table, and commentary; the Chapter 25 +table must have rows for cohorts 20-25 using the Chapter 25 compiler. + ## Review and test protocol 1. Run the destination's unmodified `make tests`. Record baseline failures and @@ -116,6 +206,52 @@ Historical results below are dated evidence, not a substitute for a fresh baseline. Logs live in ignored build directories and may no longer exist. Reusable implementation lessons are in `skills/chapter25-codex-notes.md`. +### Chapter 20 allocator: ready for review, 2026-09-20 + +Implemented only in 20, per Cliff's chapter-by-chapter review gate. Corrected +high-word/empty register masks and boundary iteration, LRG mask merging/use-slot +bookkeeping, null register-mask dependencies, commutative outputs used by Phis, +CFG projection visitation, and kills from instructions without output LRGs. +Splits now preserve progress through self-conflicts/backedges and intervening +clobbers. Rematerialization must satisfy the use mask; fixed-register clones +with flexible uses go through use-side splitting instead of a no-op simple +split. Copy cleanup scans backward and respects both fixed definitions and kill +masks. Removed the unused `splitEmptyMask` path and its `_killed` bookkeeping. + +Support includes deterministic failed-range ordering, null-safe split printing, +a function-local-edge diagnostic, and `make spill-stats`. The program tests also +check assigned register masks, two-address constraints, and Phi agreement. +Seven small machine-graph/mask regressions fail against the saved original +implementation and pass after correction, including a round-limit failure for +incompatible clone/use register classes. These are separate from the quality +corpus; they do not supply extra zero-spill examples to improve a total. + +The complete program cohort includes Chapter20Test's 11 examples plus BrainFuck +and MergeSort on all three SystemV targets: 39 compilations, default seed 123. +The fresh original baseline passes 368 tests plus the fuzzer regression. After +forced rebuilds, `make -j 4 tests` passes 375 plus 1. The 11 ordinary examples +also pass 990 compilations across seeds 0-29 and three CPUs, with the current +register/ownership checks enabled. Native execution begins in Chapter 21. + +| SystemV target | Compilations | Original splits | Corrected splits | Original weighted | Corrected weighted | +|---|---:|---:|---:|---:|---:| +| x86-64 | 13 | 80 | 82 | 150 | 152 | +| RISC-V | 13 | 82 | 80 | 103 | 101 | +| ARM | 13 | 73 | 74 | 101 | 102 | +| Total | 39 | 235 | 236 | 354 | 355 | + +This is a one-move correctness cost, not a quality win. Adjusted three local +weighted goldens after reviewing the full aggregate: x86 array 3->5, x86 String +18->21, ARM String 3->5 (the original actual ARM count was 2 within tolerance). +All assertions remain active. The stats runner emits per-compilation data and +fails on any JUnit failure; the Chapter20Test collector allows all three target +checks to run before reporting golden differences. The README preserves Cliff's +new introduction, removes premature coalescing/popular-use-grouping claims, +and ends with the measured baseline and discussion of statistical comparison. +No advanced coalescing, color-bias, grouping, cold-first, or area/cost heuristic +was imported. Logs and the original-code snapshots are under +`chapter20/build/regalloc-review/`. Chapters 21-25 are unchanged. + ### TypeFunPtr normalization: complete locally, 2026-09-20 Backported the trailing-default normalization from `7f3b8856` to 23-24, where diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 4fb182ff..b38d1c29 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -121,6 +121,41 @@ lessons rather than duplicating that history. recursive calls keep this regression meaningful. Check all chain members, registered data edges, and one shared copy per function. +## Register allocation review + +- Allocation starts in 20; native encoding in 21. Backport legality and + no-progress fixes to the first applicable chapter, but introduce spill-quality + heuristics gradually. Do not import the complete Chapter 25 allocator into 20. + Printing, deterministic ordering, and diagnostic support may start in 20. +- Compare measured spill totals over the same tests, targets/ABIs, and seeds. + Local increases are acceptable when offset elsewhere; report per-target and + overall totals. `_spills` counts surviving SplitNodes, and `_spillScaled` + weights those moves by `8^loopDepth`; neither means only memory stores. +- Separate allocation completion/register legality/runtime results from quality + expectations. Reaching the round limit is a correctness bug; raising the + limit or changing spill goldens does not prove progress fixed. Heuristics + which defer necessary splitting must retain a bounded fallback. +- Review the README with each allocator chapter. End it with a RegAlloc + improvements section, a measured table, and commentary. Each row names a + program cohort, all compiled by that directory's compiler: 20 in Chapter 20, + 20-21 in Chapter 21, through 20-25 in Chapter 25. Include the BrainFuck and + MergeSort allocator cases in the Chapter 20 cohort (39 compilations, not just + Chapter20Test's 33). Keep diagnostic machine graphs separate from quality data. +- `make spill-stats` starts in 20. Helpers explicitly name the program cohort; + the JUnit listener labels individual cases and sums CPU/ABI and cohort totals. + Assertions stay enabled and failures propagate. Do not silently change cohort + membership, seeds, or targets when comparing chapters. +- Chapter 20's corrected baseline costs one extra weighted move (354->355 over + 39 compilations); document this as a correctness cost. Advanced quality + heuristics remain staged. Stop after 20 for Cliff's review. When reaching 21, + shorten its excessive encoding detail as requested. +- Copy cleanup/reuse must check kill masks even when an instruction has no LRG; + before coloring, a fixed-register definition can clobber despite `_reg==-1`. + Cloning is valid only if its output mask can satisfy the use. A fixed-register + clone with flexible uses needs use-side splits, not a no-op def-side path. +- The staged plan and historical fix inventory are in + `docs/chapter-backports.md`; its review is not evidence of completed backports. + ## Null guards: B13 / issue #246 lessons - Null refinement starts in Chapter 10; arrays in 15; scoped expression guards |