Forward-port allocator bug fixes and test support through ch25

Improved spilling

9 files changed, 243 insertions, 10 deletions

diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index 20619c1b..647b253e 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter25/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 org.junit.Test;
@@ -23,6 +25,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();
     }
@@ -37,7 +47,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;
@@ -102,7 +112,7 @@ val _test_sqrt_noInline = { flt x ->
 };
 flt farg = arg; return _test_sqrt_noInline(farg) + _test_sqrt_noInline(farg+2.0);
 """;
-        testCPU(src,"x86_64_v2", "SystemV",48,null);
+        testCPU(src,"x86_64_v2", "SystemV",40,null);
         testCPU(src,"riscv"    , "SystemV",17,null);
         testCPU(src,"arm"      , "SystemV",18,null);
     }
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index e8a9e700..e194829a 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter25/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;
@@ -9,6 +10,8 @@ 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 testArmSubtractRegisters() {
         EvalArm64 cpu = new EvalArm64(new byte[16],16);
         cpu.st4(0,0xCB020020); // SUB X0,X1,X2, no shift or flag update.
@@ -79,7 +82,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 && !CodeGen.iterSeedOverridden() )
@@ -447,7 +450,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.runC(src, "arg_count", arg_count, TestC.CALL_CONVENTION.equals("win64") ? 31 : 15);
+        TestC.runC(src, "arg_count", arg_count, TestC.CALL_CONVENTION.equals("win64") ? 35 : 15);
 
         EvalRisc5 R5 = TestRisc5.build( src, "addAll", 0, 4, false);
 
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java
index 96e7fce7..fde523cf 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java
+++ b/chapter25/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.util.Utils;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.node.cpus.arm.arm;
@@ -37,7 +38,7 @@ return new s0.v1;
     }
 
     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 && !CodeGen.iterSeedOverridden() )
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java
index 0e6398ee..923395bf 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java
+++ b/chapter25/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.*;
 
@@ -47,7 +49,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 && !CodeGen.iterSeedOverridden() )
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java
index 1307d2ce..0abdfb3e 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java
+++ b/chapter25/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 && !CodeGen.iterSeedOverridden() )
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java
index 14864d64..d2c6cde4 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.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.cpus.arm.arm;
@@ -14,7 +15,7 @@ public class TestArm64 {
 
     public static EvalArm64 build( String main, String src, int arg, int spills, boolean print ) throws IOException {
         // Compile and export Simple
-        CodeGen code = new CodeGen(src).driver("arm", "SystemV",true,false);
+        CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",true,false);
 
         // Allocation quality not degraded
         int delta = spills>>3;
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java
index 55c62c37..e0ee701a 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java
+++ b/chapter25/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;
@@ -118,7 +119,7 @@ public abstract class TestC {
         String obj = pathBase+".o";
         String exe = pathBase+(OS.startsWith("Windows") ? ".exe" : "");
         // Compile simple, emit ELF
-        CodeGen code = new CodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT);
+        CodeGen code = new CheckedCodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT);
         code.driver( CPU_PORT, simple_conv, false, cfile==null );
 
         linkExe(obj, c_conv, cfile, linkObjs(externPaths), exe);
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java
index 658909ca..1de5e3bc 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java
+++ b/chapter25/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.codegen.Encoding;
 import com.seaofnodes.simple.node.FunNode;
@@ -14,7 +15,7 @@ public abstract class TestRisc5 {
 
     public static EvalRisc5 build( String src, String main, int arg, int spills, boolean print ) throws IOException {
         // Compile and export Simple
-        CodeGen code = new CodeGen(src).driver("riscv", "SystemV",true,false);
+        CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",true,false);
 
         // Allocation quality not degraded
         int delta = spills>>3;
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
new file mode 100644
index 00000000..5e1b276e
--- /dev/null
+++ b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -0,0 +1,212 @@
+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,null), b = new LRG((short)2,null);
+        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",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 modDir, String buildDir, com.seaofnodes.simple.util.Ary<String> externPaths,
+                              String srcName, String src, long seed, boolean reset, TypeInteger arg) {
+            super(modDir,buildDir,externPaths,srcName,src,seed,reset,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,null)._reg=0;
+            SplitNode hi = code._mach.split(null,"test",(byte)0);
+            hi.setDef(0,code._start); hi.setDef(1,def);
+            alloc.newLRG(hi,null)._reg=1;
+            new Op(null,null,killed ? A : null,false,code._start);
+            SplitNode lo = code._mach.split(null,"test",(byte)0);
+            lo.setDef(0,code._start); lo.setDef(1,hi);
+            alloc.newLRG(lo,null)._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,null)._mask=A;
+        Op fixed = new Op(A,null,null,false,pre._start);
+        uncolored.newLRG(fixed,null)._mask=A;
+        SplitNode copy = pre._mach.split(null,"test",(byte)0);
+        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(null,"test",(byte)0);
+            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,null), to = alloc.newLRG(copy,null);
+            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,null), right = new LRG((short)101,null);
+            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());
+            }
+        }
+    }
+
+}