Chapter 25: Modules, Separate Compilation, and SSA Constructionlinear

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

3 files changed, 82 insertions, 150 deletions

diff --git a/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java
index b9b49c9f..b255bcf7 100644
--- a/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java
+++ b/src/test/java/com/seaofnodes/simple/codegen/PrintRegTestSupport.java
@@ -7,9 +7,9 @@ public class PrintRegTestSupport {
         var code = new CodeGen("return 0;").parse();
         var alloc = new RegAlloc(code);
         var n = new ConstantNode(TypeInteger.ZERO);
-        var a = new LRG((short)1);
-        var b = new LRG((short)2);
-        var c = new LRG((short)3);
+        var a = new LRG((short)1,null);
+        var b = new LRG((short)2,null);
+        var c = new LRG((short)3,null);
         a._reg = -1;
         c._leader = b;
         b._leader = a;
@@ -23,4 +23,54 @@ public class PrintRegTestSupport {
         assertSame(b,c._leader);
         assertSame(a,b._leader);
     }
+    public static void checkConstantPool() throws Exception {
+        var code = new CodeGen("return 0;").parse();
+        code._phase = CodeGen.Phase.Encoding;
+        var enc = new Encoding(code);
+        var t = com.seaofnodes.simple.type.TypeStruct.make("PrintPool",false,
+            com.seaofnodes.simple.type.Field.make("x",TypeInteger.ZERO,2,true));
+        var n = new ConstantNode(TypeInteger.ZERO);
+        enc.largeConstant(n,t,0,2);
+        int size = t.size(); // Encoding lays out data before printing the pool.
+        for( int i=0; i<size; i++ ) enc._cpool.write(0);
+        // Layout queries are forbidden during printing, even if they would
+        // happen to return a cached answer without changing the type.
+        boolean[] printing = {false};
+        var scalar = new com.seaofnodes.simple.type.Type(com.seaofnodes.simple.type.Type.BOTTOM._type) {
+            @Override public int alignment() {
+                assertFalse("alignment queried by printer",printing[0]);
+                return 0;
+            }
+            @Override public int size() {
+                assertFalse("size queried by printer",printing[0]);
+                return 1;
+            }
+            @Override public String str() { return "LayoutProbe"; }
+        };
+        var scalarNode = new ConstantNode(TypeInteger.TRUE);
+        enc._bigCons.put(scalarNode,new Encoding.Relo(scalarNode,scalar,(byte)0,(byte)2));
+        enc._cpool.write(0);
+        printing[0] = true;
+        var offsets = com.seaofnodes.simple.type.TypeStruct.class.getDeclaredField("_offs");
+        offsets.setAccessible(true);
+        offsets.set(t,null); // Printer must not lazily rebuild the cached layout.
+        var field = com.seaofnodes.simple.type.Type.class.getDeclaredField("VISIT");
+        field.setAccessible(true);
+        var visit = (java.util.Map<Object,Object>)field.get(null);
+        var marker = new Object();
+        visit.put(marker,t);
+        var method = com.seaofnodes.simple.print.ASMPrinter.class.getDeclaredMethod(
+            "printConstantPool",int.class,com.seaofnodes.simple.util.SB.class,
+            com.seaofnodes.simple.util.BAOS.class,java.util.HashMap.class,boolean.class,String.class);
+        method.setAccessible(true);
+        try {
+            var sb = new com.seaofnodes.simple.util.SB();
+            method.invoke(null,0,sb,enc._cpool,enc._bigCons,true,"Constant Pool");
+            assertTrue(sb.toString().contains("PrintPool"));
+            assertTrue(sb.toString().contains("LayoutProbe"));
+            assertNull(offsets.get(t));
+            assertSame(t,visit.get(marker));
+            assertEquals(1,visit.size());
+        } finally { visit.clear(); }
+    }
 }
diff --git a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
index 1ffdb3d0..93380c87 100644
--- a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
+++ b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -33,8 +33,8 @@ public class RegAllocTestSupport {
         CodeGen code = graph();
         RegAlloc alloc = new RegAlloc(code);
         Op def = new Op(new RegMask(3L),null,null,false,code._start);
-        LRG lrg = alloc.newLRG(def);
-        LRG neighbor = new LRG((short)99);
+        LRG lrg = alloc.newLRG(def,null);
+        LRG neighbor = new LRG((short)99,null);
         neighbor._mask = A;
         lrg.addNeighbor(neighbor); // Uncolored, but its only possible color is A.
         var bias = IFG.class.getDeclaredMethod("biasColorNeighbors",RegAlloc.class,Node.class,RegMask.class);
@@ -59,7 +59,7 @@ public class RegAllocTestSupport {
     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);
+        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);
@@ -113,7 +113,7 @@ public class RegAllocTestSupport {
             @Override public boolean commutes() { return true; }
         };
         RegionNode region = new RegionNode(null,code._start,code._start);
