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.

3 files changed, 249 insertions, 31 deletions

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