Ch 20 Reg Alloc

Includes all bug fixes from later chapters, so its at least correct.
Skips a lot of improvement heuristics, these get added in later chapters.
Includes spill-stats, to more easily track improvements.
Includes targeted tests.

9 files changed, 289 insertions, 92 deletions

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));
+    }
+
+}