Forward-port allocator bug fixes and test support through ch25

Improved spilling

15 files changed, 351 insertions, 64 deletions

diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
index e9b5eb2e..f4ce4366 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
@@ -40,8 +40,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();
                     }
 
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java
index 6dd6fbf1..bc14aadd 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java
@@ -207,20 +207,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.
-                Node n = (Node)m;
-                CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0();
-                if( m.isClone() &&  // Must be clonable
-                    (n.nOuts()>1 || // Has many users OR
-                     // Only 1 user but effective use is remote block
-                     effUseBlk != n.cfg0() ))
-                    // Then fail the clonable; it should split or move
-                    alloc.fail(alloc.lrg((Node)m));
-                // Else clonable cannot move
-                else if( !tlrg.sub(killMask) )
-                    alloc.fail(tlrg);
+                if( !tlrg.sub(killMask) ) alloc.fail(tlrg);
             }
         }
     }
@@ -438,13 +425,13 @@ abstract public class IFG {
     private static int pickRiskyScore( LRG lrg ) {
         // Pick single-def clonables that are not right next to their single-use.
         // Failing to color these will clone them closer to their uses.
-        if( !lrg._multiDef && lrg._machDef.isClone() ) {
-            Node def = ((Node)lrg._machDef);
-            Node use = ((Node)lrg._machUse);
+        if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) {
+            Node def = (Node)lrg._machDef;
+            Node use = (Node)lrg._machUse;
             CFGNode cfg = def.cfg0();
-            if( cfg != use.cfg0() || // Different blocks OR
+            if( lrg._multiUse || cfg != use.cfg0() || // Many uses or different blocks OR
               // Same block, but not close
-              cfg._outputs.find(def) < cfg._outputs.find(use)+1 )
+              cfg._outputs.find(def)+1 < cfg._outputs.find(use) )
                 return 1000000;
         }
 
@@ -452,7 +439,7 @@ abstract public class IFG {
         // and very cheap to spill.
         if( lrg._machDef instanceof CalleeSaveNode )
             return 1000000-2-lrg._mask.firstReg();
-        if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode &&
+        if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode &&
             lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode )
             return 1000000-1;
 
@@ -506,7 +493,7 @@ abstract public class IFG {
 
     private static int biasable(Node split) {
         if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1
-        if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1;   // Yes biasable, advance is slot 1
+        if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1;   // Prefer the backedge in loops
         if( !(split instanceof MachNode mach) ) return 0; // Not biasable
         return mach.twoAddress();                         // Only biasable if 2-addr
     }
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 10297a9a..adc198fc 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -176,17 +176,35 @@ public class RegAlloc {
                 if( n instanceof NewNode nnn ) nnn.cacheRegs(_code);
         }
 
+        // Optional diagnostic for values accidentally shared across functions.
+        //assert verifyFunctionLocalEdges();
+
         // Top driver: repeated rounds of coloring and splitting.
         byte round=0;
         while( !graphColor(round) ) {
             split(round);
             if( round >= 7 )    // Really expect to be done soon
-                throw Utils.TODO("Allocator taking too long");
+                throw new IllegalStateException("Register allocation made no progress after eight rounds");
             round++;
         }
         postColor();                       // Remove no-op spills
     }
 
+    boolean verifyFunctionLocalEdges() {
+        for( CFGNode bb : _code._cfg ) {
+            if( bb instanceof StartNode ) continue;
+            FunNode fun = bb.fun();
+            for( Node use : bb._outputs )
+                if( use instanceof MachNode mach && !(use instanceof ParmNode) )
+                    for( int i=1; i<use.nIns(); i++ ) {
+                        Node def = use.in(i);
+                        if( def==null || mach.regmap(i)==null || def.cfg0()==null || def.cfg0() instanceof StartNode ) continue;
+                        assert def.cfg0().fun()==fun : "Cross-function register edge: "+def.uniqueName()+" -> "+use.uniqueName()+" input "+i;
+                    }
+        }
+        return true;
+    }
+
     private boolean graphColor(byte round) {
         _failed.clear();
         _lrgs.clear();
@@ -233,7 +251,9 @@ public class RegAlloc {
         if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) {
             if( lrg._1regDefCnt <= 1 &&
                 lrg._1regUseCnt <= 1 &&
-                (lrg._1regDefCnt + lrg._1regUseCnt) > 0 )
+                (lrg._1regDefCnt + lrg._1regUseCnt) > 0 &&
+                // A fixed-register clone with flexible uses must split at the uses.
+                !(lrg._1regDefCnt==1 && lrg._machDef.isClone() && lrg._1regUseCnt==0) )
                 return splitEmptyMaskSimple(round,lrg);
             // Repeated single-reg uses from a single def.  Special for archs
             // with more fixed regs.
@@ -255,16 +275,16 @@ public class RegAlloc {
 
         // Split just after def
         if( lrg._1regDefCnt==1 && !lrg._machDef.isClone() )
-            // Force must-split, even if a prior split same block because register
-            // conflicts.  Example:
+            // An earlier copy is reusable only if no intervening clobber.
+            // Being in the same block alone is insufficient.  Example:
             //   alloc
             //     V1/rax - forced by alloc
             //   alloc
             //     V2/rax - kills prior RAX
             //   st4 [V1],len - No good, must split around
-            insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/);
+            insertAfterAndReplace(makeSplit("def/empty1",round,lrg),(Node)lrg._machDef,false);
         // Split just before use
-        if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) )
+        if( lrg._1regUseCnt==1 )
             insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg);
         return true;
     }