-        new PhiNode("sum",TypeInteger.BOT,region,add,a);
+        new PhiNode("sum",region,add,a);
         code._cfg.add(region);
         assertTrue(BuildLRG.run(0,new RegAlloc(code)));
     }
@@ -131,7 +131,7 @@ public class RegAllocTestSupport {
             RegAlloc alloc = new RegAlloc(code);
             RegionNode block = new RegionNode(null,code._start,code._start);
             Op def = new Op(new RegMask(7L),null,null,false,block);
-            LRG lrg = alloc.newLRG(def);
+            LRG lrg = alloc.newLRG(def,null);
             lrg._machDef = def;
             lrg._mask = new RegMask(0L);
             Op ab = new Op(null,new RegMask(3L),null,false,block,def);
@@ -163,10 +163,14 @@ public class RegAllocTestSupport {
     // 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); }
+        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);
+            com.seaofnodes.simple.SpillStats.record25(this);
             return this;
         }
     }
@@ -180,7 +184,7 @@ public class RegAllocTestSupport {
             Op def = new Op(A,null,null,false,code._start);
             Node top = new ConstantNode(com.seaofnodes.simple.type.Type.TOP);
             RegionNode region = new RegionNode(null,code._start,code._start);
-            PhiNode phi = new PhiNode("value",TypeInteger.BOT,region,slot==1 ? top : def,slot==2 ? top : def);
+            PhiNode phi = new PhiNode("value",region,slot==1 ? top : def,slot==2 ? top : def);
             phi._type = TypeInteger.BOT;
             new Op(null,A,null,false,region,phi);
             code._cfg.add(region);
@@ -220,14 +224,14 @@ public class RegAllocTestSupport {
             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);
+            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)._reg=1;
+            alloc.newLRG(hi,null)._reg=1;
             new Op(null,null,killed ? A : null,false,code._start);
-            SplitNode lo = code._mach.split("test",(byte)0,null);
+            SplitNode lo = code._mach.split(null,"test",(byte)0);
             lo.setDef(0,code._start); lo.setDef(1,hi);
-            alloc.newLRG(lo)._reg=0;
+            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);
@@ -236,10 +240,10 @@ public class RegAllocTestSupport {
         CodeGen pre = graph();
         RegAlloc uncolored = new RegAlloc(pre);
         Op def0 = new Op(A,null,null,false,pre._start);
-        uncolored.newLRG(def0)._mask=A;
+        uncolored.newLRG(def0,null)._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);
+        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));
     }
@@ -249,13 +253,14 @@ public class RegAllocTestSupport {
             CodeGen code = graph();
             RegAlloc alloc = new RegAlloc(code);
             Op init = new Op(A,null,null,false,code._start);
-            LoopNode loop = new LoopNode(null,code._start);
-            PhiNode phi = new PhiNode("loop",TypeInteger.BOT,loop,init,null);
+            LoopNode loop = new LoopNode(null,null,code._start);
+            PhiNode phi = new PhiNode("loop",loop,init,null);
+            phi._type = TypeInteger.BOT;
             Op back = new Op(A,A,null,false,loop,phi);
             phi.setDef(2,back);
             Op use = new Op(null,A,null,false,loop,phi);
             loop.setDef(2,loop);
-            LRG lrg = alloc.newLRG(phi);
+            LRG lrg = alloc.newLRG(phi,null);
             lrg._mask = A;
             alloc.union(lrg,init); alloc.union(lrg,back);
             lrg.selfConflict(back);
@@ -278,10 +283,10 @@ public class RegAllocTestSupport {
             CodeGen code = graph();
             RegAlloc alloc = new RegAlloc(code);
             Op def = new Op(A,null,null,false,code._start);
-            alloc.newLRG(def)._reg=0;
-            SplitNode copy = code._mach.split("test",(byte)0,null);
+            alloc.newLRG(def,null)._reg=0;
+            SplitNode copy = code._mach.split(null,"test",(byte)0);
             copy.setDef(0,code._start); copy.setDef(1,def);
-            alloc.newLRG(copy)._reg=1;
+            alloc.newLRG(copy,null)._reg=1;
             if( kind==3 ) new Op(null,null,A,false,code._start);
             int twoAddress = kind==2 ? 1 : 0;
             RegMask mask = kind==1 ? B : kind==5 ? null : new RegMask(3L);
@@ -302,15 +307,15 @@ public class RegAllocTestSupport {
             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);
+            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), to = alloc.newLRG(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), right = new LRG((short)101);
+            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);
diff --git a/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java
deleted file mode 100644
index 0914d916..00000000
--- a/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java
+++ /dev/null
@@ -1,123 +0,0 @@
-package com.seaofnodes.simple.codegen;
-
-import com.seaofnodes.simple.node.Node;
-import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86;
-import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86;
-import com.seaofnodes.simple.node.cpus.x86_64_v2.MulIX86;
-import org.junit.Test;
-import static org.junit.Assert.*;
-
-public class X86EncodingTest {
-
-    @Test
-    public void testLogicalNotRegisters() {
-        CodeGen code = new CodeGen("return !arg;")
-            .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV");
-        var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null);
-        assertNotNull("Must exercise logical not", not);
-        int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}};
-        // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping
-        // registers, low-byte registers requiring REX, and extended registers.
-        String[] expected = {
-            "4885c00f94c00fb6c0", "4885c90f94c10fb6c9",
-            "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9",
-            "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9",
-            "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff"
-        };
-        for (int i = 0; i < registers.length; i++) {
-            int dst = registers[i][0], src = registers[i][1];
-            var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src);
-            not.encoding(enc);
-            assertArrayEquals("Logical not dst=" + dst + ", src=" + src,
-                java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray());
-        }
-    }
-
-    @Test
-    public void testLogicalNotExecution() throws java.io.IOException {
-        var dir = java.nio.file.Path.of("build/objs");
-        java.nio.file.Files.createDirectories(dir);
-        java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"),
-            "val logicalNot = { int x -> return !x; };");
-        java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """
-            #include <limits.h>
-            extern long long logicalNot(long long);
-            int main(void) {
-                long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32};
-                for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++)
-                    if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1;
-                return 0;
-            }
-            """);
-        com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1);
-    }
-
-    @Test
-    public void testMultiplyImmediateRegisters() {
-        // Destination, source, expected REX and ModRM. Cross the register-8
-        // boundary in both directions, with low/low and high/high controls.
-        int[][] cases = {{1, 9, 0x49, 0xC9}, {9, 1, 0x4C, 0xC9},
-                         {1, 2, 0x48, 0xCA}, {9, 10, 0x4D, 0xCA}};
-        for (int immediate : new int[]{11, -11, 123456789, -123456789}) {
-            CodeGen code = new CodeGen("return arg * " + immediate + ";")
-                .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV");
-            var mul = code._stop.walk(n -> n instanceof MulIX86 ? n : null);
-            assertNotNull("Must exercise immediate multiply", mul);
-            for (int[] regs : cases) {
-                var enc = new FixedRegisterEncoding(
-                    code, mul, regs[0], mul.in(1), regs[1]);
-                ((MulIX86)mul).encoding(enc);
-                boolean small = immediate == 11 || immediate == -11;
-                assertEquals("REX for dst=" + regs[0] + ", src=" + regs[1], regs[2], enc.read1(0));
-                assertEquals(small ? 0x6B : 0x69, enc.read1(1));
-                assertEquals(regs[3], enc.read1(2));
-                assertEquals(small ? 4 : 7, enc._bits.size());
-                assertEquals(immediate, small ? (byte)enc.read1(3) : enc.read4(3));
-            }
-        }
-    }
-    @Test
-    public void testMemoryCompare64Immediate32() {
-        for (int immediate : new int[]{123456789, -123456789}) {
-            String src = "int[] !a = new int[2]; a[0] = arg; return a[arg & 1] == " + immediate + ";";
-            CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding, "x86_64_v2", "SystemV");
-            var cmp = code._stop.walk(n -> n instanceof CmpMemX86 ? n : null);
-            assertNotNull("Must exercise a memory comparison", cmp);
-            var enc = code._encoding;
-            int start = enc._opStart[cmp._nid];
-
-            // REX.W, 81 /7, SIB with scale 8, disp8, and a sign-extended imm32.
-            assertEquals(0x48, enc.read1(start) & 0xF8);
-            assertEquals(0x81, enc.read1(start + 1));
-            assertEquals(0x7C, enc.read1(start + 2));
-            assertEquals(0xC0, enc.read1(start + 3) & 0xC0);
-            assertEquals(8, enc.read1(start + 4));
-            assertEquals(immediate, enc.read4(start + 5));
-            assertEquals("CMP r/m64 uses four immediate bytes", 9, enc._opLen[cmp._nid]);
-
-            // SETE must immediately follow the CPU's nine-byte CMP instruction.
-            assertEquals(0x0F, enc.read1(start + 9));
-            assertEquals(0x94, enc.read1(start + 10));
-        }
-    }
-
-    /** Exercise instruction encoders with explicit registers, independent of allocator choices. */
-    private static class FixedRegisterEncoding extends Encoding {
-        private final Node _dst, _src;
-        private final short _dstReg, _srcReg;
-
-        FixedRegisterEncoding(CodeGen code, Node dst, int dstReg, Node src, int srcReg) {
-            super(code);
-            _dst = dst;
-            _src = src;
-            _dstReg = (short)dstReg;
-            _srcReg = (short)srcReg;
-        }
-
-        @Override public short reg(Node n) {
-            if (n == _dst) return _dstReg;
-            if (n == _src) return _srcReg;
-            throw new AssertionError("Unexpected register lookup");
-        }
-    }
-}