@@ -491,8 +511,8 @@ public class RegAlloc {
     void findAllLRG( LRG lrg ) {
         _ns.clear();
         int wd = 0;
-        _ns.push((Node)lrg._machDef);
-        _ns.push((Node)lrg._machUse);
+        if( lrg._machDef!=null ) _ns.push((Node)lrg._machDef);
+        if( lrg._machUse!=null ) _ns.push((Node)lrg._machUse);
         while( wd < _ns._len ) {
             Node n = _ns.at(wd++);
             if( lrg(n)!=lrg ) continue;
@@ -615,10 +635,10 @@ public class RegAlloc {
                 break;
             hi = hi.in(1);
         }
-        // Check no clobbers
-        for( int idx = j-1; bb.out(idx) != hi; idx++) {
+        // Walk backward from the later copy, including instructions without results.
+        for( int idx = j-1; bb.out(idx) != hi; idx--) {
             Node n = bb.out(idx);
-            if( lrg(n)!=null && lrg(n)._reg == defreg )
+            if( clobbers(n,defreg) )
                 return false;   // Clobbered
         }
         lo.setDefOrdered(1,hi.in(1));
@@ -626,6 +646,12 @@ public class RegAlloc {
     }
 
 
+    private boolean clobbers(Node n, int reg) {
+        LRG lrg = lrg(n);
+        return lrg!=null && (lrg._reg==reg || lrg._reg==-1 && lrg._mask.size1() && lrg._mask.firstReg()==reg) ||
+            n instanceof MachNode mach && mach.killmap()!=null && mach.killmap().test(reg);
+    }
+
     public boolean sameBlockNoClobber( SplitNode split ) {
         Node def = split.in(1);
         CFGNode cfg = def.cfg0();
@@ -639,7 +665,7 @@ public class RegAlloc {
             Node n = cfg.out(idx);
             if( n==def0 ) return true;    // No clobbers
             if( lrg(n) == lrg(def) ) return false; // Self conflict
-            if( lrg(n)!=null && lrg(n)._reg == defreg )
+            if( clobbers(n,defreg) )
                 return false;   // Clobbered
         }
         throw Utils.TODO();
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
index c7dda1da..303bba9e 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
@@ -72,16 +72,12 @@ public class RegMask {
                        : 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; }
@@ -98,8 +94,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/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java
index d06c0c35..df83ce1c 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java
@@ -26,7 +26,9 @@ public class StoreRISC extends MemOpRISC {
         if( i==1 ) return null; // mem
         if( i==2 ) return riscv.RMASK; // ptr
         // 2 - index
-        if( i==4 ) return riscv.MEM_MASK; // Wide mask to store GPR and FPR
+        if( i==4 ) return _sz >= '4'
+                       ? riscv.MEM_MASK   // Word/dword value in GPR or FPR
+                       : riscv.RMASK;     // Byte/short stores require a GPR
         return null; // Anti-dependence
     }
     @Override public RegMask outregmap() { return null; }
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java
index 5f090717..20578467 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java
@@ -66,7 +66,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode {
         if( i==1 ) return null;               // Memory
         if( i==2 ) return x86_64_v2.RMASK;    // base  in GPR
         if( i==3 ) return x86_64_v2.RMASK;    // index in GPR
-        if( i==4 ) return _sz >= 2
+        if( i==4 ) return _sz >= '4'
                        ? x86_64_v2.MEM_MASK   // value in GPR or XMM
                        : x86_64_v2.RMASK;     // Bytes and shorts in GPR only
         return null; // Anti-dependence
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index 760344ec..e668f90d 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -1,5 +1,7 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
+
 
 import com.seaofnodes.simple.codegen.CodeGen;
 import java.io.IOException;
@@ -24,6 +26,14 @@ return f(s);
     }
 
 
+    @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();
     }
@@ -38,7 +48,7 @@ return f(s);
     }
 
     static void testCPU( String src, String cpu, String os, int spills, String stop ) {
-        CodeGen code = new CodeGen(src);
+        CodeGen code = new CheckedCodeGen(src);
         code.driver(CodeGen.Phase.RegAlloc,cpu,os);
         int delta = spills>>3;
         if( delta==0 ) delta = 1;
@@ -83,7 +93,7 @@ val sqrt = { int x ->
 int cast_int = arg+2;
 return sqrt(arg) + sqrt(cast_int);
 """;
-        testCPU(src,"x86_64_v2", "Win64"  ,55,null);
+        testCPU(src,"x86_64_v2", "Win64"  ,48,null);
         testCPU(src,"riscv"    , "SystemV",19,null);
         testCPU(src,"arm"      , "SystemV",19,null);
     }
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 38029ee8..49c95fb8 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.cpus.arm.arm;
 import com.seaofnodes.simple.node.cpus.riscv.riscv;
@@ -12,6 +13,54 @@ import org.junit.Test;
 import static org.junit.Assert.*;
 
 public class Chapter21Test {
+    @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); }
+
+    @Test public void testNarrowStores() throws IOException {
+        for( String type : new String[]{"i8","u8","i16","u16"} ) {
+            String src = "struct S { "+type+" x; }; S !s = new S; s.x = arg; return 0;";
+            CodeGen code = new CodeGen(src).driver("riscv","SystemV",null);
+            int stores=0;
+            for( var bb : code._cfg )
+                for( var node : bb.outs() )
+                    if( node instanceof com.seaofnodes.simple.node.cpus.riscv.StoreRISC st ) {
+                        stores++;
+                        assertEquals("Byte/short stores have no FP encoding",-1,st.regmap(4).nextReg((short)31));
+                    }
+            assertEquals(1,stores);
+            byte[] image = new byte[1<<20];
+            byte[] bits = code._encoding.bits();
+            System.arraycopy(bits,0,image,0,bits.length);
+            EvalRisc5 cpu = new EvalRisc5(image,1<<16);
+            cpu.regs[riscv.A0] = 0x8765;
+            assertEquals(0,cpu.step(100));
+            assertEquals(type.endsWith("8") ? 0x65 : 0x8765,
+                         type.endsWith("8") ? cpu.ld1z(1<<16) : cpu.ld2z(1<<16));
+            code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"x86_64_v2",TestC.CALL_CONVENTION);
+            stores=0;
+            for( var bb : code._cfg )
+                for( var node : bb.outs() )
+                    if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) {
+                        stores++;
+                        assertEquals("Byte/short stores have no XMM encoding",-1,st.regmap(4).nextReg((short)15));
+                    }
+            assertEquals(1,stores);
+        }
+    }
+
+    @Test public void testNativeExitStatus() throws IOException {
+        Path source = Path.of("build/objs/nativeExit.c");
+        Files.createDirectories(source.getParent());
+        Files.writeString(source,"int main() { return 7; }\n");
+        try {
+            TestC.gcc(source.toString(),null,null,false,
+                      "build/objs/nativeExit"+(TestC.OS.startsWith("Windows") ? ".exe" : ""));
+        } catch( AssertionError error ) {
+            assertTrue(error.getMessage(),error.getMessage().contains("Program exit status"));
+            return;
+        }
+        fail("A failing native program must fail the test, even with empty stdout");
+    }
+
     @Test public void testArmSubtractRegisters() {
         EvalArm64 cpu = new EvalArm64(new byte[16],16);
         cpu.st4(0,0xCB020020); // SUB X0,X1,X2, no shift or flag update.
@@ -82,7 +131,7 @@ return new s0.v1;
     }
 
     static void testCPU( String src, String cpu, String os, int spills, String stop ) {
-        CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
+        CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
         int delta = spills>>3;
         if( delta==0 ) delta = 1;
         if( spills != -1 )
@@ -323,11 +372,11 @@ val sieve = { int N ->
         String sprimes = sb.p("]").toString();
 
         // Compile, link against native C; expect the above string of primes to be printed out by C
-        TestC.run(src, "sieve", null, sprimes, 257);
+        TestC.run(src, "sieve", null, sprimes, 186);
 
         // Evaluate on RISC5 emulator; expect return of an array of primes in
         // the simulated heap.
-        EvalRisc5 R5 = TestRisc5.build("sieve", src, 100, 160, false);
+        EvalRisc5 R5 = TestRisc5.build("sieve", src, 100, 92, false);
         int trap = R5.step(10000);
         assertEquals(0,trap);
         // Return register A0 holds sieve(100)
@@ -339,7 +388,7 @@ val sieve = { int N ->
 
         // Evaluate on ARM5 emulator; expect return of an array of primes in
         // the simulated heap.
-        EvalArm64 A5 = TestArm64.build("sieve", src, 100, 160, false);
+        EvalArm64 A5 = TestArm64.build("sieve", src, 100, 94, false);
         int trap_arm = A5.step(10000);
         assertEquals(0, trap_arm);
         int ary_arm = (int)A5.regs[arm.X0];
@@ -450,7 +499,7 @@ val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, i
 """;
         String arg_count = "191.000000\n";
 
-        TestC.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 42 : 15);
+        TestC.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15);
 
         EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", src, 0, 4, false);
 
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
index 78b9e7a1..fa9036d2 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
 import com.seaofnodes.simple.codegen.CodeGen;
 import java.io.IOException;
 import java.nio.file.Files;
@@ -39,7 +40,7 @@ fib(10);
     }
 
     static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) {
-        CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
+        CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
         int delta = spills>>3;
         if( delta==0 ) delta = 1;
         if( spills != -1 )
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java
index 56a672aa..661d4f39 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java
@@ -1,4 +1,6 @@
 package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 
@@ -90,7 +92,7 @@ public class Chapter23Test {
 
 
     static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) {
-        CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
+        CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
         int delta = spills>>3;
         if( delta==0 ) delta = 1;
         if( spills != -1 )
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
index a4fb5829..a1dd6eaa 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java
@@ -1,4 +1,6 @@
 package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 
@@ -37,7 +39,7 @@ public class Chapter24Test {
     }
 
     static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) {
-        CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
+        CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os);
         int delta = spills>>3;
         if( delta==0 ) delta = 1;
         if( spills != -1 )
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java
index a1c02ede..d0fdae0c 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java
@@ -1,5 +1,7 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
+
 
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.cpus.arm.arm;
@@ -27,7 +29,7 @@ public class TestArm64 {
     // Compile and run a simple program
     public static EvalArm64 build( String dir, String src, String file, int arg, int spills, boolean print ) throws IOException {
         // Compile and export Simple
-        CodeGen code = new CodeGen(src).driver("arm", "SystemV",null);
+        CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null);
         if( print ) { code.print_as_hex(); System.out.print(code.asm()); }
 
         // Allocation quality not degraded
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java b/chapter24/src/test/java/com/seaofnodes/simple/TestC.java
index f1831929..aed9f844 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/TestC.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.util.Ary;
@@ -75,7 +76,7 @@ public abstract class TestC {
         String obj = bin+".o";
         String exe = OS.startsWith("Windows") ? bin+".exe" : bin;
         // Compile simple, emit ELF
-        CodeGen code = new CodeGen(src, arg).driver( CPU_PORT, simple_conv, obj);
+        CodeGen code = new CheckedCodeGen(src, arg).driver( CPU_PORT, simple_conv, obj);
 
         String result = gcc(obj, c_conv, cfile, false, exe );
         assertEquals(expected,result);
@@ -130,10 +131,9 @@ public abstract class TestC {
         ProcessBuilder smp = new ProcessBuilder(args);
         if( stdin ) smp.redirectInput(ProcessBuilder.Redirect.INHERIT);
         Process p = smp.start();
-        try { exit = (byte)p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); }
+        try { exit = p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); }
         result = new String(p.getInputStream().readAllBytes());
-        if( exit!=0 )
-            System.err.println("exec exit code: "+exit);
+        assertEquals("Program exit status",0,exit);
         return result;
     }
 }
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java
index a8f6817e..72a05c61 100644
--- a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java
+++ b/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple;
 
+import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.FunNode;
 import com.seaofnodes.simple.node.Node;
@@ -26,7 +27,7 @@ public abstract class TestRisc5 {
     // Compile and run a simple program
     public static EvalRisc5 build( String dir, String src, String file, String main, int arg, int spills, boolean print ) throws IOException {
         // Compile and export Simple
-        CodeGen code = new CodeGen(src).driver("riscv", "SystemV",null);
+        CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null);
         if( print ) { code.print_as_hex(); System.out.print(code.asm()); }
 
         // Allocation quality not degraded
diff --git a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
new file mode 100644
index 00000000..b2d14a02
--- /dev/null
+++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -0,0 +1,209 @@
+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 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 void encoding(Encoding enc) { throw new AssertionError(); }
+    }
+    private static CodeGen graph() {
+        CodeGen code = new CodeGen("");
+        code._mach = new x86_64_v2(code);
+        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)));
+    }
+
+    // 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); }
+        public CheckedCodeGen(String src, TypeInteger arg) { super(src,arg); }
+        @Override public CodeGen regAlloc() {
+            super.regAlloc();
+            checkRegisters(this);
+            return this;
+        }
+    }
+
+    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));
+    }
+
+    public static void coalescing() {
+        // Merge, incompatible masks, interference, capacity, and adjacency remapping.
+        for( int kind=0; kind<5; kind++ ) {
+            CodeGen code = graph();
+            RegAlloc alloc = new RegAlloc(code);
+            Op def = new Op(new RegMask(3L),null,null,false,code._start);
+            SplitNode copy = code._mach.split("test",(byte)0,null);
+            copy.setDef(0,code._start); copy.setDef(1,def);
+            Op use = new Op(null,new RegMask(3L),null,false,code._start,copy);
+            LRG from = alloc.newLRG(def), to = alloc.newLRG(copy);
+            from._mask = kind==1 ? A : new RegMask(3L);
+            to._mask = kind==1 ? B : new RegMask(3L);
+            from.machDef(def,false); from.machUse(copy,(short)1,false);
+            to.machDef(copy,false); to.machUse(use,(short)1,false);
+            LRG left = new LRG((short)100), right = new LRG((short)101);
+            if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); }
+            if( kind>=3 ) {
+                from.addNeighbor(left); left.addNeighbor(from);
+                if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); }
+                else { to.addNeighbor(left); left.addNeighbor(to); }
+            }
+            int fcnt=from.nadj(), tcnt=to.nadj();
+            assertTrue(Coalesce.coalesce(0,alloc));
+            if( kind==0 || kind==4 ) {
+                assertSame(def,use.in(1));
+                assertSame(alloc.lrg(def),alloc.lrg(copy));
+                assertSame(use,alloc.lrg(def)._machUse);
+                assertEquals(1,alloc.lrg(def)._uidx);
+                if( kind==4 ) {
+                    assertEquals(1,left.nadj());
+                    assertSame(alloc.lrg(def),left._adj.at(0));
+                    assertSame(left,alloc.lrg(def)._adj.at(0));
+                }
+            } else {
+                assertSame(copy,use.in(1));
+                assertNotSame(alloc.lrg(def),alloc.lrg(copy));
+                assertEquals(fcnt,from.nadj());
+                assertEquals(tcnt,to.nadj());
+            }
+        }
+    }
+
+}